Algorithmic Design

• Problem: word segmentation
• Step 0 (formalize): unigram model, find maximum probability segmentation
• Step 1 (devise algorithm): table-based approach (DP)
• Step 2 (correctness): follows from equation for probability
• Step 3 (time): time per cell times number of cells (O(n²))
• refine: better formal model, better data structure, worse formal model!