Week 0
- Peter Alfeld’s Guide to Understanding Mathematics
- Course policies on academic integrity
- Sets, Functions and Relations (pages 1-12)
- Basic Proof Techniques (pages 13-15)
- Propositional Logic and Inference (pages 95-100)
Week 1
- Prologue for Algorithms (Chapter 0; 10 pages)
- Simple Arithmetic Algorithms (Sections 1.1-1.5; 13 pages)
- Fibonacci Numbers (Section 0.2; 4 pages)
Week 2
- Refresher: Basic Data Structures (lists, stacks, queues, binary trees and binary search trees)
- Analysis of Insertion Sort (4 pages)
- Big-O notation (Section 0.3; 2 pages)
- Proofs by Induction (Sections 1-6; 12 pages)
- Asymptotic Complexity (Slides 1-15; this slide set also includes useful formulae)
- Examples, courtesy Charles A. Cusack
Week 3
- Divide and Conquer (Chapter 2; 28 pages)
- This chapter contains a discussion of problems different from lectures.
- Focus on mastering the principle.
- FFTs are useful but you could skip that material initially.
- Solving recurrences
Week 4
- Greedy Algorithms (Chapter 5; 28 pages)
- Some examples may differ from those in lecture.
Week 5
- Dynamic Programming (Chapter 6; 22 pages)
- Some examples may differ from those in lecture.
Week 6
- Graphs (Chapter 3; 16 pages)
- Simple Proofs with Graphs
- Inductive Proofs on Trees (Section 11; 3 pages)
- More Proofs with Graphs (6 pages)
- Graphs and Matching Problems
Week 7
- Paths in Graphs (Chapter 4; 17 pages)
- Minimal Spanning Trees (Sections 18.1-18.3, 18.6; 6 pages)
Week 8
- Data Structures for Disjoint Sets (Sections 16.1-16.3; 5 pages)
- Red-Black Trees (or how to keep a tree height-balanced)
Week 9
- Universal Hashing (Section 1.5; 4 pages)
- Hashing (9 pages)
- Applications of Hashing (3 pages)
- (background) Introduction to Probability
- (background) Random Variables and Linearity of Expectation
Week 10
- Primality Testing (5 pages)
- Cryptographic Algorithms: RSA (6 pages)
Week 11
- An Introduction to Linear Programming (Section 7.1; 11 pages)
- Linear Programming (8 pages)
Week 12
- NP-completeness (Wikipedia entry)
- NP-complete Problems (Sections 8.1-8.2; 15 pages)
Week 13
- Approximation Algorithms