Greedy Strategy Interview Question Part 4

32. Lossless compression refers to
a. data that can be uncompressed exactly as it was before compression
b. Huffman coding
c. The assumption that data need not be stored perfectly
d. a and b
Ans. d
Huffman coding is an example of lossless compression wherein the characters are converted into a binary code such that the original text can be retrieved as it was.


33. State whether the following statement is true or false
The basic idea in Huffman coding is to assign short codewords to those input blocks with low probabilities and long codewords to those with high probabilities.
Ans. False
The basic idea in Huffman coding is to assign short codewords to those input blocks with high probabilities and long codewords to those with low probabilities.

34. Dijkstra’s Algorithm determines
a. Shortest Path between every pair of vertices
b. Paths between every pair of vertices
c. Paths between every pair of vertices
d. Shortest path only between a given source and multiple destinations
Ans. d

35. Which is an example of a minimum spanning tree algorithm?
a. Kruskal's
b. Huffman
c. Euler's
d. Fibonacci
Ans. a

36.. Kruskal's Algorithm can be solved on the Bases of __________.
a. Cost
b. Nodes
c. Edges
d. Tree
Ans. a

37. Huffman code is a
a. fixed-to-variable length code
b. variable-to-fixed length code
c. variable-to-variable length code
d. fixed-to-fixed length code
Ans. a

38. An edge of a spanning tree is called a ________
Ans. branch

39. An edge in the graph that is not in the spanning tree is called a ________
a. tree
b. branch
c. chord
d. root
Ans. c

40. Spanning trees are important because of following reasons.
i)Spanning trees construct a sparse sub graph that tells a lot about the original graph.
ii)Spanning trees a very important in designing efficient routing algorithms.
iii)Some hard problems (e.g., Steiner tree problem and traveling salesman problem) can be solved approximately by using spanning trees.
iv)Spanning trees have wide applications in many areas, such as network design, etc. Which of the following options are correct?
a. i,ii and iii
b. i and iii
c. all the above
d. ii and iv
Ans. c
41. A minimum spanning tree is a graph that has the following properties:
● it spans the graph
● it is a minimum
State whether the above statement is true or false.
Ans. True
42. Which of the following algorithms solves the all-pair shortest path problem?
a. Dijkstra’s algorithm
b. Floyd’s algorithm
c. Prim’s algorithm
d. Warshall’s algorithm
Ans. b
Dijkstra’s algorithm solves single source shortest path problem.Warshall’s algorithm finds transitive closure of a given graph.Prim’s algorithm constructs a minimum cost spanning tree for a given weighted graph
43. In kruskal’s algorithm
i)the selection function chooses edges in increasing order of their length
ii)cycle has to be formed
iii)result is a forest of trees that grows until all the trees merge into one.
The correct options are
a. i and ii
b. i,ii and iii
c. i and iii
d. ii and iii
Ans. c
In kruskal's algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree