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 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

Comments

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.

• Utskriftsversion