Feb 21: 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)
Feb 28: Basic elements for the analysis of algorithms:
complexity and correctness of insertion-sort; worst-, best-, and
average-case complexity; loop invariants.
TBD: Review of BST deletion. Red-black trees: deletion.
Exercises. (OPTIONAL)
Book ref.: CLRS 13.4.
TBD: Exercises from past exams.
Apr 13: B-Trees. Data structures in secondary storage:
modeling disk access. Structure, search, and insertion in
B-trees. Relation with red-black trees.
May 18: Basic elements of complexity theory: polynomial-time
algorithms and problems; the P complexity class; the NP class;
polynomial-time reduction and NP-completeness; satisfiability.