COMP 3600 -- Algorithm Design and Analysis, Winter 2022

Announcements

4/1/2022 The first lecture will be on Tuesday, Jan 11th (first class). A Zoom link for it will be posted on Brightspace/D2L .

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

Midterm, 20%, in-person. Date TBD, end of February/beginning of March.
Final exam, 30%, in-person. You have to pass the final exam to pass the course.
Drills, 20% total, in D2L. Drills are short multi-attempt repeatable autograded exercises available through D2L/Brightspace quizzes. There are unlimited attempts for each drill, with the drill mark an average of all attempts. The number of drills is TBD, but together they will account for 20% of the total mark.
Oral exam, 15%, on Zoom. It will be a "mock job interview" based on a posted ungraded list of problems, as well as assignment questions
Assignments, 3 x 5% = 15 % The main role of the assignments is to give you a chance to practice and get feedback for questions similar to what will appear on the exams. You are encouraged to work together on the assignments, however do write the final solutions yourself (as this will allow for a more useful feedback). The use of Chegg and similar services is a serious academic offence and is absolutely not permitted.
Additionally, we will have a bonus "bug bounty" for finding errors in slides, drills, assignments, etc. In particular, if you found an error in marking of your assignment (such as an incorrect solution marked as correct), you can get the bug bounty for it.
Please post the bugs you find on the discussion board in D2L: the first person to find the bug and post about it gets the bounty. For bugs in marking, please email me directly.
To be eligible for the bounty, this should be a conceptual/technical error rather than just a typo (eg, a missing non-trivial case in an algorithm or a proof, algorithm that does not work, incorrectly computed example, error in a proof, unsolvable or trivially solvable problem, wrong marking in a drill or assignment, etc).

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.