Week 4

As noted in section 3.1, undirected graphs are just a special case of directed graphs in that an undirected has a set of edges such that for every edge (u, v) there also exists an edge (v, u), making every edge effectively bidirectional.

When a graph is described as being strongly connected, that means that for every pair of nodes in the graph there is a path of edges connecting one to the other and vice versa¹⁾.

A directed acyclic graph is defined to be a directed graph in which no cycles occur. Such graphs typically have a large number of edges compared to the number of nodes. Every directed acyclic graph has a topological ordering in which edges from nodes earlier in the order always point to nodes that occur later in the ordering.

1. 2^((log n)^(1/2))
2. n^(4/3)
3. n*(log n)^3
4. n^(log n)
5. 2^n
6. 2^n^2
7. 2^2^n

(a) The algorithm is O(n^3) because up to n items in the original array (n) need to be summed for each row and column in the matrix (n^2).

(b) The running time of the algorithm is also Ω(n^3) because there are no shortcuts in the algorithm, each for loop runs to completion without skipping any indices as the algorithm progresses.

The algorithm is O(m+n) because each node and edge must be visited once. As the algorithm progresses, the nodes and edges are stored in memory and the algorithm reports a cycle if it comes across a node again.