Course OverviewThe Structure of a PackageParameter PassingCS 311 Data Structures and AlgorithmsLecture SlidesFriday, September 4, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell4 Sep 2009 CS 311 Fall 2009 2Course OverviewCS 311 in the CompSci & CompEng ProgramsCS 311 has a dual role: It serves as “C.S. III”. CS 201 → CS 202 → CS 311 It introduces theoretical computer science (as opposed to programming, software engineering, etc.): Data Structures Representing data. Algorithms Dealing with data, accomplishing tasks. Analysis of Algorithms How good is an algorithm? Efficiency Making our programs run quickly.4 Sep 2009 CS 311 Fall 2009 3Course OverviewGoalsAfter 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.4 Sep 2009 CS 311 Fall 2009 4Course OverviewTopicsThe 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.4 Sep 2009 CS 311 Fall 2009 5Course OverviewTwo ThemesTwo themes will pop up over & over again this semester: Robustness Robust code is code that always behaves reasonably, no matter what input it is given. Not the same as reliability. Reliable code always does what you tell it to do. (But building reliable systems generally requires robust components.) Scalability Code, an algorithm, or a technique is scalable if it works well with increasingly large problems. Speed is the major issue here, of course.4 Sep 2009 CS 311 Fall 2009 6Course OverviewLanguageWe will achieve our goals, in part, by doing an in depth study of a particular programming language, along with its standard libraries. We will study ANSI C++ (1998 standard) and the Standard Template Library. Any reasonably recent C++ compiler should be fine. You may use the Chapman 103 Lab, which has C++ compilers available.“iostream.h”???Never heard of it.ANSI4 Sep 2009 CS 311 Fall 2009 7Course OverviewGeneric ProgrammingAn important topic in this class is generic programming. We write code so that it can handle arbitrary data types. We separate algorithms from data. Generic programming can make fancy data structures much more practical. In C++, generic programming is facilitated primarily by templates.Compare with object-oriented programming, covered in CS 202, which is facilitated primarily by inheritance and virtual dispatch.4 Sep 2009 CS 311 Fall 2009 8Unit OverviewAdvanced C++ & Software Engineering ConceptsWe now begin a unit on advanced C++ programming and software engineering concepts. Some of this will be review from CS 201/202. Most of this is not in the text. Later, we will follow the text more closely.Major TopicsLater in the semester we will cover other advanced C++ topics: Exception safety The C++ Standard Template Library Advanced C++ The structure of a package Parameter passing Operator overloading Silently written & called functions Pointers & dynamic allocation Managing resources in a class Templates Containers & iterators Error handling Introduction to exceptions Introduction to Linked Lists Software Engineering Concepts Abstraction Invariants Testing Some principlesThese two will be covered concurrently.4 Sep 2009 CS 311 Fall 2009 9The Structure of a PackageBasics [1/2]By a package we mean a program, library, or similar collection of code & related files that is distributed as a unit.A package may include: Documentation. Source code. Makefiles or other information on how to build. Pre-compiled files (libraries or executables). Data (images, etc.)In this class: We require API documentation. It will generally be written as comments in the code, not separate files. More on this in a couple of days. Files should be able to be compiled in the “normal” manner. Package files automatically generated by your favorite IDE should work. Nothing is precompiled. In short: Just give me the source, and put the doc’s in it.4 Sep 2009 CS 311 Fall 2009 10The Structure of a PackageBasics [2/2]“Module” is a general term for a smaller, self-contained collection of code: a function, class, etc. A client of a module is code that uses the module. The interface of a module is how clients deal with it. The implementation is how the module is written internally.Note: Here, a client is code; a user is a person.ModuleClientClientClientImplementationInterface4 Sep 2009 CS 311 Fall 2009 11The Structure of a PackageTypes [1/3]The type of a value or variable indicates the set of values it can take on and the operations available on it.Examples of C++ types: Simple types: int, double, char, long, etc. Pointers: pointer-to-int (int *), etc. Array-of-double …int n; // Declaration of variable of type int3 // Value of type int(3+n) // Expression whose value has type intA type conversion takes a value and returns a value of another type.int n = 3;double d1 = n; // Implicit conversion int to doubledouble d2 = double(n); // Two explicit conversionsdouble d3 = static_cast<double>(n) // None of these change n!4 Sep 2009 CS 311 Fall 2009 12The Structure of a PackageTypes [2/3]In C++, we can define our own types in three ways: Using class (or struct).class Foo { // Define a type called Foo…};Foo * myFooPtr; // Declare variable of type pointer-to-Foo Using typedef to create an “alias” for an existing