CIS*2130 - Discrete Mathematics for Computer Science

Course Description

Learning Outcomes

By the end of the course, the learner should be able to:

• Explain the basic terminology of sets and functions.
• Perform basic operations associated with sets, and functions.
• Be able to relate practical examples of the appropriate set or function model and interpret the associated operations and terminology in context (this will be accomplished gradually in later weeks).
• Explain the basic terminology of relations.
• Perform basic operations associated with relations.
• Be able to relate practical examples of the relational model and interpret the associated operations and terminology in context (this will be accomplished gradually in later weeks).
• Perform basic arithmetic operations in and conversions between binary, octal, hexadecimal and decimal number systems.
• Apply formal methods of symbolic propositional and predicate logic.
• Describe how formal tools of symbolic logic are used to model real-life situations: natural language, computer circuits and logic puzzles.
• Construct truth tables for complex propositions by applying operator precedence.
• Distinguish between valid and invalid mathematical arguments.
• Apply logical equivalences to simplify compound propositions.
• Use some Boolean algebra laws to derive others.
• Apply Boolean algebra laws to manipulate and complement Boolean expressions.
• Relate Boolean algebra to circuits, logic, and sets.
• Outline the basic structure and give examples for a variety of proof methods.
• Discuss which types of proof is best for a given problem.
• Recognize monotonic, arithmetic and geometric sequences.
• Manipulate sums and apply some basic summation formulae.
• Apply induction to prove some simple propositions (mathematical statements).
• Identify the apparent difference between weak and strong induction.
• Understand the application of the Well Ordering Property.
• Apply the pigeon hole principle.
• Compute permutations and combinations and interpret the meaning in the context of the particular application.
• Discuss applications of combinatorics in computer science.
• Compute generalized permutations and combinations and interpret their meaning in the context of a particular application.
• Calculate probabilities of events and expectation for elementary problems such as games of chance.
• Illustrate the basic terminology of graph theory.
• Relate graphs to counting.
• Model computer science problems using graphs.
• Relate graphs and trees to counting.
• Model computer science problems using graphs and trees.
• Understand some important graph theoretic concepts: Hamilton and Euler path, planar graphs, graph coloring.

Course Topics

• Sets and Functions
• Relations and Integer Representations
• Propositional Logic
• Boolean Algebra
• Proof Methods
• Sequences and Summations
• Induction and Well Ordering
• Basics of Counting
• Advanced Counting and Basic Probability
• Graph Theory
• Graph Applications and Trees

Assessment