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.
Testing
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 abs() to get the absolute value of a number or calculation.
- 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()
F[0] = 0 F[1] = 1
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
Rules of the Game
You have been invited to participate in a new game created by Head TA Jamie. Jamie gives you a list of tasks that you may choose to attempt or skip.
- The ith task has a point value of P[i]
- The ith task has a success rate of S[i] where 0.0 <= S[i] <= 1.0
- You start with a multiplier value x and an increment value y
Starting from task 1, you may choose to attempt or skip a task. This will affect your final score.
- If you succeed, your score will be increased by the point value times the current multiplier.
- If you fail, your score will be deducted by half the point value, ignoring the multiplier.
- To add a bit of strategy to the game, every task you skip increments the multiplier by y.
- Each time you attempt a task, the multiplier is reset to x after the attempt. To play the game, you are given the following:
- A list of point values P for n tasks, with non-negative values.
- A list of success rates S for n tasks, with non-negative values.
- A non-negative x as the initial multiplier.
- A non-negative y as the multiplier increment.
Develop an efficient dynamic programming algorithm to determine the maximum expected value and which tasks you should attempt to achieve it.
Notes:
- You start with zero points.
- The list of attempted tasks must be in the same order that you received them.
Implement your algorithm for solving this problem in cs6515_rules_game.py.
Appendix
MutableSequence Method Examples
__init__
# Using __init__ M = MutableSequence[int]([3, 4, 5]) print(M[1]) # Prints ‘3’
__eq__
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__ M[1] = 2 print(M[1]) # Prints ‘2’
append
M = MutableSequence[int]([3, 4, 5])
# Using append M.append(6) print(M[4]) # Prints ‘6’
Sequence Method Examples
__init__ # Using __init__ S = Sequence[int]([3, 4, 5]) print(S[1]) # Prints ‘3’
__len__ 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’
reverse
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()
T[0] = 1
T[1] = 2
T[2] = 3
# Using max print(T.max()) # Prints ‘3’
Table Method Examples (Continued)
min [Inherited]
T = Table()
T[0] = 1
T[1] = 2
T[2] = 3
# Using min print(T.min()) # Prints ‘1’
sum [Inherited] T = Table()
T[0] = 1
T[1] = 2
T[2] = 3
# Using sum print(T.sum()) # Prints ‘6’
