DESIGN AND ANALYSIS OF ALGORITHMS
TWO MARK QUESTIONS
UNIT I INTRODUCTION
1. Define algorithm
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
2. What are the properties of an algorithm?
Finiteness
Input
Output
Effectiveness
Non Ambiguity
Range of Input
Multiplicity
Speed
3. What are the methods are used for specifying an algorithm?
Natural languages
Flow chart
Pseudo code
4. What are the two factors to measure the efficiency of an algorithm?
Time efficiency-> The amount of time to take execute the algorithm’s basic operation
Space efficiency-> The amount of memory required to store the algorithm and the amount of memory required to store the input for that algorithm.
5. How to measure the running time?
• Find the basic operation of the algorithm.
• Compute the time required to execute the basic operation.
• Compute how many times the basic operation is executed. The Time complexity calculated by the following formula
T(n) = Cop * C(n) Where,
Cop – Constant (The amount of time required to execute the basic operation)
C(n) – How many times the basic operation is executed.
6. Name the three asymptotic Notations.
(i) Big Oh
(ii) Big Omega
(iii) Big Theta
7. Define Big-Oh Notation.
A function t(n) is said to be in O(g(n)), denote t(n) € O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integer n0 such that
t(n) ≤ c.g(n) for all n ≥ n0.
8. Define Big-Omega Notation.
A function t(n) is said to be in Ω (g(n)), denote t(n) € Ω (g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integer n0 such that
t(n) ≥ c.g(n) for all n ≥ n0.
9. Define Big Theta (or) θNotation
A function t(n) is said to be in O(g(n)), denote t(n) €θ(g(n)), if t(n) is bounded both above andbelow by some constant multiple of g(n) for all large n, i.e., if there exists some positive constantc1 and c2 and some nonnegative integer n0 such that
C2.g(n) ≤ t(n) ≥ c1.g(n) for all n ≥ n0.
10. What do you mean by divide and conquer?
The divide-and-conquer strategy solves a problem by:
1. Breaking it into sub problems that are themselves smaller instances of the same type of problem
2. Recursively solving these sub problems
3. Appropriately combining their answers
11. Write the examples of Divide and Conquer.
Binary Search
Quick Sort
Merge Sort
12. Write down the formula for finding the time complexity using divide and conquer.
T(n)=a(n/b)+f(n)
Where, T(n) is the running time of the given algorithm
A is the number of sub problems
B is the sub problem size
F(n) is the time to combine the solutions of sub problems
13. Write an algorithm for binary search.
procedure: int binarySearch(int arr[], int value, int left, int right)
while (left <= right) do
middle = (left + right) / 2;
if (arr[middle] == value)
return middle;
else if (arr[middle] > value)
right = middle - 1;
else
left = middle + 1;
return -1;
14. Compare the time complexity of quick sort, heap sort, Merge sort and Selection sort.
Analysis / Quick / Merge / Heap / SelectionBest / O(nlogn) / O(nlogn) / O(nlogn) / O(n2)
Average / O(nlogn) / O(nlogn) / O(nlogn) / O(n2)
Worst / O(n2) / O(nlogn) / O(nlogn) / O(n2)
15. Write an algorithm for selection sort.
procedure SELECTION_SORT (A)
for i ← 1 to n-1 do
min j ← i;
min x ← A[i]
for j ← i + 1 to n do
If A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x
16. Define Heap.
Heap is a binary tree that is completely filled on all levels except possibly the lowest, which is filled from the left to right. It is also called as a complete binary tree.
17. List out the drawbacks of binary search algorithm.
The disadvantage of binary search in any language is that you must provide an ordered list, usually an array, for the algorithm to search. Arrays are either static in size or, if dynamic, require special processing when they grow in size. A linked list does not work, because you need to make random access to the elements.
18. Name any four algorithm’s basic efficiency classes.
O(1)
O(n)
O(logn)
O(n logn)
O(n2)
O(n3)
O(n!)
O(2n)
UNIT II GREEDY METHOD
1. Define greedy algorithm.
Greedy method is an approach to find the optimized solutions for the given problem. The solutions are constructed through a sequence of steps, each step expanding a partially constructed solution so far, until a complete solution to the problem is reached.
2. What are the applications of greedy method?
Optimal Storage on tapes
Knapsack problem
Minimum Spanning Tree
Finding Shortest Path
3. Write an algorithm for optimanl storage on tapes.
Pseudo tapes(n,m) // n is the no. of programs and m is the no. of tapes
{
j=0;
for(i=1 to n do)
{
write ("append", i "to the permutation of the tape", j)
j=(j+1) mod m
}
}
4. Define Knapsack problem
Knapsack problem is one of the optimization problems in which given a set of items each with a cost and a value, determine the number of each item to include in a collection so that the total cost does not exceed some given cost and the total value is as large as possible.
5. Write an algorithm fro Knapsack problem.
Algorithm Knapsack_greedy(W,n)
For i:=1 to n do
If(w[i]<W) then
X[i]=1.0
W=W-w[i]
If(i<=n) then
X[i]=W/w[i];
6. What are the three different ways to implement knapsack problem?
Greedy method
Backtracking
Branch and Bound
7. Define Minimum Spanning Tree.
A minimum spanning tree is a spanning tree, but has weights or lengths associated with the edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum.
Graph Minimum Spanning Tree
8. What are the methods are used to implement the Minimum Spanning Tree?
Prim’s algorithm
Kruskal’s algorithm
9. Define Prim’s algorithm( For Kruskal’s algorithm also).
Prim's algorithm is an algorithm that finds a minimum spanning tree for a connectedweightedundirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. Prim's algorithm is an example of a greedy algorithm.
10. Compare Prims and Kruskal’s algorithm
PrimKruskal
Looks Harder Looks easier
Easy to implementHard to implement
More efficientLess efficient
11. Define Dijkstras algorithm.
Dijkstra’s algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative. Dijkstra's algorithm keeps two sets of vertices:
S the set of vertices whose shortest paths from the source havealready been determined
V-Sthe remaining vertices.