CS502 Fundamentals of Algorithms Spring 2009 Final Term Paper

[viki]

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
  

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 (Size: 91.83 KB / Downloads: 1,483)