Foundations & proof moves

Summations & arithmetic series

These are the first formulas the course assumes you can deploy without pausing the algorithmic story.

Tutorial 1 opens with summation notation and standard closed forms. These appear constantly when you count loop iterations, analyse resize costs, or expand recurrences.

Key identity (given on the sheet):

Warm-up uses:

• Evaluate \(\sum_{i=1}^{20} i\) by substituting \(n=20\).
• Derive \(\sum_{i=m}^{n} i\) by subtracting \(\sum_{i=1}^{m-1} i\) from \(\sum_{i=1}^{n} i\).
• Express \(\sum_{i=n}^{2n} i\) in terms of \(n\) and plug in a value (e.g. \(n=20\)).

Bonus sheet adds:

Use these to evaluate partial sums such as \(\sum_{i=5}^{10} i^2\) or \(\sum_{i=n}^{2n} i^3\) by splitting ranges.

Logs, floors, ceilings & proof templates

Tutorial 1 is really a compact toolkit for arguing cleanly about discrete objects.

Tutorial 1 lists discrete-math topics that support proofs and analyses later in the unit (Goodrich & Tamassia sections 1.2.1–1.2.3). You should be comfortable with each bullet before heavier data-structure proofs (trees, heaps, graphs).

Logarithms & exponents

Know identities such as \(\log(ab)=\log a + \log b\) (for a fixed base) and \(a^{m+n}=a^m\cdot a^n\). Be able to simplify expressions like \(\log_{10}(1000)\), \(2^3\cdot 2^4\), and \(8^{2/3}\), and to solve simple equations such as \(3^x=81\).

Floor & ceiling

\(\lfloor x\rfloor\) is the greatest integer \(\le x\); \(\lceil x\rceil\) is the smallest integer \(\ge x\). They appear when halving subproblems (\(\lfloor n/2\rfloor\)), counting levels of a recursion tree, or translating real-valued bounds to integer indices.

Proof patterns

• Counterexample — disprove a universal claim by one concrete instance.
• Contrapositive — prove \(P\Rightarrow Q\) via \(\neg Q\Rightarrow \neg P\).
• Contradiction — assume the negation of what you want and derive an impossible statement.
• Induction — treated more fully when we study trees (Week 4 in this hub); base case + inductive step.

Sets & logic (basics)

Notation \(x\in S\), \(x\notin S\), unions, intersections, Cartesian products, and power sets (Tutorial problems 2–4). These underpin formal specification of inputs and invariants.

Probability (preview)

Sample spaces, events, \(\Pr(A)=\frac{\text{favourable outcomes}}{\text{total outcomes}}\) when equally likely; independence and conditional probability — used in randomized algorithms and average-case analysis later.

Loop models & recurrence intuition

Before the course starts proving big theorems, it wants you comfortable turning pseudocode into growth estimates.

Connect Tutorial 1’s algebra with growth rates and simple loop models. This complements the Big-O section on the main study page.

Recurrence intuition (preview)

• Balanced divide & conquer — e.g. \(T(n)=2T(n/2)+O(n)\) often yields \(O(n\log n)\) (think: linear work per level, \(\log n\) levels).
• Linear decrease — e.g. \(T(n)=T(n-1)+O(n)\) often yields \(O(n^2)\) (triangle sum).

When unsure, sketch a recursion tree: track total work per level and the number of levels.

Nested loops & \(\Theta(n^2)\)

A common pattern:

for i in range(n):
    for j in range(i):   # j = 0 .. i-1
        ... O(1) work ...

The inner bound depends on \(i\); total iterations behave like \(\sum_{i=0}^{n-1} O(i)=\Theta(n^2)\). Match this with the summation formulas on the Foundations page.

Limits of asymptotic notation

Big-O suppresses constants and lower-order terms — two algorithms with the same big-O class can differ by large factors. Use asymptotics for scalability; combine with measurement for tuning.

Quick checks

These are short retrieval questions. Use them after reading the sections above so the explanations tell you exactly where your understanding still needs repair.

Tutorial PDF review

Open the tutorial PDF in Materials/, attempt the problems first, then use the checklist below to self-audit whether you really understand the intended reasoning moves.