".. People who analyze algorithms have double happiness. First of all they experience the beauty of elegant mathematical patterns that surround elegant computation procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and economically" D. E. Knuth
This course is intended to overview primary techniques that are used in the mathematical analysis of algorithms. Sample analyses will include algorithms for data structures, graphs and communication networks.
Various performance measures and the types of problems for which they are applied will be discussed, in particular, worst case, amortized, competitive and probabilistic analysis of algorithms. As time permits, we will discuss algorithmic game theory and analysis of fixed parameter algorithms.
Grading Policy
- Assignments: There will be around 5 MAGEN assignments with total weight 25%
- Project: 30% - 35% MAGEN.
- Final Exam: 40% - 100% according to the MAGEN