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

"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
(notation reads:  "Grade of F assigned for academic dishonesty"), and/or
suspension or expulsion from the university.

It is your responsibility to understand what constitutes academic
dishonesty.  For information on the various kinds of academic dishonesty
please refer to the Academic Integrity Policy, specifically Appendix 3,
located at http://www.mcmaster.ca/senate/academic/ac_integrity.htm

The following illustrates only three forms of academic dishonesty:
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."

 
Faculty Notices

"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."