Theoretical Computer Science  Modultafeln of TU Ilmenau
The module lists provide information on the degree programmes offered by the TU Ilmenau.
Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).
You can find all details on planned lectures and classes in the electronic university catalogue.
Information and guidance on the maintenance of module descriptions by the module officers are provided at Module maintenance.
Please send information on missing or incorrect module descriptions directly to modulkatalog@tuilmenau.de.
module properties module number 100089  common information  

module number  100089 
department  Department of Computer Science and Automation 
ID of group  2242 (Complexity Theory and Efficient Algorithms) 
module leader  Prof. Dr. Martin Dietzfelbinger 
language  Englisch 
term  Wintersemester 
previous knowledge and experience  Basic Data Structures, Calculus, Discrete Structures 
learning outcome  *** This course has ben replaced by "ALGORITHMS" (number 101720) *** Fachkompetenz: The students know the basic principles of the design and the analysis of algorithms: correctness and running time. They know the o notation and their 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 scheme. The students know the divideandconquer 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 “dary 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, allpairs shortest paths (FloydWarshall), singlesource shortest paths with edge lengths (BellmanFord), knapsack problems and matrix chain multiplication. They know the basic definitions and facts from NPcompleteness theory, in particular the implications one gets (if P <> NP) from the fact that a search problem is NPcomplete as well as central examples of NPcomplete problems. 
content  Fibonacci numbers and their algorithms, BigO notation, multiplication, division, modular addition and multiplication, fast exponentiation, 8extended) Euclidean algorithm, primality testing by Fermat’s test (with proof) and by MillerRabin (without proof), generating primes, cryptography and the RSA system (with correctness proof and runtime analysis). The divideandconquer scheme, Karatsuba multiplication, the master theorem (with proof), Mergesort, Quicksort, polynomial multiplication and Fast Fourier Transform. Graph representation. Exploring graphs and digraphs by BFS and (detailed) DFS. Acyclicity test (with proof), topological ordering. Strongly connected components by Kosaraju’s algorithm (with proof). Shortest paths by Dijkstra’s algorithm (with proof), priority queues as auxiliary data structure. The greedy paradigm. Minimum spanning trees by Kruskal’s algorithm (with unionfind data structure) and the Prim/Jarnik algorithm (with correctness proof). Huffman encoding, with priority queue, correctness proof. The dynamic programming paradigm. Examples: edit distance, chain matrix multiplication, knapsack with and without repetition, shortest paths (FloydWarshall and BellmanFord). Polynomial search problems, class NP, NPcomplete problems. Significance of the notion. Central examples: Satisfiability, Clique, vertex cover, traveling salesperson, graph coloring. 
media of instruction and technical requirements for education and examination in case of online participation  Blackboard, slide projection, exercise sheets, Moodle platform for communication. 
literature / references  * S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, McGraw Hill, 2006 (Prime textbook) * T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press 2001. * Sedgewick, Algorithms, Addison Wesley. (Any edition will do, with or without specific programming language.) 
evaluation of teaching  Pflichtevaluation: WS 2015/16 (Fach)
WS 2010/11 (Vorlesung) WS 2011/12 (Vorlesung, Übung) WS 2012/13 (Vorlesung) WS 2013/2014 (Vorlesung, Übung) WS 2014/15 (Vorlesung, Übung)

Details reference subject  

module name  Theoretical Computer Science 
examination number  2200315 
credit points  5 
SWS  3 
oncampus program (h)  33.75 
selfstudy (h)  116.25 
obligation  obligatory module 
exam  written examination performance, 90 minutes 
details of the certificate  
alternative examination performance due to COVID19 regulations incl. technical requirements  
signup details for alternative examinations  
maximum number of participants 
Details in degree program Master Research in Computer & Systems Engineering 2012  

module name  Theoretical Computer Science 
examination number  2200315 
credit points  5 
oncampus program (h)  34 
selfstudy (h)  116 
obligation  obligatory module 
exam  written examination performance, 90 minutes 
details of the certificate  
alternative examination performance due to COVID19 regulations incl. technical requirements  
signup details for alternative examinations  
maximum number of participants 