Homework 7
1 Longest Common Subsequence (50’)
Finish the LCS problem on https://www.educoder.net/classrooms/9025/shixun_homework.
2 Genetic Algorithm (50’)
Use genetic algorithm to find x
∗
that
x
∗ = arg min
x
x · sin(x)
x ∈ (−1, 15)
Use 16-bit binary digits to represent the chromosome of an individual.
• Implement your code in a .cpp file. Print the individual x with the best fitness score in each
generation.
• Describe the implementation details, such as the stopping criterion, the selection method, the
crossover method, the mutation method and so on, in a README file.
Hint: x
∗ = arg minx x · sin(x) ≈ 11.0857
3 Bonus (Voluntary) (50’)
Answer the question 15-5 (a) in book Introduction to Algorithm (3rd Edition), chapter 15.
Write down the dynamic progamming pseudo-code.
4 Due
1. Due is Nov. 15th, 23:59.
2. Pack a ZIP file for Q2 (and Q3, if finished), and submit it on the canvas.
1
