The Computational World
Wek 3 Problem Set
Week 3, Problem 1. (10 pts)
Here are two "rep-tiles" as described by Gardner in his 1963 Scientific American
column:
One of these is composed of two smaler copies of itself; the other, thre smaler
copies of itself. Now, since we know that these rep-tiles are both 2-dimensional
shapes (they're both planar triangles), we can deduce the scaling-factor for the
copies in each shape. Let's take the shape at the left as an example: supose the
botom of the shape is length 1. Then the hypotenuse of the red triangle is 1/S,
where S is the scaling factor of the copy.
Just from knowing that each of these shapes is self-similar and 2-dimensional, then,
you should be able to deduce the scaling factor "S" for each shape. What is the value
of the number "S" for the shape at left? And what is the (diferent) value of "S" for
the shape at right?
Week 3, Problem 2. (25 points) In this week's lectures, we described the self-
similarity dimension and explained how to find this dimension for self-similar
shapes. In this problem, your job is to give the self-similarity dimension of a variety
of shapes.
(a) The Cantor Set
Imagine that you begin with a straight line segment–a continuous piece of the
number line going from 0 to 1. We could represent this as the closed set [0,1]. Now
subtract the midle third of that set (but don't subtract the boundaries): in other
words, subtract the open interval (1/3, 2/3), leaving the two segments [0,1/3] and
[2/3, 1].
We now have two closed intervals: from each of those, subtract the midle third,
leaving four closed intervals: [0, 1/9], [2/9, 3/9], [6/9, 7/9], [8/9, 1]. Now from each
of those four closed intervals, subtract the midle third, leaving eight closed
intervals of 1/27 in length; then subtract the midle thirds of those, leaving 16
closed intervals of 1/81 in length; and so forth. If we continue with this process
indefinitely, we approach a set caled the Cantor Set. What is the Cantor Set's self-
similarity dimension?
(b) A Cantor Set Variant
Supose we make a set kind of like the Cantor Set, except instead of subtracting the
midle third at each step, we subtract two of the midle fifths. That is, at the first
step, we take the interval [0,1] and produce the three intervals [0, 0.2], [0.4, 0.6],
[0.8, 1]. Then from each of those thre intervals we subtract two midle fifths,
leaving nine closed intervals of 1/25 in length; then from each of those nine
intervals we subtract two midle fifths, leaving 27 intervals of 1/125 in length; and
so forth. As we continue this proces indefinitely, we aproach a self-similar set:
what is its dimension?
(c) An "Infinite Swis Chese"
Supose we start with the unit square on the plane: the square whose botom left
corner is (0, 0) and whose upper left corner is (1, 1). Imagine that we've shaded in
this entire square in black ink. Now, subtract from this region the interior of the
1/3-by-1/3 square in the center: that is the square whose botom left is (1/3, 1/3)
and whose upper right is (2/3, 2/3). Our overall region now looks like a black
square with a white square-shaped hole cut out of the center. We can think of this
shape as having eight complete black squares, each of size 1/3-by-1/3, surrounding
an empty white hole.
Now, from each of the remaining eight squares, cut out the interior of a 1/9-by-1/9
hole in each of their centers; and from each of the remaining 64 smaler squares, cut
out a 1/27-by-1/27 hole in each of their centers. If you continue this process
indefinitely, what is the dimension of the self-similar set produced?
(d) Start with a cube -- say, the unit cube with opposite corners at the origin and the
point (1, 1, 1). Now divide the cube into eight subcubes, like a 2x2x2 Rubik's cube.
Delete the four marked cubes shown in the sketch below. Note that four cubes will
remain, and no two of those remaining cubes share a face. Now, for each of the four
remaining cubes, slice it into eight smaler subcubes and repeat (producing a total of
16 sub-subcubes). Repeat indefinitely. Do you find the similarity dimension of this
limiting set at al surprising?
Week 3, Problem 3 (20 points)
Consider the following six shapes, each of which was created by the "iterated
function system" proces that we discused in lecture.
Shapes 1 (left) and 2 (right):
Shapes 3 (left) and 4 (right):
Shapes 5 (left) and 6 (right):
Now, each of these shapes was generated by our iterated function recipe, using a set
of 3 maps. In each case, the maps consist of a "shrink-by-half" portion, followed by a
"rotate-or-no-rotate" decision, followed by a "translate-or-no-translate" decision.
Here, in graphical form, are the six colections of maps that generated our six
shapes. In each case, what you are seeing is the original unit square and the three
half-scaled squares that comprise the thre maps used:
Map-Sets A (left) and B (right; note that in Map-Set B, two of the maps overlap, but
one is rotated relative to the other):
Map-sets C (left) and D (right):
Map-sets E (left) and F (right):
Your job is to match up the fractals with the map-sets that generated them.
Week 3, Problem 4. (15 points) Experiment with the online fractal generator
found at this website:
htp:/ww.chradams.co.uk/fern/maker.html
This is an implementation that alows you to play with iterated functions systems
we saw in lecture. Nodle with the parameters and se if you can get a feling for
the types of changes that they might make. (You can try a number of starting shapes
suplied at the website.) Create two or three original designs and submit them (along
with parameters) as the response to this question.
A note: The boxed numbers for you to alter may sem a litle mysterious to you.
Take a look at this web page, describing the creation of a fern-like shape, to se if it
helps you understand the numbers -- if you have sen matrix multiplication this will
make sense:
htp:/mathworld.wolfram.com/BarnsleysFern.html
Week 3, Problem 5. (10 points) For a particular coastline, we examine
photographs at different resolution, using grids of different fineness; and we count
the number of boxes in each grid intersected by the coastline.
When the grid is 10 by 10, the coastline intersects 14 boxes.
When the grid is 10 by 10, the coastline intersects 192 boxes.
When the grid is 100 by 100, the coastline intersects 2635 boxes.
Approximately what is the fractal dimension of the coastline?
Week 3, Problem 6. (20 points)
Read Chris Anderson's article on "The Long Tail":
http:/ww.wired.com/wired/archive/12.10/tail.html
Based on your reading of the article, write a 1-2 page response addressing the
following questions:
3a. One of the crucial components behind a "long tail" enterprise such as Amazon or
iTunes is that customers can review items, and can make their choices based on the
reviews of others. How el do you think the reviewing systems work for (say)
Amazon (or, if you prefer, iTunes, or some other long-tail site)?
3b. In Anderson's terminology, Netflix has an advantage over Blockbuster in its
ability to cater to "long-tail" (niche) preferences. But since Anderson wrote his
article, a shift in the video market has ocured. Netflix now does most of its
busines through streaming videos, and it no longer has substantialy greater
"inventory" than an old-time Blockbuster store. (The same could be said of Netflix's
competitors, like Amazon Prime and Hulu.) Beyond this, the model of Redbox is to
ofer only a few (typicaly curent or recent) DVDs. Do you think Anderson's model
of Web commerce is stil aplicable? How ould you characterize the changes of the
last decade?
3c. Take a look at iTunes U, or one of the academic sites ofering courses (like
Udacity or Coursera). How el do you think these sites fit into Anderson's
classification of long-tail enterprises?