Your revision desk
A compact companion to the full lectures. Review the reasoning, then close the notes and try a practice question. These notes do not predict any particular exam.
Git & the working environment
Working tree → staging area → commit is the core local sequence. A branch lets you compare experiments. A remote supports sharing and backup. Always inspect the changes you intend to commit.
Revisit the full explanationThinking in algorithms
Choose the representation and the algorithm together. State preconditions, establish correctness, and then compare time and space. A fast implementation of the wrong procedure does not solve the problem.
Revisit the full explanationJava setup & first programs
Record the source version, input and runtime environment with each timing experiment. First establish that the program returns the expected result. Then measure performance using a clear input-size definition.
Revisit the full explanationEuclid’s algorithm & recursion
Explain both preservation and progress: the GCD does not change, and a positive remainder is smaller than its divisor. State the input assumptions when discussing correctness or complexity.
Revisit the full explanationMeasuring & modelling algorithms
Define n and the input assumptions. Select a cost model. Count operations or derive a recurrence. Simplify with the appropriate notation. Separate empirical observations from proofs, and state the memory model.
Revisit the full explanationUnion–find & dynamic connectivity
Quick-find makes lookup cheap by making updates expensive. Quick-union delays work but can grow deep trees. Weighting controls tree height; path compression speeds later operations. Always name the variant when quoting a bound.
Revisit the full explanationAsymptotic analysis & growth rates
Define the function and the input model before writing a bound. O is an upper bound, Ω a lower bound and Θ a tight bound. Show the loop count, sum or recurrence that justifies the result.
Revisit the full explanationStacks, queues & amortized analysis
Linked structures avoid resizing pauses but use references per node. Resizing arrays store items compactly but occasionally copy. Distinguish worst-case per-operation cost from amortized cost across a sequence.
Revisit the full explanationKeep these formulas close
Euclidean reduction
All index pairs
All index triples
Doubling hypothesis
Geometric growth
Binary-search recurrence
Common confusions, resolved
| Distinction | Remember |
|---|---|
| Big O vs Big Theta | O provides an upper bound; Θ provides a tight growth class. |
| Best case vs Omega | Best case selects the easiest input; Ω is a lower-bound relation on a specified function. |
| Average vs amortized | Average case uses a probability model; amortized analysis bounds a sequence without assuming random inputs. |
| Quick-find vs quick-union | Quick-find relabels an array; quick-union links component roots. |
| Stack vs queue | Stack is LIFO; queue is FIFO. |
| Correctness vs performance | An algorithm must return the required result before its speed is useful. |