CSC 344
Homework 1

Assigned Jan 31, due Feb 19

Problems from the textbook
A sorting algorithm: (1 point)
Here's a silly way to sort a bunch of numbers: generate each of the possible permutations of the numbers, and for each one, test whether it's in order. Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation.
Another sorting algorithm: (1 point)
A slightly less-silly way to sort: for each number, count how many of the other numbers are less than it, and use this count to put it into the right location in an array. Then read off the array from beginning to end. Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation.
A problem from another textbook: (1-2 points)

You are given a bunch of floating-point numbers, and you want to find which two of them are closest together. Describe an algorithm (in pseudocode) that solves this problem. Analyze the algorithm: tell how long it will take, as a function of how many numbers there are. You'll get one point for a correct but inefficient algorithm, two for a more efficient one.

A problem from another textbook: (1-4 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"?) If it doesn't depend on what numbers are written down, convince me that it doesn't.

For 1 more point, suppose you had to decide whether to move first or second before the initial 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).

A geometry problem from another textbook: (1-2 points)

You are given a list of points in a plane, each specified by an (x,y) coordinate pair, and you want to know whether there is a single circle that they're all on. (Don't worry about "close enough"; you may assume for this problem that your floating-point numbers are infinitely accurate.) Describe an algorithm in pseudocode to solve this problem. Analyze it: tell how long it takes, as a function of the number of points.

Programming:

Write an algorithm in pseudocode which takes in two natural numbers x and b, and produces the sequence of digits in the base-b representation of x. You may assume that b is at least 2 and at most 10. Your algorithm may use the standard arithmetic operations -- addition, subtraction, multiplication, division, and remainder -- and a table containing the characters '0', '1', '2', ... '9', but you may not assume any built-in conversion routines.
Trace the action of your algorithm as it computes the base-7 representation of 103 and the base-9 representation of 5280.

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


Last modified: Wed Jan 31 10:47:04 EST 2007
Stephen Bloch / sbloch@adelphi.edu