Exercise 1

a) During a run of dfs-based topological sort we find a grey node G. This means that:
    G will be finished before the node we are currently processing, and therefore behind the node in the sorted sequence.
    G will be finished after the node we are currently processing, and therefore in front of the node in the sorted sequence.
    The graph cannot be topologically sorted.

b) Prim's and Kruskal's algorithms are greedy because:
    They have a very low runtime
    They choose what seems best at the time
    They use constant memory

c) What is the lowest runtime for finding the number of connected components in a connected directed graph?
    O(1)
    O(lg n)
    O(n)
    O(E+V)

d) What is the lowest runtime for finding the number of connected components in a connected undirected graph?
    O(1)
    O(lg n)
    O(n)
    O(E+V)

e) What is the lowest runtime for finding the number of connected components in a connected DAG?
    O(1)
    O(lg n)
    O(n)
    O(E+V)



Exercise 2


The above matrix represents a directed graph. An X means an edge exists between the two indices.

Visit the nodes in alphabetical order.

a) Which node will be in the middle of the topologically sorted sequence from Topological-Sort(G)?
    A
    C
    D
    F

b) What does DFS[G] do if we add the following line between lines 6 and 7 (look in the text book):
	i=1+i
    Counts the number of cycles in the graph
    Counts the number of nodes
    Counts the number of trees in the depth-first forest
    Counts the number of forward edges in the graph



Exercise 3

a) How many "strongly connected components" are there in the graph?
    5
    6
    7
    8
    9
    10



Exercise 4

The figure above is a graph, with a minimum spanning tree marked with
thick edges.

The questions use definitions from Cormen chap. 23.

a) Which of the following statements is correct?
	The sets {a,e,d,b} and {h,i,g,c} represents a cut of the graph
	This graph has exactly one minimum spanning tree
	If X = {(a,b), (a,d), (a,e)}, then (b,h) is a safe edge for X
	None of the above statements are correct

b) MAYBE-MST will find a minimum spanning tree if...
	line 2 is changed to "for each edge e, taken in non-decreasing order"
	line 3 is changed to "do if T U {e} has no cycles and is connected"
	both line 2 and 3 are changed as in the statements above
	it is left unchanged, the algorithm already finds a minimum spanning tree

c) The following graph is given in adjacency list form, where each element in the
   lists is of the form (b,w), where b is the endpoint of the edge and w the weight
   of the edge. In this list the undirected graph has been represented by
   including each edge in both directions.

a : (b,14), (e,7), (h,1)
b : (a,14), (e,2), (f,20)
c : (e,3), (g,6), (h,8)
d : (e,13), (f,15), (g,11)
e : (a,7), (b,2), (c,3), (d,13), (f,21)
f : (b,20), (d,15), (e,21)
g : (c,6), (d,11), (h,10)
h : (a,1), (c,8), (g,10)

This graph has...
	exactly one minimum spanning tree
	more than one minimum spanning tree



Exercise 5

Use the above figure to answer the questions. If you during Prim's or Kruskal's algorithm are presented
with the choice between two or more edges of equal weight, you should choose the one
connecting nodes of the lowest lexical values.

a) The minimum spanning tree for this graph is given by which edges?
	(a,f),(d,f),(b,d),(g,d),(b,c),(c,e),(c,h),(h,j),(i,j)
	(b,e),(c,e),(c,h),(h,j),(i,j),(b,d),(a,d),(a,f),(h,g)
	(a,f),(a,d),(a,b),(c,b),(c,e),(c,h),(h,g),(h,j),(i,j)
	(i,j),(h,j),(c,h),(c,e),(c,b),(a,f),(a,d),(b,d),(d,g)

b) If you use Prim's algorithm starting in node j, (d,b) is chosen as edge number?
	5
	6
	7
	8
	9

c) If you use Kruskal's algorithm, which edge is added after (a,d)?
	(b,e)
	(b,c)
	(i,j)
	(d,g)
	(h,j)



Exercise 6

In this task we look at the problem of finding a minimum spanning tree in a directed graph.
The problem then becomes to, for a given root-node, finding a subset of the edges,
such that by following the edges from the given node, we can reach all the other nodes in the graph.
The sum of these edges must also be minimal.

a) For a spanning tree to exist, all nodes(except the root) must have an incoming edge.
    True
    False


b) For a spanning tree to exist, all nodes must have an outgoing edge.
    True
    False

c) If we for each node choose the cheapest incoming edge(except for the root-node), and we have found a minimum spanning tree.
    True
    False

d) If we for each node choose the cheapest outgoing edge, and we have a tree, we have found a minimum spanning tree.
    True
    False

e) The following algorithm solves the problem:
    Prim's
    Kruskal's
    Topological sort
    Prim's and Kruskal's
    None of the above