Lectures: Fridays 15:30 - 16:20 in GHC 5222
Instructors: Anil Ada (aada), Klaus Sutner (sutner)
TA: Zhen Zhou (zzhou1)
TA Office Hours: Thursdays 2-2:30pm, Fridays 1-1:30pm, at Gates 5th floor teaching commons
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/19): Sorting Pancakes [Slides]
- (01/26): Non-Deterministic Finite Automata
- (02/02): State Explosion [Slides]
- (02/09-16): Kolomogorov-Chaitin Complexity [Slides]
10000 digits of pi pitiny.c a universality "proof" of the
(2,3) TM TM23
- (02/23): Finite Fields [Notes]
- (03/02): Error-correcting Codes [Notes]
- (03/23): Communication Complexity [Slides]
- (03/30): A Visit to a Subset of the Complexity Zoo
- (04/06): More Randomness [Slides]
- (04/13): The Probabilistic Method
- (04/27): Markov Chains [Slides]
- (05/04): Flipping Pebbles [Slides]
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.