CSE332: Data AbstractionsLecture 1: Introduction; Stacks/QueuesDan GrossmanSpring 2010Welcome!We 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!)Today in class:• Course mechanics• What this course is about (“the new 326”)– And how it fits into the revised curriculum• Start (finish?) stacks and queues (largely review)Spring 2010 2CSE332: Data AbstractionsConcise to-do listIn the 24-48 hours:• Adjust class email-list settings• Email homework 0 (worth 0 points) to me• Read all course policies• Read/skim Chapters 1 and 3 of Weiss book– Relevant to Project 1, due next week– Will start Chapter 2 on WednesdayPossibly:• Set up your Eclipse / Java environment for project 1– Thursday’s section will helphttp://www.cs.washington.edu/education/courses/cse332/10sp/Spring 2010 3CSE332: Data AbstractionsWhoCourse Staff:Dan Grossman Tyler Robison Brent SandonaSpring 2010 4CSE332: Data AbstractionsDan: Faculty, “a 341 guy”, excited about 332 (& curriculum revision)Tyler: Grad student, Summer2010 332 instructor, Winter2010 326 TABrent: Senior, CompE, veteran TA, including 326Office hours, email, etc. on course web-pageStaying in touch• Course email list: cse332a_sp10@u– Students and staff already subscribed– You must get announcements sent there– Fairly low traffic• Course staff: cse332-staff@cs plus individual emails• Message Board– For appropriate discussions; Brent will monitor– Optional, won’t use for important announcements• Anonymous feedback link on webpage– For good and bad: if you don’t tell me, I don’t knowSpring 2010 5CSE332: Data AbstractionsCourse meetings• Lecture (Dan)– Material posted (sometimes afterwards), but take notes– Ask questions, focus on key ideas (rarely coding details)• Section (Tyler)– Often focus on software (Java features, tools, project issues)– Reinforce key issues from lecture (good practice)– Answer homework questions, etc.– Goal: More important than it was for your friends in 326• Office hours– Use them: please visit me– Ideally not just for homework questions (but that’s great too)Spring 2010 6CSE332: Data AbstractionsCourse materials• All lecture and section materials will be posted– But they are visual aids, not always a complete description!– If you have to miss, find out what you missed• Textbook: Weiss 2ndEdition in Java– Good reading, but only responsible for lecture/section/hw topics– Will assign homework problems from it• Core Java book: A good Java reference (there may be others)– Don’t struggle Googling for features you don’t understand– Same book recommended for CSE331• Weeks 8-10 not in either book (or any appropriate one)– Will write and post more thorough lecture notes, etc.Spring 2010 7CSE332: Data AbstractionsCourse Work• 8 written/typed homeworks (25%)–Due at beginning of class each Friday (not this week)– No late homeworks accepted– Often covers through Monday before it’s due• 3 programming projects (with phases) (25%)– First phase of first project due in 9 days– Use Java and Eclipse (see this week’s section)– One 24-hour late-day for the quarter– Projects 2 and 3 will allow partners• Midterm Friday April 30 (20%)• Final Tuesday June 8 (25%)Spring 2010 8CSE332: Data AbstractionsCollaboration and Academic Integrity• Read the course policy very carefully– Explains quite clearly how you can and cannot get/provide help on homework and projects• Always explain any unconventional action on your part• Your instructor has promoted and enforced academic integrity since he was a freshman– Believes in great trust with little sympathy for violations– Honest work is the most important feature of a universitySpring 2010 9CSE332: Data AbstractionsUnsolicited advice• Get to class on time!– Instructor pet peeve (I will start and end promptly)– First 2 minutes are much more important than last 2!– April 30 will prove beyond any doubt you are capable• Learn this stuff– You need it for so many later classes/jobs anyway– Falling behind only makes more work for you• Embrace being a “charter member” of CSE332– Things may be a little rough around the edges– But we make up for it with excitement and a nice class sizeSpring 2010 10CSE332: Data AbstractionsToday in Class• Course mechanics – Did I forget anything?• What this course is about (“the new 326”)– And how it fits into the revised curriculum• Start stacks and queues (largely review)Spring 2010 11CSE332: Data AbstractionsLast word about 326• Many new courses have no one obvious counterpart in the old• But 332 is about 70% of the material from 326– First 7 weeks or so, obviously cutting out some topics • and a little moving to 312– Timeless, essential stuff– And a good chance to clean up some 326 “cruft”• Biggest new topic: a serious treatment of programming with multiple threads–For parallelism: To use multiple processors to finish sooner–For concurrency: Allow properly synchronized access to shared resourcesSpring 2010 12CSE332: Data AbstractionsWhere 332 fitsNote: This picture was the story of my life in 2009Spring 2010 13CSE332: Data AbstractionsOkay, so what is 332 about already!• 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 14CSE332: Data AbstractionsGoals• 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”