David R. Cheriton School of Computer Science

- General Policies
- Programming Guidelines
- Calendar Description - Official course description from academic calendar.
- Handbook Description - Longer course description from Computer Science Undergraduate Handbook.

**Instructors:**

Mark Petrick, DC 3109, x31755, mdtpetri "at" uwaterloo "dot" ca

Office hours: Wednesday and Friday 11:30am - 12:30 PM, or by appointment

**Time and Place:**

- Section 1: Wednesdays & Fridays, 8:30 AM - 9:50 AM, MC 2017
- Section 2: Wednesdays & Fridays, 10:00 AM - 11:20 AM, MC 4045

- Hicham El-Zein. helzein "at" uwaterloo "dot" ca. Office: TBA.

- Honghao Fu. h7fu "at" uwaterloo "dot" ca. Office: TBA.

- Vijay Menon. v3menon "at" uwaterloo "dot" ca. Office: TBA.

- Vijay Subramanya. v7subram "at" uwaterloo "dot" ca. Office: TBA.

**Credit:**

- Assignments 30% -- see dates below.
- Midterm 25% -- Friday, June 19, 2015, 6:30 PM - 8:00 PM

in MC 2065 and MC 2066. - Final Exam 45% -- To be scheduled by the Registrar's Office
**Note:**In order to pass CS 341, students are required to pass the combined portion of the midterm + final; i.e. get 35 or more out of the 70 possible marks available.

**Introduction**- Lecture 01 - 2015-05-06: Maximum, Max-and-Min, 3SUM, introduction to algorithm analysis.
- Lecture 02 - 2015-05-08: Asymptotic (order) notation, summation formulas.
- Lecture 03 - 2015-05-13: Growth of functions, loop analysis, recurrences.
- Lecture 04 - 2015-05-15: Solving recurrences, recurrence trees, the Master Theorem, the guess-and-check method.

**Divide and Conquer**- Lecture 05 - 2015-05-20: Divide and conquer algorithms. The maxima problem.
- Lecture 06 - 2015-05-22: The closest-pair problem and Shamos' algorithm. Integer multiplication and Karatsuba's algorithm.
- Lecture 07 - 2015-05-27: Matrix multiplication and Strassen's algorithm.
- Lecture 08 - 2015-05-29: The selection problem. Randomized and deterministic linear-time algorithms for selection.

**Greedy Algorithms**- Lecture 09 - 2015-06-03: Interval selection. Interval colouring
- Lecture 10 - 2015-06-05: Fractional knapsack problem.
- Lecture 11 - 2015-06-10: Stable marriage problem. Coin changing problem.

**Dynamic Programming**- Lecture 12 - 2015-06-12: The combinatorial choose function OR the Fibonacci sequence. A DP solution to the coin changing problem. Solving DP by memoization.
- Lecture 13 - 2015-06-17: Longest-common subsequence. The 0-1 Knapsack problem. Minimum-length triangulation. Solving DP via memoization

**Graph Algorithms**- Lecture 14 - 2015-06-19: Overview of graphs. Adjacency matrix and adjacency list representations.
- Lecture 15 - 2015-06-24: Breadth-first search (BFS) and depth-first search (DFS).
- Lecture 16 - 2015-06-26: Applications of BFS and DFS. Bipartiteness. Shortest unweighted path from a fixed vertex. Topological sort.
- Lecture 17 - 2015-07-03: Sharir's algorithm for strongly connected components. Minimum spanning trees (MSTs) and Kruskal's algorithm.
- Lecture 18 - 2015-07-08: Prim's algorithm for MST.
- Lecture 19 - 2015-07-10: Single-source shortest paths. An algorithm for single-source shortest paths in DAGs. Dijkstra's algorithm.
- Lecture 20 - 2015-07-15: 3 dynamic-programming methods for computing all-pairs shortest paths, including the Floyd-Warshall algorithm.

**NP-Completeness**- Lecture 21 - 2015-07-17: Decision problems. P and NP decision problem classes. Certificates and verification. P vs NP conjecture.
- Lecture 22 - 2015-07-22: NP-Complete, NP-Hard classes. Vertex cover. Satisfiability (SAT). Cook's Theorem. Polynomial-time reductions.
- Lecture 23 - 2015-07-24: 3CNF-Satisfiability (3SAT) problem. Independent Set problem. The clique problem.
- Lecture 24 - 2015-07-28: Undecidability and the halting problem.

**Where to get your marked assignment**

Assignments will be handed back in the section you wrote down on your assignment. You will also be able to collect your assignments during the office hours of the lecturer of your registerd section.

**How to appeal marks**

After assignments have been handed back to students in class, you have two weeks to appeal you mark. You must first consult the TA who marked the question. (see Piazza postings for whom). Only if the problem is still unresolved should you then bring the case to the instructor's attention.

**Tentative dates:**

- Assignment 1 (PDF) -- Available Mon May 11. Due Thurs May 21 at 3 PM.

Assignment 1 (Latex)

Assignment 1 Cover Sheet - Assignment 2 (PDF) -- Available Mon May 25. Due Thurs June 4 at 3 PM.

Assignment 2 (Latex)

Assignment 2 Cover Sheet

Sample Math Induction Proof - Assignment 3 (PDF) -- Available Mon June 8. Due Thurs June 18 at 3 PM.

Assignment 3 (Latex)

Assignment 3 Cover Sheet

- Assignment 4 -- Available Mon July 6. Due Thurs July 16 at 3 PM.

- Assignment 5 -- Available Fri July 17. Due Tues July 28 at 3 PM.

CLRS is available in the Davis Centre Library Reserves, as well as the following textbooks:

- [DPV] Dasgupta, Papadimitriou, and Vazirani,
*Algorithms*(QA9.58 .D37 2008); - [KT] Kleinberg and Tardos,
*Algorithm Design*(QA76.9.A43K54 2006); - [BB] Brassard and Bratley,
*Fundamentals of Algorithmics*(QA9.58.B73 1996); - [GJ] Garey and Johnson,
*Computers and Intractability: A Guide to the Theory of NP-Completeness*(QA76.6.G35 1979).

**Introduction**- Introduction to algorithms and algorithm analysis: 1, 2
- Order notation: 3
- Recurrences: 4.3, 4.4, 4.5, (4.6)
- Find-Min-And-Max: Problem: 9.1

**Divide and Conquer**- Overview: Section 4
- Matrix Multiplication: 4.2
- Closest pair problem: 33.4
- Selection problem: 9.2, 9.3

**Greedy Algorithms**- Overview: Section 16

**Dynamic Programming**- Overview: 15
- Memoization: 15.3
- Longest common subsequence: 15.4

**Graph Algorithms**- Overview of graphs: B.4
- Graph representations: 22.1
- BFS: 22.2
- DFS: 22.3
- Topological Sort: 22.4
- Strongly Connected Components: 22.5
- Minimum spanning trees: 23
- Kruskal's algorithm and Prim's algorithm: 23.2
- Single-source shortest paths: 24
- Single-source shortest paths algorithm for DAGs: 24.2
- Dijkstra's algorithm: 24.3
- All-pairs shortest parts: 25
- Floyd-Warshall algorithm: 25.2

**Theory of NP Completeness**- Overview: 34
- P: 34.1
- NP: 34.2
- NP-completeness, NP-hardness, and reductions: 34.3
- SAT, 3-CNF-SAT: 34.4
- clique, vertex-cover, Hamiltonian cycle, traveling-salesman, and subset-sum problems: 34.5

The following is a set of lecture slides (by Douglas R. Stinson) used in the previous term and offered here as a resourse for students.
We will loosely follow these slides but will also present different approaches and alternate algorithms, etc. At times we may follow the slides closely but others we may skip completely.
**The lecture slides are not a substitute for attending lecture or taking notes from board presentation.**

- Introduction
- Divide and Conquer Algorithms
- Greedy Algorithms
- Dynamic Programming
- Graph Algorithms
- NP-Completeness and Undecidability

- 2015-01-07: A proof that MIN-MAX requires 3n/2-2 comparisions: link.
- 2015-01-09: A probabilistic O(n^2 (loglog n)^2/ log n) 3SUM algorithm: link.
- 2015-01-30: The Blum-Floyd-Pratt-Rivest-Tarjan selection algorithm: link. This is behind a pay-wall. You can access it via internet at the University of Waterloo.
- 2015-02-25: Notes on min-length triangulation: link.
- 2015-04-01: tree of NP-complete problems connected by polynomial time reductions: link (Source).