COMP 3711 Design and Analysis of Algorithms
Lecture 2: Divide & Conquer – Intro
Divide-and-Conquer intro: Binary search
Copyright By PowCoder代写 加微信 powcoder
Main idea of DaC: Solve a problem of size n by breaking it into one or more smaller problems of size less than n. Solve the smaller problems recursively and combine their solutions, to solve the large problem
Example: Binary Search
Input: A sorted array A[1..n], and an element x.
Output: Return the position of x, if it is in A; otherwise output nil.
Idea of binary search : Set q middle of the array. If x = A[q], return q. If x < A[q], search A[1..q-1]. If x > A[q], search A[q+1..n]
BinarySearch( ):
if then return
if return
if thenBinarySearch() else BinarySearch( )
First call: BinarySearch( )
Binary Search Example
1 2 3 4 5 6 7 8 9 10
(A, 1, 10, 42)
q = A[5] = 19
(A, 6, 10, 42)
q = A[8] = 54
(A, 6, 7, 42)
q = A[6] = 20
(A, 7, 7, 42)
(A, 7, 7, 42)
Analysis of Binary Search
Analysis: Let be the number of comparisons needed for elements.
Recurrence: With a single comparison we eliminate half of the array. => we search for the element in the remaining half, which has size n/2. Thus, the recurrence counting the number of comparisons is:
if n > 1, with Solve the recurrence by the expansion method:
= 1
+ 1
Note: Binary search may General terminate faster than
Case , but the worst- case running time is still
+
Binary Search recurrence with the recursion tree method
For #problems (nodes)
Comparisons per level
level level
level
level ( level
per level level
level level
level
Total number of comparisons:
Note: This is actually equivalent to the expansion method but more visual.
Exercise 1a Rotated Sorted Array
Suppose you are given a sorted array A of n distinct numbers that has been rotated k steps, for some unknown integer k between 1 and also sorted in increasing order, and A[n] < A[1]. The following array A is an example of n = 16 elements with k = 10.
A = [9, 13, 16, 18, 19, 23, 28, 31, 37, 4=k2, 0, 1, 2, 5, 7, 8].
1) Design an O(log n)-time algorithm to find the value of k. (A[k] is the maximum element in the array)
Find-k(A, p, q)
m (p+q)/2
if A[m] > A[m + 1] then return m
-k(A, m+1, q) Else return Find-
This is similar to binary search: with a constant number of comparisons, we reduce the problem size by half: T(n)=T(n/2)+c T(n) = O(logn)
Exercise 1b Rotated Sorted Array (cont)
2) Design an O(log n)-time algorithm that for any given x, finds x in the rotated sorted array, or reports that it does not exist.
Find-x(A, x)
k Find-k(A, 1, n)
BinarySearch(A, 1, k, x) Else return BinarySearch(A, k + 1, n, x)
Exercise 2a Finding the last 0
You are given an array A[1..n] that contains a sequence of 0 followed by a sequence of 1 (e.g., 0001111111). A contains at least one 0 and one 1.
1 ) Design an O(log n)-time algorithm that finds the position k of the last 0, i.e., A[k] = 0 and A[k + 1] = 1.
find-k(A[p..r])
if r=p+1, RETURN p
mid (p+r)/2
if A[mid]=0 and A[mid+1]=1, RETURN mid if A[mid]=0, find-k(A[mid..r])
else find-k(A[p..mid])
Exercise 2b Finding the last 0 (cont)
2) Suppose that k is much smaller than n. Design an O(log k)- time algorithm that finds the position k of the last 0. (you can re-use solution of part 1).
while A[i]=0
i2i find-k(A[i/2+1..i])
The while loop will stop when it finds a 1. Since each time we double the value of i, the while loop performs logk iterations. The first 1 occurs somewhere between the positions A[i/2+1] and A[i]. To find it, we call find-k(A[i/2+1..i]), which has cost log(k/2)= O(logk). Therefore, the total cost is O(logk).
More complex example: Towers of Hanoi
Goal: Move discs from peg A to peg C
One disc at a time
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
The base case
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 frompeg1to2
3: move
disk frompeg1to3
disks from peg 2 to 3
Thus, the recurrence counting the number of steps is:
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
General Case
=
=
+ + +2 +1 geometric series
+ + +2 +1
Exercise 3 Geometric Series Assume c is a positive constant. Prove that
Set =1+c+c2++cn-1
Then,
For c>1,
For c<1,
) (also (cn-1) because )
)
In general the largest term dominates the asymptotic cost:
Solving the recurrence with the recursion tree method
For
level node level nodes
levelnodes level nodes
level nodes level nodes
1 1
1 1
1 1 1 1 1 11 1 1 11 1
total number of nodes: each doing one unit of work
Merge sort
Mergesort( ): if then return Mergesort( ) Mergesort( ) Merge( )
First call: Mergesort( )
Merge sort.
Divide array into two halves.
Recursively sort each half.
Merge two halves to make
sorted whole.
Merge. Combine two sorted lists into a sorted whole.
Merge( ):
create two new arrays and
,
append attheendof and
for to
if then
Merge: Example
Merge: Example
Splits each array into left and right Sorts Left
Sorts Right Merges results
Mergesort: Example
4 2 12 7 1 5 8 10 6 9 11 3
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 n 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 an big-O upper bound of
for any , let be the smallest power of such that ,
=> , as long as is a increasing polynomial function.
Simplified merge sort recurrence.
==
Solve the recurrence
=
=
Simplified merge sort recurrence.
Solve the recurrence
. . .
So, merge sort runs in time.
Running time of merge sort
Q: Is the running time of merge sort also
time no matter what the
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 .
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com