The following topics are covered during the course:
- Introduction. What is an efficient algorithm?
- Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls.
- Solving recurrences;
- Data structures and algorithms. Review of basic data structures;
- Combining data structures. Merge-and-find;
- Graph algorithms;
- Greedy algorithms;
- Dynamic programming;
- Backtracking and Implicit search trees. Branch-and-bound;
- Short introduction to local search and approximation algorithms;
- Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. Coping with hard problems;
- Short introduction to other design techniques: local search, approximation algorithms, randomized algorithms, preprocessing, network flow.