Print Page

Credit hours

3 credits

Prerequisites

MATH 1200 or 1200C/0200C with a grade of C or better

Course Description

This course provides an introduction to the mathematical tools used in computing and to formal methods of reasoning for computing. Topics will include propositional logic, basic level mathematical proofs, elementary number theory, counting, graphs, and linear algebra. There will be an emphasis on application problems related to computing. 

Course Objectives

1. Introduce students, particularly those on a computer science pathway, to logic, induction, modular arithmetic, and graph theory.
2. Develop problem solving strategies and critical thinking skills for computer science students.
3. Enhance the use of proper mathematical terminology and communication of essential topics in computing.

Learning Outcomes

1. Understand and use proper mathematical terminology and symbols to solve problems and communicate solutions. 
2. Construct truth tables of logical statements involving conjunction, disjunction, negation, conditionals, and biconditionals.
3. Utilize induction and mathematical logic to prove basic statements about discrete mathematical concepts. 
4. Perform calculations using modular arithmetic. 
5. Perform basic operations on vectors, matrices, and systems of linear equations.  
6. Use graph theory concepts to solve concrete real-world problems. 
7. Apply course material to essential topics in computing. 

Course Topics

I. Speaking Mathematically

1. The Language of Sets
2. The Language of Relations and Functions
3. The Language of Graphs

II. The Logic of Compound Statements

1. Logical Form and Logical Equivalence
2. Conditional Statements
3. Valid and Invalid Arguments
4. Predicates and Quantified Statements   

III. Elementary Number Theory and Methods of Proof

1. Direct Proof and Counterexample VI: Floor and Ceiling

2. Indirect Argument: Contradiction and Contraposition

3. Application: The Handshake Theorem

IV. Sequences, Mathematical Induction, and Recursion

1. Sequences

2. Mathematical Induction I: Proving Formulas

3.  

   Mathematical Induction II: Applications

4.  

   Defining Sequences Recursively

5.  

   Solving Recurrence Relations by Iteration

6. General Recursive Definitions and Structural Induction

V. Properties of Functions  

1. Functions Defined on General Sets
2. One-to-One, Onto, and Inverse Functions

VI. Properties of Relations

1. Relations on Sets
2. Equivalence Relations
3. Modular Arithmetic with Applications to Cryptography

VII. Counting and Probability

1. Possibility Trees and the Multiplication Rule
2. Counting Elements of Disjoint Sets: The Addition Rule
3. Counting Subsets of a Set: Combinations

VIII. Theory of Graphs and Trees

1. Trails, Paths, and Circuits
2. Matrix Representations of Graphs

3. Trees: Examples and Basic Properties

4. Spanning Trees and a Shortest Path Algorithm

Print Page