Lectures

Lectures

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.

 

Lecture schedule 2012

#	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

• Utskriftsversion