Algorithms Introduction
BACK: Table of Contents
Introduction
When you’re playing your favorite card game with your buddies and you’re given 13 cards, how do you go about sorting your cards? Do you just sort of scan through each card to find where it would go? Do you start with the first card and then place the next cards either higher or lower than that first card? Do you split your cards up in half over and over again and then merge the piles up in a sorted order? Do you randomly shuffle your cards and then hope that it miraculously ends up in a sorted order?
Consider the sorting problem:
This ‘black box’–however we decide to sort our cards–can be considered as an algorithm. We call algorithms correct if for every input, it produces the correct output. However, there are more than just the inputs and outputs: Algorithms aim to make things efficient, both in speed and in space. Even if we had infinite storage and infinite computing power, we still want to consider algorithms.
What if your friends decided to play with 1000 deck of cards instead of just 1 to make one giant super game just for the giggles. How would you sort out your 1300 cards? What if you decided to play with 100000000 deck of cards? Suddenly shuffling your cards seems less viable.
If Friend A decided to do this randomly card shuffle–we might be starting the game a year out from now. If Friend B took look through each card and then place it in the right place, it might work out for us a month later. But interestingly enough, if we split the cards up in half over and over again, we might find that we’d be playing in a day or so.
This is the idea that algorithms poke at: How can we solve our problems in a efficient (quickly and with as little storage as possible) manner?
Example (pg 12): Consider the case where you have two different computers, one which is faster than the other. Computer A can perform 10 billion (\(10^{10}\)) instructions per second while Computer B can only perform 10 million (\(10^7\)). Suppose we wanted to sort the same array of 10 million numbers, but computer A runs insertion sort (\(2n^2\) instructions) while computer B runs merge sort (\(50nlg(n)\) instructions), where n is the number of numbers to sort. Running the math out gives us:
\[\text{Computer A: }\frac{2 * (10^7)^2\text{ instructions}}{10^{10} \text{ instructions/sec}} = 20,000 \text{ seconds (~5.5 hours)}\] \[\text{Computer B: }\frac{50 * 10^7lg(10^7)\text{ instructions}}{10^7 \text {instructions/sec}} = 1163 \text{ seconds (~20 minutes)}\]So even though Computer B was slower than Computer A, we can see that having an efficient algorithm that is scalable (to higher degrees of n) can save us a ton of time–this will only grow bigger with larger n. We will continue exploring this idea in the next section. Here’s an example from homework in FA 18, also similar to Problem 1-1 (pg 15).
Of course, there are a ton of different problems–not just the sorting problem. Finding subsequences, stealing from stores, determining cancer mutations, and many more!