25 questions · about 30 minutes. Press End Mock any time to see your score and the correct answers.
Let f(n) and g(n) be asymptotically positive functions. Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)). Statement II: f(n) = O(g(n)) ⇒ lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n. Choose the most appropriate answer.
Correct answer: A. Both Statement I and Statement II are correct
I is the transpose symmetry of O and Ω. For II, f ≤ c·g gives lg f ≤ lg c + lg g ≤ (lg c + 1)·lg g once lg g ≥ 1, so lg f = O(lg g). Both hold (CLRS Problem 3-4).
A. If some NP-complete problem P is in 𝒫, then 𝒫 = 𝒩𝒫. B. TSP is in 𝒩𝒫. C. SAT is in 𝒩𝒫. D. The Hamiltonian circuit problem is not NP-complete. Which are correct?
Correct answer: A. A, B and C only
A polynomial algorithm for one NP-complete problem solves all of NP. The decision versions of TSP and SAT are in NP. The Hamiltonian circuit problem is NP-complete, so D is false.
Suppose a circular queue of capacity n-1 elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variable respectively. Initially, REAR = FRONT =0. The conditions to detect queue empty and queue full are
Correct answer: A. EMPTY: REAR == FRONT FULL: ( REAR +1 ) mod n == FRONT
Leaving one slot empty: the queue is empty when REAR == FRONT and full when (REAR + 1) mod n == FRONT.
Given below are two statements: one is labelled as Assertion A and the other is labelled as
Reason R.
Assertion A: The AVL trees are more balanced as compared to Red Black trees, but they may cause more rotations during insertion and deletion
Reason R: A Red Black tree with n nodes has 2 log (n + 1) height that is greater than 2 and the AVL tree with n nodes has height less than – log (√5(n + 2)) − 2( Φ Φ where is golden ratio) In the light of the above statements, choose the correct answer from the options given below.
Correct answer: C. A is true but R is false
AVL trees are more strictly balanced and may rotate more on updates (A true). A red-black tree's height is at most 2 lg(n + 1), not greater than it, so R is false.
Consider a hash table of size seven with starting (6x + 3) mod 4 index zero and a hash function . Assuming the hash table is initially empty. Which of the following is the content of the table when 1, 3, 8, 10, 5 the sequence , is inserted into the table using closed hashing? Here "__ " denotes an empty location in the table.
Correct answer: D. _1,3,8,10,5_ C + +
h(1) = 9 mod 4 = 1 → slot 1. h(3) = 21 mod 4 = 1 → taken, slot 2. h(8) = 51 mod 4 = 3 → slot 3. h(10) = 63 mod 4 = 3 → slot 4. h(5) = 33 mod 4 = 1 → next free is 5. Table: _, 1, 3, 8, 10, 5, _.
Match List I with List II
Correct answer: B. A-IV B-III C-II D-I
Plain recursion for Fₙ takes Θ(φⁿ); memoization gives O(n); repeated squaring (integer addition and multiplication only) gives O(log n); the optimal bitonic tour DP takes O(n²).
Given below are two statements:
Statement I: If f and g are two functions and f = O(g) g ≠ o(f) but , we say that the growth rate of g is smaller than that of f
Statement II: The class of all decision problems decided by a TM in exponential time, that is O(2k) k , being a constant. In the light of the above statements, choose the most appropriate answer from the options given below.
Correct answer: B. Both Statement I and Statement II are incorrect
If f = O(g) and g ≠ o(f), then f and g grow at the same rate; g is not smaller than f, so Statement I is false. EXPTIME is decided in O(2^(nᵏ)) time — exponential in a power of n — not O(2ᵏ) for a constant k, so Statement II is false.
Assertion A: It is possible to create doubly linked list using only one pointer with every node.
Reason R: By storing the XOR of the addresses of the previous and next nodes. In the light of the above statements, choose the most appropriate answer from the options given below.
Correct answer: A. Both A and R are true and R is the correct explanation of A
An XOR linked list stores prev ⊕ next in one field; knowing one neighbour's address recovers the other. So a doubly linked list with one pointer per node is possible, and R explains how.
Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (binary tree). What is the minimum weighted path length?
Correct answer: B. 172
Huffman merges: 4 + 5 = 9; 8 + 9 = 17; 15 + 16 = 31; 17 + 25 = 42; 31 + 42 = 73. The weighted path length is the sum of the internal nodes: 9 + 17 + 31 + 42 + 73 = 172.
Consider: A. The number of labelled binary trees possible with n nodes is (2n)!/(n + 1)!. B. The number of binary search trees possible with n nodes is (2n)!/((n + 1)! n!). C. The number of unlabelled binary trees possible with n nodes is C(2n, n)/(n + 1)!. D. The number of simple, undirected, labelled graphs possible with n vertices is 2^(n(n−1)/2).
Correct answer: B. (A, B) and (D) are only correct
Unlabelled binary trees (and BSTs) number the Catalan number C(2n,n)/(n + 1) = (2n)!/((n + 1)! n!), so B is true and C (dividing by (n + 1)!) is false. Labelled trees multiply the Catalan number by n!: (2n)!/(n + 1)! (A true). Each of the C(n,2) possible edges is present or not: 2^(n(n−1)/2) (D true).
Which of the following are correct about Hamiltonian problems? A. The Hamiltonian cycle problem is NP-complete. B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian. C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph. D. If G is a connected undirected graph with at least three vertices, then G³ (obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian. E. If any NP-complete problem is polynomial-time solvable, then P = NP.
Correct answer: C. A, D, E only
A, D and E are true (D is a known result about the cube of a connected graph). A bipartite graph with an odd number of vertices can never be Hamiltonian, since a cycle alternates sides (B false). On a DAG, a Hamiltonian path is found in linear time with a topological sort (C false).
For matrix multiplication with a simple divide-and-conquer algorithm: A. the running time is T(n) = Θ(n³) B. the running time is T(n) = Θ(n² log n) C. the recurrence is T(n) = 8T(n/2) + Θ(n²) D. the recurrence is T(n) = 8T(2n) + Θ(n² log n) E. one of the cases of the master theorem applies
Correct answer: A. A, C, E only
Splitting into n/2 blocks needs 8 recursive multiplications plus Θ(n²) additions: T(n) = 8T(n/2) + Θ(n²). Since n^(log₂8) = n³ dominates n², master theorem case 1 gives Θ(n³).
Correct answer: B. A-III; B-IV; C-II; D-I
Linear programs are solved with the simplex algorithm; predicate logic is first-order logic; inorder is a tree traversal; Prim's algorithm solves the minimum spanning tree problem.
Correct answer: C. A-IV, B-I, C-II, D-III
8-queens uses backtracking; closest pair of points uses divide and conquer; string edit distance uses dynamic programming; the (fractional) knapsack problem uses a greedy method.
Directions (Q91–95): For a knapsack problem, the profits and weights of 7 items are P = {9, 5, 2, 7, 6, 16, 9} and W = {2, 5, 6, 11, 1, 9, 3}.
What is the maximum value of items you can carry if maximum weight allowed is 25 with a fractional knapsack?
Correct answer: A. 48.1
With capacity 25: items 5, 1, 7, 6 give 40 at weight 15; item 2 adds 5 (weight 20, profit 45); 5/11 of item 4 adds 7 × 5/11 ≈ 3.18. Total ≈ 48.1.
If new item is added to the list, total items is 8 and capacity is 25 , then the best-case time of fractional knapsack for this case is _____
Correct answer: C. O(24)
Fractional knapsack is dominated by sorting the items by ratio, O(n log n). For n = 8: 8 × log₂8 = 24.
Which of the following statements is correct for a knapsack?
Correct answer: D. In 0/1 knapsack problem, items cannot be divided into smaller portions and in fractional knapsack we can divide the item into required proportions of weight. Directions (96-100) Read the following passage and answer the given questions. Use the following schema of the academic institution relational database: student (rollno, name, degree, year, sex, deptno, advisor) department (deptid, name, hod, phone) professor (empid, name, sex, startyear, deptno, phone) course (courseid cname, credits, deptno) enrollment (rollno, courseid, sem, year, grade) teaching (empid, courseid, sem, year, classroom) prerequisite (precourseid, courseid) deptno is foreign key in the student, professor and course relations referring to deptid of department relation; advisor is a foreign key in the student relation referring to empid of professor relation; hod is a foreign key in the department relation referring to empid of professor relation; rollno is a foreign key in the enrollment relation referring to rollno of student relation; courseid is a foreign key in the enrollment, teaching relations referring to courseid of course relation; empid is a foreign key of the teaching relation referring to empid of professor relation; precourseid and courseid are foreign keys in the prerequisite relation referring to courseid of the course relation;
In 0/1 knapsack items are taken whole or not at all (solved by DP); in fractional knapsack items can be split (solved greedily).
How many different binary trees are possible with ' n ' nodes?
Correct answer: D. (1/(n + 1))·C(2n, n)
The number of structurally different binary trees with n nodes is the Catalan number C(2n, n)/(n + 1).
Let n be a positive integer and f(n) = 0 if n = 1, and f(n) = f(⌊n/2⌋) + 1 if n > 1. What is f(25), and what does the function compute?
Correct answer: A. 4, ⌊log₂ n⌋
f(25) = f(12) + 1 = f(6) + 2 = f(3) + 3 = f(1) + 4 = 4. Halving until 1 counts the halvings, i.e. ⌊log₂ n⌋.
Given the FFT we can have ______ time procedure for multiplying two polynomials A(x) Q and B(x) of degree bound n where input and output representations are in coefficient form, assuming n is a power of 2.
Correct answer: B. O(n log₂ n)
Evaluate both polynomials at 2n points with FFT, multiply pointwise, and interpolate with the inverse FFT: O(n log n) in total.
Circuit satisfiability problem: given a Boolean combinational circuit of AND, OR and NOT gates, is it satisfiable (is there an input for which the output is 1)? 1. Circuit-SAT belongs to NP. 2. Circuit-SAT is at least as hard as any language in NP. 3. Circuit-SAT is NP-complete. 4. The size of the circuit is Θ(k² + 1). 5. If P ≠ NP, this would contradict the NP-completeness of the problem.
Correct answer: C. 1, 2, 3 Only
Circuit-SAT is in NP (a satisfying input can be checked quickly), every NP language reduces to it (NP-hard), so it is NP-complete (CLRS Lemma 34.5–34.6). Statements 4 and 5 are not part of this result.
Given the expression (A + B * D)/(E − F) + G: 1. The prefix notation is + / + A * D B − E F G. 2. The prefix expression is the reverse of the postfix expression. 3. The order of operands in infix and postfix is the same. 4. The order of operands in infix, prefix and postfix is the same.
Correct answer: B. 3 and 4 Only
The correct prefix form is + / + A * B D − E F G, so statement 1 (with D B) is wrong. Prefix is not simply postfix reversed (2 false). Converting between notations moves only operators, so operands keep their order in all three forms (3 and 4 true).
Correct answer: B. a-III, b-II, c-I, d-IV
Dijkstra stores the total cost from the source to each node; Prim stores the minimum-cost edge to each vertex; Warshall computes the path (reachability) matrix; Kruskal finds a minimum spanning tree.
Given the graph below one of the following edges cannot be added in that order to find a minimum spanning tree algorithm.
Q
I. a-b
II. d-f
III. b-f
IV. d-c
V. d-e
Correct answer: C. II, I, III, V, IV
The MST uses a–b (1), d–f (1), b–f (2), d–c (2) and d–e (3). Kruskal adds edges in non-decreasing weight order, so d–e (3) cannot come before d–c (2). Sequence C (II, I, III, V, IV) does exactly that; the other orders are valid.
Statement 1: su Given a graph G=(V, E) in which each vertex v € V has an associated positive weight w(v), we can Q use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement 2 : Q The lower bound can be found by maximizing the following ∑n w(v)x(v) v∈V subject to Q x(u) + x(v) ≥ 1 for each (u, v) ∈ V x(v) ≤ 1 for each v ∈ V x(v) ≥ 0 for each v ∈ V In the light of the above statements, choose the most appropriate answer from the options given below:
Correct answer: C. Statement I is correct but Statement II is incorrect
The LP relaxation of weighted vertex cover gives a lower bound on the optimal weight (Statement I true). It must minimize Σ w(v)x(v), with constraints over edges (u, v) ∈ E, not maximize, so Statement II is incorrect.
