Answer Happy

The following problems are multiple choice with multiple selection. A problem situation will be described, and it is your job to choose the best data structure (where applicable) and algorithm for the most time efficient implementation of the operations specified. Don't be fooled by words: often clients give problems in words different than those you learned in this class. It is your job to find the right computational model. Application: Your client is a transportation company that transports high value small cargo (e.g., jewels, human organs, and visiting dignitaries) on demand in a large metropolitan area using cars and vans. You have a map of roads and relevant locations. Roads are marked with expected travel time, based on experience. Travel times are frequently updated for current conditions, so we can't pre- compute routes. We want to quickly find the fastest route between a start location and destination on demand. Make exactly two selections: the computational model you choose, and the time complexity for the main operations specified: A. Model: Array implementation of Heap for partial order B. Model: Dynamic Set ADT using Hashtable with chaining C. Model: Dynamic Set ADT with Binary Search Tree D. Model: Dynamic Set ADT with Red-Black Tree or Skip List E. Model: Flow network using Edmunds-Karp F. Model: Sorted List maintained with Randomized Quicksort G. Model: Union-Find ADT using forest with rank and path heuristics H. Model: Weighted Graph; Dijkstra's algorithm for shortest paths 1. Time: 0(1 + n/m) where m is an additional parameter you choose J. Time: O(E lg V) since it's connected K. Time: O(VE?) L. Time: O(a(V)), which is for practical purposes O(1) M. Time: O(lg n) for most operations; O(n) for listing contents N. Time: O(n lg n) expected Ooo O. Time: O(n) P. Time: O(n) to build it, O(lg n) to extract items