Detailed Course Information

Instructors: Eric Vigoda
All communication is through Piazza;  if necessary you can send a private note (and flag us) in Piazza.  Do not expect a response to emails.

TA’s:
Kate Alpert
Mark Benjamin (head TA)
Zheng Kuang
Menghana Manusanipalli
Michael Meehan
Jeremy Stephens
John Turner (head TA)
Santiago Valdarrama
Kyle Zimmerman (head TA)

Grading:  

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

Course topics:

  • Dynamic programming
  • Divide and conquer, including FFT
  • Randomized algorithms, including:
    • RSA cryptosystem
    • Randomized rounding
    • 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 PageRank.  There is no collaboration on the project, it needs 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 and you can look at any other references (including online).  However you need to write up your solution from scratch as if you are in an exam (this is how you will learn the material).  You need to cite your sources and collaborators at the top of your homework.  There are no extensions on the homework, and typically only a subset of the problems will be graded/counted.  The homeworks are worth little but they are good practice for the exams so your efforts will pay dividends on the exams.

Gradescope:  Homeworks and exams will be submitted through Gradescope.  We will import your information into Gradescope which will create a Gradescope account for you; you are required to use this Gradescope account with the name and GTid that matches exactly with T-Square (otherwise the systems won’t sync and you won’t get a grade).  The default due date/time for all homeworks, exams and projects is Mondays at 8am; there are no extensions (so submit the day before in case of unexpected problems).

Exams:  Exams are administered through Proctortrack.  Exams are closed book, you cannot use any additional devices (no calculators, phones, etc. or other applications on your computer) and no additional references (no notes or books).  You will be given a blank template the evening before the exam window begins.  You print this out and keep it blank (you need to show it at the exam and any additional markings on it will qualify as cheating).  The exam will typically be open for 3 days: starting on a Thursday or Friday morning and closing at 8am EST on Monday.  You need to finish uploading your exam by 8am EST on Monday so plan your start time accordingly (there are often delays due to Proctortrack).  There are no extensions.  We suggest doing the exam at least 24 hours before the deadline in case of potential problems with Proctortrack.

Accommodations:  If you have any accommodations you need to inform us during the first week of classes, and provide us with the detailed accommodation approval letter from the GT Office of Disability Services.  We need to confirm during the first week of classes (by the first Friday at 4pm) that we can accommodate your requests.  If you don’t get approval from us by the first Friday at 4pm then we cannot accommodate your requests.

Scanner: At the conclusion of the exam while Proctortrack is still running you will scan your exam (within view of your computer’s camera), and then upload your exam to Gradescope.   You can use your phone.  You need to have a high-quality scanner or phone+app that will allow you do the scanning reasonably quickly and that produces images of high enough quality that the PDF is easily legible.

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).

Cheating: Any incidents of suspected cheating will be treated in the same manner as plagiarism (zero on that component + 1 course letter grade lower) and will be reported to the GT Office of Student Integrity.