New version page

# WSU CPTS 223 - Advanced Data Structures

Documents in this Course

97 pages

35 pages

3 pages

30 pages

18 pages

66 pages

52 pages

2 pages

53 pages

47 pages

3 pages

4 pages

2 pages

19 pages

33 pages

22 pages

20 pages

11 pages

19 pages

3 pages

61 pages

8 pages

116 pages

42 pages

131 pages

51 pages

51 pages

39 pages

39 pages

109 pages

15 pages

56 pages

10 pages

20 pages

2 pages

2 pages

## This preview shows page 1-2-3-4 out of 11 pages.

View Full Document

End of preview. Want to read all 11 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

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, WSU2TopicsData structures(review) stack, list, array, BST(new) Trees, heaps, union-find, hash tables, specialized (for spatial & strings)Algorithm design & analysisSorting, graph algorithmsApplications 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 problemGiven: a set of N numbersGoal: search for number kSolutionStore numbers in an array of size NLinearly scan array until k is found or array is exhaustedNumber of checksBest case: 1 Worst case: NAverage case: N/27 16 10 4383Cpt S 223. School of EECS, WSU5Why study data structures?Solution #2Store numbers in a binary search treeSearch tree until find kNumber of checksBest case: 1 Worst case: log2NAverage case: (log2N)/273 101 6 8 43Cpt S 223. School of EECS, WSU6AnalysisDoes 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, WSU7AnalysisAssumeN = 1,000,000,0001 billion (Walmart transactions in 100 days)1 GHz processor = 109 cycles per second1 cycle per transactionO(N) algorithm 1 billion transactions = > 1 billion clock cyclesO(lg N) algorithm 1 billion transactions => 30 clock cyclesCpt S 223. School of EECS, WSU8Example 2Scheduling job in a printerWrite a code to manage the printer queueFunctions to supportInsert, deleteSpecial accommodations needed for:PriorityDynamic update Scheduling challengesCpt S 223. School of EECS, WSU9Example 3Exploring the Facebook connection networkWrite a code to tell who is connected to who (directly or indirectly) through your Facebook profileDegrees of separationCpt S 223. School of EECS, WSU10Example 4Pattern matchingWrite a code to do Google search on your web databaseCpt S 223. School of EECS, WSU11SummaryKeep the data organizedChoice of data structures mattersAppropriate data structures ease design & improve performanceChallengeDesign appropriate data structure & associated algorithms for a problemAnalyze to show improved performanceCpt S 223. School of EECS,

View Full Document
Unlocking...