Algorithms
CS 341, Spring 2018

General Information

Instructors
Eric Blais (eblais@uwaterloo.ca)
Office hours: M, 1-2pm, DC 3122

Nathan Harms (nharms@uwaterloo.ca)
Office hours: W, 3-4pm, DC 2128

Eugene Zima (ezima@uwaterloo.ca)
Office hours: T Th, 4-5pm, DC 2127


Lectures
Section 1: T Th, 11:30-12:50, MC 4040, E. Blais
Section 2: T Th, 1:00-2:20, MC 4040, E. Blais
Section 3: T Th, 2:30-3:50, RCH 308, E. Zima
Section 4: T Th, 1:00-2:20, RCH 308, N. Harms

Midterm
Monday, June 18, 7pm-8:50pm
Section 1: STC 0010
Section 2: STC 0020
Section 3: STC 0050
Section 4: STC 0040

Tutorials
Section 101: F, 10:30-11:20, MC 2038
Section 102: F, 11:30-12:20, MC 4042
Section 103: F, 2:30-3:20, MC 4041
Section 104: F, 9:30-10:20, MC 2038
Section 105: F, 12:30-1:20, MC 4060

IAs
Kaleb Alway (kpalway@uwaterloo.ca)
Abhinav Bommireddi (vabommir@uwaterloo.ca)

TAs
Nicole Dillen (nbdillen@uwaterloo.ca)
Kshitij Jain (k22jain@uwaterloo.ca)
Si Chuang Li (sc6li@uwaterloo.ca)
Thomas Lidbetter (t3lidbet@uwaterloo.ca)
Vijay Menon (v3menon@uwaterloo.ca)
Nolan Shaw (n5shaw@uwaterloo.ca)
Bharath Subramanyam (b3subram@uwaterloo.ca)

Office hours
M, 1-2pm, DC 3122 (E. Blais)
T Th, 4-5pm, DC 2127 (E. Zima)
W, 3-4pm, DC 2128 (N. Harms)
F, 1:30-2:30pm, DC 2102 (TAs; on June 22, offic hours will be in DC 3317)
On weeks when assignments are due: F, 3:30-4:30pm, DC 2102 (TAs)

Syllabus
Here.

Piazza page
http://piazza.com/uwaterloo.ca/spring2018/cs341/
All announcements for the class will be posted on the Piazza page. The page will also be the central place for class discussions and for any questions about the lectures and assignments.

Assignments

Assignment 1.
Due on May 18. (LaTex source for solutions to: Q1 Q2 Q3 Q4)

Assignment 2.
Due on June 1. (LaTex source for solutions to: Q1 Q2 Q3 Q4 Q5)

Assignment 3.
Due on June 15. (LaTex source for solutions to: Q1 Q2 Q3 Q4 Q5)

Assignment 4.
Due on July 9. (LaTex source for solutions to: Q1 Q2 Q3 Q4 Q5)

Assignment 5.
Due on July 23. (LaTex source for solutions to: Q1 Q2 Q3 Q4 Q5)


Instructions
Your written solutions will be judged not only for correctness but also for the quality of your presentation and explanations. In questions that involve designing an algorithm, (i) describe the main idea first, (ii) present clearly written pseudocode (e.g., at a level of details mimicking the style of the lectures, the model solutions, or the textbook), (iii) give a correctness proof/argument if it is not immediately obvious, and (iv) include an analysis (usually, of the running time).

Collaboration policy
The work you hand in must be your own. The value of the assignment is in doing it yourself (as you must do on tests and exams). Acknowledge any sources (human or non-human) you have used. You may discuss the assignment questions verbally with others, but you should come away from these discussions with no written or electronic records and you must acknowledge the discussion. If you use an electronic source, again, read it, then close it, then compose your solution and acknowledge your source. Write your solutions in your own words, from your own head. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Submission
Assignments will be submitted as pdf files (each question as a separate pdf). Type your assignments or write legibly. We are using Crowdmark to submit assignments this term. Before the submission deadline (usually the weekend before the deadline), we will send a submission link to your uwaterloo email and make an announcement on piazza. If you didn't get the link or have any question about the submission, you can contact Nicole Dillen (nbdillen@uwaterloo.ca). If you need any help for submitting via Crowdmark, you can find instructions here.

Programming
Some of the assignments will contain programming questions, for which we will provide detailed instructions on how to submit your programs.

Late Policy
Assignments are due at 11:59PM on the due dates. No late submissions will be accepted.

Mark Appeals
All mark appeals (for assignments and midterm) must be made within two weeks of the date of the return (if you pick up your assignment/exam late, your appeal period does not lengthen). Your appeal should be submitted by email to the TA who marked the question. Only if the problem is still unresolved should you then bring the case to the instructor's attention.

Lectures

The lecture notes are available on Learn, where they will be added throughout the term. The specific examples covered in each lecture will vary per section. References to the corresponding sections in the course textbook are included in parentheses

Introduction
Overview of the course, first examples (CLRS §1-2)
Analyzing algorithms
Model of computation, worst-case time complexity, Big-O notations (CLRS §3)
Solving recurrences
Recursion trees, Master theorem (CLRS §4.4-4.5)
Divide and Conquer I
Fast multiplication (CLRS §4)
Divide and Conquer II
Closest pair of points (CLRS §4,33.4)
Greedy Algorithms I
Scheduling problems (CLRS §16)
Greedy Algorithms II
Minimizing lateness. Exchange proofs (CLRS §16)
Dynamic Programming I
Making change, weighted interval scheduling (CLRS §15)
Dynamic Programming II
Longest common subsequences, edit distance (CLRS §15)
Dynamic Programming III
Other examples (CLRS §15)
Introduction to Graph Algorithms
Breadth-first search, testing bipartiteness (CLRS §22)
Depth first search I
Undirected graphs: detecting cycles (CLRS §22)
Depth first search II
Directed graphs (CLRS §22)
Greedy algorithms in graphs I
Minimum spanning trees (CLRS §23)
Greedy algorithms in graphs II
Shortest paths, Dijkstra's algorithm (CLRS §24)
Dynamic programming for shortest paths
Bellman-Ford algorithm, Floyd-Warshall algorithm (CLRS §24,25)
Exhaustive search techniques
Backtracking, branch-and-bound
Introduction to P
Polynomial-time algorithms, reductions (CLRS §34)
NP and NP-completeness
Definition, certificates (CLRS §34)
NP-completeness on graphs
Clique, vertex cover, Independent set, Hamiltonian cycle (CLRS §34)
More NP-completeness
More examples (CLRS §34)
Approximation algorithms
Euclidean TSP, Vertex cover, subset sum (CLRS §35)
Bonus lecture I
Undecidability or other topics
Bonus lecture II
(Instructor's choice)

Site designed with Bootstrap.