Comprehensive Overview of Midterm Review Topics in Data Structures and Object-Oriented Design
Midterm Review
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Data Structures So Far
Array List
(Extendable) Array
Node List
Singly or Doubly Linked List
Stack
Array
Singly Linked List
Queue
Array
Singly or Doubly Linked List
Priority Queue
Unsorted doubly-linked list
Sorted doubly-linked list
Heap (array-based)
Adaptable Priority Queue
Sorted doubly-linked list with location-
aware entries
Heap with location-aware entries
Tree
Linked Structure
Binary Tree
Linked Structure
Array
Topics on the Midterm
D
a
t
a
S
t
r
u
c
t
u
r
e
s
&
O
b
j
e
c
t
-
O
r
i
e
n
t
e
d
D
e
s
i
g
n
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Data Structures & Object-Oriented Design
Definitions
Principles of Object-Oriented Design
Hierarchical Design in Java
Abstract Data Types & Interfaces
Casting
Generics
Pseudo-Code
Software Engineering
Software must be:
Readable and understandable
Allows correctness to be verified, and software to be easily updated.
Correct and complete
Works correctly for all expected inputs
Robust
Capable of handling unexpected inputs.
Adaptible
All programs evolve over time. Programs should be designed so that re-use,
generalization and modification is easy.
Portable
Easily ported to new hardware or operating system platforms.
Efficient
Makes reasonable use of time and memory resources.
Seven Important Functions
Seven functions that often
appear in algorithm analysis:
Constant
≈
1
Logarithmic
≈ log
n
Linear
≈
n
N-Log-N
≈
n
log
n
Quadratic
≈
n
2
Cubic
≈
n
3
Exponential
≈
2
n
In a log-log chart, the slope of
the line corresponds to the
growth rate of the function.
Topics on the Midterm
Data Structures & Object-Oriented Design
R
u
n
-
T
i
m
e
A
n
a
l
y
s
i
s
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
p
r
o
p
e
r
t
i
e
s
o
f
l
o
g
a
r
i
t
h
m
s
:
log
b
(xy) = log
b
x + log
b
y
log
b
(x/y) = log
b
x - log
b
y
log
b
x
a
= alog
b
x
log
b
a = log
x
a/log
x
b
p
r
o
p
e
r
t
i
e
s
o
f
e
x
p
o
n
e
n
t
i
a
l
s
:
a
(b+c)
= a
b
a
c
a
bc
= (a
b
)
c
a
b
/a
c
= a
(b-c)
b = a
log
a
b
b
c
= a
c*log
a
b
Summations
Logarithms and Exponents
Existential and universal operators
Proof techniques
Basic probability
Some Math to Review
•
e
x
i
s
t
e
n
t
i
a
l
a
n
d
u
n
i
v
e
r
s
a
l
o
p
e
r
a
t
o
r
s
Definition of “Big Oh”
Arithmetic Progression
The running time of
prefixAverages1
is
O
(1
2
…
n
)
The sum of the first
n
integers is
n
(
n
1)
2
There is a simple visual
proof of this fact
Thus, algorithm
prefixAverages1
runs in
O
(
n
2
)
time
Relatives of Big-Oh
b
i
g
-
O
m
e
g
a
f(n) is
Ω(g(n)) if there is a constant c > 0
and an integer constant n
0
≥ 1 such that
f(n) ≥ c
•
g(n) for n ≥ n
0
b
i
g
-
T
h
e
t
a
f(n) is
Θ(g(n)) if there are constants c
1
> 0
and c
2
> 0 and an integer constant n
0
≥ 1
such that c
1
•
g(n) ≤ f(n) ≤ c
2
•
g(n) for n ≥ n
0
Time Complexity of an
Algorithm
O(n
2
):
For any
input size n ≥ n
0
, the algorithm takes
no more
than
cn
2
time on
every
input.
Ω(n
2
):
For any input size n ≥ n
0
, the algorithm takes
at
least
cn
2
time on
at least one
input.
θ (n
2
):
Do both.
The time complexity of an algorithm is
the
largest
time required on
any
input
of size n.
(Worst case analysis.)
Time Complexity of a
Problem
O(n
2
):
Provide
an
algorithm that solves the problem in no more than
this time.
Remember: for
every
input, i.e. worst case analysis!
Ω(n
2
):
Prove that
no
algorithm can solve it faster.
Remember: only need
one
input that takes at least this long!
θ (n
2
):
Do both.
The time complexity of a problem is
the time complexity of the
fastest
algorithm that solves the problem.
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
L
i
n
e
a
r
D
a
t
a
S
t
r
u
c
t
u
r
e
s
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Arrays
Arrays
Array: a sequence of indexed components with
the following properties:
a
r
r
a
y
s
i
z
e
i
s
f
i
x
e
d
a
t
t
h
e
t
i
m
e
o
f
a
r
r
a
y
’
s
c
o
n
s
t
r
u
c
t
i
o
n
i
n
t
[
]
n
u
m
b
e
r
s
=
n
e
w
i
n
t
[
1
0
]
;
a
r
r
a
y
e
l
e
m
e
n
t
s
a
r
e
p
l
a
c
e
d
c
o
n
t
i
g
u
o
u
s
l
y
i
n
m
e
m
o
r
y
address of any element can be calculated directly as its offset
from the beginning of the array
c
o
n
s
e
q
u
e
n
t
l
y
,
a
r
r
a
y
c
o
m
p
o
n
e
n
t
s
c
a
n
b
e
e
f
f
i
c
i
e
n
t
l
y
i
n
s
p
e
c
t
e
d
o
r
u
p
d
a
t
e
d
i
n
O
(
1
)
t
i
m
e
,
u
s
i
n
g
t
h
e
i
r
i
n
d
i
c
e
s
r
a
n
d
o
m
N
u
m
b
e
r
=
n
u
m
b
e
r
s
[
5
]
;
n
u
m
b
e
r
s
[
2
]
=
1
0
0
;
Arrays in Java
S
i
n
c
e
a
n
a
r
r
a
y
i
s
a
n
o
b
j
e
c
t
,
t
h
e
n
a
m
e
o
f
t
h
e
a
r
r
a
y
i
s
a
c
t
u
a
l
l
y
a
r
e
f
e
r
e
n
c
e
(
p
o
i
n
t
e
r
)
t
o
t
h
e
p
l
a
c
e
i
n
m
e
m
o
r
y
w
h
e
r
e
t
h
e
a
r
r
a
y
i
s
s
t
o
r
e
d
.
r
e
f
e
r
e
n
c
e
t
o
a
n
o
b
j
e
c
t
h
o
l
d
s
t
h
e
a
d
d
r
e
s
s
o
f
t
h
e
a
c
t
u
a
l
o
b
j
e
c
t
Example [ arrays as objects]
i
n
t
[
]
A
=
{1
2
,
2
4
,
3
7
,
5
3
,
6
7
}
;
i
n
t
[
]
B
=
A
;
B[3]=5;
Example [ cloning an array]
i
n
t
[
]
A
=
{1
2
,
2
4
,
3
7
,
5
3
,
6
7
}
;
i
n
t
[
]
B
=
A
.
c
l
o
n
e
(
)
;
B[3]=5;
A
B
A
B
A
B
A
B
Example
Example [ 2D array in Java = array of arrays]
i
n
t
[
]
[
]
n
u
m
s
=
n
e
w
i
n
t
[
5
]
[
4
]
;
i
n
t
[
]
[
]
n
u
m
s
;
n
u
m
s
=
n
e
w
i
n
t
[
5
]
[
]
;
f
o
r
(
i
n
t
i
=
0
;
i
<
5
;
i
+
+
)
{n
u
m
s
[
i
]
=
n
e
w
i
n
t
[
4
]
;
}
Array Lists
The Array List ADT (§6.1)
The
Array List
ADT extends the notion of array by storing
a sequence of arbitrary objects
An element can be accessed, inserted or removed by
specifying its rank (number of elements preceding it)
An exception is thrown if an incorrect rank is specified
(e.g., a negative rank)
The Array List ADT
p
u
b
l
i
c
i
n
t
e
r
f
a
c
e
I
n
d
e
x
L
i
s
t
<
E
>
{/** Returns the number of elements in this list */
p
u
b
l
i
c
i
n
t
s
i
z
e
(
)
;
/** Returns whether the list is empty. */
p
u
b
l
i
c
b
o
o
l
e
a
n
i
s
E
m
p
t
y
(
)
;
/** Inserts an element e to be at index I, shifting all elements after this. */
p
u
b
l
i
c
v
o
i
d
a
d
d
(
i
n
t
I
,
E
e
)
t
h
r
o
w
s
I
n
d
e
x
O
u
t
O
f
B
o
u
n
d
s
E
x
c
e
p
t
i
o
n
;
/** Returns the element at index I, without removing it. */
p
u
b
l
i
c
E
g
e
t
(
i
n
t
i
)
t
h
r
o
w
s
I
n
d
e
x
O
u
t
O
f
B
o
u
n
d
s
E
x
c
e
p
t
i
o
n
;
/** Removes and returns the element at index I, shifting the elements after this. */
p
u
b
l
i
c
E
r
e
m
o
v
e
(
i
n
t
i
)
t
h
r
o
w
s
I
n
d
e
x
O
u
t
O
f
B
o
u
n
d
s
E
x
c
e
p
t
i
o
n
;
/** Replaces the element at index I with e, returning the previous element at i. */
p
u
b
l
i
c
E
s
e
t
(
i
n
t
I
,
E
e
)
t
h
r
o
w
s
I
n
d
e
x
O
u
t
O
f
B
o
u
n
d
s
E
x
c
e
p
t
i
o
n
;
}
Performance
In the array based implementation
The space used by the data structure is
O
(
n
)
s
i
z
e
,
i
s
E
m
p
t
y
,
g
e
t
a
n
d
s
e
t
r
u
n
i
n
O
(
1
)
t
i
m
e
a
d
d
a
n
d
r
e
m
o
v
e
r
u
n
i
n
O
(
n
)
t
i
m
e
I
n
a
n
a
d
d
o
p
e
r
a
t
i
o
n
,
w
h
e
n
t
h
e
a
r
r
a
y
i
s
f
u
l
l
,
i
n
s
t
e
a
d
o
f
t
h
r
o
w
i
n
g
a
n
e
x
c
e
p
t
i
o
n
,
w
e
c
o
u
l
d
r
e
p
l
a
c
e
t
h
e
a
r
r
a
y
w
i
t
h
a
l
a
r
g
e
r
o
n
e
.
I
n
f
a
c
t
j
a
v
a
.
u
t
i
l
.
A
r
r
a
y
L
i
s
t
i
m
p
l
e
m
e
n
t
s
t
h
i
s
A
D
T
u
s
i
n
g
e
x
t
e
n
d
a
b
l
e
a
r
r
a
y
s
t
h
a
t
d
o
j
u
s
t
t
h
i
s
.
Doubling Strategy Analysis
We replace the array
k
=
log
2
n
times
T
h
e
t
o
t
a
l
t
i
m
e
T
(
n
)
o
f
a
s
e
r
i
e
s
o
f
n
a
d
d
(
o
)
o
p
e
r
a
t
i
o
n
s
i
s
p
r
o
p
o
r
t
i
o
n
a
l
t
o
n
+
1 + 2 + 4 + 8 + …+ 2
k
=
n
2
k
+ 1
1
=
2
n
1
Thus
T
(
n
)
is
O
(
n
)
T
h
e
a
m
o
r
t
i
z
e
d
t
i
m
e
o
f
a
n
a
d
d
o
p
e
r
a
t
i
o
n
i
s
O
(
1
)
!
Stacks
Chapter 5.1
The Stack ADT
The
Stack
ADT stores
arbitrary objects
Insertions and deletions
follow the last-in first-out
scheme
Think of a spring-loaded
plate dispenser
Main stack operations:
push
(object): inserts an
element
object
pop
(): removes and
returns the last inserted
element
Auxiliary stack
operations:
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
Array-based Stack
A simple way of
implementing the
Stack ADT uses an
array
We add elements
from left to right
A variable keeps
track of the index of
the top element
S
0
1
2
t
…
Algorithm
size
()
return
t
+
1
Algorithm
pop
()
if
isEmpty
()
then
throw
EmptyStackException
else
t
t
-
1
return
S
[
t
+
1]
Queues
Chapters 5.2-5.3
Array-Based Queue
Use an array of size
N
in a circular fashion
Two variables keep track of the front and rear
f
index of the front element
r
index immediately past the rear element
Array location
r
is kept empty
normal configuration
wrapped-around configuration
Queue Operations
We use the
modulo operator
(remainder of
division)
Algorithm
size
()
return
(
N
f
+
r
) mod
N
Algorithm
isEmpty
()
return
(
f
r
)
Linked Lists
Chapters 3.2 – 3.3
Singly Linked List (
§ 3.2)
A singly linked list is a
concrete data structure
consisting of a sequence
of nodes
Each node stores
element
link to the next node
next
elem
node
A
B
C
D
Running Time
Adding at the head is O(1)
Removing at the head is O(1)
H
o
w
a
b
o
u
t
t
a
i
l
o
p
e
r
a
t
i
o
n
s
?
Doubly Linked List
Doubly-linked lists allow more flexible list management (constant
time operations at both ends).
Nodes store:
element
link to the previous node
link to the next node
Special trailer and header (sentinel) nodes
prev
next
elem
trailer
header
nodes/positions
elements
node
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
T
h
e
J
a
v
a
C
o
l
l
e
c
t
i
o
n
s
F
r
a
m
e
w
o
r
k
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Iterators
An
Iterator
is an object that enables you to traverse
through a collection and to remove elements from the
collection selectively, if desired.
You get an Iterator for a collection by calling its iterator
method.
S
u
p
p
o
s
e
c
o
l
l
e
c
t
i
o
n
i
s
a
n
i
n
s
t
a
n
c
e
o
f
a
C
o
l
l
e
c
t
i
o
n
.
T
h
e
n
t
o
p
r
i
n
t
o
u
t
e
a
c
h
e
l
e
m
e
n
t
o
n
a
s
e
p
a
r
a
t
e
l
i
n
e
:
I
t
e
r
a
t
o
r
<
E
>
i
t
=
c
o
l
l
e
c
t
i
o
n
.
i
t
e
r
a
t
o
r
(
)
;
w
h
i
l
e
(
i
t
.
h
a
s
N
e
x
t
(
)
)
S
y
s
t
e
m
.
o
u
t
.
p
r
i
n
t
l
n
(
i
t
.
n
e
x
t
(
)
)
;
Interface
Abstract Class
Class
The Java Collections Framework (Ordered Data Types)
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
R
e
c
u
r
s
i
o
n
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Linear Recursion Design Pattern
T
e
s
t
f
o
r
b
a
s
e
c
a
s
e
s
Begin by testing for a set of base cases (there should be at least
one).
E
v
e
r
y
p
o
s
s
i
b
l
e
c
h
a
i
n
o
f
r
e
c
u
r
s
i
v
e
c
a
l
l
s
m
u
s
t
e
v
e
n
t
u
a
l
l
y
r
e
a
c
h
a
b
a
s
e
c
a
s
e
,
a
n
d
t
h
e
h
a
n
d
l
i
n
g
o
f
e
a
c
h
b
a
s
e
c
a
s
e
s
h
o
u
l
d
n
o
t
u
s
e
r
e
c
u
r
s
i
o
n
.
R
e
c
u
r
s
e
o
n
c
e
Perform a single recursive call. (This recursive step may involve
a test that decides which of several possible recursive calls to
make, but it should ultimately choose to make just one of these
calls each time we perform this step.)
D
e
f
i
n
e
e
a
c
h
p
o
s
s
i
b
l
e
r
e
c
u
r
s
i
v
e
c
a
l
l
s
o
t
h
a
t
i
t
m
a
k
e
s
p
r
o
g
r
e
s
s
t
o
w
a
r
d
s
a
b
a
s
e
c
a
s
e
.
Binary Recursion
B
i
n
a
r
y
r
e
c
u
r
s
i
o
n
o
c
c
u
r
s
w
h
e
n
e
v
e
r
t
h
e
r
e
a
r
e
t
w
o
r
e
c
u
r
s
i
v
e
c
a
l
l
s
f
o
r
e
a
c
h
n
o
n
-
b
a
s
e
c
a
s
e
.
E
x
a
m
p
l
e
1
:
T
h
e
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
Formal Definition of Rooted Tree
A rooted tree may be empty.
Otherwise, it consists of
A
r
o
o
t
n
o
d
e
r
A
s
e
t
o
f
s
u
b
t
r
e
e
s
w
h
o
s
e
r
o
o
t
s
a
r
e
t
h
e
c
h
i
l
d
r
e
n
o
f
r
subtree
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
T
r
e
e
s
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
subtree
Tree Terminology
R
o
o
t
:
n
o
d
e
w
i
t
h
o
u
t
p
a
r
e
n
t
(
A
)
I
n
t
e
r
n
a
l
n
o
d
e
:
n
o
d
e
w
i
t
h
a
t
l
e
a
s
t
o
n
e
c
h
i
l
d
(
A
,
B
,
C
,
F
)
E
x
t
e
r
n
a
l
n
o
d
e
(
a
.
k
.
a
.
l
e
a
f
)
:
n
o
d
e
w
i
t
h
o
u
t
c
h
i
l
d
r
e
n
(
E
,
I
,
J
,
K
,
G
,
H
,
D
)
A
n
c
e
s
t
o
r
s
o
f
a
n
o
d
e
:
p
a
r
e
n
t
,
g
r
a
n
d
p
a
r
e
n
t
,
g
r
a
n
d
-
g
r
a
n
d
p
a
r
e
n
t
,
e
t
c
.
D
e
s
c
e
n
d
a
n
t
o
f
a
n
o
d
e
:
c
h
i
l
d
,
g
r
a
n
d
c
h
i
l
d
,
g
r
a
n
d
-
g
r
a
n
d
c
h
i
l
d
,
e
t
c
.
S
i
b
l
i
n
g
s
:
t
w
o
n
o
d
e
s
h
a
v
i
n
g
t
h
e
s
a
m
e
p
a
r
e
n
t
D
e
p
t
h
o
f
a
n
o
d
e
:
n
u
m
b
e
r
o
f
a
n
c
e
s
t
o
r
s
(
e
x
c
l
u
d
i
n
g
s
e
l
f
)
H
e
i
g
h
t
o
f
a
t
r
e
e
:
m
a
x
i
m
u
m
d
e
p
t
h
o
f
a
n
y
n
o
d
e
(
3
)
S
u
b
t
r
e
e
:
t
r
e
e
c
o
n
s
i
s
t
i
n
g
o
f
a
n
o
d
e
a
n
d
i
t
s
d
e
s
c
e
n
d
a
n
t
s
Position ADT
The
Position
ADT models the notion of place
within a data structure where a single object is
stored
It gives a unified view of diverse ways of storing
data, such as
a cell of an array
a node of a linked list
a node of a tree
Just one method:
object
element
(): returns the element stored at the
position
Tree ADT
We use positions to abstract nodes
Generic methods:
integer
size
()
boolean
isEmpty
()
Iterator
iterator
()
Iterable
positions
()
Accessor methods:
position
root
()
position
parent
(p)
positionIterator
children
(p)
Query methods:
boolean
isInternal
(p)
boolean
isExternal
(p)
boolean
isRoot
(p)
Update method:
object
replace
(p, o)
Additional update methods may
be defined by data structures
implementing the Tree ADT
Preorder Traversal
A traversal visits the nodes of a
tree in a systematic manner
In a preorder traversal, a node is
visited before its descendants
Make Money Fast!
1. Motivations
References
2. Methods
2.1 Stock
Fraud
2.2 Ponzi
Scheme
1.1 Greed
1.2 Avidity
2.3 Bank
Robbery
1
2
3
5
4
6
7
8
9
A
l
g
o
r
i
t
h
m
p
r
e
O
r
d
e
r
(
v
)
v
i
s
i
t
(
v
)
f
o
r
e
a
c
h
c
h
i
l
d
w
o
f
v
p
r
e
O
r
d
e
r
(
w
)
Postorder Traversal
In a postorder traversal, a
node is visited after its
descendants
A
l
g
o
r
i
t
h
m
p
o
s
t
O
r
d
e
r
(
v
)
f
o
r
e
a
c
h
c
h
i
l
d
w
o
f
v
p
o
s
t
O
r
d
e
r
(
w
)
v
i
s
i
t
(
v
)
cs16/
homeworks/
todo.txt
1K
programs/
DDR.java
10K
Stocks.java
25K
h1c.doc
3K
h1nc.doc
2K
Robot.java
20K
9
3
1
7
2
4
5
6
8
Properties of Proper Binary Trees
Notation
n
n
u
m
b
e
r
o
f
n
o
d
e
s
e
n
u
m
b
e
r
o
f
e
x
t
e
r
n
a
l
n
o
d
e
s
i
n
u
m
b
e
r
o
f
i
n
t
e
r
n
a
l
n
o
d
e
s
h
h
e
i
g
h
t
Properties:
e = i + 1
n = 2e - 1
h ≤ i
h ≤ (n - 1)/2
e ≤ 2
h
h ≥ log
2
e
h ≥ log
2
(n + 1) - 1
BinaryTree ADT
The BinaryTree ADT extends the Tree ADT,
i.e., it inherits all the methods of the Tree ADT
Additional methods:
p
o
s
i
t
i
o
n
l
e
f
t
(
p
)
p
o
s
i
t
i
o
n
r
i
g
h
t
(
p
)
b
o
o
l
e
a
n
h
a
s
L
e
f
t
(
p
)
b
o
o
l
e
a
n
h
a
s
R
i
g
h
t
(
p
)
Update methods may be defined by data
structures implementing the BinaryTree ADT
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
P
r
i
o
r
i
t
y
Q
u
e
u
e
s
&
H
e
a
p
s
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Priority Queue ADT
A
p
r
i
o
r
i
t
y
q
u
e
u
e
s
t
o
r
e
s
a
c
o
l
l
e
c
t
i
o
n
o
f
e
n
t
r
i
e
s
E
a
c
h
e
n
t
r
y
i
s
a
p
a
i
r
(
k
e
y
,
v
a
l
u
e
)
Main methods of the Priority Queue ADT
i
n
s
e
r
t
(
k
,
x
)
i
n
s
e
r
t
s
a
n
e
n
t
r
y
w
i
t
h
k
e
y
k
a
n
d
v
a
l
u
e
x
r
e
m
o
v
e
M
i
n
(
)
r
e
m
o
v
e
s
a
n
d
r
e
t
u
r
n
s
t
h
e
e
n
t
r
y
w
i
t
h
s
m
a
l
l
e
s
t
k
e
y
Additional methods
m
i
n
(
)
r
e
t
u
r
n
s
,
b
u
t
d
o
e
s
n
o
t
r
e
m
o
v
e
,
a
n
e
n
t
r
y
w
i
t
h
s
m
a
l
l
e
s
t
k
e
y
s
i
z
e
(
)
,
i
s
E
m
p
t
y
(
)
Applications:
Process scheduling
Standby flyers
Entry ADT
A
n
e
n
t
r
y
i
n
a
p
r
i
o
r
i
t
y
q
u
e
u
e
i
s
s
i
m
p
l
y
a
k
e
y
-
v
a
l
u
e
p
a
i
r
Methods:
k
e
y
(
)
:
r
e
t
u
r
n
s
t
h
e
k
e
y
f
o
r
t
h
i
s
e
n
t
r
y
v
a
l
u
e
(
)
:
r
e
t
u
r
n
s
t
h
e
v
a
l
u
e
f
o
r
t
h
i
s
e
n
t
r
y
As a Java interface:
/**
* Interface for a key-value
* pair entry
**/
p
u
b
l
i
c
i
n
t
e
r
f
a
c
e
E
n
t
r
y
{p
u
b
l
i
c
O
b
j
e
c
t
k
e
y
(
)
;
p
u
b
l
i
c
O
b
j
e
c
t
v
a
l
u
e
(
)
;
}
Comparator ADT
A comparator encapsulates the action of comparing two
objects according to a given total order relation
A generic priority queue uses an auxiliary comparator
The comparator is external to the keys being compared
When the priority queue needs to compare two keys, it
uses its comparator
The primary method of the Comparator ADT:
c
o
m
p
a
r
e
(
a
,
b
)
:
Returns an integer
i
such that
i <
0 if
a < b
i
= 0 if
a
=
b
i >
0 if
a > b
an error occurs if
a
and
b
cannot be compared.
Sequence-based Priority Queue
Implementation with an
unsorted list
Performance:
i
n
s
e
r
t
t
a
k
e
s
O
(
1
)
t
i
m
e
s
i
n
c
e
w
e
c
a
n
i
n
s
e
r
t
t
h
e
i
t
e
m
a
t
t
h
e
b
e
g
i
n
n
i
n
g
o
r
e
n
d
o
f
t
h
e
s
e
q
u
e
n
c
e
r
e
m
o
v
e
M
i
n
a
n
d
m
i
n
t
a
k
e
O
(
n
)
t
i
m
e
s
i
n
c
e
w
e
h
a
v
e
t
o
t
r
a
v
e
r
s
e
t
h
e
e
n
t
i
r
e
s
e
q
u
e
n
c
e
t
o
f
i
n
d
t
h
e
s
m
a
l
l
e
s
t
k
e
y
Implementation with a
sorted list
Performance:
i
n
s
e
r
t
t
a
k
e
s
O
(
n
)
t
i
m
e
s
i
n
c
e
w
e
h
a
v
e
t
o
f
i
n
d
t
h
e
r
i
g
h
t
p
l
a
c
e
t
o
i
n
s
e
r
t
t
h
e
i
t
e
m
r
e
m
o
v
e
M
i
n
a
n
d
m
i
n
t
a
k
e
O
(
1
)
t
i
m
e
,
s
i
n
c
e
t
h
e
s
m
a
l
l
e
s
t
k
e
y
i
s
a
t
t
h
e
b
e
g
i
n
n
i
n
g
I
s
t
h
i
s
t
r
a
d
e
o
f
f
i
n
e
v
i
t
a
b
l
e
?
Heaps
Goal:
O(log n) insertion
O(log n) removal
Remember that O(log n) is almost as good as O(1)!
e.g., n = 1,000,000,000
log n
≅
30
There are min heaps and max heaps. We will assume
min heaps.
Min Heaps
A min heap is a binary tree storing keys at its nodes and
satisfying the following properties:
Heap-order:
for every internal node v other than the root
key
(
v
)
≥
key
(
parent
(
v
))
(Almost) complete binary tree:
let
h
be the height of the heap
for
i
0, … ,
h
1,
there are
2
i
nodes of depth
i
at depth
h
–
1
the internal nodes are to the left of the external nodes
Only the rightmost internal node may have a single child
2
6
5
7
9
T
h
e
l
a
s
t
n
o
d
e
o
f
a
h
e
a
p
i
s
t
h
e
r
i
g
h
t
m
o
s
t
n
o
d
e
o
f
d
e
p
t
h
h
Upheap
After the insertion of a new key
k
, the heap-order property may be
violated
A
l
g
o
r
i
t
h
m
u
p
h
e
a
p
r
e
s
t
o
r
e
s
t
h
e
h
e
a
p
-
o
r
d
e
r
p
r
o
p
e
r
t
y
b
y
s
w
a
p
p
i
n
g
k
a
l
o
n
g
a
n
u
p
w
a
r
d
p
a
t
h
f
r
o
m
t
h
e
i
n
s
e
r
t
i
o
n
n
o
d
e
U
p
h
e
a
p
t
e
r
m
i
n
a
t
e
s
w
h
e
n
t
h
e
k
e
y
k
r
e
a
c
h
e
s
t
h
e
r
o
o
t
o
r
a
n
o
d
e
w
h
o
s
e
p
a
r
e
n
t
h
a
s
a
k
e
y
s
m
a
l
l
e
r
t
h
a
n
o
r
e
q
u
a
l
t
o
k
S
i
n
c
e
a
h
e
a
p
h
a
s
h
e
i
g
h
t
O
(
l
o
g
n
)
,
u
p
h
e
a
p
r
u
n
s
i
n
O
(
l
o
g
n
)
t
i
m
e
2
1
5
7
9
6
1
2
5
7
9
6
Downheap
After replacing the root key with the key
k
of the last node, the
heap-order property may be violated
Algorithm downheap restores the heap-order property by
swapping key
k
along a downward path from the root
Note that there are, in general, many possible downward paths –
which one do we choose?
?
?
Downheap
W
e
s
e
l
e
c
t
t
h
e
d
o
w
n
w
a
r
d
p
a
t
h
t
h
r
o
u
g
h
t
h
e
m
i
n
i
m
u
m
-
k
e
y
n
o
d
e
s
.
Downheap terminates when key
k
reaches a leaf or a node whose
children have keys greater than or equal to
k
Since a heap has height
O
(log
n
)
, downheap runs in
O
(log
n
)
time
7
6
5
9
w
5
6
7
9
w
Array-based Heap Implementation
We can represent a heap with
n
keys
by means of an array of length
n
1
Links between nodes are not explicitly
stored
The cell at rank
0
is not used
The root is stored at rank 1.
For the node at rank
i
the left child is at rank
2
i
the right child is at rank
2
i
1
t
h
e
p
a
r
e
n
t
i
s
a
t
r
a
n
k
f
l
o
o
r
(
i
/
2
)
if 2i + 1 > n, the node has no right child
if 2i > n, the node is a leaf
2
6
5
7
9
We can construct a heap
storing
n
keys using a
bottom-up construction with
log
n
phases
In phase
i
, pairs of heaps
with
2
i
1
keys are merged
into heaps with
2
i
1
1
keys
R
u
n
t
i
m
e
f
o
r
c
o
n
s
t
r
u
c
t
i
o
n
i
s
O
(
n
)
.
Bottom-up Heap Construction
2
i
1
1
Adaptable
Priority Queues
Additional Methods of the Adaptable Priority Queue ADT
remove
(
e
): Remove from
P
and return entry
e
.
replaceKey
(
e,k
): Replace with
k
and return the old key
;
an error condition occurs if
k
is invalid (that is,
k
cannot
be compared with other keys).
replaceValue
(
e,x
): Replace with
x
and return the old
value.
Location-Aware Entries
A locator-aware entry identifies and tracks the
location of its (key, value) object within a data
structure
List Implementation
A location-aware list entry is an object storing
key
value
position (or rank) of the item in the list
In turn, the position (or array cell) stores the entry
Back pointers (or ranks) are updated during swaps
trailer
header
nodes/positions
entries
2
c
4
a
5
d
8
b
Heap Implementation
A location-aware heap
entry is an object storing
key
value
position of the entry in the
underlying heap
In turn, each heap position
stores an entry
Back pointers are updated
during entry swaps
4
a
2
d
6
b
8
g
5
e
9
c
Performance
Times better than those achievable without location-aware
entries are highlighted in
red
:
Method
Unsorted List
Sorted List
Heap
size, isEmpty
O
(1)
O
(1)
O
(1)
insert
O
(1)
O
(
n
)
O
(log
n
)
min
O
(
n
)
O
(1)
O
(1)
removeMin
O
(
n
)
O
(1)
O
(log
n
)
remove
O
(1)
O
(1)
O
(log
n
)
replaceKey
O
(1)
O
(
n
)
O
(log
n
)
replaceValue
O
(1)
O
(1)
O
(1)
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
M
a
p
s
,
H
a
s
h
T
a
b
l
e
s
&
D
i
c
t
i
o
n
a
r
i
e
s
Iterative Algorithms & Loop Invariants
Maps
A map models a searchable collection of key-value
entries
The main operations of a map are for searching,
inserting, and deleting items
M
u
l
t
i
p
l
e
e
n
t
r
i
e
s
w
i
t
h
t
h
e
s
a
m
e
k
e
y
a
r
e
n
o
t
a
l
l
o
w
e
d
Applications:
address book
student-record database
Performance of a List-Based Map
Performance:
put, get
and
remove
take
O
(
n
)
time since in the worst case
(the item is not found) we traverse the entire sequence to
look for an item with the given key
The unsorted list implementation is effective only for
small maps
Hash Tables
A hash table is a data structure that can be used to
make map operations faster.
While worst-case is still O(n), average case is typically
O(1).
Polynomial Hash Codes
Polynomial accumulation
:
We partition the bits of the key into a sequence of components of fixed
length (e.g., 8, 16 or 32 bits)
a
0
a
1
…
a
n
1
We evaluate the polynomial
p
(
z
)
a
0
a
1
z
a
2
z
2
…
a
n
1
z
n
1
at a fixed value
z
, ignoring overflows
Especially suitable for strings
Polynomial
p
(
z
)
can be evaluated in
O
(
n
)
time using Horner’s rule:
The following polynomials are successively computed, each from the previous
one in
O
(1)
time
p
0
(
z
)
a
n
1
p
i
(
z
)
a
n
i
1
zp
i
1
(
z
) (
i
1, 2, …,
n
1)
We have
p
(
z
)
p
n
1
(
z
)
Compression Functions
Division
:
h
2
(
y
)
y
mod
N
The size
N
of the hash table is usually chosen to be a prime (on
the assumption that the differences between hash keys
y
are
less likely to be multiples of primes).
Multiply, Add and Divide (MAD)
:
h
2
(
y
)
(
ay
b
)
mod p] mod N
, where
p is a prime number greater than N
a
and
b
are integers chosen at random from the interval [0, p – 1],
with a > 0.
Collision Handling
Collisions occur when different elements are mapped to
the same cell
S
e
p
a
r
a
t
e
C
h
a
i
n
i
n
g
:
Let each cell in the table point to a linked list of entries that map
there
Separate chaining is simple, but requires additional memory
outside the table
Open Addressing: Linear Probing
O
p
e
n
a
d
d
r
e
s
s
i
n
g
:
t
h
e
c
o
l
l
i
d
i
n
g
i
t
e
m
i
s
p
l
a
c
e
d
i
n
a
d
i
f
f
e
r
e
n
t
c
e
l
l
o
f
t
h
e
t
a
b
l
e
L
i
n
e
a
r
p
r
o
b
i
n
g
h
a
n
d
l
e
s
c
o
l
l
i
s
i
o
n
s
b
y
p
l
a
c
i
n
g
t
h
e
c
o
l
l
i
d
i
n
g
i
t
e
m
i
n
t
h
e
n
e
x
t
(
c
i
r
c
u
l
a
r
l
y
)
a
v
a
i
l
a
b
l
e
t
a
b
l
e
c
e
l
l
Each table cell inspected is
referred to as a “probe”
Colliding items lump together, so
that future collisions cause a longer
sequence of probes
Example:
h
(
x
)
x
mod
13
Insert keys 18, 41, 22, 44,
59, 32, 31, 73, in this order
0
1
2
3
4
5
6
7
8
9
10
11
12
41
18
44
59
32
22
31
73
Open Addressing: Double Hashing
D
o
u
b
l
e
h
a
s
h
i
n
g
i
s
a
n
a
l
t
e
r
n
a
t
i
v
e
o
p
e
n
a
d
d
r
e
s
s
i
n
g
m
e
t
h
o
d
t
h
a
t
u
s
e
s
a
s
e
c
o
n
d
a
r
y
h
a
s
h
f
u
n
c
t
i
o
n
h
’
(
k
)
i
n
a
d
d
i
t
i
o
n
t
o
t
h
e
p
r
i
m
a
r
y
h
a
s
h
f
u
n
c
t
i
o
n
h
(
x
)
.
Suppose that the primary hashing i=h(k) leads to a collision.
We then iteratively probe the locations
(
i
+
jh’
(
k
)) mod
N
for
j
= 0, 1, … ,
N
- 1
The secondary hash function
h’
(
k
)
cannot have zero values
N
is typically chosen to be prime.
Common choice of secondary hash function h’(k):
h’(k
) =
q
-
k
mod
q,
where
q
<
N
q
is a prime
The possible values for
h’
(
k
)
are
1, 2, … ,
q
Dictionary ADT
The dictionary ADT models a
searchable collection of key-
element entries
The main operations of a
dictionary are searching,
inserting, and deleting items
M
u
l
t
i
p
l
e
i
t
e
m
s
w
i
t
h
t
h
e
s
a
m
e
k
e
y
a
r
e
a
l
l
o
w
e
d
Applications:
word-definition pairs
credit card authorizations
Dictionary ADT methods:
get
(k): if the dictionary has at
least one entry with key k,
returns one of them, else, returns
null
getAll
(k): returns an iterable
collection of all entries with key k
put
(k, v): inserts and returns the
entry (k, v)
remove
(e): removes and returns
the entry e. Throws an exception
if the entry is not in the
dictionary.
entrySet
(): returns an iterable
collection of the entries in the
dictionary
size
(),
isEmpty
()
A List-Based Dictionary
A log file or audit trail is a dictionary implemented by means of an
unsorted sequence
We store the items of the dictionary in a sequence (based on a doubly-
linked list or array), in arbitrary order
Performance:
insert
takes
O
(1)
time since we can insert the new item at the beginning or
at the end of the sequence
find
and
remove
take
O
(
n
)
time since in the worst case (the item is not
found) we traverse the entire sequence to look for an item with the given
key
The log file is effective only for dictionaries of small size or for
dictionaries on which insertions are the most common operations, while
searches and removals are rarely performed (e.g., historical record of
logins to a workstation)
Hash Table Implementation
We can also create a hash-table dictionary
implementation.
If we use separate chaining to handle collisions, then
each operation can be delegated to a list-based
dictionary stored at each hash table cell.
Ordered Maps and Dictionaries
If keys obey a total order relation, can represent a map or
dictionary as an ordered search table stored in an array.
C
a
n
t
h
e
n
s
u
p
p
o
r
t
a
f
a
s
t
f
i
n
d
(
k
)
u
s
i
n
g
b
i
n
a
r
y
s
e
a
r
c
h
.
at each step, the number of candidate items is halved
terminates after a logarithmic number of steps
Example:
find
(7)
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
0
0
0
0
m
l
h
m
l
h
m
l
h
l
m
h
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
I
t
e
r
a
t
i
v
e
A
l
g
o
r
i
t
h
m
s
&
L
o
o
p
I
n
v
a
r
i
a
n
t
s
Loop Invariants
B
i
n
a
r
y
s
e
a
r
c
h
c
a
n
b
e
i
m
p
l
e
m
e
n
t
e
d
a
s
a
n
i
t
e
r
a
t
i
v
e
a
l
g
o
r
i
t
h
m
(
i
t
c
o
u
l
d
a
l
s
o
b
e
d
o
n
e
r
e
c
u
r
s
i
v
e
l
y
)
.
L
o
o
p
I
n
v
a
r
i
a
n
t
:
A
n
a
s
s
e
r
t
i
o
n
a
b
o
u
t
t
h
e
c
u
r
r
e
n
t
s
t
a
t
e
u
s
e
f
u
l
f
o
r
d
e
s
i
g
n
i
n
g
,
a
n
a
l
y
z
i
n
g
a
n
d
p
r
o
v
i
n
g
t
h
e
c
o
r
r
e
c
t
n
e
s
s
o
f
i
t
e
r
a
t
i
v
e
a
l
g
o
r
i
t
h
m
s
.
From the Pre-Conditions on the input instance
we must establish the loop invariant.
Establishing Loop Invariant
Maintain Loop Invariant
•
By
Induction
the computation will
always be in a safe location.
Ending The Algorithm
Define Exit Condition
Termination: With sufficient progress,
the exit condition will be met.
When we exit, we know
exit condition is true
loop invariant is true
from these we must establish
the post conditions.
Topics on the Midterm
Data Structures & Object-Oriented Design
Run-Time Analysis
Linear Data Structures
The Java Collections Framework
Recursion
Trees
Priority Queues & Heaps
Maps, Hash Tables & Dictionaries
Iterative Algorithms & Loop Invariants
Covering topics such as run-time analysis, linear data structures, recursion, trees, priority queues, heaps, maps, hash tables, dictionaries, iterative algorithms, loop invariants, software engineering principles, and important functions in algorithm analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Data Structures So Far Array List Priority Queue (Extendable) Array Unsorted doubly-linked list Sorted doubly-linked list Node List Heap (array-based) Singly or Doubly Linked List Adaptable Priority Queue Stack Sorted doubly-linked list with location- aware entries Array Singly Linked List Heap with location-aware entries Queue Tree Array Linked Structure Singly or Doubly Linked List Binary Tree Linked Structure Array
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Data Structures & Object-Oriented Design Definitions Principles of Object-Oriented Design Hierarchical Design in Java Abstract Data Types & Interfaces Casting Generics Pseudo-Code
Software Engineering Software must be: Readable and understandable Allows correctness to be verified, and software to be easily updated. Correct and complete Works correctly for all expected inputs Robust Capable of handling unexpected inputs. Adaptible All programs evolve over time. Programs should be designed so that re-use, generalization and modification is easy. Portable Easily ported to new hardware or operating system platforms. Efficient Makes reasonable use of time and memory resources.
Seven Important Functions Seven functions that often appear in algorithm analysis: Constant 1 Logarithmic log n Linear n N-Log-N n log n Quadratic n2 Cubic n3 Exponential 2n In a log-log chart, the slope of the line corresponds to the growth rate of the function.
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Some Math to Review properties of logarithms: logb(xy) = logbx + logby logb (x/y) = logbx - logby logbxa = alogbx logba = logxa/logxb properties of exponentials: a(b+c) = aba c abc = (ab)c ab /ac = a(b-c) b = a logab bc = a c*logab Summations Logarithms and Exponents Existential and universal operators Proof techniques Basic probability existential and universal operators $g"b Loves(b, g) "g$b Loves(b, g)
Definition of Big Oh cg n ( ) ( ) f n ( ) f n ( ( )) O g n ( ) g n n c n 0 : n , ( ) n f n cg n ( ) , 0 0
Arithmetic Progression The running time of prefixAverages1 is O(1 + 2 + + n) 7 6 5 The sum of the first n integers is n(n+ 1) 2 4 3 There is a simple visual proof of this fact 2 1 Thus, algorithm prefixAverages1 runs in O(n2) time 0 1 2 3 4 5 6
Relatives of Big-Oh big-Omega f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0 1 such that f(n) c g(n) for n n0 big-Theta f(n) is (g(n)) if there are constants c1 > 0 and c2 > 0 and an integer constant n0 1 such that c1 g(n) f(n) c2 g(n) for n n0
Time Complexity of an Algorithm The time complexity of an algorithm is the largest time required on any input of size n. (Worst case analysis.) O(n2): For any input size n n0, the algorithm takes no more than cn2 time on every input. (n2): For any input size n n0, the algorithm takes at least cn2 time on at least one input. (n2): Do both.
Time Complexity of a Problem The time complexity of a problem is the time complexity of the fastest algorithm that solves the problem. O(n2): Provide an algorithm that solves the problem in no more than this time. Remember: for every input, i.e. worst case analysis! (n2): Prove that no algorithm can solve it faster. Remember: only need one input that takes at least this long! (n2): Do both.
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Arrays Array: a sequence of indexed components with the following properties: array size is fixed at the time of array s construction int[] numbers = new int [10]; array elements are placed contiguously in memory address of any element can be calculated directly as its offset from the beginning of the array consequently, array components can be efficiently inspected or updated in O(1) time, using their indices randomNumber = numbers[5]; numbers[2] = 100;
Arrays in Java Since an array is an object, the name of the array is actually a reference (pointer) to the place in memory where the array is stored. reference to an object holds the address of the actual object Example [ arrays as objects] A B 12 24 37 53 67 int[] A={12, 24, 37, 53, 67}; int[] B=A; A B 12 24 37 5 67 B[3]=5; Example [ cloning an array] 12 24 37 53 67 A int[] A={12, 24, 37, 53, 67}; B 12 24 37 53 67 int[] B=A.clone(); B[3]=5; 12 24 37 53 67 A 12 24 37 5 67 B
Example Example [ 2D array in Java = array of arrays] int[][] nums = new int[5][4]; int[][] nums; nums = new int[5][]; for (int i=0; i<5; i++) { nums[i] = new int[4]; }
The Array List ADT (6.1) The Array List ADT extends the notion of array by storing a sequence of arbitrary objects An element can be accessed, inserted or removed by specifying its rank (number of elements preceding it) An exception is thrown if an incorrect rank is specified (e.g., a negative rank)
The Array List ADT public interface IndexList<E> { /** Returns the number of elements in this list */ public int size(); /** Returns whether the list is empty. */ public boolean isEmpty(); /** Inserts an element e to be at index I, shifting all elements after this. */ public void add(int I, E e) throws IndexOutOfBoundsException; /** Returns the element at index I, without removing it. */ public E get(int i) throws IndexOutOfBoundsException; /** Removes and returns the element at index I, shifting the elements after this. */ public E remove(int i) throws IndexOutOfBoundsException; /** Replaces the element at index I with e, returning the previous element at i. */ public E set(int I, E e) throws IndexOutOfBoundsException; }
Performance In the array based implementation The space used by the data structure is O(n) size, isEmpty, get and set run in O(1) time add and remove run in O(n) time In an add operation, when the array is full, instead of throwing an exception, we could replace the array with a larger one. In fact java.util.ArrayList implements this ADT using extendable arrays that do just this.
Doubling Strategy Analysis We replace the array k = log2n times The total time T(n) of a series of nadd(o) operations is proportional to n + 1 + 2 + 4 + 8 + + 2k= n+ 2k + 1 1 = 2n 1 geometric series 2 Thus T(n) is O(n) 4 1 1 The amortized time of an add operation is O(1)! 8 =1-rn+1 1-r n ri Recall: i=0
Stacks Chapter 5.1
The Stack ADT The Stack ADT stores arbitrary objects Auxiliary stack operations: Insertions and deletions follow the last-in first-out scheme object top(): returns the last inserted element without removing it integer size(): returns the number of elements stored Think of a spring-loaded plate dispenser Main stack operations: boolean isEmpty(): indicates whether no elements are stored push(object): inserts an element object pop(): removes and returns the last inserted element
Array-based Stack Algorithmsize() returnt + 1 A simple way of implementing the Stack ADT uses an array Algorithmpop() ifisEmpty() then throw EmptyStackException else t t - 1 returnS[t + 1] We add elements from left to right A variable keeps track of the index of the top element S t 0 1 2
Queues Chapters 5.2-5.3
Array-Based Queue Use an array of size N in a circular fashion Two variables keep track of the front and rear f index of the front element r index immediately past the rear element Array location r is kept empty normal configuration Q f r 0 1 2 wrapped-around configuration Q r f 0 1 2
Queue Operations Algorithmsize() return (N f + r) mod N We use the modulo operator (remainder of division) AlgorithmisEmpty() return (f=r) Note: N-f +r =(r +N)-f Q f r 0 1 2 Q r f 0 1 2
Linked Lists Chapters 3.2 3.3
Singly Linked List ( 3.2) A singly linked list is a concrete data structure consisting of a sequence of nodes next Each node stores node elem element link to the next node A B C D
Running Time Adding at the head is O(1) Removing at the head is O(1) How about tail operations?
Doubly Linked List Doubly-linked lists allow more flexible list management (constant time operations at both ends). prev next Nodes store: element link to the previous node elem node link to the next node Special trailer and header (sentinel) nodes trailer nodes/positions header elements
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Iterators An Iterator is an object that enables you to traverse through a collection and to remove elements from the collection selectively, if desired. You get an Iterator for a collection by calling its iterator method. Suppose collection is an instance of a Collection. Then to print out each element on a separate line: Iterator<E> it = collection.iterator(); while (it.hasNext()) System.out.println(it.next());
The Java Collections Framework (Ordered Data Types) Iterable Interface Abstract Class Collection Class List Abstract Collection Queue Abstract List Abstract Queue Priority Queue Abstract Sequential List Vector Array List Stack Linked List
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Linear Recursion Design Pattern Test for base cases Begin by testing for a set of base cases (there should be at least one). Every possible chain of recursive calls must eventually reach a base case, and the handling of each base case should not use recursion. Recurse once Perform a single recursive call. (This recursive step may involve a test that decides which of several possible recursive calls to make, but it should ultimately choose to make just one of these calls each time we perform this step.) Define each possible recursive call so that it makes progress towards a base case.
Binary Recursion Binary recursion occurs whenever there are two recursive calls for each non-base case. Example 1: The Fibonacci Sequence
Formal Definition of Rooted Tree A rooted tree may be empty. Otherwise, it consists of A root node r A set of subtrees whose roots are the children of r r B C D E F G H I J K subtree
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
Tree Terminology Root: node without parent (A) Internal node: node with at least one child (A, B, C, F) External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grand-grandparent, etc. Descendant of a node: child, grandchild, grand-grandchild, etc. Siblings: two nodes having the same parent Depth of a node: number of ancestors (excluding self) Height of a tree: maximum depth of any node (3) Subtree: tree consisting of a node and its descendants A B C D E F G H I J K subtree
Position ADT The Position ADT models the notion of place within a data structure where a single object is stored It gives a unified view of diverse ways of storing data, such as a cell of an array a node of a linked list a node of a tree Just one method: object element(): returns the element stored at the position
Tree ADT We use positions to abstract nodes Generic methods: Query methods: integer size() boolean isInternal(p) boolean isEmpty() boolean isExternal(p) Iterator iterator() boolean isRoot(p) Iterable positions() Update method: Accessor methods: object replace(p, o) position root() Additional update methods may be defined by data structures implementing the Tree ADT position parent(p) positionIterator children(p)
Preorder Traversal A traversal visits the nodes of a tree in a systematic manner AlgorithmpreOrder(v) visit(v) foreach child w of v preOrder (w) In a preorder traversal, a node is visited before its descendants 1 Make Money Fast! 2 5 9 1. Motivations 2. Methods References 6 7 8 3 4 2.3 Bank Robbery 2.1 Stock Fraud 2.2 Ponzi Scheme 1.1 Greed 1.2 Avidity
Postorder Traversal In a postorder traversal, a node is visited after its descendants AlgorithmpostOrder(v) foreach child w of v postOrder (w) visit(v) 9 cs16/ 8 3 7 todo.txt 1K homeworks/ programs/ 4 5 6 1 2 Robot.java 20K h1c.doc 3K h1nc.doc 2K DDR.java 10K Stocks.java 25K
Properties of Proper Binary Trees Notation Properties: n number of nodes e = i + 1 e number of external nodes n = 2e - 1 i number of internal nodes h i h height h (n - 1)/2 e 2h h log2e h log2(n + 1) - 1
BinaryTree ADT The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT Additional methods: position left(p) position right(p) boolean hasLeft(p) boolean hasRight(p) Update methods may be defined by data structures implementing the BinaryTree ADT
Topics on the Midterm Data Structures & Object-Oriented Design Run-Time Analysis Linear Data Structures The Java Collections Framework Recursion Trees Priority Queues & Heaps Maps, Hash Tables & Dictionaries Iterative Algorithms & Loop Invariants
