COMP 3711 Design and Analysis of

Algorithms

Divide & Conquer - Intro

 Divide-and-Conquer intro: Binary search
Main idea of DaC: Solve a problem of size by breaking it into one or more
smaller problems of size less than . Solve the smaller problems recursively
and combine their solutions to solve the large problem.

Example: Binary Search

Input: A sorted array and an element .

Output: Return the position of , if it is in ; otherwise output nil.

Idea of binary search : Set middle of the array. If , return .

If , search . If , search

BinarySearch():
if then return

if return
if then BinarySearch()
else BinarySearch()

First call: BinarySearch()

2
 Binary Search Example

1 2 3 4 5 6 7 8 9
10 7
4 10 15 19 20 42 54 87 90 (A, 1, 10, 42)

4 7 10 15 19 20 42 54 87 90 𝑞= 𝐴 [ 5 ] =19

4 7 10 15 19 20 42 54 87 90 (A, 6, 10, 42)

4 7 10 15 19 20 42 54 87 90 𝑞= 𝐴 [ 8 ] =54

4 7 10 15 19 20 42 54 87 90 (A, 6, 7, 42)

4 7 10 15 19 20 42 54 87 90 𝑞= 𝐴 [ 6 ] =20

4 7 10 15 19 20 42 54 87 90 (A, 7, 7, 42)

4 7 10 15 19 20 42 54 87 90 (A, 7, 7, 42)
FOUND

3
 Analysis of Binary Search

Analysis: Let be the number of comparisons needed for elements.

Recurrence: With at most two comparisons we eliminate half of the

array.
=> we search for the element in the remaining half, which has size .
Thus, the recurrence counting the number of comparisons is:

if n > 1, with
Solve the recurrence by the expansion method:
= 2
= +2 Note: Binary search
may terminate faster
= +4 Genera
than , but the worst-
l
= .…. Case case running time is
= + 2i still
𝑖=log 2 𝑛
= ….
= +
=
¿ 𝟏+𝟐 𝐥𝐨𝐠𝟐 𝐧 4
 Binary Search recurrence with the recursion tree method
For

#problems (nodes) Comparisons

per level per level
level 𝑇 (𝑛 ) 2 level

level 𝑇 ( 𝑛 / 2) 2 level

level 𝑇 ( 𝑛 / 2𝑖 ) 2 level

level 2 level (

𝑇 ( 1) level

Total number of comparisons:

Note: This is actually equivalent to the expansion method but more

5
 Exercise 1a Rotated Sorted Array
L be a sorted array of distinct numbers that has been rotated
steps for some unknown integer . That is, is sorted in increasing
order, and is also sorted in increasing order, and . The following
array is an example of elements with .

= [9, 13, 16, 18, 19, 23, 28, 31, 37, 42, 0, 1, 2, 5, 7, 8].
1) Design an -time algorithm to find the value of . ( is the
maximum element in the array)

Find-k(

if then return
if then return Find-k()
Else return Find-k()

First call: Find-k()

This is similar to binary search: with a constant number of

comparisons, we reduce the problem size by half:

6
 Exercise 1b Rotated Sorted Array (cont)
2) Design an -time algorithm that for any given , find in
the rotated sorted array, or report that it does not exist.

Find-x()
← Find-k()
if then return BinarySearch()
Else return BinarySearch()

7
 Exercise 2a Finding the last 0
You are given an array that contains a sequence of 0
followed by a sequence of 1 (e.g., 0001111111). contains
at least one 0 and one 1.
1 ) Design an -time algorithm that finds the position of the
last , i.e., and .

find-k()
←
if and , RETURN
if , find-k()
else find-k(

First call: find-k()

8
 Exercise 2b Finding the last 0 (cont)
2) Suppose that is much smaller than . Design an -time
algorithm that finds the position of the last 0. (you can re-
use solution of part 1).

1
while

find-k()

The while loop will stop when it finds a 1. Since each time
we double the value of , the while loop performs iterations.
The first 1 occurs somewhere between the positions and .
To find it, we call find-k(), which has cost . Therefore, the
total cost is

9
 More complex example: Towers of Hanoi

Goal: Move discs from peg A to peg C


One disc at a time

Can’t put a larger disc on top of a smaller one

MoveTower(, peg1, peg2, peg3):

if then
move the only disc from peg1 to peg3
return
else
MoveTower(, peg1, peg3, peg2)
move the only disc from peg1 to peg3
MoveTower(, peg2, peg1, peg3)

First call: MoveTower()

Keys things to remember:

Reduce a problem to the same problem, but with a smaller


size
10
 Analyzing a recursive algorithm with recurrence
Q: How many steps (movement of discs) are needed?

Analysis: Let be the number of steps needed for discs.

In the recursive algorithm, to solve the problem of size n, we:


1: move disks from peg 1 to 2

2: move disk from peg 1 to
3

3: move disks from peg 2 to 3
Thus, the recurrence counting the number of steps is:

11
 Solving the recurrence with the Expansion method

The recurrence counting the number of steps is

Solve the recurrence by the expansion method:

= 1

= 2

= + 2 +1

= + +2 +1
= .….
Genera
l = + + +2 +1
Case = .…. geometric series

𝑖=𝑛 −1 = + + +2 +1
12
 Exercise 3 Geometric Series
Assume c is a positive constant. Prove that
Set
Then,

For , ) (also because )

For , )

In general, the largest term dominates the asymptotic

cost:

13
 Solving the recurrence with the recursion tree method

For

𝑇 ( 𝑛 )1 level node

𝑇 ( 𝑛 −1 1
) 𝑇 ( 𝑛 −1 )1 level nodes

𝑇 ( 𝑛 − 21)𝑇 ( 𝑛 − 21) 𝑇 ( 𝑛 − 21) 𝑇 ( 𝑛 − 21) level nodes

level nodes

𝑇 ( 2 1) 𝑇 ( 21) 𝑇 ( 21) 𝑇 ( 21) level nodes

……

𝑇 ( 11) 𝑇 ( 11)𝑇 ( 11) 𝑇 ( 1 1) 𝑇 ( 11) 𝑇 ( 11)𝑇 ( 11) 𝑇 ( 11) level nodes

total number of nodes:

each doing one unit of work
14
 Merge sort

Merge sort. Mergesort():


Divide array into two if then return
halves.

Recursively sort each half. Mergesort()
Mergesort()

Merge two halves to make
Merge()
sorted whole.
First call: Mergesort()

5 2 4 7 1 3 2 6

5 2 4 7 1 3 2 6 divide 𝑂 (1)

2 4 5 7 1 2 3 6 sort 2 𝑇 (𝑛/2)

1 2 2 3 4 5 6 7 merge 𝑂 (𝑛)

15
 Merge
Merge. Combine two sorted lists into a sorted whole.

Merge():
create two new arrays and
,
append at the end of and

for to
if then

else

16
Merge: Example

17
Merge: Example

18
Splits each array
into left and right Mergesort: Example
Sorts Left
Sorts Right
Merges results 1 5
2 4
3 8
4 10
5 2
6 6
7 9
8 12 11 11
9 10 3 12
7

1 2
5 4 5
8 8 10
10 2 6
3 9
6 12
7 11 3 12
9 11 7

1
1 4
5 5
4 2
8 8 10
10 2 6 9 12 11
3 3
7 7
11

1 5 4 8 10 2 6 9 12 11 3
3 11 7

1 5 8 10 6 9 11 3

19
 Analyzing merge sort

Def. Let be the running time of the algorithm on an array of size .

Merge sort recurrence.

A few simplifications

Replace with
– since we are interested in a big-O upper bound of

Replace with , replace with
– since we are interested in a big-O upper bound of
– Can also think of this as rescaling running time

Assume is a power of , so that we can ignore
– since we are interested in a big-O upper bound of
– for any , let be the smallest power of such that ,

=> ,
as long as is a increasing polynomial function.

20
 Solve the recurrence
Simplified merge sort recurrence.

==
=
=

¿ 𝑛 log 2 𝑛+ 𝑛
21
 Solve the recurrence 2
log2 𝑛 − 1
=
𝑛
2
Simplified merge sort recurrence.

𝑇 (𝑛)𝑛 𝑛
𝑛 𝑛
𝑇 (𝑛/2) 2 𝑇 (𝑛/ 2) 2 2 ⋅ 𝑛/ 2 ¿𝑛
𝑛 𝑛 𝑛 𝑛
𝑇 (𝑛/ 4)4 𝑇 (𝑛/ 4)4 𝑇 (𝑛/ 4)4 𝑇 (𝑛/ 4)4 4 ⋅ 𝑛/ 4 ¿𝑛
log 2 𝑛
...
𝑇 (𝑛/ 2 𝑖 ) 2 𝑖 ⋅ 𝑛/ 2 𝑖 ¿ 𝑛
...

𝑛
𝑇 (2) 𝑇 (2) ) 𝑇 (2) 𝑇 (2) 𝑇 (2) 𝑇 (2) 𝑇 (2) 2
log2 𝑛 − 1

2
log 2 𝑛 −1 ¿𝑛
𝑇 (1)𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑇 (1) 𝑛𝑇 ( 1 ) ¿𝑛

So, merge sort runs in time. 𝒏( 𝐥𝐨𝐠 𝟐 𝒏+𝟏)

22
 Running time of merge sort

Q: Is the running time of merge sort also

A: Yes

Since the “merge” step always takes time no matter what the
input is, the algorithm’s running time is actually “the same”
(up to a constant multiplicative factor), independent of the
input.

Equivalently speaking, every input is a worst case input.

The whole analysis holds if we replace every with

Theorem: Merge sort runs in time .

23