CS502- Fundamentals of Algorithms Current Finial term paper

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

 If a problem is in NP-complete, it must also be in NP.

       ► True

       ► False

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

   The Huffman algorithm finds a optimal solution.

       ► True

       ► False

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

  The Huffman algorithm finds an exponential solution

       ► True

       ► False

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

 The Huffman algorithm finds a polynomial solution

       ► True

       ► False

  Question No: 5    ( 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: 6    ( Marks: 1 )    - Please choose one

   The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the prefix of any other.

       ► True

       ► False

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

 Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.

       ► True

       ► False

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

Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.

       ► True

       ► False

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

The term “coloring” came form the original application which was in architectural design.

       ► True

       ► False

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

In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.

 ► True

► False

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

 Dijkstra’s algorithm is operates by maintaining a subset of vertices

 ► True

► False 

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

We do sorting to,

       ► keep elements in random positions

       ► keep the algorithm run in linear order

       ► keep the algorithm run in (log n) order

       ► keep elements in increasing or decreasing order

   

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

 After partitioning array in Quick sort, pivot is placed in a position such that

       ► Values smaller than pivot are on left and larger than pivot are on right

       ► Values larger than pivot are on left and smaller than pivot are on right

   ► Pivot is the first element of array

       ► Pivot is the last element of array

   

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

Merge sort is stable sort, but not an in-place algorithm

 ► True

► False

   

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

 A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute.

      ► O (q)

       ► O (1)

       ► O (n²)

       ► O (n³)

Question No: 16    ( 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: 17    ( Marks: 1 )    - Please choose one

Merge sort requires extra array storage,

• True  
• False

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

The Huffman codes provide a method of encoding data inefficiently when coded using

ASCII standard.

• True
• Falase      

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

Using ASCII standard the string abacdaacac will be encoded with __________ bits.

• 80
• 160
• 320
• 100

   

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

 Using ASCII standard the string abacdaacac will be encoded with 160 bits.

• True
• False 

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

 Using ASCII standard the string abacdaacac will be encoded with 10 bytes.

• True
• False  

Question No: 22    ( 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: 23    ( Marks: 1 )    - Please choose one

 Huffman algorithm uses a greedy approach to generate an prefix code T that minimizes

the expected length B (T) of the encoded string.

• True  
• False

   

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

 Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative and there are negative cost cycles.

• True 
• False

  

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

   

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

   

Question No: 27    ( Marks: 2 )

 explain 2-d maxima problem mathematically or algrithmically.

   

Question No: 28    ( Marks: 2 )

 Differentiate between back edge and forward edge.

   

Question No: 29    ( Marks: 2 )

Question No: 30    ( Marks: 2 )

Question No: 31    ( Marks: 3 )

Question No: 32    ( Marks: 3 )

Question No: 33    ( Marks: 3 )

Question No: 34    ( Marks: 5 )

 Suppose you could prove that an NP-complete problem can not be solved in polynomial time. What would be the consequence?

Question No: 48    ( Marks: 3 )

Recursive explanation of dynamic programming.

Question No: 49   ( Marks: 5 )

What is the cost of the following graph?

Cost =33

Question No: 50 ( Marks: 5 )

. 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

Question No: 51 ( Marks: 5 )

Floyd Warshal algorithm with three recursive steps

Question No: 52 ( Marks: 5 )