Introduction to Algorithms (3rd Edition) - Unit 1

Summary
Chapter 1: The Role of Algorithms in Computing

What Are Algorithms?

An algorithm is a well-defined computational procedure that takes input values and produces
output values. It's a sequence of computational steps that transform input into output to solve
a specific problem. An algorithm must be correct, meaning for every input instance, it halts
with the correct output.

Example: The sorting problem takes a sequence of numbers (like 31, 41, 59, 26, 41, 58) and
reorders them into a non-decreasing sequence (like 26, 31, 41, 41, 58, 59).

Algorithms can be specified in English, as computer programs, or even as hardware designs.

The only requirement is that the specification provides a precise description of the
computational procedure.

Real-World Applications of Algorithms

1. Human Genome Project

o Identifying all 100,000 genes in human DNA
o Determining sequences of 3 billion chemical base pairs
o Storing information in databases
o Developing tools for data analysis
o Algorithms enable scientists to accomplish these tasks efficiently
2. Internet Technologies
o Managing and manipulating large volumes of data
o Finding optimal routes for data transmission (Chapter 24)
o Powering search engines to find relevant information (Chapters 11 and 32)
3. Electronic Commerce
o Ensuring privacy of sensitive information (credit cards, passwords)
o Implementing public-key cryptography and digital signatures (Chapter 31)
o Securing transactions through number theory algorithms
4. Resource Allocation
o Placing oil wells to maximize profit
o Optimizing campaign advertising placement
o Assigning airline crews to flights cost-effectively
o Determining optimal placement of internet service resources
o These problems use linear programming techniques (Chapter 29)

Specific Problems Solved by Algorithms

1. Shortest Path Problem

o Finding the shortest route between intersections on a road map
o Modeling the road map as a graph with weighted edges
o Efficiently determining the optimal path (Chapter 24)
 2. Sequence Comparison
o Finding the longest common subsequence between two sequences
o Applications in DNA analysis for measuring similarity
o Using dynamic programming to avoid checking all possible subsequences
(Chapter 15)
3. Topological Sorting
o Ordering parts in a mechanical design so each part appears before any part that
uses it
o Handling dependencies efficiently (Chapter 22)
4. Convex Hull
o Finding the smallest convex polygon containing a set of points
o Like stretching a rubber band around nails on a board
o Efficient algorithms exist despite many possible solutions (Chapter 33)

Data Structures

Data structures are ways to store and organize data to facilitate access and modifications. No
single data structure works well for all purposes, so it's important to know the strengths and
limitations of several different structures.

Hard Problems and NP-Completeness

Some problems have no known efficient algorithms. NP-complete problems (Chapter 34)
have the interesting property that if an efficient algorithm exists for one of them, then
efficient algorithms exist for all of them.

Example: The traveling-salesman problem requires finding the shortest route for a delivery
truck to visit multiple locations and return to a depot. This problem is NP-complete, but
approximation algorithms can provide near-optimal solutions (Chapter 35).

Algorithms as Technology

Algorithms should be considered a technology alongside hardware, GUIs, and networking.

The efficiency of algorithms can have a greater impact on performance than differences in
hardware or software.

Example: When sorting 10 million numbers:

 Computer A: 10 billion instructions/second using insertion sort (2n² instructions)

Takes 20,000 seconds (more than 5.5 hours)
 Computer B: 10 million instructions/second using merge sort (50n log n instructions)
Takes 1,163 seconds (less than 20 minutes)

Even though Computer A is 1000 times faster in raw computing power, Computer B finishes
17 times faster because it uses a more efficient algorithm!

As problem sizes increase, the importance of efficient algorithms grows. The relative
advantage of merge sort over insertion sort becomes even more pronounced with 100 million
numbers: insertion sort would take more than 23 days, while merge sort would take under
four hours.
Chapter 2: Getting Started

Insertion Sort

Insertion sort is an efficient algorithm for sorting small numbers of elements. It works the
way many people sort playing cards: start with an empty left hand, then take one card at a
time from the table and insert it into the correct position in your hand.

Pseudocode:

INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1..j-1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i+1] = A[i]
7 i = i - 1
8 A[i+1] = key

Example: To sort [5, 2, 4, 6, 1, 3]:

1. Start with [5]

2. Insert 2: Compare with 5, move 5 right, insert 2 → [2, 5]
3. Insert 4: Compare with 5, move 5 right, compare with 2, insert 4 → [2, 4, 5]
4. Insert 6: Compare with 5, insert 6 → [2, 4, 5, 6]
5. Insert 1: Compare and move 6, 5, 4, 2 right, insert 1 → [1, 2, 4, 5, 6]
6. Insert 3: Compare and move 6, 5, 4 right, insert 3 → [1, 2, 3, 4, 5, 6]

Loop Invariant: At the start of each iteration of the for loop, the subarray A[1..j-1] consists
of the elements originally in A[1..j-1], but in sorted order.

To prove correctness using the loop invariant:

1. Initialization: Before the first iteration (j=2), the subarray A[1..1] is trivially sorted.
2. Maintenance: Each iteration maintains the invariant by inserting A[j] into its proper
place.
3. Termination: When the loop terminates, j=n+1, so A[1..n] is sorted, which means the
entire array is sorted.

Analyzing Algorithms

Analyzing an algorithm means predicting the resources it requires. We typically focus on

computational time using the RAM (random-access machine) model, where each basic
operation takes a constant amount of time.

The running time depends on the input size n. For insertion sort:

Best case (already sorted array):

 The "while" loop test executes once for each value of j

  Running time is Θ(n)

Worst case (reverse sorted array):

 For each j=2,3,...,n, we compare A[j] with each element in the sorted subarray A[1..j-
1]
 Running time is Θ(n²)

Average case:

 On average, we compare with about half the elements in the sorted subarray
 Running time is still Θ(n²)

We focus on the order of growth of running time, ignoring constant factors and lower-order
terms. For insertion sort, the worst-case running time is Θ(n²).

The Divide-and-Conquer Approach

Divide-and-conquer is a powerful algorithm design paradigm with three steps:

1. Divide the problem into smaller subproblems

2. Conquer the subproblems by solving them recursively
3. Combine the solutions to solve the original problem

Merge Sort

Merge sort applies divide-and-conquer to sorting:

1. Divide: Split the n-element sequence into two subsequences of n/2 elements each
2. Conquer: Sort the two subsequences recursively using merge sort
3. Combine: Merge the two sorted subsequences to produce the sorted answer

The recursion bottoms out when the sequence has length 1 (already sorted).

Pseudocode:

MERGE-SORT(A, p, r)

q = ⌊(p + r)/2⌋
1 if p < r
2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q+1, r)
5 MERGE(A, p, q, r)

The MERGE procedure takes time Θ(n) and works like merging two piles of sorted cards:

1. Compare the top cards from each pile

2. Take the smaller card and put it into the output pile
3. Repeat until one pile is empty, then take the remaining pile

Analysis of Merge Sort:

  Divide: Computing the middle of the subarray takes constant time: Θ(1)
 Conquer: Recursively solving two subproblems of size n/2 takes 2T(n/2)
 Combine: Merging takes Θ(n) time

This gives us the recurrence: T(n) = 2T(n/2) + Θ(n)

Using the recursion tree method, we can see that:

 Each level of recursion contributes Θ(n) work

 There are log n + 1 levels
 Total running time is Θ(n log n)

Merge sort is much more efficient than insertion sort for large inputs, despite having a larger
constant factor.

Chapter 3: Growth of Functions

Asymptotic Notation

Asymptotic notation allows us to focus on the growth rate of functions as input sizes increase,
ignoring constant factors and lower-order terms. This helps us analyze algorithm efficiency in
a simplified way.

Θ-Notation (Theta)

Θ(g(n)) represents functions that are bounded both above and below by g(n), within constant
factors.

Definition: Θ(g(n)) = {f(n): there exist positive constants c₁, c₂, and n₀ such that 0 ≤ c₁g(n)
≤ f(n) ≤ c₂g(n) for all n ≥ n₀}

Example: 1/2n² - 3n = Θ(n²)

 We need to find constants c₁, c₂, and n₀ such that c₁n² ≤ 1/2n² - 3n ≤ c₂n²
 Dividing by n²: c₁ ≤ 1/2 - 3/n ≤ c₂
 For n ≥ 7, we can choose c₁ = 1/14 and c₂ = 1/2

Θ-notation provides an asymptotically tight bound.

O-Notation (Big-O)

O(g(n)) represents functions that are bounded above by g(n), within a constant factor.

Definition: O(g(n)) = {f(n): there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n)
for all n ≥ n₀}

Example: 2n = O(n²)

 We need constants c and n₀ such that 2n ≤ cn²

 Dividing by n: 2 ≤ cn
  This holds for any n ≥ 1 if we choose c = 2

O-notation provides an asymptotic upper bound.

Ω-Notation (Omega)

Ω(g(n)) represents functions that are bounded below by g(n), within a constant factor.

Definition: Ω(g(n)) = {f(n): there exist positive constants c and n₀ such that 0 ≤ cg(n) ≤ f(n)
for all n ≥ n₀}

Example: n²/2 = Ω(n)

 We need constants c and n₀ such that cn ≤ n²/2

 Dividing by n: c ≤ n/2
 This holds for any n ≥ 2c if we choose, for example, c = 1 and n₀ = 2

Ω-notation provides an asymptotic lower bound.

Theorem 3.1: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

o-Notation (Little-o)

o(g(n)) represents functions that grow strictly slower than g(n).

Definition: o(g(n)) = {f(n): for any positive constant c > 0, there exists a constant n₀ > 0 such
that 0 ≤ f(n) < cg(n) for all n ≥ n₀}

Example: 2n = o(n²)

 For any c > 0, we need n₀ such that 2n < cn² for all n ≥ n₀

This holds for n > 2/c, so we can set n₀ = ⌈2/c⌉ + 1

 Dividing by n: 2 < cn


ω-Notation (Little-omega)

ω(g(n)) represents functions that grow strictly faster than g(n).

Definition: ω(g(n)) = {f(n): for any positive constant c > 0, there exists a constant n₀ > 0
such that 0 ≤ cg(n) < f(n) for all n ≥ n₀}

Example: n² = ω(n)

 For any c > 0, we need n₀ such that cn < n² for all n ≥ n₀

This holds for n > c, so we can set n₀ = ⌈c⌉ + 1

 Dividing by n: c < n


Using Asymptotic Notation

Asymptotic notation can be used in equations and inequalities:

 When it stands alone on the right side: n = O(n²) means n ∈ O(n²)
Within formulas: 2n² + 3n + 1 = 2n² + Θ(n) means there exists f(n) ∈ Θ(n) such that


2n² + 3n + 1 = 2n² + f(n)
 In chains: 2n² + 3n + 1 = 2n² + Θ(n) = Θ(n²)

Standard Notations and Common Functions

Monotonicity

 A function f(n) is monotonically increasing if m ≤ n implies f(m) ≤ f(n)

 A function f(n) is monotonically decreasing if m ≤ n implies f(m) ≥ f(n)
 A function f(n) is strictly increasing if m < n implies f(m) < f(n)
 A function f(n) is strictly decreasing if m < n implies f(m) > f(n)

Floors and Ceilings

Floor function: ⌊x⌋ = greatest integer less than or equal to x

Ceiling function: ⌈x⌉ = least integer greater than or equal to x


Properties: x - 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1



For any integer n: ⌈n/2⌉ + ⌊n/2⌋ = n




Modular Arithmetic

 a mod n = a - n⌊a/n⌋
 0 ≤ a mod n < n
 a ≡ b (mod n) if (a mod n) = (b mod n)

Common Functions in Algorithm Analysis

 Polynomials: n², n³, etc. - grow faster than logarithms but slower than exponentials
 Logarithms: log n - grow very slowly; log(n^k) = k log n
 Exponentials: 2^n - grow faster than any polynomial when base > 1
 Factorials: n! - grow faster than exponentials

These functions form a hierarchy of growth rates: log log n ≪ log n ≪ n^(1/2) ≪ n ≪ n log
n ≪ n² ≪ n³ ≪ 2^n ≪ n! ≪ n^n

Understanding these growth rates helps us compare algorithm efficiencies and make
informed choices about which algorithms to use for different problem sizes.