Where: 211 MATH

When: 12:10-1:00 PM MWF

Final exam: 8:00-10:00 AM, Tuesday, December 10

Office hours: 10:30-11:30 AM, Tuesday or by appointment in 004E MATH

email: cory.palmer [at] umontana [dot] edu

Syllabus (exam dates are TBA)

- The final exam is Tuesday, Dec. 10th at 8:00 AM in our usual classroom.
- Exam 2 study problems.
- Course announcement for Math 491: Combinatorial Algorithms
- Grades can be viewed on Moodle.
- Be sure to staple and remove perforated edges from homework.
- Regrade request form. Fill this out if you find a grading error in your homework or exams.
- Everyone has had .5 points added to their homework 1 score to account for a grading error on problem 8 from section 1.2
- Office hours have been changed to Tuesdays 10:30 to 11:30 AM.

- Homework 1: (Due Fri., 9/6)
- 1.1: # 6cfg, 12, 20abcd, 26, 62
- 1.2: # 8ab, 22 (use a truth table), 40, 46 (read the definition of a NAND gate above problem 46)
- 1.3: # 2, 6, 10, 15, 34

- Homework 2: (Due Wed., 9/18)
- 1.4: # 10abcd, 24, 28agh, 38
- 1.6: # 5, 6, 14, 24, 25
- 1.7: # 4, 5, 9, 12, 31

- Homework 3: (Due Wed., 9/25)
- 2.1: # 2, 15, 24
- 2.2: # 20, 26, 30
- 2.3: # 2, 12, 16, 36, 70bc
- 2.4: # 2, 14, 19,
~~32, 37~~

- Homework 4: (Due Wed., 10/2)
- 2.4: # 32, 37, 42
- 4.1: # 4, 8, 10, 20, 28, 38, 43
- 4.2: # 4, 8, 12, 30, 38

- Homework 5: (Due Fri., 10/18)
- 3.1: # 4, 15, 24, 41, 42, 46, 56, 60
- 4.3: # 2, 12, 26, 44 (in 26 the symbol 5|a+b means that a+b is divisible by 5)

- Homework 6: (Due Fri., 10/25)
- 3.2: # 2, 8, 10, 18, 20, 24, 26
- 4.4: # 8, 10, 18, 24, 50, 51, 52

- Homework 7: (Due Fri., 11/1)
- 3.3: # 2, 8, 24, 27, 28ab

- Homework 8: (Due Fri., 11/8)
- 3.4: # 12, 18, 24
- 3.5: # 8, 10, 14, 20abc
- 3.6: # 2ab, 10,
~~30~~(hint: for 10 look at example 6 on pg. 222) - 3.7: # 2ab, 18 (for 18 use the Chinese Remainder Theorem)

- Homework 9: (Due Fri., 11/15)
- 5.1: # 2, 12, 26, 35, 38, 44
- 5.2: # 2, 6, 16, 42 (hint: use induction for 42)
- 5.3: # 2, 14, 16, 24, 34, 40

- Homework 10: (Due Fri., 12/6)
- 7.1: # 6abeh, 8dfg, 24, 26, 28, 42, 44
- 7.2: # 4ad, 8, 11,
~~12, 18~~

#### Practice problems

- Chapter 1 Review Questions: 1-3, 4a, 6-7, 10-16
- Chapter 1 Supplementary Exercises: 1, 2, 4-7, 14-21, 23-29, 32-40
- Chapter 2 Review Questions: 1-15
- Chapter 2 Supplementary Exercises: 1-10, 11a, 12-16, 18-32
- Chapter 4 Review Questions: 1-5
- Chapter 4 Supplementary Exercises: 1-11, 13-14

- Chapter 4 Review Questions: 7, 10-13
- Chapter 4 Supplementary Exercises: 51, 53-59, 62
- Chapter 3 Review Questions 1-20
- Chapter 3 Supplementary Exercises: 1-32
- Chapter 5 Review Questions: 1-18
- Chapter 5 Supplementary Exercises: 1-46

#### Class Schedule and readings

- Fri, 12/6: Final exam review
- Wed, 12/4: More on solving recurrence relations. (Reag pg. 460-464 in Rosen)
- Mon, 12/2: Solving recurrence relations. (Read pg. 460-464 in Rosen)
- Mon, 11/25: More recurrence relations. (Read. 456 in Rosen)
- Fri, 11/22: Begin recurrence relations. (Read pg. 449-456 in Rosen)
- Wed, 11/20: EXAM 2
- Mon, 11/18: Permutations and combinations with repetition (bars and stars argument). Permutations of indistinguishable objects. (Read pg. 370-376 in Rosen)
- Fri, 11/15: Combinatorial proofs (proofs by double counting). (Read pg. 365-368 and exercise 21 in Rosen)
- Wed, 11/13: More combinations: poker hands. Binomial theory and applications. (Read pg. 363-364 in Rosen)
- Fri, 11/8: Permutations and combinations. (Read pg. 355-360 in Rosen)
- Wed, 11/6: Pigeonhole principle. (Read pg. 347-351 in Rosen)
- Mon, 11/4: Begin counting: sum rule, product rule, basic inclusion-exclusions. (Read pg. 335-344 in Rosen)
- Fri, 11/1: Inverses, Chinese Remainder Theory, Fermats Little Theorem, public-key cryptography. (Read pg. 234-237, 239, 241-244 in Rosen)
- Wed, 10/30: Representation of integers and applications of number theory. (Read pg. 220-222, 231-232 in Rosen)
- Mon, 10/28: Greatest common divisors and representation of integers. (Read pg. 215-217, 219-221, 228 in Rosen)
- Fri, 10/25: More modular arithmetic, prime numbers. (Read pg. 204, 210-213 in Rosen)
- Wed, 10/23: More number theory: division algorithm, modular arithmetic. (Read pg. 202-208 in Rosen)
- Mon, 10/21: Finish growth of functions. Begin integers and division. (Read pg. 194-196, 200-202 in Rosen (197-199 optional but interesting))
- Fri, 10/18: Growth of functions and algorithms. (Read pg. 186-190, 193-194 in Rosen)
- Wed, 10/16: Growth of functions. (Read pg. 180-186 in Rosen)
- Mon, 10/14: Return exam 1. Halting problem. Recursive algorithms. (Read pg. 176-177, 311-312, 314 in Rosen. Skip examples with gcd and mod.)
- Fri, 10/11: Algorithms: search, sort, and greedy. Sorting as folk dances: bubble, insertion, others (Read pg. 167-176 in Rosen)
- Wed, 10/9: EXAM 1.
- Mon, 10/7: Recursive definitions and structural induction. (Read pg. 299-305 in Rosen)
- Fri. 10/4: Recursive definitions and structural induction. Euler-Binet formula (Read pg. 294-298, 303-304 in Rosen)
- Wed, 10/2: More induction. (Read pg. 273-275, 277-278 in Rosen)
- Mon, 9/30: Strong induction. (Read pg. 283-288 in Rosen)
- Fri, 9/27: More induction examples. Shifting the base case. (Read pg. 268-272 in Rosen)
- Wed, 9/25: Principle of induction and basic examples. (Read pg. 263-268 in Rosen)
- Mon, 9/23: Countable vs. uncountable: rationals are countable, reals are uncountable. (Read pg. 158-160 in Rosen)
- Fri, 9/20: Floor/ceiling function, sequences, geometric sequence, summations (series), geometric series. (Read pg. 143-144, 149-157 in Rosen)
- Wed, 9/18: Onto functions, bijective funtions, inverse function, composition of functions. (Read pg. 137-142 in Rosen)
- Mon, 9/16: deMorgan's laws for sets, introduction to function, one-to-one function. (Read pg. 124-128, 133-137 in Rosen)
- Fri, 9/13: Empty set, cardinality, power set, Cartesian product, union, intersection, disjoint sets, set difference, complement (Read pg. 115-119, 121-124 in Rosen)
- Wed, 9/11: Introduction to sets: basic definitions. (Read pg. 111-114 in Rosen)
- Mon, 9/9: Existence (constructive and non-constructive) proofs, uniqueness proofs, chessboard problems. (Read pg. 91-100 in Rosen)
- Fri, 9/6: More proofs by contradiction. Proofs by exhaustion and case analysis. (Read pg. 80-90 in Rosen)
- Wed, 9/4: Introduction to proofs: direct, contrapositive, contradiction. Multiple examples. (Read pg. 75-80 in Rosen)
- Fri, 8/30: Propositional logic, quantifiers, nested quantifiers, negation of quantifiers. (Read pg. 37-43, 50-58 in Rosen)
- Wed, 8/28: Propositional logic: biconditional, de Morgan's laws, propositional function, quantifiers. (Read pg. 9-11, 21-26, 30-36 in Rosen)
- Mon, 8/26: Syllabus. Propositional logic: statements, compound statements, truth tables, conditionals. (Read pg. 1-8 in Rosen)