Algorithms - Interactive curriculae of TU Ilmenau

General mathematical maturity:

• Knowing objects like sets, relations, (integer, real, complex) numbers, functions, matrices and vectors, directed and undirected graphs, propositional logic and Boolean algebra.
• Formulate and understand mathematical definitions, theorems and proofs.
• Familiarity with proof techniques such as induction, proof by contradiction, proving the contrapositive. 

Algorithms and data structures:

• Fundamental iterative programing concepts (variables, conditionals, loops, subroutines, recursion). Understanding pseudo-code descriptions of algorithms and beeing able to implement them in some programing language.
• Basic runtime analysis of iterative programs; growth of functions and asymptotic notation.
• Knowing abstract data types and data structures: arrays, lists, stacks, queues, (balanced) search trees, heaps, dictionaries.
• Knowing fundamental algorithms such as binary search, sorting algorithms, tree traversal, breadth-first-search and depth-first-search.

The students know the basic principles of the design and the analysis of algorithms: correctness and running time. They know the Big-O notation and its use for analyzing running times. They know basic number theoretical algorithms (addition, multiplication, division, modular multiplication, modular exponentiation, greatest common divisor), they know basic primality tests and the RSA encryption scheme. The students know the divide-and-conquer paradigm with the master theorem (and its proof) and the most important examples like Karatsuba's algorithm, Strassen's algorithm, Mergesort, Quicksort, and the Fast Fourier Transform. They know basic techniques for orienting oneself in graphs and digraphs: BFS, DFS, Kosaraju's algorithm for strongly connected components. They know Dijkstra's algorithm for calculating shortest paths in graphs, and the data type priority queue with its most important implementation techniques "binary heap" and "d-ary heap". Out of the family of greedy algorithms they know Kruskal's algorithm and Prim's algorithm for the problem of a mimimum spanning tree, including the correctness proof and the runtime analysis including the use of the union find data structure. As another greedy algorithm they know Huffman's algorithm for an optimal binary code. In the context of the dynamic programming paradigm the students know the principal approach as well as the specific algorithms for Edit distance, all-pairs shortest paths (Floyd-Warshall), single-source shortest paths with edge lengths (Bellman-Ford), knapsack problems and matrix chain multiplication. They know the basic definitions and facts from NP-completeness theory, in particular the implications one gets (if P <> NP) from  the fact that a search problem is NP-complete as well as central examples of NP-complete problems.

Methodenkompetenz: The students can formulate the relevant problems and can describe the algorithms that solve the problems. They are able to carry out the algorithms for example inputs, to prove correctness and analyze the running time. They are able to apply algorithm paradigms to create algorithms in situations similar to those treated in the course. They can explain the significance of the concept of NP-completeness and identify some selected NP-complete problems.

Sozialkompetenz: The international students, coming from different countries and different backgrounds, have experienced and trained working together despite of such differences. The lectures make it necessary to respect the right of all other students to a concentrated working atmosphere, while being open for discussion of the subject matter. The students can participate in the discussion of the material in an organized manner. The students can participate actively and interactively in the discussion of the exercise problems in the discussion sessions. They have also experienced the possibility of different approaches to an algorithmic problem within the rules of the game and the state of the art. The (voluntary) practice sessions further have improved the students' ability to explore and assess the significance of the theoretical results of the lecture.  

The course covers a variety of problems and algorithms along different algorithm design strategies. It includes the formal specification and complexity analysis of problems as well as the runtime analysis and proof of correctness of algorithms. The planned content is:

1. Divide-and-Conquer: Mergesort, integer multiplication, matrix multiplication, Quicksort, selection in linear time, fast Fourier transform, polynomial multiplication
2. Dynamic programming: longest increasing subsequence, edit distance, optimal binary search trees, matrix chain multiplication, independent set on trees, all pairs shortest path (Floyd-Warshall)
3. Greedy algorithms: Huffman codes, minimum spanning trees (Prim, Kruskal), shortest path (Dijkstra, Bellman-Ford) 
4. Complexity theory: notion of NP-completeness, reductions between problems, examples of NP-hard problems: Traveling Salesman Problem, 3-SAT, Independent Set, Clique, Vertex Cover, 3-Coloring

Blackboard, slide projection, exercise sheets, Moodle platform for communication

• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, Third Edition, MIT Press 2009
• J. Erickson: Algorithms, online 2019

Prof. Berkholz