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 Monday 12 September.

Tutorials roughly alternate between review periods (review of the previous week and practice for the next) and quizzes. The quizzes are “low-stakes” in that your quiz grade will be a small fraction of your grade on a follow-up assignment. (So, you could skip tutorial at the expense of a small amount of credit. Unless you anticipate the course is easy, you should attend! If you do think it’s easy, be sure you understand the Dunning–Kruger effect.)

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/Quizzes (5-8) 25% Midterm Exam 25% Final Exam 45% Pre-Class Preparation Work 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 exam mark (the weighted average of 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 work will be collected either online at noon on the day of 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 assigned prep missions (because “mission” sounds awesome, and `p` is a less ominous letter) over the term and you earn `y` points total, then your pre-class prep grade will be `min(100, 100*y/(0.75*2*p))`. In other words, you only need the equivalent of full marks on 75% of these to earn 100% on this component. However, the hands-on nature of class time means I 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 prep missions should be 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, on the other hand, you want to skip all 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): staple a note detailing all of your objections to the assessment and submit this 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). (For online returns like scanned exams, just submit a separate note, but include your ugrad login ID and student number.) The instructor will 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. 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

 Add/Drop Deadline 20 September (Tuesday) Thanksgiving 10 October (Monday) Drop with W Deadline 14 October (Friday) Midterm Exam 20 October (Thursday) Remembrance Day 11 November (Friday) 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 very much ubject 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.

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 roughly six written assignments during the term, possibly including a small amount of programming. All will 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. (We reserve the right to make the quiz marking scheme more generous than the corresponding assignment marking scheme.)

• 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 Thursdays at 5PM 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, which we have for the midterm exam so far), 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.) EXCEPTION: the in-tutorial group stage of quizzes will be just 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 so we 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.

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

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