Lectures: Fridays 15:30 - 16:20 in GHC 5222
Instructors: Anil Ada (aada), Bernhard Haeupler (haeupler), Ryan O'Donnell (odonnell)
Office Hours: Fridays right after lecture in GHC 5222
Course description:
This 3-unit mini-course is intended for students who are taking 15-251 and would like more intensive exposure to theoretical computer science. The class meets once a week for a lecture and the students are expected to solve a number of homework problems during the course of the semester. The work done in 15-252 does not replace any of the requirements of 15-251.
Topics:
- (01/20): Sorting Pancakes (Notes)
- (01/27): Non-Deterministic Finite Automata
- (02/03): Even More Models of Computation
- (02/10): Kolmogorov Complexity
- (02/17): Structural Complexity
- (03/03): Fields and Polynomials (Notes)
- (03/24): Fast Fourier Transform
- (03/31): Random kSAT
- (04/07): Network Coding
- (04/14): Probabilistic Method
- (04/28): Error Correction: Reed-Solomon Codes
- (05/05): Quantum Computation and Shor's Factoring Algorithm
Assignments
General rules: You can work alone or with one other person (the recommended option is the latter). However you must write the solutions completely by yourself. You may not share any written documents. Solutions must be typeset using LaTeX.
Evaluation
Attendance and weekly assigned problems.