MATH 280 Discrete Mathematical Structures Test 2 Study Guide
The material presented in this guide covers the concepts emphasized on
Test 2. It is meant to guide students studying and reviewing for Test 2;
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 6–11, and 14, reviewing completed assignments,
worksheets, quizzes, etc.)
Things to know:
- Relations: properties
(reflexive, symmetric, antisymmetric, transitive),
partially ordered sets, equivalence relations, Hasse diagrams
- Functions: properties (injective, surjective,
bijective), functional composition, inverse functions
- 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
- Modeling computation and languages:
deterministic finite automata, regular sets,
regular expressions,
context-free languages, parse trees
- Coding theory: group codes, Hamming distance, single error
correction group codes, canonical parity check matrices
There will be no questions about Turing machines on the test.