Topics in Theoretical Computer Science
| Credits | 4 | |
| Lecturer | Ola Svensson | |
| Office hours | Wednesdays 16-18 in INJ 112 | |
| Schedule | Mondays 9:00-13:00 in CM 011 |
Short description
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced algorithmic techniques, and develop an understanding of fundamental questions that underlie some of the key problems of modern computer science.
For last year's course, please see here.Assignments
- First assignment available here. Deadline 09:15 Monday, March 16.
- Second assignment available here. Deadline 09:15 Monday, March 30.
- Third assignment available here. Deadline 12:00 AM Tuesday, April 21.
- Fourth assignment available here. Deadline 12:00 AM Friday, May 8.
(Preliminary) Schedule and references
| The probabilistic method | Monday | 9-13 | February 16 | CM 011 | Reference book: "The probabilistic method" by N. Alon and J. H. Spencer.Scribes of Lecture 1 |
| Lovasz Local Lemma | Monday | 9-13 | February 23 | CM 011 | Reference book: "The probabilistic method" by N. Alon and J. H. Spencer. Scribes of Lecture 2 |
| Expanders | Monday | 9-13 | March 2 | CM 011 | Good reference here. Scribes of Lecture 3 |
| Bipartite Matchings, intro to LPs | Monday | 9-13 | March 9 | CM 011 | Good reference here.Scribes of Lecture 4 |
| LP duality, Bipartite Matchings, Spanning trees | Monday | 9-13 | March 16 | CM 011 | Good reference: "Understanding and using Linear Programming". Scribes of Lecture 5 |
| Matroids and Matroid Polytope | Monday | 9-13 | March 23 | CM 011 | Good reference here.Scribes of Lecture 6 |
| Matroid Intersection | Monday | 9-13 | March 16 | CM 011 | Good references here, Lectures 10-13 here, and here. Scribes of Lecture 7 |
| Matroid Intersection Polytope | Monday | 9-13 | April 13 | CM 011 | Good reference here.Scribes of Lecture 8 Comment: guest lecture by Hyung-Chan An |
| Perfect Matchings in General Graphs | Monday | 9-13 | April 20 | CM 011 | Good reference here. Slides of Jakub's presentation: here |
| Ellipsoid method | Monday | 9-13 | April 27 | CM 011 | Good references: here and here.Scribes of Lecture 10 |
| Multiplicative weight update, simplex | Monday | 9-13 | May 4 | CM 011 | Good references: "Understanding and using Linear Programming" and here.Scribes of Lecture 11 |
| Lower bounds on Extended Formulations | Monday | 9-13 | May 11 | CM 011 | Scribes of Lecture 12 |
| Final Exam and Project Presentations | Monday | 9-13 | May 18 | CM 011 | Good luck! |
Grading
The grade will be based on problem sets [50%], scribe notes [15%], and final exam [35%] (that can be replaced by a project).Scribe notes:
For each lecture, there will be one team (of one or two students) in charge of taking detailed notes, typing them in LaTeX, preparing any needed figures, and sending them to the lecturer within at most 72 hours after the lecture. These notes will be posted on the course website. LaTeX is a typesetting language in which most (if not all) scientific literature is
written. So, if you are not familiar with it yet, it is probably a good time to do it now.
To start, take a look at www.latex-project.org and play with our template. (Make sure you have a distribution installed and don't forget to put the preamble.tex and fullpage.sty files in the same directory as the template.)
When preparing scribe notes, please use this template -- just edit it to include your notes. (The template requires preamble.tex and fullpage.sty files to compile. Put them in the same directory.)
Here are some guidelines regarding the style of the notes.
To start, take a look at www.latex-project.org and play with our template. (Make sure you have a distribution installed and don't forget to put the preamble.tex and fullpage.sty files in the same directory as the template.)
The target audience of these notes is you -- students -- a couple of weeks after the lecture, when you already have forgotten what it was about. Therefore, while scribing the notes, you should strive to present, in succinct, readable, and technically correct (but not too formal) way, all the important points and results of the lecture.
A couple of more concrete suggestions:
- Start by briefly summarizing the main topics discussed in the lecture;
- Try to use full sentences/prose - avoid bullet points;
- (Very important) Make sure to also include the motivation, illustrative examples and intuitions related to the presented concepts/algorithms/proofs -- either the ones presented in the lecture or (even better!) the ones you came up on your own;
- If there is a simple figure that you feel would be helpful in understanding something, try to include it too;
- Make sure that all the formal arguments are correct and do not have any gaps in reasoning - if something in the argument is unclear to you, just email the lecturer for clarification.
- Polish the language and spell check your notes before sending them to the lecturer;