CSE 105 Assignment 4

Due date, July 28, 2003, 8:00 AM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
  1. Work problem 3.2 on page 147 of your textbook.
  2. Work problem 3.8(a) on page 148 of your textbook.
  3. Work problem 4.3 on page 169 of your textbook.
  4. Prove that every NP-complete problem is decidable.
  5. Convince me that, if P is a problem that can be worked by any machine that exists now or could ever be invented, that P can be worked by some Pascal program. (Use C, C++, or Java, if you prefer.) (You may make use of the Church-Turing thesis.)
  6. You have a job as a grader for some elementary programming course. The instructor says to you, "For this first assignment, I just want them to write a program that inputs two numbers and prints the sum. I don't care how their program does it, or how long the program takes to do it. I just want you to give them full credit if it works."
    Prove that your job is impossible.

Back to Course Page