CSC 343
Homework 1

Assigned Aug 28, due Sept 23

Some of these problems can be done in varying levels of detail. The more work you do, and the more aspects of the problem you explore, the more impressed I'll be and the more credit you'll get.

In order to save time, I won't grade every single problem; the rest should be considered as "for practice".

There are 17 problems and a program to do. You have 26 days, so try to do at least one problem a day; that way even if you get delayed, you have some safety cushion.

Problems from the CLRS textbook

• Exercise 1.1-5: real-world examples of optimization and "approximate optimization" problems
• Problem 1-1: how large a problem instance can be solved in given amount of time for given algorithm efficiencies?
• Exercise 2.2-4: how to "game" the notion of "best-case run-time"
• Problem 3-2: for each of six pairs of functions, identify O(), o(), Ω(), ω(), and Θ() relationships

Problems from the Shaffer textbook

• Exercise 1.6 on sparse arrays: describe the ADT and two different implementations (a few sentences each; no code!)
• Exercise 1.16 on representing a graph
• Choose one: either 2.15 (permutations) or 2.16 (subsets). Shaffer describes the "subsets" problem as being "subsets of the first n positive integers," but I'd prefer that you write it to work for any n integers you are given. This shouldn't be significantly harder.
  You can write this in pseudocode, but if you're not sure your algorithm is correct, try writing it in real code (whatever language you like) and testing it.
  It may be easier to think of your function as returning the answer rather than printing it.
• Exercise 2.24 (an induction proof)
• Exercise 2.32 (proving by induction the solution to a recurrence)
• Choose two of exercises 2.36-2.45 (back-of-the-envelope estimation)
• Exercise 3.3: arrange expressions by growth rate
• Exercise 3.12: analyze some code fragments for run-time

Problems from other textbooks:

• 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 partial credit for a correct but inefficient algorithm, full credit for a more efficient one.

• 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.

• Four people need to cross a narrow suspension bridge. The bridge is only strong enough for two people to cross at a time. Furthermore, it's really dark and the suspension bridge has some gaps, so nobody's going to cross the bridge without a flashlight. Unfortunately, there's only one flashlight among the group, and the batteries will die in 17 minutes. Some of the people in the group can walk faster than others, and if two people are crossing together, they can only go as fast as the slower of the two. To be precise, the guide can cross the bridge in 1 minute; another person can cross in 2 minutes; another in 5 minutes; and another in 10 minutes. The bridge is too long to throw the flashlight across; it must be carried.

  For partial credit, is it possible to get all four people across the bridge before the batteries die? Who should cross, with whom, in what order?

  For more credit, generalize the problem: give an algorithm which, given any number of people and how long each of them takes to cross, and the amount of battery life left, tells whether it's possible to do it in that length of time (and how). Even better, have your algorithm determine the shortest time in which all the people can get across. How efficient is your algorithm?

• 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 partial credit, prove that the game will end, i.e. eventually one player or the other won't be able to move.

  For more credit, 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 more credit, 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 more credit (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).

Programming:

Write a program in your favorite programming language -- C, C++, Java, Pascal, perl, Prolog, Python, Ruby, Scheme, etc. -- to manipulate polynomials. A polynomial is (usually) represented as a list of coefficients: for example, the list 3, -4, 2 could represent the polynomial

3x² -4x + 2

You need to write the following functions/methods:

• A way to create a polynomial, given its coefficients (e.g. a constructor, in Java)
• A way to display a polynomial in a nice, human-readable form (e.g. a toString method, in Java)
• A way to test whether two polynomials are exactly the same
• A way to evaluate a polynomial by plugging in a particular value for x
• A way to add two polynomials, producing a new polynomial
• A way to multiply two polynomials, producing a new polynomial
• (extra credit) A way to compose two polynomials, producing a new polynomial (i.e. if p(x) and q(x) are polynomials, find p(q(x)))

For each function/method, be sure to provide well-chosen test cases with correct answers (preferably written before you write the function/method itself), so it's easy to test the program.

I'm not really interested in your ability to write I/O and driver code, so I recommend doing this problem in a system that allows you to call functions directly and interactively, such as BlueJ, DrJava, SWI-Prolog, or DrRacket.