Mathematics > EXAM > University of Southern California CSCI 570 Midterm Exam 3 Summer Rubric1-REVIEWED AND VERIFIED BY E (All)
CS570 Exam III Name: _____________________ Student ID: _________________ Email Address:________________ _____Check if DEN Student Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Prob... lem 4 15 Problem 5 10 Problem 6 15 Problem 7 10 Total 100 Instructions: 1. This is a 2-hr exam. Closed book and notes 2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question. 3. No space other than the pages in the exam booklet will be scanned for grading. 4. If you require an additional page for a question, you can use the extra page provided within this booklet. However please indicate clearly that you are continuing the solution on the additional page.1) 20 pts Mark the following statements as TRUE or FALSE. No need to provide any justification. [ TRUE/FALSE ] Every problem in P can be reduced to 3-SAT in polynomial time. [ TRUE/FALSE ] If there is a polynomial-time algorithm for 2-SAT, then every problem in NP has a polynomial-time algorithm. [ TRUE/FALSE ] If all edge weights are 1, 2, or 3, the shortest path problem can be solved in linear time. [ TRUE/FALSE ] Suppose G is a graph with n vertices and n1.5 edges, represented in adjacency list representation. Then depth-first search in G runs in O(n1.5) time. [ TRUE/FALSE ] The weight of a minimum spanning tree in a positively weighted undirected graph is always less than the total weight of a minimum spanning path (Hamiltonian Path with lowest weight) of the graph. [ TRUE/FALSE ] If A is in NP, and B is NP-complete, and A ≤p B then A is NP-complete [Show More]
Last updated: 1 year ago
Preview 1 out of 12 pages
Connected school, study & course
About the document
Uploaded On
May 31, 2021
Number of pages
12
Written in
This document has been written for:
Uploaded
May 31, 2021
Downloads
0
Views
51
In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.
We're available through e-mail, Twitter, Facebook, and live chat.
FAQ
Questions? Leave a message!
Copyright © Browsegrades · High quality services·