Design and Analysis of Algorithms

CS 3510 - Spring 2020

[ Home | Lectures | Calendar | Homeworks ]


CLASS TIMES: Tu+Th Noon-1:15pm in Van Leer C240

INSTRUCTOR:   Eric Vigoda
Eric's office: Klaus 2222  
Eric's office hours: Tuesday and Thursday 10:30-11am. Held in Klaus 2222

TAs:   Daniel Hathcock, Neil Thistlewaite, Ida Wang, and Bojun Yang.
TA office hours: in the common area in front of Klaus 2138 and Klaus 2119.
        Monday: 12:30-1:30pm (Daniel), 5:30-6:30pm (Bojun)
        Tuesday: 5-6pm (Neil)
        Wednesday: 12:30-1:30pm (Daniel), 4:30-5:30pm (Bojun)
        Thursday: 5-6pm (Ida)
        Friday: 1:30-2:30pm (Ida), 4:30-5:30pm (Neil)

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

Other good references:
Algorithms by Jeff Erickson
Algorithms Unlimited by Roughgarden
Algorithm Design by Kleinberg and Tardos
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
(Some of these books are available online from the library)

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

    Best of two schemes:
      Scheme 1:
    1. All 4 midterm exams: 100% (equally weighted)
      (this scheme can only be used for an A or B)
      Scheme 2:
    1. Homeworks: 5%
    2. All 4 midterm exams: 60% (equally weighted)
    3. Final exam: 35%
    Thresholds for A's and B's will be announced at the end of the semester on April 21st.
    If you take the final exam then we will take the max of the two schemes.
    If you don't reach the B threshold by scheme 1 then you need to take the final exam.

    There will be 4 midterm exams plus a final exam.
    The tentative exam dates are listed on the lecture schedule page.
    No books, no notes, no calculators.
    We will provide scrap paper.
    The final exam will be all inclusive.
    You do not need to take the final exam if you qualify for an A or a B.

    If you have special accommodations for testing or homeworks then you should discuss it with me during the first week of classes. Note you need to submit your ADAPTS testing requests on time so that they can adminster the testing, we cannot adminster the testing with special accommodations.

    Exam Absences:
    If you have an institute approved absence around an exam date then notify the instructor at least 10 days in advance and email me a copy of the institute approved absence from the Dean of Students. If you are sick for an exam then you need to submit documentation to the Dean of Students and then email the instructor an excused absence letter from the Dean of Students (we cannot be privy to any medical information).

    Any evidence of cheating or plagarism on homeworks or exams will be immediately reported to the Office of Student Integrity (OSI).
    You will be given a zero on that aspect (total homework grade for the course or that exam) AND your overall course grade will be lowered by one letter.
    OSI may impose stricter punishments.
    There are typically multiple versions of the exam so it is easy to identify students who copy from other students.

    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 Canvas after the homeworks are collected.

    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 and any outside sources you consulted (including any solution sets you might have found on the web).
    Note homeworks are not worth much, the point of homeworks is to practice and learn the material so copying the solutions does not serve much purpose.
    We will typically do a fast grading of the homeworks and only of a subset of the problems, so you should double-check the solutions yourself.