Category: Handouts

Here are sample solutions to our live-coding exercise on Deterministic Select in various formats:

• as a webpage
• as a Jupyter Notebook
• as a Python file
• as a PDF

Here are sample solutions to our divide-and-conquer (quickselect) worksheet.

We don’t code a lot in CPSC 320, and that’s intentional. You have lots of coding classes in CPSC. Reasoning about problems, writing about them on paper or whiteboards, designing and analyzing solutions: these are all incredibly important skills to be a successful Computer Scientist, no matter what work you take on.

However, now and then, it’s fun to code. Especially when an algorithm is so completely bizarre that it’s hard to believe it works without trying it.

Enter Deterministic Select.

We’ll do our best to code this rather intricate algorithm live, after working through the ideas that lead up to it. It could even work!

If you’d like to follow along, try opening https://ubc.syzygy.ca. You can then download our blank DSelect Jupyter Notebook to your computer, start your Syzygy server, and use the “Upload” button to upload the notebook onto syzygy. Use the “play”, “up”, and “down” buttons on syzygy to run code and navigate among the cells.

You can also see blank copies in plain python, PDF, or HTML.

Here is the worksheet on an efficient median-finding algorithm.

Here are sample solutions for our clustering worksheet: part 1 (developing the metric and algorithm) and part 2 (proving optimality of the algorithm).

Here’s a worksheet on proving our clustering algorithm optimal.

Here are sample solutions to the graph play worksheet. Note that these solutions take one particular approach (particularly with respect to representation) that may be very different from both what you did personally or your lecture section did!

Here’s one version of a worksheet on clustering images. We’ll work a bit more on this same problem for our next worksheet.

Patrice and Steve each use their own images for clustering. 🙂

Here is a tutorial and bonus mini-assignment worth up to three bonus marks on the PageRank algorithm. It’s based on the material in today’s PageRank session. If you weren’t able to make the session, there should be enough information in the walkthrough for you to be able to take a stab at the questions anyway.

If you’re interested, here is a zip file of the MATLAB functions Susanne used in the session. (A warning that some of the plotting commands may not work as expected in Octave or older versions of MATLAB.)

We’ve put a totally optional submission target for this on GradeScope (should appear later today). It’s due on 2 March to give you plenty of time 🙂

We don’t supply any specific solutions to the PageRank worksheet. The goal was to frame a famous problem in graphs yourself, in particular noticing that an ill-defined English notion like “biggest bigwig” can lead to various well-defined metrics that in turn lead to very different algorithms.