(50 pts.) A Planning Problem Suppose you are given a weighted undirected graph G=(V, E) encoding places on a map and the possible movements between them (the weights being the corresponding distances), a starting position s EV, and an ending position 1 V. You are also given a list of checkpoints c1, ..., CL V which must be visited in increasing order: for example, if you visit C3, you cannot later visit cy or cz (but visiting them before you got to cz is fine, and passing through non-checkpoint vertices along the way is also fine). Describe an efficient algorithm which, given some k {1,...,l}, finds the shortest path from s to t which visits exactly k of the checkpoints, in an allowed order (or detects that no such path exists). (Note: you can't just try all possible choices of k checkpoints, since if there are n vertices and l = n/2 for example, then there are (172) = 20(n) such choices. Make your algorithm as fast as you can it should take no more than O(na) time for some small d, e.g. 3 or 4) (50 pts.) A Planning Problem Suppose you are given a weighted undirected graph G=(V, E) encoding places on a map and the possible movements between them (the weights being the corresponding distances), a starting position s EV, and an ending position 1 V. You are also given a list of checkpoints c1, ..., CL V which must be visited in increasing order: for example, if you visit C3, you cannot later visit cy or cz (but visiting them before you got to cz is fine, and passing through non-checkpoint vertices along the way is also fine). Describe an efficient algorithm which, given some k {1,...,l}, finds the shortest path from s to t which visits exactly k of the checkpoints, in an allowed order (or detects that no such path exists). (Note: you can't just try all possible choices of k checkpoints, since if there are n vertices and l = n/2 for example, then there are (172) = 20(n) such choices. Make your algorithm as fast as you can it should take no more than O(na) time for some small d, e.g. 3 or 4)