Thoughts on String Guessing Algorithms

I recently proposed that an email address be simplified in order to improve the user experience, and I used mathematics to justify the idea. I proposed to replace the email address with Ignoring the common ending, the chance of randomly discovering the first email address is 1 in 1,133,827,315,385,150,000,000,000 (2617 or 1.13 septillion), which means that you have a better chance of winning the super-lotto multiple times. With those odds it would make a better password than it does a customer service email address. The chance of randomly discovering the email address that I suggested is 1 in 456,976 (264), which seems much more sane.

As I thought about the problem it occurred to me that the chances of randomly discovering the email address that I suggested is probably better than stated above since it is a word that English speaking people already know (and readily associate with what they are looking). As far as I can tell there are less than 250,000 words in the English language, which nearly doubles the chances of discovering This idea made me think about string guessing algorithms and the assumptions that are made when evaluating them, specifically algorithms designed to guess passwords.

JavaScript Dynamic Programming Example

Despite its name, many programmers have never heard of dynamic programming. In all fairness, it is not really programming in that sense of the word, rather it is a mathematical method for dividing problems into smaller subproblems and then combing those parts to form an optimal solution. The “programming” portion of “dynamic programming” probably shares more in common with “television programming,” since they both involve using tables to organize data. The technique is taught in advanced computer science classes, so computer scientists and software engineers should be familiar with the technique.

Dynamic programming is a general technique which involves four basic steps: determine the structure of an optimal solution; recursively define values of the optimal solution; compute the optimal solution; and, if you need to know the optimal path in addition to the computed optimal solution value, construct the value formed by the path. The code on this page shows all of these parts, so it may help in understanding the technique.

1936 Akron Rubber Strike

The world has recently experienced an economic depression the likes of which have not been seen since the Great Depression. World leaders have been struggling for over three years to keep this economic calamity from destroying social institutions and precipitating war as the last one did. Of the tools and techniques that were used in the 1930s to restore American economic prosperity there is one that has been neglected. Not only has this tool remained unused during the current depression, but it has been actively attacked. That tool is organized labor.

Like other labor movements, the American labor movement began to appear with the onset of industrialization. In its early years American labor was weak, decentralized, and probably not classifiable as a movement. It was not until the Great Depression that unionization gained the institutional acceptance that it needed to truly become a movement. However, as Americans learned with the “Nobel Experiment” of Prohibition, laws and institutional changes cannot alter society without the acceptance of the people. The 1936 Akron Rubber Strike marks the moment when the ideas of policy makers met the hands of labor and the American labor movement began its ascent.

It can be demonstrated that the 1936 Akron Rubber Strike was a pivotal event by examining the changed attitude of Goodyear’s management team. Prior to the rubber strike Goodyear felt that it had the upper hand, while afterwards management’s tone was much more conciliatory. The chronology of events will establish that this change in attitude was caused by the workers themselves and not simply foisted upon the company and its employees by “professional strike leaders” as Goodyear’s president at the time asserted.1

Calories in Christmas Ale for 2011

There are approximately 278 calories in each 12 fluid ounces of Great Lakes Christmas Ale this year, if my math is correct. Below are my calculations, if you would like to know how I came to this answer. To calculate the number on your own: grab a hydrometer, calculate the final gravity, plug your findings into the equations below, and let me know if I did it right!

First we need to find the original gravity:

Alcohol(by weight) = 76.08(OG-FG)/(1.775-OG)
7.5 = 76.08(x - 1.012) / (1.775 - x)
7.5(1.775 - x) = 76.08(x - 1.012)
13.3125 - 7.5x = 76.08x - 76.99
90.3025 = 83.58x
x = 1.080
OG = 1.080

Now, for the calories calculation:

C = 851(1.080 - 1)(1.080 + 3)
C = 851 * 0.080 * 4.080
C = 277.77

Historical Values:

Where Have All the Capitalists Gone?

Where Have All the Capitalists Gone?

I have been reading through primary sources at the University of Akron’s Archive for a research paper that I am writing, and I have come across some interesting documents. Below is an essay written in 1937 for the Chamber of Commerce by the CEO of Goodyear, Paul Litchfield. Based upon his latter writings, such as this one, he has what contemporary business people might consider to be an outright liberal attitude. It is likely that his views were shaped by the post-depression unionism movement as well as the rise of communism and fascism.

In the first four sections he discusses the labor laws and customs of Great Brittan, Canada, Australia, and the US (specifically with rail roads). The transcription begins at section five. The emphasis is mine.

Steve Jobs

I am not the type of person who is normally enthralled with famous people whom I do not know, but I am truly saddened by the passing of Steve Jobs. It could just be that I am huge fan of his company’s products, after all some of those products led me to where I am today. The first computer I used was an Apple IIe (for playing the Oregon Trail), and HyperCard on the Macintosh is what sparked my interest in computer programming. Of course I know that Steve Jobs could not have create these products without teams of intelligent and dedicated individuals, but based upon the history of Apple it seems that Steve provided the environment which allowed these people to excel.

k-D Tree Nearest Neighbor Search

Yesterday I posted a simple demonstration of the kD tree data structure, today I am posting an animation of the nearest neighbor search algorithm for it. The tree itself should be very straightforward for any one familiar with trees; the nearest neighbor search is where things get a little tricky. I looked up the nearest neighbor algorithm on Wikipedia and was not entirely clear how it worked. I suspect that most people would not understand the description there unless they already understood the algorithm, which is probably why you are here. So, I created an animation that hopefully makes things easier to understand.

k-D Tree

For my current algorithms class I am working on a program that demonstrates the power of k-D trees, but before I implement any new data structure or algorithm I have to completely understand how it works. So, I created an animation that shows how a k-D tree is constructed. Later I will create an animation explaining the nearest neighbor search of a k-D tree.