Skip to main content
Logo image

Applied Discrete Structures

Appendix D Hints and Solutions to Selected Exercises

For the most part, solutions are provided here for odd-numbered exercises.

1 Set Theory
1.1 Set Notation and Relations
1.1.3 Exercises

1.2 Basic Set Operations
1.2.4 Exercises

1.3 Cartesian Products and Power Sets
1.3.4 Exercises

1.4 Binary Representation of Positive Integers
1.4.3 Exercises

1.5 Summation Notation and Generalizations
1.5.3 Exercises

2 Combinatorics
2.1 Basic Counting Techniques - The Rule of Products
2.1.3 Exercises

2.2 Permutations
2.2.2 Exercises

2.3 Partitions of Sets and the Law of Addition
2.3.3 Exercises

2.4 Combinations and the Binomial Theorem
2.4.4 Exercises

3 Logic
3.1 Propositions and Logical Operators
3.1.3 Exercises

3.2 Truth Tables and Propositions Generated by a Set
3.2.3 Exercises

3.3 Equivalence and Implication
3.3.5 Exercises

3.4 The Laws of Logic
3.4.2 Exercises

3.5 Mathematical Systems and Proofs
3.5.4 Exercises

3.6 Propositions over a Universe
3.6.3 Exercises

3.7 Mathematical Induction
3.7.4 Exercises

3.8 Quantifiers
3.8.5 Exercises

3.9 A Review of Methods of Proof
3.9.3 Exercises

4 More on Sets
4.1 Methods of Proof for Sets
4.1.5 Exercises

4.2 Laws of Set Theory
4.2.4 Exercises

4.2.4.5. Hierarchy of Set Operations.

4.3 Minsets
4.3.3 Exercises

4.4 The Duality Principle
4.4.2 Exercises

5 Introduction to Matrix Algebra
5.1 Basic Definitions and Operations
5.1.4 Exercises

5.2 Special Types of Matrices
5.2.3 Exercises

5.2.3.5. Linearity of Determinants.

5.3 Laws of Matrix Algebra
5.3.3 Exercises

5.4 Matrix Oddities
5.4.2 Exercises

6 Relations
6.1 Basic Definitions
6.1.4 Exercises

6.2 Graphs of Relations on a Set
6.2.2 Exercises

6.3 Properties of Relations
6.3.4 Exercises

6.4 Matrices of Relations
6.4.3 Exercises

6.5 Closure Operations on Relations
6.5.3 Exercises

7 Functions
7.1 Definition and Notation
7.1.5 Exercises

7.2 Properties of Functions
7.2.3 Exercises

7.3 Function Composition
7.3.4 Exercises

8 Recursion and Recurrence Relations
8.1 The Many Faces of Recursion
8.1.8 Exercises

8.2 Sequences
8.2.3 Exercises

8.3 Recurrence Relations
8.3.5 Exercises

8.4 Some Common Recurrence Relations
8.4.5 Exercises

8.5 Generating Functions
8.5.7 Exercises

9 Graph Theory
9.1 Graphs - General Introduction
9.1.5 Exercises

9.2 Data Structures for Graphs
9.2.3 Exercises

9.3 Connectivity
9.3.6 Exercises

9.4 Traversals: Eulerian and Hamiltonian Graphs
9.4.3 Exercises

9.5 Graph Optimization
9.5.5 Exercises

9.6 Planarity and Colorings
9.6.3 Exercises

10 Trees
10.1 What Is a Tree?
10.1.3 Exercises

10.2 Spanning Trees
10.2.4 Exercises

10.3 Rooted Trees
10.3.4 Exercises

10.4 Binary Trees
10.4.6 Exercises

11 Algebraic Structures
11.1 Operations
11.1.4 Exercises

11.2 Algebraic Systems
11.2.4 Exercises

11.3 Some General Properties of Groups
11.3.3 Exercises

11.4 Greatest Common Divisors and the Integers Modulo \(n\)
11.4.2 The Euclidean Algorithm

11.4.6 Exercises

11.5 Subsystems
11.5.5 Exercises

11.6 Direct Products
11.6.3 Exercises

11.6.3.3. Algebraic properties of the \(n\)-cube.

11.7 Isomorphisms
11.7.4 Exercises

12 More Matrix Algebra
12.1 Systems of Linear Equations
12.1.7 Exercises

12.2 Matrix Inversion
12.2.3 Exercises

12.3 An Introduction to Vector Spaces
12.3.3 Exercises

12.4 The Diagonalization Process
12.4.4 Exercises

12.5 Some Applications
12.5.5 Exercises

12.6 Linear Equations over the Integers Mod 2
12.6.2 Exercises

13 Boolean Algebra
13.1 Posets Revisited

Exercises

13.2 Lattices

Exercises

13.3 Boolean Algebras

Exercises

13.4 Atoms of a Boolean Algebra

Exercises

13.5 Finite Boolean Algebras as \(n\)-tuples of 0’s and 1’s

Exercises

13.6 Boolean Expressions

Exercises

13.7 A Brief Introduction to Switching Theory and Logic Design

Exercises

14 Monoids and Automata
14.1 Monoids

Exercises

14.2 Free Monoids and Languages

Exercises

14.3 Automata, Finite-State Machines

Exercises

14.4 The Monoid of a Finite-State Machine

Exercises

14.5 The Machine of a Monoid

Exercises

15 Group Theory and Applications
15.1 Cyclic Groups

Exercises

15.2 Cosets and Factor Groups

Exercises

15.3 Permutation Groups
15.3.5 Exercises

15.4 Normal Subgroups and Group Homomorphisms
15.4.3 Exercises

15.5 Coding Theory, Linear Codes
15.5.4 Exercises

16 An Introduction to Rings and Fields
16.1 Rings, Basic Definitions and Concepts
16.1.6 Exercises

16.2 Fields

Exercises

16.3 Polynomial Rings

Exercises

16.4 Field Extensions

Exercises

16.5 Power Series
16.5.3 Exercises