Transcript Notes for Lecture 1 (ppt file)

CS2468: Data Structures and Data Management
•
•
•
•
•
Lecturer: Lusheng Wang
Office: B6422
Phone: 3442 9820
E-mail [email protected]
TA (Assignment Marking and Tutorial)
– Chao SHEN [email protected] , Phone: 3442 2546
– Zicheng ZHAO [email protected]
Welcome to ask questions at ANY time.
• The course Website: Canvas
• Some Java Source code:
http://net3.datastructures.net/download.html
• The course Website:
Text Book: Michael T. Goodrich and Roberto Tamassia, Data Structure and
Algorithms in Java, John Wiley & Sons, Inc. 5th Edition
Stacks
1
Topics to be covered
• Analysis of Algorithms
– worst case time and space complexity
• Data Structures
– stack, queue, linked list, tree, priority queue, heap, hash, and graph,
• Searching algorithms
– binary and AVL search trees;
• Sorting algorithms
– merge sort, quick sort, bucket sort and radix sort; (Reduce some
contents)
• Graph
– data structure, depth first search and breadth first search. (add
some interesting contents).
• shortest path.
Stacks
2
Why This Course?
• You will be able to evaluate the quality of a
program (Analysis of Algorithms: Running time and
memory space )
• You will be able to write fast programs
• You will be able to solve new problems
• You will be able to give non-trivial methods to solve
problems.
(Your algorithm (program) will be faster than others.)
Stacks
3
Course Evaluations
• Course work: 30%
• Final Exam: 70%
• Course Work:
– Three assignments, 15%
– One quiz or lab test 3%
– One mid term exam 12%
Stacks
4
OBTL:
Course Intended Learning Outcomes
1.Describe the functionality of a data structure as an
abstract data type;
2.Implement an abstract data type in a programming
language;
3.Implement and test data structures for common
structures;
4.Select an appropriate data structure from a given set
of structures to solve a given problem;
5.Design and implement data storage management
with simple file structures.
Will be tested in quiz or assignment or midterm.
5
For each item, you have to
get 40% to pass.
Pre-requisites:
• CS2360 Java Programming /or
• Not known java?
– Spend the rest of 8-10 days to study Java.
– Read textbook p1-p53
– Design a class with two integers C1 and C2 and a method f() to
calculate the average value of c1 and c2.
– If you cannot do that, you should worry…
Stacks
6
• Data Structures
– A systematic way of organizing and accessing data.
--No single data structure works well for ALL purposes.
– Data stored
– operation on data
• Algorithms
– an effective method expressed as a finite list of well-defined
instructions for calculating a function.
– Algorithms are used for calculation, data processing, and automated
reasoning.
– In simple words an algorithm is a step-by-step procedure for
calculations.
Stacks
7
How to describe algorithm?
• Nature languages
– Chinese, English, etc.
– Not accurate.
• Pseudo-code
– Codes close to computer languages
• Omits details that are not essential for human understanding
– Intended for human reading rather than machine reading
• Programs
– C /C++ programs, Java programs.
• Pseudo-code is preferred
– Allow a well-trained programmer to be able to implement.
– Allow an expert to be able to analyze the running time.
Stacks
8
An Example of an Algorithm
Algorithm sorting(X, n)
Input array X of n integers
Output array X sorted in a nondecreasing order
Algorithm sorting(X, n)
Input array X of n integers
Output array X sorted in a nondecreasing order
for i  0 to n  1 do
for j  i+1 to n-1 do
for i from 0 to n  1 do
for j from i+1 to n-1 do
if X[i] is larger than X[j]
swap(X[i], X[j])
if (X[i]>X[j]) then
{ s=X[i];
X[i]=X[j];
X[j]=s;
}
return X
return X
// after i-th round, the i-th smallest
number is at i-th position.
// after i-th round, the i-th smallest
number is at i-th position.
Stacks
9
Variables, Primitives
• A variable has its value
– A type is associated,
• E.g., int, boolean, float, long, etc.
– A value is assigned to the variable
• The value is stored in the memory
• The size of the value is determined umbigously; 64 bit machine, int 8 bytes,
double 8 bytes, etc
– Examples
• int x;
• int y=50;
• char c, z=‘A’;
Stacks
10
Objects (extension of variables)
A class template
Class Name: Circle
Data Fields:
radius is _______
Methods:
getArea
Circle Object 1
Circle Object 2
Circle Object 3
Data Fields:
radius is 10
Data Fields:
radius is 25
Data Fields:
radius is 125
Three objects of
the Circle class
• An object has both a state and behavior.
•
State defines the object,
•
Behavior defines what the object does.
•
What is the size of an object in the memory?
11
Class
• Class defines
•
the type of an object
•
the kinds of operations that it performs.
• A Java class uses variables to define data fields
and methods to define behaviors.
• A class provides a special type of methods,
• known as constructors, which are invoked to
construct objects from the class.
12
Classes
class Circle {
/** The radius of this circle */
double radius = 1.0;
/** Construct a circle object */
Circle() {
}
Data field
Constructors
/** Construct a circle object */
Circle(double newRadius) {
radius = newRadius;
}
/** Return the area of this circle */
double getArea() {
return radius * radius * 3.14159;
}
}
13
Method
Class Diagram
Class name
Circle
UML Class Diagram
radius: double
Data fields
Circle()
Constructors and
Methods
Circle(newRadius: double)
getArea(): double
circle1: Circle
radius: 10
circle3: Circle
circle2: Circle
radius: 125
radius: 25
14
UML notation
for objects
State/attributes—variables
Operation/action – methods
Figure 2.3: Class
specification of Person
© 2003 Brooks/Cole Publishing / Thomson Learning™
15
Figure 2.7: Providing
methods to access the
attributes of Person
© 2003 Brooks/Cole Publishing / Thomson Learning™
16
Figure 2.8: An
Instance fred of the
Person class
© 2003 Brooks/Cole Publishing / Thomson Learning™
17
© 2003 Brooks/Cole Publishing / Thomson Learning™
Figure 2.9: Using the access methods
to set fred’s attributes
18
Constructors
Circle() {
}
Circle(double newRadius) {
radius = newRadius;
}
Constructors are a special
kind of methods that are
invoked to construct objects.
19
Constructors, cont.
A constructor with no parameters is referred to as a
no-arg constructor.
 Constructors must have the same name as the class
itself.
 Constructors do not have a return type—not even void.
 Constructors are invoked using the new operator when
an object is created. Constructors play the role of
initializing objects.
20
Creating Objects Using Constructors
new ClassName();
Example:
new Circle();
new Circle(5.0);
21
Declaring/Creating Objects
in a Single Step
ClassName objectRefVar = new ClassName();
Example:
Create an object
Assign object reference
Circle myCircle = new Circle();
22
Accessing Objects
• Referencing the object’s data:
objectRefVar.data
e.g., myCircle.radius
• Invoking the object’s method:
objectRefVar.methodName(arguments)
e.g., myCircle.getArea()
Show a complete program
C7-TestCircle1.html
23
Part-B1
Stacks (p198-p213)
Abstract Data Types (ADTs)
• Abstract data type • e.g. : ADT modeling a students
record
– an abstraction of a
data structure
– The data stored are
• An ADT specifies:
– Data stored
– Operations on the
data
– Error conditions
associated with
operations
• Student name, id, as1, as2,as3,
exam
– The operations supported are
• int averageAs(as1,as2,as3)
• Int finalMark(as1, as2,as3, exam) )
– Error conditions:
• Calculate the final mark for absent
student
Stacks
25
The Stack ADT (§5.1)
• The Stack ADT stores
arbitrary objects
• Insertions and deletions
follow the last-in first-out
(LIFO) scheme
• Main stack operations:
– push(object)
•
– object top()
• returns the last inserted
element without removing it
– integer size()
•
returns the number of
elements stored
– boolean isEmpty()
• indicates whether no
elements are stored
inserts an element
– object pop()
•
• Auxiliary stack operations:
removes and returns the last
inserted element
Stacks
26
Applications of Stacks
• Direct applications
– Undo sequence in a text editor
– Chain of method calls in the Java Virtual Machine
• Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
Stacks
27
Parentheses Matching
• An expression, i.e.,[(2+3)*x+5]*2.
• Each “(”, “{”, or “[” must be paired with a
matching “)”, “}”, or “[”
– correct:
• ( )(( )){([( )])}
• ((( )(( )){([( )])}))
– incorrect
•
•
•
•
)(( )){([( )])}(
({[ ])}
([)])
(
Stacks
28
Examples
Picture is from http://www.davesquared.net/2008/07/brackets-braces-parenthesis-and-other.html
Stacks
29
Examples
(
)
(
(
)
)
{
(
[
(
)
]
)
(
(
(
(
(
(
{
[
[
[
(
(
(
(
(
{
{
{
{
{
{
}
Examples
(
)
(
(
]
)
{
(
[
Mismatch!!!
(
(
(
(
(
(
)
]
)
}
Examples
(
)
(
(
)
)
{
(
[
)
]
)
}
Mismatch!!!
[
(
(
(
(
(
{
(
(
(
{
{
{
Examples
(
)
(
(
)
)
{
(
[
Mismatch!!!
(stack is non-empty)
[
(
(
(
(
(
{
(
(
{
{
Examples
(
)
(
(
)
)
)
Mismatch!!!
(pop empty stack)
(
(
(
(
(
Parentheses Matching Algorithm
Algorithm ParenMatch(X,n):
Input: An array X of n tokens, each of which is either a grouping symbol, a
variable, an arithmetic operator, or a number
Output: true if and only if all the grouping symbols in X match
Let S be an empty stack
for i=0 to n-1 do
if X[i] is an opening grouping symbol then
S.push(X[i])
else if X[i] is a closing grouping symbol then
if S.isEmpty() then
return false {nothing to match with}
if S.pop() does not match the type of X[i] then
return false {wrong type}
if S.isEmpty() then
return true {every symbol matched}
else
return false {some symbols were never matched}
Stacks
35
Parentheses Matching Example 1
• Input: () (() [()])
i
X[i]
Operation
Stack
0
(
Push (
1
)
Pop (
Test if ( and X[i] match?
(
YES
2
(
Push (
(
3
(
Push (
((
4
)
Pop (
Test if ( and X[i] match?
(
5
[
Output
Push [
YES
([
Stacks
36
Parentheses Matching Example 1
• Input: () (() [()])
i
X[i] Operation
Stack Output
6
(
Push (
([(
7
)
Pop (
Test if ( and X[i] match?
([
8
9
]
)
YES
Pop [
Test if [ and X[i] match?
YES
Pop (
Test if ( and X[i] match?
YES
Test if stack is Empty?
YES
Stacks
(
TRUE
37
Parentheses Matching Example 2
• Input: ( () [] ]()
i
X[i]
Operation
Stack
0
(
Push (
(
1
(
Push (
((
2
)
Pop (
Test if ( and X[i] match?
(
YES
3
[
Push [
([
4
]
Pop [
Test if [ and X[i] match?
(
YES
Pop (
Test if ( and X[i] match ?
NO
5
]
Stacks
Output
FASLE
38
Stack Interface in Java
• Java interface
corresponding to our
Stack ADT
• Requires the
definition of class
EmptyStackException
public interface Stack {
public int size();
public boolean isEmpty();
public Object top()
throws EmptyStackException;
public void push(Object o);
public Object pop()
throws EmptyStackException;
}
Stacks
39
Exceptions
• Attempting the
• In the Stack ADT,
execution of an
operations pop and top
operation of ADT may
cannot be performed if
sometimes cause an
the stack is empty
error condition, called
• Attempting the
an exception
execution of pop or top
• Exceptions are said to be
on an empty stack
“thrown” by an
throws an
operation that cannot
EmptyStackException
be executed
Stacks
40
Array-based Stack (Implementation)
• A simple way of
implementing the
Stack ADT uses an
array
• We add elements
from left to right
• A variable t keeps
track of the index of
the top element
Algorithm size()
return t + 1
Algorithm pop()
if isEmpty() then
throw EmptyStackException
else
tt1
return S[t + 1]
…
S
0 1 2
t
Stacks
41
Array-based Stack (cont.)
• The array storing the
stack elements may
become full
• A push operation will
then throw a
FullStackException
– Limitation of the arraybased implementation
– Not intrinsic to the Stack
ADT
Algorithm push(o)
if t = S.length  1 then
throw FullStackException
else
tt+1
S[t]  o
…
S
0 1 2
t
Stacks
42
Array-based Stack (Cont.)
• A Stack might be
empty
• top returns the
element at the top of
the Stack, but does
not remove the top
element. When the
Stack is empty, an
error occurs.
Algorithm isEmpty()
if t<0 then return true
else return false
Algorithm top()
if isEmpty() then
throw EmptyStackException
return S[t ]
…
S
0 1 2
t
Stacks
43