Read: Chapter 2

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

Section   Number       Points    Comments
2.2 	  24(a)          4       DAM2: same problem
          26             5       DAM2: same problem
2.3 	  12 	         5       DAM2: 2.3: 8
                                 Note: as in problem 2.3: 11, you can assume de Morgan's 
                                 Law (although you should be able to prove it)
 	  19 	         5       DAM2: 2.3: 14
	  25             5       DAM2: 2.3: 22  
2.5       27(a)          4       Prove the algorithm described in DAM2: 2.6: 6 is correct
                                 Note that to prove correctness you have prove both that
				 the program terminates and that it does the right thing. 
				 You should use induction for both parts.  (Try to think 
                                 of a property that is maintained as you go through each
				 iteration of the loop, and use that for your induction 
                                 hypothesis.)  You can  assume that if n=1, the program 
                                 just returns the input. 
2.7       19             5       DAM2: 2.7, 14.  Note that p and q could be the same.
2.8        2             5       DAM2: 2.5, 2
           4             5       DAM2: 2.5, 4 
          10             5       DAM2: 2.5, 10