1. What condition must be true for Dijkstra\'s shortest path algorithm to be suc

Question

1. What condition must be true for Dijkstra's shortest path algorithm to be successful?

2. what condition must be true to perform a topological sort of a directed graph?

3. What condition must be true for every vertex except the source and sink for a graph to represent a valid flow?

4. Concatenate your first and last name and turncate the result to 7 characters. Draw the finite automaton that will match a string for your name.

5. When we examined amortized analysis of the dynamic table insertion algorithm (when ever the table becomes full, it is reallocated at twice its current size ), we allocated a constant cost of 3 for each insert (regardless of whether the table needed to be expanded or not). Please explain why 3 and how each unit of the cost was allocated to the various operations.

6. Find the optimal Huffman code for the following set of frequencies:

a: 49 b: 14 c: 30 d: 27 e: 23 f: 15 g: 32

Show the final tree and encode the string "abadeafe".

Explanation / Answer

Multiple Questions : ANswering 1st 3.

1. The edge weights must be non-negative.

2. A topological ordering is possible if and only if the graph has no directed cycles.

3. In order for the assignment of flows to be valid, we must have the sum of flow coming into a vertex equal to the flow coming out of a vertex, for each vertex in the graph except the source and the sink

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.