CSE SOLUTION SITE



Data Structure Question List | Solve
Data Structure Question List | Solve

(Bubble Sort) BUBBLE(DATA, N) Here DATA is an array with N elements. This algorithm sorts the elements in DATA.

    
1.   Repeat Steps 2 and 3 for K = 1 to N - 1.

2.   Set PTR : = 1.       [Initializes pass pointer PTR.]

3.     Repeat while PTR < N - K:    [Execute pass.]  // Less Than Equal

      (a)   If DATA[PTR]  > DATA[PTR + 1], then:
               Interchange DATA[PTR] and DATA[PTR + 1].
               [End of If Structure.]

     (b)  Set PTR : = PTR + 1.

           [End of inner Loop.]
     [End of Step 1 outer loop.]

4. Exit.


Number Sorted Of Bubble Sort

Suppose the following numbers are stored in an array A: 32, 51, 27, 85, 66, 23, 13, 57

We apply the bubble sort to the array A. We discuss each pass separately

    
Pass 1. We have the following comparisons:


(a)  Compare A1  and A2. Since 32 < 51, the list is not altered.
(b)  Compare A2  and A3. Since 51 <  27, interchange 51 and 27 as follows:
                                                      
                                                  32, 27, 51, 85, 66, 23, 13, 57

(c)  Compare A3  and A4. Since 51< 85, the list is not altered.
(d)  Compare A4  and A5. Since 85 > 66, interchange 85 and 86 as follows:
                                                      
                                                  32, 27, 51, 66, 85, 23, 13, 57

(e)  Compare A5  and A6. Since 85 > 23, interchange 85 and 86 as follows: 
                                                      
                                                  32, 27, 51, 66,  23, 85, 13, 57

(f)  Compare A6  and A7 Since 85 > 13, interchange 85 and 13 to yield: 
                                                      
                                                  32, 27, 51, 66,  23, 13,  85, 57

(g)  Compare A7  and A8. Since 85 > 57, interchange 85 and 51 to yield: 
                                                      
                                                  32, 27, 51, 66,  23, 13,  57, 85


At the end of this first pass, the largest number, 85, has moved to the last position. However, the rest of the numbers are not sorted, even though some of them have changed their position.


For the remainder of the passes, We show only the interchange.

Pass 2.  27, 33, 51, 66, 23, 13, 57, 85
             27, 33, 51, 23, 66, 13, 57, 85
             27, 33, 51, 23, 13, 66, 57, 85
             27, 33, 51, 23, 13, 57, 66, 85

At the end of Pass 2, the second largest number, 66, has moved its way down to the next-to-last position.

Pass 3.      27, 33, 23, 51, 13, 57, 66, 85
                 27, 33, 23, 13, 51, 57, 66, 85 

Pass 4.     27,  23, 33, 13, 51, 57, 66, 85  
                27,  23, 13, 33, 51, 57, 66, 85  

Pass 5.     23, 27, 13, 33, 51, 57, 66, 85 
                23, 13, 27, 33, 51, 57, 66, 85   

Pass 6.   13, 23, 27, 33, 51, 57, 66, 85       

Pass 6 actually has two comparisons, A1 with A2 and A3. The second comparison does not involve an interchange. 

Pass 7. Finally,  A1 is compared with A2. Since 13 < 23, no interchange takes place.

Since the list has 8 elements; it is sorted after the seventh pass.  
           


Using the bubble sort algorithm, Algorithm 4.4, find the number C of comparisons and the number D of interchanges which alphabetize the n = 6 letters in PEOPLE. The sequence of pairs of letters which are compared in each of the n - 1 = 5 Passes follow: a square indicates that the pair of letters is compared and interchanged, and a circle indicates that the pair of letters is compared but not interchanged.

    
Pass 1.  P E O P L E,   E P O PLE,  E O P P L E
            E O P P L E     E O P L P E   E O P L E P


Pass 2.    E O P L E P,   E O P L E P,    E O P L E P
               E O L P E P,     E O L E P P

Pass 3.   E O L E P P,  E O L E P P,  E L O E P P
             E L E O P P

Pass 4.  E L E O P P,  E L E O P P,  E E L O P P

Pass 5.   E E L O P P,   E E L O P P  


Solve Math problem By Using Linear Arrays: 4.1 Consider the linear arrays AAA(5:50), BBB(-5:10) and CCC(18). (a) Find the number of elements in each array. (b) Suppose Base(AAA) = 300 and W = 4 words per memory cell for AAA. Find the addess of AAA[15], AAA[35] and AAA[55].

    

(a) The number of elements is equal to the length; hence use the formula

Length = UB - LB + 1 Accordingly, Length(AAA) = 50 - 5 + 1 = 46 Length(BBB) = 10 - (-5) + 1 = 16 Length(CCC) = 18 - 1 + 1 = 18 Note that Length(CCC) = UB, Since LB = 1

(b) Use the formula

LOC(AAA[K]) = base(AAA) + W(K - LB) Hence: LOC(AAA[15]) = 300 + 4(15 - 5) = 340 LOC(AAA[35]) = 300 + 4(35 - 5) = 420 AAA[55] is not an element of AAA, since 55 exceeds UB = 50

(Matrix Multiplication) MATMUL(A, B, C, M, P, N) Le A be an M * P matrix array, and let B be a P * N matrix array. This algorithm stores the product of A and B in an M * N matix array C.

    
1.  Repeat Steps 2 to 4 for I = 1 to M:

2.   Repeat Steps 3 and 4 for J = 1 to N:

3.   Set C[I,J]:=0.  [Initializes C(I,J).]

4.    Repeat for K = 1 to P.
  
          C(I, J):  = C(I, J) + + A[I, K] * B[K, J]

          [End of inner loop.]
[End of Step 2 middle loop.]
   [End of Step 1 outer loop.]

5. Exit.


(Warshall's Algorithm) A directed graph G with M nodes is maintained in memory by its adjacency matrix A. This algorithm finds the (Boolean) path matrix P of the graph-G

    

1.  Repeat for I, J = 1, 2......, M: [Initializes P].
      If A[I, J] = 0, then : Set P[I, J]:=0;
 Else: Set P[I, J] : = 1.
[End of loop.]

2.  Repeat Steps 3 and 4 for K = 1, 2, ......., : [Updates P.]

3.  Repeat Step 4 for I = 1, 2,....,M:

4.                Repeat for J = 1, 2,......,M:
                                       Set P[I, J] : = P[I, J] v (P[I, J] ^ P[K, J]).
[End of loop].
[End of Step 3 loop]

5.Exit.


(Shortest Path Algorithm) A directed graph G with M nodes is maintained in memory by its weight matrix W. This algorithm finds a matrix Q such that Q[I,J] is the length of a shortest path from node VI tonode VJ.Infinity is a very large number, and MIN is the minimum value function.

    
1.  Repeat for I, J = 1, 2......, M: [Initializes P].
      W[I, J] = 0, then : Set Q[I, J]:=INFINITY;
 Else: Set Q[I, J] : = W[I, J].
[End of loop.]

2.  Repeat Steps 3 and 4 for K = 1, 2, ......., : [Updates P.]

3.  Repeat Step 4 for I = 1, 2,....,M:

4.                Repeat for J = 1, 2,......,M:
                                       Set Q[I, J] : = MIN(Q[I, J],  Q[I, K]  + Q[K, J]).
[End of loop].
[End of Step 3 loop]
[End of Step 2 loop]
5.Exit.


What is Overflow?

Overflow:
Sometimes new data are to be inserted into a data structure but there is no available space , i.e, the free-storage list is empty.This situation is called overflow.

What is underflow?

Underflow:
The term underflow refers to the situation where one wants to delete data from a data structure that is empty, The programmer may handle underflow by printing the message UNDERFLOW

Two basic Operation Of Stack:

(a) "PUSH"
"PUSH" is the term used to insert an element into a stack.

(b) "POP"
"POP" is the term used to remove an element into a stack.

What is Binary Trees?

(a) T is empty (called the null tree or empty tree), or (b) T constants a distinguished node R, called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary trees T1 and T2. If T does contain a root R, then the two trees T1 and T2 are called, respectively, the left and right subtrees of R. If T1 is nonempty, then its root is called the left successor of R; If T2 is nonempty, then its root is called the right successor of R.

Traversing Binary Tree

Traversing Binary Tree:
There are three standard ways of traversing a binary tree T with root R. These three algorithms, called preorder, inorder and postorder.

  
Preorder:
             
          (1)   Process the root R.
          (2)   Traverse the left subtree of R in preorder.
          (3)   Traverse the right subtree of R in preorder


Inorder:
             
           (1)   Traverse the left subtree of R in inorder.
           (2)   Process the root R.
           (3)    Traverse the right subtree of R in inorder




Postorder:
             
           (1)   Traverse the left subtree of R in postorder.
           (2)   Traverse the right subtree of R in postorder.
           (3)   Process the root R.


What is Recursion?

Recursion:
A recursive must have two proprties (a) There must be certain criteria, called base criteria, for which the procedure does not call itself. (b) Each time the procedure does call itself (directly or indirectly), it must be closer to the base criteria

Example Of Factorial Function

 
     
Example Of Factorial Function:    n! = 1.2.3...............(n-2)(n-1)n

0! = 1             1! = 1         2! = 1.2 = 2              3! = 1.2.3 = 6
 4! = 1.2.3.4 = 24  5! = 1.2.3.4.5 = 120  6! = 1.2.3.4.5.6 = 720
and so observe that 
             5! = 5.4! = 5.24 = 120

This is true for every positive integer n;  that is,
      n! = n.(n.1)!

(Factorial Function)

(a)  If n = 0, then n! = 1.
(b)  If n > 0, then n! = n. (n-1)!  


Procedure A: FACTORIAL(FACT, N)

    
This procedure calculate N! and returns the value in the variable FACT.

1.  If N = 0, then:Set FACT : = 1, and return.

2.  Set FACT : = 1. [Initializes FACT for loo.]

3.  Repeat for K = 1 to N.
        Set FACT : = K*FACT.
[End of loop.]

4.   Return.



© Copyright & reserved CSE Solve