Course Description

• The Course's Academic Focus and Scope: This elective course covers advanced methods of algorithmic design and analysis with focus on efficiency and correctness of algorithms. The course starts with an overview of algorithms efficiency, mathematical induction and advanced data structures such as priority queues. Then, the greedy design technique will be discussed in depth with focus on design of correct greedy algorithms that can actually find an optimal solution. This includes developing counter examples to incorrect greedy rules, or using an exchange argument to demonstrate correctness. An efficient implementation of greedy algorithms based on a priority queue will be illustrated on several examples. Next, the course includes a discussion of advanced divide-and-conquer algorithms, their complexity and solving recurrence equations. Namely, the topics may include a few prominent examples of the divide-and-conquer strategy such as efficient insertion and deletion algorithms in B-trees, and efficient multiplication of polynomials using the Fast Fourier Transform (FFT). Subsequently, we review Bellman's principle of optimality, overlapping sub-problems, the optimal substructure property, writing a recurrence that relates sub-problems, and then we discuss advanced examples of dynamic programming, e.g., complex variations of the knapsack problems, finding a maximum total value contiguous sub-sequence, scheduling of prioritized jobs with deadlines, and others. Next, we review linear programming, its geometric interpretation, the simplex algorithm, the weak and strong duality theorems, discuss how the primary and dual linear programs are related, and how their relation leads to complementary slackness conditions. The final parts of the course include introduction to practical algorithms for computationally challenging problems and using greedy heuristics to construct approximation algorithms for the center selection problem. In particular, we discuss how the primary-dual approach leads to design of a constant-ratio approximation algorithm for the weighted vertex cover problem and the design of an approximation algorithm for the set cover problem. We discuss an introduction to randomization algorithms, e.g., contention resolution and a randomized approximation algorithm for MAX-3SAT.
  The bonus questions in homework assignments may include questions taken from programming contests that can illustrate methods discussed in class.
  The course can be suitable for all students interested in advanced algorithms and data structures including those who would like to prepare for an interview, and students who would like to develop skills of designing algorithms for practical applications.
    Prerequisites (for undergraduate students): CPS616.
    Prerequisites (for graduate students): undergraduate level course on algorithms, and ability to write programs in one of the modern programming languages (C,C++,Java,Python).
• Educational Objectives: enable students to learn some of the fundamental ideas in algorithm analysis and design, to know and understand the basic mathematical properties of algorithms, to learn the basic techniques of proving correctness of algorithms, to implement algorithms efficiently, to develop basic skills of designing approximate algorithms and randomization algorithms.
• Teaching methods: Lectures: 3 hours, No labs.
• Text Book:  Algorithm Design, by Jon Kleinberg and Iva Tardos, ISBN: 0-321-29535-8, (C) 2006, 864 pp, publisher: Addison-Wesley/Pearson Education; online purchase price $35US. The Chapters 4,5,6,11,12,13 of this textbook cover the material related to CPS815. The remaining Chapters 8-10 include a more theoretical material on computational complexity. Click to read a detailed table of contents.
• Recommended references: 
  • Steven Skiena: The algorithm design manual, 2nd edition, Springer 2008. Available online for students through the TMU library.
  • Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, 3rd edition, MIT Press, 2009. Chapter 5 (Probabilistic Analysis and Randomized Algorithms) and Chapter 35 (Approximation Algorithms) are useful.
  • Vijay Vazirani (Computer Science Department, University of California, Irvine) Approximation Algorithms, Springer, 2003, ISBN 978-3-662-04565-7. Content of his book as a PDF file.
  • The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, published by Cambridge University Press. Download a PDF file for educational personal use only.
  • Jim Aspnes (Computer Science, Yale University) Notes on Randomized Algorithms prepared for CPSC 469/569.
  • Elias Koutsoupias (Computer Science, Oxford University) Probability and Computing, Lectures (March 9, 2017).
  • Allan Borodin and Ran El-Yaniv book Online Computation and Competitive Analysis published by the Cambridge University Press, isbn: 9780521619462. Table of content (PDF file).

• Evaluation: 3 assignments (10%, 10% and 15%): worth a total of 35% of the final grade. Quizzes: 5%. Midterm: 20%. Final exam: 40%. To complete their 3rd assignment, the students may be asked to prepare slides for a 30min talk on a topic related to the course, and present their talk in class. Graduate students will have to do additional work on assignments and tests. Undergraduate students can earn bonus marks for doing extra work. Graduate students may be assigned a project related to this course. To pass the course the following is required:
  • At least 50% must be achieved on the theoretical component (the weighted total of the quiz, test, and exam marks)
  • At least a 50% grade on the remaining practical component (the weighted total of the assignment and project marks).

• Topics (tentative list): Review of algorithm analysis and order notations (1 week), heaps and priority queues (1 week), the greedy method, interval scheduling, proving correctness (or demonstrating lack of optimality) of greedy algorithms, an exchange argument (these topics will take about 2 weeks), the divide and conquer strategy, its application to B-trees and/or efficient multiplication of polynomials using the fast Fourier transform (about 1 week), review of dynamic programming and advanced dynamic programming (1 week), linear programming (2 weeks), approximation algorithms (2 weeks), randomization algorithms (2 weeks). A moderate amount of programming may be required as part of the course (any programming language is fine). Lectures may contain formal notations, mathematical language, discussion of mature Computer Science themes and explicit proofs. Student's discretion is strongly advised.

Course Policies

• The students are strongly encouraged to take notes in class, and study their notes after each class. Learning can be a gradual process that requires time and efforts. The students benefit from attending lectures since some important details will be discussed only there. For this reason, attending lectures is mandatory.
• All course materials posted on D2L are copyrighted and protected by law. You cannot share them with anyone. You cannot repost them anywhere on the Web. Please review the Toronto Metropolitan University policy about copyrights. Moreover, you cannot post on the Web any of your solutions to the quizzes or to assignments, since doing this would violate the cps815 policy on collaboration, and the TMU Academic Policy 60. You can read online parts of this policy related to "Academic misconduct".
• Electronic devices: turn off your mobile phones and all other electronic devices in class. You can keep your laptop or tablet open only if you use it to take notes in class.
• Examinations: The quizzes, midterm test, and the final exam may include problem solving, short essay questions, yes/no questions, as well as writing algorithms in pseudo-code. The duration of these examinations may be 15-45 min, 1h40min, and 2h30min, respectively. Extra quizzes (or polls) can be given at any time in class without prior warning. The midterm and final exam may include questions similar to homework assignments and quizzes. There will be no supplemental examination. Grades are earned for the demonstration of knowledge.


• Brief quizzes may be given without notice. A mark for a quiz will be given to a student only if (1) s/he attends the entire class for which the participation occurs, and (2) the instructor observed the student actively participating, and (3) the student signs the quiz (including a student number); (4) quizzes must be submitted at the end of class; late quizzes will not be accepted; (5) there will be no supplemental quizzes. A student who missed a quiz is encouraged to solve the quiz independently and discuss it with the peers. The marks for quizzes will be given for effort, but also for solution correctness.


• If you miss a midterm test, or a final exam for medical reasons, you have to submit an academic consideration request through the Online Submission Form   and   hand in a copy of a completed official Health Certificate to the department of Computer Science within 3 working days. You can be required to bring your documents yourself to the CS front reception desk. Once the CS Department has verified the student’s health documentation, the instructor will be notified. Similarly, all documentation related to special accommodation or academic consideration should be submitted to the CS program office within the specified time limits.


• Dates are subject to change, all changes will be announced in class and on the course Web pages.
• Assignments should be submitted on or before the deadline specified in the assignment (you are encouraged to submit assignments sooner). Your assignment is considered late if any part of the assignment is late (even if it is just 1 minute late). The penalty for a late assignment is 10% off. No assignments will be accepted if more than 24 hours late. Start solving your assignment on the same day when it is posted. Do not procrastinate. No make-up assignments.
• From time to time, I will hand out exercises. The students are expected to solve the exercises, but they will not be graded. However, working on exercises will improve your understanding of this course (and will help you to get better marks on tests).
• Up to 5% extra credit may be assigned for active class participation, e.g., a student attends the entire class, participates actively by asking/answering questions, works on problems in class and/or attends office hours. Class participation marks are given at discretion of the course instructor. They cannot be requested by the students. Unexplained lack of attendance can negatively affect one's grade.
• Handouts and assignments will be made available on the Web only. More specifically, they will be linked from the CPS815 online course shell on D2L. In addition, you are responsible for visiting the Home Work Assignments related Web pages regularly and reading assignments and tests related information that is provided or linked from these Web pages. In particular, Frequently Answered Questions (FAQs) related to CPS815 home work will be linked from this Web page. These FAQs are considered to be an integral part of the assignment. Before sending your questions by e-mail to the instructor, check these Web pages whether similar questions have been already answered.
• Email communication: please send me email from local TMU email addresses only: you can use either your departmental account (preferred) or your university account to send email. Email sent from Bell, Rogers, Google and other external domains can be filtered out as spam and may not reach me. Students can usually expect a brief reply within 24 hours to email messages sent Monday to Friday, but emails received on weekend or Friday late might not be answered until the following Monday. Students who have questions that need a long time to answer are advised to ask questions in person during the posted office hours.
• Grades for tests and assignments will be posted on TMU D2L no later than two weeks after the due date (test date). Handouts and some other course related documents will be posted on the TMU D2L course shell only. Graded assignments and quizzes will be usually returned to students within two weeks. Those students who missed a class when their graded work was returned are welcome to pick it up from the instructor during the posted office hours.

Policy on collaboration in homework assignments

Contract Cheating Statement
In regard to any and all assessments in this course, the use of Chegg or any other similar help site/service will be pursued as "contract cheating".

The use of ChatGPT, Gemini, Copilot and similar generative large language models (LLM) with the purposes of solving homework problems will be pursued as "a breach of Policy 60: Academic Integrity", if the student accessed them before submitting course work and assessment is presented as if it is one’s own original work without appropriate referencing. Generative LLM tools may only be used for comparison with your own course work that you have already submitted, but not for the creation of submitted work.

Falsified citations or misrepresentation of source material will be considered a breach of Policy 60. You are responsible for the accuracy of the work you submit.

In regard to any and all assessments in this course, the use of any third party (e.g., family member, freelancer, roommate, friend, tutor) to complete work on your behalf will be pursued as "contract cheating" under Policy 60 "Academic Integrity".

Policy 60 Penalty Guidelines for contract cheating (e.g., viewing a solution on Chegg or Discord) that only impacts you: F in course.

Policy 60 Penalty Guidelines for contract cheating that facilitates cheating for others (e.g., posting a question to Chegg): Disciplinary Suspension.

ACADEMIC CONDUCT
In order to create an environment conducive to learning and respectful of others rights, phones and pagers must be silenced during lectures and evaluations. Students should refrain from disrupting the lectures by arriving late and/or leaving the classroom before the lecture is finished.

ACADEMIC MISCONDUCT
Committing academic misconduct, such as plagiarism and cheating, will trigger academic penalties including failing grades, suspension and possibly expulsion from the University. As a TMU student, you are responsible for familiarizing yourself with the Student Code of Academic Conduct.

Policy on Non-Academic Conduct
No disruption of instructional activities is allowed. Among many other infractions, the Code specifically refers to the following as a violation: ``Disruption of Learning and Teaching - Students shall not behave in disruptive ways that obstruct the learning and teaching environment." In particular, the students can use the laptops (and similar electronic devices) in class only for taking notes. In difficult cases, penalties can be imposed by the Student Conduct Officer.

Remarking Policy

1. Grades are earned for the demonstration of knowledge.
2. Read carefully the marking guide for the assignment or test you'd like to be remarked. Your grade may go up, down, or remain the same.
3. Fill in this remarking form (available online). Attach this form to the hard copy of your assignment. Same rules apply if you request recalculation to correct an arithmetical error in calculating your total score.
4. Forward your assignment and the remarking request form to the TA/GA who marked your assignment.
5. Remarking request can be only submitted within 10 working days of the return of the graded work (quiz or assignment) in class. Late re-grading requests will not be accepted.
6. Mark can decrease if TA finds something that was incorrectly awarded too high a mark.

Tentative Course Calendar (all changes of dates will be announced)

Course Work	Due Date	Grade Value (%)
Assignment  1	February 8, Thursday	10
Midterm	Friday, February 16, in class	20
Assignment 2	March 14, Thursday	10
Assignment 3	March 29-April5, Friday	15
Quizzes & tracing algorithms	In assigned class time	5
Final Exam	Exam period	40
Total		100

The total grade (100%) is the sum of marks for assignments, quizzes, midterm and the final exam.