The Happiness at work Matrix - 4Ps

For me there are four important factors that decide if the  time  I spent at work was worthwhile or not .They are what I call the 4Ps -

• People - This is the most important factor for me.I really like being with people who are smarter than me(oh which is not that hard to find) , people who I respect and  and people who are fun to work with.

• Problem - This is the problem you are trying to solve at work, which is the second most important thing for me.This is how excited are you to work on the problem, it doesn't have to be rocket science to be fun, for example on my first project creating a web page was like an amazing experience.

• Power - This is the third most important thing.This is the amount of influence you have at the place you work, how much people listen to your opinions and how important they think you are to the project.I think this directly is related to how you are "growing" at work, the higher your power the faster you are growing

• PayCheck -The obvious one, how much you make

So you  can draw a little matrix with years as the Y axis and the 4Ps on the X and mark it Blue if that P was good for you for that year, Orange for medium and Red for bad.It should give you a good perspective of how your years went by.Here is mine.Just because I have so many blues for the Pay Check  does not mean I am like the best paid guy around - everything is your perspective of things so all it means when a blue is there is that I "thought" I was doing good on that P

Closures

I keep hearing people talking about Closures but it always seemed hard to grasp it by just a cursory look at the material.For the uninitiated Wikipedia's definition is hard to grasp

What is a closure? In computer science, a closure is a first-class function with free variables that are bound in the lexical environment.

Oh what is a first-class function?A programming language is said to support first-class functions (or function types or function literals) if it treats functions as first-class objects. Specifically, this means that the language supports constructing new functions during the execution of a program, storing them in data structures, passing them as arguments to other functions, and returning them as the values of other functions. This concept doesn't cover any means external to the language and program (meta programming), such as invoking a compiler or an eval function to create a new function.

Now what the heck is a free variable?In computer programming, a free variable is a variable referred to in a function that is not a local variable or an argument of that function[1].


And what do you mean bound? In programming languages, name binding is the association of values with identifiers[1]. An identifier bound to a value is said to reference that value.

Oh finally what is a lexical environment?In computer programming, lexical environment or scope is an enclosing context where values and expressions are associated

Kinda still hard to get if we don't know the formal terminology used

But from what I got and crudely put, Closure is the ability to be able to pass  a piece of "executable code" around and then the executable code when being executed will have access to the same set of variables as available to the place from where you are passing it .Here is a simple example in Ruby

def foo
        local_variable ="foo variable";   
       f = Proc.new { puts "local variable ="+local_variable}
       bar(f)     
 end

def bar(f)
      local_variable ="bar variable";   
      f.call
end

foo

This is going to print "local variable =foo variable" , so I was able to pass the { puts "local variable ="+local_variable} code around and wherever I executed it had access to the same variables as from where it was called i.e. foo

MIT OCW -Lecture 7(Hashing and Hash Functions)

Today morning I took the 7th Lecture which covered Hashing and Hash Functions.This was not as math intensive as the previous few lectures and was more intuition based( if there is such a thing - but basically what I mean is you could kinda see why things were good or bad without even having to do the Math).Here is what was covered

• Symbol table problem that is encountered in Compilers, Operations on the Symbol table i.e. insertion,deletion and search
• Direct Access table - Just an array where you use the key to index into the array to find the value
• What is "Hashing"?
• How to resolve collisions by chaining
• Runtime analysis for hashing with resolving collisions by chaining - worst case is Theta(n) and average case is Theta(1+ alpha), where alpha is the load factor(i.e. n/m ,n=number of elements in the Set and m is the number of slots in the Hash Table)
• How to choose a Hash function? - Should distribute keys uniformly and regularity of keys (for example all keys are even numbers) should not affect the uniformity
• Hash Function using Division Method => h(k) = k Mod m , don't pick m to have a small divisor for example 2 or don't pick m as a power of 2, typically pick a prime which  is not too close to power or 2 or 10
• Hash Function using Multiplication Method => h(k)= (A.k mod 2**w).right.shift(w -r) where A is an odd integer between 2**(w-1) and 2**w  and not too close to the bounds, 2**r = m and w is the word length in bits of the computer.
• The above method is fast since multiplication and right shifting are typically faster on a computer than division
• Resolving collisions through open addressing i.e. when you don't have storage for pointers for doing resolving using linking. - you basically keep probing with a different hash function each time you don't find an empty slot or the search key you are looking for
  
• Linear Probing Strategy => h(k,i) = (h(k,0) + i) mod m. This method suffers from primarly clustering i.e. basically we are search the Hash Table linearly one after the another, so if we have a block of 10 occupied slots in one stretch, everytime you have to check those 10 slots before moving on to the next empty slot
• Double Hashing Strategy => h(k,i) = (h1(k) + i*h2(k))mod m, typically you pick m as a power of 2 and h2(k) is odd for uniform distribution
• Analysis of runtime for Open Addressing => Expected number of probes <=  1/(1-alpha) where alpha is the load factor.The lecture proves the above theorem
  

Network Programming in C - Beej's guide summary(Part 1)

So to brush up my C skills, I thought of doing some C programming and Network programming was something I was always curious about so what better way then do network programming in C.I haven't gotten to the programming part yet.So far I have just completed about half of Beej's guide to Network Programming
And since I have fallen into this good (or bad? who knows) habit of taking notes, here is what I have covered so far from the tutorial

• What is a socket?
• Difference between Stream Sockets and Datagram Sockets (SOCK_STREAM and SOCK_DGRAM)
• Stream sockets use Transmission Control Protocol and Datagram Sockets use User Datagram protocol
• Streams sockets have a connection open during transmissioin and have all the good stuff of ensuring the packets reach other end in same order etc whereas datagram sockets don't ensure any of that, the reason to use UDP over TCP is speed and speed
• Layers of Network stack and why it is layered (very brief)
• why ipv6? Because we were running out of address in ipv4 - ipv4 is 32 bits for each address, ipv6 is 128 bits
• Representation of ipv4 address e.g. 192.0.2.111 and ipv6 address e.g. 2001:0db8:c9d2:0012:0000:0000:0000:0051 , you can actually ignore zeros and represent it as 2001:db8:c9d2:12::51
• Loopback ipv6 address is ::1 and ipv4 is 127.0.0.1
• What is a subnet and how it is represented?
• What are port numbers?
• byte orders - big endian and little endian and the need to convert from network byte order to host byte order and vice versa during receiving and sending packets
• Explains Structs - addrinfo, sockaddr,sockaddr_in, in_addr, sockaddr_in6, in6_addr,sockaddr_storage
• Explains - inet_pton() function which converts String representation of ip address (e.g. 172.78.89.1) to in_addr struct and inet_ntop() for vice versa conversion
• Private networks and Network Address Translation(NAT) - for example when you are connected via a router to the internet from home , your ip addres via ipconfig is different than what your ip address is on this site http://www.whatismyip.com/.Also in theory there can be so many addresses with ipv6 that NAT won't be needed

MIT OCW -Lecture 6(Order Statistics, Median)

I took this Lecture 6 on Sunday.This is what was covered

• What is order statistic i.e. finding the k-th smallest element in an array
• Naive Algorithm for doing it i.e. sorting the array and returning the k-th element from it Theta( nlg(n))
• Algorithm using randomized divide and conquer (basically using quicksort's random partitioning method)
• Intuitive analysis on running time of randomized partition for finding the order statistic i.e. All cases when we split the array into any ratio other than (0:n-1) = Theta(n) and only worst case when we always pick a pivot such that the array is split (0:n-1) = Theta (n**2)
• Formal analysis of running time using Indicative Random variables and substitution method of the above algorithm
• To overcome the worst case of the above algorithm , another algorithm by Rivest, Floyd,Pratt et al was covered 
• The above algorithm basically involves splitting the input array into n/5 groups, finding the median of each n/5 group and then recursively finding the median of these medians.
• The above algorithm was covered at a high level and proof provided on why it would always be Theta(n) run time, but the important part is that the constant C is so high that this may not be a practical algorithm .
  

Other than the above lecture, I also cleaned up this blog a little but changing the URL and the Blog Template,editing a few blogs entries with no title etc..While in the cleaning up mood, I also cleaned up my home directory to group all logically related projects/files into one parent folder.Then I was playing around with C a little and I think I got back 80% of the C I knew 8 years back, pointer arithmetic funness is something I probably need to spend a little more time to get it back.

MIT OCW - Lecture 5(Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort)

Today morning I took the 5th Lecture which talked about decision trees and linear sorting algorithms.Specifically it covered

• Started by reviewing how fast were the already covered sorting algorithms i.e. Merge,Insertion,Quick and Heap Sort(which is not covered in the lectures but wikipedia has good information on it )
• Discussed what is a computation model
• Comparison sorting model - All sorts which use comparison operators for sorting
• What is a decision tree model
  
• How we can represent sorting algorithms based on comparison in decision tree model
• Proof using decision tree model that all comparison sorts have a lower bound of at least n*lg(n).
  
• Merge sort, Heap Sort and Randomized QuickSort are asymptotically optimal comparison model sorting algorithms
• Counting Sort for sorting in linear time - O(n+k) where n is input size and k is the number of distinct elements in the input
• limitations of Counting sort i.e k needs to be fairly small else it will need very large storage space for keeping the counter array
• What is a Stable sorting algorithm - keeps the relative position of equal elements in output same as in input array
• Radix sort
  
• Run time analysis of Radix sort and also how to optimally break the input integer into digits i.e O(n) and r =lg(n)
  

Then I got a little bored of all the theory so went ahead and installed Go. Go is using Mercurial for version control.I have used CVS, use ClearCase now in work life, use Git for GitHub (still know just the basics) and hopefully I will get to a point with Go where I can compare Mercurial with other version control systems.Always fun to compare different designs for the same problem.

I have been too long in the Object Oriented Java world that I am yet to digest the Cish type of syntax of Go and unfortunately all it's speed is lost on my computer because I run Ubuntu on VMWare and that is sloooooooooooow.

MIT OCW - Lecture 4 (Quicksort and Randomized Algorithms)

I completed the 4th Lecture today morning which was on QuickSort and Randomizing QuickSort.Here is what was covered

• How Quick sort fits into Divide and Conquer paradigm
• QuickSort pseudo code and algorithm explanation
• Time analysis of partition method i.e. Theta(n)
• Worst case time analysis of QuickSort i.e. when input is sorted or reverse sorted (Theta (n**2)h
• Best case time analysis of QuickSort when we the pivot always splits the array into two equal halves( Theta(nlg(n))
• Analysis for Average Case time of QuickSort when Pivot splits the array 1/10:9/10 (Theta(nlg(n))
• Time analysis of QuickSort when we alternate between best case and worst case for each recursive partition (Theta(nlg(n))
• Randomized Quicksort - How to overcome worst case by randomly picking a pivot so that the running time is independent of the input array order
• Time analysis of Randomized QuickSort (Theta(nlg(n))
  

This lecture expects a background in basics of probability and random variables(the proof for time analysis of Randomized quick sort uses Indicator random variables)

All in all QuickSort is one of the best practical algorithms available for sorting, of course it may needed to be tuned a little on a case by case basis e.g. if you expect sorted inputs at times, use randomized quick sorts, if the partition array size is say less than 5 elements use some other algorithm to sort it instead of recursively going all the way to one element to partition etc.

Here is a basic implementation of QuickSort in Java