Predavanja:
- 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.
- nosilec: Borut Robič