## Topological Sort and Tasks Scheduling (Kahn’s algorithm)

Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex VU comes before V in the ordering.

Given a directed graph, find the topological ordering of its vertices.

Example 1:

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0

Example 2:

Input: Vertices=5, Edges=[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]
Output: Following are all valid topological sorts for the given graph:
1) 4, 2, 3, 0, 1
2) 4, 3, 2, 0, 1
3) 4, 3, 2, 1, 0
4) 4, 2, 3, 1, 0
5) 4, 2, 0, 3, 1

Here are a few fundamental concepts related to topological sort:

1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
3. So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in either a Breadth First Search (BFS) way using Kahn’s algorithm or Depth First Search (DFS). We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

[preserved_text 1fbfd1112ea81554cf8bd39aca16ff45 /]

#### Time Complexity

In step ‘d’, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity of the above algorithm will be O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.

#### Space Complexity

The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list.

# Tasks Scheduling

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

Example 1:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: true
Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish
before '2' can be scheduled. A possible scheduling of tasks is: [0, 1, 2]

Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
Output: false
Explanation: The tasks have cyclic dependency, therefore they cannot be scheduled.

As you can see, we can represent the task and its dependency as an edge in a directed graph. There’s a little change in the above code that need to be changed to solve this problem so I let this as an exercise for you. Instead of returning a list, you just need to return a boolean.

Another application of Topological Sort is to check if a directed graph contains a cycle.

## Understanding how to generate permutation in Java

Given a set of distinct numbers, find all of its permutations.

Permutation is defined as the re-arranging of the elements of the set. For example, {1, 2, 3} has the following six permutations:

1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 1, 2}
6. {3, 2, 1}

If a set has ‘n’ distinct elements it will have n! permutations.

Example 1:

Input: [1,3,5]
Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]

Let’s take the example-1 mentioned above to generate all the permutations. Following a BFS approach, we will consider one number at a time:

1. If the given set is empty then we have only an empty permutation set: []
2. Let’s add the first element (1), the permutations will be: [1]
3. Let’s add the second element (3), the permutations will be: [3,1], [1,3]
4. Let’s add the third element (5), the permutations will be: [5,3,1], [3,5,1], [3,1,5], [5,1,3], [1,5,3], [1,3,5]

Let’s analyze the permutations in the 3rd and 4th step. How can we generate permutations in the 4th step from the permutations of the 3rd step?

If we look closely, we will realize that when we add a new number (5), we take each permutation of the previous step and insert the new number in every position to generate the new permutations. For example, inserting ‘5’ in different positions of [3,1] will give us the following permutations:

1. Inserting ‘5’ before ‘3’: [5,3,1]
2. Inserting ‘5’ between ‘3’ and ‘1’: [3,5,1]
3. Inserting ‘5’ after ‘1’: [3,1,5]

Here is the visual representation of this algorithm:

Here’s the non-recursive version:

public static List<List> findPermutations(int[] nums) {
List<List> result = new ArrayList();
Queue<List> permutations = new LinkedList();
permutations.add(new ArrayList());
for (int currentNumber : nums) {
// we will take all existing permutations and add the current number to create new permutations
int n = permutations.size();
for (int i = 0; i < n; i++) {
List oldPermutation = permutations.poll();
// create a new permutation by adding the current number at every position
for (int j = 0; j <= oldPermutation.size(); j++) {
List newPermutation = new ArrayList(oldPermutation);
newPermutation.add(j, currentNumber);
if (newPermutation.size() == nums.length)
result.add(newPermutation);
else
permutations.add(newPermutation);
}
}
}
return result;
}

and its recursive version:

public static List<List> generatePermutations(int[] nums) {
List<List> result = new ArrayList();
generatePermutationsRecursive(nums, 0, new ArrayList(), result);
return result;
}

private static void generatePermutationsRecursive(int[] nums, int index, List currentPermutation,
List<List> result) {
if (index == nums.length) {
result.add(currentPermutation);
} else {
// create a new permutation by adding the current number at every position
for (int i = 0; i <= currentPermutation.size(); i++) {
List newPermutation = new ArrayList(currentPermutation);
newPermutation.add(i, nums[index]);
generatePermutationsRecursive(nums, index + 1, newPermutation, result);
}
}
}

## Knapsack: Top-down, Memoization & Bottom-up

### Introduction

Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack which has a capacity ‘C’. The goal is to get the maximum profit out of the items in the knapsack. Each item can only be selected once, as we don’t have multiple quantities of any item.

Let’s take the example of Merry, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack capacity: 5

Let’s try to put various combinations of fruits in the knapsack, such that their total weight is not more than 5:

Apple + Orange (total weight 5) => 9 profit
Apple + Banana (total weight 3) => 7 profit
Orange + Banana (total weight 4) => 8 profit
Banana + Melon (total weight 5) => 10 profit

This shows that Banana + Melon is the best combination as it gives us the maximum profit and the total weight does not exceed the capacity.

### Problem Statement

Given two integer arrays to represent weights and profits of ‘N’ items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number ‘C’. Each item can only be selected once, which means either we put an item in the knapsack or we skip it.

### Basic Solution

A basic brute-force solution could be to try all combinations of the given items (as we did above), allowing us to choose the one with maximum profit and a weight that doesn’t exceed ‘C’. To try all the combinations, our algorithm will look like:

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return knapsackRecursive(profits, weights, capacity, 0);
}

private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex >= profits.length)
return 0;

// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity - weights[currentIndex], currentIndex + 1);

// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

return Math.max(profit1, profit2);
}

Complexity:

For recursive function with two separate calls of itself, the time complexity is O(2​^n). Since recursive calls work the same way as DF search, space complexity is O(n).

### Top-down Dynamic Programming with Memoization

Memoization is when we store the results of all the previously solved sub-problems and return the results from memory if we encounter a problem that has already been solved.

Since we have two changing values (capacity and currentIndex) in our recursive function knapsackRecursive(), we can use a two-dimensional array to store the results of all the solved sub-problems. As mentioned above, we need to store results for every sub-array (i.e. for every possible index ‘i’) and for every possible capacity ‘c’.

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
Integer[][] dp = new Integer[profits.length][capacity + 1];
return knapsackRecursive(dp, profits, weights, capacity, 0);
}

private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
int currentIndex) {

// base checks
if (capacity <= 0 || currentIndex >= profits.length)
return 0;

// if we have already solved a similar problem, return the result from memory
if(dp[currentIndex][capacity] != null)
return dp[currentIndex][capacity];

// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
capacity - weights[currentIndex], currentIndex + 1);

// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);

dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}

#### Time and Space complexity

Since our memoization array dp[profits.length][capacity+1] stores the results for all subproblems, we can conclude that we will not have more than  N*C subproblems (where ‘N’ is the number of items and ‘C’ is the knapsack capacity). This means that our time complexity will be O(N*C).

The above algorithm will use O(N*C) space for the memoization array. Other than that we will use O(N) space for the recursion call-stack. So the total space complexity will be O(N*C + N), which is asymptotically equivalent to O(N*C)

### Bottom-up Dynamic Programming

Let’s try to populate our dp[][] array from the above solution by working in a bottom-up fashion. Essentially, we want to find the maximum profit for every sub-array and for every possible capacity. This means that dp[i][c] will represent the maximum knapsack profit for capacity ‘c’ calculated for the first ‘i’ items.

So, for each item at index ‘i’ (0 <= i < items.length) and capacity ‘c’ (0 <= c <= capacity), we have two options:

1. Exclude the item at index ‘i’. In this case, we will take whatever profit we get from the sub-array excluding this item => dp[i-1][c]
2. Include the item at index ‘i’ if its weight is not more than the capacity. In this case, we include its profit plus whatever profit we get from the remaining capacity and from previous items => profit[i] + dp[i-1][c-weight[i]]

Finally, our optimal solution will be maximum of the above two values:

dp[i][c] = max (dp[i-1][c], profit[i] + dp[i-1][c-weight[i]])
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
// basic checks
if (capacity &lt;= 0 || profits.length == 0 || weights.length != profits.length)
return 0;

int n = profits.length;
int[][] dp = new int[n][capacity + 1];

// populate the capacity=0 columns, with '0' capacity we have '0' profit
for(int i=0; i &lt; n; i++)
dp[i][0] = 0;

// if we have only one weight, we will take it if it is not more than the capacity
for(int c=0; c &lt;= capacity; c++) {
if(weights[0] &lt;= c)
dp[0][c] = profits[0];
}

// process all sub-arrays for all the capacities
for(int i=1; i &lt; n; i++) {
for(int c=1; c &lt;= capacity; c++) {
int profit1= 0, profit2 = 0;
// include the item, if it is not more than the capacity
if(weights[i] &lt;= c)
profit1 = profits[i] + dp[i-1][c-weights[i]];
// exclude the item
profit2 = dp[i-1][c];
// take maximum
dp[i][c] = Math.max(profit1, profit2);
}
}

// maximum profit will be at the bottom-right corner.
return dp[n-1][capacity];
}

#### Time and Space complexity

The above solution has the time and space complexity of O(N*C), where ‘N’ represents total items and ‘C’ is the maximum capacity.

## Folk/Join Framework & Merge Sort (Java)

We all know that Merge Sort is one of the fastest sorting algorithms out there (on average), it’s based on the divided & conquer technique. In today world of computing, computers usually have more than one CPU, and to take advantage of all of those resources, we need to implement Merge Sort in a way such that it will leverage all of those juicy CPUs.

Today I am going to show you how to implement Merge Sort using Java’s Folk/Join framework. However before we start, let’s get some information about Folk/Join framework in Java.

So what is Folk/Join framework?

This framework is based on the ForkJoinPool class in Java, which is a special kind of executor, two operations, the fork() and join() methods (and their different variants), and an internal algorithm named the work-stealing algorithm. What this algorithm does is to determine which tasks to be executed. When a task is waiting for the finalization of a child task using the join() method, the thread that is executing that task steal another task from the pool of tasks that are waiting and starts its execution. There are disadvantages though, for example, it wont work if the child task is doing some IO operations.

From Java 8 onward, with the introduction of the mighty Stream, behind the scene, it is implemented using Fork/Join framework.

if ( problem.size() > DEFAULT_SIZE) {
childTask1=new Task();
childTask2=new Task();
childTask1.fork();
childTask2.fork();
childTaskResults1=childTask1.join();
childTaskResults2=childTask2.join();
taskResults=makeResults(childTaskResults1, childTaskResults2);
return taskResults;
} else {
taskResults=solveBasicProblem();
return taskResults;
}

The above snippet is basically what it looks like. It’s very similar to your normal recursive function, we have a base case, in this case the data is small enough for us to calculate directly, otherwise we will split the data into two equal parts, and continue to process recursively on each part.

Similarly, the Merge Sort algorithm stops when the data need to be processed is small enough (usually just 1 element).

Here’s one of the way you can implement a normal Merge Sort.

public class SerialMergeSort {

public void mergeSort (Comparable data[], int start, int end) {
if (end-start > 1) {
int middle = (end + start) >>> 1;
mergeSort(data,start,middle);
mergeSort(data,middle,end);
merge(data,start,middle,end);
}
}

private void merge(Comparable[] data, int start, int middle, int end) {
int length=end-start;
Comparable[] tmp=new Comparable[length];

int i, j, index;
i=start;
j=middle;
index=0;

while ((i<middle) && (j<end)) {
if (data[i].compareTo(data[j])<=0) {
tmp[index]=data[i++];
} else {
tmp[index]=data[j++];
}
index++;
}

while (i<middle) {
tmp[index++]=data[i++];
}

while (j<end) {
tmp[index++]=data[j++];
}

for (index=0; index < length; index++) {
data[index+start]=tmp[index];
}
}
}

With Fork/Join framework, most of the time you will choose between RecursiveAction which does not return anything and RecursiveTask which is a generic abstract class which returns something when it’s done. With Merge Sort, we need to do an extract processing step when two child tasks are done (merge the sorted lists). In this case our class will extend CountedCompleter class. It has some important methods that we’re going to use.

• compute(): this is where the body of the Merge Sort algorithm is implemented.
• addToPendingCount(1): Increase the number of child tasks by 1 that need to be completed before onCompletion method can be executed.
• onCompletion(CountedComplete caller): this method will be called as soon as all of the child tasks are finished.
• tryComplete(): tell the parent task that one of its child tasks has been completed.

Here is the most important part in the compute() method:

@Override
public void compute() {
if (end - start >= 1024) {
middle = (end + start) >>> 1;
MergeSortTask task1 = new MergeSortTask(data, start, middle, this);
MergeSortTask task2 = new MergeSortTask(data, middle, end, this);
addToPendingCount(1);
task1.fork();
task2.fork();
} else {
new SerialMergeSort().mergeSort(data, start, end);
tryComplete();
}
}

Let’s explain the code snippet above.

As you can see, it’s very similar to the serial Merge Sort. We use theSerialMergeSort for the base case. Also we add the reference to the parent task in case we need it. tryComplete() internally will call onCompletion(), when onCompletion() is finished it will call tryComplete() over its parent to try to complete that task.

If the data is still too big (more than 1024 elements), we will split it into two child MergeSortTask, addToPendingCount(1) to register this as one of the child task of the parent task. Then we call fork() to asynchronously invoke task1 and task2.

Here’s the onCompletion() part that you’re looking for:

@Override
public void onCompletion(CountedCompleter caller) {

if (middle == 0) {
return;
}
int length = end - start ;
Comparable tmp[] = new Comparable[length];

int i, j, index;
i = start;
j = middle;
index = 0;

while ((i < middle) && (j < end)) {
if (data[i].compareTo(data[j]) <= 0) {
tmp[index] = data[i++];
} else {
tmp[index] = data[j++];
}
index++;
}

while (i < middle) {
tmp[index++] = data[i++];
}

while (j < end) {
tmp[index++] = data[j++];
}

for (index = 0; index < length; index++) {
data[index + start] = tmp[index];
}

}

It's the "merge" part of the SerialMergeSort.

You can download the full source code here.

It’s already too long for a daily blog post and I’m also not a fan of a blog that’s too long. After running benchmark locally on my local laptop (4 cores – 8 threads), the improvement in term of time is usually more than x2 on average.

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel