Dynamic Sets and Data StructuresSome Example OperationsBasic Data Structures/ContainersImplementation QuestionsSlide 5Case Study: DictionaryCase Study: Priority QueueCase Study: Minimum Spanning TreesPrim’s algorithmIllustrationUpdating Dynamic SetSlide 12Dynamic Set AnalysisDynamic Sets and Data Structures•Over the course of an algorithm’s execution, an algorithm may maintain a dynamic set of objects•The algorithm will perform operations on this set–Queries–Modifying operations•We must choose a data structure to implement the dynamic set efficiently•The “correct” data structure to choose is based on –Which operations need to be supported–How frequently each operation will be executedSome Example Operations•Search(S,k)•Insert(S,x)•Delete(S,x)•Minimum or Maximum(S)•Successor or Predecessor (S,x)•Merge(S1,S2)Basic Data Structures/Containers•Unsorted Arrays•Sorted Array•Unsorted linked list•Sorted linked list•Stack•Queue•HeapImplementation Questions•How can I implement a queue with two stacks?–Running time of enqueue?–Dequeue?•How can I implement two stacks in one array A[1..n] so that neither stack overflows unless the total number of elements in both stacks exceeds n?Unsorted ArraySorted ArrayUnsorted LLSorted LLHeapSearchInsertDeleteMax/MinPred/SuccMergeCase Study: Dictionary•Search(S,k)•Insert(S,x)•Delete(S,x)•Is any one of the data structures listed so far always the best for implementing a dictionary?•Under what conditions, if any, would each be best?•What other standard data structure is often used for a dictionary?Case Study: Priority Queue•Insert(S,x)•Max(S)•Delete-max(S)•Is any one of the data structures listed so far always the best for implementing a priority queue?•Under what conditions, if any, would each be best?Case Study: Minimum Spanning Trees•Input–Weighted, connected undirected graph G=(V,E)•Weight (length) function w on each edge e in E•Task–Compute a spanning tree of G of minimum total weight•Spanning tree–If there are n nodes in G, a spanning tree consists of n-1 edges such that no cycles are formedPrim’s algorithm•A greedy approach to edge selection–Initialize connected component N to be any node v–Select the minimum weight edge connecting N to V-N–Dynamic set implementation•The nodes in V-N•Value of a node is how close it is to any node in N•To select minimum weight edge, choose node v with minimum value in dynamic set (Extract minimum) and add v to N•When v is added to N, we need to update the value of the neighbors of v in V-N (Decrease key)•Maintain dynamic set of nodes in V-N•If we started with node D, N is now {C,D}•Dynamic set values of other nodes:–A, E, F: infinity–B: 4–G: 6IllustrationA B CDE F G1223455610•Node B is added to N; edge (B,C) is added to T•Need to update dynamic set values of A, E, F–Decrease-key operation•Dynamic set values of other nodes:–A: 1–E: 2–F: 5–G: 6Updating Dynamic SetA B CDE F G1223455610•Node A is added to N; edge (A,B) is added to T•Need to update dynamic set values of E–Decrease-key operation•Dynamic set values of other nodes:–E: 2 (unchanged because 2 is smaller than 3)–F: 5–G: 6Updating Dynamic SetA B CDE F G1223455610Dynamic Set Analysis•How many objects in initial dynamic set representation of V-N?•Time to build this dynamic set?•How many extract-min operations need to happen?•How many decrease-key operations may occur?•Given all of the above, choose a data structure and tell me the implementation