CA-C2T: PROBLEM SOLVING TECHNIQUES

UNIT - 3 [12 Hours]

Factoring Methods: Finding the square root of a number, the smallest Divisor of an integer, the greatest common
divisor of two integers, computing the prime factors of an integer, generation of pseudo random numbers, raising a
number to a large power. Array Techniques: Array order Reversal, Array counting or Histogramming, Finding the
maximum number in a set, removal of duplicates from an ordered array, partitioning an array, Finding the kth
smallest element, multiplication of two matrices
Two Mark Questions

1) List any 4 Factoring methods.

Different types of factoring methods are:
a) Square root of a number
b) Greatest Common Divisor of two number.
c) Computing the Prime factor of an Integer.
d) Generation of Pseudo random number.

2) Write an algorithm to find square root of a number.

i. Establish m the number whose square root is required and the termination condition error e.
ii. Set the initial guess g2 to m/2.
iii. Repeatedly
(a) Let g1 assume the role of g2,
(b) Generate a better estimate g2 of the square root using the averaging formula,
Until the absolute difference between the g1 and g2 is less than error e
iv. return the estimated square root g2.

3) Write an algorithm to reverse an Array.

1. Establish the array a[1..n] of n elements to be reversed.
2. Computer 4 the number of exchanges needed to reverse the array.
3. While there are still pairs of array elements to be exchanges
a. Exchange the ith element with [n-i+1]th element.
4. Return the reversed array.

4) What is an array? List two types of representation of 2-D array stored in memory.
Array is a bounded collection of elements of same data type.
Two-dimensional array are stored in the memory in the following two ways:
a) Row-Major representation:
Location[i,j]= Base Address(A) + {i*ColSize)+j}*WordSize
b) Column-Major representation:
Location[i,j]= Base Address(A) + {i*RowSize)+j}*WordSize
5) Write a C function to print random number between 0 to 49. Include header file.
C Function :
# include <stdlib.h>
for (i=0 ; i < 50 ; i++)
{
printf(“%d \n”, rand() % 50 );
}

6) Write a C function to find GCD of 2 numbers using recursion.

int GCD(int n1, int n2)
{
If ( n2 != 0)
return GCD(n1, n1 % n2);
Else
return n1;
}
7) What is Histogramming? Explain with an example.
Histogramming is a type of graph used to count or visualize the frequency of data.
 Long Answers ( 4M / 5M / 8 M Questions )
1. Write an algorithm to find smallest divisor of an integer.
i. Establish n the integer whose smallest divisor is required.
ii. If n is not odd then return 2 as the smallest divisor
else
a. Compute r the square root of n,
b. Initialize divisor d to 3,
c. While not an exact divisor and square root limit not reached do (c.1) Generate next
member in odd sequence d,
d. If current odd value d is an exact divisor then return it as the exact divisor of n,
else return 1 as the smallest divisor of n.

2. Write an algorithm to compute prime factors of an integer.

1. Establish n the number whose prime factors are sought.
2. Compute the remainder r and quotient q for the first prime nxtprime=2.
3. While it is not established that n is prime do
(a) if nxtprime is an exact divisor of n then
(a.1) save nxtprime as a factor f,
(a.2) reduce n by nxtprime,
else
(a’.1) get next biggest prime
(b) Compute next quotient q and remainder r for current value of n and current prime
divisor nxtprime.
4. if n is greater than 1 then
Add n to list as a prime factor f.
5. return the prime factor f of the original number n.

3. Write an algorithm to raise the number to a large power.

1. Establish n, the integer power, and x the integer to be raised to the power n.
2. Initialize the power sequence and product variable for the zero power case.
3. While the power n is greater than zero do
(a) If next most significant binary digit of power n is one then
Multiply accumulated product by current power sequence value.
(b) Reduce power n by a factor of two using integer division.
(c) get next power sequence member by multiplying current value by itself.
4. Return x raised to the power n.

4. Write an algorithm to find maximum number in a set.

1) Establish an array a*1…n+ of n elements where n>=1
2) Set temporary maximum max to first array element
3) While less than n array elements have been considered do
(a) if next element greater than current maximum max, then assign it to max
4) Repeat maximum max for the array of n elements.
5. Explain Partition of an Array with an example
In the partitioning of an array, divide the array in such a way that the left part of the array will be
less than or equal to partition value (P) and the right part of the array will be greater than or equal
to the partition value.
Ex:
28 26 25 11 16 12 24 29 6 10
Random set;
Let P=17

12 6 10 11 16 (P) 28 24 29 26 25
<< <17 >> << 17> >>
A partitioned solution.

6. Write an algorithm to find kth smallest divisor of an integer.

7. Write a C program to find product of 2 matrices.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[3] [3], b[3] [3], mul[3] [3], i, j, k, n;
clrscr();
printf(“\n \t Enter the Order of the matrix: “);
scanf(“%d”, &n);
// Enter A matrix elements
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
scanf(“%d”, &a[i][j]);
}

// Enter B matrix elements

for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
scanf(“%d”, &b[i][j]);
}
// product matrix
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
mul[i][j]=0;
for(k=0; k<n; k++);
mul[i][j]+ = a[i][j] * b[i][j];
}
// print product matrix
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
printf(“\t %d”, mul*i+*j+);
printf(“\n”);
}
getch()
}
8. Write a C program to duplicate elements for an ordered list.
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20], n, i, j, ele;
clrscr();
printf(“\n Enter array limit(n): “);
scanf(“%d”, &n);
for(i=0; i<n-1; i++)
{
printf(“\n Enter a[%d]: “, i);
scanf(“%d”, &a[i]);
}
//remove duplicate
for(i=0; i<n-1; i++)
{
ele= a[i];
for(j=i+1; j<n; j++)
{
if(ele==a[j] && a[j]! = -111)
{
printf(“\n %d duplicate entry!!! “, a[j]);
a[j]= -111; //set -111 for duplicate entry!!!
}
}
}
printf(“\n Final Array List \n”);
for(i=0; i<n; i++)
{
if( a[i]!= -111)
printf(“ %5d”, a[i]);
}
getch();
}
9. Write a C program to find addition and subtraction of two matrices.
#include<stdio.h>
#include<conio.h>
void main()
{
int a[3] [3], b[3] [3], add[3] [3],sub[3][3] i, j,n;
clrscr();
printf(“\n \t Enter the Order of the matrix: “);
scanf(“%d”, &n);

// Enter A matrix elements

for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
scanf(“%d”, &a[i][j]);
}
// Enter B matrix elements
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
scanf(“%d”, &b[i][j]);
}
// add & sub of two matrices
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
add[i][j] = a[i][j] + b[i][j];
sub[i][j] = a[i][j] – b[i][j];
}
// print addition matrix
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
printf(“\t %d”, add[i][j]);
printf(“\n”);
}
// print subtraction matrix
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
printf(“\t %d”,subl*i+*j+);
printf(“\n”);
}
getch()
}