Week 0, continued

For this lecture, CS50 comes to Yale!

Although most lectures will happen in Cambridge, all students are always able to watch lectures online - which may be a more effective way to absorb the information.

We’ve distilled computer science down to "computational thinking", which we can break down into the process inputs → algorithms → outputs.

On Wednesday, we looked at the problem of looking someone up in the phonebook, and found that an intuitive "divide and conquer" algorithm is much more efficient than going through the pages of the phonebook one by one.

 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

Where else can we apply a divide-and-conquer algorithm? Taking attendance, for example.

With this algorithm, we found that the number of people in the lecture hall was 392 (…​even though there are 497 seats, all of which are full).

TF Sam and volunteers Erica and Antonio will try to make a peanut butter and jelly sandwich, following pseudocode instructions from the audience.

 1open the bag of bread
 2open the inner bag of bread as well
 3gently remove two slices of bread
 4place bread on plate
 5lightly place hand on top of peanut butter, unscrew and put lid next to peanut butter (or "just open the peanut butter jar!")
 6take knife and insert into peanut butter jar
 7remove seal from peanut butter jar
 8gray computer (Sam) follow other computers (Erica and Antonio)
 9use knife to gently spread peanut butter on bread
10repeat steps 5–9 with the jelly

Only partly successful—computers do EXACTLY what you tell them to, so you need to be very precise!

Prof. Scassellati (Scaz) and course heads Jason and Andi come up to say hello.

The team at Yale will be supplementing CS50 with an exploration of "intelligent software", like the algorithms Hulu and Netflix use for recommendations, grounding this in the principles of the course.

David took a video tour of Yale campus.

So far we’ve looked at pseudocode, but now we’ll transition to actual code, or "source code".

We briefly showed this example on Wednesday, which is written in a language called C and (underwhelmingly) simply prints the words "hello, world" to the screen:

#include <stdio.h>

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

Much of the semester will be spent working with C, and toward the end of the semester we’ll build upon it with other languages like PHP, JavaScript, and even a database language called SQL.

To begin with, we’ll work in a programming language called Scratch from MIT’s Media Lab (which you’ll use for Problem Set 0). Scratch is a graphical language, in which you can drag around puzzle pieces containing pieces of code that only interlock if they go together programmatically. It contains all the same programming concepts, like loops and conditionals, as any other language, but lets us put off the uninteresting details of syntax for now.

Volunteer Angela plays David’s grad school Scratch project Oscartime and an updated version by CS50’s own Jordan Hayashi.

Another game, Pikachu’s Pastry Catch (written by a student in a previous year of CS50!), is played by volunteer Lance.

We’ve also recreated the Binary Bulbs interface in Scratch.

Let’s take a look at the pieces that go into the actual implementations of these programs.

The Scratch interface lets us apply scripts to sprites (characters, objects, etc) by dragging and dropping puzzle pieces.

The Control category of blocks contains familiar structures like if, else, and repeat.

The Looks category has a block named that has a box for us to type text into, so we can make our sprite say "Hello, Yale" or whatever else we want.

Some of our control structures, like "if" and "else", require boolean expressions, which evaluate to either true or false. These blocks have hexagonal spaces into which you can drop boolean expression pieces.

Loops include the and blocks.

Variables are represented by blocks such as (where N can be replaced with any variable name and 0 can be replaced with any value for that variable).

Arrays let us store more than one piece of information, using blocks like .

We can also write functions in scratch, using a define block, in which we’ll group together a bunch of commands we often use together into a new reusable block with a name that we assign, like this simple example:

Scratch also supports fancier features like threads, events, etc, which students more comfortable may want to look into.

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

Scratch lets you record your own sounds and draw or upload your own images to use as sprites, in addition to a whole bunch of provided sounds and images.

One of the fundamental takeaways of the class is good design—more than just the correctness of your program, it’s important to write elegant, readable, maintainable code.