CS566_Final_Exam Boston University MET CS 566

Document Content and Description Below

Final Exam Fall 2021 ____________________________________________________________________________________ CS566 A1 Final Exam Due – Dec 15, 2021, 6:00 PM Student’s Name: Mohamed Aboulela Al... l work must be your own. No extensions or late submissions for anything. (1) [5 pts.] A graph with n nodes is connected, undirected, and acyclic. How many edges must it have? Select the answer from the following options and prove your choice. a) n b) n*(n-1) c) n - 1 d) n/2 – 1 Answer: c) n – 1. This is the answer because any connected and undirected graph with an n number of nodes and doesn’t have any cycle is a tree and a tree over n always has n – 1 edges. (2) [10 pts.] Which Design Technique was used to produce Kruskal's Algorithm? Select the answer from the following options and explain your choice: a) Dynamic Programming b) Greedy c) Divide and Conquer d) Linear Programming Answer: b) Greedy. This is because any algorithm related to Prim and Kruskal are greedy algorithms. In a Kuskal algorithm, in order to find the MST, the edge with the least weight is selected greedily. (3) [25 pts.] Given this method: METHOD math1: public int math1( int n ) { if (n < 1) { return 0; } // if [Show More]

Last updated: 5 days ago

Preview 4 out of 11 pages