Algorithms B-Exam May 1997

There are 3 questions worth 10 points each for a total of 30 points.

1. You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together (a comparison), from which you can determine whether the nut is too small, too large, or an exact match for the bolt, but there is no way to compare two nuts together, or two bolts together. Show that you can find the smallest bolt and its corresponding nut with only 2n − 2 comparisons.

2. Design an efficient algorithm that, given a connected undirected graph G, finds a spanning tree of G of minimum height. Analyze the complexity of your algorithm.

3. The HALF-CLIQUE problem is, given an n-vertex graph G, to determine whether G has a clique with at least n/2 vertices. Show that HALF-CLIQUE is NP-complete.