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.

T61 RIAA SoundMax

So today I spent a good 4 hours of time trying to record what my speakers play on my Lenovo T61.Looks like recording right off the sound mixer was kind of a standard feature in sound cards even as back as in 2002.On windows XP if you go to Volume Control Applet -> Options ->Properties and then select the Recording radio button and if your sound card/driver support the record what you listen feature, you will see more than just the microphone in the white box below the radio button

Unfortunately looks like on T61 ,Lenovo deliberately prevents "record what you hear" feature from the sound card at a hardware level.So even if you upgrade to the latest version of SoundMax driver it won't help

Here are a few forum posts I found

http://forums.lenovo.com/t5/General-Discussion/Why-has-stereo-Mix-been-disabled-on-thinkpads-amp-when-do-we-get/m-p/38690

http://forum.thinkpads.com/viewtopic.php?t=52527

People think it is probably Recording Industry Association of America(RIAA) to blame.

But if you really want to overcome the hardware restriction you can go for a combination of audacity and Virtual Audio Cable. Worked pretty slick for me, audacity is open source and free whereas VAC is 30 $ per License.They have a trial version too but it keeps saying the word "Trial" every 30 seconds in your audio output.

T61 Bug

My office T61 Lenovo runs Win XP Pro.When I shut the lid of my laptop it automatically hibernates and when I bring that lid back up it automatically wakes up.But the problem is every time the laptop wakes up like this there is no sound and I had to restart all over again

Apparently it is a bug and there are a couple of ways to fix it. 1) Disable/Enable your sound device 2)Uncheck “allow this device to bring the computer out of standby” from the Power Management properties of your software modem 3)If you don't use your software modem at all just disable it.

All I got from http://www.paralaptop.com/lenovo-laptops/fix-sound-bux-on-thinkpad-t61-after-standby.html but just blogged it on my own blog in case I forget this 6 months from now and start looking for it all over again.

The link never explained what exactly the bug was but made it sound it was some sort of a hardware conflict.I did not find any other material about it on the inter tubes.

A couple of useful google map mashups

http://www.propertymaps.com/maps/polylines.php - You give the zip code and it shows the county and also some information (select zip in the return drop down ) about the county for example average income in that county, average house value etc etc.

http://maps.huge.info/zip.htm - This one is really useful.If you are planning a road trip and want to halt somewhere en route.Google maps gives you the route and the map but with this mashup you can get the zip codes along the route as well which will help you in finding hotels easily.