Author Archives: Steve

Lecture 2016/10/26

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!

Lecture 2016/10/21

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.
  • 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 🙁

Lecture 2016/10/17

Today we continue our work on divide-and-conquer.

  • The last blank and solved versions of the quizzes have been posted (or will pop up by classtime).
  • For Wednesday’s class, no new reading. Instead, review for the exam! However, if you want to get ahead, please read section 6.1 on the unbelievably awesome idea of memoization. (Trade polynomial memory for exponential speedup!)
  • 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!

Lecture 2016/10/14

Today we continue our work on divide-and-conquer.

  • We continue to post blank and solved versions of the quizzes as they finish.
  • Don’t forget: quizzes on Monday in tutorial!
  • For Monday’s class, please read Section 5.4, plus the Master Theorem entry on Wikipedia.
  • No pre-class quiz for Monday. But if you don’t do the reading, you’ll wish you had. The Master Theorem will make your life so much easier!
  • There will be a midterm review session just after class today with Susanne and Raunak!
  • 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!