Given a list of positive integers, find if it is possible to partition the list into two subsets with equal sum. For example, given the list L = [3,1,1,2,2,1] we can partition L into two partitions each having sum 5. L1 = [1,1,1,2] and L2 = [2,3]. Note that this solution is not unique. Another solution would be L1 = [3,1,1] and L2 = [2,2,1].
def check(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
Given the L = [ 3, 5, 2, 1, 1 ] is it possible to partition it to two sets with the same sum? If yes, write down what the two lists would be.
Write your answer here:
Given the L = [ 3, 5, 2, 1, 1, 2 ] is it possible to partition it to two sets with the same sum? If yes, write down what the two lists would be.
Write your answer here:
If the sum of the list is odd, is it possible to partition it in to two lists? Write down a function called sum_L that sums the integers in the list. And determine if the sum returned from the function sum_L is even or odd.
# Write your answer here.
def sum_L(L):
pass
def is_even(n):
pass
# test case 1
L = [-4, 8, 7, 5, 3, 2, 1, 9, 5, 6, 6, 1000]
check(sum_L(L), sum(L))
Function should return the value 1048, it is returning the value None
L = [-5, -3, -1, 0, 0, 0]
check(sum_L(L), sum(L))
# test case 3: The is_even function would be tested for all of the values
# in list_n
list_n = [0, 2, 5, 199990902, 1, -1]
for i in list_n:
print("testing is_even({i}) ".format(i=i))
check(is_even(i), not(bool(i%2)))
testing is_even(0) Function should return the value True, it is returning the value None testing is_even(2) Function should return the value True, it is returning the value None testing is_even(5) Function should return the value False, it is returning the value None testing is_even(199990902) Function should return the value True, it is returning the value None testing is_even(1) Function should return the value False, it is returning the value None testing is_even(-1) Function should return the value False, it is returning the value None
In today's lab, implement a function called partition
which returns True
if it is possible to partition the list L
into two lists with equal sum.
def partition(L):
# Write your code here. Hint: you may need to create new functions.
pass
# test-case 1
L = [3,1,1,2,2,1]
check(partition(L), True)
L = [3,3,3,3,3,1,1]
check(partition(L), False)
Function should return the value True, it is returning the value None Function should return the value False, it is returning the value None
Think how you could use memoization to improve the running time of the algorithm and write down a function partition_memo
which contains a memoized version of the above solution.
# Write the memoized version of the previous solution here.
def partition_memo(L):
pass
# test-case 2
L = [3,1,1,2,2,1,2,3,2,1,100,123,3,1,32,1,23,1,23,12,321,32,123,213,1,1]
check(partition_memo(L),True)
L = [3,1,1,2,2,1]
check(partition_memo(L)(L), True)
L = [500, 500, 10, 15, 1000, 5]
check(partition_memo(L)(L), True)
L = [200, 200, 200, 200, 200, 200, 200, 200, 200, 200]
check(partition_memo(L)(L), True)
L = [4,21,3,100,2,30,1000,20,200,1]
check(partition_memo(L)(L), False)
Alright, so now that you've built Mini-Tron, time to begin navigation. Mini-Tron needs to go down a staircase in order to get out of the building that it was constructed in. The staircase has $n$ number of steps. Unfortunately, Mini-Tron cannot fly and it needs to go down the steps in the old boring way: using its artificial legs.
Minitron can only hop 1 step, 2 steps or 3 steps at a time. Our goal is to figure out how many possible ways there are for the robot to go down $n$ number of steps. We will implement a function countWays(n)
that take as input the number $n$ of steps in the staircase and returns the number of ways for Mini-Tron to descend the step.
countWays(1)
=> 1. For a staircase with 1 step, you can only go down the staircase in one way: hopping 1 step.countWays(2)
=> 2. For a staircase with 2 steps, either one double hop or two single hops are possible )countWays(3)
=> 4. For a staircase with 3 steps, there are 4 possible ways to go down:Assume that you have the countWays function propely implemented. What would be the output of the function for the following inputs? NOTE: You don't have to write code for this problem.
# Write your answer here
# Write your answer here
Write a recursive function countWays(n) that takes the number of steps n in the staircase and returns the number of possible ways for the robot to go down n number of steps.
def countWays(n):
pass
# Write your answer below
Run the four cells below.
def check(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
# Run test case 1
check(countWays(6),24)
Function should return the value 24, it is returning the value None
# Run test case 2
check(countWays(15),5768)
# Run test case 3
check(countWays(-1),0)
Add print("Calculating countWays of ({n})".format(n)) at the beginning of your function above, and run the cell below:
countWays(4)
Looking at the printed output above, how many times does your function calculate countWays(1)
?
# Answer here
What is the time complexity of your algorithm?
# Answer here
Now, let's try to make our function more efficient by adding memoization to it. We want to store our pre-calculated results in a list called $mem$.
$$ mem[i] = \begin{cases} -1 \text { if we haven't computed countWays(i) before } \\ countWays(i) \text { if we have already computed it} \end{cases} $$## NOTE: Don't run this cell before you complete both functions.
## Implement the wrapper function countWays_mem that creates a list called mem and passes it to count_steps_recursive
## which does most of the work.
def countWays_mem(n):
## Initialize a list called mem below here.
## call the recursive version 'count_steps_recursive' below here by passing in mem as an additional argument to n.
pass
### 3.3.2 Implement count_steps_recursive
def count_steps_recursive(n, mem):
pass
# write your recursive function here
## Run test case 1
check(countWays_mem(6),24)
## Run test case 2
check(countWays_mem(35),1132436852)
## Run test case 3
check(countWays_mem(50),10562230626642)
Add 'print("Calculating countWays of ({n})".format(n))' in your countWays_rec function right after you check if your current input has been memoized previously. Then run the cell below:
countWays_mem(10)
How many times does it calculate count_steps_recursive
with n = 1
?
# Answer here
What is the time complexity of the countWays_mem
function?
Congratulations! Mini-Tron has made it out of the building. But now it needs to navigate its way to the rescue destination. But before the robot makes an effort to get to the destination, we want to make sure it will be able to reach the destination in time. If it's not going to make it in time, why even bother right?
Given a cost matrix where the cost for each cell is the amount of time it takes to walk through the cell, we want to find out the minimum time it would take for the robot to get from point A(source) to point Z(destination).
But there are a couple of restrictions:
An example cost matrix is
inf = float('inf')
cost = [[1,2,inf],
[8,inf,2],
[3,5,1]]
Write a simple recursive function minTime(grid,x,y)
that takes in a 2d array grid
and coordinates x,y
and outputs the minimum time required to go from (0,0)
to (x,y)
in the grid.
def minTime(grid, x, y):
pass
# Write your solution here
# test minTime
inf = float('inf')
Grid = [[2,4,inf],
[1,inf,9],
[3,1,4]]
check(minTime(Grid, 2,2),8)
check(minTime(Grid, 1, 2), 15)
check(minTime(Grid, 1, 1), inf)
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
What is the time complexity of the minTime
algorithm?
Write your answer here:
Write a memoized version of minTime
function and call it minTime_mem
.
# Write your solution here (Hint: You might want to use a helper function.)
def minTime_mem(grid,x,y):
pass
# write your code here
## test minTime_mem
# test-case set 1
inf = float("inf")
Grid = [[2,4,inf],
[1,inf,9],
[3,1,4]]
check(minTime_mem(Grid, 2,2),8)
check(minTime_mem(Grid, 1, 2), 15)
check(minTime_mem(Grid, 1, 1), inf)
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
# test-case set 2
Grid = [[2,4,inf,9, 1, 3, 8, 9],
[1,inf,9,13, 12, 2, 4, 1],
[3,1,4,1, 6, 2, 2, 2 ]]
check(minTime_mem(Grid, 2,7),21)
check(minTime_mem(Grid, 0,7), inf)
check(minTime_mem(Grid, 1, 4), 40)
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
What is the time complexity of the minTime_mem
algorithm?
Write your answer here:
Now that we've found the minimum time required to get from the source cell (cell A) to the destination cell (cell B), we want to figure out the minimum or shortest path. Implement a minPath(grid, x, y)
function that returns the shortest path from cell A to cell B. You should return a list of tuples where the tuples represent the coordinates (x,y) of the path, including the origin and the destination.
Example:
Grid = [[2,4,inf],
[1,7,9],
[3,1,4]]
minPath(Grid, 2, 2)
=> [(0,0),(1,0),(2,0),(2,1),(2,2)]
NOTE: minPath(grid, x, y)
should return an empty list if there is no valid path from the origin to the destination
def minPath(grid, x, y):
pass
# Write your solution here
# test minPath
# test-case set 1
inf = float("inf")
grid = [[2,4,inf],
[1,inf,9],
[3,1,4]]
check(minPath(grid, 2, 2), [(0, 0), (1, 0), (2, 1), (2, 2)])
check(minPath(grid, 2, 1), [(0, 0), (1, 0), (2, 1)])
check(minPath(grid, 1, 1), [])
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
Now write the memoized version of the minPath
function and call it minPath_mem(grid, x, y)
.
# Write your solution here (you may want to create a helper function)
def minPath_mem(grid, x, y):
pass
# test minPath_mem
# test-case set 1
inf = float("inf")
grid = [[2,4,inf],
[1,inf,9],
[3,1,4]]
check(minPath(grid, 2, 2), [(0, 0), (1, 0), (2, 1), (2, 2)])
check(minPath(grid, 2, 1), [(0, 0), (1, 0), (2, 1)])
check(minPath(grid, 1, 1), [])
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!