Transcript Complexity, Origami, etc.

Complexity, Origami, etc.
Big Oh
Traditional Origami
Fold and cut
Analyses of Algorithms
• What resources does an algorithm take?
– runtime
– space
• Calculate as function of size of input
– size of set
– magnitude of input values
• Typical problems
– sort, search, paths/circuits of graph, Fibonacci, GCD
– origami, 'off-line Tetris', piano-movers problem
Time complexity
•
•
Can write program, run program and
record time…
Want machine independent analysis in
terms of inputs
– magnitude of inputs, size of set
•
Count basic operations
– For sorting, typically count compares
•
•
Some judgment required
Want bounds, not necessarily details
Example
• How many steps required to find average of N numbers
in an array?
• Pseudo-code (array is aa, size n
sum = aa[0]; set sum to the first number
for (i=1;i<n;i++) { go through the array…
sum = sum + aa[i]; } adding in the numbers
How many steps?
initialize sum
initialize i
{compare i to n
add aa[i] to sum
increment i
}
1
1
loop done completely n-1 times
1 compare operation
3*(n-1) + 3
Big Oh
• Formal definition of upper bounds
A function g(n) is said to be O(f(n)) if and only if the
following is true:
There exists a number n0 and a number c such
that is n>n0
g(n) <= c*f(n)
English: beyond a certain value of n, f(n) is an
upper bound for g(n).
You can use a coefficient c.
Jargon
• You say
– g(n) is O(f(n))
– g(n) = O(f(n))
– g(n) є O(f(n)) (contained in, belongs to, is in)
• Generally, the f(n) functions are standard
– O(log n), log NOTE: base doesn't matter
– O(n), linear
– O(n2), n-squared, quadratic
– O(nk) for some k, polynomial, also called P
– O(2n), exponential
These may be 'NP' or NP-Complete
Exercise
• What is the relationship between
log2(n) and
ln(n) by definition: loge(n)
log n
• Why does base not matter?
• Because
logb(n) = logb(a)*loga(n)
this is the
coefficient
NP, NP-complete
• Formal definition: an algorithm is NP if it can be
performed by a non-deterministic Turing machine.
• Less formal: an algorithm is NP if it can be done by a
process in which there are a finite number of choices,
and assuming the correct choice is made, the process is
polynomial. The correctness can be checked in
polynomial time. If all choices must be tried, the
algorithm is O(2n)
• NP-complete refers to a set of problems for which there
are NP algorithms that have been shown to be equally
hard
– (can convert one to the other on polynomial time).
– These include: traveling salesman, satisfying logical formulas,
subgraph isomorphism.
– BIG question in computer science proving either P = NP or P
proper subset of NP.
Examples
• g(n) = 5n+10 is O(n)
Let n0=10, c = 6, then if n>10
5*n+10 <= 5*n+n = 6*n
• g(n) = 3n2+5n+100 is O(n2)
Let n0 = 100, c=6, then if n>100
3n2+5n+100 <= 5n2+5n+100<=5n2+6n<=
5n2+n*n<= 6n2
log n
• log n is O(n)—that is, log n is bounded by
O(n)
Assume base 2.
Let n0=2, c=1
log n <= n Why? Raise 2 to each
n <=2n
2<22, 3<23, etc.
Big Oh
• This is an asymptotic, upper bound
eventually, this is the
n>n0 condition
May not be a tight
bound.
Bounds
• If g(n) is O(n), it is also O(n2), O(nk), O(2n)
• But, n2 is not O(n)? Why?
• Suppose there was an n0 and a c,
n2<=c*n
Divide both sides by n,
n<c FALSE, can choose n>c and n>n0
Exercises
• g(n) = 4n3+n+10. Show g(n) is O(n3)
• g(n) = log(n) * n. This is called log linear.
Show it is O(n).
Growth rates illustrated
n=1 n=2 n=4 n=8 n=16
n=32
O(1)
1
1
1
1
1
1
O(logn)
0
1
2
3
4
5
O(n)
1
2
4
8
16
32
O(nlogn)
0
2
8
24
64
160
O(n2)
1
4
16
64
256
1024
O(n3),
1
8
64
512 4096
O(2n)
2
4
16
235 65536 4294967296
32768
Methods
• For loops,
multiply number of steps in loop by
upper bound on number of times loop is
run
• For conditionals, add step for doing
condition plus maximum of each of the
branches
Lower bounds (omega)
• To give better performance estimates, we
may also want to give lower bounds on
growth rates
• Definition (omega): g(n) = Ω(f(n))
if there exist some constants c and n0
such that g(n) ≥ cf(n) for all n ≥ n0
• This says, g(n) grows at least this much
“Exact” bounds
• Definition (Theta): g(n) = Θ(f(n)) if and only
if g(n) =O(f(n)) and g(n) = Ω(f(n)).
• An algorithm is Θ(f(n)) means that f(n) is a
tight bound (as good as possible) on its
running time.
– On all inputs of size n, time is ≤ f(n)
– On all inputs of size n, time is ≥ f(n)
Complexity
• Bounds (such as Big Oh) are for specific
algorithms
– Tight[er] bounds are better than looser bounds
– Sometimes there are reports giving average bounds
• Problems may have different algorithms with
different bounds
• Sometimes possible to prove result about a
problem as opposed to an algorithm
– There is no method that is better than …
Good source
Algorithm (Run Time) Analysis
www.cs.uic.edu/~liub/teach/ cs2012004/cs201-algo-analysis.ppt
Computing Fibonacci numbers
• Recursive program
1 long int fib(n) function returns integer
2
3
4
if (n <= 1)
which case?
return 1; 0,1 case return 1
else return fib(n-1) + fib(n-2) else calculate
• This is based on definition. It takes a long
time [for big numbers]
fib(n) runs in exponential time
• Let T denote the running time.
T(0) = T(1) = c
T(n) = T(n-1) + T(n-2) + 2
where 2 accounts for line 2 plus the
addition at line 3.
• It can be shown that the running time is
Ω((3/2)n).
– at most and at least exponential
Efficient Fibonacci numbers
• Avoid recomputation
– Work iteratively: working up and saving past results
• Solution with linear running time
int fib(int n)
{
int fibn=0, fibn1=0, fibn2=1;
}
set up 3 numbers
if (n < 2)
check case
return n
low(er) cases return n
else
{
for( int i = 2; i <= n; i++ ) { loop
fibn = fibn1 + fibn2; calculate fibn
fibn1 = fibn2;
reset fibn1
fibn2 = fibn;
reset fibn2
}
ends the looping
return fibn;
}
ends the else clause
ends the function
Origami: paper folding
• Associated most with Japan
• Many oldest models come from China
• Independent development in Spain,
elsewhere
• Worldwide
• Conventions all over: NYC in June
• http://www.origami-usa.org/
Water bomb
• Traditional model
• Can ask questions:
– what is surface area?
– what areas are on outside?
– from folding pattern, what is foldable
assignment of mountain and valley? What is
folding order?
Modular origami
• 6 preliminary folds unit
• systems of models
• Rona Gurkewitz, others
Complexity and origami
• Many complexity questions have been
addressed for origami, including: can a
model be folded? Can a folding pattern be
folded? Can a folding pattern with
mountain and valley assignments be
folded flat?
• http://www.msri.org/publications/ln/msri/20
03/introdcgeom/demaine/2/index.html
Fold and cut
• Examples by Betsy Ross, Houdini, Martin
Gardner (Scientific American), others.
• 5 pointed star
General problem
• Take a square
• Draw a polygon
• Is there a way to fold a flat model and
make one cut to produce the polygon?
• Answer: Yes.
– two ways. One way: generate skeleton, add
perpendicular folds, then determine how to
fold this pattern.
– NP-complete
Conclusion
• Very big topic
• Active research
• Questions and comments?