We’ll finish talking about the resident/hospital matching problem and start talking about asymptotic analysis!
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). That said, they’re in service, as always, of solving algorithmic problems!
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. However, the following pre-class quiz has been sent out already, if you want to get a start on it.)
- The add/drop deadline is Tue 17 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
- As of ~1PM on Saturday, today’s pre-class quiz was going well. The only question that was below a 70% correct rate was whether lg n is in the class of polynomial functions (in particular, the set of “efficient algorithms” or “efficiently solvable problems”).