Final Exam
The final exam will cover Chapters 1, 2, 3, 5, 6, 7, 9, and X, with questions evenly distributed across these chapters. The exam consists of 100 questions, each worth 1 point.
Chapters Covered
- ★ Chapter 1: Mathematical Logic
- * Formal symbols of Propositional logic
- Proposition
- Propositional variable
- Logical Connectives
- Truth Table
- * Translating into Propositional Logic
- * Tautology
- Tautology
- Contradiction
- Tautological Equivalences
- De Morgan's laws
- * Valid Argument
- * Derivation Rules
- Equivalence rules
- Inference rules
- Deduction Method
- * Verbal Arguments
- ★ Chapter 2: Induction and Proofs
- * Proof Techniques
- Disprove
- Exhaustive Proof
- Direct Proof
- Proof by Contraposition
- Proof by Contradiction
- * Induction
- First Principle of Induction
- ★ Chapter 3: Recursion and Recurrence Relations
- * Recursive Definitions
- Recursively Defined Sequences
- Recursive Algorithm in C++
- Iterative Algorithm in C++
- * Recurrence Relations
- Linear first-order recurrence relations with constant coefficients
- Closed-form solution to the recurrence relation
- ★ Chapter 5: Matrices
- * Terminology
- Square Matrices
- Symmetric Matrix
- Identity Matrix
- Matrix Inverse
- * Matrix Operations
- Scalar Multiplication
- Matrix Addition/Subtraction
- Matrix Multiplication
- * Gaussian Elimination
- Allowable elementary row operations
- i. Switch any two rows of the matrix.
- ii. Multiply all the elements in any one row of the matrix by a non-zero scalar.
- iii. Add a scalar multiple of any one row to another row.
- Solve the System of Equations
- Create Matrix Inverse
- * Boolean Matrices
- Boolean Multiplication
- Boolean Addition
- Boolean matrix multiplication
- ★ Chapter 6: Graphs and Trees
- * Graph Basics
- Graph (Formal Definition)
- Labeled Graph
- Weighted Graph
- * Graph Terminology
- Adjacent Vertices
- Adjacent Edges
- Loop
- Parallel Arcs
- Simple Graph
- Isolated Node
- Degree of a Vertex
- Complete Graph
- Path
- Length of a Path
- Connected Graph
- Cycle
- Bipartite Complete Graph
- Isomorphism Graphs
- *Representation of Graphs
- Adjacency Matrix
- Adjacency List
- * Tree Terminology
- Tree Formal Definition
- Root
- Depth of a node
- Depth (height) of the tree
- Leaf and internal nodes
- Forest
- Binary trees
- Full binary tree
- Complete binary tree
- *Binary Tree Representation
- Left Child-Right Child Array Reprentation
- Pointer Representation
- * Tree Traversal Algorithms: Preorder, Inorder, Postorder
- * Decision Tree Searching Lower Bound
- * Decision Tree Sorting Lower Bound
- * Huffman Code
- ★ Chapter 7: Graphs and Algorithms
- * Directed Graphs
- * Adjacency/Binary Relations
- * Reachability Matrix
- * Warshall's Algorithm
- * Euler Path and Hamiltonian Circuit for undirected graph
- * Dijkstra's Algorithm
- * Depth-First Search
- * Breadth-First Search
- ★ Chapter 9: Modeling Arithmetic, Computation
- * Finite-State Machines
- State Graph
- State Table
- Input/Output Time Table
- Finite-state machines as recognizers
- Regular Sets and Kleene's Theorem
- * Turing Machines
- Quintuple
- Initial tape/Final tape
- Turing Machines as Set Recognizers
- * Halting Problem
- * Common problem definitions in Computer Science:
- P Problems
- NP Problems
- NP-Complete Problems
- NP-Hard Problems
- * Formal Languages
- Type 0
- Context-sensitive
- Context-free
- Regular
- ★ Chapter X: Binary Encoding Scheme
- * Weighted Codes
- Binary to Decimal
- BCD Code
- Self-Complementing Code
- Two's complement
- Convert a Negative Decimal Number to a Binary Number
- Converting a Binary Number to Decimal Number
- Value Ranges
- * Non-Weighted Codes
- Excess-3 Code
- Gray Code
- Binary to Gray conversion
- Gray to binary conversion
- n-bit Gray Code Generating
- * Error Detecting Codes
- Parity Bit
- Even Parity
- Odd Parity
- * Error Correcting Codes
Format
- ★ Face to Face (D2L Password Protected)
- ★ 100 Multiple Choice Questions (A,B,C,D)
- ★ Total points: 100 points
Demo Questions