1.1 Algorithms

An algorithm is a well-defined computational procedure that takes input, performs a finite sequence of steps, and produces output. It’s both a step-by-step process and a tool for solving computational problems — each problem defines an input–output relationship, and the algorithm provides the specific method to achieve it.

Example – Sorting problem:

• Input: a sequence of numbers ⟨a₁, a₂, …, aₙ⟩

• Output: a permutation ⟨a′₁, a′₂, …, a′ₙ⟩ such that a′₁ ≤ a′₂ ≤ … ≤ a′ₙ

• Example instance: ⟨31, 41, 59, 26, 41, 58⟩ → ⟨26, 31, 41, 41, 58, 59⟩

  Sorting is a fundamental operation used by many programs, and the best algorithm depends on factors like data size, order, constraints, and hardware.

Correctness:

An algorithm is correct if it halts (finishes its computing in finite time) and always produces the right output.

Incorrect algorithms may still be useful if their error rate is controlled.

Applications of algorithms:

• Biology: e.g., DNA sequence analysis and gene identification in the Human Genome Project using dynamic programming.
• Internet: routing and search engines use algorithms for efficient data handling.
• E-commerce: relies on cryptography and digital signatures for privacy.
• Optimization in industry: resource allocation, scheduling, and planning modeled as linear programs.

Algorithms often tackle problems with an enormous number of possible solutions, where testing each option is infeasible. Instead, they find efficient ways to reach correct or optimal results.

Examples include:

• Shortest path problem: Finding the minimum-distance route between two points on a map, modeled as a graph. Used in navigation and network routing.
• Topological sorting: Ordering components so that each appears before those depending on it, such as arranging parts in a mechanical design.
• Clustering in medical imaging: Grouping data (e.g., tumor images) by similarity to classify outcomes like benign or malignant.
• Data compression: Reducing file size efficiently through encoding schemes like Huffman coding or LZW.
• Fourier transform: Converting signals from the time domain to the frequency domain (as in FFT), essential for signal processing, compression, and numerical computation.

All these problems share two key traits:

1. They involve a vast space of potential solutions but need efficient methods to find the right or best one.
2. They have strong practical applications — in navigation, communication, healthcare, manufacturing, and data processing.

Some problems, like the Fourier transform, don’t have a clear set of discrete candidate solutions but still rely on algorithmic procedures to compute results efficiently.

Data structures

Organize and store data to enable efficient access and modification. Choosing the right structure is crucial for designing effective algorithms.