CPSC 320 2017W2 – Page 5 – The #1 Course to Beat Brute Force

January 21, 2018

Asymptotic Analysis Worksheet

Here’s a worksheet to briefly discuss asymptotic analysis, considering both comparison of growth rates of functions and analysis of algorithms. We’ll start in on this worksheet soon, and we may move through it very quickly.

Also, here’s a one-pager to review big-O notation, add little-o notation, and offer a way that limits can help you with these comparisons.

January 15, 2018

Readings for 2018/01/21

Before Sunday’s pre-class quiz (pquiz): Our upcoming readings for the week of Jan 15 to Jan 21 are: Sections 3.1, 3.2, 3.3, and 3.4. Sections 3.1-3.3 should be largely review, with section 3.4 providing a (hopefully!) new application area to explore.

(Readings will slow down after this week, as we exit “review territory” in the textbook.)

January 14, 2018

SMP Intro Worksheet Sample Solution

Here is a sample solution to the SMP/Intro worksheet.

January 12, 2018January 13, 2018

Assignment #1

UPDATE (2018/01/13, 9:30AM): Included group size maxima at top; fixed a minor typo; marked many problems as NOT GRADED. These make great practice, but we won’t mark them.

Here is the full assignment version of Assignment #1. (Here is the LaTeX source. It has a “.txt” extension because blogs.ubc.ca doesn’t allow upload of “.tex” files.)

This is due Monday 22 Jan at 10PM.

Please submit it on GradeScope. GradeScope invitations have already gone out. Please see the Piazza post on the subject for more information about that.

For reference, here are the collected quizzes and the collected quizzes with sample solutions.

January 9, 2018January 10, 2018

Unit 2 Worksheet: Reductions and Stable Marriage

Here’s our next handout on reductions and stable marriage. We’ll likely start this on Wednesday or Friday.

UPDATED: WED 2018/01/10 9:30AM. If you have an old copy, just take a quick look at the extra question in Trivial/Small Instances and the figure added in Promising Approaches. All other changes are minor.

January 8, 2018January 8, 2018

Readings for 2018/01/08 to 2018/01/14

Before Sunday’s pre-class quiz (pquiz): Read Chapter 2 of the textbook. Most of this should be review! Sections 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis. This is what you should be good at to be awesome computer scientists. Work through the asymptotic analysis worked example. Here’s the blank worksheet and the screencast solution.

January 5, 2018

Readings for 2018/01/08 and the first pre-readingquiz

Please finish Chapter 1 and watch and work through the Unequal Stable Marriage Problem video playlist. Here is a blank copy of the problem. (Suggestion: print the blank problem and try it, but after each major section or if you’re stuck even briefly, let the screencast help! This is not the way to study for an exam, but it will prepare you for class.)

This week and always, the pre-reading quiz also lists the readings it assesses in its description. So, if you’re ever in doubt, just check the quiz! (If we mess up and post different readings, just tell us on Piazza! 🙂

January 2, 2018January 2, 2018

First Day Notes

Welcome to CPSC 320!

Our overall course goal is to learn about a common and important set of problem types, algorithmic solution approaches, and analysis techniques, and to gain 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.

A few administrative notes for today, much longer than our usual since it’s the start of the term:

Sign up for our Piazza discussion board at https://piazza.com/ubc.ca/winterterm22017/cpsc320/ and read the welcome post there that has other important material! You’ll need the Piazza access code, which we’ll announce each day in lecture for the first week or so.
Get your @ugrad.cs.ubc.ca account set up. See https://www.cs.ubc.ca/getacct/.
Come to your registered tutorial this week (3-5 Jan) for some review problems to help get you ready for CPSC 320. Next week (10-12 Jan) there will be a graded quiz focused on stable marriage and algorithm/data structures design and analysis review in tutorial!
Do the pre-class reading for 2018/01/05, which is Kleinberg and Tardos Section 1.1. (Do get the textbook ASAP or be prepared to thoroughly study other resources on your own! Previous terms’ students have suggested that the international edition is equivalent but cheaper, although we cannot guarantee that’s true!)
Review CPSC 221/EECE 320, especially asymptotic analysis and very high-level data structure info (binary trees, self-balancing binary trees, heaps, hash tables, etc.).

Next, here are today’s handouts:

Slides used to introduce the course.
Stable Marriage Problem Worksheet (sample solution to be posted later)
How to Solve a 320 Problem
Gale-Shapley Algorithm
Canadian Resident Matching Service’s Match Algorithm page
“NRMP As a Labor Market” article about the genesis of the National Resident Matching Program

Finally, if you wish to read ahead, we expect to read at least these sections in this order (changes may happen but probably not drastic ones):

The rest of Chapter 1 (and, for every chapter we read, the chapter intro)
Chapter 2 (largely review), with emphasis on 2.3
Chapter 3
Sections 4.1-4.7 of Chapter 4 (a bit of which is likely review)
Sections 5.1-5.4 of Chapter 5, plus the Master Theorem on Wikipedia
Sections 6.1-6.6 and 6.8 (which is likely review) of Chapter 6
Sections 8.1-8.5, maybe 8.6, 8.7, 8.8, and 8.10 of Chapter 8. Note that 8.10 is useful to read early and reread as you work through this chapter.

December 28, 2017December 28, 2017

Welcome to CPSC 320!

Welcome to the website for CPSC 320 in 2017 Winter Term 2 (Jan-Apr 2018). We’re getting set up right now. Expect more as the term approaches. Looking forward to seeing you in January!!

In the meantime:

Please set up your @ugrad.cs.ubc.ca e-mail account, which you’ll need almost immediately for GradeScope submission of assignments and return of quizzes, assignments, and exams!
Be aware that we’re using Canvas (and not Connect) for the course. We’ll use it for pre-class quizzes (for you to take them and to return their results) and for recording bonus points. (Assignment submission and grading plus tutorial quiz/exam grading and return will be on GradeScope.)UBC asked that we include this message: “Dear student: Canvas is UBC’s new online learning platform, which will be gradually replacing Connect (Blackboard Learn) throughout the 2017/2018 academic year. Starting September 2017, the Faculty of Science began to host Science courses in Canvas. By September 2018, all the Faculty of Science courses will have moved to Canvas. At some point during the 2017/2018 academic year, you may have had, and/or will have Science courses in both systems (Canvas and Connect). To find out which of your classes will be in Canvas this January 2018, please check the Canvas course lists here: http://students.canvas.ubc.ca.