COSC/MATH 2300 DISCRETE MATHEMATICS

Spring semesters

Text: Discrete Mathematics and Its Applications, 5th Edition

Author: Kenneth Rosen

Publisher: McGraw-Hill

ISBN: 0-07-242434-6

Optional addition: Student Solution Guide

Course Description:

Discrete structures are widely used in computer science, both in the design and analysis of computer programs. This course teaches about the major types of discrete structures, along with important methods of mathematical reasoning about these structures. The material covered includes formal logic, set theory, functions, introductory number theory and graph theory, proofs, proof by induction, combinatorics and, if time permits, probability. The course provides an introduction to the abstract and rigorous thinking that is required in other mathematics and computer science courses.

Prerequisites:

COSC 1030 (Computer Science I) and either MATH 2200 (Calculus I) or 2350 (Business Calculus)

Tentative Lecture Schedule (open to change -- check here regularly for updates):

Students are expected to know the following material by having had the course prerequisites. This material will NOT be taught in class: The laws of arithmetic, logarithms, exponents, polynomials, and limits.

Below is a tentative list of topics to be covered during the semester. The actual list may change, depending on the needs and capabilities of the students. For each topic, the relevant textbook section and the topic title are noted. It is expected that students will have read the relevant textbook section(s) prior to each lecture. Also, note that the textbook and lecture material will overlap, but will not be identical. Students are responsible for understanding all of the material in the textbook (required sections only) and the lectures.

I. LOGICAL REASONING

• Sections 1.1-1.4. Introduction to the course; Formal logic

• Discussion of an application of formal logic: Analysis (proofs) of program correctness (Section 3.6)

  II. DISCRETE STRUCTURES: INTEGERS AND SETS

• Sections 1.6 and 1.7. Sets of discrete elements, such as integers

• Sections 1.8. Functions and relations as mappings between sets

• Section 3.2. Closed-form formulas for solving finite sums of integers and set elements

  III. PROOFS OF THE TIME COMPLEXITY OF ALGORITHMS

  This is an important application of sets, functions, and summations to be studied in computer science. We briefly introduce the topic here, and then it is studied in depth in COSC 3020.

• Section 2.1 and Appendix A.2. Algorithms and pseudocode

• Section 2.2. Growth of functions

• Section 2.3. Analysis (proofs) of the time complexity of algorithms

  MIDTERM EXAM

  IV. DISCRETE STRUCTURES: INTEGERS AND NUMBER THEORY

• Section 2.4. Integers, number theory, and cryptology as an application.

  V. DISCRETE STRUCTURES: GRAPHS AND GRAPH THEORY

• Parts of Sections 2.7 and 8.1-8.4. Graphs; Representing graphs with matrices. Brief discussion of applying graphs to represent communication/information networks.

  VI. GENERAL MATHEMATICAL REASONING: FORMAL PROOFS

• Sections 1.5 and 3.1. Proof methods and strategies. Number theory and graph theory proofs.

• Sections 3.3, 3.4 and 3.5. Inductive proofs (and the relation to recursion)

• Proofs of summation formulas

  VII. PROBABILISTIC REASONING: COMBINATORICS AND PROBABILITY

• Sections 4.1-4.3. Counting, permutations, and combinations

  The following material may be covered if time permits:

• Parts of Sections 5.1-5.3. Discrete probability, conditional probability and Bayes' Theorem.

• Discussion of an artificial intelligence (AI) application of probability and graphs: Probabilistic reasoning with graphs

  FINAL EXAM

Written Homework:

Exams:

There will be quizzes, a midterm and a final exam.

Written Reports:

One written report will be required. The topic is chosen by each student, and can be an application, biography, or other subject related to discrete math. Note that topic ideas are scattered throughout the Rosen textbook. The report should be in the form of a scholarly paper, with citations and references. The minimum length is 5 pages, not including the references. The report should be written mostly in your own words, with some quotes allowed. Plagiarism from the web, books, or any other source will result in a 0 on this assignment and may also result in failing the course.

Grading:

The various required work in this class will be counted toward your final grade as follows:

• Written homework - 30%

• Quiz on logic and sets - 5%

• Written report - 5%

• Midterm Exam - 30%

• Final exam - 30%

A standard grading scale will be used, where an overall average of 90% or above earns an A, 80% a B, 70% a C, and 60% a D. The professor reserves the right to alter the grading scheme or to take extenuating circumstances into account when assigning grades.

Academic Dishonesty:

Discussion of the course material among students is encouraged, although homework, quizzes and exams are expected to be the student's OWN work. Copying from another student (or other source) or allowing another student access to your work is strictly prohibited. Academic dishonesty will be treated in accordance with the strictest university standards. Cheating may result in an F in the course or expulsion from the university. Students are urged to read University regulation 802. Section 3 defines academic dishonesty.