UGC NET Computer Science Data Structures Previous Year Questions (PYQs) – Page 8 of 9

Normally, multiplying two polynomials by the direct method takes:

$O(n^2)$

Using FFT, polynomial multiplication is done in three main steps:

Step 1: Convert coefficient form to point-value form using FFT.

Time complexity:

$O(n\log_2 n)$

Step 2: Multiply corresponding values.

Time complexity:

$O(n)$

Step 3: Convert point-value form back to coefficient form using inverse FFT.

Time complexity:

$O(n\log_2 n)$

Total time complexity:

$O(n\log_2 n)+O(n)+O(n\log_2 n)$

$=O(n\log_2 n)$

Given expression is:

$(A+B*D)/(E-F)+G$

First solve according to operator precedence:

$B*D$

So, expression becomes:

$(A+(B*D))/(E-F)+G$

Prefix of $B*D$ is:

$*BD$

Prefix of $A+B*D$ is:

$+A*BD$

Prefix of $E-F$ is:

$-EF$

Now prefix of $\frac{A+B*D}{E-F}$ is:

$/+A*BD-EF$

Finally add $G$:

$+/+A*BD-EFG$

So, statement $1$ is true.

Prefix is not simply the reverse of postfix.

So, statement $2$ is false.

The order of operands in infix and postfix remains:

$A,B,D,E,F,G$

So, statement $3$ is true.

The order of operands in infix, prefix, and postfix also remains the same:

$A,B,D,E,F,G$

So, statement $4$ is true.

Correct statements are:

$1,3,$ and $4$

A – Parallel Fast Fourier Transform (FFT):

The FFT can be executed in parallel, which reduces the time complexity from O(n log n) to O(log n) under ideal conditions, as the operations required to calculate the FFT can be effectively divided among multiple processors. Thus, it corresponds to III. Θ(lg n).

B – Iterative Fast Fourier Transform (FFT):

The FFT, even when implemented iteratively, has a time complexity of O(n log n) because we divide the problem into smaller chunks recursively, and for each level of division, we do a constant amount of work. Hence it matches with IV. Θ(n lg n).

C – Evaluation of polynomial at n points by Horner method:

If evaluated using the Horner method, a polynomial can be evaluated in O(n) operations. However, if we are evaluating the polynomial at n points, and the polynomial itself has degree n, the total complexity becomes O(n²). Therefore, it corresponds to I. Θ(n²).

D – Product of two polynomials that are represented in point value form:

If the polynomials are represented in point-value form, their product can be computed pretty efficiently in O(n) time complexity. This is due to the fact that to compute the product polynomial at a point, you simply multiply the evaluations of the input polynomials at that point.

Therefore, D corresponds to II. Θ(n).

• Binary Search halves the input and performs constant work

$f(n) = f(n/2) + O(1)$ → IV

• Find maximum and minimum (divide and conquer)

Two recursive calls with constant comparisons

$f(n) = 2f(n/2) + 2$ → III

• Merge Sort divides into two parts and merges in linear time

$f(n) = 2f(n/2) + n$ → II

• Fast Matrix Multiplication (Strassen)

$f(n) = 7f(n/2) + O(n^2)$ → I

Thus matching:

A → IV

B → III

C → II

D → I

Dijkstra's Algorithm is used to find the shortest path from a single source. It stores the total minimum cost from source node to current node.

So,

a → III

Prim's Algorithm selects the minimum cost edge to construct a minimum spanning tree.

So,

b → II

Warshall's Algorithm calculates the path matrix or transitive closure.

So,

c → I

Kruskal's Algorithm is used to find Minimum Spanning Tree.

So,

d → IV

Correct matching:

a-III, b-II, c-I, d-IV

Evaluate each prefix expression.

A:

• • • 2 / 8 4 3 2
      = + - * 2 2 3 2
      = + - 4 3 2
      = + 1 2
      = 3

B:
↑ - * 3 3 * 4 2 5
= ↑ - 9 8 5
= ↑ 1 5
= 1

C:

• • ↑ 3 2 ↑ 2 3 / 6 - 4 2
    = + - 9 8 / 6 2
    = + 1 3
    = 4

D:

• • 3 + 3 ↑ 3 + 1 1 3
    = * + 3 + 3 9 3
    = * + 3 12 3
    = * 15 3
    = 45

Values:

A = 3
B = 1
C = 4
D = 45

Increasing order:

B < A < C < D