TDA250/INN 280, LP 2 2008: Algorithms (Advanced Course)

Lecturer

Devdatt Dubhashi , EDIT 6479 name(at)cs.chalmers.se

Assistant

Leonid Molokov , EDIT 6479 name(at)cs.chalmers.se

Student Reps

Karin Keijzer (karin.keijzer@gmail.com)
Robert Luciani (r3tex@dtek.chalmers.se)

Announcements

Oral exams in our offices.
Exam up! (see below) Bring your exam solutions to class on Friday where you also get an opportunity to hear about the local p2p company Contribio from its CEO.
Exam will be posted here tomorrow at 10 AM.
Inportant! As some of you noticed, I goofed up with the date of the exam - wrote 11th instead of 10th as agreed. Now, in order to be fair to students who planned according to what I wrote, the exam will be released Dec. 11 10 AM, due 24 hrs later in my office. Correspondingly, oral exams will be on the 12th and 15th.
Sign up sheets, up.
Sign up sheets will be up on my and Leonid's doors, hopefully later today.
About the Oral Exam: you'll be asked questions around the problems you answerr on the written exam to test your understanding. For example, if there was a problem on NP-completeness, you may be asked some general questions about what it means, what is a reduction etc. Or if a question is about approximation algorithms, what does an approximation algorithm mean, what are some common techniques, how are they used etc?
On Dec. 12, we will have a 45 min talk from the CEO of Contribio which uses p2p algorithm technologies and is looking for ex-jobbare.
Exercise session on Dec. 9 will be a review of previous exercises and questions people have asked.
Added topic "Network Flows" this year from Chapter 7, will only consider just the simplest concepts and applications for the Exam, 7.1, 7.2, 7.6.
Take Home Exam out Dec. 10 10 Am, due 24 hrs later, folowed by 15 minute oral exam for which you can sign up for slots which will be put up that week
Welcome!

Course Description

The course is part of the D Specialization in algorithms. It will be given in English.The goal of the course is to develop advanced techniques in the design and analysis of algorithms. The course will continue in the spirit of the first algorithms course and maintain a rigorous analytical style. It is assumed that you are taking this course because you like the subject and you want to gain a deeper understanding of algorithms, not for a practical guide on how to implement them. Taking this course is also intended to prepare you for further research in the area. A more detailed outline of the topics to be covered can be seen in the tentative schedule of lectures below. Many of the topics are the result of recent research in algorithms: if the first course was about algorithms of the 1970's and 80's, this one is about algorithms of the 1990's and the new millennium! At some points in the course, we will also touch on frontiers of current research.

Prerequisites

You must have done the basic course in Algorithms (or equivalent) and have a good background in discrete mathematics. You should be comfortable with a rigorous style of presentation

Evaluation

Will be based on one final exam.

Time and Place

Schema in TimeEdit .

Lectures, Wed and Friday 10 - 11:45
Exercise sessions: Tuesday 1315 - 1400

Topics

Lectures are planned as follows (estimated number of lectures in parenthesis as well as the relevant chapters in the textbook which is referrred to as [KT] below)

NP-completeness [3, KT Chap. 8]
Approximation Algorithms [3, KT Chap 11]
Randomized Algorithms [4, KT Chap. 13]
Special Topics [2]: Peer-to-peer systems for content distribution networks.

The "Dream Textbook"!

Ronaldo, Zidane, Thuram ... that's the Football Dream Team. For this course, we have a Computer Science Dream Team of Jon Kleinberg and Eva Tardos , two of the foremost researchers and teachers in the world. Through their research and teaching they have made pioneering contributions to Computer Science. Kleinberg had the basic idea behind CLEVER a search engine rival to Google and many other interesting ideas on internet algorithmics. Tardos has done pioneering work in the design, maintenance, and management of high-speed communication networks and auctions on the internet. Together, they have developed the Dream Textbook for an introduction to Algorithms at Cornell It is a "Dream text" because it shows how algorithms lie at the core of many Computer Science applications in the real world, give strategies to think about how to come up with solutions to algorithmic problems and how to scientifically analyse their performance - exactly the goals of this course! They show how the modern subject of algorithms has reached a high level of sophistication. We will be one of the first courses in the world to start using it. Almost surely, it will soon catch up in the rest of the world! We will use roughly the second half of the book for this course (roughly the first half was covered in Basic Algorithms course that is prerequisite for this course.

Related Courses

Randomized Algorithms A course that deals extensively with the powerful Markov Chain Monte Carlo method. Highly recommended!
Markov Chains.
Discrete Optimization a course that specializes on techniques for optimization problems.

Algorithms Seminar Course.

Lecture Diary

NP-completeness [KT, Chapter 8]
1. [Oct. 29] KT, section 8.1 Basic concepts and reductions .
2. [Oct. 31] KT, section 8.1. 8.5, 8.7 More Reductions .
3. [Nov. 5] KT section 8.2, 8.3 NP, NP-complete and all that
4. [Mov. 7] More Np blah blah.
Approximation Algorithms [KT Chap 11]
1. [Nov. 12] Introduction to approximation algorithms [KT 11.1,11.2].
2. [Nov. 14] Approximation algorithms cont'd, pricing and LP rounding for vertex cover [KT 11.4, 11.6] and greedy for set cover [KT 11.3]
3. [Nov. 19] FPTAS for Knapsack [KT 11.8] and introduction to randomized algorithms with contention resolution [KT 13.1]. Read [KT 13.12] for background in discrete probability.
Randomized Algorithms
1. [Nov. 21] Randomized algorithms cont'd.
2. [Nov. 25] Coupon collector [KT 13.3], randomized 3-SAT [KT 13.4] Hashing [KT 13.6].
3. [Nov. 28] Randomized closest pair [KT 13.7].
Network Flow
1. [Dec. 3] Network Flows, Min Cut, Ford Fulkerson Algorithm and applications [KT 7.1, 7.2, 7.5, 7.6, 7.12] Chandra Chekuri's slides 1 and Chandra Chekuri's slides 2. Max-Flow Demo and Flow Applications .
Network Coding and p2p Networks
1. [Dec. 5] Sashi Hariharan's slides on network coding based on Microsoft Tech report on network coding.. Gopal Pandurangan's slides on randomization to build p2p networks.

Exercise Diary

[Nov. 4]. Problem 8.2, 8.6. Look at the solved problems especially to see how to write solutions.
[Nov. 11] Problems 8.10, 8.14, 8.22.
[Nov. 18]
1. Construct a worst case example for the LPT rule for machine scheduling.
2. Construct a worst case example for the greedy set cover algorithm.
3. Construct a graph such that the gap between the ILP and LP optimum for the vertex cover problem is 2. Hence argue that a certain class of algorithms cannot give a better epproximation factor than 2.
4. Write a ILP for the set cover problem, pass to the LP relaxation and suggest a rounding based algorithm. Analyse its performance.
[Nov. 25]
1. [Monty Hall Problem] At a talk show, the host shows you three doors behind one of which is a lovely blonde (for non-sexist version, a treasure chest). You have to choose one of the doors. After you make your choice, the host opens one of the other doors to show that nothing is behind it. Now you have the option to either keep to your choice or to switch to the third door. What would you do and why?
2. [Lost Boarding Pass] One hundred passengers start to board a plane. However the first passenger lost her boarding card, and hence goes and sits on a random seat. Every subsequent passenger goes to his/her own seat, but if it is already taken, goes and sits on a random seat instead. What is the probability that the last passenger gets his correct seat?
3. A traditional fair die is thrown twice independently. What is the probability that
  1. a six turns up exactly once?
  2. both numbers are odd?
  3. the sum of the scores is 4?
  4. the sum of the scores is divisible by 3?
4. Solved Exercise 1, Chapter 13.
5. Discuss how you'd implement Karger's algorithm to run fast.
6. Lazy Lars says there is no reason to have solved the dynamic programming for Knapsack all over again: we can just use the solution from section 6.4 which runs in time O(nW) and to make it polynomial time, we scale and round the weights. Agree?
[Dec. 2]
1. A set of n bar magnets is placed along a line with random independent orientations. Like poles repel and opposite poles attract. What is the expected number of blocks of joined magnets?
2. Problem 13.2 (Note that the problem is very unrealistic even in Obamamania, and also doesn't take into account the mysterious failures of voting machines in the Land of the Free.)
3. Problem 13,3.
4. Solved Exercise 2.

Exam

Exam for real . Bring solutions to class on Friday at 10 AM where you can also listen to a short presentation by the CEO of local p2p company Contribio. .
Sample Exam .
Sample Exam Solutions