Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:garrett:entries:week_4 [2012/02/01 16:36] – created garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_4 [2012/02/15 05:06] (current) – garrettheath4
@@ Line 1: / Line 1: @@
 ====== Week 4 ======
+===== Readings =====
 ==== Chapter 3: Graphs ====
 === 3.5: Connectivity in Directed Graphs ===
@@ Line 9: / Line 10: @@
 === 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~~