Assignment No.2 - Design and Analysis of Algorithms
Assignment No.2 - Design and Analysis of Algorithms
Assignment No.2 - Design and Analysis of Algorithms
Decrease-and-Conquer
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-1
3 Types of Decrease and Conquer
Decrease by a constant (usually by 1):
• insertion sort
• graph traversal algorithms (DFS and BFS)
• topological sorting
• algorithms for generating permutations, subsets
Example: Sort 6, 4, 1, 8, 5
6|4 1 8 5
4 6|1 8 5
1 4 6|8 5
1 4 6 8|5
1 4 5 6 8
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-4
Pseudocode of Insertion Sort
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-5
Analysis of Insertion Sort
Time efficiency
Cworst(n) = n(n-1)/2 Θ(n2)
Cavg(n) ≈ n2/4 Θ(n2)
Cbest(n) = n - 1 Θ(n) (also fast on almost sorted arrays)
Stability: yes
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-7
Depth-First Search (DFS)
Visits graph’s vertices by always moving away from last
visited vertex to an unvisited one, backtracks if no adjacent
unvisited vertex is available.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-8
Pseudocode of DFS
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-9
Example: DFS traversal of undirected graph
a b c d
e f g h
1 2 6 7
a b c d
abgcdh
abgcd
abgcd
abgc
abfe
abg
abf
abf
…
ab
ab
e f h g
a
4 3 8 5
Red edges are tree edges and
white edges are back edges.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-10
Notes on DFS
DFS can be implemented with graphs represented as:
• adjacency matrices: Θ(|V|2). Why?
• adjacency lists: Θ(|V|+|E|). Why?
Applications:
• checking connectivity, finding connected components
• checking acyclicity (if no back edges)
• finding articulation points and biconnected components
• searching the state-space of problems for solutions (in AI)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-11
Breadth-first search (BFS)
Visits graph vertices by moving across to all the neighbors
of the last visited vertex
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-12
Pseudocode of BFS
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-13
Example of BFS traversal of undirected graph
a b c d
e f g h
1 2 6 8
a b c d
bef
efg
hd
ch
fg
e f g h
g
d
a
3 4 5 7
Red edges are tree edges and
white edges are cross edges.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-14
Notes on BFS
BFS has same efficiency as DFS and can be implemented
with graphs represented as:
• adjacency matrices: Θ(|V|2). Why?
• adjacency lists: Θ(|V|+|E|). Why?
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-15
DAGs and Topological Sorting
A dag: a directed acyclic graph, i.e. a directed graph with no (directed)
cycles
a b a b
a dag not a dag
c d c d
Arise in modeling many problems that involve prerequisite
constraints (construction projects, document version control)
Vertices of a dag can be linearly ordered so that for every edge its starting
vertex is listed before its ending vertex (topological sorting). Being a dag is
also a necessary condition for topological sorting to be possible.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-16
Topological Sorting Example
Order the following items in a food chain
tiger
human
fish
sheep
shrimp
plankton wheat
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-17
DFS-based Algorithm
DFS-based algorithm for topological sorting
• Perform DFS traversal, noting the order vertices are popped off
the traversal stack
• Reverse order solves topological sorting problem
• Back edges encountered?→ NOT a dag!
Example:
b a c d
e f g h
Efficiency: The same as that of DFS.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-18
Source Removal Algorithm
Source removal algorithm
Repeatedly identify and remove a source (a vertex with no incoming
edges) and all the edges incident to it until either no vertex is left or
there is no source among the remaining vertices (not a dag)
Example:
a b c d
e f g h
Efficiency: same as efficiency of the DFS-based algorithm, but how would you
identify a source? How do you remove a source from the dag?
“Invert” the adjacency lists for each vertex to count the number of incoming edges by
going thru each adjacency list and counting the number of times that each vertex appears
in these lists. To remove a source, decrement the count of each of its neighbors by one.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-19
Decrease-by-Constant-Factor Algorithms
In this variation of decrease-and-conquer, instance size is
reduced by the same factor (typically, 2)
Examples:
• Binary search and the method of bisection
• Exponentiation by squaring
• Fake-coin puzzle
• Josephus problem
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-20
Exponentiation by Squaring
The problem: Compute an where n is a nonnegative integer
a n = (a (n-1)/2 )2 a
Recurrence: M(n) = M( n/2 ) + f(n), where f(n) = 1 or 2,
M(0) = 0
Master Theorem: M(n) Θ(log n) = Θ(b) where b = log2(n+1)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-21
Russian Peasant Multiplication
The problem: Compute the product of two positive integers
n * m = n * 2m
2
n * m = n – 1 * 2m + m if n > 1 and m if n = 1
2
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-22
Example of Russian Peasant Multiplication
Compute 20 * 26
n m
20 26
10 52
5 104 104
2 208 +
1 416 416
520
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-23
Fake-Coin Puzzle (simpler version)
There are n identically looking coins one of which is fake.
There is a balance scale but there are no weights; the scale can
tell whether two sets of coins weigh the same and, if not, which
of the two sets is heavier (but not by how much, i.e. 3-way
comparison). Design an efficient algorithm for detecting the
fake coin. Assume that the fake coin is known to be lighter
than the genuine ones.
Examples:
• Euclid’s algorithm for greatest common divisor
• Interpolation search
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-25
Euclid’s Algorithm
Euclid’s algorithm is based on repeated application of equality
gcd(m, n) = gcd(n, m mod n)
One can prove that the size, measured by the first number,
decreases at least by half after two consecutive iterations.
Hence, T(n) O(log n)
Proof. Assume m > n, and consider m and m mod n.
Case 1: n <= m/2. m mod n < n <= m/2.
Case 2: n > m/2. m mod n = m-n < m/2.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-26
Selection Problem
Find the k-th smallest element in a list of n numbers
k = 1 or k = n
median: k = n/2
Example: 4, 1, 10, 9, 7, 12, 8, 2, 15 median = ?
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-27
Algorithms for the Selection Problem
The sorting-based algorithm: Sort and return the k-th element
Efficiency (if sorted by mergesort): Θ(nlog n)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-29
Tracing the Median / Selection Algorithm
array index 1 2 3 4 5 6 7 8 9
4 1 10 9 7 12 8 2 15
4 1 2 9 7 12 8 10 15
2 1 4 9 7 12 8 10 15 --- s=3 < k=5
9 7 12 8 10 15
9 7 8 12 10 15
8 7 9 12 10 15 --- s=6 > k=5
8 7
7 8 --- s=k=5
Solution: median is 8
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-30
Efficiency of the Partition-based Algorithm
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-31
Interpolation Search
Searches a sorted array similar to binary search but estimates
location of the search key in A[l..r] by using its value v.
Specifically, the values of the array’s elements are assumed to
grow linearly from A[l] to A[r] and the location of v is
estimated as the x-coordinate of the point on the straight line
through (l, A[l]) and (r, A[r]) whose y-coordinate is v:
value
A[r] .
v
A[l] .
index
l x r
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-32
Analysis of Interpolation Search
Efficiency
average case: C(n) < log2 log2 n + 1 (from “rounding errors”)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-33
Binary Search Tree Algorithms
Several algorithms on BST requires recursive processing of
just one of its subtrees, e.g.,
Searching
k
Insertion of a new key
Finding the smallest (or the largest) key
<k >k
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-34
Searching in Binary Search Tree
Algorithm BST(x, v)
//Searches for node with key equal to v in BST rooted at node x
if x = NIL return -1
else if v = K(x) return x
else if v < K(x) return BST(left(x), v)
else return BST(right(x), v)
Efficiency
worst case: C(n) = n
average case: C(n) ≈ 2ln n ≈ 1.39log2 n, if the BST was built
from n random keys and v is chosen randomly.
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-35
One-Pile Nim
There is a pile of n chips. Two players take turn by removing
from the pile at least 1 and at most m chips. (The number of
chips taken can vary from move to move.) The winner is the
player that takes the last chip. Who wins the game – the
player moving first or second, if both player make the best
moves possible?
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 5 5-36
Partial Graph of One-Pile Nim with m = 4
1 6
2 7
0 5 10
3 8
4 9