Computer Science 280: Homework 4

WARNING: STUDENTS IN PREVIOUS YEARS FOUND THIS THE PROBLEM SET ON CHAPTER 2 THE HARDEST ASSIGNMENT. THIS MEANS:

1.

DON'T LEAVE THIS TO THE LAST MINUTE

2.

DON'T GET DISCOURAGED

3.

DO MAKE USE OF OFFICE HOURS FOR HELP

Don't forget

• clearly describe the induction hypothesis P(n) for each proof by induction
• if you're using strong induction, say so clearly

Homework 4:

2/18/04 (due 2/25/04) Read 2.5 - 2.7, Problem 2.2: 44, Supplementary problems 4 and 17 (you just have to read these; you don't have to hand them in).

Section   Number   Points    Comments
2.2 	  26 	   5
2.3 	   8       5
          11 	   5
2.4       13       5
2.5 	  2 	   5 	     For each of the problems in Section 2.5
	  4 	   5 	     If the statement is incorrect, provide a counterexample
	  10 	   5 	     (as well as pointing out the flaw in the proof); if it is correct
		 	     provide a correct proof by induction (after pointing out the flaw).
2.6 	  6(a),(c) 5 	     You can use the answer to 6(b) given in the back of the book 
                             without reproving it
          10       5
2.7 	  14 	   5