Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.
To specify an array or sequence of values in an answer, separate the values inthe sequence by whitespace. For example, if the question asks for the firstten powers of two (starting at 1), then the following answer is acceptable: 1 2 4 8 16 32 64 128 256 512If you wish to discuss a particular question and answer in the forums, pleasepost the entire question and answer, including the seed (which can be used bythe course staff to uniquely identify the question) and the explanation (whichcontains the correct answer).
(seed = 837393)Which of the following problems can be linear-time reduced *to* the standard shortest-paths problem in digraphs with nonnegative weights? Check all that apply.
Given a digraph and two vertices s and t, find a path from s to t that uses the fewest edges.
Given a digraph with positive edge weights where each edge is colored either red or black, find the shortest path from s to t that uses at most one red edge.
Given a digraph with positive *vertex* weights and two vertices s and t, find a shortest path from s to t (where the length of the path is the sum of the vertex weights).
Given an undirected graph and two vertices s and t, among all paths between s and t, find one that uses the fewest edges.
Given a currency exchange digraph, determine if there exists an arbitrage opportunity.
(seed = 892350)Which problems are known to have the same asymptotic complexity as multiplying two N-by-N matrices? Check all that apply.
Finding the maximum value in an N-by-N matrix.
Inverting an N-by-N matrix.
Adding two N-by-N matrices.
Solving an N-by-N system of linear equations.
Sorting each of the N rows of an N-by-N matrix in ascending order.
(seed = 505865)Suppose that 3-SUM has a N^(3/2) lower bound and that 3-SUM linear-time reduces to 3-COLLINEAR. Which of the following can you infer? Check all that apply.
3-SUM can be solved in N^(3/2) time.
3-COLLINEAR cannot be solved in N^(5/4) time.
If 3-SUM can be solved in N^(3/2) time, then so can 3-COLLINEAR.
If 3-COLLINEAR can be solved in N^(3/2) time, then so can 3-SUM.
3-SUM cannot be solved in N^(5/4) time.