PROBLEM SOLVING

1.1 INTRODUCTION

Computer problem solving is an iteractive process requiring much thought, careful planning, logical precision, persistance and attention to detail. At the same time, it can be challenging, exciting and satisfying experience with personal creativity.

PROGRAMS AND ALGORITHM

A program is a set of explicit and unambiguous instructions expressed in a programming language. It takes the input from the end user and manipulate it according to its instructions and produces an output which represents the solution to the problem.

An algorithm consists of a set of explicit and unambiguous finite steps which, when carried out for a given set of initial conditions, produce the corresponding output and terminate in a finite time.

1.2 PROBLEM SOLVING ASPECT

The problem solving is recognized as a creative process which largely defines systematization and mechanization.

The various aspects of problem solving are :

1. Problem definition phase

2. Getting started on a problem

3. The use of specific examples.

4. Simulation among problems.

5. Working backwards from the solution.

6. General problem - solving strategies.

1.2.1 Problem definition phase

The problem definition phase deals with "What must be done rather than how to do it". That is, the user tries to extract a set of precisely defined tasks from the problem statement.

1.2.2 Getting Started on a Problem

There are many ways to solve most problems and also many solutions to most problems, which makes the job of problem solving difficult to recognize quickly which paths are likely to be fruitless or productive. Hence the programmer do not have any idea where to start on the problem, even after the problem definition phase. They became concerned with details of the implementation before they have completely understood or worked out an implementation (i.e.,) independent solution. So it is better not to be concerned about detail in the beginning of the problem solving phase itself.

1




Data Structures 1.1


1.2.3. The use of specific examples

A useful stragegy is to use some heuristics to try to get a start with the problem. One way is to pick a specific example to the general problem that we wish to solve and try to workout the mechanism that will allow us to solve this particular problem. It is usually much easier to work out the details of a solution to a specific problem because the relationship between the mechanism and the particular problem is more clearly defined.

1.2.4 Similarities among problems

Another way to make a start on a problem is to bring as much past experience as possible to bear on the current problem. Therefore it is always make an effort to be aware of the similarities among problems. The more experience one has the more tools and techniques one can bring to bear in tackling a given problem. Sometimes, it leads to discovering desirable or better solution to a problem.

The important skill in problem solving is the ability to view a problem from a variety of angles. Once this skill has been established, then it should be possible to get started on any problem.

1.2.5 Working backwards from the solution

We can also start a problem by working backwards to the starting conditions. Documentation as we go along the various steps and explorations made allow us to systematize our investigation and avoid duplication of effort. The most critical thing of all in developing problem solving skills is its practice.

1.2.6 General problem solving strategies

There are a number of general and powerful computational strategies that are repeatedly used in various guises in computing science.

They are:

Divide and conquer

Dynamic programming

Greedy search

Back tracking

Branch and Bound Techniques.

The most widely known and most often used of these principles is the divide and conquer strategy, which divides the original problem into two or more sub-problems.

Another general problem solving strategy is Dynamic programming, which builds of intermediate steps. The techniques of greedy search, back tracking and branch-and-bound evaluations are all variations on the basic dynamic programming idea.

1.3 TOP-DOWN DESIGN

Top-down design or stepwise refinement is a strategy that can apply to take the solution of a computer problem from a vague outline to a precisely defined algorithm and program


Data Structures 1.2


implementation. It allows us to build our solutions to a problem in a stepwise fashion.

1.3.1 Breaking a problem into subproblems

The process of repeatedly breaking a tasks down into subtasks and then each subtask into still smaller subtasks and continue until we end up with subtasks that can be implemented as program statements. The larger and more complex the problem, the more it will need to be broken down to be made it tractable. This makes the implementation task as simple as possible.

Fig. 1.3 Breakdown of a problem into substasks

1.3.2 Choice of suitable data structure

All programs operate on data and consequently the way the data is organised can have a effect on every aspect of the final solution.

An appropriate choice of data structure is usually leads to a simple, transparent and efficient implementation. Data structures and algorithms are usually linked to one another. A small change in data organisation can have a significant influence on the algorithm required to solve the problem.

Setting up data structures are based on the questions such as

1. Can it be easily searched ?

2. Can it be easily updated ?

3. Whether the data structure involve the excessive use of memory.

4. Can any one of the common data structures such as array, queue, set, stack, tree, graph,


Data Structures 1.3


list be used to formulate the problem ?

5. Will it reduce the amount of computation to find the intermediate results, which is based on the way in which it is arranged.

1.3.3 Construction of loops

To construct any loop, we must take three things in account. They are

Initial conditions - that apply before the loop begins to execute

Invariant relation - that apply after each iteration of the loop.

Termination condition - under which the iterative process must terminate.

1.3.4 Establishing initial conditions for loops

To establish the initial conditions for a loop set the loop variables to the values that assumes to solve the smallest problem associated with the loop. For example, to find the sum of a set of numbers in an array using an iterative construct, the loop variables are i the array and loop index, and s the variable for accumulating the sum of array elements.

The smallest problem in this case is to find sum of zero numbers which is zero and so the initial values of i and s must be zero.

1.3.5 Finding the iterative construct

After finding the smallest problem, the next step is to extend it to the next smallest problem. i.e., to get the solution for i = 1, we build on the solution to the problem for i = 0. Similarly from (i - 1)th case, we get the solution for ith case. (where i1).

Example i : = 0

s : = 0

while i < n do // `n' represents number of iterations

begin

i : = i + 1;

s : = s + a[i]

end

1.3.6 Termination of loops

The loops can be terminated in a number of ways. In general the termination conditions are dictated by the nature of the problem. The simplest condition for terminating a loop occurs when the number of iterations to be made is known in advance. For example, In Pascal the for-loop can be used as

for i : = 1 to n do

begin

.......


Data Structures 1.4


.........

end

This loop terminates unconditionally after n iterations.

The while-loop in Pascal can be used as

while (x > 10) do

begin

........

........

end

This loop terminates when conditional expression becomes false.

1.4 IMPLEMENTATION OF ALGORITHMS

The implementation of an algorithm that has been properly designed in a top-down fashion should be an almost mechanical process. If an algorithm has been properly designed the path of execution should flow in a straight line from top to bottom which is much easier to understand and debug.

1.4.1 Use of procedures to emphasise modularity

Modularization of program assist for both the development of the implementation and the readability of the main program. This allows to implement a set of independent procedures to perform specific and well defined tasks. In applying modularization in an implementation, the process is not taken too far, to a point at which the implementation again becomes difficult to read because of fragmentation.

1.4.2 Choice of variable names

Choosing appropriate variable and constant names makes programs more meaningful and easier to understand. Each variable should only have one role in a given program.

1.4.3 Documentation of programs

Another useful documenting practice that can be employed is to associate a brief but accurate comment with each procedure. A good programming practice is always to write programs so that they can be executed and used by other people unfamiliar about the program. This means that the program must specify during execution exactly what responses it requires from the user.

1.4.4 Debugging programs

In implementing an algorithm it is very important to carry out a number of tests to

ensure that the program is behaving correctly according to its specifications.

To make the task of detecting logical errors, a set of statements that will print the

information at strategic points in the computation is build into the program.

The simplest way to implement this debugging tool is to have a Boolean variable

(eg. debug) which is set to true when the debugging output for the program is required.


Data Structures 1.5


Each debugging output can then be parenthesized in the following way:

if debug then

begin

writeln (....)

.......

.......

end

A good rule to end follow when debugging is not to assume anything.

1.4.5 Program testing

In attempting to test whether or not a program will handle all variations of the problem it was designed to solve that it will cope with the limiting and unusual cases. We might check whether the program solves the smallest problem, whether it handles the case when all data values are the same and so on. Wherever possible, input and output assertions should be accompanied to the programs. We have to build the program that informatively respond to the user when it receives input conditions it was not designed to handle.

A good rule to follow is that fixed numeric constants should only be used in programs for things like the number of months in a year and so on.

1.5 PROGRAM VERIFICATION

The cost of software development is extremely high. Also, it may cause serious changes on sensitive data if the program doesn't work correctly. Therefore, it is essential to verify whether the program works correctly or not.

A better method of program verification is to verify the individual modules as it is completed rather than postponing the verification process to the end.(i.e.,) after integrating the modules.

The various phases in the program verifications are

1. Input and output assertion

2. Computer model for program execution

3. Implications and symbolic executions.

4. Verification of straight-line program segments

5. Verification of program segments with branches

6. Verification of program segments with loops

7. Verification of program segments that employ arrays

8. Proof of termination.

1.5.1 Input and Output assertions

The input and output assertion is the first and foremost step that has to be taken inorder to prove the correctness of a program. It provides a formal statement which consists of specifications interms


Data Structures 1.6


of the variables.

The formal statements gives two assertions

(a) An input assertion

(b) An output assertion

Input assertion

It specifies any constraints that are placed on the value of the input variables used by the program.

Example

In the division operation let us consider `d' as the divisor. Hence it is clear that d cannot have the value 0. The input assertion is therefore d0.

Output assertion

It specifies the result symbolically that the program is expected to produce for the input data which satisfies the input assertion.

Example

In calculating the quotient q and the remainders x from the division of `a' by `b', then the output assertion is as (a = q * b + r) (r < b)

where `^' represents the logical AND operation.

1.5.2 Compute Model for program execution

A program may have a variety of execution paths leading to successful termination. For a given set of input conditions only one of these paths will be followed. The progress of a computation from specific input conditions through to termination can be thought of as a sequence of transitions from one computation state to another. Each state is defined by the values of all variables at the corresponding point in time.

A state transition model for program execution provides a foundation on which to construct correctness proof of algorithms.

1.5.3 Implications and Symbolic execution

Verifying a program can be formulated as a set of implications which must be shown to be logically true.

The general form of implication is

P Q

P - Assumption

Q - Conclusion


Data Structures 1.7


P Q PQ

True True True

True False False

False True True

False False True

Fig. 1.5(a) Truth Table defining implication

In order to show that these implications or propositions are logical true, it is necessary to use the technique of symbolic execution.

In symbolic execution, all input data values are replaced by symbolic values and all arithmetic operations on numbers are translated into algebraic manipulation of symbolic expression. This enables us to transform the verification procedure into providing that the input assertion with symbolic values substituted for all input variables implies the output assertion with final symbolic values substituted for all variables.

Step Normal Execution Symbolic Execution

Input values : x = 3, y = 1 Input values : ,

1. X : = x - y x = 3 - 1 = 2 X : = x - y x =

2. Y : = x + y y = 2 + 1 = 3 Y : = x + y y = () + =

3. X : = y - x x = 3 - 2 =1 X : = y - x x = ((() + ) -

()) = .

Fig. 1.5(6) Normal and Symbolic execution for exchange mechanism.

Consider the following program segment labelled with input and output assertions :

A readln (x, y);

{assert ; true)

x : = x - y;

y : = x + y;

x : = y - x;

B {assert }

where xo and yo refer to the initial values of x and y respectively.

Fig. 1.5(b) Exchange Mechanism program segment




Data Structures 1.8


1.5.4 Verification of Straight - line program segments

Let us consider the exchange mechanism program segment.

The verification condition is ;

VC (A - B) : true {} on substitution of initial and final values of all variables, we get :

VC (A - B) : true (() + ) - ())

= (() +) =

The conclusion part of the verification condition an be simplified to yield and which is true and so the implication is true.

[Note : VC (A - B) refers to the verification condition over the program segment A to B. Therefore apply the resultant of the program A to the program segment B.

(i.e) Symbolic execution of A is resulted as

x = , y = [initial values]

x = ((-) +) - (-) [Final Value]

y = (-) + ) [Final Value]

program segment B is {}.

1.5.5 Verification of program segments with branches

To handle program segments that contain branches, it is necessary to set up and prove verification condition for each branch seperately. Let us consider the following program segment that ensures x is less than or equal to y.

read ln (x, y)

A {assert PA : true}

if x > y then

begin

t : = x;

x : = y;

y : = t;

end.

B {assert PB : ((x < = y)(x = xo y = yo)) ( x = yo y = xo);

In general, the propositions that must be proved for the basic if construct are


Data Structures 1.9


where CA is the branch condition.

1.5.6 Verification of Program segments with loops

Problems using program segments with loops can be solved with a loop invariant.

A Loop invariant is a property that captures the progressive computational role of the loop while at the same time remaining true, before and after each loop traversal irrespective of how many times the loop is executed. Let us consider the following single - loop program structure as model.

A {input assertion PA}

B {loop invariant IB}

while loop - condition do

begin

end

C {Output assertion PC}

The steps to be employed to verify a loop segment are.

Step 1: We have to show that the loop invariant is initially true. This can be done by setting up a

verification condition,

VC (A - B) for the program segment from A to B.

Step 2 : To show that the loop invariant is still true after the segment of program within the loop has

been executed. To do this, set up a verification condition as VC (B - B).


Data Structures 1.10


The loop invariant with initial values of variables set, together with condition for loop

execution , implies the truth of the loop invariant with final values of variables.

(i.e) .

Step 3 : The final step is verifying a loop segment, it is necessary to show that, the loop invariant

together with the negation of the loop entry condition, implies the assertion that applies on

existing form of the loop. The verification condition for this care is VC (B - C). The

corresponding proposition will be :

1.5.7 Verfication of program segments that employ arrays

The idea of symbolic execution can be extended to simpler examples that employ arrays by accounting symbolic values of all array elements.

Let us consider the program segment which finds the position of the smallest element in the array.

A {assert PA : }

i : = 1;

p : = 1;

B

while i < n do

begin

i : = i + 1;

if a[i] < a [p] then p! = i

end

C

Assume the initial values of a[1], a[2], ........, a[n] as and the initial value of n as , then the symbolic execution to check the verification condition is given as :

1.5.8 Proof of termination

To prove that a program terminates, it is necessary to show that every loop in the program terminates in a finite number of steps. Consider, for example, the for - loop ;


Data Structures 1.11


for i = 1 to n do

begin

...

...

end

when n is positive and finite, the loop is guaranteed to terminate because, with each iteration, the number of steps to the termination condition being satisfied is reduced by at least one. This reduction can only be carried out a finite number of times and so the loop must terminate.

The proof of termination is much more subtle and elusive for loops which has any one of the following two situations.

* When there is no single variable that is monotonically progressing towards the termination

condition.

* An arithmetic combination of two or more variables makes progress towards termination with

each iteration.

The problem of proving loop termination can often be approached by associating another expression in addition to the loop invariant, with each loop.

The expression , should be chosen to be a function of the variables used in the loop. It should always be non - negative and the value is decreased with each loop iteration.

To verify the loop structure perform the following steps.

Step 1 : Show that the loop invariant IB, together with condition for loop execution CB, implies that

the value of the expresion is greater than zero.

(i.e)

The condition becomes an invariant of the loop.

Step 2 : Show that the loop invariant IB, together with the condition for loop execution, CB, implies

that the value of the expression before execution is strictly greater than its value

after loop execution. (i.e) for a loop B

1.6 THE EFFICIENCY OF ALGORITHMS

The Efficiency considerations for algorithms are inherently tied in with the design, implemenation and analysis of algorithms. The resources used by the algorithms are central processing unit (CPU) time and internal memory. So the efficiency of the algorithm lies with the economical usage of these resources.

Some of the suggestions to improve the efficiency of an algorithm in designing are

* Redundant computations

* Referencing array elements

* Inefficiency due to late termination


Data Structures 1.12


* Early detection of desired output conditions.

* Trading storage for efficiency gains.

1.6.1 REDUNDANT COMPUTATONS

The effects of redundant computations are most serious when they are embedded within a loop that must be executed many times which utilizes unnecessary memory space. The most common mistake using loops is to repeatedly recalculate part of an expression, that remains constant throughout the entire execution phase of the loop. For example

S : = 0; K : = 2;

for i = 1 to n do

begin

S : = k * k * k + i ;

end

The unnecessary multiplication can be removed by precomputing a constant K3 before executing the loop.

S : = 0 ; K : = 2 ;

K3 : = k * k * k ;

for i = 1 to n do

begin

S : = K3 + i ;

end

1.6.2 Referencing array elements

Let us consider for example, the two versions of an algorithm for finding the maximum.

Version (1)

for i = 2 to n do

if a [i] > a [p] then

max : = a [p]

version (2)

max : = a[1];

for i = 2 to n do

if a[i] > max then

max : = a[i];


Data Structures 1.13


The version (2) implementation would normally preferred because the condition test a[i] > max is more efficient because it uses the variable max which requires only one memory reference instruction, whereas the use of variable a[p] requires two memory references.

1.6.3 Inefficiency due to late termination

Inefficiencies can come into an implementation due to late termination.

Let us consider an example to search an alphabetically ordered list of names for some particular name linearly.

Suppose we were looking for the name `Ram', then as soon as we had encountered a name that occurred alphabetically later than Ram, (ie) Rekha, we would no need to proceed further.

The inefficient implementation could have the form :

while (namesought < > current name and not end of file) do

get next name from list

A more efficient implementation would be :

while (namesought > current name and not end of file) do

get nextname from list.

1.6.4 Early detection of desired output conditions

Due to the nature of the input data, the algorithm establishes the desired output condition before the general conditions for termination have been met.

For example, a bubble sort might be used to sort a set of data that is already almost in sorted order. If there have been no exchanges in the current pass, the data must be sorted and so early termination can be applied.

1.6.5 Trading storage for efficiency gains

Storage and efficiency is often used to improve the performance of an algorithm.

One strategy that sometimes used to speed up an algorithm is to implement the algorithm using the least number of loops, which makes the program much harder to read and debug. It is therefore usually better to have one loop for one job.

1.7 THE ANALYSIS OF ALGORITHMS

The analysis of algorithms is made considering both qualitative and quantitative aspects to get a solution that is economical in the use of computing and human resources which improves the performance of an algorithm. A good algorithm usually possess the following qualities and capabilities.

1. They are simple but powerful and general solutions.

2. They are user friendly

3. They can be easily updated.

4. They are correct.


Data Structures 1.14


5. They are able to be understood on a number of levels.

6. They are economical in the use of computer time, storage and peripherals.

7. They are well documented.

8. They are independent to run on a particular computer.

9. They can be used as subprocedures for other problems.

10. The solution is pleasing and satisfying to its designer.

1.7.1 Computational Complexity

The computational complexity can be measured in terms of space and time required by an algorithm.

Space Complexity

The space complexity of an algorithm is the amount of memory it needs to run the algorithm.

Time Complexity

The time complexity of an algorithm is the amount of time it needs to run the algorithm.

The time taken by the program is the sum of the compile time and run time.

To make a quantitative measure of an algorithm's performance, the computational model must capture the essence of the computation while at the same time it must be divorced from any programming language.

1.7.2 Asymtotic Notation

Asymtotic notations are method used to estimate and represent the efficiency of an algorithm using simple formula. This can be useful for seperating algorithms that leads to different amounts of work for large inputs.

Comparing or classify functions that ignores constant factors and small inputs is called as asymtotic growth rate or asymtotic order or simply the order of functions. Complexity of an algorithm is usually represented in O, o, , notations.

Big - oh notation (O)

This is a standard notation that has been developed to represent functions which bound the computing time for algorithms and it is used to define the worst case running time of an algorithm and concerned with very large values of N.

Definition : - T(N) = O(f(N)), if there are positive constants C and no such that T(N)Cf(N) when Nno


Data Structures 1.15


Fig. 1.7(a) Big - oh notation T(N) O(F(N))

BIG - OMEGA NOTATION ()

This notation is used to describe the best case running time of algorithms and concerned with very large values of N.

Definition : - T(N) = (f(N)), if there are positive constants C and no such that T(N)CF(N) when Nno

Fig. 1.7(b) BIG - OMEGA NOTATION

BIG - THETA NOTATION

This notation is used to describe the average case running time of algorithms and concerned with very large values of n.


Data Structures 1.16


Definition : - T(N) = (F(N)), if there are positive constants C1, C2 and no such that

T(N) = O(F(N)) and T(N) = (F(N)) for all Nno.

Fig. 1.7 (c) BIG - THETA NOTATION

Little - Oh Notation (o)

This notation is used to describe the worstcase analysis of algorithms and concerned with small values of n.

Definition :

Basic Asymptotic Efficiency Classes

Computing Time Name

0(1) constant

0(log n) Logarithmic function

0(n) Linear

0(n2) quadratic

0(n3) cubic

0(2n) exponential

0(nlogn) n - log - n Logarithmic

n! factorial

1.7.3 WORST - CASE, BEST - CASE AND AVERAGE - CASE EFFICIENCIES

Worst - Case - Efficiency

The worst - case efficiency of an algorithm is its efficiency for the worst - case input of size n, which is an input of size n for which the algorithm runs the longest among all possible inputs of that size.


Data Structures 1.17


Best - Case Efficiency

The best - case efficiency of an algorithm is its efficiency for the best case input of size n, which is an input of size n for which the algorithm runs the fastest among all possible inputs of that size.

Average - Case Efficiency

The average - case efficiency of an algorithm is its efficiency for the random input of size n, which makes some assumptions about possible inputs of size n.

For example, let us consider sequential search

ALGORITHM

SequentialSearch (A[0...n-1],K)

// Input : An array A[0..n-1] and a search key k.

// Output : Returns the index of the first element of A that matches R or -1 if there are no matching elements.

while i < n and A[i] # k do

i i + 1

if i < n return i

else return - 1

Here, the best - case efficiency is 0(1) where the first element is itself the search element and the worst - case efficiency is 0(n) where the last element is the search element or the search element may not be found in the given array.

1.8 SAMPLE ALGORITHMS

PROBLEM 1 (a) :

Give two variables a and b, exchange the values assigned to them without using temporary variable.

INPUT : Given element a and b

OUTPUT : The value of b is stored in variable a and the value of a is stored in variable b.

ALGORITHM :

Swap (a, b)

a = a + b;

b = a - b;

a = a - b;

return a, b


Data Structures 1.18


PROBLEM 1 (b)

Give two variables a and b, exchange the values assigned to them using temporary variable.

INPUT : Given element a and b

OUTPUT : The values of a and b is swapped

ALGORITHM :

Swap (a, b)

t = a;

a = b;

b = t;

return a, b

PROBLEM 2 :

To check whether all the elements in a given array are distinct.

INPUT : An array A[0...n-1]

OUTPUT : Returns "true" if all the elements in A are distinct and "false" otherwise.

ALGORITHM :

UniqueElements (A[0...n-1])

for i = 0 to n-1 do

for j = i + 1 to n-1 do

if A[i] = = A[j]

return false

return true

PROBLEM 3 :

Make a count of the number of students on a particular subject who passed the examination scoring 50 and above.

INPUT : Number of Students (n)

OUTPUT : Total count of the students who passed in that subject.

ALGORITHM :

Passcount (n)

count = 0;

i = 0;

while (i < n) do

read (m)


Data Structures 1.19


if m > = 50 then

count = count + 1;

i = i + 1;

endwhile

return count

PROBLEM 4(a) :

To find the sum of a given set of numbers.

INPUT : An array A[0.. n - 1]

OUTPUT : returns sum of the elements in the given array.

ALGORITHM :

Sum1(A [0 .. n-1]

sum = 0;

for i = 0 to n -1 do

sum = sum + A[i]

return sum

PROBLEM 4(b) :

To find the sum of the squares of a given set of numbers.

INPUT : An array A[0.. n - 1]

OUTPUT : Returns the sum of squares of a given set of numbers.

ALGORITHM :

Sumsquare (A[0.. n - 1])

sum = 0;

for i = 0 to n - 1 do

sum = sum + A[i] * A[i];

return sum

PROBLEM 5(a) :

To compute factorial of a given number without recursion.

INPUT : The element n

OUTPUT : Returns factorial of the given element n.

ALGORITHM :

fact (n)

f = 1;


Data Structures 1.20


for (i = 1; i < = n; i ++)

f = f * i;

return f

PROBLEM 5(b) :

To compute factorial of a given number using recursion.

INPUT : A positive integer n

OUTPUT : Returns the factorial of the given element.

ALGORITHM :

fact (n)

if (n = = 0)

return 1

else

return fact (n - 1) * n

PROBLEM 6(a) :

Generate the Fibonacci series for first n terms.

INPUT : A positive integer n

OUTPUT : Prints Fibonacci series for n terms.

ALGORITHM :

Fibo (n)

F1 = -1; F2 = 1;

Fib = 0;

for i = 1 to n do

Fib = F1 + F2 ;

write Fib

F1 = F2;

F2 = Fib;

PROBLEM 6(b) :

Generate nth Fibonacci term using recursion.

INPUT : A positive integer n

OUTPUT : The nth Fibonacci number.


Data Structures 1.21


ALGORITHM :

Fibo (n)

if n 1

return n

else

return Fibo(n-1) + Fibo(n-2)

PROBLEM 7(a) :-

Design an algorithm to evaluate the function sin(x) as defined by the infinite series expansion.

INPUT : - Get the values for x and n

OUTPUT : - Sine function for the given terms is calculated.

ALGORITHM :-

Sineseries (x, n) // Get x in radians

S = 0;

term = x;

i = 1;

while i < = n do

S = S + term;

term = (term * x * x * (-1)) / ((i + 1) * (i + 2));

i = i + 2

write S;

PROBLEM 7(b) :-

The exponential growth constant e is characterized by the expression

Device an algorithm to compute e to n terms.

INPUT : - Get the values of n (no. of terms)

OUTPUT : - Sum of the exponential series for `n' terms is calculated.


Data Structures 1.22


ALGORITHM :-

EXPOSERIES (n)

i = 1;

e = 1;

f = 1;

while i < = n do

e = e + 1/f ;

f = f * i ;

i = i + 1;

write e ;

PROBLEM 8 :-

To sort the given set of numbers.

INPUT : - An array A[0..n - 1]of orderable element.

OUTPUT : - Array A[0..n - 1] sorted in ascending order.

ALGORITHM :-

Sort (A[0.. n - 1]

for i = 0 to n - 2 do

for j = 0 to n - 2 - i do

if A[j + 1] < A[j]

swap A[j] and A[j + 1]

PROBLEM 9 :-

To search a given element in the array using binary search non recursively.

INPUT : - An array A[0..n - 1]sorted in ascending order and a search key k.

OUTPUT : - An index of the array's element that is equal to K or -1 if there is no such element.

ALGORITHM :-

Binary Search (A[0 .. n - 1], K)

l = 0;

r = n - 1;

while lr do

m = (l + r) / 2

if K = A[M]


Data Structures 1.23


return m

else if K < A[M]

r = m - 1

else

l = m + 1

return - 1

PROBLEM 10 :-

Design an algorithm that accepts a positive integer and reverse the order of its digits.

INPUT : - A positive integer n.

OUTPUT : - A positive integer n with reversed order of its digits.

ALGORITHM :-

Reverse (n)

s = 0;

while n > 0 do

r = n % 10 ;

s = r + s * 10;

n = n/10;

write s

PROBLEM 11 :-

To compute the multiplication of two square matrices of order n.

INPUT : - Two n x n matrices A and B.

OUTPUT : - Matrix C = AB

ALGORITHM :-

MatrixMult (A[0..n - 1, 0.. n - 1], B[0..n - 1, 0..n -1])

for i = 0 to n - 1 do

for j = 0 to n - 1 do

C[i, j] = 0;

for k = 0 to n - 1 do

C[i, j] = C[i, j] + A[i, k] * B[k, j];

return C


Data Structures 1.24


PROBLEM 12(a) :-

To convert the given decimal number into its binary form.

INPUT : - A positive integer n.

OUTPUT : - A binary representation for the given decimal number n.

ALGORITHM :-

Decitobin (n)

C = 0;

while n > 0 do

r = n% 2;

a [i] = r;

n = n/2 ;

C = C + 1;

endwhile

for i = C - 1 to 0

write a[i];

PROBLEM 12(b) :-

To convert a binary number into a decimal number.

INPUT : - A positive integer in binary form.

OUTPUT : - decimal form of the given number is obtained.

ALGORITHM :-

Bintodeci (n)

q = n;

s = 0;

i = 0;

while q > 0 do

r = q % 10 ;

s = s + r * pow (2, i);

i = i + 1;

endwhile

write s ;


Data Structures 1.25


Questions

Part - A

1. Define an algorithm

2. Write an algorithm to swap two numbers.

3. Define the top - down design strategy.

4. What is meant by problem solving?

5. Mention some of the problem solving strategies.

6. What is divide and conquer strategy?

7. What are the steps involved in problem solving?

8. Write an algorithm to find the factorial of a given number.

9. List the types of control structures.

10. Define the worst case and average case complexities of an algorithm.

11. How do you debug a program?

12. What is program testing?

13. What is program verification?

14. Write down the various phases in the program verification.

15. Define space complexity and time complexity.

16. What are the qualities and capabilities of good algorithm.

17. How can you improve an efficiency of an algorithm in the design phase?

18. What do you mean by proof of termination?

19. What is O - notation?

20. Write an algorithm to find the sum of a set of numbers.

Part - B

1. Explain Top - down design strategy in detail.

2. Write down the algorithm for binary search.

3. The exponential growth constant e is characterized by the expression

. Device an algorithm to compute e to n terms.

4. Explain in detail the types of analysis that can be performed on an algorithm.

5. Write an algorithm to perform matrix multiplication and give the analysis for it.

6. Design an algorithm to compute the sum of the squares of n numbers.

7. Design an algorithm that accepts a positive integer and reverses the order of digits.

8. Write an algorithm to convert a decimal number to its corresponding octal form.


Data Structures 1.26