A general outgrowth (application) of combinatorics
(the science of counting)
Basic reading: Pfaltz 1978: Harvard Papers on GIS
deeper reading on algorithmic analysis: Don Knuth The Art of
Computer Programming, volume 1: Fundamental Algorithms,
second ed. 1973; volume 3: Sorting and Searching 1973.
Fundamental distinction between computational complexity
studies which investigate complexity of problems, whatever algorithm
might be used, and algorithmic analysis which studies the
behavior of individual algorithms under a range of assumptions
about the input data.
Notation- Big O: O(n), O(
n log n ), O( n-squared) ...[polynomial time]; O(e to the
n power) [exponential time]. These mean asymptotic complexity,
often worst case...
Algorithmic analysis must consider the whole life-span of the
data. It is common to talk about one kind of operation (say searching)
without considering the cost of inserting the data and maintaining
the structure.
Computational complexity studies may be limited, but they provide
specific results that cannot be ignored. For example, sorting
is, at best, O( n log n ). Many problems contain sorting or perform
something more complex than a sort, so they must be at least O(
n log n )...
Wise's Chapter 5 is short, but introduces the basic issues.
Sorting: O (n log n)
Lecture will concentrate on showing complexity of simple sorting
algorithms.
General searching: once an index is created (a lot like a sort....),
each search at best O(log n)
Lecture will begin with demonstrating complexity for retreival...
Spatial searching: Lots of alternatives, see some later lectures
problem often called Thiessen polygons by geographers
There are a few problems which are significantly difficult. Some are beyond all hope, but a very interesting class is called NP Complete. These problems include some interesting geographic problems like the graph coloring problem and the travelling salesman problem, along with the satisfiability problem and the knapsack problem (see below). If one of these problems has a given polynomial order of complexity, then all can be shown to be in the same class. The conjecture is that they are not polynomial, but no rigorous proof has been found. If a problem seems tough, it may be NP Complete, and you should find a way to simplify the problem to make it less restrictive.
Also discussed in the 460 course.
(Common character of NP Complete, you cannot make a first choice,
without knowing all choices...)
A fairly complete list
of all NP problems
given a graph, find minimum cost (distance) path which visits
each node once and only once.
Solutions
given a set of integers and an integer sized "knapsack",
determine which integers may be packed into the knapsack so that
it is exactly filled.
a discussion
of heuristic for knapsack problem
participatory experiment from 460