Reference no: EM131058743
1. Describe how we might use DFS to locate vertices in a graph who are not connected to any other vertex in the graph.
2. Suppose we use DFS on a binary search tree, starting with the root. The edge to a left child is always traversed before an edge to a right child. In what order are the vertices visited? In what order are the vertices finished?
3. An undirected graph contains a "cycle" (i.e., loop) if there are two different simple paths by which we can get from one vertex to another. Using breadth-first search (not DFS), how can we tell if an undirected graph contains a cycle?
4. Let ???? = ????1????2···???????? and ???? = ????1????2···???????? be two strings over the alphabet Σ={????,????,????,????}. A longest common subsequence (LCS) of X and Y can be found by dynamic programming. To compute ????[????; ????], where 1≤????≤???? and 1≤????≤????, how many table entries are examined in the worst case?
5. Calculate the minimum number of multiplications necessary to find the matrix product ABCDE.
The dimensions of each of the matrices are listed below:
Matrix Dimensions
A 2x4
B 4x3
C 3x2
D 2x5
E 5x1
A 2 dimensional grid is provided below.
|
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
|
|
|
|
|
B
|
X
|
0
|
|
|
|
|
C
|
X
|
X
|
0
|
|
|
|
D
|
X
|
X
|
X
|
0
|
|
|
E
|
X
|
X
|
X
|
X
|
0
|
6. A directed graph G has four vertices, A, B, C, and D and the adjacency matrix below:
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
7
|
-1
|
4
|
|
B
|
3
|
0
|
5
|
∞
|
|
C
|
∞
|
4
|
0
|
∞
|
|
D
|
∞
|
1
|
∞
|
0
|
Show the updates to the shortest path estimates when allowing just vertex A as an intermediate vertex in
Floyd-Warshall's algorithm. The non-trivial values have been left for you to fill in.
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
7
|
-1
|
4
|
|
B
|
3
|
0
|
|
|
|
C
|
∞
|
|
0
|
|
|
D
|
∞
|
|
|
0
|
|
Angular momentum with respect
: A pitcher throws a ball past a stationary batter. If the ball has no spin and is thrown straight, then will the ball has no angular momentum with respect to the batter?
|
|
Forces of equal magnitude and opposite direction
: If two ends of a rope are pulled with forces of equal magnitude and opposite direction does the tension at the center of the rope must be zero? Explain?
|
|
Kinds of casual searches wikipedia
: Most people have heard of Wikipedia and many have used it at some point for casual research. Refresh your knowledge of how Wikipedia works and provide a brief description in your posting.
|
|
System comprising the water and the iceberg
: A 3100-kg iceberg at 0 °C falls into the ocean at a location where the water temperature is 2 °C, and all the ice melts by absorbing thermal energy from the water. For ice, the specific transformation energy for melting is 334 kJ/kg. What is the e..
|
|
How we might use dfs to locate vertices in a graph
: Describe how we might use DFS to locate vertices in a graph who are not connected to any other vertex in the graph.
|
|
Base did the diver hit the water
: A diver running 2.5 m/s dives out horizontally from the edge of a vertical cliff and 3.0 s later reaches the water below. How high was the cliff and how far from its base did the diver hit the water?
|
|
Identify symptoms of stress experienced by law enforcement
: Identify the symptoms of stress experienced by law enforcement personnel and explain how the symptoms of stress experienced by law enforcement personnel impact their work.
|
|
Acceleration all have the same sign
: During simple harmonic motion, is there a time at which the position, velocity, and acceleration all have the same sign (+,-, or 0)? Explain?
|
|
For natural science guru discussion 4
: Leaf through some popular magazine articles, examining introductory paragraphs until you find one that appeals to you. Describe it briefly.
|