Slide 1Final ExamVictory LapThank you!Thank you!Four slides from Lecture 1Four slides from Lecture 1Four slides from Lecture 1Four slides from Lecture 1Victory LapWhat I told the faculty about CSE332Topics: Data structures + ThreadsTopics: Data structures + ThreadsTopics: Data structures + ThreadsWhat worksWhat might not workVictory LapLast slideCSE332: Data AbstractionsLecture 28: Course Wrap-Up / Victory LapDan GrossmanSpring 2010Final Exam As also indicated in class-list email and on the web page:•Next Tuesday, 2:30-4:20•Intention is to test a subset of the topics in sorting, graphs, parallelism, concurrency, amortization–In other words, “stuff not covered by the midterm”–But as always the course topics build on earlier ones•You will need to read and write Java, among other things•Dan leaves town tomorrow morning, but will have email–Exam and course grades will not be available until June 13-14–Homework and project grades available soonerSpring 2010 2CSE332: Data AbstractionsVictory LapA victory lap is an extra trip around the track –By the exhausted victors (that’s us) Review course goals–Slides from Lecture 1–What I told the facultyFeedback from you on a new course being taught every quarter–Anything to discuss as a group–Course evaluations• Please spend even more time than usual on themSpring 2010 3CSE332: Data AbstractionsThank you!Huge thank-you to your TAs–New homeworks, projects, material, libraries–Tyler: Use section to teach relevant programming idioms, project 3 guinea pig, teaching the course in summer, …–Brent: A cool GUI, project 2 unit-test examples, …Spring 2010 4CSE332: Data AbstractionsThank you!And huge thank you to all of you–Great attitude about a new course–Good class attendance and questions–Occasionally laughed at stuff Spring 2010 5CSE332: Data AbstractionsFour slides from Lecture 1We have 10 weeks to learn fundamental data structures and algorithms for organizing and processing information–“Classic” data structures / algorithms and how to analyze rigorously their efficiency and when to use them–Queues, dictionaries, graphs, sorting, etc.–Parallelism and concurrency (new!)Spring 2010 6CSE332: Data AbstractionsFour slides from Lecture 1•Introduction to many (not all) of the basic data structures used in computer software–Understand the data structures and the trade-offs they make–Rigorously analyze the algorithms that use them (math!)–Learn how to pick “the right thing for the job”–More thorough and rigorous take on topics introduced in 143•And more•Practice design and analysis of data structures / algorithms•Practice implementing and using these data structures by writing programs•Experience the purposes and headaches of multithreadingSpring 2010 7CSE332: Data AbstractionsFour slides from Lecture 1•To be able to make good design choices as a developer, project manager, etc.–Reason in terms of the general abstractions that come up in all non-trivial software (and many non-software) systems•To be able to justify and communicate your design decisionsDan’s take: 3 years from now this course will seem like it was a waste of your time because you can’t imagine not “just knowing” every main concept in it–Key abstractions computer scientists and engineers use almost every day–A big piece of what separates us from othersSpring 2010 8CSE332: Data AbstractionsFour slides from Lecture 1(Often highly non-obvious) ways to organize information in order to enable efficient computation over that information–Key goal over the next week is introducing asymptotic analysis to precisely and generally describe efficient use of time and spaceA data structure supports certain operations, each with a:–Meaning: what does the operation do/return–Performance: how efficient is the operationSpring 2010 9CSE332: Data AbstractionsVictory LapA victory lap is an extra trip around the track –By the exhausted victors (that’s us) Review course goals–Slides from Lecture 1–What I told the facultyFeedback from you on a new course being taught every quarter–Anything to discuss as a group–Course evaluations• Please spend even more time than usual on themSpring 2010 10CSE332: Data AbstractionsWhat I told the faculty about CSE332Catalog Description:Abstract data types and structures including dictionaries, balanced trees, hash tables, priority queues, and graphs; sorting; asymptotic analysis; fundamental graph algorithms including graph search, shortest path, and minimum spanning trees; concurrency and synchronization; and parallelism. Goals:–Deep understanding of core data-structure trade-offs–Fluency with asymptotic complexity, exponentials, etc.–Ability to analyze correctness (?) and efficiency–Recognizing basic opportunities for parallelism–Addressing challenges of concurrent access to resourcesSpring 2010 CSE332: Data Abstractions 11Topics: Data structures + Threads326 & 332 (20 lectures)Big-Oh, Algorithm AnalysisBinary Heaps (Priority Qs)AVL TreesB TreesHashingSortingGraph TraversalsTopological SortShortest PathsMinimum Spanning TreesAmortizationSpring 2010 CSE332: Data Abstractions 12Topics: Data structures + Threads326 & 332 (20 lectures)Big-Oh, Algorithm AnalysisBinary Heaps (Priority Qs)AVL TreesB TreesHashingSortingGraph TraversalsTopological SortShortest PathsMinimum Spanning TreesAmortizationSpring 2010 CSE332: Data AbstractionsRemoved from 326 (8 lectures)D-heapsLeftist heapsSkew heapsBinomial queuesSplay treesDisjoint setsNetwork flowHack job on NP (moves to CSE312)13Topics: Data structures + Threads326 & 332 (20 lectures)Big-Oh, Algorithm AnalysisBinary Heaps (Priority Qs)AVL TreesB TreesHashingSortingGraph TraversalsTopological SortShortest PathsMinimum Spanning TreesAmortizationSpring 2010 CSE332: Data AbstractionsAdded to 332 (8 lectures)Multithreading Basics (1)Fork-Join Parallelism (3)•Using Java library•Analysis: T1 and T •Amdahl’s Law•Reductions, Prefix, SortingConcurrency (4)•Races, deadlocks•Locks (mostly) •Condition variables (a bit)•Programming guidelines (!)14What works•Triage 30% without killing the patient–Plus pretty deep scrub of other 70%–Projects use more modern Java (generics, iterators, JUnit)–Still keystone course with algorithms, code, proofs, and charts•Parallelism and concurrency in this course–Natural fit (!): same notion of trade-offs, asymptotics•Example: Sequential