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. It will be similar to my previous year's ADS1 course.
The lectures are held on every Wednesday from 15:40 in room S5.
Classes (exercises) are on Wednesdays from 14:00 in room S11. They are taught by Radek Hušek. Czech-speaking students can also select any classes of the Czech version of the course, we will try to keep both versions of the course synchronized.
Syllabus
date | topic |
---|---|
21. 2. | Introductory examples: finding the longest increasing subsequences in different ways. An attempt at defining an algorithm. |
28. 2. | The Random Access Machine as a model of computation. Execution time and space, possible choices of instruction cost (unit cost, limited arguments, logarithmic and 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, Ω, Θ. |
7. 3. | Graph algorithms: Breadth-first search (BFS) and its properties. Representation of graphs (matrices vs. lists) and its effect on time complexity. Applications of BFS: connected components, shortest paths. |
14. 3. | Graph algorithms: Depth-first search (BFS) and its properties. The DFS tree and classification of edges (tree, back, forward, cross). Identifying bridges in undirected graphs. DFS on directed graphs: detection of cycles. Topological order and its existence. |
21. 3. | Plan: Topological order using DFS, induction based on it. Strongly connected components. 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). |
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