Welcome to CS 231!
This term, material for the course will be divided between this website (resources and reference materials) and the LEARN site (announcements and updates).
For each of the sections of the website, listed below, please see when and if you need to read the material provided.
Mental health resources: This section discusses both mental health and diversity, though it hasn't been updated to reflect possible changes to on-campus services this term.
Policies and marks: This section outlines course policies as well as university policies. Be sure to read the information here carefully to make sure that you uphold the necessary standards of academic integrity and that you know your rights.
Contact information: Consult this section for information on how to use Piazza as well as whom to contact for various issues that arise.
Schedule: You can plan your time based on the schedule listed here, which includes lecture material, Python and math sessions, reading material, and due dates for each week of the term.
Lectures: This page outlines the topics covered in each module.
Resources: This section is a repository for extra reading materials and source code referenced in the lectures, as well as the math guide and session material and general course information.
Python: Make sure to consult the style guide provided here to ensure that your code fits the required standards. In this section you will also find Python modules provided for the course, Python guides and session materials, and resources for review.
Grading: Consult this page for the mark breakdown, marking policies, and what to do if you believe there was a marking error.
Assignments: Make sure you understand the assignment policies, including the need to submit an academic integrity declaration in order for you work to be marked.
Assessments: This section has information on the quizzes and final assessment.
Contact information
You can contact course personnel in office hours and using Piazza, as detailed below. Please limit your use of email to personal issues that require private discussion; general questions should be posted to Piazza. Email to the IA can be sent to [email protected].Note: If you decide to email course personnel, you must use your uwaterloo email account; otherwise we cannot verify who you are and are limited on what we can accept and respond to.
Whom to contact for various issues
| Help Topic | Contact |
| Assignment help: | Piazza or office hours |
| Assignment remark: | Email IA |
| Assignment submission error: | Describe your submission error in an email to the IA or post to Piazza. Keep trying to submit to Markus in the meantime. We do not accept e-mailed assignments. |
| Error in course website: | Email IA |
| Error in course slides or resources: | Email course instructor |
| Error in mark entry: | For assignments or midterms:Email IA |
| Exam seating | See instructions on the exams page |
| Lecture questions: | Piazza or office hours |
| Midterm remarks: | See instructions on the grading page |
| Missed assignment/midterm/final exam: | Karen Anderson (CS 231 ISC) |
Office hours
We will be holding both group and individual office hours, probably through MS Teams. The times may depend on the results of our polling to figure out what will suit you best. Please see LEARN for announcements of further details.
If you are unable to be available during an office hour but have a question you would like to be addressed, please post your question to Piazza with the tag OfficeHourRequest. Group office hours will be recorded and posted on LEARN for later viewing.
As needed, additional video explanations may be posted to LEARN, based on either office hours or written questions to Piazza.
Piazza
A discussion forum for the course has been set up on Piazza. Due to the lack of in-person interactions this term, Piazza will be the main way in which you will be asking questions about lecture material and interacting with your classmates. Please read the instructions and guidelines below before posting any questions.
Setting up your account
An email from the Piazza Team will be sent to your uwaterloo email address. Please follow the steps provided below.
- Check your uwaterloo email account for the email from the Piazza Team. If the email is not there, then you may have changed your email settings to forward all your uwaterloo emails to another email account. If the email cannot be found in any of your email accounts, then please email [email protected].
- The email will contain a link to activate your Piazza account and set your password. It is imperative that you provide your first and last name when creating your account so that we can easily contact you should any problems arise.
- After activating your account, you will be redirected to the CS 231 class discussion forum. Click on the drop down arrow in the top right-hand corner and click on Account/Email Settings. A dialog box will appear on the screen. Under "Preferences for Email Notifications", select "No Emails". It is important that "Real Time" is NOT selected; otherwise, you will receive an email every time another student posts on Piazza.
Using Piazza
To post a question on Piazza, click on "New Post" at the top of the page. You can choose to post a question or post a note. Use a question if you expect an answer, and a note otherwise.
On every question posted on Piazza, there is a students' response box where you can answer other students' questions or edit a previous response to include additional information. If you have followup questions on the original question, please use the followup discussions box.
Course personnel will be checking Piazza regularly to answer student questions and to monitor student behaviour on Piazza. Please read the guidelines below to avoid committing any offence while using Piazza.
Guidelines
Here are some guidelines that you should keep in mind when posting messages.
- Please remember that everything you post is public -- everyone will be reading it. As a result, in any posts you make to Piazza, do not give away any information about assignment solutions -- this could be construed as cheating. If you have questions about an assignment that require you to give specific details of your solution, visit office hours or send email to [email protected]. We have disabled the "anonymous" posting capability (although you will have the option of appearing anonymous to your fellow classmates but not to instructors).
- Please do not post any assignment code on Piazza, even as a private message. Visit office hours for any code-related questions.
- Limit posts on Piazza to those related to the course. Do not use Piazza for posting "test" posts or unrelated material.
- Make use of Piazza's excellent search facilities before posting a question. Please help keep Piazza from getting so cluttered with repeated questions that it becomes too cumbersome to be useful to you and your fellow students.
-
Make it easy for other students to find your question.
- Use a meaningful subject heading. "Help" and even "Help for a03q3" is not very meaningful. "Clarify contract restrictions for a03q3" is much better.
- Tag your post with all the applicable tags. Start a tag by typing the hash character (#). A drop-down list of tags that are currently in use will appear. Use one of them, if applicable. If not, create a new one. However, any tag you create should be applicable to many posts, not just yours.
- Make sure that your post contains useful information. Posts like "I have the same question" or "I agree with this comment" serve no useful purpose, and waste people's time.
- Please keep complaints about the course out of Piazza. If you have a concern about anything to do with the course, the best way to deal with it, and to get results, is to take it to the instructor. Piazza is not a complaint forum.
- Please be respectful of your peers and others in your posts.
Schedule
Please see the lectures page for details on topics and readings for each module.
Videos for the Python and math sessions will be posted on LEARN. Resources for the Python sessions can be found on the Python page. Session 1 will focus on the documents Python guide 1 and Python session 1 and session 2 will focus on the documents Python guide 2 and Python session 2, but each may cover other material as time permits. Resources for math session can be found on the Resources page.
| Week | Dates covered | Lectures and review sessions | Reading material | Important dates |
| 1 | May 11-18 | Modules 1a-2c | Python guide 1 | Victoria Day May 18 |
| 2 | May 19-25 | Modules 2d-2i; Python session 1 | Python guides 1/2 | |
| 3 | May 26-June 1 | Module 3a-3f; Python session 2 | Python guide 2 | Quiz 1 due May 29 |
| 4 | June 2-8 | Modules 3g-4d | Math guide | A1 due June 2 |
| 5 | June 9-15 | Modules 4e-4j; Math session | ||
| 6 | June 16-22 | Module 5a-5e | Quiz 2 due June 19 | |
| 7 | June 23-29 | Modules 5f-6c | A2 due June 23 | |
| 8 | June 30-July 7 | Module 6d-6h | Canada Day July 1; Prequiz 3 due July 6 | |
| 9 | July 8-14 | Modules 7a-7f | Quiz 3 due July 10; A3 due July 14 | |
| 10 | July 15-21 | Modules 7g-8b | ||
| 11 | July 22-28 | Module 8c-8g | Prequiz 4 due July 27 | |
| 12 | July 29-August 4 | Review | Quiz 4 due July 31; A4 due August 4 |
Lectures
This page contains the order of topics contained in lectures, listed as a sequence of modules. Please note that modules may vary considerably in length and difficulty; please see the schedule for details on timing.
Lecture materials are posted on LEARN in various formats, for your convenience. The slides and audio have been joined together into videos; there are also written transcripts of the audio.
Please see the resources page for additional relevant material, including a document outlining coverage of the material by the (optional) textbook.
Module 1: Introduction
Topics: Introduction, course goals, types of problems, exhaustive search
Module 2: Comparing problems and solutions
Topics: Comparing problems, models of computation, pseudocode, asymptotic notation, analyzing algorithms, analyzing exhaustive search
Module 3: Greedy approach
Topics: Scheduling activities, making change, fractional knapsack, single-source cheapest paths, spanning tree
Module 4: Divide-and-conquer
Topics: Binary search, sorting, solving recurrence relations, maximum subtotal, matrix multiplication
Module 5: Dynamic programming
Topics: Matrix-chain multiplication, longest common subsequence, all-pairs cheapest paths
Module 6: Hardness of problems
Topics: Complexity, polynomial time, lower bounds, decision trees, adversary lower bounds, reductions, NP-completeness
Module 7: Compromising on speed
Topics: Search trees, backtracking, branch and bound, fixed-parameter algorithms, Las Vegas algorithms
Module 8: Compromising on correctness
Topics: Approximation algorithms, Monte Carlo algorithms, heuristics
Course information
- The course outline/syllabus
- Undergraduate Calendar course description
- Course information from the Cheriton School of Computer Science
Textbook
This course has been designed so that all the material you need will either be available on the course site or explained in lecture. Those who wish to have an additional resource may find a textbook helpful. The textbook is optional, not required; it does not cover all the course material, but has additional material on algorithms for those interested in additional application areas. Where they differ, style and terminology used in lectures, not the textbook, should be used.
- Coverage of course material by the textbook can be found in this document.
Introduction to the Design and Analysis of Algorithms, third edition
Anany Levitin
Pearson, 2011
Resources
The resources below are summaries and/or extensions of material covered in lecture as well as resources for the math session. For the math session, please attempt the exericises (either at the session or on your own) before downloading the solutions.
Please see the Python page for resources relating to Python, including information for the Python sessions.
- Pseudocode
- Calculating worst-case costs
- Recipes from lecture
- Problems from lecture
- Math guide
- Math session problems
- Math session solutions
Lecture videos
Videos of lectures are available on LEARN. In case it is easier for you to process the material in a different way, audio, transcripts of the audio, and slides are also available.
Source for examples
Code used in lecture can be downloaded here.
- Module 1: Colour neighbours
- Module 3: Activities
- Module 3: Testing activities
- Module 3: Finish first
- Module 3: Selection sort
- Module 4: Binary search
- Module 4: Mergesort
- Module 4: Maximum subtotal
- Module 5: Longest common subsequence
- Module 7: One sequence
- Module 7: All sequences
Learning/reviewing Python
This course has been designed with the understanding that although all students will be familiar with programming, comfort with Python may vary. This page provides information to help prepare you for programming assignments.
The two Python guides list material to review as well as available resources; please see the schedule for dates by which the material should be mastered. The third document outlines differences between Python 2 (what you might have been taught, if you studied Python some time ago) and Python 3 (what is used in this course).
Logistics of using Python
The resources below are designed to help you get started in running Python. Please note that not all options listed here are guaranteed to ensure that your code will run in the school environment, as required for assignments.
- Information on how to obtain and run Python software is available on the CS 116 website.
- This resource addresses how to use Python on Windows and Linux machines.
- The Python panel of Python from scratch (discussed more below) can be used to run Python on the web.
- The file check.py is required for testing; you can learn more about it in the Python style guide, below.
Python style guide
Coding assignments in the course must use Python 3.2.3 or higher, and will be judged based on the criteria listed in the style guide linked below. Be sure to review the material listed, and if your previous exposure was to Python 2, make sure to learn differences between Python 2 and Python 3.
- Python style guide
- Code examples from the style guide (zip file)
- The file check.py, used for testing
Modules created for the course
The links below cover three modules provided for the course, information on how to use them, and related files.
- Information on equivalent lists, the module equiv.py, and the file equivuse.py, which demonstrates how to use the module
- Information on grids, the module grids.py, sample grids, sample images, and the file griduse.py, which demonstrates how to use the module
- Information on graphs, the module graphs.py, sample graphs and the file graphuse.py, which demonstrates how to use the module
- Information on trees, the module trees.py, sample trees and the file treeuse.py, which demonstrates how to use the module
Materials for review sessions
Materials are provided here for those who are not able to attend one or more of the optional Python review sessions. Please attempt the questions by following the instructions for exercises prior to downloading the sample solutions.
- Instructions for exercises for session 1
- Sample solutions for session 1 (zip file)
- Instructions for exercises for session 2
- Sample solutions for session 2 (zip file)
Resources for learning/reviewing Python
The following links provide additional resources on Python, to be used as you need. They come with the caution that you are expected to follow the terminology and style presented in the course.
- CS 116 course notes
- Python from scratch (basic Python instruction, including videos and interactive exercises)
- CS Circles (basic Python instruction, including text explanations and interactive exercises)
- The main Python homepage
- Style Guide for Python Code (PEP 8)
- A python wiki for beginners
- A reasonably comprehensive tutorial
- A reasonably comprehensive quick guide
Grading
Grading scheme
Marks in the course will be calculated as follows:
- Assignments (4): 60%
- Quizzes (4): 20%
- Final assessment: 20%
Notes:
- You must pass the final assessment in order to pass the course.
- Each assignment has the same weight towards the overall mark.
- You should periodically check recorded marks for accuracy.
Grade appeals
If you believe that there was an error in the marking of your assignment or quiz, please follow the steps listed below within two weeks of the marks being released:
- Review the model solutions and post mortem to ensure that the error is in the marking, not your understanding.
- Send an e-mail to the IAs with a request, including the rationale for the remark and the question or questions that need attention.
- Be prepared for your mark to either increase or decrease, and for questions other than those specified to be remarked.
- Contact the instructor only if you are not satisfied with the resolution of the remark request.
Assignments
Assignments consist of written and programming components, which are handled differently. Please read the information below carefully to ensure that your assignments are handed in properly.
Submit both types of components electronically using MarkUs. If MarkUs is new to you, help is available from the CS 116 website.
Written components
Please ensure that each written component contains your name, student ID, and assignment number.
Programming components
You must use Python 3.2.3 or higher for all programming questions. Your code will be assessed based on how it runs on linux.student.cs.uwaterloo.ca -- it is not sufficient for it to run without any errors on your home machine, so please test it accordingly.
The Python page contains a style guide that outlines guidelines for all assignments. Your code must be formatted according to these guidelines.
Assignment policies
All assignments must be completed individually in this course. The solutions you submit must be entirely your own work. Do not look up full or partial solutions on the Internet or in printed sources. Please consult the Policy page for information on plagiarism and various course policies.
In order for your assignment to be marked, you must submit the associated academic integrity declaration (available on LEARN) to MarkUs as a text file before you start work on the assignment.
No late assignments will be accepted.
We do not accept assignments that are emailed to course personnel. If there are problems with MarkUs, continue to submit your work until you succeed. We will handle special cases as warranted, based on what has been submitted. We recommend that you submit drafts of your work early and often before the deadline. Should problems occur, your early drafts serve as backups in case of computer problems, and provide evidence of your having attempted to submit work before the deadline.
When assignments are marked and available on MarkUs, an announcement will be made.
If you believe your assignment was not marked correctly, please see the section on grade appeals on the grading page.
Assignment schedule
Assignments will be available at least two weeks before due dates, on LEARN.
| Assignment | Deadline | Solutions | PostMortem |
| Assignment 1 | Tuesday June 2 at 4 PM | ||
| Assignment 2 | Tuesday June 23 at 4 PM | ||
| Assignment 3 | Tuesday July 14 at 4 PM | ||
| Assignment 4 | Tuesday August 4 at 4 PM |
Quizzes
Throughout the term, you will be provided with quizzes that will help provide a bridge between lecture material and assignments. You are allowed to take each quiz as many times as you like before the due date.
Quizzes are available on LEARN.
| Quiz | Coverage | Deadline |
|
Quiz 1 |
Modules 1-2 | Friday May 29 at 4 PM |
|
Quiz 2 |
Modules 3-4 | Friday June 19 at 4 PM |
|
Quiz 3 |
Modules 5-6 | Friday July 10 at 4 PM |
|
Quiz 4 |
Modules 7-8 | Friday July 31 at 4 PM |
Final assessment
The final assessment will cover all the material in the course. Unlike the quizzes and the assignments, the final assessment may ask you to synthesize information learned across modules taught at different times in the course.
To give you a sense of the types of questions that might be asked, a sample midterm example will be posted closer to the exam date.