CS 341: Algorithms
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.
||DC 3120, x31755
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
||DC 3136, x31355
Lecture 3: T Th 2:30-3:50, MC 4020
Office hours: Mon Apr 14 and Tues Apr 15 at 4:00-5:30
||Office hour: Fri Apr 12 at 10:00-Noon
||Office hour: Mon Apr 14 at 10:00-Noon
||Office hour: Unavailable
||Office hour: Fri Apr 12 at Noon-2:00pm
||DC 2551D #4
||Office hour: Mon Apr 14 at 2:00-4:00pm
||Office hour: Tues Apr 15 ?
Assignments & Exam Schedule
Make sure to read and fully understand the Assignment Policy.
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 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]|
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.
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
and the lecture slides for section 3 will be posted on Learn
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.
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
- Assignment 1 - due Wednesday January 22 at 3:00pm
- Assignment 2 - due Wednesday February 5 at 3:00pm
- Reading Week - February 17 - 20
- Assignment 3 - due Wednesday February 26 at 3:00pm
- Midterm Exam - Friday February 28 at 6:30-8:00pm
- Assignment 4 - due Wednesday March 19 at 3:00pm
- Assignment 5 - due Friday April 4 at 3:00pm
- Final Exam - scheduled by the Registrars' Office
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.
- Assignments will be due at 3:00 PM on the due date.
- Late submissions will be accepted up to 24 hours after due date.
- There will be a penalty of 15% for accepted late submissions.
- No assistance will be given after the due date.
- You need to notify your instructor before the due date of a severe, long-lasting problem that prevents you from doing an assignment
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
- Divide-and-Conquer Algorithms
- Greedy Algorithms
- Graph Algorithms
- Dynamic Programming Algorithms
- Intractability and Undecidability
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
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.