Slide 1MergingSome unexplored nodesWhat we’ve coveredWhat we’ve coveredAnd nowApplicationsApplicationsTrees & TraversalsDecision TreesNeural NetworksThanks!CSE332: Data AbstractionsLecture 28: Course Wrap-upTyler RobisonSummer 20101Merging2So, we’ve spent the quarter exploring many different data structures; time to merge back together:Some unexplored nodes3Alternative data structures for balanced trees, priority queuesDisjoint-set data structure (union-find)AVL deletionMax-flow / min-cut graph algorithmsHuffman coding (compression)What we’ve covered4Really just a beginningMany other priority queues: skew heap, leftist heap, binomial queue, …Many other dictionaries: red/black tree, splay tree, …Many variations on hash tablesMany variations on B-TreesMany other sorts, graph algorithms, etc.Just scratched the surface of concurrencyRun-time/recurrence-relation analysis go much deeperWhat we’ve covered5But we’ve covered the foundationMany priority queues, but binary heaps are among the most commonMany dictionary data structures; among which balanced trees and hash tables are most importantGraph theory is an enormous area, but the basics will get you a long waysParallelism/concurrency issues covered are all that’s needed for many situationsAnd now6You should now be equipped toLearn new data structures & ADTs‘Once you learn one programming language, others come much easier’Understand/analyze run-timesUnderstand uses & trade-offsIn general make more informed use of them in programmingHave had experience writing/debugging/testing data structures & parallel/concurrent softwareMore experience with proofsMaybe not up to proving P!=NP, but stillKnow a bunch of tools, and know how to pick the right tool for the jobApplications7Hash tables: EverywhereSeriously, everywhereIf you’re interviewing for a programming job/internship, hash table questions are likely candidatesData Bases: B-Trees under the hoodGraphs show up in CS again and againJust very useful for modeling stuff:Computer networksPower gridsRoad systemsSocial networksKnowledge/concept mapsApplications8Parallelism & ConcurrencyIncreasingly importantMany more cores is likely the future of computing hardwareProgramming for many cores is going to be importantSpeed, and thus parallelism, hugely important in many areasGames (Xbox 360: 3 cores)ServersScientific/mathematical simulationsMany others; anything concerned with speedConcurrency problems pop up even in some simple Java applicationsEx: Handling GUI eventsBig Oh analysis: ubiquitous in CSNow some specific examples in AI; trees & graphsTrees & Traversals9•Problem space as tree•Want to find optimal solution•BFS & iterative deepening search both work well•Better technique called A* search:•Instead of ‘closest’ or ‘furthest’, choose lowest cost=g( )+h( )•g( ) is cost so far•h( ) is expected distance to goalDecision Trees10•Basis for simple decision-making agents•Algorithms to create optimal decision tree:•Take set of labeled data (‘Sunny,Normal Humidity,Strong Wind: Yes’)•Uses ‘information gain’ to decide what attribute to ask about next•Of course, real decision trees likely to be much larger•Ex: Face detection featuresNeural Networks11•Usually DAG of ‘neurons’•Edges represent how information propagates from input nodes (observations) to output nodes (decision)•Uses include OCR:•Conceptually have each pixel as a binary input•Each output represents a character: ‘Is this image a 9?’Thanks!12Extra office
View Full Document
Unlocking...