CS 502 MCQ's Principles of Algorithm free mcq's solution for Quiz, Final Term&MD

[admin]

CS 502 MCQ's Principles of Algorithm free mcq's solution for Quiz, Final Term&MID Term Exams

[/color]


The sieve technique is a special case, where the number of sub problems is just

•   5
•   Many
•   1
•   few

Question No: 1    ( Marks: 1 )    - Please choose one
  Random access machine or RAM is a/an
       ? Machine build by Al-Khwarizmi
       ? Mechanical machine
       ? Electronics machine
       ? Mathematical model
   
Question No: 2    ( Marks: 1 )    - Please choose one
  _______________ is a graphical representation of an algorithm
       ?   notation
       ?  notation
       ? Flowchart
       ? Asymptotic notation
   
Question No: 3    ( Marks: 1 )    - Please choose one
  A RAM is an idealized machine with ______________ random-access memory.
       ? 256MB
       ? 512MB
       ? an infinitely large
       ? 100GB
   
Question No: 4    ( Marks: 1 )    - Please choose one
  What type of instructions Random Access Machine (RAM) can execute? Choose best answer
       ? Algebraic and logic
       ? Geometric and arithmetic
       ? Arithmetic and logic
       ? Parallel and recursive
   
Question No: 5    ( Marks: 1 )    - Please choose one
  What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?
       ? 
       ? 
       ? 
       ? 
   
Question No: 6    ( Marks: 1 )    - Please choose one
  What is the solution to the recurrence T(n) = T(n/2)+n .

       ? O(logn)
       ? O(n)
       ? O(nlogn)
       ? O(n2)
   
Question No: 7    ( Marks: 1 )    - Please choose one
  Consider the following code:
   For(j=1; j<n;j++)
      For(k=1; k<15;k++)
         For(l=5; l<n; l++)
         {
            Do_something_constant();
         }
What is the order of execution for this code.
       ? O(n)
       ? O(n3)
       ? O(n2 log n)
       ? O(n2)
   
Question No: 8    ( Marks: 1 )    - Please choose one
  Consider the following Algorithm:
Factorial (n){
   if (n=1)
      return 1
   else
       return (n * Factorial(n-1))
}
Recurrence for the following algorithm is:
       ? T(n) = T(n-1) +1
       ? T(n) = nT(n-1) +1
       ? T(n)= T(n-1) +n
       ? T(n)=T(n(n-1)) +1
   
Question No: 9    ( Marks: 1 )    - Please choose one
  What is the total time to heapify?
       ? ?(log n)
       ? ?(n log n)
       ? ?(n2 log n)
       ? ?(log2 n)
   
Question No: 10    ( Marks: 1 )    - Please choose one
  When we call heapify then at each level the comparison performed takes time
       ? It will take ? (1)
       ? Time will vary according to the nature of input data
       ? It can not be predicted
       ? It will take ? (log n)
   
Question No: 11    ( Marks: 1 )    - Please choose one
  In Quick sort, we don’t have the control over the sizes of recursive calls
       ? True
       ? False
       ? Less information to decide
       ? Either true or false
   
Question No: 12    ( Marks: 1 )    - Please choose one
  Is it possible to sort without making comparisons?
       ? Yes
       ? No
   
Question No: 13    ( Marks: 1 )    - Please choose one
  If there are ? (n2) entries in edit distance matrix then the total running time is
       ? ? (1)
       ? ? (n2)
       ? ? (n)
       ? ? (n log n)
   
Question No: 14    ( Marks: 1 )    - Please choose one
  For Chain Matrix Multiplication we can not use divide and conquer approach because,
       ? We do not know the optimum k
       ? We use divide and conquer for sorting only
       ? We can easily perform it in linear time
       ? Size of data is not given
   
Question No: 15    ( Marks: 1 )    - Please choose one
  The Knapsack problem belongs to the domain of _______________ problems.
       ? Optimization
       ? NP Complete
       ? Linear Solution
       ? Sorting
   
Question No: 16    ( Marks: 1 )    - Please choose one
  Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.
Item   Value   Weight
1   60   10
2   100   20
3   120   30
The optimal solution is to pick
       ? Items 1 and 2
       ? Items 1 and 3
       ? Items 2 and 3
       ? None of these



3. ______________ graphical representation of algorithm.
> asymptotic
>. flowchart
4. who invented the quick sort
C.A.R. Hoare

5. function is given like 4n^4+ 5n^3+n what is the run time of this
•    (n^4)
•    (n^3)
•    (4n^4+ 5n^3)
•    (4n^4+ 5n^3)
6. main elements to a divide-and-conquer
Divide---->conquer---------->combine
7. T(n)={4 if n=1, otherwise T(n/5)+3n^2
what is the answer if n=5
answer is 79
8. Merge sort is a stable algorithm but not an in-place algorithm.
>True
>false
_______________ is a graphical representation of an algorithm   
•   notation 
•   Flowchart 
•   Asymptotic notation 
•    notation   
Question No: 2      ( Marks: 1 ) - Please choose one

Which of the following is calculated with Big o notation?   
•   Lower bounds 
•   Upper bounds 
•   Both upper and lower bound 
•   Medium bounds

Question No: 3      ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?   
•   The array elements form a heap 
•   Elements in each half of the array are sorted amongst themselves 
•   Elements in the first half of the array are less than or equal to elements in the
second half of the array 
•   None of the above

Question No: 4      ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?   
•   Hoare 
•   Sedgewick 
•   Mellroy 
•   Coreman     

Question No: 5      ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1   
•   O(logn) 
•   O(n) 
•   O(nlogn) 
•   O(2n)   

FINALTERM EXAMINATION
Fall 2008
CS502- Fundamentals of Algorithms (Session - 1)
Marks: 75
Question No: 1 ( Marks: 1 ) - Please choose one
_______________ is a graphical representation of an algorithm
notation
Flowchart
Asymptotic notation
notation

Question No: 2 ( Marks: 1 ) - Please choose one
Which of the following is calculated with Bigo notation?
Lower bounds
Upper bounds
Both upper and lower bound
Medium bounds

Question No: 3 ( Marks: 1 ) - Please choose one
Merge sort makes two recursive calls. Which statement is true after these recursive calls
finish, but before the merge step?
The array elements form a heap
Elements in each half of the array are sorted amongst themselves
Elements in the first half of the array are less than or equal to elements in the
second half of the array
None of the above

Question No: 4 ( Marks: 1 ) - Please choose one
Who invented Quick sort procedure?
Hoare
Sedgewick
Mellroy
Coreman



Question No: 5 ( Marks: 1 ) - Please choose one
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
O(logn)
O(n)
O(nlogn)
O(2n)


Question No: 6 ( Marks: 1 ) - Please choose one(Huffman tree is missing)
Consider the following Huffman Tree
The binary code for the string TEA is
10 00 010
011 00 010
10 00 110
11 10 110


Question No: 7 ( Marks: 1 ) - Please choose one
If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
v edges.
v e + 5 edges
v + e edges.
None of these


Question No: 8 ( Marks: 1 ) - Please choose one
Can an adjacency matrix for a directed graph ever not be square in shape?
Yes
No



Question No: 9 ( Marks: 1 ) - Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any
_______________.
Pointers
constants
variables
functions


Question No: 10 ( Marks: 1 ) - Please choose one
Merge sort requires extra array storage,
True
False


Question No: 11 ( Marks: 1 ) - Please choose one
Non-optimal or greedy algorithm for money change takes____________
O(k)
O(kN)
O(2k)
O(N)

[admin]

 
•   

42:

Question No: 12 ( Marks: 1 ) - Please choose one
The Huffman codes provide a method of encoding data inefficiently when coded using
ASCII standard.
True
False


Question No: 13 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with __________ bits.
80
160
320
100


Question No: 14 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 160 bits.
True
False


Question No: 15 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 320 bits.
True
False


Question No: 16 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 100 bits.
True
False


Question No: 17 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 32 bytes
True
False


Question No: 18 ( Marks: 1 ) - Please choose one
The greedy part of the Huffman encoding algorithm is to first find two nodes with
smallest frequency.
True
False


Question No: 19 ( Marks: 1 ) - Please choose one

The greedy part of the Huffman encoding algorithm is to first find two nodes with
character frequency
True
False

Question No: 20 ( Marks: 1 ) - Please choose one
Huffman algorithm uses a greedy approach to generate an antefix code T that minimizes
the expected length B (T) of the encoded string.
True
False

Question No: 21 ( Marks: 1 ) - Please choose one
Depth first search is shortest path algorithm that works on un-weighted graphs.
True
False

Question No: 22 ( Marks: 1 ) - Please choose one
Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative
and there are no negative cost cycles.
True
False


Question No: 23 ( Marks: 1 ) - Please choose one
Dijkestra s single source shortest path algorithm works if all edges weights are negative
and there are no negative cost cycles.

True
False
 hb


Question No: 24 ( Marks: 1 ) - Please choose one
Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the
algorithm is in the clever recursive formulation of the shortest path problem.
True
Flase



Question No: 25 ( Marks: 1 ) - Please choose one
Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive
evaluation by generating a table for
k
ij d
True
Flase


Question No: 26 ( Marks: 1 ) - Please choose one
The term coloring came form the original application which was in map drawing.
True
False



Question No: 27 ( Marks: 1 ) - Please choose one
In the clique cover problem, for two vertices to be in the same group, they must be
_______________each other.
Apart from
Far from
Near to
Adjacent to

Question No: 28 ( Marks: 1 ) - Please choose one
In the clique cover problem, for two vertices to be in the same group, they must be apart
from each other.
True
False


Question No: 29 ( Marks: 1 ) - Please choose one
The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s
algorithm uses a different key.
True
False


Question No: 30 ( Marks: 1 ) - Please choose one
The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s
algorithm uses a same key.
True
False


Question No: 31 ( Marks: 1 )
Do you think greedy algorithm gives an optimal solution to the activity scheduling
problem?
yes, greedy algorithm gives an optimal solution to the activity scheduling
problem. as  we have the data as a whole ,and activity a1 must be started at a given  start time and ends at a given finish time. all the intermediate activities who overlap will be excluded automatically as no new activity will be selected as our data till the finish of last activity. so this greediness of algorithm gives us the optimal solution.

Question No: 32 ( Marks: 1 )
Define Forward edge

A forward edge is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Question No: 33 ( Marks: 2 )
Is there any relationship between number of back edges and number of cycles in DFS?

A back edge connects a vertex to an ancestor in a DFS-tree. No back edges means no cycles. But there is some simple relationship Between the number of back edges and the number of cycles. For example, a DFS tree may only have a single back edge, and there may anywhere from one up to an exponential number of simple cycles in the graph.




Question No: 34 ( Marks: 2 )
What is the common problem in communications networks and circuit designing?

Common problem in communications networks and circuit design is that of connecting together a set of nodes by a network of total minimum length. The length is the sum of lengths of connecting wires.

Question No: 35 ( Marks: 3 )
Let the adjacency list representation of an undirected graph is given below.
Explain what general property of the list indicates that the graph has an isolated
vertex.
a b c e
b a d
c a d e f
d b c f
e a c f
f c d e
g

Ans:
A graph is connected if every vertex can reach
Every other vertex. and is isolated if any node has not connected to other vertex ,here’s “g” is the node that is not connected with any other vertex. This general property of the list indicates that the graph has an isolated vertex.