====== 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 versa((The types of graphs where we consider how strongly connected it is are typically undirected graphs.)).

=== 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 ===
  - <nowiki>2^((log n)^(1/2))</nowiki>
  - n^(4/3)
  - n*(log n)^3
  - n^(log n)
  - 2^n
  - 2^n^2
  - 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.



~~DISCUSSION~~