Quiz: Algorithms and Problem-Solving Strategies

Test your understanding before moving on. Target: 70% or higher to proceed confidently.

Section 1: Multiple Choice (1 point each)

1. Which of the following BEST describes Big-O notation?

  • A) The exact number of operations an algorithm performs
  • B) How fast an algorithm runs on a specific computer
  • C) How an algorithm's running time grows as input size increases
  • D) The maximum size of input an algorithm can handle
Answer **C)** How an algorithm's running time grows as input size increases. *Why C:* Big-O describes the growth rate — the *shape* of the curve — not exact counts or speeds. *Why not A:* Big-O drops constants and lower-order terms; it doesn't give exact counts. *Why not B:* Big-O is hardware-independent. *Why not D:* Big-O doesn't describe input limits — any algorithm can handle any size, just slower. *Reference:* Section 17.2

2. What is the Big-O of this code?

for i in range(n):
    for j in range(n):
        print(i, j)
  • A) O(n)
  • B) O(n log n)
  • C) O(n²)
  • D) O(2n)
Answer **C)** O(n²) *Why C:* The outer loop runs n times; for each iteration, the inner loop also runs n times. Total: n × n = n². *Why not A:* That would be a single loop. *Why not B:* Linearithmic complexity involves halving at some point. *Why not D:* O(2n) simplifies to O(n), and this is quadratic, not linear. *Reference:* Section 17.3.4

3. What is the time complexity of accessing an element in a Python list by index (e.g., my_list[5])?

  • A) O(n)
  • B) O(log n)
  • C) O(1)
  • D) O(n²)
Answer **C)** O(1) *Why C:* Python lists are implemented as arrays; accessing by index is a direct memory lookup regardless of list size. *Why not A:* That would mean scanning through the list, which isn't needed for index access. *Reference:* Section 17.3.1

4. Which complexity class describes an algorithm that cuts the problem in half at each step?

  • A) O(1)
  • B) O(n)
  • C) O(log n)
  • D) O(n²)
Answer **C)** O(log n) *Why C:* Halving repeatedly means you need log₂(n) steps to reach 1. Example: binary search. *Why not A:* O(1) does the same work regardless of input size. *Why not B:* O(n) processes every element once. *Why not D:* O(n²) compares every element with every other. *Reference:* Section 17.3.2

5. What is the Big-O of this code?

for i in range(n):
    for j in range(100):
        print(i + j)
  • A) O(n²)
  • B) O(100n)
  • C) O(n)
  • D) O(n + 100)
Answer **C)** O(n) *Why C:* The inner loop runs a constant 100 times regardless of n. Total: 100n = O(n) after dropping the constant. *Why not A:* Both loops would need to depend on n for O(n²). *Why not B:* O(100n) simplifies to O(n) — constants are dropped. *Why not D:* O(n + 100) also simplifies to O(n). *Reference:* Section 17.2.2, Check Your Understanding #1

6. A greedy algorithm:

  • A) Always finds the optimal solution
  • B) Tries every possible solution
  • C) Makes the locally optimal choice at each step
  • D) Splits the problem in half and solves each half
Answer **C)** Makes the locally optimal choice at each step. *Why C:* This is the definition of greedy — always pick the best option available right now. *Why not A:* Greedy only finds the optimal solution for problems with the greedy-choice property. *Why not B:* That's brute force. *Why not D:* That's divide and conquer. *Reference:* Section 17.6

7. Which problem-solving strategy is BEST described as "try every possibility"?

  • A) Greedy
  • B) Divide and conquer
  • C) Dynamic programming
  • D) Brute force
Answer **D)** Brute force. *Why D:* Brute force systematically enumerates all candidates and checks each one. *Why not A:* Greedy picks the locally best option, skipping many possibilities. *Why not B:* Divide and conquer splits the problem, doesn't try every possibility. *Why not C:* Dynamic programming avoids redundant work by storing subproblem solutions. *Reference:* Section 17.5

8. What is the key insight behind divide and conquer?

  • A) Always choose the largest element first
  • B) Break the problem into smaller instances of the same problem
  • C) Try every combination of inputs
  • D) Use a dictionary for fast lookups
Answer **B)** Break the problem into smaller instances of the same problem. *Why B:* Divide and conquer splits a problem into subproblems of the same type, solves them, and combines the results. *Why not A:* That's greedy thinking. *Why not C:* That's brute force. *Why not D:* That's a data structure technique, not a problem-solving strategy. *Reference:* Section 17.7

9. O(n² + n) simplifies to:

  • A) O(n² + n)
  • B) O(n²)
  • C) O(n³)
  • D) O(2n²)
Answer **B)** O(n²) *Why B:* Drop lower-order terms. As n grows, n² dominates n completely. *Why not A:* Big-O always drops lower-order terms. *Why not C/D:* These are different growth rates entirely. *Reference:* Section 17.2.2

10. Which is faster for looking up a value: a Python list or a Python dict?

  • A) List — it's simpler
  • B) Dict — it uses hashing for O(1) average lookup
  • C) They're the same speed
  • D) It depends on the size of the data
Answer **B)** Dict — it uses hashing for O(1) average lookup. *Why B:* Dict lookup is O(1) on average (hash table). List lookup with `in` is O(n) (linear scan). *Why not A:* Simplicity doesn't determine speed; lists require scanning. *Why not C:* They use fundamentally different data structures. *Why not D:* For a handful of items the difference is too small to notice (a short list can even win on constant factors), but as the data grows the list keeps getting slower while the dict doesn't. B is the best general answer. *Reference:* Section 17.3, Spaced Review ([Chapter 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))

Section 2: Short Answer (2 points each)

11. Explain why an algorithm that is O(n²) on 100 items might seem "fast enough" but becomes impractical on 100,000 items. Use specific numbers to support your answer.

Answer With 100 items, O(n²) means ~10,000 operations — fast on any modern computer. With 100,000 items, O(n²) means ~10,000,000,000 (10 billion) operations. If each operation takes 1 nanosecond, that's 10 seconds — noticeable. And the problem compounds: 1,000,000 items would mean 10¹² operations (~16 minutes). The quadratic growth makes the algorithm impractical as data scales, even though it appeared fine on small inputs. *Reference:* Section 17.2, Threshold Concept

12. Write the Big-O complexity for each of these operations and briefly explain: - a) Appending to a Python list - b) Inserting at position 0 of a Python list - c) Looking up a key in a dict - d) Checking if an element is in a list using in

Answer - a) **O(1)** amortized — append adds to the end; Python pre-allocates space. - b) **O(n)** — every existing element must shift right by one position. - c) **O(1)** average — hash table lookup. - d) **O(n)** worst case — must scan through the entire list. *Reference:* Sections 17.3.1, 17.3.3, 17.10 (operations table), Spaced Review ([Ch 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))

13. Give an example of a problem where brute force is the most practical approach. Explain why a more sophisticated algorithm isn't needed.

Answer Finding the best combination of 3 items from a list of 20 (e.g., project selection). C(20, 3) = 1,140 combinations — brute force checks all of them in milliseconds. A more sophisticated algorithm (greedy, dynamic programming) adds implementation complexity without meaningful speed improvement because the input is inherently small. *Reference:* Section 17.5.1

14. Explain the time-space trade-off using the duplicate-detection example from the chapter. Which version is faster? Which uses less memory?

Answer The O(n²) nested-loop version uses O(1) extra space (just loop variables) but is slow. The O(n) set-based version uses O(n) extra space (to store the set of seen elements) but is fast. Trading memory for speed: the set version allocates extra memory to avoid redundant comparisons. For large inputs, the time savings are dramatic (thousands of times faster for just 10,000 items in the chapter's timing test). *Reference:* Section 17.9.2

Section 3: Code Analysis (3 points each)

15. What is the Big-O of this function? Trace its execution for n = 8.

def halver(n: int) -> None:
    while n >= 1:
        print(n)
        n //= 2
Answer **O(log n)**. The value of n is halved each iteration, so the loop runs ⌊log₂(n)⌋ + 1 times (the + 1 is the final pass when n is 1). Trace for n = 8: - Iteration 1: print 8, n becomes 4 - Iteration 2: print 4, n becomes 2 - Iteration 3: print 2, n becomes 1 - Iteration 4: print 1, n becomes 0 - Loop ends (0 < 1) Output: 8, 4, 2, 1 (4 iterations = log₂(8) + 1) *Reference:* Section 17.3.2

16. What does this function return, and what is its Big-O?

def compute(items: list[int]) -> int:
    total = 0
    for i in range(len(items)):
        for j in range(i):
            total += items[j]
    return total
Answer The function sums all prefix sums: for each position i, it sums all elements before position i and adds that to a running total. For `[3, 1, 4]`: - i=0: inner loop doesn't run (range(0) is empty) - i=1: adds items[0] = 3, total = 3 - i=2: adds items[0] + items[1] = 3 + 1 = 4, total = 7 So `compute([3, 1, 4])` returns 7. Notice the last element never gets added: the inner loop only reaches positions *before* i. The Big-O is **O(n²)**: the inner loop runs 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 times. *Reference:* Section 17.4.1

17. A teammate wants to reuse this greedy change-making function for other currencies by editing the coins list. Does it return the fewest coins for US coins as written? What could go wrong after the edit? Give a concrete example.

def make_change(amount: int) -> list[int]:
    coins = [25, 10, 5, 1]
    result = []
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return result
Answer As written, the function is correct: for US denominations [25, 10, 5, 1], greedy always gives the fewest coins. The danger is the hidden assumption. If the denomination list changes, greedy may stop being optimal: - Coins [4, 3, 1], amount 6: greedy gives [4, 1, 1] (3 coins), but [3, 3] needs only 2. - Coins [25, 10, 1] (no nickels), amount 30: greedy gives [25, 1, 1, 1, 1, 1] (6 coins), but [10, 10, 10] needs only 3. The real "bug" is assuming greedy always works. It only works when the coin system has the greedy-choice property, so a reusable version should document that assumption (or use a different algorithm for arbitrary coins). *Reference:* Section 17.6.2

Section 4: Applied Reasoning (3 points each)

18. You have a sorted list of 1,000,000 names. You need to check whether "Zara" is in the list. Would you use a linear scan O(n) or binary search O(log n)? How many comparisons would each require in the worst case?

Answer Use **binary search** — O(log n). - Linear scan worst case: 1,000,000 comparisons (check every name). - Binary search worst case: log₂(1,000,000) ≈ 20 comparisons. Binary search is ~50,000x fewer comparisons. Since the list is already sorted, binary search's precondition is met. *Reference:* Section 17.3.2

19. A developer writes a function to find common elements between two lists:

def common_elements(list_a, list_b):
    result = []
    for item in list_a:
        if item in list_b:
            result.append(item)
    return result

What is the Big-O if list_a has n elements and list_b has m elements? How could you improve it?

Answer **O(n × m)**: For each of the n elements in list_a, `item in list_b` scans up to m elements. **Improvement:** Convert list_b to a set first: 
set_b = set(list_b)      # O(m)
result = [item for item in list_a if item in set_b]  # O(n)
Total: O(n + m), using O(m) extra space for the set. *Reference:* Sections 17.3.3, 17.9.2

20. You're building a spell-checker. For each word the user types, you need to check if it's in a dictionary of 200,000 words. Which data structure would you choose (list, set, or dict)? What's the Big-O of each check? If the user types a 500-word essay, what's the total Big-O for checking all words?

Answer Use a **set** (or a dict if you need extra information per word). Let n = 200,000 dictionary words and w = 500 essay words. - List: Each check is O(n) — a misspelled word forces a scan of all 200,000 entries. Total: O(w × n), up to 500 × 200,000 = 100,000,000 comparisons. - Set: Each check is O(1) on average — one hash lookup, no matter how big the dictionary is. Total: O(w), about 500 lookups. The list version's cost grows with the size of the dictionary; the set version's doesn't. Building the set from the word list is a one-time O(n) cost, paid before the user starts typing. *Reference:* Section 17.3, Spaced Review ([Ch 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))