CISC320

Can you run the following algorithms on a given input?
• Kruskal’s algorithm
• Prim’s algorithm
• Cycle-breaking algorithm

These are graph algorithms used to find the minimum spanning tree. Kruskal's algorithm focuses on edges and runs efficiently with a disjoint set data structure, while Prim's algorithm grows the spanning tree by selecting the minimum weight edge from a subset of vertices. The cycle-breaking algorithm is used to ensure acyclic behavior when constructing trees.

What are the definitions of the followings?
• Cut optimality condition
• Path optimality condition
• Cut property
• Cycle property

These are principles used in optimization and graph theory. The cut optimality condition states that any minimum spanning tree can be formed by selecting the lightest edge across any cut, while the path optimality condition indicates that any subpath of a minimum path is also optimal. The cut property ensures that any minimum spanning tree contains the smallest edge crossing a cut, and the cycle property states that for any cycle in a graph, at least one edge must be part of the minimum spanning tree.

Can you prove that the followings are optimality conditions on graphs with distinct
weights?
• Cut property
• Cycle property

The cut property states that the minimum spanning tree contains the smallest edge crossing any cut in the graph, while the cycle property asserts that for any cycle, at least one edge must be included in the minimum spanning tree. Both properties hold true when the graph has distinct edge weights.

Can you give algorithms for the following problems?
• Activity selection
• Optimal code

• Greedy algorithm for activity selection
• Huffman coding algorithm

What is the maximum flow problem?
• What are valid flows?

The maximum flow problem seeks to find the greatest possible flow in a flow network from a source node to a sink node, subject to capacity constraints on the edges. Valid flows adhere to the capacity limits and conservation of flow at each node except for the source and sink.

Can you run the Ford-Fulkerson algorithm on a given input?

The Ford-Fulkerson algorithm is used to compute the maximum flow in a flow network. It iteratively finds augmenting paths from the source to the sink and increases the flow until no more augmenting paths can be found.

What is the relationship between minimum cut and maximum flow?

The relationship between minimum cut and maximum flow is established by the Max-Flow Min-Cut Theorem, which states that the maximum flow in a flow network is equal to the capacity of the smallest cut that separates the source and sink.

Can you give an algorithm to solve the minimum cut problem?

One common algorithm to solve the minimum cut problem is the Stoer-Wagner algorithm, which finds the minimum cut in a weighted undirected graph efficiently. Another approach is to use the Max-Flow Min-Cut Theorem, where the minimum cut can be derived from the maximum flow calculations using an appropriate flow algorithm.

What are the definitions of the following problem? Can you give algorithms to
solve them?
• Maximum bipartite matching
• Maximum edge-disjoint path set
• Network connectivity

The maximum bipartite matching problem finds the largest matching in a bipartite graph, and can be solved using algorithms like the Hopcroft-Karp algorithm. The maximum edge-disjoint path set problem seeks the largest set of paths where no two paths share an edge, which can be approached with flow network techniques. Network connectivity refers to the measure of a network's connectedness; it can be analyzed using depth-first search or the Edmonds-Karp algorithm to determine connectivity and components.

Can you run the incremental method to find the maximum matching on a given
graph?

Yes, the incremental method for finding the maximum matching can be applied to a given graph by progressively adding edges and checking for augmenting paths until no more can be found.

What is the Hall’s theorem?

Hall's theorem states that a bipartite graph has a matching that covers every vertex of one partition if and only if for every subset of vertices in that partition, the number of neighbors in the other partition is at least as large as the subset itself.

Can you run the Dijkstra’s algorithm on a given input?

Yes, Dijkstra's algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative weights by repeatedly selecting the vertex with the smallest tentative distance and updating the distances of its neighbors.

Why Dijkstra’s algorithm requires that the weights are non-negative?

Dijkstra's algorithm requires non-negative weights because negative weights can lead to situations where previously determined shortest paths are invalidated, making it impossible to guarantee the correctness of the algorithm's results.

Can you give an analysis of the running time of Dijkstra’s algorithm?

Dijkstra's algorithm has a time complexity of O(V^2) using a simple array or O(E + V log V) when using a priority queue implemented with a binary heap, where V is the number of vertices and E is the number of edges in the graph.