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: firstname.lastname@example.org
Senast uppdaterad: 2013-03-20