Transcript L-1

Data Structures and algorithms (IS ZC361)
An overview of topics for the mid-semester exam
S.P.Vimal
BITS-Pilani
Source :This presentation is composed from the presentation materials provided by the
authors (GOODRICH and TAMASSIA) of text book -1 specified in the handout
Data Structures and Algorithms
Overview topics
1.
2.
3.
4.
Algorithm analysis
Linear Data structures
Trees
Sorting Algorithms
Data Structures and Algorithms
Introduction
• Data Structures: A systematic way of organizing and
accessing data.
--No single data structure works well for ALL purposes.
Input
Algorithm
Output
• An algorithm is a step-by-step procedure for solving a
problem in a finite amount of time.
Data Structures and Algorithms
Algorithm Descriptions
• Nature languages: Chinese, English, etc.
• Pseudo-code: codes very close to computer languages, e.g., C
programming language.
• Programs: C programs, C++ programs, Java programs.
Goal:
• Allow a well-trained programmer to be able to implement.
• Allow an expert to be able to analyze the running time.
Data Structures and Algorithms
Algorithm: An example
Algorithm sorting(X, n)
Input array X of n integers
Output array X sorted in a non-decreasing order
for i  0 to n  1 do
for j  i+1 to n do
if (X[i]>X[j]) then
{ s=X[i];
X[i]=X[j];
X[j]=s;
}
return X
Data Structures and Algorithms
What do we analyze in an algorithm???
– Estimate the running time
– Estimate the memory space required.
>> Depends on the input size.
Data Structures and Algorithms
Running time of an algorithm
120
100
Running Time
• Most algorithms transform
input objects into output
objects.
• The running time of an
algorithm typically grows
with the input size.
best case
average case
worst case
80
60
40
20
0
1000
2000
3000
Input Size
Data Structures and Algorithms
4000
Counting Primitive Operations
• By inspecting the pseudo code, we can determine the
maximum number of primitive operations executed
by an algorithm, as a function of the input size
Algorithm arrayMax(A, n)
currentMax  A[0]
for i  1 to n  1 do
if A[i]  currentMax then
currentMax  A[i]
{ increment counter i }
return currentMax
# operations
2
2+n
2(n  1)
2(n  1)
2(n  1)
1
Total
Data Structures and Algorithms
7n  1
Growth Rate of Running Time
• Changing the hardware/ software environment
– Affects T(n) by a constant factor, but
– Does not alter the growth rate of T(n)
• The linear growth rate of the running time T(n) is an intrinsic
property of algorithm arrayMax
• Growth rates of functions:
– Linear  n
– Quadratic  n2
– Cubic  n3
• In a log-log chart, the slope of the line corresponds to the
growth rate of the function
Data Structures and Algorithms
T (n )
Growth rates
1E+30
1E+28
1E+26
1E+24
1E+22
1E+20
1E+18
1E+16
1E+14
1E+12
1E+10
1E+8
1E+6
1E+4
1E+2
1E+0
1E+0
Cubic
Quadratic
Linear
1E+2
1E+4
1E+6
n
Data Structures and Algorithms
1E+8
1E+10
Big-Oh notation
• To simplify the running time estimation,
for a function f(n), we ignore the constants and lower
order terms.
Example: 10n3+4n2-4n+5 is O(n3)
Formally,
Given functions f(n) and g(n), we say that f(n) is
O(g(n)) if there are positive constants
c and n0 such that
f(n)  cg(n) for n  n0
Data Structures and Algorithms
10,000
3n
2n+10
1,000
n
100
Example: 2n + 10 is O(n)
2n + 10  cn
(c  2) n  10
n  10/(c  2)
10
1
1
10
100
n
1,000
Pick c = 3 and n0 =
10
Data Structures and Algorithms
Big-Oh notation - examples
• Example: the function n2 is not O(n)
– n2  cn
– nc
– The above inequality cannot be satisfied since c must
be a constant
– n2 is O(n2).
Data Structures and Algorithms
Big-Oh notation - examples
• 7n-2 is O(n)
– need c > 0 and n0  1 such that 7n-2  c•n for n  n0
– this is true for c = 7 and n0 = 1
• 3n3 + 20n2 + 5 is O(n3)
– need c > 0 and n0  1 such that 3n3 + 20n2 + 5  c•n3 for n  n0
– this is true for c = 4 and n0 = 21
• 3 log n + 5 is O(log n)
– need c > 0 and n0  1 such that 3 log n + 5  c•log n for n  n0
– this is true for c = 8 and n0 = 2
Data Structures and Algorithms
• The big-Oh notation gives an upper bound on the
growth rate of a function
• The statement “f(n) is O(g(n))” means that the growth
rate of f(n) is no more than the growth rate of g(n)
• We can use the big-Oh notation to rank functions
according to their growth rate
Data Structures and Algorithms
1.
2.
3.
4.
Algorithm analysis (  )
Linear Data structures
Trees
Sorting Algorithms
Data Structures and Algorithms
ADT (Abstract Data Type)
• An abstract data type (ADT) is an abstraction of a
data structure
• An ADT specifies:
– Data stored
– Operations on the data
– Error conditions associated with operations
Data Structures and Algorithms
ADT (Abstract Data Type)
• Example: ADT modeling a students record
– The data stored are
• Student name, id No., 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
Data Structures and Algorithms
The Stack ADT
• The Stack ADT stores arbitrary objects
• Insertions and deletions follow the last-in first-out
scheme
• Main stack operations:
– push (object): inserts an element
– object pop(): removes and returns the last inserted
element
Data Structures and Algorithms
• 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
Data Structures and Algorithms
Array-based Stack
• 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 (size is
t+1)
Algorithm pop():
if isEmpty() then
throw EmptyStackException
else
tt1
return S[t + 1]
Algorithm push(o)
if t = S.length  1 then
throw FullStackException
else
tt+1
S[t]  o
Data Structures and Algorithms
The Queue ADT
• The Queue ADT stores arbitrary objects
• Insertions and deletions follow the first-in first-out
scheme
• Insertions are at the rear of the queue and removals
are at the front of the queue
• Main queue operations:
– enqueue(object): inserts an element at the end of the
queue
– object dequeue(): removes and returns the element at
the front of the queue
Data Structures and Algorithms
• Auxiliary queue operations:
– object front(): returns the element at the front without
removing it
– integer size(): returns the number of elements stored
– boolean isEmpty(): indicates whether no elements are
stored
• Exceptions
– Attempting the execution of dequeue or front on an
empty queue throws an EmptyQueueException
Data Structures and Algorithms
Singly Linked List
• A singly linked list is a concrete data structure
consisting of a sequence of nodes
• Each node stores
– element
– link to the next node
elem
next
node

A
B
C
Data Structures and Algorithms
D
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

Data Structures and Algorithms
elements
List ADT
• The List ADT models a
sequence of positions storing
arbitrary objects
• It allows for insertion and
removal in the “middle”
• Query methods:
– isFirst(p), isLast(p)
Accessor methods:
– first(), last()
– before(p), after(p)
• Update methods:
– replaceElement(p, o),
swapElements(p, q)
– insertBefore(p, o),
insertAfter(p, o),
– insertFirst(o),
insertLast(o)
– remove(p)
Data Structures and Algorithms
Doubly Linked List
•
•
A doubly linked list provides a natural
implementation of the List ADT
Nodes implement Position and store:
prev
– element
– link to the previous node
– link to the next node
•
next
elem
node
Special trailer and header nodes
header
nodes/positions
elements
Data Structures and Algorithms
trailer
1.
2.
3.
4.
Algorithm analysis (  )
Linear Data structures (  )
Trees
Sorting Algorithms
Data Structures and Algorithms
Trees (§2.3)
•
•
•
In computer science, a tree is
an abstract model of a
hierarchical structure
A tree consists of nodes with a
parent-child relation
Applications:
– Organization charts
– File systems
US
– Programming environments
Europe
Computers”R”Us
Sales
Manufacturing
International
Asia
Data Structures and Algorithms
Laptops
Canada
Desktops
R&D
Tree ADT (§2.3.1)
•
•
We use positions to abstract nodes
Generic methods:
–
–
–
–
•
integer size()
boolean isEmpty()
objectIterator elements()
positionIterator positions()
•
– boolean isInternal(p)
– boolean isExternal(p)
– boolean isRoot(p)
•
Update methods:
– swapElements(p, q)
– object replaceElement(p, o)
Accessor methods:
– position root()
– position parent(p)
– positionIterator children(p)
Query methods:
•
Additional update methods may be
defined by data structures
implementing the Tree ADT
Data Structures and Algorithms
Preorder Traversal (§2.3.2)
•
•
•
A traversal visits the nodes of a tree in a
systematic manner
In a preorder traversal, a node is visited
before its descendants
Application: print a structured document
1
Algorithm preOrder(v)
visit(v)
for each child w of v
preorder (w)
Make Money Fast!
2
5
1. Motivations
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
6
2.1 Stock
Fraud
7
2.2 Ponzi
Scheme
Data Structures and Algorithms
References
8
2.3 Bank
Robbery
Post order Traversal
•
•
In a postorder traversal, a node is
visited after its descendants
Application: compute space used by
files in a directory and its
subdirectories
9
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
cs16/
3
8
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
DDR.java
10K
5
Stocks.java
25K
Data Structures and Algorithms
6
Robot.java
20K
Binary Trees
•
A binary tree is a tree with the following
properties:
•
– arithmetic expressions
– decision processes
– searching
– Each internal node has two children
– The children of a node are an ordered
pair
•
•
Applications:
We call the children of an internal node
left child and right child
Alternative recursive definition: a binary
tree is either
A
B
– a tree consisting of a single node, or
– a tree whose root has an ordered pair of
children, each of which is a binary tree
C
D
E
H
Data Structures and Algorithms
F
I
G
Arithmetic Expression Tree
• Binary tree associated with an arithmetic expression
– internal nodes: operators
– external nodes: operands
• Example: arithmetic expression tree for the expression (2  (a  1) + (3
 b))
+



2
a
3
1
Data Structures and Algorithms
b
Properties of Binary Trees
• Notation
n number of nodes
e number of external
nodes
i number of internal
nodes
h height
• Properties:
Data Structures and Algorithms
–
–
–
–
–
–
–
e=i+1
n = 2e  1
hi
h  (n  1)/2
e  2h
h  log2 e
h  log2 (n + 1)  1
Inorder Traversal
•
•
In an inorder traversal a node is
visited after its left subtree and
before its right subtree
Application: draw a binary tree
Algorithm inOrder(v)
if isInternal (v)
inOrder (leftChild (v))
visit(v)
if isInternal (v)
inOrder (rightChild (v))
– x(v) = inorder rank of v
– y(v) = depth of v
6
2
8
1
4
3
7
9
5
Data Structures and Algorithms
Printing Arithmetic Expressions
•
Specialization of an inorder traversal
–
–
–
print operand or operator when
visiting node
print “(“ before traversing left
subtree
print “)“ after traversing right
subtree
+



2
a
3
1
b
Algorithm printExpression(v)
if isInternal (v)
print(“(’’)
inOrder (leftChild (v))
print(v.element ())
if isInternal (v)
inOrder (rightChild (v))
print (“)’’)
((2  (a  1)) + (3  b))
Data Structures and Algorithms
Linked Data Structure for Representing
Trees
•
A node is represented by an
object storing
–
–
–
•
Element
Parent node
Sequence of children nodes

B
Node objects implement the
Position ADT

A
B
D
A
C

D
F
F

E
Data Structures and Algorithms
C

E
Linked Data Structure for Binary Trees
•
A node is represented by an
object storing
–
–
–
–
•

Element
Parent node
Left child node
Right child node
B
Node objects implement the
Position ADT

B
A
A
D
C

D

E

C
Data Structures and Algorithms


E
Array-Based Representation of Binary Trees
• nodes are stored in an array
1
A
…
2
3
B

D
let rank(node) be defined as follows:



4
rank(root) = 1
if node is the left child of parent(node),
rank(node) = 2*rank(parent(node))
if node is the right child of parent(node),
rank(node) = 2*rank(parent(node))+1
Data Structures and Algorithms
5
E
6
C
F
10
11
G
7
H
J
Binary Search Tree
• A binary search tree is a binary
tree storing keys (or keyelement pairs) at its internal
nodes and satisfying the
following property:
– Let u, v, and w be three
nodes such that u is in the
left subtree of v and w is in
the right subtree of v. We
have
key(u)  key(v)  key(w)
• External nodes do not store
items
• An inorder traversal of a binary
search trees visits the keys in
increasing order
6
2
1
Data Structures and Algorithms
9
4
8
Search
•
•
•
•
To search for a key k, we
trace a downward path
starting at the root
The next node visited
depends on the outcome of
the comparison of k with the
key of the current node
If we reach a leaf, the key is
not found and we return
NO_SUCH_KEY
Example: findElement(4)
Algorithm findElement(k, v)
if T.isExternal (v)
return NO_SUCH_KEY
if k < key(v)
return findElement(k, T.leftChild(v))
else if k = key(v)
return element(v)
else { k  key(v) }
return findElement(k, T.rightChild(v))
<
2
1
Data Structures and Algorithms
6
9

4 =
8
Insertion
•
•
•
•
6
<
To perform operation
insertItem(k, o), we search for
key k
Assume k is not already in the
tree, and let let w be the leaf
reached by the search
We insert k at node w and expand
w into an internal node
Example: insert 5
2
9

1
4
8

w
6
2
1
9
4
8
w
5
Data Structures and Algorithms
Deletion
•
•
•
•
To perform operation
removeElement(k), we search for
key k
Assume key k is in the tree, and let
let v be the node storing k
If node v has a leaf child w, we
remove v and w from the tree with
operation
removeAboveExternal(w)
Example: remove 4
6
<
2
9

4 v
1
8
w
5
6
2
1
Data Structures and Algorithms
9
5
8
Deletion (cont.)
•
1
We consider the case where the key
k to be removed is stored at a node v
whose children are both internal
– we find the internal node w that
follows v in an inorder traversal
– we copy key(w) into node v
– we remove node w and its left
child z (which must be a leaf) by
means of operation
removeAboveExternal(z)
•
v
3
2
8
6
w
9
5
z
1
v
Example: remove 3
5
2
8
6
Data Structures and Algorithms
9
Performance
• Consider a dictionary with n
items implemented by means
of a binary search tree of
height h
– the space used is O(n)
– methods findElement ,
insertItem and
removeElement take O(h)
time
• The height h is O(n) in the
worst case and O(log n) in the
best case
Data Structures and Algorithms
1.
2.
3.
4.
Algorithm analysis (  )
Linear Data structures (  )
Trees (  )
Sorting Algorithms
Data Structures and Algorithms
Divide-and-Conquer
•
•
Divide-and conquer is a general
algorithm design paradigm:
– Divide: divide the input data S
in two disjoint subsets S1 and
S2
– Recur: solve the subproblems
associated with S1 and S2
– Conquer: combine the
solutions for S1 and S2 into a
solution for S
The base case for the recursion are
subproblems of size 0 or 1
•
•
•
Merge-sort is a sorting algorithm
based on the divide-and-conquer
paradigm
Like heap-sort
– It uses a comparator
– It has O(n log n) running
time
Unlike heap-sort
– It does not use an auxiliary
priority queue
– It accesses data in a
sequential manner (suitable
to sort data on a disk)
Data Structures and Algorithms
Merge-Sort
• Merge-sort on an input
sequence S with n elements
consists of three steps:
– Divide: partition S into two
sequences S1 and S2 of
about n/2 elements each
– Recur: recursively sort S1
and S2
– Conquer: merge S1 and S2
into a unique sorted
sequence
Algorithm mergeSort(S, C)
Input sequence S with n
elements, comparator C
Output sequence S sorted
according to C
if S.size() > 1
(S1, S2)  partition(S, n/2)
mergeSort(S1, C)
mergeSort(S2, C)
S  merge(S1, S2)
Data Structures and Algorithms
Merging Two Sorted Sequences
•
•
The conquer step of
merge-sort consists of
merging two sorted
sequences A and B into a
sorted sequence S
containing the union of
the elements of A and B
Merging two sorted
sequences, each with n/2
elements and
implemented by means of
a doubly linked list, takes
O(n) time
Algorithm merge(A, B)
Input sequences A and B with
n/2 elements each
Output sorted sequence of A  B
S  empty sequence
while A.isEmpty()  B.isEmpty()
if A.first().element() < B.first().element()
S.insertLast(A.remove(A.first()))
else
S.insertLast(B.remove(B.first()))
while A.isEmpty()
S.insertLast(A.remove(A.first()))
while B.isEmpty()
S.insertLast(B.remove(B.first()))
return S
Data Structures and Algorithms
Merge-Sort Tree
• An execution of merge-sort is depicted by a binary tree
– each node represents a recursive call of merge-sort and stores
• unsorted sequence before the execution and its partition
• sorted sequence at the end of the execution
– the root is the initial call
– the leaves are calls on subsequences of size 0 or 1
7 2
7


9 4  2 4 7 9
2  2 7
77
22
9

4  4 9
99
Data Structures and Algorithms
44
Execution Example
• Partition
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 2 9 4  2 4 7 9
7 2  2 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, partition
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
7 2  2 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, partition
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, base case
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, base case
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Merge
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, …, base case, merge
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Merge
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 8 6
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Recursive call, …, merge, merge
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 6 8
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Execution Example (cont.)
• Merge
7 2 9 43 8 6 1  1 2 3 4 6 7 8 9
7 29 4 2 4 7 9
722 7
77
22
3 8 6 1  1 3 6 8
9 4  4 9
99
44
3 8  3 8
33
Data Structures and Algorithms
88
6 1  1 6
66
11
Analysis of Merge-Sort
•
The height h of the merge-sort tree is O(log n)
– at each recursive call we divide in half the sequence,
•
The overall amount or work done at the nodes of depth i is O(n)
– we partition and merge 2i sequences of size n/2i
– we make 2i+1 recursive calls
•
Thus, the total running time of merge-sort is O(n log n)
depth
#seqs
size
0
1
n
1
2
n/2
i
2i
n/2i
…
…
…
Data Structures and Algorithms
Summary of Sorting Algorithms
Algorithm
selection-sort
insertion-sort
heap-sort
merge-sort
Time
Notes
O(n2)
• slow
• in-place
• for small data sets (< 1K)
O(n2)
• slow
• in-place
• for small data sets (< 1K)
O(n log n)
• fast
• in-place
• for large data sets (1K — 1M)
O(n log n)
• fast
• sequential data access
• for huge data sets (> 1M)
Data Structures and Algorithms
1.
2.
3.
4.
Algorithm analysis (  )
Linear Data structures (  )
Trees (  )
Sorting Algorithms (  )
Questions ?
Data Structures and Algorithms
Reference :
Chapter 1,2,3 and 4 of Text book-1
Data Structures and Algorithms