Discrete Mathematics, Spring 2018


Week 1

1 Mon, 22 Jan Download the Course Syllabus.

Homework: Section 0.2, #1, 2, 5.
2 Wed, 24 Jan Homework: Section 0.2, #7, 8, 10.
3 Fri, 26 Jan Homework: Section 0.3, #1, 5, 7, 9.


Week 2

4 Mon, 29 Jan Nick's office hours are from 5:00—7:00 tonight in Room 315 in the library.

Homework from Section 0.4: #1, 5, 7, 10, 13.
5 Wed, 31 Jan Homework from Section 1.1: #1, 2, 3, 5.
6 Fri, 2 Feb Homework from Section 1.1: #6, 7, 11; Section 1.2: #1, 6, 10.


Week 3

7 Mon, 5 Feb Download solutions to the first Homework Quiz.

Nick will be in Room 315 in the library from 5:00—7:00 tonight.

Prof. Tom Banchoff will be speaking at 3:30 in Cowell 107 (and there is food in the Getty Lounge (where the fireplace is in Lo Schiavo) starting at 3:00).

Homework: Section 1.3, #1, 2, 8, 10, 11, 12. Note: For large answers, leave in unevaluated form, such as ${200\choose93}{367\choose58},$ rather than multiplying out.

Don't forget the Homework Quiz on Wednesday!
8 Wed, 7 Feb Here is a link to counting poker hands. You will be given one of these (except "high card only") to reproduce on your midterm!
9 Fri, 9 Feb Homework from Section 1.4: First, read the solutions to #3 and #5. Bring questions! Then do problems #1, 4, 7.


Week 4

10 Mon, 12 Feb Nick will be in Room 314 tonight in the library from 5:00—7:00.

Download solutions to Homework Quiz 2.

Homework from Section 1.5: #2, 3, 4.
11 Wed, 14 Feb Homework from Section 1.6: #1, 3. Bring your books on Friday!
12 Fri, 16 Feb In-class review (Section 1.7): #1(a)-(c), 2(a)-(f), 5(a)(b), 7, 10, 12, 13, 16(a)(b), 17(a)(b).

Additional practice problems from the book (all but a few have answers in the back):
  1. Section 0.3: #14, 15.
  2. Section 0.4: # 2, 6, 8.
  3. Section 1.2: #2, 5.
  4. Section 1.3: #3.
  5. Section 1.5: #5, 11.
  6. Section 1.6: #4, 8.
Remember that you should bring a calculator to the exam! You may NOT use your phone. I will NOT have any extra calculators. If you forget one, you will have to use the Pascal's Triangle projected on the screen.


Week 5

13 Wed, 21 Feb Nick will be in Room 315 tonight in the library from 5:00—7:00.

I will choose one of the first six poker hands listed.

Study for your Midterm Friday! Remember, no notes allowed, but you may bring a calculator! (I will not have extras.)
14 Fri, 23 Feb First Midterm!


Week 6

15 Mon, 26 Feb Download solutions to the first Midterm.

Nick will be in Room 315 tonight in the library from 5:00—7:00.

Homework: Section 2.1, #1, 3; Section 2.2, #1, 2, 4.
16 Wed, 28 Feb Homework: Section 2.2, #6, plus the problems on the handout.
17 Fri, 2 Mar Homework: Section 2.3, #1(a)(b)(c), 3.


Week 7

18 Mon, 5 Mar Nick will be in Room 315 tonight in the library from 5:00—7:00.

Homework: Section 2.4, #5, 7.
19 Wed, 7 Mar Solve the following linked systems:

  1. $F_{n+1}=5F_n-4G_n,\quad$ $G_{n+1}=2F_n-G_n,\quad$ $F_0=-1,\quad$ $G_0=4.$

  2. $F_{n+1}=F_n+G_n,\quad$ $G_{n+1}=8F_n+3G_n,\quad$ $F_0=0,\quad$ $G_3=747.$
20 Fri, 9 Mar Solutions to Wednesday's homework: (1) $F_n=-10\cdot3^n+9,$ $G_n=-5\cdot3^n+9.$ (2) $F_n=\dfrac32(5^n-(-1)^n),$ $G_n=6\cdot5^n+3(-1)^n.$

Homework: Section 2.4, #2 (there are two similar examples worked out in detail in the book), and solve the recurrence $a_{n+2}=4a_{n+1}-4a_n,$ $a_0=a_1=1.$

Solution: $a_n=\left(1-\dfrac n2\right)2^n.$



Week 8

21 Mon, 19 Mar Nick will be in Room 315 tonight in the library from 5:00—7:00.

Download solutions to Homework Quiz 3.

Homework:
  1. Prove using mathematical induction that $\displaystyle\sum_{k=1}^nk^2=\dfrac16n(n+1)(2n+1)$ for $n\ge1.$

  2. Prove using mathematical induction that $4^n+(-1)^n$ is the solution to the recurrence $a_n=3a_{n-1}+4a_{n-2},$ with $a_0=2$ and $a_1=3.$

  3. Section 2.5, #1—5.
Homework quiz on recurrence relations is Friday this week. This is so you can work on the induction homework. We are having an in-class work day on Wednesday, and I will be coming around working with you individually. In order for me to critique your work, you need to have something done!


Week 9

24 Mon, 26 Mar Nick's office hours will be Wednesday evening this week.

Here is the link to the complexity of algorithms. You should do Exercises 1 and 3 for homework.
25 Wed, 28 Mar Nick's office hours are in Room 315 tonight in the library.

Do Exercises 5 and 7 from the complexity website.

Practice problems from the Chapter Review: #1, 2, 3, 5, 6, 10, 11, 13(a)(b)(c), 14, 15, 16.

Download solutions to Homework Quiz 3.


Week 10

28 Fri, 6 Apr Download solutions to the second Midterm.


Week 11

29 Mon, 9 Apr Homework from Section 3.1: #1, 2, 5, 7(a)(b)(c), 10, 14(a)(b).

Start homework from handout: #27, 28.
30 Wed, 11 Apr Proofs from Section 3.2: 1, 2, 6, 8, 11, 13, 15 (prove each part). Note: This homework is for today, Friday, and next Monday.

Homework quiz next Wednesday!


Week 12

33 Wed, 18 Apr Read this chapter on relations! There are a lot of new definitions and notations. None are especially difficult, but the language is different from mathematical language we've used up until now, so you need to get familiar with it. We'll continue going over it on Friday.
34 Fri, 20 Apr Homework from the chapter on relations: #72, 73, 75, 78, 79, 80, 81, 84.