Slide 1Welcome to 332!Today in class:About usTo-doStaying in touchCourse materialsCourse WorkCollaboration and Academic IntegrityHow 332 differs from 326Data structuresTrade-offsTerminologyExample: StacksWhy ADT is a useful abstractionThe Queue ADTCircular Array Queue Data StructureLinked List Queue Data StructureCircular Array vs. Linked ListThe Stack ADTCSE332: Data AbstractionsLecture 1: Introduction; Stacks/QueuesTyler RobisonSummer 2010Welcome to 332!What we’re going to be doing this quarter:Study many common data structures & algorithms that underlie most computer systems, for instance:Btrees -> DatabasesQueues -> Printer queueStacks -> Program call-stackHashtables, sorting algorithms, graphs, etc.Learn to rigorously analyze them and think carefully about what to use when: Uses, limitations, efficiency, etc.Asymptotic analysis -> shows up everywhere in CSStudy the increasingly important areas of parallelism and concurrency, and relevance to algorithms/data-structuresToday in class:Course mechanicsWhat this course is aboutHow it differs from 326Abstract Data TypesStart (finish?) stacks and queues (largely review)About usCourse Staff:Tyler Robison Sandra FanOffice hours:Wednesday 2:00-3:00 & by appointmentRoom: CSE 212Office hours:Thursday 12:00-1:00Room: CSE 218To-doYour to-do:Make sure you get mail sent to cse332a_su10 at u.washington.eduRead all course policiesRead/skim Chapters 1 and 3 of Weiss bookRelevant to Project 1, due next week (don’t worry; it’s not too bad)Relevant to Hw 1, due next weekWill start Chapter 2 on WednesdayPossibly set up your Eclipse / Java environment for the first project Thursday’s section will helpCheck out the website:http://www.cs.washington.edu/education/courses/cse332/10su/Staying in touchCourse email list: cse332a_su10@uStudents and staff already subscribed (in theory – let me know)Used for announcementsFairly low trafficCourse staff: cse332-staff@cs to send to both Sandra & myselfQuestions, comments, etc.Message BoardPosing questions, discussing materialSandra & I will try to check it on a regular basisAnonymous feedback link on webpageFor good and bad: if you don’t tell me, I don’t knowCourse materialsLectures:First exposure to materialPresentation of algorithms, proofs, etc.Provide examples, asidesSection:Programming details (Eclipse, generics, junit, ForkJoin framework)Practice with algorithms: Given the stuff we’re going to cover, practice is definitely importantMain Textbook: Weiss 2nd Edition in JavaOptional Textbook: Core Java book: A good Java reference (there may be others)Parallelism/Concurrency material not in either book (or any appropriate one)However, Dan Grossman wrote up excellent slides and notes for those topicsCourse Work7 to 8 written/typed homeworks (25%)Due at beginning of class each Friday (but not this week)No late homework, pleaseEven if you don’t have time to do it all, turn in something – some credit is better than no credit3 programming projects (some with phases) (25%)Use Java and Eclipse (see this week’s section)You’ve got one 24-hour late-day for the quarterFirst project due next week (rather lighter than the others)Projects 2 and 3 will allow partners; use of SVN encouragedMidterm: July 19th (20%)Final: August 20th (25%)5% to your strongest aboveCollaboration and Academic IntegrityWorking together is fine – even encouraged – but keep discussions at a high level, and always prepare your own solutionsRead the course policy (on the website)Explains how you can and cannot get/provide help on homework and projectsHow 332 differs from 326332 is about 70% of the material from 326Covers the same general topics, and the important algorithms/data-structuresCuts out some of the alternative data-structures, and some less important onesYou can probably live a full & meaningful life without knowing what a binomial queue isBiggest new topic: a serious treatment of programming with multiple threadsFor parallelism: To use multiple processors to finish soonerFor concurrency: Allow properly synchronized access to shared resourcesData structures(Often highly non-obvious) ways to organize information in order to enable efficient computation over that informationKey goal over the next week is introducing asymptotic analysis to precisely and generally describe efficient use of time and space‘Big Oh’ notation used frequently in CS: O(n), O(logn), O(1), etc.A data structure supports certain operations, each with a:Purpose: what does the operation do/returnPerformance: how efficient is the operationExamples:List with operations insert and deleteStack with operations push and popTrade-offsA data structure strives to provide many useful, efficient operationsOften no clear-cut ‘best’: there are usually trade-offs:Time vs. spaceOne operation more efficient if another less efficientGenerality vs. simplicity vs. performanceThat is why there are many data structures and educated CSEers internalize their main trade-offs and techniquesRecognize the right tool for the jobAnd recognize logarithmic < linear < quadratic < exponentialTerminologyAbstract Data Type (ADT)Mathematical description of a “thing” with set of operations on that “thing”; doesn’t specify the details of how it’s doneEx, Stack: You push stuff and you pop stuffCould use an array, could use a linked listAlgorithmA high level, language-independent description of a step-by-step processEx: Binary searchData structureA specific family of algorithms & data for implementing an ADTEx: Linked list stackImplementation of a data structureA specific implementation in a specific languageExample: StacksThe Stack ADT supports operations:isEmpty: initially true, later have there been same number of pops as pushespush: takes an itempop: raises an error if isEmpty, else returns most-recently pushed item not yet returned by a pop… (Often some more operations)A Stack data structure could use a linked-list or an array or something else, and associated algorithms for the operationsOne implementation is in the library java.util.StackWhy ADT is a useful abstractionThe Stack ADT is a useful abstraction because:It arises all the time in programming (see text for
View Full Document