CPSC 320: Intermediate Algorithm Design and Analysis
2009 Winter Term 2
Handouts
Home
Calendar
Administration
Textbooks
Handouts
Assignments/Exams
Last week!
Anne Condon's RNA Secondary Structure notes
Sample final exam (see
Vista
)
Week 13
In-Class Notes (Thursday)
Week 12
In-Class Notes (Thursday + following Tuesday)
Minesweepeer is NP-complete
Tutorial 7 (for week 12)
Week 11
In-Class Notes (Thursday + following Tuesday)
(with final zig-zag case added after class as promised)
Slide Set #8: Splay Trees (for Amortized Analysis)
[
PPTX
] (updated w/ink)
Week 10
In-Class Notes (Tuesday/Thursday)
Python Fibonacci code
illustrating memo-izing and bottom-up dynamic programming
CodeLab "tour"
— the code practice system that uses (perhaps) a mysterious DP-like minimum edit distance algorithm along with large volumes of student-provided data to help correct students' submissions
Tutorial 6 (for week 10)
Week 9
Solution to question 6 from practice midterm from class
In-Class Notes (Tuesday/Thursday)
(Note: updated with Q4, multi-week tutorial)
Tutorial Handout #5
Week 6
Slide Set #6: Greedy Algorithms and Graphs
[
PPTX
] (updated with ink)
In-Class Notes (Thursday)
In-Class Notes (Tuesday; missing page 2, unfortunately!)
Tutorial Handout #4
Week 5 (Midterm #1 Week)
In-Class Notes (Thursday)
Week 4
In-Class Notes (Thursday)
In-Class Notes (Tuesday)
Tutorial Handout #3
Week 3
In-Class Notes (Thursday)
(Fun note: Skyline calculations are an optimization technique for a class of DB queries. Here's a paper on
Skyline Query Processing for Incomplete Data
.)
In-Class Notes (Tuesday)
Slide Set #3: Divide and Conquer and Recurrence Relations
[
PPTX
]
Tutorial Handout #2
Week 2
In-Class Notes (Tuesday)
Slide Set #2: Asymptotic Notation
[
PPTX
]
Tutorial Handout #1
Tutorial Solutions #1
Week 1
In-Class Notes (Thursday)
In-Class Notes (Tuesday)
Textbook treatment of Stable Marriage:
Chapter 1 of Kleinberg and Tardos
, pages 1–12. (An excellent text overall!)
Canadian Resident Matching Service Match Algorithm
[
PDF
]
"A capsule history" section of
The NRMP As a Labor Market: Understanding the Current Study of the Match
[
PDF
]
Slide Set #1: Intro
[
PPTX
]
Syllabus
[
PDF
from start of term]
cs320@cs.ubc.ca
