LECTURE 2: DIVIDE &
CONQUER ALGORITHM
SUB-TOPIC BINARY SEARCH, MERGE SORT, QUICK SORT, STRASSEN'S
MATRIX, FINDING MAXIMUM AND MINIMUM
THE DEFECT COIN PROBLEM
DIVIDE AND CONQUER
• General Definition:
• A divide and conquer algorithm is a strategy for solving large problems by,
• 1. Breaking the problem into smaller sub-problems
• 2. Solving the sub-problems and
• 3. combining them to get the desired output
• To use the divide and conquer algorithm, recursion is used.
DAC ALGORITHM
BINARY SEARCH ALGORITHM
• Let a1 be list of elements that are in non-decreasing order
• It is a problem of determining whether a given element x is present in the list
and it is a quick and method
EXAMPLE OF BINARY SEARCH
EXAMPLE 2
5 7 9 13 32 33 44 54 56 88
MERGE SORT
MERGE SORT PROCEDURE
• Usually done recursively
• Divide and conquer
EXAMPLE
• The array is broken down into individual items
• Quick note, when this is implemented in code, the above steps will be done
in different order because of recursion
• To sort, we will examine the individual items, compare their value and merge
them into temporary arrays
CONTINUATION
FINAL OUTCOME
QUICK SORT
• Quick sort is recursive algorithm
• When you think of quick sort, the word pivot comes to bear
• Pivot is simply one of the items in the array that means the following three
conditions after we sorted it.
PIVOT CONDITIONS
• Correct position in final sorted array
• Items to the left are smaller
• Items to the right are larger
EXAMPLE
CONTINUATION
MORE ON QUICK SORT
• Since the left side of the array is sorted
• We can divide the array into sub arrays
• Recursion will handle the rest
HOW TO CHOOSE PIVOT ELEMENT
• Median of three- In this method we consider the first, middle and last
element of the array. (2+8+4)/3 = 4.6
