CS 4540 - Advanced Algorithms

Fall 2010

[ 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 2:05:-2:55, Bunger-Henry, Room 380.
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: Mondays and Thursdays 11-1, 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)

Topics and Schedule Overview

(a) Fundamental Algorithmic Paradigms at an Advanced Undergraduate Level
(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.
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.

Required Textbooks

(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.
Required textbooks available at Barnes and Noble and everywhere over the internet (probably cheaper). All textbooks available on the internet

Grading

(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 (in fact, this is often very useful for your own understanding and your contribution to the class, so you are encouraged to do so as you see fit), but please indicate your collaboration group and/or the resources you used. You MUST write your answers by yourselves, without any collaboration and without lifting material verbadum from any resource. Please remember, no matter how much one reads, or works, or sketches, or discusses, 50% of one's final understanding comes at the point of writing down and presenting.
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) 2-3 MidTerms: 25%. In class, open book.
(c) Final: 25%%. In-class, open book.
(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.

Mon Aug 30: Homework 1 is now posted and due Friday Sept 10.
Make sure you read, understand and consult the lecture notes and the assigned reading.
Start working on the homework very soon; do not leave it for the last minute.
Do not hesitate for a moment to contact to your instructor for any questions and advise.

Fri Sept 10: Homework 2 is now posted and due Friday Sept 17.
Make sure you read, understand and consult the lecture notes and the assigned reading.

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.