[UW Logo]

CS 341: Algorithms, Winter 2012

link to F 11 web page

David R. Cheriton School of Computer Science

Contents: General Info, Organization, Announcements, Resources, Assignments, Lectures, University Policies

General Information

Organization

Instructor: Anna Lubiw, DC2334, x34449, alubiw "at" cs.uwaterloo.ca

Time and Place:

TAs:

General Office Hours (changes for specific weeks will be posted on Piazza):

Credit:

Announcements

Also be sure to enroll in Piazza, which we will use instead of a newsgroup.

Resources

Textbook: [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 (QA76.6 .C662 2009). (on-reserve in the DC library)
You can also use the 2nd edition, which is available electronically through the library.

Additional books. The first two are on reserve in the DC library for 3 hour loan:

Other web sources:

Assignments

The work you hand in must be your own. Acknowledge any sources 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. Write your solutions in your own words, from your own head.

Please include a cover page for your assignment with your name and student number. The TAs will use the cover page to write your marks. Hand in your assignment to the assignment boxes on the 3rd floor of MC near the bridge to DC.

You may hand in one assignment late (on Friday at 5 PM rather than the usual time of Wednesday at 5 PM).)

Assignments will be handed back in class.

Lectures

Here is a list of the topics covered in each lecture, with the relevant sections of the text [CLRS] and Skiena [S] and also some other references. I am not following the text exactly, so the lecture notes should be your primary source. Please borrow someone's notes if you miss a class.

L01 Tues. Jan. 3 Introduction: Convex hull example to illustrate design of algorithms, analysis of algorithms, lower bounds. [CLRS Ch. 1] [S Ch. 1] (Convex hull in [CLRS 33.3] or [S 17.2] but you don't need to read it.) notes
L02 Thurs. Jan. 5 Analysis of Algorithms: models of computation, asymptotic analysis, order notation. [CLRS 2.2, 3.1] [S Ch. 2] notes
L03 Tues. Jan. 10 Greedy Algorithms: making change, activity selection, scheduling to minimize lateness [CLRS 16.1] but not too readable. [KT 4.1] notes
L04 Thurs. Jan. 12 Greedy Algorithms: scheduling to minimize lateness, optimal caching, fractional knapsack [KT 4.2] (scheduling) notes
L05 Tues. Jan. 17 Divide and Conquer: Unrolling recurrences, proofs by induction, weak form of Master Theorem. [CLRS 4.3], [DPV 2.2] notes
L06 Thurs. Jan. 19 Divide and Conquer: Counting inversions, closest points in the plane. inversions [KT 5.3]. closest pair [KT 5.4], [CLRS 33.4]. notes
L07 Tues. Jan. 24 Divide and Conquer: Integer multiplication, Multiplying matrices. Graph Algorithms: Breadth-First Search. integer mult. [DPV 2.1], [KT 5.5], [BB 2.7.3]. matrix mult. [CLRS 4.2]. BFS [CLRS 22.2], [S 5.6]. notes
L08 Thurs. Jan. 26 Depth First Search: topological sort, strongly connected components. [CLRS 22.3 - 22.5] (wordy), [DPV 3.2 - 3.4] (more succinct, omits topological ordering) notes
L09 Tues. Jan. 31 Minimum Spanning Trees: Prim, Kruskal. [CLRS Ch. 23] (very abstract), [KT 4.5, 4.6] notes
L10 Thurs. Feb. 2 Single Source Shortest Paths: Dijkstra, on a DAG. [CLRS 24.3], [DPV 4.4], [KT 4.4]. notes
L11 Tues. Feb. 7 Dynamic Programming (lecture by Vinayak Pathak) [CLRS] [KT] [DPV] notes
L12 Thus. Feb. 9 Dynamic Programming (lecture by Vinayak Pathak) [CLRS] [KT] [DPV] notes
L13 Tues. Feb. 14 Dynamic Programming: shortest paths in graphs (lecture by Prof. J. Shallit) [CLRS] [KT] notes

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.
[Check www.uwaterloo.ca/academicintegrity for more information. ]

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. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.

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. For typical penalties check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.

Note for students with disabilities: The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.