Transcript Document

CSCE350 Algorithms and Data Structure
Lecture 6
Jianjun Hu
Department of Computer Science and Engineering
University of South Carolina
2009.9.
Outline
Review of recursive algorithm running time—cheat sheet
Homogeneous Second-Order Linear Recurrence
Brute Force Strategy for Algorithm Design
 The art of lazy algorithm is to count/estimate its running time
 Is it doable within given timeframe?
Time Efficiency of Recursive Algorithms
Steps in mathematical analysis of recursive algorithms:
Decide on parameter n indicating input size
Identify algorithm’s basic operation
Determine worst, average, and best case for input of size n
Set up a recurrence relation and initial condition(s) for C(n)-the
number of times the basic operation will be executed for an
input of size n (alternatively count recursive calls).
Solve the recurrence to obtain a closed form or estimate the
order of magnitude of the solution (see Appendix B)
Three Recurrence Types We know How to
Find the Closed-Form Solution
T ( n )  a  T ( n  1)  n k
T ( n )  a  T ( n / b)  n k ( a  1, b  1)  Maste rTh e ore m
T ( n )  a  T ( n  1)  b  T ( n  2)
Please related them to the following algorithms we learned in
the last class
• Recursive algorithm for n!
• Recursive algorithm for Tower of Hanoi
• Recursive algorithm for finding the number of digits in the
binary representation of a decimal integer
• Recursive algorithm for finding the Fibbonacci numbers
Important Recurrence Types:
One (constant) operation reduces problem size by one.
T(n) = T(n-1) + c
T(1) = d
Solution: T(n) = (n-1)c + d
linear
A pass through input reduces problem size by one.
T(n) = T(n-1) + cn
T(1) = d
Solution: T(n) = [n(n+1)/2 – 1] c + d
quadratic
One (constant) operation reduces problem size by half.
T(n) = T(n/2) + c
Solution: T(n) = c lg n + d
T(1) = d
logarithmic
A pass through input reduces problem size by half.
T(n) = 2T(n/2) + cn
Solution: T(n) = cn lg n + d n
T(1) = d
n log n
A General Divide-and-Conquer Recurrence:
Master Theorem
T(n) = aT(n/b) + f (n)
where f (n) ∈ Θ(nk)
a < bk
T(n) ∈ Θ(nk)
a = bk
T(n) ∈ Θ(nk lg n )
a > bk
T(n) ∈ Θ(nlog b a)
Note: the same results hold with O instead of Θ.
Solutions to a Homogeneous Second-Order
Linear Recurrence with Constant Coefficients
aT (n)  bT (n  1)  cT (n  2)  0, a  0
Characteristic equation
ar2  br  c  0
 roots
r1, r2
Then
i f r1  r2 an d both are re al  T ( n )   r1n   r2n
i f r1  r2  r i s re al  T ( n )   r n  nr n
i f r1, 2  u  iv are com ple x T ( n )   n (cosn   sin n )
wh e re  u 2  v 2 an d  arctanv / u
Fibonacci numbers
The Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
Fibonacci recurrence:
F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1
Another example:
A(n) = 3A(n-1) – 2A(n-2)
2nd order linear homogeneous
recurrence relation
with constant coefficients
A(0) = 1
A(1) = 3
How to Find the Constants

and

Using the initial conditions
For example, for Fibonacci numbers
F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1
1 5
Characteristic equation r  r  1  0  roots r1, 2 
2
2
We have
n
1 5 
1 5 
  

F (n )   



2
2




Using F(0)=0 and F(1)=1 
n
  1/ 5 and   1 / 5
Computing Fibonacci numbers
•
Definition based recursive algorithm
•
Nonrecursive brute-force algorithm
•
Explicit formula algorithm
•
Logarithmic algorithm based on formula:
F(n-1)
F(n)
F(n) F(n+1)
=
0 1
n
1 1
for n≥1, assuming an efficient way of computing matrix powers.
Another Example: calculating a^n
Construct an algorithm for computing an, where a>0 is a
constant and the integer n>=0 is the input size. Then analyze
its time efficiency
Basic operation  a multiplication of two float numbers
Two choices
• Nonrecursive algorithm
• Recursive algorithm
Any idea to make it faster, e.g., with a better time efficiency?
Can we solve this problem in (logn ) time?
Empirical Analysis of Algorithm Time
Efficiency
 Why?
 Mathematical analysis is difficult for many algorithms
 Difficult for average case analysis
 Difficult for special type of data distribution
 How?
 Purpose: compare efficiency
 Efficiency measures M: operation counts or time unit
 Determine characteristics of typical sample input
 Implement the algorithm and run it
 Different sample sizes, multiple samples for each size
 Profiling tools: measuring time spent on different segments of
program can pinpoint bottleneck in a program..
Empirical Analysis of Algorithm Time
Efficiency
Data analysis for the empirical data
Scatter Plot
Now We Get to Chapter 3 -- Brute Force
From now on, we are going to learn some basic and general
strategies in designing algorithms to solve some typical
computing problems.
We will analyze the efficiency of these algorithms using the
tools learned in the past several classes
We will learn how to design algorithms with better efficiency
First, let’s talk about the Brute Force strategies– the simplest
Brute Force Strategy for Algorithm Design
• Brute Force is a straightforward approach to solving a
problem, usually directly based on the problem’s statement
and definitions of the concepts involved
• In many cases, Brute Force does not provide you a very
efficient solution
• Brute Force may be enough for moderate size problems with
current computers….
Sorting Algorithm
We have discussed two sorting algorithms: Selection Sort and
Insertion Sort
What are the basic idea behind the Selection-Sort algorithm?
• Scanning the entire given list to find its smallest element and
swap it with the first element
• This is a straightforward solution – Brute Force strategy
• What is its time efficiency – (n2 )
An example: sorting the numbers [89 45 68 90 29 34 17]
See pseudocode in Section 3.1
Selection sort
Cworst (n)  Cbest (n)  Caverage (n)  (n )
2
Insertion Sort
Cworst (n)  (n ), Cbest (n)  (n), Caverage (n)  ?
2
Another Brute-Force Application: Bubble Sort
Compare adjacent elements and exchange them if they are out
of order
This the result after the first pass, which moves the largest as
the rightmost element
89 ? 45
68
90
29
34
17
45
45
89 ? 68 90 29
68 89 ? 90 ? 29
34
34
17
17
45
68
89
29
90 ? 34
17
45
68
89
29
34
90 ? 17
45
68
89
29
34
17
90
Algorithm in Pseudocode
ALGO RITHMBubbleSort( A[0..n  1])
// Th e algorith msortsarray A[0..n  1] by bu bblesort
// In pu t: An array A[0..n  1] of orde rablee le m e n ts
// O u tpu t: Array A[0..n  1] sorte di n asce n din gorde r
for i  0 to n-2 do
for j  0 to n-2  i do
i f A[ j  1]  A[ j ] swap A[ j ] an d A[ j  1]
What is the time efficiency?
n- 2 n- 2 -i
2
1


(
n
)

i 0 j 0
Sequential Search – Brute Force
Find whether a search key is present in an array
// S e archk e yK in A[0..n-1]
ALGO RITHMSequentialSearch( A[0..n ], K )
A[n ]  K
i0
wh i leA[i ]  K do
i  i 1
if i  n re tu rni
e l sere tu rn-1
What is time efficiency of this algorithm?
Brute-Force String Matching
Find a pattern in the text: Pattern – ‘NOT’, text –
‘NOBODY_NOTICED_HIM’
Typical Applications – ‘find’ function in the text editor, e.g., MS-Word,
Google search
ALGO RITHMBFStringMatch(T [0..n  1], P[0..m  1])
for i  0 to n-m do
j0
while j  m and P[ j ]  T [i  j ]
j  j 1
if j  m re turni
re turn-1
What is the time efficiency of this algorithm?
Closest-Pair and Convex Hull Problems by
Brute Force
Closest-Pair problem
• Given n points in a plane, find the closest pair
• How to solve this problem and what is the time efficiency of
this algorithm?
Convex-Hull problem
• Convex hull is the tightest convex polygon that bounds a set of
n points in a plane
• Convex polygon – any two points in this polygon results in the
inclusion of the segment that links these two points also in this
polygon
Convex/NonConvex Polygons
Convex Hull
Imagine a rubber band around a set of nails
Nails touched by the band  extreme points
P6
P7
P2
P8
P3
P4
P5
P1
Solve Convex-Hull Problem
Connect any pair of points by a line segment.
Each line segment partitions the plane to the two half planes
If all the n points are on the same side of this line segment
Such a line segment is an edge of the convex-hull polygon
What is the time efficiency of this Brute-Force algorithm?
For each possible pair of points, we need to check whether all
the remaining n-2 points are on the same side of the line
segment that connects these pair of points.
For Sorting, String Matching, and Convex-Hull problems, we
will revisit them by designing more efficient algorithms.
Exhaustive Search
A brute-force approach to combinatorial problem
• Generate each and every element of the problem’s domain
• Then compare and select the desirable element that satisfies
the set constraints
• Involve combinatorial objects such as permutations,
combinations, and subsets of a given set
• The time efficiency is usually bad – usually the complexity
grows exponentially with the input size
Three examples
• Traveling salesman problem
• Knapsack problem
• Assignment problem
Traveling Salesman Problem
Find the shortest tour through a given n cities that visits each
city exactly once before returning to the starting city
Using graph model: city  vertex, road  edge, length of the
road  edge weight.
TSP  shortest Hamiltonian Circuit – a cycle that passes
through all the vertices of the graph exactly once
Exhaustive search:
• List all the possible Hamiltonian circuits (starting from any
vertex)
• Ignore the direction
• How many candidate circuits do we have?  (n-1)!/2
• Very high complexity
TSP Example
2
a
5
3
7
8
c
1
Tour
b
d
Length
a ---> b ---> c --->d ---> a
l = 2 + 8 + 1 + 7 = 18
a ---> b---> d ---> c ---> a
l = 2 + 3 + 1 + 5 = 11
a ---> c ---> b ---> d --->a
l = 5 + 8 + 3 + 7 = 23
a ---> c ---> d ---> b ---> a
l = 5 + 1 + 3 + 2 = 11
a---> d ---> b ---> c ---> a
l = 7 + 3 + 8 + 5 = 23
a ---> d ---> c ---> b ---> a
l = 7 + 1 + 8 + 2 = 18
optimal
optimal