CS theory Problem 1: CS Data and Algorithm Analysis question Let us start with s
ID: 3830341 • Letter: C
Question
CS theory Problem 1: CS Data and Algorithm Analysis question
Let us start with some quickies. For each statement below, say whether it is true or false or fill in the blank. You do not need to provide a rationale for your solution. 1. If A and B are problems such that B element P and B lessthanorequalto p A, then A elementof P. In a directed graph, every edge has a positive integer weight that is bounded by the quantity omega. The graph has n nodes and m edges. We can compute the shortest path between any two nodes in this graph in O(omega(n + m)) time. In a directed graph, let d(x, y) denote the length of the shortest path between nodes x and y. If e = (u, v) is an edge on a shortest path from s to t, then d(s, t) = d(s, u) + l_e + d(v, t), where l_e is the length of the edge e. An algorithm takes an input of size n, performs some computation in O(n) time, and then recurses on one sub-problem of size n/2 to compute the solution. The running time of this algorithm is O(n). If P = NP and problem X is NP-Complete, then there is a polynomial time algorithm to solve X. ___ ___ is a real-life person who appears as an unseen character in the first Harry Potter book and movie.Explanation / Answer
1. False, here there should be A<=p B
4. False
5.True, If P=NP then X can be solved in polynomial time