You will be using gitlab for submitting this assignment. We have created a
private repository for you in the CS gitlab server gitlab.cs.ucl.ac.uk; its
path is:
where is your Computer Science username (not your Moodle
one!). To create a local copy of your repository, you can use the command
git clone @gitlab.cs.ucl.ac.uk:/cs/student/engs102p/
Submission
Deadline: December 13, 23:59
Late deadline: December 20, 23:59
Solve the three exercises in this document. Create four les
author.txt exercise1.py exercise2.py exercise3.py
The le author.txt must have your UCL email address on the rst line|the
one of the form
Each exercise le must be a python 3 source le containing:
your solution for the exercise|the signature of functions and classes must
be exactly as speci ed in the text of the exercise;
pytest tests for your solution;
auxiliary functions, if needed.
Do not put your name or any personal information in the exercise les. Your
code must not:
1
Request user input from the command line, or print anything to standard
output.
Import python modules that are not part of the python 3 standard library
(https://docs.python.org/3/library/index.html).
In order to submit, simply push those les to your repository. You can push
as many times as you want. Any push beyond the late deadline will be
ignored. Moreover, the last push is the one that counts: if you submit
once before the deadline and once afterwards (before the late deadline), only
the latter one will be considered. The late submission penalty is applied
to all the exercises, even if you submit a new version of just one le after the
deadline.
Evaluation
The evaluation will be done automatically, via a battery of tests. Please make
sure that there are no syntax errors in your code before submitting. Solution
les that cannot be tested due to syntax errors or due to imports
of non-standard modules will get a 0% grade. Once your solution has
been graded, we will send a report with test results to the email address in
author.txt.
Correctness (50 points per exercise). These tests will check whether your
code does what it is supposed to do. We will test correctness of results for all
inputs (including corner cases). We will also check whether exceptions are raised
for malformed inputs.
E ciency (25 points per exercise). We will measure the execution time
of your code on large inputs|examples of what we mean by large inputs are
provided for each exercise. Then we will compare the execution times of solutions
from all students. The most e cient solutions will get full e ciency points, and
a decreasing amount of points will be given to less e cient solutions.
Two solutions are considered equally e cient if their execution
time is of the same order of magnitude. For instance, two solutions running
in 0.02 seconds and 0.05 seconds respectively will get the same amount of
points; a solution running in 0.15 seconds will get fewer points.
Testing (25 points per exercise). We will check the presence of appropriate
pytest tests and their coverage, that is the percentage of code that they actually
test. You can check the coverage for your solution by installing the python
module coverage and running the following two commands on the command
line:
coverage run -m pytest
coverage report
where is either exercise1.py, exercise2.py or exercise3.py.
2
Exercise 1
You are a thief in a treasure trove, full of valuable objects. You want to steal as
many objects as you can, but you can only carry a certain weight. This exercise
is about writing an algorithm to compute the maximum value you can steal.
Implement a function
thief(objects, max_weight)
where:
objects is a list of pairs (weight,value) giving the weight and value of
each type of object in the trove | both positive integers. For instance:
[(2,50), (3,100), (5,140)]
max weight is the maximum weight you can carry { a non-negative integer.
The function should return the maximum value you can get by stealing zero or
more instances of the input objects. For the example above:
thief([(2,50), (3,100), (5,140)], 17) = 550
which is obtained by stealing 1 object of weight 2, 5 objects of weight 3 and 0
objects of weight 5.
Large inputs. We will consider objects lists with hundreds of objects, and
values of max weight up to 104.
Hint: Solutions for this problem can be computed recursively. Suppose you can
compute the solution up to a certain weight w < max weight for a given objects
list. Then the solution for weight w+1 can be computed as the maximum of the
following values:
The solution for w | you don’t steal any more objects.
All possible values you reach by stealing one additional object. For any
object (weight,value) in objects, the corresponding value is obtained
by adding value to the solution for (w + 1) - weight (that is, the best
value you can get after \making room" for the object).
You could implement this computation in python as a recursive thief(objects,
max weight) function. However, you need to be careful because: a) it may do
useless work by recomputing the solution for the same value of w many times;
b) recursion is computationally expensive; c) python has a maximum recursion
depth. One way of making it more e cient is by storing intermediate solutions
and then re-using them when needed. An even more e cient implementation
does not use recursion at all|this requires turning the recursive computation
above into a non-recursive one.
3
Exercise 2
Now you also want to compute which objects you would steal. Implement an-
other function
thief_which(objects, max_weight)
that returns a list of non-negative integers such that the integer at position i in
the list is the number of objects of type objects[i] you would steal in order
to get the maximum value. For the example of Exercise 1:
thief_which([(2,50), (3,100), (5,140)], 17) = [1, 5, 0]
Large inputs. Large inputs will be as in Exercise 1.
Hint: you can reuse code from Exercise 1. Additionally, you need to implement
a way of keeping track of the objects you steal.
Exercise 3
You want to implement a cache data structure. A cache is a small table with a
maximum number of slots size. In each slot you can put a value, indexed by
a key, and you can retrieve that value by looking its key up in the cache.
Since the number of slots is limited, when you put a new element into the
cache and the cache is full, one the existing elements must be discarded. One
way of doing this is by discarding the Least Recently Used (LRU) element, that
is, the element that has not been \used" for the longest time among all those
in the cache. An element is considered \used" when it’s put into the cache or
looked up.
Moreover, the cache has a Time To Live ttl, that is: the number of seconds
each element is allowed to stay in the cache without being used. An element is
considered dead if it has not been used for more than ttl seconds.
Implement a LRUCacheWithTTL class with the following structure:
class LRUCacheWithTTL:
# creates cache
def __init__(self, size, ttl):
pass # your code here
# puts "value" into the cache with key "key"
def put(self, key, value):
pass # your code here
# returns value with key "key" from the cache
# raises an exception if key is not in the cache
def lookup(self, key):
4
pass # your code here
# removes dead elements
def validate(self):
pass # your code here
The class should also implement an iterator that lists the pairs (key,value) in
the cache from the most recently used to the least recently used. For instance:
cache = LRUCacheWithTTL(2, 100)
cache.put("foo", 20)
cache.put("bar", 10)
element = cache.lookup("foo")
for e in cache:
print(e)
should print
(foo, 20)
(bar, 10)
Large inputs. Your solution will be tested for large values of size (up to
106), by calling the class methods and the iterator thousands of times.
Hint: You can use time.time() to get the current time in seconds.