Unit 2: Divide and Conquer Algorithms

Prog.

Disc.

The divide-and-conquer strategy solves a problem by:

Breaking it into subproblems that are themselves smaller instances of the same type of problem

Recursively solving these subproblems

Appropriately combining their answers

Master Theorem

Divide-and-conquer algorithms often follow a generic pattern:

for some
they tackle a problem of size by recursively solving, say, subproblems of size
then combining these answers in time.

Their running time can therefore be captured by the equation

So, Master Theorem comes to find the running time of the divide-and-conquer algorithms as follows:

Master Theorem Cheatsheet

Examples of divide and conquer algorithms

Recurrence Two Numbers Multiplication based on Gauss Rule (Section 2.1 in Algorithms by Vazirani 2006)
Binary Search
Mergesort

Recursive functions can be analyzed using Recursion Tree, and the following shows the characteristics of the tree in case of using D&Q strategy, assuming is power of and is the level number

# of Levels = =
Subproblems in each level (width of each level) =
Size of each subproblem in each level =

Guiding Principles for Analysis of Algorithms

Conduct worst-case analysis:

Finding the running time bound holds for every input of length n

We find it for worst-case because it is appropriate for “general purpose” routines

It is easier to analyze

Worst-case is opposed to average-case analysis

This requires domain knowledge
It is used for benchmarking

Don’t pay much attention to constant factors, lower-order terms

Way easier mathematically

Constants depend on computer architecture, compilers, programming language. So, we want to model the algorithm in an abstract way for analysis

Doesn’t affect the prediction of algorithm’s power when we want to compare it with others.

Constant factors are sometimes important to consider in crucial programs

Asymptotic analysis:

Focus on running time for large input size n

Because only big problems are interesting

It doesn’t matter how is the performance with small inputs

More suitable to forget about the computational power

📌

Fast Algorithm worst-case running time grows slowly with input size Don’t forget: We cannot mathematically trace everything and we want to preserve the predictive power

Algorithm: Merge Sort

It has better performance than other normal sorting algorithms

Pseudocode

Sort Function


Base case (if n <= 1: return)
Recursively sort 1st half of input array
Recursively sort 2nd half of input array
Merge 2 sorted sublists into one (using Merge function) 
Return the sorted input array

Merge Function


// ascending sort

n = length of input array
C = OutputArray[length = n]
A = 1stSortedArray[n/2]
B = 2ndSortedArray[n/2]


// traverse A and B in parallel

// counter for A
i=1
// counter for B
j=1

// populate C based on the comparison
for k=1 to n
	if A[i] < B[j]:
		C[k] = A[i]
		i++
	else B[j] < A[i]:
		C[k] = B[j]
		j++
end

Running Time Analysis

# of operations in the level = = which is the # of operations per level regarding of
# of levels =
Total = = operations to sort numbers

Problem: Counting Inversions in an Array

📌

It is used to build recommendation systems

To calculate the largest number of inversions in an array of N elements:

Solution #1: Brute-force

By using two loops (the 2nd loop is nested)
It takes time

Solution #2: Divide & Conquer

(See Stanford lecture)
The solution is identical to Merge Sort, but the merge function has just a counter for inversion


'''
Problem: Giving an array $A$ with $N$ elements, find the pairs (A[i], A[j]) that meet the following critieria: i < j and A[i] > A[j]

The following solution is implemented in divide & conquer strategy (like Mergesort)
'''

# run in O(n logn)
def sort_and_count_inv(li):
    if len(li) <= 1:
        return li, 0
    
    mid = len(li)//2
    # the sorted version of 1st half
    C, left_inv = sort_and_count_inv(li[:mid])
    # the sorted version of 2nd half
    D, right_inv = sort_and_count_inv(li[mid:])
    # the final sorted list
    B, split_inv = merge_and_count(C, D)
    
    return B, left_inv+right_inv+split_inv


# run in O(n)
def merge_and_count(left, right):
    sorted = []
    inversions = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted.append(left[i])
            i += 1
        else:
            sorted.append(right[j])
            # numbers of all remaining items in the left half
            inversions = inversions + len(left) - i
            j += 1
    sorted += left[i:]
    sorted += right[j:]
    return (sorted, inversions)


print(sort_and_count_inv([2,4,1,3,1,12,3,2143,5]))

Problem: Strassen's Subcubic Matrix Multiplication Algorithm

Solution #1: Straightforward Matrix Multiplication method is defined according to the summation:

is a array
is a array
The resulted array is
Note that must be equal between and
Pseudocode (for integer square matrices and )


for i := 1 to n do
	for j := 1 to n do
		Z[i][j] := 0
		for k := 1 to n do
			Z[i][j] := Z[i][j] + X[i][k] · Y[k][j]
return Z

The running time of this algorithm is

Solution #2: Apply Divide & Conquer strategy (for square matrices )

First, divide the internal matrix items into submatrices

Recursively compute the 8 matrix products

The asymptotic complexity of this algorithm is also
Pseudocode


if n = 1 then // base case
	return the 1 x 1 matrix with entry X[1][1] · Y[1][1]
else // recursive case
	A, B, C, D := submatrices of X as in (3.3)
	E, F, G, H := submatrices of Y as in (3.3)
	recursively compute the eight matrix products 
	return the result of the summation

Solution #3: Apply Divide & Conquer strategy and Strassen’s algorithm (for square matrices )

If the matrices , are not of type we can think conceptually about filling the "missing" rows and columns with zeros to obtain matrices with sizes of powers of two -- though real implementations of the algorithm will of course not actually do this in practice.
Strassen’s algorithm decreases the number of required multiplication from 8 to 7 products
The new running time is:

By the master theorem, it works out to .
This decrease improves the performance and the asymptotic complexity would be

Pseudocode


if n = 1 then
	return the 1 x 1 matrix with entry X[1][1] · Y[1][1]

else // recursive case
	A, B, C, D := submatrices of X 
	E, F, G, H := submatrices of Y 
	recursively compute seven (cleverly chosen) products involving A, B, . . . , H
	return the appropriate (cleverly chosen) additions and subtractions of the matrices computed in the previous step

The Seven products:

P1 = A · (F - H)
P2 = (A + B) · H
P3 = (C + D) · E
P4 = D · (G - E)
P5 = (A + D) · (E + H)
P6 = (B - D) · (G + H)
P7 = (A - C) · (E + F)

Summations:

Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication.

https://www.youtube.com/watch?v=h7apO7q16V0

Polynomial multiplication is the main application for this algo

This application is important in many fields

This is the general form of computing the multiplication

There are three ways to represent a polynomial

Coefficients

Roots

Samples (Value representation)

The normal multiplication way (in coeff. representation) has a runtime , and FFT comes to do that in . This is the goal of this algorithm.

Value Representation (a.k.a. Samples Representation)

points uniquely define a degree polynomial

For example, given these points

We will have this quadratic function

There is a proof for that called Vandermonde Matrix

https://math.stackexchange.com/questions/426932/why-are-vandermonde-matrices-invertible

Multiplication in value rep. is only

So, this is the general plan to improve the polynomial multiplication

The issue we have is in converting between the representation types, and FFT handles this

Coeff → Value (Evaluation)

Finding points by calculating s by plug values in the function.

It takes

This can be improved to be O(n)

This way, we can formalize a general approach for dividing this problem based on even and odd terms:

holds the odd terms
holds the even terms

This division allows us to solve the subproblems recursively in

(Continue with roots of unity concept)

Value → Coeff

This process is called Interpolation (Inverse FFT)

It involves inversing the DFT matrix (Discrete Fourier Transform)

Code

The difference between both functions is only in the 6th line

Example with Code Breakdown

FFT Example: Unraveling the Recursion

This video is meant as further support to the main video on the FFT https://youtu.be/h7apO7q16V0 We break down how the FFT evaluates a particular polynomial at the roots of unity by unraveling the recursive process completely.

https://www.youtube.com/watch?v=Ty0JcR6Dvis

Amortized Algorithms

📌

Based on this lecture:

Lecture 13: Amortized Algorithms, Table Doubling, Potential Method

"OK, good morning. So today we are going to, as I mentioned last week, we've started the part of the course where we are doing more things having to do with design than purely analysis. Today, we're actually going to do analysis, but it's the type of analysis that leads to really interesting design issues.

http://videolectures.net/mit6046jf05_leiserson_lec13/

Dynamic Hash Table

Question: How large should a hash table be?

To improve search time: As large as possible
To make it space efficient: As small as possible

What if we don’t know how many items we want to hash and store in advance?

Solution: use Dynamic Tables

How Dynamic Table works:

Whenever the table gets too full (overflows), grow it by using malloc or new to allocate larger table (size )

Move all items from the old table into the new one

Free the storage for the old table

Worst-case analysis

Cost of 1 insertion:
Cost of n insertion: because insertion operation depends on the situation of the table at which the insertion happens (in case of overflow, expand the table and copy items etc.), we need to analyze this thoroughly

Let the cost of the th insertion, then

if is an exact power of →
else

By looking to the patterns

According to the pattern, the cost of insertions =
Therefore, the average cost of each dynamic table operation is

Amortized Analysis

Analyze a seq. of operations to show that the average cost per operation is small, even though one operation may be expensive

This analysis doesn’t involve any probability.

It only guarantees the average performance of each operation in the worst case

Types of amortized arguments:

Aggregate analysis method (described above)

Accounting method

Potential method

📌

2 and 3 are more precise because they allocate specific amortized costs to each operation

Accounting Method

Charge th operation a fictitious amortized cost

e.g. $1 pays for 1 unit of work

Fee is consumed to perform the operation

Unused amount stored in “bank” for use by later operations

Bank balance must not go negative!

Ensure that true costs must be bounded above by the amortized cost for all n

Accounting analysis of dynamic tables

Charge $3 for the th inser t

Pay $1 for immediate insert
Store $2 for table doubling

When table doubles

Pay $1 to move a recent item
Pay $1 to move an old item

Potential Method

Potential argument gives powerful results

“Bank Account” now is viewed as potential energy of dynamic set

Think of potential energy when extend a spring

Framework:

Start with some data structure
Operation transforms
Cost of operation is
Define potential function that maps the set of data structures into the Real Number such that and for all
Amortized cost is defined by the equation

Resources