Today’s reading questions.
Read Before 2015/01/12 Class
- Review Chapter 2 with special emphasis on Section 2.3. (2.3’s a kind of summary of all of CPSC 221: using data structures to implement algorithms and understand/improve their performance.)
Reading Question Template
In case you’d rather not start from a blank sheet of paper for reading questions, feel free to print and fill in this Reading Question Template.
Slides #2
Today we’ll make the idea of a “reduction” (compiling one problem to another) clearer.
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.)
Assignment Cover Sheet
PDF: cover page
Assignment #1
PDF document: Assignment #1
Due Monday 2015/01/12 at 5PM in our submission box.
- Use the assignment cover page.
- Read the academic conduct guidelines or expect horrendous consequences for you.
- Please work with a partner; you’ll learn more, and we’ll spend less time on marking and more on making the course awesome.
(Submission box location to be posted soon!)
Read Before 2015/01/09 Class
- Section 1.2
Read Before 2015/01/07 Class
- Section 1.1
Note that the first chapter of the textbook is available online, but get the textbook ASAP!
Slides #1
- Intro Slides (not actually used in class!)
- Syllabus
- In-class notes (both very brief this time!)
Just for fun:
- A look back at the history of the stable marriage algorithm
- The Canadian Resident Matching Service’s description of the algorithm