UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 6 of 9
Study Stuff for MCA Examinations
Solution
Why: The LCS length for the two sequences is $4$. $2,3,2,1$ is a subsequence of both: $\{1,\underline{2},3,\underline{2},4,1,\underline{2}\}$ and $\{\underline{2},4,\underline{3},1,\underline{2},\underline{1}\}$. Option (4) has length $5$ (too long), and (1), (2) are not subsequences of both.
The elements $42,25,30,40,22,35,26$ are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as:
Solution
Insert elements one by one into max-heap.
After inserting $42,25,30$:
$\langle 42,25,30\rangle$
Insert $40$.
Since $40>25$, swap them:
$\langle 42,40,30,25\rangle$
Insert $22$:
$\langle 42,40,30,25,22\rangle$
Insert $35$.
Since $35>30$, swap them:
$\langle 42,40,35,25,22,30\rangle$
Insert $26$.
No swap is needed.
Final max-heap array is
$\langle 42,40,35,25,22,30,26\rangle$
| List I | List II |
|---|---|
| A. Circular Queue | III. Dijkstra algorithm |
| B. Priority Queue | II. CPU Scheduling |
| C. Double Ended Queue | I. Print Queue |
| D. Simple Queue | IV. Palindrome checking |
Choose the correct answer from the options given below:
Solution
The following multithreaded algorithm computes transpose of a matrix in parallel:
$p\ Trans(X,Y,N)$
if $N=1$
then $Y[1,1]\leftarrow X[1,1]$
else partition $X$ into four $(N/2)\times(N/2)$ submatrices $X_{11},X_{12},X_{21},X_{22}$
partition $Y$ into four $(N/2)\times(N/2)$ submatrices $Y_{11},Y_{12},Y_{21},Y_{22}$
spawn $p\ Trans(X_{11},Y_{11},N/2)$
spawn $p\ Trans(X_{12},Y_{12},N/2)$
spawn $p\ Trans(X_{21},Y_{21},N/2)$
spawn $p\ Trans(X_{22},Y_{22},N/2)$
What is the asymptotic parallelism of the algorithm?
Solution
Parallelism is given by:
$\dfrac{T_1}{T_\infty}$
Here, $T_1$ is total work.
The algorithm recursively divides the matrix into $4$ subproblems of size $N/2$.
So,
$T_1(N)=4T_1(N/2)+\theta(1)$
Hence,
$T_1(N)=\theta(N^2)$
Now, span or critical path time is:
$T_\infty(N)=T_\infty(N/2)+\theta(1)$
because recursive calls run in parallel.
So,
$T_\infty(N)=\theta(\lg N)$
Therefore,
$\dfrac{T_1}{T_\infty}=\dfrac{\theta(N^2)}{\theta(\lg N)}$
$=\theta(N^2/\lg N)$
Consider two sequences $X$ and $Y$:
$X=\langle 0,1,2,1,3,0,1\rangle$
$Y=\langle 1,3,2,0,1,0\rangle$
The length of longest common subsequence between $X$ and $Y$ is:
Solution
Given sequences are
$X=\langle 0,1,2,1,3,0,1\rangle$
$Y=\langle 1,3,2,0,1,0\rangle$
One longest common subsequence is
$\langle 1,2,1,0\rangle$
This subsequence has length
$4$
Therefore, the length of the longest common subsequence is
$4$
Consider the following statements:
(a) The running time of dynamic programming algorithm is always $\theta(\rho)$ where $\rho$ is number of subproblems.
(b) When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation $($unmodified$)$ in a correct dynamic program.
(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization.
(d) If a problem $X$ can be reduced to a known NP-hard problem, then $X$ must be NP-hard.
Which of the statement(s) is/are true?
Solution
Statement (a) is false because running time also depends on the time required to solve each subproblem, not only the number of subproblems.
Statement (b) is true because cyclic dependency creates a circular dependency, so the recurrence cannot be used directly in a correct dynamic program.
Statement (c) is false because bottom-up DP and memoized recursion usually have the same asymptotic time complexity.
Statement (d) is false because if $X$ is reduced to an NP-hard problem, it does not prove that $X$ is NP-hard. To prove $X$ is NP-hard, a known NP-hard problem should be reduced to $X$.
So, only statement (b) is true.
Solution
Solution
Solution
Solution
$(A+B)*(C*D-E)*F/G$
First convert each part:
$(A+B)\Rightarrow AB+$
$(C*D-E)\Rightarrow CD*E-$
Now multiply both:
$(A+B)*(C*D-E)\Rightarrow AB+CD*E-*$
Now multiply by $F$:
$AB+CD*E-*F*$
Now divide by $G$:
$AB+CD*E-*F*G/$
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
