1Advanced Data Structures2TopicsData structuresstack, list, arrayTrees, heaps, union-find, hash tables, spatial, stringAlgorithm design & analysisSorting, graph algorithmsApplications3Why 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: 1Worst case: NAverage case: N/27 16 10 43834Why 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 435AnalysisDoes it matter?N vs. log2NN vs. Log N0204060801001201 2 3 4 5 6 7 8 9 10Nlinear (N)Logarithmic (log N)6AnalysisDoes it matter?AssumeN = 1,000,000,0001 billion (Walmart transactions in 100 days)1 GHz processor = 109cycles per second1 cycle per transactionO(N) algorithm1 billion transactions = > 1 billion clock cyclesO(lg N) algorithm1 billion transactions => 30 clock cycles7Example 2Scheduling job in a printerWrite a code to manage the printer queueFunctions to supportInsert, deleteSpecial accommodations needed for:PriorityDynamic updateScheduling challenges8Example 3Exploring the Facebook connection networkWrite a code to tell who is connected to who (directly or indirectly) through your Facebook profile6-degrees of separation9Example 4Pattern matchingWrite a code to do Google search on your web database10SummaryKeep the data organizedAppropriate data structures ease design & improve performanceChallengeDesign appropriate data structure & associated algorithms for a problemAnalyze to show improved
View Full Document
Unlocking...