Transcript Introduction (CB chap. 1 & 2)

Introduction
Ellen Walker
CPSC 201 Data Structures
Hiram College
Data Structures
• Toolkit for programmers
– Abstract Data Types: List, Queue, Stack, Tree,
Graph
– Algorithms to implement and use these types
• Practical Programming
– Larger programs than CS 172
– More “independence” in design
– Additional Java topics (exceptions, interfaces &
implementations, collections…)
– [ time management in programming ]
What we won’t cover
• In-depth analysis of algorithms related to data
structures
• Sorting and searching (except as it relates to
specific data structures)
• Advanced algorithms, especially those not
tied to data structures
• There is a 400-level course “Algorithms” that
deals with these topics in depth
Problem Solving
• Algorithm
– Step by step description of how to solve the
problem
– (Not enough by itself!)
• Data structure
– How the data is stored
– Organized so that you can “operate on it easily as
the algorithm requires”
• Must be coordinated!
Data Structures You’ve Used
• Array - collection of data, all of the same type,
accessible by index
• Class - collection of data of many types,
relating to a single object
– Classes also include methods (functions)
• String - sequence of characters
• Appendix A (Introduction to Java) should be a
review of material you learned in 172
Software Life Cycle Activities
•
•
•
•
•
•
Requirements
Analysis
Design
Implementation
Testing
(Maintenance)
Waterfall (unworkable!)
Requirements
Analysis
Design
Implementation
Testing
Unified Model
• Project developed in “iterations”
• Each iteration is a mini-waterfall
• Depending on “phase”, different activities are
emphasized
• Allows loops: requirement -> analysis ->
improve requirement -> more analysis ->
design ->improve analysis …
Unified Model Phases
• Inception
– Requirements, some Analysis
• Elaboration
– Requirements, Analysis, some Design & Testing
• Construction
– Design, Implementation, some Analysis, minimal
Requirements, increasing Testing
• Transition
– Testing, some Implementation
Requirements
• Finding out what the client really needs
• Generally a dialog with the client
• Result is specific enough to take forward to…
Analysis
• Evaluate alternative approaches and make
necessary decisions (e.g. off-the-shelf vs.
custom design)
• Refine requirements if necessary
Design
• Determine how the system will be organized
and broken down into smaller parts for
implementation
– Top-down
– Object-oriented
Design vs. Implementation
• Design
– Determine what the pieces are (abstractions)
– Determine how they fit together (interfaces)
• Implementation
– Translate pieces into (Java) code
• Develop Java interfaces
• Develop Java classes, including implementing algorithms
Abstraction
• Model of a physical entity or activity
• Emphasizes what we need; “abstracts away”
irrelevant complexity
• Different abstractions of the same entity for
different uses:
–
–
–
–
CAR, to a driver
CAR, to a mechanic
CAR, to a new-model designer
CAR, to an insurance agent
Procedural Abstraction
•
•
•
•
Separating what a method does …
…from how it does it
Example: system.out.println()
Another example (assuming methods do
what their names say):
Circle Sun = new Circle();
Sun.setColor(“yellow”);
Sun.draw();
Advantages of Procedural
Abstraction
• Reducing complexity
• Allowing code reuse
• Easy to improve all code by improving a
library method (as long as the what doesn’t
change)
– Example: substitute binary search for sequential
search to make directory lookups faster
Data Abstraction
• Separate the “logical view” of data from the “physical
view” of how it’s actually stored
• Example: number
– Logical view: the numeric value
– Physical view: binary 2’s complement or floating point
representation
• Example: list
– Logical view: sequence of elements
– Physical view: exactly how and where those elements are
stored, as well as any bookkeeping information
Advantages of Data Abstraction
• Same program can work on different
underlying architectures
• Programmer freed from dealing with
representation issues
– Except if they’re implementing the object itself
(such as Integer or Double)
Information Hiding
• Clients (higher-level objects) can access data
objects only through their methods
– Clock.set (“01:00”);
– Clock.addMinute(); //NOT Clock.minute++;
• Illegal representations impossible
• Changing implementations doesn’t break
existing code
Abstract Data Type
• An abstract data type (ADT) encapsulates all
relevant data items and methods
– Includes data and procedural abstraction
– Provides information hiding
– Allows for reusable code
ADT (data inside)
(public methods)
Interfaces & Implementations
• An interface is an abstract specification for an object
– Methods it provides
– Parameters those methods take
• An implementation is a class that includes methods
specified by the interface
• An instance is an actual object (created with new)
• A client is a “higher-level” program that uses the
implementation (knowing only the interface)
Interface: Light Bulb Socket
• Implementations (instances)
• Clients (instances)
Interface as Contract
• Interface designer specifies methods and
parameters (and what they mean)
• Implementor promises to implement all
specified methods
– Java compiler enforces this (to a point)
• Client must use methods as specified
– No knowledge of implementation
– Consider implementation can change tomorrow
Specifying What a Method Does
• Preconditions
– True before the method runs (assumptions)
– Example: “X is a positive number”
• Postconditions
– True after the method runs (results)
– Example: “Y = 2X”
• Contract
– IF preconditions are true before, THEN postconditions are
true after
– When preconditions are false, all bets are off!
Specification with Preconditions and
Postconditions
• Sort(anArray, num)
– Sorts an array into ascending order
– Precondition: anArray is an array of num integers
• Num is positive
• Num is less than the declared size of the array
(MAXARRAY)
– Postcondition: anArray is sorted into ascending
order , i.e anArray[0] <= anArray[1] <=
anArray[2]… <=anArray[num-1], elements beyond
num are not affected, and num is the same as
before…
If we use a list instead…
• Sort(aList)
– Sorts a vector into ascending order
– Precondition: aList is a list of objects that have a
value that can be compared (i.e. have a
compareTo method)
– Postcondition : aList is sorted into ascending order
, i.e each element is <= the following one
What about search?
• aSequence.Search (anItem)
– Precondition
– Postcondition
Documentation
• Write preconditions and postconditions as
part of your documentation
• You might as well write them first!
• They are a “contract” - if you know these
conditions, you can use a method without
even looking at its source code!
Conditions as Documentation
/** Process a bank account deposit
pre: amount is positive
post: Adds the specified amount to balance
*/
Public void processDeposit(double amt){
balance += amt;
}
Assertions
• Statements that must be true at a given point
in the code
• Preconditions & postconditions are special
cases
• Java provides “assert” function to test
assertions in the code
• Loop invariants are another kind of
assertion…
Assertions and Verification
• Goal: given precondition and algorithm,
prove the postcondition will happen
• Technique: work backwards step by step
from the postcondition, seeing what is
needed…
• Example: x=y+1, postcondition x=2
• Required precondition:
Loop invariant
• True before the loop begins (after
initialization)
• True before / after each iteration of the loop
• True after the loop terminates
• Usually, all variables that are changed by a
loop are included in its invariant.
Example:
• Code
int i=1
int x=2
while(i<n)
x+=x; i++;
• Invariant is:
• Postcondition is:
A Loop is Correct When…
1. The invariant is true before the loop.
2. The invariant is preserved through a single
execution of the loop.
3. If the invariant is true and the loop exited,
the postcondition is true.
4. The loop always terminates.
Using Invariants
• Determine invariants to understand existing
code
• Develop invariants during design
– Aid in correct initialization
– Aid in avoiding “off by one” errors
• Document invariants in code (especially
complex loops)