# Test: Greedy Techniques- 1

## 15 Questions MCQ Test Algorithms | Test: Greedy Techniques- 1

Description
Attempt Test: Greedy Techniques- 1 | 15 questions in 35 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Algorithms for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
QUESTION: 1

### The length of the path from v5 to v6 in the MST of previous question with n = 10 is

Solution:

Any MST which has more than 5 nodes will have the same distance between v5 and v6 as the basic structure of all MSTs (with more than 5 nodes) would be following. Distance between v5 and v6 = 3 + 4 + 6 + 8 + 10 = 31

QUESTION: 2

### To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Solution:

The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.

QUESTION: 3

### A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency: character   Frequency     a            5     b            9     c           12     d           13     e           16     f            45 Note : Each character in input message takes 1 byte. If the compression technique used is Huffman Coding, how many bits will be saved in the message?

Solution:

Total number of characters in the message = 100.
Each character takes 1 byte. So total number of bits needed = 800.

After Huffman Coding, the characters can be represented with:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
Total number of bits needed = 224
Hence, number of bits saved = 800 - 224 = 576
See here for complete explanation and algorithm.

QUESTION: 4

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T? Solution:

To get the minimum spanning tree with vertex 0 as leaf, first remove 0th row and 0th column and then get the minimum spanning tree (MST) of the remaining graph. Once we have MST of the remaining graph, connect the MST to vertex 0 with the edge with minimum weight (we have two options as there are two 1s in 0th row).

QUESTION: 5

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered. Solution:

See Dijkstra’s shortest path algorithm When the algorithm reaches vertex 'C', the distance values of 'D' and 'E' would be 7 and 6 respectively. So the next picked vertex would be 'E'

QUESTION: 6

What is the time complexity of Huffman Coding?

Solution:

O(nlogn) where n is the number of unique characters. If there are n nodes, extractMin() is called 2*(n – 1) times. extractMin() takes O(logn) time as it calles minHeapify(). So, overall complexity is O(nlogn). See here for more details of the algorithm.

QUESTION: 7

In the graph given in above question question, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

Solution:

Path: 1 → 0 → 4 → 2 Weight: 1 + 4 + 3

QUESTION: 8

Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to Solution:

Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph. Let us see... Let us run the 1st pass b 1 b is minimum, so shortest distance to b is 1. After 1st pass, distances are c 3, e -2. e is minimum, so shortest distance to e is -2 After 2nd pass, distances are c 3, f 0. f is minimum, so shortest distance to f is 0 After 3rd pass, distances are c 3, g 3. Both are same, let us take g. so shortest distance to g is 3. After 4th pass, distances are c 3, h 5 c is minimum, so shortest distance to c is 3 After 5th pass, distances are h -2 h is minimum, so shortest distance to h is -2

QUESTION: 9

In question #2, which of the following represents the word "dead"?

Solution:

The Huffman Tree generated is: character   code-word
f                0
c             100
d             101
a             1100
b             1101
e              111
The word dead can be represented as: 101 111 1100 101 However, the alternative codeword can also be found by assigning 1 to the left edge and 0 to the right edge of the tree, i.e. dead can also be represented as: 010 000 0011 010 See here for more details of the algorithm.

QUESTION: 10

An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose

(i) diagonal elements are 0‘s and

(ii) non-diagonal elements are 1‘s.

which one of the following is TRUE?

Solution:

If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1.

QUESTION: 11

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Solution:

* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)
* Time Comlexity of the Warshall’s algorithm is O(|V|^3)
* DFS cannot be used for finding shortest paths
* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

QUESTION: 12

Which of the following is true about Huffman Coding.

Solution:

Huffman coding is a lossless data compression algorithm. The codes assigned to input characters are Prefix Codes, means the codes are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding.

QUESTION: 13

Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

Solution:

The edge (d-e) cannot be considered before (d-c) in Kruskal's minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.

QUESTION: 14

In a weighted graph, assume that the shortest path from a source 's' to a destination 't' is correctly calculated using a shortest path algorithm. Is the following statement true? If we increase weight of every edge by 1, the shortest path always remains same.

Solution:

See the following counterexample. There are 4 edges s-a, a-b, b-t and s-t of wights 1, 1, 1 and 4 respectively. The shortest path from s to t is s-a, a-b, b-t. IF we increase weight of every edge by 1, the shortest path changes to s-t. QUESTION: 15

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?

Solution:

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.  Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code