Week 0, continued

CS50 Staff 2014 share favorite memories of CS50, advice for students, and their signature dance moves.

Register for Puzzle Day 2014 with friends from Facebook who will challenge you with problems they have written.

Ansel Duff, former student and advisee, is now an engineering student who built the binary bulbs this summer with Dan Bradley, as well as the lecturn used on stage.

On campus, more advanced researchers are using biological materials to solve physiological problems for humans.

The field of computer science has many directions and areas to go into. The guide has descriptions and a diagram of classes after 50.

Today we focus on the fundamental view of having algorithms that find the outputs for a problem given some inputs. The phonebook example was solved in three ways, with one (dividing the problem in half each time) being fundamentally faster. If the phonebook had 4 billion pages, it would only take 32 divisions to find the page containing a particular person like Mike Smith.

Pseudocode is expressed using English or any language to convey the idea of an algorithm, with the goal of anticipating all possible cases.

 1pick up phone book
 2open to middle of phone book
 3look at names
 4if "Smith" is among names
 5    call Mike
 6else if "Smith" is earlier in book
 7    open to middle of left half of book
 8    go to line 3
 9else if "Smith" is later in book
10    open to middle of right half of book
11    go to line 3
12else
13    give up

Software crashing usually means that a programmer didn’t anticipate a case or mistake, so the program acts unpredictably, crashing or rebooting your computer.

More general problem of taking attendance can be formalized as shown in TED’s animated clip "What’s an algorithm?".

A variable is like a container (a glass bowl) implemented as bits on a hard drive or memory, that stores a particular value.

1let N = 0
2for each person in room
3  set N = N + 1

A loop is doing the same thing over and over again, commonly expressed in a format like "for each person in the room, do this" with the proposition for.

A condition, or branch, will handle certain cases. In the animated example, when counting pairs of people in a room, the case of having an odd number of people is handled by such a condition, as shown below.

1if 1 person remains then
2  set N = N + 1

Rob and two volunteers, Anita and Kiersten, will demonstrate making a peanut butter and jelly sandwich. David will note pseudocode instructions from the audience.

Computers need very specific instructions to complete tasks, and here audience volunteers will give instructions.

This demonstration (and Rob in particular) reveals how humans take for granted that others will understand what they mean, but computers need explicit, literal instructions.

Ultimately, we will program in source code that is not in English but a language like C or Java or C++.

The following code looks scary, but will be understandable by next week.

#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}

The syntactic stuff, braces and semicolons, is not as important as the "simple ideas." In this case, we want to focus on the line that begins with printf and simply has the effect of saying hello, world.

To work with just the important ideas for now, we will start with a programming language called Scratch from MIT for Problem Set 0. The Scratch software can be used in the browser, or downloaded for use offline. The software allows us to write programs that use graphical puzzle pieces to instruct programs using the same concepts of variables, loops, and conditions. Its mascot, a cat, is also named Scratch.

The Control category contains blocks with familiar words like if, else, and repeat.

The Looks category has a block named [say [] ] that has a box for us to type text into.

We can call each instruction a statement. Programs are generally many algorithms that humans wrote, in essence zeroes and ones, that represent statements that together solve a problem.

A boolean expression is either true or false.

A condition such as the [ if <> ] block will have hexagonal openings that fit boolean expression blocks, which are in the shape of a hexagon.

Loops include the forever and repeat blocks.

Variables are represented by blocks such as [ set [N] to [0] ] where N and 0 can be arbitrarily defined.

Demonstrations of Pastry Catch with Abby and Ivy`s Hardest Game with Phillip.

Let’s build a sample Scratch program using all of these concepts.

In pet the cat, we combine a loop and a condition so that the cat will meow only if the mouse pointer is touching it or, in other words, if we are petting it. In don’t pet the cat, we add an extra condition (using the else keyword) so that the cat will meow indefinitely, but will roar if we touch it with the mouse pointer.

hi hi hi contains a seal barking, but will stop when the space bar is pressed. One block controls the barking of the seal and one waits for space to be pressed, but both loops run simultaneously.

counting sheep contains a sheep that says "baa" with some probability.

The seal and sheep are called sprites, each with a different costume. Each sprite can have its own set of blocks controlling its actions, and move or act simultaneously, which is what we call threading.

Another program written by Dan Bradley has a Scratch extension, or custom puzzle piece, that controls the lightbulb on the lectern. It sends a message across the internet to do this.

Sections and office hours will begin next week.

Zamyla Chan’s walkthroughs will help you begin problem sets.

Finally, we play What Does the Fox Say as a final example of Scratch.