Computational Modeling
Fall 2005

For today: HomeworkFifteen (cdf)


Today's outline:

1) Zipf's Law, Pareto distribution, power law... (from notes11)

2) Fourier transform

For next time: HomeworkSixteen  (Gould)


Exam 1 Solutions
----------------

Part Three
----------

I defined

m = number of vertices
n = number of edges

which was confusing.  I tried to infer what you meant and
not beat you up for getting it backwards.  Sorry!


def check_colors(g):
    for v, w in g.edges():
	if v.color == w.color: return False
    return True

Remember that an edge _is_ a tuple, so we can use it in a
tuple assignment.

This takes time proportional to n, the number of edges,
if we assume that Graph.edges is also O(n).

def check_colors(g):
    for v in g.vertices():
        for w in g.outVertices(w):
	    if v.color == w.color: return False
    return True

This looks like it might be O(mn) because the outer loop
iterates over vertices and the inner loop iterates over
edges, but remember that the body of the loop only runs
once for each edge, so the run time is O(n), except in
a sparse graph where m < n; in that case, run time is O(m),
so overall, run time is O(m + n).

In big-O notation addition has the sense of OR.


Part Four
---------

Many of you chose to implement simultaneous updates.  Masochists.

    def step(self):
        d = {0:self.step_empty, 1:self.step_tree, 2:self.step_burning}
        d[self.state]()

    def step_empty(self):
        if random.random() < self.world.p:
            self.mark_tree()
            
    def step_tree(self):
        if random.random() < self.world.f:
            self.mark_burning()
        elif self.any_neighbor_burning():
            self.mark_burning()            

    def step_burning(self):
        self.mark_empty()

    # the next two methods should probably be in Forest...

    def any_neighbor_burning(self):
        x, y = self.indices
        return (self.patch_burning(x+1, y) or
                self.patch_burning(x-1, y) or
                self.patch_burning(x, y+1) or
                self.patch_burning(x, y-1))
    
    def patch_burning(self, x, y):
        try:
            return self.world.cells[x,y].state == 1
        except KeyError:
            return False



The FFT in 5 easy steps:

0) what is a signal?

1) what is the correlation of two signals?

2) continuous Fourier transform

3) discrete Fourier transform

4) fast (discrete) Fourier transform


Signal
------

A signal is a flow of information.

According to our friends at the Wikipedia, most signals
"can be modeled" as a function of time or position.

     (doesn't that make you feel like they're hiding something?)

The domain is bounded (signals have a beginning and an end,
like a line segment).

Easiest example is a sound wave, which is pressure as a function
of time.


Correlation

If you want to know how similar two signals are to each other,
you can multiply them together and integrate.

If you assume that the signals are zero-centered, there is an
intuitive explanations for this:

1) where both signals are positive, the integral accumulates

2) where both signals are positive, the integral accumulates

3) where they have different sign, the integral give some back 

If they are not zero-centered, that adds a constant, which doesn't
matter for comparisons.


Fourier Transform

If you want to know how much of a given frequency is in a signal,
you can compute the correlation with a sine wave.

But the result depends on the phase.

Alternatively, you can correlate the signal with exp(2 pi i f t)

The result is a complex number, which can be interpreted as

1) the magnitude of the correlation

2) the phase shift that maximizes the correlation

The Fourier Transform is a function from freqency f to a
(magnitude, phase) pair.

If you give me the FT of a function, I can compute the function.

In other words, the FT is just an alternative way to specify a
signal.


Discrete Fourier Transform

In the real world, there are no functions, only quantities
we can measure.

How many measurements do you have to make in order to completely
describe a function?

Sampling theorem: if the signal is bandwidth-limited (maximum
frequency component of f), then we only have to take samples
at a rate of 2f to describe the function completely
(assuming infinite sample resolution)

Imagine that we measure air pressure at a sequence of equally-spaced
points in time, at frequency 44,100 samples per second.

What is the highest frequency we could recover from our measurement?

What would happen if the signal contained a higher frequency
component?