Sunday, 10 December 2017

CS201 - Introduction to Programming -- Assignment No.2 - Fall 2017 - Solution

Leave a Comment
Objectives:
To enable students to write, compile and execute a program in DevC++. Moreover to familiarize students with  the concepts of:

  • If else structure
  • Loops
  • Passing array to a function
  • Multidimensional array declaration
  • Multidimensional array manipulation

Assignment:
Write a program that will generate random numbers and that numbers will be stored in a two-dimensional array. Then display the generated values on the screen and then also print the even numbers from the generated array elements.

Task 1:

First of all, you are required to generate random numbers from 1 to 500. For this, you are required to create a function named as “generateArray. The generateArray will load two- dimensional array with random numbers from 1to 500. The size of the two-dimensional array will be 7*7.

Task 2:

Defined a function named as “showArray(), which will display the elements of the two- dimensional array on the screen. See the sample output.

Task 3:
            The final task is to find the even numbers in this array and display it on the console. For this purpose create a function findEvenNumber().

CS201 - Introduction to Programming -- Assignment No.2 - Fall 2017 - Solution


Solution:

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

// functions definations
void generateArray(int inArr[7][7])
{
       for (int i = 0; i<7; i++)//rows
       {
              for (int j = 0; j<7; j++)//columns
              {
                     inArr[i][j] = rand() % 500 + 1; //Random Values Generation
              }
       }
}

void showArray(int inArr[7][7])
{
       for (int i = 0; i<7; i++)//rows
       {
              for (int j = 0; j<7; j++)//columns
              {
                     cout << inArr[i][j] << "\t"; // Output on Console
              }
              cout << "\n";
       }
}

void evenArray(int inArr[7][7])
{
       for (int i = 0; i<7; i++)
       {
              for (int j = 0; j<7; j++)
              {
                     if (inArr[i][j] % 2 == 0)
                     {
                           cout << inArr[i][j] << "\t"; // Output Even Values on console
                     }
              }
       }
}
// -- main body
main()
{
       int randarr[7][7];
       srand(time(NULL));// Null Time Randow Initialization
                                    // Array Generation
       generateArray(randarr);
       // Raw Array Output
       cout << "Array Element......\n\n";
       showArray(randarr);
       // Even Array output
       cout << "\n\nEven Array......\n\n";
       evenArray(randarr);
       // pause console screen
       cout << "\n\n";
       system("pause");
}


Read More

CS201 - Introduction to Programming -- Assignment No.1 - Fall 2017 - Solution

Leave a Comment
Objectives:
To enable students to understand and practice the concepts of:

  • Variables and operators
  • Expressions in C++
  • Decision structures
  • Repetition structures

Assignment:
Write a program that will
  1. Ask the user to enter lower limit and upper limit in the form of integer numbers.
  2. The program will then add / sum all those numbers between upper limit and lower limit (including the lower and upper limits) which are NOT multiple of 4.
  3. This process should continue for all the remaining integer numbers up until the upper limit is reached.
  4. The program will then show the aggregate sum of all numbers for the given range.

Make sure that lower limit entered by the user should be greater than zero. Also the upper limit value entered by the user should be greater than the lower limit value.

Example:
Lower limit is 1 and Upper limit is 8 then the program will subtract 4 and 8 as these are the multiples of 4. While add remaining integers in the range (1+2+3-4+5+6+7-8 = 12). So, 12 is the calculated number.

Sample output for correct input:
CS201 - Introduction to Programming -- Assignment No.1 - Fall 2017 - Solution

Sample output for the wrong input:
CS201 - Introduction to Programming -- Assignment No.1 - Fall 2017 - Solution

Sample output for the wrong input:
CS201 - Introduction to Programming -- Assignment No.1 - Fall 2017 - Solution

Solution:

#include<iostream>
using namespace std;
main()
{
       int upperlmt, lowerlmt, sum = 0, a;
       cout << "Please Enter Lower Limit <Greater Then 0 >: ";
       cin >> lowerlmt;
       if (lowerlmt > 0)
       {
              cout << "Please Enter Upper Limit <Greater Than Lower Limit>: ";
              cin >> upperlmt;
              if (upperlmt > lowerlmt)
              {
                     for (a = lowerlmt; a <= upperlmt; a++)
                     {
                           if (a % 4 == 0)
                           {
                                  sum = sum - a;
                           }
                           else
                           {
                                  sum = sum + a;
                           }
                     }
                     cout << "Calculated Number is " << sum << endl;
              }
              else
              {
                     cout << "Upper Limit Must Be Greater Than Lower Limit" << endl;
              }
       }
       else
       {
              cout << "Lower Limit Should Be Greater Then Zero" << endl;
       }
       system("pause");
}
Read More

Thursday, 16 November 2017

COUNTING SORT – EXPLANATION, PSEUDOCODE AND IMPLEMENTATION

Leave a Comment
Counting Sort is a linear sorting algorithm with asymptotic complexity O(n+k), which was found by Harold Seward in 1954.
Counting Sort is very time efficient and stable algorithm for sorting. Unlike bubble sort and insertion sort, counting sort is not a comparison based algorithm. It avoids comparisons and exploits the O(1) time insertions and lookup in an array.

Counting Sort algorithm works on the keys that are small integer and lies between a specific range. It functions by counting the number of objects that have each distinct key value. Then it uses some arithmetic calculation to place each key value into a sorted sequence.
Its running time is O(Maximum key value – Minimum key value) which is linear. So it is useful only when a difference is not large.

HERE ARE SOME KEY POINTS OF COUNTING SORT ALGORITHM –

  • Counting Sort is a linear sorting algorithm.
  • Time complexity of Counting Sort is O(n+k), where n is the size of the sorted array and k is the range of key values.
  • It is not an in-place sorting algorithm as it requires extra additional space O(k).
  • Counting Sort is stable sort as relative order of elements with equal values is maintained.
  • Counting Sort is inefficient if the range of key value (k) is very large. If the input array is already sorted then also it will require an additional array to store the sorted elements and will process it completely.
  • Counting Sort has a disadvantage that it can only sort discrete values like integer, as frequency range cannot be constructed for other values.

PSEUDOCODE OF COUNTING SORT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
CountingSort(A)
  //A[]-- Initial Array to Sort
  //Complexity: O(k)
  for i = 0 to k do
  c[i] = 0
 
  //Storing Count of each element
  //Complexity: O(n)
  for j = 0 to n do
  c[A[j]] = c[A[j]] + 1
 
  // Change C[i] such that it contains actual
  //position of these elements in output array
  ////Complexity: O(k)
  for i = 1 to k do
  c[i] = c[i] + c[i-1]
 
  //Build Output array from C[i]
  //Complexity: O(n)
  for j = n-1 downto 0 do
  B[ c[A[j]]-1 ] = A[j]
  c[A[j]] = c[A[j]] - 1
end func

ASYMPTOTIC ANALYSIS OF COUNTING SORT

In this algorithm, the initialization of the count array and the loop which performs a prefix sum on the count array takes O(k) time. And other two loops for initialization of the output array takes O(n) time. Therefore, the total time complexity for the algorithm is : O(k)+ O(n)+ O(k)+ O(n)= O(n+k).
Worst Case Time complexity: O (n+k)
Average Case Time complexity: O(n+k)
Best Case Time complexity: O(n+k)
Space Complexity: O(k)
Data Structure: Array
Sorting In Place: No
Stable: Yes

Implementation of Counting Sort in C and Java programming language
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* C implementation Counting Sort */
#include <stdio.h>
 
/*  Counting sort function  */
void counting_sort(int A[], int k, int n)
{
    int i, j;
    int B[n], C[k+1];
 
    //Initializing counting array C[i] to 0
    for (i=0; i<=k; i++)
        C[i] = 0;
    //Store count of each element in array C
    for (j=0; j<n; j++)
        C[A[j]] = C[A[j]] + 1;
 
    /* Change C[i] such that it contains actual
    position of these elements in output array*/
    for (i=1; i<k+1; i++)
        C[i] = C[i] + C[i-1];
 
    //Creating Output array from C[i]
    //and decrementing value of C[i].
    for (j=n-1; j>=0; j--)
    {
        B[C[A[j]]-1] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }
 
    //Printing sorted array
    printf("The Sorted array is : ");
    for (i=0; i<n; i++)
        printf("%d ", B[i]);
}
 
/*  The main() begins  */
int main()
{
    int n, max = 0,i;
    printf("Enter the number of input : ");
    scanf("%d", &n);
    int A[n];
    printf("\nEnter the elements to be sorted :\n");
    /*Storing element in a array.
     And finding max of elements to set range
     of counting array C[]*/
    for (i=0; i<n; i++)
    {
        scanf("%d", &A[i]);
        if (A[i] > max) {
            max= A[i];
        }
    }
    //calling counting-sort function
    counting_sort(A, max, n);
    printf("\n");
    return 0;
}

Counting Sort is one of the most efficient and a stable algorithm for sorting. It is simple to understand and easy to implement. A good programmer must know this linear sorting algorithm. This is also a hot topic in many beginner and algorithm based interviews.
Some other Linear Sorting Algorithms are: Bucket Sort and Radix Sort.(Will be discussed in future posts)
Radix Sort can handle larger keys more efficiently as compare to Counting Sort.
Read More

Popular Posts