COMP 3600 -- Algorithm Design and Analysis, Winter 2022

Announcements | Course information |


Course information

The course information below is very tentative! The way the lectures/tests are done and the marking scheme, in particular, are likely to change depending on how long we stay remote and other factors.

Lectures: Until the end of January, synchronous, on Zoom, during scheduled class times (7pm-8:30pm Newfoundland time on Tuesdays/Thursdays). The lectures will be recorded and recordings/slides posted on
Brightspace/D2L . If you have trouble accessing Zoom, please let me know as soon as possible and we'll try to find a workaround.
If the situation permits, from February the lectures should revert to in-person: same time in EN-1054.

Instructor: Antonina Kolokolova Email: Please email me at, unless you have an attachment (or generally if your email is larger than 0.5Mb). If you want to send me a screenshot/photo/etc and end up with a large message, please send it to me through D2L/Brightspace mail, but do email me at to let me know that you sent it, as D2L mail has to be checked by manually and so will not be read nearly as often.
Instructor office hours: TBD. Also on Zoom.
Additionally, we will be using discussion boards on Brightspace.

We will be using Brightspace (formerly known as D2L) for posting slides and videos of the lectures, discussion board, grades, etc. The Brightspace shell for our course should be available shortly to all registered students; if you cannot register/access Brightspace after the first week of classes, please let me know.

Textbook: There will be no official textbook for this course. We will mostly follow "Algorithm design" by Kleinberg and Tardos , but you do not need to buy it.

Reference books:

See the lecture notes from a somewhat similar graduate course and another course covering NP-completeness for more information. I may use some of the slides for the Kleinberg-Tardos textboook, but will likely modify them fairly significantly, adjusting both the slides and the topics depending on how the course is going, everybody's background, etc. I will not be posting anything before the lectures; please see the materials above to get a preview of what we may cover and how.

Marking scheme: (tentative!): There will be four components of the marking scheme: assignments, drills, oral exam and written exams. If we are not able to have written exams in person, the marking scheme will be changed; in that case, already submitted work may be reweighted.

Description: This course focuses on techniques for designing algorithms for computational problems, with an emphasis on correctness proofs and complexity analysis. We will cover greedy algorithms, divide-and-conquer, dynamic programming, backtracking and network flows, as well more advanced algorithms and techniques (time permitting). We will also devote part of the course to both showing computational hardness (primarily NP-hardness) of problems, and discussing ways of dealing with this hardness.

Prerequisites: This course mainly relies on proficiency in the topics covered in COMP 2002 and COMP 1002. In particular, I will assume that you can read and write proofs, know basic probability theory and combinatorics, know basic data structures and algorithm complexity analysis, and can read and write pseudocode. Programming proficiency is useful, but not required.


Policy on collaboration and plagiarism.
The main rule is: the work you submit must be your own. You are encouraged to work together on problems and ask questions about them on the discussion forum; however, you must work out all answers you submit on drills, exams, etc by yourself, without looking things up online or interacting with anybody except for the instructor. You are welcome to work together on the assignments, but write solutions by yourself. If you come across an answer to a similar problem while researching a topic, you must reference the source and restate the solution in your own words, then you can receive full marks.
Plagiarism is a serious academic offence and will be dealt with accordingly. Posting any course content (assignments, drills, exams, practice problems) on the internet, with or without solutions, or using services such as Chegg is a serious academic misconduct which will be reported.