[UW Logo]

CS 341: Algorithms, Winter 2018

David R. Cheriton School of Computer Science


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


Announcements

Piazza will be used for all course discussions and announcements.
To see your marks, go to LEARN.

General Information


Organization

Instructors:

Ming Li, DC 3355, x84659, mli "at" uwaterloo.ca
Office hours: Thursday 5:00 - 6:00pm, DC3355.

Bin Ma, DC 3345, x32747, binma "at" uwaterloo.ca
Office hours: Wednesday 4-5pm, DC3345.

Semih Salihoglu, DC 3351, semih.salihoglu "at" uwaterloo.ca
Office hours: Wednesday 3-4pm, DC3351.

Time and Place:

TAs:

All Office hours:

For week-to-week changes, see Piazza.

Wednesday 3-4 pm Semih Salihoglu DC 3351
Wednesday 4-5 pm Bin Ma DC 3345
Thursday 5-6 pm Ming Li DC 3355
Friday 11am-12noon TAs DC 2136B (CS advising office)
Friday (only for the weeks assignments are due) 3-4pm TAs DC 2102

Credit:


Resources

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

Additional books.


Assignments

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

Collaboration policy: The work you hand in must be your own. The value of the assignment is in doing it yourself (as you must do on tests and exams). Acknowledge any sources (human or non-human) 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 and you must acknowledge the discussion. If you use an electronic source, again, read it, then close it, then compose your solution and acknowledge your source. Write your solutions in your own words, from your own head. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Submission: Assignments will be submitted as pdf files (each question as a separate pdf). Type your assignments or write legibly. We are using Crowdmark to submit assignments this term. Before the submission deadline (usually the weekend before the deadline), we will send a submission link to your uwaterloo email and make an announcement on piazza. If you didn't get the link or have any question about the submission, you can contact Hong Zhou (h76zhou@uwaterloo.ca). If you need any help for submitting via Crowdmark, you can find instructions here.
Programming: Some of the assignments will contain programming questions, for which we will provide detailed instructions on how to submit your programs.

Late Policy: Assignments are due at 11:59PM on the due dates. No late submissions will be accepted.

Mark Appeals: All mark appeals (for assignments and midterm) must be made within two weeks of the date of the return (if you pick up your assignment/exam late, your appeal period does not lengthen). Your appeal should be submitted to the TA who marked the question in writing. Only if the problem is still unresolved should you then bring the case to the instructor's attention.

Assignments (to be uploaded on the handout dates) and Due Dates:

pdf tex OUT DUE marks
A1 pdf assn1.tex fig1.png fig2.png Monday, Jan. 8 Friday, Jan. 26 6
A2 pdf assn2.tex tiles2.png Tuesday, Jan. 23 Friday, Feb. 9 6
A3 pdf assn3.tex chocolate.png Tuesday, Feb. 13 Sunday, Mar. 4 6
A4 pdf assn4.tex scorpion.png Sunday, Mar. 4 Tuesday, Mar. 20 (written part, Q2-Q5)
Friday, Mar. 23 (programming part, Q1)
6
A5 pdf assn5.tex grid-graph.jpg Wednesday, Mar. 21 Wednesday, Apr. 4 6
TOTAL 30


Lectures (lecture notes will be uploaded gradually, and topics revised accordingly)

Note: Lecture notes for Section 4 (Prof. Ma's section) are downloadable from LEARN. Please feel free to share a copy with another student who does not have LEARN access.

Note: Although the topics covered in each section overall are the same, there may be differences when different topics are covered. Therefore for some sections, the topics we list in the table below may sometimes be different than the actual topic covered in that section. You might have to look for that section's slides/notes covering that topic in another day.

DATE TOPICS NOTES-Li NOTES-Salihoglu REFERENCES
L01 Th Jan  4 Introduction L1 L1 [CLRS Ch. 1]
L02 Tu Jan  9 Analyzing algorithms: models of computation, asymototic analysis, order notation L2 L2 [CLRS 2.2, Ch. 3]
L03 Th Jan  11 Reductions, Recurrences: Reducing 3-SUM to 2-SUM. Solving recurrences, intro to divide and conquer L3 [CLRS 4.3, 4.4]
L04 Tu Jan  16 Recurrences and Master Theorem L4 [CLRS 4.3-4.6]
L05 Th Jan  18 Divide and Conquer 1: Some of the following examples (examples may change by sections): Counting inversions, 2D-Maxima, Closest pair, Integer multiplication, Matrix multiplication L5 L5 [CLRS 4.2, 33.4]. Also see the handout on Learn from the DPV book on Divide and Conquer for integer multiplication.
L06 Tu Jan  23 Divide and Conquer 2:Some of the following examples (examples may change by sections): Counting inversions, 2D-Maxima, Closest pair, Integer multiplication, Matrix multiplication, FFT L6 L6 CLRS 4.2; Handout on Learn from DPV book 2.1
L07 Th Jan  25 Greedy Algorithms 1: several examples that may change by sections L7 L7 CLRS 16.1-16.2
L08 Tu Jan  30 Greedy Algorithms 2: Scheduling problems, knapsack L8 L8 CLRS 16.1-16.2
L09 Th Feb  1 Greedy Algorithms 3: Stable marriage and more greedy algorithms L9 L9 CLRS 16.1-16.2
L10 Tu Feb  6 Dynamic Programming 1: selections from: coin change, weighted independent subset, sequence alignment Knapsack, Subset Sum, Chain Matrix Multiplication L10 L10 general refs for the next 3 lectures: [CLRS Ch. 15] [KT Ch. 6] [DPV Ch. 6].
L11 Th Feb.  8 Dynamic Programming 2 L11 Cancelled [CLRS Ch 15]
   
L12 Tu Feb  13 Dynamic Programming 3 L12 L12 [CLRS Ch 15] (15.2 for matrix chain multiplication)
L13 Th Feb  15 Dynamic Programming / graph algorithms (not covered in midterm) L13 L13 [CLRS 22.1-22.3]
No lecture Tu Feb  20
No lecture Th Feb  22
L14 Tu Feb  27 Introduction to graph algorithms Definitions, BFS, DFS and their applications L14 L14 CLRS 22.1-22.3
L15 Th March  1 More applications of BFS/DFS L15 L15 CLRS 22.4-22.5
L16 Tu March  6 Minimum Spanning Trees or Shortest Paths or SCC L16 L16 [CLRS Ch. 22 and 23]
L17 Th March  8 Minimum Spanning Trees or Shortest Paths or SCC L17 L17 [CLRS Ch. 22 and 23]
L18 Tu March  13 Minimum Spanning Trees or Shortest Paths or SCC L18 L18 [CLRS Ch. 22 and 23]
L19 Th March  15 Graph topics, randomized algorithms, prelude of NP vs P L19
L20 Tu March  20 NP vs P, NP-completeness: Satisfiability L20 L20 [CLRS Ch. 34.1-34.4]
L21 Th March  22 NP-completeness Reductions 1 L21 L21 [CLRS Ch. 34.1-34.4]
L22 Tu March  27 NP-completeness Reductions 2 L22 L22-L23
L23 Th March  29 NP-completeness Reductions 3 L23 L22-L23
L24 Tu April  3 Undecidability L24 L24

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 https://uwaterloo.ca/academic-integrity/ 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 [check https://uwaterloo.ca/academic-integrity/] to avoid committing an academic offence, 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 instructor, academic advisor, or the undergraduate Associate Dean. For information on categories of offences 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: AccessAbility Services, located in Needles Hall, Room 1401, 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 AccessAbility Services at the beginning of each academic term.

Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:

Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).

Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).