CSCI 2030 Mathematical Foundations for Computer Science Review Questions 1. The Foundations: Logic and Proofs 1. What is a “Proposition?” Give examples, Give counter examples. 2. What is a “Predicate?” How it differs from Proposition? 3. What is a “Truth Table?” Give examples. 4. What are logical operators? Give examples of “Compound propositions.” 5. What is the precedence of logical operators? Show examples 6. What is a “Tautology” and what is a “Contradiction?” 7. What are the “De Morgan’s Laws?” Write them out. 8. What are the “Logical Equivalences?” 9. What are the predicate quantifiers? Give examples. 10. How to translate English sentences into Logical Expressions? Show examples. 11. What is the “modus ponens” rule of inference? Show an example. 12. What are the rules of inferences? 13. How to do a “Direct Proof?” Show an example. 14. How to do a proof by “Contraposition?” Show an example. 15. How to do a proof by “Contradiction?” Show an example. 16. What are the differences between “Proof” and “Inference?” 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 1. What is the difference of “” and “” 2. What are the Set operations? 3. What are the properties of “” 4. What is P(S) and what is |P(S)|? 5. What is a relation? How is it related to Cartesian Product? 6. What is a function? What is NOT a function? 7. What is “One-to-one” function? What is “Onto” function? 8. What is “Inverse” function?9. What is “Compositions” of functions? 10. What is a “Sequence?” 11. What is a “Geometric Progression” sequence? What is a “Arithmetic Progression” sequence? 12. What are the formulas for calculating the summations of sequences? 13. What is the Transpose of a matrix? What is a Symmetric matrix? 14. What is a Zero-one matrix? What are the uses of it? 3. Algorithms 1. What is the definition of “Algorithm?” 2. What is “linear Search” and what is “Binary Search?” 3. What is “Bubble Sorting” and what is “Insertion Sorting?” 4. What is “Greedy Algorithm?” 5. What is Big-O notation 6. What is “P” “NP” and “NP-Complete” problem? 4. Number Theory and Cryptography 1. What is the “Fundamental Theory of Arithmetic?’ 2. What does “q = a div d” and “r = a mod d” mean? 3. What does “a  b (mod m)” (congruent) mean? 4. What is a “prime” number? 5. What is the “Goldbach’ Conjecture” of Prime numbers? 6. What does “gcd(a, b)” and “lcm(a, b)” mean? 5. Induction and Recursion 1. What are the two “steps” of mathematical Induction? 2. What are the two “steps” of strong induction? 3. What are the differences between “Mathematical Induction” and “Strong Induction?” 4. What are the two “steps” of Recursively defined functions?5. What are the two “steps” of Recursively defined Sets and Structures? 6. What is the definition of “Well-formed Formulae?” 6. Counting 1. What is the “Product rule” of counting? 2. What is the “Sum rule” of counting? 3. What is the “Subtraction rule” of counting? 4. What is the “Pigeonhole Principle?” Give an example of its application. 5. What is a “Permutation?” Give an example. 6. What is a “Combination?” Give an example. 8. Advanced Counting Techniques 1. What is a “Recurrence relation?” 2. How to solve Linear Homogeneous Recurrence Relations with Constant Coefficients 3. What is the “principle of Inclusion-Exclusion?” 9. Relations 1. What is a “Binary Relation?” Give an example. 2. What are the differences between a “relation” and a “function?” 3. What is the “Reflective” property of a relation? 4. What is the “Symmetric” property of a relation? 5. What is the “Antisymmetric” property of a relation? 6. What is the “Transitive” property of a relation? 7. What is an “n-ary” relation? Give an example. 8. What is the “Closure” of a relation? Give an example. 12. Boolean Algebra 1. What are the differences of a “Boolean Function” and a “Propositional Logic?”2. What is a “Sum-of-product” expansion of a Boolean function? 13. Modeling Computation 1. What are the components of a “Phrase-structure grammar?” 2. What are the types of Phrase-structure grammar? 3. What are the components of a “Finite-State Machine with Output?” 4. What are the components of a “Finite-State Machine with No Output?” 5. What does it mean that “a language is recognized or accepted? By a Finite-State Machine?” 6. What is a “Nondeterministic Finite-State Machine?” 7. What is a “Turing