Git ,VMware and Ubuntu!

So I started reading up a little bit on Git today and hopefully soon get a GitHub account.But before that I wanted to set up Ubuntu on the Vmware player which I got done.Now I need to setup Eclipse and Git and all the good stuff on my Ubuntu

Here is a old talk on Git by Linus and also the intro to Git on github.com but the gist I got so far is

• Git Keeps a copy of ALL the files and ALL the versions locally unlike your other version control things like CVS, SVN , ClearCase which keep only the latest version locally
  
• Git is distributed version control System, so it has multiple servers instead of just one centralized server
• In Git each person can have as many branches as they want and work on it.Since merging is easy , you can have like a "main" branch and merge all verified changes into that branch
• This does not mean Git takes a whole lotta space, it is still probably less than what subversion takes to keep just the latest version of the files
• Since Git keeps everything on your disk it is super duper fast
  
• Since Git keeps everything on your disk you can do pretty much everything other than push and pull while you are offline
  
• Branching and Merging is very fast

I would have liked to have atleast completed my Ubuntu setup and Git setup today.But dumb fuckers and dumb fuck processes of corporate IT spoiled my mood a little and then I had a lengthy lengthy argument with the missus which took up a lot of my time :-(

Summary of all the MIT Introduction to Algorithms lectures by Peteris Krumins

Wow somebody has done such an awesome awesome job of summarizing it

Summary of all the MIT Introduction to Algorithms lectures

Today probably will take the MIT's first lecture and see how that compares to the one I am taking

Stack implementation - NPTEL -Lecture 2(Stacks)

Below is the implementation of a simple stack based on the Stacks Lecture. A straight forward implementation in Java which supports both the growth strategy and the tight strategy for increasing the stack size.


Stack - Interface with Stack methods
MyStack - Concrete implementation
StackOverFlowException - Thrown when we run out of memory
StackEmptyException Thrown when the user calls top or pop when Stack is empty
StockSpanAlgorithm This class implements the calculating stock span (javadoc describes what the problem is) using both a trivial implementation (O(n**2)) and using Stacks (O(n))
Utils - Utils class which prints the array contents to the output

I am thinking instead of using pastie to post my code, I am better off using github.Lets see how that goes

NPTEL -Lecture 2(Stacks)

So Day 2 sat through the Stacks Lecture and here are the notes

Stacks

Abstract Data Type - Here is the fancy defintion , ADT is a mathematically specified entity that defines a set of its instances with:

A specific interface - a collection of signatures of operations that can be invoked on an instance
A set of axioms ( preconditions and postconditions) that define the semantics of the operations ( i.e. what the operations do to the instance of ADT, not how)

so in terms of Java ADT is pretty much like a Interface with decent JavaDoc

There are three types of operations
Construction (Constructor in Java)
Access functions ( something like a getter(), list())
Manipulation functions (something like a setter(), put(), add())


Stack
LIFO Datatype

operations on a stack , new - creates it, push - pushes , pop - pops, top - just reads the top most element without removing it, size - gives the size, isEmpty - checks if Empty

Formally axioms will be defined like this for example
Pop(Push(S,v)) = S
Top(Push(S,v)) = v

Stack interface in Java and some basics of Exceptions was covered

Creating an Array based stack in Java and it's implementation was shown


All methods of Stack run at O(1) - so Stack is very efficient

Example of Calculating the Stock Span i.e. If you have an array of daily stock prices , create another array such that for each element in the stock price array you have a corresponding element for the Span of that day. For example let us say the stock prices varied like this {10, 3,1,8,3,2 }, Span is defined as the difference between current day index and the index of the last day when the stock price is greater than the current day , for example Span for the day Stock price was 2 is 1 , for 8 it is 3

1)First approach using loop of loops so order was O(n**2)
2)More efficient Stack approach where order was O(n)


A growable ArrayBased Stack, Everytime the Stack is full you increase the size
1)Tight Strategy - Add the constant to the current max size and create a new Stack -O(n**2/c) where c is the constant
2)Growth Strategy - Double the size of Stack everytime is full - O(n)

So growth Strategy is a better option

Other 3 Lectures on Cluster computing and MapReduce from Google+ NPTEL -Lecture 1(Introduction to Algorithms)

So today I took the last three lectures as well here Google Cluster Computing and Map Reduce.

The third one on distributed file systems talked about Google File System was really good.It was not at all hard to understand and was kind of amazing in the sense that with ideas that are not even that hard to understand , you can actually manage peta bytes of data.Though GFS isn't you general purpose file system but a file system that is optimized to store a few millions of very large files ( the block size is 64 MB!!), optimized for reading large chunks of data in one shot and for appending data at the end of the file.

The other two lectures on Clustering Algorithms and Graph Algorithms was a little hard for me to appreciate because I had no background on it whatsoever.

So I started off by hunting videos on youtube that start with algorithm basics ( I do have a book on the same subject, but watching online lectures seems to be a much better option for me).Guess what I found a gold mine of Lectures from a Professor from Indian Institute of Technology in Delhi , here is the link

I'll try to listen to one lecture everyday and post the class notes here.So today's lecture was on "Introduction to Algorithms" and here are the class notes I took

Data Structures and Algorithms

• What is an Algorithm?
• What is a good Algorithm? - Small Running time and takes less memory

First Sorting Algorithm - Insertion Sort

Analysis of running time - At the very basic level, there are some basic fundamental operations

for example comparison operation(>,<,==), arithmetic operation(+,-,*,/), logical operations( &&, ||).So run time is just the sum of number of times the fundamental operations need to be executed for a given algorithm, multiplied by the time taken for each of these fundamental operations. There is best case times, worst case times and Average case times. Typically you would want to consider the worst case because that is the upper bound.Secondly the average case is typically as bad as the Worst case .Average case is difficult to compute as well Asymptotic Analysis: This method simplifies analysis of running time by getting rid of the implementation specific detail like what hardware, what software etc. Secondly the obvious way to measure the run-time is to implement it and measure the time taken to run the program , but that is hard and not feasible for obvious reasons (because input size can vary all over the place, the run time will vary based on OS Load, hardware etc etc)

Asymptotic Analysis just captures the essence of how the algorithm's running time increases with the increase in the input size Big Oh Notation f(n) = O(g(n)) if there exists constants c and no such that f(n) <= cg(n) for n >= no
for example f(n) = 2n+6 and g(n) = n. and c = 4 and no is 3 .

Big Oh notation is used for worst case analysis

But really outside the fancy definition the simple rule is just Drop the lower order terms and the constants from the function

For example if the run time is a function 50nlog(n), then in Big-Oh notation you would simply represent it as O(nlog(n))

So if you are running a loop within a loop for input size n, your algorithmic efficiency is O(n(outer loop) * n (inner loop)) = O (n*2), if you have a loop within a loop within a loop it is O(n*3) etc

O(log(n)) is better than O(n) is better than O(n2) is better than O(n to the power k) is better than O ( a to the power n)

There is also big Omega(lower bound) and big Theta (tight bound = average case) - but these notations aren't as widely used as Big Oh

dirty basic MapReduce implementation(well not even an implementation)

So just to understand the concept of MapReduce better, I tried to create some Java code which would use the MapReduce 'pattern' to solve the word count problem (i.e counting number of times each unique word occurs in the given set of documents).Of course this has been tested only on a sample of three basic text files ,not error checking whatsoever and was implemented using the the first way that came to mind.

FileKeyValue.java - File name and File value(list of words in the file)
WordKeyValue.java - Word name and word count
MapReducer.java - This does the bulk of the work.

1. It creates a list of FileKeyValue objects for all the input files.
2. Then threads out each FileKeyValue object to be processed in a Mapper.
3. Waits for all the Mappers to finish.
4. Then sorts the output of all the mappers by the outputKey(i.e word) and consolidates the output value from all the Mappers for that output key (i.e. creates the intermediate list).
5. Threads out each unique combination of (outputKey, intermediate list) combination to a Reducer for reduction.
6. Waits for all reducers to complete.
7. Prints out the results

Mapper.java - Breaks the FileKeyValue object into a list of WordKeyValue objects.Each Mapper runs as a separate Thread
Reducer.java - Sums up the intermediate list values for a given word and passes it back to MapReducer class.Each Reducer runs as a separate Thread

Lecture on Cluster Computing and MapReduce from Google

For a while I was curious on what was MapReduce exactly and if even you are curious these lectures from Google will help

http://code.google.com/edu/submissions/mapreduce-minilecture/listing.html

So far I took the first and the second one.Both are approx an hour long.

The first one gives an overview of distributed computing and it's history.

• Difference between parallel computing and distributed computing
• Synchronization primitives and Semaphores
• Condition variables
• Fundamentals of Networking (what is a port, TCP, IP etc)

The second lecture goes into details of Map Reduce

• Overview of Functional Programming
• What is Map and Fold in the context of Functional Programming
• Overview of MapReduce with the example of a word count on a bunch of files Algorithm

I started writing a very basic MapReduce implementation in Java (using regular Threads of course to parallelize the Mappers and Reducers) for the Word Count Algorithm.I have about 50% completed and hopefully will complete it all tomorrow and post the code out here.