CS/ECE 374 A (Spring 2022) Homework 6 (due March 10 Thursday at 10am)
Instructions: As in previous homeworks.
Note: In any dynamic programming solution, you should follow the steps below (if we explicitly
state that pseudocode is not required, then step 4 may be skipped):
Copyright By PowCoder代写 加微信 powcoder
1. first give a clear, precise definition of the subproblems (i.e., what the recursive function is intended to compute);
2. then derive a recursive formula to solve the subproblems (including base cases), with justifi- cation or proof of correctness if the formula is not obvious;
3. specify a valid evaluation order;
4. give pseudocode to evaluate your recursive formula bottom-up (with loops instead of recur- sion); and
5. analyze the running time.
Do not jump to pseudocode immediately. Never skip step 1!
Problem 6.1: For a sequence ⟨b1,…,bm⟩, an alternation is an index i ∈ {2,…,m−1} such that
(bi−1