MATH 1843: Discrete Math

Download as PDF
Subject:
Mathematics
Credit hours: 3 Lecture hours: 3 Lab hours: 0
PCS code (Local ID):
Baccalaureate/Transfer
View Class Schedule
Course Description

Introduction to analysis of finite collections and mathematical foundations of sequential machines, computer system design, data structures, and algorithms. Includes sets and logic, subscripts, arrays, number systems, counting, recursion, graph theory, trees, nets, and Boolean algebra.

Prerequisite(s)

MATH 1814 with a grade of C or better or appropriate assessment score

IAI Number
CS-915
M1-905
IAI Title
Discrete Structures
Discrete Mathematics
Topical Outline
  1. First Examples of Puzzles and Patterns
  2. Number Puzzles and Sequences
  3. Truth-Tellers, Liars, and Propositional Logic
  4. Predicates
  5. Implications
  6. Validity of Arguments
  7. Mathematical Writing
  8. Proofs about Numbers
  9. Mathematical Induction
  10. Contradiction and the Pigeonhole Principle
  11. Representation of Numbers
  12. Set Definitions and Operations
  13. More Operations on Sets
  14. Proving Set Properties
  15. Boolean Algebra
  16. Logic Circuits
  17. Introduction to Combinatorics
  18. Basic Rules for Counting
  19. Combinations and the Binomial Theorem
  20. Binary Sequences
  21. Recursive Counting
  22. Solving Recurrence Relations
  23. Introduction to Probability
  24. Sum and Product Rules for Probability
  25. Probability in Games of Chance
  26. Expected Value in Games of Chance
  27. Graph Theory
  28. Isomorphism and Planarity
  29. Graphs in Puzzles and Games
  30. Binary Trees
  31. Hamilton Cycles and the TSP

At the end of this course, students will be able to:

  • Apply classical problem-solving strategies in varying circumstances
  • Use mathematical theory of discrete systems as it applies to computer programming
  • Manipulate sets, sequences, and matrices and perform corresponding operations
  • Solve basic counting and probability problems
  • Apply various methods of proof (including induction)
  • Solve problems using recursive and explicit algorithms
  • Identify the costs and benefits of recursion
  • Represent the concept of relations in various ways (matrix, ordered pairs, digraphs)
  • Apply the concept of function growth to compute and compare the complexity of simple algorithms
  • Apply several classical algorithms related to applications of trees and graphs