Hem  |  
Anpassa  |  
Översikt  |  
English  |  
Lunds universitet



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 2014
#WhenWhatWhere in [KT]Where in [E]
1Mon, Mar 17IntroductionChap. 1Chap. 0
2Tue, Mar 18GraphsChap. 3Chap. 17
3Mon, Mar 24Greedy algorithmsChap. 4.1–2, 11.1Chap. 7
4Tue, Mar 25Shortest paths and spanning treesChap. 4.4–6Chap. 18, 19
5Mon, Mar 31Divide and conquerChap. 5.1–4Chap. 1
6Tue, Apr 1Dynamic programmingChap. 6.1–7Chap. 5, 6
7Tue, Apr 8Network flowChap. 7.1–4Chap. 15–18
8Tue, May 6Computational complexityChap. 8.1–3Chap. 29
9Tue, May 13NP-hardnessChap. 8.4–10Chap. 29
10Tue, May 20Algorithms for hard problemsChap 10, 11

Frågor om innehållet: Peter Möller
Webbtekniska frågor: webmaster@lth.se
Senast uppdaterad: 2014-03-18