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?