Kruskal's algorithm - graphs

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Graphs - airport problem

(See attached file for full problem description)

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 that... click for more

Minimum amount of Base Stations

Let's consider a long, quiet country road with houses scattered very sparsely along it. (Picture the road as a long line segment with an eastern endpoint and a western endpoint.) Further lets suppose that despite the country setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations. Give an efficient algorithm that achieves this goal using as few base stations as possible.

Pseudocode to check if sum of 2 items in an array is 100

Write and explain the pseudocode to check whether there are 2 items in an array of n integers so that their total is 100.