CSC 344
Homework 1

• Chapter 1, Exercise 3, about two competing television networks. 3 points.
• Chapter 2, Exercise 1, working with asymptotic growth rates. 1 point.
• Chapter 2, Exercise 2, working with asymptotic growth rates. 1 point.
• Chapter 2, Exercise 3, working with asymptotic growth rates. 1 point.
• Chapter 2, Exercise 4, working with asymptotic growth rates. 1 point.
• Chapter 2, Exercise 6, analyzing and improving an algorithm in pseudocode. 3 points.
• Chapter 2, Exercise 8, developing and analyzing a series of algorithms in pseudocode. 3 points.

Consider the following two-player game: several distinct positive integers (initially two) are written down on a large sheet of paper. Each player, in alternation, chooses two of the existing numbers and writes down their difference on the sheet, but only if that number is not already written down. Whichever player makes the last legal move wins.

For 1 point, prove that the game will end, i.e. eventually one player or the other won't be able to move.

For 1 more point, tell me which player wins, if they both play optimally. If it depends on what two numbers are written down, tell me how it depends on those numbers, i.e. given the two numbers, how would you decide whether you wanted to move first or second? (And, incidentally, what constitutes "playing optimally"?)

For 1 more point, suppose you had to decide whether to move first or second before the numbers were chosen (at random). Would your chances of winning be better if you moved first, if you moved second, or are the chances the same? (It may take a bit of work even to state the problem precisely, since there are infinitely many possible numbers to choose from.)

For 1 more point (even if you didn't do the preceding "random" part of the problem), generalize the problem to any number of players (at least two) and any number of numbers written down initially (at least two).

Write an algorithm in pseudocode which takes in a list (or array or whatever) of n numbers, and determines whether or not there is a number that appears more than once in the list. For example, dups(3,8,5,1,6) would return false, but dups(3,8,5,3,6) would return true.

Analyze your algorithm's running time as a function of n. Hint: there's a brute-force way to do it, and a more efficient (but not quite as obvious) way to do it. For full credit, show me the latter.

Write an algorithm in pseudocode which takes in two binary numbers (represented as lists or arrays of booleans) and adds them, producing the result as another list or array of booleans. (Converting to int and using the built-in + operation is cheating.)

Implement, test, and debug your binary-addition algorithm in your favorite programming language -- C, C++, Java, Scheme, Prolog, perl, Pascal, etc.