# 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