Algorithms Previous Year Questions

Explanation

First analyse the problem, then develop an algorithm, code it, and finally test and debug it: (C), (A), (B), (D).

Explanation

Floyd's (Floyd-Warshall) algorithm finds shortest paths between every pair of vertices in O(V³). Dijkstra is single-source, Prim builds an MST, and Warshall finds transitive closure.

Explanation

Heapsort is O(n log n) even in the worst case. Quicksort's worst case is O(n²), and insertion and selection sort are O(n²).

Explanation

Corrected: the book's key says (b). The standard order is: analyse the problem, develop an algorithm, code, then test and debug.

Explanation

With LRU and 4 frames: 7, 0, 1, 2 are 4 faults; 3 replaces 7; 4 replaces 1; then 1 replaces 4. All other references are hits, so there are 7 page faults.

Explanation

Corrected: the book's key says (c), but (b) is the true statement. Binary search needs random access, so a linked list is unsuitable for it.

Explanation

Binary search halves the list at each step, and 32 = 2⁵, so it takes about log₂32 = 5 comparisons. Strictly, the worst case is ⌊log₂32⌋ + 1 = 6, but 6 is not an option, so the intended answer is 5.

Explanation

Linear search may have to check every one of the n elements in the worst case, so it takes O(n) time.

Explanation

The z-buffer method stores a depth value for every pixel, so it can handle any surface for which depth can be computed at each pixel, including non-polygonal and non-planar patches, with no sorting needed.

Explanation

If the item is equally likely to be at any position, the average number of comparisons is (1 + 2 + ... + n)/n = (n + 1)/2.

Explanation

For large n the growth order is log n < n < n log n < n² < 2ⁿ.

Explanation

The number of distinct BSTs on n keys is the Catalan number C(n) = (2n)!/((n+1)! n!). For n = 6 this is 132.

Explanation

Pass 1 merges pairs: (200,470)(80,150)(40,90)(300,400)(70,120). Pass 2 merges runs of two into fours: 80,150,200,470 | 40,90,300,400 | 70,120.

Explanation

Selection sort always makes about n²/2 comparisons, scanning the unsorted part for the minimum on each of n passes, so it is O(n²) in every case.

Explanation

<title> must be placed inside <head>, not outside it. It sets the page title shown in the browser tab, and search engines use it.

Explanation

Quicksort partitions the array around a pivot and recursively sorts the two parts, which is divide and conquer.

Explanation

Ciphertext is plaintext transformed by an encryption algorithm. Kerckhoffs's principle says the algorithm should be public and only the key secret, so II is false.

Explanation

Matching, sorting/classifying, comparing and seriation are pre-number concepts developed in the preschool years.

Explanation

Quick sort's worst case happens when the pivot is always the smallest or largest element, for example on already sorted input. Each partition then removes only one element, giving Θ(n²).

Explanation

Pass 1 moves 85 to the end: 37, 21, 54, 68, 12, 9, 57, 85. Pass 2 moves 68 to its place: 21, 37, 54, 12, 9, 57, 68, 85.

Explanation

Pass 1 (units): 720, 355, 436, 457, 657, 329, 839. Pass 2 (tens, stable): 720, 329, 436, 839, 355, 457, 657.

Explanation

Pass 1 swaps A with H: A, V, H, T, L, N, K. Pass 2 swaps H with V: A, H, V, T, L, N, K. Pass 3 swaps K with V: A, H, K, T, L, N, V.

Explanation

Big-Omega (Ω) gives an asymptotic lower bound. Big-O gives an upper bound and Theta (θ) a tight bound.

Explanation

A flowchart is a pictorial representation of a program's logic. Pseudo code and algorithms are written in text.

Explanation

Cohesion measures the functional strength of a module, i.e. how closely the elements inside one module work toward a single task. High cohesion is desirable.

Explanation

LCS is solved by dynamic programming, Huffman coding by a greedy algorithm, quick sort by divide and conquer, and the simplex method is for linear programming.

Explanation

Algorithm efficiency is measured by time complexity (running time) and space complexity (memory used).

Explanation

An algorithm is a step-by-step procedure that is independent of any programming language (I and III). It is actually easy to debug, so II is false.

Explanation

Binary search needs at most ⌊log₂n⌋ + 1 comparisons. 2¹³ = 8192 ≤ 12000 < 16384 = 2¹⁴, so ⌊log₂12000⌋ = 13 and the maximum is 14.

Explanation

In the worst case (reverse-sorted input) bubble sort makes n(n−1)/2 comparisons and swaps, so it is O(x²) with x elements.

Explanation

Bubble sort makes one swap per inversion. In S O R T E D (order D < E < O < R < S < T), the inversions are S:4, O:2, R:2, T:2, E:1, totalling 11 interchanges.

Explanation

In FIFO, increasing the number of frames can increase page faults for some reference strings (Belady's anomaly). Optimal and LRU are stack algorithms and do not suffer from it.

Explanation

Average cases: binary search O(log n) < linear search O(n) < quick sort O(n log n) < selection sort O(n²).

Explanation

A stable sort keeps records with equal keys in their original relative order. Insertion sort and merge sort are stable.

Explanation

The outer loop runs about n/2 times, and the inner loop doubles j, so it runs about log₂ n times. That gives O(n log n).

Explanation

Selection sort does at most one swap per pass, and there are n − 1 passes, so at most n − 1 swaps.

Explanation

This is exponentiation by squaring: each inner step halves m, and each outer step subtracts 1 from an odd m, making it even. So m reaches 0 in about 2 log₂ n steps, giving Θ(log n).

Explanation

Space complexity measures how much memory an algorithm needs to run, as a function of input size. Time complexity measures running time.

Explanation

Statement C is incorrect: a Las Vegas algorithm always gives the correct answer, but its running time depends on the random choices. A Monte Carlo algorithm has bounded time, but its output may vary or be wrong.

Explanation

Every algorithm must produce at least one output, have clear and unambiguous steps and terminate after finitely many steps. So "may not produce any output" is not a property of an algorithm.

Explanation

Best Fit must search the whole free list (or keep it sorted) to find the smallest hole that fits, so allocation takes longer. It also leaves many tiny unusable holes, so it does not guarantee less wastage or better performance.

Explanation

Theta notation bounds a function both from above and below by constant multiples of g(n), giving an asymptotically tight bound. Big O gives only an upper bound and Omega only a lower bound.

Explanation

Time complexity is analysed for the best, average and worst cases. A "test case" is an input used in software testing, not a case of complexity analysis.

Explanation

A flowchart shows an algorithm graphically using standard symbols joined by arrows. Pseudocode is a text description.

Explanation

In Cohen-Sutherland clipping, a line that crosses (intersects) the window boundary is partially visible and must be clipped. Lines fully inside are accepted and lines fully outside are rejected.

Explanation

Interdependence means the parts of a business system are closely interacting and depend on each other.

Explanation

Definiteness means every step of an algorithm is precisely and unambiguously defined.

Explanation

The Tabular Data Control (TDC) is a Microsoft ActiveX control that reads a delimited data file and shows the data in chosen areas of a web page.

Explanation

Triple DES uses three 56-bit DES keys, so the full key length is 3 × 56 = 168 bits.

Explanation

Optimisation problems ask for the best solution from a set of feasible solutions. Decision problems only need a yes/no answer.