CIS*2130 - Discrete Mathematics for Computer Science
Course DescriptionThis course provides a foundation in finite mathematics which is required for further computer science courses. Topics which will be studied include abstract representation of structures and algorithms, graph theory, logic, and set theory.
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.
- 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
Restriction(s): Entry into the Pathways program for the Computer Science major in the BCOMP program.
Assignments (best 10 out of 11)
On Campus Final Exam
You are responsible for ensuring that your computer system meets the necessary system requirements. Use the browser check tool to ensure your browser settings are compatible and up to date (results will be displayed in a new browser window).
*Course details are subject to change.