
CSC 789 Assignment 5
Due date, November 30, 2004, 5:30 PM.
-
I have concluded that the proof of the probability of success of the
algorithm FASTCONTRACT given on page 295 of your textbook is intuitively
incomprehensible to me.
This is not the same as saying I could not present the proof in class.
I certainly could. But what would you learn? Nothing, I claim.
Your assignment is to find a different proof of the same theorem.
Hopefully, someone will find an intuitively comprehensible proof, or that
I can piece together an intuitively comprehensible proof from the
different things that people turn in.
Just copying the proof in the book is unacceptable. I want something
different, preferably something different from each student.
"Intuitively comprehensible" does not mean the same thing as comprehensible.
A proof can be comprehensible in the sense that each step can be explained.
I want something better ... a proof where a person at your level of
sophistication can understand it "all at once," i.e., it makes sense.
Barring that, I would like a proof where a person at MY level of
sophistication can understand it "all at once."
I have spent hours at home working on this without success, and will waste
no more class time with it, until you people turn in the homework on
November 30 and I look at it. It has been a humbling experience.
I should point out that some published proofs of major theorems are
intuitively incomprehensible. But this is frowned upon, i.e., a
later comprehensible proof of the same theorem is considered a major
contribution.

Back to
Course Page