Today's Final paper of cs502

[maz01]

Dear Fellows this is my paper of cs502 16july,2011. prepare it and pray for my further success.

[Xpert]

Thank you so much for sharing this paper..... please other students also share your paper


[FONT=&quot]Question No: 1 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]] [/FONT][FONT=&quot]If a problem is in NP-complete, it must also be in NP.[/FONT]
[FONT=&quot]►[/FONT] [FONT=&quot]True[/FONT]
[FONT=&quot] ► False[/FONT]

[FONT=&quot]Question No: 2 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot] The Huffman algorithm finds a optimal solution.[/FONT]

[FONT=&quot]►[/FONT] [FONT=&quot]True[/FONT]

[FONT=&quot] ► False[/FONT]

[FONT=&quot]Question No: 3 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot] The Huffman algorithm finds an exponential solution[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot]►[/FONT] [FONT=&quot]False[/FONT]

[FONT=&quot]Question No: 4 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]The Huffman algorithm finds a polynomial solution[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot]►[/FONT][FONT=&quot]False[/FONT]
[FONT=&quot] Question No: 5 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]The greedy part of the Huffman encoding algorithm is to first find two nodes with smallest frequency.[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot]►[/FONT][FONT=&quot]False[/FONT]

[FONT=&quot]Question No: 6 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot] The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the prefix of any other.[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot] ► False[/FONT]

[FONT=&quot]Question No: 7 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot] ► False[/FONT]
[FONT=&quot]Question No: 8 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot] ► False[/FONT]
[FONT=&quot]Question No: 9 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]The term “coloring” came form the original application which was in architectural design.[/FONT]
[FONT=&quot] ► True[/FONT]
[FONT=&quot] ► False[/FONT]
[FONT=&quot]Question No: 10 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.[/FONT]
[FONT=&quot]► True[/FONT]
[FONT=&quot]►[/FONT][FONT=&quot]False[/FONT]

[FONT=&quot]Question No: 11 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Dijkstra’s algorithm is operates by maintaining a subset of vertices[/FONT]
[FONT=&quot]► True[/FONT]
[FONT=&quot]►[/FONT][FONT=&quot]False[/FONT]
[FONT=&quot]Question No: 12 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]We do sorting to,[/FONT]
[FONT=&quot] ► keep elements in random positions[/FONT]
[FONT=&quot] ► keep the algorithm run in linear order[/FONT]
[FONT=&quot] ► keep the algorithm run in (log n) order[/FONT]
[FONT=&quot] ► keep elements in increasing or decreasing order[/FONT]

[FONT=&quot]Question No: 13 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot][/FONT][FONT=&quot]After partitioning array in Quick sort, pivot is placed in a position such that[/FONT]
[FONT=&quot] ► Values smaller than pivot are on left and larger than pivot are on right[/FONT]
[FONT=&quot] ► Values larger than pivot are on left and smaller than pivot are on right[/FONT]
► Pivot is the first element of array
[FONT=&quot] ► Pivot is the last element of array[/FONT]

[FONT=&quot]Question No: 14 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Merge sort is stable sort, but not an in-place algorithm[/FONT]
[FONT=&quot]► True[/FONT]
[FONT=&quot]►[/FONT][FONT=&quot]False[/FONT]

[FONT=&quot]Question No: 15 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot][/FONT][FONT=&quot]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.[/FONT]
[FONT=&quot] ►[/FONT] [FONT=&quot]O (q)[/FONT]
[FONT=&quot] ► O (1)[/FONT]
[FONT=&quot] ► O (n2)[/FONT]
[FONT=&quot] ► O (n3)[/FONT]

[FONT=&quot]Question No: 16 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]One of the clever aspects of heaps is that they can be stored in arrays without using any[/FONT]
[FONT=&quot]_______________.[/FONT]

• [FONT=&quot]Pointers [/FONT]
  
• [FONT=&quot]constants[/FONT]
  
• [FONT=&quot]variables[/FONT]
  

[FONT=&quot]functions[/FONT]

[FONT=&quot]Question No: 17 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Merge sort requires extra array storage,[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]False[/FONT]
  

[FONT=&quot]Question No: 18 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]The Huffman codes provide a method of encoding data inefficiently when coded using[/FONT]
[FONT=&quot]ASCII standard.[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]Falase[/FONT]
  

[FONT=&quot]Question No: 19 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Using ASCII standard the string abacdaacac will be encoded with __________ bits.[/FONT]

• [FONT=&quot]80 [/FONT]
  
• [FONT=&quot]160[/FONT]
  
• [FONT=&quot]320[/FONT]
  
• [FONT=&quot]100[/FONT]
  

[FONT=&quot]Question No: 20 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Using ASCII standard the string abacdaacac will be encoded with 160 bits.[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]False[/FONT]
  

[FONT=&quot]Question No: 21 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Using ASCII standard the string abacdaacac will be encoded with 10 bytes.[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]False [/FONT]
  

[FONT=&quot]Question No: 22 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]The greedy part of the Huffman encoding algorithm is to first find two nodes with[/FONT]
[FONT=&quot]character [/FONT][FONT=&quot]frequency[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]False[/FONT]
  

[FONT=&quot]Question No: 23 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Huffman algorithm uses a greedy approach to generate an prefix code T that minimizes[/FONT]
[FONT=&quot]the expected length B (T) of the encoded string.[/FONT]

• [FONT=&quot]True[/FONT]
  
• [FONT=&quot]False[/FONT]
  

[FONT=&quot]Question No: 24 ( Marks: 1 ) - Please choose one[/FONT]
[FONT=&quot]Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative and there are negative cost cycles.[/FONT]

• [FONT=&quot]True [/FONT]
  
• [FONT=&quot]False[/FONT]
  

[FONT=&quot]Question No: 25 ( Marks: 1 ) - Please choose one[/FONT]

[FONT=&quot]Question No: 26 ( Marks: 1 ) - Please choose one[/FONT]

[FONT=&quot]Question No: 27 ( Marks: 2 )[/FONT]
[FONT=&quot][/FONT][FONT=&quot]explain 2-d maxima problem mathematically or algrithmically.[/FONT]


[FONT=&quot]Question No: 28 ( Marks: 2 )[/FONT]
[FONT=&quot][/FONT][FONT=&quot]Differentiate between back edge and forward edge.[/FONT]


[FONT=&quot]Question No: 29 ( Marks: 2 )[/FONT]
[FONT=&quot]Question No: 30 ( Marks: 2 )[/FONT]
[FONT=&quot]Question No: 31 ( Marks: 3 )[/FONT]

[FONT=&quot]Question No: 32 ( Marks: 3 )[/FONT]



[FONT=&quot]Question No: 33 ( Marks: 3 )[/FONT]


[FONT=&quot]Question No: 34 ( Marks: 5 )[/FONT]
[FONT=&quot][/FONT][FONT=&quot]Suppose you could prove that an NP-complete problem can not be solved in polynomial time. What would be the consequence?[/FONT]

[FONT=&quot]Question No: 48 ( Marks: 3 )[/FONT]
[FONT=&quot]Recursive explanation of dynamic programming.[/FONT]

[FONT=&quot]Question No: 49 ( Marks: 5 )[/FONT]
[FONT=&quot][/FONT][FONT=&quot]What is the cost of the following graph?[/FONT]

[FONT=&quot]
[/FONT]

[FONT=&quot]Cost =33[/FONT]

[FONT=&quot]Question No: 50 ( Marks: 5 ) [/FONT]
[FONT=&quot]. 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[/FONT][FONT=&quot].[/FONT]

[FONT=&quot] a [/FONT]à[FONT=&quot] b [/FONT]à[FONT=&quot] c [/FONT]à[FONT=&quot] e[/FONT]
[FONT=&quot] b [/FONT]à[FONT=&quot] a [/FONT]à[FONT=&quot] d [/FONT]
[FONT=&quot] c [/FONT]à[FONT=&quot] a [/FONT]à[FONT=&quot] d [/FONT]à[FONT=&quot] e [/FONT]à[FONT=&quot] f[/FONT]
[FONT=&quot] d [/FONT]à[FONT=&quot] b [/FONT]à[FONT=&quot] c [/FONT]à[FONT=&quot] f[/FONT]
[FONT=&quot] e [/FONT]à[FONT=&quot] a [/FONT]à[FONT=&quot] c [/FONT]à[FONT=&quot] f[/FONT]
[FONT=&quot] f [/FONT]à[FONT=&quot] c [/FONT]à[FONT=&quot] d [/FONT]à[FONT=&quot] e[/FONT]
[FONT=&quot] g[/FONT]
[FONT=&quot]Question No: 51 ( Marks: 5 )[/FONT]
[FONT=&quot]Floyd Warshal algorithm with three recursive steps[/FONT]

[FONT=&quot]Question No: 52 ( Marks: 5 )[/FONT]