Lectures: Fridays 15:30 - 16:20 in GHC 4211
Instructor: Anil Ada (aada)
Office Hours: Fridays right after lecture in GHC 6215
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:
- (09/01): Sorting Pancakes [Slides] [Notes]
- (09/08): Non-Deterministic Finite Automata
- (09/15): Integer and Matrix Multiplication [Slides]
- (09/22): Gödel's Incompleteness Theorems [Slides]
- (09/29): Rent Division [Slides]
- (10/06): Polynomials and Error-Correcting Codes [Notes]
- (10/13): Structural Complexity
- (10/20): No class. Mid-semester break.
- (10/27): Communication Complexity [Slides]
- (11/03): Online Algorithms [Slides]
- (11/10): No class. 50th Anniversary Celebration of the merger of CIT and Mellon Institute.
- (11/17): Probabilistic Method
- (11/24): No class. Thanksgiving.
- (12/01): Learning Theory [Slides]
- (12/08): TBD
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.