Problems, mathematics and analysis · 01 / 53
Algorithmic thinking: what are we solving?
Understand → trace → implement → justify
2 min reading · allow extra time for practiceAn algorithm is a finite procedure with a defined result for every admissible input. Passing a few examples does not establish correctness. Write the input contract first: are negatives allowed, can keys repeat, is the input sorted, and does it fit in memory? Define the objective as well: a shortest path may minimise edge count or total weight.
A data structure describes representation; an abstract data type describes operations. A stack is an ADT implemented by an array or linked list. Representation should preserve its behavioural contract while changing costs. Representation and algorithms must be designed together: BFS scans different amounts of data with an adjacency matrix and an adjacency list.
Python 3 examples make executable logic visible; memory lessons distinguish C and C#. Trace by hand, execute, then justify costs. Reading progress is not a proficiency certificate. This course separates undergraduate foundations from advanced research topics; no single course guarantees mastery of every subfield or interview success.
A worked trace
For order IDs [8,3,8], “return unique IDs” leaves ordering ambiguous. The set {3,8} and first-occurrence list [8,3] are different outputs.
Cost and assumptions
Always state input size and computational model. The count n of integers differs from their bit length b.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
def unique_in_order(values):
seen, result = set(), []
for value in values:
if value not in seen:
seen.add(value)
result.append(value)
return result
assert unique_in_order([8, 3, 8]) == [8, 3]INTERACTIVE LAB
See every decision.
Step through the real algorithm. Binary search sorts the input first; highlighted indices belong to the sorted array.
Range [0, 6], midpoint 3: compare 18 with 24.
TEST YOUR UNDERSTANDING
Your turn
Specify empty input, duplicates and unhashable inputs for this function.
Reveal the reasoning
Empty input returns []; first occurrence order is preserved. Elements must be hashable. Lists raise TypeError; do not promise support for every object.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
MIT 6.006 · Introduction to Algorithms ↗Pat Morin · Open Data Structures ↗