Department of Mathematics |
University of San Francisco |
---|

Discrete Mathematics

Fall 2017

MWF 3:30-4:45, LS 103

**Announcement:** The final exam is Wed, Dec 13, 3-6p in LS 103.

**Announcement:** My last office hour is Wed, Dec 6. My office hours
during finals are Thu, Dec 7, 4-5p, and Mon, Dec 11, 1:30-2:30p.

**Announcement: 10/2/2017** The correct date for the Midterm
is Friday, October 13, *not* Wed, Oct 11.

**Professor:** Peter Pacheco

**Office:** Harney 406

**Phone:** 422-6630

**Email:** domain: `cs.usfca.edu`, user: `peter`

**Office Hours:** MW 4:45-5:45, F 12-1, and by appointment

**TA:** Wesley Yee

**Office:** HR 411 or HR 413

**Email:** domain: `dons.usfca.edu`, user: `whyee`

**Office Hours:** T 1-2, R 1-2:30

**Class mailing list:**
You can post to the class mailing
list by sending email to user `math501` in the
domain `cs.usfca.edu`. Note that this will only work from
your `usfca.edu` account.

**Course Syllabus** (Here's a
PDF Version.)

**Homework Assignments**

- Assignment 1. To be completed by the beginning of class on
Friday, Sep 1.
- Complete the participation and challenge activities in sections 1.1-1.3 of the text. (You don't need to hand anything in for this part.)
- Also complete on paper the following additional exercises: 1.1.2, 1.1.3, 1.1.4, 1.2.1, 1.2.4, 1.2.6, 1.3.1, 1.3.5. These should be handed in at the beginning of class on Friday.
- Complete the participation activities for sections 1.4-1.5 of the text. You can skip the challenge activities.
- Complete on paper the following additional exercises: 1.4.1abcd, 1.4.2bc, 1.4.3bc, 1.4.4bd, 1.4.5, 1.5.1ab, 1.5.2, 1.5.3. These should also be handed in at the beginning of class on Friday.

- Assignment 2. To be completed by the beginning of class on
Friday, Sep 8. PA = participation activity, CA = challenge
activity, AE = additional exercise.
- Section 1.6: PA: all; AE: 2-4
- Section 1.7: PA: all; CA: all; AE: 1, 2, 3, 5
- Section 1.8: PA: all; AE: all
- Section 1.9: PA: all; AE: 1, 3, 4, 5
- Section 2.1: PA: all
- Section 2.2: PA: all

- Assignment 3. To be completed by the beginning of class on
Friday, Sep 15. PA = participation activity, CA = challenge
activity, AE = additional exercise.
- Section 2.1: AE: 1a, 2bc, 3ac
- Section 2.2: AE: 1bc, 2b
- Section 2.3: PA: all; AE: 1bcgj
- Section 2.4: PA: all; AE: 1adf
- Section 2.5: PA: all; AE: 1abdh

- Assignment 4. Due at the beginning of class on Fri, Sep 22.
- Section 3.1: PA: all; AE: 1d-i, 1mo, 2, 4cd, 5
- Section 3.2: PA: all; AE: 1abefk, 2, 3, 4, 5
- Section 3.3: PA: all; CA: all; AE: 1deh
- Section 3.3: AE: 2ab
- Section 3.4: PA: all; CA: all; AE: 1, 2ab
- Section 3.5: PA: all; AE: 1abc, 2ac
- True or false. If a statement is a false, give an
example to show that it's false.
- If A and B are infinite sets, then |A| = |B|.
- If A is a proper subset of B, then |A| < |B|.
- If A is a finite set and A is a proper subset of B, then |A| < |B|.

- Assignment 5. Due at the beginning of class on Fri, Sep 29.
- Section 3.6: PA: all; AE: 1abc, 3bde, 5
- Section 4.1: PA: 1-6; AE: 1, 3
- Section 4.1: PA: 7
- Section 4.2: PA: all; CA: all; AE 1
- Section 4.6: PA: 1
- Section 4.6: PA: 2-5; AE: 2, 3, 4, 5ab
- Section 4.5: PA: all; AE: 1, 2ad, 3ac

- Assignment 6. Due at the beginning of class on Fri, Oct 6.
- Section 4.5: AE: 4
- Section 4.3: PA: all; AE: 1, 2
- Section 4.4: PA: all; AE: 1, 2
- Section 6.1: PA: all; AE: 1ac, 2a
- Section 6.2: PA: 1-6; AE: 1bde

- Assignment 7. Due at the beginning of class on Fri, Oct 20.
- Section 3.7: PA: all; AE: 1a, 2abc
- Section 6.9: PA: all; AE: 1ade, 2

- Assignment 8. Due at the beginning of class on Fri, Oct 27.
- Section 7.1: PA: all; AE: 1abe
- Extra Problems. Here are some solutions to the extra problems

- Assignment 9. Due at the beginning of class on Fri, Nov 3.
- Section 7.2: PA: 1-5.
- Section 7.2: PA: 6-7, AE: 1ah, 2a, 3a
- Section 7.2: PA: 8-9, AE: 1cdg, 4a

- Assignment 10. Due at the beginning of class on Fri, Nov 10.
- Section 7.3: PA: 1-6. Note that the analysis in 5 isn't quite right: it counts both returns, when only one will be executed.
- Section 7.3: AE: 1, 2a, 3, 4. You can use any results from the text or class.
- Extra Problems.
Here are some solutions.

- Assignment 11. Due at the beginning of class on Fri, Nov 17.
- Section 8.4: PA: 1-4, AE: 2ab, 3ab
- Section 8.5: PA: 1, 3-7, AE: 1a
Note that the inductive step in the text's solution to 8.4.3a states that "k is a positive integer." Technically, they should say that "k is a positive integer ≥ 2."

- Assignment 12. Due at the beginning of class on Fri, Dec 1.
- Section 8.5: PA: 2; AE: 2b
- Section 8.6: PA: 1, 2, 5; AE: 2b
- Extra Problems.
- Section 8.10: PA: 1, 3, 4; AE: 1, 2 (the algorithms are given in the solutions to AE 8.9.1 and 8.9.2).

- Not for credit. These problems are not for credit, but I
recommend that you work them before the final exam.
- Section 8.11: PA: 2-6; AE: 1ab, 2abc, 3ad

**Other Information**

- Implementation of set operations using bit vectors. The universal set is {0, 1, ..., n-1}.
- C program that uses
the algorithms in Theorem 4.6.1 in the text to compute
the floor and ceiling of
`log_b(n)}`. - C program that carries out n integer additions and n integer divisions and reports the elapsed time for the additions and the elapsed time for the divisions.
- C program that implements an algorithm for finding the maximum element in an array of ints.
- C program that uses selection sort to sort an array of ints.
- Keys to the first and second versions of the midterm.
- C program that raises a real number to an integer power. It uses an iterative and a recursive algorithm.
- Pseudocode for finding the power set of a input set.
- C program using recursion to compute the Fibonacci numbers
- C program implementing binary search and reporting on its run-time

USF Math Department home page

USF CS Department home page

USF home page

Peter Pacheco 2017-12-06