PROBLEM SOLVING TECHNIQUES

STUDY MATERIAL

1. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
1

UNIT 1: INTRODUCTION TO COMPUTER PROBLEM SOLVING
Programs and Algorithms

 Computer solution to a problem is a set of explicit and unambiguous instructions expressed in a
programming language.
 Set of instructions is called a program.

 A Program can thought as algorithm expressed in a programming language.

 An algorithm corresponds to a solution to a problem that is independent of any programming
language.
 Program should supply with input data.

 Input data manipulate according to the instructions and produce the output.

 Output represents computer solution to the problem.

Algorithm:

Algorithm consists of a set of explicit and unambiguous final steps which, when
carried out for a given set of initial conditions, produce the corresponding output and
terminate in a finite time.
Requirements for solving problems by Computer

 One can employ algorithms to solve problems.
 Depth understanding is needed to design algorithm which solve any complex problem.
Problem Solving Aspect in detail

 Problem Solving is a creative process which largely defines systematic and mechanization.
 Problem solving has number of steps to achieve the goal.

1) Problem definition phase:

v Defining the problem fully is done in the problem definition phase.

v This phase decides “What must be done” rather “How to do it”.

v Problem statement gives a set of precisely defined tasks.

2) Getting started on a problem:

 Many ways to solve most problems.
 Many solutions to most problems.
 Difficult to identify which path is fruitful and fruitless while solving a problem.
 After getting complete idea it is better to start implementation. It means “What can we do”.
Use of specific examples:
 Many strategies, while using, we may stuck in some point.
 It is usually much easier to work out the details of a solution to a specific problem.
 Geometrical or schematic diagrams representing certain aspects of the problem can be
usefully employed in many instances.
4) Similarities among problems:

v Get the past experience for any current problem

2. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
2

v Start any solving process with specific example.

v Have aware about the similarities of various problems.

v More experience in more tools and techniques helps to solve the problem easily.

v Sometimes previous experience blocks new creativity or better solution.

v Place only cautious reliance on past experience.

v Independently solving the problem sometimes gives better solution.

v Analyzing past problems and experience sometimes leads to dead end.

v Solve a problem after viewing the problem from different angles.

v Analyze the problem by turning a problem upside down, inside out, sideways,
backwards, forwards and so on…..
5. Working backwards from the solution

v Try to work backwards to the starting conditions. This is significantly better.

v Important thing in developing problem solving skills is practice.

v Piaget says that “We learn more when we have to intent”.

General problem solving strategies:

v There are many general and powerful computational strategies that are used in
many guises in computer science.
v Mostly used principle is “Divide and Conquer Strategy”.

v Divide and Conquer:

Ø It divide the original problem in to sub problems

Ø It is possible to split the problem into smaller and smaller sub problems.
v Dynamic Programming

o Build up a solution to a problem through a sequence of intermediate
steps.
o Idea that a good solution to a large problems by finding
good solution to smaller problems
o It is technique for solving problems with overlapping sub problems
Dynamic Programming algorithm:

v Refined to avoid using extra space.

v Avoid solving unnecessary sub problems.

v It is an algorithm design technique for optimization problems.

v Solves problems by combing solutions to sub problems.

v Sub problems dependent.

v Solutions of sub problem not affect another sub problem

3. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
3

Top Down Design

v An algorithm is able to implement a correct and efficient computer program.

v To solve a problem powerful techniques are used to design an algorithm.

v The problem can be solved effectively if the algorithm manages the inherent complexity.

v A technique for algorithm design that tries to accommodate some human limitations
is known as Top down design or stepwise refinement.
v Solve the problem in stepwise fashion.
] [1] Breaking a problem into sub problems

v First the ground work should be done that gives the outline of a solution.

v Problem description itself sometimes gives starting point for top down design.

v Outline may have set of statement or a single statement.

v One statement or task can be splitted into sub tasks.

v These well-defined sub tasks are useful to reach the final goal.

v Sub tasks need to interact with each other should well defined. This preserve over
all structure of the solution to the problem.
v Preservation of overall structure needed to prove the correctness of the solution.

v Large task is divided into sub tasks. Sub tasks are again sub divided into sub tasks.
End sub tasks form the program statement.
v Schematic breakdown of a problem into sub tasks as employed in top down design.

4. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
4

[2] Choice of a suitable data structure
v Important decision in formulating computer solutions to problems is the choice
of appropriate data structures.
v Organized data has the effect on final solution.

v Inappropriate choice leads to a simple, transparent and efficient implementation.

v Data structure can be defined at any stage of the algorithm development.

v It is desirable when considered DS at very outset of our problem solving
explorations before the top down design.
v It can also be refined as the algorithm is developed.

v Data structures and algorithms are linked to each other.

v A small change in data organization can have a significant influence on an algorithm.

v There is no formula that is problem must use this choice of data structure.

v Things to be asked or aware when DS chosen are

§ How can the intermediate results are arranged that reduce computation in the later
stage?
§ Can the data structure be easily searched?

§ Can the data structure be easily updated?

§ Can earlier state can be recovered?

§ Whether need excess storage?

§ It is possible to impose some data structures on a problem that is not initially
apparent?
§ Can be problem be formulated in terms of one of the common data structures.

Example: array, set, queue, stack, tree, graph, list?
[3] Construction of loops:

v Sub tasks are leads to series of iterative constructs, loops or structures that work
under condition.
v These, work with i/p or o/p statements, computable expressions and assignments form
the heart of the program implementation.
v Loop has three important parts

· Initial condition – loop begins

· Invariant relation – apply for each iteration

· Terminate (condition) – Under which iterative process work or terminate.

v Some problems use straight forward process instead of loops.

5. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
5



a




g


[4] Establishing initial conditions for loops

v Set loop variable to a value
v The range may be 0≤i≤n for n iterations.
v A smallest problem has i=0 or i=1
v n=0 means i=0 and s=0
[5] Finding the iterative construct
v To solve a problem of i=1 then we must solve i=0
The solution for n=1

I = 1
S = a[1]
The solution for n>1 is
i=i+1
s=s+ [i]
The solution to summation problem is n≥0
i=0; s=0;

while i<n do

be in

i=i+1;

s=s+a[i];

end

[6] Termination of loops

v Loops terminated by

 Known number of iterations.
 Direct termination facility in program code.
 Termination possible with simplifying test

IMPLEMENTATION OF ALGORITHMS
 Properly designed in a top down fashion
 Top down rule easy to understand and debug
 Also easy to modify because the program are much more apparent.
[1] Use of procedure to emphasize modularity:

v Top down design are easy to understand and more readable, thus it can be modularize.
v Modularize means splitting the large or lengthy program into set of
independent procedures.
v This set of procedures will perform well defined tasks.

Procedure sort

Begin

Writeln(‘sort called’)

end

6. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
6

[2] Choice of variable names:

v Proper variable names are chosen so that easy to understand and remember in
future work.
v Example : To name a variable to store a day means, variable name is day instead of
just d or a.
v A clean definition of all variables and constants at the start of each procedure can
makes the program more meaningful. This is a process of self documenting.
3] Documentation of programs:

v A program should be more effective and useful if it understood and used by other people.

v It must give the extract requirement i.e input with format for the user.

Example: Enter a number between 0 to 10 as a whole number.
v The program should properly handle the wrong request i.e proper response should
be given.
[4] Debugging programs:

v Various test should be done even for a small program to have a error free program.
v Additional information given with output that it can work normal or abnormal
situation respect to the input given.
v A simple debugging tool is Boolean variable.

if debug then
Begin
Writeln(…..)
End
v Error should be handled more effectively which results in a good program.
v Work the program by hand before put in to the system.
5] Program Testing

v A program must be designed to solve a problem which can accommodate with
limiting and unusual cases.
v Unusual cases make the program critical.
v Necessary to handle all types of inputs.
v A program should properly respond to the user inputs.
v Writing a program to a specific case generally need a lot of time and effort.
v Program must solve wide area of problems.
v Instead of fixed constants, variables are used.
Program Verification:
 It refers to an application of mathematical proof techniques to establish that the results obtained
by the execution of a program with arbitrary inputs are in accord with formally defined output
specifications.
 Prove the algorithm at the basic level itself or abstract or superficial level.
[1] Computer model for program execution

v A program may have variety of path for termination.
v According to the input path has chosen for execution and terminate.
v A program may transit from one state to another.

7. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
7

P Q
P Q
True True True
True False False
False True True
False False true

v A state transition changes the value of the variable in a current execution path.
v As well as instructions that change the computation state there also other instructions
that simply makes tests on the current state.
v These tests make change in the sequential flow of execution.
v This model for program execution provides us with a foundation on which to
construct correctness proofs of algorithms.
[2] Input and Output assertions:

v Program correctness depends on formal statement
v Formal statement has 2 parts:
è Input assertion
è Output assertion
v Input assertion: Specify any condition placed on the values of the
input variable
v Output assertion: Produce for input data that satisfies the input assertion.

(x=q * y+r) ^ (r<y)

v The output assertion can written as logical notation

(x=q * y + r) ^ r<y

^ - Logical connectivity “and”
Q - Quotient
R - remainder x
divided y
[3] Implication and Symbolic execution

v Problem can be verified by a set of implication.

v General form of implication.

P Q

P à assumption

Q à conclusion








v If assumption and conclusion are same then true else if conclusion is true then true.

v Symbolic execution replaces all input data values into symbolic value and all
arithmetic operations into algebraic manipulation of symbolic expressions.
[4] Verification of straight line program segments:
[5] Verification of program segments with branches:
[6] Verification of program segments with loops:

8. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
8






















ENGINEERING











XAVIER
THE EFFICIENCY OF ALGORITHMS
v This is possible by only by giving specific response regarding to the characteristics of a problem.
v Efficiency lies on design, implementation and analysis of algorithms
v CPU and internal memory efficiency helps to improve algorithm efficiency.
v Computer resources are needed to complete the task of a algorithm.
v Always aware to design a algorithm which was more economical

[1] Redundant Computations:

v Redundant computation leads to inefficiency.
v When it occurs inside for loop or any other loops, it will be executed many times.
That leads more serious.
v Repeatedly recalculating same set of statements remains constant.
v Unnecessary multiplications and additions should be removed.




Redundancy inside the inner loops should be eliminated.
[2] Referring array elements:

v Redundancy easily creeps into array processing.

v Version 1 is not more efficient because of condition a[i]>a[p].

v The condition a[i]>a[p] need only one memory reference.

9. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021
9












X











3] Inefficiency due to late termination
v The inefficiency will occur if the algorithm terminates late.
v Late in-sense, suppose after achieving the goal the other data also visited.
v Example: Alphabetical (linear) search
In linear search each data is visited and if target achieved the program
terminates. If it does not terminate then occur inefficiency.
Version 1 terminates after visiting complete list of
items. Version 2 terminates once the target is obtained.
[4] Early detection of desired output conditions
v Inefficiency sometimes involved due to early detection of desired output conditions.
v This early detection of desired output condition leads to termination problem
v Due to the nature of input the output condition met early before termination
condition met.
v This will happen when i/p list is in sorted order.
[5] Trading storage for efficiency gains
v To speed up an algorithm, always include least number of loops.
v One loop to do one job is better. This is like one variable hold one value.
v Trade between storage and efficiency improve performance.
v Save some intermediate results to avoid unnecessary testing.
v Always use less memory space algorithm to improve efficiency.
The Analysis of algorithms
v Every one follow algorithm which gives good solution.
v Good solution to a problem is always appreciable.
v Good solution should be quantitative or qualitative.
v The solution should be more economical.
v Economical in terms of human as well as system.
Good algorithm qualities and capabilities

10. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

· They are simple but powerful and general solution.
· Easy to understood and clear in implementation without tricky.
· Easily modified if needed.
· Correct for clearly defined situations.
· Able to understand on number of levels.
· Economical in terms of time, storage and peripherals.
· Documented clearly that anyone can understand.
· Must machine independent.
· Used as sub procedure for other problems.
· The solution must please, satisfy and made to feel proud to its designer.
Quantitative measures give the way to predict the performance of an algorithm and can
be comparing with other algorithm of same problem.


1. Exchanging the values of two variables
Problem:
Given two variables a and b exchange the values and assigned to them.
Algorithm Development:
Starting Configuration :( initial state)
Let a = 300 and b = 750
Target Configuration :( required state)
a = 750 and b= 300
Using the assignment operator we change the values of the variable.
Now with the following two statement we change the values of a and b.
a = b step-1
b = a step -2
after step-1 the value of a becomes
a = 750
after step-2 the value of b becomes
b = 750. (because present value of a is 750)
so we need different logic for swap a and b.
The new logic is
New value of a is assigned by old value of b.
And
New value of b is assigned by old value of a.
To do this we need third temporary variable t
t = a; step 3 (store t with the old value a that is t = 300)

11. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

a = b step 4. (assign a with old value of b that is a = 750).
b = t step 5(assign b with old value of a that is b= 300 through t)
Program in c:
void main()
{
int a, b , t;
a = 300;
b = 750;
printf(“the values of a and b before exchange \n”);
printf(“a is %d and b is %d\n”);
t = a; // t =300
a = b ; // a = 750
b =t ; // b = 300
printf(“the values of a and b after exchange \n”);
printf(“a is %d and b is %d\n”);
}
2. Counting
Problem:
Form the given set of values to make the count of values which meet the specified criteria. Example
from the given set students marks to count the no of pass where mark is greater than 50.
Algorithm development:
Suppose the following are the given set of marks.
60 , 50 , 35 , 46 , 80
Initially present count is 0.
If mark is >= 50 current count = previous count + 1 otherwise no change in current count.
Mark present count current count
60 0 1 (60 >=50)
50 1 2 (50 >=50)
35 2 2 (No change because 35 < 50)
46 2 2 (No change because 46 < =50)
80 2 3 (80 >=50)

12. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

In the above example if mark is greater than or equal to 50 current is increased by 1 using the following
formula. current count = previous count + 1 . step -1
if you closely examine every successive steps current count in the first step becomes the present count of
the next step.
This can be written by
previous count = current count. Step -2.
So we replace the current count of step -2 by step1 current count (previous count + 1)
We get
current count = current count + 1.

C Implementation.
void main()
{
int n , m, count=0;
printf (“enter the no o f marks to be processed\n”);
scanf(“%d”,&n);
for(int i = 1;i<=n;i++)
{
printf(“enter the i th mark %d\n”);
scanf(“%d’,&m);
if(m >= 50)
count = count + 1;
}
printf(‘the number of students passed is %d”, count);
}
3. Summation of Set of N Numbers.
Problem:
Given a set of N numbers (N>=0) design an algorithm to add these numbers and return the sum.
Algorithm development:
Computer is a device capable of adding two numbers at a time.
First it receive first number a and receive second number b and add this number and produce the sum.
To add set of three numbers we write the expression as x =20 + 35 + 45. (1)

13. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

It add 25 and 35 produce 55 and add it with 45 to produce the resultant sum 100.
But the limitation of expression 1 is it add only three constants.
To add any three values it can be modified as x = a + b + c (2)
But again there is a limitation that is it can add only three values.
To add n values the general equation is
S = a1 + a2 +a3+…….+an (3)
The system is capable of adding only two numbers at a time. The expression 3 can be implemented with
the following steps.
S = a1 + a2 step -1
S =S + a3 step -2
S = s + a4 step -3
S = s + a5 step -4

S = s + an step n-1
In general it can be written as
S = s + ai+1 step i
Initially s is assigned by 0.
The process is implemented with iteration.
C Implementation:
void main()
{
int a, sum=0 , n;
printf (“enter the no of numbers to be summed\n”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
printf (“enter the %d number to be added\n”,i);
scanf(“%d”,&a);
sum = sum + a;
}
printf (“the sum is %d\n”,sum);
}

14. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

4. Factorial Computation:
Problem:
Given a number n , compute the factorial of n.(n! where n >=0)
Algorithm development:
In general n! = 1 * 2 * 3 * …….* n-1 * n
and 0! = 1.
So by definition
0! = 1
1! = 1 * 1
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4.
With the above example the n! is written as
n! = n * (n-1) ! (n >=1) - 1
using the above formula we can write first few factorial as
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3 !
To compute n! ( for example 4!) we start p = 1(0!)
p= 1
p = p * 1
p = p * 2
p = p * 3
p = p *4 (4!)
p = p * n.
The above sequence can be implemented with iterative construct.
C Implementation:
void main()
{
int n, fact = 1, i;

15. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

printf(“enter the integer value for which factorial value to be computed\n”);
scanf(“%d” , &n);
for(i = 1;i<=n;i++)
{
fact = fact * i;
}
printf(“the factorial of n = %d is %d “, fact);
}

5. Generation of Fibonacci sequence
Problem:
Generate the Fibonacci Sequence of n terms where n >= 1
Ex : 0 ,1,1,2,3,5,8,13 ……………………n.
Algorithm Development:
General formal for generation of Fibonacci sequence is
New term = preceding term + term before preceding term
Example
13 ( New term) = 8 (preceding term) + 5 ( term before preceding term)
Let start
a = 0 ( a - term before preceding term)
b = 1 ( b - preceding term)
c = a+ b = 1( new term)
to generate the next computation we must ensure that
(i) new term ( c ) assume the role of preceding term
(ii) the current preceding term become the term before preceding term(b)

that is
a = b
b = c

c Implementation:
void main()
{
int a,b,c,,n;
printf(“enter the no terms”);
scanf(“%d”,&n)
a = 0;

16. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

b = 1;
printf(“%d %d”,a,b;
for(int i=3;i<=n;i++)
{
c= a + b;
printf(“%d”,c);
a = b;
b= c;
}
}



Unit -2
1. Finding the Square Root of a Number.
Problem:
Given number m device an algorithm to compute its square root.
Algorithm Development:
For Given m the square root n satisfies the following condition
n * n = m
for example m = 25 then n = 5
that is
5 * 5 = 25.
Using the following notation we can find the square root.
1. Choose the number n less than the number to m we want the
square root.
2. Square n and if n is greater than m decrease n by 1 and repeat
step 2 else
3. Increase n by 0.1 and again compute the guess than m.

Let us devices a better algorithm by example.
Suppose we want to find the square root of 36.
First we choose our initial guess 9.

9
2
= 81 which is greater than 36.
Now divide 36 by 9 which gives 4.
Now
4
2
= 16 which is less than 36.
So we conclude that the square root of 36 is in between 9 and 4.
B y taking average of 9 and 4 we get (9 + 4) / 2 = 13/2 = 6.5.
Repeat the steps now
6.5
2
= 42.25 ( > 36)
Now divide 36 by 6.5 which gives 5.53

17. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

5.53
2
= 30.58 (<36)
Repeat the above steps
B y taking average of 6.5 and 5.53 we get (6.5 + 5.53) / 2 = 6.051.
So we can repeat we get 6 as the square root of 36.

We generalize this
g1 = m /2.
g2 = (g1 + (m/g1))/2
by looping in the next iteration
g1 = g2; That is g2 becomes the role of g1.

void main()
{
int m,g1,g2,sr;
printf(“enter the number for which square root is to be find\n”);
scanf(“%d”,&m);
g1= m /2;
g2 = m/2;
do
{
g1= g2;
g2 = (g1 + m/g1)/2
while(abs(g1-g2) > 0.00001);
}
sr = g2;
printf (the square root is %d” , sr);
}

2. The Smallest Divisor of an Integer

Problem:
Given an integer n device an algorithm that will find its smallest exact divisor other than one.
Algorithm development:
Let device to find the smallest divisor with an example. We choose 36 as a number for
which we find the smallest divisor.
The following are the complete set of divisor of 36.
{ 2,3,4,6,9,12,18}
As we know that each divisor divides the number with no remainder.
For example 4 divides 36 with no remainder and 9 as quotient.
Which means
36 / 4 = 9 and 36 / 9 = 4 which implies that 36/(9*4) = 1
Like wise
36 / 3 = 12 and 36 / 12 = 3 which implies that 36/(12*3) = 1

With this we see that

Smaller factor(s) Biggest factor(b)

2 is linked with 18
3 is linked with 12
4 is linked with 9
6 is linked with 6

s * b = n

18. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

we stop that
s= b that is s*s = n which conclude that it is not necessary to look the smallest divisor beyond its
square root.
We can improve the analysis by the example that n = 127. We consider only less that its square root
of 127 that is
2,3,4,5,6,7,8,9,10,11.
We know that all even numbers 2 is the smallest divisor and if a number is not divisible by 2 it also
not divisible by 4,6,8 and so on.
So we consider only 3,5,7,11.
So we start the divisor d = 3 using the steps d = d + 2 we stop either
n mod d = 0 where d is smallest divisor or d is greater than square root of 127 that is n.
c implementation:
void main()
{
int n , sd , sr,d;
{
printf(“enter the value for n for which smallest divisor has to find”);
scanf(“%d”,&n);
if(n % 2 = 0)
sd = 2;
else
{
d = 3 ;
sr = (int) sqrt(n);
while((n % d != 0) && (d < sr))
{
d= d + 2;
}
if (n % d == 0)
{
sd = d;
}
else
{
sd = 1;
}
}

printf(“the smallest divisor of % is %d “, n, sd”);
}
3. The Greatest Common Divisor of Two Integers
Problem:
Given two positive non-zero integer n and m design an algorithm to find their gcd.
Algorithm description:
The gcd of two integers is the largest integer that will divide exactly into the two integers with no
remainder. The exact divisor of a number is a another smaller number that divides the original number into
set of equal parts. For example the divisor 5 divides 30 in to 6 equal parts.
0 5 10 15 20 25 30

19. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

P1 P2 P3 P4 P5 P6

Where p1=p2=p3=p4=p5=p6 = 5
Now let us device an algorithm with example.
Suppose we find gcd of 30 , 18 which is x. n = 30 and m = 18.
The exact divisor x divides n , m into the segment of size x.
from the
above fig the two block matches in length AB(m) and exceeds in n by length BC. From observation the
part of the block BC also divides in x(gcd).
The greatest divisor of a single number is the number itself. But our problem is to find the greatest divisor
of a two number.
By example
1. Greatest divisor of 30 is 30.
2. Greatest divisor of 18 is 18 .
So no number greater than 18 is not the gcd for 18 and 30.
Next the segment BC is 12 (30-18) is to be divide by gcd.


Now we find gcd of 18 and 12 which is equal to the gcd of 30 and 18.
By observation 12 is not exact divisor of 18.
Now the segment BC is 6 (18-12) is to be divide by gcd.

20. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021


Now we find gcd of 6 and 12 which equal to the gcd of 30 and 18.
By observation 6 exactly divides 12 so gcd of 30 and 18 is 6.
For remainder we use mod function.
r = n mod n.
for the above example
r =30 mod 18 = 12.

r =18 mod 12 = 6

r =12 mod 6 = 0
C implementation:
void main()
{
int n , m , r , gcd;
printf(“enter the two integers for which gcd be find\n”);
scanf(“%d%d”,&n,&m);
do
{
r = n % m;
n=m;
m= r;
} while(r<>0);
gcd = r;
printf(“the gcd is %d”,gcd”);
}
Generating Prime Numbers

21. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

Problem:
Generating all the primes in the first n positive Integers.
Algorithm Development:
A prime Number is a positive integer that is exactly divisible only by 1 and Itself.
Ex:
2,3,5,7,11,13,17,19,23,29,31,37.
All the primes apart from 2 are odd.
For example to test 13 is prime
we divide 13 by 2,3,4,5,6,7,8,9,10,11,12.
If any the above number divides 13 , it is not prime.
In order to generate odd sequence the following is the formula
X= 1
X = x + 2
The following sequence generated
3,5,7,9,11,13,15,17, ………
So for we eliminate the numbers divisible by 2.
next we eliminate the numbers divisible by 3 and 5 so on.
First in the odd sequence with multiples of 3 is removed

In order generate the above pattern
We use the following formula
dx = abs(dx-6) initially dx = 4
To check x is prime or not we need not divide beyond the square root of x.
The following is the algorithm for generate prime numbers to n integers.

C Program:
void main()

22. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

{
int p,d,n;
int flag;
printf(“Enter the value of n up to which prime numbers are to be generated\n”);
scanf(“%d”,&n);
for(p=2;p<=n;p++)
{
flag = 1;
for(d = 2;d<p;++d)
if(p%d==0)
flag = 0;
if(flag) printf(“%d”,p);
}
}

Generation of Pseudo Random Numbers
Problem:
Use the linear congruential method to generate uniform set of pseudo random numbers.
Algorithm development:
The Sequence of random numbers are predictable in advance is referred as pseudo random numbers.
They are many methods to generate pseudo random numbers.
One of the method is Linear Congruential Method.
It is based on the following expression.
Where a, b, m is called multiplier, incremental and modules.
The above parameter should satisfy the following criteria.
1. All are greater than 0 and m should be greater than a , b,
xn
2. x should be 0 <= x <= m.
3. m should be greater than the length of random sequence
required and the computation should be done without any round off.
4. The parameter a depends on m. if m is power of 2 then a
should satisfy a mod 8 = 5 and if m is power of 10 then a should satisf a mod 200 = 21.

23. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

5. The parameter a should greater than

6. The parameter b should be odd and not divisible by 5.
C Implementation:
int main()
{
int a,b,m,x;
m = 4096;
scanf(“%d”,&x);
b = 853;
a = 109;
x = ((a*x)+b)%m);
printf(“%d”,x);
}



Computing the nth Fibonacci number
Problem:
Given a number n generate the n’th member of the Fibonacci sequence.
Algorithm development:

The first few numbers of Fibonacci sequence is

24. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

generalize.

To generate

25. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021





So

When k = 1
fn = f2n+1
fn+1 = f2n+1 + f2n
when k = 0

26. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

fn = f2n
fn+1 = f2n+1
The following the algorithm for the 10 the Fibonacci number.
N=10
A[4] = {1,0,1,0}
For k = 3 to 1 do
fn+1
2
= fn+1 * fn+1
f2n = fn+1
2
+ fn * fn
If a[k] = 0 then
fn = f2n
fn+1 = f2n+1
else
fn = f2n+1
fn+1 = f2n+1 + f2n
end
end
result = fn
end



Unit – 3
ARRAY TECHNIQUES
1. Array order reversal
Problem:
Rearrange the elements of an array so that they appear in reverse order.
Algorithm development:

27. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021



We start with i = 1 and exchanged with n –i+1 and each step i is incremented by 1.

Each exchange can be achieved by the following mechanism.

Implementation in C Program:
void main()
{
int i , r,t,n;
int a[7] = {1,2,3,4,5,6,7};
n = 6;
r= n/2;
for(i=0; i<=r;i++)
{

28. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

t = a[i];
a[i] = a[n-1-i+1];
a[n-1-i+1] = t;
}
for(i=0;i<=7;i++)
{
prinf(“%d”,a[i]);
}
}
2. Array counting or Histogramming


First all location are initialized with 0 as a count.
When new mark is entered the corresponding location content (mark as a index) is incremented by
one(count).
For example mark 57 is entered
a[57] = previous count at a[57] +1

29. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

in general a[m] = a[m] + 1.
C implementation :
void main()
{
int i , m , n;
int a[100];
for(int i = 0;i<=100;i++)
{
a[i] = 0;
}
printf(“enter the no of students\n”);
scanf(“%d”,&n);
for(i=0;i<=100;i++)
{
scanf(“%d”,&m);
a[m] = a[m] + 1;
}
for(i=0;i<=100;i++)
{
printf(“%d”,a[i]);
}
getch();
}

3. Finding the maximum number in a set.
Problem:
Find the maximum number in a set of n numbers.
Algorithm development:
First assume the first number is the maximum number and store it as a temporary maximum
Then compare the temporary maximum with the second number. There are three possible case
1. The second number is lesser than temporary
maximum

30. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

2. The second number is equal to temporary
maximum
3. The second number is greater than temporary
maximum
For case 1 and 2 there is no change the temporary maximum and compare it the third number.
For case 3 second number is the temporary number. The same process continued.
The main algorithm is

C Implementation:

void main()
{
int a[100], max , i, n;
printf(“enter the value for n\n”);
scanf (“%d”, &n);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
}
max=a[0];
for(i=1;i<n;i++)
{
if(a[i]>max)
{
max=a[i];
}
}
printf(“the maximum is %d”,max)
}
4. Removal of duplicates in the Array.
Problem:
Remove all duplicates form an ordered array.




Algorithm development:

31. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021


The duplicate pair is

32. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021




C
Implementation:
void main()
{
int a[10]= {4,6,7,8,8,8,9,10,10,11};
int i,j;
i=1;
clrscr()
{
while(a[i-1] !=a[i])
{

33. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

i++;
}
if(a[i-1] !=a[i])
{
i++;
}
j=i-1;
while(i<10)
{
i++;
if(a[i-1] !=a[i])
{
j++;
a[j]=a[i];
}
for(i=0;i<j;i++)
{
printf(“%d\n”,a[i]);
}
}
5. Partitioning an Array

Problem:

Algorithm Development:
For example given array

34. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021


Based x=17 the partitioned array is

The elements on the left side less than 17 leave as it is . if it is greater than 17 it is exchanged with
the element which is less than 17. Likewise element on the right is greater than 17 leave as it is. If it is less
than 17 it is exchanged with the right element which is greater than 17.

35. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

C implementation:
void main()
{
int a[10]={28,26,25,11,16,12,24,29,6,10};
x=17;
int i,j,t;
i=0;
j=9;
while((a[i]<=x) && (i<j)) ++i;
while((a[j]>x) && (i<j)) --j;
if(a[j] >x) –j;
while(i<j)
{
t = a[i];
a[i]=a[j];
a[j] = t;
++i;
--j;
while((a[i]<=x) && (i<j)) ++i;
while((a[j]>x) && (i<j)) --j;
}

for(i=0;i<9;i++)
{
printf(“%d\n”,a[i]);
}
}
6 . Finding the K’th Smallest Element
Problem:

Algorithm development:
This problem is similar to array partition problem but x value is not known in advance. Here a value is
chosen randomly.

The k’th smallest value is present either in subset A or B. suppose the k’th smallest value is present in B ,
we completely ignore A and we partition only B . Now l’ becomes l. we repeat the partition process until
we find K’th smallest position.

36. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021




We choose x in a[k]’th position.
X= a[k];
While a[j] > x do j = j-1;
While a[i] < x do i = i+1;
C implementaton:
void main()
{
int a[10]={4,7,8,3,5,6,11,2,9,1};
int i,j,k,l,u,x,t;
scanf(“%d”,&k);
l=0;
u = 10-1;
while(l<u)

37. PROBLEM SOLVING TECHNIQUES (15UCAM101) DEPARTMENT OF COMPUTER APPLICATIONS 2018 - 2021

{
i=l;
j=u;
x=a[k];
while(a[i]<x)
{
i++;
};
while(a[j]>x)
{
j--;
};
while(i<j)
{
t = a[i];
a[i]=a[j];
a[j] = t;
++i;
--j;
while(a[i]<x)
{
++i;
}
while(a[j]>x)
{
--j;
}
}
if(i<k)
{
l=i;
}
if(i>k)
{
u=j;
}
}