Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks, Forum, Exam

Topics	Slides	Key Notes	Questions
Intro
Quantifiers
Loop Invariants
Recursion
Network Flow
Linear Programming
Randomized Algorithms
Algebra
FFT
Common Knowledge
Greedy Algorithms
Dynamic Programming
Approximation Algorithms
NP-completeness
Computability
Other Stuff

Quantifiers: (Steps, ppt, Questions)

Existential and Universal quantifiers
Fun

Loop Invariants: (1.5 classes) (Steps, ppt, Questions)

Proof of Correctness
More of Input vs Output
Two Graph Path Problems (pdf)
Lower Bounds (pdf)
Amortized Analysis (Create-Delete, Trits)
Maximal Rectangles ppt

Recursion: (4 classes) (Steps, ppt, pdf, Questions)

Friends
Derivatives of Functions
Recursive multiplication
Recursive Pictures
Multiply two integers by cutting into d pieces (assignment)
Parsing (pdf, Java)
Ackermann's Function
Fast Fourier Transformations

Network Flow: (2 classes) (ppt, Questions)

The Primal-Dual Hill Climbing Method
The Steepest Ascent Hill Climbing Algorithm (pdf)
Bipartite Matching

Linear Programming: (ppt)

What to put in a hotdog
Primal Dual

Randomized Algorithms: (3 class) (pdf, Rudich1.ppt, Rudich2.ppt, Questions)

Random variables, random walks, Chernoff bounds.
Las Vegas & Monte Carlo Algorithms, primes.
Max Cut, Expander Graphs.
Choose a new door & Driver's Licenses in Lockers (board)
Gambling Dice html
Yao's Min-Max (board)
Entropy

Algebra: (3 class) (ppt, Questions)

Fields
      GCD
      Powers mod p
      Fermat Little Theorem, Roots of Unity, & Generators
      Z mod p vs Complex Numbers
      Cryptography (Josh's, Rudich.ppt)
      Other Finite Fields
Vector Spaces
      Colour
      Error Correcting Codes
Linear Transformations
      Integrating
Changing Basis
      Fourier Transformations (sine)
      Fourier Transformations (JPEG)
      Fourier Transformations (Polynomials)
Other Algebra
      Taylor Expansion
      Counting with Generating Functions
      Primes Numbers

More Recursion - Fast Fourier Transformations: (3 class) (ppt, Questions)

Change from Time to Polynomial Basis
Evaluating & Interpolating
FFT in nlogn Time
Roots of Unity
Same FFT Code & Butterfly!
Inverse FFT
Polynomial Multiplication
Integer Multiplication

Distributed Systems: mud on forehead & common knowledge: (1 class) (ppt, Questions)

Knowing Mud Problem
Boys Learn Common Knowledge
Formal Definition of "Knowing"
Applying Formal Definition to Mud Problem

Greedy Algorithms: (2 classes) (Steps, ppt Questions)

Interval Point Cover
Lower Bounds ppt

Dynamic Programming: (2 classes) (ppt, Questions)

Skip most of slides & start with Knapsack
Could do Event Scheduling Problem, Parsing, & Satisfiability if desired.
Bird-Friend Method & Shortest Path Method (pdf)
Pebbles (pdf)

Approximation Algorithms: (1 class) (ppt)

Knapsack
Clique
Max Cut

NP-completeness:: (ppt, pdf,Questions)

History
Course vs Schedule
Circuit vs Airplane
Circuit vs 3-Colouring
Non-Deterministic Poly-Time
Reductions
K-Clique vs K-Independent Set
12 Steps
Any P <= Sat
3-Col <= 3-Sat
Sat <= 3-Col
More Problems
12 Steps in More Depth
Making Change scan
Embedding points with distortion pdf

Computability: (3 classes) (ppt, Questions, ppt)

Diagonalization & Uncomputability
Halting Problem
Time Hierarchy
Godel's Incompleteness Theorem

Other Stuff:

Intro to Quantum: Shor's factoring (1 class) (stuff)
Concurrency Theory:
Structural Complexity: polytime hierarchy, P-space, Exp-time
Data Structures: dynamic perfect hashing
Rudich's course

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.