Graduate Algorithms

Instructor: Eric Vigoda  (office hours: TBD)
TA’s: (office hours:  TBD)

  • Murali Raghu Babu
  • Tiancheng Gong
  • Michael Meehan
  • Jian Shi
  • Jeremy Stephens
  • John Turner
  • Xinyu Wang

Grading:  

  • HW/quizzes:  5%
  • Programming project (on Bloom filters): 10%
  • Midterm exams (3):  55%
  • Final:  30%

Course overview:

  • Dynamic programming
  • Divide and conquer, including FFT
  • Randomized algorithms, including:
    • RSA cryptosystem
    • Bloom filters
  • Graph algorithms, including:
    • Strongly connected components
    • Minimum spanning tree
    • PageRank
  • Max-flow algorithms
  • Linear programming: basics and duality
  • NP-completeness

Projects:  There will be one programming project on Bloom filters.  There is no collaboration on the project, they need to be done individually.  Each project will have a programming aspect (in Python) and a brief report.  Details about the projects will be posted during the semester.  You will have roughly 2 weeks to do the project.

Textbook: The required textbook is Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.
The textbook Algorithm Design by J. Kleinberg and E. Tardos is an excellent reference that you might consider looking at as well.

Homework collaboration: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate who you worked with on your solution.

Plagiarism: plagiarism is a violation of the GT honor code.  Your homeworks and projects will be checked with auto-checkers to detect plagiarism.  All violations will be reported to the GT Office of Student Integrity, and you will be given a 0 on that component of the grade (projects or homeworks) and your course grade will be dropped one letter grade (OSI may impose stricter penalties, especially if you have prior offenses).

Advertisements