14:332:312 Discrete Mathematics

Course catalog description: An application-driven course based upon the study of events that occur in small, or discrete, segments in business, industry, government and the digital world.  The student will be introduced to the mathematical tools of logic and set theory, combinatorics, number theory, and graph theory.  Practical applications will be introduced throughout the course.                

Credits and contact hours: 3 credits; 1 hour and 20-minute session twice a week, every week

Pre-Requisite courses: 14:332:226 and 14:332:231  

Co-Requisite courses: None

Topics Covered:

  • Review of Logic Statements 
  • Logic Statements and Connectives, Quantifiers and Logic word problems
  • Combinatorial Circuits
  • Boolean Algebra         
  • Fundamentals of Set Theory
  • Set Operations: union, intersection, complement, difference; Proofs
  • Membership Tables and Venn Diagrams
  • Permutations, combinations, Counting Principles
  • Probability, Independence, Bayes’ Theorem
  • Prime Numbers and cryptography 
  • Divisibility and Euclidean Algorithm; Modular Arithmetic, congruence
  • Concepts in Graph Theory; Euler Circuits and Path; Fleury’s Algorithm; Example Applications (such as Seven Bridges of Konigsberg; Chinese Postman Problem; Instant Insanity; Three Houses-Three Utilities Problem); digraphs
  • Hamilton Circuits and Paths; Gray Codes; Traveling Salesman Problem; Nearest-Neighbor Algorithm; Cheapest-Link Algorithm; RNA Chains; Tournaments
  • Planar Graphs and Coloring; Circuit Testing and Facilities Design
  • Trees and Networks; Kruskal’s Algorithm; Steiner Points and Shortest Networks; One-Way Street Problem

Textbook: Kenneth H. Rosen, Discrete Mathematics and It’s Applications, McGraw-Hill.