Syllabus

Introduction

This course is about several broad categories of problems and problem-solving techniques (such as greedy algorithms, divide-and-conquer algorithms, dynamic programming, and the class of NP-complete problems) and gaining the tools and experience necessary to judge how a new problem might fit one of these categories, how to approach solving the problem, and how to analyze and adjust your solution.

At the end of the course, you will be able to:

  1. Recognize which algorithm design technique(s), such as divide and conquer, prune and search, greedy strategies, or dynamic programming was used in a given algorithm.
  2. Select and judge several promising paradigms and/or data structures (possibly slightly modified) for a given problem by analyzing the problem’s properties.
  3. Implement a solution to a problem using a specified algorithm design paradigm, given sufficient information about the form of that problem’s solution.
  4. Select, judge and apply promising mathematical techniques (such as asymptotic notations, recurrence relations, amortized analysis and decision trees) to establish reasonably tight upper and lower bounds on the running time of algorithms.
  5. Recognize similarities between a new problem and some of the problems they have encountered, and judge whether or not these similarities can be leveraged towards designing an algorithm for the new problem.

You can also see a more detailed list of topic-level learning goals, although we may alter the specific topics used to address the course-level learning goals.

Prerequisites and Calendar Description

Available in the CPSC 320 UBC Calendar Entry.

Beyond these, brush up on probability and combinatorics (e.g., at least the intro to the Wikipedia article on combinations). You should also be comfortable reasoning using mathematical notation. You will need familiarity with summations, sets, relations, functions, asymptotic notation (O, Ω, Θ), recursion, loop invariants, basic data structures (stacks, queues, linked lists, heaps, graphs, hash tables), sorting algorithms, and graph traversal (depth-first and breadth-first search).

Tutorials

Tutorials begin on Wednesday July 3.

All tutorials meet twice a week on Wednesday and Friday. In most weeks, the Wednesday tutorial will involve a low-stakes quiz (see quizzes section for details) intended as preparation for the week’s assignment and the Friday tutorial will involve some new material (often supplementary to lecture material or review of previous courses). For quiz tutorials, you must attend your own tutorial section. For non-quiz tutorials, you are free to attend other tutorial sections (though we prefer you attend your own to avoid overcrowding in any particular section).

Evaluation

Your course mark will be based on the following breakdown. The course staff reserves the right to change this scheme (but does not anticipate using that right).

Assignments 25%
Midterm Exam 25%
Final Exam 45%
Tutorial Quizzes 3%
Pre-Class Reading Quizzes 1%
Clicker Questions 1%

To pass the course, you must obtain a 50% overall mark and 45% on the weighted average of your midterm and final exam grades. Students who receive less than 45% on the exam component of their grade will receive as their course grade the minimum of their normally computed grade and 45%.

If your final exam grade is higher than your midterm exam grade, we will move 10 percentage points from the midterm exam component to the final exam component. Exceptions: you are not eligible to have midterm exam weight shifted to the final exam component if you skipped the midterm exam without obtaining approval from the instructor, or if you received a lowered grade on the midterm exam as part of a disciplinary action for academic misconduct.

There will be 5-6 assignments and tutorial quizzes throughout the term. Each assignment and quiz contributes an equal amount to the respective average for that category; however, your lowest grade in each category will be dropped.

Pre-class reading quizzes will be due online roughly once or twice a week. They aim to provide a light assessment of your understanding of the textbook material after an initial reading (we will explore the material more in lecture and assignments, so don’t feel that you need to have mastered the content after the reading). Quizzes will be scaled to 2 points each, where your grade will be rounded up to the next integer (so 30% on a quiz would earn 1/2, and 68% on a quiz would earn 2/2). If p is the total number of pre-class quizzes and you earn y points total, then your pre-class quiz grade will be min(100, 100*y/(0.8*2*p)). In other words, you only need the equivalent of full marks on 80% of these to earn 100% on this component. However, the heavily hands-on nature of this class means that doing the pre-class work will leave you better prepared to learn and contribute in lecture — so, although this component is not worth much, we recommend you take it seriously so that you benefit as much as possible from your time in lecture.

Clicker questions are graded based on completion — so, if you show up to lecture and answer the question, you will earn a point for it. If q is the total number of in-class clicker questions and you earn y points total, then your clicker question grade will be min(100, 100*y/(0.8*q)). In other words, if you answer 80% of the clicker questions, you will earn full marks for this component.

Bonus points

We award bonus points for useful Piazza contributions, solving bonus problems on assignments/exams, helping other students in lecture and office hours, and anything else that helps promote learning for the class. Each bonus point will add 0.15 points to your final course grade, up to a maximum of 16 bonus points (or a 2.4-point increase to your final grade). Any further bonus points will not contribute to your grade.

Regrade requests

We accept regrade requests for submissions marked on Gradescope (that is, for assignments, quizzes, and the midterm exam) until one week after the submission is returned to you. Your request will be handled by whoever originally graded your submission, possibly with input from other TAs or the instructor. The decision of the grader is final, and may either increase or decrease your grade. Note that we will regrade based solely on what is written in your original submission and not on any additions or clarifications made in your regrade request.

Before you submit a regrade request:

  • Make sure you understand the solution. Please read and understand the sample solution before you dispute your grade. If you aren’t sure why your answer is incorrect, we are happy to help you with this during office hours.
  • Check Piazza for a post about common errors and other general grading comments. After grading an assignment or exam, TAs will often compile a Piazza post of common errors with notes on how they graded. Be sure to look this over, as it may help clarify why you lost points.
  • Make your request clear and specific. Your regrade request should be clear, concise, and refer specifically to the item(s) on the rubric that you think should or should not have been applied to your submission. Something like “My friend gave basically the same answer and got a higher grade” is not specific enough.

What merits a regrade: regrade requests are justified if there was a mistake in applying the rubric. These are the usual circumstances that lead to an increase in points:

  • Your answer is essentially the same as the solution, but the grader didn’t realize it. Make sure your request is clear about why your answer is correct. For example: “I lost points for not initializing my table entries, but I initialized them on line 6,” or “My answer is marked as blank, but I wrote my answer on the next page of the exam booklet.”
  • Your answer is substantially different from the solution key, but is still correct. Problems in CPSC 320 often have more than one correct way to solve them. If you had a different approach that you believe is correct, your regrade request should provide a clear, informal explanation of why your approach does in fact work.

What does not merit a regrade: you should not submit a regrade request if:

  • You disagree with a judgment call. For example: “I got ‘significant errors’ but I think I should have gotten ‘minor errors.'” We will not regrade judgment calls because a grader is far more likely to make a biased or inconsistent judgment when they’re looking at a submission long after the other ones and they’ve just seen a student’s complaint about the grading decision.
  • You disagree with the rubric itself. For example: “I lost points for not justifying my answer, but I thought the justification was trivial and didn’t need to be included, so I don’t feel I should be penalized.” You might not like that you lost points under the rubric because of something you did or didn’t do, but we have to grade all submissions consistently. That means we can’t change the grading scheme just for you.

You may be penalized for submitting several bad regrade requests on a single submission (e.g., requests that are poorly explained, reflect poor understanding of the requirements for a correct solution, and/or fall under “what does not merit a regrade”).

For the final exam, you can email the instructor to make an appointment in the fall term to review your exam and learn from it. For marking disputes, see UBC’s Review of Assigned Standing policy.

Important Dates

First Day of Classes July 3
Add/Drop Deadline July 8
Drop with W Deadline July 19
Midterm exam July 24
Statutory holiday (no classes) August 5
Last Day of Classes August 9
Final Exam August 13

Rough Topic Schedule

Here is a rough schedule of topics very much subject to change.

  • Week 1: Introduction, stable matching problem, and reductions
  • Week 2: Asymptotic analysis, graphs, and intro to greedy algorithms
  • Week 3: Wrap up greedy algorithms; divide and conquer
  • Week 4: Dynamic programming
  • Week 5: NP-completeness
  • Week 6: Catch-up and additional fun topics

Communication

We’ll post class and tutorial material and assignments as tagged blog posts here. Most other communication (including yours!) will go through our Piazza page. You are expected to read our course’s Piazza “Announcements” daily!

Additionally, set up your @ugrad.cs.ubc.ca account immediately, as we’ll use it for a variety of purposes in the course. Test it by sending yourself mail at that address to ensure you receive the mail either directly or via forwarding (whichever you choose).

Personal questions for the course staff can be asked as private questions on Piazza. If you prefer not to post your question on Piazza, you may send email to cs-320@students.cs.ubc.ca for response by any staff member or to the individual staff member you wish to contact.

We generally aim to respond to student communications within one day, though response times may be slower when the course staff is busy (e.g., during exam grading) and on weekends and holidays. In particular, the instructor will often not be checking email or Piazza on Saturdays, but will try to respond on Sunday (you may also get Piazza responses from the TAs).

Assignments

There will be 5-6 written assignments during the term. We will drop your lowest assignment mark.

  • Submission: Assignments will be submitted by Gradescope. Your @ugrad.cs.ubc.ca email alias (which you can view in the previous link) is used to identify you on Gradescope. As Gradescope is hosted outside Canada, we want to remind you to keep your @ugrad alias private, just as you would any other account information.  If you choose not to keep your @ugrad alias confidential, please note that UBC will proceed on the assumption that you do not object to Gradescope potentially identifying you personally, and that you are consenting to the storage of personal information on Gradescope servers outside Canada. You can submit your assignment early and you may resubmit as many times as you want before the deadline. We encourage you to submit something a few days before the first assignment deadline to make sure that everything is working properly.
  • Typesetting: We encourage you to write your assignments in LaTeX. If you choose not to use LaTeX, you may use other typesetting software (e.g., MS Word), or you can write your assignment by hand and submit a scan or high-quality photograph. Please ensure that your submission is clearly legible. You may be penalized if your submission is hard to read at any point.
  • Schedule: Assignments are released roughly once per week. They will generally be released on Wednesday afternoon and be due the following Tuesday night (this schedule may change in the weeks of the midterm and final exams).
  • Late Policy: We will not accept late assignments, but please contact us promptly if you believe you’ll be late. We may be willing to make some accommodation. Remember, however, that we already drop the lowest assignment mark.
  • Collaboration: We allow (and encourage!) you to submit assignments in groups. See the academic conduct guidelines.

Quizzes

Quizzes are written in tutorial, generally on Wednesdays.  The quizzes are low-stakes, and the purpose is to give you a chance to get started on a problem for the week’s assignment and to collaborate with your classmates, with TAs to help facilitate.

The first part of the tutorial consists of a group quiz, where you’re free to discuss the problem with your peers and ask for help from TAs. This portion of the quiz is open book, open notes, and open internet (though we encourage you to focus more on discussing problems with your peers and TAs than on trying to look things up online!). In the last half of the tutorial, you will be given an individual quiz that builds on the group quiz. The individual quiz is open book and open notes, but electronic devices are not allowed. You will be graded based on your submission for the individual quiz. NOTE: grading for the quizzes will be largely based on effort, rather than correctness; so, even if you got full credit for a question the quiz, this does not necessarily mean that the same answer would earn full marks on the assignment.

Exams

There will be a midterm and a final exam. You will be allowed to bring cheat sheets to both exams (we will provide more details about this closer to the exam dates).

Missing an exam: Do not write an exam if a medical factor might significantly impair your performance. If you are unable to write a midterm due to illness, inform your instructor immediately, detailing the period during which you were ill, but do not present a doctor’s note. The instructor will establish and explain accommodation at that time. If you are unable to write the final due to illness, contact your Faculty’s advising office (e.g., the Science Undergraduate Advising office) immediately.

Missing a quiz: We already drop the lowest quiz, and the quizzes are only worth a small percentage of your grade. So, we do not anticipate waiving a missed quiz. If you miss more than one, please email cs-320@students.cs.ubc.ca or the instructor to tell us why, and we’ll consider accommodation.

Academic Conduct

Collaboration enhances the learning experience. We encourage collaboration in various ways throughout the course, subject to the rules stated here:

  • Assignments: You may work on assignments in groups of up to three people. Groups are described below. Your group may also work with any other person or resource subject to five rules:
    • The group must spend at least 15 minutes working on each problem independently before collaborating with others.
    • Collaboration with others must be limited to discussion and brainstorming. No record of any sort (e.g., written or electronic material) may be exchanged or leave the brainstorming session. Nor may you bring your solution into the session (except in your head), since that tempts you to annotate it.
    • After collaborating, each student must take a half-hour break from the problem. Watching some brainless TV is a recommended activity. In other words, do something so distracting and inane that you must have learned anything you can reconstruct afterward.
      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 up their own solution independently, using their own words to prove that they understand the problem on their own.
    • Groups must acknowledge all collaborators or sources of assistance in their submission, although you need only name CPSC 320 course staff, handouts, and required textbook if you quote or adapt directly from them. (Despite previous rules, you may record the names of people you collaborate with! RECORD EVERYONE IN YOUR QUIZ GROUP IN TUTORIAL!)
  • Groups: must submit only one joint solution to the assignment and will receive one grade for the assignment that applies to every group member. We urge you to attempt the problems individually for a while, then come together to meet physically and hash out a joint solution as a group. Any other approach is likely to lead to disaster on the exams. For advice on group work, speak with the teaching staff and check out All I Need to Know About Pair Programming I Learned in Kindergarten (lighthearted but well-researched, for programming but applicable to written assignments).
  • Exams will follow the University’s Rules Governing Formal Examination, including disallowing any communication by any means with anyone besides the exam’s invigilators except where specifically noted in exam instructions.

Violation of any of these rules constitutes academic misconduct and is subject to penalties ranging from a grade of zero on a particular assignment to indefinite suspension from the University. If you are uncertain as to what is or is not reasonable collaboration, or you’re having problems understanding or keeping up, please contact the instructor or a TA. Don’t cheat! It sucks the soul from the course.

Textbook

Our required textbook (from which we will have assigned readings!) is: John Kleinberg and Éva Tardos, Algorithm Design, Addison-Wesley Publishing company, 2005, ISBN 0-321-29535-8. We have been informed by previous students (but cannot confirm or deny) that the international edition of the textbook is cheaper and yet corresponds closely to the edition listed here.

You may find Kevin Wayne’s slides accompanying the book a good supplement: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/

(You could even use them for your pre-class readings as long as you’re aware that they’re not the same as the textbook. “Buyer beware.”)

Other references

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009, ISBN 0-262-03384-4.
  • Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw Hill Book Company, 2008, ISBN 0-07-352340-2. (you can find a draft here).
  • Michael Garey and David Johnson, Computers and Intractability: a Guide to the theory of NP-Completeness, W.H. Freeman & Company, 1979, ISBN 0-7167-1044-5.
  • Donald E. Knuth, The Art of Computer Programming, Volume 1-4a.

Online references:

  • Algorithms, etc. by Jeff Erickson. A good, up-to-date review of algorithms.
  • The Algorithm Design Manual by Steven S. Skiana. A somewhat out-of-date, but engagingly written review of algorithms. (Also a print book now in 2nd edition.)
  • Algorithms on WikiBooks. (Open.. but spotty and strange in coverage. Maybe you can help!)