www.studymaterialz.

in

5. What is XML? Explain Breifly

6. Explain the types of database security and database security issues. [May/June 2016]
7. Explain clearly the Classification& clustering techniques.
8. Explain briefly the retrieval of information.
9. Explain in detail about Association & regression.
10. Explain Geographic information system.
11. Explain about cloud based databases.
12. Explain about XML query languages.
13. Give details about approaches used to store XML documents in database.
14. Describe Cloud storage architecture with neat diagram
Give the DTD or XML Schema for an XML representation of the following nested-
relational schema :
Emp = (ename, ChildrenSet setof (Children), SkillsSet setof (Skills)) Children = (name,
15. Birthday)
Birthday = (day, month, year) . ‘
Skills = (type, ExamsSet setof(Exams)) Wwwereceitigc swan Paper.com Exams=
(year, city) . . [NOV/DEC2016]
Explain about Distributed Databases and their characteristics, functions and advantages
16.
and disadvantages. [May/June 2016]
17. Explain the process of querying XML data with an example. [April/May 2017]
Explain the necessary characteristics a system must satisfy to be considered as an object
18.
oriented database management system. [April/May 2018]

CS8451 DESIGN AND ANALYSIS OF ALGORITHMS

UNIT-I

PART-A

1. Define algorithm.

An algorithm is a sequence of unambiguous instructions for solving a problem in a

finite amount of time.
2. What is the process of Algorithm Design and Analysis?
o Understand the problem
o Decide on Computational Device Exact Vs Approximate Algorithms
o Algorithm Design Techniques
o Design an algorithms
o Prove Correctness
o Analyze the Algorithm
o Code the Algorithm

3. How to measure the algorithm’s efficiency?

a)Time Efficiency-How fast your algorithm runs?
 www.studymaterialz.in

b)Space Efficiency-How much extra memory your algorithm needs?

4. How can you specify Algorithms?

Algorithms can be specified natural language or pseudo code.

5. What is Pseudo Code?

Pseudo Code is a mixture of Natural Language and Programming Language
Constructs such as functions, loops, decision making statements.etc

6. What are the Important Problem Types?

 Sorting
 Searching
 String Processing
 Graph Problem
 Combinatorial Problem
 Geometric Problem
 Numerical Problem

7. How can you classify Algorithms?

Among several ways to classify algorithms, the two principal alternatives are
 To group algorithms according to types of problem they solve com
 To group algorithms according to underlying design techniques they are based
upon

8. What is Sorting Problem?

Sorting algorithm is rearranging the items of given list descending/ascending order. Sorting
algorithms classified into
 Stable Sorting Algorithm
 Non-Stable Algorithm

9. What is Searching Problem?

Finding a given value, called search key given set. Searching Algorithms needs
more memory space and sorted array.

10. What is Graph Problem?

Graph is a collection of dg s and vertices. G=(V,E). For e.g. Traversal Algorithms,
Shortest Path Algorithm, Graph Colouring Problem

11. What is Combinatorial Problem?

This problem that ask to find combinatorial object such as permutations, combinations
or a subset. Combinatorial problems are most difficult to solve. For eg travelling sales man
problem.

12. Differentiate Time Efficiency and Space Efficiency?

 www.studymaterialz.in

Time Efficiency measured by counting the number of times the algorithms basic
operation is executed. Space Efficiency is measured by counting the number of extra
memory units consumed by the algorithm.
13. What are the features of efficient algorithm?
 Free of ambiguity
 Efficient in execution time
 Concise and compact Completeness
 Definiteness Finiteness

14. Define Order of Algorithm

The order of algorithm is a standard notation of an algorithm that has been
developed to represent function that bound the computing time for algorithms. The order of
an algorithm is a way of defining its efficiency. It is usually referred as O-notation.

15. Define Big Omega Notation.

Omega notation provides lower bound for the function t
A function t(n) is said to Omega (g(n)), if there exist some. Positive constant C and some
non negative integer N0, such that
t(n)>=Cg(n) for all n>=n0

16. What is Big ‘Oh’ Notation?

The Big ‘Oh’ notation provides an upper bound for the function t. A function t(n) is
said to be O(g(n)), if there exist some positive constant C and some non negative number,
suchthat, t(n)<=Cg(n), for all n>=no

17. What are the different types of time complexity?

The time complexity can be classified into 3 types, they are
 Worst case analysis
 Average case analysis
 Best case analysis

18. How the algorithm’s time efficiency is measured.

Time efficiency indicates how fast an algorithm runs. Time taken by a program to
complete its task depends on the number of steps in an algorithm. The time taken by an
algorithm is the sum of compile time and execution time. The compile time does not
depend on the instance characteristics.

19. Write the For LOOP general format.

The general form of a for Loop is

For variable : = value 1 to value 2 step

 www.studymaterialz.in

Step do

statement 1

statement n

20. Write algorithm using iterative function to fine sum of n numbers.

Algorithm sum(a,n)

{ S : = 0.0

For i=1 to n do

S : - S + a[i];

Return S;

21. Write an algorithm using Recursive function to fine sum of n numbers,

Algorithm Rsum (a,n)

if(n≤ 0) then

return 0.0;

else return Rsum(a, n- 1) + a(n);

22. What is recurrence equation?

The recurrence equations are solved often in analyzing the complexity of algorithms,
circuits, and other such cases.

A recurrence equation is written as:

a0tn + a1tn-1 + . . . . + aktn-k = 0.

23. Establish the relationship between big Oh and big Omega.

 www.studymaterialz.in

The difference between Big O notation and Big Omega notation is that Big O is used to
describe the worst case running time for an algorithm. But, Big Omega notation, on the
other hand, is used to describe the best case running time for a given algorithm.

"T(n)T(n) is O (f(n))O(f(n))" iff for some constants c and n0

, T(n)<=cf(n)T(n)<=cf(n) for all n>=n0
"T(n)T(n) is Ω (f(n))Ω(f(n))" if for some constants c and n0, T(n)>=cf(n)
T(n)>=cf(n) for all n>=n0
"T(n)T(n) is Θ (f(n))Θ(f(n))" if T(n) is O(f(n)) AND T(n) is Ω(f(n))
"T(n) is o(f(n))" if T(n) is O(f(n)) AND T(n) is NOT Θ (f(n))Θ(f(n))

24. Give the two major phases of performance evaluation

Performance evaluation can be loosely divided into two major phases:

a. a prior estimates (performance analysis)

b. a Posterior testing(performance measurement)
25. Define input size.
The input size of any instance of a problem is defined to be the number of words(or the
number of elements) needed to describe that instance.

PART-B

1. Describe the steps in analyzing & coding an algorithm.

2. Explain some of the problem types used in the design of algorithm.
3. Discuss the fundamentals of analysis framework .
4. Explain the various asymptotic notations used in algorithm design.
5. Explain the basic efficiency classes.
6. Explain in detail about mathematical analysis of non-recursive algorithms with
suitable problem.
7. Explain in detail about mathematical analysis of non-recursive algorithms with
suitable problem.

UNIT-II
PART-A
1. What is Empirical Analysis?
It is performed by running a program implementing the algorithm on a sample of
inputs and analyzing the data observed. This involves generating pseudo code and
random numbers.

2. Define Convex-Hull Problem.

A set of points (finite or infinite) on the plane is called convex if for any two Points P
and Q in the set, the entire line segment with the end points at P and Q belongs to the set.

3. What is Divide and Conquer Algorithm?

It is a general algorithm design techniques that solved problem’s instance by
 www.studymaterialz.in

dividing it into several smaller instance, solving of them recursively, and then
combining their solutions to the original instance of the Problem.

4.What are the Features of Algorithm Visualization?

 Consistent
 Interactive
 Very Clear and Concense
 Emphasize the visual component

5. Define O-Notation.
A function t(n) is said to be O (g(n)), denoted t(n) C O (g(n)), if t(n) is bounded
above by some constant multiple of g(n) for all large n, ie ., if there exist some positive
constant c and some nonnegative integer 0 such that
t(n) <= cg(n) for all>=0

6. What is Algorithm Visualization?

It is defined as the use of images to convey some useful information about
algorithms.

7. Define Static Algorithm Visualization?

Static Algorithm Visualization shows an algorithms progress through a series of still
images. On other hand, Algorithm animation shows a continuous movie like presentation
of an algorithm’s operation.

8. What is Fibonacci Numbers?

The Fibonacci numbers are an important sequence of integers in which every element
is equal to the sum of its two immediate predecessors. There are several algorithms for
computing the Fibonacci numbers with drastically different efficiency.

9.What is the Classification of Algorithm Visualization?

Static Algorithm Visualization and Dynamic Algorithm Visualization

10.What is Brute Force?

Brute Force is a straightforward approach to solving problem, usually directly based
on the problem’s statement and definitions of the concepts involved.

11. What are the different criteria used to improve the effectiveness of algorithm?
 Input- Zero or more quantities are externally supplied .
 Output-At least one quantity is produced
 Definiteness-Each instruction is clear and unambiguous
 www.studymaterialz.in

 Finiteness-If we trace out the instructions of algorithm, then for all case the
algorithm terminates after finite number of steps
 Effectiveness-Every instruction must be very clear

12. What is recursive call?

An algorithm is said to be recursive if the same algorithm invoked in the body. There
are 2 types of algorithm. They are
1) Direct Recursive
2) Indirect Recursive

13. What is meant by direct recursive call?

An algorithm that calls itself is direct
recursive call. Eg.int fun(int x)
{
if(x<=0)
return x;
return (fun(x-1));}

14. Define indirect recursive call?

Algorithm A is said to be indirect recursive if it calls another algorithm which in
turn call A Eg: int fun(int x)
{
if(x<=0)
return x;
return (f1(x-1));
}
Int fun1(int y){
return fun(y-1)
}

15. List the application areas of algorithm visualization?

The 2 application are of algorithm visualization are Research and Education.

16. Define Extrapolation?

Extrapolation is approach, which deals with values of n that are outside of
the range of the samples values.

17.Define profiling?
Profiling is an important resource the empirical analysis of an algorithm running time.
Measuring n different segments of program can pinpoint a bottleneck in the program’s
performance that can be missed by an abstract deliberation about the algorithm’s basic
operations. The process of getting such data is called profiling.
 www.studymaterialz.in

18. Write the Control abstraction for Divide-and conquer.

Algorithm D And(ρ)
{ if small(p)
then return
S(ρ); else
{
divide P into smaller instance ρ 1, ρ 2, ρ k, k ≥ 1;
Apply D and C to each of these subproblems
Return combine (DAnd C(ρ1) DAnd C(ρ2),----, DAnd ((ρk));
}}

19. What is the substitution method?

One of the methods for solving any such recurrence relation is called the substitution
method.

20. Give computing time for Binary search?

In conclusion we are now able completely describe the computing time of binary
search by giving formulas that describe the best, average and worst cases.

Successful searches

Θ (1) θ (log n) θ (Log n)

best average worst

unsuccessful searches θ(log n) best, average, worst.

21. What is the maximum and minimum problem?

The problem is to find the maximum and minimum items in a set of ‘n’ elements.
Though this problem may look as simple as to be contrived, it allows us to demonstrate
divide-and-conquer in simple setting.

22. Define external path length.

The external path length E, is defines analogously as sum of the distance of all
external nodes from the root.

23. Define internal path length.

The internal path length ‘I’, is the sum of the distances of all internal nodes from the
root.
 www.studymaterialz.in

24. Is insertion sort better than the merge sort?

Insertion sort works exceedingly fast on arrays of less than 16 elements, though for
large ‘n’ its computing time is O(n2 ).

25. Write a algorithm for straightforward maximum and minimum.

algorithm straight MaxMin(a,n,max,min)

//set max to the maximum and min to the minimum of a[1:n]

max := min: = a[i];

for i = 2 to n

do

if(a[i] >max)

then max: = a[i];

if(a[i] >min) then min: = a[i];

}}

26. Give the recurrence relation of divide-and-conquer?

The recurrence relation is T(n) = g(n) T(n1) + T(n2) + ----+ T(nk) + f(n).

PART-B

1. Devise an algorithm to sort the following elements using merge sort technique
2. 286, 45,278,368,475,389,656,788,503,126
3. Write an efficient and exhaustive search algorithm for the traveling salesman
problem.
4. Explain Binary search in detail.

5. Give examples of assignment problems where

a. i) The largest element of cost matrix is not included in the optimal
solution .
b. ii) The largest element of cost matrix is not feasible for optimal solution.

6. Solve the recurrence for the number of additions required by strassen’s algorithm.
(Assume that n is a power of 2)
7. Implement in C, the divide and conquer closest pair algorithm.
 www.studymaterialz.in

8. Explain the upper and lower hulls in the convex-hull problem, with an example.
9. Give a specific example of inputs that make the quickhull algorithm run in quadratic
time.
UNIT III

PART-A

1. What is articulation point?

A vertex of a connected graph G is said to be in articulation point, if its removal
with all edges incident to it breaks the graph into disjoint pieces.

2.List the advantages of binary search?

 Less time is consumed
 The processing speed is fast
 The number of iterations is less. It take n/2 iterations.
 Binary search, which is used in Fibonacci Series, involves addition
and subtraction rather than division
 It is priori analysis, since it can be analyzed before execution.

3. Explain the principle used quick sort?

It is a partition method using the particular key the given table is partitioned into 2
sub tables so that first, the original key will be its position the sorted sequence and
secondly, all keys to the left of this key will be less value and all keys to the right of it
will be greater values.

4. What is binary search?

The binary search algorithm some of the most efficient searching techniques
which requires the list to be sort descending order.
To search for an amount of the list, the binary search algorithms split the list and
locate the middle element of the list.
First compare middle key K1, with given key K . If K1=K then the element is found.

5. What are the objectives of sorting algorithm?

 To rearrange the items of a given list
 To search an element in the list.

6. Why is bubble sort called by the name?

The sorting problem is to compare adjacent elements of the list and exchange them
if they are out of order. By doing it repeatedly, we end up bubbling up the largest element
to the last position on the list. The next pass bubbles up the second largest element and so
on until, after n-1 pass the list is sorted.

7. What are the 3 variations in transform and conquer?

The principle variations of transformed and conquer techniques are
 www.studymaterialz.in

 Instance simplification
 Representation change
 Problem reduction

8. Explain principle of Optimality?

The principle of optimality says that an optimal solution to any instance of an
optimization problem is composed of optimal solution to its sub instances.

9. What is need for finding minimum spanning tree?

Spanning tree has many applications. Any connected graph with n vertices much
have atleast-1 edges and connected graphs with n-1 edges are trees. If the nodes of G
represent cities and edges represent possible communication links connecting 2 cities,
then the minimum number of links needed to connect the cities is -1. Therefore, it is
necessary for finding minimum spanning tree.

10.What is spanning tree?

Let G={V,E} be an undirected connected graph. A sub graph t={V,E} of G is a
spanning tree of G, if it is tree.

12. What is Dynamic programming?

Dynamic programming is an algorithm design technique for solving problem with
overlapping subprograms. The smaller subprograms are solved only once and recording
the results in a table from which the solution to the original problem is obtained.

13. What is greedy method?

The greedy method is the most straight forward design, which is applied for change
making problem. The greedy technique suggests constructing a solution to an
optimization problem through a sequence of steps, each expanding a partially constructed
solution obtained so far, until a complete solution to the problem is reached. On each
step, the choice made must be feasible, locally optimal and irrevocable.

14.List the advantage of greedy algorithm

1) Greedy algorithm produces a feasible solution
2) Greedy method is very simple to solve a problem
3) Greedy method provides an optimal solution directly

15. Define the term control abstraction?

Control abstraction is procedure whose flow of control is learn but whose
primary operations are specified by other proceed res whose precise meanings are
left undefined.

16. List the applications of minimum spanning tree?

Spanning tree are used to obtain independent set of circuit equations for an electric
network. Another application of spanning tree arises from the property that a spanning tree
 www.studymaterialz.in

is minimal sub graph G’ of G such that

V (G’)=V(G) and G’

17. Define AVL Tree.

An AVL Tree is binary search tree which the balance factor of every node, which the
balance factor of every node, which is defined as the difference between the heights of
the node’s left and right sub trees is either 0 or +1 or -1

18. What do you mean by row major and column major?

In given matrix, the maximum elements particular row is called row major. In a given
matrix, the maximum elements in a particular column is called column major.

19. What is Minimum Cost Spanning Tree?

A minimum cost spanning tree of a weighted connected graph is its spanning tree of
the smallest weight, where the weight of the tree is defined as the sum of the weights on
all its edges.

20. Write any two characteristics of Greedy Algorithm?

 To solve a problem in an optimal way construct the solution from given set of
candidates.
 As the algorithm proceeds, two other sets get accumulated among this one set
contains the candidates that have been already considered and chosen while the
other set contains the candidates that have been considered but rejected.

21. What is Knapsack problem?

A bag or sack is given capacity n and n objects are given. Each object has weight wi
and profit pi .Fraction of object is considered as xi (i.e) 0<=xi<=1 .If fraction is 1 then
entire object is put into sack. When we place this fraction into the sack we get wixi and
pixi.

22. Define weighted tree.

A directed binary tree for which each edge is labeled with a real number (weight) is
called as weighted tree.

23. What is the use of TVSP?

In places where the loss exceeds the tolerance level boosters have to the placed. Given
a network and loss tolerance level the tree vertex splitting problems is to determine an
optimal placement of boosters.

24. What is the Greedy choice property?

 The first component is greedy choice property (i.e.) a globally optimal solution
can arrive at by making a locally optimal choice.
 www.studymaterialz.in

 The choice made by greedy algorithm depends on choices made so far but it
cannot depend on any future choices or on solution to the sub problem.
 It progresses in top down fashion.

25. Write the difference between the Greedy method and Dynamic programming.

Greedy method Dynamic programming

1. Only one sequence of decision is 1.Many number of decisions are generated.
generated
2. It does not guarantee to give an 2. It definitely gives an optimal
optimal solution always

26. What are the features of dynamic programming?

Optimal solutions to sub problems are retained so as to avoid recomputing their values.
Decision sequences containing subsequences that are sub optimal are not considered.
It definitely gives the optimal solution always.

PART-B

1. Apply Floyd’s algorithm or obtain all pair shortest path for the following graph.
Explain with the algorithm.

2. Solve the following instance of the 0/1 Knapsack problem for the given knapsack
capacity M=5.

Items Weight Value

1 2 12
2 1 10
3 3 20
4 2 15
3. Solve the following knapsack problem using the greedy technique.
N=6,
(P1,P2,P3,P4,P5,P6) = (W1,W2,W3,W4,W5,W6)=(100,50,20,70,7,3) and m=165

4. Explain Warshall’s & Floyd’s Algorithm.

5. Define optimal binary search trees with example.
 www.studymaterialz.in

6. Describe in detail about prim’s algorithm with suitable example.

7. Explain in detail about kruskal’s algorithm.
8. Define Dijkstra’s algorithm. Explain in detail with example.

UNIT-IV

PART-A

1. Define rotation?
A rotation in an AVL tree is a local transformation of its sub tree rooted at a node,
which is performed, when the balance factor of a node either +2 or -2.If an insertion or
deletion of a new node in AVL Tree creates a tree with a violated balance requirement,
then the tree is restructured by performing special transformation called rotation, that
restore the balance required.
2. What are the different type’s rotations?
The four types of rotations are.
 Right rotation
 Left rotation
 Double right-left rotation
 Double left right rotation.

3. What are the drawbacks of AVL Tree?

1) Frequent rotations are needed to maintain balances from the tree’s nodes.
2) Deletion is d ff cult due to the frequency rotations.
3)AVL tree is not considered as stranded structure for implementing dictionaries.

4. What is 2-3 trees?

A 2-3 tree is tree have 2 kinds of nodes. They are 2 nodes and 3 nodes. 2 nodes
contain single key k and has 2 children. A 3 nodes contains two ordered key K1 and
K2(K1<k2) and has three children.

5. Define Heap.
Heap is partially ordered data structure that is especially suitable for implementing
priority queues. A heap is said to be a max heap, then the children of every node have a
value less than that node. A heap is said to be a min heap, then the children of every node
have a value greater than node

7. What is a priority queue?

Priority queue is a data structure in which the intrinsic ordering of the elements does determine
the results of its basic operations Ascending and descending priority queue are the 2 types of priority
queue.

8. Define warshall’s algorithm?

 www.studymaterialz.in

Warshall’s algorithm is an application of dynamic programming technique, which is

used to find the transitive closure of a directed graph.

9. Define Floyd’s algorithm?

 Floyd’s algorithm is an application, which is used to find the entire pairs shortest
paths problem.
 Floyd’s algorithm is applicable to both directed and undirected weighted graph,
but they do not contain a cycle of a negative length
 Define prim’s algorithm.
 Prim’s algorithm is greedy and efficient algorithm, which is used to find the
minimum spanning tree of weighted connected graph

10. How efficient is prim’s algorithm?

The efficiency of the prim’s algorithm depends on data structure chosen for the
graph.

11. What is path compression?

The better efficiency can be obtained by combining either variation of quick union
with path compression. Path compression makes every node encountered during the
execution of a find operation point to the tree’s node.

12. Define Dijkstra’s Algorithm?

Dijkstra’s algorithm solves the single source shortest path problem of finding
shortest paths from a given vertex( the source), to all the other vertices of a weighted
graph or digraph. Dijkstra’s algorithm provides a correct solution for a graph with non
negative weights.

13. Define Huffman trees?

A Huffman tree is binary tree that minimizes the weighted path length from the root
to the leaves containing a set of predefined weights. The most important application of
Huffman trees are Huffman code.

14. What do you mean by Huffman code?

A Huffman code is a optimal prefix tree variable length encoding scheme that
assigns bit strings to characters based on their frequencies in a given text.

15. What is meant by compression ratio?

Huffman’s code achieves the compression ratio, which is a standard measure of
compression algorithms effectiveness of
(3-2.25)/3*100 = 0.75/3*100 .
= 0.25 *100
= 25%.

16. List the advantage of Huffman’s encoding?

 www.studymaterialz.in

Huffman’s encoding is one of the most important file compression methods.

1. It is simple
2. It is versatility
3. It provides optimal and minimum length encoding

17. What is dynamic Huffman coding?

In dynamic Huffman coding, the coding tree is updated each time a new character
is read from the source text. Dynamic Huffman n codlings used to overcome the
drawback of simplest version.

18. What do you mean by optimal solution?

Given problem with inputs, we obtain subset that satisfies come constraints. Any
subset that satisfies these constraints is called a feasible solution. A feasible solution,
which either maximizes or minimizes a given objective function, is called optimal
solution.

19. Define the Iterative Improvement Technique.

A technique that approaches a solution by progressive approximation, using the kth
approximate solution to find the (k+1)th approximate solution (see also iteration).
Examples of methods that rely on iterative improvement are the Jacobi method and
Gauss–Seidel method

20. Define flow shop scheduling.

The processing of jobs requires the performance of several distinct job. In flow shop
we have n jobs each requiring n tasks i.e. T1i, T2i,…...Tmi, 1<i<n.

21. Define non preemptive schedule.

A non preemptive schedule is a schedule in which the processing of a task on any
processor is not terminated until the task is complete.

22. Define preemptive schedule.

A preemptive schedule is a schedule in which the processing of a task on any
processor can be terminated before the task is completed.

23. Define optimal finish time.

Optimal finish time scheduling for a given set of tasks is a non preemptive schedule
S for which F (S) is minimum over all non preemptive schedules S.

24. Define preemptive optimal finish time.

Preemptive optimal finish time scheduling for a given set of tasks is a preemptive
schedule S for which F (S) is minimum over all preemptive schedules S.

25. What are the conditions of flow shop scheduling?

 Let Tji denote jth task of the ith job. Task Tij is to be performed on Pj number of
 www.studymaterialz.in

processors where 1<j<m i.e. number of processors will be equal to number of

task Any task Tji must be assigned to the processor Pj.
No processor can have more than one task assigned to it at any time. For any job I
processing the task for j>1 cannot be started until T(j-i), job i has been completed.

PART-B

1. Consider the following linear programming problem in two variables:

maximize 3x + 5y
subject to x+y<4
x + 3y < 6
x > 0, y> 0.
2. Explain in detail about an outline of an simplex method with example.

3. Prove the Max-flow Min-cut theorem with example.

4. Write short notes on the following:

i. Flow conservation requirement
ii. Augmenting path method
iii. Shortest augmenting path algorithm
iv. Forward and Backward edges

5. Explain how the maximum flow problem for a network with several sources and
sinks can be transformed into the same problem for a network with a single source
and a single link.
6. Define the following: source, sink, capacity, flow network and preflow.
7. Proof a matching M is maximal if and only if there exists no augmenting path
with respect to M.
8. Write an algorithm for Maximum Bipartite matching with example.

9. Write an algorithm for stable marriage algorithm with example.

10. Explain the following:
1. Blocking pair
2. Man-optimal
3. Woman-optimal

UNIT V

PART-A

1. Define backtracking.
Depth first node generation with bounding function is called backtracking. The backtracking
algorithm has its virtue the ability to yield the answer with far fewer than m trials.

2. What is Hamiltonian cycle in an undirected graph?

 www.studymaterialz.in

A Hamiltonian cycle is round trip along n edges of G that visits every vertex once
and returns to its starting position.
3. What is feasible solution?
It is obtained from given n inputs Subsets that satisfies some constraints are called
feasible solution. It is obtained based on some constraints

4. What is optimal solution?

 It is obtained from feasible solution.
 Feasible solution that maximizes or minimizes a given objective function. It is
obtained based on objective function.

5. List the application of backtracking technique?

8-Qeens problem
6. Given an application for knapsack problem?
The knapsack problem is problem combinatorial optimization. It derives its
name from the maximum problem of choosing possible essential that can fit too bag to
be carried on trip. A similar problem very often appears business, combinatory,
complexity theory, cryptography and applied mathematics.

7. Define subset sum problem?

Subset sum problem is problem, which is used to find a subset of a given
set S={S1,S2,S3,…….Sn} of positive integers whose sum is equal to given positive integer .

8. What is heuristic?
A heuristic is common sense rule drawn from experience rather than from
mathematically proved assertion.
For example, going to the nearest unvisited city in the travelling salesman
problem is good example for heuristic.

9. State the concept of branch and bound method?

The branch and bound method refers to all state space search methods in which all
children of the E-Node are generated before any other live node can become the E-node.

10. Give the upper bound and lower bound of matrix multiplication algorithm?
Upper bound: The given algorithm does n*n*n multiplication hence at most
n*n*n multiplication are necessary.
Lower bound: It has been proved in the literature that at least n*n multiplications
are necessary.

11. What is state space tree?

Backtracking and branch bound are based on the construction of a state space tree,
whose nodes reflect specific choices made for a solution’s component .Its root represents
an initial state before the search for a solution begins.
 www.studymaterialz.in

The nodes of the first level the tree represent the made for the first component of
solution; the nodes of the second even represent the Choices for the second components
& so on.

12. What is promising and non promising node?

A node state space tree is said to be promising, if it corresponds to a partially
constructed solution that may still lead to complete solution. Otherwise, node is called
non- promising.

13. What are the additional items are required for branch and bound compare to
backtracking technique?
Compared to backtracking, branch and bound requires 2 additional items.
1) A way to proved , for every node of node of state space tree, a bound on the best
value of the objective function on any solution that can be obtain d by adding further
components to the partial solution represented by the node.
2) The value of the best solution seen so far.

14. Differentiate backtracking and branch bound techniques.

1. Backtracking is applicable only to non optimization problems.
2. Backcktracking generates state space tree depth first manner.
3. Branch and bound is applicable only to optimization problem.
4. Branch and bound generated a node of state space tree using best first rule.

15. What is called all pair shortest path problem?

Given a weighted connected graph, the all pairs shortest paths problem is to find the
distances from each vertex to all other vertices.

16. When do you say a tree as minimum spanning tree?

A spanning tree is said to be minimum spanning tree when the weight of the
spanning tree is smallest, where the weight of a tree is defined as the sum of the weight of
all its edges.

17. How will you construct an optimal binary search tree?

A binary search tree is one of the most important data structures in computer
sciences. Its principal applications are to implement a dictionary, a set of elements with
the operations of searching, insertion and deletion. If probabilities of searching for
elements of a set are known as optimal binary search tree, for which the average
number of comparisons in a sear h is the smallest possible.

18. What is the runtime of shortest path algorithm?

The runtime of shortest path algorithm is θ((n+|E|) log n)

19. What is mathematical modeling?

 www.studymaterialz.in

Mathematical modeling is method of ex pressing problem in terms of purely

mathematical objects such as variables, functions and equations.

20. What is pre structure?

Pre structuring is type of technique that exploits space for time tradeoffs simply
uses extra space of facilities faster and or more flexible access to data.

21. Define Heap sort?

Heap sort is sorting algorithm. Heap sort is 2 stage algorithms. The two stages are
Stage 1- Heap Construction- Construct heap for a given array of
elements
Stage 2- Maximum Deletion- Apply the root deletion operation n-1 times to the
remaining heap.

22. What are the requirements that are needed for performing Backtracking?
To solve any problem using backtracking, it requires that all the solutions satisfy a
complex set of constraints. They are:
i. Explicit constraints.
ii. Implicit constraints.

23. What are NP- hard and NP-complete problems?

The problems whose solutions have computing times are bounded by polynomials
of small degree.

24. What is Biconnected Graph?

 An undirected graph is called Biconnected if there are two vertex-disjoint paths

between any two vertices.
 In a Biconnected Graph, there is a simple cycle through any two vertices.
By convention, two nodes connected by an edge form a biconnected graph, but this
does not verify the above properties.
 For a graph with more than two vertices, the above properties must be there for it to
be Biconnected

25. What is approximate solution?

A feasible solution with value close to the value of an optimal solution is called
approximate solution.
PART-B

1. Explain the 8-Queen’s problem & discuss the possible solutions.

2. Solve the following instance of the knapsack problem by the branch & bound
algorithm.
 www.studymaterialz.in

3. Apply backtracking technique to solve the following instance of subset sum

problem:
S={1,3,4,5} and d=11
4. Solve the following 6 city traveling salesperson problem using the branch and
bound algorithm.

α 21 42 31 6 24
11 α 17 7 35 18
25 5 α 27 14 9
12 9 24 α 30 12
14 7 21 15 α 48
40 15 16 5 20 α

5. Explain how branch and bound technique is used to solve 0/1 knapsack problem.
for n=4 , W=10, (p1,p2,p3,p4) = (40,42,25,12) and (w1,w2,w3,w4) = (4,7,5,3).

6. Briefly explain NP-Hard and NP-Completeness with examples.

7. Explain about assignment problem using branch and bound with example.

8. Discuss the solution for travelling salesman problem using branch & bound
technique.
9. Discuss the decision trees for sorting algorithms.

CS8493- OPERATING SYSTEM

UNIT – I

PART-A

1. What is an Operating system?

An operating system is a program that manages the computer hardware. It also

provides a basis for application programs and act as an intermediary between a
user of a computer and the computer hardware. It controls and coordinates the
use of the hardware among the various application programs for the various
users.

2. List the services provided by an Operating System?

Program execution

I/O Operation

File-System manipulation

Communications