The Physicist's Paradigm

Our next topic on amortized analysis is a parallel to the Banker’s Paradigm. This new approach, the physicist’s paradigm, is a little more mathematically rigorous, but ultimately should produce the same answer (or same type of answer) as its money-grubbing counterpart. Although both techniques should produce the same result, it is worth understanding both because often times problems are more easily understood when phrased as one or the other.

So what is it?

Think back to your last physics class, remember gravity? If you took any introduction to physics you likely learned about gravitational potential energy, which is the amount of energy stored in an objects distance from the earth. If you take a one kilogram ball and raise it one meter off the ground, you have bestowed it with 9.8 joules of energy. Releasing the ball also releases that energy, which can be seen when the ball falls to the ground. Now, if you remember this, you might also remember that it doesn’t matter what path the ball takes when you lift it up one meter. All that matters for the calculation of gravitational potential energy is the initial and final position.


How do we use it?

So what does this have to do with algorithms? Well, lets look at each step of an algorithm through the lens of energy functions. We are going to use this short function to determine how much work is done by our algorithm at each step. Here, a_i is the amortized cost required to get us from step i-1 to step i, while t is the actual cost of doing step i. Phi is a potential energy value for the data structure, and we look at the change in potential between the previous step and the current one. Now, if you are reading this and have no clue how to calculate the potential energy of a data structure, well, you are in the right place.

Posted

Digits that Divide

Problem Description

Find all 10 digit numbers who for all n=1,2,3,...,9,10 the number formed by taking the leftmost n digits is divisible by n.

In layman's terms, we want to find all 10 digit numbers where:

-The first digit must be divisible by 1. -The leftmost two digits must be divisible by 2. -... -The leftmost nine digits must be divisible by 9. -The leftmost ten digits (the whole number) must be divisible by 10.

The Naive Solution

Well, a program which finds these numbers needs to explore the whole "problem space" (all possible 10 digit numbers) so the easiest way to do this is a loop. We can start at 0000000000 and count up to 9999999999. Each number we go to, we can check if it meets all of these requirements and if so, we can store it.

Code

results = []
for i in range(0,10 ** 10):
  if slowCheckDigit(i):
    results.append(i)
print(results)

def slowCheckDigit(num):
  goodNum = True
  for j in range(10,0,-1):
    if num % j == 0:
      num //=10
    else:
      goodNum = False
      break;
  return goodNum

Analysis

Looking at this code, we see that we will be making 10^10^10 comparisons. This is because we will be looping through 10^10 numbers, and each call to slowCheckDigit requires 10 checks (one for each digit). This is ridiculously bad. I attempted to run it on my desktop and got bored before it finished (a great metric for algorithm complexity). We also check a lot of values we should know better than checking. For example, for the first two digits to be divisible by two, we can pretty easily determine that the second digit should be a 2,4,6,8, or 0. Unfortunately the naive solution not only checks 1100000000 but it checks the 99999999 values which start with 1's in the first two digits. This is really inefficient.

The Advanced Solution

The inspiration behind the advanced solution is to build partial solutions to the problem, and only consider digits that fit with our partial solutions. For example, we would start with a first digit (say 1), and then try all possible second digits for our current "partial solution" of 1XXXXXXXXX (I am using X's to represent unknown values). We would then find a valid second digit (say 2), and repeat the process to find a valid third digit for the partial solution 12XXXXXXXX.


Posted

Amortized Analysis - Bankers Paradigm

In the last post, we learned the absolute basics of Amortized Analysis. To make a long story short (or more specifically, to split a long story up between a series of smaller incremental posts) amortized analysis is a way to look at algorithm's typical cost rather than its strict worst-case run time.

So how does one determine this typical cost in an actually meaningful way?

Turns out there are two main methods, the first of which, the Banker's Paradigm, we will discuss here.

Posted

Intro to Amortized Analysis

This is the first of series of blog posts I intend to make regarding Data Structures. Hopefully these will be informative for anyone who has stumbled to this site, but more importantly, these posts will form the basis for a textbook I am writing for my graduate data structures class. So without further ado, let me present my first topic.

 

Amortized Analysis

Definition: Amortized – “to pay money that is owed for something (such as a mortgage) by making regular payments over a long period of time” ~ Merriam Webster

Which sounds worse? Paying $30 now or paying $1 a day for the rest of the month? Although they are the same amount of money, many people would rather part with their cash in smaller increments spread over a long period of time. Similarly, when making a large purchase, for example a $2000 laptop, it is common to justify the expense by saying “buy I will use that laptop for the next five years!” Such a statement is unconscious amortization.

Posted

Bash on Ubuntu On Windows (First Impressions)

Last week I installed the most recent Windows Insider Preview Build (Instructions Linked)  in order to try out the recent new feature for Windows 10. Bash on Ubuntu on Windows is a native Ubuntu installation which lives alongside Windows 10, albeit sandboxed in its own file system. More details can be found here but the long story short is that it works as advertised. After getting the Windows Insider update, bash can be found from the start menu. Clicking on the familiar orange circle opens a black terminal similar to the standard ubuntu window. From there the user has access to commands like ls, find, top, and most importantly, apt-get. I took a bit to customize my setup and play with bash, and so far I have been really impressed, despite the growing fear that microsoft plans to embrace, expand, and exterminate ubuntu. Unfortunately though, their choice of name is clunky and contains 100% more prepositions than necessary. (For some reason, this fits the Microsoft ethos in my mind...)



Posted