Application: You are writing a program to do cluster analysis of a graph G = (V, E). Initially, every vertex is in its o

[answerhappygod]

Application You Are Writing A Program To Do Cluster Analysis Of A Graph G V E Initially Every Vertex Is In Its O 1 (109.07 KiB) Viewed 24 times

Application: You are writing a program to do cluster analysis of a graph G = (V, E). Initially, every vertex is in its own cluster. Then vertices that have similar connectivity are merged bottom-up into larger clusters. Among other things, you need to quickly determine whether two vertices are in the same cluster, and to merge clusters efficiently. (We are not asking you to solve cluster analysis here!) 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 OOOOO 0. Time: O(n) P. Time: O(n) to build it, Ollg n) to extract items