CS341 Home Page
CS 341 (CM 339) Algorithms, Winter, 2011
- Ming Li
- Office: DC 3355
- Phone: x84659
- E-mail: mli at uwaterloo dot ca
- Office Hours: Tuesdays & Thursdays, 4:00 -- 6:00 PM (or
just drop by in the afternoons.)
Time and Place:
- Section 1: Tuesdays & Thursdays: 2:30-3:50pm, MC 2038
- Section 2: Tuesdays & Thursdays: 1:00-2:20pm, MC 2038
- 5 assignments at 10% each.
- Midterm Exam 20%, Feb 17, 7-9pm. Rooms: MC4020 (go to this room
if your student id is 0 mod 3)/4021 (student id = 1 mod 3)/4045
(student id = 2 mod 3). For those who have conflicts and would
be taking the exam 5-7pm, please go to MC2036.
Solutions and marking scheme
for the midterm exam.
- Final Exam 30%
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms
(3rd ed. any edition will work), MIT Press, 2009.
Available in the DC library, 3-hour
reserve, QA76.6.C662 2009. The second edition can be read
(click "online resource"). If that link doesn't work for you, try
- Additional Reference: Dasgupta, Papadimitriou, Vazirani,
- Additional Books: Kleinberg and Tardos, Algorithm Design
Brassard and Bratley, Fundamentals of Algorithmics (QA9.58.B73 1996)
Garey and Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness (QA76.6.G35 1979)
- Soroush Hosseini Alamdari, DC2503, x37729,
s26hosse at uwaterloo dot ca,
Office Hours: (Soroush is responsible for marking Assignment 2).
Tu Jan 25 9-11 (before A2 deadline)
Mo Jan 31 9-11 (before A2 deadline)
Tu Feb 1 9-11 (before A2 deadline)
Fr Feb 11 9-11 (complains, midterm)
Mo Feb 14 9-11 (complains, midterm)
Tu Feb 15 9-11 (last chance of complains, midterm)
and one hour for final (tba)
NEW: Feb. 17 2:30pm to 4:30pm
New: March 2, Wednesday from 12:30 to 2:30 for assignment 2 complains.
New: April 12, 1-2pm.
- Pooyan Khajehpour Tadavani, DC3320, x33853, pkhajehp at
uwaterloo dot ca ,
Office Hours: (Pooyan is responsible for marking Assignment 1).
Fri Jan 14 - (10-12) (before the due date of A1)
Mon Jan 17 - (10-12) (before the due date of A1)
Wed Jan 19 - (10-12) (before the due date of A1)
Wed Jan 26 - (11-12) (for complains)
Fri Jan 28 - (11-12)
Mon Jan 31 - (11-12) (NEW: Pooyan has added this last chance for the complains)
Mon Feb 14 - (10-12) (for mid term)
New: April 12, 3-4pm.
- Alex Leong, DC2505, x33400, aleong at uwaterloo dot ca,
Office Hours: (Alex is responsible for marking Assignment 3).
Fri Feb 4 1-2
Mon Feb 7 1-2
Wed Feb 9 1-2
Fri Feb 11 1-2
Mon Feb 14 1-3
Wed Feb 16 1-3
Fri Feb 18 1-2
And then 3 more hours near the final (TBA).
New: Wednesday March 9 1pm-2pm and Friday March 11 1pm-2pm.
New: April 12, 2-3pm.
Jakub Michal Truszkowski, DC2501, x36612, jmtruszk at uwaterloo dot
Office Hours: (Jakub is responsible for marking Assignments 4 and 5)
For Assignment 4: Wed March 9 11 am -1 pm
Fri 11 March 11-1
Mon 13 March 11-1
Wed 23 March 11-1 (complaints)
For Assigment 5: Assignment 5:
Fri March 25 11-2
Mon March 28 11-2
Wed April 5 11-1 (complaints)
Mon Feb 14 11-1
Wed Feb 16 11-1
Office hour for A5 and Final exam:
Monday 12 April from 2 to 4 pm, and on Tuesday 13 April, from 11
to 2 pm, in DC2501
The work you hand in must be your own. Acknowledge any sources you
have used. Plagiarism is a serious offence.
The penalty for the first offence is -100% for the assignment.
General discussion of course material
with other people is ok, but not specific solutions. Write
up the solutions yourself, not in groups.
Write your name and student number clearly
at the top of the first page of your solution and hand it in to the
assignment boxes on the 3rd floor of MC near the bridge to DC before
1PM of the due date. Late assignments will not be accepted.
These lecture notes are powerpoint files. They will be complemented
by classroom explanations.
They will also be modified and improved gradually, sometimes
before the class time. Thus, it is a good idea you only download
the corresponding file before a class.
It may not be the case that one lecture corresponds to one set of
notes. I divided them more according to logical topics rather than
- Lecture 1, January 4
- Lecture 2, January 6, Assignment
1 handed out
- Lecture 3, January 11
- Lecture 4, January 13
- Lecture 5, January 18
- Lecture 6, January 20,
Assignment 1 due, Assignment 2 handed out
- Lecture 7, January 25
- Lecture 8, January 27
- Lecture 9, February 1
- Lecture 10, February 3,
Assignment 2 due, Assignment 3 handed out
- Lecture 11, February 8
- Lecture 12, February 10
- Lecture 13, February 15
- Lecture 14, February 17
Assignment 3 due 1pm -- solution will be posted 1:30pm, Midterm Exam --
No class, I will hold office hours from 2pm to 5pm in my office.
- Feb 21-25, reading week. No classes.
- Lecture 15, March 1
Assignment 4 handed out
- Lecture 16, March 3
- Lecture 17, March 8
- Lecture 18, March 10
- Lecture 19, March 15
Assignment 4 due, Assignment 5 handed out
- Lecture 20, March 17
- Lecture 21, March 22
- Lecture 22, March 24
- Lecture 23, March 29
Assignment 5 due.
- Lecture 24, March 31
New office hours on April 12: Soroush 1-2pm, Alex 2-3pm, Pooyan 3-4pm.
Assignment 5 is now marked. The solution to A5 is posted here.
Please pick up assignment 5 outside
Jakub Truszkowski's office: DC2501. Jakub will have
office hour for answering A5 questions and final exam
questions: Monday 12 April from 2 to 4 pm, and on Tuesday 13 April,
from 11 to 2 pm, in DC2501.
March 11, I have fixed some typo and improved the hint on the scorpion graph
in assignment 4. -- Ming
Solutions and marking scheme
for the Midterm are posted today (March 2, 2011).
I will discuss how to handle complains on the marking on
the Thursday (March 3) class. Please attend that if you have questions on the
marking of midterm.
New office hours for Alex for answering questions on Assignment 3
Wednesday March 9 1pm-2pm and Friday March 11 1pm-2pm.
New office hours for Soroush for any left complains on
Assignment 2: Wednesday from 12:30 to 2:30.
Assignment 2, Problem 5 (Programming), replace
"dynamic programming" by "divide-and-conquer".
The phrase "dynamic programming" was put there by mistake.
Assignment 1, Problem 2(b). Let's assume f(x) and g(x) are
always strictly greater than one.
We have now listed all the TA office hours. Each assignment will
be marked by ONE TA. Thus, for questions related to a particular assignment,
you should look for that TA who would have office hours around
that assignment period. If you have general questions related to the
lecture, then you can either talk to me, or the TA who has
the closest office hours.
- In Assignment 1, Problem 1(b), you are allowed to use "<" or ">"
Problem 1(c), please do not use any existing
algorithms like "find-median" -- which gives a trivial solution to
1(c). We will study that problem later. For the time being,
you should focus on understanding the problem, and
give a very simple solution to this problem.
University Policies (University required text)
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.
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,
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
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,
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,