CAS
702: Data Structures & Algorithms

Instructor:
George Karakostas

Lectures: Tue 10:30-12:00 PM, Thu 1:00-2:30 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:

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

Student evaluation:

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,
ITB/222)**

** **

Problem sets

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

Lectures: Tue 10:30-12:00 PM, Thu 1:00-2:30 PM. All lectures

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 Bjorner & Ziegler, and Helman et al.
- DP slides
- 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.

Topics

- Binomial heaps, an example of worst-case analysis
(Problem 19-2)

- Amortized analysis (Ch. 17)

- Fibonacci heaps, an example of amortized analysis
(Ch. 19)

- Hash tables, an example of randomized analysis (Ch.
11)

- Greedy algorithms and matroids (Ch. 16)

- Dynamic programming and all-pairs shortest paths (Ch. 15, 25)
- 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)

Student evaluation:

40% Midterm exam

60% Final exam

Problem sets

- 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 1/11)** - 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)**

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