MATH 280 Discrete Mathematical Structures Test 3 Study Guide

The material presented in this guide covers the concepts emphasized on the final examination. It is meant to guide students studying and reviewing for the final exam; it is not guaranteed to be comprehensive. Actual test questions will differ from the examples given here. Students should use this guide in addition to other study activities (like re-reading Chapters 7, 8, 9, 10, 11, and 14, handouts, reviewing completed assignments, , quizzes, videos, etc.)

Things to know:

• Functions:
  • properties (injective, surjective, bijective)
  • functional composition
  • inverse functions
  • countability (countable vs. uncountable sets)

• Recurrence relations:
  • solving simple recurrence relations
  • proving solution correct via mathematical induction

• Mathematical structures:
  • binary operations
  • semigroups
  • monoids
  • groups
  • homomorphisms

• Properties of binary operations:
  • associativity
  • commutativity
  • identity
  • idempotence
  • invertibility

• Basic graph theory:
  • representations and applications,
  • terminology
  • trees
  • isomorphisms

• Graph algorithms:
  • Huffman encoding,
  • Dijkstra's shortest path algorithm

• Coding theory:
  • group codes
  • Hamming distance
  • single error correction group codes
  • canonical parity check matrices

• Modeling computation and languages:
  • deterministic finite automata
  • regular sets
  • regular expressions
  • context-free grammars and languages
  • parse trees
  • recursive descent parsing
  • Turing machines
  • Church-Turing thesis
  • Halting problem
  • classes of grammars