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. Extend the topological ordering algorithm so that given an input directed graph G it outputs one of two things: (a) a topological ordering, thus establishing that G is a DAG; or (b) a cycle in G, and thus establishing that G is not a DAG. The running time of your algorithm should be O(m+n) for a directed graph with n nodes and medges.

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. However, the only way you can access these values is through queries to the databases. In a single query you can specify a value k to one of the two databases and the chose database will return the k-th smallest value that it contains. Since queries are expensive you would like to compute the median using as few queries as possible. Give an algorithm that fins the ... click for more

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 contestants must use the pool one at a time. In other words, first one contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out of the pool a second contestant begins swimming the 20 laps; as soon as he is out of the pool and starts biking, a third contestant begins swimming and so on. Each contestant has projected swimming time (the e... click for more

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 has one of the following two forms: For some i and j, person Pi died before person Pj was born, or For some i and j, the life spans of Pi and Pj overlapped at least partially. Naturally they are not sure that all these facts are correct. What they would like you to determine is whether the data they have collected is at least internally consistent, in the sense ... click for more