Lectures:
- Intro: about methods of algorithm design, analysis of algorithms, and computational complexity of algorithms and problems
- Divide-and-Conquer: description of the method, examples of problems and algorithms (see examples 12 below)
- Greedy method: description, examples
- Iterative improvement: descr., examples
- Dynamic programming: descr., examples
- Backtracking: description, examples
- Branch&Bound: description, examples
- Linear programming: descr., Simplex algorithm, examples
- Selected advanced data structures
- NP-hard computational problems: lower bounds on time complexity, informally about P, NP and NP-hard problems;
- Methods of solving NP-hard problems: heuristic algorithms, approximation algorithms, randomized algorithms, parameterized algorithms, exact exponential algorithms, examples
- Example problems and algorithms: advanced sorting & Heapsort, Quicksort; selection problem & linear algorithms; matrix multiplication & Strassen alg.; Discrete Fourier Transformation & FFT alg; string matching & Knuth-Morris-Pratt; elementary and other graph problems and algorithms (searching a graph; topological sort; maximum flow & Ford-Fulkerson alg.; shortest paths & algorithms of Bellman-Ford, and Floyd-Warshall); selected problems from computational geometry.
Tutorial: Students will use the topics given during the lectures to independently solve practical problems (with the assistance of the TAs if needed). They will implement several smaller programs (home works) as well as larger programs (seminars), and present them at the tutorial.
