CATALOG DESCRIPTION: |
|
Fundamental mathematical concepts and algebraic structures used in theoretical areas of computer science. Topics include sets, relations, functions, mathematical induction, Boolean algebra, Karnaugh maps, introduction to the theory of trees and graphs and combinatorics. The course emphasizes applications of the topics.
Prerequisite: One programming language and either MAT 142 or MAT 151 or higher level math course.
|
LEARNING OBJECTIVES: |
Upon completion of this course, the student will be able to:
- Use the notation specific to sets, logic, summation, functions, and matrices.
- Recognize properties of functions and relations.
- Construct direct and indirect proofs.
- Construct proofs by mathematical induction.
- Solve counting problems using permutations and combinations.
- Solve graph theory problems involving shortest path and minimum spanning trees.
- Simplify Boolean expressions using Karnaugh maps.
|
COURSE OUTLINE: |
Foundations: Logic, Sets, and Functions:
- Logic - propositions, conjunctions, equivalences
- Logic - predicates and quantifiers
- Methods of proof
- Sets and set operations
- Functions
Fundamentals: Algorithms, Integers, Matrices:
- Algorithms
- Growth of functions, big-O notation
- Complexity of algorithms
- Integers - algorithms, modular arithmetic
- Matrices, matrix multiplication
Proof Techniques:
- Proof strategy
- Sequences and summation
- Mathematical induction
- Recursive definitions of functions, sets
Counting:
- Basics. Pigeonhole principle
- Permutations and combinations
- Recurrence relations; solving recurrence relations
- Inclusion/exclusion; applications
Relations:
- Properties
- Equivalence relations
- Partial order relations
Graph Theory (select 5 sections from those listed below):
- Introduction; terminology
- Representing graphs, isomorphisms
- Connectivity
- Euler and Hamilton paths
- Shortest path problems
- Trees: introduction, application
- Trees: spanning and minimum spanning
Boolean functions:
- Introduction
- Logic gates; Karnaugh Maps
|
