page 1  (2 pages) 2

Prelim Algorithms Question?9/28/92

Each part is worth 20 points. You should score 60 to ensure passing. You may answer all parts. Please feel free to ask questions if you do not understand a problem.

Part 1.

A. Person 1 proves that problem P has W(n2) best-case time complexity. Person 2 proves that algorithm A solves the problem with best-case time W(n3). Person 3 proves that algorithm B solves the problem with best-case time W(n) . Can all three be right? Why or why not?

B. The clique problem is the following: given a graph G=(V,E) and an integer k, determine whether there is a subgraph of size k that is completely connected (i.e. a clique). The clique problem is NP-complete.

Consider the following algorithm to determine whether a graph has a clique of size k . First, generate all subsets of vertices of size k. Then, check whether any of the subgraphs induced by these subsets is complete. Why is this not a polynomial-time algorithm for the clique problem, thus proving that P=NP?

C. Give an exact solution for the following recurrence relation when n is a power of 3. Simplify your solution as much as possible.
T(1) = 2
T(n) = 3 T(n/3) + n, n >1

D. What is the asymptotic running time of the following section of code as a function of n? x = n
while x > 2 do

x = x

Part 2: You want to statistically test whether the player with the white pieces has a significant advantage in the game of chess. Therefore you have taught the game to a number of players. A tournament is set up in advance with a number of games listed: player A will play B, C will play D, A will play D, etc. You can?t change the schedule of games to be played, but you want to arrange it so that some players will specialize in playing the black pieces (i.e. always play black), and some will specialize in playing the white pieces (i.e. always play white). Of course, each game must have one player playing black and one playing white. It may or may not be possible to assign specializations to players so each will play only black or only white and all the games of the tournament will be played. Give the most efficient algorithm you can find for assigning specializations to players so that all the games can be played, if possible. Analyze the runtime of the algorithm both in terms of the number of players and the number of games scheduled. Justify the correctness of your algorithm.

Part 3: In some games, players have to roll large handfuls of dice with varying numbers of sides per die. Some dice may have 6 sides, some 12, some 20, etc., and the sides of a die are numbered 1, 2, ..., k, where k is the number of sides of the die. When you roll a handful of dice, the value of the roll is the sum of the numbers on each of the faces pointing up. The game designer needs to know the relative likelihood of the different possible values for a roll of several dice, and she has asked you to devise an algorithm to help.

You are given n dice with s1, s2, ..., sn sides. Give an efficient dynamic programming algorithm for computing the number of ways of rolling each possible value.