Algorithms and Data Structures I
In the summer semester 2016/2017, I teach the English version of the basic course on Algorithms and Data Structures I [NTIN060]. It is primarily intended for students of the English study programs, but everybody is welcome.
The lectures are held on every Thursday from 9:00 in room S3.
Classes (exercises) are on Tuesdays from 15:40 in room S11. They are taught by Petr Kučera. Czech-speaking students can also select any classes of the Czech version of the course, but they are likely to be differences in the order of topics taught.
Syllabus
datum | téma |
---|---|
23. 2. | Introductory examples: finding the longest increasing subsequences in different ways. An attempt at defining an algorithm. |
2. 3. | The Random Access Machine as a model of computation. Execution time and space, possible choices of instruction cost (unit cost, logarithmic cost, limited arguments, relative logarithmic cost). Time and space complexity of an algorithm. Programming on RAM and estimating complexity: an example with sorting by selection. Asymptotic notation: O. |
9. 3. | More asymptotic notation: Ω, Θ. Graph algorithms: examples of reduction to graph problems, breadth-first search (BFS). |
16. 3. | Graph algorithms: Connected compoments, relation of BFS to shortest paths, representation of graphs and its effect on the time complexity of BFS. Depth-first search (DFS). The DFS tree and classification of edges (tree, back, forward, cross). Identifying bridges. |
23. 3. | DFS on directed graphs: detection of cycles, topological order and induction based on it. Strongly connected components. |
30. 3. | Plan: Shortest paths in graphs with variable edge lengths: triangle inequality for distance, problems with negative cycles, shortest path versus shortest walk. Dijkstra's algorithm and its derivation from BFS with subdivided edges. Implementation with heaps (binary and k-regular). Relaxation principle and proof of Dijkstra's algorithm in general case. |
Recommended reading
- Dasgupta, Papadimitriou, Vazirani: Algorithms (a beautiful books on algorithms covering the most of our lecture, available online)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd or later edition), Mc Graw Hill 2001
- Matoušek, Nešetřil: Invitation to Discrete Mathematics, Oxford University Press. (background in combinatorics and graph theory)
- An applet demonstrating search trees
- Robert Sedgewick: Left-Leaning Red-Black Trees
- Other materials in Czech language