Homework 5 is out. Any question can be asked here.
Problem 1
Q: is there a maximum grade?
A:You can assume there is no maximum grade for each course.
Q: Can you give us hint on the running time for problem 1?
For full credit. The running time should be O(n), O(T log n+ n), O(nT^2)
Hint for case 3: dynamic programming
Problem 4
Q:The goal is to: delete as many edges as possible from G , when Vertex u is reachable from v if there is a path from v to u. Also, do we need to remove as many edges as possible from the other vertexes that will be along the path from u--to --v? or just to remove the edges that connect u--to--v and left the minimum path.
A: This problem requires you to delete the maximum number edges so that the reachability does not change for *ANY* two vertices u, v; i.e., for any two vertices u,v in V, u is reachable from v in G if and only if u is reachable from v in G'.
For problem 2, does this case work: first stay in a lecture for time t1, then leave, then enter again and stay time t2, both t1 and t2 are less than t, but t1+t2 are greater than t?
ReplyDeleteYou can enter each lecture only one time.
ReplyDeleteFor problem 1, Could you give any hint about the optimal time complexity for case 1) 2) and 3)?
ReplyDelete