# CS 4540 - Advanced Algorithms

Fall 2009

[ Lectures] [Homework]

GT Catalog Description

Advanced techniques for designing and analyzing efficient algorithms for combinatorial problems and their applications in computer science.

Students

1. This class is a requirement for the CS Theory Thread.
2. This class is suitable for Discrete Math majors from the School of Mathematics, and it will count towards their CS requirements.
3. This class is suitable for all CS and CM students who wish to complement their credentials with strong analytical skills.
We shall address how the skills that you will obtain in this class enhance your particular main expertize, on an individual basis, and every step of the way. You may also consider taking this class just for audit.
4. Prerequisite: CS3510 or CS3511 or permission of the instructor.
5. If you need instructor's permission to register for this class, please email mihail@cc.gatech.edu.

Lectures

MWF 1:05:-1:55, CoC College of Computing, Room 102.
The material covered in each lecture together with references and/or notes will be posted in the Lectures web page. It is very important to understand that lecture notes are outlines and not substitutes for attending the class or for assigned reading material from the lecture.

Instructor

Milena Mihail, Associate Professor
Office hours: MWF 11-12, Klaus 2138, or by appointment.
mihail@cc.gatech.edu
All email concerning this course should have a subject entitled CS4540.
including new ideas, suggestions, pointers to related materials (such as readings, web sites, etc),
topics that interest you and you want to explore further, and so on.
Office phone: 404-385-0617 (unreliable answering machine)
Cell Phone: 404 379-1460 (quickest and most reliable communication, but use only if necessary)

Topics and Schedule Overview

(main topics from Dasgupta-Papadimitriou-Vazirani, Cormen-Leiserson-Rivest-Stein, Motwani-Raghavan and V. Vazirani.)
(b) Approximation Algorithms, (main topics from V. Vazirani.)
(c) Randomized Algorithms, (main topics from Motwani-Raghavan and V. Vazirani).
(d) Student Term Paper or Project Presentations
and instructor lectures on current topics in theoretical computer science (very large scale data and networks).
The material covered in each lecture together with references and/or notes will be posted in the Lectures web page. It is very important to understand that lecture notes are outlines and not substitutes for attending the class or for assigned reading material from the lecture.

Textbooks

Required (instructor can lend a few extra copies, but these are good reference books to have anyway):
1. "Algorithms" by Dasgupta, Papadimitriou and U. Vazirani. Ed: McGrawHill.
2. "Randomized Algorithms" by Motwani and Raghavan. Ed: Cambridge University Press.
3. "Approximation Algorithms" by V. Vazirani. Ed: Springer Verlag.
4 "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Klein. Ed: McGraw Hill.

Required textbooks available at Barnes and Noble and everywhere over the internet (probably cheaper). All textbooks available on the internet

(a) Weekly or biweekly homeworks, posted in the Announcement Section below and in the Homework web page 25%.
You may collaborate or read any resource you want in solving the problems, but please indicate your collaboration group and/or the resources you used. You MUST write your answers by yourselves, without any collaboration and without using any resource, as if you are taking a closed book test.
Academic conduct is subject to the Georgia Tech Honor Code.
Complete solutions will be posted on Homework web page shortly after the deadline.
Late homework policy: no credit for late homeworks (unless well explained circumstances and communication with the instructor).
Finally, please be respectful by using your best handwriting when writing up your solutions (or otherwise type them up).
(b) MidTerm: 25%. Take-home, to be completed within 48 hours.
(c) Final: 25%%. In-class, with ten 1-sided "cheatsheet" pages.
(d) Term Paper or Project: 25%.
Note 1: You must receive at least 70/100 on each one of (a), (b), (c) and (d) above, in order to pass this class (modulo well explained circumstances and communication with the instructor).
Note 2: You will have ample help from the instructor on each one of (a), (b), (c) and (d) above.
Academic conduct is subject to the Georgia Tech Honor Code

Web Announcements

You are responsible for reading these announcements at the end of the day every Monday, Wednesday and Friday.

Fri Nov 5: Homework 5 is now posted and due Friday November 13.
Make sure you read the notes from the lecture of Mon Oct 26 for Problem 4.
For Problem 5 (and in general) you can use the simplified from of Chernoff bounds (for 0 < \delta < 1):
Pr[X>(1+\delta)\mu] < exp{\delta^2*\mu / 3} and Pr[X<(1-\delta)\mu] < exp{\delta^2*\mu / 2}.

Wed Nov 18: The Final Exam is now posted and due Wed Dec 9.
INSTRUCTIONS: (a)For Problems 1 and 2, you may find the lecture notes of Fri Nov 13 particularly helpful. (For Problem 1, make sure that your divide and conquer algorithm also considers the case where $n$ is odd.) (b)For Problem 3, you may review the lecture notes of Wed Nov 18, and also review your favorite dynamic programming algorithm. (c)For Problem 4, part (a), realize that a graph is 2-colorable if and only if it is bipartite. Part (b) of Problem 4 is fairly straightforward. (d)For Problem 5, you may review the lecture notes and reading assignment of Fri Oct 16.

Class Web-site http://www.cc.gatech.edu/~mihail/index4540.html.

This site is maintained by Milena Mihail, please report problems to mihail@cc.gatech.edu.