Monthly Archives: October 2017

Assignment #3

Here is Assignment #3, composed of the collected tutorial quizzes, solutions to those quizzes, and some extra questions building on the quizzes for the assignment. (Here is LaTeX source, with a .txt extension so the blog lets us post it!)

Quick reminder on one question: a wBST is a BST. So, it has the search tree property. That should be important if you want to do operations that depend on the order of keys in the structure.

The assignment is due on Fri 27 Oct at 10PM. (Which is actually almost as spooky as the last due date on Fri the 13th, what with Halloween coming up.)

Please submit it on GradeScope.

Protected: Assignment #2 Sample Solution

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

Tug-o-War (Divide and Conquer) Worksheet

Here’s our worksheet on tug-o-war and divide-and-conquer algorithms.

Readings to finish for the week of Oct 15-Oct 21

Our upcoming readings for this week are: Sections 5.1 and 5.2 plus Wikipedia’s page on the Master Theorem, which put the more narrative description in 5.1 and 5.2 into a formulaic context.

Clustering Completed Sample Solutions

Here are sample solutions to the Clustering Completed worksheet.

First clustering worksheet sample solution

Here’s a sample solution to the first clustering worksheet.

 

Clustering Completed Worksheet

We’ve designed our clustering algorithm. Now, we need to prove it really works. Let’s finish working through clustering.

UPDATE: We replaced the last two problems of the worksheet. Here is the updated version of the clustering completed worksheet.

Readings to finish for the week of Oct 8-Oct 14

Sorry for the late posting on this one!

Our upcoming readings for this week are: Sections 4.5 through 4.7. Happily, the Canvas quiz has been up for several days and also lists the readings!

PageRank bonus worksheet

A tutorial and bonus mini-assignment (worth up to three bonus marks) on the PageRank algorithm has been posted. 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 I used in the session. (A warning that some of the plotting commands may not work as expected in Octave or older versions of MATLAB.)

Clustering Worksheet

We’ll spend a bit more time playing with graphs and Chapter 3 and see if it brings us to Chapter 4.

Here’s stage one of our clustering worksheet.