Introduction To

Algorithms
Lecture 4 – Divide and Conquer

2nd Year, 2nd Semester – Musa Hodman

Winter, 2024
Contents
 Divide and Conquer – History
 Divide and Conquer – Problem Solving
 Divide and Conquer - Definition
 Recursion
 Characteristics of Recursive Functions
 The Nature of Recursion
 Recursion Illustration
 Recursive multiplication
 Fibonacci Series

 …

Musa Hodman 2
Divide and Conquer – History
 Divide and rule policy or divide and
conquer, is gaining and maintaining
power divisively.

 Historically, this strategy was used in

many different ways by empires
seeking to expand their territories.

 The divide your enemy so you can

reign approach is attributed to Julius
Cesar — he successfully applied it to
conquer Gaul twenty-two centuries
ago. (Gallic Wars 50-58 BC)
Musa Hodman 3
Divide and Conquer – Problem Solving

Musa Hodman 4
Divide: Break into non-overlapping
subproblems of the same type

Musa Hodman 5
Divide: Break into non-overlapping
subproblems of the same type

Musa Hodman 6
Divide: Break into non-overlapping
subproblems of the same type

Musa Hodman 7
Divide: Break into non-overlapping
subproblems of the same type

Musa Hodman 8
Musa Hodman 9
Musa Hodman 10
Musa Hodman 11
Musa Hodman 12
Musa Hodman 13
Musa Hodman 14
Musa Hodman 15
Musa Hodman 16
Musa Hodman 17
Musa Hodman 18
Musa Hodman 19
Musa Hodman 20
Musa Hodman 21
Musa Hodman 22
Musa Hodman 23
1. Break into non-overlapping
subproblems of the same type.

2. Solve subproblems

3. Combine Results

Musa Hodman 24
Divide and Conquer – Definition

 One of the most common techniques in computer

science is known as “divide and conquer”

 This technique represents a strategy of dividing a

complex problem into smaller ones to solve them.

 Math problems are broken down into smaller/simpler

problems.

Musa Hodman 25
Divide and conquer
 Recall that in divide and conquer, we solve a problem
recursively, applying three steps at each level of the
recursion.
 Divide the problem into a number of subproblems that are
smaller instances of the same problem.
 Conquer the subproblems by solving them recursively. If the
subproblem sizes are small enough, however, just solve the
subproblems in straightforward manner.
 Combine the solutions to the subproblems into the solution
for the original problem.
Musa Hodman 26
Divide and Conquer

Musa Hodman 27
Recursion

 We have seen that repetition can be achieved by

writing loops, such as for and while loops.

 Another way to achieve repetition is through

recursion, which occurs when a function calls itself.

 Recursion applies the divide and conquer strategy.

Musa Hodman 28
Recursion
 The word Recursion actually comes from a Latin word meaning "a
running back".
 This makes sense because recursion is the process of actually
"going of”, breaking down a problem into small pieces and then
bringing the solutions to those smaller pieces back together to
form the complete solution.
 Some points to remember:
 Recursion breaks down a complex problem into smaller sub-
problems
 Subproblems are smaller instances of the same type of problem.
Musa Hodman 29
The Nature of Recursion

 The recursive algorithms that we write will generally

consist of an if statement with the form shown below:

Musa Hodman 30
Recursion Illustration

 Lets assume that for a particular problem of size N,

we can split this problem into one involving a
problem of size 1.
 Which can solve (a stopping case), and a problem of
size N-1, which we can split further.
 If we split the problem N times, we will end up with
N problems of size 1, all of which we can solve.
Musa Hodman 31
Recursion illustration

Musa Hodman 32
Recursive Multiplication

 Consider how we might solve the problem of multiplying

6 by 3.
 Assuming that we know the addition tables but not the
multiplication tables.
 The problem of multiplying 6 by 3 can be split into the
two problems:
1. Problem 1: Multiply 6 by 2
2. Problem 2: Add 6 to the result of problem 1.
Musa Hodman 33
Recursive Multiplication
 Because we know the addition tables, we can split problem 1
into two problems 1.1 and 1.2, leaving us three problems to
solve, two of which are additions.
1. Problem 1: multiply 6 by 2
1.1 multiply 6 by 1
1.2 add 6 to result
2. Problem 2: Add 6 to the result of problem 1
 Even though we don’t know the multiplication tables, we are
familiar with the simple rule that, for any M, M*1 is M.
 By solving problem 1.1 (the answer is 6) and problem 1.2
 We get the solution to problem 1 (the answer is 12). Solving
problem 2 gives us the final answer 18.
Musa Hodman 34
Recursive Multiplication Implementation

Musa Hodman 35
Fibonacci Series
0,1,1,2,3,5,8,13,…
 Begins with 0 and 1 and has the property that each
subsequent Fibonacci number is the sum of the previous two.
 This series occurs in nature and describes a form of spiral.
 The Fibonacci series may be defined recursively as follows:
 Fibonacci(0) = 0, Fibonacci(1) = 1
 Fibonacci(n) = Fibonacci (n-1) + Fibonacci (n-2_
 There are two base cases for the Fibonacci calculation:
 Fibonacci(0) is defined to be 0,
 Fibonacci(1) is defined to be 1.
Musa Hodman 36
Fibonacci Series
 Set of recursive calls for Fibonacci(3)

Musa Hodman 37
Recursive Algorithm
 A recursive algorithm is one that solves a problem by
solving one or more smaller instances of the same problem.
 To implement recursive algorithm, we use recursive
methods – a recursive method is one that calls itself.
 A recursive problem is consists of three parts:
 Recursive Algorithm: algorithm that finds the solution to given
problem by reducing the problem to smaller versions of itself.
 Recursive Method: Method that calls itself.
 Base Case: case in recursive definition in which the solution is
obtained directly or stops the recursion.
Musa Hodman 38
Recurrences and Running Time
 An equation or inequality that describes a function in
term of its value on smaller inputs.
 T(n) = T(n-1) + n
 Recurrences arise when an algorithm contains recursive
calls to itself.
 What is the actual running time of the algorithm?
 Need to solve the recurrence
 Find an explicit formula of the expression.
 Bound the recurrence by an expression that involves n.
Musa Hodman 39
Maximum Subarray Problem
 Given an array we have to find the sub-array whose sum is
maximum among all sub-arrays.
 Finding such array refers to the maximum sub-array or the
MSS.
 The Original array can have positive and negative
numbers.

Musa Hodman 40
Finding Sub-array
 A sub-array is a continues part of the given array.
 We consider the sub-array to have at least one element.

 Consider the following Array and find MSS

Musa Hodman 41
Brute-Force Algorithm
 Find all possible sub arrays
 Find their sum
 Find the maximum sum among all sum
 Sub-arrays should be form with the size 1,2,… to the end
of original array
 For example we have the following array.

Musa Hodman 42
Example
 We start sub-arrays with the size one.

 We define a variable answer to store each

MSS and compare it with the previous ans.

Musa Hodman 43
Cont.
 Then we move to the array with size two.

 We define a variable answer to store each

MSS and computer it the previous

Musa Hodman 44
Cont.
 Finally we form the array with the size four.

Musa Hodman 45
Divide and Conquer Technique
 Now we want to use divide and conquer strategy to find
maximum sub-array sum or MSS
 Let’s go back to our previous example divide the array by
two with the left half and right half.

Musa Hodman 46
Decimal Conversion

 You enter integer data in decimal form, and the computer

converts these decimal numbers to binary form for use
within a program.
 Do you know how decimal integers are converted to
binary numbers?
 The algorithm for this conversion will be shown in the
next slide.

Musa Hodman 47
Decimal Conversion

 Take the decimal number and divide it by 2.

 Make the reminder the rightmost digit in the answer.
 Replace the original dividend with the quotient.
 Repeat, placing each new remainder to the left of the
previous one.
 Stop when the quotient is 0.

Musa Hodman 48
Decimal Conversion
 The answer is the sequence of remainders from last to
first. Therefore, decimal number 42 is 101010 in binary.

Musa Hodman 49
Decimal Conversion Implementation

Musa Hodman 50
Decimal Conversion Implementation

Lets do a code walk-through of convert(10)

Musa Hodman 51
Tower of Hanoi
 When the game begins, all the circles are on the first peg in order
by size, with the smallest on the top.
 The object of the game is to move the circles, one at a time, to the
third peg.
 The catch is that a circle cannot be placed on top of one that is
smaller in diameter.
 We can use the middle peg as an auxiliary peg, but it must be
empty at the beginning and end of the game.

Musa Hodman 52
Towers of Hanoi

Musa Hodman 53
Printing values in an Array

Musa Hodman 54
Questions

Musa Hodman 55
THANK YOU
[email protected]