To see revisions of this document or browse other course outlines, please Log In

Elementary Algorithm Design and Data Abstraction Fall 2022
CS 136

Published Nov 22, 2022

Class Schedule

Section Location Time Instructor(s)
CS 136 001 [LEC] B2 350
Wednesdays
8:30 a.m. - 9:50 a.m.
Stacey Watson
CS 136 002 [LEC]
Wednesdays
10 a.m. - 11:20 a.m.
CS 136 003 [LEC] MC 4060
Wednesdays
1 p.m. - 2:20 p.m.
This table is generated automatically

Instructor / TA Information

Instructor Contact Information

Stacey Watson
email address: stacey.watson@uwaterloo.ca

Coordinator Contact Information

Dalibor Dvorski
email: ddvorski@uwaterloo.ca

Instructional Support Assistant Contact Information

Caglar Memis & Alex Li
email: cs136@uwaterloo.ca

Office hours will be published on the course edX site: https://online.cs.uwaterloo.ca/

 

Course Description

CS 136

This course builds on the techniques and patterns learned in CS 135 while making the transition to use an imperative language. It introduces the design and analysis of algorithms, the management of information, and the programming mechanisms and methodologies required in implementations. Topics discussed include iterative and recursive sorting algorithms; lists, stacks, queues, trees, and their application; abstract data types and their implementations.

Prereq: At least 90% in CS 115 or at least 70% in CS 116 or at least 60% in CS 135 or CS 145. Coreq: CS 136L. Antireq: CS 137, 138, 146, PHYS 239

Learning Outcomes

By the end of this course students should be able to:
produce well-designed, properly formatted, documented and tested programs of a moderate size (200 lines) that can use basic I/O
use imperative paradigms (e.g., mutation, iteration) effectively
explain and demonstrate the use of the C memory model, including the explicit allocation and deallocation of memory
explain and demonstrate the principles of modularization and abstraction
implement, use and compare elementary data structures (structures, arrays, lists and trees) and abstract data type collections (stacks, queues, sequences, sets, dictionaries)
analyze the efficiency of an algorithm implementation

Tentative Course Schedule

Week 1

  • Sections 0 (Intro to CS136) and 1 (Intro to C) released
  • Assignment 0 released

Week 2

  • Section 2 (Imperative C) released
  • Sections 0 (Intro to CS136) and 1 (Intro to C) due
  • Assignment 1 released

Week 3

  • Section 3 (Memory & Flow Control) released
  • Section 2 (Imperative C) due
  • Assignment 2 released
  • Assignment 0, 1 due

Week 4

  • Section 4 (Pointers in C) released
  • Section 3 (Memory & Flow Control) due
  • Assignment 3 released
  • Assignment 2 due

Week 5 & Reading Week

  • Section 5 (Modularization & ADTs) released
  • Section 4 (Pointers in C) due
  • Assignment 4 released (during Reading Week)
  • Assignment 3 due

Week 6

  • Section 6 (Arrays) released
  • Section 5 (Modularization & ADTs) due
  • Assignment 5 released
  • Assignment 4 due

Week 7

  • Section 7 (Efficiency) released
  • Section 6 (Arrays) due
  • Assignment 6 released
  • Assignment 5 due

Week 8

  • Section 9 (Strings) released
  • Section 7 (Efficiency) due
  • Midterm

Week 9

  • Section 10 (Dynamic Memory & ADTs) released
  • Section 7 (Efficiency) due
  • Assignment 7 released
  • Assignment 6 due

Week 10

  • Section 11 (Linked Data Structures) released
  • Section 10 (Dynamic Memory & ADTs) due
  • Assignment 8 released
  • Assignment 7 due

Week 11

  • Section 12 (Abstract Data Types (ADTs)) released
  • Assignment 9 released
  • Assignment 8 due

Week 12

  • Section 12 (Abstract Data Types (ADTs)) due

Week 13

  • Assignment 9 due (Tuesday)

 

Texts / Materials

Title / Name Notes / Comments Required
C Programming: A Modern Approach, 2nd edition by K.N. King (W.W. Norton & Company) No
How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2001. No

Student Assessment

If both exams are held in person
Component Value
Concept Checks 5%
Assignments 25%
Midterm Exam 20%
Final Exam 50%
If both exams must be held online
Component Value
Concept Checks 5%
Assignments 60%
Midterm Assessment 10%
Final Assessment 25%

Notes:

  • You must pass both the Assignment portion and the weighted exam portions of the course in order to pass the course.
  • All assignments are weighted equally, except for Assignment 0 which does not contribute to the final grade in the course.
  • If in-person exams cannot be held then they will be held online (if possible).  An online exam will have half of its weight moved to the assignment component.
    • See the second table for an example of what this would look like if both exams are moved online.
  • If an online exam is not possible (e.g. due to not having enough time to switch format) then that exam will be cancelled.  Half of the weight will be moved to the assignment component, and the other half will be moved to the other exam.

 

Assignment Screening

Measure of Software Similarities (MOSS) 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 or MarkUs 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.

Administrative Policy

Assignment Questions: Assignment questions will be colour-coded as either "black" or "gold" to indicate if collaboration is permitted.  For "black" questions, moderate collaboration is permitted. You may discuss assignment strategies openly with others (including online) but you may not share your code with another individual in the class. You may also search the Internet for strategies and code examples. Any form of collaboration, including discussion must be stated explicitly in your submissions. Not properly stating collaboration on your assignment is considered to be a violation of academic integrity.  For "gold" questions, no collaboration is permitted. This also implies no collaboration on test cases. All work is to be done individually. You are not allowed to discuss solution ideas, implementation details, or code. Only clarification on what an assignment question is asking is permitted. All work submitted must be entirely your own. If you find yourself stuck, contact an ISA or instructor or IA for additional help, instead of getting the solution from someone else. You may also ask on the discussion forums in a private message. When trying to deal with difficulties, do not copy from the book or any Web sources, unless explicitly authorized to do so.  The penalty for plagiarism is an assigned mark of zero on the assignment question or test and a deduction of five marks from the final course grade, consistent with the School of Computer Science and Faculty of Mathematics policy. In addition, a letter detailing the offence is sent to the Associate Dean of Undergraduate Studies, meaning that subsequent offences will carry more severe penalties, up to suspension or expulsion. To avoid inadvertently incurring this penalty, do not copy work from anyone or any place.

Remarking Policy: Submit a remark request form, which is available on the course Web site, to your course ISA to request a remark on your assignments.

Missed Assessments: Assignments are a key component of this course, and you are expected to complete them all. Exceptions may be granted in the case of illness or other extenuating circumstances (if you need such an exception, ask your ISC, and be aware that you may be required to provide documentation). However, no more than 1/3 of the assignments may be excluded from the final grade, regardless of your circumstances. If your circumstances are such that that level of accommodation is insufficient, consult an academic advisor to discuss your options.  With a valid Verification of Illness Form (VIF), the weight of the assignment or quiz you missed may be shifted to the rest of your assignments or quizzes; and for the midterm, the weight may be shifted to your final assessment.  With a valid VIF, a missed final assessment results in an INC for your final grade; and your final grade will be calculated when you are next able to write a final assessment.  Your grade will then be calculated using your previous assignment, quiz and midterm mark and using the current weighting used from this semester.  If you are in any of these cases, please contact the coordinator.

Use of the Discussion Forums: Use the discussion forums for general questions about assignments. Do not discuss implementation details for assignments (such as code particulars) or concrete assignment solutions publicly.  Do not discuss anything about quizzes, the midterm or the final assessment on the discussion forums (except privately to the instructors).

Use of Microsoft Teams: The use of Microsoft Teams is exclusive to office hours, question and answer sessions, and private appointments; and should be limited to the specific channel and timeslot.  You should not post nor discuss anything relating to the assignments with others nor information about the quizzes on Microsoft Teams, and specific questions should not be posted directly on Teams.  If you have a question, use the discussion forums if applicable or email the appropriate person. The student group on Teams is only monitored during specified office hours or question and answer sessions in the specific channel.

Mental Health Support: The Faculty of Math encourages students to seek out mental health support if needed.

  • On-campus Resources:
  • Off-campus Resources:
    • Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454 (Ontario and Nova Scotia only)
    • Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247 (Waterloo Region only)
    • OK2BME: set of support services for lesbian, gay, bisexual, transgender or questioning teens. Phone: 519-884-0000 extension 213 (Waterloo Region only)
    • EMPOWER ME 1-833-628-5589 for Cdn./USA other countries see: http://studentcare.ca/rte/en/IHaveAPlan_WUSA_EmpowerMe_EmpowerMe
      • EMPOWER ME in China:
        China North 108007142831
        China South 108001402851

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 term 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 Policy

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.

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.

Turnitin.com: Text matching software (Turnitin®) may be used to screen assignments in this course. Turnitin® is used to verify that all materials and sources in assignments are documented. Students' submissions are stored on a U.S. server, therefore students must be given an alternative (e.g., scaffolded assignment or annotated bibliography), if they are concerned about their privacy and/or security. Students will be given due notice, in the first week of the term and/or at the time assignment details are provided, about arrangements and alternatives for the use of Turnitin in this course.

It is the responsibility of the student to notify the instructor if they, in the first week of term or at the time assignment details are provided, wish to submit alternate assignment.