程序代写代做代考 go C algorithm Algorithms Week 2

Algorithms Week 2
Ljubomir Perkovi ́c, DePaul University

Course overview: core techniques
Algorithm design techniques that we will use in this class include: 1 divide-and-conquer
2 backtracking
3 dynamic programming
4 greedy
All of the above techniques rely on reductions.

Reductions
As your textbook says:
“Reductions are the single most common technique used in designing algorithms.
Reducing one problem X to another problem Y means to write an algorithm for X that uses an algorithm for Y as a black box or subroutine.
Crucially, the correctness of the resulting algorithm for X cannot depend in any way on how the algorithm for Y works. The only thing we can assume is that the black box solves Y correctly. The inner workings of the black box are simply none of our business; they’re somebody else’s problem. It’s often best to literally think of the black box as functioning purely by magic.”

Recursion
Recursion is a special type of reduction that reduces a problem instance to one or more simpler instances of the same problem.
All four algorithm design techniques 1 divide-and-conquer
2 backtracking
3 dynamic programming
4 greedy
that we will use in this class can be described using recursion.

Divide-and-conquer approach
A divide-and-conquer algorithm works as follows:
1 If the problem is small enough, solve it directly (and quickly).
2 Otherwise, divide it into subproblems (Divide) that your solve recursively (“as a black box functioning purely by magic”!)
3 Combine the solutions to the subproblems into a solution of the original problem (Conquer)

Sorting
A fundamental problem is sorting an array of numbers. Input: An array A[1..n] of n numbers
Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n]
There are many different ways of approaching the problem
InsertionSort works by repeatedly moving elements into their proper relative positions

MergeSort
A fundamental problem is sorting an array of numbers. Input: An array A[1..n] of n numbers
Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n]
There are many different ways of approaching the problem
MergeSort recursively sorts each half of the array recursively and then merges the two sorted halves

MergeSort
MergeSort(A[1..n])
if n > 1
m ← ⌊n/2⌋ MergeSort(A[1..m]) MergeSort(A[m+1..n]) Merge(A[1..n], m)
We describe Merge next

Merging the sorted halves
The specification for the Merge procedure is:
Input: An array A[1..N] and index m such that A[1..m] and
A[m + 1..n] are sorted in non-decreasing order.
Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n]

Merge
Merge(A[1..n], m) i← 1; j← m+1 for k ← 1 to n
if j > n
B[k]← A[i]; i← i+1
else if i > m
B[k]← A[j]; j← j+1
else if A[i] < A[j] B[k]← A[i]; i← i+1 else B[k]← A[j]; j← j+1 for k ← 1 to n A[k] ← B[k] Merge Merge(A[1..n], m) i← 1; j← m+1 for k ← 1 to n if j > n
B[k]← A[i]; i← i+1
else if i > m
B[k]← A[j]; j← j+1
else if A[i] < A[j] B[k]← A[i]; i← i+1 else B[k]← A[j]; j← j+1 for k ← 1 to n A[k] ← B[k] Correctness: After iteration k, B[1..k] holds the smallest k elements of A in sorted order. Merge Merge(A[1..n], m) i← 1; j← m+1 for k ← 1 to n if j > n
B[k]← A[i]; i← i+1
else if i > m
B[k]← A[j]; j← j+1
else if A[i] < A[j] B[k]← A[i]; i← i+1 else B[k]← A[j]; j← j+1 for k ← 1 to n A[k] ← B[k] Running time: O(n) Running time analysis of MergeSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first recursive call to MergeSort takes T(⌊n⌋) time. 2 • The second recursive call to MergeSort takes T(⌈n⌉) time. 2 • The call to Merge takes O(n) time. and we thus we get the recurrence relation: T(n) = T(⌊n⌋) + T(⌈n⌉) + O(n) 22 Running time analysis of MergeSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first recursive call to MergeSort takes T(⌊n⌋) time. 2 • The second recursive call to MergeSort takes T(⌈n⌉) time. 2 • The call to Merge takes O(n) time. and we thus we get the recurrence relation: T(n) = T(n) + T(n) + O(n) 22 We can safely ignore the floors an ceilings (see textbook). Running time analysis of MergeSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first recursive call to MergeSort takes T(⌊n⌋) time. 2 • The second recursive call to MergeSort takes T(⌈n⌉) time. 2 • The call to Merge takes O(n) time. and we thus we get the recurrence relation: T(n) = 2T(n) + O(n) 2 We can safely ignore the floors and ceilings (see textbook). Recurrence relations A recurrence relation is a recursive way to define a function. It has two parts: 1 The recursive definition, that is, the part that describes T(n) in terms of itself on smaller sized inputs. For example, T (n) = 2T (n/2) + f (n) Or, a bit more loosely, T(n) = 2T(n/2) + O(n). 2 The initial conditions, that is, the part that determines when the recurrence stops. For example, T (1) = 1 Or, T(1) = O(1), which we will in general assume and not write down. Solving recurrence relations We can solve recurrence relations using recursion trees, which is a rooted tree with one node for each recursive subproblem. The value of each node is the amount of time spent on the corresponding subproblem excluding recursive calls. Solving recurrence relations We can solve recurrence relations using recursion trees, which is a rooted tree with one node for each recursive subproblem. The value of each node is the amount of time spent on the corresponding subproblem excluding recursive calls. Example: T(n) = 2T(n/2) + O(n) n n/2 n/2 n/4 n/4 n/4 n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 Solving recurrence relations Thus, the overall running time of the algorithm is the sum of the values of all nodes in the tree. Since each row adds up to n and since there are log2 n rows (why?) the total running time T(n) is O(nlogn). Example: T(n)=2T(n/2)+O(n)=O(nlogn) n n/2 n/2 n/4 n/4 n/4 n/4 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 Sorting A fundamental problem is sorting an array of numbers. Input: An array A[1..n] of n numbers Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n] There are many different ways of approaching the problem InsertionSort works by repeatedly moving elements into their proper relative positions MergeSort A fundamental problem is sorting an array of numbers. Input: An array A[1..n] of n numbers Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n] There are many different ways of approaching the problem MergeSort recursively sorts each half of the array recursively and then merges the two sorted halves QuickSort A fundamental problem is sorting an array of numbers. Input: An array A[1..n] of n numbers Output: A re-ordering of the numbers in the array such that A[1] ≤ A[2] ≤ · · · ≤ A[n] There are many different ways of approaching the problem QuickSort partitions the array into three parts: an element chosen to be the pivot, a subarray containing elements smaller than the pivot, and a subarray containing elements larger than the pivot. QuickSort then recursively sorts the two subarrays. QuickSort QuickSort(A[1..n]) if (n > 1)
Choose a pivot element A[p] r ← Partition(A[1..n], p) QuickSort(A[1..r-1]) QuickSort(A[r+1..n])
We describe Partition next

Partition
The Partition procedure has the following specification: Input: An array A[1..N] and a pivot element P = A[p]
where 1 ≤ p ≤ N.
Output: Modified array A with an index r such that entries in A[1..r − 1] are less than P, entries in A[r + 1..n] are greater than or equal to P, and A[r] = P.

Partition
Partition(A[1..n], p) swap A[p] ↔ A[n] l←0
for i ← 1 to n – 1
if A[i] < A[n] l← l+1 swap A[l] A[i] swap A[n] ↔ A[l + 1] return l + 1 Partition Partition(A[1..n], p) swap A[p] ↔ A[n] l←0 for i ← 1 to n - 1 if A[i] < A[n] l← l+1 swap A[l] A[i] swap A[n] ↔ A[l + 1] return l + 1 Correctness: At the end of each iteration of the main loop, everything in the subarray A[1..l] is < A[n] and everything in the subarray A[l + 1..i] is ≥ A[n]. Partition Partition(A[1..n], p) swap A[p] ↔ A[n] l←0 for i ← 1 to n - 1 if A[i] < A[n] l← l+1 swap A[l] A[i] swap A[n] ↔ A[l + 1] return l + 1 Correctness: At the end of each iteration of the main loop, everything in the subarray A[1..l] is < A[n] and everything in the subarray A[l + 1..i] is ≥ A[n]. Running time: O(n). Running time analysis of QuickSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first call to Quicksort takes T (r − 1) time. • The second call to QuickSort takes T (n − r ) time. • The call to Partition takes O(n) time. and we thus we get the recurrence relation: T(n) = T(r − 1) + T(n − r) + O(n) Running time analysis of QuickSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first call to Quicksort takes T (r − 1) time. • The second call to QuickSort takes T (n − r ) time. • The call to Partition takes O(n) time. and we thus we get the recurrence relation: T(n) = T(r − 1) + T(n − r) + O(n) If we could magically choose the pivot to be the median then T(n) = 2T(n/2) + O(n) Running time analysis of QuickSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first call to Quicksort takes T (r − 1) time. • The second call to QuickSort takes T (n − r ) time. • The call to Partition takes O(n) time. and we thus we get the recurrence relation: T(n) = T(r − 1) + T(n − r) + O(n) If we could magically choose the pivot to be the median then T (n) = 2T (n/2) + O(n) = O(n log n) Running time analysis of QuickSort Let T(n) be the time needed to sort an array of n elements. • Lines 1 and 2 take constant time each. • The first call to Quicksort takes T (r − 1) time. • The second call to QuickSort takes T (n − r ) time. • The call to Partition takes O(n) time. and we thus we get the recurrence relation: T(n) = T(r − 1) + T(n − r) + O(n) If the pivot happens to be the smallest or largest entry then T(n) = T(n − 1) + O(n) Running time analysis of QuickSort If the pivot happens to be the smallest or largest entry then T(n) = T(n − 1) + O(n) n n−1 n−2 n−3 Running time analysis of QuickSort If the pivot happens to be the smallest or largest entry then T(n) = T(n − 1) + O(n) = O(n2) n n−1 n−2 n−3 Running time analysis of QuickSort What if we can guarantee that the pivot is in the middle half of the array? Then T(n) ≤ T(3n/4) + T(n/4) + O(n) Running time analysis of QuickSort What if we can guarantee that the pivot is in the middle half of the array? Then T (n) = T (3n/4) + T (n/4) + O(n) = O(n log n) since all rows sum to n and the depth of the tree is log4/3 n. 3n/4 n/4 n 9n/16 3n/16 3n/16 n/16 Running time analysis of QuickSort In Section 1.8, your textbook describes an algorithm that can be used to find the pivot in O(n) time. Therefore the worst-case running time of QuickSort can be made O(n log n). (Last week) Exponentiation Consider the problem of computing an: Input: number a and positive integer n Output: an Example: givena=1.5andn=2,an =1.52 =2.25 The obvious algorithm: SlowPower(a, n) res ← a for i ← 2 to n res ← res * a return res (Last week) Exponentiation Consider the problem of computing an: Input: number a and positive integer n Output: an Example: givena=1.5andn=2,an =1.52 =2.25 The obvious algorithm: SlowPower(a, n) res ← a for i ← 2 to n res ← res * a return res Running time: T(n) = O(n) (Last week) Exponentiation Consider the problem of computing an: Input: number a and positive integer n Output: an Example: givena=1.5andn=2,an =1.52 =2.25 The obvious algorithm: SlowPower(a, n) res ← a for i ← 2 to n res ← res * a return res Running time: T(n) = O(n) How could divide-and-conquer possibly help? (Last week) Fast exponentiation Indian scholar Pingala proposed the following recursive formula in 2nd century BCE! 1 if n = 0 an =(an/2)2 ifn>0andniseven
(a⌊n/2⌋)2a otherwise
which leads to the following exponentiation algorithm:
PingalaPower(a, n) if n ← 1
return a
tmp ← PingalaPower(a, ⌊n/2⌋) if n is even
return tmp*tmp
else
return tmp*tmp*a

Running time analysis of PingalaPower
The running time T(n) for input n satisfies T(n) = T(n/2) + O(1)
1 1 1 1

Running time analysis of PingalaPower
The running time T(n) for input n satisfies T (n) = T (n/2) + O(1) = O(log n)
since the depth of the tree is log2 n.
1 1 1 1

Exercise: What is the running time of BinarySearch?
The recurrence relation for BinarySearch is

Exercise: What is the running time of BinarySearch?
The recurrence relation for BinarySearch is
T (n) = T ( n ) + O (1) 2

Exercise: What is the running time of BinarySearch?
The recurrence relation for BinarySearch is
T (n) = T ( n ) + O (1) = O (log n) 2

Fast multiplication
Multiplying two n-digit numbers x and y using a traditional multiplication algorithm requires O(n2) single-digit multiplications.
xn−1 xn−2 xn−3 … x3 x2 x1 x0 × yn−1 yn−2 yn−3 … y3 y2 y1 y0

Fast multiplication
Multiplying two n-digit numbers x and y using a traditional multiplication algorithm requires O(n2) time.
xn−1 xn−2 xn−3 … x3 x2 x1 x0 × yn−1 yn−2 yn−3 … y3 y2 y1 y0

Fast multiplication
xn−1 xn−2 xn−3 … x3 x2 x1 x0 × yn−1 yn−2 yn−3 … y3 y2 y1 y0

Fast multiplication
xn−1 xn−2 xn−3 … x3 x2 x1 x0 × yn−1 yn−2 yn−3 … y3 y2 y1 y0
Let a, b, c, and d be numbers defined as follows:
a = xn−1 xn−2 … xm+1 xm b = xm−1 xm−2 … x1 x0 c = yn−1 yn−2 … y1 y0 d = ym−1 ym−2 … y1 y0
Then xy = (10ma+b)(10mc +d) = 102mac +10m(bc +ad)+bd.
If m ≈ n/2, multiplying two n-digit numbers is reduced to multiplying 4 n/2-digit numbers: ac, bc, ad, and bd.

Fast multiplication
SplitMultiply(x, y, n): if n = 1
return xy
else
m ← ⌈n/2⌉
a ←⌊x/10m⌋; b ←x mod10m c ←⌊y/10m⌋; d ←y mod10m e ← SplitMultiply(a, c, m) f ← SplitMultiply(b, d, m) g ← SplitMultiply(b, c, m) h ← SplitMultiply(a, d, m)
return 102me + 10m(g + h) + f
Running time: T(n) = 4T(n/2) + O(n)

Running time analysis
The running time of this divide-and-conquer multiplication algorithm is
T(n) = 4T(n/2) + O(n)
n
n/2 n/2
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

Running time analysis
The running time of this divide-and-conquer multiplication algorithm is
T(n) = 4T(n/2) + O(n) = O(n2)
since the rows add up to the geometric progression
n,2n,22n,23n,…,2lognn which adds up to O(n2). n
n/2 n/2
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

Fast multiplication
xn−1 xn−2 xn−3 … x3 x2 x1 x0 × yn−1 yn−2 yn−3 … y3 y2 y1 y0
Let a, b, c, and d be numbers defined as follows:
a = xn−1 xn−2 … xm+1 xm b = xm−1 xm−2 … x1 x0 c = yn−1 yn−2 … y1 y0 d = ym−1 ym−2 … y1 y0
Then xy = (10ma+b)(10mc +d) = 102mac +10m(bc +ad)+bd.
In the mid-1950s, Karatsuba, a 23 year old student, realized that we do not necessary need to compute bc and ad to get (bc + ad). One can compute (bc + ad) as follows:
ac + bd − (a − b)(c − d) = bc + ad

Fast multiplication
FastMultiply(x, y,n): if n ← 1
return xy
else
m ← ⌈n/2⌉
a ← ⌊x/10m⌋; b ← xmod10m
c ← ⌊y/10m⌋; d ← ymod10m
e ← FastMultiply(a, c, m)
f ← FastMultiply(b, d, m)
g ← FastMultiply(a – b, c return102m e+10m (e+f-g)+f
Running time: T(n) = 3T(n/2) + O(n).
– d, m)

Solving recurrence relations
The running time of the 2nd divide-and-conquer multiplication algorithm is
T(n) = 3T(n/2) + O(n)
n
n/2 n/2 n/2
n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4

Solving recurrence relations
The running time of the 2nd divide-and-conquer multiplication algorithm is
T(n) = 3T(n/2) + O(n) = O(n1.58496)
since the rows add up to the geometric progression
n, 3n/2, (3/2)2n, (3/2)3n, . . . , (3/2)log2 nn which adds up to O(nlog2 3) = O(n1.58496).
n
n/2 n/2 n/2
n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4 n/4

Finding the closest pair of points
Given n points on the plane,

Finding the closest pair of points
Given n points on the plane, find the pair that is closest together.

Finding the closest pair of points
Input: Points p1, . . . , pn where pi has coordinates (xi , yi ). Output: Pair pi,pj whose distance d(pi,pj) is smallest.

Divide-and-conquer approach

Divide-and-conquer approach
Step 1: Sort the points by x-coordinate
l

Divide-and-conquer approach
Step 1: Sort the points by x-coordinate
Step 2: Split the plane at the median point and recursively find the closest pair of points in each half
l

Divide-and-conquer approach
Step 1: Sort the points by x-coordinate
Step 2: Split the plane at the median point and recursively find the closest pair of points in each half
Step 3: Return the closer of the two pairs!
l

Finding the closest opposite pair of points
Insight 1: If there is a pair of opposite points whose distance is less than δ their distance from line l must be less than δ
l
δδ

Finding the closest opposite pair of points
Step 1.1: Sort the points by y-coordinate to get ordered list Sy. Let Sy′ be the sublist of Sy consisting of points in the narrow 2δ band.
Insight 2: If two points in Sy′ are closer than δ then the points must be within 15 positions of each other in the list.
l
δ
δ

Finding the closest opposite pair of points
Step 1.1: Sort the points by y-coordinate to get ordered list Sy. Step 3: Construct sublist Sy′ from Sy and then go through list Sy′ and for each point compute the distance to the next 15 points in Sy′ to find closest pair of opposite points whose distance is < δ, if any. l δ δ Running Time Analysis • Steps 1 and 1.1 take O(n log(n)) time each and are done only once. • Step 2 consists of two recursive calls, each taking T(n/2) time. • Step 3 consists of a sequential search through Sy followed by a sequential search through Sy′ which takes a total time of O(n). If T(n) is the running time of steps 2 and 3 then T (n) = 2T (n/2) + O(n) = O(n log n). By homework problem 1(c), the running time of the whole algorithm is O(n log n).

Related Posts