Topics
This course is intended as an introductory course concerning the design and analysis of (discrete) algorithms. A study of algorithms requires a foundation in discrete mathematics. We will cover elements of discrete mathematics rapidly and then spend more time understanding how to design and analyze algorithms.
The central discussion in the course will revolve around
- algorithmic techniques such as divide-and-conquer, dynamic programming and greedy algorithms;
- methods of proof to establish correctness of algorithms;
- asymptotic runtime complexity analysis of algorithms;
- graphs and graph algorithms;
- hardness of computation.
Towards the end of the course, we will discuss intractability and undecidability in the context of algorithms.
The basics of discrete mathematics that would be needed to follow the discussion closely include:
- Propositional and Predicate Logic;
- Methods of Proof;
- Sets, Relations and Functions;
- Counting.