Write a function lis(L)
which takes as input a list of integers L
and outputs the length of the longest increasing subsequence (lis) of L
. A subsequence of L
is a sublist of L
that does not have to be contiguous. For example, [1,5,9]
is a subsequence of the list L = [1,2,3,4,5,6,7,8,9]
since 1,5,9
appear in the list L
in the same order (though just not in a row). 9,5,1
is not a subsequence of L
since it does not appear in L
in that order.
First implement lis
using plain recursion.
Implement a faster version of lis
using memoization.
Write the function lcs(s1, s2)
which takes as an input two strings and outputs the length of the longest common substring between the two. A subsequence of strings
is a set of letters that does not have to be contiguous. For example, the longest common subsequence of 'apple'
and 'pimple'
is 'pple'
, so the function would return 4
.
Imagine you are a mechanical engineer working for the search and rescue team in Addis Ababa. You are are in charge of building Mini-Tron, a robot that will navigate its way around a minefield. You want to make sure that Mini-Tron is as fast and agile as possible. Thus, your goal is to minimize the total weight of the robot. You are given a collection of robotic parts, each part belongs to one of n different categories. Your robot must be built from one part from each category.
For instance, you can have 4 categories: wheels, batteries, processing unit, distance sensors. Thus your robot must contain 4 parts: a set of wheels, one battery, one processing unit, and one distance sensor.
You are also given the weight and cost of each part. The parts are given as an array of $n$ lists. Each list will contain the parts of the category, represented as a tuple (cost, weight).
For example, for a problem with 4 categories and 10 total parts (2 parts in the first category, 3 parts in the second category, 3 parts in the third category, and 2 parts in the fourth category), your input $p$ can look like this:
[[(5, 4), (3, 8)],
[(1, 10), (9, 1), (7, 5)],
[(5, 12), (10, 7), (12, 5)],
[(20, 2), (12, 6)]]
And lastly, you have a total of $s$ birr to spend on the robot.
Write a function that take as input three arguments: $n$ the number of categories, $p$ the list of parts, and $s$ the budget in birr, and outputs the minimum possible weight of the robot. If there is no solution, return -1.
For the above input and a budget of $30$ birr, your function should return $25$.
First write a brute force solution robot_building_bf(p,s)
that takes a list $p$ and a budget (integer) $s$. Hint: you should use recursion.
def robot_building(p, s):
pass
Test your brute force solution on the following test cases before moving on to Part 1.2.
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!")
#TEST_CASE
def test_small(function):
def test_1():
p = [[(5, 4), (3, 8)],
[(1, 10), (9, 1), (7, 5)],
[(5, 12), (10, 7), (12, 5)],
[(20, 2), (12, 6)]]
check(function(p, 30), 25)
def test_2():
p = [[(5, 4), (3, 8)],
[(1, 10), (9, 1), (7, 5)]]
check(function(p, 15), 5)
def test_3():
p = [[(5, 4), (3, 8)],
[(1, 10), (9, 1), (7, 5)],
[(5, 12), (10, 7), (12, 5)],
[(20, 2), (12, 6)]]
check(function(p, 10), -1)
test_1()
test_2()
test_3()
test_small(robot_building)
Now, you should write a memoized solution.
def robot_building_mem(p, s):
pass
test_small(robot_building_mem)
def test_long():
objects = [[(19, 6), (17, 17), (13, 8)], [(14, 9), (3, 12), (9, 4)], [(9, 16), (14, 6), (18, 2)], [(3, 11), (8, 17), (13, 11), (12, 7), (17, 12), (10, 10)], [(3, 11), (2, 12), (16, 17), (15, 13), (13, 18)], [(17, 14), (6, 8), (8, 9), (6, 18), (12, 17), (19, 7), (11, 3)], [(5, 6), (13, 4), (2, 10), (14, 12)], [(5, 10), (16, 17), (11, 20), (6, 14), (9, 15), (19, 15), (15, 10), (20, 12), (2, 18)], [(9, 2), (6, 8), (5, 14), (15, 15), (11, 7), (13, 2), (5, 16), (11, 15), (10, 17), (9, 18)], [(10, 18), (2, 15), (13, 13), (5, 20), (6, 2), (15, 11), (12, 4), (15, 12), (15, 15)], [(5, 16), (6, 10), (2, 5)], [(20, 15), (9, 9)], [(13, 18), (3, 10), (5, 6), (16, 13), (11, 7), (15, 17), (15, 17)], [(3, 6), (8, 18), (16, 8), (14, 2), (20, 6), (15, 17), (3, 16), (17, 19), (8, 10)], [(8, 6), (2, 12)], [(4, 15), (8, 5), (13, 18), (12, 20), (20, 13)], [(17, 10), (4, 7), (3, 14), (17, 20), (16, 15)], [(5, 10), (12, 8)], [(18, 17), (7, 14), (4, 19), (10, 4), (11, 10), (9, 9), (4, 12), (14, 16), (13, 13), (19, 7)], [(14, 14), (12, 17), (16, 5), (4, 18), (2, 16), (20, 17), (9, 10)], [(6, 14), (8, 17), (6, 15), (3, 20), (9, 9), (12, 3), (13, 11), (9, 20), (18, 19)], [(16, 18), (16, 2)], [(8, 10), (9, 10), (5, 2)], [(15, 5), (10, 19), (18, 17), (20, 13), (19, 19), (19, 9), (14, 15), (15, 9), (6, 11), (5, 9)], [(10, 7), (19, 5), (16, 9), (2, 5), (11, 11), (7, 13), (9, 17), (9, 14), (10, 18)], [(3, 8), (2, 13), (12, 12), (17, 2), (13, 19), (17, 19)], [(8, 3), (5, 7), (12, 15), (11, 3)], [(6, 17), (15, 17), (18, 15), (12, 10)], [(6, 13), (13, 10), (12, 8), (18, 9), (16, 16), (17, 3)], [(10, 2), (6, 9), (14, 2), (9, 15), (5, 3), (11, 19), (12, 20)], [(4, 19), (19, 9)], [(3, 6), (7, 7), (8, 12), (3, 2), (16, 4), (4, 9), (6, 5)], [(3, 9), (8, 2), (9, 9), (8, 2), (14, 9), (9, 18)], [(18, 16), (6, 5), (11, 8), (6, 14)], [(13, 4), (11, 9), (19, 4), (9, 13), (18, 3), (20, 6), (7, 8), (14, 16)], [(5, 20), (12, 18), (15, 16), (4, 9), (4, 5), (17, 8), (7, 5), (13, 12)], [(5, 13), (4, 14), (3, 12), (9, 5)], [(11, 11), (9, 10), (10, 5), (6, 14), (10, 16), (3, 17), (17, 17)], [(17, 9), (3, 17)], [(17, 14), (17, 13), (18, 3), (10, 11), (13, 11)], [(14, 19), (8, 10), (13, 6), (8, 13)], [(3, 6), (12, 6), (12, 7), (15, 17), (5, 7), (13, 10), (7, 10), (7, 14), (16, 11), (14, 13)], [(4, 2), (15, 6), (14, 17), (17, 5), (8, 10), (13, 20), (16, 6), (3, 7)], [(16, 20), (18, 7), (7, 6)], [(2, 9), (16, 19), (8, 12), (16, 11), (5, 3)], [(11, 15), (8, 4), (15, 14), (2, 3), (4, 16), (8, 8)], [(9, 8), (15, 17), (10, 2)], [(7, 10), (18, 6), (17, 4), (4, 8), (4, 8), (6, 9)], [(8, 15), (18, 2), (6, 7), (4, 19), (16, 13), (16, 10), (9, 18), (12, 14)], [(7, 5), (2, 20), (2, 7), (18, 4), (11, 20)]]
check(robot_building_mem(objects, 317), 334)
objects2=[[(7, 13), (6, 6), (17, 10), (14, 5), (6, 11), (8, 10), (14, 10), (7, 5)], [(7, 7), (20, 18)], [(4, 17), (6, 18), (13, 11), (16, 8), (16, 12), (4, 10), (9, 9), (3, 10)], [(8, 10), (11, 11), (4, 6), (20, 18), (19, 20), (13, 19)], [(20, 7), (13, 12), (18, 10), (3, 11)], [(9, 10), (4, 11), (2, 11), (12, 18), (20, 11)], [(9, 5), (13, 2), (17, 2)], [(10, 19), (18, 4), (10, 13), (7, 7), (18, 4), (10, 18)], [(2, 10), (13, 14), (11, 2)], [(10, 4), (10, 13), (11, 9), (12, 15), (16, 18)], [(13, 10), (2, 14), (2, 5), (17, 3), (18, 19), (20, 12), (4, 15), (14, 20)], [(6, 7), (6, 11), (12, 14), (13, 14), (19, 6), (9, 9), (17, 15)], [(18, 14), (2, 15), (15, 2), (14, 18), (19, 14), (16, 7), (5, 17), (10, 3), (20, 17), (14, 11)], [(18, 9), (17, 11), (13, 5), (8, 2), (4, 2), (20, 17), (11, 15)], [(10, 11), (12, 4), (20, 5), (8, 16), (13, 4), (2, 9), (2, 20), (18, 15)], [(15, 7), (2, 2), (16, 17)], [(12, 20), (19, 9), (18, 10), (9, 4)], [(15, 6), (10, 11), (8, 6), (20, 10), (11, 20), (18, 5), (17, 12), (9, 20), (13, 4), (20, 20)], [(11, 17), (12, 18), (11, 5), (7, 6), (20, 15), (15, 9), (6, 17), (7, 10), (7, 11), (11, 19)], [(17, 15), (2, 3), (5, 10), (5, 5), (14, 9)], [(20, 3), (20, 3), (7, 5), (16, 10), (20, 13), (10, 18)], [(12, 12), (2, 12)], [(15, 8), (4, 18), (18, 2), (6, 18), (9, 16), (19, 9), (8, 18), (8, 7)], [(17, 14), (20, 4)], [(18, 13), (2, 7), (15, 11), (4, 2), (14, 4), (4, 13), (9, 15)], [(7, 3), (9, 18), (7, 14), (10, 10)], [(12, 18), (17, 16)], [(3, 15), (18, 12), (15, 15)], [(3, 17), (8, 4), (5, 19), (2, 9), (19, 18), (7, 13), (9, 5), (18, 11), (12, 4), (7, 5)], [(11, 3), (2, 15), (5, 12), (2, 4), (14, 11), (12, 13), (17, 4), (14, 8), (14, 13), (3, 10)], [(8, 9), (10, 9), (3, 13), (2, 5)], [(19, 20), (13, 20), (7, 5), (16, 12), (9, 14), (10, 16), (20, 16), (18, 10)], [(17, 15), (10, 7), (7, 17), (9, 14), (7, 17), (7, 9), (9, 4), (3, 11), (11, 16)], [(3, 20), (7, 12), (13, 18), (8, 19), (4, 16), (6, 9), (8, 10), (5, 19), (17, 11), (20, 16)], [(15, 10), (18, 18), (8, 9), (6, 12), (3, 15), (13, 18), (4, 9), (11, 14), (12, 5), (6, 4)], [(15, 18), (20, 7)], [(12, 20), (9, 8), (14, 5)], [(9, 18), (16, 18), (13, 9), (4, 4), (20, 19), (10, 8), (6, 7), (10, 6), (3, 20)], [(2, 13), (15, 12), (8, 9), (10, 6), (12, 16)], [(15, 16), (14, 10), (16, 5), (3, 5), (2, 13), (13, 8), (4, 13), (2, 4), (6, 17), (6, 5)], [(14, 16), (3, 13), (5, 18), (5, 19), (18, 4), (17, 6), (4, 6), (11, 11)], [(12, 16), (8, 13), (10, 20), (13, 20), (17, 15)], [(14, 14), (6, 12), (20, 7), (20, 11), (12, 8), (10, 17), (9, 9), (2, 6), (14, 2)], [(9, 8), (3, 16), (14, 11), (11, 16), (3, 6), (8, 6), (8, 13)], [(19, 2), (15, 12), (17, 18), (7, 4), (4, 7)], [(10, 13), (2, 11), (10, 13), (9, 12), (6, 18)], [(11, 12), (16, 6), (15, 3), (3, 19), (13, 8), (20, 6)], [(5, 5), (3, 10), (12, 12), (14, 17), (8, 11), (4, 20)], [(6, 14), (18, 3), (17, 12), (8, 9), (20, 17), (4, 14)], [(14, 4), (11, 4), (3, 20), (4, 19), (18, 17), (3, 6)], [(15, 4), (5, 7), (17, 16), (11, 12), (12, 3), (7, 15), (8, 20)], [(3, 18), (19, 12), (9, 19), (4, 10), (9, 7), (5, 9), (8, 6), (8, 3)], [(4, 11), (15, 17), (16, 4)], [(7, 8), (9, 15), (15, 9), (20, 17), (13, 15), (7, 20), (7, 3), (6, 2), (12, 4)], [(8, 6), (11, 11), (16, 7), (9, 8), (20, 17), (8, 12), (7, 5)], [(2, 5), (19, 11), (20, 12), (19, 10)], [(15, 20), (20, 9), (7, 14), (19, 11), (9, 13), (4, 15), (2, 19), (14, 8), (12, 6), (20, 16)], [(18, 4), (4, 16), (6, 11), (17, 16), (17, 6), (4, 3), (19, 8), (10, 11), (2, 16)], [(7, 6), (19, 15), (17, 11), (4, 11)], [(20, 6), (6, 10), (14, 20), (16, 16), (7, 4), (10, 15), (16, 10)], [(15, 10), (2, 5), (20, 17), (6, 13), (17, 3), (13, 12)], [(3, 4), (14, 20), (17, 7), (6, 3), (3, 2), (13, 17), (6, 18)], [(14, 6), (7, 15), (13, 2), (17, 7), (12, 3)], [(5, 12), (6, 7), (14, 4), (19, 17), (11, 11), (7, 10), (10, 5)], [(5, 11), (16, 18), (11, 3), (14, 12), (16, 3)], [(14, 15), (14, 17), (7, 3), (4, 12), (2, 20)], [(19, 8), (7, 15), (15, 4)], [(4, 16), (7, 11), (8, 20)], [(2, 3), (13, 16), (17, 16), (20, 10), (18, 10), (10, 12), (17, 5), (6, 5), (13, 11)], [(17, 6), (19, 17), (2, 5)]]
check(robot_building_mem(objects2, 560), 362)
test_long()
What is the runtime of your memoized algorithm? Explain your reasoning. Also check with a teaching assistant.
Write your solution here