
The lectures cover roughly the first half of the course book by Kleinberg and Tardos [KT], which is required reading.
In some lectures, I will use Kevin Wayne’s slides for [KT], available at tinyurl.com/6aprfoy.
For those who want another presentation of roughly the same material, I suggest the corresponding passages in Jeff Erickson’s course notes [E], which are freely available online. These are entirely optional. This being said: make no mistake that [KT] is the course book.
I assume that you are already familiar with the basics of algorithms analysis covered in [KT] chapter 2, so I will not cover it. It’s a good chapter, so unless you are confident about this material, I suggest you read it on your own.
| # | When | What | Where in [KT] | Where in [E] |
|---|---|---|---|---|
| 1 | Tue, Mar 13 | Introduction | Chap. 1 | Chap. 0 |
| 2 | Fri, Mar 16 | Graphs | Chap. 3 | Chap. 17 |
| 3 | Tue, Mar 20 | Greedy algorithms | Chap. 4.1–2, 11.1 | Chap. 7 |
| 4 | Fri, Mar 23 | Shortest paths and spanning trees | Chap. 4.4–6 | Chap. 18, 19 |
| 5 | Tue, Mar 27 | Divide and conquer | Chap. 5.1–4 | Chap. 1 |
| 6 | Fri, Mar 30 | Dynamic programming | Chap. 6.1–7 | Chap. 5, 6 |
| 7 | Wed, Apr 18 | Network flow | Chap. 7.1–4 | Chap. 15–18 |
| 8 | Tue, Apr 24 | Computational complexity | Chap. 8.1–3 | Chap. 29 |
| 9 | Tue, May 8 | NP-hardness | Chap. 8.4–10 | Chap. 29 |
| 10 | Tue, May 15 | Algorithms for hard problems | Chap. 10.1, 11–12 (cursory) | Chap. 4, 30 |
Note that lecture 7 (Apr 18) is on a Wednesday, not on a Tuesday.
Intellectually, lectures 2–7 belong together, the big gap between lectures 6 and 7 is a shame. Similarly, I would like lectures 8 and 9 to be closer together.
The exam is 23 May 2012, 8–13.
Frågor om innehållet: Peter Möller
Webbtekniska frågor: webmaster@lth.se
Senast uppdaterad: 2012-03-06