MATH 280 Discrete Mathematical Structures Test 2 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 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
• 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
• Modeling computation and languages: deterministic finite automata, regular sets, regular expressions, context-free grammars and languages, parse trees, recursive descent parsing,
• 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.