* Lecture 11: Programming
* Wednesday, 6 December 2006
* As the class ends, it becomes a bit more of a segue into other Extension school classes
* While you won't leave this lecture a programmer, you'll have a better understanding about what programmers do and how they do it
wedge Programming is just a way of doing things, an algorithm
* Programmers get to exercise some discretion when creating the algorithm
wedge What's a program?
* Instruction set to a computer
wedge A programmer, therefore, is just a person that writes those instructions
* A software developer, software engineer, etc are essentially synonyms
wedge Example: phone book with 1000 pages in it.
wedge If I wanted to look up the phone number of a company, how would I do that?
* Lets look for 'Leo's Diner'
* First, go through the Restaurant section
* Flip through the pages alphabetically until you get to the first letter of the name
* Continue searching each successive letter alphabetically until you find the target
wedge How would you quantify how efficient this algorithm is? How would you be able to tell how 'long' the program might need to run?
* Lets take worst-case scenario: finding 'Zoe's' restaurant in the phone book, we would have to go through 1,000 pages before finding it.
* Since we're going page by page, it is a linear algorithm - every additional page we must search through increases the time required by some unit time.
wedge As a programmer, we might consider - how can we make this better?
* We could just give it a faster processor, but how could we make the algorithm more efficient?
wedge Start at the middle. When looking for Zoe's:
* Open to the 'L' section (about halfway through). We know that our answer is in the second half of the phone book. So, lets forget about the first half! In the remaining half, divide it in half once more (so now the half of the original phonebook becomes a 1/4 of the original phonebook) and again decide in which new half the phone number is.
* Just by doing 2 steps in this method, we have divided the number of phone entries to search to 1/4 of the original size!
* This is a logarithmic algorithm. In the long term, this is considerably faster than any linear search.
wedge The max runtime to find a phone number in a 1024 page phonebook?
* Linear: 1024
* Logarithmic: 10!
wedge What about for a 1 million page phonebook?
* Linear: 1 million
* Logarithmic: 20!
wedge Algorithm example: counting students
* 1. all students stand up
* 2. assign yourself the number 1
* 3. find someone else that is standing up
* 4. add your number to that person's number; the total is your new number.
* 5. one of you should sit down
* 6 if you're still standing, go back to step 3.
wedge What's happening in this algorithm?
* Everyone stood up, and with each repeat, half of the people sat down.
* So for the 18 students we have here today, dividing the standing students in half 4 times should leave us with one student standing with the total student count number.
wedge Its one thing to talk about things in terms of algorithms, its another thing to start writing programs, implementing algorithms yourself.
* Precision becomes very important.
* Computers will only do what you tell it to do. Its not going to figure out what you meant, or infer what you meant. If it is lacking instructions, it will just not do what you expect it to.
wedge Student exercise: verbally craft an algorithm to change a [toy] baby's diaper
wedge 'Place the baby on a safe surface'
* David: places baby on table
wedge Step 2:'Unsnap clothes'
* David: throws baby over and unsnaps
wedge Step 2:'no no, turn over baby'
* David throws baby over
* Step 2:'without moving the baby feel for the snaps of the clothes'
wedge Step 3:'without moving the baby, undo the snaps'
* David: done
* Step 4: 'without harming the baby, gently remove the clothes to expose the diaper'
* 'Gently put the baby back down on the surface'
wedge 'Without lifting the baby, remove the diaper - carefully - incase its loaded'
* David: removes diaper with interior shell exposed, 'something tells me this was not wise' (but nobody picks up on it and they move on)
* 'Throw diaper away in trash'
* 'Obtain new diaper'
* 'Slide diaper under baby with the straps behind the baby'
* 'Pull the button tab on both sides around the tap and fasten to the front part of the diaper'
* 'Gently dress the baby'
wedge This demo is meant to show that we, as humans, make certain assumptions when providing each other instructions.
* a computer is simply a dumb machine, so when you create an algorithm you must consider every aspect of it, what if the user messes up? Can your algorithm cope with non-perfect situations, (say, if a user enters in the wrong value)
wedge One of the most difficult aspects of programming for human interactivity is dealing with and considering every single possible case, to make sure your program completes successfully but also so that your program is secure
* security is important, because a sloppily created program could be hacked in some cases, allowing a hacker to run code that you do not want to be run
wedge How can we begin to approach programming a bit more procedurally?
wedge Lets introduce pseudocode
* typically when creating a program, people sketch out a framework or an outline of how they think the algorithm should work before actually writing it in the programming language
* Pseudocode example: 'Putting on socks'
* 1. let socks_on_feet = 0 (See note 1)
2. while socks_on_feet != 2 (note 2)
3.    open sock drawer (note 3)
4.    look for sock
5.    if you find a sock then
6.        put on sock
7.        socks_on_feet++ (note 4)
8.        look for matching sock
9.        if you find a matching sock then
10.         put on matching sock
11.         socks_on_feet++
12.         close sock drawer
13.       else
14.         remove first sock from foot
15.         socks_on_feet--
16.   else (note 5)
17.       do laundry and replenish sock drawer

wedge Notes
* 1) Just like algebra has variables (x, y, z), we use variables in programming. Although, many times programming variables are meant to be a bit more descriptive than x,y,z (although this can be used). socks_on_feet is a variable here
* 2) '!=' is programming speak for 'not equals'
* 3) notice the indentation, this is meant to show that this line will only be run given the non-indented line above. so lines 3-17 below only run when line 2 is true
* 4) what does '++' mean? you are incrementing your variable - you are adding 1 to your variable
* 5) note that this else applies to the 'if' statement from line 5. the statement 'you find a sock' is a condition, and if it is not true, the 'else' is run. Just as we would expect, 'if something is true, then [follow these instructions] else [follow these instead'
wedge What happens if we only have one sock in her drawer?
* Given the code above, she will continue searching for a second sock for infinite amount of time. This is known as an infinite loop.
* Even though this is somewhat silly, it is an excellent representation of what can happen in a true computer program.
wedge Languages
wedge Markup - HTML
* Code that a program interprets
wedge Compiled
* Example of C:
* int
main(int argc, char * argv[])
{
     printf("Hello world!");
     exit(0);
}

* Example of C++:
* #include <iostream>

int
main(int argc, char * argv[])
{
     cout << "Hello world!";
     exit(0);
}

* Example of Java:
* class Hello

{
     public static void main(String [] argv)
     {
          System.out.println("Hello world!");
     }
}

* The above is an example of source code. A programmer only understands this, a computer does not understand this. A computer only understands binary. So, in order to run this program, you must 'compile' the source code. This converts it to a pattern of 0s and 1s that a computer does understand.
* It then follows that there are different compilers for PCs and Macs. You can't always use the same source code in a PC and a Mac compiler (there are enough differences between the two such that the source code is different as well)
wedge Java is a language that can be compiled into 'bytecode'. This bytecode is then run by a 'Virtual Machine' on any computerm (there exist Virtual Machines for Macs, PCs, linux, even cell phones). In this way, the same program can be run universally on any machine.
* However, the extra overhead required for the conversion from bytecode to the machine's native language is taxing, so Java programs tend to be slower
wedge Popular languages: C, C++, PHP, Java, Perl, C# (pronounced 'C sharp'), Python
* You choose which language based on many factors, including what you are familiar with, what resources are available to you, what you are aiming your program for (Mac vs PC vs Web)
wedge Javascript is a language that web browsers execute.
* You can do things in webpages such as error checking of fields, etc.
* Usually we teach this in class, but its difficult to teach to a class of non-programmers
wedge Instead, we'll demo Scratch.
* Designed by MIT's Media Lab
* A programming language that makes it really easy and really fast to implement animations, games, art, other fun projects.
* Its relatively easy to learn and pick up.
* Demo: Scratch soccer game demo
* Demo 2: 'Oscartime' - the point is to drag falling trash onto Oscar the Grouch's (from Sesame Street) trashcan
wedge Remember the 'Hello world' sample source code from above? Here is how we would do it in scratch:
*
Picture 1
Picture 1

* Note that there is a 'Green flag' icon on the scratch program. Clicking this button begins your program.
* Running the above script in Scratch reveals this:
wedge
Picture 2
Picture 2

* Congrats! Your first program.
wedge To begin with Scratch, open the program.
* To open a pre-made program, click the 'Open' button at the top and find the project you'd like to try.
* In the upper left hand corner of the program there are categories of things that you can do with Scratch, such as Motion, Looks, Sound, Control, Sensing, Numbers, etc.
* To create a program, you drag puzzle pieces (as shown above) from various categories into the 'Script' column.
* A 'sprite' is a 'character' for your program. It is represented by an image that you can create and import. The default sprite is a cat that you can manipulate.
* The 'Stage' is on the top right. This is where the sprites do something.
wedge By clicking on a Sprite, you can manipulate that sprite's scripts.
* So, with this method, you can have different sprites perform different scripts, ultimately having them do different things.
* Example, you might have a bird sprite and a cat sprite. The bird's script can follow the cat.
wedge Here is another sample program:
*
Picture 4
Picture 4

wedge What does this do?
* Well, when you start the program, the cat says says 'I survived E-1' for 1 second, waits a second, then says 'Okay, I didn't' for 2 secs.
* Try to replicate on your own Scratch.
wedge Another:
*
Picture 5
Picture 5

* This will cause the cat to meow, wait a second, and meow again.
wedge What are some other things that exist in Scratch?
wedge Constructs
wedge Boolean expression
* 'true' or 'false'
* So for example, 'is 5 greater than 4?' is a boolean expression. You can answer in 'true' or 'false'
wedge You can manipulate booleans by having an AND - for example, 'is 5 greater than 4 AND less than 6?'
* in order to solve this, you first figure out if the first part is true, then if the second part is true. If both are true, then the whole statement is true. If either are false, then the whole expression is false.
* Lets take a look at one ('Hello 4' example from Lecture 11 scratch examples):
*
Picture 6
Picture 6

wedge What happens?
* Since 1 is always less than 2, the meow will always sound. However, if we were to swap it (such that we ask 'if 2 is less than 1') - we would never hear the meow.
wedge Scratch also supports random numbers. See example below ('Hello 5' Scratch example)
*
Picture 7
Picture 7

* So, if it picks a random that is less than 6, it will meow. If it picks the number 6 or larger (since 6<6 is false) then it will not meow. So essentially half the time we would expect this program to meow.
wedge You can also run loops. There are cases when always running a loop (for example, in Oscartime, so that the program picked a new piece of trash to fall)
* So, what does this do?
*
Picture 8
Picture 8

* So, after you start the program, the loop runs forever. However, it will only meow if the mouse is touching the cat. So we have already built some interactivity - the cat meows if you pet him.
* How about this?
*
Picture 9
Picture 9

* Now the cat will always meow, unless you touch him with the mouse. In this case, he will roar.
* Another ('Count' Scratch example):
*
Picture 10
Picture 10

wedge We initialize a variable named 'counter'. Every one second it counts up one and tells us the new count.
* Not terribly interesting here, but you can use a counter to keep score in your game
* One more ('Move1' Scratch example):
*
Picture 11
Picture 11

* This will cause the Cat sprite to move. It constantly loops such that it moves the cat 1 step. When it hits an edge, it plays a sound and 'bounces' off the edge.
* Yet another ('Move2' Scratch example):
wedge Cat script:
Picture 12
Picture 12

wedge What does the cat do?
* The cat moves 1 step at all times until it is touching the bird (and then it stops).
wedge Bird script:
Picture 13
Picture 13

wedge What does the bird do?
* When the program starts, it begins at a certain place on the stage. It moves 3 steps and bounces off of the edge and bounces off edges until it is touching the cat.
wedge Which sprite is moving more quickly, the cat or the bird?
* The bird, it moves 3 steps at every iteration of the loop when the cat only moves 1.
wedge This is an example of a threaded program
wedge a 'threaded' program is a program that can do more than one thing at once. In this example, we are running two scripts at once, so it is double-threaded.
* In the case of Microsoft Word, if you click 'print', it still allows you to type in the background. This implies that there is a second thread to manage the printing while the original thread allows you to type.
wedge This next example shows us a sample of state ('Hello10'):
*
Picture 14
Picture 14

* State means that the program is aware of its environment. This program will forever play the sound until the 'muted' variable is equal to 0. The space bar toggles the 'muted' variable between 1 and 0.
* These are two scripts associated with the cat. The script on top always meows. The next script simply spends its entire life listening to the spacebar to be pressed. This changes the muted value and can affect the first script.
* Explore the sample Scratch programs provided in the Lecture 11 Scratch 'Examples' set.
wedge Marco Scratch example shows how scripts among different sprites can communicate with each other.
* This is known as 'event handling'
* The boy waits forever until the spacebar is pressed. It then says 'Marco' and it broadcasts an event. The event is 'whispered' if you will to all the other scripts. The girl sprite is listening for an event, and upon its receipt says 'Polo'.
* Feel free to explore and have fun with Scratch!
* Just take it easy, take baby steps.
* Don't sit down and write an entire program, write part of it and debug it and refine it until it does what it should, then move on.
* Don't forget Exam 2 next week!