Data Structure and Algorithm Algorithms Flashcards

24 sample cards from the Algorithms deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. What is a hash collision and name two strategies to resolve it.

   A collision occurs when two distinct keys hash to the same index. Resolution strategies: (1) separate chaining (store colliding entries in a linked list per bucket) and (2) open addressing (probe for another slot, e.g., linear probing, quadratic probing, double hashing).

2. What is the load factor of a hash table and why does it matter?

   The load factor is $\alpha = \frac{n}{m}$, where $n$ is the number of stored entries and $m$ is the number of buckets. A high $\alpha$ increases collisions; tables typically resize (rehash) when $\alpha$ exceeds a threshold (e.g., $0.7$) to keep operations near $O(1)$.

3. What is the lower bound on time complexity for any comparison-based sorting algorithm, and why?

   $\Omega(n \log n)$. Any comparison sort corresponds to a decision tree with $n!$ leaves; its height is at least $\log_2(n!) = \Theta(n \log n)$.

4. State the worst-case and average-case time complexity of QuickSort and its space usage.

   Average: $O(n \log n)$. Worst case: $O(n^2)$ (e.g., already-sorted input with poor pivot). Space: $O(\log n)$ average for the recursion stack. It is in-place but not stable.

5. State the time and space complexity of MergeSort and whether it is stable.

   Time: $O(n \log n)$ in all cases. Space: $O(n)$ auxiliary. MergeSort is stable.

6. State the time and space complexity of HeapSort and whether it is stable.

   Time: $O(n \log n)$ in all cases. Space: $O(1)$ auxiliary (in-place). HeapSort is not stable.

7. What are the best, average, and worst-case complexities of Bubble Sort, Insertion Sort, and Selection Sort?

   Bubble: best $O(n)$, average/worst $O(n^2)$. Insertion: best $O(n)$, average/worst $O(n^2)$. Selection: $O(n^2)$ in all cases. All use $O(1)$ extra space.

8. What does it mean for a sorting algorithm to be 'stable'?

   A stable sort preserves the relative order of elements that compare equal. Examples: MergeSort, Insertion Sort, Bubble Sort. Not stable: QuickSort, HeapSort, Selection Sort.

9. How does Counting Sort work and what is its complexity?

   It counts occurrences of each key value within a known range $k$, then computes prefix sums to place elements directly. Time: $O(n + k)$; Space: $O(n + k)$. It is non-comparison-based and stable, efficient when $k = O(n)$.

10. How does Radix Sort work and what is its time complexity?

    It sorts numbers digit by digit (least or most significant first), using a stable sort (often Counting Sort) per digit. Time: $O(d(n + k))$, where $d$ is the number of digits and $k$ is the radix/base.

11. How does Bucket Sort work and when is it efficient?

    It distributes elements into buckets over a range, sorts each bucket (often with insertion sort), then concatenates them. Average time $O(n + k)$ when input is uniformly distributed; worst case $O(n^2)$ if all elements fall in one bucket.

12. Why can non-comparison sorts beat the $\Omega(n \log n)$ comparison bound?

    They do not compare elements pairwise; instead they exploit structure of the keys (e.g., integer values in a bounded range or fixed digit length), so the comparison decision-tree lower bound does not apply.

13. How does linear search work and what is its time complexity?

    It scans elements sequentially from the start until the target is found or the list ends. Time: $O(n)$ worst and average case, $O(1)$ best case. It works on unsorted data.

14. How does binary search work and what is its prerequisite and complexity?

    It requires a sorted array. It repeatedly compares the target to the middle element and discards half the search space. Time: $O(\log n)$; Space: $O(1)$ iterative.

15. Write the recurrence relation for binary search and state its solution.

    $T(n) = T\!\left(\frac{n}{2}\right) + O(1)$, which solves to $T(n) = O(\log n)$.

16. What is the typical mid-index formula in binary search and why is it written that way to avoid overflow?

    $mid = low + \frac{(high - low)}{2}$ instead of $\frac{(low + high)}{2}$, because the latter can overflow when $low + high$ exceeds the integer maximum.

17. What is the expected search time in a balanced BST, a hash table, and a sorted array (binary search)?

    Balanced BST: $O(\log n)$. Hash table: $O(1)$ average. Sorted array with binary search: $O(\log n)$. Unsorted array (linear): $O(n)$.

18. What is dynamic programming and what two properties must a problem have to use it?

    Dynamic programming solves problems by combining solutions to overlapping subproblems, storing results to avoid recomputation. Required properties: (1) optimal substructure and (2) overlapping subproblems.

19. What is the difference between memoization (top-down) and tabulation (bottom-up) in dynamic programming?

    Memoization is top-down recursion that caches results as subproblems are encountered. Tabulation is bottom-up, iteratively filling a table from base cases upward. Both avoid recomputation; tabulation usually avoids recursion overhead.

20. Give the dynamic programming recurrence for the 0/1 Knapsack problem.

    $dp[i][w] = \max\big(dp[i-1][w],\; v_i + dp[i-1][w - w_i]\big)$ if $w_i \leq w$, else $dp[i][w] = dp[i-1][w]$. Time and space: $O(nW)$.

21. What is the recurrence and complexity for the Longest Common Subsequence (LCS) of strings $X$ and $Y$?

    $dp[i][j] = dp[i-1][j-1] + 1$ if $x_i = y_j$, else $dp[i][j] = \max(dp[i-1][j],\, dp[i][j-1])$. Time and space: $O(mn)$.

22. What is a greedy algorithm and what property must a problem have for it to yield an optimal solution?

    A greedy algorithm makes the locally optimal choice at each step, hoping to reach a global optimum. It is provably optimal only when the problem exhibits the greedy-choice property and optimal substructure.

23. How does the greedy approach differ from dynamic programming?

    Greedy commits to one locally optimal choice at each step without revisiting it, never reconsidering. Dynamic programming explores and combines all relevant subproblem solutions, making it more powerful but typically slower and more memory-intensive.

24. Name three classic greedy algorithms and the problems they solve.

    Dijkstra's algorithm (single-source shortest paths, non-negative weights), Huffman coding (optimal prefix-free compression), and Kruskal's / Prim's algorithms (minimum spanning tree). The activity-selection and fractional-knapsack problems are also classic greedy examples.

What this deck covers

Algorithms flashcards FAQ