The introduction talked about the sort of hazy nature of the definition of what precisely a “greedy algorithm” is–but it defined greedy algorithms as “builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion.” The section proper outlines a greedy stays ahead proof, illustrating by example with the interval scheduling problem, and did the “let's look for a suitable measure” query that happened in the lecture, too. I used this section mainly as sort of a reference/model for my answer to number 1 on the problem set–but that didn't work out very well. A lot of the material was dense information about the details of the proof for the specific problem, and it was hard to pick out the parts of emphasis on strategy in general. Like, in problem one, my main issue was coming up with a measure that I could use throughout the algorithm to measure progress–it seemed really natural to do in the interval scheduling problem, and the section couldn't really help me with that. Maybe stuff was there, but I spent so much time looking for the information about strategies for proofs in general because it was all buried in the specific example.

I give it a 5/10 for readability.

This section talked about greedy exchange proofs. This problem helped me a lot more with problem 2 than 4.1 helped me with problem 1–but I don't know whether it's whether the section is any better or not, or if it's just that this kind of proof is a lot more natural for me, or maybe it's just that the problem for number 2 is closer to the maximum lateness problem than the interval scheduling was to the truck problem…it's pretty much just total lateness, I guess. But there are inversions, and there's a overall measure thing that you have to prove that inversions don't mess with in the wrong way. One especially helpful insight was that there are n choose 2 possible inversions – that'll help me in my efficiency analysis.

Another I was thinking about while reading the text is how the proof extends for pages–I'm not entirely sure I should be modelling my proofs after the ones in the textbook, because the textbook proofs are explanations, not just demonstrations of truth–it's geared more towards education than simply proving. To put it another way, like, I don't need to explain the concept of greedy measures to you when I'm writing a proof to turn in to you. You get them already, you teach this stuff. I should focus on writing a clear and simple proof–like I'm writing for an academic (which I am.) But I'd love to be able to model my proofs on examples of that, without all the educational explaining concepts to me

I give it a 6/10

Man, we aren't doing this one. Bummer.

This section overviewed Dijkstra's algorithm. It was pretty easy to follow considering I was exposed to this in 112 and during lecture. There was an interesting analogy, the authors compared Dijkstra's algorithm to a system of pipes where the edge lengths are the weights and then a droplet of water falls and creates a wave that expands at constant speed. That's an interesting way to think about it–they talk about how it's sort of a “continuous version” of depth-first search. It runs in O(n log n) though, not O(n). They also provided two proofs for correctness, one with all the exposition and another one with just inequalities.