I recently came across this example in my “Learning Python” book:
It converts a binary string to integer. The ord method is interesting, but I was interested in the algorithm itself. The algorithm says to look at the digits one by one, and each time through the loop, multiply the current value by 2 and add the next digit’s integer value. In this case, ‘1011’ would end up printing 13, which is correct. 13 in binary is 1011.
But then I struggled to think of how this would work. My naive solution would be to create a powers of two table, work my way from left to right, and get the highest value I can get without going over. For instance, 2^4 is 16, so I have to use 2^3, which is 8. Thus there is a bit in the 2^3 spot. Next I try 2^2, which is 4, and 8 + 4 is less than 13, so I can put a bit in the 2^2 spot. Then I try 2^1 which is 2, and 8 + 4 + 2 is 14, which is larger than 13, so there is a 0 in the 2^1 spot. And finally I need 2^0, as that is 1, and 8 + 4 + 1 = 13.
Since that was my solution, I would try to convert to code – because often times how you think about a solution is how you write it in code.
However, that was not what the book had. I now know what the book did.
Any integer can be represented in the form:
N is the integer, x_n is the number of digits depending on the base. So if it’s base 2 (binary), then it’s either 0 or 1. If it’s base 10, then it’s 0-9. q^n is going to be the base to the nth power. For binary, it’s going to be 2^n.
13 can be represented like this:
Now we can factor the 2 out, and keep factoring out the inner 2 until we can’t anymore:
We end up with the bottom form, which makes it easier to see why the original algorithm works. As a reminder, the original algorithm says multiply the current value by 2, and then add the next value. This is indeed what we do with (1), (2), and then (3).
In Part I, we looked at an implementation of Stacks using Linked Lists. In this post, we’ll look at Linked Lists with Queues.
As a review of the Linked Lists of Stacks, here’s a drawing of the implementation of Stacks using the linked-list nodes:
As you can see, the latest node points to the previous node, which points to the node previous to that, etc…
Whenever we add a new node to the Stack, we make sure we point it back to the previous node. Once we “pop” the stack, we return the value of the “current” node, and follow the “current” node’s pointer back to the previous node, which we now make as the new “current” node. The previous “current” node is now orphaned, and left for the garbage collector. The main thing to note is that the pointers are going backwards (towards the left), as we add more nodes to the Stack.
In my implementation of a Queue, the pointers are going to go in the opposite direction! Check it:
The pointers are now going to the right. What’s going on ? In a queue, recall that it’s “FIFO”, or “First in, First Out”. We start out with a single node as our first item. When we add a node, the previous node points to our new node.
In order to “pop” (we call it “dequeue” in this case), we have to remember our very first node on the left, so we assign a variable to keep track of it. After that first node is returned, we follow it’s pointer to the next node, and make this next node the “first” node. The first node is then orphaned, and gets cleaned up from the garbage collector.
In addition to remembering our first node, we also have to keep track of our most recent node, in order to add the future nodes to it. Let’s talk with code now:
The “@q” variable is our “first” node, and the “@current” variable is the latest node.
To summarize, creating Stacks and Queues with linked lists has some advantages:
We don’t need to keep track of the size of the array, and the memory is dependent strictly on how big our list is
As another point related to size – the bigger the size, the longer it takes to do certain operations, such as resizing. For instance, downsizing a large array takes at least as many operations as the size of the array to resize, since we’re copying the values. In linked lists, the time is independent of the size
It’s easier to think about conceptually, then the resizing (more of an opinion)
As one might have imagined from the many hints and questions from the previous post, linked lists can be very useful when dealing with Stacks and Queues.
To define a linked list, let’s start with the basic element of a linked list, called a node. Here is my silly illustration of a node:
The left box represents the “value” of the node, and the right box represent where to look for the next node. That’s it!
You can put nodes in a list like this:
The leftmost node has a value, and it also tell us where to go for the next node, which is the node in the center. The center node has a value and tells us to look at the right node next. Nodes in a list are called a “linked list.”
Let’s see a node represented in Ruby!
In this “node class”, there are two variables: “item” and “next”.
The “Item” can hold anything you want: Strings, Numbers, Integers, Arrays, Hashes, other Ruby classes, etc… the “list” goes on (pardon my intended pun). The “next” is like a pointer, in that it shows us where to look for the “next” node.
To see it in action, here is one implementation of a Stack using Linked Lists:
We need our node class, so the first line requires it. Before saying anything, see how much shorter the code is already! This has to do with not needing to remember the array size. If all you need to remember is where to go next, you don’t need to remember to resize your data structure once you hit size limits. The Linked Lists shrinks and grows on command, and “orphaned” nodes are cleaned up by the garbage collector. It seems to be more pleasant to read (and implement) the stack class using linked lists.
The stack is initialized by creating a single node. As we add items to the stack, we tell our new node to point to our previous node. Unlike the array implementation where we had to keep track of all elements in the stack, all we ever have to know at any point in time is our latest node when we use the linked list implementation. When we remove items, we follow our latest node to the previous node, and tell the previous node to become the “current” node.
In Part II, let’s see how to implement Queues with Linked Lists!
To get a sense of how important Linked Lists are, it might be useful to imagine a world without Linked Lists.
Suppose we want to build a Stack. A Stack is a collection of objects in a sequence, where the last object added is also the first object removed. The common term is “Last in, first out”, or “LIFO.”
A commonly used real-world example for a Stack is a stack of pancakes. When pancakes are placed on top of each other, the last pancake added is the one on the very top. This very top pancake is also the first to be eaten.
How would we implement a Stack without using Linked Lists ?
Let’s say we are allowed to use an Array to implement our Stack. How big should our array be at the start ?
By its definition, a Stack implies that its size varies with the addition or removal of objects. What if our Stack outgrows our initial Array size ?
If we are able to solve the problem of our Stack outgrowing our Array size, what then if our Stack eventually shrinks significantly ? Would we have hold a large number of empty elements in our Array ?
With some thought, we are able to implement our Stack using just an Array. Here is one implementation:
The main takeaway is that we double the array size whenever we reach our limit, and we shrink to a quarter whenever half of the array is empty (we shrink to a quarter instead of a half so that we aren’t teetering on the edge of doubling or shrinking the array with a single add or drop in the stack). In expanding or reducing the array, we make use of the “resize” method, which makes a copy of the entire array, temporarily doubling the space cost.
Let’s look at another collection of objects – a queue. A Queue is “First in, first out”, or “FIFO”. A queue in the real world could be people lining up to see a movie. The first person in line is also the first person to get into the theater.
We run across the same sizing questions as the Stack – and can handle them similarly.
In the Stack implementation, the last element of the Array was always the element being popped, and the element being pushed was always added at the end of the Array. For a Queue, we need to keep the position of the “head” and “tail” of the queue. If the beginning element of the array is removed when we “dequeue”, what do we do with the empty elements at the beginning of the array as we continue to dequeue ?
Here is one implementation of a Queue using Arrays:
We have to be more careful with our tail and head position of the array. Whenever we resize our array or whenever our head position reaches our tail position, we shift our head position back to the beginning of the array. The length of our queue is determined by our head position less our tail position. After these differences, we handle our sizing decisions are similar to our Stack implementation.
Boy – that’s a lot of resizing and keeping track of positions! A world without Linked Lists is tough!
Can Linked Lists make things easier ? What are Linked Lists ?
Sometimes, an elegant algorithm in computer science is processed the
same way a person would perform a task. For example, if you were looking
up a name in a phone book, you wouldn’t start at the very beginning
of the book. You would perhaps start somewhere in the middle, and divide by half
each time until you zeroed in on the target.
Maybe you know that the phone book is alphabetized, and if the name started with a “B,”
then you might start towards the beginning of the book. However, imagine that you didn’t know
how many names there were for each letter, and it’s possible that letters that
start with “A” could take up a majority of the book. Here, you might guess to
open the book up to about the center, and go from there. For the rest of
this post, let us assume we don’t know the distribution of the numbers in an array,
but only that it is sorted.
When you looked up the numbers in the phone book, you are roughly doing a “binary search.”
Here is a table that shows how a computer might process the steps:
If we were to do a “brute-force” method, which is checking each number starting at
the beginning, the process will take on the order of N/2 times on average, where N
is the number elements in the array. If we guess at random until we find the target,
it will also take on the order of N/2 times on average.
However, binary search limits the set that we must search by half each time, so it
will only take on the order of lg N on average. For illustration, if there were 10,000,000
numbers, the brute-force method will take 5,000,000 steps on average, whereas binary search
will take on average 23 steps!
It is worth thinking about efficient algorithms, because even the best hardware will lose
to a great algorithm.
Euclid was a very prolific mathematician, and it is probably a mistake to be surprised that his name resides in yet another algorithm – one used to determine the greatest common divisor. This is commonly known as Euclid’s Algorithm. This algorithm is very simple (only 2 steps), but it can seem subtle at first.
The greatest common divisor (GCD) is the largest number that two integers can divide by. For instance, the greatest common divisor of 16 and 12 is 4. In this post, we consider only nonnegative integers.
Consider the following illustration (left side only – the one labeled “Euclid’s example”), where the two black bars represent the integers for which we seek the greatest common divisor.
Illustration of Euclid’s Algorithm
The black bars are those labeled AB and CD. Suppose we craft the bars so that CF (blue) is in fact the greatest common divisor of AB and CD. Let AB be 10 times the length of CF, and CD be 7 times the length of CF.
Suppose that the length of AB is larger than the length of CD. The trick in the algorithm is that the difference, or d, between AB and CD (AB – CD) will always be greater than the GCD, unless AB = CD (in which case AB or CD is the GCD).
The reason why d will always be greater than the GCD is because both AB and CD must be a factor of GCD, and the difference between AB and CD must be a factor GCD. Therefore, GCD is a factor of d, so d must be greater than or equal to GCD.
The steps to the algorithm are as follows, if AB and CD are the two nonnegative integers we wish to find the GCD for:
Step 1: Let AB be the larger of the two numbers. Then set d = AB – CD
Step 2: If d = 0, then CD is the GCF. If d is not 0, then repeat Step 1 with AB = CD, and CD = d
However, the subtraction method can take many steps if the two values AB and CD are far apart. It has been common to reduce the number of steps by calculating the remainder between AB and CD. The same logic still applies, however, except we remove the many factors of CD in the difference d between the two numbers AB and CD for each loop.
The Sieve of Eratosthenes is often one of the first algorithms taught in
computer science books. This simple algorithm showcases the ability
to calculate primes numbers through the power of a computer without learning
much of the nuts and bolts of a programming language. Finding the
first 100 prime numbers can be done in a fraction of a second, and the
first 1000 prime numbers performed in a split second. It definitely proves to have a
computer around to aid in computation!
From Wikipedia, here is an animation of how the algorithm works:
Animation showing the Sieve of Eratosthenes
The above animation uses the Sieve of Eratosthenes to find all prime
numbers up to 120.
The number 2 is chosen first as the starting point and first prime. Then, all multiple values of 2
are crossed off (in red) from being prime numbers. Next, number 3 is chosen as a
prime number, and all multiple values of 3 (in green) are crossed off from being
possible prime numbers. Since the number 4 is already marked off as red from being
a multiple of 2, the number 5 is chosen as the next starting point and saved as a prime. This continues
until all positions are either chosen as prime or crossed off.
If n is the value that we want to check prime numbers until, then we will ever cross off
multiples up to sqrt(n), because all multiples of sqrt(n) above sqrt(n) are larger than n.
(This is because we would only ever multiple sqrt(n) by values larger than sort(n) by the
time we get there, since values smaller than sqrt(n) have been crossed off).
The mod operation comes to mind when checking for prime numbers.
Here is the Sieve of Eratosthenes using the mod operation: