Handy Maths to solve Data Structure Problem

Let me first define the problem:

Prob: F(n) is a function defined as :

F(n) = 1 ; n = 1

F(n) = F(n-1) + 1/n ; n>1

Prove that Big Oh of F(n) is log n

Solution:

F(n) = F(n-1) + 1/n

= F(n-2) + 1/(n-1) + 1/n

=F(n-3) + 1/(n-2) + 1/(n-1) + 1/n

This kind of series is called the Harmonic Series and can be represented as 1 + 1/2 + 1/3 + 1/4 + ......+ 1/n

Mathematically we can prove that the sum of an Harmonic series is ln n + gamma( a constant). This constant is called Euler's constant and its approx value is 0.57721

Therefore, we can say limit   f(n) = limit ln n + gamma

                               n->infinity       n->infinity

Hence                limit   f(n)/log n 

                         n->infinity 

                       = limit (ln n + gamma)/log n

                          n->infinity

                       = limit ln n/log n  +  gamma/limit log n

                           n->infinity                  n->infinity

                       = ln 2 + 0

                       = ln 2

Hence we can say F(n) = O(log n)

You can find the document here.

For my Data Structure Students - Insertion Sort

The Algorithm -

Lets define a function to insert an integer into a non-decreasing sorted array. See the function void insert(int x[], int& length, int& number_to_be_inserted). What it does, is that it starts scanning the array from the end - the maximum number (as it is a non-decreasing array). Whenever it finds that the number_to_be_inserted is less than than the number in the array, it shifts the position of that number in the array towards right. Otherwise it inserts the new number in that position. This principle can be applied to Sort an array. We will start with an one element array. It is obviously sorted. We will pick up the next element and put it in the right place of the sorted array. Thus we get a two element sorted array. Similarly we can get a sorted array of size n.

In the following code snippet, the Method I is the Algorithm with a separate Insert Function. The method II is the sorting algorithm with the Insert function inbuilt into it.

The source code of Method I can be found here.

The output of this program is as given below

The source code of Method II can be found here.

The output of this program is given below

Hope you enjoy this study.

For my Data Structure Students - Selection Sort

As mentioned earlier, i have started writing code and analyzing of various data structure area of computer science... Here is one such Sorting Algorithm called Selection Sort. In the first pass, it just finds the minimum number and exchanges it with the first place, in the second pass it finds out the second most minimum number and exchanges it with the second position.


Please find the source code of the Selection Sort from here.


The result of the code is as shown below. Please look at how at each outer loop pass, the small numbers occupy the places in the beginning of the sorted array...

Analysis:

For first outer loop, the inner loop goes for n-1 times, for the second outer loop, the inner loop goes for n-2 times and so on. The outer loop itself goes for n-1 times.

Hence f(n) = (n-1) + (n-2) + (n-3) + ....+ 2+1 = n*(n-1)/2

Hence O(n) = n^2

Hope you enjoy this...

For my Data Structure Students - Bubble Sort...

As a professor of computer science i have started recapitulating the basic theoretical computer science. Few days back i have written the code for bubble sort and did its analysis. I would like to share it with the student community...

You can find the source code from here.

The result of the above program is shown below.

Please have a look at how at each pass of the outer loop the large numbers are pushed towards the end.


Analysis:

The outer loop of the bubblesort algorithm does n times. For first outer loop the inner loop is for n-1 times, for second outer loop the inner loop is for n-2 times and so on.

Hence total loop count is (n-1) + (n-2) +........+2+1 = n*(n-1)/2

Hence O(n) = n^2

Hope this discussion helps the student community...

For my Microprocessor Students

I got this resource by googling. Hope this helps the student community.

Microprocessor Training

A good simulator for 8085 programming on PC is GNUSIM8085 and it is available at http://gnusim8085.org/


The interface of GNUSIM8085 looks like the following.