Final Exam Information - ICS 6D - Winter, 2024 (Dillencourt)

FOR GENERAL INFORMATION ABOUT TEST RULES AND THE TEST FORMAT, CLICK HERE.

Test coverage

The Final exam will cover the material material covered in the readings and slides listed below. The test is cumulative, with somewhat more emphasis on the newer topics (i.e., the topics that come after the topics covered on Test 3.) This means that a given newer topic has a higher likeliheed of being covered that an given topic from the earlier material but any topic on the list is fair game for an exam question. Test 3 covered up through Section 10.10 and up through Slide 67 of the Chapter 10 notes, so the newer topics beging after that.

• Zybook readings:
  • Chapter 1: Logic
    • Section 1.1: Propositions and logical operations
    • Section 1.2: Evaluating compound propositions
    • Section 1.3: Conditional statements
    • Section 1.4: Logical equivalence
    • Section 1.5: Laws of propositional logic
    • Section 1.6: Predicates and quantifiers
    • Section 1.7: Quantified statements
    • Section 1.8: DeMorgan;s law for quantified statement
  • Chapter 3: Sets
    • Section 3.1: Sets and subsets
    • Section 3.2: Sets of sets
    • Section 3.3: Union and intersection
    • Section 3.4: More set operations
    • Section 3.5: Sed identities
    • Section 3.6: Cartesian products
    • Section 3.7: Partitions
  • Chapter 4: Functions
    • Section 4.1: Definitions of functions
    • Section 4.2: Floor and ceiling functions
    • Section 4.3: Properties of functions
    • Section 4.4: The inverse of a function
    • Section 4.5: Composition of functions
    • Section 4.6: Logarithms and exponents
  • Chapter 8: Induction and Recursion
    • Section 8.1: Sequences
    • Section 8.2: Recurrence relations
    • Section 8.3: Summations
    • Section 8.4: Mathematical induction
    • Section 8.5: More inductive proofs
    • Section 8.6: Strong induction and will-ordering
      • The material on well-ordering (from Figure 8.6.4 on) will not be covered on the test
    • Section 8.8: Recursive definitions
    • Section 8.9: Structural induction
    • Section 8.10: Recursive algorithms
    • Section 8.11: Induction and recursive algorithms
    • Section 8.15: Solving linear non-homogeneous recurrence relations
  • Chapter 9: Integer Properties
    • Section 9.1: The division algorithm
    • Section 9.2: Modular arithmetic
    • Section 9.3: Prime factorizations
    • Section 9.4: Factoring and primality testing
    • Section 9.5: Greatest common denominator and Euclid's algorithm
    • Section 9.6: Number representation
    • Section 9.7: Fast exponentiation
    • Section 9.8: Introduction to cryptography
    • Section 9.9: The RSA cryptosystem
      • You are not expected to memorize the RSA algorithm. You should be sufficiently familiar with it that if you are given the pseudocode you can apply it. For example, given the pseudocode and two chosen primes p and q, you should be able to compute the public and private keys.
  • Chapter 10: Introduction to Counting
    • Section 10.1: Sum and product rules
    • Section 10.2: The bijection rule
    • Section 10.3: The generalized product rule
    • Section 10.4: Counting permutations
    • Section 10.5: Counting subsets
    • Section 10.6: Subset and permutation examples
    • Section 10.7: Counting by complement
    • Section 10.8: Permutations with repetitions
    • Section 10.9: Counting multisets
    • Section 10.10: Assignment problems: Balls in bins
    • Section 10.11: Inclusion-exclusion Principle
  • Chapter 11: Advanced Counting
    • Section 11.1: Generating permutations and combinations
    • Section 11.2: Binomial coefficients and combinatorial identities
    • Section 11.3: The pigeonhole principle
  
  
• Class lecture notes/slides:
  • Chapter 1 Notes: All slides
  • Chapter 3 Notes: All slides
  • Chapter 4 Notes: All slides
  • Chapter 8 Notes: Slides 1 through 88
    • Slides 44 and 45 will not be covered
    • Slides 89 and 90 will not be covered
  • Chapter 9 Notes: All slides
  • Chapter 10 Notes: Slides 1 through 83
    • Slide 84 will not be covered
  • Chapter 11 Notes: Slides 1 through 41
    • Slides 42 through 59 will not be covered