Transcript A(n)

Chapter 4
Algorithmic Foundation
of
Computer Science
Computer Science/Ch. Algorithmic Foundation of CS
4-1
What is an algorithm?
• Example:
ingredients
Baking
a
cake
software
hardware
recipe
oven
baker
cake
• Software : algorithm
Computer Science/Ch. Algorithmic Foundation of CS
4-2
What is an algorithm?
• Formal definitions:
– A sequence of operations that can solve a specified problem
– A sequence of computational steps that transform the input
into the output
– A tool for solving a well-specified computational problem
– A well-ordered collection of unambiguous and effectively
computable operations that when executed produces a result
and halts in a finite amount of time
• Algorithmics:
– The area of human study, knowledge, and expertise that
concerns algorithms.
Computer Science/Ch. Algorithmic Foundation of CS
4-3
History
• 400 and 300 B.C. :
– Greek mathematician: Euclid.
– GCD (greatest common divisor)
– The first non-trivial algorithm
• Algorithms came from:
– Persian mathematician: Mohammed al-Khowarizmi
– When written in Latin: Algorismus
• Key person : Alan Turing
– English mathematician
– Turing Machine: Finite Automata
» Develop some results of the theory of algorithms, that
concern the capabilities and limitations of machineexecutable algorithms
– Turing Award:
» Nobel Prize of Computer Science
Computer Science/Ch. Algorithmic Foundation of CS
4-4
Problem and Instance
• Problem:
– sorting problem:
» sorting a sequence of numbers into nondecreasing order
– input : A sequence of n number <a1,a2,...,an>
– Output: A permutation (reordering) <a1',a2', ..., an'> of input
sequence such that a1'<a2'< ... < an'.
– Example:
<31,41,59,26,20> => <20,26,31,41,59>
• Instance :
– a particular input sequence of a problem
• Correct algorithm :
– for every input sequence, the algorithm halts with the correct
output.
Computer Science/Ch. Algorithmic Foundation of CS
4-5
Why study algorithms?
• More needs of high speed computations
• How to accomplish that?
– High speed computers
– Highly efficient algorithms
Note:
High speed
computers
High speed
computations
Quicksort
on PC/XT
T
Insertion
sort on
VAX 8800
T : time
N : # of data elements
Computer Science/Ch. Algorithmic Foundation of CS
4-6
N
How to solve problems?
• Algorithmic methods:
– Getting it done methodically
• Correctness of algorithms:
– Getting it done right
– Prove the correctness of algorithms
– How?
» By induction ...
• Efficiency of algorithms:
– Getting it done cheaply or quickly
• Inefficiency and Intractability:
– You can't always get it done cheaply
• Noncomputability and Undecidability
– Sometimes you can't get it done at all
Computer Science/Ch. Algorithmic Foundation of CS
4-7
Performance of algorithms
• How to determine the performance of an
algorithm ?
– depends on the size of input.
– use special notations to denote the growth rate.
• How to distinguish the easy problems
and the difficult problems?
– the complexity of problems
– easy problem
» a problem which can be solved by a polynomial time
algorithm.
– difficult problem
» a problem which can only be solved by some
exponential time algorithms.
» NP-Complete problems.
Computer Science/Ch. Algorithmic Foundation of CS
4-8
Difficult problems
• Partition problem:
– Input : S = {1, 7, 10, 9, 5, 8, 3, 13}
– Output : S1 and S2 s.t. sum of S1 = sum of S2.
– Example:
S1 = { 1, 10, 9, 8 } S2 = { 7, 5, 3, 13 }
• Traveling salesperson problem:
– Find a minimum length tour
4
3
3
3
2
5
1
8
6
Computer Science/Ch. Algorithmic Foundation of CS
4-9
Easy problems
• Minimum spanning tree:
– Find a tree with minimum length
• One-center problem:
– Find a smallest circle which can cover all points
Computer Science/Ch. Algorithmic Foundation of CS
4-10
Analysis of algorithms
• How to analyze?
– Empirical approach
» actually running time.
– Theoretical approach
» determining mathematically the quantity of resources
needed by each algorithm as a function of the size of
the instances considered.
• How to measure?
– Use a particular step or an elementary operation.
– Examples:
Operation
Problem
Find x in a list of names
Comparison
Multiply two matrices
Multiplication
Sort n integers
Comparison/
Data Movement
• What measurement?
– Use O-notation, -notation and -notation.
Computer Science/Ch. Algorithmic Foundation of CS
4-11
Complexity
• Question:
– Let A1 and A2 be two algorithms that solve the same
problem. Let the time complexity of A1 and A2 be O(n2) and
O(n) respectively.
– Would the program for A2 run faster than that of A1 ?
• Answer:
– Not exactly!
• Example:
– A1 : n2
– A2 : 100n
Note:
100n > n2, for n < 100.
Computer Science/Ch. Algorithmic Foundation of CS
4-12
Complexity
• How Important Is Order ?
– Time Complexity Functions
problem size
10
102
103
104
lg n
3.3
6.6
10
13.3
n
10
102
103
104
nlg n
0.33*102 0.7*103 104
2n
1024
1.3*1030 >10100
>10100
n!
3*106
>10100 >10100
>10100
functions
Computer Science/Ch. Algorithmic Foundation of CS
4-13
1.3*105
What complexity?
• What complexity do we need?
– Best-case complexity
– Worst-case complexity
– Average-case complexity
• Definition:
– Let Dn be the set of inputs of size n for the problem under
consideration, and let I be an element of Dn.
– Let t(I) be the number of basic operations performed by the
algorithm on input I.
– Worst-Case Complexity : W(n)
» W(n) = max { t(I) | I  Dn}
– Best-Case Complexity : B(n)
» B(n) = min { t(I) | I  Dn}
– Average-Case Complexity: A(n)
» p(I) : probability that input I occurs.
A(n) =  p(I) t(I)
IDn
Computer Science/Ch. Algorithmic Foundation of CS
4-14
Example of analysis
• Sequential search:
– Problem: Find x in list L.
– Basic operation: Comparison of x with a list entry.
• Analysis:
– Best case:
» B(n) = 1
– Worst case:
» W(n) = n
– Average case: Assume all elements are distinct.
– Case 1: Suppose x is in L
» Ii : represent the case where x appears in the i-th
position in L.
» t(I) : the # of comparisons.
» p(Ii) : prob. that Ii occurred.
» t(Ii) = i, for 1  i  n.
n
=> A(n) =  p(Ii)t(Ii) =  (1/n) i
i=1
n
i=1
n
= (1/n)  i = (1/n)(n(n+1)/2)=(n+1)/2
i=1
Computer Science/Ch. Algorithmic Foundation of CS
4-15
Example of analysis
– Case 2: x si not in L
» (n+1) inputs should be considered.
» In+1 : represent the case where x is not in L.
» q : prob. that x is in L.
» p(Ii) = q/n, for 1 <= i <= n
» p(In+1) = 1- q.
n+1
A(n) =  p(Ii)t(Ii)
i=1
n
=  (q/n)i + (1-q)n
i=1
= (q/n)(n(n+1))/ 2+ (1-q)n
= q((n+1)/2) + (1-q)n
Note:
When q=1, A(n) = (n+1)/2
When q=1/2, A(n) = (n+1)/4 + n/2
Computer Science/Ch. Algorithmic Foundation of CS
4-16
Sorting problem
• Sorting problem:
– Input: a list of numbers
– Output: increasing order
– Example: 5, 7, 2, 8, 3 => 2, 3, 5, 7, 8
• Selection sort:
1. Get values for n and the n items
2. Set the marker for the unsorted section at the end of the list
3. Repeat steps 4 thru 6 until the unsorted section of the list is
empty
4. Select the largest number in the unsorted
section of the list
5. Exchange this number with the last number in
the unsorted section
6. Move the marker for the unsorted section
forward one position
7. Stop
5, 7, 2, 8, 3 |
5, 7, 2, 3 | 8
5, 3, 2 | 7, 8
2, 3 | 5, 7, 8
2 | 3, 5, 7, 8
| 2, 3, 5, 7, 8
Computer Science/Ch. Algorithmic Foundation of CS
# of comparisons:
(n-1)+(n-2)+ ... + 2 + 1
= n*(n-1)/2
4-17
Binary search
<X
X
>X
Time:
# of comparisons: lg n
Computer Science/Ch. Algorithmic Foundation of CS
4-18
Pattern matching
• Pattern matching problem:
–
–
–
–
–
Input: a pattern P and a text T
Output: All occurrences of pattern P
Example:
Text:
KLMNPAQKKAQJDS
Pattern:
AQ
• Time:# of comparisons:
–
–
–
–
Length of T : n
Length of P : m
Best case : O(n)
Worst case: O(m*n)
Computer Science/Ch. Algorithmic Foundation of CS
4-19
When things get out of hand
• Exponential algorithm:
– An algorithm which needs O(2n) steps to solve the problem
• Intractable problems:
– those problems which have no polynomially bounded
algorithm to solve the problem exists
• Example:
– Bin-packing problem:
» Given an unlimited number of bins of volume 1 unit,
and n objects, all of volume between 0.0 and 1.0, find
the minimum number of bins needed to store the n
objects.
• Approximation algorithms:
– provide a close approximation to the solution of the
problem.
– Example: Bin-packing problem
» First-Fit
Computer Science/Ch. Algorithmic Foundation of CS
4-20