Problem I. Asymptotic Growth Rates (20 points)

• Remember that your proof must be general to any functions f(n) and g(n) that are positive.
• Remember that your proof needs to be rigorous. It is not enough to provide the intuition underlying this property.
• Remember that you need to prove an "IF AND ONLY IF" result. In order to prove "a if and only if b", you must prove that "a implies b" and also that "b implies a".
• Hint: You can use the results proven in Quiz1, if you wish. If you do, state clearly what those results are and where in your proof below you use them.

Solutions:

f(n) is Θ(g(n)) 

if and only if f(n) is O(g(n)) and also f(n) is Ω(g(n)) by the definition of Θ

if and only if g(n) is Ω(f(n)) and also g(n) is O(f(n)) as proven in Quiz 1

if and only if g(n) is Θ(f(n)) by the definition of Θ.

Problem II. Asymptotic Growth Rates (10 points)

• g₁(n) = 2ⁿ

• g₂(n) = n^4/3

• g₃(n) = n(log n)³

• g₄(n) = n^{log n}

• g₅(n) = 2²ⁿ

• g₆(n) = 2ⁿ²

Solutions:

• g₃(n) = n(log n)³

• g₂(n) = n^4/3

• g₄(n) = n^{log n}

• g₁(n) = 2ⁿ

• g₆(n) = 2ⁿ²

• g₅(n) = 2²ⁿ

Problem III. Graph Algorithms (35 points)

Input: 
    - An undirected graph G = (V,E), where |V| = n and |E| = m.
      Let's assume that the graph G is connected.
    - A node s in V.
Output: None, but the DFS procedure traverses the nodes in G 
          in depth first order, starting with s.

DFS(G,s) {

 1.  For all nodes u in V { 
 2.    explored[u] := false
     }
 3.  Add s to the top of an empty stack K
 4.  While K is not empty {
 5.     Remove the top node of the stack K. Let's call that node u. 
 6.     If explored[u] == false then {
 7.         explored[u] := true
 8.         For each edge (u,v) incident to u {
 9.             add v to the top of the stack K
            }
        }
     }
   }

1. (20 points) Analyze the time complexity of the DFS algorithm above by calculating its big-O growth rate, ASSUMING THAT THE GRAPH G IS REPRESENTED USING ADJACENCY LISTS. For your analysis, show how much time each line of the algorithm will take each time it is executed and also how much time each line of the algorithm will take over all the iterations of the for and while loops. Give the tightest possible upper bound in your big-O analysis.

   Explain your answers.

   Solutions:

   	time taken for ONE iteration and why	time taken for ALL iterations and why
   1.	constant1 to increment the counter	n * constant1 as it iterates over all nodes in V.
   2.	constant2 to write on the array cell	n * constant2 as it iterates over all nodes in V.
   3.	constant3 to add s on top of the stack	constant3 as this line is executed only once.
   4.	constant4 to check if K is empty	constant4 * 2m since the while loop is repeated as many times as nodes are added to the stack. Since a node is added to the stack when an edge incident to the node is found, then the maximum number of nodes added is equal to the sum over all nodes u in V of the degree(u), which is 2m.
   5.	constant5 to remove the top node in K	constant5 * 2m since the while loop is repeated 2m times as explained above
   6.	constant6 to access explored[u]	constant6 * 2m since the while loop is repeated 2m times as explained above
   7.	constant7 to access explored[u]	constant7 * n since each node is changed from "unexplored" to "explored" exactly once. Note that since the graph is connected, then n ≤ m-1.
   8.	constant8 to advance the pointer over u's adjacency list	constant8 * 2m since the for loop is repeated degree(u) times for node u, for a total of 2m (= the sum over all nodes u in the graph of degree(u)) times.
   9.	constant9 to add a node to the top of K	constant9 * 2m since the maximum number of nodes added to the stack is 2m times as explained above

   Total complexity: O(n + m), that is linear in the size of the input graph.

2. (15 points) Now, ASSUME THAT THE GRAPH G IS REPRESENTED USING AN ADJACENCY MATRIX. State clearly what changes need to be made to your complexity analysis above. For the lines of your analysis that remain unchanged (both in terms of the complexity and the explanation), JUST WRITE "SAME" IN THE CORRESPONDING LINES BELOW. Give the tightest possible upper bound in your big-O analysis for this new representation.

   Explain your answer.

   Solutions:

   	time taken for ONE iteration and why	time taken for ALL iterations and why
   1.	same	same
   2.	same	same
   3.	same	same
   4.	same	same
   5.	same	same
   6.	same	same
   7.	same	same
   8.	constant8 to increment the counter over the row u of the adjacency matrix	constant8 * n * n since one full row of the adjacency matrix (length n) must be explored in order to determine which nodes are adjacent to u, and this is repeated for each of the n nodes in the graph (since each node is converted from "unexplored" to "explored" at some point during the execution of the algorithm).
   9.	same	same

   Total complexity: O(n + m + (n*n)) = O(n²), since m ≤ n*n.

Problem IV. Graph Algorithms (35 points)

• (a) a topological ordering of G, thus establishing that G is a DAG; or
• (b) the word "cycle" if there is a cycle in G, thus establishing that G is not a DAG.
  (8 extra points: if you output an actual cycle in G instead of just the word "cycle").

1. (20 points) Provide your detailed algorithm here:

   
   Solution:
   
   In this solutions, we'll use the following data structures and variables:
   
   - An array IncomingEdges of size n, such that
     IncomingEdges[v] = # of incoming edges into node v 
     at a given point during the execution.
   
   - A linked list Orphans containing the list of nodes with
     zero incoming edges at a given point during the execution.
   
   - An array OrderedNodes of size n, such that
     OrderedNodes[i] = the ith node in the topological ordering.
   
   - A counter i to access the OrderedNodes array
     This counter will also be used to determine whether all n nodes have
     been added to the OrderedNodes at the end of the algorithm (if so, 
     then there is a topological ordering of G) or not (hence, G has a
     cycle).
   
   Algorithm:
   
   ModifiedTopologicalOrdering(G = (V,E) with n nodes and m edges) {
   
     For each node u in G {
        IncomingEdges[u] := 0
     }
     // The above for loop takes O(n) time //
   
     For each node v in G {
        For each edge (v,u) leaving from node v {
   	IncomingEdges[u] := IncomingEdges[u] + 1 
        }
     }
     // The above for loop takes O(m) time as the
      adjacency lists of all nodes are traversed for a total of
      2m = sum of degree(v) over all nodes v in G //
   
     Create an empty linked list Orphans
     // Creating an empty list takes O(1) time //
   
     For each v in G {
        If IncomingEdges[u] == 0 {
             Add u to the list of Orphans nodes
                 // This addition can be done in O(1) time by inserting u first in the list//
        }
     }
     // The above for loop takes O(n) time //
   
     i := 0 // This assignment takes constant (i.e., O(1)) time //
   
     While Orphans is not empty {
   	 // This loop will be repeated at most n times //
   
        Let w be the first node in the Orphans list 
   	 // This line takes O(1) time, for a total of O(n) time over all the loop iterations //
        Remove w from the Orphans list  
   	 // This line takes O(1) time, for a total of O(n) time over all the loop iterations //
        i := i + 1  
   	 // This line takes O(1) time, for a total of O(n) time over all the loop iterations //
        OrderedNodes[i] := w  
   	 // This line takes O(1) time, for a total of O(n) time over all the loop iterations //
   
        For each edge (w,u) leaving from node w {
   	IncomingEdges[u] := IncomingEdges[u] - 1
   	If IncomingEdges[u] == 0 {
              Add u to the list of Orphans nodes
                 // This addition can be done in O(1) time by inserting u first in the list//
           }
        }
          // The above for loop takes O(m) time over all executions of the 
            while loop as, in the worst case, the adjacency lists of all nodes are traversed 
            for a total of 2m = sum of degree(v) over all nodes v in G //
   
        Remove w from graph G (that is, assign "nil" to the adjacency list of w)
   	 // This line takes O(1) time, for a total of O(n) time over all the loop iterations //
     }  
   
     If i = n then { // This line takes O(1) time //
         // this means that all nodes in G were added to the topological ordering //
          return OrderedNodes
   	 // This line takes O(1) time //
     } else { // This line takes O(1) time //
         // this means that all remaining nodes in G have at least one incoming edge, and
            so as proven in Fact 3.19 (p. 102), G contains a cycle involving the nodes still
            remaining in G //
   
          return "cycle"
   	 // This line takes O(1) time //
   
         // For the extra credit you can run 
   	 the algorithm given in the solutions of Exercise 2 (Chapter 3) in Homework 3 
   	 using the current graph G (after the node removals done above to the original graph); 
   	 or simply you can realize that there are still n-i remaining nodes in G, and hence if you 
   	 follow any path of length (n-i) it will for sure contain a cycle, as proven in the textbook 
            in Fact 3.19 (p. 102).  // 
   	 // This takes O(m + n) time as shown in Homework 3//
     }
      
   }
   
   

2. (15 points) Prove in detail that your algorithm runs in O(n + m), as required.

   
   Solutions:
   
   A detailed complexity analysis of each part of the algorithm was provided together
   with the algorithm above.
   
   The total time complexity of the algorithm is then O(n + m).