Computational Modeling
Fall 2008

For today, you should:

1) really finish Chapter 7

2) read Chapter 8

Today:

1) quiz 6 solutions

2) chapter 8 suggestions

3) work on Chapter 8

For next time you should:

1) work on Chapter 8

Quiz 6 Solutions
----------------

1) FFT divides the size of the vector in half at each level of
recursion, so the number of levels of recursion is O(log n).

The total amount of work done at each level is O(n), so the whole
algorithm is O(n log n), which is better than O(n^2) for the naive
implementation of DFT.

The version of FFT I described in the book makes copies of the
subvectors at each level of recursion, so the total space requirement
is O(n log n).

With butterfly indexing you can eliminate the copying and reduce
the space requirement to O(n).


2) Holism is the view that there are limits to what reductionist
models can do.  Different flavors of holism posit different limits.

To generate statements of holism in various strengths, you can choose
different points on several axes:

   a) Model choice: is a holistic approach right and a reductionist
      approach wrong, or is one better than the other, or are
      both good, or do you need both?

   b) Which systems: are holistic models better (or necessary)
      for some systems, most, or all?

   c) Are holistic models necessary for explanation or prediction
      or both?

      In the context of explanation, people sometimes say things
      like "complex systems can only be understood with holistic
      models."

      In the context of prediction, people (ahem, Wolfram) sometimes
      talk about computational irreducibility:
      en.wikipedia.org/wiki/Computational_irreducibility

   d) Ontological status of emergent entities: a holist is more
      likely to consider emergent entities real (or at least entitled
      to the same status as entities at lower levels).

   e) Observer effects: a holist is more likely to worry about
      whether and how the observer interacts with the system.

These are the forms of holism associated with complexity science.
More generally (and dubiously) holism is associated with the view that
systems are formally inscrutable because in order to make them an
object of study you have to take them out of context, or adopt a
particular methodological stance, or shift focus from the system to
the parts, or somehow interfere with whatever was making the thing
work when you weren't watching.  Of course, hypotheses of this type
can run afoul of unfalsifiability.

3) Suggestion: take advantage of Python's built-in functions,
like max, sort, zip and enumerate, and use patterns like DSU.

def formants(h, d):
    N = len(h)
    P = psd(h)           # P is a list of powers for n = 0..N/2

    # make a sorted list of (power, freq) pairs
    t = [(p, float(n)/d/N) for n, p in enumerate(P)]
    t.sort(reverse=True)

    return t[0][1], t[1][1]

If your solution involves more than 10 lines of code, please
read en.wikipedia.org/wiki/Flagellation


Chapter 8
---------

Some of you have reported discomfort with the feeling that we
are leaving so much unexplored.  Chapter 8 will make this feeling
much, much worse.

8.1: Implement Schelling's model and extend it in one of several
     ways.  One particularly interesting variation is a utility
     function that favors mixed neighborhoods.

8.2: The "Big Sort" variation on Schelling's model.

8.3: (Can someone help me get Highway.py working on Windows?)

     Explore traffic models.

     See also: http://www.slatev.com/player.html?id=1681718043

8.4: Build a better boid.

8.5: Ants

8.6: Sugarscape

8.7: Read (and write) about Emergence, probably starting with
     en.wikipedia.org/wiki/Emergence