Unit 3 - Practice Quiz

1 Which algorithm design paradigm is primarily used by both Merge Sort and Quick Sort?

2 What is the worst-case time complexity of the Binary Search algorithm on a sorted array of elements?

3 The Karatsuba algorithm for multiplying large integers reduces the number of recursive multiplications from 4 to what number?

4 Strassen's Matrix Multiplication algorithm is faster than the standard matrix multiplication. What is its time complexity?

5 The Master Method is typically applied to recurrences of which of the following forms?

6 In a recursion tree used to solve a recurrence relation, what does the value at each node represent?

7 What is the primary mathematical technique used to prove the guessed bounds in the Substitution Method?

8 Insertion Sort is a classic example of the Decrease and Conquer paradigm. By how much does it decrease the problem size in each step?

9 Which data structure is primarily used to implement Breadth-First Search (BFS)?

10 Which data structure is naturally suited for implementing Depth-First Search (DFS) iteratively?

11 Topological sorting is only possible for which type of graph?

12 In the context of the Transform and Conquer paradigm, what is 'presorting'?

13 In an AVL tree, what is the maximum allowed difference in height between the left and right subtrees of any node?

14 Which of the following sorting algorithms is a non-comparison-based integer sorting algorithm?

15 How does Radix Sort typically process the individual digits of numbers?

16 Bucket Sort works most efficiently when the input elements are:

17 In a Max-Heap, what is the required relationship between a parent node and its children?

18 What is the primary purpose of a hash function in a Hash Table?

19 Which sorting algorithm works by repeatedly swapping adjacent elements if they are in the wrong order?

20 The Convex-Hull problem aims to find the smallest convex polygon that:

21 What is the time complexity of the recurrence relation using the Master Theorem?

22 In Quick Sort, if the partition algorithm always chooses the largest or smallest element as the pivot, what is the resulting time complexity?

23 How many scalar multiplications are required by Strassen's algorithm to multiply two matrices, and what is its asymptotic time complexity?

24 Which of the following is the recurrence relation for the standard Binary Search algorithm?

25 Karatsuba's algorithm for multiplying two -digit integers reduces the number of recursive multiplications from 4 to 3. What is its time complexity?

26 In the divide and conquer algorithm for the Closest-Pair problem, after dividing the points into two halves, what is the maximum number of points in the strip that need to be checked for a given point?

27 Suppose we guess that for the recurrence . What is the condition on to make the inductive proof work (ignoring base cases)?

28 In the recursion tree for , what is the total cost at depth of the tree?

29 Which data structure is primarily used to implement Breadth-First Search (BFS) and Depth-First Search (DFS) respectively?

30 Topological sorting can only be applied to which type of graph?

31 In the worst-case scenario, how many comparisons are made by Insertion Sort to sort an array of elements?

32 What is the minimum number of comparisons required to find both the minimum and maximum of an array of elements simultaneously?

33 Which of the following is a key limitation of the Counting Sort algorithm?

34 If Radix Sort uses Counting Sort as a subroutine to sort numbers having digits each, what is the overall time complexity? (Assume the base/radix is ).

35 What is the time complexity to build a max-heap from an unsorted array of elements using the standard bottom-up build-heap approach?

36 In open addressing with linear probing, the hash function is modified to . What primary issue does linear probing suffer from?

37 In an AVL tree, what is the maximum allowed difference in heights between the left and right subtrees of any node?

38 How does presorting an array optimize the problem of checking for duplicate elements in an array?

39 Which algorithm is commonly used to find all Strongly Connected Components (SCCs) of a directed graph in time?

40 Which sorting algorithm performs the minimum number of swaps in the worst-case scenario?

41 Consider the recurrence relation . Which case of the Master Theorem applies, and what is the tight asymptotic bound?

42 In Quick Sort, suppose the partition function is modified such that it always produces a split of and of the array elements. What is the exact depth of the deepest node in the recursion tree (in terms of )?

43 Strassen's algorithm multiplies two matrices using $7$ multiplications of matrices. If a new divide-and-conquer algorithm breaks matrices into submatrices, what is the maximum number of submatrix multiplications it can use to be asymptotically faster than Strassen's?

44 When solving the recurrence using the substitution method to prove , why does a direct induction hypothesis often fail for the base cases (e.g., )?

45 In the divide-and-conquer algorithm for the Closest-Pair problem in 2D, a strip of width is analyzed where is the minimum distance found in the left and right subsets. What is the maximum number of points in the right half of the strip that need to be compared against a given point in the left half, ensuring the distance condition is maintained?

46 Given a Directed Acyclic Graph (DAG) , how many unique topological sorts exist if is a set of disjoint directed paths, where the -th path has length ?

47 In a directed graph, a DFS is performed. Which combination of edge types implies the graph has a cycle?

48 Karatsuba's algorithm for multiplying two -bit integers achieves a time complexity of . If applied to two numbers of size , what is the size of the recursive subproblems, and how many are there?

49 For the recurrence , what is the total cost of the nodes at depth in the recursion tree, assuming the tree is full at that depth?

50 In an AVL tree, what is the maximum number of rotations required to restore the AVL property after a single node deletion?

51 Counting Sort is stable. If an array of elements has a maximum value , why is standard Counting Sort generally not used, and how can Radix Sort resolve this?

52 Given an array of elements, the Floyd method to build a Max-Heap (calling max_heapify bottom-up) takes time. Why is it strictly faster asymptotically than inserting elements one by one into an initially empty heap?

53 In a hash table using open addressing with linear probing, the table size is and there are elements. If and the step size are not coprime, what is the worst-case consequence for insertion?

54 To find both the minimum and maximum of an array of elements simultaneously, the optimal number of comparisons is:

55 When analyzing Insertion Sort, the number of shifts (or swaps) is directly proportional to which specific property of the input array?

56 In Tarjan's strongly connected components algorithm, a node is identified as the root of an SCC if and only if:

57 Given a sorted array of distinct integers , finding an index such that can be done in time using Binary Search. If the integers are not distinct, what is the worst-case time complexity?

58 Suppose we sort strings of length over an alphabet of size using LSD (Least Significant Digit) Radix sort. If , what is the overall time complexity?

59 An algorithm determines if an array contains two elements that sum to exactly . By presorting the array in time, the search phase can be reduced to:

60 Consider Bubble Sort and Selection Sort applied to an array of elements. Which statement accurately compares their minimum number of element swaps in the worst-case input scenario?