Month: January 2017

Today we’ll continue working on clustering of photos with a graph-based approach.

• Here is a sample solution to our clustering notes.
• For next time, read Sections 4.5-4.6.
• Complete the pre-class quiz before next time (by 10PM on Thu 2 Feb).
• Assignment #2 is due on Friday at 10PM on GradeScope.
• Just for fun: If you’re looking for implementation challenges, make an open-source web-based app for one of the problems below and post a link to the app and the source on Piazza for 1 bonus point (for an individual making a good version) or 2 bonus points per person (for a team making a very good version). (Not sure what web-based system to use or where to write it? I’m enjoying using Meteor on Cloud 9.)
  • The user uploads a set of photos and then drags a slider (or otherwise adjusts the desired number of categories) to see the photos auto-categorized into groups. (Choose and implement some good similarity metric between photos.)
  • A CPSC 320 student uses the app to learn about the random walk definition of a graph node’s PageRank. The app shouldn’t (only?) simulate the random walk for the student, but rather help the student walk through the algorithm for the random walk and understand what results it produces. (We’ve already got some good implementations of the walk itself; so, take it one step further by creating a visualization of some sort.)

Today we’ll start work on our categorization problem. Just one new note: read Sections 4.3-4.4 for Wednesday. (The next pre-class quiz isn’t due until Thursday.)

 

Today we’ll finish our kickoff exploration of graphs and move on to one or the other of the fun notes on the most “influential” node in a directed graph (AKA the Google Guide to How to Win at Search), and how to cluster nodes in an undirected graph (if an edge’s weight denotes similarity)?

• Here are the very brief “influential node” notes.
• Here are the clustering notes. (In case you’re wondering why you’re reading Chapter 4 and we’re still talking about graphs… these are also greedy algorithm notes! Graphs make an awesome domain for just about any algorithm.)
• Assignment #2 will be posted at 5PM and due Fri 3 Feb at 10PM on GradeScope. Be sure to indicate your whole group using GradeScope’s interface (not just by including the GradeScope login in your submission).
• For next time, please read Sections 4.1-4.2. (No pre-class quiz; the next one is due on Thursday 2 Feb.)
• 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 we checked!), by David Lowe, looks at how to find similar features between images using the SIFT algorithm.

We’re continuing to play with graphs today. We may finish. Just in case, we also include a tiny set of fun notes on some mysterious definition of “the most important node” in a graph. Surely this definition isn’t the starting point for a modern juggernaut of the computing industry!

• Here is the fun handout on the “most important node” in a weighted, directed graph. (Note: There’s no sample solution to this, as it’s just a way to emphasize the value of exploring a problem and looking for a promising metric of what’s “good”.)
• Remember to 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 the last tutorial.)
• Finish reading Chapter 3 (so, 3.5 and 3.6, on directed graphs) for Friday.
• The pre-class quiz for Tuesday was rescheduled to Thursday. (Sorry for the mixed-up early deadline. Here’s hoping the extension comes as a pleasant surprise!)