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
	  22 	         5       DAM2: 2.3: 19  
	  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 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
2.8        4             5       DAM2: 2.5, 4 
2.8       10             5       DAM2: 2.5, 10