Transcript document

Session 11
Revisiting Graph Algorithms
Algorithm Patterns
Algorithm Efficiency
Difficult and Unsolvable Problems
Fall 2008
NOEA – Computer Science
1
Læringsmål
• Kunne redegøre for begrebet algoritme pattern
• Kende nogle forskellige algoritme patterns
• Kunne redegøre for algoritmekompleksitet og
forskellige kompleksitetsklasser
• Kunne forklare eksempler på algoritmer i forskellige
kompleksitetsklasser
Fall 2008
NOEA – Computer Science
2
Example: Prim’s Algorithm
Fall 2008
NOEA – Computer Science
3
Example: Dijkstra’s Algorithm
Fall 2008
NOEA – Computer Science
4
Greedy Algorithms
• C: a collection of candidates
• S: a collection of candidates representing the partly
solution, eventually becoming the total solution
• Solution: a function that determines if a collection of
candidates is a solution to the problem
• Feasible: a function that checks if collection of
candidates may become a solution (not necessary an
optimal solution, but any solution)
• Select: a function that returns a measure for how
good a candidate is
Fall 2008
NOEA – Computer Science
5
The Greedy Pattern
proc Greedy( in C: <<collection of candidates>>;
out S: <<collection of candidates>>)
pre C is a collection of all candidates and a solution exists
post S is a collection of candidates constituting an optimal solution
S:= []; -- initially S is empty
while not Solution(S) and C <> [] do
x:= an element in C that maximises Select(x)
C:= C - [x] -- x is removed from the collection of candidates
if Feasible(S+[x]) then S:= S+[x]; -- x is added to the solution
endwhile
endproc
Fall 2008
NOEA – Computer Science
6
Prim’s Algorithm
and
the Greedy Pattern
proc prim(in G: Graph, v: vertex; out T: Tree)
pre G is connected, v is in G
post T is a minimum spanning tree for G
T:= [v]
mark(v)
while there are unvisited vertices do
Select the minimum weight edge (w,u)
from a vertex w in T to an unvisited vertex u
mark(u)
add u and (w,u) to T
endwhile
endproc prim
What happened
to Feasible?
Fall 2008
NOEA – Computer Science
7
Kruskal’s Algorithm
(finding a minimum spanning tree)
Input: a set of edges, E Output: a tree, T
T:= []; -- T, initially T is empty
while noOfEdges(T) < n-1 and E <> [] do
x:= an edge, (v,w), from E with minimum weight
E:=E - [x] – remove x from the candidates
if (v,w) + T is acyclic then
T:=T+[x] -- x is added to the solution
fi
endwhile
Fall 2008
Exercise:
Define:
C:
S:
Solution():
Feasible():
Select():
Compare with the pattern.
NOEA – Computer Science
8
Dijkstra’s Algorithm and the Greedy Pattern
proc dijkstra(in G: GraphMatrix, v: vertexNo; out w: arrayOfCosts)
pre
true
post
w contains the length of the shortest path from v to all other
vertices in G (if no path exists to u, then w[u]==“infinity”)
S:= [1]
for v:= 1 to G.size do
w[v]:= G[1,v];
for v:= 2 to N do
select u not in S, so w[u] is a minimum in w
S:= S + [u];
for each u not in S do
if w[u] > w[v] + G[v,u] then w[u]:= w[v] + G[v,u];
endfor
endproc dijkstra
Does this follow the
greedy pattern?
Fall 2008
NOEA – Computer Science
9
Algorithm Patterns
•
•
•
•
•
•
•
Fall 2008
Sweep Algorithms
Search Algorithms
Merge Algorithms
Divide and Conquer Algorithms
Greedy Algorithms
Backtracking Algorithms
Dynamic Programming – improving
efficiency of recursive algorithms
NOEA – Computer Science
10
Divide and Conquer Algorithms
proc DivCon(in P: Problem; out S: Solution)
if P is simple then
Simple(P, S)
else
Divide(P, P1, P2)
DivCon(P1, S1)
DivCon(P2, S2)
Combine(S, S1, S2)
endif
endproc DivCon
Fall 2008
NOEA – Computer Science
11
Sorting and Divide and Conquer Algorithms
proc Sort(in S: Sequence; out S’: Sequence)
if S.length>1 then
Split(S, S1, S2)
Sort(S1, S’1)
Sort(S2, S’2)
Join(S’1, S’2, S’ )
endif
endproc Sort
• easy split/hard join
• hard split/easy join
Fall 2008
NOEA – Computer Science
12
MergeSort
proc mergeSort(inout v: vector; in l, u: int)
pre true
post The segment v[l..u] is sorted in increasing order
if l<u then
m:= (l+ u) div 2
mergeSort(v,l,m)
mergeSort(v,m+1,u)
merge(v,l,m,u)
-- total merge of v[l..m] and v[m+1..u]; returns v
fi
endproc mergeSort
Fall 2008
NOEA – Computer Science
13
QuickSort
proc quickSort(inout v: vector; in l, u: int)
pre true
post the segment v[l..u] is sorted in increasing order
if l<u then
p:= -- Select some index as pivot (the first for instance)
-- do the pivot process, so each element in v[l..p-1]
-- is less than each element in v[p+1..u]
quickSort(v,l,p-1)
quickSort(v,p+1,u)
fi
endproc quickSort
Fall 2008
NOEA – Computer Science
14
Efficiency of Merge- and QuickSort
• mergeSort:
– O(n log n) in worst case
– O(n) additional memory
– In average a larger overhead than quickSort
• quickSort:
– In average :
• O(n log n) (worst case O(n2) – if for instance input is
sorted)
– additional memory for the recursion stack:
• O(log n) (O(n) in worst case)
– Choosing pivot as ”mean of three” (or the median) will in
practice often make worst case very unlikely.
Fall 2008
NOEA – Computer Science
15
Some Sorting Algorithms
• See them work:
http://cg.scs.carleton.ca/~morin/misc/sortalg/
Fall 2008
NOEA – Computer Science
16
Backtracking algorithms
(TicTacToe, 8 Queens, Sudoko and others)
• A recursive strategy:
– in each step (j) the algorithm “guesses” a partial
solution (picking a candidate at random)
– If there is a candidate to pick, the algorithm calls it
selves recursively for step j+1
– If there at some step is no candidate to pick for the
solution, then the algorithm returns (backtracks) to
the previous level
Fall 2008
NOEA – Computer Science
17
8-Queens Problem
• Place 8 queens on a chessboard, so no queen can attack an
other. (A queen may attack horizontally, vertically and
diagonally):
Fall 2008
NOEA – Computer Science
18
The Backtrack-Pattern
proc backtrack(in j)
if j<= n then
while any more candidates at level j and a solution is not found do
choose some candidate
if the candidate is a possible solution at this level then
add the candidate to the total solution
backtrack(j+1)
if no more candidates at level j+1 then
remove the chosen candidate from level j from the total solution
choose a new candidate
fi
fi
endwhile
endproc backtrack
Fall 2008
NOEA – Computer Science
19
Dynamic Programming
• Improving running time for recursive algorithms using additional
space:
• For instance. Finding the nth Fibonacci number:
func fib(in n)
if n<=1 then
return n
else
return fib(n-1)+fib(n-2)
fi
endfunc fib
• efficiency (draw a recursion tree)?
Fall 2008
NOEA – Computer Science
20
Recursion Trees
• The execution of a recursive algorithm can be
modelled using a tree, where each node models a
recursive call:
– The number of nodes indicates the time complexity
– The depth of the tree indicates the size of the
recursion stack, and hence the additional space
needed due to recursion
Fall 2008
NOEA – Computer Science
21
Improving Running Time for Fib
// We will use an global array:
t: array[0..max] of int
func fib1(in n)
if t[n] = empty then
if n<=1 then
t[n]:=n
else
t[n]:= fib(n-1) + fib(n-2)
fi
fi
fib:= t[n]
endfunc
Tail Recursion!
Fall 2008
NOEA – Computer Science
22
Tail Recursion
• If the recursive call is the last statement in
the method, then it is called tail recursion.
• In the case of tail recursion, recursion may
be removed:
– Since the algorithm returns just after returning
from the recursive call, there is no need for
remembering temporary results at the recursion
stack
– In this case the recursive algorithm may be
formulated iteratively with no extra costs
Fall 2008
NOEA – Computer Science
23
A Word on
Divide and Conquer and Efficiency
• The efficiency of solution developed applying Divide
and Conquer depends on how the problem is divided
into sub problems:
– Binary Search: The problem is halved at each step – very
efficient: O(log n)
– MergeSort: The problem is divided into two sub problems at
each step. The sub problems are of half the size of the
original problem: O(nlogn)
– Fibonacci-numbers or the Towers of Hanoi: the problem is
divided into two sub problems each of almost the same size
as the original problem (n-1): O(2n)
Fall 2008
NOEA – Computer Science
24
Exercise
1. Write an iterative version of Fib, that uses
no extra space. (Remember the version on
slide 20 has tail recursion)
Fall 2008
NOEA – Computer Science
25
Recursive Data Structures
• General Trees
• Lists of lists
• Composite Pattern
Fall 2008
NOEA – Computer Science
26
General Trees
• Structure:
– A single node (the
root), or
– A root with an
arbitrary number of
children (subtrees)
• Cannot be implemented as
binary trees since the number of
subtrees may vary a lot
• For instance:
– Directory structure
on a computer.
– Organisation
structure
– Project Management
A
C
B
E F G
D
H
I
27
Implementation of General
Trees
A
• Recursive Structures:
– Linked implementation:
general lists:
• Lists with list-elements
– Object-oriented:
• Composite Pattern
C
B
E F G
D
H
I
28
Linked Implementation
29
The Object-Oriented
Implementation: The Composite
Pattern
AbstractTree
Leaf
0..*
Tree
•Examples in C#:
Organisation
Project
File Directories
30
The Algorithmic Space
Unsolvable
Problems
Difficult
Problems
Practical Solvable
Problems
Fall 2008
NOEA – Computer Science
31
Practical Solvable Problems
• Problems that can be solved by algorithms with
polynomial running time.
• That is, algorithms with complexity
O(nk)
k been some fixed integer constant
Fall 2008
NOEA – Computer Science
32
Some Sample Complexities
• Kh fig.
Fall 2008
NOEA – Computer Science
33
Some Difficult Problems - O(2n)
• Traveling Salesman
– Given a collection of towns connected with roads or railroads
in a weighted graph:
– find the shortest path from one town (the source) that visits
all other towns exactly once and ends in the source (a cycle)
• Hamilton-Circuit:
– Given some graph: does there exist a cyclic path passing all
vertices?
• Scheduling Problems:
– Give a collection of lectures, a collection of classes and a
collection rooms:
– Make schedule where no resource is booked more than
once in same period.
Fall 2008
NOEA – Computer Science
34
• Logic Satisfiability:
– Given some arbitrary Boolean expression:
A && B || !C && D …etc
– Is it possible to assign truth values to all the variables, so the
expression becomes true?
• Map Colouring
– Any map can be coloured with four colours, so no two adjacent
countries have the same colour.
– Many maps can be coloured using only three colours.
– Only maps with no points where an odd number of countries is
adjacent can be coloured with two colours.
– Determine if a map can be coloured with three colours.
• Graph Partition
At most O(logn)
worse than an
optimal solution,
n is the number
of vertices.
Fall 2008
– Split the vertices of a graph in two sets (approximately of the same
size – balanced), so a minimum number of edges crosses the
boundary between the two sets.
– Many applications uses this: data clustering in data warehouse and
data mining, divide-and-conquer solutions, parallel architectures
and algorithms, packet routing in distributed networks, integrated
circuit layout and many more.
– O(logn) approximations in polynomial time are known
NOEA – Computer Science
35
Unsolvable Problems
• Automatic generation of programs
• Automatic proof of correctness of a program
• The Halting Problem:
– Is it possible to write an algorithm that given an arbitrary
program as input determine whether the program terminates
(halts) or loops forever?
Fall 2008
NOEA – Computer Science
36
The Halting Problem
• We are going to prove that the Halting Problem has
no algorithmic solution. We will make the proof by
showing a contradiction:
• We will assume that there is an algorithmic solution,
and then show that this assumption leeds to a
contradiction.
• So assume that the algorithm halt(a) returns true, if
the program a halts and false if not.
Fall 2008
NOEA – Computer Science
37
No consider the following program called evil:
void evil(){
if(halt(evil()))
while(true);//indefinite loop
else
break;
}
• If halt(evil()) returns true (that is that evil() will terminate), then
evil() enters in an infinite loop (loops forever). So evil() does not
terminate after all???
• If halt(evil()) returns false (that is that evil() will not terminate),
then evil() enters the else part and terminates???
• So in either case halt(evil()) gives the wrong answer, and hence
our assumption about the existence of halt is wrong, and we
conclude that halt cannot exist?
Fall 2008
NOEA – Computer Science
38
Læringsmål
• Kunne redegøre for begrebet algoritme pattern
• Kende nogle forskellige algoritme patterns
• Kunne redegøre for algoritmekompleksitet og
forskellige kompleksitetsklasser
• Kunne forklare eksempler på algoritmer i forskellige
kompleksitetsklasser
Fall 2008
NOEA – Computer Science
39