Catalog Description

M 387 DISCRETE AND FOUNDATIONAL MATHEMATICS II (4-0-4)(S). A continuation of M 187, exploring more advanced topics in logic, set theory, and discrete mathematics. Proof techniques in predicate logic; diagonalization arguments in logic, set theory and computer science; orderered sets; mathematical methods in cryptography; advanced techniques of combinatorial enumeration; selected topics in graph theory. PREREQ: M 187.

Prerequisites

M 187, Discrete and Foundational Mathematics I. This course builds heavily on the foundation provided by M 187; many of the topics in M 387 are extensions of M 187 topics into greater depth.

Jurisdiction

This course is not currently controlled by a departmental committee. Exams, homework, grading system and exact choice of topics are left to the instructor.

Learning Objectives

This course is a continuation of M 187, and its objectives are similar, but topics are explored in greater depth with the aim of increasing the mathematical sophistication of the students. As with M 187, the course objectives encompass all four of the Department's general teaching goals: (D.1) identification and description of mathematical patterns, with an appreciation of mathematical aesthetics; (D.2) application of mathematics to real world problems; (D.3) mastery of specific mathematical tools; and (D.4) effective use of the language of mathematics in formulating problems and presenting solutions and proofs. Although it is not a Core course, M 387 also addresses quite extensively three of the four general outcomes specified in the Boise State University Core Curriculum guidelines: (C.1) critical thinking/problem solving skills, (C.2) communication skills, and (C.4) breadth of knowledge. The exact emphasis of the course will vary from semester to semester, but upon completion of the course, students should be able to:

1. Carry out translations of fairly complex statements (of both ``ordinary language" and mathematics) into precise logical form, including statements whose logical structure is not obvious from their grammatical structure.

2. Define conjunctive and disjunctive normal form for statements of propositional logic and transform arbitrary statements into those forms.

3. Construct models for sets of premises expressed in the language of predicate logic.

4. Construct well-written proofs or counterexamples, as appropriate, to show that statements expressed in the language of predicate logic do or not follow from a given set of premises.

5. Describe several well-known diagonal arguments such as Russell's paradox, Cantor's theorem on uncountability of the reals, and the Halting Problem.

6. Define the basic properties associated with partially ordered, totally ordered, and quasi-ordered sets and determine which of those properties various relations have.

7. Describe the basic notions of, and carry out computations in, modular arithmetic: congruence, operations on congruence classes, modular exponentiation, Euler's phi-function, Euler's Theorem, and Fermat's Little Theorem.

8. Explain the RSA method for public-key cryptography and illustrate it by carrying out appropriate computations.

9. State, prove and apply the general inclusion-exclusion principle, Vandermonde's convolution, the multinomial theorem, and generating function techniques; apply those principles together with the more basic ones to applied counting problems.

10. State, prove and apply several graph-theoretic theorems and algorithms to problems involving colorings, paths, cycles and circuits, shortest paths, minimum weight spanning tree, and other graph properties.

11. State the definitions of Big-O, little-o and Big-Omega notation, describe the structure of the Big-O quasi-ordering, and use these concepts to analyze the complexity of several algorithms such as basic searching and sorting algorithms, graph algorithms, and the Euclidean algorithm.

Assessment of Learning Objectives

Students' progress toward attaining the learning objectives is assessed continually throughout the course by means of homework assignments, in-class exams, take-home exams, and class participation. Because of the complexity of the material, take-home exams tend to be used more than in-class ones.

• Homework problems include a few ``routine" problems designed to check students' mastery of the basic ideas, but the majority of the problems require a higher level of critical thinking in applying those ideas to new situations, and there are frequent challenge problems that require considerable originality and insight to extend the ideas themselves in new directions. Students are expected to have developed basic mathematical writing skills in M 187, and to refine those skills further in this course.

• Problems given on take-home exams are generally similar to homework problems, requiring critical thinking, careful exposition, and considerable time. Students are graded on clarity and presentation as well as mathematical correctness.

• Problems given on in-class exams are less complex, reflecting the limited time available. Standards for presentation are not as stringent, and problems often are given in multiple-choice or short answer format. However, these problems still require analysis and critical thinking; they are never simply ``regurgitation" questions.

• Assessment of students' learning through in-class participation usually does not factor into their grades, but it does provide both the students and the instructor with ongoing, real time feedback as to whether the objectives are being attained.

Topics and Approximate Timeline

The following table is based on a typical semester schedule-60 class meetings of 50 minutes each. The actual amount of time spent on each topic will vary slightly from semester to semester and instructor to instructor.

Text

Discrete and Foundational Mathematics, Steve Grantham, unpublished manuscript in progress.

Format, Student Activities, and Grades

Class meetings involve a combination of lecture, questions and discussion, and sometimes small group activity; the instructor chooses the appropriate mix. Homework is an important part of the course; students sometimes do homework in teams. Exams are often partially or wholly take-home, especially those dealing with more complex material. The instructor chooses the exact grading scheme, but a typical distribution would be: