SYLLABUS CS301 DATA STRUCTURES

DATA STRUCTURES 3 1 0 100

UNIT I PROBLEM SOLVING 9

Problem solving – Top-down Design – Implementation – Verification – Efficiency

– Analysis – Sample algorithms.

–

UNIT II LISTS, STACKS AND QUEUES 8

Abstract Data Type (ADT) – The List ADT, Singly Linked list, Doubly linked list,

Circular linked list – The Stack ADT – The Queue ADT - Applications of Stack

and Queue.

UNIT III TREES 10

Preliminaries – Binary Trees – The Search Tree ADT – Binary Search Trees –

AVL Trees – Tree Traversals – Hashing – General Idea – Hash Function –

Separate Chaining – Open Addressing – Linear Probing – Priority Queues

(Heaps) – Model – Simple implementations – Binary Heap

UNIT IV SORTING 9

Preliminaries – Insertion Sort – Shellsort – Heapsort – Mergesort – Quicksort –

External Sorting

UNIT V GRAPHS 9

Definitions – Topological Sort – Shortest-Path Algorithms – Unweighted Shortest

Paths – Dijkstra’s Algorithm – Minimum Spanning Tree – Prim’s Algorithm –

Applications of Depth-First Search – Undirected Graphs – Biconnectivity –

Introduction to NP-Completeness

THEORY: 45 TUTORIAL: 15 TOTAL : 60

REFERENCE BOOKS

1. R. G. Dromey, “How to Solve it by Computer” (Chaps 1-2), Prentice-

Hall of India, 2002.

2. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, 2nd ed,

Pearson Education Asia, 2002. (chaps 3, 4.1-4.4 (except 4.3.6), 4.6,

5.1-5.4.1, 6.1-6.3.3, 7.1-7.7 (except 7.2.2, 7.4.1, 7.5.1, 7.6.1, 7.7.5,

7.7.6), 7.11, 9.1-9.3.2, 9.5-9.5.1, 9.6-9.6.2, 9.7)

3. Seymour Lipschutz, G A Vijiyalakshmi Pai, “Data Structures”,

Schaum’s Outlines, TMH, 2006.

4. Aho, J. E. Hopcroft and J. D. Ullman, “Data Structures and Algorithms”,

Pearson education Asia, 1983.

DATA STRUCTURES / CS1151 / II SEM CSE

UNIT –I PROBLEM SOLVING

Ø Problem solving.

Ø Top down design.

Ø Implementation of algorithm.

Ø Verification of algorithm.

Ø Efficiency and Analysis of algorithms.

Ø Sample algorithms.

CONTENTS
S.NO	2 MARKS / 25 QUESTIONS	PAGE NO
1	Define Data structures	8
2	Define program	8
3	Define algorithm	8
4	Mention how similarities among the problems are used in problem solving.	8
5	Mention some of the problem solving strategies.	8
6	What is divide and conquer method?	8
7	Where is dynamic programming used?	8
8	Define top-down design	9
9	Mention the steps involved in solving a problem using top-down design.	9
10	What is loop statement?	9
11	Mention the parts of a loop.	9
12	Write down the points to be considered in implementing an algorithm.	9
13	Name some problem solving strategies, which are variations of dynamic programming	9
14	What is program testing?	9
15	What is program verification?	10
16	Why do we have to go for program verification?	10
17	How will you find the efficiency of an algorithm?	10
18	How will you verify branches with segments?	10
19	How can you improve an efficiency of an algorithm in the design phase?	10
20	What are measures to be considered in analyzing algorithm?	10
21	Where can we apply the average and worst case measures?	10
22	Give some applications where the divide and conquer strategy is used.	10
23	What is the other name given for top-down design?	11
24	Why is the selection of data structures more important?	11
25	How do you correct the logical errors in a problem?	11

CONTENTS
S.NO	16 MARKS / 15 QUESTIONS	PAGE NO
1	1) Explain briefly about Problem definition phase. (OR) 2) Explain Problem-solving Technique.	12
2	3) Explain in detail about Top-down design technique. (Nov/Dec 2003) (OR) 4) Explain in detail about establishing the initial conditions, for loops, finding the iterative constructs, termination of loops with example. (OR) 5) How to construct a loop & establishing the initial conditions for loops and finding the iterative construct. (OR) 6) Draw the schematic diagram to represent the breakdown of a problem into subtasks employed in top down design and explain in detail.	14
3	7) Describe in detail about the implementation of algorithm. (OR) 8) Explain in detail about an algorithm implementation. (OR) 9) What are the steps involved in implementing an algorithm?	17
4	10) Write in detail about the program verification and verification of program segments with loops. (OR) 11) Explain in detail about Program verification with suitable example. (OR) 12) Explain in detail about Implications and symbolic execution & Input and output assertions. (OR) 13) Write in detail about the program verification and verification of program segments with loops and Verification of program segments with branches.	19
5	14) How to improve the efficiency of an algorithm and point out the mistakes in the loops with redundant computations? (OR) 15) How can you improve efficiency of an algorithm using the Referencing array elements? (OR) 16) Explain in detail about efficiency of an algorithm. (OR) 17) What are the steps involved to improve the efficiency of an algorithm?	22
6	18) How to calculate the time complexity for the best case, worst case and average case. Explain with example. (OR) 19) Explain in detail about the analysis of algorithm. (OR) 20) Explain in detail about the case behavior of an algorithm with example. 21) Explain in detail the types of analysis that can be performed on an algorithm (Nov/Dec2005)	25
7	22) Write an algorithm to find the largest element in an array. (OR) 23) Explain the concept of divide and conquer algorithm for the selection largest no. in an array. (April/ May 2004)	28
8	24) Write an algorithm to find real solutions of a quadratic equation.	28
9	25) Compare the algorithm for linear search. (Nov /Dec 2003)	29
10	26) Explain the procedures of Bubble sort. (April/May 2004)	29
11	27) Write an algorithm to find an element in an array using Binary search (OR) 28)Write down the algorithm binary search for searching x from an array a [1,n] and give stepwise execution. (May/June 2005) (OR) 29) Explain the binary search algorithm with suitable example. (April/May 2004)	30
12	30. Write an Algorithm to implement Matrix multiplication. 31.write an algorithm to perform matrix multiplication algorithm and analyze the same (Nov/Dec 2005)	31
13	32.Write an algorithm to find the Factorial value of N (OR) 33. Using the concept of recursion, write a pgm to factorial of a number.(Apr/May 2004)	31
14	34.Write an algorithm to find the sin(x) computation[x-x3]	32
15	35.Write an algorithm to Reverse the digits of an integer	32

2 MARKS Q& A

1. Define Data structures

The organization, representation and storage of data are called the data structure. Since all programs operate on data, a data structure plays an important role in deciding the final solution for the problem.

Ex: Stack, Queue, List, Array, etc…

2. Define program

Set of instructions to find the solution to a problem. It is expressed in a programming language in an explicit and unambiguous manner.

3. Define an algorithm (May/June 2005) OR

What is meant by algorithm? (April/May 2004)

Algorithm is a solution to problem independent of programming language. It consists of set of finite steps which, when carried out for a given set of inputs, produce the corresponding output and terminate in a finite time.

4. Mention how similarities among the problems are used in problem solving.

This method is used to find out if a problem of this sort has been already solved and to adapt a similar method in solving the problem. The contribution of experience in the previous problem will help and enhance the method of problem solving for the current problem.

5. Mention some of the problem solving strategies

The most widely strategies are listed below:

a. Divide and conquer

b. Binary doubling strategy.

c. Dynamic programming.

6. What is divide and conquer method?

What is divide and conquer algorithm? Give an example. (Nov/Dec2003)

The basic idea is a divide the problem into several sub problems beyond which cannot be further subdivided. Then solve the sub problems efficiently and join them together to get the solution for the main problem. E.g. Quick sort, Binary Search

7. Where is dynamic programming used?

Dynamic programming is used when the problem is to be solved in a sequence of intermediate steps. It is particularly relevant for many optimization problems. I.e., frequently encountered in operations research.

8. Define top-down design.

Top- down design is a strategy that can be applied to find a solution to a problem from a vague outline to precisely define the algorithm and program implementation by stepwise refinement.

9. Mention the steps involved in solving a problem using top-down design.

The steps involved in solving a problem using top-down design are,

a. Divide the problem into a set of precisely define sub tasks.

b. Decide the way of interaction between the sub tasks

c. Prove the correctness of the solution.

10. What is loop statement?

A loop statement is an iterative construct that is conditionally executed which includes input, output statements, computable expressions and assignments. They improve the efficiency of coding.

11. Mention the parts of a loop.

The construction of a loop includes three points.

a. Initial condition –to begin the loop to execute

b. Invariant relation – that must apply after each iteration of the loop

c. Terminal condition – to terminate the iterative process of the loop.

12. Write down the points to be considered in implementing an algorithm.

a. Choice of variable names

b. Use of procedures to emphasize modularity

c. Debugging of programs

d. Program verification

e. Program testing

f. Documentation of programs

13. Name some problem solving strategies, which are variations of dynamic programming.

Some of the problems solving strategies are,

a. Greedy strategy

b. Back tracking

c. Branch and bound.

14. What is program testing?

Program testing is a process to ensure that a program solves the smallest possible problem, when all the variables have the small value, the biggest problem, unusual cases etc.

15. What is program verification?

Program verification refers to the application of mathematical proof techniques, to verify that the results obtained by the execution of the program with arbitrary inputs are in accord with formally define output specifications.

16. Why do we have to go for 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.

17. How will you find the efficiency of an algorithm?

The efficiency consideration for algorithm is in inherently tied in with the design, implementation 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.

18. How will you verify branches with segments?

To handle the branches that appear in the program segments, it is necessary to set –up and prove verification conditions individually.

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

The following are the suggestions to improve the efficiency of an algorithm in designing.

a. Redundant computations.

b. Referencing array elements.

c. Inefficiency due to late termination.

d. Early detection of desired output conditions.

e. Trading storage for efficiency gains.

20. What are measures to be considered in analyzing algorithm?

The measures to be considered in analyzing algorithm are,

a. Worst case behavior b. Average case behavior.

21. Where can we apply the average and worst case measures?

(April/May 2004)

Both the measures can be applied to the time complexity as well as to the space complexity of an algorithm.

22. Give some applications where the divide and conquer strategy is used

The divide and conquer strategy is much useful in application like sorting, selection and searching algorithms.

23. What is the other name given for top-down design and explain?

Top-down design is also called as stepwise refinement. A project is decomposed into subprojects, and this procedure is repeated until the subtasks have become so simple that an algorithm can formulated as a solution.

24. Why is the selection of data structures more important?

The choice of data structure leads to a simple, transparent and efficient implementation. Inappropriate data structure for a problem will lead to difficulty in solving a problem. Hence the selection of data structure is more important.

25. How do you correct the logical errors in a problem?

By adopting a sequence of steps debugging can be made easier. The best way to avoid logical error in the program is to manually work out the logic of the program before actually developing it.

16 MARKS Q& A

1.1.Explain briefly about Problem definition phase.(OR)

1.2. Explain Problem-solving Technique.

Problem solving is a creative process, which needs systemization and mechanization

Data structure mainly specifies the following four things:

i) Organization of data

ii) Accessing method

iii) Degree of associatively

iv) Processing alternative for information

Then program is defined as the combination of algorithm and data structure.

Algorithm + Data structure = Program

Problem solving:

It can be defined as the creative process which defines systemization and Mechanization.

The problem solving contains the following components to solve the given problem

· Problem definition Phase

· Getting started

· Use of specific examples

· Similarities among problems

· Working backwards from the solution

· General problem solving technique.

Ø Problem definition Phase

The preliminary investigation may be thought of as the Problem definition Phase. An experienced Problem solver is going to solve the Problem only to find that he is either solving the wrong problem as he is solving just a very special case of what is actually required

Ø Getting started with a problem

These are a number of general and powerful computational strategies to a solve a problem

Probably the most widely known and most often strategy is divide and conquer strategy. The basic ideas with divide & conquer strategy. The basic idea with divide & conquer is to divide the original problem into two or more sub problems & the problem can be solved efficiency by the same technique

Most often used strategy is “Derived and conquer” strategy. The basic idea with divide and conquer is to divide the original problem into live or more sub problems and the problem can be solved efficiently by the same technique

Another general strategy is dynamic programming. This method is used often when we have to build up a solution to a problem via a sequence of intermediate.

Ø Use of specific examples

An approach that often allows us to make a start on a problem is to back specific examples of the general problem. We wish to solve and try to work out the mechanism that will allow us to solve this particular problem.

Example

If you want to find a maximum in a set of number choose a particular set of numbers and workout the mechanism for finding the maximum in the set.

Ø Similarities among problems

It is important to see if there is any similarity between the current problem and other problem. That we have solved or we have seen solved.

Therefore it is always to makes an effort to be aware of these similarities among problems.

A skill that is important to try to develop in problem Solving is the ability to give a problem from a variety of angles.

Ø Working backward from the solution

There are still other things we can find when we do not know to start on problem.

For example, in some cases assume that we already have solution to the problem and then try to work backward to the starting condition

Ø General problem solving strategy

There are no of general powerful and computational strategies that are repeatedly used in various find in computer science.

Divide and conquer strategy:

Most often used of these principles is the divide and conquer strategy, the basic idea of the divide and conquer strategy is to divide original problem into two or more, sub problem which can hopefully be solved more efficiency by same technique.

If it is possible to proceed with this splitting into smaller sub problems.

We will eventually reach the stage where the sub problem is small enough to be solved without further spilitting. This way of breaking down the solution to a problem has found wide application in particular with sorting, selection and searching algorithms. It is also possible to apply the divide and conquer strategy essentially in reverse of some problem.

Dynamic programming:

Another general problem solving strategy that we will briefly consider is that of Dynamic programming. This method is used most often when we have to built up a solution to a problem sequence of intermediate stages.

This method rules on the idea that a good solution to a large problem can sustain from the built-up from good art.

This type of strategy is particularly used for many optimization problem that are frequency encounter in operations in search.

The techniques of greedy search, back tracking, branch and bound are the evaluations for all variations on the basic dynamic programming idea.

2. Explain in detail about Top-down design technique.

(November/December 2003). (OR)

Explain in detail about establishing the initial conditions, for

loops, finding the iterative constructs, termination of loops with

example.(OR)

How to construct a loop & establishing the initial conditions for

loops and finding the iterative construct.(OR)

Draw the schematic diagram to represent the breakdown of a

problem into Subtasks employed in top down design and explain in

detail.

Top-down Design:

The primary goal in compute problem solving algorithm which is capable of being implemented as a and efficient computer program

A technique for algorithm design that lies accommodate this human limitation is as top-down design (or) stepwise refinement.

Ø Breaking a problem into sub problems

Ø Choice of a suitable data structure

Ø Construction of Loops

Ø Establishing initial condition for Loops

Ø Finding the iterative construct

Ø Termination of loops

ü Breaking a problem into sub problems

Top-down design take the general statements and break them down into a set of more accurately describe how the final goal into be reached. The process of repeatedly breaking down a task into subtasks and then each sub task into still smaller subtasks must contain until we eventually end up smaller subtasks that can be implemented as program statements

A schematic breakdown of a problem is shown is fig

Diagram

General outline

SS…. ….. ……….

ü Choice of a suitable data structure

Data structure and algorithms are usually intimidate Linked to one another

In setting up a data structure certain factors to be considered are,

i) Can the data structure be easily searched

ii) Can the data structure be easily updated

ü Construction of Loops

To construct any loop we must take factors into account the initial conditions that need to apply before the loop begins to execute the invariant relation that must apply after each iteration of the loop, and the conditions under which the interactive process must terminate

ü Establishing initial condition for Loops

To establish the initial conditions for a loop usually effective strategy is to set the loop variable to the values that they would have to assume in order to solve the smallest problem associated with the loop

Typically the number of iteration ‘n’ that must by a loop are in the range 0<=I<-n

The smallest problem corresponds to the sum of zero numbers. The sum of zero numbers is zero and so the initiate value of I and s must be

I: =0 Solution for n=0

S: =0

ü Finding the iterative construct

Once we have the conditions for solving the smallest problem the next step is try to extend it to the next smaller problem (when i=1)

The solution for n=1 is

I: =0 Solution for n=1

S: =0

The solution for n=1 can be built from the solution for n=0 using the values for s and I, n=0 and the two expression.

I: = I+1

S: = S+a [I] Generalized Solution for n>0

The same two steps can be used to extend the solution from where n=1 to n=2 and so on. These two steps will in general exkind the solution from the (I-1) th case to the it case (where I<1)

ü Termination of loops

These are number of warp is which loops can be terminated. The simplest condition for terminating a loop occurs when it is known is advancing how much iteration need to be made.

For ex: in Pascal the for-loop can be used for such computations

For I: =1 to do

Begin

-------

End

A second way in which loops can terminate is when some conditional expression

become false. An ex:

While (x>0) and (x<10) do

Begin

-------

End

Yet another way in which terminate of loop can be setup is by forcing the condition under which the loop will continue to iterate to become false,

A [n+1]: = a [n]

I: =1;

While a [I] < a [I+1] do

I : I+1;

If ‘n’ was assigned the value n=5 the data was a[1]=2; a[2]=3; a[3]=5; a[4]=14;

a[n+1]=4;

a[n+1]=a[n]

The test a[I] < a(I+1) will be false when I=n and so the loop will terminate correctly when I=n if not before

The general rule for using the method of termination is to arrange the data at the end of the array so that it will force the conditional expression for the loop to

become false:

I: =2

While (a[I-1] < a[I] and I<1) do

I: = I +1.

3. Describe in detail about the implementation of algorithm.(OR)

Explain in detail about an algorithm implementation.(OR)

What are the steps involved in implementing an algorithm?

Implementation of algorithm

The Implementation of an algorithm has been properly in a top-down fashion use of top-down fashion. An algorithm can be implemented using the following steps.

Ø Use of procedures to emphasize modularity

Ø Choice of variable names

Ø Documentation of programs

Ø Debugging programs

Ø Program testing

ü Use of procedures to emphasize modularity

Implementation and readability of the main program to helpful to modulaize the program from top-down design. The practice allows us to implement a set of independent procedure to perform specific and well-defined tasks

The mechanism for the main program can be implemented with “calls” to the various procedures that will be needed in the final implementation

We can just place a “write” statement is the selection procedure which simply writes out the procedure name when it is called for ex:

Procedures sort:

Begin

Writeln (‘sort called’)

End

ü Choice of variable names

Another implementation is detail that can make programs more meaningful and easier to understand is to choose appropriate variable and constant names. For ex: if we have to make manipulations on days of the week we are much convenient with using the variable “day” taken then the single letter or same other variable.

ü Documentation of programs

A good programming practice is to always write program so that they can be executed and used by other people. An familiar with the workings and i/p requirements of the program.

This means that the program must specify during execution exactly what responses (and their format) requires from the user.

Also the program should catch incorrect responses to its requests and inform the user in a appropriate manner.

ü Debugging programs

To make the task of detecting logical errors somewhat easier is a good idea to built into the program a set of statements that will printout information at strategic points in the computation.

The simplest way to a implement is debugging tool is to have a Boolean variables

Which is set to turn when the verbose debugging o/p for the program is required

Each debugging o/p can then be parenthesized in the following way:

Begin

Writeln (---)

End

ü Program testing

In attempting to test whether or not a program will handle all variations of the problem it was designed to solve we must make every effort to be sure that it will cope with the limiting and unusual cases

Eg:

Table 1 Appropriate data sets for testing binary search algorithm

	Test	Search value(s)x	sample data
	1) Will the algorithm handle the search of array of one element 2) Will it handle the case where all array values are equal 3) Will it handle the case where the element is sought equals the first value in the array 4) Will it handle the case where the values sought equals the last value in the array 5) Will it handle the case where the values sought less than first element in the array 6) Will it handle the case where the values sought greater than last value in the array 7) Will it handle the case where the values sought is at an even array location	0,1,2 a[1] = 1 0,1,2 a[1] 1 n 0 n+1 2	N=1 A[1]=1,a[2]=1------a[n]=1 A[1]=1,a[2]=2------a[n]=n A[1]=1,a[2]=2------a[n]=n A[1]=1,a[2]=2------a[n]=n A[1]=1,a[2]=2------a[n]=n A[1]=1,a[2]=2------a[n]=n
4. Write in detail about the program verification and verification of program Segments with loops.(OR) Explain in detail about Program verification with suitable example.(OR) Explain in detail about Implications and symbolic execution & Input and Output assertions.(OR) Write in detail about the program verification and verification of program Segments with loops and Verification of program segments with branches.

ü Program verification

Program verification refers to the apply 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.

ü Input and output assertions

The very first step that needs to be taken in order to prove a program correct is to provide a formal statement of its specifications in terms of the variables that it employs. The formal statement has two parts an i/p assertion and an o/p assertion, which can be expensed in logic notation as predicates that describe the state of the execution program Variables. The i/p assertion should specify any constraints that have been placed on the values of the i/p variable used by program. When there are no restrictions on the values of the i/p variables the i/p assertion is given the logical value tree. The o/p assertion must specify symbolically the results that the program is expected to produce for input data that satisfies the input assertion

If a program is designed to calculate the quotient q and remainder “l” resulting from the divisions of x by y the o/p assertion can written as

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

When the symbol “l” represent the logical connective “and”.

ü Implications and symbolic execution

The problem of actually verifying a program can be formula as a set of implications, which must be shown to be logically true. These implications have the general form.

p>q

Where the logical connective “>” is read as “implies” “p” is learned as assumption and as conclusion. The associated truth defining implication is given in Table1.3

Truth Table defining implication

P q p>q

True True True

True False False

False True True

False False True

A relatively straight forward way to do this to to use the technique of symbolic execution with symbolic execution, all i/p data values are replaced by symbolic values with all arithmetic operations on numbers translate into algebraic manipulation of symbolic expressions. As an example, consider the following program segment labeled with i/p & o/p operations:

A real ln (x, y);

{assert: true}

x: =x-y;

y: =x+y;

x: =y-x;

B { assert x=y0^y=x0}

Where x0 & y0 refer to the initial values of x & y respectively.

Normal & symbolic execution for exchange mechanism.

Step Normal execution symbolic execution

Input values: x=3, y=1

1 x: = x-y->x=3-1=2 x: = x-y->x=a-b

2 y: = x+y->y=2+1=3 y: = x+y-> y=(a-b)+b=a

3 x: =y-x->x=3-2=1 x:=y-x ->x=(a-b+b)-(a-b)=b.

Both normal execution & symbolic execution, shown in Table , indicate that values of x & y are exchanged.

A proposition phrased in this way is referred to as a verification condition (vc) over the pgm segment from the i/p assertion to the o/p assertion.

We will adopt the convention that vc (A-B) refers to the verification condition over the pgm segment from A to B. We will now consider the verification of each of these basic segment types in turn.

ü Verification of straight –line program segments.

Exchange mechanism mentioned allover will serve as an example of a straight-line pgm segment.

The verification condition for this pgm segment is

VC (A-B): true>{x=y 0 ^y=x0}

On substitution of the initial & final values of all variables we get,

VC (a-b): true > ((a-b) +b-(a-b)) =b^(a-b)+b)= a

The conclusion part of the verification condition can be simplified to yield b=b & a=a which is clearly true & so the implication is true.

ü Verification of program segments with branches:

To handle program segments that contain branches it to necessary to set up & prove verification condition for each branch separately. As an example, consider the full pgm 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:={

End

B{assert PB:((x<=y)^(x=x0^y=y0))V(x=y0^y=x0))}

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

PA ^ CA > PB

PA ^ »CA>PB

Where CA is the branch condition.

ü Verification of program segments with loops:

There are pbms with trying to verify loop segments directly by symbolic execution because the number of iterations required is usually arbitrary a special kind of assertion called a loop invariant must be employed. A loop invariant should be a property that caplets the progressive computational role of the loop while at the same time remaining true before & after each loop traversal irrespective of how many times the loop is executed.

A [input assertion PA]

[straight –line pgm segment]

B [loop invariant IB]

While loop-condition do

Begin

[Loop-true pgm segment]

End

C [output assertion pc]

The 1^st step that must be taken into show that the loop invariant is true initially, before the loop is entered. Setting up a verification condition VC can do this

(A-B) for the pgm segment from A to B.That is, we must show PA>PB

The 2^nd part of verifying a loop involves showing that loop invariant is still true after the segment of pgm with in the loop has been executed. To do this we can set up a verification condition vc (B-B).

IB^(B>IB).

As a final step in verifying a loop segment , it is necessary to show that the invariant together with the negation of the loop entry condition, implies the assertion the applies on existing from the loop,

IB^»CB>pc

the verification method we have described gives us only a proof of partial correctness, with the implication that if algorithm terminates the result produced will be correct.

Verification a program segments that employ always:

The idea of symbolic execution developed in the preceding sections can be, extended to some of the simpler that employ always although it now becomes, necessary to account to the symbolic values of all away elements.

The pgm annotated with assertions may take the following form:

A {assert PA :n>³,}

I: =1;

P: =1;

B {invariant IB:(1£I<n)^(1<=p<=p<=I)^ (a[p]<=a[1];------a[I]}

While I<n do

Begin

I:=I+1;

If a[I]<a[p] then p:=1;

End

C{assert pc: (1<=p<=n) ^ (a[p]<=a[1],a[2], -------a[n]}

Where we have used the shorthand convention that:

A[p]<=a[1],a[2]-----a[n]=a[p]<=a[1]^a[p]<=a[2]^---^a[p]<=a[n]

Assuming that the initial values of a[1],a[2],----a[n] respectively a1, a2,------ an

Vc (A-B):¶ ³ 1>(1£1£¶)^(1£1£1)^µ1£µ1.

5. How to improve the efficiency of an algorithm and point out

the mistakes in the Loops with redundant computations?(OR)

How can you improve efficiency of an algorithm using the

Referencing array Elements?(OR)

Explain in detail about efficiency of an algorithm.(OR)

What are the steps involved to improve the efficiency of an

algorithm?

Efficiency of algorithm:

Efficiency of considerations for algorithm are inherently tied in with the design implementation, and analysis of algorithms. Every algorithm must use some of computers resources to complete its task. The resources most relevant in relation to efficiency of it are always desirable to design algorithms that are economical in the use of CPU time & Memory.

ü Redundant computations

ü Referencing array elements

ü Inefficiency due to late termination

ü Early detection of desired output conditions

ü Trading storage for efficiency gains

ü Redundant computations:

Most of the inefficiencies that sleep into the implementation of algorithm come about because redundant computations are made or unnecessary storage is used.

The most common mistake using loops is to repeatedly recalculate part of expression that remains constant throughout the entire execution phase of the loop. The example below illustrate this point

X: =0;

For I: =1 to n do

Begin

X: X+0.01; / * ‘X’ value is repeatedly calculated */

Y:= (a*a*a + c) * x * x + b * b *x;

Writeln ( ‘x=’;x : y=’,y)

End.

This loop does twice the number of multiplication necessary to complete the computation

A3c : = a * a * a +c;

B2 : = b * b;

X : = 0;

For I:=1 to n do

Begin

X : = x+ 0.01;

Y : = a3c * x * x * +b2 *x;

Writeln(‘x=’,x’ y =’, y)

End.

ü Referencing array elements

If care is not exercised redundant computations can also easily creep into array processing.

Version (1)

P : =1;

For I : =2 to n do

If a[I] > a[p] then p : =I;

Max : = a[1];

For I: =2 to n

If a[ I ] > a[p] then p:=I;

Max: = a[p]

Version (2)

P: = 1

Max: = a[1];

For I: = 2 to n

If a [I] > max then

Begin

Max: = a [I]

P ; = I

End

ü Inefficiency due to late termination

This type of inefficiency can be best illustrated by example we had to linear search an alphabetically ordered list of names for some particular name. This efficient implementation could have the form

1.While name sought <> current name and end-of –file do a get next name from list

A more efficient implementation would be:

While name sought <> current name and end-of –file do a get next name from list

Test if current name is equal to name sought with this sorting mechanism, after I th iteration the last I values is the array will be sorted order. This for any given I the inner loop should not proceed beyond n-I,

The loop structure will then be:

For I : =1 to n-1

For j: =1 to n- I

If a[j] > a[j + 1] then “exchange a[j] with a[j + 1]”

The lesson to be learned from this is that we should always try to take advantage of any order or structure is a problem.

ü Early detection of desired output condition

It is sometimes happens, due to the nature of the input data that the algorithm establishes the desired output condition before the general conditions for termination have been met.

For example a bubble sort might we used to sort a set of data. That is already almost in sorted order.

When this happens it is very likely that the algorithm will have the data in sorted order long before the loop terminations are met.

If there have been no exchanges in the current pass the data must be sorted and so early termination can be applied.

When a more efficient solution to a problem is for better to try to improve the algorithm rather than resorting to programming “tricks”.

6. How to calculate the time complexity for the best case,

worst case and Average case. Explain with example. (OR)

Explain in detail about the analysis of algorithm. (OR)

Explain in detail about the case behavior of an algorithm

with example.(OR)

Explain in detail the types of analysis that can be

performed on an algorithm (Nov/Dec2005)

Analysis of algorithms

These are usually many ways to solve any given problem. In computing as in most efforts of human endeavor. We are generally concerned with “good” solution to problem. Among other things, a good algorithm usually passes the following qualities & capabilities.

ü There are simple but powerful & general solutions

ü They can be easily understood by other that is the implementation is clear and concise without being “likely”

ü They can be easily modified if necessary

ü They are correct for clearly defined situations

ü They are able to be understood on a number of levels

ü They are economical is the use of computer line, computer storage & peripheral

ü They are documented well enough to be used by others who do not having detailed knowledge of their inner workings.

ü They are not dependent on being run on a particular computer

ü They are able to be used as a sub procedure for other problems

ü The solution is pleasing & satisfying to its designer a product that the designer feels proud to have created

Computational complexity

To make a quantitative measure of an algorithms performance it is necessary to set up a computational model that reflects its behavior under specified input conditions.

The computational cost as function of problem size for a Lange of computational complements.

Log2n n nlog2n n2 n3 2^n

1 2 2 4 8 4

3.322 10 33.22 10^2 10^3 >10^3

6.644 10^2 664.4 10^4 10^6 >>10^25

9.966 10^3 9966.0 10^6 10^9 >>10^250

13.287 10^4 132.877 10^8 10^12 >>10^2500

Order notation

A standard notation has been developed to represent function, which bound the computing time for algorithm. It is an order notation & it is usually referred to as the

O-notation

G(n) <= (for (n) (o-big oh)

Holds for all values of n that are finite & positive we can write the alive relationship in the form:

Lim g(n) / f(n) =c where c is not equal to Zero

n->¥

As an example suppose we have an algorithm that requires (3n^2 + bn +3) comparisons to computer its task.

According to the conversion just outlined we have

G (n) = 3n^2 + bn +3 and Lim 3n^2 + bn +3 =3

n->¥ n^2

For example consider the Marti - Multiplication algorithm.

Algorithm Marti – Multiplication: Given two dimensional sequence matrices A and B, each containing N rows and columns This algorithms computer the matrix product and place the result is matrix c,I,j and k are integer variables

1. [Multiply matrices a and B and store the result in matrix c]

Repeat for I = 1,2, ------- n

Repeat for j = 1,2,- ------ n

Sum<-0

Repeat for k = 1,2, ------- n

Sum <- Sum + A [I,K] * B [K,J]

C [I,J]<- Sum

2. [Finished]

Exit

The actual size of the input for this algorithm 2N^2 but it is convenient to use N as measure of the size input in order to simplify the calculations

These are actually more assignment to I, N^2 assignments to J and c , N^3 assignments to k and N^2 + N^3 assignments to sum

The yields a total of N + 3 N^2 + 2 N^2 assignments. We would conclude that the line was proportional to N + 3 N^2 + 2 N^3. Finally we obtain that the order magnitude for the time required is N^3

Best case, worst case and average analysis of algorithm

Consider the algorithm linear search. In this algorithm given a vector V containing N elements, it searches V for the value of a given X. Found is a Boolean variable I and location are integer variables

Algorithm search

1. [ Search for the location of value x vector v]

FOUND <-false

I<-1

Repeat while I<=n and not FOUND

IF V[I]=X

THEN FOUND<-TRUE

LOCATION<- I

Exit

Else I<-I + 1

Write(‘Value of’, x , ,’ NOT FOUND)

2. [Finished]

Exit

The answer depends on the index of the location containing x N=5; V[1]=15; V[2]=25; V[3]=35; V[4]=40; V[5]=60;

When x=15, so ‘x’ is equal to v[1] since only one comparison is used so it is called “best case” of an algorithm. The magnitude of the time to required for the best case of the algorithm is TLS B (N) =0 (1) [*only one comparison]

Which x=60 so x is equal to V(N) and N comparison are used. So it is called “worst case” of an algorithm. The magnitude is Tw (N) = 0(N) (N comparisons *)

Average: The probability distribution for the value x in the vector that is probability of x occurring in each location. Then using the above assumption we have probability in location I is q/n, probability x is not in the vector is 1-q

The average time is given by

TA (N) = å(probability of situations ) * (time for situation s)

Where s is the set of all possible situation

TA(N) = (probability of x in location 1) * 1+ (probability of x in location 2) * 2------+(probability of x in location N) * N+(probability of x not is v) * N

=å q/N * s + (1-q) * N

=q / N =å q/N * s + (1-q) * N

= q*(N + 1)/2 + (1-q) * N

This if q=1 then TlsA (N)=N+1/2 and if q=1/2 then TlsA (N)=N+1/4 + N/2 3N/4

In either case TlsA (N)= O(N)

So the argument case timing analysis is generally more difficult than the best case or the worst case.

Sample algorithm (Following algorithms may asked in 8 or 16 marks)

7. Write an algorithm to find the largest element in an array

Explain the concept of divide and conquer algorithm for the

selection largest no. in an array. (April/ May 2004)

Algorithm: (Largest element in an Array) A non-empty query DATA with N numerical values given. This algorithm finds the Location LOC 7 the value MAX of the largest element of DATA. The K is used as a counter.

Step1: [Initialize]

Set k: = 1, Loc: = 1 & MAX: = DATA [1]

Step2: [Increment counter]

Set k: = K+1

Step3: [Test counter]

If k > N then:

Write: LOC, MAX and EXIT

Step4: [Compare and update]

If MAX < DATA[ K], then

Step5: [Repeat Loop]

Go to step2.

8.To find real solutions of a quadratic equation

Alg: (Quadratic equation) This algorithm inputs the co- efficient A, B, C of a quadratic & outputs the real solution, if any

Step 1: Read A, B, C

Step 2: [calculate the value}

D: =B 2 - 4ac

Step3: [check the value of D]

If D > 0 then

a) Set x1: =(-B + d)/(2 * A)

and

b) X2 := (-b –d)/ (2*A)

Else if d=0, them:

a) Set x: = -b/2a

b) Write ‘UNIQUE SOLUTION’, x

Else

Write: ‘NO REAL SOLUTION’.

[End of if structure]

Step4: Exit.

9. Compare the algorithm for linear search. (Nov /Dec 2003)

Alg: (Linear search) A Linear array Data with N element and a specific ITEM of inform are given. This algorithm finds the Location LOC of ITEM in the away DATA or sets LOC=0

Step 1: [Initialize]

Set k: =1 and LOC: =0

Step 2: check LOC and K value]

Step 3: [check the ITEM value]

If ITEM = DATA [k], then set LOC:=k

Step 4: [Increments counter]

Set k: =k+1

[End of step2 loop]

Step 5: [successful]

If LOC=0,then

Write: Item is not in the away DATA

Else

Write: LOC is the location of ITEM

[End of if statement]

Step6: Exit

10. Explain the procedures of Bubble sort.( April/May 2004)

Alg: [Bubble sort] BUBBLE (DATA, N)

1. [Repeat the steps 2 and 3]

Repeat steps 2 & 3 for k=1 to n-1

2. [Initialize pan pointer PTR]

Set PTR: =1

Execute

Repeat while PTR £ N-K;

a) IF DATA [PTR] and DATA [PTR+1], then:

Interchange DATA [PTR] and DATA [PTR+1]

[End of if structure]

b) Set PTR: = PTR+1

[End of Inner loop]

[End of step 1 outer loop]

3. Exit.

11.Write an algorithm to find an element in an array using

Binary search.(OR)

Write down the algorithm binary search for searching x

from an array a [1,n]and give stepwise execution.

(May/June 2005) (OR)

Explain the binary search algorithm with suitable example.

(April/May2004)

Alg: (Binary search) BINARY (DATA, LB, UB, ITEM, LOC) Here DATA is a sorted away with lower bound LB and upper bound UB, and ITEM is a given item of inform. The variables BG, END, &mid denote respectively, the beginning, end and middle location of a segment of elts of DATA. This alg finds the location LOC of ITEM in DATA or sets LOC NULL.

1. [Initialize segment variables]

Set BEG: =LB, END: =VB and

MID = INT (BEG + END)/2

2. [Execute]

Repeat step3 and & while BEG £END and

DATA [MID]<ITEM.

a. [Check the Item value]

If ITEM < DATA [MID], THEN;

Set END: =MID-1

Else ¹

Set BEG =MID+1

[END of if structure]

3. [Set the MID value]

Set MID: = INT (BEG+END)/2

[END of step 2 loop]

4. [Check the MID value with the ITEM]

If (DATA [MID]=ITEM) then

Set LOC: = MID

Else:

Set LOC: =Null

[End of if structure]

5. Exit.

12.Write an algorithm to implement Matrix multiplication

Write an algorithm to perform matrix multiplication algorithm

and analyze the same (Nov/Dec 2005)

Alg: (Matrix multiplication) MATMUL (A<B<C,M<P<N)Let A be an M&P matrix away, and let B be a P & N matrix away. This alg slots the product of A and B in an M & N Matrix away. Repeat step2 to 4 for I=1 to m

1. [Repeat the value of J]

Repeat steps 3 to 4 for j=1 to N

2. [Initialize c [I, J];

Set c [I, J]=0

3. [Repeat the value of K]

Repeat for K=1 to p;

C [I,J]:=c[I,J]+a[I,K]*b[k,J]

[End of loner loop]

[End of step 2 middle loop]

[End of step 1 outer loop]

4. Exit.

13.To find the Factorial value of N.(OR)

Using the concept of recursion, write a pgm to find factorial

of a number.(Apr/May 2004)

Alg: (Factorial value of N)

1. [Initialize the FACT value]

IF N=0 then set FACT: =1

and Exit

2. [Initialize FACT for loop]

Set FACT: =1

3. [Repeat the value of k]

Repeat for k=1 to N

Set FACT:=K*FACT

[END of loop]

4.Exit

14.To find the sin (x) computation [x-x3]

Alg:(sin (x) computation): sin (x)

1. [Assign the values]

Term: =x; sin: =x; I=1; x2:=x+x

error=1.oe-6

2. [Check and generate the terms of sine expression]

While abs (term)>errors do

i: =i+2;

term: =-term*x2/(I*(I-I));

t sin:=t sin term

end;

sin: = t sin;

end.

15.Reversing the digits of an integer

Alg: (Reverse the digits of an Integer)

Dreverse(n)

1. [Assign the value]

reverse: =0;

2. [Repeat the value]

While n>0 do

reverse: = reverse * 10 + n mod 10;

n:=n div 10

dreverse: =reverse

End.

MILIND KUMAR

Thursday, 19 September 2013

EDC III SEM LAB MANUAL FREE DOWNLOAD

Friday, 13 September 2013

DSA STUDY MATERIAL III SEM UNIT 1.

DATA STRUCTURES / CS1151 / II SEM CSE

UNIT –I PROBLEM SOLVING

CONTENTS

Ø Problem definition Phase

Ø Getting started with a problem

Ø Construction of Loops

ü Choice of a suitable data structure

ü Construction of Loops

ü Establishing initial condition for Loops

VISITED