Topics in Algorithms
Course Management Form, Fall 2017
- 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
the complexity of divide-and-conquer algorithms and solving recurrence equations.
We discuss a few prominent examples of the divide-and-conquer strategy, namely,
fast multiplication of long integers, and
efficient multiplication of polynomials using the fast Fourier transform.
will be discussed including Bellman's principle of optimality, overlapping sub-problems,
the optimal substructure property, writing a recurrence that relates sub-problems.
Next, correctness, complexity and implementation of dynamic programming algorithms
will be discussed including comparison of memoization and iteration over subproblems.
This will be illustrated with examples, e.g., matrix multiplication, polygon triangulation,
fiding a maximum total value contiguous sub-sequence,
scheduling of prioritized jobs with deadlines, and others.
The final parts of the course include
introduction to practical algorithms for computationally challenging problems,
using heuristics, approximation algorithms and introduction to randomization algorithms.
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).
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 or
Lectures: 3 hours, No labs.
Compulsory Text Book:
by Jon Kleinberg and Iva Tardos,
ISBN: 0-321-29535-8, (C) 2006, 864 pp, publisher:
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.
The algorithm design manual, 2nd edition, Springer 2008.
Available online for students through the Ryerson 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 (College of Computing, Georgia Institute of Technology)
Approximation Algorithms, Springer, 2003, ISBN 978-3-662-04565-7. A
PDF file of
his book is available for educational personal use only.
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.
(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).
Steven Skiena and Miguel Revilla:
The Programming Contest Training Manual, Springer, 2003,
ISBN: 978-0-387-00163-0 (Print) 978-0-387-22081-9 (Online).
Table of content.
3 assignments (10% each): worth a total of 30% of the final grade.
Quizzes: 5%. Midterm: 20%. Final exam: 45%.
Graduate students will have to do additional work on assignments and tests.
Undergraduate students can earn bonus marks for doing extra work.
Topics (tentative list):
Introduction to algorithm analysis, order notations, heaps and priority queues, the greedy
method, interval scheduling, proving correctness (or demonstrating lack of optimality)
of greedy algorithms, an exchange argument (these topics will take about 4 weeks),
the divide and conquer strategy, its application to fast multiplication of long integers
and efficient multiplication of polynomials using the fast Fourier transform
(these topics will take next 1 week),
dynamic programming, overlapping sub-problems, optimal sub-problems,
matrix chain-product, multy-way choices,
optimal scheduling of jobs with priorities and deadlines,
(these material will take about 3 weeks after the reading week),
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 coarse notations, mathematical language,
discussion of mature Computer Science themes and explicit proofs.
Student's discretion is strongly advised.
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.
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 will be 15-45 min, 1h40min,
and 2h30min, respectively. There will be
no supplemental examination.
- 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.
Grades are earned for the demonstration of knowledge.
If you miss a midterm test, a final exam or a deadline for an assignment
for medical reasons, you have to provide an
Health Certificate AND
Academic Consideration form
to the department of Computer Science within 3 working days.
You have to bring your documents yourself to the CS front reception desk.
Similarly, all documentation related to special accomodation 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 earlier).
Your assignment is considered late if any part of the assignment is late
(even if it is just 1 minute late). Printed copies of the assignments should be
handed in before class starts.
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.
Late assignments: to hand in your printout, you can give it in person to
a secretary at the CS reception desk and ask her/him to put a stamp on your assignment
to confirm that you handed in your assignment in time. Send email to the TA
who is responsible for marking this assignment: inform that a hard copy of
your assignment is available from the front desk.
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% (or less) extra credit may be assigned for active class participation
throughout the term, e.g., a student attends most of the classes, participates actively
by asking/answering questions, solves exercises in class. Class participation
marks are earned for active course participation and 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 Ryerson's
email addresses only: you can use either your departmental account
(preferred) or your university account to send email.
Email sent from Yahoo, Hotmail
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
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 Ryerson D2L
no later than two weeks after the due date (test date). Handouts and
some other course related documents will be posted on the
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
Policy on collaboration in homework assignments and in labs
Limited collaboration in discussing general approaches to problems
may be allowed (only with students in your team); no collaboration is allowed
between teams. You may discuss assignments only with other people
currently taking the course. However, you should never put your name
on anything you do not understand. If challenged,
you must be able to reproduce and explain all solutions by yourself,
or solve similar exercises. If you cannot explain a solution that
you handed in, or if you cannot solve an exercise similar to questions
in your home work, the grade for the home work can be decreased to 0.
In particular, you might be asked to solve exercises during the office
hours, or in class (as a quiz). Remember that if you work with partners,
you are still expected to know solutions of all exercises from the home
work. Grades are earned for the demonstration of knowledge.
The first page of your homework should include: the name of all
students with whom you discussed any homework problems (even briefly).
Otherwise, it is assumed that you didn't discuss with anyone except the
instructor. Copied work (both original and copies) will be graded as 0.
Involvement with plagiarism will be penalized in accordance with the departmental
policy and the Student Code of 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.
Committing academic misconduct, such as plagiarism and cheating,
will trigger academic penalties including failing grades,
suspension and possibly expulsion from the University.
As a Ryerson student, you are responsible for familiarizing yourself
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.
- Grades are earned for the demonstration of knowledge.
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.
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.
Forward your assignment and the remarking request form to the TA/GA who
marked your assignment. To do this leave your remarking request
attached to the hard copy of your assignment at the Computer Science
reception desk (ask for a stamp with the date). Send email to the TA/GA to
inform that you left a remarking request.
Remarking request can be only submitted within 10
working days of the return of the graded work (quiz or assignment) in
class. It is your responsibility to pick up your quiz/assignment as
soon as possible. Late regrading requests will not be accepted.
It's your responsibility to pick up your work ASAP.
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)
||Grade Value (%)
October 6, Friday
Friday, October 20, 3-5pm
November 9, Thursday
November 30, Thursday
|Quizzes & tracing algorithms
In assigned class time
The total grade (100%) is the sum of marks for assignments (30%), quizzes(5%),
midterm (20%) and the final exam (45%).