CS 341: Algorithms
Winter 2014


Mon March 24: Assignment 5 posted
Thurs March 13: Updated Alt_0-1Knapsack.pdf - typo: mixed up > and <
Wed Feb 12: Assignment 3 posted - download assignment files below
Fri Jan 24: Assignment 2 posted - download assignment file and cover sheet below.
Tues Jan 21: Assignment Policy - Please read the Assignment Policy
Mon Jan 13: Assignment 1 posted - download assignment file and cover sheet below.
Piazza is now available. Please read the Piazza Usage Guidelines to avoid any violations of academic integrity.
Course Staff & Office Hours

Office hours will begin at the second week of the semester.

Mark Petrick DC 3120, x31755 mdtpetri@uwaterloo.ca
Lecture 1: T Th 10:00-11:20, MC 2038
Lecture 2: T Th 1:00-2:20, MC 2054
Office hours:Wed Apr 9 at 10:00-1:00 and Tues Apr 15 at 11:30-1:00

Kevin Lanctot DC 3136, x31355 klanctot@uwaterloo.ca
Lecture 3: T Th 2:30-3:50, MC 4020
Office hours: Mon Apr 14 and Tues Apr 15 at 4:00-5:30

Teaching Assistants:
Hicham El-Zein DC 2569 Office hour: Fri Apr 12 at 10:00-Noon
Stephen Kiazyk DC 2569 Office hour: Mon Apr 14 at 10:00-Noon
Neeraj Kumar DC 2531 Office hour: Unavailable
Ankit Pat DC 3562 Office hour: Fri Apr 12 at Noon-2:00pm
Prashant Raghav DC 2551D #4 Office hour: Mon Apr 14 at 2:00-4:00pm
Jenny Wang DC 2581 Office hour: Tues Apr 15 ?

Assignments & Exam Schedule

Make sure to read and fully understand the Assignment Policy.

EventFiles to DownloadDue DateSolution
Assignment 1 A1-Questions (PDF)
A1-Questions (LaTex)
Wednesday January 22 at 3:00pmA1 Solutions
Assignment 2A2-Questions (PDF)
A2-Questions (LaTex)
Wednesday February 5 at 3:00pmA2 Solutions
Reading WeekHave a good break!February 17 - 20Welcome back!
Assignment 3 A3-Questions (PDF)
A3-Questions (LaTex)
Wednesday February 26 at 3:00pmA3 Solutions
Midterm ExamFriday Feb 28 at 6:30-8:00pm in DC1350 (lastname A-L), 1351 (lastname M-Z)Solutions available on LEARN
Assignment 4 A4-Questions (PDF)
Mon March 24 at 3:00pm - NO LATES ACCEPTED!A4 Solutions
Assignment 5 A5-Questions (PDF)
A5-Questions (LaTex)
Friday April 4 at 3:00pmA5 Solutions
Final ExamWednesday April 16 at 12:30-3:00pm in PAC 7,8,9Good Luck

The assignment late policy is detailed below.

Textbook Readings - from [CLRS 2009]

The course slides are available here (in both 1up and 3up): http://www.student.cs.uwaterloo.ca/~cs341/slides.

There are also some supplemental notes and proofs here: https://www.student.cs.uwaterloo.ca/~cs341/supp.

Week      Readings
Week 1:Section 2.1 (loop invariants), Chapter 3, Appendix A, C2 and C3
Week 2:Sections 2.2, 2.3, 4.4, 4.5, 4.6
Week 3:Sections 4.2, 33.4
Week 4:Sections 9.2, 9.3, 16.1
Week 5:Material not in [CLRS 2009]
Week 6:Sections 22.1, 22 and some material not in [CLRS 2009]
Week 7:Sections 22.3, 22.4, 22.5
Week 8:Chapters 23 and Section 24.3
Week 9:Section 15.3 (design strategy), 15.4 (LCS) and some material not in [CLRS 2009]

Course Information

Course Description

The objective of this course is to study efficient algorithms, effective algorithm design techniques and approaches to handling situations in which no feasible algorithms are known. The course is intended to give the student experience in program design and to emphasize both pragmatic and mathematical aspects of program efficiency.

Course Text

The lectures will mostly be covering material from Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest and Stein, MIT Press, 2009.

Posting Lecture Slides and Course Information

The lectures slides for sections 1 and 2 will be posted on the course web site at http://www.student.cs.uwaterloo.ca/~cs341/slides and the lecture slides for section 3 will be posted on Learn at https://learn.uwaterloo.ca. The course syllabus, assignments and assignment solutions will be available on both platforms.
The course syllabus is here: cs341-syllabusW14.pdf.

Announcements and discussions about the course material or assignments will take place on Piazza (piazza.com). Please read the Piazza Usage Guidelines to avoid any violations of academic integrity.

Course requirements

Open to Computer Science students only.
Prerequisites: CS 240 and (CS 245 or SE 112/212) and MATH 239/249
Anti-requisites: SE 240, SYDE 423


Assignments  30% - a mixture of programming and written solutions to problems
Midterm Exam  25%
Final Exam  45%

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.

Schedule of Midterm and Assignment Due Dates

Submitting Assignments

Assignments are due at 3:00PM and are to be placed in the CS341 assignment box located on the 4th floor in the Math building across from the Tutorial Centre, MC4065.

Late Assignments

No Makeup

There will be no deferred/makeup midterm exam. Under extenuating circumstances that are pre-approved, where a student is unable to write the mid-term, the instructor will assign a higher weight to student.s final exam.

Major Topics covered in this course

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 (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.


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.


A student is expected to know what constitutes academic integrity, to avoid committing academic offences, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (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 offences and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.

Avoiding Academic Offences:

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 offences and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml.


A student may appeal the finding 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.