Transcript 01_Introduction

Data Structures and
Algorithms for Information
Processing
Lecture 1: Introduction
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
1
Course Web Site
• http://www.andrew.cmu.edu/~mm6
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
2
Structure of the Course
• Lectures / class participation
• Homeworks (programming)
• Midterm examination
• Final examination
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
3
Readings
• Readings from the required text
are assigned for each lecture -read them in advance
• The book contains self-test
exercises in each section
• Work these exercises (especially if
you are new to the material)
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
4
Grading
• Homework (5-6)
• Midterm Exam
• Final Exam
90-723: Data Structures
and Algorithms for
Information Processing
50%
25%
25%
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
5
Definitions
• A data structure is an organized
collection of data with specific
aggregate properties
• An algorithm is a sequence of
program instructions designed to
compute a particular result
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
6
Five Steps per Datatype
• Understand it Abstractly
• Write a Specification
• Write Applications
• Select an existing, or Design and
Implement our own
• Analyze the Implementation in
terms of performance
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
7
Abstract vs. Concrete
• An abstract data type (ADT)
specifies behavior, but not
implementation
• An implementation uses a
particular low-level datatype to
implement the desired behavior
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
8
Quick Example
• A stack is an abstract data type (ADT).
• We push and pop from the top.
• Consider three implementations:
(1) Every push causes all elements in an array to shift
down 1 before the insertion at s[0].
(2) We add at stackTop and then add one to stackTop.
(3) A linked list use where the top is always at the list’s
front end.
• Each implementation can be written correctly.
• Implementation (1) runs in Θ(n).
• Implementations (2) and (3) run in Θ(1).
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
9
Step 1: Understanding
• Grasp the datatype at the level of
concepts and pictures
e.g., visualize a stack and the
operations of pushing / popping
• Understand simple applications
• Simulate by hand
e.g., use a stack to reverse the
order of letters in a word
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
10
Step 2: Specification
• Write a specification for a Java
class that could implement the
datatype (see javadoc Appendix H)
• Headings for constructor, public
methods, public features
• Includes precondition /
postcondition for each method
• Independent of implementation!
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
11
Step 3: Application
• Based on the specification, write
small applications to illustrate the
use of the datatype
• “Test the specification” prior to
implementation
• Code not yet compiled / run
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
12
Step 4: Implementation
• Select appropriate data structure
• Implement as private class vars
• Write rules relating instance
variables to abstract specification:
the invariant of the ADT
• Each method knows the invariant
is true when it starts
• Each method upholds the invariant
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
13
Step 5: Analysis
• Correctness
• Flexibility
• When possible, compare different
implementations of the same ADT
• Time Analysis
– number of operations
– big-O notation, e.g.,
90-723: Data Structures
and Algorithms for
Information Processing
2
O(n )
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
14
Phases of Software
Development
• Specification of the Task
• Design of a Solution
• Implementation of the Solution
• Running Time Analysis
• Testing and Debugging
• Maintenance and Evolution
• Obsolescence
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
15
Java
•
•
•
•
Conceived in 1991 at Sun
Has Similarities to C++
Is simpler than C++
Object-Oriented Programming (OOP)
– information hiding
– component re-use
– programs (methods) and data are
grouped together into classes
– we will not be using the collection
classes
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
16
What You Should Know
Already
• How to use a Java development
environment (java, javac, javadoc)
• How to write, compile, and run
short Java programs
• Java primitive types (number
types, char, boolean) and arrays
• Easy to pick up with prior
programming experience
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
17
Specifying a Java Method
• Specification: what a method does
not how it does it
• A form of information hiding called
procedural abstraction
• Method signature
public static double celsiusToFahrenheit(double c)
• Method call
double fahrenheit = celsiusToFahrenheit(celsius);
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
18
Elements of Specification
• Short Introduction
• Parameter Description
• Returns
– Specify the meaning of return value
• Throws list
– error conditions (exceptions)
“thrown” by this method
• Precondition and Postcondition
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
19
Preconditions
• A precondition is a statement
giving the condition that should be
true when the method is called
• The method is not guaranteed to
perform as it should unless the
precondition is true.
• If violated, ignore (like c) or throw
an exception (like Java).
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
20
Postconditions
• A postcondition is a statement
describing what will be true when a
method call completes
• If the method is correct and
precondition was met, then the method
will complete, and the postcondition will
be true when it does
• Use Java assert statement for postcondition checks during debugging. Not
during deployment.
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
21
Example Specification
• celsiusToFahrenheit
public static double celsiusToFahrenheit(double c)
– convert a temperature from Celsius
degrees to Fahrenheit degrees
– Parameters:
c - a temperature in Celsius degrees
– Precondition: c>= -273.16
– Returns: temperature c in Fahrenheit
– Throws: IllegalArgument Exception
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
22
More on
Pre/Postconditions
• Slides from Main’s Lectures
90-723: Data Structures
and Algorithms for
Information Processing
Lecture 1: Introduction
Copyright © 1999, Carnegie Mellon. All Rights Reserved.
23