Data Structures & Algorithms Foundations & Complexity Analysis Flashcards

24 sample cards from the Foundations & Complexity Analysis deck

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

1. State the Fundamental Theorem of Arithmetic.

   Every integer greater than $1$ can be expressed uniquely as a product of prime powers, up to the ordering of factors: $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$.

2. How does the Sieve of Eratosthenes work and what is its time complexity?

   It marks multiples of each prime starting from $2$ as composite; unmarked numbers are prime. Its time complexity is $O(n \log \log n)$.

3. Define the expected value of a discrete random variable $X$.

   $E[X] = \sum_{x} x \cdot P(X = x)$, the probability-weighted average of all possible values.

4. State the linearity of expectation and note its key convenience.

   $E[X + Y] = E[X] + E[Y]$ for any random variables $X, Y$. It holds even when $X$ and $Y$ are not independent, making it powerful for analyzing randomized algorithms.

5. What is the expected number of comparisons (order) for randomized quicksort, and why?

   $O(n \log n)$ expected. A random pivot yields balanced splits on average; the expected comparison count is $\approx 2n \ln n$.

6. Define conditional probability $P(A \mid B)$.

   $P(A \mid B) = \frac{P(A \cap B)}{P(B)}$, provided $P(B) > 0$.

7. State Bayes' Theorem.

   $P(A \mid B) = \frac{P(B \mid A)\, P(A)}{P(B)}$.

8. What two components must every correct recursive function have?

   A base case (that stops recursion without further calls) and a recursive case that makes progress toward the base case on a smaller subproblem.

9. Write the recurrence relation for the running time of the merge sort algorithm.

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

10. State the Master Theorem for recurrences of the form $T(n) = aT\!\left(\frac{n}{b}\right) + f(n)$.

    Compare $f(n)$ with $n^{\log_b a}$. Case 1: if $f(n) = O(n^{\log_b a - \epsilon})$ then $T(n) = \Theta(n^{\log_b a})$. Case 2: if $f(n) = \Theta(n^{\log_b a})$ then $T(n) = \Theta(n^{\log_b a} \log n)$. Case 3: if $f(n) = \Omega(n^{\log_b a + \epsilon})$ and regularity holds then $T(n) = \Theta(f(n))$.

11. Apply the Master Theorem to $T(n) = 2T\!\left(\frac{n}{2}\right) + \Theta(n)$.

    Here $a = 2$, $b = 2$, so $n^{\log_b a} = n^{1} = n$, matching $f(n) = \Theta(n)$ (Case 2). Thus $T(n) = \Theta(n \log n)$.

12. Solve the recurrence $T(n) = T(n-1) + O(1)$ with $T(1) = O(1)$.

    $T(n) = \Theta(n)$, since the constant work accumulates over $n$ levels of linear-depth recursion.

13. What is the substitution method for solving recurrences?

    Guess a bound for the solution, then use mathematical induction to prove the guess is correct by verifying it satisfies the recurrence and base cases.

14. How does the recursion-tree method estimate a recurrence's cost?

    Expand the recurrence into a tree where each node is a subproblem cost; sum the costs at each level, then sum across all levels to get the total, giving a good guess for a closed form.

15. Define the Fibonacci recurrence and give its exponential naive time complexity.

    $F(n) = F(n-1) + F(n-2)$ with $F(0)=0, F(1)=1$. Naive recursion runs in $O(\varphi^{n})$ where $\varphi = \frac{1+\sqrt{5}}{2}$, i.e. exponential.

16. What is tail recursion?

    A recursive call that is the very last operation in a function, with nothing left to compute after it returns. No pending work remains on the current frame.

17. Why can tail recursion be optimized, and what is the benefit?

    Because no work follows the recursive call, the compiler can reuse the current stack frame (tail-call optimization), converting the recursion into a loop and reducing stack space from $O(n)$ to $O(1)$.

18. List the six common bitwise operators and their symbols.

    AND ($\&$), OR ($|$), XOR ($\wedge$), NOT ($\sim$), left shift ($\ll$), and right shift ($\gg$).

19. What arithmetic effect do left shift and right shift have on an unsigned integer?

    $x \ll k$ multiplies by $2^{k}$; $x \gg k$ performs integer division (floor) by $2^{k}$, i.e. $\lfloor \frac{x}{2^{k}} \rfloor$.

20. How do you check whether the $i$-th bit of $x$ is set, and how do you set it?

    Check: $(x \;\&\; (1 \ll i)) \neq 0$. Set: $x \;|\; (1 \ll i)$. Clear: $x \;\&\; \sim(1 \ll i)$. Toggle: $x \wedge (1 \ll i)$.

21. What does the bit trick $x \;\&\; (x-1)$ do?

    It clears (turns off) the lowest set bit of $x$. Repeatedly applying it counts set bits, and $x \;\&\; (x-1) = 0$ tests whether $x$ is a power of two.

22. How do you extract the lowest set bit of $x$, and how do you test if $x$ is a power of two?

    Lowest set bit: $x \;\&\; (-x)$. Power-of-two test: $x > 0$ and $(x \;\&\; (x-1)) = 0$.

23. How is a subset of an $n$-element set represented with bit masking, and how many masks are there?

    Each element maps to one bit; a subset is an integer where set bits indicate membership. There are $2^{n}$ possible masks, enumerated by iterating an integer from $0$ to $2^{n}-1$.

24. Using Brian Kernighan's algorithm, what is the time complexity of counting set bits in an integer, and why is it efficient?

    It runs in $O(s)$ where $s$ is the number of set bits, because each iteration of $x = x \;\&\; (x-1)$ removes exactly one set bit, rather than looping over all bit positions.

What this deck covers

Foundations & Complexity Analysis flashcards FAQ