Where Are We?Data AbstractionIntroduction to SequencesArray InterfaceCS 311 Data Structures and AlgorithmsLecture SlidesFriday, October 23, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell23 Oct 2009 CS 311 Fall 2009 2Unit OverviewAlgorithmic Efficiency & SortingMajor Topics Introduction to Analysis of Algorithms Introduction to Sorting Comparison Sorts I More on Big-O The Limits of Sorting Divide-and-Conquer Comparison Sorts II Comparison Sorts III Radix Sort Sorting in the C++ STLDONE23 Oct 2009 CS 311 Fall 2009 3Where Are We?From the First Day of Class: Course Overview — GoalsAfter taking this class, you should: Have experience writing and documenting high-quality code. Understand how to write robust code with proper error handling. Be able to perform basic analyses of algorithmic efficiency, including use of “big-O” notation. Be familiar with various standard algorithms, including those for searching and sorting. Understand what data abstraction is, and how it relates to software design. Be familiar with standard data structures, including their implementations and relevant trade-offs.The rest of the semesterWe will also discuss this in more detail23 Oct 2009 CS 311 Fall 2009 4Where Are We?From the First Day of Class: Course Overview — TopicsThe following topics will be covered, roughly in order: Advanced C++ Software Engineering Concepts Recursion Searching Algorithmic Efficiency Sorting Data Abstraction Basic Abstract Data Types & Data Structures: Smart Arrays & Strings Linked Lists Stacks & Queues Trees (various types) Priority Queues Tables Other, as time permits: graph algorithms, external methods.Goal: Practical generic containersA container is a data structure holding multiple items, usually all the same type.A generic container is one that can hold objects of client-specified type.DONE23 Oct 2009 CS 311 Fall 2009 5Where Are We?The Big ProblemFor most of the rest of the semester, we will be addressing the following problem: We have a collection of data items, all of the same type, that we wish to store. We need to be able to access items [retrieve/find, traverse], add new items [insert] and eliminate items [delete]. All this needs to be efficient in both time and space.Solutions to this problem are called “containers”. There are many good ones. Which one we use depends on many factors, including what priority we place on the various requirements above.We are particularly interested in generic containers: containers in which client code can specify the type of data to be stored.23 Oct 2009 CS 311 Fall 2009 6Unit OverviewHandling Data & SequencesWe now begin a unit on handling data and implementing Sequence data.Major Topics Data abstraction Introduction to Sequences Smart arrays Array interface Basic array implementation Exception safety Allocation & efficiency Generic containers Linked Lists Node-based structures More on Linked Lists Sequences in the C++ STL Stacks QueuesSome material is in chapters 3, 4, 6, and 7 in the text.After this, we will look at trees.23 Oct 2009 CS 311 Fall 2009 7Data AbstractionAbstraction AgainAbstraction: Separate the purpose of a module from its implementation.We have been doing functional abstraction.Now we look at data abstraction.ModuleClientClientClient(defined by the specification)Implementation(hidden from clients andnot part of the abstraction)InterfaceRecall: Function, class, or other unit of code. Generally smaller than a package.23 Oct 2009 CS 311 Fall 2009 8Data AbstractionWhat is It?In data abstraction, we separate the various aspects of dealing with data, from the implementation of the data: The conceptual form of the data. The operations available on the data. The method used to access the data.Important concepts Abstract data type (ADT). Interface.23 Oct 2009 CS 311 Fall 2009 9Data AbstractionADTs, Data Structures, ClassesAbstract data type (ADT): a collection of data, along with a set of operations on that data.ADTs are independent of implementation, and even of programming language.Data structure: a construct within a programming language that stores a collection of data.C++ and some other programming languages include classes, which facilitate object-oriented programming. An important use of classes is the implementation of data structures, each of which is often conceptually based on some ADT. However, one can implement data structures without using classes.23 Oct 2009 CS 311 Fall 2009 10Data AbstractionADT ExampleSuppose we want to specify an ADT that holds exactly three pieces of information. We might call this ADT “Triple”. These are not assumed to be numeric or have any arithmetic properties at all. Rather, they are simply three pieces of data. Think of this as a list that always has size three.What operations might such an ADT have? The following were mentioned in class. Data access (get/set). Check equality. Reorder. Create. Destroy. Output.We might store the data for a Triple in an obvious data structure: threevariables.And we might implement all this using a class with three data members, and member functions implementing the various Triple operations.23 Oct 2009 CS 311 Fall 2009 11Data AbstractionGood InterfacesWhen we implement a data structure, the idea of abstraction requires that we have a well defined interface.Designing a good interface can be difficult. Here are some characteristics of a good interface.An interface should be complete. All required operations should be possible.We often strive for interfaces that are minimal. Avoid unnecessary functionality.An interface should be convenient. Avoid making the interface a pain to use.We want to facilitate efficiency. Allow the data to be dealt with efficiently.We often want our interface to be generic. Avoid restricting possible implementations and internal data types.These two often pull in opposite directions.These two canpull in opposite directions.23 Oct 2009 CS 311 Fall 2009 12Introduction to SequencesWhat is a Sequence?A Sequence is a collection of items that are in some order. We will restrict our attention to finite Sequences in which all items have the same type. It may help to think of an