Assignment 7
CSCI:381:01-Algorithms
Algorithm 算法作业 You need to submit Problems 1-6 as hardcopy and also submit the code for Problem 1, 3, 4, 5, and 6 to Blackboard.
Chapter 9: Medians and Order Statistics Algorithm 算法作业
- Write a program to implement the algorithm RANDOMIZED_SELECT(A,p,r,i) to select the ith smallest element of the array
The output of the program should look like the following.
>>> main()
RANDOMIZED_SELECT(A,p,r,i):
Find ith smallest element of an array A for i = 3 Input: [5, 4, 3, 2, 1]
Output: 3
Chapter 15: Dynamic Programming
2.Exercise1-1
3.Write a program to implement the algorithm CUT_ROD(p,n) to finds the maximum revenue for a rod of n inches using recursive top-down solution.
The output of the program should look like the following.
>>> main()
Find optimal value rn
Input: [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
4.Write a program to implement the algorithm MEMOIZED_CUT_ROD(p,n) to finds the maximum revenue for a rod of n inches using top-down with memoization.
The output of the program should look like the following. Algorithm 算法作业
>>> main()
Find optimal value rn
Input: [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
5.Write a program to implement the algorithm BOTTOM_UP_CUT_ROD(p,n) to finds the maximum revenue for a rod of n inches using bottom-up solution.
The output of the program should look like the following.
>>> main()
Find optimal value rn
Input: [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
6.Write a program to implement the algorithm PRINT_CUT_ROD_SOLUTION(p,n) to print the cuts using theEXTENDED_BOTTOM_UP_CUT_ROD(p,n). Algorithm 算法作业
The output of the program should look like the following.
>>> main()
Find optimal value rn
Input: [1, 5, 8, 9, 10, 17, 17, 20]
2
6
You need to submit Problems 1-6 as hardcopy and also submit the code for Problem 1, 3, 4, 5, and 6 to Blackboard.
Guideline for Homework Submission Algorithm 算法作业
- Zip the files of the programs and submit the zipped file to
- The first three lines in each file are
a)Write the name of the program on the first line.
b)Describe the purpose of the program on the second line.
c)Write the name of the programmer on the third line.
For example,
// Filename: assignment1.py
// Purpose: This program coverts a positive integer in base 10 to a new base.
// Programmer: R2 D2
