NAT1 mark
Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is ________.
Numerical answer
Answer key coming soon
MCQ1 mark
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Single correct
Answer key coming soon
MCQ1 mark
Let be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of does not change
Q: Shortest path between any pair of vertices does not change
Single correct
Answer key coming soon
NAT2 marks
Consider the weighted undirected graph with 4 vertices, where the weight of edge is given by the entry in the matrix .
The largest possible integer value of , for which at least one shortest path between some pair of vertices will contain the edge with weight is ________.
Numerical answer
Answer key coming soon
NAT2 marks
Let be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of can have is ________.
Numerical answer
Answer key coming soon
MCQ2 marks
is an undirected simple graph in which each edge has a distinct weight, and is a particular edge of . Which of the following statements about the minimum spanning trees (MSTs) of is/are TRUE?
I. If is the lightest edge of *some* cycle in , then every MST of *includes*
II. If is the heaviest edge of *some* cycle in , then every MST of *excludes*
Single correct
Answer key coming soon
MCQ1 mark
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in time
II. Bubblesort runs in time
III. Mergesort runs in time
IV. Insertion sort runs in time
Single correct
Answer key coming soon
MCQ1 mark
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Single correct
Answer key coming soon
NAT2 marks
Let , , , and be four matrices of dimensions , , , and , respectively. The minimum number of scalar multiplications required to find the product using the basic matrix multiplication method is ________.
Numerical answer
Answer key coming soon
NAT2 marks
The given diagram shows the flowchart for a recursive function A(). Assume that all statements, except for the recursive calls, have time complexity. If the worst case time complexity of this function is , then the least possible value (accurate up to two decimal positions) of is ________.
Numerical answer
Answer key coming soon
MCQ2 marks
In an adjacency list representation of an undirected simple graph , each edge has two adjacency list entries: in the adjacency list of , and in the adjacency list of . These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If and , and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Single correct
Answer key coming soon
Use ← → to move