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?