David R. Cheriton School of Computer Science

**March 27**:

- Yaoliang's slides for week 11 and 12 have been posted
- Semih's slides for week 12 have been posted

**March 18**:

- Yaoliang's slides for week 10 have been posted
- Semih's slides for week 11 have been posted

**March 14**:

- Assignment 5 is now available. It is due April 3
- Semih's slides for week 10 have been posted

**March 10**:

- Yaoliang's office hours info has been updated
- Slides for week 9 have been updated

**March 07**:

- Lecture topics for week 9 have been posted
- Yaoliang's slides for lecture 16 are now available
- Semih's slides for week 9 are now available

**February 28**:

- Yaoliang's slides for lecture 14 are now available
- Semih's slides for week 8 are now available

**February 20**:

- Assignments
**due dates have been updated** - Assignment 4 is now available. It is due March 14. (See assignments section)
- Sample midterm is available (See credit section)

**February 16**:

- Yaoliang's slides for lecture 11 have been posted
- Yaoliang's slides for lecture 10 have been updated
- Semih's slides for lecture 13 and 14 have been updated

**February 13**:

- Lecture topics for week 6 have been posted
- Semih's slides for lecture 13 and 14 are now available

**February 10**:

- Yaoliang's slides for week 6 have been posted

**February 06**:

- Lecture topics for week 6 have been posted
- Semih's slides for lecture 11 and 12 are now available

**February 04**:

- tex file for assignment 3 is now available

**February 03**:

- Assignment 3 is now available. It is due Feb 17. (See assignments section)
- Yaoliang's slides for weeks 4 and 5 have been posted

**January 28**:

- Lecture topics for week 5 have been posted
- Semih's slides for lecture 10 are now available

**January 20**:

- Assignment 2 is now available. It is due Feb 3
- Semih's slides for lecture 6 have been updated
- Lecture topics for week 4 have been posted

**January 18**:
Yaoliang's slides for week 3 are now available.

**January 17**:

- TA office hours have been updated.
- Corrected version of slide 77 has been posted (Doug)

**January 13**:

- Yaoliang's slides for week 2 are now available
- Lecture topics for week 3 have been posted
- Semih's slides for week 3 are now available

**January 10**:
Lecture topics for week 2 have been posted.

**January 09**:
LaTeX file for assignment 1 is available.(See assignments section)

**January 06**:
Assignment 1 is now available. It is due Jan 20. (See assignments section)

**January 04**:
Piazza will be used for all
course discussions.

- Calendar Description - Official course description from academic calendar.
- Handbook Description - Longer course description from Computer Science Undergraduate Handbook.

**Instructors:**

Douglas Stinson, DC 3522, x35590, dstinson "at" uwaterloo.ca

Office hours: Thursdays, DC 3522, 01:30-02:30 p.m.

Semih Salihoglu, DC 3351, x37522, semih.salihoglu "at" uwaterloo.ca

Office hours: Wednesdays, DC 3351, 11:00-12:00 p.m.

Yaoliang Yu, DC 3617, yaoliang.yu "at" uwaterloo.ca

Office hours: Tuesdays, DC 3617, 10:00-11:00 a.m.

**Time and Place:**

- Section 1: Tuesday & Thursday, 02:30 - 03:50 p.m., MC 2034, (Semih)
- Section 2: Tuesday & Thursday, 10:00 - 11:20 a.m., RCH 207, (Douglas)
- Section 3: Tuesday & Thursday, 04:00 - 05:20 p.m., MC 2034, (Semih)
- Section 4: Tuesday & Thursday, 08:30 - 09:50 a.m., RCH 207, (Douglas)
- Section 5: Tuesday & Thursday, 08:30 - 09:50 a.m., MC 4040, (Yaoliang)

- Aayush Rajasekaran (arajasekaran "at" uwaterloo.ca)

- Dimitrios Skrepetos (dskrepet "at" uwaterloo.ca)

- Jian Li (j493li "at" uwaterloo.ca)

- Jose Serna (jserna "at" uwaterloo.ca)

- Shayan Hassantabar (ss3hassa "at" uwaterloo.ca)

- Shikha Mahajan (s7mahaja "at" uwaterloo.ca)

- Woojung Kim (w3kim "at" uwaterloo.ca)

*TA Office hours* will be in DC2102 the following dates:

- Tuesday 3:00 - 4:00 p.m.
- Wednesday 3:00 - 4:00 p.m.
- Thursday 2:00 - 3:00 p.m.

- Assignments 25% -- see dates below.
- Midterm 25% (sample) -- March 02 (thursday), 7:00-8:50 p.m., STC 1012/AHS 1689.

- Final Exam 50% -- TBA.

- Douglas' slides: 1up, 2up, slide 77
- Semihs' slides: Will be posted weekly (see below)
- Yaoliangs' slides: Will be posted weekly (see below)

**Week 1: Introduction**

Tuesday (Jan 3): Administrivia, Overview, Divide & Concur Example: Merge Sort. (Semih's slides: pptx, pdf. Yaoliang's slides: pdf)

Thursday (Jan 5): Asymptotic Notation: For reading Assign CLRS 3.1, 3.2. (Semih's slides: pptx, pdf. Yaoliang's slides: pdf)**Week 2: Assymptotic Notation and Recurrences**

Tuesday (Jan 10): Asymptotic Notation and Summations: Reading CLRS 3.1, 3.2. (Yaoliang's slides: pdf)

Thursday (Jan 12): Recurrences & Master Theorem: Reading 4.3-4.5 (optional 4.6). (Yaoliang's slides: pdf)**Week 3: Divide & Conquer**

Tuesday (Jan 17): Divide & Conquer 1: CLRS 3.2, 33.4, D&C handout 2.1. (Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (Jan 19): Divide & Conquer 2: CLRS 3.2, 33.4, D&C handout 2.1. (Semih's slides: pptx,Yaoliang's slides: pdf)**Week 4: Greedy Algorithms**

Tuesday (Jan 24): Greedy Algorithms 1: CLRS 16.1-16.2.*Semih and Doug will finish Divide & Conquer*(Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (Jan 26): Greedy Algorithms 2: CLRS 16.1-16.2. (Semih's slides: pptx,Yaoliang's slides: pdf)**Week 5: Greedy Algorithms**

Tuesday (Jan 31): Greedy Algorithms 3: CLRS 16.1-16.2. (Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (Feb 2): Greedy Algorithms 4: CLRS 16.1-16.2. (Semih's slides: pptx, Yaoliang's slides: pdf)**Week 6: Dinamic Programming**

Tuesday (Feb 7): Dynamic Programming 1: (CLRS 15.1-15.3).*Semih will finish Stable Marriage*. (Semih's slides: pptx, Yaoliang's slides: pdf)

Tuesday (Feb 9): Dynamic Programming 2: (CLRS 15.4-15.5). (Semih's slides: pptx, Yaoliang's slides: pdf)**Week 7: Dinamic Programming - Graph Algorithms**

Tuesday (Feb 14): Dynamic Programming 3.*Doug will start with Graph algorithms*. (Semih's slides: pptx, Yaoliang's slides: pdf)

Tuesday (Feb 16): Graph Algorithms 1: CLRS 22.1-22.3.*Semih will take the first half to finish Dynamic Programming*. (Semih's slides: pptx)**Week 8: Graph Algorithms**

Tuesday (Feb 28): Graph Algorithms: CLRS 22.1-22.5. (Semih's slides: pptx, Yaoliang's slides: pdf )

Thursday (March 02): Graph Algorithms: CLRS 22.1-22.5. (Semih's slides: pptx)**Week 9: Graph Algorithms**

Tuesday (March 07): Graph Algorithms 4: CLRS 23.1-23.2. (Semih's slides: part 1 - part 2 - doug's section, Yaoliang's slides: pdf )

Thursday (March 09): Graph Algorithms 5. CLRS 23.1-23.2.*Some sections will start 24.1-24.3*. (Semih's slides: part 1 - part 2 - doug's section, Yaoliang's slides: pdf)**Week 10: Graph Algorithms - Intractability**

Tuesday (March 14th): Graph Algorithms 6.*Doug and Yaoliang might start Intractability*: CLRS 25.1-25.2, CLRS 34.1-34.2. (Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (March 16th): Intractability 1. CLRS 34.1-34.2 (Semih's slides: pptx, Yaoliang's slides: pdf)**Week 11: Intractability**

Tuesday (March 21): Intractability 2: CLRS 34.3-34.4. (Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (March 23): Intractability 3. (Semih's slides: pptx, Yaoliang's slides: pdf)**Week 12: Intractability**

Tuesday (March 28): Intractability 4: CLRS 34.3-34.4. (Semih's slides: pptx, Yaoliang's slides: pdf)

Thursday (March 30): Intractability 5.

- Assignment 1 (pdf, tex): due Friday Jan. 20
- Assignment 2 (pdf, tex): due Friday Feb. 3
- Assignment 3 (pdf, tex): due Friday Feb. 17
- Assignment 4 (pdf, tex): due Tuesday March 14
- Assignment 5 (pdf, tex): due Monday April 3

Assignments will be submitted as pdf files in LEARN. In LEARN you will upload your assignments to the specific dropbox for the assignment. Please type your assignments or write legibly. Please use a * cover page*. Put your full name and ID number on this first page.

As per the collaboration policy, you must indicate on your assignments any assistance you received.

Assignments are due at noon. So the dropbox on LEARN will close at that time.

Your appeal should be submitted to the TA who marked the question in writing. Only if the problem is still unresolved should you then bring the case to the instructor's attention

Remember that, you are responsible for understanding and being able to explain all of the statements in your homeworks and exam solutions. Most importantly, the solutions must be **written up independently** of the other students.

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