This should be considered “just for fun” handouts, as long as you are confident you are capable of implementing something like LCS in whatever your favorite language is, given sufficient time.
With that caveat, here’s a PDF of our LCS implementation, with some extra embellishments toward the end, including patching the code we didn’t quite finish.
Today we’ll start talking about NP-completeness with special guest host and TA Raunak Kumar! Thanks, Raunak!
- Here are our notes on NP-completeness.
- Don’t forget that there’s an assignment due Thursday!
- Please read Section 8.2 and skim Section 8.10 for this coming Monday. Keep skimming 8.10 as we read each section. It will help to keep the problems straight in your head! (Note that we won’t discuss every type of problem categorized in 8.10, however.)
- No reading quiz for Monday. (It’s a long weekend; have fun, remember those who have served the country, but do think for at least a while about algorithms!)
Today we’ll work on dynamic programming in two dimensions.
- Here are the new DP in 2-D notes for today.
- For next lecture, please read section 6.5 in the textbook. (No reading quiz for Wed, however.)
- Tue/Wed tutorial students: remember the quiz this week!
- Everyone: get started on the so-far-released quiz/assignment questions.
Today we’ll continue with (and probably finish) our work on the change-making memoization/dynamic programming problem.
- Here are sample solutions for part 1 and part 2 (updated with corrections by Victoria and others; thanks!) of the notes.
- For Monday, please read Section 6.4 of Chapter 6. There will be a pre-class quiz (for which invitations have been sent by mail, as usual).
- Don’t forget to expect quizzes in next week’s tutorial.
We’ll continue to part 2 of memoization and dynamic programming.
- Here are the part 2 notes.
- For Friday, please read section 6.3 of the textbook, but there is no pre-class quiz. (PLEASE finish 6.1 and 6.2 at minimum ASAP, however, or class time will be far less useful than it should be!)
- Loads of midterm exam info has been posted on Piazza.
- Expect a tutorial quiz next week!
Today we move on to memoization and dynamic programming! This is a widely applicable technique that also lets us practice algorithm design and analysis, designing recursive solutions, and designing iterative solutions. Woo-hoo! 🙂
- Here are today’s notes (part 1 on Memoization and DP using the change example).
- For Monday, read Section 6.1.
- I will try to post a quiz, but the UBC Survey system is crashing for me. If I cannot post it by noon on Saturday, I won’t, but please work the problems anyway!
Here is the quiz:
- The recursive solution to the weighted interval scheduling problem has to make one key decision among two or more choices by trying all the choices and picking the best. What is the decision?
- Which among all the previous events will go before this event
- Whether or not to include this event in the solution
- Whether the next event’s start time is before this event’s finish time (i.e., they conflict)
- How do we figure out that there are only n+1 total possible sub-problems in the memoized solution?
- Because the only legal arguments to the algorithm are 0 through n.
- Because of the algorithm’s “for” loop going from 0 up to n.
- Because the algorithm runs in O(n) time.
- We’re working on grading the exam and will be done soon. However, scanning/handback is likely to take until roughly class time on Wednesday.
- There will be no quiz in next week’s class. Sorry! Too busy with exam prep/marking to get one together 🙁
I’ve written an overview of how some tools in combinatorics work, such as permutations, combinations and binomial coefficients. Reading the document may be useful if you’ve had trouble in previous classes counting the size of a possible solution space, when given asked to use a brute force approach.
Today we move on to divide and conquer! We divide! We conquer!
- Here are today’s notes on tug-o-war and median-finding.
- Be sure to read the other recent posts that include blank and solved copies of the Tuesday and Wednesday quizzes.
- Check out the sample solution to our clustering concluded notes.
- Don’t forget: quizzes on Monday in tutorial!
- For Friday’s class, please read 5.2-5.3 in the textbook.
- Complete the pre-class quiz by noon on Friday.
- There will be a midterm review session with Susanne and Raunak on Fri 14 Oct 5-6PM in our usual room (Swing 121).
- The midterm exam is coming soon (20 October). Check out our scheduling and room assignment information! Also, if you’re curious about little things like “am I allowed any notes in the exam”, you should really read the syllabus.
- Unwind from the midterm with PageRank For Real with Susanne Fri 21 Oct 5-6PM near our lecture room (Swing 105); bonus points available!