Sorting Algorithms

There's only two reasons to sort a list:

1. So that you can present it in a way that's more readable. Say, a list of state names in alphabetical order.

2. Increase the efficiency of things you do to that list. For example, retrieving and removing the max value element in the list over and over (for some reason...) 

There's a lot of ways to achieve both of those goals. And they all force you to understand the property of the list you want to sort and the characteristics of the sorting algorithm you use. 

• How much data are you trying to sort? 
• Is that data partially sorted?
• Can all that data fit in memory? 
• Does the algorithm you use maintain the relative position of equal values? (stability) 
• Does the algorithm require extra memory?

If you're a programmer, you should at least know the basic properties of some of the most common sorting algorithms such as ...

• Bubble sort (O(n^2))
• Go through the list looking at pairs of elements. If the left one is less than the right, swap their positions.
• Selection sort (O(n^2))
• Start at the first element. Now find the minimum and swap the minimum with the first element and then move on to the second element and find the minimum from the second element to the last and swap. 
• Insertion sort (O(n^2))
• Start at the second element and check if it's smaller than the first. If so, insert it before the first (the first becomes the second). You now have a partially sorted list! Now, you move on to the third element and insert it in the right position in that partially sorted list and continue until you have a fully sorted list.  
• Quick sort  (O(n log n))
• Pick a pivot and swap the elements so that all the numbers smaller than or equal to the pivot is on the left and those larger are on the right. Do this recursively!
• Merge sort (O(n log n))
• Split the list into individual elements, then merge them together (first by pairs) in order. The merge algorithm works by creating a new list and inserting the correct elements into the lists through comparisons of the two lists. 

Most general purpose languages include sorting functions in their core libraries so you shouldn't ever have to write one yourself :)

Telephone Words

Write a function that takes a seven-digit telephone number and prints out all of the possible "words" or combinations of letters that can represent the give number. 

Recursive Solution

• If we've passed 7 digits, print out our current number. Other wise, loop through each letter associated with the current digit, save the current digit in position, and then recurse.

If you want to instead return the values instead of merely printing them, you would want to maintain a running list of all the numbers that grows as the functions "unwind". 

Iterative Solutions

1. Just use 7 for loops :)

for ...

    for ...

        for ...

            :(

1. If you write out a bunch of combinations for a number by going from left to right, you'll notice that as the last digit cycles, the digit to its left also cycles. 

For example, lets say we're only dealing with three sets of characters: [[a,b,c],[d,e,f],[g,h,j]]. Our pattern will be as follows:

a,d,g

a,d,h

a,d,j

a,e,g

a,e,h

a,e,j

a,f,g

a,f,h

a,f,j

b,d,g

...

As you can see, after we go through [g,h,j] at the end once, the previous numbers letter changes from a higher value to a lower value (d to e). We can take advantage of this simply by starting out with a word, say "a,d,g". Then we'll change "g" to "h" and print. Then change "h" to "j" and print. And then since we've gone through a full cycle, we'll reset it back to zero and then change our neighbor to be a higher value ("e"). The trick here is updating the counters for each position correctly (like when [d,e,f] is cycled through, its neighbor is updated. 

Recursion

"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."                                                                                                                                                                                                                                 - Andrew Plotkin

Informally defined, recursion is simply the process of repeating self similar elements. The easiest way to visualize a recursive event is by standing in front of a mirror with a mirror. You’ll see an infinite repetition of the same reflection.

In math and computing, recursion is more formally defined.

In mathematics, recursion is a definition of a function in which the application of the function is in its definition. A common example of this is the definition of the fibonacci sequence, which has two properties:

1. The base case or base cases(a non-recursive definition).
2. A set of rules that reduces all other cases to the base case(s).

In computation, a recursive function is one that invokes itself. In most programming languages, the definition of recursive functions end up closely resembling mathematical definitions of recursive functions.

Daylight Saving

To understand the "why" of daylight saving, we have to dig into the past.

In ancient times, the start and end of labor was determined by the rising and setting of the sun. The notion of having to abide by a specific time schedule is a product of the industrial revolution, when manufacturing factory owners began enforcing time schedules. Be at work at 7AM. Eat at 12PM. Go home at 8PM.

As people of industrial society, we’re accustomed to living by a strict time-based schedule. Nowadays, the starting and stopping in the operation of nearly all of our institutions are based on fixed, precise measurements of time. A store opens at an agreed upon moment in time and is opened for some measure of time. Since so many of our activities are based on some agreed upon measure of time, what if we change the time? What effect will that have on the activities?

In the mid-19th century, a man by the name of George Vernon Hudson pondered those exact questions that led to the implementation of "daylight savings". Hudson was working a shift job that gave him leisure time to collect insects, and led him to value after-hours daylight.

George had later shifts (not uncommon amongst industrial workers), so he wished for the sun to still be out by the time his boss let him off! But if his boss lets him off really late, then he wouldn’t be able to collect insects. Of course, he could always ask his boss to let him out earlier, but most factory owners weren’t that nice - and they certainly weren’t going to change their hours of operation just for a bunch of insect collectors!

Now if your boss won't let you off early, who should you appeal to? Well, Hudson went to the government. If the government moved the time forward, he will be able to get off work early and enjoy the sun! And this concept of moving the time forward to enjoy more sun in the evening is what is now called Daylight Saving.

Unfortunately for George, the government laughed at him. And when this idea of changing the time was finally enacted in 1916, he was already dead.

Learning about the Y-Combinator

Mike Vanier wrote an awesome article on the Y-Combinator function that I've been working my way through. It's a fascinating read. Here are my notes on it so far.

• An explicit recursive definition is a recursive function definition whose body contain the name of the recursive function. For example, (define (hello a) (hello a)).
• It's possible to generate the recursive version of a function without using an explicit recursive definition by use of higher-order functions. Holy shit, right? 
• The Y-Combinator is one such higher-order function that can generate a recursive version of a function by using it's non-recursive function. 
• In functional programming, you can create the non-recursive version of a function by abstracting out the recursive call. So instead of referencing itself, it will reference a function that's to be passed in as an argument by a higher order function. Common technique in FP.
• Pass an identity function as an argument to the non-recursive function to get the factorial of all numbers up to 0. For example, (define factorial-zero (almost-factorial identity)). This will fail for N > 0. However, it will succeed if you pass factorial-zero as an argument to factorial-one! This can be proven although why it works is still a mystery to me. 
• By performing the above process infinity times, you can get the factorial of all numbers up to infinity. The function that can do that for all numbers up to infinity is the factorial function! But how the heck do you define this chain of functions up to infinity?
• To be continued ...

Two definitions of programming

Over the past year I've finally begun to realize that writing machine executable code is not the essence of programming and these two definitions have helped me articulate what's really the essence.

"Well it seems to me the most succesful programmers I’ve encountered don’t craft software; they write software in order to move information around, in order to get something done. Information is the real deal – the software just defines the space that it moves around in. For those programmers, success is about getting information from point A where it’s currently languishing to point B where it’s going to actually be useful, as quickly and effectively as they can." - Dan North

"Programming, by definition, is about transforming data: It’s the act of creating a sequence of machine instructions describing how to process the input data and create some specific output data." - Noel

The movement and transformation of information. How effectively you do this to create value in a domain will determine your worth as a programmer in that domain.

Sublime line editing

One of the most common code editing actions I do is at the individual line level. I copy lines, delete lines, move lines. The shortcuts that sublime provides are great. Here's some of the main ones I use.

Selecting

Select a line - CMD + L

Deleting

Delete from cursor to end of the line - CTRL + K
Delete from cursor to the beginning of the line - CMD + Delete

Delete entire line - CTRL + SHIFT + K (Really annoying to use)

Cut line - CMD + X (delete entire line and copy)

Moving

Move a line up - CTRL + CMD + UP

Move a line down - CTRL + CMD + DOWN

Copying

Duplicate a line - CMD + SHIFT + D

Then there are a couple more that are not about manipulating lines themselves but are based on lines:

Insert cursor to line before current line - CMD + SHIFT + ENTER

Insert cursor to line after current line - CMD + ENTER