Computational thinking & programmer mindset This is a lesson I had prepared for General Assembly's IWD program day 1.

lesson_on_comp_thinking.md

Mapping problems into computational framework

Making the computer do what you want it to do

Let's take an example of a body wash bottle's instructions

Instructions for using Aveeno active naturals body wash:

• Squeeze onto a wet pouf or washcloth
• Work into a rich creamy lather
• Rinse

What is one problem with the above set of instructions that you can see right away?

The set of instructions above assumes that you understand the meaning of squeezing stuff onto a wet pouf, making a rich creamy lather, and rinsing.

What if you had to build a robot that would wash you?

How would you have it understand the concepts above?

A computer will always do exactly and only what you tell it to do.

Data representation

• ASCII, the alphabet, as a mapping of 0s and 1s to letters

Summary

• At the end of the day, it's all zeroes and ones.
• It would be impractical to operate with those.
• We have been building what are called layers of abstraction on top of zeroes and ones.
• With high level programming languages, liker ruby, we operate with human readable abstractions.
  • In the case of ruby, those human readable abstractions are especially beautiful and pleasant to work with. It's one of the reasons we are starting with ruby!

A phone book

• Let's all break into groups, based on the tables that you are sitting at
• Write a recipe for a computer to search through a phone book for a person, given a "Lastname, Firstname"
• You have the following abstractions at your disposal:
  • Pages may be turned one at a time or more than one at a time
  • The book may be browsed arbitrarily to a given page
  • When you browse to a page you may instantly identify the first letter of all the names on that page
  • The names may be read one at a time from the top of a page to the bottom
  • Names may also be read arbitrarily on a page - you may jump anywhere on the page for a name
  • Pages never have more than one letter of names on it
  • The book is sorted alphabetically, by last name

Some possible results

• Look for a name by going through each page (n)
• Look for a name by going through every two pages (n/2)
• Split the problem in half by going to the middle and the middle again - divide and conquer (log n)
  • Given the abstractions at our disposal we may find the page on which the name is, and the actual name

A computer's basic operations

Turing Machine

The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc.

• Invented by British mathematician Alan Turing in 1936.
• A hypothetical device that manipulates symbols on a strip of tape
• A table of rules.
• Can be adapted to simulate the logic of any computer algorithm

There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:

• read (i.e. identify) the symbol currently under the head
• write a symbol on the square currently under the head (after first deleting the symbol * already written there, if any)
• move the tape left one square
• move the tape right one square
• change state
• halt.

Turing Machine Simulator

What is computation?

Two kinds of knowledge:

• declarative

  • statements of fact
  • example: y is the square root of x, iif y * y = x

• imperative

  • how to solve a problem

  • a recipe

  • an algorithm: a description of how to perform a computation

    • a set of instructions
    • a flow of control (the order in which steps are executed)

  Algorithm Video

Programming languages

All programming languages have the following, to one degree or another:

• syntax: which sequences of characters constitute a well formed string (not necessarily meaningful)

in irb: x = 100 200 fails with:

irb(main):003:0> x = 100 200
SyntaxError: (irb):3: syntax error, unexpected tINTEGER, expecting end-of-input
from /usr/bin/irb:12:in `<main>'

• static semantics: which well-formed strings have a meaning

in irb: x = 100 / "xyz" fails with:

irb(main):004:0> x = 100 / "xyz"
TypeError: String can't be coerced into Fixnum
	from (irb):4:in `/'
	from (irb):4
	from /usr/bin/irb:12:in `<main>'

• semantics: what that meaning is

  • All well-formed programs have a meaning; it's not always what you had intended.
  • The program doesn't give you the correct answer; it doesn't perform as expected.

Problems when the first two are OK

When the meaning is not what you had intended:

• Crash
• Never stop (infinite loop)
• Run to completion and produce the wrong answer