Reading

Unit 5 Notes Sections 1.1,1.2.

Quiz questions

• P1 from Week 08 quiz questions (take home, to be done before Class 13)
• P2 from Week 08 quiz questions (take home, to be done before Class 18)

Problem 1

Here's an adjacency list describing a graph. Draw it. Here's an adjacency matrix describing a graph. Draw it. Note: The two diagrams were given in class.

Problem 2

Analyse the worst-case running time for the following algorithm, once assuming the adjacency list representation, once assuming the adjacency matrix representation

checkTrail(G,n,L,k)
------------------
Input:  directed graph G on n vertices {0,1,...,n-1}, array L of k vertices
Output: true if L is a "trail", i.e. in going from each vertex to the
        next in L, we only follow valid edges.

check = true, i = 1, curr = L[0]
while i < k and check
  next = L[i]
  check = check if there's an edge from curr to next
  curr = next
  i = i + 1
return check        

Problem 3

Suppose that we store the neighbors list in the adjacency list representation as a sorted array. What would your analysis look like for the previous algorithm in this variant of the adjacency list?

Problem 4

modify checkTrail to make it "checkPath", where we also require that no vertex is visited more than once. Analyze your modified algorithm (once again in both representations).

Problem 5

Let's describe the input size of G more precisely: it has n vertices and e edges. Do a worst-case analysis of checkPath (for both representations) using all three paramters (n,e,k) as the input "size".

Problem 6

A vertex is a "source" if there are no edges coming into it from other vertices. Design an algorithm that takes a graph (n vertices and e edges) and determines all sources in the graph. Analyze your algorithm in both representations.

Problem 7

Consider the algorithm findCommon that takes a graph and an array L of k source vertices and determines whether there is a vertex that is a descendent of more than one of the given sources, returning such a vertex if one exists. Analyze the worst-case running time of this algorithm in terms of n (number of vertices) and e (number of edges) in both representations (i.e. adjacency list and matrix).