Greedy Algorithms: GATE CS previous year questions (Algorithms)

GATE CS 2023MSQ2 marksMedium (estimate)
GATE CS 2023, Q.55
Let $G$ be a simple, finite, undirected graph with vertex set ${v_{1}, \dots, v_{n}}$ . Let $Δ (G)$ denote the maximum degree of $G$ and let $N = {1, 2, \dots}$ deno...
Graph Theory · Greedy Algorithms
GATE CS 2021 Set 2MCQ2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.36 (CS Q.26)
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one...
Greedy Algorithms
GATE CS 2020MCQ2 marksMedium (estimate)
GATE CS 2020, Q.41 (CS Q.31)
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 edge…
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
GATE CS 2020NAT2 marksEasy (estimate)
GATE CS 2020, Q.59 (CS Q.49)
Consider a graph $G = (V, E)$ , where $V = {v_{1}, v_{2}, \dots, v_{100}}$ , $E = {(v_{i}, v_{j}) ∣ 1 \leq i < j \leq 100}$ , and weight of the edge $(v_{i}, v_{j})$ is $∣ i - j ∣$ . The wei...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
GATE CS 2019MCQ2 marksMedium (estimate)
GATE CS 2019, Q.48 (CS Q.38)
Let $G$ be any connected, weighted, undirected graph. I. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. II. $G$ has a unique minimum spanni...
Greedy Algorithms
GATE CS 2018NAT2 marksMedium (estimate)
GATE CS 2018, Q.57 (CS Q.47)
Consider the following undirected graph G: Undirected weighted graph G with 5 vertices and 7 edges, with edge weights 1, 3, 4, 4, 4, 5, and variable x. Choose a value for $x$ th...
Greedy Algorithms
GATE CS 2017 Set 1MCQ1 markEasy (estimate)
GATE CS 2017 Set 1, Q.5 (CS Q.5)
Consider the following table: Algorithm Design Paradigm (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming Match the algor...
Greedy Algorithms · Dynamic Programming · Divide and Conquer
GATE CS 2017 Set 1MCQ2 marksEasy (estimate)
GATE CS 2017 Set 1, Q.26 (CS Q.26)
Let $G = (V, E)$ be any connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: (I) Minimum Spann...
Greedy Algorithms · Graph Theory
GATE CS 2017 Set 2NAT2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.50 (CS Q.50)
A message is made up entirely of characters from the set $X = {P, Q, R, S, T}$ . The table of probabilities for each of the characters is shown below: | Character | Probability...
Greedy Algorithms
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.16 (CS Q.6)
Match the following: | | Algorithm | | Design Paradigm | | :--- | :--- | :--- | :--- | | (P) | Prim's algorithm for minimum spanning tree | (i) | Backtracking | | (Q) | Floyd-Wa...
Greedy Algorithms
GATE CS 2014 Set 2NAT2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.48 (CS Q.38)
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 together two sequences at a ti...
Greedy Algorithms
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.29 (CS Q.29)
Let $G$ be a weighted graph with edge weights greater than one and $G^{'}$ be the graph constructed by squaring the weights of edges in $G$ . Let $T$ and $T^{'}$ be the minimum spannin...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.40 (CS Q.40)
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 Dijkstra's shortest path algorit...
Single-Source and All-Pairs Shortest Paths · Greedy Algorithms

Questions

Other topics of Algorithms