Teaching Kids Programming – Divide and Conquer Algorithm Explained (Max Number, Ruler Marker)

Teaching Kids Programming: Videos on Data Structures and Algorithms

We have used the Divide and Conquer algorithm to solve some problems earlier. For example, for Hanoi Tower, we solve the problem by dividing into three steps: moving n-1 disks from A to B, moving disk-n to C, and moving n-1 disks from B to C. The first and third steps are carried on recursively.

Also, the merge sort algorithm is a good example of divide and conquer. We divide the elements in two halves, recursively merge-sort them and then we can merge two sorted list into a sorted array.

Advantages of Divide and Conquer – why we use it?

For big problems, it might be easier to solve a smaller problems by divide-and-conquer. Also, the sub problems are independent and they can be solved separately at the same time – which means we can use multithreading/parallelism to speed the performance.

Divide and Conquer to Get the Maxmium

Consider the following linear version – go through elements one by one and keep the maximum:

1
2
3
4
5
6

def max(nums):
    ans = -math.inf
    for i in nums:
        if i > ans:
            ans = i
    return ans

def max(nums):
    ans = -math.inf
    for i in nums:
        if i > ans:
            ans = i
    return ans

Time complexity obviously O(N) and space complexity O(1).

We can divide the numbers into two halves and obtain the sub-max for both halves, then return the max of them. As we divide and recursively solve the sub problems, we need to tell computers how to handle the base case which is only one element – then it is the max.

1
2
3
4
5
6
7

def max(nums):
    if len(nums) == 0:
        return nums[0]
    mid = len(nums) // 2
    leftMax = max(nums[:mid])
    rightMax = max(nums[mid:])
    return leftMax if leftMax > rightMax else rightMax

def max(nums):
    if len(nums) == 0:
        return nums[0]
    mid = len(nums) // 2
    leftMax = max(nums[:mid])
    rightMax = max(nums[mid:])
    return leftMax if leftMax > rightMax else rightMax

Divide and Conquer Strategy to Mark a Ruler

We can mark a ruler with 3 steps (divide and conquer) – first mark the center with height h, then second step is to mark the left with height-1 and finally mark the right with height-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def ruler(l, r, h):
    mid = l + r >> 1
    if h > 0:
        ruler(l, mid, h - 1)
        print("Mark %d with height = %d" % (mid, h))
        ruler(mid, r, h - 1)
    
ruler(0, 8, 3)
# Mark 1 with height = 1
# Mark 2 with height = 2
# Mark 3 with height = 1
# Mark 4 with height = 3
# Mark 5 with height = 1
# Mark 6 with height = 2
# Mark 7 with height = 1

def ruler(l, r, h):
    mid = l + r >> 1
    if h > 0:
        ruler(l, mid, h - 1)
        print("Mark %d with height = %d" % (mid, h))
        ruler(mid, r, h - 1)
    
ruler(0, 8, 3)
# Mark 1 with height = 1
# Mark 2 with height = 2
# Mark 3 with height = 1
# Mark 4 with height = 3
# Mark 5 with height = 1
# Mark 6 with height = 2
# Mark 7 with height = 1

–EOF (The Ultimate Computing & Technology Blog) —