Algorithms Previous Year Questions

Explanation

When the two modules run one after the other, the total time is h(n) + g(n), which is O(max(h(n), g(n))) because the larger term dominates and lower-order terms are ignored. Hence the answer is (b).

Explanation

N! < nⁿ for all n ≥ 1, so n! is O(nⁿ). Using Stirling's approximation, log(n!) ≈ n log n − n + O(log n), so log n! is O(n log n). Therefore, the correct answer is (b) O(nⁿ) and O(n log n).

Explanation

There are 14 relative complexity adjustment factor are (1) Requirement for reliable backup and recovery (2) Require for data communication (3) Extent of distributing processing (4) Performance requirement (5) Expected operational environment (6) Extent of online data entries (7) Extent of multi-operation online data input. (8) Extent of online updating of master files. (9) Extent of complex inputs, outputs. (10) Extent of complex data processing. (11) Extent of currently developed code can be designed for reuse. (12) Extent of conversion and installation in the design. (13) Extent of multiple installation in an organization. (14) Extent of change and focus on ease of use.

Explanation

P₁/w₁ = 5, p₂/w₂ = 2.5, p₃/w₃ = 2, p₄/w₄ = 2. Select object 1 (profit 10), then object 2 (profit 10). Objects 3 and 4 have the same ratio, but object 4 gives more profit and fits exactly: total weight = 2 + 4 + 9 = 15. Maximum profit = 10 + 10 + 18 = 38. So the answer is (b).

Explanation

For a sorted list followed by a few random elements: bubble sort and selection sort take O(n²) time, quick sort degrades to its O(n²) worst case on nearly sorted input, while insertion sort takes close to O(n) time. Hence insertion sort is most suitable.

Explanation

The DES algorithm works with a 64-bit block size, employs 16 processing rounds, and is driven by a 56-bit key (with 8 additional parity bits), making up a total of 19 distinct stages.

Explanation

Dijkstra's algorithm for the single-source shortest-paths problem is a greedy algorithm, and the Floyd-Warshall algorithm for all-pairs shortest paths is a dynamic programming algorithm.

Explanation

The complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

Explanation

Radix sort because it sorts in integers in range 0 … (n² – 1) in O(n) time using base-n representation.

Explanation

SSTF from cylinder 24: 24 → 26 (2) → 12 (14) → 8 (4) → 4 (4) → 42 (38) → 50 (8). Total distance = 70 cylinders. Seek time = 70 × 6 msec = 420 msec = 0.42 sec.

Explanation

(a) Size oriented metrics is directly implied with (iii) (b) Function oriented metrics is number of user inputs, number of user outputs, number of files, number of external interfaces. So it satisfies (i) (c) Extended function point metrics is a superset of the function point measure that can be applied to system. It uses algorithm characteristics as one of the measurement parameter. (d) Function point is a "unit of measurement" to express the amount of business functionality an information provides to a user.

Explanation

The Floyd-Warshall algorithm solves the all-pairs shortest-paths problem efficiently in O(n³) time using dynamic programming.

Explanation

It will be solved by using branch and bound technique. The travelling salesman problem is NP- complete problem. It can also be solved by- one of the earliest application of dynamic programming is the Held-Karp algorithm to solve TSP in time O(n².2ⁿ).

Explanation

Branch and bound is an algorithm design paradigm for discrete and combinatorial optimization problems; it systematically enumerates candidate solutions by state space search. In branch and bound, the dynamic programming principle can be used to discard redundant partial paths.

Explanation

Recursion does not offer better space or time complexity; it only makes the program compact and simpler to write and understand than a non-recursive implementation. The non-recursive version avoids function-call overhead and stack space.

Explanation

In-place sorts do not need extra space beyond the input array; any extra space they use is a constant, O(1).

Explanation

Consider k buckets. For each digit: (1) place each number in the appropriate bin – O(n); (2) append all the k bins sequentially – O(k). With d digits, the total is O(d(n + k)).

Explanation

Given reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4. (i) FIFO with 3 page frames: faults occur at 0, 1, 2, 3, 0, 1, 4, 2, 3 (hits at the 2nd 0 and 1 after 4). Total page faults = 9. (ii) FIFO with 4 page frames: faults occur at 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 (hits at 0 and 1 before 4 is loaded). Total page faults = 10. This is Belady's anomaly.

Explanation

Correct matching: Huffman codes – O(nlogn); Optimal polygon triangulation – θ(n³); Activity selection problem – θ(n); Quicksort – O(n²).

Explanation

(i) Corrective maintenance fixes errors observed when the software is in use – (B). (ii) Adaptive maintenance changes the software to make it adaptable to a new environment – (C). (iii) Perfective maintenance implements new or changed user requirements – (D). (iv) Preventive maintenance performs activities to reduce complexity and prevent future errors – (A).

Explanation

Radix sort performs one stable counting sort per digit; each pass takes O(n + k) time and there are d digits. So n integers of d digits, each digit in {1, 2, ..., k}, are sorted in O(d(n + k)) time.

Explanation

Dijkstra's algorithm always chooses the closest vertex in V – S to add to the set S, where S is the set of vertices whose final shortest-path weights from the source are known. So it is a greedy algorithm.

Explanation

Game playing uses heuristic search, since brute-force computation over hundreds of thousands of positions is not practical.

Explanation

Merge sort performs O(n log n) comparisons, and comparing two strings of length n takes O(n) time in the worst case. So the worst-case running time is O(n · n log n) = O(n² log n).