COMP 3600 -- Algorithm Design and Analysis, Winter 2021

Announcements

4/1/2021 The first lecture will be on Tuesday, Jan 12th (first class). A Zoom link for it will be posted on Brightspace/D2L .
4/1/2021 If you still could not register, but would like to attend, please send me an email (I have no control over registration -- you'd have to wait for a spot to open, but I can at least let you participate in the lectures while you are waiting).

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 everybody's availability, enrolment, software licenses and other factors.

Lectures: 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.

Instructor: Antonina Kolokolova Email: Please email me at kol@mun.ca, 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 kol@mun.ca 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:

Jon Kleinberg, Eva Tardos. "Algorithm Design".
Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. "Introduction to Algorithms."
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani "Algorithms"

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 two main components of the marking scheme: drills and exams.

Drills will be short multi-attempt repeatable autograded exercises available through D2L/Brightspace; together, they will account for 40% of the total mark.
Instead of the normal written tests, we plan to have oral exams both for the midterm (25%) and the last week of classes test (35%). They will be based on a posted ungraded list of problems, which we will discuss in the office hours and on the D2L discussion board.
We will talk about the details during classes.
Additionally, we will have a bonus "bug bounty" for finding errors in slides, drills and ungraded assignments.

Description: The goal of this course is to study both classical and advanced algorithm design techniques, with the corresponding 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. Time permitting, we will consider randomized, parallel and distributed algorithms, and/or streaming algorithms.

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.
The main rule is: the work you submit must be your own . You are encouraged discuss 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. Plagiarism is a serious academic offense and will be dealt with accordingly.
Posting any the content of drills and exams on the internet, with or without solutions, is a serious offence which will be reported.