Computer Science: Algorithms
We've already discussed abstract data types and how to implement real-world things using a set of tools available to us when using a particular programming language. Next we'll discuss a few algorithms that will give us a foundation to discuss more advanced computer science topics, and also help can us make better choices when writing code.
By the end of this, developers should be able to:
- Define "algorithm"
- Identify what Big-O time-complexity measures
- Give an example of a divide-and-conquer algorithm
- Predict the time-complexity of a given algorithm
- Fork and clone this repository.
algorithm (n.) - a process or set of rules to be followed to attain a goal
Algorithm is a fancy word for recipe. When we have a problem, we take a series of steps to solve that problem. Say I want a peanut butter and jelly sandwich, and Robin has agreed to make it for me. The problem is, he doesn't know how. Assuming an otherwise-adult set of knowledge, how might we tell Robin to make me a sandwich?
- Go to the 12th floor
- Go to the kitchen
- Find the bread, toaster, utensils, peanut butter, and jelly
- Toast the bread
- Using a knife or spoon, spread one slice of toast with peanut butter
- Spread the other slice of toast with jelly
- Place the two pieces of bread together
- Return to me with the sandwhich
If Robin needed to make sandwiches for all of us, how would he do that? What's the "easy" or naïve way to obtain many sandwiches? What is a more efficient way?
Lab: Outline an Algorithm
Take a few minutes to describe your morning algorithm... uh, routine. Share it with a neighbor. How many steps are there? How do you save time if you're in a rush?
Follow Along: Sorting Cards
I have a deck of unsorted playing cards. Describe in English an algorithm for sorting them. How would this algorithm change if my goal were not only to sort the deck, but to kill time while doing it?
A well-known problem in computer science is sorting an array. There are many strategies (read: algorithms) for accomplishing this. Here is an incomplete list:
- Bubble sort
- Quick sort
- Merge sort
- Insertion sort
- Selection sort
- Heap sort
This illustrates something important about algorithms: you nearly always have a choice. There is no "one way" to solve a problem, no "right" way. Different algorithms are better in different contexts, or with different constraints. It's up to you to consider the options and pick the one that best meets your needs.
Lab: Research Quick Sort
Lab: Visualize an Algorithm or two
Let's visualize both selection sort and insertion sort with six volunteers holding cards.
Big-O (Asymptotic Analysis)
We use "Big-O" notation to describe an algorithm's complexity. Complexity measures how much time is needed and how much space is required to scale with input. A common optimization technique is to trade increased space complexity for reduced time complexity (and less commonly vice versa).
Question: Why do we focus on time-complexity?
Take a simple algorithm for demonstration purposes: printing an element of an array to the screen.
[1, 2, 3].each do |n| puts n end
This procedure iterates through an array and prints each element to the screen.
This example has three steps. If the array had five elements, five steps would
be require to print all the elements complete. We say that this procedure has
linear time-complexity: the time-to-complete grows in lock-step with the number
of elements. This is denoted
O(n) and pronounced "Big o of n", "O of n", or
To identify an algorithm's complexity, we focus on the "family" of scaling functions the algorithm belongs to. We don't care about exact values. For example:
[1, 2, 3].each do |n| puts "hello!" puts n end
This procedure prints two lines to the screen on each iteration, for a total of
six lines. If we had a five-item array, it would print ten items to the screen.
You might be tempted to say this algorithm has complexity
y = 2n is still a linear function, so it is more appropriate to say that this
procedure is linear (
Another way of saying we care about the "family" of scaling functions is to say
we care about the shape of the scaling function for an algorithm. In both of the
previous examples, graphing elements (
n) against completion time yields a
straight line, hence we say that the procedures scale linearly.
Lab: Study Big-O Families
How can you predict the complexity of a given algorithm? We can look for certain features to help us characterize it.
- Loops take linear time to complete (
- Nested loops take quadratic time to complete (
O(n^2)), or worse, cubic time (
- For consecutive statements, add the times-to-complete.
- For branching statements (
if/else), take the complexity of the worse branch.
- Generating all the possible permutations of a set, e.g.
cba, etc, takes factorial time (
Here's a party trick that is sure to make you popular. Bet someone you can state
with certainty a number they've chosen, between one and one hundred, after seven
questions. The questions will all be "Is
<number> less than the number you've
chosen?" Before I show you how, let's look at a simplistic solution that takes,
at worst, 100 guesses:
1. Guess "1". If no, 2. Guess "2". If no, 3. Guess "3". If no, ... 100. Guess "100". You win!
Question: What is the complexity of this algorithm?
The algorithm that gets you there in the minimum number of guesses is called a "binary search". It goes like this:
- Calculate the mid-point of the array.
- If it is the target value, return it and you're done.
- If not, ask if the mid-point is less than their chosen number.
- If not, the answer is in the upper half-range. If so, it's in the lower half-range.
- Repeat the above steps until there are only two numbers left.
- The final "less than" question gives you the answer.
It's relatively easy to see in a tree diagram. Can you see the binary structure of the tree?
Would checking if the middle number is the correct answer speed things up?
A binary search works with any direct access weakly ordered set (an ordered array with elements that may compare equal). See here for a more rigorous algorithm.
Question: Explain why this algorithm is an example of divide-and-conquer in your own words.
- Big-O Algorithm Complexity Cheat Sheet
- Sorting Algorithm Animations
- A Beginner’s Guide to Big O Notation « Rob Bell
- Fibonacci sequence - Rosetta Code
- Bubble-sort with Hungarian ("Csángó") folk dance - YouTube
- Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - YouTube
- CS50's Sort lesson
- Big O Notation in JS
- Algorithms in JS
- More Algorithms in JS
- The Definitive Guide To Time Complexity For Ruby Developers
- The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms
- Visualization of Common Time Complexities
- Ruby Binary Search Implementation
- Algorithms Explained like Ikea Instruction Manuals
- Sorting Algorithms Visualization
- All content is licensed under a CCBYNCSA 4.0 license.
- All software code is licensed under GNU GPLv3. For commercial use or alternative licensing, please contact email@example.com.