Lecture Notes 2016/09/19

Today we’ll review and play with asymptotic analysis. These notes will have a different feel, as we’re not solving an algorithmic problem but performing analysis on algorithms (or, in some cases, performing bits and pieces of that analysis).

A few notes:

  • Here are today’s notes on asymptotic analysis.
  • Here is a handout describing little-o and little-ω notation.
  • Read Section 3.1 of the textbook introducing graphs. (But, no pre-class quiz for Wednesday.)
  • The add/drop deadline is Tue 20 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
  • Fill out the optional start-of-term survey (by the add/drop deadline tomorrow!) to help me learn a bit more about you and help the department learn about our courses. It’s worth 2 bonus points!
  • Today’s pre-class quiz went OK with some hiccoughs:
    • Functions like lg n and n lg n are within the class of “polynomial” functions as far as we’re concerned (because they’re upper-bounded by a polynomial).
    • Linear functions (like the simplest one: n) are definitely in the class “polynomial”!
    • If you thought it takes O(5^n) time to investigate all subsets of size 5 of a set of size n, be sure to read the chapter!

Leave a Reply

Your email address will not be published. Required fields are marked *