Book: Introduction to the design and analysis of algorithms
0001 Jun 1

# Computing the greatest common divisor

greatest common divisor of two nonnegative, not-both-zero integers m and n, denoted gcd(m, n), is defined as the largest integer that divides both m and n evenly, i.e., with a remainder of zero.

## Euclid’s algorithm

gcd(m, n) = gcd(n, m mod n),  gcd(m, 0) = m

• Step 1 If n = 0, return the value of m as the answer and stop; otherwise, proceed to Step 2.
• Step 2 Divide m by n and assign the value of the remainder to r.
• Step 3 Assign the value of n to m and the value of r to n. Goto Step 1.

//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n //Output: Greatest common divisor of m and n
while n != 0 do
r ← m mod n
m ← n
n ← r
return m


## Consecutive integer checking algorithm

gcd as the largest integer that divides both numbers evenly

Step 1 Assign the value of min{m, n} to t.

Step 2 Divide m by t. If the remainder of this division is 0, go to Step 3; otherwise, go to Step 4.

Step 3 Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop; otherwise, proceed to Step 4.

Step 4 Decrease the value of t by 1. Go to Step 2.

Generating consecutive primes (sieve of Eratosthenes)

//Implements the sieve of Eratosthenes
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to √n do
if A[p] != 0 //p hasn’t been eliminated on previous passes
j ← p ∗ p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
j ← j + p
//copy the remaining elements of A to array L of the primes
i ← 0
for p ← 2 to n do
if A[p] != 0
L[i] ← A[p]
i ← i+1
return L


# Algorithm design and analysis process

• Understanding the Problem
• type of problem
• legitimate inputs
• Ascertain the Capabilities of the Computational Device
• Specify an Algorithm
• Prove correctness
• algorithm yields a required result for every legitimate input in a finite amount of time
• mathematical induction
• For an approximation algorithm - error does not exceed a predefined limit
• Analyzing an Algorithm
• efficiency
• time
• space
• simplicity
• generality
• Coding an Algorithm

An Algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

# Problem solving

• exact algorithm.
• approximation algorithm.

# Methods of Specifying an Algorithm

• natural language
• pseudocode
• flowchart

# Problem Types

• Sorting
• Searching
• String processing
• Graph problems
• Combinatorial problems
• Geometric problems
• Numerical problems

## Sorting

### Stable sorting

preserves the relative order of any two equal elements in its input.

### in-place sorting

does not require extra memory, except, possibly, for a few memory units.

# Data structures

## Linear

Operations usually are searching for, inserting, and deleting an element.

### Array

is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the array’s index.

String; Bit, binary string;

is a sequence of zero or more elements called nodes, each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list.

### Stack

is a list in which insertions and deletions can be done only at the end.

### Queue

is a list from which elements are deleted from one end of the structure, called the front and new elements are added to the other end, called the rear

Operations: enque, dequeue

### Priority queue

is a collection of data items from a totally ordered universe

Operations: finding its largest element, deleting its largest element, and adding a new element.

## Graphs

Vertices or Nodes
Edges

graph G = ⟨V , E⟩

Operations:

### Graph types

• Directed
• Undirected
• Complete
• Dense
• Sparse
• Weighted
• acyclic
• connected

• subgraph

• connected component

• cycle

• path

### Tree (connected acyclic graph)

Always |E|=|V|−1

• root
• rooted tree
• state-space tree
• depth
• length
• vertex
• parent
• child
• leaf
• parental
• sibling

### Ordered Tree

• binary tree
• binary search tree
• multiway search tree

#### Representation

• first child–next sibling representation.

Let us see one example. Consider the following multiway tree

                  1
/|\
/ | \
/  |  \
2   3   4
/ \      |
5   6     7
/ \
8   9


This tree can be represented in first child-next sibling manner as follows

                  1
/
/
/
2---3---4
/       /
5---6   7
/
8---9


Now, if we look at the first child-next sibling representation of the tree closely, we will see that it forms a binary tree. To see this better, we can rotate every next-sibling edge 45 degrees clockwise. After that we get the following binary tree:

                1
/
2
/ \
5   3
\   \
6   4
/
7
/
8
\
9


### Problems

• Depth-first search

## Set

unordered collection (possibly empty) of distinct items called elements.

### Representations

• Bit string, bit vector
• Universal set U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, then S = {2, 3, 5, 7} is represented by the bit string 011010100
• List structure

Operations:

• searching for a given item, adding a new item, and deleting an item
• dynamic partition of some n-element set into a collection of disjoint subsets (set union problem)

# Analysis

## Time Efficiency(complexity)

• Measuring input size
• Measuring Running Time
• Count basic operations
• (C_{op}) - the execution time of an algorithm’s basic operation on a particular computer
• (C(n)) - the number of times this operation needs to be executed for this algorithm
• (T(n) = C_{op} C(n))

• (log n)
• (n)
• (n log n)
• (n^2)
• (2^n)
• (n!)

## Worst-case efficiency

input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
for any instance of size n, the running time will not exceed (C_{worst}(n)).
bounding its running time from above.

## Best-case efficiency

input (or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.

## Average-case efficiency

we must make some assumptions about possible inputs of size n.
probability

## Amortized efficiency

It applies not to a single run of an algorithm but rather to a sequence of operations performed on the same data structure.
In some situations a single operation can be expensive, but the total time for an entire sequence of n such operations is always significantly better than the worst-case efficiency of that single operation multiplied by n

# Asymptotic Notations

• (O) (big oh)
• (\Theta) (big theta)
• (\Omega) (big omega)
• (t(n)) algorithm running time
• (g(n)) simple function to compare count with
• (C(n)) basic operation count

## Asymtotic efficiency classes

• (1 ) - constant
• (log n ) - logarithmic - cutting a problem’s size by a constant factor on each iteration
• (n ) - linear - scan list of size n
• (n log n) - linearithmic - divide-and-conquer algorithms
• (n^2 ) - quadratic - two embedded loops
• (n^3 ) - cubic - three embedded loops
• (2^n ) - exponential - algorithms that generate all subsets of an n-element set
• (n! ) - factorial - algorithms that generate all permutations of an n-element set

## General plan for Analyzing the Time Efficiency of Nonrecursive Algorithms

1. Decide on a parameter(s) indicating an input’s size.
2. Identify algorithm’s basic operation.
3. Whether the number of times the basic operation is executed depends only on the size of an input;
• if depends on additional property worst, average case and if necessary best-case effeciencies have to be investigated seperately.
4. Set up sum expressing the number of times the algorithm’s basic operation is executed.
5. Find closed form formula for the count or establish order of growth.

## Reccurence relation

Equation defines not explicitly, i.e., as a function of n, but implicitly as a function of its value at another point.

## General Plan for Analyzing the Time Efficiency of Recursive Algorithms

1. Decide on a parameter(s) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution.

# UNSORTED

• backtracking
• branch-and-bound

Gri81
Ker99
Ben00

The greedy approach

geometric algorithms, data compression

brute-force,
decrease-and-conquer,
transform-and-conquer,
iterative improvement

Euclid’s algorithm,
heapsort,
search trees,
hashing,
topological sorting,
Gaussian elimination,
Horner’s rule

numerical algorithms

Back to posts