Study plan: recurrences and quicksort

Block 1, about 3 hours

1. 45 min. Read Recurrences. Move the k slider on all four presets and notice which ones have constant, growing, or shrinking level totals.
2. 30 min. Watch one recurrence video. Pause before each reveal and try the next step yourself.
3. 30 min. Invent two recurrences of your own, such as \(T(n)=2T(n/3)+n\) or \(T(n)=3T(n/3)+1\), and unroll them on paper. Check with values for \(n=1,3,9\).
4. 45 min. Read Quicksort's partition. Step the partition on three arrays, predicting each move before you press Step.
5. 30 min. Watch a quicksort video, then redraw the three-region picture from memory and write the pseudocode without looking.

Block 2, about 2 hours

• 45 min. Redo your own recurrence examples cold and compare them to the pattern in the notes.
• 45 min. Design a variation of partition on paper (for example, a different pivot choice or a different direction of scan). Draw the regions, write the invariant, write the code, and trace it on a short array.
• 30 min. Review the packet and crib and anything you're unsure about.