July 15 Handouts and Notes

In today’s class we’ll wrap up our worksheet on clustering and then we’ll prove that the algorithm we developed is optimal.

Announcements for today:

  • Assignment 2 is due tomorrow night.
  • We have some information about the midterm exam posted on Piazza.

Here are today’s clicker questions.

July 12 Handouts and Notes

In today’s class we’ll start on greedy algorithms. In our worksheet we’ll develop an algorithm for clustering photos.

Announcements for today:

  • Assignment 2 has been released and is due on Tuesday.
  • Tutorials today will cover how to write good pseudocode and a review of asymptotic analysis notation (big- and little-O/omega, etc.). A reminder to please attend your registered tutorial section if possible, as the earlier sections are nearly full and priority needs to be given to students registered in that section.
  • The second reading quiz on greedy algorithms is due on Sunday night. 

Here are the clicker questions from today’s class.

Assignment #2

Here is Assignment #2, due 11 pm on July 16. LaTeX source for the assignment will be posted on Piazza (because UBC blogs doesn’t allow upload of .tex files).

Protected: Assignment #1 Sample Solution

This content is password protected. To view it please enter your password below:

July 10 Handouts and Notes

In today’s class we will play with graphs.

Announcements for today:

  • The solution to Assignment 1 has been released on the course page. You will need a password to access it, which you can find on Piazza.
  • You have a quiz in tutorial today, so be sure to attend your registered tutorial section. Assignment 2 will be released today at 4:30 pm and be due on Tuesday July 16 at 11 pm.
  • The first reading quiz on greedy algorithms is due Thursday evening.

Here are the clicker questions from today’s class.

July 8 Handouts and Notes

Today we’ll start on our asymptotic analysis worksheet. We also have this handy-dandy handout on formal definitions in asymptotic notation. If we have time, we may also get started on graphs.

Notes/announcements for today:

  • Assignment 1 is due tomorrow night. Make sure you know how to log in and upload to Gradescope! You will have received an email invitation to your @ugrad.cs.ubc.ca email. If you can’t find the email, go to Gradescope and try to login as [your CSID]@ugrad.cs.ubc.ca and select “Forgot password?” to get a password reset link emailed you.
  • Today is the add/drop deadline. This is your last day to switch tutorial sections or to drop the course without a W standing.

Here are the clicker questions from today’s class.

July 5 Handouts and Notes

Today we’ll be working on the Resident Hospital Problem, which involves figuring out how to assign residents to different hospitals. Hopefully the problem will seem somewhat familiar to you…

Notes/announcements for today:

  • Assignment 1 has been released and is due on Tuesday. Be sure to check out the Piazza post on administrative rubric items so that you don’t accidentally lose points for something like a hard-to-read scan.
  • An invitation to the course Gradescope page has been sent to your @ugrad.cs.ubc.ca email address. We suggest you log in to Gradescope and submit something for Assignment 1 in advance of the deadline (you can resubmit as many times as you want before the deadline) to avoid any last-minute stress when you submit your assignment.
  • Remember to complete your Canvas reading quizzes. In the upcoming week you have quizzes on asymptotic analysis and graphs due on Sunday, and a quiz on greedy algorithms due Thursday.
  • You have tutorials this afternoon. There is no quiz in tutorial today. Instead, your TAs will go over mathematical proof techniques and some combinatorics review.

Here are the clicker questions from today’s class.

Assignment #1

Here is Assignment #1, due 11 pm on July 9.

After Wednesday’s class, you should be able to do questions 1 and 2, along with the first parts of questions 3 and 4. You should be able to do the parts of questions 3 and 4 that deal with reductions after Friday’s class (though we will post Friday’s lecture materials sometime on Thursday, so you can look ahead in that worksheet if you want to read about reductions early and get a head start).

July 3 Handouts and 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 tomorrow’s class, longer than usual since it’s the start of the term:

  • Sign up for our Piazza discussion board at http://piazza.com/ubc.ca/summer2019/cpsc320. You’ll need the access code, which was emailed to you last week (unless you joined the waitlist later than Friday), is on the Canvas landing page, and will be announced tomorrow in class.
  • Come to your registered tutorial tomorrow. There will be a graded quiz focused on asymptotic analysis and data structures.
  • Complete the reading quizzes due this week on Canvas. There are quizzes on the stable matching problem and the course syllabus due Thursday night, and on asymptotic analysis and graphs due Sunday night. (Future weeks will probably not have multiple reading quizzes due on the same day: this was unfortunately necessary for scheduling purposes as we cover several different units early in the term.)
  • Make sure you have run getacct and have your CS ID. You will need to activate your CWL at https://www.cs.ubc.ca/getacct/ to access our Canvas page.
  • Bring your iClicker to tomorrow’s class, or set up your phone/laptop to answer iClicker questions. If you are using your phone or laptop, our course code is CPSC 320, the title is Intermediate Algorithm Design and Analysis, and the term is 2019S2.

Meanwhile, here are the handouts for tomorrow’s class:

See you in class!
UPDATE (July 3): here are the introductory slides and clicker questions from today’s class.

Links to old exams and course offerings

Several old CPSC 320 offerings are still available online, and many of them have assignments, tutorial problems, and copies of old exams that you may find useful in studying for your exams (though solutions may not be posted publicly).

If you plan to study from previous exams, 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. We (the instructional staff) will not be familiar with every old assignment/exam problem and may not be able to answer all your questions about them. We will do our best to give guidance on next steps you might try, but don’t guarantee that we will know the answers. (This is really a concern about practicality: we simply don’t have the time to solve every algorithmic problem you might find in a previous course or elsewhere online.)

The worst thing you can do with practice exams is read the question, read the solution without struggling with the problems, convince yourself that you too could have solved them, and then go into your own exam with inflated confidence. Instead, work with these problems, write a complete solution (like you would in an exam), then compare against the solutions!

Below are some old exams or practice exams with available sample solutions:

Old course offerings are often available at http://www.students.cs.ubc.ca/~cs-320/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: