UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 4 of 9
Study Stuff for MCA Examinations
Consider the following steps:
$S_1$: Characterize the structure of an optimal solution
$S_2$: Compute the value of an optimal solution in bottom-up fashion
Which of the step(s) is/are common to both dynamic programming and greedy algorithms?
Solution
Both dynamic programming and greedy algorithms use the idea of optimal substructure.
So, characterizing the structure of an optimal solution is common to both.
Therefore, $S_1$ is common.
But computing the value of an optimal solution in bottom-up fashion is mainly a dynamic programming approach.
It is not a necessary step in greedy algorithms.
So, $S_2$ is not common.
| List-I | List-II |
| A. Dijkstra’s Algorithm | I. Find the shortest path between all pairs of vertices in a graph with positive or negative edge weights |
| B. Floyd-Warshall Algorithm | II. Finds the shortest path in a weighted graph with non-negative edge weights |
| C. Bellman-Ford Algorithm | III. Sorts elements by repeatedly moving them past neighboring elements that are smaller |
| D. Prim’s Algorithm | IV. Determines the strongly connected components in a directed graph |
Solution
Dijkstra Algorithm → shortest path with non-negative weights
Floyd-Warshall → all pairs shortest paths
Bellman-Ford → handles negative edge weights
Prim → Minimum Spanning Tree
Thus correct matching:
A → II
B → I
Remaining pair becomes
C → IV
D → III
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f:V\times V\to R$:
$P_1$: For all $u,v\in V,\ f(u,v)=-f(v,u)$
$P_2$: $\sum_{v\in V} f(u,v)=0$ for all $u\in V$
Which one of the following is/are correct?
Solution
Property $P_1$ is the skew-symmetry property of flow.
So, $P_1$ is correct.
Property $P_2$ represents flow conservation, but in a flow network, flow conservation holds for all vertices except the source and sink.
The statement says it holds for all $u\in V$, which is not correct.
So, $P_2$ is false.
Solution
(A) $abcghf$
(B) $abfchg$
(C) $abfhgc$
(D) $afghbc$
Which of the following is correct?
Solution
In DFS, we start from a vertex and keep going deeper through an unvisited adjacent vertex.
From the graph, important edges are:
$a-b,\ a-c,\ a-f,\ b-c,\ b-f,\ b-h,\ c-g,\ g-h,\ f-h,\ f-g$
Now check each DFS sequence.
Check (A): $abcghf$
Path followed:
$a\to b\to c\to g\to h\to f$
All these are valid edges:
$a-b,\ b-c,\ c-g,\ g-h,\ h-f$
So, sequence (A) can be a valid DFS order.
Check (B): $abfchg$
Path starts as:
$a\to b\to f$
After reaching $f$, there are still unvisited adjacent vertices such as $h$ and $g$.
DFS should go deeper from $f$ to one of its unvisited adjacent vertices.
But the next vertex in the sequence is $c$, and $f-c$ is not an edge.
So, sequence (B) cannot be a valid DFS order.
Check (C): $abfhgc$
Path followed:
$a\to b\to f\to h\to g\to c$
All these are valid edges:
$a-b,\ b-f,\ f-h,\ h-g,\ g-c$
So, sequence (C) can be a valid DFS order.
Check (D): $afghbc$
Path followed:
$a\to f\to g\to h\to b\to c$
All these are valid edges:
$a-f,\ f-g,\ g-h,\ h-b,\ b-c$
So, sequence (D) can be a valid DFS order.
Therefore, valid DFS sequences are:
(A), (C) and (D) only.
Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.
(A) Define the base case when the capacity is zero $(0)$ or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the $i$-th item and a knapsack capacity of $0$
(C) Identify subproblems and their dependencies based on items weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible capacity to fill the table
Choose the correct answer from the options given below :
Solution
What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accommodated.
Solution
In an unsorted array implementation of priority queue:
For Insert operation, we can insert the new element directly at the end of the array.
So, worst case time for Insert is:
$\theta(1)$
For Extract-min operation, the array is unsorted, so we must search the entire array to find the minimum element.
So, worst case time for Extract-min is:
$\theta(n)$
Solution
In a B-tree of order $M$:
Number of keys $=M-1$
Memory used by keys:
$(M-1)\times 32=32M-32$
Number of branches in non-leaf node $=M$
Memory used by branches:
$M\times 4=4M$
Total memory requirement:
$(32M-32)+4M$
$=36M-32$
Give asymptotic upper and lower bound for $T(n)$ given below. Assume $T(n)$ is constant for $n\le 2$.
$T(n)=4T(\sqrt n)+\lg^2 n$
Solution
Let,
$m=\lg n$
So,
$n=2^m$
Also,
$\sqrt n=2^{m/2}$
Now define:
$S(m)=T(2^m)$
Then recurrence becomes:
$S(m)=4S(m/2)+m^2$
Using Master Theorem:
$a=4,\ b=2$
$m^{\log_b a}=m^{\log_2 4}=m^2$
Here,
$f(m)=m^2$
So,
$S(m)=\theta(m^2\lg m)$
Now put $m=\lg n$:
$T(n)=\theta((\lg n)^2\lg(\lg n))$
So,
$T(n)=\theta(\lg^2 n\lg\lg n)$
Solution
In shortest path relaxation:
$d[v]=\min(d[v],d[u]+w[u,v])$
Given:
$d[v]=29$
$d[u]=15$
$w[u,v]=12$
So,
$d[u]+w[u,v]=15+12=27$
Now,
$d[v]=\min(29,27)$
$d[v]=27$
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
