Midterm 1: Learn, Practice, Recall

Content locked

The catalog is public. Reading this content requires approved access.

1. How to use this guide

2. What a complete answer looks like [Core]

3. Take or skip: a complete first DP [Core]

Indexing first

Worked table

An exam-ready answer

Question 1: Change the restriction

4. Growth and runtime recurrences [Core]

Growth rates

A runtime recurrence counts work

Question 2: Short analysis drill

5. Sorting and comparison lower bounds [Core]

Worked example: sorting a polynomial integer range

A short lower-bound proof

Question 3: Can counting sort do this?

6. Divide and conquer: what happens between the halves? [Core]

Search: justify discarding a half

Combining: left, right, crossing

Question 4: Buy before selling

7. DP with a budget or target [Core]

Why add a second index?

Bases depend on what the state promises

Question 5: Minimum time to reach a score

Question 6: Equal teams — add the missing constraint

8. Ending here versus best so far [Core]

Question 7: Make it contiguous

9. Interval DP and two-string DP [Second pass]

Matrix chain: choose the final split

Two strings: two independent prefix lengths

Question 8: Cost, bases, and order

10. DP on trees: condition on the root [Core]

Question 9: A tiny tree

11. Breadth check: recognize these before Tuesday [Second pass]

12. Closed-note mixed check

Question 10: Four quick checks

Question 11: Design without a supplied state

Question 12: Find the bug

13. What to do with your results

Source map