Algorithms Test 3

Greedy algorithm

• It is a technique to solve the problem and goal is to make optimal solution.

Example of greedy approach:

• Minimum Spanning tree ( Prim’s and kruskal’s )
• Single source shortest path problem ( Dijkastra’s algorithm )
• Huffman code problem
• Fractional knapsack problem
• Job sequencing problem
• Max flow problem and many more problems can be solved using Greedy method.

Explanation:

0-1 knapsack problem cannot be solved by the greedy method because it is enabled to fill the knapsack to full capacity so here greedy algorithm is not optimal. 0-1 knapsack problem is solved by Dynamic programming approach.

Note:  

Fractional knapsack problem is different from 0-1 knapsack problem.

Use the divide and conquer paradigm. Compute medians of both the arrays and compare them. Consider m1 be the median of the f 1^st array a1[] and m2 be the median of the 2^nd array a2[].  

If m1 is greater than m2 then median may be present in subarray from the first element of a1[] to m1 or it may be present in subarray from m2 to last element of a2[].

If m2 is greater than m1 then median may be present in subarray from the first element of a2[] to m2 or it may be present in subarray from m1 to last element of a1[].

\( \left[ {\begin{array}{*{20}{c}} A&B\\ C&D \end{array}} \right] \left[ {\begin{array}{*{20}{c}} E&F\\ G&H \end{array}} \right]= \left[ {\begin{array}{*{20}{c}} I&J\\ K&L \end{array}} \right] \)

Therefore:

I = AE + BG

J = AF + BH

K = CE + DG

L = CF + DH

Will need 8 multiplications of subproblems of size n/2 each.

We also need to spend O(n²) time to add up these results. 

The Greedy algorithm for Job sequencing problem with deadline is as follows :

1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as first job in sorted jobs.
3) Do following for remaining n – 1 jobs
a) If the current job can fit in the current result sequence
          without missing the deadline, add current job to the result.
          Else ignore the current job.

Following the above algorithm :

Now we can add the task in the following order :

{T3}

{T9, T3}

{T7, T9, T3}

{T2, T7, T9, T3}

{T2, T7, T9, T5, T3}

{T2, T7, T9, T5, T3, T8}

{T2, T7, T9, T5, T3, T8, T1}

In the findDuplicate() function sorting is done to get the end result and hence it is the Greedy approach.

Important Point:

Since sorting algorithm is not mentioned it cannot be divide and conquer

Nothing is stored previously to calculate the result and hence not Dynamic Programming

Exhaustive search (Brute force)

int findDuplicate(int[ ] nums) {
        int length = nums.length;
        if(length == 0)
            return 0;
        for(int i=0; i<length-1; i++)
        {

         for(int j=i+1; j < length; j++)

              {
            if(nums[i] == nums[j])
                return nums[i];

             }
        }
        return 0;   
    }
}

Largest Sum Contiguous subarray is from index 3 to 13

Maximum subsequence sum = {11, -2, -3, 6, -1, -2, 1, 4, 5, -3, 4} = 20

Code in C++ to find the maximum contiguous sum of array

#include <iostream>

using namespace std;

int kadane(int arr[], int n)

{

int max_so_far = 0;

int max_ending = 0;

for (int i = 0; i < n; i++)

{

max_ending = max_ending + arr[i];

max_ending = max(max_ending, 0);

max_so_far = max(max_so_far, max_ending);

}

return max_so_far;

}

int main()

{

int arr[] = { −5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "largest sum of contiguous sub-array is " << kadane(arr, n);

return 0;

}

Important Point

There is no significance of Divide and Conquer note.

Data:

T₁ = 2048 sec = 2¹¹ sec

n₁ = 65536 = 2¹⁶

T₂ = 16 min = 16 × 60 sec

Formula:

Time complexity of merge sort is O(nlog₂n),

T = c × n × log₂n

where c is constant

Calculation:

T₁ = c × n₁ × log₂ n₁

2¹¹ = c × 2¹⁶ × log₂ 2¹⁶

1 = c × 2⁵ × 16

\(\therefore c = \frac{1}{{{2^9}}}\)

T₂ = c × n × log₂n

\(16 \times 60 = \frac{1}{{{2^9}}}\;{n_2}{\log _2}{n_2}\)

nLog₂n = 2⁹ × 2⁴ × 2² × 15

nLog₂n = 15 × 2¹⁵

Concept:

Fractional knapsack uses Greedy approach.

An item with maximum profit/weight is selected first

Explanation:

Profit = Item 1 + Item 3 + Item 4 + fraction part of 4

Profit = 90 + 60 + 42 + \(35 \times\frac{110}{50}\) = 269