Homework 2

September 23rd, 2007

Homework 2 consists of problems that are entirely from the textbook. Since many of the problems are rather long and wordy, I thought it better to merely mention the problem numbers, rather than reproducing them in their entirety. However, I know that many of you don’t own the textbook, and use library versions. If you foresee *any* problems in accessing the textbook in order to work on the problems, please let me know as soon as possible, and I can make copies of the problems for you.

Note that the due date is earlier than normal: Oct 5 rather than Oct 8. This is because fall break starts on Oct 6.

The problems are:

  1. 4.3 (The UPS problem)
  2. 4.9 (Bottleneck spanning trees)
  3. 6.1 (Independent sets)
  4. 6.6 (Typesetting): This problem dates back to Knuth, who mentions this as one of the problems he faced when designing TeX, (LaTeX is a high-level wrapper for TeX)
  5. 6.8 (The Matrix, Reloading…)

Here’s the PDF and LaTeX source for the homework.

This entry was posted on Sunday, September 23rd, 2007 at 10:22 pm and is filed under Homework, News.

6 Responses to “Homework 2”

  1. Randy Q. Sort Says:
    September 25th, 2007 at 10:43 am

    I think you mean 6.6 (the Typesetting problem) - 6.7 talks about stocks and the like.
    This, of course, assumes I’m looking in the right book.

  2. admin Says:
    September 26th, 2007 at 11:55 pm

    This is correct. I have updated both the pdf/latex and the page itself. Thanks for pointing this out.

  3. A. Star Says:
    September 29th, 2007 at 5:53 pm

    So suppose there’s some question, and we come up with a solution, but it doesn’t work. This solution, however, leads us to a working one. Would you prefer we put only our final answer? Or also our train of thought leading up to it?

  4. admin Says:
    September 30th, 2007 at 9:04 pm

    Nothing except the final solution is necessary. I’m leery of allowing “train of thought” submissions, because they tend to degenerate into multi-page rambles that go nowhere.

    If however, the train of thought itself is “interesting” (maybe it solves a related problem), then you’re welcome to insert it. Often in research papers, a “wrong” solution is presented to give some intuition for the “right” answer a section later.

  5. Randy Q. Sort Says:
    October 1st, 2007 at 5:51 pm

    On 6.8, it seems like f(i) is always increasing, but it doesn’t actually say that as a restriction in the problem. Is it the case that we cannot assume f(i+1) >= f(i) for all i?

  6. admin Says:
    October 1st, 2007 at 5:57 pm

    For now, you can assume that f() is increasing. I actually think something bad might happen if not, but don’t hold me to that.

Leave a Reply