Let’s work some problems centering on pictures of Naomi. (The primary target of my image-capturing devices.)

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.

Our reading question was to determine for a particular interval in the following unweighted scheduling problem whether that interval would be considered by the textbook’s greedy algorithm before or after the interval labeled A. Which interval you needed to look at depended on your section and student #.

Just a brief handout playing with the importance of nodes in a graph.

A form for our results.

We had reading questions as well. For both sections, the question was “In the given graph, write down the letter of each node (A, B, or C) in the same strong component as your number (2nd digit of student #).” The graphs were:

• 8AM:
  
• 11AM:
  

Today’s playing with graphs handout (in PDF).

We had reading questions on graphs as well:

• 8AM: “If we start from the top node and always visit left children before right children where there’s a choice, which one would visit the node with the first (leftmost) digit of your student number on it first, depth-first search or breadth-first search?” In:
• 11AM: “A tree is a particular type of graph. If we consider the node numbered by the first (leftmost) digit of your student ID the root, is this graph a tree?” In:

• Asymptotic analysis and orders of growth problems handout.
• Some notes on Little-ο and Little-ω.

Our reading question on this set was essentially:

Consider the following problem: Given a list of n integers, determine whether any subset of ____ of the integers sum to 42.

Now, with a brute force solution, does this take polynomial or exponential time?

The blank in that was filled with “three” for one section and with “any size” for the other section. For “three”, the answer is polynomial time because we can construct a triply nested loop to produce all sets of size three and check each one in constant time. (For “four”, it would be a quadruply nested loop.) For “any size”, the answer is exponential because there are 2ⁿ subsets of n elements.

Today’s reading questions.

Today we’ll make the idea of a “reduction” (compiling one problem to another) clearer.

• Definitions and Exercises for Wed 2015/01/07
• Reading Questions for Wed 2015-01-07

Compiling a source language to a target language makes it so we can take advantage of the tools available for the target language (like running Java or Scala programs, both of which compile to Java Bytecode, on the Java Virtual Machine).

Similarly, reducing a source problem to a target problem means we can take advantage of all the tools available for the target problem, including algorithms that solve it. Basically, 320 is all about learning about a small number of (types of) problems that are good targets for reductions from all kinds of other problems.

Strange fact: Later, we’ll reduce a source problem to a target problem to take advantage of the things we know we CANNOT do in the SOURCE problem.

(Imagine we had a programming language that we KNEW couldn’t be run on any machine. It’s just too AWESOME. If you could write a compiler from the source language to a target language and you had a way to run programs in the target language, then that would mean you COULD run programs in the source language after all, but we know you can’t because of its AWESOMENESS. Therefore, what you’ve really just shown is that the target language is also TOO AWESOME to be run on any machine.)

• Intro Slides (not actually used in class!)
• Syllabus
• In-class notes (both very brief this time!)
  • 8AM
  • 11AM

Just for fun:

• A look back at the history of the stable marriage algorithm
• The Canadian Resident Matching Service’s description of the algorithm