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
Programming is just a way of doing things, an algorithm
Programmers get to exercise some discretion when creating the algorithm
What's a program?
Instruction set to a computer
A programmer, therefore, is just a person that writes those instructions
A software developer, software engineer, etc are essentially synonyms
Example: phone book with 1000 pages in it.
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
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.
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?
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.
The max runtime to find a phone number in a 1024 page phonebook?
What about for a 1 million page phonebook?
Linear: 1 million
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.
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.
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.
Student exercise: verbally craft an algorithm to change a [toy] baby's diaper
'Place the baby on a safe surface'
David: places baby on table
Step 2:'Unsnap clothes'
David: throws baby over and unsnaps
Step 2:'no no, turn over baby'
David throws baby over
Step 2:'without moving the baby feel for the snaps of the clothes'
Step 3:'without moving the baby, undo the snaps'
Step 4: 'without harming the baby, gently remove the clothes to expose the diaper'
'Gently put the baby back down on the surface'
'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'
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)
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
How can we begin to approach programming a bit more procedurally?
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
12. close sock drawer
14. remove first sock from foot
16. else (note 5)
17. do laundry and replenish sock drawer
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'
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.
Markup - HTML
Code that a program interprets
Example of C:
main(int argc, char * argv)
Example of C++:
main(int argc, char * argv)
cout << "Hello world!";
Example of Java:
public static void main(String  argv)
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)
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
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)
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
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
Remember the 'Hello world' sample source code from above? Here is how we would do it in scratch:
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:
Congrats! Your first program.
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.
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.
Here is another sample program:
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.
This will cause the cat to meow, wait a second, and meow again.
What are some other things that exist in Scratch?
'true' or 'false'
So for example, 'is 5 greater than 4?' is a boolean expression. You can answer in 'true' or 'false'
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):
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.
Scratch also supports random numbers. See example below ('Hello 5' Scratch example)
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.
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?
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?
Now the cat will always meow, unless you touch him with the mouse. In this case, he will roar.
Another ('Count' Scratch example):
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):
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):
What does the cat do?
The cat moves 1 step at all times until it is touching the bird (and then it stops).
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.
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.
This is an example of a threaded program
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.
This next example shows us a sample of state ('Hello10'):
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.
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!