FIT1058_MOC

📘 FIT1058: Foundations of Computing

Map of Content

Index for the Discrete Mathematics strand of FIT1058 — sets, functions, relations, logic & proof, sequences/series/growth. Start with Set (Mathematics).

📊 Assessment Map

• Assessment: assignments + final exam.
• Exam skills: proofs (induction, contradiction), truth tables, Euclid/modular-exponentiation traces, counting and probability derivations.

🧰 Unit Cheatsheet

• 📌 FIT1058 Unit Cheatsheet — logic → proofs → counting → probability → number theory → graphs

📅 Knowledge Index

Week 1 — Sets and Their Structure

• Set (Mathematics) → Parent Framework: Power Set
• Sets of Numbers → Parent Framework: Set (Mathematics)
• Sets of Strings → Parent Framework: Set (Mathematics)

Week 1 — Subsets and Counting

• Subset and Superset → Parent Framework: Set (Mathematics)
• Power Set → Parent Framework: Set (Mathematics)
• Binomial Coefficient → Parent Framework: Power Set

Week 1 — Set Operations

• Set Operations (Mathematics) → Parent Framework: Set (Mathematics) (union/intersection · complement/difference · symmetric difference · De Morgan)
• Cartesian Product → Parent Framework: Set (Mathematics)
• Set Partition → Parent Framework: Set (Mathematics)

Week 2 — Functions

• Function (Mathematics) → Parent Framework: Binary Relation
• Image and Codomain → Parent Framework: Function (Mathematics)
• Injection, Surjection, Bijection → Parent Framework: Function (Mathematics)
• Inverse Function → Parent Framework: Function (Mathematics)
• Function Composition → Parent Framework: Function (Mathematics)
• Counting Functions → Parent Framework: Function (Mathematics)
• Cryptosystem → Parent Framework: Function Composition

Week 2 — Relations

• Binary Relation → Parent Framework: Cartesian Product
• Properties of Binary Relations → Parent Framework: Binary Relation
• Equivalence Relation → Parent Framework: Properties of Binary Relations
• n-ary Relation → Parent Framework: Binary Relation

Week 3 — Logic and Proof

• Theorem and Proof → Parent Framework: Proof Techniques
• Logical Implication → Parent Framework: Theorem and Proof
• Modus Ponens → Parent Framework: Logical Implication
• Quantifiers (Existential and Universal) → Parent Framework: Theorem and Proof
• Finding Proofs → Parent Framework: Theorem and Proof
• Proof Techniques → Parent Framework: Theorem and Proof
• Mathematical Induction → Parent Framework: Proof Techniques

Week 4 — Propositional (Boolean) Logic

• Proposition and Truth Value → Parent Framework: Logical Connectives
• Logical Connectives → Parent Framework: Proposition and Truth Value
• Exclusive-or → Parent Framework: Logical Connectives
• Boolean Algebra Laws → Parent Framework: Logical Connectives
• Disjunctive Normal Form → Parent Framework: Boolean Algebra Laws
• Conjunctive Normal Form → Parent Framework: Boolean Algebra Laws
• Logical Modelling → Parent Framework: Conjunctive Normal Form
• Universal Sets of Operations → Parent Framework: Boolean Algebra Laws

Week 5 — Predicate (First-Order) Logic

• Predicate → Parent Framework: Binary Relation
• Term, Variable, and Constant → Parent Framework: Predicate
• Quantifiers (Existential and Universal) → Parent Framework: Theorem and Proof (extended in Week 5)
• Multiple Quantifiers → Parent Framework: Quantifiers (Existential and Universal)
• Quantifier Negation → Parent Framework: Quantifiers (Existential and Universal)

Week 6 — Sequences, Series, and Growth

• Sequence (Mathematics) → Parent Framework: Function (Mathematics)
• Recurrence Relation → Parent Framework: Sequence (Mathematics)
• Arithmetic, Geometric, and Harmonic Sequences → Parent Framework: Sequence (Mathematics)
• Fibonacci Sequence → Parent Framework: Recurrence Relation
• Limit of a Sequence → Parent Framework: Sequence (Mathematics)
• Summation Notation → Parent Framework: Sequence (Mathematics)
• Arithmetic Series → Parent Framework: Time Complexity (extended in Week 6)
• Geometric Series → Parent Framework: Summation Notation
• Big-O Notation → Parent Framework: Asymptotic Analysis (extended in Week 6)

Week 7 — Number Theory and Cryptography

• Divisibility → Parent Framework: Sets of Numbers
• Prime Number → Parent Framework: Divisibility
• Greatest Common Divisor → Parent Framework: Divisibility
• Euclidean Algorithm → Parent Framework: Greatest Common Divisor
• Integer Linear Combination → Parent Framework: Greatest Common Divisor
• Extended Euclidean Algorithm → Parent Framework: Euclidean Algorithm
• Coprimality → Parent Framework: Greatest Common Divisor
• Modular Arithmetic → Parent Framework: Divisibility (modulo operation + congruence + class arithmetic)
• Modular Inverse → Parent Framework: Modular Arithmetic
• Euler Totient Function → Parent Framework: Coprimality
• Modular Exponentiation → Parent Framework: Modular Arithmetic
• Euler’s Theorem and Fermat’s Little Theorem → Parent Framework: Euler Totient Function
• Primitive Root → Parent Framework: Euler’s Theorem and Fermat’s Little Theorem
• One-Way Function → Parent Framework: Modular Exponentiation
• Diffie-Hellman Key Agreement → Parent Framework: One-Way Function

Week 8 — Counting and Combinatorics

• Counting Principles → Parent Framework: Set (Mathematics) (addition + multiplication principles)
• Inclusion-Exclusion Principle → Parent Framework: Union and Intersection
• Selection (Counting Framework) → Parent Framework: Multiplication Principle
• Stars and Bars → Parent Framework: Selection (Counting Framework)

Week 9 — Probability

• Sample Space and Events → Parent Framework: Probability
• Probability → Parent Framework: Sample Space and Events
• Mutually Exclusive Events → Parent Framework: Probability
• Probability Rules for Events → Parent Framework: Probability
• Independent Events → Parent Framework: Probability
• Conditional Probability → Parent Framework: Probability
• Law of Total Probability → Parent Framework: Conditional Probability
• Bayes’ Theorem → Parent Framework: Conditional Probability
• Inclusion-Exclusion Principle → Parent Framework: Union and Intersection (extended in Week 9)

Week 10 — Random Variables and Distributions

• Random Variable → Parent Framework: Probability
• Expectation → Parent Framework: Random Variable
• Median and Mode → Parent Framework: Random Variable
• Variance and Standard Deviation → Parent Framework: Expectation
• Uniform Distribution → Parent Framework: Random Variable
• Binomial Distribution → Parent Framework: Random Variable (Bernoulli trial + binomial)
• Poisson Distribution → Parent Framework: Random Variable
• Geometric Distribution → Parent Framework: Bernoulli Trial
• Coupon Collector’s Problem → Parent Framework: Geometric Distribution

Week 11 — Graph Theory

• Graph → Parent Framework: Binary Relation
• Types of Graphs → Parent Framework: Graph
• Graph Representations → Parent Framework: Graph
• Subgraph → Parent Framework: Graph
• Special Graphs → Parent Framework: Graph
• Degree and the Handshaking Lemma → Parent Framework: Graph
• Walks, Trails, and Paths → Parent Framework: Graph
• Cycle (Graph Theory) → Parent Framework: Walks, Trails, and Paths
• Connectivity → Parent Framework: Graph
• Bipartite Graph → Parent Framework: Graph
• Euler Tour → Parent Framework: Walks, Trails, and Paths

Week 12 — Trees, Spanning Trees, and Planar Graphs

• Tree → Parent Framework: Data Structure (extended in Week 12: graph-theory tree)
• Forest → Parent Framework: Tree
• Spanning Tree → Parent Framework: Tree
• Kruskal’s Greedy Algorithm → Parent Framework: Spanning Tree
• Planar Graph → Parent Framework: Graph
• Euler’s Formula (Planar Graphs) → Parent Framework: Planar Graph

🧭 Suggested Reading Order

(read left→right within each week · bold = the week’s core hand skill)

• W1 — sets: Set (Mathematics) → Sets of Numbers · Sets of Strings → Subset and Superset → Power Set → Binomial Coefficient → Set Operations (Mathematics) → Cartesian Product · Set Partition
• W2 — functions & relations: Function (Mathematics) → Image and Codomain → Injection, Surjection, Bijection → Inverse Function → Function Composition → Cryptosystem · Counting Functions → Binary Relation → Properties of Binary Relations → Equivalence Relation → n-ary Relation
• W3 — proofs: Theorem and Proof → Logical Implication → Modus Ponens → Quantifiers (Existential and Universal) → Finding Proofs → Proof Techniques → Mathematical Induction
• W4 — propositional logic: Proposition and Truth Value → Logical Connectives → Exclusive-or → Boolean Algebra Laws → Disjunctive Normal Form → Conjunctive Normal Form → Logical Modelling → Universal Sets of Operations
• W5 — predicate logic: Predicate → Term, Variable, and Constant → Quantifiers (Existential and Universal) (restriction rules) → Multiple Quantifiers → Quantifier Negation
• W6 — sequences & series: Sequence (Mathematics) → Recurrence Relation → Arithmetic, Geometric, and Harmonic Sequences → Fibonacci Sequence → Limit of a Sequence → Summation Notation → Arithmetic Series · Geometric Series → Big-O Notation
• W7 — number theory: Divisibility → Prime Number → Modular Arithmetic → Greatest Common Divisor → Euclidean Algorithm → Integer Linear Combination → Extended Euclidean Algorithm → Coprimality → Modular Inverse → Euler Totient Function → Modular Exponentiation → Euler’s Theorem and Fermat’s Little Theorem → Primitive Root → One-Way Function → Diffie-Hellman Key Agreement
• W8 — counting: Counting Principles → Inclusion-Exclusion Principle → Selection (Counting Framework) (the 2×2 table) → Stars and Bars
• W9 — probability: Sample Space and Events → Probability → Mutually Exclusive Events → Probability Rules for Events → Independent Events → Conditional Probability → Law of Total Probability → Bayes’ Theorem
• W10 — random variables: Random Variable → Expectation → Median and Mode → Variance and Standard Deviation → Uniform Distribution → Binomial Distribution → Poisson Distribution → Geometric Distribution → Coupon Collector’s Problem
• W11 — graphs: Graph → Types of Graphs → Graph Representations → Subgraph → Special Graphs → Degree and the Handshaking Lemma → Walks, Trails, and Paths → Cycle (Graph Theory) → Connectivity → Bipartite Graph → Euler Tour
• W12 — trees & planarity: Tree → Forest → Spanning Tree → Kruskal’s Greedy Algorithm → Planar Graph → Euler’s Formula (Planar Graphs)

🎯 Learning Outcomes (key skills per week)

• W1 ➔
  • specify sets three ways + cardinality
  • $|\mathcal{P}(A)|=2^n$, binomials + Pascal’s identity
  • set ops incl. De Morgan
  • prove equality by double inclusion
• W2 ➔
  • classify injective/surjective/bijective + when the inverse exists
  • compose functions (socks-and-shoes inversion)
  • count functions/injections/bijections
  • relation properties → equivalence ⟺ partition
• W3 ➔
  • check a proof’s validity
  • reason with $P\Rightarrow Q$ + modus ponens (converse trap)
  • pick the blueprint: construction/cases/contradiction/manipulation
  • run induction with BOTH obligations
• W4 ➔
  • truth-table every connective
  • simplify via the Boolean laws
  • convert to DNF/CNF
  • encode rule sets as CNF
  • spot universal operation sets
• W5 ➔
  • separate free vs bound variables
  • restrict with the right connective ($\exists +\wedge$, $\forall +\Rightarrow$)
  • respect mixed quantifier order
  • negate by flipping every quantifier
• W6 ➔
  • convert recurrence ↔ closed form (explore–formulate–prove)
  • handle arithmetic/geometric/Fibonacci (Binet)
  • apply the $\epsilon$–$N$ limit definition
  • derive both series sums
  • apply Big-O from its formal definition
• W7 ➔
  • run Euclid + Extended Euclid (Bézout)
  • test coprimality ⟺ invertibility
  • compute in ${\mathbb{Z}}_n$ + modular inverses
  • shrink exponents with $\varphi (n)$/Euler/FLT
  • square-and-multiply
  • explain Diffie-Hellman + discrete log
• W8 ➔
  • choose add vs multiply by hypothesis
  • apply inclusion–exclusion
  • classify selections in the order×replacement 2×2
  • count $\sum x_i=r$ via stars and bars
• W9 ➔
  • set up sample spaces ($|A|/|U|$ needs uniform + finite)
  • apply complement/union rules
  • test independence (≠ exclusivity)
  • chain conditional → total probability → Bayes
• W10 ➔
  • define RVs + distributions
  • use $E$ linearity always, $\mathrm{Var}$ additivity only if independent
  • contrast mean/median/mode
  • deploy the five standard distributions + coupon collector
• W11 ➔
  • model with graphs + four representations
  • apply handshaking + corollaries
  • distinguish walk/trail/path/cycle + connectivity
  • test bipartite ⟺ no odd cycle
  • decide Euler tours by the degree test
• W12 ➔
  • use tree characterisations ($n-1$ edges, unique paths)
  • count forest edges ($n-k$)
  • build spanning trees + run Kruskal
  • apply $n-m+f=2$ and the planarity bounds to $K_5$/$K_{3,3}$