Let T be a binary tree. Write and analyze an algorithm that prints the contents of the tree level by level. That is, it should print the root (level 0) then all the elements at level 1 from left to right, then all the elements at level 2 from left to right, etc
You should write the algorithm in pseudocode, and you should analyze the runtime in terms of N, the number of nodes in the tree.
(Hint: This is actually a graph problem)
Recall that an articulation vertex is a vertex that, if removed from the graph, would cause the graph to become disconnected. Describe and analyze an algorithm that takes a simple, undirected graph G and a vertex v and determines if v is an articulation vertex or not. You do not have to write pseudocode. Think about algorithms that were discussed in class that might help solve this problem.
Recall that an articulation vertex is a vertex that, if removed from the graph, would cause the graph to become disconnected.
Determine if the following statement is true or false and justify your answer.
Every connected, undirected graph has at least one vertex that is NOT an articulation vertex.
Determine how many topological orderings each graph below has and justify your reasoning.
(a)
| 0 | |
| 1 | 0, 4 |
| 2 | 3, 4 |
| 3 | 0 |
| 4 | 0, 1 |
(b)
| 0 | |
| 1 | 0 |
| 2 | 3, 4 |
| 3 | 0 |
| 4 | 0, 1 |
(c) A graph with n vertices labeled where each of the vertices from 0, 1, 2, ..., n - 1 where each of the vertices from 1 to n - 1 have a single outgoing edge that points to vertex 0.
Let G be a simple, directed graph with positive edge weights. Let the same graph except G where each edge is increased by a constant value c > 0.
Let P be the shortest path from vertex s to vertex t in and let Q be the shortest path from G vertex s to vertex t in G'.
Determine if the following statement is true or false and justify your answer.
P and Q must be the same path (i.e. the same vertices in the same order) but with different weights.