15-859T: A Theorist's Toolkit 2013
Prerequisites Students should have a solid undergraduate background in math (e.g., elementary combinatorics, graph theory, discrete probability, basic algebra/calculus) and theoretical computer science (running time analysis, big-O/Omega/Theta, P and NP, basic fundamental algorithms). Mathematical maturity is a must. Suggested text The Nature of Computation by Cris Moore and Stephan Mertens.
Meetings time and place: Monday and Wednesday, 3pm-4:20pm, GHC 5222. Instructor: Ryan O'Donnell TA: Ameya Velingker Office Hours: Ryan, GHC 7213, by appointment; Ameya, Thursdays 4--5pm in GHC 6211 Course bulletin board: Piazza Scribe notes (Scribes will be de-anonymized at the end of the semester.) Lecture 01 -- Asymptotics (Misha Lavrov scribe notes, lecture draft) Lecture 02 -- Central Limit Theorem (Yu Zhao scribe notes, lecture draft) Lecture 03 -- Chernoff bounds (Elara Willett scribe notes, lecture draft) Lecture 04 -- How to do math (slides .pdf, slides .pps) Lecture 05 --…
saved by
related reading
- 15-855: Graduate Computational Complexity Theory, Fall 2017cs.cmu.edu
- Theory at Berkeleytheory.cs.berkeley.edu
- Computational Complexityblog.computationalcomplexity.org
- CSE 599 Recent Developments in Approximation Algorithmshomes.cs.washington.edu
- Teach Yourself Computer Scienceteachyourselfcs.com
- Tim Roughgarden's Lecture Notestimroughgarden.org
- What every computer science major should knowmatt.might.net
- gtacbook.pdfyufeizhao.com
- Tim Kunisky - Homekunisky.com
- Evan Chen • Mathematics Coursework and Lecture Notesweb.evanchen.cc
- MathofSNLnotes2025.pdfpeople.math.ethz.ch
- Napkin.pdfvenhance.github.io