**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.** **

- nosilec: Borut Robič