Lecture 4/24: Fractals

April 24, 2020

📂Associated files

Questions and Answers

Fractals

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

$An impressive fractal, demonstrating how a very few basic parts to an image can be beautiful$

Slide 2

Announcements

Assignment 2 is due end-of-day Saturday; the grace period for submission extends through end-of-day Monday.
Assignment 3 will be released over the weekend and we will be returning to a normal cadence of Friday deadlines for assignments.
We are currently working to address student concerns regarding LaIR – keep an eye out over the weekend for updates.

Slide 3

Observations about recursion

The base case represents the simplest possible instance of the problem you are solving.
- Example: How many people are behind you, including you? Answer? 1, it's just me!
- Example: What is x^n? Answer: x^0 = 1
- Solve the Towers of Hanoi Answer: 1 ring is easy!
The recursive case represents how you can break down the problem into smaller instances of the same problem.
- Example: How many people are behind you, including you? Answer? 1 + the number behind me
- Example: What is x^n? Answer: x * x^(n-1)
- Solve the Towers of Hanoi Answer: N-1 disks to aux, 1 disk to target, N-1 disks to target

Slide 4

Another recursion example

$An image showing how Google will perform math for you. Inside the search bar is '((1+3)*(2*(4+1)))$

An image showing how the Google calculator solution to '((1+3)*(2*(4+1))), which is 95

Google can do arithmetic:
- ((1*17)+(2*(3+(4*9)))) = 95

Slide 5

The Challenge

Implement a function which evaluates an expression string:
- "((1+3)*(2*(4+1)))"
- "(7+6)"
- "(((4*(1+2))+6)*7)"
- (only needs to implement + and *)

Slide 6

Anatomy of a mathematical expression

An expression is always one of these three things:
- a number
- (an expression + an expression)
- (an expression * an expression)
For example:
- ((1*3)+(4*2))
  - There is an expression on the left, (1*3)
    - This expression is made up of a number * a number (and a number is also an expression)
  - There is a joining operator, +
  - There is an expression on the right, 2*4
    - This expression is made up of a number * a number (and a number is also an expression)
- The two smaller expressions with the + joining operator make up an expression, as well.

Slide 7

Anatomy of a mathematical expression

How do we evaluate ((1*17)+(2*(3+(4*9))))?

An image showing a 'tree' representing the solution to the above evaluation. First, we break each expression up into its component parts, and when we get to an expression with just numbers, we calculate those results. We have the '+' separating the two main expressions, (1*17) and (2*(3+(4*9))). Etc. This text is repeated below.

First, we break each expression up into its component parts, and when we get to an expression with just numbers, we calculate those results. We have the + separating the two main expressions, (1*17) and (2*(3+(4*9)))
Next, we start looking at the sub-expressions. The (1*17) has two numbers, so can evalute the product, to get 17. The(2*(3+(4*9))) has a number, 2 and another expression, 3+(4*9). So, we have to evaluate the non-number first.
- We look at (3+(4*9)) and see that it has a number, 3 and an expression, 4*9, so we have to look at the expression first.
  - 4*9 has just numbers, so we can calculate the product, to get 36. Now we can back up, because we have a number for the previous expression.
- We can calculate (3+36) to get 39, and we can move up.
We can calculate (2*39) to get 78, and we can move up.
Finally, we can calculate 17+78 to get 95.

Slide 8

Is it recursive? Yes!

Take a look at ((1*3)+(4+2))
- The big instance of this problem is the whole problem, and the smaller instances are the numbers, 1, 3, 4, and 2.
So, we can write a recursive function:
- int evaluate(string exp); // "((1*3)+(4+2)) returns 9
- We can use the library functions:
  - stringIsInteger(exp)
  - stringToInteger(exp)
- And we can use a couple of helper functions:
  - char op = getOperator(exp); // returns '+' or '*'
  - string left = getLeftExp(exp); // returns "(1*3)"
  - string right = getRightExp(exp); // returns "(4+2)"

Slide 9

Solution in Pseudocode

"((1*3)+(2*4))"

int evaluate(expression):

if expression is a number, return expression
Otherwise, break up expression by its operator:
- leftResult = evaluate(leftExpression)
- rightResult = evaluate(rightExpression)
- return leftResult operator rightResult

Slide 10

The solution

int evaluate(string exp) {
    // base case
    if (stringIsInteger(exp)) {
        return stringToInteger(exp);
    } else {
        char op = getOperator(exp);
        string left = getLeftExp(exp);
        string right = getRightExp(exp);

        // recursive case #1
        int leftResult = evaluate(left);

        // recursive case #2 (!)
        int rightResult = evaluate(right);

        if (op == '+') {
            return leftResult + rightResult;
        } else {
            return leftResult * rightResult;
        }
    }
}

Slide 11

Helper function

int getOppIndex(string exp){
    int parens = 0; 
    // ignore first left paren
    for (int i = 1; i < exp.length(); i++) {
        char c = exp[i];
        if (c == '(') {
            parens++;
        } else if (c == ')') {
            parens--;
        }
        if (parens == 0 && (c == '+' || c == '*')) {
            return i;
        }
    }
    return -1;
}

Slide 12

Fractals

A fractal is a recurring graphical pattern. Smaller instances of the same shape or pattern occur within the pattern itself.

$An image showing many fractals. The patterns are incredible -- they repeate again and again in each image, getting (in general) smaller each time. One image is of a programatically-generated tree with the main trunk branching off to smaller copies of itself, each with its own smaller copies, as well. Another example is the Sierpinski triangle, with three triangles encompassed inside a larger triangle. Each smaller triangle is itself made of three smaller triangles, and this keeps going to infinity.$

Slide 13

Fractal Examples in Nature

$Images of a broccoli-like plant, a fern, a snow-covered mountain, and a coastline -- all examples of natural fractals$

Many natural phenomena generate fractal patterns:
- earthquake fault lines
- animal color patterns
- clouds
- mountain ranges
- snowflakes
- crystals
- coastlines
- DNA

Slide 14

The Cantor Fractal

We can create many fractals programmatically, and because fractals are self-similar, we can do so recursively!
The first fractal we will code is called the "Cantor" fractal, named after the late-19th century German mathematician Georg Cantor.

$An image of an Egyptian architectural column, with a Cantor fractor built into the column$

$An image of a tattoo of the Cantor fractal on someone's arm$

The Cantor fractal is a set of lines (indeed, a "Cantor Set" of lines) where there is one main line, and below that there are two other lines, each 1/3rd of the width of the original line, one on theleft, and one on the right (with a 1/3 separation of white space between them)
Below each of the other lines is an identical situation: two 1/3rd lines.
This repeats until the lines are no longer visible.

Slide 15

The Cantor Fractal

$An image of the cantor fractal using just line segments$

In text, a 4-level Cantor fractal would look like this:

---------------------------
---------         ---------
---   ---         ---   ---
- -   - -         - -   - -

Parts of a cantor set image … are Cantor set images!

Slide 16

The Cantor Fractal

$An image of a six-level cantor fractal using just line segments, showing that the left third of the diagram under the original line is a Cantor set, and so is the right third of the diagram under the original line$

The Cantor fractal above has six levels.
Every individual line segment is its own 1-level Cantor fractal

Slide 17

How to draw a level 1 Cantor fractal

A single line, going across the whole screen

Slide 18

How to draw a level `n` Cantor fractal

A single line, going across the whole screen. Underneath, on the left, is a space where it says 'draw a cantor of size n-1', and on the right, it says 'draw a cantor of size n-1'

Draw a line from start to finish.
Underneath, on the left third, draw a Cantor of size n - 1.
Underneath, on the right third, draw a Cantor of size n - 1.

Slide 19

Graphics in C++ with the Stanford library: `GPoint`

An image showing an x/y axis with the origin in the top left. There is a single point labeled 'GPoint a', and some code that says, GWindow w; GPoint a(100, 100); cout << a.getX() << endl;

An image showing an x/y axis with the origin in the top left. There are now two points labeled 'GPoint a' and 'GPoint b', and some code that says, GWindow w; GPoint a(100, 100); GPoint b(20, 20); w.drawLione(a, b);

Slide 20

Let's code!

$The Cantor fractal and the Qt Logo$

Slide 21

Snowflake Fractal

$A 'snowflake' fractal which is made up of lines and triangles. It has the apperance of a snowflake with six 'sides' of the snowflake, with each side made up of an infinite number of smaller line/triangle segments. See below on how we are going to draw it$

Slide 22

Let's break this down to a smaller part

$A part of the 'snowflake' fractal that has been sliced such that only a horizontal section remains$

Slide 23

Depth 1 Snowflake: A line

To start drawing a snowflake, you draw a line all the way across the screen

Slide 24

Depth 2 Snowflake: The line has a triangle break

To draw a depth 2 snowflake, you split the line from level 1 at the 1/3 and 2/3 marks, and draw a triangle between those two points that is at the middle and above the line.

Slide 25

Depth 3 Snowflake: In progress

A level 3 snowflake starts by taking the original 1/3 of the level 1 snowflake and splitting that into thirds, with the 1/3 and 2/3 points of that smaller line creating a vertical triangle as with a level 2 snowflake

Slide 26

Depth 3 Snowflake: In progress

To continue a level 3 snowflake, you break the left part of the level 2 triangle into thirds, and the points at 1/3 and 2/3 of that smaller line are drawn out and to the right (at an angle such that the point in the middle creates an equilateral triangle with the slanted edge.

Slide 27

Depth 3 Snowflake: Finished

A finished level three snowflake has another two side triangles drawn as in the previous two drawings. There are a total of four new triangle 'bumps' on the level 2 snowflake.

Slide 28

Let's Code a Snowflake!

A partial snowflake and the Qt logo

Lecture 4/24: Fractals

Fractals

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

Announcements

Observations about recursion

Another recursion example

The Challenge

Anatomy of a mathematical expression

Anatomy of a mathematical expression

Is it recursive? Yes!

Solution in Pseudocode

The solution

Helper function

Fractals

Fractal Examples in Nature

The Cantor Fractal

The Cantor Fractal

The Cantor Fractal

How to draw a level 1 Cantor fractal

How to draw a level n Cantor fractal

Graphics in C++ with the Stanford library: GPoint

Let's code!

Snowflake Fractal

Let's break this down to a smaller part

Depth 1 Snowflake: A line

Depth 2 Snowflake: The line has a triangle break

Depth 3 Snowflake: In progress

Depth 3 Snowflake: In progress

Depth 3 Snowflake: Finished

Let's Code a Snowflake!

How to draw a level `n` Cantor fractal

Graphics in C++ with the Stanford library: `GPoint`