CSE408
Fundamentals of Algorithms
Lecture #1
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
What is an algorithm?
An algorithm is a sequence of unambiguous instructions
for solving a problem, i.e., for obtaining a required
output for any legitimate input in a finite amount of time.
problem
algorithm
input “computer” output
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Notion of algorithm and problem
problem
algorithm
input “computer” output
(or instance)
algorithmic solution
(different from a conventional solution)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Some Well-known Computational Problems
Sorting
Searching
Shortest paths in a graph
Minimum spanning tree
Primality testing
Traveling salesman problem
Knapsack problem
Chess
Towers of Hanoi
Program termination
Some of these problems don’t have efficient algorithms,
or algorithms at all!
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Basic Issues Related to Algorithms
How to design algorithms
How to express algorithms
Proving correctness
Efficiency (or complexity) analysis
Optimality
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm design strategies
Brute force Greedy approach
Divide and conquer Dynamic programming
Decrease and conquer
Backtracking and branch-and-bound
Transform and conquer
Space and time tradeoffs
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Analysis of Algorithms
How good is the algorithm?
• Correctness
• Time efficiency
• Space efficiency
Does there exist a better algorithm?
• Lower bounds
• Optimality
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
What is an algorithm?
Recipe, process, method, technique, procedure,
routine,… with the following requirements:
1. Finiteness
terminates after a finite number of steps
2. Definiteness
rigorously and unambiguously specified
3. Clearly specified input
valid inputs are clearly specified
4. Clearly specified/expected output
can be proved to produce the correct output given a valid input
5. Effectiveness
steps are sufficiently simple and basic
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Why study algorithms?
Theoretical importance
• the core of computer science
Practical importance
• A practitioner’s toolkit of known algorithms
• Framework for designing and analyzing algorithms for new problems
Example: Google’s PageRank Technology
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Euclid’s Algorithm
Problem: Find gcd(m,n), the greatest common divisor of two
nonnegative, not both zero integers m and n
Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?
Euclid’s algorithm is based on repeated application of equality
gcd(m,n) = gcd(n, m mod n)
until the second number becomes 0, which makes the problem
trivial.
Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Two descriptions of Euclid’s algorithm
Step 1 If n = 0, return m and stop; otherwise go 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. Go to
Step 1.
while n ≠ 0 do
r ← m mod n
m← n
n←r
return m
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Other methods for gcd(m,n) [cont.]
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factors
and return it as gcd(m,n)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Fundamentals of Algorithmic Problem Solving
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Two main issues related to algorithms
How to design algorithms
How to analyze algorithm efficiency
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm design techniques/strategies
Brute force Greedy approach
Divide and conquer Dynamic programming
Decrease and conquer Iterative improvement
Transform and conquer Backtracking
Space and time tradeoffs Branch and bound
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Analysis of algorithms
How good is the algorithm?
• time efficiency
• space efficiency
• Correctness
Does there exist a better algorithm?
• lower bounds
• optimality
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
