COMP 6901 -- Applied Algorithms, Fall 2025

The course information below is tentative! .

Lectures: 12:00pm-12:50pm on Monday, Wednesday, Friday in ED 2018A.

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

We will be using Brightspace (formerly known as D2L) for submissions, grades, announcements, etc. All the course materials will also be posted here.

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.

We will also use other materials such as research papers.
See the lecture notes from the previous run of this course for more information.

Marking scheme: (tentative!): The course mark is determined by your performance on written tests and drills, with an optional drill-writing project, and an optional oral exam.

• Test 1, 45%, sometime in October
• Test 2, 45%, last week of classes
• Drills, 10% total
  Drills are short multi-attempt repeatable autograded exercises available through Brightspace quizzes. There are unlimited attempts for each drill, with each drill mark an average of all attempts. There will be several drills, 10% is the sum total over all of them.
• Optional: drill-writing project. If you do it, it will be 20% of your total, with tests respectively becoming 35% each.
  The challenge is to create drills that would not be easily solvable by current LLMs (eg chatbots), on the topics of this course (background also OK). I will provide the template code (in Python), and you will have all the formatting functions already available, you just need to add a solved instance generator for your problem. If you are interested, please email me and meet me to discuss your idea for the drill by the end of September. This project can be done in groups of at most 3, and your drill will be added to the pool of drills for the course.
• Optional: oral exam
  You can also opt to replace some of your test 1 weight by "mock job interview". It will be in person, and if anyone is interested I will post a list of practice problems. If you choose to do it, the oral exam will count as a 20% of your total grade, with the test 1 becoming the remaining 25% (or 15% if you do the project). If you are interested, please let me know by the end of September.
• 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 Brightspace: 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 (in particular, tests are pen-and-paper, no LLMs!) The goal is to learn to solve the problems and demonstrate that skill on the tests, and if you solve a practice problem with an LLM you just wasted a problem.

Plagiarism is a serious academic offence and will be dealt with accordingly. Posting any course content (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.