Part: Algorithms and Datastructures

For this part you need to have knowledge about the typical topics on datastructures and algorithms and their runtime and memory complexities. Possible materials/literature:

e.g. Cormen, Leiserson, Rivest, Stein (2009) Introduction to Algorithms (3rd Edition). MIT Press, Cambridge, London [CLR]
050015 VO Algorithmen und Datenstrukturen (2016S) [ADS]

Topics:

Types of algorithms/ algorithm classes [ADS1.2]
- brute force
- greedy algorithms [ADS1.2.1; CLR16]
- divide and conquer algorithms [ADS1.2.2; CLR4] (problem size division, step size division, case division, ...)
- dynamic programming [ADS1.2.3; CLR15]
- randomized algorithms [CLR5/5.3]
Analysis and evaluation of algorithms [ADS1.3; CLR2.2]
- efficiency (solvable? convertable into program?) [ADS1.3.1; CLR1.2]
- correctness (testing, verification) [ADS1.3.2; CLR2.1]
- termination (sometimes 1-to-1 projetion to integers, size is positive and is continuously decremented) [ADS1.3.3; CLR2.1]
- complexity (runtime complexity, memory complexity, structural complexity) [ADS1.3.4; CLR3]
  - Bachmann-Landau notation / asymptotic notation: O, Omega, Theta [CLR3.1]
  - worst-case, best-case, average-case [CLR2.2]
  - calculation rules (ignore constants, use only highest exponent, etc)
  - Master Theorem [CLR4.5]
Data structures: [ADS2; CLR]
- basic structures like vectors and arrays [ADS3; CLR]
- sequential structures like lists, stacks, queues [CLR10]
- hash tables [ADS3.2; CLR11]
  - vectors, dictionary, hash tables, collisions [ADS3; CLR]
  - hash functions (modulo: key mod m, bitstring interpretations, transformations tables/functions)
  - collisions and solutions like linear probing / linear hashing, separate chaining, double hashing [ADS3.2, ADS3.3; CLR11.2, CLR11.4]
- trees like binary trees, B+ trees, priority queues etc. (see below)
Sorting algorithms:
- Selection Sort [ADS3.4.1; CLR2.2 (Ex2.2-2)]
- Insertion Sort [CLR2.1]
- Bubble Sort [ADS3.4.2; CLR2.3 (Ex2-2)]
- Quicksort [ADS3.4.3; CLR7]
- Mergesort [ADS3.4.4; CLR2.3.1]
- Heapsort [ADS3.4.3; CLR6]
- linear time sorting algorithms like Counting Sort, Radix Sort, Bucket Sort [ADS3.5; CLR8]
- external sorting (disks/tapes) [ADS3.6; CLR]
  - Balanced Multiway Merge Sort, [ADS3.6.1]
  - Replacement Selection, [ADS3.6.2]
  - Polyphase Merge Sort [ADS3.6.3]
- heap sort [ADS5.9.2; CLR6]
- stable sorting approaches [CLR8.2]
Lists [ADS4.1; CLR10.2]
- implementations (memory types: Contiguous memory, Scattered (Linked) memory, static / dynamic [ADS4.2; CLR]
- operations (insert, access, delete, generate/construct, length, is_element, add, 1st_element, delete_1st/remove_1st) and their complexities
- Doubly Linked List [CLR10.2]
Stacks and Queues [ADS4.3, ADS4.4; CLR10.1]
- stack operations (push, top, pop, empty, construct/destruct) and their complexities
- queue operations (enqueue, dequeue, front, empty, construct/destruct) and their complexities
Trees [ADS5; CLR]
- definitions (node, edge, path, root, leaf, recursion, length, height, depth)
- unordered trees, ordered trees, balanced trees, binary trees vs multiway trees
- binary trees (empty binary tree, full binary tree, perfect binary tree, complete binary tree, height-balanced binary tree) [ADS5.2; CLRB.5]
  - tree traversal (preorder/postorder/inorder traversal) [CLR12.1]
  - binary search trees (features, operations, runtime) [ADS5.3; CLR12]
    - red-black trees, AVL trees [CLR13]
  - multiway trees [ADS5.4]
    - 2-3-4 trees (overflow and split, underflow, operations) [CLR18.1 (B-tree)]
  - external storage management [ADS5.6; CLR]
  - B+ trees (perfect height-balanced multiway tree, operations) [ADS5.7]
  - trie (digital search tree or prefix tree) [ADS5.8; CLR]
    - Patricia Trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric)
    - de la Briandais Trie (list representation of a trie)
  - priority queues (operations, implementation) [ADS5.9; CLR6.5]
  - heap [ADS5.9.1 ; CLR6.1]
  - heap sort [ADS5.9.2; CLR6]
- Graphs [ADS6; CLR22]
  - definitions (node, edge, path, cycle, connected graphs, (strongly) connected components, subgraphs) root, leaf, recursion, length, height, depth, degree, induced subgraphs)
  - undirected graphs [ADS6.1; CLR22]
  - directed graphs [ADS6.2; CLR22]
  - implementation of graphs (DAG, adjacency matrix, adjacency list) [ADS6.3; CLR22.1]
  - topological sorting [ADS6.4; CLR22.4]
  - Euler path, Euler cycle/tour
  - graph traversal [ADS6.5; CLR]
    - depth-first search (recursive, iterative) [ADS6.5.1; CLR22.3]
    - breadth-first search [ADS6.5.2; CLR22.2]
    - general iterative approach [ADS6.5.3; CLR]
  - minimal spanning tree (MST) [ADS6.6; CLR23]
    - Kruskal [ADS6.6.1; CLR23.2]
    - Prim [ADS6.6.2; CLR23.2]
  - shortest paths [ADS6.7; CLR24+25]
    - Single Source Shortest Paths: Dijkstra Algorithm [ADS6.7.1; CLR24]
    - All Pairs Shortest Paths: Floyd-Warshall algorithm (based on transitive closure, shortest paths) [ADS6.7.2 ; CLR25]
    - problems with negative edge weights
  - Dynamic Programming approaches on graphs (transitive closure, Floyd-Warshall algorithm, Fibonacci numbers, Knapsack problem)
- Dynamic Programming algorithms [ADS7; CLR15]
  - definition
  - application (Knapsack problem, sequence of matrix multiplication, longest common subsequences)
- String Matching algorithms [CLR32]
  - naive approach, Rabin-Karp algorithm, String matching with finite automata (string-matching-automata), Knuth-Morris-Pratt algorithm