21CSC204J

Design and Analysis of Algorithms

Prepared by
Dr L Josephine Usha
Asst.Professor/CSE
SRM Institute of Science and Technology
Syllabus Outline
• Unit I - Introduction
• Unit II - Divide-and-conquer
• Unit III - Greedy and Dynamic Programing
• Unit IV - Backtracking
• Unit V - Introduction to randomized and approximation algorithm

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 2

 Unit II Outline

• Introduction-Divide and Conquer - Maximum Subarray Problem.

• Binary Search - Complexity of binary search
• Merge sort - Time complexity analysis - Quick sort and its Time complexity
analysis Best case, Worst case, Average case analysis
• Strassen's Matrix multiplication and its recurrence relation - Time complexity
analysis of Merge sort - Largest sub-array sum - Time complexity analysis of
Largest subarray sum
• Master Theorem Proof - Master theorem examples - Finding Maximum and
Minimum in an array - Time complexity analysis-Examples
• Algorithm for finding closest pair problem – Convex Hull problem

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 3

INTRODUCTION

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 4

Introduction – Divide and Conquer
• Divide / Break
• Conquer / Solve
• Merge / Combine

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 5

Introduction – Divide and Conquer
• This technique can be divided into the following three parts:
• Divide: This involves dividing the problem into smaller sub-
problems.
• Conquer: Solve sub-problems by calling recursively until solved.
• Combine: Combine the sub-problems to get the final solution of the
whole problem.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 6

Introduction – Divide and Conquer
• The following are some standard algorithms that follow Divide and Conquer
algorithm.
• Quicksort is a sorting algorithm. The algorithm picks a pivot element and
rearranges the array elements so that all elements smaller than the picked pivot
element move to the left side of the pivot, and all greater elements move to the
right side. Finally, the algorithm recursively sorts the subarrays on the left and right
of the pivot element.
• Merge Sort is also a sorting algorithm. The algorithm divides the array into two
halves, recursively sorts them, and finally merges the two sorted halves.
• Closest Pair of Points The problem is to find the closest pair of points in a set of
points in the x-y plane.
• Strassen’s Algorithm is an efficient algorithm to multiply two matrices.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 7

Introduction – Divide and Conquer
•

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 8

Introduction – Divide and Conquer
•

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 9

Introduction – Divide and Conquer
•

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 10

Introduction – Divide and Conquer
• The recurrence equation for the number of additions A(n) made by
the divide-and-conquer algorithm for the problem of computing the
sum of ‘n’ numbers a0,a1,……an-1, on input of size n=2k is
•

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 11

Introduction – Divide and Conquer
• Merge Sort
• It is an application of divide-and-conquer technique. It sorts the
given array A[0,…n-1] by dividing it into 2 halves,
A[0,..,[n/2]-1] and A[[n/2]….n-1].
• Sorting each of them recursively & then merging the 2 smaller
sorted arrays in to a single sorted one.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 12

Introduction – Divide and Conquer
•

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 13

Divide-and-Conquer
Divide-and-Conquer
• Example: Merge sort using divide and conquer strategy for the given numbers 8, 3, 2, 9, 7, 1,
5, 4.
Divide-and-Conquer
• Merge Sort – Analysis
• Then the recurrence relation for the number of key comparisons C (n) is,
C(n) = 2C (n / 2) + Cmerge (n) ; n > 1
C(n)=0
• In the worst case, neither of the 2 arrays becomes empty i.e.) smaller elements
may come from the alternating arrays.
Cmerge(n) = n-1 & so the recurrence is
Cworst(n) = 2Cworst (n / 2) + n – 1; n > 1
Cworst(1) = 0
• Hence, according to the master theorem, Cworst (n) ε (n log n).
Divide-and-Conquer
• Merge Sort – Analysis
• Disadvantage:
• Requires linear amount of extra storage.
• Algorithm is complicated.
• Has larger multiplicative constant.
Divide-and-Conquer
• Quick Sort
• It divides according to their value and not based on the position.
• To achieve a partition in an array A[0,...., n-1], the algorithm finds an
element at position ‘s’, such that all the elements before that position
‘s’ are smaller than (or) equal to A[s] and all elements after position
‘s’ are greater than or equal to A[s] .
Divide-and-Conquer
• Quick Sort
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Divide-and-Conquer
Binary search
Binary Search
• Example: Find the search element, k = 70 in the given sorted array
of 13 elements.
Binary Search
Binary Search
• Analysis
Multiplication of Large Integers
Multiplication of Large Integers
Multiplication of Large Integers
• Multiplying 2-n digit numbers ‘a’ &’b’, where ‘n’ is a positive even number.
Multiplication of Large Integers
Multiplication of Large Integers
• Analysis
• Since the multiplication of n-digit numbers, requires, 3 multiplication of n/2
digit numbers, the recurrence for the number of multiplications, M(n) will be
given as M(n)=3. M(n/2) for all n > 1, and M(1) = 1.
Multiplication of Large Integers
• Analysis
Strassen’s Matrix Multiplication
Strassen’s Matrix Multiplication
Finding Maximum and Minimum in an array
• Algorithm straightforward
Finding the maximum and minimum elements in a set of (n) elements

Algorithm straightforward (a, n, max, min)

Input: array (a) with (n) elements
Output: max: max value, min: min value
max = min = a(1)
for i = 2 to n do
begin
if (a(i)>max) then max=a(i)
if (a(i)<min) then min=a(i)
end
End

Complexity
best= average =worst= 2(n-1) comparisons
Closest- pair problem
Closest- pair problem
Closest- pair problem
Convex - Hull Problem
• Finding the smallest convex polygon, that contains ‘n’ given points in the plane.
This algorithm is also known as quick hull because; its operations are same as
quick sort.
Convex - Hull Problem
Convex - Hull Problem
• Quick hull algorithm
Convex - Hull Problem
• Quick hull algorithm
Convex - Hull Problem
• Algorithm’s geometric operations