Coffee & Algorithms: Graph Networks & Plagues!
“And the plague gathered strength as it was transmitted from the sick to the healthy through normal intercourse, just as fire catches on to any dry or greasy object placed too close to it. Nor did it stop there: not only did the healthy incur the disease and with it the prevailing mortality by talking to or keeping company with the sick--they had only to touch the clothing or anything else that had come into contact with or been used by the sick and the plague evidently was passed to the one who handled those things.”
Giovanni Boccaccio, the Decameron
This week we will continue our exploration of Karger's Algorithm to find the minimum cut necessary in a complex graph.
What We'll Do
Focus will be on implementation of Karger's algorithm, and testing to see how effective it is. We'll be implementing in python but with no screens, just whtieboarding :)
Plagues and the Minimum Cut
There are a lot of places to shoehorn the algorithm, but one of the most interesting that came to mind was diseases, particularly dramatic stuff like plagues!
The Bubonic plague spread through various trade networks. Could cutting some networks or implementing quarantines have been effective ways to stop it if people had known the cause?
Links
The Plague Network - Cornell University - https://blogs.cornell.edu/info2040/2019/09/23/the-plague-network/
Leper Colonies - https://en.wikipedia.org/wiki/Leper_colony
Boccacio's the Decameron - (we couldn't leave this week without a spice of literature :) - Brown University's Decameron Web
MAKE ALGORITHMS MEANINGFUL AGAIN
We think that programming is inherently fun, more fun than most any game. It pushes our minds and gives us fundamentals to tackle bigger problems. Algorithms are also great for learning new ways of doing things in different programming languages.
Somewhere along the way job interviews have made algorithms a joyless, high stakes exercise 🙁 . A lot of us never get to use algorithms in our daily work anyway, and they’re just plain fun.
BUT CAN ALGORITHMS BE ART?
Ideally you should be able to put your studies in a notebook. A few year ago one of our SudoRoom members even drew graph theory and cliques on the sidewalk around the neighborhood in a nearby park.
REQUIREMENTS
Adults 18 and over
Passion!
TIPS AND TRICKS
This is for people of all levels, since everyone is at all levels of practice. If you’re rusty on graphs, then start on your trees, and if you’re rusty on your trees, then brush up to linked lists.
If at any point you’re lost just speak up! Just work your way backwards if you get confused or are rusty! We did this with Jade at the algebraic data types workshop in Rust at our women and non-binary hacknight.