Here we'll collect and update the resources and information you need for your learning. In what will hopefully be our last semester of online learning, we will be flexible and will work with you to ensure that you can participate as fully as possible.
If a medical or other factor might significantly impair your performance at some point in the course, inform the course coordinator (cpsc320-admin@cs.ubc.ca) immediately, detailing the issue and time frame.
Lectures and Tutorials
See here for times of lectures and tutorials. Tutorials will start on Wed July 7 (the first week of class). We expect that you will go to the tutorial for which you are registered. If for some reason that is not possible on occasion, you may attend a different tutorial on that week, but make sure to let your regular tutorial TAs know.
Because we believe strongly that you will learn most by interacting with your peers as well as course staff, lectures and tutorials will involve group and individual problem-solving work. While work done in lectures and tutorials will not be graded, participation will contribute to your overall mark. Lectures will be recorded, so you can follow along later in the day if needed. If feasible, we will arrange a regular set time for students who need accommodation to follow the lecture at a different time, so that they can do the group work together. Lecture worksheets and slides will be provided in advance of the lectures, and tutorial problems will be provided in advance of tutorials.
- To get participation credit for lecture work, upload to Gradescope the work you did on your worksheet during the lecture. You should do the upload within 24 hours of the start of lecture, i.e., by 1pm Vancouver time on the day after the lecture. No late credit will be given. Since the purpose of the worksheets is for you to learn by trying (and probably making mistakes), we will not be assessing the correctness of your work - this is about participation. We will do random checks, just to ensure worksheets are not blank and reflect your own work, not just solutions provided by the instructor.
- To get bonus points for tutorial attendance, upload your work on Gradescope by 4:30pm Vancouver time on the day after the tutorial.
| Week | Topic | Reading | Lecture Materials | Tutorial Materials |
|---|---|---|---|---|
| 1 |
Algorithm Design Steps
Asymptotic Notation |
Chapter 1, pages 1-12
Chapter 2 Gradescope Quiz Tutorial |
Mon Worksheet:
.pdf,
.docx
Wed Worksheet: pdf, docx Fri Worksheet: pdf, docx |
Wed: Permutations; Proof Review
Fri: Asymptotic Notn |
| 2 |
Graph Algorithms
Intro to Greedy Algorithms |
Chapter 3.1, 3.2, 3.4-3.6
Chapter 4.1 |
Mon Worksheet:
.pdf ,
docx
Wed Worksheet: .pdf , docx Fri Worksheet: .pdf , docx |
Wed: Graph Applications
Fri: Greedy Knapsack Part I |
| 3 |
Greedy Algorithms
Divide and Conquer Algorithms Recurrences |
Chapter 4.4-4.6
Chapter 5.1 |
Mon Worksheet:
.pdf ,
docx
Wed Worksheet: .pdf , docx Wed/Fri Worksheet: .pdf , docx |
Wed: Greedy Knapsack Part II
Fri: Divide and Conquer (revised Jul 21, 11am) |
| 4 |
More on Recurrences
Dynamic Programming |
Chapter 5, 5.2, 5.3, 5.5
Chapter 6, 6.1, 6.2 |
Mon Worksheet:
.pdf ,
docx
Wed Worksheet: .pdf , docx Wed/Fri Worksheet: .pdf , docx |
Wed: Recrrences, Divide and Conquer
Fri: Recurrences, Memoization |
| 5 |
Dynamic Programming
Reductions, NP |
Chapter 6, 6.4, 6.5
Chapter 8, 8.1-8.3 |
Wed Worksheet:
.pdf ,
docx
Fri Worksheet: .pdf , docx |
Wed: Dynamic Programming
Fri: Reductions |
| 6 | NP-Completeness | Chapter 8, 8.4, 8.5, 8.6, 8.8 |
Mon Worksheet
.pdf ,
docx
Wed Worksheet .pdf , docx |
Wed: NP-Completeness
No tutorial on Fri |
Assignments
| Number | Links | Source Files | Due Date |
|---|---|---|---|
| 1 | Assignment 1 (.pdf) (revised Jul 8, 10:30am) | (.tex) (revised Jul 8, 10:30am) (tutorial.sty) | 10pm Jul 14 |
| 2 | Assignment 2 (.pdf) (revised Jul 19, 10:30am) | (.tex); (tutorial-students.sty)(figure) tkz-graph.sty) | 10pm Jul 21 |
| 3 | Assignment 3 (.pdf) | (.tex) | 10pm Jul 28 |
| 4 |
Assignment 4
(.pdf)
|
(.tex) |
10pm Thu Aug 5 (because of holiday)
|
| 5 | Assignment 5 (.pdf) | (.tex) (figure) | 10pm Thu Aug 12 | -->
Assignments will be available on Wednesdays and due at 10pm Vancouver time a week later. You can work in groups of size up to three. Each group should make a single submission per assignment.
- The group must spend at least 15 minutes working on each problem independently before collaborating with others.
- Collaboration with others is limited to discussion and brainstorming. No record of any sort (e.g., written or electronic material) may be exchanged or leave the brainstorming session.
- After collaborating, each student must take a half-hour break from the problem. Treat electronic resources you consult like written resources (set them aside for a half-hour and then do not consult them while writing your solution).
- Each group must write their own independent solution, using their own words.
- Acknowledge all collaborators or sources of assistance in your submission, although you need only name CPSC 320 course staff, handouts, and textbooks if you quote or adapt directly from them. You should record the names of any other people you collaborate with.
We will make the .tex version of the assignment available, and encourage you to prepare your solutions using latex. We will accept solutions prepared using other good formatting systems, as long as they are clearly legibile. Solutions that are handwritten or difficult to read will receive a grade of zero.
Submit your assignment in pdf format on Gradescope by 10pm Vancouver time. You can submit early and resubmit as often as you want up to the deadline. We strongly encourage you to submit something at least a day in advance of the first assignment, to make sure that things are working properly.
After uploading to Gradescope, link each question with all the pages of your pdf containing your solution.
Also, add names of group members (as recorded on Canvas) on GradeScope after one student has made the initial submission. See the image below for adding group members to a submission:
As a secondary failsafe, please clearly write the names of all group
members on the first page of each submission, and
if you want an extra double-check on your identity, include your student number.
Late homework submissions will be accepted up to 24 hours past the due date, at a penalty of 15% of the assignment's full value. To avoid the deduction, have your documents imaged and ready to upload ahead of time, to avoid any last-minute stress and glitches. You can always upload a draft ahead of time, and resubmit later.
Quizzes
Instead of midterms, there will be a weekly quiz during lecture, at 2:30pm on Fridays, with five quizzes in total. You will have 45 minutes to do the quiz. You will not need to turn your video on during the quizzes. We will arrange an alternate time for students in a time zone where this is infeasible; please check for a poll on Piazza.The quiz will mainly test topics relating to reading, lectures, assignment and tutorials from the previous Friday up to Wednesday of that week, including reading for that week. Material from earlier weeks may also appear on a quiz. The rationale for weekly quizzes is to spread your overall mark out over more assessments, hopefully reducing stress and uncertainty.
You will take the quiz online on Gradescope. You can to refer to course materials and resources, including the textbook, the lecture slides, worksheets, and Piazza. You can use calculators or even implement algorithms to check your answers. You are not permitted to discuss with other people, use web searches or look for solutions or guidance anywhere else. You can ask clarification questions to the instructors via a private post in Piazza, or using private chat in Zoom.
Your lowest mark in a quiz will be dropped. If you miss two quizes, your mark for one will be dropped and your mark for the second will be calculated based on your performance on the final. You will not be able to make up marks for additional quizzes should you miss more than two.
Final
The final exam will be on Thursday August 19 from 8:30-11:00am Vancouver time. Students in all time zones will take the exam at the same time.The material covered in the final exam will be cumulative over the whole course. We will require that you have your video on during the final. We hope to schedule the final at a time when everyone enrolled can take it. If you are unable to write the final examination due to illness, you must apply to your home faculty for Academic Concession as soon as possible.
Evaluation
Five assignments × 6% = 30%
Four quizzes × 7% = 28% (there will be five quizzes, but lowest grade will be dropped)
One final exam × 36%
Lecture participation (16 in total, each worth 0.5%; up to four
missed lectures will be dropped) 6%
Tutorial participation You can get up to 4% extra by uploading
your tutorial work (11 in total, each worth 0.5%; up to three
missed tutorials will be dropped).
As explained above, you will get lecture participation credit by uploading your worksheet before the deadline, see above, and bonus tutorial participation credit also using upload. Check the deadlines above!
In accordance
with UBC
Policy #65, students who are scheduled to write
examinations or attend tutorials on the holy days of their religion must notify their
instructors two weeks in advance of the religious holiday they wish to
observe. Instructors will provide opportunity for students to make up
the missed work without penalty.
To pass the course, you must obtain at least 50% on the weighted
average of the quizzes and final exam. Students who fail to meet this
requirement will receive at most a mark of 45% for the course,
regardless of the results of the formula above.
Regrading Requests
We do our best to grade all submissions fairly and consistently. Because graders occasionally make mistakes, we welcome regrade requests that help us correct such mistakes and ensure fairness. You have one week from the time that the grades are posted to submit a regrade request on Gradescope. Please be respectful and help us ensure that time spent on regrades is productive by following these guidelines.- Prior to making a regrade request, make sure you understand the solution to the problem, and read any comments provided on Gradescope or Piazza about how the problem was graded. If you don't understand what's missing from your answer, come see one of us during office hours before submitting a regrade request.
- Explain clearly and specifically why you believe your mark is inappropriate, referring to your solution, and the rubric. Good examples: "I lost a point for not initializing my table entries, but I initialize them in line 6." Or, "My solution is quite different from the one in the sample solution, but I'm confident that my approach also works for the following reason..."
- Don't submit a request because you think the rubric is unfair, or if you disagree with a judgment call of the grader. A bad example that disputes the rubric is: "I lost a mark for not justifying my answer, but I didn't think I needed to justify my answer, and I don't feel I should be penalized." A bad example that disputes a judgment is: "I should get 'minor errors (-0.5 points)' instead of 'significant errors (-2 points)'." An example that is not sufficiently specific is: "My friend gave basically the same answer and got a higher grade."
The person who graded the question will review your request, possibly with input from an instructor or other TAs. The decision of your TA or instructor is final. It may either increase or decrease your mark. Submitting several poorly-explained regrade requests may result in a penalty.