Design Algorithm Analysis GATE previous year questions with answer
Ques 1 Gate 2024 Set-2
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is _________
A graph is bipartite if its vertex set can be partitioned into two disjoint sets, say V1 and V2, such that every edge connects a vertex in V1 to a vertex in V2. No edges exist between vertices within the same set.
2. Determining the Chromatic Number (χ(G)):
• By definition, all vertices within V1 are completely independent of each other (not adjacent). Therefore, every vertex in V1 can safely share the exact same color (e.g., Color 1).
• Similarly, all vertices within V2 are independent of each other and can share a different color (e.g., Color 2).
• Since every edge in the graph only goes between V1 and V2, no two adjacent vertices will ever share the same color.
3. Conclusion:
Any bipartite graph containing at least one edge can be properly colored using exactly 2 colors. Therefore, its chromatic number is 2.
Ques 2 Gate 2024 Set-2
The number of distinct minimum-weight spanning trees of the following graph is _________
Explanation:
Let us perform a thorough, rigorous verification using the properties of Minimum Spanning Trees (MST) and the cycle property to confirm why the total number of distinct options is exactly 9.
1. Classify Edges by Weight:
• Weight 1 Edges: (a, b), (a, f), (c, d), (d, e)
• Weight 2 Edges: (a, g), (b, g), (c, g), (d, g), (e, g), (f, g)
• Weight 3 Edges: (b, c), (f, e)
2. Step 1: Including Weight 1 Edges
• All 4 edges of weight 1—(a, b), (a, f), (c, d), (d, e)—must be part of any MST because they are the absolute smallest available choices and do not create any internal cycles.
• Including these edges forms two disconnected trees (sub-components):
• Left Component: {b — a — f}
• Right Component: {c — d — e}
• Isolated Center Node: {g}
3. Step 2: Connecting Components via Weight 2 Edges
The graph has 7 vertices, so an MST must contain exactly 6 edges. We have already selected 4 edges, meaning we need exactly 2 more edges of weight 2 to fully connect the entire graph.
To connect the three pieces without introducing a cycle, we must pick exactly one cross-edge to connect the Left Component to node g and exactly one cross-edge to connect the Right Component to node g. Let's analyze how many valid ways we can choose this pair:
• Connections to the Left Component {b, a, f}:
Node g has three potential incident edges to this component: (b, g), (a, g), (f, g).
Selecting any single one of these will safely connect node g to the left block without creating a cycle.
→ Number of valid choices for the left side = 3 choices.
• Connections to the Right Component {c, d, e}:
Node g has three potential incident edges to this component: (c, g), (d, g), (e, g).
Selecting any single one of these will safely connect node g to the right block without creating a cycle.
→ Number of valid choices for the right side = 3 choices.
4. Calculate Total MST Combinations:
Since the structural edge selection on the left component is completely independent of the choice made on the right component, we apply the fundamental product rule of counting:
Total Distinct MSTs = (Left Choices) × (Right Choices)
Total Distinct MSTs = 3 × 3 = 9.
5. Conclusion:
Your calculation is entirely correct. There are exactly 9 distinct Minimum Spanning Trees possible for this graph.
Ques 3 Gate 2022
Consider the following recurrence:
f(2n) = 2f(n) -1, for n≥1;
f(2n+1) = 2f(n) +1, for n≥1;
Then, which of the following statements is/are TRUE?
Ques 4 Gate 2022
Which one of the following statements is TRUE for all positive functions f (n) ?
Ques 5 GATE 2021 SET-1
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?
Ques 6 GATE 2021 SET-1
Consider the following three functions.
f1 = 10n
f2 = nlogn
f3 = n√n
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
Ques 7 Gate 2020
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?
Ques 8 Gate 2020
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially ?
Ques 9 Gate 2020
For parameters a and b, both of which are ω(1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
Ques 10 Gate 2020
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ________ .
Total Unique Visitors