COMP 6901 -- Applied Algorithms, Fall 2020

Announcements

• 8/9/2020 There will be no lecture tomorrow (Wed, Sep 9th), as we are still trying to converge on a time slot for the lectures (the scheduled time slot does not work for me, and for several students in the class).
  If you have not yet done so, please login to Brightspace and fill the survey indicating which times work for you! It is challenging to find a common time, as we are across a number of time zones from China to British Columbia, but I hope to converge on something by the end of this week, and start lectures next week.
  I will be posting videos of the lectures, so even if we cannot find time that works for everybody, you will be able to watch the lectures later, and ask me questions in the office hours.
• 6/9/20220 Since not that many people filled the lecture times survey, I have extended its availability for a few more days. Please fill it in to indicate when you can attend the lectures (on Zoom). Make sure to select as many options as possible; if you have a preference, please say it in the second question of the survey. The sooner we converge on the times, the sooner we can start the class!
• 26/8/2020 The Brightspace shell for the course is now available. Please log in to it (it should be open to all registered students) and fill in the survey for selecting a time slot for our lectures by September 4th. You can find the survey under "Assessments/Surveys", or click on the link from the first announcement.
  If you cannot yet register, but intend to be in the course, please email me.

Course information

Instructor: Antonina Kolokolova
Instructor office hours: TBA. Also on Zoom.
Additionally, we will be using discussion boards on Brightspace.

We will be using Brightspace (formerly known as D2L) for assignment submissions, tests, grades, announcements, etc. The assignments, slides and videos of lectures will also be posted here.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 J. Kleinberg, E. Tardos. Algorithm Design, but you do not need to buy it.

Reference books:

• J. Kleinberg, E. Tardos. Algorithm Design.
• Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.

Marking scheme: (tentative!): 4 assignments 15% each, and two tests 20% each. The last test is likely to be scheduled during the last week of classes.

Description: The goal of this course is to study both classical and advanced algorithm design techniques with emphasis on real-world applications. We will cover greedy algorithms, dynamic programming, backtracking, network flows as well more advanced algorithms and techniques (time permitting). Time permitting, we will consider randomized, parallel and distributed algorithms, and/or streaming algorithms.

Prerequisites: This course assumes proficiency in the core subjects of computer science: programming, discrete math, and basic data structures/algorithms. 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, can read and write pseudocode, and can program fluently in some programming language. Check our undergraduate courses COMP 1001, COMP 1002 and COMP 2002, and make sure you are comfortable with the material covered there; this should take care of most of the skills you need to succeed in COMP 6901.

Policy on collaboration: The work you submit must be your own. You may discuss problems from assignments with each other; however, you should prepare written solutions alone, and do not interact with anybody except the instructor while doing tests and online exercises. Plagiarism is a serious academic offense and will be dealt with accordingly. When in doubt, check How to avoid plagiarism