Ignou Solved Assignments

#include<stdio.h>
int main()
{
  int a[50], size, i, big, small, count = 0;
  printf("\nEnter the size of the array: ");
  scanf("%d", &size);
  printf("\n Enter %d elements in to the array: ", size);
  for(i=0; i<size; i++)
      scanf("%d", &a[i]);
  big = a[0];
  for(i = 1; i < size; i++){
      if(big < a[i])      
           big = a[i];
              {
                 count++;
              }
  }
  printf(" Largest element: %d \n ", big);
  small = a[0];
  for(i=1; i<size; i++)
{
      if(small > a[i])
              {
                  count++;
              }
           small = a[i];
  }
  printf(" Smallest element: %d \n ", small);
  printf(" number of comparison %d ", count);
  return 0;
}

Output:

step 1 : Start
step 2 : Declare variables int a[50], size, i, big, small, count = 0 step 3 : read value
step 4 : get the value element for the array                         step 5 : begin the operation for largest number
               in loop if big is less than a[i]
               do small = a[i]
               count the comparison 
                               comparison ++
step 6 : Display Largest element
step 7 : begin the operation for small  number
               in loop if small is greater than a[i]
               do big = a[i]
               count the comparison 
                               comparison ++
step 8 : Display Smallest element
step 9 : stop.

Question 2:Write Prim’s algorithm and apply it to find a minimum cost spanning tree of the following Graph. Show all the steps.
Solution:-

How does Prim’s Algorithm Work?The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree (mst).

  

Finally we get the following graph.

(ii) Differentiate between Bellman-Ford and Dijkstra’s algorithm to find a shortest path in a graph.

Initial step:
sDist[A] = 0; the value to the source itselfsDist[B]= ∞, sDist[C]= ∞, sDist[D]= ∞, sDist[E]= ∞; the nodes not processed yet

Quicksort (A, p, r) // Sort A[p .. r] into ascending order.
1. if (p < r)
1.1 q = Partition(A, p, r)
1.2 Quicksort(A, p, q-1)
1.3 Quicksort(A, q+1, r)

Partition (A, p, r) // It is assumed that p <= r.
1. x = A[r]; i = p-1; // x is the pivot value.
2. for j = p to r-1 do
if (A[j] <= x) {i = i + 1
Exchange A[i] with A[j].}
3. Exchange A[i+1] with A[r].
4. return i+1.

/* A typical recursive implementation of quick sort */

#include<stdio.h>
// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */

int partition (int arr[], int l, int h)
{
    int x = arr[h];    // pivot
    int i = (l - 1);  // Index of smaller element
    for (int j = l; j <= h- 1; j++)
    {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= x)
        {
            i++;    // increment index of smaller element
       swap(&arr[i], &arr[j]);  // Swap current element with index
        }
    }
    swap(&arr[i + 1], &arr[h]); 
    return (i + 1);
}
/* arr[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */

void quickSort(int arr[], int l, int h)
{
    if (l < h)
    {
        int p = partition(arr, l, h); /* Partitioning index */
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, h);
    }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
// Driver program to test above functions
int main()
{
    int arr[] = {25,5,30,40,15,65,20,35};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:-

Question 5:Illustrate representation of the following graph:(a) Through adjacency matrix and adjacency list

Solution:-(a) Through adjacency matrix and adjacency list

• Take a vertex that is not visited yet and mark it visited
• Go to its first adjacent non-visited (successor) vertex and mark it visited
• If all the adjacent vertices (successors) of the considered vertex are already visited or it doesn’t have any more adjacent vertex (successor) – go back to its parent vertex

T(n) = 2T(n/2) + n2.

The recursion tree for this recurrence has the following form:

In this case, it is straightforward to sum across each row of the tree to obtain the total work done at a given level: This a geometric series, thus in the limit the sum is O(n2). The depth of the tree in this case does not really matter; the amount of work at each level is decreasing so quickly that the total is only a constant factor more than the root.

T(n) = T(n/3) + T(2n/3) + n.

Expanding out the first few levels, the recurrence tree is:

    T(n)  = 2T(n/2)+ n
        = 2(2T(n/4))+ n/2)+ n
        = 4T(n=4)+2n
               = 8T(n=8)+3n =

T(n)  = 2T(n=2)+ n = 21T(n=21)+1.n  [k = 1, given recurrence]
T(n)  = 2k-1T(n=2 k-1)+(k -1)n     [inductive hypothesis]
       = 2 k-1(2T(n/2k)+ n/2 k-1)+(k -1)n   [substitution]
       = 2kT(n=2k)+ kn                     [algebra]

      T(n) = nT(1)+ n log2 n = n log2 n+ n.