Design and Analysis of Algorithms

CS 3510 - FALL 2013


[ Home | Lectures | Homeworks ]

[Piazza course page]

COURSE INFO



CLASS TIMES: MWF 12:05-12:55 PM in Instructional Center 205

INSTRUCTOR:   Eric Vigoda
Office: Klaus 2146  
Email:
Office Hours: Mondays and Wednesdays 1-2pm in Klaus 2146

TA:   Ioannis Panageas
Email:
Office Hours: Tuesdays and Thursdays 6-7pm
                in the commons area in front of Klaus 2138

GRADING SCHEME:
  • Homeworks: 5%
  • 5 Midterm Exams: 70%
  • Final exam: 25%

EXAMS:
There will be 5 midterm exams plus a final exam.
The final exam will be all inclusive.

The midterm exams will tentatively take place on the following dates:
  • Friday, September 6
  • Wednesday, September 25
  • Friday, October 11
  • Monday, November 4
  • Monday, November 25
TEXTBOOK: (required) Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani [DPV]
(Available at GaTech Bookstore or via Amazon)
A preliminary version of the book is available online.
(Note, the exercises and section numbers may be slightly different in the online version.)

Other good references:
Algorithm Design by Kleinberg and Tardos [KT]
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein [CLRS]
An online version of [CLRS] is available from the library here.
These three books ([DPV], [KT], and [CLRS]) are on course reserve at the library.


TOPICS COVERED:
  • Dynamic programming
  • Divide-and-conquer strategies
  • Graph algorithms: strongly connected components, shortest paths, and minimum spanning trees
  • NP-completeness
  • Other topics depending on the time available

  • HOMEWORK POLICIES:
    Submissions:
    Homeworks are due at the start of class.
    If you cannot make class, you can send it as a PDF to Eric and the TAs.
    No late homeworks will be accepted since we will often discuss the solutions during
    class and solution sets will be posted to T-square after the homeworks
    are collected.

    Collaboration:
    Homework solutions must be in your own words.
    It is probably best to try the homework on your own first. For the challenging problems, it might be useful to work together with other students. However, you should redo the solution from scratch by yourself, and write it up in your own words.
    List at the top of your homework who you collaborated with.
    You cannot consult outside sources, other than the above textbooks.