1667: Algorithms

2016-04-13T07:38:03Z

Rorih: /* Explanation */ title text

{{comic
| number = 1667
| date = April 13, 2016
| title = Algorithms
| image = algorithms.png
| titletext = There was a schism in 2007, when a sect advocating OpenOffice created a fork of Sunday.xlsx and maintained it independently for several months. The efforts to reconcile the conflicting schedules led to the reinvention, within the cells of the spreadsheet, of modern version control.
}}

==Explanation==
{{incomplete|Still need an explanation of the title text, and perhaps some expanded definitions of the listed algorithms.}}
An algorithm is a basic set of instructions for performing a task, usually on a computer. This comic lists some algorithms in increasing order of complexity.

At the simplest end is '''left-pad''', or adding filler characters on the left end of a string to make it a particular length, typically used in cryptography, but also in a few other areas. In many programming languages, this is one line of code.

Next is '''quicksort''', a classic (if not very efficient) way to sort a list of items.

'''Git''' is a version control program, i.e. software that allows multiple people to work on the same files at the same time. When someone finalizes ("commits") their changes, the version control program needs to figure out how to join the new content with the existing content. This process is called '''merging''', and the algorithm for it is anything but simple.

'''Self-driving car''' is what it says on the tin: an automobile with sensors and software built into it so that it can maneuver in traffic autonomously, i.e. without a human controller. Various companies have been working on such vehicles for many years now, and while they're further along now than would have been imaginable even a couple of years ago, we're still far away from the dream of hopping in a driverless taxi and sitting back as the car itself navigates to where we want to be.

The '''Google search backend''' is what enables you to type "what the heck is a leftpad algorithm" into your browser and have Mr. Google return a list of relevant results, including correcting "leftpad" to "left-pad", ignoring the "what the heck" part, and sometimes even summarizing the findings into a box at the top of the results. Behind all that magic is a way to remember what pages the internet contains, which is just a mind-bogglingly large quantity of data, and an even more mind-numbingly complex set of algorithms for processing that data.

The last item is the punchline: a sprawling Excel spreadsheet built up over 20 years by a church group in Nebraska to coordinate their scheduling. Spreadsheets are a general [https://en.wikipedia.org/wiki/End-user_development end-user development] programming technique, and therefore people use Excel for all sorts of purposes that have nothing to do with accounting (its original purpose), including one guy who made a role-playing game that runs in Excel; but even that doesn't approach the complexity that develops when multiple people of varying levels of experience use a spreadsheet over many years for the purpose of coordinating the schedule of several coordinated groups.

The scheduling of tasks over a group of resources (a.k.a. the ''[https://en.wikipedia.org/wiki/Nurse_scheduling_problem nurse scheduling problem]''), while respecting the constraints set by each person, is a [https://en.wikipedia.org/wiki/NP-hardness highly complex] problem requiring stochastic or heuristic methods for its resolution. Here, the algorithm would be further complicated by being solved by inexpert users over a spreadsheet model without without using engineering practices. The hyperbole here is in thinking that such combination of circumstances would produce complexity far over that required to drive a car or sort the public contents of the internet.

In the title text, part of the spreadsheet's complexity is described as originating from different versions of the file for different programs. The words used like schism and sect are normally used in context of religions splitting into groups about differences in believe questions. This refers on one hand to the church group handling the spreadsheet. But in this case the group split up over the use of open source software and not believe questions. On the other hand discussions on open source software are sometimes led like religious debates.

==Transcript==
'''Algorithms''' By Complexity
{|
|colspan="6" style="text-align:left;border-bottom:1px solid;"|More complex →
|- style="vertical-align:top;"
|style="padding-right:2em;"|Leftpad
|style="padding-right:2em;"|Quicksort
|style="padding-right:2em;"|GIT Merge
|style="padding-right:2em;"|Self- driving car
|style="padding-right:8em;"|Google Search backend
|Sprawling Excel spreadsheet built up over 20 years by a church group in Nebraska to coordinate their scheduling
|}

{{comic discussion}}


[[Category:Charts]]

explain xkcd - User contributions [en]

1667: Algorithms