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||Mon, Mar 17||Introduction||Chap. 1||Chap. 0|
|2||Tue, Mar 18||Graphs||Chap. 3||Chap. 17|
|3||Mon, Mar 24||Greedy algorithms||Chap. 4.1–2, 11.1||Chap. 7|
|4||Tue, Mar 25||Shortest paths and spanning trees||Chap. 4.4–6||Chap. 18, 19|
|5||Mon, Mar 31||Divide and conquer||Chap. 5.1–4||Chap. 1|
|6||Tue, Apr 1||Dynamic programming||Chap. 6.1–7||Chap. 5, 6|
|7||Tue, Apr 8||Network flow||Chap. 7.1–4||Chap. 15–18|
|8||Tue, May 6||Computational complexity||Chap. 8.1–3||Chap. 29|
|9||Tue, May 13||NP-hardness||Chap. 8.4–10||Chap. 29|
|10||Tue, May 20||Algorithms for hard problems||Chap 10, 11|
Last updated: 2014-03-18