CMPSC 360: Discrete Mathematics For Computer Science

Textbook Information

  • Students need to purchase the online package for the text by Kenneth H. Rosen, Discrete Mathematics and Its Applications (8th edition) on McGraw Hill Connect

Published Remarks

  • None

Hardware Requirements

  • None

Software Requirements

  • None

Proctored Exams

  • None

Course Description

This course is designed to teach students how to think mathematically. Students will learn a particular set of mathematical facts and how to apply them.

Prerequisite or Concurrent:  CMPSC122

You must have passed the prerequisites before you take this course or are enrolled in the concurrent courses. Please understand that misrepresentation of the facts in this matter is an act of academic dishonesty, and will subject to possible failure in the course (see Policies and Rules for Students, Section 49-20).

 

 

Overview

CMPSC 360 Discrete mathematics is mathematics that deals with discrete objects. Discrete objects are those which are separated from (not connected to/distinct from) each other. Integers. We will study objects such as propositions, sets, integers, relations, and functions, which are all discrete. We are going to learn concepts associated with them, their properties, and relationships among them among others.

Objectives

By the end of this course, students will be expected to demonstrate competency in the following areas:

  • Show how to construct and apply logical inference.
  • Present logical arguments that establish mathematical statements in the form of clear proofs
  • Apply the operations of sets and solve problems by using Venn diagrams and the principle of inclusion-exclusion
  • Perform function operations, and apply the properties of functions to application problems.
  • Compute the sum of a finite sequence, and express sequences in terms of recursive or non-recursive forms.
  • Analyze simple algorithms and compare two algorithms based on computational complexity.
  • Use elementary number theory including the divisibility properties of numbers to determine prime numbers and composites, the greatest common divisor, and the least common multiple; Perform modulo arithmetic and computer arithmetic.
  • Identify the base step and the recursive or inductive step in applied problems and give a recursive and non-recursive definition for an iterative algorithm.
  • Solve problems using recurrence relations and recursion to analyze algorithms and programs
  • Solve counting problems by applying elementary counting techniques using the product and sum rules, permutations, combinations, the pigeon-hole principle, and binomial expansion.
  • Describe binary relations, N-ary relations and apply basic database operations
  • Recognize and distinguish different graphs and represent a graph using different data structures
  • Apply graph theory to application problems such as computer networks.
  • Identify the properties of a tree and apply a spanning tree.
  • Evaluate Boolean functions and simplify an expression using the properties of Boolean algebra
  • Use finite-state machines to model computer operations

Contents:

Module 1:Discrete Math Introduction; Propositional logic; Propositional Equivalence Module 2:Predicates & Quantifiers; Nested Quantifiers; Rules of Inference Module 3: Methods of proof; Sets and Set Operations Module 4: Functions; Sequence and Summations Module 5:Algorithms; The Growth of Functions; Complexity of Algorithms Module 6: Divisibility and Modular Arithmetic; Integer Representations and Algorithms; GCD and LCM Module 7: Mathematics Induction; Recursion; Recursive Algorithms Module 8: Counting Techniques; Permutations and Combinations; Binomial Coefficients and Identities; Module 9: Relations and their properties: Representing Relations; Equivalence Relations Module 10: Introduction to Graphs, Graph Models; Graph terminology and special types of Graph; Representing graphs & graph isomorphism Module 11: Connectivity; Euler and Hamilton Paths; Planar graphs Module 12: General Trees; Tree Applications Module 13: Boolean Functions; Representing Boolean Functions Module 14: Language and Grammars; Finite-State Machine Module 15: Language Recognition

Outcomes

This course supports the following ABET computer science outcome:

  • (#1) Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions.

This course supports the following ABET software engineering outcome:

  • (#1) an ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics.

Course Requirements and Grading

Your grade for the course will be determined by the points earned.  The following grading scale* from totals will be used:

>= 94% A
>= 90% A-
>= 87% B+
>= 84% B
>= 80% B-
>= 77% C+
>= 70% C
>= 60% D
>= 0% F

Rounding is pre-calculated into the point scale.  A score of 93.99 is an A-, not an A. Students must bring grading issues to the attention of the instructor by discussing the scoring within one week of hours of receipt of the graded work.

Assignment Percentages
Quizzes 18%
Homework Assignments 22%
Exam x 3 36%
Reading Assignments 18%
Participation 6%
Total 100%

Exams and Quizzes: 

There are fifteen quizzes, two midterms and a final exam. All quizzes and exams are announced prior to the testing period [see course schedule on Canvas]. Makeup exams are only offered to those with documented excuses who have granted pre-approved permissions, so that alternate arrangements may be made. There are no make-ups for quizzes!

Assignments

There will be 14 homework assignments, 14 quizzes total, and 3 reading assignments each week.  No Late submission will be accepted. All assignments are due the following Sunday at 11:59 PM, which means that you have approximately one week to work on your assignments. Assignments are to be completed and submitted in Connect by the posted deadlines in the course schedule. You are responsible for assuring that the items are properly submitted. Once the dropbox closes, no submissions will be accepted except for the those who have granted pre-approved extensions. Participation Prompt and regular online participation is required to successfully complete this course. The lessons are cumulative; therefore, it is imperative that students stay current with their course work and assignments. In addition, forum Discussions on Canvas are encouraged. The points are assessed by the proportion of the statistics automatically recorded of accessing teaching materials for each student on Canvas and activities on Canvas and Connect such as the time spent on the contents, the number of posts viewed, and the number of posts contributed. The decision on participation rests solely with the instructor. Please do NOT request the instructor for this participation credit.