Category Archives: Handouts

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.

SMP Intro sample solution

Here is a sample solution to the SMP intro worksheet.

2017/09/10: Readings, Handouts, and Notes

We’ll continue the first stable marriage handout and (maybe!) start talking about the critical concept of reductions on our next worksheet.

Important notes for today:

  • Here’s the intro SMP handout we’re continuing work on.
  • Here’s our new handout on reductions and stable marriage.
  • Please be sure to review the syllabus.
  • The next pre-class quiz is due by 10PM on Sunday (2017/09/17).
  • 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.
  • Come to tutorial for your tutorial quiz (tquiz). We’ll be particularly lenient in marking this tquiz since you’re just getting to know the format and we’re being pretty aggressive about what we’re assessing on it. In general, the tquizzes also aren’t worth much of your grade. (See the syllabus!) The point of these is to give you hands-on time working on exam-like questions in a timed context, followed by group time to reinforce and expand what you learned from your individual work.
  • The assignment version of the tutorial quiz questions will release shortly after Wednesday’s tutorial. Start looking those over and working on them! The assignment is due next Friday!

2017-09-08: Continuing SMP Intro Worksheet

Just a quick note to say that both sections are still working on the introductory SMP worksheet. See you tomorrow!

2017/09/06: First day notes

NOTE: We’re still figuring out whether we’ll separately post handouts and notes for each section or use one combined post. For now, here are handouts and notes similar to those both sections will use tomorrow. (If we split up by section, we’ll find a way for you to disentangle them easily!)


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/winterterm12017/cpsc320/ and read the welcome post there that has other important material!
  • Get your @ugrad.cs.ubc.ca account set up. See the announcement on the Piazza board for more details.
  • Come to your registered tutorial next week (the week of Monday 11 Sep). There will be a graded quiz focused on stable marriage and algorithm/data structures design and analysis review!
  • Do the pre-class reading for 2017/01/06, 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:

 

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.