FIT1058 Cheatsheet · Foundations of Computing

0 · Exam MapCOURSE · BRIEF

Quizzes 10% · Assignment 1 10% · Mid-semester test 15% · Assignment 2 25% · Final assessment 40%

Permitted materials: not confirmed for this offering in the course materials we hold — check the exam instructions on the LMS.

The final is an examination-period assessment. Operational details remain controlled by the current institutional instructions.

1 · Universal Answer PathCOURSE STRATEGY

What a complete line earns

Definition: identify the object and its declared universe or domain. Translation: separate quantities supplied by the prompt from quantities derived. Operation: write the rule before substituting. Justification: preserve direction, indices and conditions line by line. Stress-test: try the boundary, negation or a counterexample. Interpretation: answer in the language of the prompt, not merely with a symbol or number.

The final rewards the same transferable discipline across topics: declare → translate → choose → justify → test → conclude. If a later line fails, repair the first unsupported move rather than copying a complete solution.

Exam cue Marks are lost when natural language, symbols and proof drift apart. Definitions do the checking.

2 · Sets & Inclusion–ExclusionC1

Set: well-defined collection of distinct objects. Subset: every element of one set belongs to another. Power set: all subsets, including ∅ and the set itself.

Two-set inclusion–exclusion|A ∪ B| = |A| + |B| − |A ∩ B|
Subtract the intersection once: it was counted in both cardinalities.

Control the universe, finiteness and disjointness assumptions. A numerical answer without those conditions can invoke the wrong counting identity.

3 · Functions & RelationsC2

Function: each domain element is assigned exactly one codomain element. Injective: distinct domain inputs map to distinct outputs. The declared domain and codomain control injectivity and surjectivity.

Composition(g ∘ f)(x) = g(f(x))
Apply f first, then g; the intermediate codomain/domain must be compatible.

An equivalence relation is reflexive, symmetric and transitive; therefore it partitions a set. To earn the conclusion, check all three laws for arbitrary eligible elements—not only examples.

4 · Pick the Proof MethodC3

Induction checkpointBase: verify P(first index).
Hypothesis: assume P(k) for an arbitrary eligible k.
Step: use that assumption to prove P(k+1).
Conclusion: the stated range follows.

P(k) ⇒ P(k+1) is not enough alone. Checking several cases, asserting the hypothesis, or restating the target does not prove a universal statement.

Induction line-by-line

Write the first eligible index and verify it. State the induction hypothesis exactly, including its range. In the step, begin with the P(k+1) expression and show where P(k) is used; do not assume the line being proved. Finish by stating that the base case and implication cover the declared range.

5 · Proof Quality AuditC3 FAQ

6 · Propositional LogicC4

Proposition: a declarative statement assigned a truth value. Logical equivalence: expressions match under every valuation. Normal form: a standardised form such as conjunctive or disjunctive normal form.

Implication eliminationp → q ≡ ¬p ∨ q
The implication is false only when p is true and q is false.

Do not swap implication, converse and biconditional. Their truth conditions differ even if the same propositions appear.

7 · Predicates & QuantifiersC5

Predicate: an open statement whose truth depends on variables from a declared domain. ∀ claims every object; ∃ claims at least one object.

Quantifier negation¬∀x P(x) ≡ ∃x ¬P(x)
A universal claim fails exactly when a counterexample exists in the declared domain.

Moving or swapping quantifiers can change meaning even when the same predicates appear. Write the domain beside the first translation.

8 · Sequences & SeriesC6

Sequence: a function from an ordered integer index set to values. A recurrence relation defines terms from earlier terms plus initial conditions. A geometric series has a constant ratio.

Finite geometric sumΣ from i=0 to n−1 of arⁱ = a(1−rⁿ)/(1−r)

Count terms separately from reading the largest exponent. Off-by-one indexing or a missing initial value defines a different sequence.

Fast verification: expand the first two or three terms from the stated index and compare them with the prompt. For a recurrence, confirm every required initial condition before generating a later term. For a geometric sum, identify a, r and n independently; only then substitute.

9 · Combinatorial CountingC7

The multiplication principle multiplies options at sequential independent stages. A permutation is ordered; a combination is an unordered selection of fixed size.

CombinationC(n,k) = n!/[k!(n−k)!]

Then ask: repetition? exclusions? overlap? Never divide or multiply by factorials without identifying the symmetry; that is the source’s stated over-/under-counting trap.

10 · Number TheoryC8

Divisibility: a divides b when b = ak for some integer k. The greatest common divisor is the largest positive integer dividing both. Congruence: equal integer remainders modulo a positive modulus.

Euclidean recurrencegcd(a,b) = gcd(b, a mod b)
Repeat until remainder 0; take the last non-zero remainder.

Modular cancellation is conditional. Division and cancellation rules over integers do not always transfer unchanged modulo composite numbers.

11 · Discrete ProbabilityC9

Sample space: all outcomes in the model. Conditional probability: restrict attention to cases where another event occurs. Independence: learning one event does not change the probability of the other.

Bayes’ ruleP(A | B) = P(B | A)P(A) / P(B)

12 · Graphs & TreesC10

A graph is vertices plus edges under a stated convention. A path obeys its movement rules. A tree is connected and acyclic; equivalently, every vertex pair has a unique simple path.

W1 · Inclusion–ExclusionC1 WORKED

Prompt. 28 coding students, 19 robotics students, 7 in both. How many are in at least one?

1. Name sets C and R.
2. Use |C ∪ R| = |C| + |R| − |C ∩ R|.
3. Compute 28 + 19 − 7 = 40.
4. Audit: 21 only coding + 7 both + 12 only robotics = 40.

Answer40 students are in at least one club.

Trap 28 + 19 = 47 double-counts the seven students in the intersection.

Rapid Set / Relation ChecksC1–C2

Relation audit: divisibility by 3

On integers define a~b when 3 divides a−b. Reflexive: a−a=0 is divisible by 3. Symmetric: if 3 divides a−b, it also divides b−a. Transitive: if 3 divides a−b and b−c, it divides their sum a−c. Therefore the relation is reflexive, symmetric and transitive and partitions the integers into three residue classes.

Use arbitrary integers throughout. Checking 1~4 or 2~5 illustrates the rule but does not prove a relation law.

W2 · Direct ProofC3 WORKED

Prompt. Prove: if n is odd, then n² is odd.

1. Let n = 2k + 1 for integer k.
2. n² = (2k + 1)² = 4k² + 4k + 1.
3. n² = 2(2k² + 2k) + 1.
4. Since 2k² + 2k is an integer, n² has the form 2m + 1.

AnswerTherefore n² is odd by the definition of odd.

Logic & Quantifier DrillsC4–C5 WORKED

Proof and logic failure modes

Self-test: cover the answer column. For each faulty move, explain whether it is a translation, calculation or interpretation error, then write the first corrected line. Repair the earliest failure.

Trap Negating words but leaving ∀/∃ unchanged changes the intended statement incorrectly.

W3 · Geometric SumC6 WORKED

Prompt. Find 1 + 2 + 4 + … + 2⁹.

1. Recognise a = 1, r = 2.
2. Indices 0 through 9 give n = 10 terms.
3. Apply a(1−rⁿ)/(1−r).
4. (1−2¹⁰)/(1−2) = 2¹⁰−1 = 1023.

Answer1023

Counting Judgement CardsC7

Trap 8×7×6 counts the same three-person team in multiple orders; the combination denominator removes that symmetry.

Changed-scenario checks

For the series, change only the last exponent and recount the indices before touching the formula. For the team prompt, ask whether roles are introduced: once outcomes are distinguished by role, the “order does not matter” decision must be reconsidered. For either problem, state the object being counted or summed before choosing notation.

W4 · Euclid’s AlgorithmC8 WORKED

Prompt. Find gcd(252,105).

1. 252 = 2×105 + 42.
2. 105 = 2×42 + 21.
3. 42 = 2×21 + 0.
4. The last non-zero remainder is 21.

Answergcd(252,105) = 21

Audit 21 divides 252 and 105. Every remainder step preserves the common-divisor set.

Modular & Relation TrapsC2 · C8

Euclid self-checks

At every line, the dividend equals quotient×divisor + remainder. The remainder must be smaller than the divisor. When the remainder reaches zero, the current divisor—not zero—is the gcd. Verify the reported gcd divides both original integers.

Congruence discipline: retain the positive modulus beside the statement, translate congruence into equality of remainders, and resist importing ordinary division or cancellation without checking that it remains valid for the modulus. Composite moduli are the stated warning case.

W5 · Bayes / Base RateC9 WORKED

Prompt. 1% of files are malicious. A detector catches 90% of malicious files and falsely flags 5% of benign files. Find P(malicious | flag).

1. Malicious and flagged: 0.01×0.90 = 0.009.
2. Benign and flagged: 0.99×0.05 = 0.0495.
3. Total flagged: 0.009 + 0.0495 = 0.0585.
4. Posterior: 0.009 / 0.0585 ≈ 0.154.

AnswerP(malicious | flag) ≈ 15.4%

Trap P(flag | malicious)=90% is not P(malicious | flag). The base rate changes the denominator.

Graph Rapid CheckC10 WORKED

Claim. A connected undirected graph has 9 vertices and 8 edges. Is it necessarily a tree?

Answer: yes, under the stated undirected graph convention: n=9 and m=8=n−1, while connectivity excludes separate cyclic and isolated structure. Never use the edge count without the stated condition.

Graph audit order: declare directed or undirected, then loops/parallel edges/weights, then test the requested property. The theorem comes after the convention.

Method ChooserC1–C10

Classic TrapsALL FAQ

• Domain omitted: truth, function properties and quantifiers become ambiguous.
• Evidence mistaken for proof: checked examples do not establish a universal.
• Converse drift: proving Q→P does not prove P→Q.
• Index drift: exponent 9 can coexist with ten terms when indexing begins at 0.
• Counting by reflex: factorials appear before order and symmetry are defined.
• Conditional reversal: likelihood is reported as posterior.
• Graph convention omitted: a theorem is applied despite directedness, loops, parallel edges or weights.

Exam-Morning PlanCOURSE STRATEGY