COSC1285/2123: Algorithms & Analysis – Decrease and Conquer
COSC1285/2123: Algorithms & Analysis
Decrease and Conquer
Hoang MIT University
Email : sonhoang. .au
Lecture 5
(RMIT University) Decrease and Conquer Lecture 5 1 / 69
Overview
Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 4.
Learning Outcomes:
• Understand the Decrease-and-conquer algorithmic approach.
• Understand, contrast and apply:
• Decrease-by-a-constant algorithms – insertion and topological sort.
• Decrease-by-a-constant-factor algorithms – binary search, fake
coin problem.
• Variable-size decrease algorithms – binary search tree.
(RMIT University) Decrease and Conquer Lecture 5 2 / 69
Outline
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 3 / 69
Overview
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 4 / 69
Decrease-and-conquer Approach
Process:
1 Reduce a problem instance to a smaller instance of the same
problem.
2 Solve the smaller instance.
3 Extend the solution of the smaller instance to obtain the solution
to the original instance.
• Sometimes referred to as the inductive or incremental approach.
(RMIT University) Decrease and Conquer Lecture 5 5 / 69
Decrease-and-conquer Approach
(RMIT University) Decrease and Conquer Lecture 5 6 / 69
Decrease-and-Conquer – Examples
1 Decrease-by-a-constant
• Insertion Sorting
• Topological Sorting
• Algorithms for generating permutations and subsets
2 Decrease-by-a-constant-factor
• Binary Search
• Fake-coin Problem
• Multiplication à la russe
• Josephus Problem
3 Variable-size-decrease
• Search, Insert and Delete in a Binary Search Tree
• Euclid’s Algorithm
• Interpolation Search
• Selection by Partitioning
• Game of Nim
(RMIT University) Decrease and Conquer Lecture 5 7 / 69
Overview
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 8 / 69
Insertion Sort – Sketch
Insertion sort is the method people often use to sort a hand of playing
cards. The basic idea:
• Consider each element one at a time (left to right).
• Insert each element in its proper place among those already
considered. (i.e. insert into a already sorted sub-file). This is a
right to left scan.
(RMIT University) Decrease and Conquer Lecture 5 9 / 69
Insertion Sort – Sketch
Insertion sort is the method people often use to sort a hand of playing
cards. The basic idea:
• Consider each element one at a time (left to right).
• Insert each element in its proper place among those already
considered. (i.e. insert into a already sorted sub-file). This is a
right to left scan.
(RMIT University) Decrease and Conquer Lecture 5 9 / 69
Insertion Sort – Example
34 53 21 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
34 53 21 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
34 53 21 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
34 53 21 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
34 53 21 9 12 37 75 4 47 18 27 57 1 68 88 1134 53 21 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
21 34 53 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
21 34 53 9 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
9 21 34 53 12 37 75 4 47 18 27 57 1 68 88 11
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Example
4 9 12 21 34 37 53 75 47 18 27 57 1 68 88 11
insert
unsortedsorted
(RMIT University) Decrease and Conquer Lecture 5 10 / 69
Insertion Sort – Pseudocode
ALGORITHM InsertionSort (A[0 . . . n − 1])
/* Sort an array using an insertion sort. */
/* INPUT : An array A[0 . . . n − 1] of orderable elements. */
/* OUTPUT : An array A[0 . . . n − 1] sorted in order. */
1: for i = 1 to n − 1 do
2: v = A[i]
3: j = i − 1
4: while j ≥ 0 and A[j] > v do
5: A[j + 1] = A[j]
6: j = j − 1
7: end while
8: A[j + 1] = v
9: end for
(RMIT University) Decrease and Conquer Lecture 5 11 / 69
Insertion Sort – Analysis
• Worst Case : The input is in reverse order.
Cw (n) =
n−1∑
i=1
i−1∑
j=0
1 =
n−1∑
i=1
i =
(n − 1)n
2
∈ O(n2)
• Average Case : For randomly ordered data, we expect each item
to move halfway back.
Ca(n) ≈
n2
4
∈ O(n2)
• : Next slide
(RMIT University) Decrease and Conquer Lecture 5 12 / 69
Insertion Sort – Analysis
• Worst Case : The input is in reverse order.
Cw (n) =
n−1∑
i=1
i−1∑
j=0
1 =
n−1∑
i=1
i =
(n − 1)n
2
∈ O(n2)
• Average Case : For randomly ordered data, we expect each item
to move halfway back.
Ca(n) ≈
n2
4
∈ O(n2)
• : Next slide
(RMIT University) Decrease and Conquer Lecture 5 12 / 69
Insertion Sort – Analysis
:
1 In terms of the input, what is the scenario/circumstance where we
can achieve the best case?
2 What is the time complexity for the best case?
(RMIT University) Decrease and Conquer Lecture 5 13 / 69
Useful websites
Interesting and useful sorting visualisation website:
https://visualgo.net/bn/sorting
(RMIT University) Decrease and Conquer Lecture 5 14 / 69
https://visualgo.net/bn/sorting
Overview
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 15 / 69
Topological Sort
Imagine we have the following problems:
Job scheduling with
order dependencies:
What is the order the
jobs should be
processed to avoid
breaking these
dependencies?
Subject selection with
pre-requisites: What is
the order the subjects
could be taken to
ensure we have all the
pre-requisites?
Makefile compilation:
What is the order the
source files should be
compiled to ensure we
can build a working
program?
(RMIT University) Decrease and Conquer Lecture 5 16 / 69
Topological Sort
Imagine we have the following problems:
Job scheduling with
order dependencies:
What is the order the
jobs should be
processed to avoid
breaking these
dependencies?
Subject selection with
pre-requisites: What is
the order the subjects
could be taken to
ensure we have all the
pre-requisites?
Makefile compilation:
What is the order the
source files should be
compiled to ensure we
can build a working
program?
(RMIT University) Decrease and Conquer Lecture 5 16 / 69
Topological Sort
Imagine we have the following problems:
Job scheduling with
order dependencies:
What is the order the
jobs should be
processed to avoid
breaking these
dependencies?
Subject selection with
pre-requisites: What is
the order the subjects
could be taken to
ensure we have all the
pre-requisites?
Makefile compilation:
What is the order the
source files should be
compiled to ensure we
can build a working
program?
(RMIT University) Decrease and Conquer Lecture 5 16 / 69
Topological Sort
Topological sort produces a traversal ordering of the vertices/nodes for
directed graphs.
Topological Sorting Problem
Given a digraph, list its vertices in such an order that for every edge
(a,b) in the graph, vertex a must appear before vertex b in the list.
NOTE : If the graph is a directed acyclic graph (DAG), the topological
sort has at least one solution.
(RMIT University) Decrease and Conquer Lecture 5 17 / 69
Topological Sort
Topological sort produces a traversal ordering of the vertices/nodes for
directed graphs.
Topological Sorting Problem
Given a digraph, list its vertices in such an order that for every edge
(a,b) in the graph, vertex a must appear before vertex b in the list.
NOTE : If the graph is a directed acyclic graph (DAG), the topological
sort has at least one solution.
(RMIT University) Decrease and Conquer Lecture 5 17 / 69
Topological Sort
Topological sort produces a traversal ordering of the vertices/nodes for
directed graphs.
Topological Sorting Problem
Given a digraph, list its vertices in such an order that for every edge
(a,b) in the graph, vertex a must appear before vertex b in the list.
NOTE : If the graph is a directed acyclic graph (DAG), the topological
sort has at least one solution.
(RMIT University) Decrease and Conquer Lecture 5 17 / 69
Topological Sort
Topological sort produces a traversal ordering of the vertices/nodes for
directed graphs.
Topological Sorting Problem
Given a digraph, list its vertices in such an order that for every edge
(a,b) in the graph, vertex a must appear before vertex b in the list.
NOTE : If the graph is a directed acyclic graph (DAG), the topological
sort has at least one solution.
(RMIT University) Decrease and Conquer Lecture 5 17 / 69
Topological Sort – Applications
Imagine we have the following problems:
Job scheduling with
order dependencies:
What is the order the
jobs should be
processed to avoid
breaking these
dependencies?
Subject selection with
pre-requisites: What
are the order the
subjects could be
taken to ensure we
have all the
pre-requisites?
Makefile compilation:
What is the order the
source files should be
compiled to ensure we
can build a working
program?
(RMIT University) Decrease and Conquer Lecture 5 18 / 69
Topological Sort – Approaches
There are two different approaches to solve this problem:
1 DFS Method
2 Source Removal Method (focus of this lecture)
(RMIT University) Decrease and Conquer Lecture 5 19 / 69
Topological Sort – Source Removal Method
Idea: Select next vertex in ordering that respect the (a,b) ordering. If
we can find a vertex a that does not have any incoming vertex, than it
cannot violate the property. Such a vertex is a source vertex (one that
has no incoming vertices).
Source Removal Method:
• Choose a source vertex.
• Delete the vertex and all incident edges and append the vertex to
topological ordered list.
• Repeat the selection of a source vertex and deletion process for
the remaining graph until no vertices are left.
(RMIT University) Decrease and Conquer Lecture 5 20 / 69
Topological Sort – Source Removal Method
Idea: Select next vertex in ordering that respect the (a,b) ordering. If
we can find a vertex a that does not have any incoming vertex, than it
cannot violate the property. Such a vertex is a source vertex (one that
has no incoming vertices).
Source Removal Method:
• Choose a source vertex.
• Delete the vertex and all incident edges and append the vertex to
topological ordered list.
• Repeat the selection of a source vertex and deletion process for
the remaining graph until no vertices are left.
(RMIT University) Decrease and Conquer Lecture 5 20 / 69
Topological Sort – Source Removal Method
B
A
E
C
F
D
Solution :
(RMIT University) Decrease and Conquer Lecture 5 21 / 69
Topological Sorting – Source Removal Method
B
E
C
F
D
Solution : A
(RMIT University) Decrease and Conquer Lecture 5 22 / 69
Topological Sorting – Source Removal Method
E
C
F
D
Solution : A B
(RMIT University) Decrease and Conquer Lecture 5 23 / 69
Topological Sorting – Source Removal Method
C
F
D
Solution : A B E
(RMIT University) Decrease and Conquer Lecture 5 24 / 69
Topological Sorting – Source Removal Method
F
D
Solution : A B E C
(RMIT University) Decrease and Conquer Lecture 5 25 / 69
Topological Sorting – Source Removal Method
F
Solution : A B E C D
(RMIT University) Decrease and Conquer Lecture 5 26 / 69
Topological Sorting – Source Removal Method
Solution : A B E C D F
(RMIT University) Decrease and Conquer Lecture 5 27 / 69
Topological Sorting – Summary & Questions
• Topological sorting can have more than one solution, and often
does for very large DAGs.
• Source removal algorithm:
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency matrix? What is the
time efficiency? (Homework)
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency list? What is the
time efficiency? (Homework)
• The source removal algorithm for a digraph represented as an
adjacency list can be implemented such that the running time is
O(|V |+ |E |). How? (Homework)
(RMIT University) Decrease and Conquer Lecture 5 28 / 69
Topological Sorting – Summary & Questions
• Topological sorting can have more than one solution, and often
does for very large DAGs.
• Source removal algorithm:
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency matrix? What is the
time efficiency? (Homework)
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency list? What is the
time efficiency? (Homework)
• The source removal algorithm for a digraph represented as an
adjacency list can be implemented such that the running time is
O(|V |+ |E |). How? (Homework)
(RMIT University) Decrease and Conquer Lecture 5 28 / 69
Topological Sorting – Summary & Questions
• Topological sorting can have more than one solution, and often
does for very large DAGs.
• Source removal algorithm:
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency matrix? What is the
time efficiency? (Homework)
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency list? What is the
time efficiency? (Homework)
• The source removal algorithm for a digraph represented as an
adjacency list can be implemented such that the running time is
O(|V |+ |E |). How? (Homework)
(RMIT University) Decrease and Conquer Lecture 5 28 / 69
Topological Sorting – Summary & Questions
• Topological sorting can have more than one solution, and often
does for very large DAGs.
• Source removal algorithm:
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency matrix? What is the
time efficiency? (Homework)
• How do you find a source (or determine that such a vertex does not
exist) in a digraph represented by an adjacency list? What is the
time efficiency? (Homework)
• The source removal algorithm for a digraph represented as an
adjacency list can be implemented such that the running time is
O(|V |+ |E |). How? (Homework)
(RMIT University) Decrease and Conquer Lecture 5 28 / 69
Overview
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 29 / 69
Decrease-by-a-constant-factor Approaches
Algorithms that use this approach divide the problem into parts (half,
thirds, etc), and then recursively operate on one of the halves, thirds
etc.
Hence, at each iteration, we decrease the problem by a constant (a
half, a third etc).
We study two examples:
• Binary search
• Fake coin problem
(RMIT University) Decrease and Conquer Lecture 5 30 / 69
Decrease-by-a-constant-factor Approaches
Algorithms that use this approach divide the problem into parts (half,
thirds, etc), and then recursively operate on one of the halves, thirds
etc.
Hence, at each iteration, we decrease the problem by a constant (a
half, a third etc).
We study two examples:
• Binary search
• Fake coin problem
(RMIT University) Decrease and Conquer Lecture 5 30 / 69
Binary Search
Binary search is a worst-case optimal algorithm for searching in a
sorted sequence of elements.
• Given a sorted sequence, compare the value in the array at
position n/2 with a key k .
• If A[n/2] > k , compare k with the midpoint of the lower half.
• If A[n/2] < k , compare k with the midpoint of the upper half.
• If A[n/2] = k , return n/2 (the index of the position containing k ).
(RMIT University) Decrease and Conquer Lecture 5 31 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
BINARYSEARCH(5)
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
5 < 35
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
Continue left
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
5 < 9
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search - Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
5 > 3
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search – Example
1 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 921 3 5 9 12 24 29 34 35 37 53 62 74 53 62 74 92
FOUND!
(RMIT University) Decrease and Conquer Lecture 5 32 / 69
Binary Search – Recursive
ALGORITHM RecursiveBinarySearch (A[` . . . r ], k)
/* A recursive binary search in an ordered array. */
/* INPUT : An array A[` . . . r ] of ordered elements, and a search key k . */
/* OUTPUT : an index to the position of k in A if k is found or −1 otherwise. */
1: if ` > r then
2: return −1
3: else
4: m← b(`+ r)/2c
5: if k = A[m] then
6: return m
7: else if k < A[m] then
8: return RecursiveBinarySearch (A[` . . .m − 1], k)
9: else
10: return RecursiveBinarySearch (A[m + 1 . . . r ], k)
11: end if
12: end if
(RMIT University) Decrease and Conquer Lecture 5 33 / 69
Analysis - Binary Search
1. C(n) = C(bn/2c) + 1 for n > 1 and C(1) = 1.
2. Using the smoothness rule, n = 2k .
3. C(2k ) = C(2k−1) + 1 for k > 0, C(20) = C(1) = 1.
4. Substitute C(2k−1) = C(2k−2) + 1.
5. C(2k ) = [C(2k−2) + 1] + 1 = C(2k−2) + 2.
6. Substitute C(2k−2) = C(2k−3) + 1.
7. C(2k ) = [C(2k−3) + 1] + 2 = C(2k−3) + 3.
8. We see the pattern C(2k ) = C(2k−i) + i emerge.
9. C(2k ) = C(2k−i) + i .
10. We want C(2k−i) = C(20), or k − i = 0 or i = k .
11. C(2k ) = C(2k−k ) + k = C(20) + k = 1 + k .
12. If n = 2k then k = log2 n:
13. C(n) = log2 n + 1 ∈ O(log2 n).
(RMIT University) Decrease and Conquer Lecture 5 34 / 69
Binary Search Properties
Worst case of O(log(n))
Only achieved if:
• Array is sorted.
• The array has O(1) access to any position.
(RMIT University) Decrease and Conquer Lecture 5 35 / 69
Binary Search Properties
Worst case of O(log(n))
Only achieved if:
• Array is sorted.
• The array has O(1) access to any position.
(RMIT University) Decrease and Conquer Lecture 5 35 / 69
Fake-Coin Problem
Fake-Coin Problem
Given a stack of n identical-looking coins which contains exactly one
fake coin (which is lighter) and a scale/weigh, devise an efficient
algorithm for detecting the fake coin.
(RMIT University) Decrease and Conquer Lecture 5 36 / 69
Fake-Coin Problem
Fake-Coin Problem
Given a stack of n identical-looking coins which contains exactly one
fake coin (which is lighter) and a scale/weigh, devise an efficient
algorithm for detecting the fake coin.
The solution is to use a decrease by half algorithm:
• Divide into two sub-stacks of n/2 coins and weigh on scale.
• The lighter sub-stack contains the fake coin.
• Repeat process with the lighter sub-stack until we have two coins
remaining. The fake coin must be one of the two.
The recurrence relation for number of weighings: C(n) = C(bn/2c) + 1
for n > 1, C(1) = 0. Gives worst case of Olog2(n).
(RMIT University) Decrease and Conquer Lecture 5 37 / 69
Fake-Coin Problem
Fake-Coin Problem
Given a stack of n identical-looking coins which contains exactly one
fake coin (which is lighter) and a scale/weigh, devise an efficient
algorithm for detecting the fake coin.
The solution is to use a decrease by half algorithm:
• Divide into two sub-stacks of n/2 coins and weigh on scale.
• The lighter sub-stack contains the fake coin.
• Repeat process with the lighter sub-stack until we have two coins
remaining. The fake coin must be one of the two.
The recurrence relation for number of weighings: C(n) = C(bn/2c) + 1
for n > 1, C(1) = 0. Gives worst case of Olog2(n).
(RMIT University) Decrease and Conquer Lecture 5 37 / 69
Fake-Coin Problem
Fake-Coin Problem
Given a stack of n identical-looking coins which contains exactly one
fake coin (which is lighter) and a scale/weigh, devise an efficient
algorithm for detecting the fake coin.
The solution is to use a decrease by half algorithm:
• Divide into two sub-stacks of n/2 coins and weigh on scale.
• The lighter sub-stack contains the fake coin.
• Repeat process with the lighter sub-stack until we have two coins
remaining. The fake coin must be one of the two.
The recurrence relation for number of weighings: C(n) = C(bn/2c) + 1
for n > 1, C(1) = 0. Gives worst case of Olog2(n).
(RMIT University) Decrease and Conquer Lecture 5 37 / 69
Fake-Coin Problem – Example
(RMIT University) Decrease and Conquer Lecture 5 38 / 69
Overview
1 Overview
2 Decrease-by-a-Constant: Insertion Sort
3 Decrease-by-a-Constant: Topological Sorting
4 Decrease-by-a-Constant-Factor Algorithms
5 Variable-Size Decrease Algorithms & Binary Search Trees
6 Case Study
7 Summary
(RMIT University) Decrease and Conquer Lecture 5 39 / 69
Trees
In its most general form, a tree is a connected acyclic graph.
There are many different types of trees used in computer science:
• binary trees
• m-ary search trees
• balanced trees (AVL, Red-Black)
• forests
• Kd-tree
Here we focus on binary search trees.
(RMIT University) Decrease and Conquer Lecture 5 40 / 69
Binary Tree
A binary tree is:
• a tree (hence has a root node)
• every vertex has no more than two children
Each child is designated as either a left child or a right child of its
parent
Technical point: If a node does not have a child, the pointer/reference
to the child is set to null.
(RMIT University) Decrease and Conquer Lecture 5 41 / 69
Binary Tree
A binary tree is:
• a tree (hence has a root node)
• every vertex has no more than two children
Each child is designated as either a left child or a right child of its
parent
Technical point: If a node does not have a child, the pointer/reference
to the child is set to null.
(RMIT University) Decrease and Conquer Lecture 5 41 / 69
Binary Tree
A binary tree is:
• a tree (hence has a root node)
• every vertex has no more than two children
Each child is designated as either a left child or a right child of its
parent
Technical point: If a node does not have a child, the pointer/reference
to the child is set to null.
(RMIT University) Decrease and Conquer Lecture 5 41 / 69
Binary Tree
A binary tree is:
• a tree (hence has a root node)
• every vertex has no more than two children
Each child is designated as either a left child or a right child of its
parent
Technical point: If a node does not have a child, the pointer/reference
to the child is set to null.
(RMIT University) Decrease and Conquer Lecture 5 41 / 69
Binary Search Tree
A binary search tree is a binary tree that additionally:
• have values associated with each node
• ordered such that for each parent vertex:
• all values in its left subtree are smaller than the parent’s value; and
• all values in its right subtree are larger than the parent’s value.
16
6
4
1 5
12
8 15
26
20
18 25
28
27 30
Example of a balanced, full binary
search tree.
30
28
27
26
Example of a unbalanced, “stick”
binary search tree.
(RMIT University) Decrease and Conquer Lecture 5 42 / 69
Binary Search Tree
A binary search tree is a binary tree that additionally:
• have values associated with each node
• ordered such that for each parent vertex:
• all values in its left subtree are smaller than the parent’s value; and
• all values in its right subtree are larger than the parent’s value.
16
6
4
1 5
12
8 15
26
20
18 25
28
27 30
Example of a balanced, full binary
search tree.
30
28
27
26
Example of a unbalanced, “stick”
binary search tree.
(RMIT University) Decrease and Conquer Lecture 5 42 / 69
BST Properties
• The height of a tree is the length of the path from the root to the
deepest node in a tree. A tree with only a root node has a height
of 0.
• The depth of a node is the length of the path from the root to the
node. The root node has a depth 0.
• The level of a tree is the set of all nodes at a given depth.
(RMIT University) Decrease and Conquer Lecture 5 43 / 69
BST Properties – Example
16
6
4
1 5
12
8 15
26
20
18 25
28
27 30 —
—
—
—
3
2
1
0
• Height = 3
• Depth of node 12 = 2
• Depth of node 18 = 3
• Nodes in level 1 = {6, 26}
(RMIT University) Decrease and Conquer Lecture 5 44 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height?
4
• Nodes on Level 2? {12, 20, 28}
• Depth of node 27? 3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height? 4
• Nodes on Level 2? {12, 20, 28}
• Depth of node 27? 3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height? 4
• Nodes on Level 2?
{12, 20, 28}
• Depth of node 27? 3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height? 4
• Nodes on Level 2? {12, 20, 28}
• Depth of node 27? 3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height? 4
• Nodes on Level 2? {12, 20, 28}
• Depth of node 27?
3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST Properties – Example
16
6
12
8
7
26
20 28
27
• Root is node 16.
• Height? 4
• Nodes on Level 2? {12, 20, 28}
• Depth of node 27? 3
(RMIT University) Decrease and Conquer Lecture 5 45 / 69
BST algorithms
• Searching for a value in a BST (variable-size-decrease)
• Inserting a new value into a BST (variable-size-decrease)
• Deleting a value and associated node from a BST
(RMIT University) Decrease and Conquer Lecture 5 46 / 69
BST Search
Aim: Search for a key k in tree T (represented by its root node).
Idea: Recursively search for the key k in tree, taking advantage of its
structure.
Search(T , k ):
1 If T is empty, return null.
2 If value of k = val(T ), return T.
3 If value of k < val(T ), search the left subtree (return Search(TL,
k ))
4 If value of k > val(T ), search the right subtree (return Search(TR,
k ))
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 47 / 69
BST Search
Aim: Search for a key k in tree T (represented by its root node).
Idea: Recursively search for the key k in tree, taking advantage of its
structure.
Search(T , k ):
1 If T is empty, return null.
2 If value of k = val(T ), return T.
3 If value of k < val(T ), search the left subtree (return Search(TL,
k ))
4 If value of k > val(T ), search the right subtree (return Search(TR,
k ))
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 47 / 69
BST Search
Aim: Search for a key k in tree T (represented by its root node).
Idea: Recursively search for the key k in tree, taking advantage of its
structure.
Search(T , k ):
1 If T is empty, return null.
2 If value of k = val(T ), return T.
3 If value of k < val(T ), search the left subtree (return Search(TL,
k ))
4 If value of k > val(T ), search the right subtree (return Search(TR,
k ))
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 47 / 69
BST Search
Aim: Search for a key k in tree T (represented by its root node).
Idea: Recursively search for the key k in tree, taking advantage of its
structure.
Search(T , k ):
1 If T is empty, return null.
2 If value of k = val(T ), return T.
3 If value of k < val(T ), search the left subtree (return Search(TL,
k ))
4 If value of k > val(T ), search the right subtree (return Search(TR,
k ))
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 47 / 69
BST Search
9
5
2
1 3
7
6 8
15
10
13
23
19 27
Query: 6
(RMIT University) Decrease and Conquer Lecture 5 48 / 69
BST Search
9
5
2
1 3
7
6 8
15
10
13
23
19 27
Query: 6
(RMIT University) Decrease and Conquer Lecture 5 49 / 69
BST Search
9
5
2
1 3
7
6 8
15
10
13
23
19 27
Query: 6
(RMIT University) Decrease and Conquer Lecture 5 50 / 69
BST Search
9
5
2
1 3
7
6 8
15
10
13
23
19 27
Query: 6
(RMIT University) Decrease and Conquer Lecture 5 51 / 69
BST Search
9
5
2
1 3
7
6 8
15
10
13
23
19 27
Query: 6
(RMIT University) Decrease and Conquer Lecture 5 52 / 69
Recursive BST Search
ALGORITHM BSTSearch(T , k)
// Recursive search in a binary tree.
// INPUT : Root node T of a BST and a search key k .
// OUTPUT : A reference to the node containing k or null.
1: if T = null or k = val(T ) then
2: return T
3: end if
4: if k < val(T ) then
5: return BSTSearch(TL, k)
6: else
7: return BSTSearch(TR , k)
8: end if
(RMIT University) Decrease and Conquer Lecture 5 53 / 69
BST Search - Complexity
Worst case complexity?
O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better?
Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Search - Complexity
Worst case complexity? O(n)
Can we do better? Yes if tree is balanced!
Worst case complexity is dependent on the height of the tree.
If tree is a “stick”, height = n − 1
If tree is balanced, height = log2 n
(RMIT University) Decrease and Conquer Lecture 5 54 / 69
BST Insert
Aim: Insert key/value k into tree T (represented by its root node).
Idea: Recursively traverse the tree to find a position for the key k in T .
Insert(T , k ):
1 If T is empty, place k at this position.
2 If k < val(T ), traverse into the left subtree (Insert(TL, k )).
3 If k > val(T ), traverse into the right subtree (Insert(TR, k )).
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 55 / 69
BST Insert
Aim: Insert key/value k into tree T (represented by its root node).
Idea: Recursively traverse the tree to find a position for the key k in T .
Insert(T , k ):
1 If T is empty, place k at this position.
2 If k < val(T ), traverse into the left subtree (Insert(TL, k )).
3 If k > val(T ), traverse into the right subtree (Insert(TR, k )).
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 55 / 69
BST Insert
Aim: Insert key/value k into tree T (represented by its root node).
Idea: Recursively traverse the tree to find a position for the key k in T .
Insert(T , k ):
1 If T is empty, place k at this position.
2 If k < val(T ), traverse into the left subtree (Insert(TL, k )).
3 If k > val(T ), traverse into the right subtree (Insert(TR, k )).
NOTE : This is a variable-size-decrease algorithm, as each iteration we
decrease the remaining problem size by a variable amount.
(RMIT University) Decrease and Conquer Lecture 5 55 / 69
BST Insert
54
27
13
1
44
37
89
71 92
Insert: 64
(RMIT University) Decrease and Conquer Lecture 5 56 / 69
BST Insert
54
27
13
1
44
37
89
71 92
64 > 54→ rightInsert: 64
(RMIT University) Decrease and Conquer Lecture 5 57 / 69
BST Insert
54
27
13
1
44
37
89
71 92
64 > 54→ right
64 < 89→ left Insert: 64 (RMIT University) Decrease and Conquer Lecture 5 58 / 69 BST Insert 54 27 13 1 44 37 89 71 64 92 64 > 54→ right
64 < 89→ left 64 < 71→ insert left Insert: 64 (RMIT University) Decrease and Conquer Lecture 5 59 / 69 BST Delete Aim: Remove or delete a node from a BST. Idea: It can be solved using one of three cases: • Case 1 : The deleted node has no children. • Case 2 : The deleted node has one child. • Case 3 : The deleted node has two children. (RMIT University) Decrease and Conquer Lecture 5 60 / 69 BST Delete Aim: Remove or delete a node from a BST. Idea: It can be solved using one of three cases: • Case 1 : The deleted node has no children. • Case 2 : The deleted node has one child. • Case 3 : The deleted node has two children. (RMIT University) Decrease and Conquer Lecture 5 60 / 69 BST Delete 5 2 1 3 7 6 1 If the deleted node is the root of a single-node tree, make the tree empty. 2 If the deleted node is a leaf node, set the reference from its parent to the itself to null. Case 1 : Deleted node has no children Delete: 3 (RMIT University) Decrease and Conquer Lecture 5 61 / 69 BST Delete 54 27 13 1 44 37 89 71 64 1 If the deleted node is the root node with a single child, make the child the new root. 2 If the deleted node is not the root, make the reference from its parent to point to its single child. Case 2 : Deleted node has one child Delete: 89 (RMIT University) Decrease and Conquer Lecture 5 62 / 69 BST Delete 9 5 2 1 3 15 10 13 23 19 27 Use the following three-stage procedure: 1 First, find the node k ′ which contains the smallest key in the right subtree. 2 Second, exchange the deleted node and node k ′. 3 Third, remove the deleted node from its new position by using either Case 1 or Case 2, depending on whether that node is a leaf (no children) or has a single child. Case 3: Deleted node has two childrenDelete: 15 9 5 2 1 3 19 10 13 23 15 27 (RMIT University) Decrease and Conquer Lecture 5 63 / 69 Overview 1 Overview 2 Decrease-by-a-Constant: Insertion Sort 3 Decrease-by-a-Constant: Topological Sorting 4 Decrease-by-a-Constant-Factor Algorithms 5 Variable-Size Decrease Algorithms & Binary Search Trees 6 Case Study 7 Summary (RMIT University) Decrease and Conquer Lecture 5 64 / 69 Case Study - Problem Case Study Problem Easy-as-123 University has used experienced course advisors to build valid study plans for their students. But they want to explore more automated approaches to help their advisors to quickly devise valid plans. Given courses and their pre-requisites, they want a tool that can produce valid study plans that a student can only study a course if they have satisfy the pre-requisites already. They asked you to help them. How would you approach this problem? (RMIT University) Decrease and Conquer Lecture 5 65 / 69 Case Study - Mapping the Problem to a Known Problem This can be mapped into a graph problem. Each course is a vertex in the graph. Each pre-requisite is a directed edge, from the pre-requisite to the course requiring it. (RMIT University) Decrease and Conquer Lecture 5 66 / 69 Case Study - Solving the Problem A valid plan is a vertex traversal and one that satisfies and respects all the edge directions. This is exactly the properties that a topological sort has. We can use DFS or source removal algorithm to solve this. Is it possible to have more than one valid plan? (RMIT University) Decrease and Conquer Lecture 5 67 / 69 Overview 1 Overview 2 Decrease-by-a-Constant: Insertion Sort 3 Decrease-by-a-Constant: Topological Sorting 4 Decrease-by-a-Constant-Factor Algorithms 5 Variable-Size Decrease Algorithms & Binary Search Trees 6 Case Study 7 Summary (RMIT University) Decrease and Conquer Lecture 5 68 / 69 Summary • Introduced the Decrease-and-conquer algorithmic approach. • Decrease-by-a-constant algorithms (Insertion sorting and Topological sort). • Decrease-by-a-constant-factor algorithms (Binary search, Fake coin). • Variable-size decrease algorithms (Binary search tree). (RMIT University) Decrease and Conquer Lecture 5 69 / 69 Overview Decrease-by-a-Constant: Insertion Sort Decrease-by-a-Constant: Topological Sorting Decrease-by-a-Constant-Factor Algorithms Variable-Size Decrease Algorithms & Binary Search Trees Case Study Summary