Design and Analysis of Algorithms

CS 3510 - Spring 2018


[ Home | Lectures | Homeworks | Calendar ]

COURSE INFO



CLASS TIMES: MW 3-4:15pm in College of Business 100

INSTRUCTORS:   Eric Vigoda and Prasad Tetali

Eric's office: Klaus 2222  
Email:
Eric's Office Hours: Tuesdays 10-11am and Thursdays noon-1pm in Klaus 2222

Prasad's office: TBA  
Email:
Office Hours: TBD

TA's:   TBA
Email:
Office Hours: TBD
                location TBD

GRADING SCHEME: Best of two:
    1.
    • Homeworks: 5%
    • Best 3 of 4 midterm exams: 60%
    • Final exam: 35%
    2.
    • Homeworks: 5%
    • All 4 midterm exams: 95%

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

    The midterm exams will tentatively take place on the following dates:
    • TBD

    TEXTBOOK: (required) Algorithms by Dasgupta, Papadimitriou, and Vazirani [DPV]
    (Available at GaTech Bookstore or via Amazon)
    (Note, exercise/section numbers may differ in online versions.)

    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.


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

  6. HOMEWORK POLICIES:
    Submissions:
    Homeworks are submitted via Gradescope.
    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.