Introduction to Divide and Conquer

Learning Objectives

At the end of this sub-unit, students should

know the basic of abstraction, decomposition, and integration.
know how to integrate using sequencing and nesting.
appreciate wishful thinking.

How to Build a Robot

Consider building a toy robot from a bag of components. How we typically do this? If our first instinct is to randomly grab components and try to assemble them, then we are going to have a hard time. Instead, we are going to look at the subcomponents that we need (e.g., the body) and focus our attention there. We may even further focus on the specific component of the body.

Once we focus our attention to this specific component, we can then search for the component we need. Then we assemble them into a body. Afterwards, we focus our attention to other components like the hands and the legs. Once we finish building them separately, we can combine them into a fully functioning robot. We can also express these as a form of instructions.

By making the steps into instructions, we have actually split the problem or task into smaller problem called subtask. We can tie this back to the context of programming in general where to solve a problem, we need to think in terms of smaller subproblems.

The idea of thinking in terms of tasks and subtasks is the basis of abstraction. This high-level thinking is made useful with the function abstraction. We will describe some terminologies to make the concept more concrete and easier to remember.

Terminologies

We will use the idea of making a robot to discuss the terminology. Some of these terminologies may have different meanings depending on the context. Naming is one of the hardest problem in computer science. The definition we use is intended to capture the main properties of the terminology but is still restricted to the limitation of written language.

Abstraction

The idea of an abstraction to think in terms of high-level operations (i.e., high-level abstractions). In particular, we should not care about the implementation details. Instead, we think in terms of the operations and/or procedures we can perform.

We can abstract the process of making a robot into the following operations.

Build the head of the robot.
Build the main body of the robot.
Build the left hand of the robot.
Build the right hand of the robot.
Build both feet of the robot.

Terminology01

Decomposition

A decomposition is tied to an abstraction. Once we have a suitable abstraction, we solve the smaller problem. The act of splitting a part into smaller parts (e.g., a problem into smaller subproblems_) and building the smaller part is what we call as decomposition.

In the context of building the robot, we can build the main body (i.e., subtask 2 above) by following the instruction to make the main robot body. This can entail a subproblem of building the torso or the chest.

Terminology02

Integration

Integration is the reverse of decomposition that is also often called as composition. After we decompose a problem into smaller subproblems and solve the subproblems, we obtain a collection of solutions for the smaller subproblems. The remaining problem is to combine the solutions to the smaller subproblems to solve the original problem. We say that we are integrating the solution.

After we build the five components, we need to combine them by joining the components together.

Terminology03

Solving Problem via Divide and Conquer

To solve problems using this idea of divide and conquer, we need to know the different ways we can perform abstraction, decomposition, and integration. In the case of abstraction and decomposition, it will depend on the past problems we have solved, so this hopefully motivates you to solve more problems. As for integration, there are two main ways integration can be done.

There may be more, but the two we are going to explain are the main ones. In fact, these two are not exactly new as we have implicitly used them before. They are sequencing and nesting. In this part, we will explain the solution in this framework of abstraction, decomposition, and integration.

Sequencing

Sequencing is the simplest form of decomposition and integration. The idea is to perform task one after another.

Do subtask 1, then
Do subtask 2, then
Do subtask 3, then
\(\vdots\)

There may be more than 3 subtasks, as many as the problem needs. We solve each subtask separately to obtain some solution. Here, subtask 2 may use the solution of subtask 1 and subtask 3 may use the solution of both subtask 1 and 2. In general, subtask \(n\) may use the solution of subtask \(n - 1\) up to subtask 1.

This is one form of integration. Alternatively, the integration can be done at the end after all the subtasks are completed. We will illustrate both kinds with two problems.

Rising Factorials

Problem Description

Before defining rising factorials of half integers, we need to first explain the idea of a double factorial. The double factorial of \(n\) --denoted \(n!!\)-- is not \((n!)!\) (i.e., factorial of factorial of \(n\)). Instead, it is defined as follows.

\[ n!! = \begin{cases} n \times (n - 2) \times (n - 4) \times \cdots \times 4 \times 2, & \text{if } n \text{ is even} \\ n \times (n - 2) \times (n - 4) \times \cdots \times 3 \times 1, & \text{if } n \text{ is odd} \end{cases} \]

The rising factorials of \(x\) is denoted by \(x^{(n)}\). We define the rising factorial of a half integer as follows.

\[ {\displaystyle \left[\frac{2m + 1}{2}\right]^{(n)} = \frac{(2(n + m) - 1)!!}{2^n((2m - 1)!!)}} \]

Task

Write the function half_rising(m, n) to compute and return the value of \(\left[\frac{2m + 1}{2}\right]^{(n)}\).

Assumptions

m and n are positive integers (i.e., m > 0 and n > 0).

To solve this problem via divide and conquer, we need to describe in a high-level abstraction. In particular, we need in terms of subproblems. One potential subproblem is the computation of double factorial. Thinking this way, we can then describe the problem of computing the rising factorial of a half integer as follows.

Compute \((2(n + m) - 1)!!\) and let the result be \(k\).
Compute \(((2m - 1)!!)\) and let the result be \(d\).
The result is \(\frac{k}{2^n d}\).

With some thinking, we can see that both \(2(n + m) - 1\) and \(2m - 1\) are always an odd number. So we do not check if the case for the double factorial is even or odd. As a good practice, we can first write the structure as a comment on our code. Then we fill in the code appropriately.

CommentSubproblem #1Subproblem #2Remaining ProblemCombining All

def half_rising(m, n):
  # Compute k

  # Compute d

  # Remaining: k / (2^n d)
  ​

def half_rising(m, n):
  # Compute k
  k, i, limit = 1, 1, 2 * (n + m) - 1
  while i <= limit:
    k = k * i
    i = i + 2
  # Compute d




  # Remaining: k / (2^n d)
  ​

def half_rising(m, n):
  # Compute k




  # Compute d
  d, i, limit = 1, 1, 2 * m - 1
  while i <= limit:
    d = d * i
    i = i + 2
  # Remaining: k / (2^n d)
  ​

def half_rising(m, n):
  # Compute k

  # Compute d

  # Remaining: k / (2^n d)
  return k // ((2 ** n) * d)

def half_rising(m, n):
  # Compute k
  k, i, limit = 1, 1, 2 * (n + m) - 1
  while i <= limit:
    k = k * i
    i = i + 2
  # Compute d
  d, i, limit = 1, 1, 2 * m - 1
  while i <= limit:
    d = d * i
    i = i + 2
  # Remaining: k / (2^n d)
  return k // ((2 ** n) * d)

As we can see, this solution only integrates the result at the end of both subtasks. In the next example, we will show an integration step that is done in between.

Narcissistic Number

Problem Description

A narcissistic number is a \(k\)-digit number that is the sum of the \(k\)^th powers of its digits. For instance, \(153\) is a narcissistic number.

\[ 153 = 1^3 + 5^3 + 3^3 \]

Task

Write the function is_narcissistic(n) to check if the given number n is a narcissistic number. If it is, return True. Otherwise, return False.

Assumptions

n is a positive integer (i.e., n > 0).

With high-level abstraction, we can solve the following smaller subproblems.

Find the number of digits in \(n\) and let the result be \(k\).
Find the sum of \(k\)^th power of the digits of \(n\) and let the result be \(s\).
Check if \(s\) is equal to \(n\).

Again, by writing the comments first, we can solve it in the following way. Notice how we use the result of subproblem #1 to solve subproblem #2.

CommentSubproblem #1Subproblem #2Remaining ProblemCombining All

def is_narcissistic(n):
  # Count digit k

  # Compute sum of k-th power of digit

  # Remaining: s == n
  ​

def is_narcissistic(n):
  # Count digit k
  k, m = 0, n  # copy n to m to keep the old value
  while m > 0:
    k = k + 1
    m = m // 10
  # Compute sum of k-th power of digit




  # Remaining: s == n
  ​

def is_narcissistic(n):
  # Count digit k




  # Compute sum of k-th power of digit
  s, m = 0, n  # copy n to m to keep old value
  while m > 0:
    s = s + ((m % 10) ** k)
    m = m // 10
  # Remaining: s == n
  ​

def is_narcissistic(n):
  # Count digit k

  # Compute sum of k-th power of digit

  # Remaining: s == n
  return s == m

def is_narcissistic(n):
  # Count digit k
  k, m = 0, n  # copy n to m to keep the old value
  while m > 0:
    k = k + 1
    m = m // 10
  # Compute sum of k-th power of digit
  s, m = 0, n  # copy n to m to keep old value
  while m > 0:
    s = s + ((m % 10) ** k)
    m = m // 10
  # Remaining: s == n
  return s == m

Nesting

Another form of decomposition and integration is nesting. The idea is to perform a task (e.g., subtask 1) while performing another task (e.g., subtask 2). So subtask 2 is nested inside subtask 1. We say that subtask 2 is the inner subtask and subtask 1 is the outer subtask.

Do subtask 1
- Do subtask 2
  - Do subtask 3
    - \(\vdots\)

Similar to sequencing, there may be more than 3 subtasks. There are more ways we can integrate the result. For instance, subtask 3 can use the value from subtask 2 and 1. Then, at the end of subtask 3, we return to subtask 2 which may use the result from subtask 3.

Unique Prime Divisor

Problem Description

A number \(p\) is a prime number if there is no number between 2 and \(p\) - 1 that can fully divide \(p\). Given a number \(n\), find the sum of all unique prime divisor of \(n\). A number \(k\) is a prime divisor of \(n\) if \(k\) is a prime number and \(k\) fully divides \(n\).

Task

Write the function sum_prime_divisor(n) to compute the sum of unique prime divisor of n.

Assumptions

n is a positive integer greater than 1 (i.e., n > 1).

In this case, we cannot decompose and integrate using sequencing because the check if a number is prime has to be done for each potential divisor. So we divide the problem as nesting instead.

Enumerate the number \(k\) between 2 and \(n\) - 1.
- Check if \(k\) is prime.
  - If \(k\) is prime and is a divisor of \(n\), add to the sum \(s\).

CommentSubproblem #1Subproblem #2Remaining ProblemCombining All

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]

    # Check if k is prime -> is_prime

    # is_prime <- check if k is prime

  # result is s
  ​

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]

  k = 2
  while k < n:
    # Check if k is prime -> is_prime

    # is_prime <- check if k is prime

    k = k + 1
  # result is s
  ​

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]



    # Check if k is prime -> is_prime
    is_prime = True
    d = 2
    while d < k:
      if k % d == 0:
        is_prime = False
        break
    # is_prime <- check if k is prime



  # result is s
  ​

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]
  s = 0

    # Check if k is prime -> is_prime

    # is_prime <- check if k is prime
    if is_prime and n % k == 0:
      s = s + k

  # result is s
  return s

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]
  s = 0
  k = 2
  while k < n:
    # Check if k is prime -> is_prime
    is_prime = True
    d = 2
    while d < k:
      if k % d == 0:
        is_prime = False
        break
    # is_prime <- check if k is prime
    if is_prime and n % k == 0:
      s = s + k
    k = k + 1
  # result is s
  return s

Wishful Thinking

The idea of abstraction, decomposition, and integration can be improved with the use of function. In particular, some subproblems may be delegated into functions. Take for instance the rising factorial problems. We can first write the function double factorial.

Double Factorial

def double_factorial(n):
  if n % 2 == 0:
    i = 2
  else:
    i = 1
  res = 1
  while i <= n:
    res = res * i
    i = i + 2
  return res

Then we can rewrite half_rising(m, n) as follows.

Rising Factorial

def half_rising(m, n):
  # Compute k
  k = double_factorial(2 * (n + m) - 1)
  # Compute d
  d = double_factorial(2 * m - 1)
  # Remaining: k / (2^n d)
  return k // ((2 ** n) * d)

Similarly, for the unique prime divisor problem, we can first wish for the function to check if a number is prime or not. Let us assume that there is such a function named is_prime(n). Once we have written this function, we can then solve the unique prime divisor problem as follows.

Unique Prime Divisor

def sum_prime_divisor(n):
  # Enumerate k in range of [2, n-1]
  s, k = 0, 2
  while k < n:
    if is_prime(k) and n % k == 0:
      s = s + k
    k = k + 1
  return s

Introduction to Divide and Conquer

How to Build a Robot

Terminologies

Abstraction

Decomposition

Integration

Solving Problem via Divide and Conquer

Sequencing

Rising Factorials

Narcissistic Number

Nesting

Unique Prime Divisor

Other Problems

Wishful Thinking