$1.$ Provide the adjacency matrix and adjacency list for the graph shown here:

$2.$ Suppose a graph $\backslash ($ G $\backslash )$ has adjacency list:

$\backslash [$

A L$=[[7],[2,4],[1,4],[6,7],[1,2,6,7],[],[3,4],[0,3,5]]$

$\backslash ]$

Draw a picture of $\backslash ($ G $\backslash )$ and write down its adjacency matrix.

$3.$ For a graph $\backslash ($ G $\backslash )$ with $\backslash ($ n $\backslash )$ vertices write the pseudocode for an algorithm which takes the adjacency matrix $\backslash ($ A M $\backslash )$ for $\backslash ($ G $\backslash )$ and produces the corresponding adjacency list $\backslash ($ A L $\backslash ).$ What is the $\backslash (\backslash$Theta$($n$)\backslash )$ time complexity of this? Assume it takes $\backslash (\backslash$Theta$(1)\backslash )$ time to allocate any fixed size list and array full of zeros.

$4.$ For a graph $\backslash ($ G $\backslash )$ with $\backslash ($ n $\backslash )$ vertices write the pseudocode for an algorithm which will takes the adjacency list $\backslash ($ A L $\backslash )$ for $\backslash ($ G $\backslash )$ and produce the corresponding adjacency matrix $\backslash ($ A M $\backslash ).$ What is the $\backslash (\backslash$Theta $\backslash )$ time complexity of this? Assume it takes $\backslash (\backslash$Theta$(1)\backslash )$ time to allocate any fixed size list and array full of zeros.

$5.$ Given the adjacency matrix $\backslash ($ A M $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a walk, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?

$6.$ Given the adjacency matrix $\backslash ($ A M $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a trail, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?

$7.$ Given the adjacency matrix $\backslash ($ A M $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a path, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?

$8.$ Given the adjacency list $\backslash ($ A L $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a walk, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?

$9.$ Given the adjacency list $\backslash ($ A L $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a trail, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?

$10.$ Given the adjacency list $\backslash ($ A L $\backslash )$ for a graph with $\backslash ($ n $\backslash )$ vertices and a list $\backslash ($ V $\backslash )$ of $\backslash ($ k $\backslash )$ vertices, write the pseudocode for an algorithm which would determine whether $\backslash ($ V $\backslash )$ specifies a path, returning either TRUE or FALSE. What is the best$-$ and worst$-$case $\backslash (\backslash$Theta $\backslash )$ time complexity for this?