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…
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
|
 |
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 1st
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 2nd
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.
No comments:
Post a Comment