<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Chris Nguyen on Medium]]></title>
        <description><![CDATA[Stories by Chris Nguyen on Medium]]></description>
        <link>https://medium.com/@uncompiled?source=rss-8c47dada274b------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*2FJ5jvTsggHF8vZqWqGKzQ.jpeg</url>
            <title>Stories by Chris Nguyen on Medium</title>
            <link>https://medium.com/@uncompiled?source=rss-8c47dada274b------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 10:35:20 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@uncompiled/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Code Golf with Conway’s Game of Life]]></title>
            <link>https://medium.com/@uncompiled/code-golf-with-conways-game-of-life-dbf25c1a704e?source=rss-8c47dada274b------2</link>
            <guid isPermaLink="false">https://medium.com/p/dbf25c1a704e</guid>
            <category><![CDATA[conways-game-of-life]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[code-golf]]></category>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Chris Nguyen]]></dc:creator>
            <pubDate>Sat, 03 Mar 2018 23:08:18 GMT</pubDate>
            <atom:updated>2018-03-03T23:08:18.369Z</atom:updated>
            <content:encoded><![CDATA[<p>I recently subscribed to a fun weekly newsletter from <a href="https://twitter.com/fillerwriter">Brandon Morrison</a> called <a href="https://tinyletter.com/alltestspass/">All Tests Pass</a>. Every week, I receive a JavaScript puzzle inside a JSBin link and the following week, I can see how other people solved the same problem.</p><p>Most of the time, programming is about making the right trade-offs: are we optimizing for space or time?</p><p><a href="https://en.wikipedia.org/wiki/Code_golf">Code Golf</a> is a recreational style of programming that specifically optimizes for the length of the code. This means implementing an algorithm in the shortest number of characters. To that effect, some programming languages have comprehensive collections libraries that make it easy to write a “one-liner” to implement an algorithm. JavaScript isn’t one of them, but it does have built-in methods to operate over Arrays, such as map, filter, or reduce. This enables JS developers to write in a functional style, which can result in some pretty terse code.</p><h3>The Game</h3><p>This week’s challenge was to implement an iterator or generator for <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Conway’s Game of Life</a>. If you’re not familiar with Conway’s Game of Life, it’s not really a “game” as much as it’s a simulation (a cellular automaton).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Wcpc31vjVZ3mbzPvNVu23w.gif" /></figure><p>As the initial input, the Game of Life takes the state of the world (or the board), which is represented by a matrix of alive and dead cells. Each iteration of the function produces a new state based on some specific rules:</p><ol><li>Any live cell with fewer than two live neighbors dies.</li><li>Any live cell with two or three live neighbors lives on.</li><li>Any live cell with more than three live neighbors dies.</li><li>Any dead cell with exactly three live neighbors becomes a live cell.</li></ol><p>These rules were carefully chosen by Conway to simulate the ideas of underpopulation, overpopulation, and reproduction.</p><p>Now I’ll step through my thought process as I optimize code for length.</p><h3>The Starting Point</h3><p>Here is a working algorithm for the Game of Life:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d7738534f1558b7d2a2ab11121a600ea/href">https://medium.com/media/d7738534f1558b7d2a2ab11121a600ea/href</a></iframe><p>If we check the word count with the wc command, we have <strong>192 words</strong> and <strong>1333 characters</strong> (including whitespace).</p><p>The getCellNeighborCount method is a bit lengthy, so let’s see if we can find any quick wins. This method checks all of the cells immediately surrounding position (x, y) and counts how many neighbors are alive. Since we need to check 8 neighbors (that’s a lot of duplication), let’s refactor this method by creating a function called isAlive that checks whether a cell is alive:</p><pre>const isAlive = (x, y) =&gt; board[x] &amp;&amp; board[x][y]</pre><p>Inside getCellNeighborCount, we can use isAlive to check whether a cell is alive.</p><p>Now the getCellNeighborCount function looks like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bbf3535761d28e3cf27f8db69015425f/href">https://medium.com/media/bbf3535761d28e3cf27f8db69015425f/href</a></iframe><p>Note that board isn’t used at all, so we can remove this function parameter completely.</p><p>The next thing I’m going to look at is the main part of the original algorithm that iterates over the cells:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e9ccd0d6c624dfcd415638b6ff97c748/href">https://medium.com/media/e9ccd0d6c624dfcd415638b6ff97c748/href</a></iframe><p>Since this code iterates over every cell in the board, we don’t actually need to use index variables to iterate over the array length.</p><p>We <em>could</em> use forEach to iterate over the array and populate returnBoard, but we can actually do a bit better. <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map">Array.prototype.map</a> iterates over the elements of the array, but it also returns a value, which is a nice way to model transformations in data. If you think about the board as the state of the world, then the output is the <strong><em>next</em></strong> state of the world. In other words, the goal of our function is to transform the input from one state to the next. Using map also has the benefit of letting us get rid of the returnBoard variable entirely.</p><p>We’ll replace the nested for loops with this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f27143da87babd84b967777a8808f283/href">https://medium.com/media/f27143da87babd84b967777a8808f283/href</a></iframe><p>If you’re not familiar with functional programing, this style of code probably looks confusing because it’s very dense.</p><p>Let’s unpack it.</p><p>Calling board.map iterates over the board, which is an array of rows in the board. We’re using an arrow function to transform each row of the input. Notice that because there are no curly braces, the call to row.map is explicitly returned as a value.</p><p>Calling row.map iterates over each cell in the row and does two things:</p><ul><li>gets the number of neighbors that are alive</li><li>uses the rules to return the next state of the cell <em>(whether it should be alive or dead)</em></li></ul><p>This is also a bit dense because we have nested ternary operators. In a production application, you might not want to write code like this, but since we’re code golfing, this allows us to minimize the number of if/else keywords and curly braces.</p><pre>(isAlive(x, y) ? n &gt; 1 &amp;&amp; n &lt; 4 : n === 3) ? 1 : 0</pre><p>This expression checks whether the cell in position (x, y) is alive.</p><ul><li>If so, it checks whether it has 2 or 3 live neighbors. The reason that I chose to check whether the number of live neighbors is greater than 1 is because &gt; is one character versus 3 characters for the strict equality operator. This is also why I chose to use n &lt; 4.</li><li>If the cell is dead, it checks if there are exactly 3 live neighbors.</li></ul><p>Because boolean comparisons result in true or false, we check the result of the expression with another ternary conditional operator and return 1 if it’s true or 0 if it’s false.</p><p>Here is what we have so far:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/100c20937e833e41f74c50db80aee59f/href">https://medium.com/media/100c20937e833e41f74c50db80aee59f/href</a></iframe><p>When I’m working on an algorithm, I like to use descriptive variable names, but that uses up a lot of extra characters in code golf, so let’s pretend to be a JavaScript compiler and replace variable names with one-letter versions.</p><p>Let’s replace the following variables:</p><ul><li>isAlive becomes a</li><li>board becomes b</li><li>neighborCount becomes n</li><li>row becomes r</li></ul><p>However, note that getCellNeighborCount is only invoked once. For the purpose of optimizing character count, we can remove the function definition and replace it in-line where it’s called.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9a0234c2b14bde706bef1917e641ef9e/href">https://medium.com/media/9a0234c2b14bde706bef1917e641ef9e/href</a></iframe><p>Although we’ve hand-picked single letter character names that have some logical resemblance to the more descriptive variable name, it looks pretty much like minified code at this point (if you strip out the whitespace).</p><p>The last character count optimization that we can do is replace single branch if statements with the conditional and operator (&amp;&amp;).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/01c5579829f687d293409b1d015d37c9/href">https://medium.com/media/01c5579829f687d293409b1d015d37c9/href</a></iframe><p>We’re splitting hairs at this point, but replacing the if statement with a conditional and lets us get rid of the parentheses around the condition, saving us 2 more characters per if statement.</p><h3>Summary</h3><p>Here are the results of our code golf journey:</p><ul><li>If we include whitespace, the original version is <strong>1333 characters</strong> and the final version is <strong>418 characters</strong></li><li>If we strip out whitespace (since it doesn’t have semantic meaning in JS), the original version is <strong>824 characters</strong> and the final version is <strong>294 characters</strong></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dbf25c1a704e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sorting Things Out (Part 2)]]></title>
            <link>https://medium.com/@uncompiled/sorting-things-out-part-2-5d64e41a35d4?source=rss-8c47dada274b------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d64e41a35d4</guid>
            <category><![CDATA[divide-and-conquer]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[merge-sort]]></category>
            <dc:creator><![CDATA[Chris Nguyen]]></dc:creator>
            <pubDate>Fri, 22 Dec 2017 18:10:25 GMT</pubDate>
            <atom:updated>2017-12-22T18:10:25.633Z</atom:updated>
            <content:encoded><![CDATA[<h4>Algorithms for Everyone</h4><p>In <a href="https://medium.com/@uncompiled/sorting-things-out-part-1-2c7cc68c422">Part 1</a>, we learned how to sort a collection of items in a way that mirrors how we think about sorting objects in real life.</p><p>We used an algorithm called <a href="https://en.wikipedia.org/wiki/Selection_sort">selection sort</a>, but when you use the <em>sort</em> function in your favorite language, it probably doesn’t use this algorithm. The reason is that it’s <strong><em>very</em></strong> slow.</p><h4>How slow?</h4><p>Let’s assume that we’re running our <em>selection sort</em> algorithm on a computer that takes <strong>1 second</strong> to sort a list with <strong>1,000</strong> items. That might not sound so bad right now, but if the list grows to <strong>1 million items</strong>, it would take over <strong>270 hours </strong>to sort the list!</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2Fl2JHVUriDGEtWOx0c%2Ftwitter%2Fiframe&amp;display_name=Giphy&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2Fl2JHVUriDGEtWOx0c%2Fgiphy.gif&amp;image=https%3A%2F%2Fmedia1.giphy.com%2Fmedia%2Fv1.Y2lkPTc5MGI3NjExaTZxMW5mY3N3Mjhxdno0ejV6bGl6aXZwc2Z6ZmhpNmh5aHh1bXFiZyZlcD12MV9naWZzX2dpZklkJmN0PWc%2Fl2JHVUriDGEtWOx0c%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="185" frameborder="0" scrolling="no"><a href="https://medium.com/media/40a44871130f9e7f5407c1b24450c37e/href">https://medium.com/media/40a44871130f9e7f5407c1b24450c37e/href</a></iframe><p>You might be thinking that 1 million items sounds like a lot, but there are a lot of situations where you could be working with more than a million items:</p><ul><li>In 2015, there were about <strong>218 million</strong><a href="https://www.statista.com/statistics/191653/number-of-licensed-drivers-in-the-us-since-1988/"> licensed drivers in the United States</a>. That means there are about 218 million records for all those drivers in a database somewhere.</li><li>In the United States, over <a href="https://www.ssa.gov/history/hfaq.html"><strong>453.7 million</strong> different Social Security numbers have been issued</a>. All of those records are probably stored in a database too.</li><li>India currently has a population over <strong>1.3 billion</strong>. We probably don’t want to alphabetize all those names using <em>selection sort</em>.</li></ul><p>In this article, we’ll learn about a new approach to sorting that is much faster. It uses a problem solving technique called <strong>divide and conquer</strong>.</p><h3>Divide and Conquer</h3><p>In computer science, <strong>divide and conquer</strong> is used to describe the process of breaking up a problem into smaller sub-problems that are easier to solve. By solving the smaller problems, we end up with a solution to the larger problem.</p><p>First, let’s see if we can apply this idea to a real-world problem. Let’s imagine that we’re throwing a party, but before people come over, we need to clean the entire house. Ugh, this seems like a lot of work!</p><blockquote>… but what if you broke up the task of cleaning the entire house into smaller tasks?</blockquote><p>Instead of one large task, we now have the following sub-tasks:</p><ul><li>Clean the living room</li><li>Clean the kitchen</li><li>Clean the dining room</li><li>Clean the bedroom</li></ul><p>By completing these smaller tasks, the task of cleaning the house is also completed. Another benefit of <strong>divide and conquer</strong> is that if our friends want to help, they can each take a room and get it done even faster.</p><p>Let’s reframe this analogy. When we’re writing code, the tasks in question are really just our code… and our friends are computer processors (or CPUs)!</p><p>Most modern computers have multiple processors (or multiple cores) that let your computer run multiple things at the same time. For example, the iPhone 8 has 6 CPU cores!</p><p><strong>Divide and conquer</strong> algorithms are a great way to take advantage of all that computing power.</p><h3>Breaking Up the Sorting Problem</h3><p>One of the hard parts about the divide and conquer technique is learning how to reframe the problem. When the problem that you’re facing is conceptually difficult, the breakthrough usually comes from realizing that there is a case where the sub-task is trivial to solve.</p><p>So what’s the problem? Just like in <a href="https://medium.com/@uncompiled/sorting-things-out-part-1-2c7cc68c422">Sorting Things Out: Part 1</a>, the problem is that <strong>we have an unsorted collection of items </strong>and <strong>the goal is to sort them</strong> (but faster).</p><h4>Can we think of any cases where the task is trivial?</h4><p>I often think of this step as “stating the obvious”.</p><p>We can start by making a list of things that we know. Here are a few ideas related to sorting:</p><ul><li><strong>an empty list is technically sorted</strong> because there’s nothing to sort</li><li><strong>a list with one item in it is already sorted</strong></li></ul><p><em>Wait. I think we’re onto something.</em></p><p>In Part 1, we used the example of sorting index cards.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C0OlqR5j4_2NpUPuidVUCw.png" /><figcaption>Unsorted pile of index cards</figcaption></figure><p>What if we split up the problem so that we hand all of our friends a single card? Since they only have one card, their work is already done!</p><h3>Conquering the Sorting Problem</h3><p>At this point, your friends are all holding a single index card and you’re wondering how that helped at all.</p><p>Once the work has been divided up and completed, we need to stitch the results together. This is how we <strong>conquer</strong> the problem!</p><h4>How do we combine subtasks?</h4><p>In the divide step, we broke down the input so that everyone only needed to sort a list with one item.</p><p>In this step, we need to combine those items. To do this, all we have to do is compare the two items and return a single larger list where they are sorted.</p><p>The key insight here is that the two smaller lists that we’re combining are already sorted. Every time we combine two lists, we create a larger list that’s also sorted.</p><p>The combine step merges the two smaller lists together by taking the smaller of the two items off of the smaller lists.</p><p>That’s the name of this algorithm: <a href="https://en.wikipedia.org/wiki/Merge_sort"><strong>merge sort</strong></a>!</p><p>If you combine two sorted lists this way, you end up with a single sorted list that contains both of the smaller lists, <strong>but</strong> <strong>you didn’t have to compare all of the items</strong>! You’re only comparing the first item in each of the lists — and taking the smaller (or larger) one based on the sort order.</p><h3>Performance</h3><p>In Part 1, we learned that selection sort has a time complexity of <strong>O(n²)</strong>, which is very slow when you’re dealing with a large number of items.</p><p>Now let’s figure out the time complexity of the mergesort algorithm.</p><p>There are two main parts to the mergesort:</p><ul><li><strong>Divide the input</strong> until we have a sorted list</li><li><strong>Merge the sorted lists together</strong> into a single sorted list</li></ul><h4>Divide the Input</h4><p>When we break up the work, it makes sense to divide the input in half.</p><p>That way, the work is distributed fairly. If we needed to alphabetize 100 books, it wouldn’t be fair to give one person a single book and give the other 99 books to someone else. It would also take longer because the person with one book would already have their book(s) sorted and they’d just have to wait around until the other person finishes sorting all their books.</p><p>We can break down the input fairly by splitting it into two equally sized groups. Let’s see how many splits we need until we have a list with one item in it (that is by definition sorted):</p><ul><li><strong>Split 1</strong>: 100 items</li><li><strong>Split 2</strong>: 50 items</li><li><strong>Split 3</strong>: 25 items</li><li><strong>Split 4</strong>: 12 items (the other has 13 items)</li><li><strong>Split 5</strong>: 6 items</li><li><strong>Split 6</strong>: 3 items</li><li><strong>Split 7</strong>: 1 item (the other half has 2 items)</li></ul><p>Let’s graph the number of splits that we need based on the size of the input:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/848/1*v7EaxRnfRbcdN9NK4vjXbg.png" /></figure><p>This graph shows how many times the input needs to be split up before we have a list with 1 item in it. It has the shape of a logarithmic curve, which is written as <strong>O(log(n))</strong> in Big-O notation.</p><p><strong>Merge the Sorted Lists Together</strong></p><p>When we merge two lists together, we need to iterate over every element in both of the lists.</p><p>The general algorithm is to check the first element of each list and build a new list by taking the smaller of the two items at each step.</p><p>In the “<strong>divide”</strong> step of the mergesort algorithm, we kept splitting up the input in half. If there are <strong>n</strong> items in the input list, then there would be <strong>n/2</strong> items in the left half and <strong>n/2</strong> items in the right half. This is important because when we merge the two lists back together, we have to look at all <strong>n</strong> items. This is expressed as <strong>O(n)</strong> in Big-O notation.</p><h4>Combined Performance</h4><p>We just discovered that our divide and conquer algorithm has the following characteristics:</p><ul><li>Dividing the work has <strong>O(log(n)) </strong>time complexity</li><li>Combining the sorted lists has <strong>O(n) </strong>time complexity</li></ul><p>The number of times we have to combine lists is related to the number of times that we divided the input into smaller sub-tasks.</p><p>We can express this relationship by saying our algorithm has <strong>O(log(n)) * O(n)</strong> time complexity, but we can simplify the expression into <strong>O(nlog(n))</strong>.</p><h3>Implementation</h3><p><em>The following implementation is written in </em><a href="https://www.python.org/"><em>Python</em></a><em> because the language has a lot of built-in features that make it easy to read.</em></p><p>We’ve already described how the algorithm works, so let’s take a look at how to implement it:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/592da2bc77fabef630ef0c7e7f396586/href">https://medium.com/media/592da2bc77fabef630ef0c7e7f396586/href</a></iframe><p>The <strong>merge_sort</strong> function contains the high-level algorithm:</p><ul><li>If the input only has 1 item, it’s already sorted, so we can return the input.</li><li>Otherwise, split the input in half and sort those two smaller lists.</li><li>Since the result will be two sorted lists, use <strong>merge_lists</strong> to combine them into a single sorted list.</li></ul><p>In the <strong>merge_lists</strong> function, we use variables to avoid the overhead of modifying the list. <strong>l_index</strong> and <strong>r_index</strong> are variables that store the current position in the <strong>left</strong> and <strong>right</strong> lists (respectively). To consume the smallest element off the front of a sublist, we increment the respective index to walk that list.</p><h3>Summary</h3><p>Merge sort was invented by John von Neumann in 1945 when he realized that a collating machine could take two sorted stacks and combine them into a single sorted stack.</p><p>The curious thing about merge sort is that it’s quite old, but people are still talking about it! There’s an article from 2014 about a <a href="http://www.drdobbs.com/parallel/parallel-in-place-merge-sort/240169094">Parallel In-Place Merge Sort</a> variant in Dr. Dobb’s journal. Merge sort is a divide and conquer algorithm, so if you’re adventurous, you could try to write a version of merge sort that runs on multiple CPUs (or even across multiple computers) to compare the performance.</p><p>The other thing that’s interesting about merge sort is that it’s everywhere! Java’s built-in <em>sort</em> method is based on merge sort—and some of the biggest companies in the world use Java (including Google and Netflix), so there’s a good chance that this algorithm is being used when you’re using an Android device or you’re watching your favorite show on Netflix.</p><p><em>This is part of a series that I’m creating to teach the fundamentals of computer science and algorithms in a way that’s approachable to people without a computer science background.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d64e41a35d4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Big-O Demystified]]></title>
            <link>https://medium.com/@uncompiled/big-o-demystified-9d91658bd364?source=rss-8c47dada274b------2</link>
            <guid isPermaLink="false">https://medium.com/p/9d91658bd364</guid>
            <category><![CDATA[big-o-notation]]></category>
            <category><![CDATA[algorithmic-design]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Chris Nguyen]]></dc:creator>
            <pubDate>Fri, 10 Nov 2017 15:04:50 GMT</pubDate>
            <atom:updated>2017-11-13T01:29:26.640Z</atom:updated>
            <content:encoded><![CDATA[<h4>Algorithms for Everyone</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/877/1*RhQPAEmq5mI2UIUlAN6k1A.png" /></figure><p>When discussing algorithms, computer scientists typically use <a href="https://en.wikipedia.org/wiki/Big_O_notation">Big-O notation</a>. It’s the most common way to express algorithm performance, but it’s also the quickest way to confuse new programmers or developers without a computer science background.</p><p>If you’re trying to understand what this mystical <strong>O(…)</strong> abstraction means, the first thing you might try is a quick Google search:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rzvE4hRuVEekd_OtLg1AAg.png" /></figure><p>Apparently, there’s a Japanese animated series called “The Big O”, which has nothing to do with algorithms. If you’re like me, you probably clicked on that link instead and just finished watching the entire animated series.</p><p>Now that you’re back, let’s take a look at the definition of Big-O on Wikipedia:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/794/1*Qk46hRjQZtnJdEoh2nEsYA.png" /><figcaption>Formal definition of Big-O Notation (Wikipedia)</figcaption></figure><p><strong>NOPE.</strong></p><p>If you have a math degree, that probably makes complete sense and you can stop reading now because this article is not for you.</p><p>If your eyes glazed over, keep reading. This article is for everyone else.</p><h3>What is Big-O?</h3><p>When you read articles or books about algorithms, there’s no doubt that you’ll see the performance of the algorithm expressed as one of the following:</p><ul><li><strong>O(n²)</strong></li><li><strong>O(n)</strong></li><li><strong>O(log(n))</strong></li><li><strong>O(1)</strong></li></ul><p>Let’s gloss over these expressions for a moment and get to the heart of what Big-O notation tries to express:</p><blockquote>Big-O is a way to describe how something grows based on the size of the input.</blockquote><p>That <em>something</em> is usually <strong>time</strong> or <strong>space</strong>. Computer scientists care about time and space because these two factors are tightly coupled to computer hardware.</p><h4>Time Complexity</h4><p>Time complexity is <strong>how long it takes the algorithm to run</strong>. Programs are run by a computer’s processor (or CPU), so one of the ways we can reduce the amount of time it takes to run an algorithm is by using a faster processor.</p><p>However, it’s not always an option to buy a faster processor.</p><p>For example, if you create a website using JavaScript, that code is sent to the user’s web browser, where it executes on <em>their</em> computer, not yours. As a developer, you don’t have control over what kind of computer they use.</p><p>If they complain that your website is too slow, you could buy them a new computer… or you could improve the code’s performance so that it takes less time to run. However, it’s probably cheaper to improve the algorithm rather than buy new computers for all of your users.</p><h4>Space Complexity</h4><p>Space complexity is <strong>how much memory the algorithm uses while it’s running</strong>. In a computer program, <a href="https://en.wikipedia.org/wiki/Variable_(computer_science)"><em>variables</em></a> correlate to the computer’s memory (RAM). When you buy a computer, memory is usually listed as one of the tech specs:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d9AmxYHH2xLfgPqhHj0AuQ.png" /><figcaption>2017 MacBooks come with 8GB of RAM</figcaption></figure><p>Although modern computers have a lot of RAM, if your program loads the entire input into memory, you’ll eventually run out of memory.</p><p>Let’s look at an example. If our program loads all of our users into an array to process them, this would work fine for hundreds or even thousands of users, but if we have too many users, our algorithm won’t have enough memory to run! As of right now, Facebook has over <strong>2 billion</strong> users. If you try to load 2 billion users into an array, it would take a lot of memory!</p><p>One solution is to buy more memory, but that’s not always an option. As we saw in the time complexity section, it’s not realistic to buy new computers for all of our users.</p><p>The better solution is to improve our algorithms so that they use less memory.</p><h3>Unpacking the Notation</h3><p>When you see Big-O notation, the important part is what is inside the parentheses.</p><p>Let’s take a look at an example: <strong>O(n)</strong>.</p><p>The expression inside the parentheses is a <a href="https://en.wikipedia.org/wiki/Function_(mathematics)">math function</a>:</p><blockquote>“a <strong>function</strong> is a <a href="https://en.wikipedia.org/wiki/Binary_relation">relation</a> between a <a href="https://en.wikipedia.org/wiki/Set_(mathematics)">set</a> of inputs and a set of … outputs”</blockquote><p>If you took algebra in high school, you might remember this thing:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6de2NOdedOMr-qCY2NeuCQ.jpeg" /><figcaption>TI-83 Graphing Calculator</figcaption></figure><p>It’s a TI-83 graphing calculator. Aside from being able to play games in math class, there’s also this little blue “graph” button that lets you graph functions.</p><p>Math functions are usually graphed on the X and Y axis, so you’ll normally see them expressed in the form of <strong>y=x.</strong></p><p>Here is the function <strong>y=x</strong> on a graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HoR4XobWZb7uYunZyzK6rg.jpeg" /></figure><p>The relationship that we see on this graph is: <em>when the input is x, the output is x.</em></p><p>In the context of algorithm performance, Big-O notation expresses a relationship between <strong>the size of the input</strong> and <strong>how much time or space the algorithm needs to process the input</strong>.</p><p>Since <strong>n</strong> represents the size of the <em>input</em>, what we see between the parentheses describes how the algorithm’s performance is affected as the size of the input grows:</p><ul><li><strong>O(n) </strong>is shorthand for saying that the relationship <em>when the size of the input is </em><strong><em>n</em></strong><em>, the time or space required to process the input is </em><strong><em>n</em></strong>.</li><li><strong>O(n²)</strong> is shorthand for saying that the relationship <em>when the size of the input is </em><strong><em>n</em></strong><em>, the time or space required to process the input is </em><strong><em>n²</em></strong>.</li></ul><h3>Upper Bound</h3><p>Big-O notation describes the worst-case scenario, which gives us an upper bound on the performance as the input grows.</p><p>Let’s imagine that we’re searching for a specific user in a list of names.</p><p>The brute-force algorithm iterates through the entire list and if the user is in the list, it returns. This algorithm is <strong>O(n)</strong> because <strong>n</strong> is the size of the list and we iterate through the entire list to find the name.</p><p>Performance is not an issue with a small number of users, but what happens when we have 1 million users?</p><p>Let’s assume that it takes 1 millisecond to check each name in the list. For <strong>O(n)</strong>, the algorithm would take <strong>n</strong> milliseconds to find the name <em>in the worst case.</em></p><ul><li>For 5 users, it takes 5 milliseconds <em>in the worst case</em></li><li>For 1,000 users, it takes 1,000 milliseconds <em>in the worst case</em></li><li>For 1,000,000 users, it takes over 16 minutes<strong> </strong><em>in the worst case</em>!</li></ul><p>What happens if the name that we’re looking for is the first name in the list? We could stop on the first try, but that doesn’t change the performance of the algorithm. If the name that we’re looking for is the last name in the list, then it will still take 16 minutes.</p><p>When we use Big-O notation, we’re really just stating an upper bound on how much time or space is required.</p><h3>Drop the Constants</h3><p>You might have noticed that math functions can include constants, but Big-O notation doesn’t.</p><p>One example of a math function is <strong>y=2x + 1</strong>, but you’ll never see <strong>O(2n+1)</strong>.</p><p>The reason for this is because Big-O is an <strong>estimation</strong> that focuses on the upper bound. We don’t really care about the performance when <strong>n</strong> is small. We care more about what happens when <strong>n</strong> becomes arbitrarily large so that we can get sense of the performance as the input grows.</p><p>When <strong>n</strong> becomes very large — millions, billions, or trillions — multiplying by 2 or adding 1 doesn’t really have a significant effect, so we leave them out to keep things simple.</p><h3>Orders of Magnitude</h3><p>You can think of the “O” in Big-O as standing for “Orders of Magnitude”.</p><p>Orders of magnitude provide a sense of scale for how big something is. Most countries use the decimal system (base 10), so one order of magnitude larger is 10x the previous order of magnitude.</p><p>Here are some examples:</p><ul><li>Ten (10)</li><li>Hundred (100)</li><li>Thousand (1,000)</li></ul><p>Let’s say that we’re planning to throw a party for 10 people. However, we find out at the last minute that 100 people are coming. We’d need to acquire a lot more food and we might even need to find a larger venue! A party for 100 people is much bigger in scale — an order of magnitude bigger.</p><p>Now let’s imagine that instead of 10 people, you find out that a few guests are bringing a friend. There are more people, but it’s the same order of magnitude. We might need some extra food, but it’s not a big deal.</p><p>You can also categorize algorithms by their orders of magnitude.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/814/1*6jeR1-8OUlQ8ZModajaD8g.png" /><figcaption>Comparison of different orders of magnitude</figcaption></figure><p>Most algorithms fall into a few common categories:</p><ul><li><strong>O(1)</strong> is said to have <strong>constant complexity </strong><em>(because it’s always the same)</em></li><li><strong>O(log(n))</strong> is said to have <strong>logarithmic complexity </strong><em>(because it’s the shape of a logarithmic curve)</em></li><li><strong>O(n)</strong> is said to have <strong>linear complexity </strong><em>(because it’s a line)</em></li><li><strong>O(n²)</strong> is said to have <strong>quadratic complexity </strong><em>(because it’s the shape of a quadratic equation)</em></li></ul><p>You can think of <strong>O(1)</strong> as the holy grail for algorithms because it always takes the same amount of time no matter how big your input is.</p><p>On the other end of the spectrum, it doesn’t take long for an <strong>O(n²)</strong> algorithm to run out of space (memory) or time. Remember from earlier that if it takes 1 millisecond to process a single item in a list, it will take an <strong>O(n²)</strong> algorithm over <strong>277 hours</strong> just to process 1 million items!</p><h3>Summary</h3><p>Big-O notation gives programmers a concise and common way to express the performance characteristics of an algorithm.</p><p>Big-O notation:</p><ul><li>describes <strong>time complexity</strong> or <strong>space complexity</strong></li><li>is <strong>shorthand for a math function</strong></li><li>is<strong> concerned with upper bounds</strong> (the worst-case scenario)</li><li><strong>doesn’t care about constants</strong></li><li>describes<strong> complexity in orders of magnitude</strong></li></ul><p>Hopefully, this article clears up any confusion that you might have. If you still have questions, please let me know!</p><p><em>This is part of a series that I’m creating to teach the fundamentals of computer science and algorithms in a way that’s approachable to people without a computer science background.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9d91658bd364" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sorting Things Out (Part 1)]]></title>
            <link>https://medium.com/@uncompiled/sorting-things-out-part-1-2c7cc68c422?source=rss-8c47dada274b------2</link>
            <guid isPermaLink="false">https://medium.com/p/2c7cc68c422</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[sorting-algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Chris Nguyen]]></dc:creator>
            <pubDate>Thu, 02 Nov 2017 23:26:31 GMT</pubDate>
            <atom:updated>2017-11-14T15:35:20.602Z</atom:updated>
            <content:encoded><![CDATA[<h4>Algorithms for Everyone</h4><p>Sorting is the process of <strong>arranging</strong> or <strong>ordering</strong> things based on a specific property. For example, numbers can be ordered by their value: 1 is smaller than 2. If we order the list by <em>ascending</em> order, 1 comes before 2. We can also sort a list of numbers by <em>descending</em> order. In that case, 2 comes before 1.</p><p>However, sorting also occurs in the physical world. For example, we can sort objects by size. In the United States, <a href="https://www.coinstar.com/">Coinstar</a> machines are vending machines that automatically sort and count coins for you. They charge a fee for this service, but let’s see how it actually works.</p><p>The key to sorting coins is that <strong>each coin is a different size</strong>. Inside a coin-sorting machine, there are different sized holes: one for each coin. If you’re curious how this works, go ahead and watch this video:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F7ILHtAPY29I%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D7ILHtAPY29I&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F7ILHtAPY29I%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/556f52be4fb2523d925693361f58f361/href">https://medium.com/media/556f52be4fb2523d925693361f58f361/href</a></iframe><p>The process of sorting the coins makes it much easier to count change. Similarly, in computer science, the process of sorting items makes it much easier to apply other algorithms, such as searching and merging large amounts of data.</p><h3>Why bother learning how to sort in the first place?</h3><p>In practice, every popular programming language has a built-in <em>sort</em> function:</p><ul><li><a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort">JavaScript</a>: Array.prototype.sort(…)</li><li><a href="https://docs.python.org/3/library/functions.html?highlight=sorted#sorted">Python</a>: sorted(…)</li><li><a href="https://ruby-doc.org/core-2.4.2/Enumerable.html#method-i-sort">Ruby</a>: Enumerable.sort(…)</li><li><a href="https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator-">Java</a>: Arrays.sort(…)</li><li><a href="https://golang.org/pkg/sort/">Go</a>: sort.Sort(…)</li></ul><p>In my <a href="https://medium.com/@uncompiled/binary-search-b8f8efcea0f8">binary search</a> article, we saw how the binary search algorithm can be used to find an item extremely quickly. However, <strong>it only works if the input is sorted</strong>. Binary search relies on the property of ordering to discard half of the input at every step. Without sorted input, the desired item could be in either half!</p><p>Another motivation to learn how to sort is because sorting is a problem with <a href="https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms">many well-documented implementations</a>. There’s the <a href="https://en.wikipedia.org/wiki/Bubble_sort">bubble sort</a>, the <a href="https://en.wikipedia.org/wiki/Insertion_sort">insertion sort</a>, the <a href="https://en.wikipedia.org/wiki/Selection_sort">selection sort</a>, the <a href="https://en.wikipedia.org/wiki/Merge_sort">merge sort</a>, the <a href="https://en.wikipedia.org/wiki/Quicksort">quicksort</a>, and many other variations. Some of those implementations are more efficient, so by studying the solutions that already exist, we can learn the techniques that make certain algorithms faster than others.</p><p>In this article, we’ll take a look at an approach called selection sort because it mirrors the way humans sort objects in real life.</p><h3>How do we sort things in real life?</h3><p>Let’s imagine that we’re judging a competition. We have a pile of name cards with each person’s current score and now we want to find out who the top competitors are. To do this, we need to sort the competitors by their score.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C0OlqR5j4_2NpUPuidVUCw.png" /><figcaption>Unsorted pile of cards</figcaption></figure><p>We should probably start by reserving some space to put the sorted names. Now we have two piles: <strong>the unsorted pile</strong> and <strong>the sorted pile </strong>(which is currently empty).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rOFa2VUyyR3Xr3Lut6jfJw.png" /><figcaption>Reserve some space to put the sorted names</figcaption></figure><p>One way to do this is by looking at all of the names in the unsorted pile and finding the one with the highest score. Once we’ve found the highest score, we move it to the sorted pile.</p><p>In this case, Alice has the highest score, so we’ll move her card over to the sorted pile.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fJloyBhwKtBirGHgO3sayQ.png" /><figcaption>Move the highest score over to the sorted pile</figcaption></figure><p>Now we go through the unsorted pile, find the person with the highest score, and move them over the sorted pile.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KAhqkkc2pWkGoHNSNBZ6WA.png" /><figcaption>Move the highest score over to the sorted pile</figcaption></figure><p>The next step is to go back through the unsorted pile, find the person with the highest score, and move them over to the sorted pile. This is starting to sound repetitive, isn’t it? When we sort cards in real life, we repeat this step until there are no more cards in the unsorted pile.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jq48XrUzGCpaBm8BLR8l_g.png" /><figcaption>Repeat the process of picking the person with the highest score and moving their card over to the sorted pile</figcaption></figure><p>Now that all the cards are sorted, let’s take a look at the performance of this approach.</p><h3>Performance</h3><p>There are two primary aspects of performance that computer scientists are usually interested in: <strong>space </strong>and<strong> time</strong>.</p><ul><li><strong>Space complexity </strong>is how much memory is used when the program runs.</li><li><strong>Time</strong> <strong>complexity</strong> is how long it takes to run the program.</li></ul><h4>Space Complexity</h4><p>The first thing to notice when we sorted the cards is that we used two piles for the unsorted names and the sorted names. In the physical world, this would mean that we need twice the amount of desk space to sort the cards. If we translate this process directly into a computer program, we would need to use two arrays, or 2x the amount of memory.</p><p>If we want to be conservative with space, we could make optimizations to this process by sorting the cards in-place. Starting with the unsorted pile, we do the same thing as before, but this time, we find the highest score and shuffle the cards around so that we don’t need extra desk space.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C0OlqR5j4_2NpUPuidVUCw.png" /><figcaption>Unsorted pile of cards</figcaption></figure><p>Let’s start with the first card and replace it with the highest score. Instead of clearing off extra desk space, we partition the original pile into a sorted part and an unsorted part (using the same amount of space as the original pile).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fEEb51hVZ-CvQThbNM3yvg.png" /></figure><p>Now that we know the first card has the highest score, we move onto the second card and swap it with the highest score from the unsorted part.</p><p>We’ll repeat this process until we’ve finished swapping every card in the original pile with the highest score. Each time that we swap a card, the sorted part grows and the unsorted part shrinks.</p><p>We’ll end up with something that looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Frc7O15is0Q_NA-vZj5_1A.png" /><figcaption>After shuffling the cards around in-place</figcaption></figure><p>If there are <strong>n</strong> cards in the original pile, then we would say that this implementation has <strong>O(n) space complexity.</strong></p><p><em>If you’re new to Big-O Notation, Justin Abrahms wrote a helpful post called “</em><a href="https://justin.abrah.ms/computer-science/big-o-notation-explained.html"><em>Big-O notation explained by a self-taught programmer</em></a><em>”. If </em><strong>O(n)</strong><em> is confusing, feel free to take a break and read Justin’s article.</em></p><p><strong>O(n) space complexity</strong> means that if we’re sorting <strong>n </strong>items, we also need the same amount of space to sort those items.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rDukKnTVZ8IA5ShZe0_nrA.png" /><figcaption>The amount of space required increases linearly with the number of items</figcaption></figure><p>To help us visualize this, let’s apply the constraint that the cards are not allowed to overlap. That means the amount of desk space that we need is the amount of space that’s required to place 5 cards without overlapping.</p><p>If we translate this idea to a computer program, we might use an array with 5 slots: one for each card. That’s where <strong>O(n)</strong> comes from. For <strong>n</strong> cards, we need <strong>n</strong> spaces to perform the sort.</p><h4>Time Complexity</h4><p>The key to our algorithm is that <em>for each card in the unsorted pile, find the person with the highest score, and move them over to the sorted pile</em>.</p><p>Let’s unpack this statement.</p><p><strong>“For each card in the unsorted pile” </strong>means that we need to perform some action for every item in the input. If there are <strong>n</strong> items in the pile, we have to perform <strong>n</strong> actions. In Big-O notation, we would say that this takes <strong>O(n)</strong> <strong>time</strong>.</p><p>Now let’s take a look at the action that needs to be performed for every item.</p><p><strong>“Find the person with the highest score” </strong>means that we have to look at every card to pick the one with the highest score. If we have 5 items in the unsorted pile, we have to look at all 5 of them to determine which one actually has the highest score… but we have to repeat this process for every card in the unsorted pile!</p><p>This means that we actually have to look at every card <strong>n*n</strong> (or <strong>n²</strong>) times. In Big-O notation, we would write this as <strong>O(n²)</strong>.</p><p>However, there’s one more part to analyze.</p><p><strong>“Move them over to the sorted pile”</strong> is the act of moving or swapping the cards. Within a computer program, moving or swapping can be implemented as variable assignment, which is a <em>constant time</em> operation. A constant time operation is something that always takes the same amount of time.</p><p>Even though we eventually have to move every card over to the sorted pile, Big-O notation is concerned with the <strong>worst case</strong>, which is already <strong>O(n²)</strong>. Constant time operations would not change the worst case runtime, so we just say that our algorithm runs in <strong>O(n²)</strong> time.</p><p>Now that we’ve explored a real world example, let’s implement selection sort!</p><h3>Stepping Through The Algorithm</h3><blockquote>For every item in the unsorted list, we want to find the smallest element in the rest of the list. Once we find it, we’ll swap the current item with the smallest element.</blockquote><p>Let’s step through this algorithm with an example.</p><p>We start with an unsorted list:<strong> [99, 79, 84, 80, 92]</strong></p><ul><li>The first item is <strong>99</strong>, and the rest of the items are <strong>[79, 84, 80, 92]</strong></li><li>The smallest item in the rest of the list is <strong>79</strong></li><li>Now we swap the current item (<strong>99</strong>) with the smallest item (<strong>79</strong>)</li><li>The list now looks like this: <strong>[79, 99, 84, 80, 92]</strong></li><li>At this point, the first item in the list is the smallest item in the list.</li></ul><p>Now we repeat this for every other item in the list:</p><ul><li>The second item in the list is <strong>99</strong>, and the rest of the items are <strong>[84, 80, 92]</strong></li><li>The smallest item in the rest of the list is <strong>80</strong></li><li>Now we swap the current item (<strong>99</strong>) with the smallest item (<strong>80</strong>)</li><li>The list now looks like this: <strong>[79, 80, 84, 99, 92]</strong></li></ul><p>Notice that as we iterate through the list, we begin to notice that the part we’ve iterated through is sorted, so we can visualize the list as having a sorted part and an unsorted part:</p><ul><li>Sorted part: <strong>[79, 80]</strong></li><li>Unsorted part: <strong>[84, 99, 92]</strong></li></ul><p>This is a lot like how we were shuffling the cards in place on the table!</p><p>Before we look at code, let’s finish tracing the algorithm:</p><ul><li>The next item in the list is <strong>84</strong>, and the rest of the items are <strong>[99, 92]</strong></li><li>The smallest item in the rest of the list is still <strong>84</strong></li><li>Even if we swap the current item (84) with the smallest item (84), the list looks the same: <strong>[79, 80, 84, 99, 92]</strong></li></ul><p>At this point the sorted part is <strong>[79, 80, 84]</strong> and the unsorted part is <strong>[99, 92].</strong></p><ul><li>The next item in the list is <strong>99</strong>, and the rest of the items are <strong>92</strong></li><li>The smallest item in the rest of the list is <strong>92</strong></li><li>Now we swap the current item (<strong>99</strong>) with the smallest item (<strong>92</strong>)</li><li>The list is now <strong>[79, 80, 84, 92, 99]</strong></li></ul><p>We just stepped through the whole algorithm, so let’s see what this might look like in code.</p><h3>Implementation</h3><p><em>The following implementation is written in </em><a href="https://www.python.org/"><em>Python</em></a><em> because the language has a lot of built-in features that make it easy to read.</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a930764e63c6561710de2fcf5803fead/href">https://medium.com/media/a930764e63c6561710de2fcf5803fead/href</a></iframe><p>In Part 2, we’ll explore the limitations of the selection sort algorithm and discover some new ways to improve on what we’ve learned.</p><p><em>This is part of a series that I’m creating to teach the fundamentals of computer science and algorithms in a way that’s approachable to people without a computer science background.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2c7cc68c422" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Search]]></title>
            <link>https://medium.com/@uncompiled/binary-search-b8f8efcea0f8?source=rss-8c47dada274b------2</link>
            <guid isPermaLink="false">https://medium.com/p/b8f8efcea0f8</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[binary-search]]></category>
            <dc:creator><![CDATA[Chris Nguyen]]></dc:creator>
            <pubDate>Thu, 07 Sep 2017 23:31:11 GMT</pubDate>
            <atom:updated>2017-11-13T01:28:57.140Z</atom:updated>
            <content:encoded><![CDATA[<h4>Algorithms for Everyone</h4><p>If you’re a new to programming or a self-taught programmer, binary search might sound daunting or complex. After all, <em>binary</em> is the language that your computer speaks (ones and zeroes), right?</p><blockquote>1101 1001 0001 1010 1010 0010 1100 01010 1000 0100</blockquote><p>In this case, binary search refers to a “binary decision”, which means that every time we make a decision, we have two choices:</p><ul><li>One choice leads us to whatever we’re looking for.</li><li>The other leads to a dead end.</li></ul><p>The “trick” to binary search is knowing what question to ask.</p><p>In the game of “<a href="https://en.wikipedia.org/wiki/Twenty_Questions">20 Questions</a>”, players ask “Yes/No” questions to guess an item. The type of question that is asked has a significant outcome on the game!</p><h4><strong>“Is it Taylor Swift?”</strong></h4><p>The answer to this question lets you know that the item is (or isn’t) Taylor Swift, but it doesn’t significantly reduce the potential answers. If we always ask questions like this, it would take forever to find the answer.</p><h4><strong>“Is it living?”</strong></h4><p>The answer to this question lets you know that the item is either living or inanimate object. If the answer to this question is “No”, then we know that it isn’t Taylor Swift, but we also know that it isn’t a puppy or a flower. This question removes half of the potential answers!</p><p>Binary search is commonly used in solving more complex problems, so it’s worth learning how and why it works.</p><h3>How does binary search work?</h3><p>Let’s imagine that you’re throwing an epic party. You’ve sent out the invites and everyone’s coming! Tonight’s the night and you’ve got the guest list in your hands. Everyone is sorted alphabetically by last name, but it’s still <strong>100 pages long</strong>!</p><p><em>(I told you, this is going to be an epic party.)</em></p><p>Kit Harington is the first to show up, so you start flipping through the pages to find his name.</p><p>Where do you start?</p><p>Well, you <em>could</em> start on the first page and look at every single name until you find him. Since the guest list is in alphabetical order, you’ll eventually find it. The only problem is that Mark Wahlberg is up next and he’s not going to enjoy waiting until you flip through the first 90 pages to get to the Ws.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*bL_PZ1GB0C_qHDWA1pbCcQ.gif" /></figure><p><strong>Another approach is to pick a page somewhere in the middle of the stack.</strong></p><p>“Harington” is in the first half of the alphabet, so take a look at the first name on the page. If it comes after “Harington”, you know that you only need to search the first half of the guest list.</p><p>You keep doing this until you find the name that you’re looking for:</p><ul><li>Pick a page somewhere in the middle.</li><li>Decide whether to continue searching the first half or the second half.</li></ul><p>This is exactly how binary search works.</p><ul><li>Given a sorted list, compare the item in the middle of the list to see if it’s what you’re looking for.</li><li>If it’s not, check the item in the middle of the list to see if it is less than or greater than the item that you’re looking for.</li><li>Each time you perform this check, you throw out half of the list because you know it’s in the <em>other</em> half.</li><li>Repeat this until you’ve found what you’re looking for… or there’s nothing left and you know that it isn’t there.</li></ul><p>When you’re designing an algorithm, it’s helpful to write down the steps like this because it lets you think about how to solve the problem without implementation details getting in the way.</p><h3>Why is binary search important?</h3><p>Many other algorithms and data structures build on the idea of binary search. Most databases use some form of binary search and you can probably find it used in the code that searches for files on your computer.</p><p>The effectiveness of this algorithm lies in breaking down the problem into smaller parts. Since the input must be a sorted list, this algorithm uses the property of being sorted to divide the problem in half at every step.</p><p>This idea isn’t limited to computers either. If we have a daunting list of errands or tasks that need to be done, one way to increase your efficiency is by figuring out what you <strong>don’t</strong> have to do. You’re going to be more efficient if you can focus on tasks that produce value and ignore the tasks that don’t.</p><p>In binary search, when we compare the item in the middle of the list to the item that we’re looking for, what we’re actually doing is trying to figure what work we can remove from our to-do list.</p><blockquote>Binary search is all about throwing out the work that doesn’t provide value, so that we can focus on the work that gives us more information.</blockquote><h3>Implementation</h3><p>The following implementation is written in <a href="https://www.python.org/">Python</a> because the language has a lot of built-in features that make it easy to read.</p><p>It’s also implemented using recursion. Although recursion can be a difficult topic for beginning programmers to understand, I think the recursive implementation underscores the behavior of the binary search algorithm (which is that if we don’t find what we’re looking for, we keep searching on smaller parts of the original list). If the concept of recursion is tough for you, Daniel King wrote a great post about <a href="https://medium.com/@daniel.oliver.king/getting-started-with-recursion-f89f57c5b60e">learning to think with recursion</a>.</p><h4>The Algorithm</h4><p>In this algorithm, we check the item in the middle of list at every step. If that item is the one that we’re looking for, then we’re done!</p><p>Otherwise, we break up the list into two smaller lists (the first half &amp; the second half), but now we have to decide which half to search. That decision is done by checking whether the item in the middle of the list comes <em>before</em> or <em>after</em> the item we’re looking for.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0f3863574f984f22805de5d9fe8d9e38/href">https://medium.com/media/0f3863574f984f22805de5d9fe8d9e38/href</a></iframe><h3>Performance</h3><p><em>If you’re new to Big-O Notation, Justin Abrahms wrote a helpful post called “</em><a href="https://justin.abrah.ms/computer-science/big-o-notation-explained.html"><em>Big-O notation explained by a self-taught programmer</em></a><em>”. If any of the following is confusing, feel free to take a break and read Justin’s article.</em></p><p>When programmers talk about the performance of an algorithm, they’re usually concerned with the worst-case scenario.</p><p>To understand why the worst-case scenario is the most useful, let’s start by analyzing the runtime performance of the brute-force approach.</p><h4>Start on the first page of the guest list and read everyone’s name until we find the name that we’re looking for…</h4><ul><li><strong>In the best case</strong>, the name that we’re looking for is the first name in the list. That takes no time at all, but what are the odds that you’ll only search for the first name in the list.</li><li><strong>In the worst case</strong>, we have to find the name of the last person on the guest list. That means flipping through 100 pages of names! What if there were 1,000 pages or 1,000,000 pages!</li></ul><p>If there are <strong>n</strong> people on the list, then we would say that this algorithm’s performance is <strong>O(n)</strong>. This means that in the worst-case, you’ll have to look at every item.</p><blockquote>The reason that programmers care about the worst-case scenario is because <strong>it’s a guarantee that calling this function will never take longer than the worst-case</strong>.</blockquote><p><strong>In the case of binary search</strong>, we throw away half of the list every time we check to see whether we’ve found a match.</p><p>If there are 100 people to start with:</p><ul><li>The first check removes 50 names from the potential search space.</li><li>The second check removes 25 names.</li><li>The third check removes 13 names.<br><em>(12 names + the name that you’re checking)</em></li><li>The fourth check removes 7 names.<br><em>(6 names + the name that you’re checking)</em></li><li>The fifth check removes 4 names.</li><li>The sixth check removes 2 names.</li><li>The seventh check only has 1 name.</li></ul><p>This means that binary search takes no more than 7 checks to search a list of 100 people. If you perform this exercise for every possible list, you would find that the graph looks a lot like a logarithmic curve. In Big-O notation, this is written as <strong>O(log(n))</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*IaiR2lYe5lGsAKEkIWMTwg.png" /></figure><p>This graph shows that the brute force method <em>(of starting at the beginning of the list and reading every name) </em>doesn’t scale very well. For a list of 1,000,000 names, we eventually have to read 1,000,000 names.</p><p>The party would be over before you could find Billy Zane’s name!</p><p>On the other hand, using binary search on a list of 1,000,000 names, we can <strong>always</strong> find Billy Zane’s name in less than 20 tries. That’s the guarantee that Big-O notation provides. No matter how big the list becomes, the number of steps needed to find an item is <em>no worse</em> than <strong>log(n)</strong>.</p><p>To put the performance of binary search into context, let’s imagine that you’re a developer at Facebook, where they currently have more 1 billion users. Let’s say that you have to build a new feature that requires looking up a specific user name. You probably don’t want to use brute-force to search a billion users! If each try takes 1 millisecond, the brute-force approach would take over <strong>270 hours</strong>, but<strong> </strong>a binary search would return an answer in <strong>30 milliseconds</strong>. That’s a tremendous improvement and why binary search is a useful algorithm to understand.</p><p><em>This is part of a series that I’m creating to teach the fundamentals of computer science and algorithms in a way that’s approachable to people without a computer science background.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b8f8efcea0f8" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>