Let’s talk CLOUD COMPUTING

Cloud Computing, what’s the big deal? I heard someone saying that data is actually stored on cloud and could get wet due to rain water… lol Well yes could be… :P

Storing you data in a location outside your organization, where servers are actually present somewhere you don’t really know is cloud. Someone could make the definition even better for me. To actually understand the concept of what is new in cloud, one needs to understand, how things were before cloud came into existence (cloud was always their in existence, its just that the term was coined later).

Traditionally, companies had their own data servers or data centers to maintain or keep their data safe. Incase they had multiple centers they had distributed systems to maintain and use data, but the concept remains the same that each company took care of its own data through its own data centers. Incase they wanted to access this data at the same location or at different location they could do it through network. Basically, they kept their own data with themselves handled it or maintained it all by themselves.

So what’s the problem with it? Well in a way no problem. But if we understand cloud computing we will get what it helps in. Sometimes you get so used to a problem, that you don’t really think if it’s a problem. Now suppose for an X company the data servers were present in such a location with an illusion of being stored in a centralized manner, so that the company and all its centers can connect and access data from it whenever and wherever they want without worrying about the existence and maintenance of data how better it would be. Well sounds much like distributed databases except for the data is distributed throughout, what’s the difference? What if your organization is not supposed to worry about all of this hassle and handled it all to some third organization for maintaining? Sounds cool, but how does it help? X company works in a domain that has nothing to do with software. E.g X is a telecom company, all they worry about is if communication is perfect between their customers. But if X also has to maintain and keep up the database of all the communications like files sent and received from one customer to another, and this happening for a millions of customers. X will have to have a separate department that handle database, employ more workers, pay administrators, buy database servers maintain them. Distribute it to various locations. Rather if the job is being handled by a third organization which works itself in database maintenance and storage and is ready to provide the data whenever and wherever in an efficient manner with a little cost which should be surely less then employing more people and buying servers for yourself, why not go for it?

So, is that all? No, but there's more to it and more keeps growing too. This was just an example of what it really could do. Lets elaborate a bit.

Cloud services as mentioned in the earlier example are essentially divided into 3 major services. While these 3 are not the only services, but these services conquer the major part of the cloud. So what are these services:

SAAS : Software as a Service
PAAS : Platform as a Service
IAAS : Infrastructure as a Service

By now with the example stated above you probably might have had a hint of what these services really are all about.

SAAS: Software as a Service is using a Software as a service from the service provider on demand when the software is actually hosted on some cloud servers out there.
But whats the benefit? I would rather install the software on my own PC and use it when i want. Why cloud.
Suppose your work in some industry and you don't necessarily need Microsoft Office all the time. You probably may need it may be once every month or so may be to just view a document and edit it a bit. If you buy MS-Office for this reason and get it installed on your system lets see what all you did for this one year.

1. You bought MS-Office professional for Rs. 24000 as per the latest price stated on Flipkart for 2013 edition.
2. You called someone and paid him to have it installed on you machine since you were not good at installations and stuff.
3. On your machine the installation took around 1 GB or more of your Hard disk drive
4. Whenever you start it it consumes around 60 MB of RAM disk.
5. Whenever in this year you had a problem accessing Office you called up Microsoft service center too get help from customer care and waited for long queues.
6.  Every time Microsoft comes up with an update, you download the new update and install it which consumes more of your internet.
7. If Microsoft decides to stop docx, pptx extensions again as they did with the Old office in their new release. Gosh!!! you buy another office.
8. If system crashes, data done!!

Instead if you were using Office 365 which is Microsoft's cloud based Software as a Service lets see how the above mentioned steps changed.

1. You opened any browser and accessed the URL http://office.microsoft.com/en-in/business/compare-office-365-for-business-plans-FX102918419.aspx paid some amount on per month basis or per year basis as per your need which was 3 times less then what you paid for in a local installation
2. You accessed URL : https://office.live.com/start/Word.aspx?ui=en-US
3. You started working opened closed edited your docs saved it. Done!!!

Thats it?
No installation charges. No space consumed on local drive. No RAM consumed other than the browser RAM. No customer care calls needed as per SLA. No upgrades needed since they will handle it all by them self. If they plan to change the file extension in the next release, it get automatically reflected. Plus Advantages also include, you can access you documents online from anywhere. Your documents are protected with you username passwords. No worries of system crash.

This was just one example of a Saas based service there are surely many more such services existing that you could look for. Now that Saas is clear Paas and Iaas will be easy to understand.

PAAS: Just like in Saas you used office to create docs, In Platform as a service a service provider, provides you with a platform to build apps. Its basically used by the developers to create web applications without worrying about the infrastructure beneath for development purpose. The benefit remains almost the same however the added ones could be that it promotes collaborative development, and comes up with so many tools for development making it easy for developers.

IAAS: Many a times you might have felt the need to have a greater storage space for some reason but did not consider buying a disk for it. Also you might have felt a need to greater CPU or RAM for some performance reason but again, why buy something for a task that wont take more than an hour. Infrastructure as a service is a way to provide you with Hardware Infrastructure over the cloud. Its been heavily used by most of the companies and users. Storage, CPU and Memory are not the only things that Iaas is limited to. There's more to it for sure. Nowadays different options are provided by different service providers only to make the world a better place to live in.

Most of these services are free to use or at least free to try. Before making a mind, if or not to purchase it. We could surely try them out.
Some well known cloud services/providers

SAAS : Facebook, Gmail
PAAS : Googel App Engine, Heroku
IAAS : Amazon, Rackspace

Corruption

A king once announced in his kingdom, "Anyone who gets him  something that is really unique, which no one in this world has will be rewarded, but if its not unique, he will be hanged" A tailor came forward and gifted him an air jacket. He said that the jacket was invisible and was made up of air. The king proudly got up wore nothing but the jacket and proudly went on a ride in the kingdom. No one else, but a 12 year old kid came forward laughing out of his innocence and honesty saying "O king!! You are wearing absolutely nothing and are roaming naked giving your kingdom a full view of yourself." This is the end of the story. Don’t really know what happened with the kid, but pretty sure he dint live thereafter!!! Hope everyone got the right message….

ACM ICPC 2011 (2)

Some rights reserved by Kiewic

Onsite Competition Registration

Once you are selected for the regionals, the college is supposed to pay a registration fees of Rs. 3500/- which is for 5 people 3 contestants one reserve and a coach. This fees includes the accommodation and food for 5 days. The fees is to be sent by DD. After having a terrible experience with the Online registration I dint take a risk of being late for the Onsite one. I sent the amount as soon as possible. The money was paid by College. Registration was accepted. We were supposed to fill online registration forms for travel and accommodation. ICPC this time also took care about those students travel expenses, for those whose colleges could not sponsor it (Our college did it for us... ;)). You can even get guests to the venue subject to availability of accommodation and at their own expenses. As i mentioned earlier, we could not register a reserve due to technical problems. We registered him as a guest. So 4 of us. Me, Shreyas Damle, Rahul Dange and Gaurav Deochakke. were all set for the Onsite Contest. Our coach couldn't come for she had work in college.

Railway Reservation

Had a tough time with this one. I already knew it since i did Google a few blogs which did mention how previous year students had problems with it. Well, so did we. We booked Kanyakumari express, waiting ticket  and 2 nights and 3 day travel. We obviously didn't wanted this. We checked again for other trains from Mumbai and found Kerala Kranti Express from Panvel to Kollam 18 rs travel and seats available. Cancelled the previous tickets booked Kerala Kranti ticket for 8th December and mailed ICPC that we will be coming a day earlier cos of unavailability of proper reservations. Not to risk the return journey booked a return ticket as well. Netravati Express for 15th December Kollam to Panvel. 

Train Journey

The best journey i ever had. Thankfully all the passengers in our berth were cooperative and talkative too (or i guess we were too social... :P ) Made friends with almost all of them. One was a teacher in Kollam and one of them was sitting with his Mom was working in Punjab, and one was a student just like us. Clicked pics with all of them throughout the journey. Got down from the train at every signal at every station, bought everything at every station. Pretty sure people admired our appetites...:P

When train reached Kerela, we were not sure if were supposed to be picked up cause we were a day earlier than expected. Called up the Technical Director of ICPC (which we were not knowing earlier, else would have never dared to do so, for such a cheap reason). A very polite sounding gentleman recieved the call and ensured that a team will be recieving us on Kayankullam Junction. Kayankullam was one station before Kollam. Thereafter got numerous calls from ICPC volunteers to check as to where the train had reached. The volunteers were standing outside the station main gate in orange ICPC T-Shirts as they had already informed us over the phone. They welcomed us. Happy lot of crowd I must say. Although I feel sorry cause I forgot their names. They took us to their Hostel.

Introduction to algorithms by MIT

Lecture 1

This blog is an extract from MIT's Introduction to Algorithm course.

First part of the course ids focused on Analysis. Second part is focused on design i.e. before u design algorithms; you have to master and analyze a bunch of algorithms. Analysis is a theoretical study of a computer program performance and resource usage.

How to make fast and memory reliable programs?

What is more important than performance?

1.        correctness

2.        simplicity

3.        maintainability

4.        cost(programmer’s time)

5.        stability(robustness)

6.        features(functionality)

7.        modularity(changes implementation easy)

8.        security

9.        scalability

10.     user friendliness

Then, why study algorithm and performance?

Some times performance is correlated to user friendliness. Some times there are real time constraints. i.e. the software wont work untilit performs a function for a particular time. Performance measures the line between feasible and infeasible. In real time , if it is not fast enough, its as good as not functional. If it simply uses more memory, its not going to work for you.

Algorithms are at the cutting edge of entrepreneurship. If you are thinking of doing something that already exists, performance isn’t that necessary. But, if you are planning to do something’s that’s never done before, than its most important.

The reason why performance is at the bottom of the heap is because performance is just like money. What good is a $100 bill for you? Instead you would want to have food worth $100, that should be of some use to you. Performance is something you pay for. E.g you pay for user friendliness, you pay for security, etc.

So for this reason, a user may gor for JAVA instead of C for it may be slow, but it gives more functionality like exceptions, Object Orientations,etc.

PROBLEM: INSERTION SORT

Input: sequence <a1,a2,a3,….,an>of numbers

Output: permutations<a’1,a’2,a’3,…..,a’n>

Such that a’1 <= a’2 <= a’3 <= ….. <= a’n

Pseudo code:

Insertion_Sort(A,n) //Sorts A[1….n]

for j = 2 to n

                do key = A[j]

                                i = j-1

                while i>0 and A[i]>key

                                do A[i+1] = A[i]

                                                i=i-1

                A[i+1]=key

Figure 1

                   

                It basically takes array A[] and at any point we are running the outer loop of j from 2 to n and the inner loop that starts with i = j-1 and goes until i = 0 .  so we are looking at some element j in the algorithm, and then we pull out here a value called a key and the important thing to note is that there is an invariant that is being maintained by the loop each time through. The invariant is that the LEFT part of the array in the above figure 1 is sorted. And the goal each time through the loop is to add one to the length of the strings that are sorted. And the way we do that is we pull out the key, and we just copy the value up like the arrows shown until we find a place for the key shown and then INSERT it in that place, hence the name INSERTION SORT. Once we have arrays till j sorted we go for j+1. now let us see an example for the same.

Example

8 2 4 9 3

2 8 4 9 3

2 4 8 9 3

2 4 8 9 3

2 3 4 8 9 sorted

Analysis of this algorithm

Running time:

1. Depends on input. (e.g if already sorted, insertion sort has very little to do, cos every time we try to sort it would be like the step number 3 above where 9 is already sorted and was at its correct position so you don’t need to move it. Worst case is if its reverse sorted then there will be a lot of work to do, lot of shuffling to do as well.
2. Depends on the input size. (6 elements less time 10 elements more time) so large number of elements means long time for sorting. So we handle it by:

-          parameterize things in the input size.

3. generally we want upper bound on running time i.e we want to know that the time is no more than  a certain amount reason being that represents a guarantee to the user. E.g if I tell you that there’s  aprogram that wont run more than 3 seconds, that gives you real information about how you could use it for example in a real time setting. And if I say there’s a program that goes for at least 3 seconds, it could go for years. That doesn’t give you a guarantee if you are a user.

- guarantee to the user.

Different kinds of analysis :

Worst case analysis: this is done usually

Where T(n) = maximum time on any input of size n

So as we saw running time depends on input that some times the inputs are better like in sort if already sorted less time and if reverse sorted maximum time. So we are looking at the worst case. If T(n) is not for maximum time then T(n) is a relation and not a function, because the time on input size n will depend on which input of size n, I can have many different times. But by putting a maximum at it, turns that relation into a function, cos there’s only one maximum time.

Average case analysis: this is done sometimes.

Where T(n) = expected time over all inputs of size n

What is expected time? Time of every input and average them? Time of every input times of probability that it will be there that it would occur. How do we know the probability time of every input occurs is?

Well we don’t know it.

So we need an assumption of statistical distribution of inputs. Common assumption is that all inputs are equally likely that’s called uniform distribution.

Best case analysis: bogus

Because its already done. You can cheat, it doesn’t tell u of the vast majority cases.

What is insertion sort’s worst case time?

Depends on computer you are running on.

-          Compare two algorithm for Relative speed (on same machine)

-          Absolute speed (if onde algorithm is betr than the other no matter what machine it runs on.

Asymptotic analysis: ignore machine dependent constants and look at growth of running time T(n) as n -> ∞

Asymptotic notations

(Theta notation) q - notation:

Drop low order terms and ignore leading constants

e.g if there is a formula 3n^3+90n^2-5n+6046= q(n^3)

here n^3 is a bigger term than n^2 , n and all the leading terms thus it becomes q(n^3)

as n -> ∞ , q(n^2) algorithm always beats a q(n^3) algorithm.

n^2 will be faster than n^3

There will always be a point n0 where q(n^2) algorithm will be cheaper than q(n^3) algorithm

Insertion sort analysis

Worst case: input reverse sorted biggest element comes 1^st and smallest comes last.

T(n)= S ^j=2 to _n q(j) = q(n^2) (arithmetic series)

Is insertion sort fast? Moderately fast for small n but not for large n. Merge sort is faster instead.

MERGE SORT

Merge sort A[1….N}

1.        If n =1 done

2.         Recursively sort
A[1….[n/2]] and
A[[n/2]+1….n]

3.        Merge 2 sorted lists

Key subroutine here is merge and it works like this one of them is

20 13 7 2

12 11 9 1

We look at the two sorted arrays and see where is the smallest element and now we find 1 and two are smallest so we now look for the smallest of them and place the smallest in the new list so 1 is placed in new list. Now we compare the 1^st element of first list and 2^nd element from second list, similarly

Time = q(n) on n total elements

Recurrence for the program

q(1)

2T(n/2)

q(n)

Performance of merge sort T(n) = q(1) if n=1 (omit usually),2T(n/2)+ q(n) if n>1

Recursion tree T(n)=2T(n/2)+cn const c>0

T(n) = cn - > T(n/2) 2 times