Unit 1: Introduction - Practice Quiz

1 Which principle describes how elements are removed from a stack?

2 Which principle is normally followed by a queue?

3 Which data structure stores elements that are commonly accessed using an index?

4 In the basic Random Access Machine model, how are simple operations usually treated?

5 What is the main purpose of a computational model in algorithm analysis?

6 What does commonly represent when analysing an algorithm?

7 What does the best-case running time describe?

8 What does the worst-case running time describe?

9 What does average-case analysis estimate?

10 What is the worst-case number of element comparisons in a linear search through elements?

11 What does big notation commonly express?

12 Which complexity represents linear growth?

13 Which notation represents constant-time complexity?

14 What is the big complexity of ?

15 What is recursion?

16 What is the purpose of a base case in recursion?

17 Which formula correctly defines factorial recursively for ?

18 What does a recurrence relation describe in recursive algorithm analysis?

19 What is the asymptotic solution of with ?

20 What is the asymptotic solution of with ?

21 A queue initially contains , with at the front. After performing dequeue, enqueue(40), and enqueue(50), what is the queue from front to rear?

22 Which data structure is most appropriate for processing nested function calls in the order required for returns?

23 A graph has vertices and edges, where is much smaller than . Which representation generally uses less space?

24 A binary search tree contains the keys inserted in that order. Which key is the left child of ?

25 In the unit-cost RAM model, an algorithm executes primitive operations. What running time is assigned to it asymptotically?

26 In the comparison model, a comparison-based sorting algorithm is represented by a binary decision tree. What does each leaf represent?

27 Why can treating arithmetic on arbitrarily large integers as a constant-time operation produce a misleading analysis?

28 For linear search on an array of distinct elements, which situation gives the best-case running time?

29 Suppose a successful linear search is equally likely to target any of the array positions. What is the expected number of comparisons?

30 Quicksort always chooses the first element as its pivot. Which input is most likely to produce its worst-case behaviour?

31 An algorithm takes operations with probability and operations with probability . What is its expected operation count?

32 What is the tightest big O bound among the choices for ?

33 Consider a loop where starts at and is doubled after each iteration until . What is the loop's running time?

34 An outer loop runs times, while an inner loop runs from through the current outer-loop index . What is the total running time?

35 What value is returned by the following function when called as ? and for .

36 A recursive function reduces its argument from to and performs constant work per call. What is its maximum call-stack depth?

37 Which change is necessary to prevent infinite recursion in a function that repeatedly calls itself with a smaller positive integer?

38 What is the asymptotic solution of with ?

39 What is the asymptotic solution of with ?

40 What is the asymptotic solution of with ?

41 A dynamic array starts empty with capacity . Whenever an append finds the array full, its capacity is doubled and all existing elements are copied before the new element is inserted. If , how many existing-element copies occur during the first appends?

42 A queue is implemented using input and output stacks. Enqueue pushes onto the input stack; dequeue transfers every item to the output stack only when the output stack is empty. For any sequence of operations starting from empty, which bounds are tight?

43 A disjoint-set forest uses both union by rank and path compression. For operations, including Make-Set operations, which asymptotic bound applies to the total running time?

44 Which capability is available in a word-RAM with -bit words but not generally in a pure pointer-machine model?

45 An algorithm computes using multiplications. Why does the claim that its running time is fail in the bit-complexity model?

46 In the deterministic comparison-tree model, an algorithm sorts distinct keys. What lower bound follows directly from the number of possible input orders?

47 A binary string of length is selected uniformly from all nonzero strings. An algorithm scans left to right and stops at the first . What is the exact expected number of inspected bits?

48 Randomized Quicksort chooses its pivot uniformly from the current subarray. For any fixed input containing distinct keys, which statement correctly distinguishes expected and worst-randomness behavior?

49 An algorithm has best-case running time and worst-case running time . Without specifying an input distribution, what can be concluded about its average-case time?

50 For integers , let . Which statement is true?

51 Let . Which asymptotic classification is correct for every fixed and ?

52 Define when is prime and otherwise. Which relation between and is correct?

53 Quicksort is modified to recurse only on the smaller partition and to process the larger partition by iteration. What are the tight worst-case time and auxiliary-stack bounds?

54 A top-down recursive Fibonacci algorithm evaluates and memoizes every computed value. Including the memo table and recursion stack, what are its tight time and space bounds?

55 Consider a recursive procedure that makes two separate calls on and performs local work, without memoization. What is its total running time?

56 For powers of two, solve with .

57 Assume constant base-case cost. What is the solution of ?

58 For powers of two and constant base-case cost, solve for .

59 Given and , which bound is tight?

60 For sufficiently large , let with a constant-size base case. What is the tight solution?