3.
a. CLRS 22.1-1
- Each vertex of v is a list, so the cost will be Big O of each out degree of v. This is equal to O(|E| + |V|)
- This operation has the same time complexity as the previous one. O(|E| + |V|)
b. CLRS 22.1-8
- The expected lookup time (for hash tables in general) is O(1), and the worst case is O(V). But if you sort each list, (which would take nlogn time, but only once per list) one could use a search algorithm (like binary search) to reduce the worst case to O(log(n)). This can also slow down the expected lookup time.
4. CLRS 22.3-7
- NOTE: I used / modified the algorithms from CLRS
DFS.(G)
1 for each vertex u 2 G:V
2 u.color =WHITE
3 u.pi = NIL
4 time = 0
5 for each vertex u in G.V
6 if u.color = = WHITE
7 DFS-VISIT(G, u)
DFS-VISIT(G; u)
1 time = time +1 // white vertex u has just been discovered
2 u.d = time
3 u.color = GRAY
4 for each v in G.Adj[u] // explore edge .u; /
5 if v.color == WHITE
6 v.pi = u
7 DFS-VISIT(G, v)
8 time =time + 1
9 u.f = time
all we have to do is remove line 8 and just work with white and grey