David R. Cheriton School of Computer Science

**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 3602, yaoliang.yu "at" uwaterloo.ca

Office hours: Tuesdays, DC 3602, 10:00-10: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% -- 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)

- Assignment 1 (pdf, tex): due Friday Jan. 20
- Assignment 2: due Friday Feb. 3
- Assignment 3: due Friday Feb. 17
- Assignment 4: due Friday March 10
- Assignment 5: due Friday March 31

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