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
date | topic |
---|---|
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. | 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. Bellman-Ford algorithm. |
6. 4. | Minimum spanning trees: Jarník's (a.k.a. Prim's) and Borůvka's algorithm. Proofs via cut lemma. MST is unique and determined by order of edges. Kruskal's algorithm, maintenance of connected components and the Union-Find problem. |
13. 4. | Interfaces of common data structures: array, queue, stack, set, dictionary. Binary search trees and operations on them. Perfectly balanced trees and lower bound on their complexity. |
20. 4. | Height-balanced (AVL) trees: definition, proof of logarithmic height. Balancing AVL trees using rotations. |
27. 4. | Plan: (a,b)-trees: definition, bounds on height. Insertion and deletion based on vertex splits and merges, top-down insertion. Left-leaning red-black (LLRB) trees: definition, isomorphism with (2,4)-trees, insertion. |
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