# Book: Introduction to the design and analysis of algorithms

# 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

- type of problem
- 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

- algorithm yields a required result for every legitimate input in a finite amount of time
- Analyzing an Algorithm

- efficiency

- time
- space

- time
- simplicity
- generality

- efficiency
- 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.

## Searching

### Binary search

# 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;

### Linked list

- 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.

Operation: add, pop

### 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

### Representations

- Adjacency matrix
- Adjacency lists

### Tree (connected acyclic graph)

Always |E|=|V|−1

- root
- rooted tree
- state-space tree
- depth
- length
- vertex

- parent
- child
- leaf
- parental
- sibling

- parent

### Forest

### 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

#### Search

- Depth-first search
- Breadth-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

- 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)

## Dictionary

# 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))

- Count basic operations

## Space Efficiency(complexity)

## Orders of Growth

- (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

- Decide on a parameter(s) indicating an input’s size.
- Identify algorithm’s basic operation.
- 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.

- if depends on additional property worst, average case and if necessary best-case effeciencies have to be investigated seperately.
- Set up sum expressing the number of times the algorithm’s basic operation is executed.
- 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

- Decide on a parameter(s) indicating an input’s size.
- Identify the algorithm’s basic operation.
- 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.
- Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.
- Solve the recurrence or, at least, ascertain the order of growth of its solution.

# NEXT 2.5

# UNSORTED

- backtracking
- branch-and-bound

Gri81

Ker99

Ben00

The greedy approach

geometric algorithms, data compression

brute-force,

decrease-and-conquer,

transform-and-conquer,

space and time trade-offs,

iterative improvement

Euclid’s algorithm,

heapsort,

search trees,

hashing,

topological sorting,

Gaussian elimination,

Horner’s rule

numerical algorithms