COMP90038
Algorithms and Complexity
Lecture 2: Review of Basic Concepts (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
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
•
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.
Can we cover this board with 31
•
tiles of the following form?
This is the mutilated
•
checkerboard problem.
Approaching a problem
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
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.
Can we cover this board with 31
•
tiles of the following form?
This is the mutilated
•
checkerboard problem.
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
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.
4
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
Linear data structures: stacks and queues Trees and graphs
Dictionaries
•
•
algorithm.
•
Which data structures are you familiar with?
• • •
5
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
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
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How many bytes does each integer occupy here?
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
How many bytes does each integer occupy here?
Answer: 2 (16-bit integers)
Primitive Data Structures: The Linked List
An array X:
2
3
5
7
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
2
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
3
5
7
Primitive Data Structures: The Linked List
2
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
3
5
7
Primitive Data Structures: The Linked List
2
3
5
7
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
2
3
5
7
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
2
3
5
7
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
2
3
5
7
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
null
Primitive Data Structures: The Linked List
A linked list X:
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
null
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Primitive Data Structures: The Linked List
A linked list X:
Suppose variable X holds the address 42160, then the list could look like this in memory:
null
2
3
5
7
7
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
2
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
2
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
2
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
2
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
2
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
2
2
3
5
7
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
2
2
3
5
7
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
Y:
2
2
3
5
7
2
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
Y: “Y.val” refers to
2
2
3
5
7
2
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
Y: “Y.val” refers to
2
2
3
5
7
2
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
2
2
3
5
7
2
Y: “Y.val” refers to
“Y.next” refers to
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
2
2
3
5
7
2
Y: “Y.val” refers to
“Y.next” refers to
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linked List
• •
Inserting and deleting elements is very fast: just move a few links around. Finding the ith element can be time-consuming.
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.
10
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.
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
• •
Iterative Processing: Array
Walk through the array (of length n) For example, to locate item x.
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
• •
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
10
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.
function find(A,x,n) j←0
while j < n if A[j] = x
return j j ← j+1
return -1
• •
Y:
Iterative Processing: Array
Walk through the array (of length n) For example, to locate item x.
• •
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)
10
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.
A: Y
• •
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)
10
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.
• •
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 x: 7
10
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.
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
x: 7
n: 6
10
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.
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
x: 7
n: 6
j: 0
10
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.
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 A[j]
x: 7
n: 6
j: 0
10
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.
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 A[j]
x: 7
n: 6
j: 1
10
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.
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 A[j]
x: 7
n: 6
j: 1
10
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.
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
x: 7 A[j]
n: 6
j: 2
10
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.
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
x: 7
n: 6 A[j]
j: 3
10
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.
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
x: 7
n: 6
j: 4 A[j]
10
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.
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)
(returns 4)
A: Y
x: 7
n: 6
j: 4 A[j]
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
Walk through a linked list.
For example, to locate item x.
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.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p ← p.next
return null head:
• •
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Iterative Processing: List
• •
Walk through a linked list.
For example, to locate item x.
function find(head,x) p ← head
while p ≠ null if p.val = x
return p p: p ← p.next
return null head:
(note similarity to array version)
function find(A,x,n) j ← 0
while j < n if A[j] = x
return j j ← j+1
return -1
2
3
5
7
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: Array
For example, to locate item x.
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)
•
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: Array
For example, to locate item x.
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(A,x,0,n-1)
•
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
Recursive Processing: Array
For example, to locate item x.
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(A,x,0,n-1)
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
•
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: Array
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
return lo else
12
Initial call: find(A,x,0,n-1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Y: return find(A,x,lo+1,hi)
12
Recursive Processing: Array
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
•
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
12
Recursive Processing: Array
For example, to locate item x.
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
•
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
return lo else
A: Y
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
12
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
return lo else
Y: return find(A,x,lo+1,hi)
A: Y x: 7
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
12
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
return lo else
Y: return find(A,x,lo+1,hi)
A: Y
x: 7
lo: 0
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
12
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
return lo else
Y: return find(A,x,lo+1,hi)
A: Y
x: 7
lo: 0
hi: 6
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
•
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
A: Y A[lo]
x: 7
lo: 0
hi: 6
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y A[lo]
x: 7
lo: 0
hi: 6
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y A[lo]
x: 7
lo: 1
hi: 6
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y A[lo]
lo: 1
hi: 6
x: 7
A[hi]
return lo else
12
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y A[lo]
lo: 1
hi: 6
x: 7
A[hi]
return lo else
12
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y
x: 7 A[lo]
lo: 2
hi: 6
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
•
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
A: Y
x: 7
lo: 3 A[lo]
hi: 6
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y
x: 7
lo: 4
hi: 6 A[lo]
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
Let’s trace the execution of find(Y,7,0,6) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: find(A,x,0,n-1)
Recursive Processing: Array
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
For example, to locate item x.
function find(A,x,lo,hi) if lo > hi
return -1 else if A[lo] = x
•
A: Y
x: 7
lo: 4
hi: 6 A[lo]
A[hi]
12
return lo else
Y: return find(A,x,lo+1,hi)
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
(returns 4)
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
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
2
3
5
7
13
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x)
head:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) Initial call: find(head,x)
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
2
3
5
7
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursive Processing: List
Solve the problem for a sub-instance and use the solution to solve the full (note similarity to array version)
•
instance
function find(p,x) if p = null
return p else if p.val = x
return p else
return find(p.next,x) p: Initial call: find(head,x)
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)
2
3
5
7
head:
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
We will
discuss recursion properly in Week 3
14
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
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
•
data
•
•
•
Nothing outside of the definition of the ADT should refer to anything
•
inside, except through function calls and basic operations
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
Fundamental Data Structure:
The Stack
Last-In-First-Out (LIFO) Operations:
CreateStack Push
Pop
Top EmptyStack? …
•
•
•
• • • • •
•
Usually implemented as an ADT
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
top: 5
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Array
top: 5 Push(5)
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Array
top: 5 Push(5)
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Array
top: 6 Push(5)
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
2
3
5
7
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
2
3
5
7
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
2
3
5
7
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
elt: Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stack Implementation: Linked List
st:
2
3
5
7
5
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
Stack Implementation: Linked List
st:
2
3
5
7
5
Push(5)
function push(st,x) elt ← new node elt.val ← x elt.next ← st
st ← elt return st
See
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
for more visualisations
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Pseudo Code
•
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.
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.
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
20
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.
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next Week
Algorithm analysis—how to reason about an algorithm’s resource
•
consumption.