10:30-12:00 PM, Thu 1:00-2:30 PM. All lectures in ITB/222
Textbook: "Introduction to Algorithms",
3rd Ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.
- More information about the expansion of matroids to greedoids can be found
in the references of the Wikipedia article here.
Especially interesting are the articles by Bjorner &
Ziegler, and Helman et al.
- A very nice recent survey on Max Flow here.
The course will cover data structures and algorithms topics at
a graduate level. This means that this
course will not be a
repetition of an undergraduate course on the subject, such as,
e.g., CAS CS 2C03, but it will rather cover more advanced
topics, or known material at a more advanced /deeper level of
understanding. For example, Kruskal's algorithm for the
minimum spanning tree problem should already be known, but we
will examine it under a general framework for greedy
algorithms called matroid theory. Therefore it is assumed that
the students already know the material of Chapters 1-5
(Foundations) of the text (note:
students who are not familiar with this material must
cover it as soon as possible).
A tentative list of topics we will try to cover follows.
- Binomial heaps, an example of worst-case analysis
- Amortized analysis (Ch. 17)
- Fibonacci heaps, an example of amortized analysis
- Hash tables, an example of randomized analysis (Ch.
- Greedy algorithms and matroids (Ch. 16)
- Dynamic programming and all-pairs shortest paths (Ch.
- Maximum flow (Ch. 26)
- Linear Programming and Duality (Ch. 29)
- Primal-Dual schema as an algorithmic design tool
- NP-completeness (Ch. 34)
- Approximation algorithms (Ch. 35)
40% Midterm exam (Thu
25/10, 12:00-2:30 pm, open book)
60% Final exam (Thu 13/12, 1:00-3:30 pm, open book,
McMaster Course Policies
- Problem set #1:
Do Exer. 5.2-1 - 5.2-5, 5.4-6, 17.1-3, 17.2-2, 17.3-2,
Prob. 17.2.b, Exer. 19.3-1, 19.4-2 (due during lecture 9/10)
- Problem set #2: Do
Exer. 11.1-4, 11.2-5, 11.4-5, 16.2-1 - 16.2-3, 16.4-3,
16.4-5, 16.5-2. Is Dijkstra's algorithm an application of
GREEDY (p. 440)? (i.e., is there a corresponding matroid?)
(due during lecture
- Problem set #3: Do
Exer. 15.3-4, 15.3-6, Problem 15-5, 25.2-5 - 25.2-7,
26.1-6, 26.2-4 - 26.2-7, 26.3-4 - 26.3-5 (due during lecture 6/12)
"The instructor and university reserve the right to
modify elements of the course during the term. The university
may change the dates and deadlines for any or all courses in
extreme circumstances. If either type of modification becomes
necessary, reasonable notice and communication with the
students will be given with explanation and the opportunity to
comment on changes. It is the responsibility of the student to
check their McMaster email and course websites weekly during
the term and to note any changes."
"Academic dishonesty consists of misrepresentation by
deception or by other
"The Faculty of Engineering is concerned with
ensuring an environment that is free of all
discrimination. If there is a problem, individuals are
reminded that they should contact the Department Chair, the
Sexual Harrassment Officer or the Human Rights Consultant, as
the problem occurs."
fraudulent means and can result in serious consequences,
e.g. the grade of
zero on an assignment, loss of credit with a notation on the
(notation reads: "Grade of F assigned for academic
suspension or expulsion from the university.
It is your responsibility to understand what constitutes
dishonesty. For information on the various kinds of
please refer to the Academic Integrity Policy, specifically
The following illustrates only three forms of academic
1. Plagiarism, e.g. the submission of work
that is not one's own or for which other credit has been
obtained. (e.g. submitting a copy of someone else's
writeup for an assignment)
2. Improper collaboration in group work.
(e.g. collaboration between groups in an assignment)
3. Copying or using unauthorized aids in
tests and examinations."