Main resource materials: These are given by links provided through the course calendar. This includes:

• 14 links to daily lectures, in a uniform lectures file.
• 7 links to the 7 weekly assignments.
• 6 links to the 6 weekly recitations.
• Solutions to Rec 4 and Rec 6: Solutions (PDF)

• Definition of algorithm.
• Three examples: gcd, binary search, Traveling Salesman.
• Data structures for algorithms.
• Algorithm efficiency: time usually, sometimes space.
  Worst case usually, sometimes average case.
  Using Big-Theta notation usually, sometimes Big-Oh and Big-Omega.
• Efficiency of an algorithm versus efficiency of a problem.
• Three examples: MaxElement, UniqueElements, MatrixMultiplication.
• Tower of Hanoi example and proof by induction.
• Fibonacci numbers, and exact formula.
• Three algorithms for Fibonacci numbers: exponential, linear, logarithmic.
• Brute force algorithms.
• Divide and Conquer: Finding Max and Min simultaneously.
• Recurrence equations and proving them by induction.
• Divide and Conquer: quicksort.
• Randomized quicksort.
• Big-Theta(n) algorithm to randomize n elements in an array.
• Divide and Conquer: Strassen's matrix multiplication algorithm.
• Master Theorem for solving recurrences.
• Searching lists, including esp. binary search trees, hashing (including deletions), and Fibonacci search.
• Correctness proofs and loop invariants: simple exponentiation, complex exponentiation, three examples in an assignment.
• Heaps, heapsort, priority queues.
• Dynamic programming: memoization to compute Fibonacci numbers, Matrix-chain multiplication.

• If I ask you to derive the solution to a recurrence using the Master Theorem, then I will state this theorem for you (so you don't need to memorize it).
• There will be a mix of easier and harder problems.

• A proof by induction (perhaps as part of another question).
• Use Master Theorem to derive solution to a recurrence.
• Start with a small specific array, and use one of the algorithms involving heaps, heapsort, or priority queue on it.
• Prove correctness of an algorithm (may be given the loop invariant).
• Some question related to Strassen's matrix multiplication.
• Some question related to quicksort or randomized quicksort.
• Question related to dynamic programming: either memoization or matrix chain multiplication.
• Question about hashing.
• Possible questions about material covered during the recitation sessions.