COMP 6901 -- Applied Algorithms, Winter 2022

Announcements

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

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 submissions, tests, grades, announcements, etc. All the course materials 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!): The course mark is determined by your performance on assignments, drills, drill-writing project, and written exams; there is also an optional oral exam. 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, 25%, 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.
• 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.
• Drills (15% writing + 15% solving) 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.
  In this course, you will need to write your own drill on some algorithms or related question of your choice. You can work in groups of up to 3 students; a template in Python will be provided. Then, all drills will go live on D2L, and everybody will need to do all posted drills. The first person to find a bug in somebody's drill gets extra points, and drill authors' mark is decreased; they will have to fix the bug and repost the drill. Tentatively, drill proposal (question and groups) will be due no later than Jan 24 and drills submitted by Feb 16; after that, solving/debugging stage begins, timeline TBD.
• Optional oral exam, on Zoom. You may opt to do a "mock job interview" (oral exam) for a part of your midterm weight. In this case, 2/5 of your midterm weight (10% of the course total mark) will be based on the oral exam, and the rest, 3/5 of the midterm weight (15% of the course total) will be based on the written midterm.
  
• Additionally, we will have a bonus "bug bounty" for finding errors in slides, 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, etc).

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 topics. 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 such as Python. 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 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.