Regents of the University of Michigan - EECS 281 Lab 10 Part A- Assignment. Algorithm Families & Dynamic Programming . Part C: Coding Assignment

Document Content and Description Below

EECS 281 Lab 10 Assignment (18 points) Due ​Thursday, December 12, 2019​ at 11:59 PM Note: ​This lab assignment contains a survey, multiple choice quiz, and coding portion. Submit your answe... rs ​to ​the ​lab 10​ ​Canvas​ ​quiz​ ​and​ ​the​ ​coding​ ​portion​ ​to​ ​the​ ​autograder.​ ​You​ ​will​ ​have​ ​three​ ​attempts​ ​on​ ​the​ ​quiz. You ​MUST include the following assignment identifier at the top of every file you submit to the autograder as a comment. This includes all source files, header files, and your Makefile (if there is one). If there is no autograder assignment, you may ignore this. Assignment Identifier: D7E20F91029D0CB08715A2C54A782E0E8DF829BF Part A: Exit Survey (3 points) The exit survey can be found here: ​https://bit.ly/34sr80L​. Please complete the survey by Thursday, December 12th, at 11:59 PM! Completion of this survey is required to earn these three points. Part B: Algorithm Families & Dynamic Programming (5 points) 10.1 - MST Algorithms (0.75 points) What kind of algorithms are Prim’s and Kruskal’s? A. brute force B. greedy C. divide and conquer D. branch and bound E. none of the above 10.2 - Selection Sort (0.75 points) What kind of algorithm is selection sort? A. brute force B. greedy C. divide and conquer D. branch and bound E. none of the above © 2019 Regents of the University of Michigan​ ​Page 110.3 - Quicksort and Mergesort (0.75 points) What kind of algorithms are quicksort and mergesort? A. brute force B. greedy C. divide and conquer D. branch and bound E. none of the above 10.4 - Map Application (0.75 points) Your company is working on a map application but has run into a roadblock in their algorithm — finding the shortest route from point A to point B takes too long for practical use! Upon further analysis, you realize that the algorithm often does unnecessary work by traversing paths that are worse than the current optimal path. What algorithm can you use to fix this problem? A. brute force B. greedy C. divide and conquer D. branch and bound E. none of the above 10.5 - Know Your Algorithms (1 point) Which of the following statements is/are TRUE? Select all that apply. A. a brute force solution will ​always​ give you the optimal solution B. because backtracking avoids looking at large portions of the search space by pruning, the asymptotic complexity of backtracking is ​always​ better than that of brute force C. the greedy algorithm guarantees an optimal solution to the 0-1 knapsack problem D. branch and bound will not speed up your program if it takes just as long to determine the bounds than to test all possible choices E. dynamic programming reduces both the time and memory needed to solve a problem with multiple overlapping subproblems F. given ​n items and a knapsack capacity of ​m​, the dynamic programming solution to the 0-1 knapsack problem runs in Θ(​mn​​) time [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages