USA: +1(669)289-8683 
Sign in
Here is teh question. I need detailed and step by step answer as per guideline.
270-1/02-divide-and-conquer_handout
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Week 2
Divide and Conquer
1 Growth of Functions
2 Divide-and-Conquer
Min-Max-Problem
3 Tutorial
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
General remarks
First we consider an important tool for the analysis of
algorithms: Big-Oh.
Then we introduce an important algorithmic paradigm:
Divide-and-Conquer.
We conclude by presenting and analysing a simple example.
Reading from CLRS for week 2
Chapter 2, Section 3
Chapter 3
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Growth of Functions
A way to describe behaviour of functions in the limit. We
are studying asymptotic efficiency.
Describe growth of functions.
Focus on what’s important by abstracting away low-order
terms and constant factors.
How we indicate running times of algorithms.
A way to compare “sizes” of functions:
O corresponds to ≤
Ω corresponds to ≥
Θ corresponds to =
We consider only functions f , g : N → R
≥0
.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
O-Notation
O
(
g(n)
)
is the set of all functions f (n) for which there are
positive constants c and n0 such that
f (n) ≤ cg(n) for all n ≥ n0.
cg(n)
f (n)
n
n0
g(n) is an asymptotic upper bound for f (n).
If f (n) ∈ O(g(n)), we write f (n) = O(g(n)) (we will precisely
explain this soon)
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
O-Notation Examples
2n2 = O(n3), with c = 1 and n0 = 2.
Example of functions in O(n2):
n2
n2 + n
n2 + 1000n
1000n2 + 1000n
Also
n
n/1000
n1.999999
n2/ lg lg lg n
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Ω-Notation
Ω
(
g(n)
)
is the set of all functions f (n) for which there are
positive constants c and n0 such that
f (n) ≥ cg(n) for all n ≥ n0.
cg(n)
f (n)
n
n0
g(n) is an asymptotic lower bound for f (n).
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Ω-Notation Examples
√
n = Ω(lg n), with c = 1 and n0 = 16.
Example of functions in Ω(n2):
n2
n2 + n
n2 − n
1000n2 + 1000n
1000n2 − 1000n
Also
n3
n2.0000001
n2 lg lg lg n
22
n
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Θ-Notation
Θ
(
g(n)
)
is the set of all functions f (n) for which there are
positive constants c1, c2 and n0 such that
c1g(n) ≤ f (n) ≤ c2g(n) for all n ≥ n0.
c2g(n)
c1g(n)
f (n)
n
n0
g(n) is an asymptotic tight bound for f (n).
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Θ-Notation (cont’d)
Examples 1
n2/2− 2n = Θ(n2), with c1 =
1
4
, c2 =
1
2
, and n0 = 8.
Theorem 2
f (n) = Θ(g(n)) if and only if f (n) = O(g(n)) and
f (n) = Ω(g(n)).
Leading constants and lower order terms do not matter.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Asymptotic notation in equations
When on right-hand side
Θ(n2) stands for some anonymous function in the set Θ(n2).
2n2 + 3n + 1 = 2n2 +Θ(n) means 2n2 + 3n + 1 = 2n2 + f (n)
for some f (n) ∈ Θ(n). In particular, f (n) = 3n + 1.
When on left-hand side
No matter how the anonymous functions are chosen on the
left-hand side, there is a way to choose the anonymous functions
on the right-hand side to make the equation valid.
Interpret 2n2 +Θ(n) = Θ(n2) as meaning for all functions
f (n) ∈ Θ(n), there exists a function g(n) ∈ Θ(n2) such that
2n2 + f (n) = g(n).
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Asymptotic notation chained together
2n2 + 3n + 1 = 2n2 +Θ(n) = Θ(n2)
Interpretation:
First equation: There exists f (n) ∈ Θ(n) such that
2n2 + 3n + 1 = 2n2 + f (n).
Second equation: For all g(n) ∈ Θ(n) (such as the f (n)
used to make the first equation hold), there exists
h(n) ∈ Θ(n2) such that 2n2 + g(n) = h(n).
Note
What has been said of “Θ” on this and the previous slide also
applies to “O” and “Ω”.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Example Analysis
Insertion-Sort(A)
1 for j = 2 to A. length
2 key = A[j ]
3 // Insert A[j ] into sorted sequence A[1 . . j−1].
4 i = j−1
5 while i > 0 and A[i ] > key
6 A[i+1] = A[i ]
7 i = i−1
8 A[i+1] = key
The for -loop on line 1 is executed O(n) times; and each
statement costs constant time, except for the while -loop on
lines 5-7 which costs O(n).
Thus overall runtime is: O(n)×O(n) = O(n2).
Note: In fact, as seen last week, worst-case runtime is Θ(n2).
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Divide-and-Conquer Approach
There are many ways to design algorithms.
For example, insertion sort is incremental: having sorted
A[1 . . j−1], place A[j ] correctly, so that A[1 . . j ] is sorted.
Divide-and-Conquer is another common approach:
Divide the problem into a number of subproblems that are
smaller instances of the same problem.
Conquer the subproblems by solving them recursively.
Base case: If the subproblem are small enough, just solve
them by brute force.
Combine the subproblem solutions to give a solution to the
original problem.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Naive Min-Max
Find minimum and maximum of a list A of n>0 numbers.
Naive-Min-Max(A)
1 least = A[1]
2 for i = 2 to A. length
3 if A[i ] < least
4 least = A[i ]
5 greatest = A[1]
6 for i = 2 to A. length
7 if A[i ] > greatest
8 greatest = A[i ]
9 return (least, greatest)
The for-loop on line 2 makes n−1 comparisons, as does the
for-loop on line 6, making a total of 2n−2 comparisons.
Can we do better? Yes!
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Divide-and-Conquer Min-Max
As we are dealing with subproblems, we state each subproblem
as computing minimum and maximum of a subarray A[p . . q].
Initially, p = 1 and q = A. length, but these values change as we
recurse through subproblems.
To compute minimum and maximum of A[p . . q]:
Divide by splitting into two subarrays A[p . . r ] and A[r+1 . . q],
where r is the halfway point of A[p . . q].
Conquer by recursively computing minimum and maximum of
the two subarrays A[p . . r ] and A[r+1 . . q].
Combine by computing the overall minimum as the min of the
two recursively computed minima, similar for the overall
maximum.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Divide-and-Conquer Min-Max Algorithm
Initially called with Min-Max(A, 1,A. length).
Min-Max(A, p, q)
1 if p = q
2 return (A[p],A[q])
3 if p = q−1
4 if A[p] < A[q]
5 return (A[p],A[q])
6 else return (A[q],A[p])
7 r = ⌊(p+q)/2⌋
8 (min1,max1) = Min-Max(A, p, r)
9 (min2,max2) = Min-Max(A, r+1, q)
10 return
(
min(min1,min2),max(max1,max2)
)
Note
In line 7, r computes the halfway point of A[p . . q].
n = q − p + 1 is the number of elements from which we compute
the min and max.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Solving the Min-Max Recurrence
Let T (n) be the number of comparisons made by
Min-Max(A, p, q), where n = q−p+1 is the number of
elements from which we compute the min and max.
Then T (1) = 0, T (2) = 1, and for n > 2:
T (n) = T (⌈n/2⌉) + T (⌊n/2⌋) + 2.
Claim
T (n) = 3
2
n − 2 for n = 2k ≥ 2, i.e., powers of 2.
Proof.
The proof is by induction on k (using n = 2k).
Base case: true for k=1, as T (21) = 1 = 3
2
· 21 − 2.
Induction step: assuming T (2k) = 3
2
2k − 2, we get
T (2k+1) = 2T (2k)+2 = 2
(
3
2
2k−2
)
+2 = 3
2
2k+1−2
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Solving the Min-Max Recurrence (cont’d)
Some remarks:
1 If we replace line 7 of the algorithm by r = p+1, then the
resulting runtime T ′(n) satisfies T ′(n) =
⌈
3n
2
⌉
−2 for all
n > 0.
2 For example, T ′(6) = 7 whereas T (6) = 8.
3 It can be shown that at least
⌈
3n
2
⌉
− 2 comparisons are
necessary in the worst case to find the maximum and
minimum of n numbers for any comparison-based
algorithm: this is thus a lower bound on the problem.
4 Hence this (last) algorithm is provably optimal.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Big-Oh, Omega, Theta by examples
1 5n + 111 = O(n) ? YES
2 5n + 111 = O(n2) ? YES
3 5n + 111 = Ω(n) ? YES
4 5n + 111 = Ω(n2) ? NO
5 5n + 111 = Θ(n) ? YES
6 5n + 111 = Θ(n2) ? NO
7 2n = O(3n) ? YES
8 2n = Ω(3n) ? NO
9 120n2 +
√
n + 99n = O(n2) ? YES
10 120n2 +
√
n + 99n = Θ(n2) ? YES
11 sin(n) = O(1) ? YES
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Can we improve the Min-Max algorithm?
Determine T (6), the number of comparisons the Min-Max
algorithms performs for 6 elements.
As usual, the argumentation is important (why is this
correct?).
Perhaps best is that you run the algorithm (on paper) for 6
elements.
Notice that the basic parameters for a run do not depend on
the values of the elements, but only on their total number.
Once you found T (6), is this really optimal?
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Unfolding the recursion for Min-Max
We have
T (n) =
0 if n = 1
1 if n = 2
T (
⌈
n
2
⌉
) + T (
⌊
n
2
⌋
) + 2 else
.
1 T (1) = 0
2 T (2) = 1
3 T (3) = T (2) + T (1) + 2 = 1 + 0 + 2 = 3
4 T (4) = T (2) + T (2) + 2 = 1 + 1 + 2 = 4
5 T (5) = T (3) + T (2) + 2 = 3 + 1 + 2 = 6
6 T (6) = T (3) + T (3) + 2 = 3 + 3 + 2 = 8
7 T (7) = T (4) + T (3) + 2 = 4 + 3 + 2 = 9
8 T (8) = T (4) + T (4) + 2 = 4 + 4 + 2 = 10
9 T (9) = T (5) + T (4) + 2 = 6 + 4 + 2 = 12
10 T (10) = T (5) + T (5) + 2 = 6 + 6 + 2 = 14.
We count 4 steps +1 and 5 steps +2 — we guess T (n) ≈ 3
2
n.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Finding the best min-max algorithm
1 As you can see in the section on the min-max problem, for
some input sizes we can validate the guess T (n) ≈ 3
2
n.
2 One can now try to find a precise general formula for T (n),
3 However we see that we have T (6) = 8, while we can
handle this case with 7 comparisons. So perhaps we can
find a better algorithm?
4 And that is the case:
1 If n is even, find the min-max for the first two elements
using 1 comparison; if n is odd, find the min-max for the
first element using 0 comparisons.
2 Now iteratively find the min-max of the next two elements
using 1 comparison, and compute the new current min-max
using 2 further comparisons. And so on ….
This yields an algorithm using precisely
⌈
3
2
n
⌉
− 2
comparisons. And this is precisely optimal for all n.
We learn: Here divide-and-conqueor provided a good stepping
stone to find a really good algorithm.
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
Designing an algorithm: Median
The median of a sequence of numbers is the “middle value” —
the value in the middle position of the list after sorting.
Can we do better than the obvious algorithm (by sorting),
using divide-and-conquer?
(Here some judgement is needed, that the precise details about
what actually is the “middle value” won’t make a fundamental
difference, and so it’s best to ignore them for the initial phase,
where developing the ideas is of utmost importance.)
CS 270
Algorithms
Oliver
Kullmann
Growth of
Functions
Divide-and-
Conquer
Min-Max-
Problem
Tutorial
First strategy: divide in half
1 Divide the array A of numbers into two parts, B and C , of
equal size (more precisely, nearly equal size, but such details
are best ignored in the beginning).
2 In principle B and C could be anything, but easiest is to let
them be the first half and the second half of A.
3 Compute (that is now the conquer-phase) the medians
mB ,mC of the arrays B ,C .
4 If mC < mB , then swap B and C . 5 Re-order B and C internally, so that the elements smaller than the median are on the left, and the larger elements on the right. 6 Now consider the array of elements from mB to mC (note that this is again half of the size of A): The median of this array (computed again in the conquer-phase, recursively) is the median of A. CS 270 Algorithms Oliver Kullmann Growth of Functions Divide-and- Conquer Min-Max- Problem Tutorial Example run 1, 20, 5, 18, 7, 10, 10 | 4, 20, 7, 7, 17, 14, 1, 12 of length 15, partitioned into 7 and 8 elements. The left median is 10. The right median is 7 or 12; let’s take 7. Swap, and partition the two parts according to their medians: 4, 7, 1, 7, 20, 17, 14, 12 | 1, 5, 7, 10, 20, 18, 10. Compute the median of the new middle part 20, 17, 14, 12, 1, 5, 7, 10 which is 10 (the right answer) or 12. So, it could work (or not). CS 270 Algorithms Oliver Kullmann Growth of Functions Divide-and- Conquer Min-Max- Problem Tutorial The recurrence We are in this phase only interested in the recurrence: T (n) = 3 · T (n/2) + O(n). We ignore here all issues about the precise partitioning (and whether we can get it to work at all!) — all what counts here is the insight whether we could get a good algorithm! Next week we develop tools to see immediately how good this approach could be. Divide and Conquer Growth of Functions Divide-and-Conquer Min-Max-Problem Tutorial 270-1/03-solving-recurrences_handout CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Week 3 Solving Recurrences 1 Divide-and-Conquer Merge Sort 2 Solving Recurrences Recursion Trees Master Theorem 3 Divide-and-Conquer Matrix multiplication 4 Tutorial CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial General remarks First we continue with an important example for Divide-and-Conquer, namely Merge Sort. Then we present a basic tool for analysing algorithms by Solving Recurrences. We conclude by considering another example, namely Matrix Multiplication. Reading from CLRS for week 3 Chapter 4 CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Another example: Merge-Sort A sorting algorithm based on divide and conquer. The worst-case running time has a lower order of growth than insertion sort. Again we are dealing with subproblems of sorting subarrays A[p . . q] Initially, p = 1 and q = A. length, but these values change again as we recurse through subproblems. To sort A[p . . q]: Divide by splitting into two subarrays A[p . . . r ] and A[r+1 . . . q], where r is the halfway point of A[p . . . q]. Conquer by recursively sorting the two subarrays A[p . . . r ] and A[r+1 . . . q]. Combine by merging the two sorted subarrays A[p . . . r ] and A[r+1 . . . q] to produce a single sorted subarray A[p . . . q]. The recursion bottoms out when the subarray has just 1 element, so that it is trivially sorted. CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Another example: Merge-Sort Merge-Sort(A, p, q) 1 if p < q // check for base case 2 r = ⌊(p+q)/2⌋ // divide 3 Merge-Sort(A, p, r) // conquer 4 Merge-Sort(A, r+1, q) // conquer 5 Merge(A, p, r , q) // combine Initial call: Merge-Sort(A, 1,A. length) CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Merge Input: Array A and indices p, r , q such that p ≤ r < q Subarrays A[p . . r ] and subarray A[r+1 . . q] are sorted. By the restriction on p, r , q neither subarray is empty. Output: The two subarrays are merged into a single sorted subarray in A[p . . q]. We implement is so that it takes Θ(n) time, with n = q − p + 1 = the number of elements being merged. CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Merge(A, p, r , q) 1 n1 = r − p + 1 2 n2 = q − r 3 let L[1 . . n1+1] and R[1 . . n2+1] be new arrays 4 for i = 1 to n1 5 L[i ] = A[p+i−1] 6 for j = 1 to n2 7 R[j ] = A[r+j ] 8 L[n1+1] = R[n2+1] = ∞ 9 i = j = 1 10 for k = p to q 11 if L[i ] ≤ R[j ] 12 A[k] = L[i ] 13 i = i+1 14 else A[k] = R[j ] 15 j = j+1 CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Analysis of Merge-Sort The runtime T (n), where n = q−p+1 > 1, satisfies:
T (n) = 2T (n/2) + Θ(n).
We will show that T (n) = Θ(n lg n).
It can be shown (see tutorial-section) that Ω(n lg n)
comparisons are necessary in the worst case to sort n
numbers for any comparison-based algorithm: this is thus
an (asymptotic) lower bound on the problem.
Hence Merge-Sort is provably (asymptotically) optimal.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Analysing divide-and-conquer algorithms
Recall the divide-and-conquer paradigm:
Divide the problem into a number of subproblems that are
smaller instances of the same problem.
Conquer the subproblems by solving them recursively.
Base case: If the subproblem are small enough, just solve
them by brute force.
Combine the subproblem solutions to give a solution to the
original problem.
We use recurrences to characterise the running time of a
divide-and-conquer algorithm. Solving the recurrence gives us
the asymptotic running time.
A recurrence is a function defined in terms of
one or more base cases, and
itself, with smaller arguments
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Examples for recurrences
T (n) =
{
1 if n = 1
T (n − 1) + 1 if n > 1
Solution: T (n) = n.
T (n) =
{
1 if n = 1
2T (n/2) + n if n > 1
Solution: T (n) ≈ n lg n + n.
T (n) =
{
0 if n = 2
T (
√
n) + 1 if n > 2
Solution: T (n) ≈ lg lg n.
T (n) =
{
1 if n = 1
T (n/3) + T (2n/3) + n if n > 1
Solution: T (n) = Θ(n lg n).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Main technical issues with recurrences
Floors and ceilings: The recurrence describing worst-case
running time of Merge-Sort is really
T (n) =
{
Θ(1) if n = 1
T (⌈n/2⌉) + T (⌊n/2⌋) + Θ(n) if n > 1
Exact vs. asymptotic functions Sometimes we are interested in
the exact analysis of an algorithm (as for the
Min-Max-Problem), at other times we are concerned with the
asymptotic analysis (as for the Sorting Problem).
Boundary conditions Running time on small inputs is bounded
by a constant: T (n) = Θ(1) for small n. We usually do not
mention this constant, as it typically doesn’t change the order
of growth of T (n). Such constants only play a role if we are
interested in exact solutions.
When we state and solve recurrences, we often omit floors,
ceilings, and boundary conditions, as they usually do not matter.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Recursion trees (quadratic growth)
Draw the unfolding of the recurrence
T (n) = n + 4T (n/2).
T (n)
T ( n
2
) T ( n
2
) T ( n
2
) T ( n
2
)
n
· · · · · · · · ·
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
4
n
2
n
2
n
2
n
2
n
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
lg n
✻
❄
20n
21n
22n
2lg nn
Total: Θ(2lg nn)
= Θ(n2)
…
✲
✲
✲
✲
We exploited that 1 + 2 + 4 + · · ·+ 2k = 2k+1 − 1 = Θ(2k).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Recursion trees (quasi-linear and linear growth)
What about the “merge-sort” recurrence
T (n) = n + 2T (n/2) ?
Again the height of the tree is lg n.
However now the “workload” of each level is equal to n.
So here we get
T (n) = Θ(n · lg n).
And what about the recurrence
T (n) = 1 + 2T (n/2) ?
Again the height of the tree is lg n.
The “workload” of the level is 1, 2, . . . , 2lg n.
So here we get
T (n) = Θ(n).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Master Theorem (simplified version)
Let a ≥ 1 and b > 1 and c ≥ 0 be constants.
Let T (n) be defined by the recurrence
T (n) = aT (n/b) + Θ(nc),
where n/b represents either ⌊n/b⌋ or ⌈n/b⌉.
Then T (n) is bounded asymptotically as follows:
1 If c < logb a then T (n) = Θ(nlogb a). 2 If c = logb a then T (n) = Θ(nc lg n). 3 If c > logb a then T (n) = Θ(nc).
(General version: CLRS, Thm 4.1, p94.)
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
In other words
We need to give an equation for T (n) of the form
T (n) = bx · T (
n
b
) + Θ(nc),
where the x you have to find: x = logb a.
Then T (n) is bounded asymptotically as follows:
1 If x > c then T (n) = Θ(nx).
2 If x = c then T (n) = Θ(nc lg n).
3 If x < c then T (n) = Θ(nc). The meaning of the three parameters in a divide-and-conquer scheme: a = bx : the number of subproblems to be solved b: how often the subproblems (all of the same size) fit into the full problem c : power in the runtime of combination-computation. CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Using the Master Theorem The runtime for Min-Max satisfies the recurrence: T (n) = 2T (n/2) + Θ(1). The Master Theorem (case 1) applies: a = b = 2 and c = 0 < 1 = logb a, giving T (n) = Θ(nlogb a) = Θ(n). The runtime for Merge-Sort satisfies the recurrence: T (n) = 2T (n/2) + Θ(n). The Master Theorem (case 2) applies: a = b = 2 and c = 1 = logb a, giving T (n) = Θ(nc lg n) = Θ(n lg n). CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial What’s happening For the recurrences T1(n) = 4T (n/2) + n T2(n) = 4T (n/2) + n2 T3(n) = 4T (n/2) + n3 the Master Theorem (case i) applies: a = 4 and b = 2 (so logb a = 2 ), and c = i , giving T1(n) = Θ(n2) , T2(n) = Θ(n2 lg n) , and T3(n) = Θ(n3) . Case 1: applies if the combination-cost (nc) is negligible compared to the number and size of the subproblems. Case 2: applies if the combination-cost (nc) is as costly as the subproblems. Case 3: applies if the combination-cost (nc) is the dominating factor. If we have Case 3, then in general this indicates, that the divide-and-conquer approach can be replaced by a simpler approach (as we have seen for the min-max algorithm). CS 270 Algorithms Oliver Kullmann Divide-and- Conquer Merge Sort Solving Recurrences Recursion Trees Master Theorem Divide-and- Conquer Matrix multiplication Tutorial Easy decision between the three cases Consider (again) T (n) = a · T ( n b ) + Θ(nc). The main question to start with is always: Which of the three cases applies? Apparently you needed to compute x = logb a for that. But it is actually easier: 1 If bc < a then Case 1 applies. 2 If bc = a then Case 2 applies. 3 If bc > a then Case 3 applies.
(Try to understand why this holds — it’s easy.)
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Further examples
T (n) = 5T (n/2) + Θ(n2)
In Master Theorem: a = 5, b = 2, c = 2.
As logb a = log2 5 > log2 4 = 2 = c , case 1 applies:
T (n) = Θ(nlg 5).
T (n) = 27T (n/3) + Θ(n3)
In Master Theorem: a = 27, b = 3, c = 3.
As logb a = log3 27 = 3 = c , case 2 applies:
T (n) = Θ(n3 lg n).
T (n) = 5T (n/2) + Θ(n3)
In Master Theorem: a = 5, b = 2, c = 3.
As logb a = log2 5 < log2 8 = 3 = c , case 3 applies:
T (n) = Θ(n3).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
A quick glance at matrix multiplication
Hopefully you recall from your first-year:
Multiplication of two n × n matrices is done by a
three-times nested loop,
and thus can be done in time O(n3)
(counting multiplications and additions).
For example
(
a b
c d
)
·
(
w x
y z
)
=
(
aw + by ax + bz
cw + dy cx + dz
)
.
Matrix multiplication is “everywhere” —
can we do better than O(n3) ?
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
First approach
The previous formula for multiplication of 2× 2 matrices can be
used for arbitrary matrix multiplication for n × n matrices:
Subdivide each of the two matrices into 4 submatrices of
size n
2
× n
2
.
Apply the formula, plugging in the sub-matrices.
We have 8 multiplications with the smaller matrices, yielding
T (n) = 8T (
n
2
) + n2
(n2 is for the additions). This yields
T (n) = Θ(n3).
We needed to do better ?!
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
A trick with astounding effects
The trick is now to do the multiplication of two 2× 2 matrices
with only 7 multiplications:
1 We need more additions, but this is irrelevant here.
2 The savings comes from using intermediate results
(factoring out ...).
3 See the tutorial for how this is done.
We then get the recurrence
T (n) = 7T (
n
2
) + Θ(n2).
We have lg 7 ≈ 2.807355, and thus
T (n) = Θ(n2.807356).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Couting only multiplications
If T (n) only considers the multiplications, then we can actually
give precise recurrences for even n, namely T (n) = 8T (n
2
) resp.
T (n) = 7T (n
2
), where for both algorithms (simple and
improved) we have the base case T (1) = 1 (here we just have to
multiply two numbers).
We have more additions than multiplications for both algorithms,
but in both cases they have the same asymptotic growth.
The improved algorithm trades additions (and substractions!)
for multiplications (more additions/subtractions, less
multiplications), but due to the improved recursion it uses also
less additions than the simple (divide-and-conquer) algorithm.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
How to do it with 7 multiplications
(
a1,1 a1,2
a2,1 a2,2
)
·
(
b1,1 b1,2
b2,1 b2,2
)
=
(
a1,1b1,1 + a1,2b2,1 a1,1b1,2 + a1,2b2,2
a2,1b1,1 + a2,2b2,1 a2,1b1,2 + a2,2b2,2
)
Create 10 auxiliary results:
S1 = b1,2 − b2,2 S6 = b1,1 + b2,2
S2 = a1,1 + a1,2 S7 = a1,2 − a2,2
S3 = a2,1 + a2,2 S8 = b2,1 + b2,2
S4 = b2,1 − b1,1 S9 = a1,1 − a2,1
S5 = a1,1 + a2,2 S10 = b1,1 + b2,1
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
How to do it with 7 multiplications (cont.)
Perform 7 multiplications:
P1 = a1,1 · S1 = a1,1 · b1,2 − a1,1 · b2,2
P2 = S2 · b2,2 = a1,1 · b2,2 + a1,2 · b2,2
P3 = S3 · b1,1 = a2,1 · b1,1 + a2,2 · b1,1
P4 = a2,2 · S4 = a2,2 · b2,1 − a2,2 · b1,1
P5 = S5 · S6 = a1,1 · b1,1 + a1,1 · b2,2 + a2,2 · b1,1 + a2,2 · b2,2
P6 = S7 · S8 = a1,2 · b2,1 + a1,2 · b2,2 − a2,2 · b2,1 − a2,2 · b2,2
P7 = S9 · S10 = a1,1 · b1,1 + a1,1 · b1,2 − a2,1 · b1,1 − a2,1 · b1,2
Harvest:
a1,1b1,1 + a1,2b2,1 = P5 + P4 − P2 + P6
a1,1b1,2 + a1,2b2,2 = P1 + P2
a2,1b1,1 + a2,2b2,1 = P3 + P4
a2,1b1,2 + a2,2b2,2 = P5 + P1 − P3 − P7.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
More recurrences
1 T (n) = 3T (n/3) + 1 : T (n) = Θ(n)
2 T (n) = aT (n/a) + 1 : T (n) = Θ(n)
3 T (n) = 2T (n/3) + 1 : T (n) = Θ(nlog3 2)
4 T (n) = 4T (n/3) + 1 : T (n) = Θ(nlog3 4)
5 T (n) = 3T (n/3) + n : T (n) = Θ(n log n)
6 T (n) = aT (n/a) + n : T (n) = Θ(n log n)
7 T (n) = 2T (n/3) + nlog3 2 : T (n) = Θ(nlog3 2 log n)
8 T (n) = 4T (n/3) + nlog3 4 : T (n) = Θ(nlog3 4 log n)
9 T (n) = 3T (n/3) + n1.5 : T (n) = Θ(n1.5)
10 T (n) = aT (n/a) + n1.5 : T (n) = Θ(n1.5)
11 T (n) = 2T (n/3) + n : T (n) = Θ(n)
12 T (n) = 4T (n/3) + n2 : T (n) = Θ(n2)
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Continuing the median-computation
Recall our (first) divide-and-conquer approach for a better
median-computation from last week:
Now we know that using Merge-Sort we can compute the
median in time O(n · lg n).
For the possible(!) alternative approach we got the
recurrence T (n) = 3T (n/2) + O(n).
Since 21 < 3, the first case of the Master Theorem applies.
We get T (n) = Θ(nlg 3), where lg 3 < 1.59.
So the alternative approach would be faster than using
Insertion-Sort, but it is slower than using Merge-Sort.
We are looking for a median-computation in linear time.
When we come to Quick-Sort, then we discuss an alternative
(better) idea for divide-and-conquer.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Remarks on Merge-Sort
Stability For many sorting-applications, the objects to be
sorted consist of a key which provides the sorting
criterion, and a lot of other data; for example the
last name as part of an employee-record. Then it
is quite natural that different objects have the
same key. Often, such arrays are then pre-sorted
according to other criterions.
“Stability” of a sorting algorithm is now the
property that the order of equal elements
(according to their keys) is not changed.
Merge-Sort is stable (at least in our
implementation; also Insertion-Sort is stable).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Remarks on Merge-Sort (cont.)
In-place A sorting algorithms sorts “in-place” if besides the
given array and some auxiliary data is doesn’t need
more memory. This is important if the array is very
large (say, n ≈ 109).
Insertion-Sort is in-place, while our algorithm for
Merge-Sort is not (needing ≈ 2n memory cells).
One can make Merge-Sort in-place, but this
(apparently) only with a complicated algorithm,
which in practice seems not to be applied. If
in-place sorting is required, then often one uses
“Heap-Sort”.
Already sorted If the array is already sorted, then only n − 1
comparisons are needed (however overall it still
needs time Θ(n log n) because of the swapping,
and it stills needs space 2n).
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
Remarks on Merge-Sort (cont.)
Combination-cost The general combination-cost of Merge-Sort
(due to the swapping) is somewhat higher than
what can be achieved with “Quick-Sort”, which
typically is the default sorting-algorithm in libraries.
CS 270
Algorithms
Oliver
Kullmann
Divide-and-
Conquer
Merge Sort
Solving
Recurrences
Recursion
Trees
Master
Theorem
Divide-and-
Conquer
Matrix
multiplication
Tutorial
The minimal numbers of comparisons
Let S(n) be the minimum number of comparisons that will
(always!) suffice to sort n elements (using only comparisons
between the elements, and no other properties of them). It holds
S(N) ≥ ⌈lg(n!)⌉ = Θ(n log n).
This is the so-called information-theoretic lower bound: It
follows by observing that the n! many ordering of 1, . . . , n need
to be handled, where every comparison establishes 1 bit of
information.
The initial known precise values for S(n) are:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
S(n) 0 1 3 5 7 10 13 16 19 22 26 30 34 38
The first open value is S(15) (see http://oeis.org/A036604).
http://oeis.org/A036604
Solving Recurrences
Divide-and-Conquer
Merge Sort
Solving Recurrences
Recursion Trees
Master Theorem
Divide-and-Conquer
Matrix multiplication
Tutorial
270-1/04-graph-algorithms_handout
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Week 4
Elementary Graph Algorithms
1 Graphs and directed graphs
2 Representing graphs
3 Trees
4 Breadth-first search
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
General remarks
We consider graphs, an important data structure.
We consider the simplest graph-search algorithm,
breadth-first search (BFS).
We consider one application of BFS, the computation of
shortest paths.
Reading from CLRS for week 4
Chapter 22, Sections 22.1, 22.2.
Plus appendices
B.4 “Graphs”
B.5.1 “Free trees”
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Towards the mathematical notion of “graph”
Definition A graph G is a pair G = (V ,E ), where V is the set
of vertices, while E is the set of (undirected) edges. An
(undirected) edge connecting vertices u, v is denoted by { u, v }.
We require u 6= v here.
An example is
G = ({ 1, 2, 3, 4, 5 }, { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 3, 4 } })
which is a graph with |V | = 5 vertices and |E | = 4 edges. A
possible drawing is as follows:
1 2
3 4 5
We see that G has two “connected components”.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Directed graphs
A “graph” is synonymous with “undirected graph”. Now for a
“directed graph” the edges are directed:
Definition A directed graph (or digraph) G is a pair
G = (V ,E ), where V is again the set of vertices, while E is the
set of directed edges or arcs. A directed edge from vertex u
to vertex v is denoted by (u, v). Again we require u 6= v here.
An example is
G = ({ 1, 2, 3, 4, 5 }, { (1, 2), (3, 1), (2, 4), (4, 3) })
which is a graph with |V | = 5 vertices and |E | = 4 edges. A
possible drawing is as follows:
1 // 2
��
3
OO
4oo 5
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Remarks on these fundamental notions
A loop is an edge or arc connecting a vertex with itself:
1 The notion of graph doesn’t allow loops; only the extension
of “graphs with loops” allows them, but we do not consider
them here.
2 Also the notion of directed graph doesn’t allow loops
(different from the book we keep the symmetry between
“graphs” and “directed graphs”); the extension of “directed
graphs with loops” allows them, but again we do not
consider them.
For a graph G with n = |V | vertices we have
|E | ≤
(
n
2
)
=
n(n − 1)
2
while for a directed graph G we have
|E | ≤ n(n − 1).
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Representations of graphs
The above notions of graphs and digraphs yield mathematical
objects. These are the eternal platonic ideas, which have many
different representations in computers.
There are two main ways to represent a graph G = (V ,E ):
Adjacency lists: The graph is represented by a V -indexed array
of linked lists, with each list containing the neighbours of a
single vertex.
Adjacency matrix: The graph is represented by a |V | × |V | bit
matrix where the Ai ,j = 1 if and only if vertex i is adjacent
to vertex j .
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Adjacency list representation
1 2 4 6
3 5 7
1 2
2 1 3 4
3 2 4 5
4 2 3 5 6 7
5 3 4 7
6 4
7 4 5
For (undirected) graphs this representation uses two list elements
for each edge (since both directions are present); for directed
graphs this is only the case when antiparallel edges are present.
The total space required for this representation is O(V + E )
(that is, O(|V |+ |E |)).
This representation is suited to sparse graphs, where E is much
less than V 2.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Adjacency matrix representation
1 2 4 6
3 5 7
A =
0 1 0 0 0 0 0
1 0 1 1 0 0 0
0 1 0 1 1 0 0
0 1 1 0 1 1 1
0 0 1 1 0 0 1
0 0 0 1 0 0 0
0 0 0 1 1 0 0
For (undirected) graphs the matrix is symmetric.
The total space required for this representation is O(V 2).
This representation is suited to dense graphs, where E is on the
order of V 2.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Comparing the two representations
Apart from the different space requirements needed for sparse
and dense graphs, there are other criteria for deciding on which
representation to use.
The choice of representation will depend mostly on what
questions are being asked.
For example, consider the time required to decide the following
questions using the two different representations:
Is vertex v adjacent to vertex w in an undirected graph?
What is the out-degree of a vertex v in a directed graph?
What is the in-degree of a vertex v in a directed graph?
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
The notion of a tree
You might have seen already “rooted trees” (and you will see
more of them in the following weeks) — trees are basically just
like rooted trees, but without a designated root.
Definition A tree is a graph T with at least one vertex, which is
connected and does not have a cycle.
Intuitively, a graph G has a cycle if there are two different
vertices u, v in G such that there are (at least) two essentially
different ways of getting from u to v . And thus going from u to
v the one way, and from v to u the other way, we obtain the
“round-trip” or “cycle”.
We have the following fundamental characterisation of trees:
Lemma 1 A graph G is a tree if and only if G is connected,
|V | ≥ 1 and |E | = |V | − 1 holds.
So trees realise minimal ways of connecting a set of vertices.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Examples
Here are two trees:
1 2
4
��������
3
1 2 3 4
♣♣
♣♣
♣♣
♣♣
♣♣
♣♣
♣♣
8
��������
7 6
◆◆◆◆◆◆◆◆◆◆◆◆◆◆
5
◆◆◆◆◆◆◆◆◆◆◆◆◆◆
And here is the smallest connected graph with at least one
vertex, which is not a tree (the “triangle”):
1
❃❃
❃❃
❃❃
❃❃
2
3
And here the smallest graph with at least one vertex (namely
with two vertices), which is not a tree:
1 2
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Spanning trees
Definition Consider a connected graph G with at least one
vertex. A spanning tree of G is a tree T with V (T ) = V (G )
and E (T ) ⊆ E (G ).
So spanning trees just leave out edges which are not needed to
connect the whole graph. For example consider the graphs
G1 = 1 2
3 4
, G2 = 1
❃❃
❃❃
❃❃
❃❃
2
3 4
.
G1 has 4 different spanning trees, while G2 has 4 + 4 = 8.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Computing spanning trees
We will see two algorithms, BFS and DFS, for computing
spanning trees:
In both cases actually rooted spanning trees are
computed, that is, additionally a vertex is marked as “root”.
When drawing such rooted spanning trees, one starts with
the root (otherwise one could start with an arbitrary
vertex!), going from the root to the leaves.
For such rooted spanning trees, one typically speaks of
nodes instead of vertices.
Both algorithms compute additional data, besides the
rooted spanning trees.
The DFS version will be extended to compute a spanning
forest: It can be applied to non-connected graphs, and
computes a (rooted) spanning tree for each connected
component.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Representing rooted trees
A rooted tree, that is, a tree together with a root T , will be
represented by BFS and DFS as follows:
Now there is a “direction” in the tree, either going from the
root towards the leaves, or from the leaves towards the root.
We obtain the usual notion of the children of a node
(without a root, in a “pure tree”, there is no such thing).
The leaves are the nodes without children.
And we speak of the(!) parent of a node (note that every
node can have at most one parent).
The root is the only vertex without a parent.
Now specifying the root for each non-root vertex is
sufficient to represent the tree.
This is done in BFS and DFS by an array π (like “parent”).
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Forests
A forest is a graph where every connected component is a tree:
A connected component of a graph contains some vertex
and precisely all vertices reachable from it.
So a graph is connected if and only it has at most one
connected component.
Note that the empty graph (with the empty vertex-set) is
connected and has zero connected components.
And also note that every tree is a forest (but not the other
way around).
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Forests (cont.)
Considering the so-called “disjoint union” of the two trees we
have seen previously, we get a (proper) forest (now taking this
as one graph — note the necessity of the renaming):
1 2 5 6 7 8
♥♥
♥♥
♥♥
♥♥
♥♥
♥♥
♥♥
♥
4
��������
3 12
⑤⑤⑤⑤⑤⑤⑤⑤
11 10
PPPPPPPPPPPPPPP
9
PPPPPPPPPPPPPPP
Lemma 1 A graph G is a forest if and only if G contains no
cycle.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Spanning forests
A graph G has a spanning tree if and only if G is not empty and
G is connected.
On the other hand, every graph has a spanning forest.
These are precisly given by the spanning trees of the
connected components (taken together).
If we have a disconnected graph, then we can just break it up
into its components, and treat them separately.
In this sense the case of
connected graphs and spanning trees
is the central case.
However for real software systems, we cannot just assume the
graphs to be connected, and there we handle forests.
This is just done by restarting BFS (or later DFS)
on the vertices not covered yet.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
Breadth-first search
Searching through a graph is one of the most fundamental of all
algorithmic tasks.
Breadth-first search (BFS) is a simple but very important
technique for searching a connected graph.
Such a search starts from a given source vertex s and constructs
a rooted spanning tree for the graph, called the breadth-first
tree (the root is s).
It uses a (first-in first-out) queue as its main data structure.
BFS computes the parent π[u] of each vertex u in the
breadth-first tree (with the parent of the source being nil), as
well as its distance d [u] from the source s (initialised to ∞),
which is the length of the path from s to u in the breadth-first
tree, which is a shortest path between these vertices.
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
The algorithm
Input: A graph G with vertex set V (G ) and edges represented
by adjacency lists Adj.
BFS(G , s)
1 for each u ∈ V (G )
2 d [u] = ∞
3 π[s] = nil
4 d [s] = 0
5 Q = (s)
6 while Q 6= ()
7 u = Dequeue[Q]
8 for each v ∈ Adj[u]
9 if d [v ] = ∞
10 d [v ] = d [u] + 1
11 π[v ] = u
12 Enqueue(Q, v)
CS 270
Algorithms
Oliver
Kullmann
Graphs and
directed
graphs
Representing
graphs
Trees
Breadth-first
search
BFS illustrated
Q = (1)
1 2 4 6
3 5 7
0/nil ∞/− ∞/− ∞/−
∞/− ∞/− ∞/−
u
d [u]/π[u]
(labelling)
Q = (2)
1 2 4 6
3 5 7
0/nil 1/1 ∞/− ∞/−
∞/− ∞/− ∞/−
Q = (3, 4)
1 2 4 6
3 5 7
0/nil 1/1 2/2 ∞/−
2/2 ∞/− ∞/−
Q = (4, 5)
1 2 4 6
3 5 7
0/nil 1/1 2/2 ∞/−
2/2 3/3 ∞/−
Q = (5, 6, 7)
1 2 4 6
3 5 7
0/nil 1/1 2/2 3/4
2/2 3/3 3/4
Q = (6, 7)
1 2 4 6
3 5 7
0/nil 1/1 2/2 3/4
2/2 3/3 3/4
Q = (7)
1 2 4 6
3 5 7
0/nil 1/1 2/2 3/4
2/2 3/3 3/4
Q = ()
1 2 4 6
3 5 7
0/nil 1/1 2/2 3/4
2/2 3/3 3/4
Elementary Graph Algorithms
Graphs and directed graphs
Representing graphs
Trees
Breadth-first search
270-1/05-dfs_handout
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Week 5
Depth-first search
1 Analysing BFS
2 Depth-first search
3 Analysing DFS
4 Dags and topological sorting
5 Detecting cycles
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
General remarks
We finish BFS, by analysing it.
Then we consider the second main graph-search algorithm,
depth-first search (DFS).
And we consider one application of DFS, topological
sorting of graphs.
Reading from CLRS for week 5
Chapter 22, Sections 22.2, 22.3, 22.4.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Recall: BFS
BFS(G , s)
1 for each u ∈ V (G )
2 d [u] = ∞
3 π[s] = nil
4 d [s] = 0
5 Q = (s)
6 while Q 6= ()
7 u = Dequeue[Q]
8 for each v ∈ Adj[u]
9 if d [v ] = ∞
10 d [v ] = d [u] + 1
11 π[v ] = u
12 Enqueue(Q, v)
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Analysis of BFS
Correctness Analysis: At termination of BFS(G , s), for every
vertex v reachable from s:
v has been encountered;
d [v ] holds the length of the shortest path from s to v ;
π[v ] represents an edge on a shortest path from v to s.
Time Analysis:
The initialisation takes time Θ(V ).
Each vertex is Enqueued once and Dequeued once;
these queueing operations each take constant time, so
the queue manipulation takes time Θ(V ) (altogether).
The Adjacency list of each vertex is scanned only when
the vertex is Dequeued, so scanning adjacency lists
takes time Θ(E ) (altogether).
The overall time of BFS is thus Θ(V + E ).
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Why do we get shortest paths?
Is it really true that we get always shortest paths (that is, using
the minimum number of edges)? Let’s assume that to some
vertex v there exists a shorter path P in G from s to v than
found by BFS. Let this length be d ′ < d [v ].
1 v 6= s, since the distance from s to s is zero (using the path
without an edge), and this is correctly computed by BFS.
2 Consider the predecessor u on that shorter path P .
3 If also d [u] would be wrong (that is, too big), than we
could use u instead of v . Thus w.l.o.g. d [u] is correct.
4 Now when exploring the neighbours of u, in case v is still
unexplored, it would get the correct distance d ′ = d [u] + 1.
5 So v must have been explored already earlier (than u).
6 So at the time of determining the distance d [u] ≤ d [v ]− 2,
the distance d [v ] must have been already set.
7 However the distances d [w ] set by BFS are non-decreasing!
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
The role of the queue
A crucial property of BFS is that the distances set in step 10 of
the algorithm are non-decreasing, that is,
if we imagine a watch-point set at step 10,
and monitor the stream of values d [v ], then we will see
0, 1, . . . , 1, 2, . . . , 2, 3, . . . , 3, . . . .
Why is this the case? This must be due to the queue used —
whose special properties we haven’t yet exploited!
Since in step 12, directly after setting the distance, we put the
vertex into the queue, the above assertion is equivalent to the
statement, that the distances of the vertices put into the queue
are non-decreasing (in the order they enter the queue).
Now why is this the case?
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
The role of the queue (cont.)
First we need to notice that once a distance d [v ] is set, it is
never changed again.
The vertices are taken off the queue (“dequeued”) from the
left, and are added (“enqueued”) to the right (“first in, first
out”).
What is added has a distance one more than what was
taken away.
We start with 0, and add some 1’s.
Then we take those 1’s, and add 2’s.
Once the 1’s are finished, we take the 2’s, and add 3’s.
And so on — that why the sequence of distances is
non-decreasing.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Running BFS on directed graphs
We can run BFS also on a digraph G , with start-vertex s:
1 For digraphs we have directed spanning trees/forests.
2 Only the vertices reachable from s following the directions
of the edges are in that directed tree (directed from s
towards the leaves).
3 Still the paths in the directed tree, from s to any other
vertex, are shortest possible (given that we obey the given
directions of the edges).
For a graph (i.e., undirected graph), we need to restart BFS (to
obtain a spanning forest, not just a spanning tree) only if the
graph is disconnected.
However for a digraph there is a much higher chance, that we
need to restart in order to cover all vertices.
We thus more often need a directed spanning forest, not just a
directed spanning tree.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Restart typically needed for digraphs to cover all
vertices
Consider the simple digraph
1 2oo
3
OO
In order to cover all vertices, one needs to run BFS at least two
times (and if the first time you start it with s = 1, then you
need to run it three times).
So even for the above apparently very simple graph we need
a directed spanning forest.
Note that the obtained directed trees (given by π) overlap.
So in such a directed forest there is typically a certain
overlap between the directed trees in it.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Arcs of different lengths
The edges of (di-)graphs have (implicitly) a length of one unit.
If arbitrary non-negative lengths are allowed, then we have
to generalise BFS to Dijkstra’s algorithm.
This generalisation must keep the essential properties, that
the distances encountered are the final ones and are
non-decreasing.
But now not all edges have unit-length, and thus instead of
a simple queue we need to employ a priority queue.
A priority queue returns the vertex in it with the smallest
value (distance).
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Depth-first search
Depth-first search (DFS) is another simple but very important
technique for searching a graph.
Such a search constructs a spanning forest for the graph, called
the depth-first forest, composed of several depth-first trees,
which are rooted spanning trees of the connected components.
DFS recursively visits the next unvisited vertex, thus extending
the current path as far as possible; when the search gets stuck in
a “corner” it backtracks up along the path until a new avenue
presents itself.
DFS computes the parent π[u] of each vertex u in the
depth-first tree (with the parent of initial vertices being nil), as
well as its discovery time d [u] (when the vertex is first
encountered, initialised to ∞) and its finishing time f [u] (when
the search has finished visiting its adjacent vertices).
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
The algorithm
DFS(G )
1 for each u ∈ V (G )
2 d [u] = ∞
3 time = 0
4 for each u ∈ V (G )
5 if d [u] = ∞
6 π[u] = nil
7 DFS-Visit(u)
DFS-Visit(u)
1 time = time + 1
2 d [u] = time
3 for each v ∈ Adj[u]
4 if d [v ] = ∞
5 π[v ] = u
6 DFS-Visit(v)
7 time = time + 1
8 f [u] = time
Analysis: DFS-Visit(u) is invoked exactly once for each
vertex, during which we scan its adjacency list once. Hence
DFS, like BFS, runs in time Θ(V + E ).
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
DFS illustrated
Stack = () u = 1
1 2 4 6
3 5 7
1
−
/nil ∞
−
/− ∞
−
/− ∞
−
/−
∞
−
/− ∞
−
/− ∞
−
/−
u
d [u]
f [u]
/π[u]
(labelling)
Stack = (1) u = 2
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 ∞
−
/− ∞
−
/−
∞
−
/− ∞
−
/− ∞
−
/−
Stack = (2, 1) u = 3
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 ∞
−
/− ∞
−
/−
3
−
/2
∞
−
/− ∞
−
/−
Stack = (3, 2, 1) u = 4
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 4
−
/3 ∞
−
/−
3
−
/2
∞
−
/− ∞
−
/−
Stack = (4, 3, 2, 1) u = 5
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 4
−
/3 ∞
−
/−
3
−
/2 5
−
/4
∞
−
/−
Stack=(5, 4, 3, 2, 1) u = 7
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 4
−
/3 ∞
−
/−
3
−
/2 5
−
/4 6
−
/5
Stack = (4, 3, 2, 1) u = 6
1 2 4 6
3 5 7
1
−
/nil 2
−
/1 4
−
/3 9
−
/4
3
−
/2 5
8
/4 6
7
/5
Stack = ()
1 2 4 6
3 5 7
1
14
/nil 2
13
/1 4
11
/3 9
10
/4
3
12
/2 5
8
/4 6
7
/5
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Running DFS on directed graphs
Again (as with BFS), we can run DFS on a digraph G .
Again, no longer do we obtain spanning trees of the
connected components of the start vertex.
But we obtain a directed spanning tree with exactly all
vertices reachable from the root (when following the
directions of the edges).
Different from BFS, the root (or start vertex) normally does not
play a prominent role for DFS:
1 Thus we did not provide the form of DFS with a start
vertex as input.
2 But we provided the forest-version, which tries all vertices
(in the given order) as start vertices.
3 This will always cover all vertices, via a directed spanning
forest.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
What are the times good for?
(Directed) DFS trees do not contain shortest paths — to that
end their way of exploring a graph is too “adventuresomely”
(while BFS is very “cautious”).
Nevertheless, the information gained through the computation
of discovery and finish times is very valuable for many tasks. We
consider the example of “scheduling” later.
In order to understand this example, we have first to gain a
better understanding of the meaning of discovery and finishing
time.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Existence of a path versus finishing times
Lemma 1
Consider a digraph G and nodes u, v ∈ V (G ) with d [u] < d [v ].
Then there is a path from u to v in G if and only if f [u] > f [v ]
holds.
In words: If node u is discovered earlier than node v , then we
can reach v from u iff v finishes earlier than u.
Proof.
If there is a path from u to v , then, since v was discovered later
than u, the recursive call of DFS-Visit(v) must happen inside
the recursive call of DFS-Visit(u) (by construction of the
discovery-loop), and thus v must finish before u finishes.
In the other direction, if v finishes earlier than u, then the
recursive call of DFS-Visit(v) must happen inside the
recursive call of DFS-Visit(u) (since the recursion for u must
still be running). Thus, when discovering v , we must be on a
path from u to v .
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Directed acyclic graphs
An important applications of digraphs G is with scheduling:
The vertices are the jobs (actions) to be scheduled.
A directed edge from vertex u to vertex v means a
dependency, that is, action u must be performed before
action v .
Now consider the situation where we have three jobs a, b, c and
the following dependency digraph:
G = a // b
��⑧⑧
⑧⑧
⑧⑧
⑧⑧
c
__❃❃❃❃❃❃❃❃
Clearly this can not be scheduled!
In general we require G to by acyclic, that is, G must not
contain a directed cycle.
A directed acyclic graph is also called a dag.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Topological sorting
Given a dag G modelling a scheduling task, a basic task is to
find a linear ordering of the vertices (“actions”) such that all
dependencies are respected.
This is modelled by the notion of “topological sorting”.
A topological sort of a dag is an ordering of its vertices
such that for every edge (u, v), u appears before v in the
ordering.
For example consider
G = a // b
c
??⑧⑧⑧⑧⑧⑧⑧⑧
The two possible topological sortings of G are a, c , b and c , a, b.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Finishing times in DAGs
Lemma 2
After calling DFS on a dag, for every edge (u, v) we have
f [u] > f [v ].
Proof.
There are two cases regarding the discovery times of u and v :
1 If d [u] < d [v ], then by Lemma 1 we have f [u] > f [v ] (since
there is a path from u to v (of length 1)).
2 Now assume d [u] > d [v ]. If f [u] > f [v ], then we are done,
and so assume that f [u] < f [v ]. But then by Lemma 1
there is a path from v to u in G , and this together with the
edge from u to v establishes a cycle in G , contradicting
that G is a dag.
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Topological sorting via DFS
Corollary 3
To topologically sort a dag G, we run DFS on G and print the
vertices in reverse order of finishing times. (We can put each
vertex on the front of a list as they are finished.)
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Topological sorting illustrated
Consider the result of running the DFS algorithm on the
following dag.
m n o p
q r s
t u v w
x y z
1/20 21/26 22/25 27/28
2/5
6/19
23/243/4
7/8 10/17
13/16
11/12 9/18 14/15
(labelling: d [u]/f [u])
Listing the vertices in reverse order of finishing time gives the
following topological sorting of the vertices:
u : p n o s m r y v w z x u q t
f [u]: 28 26 25 24 20 19 18 17 16 15 12 8 5 4
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Deciding acyclicity
For a graph G (i.e., undirected) detecting the existence of a
cycle is simple, via BFS or DFS:
G has a cycle (i.e., is not a forest) if and only if
BFS resp. DFS will discover a vertex twice.
One has to be a bit more careful here, since the parent vertex
will always be discovered twice, and thus has to be excluded, but
that’s it.
However for digraphs it is not that simple — do you see why?
CS 270
Algorithms
Oliver
Kullmann
Analysing
BFS
Depth-first
search
Analysing
DFS
Dags and
topological
sorting
Detecting
cycles
Revisiting the lemma for topological sorting
In Lemma 2 we said:
If G has no cycles, then along every edge
the finishing times strictly decrease.
So if we discover in digraph G an edge (u, v) with f [u] < f [v ],
then we know there is a cycle in G .
Is this criterion also sufficient?
YES: just consider a cycle, and what must happen with the
finishing times on it.
Lemma 4
Consider a digraph G. Then G has a cycle if and only if every
run of DFS on G yields some edge (u, v) ∈ E (G ) with
f [u] < f [v ].
Depth-first search
Analysing BFS
Depth-first search
Analysing DFS
Dags and topological sorting
Detecting cycles
270-1/CW_1
Swansea University
Computer Science
CS-270 Algorithms 2013/14
Coursework I
Oliver Kullmann, 24/10/2013
Deadline: 8/11/2013
• See https://science.swansea.ac.uk/
intranet/help/students/coursework
for how to submit.
• See the course home-page http:
//www.cs.swan.ac.uk/~csoliver/
Algorithms201314/index.html for gen-
eral information on the course work.
• If you have collaborated with another stu-
dent (as it is advised), clearly state his/her
name and student number.
The complete coursework must be written in its
entirety by you. If you use any sources other
than the course-book, then you must clearly cite
it, and you need to explain how you used it.
Since we cannot return your coursework to
you, please keep a copy for yourself.
1. Formulate, in your own words (really im-
portant) a kind of “framework” for working
out Θ-expressions:
(a) These rules should be tailored to the
task at hand: not a general theory, but
something workable which suffices for
the task (Part 2).
(b) Try to be as precise as possible.
In Part 2, you need to state which
rules you applied, and the application
should be always obvious.
(c) Give examples for each rule.
(d) You need to justify these rules, but
it definitely doesn’t need to be a
mathematical explanation: you might
cite the book, or even some Internet
sources might be used (only if they are
really authoritative — sorry, but other
students don’t count here).
[30 marks]
2. Give Θ-expressions which are as simple as
possible, and state the rules (your rules!)
you applied:
5n3 − 8n + 11n4 = Θ(?)
2n + 3n + n500 = Θ(?)
√
n + log(n) = Θ(?)
n · (n + 1) · (n + 2) = Θ(?)
[20 marks]
3. Sort the nine expressions into asymptotic
ascending order (i.e., if f(x) is left of g(x),
then you need to have f(x) = O(g(x)):
lg n,
√
n− lg(n), 2n+1,
√
n + n
3.4n, 4n, nn, n2 + n3, 2n, n + n2
You need also to give some justifica-
tion (could be a mathematical proof, but
doesn’t need to be) for each relation in this
list, in the form of “f(x) = O(g(x)) be-
cause of ...”. In some cases we even have a
relation f(x) = Θ(g(x)), which needs to be
stated and argued for. [20 marks]
4. State in your own words a methodology for
solving recurrences as considered by us:
(a) Here the source shall be just the lec-
ture notes (nothing else).
(b) Say clearly, what is given (the “prob-
lem”), and how to solve it, as a kind
of (little) tutorial.
(c) Give two examples for each case.
[30 marks]
https://science.swansea.ac.uk/intranet/help/students/coursework
https://science.swansea.ac.uk/intranet/help/students/coursework
http://www.cs.swan.ac.uk/~csoliver/Algorithms201314/index.html
http://www.cs.swan.ac.uk/~csoliver/Algorithms201314/index.html
http://www.cs.swan.ac.uk/~csoliver/Algorithms201314/index.html
392358
Highlight
270-1/Thumbs.db
