Latest From My Blog

Algorithm: Counting Sort

Hey folks, whats up..?

I've reading about algorithms a lot lately. I have this awesome site GeeksforGeeks, they teach all things about computer, such as algorithms, data structures, c, c++ and some of the interview experiences from the people who got selected in the IT Giants like Google, Facebook, Amazon etc..

I was reading about radix sort when encounter a problem with some fraction of the program. So moderator of the site suggested me another algorithm to understand the radixsort. That is counting algorithm. Here are the details.

Counting sort  is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Let us understand it with the help of an example.
For simplicity, consider the data in the range 0 to 9. 
Input data: 1, 4, 1, 2, 7, 5, 2
  1) Take a count array to store the count of each unique object.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) Modify the count array such that each element at each index 
  stores the sum of previous counts. 
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

The modified count array indicates the position of each object in 
the output sequence.
 
  3) Output each object from the input sequence followed by 
  decreasing its count by 1.
  Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
  Put data 1 at index 2 in output. Decrease count by 1 to place 
  next data 1 at an index 1 smaller than this index.
Following is C implementation of counting sort.
// C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255
 
// The main function that sort the given string str in alphabatical order
void countSort(char *str)
{
    // The output character array that will have sorted str
    char output[strlen(str)];
 
    // Create a count array to store count of inidividul characters and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));
 
    // Store count of each character
    for(i = 0; str[i]; ++i)
        ++count[str[i]];
 
    // Change count[i] so that count[i] now contains actual position of
    // this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];
 
    // Build the output character array
    for (i = 0; str[i]; ++i)
    {
        output[count[str[i]]-1] = str[i];
        --count[str[i]];
    }
 
    // Copy the output array to str, so that str now
    // contains sorted characters
    for (i = 0; str[i]; ++i)
        str[i] = output[i];
}
 
// Driver program to test above function
int main()
{
    char str[] = "geeksforgeeks";//"applepp";
 
    countSort(str);
 
    printf("Sorted string is %s\n", str);
    return 0;
}
Output:
Sorted character array is eeeefggkkorss

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
(You might be thinking what is time complexity. Here is the WikiPedia Article on that.)

Auxiliary Space: O(n+k)

Points to be noted:
1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10K and the data is 10, 5, 10K, 5K.
2. It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.
3. It is often used as a sub-routine to another sorting algorithm like radix sort.
4. Counting sort uses a partial hashing to count the occurrence of the data object in O(1).
5. Counting sort can be extended to work for negative inputs also.

Exercise:
1. Modify above code to sort the input data in the range from M to N.
2. Modify above code to sort negative input data.
3. Is counting sort stable and online?
4. Thoughts on parallelizing the counting sort algorithm.
00:36

GSM: Modulation Techniques - Overview of the Overview

I was in a training today, kinda joined in the middle of the session and saw that the faculty was about to start with modulation techniques used for digital signals and in GSM. So I though to write it down in my notebook, and sharing with you people.

Modulation: To modulate - To modify. Modifying signal with the reference signal.

I am not sure whether I explained it correctly or not. But here is the Wikipedia link to Modulation thing. Just go though it in case you are not sure about what modulation is.

So, there are many kinds of modulation techniques available today, some of them are:
(1) Amplitude Shift Keying (ASK)
(2) Frequency Shift Keying (FSK)
(3) Phase Shift Keying (PSK)
(4) Gaussian Minimum Shift Keying (GMSK) <-- This is mainly used in current GSM technology.
(5) Quadrature Amplitude Modulation (QAM)
and many others...

(1) Amplitude Shift Keying: Amplitude shift keying is a modulation technique in which the amplitude of the carrier signal is changed based on the information signal.

(2) Frequency Shift Keying: Frequency shift keying is a modulation technique in which the frequency of the carrier signal is changed based on the information signal.

(3) Phase Shift Keying: Phase shift keying is a modulation technique in which the phase of the carrier signal is changed based on the information signal.

Below is the image to explain what about techniques are exactly...

Amplitude Shift Keying, On-Off Keying, and Frequency Shift Keying.

I am still digging into the topic so don't expect this article to be fully correct or something. It may contain some false information which may have slipped away from my mind. If so, please correct me at any wrong point. I'll be greatful..

Keep learning. Keep sharing. Keep improving....
... See yaa in the next... :)

Q5WJMC7JZG6Y
03:19

Algorithms: What exactly is Big-O Notation.?

So, I've been reading as usual, as I found something to-the-point and interesting which is worth sharing with you people.

Its about Big-O Notation. How one can simply explain what Big-O Notation is.. Here is the answer.

This is a true story.

In 2009, a South African company named The Unlimited grew frustrated by their ISP’s slow internet and made news by comically showing just how bad it is. They “raced” a carrier pigeon against their ISP. The pigeon had a USB stick affixed to its leg and was taught to fly to an office, 50 miles away. Meanwhile, the company transferred this same data over the internet to this same office. The pigeon won -- by a long shot.

What a joke this ISP was, right? A BIRD could transfer data faster than them. A bird!

Their internet may or may not have been slow, but this experiment doesn't say much. No matter how fast or slow your internet is, you can select an amount of data that will allow the internet or a pigeon to win.

Here's why: 

How long does it take a pigeon to fly 50 miles with a 10 GB USB stick attached to its leg? Let's say it takes about 3 hours. Great.

Now, how long does it take to transfer 10 GB on the internet? Let's say you have pretty fast internet, and 10 GB only took 30 minutes. Okay, then transfer 100 GB and you know it will take more than 3 hours.

How long does it take that same pigeon to "transfer" 100 GB? Still 3 hours. The pigeon's transfer speed doesn't depend on the amount of data. (USB sticks are pretty light but can fit a ton of data.)

So, just like that: the pigeon beat the internet!

The pigeon's transfer time is constant. The internet's transfer time is proportional to the amount of data: twice the data will take about twice as much time.

In Big-O time, we'd say that the pigeon takes O(1) time. This means that the time it takes to transfer N gigabytes varies proportionally with 1. That is, it doesn't vary at all.

The internet's transfer speed is O(N). This means that the amount of time it takes varies proportionally with N.

Now, what if you had something that was O(N^2)? This would mean that the time varies with the size of N squared.

A real life example of an O(N^2) problem would be the time it takes to paint a square wall of length N (note: N is the length of the wall, not the area of the wall). If I make the edge of my square twice as long, the area of the square wall increases 4x.

Big-O offers an equation to describe how the time of a procedure changes relative to its input. It describes the trend. It does not define exactly how long it takes, as a procedure with a larger big-O time than another procedure could be faster on specific inputs.

Note: If you’ve taken an algorithms class, you might remember that, technically, big-O refers to an upper-bound. Anything that is O(N) could also be said to be O(N^2). To describe the exact runtime, we should be using big-theta.

However, outside of an algorithms class, this distinction has basically been forgotten about. People use big-O when they should really be using big-theta.
00:11

GSM: SIM Cards: IMSI, ICCID, IMEI, MSISDN

Again I read this on Quora. This is important to those who work in telecom industries. 

 IMSI = International Mobile Subscriber Identity. This is a unique identifier that defines a subscriber in the wireless world, including the country and mobile network to which the subscriber belongs. It has the format MCC-MNC-MSIN. MCC = Mobile Country Code (e.g. 310 for USA); MNC = Mobile Network Code (e.g. 410 for AT&T), MSIN = sequential serial number. All signaling and messaging in GSM and UMTS networks uses the IMSI as the primary identifier of a subscriber.
The IMSI is one of the pieces of information stored on a SIM card.


ICCID = Integrated Circuit Card ID. This is the identifier of the actual SIM card itself - i.e. an identifier for the SIM chip. It is possible to change the information contained on a SIM (including the IMSI), but the identify of the SIM itself remains the same.

IMEI is short for International Mobile Equipment Identity and is a unique number given to every single mobile phone, typically found behind the battery.
IMEI numbers of cellular phones connected to a GSM network are stored in a database (EIR - Equipment Identity Register) containing all valid mobile phone equipment.
When a phone is reported stolen or is not type approved, the number is marked invalid.
 
MSISDN = Mobile Station ISDN number. This is the full phone number of a subscriber, including the national country code (e.g. 1 for US, 44 for UK, etc.). The purpose of the MSISDN is simply to allow a device to be called. A subscriber can have multiple MSISDNs (e.g. one phone number for business, one for personal calls, one for fax, etc.), but generally only one IMSI. The MSISDN does not need to be stored on the SIM card. In cases where it is stored on the SIM, the main reason is so that the user can use check to see what their own MSISDN is (in case they forget). The MSISDN is never signaled to of from the device.

 Hope it helps.

 Keep learning. Keep Sharing. Keep Improving.
..... Later Folks :)
1Abc Directory
23:57

Psychology: Some more psychological facts

Hey folks,

You might have read my previous post about the psychological facts, so here are some more facts about the psychology. I continued reading the whole article on the Quora, and it really amazed me, so I am sharing some more of it. Hope you like them.

Topic #1:
 Inception (only sort of) or Incorporation of Reality in Dreams

You can alter someone's dreams as they are dreaming.

What the brain does, ever so often, is include stimuli happening in reality in whatever one is dreaming. Say you throw water on someone who is sleeping and she wakes up all of a sudden and narrates what she saw in her dreams. More often than not this gushing of water is incorporated elegantly in the dream. This served as inspiration for a sequence in Inception where  [1]

a sleeping Cobb is shoved into a full bath, and in the dream world water gushes into the windows of the building, waking him up

This happened in reality.

 And caused this in his dream.

Freud had also mentioned this. Alfred Maury in Le sommeil et les rêves narrates how a bar falling on his neck while sleeping became a guillotine in his dream and he woke up suddenly. This was related by Freud in The Interpretation of Dreams.

Also sounds happening around us make their way into our dreams. Optimistically, you can think of introducing characters in dreams by saying some names while someone is sleeping. This is exactly what Berger set out to do.[2]
Berger (1963) assessed the effects of meaningful verbal stimuli on dreaming. These stimuli were the names of the subjects' friends (provided by the subjects) that when presented while the subjects were awake had elicited the largest galvanic skin responses (GSRs). Dream incorporation was judged to have taken place on about half of the occasions. Of the 48 dreams that were judged to have been affected by the stimuli there had been 31 incorporations on the basis of assonance alone - for instance, 'Gillian' had been voiced as 'Chilean', 'Jenny' as 'Jemmy', and 'Mike' as 'like'. Only on three occasions had the named individual actually appeared in the dream as themselves.

Anyone up for a little game of Inception?

Topic #2:
Bystander effect 

You might want to believe that if you are in an accident or emergency, you would have a greater chance of being rescued if you are in a crowded place. But countless experiments and incidents have proven exactly the opposite.The greater the number of observers, the less likely it is that one of them will help you. This is due to a phenomenon called Diffusion of responsibility whereby a person is less likely to take responsibility for action or inaction when others are present.


[image from Overcoming the Bystander Effect]

If you have ever worked in a group project in school.or college you probably have experienced this first-hand. There is almost always that one guy or girl who refuses to contribute to the project till the very end. 

A darker example of this phenomenon is the group dynamics in a gang rape.[3]
These factors are diffusion of responsibility, deindividuation, and modeling, all of which can be applied to the dynamics of gang rape. Thus, no one individual in a gang rape believes that he is solely to blame for the victimization taking place.

This effect goes even deeper[4]

Topic #3. 
Cocktail party effect

Even in a noisy, crowded place if someone says your name, you can tune out other noises and focus on that voice. This effect is also true for other information that might be important to us. This effect changed the way psychologists thought about auditory input and attention. 

Do we listen to everything first and then filtering takes place? Or filtering of supposedly useless input takes place even before we hear things? 

This effect led to the concept of attention models which is important in psychology
[1] With 'Inception,' Chris Nolan's head games continue
[2] Experimental Modification of Dream Content by Meaningful Verbal Stimuli
[3]Gang Rape: A Psychological Perspective of Group Dynamics
[4]10 Notorious Cases of the Bystander Effect - Listverse
23:41

Psychology: Some awesome psychological facts

Yea, you read it right. Its about psychology. I've been reading on Quora and found this interesting topic with lot many answers. I mean, I really felt some of them, but never knew the exact reason of feeling the same.

 So here are some of the psychological facts that may get you into thinking why you've done something instead of something else [hehe, confusing..!! Even I got confused while writing this. So deal with it, its really gonna be little more difficult to understand certain things in this article.] 

 Topic #1:

 The paradox of choice - which I believe is both the blessing and the bane of our generation (Gen Y).
 
To put it simply, the paradox of choice states that the more choices one is given when making a decision, the less happy they tend to be about the decision they make (even if the selection is objectively better). This is driven by many factors, namely:
  • Additional effort and psychological stress associated with evaluating multiple options
  • Increased opportunity cost(the way in which we value things depends on what we compare them to. It's thus easier to imagine the attractive features of rejected options, the features we did NOT choose)
  • Greater "buyer's remorse" (with so many alternatives, it's easier to imagine how another choice would have been better)
  • Increased expectations from options ("with 87 options I have to find the perfect option for me")
  • Finally, we are more likely to blame ourselves when our choices don't meet our expectations ("I had all these options, it's obviously my fault, I should have picked better" vs. "I was only presented with 2 options, not enough to make the right decision")

In affluent societies, youth is presented with an overwhelming selection of options whether for small less significant decisions (e.g., 87 types of toothpastes) or for more significant decisions (e.g., university degrees, career paths). I believe theparadox of choice is one of the underlying reasons why so many of us (including myself) are increasingly indecisive and anxious about these so called "life decisions". But that's a different topic...

 Topic #2:
People don't notice you or your screwing up as much as you think they do.

The belief that people are constantly scrutinising your behaviour and the resultant paranoia and self-doubt that arises from it is called the spotlight effect. 

Even if you do something embarrassing, like spilling a drink down your front or falling flat on your face, other people don't notice/criticise you as much as you think they do.

In an experiment conducted by Thomas Gilovich et al, test subjects were made to wear embarrassing T-shirts and asked to estimate how many people giggled about it behind their back (read: noticed that they had an embarrassing T-shirt on). The subjects overestimated the number of people they thought had observed their clothing- their predictions were twice as big as the actual number.

So what can you learn from this? Take a deep breath and look around. You are surrounded by hundreds and thousands of people who are more or less just like you. Nobody is paying specific attention to you, waiting for you to slip up so that they can make fun of you.
Get over it.

This also means that the positive things you do will be forgotten over time, but oh well...the spotlight doesn't shine on any of us no matter what we do.

 Hope you enjoyed [what...?? Are you kiddin' me..?] the article..

Keep learning. Keep sharing, Keep Improving.
.....Later folks. :)
23:22
+

Copyright 2014 Learn. Share. Improve.

Designed by Template Trackers