github twitter email rss
Book: Introduction to the design and analysis of algorithms
0001 Jun 1
7 minutes read

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


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


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


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.


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

Operation: add, pop


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.


Vertices or Nodes

graph G = ⟨V , E⟩


Graph types

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

  • subgraph

  • connected component

  • cycle

  • path


  • 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


Ordered Tree

  • binary tree
  • binary search tree
  • multiway search tree


  • first child–next sibling representation.

Let us see one example. Consider the following multiway tree

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

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

             /       /        
            5---6   7         

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:

             / \              
            5   3             
             \   \            
              6   4           


  • Depth-first search
  • Breadth-first search


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


  • 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


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



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

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.

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.

NEXT 2.5


  • backtracking
  • branch-and-bound


The greedy approach

geometric algorithms, data compression

space and time trade-offs,
iterative improvement

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

numerical algorithms

Back to posts

comments powered by Disqus