CS 341: Algorithms Fall 2022

---

Assignments

---

Hand in a PDF file with your solutions via CrowdMark. You may prepare your solutions using LaTeX but you can use other software or submit handwritten assignments as long as they are legible. We have the right to take marks off for illegible answers.

When the CrowdMark instance is ready, all students enrolled in the class will receive an email with a link to their individual submission site. In order to submit, upload a separate PDF file (multiple pages are allowed) to each question. You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.com/help/completing-and-submitting-an-assignment/.)

Marmoset will be used for the programming questions, and is available at https://marmoset.student.cs.uwaterloo.ca.

Assignments will appear in the following table, and will be due on the dates specified:

Assignment Number	Date Posted	Due (11:59pm EDT/EST)	Hand In Via	Markers	Solution Sketches
1 PDF, LaTeX	Fri Sept 16	Mon Sept 26	CrowdMark	Q1: Yueheng Q2: Argyris Q3: Abhiroop Q4: Multiple TAs (contact Sylvie)	Learn
2 PDF, LaTeX	Tues Sept 27	Mon Oct 17	CrowdMark	Q1: Jarrod & Kam Q2: Jesse & Daniel Q3: Jesse & Yueheng Q4: Abhiroop & Argyris	Learn
Programming 1 PDF	Tues Sept 27	Mon Oct 24	Marmoset
3 PDF, LaTeX	Mon Oct 24	Mon Nov 7	CrowdMark		Learn
Programming 2 PDF	Tues Nov 8	Thurs Dec 1	Marmoset
4 PDF, LaTeX	Tue Nov 8	Mon Nov 21	CrowdMark
5 PDF, LaTeX	Tue Nov 22	Mon Dec 5	CrowdMark

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). In all assignments, unless otherwise directed, you are expected to justify any claims that you make. The level of explanation we generally expect is "enough to convince a skeptical TA". Usually this means that a complete formal proof from first principles is not needed (unless we say so). Furthermore, since this course is essentially all about efficient use of time and space, strive to make your solutions as efficient as possible. Solutions that are technically correct, but not as efficient as they could be in terms of time and space, will not receive full credit.

Collaboration Policy: The work you hand in must be your own. Unless specified otherwise, you can always use any result from the textbook, notes, or previous assignment just by citing it. 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. Acknowledge any sources you have used. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.

Late Policy: No lates are accepted.

Programming Questions: There will be 2 programming assignments, where we ask you to code an algorithm. We will not test your code against inputs that do not match our specifications. However, your program should take care of the edge cases that are crucial to the algorithm's correctness or analysis. For example, unless the problem states so, you should not usually assume that the input size is a power of 2. We will send out detailed instructions about how to submit programming questions.

---

Piazza

---

We will use Piazza for all course announcements and as a forum for students to ask and answer questions. So you should enroll yourself at your earliest convenience. During Piazza discussions, please do not reveal the solutions to the assignments by requesting or offering detailed advice. We'll delete comments that reveal too much. Violations can result in academic sanctions.

Similarly, do not solicit hints or provide hints about how to solve the homework problems on other bulletin boards, such as Facebook. Violations can result in academic sanctions.

Piazza is not the place to dispute how assignments are marked. If you have a complaint, please follow the process given below.

---

Organization

Teaching assistant	Email (at school name dot ca)
Bandar Al-Dhalaan	bh3aldha
Aseem Baranwal	arbaranw
Jesse Allister Kasian Elliott	jakellio
Daniel Herman	d2herman
Argyris Mouzakis	amouzaki
Jarrod Pas	jpas
Abhiroop Sanyal	a5sanyal
Kam Chuen Tung	kctung
Yueheng Zhang	y3763zha

TA Office hours

Time (EDT/EST)	Link
See Piazza	See Piazza

Instructional support coordinator

Instructional support coordinator	Email (at school name dot ca)
Sylvie Davies	sldavies

Mark breakdown

• 5 written assignments worth 6% each.
• 2 programming assignments worth 3% each.
• An in-person midterm worth 24% (Tuesday, Nov 1, 7:00pm to 8:50pm, room TBA).
  Midterm Reference Sheet: link
• An in-person final exam worth 40% (Schedule by the Registrar, date TBA).

Points of contact for common questions

Note: If you decide to e-mail the course staff, you must use your uwaterloo Quest e-mail account (WatIAM/Quest userID @uwaterloo.ca); otherwise we cannot verify who you are and are limited on what we can accept and respond to.

Help Topic	Contact
Assignment, Missed Deadline:	We do not accept emailed assignments or more than 0 late assignments. The last files submitted before the deadline will be marked (submit early and often, even if not finished). If the deadline is missed due to illness or other valid, verifiable reason, see Missed Work Due To Illness below.
Assignment Marking Error:	Re-mark request, due within one week of release of marks on CrowdMark/Marmoset. Contact the TA who marked the specific question and submit a written request. See TAs for contact information.
Assignment Recording Error:	Grades will be made available through https://www.student.cs.uwaterloo.ca/~cs341/cgi-bin/displayMarks.cgi. If you notice an error in the recorded value, please contact Sylvie Davies (CS 341 ISC).
Course Website Error:	Email CS341 course account
Handouts Error:	Instructors - email or check consulting hours listed at Instructors
Enrollment:	If Quest won't let you enroll or switch LEC or TUT sections without a permission/override number: Instructors and course staff are unable to help you—you must see a CS academic advisor.
General Course Help:	TA office hours or instructor office hours.
Lecture Questions:	TA office hours or instructor office hours.
Missed Work Due To Illness/Valid, Verifiable Reason (Assignments, Exams):	Assignments, midterms, final exam: Validation required (see Verification of Illness Services at https://uwaterloo.ca/campus-wellness/health-services/student-medical-clinic but substitute Sylvie Davies (CS 341 ISC) for references to instructor. Make sure you also read the Math Faculty document on the consequences of submitting a VIF.
AccessAbility Services (AAS) exam accommodation forms (request to write at AAS):	Submit to AAS at least 3 weeks before exam

---

Resources

---

If you are person who likes a more detailed text book format, here are our recommendations for sources available online.

• [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.)
  A standard reference. Thorough, but can be wordy and complicated. https://ocul-wtl.primo.exlibrisgroup.com/permalink/01OCUL_WTL/5ob3ju/alma9940369163505162

Note: An older edition of the book is also available through the UWlibrary but the relevant sections may not be numbered the same.

• [DPV] Dasgupta, Papadimitriou, Vazirani, Algorithms
  Very concise. http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf
• [Erickson] Jeff Erickson, Algorithms
  Good coverage, many exercises and problems. available online https://jeffe.cs.illinois.edu/teaching/algorithms/
• [Skienna] Steven Skienna, The Algorithm Design Manual
  More practical, and with a catalogue of algorithms. https://ocul-wtl.primo.exlibrisgroup.com/permalink/01OCUL_WTL/5ob3ju/alma9953151786305162

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

This book is available electronically through the UW library catalog.

Additional reference: [DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available here.

Additional books:

• [KT] Kleinberg and Tardos, Algorithm Design (QA76.9.A43K54 2006)
• [BB] Brassard and Bratley, Fundamentals of Algorithmics (QA9.58.B73 1996)
• [GJ] Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (QA76.6.G35 1979)

The following resource is also useful for the course but more importantly for technical interviews you may have:

• Adnan Aziz and Amit Prakash, Algorithms for Interviews, 2010. Available here. Nice small collection of problems and solutions

---

Course policy and other information

---

Plagiarism

Plagiarism is a very serious academic offence and is penalized accordingly. When you plagiarize you damage the learning experience for yourself and others. To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use. If you work with others, only discuss general aspects of the course material, not specific solutions. Write up the solutions yourself, not in groups.

Mental Health Resources

Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.

On-campus Resources

• Campus Wellness https://uwaterloo.ca/campus-wellness/
• Counselling Services: counselling.services@uwaterloo.ca / 519-888-4567 ext 32655 / Needles Hall North 2nd floor, (NH 2401)
• MATES: one-to-one peer support program offered by Federation of Students (FEDS) and Counselling Services: mates@uwaterloo.ca
• Health Services service: located across the creek from Student Life Centre, 519-888-4096.

Off-campus Resources

• Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454
• Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247
• OK2BME: set of support services for lesbian, gay, bisexual, transgender or questioning teens in Waterloo. Phone: 519-884-0000 extension 213

Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students' learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

• We will gladly honour your request to address you by an alternate/preferred name or gender pronoun. Please advise us of this preference early in the semester so we may make appropriate changes to our records.
• We will honour your religious holidays and celebrations. Please inform of us these at the start of the course.
• We will follow AccessAbility Services guidelines and protocols on how to best support students with different learning needs.

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 the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their 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 an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] 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.

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, https://uwaterloo.ca/math/current-undergraduates/regulations-and-procedures/cheating-and-student-academic-discipline-guidelines.

MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.

Discipline cases involving any automated marking system such as Marmoset include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.

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 they have 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.