Internal Energy of an Ideal Gas

Was originally planning on taking a brain dump and proving the ideal gas law P V = n R T. Realized that I didn’t have enough board space to get to the Maxwell-Boltzmann distribution, so I just ended the derivation at the internal energy of an ideal gas.

2013-03-07 14.04.50

Pretty neat how statistical mechanics bridges the gap between the quantum world of discrete energy eigenstates and the macroscopic thermodynamic world.

Linear coefficient for number of compares in mergesort

Mergesort is a divide and conquer sorting algorithm which can be implemented to be in place and stable. It can be shown that the number of compares in mergesort for a dataset of size N is ~(NlgN + cN) for some constant c.

I couldn’t sleep and playing with web SVG graphics sounded like fun, and who doesn’t like a little bit of algo-geekout… ;) .

So I tried simulating mergesort and counting compares, then figuring out what value for c would be required to make the recurrence hold at that point. I tried this for multiple mergesort partition schemes, ranging from the archetypeal 2 partitions up to 4. The magnitudes were drastically different, so the results are normalized to better illustrate the behavior of the c value. Check it out:

Oooh, fancy HTML5 scriptable SVG graphics. Link to the library is below.

Anyways… Clearly the linear coefficient is not constant. Rather, it appears to be oscillatory in nature. A special kind of oscillatory that is; the telltale dependence of the Nth peak’s magnitude on the N-1th peak’s gives away the combinatoric nature of this relationship. Cool huh? Makes me feel like I’m getting at some deep math with basic programming. Code:

#!/usr/bin/python

import sys
import math
import pygal
from pygal.style import LightStyle

def main():
    if len(sys.argv) < 2:
        print "Usage: python MergeLinearTerm.py maxN"
        sys.exit()
    maxN = int(sys.argv[1])

    results = []
    for merge_N in range(2, 6):
        results.append(simulate_N_merge(merge_N, maxN))

    # Normalization
    for i, res in enumerate(results):
        norm_factor = max(res)
        results[i] = map(lambda x: x / norm_factor, res)

    # Decrease resolution
    downsample_factor = 15
    for i, res in enumerate(results):
        results[i] = [res[j] for j in range(0, len(res), downsample_factor)]

    chart = pygal.StackedLine(fill=True, style=LightStyle, human_readable=True,
                              legend_at_bottom=True)
    chart.title = "Normalized linear coeff c, # compares in mergesort (~NlgN\
        + cN)"
    chart.x_labels = map(str, range(0, (maxN / len(results[0]) *
                         len(results[0])), maxN / len(results[0])))
    for merge_N in range(len(results)):
        chart.add(str(merge_N + 2) + " partitions", results[merge_N])
    chart.render_to_file('MergeLinearTerm.svg')

def simulate_N_merge(merge_N, maxN):
    c = [0 for i in range(maxN + 1)]
    for N in range(1, len(c)):
        c[N] = N + c[N / merge_N] + c[N - (N / merge_N)]
    # convert to what c should be for this point
    for N in range(1, len(c)):
        c[N] -= N * math.log(N) / math.log(merge_N) + N
    return c

if __name__ == "__main__":
    main()

Anyways, lets get to bed before 9am ENGS x-hour.

http://pygal.org/ - Python SVG Plotting Libraries

http://aofa.cs.princeton.edu/20recurrence/ - Analysis of mergesort recursion

Fourier Expansion Demo

I’m dying in my Fourier analysis class… Perhaps you’ll enjoy some of the fruits of my labor.

Understanding Ruby’s Select, Map, and Reduce

When you call Array#each, what you actually get back is an Enumerator object. This object is simply something which implements the Enumerable mix in and defines an Object#each instance method which (by convention should) yield objects to another code block. With these requirements in place, the Enumerator provides a set of very powerful methods. I will be covering three of them: select, map, and reduce.

For demonstration purposes, I will be using an array (which implements an “each” method, returning an Enumerator object). In this example, we have an array of colors:

rainbow = ['red', 'orange', 'yellow', 'green', 'blue', 'purple']
# ['red', 'orange', 'yellow', 'green', 'blue', 'purple']

In terms of the Array class, Array#each simply yields each item from the array starting at the first element and ending on the last element.

Select

Select is a method built on top of each which enables quick and easy list filtering. Some examples may help illustrate this:

# any color with 5 or more letters
rainbow.select {|color| color.size >= 5}
# ['orange', 'yellow', 'green', 'purple']

# any color containing g
rainbow.select {|color| color.include?('g')}
# ['orange', 'green']

# regular expression matching any letter repeated more than once
rainbow.select {|color| color =~ /(\w)\1+/}
# ['yellow', 'green']

Select uses Array#each to enumerate the array, running the test that you specify in the code block against each element. If it returns true, then select copies that into another array which is returned. Just like how most methods have dangerous banged (Class#method!) versions which modify the object it’s called on, so does each:

# destructive select method
rainbow.select! {|color| color.include?('g')}
# ['orange', 'green']

# original rainbow array has been modified!
rainbow
# ['orange', 'green']

Map

Map may be familiar to people coming from a functional programming background. To fully understand it, you need to know that in Ruby methods are first-class citizens (atoms). Just like how you can pass an integer as a method argument, Ruby places no restriction on passing functions in as well; there are no complaints so long as the resulting code makes sense. In functional languages (and Ruby), map is a method which takes a method and an enumerable as arguments and applies the method to each item of the enumerable.

While other languages (Python, Scheme) have syntax which follow the style discussed above, Ruby’s code blocks allow map to be viewed as another method built on top of each. Some examples:

rainbow = ['red', 'orange', 'yellow', 'green', 'blue', 'purple']
# ['red', 'orange', 'yellow', 'green', 'blue', 'purple']

# all the words capitalized
rainbow.map {|color| color.upcase}
# ['RED', 'ORANGE', 'YELLOW', 'GREEN', 'BLUE', 'PURPLE']

# all the words reversed
rainbow.map {|color| color.reverse}
# ['der', 'egnaro', 'wolley', 'neerg', 'eulb', 'elprup']

# length of all the words
rainbow.map {|color| color.size}
# [3, 6, 6, 5, 4, 6]

In each case, map takes a code block and applies it to each individual element of the array, returning a new array with the method specified in the code block applied to each element.

Inject/Reduce

Array#inject and Array#reduce are the same function with two different names. In a way, reduce is the kingpin of all the other Enumerator methods seen above. Rather than forcing you to return a filtered enumeration (select) or a transformed enumeration (map), reduce allows you to directly craft the object being returned (commonly called an accumulator because it accumulates the results as you enumerate the collection). Some examples:

# number of colors
rainbow.reduce(0) {|acc, n| acc += 1}
# 6

# number of characters in all colors of rainbow
rainbow.reduce(0) {|acc, n| acc += n.length}
# 30

# defining map with reduce/inject
rainbow.reduce([]) {|acc, n| acc.push(n.upcase)}
# ['RED', 'ORANGE', 'YELLOW', 'GREEN', 'BLUE', 'PURPLE']

Note how in the third example, reduce has done the same thing as map. We could, in fact, never use map and always just use reduce. However, the two different methods provides clarity and self documenting code. Map is typically used when you apply a function across an array, whereas inject is used if you have a specific need for the accumulator. If you consider which one will be more appropriate for what you are trying to do, your code will be clearer and easier to understand for others.

I hope this helps explain some of the essential methods used when programming with enumerators in Ruby!

Design Decisions at Microsoft

Microsoft Corporation - 1978

Microsoft Corporation - 1978 (Photo credit: Brajeshwar)

Prior to this summer, I shared the common sentiment about Microsoft: gigantic, corporate, and ignorant of end users. It wasn’t until I worked for two weeks there did my appreciation for Microsoft grow.

The first two points are true: Microsoft is huge. With revenue close to $70 billion last year and a head count just over 90k, the average Microsoft employee is generating over $750k for the company. For a company that’s only been around for less than half a century, that’s pretty good.

Beyond corporate success, there’s something more subtle that most people glaze over: the customer focus. What? That’s usually the last thing that comes to my mind when I hear Microsoft, the company backing Windows Vista and Internet Explorer.

Almost all of the woes I hear about Microsoft are due to a single factor: scale. Microsoft Office serves 94% of all desktop productivity software, so what may seem like a bug to one may be a feature to another. With the bulk of the revenue coming from enterprise agreements, even the smallest UI change can bring hordes of complaints from droves of end-users.

Microsoft Office Excel 2007

Microsoft Office Excel 2007 (Photo credit: Wikipedia)

To be fair, Microsoft is full of technological freaks. And this demographic does lead to some design choices that may not make sense to end users. For example remember that floating orb in Office 2007? Now, I don’t know your background, but if you’re anything like me (and most of my co-workers), when I see a glowing orb in the corner of the screen, my ADD mouse immediately jumps to it. And that’s what the UX designers wanted; the glowing orb to indicate click me.
Oh how wrong that actually translated in market. Most end users couldn’t care less about testing their software’s capabilities; they just wanted to finish their job without breaking anything. When an orb lights up for no reason, the reaction isn’t click me. Rather, it’s closer to “oh shit, what did I do?”

But to be fair, Microsoft does respond to user feedback. After Clippy became more annoying than helpful, he was promptly executed in Office 2003. After the “freaky” glowing orb, in Office 2010 the “File” menu made it’s appearance again. And currently, with the consumerization of technology, Microsoft Office is undergoing a dramatic paradigm shift as they move from a on-premise model to a service model with Office 365.

Office 365 is extremely exciting. Previous versions of Office required an IT department to deploy and maintain. When e-mail went down, companies called their IT departments. When files were lost, companies blamed their IT departments. Software was primarily sold to corporations,who hired guys to deploy it.
With Office 365, Microsoft becomes your IT department. Through providing software as a service, Microsoft themselves is responsible for the integrity and reliability of the data, security, all that stuff. This is a huge paradigm shift; companies won’t need IT departments anymore. Considered with the growing trend towards cloud computing and mobile access, we can expect some very big things in this very exciting transitionary period.

Stop trading your privacy for cookies

In case you didn’t know, any website that uses any Google products (+1, Analytics, AdSense) or Facebook (“Like”) and many other ad providers set tracking cookies. These cookies basically let these companies know what sites you access so that they can “better target ads” for you.

I don’t trust that (and I’m not paranoid). I’ve seen firsthand how in cyberspace compliance with the Justice department is the same as “what 4th amendment?”

Here’s how to cut the ties and anonymize (I will be using Chrome but the steps should be the same):

1) Settings:

Settings  Basics

 

 

2) Under the hood/Privacy settings/etc

Settings  Under the Hood 2

 

 

 

 

 

 

3) Block all third party cookies

3

This way, only the website you are actually requesting can set cookies. Google, Facebook, etc. are all blocked.

Note that this does not stop tracking through request tracking (when your browser loads the AdSense ads or Facebook “Like” links) nor does it stop Google’s Instant Search tracking. To do that, install an ad-blocker or content remover for your specific browser.