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. | (a,b)-trees: definition, bounds on height. Insertion and deletion based on vertex splits and merges. Left-leaning red-black (LLRB) trees: definition, isomorphism with (2,4)-trees, insertion. |
| 4. 5. | Representation of strings and numbers by tries. Hashing: buckets with chains, choice of hash function, dynamic reallocation of hash tables and its amortization. Universal families of hash functions, construction of a 1-universal system from scalar products. |
| 11. 5. | Hashing with open addressing: general technique, upper bound on expected time complexity (assuming perfectly random probe sequences), a note on linear probing and double hashing. Divide and conquer: Mergesort and its analysis. |
| 18. 5. | Divide and conquer: multiplication of n-digit numbers in O(nlog23) time (Karatsuba-Ofman algorithm). Master theorem on complexity of recursive algorithms. Strassen's algorithm for matrix multiplication (formulae). |
| 25. 5. | Selection of the k-th smallest element and different ways of choosing the pivot. Randomization and expected time complexity. Linear-time selection. QuickSort: basic principle, analysis of expected complexity. Lower bound on complexity of sorting in the comparison model. Remark on bucket sorting. |
Exams
Exam dates will be listed in SIS, please sign up there. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.
You are expected to know the theory presented at the lectures and to be able to use it for solving algorithmic problems, similar to those from the classes. The necessary (but generally not sufficient) condition of passing the exam is knowledge and understanding of all definitions and algorithms from the syllabus.
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