## Reading

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