Category: Readings

Today we begin/continue working on a proof that our clustering algorithm is correct.

• Don’t forget this week’s quiz in tutorial!
• For next class, please read 5.1 in the textbook. No pre-class quiz, however.
• Midterm review session with Stephanie and Vaastav on Tue 14 Feb 5-7PM in MCML 166.
• After the extension due to snow, Assignment #2 is due Mon 6 Feb at 10PM. As always, a solution will be available on the course website shortly after the deadline.
• Here are our notes to wrap up photo clustering.

Today we’ll continue (and maybe finish!) our work on an algorithm for clustering photos.

• UPDATE on the last pre-class quiz: A minority of people correctly identified the greedy condition used in Dijkstra’s Algorithm. PLEASE GO BACK AND RE-READ THAT SECTION! If you have trouble with it, ask questions (in class, on Piazza, in office hours, etc.). You do need to learn not only from lecture and tutorial but from the textbook, and Dijkstra’s Algorithm is an example of a very important algorithm we expect you to learn about from the text! (Yes, we can ask about it on the exam.)

  Additionally, participation in online quizzes has been dropping. Remember these are graded, and if you do well on them, they can be 5% of your course grade. If you really want to ignore them, they’ll only be 1%, but (a) you need to do the readings anyway to prepare for the exams, (b) if you don’t do the readings before class, you’ll learn much less in class, and (c) you’ll have to fill in that other 4% with some other course element, which you’ll be doing much worse on if you don’t do the readings. So, do the readings and the pre-class quizzes. See the syllabus for more info on our grades.

• For next time, read Sections 4.7. No pre-class quiz, however.
• In case we get there, here’s a set of notes to wrap up photo clustering.
• There is a third quiz in tutorial next week, but there will be no follow-up assignment. Instead, use the quiz and problems as an opportunity to practice for the exam. (We’ll clarify where the grade for the “assignment” portion of this quiz/assignment comes from soon.)
• The midterm exam is coming up on Wed 15 Feb. We’ll post details about the exam (e.g., length of the individual and group stages and room assignments) on Piazza soon.

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!)

Today we’ll start (or continue, depending on where your section is right now!) 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 the assignments category (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 next tutorial!
• Read Section 3.5 in the textbook for Wednesday.
• There is a pre-class quiz for Wednesday.

Today we’ll finish up asymptotic analysis and 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.
• The first assignment is due Friday at 10PM. A sample solution will be released tonight shortly after the deadline. (It’ll be password-protected with the password posted on Piazza.)
• The second tutorial quiz is coming in your tutorial next week!
• Read Section 3.4 in the textbook for Monday.
• There is no pre-class quiz for Monday.