Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Below is a super-brief reminder of the two main data structures used to represent graphs: the adjacency list and the adjacency matrix. If this doesn't ring a bell, go review your data structures notes. This was definitely a thing! We have two basic flavors of graphs: directed and undirected.

In a directed graph, edges have a direction, which is indicated by arrows.
In an undirected graph, edges have no direction, meaning you can traverse the edge in either direction.

So an adjacency matrix is a 2D array. An adjacency list is an array $A$ of size $n$, where the vertices are numbered $0,\ldots ,n-1$, such that $A[i]$ is an unordered list of the children of vertex $i$, for directed graphs, or the neighbors of vertex $i$ in the undirected case.
Note: For adjacency lists, you can choose to keep the children/neighbors in something other than an unordered list (e.g. a sorted array, a balanced binary tree, a hash table, ...), but you would have to be very clear that you were doing such a thing. The default expectation is that when someone says "adjacency list", the children/neighbors are in an unsorted list.

Problem 0 (assessment: self_______ final_______)

Consider the algorithm checkTrail below, which takes a graph $G$ and an array $L$ of vertices, and checks whether going through the vertices of $L$ in order is a "trail", meaning that there is a valid edge for each consecutive pair of vertices. 
checkTrail(G,n,L,k)
------------------
Input:  G, a directed graph G on n vertices {0,1,...,n-1}, and
        L, an array 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), false otherwise

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 1 (assessment: self_______ final_______)

Analyze the worst-case running time $T_w(n,k)$ of checkTrail assuming the graph is represented as a adjacency list. 
checkTrail(G,n,L,k)
------------------
Input:  G, a directed graph G on n vertices {0,1,...,n-1}, and
        L, an array 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), false otherwise

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 2 (assessment: self_______ final_______)

Analyze the worst-case running time $T_w(n,k)$ of checkTrail assuming the graph is represented as a adjacency matrix. 
checkTrail(G,n,L,k)
------------------
Input:  G, a directed graph G on n vertices {0,1,...,n-1}, and
        L, an array 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), false otherwise

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 (assessment: self_______ final_______)

Suppose in Problem 1 your adjacency list actually stored the children in a sorted array. How could this improve checkTrail? What would the worst-case running time be?