Introduction

• David plays a game called Oscartime that was the first Scratch program he created
• Scratch is a graphical programming language created by MIT’s Lifelong Kindergarten Group
• The language not only helps get kids excited about programming, but it’s also very instructive

Software

• Programing is ultimately about making software
  • Software is what runs on our hardware
    • Could run on a desktop, or phone, etc.

Finding Mike Smith

• Code is just a technical implementation of algorithms
  • Algorithms are step by step instructions for solving problems
• Consider a phonebook full of thousands of names and phone numbers
• How do we lookup someone like Mike Smith?
  • We could start at the first page, move to the next, and so on until we find him
    • This is a correct algorithm, as we will find Mike Smith eventually
    • However, it’s inefficient
  • We could start at the first page and count by 2s
    • I would find Mike Smith twice as quickly
    • However, this alone is not correct as we could miss Mike Smith if his name is sandwiched between two pages
    • We could fix this by checking the previous page if we go past where Mike Smith should be
• More likely, we’d probably go to the middle of the phonebook and find ourselves in the “M” section
  • As Smith is after M, he must be in the latter (right) half of the book
    • We can ignore the other half
  • After removing the other half, we are left with half of the book, representing the same problem we started with fundamentally
    • We can keep repeating this process until we’re down to one page with Mike’s number on it
  • This leverages the fact that the book is sorted alphabetically
  • We are deviding and conquering
    • 1000 pages → 500 pages → 250 pages → 125 pages…

Phonebook Algorithm

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

Pseudocode

• This example algorithm is code, not written in a programming language, but rather English
• This is called Pseudocode
  • Code-like syntax written in English
  • Numbered lines to maintain order and reference lines
  • pick up, open to, look at, call, open, and go back are functions
  • if, if else, and else are conditions
  • Smith is among names, Smith is earlier in book, and Smith is later in book are Boolean expressions
    • Can be either true or false
    • If these are true, the indented code below is executed
  • Both line 8 and 11 say to go back to step 3
    • This creates a loop
      • Doing the sane thing again and again

Programming Constructs

• These constructs of loops, Boolean expressions, functions, and conditions as well as others such as variables, threads, events, and more are common across all programming languages

C

• C is one of the oldest programming languages that someone might still write in