1 hour
Introduction video for DAGs and Topological Sort
This experiment requires you to have basic knowledge about:
And above all, a curiosity to learn and explore!
In this experiment, we will be able to do the following:
Module | Weightage | Expectation |
---|---|---|
Pre-test | 10% | Solve All Questions |
Topological Sort: DFS Algorithm | 20% | Understand the DFS algorithm |
Topological Sort: Kahn's Algorithm | 20% | Understand the Kahn's algorithm |
Analysis | 25% | Understand the time and space complexity |
Post-test | 25% | Solve all Questions |
10 minutes
A Depth First Search (DFS) is an algorithm for traversing a finite graph. DFS visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. A stack (often the program's call stack via recursion) is generally used when implementing the algorithm.
A Directed Acyclic Graph (DAG) is a graph that is directed and without cycles connecting the other edges. This means that it is impossible to traverse the entire graph starting at one edge. The edges of the directed graph only go one way.
Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
Q1. Which of these best describes a graph?
(A) A linear data structure with finite nodes and edges
(B) A non-linear data structure consisting of nodes and edges
(C) A data structure which has infinite nodes and edges
(D) All of the above
A Graph is a non-linear data structure consisting of a finite set of vertices(or nodes) and set of edges which connect a pair of nodes.
Q2. How many number of edges need to be present in a complete graph having n vertices?
(A) (n*(n-1))/2
(B) (n*(n+1))/2
(C) n
(D) None of these
Taking a general example such as inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array, when you will need to move n elements
Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
(A) X will always be a better choice for small inputs
(B) X will always be a better choice for large inputs
(C) Y will always be a better choice for small inputs
(D) X will always be a better choice for all inputs
Performance could be similar for small inputs, but definitely better for larger inputs
Q4. int i, j, k = 0;
for (i = n / 2; i <= n; i++){
for (j = 2; j <= n; j = j * 2){
k = k + n / 2; }
}
What is the time complexity for the above code?
(A) O(n)
(B) O(N + M) time, O(N + M) space
(C) O(N + M) time, O(1) space
(D) O(N * M) time, O(N + M) space
The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.
Q5. ans = 0;
for (i = n; i >= 1; i /= 2){
for (j = 1; j <=m ; j *=2 ){
ans += (i * j);
}
}
What is the time complexity for the above code?
(A) O(n*m)
(B) O(logmlogn)
(C) O(mlogn)
(D) O(nlogm)
The first for loop runs for logn times, each of the loop runs for logm. So total it runs for O(logmlogn) time.
15 min
Demo Video
In this module we will learn:
Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices v_{1},v_{2},...,v_{n} in such a way, that if there is an edge directed towards vertex v_{j} from vertex v _{i}, then v_{i} comes before v_{j}. There are multiple topological sortings possible for a graph. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).
Image for example of topological sort should be displayed here.
It is clear that a topological ordering is not possible if the graph has a cycle, since for two vertices v and w on the cycle, v precedes w and on contrary even w precedes v, so it is not meaningful to say which preceeds the other. So topological sorting can be achieved for only directed and acyclic graphs.
A DAG 'G' has at least one vertex with in-degree 0 and one vertex with out-degree 0.
Proof: A DAG does not contain a cycle which means that all paths will be of finite length. Now let S be the longest path from u(source) to v(destination). Since S is the longest path there can be with no incoming edge to u and no outgoing edge from v, if this situation had occurred then S would not have been the longest path => indegree(u) = 0 and outdegree(v) = 0
We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
Image showing Step-wise Representation of finding topological sort through DFS should be displayed here.
15 min
Demo Video
In this module we will learn about:
Steps involved in finding the topological ordering of a DAG:
Image showing Step-wise Representation of Kahn's Algorithm should be displayed here.
What is meant by indegree?
It is simply the count of number of edges pointed towards the vertex from other vertices.
How to find indegree?
Traverse the array of edges and simply increase the counter of the destination node by 1.
Algorithm:
for each node in Nodes
indegree[node] = 0;
for each edge(src,dest) in Edges
indegree[dest]++;
Demo Video
Requires Demo Artefact
Recquires Practice Artefact
Recquires Exercise Artefact
10 minutes
In this module, we will be learning about :
Time and Space complexity : We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.
Time complexity for Kahn's algorithm:
Lets assume that we are ordering a graph with V vertices and E edges using Topological Sort.
Time complexity for Topological sort through DFS:
Since it is modification of DFS, time complexity doesn't alter. Time complexity is O(|V|+|E|).
Space complexity for Kahn's Algorithm:
While enqueuing a node, we need some extra space to store temporary values. Other than that, the ordering can be done in-place. Hence space complexity is O(|V|).
Space complexity for Topological Sort through DFS:
Since we need to store the sequence of nodes into a stack, we need some extra space. Other than that, the ordering can be done in-place. Hence space complexity is O(|V|).
10 minutes
Post Test includes questions on concepts from the entire experiment. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.
Q1. Which of the following best describes the topological order?
(A) If a digraph has no directed cycle it does have a topological order otherwise it might or might not have a topological order
(B) If a digraph has at least one directed cycle it has no topological order otherwise it might or might not have a topological order
(C) A directed graph has a topological order if and only if it has no directed cycle
(D) None of these
As it is explained earlier. Please refer topological sort basic view.
Q2. Assume you use a digraph to schedule a set of tasks, that have precedence constraints. In such a graph, the tasks should be the ________________ and the constraints should be the ______________.
(A) vertices,bedges
(B) edges, vertices
(C) vertices, vertices
(D) edges, edges
It is obvious that tasks must be vertices and constraints must be edges, since in order to perform tasks, we need to complete constraints
Q3. Topological Sort is equivalent to which of the traversals in trees?
(A) Pre-order traversal
(B) Post-order traversal
(C) In-order traversal
(D) None of these
In pre-order traversal of trees, we process the root first and then the child from left to right.
Q4. Topological sort of a Directed Acyclic graph is ________.
(A) Always unique
(B) Always Not unique
(C) Sometimes unique and sometimes not unique
(D) None of these
As it is explained earlier. Please refer topological sort basic view.
Q5. Time Complexity of Topological Sorting is _______. (V – number of vertices, E – number of edges)
(A) O(|E|)
(B) O(|V|)
(C) O(|V| + |E|)
(D) None of these
O(|V|+|E|) as it is explained earlier. Please refer topological sort analysis.
You can explore more about Topological Sort Experiment through following resources: