CAS 702: Data Structures & Algorithms

Instructor:   George Karakostas

Lectures:   Tue 12:30-2:00 PM, Thu 12:30-2:00 PM. All lectures in ITB/222

Office hours:  By appointment

Textbook:  "Introduction to Algorithms", 3rd Ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.

Study material:
• 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 Björner & Ziegler, and Helman et al.
• DP slides
• A very nice recent survey on Max Flow here.
Course description:

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.

Topics
1. Binomial heaps, an example of worst-case analysis (Problem 19-2)
2. Amortized analysis (Ch. 17)
3. Fibonacci heaps, an example of amortized analysis (Ch. 19)
4. Hash tables, an example of randomized analysis (Ch. 11)
5. Greedy algorithms and matroids (Ch. 16)
6. Dynamic programming and all-pairs shortest paths (Ch. 15, 25)
7. Maximum flow (Ch. 26)
8. Linear Programming and Duality (Ch. 29)
9. Primal-Dual schema as an algorithmic design tool
10.  NP-completeness (Ch. 34)
11. Approximation algorithms (Ch. 35)

Student evaluation:

40% Midterm exam

60% Final exam

Problem sets
TBA

McMaster Course Policies

"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
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 transcript
suspension or expulsion from the university.

dishonesty.  For information on the various kinds of academic dishonesty