Unit 5 Notes Sections 1.1,1.2.

## 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).