Standard BFS-based algorithm

You may have seen the standard BFS-based algorithm that, given a set of n jugs with capacities 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 the same 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.)
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}.)
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?
How can you determine if there’s a negative-weight cycle of length at most k in time O(kn2
),
where n is the number of vertices in the graph?
Give an O(n
3
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.)

Standard BFS-based algorithm

Our Advantages

Secure Payments guaarantee