• 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.

    • We won’t focus so much on input/output representations (like binary or even ASCII) from here on out, instead emphasizing algorithms to solve problems.

  • 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
    13    give up
  • Where else can we apply a divide-and-conquer algorithm? Taking attendance, for example.

    • We can count the students in the room one by one, but that’ll be slow.

    • Similarly, we can count by twos, but it doesn’t get us much of a speedup.

    • Instead, we introduce the following algorithm:

      1stand up and assign yourself the number 1
      2pair off with someone standing, add your numbers together, and adopt the sum as your new number
      3one of the pair should sit down; the other goes back to step 2
  • 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).

    • This is an example of a bug in the execution of our algorithm - we’ll come back to this idea later.

    • In theory, this algorithm leverages the same divide-and-conquer logic as the phonebook example: on each step, half of the remaining people sit down.

    • Unlike finding Mike Smith in the phonebook, this requires additional resources: all the people in the audience! This is an example of parallel processing, whereby certain problems can be solved much faster by using more computers (or people, in this case).

PB&J Demonstration12:14

  • 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!

Yale Introduction22:38

  • 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.

Source Code and Scratch27:36

  • 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.

    • Volunteer Mary tries to represent 256 using this interface - but we’re one bit short! 255 is the largest number that fits in 8 bits (or one byte) because we start from 0.

  • 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 WhenGreenClicked_t block is what starts the program.

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

    • By dragging that block below the WhenGreenClicked_t block, the cat will say the text when the green flag is clicked.

  • 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.

    • mousedown_t, boolvars_t, touching_t are all boolean expressions.

    • The and_t block can be used to combine boolean expressions.

    • Conditions can also be nested for three possible branches.

  • Loops include the forever_t and repeat_t blocks.

  • Variables are represented by blocks such as set_t (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 array_t.

  • 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 cough
    • This lets us factor out code rather than copying and pasting - more on this later!

  • 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.

    • In pet the cat, we combine a loop forever_t and a condition touching_t 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.

    • If we omit the wait_t block, so we’re just telling the cat to meow constantly, the sound gets glitchy because it’s not waiting to finish playing the sound before starting it over again. This is a bug you should watch out for in your own code on Problem Set 0!

    • We can also make the cat move, using blocks under Motion like move_t.

    • Counting sheep illustrates the use of a variable called counter_t.

    • hi hi hi keeps track of whether or not the space bar is pressed to mute the barking of a seal, using multiple scripts.

    • It’s also possible to have multiple sprites in a single project, and they can send each other signals, or events, as in this example.

  • 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.

    • For example, if you avoid repeating yourself (instead using loops and functions), changing a minor detail only requires you to make a change in one place rather than several.

    • See how we go from cough-0 to cough-4 by increasingly modularizing and abstracting away details into functions to avoid repeating ourselves.

    • On Problem Set 0, you’ll likely want to go through multiple versions to improve upon the design of your original program.