Dynamic Programming Homework
In this assignment you will use the provided code template to implement solutions to each given problem. The solutions you submit must follow the guidelines provided in this document as well as any given in code.
Your solutions must implement non-recursive, bottom-up dynamic programming approaches to each given problem.
Restrictions
• You must complete this assignment on your own; do not share your code with anyone and do not look at or copy code from the Internet.
• You may not share test cases or test suites with your peers. Any testing must be your own, for your own use.
• Template code is provided and must be used.
– Note: The templates are refreshed each semester. Be sure to use the current version. • Your code must be compatible with Python 3.10.
• The provided container classes and their public methods are the only allowed means for retrieving,
storing, and modifying data for solving each given problem.
– Use of built-in functions (e.g., map, zip, sorted) and raw container types (e.g., dict, set, list)
to do so is strictly prohibited.
• Accessing private members and methods (denoted by a _ prefix) of the provided container classes is
strictly prohibited.
• Do not add, change, or remove imports in the code file used for submission. • Do not modify the function name, definition, or any of the provided utilities.
For each problem, one or more base test cases are provided. A properly implemented solution will pass any provided base test cases, but their trivial nature is not intended to ensure the overall correctness of your algorithm.
These are the same test cases that will be used to provide assurance that your submitted solutions run using the autograder. We do not release any other test cases.
In problem instances where more than one solution is optimal, any optimal solution will be considered correct, assuming that is the solution your algorithm produces.
The test cases can – and should! – be expanded while developing your solutions.
You can run your test cases by issuing the python3 -m unittest command from the directory containing your solution files.
Submission
Submit only – and all of – your solution files (i.e., cs6515_[problem_name].py) to the Gradescope assignment on or before the posted due date. Do not submit a zip file or any other files except those matching the naming convention defined.
You may submit your solutions as many times as desired and the most recent submission is what will be graded. Execution of your code may take up to 60 minutes. If not completed before the due date, your previous submission will be used.
Faster and correct solutions are worth more credit.
After your submission completes execution, you will see a score of – / 10 listed until grading is completed.
Generally Accepted Algorithm Practices
While using most built-in convenience features of Python is prohibited, the following examples are considered allowed, sensible use.
• Using local variables to hold default, intermediate, or single-result data.
• Using public methods of any provided standard library types, such as Decimal.
• Using raw containers to initialize given containers or facilitate use of approved built-in methods. • Using len() to determine the length of your input(s).
• Using match to simplify chained conditional checks.
• Using max() and min() to perform a value comparison between 2 or more items. May use key=. • Using range() as part of a loop construct.
• Using round() to round values, if a given problem calls for it.
Example Solution: Fibonacci
def Fib2(n: int) -> int: F = Table()
for i in range(2, n + 1):
F[i] = F[i – 1] + F[i – 2]
return F[n]
Example Solution: Table for Two
def TableForTwo(S: Sequence[int]) -> tuple[int, MutableSequence[int]]: n = len(S)
T = Table()
for i in range(0, n): T[0, i] = 0
T[i, 0] = 0
for i in range(1, n + 1): for j in range(1, i):
T[i, j] = S[i] – S[j]
result = MutableSequence[int]()
for i in range(0, n): result.append(T[i, max(0, i – 1)])
return T.max(), result
Cursed Chests
Famous Carribean pirate Captain Brittus is in front of the lost treasure of Conqueror Diego Velazquez. The treasure consists of a row of n chests, each with an amount of golden coins. BUT, some chests carry an ancient curse.
Luckily, Brittus has a map Diego himself left with the amount of gold in each chest, the locations of the cursed chests, and a way to get rid of them: you must pair each cursed chest with exactly one of its neighbors, making both disappear, along with their gold.
Once Brittus gets rid of all the cursed chests, he can keep all the gold in the remaining chests. Help the pirate figure out the maximum amount of gold he can get!
You are given a sequence of chests G of length n, where the entry G[i] represents a non-negative amount of gold inside the ith chest. If G[i] = 0, then it is a cursed chest.
Example: G = [2, 1, 0, 3, 5], then the maximum gold you can get is 10. Because the third chest is cursed, you optimally vanquish the chest to its left and keep the remaining ones.
Develop an efficient dynamic programming algorithm to return the maximum amount of gold in the chests that remain after all cursed chests have been vanquished along with the positions of the remaining chests.
• It is always possible to remove every cursed chest.
Implement your algorithm for solving this problem in cs6515_cursed_chests.py.
CS Help, Email: tutorcs@163.com
MutableSequence Method Examples
# Using __init__
M = MutableSequence[int]([3, 4, 5]) print(M[1]) # Prints ‘3’
M1 = MutableSequence[int]([3, 4, 5])
M2 = MutableSequence[int]([3, 4, 5])
M3 = MutableSequence[int]([3, 4, 5, 6])
# Using __eq__
print(M1 == M2) # Prints ‘True’ print(M1 == M3) # Prints ‘False’
__setitem__
M = MutableSequence[int]([1]) # Using __setitem__
print(M[1]) # Prints ‘2’
M = MutableSequence[int]([3, 4, 5]) # Using append
M.append(6)
print(M[4]) # Prints ‘6’
程序代写 CS代考 加QQ: 749389476
Sequence Method Examples
# Using __init__
S = Sequence[int]([3, 4, 5]) print(S[1]) # Prints ‘3’
S = Sequence[int]([1, 1, 1]) # Using __len__
print(len(S)) # Prints ‘3’ copy
S1 = Sequence[int]([3, 4, 5]) # Using copy
S2 = S1.copy()
print(S1[1] == S2[1]) # Prints ‘True’
S = Sequence[int]([3, 4, 5]) # Using reverse
S.reverse()
print(S[1]) # Prints ‘5’
Table Method Examples
__setitem__
T = Table()
# Using __setitem__
T[0] = True
print(T[0]) # Prints ‘True’
all [Inherited]
T = Table()
T[0] = True
# Using all
print(T.all()) # Prints ‘True’
T[1] = False
print(T.all()) # Prints ‘False’
any [Inherited]
T = Table()
T[0] = False
# Using any
print(T.any()) # Prints ‘False’
T[1] = True
print(T.any()) # Prints ‘True’
max [Inherited]
T = Table()
# Using max
print(T.max()) # Prints ‘3’
Code Help
Table Method Examples (Continued)
min [Inherited]
T = Table()
# Using min
print(T.min()) # Prints ‘1’
sum [Inherited]
T = Table()
# Using sum
print(T.sum()) # Prints ‘6’