I. Preliminaries to the first meeting ------------------ WELCOME TO Com S 228 INTRODUCTION TO DATA STRUCTURES Professor Gary T. Leavens 229 Atanasoff Hall phone: 294-1580 email: leavens@cs.iastate.edu Office Hours: MTRF after class to noon 1. Pick up handouts (4 of them) ------------------ II. staff introductions III. The course itself A. What is a data structure? -------------------- DATA STRUCTURE def: a *data structure* is a representation for a collection of related information. -------------------- What are some examples from Scheme? --------------------- def: an *abstract data type* is a description of data and its behavior under certain operations. --------------------- What is an example of an ADT that is not a data structure? B. history C. objectives ---------------------- Com S 228 OBJECTIVES 1. working knowledge of data structures --------------------- ---------------------- 2. Understand ADTs and their importance ---------------------- -------------------- 3. develop your design/programming skills for programs of 100-500 lines --------------------- --------------------- 4. Understand information hiding 5. Use asymptotic notation in rough estimates of time and space complexity 6. Reason informally about correctness ---------------------- D. skills --------------------- SKILLS WE TEACH IN 228 + data modeling, informal specification, matching data structures to problems + implementation of abstract data types implementation data structures (pointers, references, arrays, ...) when to use them + algorithm analysis and efficiency + ability to communicate clearly to humans good style, modularization, data abstraction + design principles, using/building data abstractions, information hiding + imperative programming in C++ use of assignment, types, classes ------------------- E. syllabus 1. when 2. prerequisites --------------- PREREQUISITES Credit or enrollment in Math 165 Com S 227 SKILLS NEEDED FROM Com S 227 + Familiarity with computers and Unix logging in, commands, editing, etc. + data modeling + small algorithm coding and development case analysis, recursion, iteration + ability to communicate clearly to humans helping procedures, modularization, right level of detail (abstraction) + handling input and output + avoiding redundancy using/building functional abstractions + imperative programming use of vectors, assignment, mutation --------------- 3. what work is involved ---------------- ESTIMATED TIME NEEDED FOR HOMEWORK Average: about 14 hrs/week. Mode: more than 20 hrs/week. Range: 4 to more than 20 hrs/week. ADVICE ON TIME + try not to work the second 1/2 semester + if you work 20 hrs, only take 9 credits + if you work 12 hrs, only take 12 credits + don't take more than 16 credits with 228 ---------------- 4. texts ---------------- TEXTBOOKS Required: Data Abstraction and Structures with C++ Recommended: C++ How to Program ---------------- 5. grading ---------------- GRADING + No curve grading + Your grade is 2/3 based on tests 1/3 on homework ---------------- 6. ask for questions/concerns IV. Why C++? A. a misconception -------------------- A MISCONCEPTION C++ is not the point. The point is data structures. ------------------- B. our purpose -------------------------- SO WHY C++? support for ADTs you learn another paradigm -------------------------- C. how C++ helps ---------------------- HOW C++ HELPS low-level exposes more details support for ADTs (and object-oriented) in demand (currently) ---------------------- 1. exposing semantic details 2. object-oriented features 3. in demand D. problems of C++ -------------------------- PROBLEMS WITH C++ lots of detail unstable -------------------------- 1. lots of detail 2. unstable E. why not some other language? ------------------------- WHY NOT SOME OTHER LANGUAGE? Scheme no direct support for ADTs C no direct support for ADTs BASIC no direct support for ADTs Pascal no standard support for ADTs SML hides details, no text CLU hides details, little demand Modula-2 less demand (?), not OO Ada '83 less demand (?), not OO LISP hides details, not typed Modula-3 little demand, no text Eiffel little demand, not free Smalltalk hides details, not typed ------------------------- F. summary V. wrapping up the first class A. last minute reminders B. write most important point, what you'd like to hear more about VI. discussion of course policies -------------- FOR YOU TO DO In groups of 3 for 5 minutes: a. introduce yourselves b. write down at least 1 question about the red tape, course specification, or syllabus that you agree is confusing or you want to talk about c. select someone to ask the question(s) --------------