01 Introduction

Why Study Algorithms?

Theoretical Reasons

• Algorithms form the cornerstone of computer science.

Practical Reasons

• Understanding essential algorithms is crucial across different computing areas.

What is an Algorithm?

An algorithm is a sequence of unambiguous instructions for solving a problem, producing a required output for any valid input in finite time.

Example: Sorting

• Input: A sequence of $n$ numbers $(a_1, a_2, ..., a_n)$
• Output: A sorted sequence $(a'_1, a'_2, ..., a'_n)$ such that $a'_i \leq a'_j$ whenever $i < j$.
• Algorithms: Selection sort, Insertion sort, Merge sort

Properties of Algorithms

• Each step must be unambiguous.
• The valid input range should be clearly defined.
• An algorithm can be expressed in multiple ways.
• Multiple algorithms can solve the same problem with different efficiencies.

Problem: Greatest Common Divisor (GCD)

Definition: Find the greatest common divisor of two nonnegative integers $m$ and $n$, where at least one is nonzero.

Example

$\gcd(60, 24) = ?$

Solutions to GCD

Euclid’s Algorithm

1. If $n = 0$, return $m$.
2. Otherwise, compute $\gcd(n, m \mod n)$.

Example:

$\gcd(60, 24) = \gcd(24, 12) = \gcd(12, 0) = 12$

Pseudocode Representation:

Algorithm Euclid(m, n)
while n ≠ 0 do
begin
    r = m mod n
    m = n
    n = r
end
return m

Consecutive Integer Checking Algorithm

1. Set $t = \min(m, n)$.
2. If $m \mod t = 0$, check $n \mod t$.
3. If true, return $t$.
4. Otherwise, decrement $t$ and repeat.

Example (Partial Steps for $\gcd(60, 24)$)

• Start with $t = 24$.
• Decrease $t$ until a common divisor is found.

Middle-School Procedure

1. Find prime factors of $m$ and $n$.
2. Identify common prime factors.
3. Multiply them to get $\gcd(m, n)$.

Example:

$60 = 2 \times 2 \times 3 \times 5$
$24 = 2 \times 2 \times 2 \times 3$
$\gcd(60, 24) = 2 \times 2 \times 3 = 12$

Fundamentals of Algorithmic Problem Solving

1. Understand the problem.
2. Know the computational limits.
3. Choose exact or approximate solving methods.
4. Decide on data structures.
5. Use algorithm design techniques.
6. Specify algorithms (pseudocode, flowcharts).
7. Prove correctness.
8. Analyze efficiency (time, space, simplicity, generality).
9. Implement in code.

Important Problem Types

• Sorting: Arrange items in order.
• Searching: Find a value in a dataset.
• String Processing: Locate patterns in text.
• Graph Problems: e.g., Traveling Salesman, Graph Coloring.
• Combinatorial Problems: Solve constraints with desired properties.
• Geometric Problems: e.g., Closest-Pair Problem.
• Numerical Problems: Solve equations, compute integrals, etc.

Test Your Understanding

• Problem: Implement Euclid’s Algorithm for computing $\gcd(102, 38)$. What is the result?
  • 2