Assignment 7
posted: 16.07.2021 due: midnight 23.07.2021
You can work in groups of up to three people. One group member should submit a copy of the solu-
tions on Brightspace, with all members’ names and banner numbers on it; the other group members
should submit text files with all members’ names and banner numbers (otherwise Brightspace won’t
let us assign them marks!). You may consult with other people but each group should understand
the solutions: after discussions with people outside the groups, discard any notes and do something
unrelated for an hour before writing up your solutions; it’s a problem if no one in a group can ex-
plain one of their answers. For programming questions you should submit your code, which should
compile and run correctly to receive full marks.
1. You may have seen the standard BFS-based algorithm that, given a set of n jugs with capac-
ities c1, . . . , cn in litres, a target of t litres and access to a tap, finds the fastest way of using
the jugs to measure out t litres of water, or that it’s not possible. If the cis are integers then
this takes O((c1 + 1) · (c2 + 1) · · · (cn + 1) · (n + 1)2) time.
How can you modify the standard algorithm such that it runs in
O((c1 + 1) · (c2 + 1) · · · (cn + 1) · (n + 1)2 · log((c1 + 1) · (c2 + 1) · · · (cn + 1))
time and, instead of the fastest way (fewest pours), it finds the way to measure out t litres
which involves the least total lifting? For example, pouring 2 litres from 5-litre jug containing
4 litres into a 3-litre jug containing 1 litre, and then pouring the remaining 2 litres from the
5-litre jug into a 6-litre jug containing 1 litre, involves lifting a jug containing 4 litres and
then lifting a jug (the same one) that contains 2 litres, so the total cost is 6. (You can assume
the tap has a hose so you can fill a jug without lifting it.)
2. Suppose you’re given a list of statements such as “Factoring polytime reduces to Sat”,
“Clique polytime reduces to Independent Set”, “Independent Set polytime reduces to
Sat” and “Sat polytime reduces to Clique”. How can you divide the mentioned problems
up into the minimum number of equivalence classes such that, for any equivalence class C and
any two problems P and Q in C, you know only from the statements that P polytime reduces
to Q and vice versa? (In the example above, there are two equivalence classes: {Factoring}
and {Sat,Clique, Independent Set}.)
3. How can you modify Dijkstra’s (without making it much slower) such that it works even when
there’s one directed negative-weight edge in the graph?
4. How can you determine if there’s a negative-weight cycle of length at most k in time O(kn3),
where n is the number of vertices in the graph?
5. Give an O(n3 log k)-time algorithm that, given an integer k and the n× n adjacency matrix
of a graph on n vertices, returns the n × n matrix in which cell (i, j) is the number of ways
of going from the ith vertex to the jth vertex in exactly k steps.
(Hint: First figure out how to do this when k is a power of 2, and then consider the binary
representation of general k.)
1
Assignment 7