CS-3510: Design and Analysis of Algorithms
School of Computer Science, Georgia Tech
The course covers basic techniques (such as divide-and-conquer, dynamic programming, greedy algorithms, local search)
for the design and analysis of efficient algorithms for standard computational problems (related to graphs, hashing, sorting, optimization, etc).
It also provides an introduction to the theory of NP-Completeness.
Prof. Constantine Dovrolis
Office: CODA S1215
Office hours: Tuesdays , 1:30-3:00 at KACB 2228
Email: firstname.lastname@example.org (but the best way to ask questions is through Piazza)
The names and email addresses of the TAs will be announced in class and on Canvas.
Table of Contents
- Lectures: Tue and Thu - 12:00-1:15pm
- Classroom: CCB 16
- Prerequisite: "C" or higher in CS2050/CS2051/MATH2106 and "C" or higher in CS1332/MATH3012/MATH3022
- Credits: 3
- Note: There are three sections for CS3510 in this semester. While all sections will cover mostly the same material, there may be difference in topic sequencing and emphasis. It is important that students attend the lectures, do the HWs and programming assignments and take the tests for the section the student is registered in. This syllabus is for SECTION A.
- Give the instructor a printed face-photo with your name, major and year of study: Jan 9 (in class)
- First midterm exam: Jan 23 (in class)
- Second midterm exam: Feb 25 (in class)
- Spring break: Mar 16-20
- Third midterm exam: Mar 26 (in class)
- Programming project due: Apr 17
- Last class: Apr 21
- Final exam: Mon, Apr 27, 11:20am-2:10pm (comprehensive exam)
We will use the following textbook (required).
The following books are optional and they can be used as references:
Introduction and algorithm analysis
Basic graph algorithms 1
Basic graph algorithms 2
Greedy algorithms 1
Greedy algorithms 2
Dynamic programming 1
Dynamic programming 2
More graphs and network flow
NP-Complete problems 1
NP-Complete problems 2
Introduction to Approximation algorithms and Local Search
This week is left blank in case we are running late. If we are not late we can cover more advanced topics
Material will be due at 11:59pm on the specified date and should be submitted using Canvas.
- Homeworks: We will be giving you homework assignments throughout the semester. I expect a total of 7-9 homework assignments.
They will be released on Monday morning and they will be due on the following Sunday evening.
The solutions will be posted a couple of days later so that you can check your solutions.
- Programming project: We will also have a programming project. We will give you an interesting computational problem for
which you will need to design and implement two different algorithms (for example, a greedy heuristic and an algorithm based on
dynamic programming). You will then evaluate the running time of the two algorithms using realistic and synthetic datasets.
You can use Python, Java or C (your choice).
The programming project can be done in groups of two students (or individually, if that is what you prefer).
- Homeworks: 30% (the lowest grade will be ignored)
- Three short exams: 30% (the lowest grade will be ignored)
- Final (comprehensive) exam: 30% (covers entire syllabus)
- Programming project: 10%
- Bonus points (if the final CIOS participation level is 95% or higher by April 26): 2%
Notes about grading:
- I can only give out a grade of I for non-academic reasons.
- If you end up doing poorly in the class please don't ask for "extra work" to raise your grade. This would not be fair to other students.
- For those registered as P/F. A Pass requires that you earn a "C" or better and that you submit all work items and take the exam.
- Final grade distribution: Roughly 35-50% A's, roughly 35-50% B's, and lower grades for students that have not done well.
- For any questions about the lectures, please contact Constantine during office hours or through email.
- For any questions about homeworks or programming assignments, please post a question on Piazza (no anonymous posts will be allowed).
- For any questions about grades, please contact the Lead TA through email.
- Late submission policy:
Assignments and programming assignments should be handed in on time -- by midnight the day the assignment is due. There is a 1 hour grace period for submitting assignments. We cannot accept late submissions.
- You are strongly urged to familiarize yourselves with the
GT Student Honor Code
rules. Specifically, the following is not allowed:
You are encouraged to discuss problems and papers with others as long as this
does not involve copying of code or solutions. Any public material that you
use (open-source software, help from a text, or substantial help from a
friend, etc...) should be acknowledged explicitly in anything you submit to us.
If you have any doubt about whether something is legal or not please do
check with the Instructor.
- Copying, with or without modification, someone else's work when this work is
not meant to be publicly accessible (e.g., a classmate's program or solution).
- Submission of material that is wholly or substantially identical to that
created or published by another person or persons, without adequate credit
notations indicating authorship (plagiarism).