Category: Readings

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

• Here is a sample solution to our pagerank/clustering notes.
• For next time, read Sections 4.5-4.6.
• Complete the pre-class quiz before next time (by noon on Wed 5 Oct).
• Don’t forget next Monday (10 Oct) is Thanksgiving. No lecture or tutorial that day. (We do have a quiz next week, but the Monday group’s quiz will be at the start of the following week. More details coming soon.)
• 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. (In other words, one-up my clunky slips of paper!)

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.

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!

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.

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.

Today we’ll review and play with asymptotic analysis. These notes will have a different feel, as we’re not solving an algorithmic problem but performing analysis on algorithms (or, in some cases, performing bits and pieces of that analysis).

A few notes:

• Here are today’s notes on asymptotic analysis.
• Here is a handout describing little-o and little-ω notation.
• Read Section 3.1 of the textbook introducing graphs. (But, no pre-class quiz for Wednesday.)
• The add/drop deadline is Tue 20 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
• Fill out the optional start-of-term survey (by the add/drop deadline tomorrow!) to help me learn a bit more about you and help the department learn about our courses. It’s worth 2 bonus points!
• Today’s pre-class quiz went OK with some hiccoughs:
  • Functions like lg n and n lg n are within the class of “polynomial” functions as far as we’re concerned (because they’re upper-bounded by a polynomial).
  • Linear functions (like the simplest one: n) are definitely in the class “polynomial”!
  • If you thought it takes O(5^n) time to investigate all subsets of size 5 of a set of size n, be sure to read the chapter!

We’re in our new classroom today! (Swing 121)

We’ll continue working on the resident-hospital matching problem.

A few notes:

• Read Chapter 2 of the textbook for Monday. Most of this should be review! I think 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis.
• Finish Monday’s pre-class quiz. You may find that you can answer most questions without having to read the chapter. Please do at least skim the chapter anyway!
• Work on your assignment! It’s due Thursday.
• Register for a tutorial if you haven’t already.
• Go to tutorial! You’ll work on assignment problems, and some TAs are considering mini-lectures on topics that have been causing trouble.
• WARNING: Tutorial T1B (Mon 3-4PM) may move. We’re looking for a closer room to Swing. We think we’ve found one that’s at least a little better. KEEP AN EYE ON PIAZZA!
• Here’s a sample solution to our reduction notes.

• Pre-class quiz review: I really won’t curve down, and we should briefly discuss the outside-of-group collaboration policy.
• Reminder: you’re welcome to use screens (laptops, phones, etc.) for course-related tasks but not for anything else. Exception: if you’re sitting in the back row.
• A classroom switch (and allowing the waitlist in) is happening! We’re moving to Swing Space 121 as of Friday 16 Sep.
• And now off to the handout on reductions and stable marriage.
• For next class, read section 1.2 (but no pre-class quiz yet).
• The assignment version of the first tutorial quizzes has been posted and is due a week from tomorrow via handin.

Today we’ll finish the first stable marriage handout and start talking about the critical concept of reductions.

Important notes for today:

• In class starting today, you’re welcome to use screens (laptops, phones, etc.) for course-related tasks but not for anything else. Exception: if you’re sitting in the back row, you may do what you like with your screens (within legal limits). Please always keep the volume off. (Justification at end of message.)
• A classroom switch (and allowing the waitlist in) looks likely, more news ASAP!
• Here’s our new handout on reductions and stable marriage.
• The pre-class quiz went well. Despite being “any submission gets full credit”, the vast majority of people answered the first two pre-class quiz questions right, and a majority answered the third right. To the 40% of people who got the third one wrong: finish that worked example by Wed!
• For next class, review the syllabus.
• The next pre-class quiz is due by noon on 2016/09/14 (Wed) and is about the syllabus.
• The assignment version of the first tutorial quiz question has already been posted. Others will be posted as those tutorials finish (including the full assignment after the Wed tutorial).

Justification of our in-class screen policy: Research has shown that you inhibit your own learning (or at least grades) by using screens for unrelated purposes during class. But, you’re adults; so, that’s your choice. However, you also inhibit the learning of those around you, which you have no right to do. (Similarly, no smoking in the classroom, please.)