Theoretical Computer Science

Lecturer:

Neurčen (gar.), Josef Kolář, Daniel Průša, Karel Zimmermann

Tutor:

Neurčen (gar.), Andrej Chu, Josef Kolář, Daniel Průša, Karel Zimmermann

Supervisor:

Department of Computer Science and Engineering

Synopsis:

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).

Requirements:

Final exam grading is in part derived from the quality of presented homeworkand activity at seminars.

Syllabus of lectures:

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 Boruvka 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. Regular languages and finite automata

11. Turing machines - structure and behavior

12. Generalized Turing machines, undecidable problems

13. Complexity classes P and NP, NP-completeness

14. Reserved

Syllabus of tutorials:

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. Application of dynamic programming

11. Maximal flow in network, heuristic search algorithms

12. Regular languages and finite automata

13. Non-determinism, homework consultation

14. Assessment

Study Objective:

Study materials:

1. Kolář, J.: Theoretical Computer Science. Prague: CTU Publishing House.

1998

2. Cormen, T.H. et al. : Introduction to Algorithms. Cambridge, Mass.: MIT

Press. 1990

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri
Thu
Fri	roomKN:E-107 Průša D. 12:45–14:15 (lecture parallel1) Karlovo nám. Zengerova posluchárna K1

The course is a part of the following study plans:

• Softwarové inženýrství (compulsory elective course)
• Web a multimedia (compulsory elective course)