Transcript Analysis of Algorithms

Vectors
7/21/2015 9:06 AM
week 2b
1
Outline and Reading
The Vector ADT (§5.1)
Array-based implementation
7/21/2015 9:06 AM
week 2b
2
The Vector ADT
The Vector 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)
7/21/2015 9:06 AM
Main vector operations:
 object elemAtRank(integer r):
returns the element at rank r
without removing it
 object replaceAtRank(integer r,
object o): replace the element at
rank with o and return the old
element
 insertAtRank(integer r, object o):
insert a new element o to have
rank r
 object removeAtRank(integer r):
removes and returns the element
at rank r
Additional operations size() and
isEmpty()
week 2b
3
Applications of Vectors
Direct applications

Sorted collection of objects (elementary
database)
Indirect applications


Auxiliary data structure for algorithms
Component of other data structures
7/21/2015 9:06 AM
week 2b
4
Array-based Vector
Use an array V of size N
A variable n keeps track of the size of the vector
(number of elements stored)
Operation elemAtRank(r) is implemented in O(1)
time by returning V[r]
V
0 1 2
7/21/2015 9:06 AM
n
r
week 2b
5
Insertion
In operation insertAtRank(r, o), we need to make
room for the new element by shifting forward the
n - r elements V[r], …, V[n - 1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
r
n
0 1 2
r
n
0 1 2
o
r
V
V
7/21/2015 9:06 AM
week 2b
n
6
Deletion
In operation removeAtRank(r), we need to fill the
hole left by the removed element by shifting
backward the n - r - 1 elements V[r + 1], …, V[n - 1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
o
r
n
0 1 2
r
n
0 1 2
r
V
V
7/21/2015 9:06 AM
week 2b
n
7
Performance
In the array based implementation of a Vector



The space used by the data structure is O(n)
size, isEmpty, elemAtRank and replaceAtRank run in
O(1) time
insertAtRank and removeAtRank run in O(n) time
If we use the array in a circular fashion,
insertAtRank(0) and removeAtRank(0) run in
O(1) time
In an insertAtRank operation, when the array
is full, instead of throwing an exception, we
can replace the array with a larger one
7/21/2015 9:06 AM
week 2b
8
Lists and Sequences
7/21/2015 9:06 AM
week 2b
9
Outline and Reading
Singly linked list (§5.2)
Position ADT and List ADT (§5.2.2)
Doubly linked list (§5.2.4)
Sequence ADT (§5.3)
Implementations of the sequence ADT
Iterators (§5.5)
7/21/2015 9:06 AM
week 2b
10
Singly Linked List
A singly linked list is a
concrete data structure
consisting of a sequence
of nodes
Each node stores


next
element
link to the next node
node
elem

A
7/21/2015 9:06 AM
B
C
week 2b
D
11
Stack with a Singly Linked List
We can implement a stack with a singly linked list
The top element is stored at the first node of the list
The space used is O(n) and each operation of the
Stack ADT takes O(1) time
nodes

t
elements
7/21/2015 9:06 AM
week 2b
12
Queue with a Singly Linked List
We can implement a queue with a singly linked list


The front element is stored at the first node
The rear element is stored at the last node
The space used is O(n) and each operation of the
Queue ADT takes O(1) time
r
nodes
f

elements
7/21/2015 9:06 AM
week 2b
13
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
Just one method:

object element(): returns the element
stored at the position
7/21/2015 9:06 AM
week 2b
14
List ADT
The List ADT models a
sequence of positions
storing arbitrary objects
It establishes a
before/after relation
between positions
Generic methods:

size(), isEmpty()
isFirst(p), isLast(p)
7/21/2015 9:06 AM





week 2b
first(), last()
before(p), after(p)
Update methods:

Query methods:

Accessor methods:
replaceElement(p, o),
swapElements(p, q)
insertBefore(p, o),
insertAfter(p, o),
insertFirst(o),
insertLast(o)
remove(p)
15
Doubly Linked List
A doubly linked list provides a natural
implementation of the List ADT
Nodes implement Position and store:



element
link to the previous node
link to the next node
prev
next
elem
node
Special trailer and header nodes
nodes/positions
header
trailer
elements
7/21/2015 9:06 AM
week 2b
16
Insertion
We visualize operation insertAfter(p, X), which returns position q
p
A
B
C
p
A
q
B
C
X
p
A
7/21/2015 9:06 AM
q
B
week 2b
X
C
17
Deletion
We visualize remove(p), where p = last()
p
A
B
C
A
B
C
D
p
D
A
7/21/2015 9:06 AM
B
week 2b
C
18
Performance
In the implementation of the List ADT
by means of a doubly linked list




The space used by a list with n elements is
O(n)
The space used by each position of the list
is O(1)
All the operations of the List ADT run in
O(1) time
Operation element() of the
Position ADT runs in O(1) time
7/21/2015 9:06 AM
week 2b
19
Case Study: Java Vector:
import util.Vector
// size and determination
size();
isEmpty();
capacity();
setSize(); //truncate/expand
// element access
contains(e);
firstElement();
lastElement();
elementAt();
7/21/2015 9:06 AM
// insertion/removal
addElement(e); // at end
setElementAt(e, r); // replace
insertElememtAt(e, r);
removeElementAt(r);
removeElement(e);
removeAllElements();
// search
indexOf(e);
lastIndexOf(e);
week 2b
20
Sequence ADT
The Sequence ADT is the
union of the Vector and
List ADTs
Elements accessed by


List-based methods:

Rank, or
Position
Generic methods:

size(), isEmpty()
Vector-based methods:

elemAtRank(r),
replaceAtRank(r, o),
insertAtRank(r, o),
removeAtRank(r)
7/21/2015 9:06 AM
first(), last(),
before(p), after(p),
replaceElement(p, o),
swapElements(p, q),
insertBefore(p, o),
insertAfter(p, o),
insertFirst(o),
insertLast(o),
remove(p)
Bridge methods:

week 2b
atRank(r), rankOf(p)
21
Applications of Sequences
The Sequence ADT is a basic, generalpurpose, data structure for storing an ordered
collection of elements
Direct applications:


Generic replacement for stack, queue, vector, or
list
small database (e.g., address book)
Indirect applications:

Building block of more complex data structures
7/21/2015 9:06 AM
week 2b
22
Array-based Implementation
elements
We use a
circular array
storing
positions
A position
object stores:


Element
Rank
Indices f and l
keep track of
first and last
positions
0
1
3
positions
S
f
7/21/2015 9:06 AM
2
week 2b
l
23
Sequence Implementations
Operation
size, isEmpty
atRank, rankOf, elemAtRank
first, last, before, after
replaceElement, swapElements
replaceAtRank
insertAtRank, removeAtRank
insertFirst, insertLast
insertAfter, insertBefore
remove
7/21/2015 9:06 AM
week 2b
Array
1
1
1
1
1
n
1
n
n
List
1
n
1
1
n
n
1
1
1
24
Case Study: Bubble sort
Keep passing through the sequence of
data, exchanging adjacent elements if
necessary, when no exchanges are
required on some pass, the sequence is
sorted.
7/21/2015 9:06 AM
week 2b
25
Example:
pass swaps
sequence
(5,7,2,6,9,3)
1
72 76 93
(5,2,6,7,3,9)
2
52 73
(2,5,6,3,7,9)
3
63
(2,5,3,6,7,9)
4
53
(2,3,5,6,7,9)
7/21/2015 9:06 AM
week 2b
26
Supplementary methods:
private static int valAtRank(Sequence S, int i){
return ((Integer) S.elemAtRank(i)).intValue();
}
private static int valAtPos(Position p){
return ((Integer) p.element()).intValue();
}
7/21/2015 9:06 AM
week 2b
27
Bubble-sort using ranks:
Public static void bubbleSort1(Sequence S){
int n = S.size();
for (int i = 0; i<n; i++)
for (int j = 1; j<n-i; j++)
if (valAtRank(S, j-1) > valAtRank(S, j))
S.swapElements(S.atRank(j-1), S.atRank(j));
}
7/21/2015 9:06 AM
week 2b
28
Bubble-sort using position:
Public static void bubbleSort2(Sequence S){
Position prec, succ;
int n = S.size();
for(int i = 0; i<n; i++){
prec = S.first();
for (int j = 1; j<n-i; j++){
succ = S.after(prec);
if (valAtPos(prec) > valAtPos(succ))
S.swapElements(prec, succ);
prec = succ;
}
}
}
7/21/2015 9:06 AM
week 2b
29
Iterators
An iterator abstracts the
process of scanning through
a collection of elements
Methods of the ObjectIterator
ADT:




object object()
boolean hasNext()
object nextObject()
reset()

ObjectIterator elements()
Two notions of iterator:
Extends the concept of
Position by adding a traversal
capability
Implementation with an array
or singly linked list
7/21/2015 9:06 AM
An iterator is typically
associated with an another
data structure
We can augment the Stack,
Queue, Vector, List and
Sequence ADTs with method:
week 2b


snapshot: freezes the
contents of the data
structure at a given time
dynamic: follows changes to
the data structure
30