CS333 AlgorithmsFinal ExamInstructor: KD KangYour name: ____________________________________________________Please be concise. Also, make sure your answers are readable.1. [10%] Prove that a complete undirected simple graph with n vertices has n(n-1)/2 edges. (Hint: A graph is simple if there is no self-loop or multiple edges between two vertices.)2. [10%] To save space, would you use an adjacency list or adjacency matrix for a sparse graph? (a) [2%] Simply name either adjacency list or adjacency matrix.(b) [8%] Explain why you think an adjacency list or adjacency matrix is more space efficient to represent a sparse graph.3. [10%] Simply say True or False for the following questions. (a) By doing a depth first search, one can check whether or not an undirected graph is connected.(b) Adding an edge to a tree creates a cycle.(c) The minimum spanning tree problem is tractable.(d) It is unknown whether or not P = NP.(e) If there is a polynomial time algorithm to solve the traveling salesman problem, then P = NP.4. [10%] Prove that the greedy minimum finish time first algorithm for activity selection is optimal. 5. [10%] Use the optimal greedy algorithm for fractional knapsack problems to maximizethe profit for the following problem instance when the capacity of the knapsack W = 27.Show the actions step by step.Profit (pi) Weight (wi) pi/wiItem 1 $50 5 10Item 2 $140 20 7Item 3 $60 10 66. [10%] Prove that the worst case time complexity of the 0-1 knapsack algorithm usingbacktracking is Θ(2n) where n is the total number of the items.7. [10%] A computational problem is NP-complete if it meets two conditions. Describe thetwo conditions. (Each condition is worth 5%.)8. [15%] Use backtracking to solve the following sum of subsets problem. You have fourintegers w1 = 3, w2 = 4, w3 = 5, and w4 = 6 and the required sum of subsets S = 15. Drawthe pruned state space tree. No credit will be given if the state space tree is not shown orbacktracking is not used to prune the state space tree.9. [15%] Use Kruskal’s algorithm to find a minimum spanning tree in the graph below. Show the actions step by step. No credit will be given if Kruskal’s algorithm is not used.AC
View Full Document
Unlocking...