CS 341: Algorithms Spring 2020



This course studies the major algorithmic design paradigms and mathematical tools for analyzing the running times of algorithms and detecting computational problems for which no efficient deterministic algorithm. Topics include: basics of analysis of algorithms; general algorithmic paradigms: (i) divide and conquer; (ii) greedy algorithms; (iii) dynamic programming; and (iv) graph algorithms; NP-completeness and its implications; and undecidability.
The course material includes:

Calendar description
Official course description from the course calendar
Handbook description
Longer course description from the Computer Science Undergraduate Handbook



Tuesday and Thursday from 11am-12:30pm online through Zoom. See Piazza announcements for more information. Recorded lecture videos are available on Learn for viewing any day/time.
We are not following the text exactly but we will suggest readings from the text book CLRS. This is an excellent text book and we highly recommended doing the suggested readings to supplement the lecture material. Below are the suggested readings, lecture notes from the recorded videos, and slides. We often do not use slides in lecture videos and instead provide them as an alternative set of notes.

    Date Topics Notes Slides Readings
Week 1 L1 May 12 Introduction and Overview of Topics PDF
PDF, PPT CLRS Ch. 1
L2 May 14 Analyzing Algorithms, Introduction to Divide-and-Conquer Algorithms, MergeSort PDF PDF, PPT
CLRS Ch. 2.2
Week 2 L3 May 19 Asymptotic notation, growths of runtime functions, and important summation PDF --- CLRS Ch. 3
L4 May 21 Mathematical tools for Analyzing Divide and Conquer Algorithms, Recursion Tree and Substitution Methods, Recurrences and the Master Theorem PDF --- CLRS Ch. 4.3-4.5 (Optional 4.6)
Week 3 L5 May 26 2-D Maxima & Closest Pair PDF PDF, PPT CLRS Ch. 33.4
L6 May 28 Integer Multiplication & Strassen's Matrix Multiplication PDF PDF, PPT CLRS Ch 4.2
Week 4 L7-8 June 2, 4 Greedy Algorithms 1 & 2: Activity Selection and Scheduling PDF (L7), PDF (L8) PDF, PPT CLRS Ch. 16.1-16.2
Week 5 L9 June 9 Greedy Algorithms 3: Stable Matching PDF PDF, PPT
L10 June 11 Dynamic Programming 1 PDF PDF, PPT CLRS Ch 15.1-15.3
Week 6 L11 June 16 Dynamic Programming 2: Weighted Activity Selection and Sequence Alignment PDF PDF, PPT CLRS 15.4, 15.5
L12 June 18 Dynamic Programming 3: Matrix Multiplication Order, 0/1 Integer Weight Knapsack PDF PDF, PPT CLRS 15.4-15.5
Week 7 L13 June 23 Dynamic Programming 5: 0/1 Integer Knapsack and Intro to Graphs PDF PDF, PPT CLRS 22.1-22.3
L14 June 25 BFS/DFS/Connectivity/Topological Sort --- PDF, PPT CLRS 22.1-22.3
Week 8 L15 June 30 Topological Sort, SCC --- PDF, PPT CLRS 22.4, 22.5
L16 July 2 Minimum Spanning Tree PDF PDF, PPT CLRS 23.1, 23.2
Week 9-10 L17 July 7 MST PDF (same as L16) --- CLRS 23.1, 23.2
L18, 19, 20 July 9, 14, 16 Kruskal's Algorithm and Shortest Paths PDF (L18), PDF (L19-L20) PDF, PPT CLRS 24.1-24.3, 25.1-25.2
Week 11-12 L21 July 21 Intractability 1: Introduction to Theory of NP-Completeness PDF PDF, PPT CLRS 34.1-34.2
L22, 23 July 23, 28 Intractability 2: Reductions PDF (L22),PDF (L23) PDF, PPT CLRS 34.3-34.4
Week 12 L24 July 30 Intractability 3: Undecidability PDF PDF, PPT CLRS 34.1-34.2


Hand in a PDF file with your solutions via CrowdMark. We encourage you to prepare your solutions using LaTeX but you can use other software or submit handwritten assignments as long as they are legible. We have the right to take marks off for illegible answers.

When the CrowdMark instance is ready, all students enrolled in the class will receive an email with a link to their individual submission site. In order to submit, upload a separate PDF file (multiple pages are allowed) to each question. You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.com/help/completing-and-submitting-an-assignment/.)

Marmoset will be used for the programming questions, and is available at https://marmoset.student.cs.uwaterloo.ca.

Assignments will be handed out and due as follows (dates are tentative and may change):

Assignment Number Due (midnight EST) Hand In Via Markers Solutions
1.1
PDF, LaTeX
May 24 CrowdMark Q1: Utsav
Q2: Catherine
Q3: Krishna
Q4: Mahdi
See A1.1 solution sketch under "Assignments" in Learn.
1.2
PDF, LaTeX
May 31 CrowdMark Q1: Vikash
Q2: Krishna
Q3: Utsav
Q4: Catherine
See A1.2 solution sketch under "Assignments" in Learn.
2
PDF, LaTeX, PNG files
June 21 CrowdMark Q1: Catherine
Q2: Mahdi
Q3 (a, b, c): Vijay
Q4 (a, b): Stavros
Q5: Vikash
See A2 solution sketch under "Assignments" in Learn.
3
PDF, LaTeX
July 1 CrowdMark and Marmoset Q1 (Programming): Stavros
Q2 (a, b, c): Krishna
Q3: Mahdi
Q4: Utsav
See A3 solution sketch under "Assignments" in Learn.
4
PDF, LaTeX
July 12 CrowdMark Q1: Mahdi
Q2: Vikash
Q3: Utsav
Q4: Catherine
Q5: Krishna
See A4 solution sketch under "Assignments" in Learn.
5
PDF, LaTeX, PNG file
July 22 CrowdMark Q1: Krishna
Q2 (a, b, c): Catherine
Q2 (d, e, f): Stavros
Q3 (a, b): Vikash
Q3 (c): Utsav
Q4 (a, b): Vijay
See A5 solution sketch under "Assignments" in Learn.
6
PDF, LaTeX, JPG file
July 31 CrowdMark Q1: Stavros
Q2 (a): Mahdi
Q2 (b, c): Utsav
Q3 (a): Vijay
Q3 (b): Utsav
Q4: Vikash
See A6 solution sketch under "Assignments" in Learn.
7
PDF, LaTeX
August 13 CrowdMark

Instructions for Assignments: 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). In all assignments, unless otherwise directed, you are expected to justify any claims that you make. The level of explanation we generally expect is "enough to convince a skeptical TA". Usually this means that a complete formal proof from first principles is not needed (unless we say so). Furthermore, since this course is essentially all about efficient use of time and space, strive to make your solutions as efficient as possible. Solutions that are technically correct, but extremely wasteful in terms of time and space, will not receive full credit.

Collaboration Policy: The work you hand in must be your own. Unless specified otherwise, you can always use any result from the textbook, notes, or previous assignment just by citing it. 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. Acknowledge any sources you have used. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Late Policy: Late assignments will not be accepted and no extensions will be granted under any circumstances. Solutions will be posted almost immediately online on Learn.

Programming Questions: There will be several assignments that contain a programming question, where we ask you to code an algorithm. However, this is not a software engineering course. We will not test your code for trivial edge cases (such as the case of empty input), or inputs that do not match our specifications. However, your program should take care of the edge cases that are crucial to the algorithm's correctness or analysis. For example, unless the problem states so, you should not usually assume that the input size is a power of 2. We will send out detailed instructions about how to submit programming questions.



We will use Piazza for all course announcements and as a forum for students to ask and answer questions. So you should enroll yourself at your earliest convenience. During Piazza discussions, please do not reveal the solutions to the assignments by requesting or offering detailed advice. We'll delete comments that reveal too much. Violations can result in academic sanctions.

Similarly, do not solicit hints or provide hints about how to solve the homework problems on other bulletin boards, such as Facebook. Violations can result in academic sanctions.

Piazza is not the place to dispute how assignments are marked. If you have a complaint, please follow the process given below.



Instructor Email (at school name dot ca) Office Hours
Semih Salihoglu ssalihog Tue: 1-2pm and Th: 8-9pm through Zoom. See Piazza announcements for Zoom links.

Teaching assistant Email (at school name dot ca)
Vikash Balasubramanian v9balasu
Stavros Birmpilis sbirmpil
Utsav Tushar Das utdas
Vijay Menon v3menon
Mahdi Ramezani m7rameza
Catherine St-Pierre c2stpier
Krishna Teja Reddy Vemula ktrvemul

TA Office hours

We plan to hold 2 TA Office Hours per week through Zoom. See Piazza announcements for Zoom links.

Instructional support coordinator Email (at school name dot ca)
Caroline Kierstead caroline.kierstead

Mark breakdown

The mark is based on 7 assignments (percentage of each will roughly be between 14-16%).

Points of contact for common questions

Note: If you decide to e-mail the course staff, you must use your uwaterloo Quest e-mail account (WatIAM/Quest userID @uwaterloo.ca); otherwise we cannot verify who you are and are limited on what we can accept and respond to.

Help Topic Contact
Assignment, Missed Deadline: We do not accept late or emailed assignments. The last files submitted before the deadline will be marked (submit early and often, even if not finished).
If the deadline is missed due to illness or other valid, verifiable reason, see Missed Work Due To Illness below.
Assignment Marking Error: Re-mark request, due within one week of release of marks on CrowdMark/Marmoset. Contact the TA who marked the specific question and submit a written request. See TAs for contact information.
Assignment Recording Error: Grades will be made available through https://www.student.cs.uwaterloo.ca/~cs341/cgi-bin/displayMarks.cgi. If you notice an error in the recorded value, please contact Caroline Kierstead (CS 341 ISC).
Course Website Error: Email CS341 course account
Handouts Error: Instructors - email or check consulting hours listed at Instructors
Enrollment: If Quest won't let you enroll or switch LEC or TUT sections without a permission/override number: Instructors and course staff are unable to help you—you must see a CS academic advisor.
General Course Help: TA office hours or instructor office hours.
Lecture Questions: TA office hours or instructor office hours.
Missed Work Due To Illness/Valid, Verifiable Reason (Assignments, Exams): Assignments, midterms, final exam: Validation required (see Verification of Illness Services at https://uwaterloo.ca/campus-wellness/health-services/student-medical-clinic but substitute Caroline Kierstead (CS 341 ISC) for references to instructor. Make sure you also read the Math Faculty document on the consequences of submitting a VIF.
AccessAbility Services (AAS) exam accommodation forms (request to write at AAS): Submit to AAS at least 3 weeks before exam


Textbook: [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 (QA76.6 .C662 2009).

This book is available electronically through the UW library catalog.

Additional reference: [DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available here.

Additional books:

The following resource is also useful for the course but more importantly for technical interviews you may have:



Plagiarism

Plagiarism is a very serious academic offence and is penalized accordingly. When you plagiarize you damage the learning experience for yourself and others. To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use. If you work with others, only discuss general aspects of the course material, not specific solutions. Write up the solutions yourself, not in groups.

Mental Health Resources

Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.

On-campus Resources

Off-campus Resources

Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

University Policies (University required text)

Academic Integrity:
In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website ( http://www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in - and out - of the classroom.

Grievance:
A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm .

Discipline:
A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.

Avoiding Academic Offenses:
Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, https://uwaterloo.ca/math/current-undergraduates/regulations-and-procedures/cheating-and-student-academic-discipline-guidelines.

MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.

Discipline cases involving any automated marking system such as Marmoset include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.

Appeals:
A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm .

Course Outline
According to UW rules, we must also point you to this course outline, although most of the information included in it is already repeated above.