1. Algorithms and Computation

A computational problem is formally a binary relation between an input space and an output space, mapping each input to one or more correct outputs. Rather than enumerating correct answers for every possible input—which would be intractable for large or infinite domains—problems are specified via a predicate that can check whether a given output is correct for a given input. The lecture uses the birthday-match problem as a running example: given a set of students, determine whether any two share the same birth time. Crucially, algorithms in this course must be general, handling arbitrarily large inputs rather than being tailored to a single fixed instance.

• A problem is a binary relation: for each input, it specifies which outputs are correct (there may be more than one).
• Problems are typically defined by a checking predicate rather than an exhaustive input-output table.
• Algorithms must accept arbitrarily sized inputs; a fixed-size classroom is too specific.
• The birthday-match problem generalizes to arbitrarily large populations (e.g., a Facebook database).

An algorithm is a finite, fixed-size procedure that maps every input in a problem's domain to exactly one output, and that output must be a correct output according to the problem's specification. The lecture presents a concrete algorithm for the birthday-match problem: maintain a record, interview students in order, check each new student's birthday against the record, return a matching pair if found, or return 'none' after exhausting all students. Correctness of this algorithm is established via mathematical induction, with the inductive hypothesis stating that after interviewing the first K students, if any match existed among them the algorithm has already returned it.

• An algorithm is a function: one output per input, and that output must be correct.
• The birthday algorithm maintains a record, checks each new entry against it, and returns a pair or 'none'.
• Correctness proofs rely on induction because algorithms loop/recurse over arbitrarily large inputs.
• The inductive hypothesis: 'If the first K students contain a match, the algorithm returns a match before interviewing student K+1.'
• Base case is K=0: zero students trivially contain no match, so the hypothesis holds vacuously.

Efficiency is not measured by wall-clock time, because that depends on hardware. Instead, the course counts the number of fundamental operations an algorithm performs as a function of input size n. Asymptotic notation—Big-O (upper bound), Omega (lower bound), and Theta (tight bound)—captures how performance scales with n while ignoring constant factors. The lecture compares common complexity classes graphically: constant and logarithmic time are nearly indistinguishable at large n and are highly desirable, linear and n log n are acceptable, quadratic is manageable, and exponential is essentially unusable for large inputs.

• Efficiency is measured by counting abstract operations, not real time, to avoid hardware dependence.
• Input size n is the key variable; for an n×n array the input size is n², and for a graph it is |V|+|E|.
• Big-O = upper bound; Omega = lower bound; Theta = tight (upper and lower) bound.
• Complexity hierarchy from best to worst: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n^c) < 2^(Θ(n)).
• Polynomial time (n^c for constant c) is the course's threshold for 'efficient.'

To count operations rigorously, the course uses the Word RAM (Random Access Memory) model. In this model, memory is a sequence of bits addressed in byte-aligned chunks, and the CPU can fetch or write a fixed-size word in constant time. On modern 64-bit machines, one word is 64 bits, allowing the CPU to address up to roughly 20 exabytes of memory. Fundamental constant-time operations include integer arithmetic, logical/bitwise operations, and reading or writing a single word from a memory address. Any operation on n words therefore takes at least linear time because the CPU must access each word individually.

• RAM = Random Access Memory: any memory location can be accessed in constant time.
• A 'word' is the fixed chunk the CPU processes at once; 64 bits on modern hardware, 32 bits on older hardware.
• 32-bit word size limited addressable memory to 2³² bytes ≈ 4 GB; 64-bit allows ≈ 20 exabytes.
• Constant-time CPU operations: integer arithmetic, logical/bitwise ops, and read/write of one word.
• Reading n words takes Θ(n) time; the CPU cannot operate on arbitrary amounts of data in O(1).

The course is divided into three major units assessed by three quizzes: data structures and sorting (first eight lectures), shortest-path algorithms and graphs, and dynamic programming. Two overarching algorithm design strategies frame the entire course: reducing a new problem to one already solved, or designing a new recursive algorithm. Recursive algorithm design is supported by paradigms such as using data structures, solving sorting problems, or searching in graphs. The emphasis throughout is not merely on producing a working solution but on proving correctness and arguing efficiency in writing.

• Two design strategies: reduction to a known problem, or recursive algorithm design.
• Recursive design paradigms include data structures, sorting, and graph search.
• Quiz 1: data structures and sorting; Quiz 2: shortest paths and graphs; Quiz 3: dynamic programming.
• The course demands more writing than coding—proving correctness and efficiency is central.
• Students should be comfortable with inductive proofs from their discrete mathematics prerequisite.