Dynamic Programming

Introduction

Dynamic programming is closely related to divide & conquer and has far-ranging applications. They share the same idea of dividing a bigger and complicated question into smaller and easy-to-solve sub-problems of the same type. So both of them are based on recursion.

The difference: In divide & conquer, sub-problems share the same type with the original problem, but every sub-problem is not totally the same. (For example, when doing merge sort, we split the input array into left-half and right-half and sort them individually. The subproblem, sorting the left-half and right-half array, is the same with the original problem; the only difference is that the input array’s length becomes halved. But sorting the left-half and sorting the right-half is not usually the same problem.) In dynamic programming, we will have exactly the same sub-problem occur multiple times. To avoid solving the same sub-problem more than once, we can memorize each sub-problem result, and before solving one, we check if the same problem has been solved before. Thus every distinct sub-problem will be solved at most once.

To solve a problem using a dynamic programming approach, we normally need a 1-d, 2-d, or more complex array. We also have to figure out what’s the meaning of each block in that array and how later blocks connect to the previous one.

Comparing to divide & conquer, dynamic programming might have less time complexity but usually need more additional space because of memorization.

Fibonacci numbers

Computing the Fibonacci numbers is a classic and straightforward problem, where dynamic programming can be applied.

Referring to the wiki page, the nth Fibonacci number Fib(n) is the nth number in the Fibonacci series. Its definition:

and for n > 1:

The beginning of Fibonacci series:

Our problem is to compute the nth Fibonacci number:

Computing nth Fibonacci number
input: a integer N>=0
output: the N th Fibonacci number

Imagine we’d like to compute Fib(5). By definition, Fib(5) = Fib(4) + Fib(3) and the problem becomes computing Fib(4) and Fib(3). We can continue doing this until getting Fib(0) and Fib(1):

                           fib(5)   
                     /                \
               fib(4)                  fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)       fib(2)     fib(1)
       /     \       /    \        /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
 /      \
fib(1) fib(0)

The native method to compute this will be computing all nodes on the above graph, a simple divide & conquer algorithm. In this case, the number of node we need to compute is O(2^logn).

However, you might notice that some sub-problem is exactly the same. For example, Fib(3) appears 2 times, Fib(2) appears 3 times and Fib(1) appears 5 times. If we can memorize distinct nodes with their result, we only need to compute O(n) nodes. Also notice that the extra space needed here is also O(n).

                           fib(5)   
                     /                \
               fib(4)                  fib(3)   
             /        \            
         fib(3)      fib(2)       
       /     \          
  fib(2)   fib(1)   
 /      \
fib(1) fib(0)

The pseudocode of Fib(n):

Algorithm computing nth Fibonacci number

int Fib(n) {
  int fibSeries[] <-- initializing an array of size n + 2 
  fibSeries[0] = 0
  fibSeries[1] = 1
  for i from 2 to n+1
    fibSeries[i] = fibSeries[i - 1] + fibSeries[i - 2]
  return fibSeries[n+1]
}

One technique often used in dynamic programming is building a 1-d, 2-d, or more complex array to store the result of every distinct sub-problem; arrange the sub-problems in order from simpler to complicated, and solve them(fill the array) in that order.

Longest Increasing Subsequence

Longest Increasing Subsequence
input: an array of integer
output: the longest increasing subsequence

Subsequences: From a sequence, any of the element but in sequence.

For example, consider sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

The longest increasing subsequence is 0, 2, 6, 9, 11, 15

Usually, a useful technique to help us think about dynamic programming problems is considering the last element.

Here, we can fix the last element in the sequence, 15, and we have two choices: either 15 is in our longest increasing subsequence, or it is not. If we decide to exclude 15, the question becomes to find the longest increasing subsequence from remaining elements. If we include 15, since it is the last element, the question becomes to find the longest increasing subsequence from remaining elements with the last element less than 15. So fixing one end (the last of subsequence) seems to work.

Let P(n): the longest increasing subsequence of array arr[1...n] end with arr[n]
P(n) = max(P(1), ..., P(i-1)) + arr[n], for all  1<=i<=n-1 and arr[i] < arr[n]
LIS(arr[1...n]) = max(P(1), ..., P(n))

*LIS stands for the longest increasing subsequence

Now, it looks similar to Fibonacci number since the later value depends on previous ones: to compute P(2), we need P(1), to compute P(3), we need P(2) and P(1), to compute P(n), we need P(1), …, P(n-1). Since the same subproblem raises over and over again, memorization is a plus.

So we will have an array p[1…n] where p[i] stores the LIS end with arr[i]. Since the later value depends on earlier values, we can fill the array from the beginning.

Algorithm find LIS
int LIS(arr[1...n]) {
  p[1...n] <-- initialize empty array
  p[1] = 1 // base case
  for i from 2 to n
    p[i] = max(p[j]) + 1 for j from 1 to i-1 and arr[j] < arr[i]
  return max(p) // return the largest element in p[1...n]
}

We are using two loops here, so the time complexity will be O(n^2). Also, O(n) space is used to store array p[1…n].

Have fun!

Divide & Conquer

Introduction

Divide and conquer is a basic but powerful technique that is widely used in many algorithms. As you might speculate from its name, the principle of divide and conquer is to recursively divide a complicated problem into a few simple sub-problems of the same type (divide), until they become simple enough and we can solve them quickly (conquer); finally we will combine the sub-result to get the final result. Thus, we’ll usually use recursion when we want to use the divide and conquer algorithm.

Merge Sort Algorithm

Merge Sort is a classic divide and conquer algorithm; let’s look at its program specification:

Algorithm: merge sort
input: an array arr[] of comparable element
output: sorted version of the input array, ascending

In merge sort, we’ll apply the divide and conquer idea. Divide: we’ll recursively divide the array into two-parts until we can not divide anymore. At this time, all sub-arrays contains only one element; therefore, they can be considered as sorted array. Conquer: now, the question becomes how to merge two sorted arrays (left-half and right-half) into a single sorted array; this is easy and can be done with O(n) time. To make it clear, we can have another function called merge:

Algorithm: merge
input: two sorted array arr1[], arr2[] of comparable element
output: one sorted array, ascending 

And we can write the pseudocode for merge sort:

arr[] mergesort(arr[]) {
  if (the length of arr[] is 1)
    return arr[]
  left[] <-- copy the left half of arr[]
  right[] <-- copy the right half of arr[]
  left[] = mergesort(left[])
  right[] = mergesort(right[])
  return merge(left[], right[])
}

Here is an concrete example from GeeksforGeeks with every step shown in order, assuming our input array is [38, 27, 43, 3, 9, 82,10]:

Algorithm analyze

Time Complexity: Let n be the number of element in our input array. Since we are recursively dividing the array into two-part, the height of the tree will be 2log(n). Consider every level before merging (the upper log(n) levels), all we do is splitting the current array into left-half and right-half, which can be done with O(n) time. Consider every level after merging (the lower log(n) levels), what we do is merging two sorted arrays, this can be done with two pointers within O(n) time. To sum all these up, the total time complexity is O(n*logn)

Space Complexity: we will need O(n) extra space to store the left-half and right-half sub-arrays we created at any time. If we also want to consider the space used by recursive calls, we need to add extra O(logn) space for the stack frames. Thus, the total space complexity is O(n) +O(logn)

Conclusion

Similar to merge sort, other classic algorithms like binary search, quick sort, closest pairs in 2-d space also use the idea of divide & conquer algorithm. Two things need to be noticed here: 1. the subproblems are easier to solve than the current problem; in other words, dividing need to reduce the difficulty of the problem. 2. The subproblems need to be in the same format so that they can be solved similarly and efficiently, which will be time-saving.

Interestingly, what if the same subproblem occurs multiple times during division? In that case, another algorithm, dynamic programming, similar to divide & conquer, can be applied. We’d like to remember the state/result of the subproblem and only solve the same subproblem once instead of multiple times.

Have fun!

Introduction to Algorithm

In computer science, an algorithm is a sequence of well-defined instructions to solve a problem, usually within a finite amount of time and space. And it is an essential and indispensable part of computer science, theoretically and practically.

Here’s a rough schedule of what will be discussed in this topic:

  • Basic Graph Algorithms
    • Breadth-first search & Depth-first search
    • Dijkstra’s shortest path
    • Floyd-Warshall algorithm
    • Prim’s algorithm
  • Divide & Conquer
    • Merge Sort
  • Dynamic Programming
    • Longest Increasing Subsequence
    • Knapsack
    • Travelling Salesman Problem
  • Greedy
  • Network Flow
  • NP Optimization

Program Correctness

What is a program? A program, the implementation of an algorithm, is a sequence of instructions that are used to solve a problem or do some calculations. It always comes with specifications, including input and output. The process of getting output from the input is considered as a program.

Before getting started, we will discuss some basics of an algorithm: program correctness, a method helps us to verify if an algorithm is correct or not.

Program correctness sometimes has been split into two parts: soundness and termination.

  • Soundness: on every valid input, if program terminates, then its output is correct.
  • Termination: on every valid input, the program terminates.

This is important as we will frequently use it to determine if our algorithm is correct. One technique that is helpful to prove program correctness is mathematical induction. If you are interested, here are more examples provided by Cornell.

Remember, algorithm can be intriguing and fun to exploit! Good luck and have fun!


Credit

Some material in this topic is selected from the coursework of CS577: Introduction to Algorithm and ICPC training material written by Prof. Van Melkebeek @ University of Wisconsin-Madison.