Teaching

See TUMonline

The exam takes the form of a 90 minutes written test. In the written exam, based on the questions posed, the students are intended to demonstrate that they have fundamental knowledge in the area of algorithms and data structures. They are able to apply their knowledge successfully in order to solve given problems. In addition, by answering the questions, the students are expected to show that they have profound knowledge of the fundamental algorithmic methods and data structures covered in the module. The students prove that they are able to recognize and analyze basic algorithmic problems and to find efficient solutions within a limited scope of time.

Content: - basics of efficiency and complexity analysis (terms, measures, Landau symbols, machine model) - data structures for sequences (dynamic arrays, lists, stacks, queues, with complexity of operations) - Hashing (hashing with chaining, universal hashing, hashing with probing; optional: perfect hashing, hash-based algorithms, e.g., set intersection) - Sorting (simple methods: InsertionSort, SelectionSort, BubbleSort; analysis of MergeSort, HeapSort, and QuickSort; optional: sorting-based algorithms, e.g., set intersection; lower bound for comparison-based sorting, selection, RadixSort, external sorting) - priority queues (binary heaps, binomial heaps) - search trees (binary search trees, AVL trees, (a,b)-trees) - graph algorithms (graph representation, traversal via DFS/BFS, 2-connected components, strongly connected components, topological sorting, shortest paths, minimum spanning trees, optional: TSP) - optional: data compression (Huffman, Lempel-Ziv) - optional: basic algorithms in pattern matching

Modul IN0001 (esp. Java)