Syllabus
Optional topics in square brackets, the rest is mandatory.
1. Means for describing the complexity of algorithms and operations with data structures - measurement of data size, number of algorithm steps as a function of data size - RAM computational model - asymptotic notation
2. Tree data structures - binary search trees - AVL trees - (a,b)-trees - [red-black trees]
3. Hashing - a description of simple collision resolution strategies - analysis of the average time complexity of the search - universal hashing
4. Sorting - average case analysis for Quicksort, Randomized Quicksort - lower bound on the complexity of comparison sorting algorithms (decision trees)
5. Basic graph algorithms - depth-first search on an undirected graph, detection of bridges and articulations - depth-first search on a directed graph, transitive closure, topological numbering - [detection of components of strong connectivity in linear time]
6. Extreme paths in graphs - extreme paths in a directed acyclic graph, the critical path method - Dijkstra's algorithm (refresher of binary heaps, comparison of implementation using an array and a binary heap) - Bellman-Ford's algorithm (looking for negative cycles) - [Floyd-Warshall's algorithm]
7. Minimum spanning tree - Jarník's and Borůvka's algorithm - [Kruskal's algorithm and data structure for Union-Find]
8. Divide and conquer method - general schema of divide and conquer algorithms, describing their complexity by recurrent equations - substitution method for recurrent equations and "master theorem (cook-book)" - simple applications: binary search, Merge sort, multiplication of numbers (Karatsuba-Ofman) - more complex applications: Strassen's multiplication of matrices, [median search in linear time in the worst case]
9. Dynamic programming - general principle of dynamic programming - edit-distance of strings - [optimal search trees]
Annotation
Introductory lecture on the basic types of algorithms and data structures necessary for their implementation. It follows the lecture NPRG062 Algorithmization in the previous semester.