Some Information for Final Exam

Date: Monday Dec. 11, 2:15-4:15, usual classroom (K301)

• Permitted: You can bring in one page (two sides of an 8x11 page) of "crib" notes containing anything you like.
• Otherwise: no text. I'll be allowing calculators, but they shouldn't help, and you should show all calculations, especially involving factorials

Section(s): 1.1-1.6 (logic)

• Expect:
  
  • Translating between English and propositional and predicate logic
    
  • Negation, converse, contrapositive of formulas
    
  • Determining whether argument forms are valid.
    
  • Using truth tables.
    
• Typical problems:
  
  • p38/27,45,61
    
  • p58/33,37
    
  • p69/11
    
  • Supplemental problems p117/3,4,9,20,21,32
    

Section(s): 2.1-2.3 (Sets and functions)

• Expect:
  
  • Basic set operations (including proofs)
    
  • Basic function ideas, such as 1-1/injection, onto/surjection, bijection, domain, range
    
• Typical problems:
  • p131/19,21,26
    
  • p145/27,23,57, 65, 66, 68
    
  • p162/15,23, 73
    
  • Supplemental problems p197/2,3, 5, 11, 18
    

Section(s): 4.1-4.4 (number theory)

• Expect:
  • Primes, arithmetic mod m, solving congruences, GCD/LCM, Euclidean algorithm, Bezout's Thorem
    
  • You can absolutely expect problems involving Fermat's little theorem and the Chinese Remainder Theorem
    
• Typical problems:
  • p259/27, 29, 39, 43
    
  • p272/33, 39
    
  • p269/11, 20, 38
    
  • Supplemental problems p325/6, 7, 8, 21, 24, 25, 29, 37, 39, 40, 41
    

Section(s): 5.1-3 (Induction)

• Expect:
  • Proof by induction, well-ordering, strong induction. Structural induction is optional.
    
• Just review the HW

Section(s): 6.1-6.5; 8.5,6

• Expect:
  • General counting methods, Permutations, Combinations, the Binomial Theorem, Combinatorial proofs of things
    
• Typical problems:
  • Just review the HW and the WW
    

Section(s): 8.1,2 (Recurrence relations)

• Expect
  • You can expect to find the closed form of a linear homogenous recurrence relation and of a nonhomogenous one.
    
  • You might get a word problem where you have to figure out what the recurrence relation is.
    
• Just review the HW and the WW
  

Section(s): 10.1-3, 10.5, 10.8 (but only the parts we discussed; see notes and the suggested reading on our main web page)

• Graph Theory
  
• Expect:
  • Some terminology (degree, path, circuit, chromatic number, complete graph, bibartite graph, etc)
  • Just do the WW and look at the 'extra' problems I've just assigned.