Feb 20: Course introduction: course organization and
policies; Example of the Fibonacci sequence: a bad algorithm and a
good algorithm; implementation-independent behaviors and
algorithmic complexity.
TBD: Representing numbers: space complexity. Adding
and multiplying numbers. The simple algorithms and their
analysis. Initial idea for a better multiplication algorithm. (OPTIONAL)
Mar 1: Basic elements for the analysis of algorithms:
complexity and correctness of insertion-sort; worst-, best-, and
average-case complexity; loop invariants.
May 22: Basic elements of complexity theory: polynomial-time
algorithms and problems; the P complexity class; the NP class;
polynomial-time reduction and NP-completeness; satisfiability.