Theoretical Computer Science

Semestr: Winter

Range: 3+2s

Completion:

Credits: 6

Programme type: Undefined

Study form:

Course language:

Summary:

The course reinforces abstraction and proof techniques in discrete structures presenting basic notions and problems of graph theory. Standard graph algorithms (as e.g. breadth-first and depth-first graph traversal, shortest paths algorithms of Dijkstra, Bellman-Ford, Floyd-Warshall, and Johnson, shortest spanning tree algorithms of Kruskal-Boruvka and Prim-Jarnik, max-flow algorithm of Ford-Fulkerson, etc.) are introduced and their complexity discussed. The course includes greedy algorithms and dynamic programming technique, complexity theory (P and NP complexity classes, NP-completeness), search problems in artificial intelligence, mathematical models of programs and computations (finite automata, Turing machines).

Keywords:

discrete structures, graph algorithms, complexity analysis, complexity classes, finite automata, Turing machines

Course syllabus:

1. Theoretical models, undirected graphs, basic properties
2. Directed graphs, strong connectivity, topological sort
3. Graph representation, breadth-first and depth-first traversals
4. Euler's graphs, dominating and independent sets, distance
5. Trees and spanning trees, circuits, minimum spanning trees, binary trees
6. Algorithms of Borůvka and Jarník, Huffman's coding
7. Shortest paths algorithms, dynamic programming
8. Flow networks, maximum flow in network
9. General problem solving, state space, heuristic search
10. Models of programs, computers and calculations
11. Algorithms and universal machines, unsolvable problems
12. Function definition using recursion, fixpoint theory
13. Complexity of algorithms, P and NP complexity classes, NP-completeness
14. Reserved

Seminar syllabus:

1. Using basic tools of mathematics (proof, induction, recurrence)
2. Operational complexity of algorithms, calculations with recurrences
3. Undirected graphs - basic properties
4. Graph traversals, decomposition into components, homework
5. Directed graphs - basic properties, depth-first search
6. Decomposition into strong components, homework consultation
7. Dominance, independence, trees
8. Spanning trees, minimum spanning trees
9. Shortest paths
10. Homework consultation
11. Application of dynamic programming
12. Flows in networks, consultation to homework
13. Searching the state space, heuristic search
14. Assessment

Literature:

[1] Cormen, T.H. et al. : Introduction to Algorithms. MIT Press, Cambridge, Mass. 1990

Examiners:

Lecturers:

Instructors: