Table of Contents

Week 4

Readings

Chapter 3: Graphs

3.5: Connectivity in Directed Graphs

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 versa1).

3.6: Directed Acyclic Graphs and Topological Ordering

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.

Corrections

Problem Set 2

Problem 1

  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

Problem 2

(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.

Problem Set 3

Problem 2

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.

1)
The types of graphs where we consider how strongly connected it is are typically undirected graphs.