**Fall 2009**

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

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.

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.

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.

Your professor welcomes technical and administrative questions
and concerns,

and particularly invites your comments
about the class,

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)

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

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

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.