Transcript CS4710 - Georgia Institute of Technology

CS4710
Algorithms
What is an Algorithm?
 An algorithm is a procedure to perform
some task.
1. General - applicable in a variety of situations
2. Step-by-step - each step must be clear and
concise
3. Finite - must perform task in a finite amount of
time
4. Note: Is not the same as an actual
implementation
Common algorithmic categories
 Recursion
 Divide and conquer
 Dynamic programming
 Greedy
Recursion
 Definition:
 An algorithm defined in terms of itself is said to use
recursion or be recursive.
 Examples
 Factorial
1! = 1
n! = n x (n-1)!, n > 1
 Fibonacci sequence
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)
Recursion
 Recursion is natural for some problems
 Many solutions can be expressed easily using
recursion
 Lead often to very elegant solutions
 Extremely useful when processing a data structure
that is recursive
 Warning!
 Can be very costly when implemented!
 Calling a function entails overhead
 Overhead can be high when function calls are
numerous (stack overflow)
 Some software is smart enough to optimize recursive
code into equivalent iterative (low overhead) code
Recursive factorial algorithm
(written in pseudo code)
factorial(n)
if n=1
return 1
else
return n * factorial(n-1)
Recursive factorial code
# a recursive factorial routine in Python
def fact(n):
if n == 1:
return 1
else:
return n * fact(n - 1)
Recursive factorial code
# a recursive factorial routine in Perl
sub factorial_recursive {
my ($n) = shift;
return 1 if $n = 1;
return $n * factorial_recursive($n – 1);
}
Non-recursive factorial code
# an iterative factorial routine in Perl
sub factorial_iterative {
my ($n) = shift;
my ($answer, $i) = (1, 2);
for ( ; $i <= $n; $i++) {
$answer *= $i;
}
return $answer);
}
Divide and conquer
 Secrets of this technique:
 Top-down technique
 Divide the problem into independent smaller
problems
 Solve smaller problems
 Combine smaller results into larger result
thereby “conquering” the original problem.
 Examples
 Mergesort
 Quicksort
Dynamic programming
 Qualities of this technique:
 Useful when dividing the problem into parts creates
interdependent sub-problems
 Bottom-up approach
 Cache intermediate results
 Prevents recalculation
 May employ “memo-izing”
 May “dynamically” figure out how calculation will
proceed based on the data
 Examples
 Matrix chain product
 Floyd’s all-pairs shortest paths problem
Matrix chain product
Want to multiply matrices
AxBxCxDxE
We could parenthesize many ways
1. (A x (B x (C x (D x E))))
2. ((((A x B) x C) x D) x E)
3. …
Each different way presents different
number of multiplies!
How can we decide on a wise approach?
Dynamic programming
applied to matrix chain product
Original matrix chain product
A x B x C x D x E (ABCDE for short)
Calculate in advance the cost (multiplies)
AB, BC, CD, DE
Use those to find the cheapest way to form
ABC, BCD, CDE
From that derive best way to form
ABCDE
Greedy algorithms
 Qualities of this technique:





Naïve approach
Little to no look ahead
Fast to code and run
Often gives sub-optimal results
For some problems, may be optimal
 Examples where optimal
 MST of a graph
Data structures do matter
 Although algorithms are meant to be general,
1. One must choose wisely the representation for data,
and/or
2. Pay close attention to the data structure already
employed, and/or
3. Occasionally transfer the data to another data
structure for better processing.
 Algorithms and data structures go hand in
hand
1. The steps of your algorithm…
2. What your chosen data structure allows easily…
Some of python’s built-in types and
data structures
 type int - integers
 type float - floating point numbers
 type str - Strings or text
 python sequence or list - (similar to an array in
other languages, but more powerful than a true
array)
 python dictionary - basically a hash table where
each data value has an associated key used for
lookup.
Some of Perl’s built-in data structures
 $scalar
number (integer or float)
string (sequence of characters)
reference (“pointer” to another data structure)
object (data structure that is created from a class)
 @array (a sequence of scalars indexed by
integers)
 %hash (collection of scalars selected by strings
(keys))
Perl (and python) arrays are
powerful!
 Can dynamically grow and shrink (not normal
array behavior)
 Need a queue? (FIFO)
Can use an array
Add data with push operator (enqueue)
Remove using shift operator (dequeue)
 Need a stack? (LIFO)
Can use an array
Push data with push operator (push)
Pop data using pop operator (pop)
Advanced data structures
Linked lists
Circular linked lists
Doubly linked lists
Binary search trees
Graphs
Heaps
Binary heaps
Hash tables
Linked list
 Consists of small node structures
 Each node
o Stores one data item (data field)
o Stores a reference to next node (next field)
 Allows non-contiguous storage of data
 Is much like a magazine article
Linked list

Benefits
o
o



Can insert more data (more nodes) in middle of list
efficiently
Can remove data from middle efficiently
Word processors typically store text using linked lists
Allows for very fast cutting and pasting.
Cons
o
o
Takes up more space (for the references)
True array would take up less space
Graphs
 Many representations
Adjacency lists
Adjacency matrix
 Must consider representation when processing
 Some graphs are weighted, others not
 Some are directed, others have implied bidirection
Graphs
 Graph Searches
 Depth-first search
 Uses stack
 Yields a path
 Exhaustive
 Breadth-first search
 Uses a queue
 Yields a shortest path
 Exhaustive
Graphs
 Greedy algorithms for graphs
Minimum spanning tree (MST)
 Prim’s algorithm
• Grow an MST from a single node
• Optimal solution
 Kruskal’s algorithm
• Keep picking cheap edges
• Optional solution