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 will 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 Tuesday 10 January.

Tutorials roughly alternate between review (of the previous week and practice for the next) and quizzes. Quizzes are low-stakes; your quiz grade will be worth 5% of your grade on a follow-up assignment. (So, if you think the course is easy, you could skip tutorial at the expense of a small amount of credit. However, if you do think the course is easy, be sure you understand the Dunning–Kruger effect.)

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/Quizzes (5-6)	25%
Midterm Exam	25%
Final Exam	45%
Pre-Class Preparation Quizzes	1%
Best of the 4 previous parts	4%

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

We use the “10% rule” for midterms: If your final exam mark is more than 10% points above your midterm exam mark, we replace the midterm mark with the final mark minus 10% points. So, if your final exam mark is f (a natural but mildly ominous-sounding letter), then the midterm mark m is: max(m, f-10).

All assignments/quizzes contribute equal weight toward the assignment/quiz average; however, your lowest assignment/quiz mark will be dropped.

Pre-class preparation quizzes will be collected online at 10PM the day before lectures with assigned work (with submission links e-mailed to your @ugrad.cs.ubc.ca address) and be worth 2 points each. 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 hands-on nature of class time means we expect you to prepare for each class so you can learn and contribute!

Finally, whichever of your assignment/quiz, midterm, final, and pre-class prep averages is best will be worth an additional 4% of your course mark.

(Since the pre-class quizzes are relatively easy if you do the readings, you can earn a high mark on 5% of the course just by putting in organized effort. If instead you want to skip the lectures and manage on your own, you can do that instead and theoretically only lose 1%.. just please don’t land in the middle and regularly show up to lecture unprepared. Also, bear in mind that “In Theory, Theory and Practice are the same. In Practice, they differ.” Put another way: Skipping lectures is wonderful preparation for failing the course.)

To have marking of any assessment reviewed (except the final exam): send a note detailing all of your objections to the assessment to your instructor no later than two weeks after the week the marked assessment was returned (regardless of whether you collected your assessment at that time). Be sure to include the name of the assessment (e.g., “Assignment #3”), your full name, your ugrad login ID, and your student number. The course staff will review the marking. Our review decision is final and may either increase or decrease the assigned mark based on your objections or other aspects of the submission. For the final exam, there will be a period to review the exam with the instructor to learn from it. For marking disputes, see UBC’s Review of Assigned Standing policy.

Important Dates

First Day of Classes	3 January (Tuesday)
Add/Drop Deadline	17 January (Tuesday)
Drop with W Deadline	10 February (Friday)
Family Day	13 February (Monday)
Mid-term Break	20–24 February
Midterm Exam	15 February
Last Day of Classes	6 April (Thursday)
Final Exam	We’ll know when you do, but between 10 and 28 April

Rough Topic Schedule

Here is a VERY rough schedule of topics and readings very much 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 (including yours!) 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.

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).

Assignments/Quizzes

There will be ~5-6 written assignments during the term. All start as quiz questions in tutorial. Your mark on your (individual) quiz submission is worth 5% of your mark for the whole assignment/quiz. The other 95% comes from your (optionally group) submission of solutions to all the quiz questions plus occasional extra questions we add.

• Submission: Quizzes may only be submitted in your registered tutorial during the time set aside for the quiz. (Arrive on time!) Assignments will be submitted via handin.
• Schedule: Quizzes will normally be every-other-week in tutorial. You must attend your registered tutorial! Assignments will normally be due Fridays at 10PM the week after their corresponding tutorial quiz, unless indicated otherwise on specific assignments.
• Late Policy: Late work will receive no credit, but please contact us promptly if you believe you’ll be late. We may be flexible, and even if we’re not, we will try to be helpful. Remember, however, that we already drop the lowest assignment/quiz mark.
• Collaboration: See the academic conduct guidelines.

Exams

There will be a midterm and a final exam. Additionally tutorial quizzes will be run like exams (with an exception mentioned below).

Straight memorization is not a course goal. So, quizzes and exams will be open-notes and open-book. (We intend for you to bring what you want, but if you push boundaries, we’ll hold you to bringing 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. EXCEPTION: the group stage of quizzes will be for practice and not collected or marked for credit.

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.

Furthermore, the midterm exam is an evening exam. So, we will accept any reasonable scheduling conflict as an excuse for missing it. (Here’s the boundary line between unreasonable and reasonable: If you see tickets to a concert during the exam time that sounds pretty cool after the term starts (and we have posted the exam date), that’s an unreasonable excuse. But, if you already bought tickets to that pretty cool concert before the term started, that’s a reasonable excuse.) That said, we strongly encourage you to write the exam, as accommodation may just involve back-calculating a midterm grade for you from the final exam.

Missing a quiz: We already drop the lowest assignment/quiz, and the quiz component is worth only a small percentage of the assignment/quiz. So, we do not anticipate waiving a missed quiz. If you miss more than one, please do drop us a note (at cs320@ugrad.cs.ubc.ca) to tell us why, and we’ll consider accommodation. NOTE: If you missed quizzes and then did not submit the corresponding assignments, you must have missed a large chunk of the term. Your reason should explain that.

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 (but not quizzes) in groups of up to three. We encourage groups of two! We grumblingly allow groups of three. 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 (but not the 5% for the quiz) that applies to every group member. We urge you to work collaboratively on the assignment like the group portion of the exam: 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/Quizzes 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 (i.e., in the group sections).

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. (Note: Exams will be open-book.) 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!)