Author: Steve

Posted on

Handouts and Notes for 2017/01/11

We’re continuing with stable marriage with an eye to reductions today. No new handouts, but an old one and plenty of notes:

  • Pre-class quiz review: As of 3PM Sunday, this was going very well, with fictional clicker questions we’re supposedly asking in class causing the most trouble. (Well, and the soulless candy, but we said we’d give credit for that.) There are no clicker questions in class, and the worksheets aren’t graded… BUT CPSC 320 is a hard course, and the practice and mini-lectures you get in class will make a big difference to your success. So, please do attend!
  • And now off to the handout on reductions and stable marriage.
  • For next class, read section 1.2 (but no pre-class quiz yet). Be aware that the reading for Monday will be all of Chapter 2. That’s because much of Chapter 2 should be review. You may want to start early, however!
  • Tutorial quizzes are posting as each tutorial finishes. Start solving them, since your assignment will be composed of the tutorial quizzes! Your assignment will be due 10PM on 20 Jan (Friday).
Posted on

Handouts and Notes for 2017/01/09

Today 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 our new handout on reductions and stable marriage.
  • As of ~3PM (before the 10PM deadline), the pre-class quiz was going well. The vast majority of people (well over 80%) answered each of the three pre-class quiz questions correctly. Be sure to finish going through the worked example if you had trouble, and ask on Piazza if you’re still unsure about the quiz!
  • For next class, review the syllabus.
  • The next pre-class quiz is due by 10PM on 2017/01/10 (Tue) and is about the syllabus. We hope you’ll find this a lighter pre-class quiz :). It should already have been mailed to you.(There won’t be a pre-class quiz due Thursday. Yay!)
  • Before your tutorial, read the quiz pre-readings. These are (vague, wordy) problem domains that would take too much time to read and understand during the quiz.
  • The assignment version of the tutorial quiz questions will release shortly after each tutorial. Start looking those over and working on them!
Posted on

Notes for 2017/01/06

Today we continue the first stable marriage handout, although we may skip some pieces that you have a good sense of from the reading.

Brief notes on the pre-class quiz: The vast majority of students who took the quiz will earn 2/2. (We’re downweighting the hardest question, which (CORRECTION) just over half of students got correct: “Independent of execution order, with the same preference lists, a particular man always proposes to the exact same number of women.”) Thanks for doing the readings!

Next time, we expect to continue stable marriage but introduce reductions, which we’ll use frequently to relate one problem to another. (We’ll use reductions to solve new problems in terms of old ones. Intriguingly, we’ll also eventually use reductions in the opposite way: to establish that we don’t know how to (or cannot) efficiently solve new problems by relating them to—reducing to them from—old ones.)

Important notes for today:

  • Come to tutorial next week prepared for your tutorial quiz. The collected quizzes will become your assignment. (We’ll post each tutorial’s quiz question as the tutorial ends so everyone can start the assignment at the same time.)
  • Follow along with the worked example in the screencast (and 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.)
  • The next pre-class quiz is due by 10PM (CORRECTED!) on 2017/01/08 and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM today. It is about the worked example. (Our normal pre-class quiz pace will be ~1-2 per week, but the start of term is so exciting!!)
  • Also read the syllabus on the course website. Early next week we’ll have a light-weight pre-class quiz about it.

 

Posted on

Sample Solution to 2016/01/04 (SMP Intro) Worksheet

Here is a sample solution to the SMP intro worksheet.

Use it to review what you’ve worked through, sparingly to get yourself unstuck when you’re entirely stuck on a problem, and to catch up to where we are in class.

But… don’t just look at the solution before you try the problems and assume you’re good! You’ll learn best by working problems, not by confirming that someone else can do it 🙂

Posted on

Handouts and Notes for 2017/01/04

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 all three sections will use tomorrow. (If we split up by section, we’ll use categories so you can just click on your section’s category to get your section’s handouts/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/winterterm22016/cpsc320/. We e-mailed the signup code to you and will give it again in class.
  • Come to your registered tutorial next week (the week of Monday 9 Jan). There will be a graded quiz focused on stable marriage and algorithm/data structures review! (The small number of waitlisted students should pick a tutorial to go to and let the TA know they’re waitlisted.)
  • Do the pre-class reading for 2017/01/06, which is Kleinberg and Tardos Section 1.1. (The first chapter used to be available online but seems to have been removed, unfortunately! 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!)
  • Take the pre-class quiz before 10PM on 2017/01/05. The quiz invitation has been e-mailed to your @ugrad.cs.ubc.ca e-mail address and will be automatically resent at the end of the day on 4 Jan. So, configure your @ugrad.cs.ubc.ca e-mail address using https://www.cs.ubc.ca/getacct/.
  • 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.
Posted on

Old Exams for Practice

Here are some old exams and sample exams (from previous terms).

Several caveats apply: Our term’s exams and course may differ from these term’s exams and courses in important ways (beyond, obviously, the specific questions used!). We do not have additional materials related to these exams that might be missing. We have not recently reviewed these, and we don’t know how well they relate to what our term has done so far.

Some of these require the login “cpsc320” and the solutions password for our term or a previous one to access, which are posted on Piazza:

Old samples I found through online searches:

Old course offerings are often available at http://www.ugrad.cs.ubc.ca/~cs320/YYYYSP, where YYYY is the 4-digit year, S is the session (W or S), and P is the part (1 or 2, often missing in summer). Here’s a few:

Spam prevention powered by Akismet