September 2016 – CPSC 320

Lecture Notes 2016/09/30

We’ll continue today to work on our categorization problem. Just one new note: read Sections 4.3-4.4 for Monday. (There’s no new pre-class quiz, but we’ll make sure to have one for Wednesday!)

UPDATE: We the instructional staff beg you to work in pairs on the assignment! First, you’ll learn more. Second, we will have more instructional resources to do things besides grade your assignment! (You can even solve it separately and then work together to form a single best solution from your two solutions!)

(Yes, you can still work in a group of three. We still reserve the right to be grumpy about it. But not as grumpy now that we’ve seen all the individual submissions on Assignment #1.)

Lecture Notes 2016/09/28

Today we’ll move on to two new questions about graphs: how do you find the most “influential” nodes in a directed graph (if an edge confers a small amount of influence from its tail to its head) AKA the Google Guide to How to Win at Search, and how do you cluster nodes in a graph (if an edge’s weight denotes similarity)?

Here are today’s notes.
Your assignment is posted and due Thu 6 Oct at 10PM on handin (under assn2). (Note the later due time!)
For next time, please read Sections 4.1-4.2. (No pre-class quiz.)
Just for fun: We’ll try a little in-class experiment. Here’s a form for our experimental results.
Just for fun: Our algorithm isn’t Google’s, but it computes the same PageRank quantity.
Just for fun: UBC CS’s most cited paper (last I checked!), by David Lowe, looks at how to find similar features between images using the SIFT algorithm.

Assignment/Quiz 2, Wed Noon Edition and Full Version

A few items this time:

The Wed noon quiz edition, which I think someone wanted for some reason (vs. just the full assignment). Algorithm 4 is new for the assignment.
The Full Assignment #2.
The Full Assignment #2 LaTeX source (with a .txt extension for UBC Blogs’ benefit).

Again, READ THE ACADEMIC CONDUCT GUIDELINES! Learn by collaborating! However, while we hate having to prosecute cheating cases, we do so when you ignore these guidelines. If in doubt, ask!

Assignment/Quiz 2, Tue 1PM Edition

Here’s the Tue 1PM Quiz in its assignment version. (Centrality is new on the assignment.)

Assignment/Quiz 2, Mon 3PM Edition

Here’s the Mon 3PM Quiz in its assignment version. (The “Even More Exhausted” questions are new on the assignment.)

Lecture Notes 2016/09/26

We’re continuing our work with graphs today.

Here’s a solution to today’s notes.
Attend your tutorial quiz this week. Also, you can get started on the assignment pieces as they’re posted after each tutorial. (The full assignment, with LaTeX source, will be posted after Wednesday’s tutorial.)
Finish reading Chapter 3 (so, 3.5 and 3.6, on directed graphs) for Wednesday.
Finish the pre-class quiz for Wednesday. (Already sent.)
I’m still working on that screencast about asymptotic analysis. Sorry; sick child all weekend 🙁
Non-CPSC 320 info: Career Days and the Graduate & Professional Schools Fair are at the AMS Nest on September 28 and 29 from 10:00am to 3:00pm. See students.ubc.ca. 3rd year students interested in grad school may want to pay particular attention so you’re ready to apply next fall!

Assignment/Quiz 2, Mon 9AM Question

Here’s the Mon 9AM Quiz in its assignment version. (Naive correctness and the bonus reduction problem are new.)

Lecture Notes 2016/09/23

Today we’ll start working with graphs. We’re going to play around with the concepts of “diameter” and “articulation point” just to get some experience with graphs. We’ll also spend some time with the DFS and BFS algorithms.

Here are today’s notes on graphs, diameter, and articulation points.
We need to spend a minute or two on some items from today’s pre-class quiz.
The sample solution to the first assignment is out on the blog under assignments (and will generally be out immediately after the slightly late deadline we leave as slack in case you have technical troubles). You need the password posted on Piazza.
The second tutorial quiz is coming in your tutorial at the start of next week!
Read Section 3.4 in the textbook for Monday. I may also manage to post another video of a worked example over the weekend, which would be good to read. (Sick child at home; we’ll see how that plays out.)
There is no pre-class quiz for Monday.

Protected: Assignment #1 Sample Solution

Lecture Notes 2016/09/21

We’ll finish up our review of asymptotic analysis today. Don’t spend the whole day on that crazy square-root-of-n-to-the-square-root-of-n function! 🙂

A few notes:

The first assignment is due Thursday (tomorrow) at 5PM on handin. Click the “assignment” category on the blog to see more information! Name your PDF file solution.pdf.
Our second tutorial quiz will happen in tutorial next week, with the same format as this tutorial quiz. Likely topics include stable marriage, reductions, asymptotic analysis, and graphs.
Read Sections 3.1-3.3 in the textbook and complete the pre-class quiz for Friday. (Invitations have already been sent.)
Here’s a sample solution to our asymptotic analysis notes.