Month: January 2017

Today we’ll start (or continue, depending on where your section is right now!) working with graphs. We’re going to play around with the concepts of “diameter” and “articulation point” just to get some experience with graphs. We’ll also spend some time with the DFS and BFS algorithms.

• Here are today’s notes on graphs, diameter, and articulation points.
• We need to spend a minute or two on some items from today’s pre-class quiz.
• The sample solution to the first assignment is out on the blog under the assignments category (and will generally be out immediately after the slightly late deadline we leave as slack in case you have technical troubles). You need the password posted on Piazza.
• The second tutorial quiz is coming in your next tutorial!
• Read Section 3.5 in the textbook for Wednesday.
• There is a pre-class quiz for Wednesday.

Today we’ll finish up asymptotic analysis and start working with graphs. We’re going to play around with the concepts of “diameter” and “articulation point” just to get some experience with graphs. We’ll also spend some time with the DFS and BFS algorithms.

• Here are today’s notes on graphs, diameter, and articulation points.
• The first assignment is due Friday at 10PM. A sample solution will be released tonight shortly after the deadline. (It’ll be password-protected with the password posted on Piazza.)
• The second tutorial quiz is coming in your tutorial next week!
• Read Section 3.4 in the textbook for Monday.
• There is no pre-class quiz for Monday.

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”).