Data Structures & Algorithms
Learn algorithms as a cumulative Python course: define the problem, trace state by hand, prove why each step works, derive resource growth, falsify weak assumptions, and finish with a locally executable route planner.
Complexity and problem modeling
Objective Turn one precise problem contract into a hand trace, invariant, termination argument, and honest time-and-space claim.
Core explanation
A problem contract says exactly what a computation accepts and returns: the input is the supplied value and the output is the promised result. For this laboratory, the input is a finite Python list of integers and the output reports whether a value repeats, the zero-based index where the first repeat is discovered, how many membership checks occurred, and how many distinct values were retained; Let n mean the number of input values. Equality follows Python integer equality, the input list is not mutated, and an empty or all-unique list is valid. These choices are part of correctness because changing “first repeated position” to “any duplicated value” would define a different problem. An invariant is a statement that remains true at a named point in every loop iteration; immediately before each membership test, seen contains exactly the distinct values at earlier indices. Initialization holds because there are no earlier values before index zero and seen is empty, while adding a new current value preserves the invariant for the next index. If the current value is already present, the invariant proves that this is the first position where the scan can discover a repeat. Progress occurs because the for loop advances to the next index, and termination follows because the list has n finite positions. Time complexity describes growth in counted work rather than seconds, so here the algorithm performs at most n membership checks and n insertions. Python set membership and insertion are expected O(1), not unconditional worst-case O(1), making the whole scan expected O(n) time. The set retains at most n distinct values, giving O(n) auxiliary space, while the returned dictionary is constant-sized.
Turn an informal request into a precise computational problem
An algorithm begins with a contract, not a technique name. State the input domain, output meaning, invalid-input policy, mutation allowance, ordering and tie rules, numeric limits, identity, and whether an answer must be exact. “Find duplicates” is incomplete until you decide whether values use identity or equality, whether the output is a boolean, first repeated value, all repeated values, or duplicate positions, and whether input order must be preserved. Concrete examples should cover empty, smallest, ordinary, boundary, duplicate, adversarial, and impossible cases.
Separate representation from the mathematical problem. A graph may arrive as edge records, a matrix, or an API; the required result may be reachability regardless of representation. Write preconditions and postconditions, then state an invariant that should hold during the computation. If the result is optimized, define the objective and deterministic tie breaker. This disciplined model prevents solving a familiar but different problem and gives tests something stronger than one expected sample to verify.
Analyze growth from primitive work and retained state
Time complexity describes how operation count grows with named input parameters under a computation model. Count loops, recursion branches, data-structure operations, comparisons, allocations, and representation conversion. Drop constants and lower-order terms only after deriving the expression. A loop over n items containing a binary search is O(n log n); two consecutive linear loops remain O(n); nested loops are not automatically quadratic when both pointers move only forward. Name several parameters when dimensions differ, such as O(V+E) or O(rows times columns).
Space complexity includes auxiliary collections, recursion depth, output storage when the convention counts it, and retained state across operations. Distinguish worst-case, average or expected, amortized, and best-case claims. Hash-table lookup is commonly expected O(1), while dynamic-array append is amortized O(1) because occasional growth copies many elements. Complexity excludes hardware constants but engineering still measures cache locality, allocation, branch behavior, network and storage costs on representative inputs.
Prove termination and correctness with invariants
A loop proof identifies initialization, invariant preservation, progress, and termination. For lower-bound binary search, the answer remains inside a half-open interval; each comparison discards a region that cannot contain the first valid position; the interval strictly shrinks; and when its ends meet, that position is the answer. A recursive proof defines base cases, shows every call moves toward them, and proves that combining correct subresults yields the parent result. These arguments expose off-by-one and nontermination defects before code runs.
Correctness also includes failure and representation boundaries. An algorithm relying on sorted input must reject, document, or establish sorting. Integer arithmetic may overflow in fixed-width languages; Unicode text may not be safely indexed by byte or code unit; floating comparisons need a domain policy. A proof should name assumptions rather than silently importing them. Use a reference implementation or exhaustive small-state oracle to test the optimized version, then add property and mutation cases that would fail if the invariant were weakened.
Laboratory: trace one executable duplicate detector before comparing techniques
Copy the displayed program into algorithms_chapter_01.py and predict all five output lines before running python3 algorithms_chapter_01.py. On paper, keep one row per membership check: index, current value, sorted seen_before, duplicate, and the action taken. Reconcile your table with the printout. The set is shown in sorted order only to make evidence deterministic; the algorithm needs membership, not sorted-set behavior.
Repeat with empty, singleton, immediate-repeat, all-unique, and late-repeat lists. The assertions must check the whole returned dictionary. Then remove seen.add(value) as one controlled mutation: [4, 1, 4, 2] will incorrectly report no repeat because the invariant stops being true after the first iteration. Restore the update, retain the smallest failing case [4, 4], and explain separately why the correctness proof, expected O(n) time claim, O(n) auxiliary-space bound, and observed trace are different kinds of evidence.