Kashish Dugar

Today I read Grokking Chapter 8 about greedy algorithms.

What greedy means

Greedy means: take the best choice right now, and never look back. My Dijkstra was greedy too, because it always grabbed the cheapest place next.

My notes

Scheduling

If activities overlap, greedy picks the one that ends earliest. That leaves the most time for the rest.

I tested a different rule, “starts earliest”. With one long class (9 to 12) and two short ones in the middle, starts-earliest only got 1 class. Ends-earliest got 2.

I made my own schedule with Code, Kumon, AOPS, Gym and TV. I predicted on paper that greedy would remove Kumon.

My schedule table

Then I coded it. My find_earliest_end works like find_cheapest from Dijkstra;My find_earliest_function:

def find_earliest_end(last_end):
    earliest = float("inf")
    pick = None
    for activity in scedule:
        if scedule[activity]["start"] >= last_end and scedule[activity]["end"] < earliest:
            earliest = scedule[activity]["end"]
            pick = activity
    return pick

It printed [‘CODE’, ‘AOPS’, ‘GYM’, ‘TV’], just like my prediction! My second test got stuck in an infinite loop. I had typed an end time of 100 instead of 1100.

Where greedy fails

Greedy is not always best. If my bag holds 3 kg, greedy grabs the laptop (3 kg, ₹30). But a pencil and an eraser together weigh 3 kg and are worth ₹40.

AND and OR with real buttons

I built AND on a breadboard: two buttons in a line, and the LED only lights when I press both. At first it didn’t work, because a wire went around a button. I fixed it by tracing the rows.

My breadboard

Then I built OR: two buttons side by side, and either one lights the LED. I predicted pressing both would turn it off, but it stayed on. “One but not both” is a different gate called XOR.

What’s next

Make my scheduler move things later instead of dropping them, like I would in real life.