Algorithm Design Techniques

Author: Harsha P Dixit


"Algorithms are to computer programs as recipes are to cooking"

The lecture on Algorithm Design Techniques was taken by Prof. Pradeesha Ashok, and covered the following -

Divide and Conquer

As the name suggests, divide and conquer method reduces a given problem into smaller problems recursively until they are small enough to be solved directly, and then appropriately combines the solution.

Example - Merge Sort. 

The two important tasks in Merge Sort are dividing the array into smaller units, and merging two sorted units into a larger sorted array. It divides the array into smaller units recursively until only one element is in each unit (single element is trivially sorted), and then merges the sorted smaller units into larger sorted array.
For example - consider an array [4 5 1 2 7 8] which needs to be sorted.
Dividing and merging step by step:

1. [4 5 1]    [2 7 3]
2. [4 5]    [1]     [2 7]    [3]
3. [4]    [5]    [1]    [2]    [7]    [3]
4. [4 5]    [1]    [2 7]    [3]
5. [1 4 5]    [2 3 7] 
6. [1 2 3 4 5 7]

Time complexity of Merge Sort is O(nlogn)

Greedy

Greedy algorithms arrive at the final solution by making the best possible choice at every step. Since they cant back-track, it is critical that they make the correct choice in every step. Greedy algorithms can be applied only if the global optimal solution for the problem is obtained by choosing the local optimal solution for every sub problem. Generally, if applicable, greedy algorithms are more efficient than other techniques.
This is how a greedy algorithms work -

1. Select greedy choice
2. Convert problem into subproblem of smaller size
3. Repeat

Example - Fractional Knapsack problem

Assume you are carrying food for everyone in a picnic. Your bag can only carry 4 KG, and you have to choose between three food items, Pizza (2 KG), Tacos(2 KG) and Cake (3 KG) which give 100, 10 and 120 KCal of energy respectively. Since you want everyone to have sufficient nutrition, you want to maximise the amount of calories you carry, while not exceeding 4 KG. You can carry a fraction of items too.

Greedy approach to solve this is by first calculating Calories per KG, and making the greedy choice at every step. 

Calories per KG: Pizza: 100/2 = 50 (How I wish this was true in real life!) , Tacos: 10/2 = 5 and Cake: 120/3 = 40.

The most greedy choice is to first load up on Pizza, and then as much Cake as possible. So, the greedy solution is to carry 2KG of Pizza and 2 KG of cake, totalling 180 KCal.

Greedy approach may not work for every problem. For instance, it fails for 0-1 Knapsack problem - which can be solved by Dynamic Programming.

Dynamic Programming

Like divide and conquer, Dynamic programming also divides the given problem into smaller subproblems, solves them, stores the results and then combines the solutions. However, this method is only useful when the following conditions are satisfied:

• Overlapping Subproblems : This method is useful when overlapping subproblems exist as it avoids solving the same problems again by storing the results.
• Optimal Substructure : A given problem has Optimal Substructure if the optimal solution to it can be obtained using optimal solutions to its subproblems. 

When to use Dynamic Programming -

• Small number of sub problems
• When solution to larger problem obtained by solving smaller ones
• When natural ordering exists

Dynamic programming algorithm design-

• Identify subproblem
• Define Recurrence
• Implement in bottom up manner 

Example: Maximum Independent Set in a path

Consider a vertex weighted path consisting of n vertices. The goal is to obtain a set of vertices which are not adjacent to one another and whose sum of weights is maximum.

Let G be the graph with n vertices - G(v_1, v_2, ..... , v_n), with w_i representing the weight of i-th vertex.

Let MIS(i) be the value of Maximum Independent Set of vertices {v_1, v_2 ... v_i}. (this is the subproblem)

We know that if v_i is in not in the solution :

MIS(i) = MIS(i-1)

If v_i is in the solution:

MIS(i) = w_i + MIS(i-2) (because v_(i-1) can't be in solution if v_i is there)

If we try to solve this by recursion (top down approach), it takes exponential time to run as subproblems are solved multiple times (because of overlapping subproblems). However, if we store the solutions to sub problems, we can obtain linear running time.

The algorithm to solve this -

MIS(1) = w_1

MIS(2) = maximum(w_1,w_2)

for i=3 to n:

   MIS(i) = maximum(w_i+MIS(i-2), MIS(i-2))