Aspire Faculty ID #17386 · Topic: UGC NET Computer Science June 2024 (Paper II) · Just now
UGC NET Computer Science June 2024 (Paper II)

Match List-I with List-II.

$f(n) = a f(n/b) + g(n)$ is a divide-and-conquer recurrence relation for the Listed-I algorithms, match their recurrence in Listed-II.

 List-I (Algorithms)

List-II (Recurrence Relation)

 
 A. Binary Search
 I. $f(n) = 7f(n/2) + 15n^2/4$
 B. Find maximum and minimum of a sequence
 II. $f(n) = 2f(n/2) + n$
 C. Merge Sort
 III. $f(n) = 2f(n/2) + 2$
 D. Fast Matrix Multiplication

 IV. $f(n) = f(n/2) + 2$

Solution

• 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

← Previous Next →

Previous 10 Questions — UGC NET Computer Science June 2024 (Paper II)

Nearest first
1
Arrange the following in correct order, so that they can follow a proper run time environment :A. Programming statement…
Topic: UGC NET Computer Science June 2024 (Paper II)
 2
Which of the following are type of interface in an ATM network ?A. user-to-userB. user-to-networkC. network-to-networkD…
Topic: UGC NET Computer Science June 2024 (Paper II)
 3
The techniques used to handle the phantom problem are A. Time stamping B. Index locking C. Predicate locking D. Executi…
Topic: UGC NET Computer Science June 2024 (Paper II)
 4
Which of the followings are White box Testing ?A. Path TestingB. Loop TestingC. Regression TestingD. Non functional Tes…
Topic: UGC NET Computer Science June 2024 (Paper II)
 5
What will be the order of the following fields in a frame relay ‘frame format’ ?A. FlagB. FCSC. addressD. informationCh…
Topic: UGC NET Computer Science June 2024 (Paper II)
 6
Lower-triangular sparse matrix is one :
Topic: UGC NET Computer Science June 2024 (Paper II)

Next 10 Questions — UGC NET Computer Science June 2024 (Paper II)

Ascending by ID
1
Match List-I with List-II : List-I List-II A. Channelization protocol I. ALOHA B. Bit-oriented…
Topic: UGC NET Computer Science June 2024 (Paper II)
 2
An IPv4 packet has arrived with the first few hexadecimal digits as shown below. How many hops can this packet travel b…
Topic: UGC NET Computer Science June 2024 (Paper II)
 3
Which of the following control problem does not exist, when processes unaware of each other during interaction?
Topic: UGC NET Computer Science June 2024 (Paper II)
 4
Which of the following is the Markup language?A. HTMLB. XMLC. DHTMLD. LMLE. PML
Topic: UGC NET Computer Science June 2024 (Paper II)
 5
Arrange the following prefix expressions based on their values in increasing order:A. + - * 2 / 8 4 3 2B. ↑ - * 3 3 * 4…
Topic: UGC NET Computer Science June 2024 (Paper II)
 6
Match List-I with List-II: List-I (Line coding scheme) List-II (Bandwidth – average) A. NRZ-L I. B …
Topic: UGC NET Computer Science June 2024 (Paper II)
 7
The instructionsADD R₁, A, B ADD R₂, C, D MUL X, R₁, R₂evaluate the expression $X = (A + B)(C + D)$ in which of the fol…
Topic: UGC NET Computer Science June 2024 (Paper II)
 8
For the fuzzy sets$A = {(x_1,0.3), (x_2,0.7), (x_3,0.4)}$ and$B = {(x_1,0.5), (x_2,0.2), (x_3,0.5)}$, the $A \cap B$ wo…
Topic: UGC NET Computer Science June 2024 (Paper II)
 9
Which of the following genetic algorithm operation is computationally most expensive?
Topic: UGC NET Computer Science June 2024 (Paper II)
 10
Multiple Inheritance is permitted directly in:A. C++B. JavaC. PythonD. VB.NETE. BASIC
Topic: UGC NET Computer Science June 2024 (Paper II)
Ask Your Question or Put Your Review.

loading...