Editing 1667: Algorithms

{{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==
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, where complexity may refer to either {{w|computational complexity theory}} (a formal mathematical account of the {{w|computational resource}}s – primarily computation time and memory space – required to solve a given problem), or the more informal notion of {{w|programming complexity}} (roughly, a measure of the number and degrees of internal dependencies and interactions within a piece of software).

At the simplest end is '''left-pad''', or adding filler characters on the left end of a string to make it a particular length. In many programming languages, this is one line of code. This is possibly an allusion to a [http://www.haneycodes.net/npm-left-pad-have-we-forgotten-how-to-program/ incident] when {{w|Npm (software)|NodeJS Package Manager}} [https://www.techdirt.com/articles/20160324/17160034007/namespaces-intellectual-property-dependencies-big-giant-mess.shtml angered a developer] in its handling of a trademark claim. The developer unpublished all of his modules from NPM, including a package implementing left-pad. A huge number of programs depended on this third-party library instead of programming it on their own, and they immediately ceased to function.

'''{{w|Quicksort}}''' is an efficient and commonly used {{w|sorting algorithm}}.

'''{{w|Git (software)|Git}}''' is a {{w|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 join the new content with the existing content. When more than one person has made overlapping changes at the same time, the process of figuring out how to join them is called '''{{w|Merge (version control)|merging}}''', and the algorithm for it is anything but simple.

A '''{{w|self-driving car}}''' is an automobile with sensors and software built into it so that it can maneuver in traffic autonomously, i.e. without a human controller. Vehicles that require zero user-guidance on the roads were commonly predicted to become widely available in the 2010s, but the algorithms required to handle any possible road and weather situation has proven much more complex than expected. [[Randall]] made several [[:Category:Self-driving cars|references to self-driving cars]] in the mid-2010s.

The '''{{w|Google Search}} backend''' is what enables you to type "what the heck is a leftpad algorithm" into your browser and have Google return a list of relevant results, including correcting "leftpad" to "left-pad", truncating "what the heck is" to simply "what is", 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 [[1605: DNA|mind-numbingly complex]] set of algorithms for processing that data.

The last item is the punchline: a sprawling {{w|Microsoft Excel|Excel}} {{w|spreadsheet}} built up over 20 years by a church group in Nebraska to coordinate their scheduling. Spreadsheets are a general {{w|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 [http://arstechnica.com/gaming/2013/04/how-an-accountant-created-an-entire-rpg-inside-an-excel-spreadsheet/ 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 ''{{w|nurse scheduling problem}}''), while respecting the constraints set by each person, is a {{w|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 using engineering practices. The potential 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. While most churches meet mainly on Sunday morning, scheduling of what happens during the service when (especially if there are multiple concurrent services) as well as Sunday School, church business meetings, and congregation-wide events all potentially needing to be scheduled on a particular Sunday morning, the need to find a solution very close to the best possible solution quickly becomes a dire need. Furthermore, with different members involved in a wide variety of activities within and outside of the church, and the classrooms available to the church on Sunday itself, (just scheduling the choir practice times to coordinate with everyone's work schedules is very possibly impossible, especially if two people share the same occupation, and one is the relief for the other,) can indeed be daunting. In addition, there would likely be assorted committee meetings and youth groups during the week.

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 {{w|schism}} and {{w|sect}} are normally used in context of religions splitting into groups about differences in beliefs. In this case, the split seems to have been not over a {{w|theology|theological}} issue, but about the use of {{w|open-source software|open-source}} vs. {{w|proprietary software|proprietary}} software, disagreements about which are often compared to religious debates. Most likely, the schism being referred to is the {{w|East–West Schism|East-West Schism of 1054}}.

The title text also implies that while trying to reconcile after the schism and to merge the two schedules they reinvented an alternative to Git within the spreadsheet itself, making the algorithms in place at least as complicated as that. Since most spreadsheet programs have a sort algorithm built in, that aspect is implied too, and left-padding could be compared to vamping on an introduction to a hymn. This would indicate that the other milestones of complexity are either included in the current version of the spreadsheet or are planned to be implemented.

==Transcript==
'''Algorithms'''<br>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<br>Merge
|style="padding-right:2em;"|Self-<br>driving<br>car
|style="padding-right:8em;"|Google<br>Search<br>backend
|Sprawling Excel spreadsheet<br>built up over 20 years by a<br>church group in Nebraska to<br>coordinate their scheduling
|}

{{comic discussion}}

[[Category:Charts]]
[[Category:Google Search]]
[[Category:Programming]]
[[Category:Religion]]
[[Category:Self-driving cars]]
[[Category:Spreadsheets]]
[[Category:Version Control]]