Greedy Method · Algorithms · GATE CSE

Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight edge in G which is present i...

Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then whic...

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

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i-j|$$. The weight of a minimum...

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. W...

The number of distinct minimum-weight spanning trees of the following graph is ________...

Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters,...

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted...

Consider a graph G = (V, E), where V = {v1, v2, ...., v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i - j|. The wei...

Consider the weights and values of items listed below. Note that there is only one unit of each item. .tg {border-collapse:collapse;border-spacing:...

Consider the following undirected graph $$G: $$ Choose a value for $$x$$ that will maximize the number of minimum weight spanning trees $$(MWSTs)$$...

$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statemen...

Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given by the entry $${W_{ij}}$$ in ...

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C),...

A Young tableau is a $$2D$$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $$\infty ,$$ ...

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging tog...

The number of distinct minimum spanning trees for the weighted graph below is ________ ...

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 Dijks...

An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. ...

An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. ...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left...

Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?...

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to...

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is ...

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?

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 compl...

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 t...

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 Krusk...

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source. In what or...

Let G=(V,E) be an undirected graph with a subgraph G1=(V1,E1). Weights are assigned to edges of G as follows. $$$w(e) = \begin{cases} 0 \text{, if }...

Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ……., vj) such that (vk, vk+1) ∈ E for...

What is the weight of a minimum spanning tree of the following graph? ...

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Whic...

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sort...

The weighted external path length of the binary tree in figure is ___________. ...

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of: