MIT 6.006 Introduction to Algorithms — Lecture 1: Algorithmic Thinking, Peak Finding

Overview

The lecture introduces MIT's 6.006 course, stressing the importance of designing algorithms that scale to massive inputs. It surveys the core topics that will be covered, from sorting to dynamic programming, and clarifies policies and expectations. The central technical focus is peak finding, first in one dimension with a transition from linear to logarithmic methods, then in two dimensions where a correct divide‑and‑conquer approach achieves near‑optimal performance.

Chapter breakdown

Key points

• 00:22Prof. Srini Devadas introduces himself and co‑lecturing the 6.006 Introduction to Algorithms course with Erik Domane.
• 01:00Directs students to the course website for the syllabus, expectations, problem‑set and quiz schedules.
• 02:08Prerequisite is 6.042; students should recall asymptotic complexity from that course.
• 06:40The follow‑up course 6.046 Designing and Analyzing Algorithms offers deeper algorithm design work.
• 09:57Sorting a massive number of items (e.g., a trillion) requires efficient algorithms.
• 11:01Low‑complexity hashing methods are essential for large‑scale genome comparisons.
• 13:01Graph representations can model puzzles such as the Rubik’s cube or the 15‑puzzle.
• 15:01Advises students to read the collaboration policy and grading breakdown on the course website.
• 18:31Describes the naïve linear‑time approach as the baseline for later improvements.
• 20:12Assigns a homework problem: prove any array always contains a peak under the ≥ definition.
• 24:38Asks the class how to improve the asymptotic complexity of the one‑dimensional peak finder.
• 25:00A student suggests a binary‑search (divide‑and‑conquer) method that halves the search space each step.
• 26:25Introduces the “cushion” system for rewarding correct answers and engages the audience with a light‑hearted demonstration.
• 30:44Sketches a correctness argument: if the middle element is greater than its neighbours it is a peak; otherwise recurse on the appropriate half.
• 34:53Compares actual runtimes: Θ(n) algorithm takes seconds for 10 million items, while the Θ(log n) version finishes in milliseconds, highlighting the exponential gap.
• 36:41A 2‑D peak is an element that is greater than or equal to its north, south, east, and west neighbors.
• 40:30In the worst case, Greedy Ascent can touch Θ(n·m) elements, i.e., linear in the size of the matrix.
• 45:01The above divide‑and‑conquer method is inefficiently correct: a 1‑D peak on the chosen row need not be a 2‑D peak.
• 47:06Introduce a recursive algorithm that improves on the greedy approach and guarantees correctness.
• 51:31Derive the recurrence T(n,m)=T(n,m/2)+Θ(n), which solves to a total running time of Θ(n log m).

Key terms

• Asymptotic complexity — The growth rate of an algorithm’s running time or space usage as the input size n approaches infinity, typically expressed with Big‑O notation.
• Peak finding — A problem of locating a local maximum (a ‘peak’) in a one‑dimensional array or two‑dimensional grid.
• Binary search tree — A tree data structure in which each node stores a key; all keys in the left subtree are smaller and all keys in the right subtree are larger.
• Hash table (dictionary) — A data structure that maps keys to values using a hash function for near‑constant‑time look‑ups.
• Balanced binary search tree — A binary search tree that maintains its height as O(log n) (e.g., AVL or red‑black tree) to guarantee efficient operations.
• Scalability — The capability of an algorithm or system to handle growth in input size or workload without a prohibitive increase in resource consumption.
• 6.006 — MIT’s undergraduate course “Introduction to Algorithms.”
• 6.042 — MIT’s “Mathematics for Computer Science,” covering discrete mathematics and asymptotic analysis.
• 6.046 — MIT’s “Designing and Analyzing Algorithms,” a more advanced follow‑up to 6.006.
• Sorting — The process of arranging data items into a defined order, usually ascending or descending.
• Binary tree — A hierarchical data structure in which each node has at most two children, called left and right.
• Hashing — Transforming input data into a fixed‑size string of characters, typically used for fast lookup or comparison.
• Genome comparison — Analyzing the similarity between DNA sequences of different organisms, often requiring efficient algorithms.
• RSA encryption — A public‑key cryptographic system that uses large prime numbers to encrypt and decrypt data.
• Infinite‑precision numbers — Numeric representations that can store arbitrarily many digits, limited only by memory.
• Graph — A collection of vertices (nodes) connected by edges, used to model relationships.
• Dynamic programming — An algorithmic technique that solves problems by breaking them into overlapping subproblems and storing intermediate results.
• Complexity theory — The study of the resources (time, space) required by algorithms as a function of input size.
• Pseudocode — A high‑level, language‑agnostic description of an algorithm’s logic.
• Peak (in an array) — An element that is greater than or equal to its immediate neighbours (adjacent elements).
• Θ (Theta) notation — Asymptotic bound that describes both the lower and upper limits of a function's growth.
• O (Big‑O) notation — An asymptotic upper bound that describes the worst‑case growth rate of an algorithm.
• Divide and Conquer — An algorithm design paradigm that solves a problem by breaking it into smaller subproblems, solving each recursively, and combining the results.
• Binary search — A logarithmic‑time search technique that repeatedly halves a sorted (or partially ordered) search space.
• Exhaustive search — A brute‑force method that checks every possible candidate to guarantee correctness.
• recursive algorithm — An algorithm that solves a problem by reducing it to a smaller instance of the same problem and calling itself on that sub‑instance.
• recurrence relation — An equation that expresses the running time of a recursive algorithm in terms of the running time on smaller inputs.
• Θ‑notation — Asymptotic notation that gives a tight bound on the growth rate of a function.
• Base Case — The simplest instance of a problem for which the answer is known directly, stopping further recursion.
• Logarithmic Complexity — A running time that grows proportionally to the logarithm of the input size, e.g., Θ(log n).
• Exponential Difference — A contrast between algorithms whose runtimes grow at dramatically different rates, such as Θ(n) versus Θ(2ⁿ).
• 2D peak — An element in a matrix that is greater than or equal to its immediate neighbors above, below, left, and right.
• Greedy Ascent algorithm — An iterative local‑search method that moves to a neighboring element with larger value until a peak is reached.
• Worst‑case complexity — The maximum amount of resources (time, steps) an algorithm may require over all inputs of a given size.
• 1‑D peak — An element in a one‑dimensional array that is not smaller than its immediate neighbors.
• global maximum — The largest value in a given set or region, such as a whole column of a matrix.

← All MIT OpenCourseWare course notes