Editing 1667: Algorithms
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==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 | + | {{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. In many programming languages, this is one line of code. This is | + | 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 a reference to a [http://www.haneycodes.net/npm-left-pad-have-we-forgotten-how-to-program/ recent incident] when a package implementing this function was unpublished from the {{w|Npm (software)|NodeJS Package Manager}}, after which a huge number of programs which used this third-party library for such a simple function instead of programming it on their own, ceased to function. |
− | '''{{w|Quicksort}}''' | + | Next is '''{{w|Quicksort}}''', a classic way to sort a list of items. |
− | '''{{w|Git (software)|Git}}''' is a | + | '''{{w|Git (software)|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. |
− | + | '''{{w|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 '''{{w|Google Search}} backend''' is what enables you to type " | + | The '''{{w|Google Search}} backend''' is what enables you to type "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 | + | 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 {{w|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 ''{{w|nurse scheduling problem}}''), while respecting the constraints set by each person, is a {{w|NP-hardness | + | The scheduling of tasks over a group of resources (a.k.a. the ''{{w|Nurse scheduling problem|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 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 | + | 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== | ==Transcript== | ||
'''Algorithms'''<br>By Complexity | '''Algorithms'''<br>By Complexity | ||
{| | {| | ||
− | |colspan="6" style="text-align:left;border-bottom:1px solid;"|More complex | + | |colspan="6" style="text-align:left;border-bottom:1px solid;"|More complex → |
|- style="vertical-align:top;" | |- style="vertical-align:top;" | ||
|style="padding-right:2em;"|Leftpad | |style="padding-right:2em;"|Leftpad | ||
Line 40: | Line 39: | ||
|Sprawling Excel spreadsheet<br>built up over 20 years by a<br>church group in Nebraska to<br>coordinate their scheduling | |Sprawling Excel spreadsheet<br>built up over 20 years by a<br>church group in Nebraska to<br>coordinate their scheduling | ||
|} | |} | ||
+ | |||
{{comic discussion}} | {{comic discussion}} | ||
+ | <!-- Include any categories below this line. --> | ||
[[Category:Charts]] | [[Category:Charts]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− |