This is an introductory graduate-level course on algorithm design and analysis,
covering fundamental techniques in designing algorithms and proving bounds on their time and space complexity.
As the course focuses on the analysis (therefore mathematical aspect) of algorithms,
students are expected to have a solid undergraduate mathematical background
(e.g., elementary combinatorics, discrete probability, basic linear algebra and calculus).
Students are also expected to have learned elementary algorithms, including
basic data structures, basic sorting and searching, elementary graph terminology, and
asymptotic analysis of time and space complexity for algorithms (i.e. big-O/Omega/Theta notation).
There will be no programming requirement in this course. However, it will be very helpful
to have past experience with implementation of basic algorithms and data structures.
Office Hours: By appointment. Associate Instructors:
Chao Tao (taochao@umail), Mounik Chinthapanti (mchintha@umail), and Yan Song (songyan@umail)
Textbook.Algorithm Design (Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005. Abbreviated as KT below).
6 homeworks (6 * 5% = 30%);
closed book exams (65%):
2 in-class midterm exams (2 * 15% = 30%);
1 final exam (35%);
class participation (5%).
5% of the total grade for this course is allocated to participation score.
Each student's participation score is determined by attendance,
using the following method.
Every student starts with 6 points.
The instructor will track attendance in a few randomly selected class meetings.
For each time failing to attend the class,
the student gets 1 point deducted from his/her base participation points.
The minimum base participation point is 0.
Besides the base points, a few bonus points will be awarded to students who actively participate in class discussion.
This will be done at the end of the semester,
and then the total participation score will be capped at 5 points.
The two in-class midterms are tentatively scheduled on Sep 25 and Oct 30 now.
These dates will be confirmed at least one week before the exams.
There will be NO make-up exams.
If students have to miss the in-class midterm exams due to family/medical emergencies
(and/or other reasons which will be granted on a case by case basis),
they need to contact the instructor before the exams for permission,
and their other exam grades will be re-weighted.
Internship and job application interviews and paper deadlines are NOT proper reasons to miss an exam.
Homework problems (and their due dates) will be posted on Canvas. Student solutions are due in class on due date.
Please contact your associate instructor for late submission.
Homework late policy.
Full credit will be given for solutions turned in on (or before) the due date. 80% credit will be given for one-day (24-hour) late.
60% credit will be given for two-day (48-hour) late.
NO credit will be given after two days.
Homework collaboration policy.
Students are encouraged to discuss and work in groups on homework problems.
However students must state the people they discussed with in the acknowledgement section of their written assignment.
Students are not allowed to take detailed notes in any group discussion that will appear verbatim in assignment write-ups. Every student has to turn in answers that are written solely by himself/herself.