Author: Steve

We’re continuing to play with graphs today. We may finish. Just in case, we also include a tiny set of fun notes on some mysterious definition of “the most important node” in a graph. Surely this definition isn’t the starting point for a modern juggernaut of the computing industry!

• Here is the fun handout on the “most important node” in a weighted, directed graph. (Note: There’s no sample solution to this, as it’s just a way to emphasize the value of exploring a problem and looking for a promising metric of what’s “good”.)
• Remember to attend your tutorial quiz this week. Also, you can get started on the assignment pieces as they’re posted after each tutorial. (The full assignment, with LaTeX source, will be posted after the last tutorial.)
• Finish reading Chapter 3 (so, 3.5 and 3.6, on directed graphs) for Friday.
• The pre-class quiz for Tuesday was rescheduled to Thursday. (Sorry for the mixed-up early deadline. Here’s hoping the extension comes as a pleasant surprise!)

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.