FINALTERM EXAMINATION
Spring 2009
CS502- Fundamentals of Algorithms

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


Sponsored Links

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
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


For Complete Paper Please Download the file

CS502_01_FINAL_Spring 2009-1.pdf