Algorithms to live by and why should we care

Talks

Elle Meredith

#programming-techniques

#decision-making

#data-structures

Algorithms to live by and why should we care

by Elle Meredith

In her talk titled "Algorithms to Live By and Why Should We Care," Elle Meredith discusses the significance of algorithmic thinking in everyday life, presented in accessible language.

Key Points Discussed:
- Definition of Algorithms: Algorithms are step-by-step instructions essential for accomplishing tasks, which can be seen in daily activities, such as cooking or navigating. Algorithms must be clear and detailed, especially when used in programming.
- Efficiency and Problem Solving: Effective algorithms must solve the intended problem efficiently, creating a balance between comprehensiveness and sufficiency.
- Examples of Algorithms in Life: Meredith highlights the importance of algorithms in various contexts, such as traffic control systems employing dynamic programming to optimize traffic flow (

00:00:00.240 Next up we have Elle Meredith. Elle has been writing Ruby and Rails for over ten years. She's currently a consultant at Blackmill and has previously been a Development Director at thoughtbot. Elle is passionate about communities and helping people work together better. She has organized Ruby conferences and Girls Who Code events in Australia and the United States.

00:00:31.480 For those of you who are going to the pizza-making party on Saturday, Elle and Lachlan are hosting that. Please welcome Elle to the stage.

00:00:41.600 Hi, everyone! Today, I want to discuss algorithms and why we should learn about them. So, what are algorithms? Algorithms are step-by-step instructions for accomplishing a task. We follow algorithms every day in activities like getting to work, making pizza, ice cream, or even baking bread. Many developers find baking bread satisfying because it involves just a few ingredients: flour, water, salt, yeast (either wild or commercial), and then time and temperature. The fun part is that you can mix them in various ways to achieve your final product: baked bread.

00:01:55.950 Algorithms used in computers or mathematics must be very detailed and resolve ambiguities that we encounter in our daily lives. For instance, when I ask you to make me a sandwich, most people understand what to do. However, when instructing a computer, you need to be more precise. You would say, 'Go to the cupboard, open it, take the bread out, bring it to the table, take a knife from the drawer, and slice two pieces.' An algorithm also embodies the pursuit of efficiency and perfection. The two essential criteria are that it should solve the problem you're addressing and do so efficiently. The question arises: how do we balance these two aspects to know when a program is good enough?

00:02:46.709 Not all algorithms are applied online; for example, one non-web use is in traffic control. It is estimated that intelligent traffic control systems can save billions of dollars yearly by reducing idling time at traffic lights and lowering fuel consumption. Traffic control systems rely on dynamic programming algorithms that consider the time needed for a car to pass through a series of traffic lights until it reaches its destination—a phenomenon often referred to as the 'Green Wave.' In everyday life, some algorithms are learned through experience, such as arithmetic, while others we figure out ourselves, like looking something up in a dictionary. Then there are the algorithms that require written instructions, such as recipes and driving directions.

00:03:34.860 We can condense the definition of an algorithm into one sentence: it is a precise, systematic method for producing a specific result. Now, why should we care? Algorithms can help us untangle very human questions and provide strategies for how to live our lives. They can guide us on making better decisions, handling overwhelming choices, and knowing when not to overthink a decision. They help us manage unknowns, incomplete information, and an uncertain future. They can assist in finding a partner or the shortest path to a destination.

00:03:59.900 In this talk, I’m going to introduce a few different types of algorithms and explore how we can work with them. Usually, in most job applications, candidates discuss binary search and its re-implementation for a job interview. So, let’s talk about that. Suppose we want to search for a word in a dictionary. If we’re looking for Ruby, we would probably start somewhere in the middle, rather than at the beginning and then start moving backwards or forwards. Binary search is an algorithm that takes an input of a sorted list of elements. If the element we are looking for is in that list, it returns the location or index of that element. If it doesn’t exist in the list, it returns null.

00:05:50.830 Let’s play a game. I’m thinking of a number between 1 and 100, and you can try to guess my number in as few attempts as possible. With each guess, I’ll tell you if your guess is too low, too high, or just right. If we start by guessing from the first number and go on, it will take a long time to get to the correct number. A better method would be to start at 50. If that's too low, we eliminate half of the options with just one guess. Then we take the range from 51 to 100 and guess the middle value again, gradually narrowing it down.

00:10:20.150 If we started with a hundred numbers and systematically halved the range, we could reduce our choices down significantly. For example, from 100 to 50, then from 50 to 25, and so forth until we identified the number—maximum seven steps to find the number we want. If we scale this up to a thousand numbers, we only need ten steps, and for a hundred thousand, we find the number in seventeen steps. The logarithm of a number shows us how many times we can divide it by two until we reach one. This illustrates the power of binary search to find elements in large datasets efficiently.

00:12:30.040 Next, let’s discuss optimal stopping. Suppose we are searching for a new place to live, aiming to maximize our chances of finding the best apartment available. How do we know if an apartment is indeed the best unless we have a baseline to judge it by? The more information we gather, the better decisions we can make; however, it may also lead to missed opportunities. This dilemma reflects a central theme in optimal stopping theories.

00:14:31.080 There’s a classic problem known as the secretary problem, where we are interviewing a set of applicants for a position, and our goal is to maximize the chance of hiring the best candidate. The key challenge is to avoid stopping too early or too late during the selection process. If we stop too early, we might overlook the best candidate; if we stop too late, we might settle for an applicant that is not the best. So, the optimal solution seeks to strike a balance between exploring options and making a decision.

00:16:43.250 The optimal strategy suggests exploring a predetermined amount of candidates to gather data without making a decision, after which we are prepared to commit to hiring any candidate that meets or exceeds the standard of the best candidate observed during the exploration phase. Research indicates that we should ideally look at about 37% of candidates before making a leap. This '37% rule' offers a good chance of selecting the best option under uncertainty.

00:19:18.740 Let me illustrate recursion next. Suppose we are exploring Grandma’s attic looking for a diary. Grandma tells us that it’s in a box, but upon opening the box, we find more boxes. One approach is to make a pile of boxes and, while the pile is not empty, keep grabbing boxes to search. This recursive thinking reminds us of Russian dolls where each box may contain another smaller box inside. For every item checked, if we find the diary, we are done; if we find another box, we continue searching recursively.

00:21:35.770 Recursion applies whenever a problem can be divided into smaller sub-problems that use the same solution method. A classic example of recursion is the calculation of factorials, where we need a base case to stop the recursion. We often visualize this through mathematical models.

00:24:12.110 Next, let's discuss sorting. If we want to alphabetize a collection of unsorted books, one basic method is the bubble sort, which is inefficient. A slightly better method is the insertion sort, wherein we place each book in the correct spot as we go. The best method is merge sort, and even more efficient is quicksort which operates by selecting a pivot and sorting the rest of the elements around it, leveraging recursion.

00:26:02.680 When it comes to decision making, the balance between sorting and searching is key. The more effort we apply to organization, the better equipped we are to handle ongoing tasks. In scheduling tasks, for instance, employing theories that minimize the sum of completion times can enhance overall efficiency.

00:28:43.490 Finally, let’s touch on design decisions. For instance, when deciding whether to marry, Charles Darwin made a list weighing the pros and cons of marriage against the burdens it would pose. His conclusion, marking 'Mary, Mary, Mary', illustrates the complexities of decision-making algorithms influenced by cognitive biases, reflecting the need for simpler heuristics in processing life's choices.

00:30:16.660 Thank you so much for your attention!

RubyConf AU 2019