Minimum spanning tree

(See attached file for full problem description)

Topological Sorting

An algorithm for computing a topological ordering of a DAG (Directed Acyclic Graph) repeatedly finds a node with no incoming edges and deletes it. This will eventually produce a topological ordering, provided that the input graph really is a DAG. But suppose that we're given an arbitrary graph that may or may not be a DAG. Ex ...continues

Median Finding Algorithm for Joint Databases

You are interested in analyzing some hard to obtain data from two separate databases. Each database contains n numerical values - so there are 2n values total- and you may assume that no two values are the same. You'd like to determine the median of this set of 2n values, which we will define here to be the nth smallest value. ...continues

Scheduling Activities

Your friend is working as a camp counselor at a camp. He needs to organize activities for the kids. One of his plans is the following marathon: each contestant must swim 20 laps of a pool, then bike 10 miles, and then run 3 miles. The plan is to send the contestants out in a staggered fashion via the following rule: the contesta ...continues

Oral History Data Organization

You are helping scientists analyze oral history data they have collected by interviewing members of a village. From these interviews they have learned about a set of n people (all are dead now) whom we will denote P1, P2, ... Pn. The have also collected facts about when these people lived relative to one another. Each fact ...continues

Edges and graphs

The solution below got cut off. Please let me know what is the total solution: problem: The number of strongly connected components in a graph G is k. By how much can this number change if we add a new edge? solution: If we add an edge to a biconnected graph with k strongly connected components, then the ...continues

Flow network

(See attached file for full problem description)

Edge connectivity

The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of vertices is 2. Show how the edge connectivity of an undirected graph G = (V, E) can be determined b ...continues

Maximum cardinality matching algorithm

A tree is a connected undirected graph with no cycles. Design a linear time algorithm to find a maximum cardinality matching in a tree.

Compare the two non-sequential file structure models

Compare the two non-sequential file structure models: the random (hashed) file and the index file. What advantages does the first one have over the second and what advantages does the second have over the first? What would be your criteria for choosing one over the other for different applications?