Showing posts with label DAA. Show all posts
Showing posts with label DAA. Show all posts

January 03, 2019

Design and Analysis of Algorithms - MCQS 2

                                          
Question
What is an optimal Huffman code for alphabet b of the following set of frequencies
 a: 45, b:13, c:12, d:16, e:9, f:5
Select one:
a. 111
b. 101
c. 100
d. 001

The correct answer is:101

Question
In flow networks Residual capacity Cf (u,v)=
Select one:
a. c(u,v) – f(u,v)
b. t(u,v) – s(u,v)
c. f(u, v) – c(u,v)
d. s(u,v) – t(u, v)

The correct answer is:c(u,v) – f(u,v)

Question
In Ford-Fulkerson algorithm, flow of the augmenting path is selected based on
Select one:
a. cf(p) =min{ cf (u,v):(u,v)is in f-P }
b. cf(p) =min{ cf (u,v):(u,v)is in p }
c. cf(p) =max{ cf (u,v):(u,v)is in f-P }
d. cf(p) =max{ cf (u,v):(u,v)is in p }

The correct answer is: cf(p) =min{ cf (u,v):(u,v)is in p }

Question
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Select one:
a. Queue
b. Heap
c. Stack
d. B-Tree

The correct answer is:Queue

Question
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
Select one:
a. Warshall’s algorithm
b. Performing a DFS starting from S.
c. Dijkstra’s algorithm starting from S.
d. Performing a BFS starting from S

The correct answer is:Performing a BFS starting from S

Question
Consider the decision problem 2CNFSAT defined as follows:

Select one:
a. NP-hard, but not NP-complete.
b. solvable in constant time since any input instance is satisfiable.
c. NP-Complete.
d. solvable in polynomial time by reduction to directed graph reachability

The correct answer is:solvable in polynomial time by reduction to directed graph reachability

Question
Find the Running Time of the fastest algorithm to calculate the shortest path between any two vertices of a graph where all edges have equal weights.
Select one:
a. 0(V  log2V+E )
b. 0 (E+V)
c. 0(V log V2+E)
d. 0 (V+E) log2V

The correct answer is:0 (E+V)

Question
Match the following
            Group A                                                                      Group B
a) Dijkstra's single shortest path                                     p) Dynamic Programming
b) Bellmen Ford's single shortest path algorithm           q) Backtracking
c) Floyd Warshell's all pair shortest path algorithm        r) Greedy Algorithm
Select one:
a. a-p,  b-r, c-q
b. a-p,  b-p, c-p
c. a-r,  b-p, c-p
d. a-r,  b-q, c-p

The correct answer is: a-r,  b-p, c-p

Question
Match the following:

              List – I                           List – II

         1 Quick Sort              a Divide and Conquer

         2 Graph colouring     b Greedy

         3 String editing          c Dynamic Programming
                                     
         4 Prim’s Algorithm   d Back tracking
Select one:
a. 1-a, 2-c, 3-b, 4-d
b. None of these
c. 1-a, 2-d, 3-c, 4-b
d. 1-b, 2-a, 3-d, 4-c

The correct answer is: 1-a, 2-d, 3-c, 4-b

Question
Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable
   from the source.
Select one:
a. P Only
b. Neither P nor Q
c. Both P and Q
d. Q Only

The correct answer is: Q Only

Question
The time required to find shortest path in a graph with n vertices and e edges is
Select one:
a. O (e)
b.  O (e2)         
c.  O (n)   
d.  O (n2

The correct answer is: O (n2)

Question
There are 5 items as follows

Select one:
a. 260 $
b. 270 $
c. 290$
d. 250$

The correct answer is:260$

Question
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
Select one:
a. 44000
b. 19000
c. 25000
d. 248000

The correct answer is:19000

Question
A simple Graph G = L U R, set of 2 non-empty vertices and each vertex from L  has an edge to atleast one vertex of R, is called as
Select one:
a.  Bifocal graph
b. Bipartite Graph
c. Complete graph
d. Flow-network graph

The correct answer is: Bipartite Graph

Question
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
Select one:
a. Π is NP-complete
b. Π is neither NP-hard, nor in NP
c. Π is NP-hard but not NP-complete
d. Π is in NP, but is not NP-complete

The correct answer is:Π is NP-complete

Question
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
       = expr1, if i,j > 0 and X[i-1] = Y[j-1]
       = expr2, if i,j > 0 and X[i-1] != Y[j-1]
Select one:
a. expr2 ≡ max(l(i-1,j-1),l(i,j))
b. expr2 ≡ max(l(i-1, j), l(i, j-1))
c. expr1 ≡ l(i-1, j) + 1
d. expr1 ≡ l(i, j-1)

The correct answer is: expr2 ≡ max(l(i-1, j), l(i, j-1))

Question
If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
Select one:
a. O(log n)
b. O(n3   
c. O(n log n)   
d. O(n2)

The correct answer is: O(n3)

Question
Kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
Select one:
a. edges,edges
b. vertex,vertex
c. edges,vertex
d. vertex,edges

The correct answer is: edges,vertex

Question
For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
Select one:
a. O(NW), O(N)
b. O(NW), O(N+W)
c. O(N), O(NW)
d.   O(N+W), O(NW)

The correct answer is:O(NW), O(N+W)

Question
Consider the following two problems of graph.
1) Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2) Given a graph, find if the graph has a cycle that visits every edge exactly once. Which of the following is true about above two problems
Select one:
a. Both problems belong to P set
b. Problem 1 belongs to P set and 2 belongs to NP Complete set
c. Problem 1 belongs NP Complete set and 2 belongs to P
d. Both problems belong to NP complete set

The correct answer is: Problem 1 belongs NP Complete set and 2 belongs to P

November 05, 2018

Design and Analysis of Algorithms - Mid Sem Solution


Question 1A)
The time factor when determining the efficiency of algorithm is measured by
a) Counting microseconds
b) Counting the number of key operations
c) Counting the number of statements
d) Counting the kilobytes of algorithm

Answer: b
Justification: It is hardware and language independent , rest are dependent on hardware or on software

1B) The concept of order Big O is important because
a) It can be used to decide the best algorithm that solves a given problem
b) It determines the maximum size of a problem that can be solved in a given  amount of time
c) It is the lower bound of the growth rate of algorithm
d) Both A and B

Answer: a
Justification: We know that Big Oh notation is used in time complexity . the reason why we called Big Oh because it says "at any condition this is worst time that an algorithm could take " where as Big Omega says its is "best time that you can get , You cant get better than this.

1C) In worst case Quick Sort has order
A) O (n log n)            B. O (n2 /2)                C. O (log n)                         D. O (n2 /4)

Answer: A
Justification: In the worst case of quick sort has order O(n2). Quick sort is the quickest comparison-based sorting algorithm. It is very fast and requires less additional space, only O(n log n) space is required.

1D) Consider the following program segment. What is the Space complexity?
Begin
i=0;
S=0;
S=s+1;
Return s;
End

Answer: [If i,S considered as integers] => Space Complexity = 4 +(4*2)  = 12 bytes, where additional 4 bytes is for return value

To calculate the Space complexity of an algorithm, we need to follow the below instruction first:
It is the amount of memory used by the algorithm (including the input values to the algorithm) to execute and produce the result.

Space Complexity = Auxiliary Space + Input space

Calculating the Space Complexity:

For calculating the space complexity, we need to know the value of memory used by different type of datatype variables, which generally varies for different operating systems, but the method for calculating the space complexity remains the same.
TypeSize
bool, char, unsigned char, signed char1 byte
short, unsigned short,2 bytes
float, int, unsigned int, long, unsigned long4 bytes
double, long double, long long8 bytes
1E)  What is the time complexity of optimal binary search
(1) a)O(n) b) O(1) c)O(2n/2 d) O(n2)

Answer: d
Justification:
An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

For Reference:
The complexity of linear search algorithm is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)

Answer: a
Justification: It refers to n values complexity in the algorithm which can be reduced by choosing the other algorithms.

The complexity of Bubble sort algorithm is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)

Answer: c
Justification: Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.

Question
Randomised algorithms are also called as __________________ and whose behavior is dependent  on  _______________ in decision making as part of its logic

Answer: probabilistic algorithm and randomness

Question:
Match the following    


Problem

Recurrence Equation
1
Binary Search 
A
tn – tn-1 = 1
2
Merge Sort
B
T(n)=2T(n/2)+n-1
3
Sequential Search
C
tn =  tn-1 + n
4
Factorial
D
T(n)=7T(n/2)+18(n/2)2
5
Strassen Matrix Multiplication
E
T(n)=T(n/2)+1
6
Selection Sort
F
T(n)=T(n/2)+n-1









Answer:

T(n) = Time Complexity
 

Problem

Recurrence Equation
1
Binary Search
E
T(n)=T(n/2)+1
2
Merge Sort
B
T(n)=2T(n/2)+n-1
3
Sequential Search
A
tn – tn-1 = 1
4
Factorial
F
T(n)=T(n/2)+n-1
5
Strassen Matrix Multiplication
D
T(n)=7T(n/2)+18(n/2)2
6
Selection Sort
C
tn =  tn-1 + n

Additional Reference:


7
Insertion sort
-
T(N) = T(N-1) + N-1
8
Tree traversal
-
T(n) = 2T(n/2) + 1
9
Quicksort
-
(n) = 2T(n/2) + n
10
Master Theorm
-
T(n)=aT(n/b)+f(n)












Tip:
Merge Sort: The merge sort algorithm deals with the problem of sorting a list of n elements. It is able to sort a list of n elements in O(n log n) run-time, which is considerably faster than insertion sort, which takes O(n2).
Merge sort uses a divide and conquer method:
1. If the length of the list is 1, the list is sorted. Return the list.
2. Otherwise, split the list in two (roughly) equal halves and then recursively merge sort the two halves
3. Merge the two sorted halves into one sorted list.

November 01, 2018

DESIGN AND ANALYSIS OF ALGORITHMS - Comprehensive Paper Solution

Question:
Assume that there are two algorithms A and B for a given problem P. The time complexity functions of algorithms A and B are 5n and log2n    respectively. Which algorithm should be selected assuming that all other conditions remain the same for both the algorithms?

Solution:
Assuming that all conditions remain the same for both algorithms, the best algorithm takes less time when the input is changed to a larger value. Results obtained employing different values of n are shown below:

October 23, 2018

Design and Analysis of Algorithms - MCQS

Question

If one was to apply Master theorem to recurrence equation T(n)=3.T(n/2)+n^2, what would be the values of a and b?

Select one:
a. a=3,b=3
b. a=3,b=2
c. A=2,b=2
d. a=2,b=3

The correct answer is: a=3,b=2

Question 
Time complexity of knapsack 0/1

where n is the number of items and W is the capacity of knapsack.

Select one:
a. O(nW)
b. O(n)
c. O(W)

The correct answer is: O(nW)

Question 
The complexity of searching an element from a set of n elements using Binary search algorithm is

Select one:
a. O(n log n)
b. O(n2)
c. O(n)
d. O(log n)

The correct answer is: O(log n)

Question 
Time complexity of matrix chain multiplication

Select one:
a. O(n2)
b. O(nlogn)
c. O(n)
d. O(n3)

The correct answer is: O(n3)

Question 
Time complexity of LCS

Select one:
a. O(n!)
b. O(m!)
c. O(mn)

The correct answer is: O(mn)

Question 
Apply Master theorem to T(n)=3.T(n/2)+n^2 and write what is f(n)

Select one:
a. f(n)=n/2
b. f(n)=n/2+n^2
c. f(n)=n^2
d. f(n)=3n/2

The correct answer is: f(n)=n^2

Question
Data Structure used for the Merge Sort

Select one:
a. Two Pointers and an Extra Array
b. Two Pointers
c. 2N/2 pointers and N/2 Extra Arrays
d. Two pointers and N Extra Arrays

The correct answer is: Two Pointers and an Extra Array

Question 
Steps of Divide and Conquer approach

Select one:
a. Combine, Divide and Conquer
b. Divide, Combine and Conquer
c. Combine, Conquer and Divide
d. Divide, Conquer and Combine

The correct answer is: Divide, Conquer and Combine

Question 
Which of the following sorting algorithms does not have a worst case running time of O(n2) ?

Select one:
a. Quick sort
b. Bubble sort
c. Insertion sort
d. Merge sort

The correct answer is: Merge sort

Question 
Data Structure used for the Merge Sort

Select one:
a. Two pointers and N Extra Arrays
b. Two Pointers and an Extra Array
c. Two Pointers
d. 2N/2 pointers and N/2 Extra Arrays

The correct answer is: Two Pointers and an Extra Array

Question
RANDOMIZE-IN-PLACE(A)
n=A.length
For i=1 to n
Swap A[i] with A[RANDOM(I,n.]
The above procedure RANDOMIZE-IN-PLACE(A) computes

Select one:
a. a different deliberate permutation
b. a uniform deliberate permutation
c. a uniform random permutation
d. a different random permutation

The correct answer is: a uniform random permutation

Question 
Time complexities of three algorithms are given. Which should execute the slowest for large values of N?

Select one:
a. O(N ½)
b. O(N)
c. O(log n)

The correct answer is: O(N)

Question 
If length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6.
length  | 1   2   3   4   5   6   7   8
--------------------------------------------
price    | 1   5   8   9  10  17  17  20
What is the worst case running time for the above problem

Select one:
a. O(log n)
b. O(n2)
c. O(n log n)
d. O(2n)

The correct answer is: O(n2)

Question 

71. PERMUTE-BY-SHORTING(A)
n=A.length
Let P[1…n] be a new array
For i=1 to n
    P[i]=RANDOM(1,n3)
Sort A, using P as sort keys
The time complexity of above algorithm is

Select one:
a. T(n ln n)
b. T(n)
c. T(n3) In
d. T(n2)

The correct answer is: T(n ln n)

Question 
 ______ is a condition that is always true at a particular point in an algorithm.

Select one:
a. assertion
b. exception
c. constant
d. invariant

The correct answer is: invariant

Question 
RANDOMIZE-IN-PLACE(A)
n=A.length
For i=1 to n
Swap A[i] with A[RANDOM(I,n.]
The time complexity of above algorithm is

Select one:
a. O(n)
b. O(n2)
c. O(n ln n)
d. O(n3)

The correct answer is: O(n)

Question 
Merge Sort divides the list in

Select one:
a. Two parts, may not be equal
b. N parts, may not be equal
c. N equal parts
d. Two equal parts

The correct answer is: Two equal parts

Question 
Time Complexity of Optimal binary search tree.

Select one:
a. O(logn)
b. O(n!) In
c. O(n)

The correct answer is: O(logn)

Question 
Division Pattern of Problems in Divide and Conquer approach

Select one:
a. Random
b. Parallel
c. Recursive
d. Iterative

The correct answer is: Recursive

Question
In dynamic programming, the output to stage n become the input to

Select one:
a. stage n itself
b. stage n-1
c. stage n-2
d. stage n+1 In

The correct answer is: stage n-1

Question 
RANDOMIZE-IN-PLACE(A)
n=A.length
For i=1 to n
Swap A[i] with A[RANDOM(I,n)]
The above procedure RANDOMIZE-IN-PLACE(A) permutation occurs with probability

Select one:
a. Probability n
b. Probability n2
c. Probability n!
d. Probability 1/n!

The correct answer is: Probability 1/n!

Question 
Which case of Master’s theorem is applicable in the recurrence relation T(n)=0.5*T(n/2)+1/n?

Select one:
a. Case 3
b. Case 2
c. Case 1
d. Master’s theorem is not applicable

The correct answer is: Master’s theorem is not applicable

Question 
In the development of dynamic programming the value of an optimal solution is computed in

Select one:
a. Top up fashion
b. Bottom up fashion
c. In any way

The correct answer is: Bottom up fashion

Question 
Run Time of Merge Sort is

Select one:
a. BIG O of N log N
b. Theta of N log N
c. Gamma of n log N
d. Omega of N log N

The correct answer is: Theta of N log N

Question 
The number of operations in Matrix multiplications M1, M2, M3, M4 and M5 of sizes 5X10, 10X100, 100X2, 2X20 and 20X50

Select one:
a. 4600
b. 12890
c. 6900
d. 5830

The correct answer is: 4600

Question 
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
  f1(n) = 2^n
  f2(n) = n^(3/2)
  f3(n) = nLogn
  f4(n) = n^(Logn)

Select one:
a. f2, f3, f1, f4
b. f3, f2, f1, f4
c. f3, f2, f4, f1
d. f2, f3, f4, f1

The correct answer is: f3, f2, f4, f1

Question 
The running time of quick sort depends on the selection of.

Select one:
a. Number of input
b. Arrangements of the elements
c. Selection of pivot elements
d. Number of passes

The correct answer is: Selection of pivot elements

Question 
RANDOMIZED-HIRE – ASSISTANT (n)
Randomly permute the list of candidates
Best=0
For i=1 to n
    interview candidate i
    If candidate I is better than candidate best
        best=i
        hire candidates i
    The expected hiring cost of the procedure is.

Select one:
a. O( n2)
b. O(n log n)
c. O(ln n)
d. O( n)

The correct answer is: O(ln n)

Question 
In dynamic programming, the output to stage n become the input to

Select one:
a. Objective function
b. Optimum solution
c. Feasible solution
d. Decision stages

The correct answer is: Decision stages

Question 
Master theorem applies to recurrences of the form (a=1 and b>1) are two constants.

Select one:
a. T(n)=n.T(n/2)+b.f(n)
b. T(n)=n.T(n-3)+b
c. T(n)=a.T(n-1)+b
d. T(n)=a.T(n/b)+f(n)

The correct answer is: T(n)=a.T(n/b)+f(n)

Question 
A sort which relatively passes through a list to exchange the first element with any elementless than it and then repeats with a new first element is called________.

Select one:
a. Insertion sort
b. Bubble sort
c. heap sort
d. Quick sort

The correct answer is: Insertion sort