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:
- 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.
- Select and judge several promising paradigms and/or data structures (possibly slightly modified) for a given problem by analyzing the problem’s properties.
- Implement a solution to a problem using a specified algorithm design paradigm, given sufficient information about the form of that problem’s solution.
- 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.
- 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 Wednesday 3 January.
Tutorials roughly alternate between TA-facilitated sessions (often preparation for assignments/exams, supplementary material, or review of previous courses) and tutorial quizzes. Tutorial quizzes are low-stakes (see the grading scheme below) opportunities for timed, exam-like questions. They also set the stage for the assignment that follows them. (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 aware that you may be misjudging your abilities as a new learner. See the fascinating 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 (~5) | 23% |
| Midterm Exams (2) | 30% |
| Final Exam | 40% |
| Tutorial Quizzes | 2% |
| Pre-Class Quizzes | 2% |
| Best of the 5 previous parts | 3% |
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 average of the individual components of your midterm and final exams, weighted according to the table above). 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).
Each assignment, each tutorial quiz, and each pre-class quiz contributes equal weight toward their respective averages. However, your lowest assignment and lowest tutorial quiz mark will be dropped.
Pre-class quizzes will be due online roughly weekly and be scaled to 2 points each, where your grade will be rounded up to the next integer. (So, a 30% on a quiz would earn 1/2, and a 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 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, tutorial quiz, midterm, final, and pre-class quiz averages is best will be worth an additional 3% of your course mark.
(Since the pre-class quizzes are relatively easy if you do the readings, you can likely earn a perfect 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 and theoretically only lose 2%.. 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 pre-class quizzes and the final exam): use GradeScope’s regrade request interface no later than two weeks after the week the marked assessment was returned (regardless of whether you collected your assessment at that time). 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 pre-class quizzes, send a note by e-mail or private Piazza post to your course instructor. Be sure to include the name of the assessment (e.g., “Pre-Class Quiz #3”), your full name, your ugrad login ID, your student number, and all grading concerns, including your justification for why you should have received a different grade.
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 for CPSC 320 | 3 January (Wednesday) |
| Add/Drop Deadline | 17 January (Wednesday) |
| Midterm Exam #1 | 6 February (Tuesday) |
| Drop with W Deadline | 9 February (Friday) |
| Family Day | 12 February (Monday) |
| Mid-Term Break | 19–23 February |
| Midterm Exam #2 | 13 March (Tuesday) |
| Good Friday/Easter Monday | 30 March/2 April |
| Last Day of Classes | 6 April (Friday) |
| Final Exam | We’ll know when you do, but between 10 and 25 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 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 and Tutorial Quizzes
There will be ~5 written assignments during the term. All start as quiz questions in tutorial. So, the time working on the quiz in tutorial will “kickstart” your assignment work.
- Submission: Tutorial 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 GradeScope.
- Schedule: Tutorial quizzes will normally be every-other-week in tutorial. Assignments will normally be due Mondays at 10PM ~1.5 weeks 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 and tutorial quiz marks.
- Collaboration: See the academic conduct guidelines.
Exams
There will be two midterm exams and a final exam. Additionally tutorial quizzes will be run somewhat like exams.
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.
For evening midterm exams, 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 tutorial quiz: Tutorial quizzes occur during scheduled tutorial times, and we already drop the lowest tutorial quiz. So, we do not anticipate waiving a missed tutorial quiz unless there is a strong reason. If you miss more than one or have a strong reason, please do drop us a note (as a private Piazza note or to cs320@ugrad.cs.ubc.ca) to tell us why, and we’ll consider accommodation. NOTE: If you missed tutorial 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 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.
- 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!)