Overview

This introductory chapter defines what algorithms are, why they matter, and how they relate to other computing technologies. It establishes that algorithms are a fundamental technology—on par with hardware advances—and motivates the study of algorithm design and analysis through practical examples ranging from genomics to cryptography.

Key Concepts

• Algorithm definition: A well-defined computational procedure that takes input and produces output; a tool for solving a specified computational problem.
• Instance of a problem: A specific input satisfying the problem's constraints (e.g., a particular sequence to sort).
• Correctness: An algorithm is correct if, for every input instance, it halts with the correct output. Incorrect algorithms can still be useful if their error rate is controllable.
• Algorithm specification: Can be expressed in English, pseudocode, a programming language, or even hardware; the key requirement is precision.
• Data structures: Ways to store and organize data for efficient access and modification; no single structure works well for all purposes.
• Hard problems (NP-completeness): A class of problems for which no efficient algorithm is known. If an efficient solution exists for any one NP-complete problem, then efficient solutions exist for all of them. The traveling-salesman problem is a classic example.
• Parallelism: Modern multicore processors require algorithms designed with parallelism in mind to extract best performance.

Algorithms and Techniques

• Sorting is introduced as the canonical algorithmic problem: given a sequence of numbers, produce a permutation in nondecreasing order. The chapter previews two sorting algorithms:

• Insertion sort: Takes time roughly proportional to c₁n² (quadratic).

• Merge sort: Takes time roughly proportional to c₂n lg n (linearithmic).

• The chapter does not present detailed pseudocode but uses sorting as a running example to illustrate broader themes.

• Practical problem domains covered include: shortest paths in graphs (Ch. 24), longest common subsequences via dynamic programming (Ch. 15), topological sorting (Ch. 22), convex hulls (Ch. 33), discrete Fourier transforms / FFT (Ch. 30), linear programming (Ch. 29), and public-key cryptography (Ch. 31).

Complexity Analysis

• Efficiency comparison: A computer running insertion sort at 2n² instructions can be dramatically outperformed by a slower computer running merge sort at 50n lg n instructions. For n = 10⁷, insertion sort takes over 5.5 hours on a 10 GHz machine, while merge sort takes under 20 minutes on a 10 MHz machine.
• As problem size increases, the relative advantage of asymptotically faster algorithms becomes more pronounced—merge sort's advantage grows without bound.
• The chapter emphasizes that order of growth (not constant factors) dominates for large inputs.