02.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 2: Review of Basic Concepts
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Approaching a problem
• Can we cover this board with 31
tiles of the following form?
• This is the mutilated
checkerboard problem.
• There are only finitely many ways
we can arrange the 31 tiles, so
there is a brute-force (and very
inefficient) way of solving the
problem.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Transform and Conquer?
Use abstraction?
• Can we cover this board with
31 tiles of the form shown?
• Why can we quickly determine
that the answer is no?
• Hint: Using the way the
squares are coloured helps.
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Transform and Conquer?
Use abstraction?
• Can we cover this board with
31 tiles of the form shown?
• Why can we quickly determine
that the answer is no?
• Hint: Using the way the
squares are coloured helps.
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Transform and Conquer?
Use abstraction?
• Can we cover this board with
31 tiles of the form shown?
• Why can we quickly determine
that the answer is no?
• Hint: Using the way the
squares are coloured helps.
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Transform and Conquer?
Use abstraction?
• Can we cover this board with
31 tiles of the form shown?
• Why can we quickly determine
that the answer is no?
• Hint: Using the way the
squares are coloured helps.
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Algorithms and Data Structures
• Algorithms: for solving problems, transforming data.
• Data structures: for storing data; arranging data in a way that suits an
algorithm.
• Linear data structures: stacks and queues
• Trees and graphs
• Dictionaries
• Which data structures are you familiar with?
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Exercise
• Pick you favourite data structure and describe:
• How to insert and item into the data structure
• How to find an item
• How to handle duplicate items
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Array
• An array corresponds to a sequence of consecutive cells in memory.
• Depending on programming language: A[0] up to A[n-1], or A[1]
up to A[n].
• Locating a cell, and storing or retrieving data at that cell is very fast.
• The downside of an array is that maintaining a contiguous bank of cells with
information can be difficult and time-consuming.
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Array
• An array corresponds to a sequence of consecutive cells in memory.
• Depending on programming language: A[0] up to A[n-1], or A[1]
up to A[n].
• Locating a cell, and storing or retrieving data at that cell is very fast.
• The downside of an array is that maintaining a contiguous bank of cells with
information can be difficult and time-consuming.
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Array
• An array corresponds to a sequence of consecutive cells in memory.
• Depending on programming language: A[0] up to A[n-1], or A[1]
up to A[n].
• Locating a cell, and storing or retrieving data at that cell is very fast.
• The downside of an array is that maintaining a contiguous bank of cells with
information can be difficult and time-consuming.
6
How many bytes does each integer occupy here?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Array
• An array corresponds to a sequence of consecutive cells in memory.
• Depending on programming language: A[0] up to A[n-1], or A[1]
up to A[n].
• Locating a cell, and storing or retrieving data at that cell is very fast.
• The downside of an array is that maintaining a contiguous bank of cells with
information can be difficult and time-consuming.
6
How many bytes does each integer occupy here?
Answer: 2 (16-bit integers)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 7An array X:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 72
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 72
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures:
The Linked List
7
2 3 5 772 3 5
null
A linked list
X:
Suppose variable X holds
the address 42160, then the
list could look like this in
memory:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
“Y.val” refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
“Y.val” refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
“Y.val” refers to
“Y.next”
refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
8
2
node
pointer
(in Java: “reference”)
72 3 5X:
X is (a pointer to) the head node of the list
2Y:
“Y.val” refers to
“Y.next”
refers to
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linked List
• Often we use a dummy head node that points to the first object, or to a
special null object that represents an empty list. This makes it easier to
write functions that insert or delete elements.
• Inserting and deleting elements is very fast: just move a few links around.
• Finding the ith element can be time-consuming.
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A: Y
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
x: 7A: Y
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
n: 6x: 7A: Y
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
j: 0n: 6x: 7A: Y
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
j: 0
A[j]
n: 6x: 7A: Y
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: Array
• Walk through the array (of length n)
• For example, to locate item x.
10
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
Y:
Let’s trace the execution of find(Y,7,6)
A[j]
n: 6x: 7A: Y j: 4
(returns 4)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(head,x)
p ← head
while p ≠ null
if p.val = x
return p
p ← p.next
return null
Iterative Processing: List
• Walk through a linked list.
• For example, to locate item x.
11
72 3 5head:
function find(A,x,n)
j ← 0
while j < n
if A[j] = x
return j
j ← j+1
return -1
(note similarity to array version)
p:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
A: Y
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
x: 7A: Y
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
lo: 0x: 7A: Y
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6lo: 0x: 7A: Y
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
lo: 0x: 7A: Y
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
lo: 0x: 7A: Y
Initial call: find(A,x,0,n-1)
A[hi]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
lo: 1
A[hi]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
lo: 1
A[hi]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
lo: 1
A[hi]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
A[hi]
lo: 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
A[hi]
lo: 3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
Initial call: find(A,x,0,n-1)
A[hi]
lo: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Recursive Processing: Array
12
• Solve the problem for a sub-instance and use the solution to solve the full
instance
• For example, to locate item x.
Y:
Let’s trace the execution of find(Y,7,0,6)
hi: 6
A[lo]
x: 7A: Y
(returns 4)
Initial call: find(A,x,0,n-1)
A[hi]
lo: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function find(p,x)
if p = null
return p
else if p.val = x
return p
else
return find(p.next,x)
Recursive Processing: List
• Solve the problem for a sub-instance and use the solution to solve the full
instance
13
72 3 5head:
(note similarity to array version)
p:
function find(A,x,lo,hi)
if lo > hi
return -1
else if A[lo] = x
return lo
else
return find(A,x,lo+1,hi)
Initial call: find(head,x)
We will
discuss
recursio
n
properly
in
Week 3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Abstract DataTypes
• A collection of data items, and a family of operations that operate on that
data
• Think of an ADT as a set of contracts, an interface
• We must still implement these promises, but it is an advantage to separate
the implementation of the ADT from the “concept” (i.e. the interface it
provides)
• Good programming practice is to support this separation
• Nothing outside of the definition of the ADT should refer to anything
inside, except through function calls and basic operations
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
The Stack
• Last-In-First-Out (LIFO)
• Operations:
• CreateStack
• Push
• Pop
• Top
• EmptyStack?
• …
• Usually implemented as an ADT
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
top: 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
top: 5
Push(5)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
top: 5
Push(5)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Array
16
Push(5)
top: 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
elt:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5 function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation:
Linked List
17
72 3 5st:
Push(5)
5
See
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
for more visualisations
function push(st,x)
elt ← new node
elt.val ← x
elt.next ← st
st ← elt
return st
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Pseudo Code
• On the previous slide, we assumed that a “node” has two attributes: a “val”
which is its value, and a “next” which points to the rest of the list.
• There is no standard for pseudo-code. Use the examples in Levitin as a
guide. Cormen et al. pages 20–22 (in Reading Resources) has a list of
standard conventions used with pseudo-code which are good to follow,
except we use ← as the assignment operator.
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Fundamental Data Structure:
Queues
• First-In-First-Out (FIFO)
• Operations:
• CreateQueue
• Enqueue
• Dequeue
• Head
• EmptyQueue?
• …
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Other Data Structures
• We will meet many other (abstract) data structures, e.g.
• The priority queue
• Various types of “tree”
• Various types of “graph”
• If you check out algorithm animation tools or advanced algorithm books, you
will meet exotic data structures such as splay trees and skip lists.
20
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next Week
• Algorithm analysis—how to reason about an algorithm’s resource
consumption.
21