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]

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.