Syllabus

Introduction

This course is about introducing 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, brushing up on probability and combinatorics is helpful (e.g., at least the intro to the Wikipedia article on combinations), although what we need can be learned as the term progresses. You should also be comfortable reasoning using mathematical notation. You will also 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, graph traversal (depth-first and breadth-first search).

Tutorials

Tutorials are your time. They are neither required nor marked. Unless we run low on space, you are free to attend any tutorial (including attending multiple in a week). Unless you anticipate the course will be easy, we strongly recommend that you find a time and TA that works well for you and use this resource!

Tutorials will typically be hands-on, facilitated time working on assignment- and exam-like problems.

Evaluation

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

Assignments (7-10) 20%
Midterm Exams (2) 30%
Final Exam 46%
Lecture Pre-reading Quizzes (20-30) 1%
Best of the 4 previous parts 4%

To pass the course, you must obtain a 50% overall mark and, in addition, you must achieve a passing grade on your overall exam mark (i.e., the weighted average of the midterms and the final exam). Students who fail this weighted average will receive as their course grade the minimum of their normally computed grade and 45%.

Excellent performance on your final may improve your midterm exam marks using the “10% rule”. For each midterm exam, if your final exam mark is more than 10% higher than it, then we will replace the midterm mark with your final exam mark minus 10%. That is, if your final mark is f (a natural but mildly ominous-sounding choice of variable name), then each midterm mark m is effectively: max(m, f-10).

Each midterm contributes equal weight toward the midterm average. All assignments contribute equal weight toward the assignment average; however, your lowest assignment mark will be dropped.

Lecture reading quizzes will happen at the start of most lectures and be worth 1 point each. If q is the total number of quizzes over the term and you earn e points total, then your quiz grade will be min(100, 100*e/(0.8*q)). In other words, you only need to complete 80% of the quizzes to earn 100% on this component.

Finally, whichever of your assignment, midterm, final, and quiz averages is best will be worth an additional 4% of your course mark. (Since the quizzes should be relatively easy if you attend class and do the readings, this means you can earn a high mark on 5% of the course just by putting in organized effort. If, on the other hand, you want to skip all the lectures and manage on your own, you can do that instead and only lose 1%.. just please don’t land in the middle and regularly show up to lecture unprepared.)

To have a mark reviewed: staple a note detailing all of your objections to the marking to the assessment and submit this to your instructor no later than two weeks after the week the marked assignment/exam was returned (regardless of whether you actually collected your assignment/exam at that time). (For scanned exams, just submit a separate note, but include your ugrad login ID and student number.) The instructor will then review the marking; the instructor’s review decision is final and may either increase or decrease the assigned mark based on your objections or other aspects of the submission.

Important Dates

Family Day 9 February (Monday)
Midterm #1 TBD, but in the evening close to 10 February
Midterm Break 14–22 February
Midterm #2 TBD, but in the evening close to 12 March
Good Friday/Easter Monday 3 and 6 April
Final Exam We’ll know when you do! See UBC’s exam page.

Rough Topic Schedule

Here is a VERY rough schedule of topics and readings subject to change. We’ll post reading assignments on this blog as they come out.

  • Week 1: Introduction and asymptotic notation review. (Chapters 1 and 2.)
  • Weeks 2 and 3: Graphs and Greedy Algorithms. (Chapters 3 and 4.)
  • Weeks 4 and 5: Divide & Conquer Algorithms and Recurrences. (Chapter 5.)
  • Week 6: Catch-up or Get Ahead
  • Weeks 7 and 8: Dynamic Programming. (Chapter 6.)
  • Week 9: NP-completeness. (Chapter 8.)
  • Weeks 10–13: Catch-up or Fun Stuff (additional topics that we select)

Communication

We’ll post class and tutorial material and assignments as tagged blog posts here. Most other communication will go through our Piazza page. (You are expected to read our course’s Piazza “Announcements” daily! Personal questions you would rather not post privately on Piazza can go to cs320@ugrad.cs.ubc.ca for response by any staff member or to the individual staff member you wish to contact.

Assignments

There will be roughly eight written assignments during the term, possibly including a small amount of programming.

  • Submission: Assignments will be submitted in the CPSC 320 hand-in box. Box #32 in room ICCSX235. (#32 as in CPSC 320 without the 0.)
  • Schedule: Assignments will normally be due Mondays at 5PM unless indicated otherwise in the assignment handout.
  • Late Policy: Late work will receive no credit, but we may be flexible if you contact us promptly and well before a due date. So, tell us if you’re having trouble! (Remember, however, that we drop the lowest assignment mark.)
  • Collaboration: See the academic conduct guidelines.

Exams

There will be two midterms and one final exam. Straight memorization is not a course goal. So, exams will be open-notes and open-book. (Specifically, you’ll be allowed up to (the equivalent of) a 3-inch 3-ring binder of notes and 3 textbooks.)

Pending scheduling (i.e., appropriate rooms and sufficient time), each exam will have an individual and a group stage. Your overall mark on the exam will be the maximum of your raw individual mark and 85% of your individual mark plus 15% of your group mark. (However, to determine whether you pass the course, we will consider only your individual components, although we will use the 10% rule on individual scores for this calculation.)

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.

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 two, and we encourage you to do so! (Specific assignments may allow larger groups; any change will be stated in the assignment handout.) 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.
    • 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!)
  • 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 collaborate rather than, for example, working on individual parts of the assignment and stitching the result together. 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 for a lighthearted but well-researched perspective on pair work in Computer Science (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, please contact the instructor. If you are having problems understanding or keeping up with the material, please contact the instructor or a TA to discuss how we can fix the problem. Please don’t cheat! It sucks the soul from the course.

Textbook

Our required textbook (which we will follow closely!) is: John Kleinberg and Éva Tardos, Algorithm Design, Addison-Wesley Publishing company, 2005, ISBN 0-321-29535-8. (Note: Exams will be open-book.)

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 officially, the reading questions are based on 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, Third edition: Fundamental Algorithms, Addison-Wesley Publishing company, 1997, ISBN 0-201-89683-4.
  • Donald E. Knuth, The Art of Computer Programming, Volume 2, Third edition: Seminumerical Algorithms, Addison-Wesley Publishing company, 1998, ISBN 0-201-89684-2.
  • Donald E. Knuth, The Art of Computer Programming, Volume 3, Second edition: Sorting and Searching, Addison-Wesley Publishing company, 1998, ISBN 0-201-89685-0.
  • Donald E. Knuth, The Art of Computer Programming, Volume 4a: Combinatorial Algorithms, Part 1, Addison-Wesley Publishing company, 2011, ISBN 0-201–3804-8.