0. Read Text Segmentation (JE2 - 2.5)

1,2. https://courses.engr.illinois.edu/cs374/sp2018/A/labs/lab7.pdf Questions (2) and (3).

Also derive the recurrence relations for the algorithms and solve the recurrences.

3. JE2-3a (addition chain)

The first two numbers must be 1 and 2. The (k+1)-th number can be the sum of any pair from {x0 ... xk}. Select any possible candidate for that number and recursively search for a solution with that partial chain.

(a) Design a backtracking algorithm for to determine the length of the shortest addition chain.

// return: length of the smallest addition chain for n by extending X
def Solve(X): 
// X : current chain which has to be extended
// target n is can be treat as a global variable or a parameter that does not change

    FILL

To solve the problem, call Solve([1]).


(b) Discuss the time complexity of the above algorithm.

T(k): What should this be?