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.
IMPORTANT! Read the Problem 4 and Problem 5 solutions from the bottom of the
lecture notes ver carefully!
Problem 0 (assessment: self_______ final_______)
A vertex is a "source" if there are no edges coming into it
from other vertices. Design an algorithm that takes a graph G
and returns the number of source vertices in the graph.
Problem 1 (assessment: self_______ final_______)
Analyze your algorithm's worst case running time in terms of n
(the number of vertices) and e (the number of edges), assuming
that the adjacency
matrix representation of G is used.
Problem 2 (assessment: self_______ final_______)
Analyze your algorithm's worst case running time in terms of n
(the number of vertices) and e (the number of edges), assuming
that the adjacency list representation of G is used.