analysis of algorithm

CS5200 Homework – 2 (Deadline: 10-06-2023 11:59pm)

Instructor: Huiyuan Yang

q Theory questions [60%] :

Q1.[10%] Given an unordered list, show the corresponding heap after each step.

§ Build a Max-Heap by calling Max-Heapify() algorithm [3%] § Delete the maximum item; [2%] § Insert an item with value of 80; [2%] § Show the heap after 30 is sorted when performing heapsort.[3%]

Q2. [10%] Given a Binary Search Tree,

§ Print out all the keys in the BST in Pre-order, In-order and Post-order; [6%] § Show the BST after performing insert(13), insert(40) and delete(35) respectively; [4%]

Q3: [10%] Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is:

§ Print the corresponding m-table, s-table and an optimal parenthesization solution..

Q4.[15%] Given strings X=CACMYCCA, and Y=YMCMAMYCCMA

§ Find the longest common subsequence for the strings X and Y. Show the table with the lengths and arrows (“← ", " ↑ ", " ↖ ") [10%]

§ Find the longest contiguous subsequence. Show the table with the lengths. [5%]

Q5. [15%] Constructing the optimal binary tree, given

§ Show the dynamic programming tables, optimal binary tree and expected search cost.

q Programming [35%] Dynamic programming solution for LCS. § [35%] Given two strings, find the length of the longest subsequence present in both of them. For

example: o LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. o LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

§ [Extra 10%] Given two strings, find the length of the longest contiguous subsequence present in

both of them. For example: o LCS for input Sequences “ABCDEEF” and “AEDEEF” is “DEEF” of length 4.

q Bonus: [Extra 10%]

Design a dynamic programming algorithm to solve the sum of subsets problem:

Problem statement: There are n positive integers 𝐴 = [𝑎!, 𝑎", … , 𝑎#] and a positive integer sum 𝑆. Is there a subset of A such that the sum of the integers in the subset is 𝑆. If there is such a subset, the output of the program is true, otherwise it is false.

Example:

§ 𝐴 = [3, 5, 11] 𝑎𝑛𝑑 𝑆 = 16. In this case the output is true since 5 + 11 = 16 § 𝐴 = [3, 5, 11] 𝑎𝑛𝑑 𝑆 = 18. In this case the output is false since 𝑡ℎ𝑒𝑟𝑒 𝑖𝑠 𝑛𝑜 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛. § 𝐴 = [3, 5, 11,15, 22, ] 𝑎𝑛𝑑 𝑆 = 30. In this case the output is true since 3 + 5 + 22 = 30

This problem can be solved with dynamic programming.

1) Define the optimal substructure, and write the recurrence for the solution. [5%] 2) Write pseudo code, and apply dynamic programming to the following problem: 𝐴 =

[1, 2, 4] 𝑎𝑛𝑑 𝑆 = 6. Show your dynamic programming table. [5%]

q Submission requirements: [5%]

Put the theory part and code into a folder with the name: [YourStudentID-YourName-HW*].zip

§ Following all the submission requirements [5%] § Theory part:

o You solution should be clear, concise but also contain enough details. o Only PDF format is allowed. o Please make sure the scanned PDF file is high-resolution and easily readable if you wrote

your solution on paper. § Programming part:

o A sanity check to test the correctness of your algorithm. o Your program will read an input file and write an output file. o Your program will be called like this: prompt>./hw* ./input.txt. ./output.txt o Your code should be complied by calling the makefile.

__MACOSX/hw2/._hw2.pdf