Name: CSPB 3104 Assignment 6/7 solved
SKU: 41618
Price: 30.00 USD
Availability: InStock

Description

5/5 - (1 vote)

Question 1: Dynamic Programmer Jane’s Progress

Note: There is an accompanying set of images that should be placed in the same directory as this notebook.

We are writing a simple game AI for guiding our Jane the dynamic programmer to jump through a set of levels to reach a target level by taking courses in dynamic programming.

The levels positions are numbered 1, … , n. The character starts at level 1 and the goal is to reach level n (where she becomes a d.p. ninja) and thus aces CSCI 3104. After taking a course, she can choose to move up by 1, 4, 5 or 11 levels forward at each step. No backward jumps are available.

Jane_Programmer At Start of Game

Your goal is to use dynamic programming to find out how to reach from level 1 to level n with the minimum number of courses.

1(A) Write a recurrence.

Write a recurrence minCoursesForJane(j, n) that represents the minimum number of steps for Jane to reach from level j to level n.

def minCoursesForJane(j, n):
    # Must return a number 
    return 0 # edit the function but do not change its name

## Test Code: Do not edit
print(minCoursesForJane(1, 9)) # should be 2
print(minCoursesForJane(1, 13)) # should be 2
print(minCoursesForJane(1, 19)) # should be 4
print(minCoursesForJane(1, 34)) # should be 3
print(minCoursesForJane(1, 43)) # should be 5

1(B) Memoize the Recurrence.

Assume that n is fixed. The memo table $T [0], \dots, T [n]$ should store the value of minCoursesForJane(j, n).

def minCoursesForJane_Memoize(n): # Assume that j = 1 is always the starting point.
    # must return a number
    # answer must coincide with recursive version
    return 10 # EDIT

## Test Code: Do not edit
print(minCoursesForJane_Memoize(9)) # should be 2
print(minCoursesForJane_Memoize(13)) # should be 2
print(minCoursesForJane_Memoize(19)) # should be 4
print(minCoursesForJane_Memoize(34)) # should be 3
print(minCoursesForJane_Memoize(43)) # should be 5

1(C) Recover the Solution

Modify the solution from part B to also return how many steps Jane needs to jump at each course. Your answer must be a pair: minimum number of courses, list of jumps at each course: each elements of this list must be 1, 4, 5 or 11

def minCoursesForJane_Solution(n): # Assume that j = 1 is always the starting point
   # must return a pair of number, list
   # number returned is the same as minCoursesForJane_Memoize
   # list must be a list of jumps consisting of elements [1,4, 5, 11]
   return 200, [1, 11, 5, 11, 5, 5, 5, 4] # EDIT

## Test Code: Do not edit
print(minCoursesForJane_Solution(9)) # should be 2, [4, 4]
print(minCoursesForJane_Solution(13)) # should be 2, [1, 11]
print(minCoursesForJane_Solution(19)) # should be 4, [1, 1, 5, 11]
print(minCoursesForJane_Solution(34)) # should be 3, [11, 11, 11]
print(minCoursesForJane_Solution(43)) # should be 5, [4, 5, 11, 11, 11]

(200, [1, 11, 5, 11, 5, 5, 5, 4])
(200, [1, 11, 5, 11, 5, 5, 5, 4])
(200, [1, 11, 5, 11, 5, 5, 5, 4])
(200, [1, 11, 5, 11, 5, 5, 5, 4])
(200, [1, 11, 5, 11, 5, 5, 5, 4])

1(D) Greedy Solution

Suppose Jane tried a greedy strategy that works as follows. Initialize number of courses $c = 0$ .

While $n \geq 11$ , 1.1 jump $11$ steps forward, and set $n = n - 11$ , $c = c + 1$
While $n \geq 5$ , 2.1 jump $5$ steps forward and set $n = n - 5$ , $c = c + 1$
While $n \geq 4$ , 3.1 jump $4$ steps forward and set $n = n - 4$ , $c = c + 1$
Finally, while $n > 1$ , 4.1 jump $1$ step forward and set $n = n - 1$ , $c = c + 1$

This way, she can reach level $n$ starting from level $1$ using $c$ courses.

Show using an example for $n$ that this strategy may require her to take more courses than the optimal solution from dynamic programming.

Answer (Expected Length 3 lines)

Your answer here

Question 2: The Defeat of Kilokahn

Unfortunately, life was not as simple as it seemed in problem 1. Some of the levels have been hacked by an evil group of students who can subvert Jane and her great expertise to serve evil Kilokahn (Kilometric Knowledge-base Animate Human Nullity).

Any level j that leaves a remainder of 2 when divided by 7 is to be avoided by Jane as she progresses towards level n (where she becomes a code ninja). However, Kilokahn will not be at level $n$ even if $n \mod 7 = 2$ .

Jane_Programmer At Start of Game with Kilokahn lurking

2(A) Write a recurrence.

Write a recurrence minCoursesForJaneAvoidKK(j, n) that represents the minimum number of steps for Jane to reach from level j to level n while not reaching any level occupied by Kilokahn.

def minCoursesForJaneAvoidKK(j, n):
    return 100

## Test Code: Do not edit
print(minCoursesForJaneAvoidKK(1, 9)) # should be 2
print(minCoursesForJaneAvoidKK(1, 13)) # should be 2
print(minCoursesForJaneAvoidKK(1, 19)) # should be 4
print(minCoursesForJaneAvoidKK(1, 34)) # should be 5
print(minCoursesForJaneAvoidKK(1, 43)) # should be 5
print(minCoursesForJaneAvoidKK(1, 55)) # should be 6

2(B) Memoize the recurrence in 2(A)

def minCoursesForJaneAvoidKK_Memoize(n): # j is assumed to be 1 
    return 100

## Test Code: Do not edit
print(minCoursesForJaneAvoidKK_Memoize(9)) # should be 2
print(minCoursesForJaneAvoidKK_Memoize(13)) # should be 2
print(minCoursesForJaneAvoidKK_Memoize(19)) # should be 4
print(minCoursesForJaneAvoidKK_Memoize(34)) # should be 5
print(minCoursesForJaneAvoidKK_Memoize(43)) # should be 5
print(minCoursesForJaneAvoidKK_Memoize(55)) # should be 6
print(minCoursesForJaneAvoidKK_Memoize(69)) # should be 8
print(minCoursesForJaneAvoidKK_Memoize(812)) # should be 83

2(C) Recover the solution in terms of number of jumps for each course.

def minCoursesForJaneAvoidKK_Solution(n):
    return 100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5]

## Test Code: Do not edit
print(minCoursesForJaneAvoidKK_Solution(9)) # should be 2, [4, 4]
print(minCoursesForJaneAvoidKK_Solution(13)) # should be 2, [11, 1]
print(minCoursesForJaneAvoidKK_Solution(19)) # should be 4, [4, 5, 4, 5]
print(minCoursesForJaneAvoidKK_Solution(34)) # should be 5, [5, 1, 11, 11, 5]
print(minCoursesForJaneAvoidKK_Solution(43)) # should be 5, [4, 5, 11, 11, 11]
print(minCoursesForJaneAvoidKK_Solution(55)) # should be 6, [5, 11, 11, 11, 11, 5]
print(minCoursesForJaneAvoidKK_Solution(69)) # should be 8, [11, 1, 11, 11, 11, 11, 11, 1]
print(minCoursesForJaneAvoidKK_Solution(812)) # should be 83, [5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11, 11, 11, 5, 11, 11]

(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])
(100, [1, 4, 5, 11, 5, 4, 1, 11, 4, 5])

Question 3: Energize Jane with a budget.

Unfortunately, life was not as simple as it seemed in problem 2. Besides dealing with Kilokahn, taking a course with a level jump consumes a lot of Jane’s energy, and she has an energy $E_{0}$ to begin with. Each time Jane jumps levels, she loses energy as follows:

Jump	Energy Consumed
1	1
4	2
5	3
11	7

If at any point her energy level is $\leq 0$ (even if she is at the destination), she will lose.

Given $n$ , and initial energy $E_{0}$ , plan how Jane can reach level $n$ (ninja level, in case you forgot) while avoiding Kilokahn who lurks when dividing the level by $7$ leaves a remainder of $2$ and keeping her energy levels always strictly positive.

3(A): Write a Recurrence

Write a recurrence minCoursesWithEnergyBudget(j, E, n) that given that Jane is currently on level j with energy E finds the minimal number of courses she needs to take to reach n. Do not forget the base cases.

def minCoursesWithEnergyBudget(j, e, n):
    return 121

# test code do not edit
print(minCoursesWithEnergyBudget(1, 25, 10)) # must be 2
print(minCoursesWithEnergyBudget(1, 25, 6)) # must be 1
print(minCoursesWithEnergyBudget(1, 25, 30)) # must be 5
print(minCoursesWithEnergyBudget(1, 16, 30)) # must be 7
print(minCoursesWithEnergyBudget(1, 18, 31)) # must be 7
print(minCoursesWithEnergyBudget(1, 22, 38)) # must be 7
print(minCoursesWithEnergyBudget(1, 32, 55)) # must be 11
print(minCoursesWithEnergyBudget(1, 35, 60)) # must be 12

3(B): Memoize the Recurrence

Write a memo table to memoize the recurrence. Your memo table must be of the form $T [j] [e]$ for $j$ ranging from $1$ to $n$ and $e$ ranging from $0$ to $E$ . You will have to handle the base cases carefully.

def minCoursesWithEnergyBudget_Memoize(E, n): # j is assumed 1 and omitted as an argument.
    return 121

# test code do not edit
print(minCoursesWithEnergyBudget_Memoize(25, 10)) # must be 2
print(minCoursesWithEnergyBudget_Memoize(25, 6)) # must be 1
print(minCoursesWithEnergyBudget_Memoize(25, 30)) # must be 5
print(minCoursesWithEnergyBudget_Memoize(16, 30)) # must be 7
print(minCoursesWithEnergyBudget_Memoize(18, 31)) # must be 7
print(minCoursesWithEnergyBudget_Memoize(22, 38)) # must be 7
print(minCoursesWithEnergyBudget_Memoize(32, 55)) # must be 11
print(minCoursesWithEnergyBudget_Memoize(35, 60)) # must be 12

3(C): Recover the Solution

Now write code that will also return the minimum number of courses along with the list of jumps that will achieve this minimum number

def minCoursesWithEnergyBudget_Solution(E, n): # j is assumed 1 and omitted as an argument.
    return 100, [11, 5, 4, 11, 1, 4, 11, 4, 5]

# test code do not edit
print(minCoursesWithEnergyBudget_Solution(25, 10)) # must be 2, [4,5]
print(minCoursesWithEnergyBudget_Solution(25, 6)) # must be 1, [5]
print(minCoursesWithEnergyBudget_Solution(25, 30)) # must be 5, [4, 5, 4, 5, 11]
print(minCoursesWithEnergyBudget_Solution(16, 30)) # must be 7, [4, 5, 4, 4, 4, 4, 4]
print(minCoursesWithEnergyBudget_Solution(18, 31)) # must be 7, [4, 5, 4, 4, 4, 4, 5]
print(minCoursesWithEnergyBudget_Solution(22, 38)) # must be 7,  [4, 5, 4, 4, 4, 5, 11]
print(minCoursesWithEnergyBudget_Solution(32, 55)) # must be 11, [4, 5, 4, 4, 4, 4, 5, 4, 4, 11, 5]
print(minCoursesWithEnergyBudget_Solution(35, 60)) # must be 12, [4, 5, 4, 4, 4, 4, 5, 4, 4, 11, 5, 5]

(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])
(100, [11, 5, 4, 11, 1, 4, 11, 4, 5])

Question 4: Subset Sum Problem

We are given a set of whole numbers $S : {n_{1}, \dots, n_{k}}$ and a number $N$ . Our goal is to choose a subset of numbers $T : {n_{i_{1}}, \dots, n_{i_{j}}} \subseteq S$ such that

(a) $\sum_{l = 1}^{j} n_{i_{l}} \leq N$ , the sum of chosen numbers is less than or equal to $N$ ,

(b) The difference $N - \sum_{l = 1}^{j} n_{i_{l}}$ is made as small as possible.

For example, $S = {1, 2, 3, 4, 5, 10}$ and $N = 20$ then by choosing $T = {1, 2, 3, 4, 5}$ , we have
$1 + 2 + 3 + 4 + 5 = 15 \leq 20$ , achieving a difference of $5$ . However, if we chose $T = {2, 3, 5, 10}$ we obtain a sum of $2 + 3 + 5 + 10 = 20$ achieving the smallest possible difference of $0$ .

Therefore the problem is as follows:

Inputs: list $S : [n_{1}, \dots, n_{k}]$ and number $N$ .
Output: a list $T$ of elements from $S$ such that sum of elements of $T$ is $\leq N$ and $N - \sum_{e \in T} e$ is the smallest possible.

The subsequent parts to this problem ask you to derive a dynamic programming solution to this problem.

Note: Because $S$ and $T$ are viewed as sets, each element in the set may occur exactly once.

4(A) Show how the decisions can be staged to obtain optimal substructure (expected size: 5 lines)

__Your answer here __

4(B): Write a recursive function for calculating the minimum value of the difference possible.

def minSubsetDifference_recursive(N, s_list): 
    return 129

# Code for testing your solution
# DO NOT EDIT
print(minSubsetDifference_recursive(15, [1, 2, 3, 4, 5, 10])) # Should be zero
print(minSubsetDifference_recursive(26, [1, 2, 3, 4, 5, 10])) # should be 1
print(minSubsetDifference_recursive(23, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_recursive(18, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_recursive(9, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_recursive(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1
print(minSubsetDifference_recursive(512, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 0
print(minSubsetDifference_recursive(616, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1

4(C): Memoize the recurrence above.

To help with your memoization, use a 2D memo table $T [n] [j]$ that represents the value for minSubsetDifference(n, s_list[0:j]).

def minSubsetDifference_Memoize(N, s_list):
    return 129

# Code for testing your solution
# DO NOT EDIT
print(minSubsetDifference_Memoize(15, [1, 2, 3, 4, 5, 10])) # Should be 0
print(minSubsetDifference_Memoize(26, [1, 2, 3, 4, 5, 10])) # should be 1
print(minSubsetDifference_Memoize(23, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_Memoize(18, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_Memoize(9, [1, 2, 3, 4, 5, 10])) # should be 0
print(minSubsetDifference_Memoize(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1
print(minSubsetDifference_Memoize(512, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 0
print(minSubsetDifference_Memoize(616, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1

4(D): Write code to recover the solution

def minSubsetDifference(N, s_list):
    return 121, [1, 4, 6, 2, 1]

# Code for testing your solution
# DO NOT EDIT
print(minSubsetDifference(15, [1, 2, 3, 4, 5, 10])) # Should be 0, [5, 4, 3, 2, 1]
print(minSubsetDifference(26, [1, 2, 3, 4, 5, 10])) # should be 1, [10, 5, 4, 3, 2, 1]
print(minSubsetDifference(23, [1, 2, 3, 4, 5, 10])) # should be 0, [10, 5, 4, 3, 1]
print(minSubsetDifference(18, [1, 2, 3, 4, 5, 10])) # should be 0, [10, 4, 3, 1]
print(minSubsetDifference(9, [1, 2, 3, 4, 5, 10])) # should be 0, [4, 3, 2]
print(minSubsetDifference(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1, [339, 94, 23]
print(minSubsetDifference(512, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 0, [312, 152, 37, 11]
print(minSubsetDifference(616, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1, [413, 94, 48, 37]

(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])
(121, [1, 4, 6, 2, 1])

4 (E): Greedy Solution

Suppose we use the following greedy solution to solve the problem.

$T = \emptyset$
While ( N≥0)
- Select the largest element $e$ for $S$ that is smaller than $N$
- Remove $e$ from $S$
- Add $e$ to $T$
- N = N – e
return (N, T)

Using an example, show that the greedy algorithm does not necessarily produce the optimal solution.

Answer (4 lines)