Topics in Theoretical Computer Science
| Credits | 4 | |
| Lecturer | Ola Svensson | |
| Office hours | Wednesdays 16-18 in INJ 112 | |
| Schedule | Tuesdays 14:00-18:00 in GCD 0386 |
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.
Assignments
- First assignment available here. Deadline 14:00 Tuesday, March 11.
- Second assignment available here. Deadline 14:00 Tuesday, April 1.
- Third assignment available here. Deadline 14:00 Thursday, April 17.
- Fourth assignment available here. Deadline 17:00 Friday, May 16.
(Preliminary) Schedule and references
| The probabilistic method | Tuesday | 14-18 | February 18 | GCD 0386 | Reference book: "The probabilistic method" by N. Alon and J. H. Spencer. Scribes of Lecture 1 |
| Lovasz Local Lemma | Tuesday | 14-18 | February 25 | GCD 0386 | Reference book: "The probabilistic method" by N. Alon and J. H. Spencer. Scribes of Lecture 2 |
| Expanders | Tuesday | 14-18 | March 4 | GCD 0386 | Good reference here. Scribes of Lecture 3 |
| Expanders | Tuesday | 14-18 | March 11 | DIA 003 | Good reference here. Scribes of Lecture 4 |
| PCP Theorem | Tuesday | 14-18 | March 18 | DIA 003 | Scribes of Lecture 5 |
| PCP Theorem | Tuesday | 14-18 | March 25 | DIA 003 | Scribes of Lecture 6 |
| Hardness of Approximation | Tuesday | 14-18 | April 1 | DIA 003 | Scribes of Lecture 7 |
| Approximation Algorithms and Linear Programming | Tuesday | 14-18 | April 8 | DIA 003 | Scribes of Lecture 8 |
| Linear Programming (extreme points) | Tuesday | 14-18 | April 15 | DIA 003 | Scribes of Lecture 9 |
| Linear Programming (duality) | Tuesday | 14-18 | April 29 | GCD 0386 | Scribes of Lecture 10 |
| Semidefinite Programming | Tuesday | 14-18 | May 6 | DIA 003 | Scribes of Lecture 11 |
| Submodular functions | Tuesday | 14-18 | May 13 | DIA 003 | Scribes of Lecture 12 |
| Submodular functions | Tuesday | 14-18 | May 20 | GCD 0386 | Scribes of Lecture 13 |
| Final exam | Tuesday | 14-18 | May 27 | DIA 003 |
Grading
The grade will be based on problem sets [40%], scribe notes [20%], and final exam [40%].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;