00:00:10.969
I want to talk about algorithms today: what they are, why we want to use them, and a few examples. An algorithm is a list of instructions for completing a task and we follow algorithms every day. We use them for activities like getting to work, making ice cream, or baking bread. For example, many developers enjoy baking bread because it involves mixing five or six ingredients: flour, water, salt, yeast, time, and temperature. You combine these in various ways to create your final product. I baked bread two weeks ago.
00:01:02.850
Algorithms are used in computers and mathematics and must be very detailed to resolve the ambiguities we often take for granted in our daily lives. For example, if I say to you, 'Go and make me a sandwich,' you know what to do—sort of. You would probably ask what I want on it, but you have a pretty good idea of how to make a sandwich. When telling a computer how to make a sandwich, however, you need to be much more specific. Instructions like 'grab the finer bread knife, slice two pieces of bread, butter one side on each, and slap them together' are necessary. Computers require detailed instructions. An algorithm also embodies the search for efficiency and perfection; its two most essential aspects are solving the problems at hand and doing so efficiently.
00:01:41.939
We always need to find the balance between these two aspects and know when to stop. Is a program 'good enough', or can it be better? Not all algorithms are used online, as many non-web applications are common. An example is intelligent traffic control systems, which can save billions of dollars a year by reducing idling time at traffic lights. These systems rely on dynamic programming algorithms that account for the time needed for vehicles to pass between signals until reaching their destination—what we commonly call the 'Green Wave.' In everyday life, we encounter algorithms we learn, such as basic arithmetic, some we derive ourselves, like looking up a dictionary definition, and others that are preset instructions like recipes or driving directions.
00:02:29.040
If I were to define an algorithm in one sentence, it would be a precise and systematic method for producing a specific result. Algorithms can help us address very human questions, giving us strategies for how to live our lives. They can explain how to sharpen our instincts, handle overwhelming choices, and know when not to overthink a decision. They also help us deal with unknowns, incomplete information, and an unforeseeable future. Moreover, algorithms can aid us in finding a partner or the shortest path to a destination.
00:03:03.120
In this talk, I want to introduce different problems and various algorithms we can use to solve them. Let's start with a common question from job interviews: 'When will we ever need binary search?' Suppose that we are searching for a word in a dictionary. For instance, if we search for the word 'Ruby,' we would open the dictionary roughly in the middle to ascertain whether it is listed before or after 'R.' From there, we adjust. Binary search operates similarly; it takes input from a sorted list of elements, returning the index of the element if it exists in the list and indicating it cannot be found if it doesn't.
00:03:45.930
For a different example, I could think of a number between one and a hundred, and I ask you to guess it using the fewest guesses possible. With each guess, I would tell you if you’re too low, too high, or just right. If you started by asking, 'Is it 1?' I'd say too low. If you then asked about 2, 3, or 4, they would all be too low, resulting in inefficient guesses. Instead, a better approach would be to first ask if it’s 50. If I say too low, you’ve eliminated all numbers below, quickly narrowing your options. Each time you halve your possibilities until discovering the target number. Starting from 100, it takes seven steps to conclude. If we raise the number to 1,000, we narrow it down to 10 steps; for 100,000, about 17 steps. This efficiency comes from using binary logarithms.
00:05:36.600
Now let’s say we are looking for a new apartment, but how do we know if it’s the best? We need to establish a baseline, which may entail initially losing a number of apartments that we could have considered our best. The accumulation of information improves our judgment when opportunities arise, yet this process may cause us to miss the best one. The situation is similar when finding a significant other while practicing serial monogamy—determining if we’ve met enough individuals to identify our best match becomes a fundamental dilemma. This is a problem frequently referred to as optimal stopping.
00:06:36.180
The secretary problem exemplifies this issue, where we want to hire the best candidate from a pool of applicants. The two ways to fail in this scenario are stopping too early and missing top candidates or stopping too late, potentially settling for less ideal options. The optimal strategy requires finding a balance between these options and establishing a plan for exploration without making decisions prematurely. The recommended approach is to look for 37% of the options available to gather data and then commit to the next best candidate after that point. This 'magic number' stems from statistical research.
00:08:34.390
In cases where we have complete information, the optimal stopping guide allows us to decide once we meet a predefined threshold. However, when we don’t know all our options, it lends itself to the quandary of timing and decision-making pressure. Consider searching for a diary among your grandmother’s belongings, where each box leads to more boxes. One approach is a depth-first search, where you systematically go through until you find the diary. But a refined method involves using recursion to help manage the process effectively—just as Russian dolls contain smaller ones within, you can reduce the problem consistently until you reach the final resolution.
00:09:49.450
Next, suppose we’re attempting to organize a collection of books by title order. A natural approach is to scan the shelf for out-of-order books, which is inefficient and is known as bubble sort. We can enhance this method by utilizing insertion sort, where we sort items as we place them efficiently, or even merge sort, where we divide and conquer our batches of books. However, I want to introduce quicksort—here, we pick a pivot element and categorize the rest based on whether they fall to the left or right. Then, recursively, we sort the smaller piles until we're ready to combine them back into a singular, sorted arrangement.
00:11:03.390
While exploring sorting algorithms, we must consider whether we should sort our items at all, as the effort to sort versus the time spent searching after is crucial. Sometimes, sorting can take more time than simply searching through a disordered list. In single machine scheduling, we need to define goals clearly—to be explicit about priorities and management strategies and implement strategies to balance tasks efficiently. As such, various methods exist to provide consistency in our scheduling tactics; strategies may vary from acting on the nearest due date to following methods like Mo's algorithm, which schedules tasks to minimize spoilage.
00:13:37.360
However, if timing is not our concern and solely getting things done matters more, we can use shortest processing time to minimize waiting and ensure productivity. By arranging tasks so that we address smaller waiting clients first, we can trim down the total waiting time drastically. This leads us to explore how scheduling theories suggest that optimizing processing times enhances our decision-making process, ultimately leading to a more streamlined workflow.
00:14:52.300
Furthermore, when searching for people in a network, we can implement graphs to analyze connections. For instance, each person in our social network represents a node connected to others by edges. Using breadth-first search methods involves checking first-degree connections before moving to second-degree connections, and when spread out sufficiently, you can construct a clearer map of relationships while identifying individuals with specific expertise or connections—much like finding a magician named Keith, who won accolades and is tied to historically significant ruby events.
00:15:55.080
Through this example of network searching, we also touch upon traveling salesperson problems, where a sales representative needs to traverse various cities without backtracking for the shortest path. If we relax certain constraints, we can expedite finding solutions more effectively—even if they’re not perfectly optimal. Lastly, constructing recommendation systems similarly involves identifying users with similar tastes to produce personalized suggestions. Utilizing neighbor algorithms can help find the best match for users, then applying distance formulas to gauge similarities based on user ratings.
00:17:42.150
Reflecting on decision-making methodologies, consider Charles Darwin's deliberation when deciding to marry Emma Wedgwood. He meticulously weighed the pros and cons—listing each possible consequence for marriage and ultimately achieving a balance that favored companionship. This historic example underlines our tendency to overthink decisions. While one might assume that more consideration leads to better outcomes, the overfitting of information introduces noise into our decision-making process. Simplifying the equation often leads to more sound decisions as seen with efficient and straightforward reasoning.
00:29:27.780
In a real-world application, we witnessed an overbooked United Airlines flight where algorithms were trained to determine passenger value. Decisions made by such algorithms might reflect subjective biases from their creators, highlighting the importance of making algorithms transparent and paying attention to those affected by them. The takeaway is clear: we must consider both the ethical implications and the operational efficiency of algorithms we create. Thank you very much.
