Advanced Data StructuresTopicsSo, what is a data structure?Why study data structures?Slide 5AnalysisSlide 7Example 2Example 3Example 4SummaryAdvanced Data StructuresAn introduction1Cpt S 223. School of EECS, WSU2TopicsData structures(review) stack, list, array, BST(new) Trees, heaps, union-find, hash tables, specialized (for spatial & strings)Algorithm design & analysisSorting, graph algorithmsApplications Cpt S 223. School of EECS, WSU3So, what is a data structure?A container for data that allows organized access and manipulationCpt S 223. School of EECS, WSU4Why study data structures?Example problemGiven: a set of N numbersGoal: search for number kSolutionStore numbers in an array of size NLinearly scan array until k is found or array is exhaustedNumber of checksBest case: 1 Worst case: NAverage case: N/27 16 10 4383Cpt S 223. School of EECS, WSU5Why study data structures?Solution #2Store numbers in a binary search treeSearch tree until find kNumber of checksBest case: 1 Worst case: log2NAverage case: (log2N)/273 101 6 8 43Cpt S 223. School of EECS, WSU6AnalysisDoes it matter?N vs. log2NN vs. Log N0204060801001201 2 3 4 5 6 7 8 9 10Nlinear (N)Logarithmic (log N)Cpt S 223. School of EECS, WSU7AnalysisAssumeN = 1,000,000,0001 billion (Walmart transactions in 100 days)1 GHz processor = 109 cycles per second1 cycle per transactionO(N) algorithm 1 billion transactions = > 1 billion clock cyclesO(lg N) algorithm 1 billion transactions => 30 clock cyclesCpt S 223. School of EECS, WSU8Example 2Scheduling job in a printerWrite a code to manage the printer queueFunctions to supportInsert, deleteSpecial accommodations needed for:PriorityDynamic update Scheduling challengesCpt S 223. School of EECS, WSU9Example 3Exploring the Facebook connection networkWrite a code to tell who is connected to who (directly or indirectly) through your Facebook profileDegrees of separationCpt S 223. School of EECS, WSU10Example 4Pattern matchingWrite a code to do Google search on your web databaseCpt S 223. School of EECS, WSU11SummaryKeep the data organizedChoice of data structures mattersAppropriate data structures ease design & improve performanceChallengeDesign appropriate data structure & associated algorithms for a problemAnalyze to show improved performanceCpt S 223. School of EECS,
View Full Document
Unlocking...