
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 19 | Introduction | Chap. 1 | Chap. 0 |
| 2 | Wed, Mar 20 | Graphs | Chap. 3 | Chap. 17 |
| 3 | Tue, Apr 9 | Greedy algorithms | Chap. 4.1–2, 11.1 | Chap. 7 |
| 4 | Thu, Apr 11 | Shortest paths and spanning trees | Chap. 4.4–6 | Chap. 18, 19 |
| 5 | Tue, Apr 16 | Divide and conquer | Chap. 5.1–4 | Chap. 1 |
| 6 | Thu, Apr 18 | Dynamic programming | Chap. 6.1–7 | Chap. 5, 6 |
| 7 | Tue, Apr 23 | Network flow | Chap. 7.1–4 | Chap. 15–18 |
| 8 | Tue, May 7 | Computational complexity | Chap. 8.1–3 | Chap. 29 |
| 9 | Tue, May 14 | NP-hardness | Chap. 8.4–10 | Chap. 29 |
| 10 | Tue, May 21 | Algorithms for hard problems | Chap. 10.1, 11–12 (cursory) | Chap. 4, 30 |
Frågor om innehållet: Peter Möller
Webbtekniska frågor: webmaster@lth.se
Senast uppdaterad: 2013-03-20