# MATH 302 - Discrete Mathematics

**TEXTBOOK:**
see
current textbook list

**CATALOG DESCRIPTION:** See catalog description here

**GRADING** Up to the instructor. Normally, two or three
major exams and a final exam are given in this course. In addition,
homework, quizzes, and/or project assignments are given.

**MAKE-UP POLICY:** Make-ups for missed quizzes and exams
will only be allowed for a university approved excuse in writing.
Wherever possible, students should inform the instructor before an
exam or quiz is missed. Consistent with
University Student Rules,
students are required to notify an instructor by the end of the
next working day after missing an exam or quiz. Otherwise, they
forfeit their rights to a make-up.

**SCHOLASTIC DISHONESTY:** Copying work done by others,
either in-class or out of class, is an act of scholastic dishonesty
and will be prosecuted to the full extent allowed by University
policy. Collaboration on assignments, either in-class or
out-of-class, is forbidden unless permission to do so is granted by
your instructor. For more information on university policies
regarding scholastic dishonesty, see
University Student Rules.
(This is soon to be moved to the Honor Council page.)

**COPYRIGHT POLICY:** All printed materials disseminated in
class or on the web are protected by copyright laws. One xerox copy
(or download from the web) is allowed for personal use. Multiple
copies or sale of any of these materials is strictly
prohibited.

**SYLLABUS**

**Note: This is a fall or spring schedule. In summer, this
schedule is accelerated by 50% in order to accommodate a 10-week
session.**

- Chapter 1 [3 weeks]
- Section 2.2 and complexity handout [1 week]
- Sections 3.1--3.4 and test [2 1/3 weeks]
- Section 4.1 [1/3 week]
- Sections 4.3--4.5 [1 1/3 week]
- Sections 6.1--6.2 and test [2 1/3 weeks]
- Section 6.3 and master theorem handout [1 week]
- Section 6.4 [2/3 week]
- Operations (optional) [2/3 week]
- Sections 7.1--7.5 and test [2 1/3 weeks]

- In Section 2.3, do big-Oh, and also teach big-Omega and big-Theta. Big-Theta and big-Omega are essential for understanding the master theorem. A handout for this section is maintained by Prof. Hobbs. This handout substantially expands the theory of complexity beyond the text. It includes the use of limits for determining big-Oh, big-Theta, and big-Omega relations between functions. It also discusses the topic of computing with big-Theta, a skill used by the students in their computer science courses. An alternative handout on the subject is available from Prof. Sue Geller.
- Emphasize proof by induction. It is one of the topics these students will need to use in subsequent courses. After doing Section 3.3, present examples and exercises involving proof by induction throughout the rest of the course. Many instructors teach induction earlier and test proof by induction on every test.
- There is no discussion of complex roots of the characteristic equation in Section 6.2. You can skip over this case, if you wish, just as the text does. However, it would be a good idea when skipping it to warn the students that complex arithmetic can show up in solving linear second and higher order recursions. If you find this unsatisfactory, a good write-up of the complex root case is in Grimaldi's text, which is in the libraries of most long-time instructors of this course.
- Mastery of the big-Theta version of the master theorem
(inadequately stated in Section 6.3) is also important for the
students. The Computer Science Department supplied us with a copy
of Chapter 4 of the book
*Algorithms*by Cormen, et. al., asking that we teach the master theorem carefully to the Math. 302 students. Prof. Hobbs has prepared a handout based on this chapter and presenting both the big-Theta version of the master theorem and a method of learning the rate of growth of the function involved in the case that the recursion falls in one of the gaps of the master theorem. This method can be used to prove the master theorem, too. An alternative handout on this subject is available from Prof. Sue Geller. - Chapter 4 of the Cormen book and the handouts prepared by Prof. Hobbs are available to you on request to him. The handouts are available to the students for less than $1.50 from Kinko's. Tell the students to ask for the Math. 302 handouts.
- This course is the prerequisite for the CS course on algorithms (CPSC 311). The instructors of that course need the students to be competent at proof by induction, asymptotics (Section 2.2 and handouts), equivalence relations, generating functions, and recurrence relations.

Last modified by rww on Thu Aug 25 13:49:49 2005>