Submission instruction:
Submit one single pdf file for this homework including both coding problems and analysis problems.
For coding problems, copy and paste your codes. Report your results.
For analysis problems, either type or hand-write and scan.
Question 1 (3 pt.) Order statistics: Write codes for Rand-Select (with linear expected running time) and Select (with linear worst-case running time). Test your two programs with an input array that is a random permutation of A = {1, 2, 3, …, 99, 100} (reuse of your Homework 2).
Question 2 (2pt.) Dynamic Programming of LCS: Write codes for the longest common subsequence.
