Lecture 4/6: Welcome!

April 6, 2020

📂Associated files

Lecture 1: Welcome!

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

The Stanford Campus

Slide 2

Lecture 1: It is a Brave New World

Instead of worrying about what you cannot control, shift your energy to what you can create.
― Roy T. Bennett, The Light in the Heart

Slide 3

Today's Topics

What day is it? asked Pooh.
It’s today, squeaked Piglet.
My favorite day, said Pooh.
― A.A. Milne

Slide 4

Instruction Team: Lecturers and Head CA

Tell me and I forget, teach me and I may remember, involve me and I learn.
– Benjamin Franklin

Lecturers

Chris Gregg     Julie Zelenski
Chris Gregg   Julie Zelenski

Head CA

Chris Gregg
Nick Bowman

Slide 5

Instruction Team: Section Leaders

When you learn, teach, when you get, give.
― Maya Angelou

crowd of people

Slide 6

What is CS 106B?

Computer Science is no more about computers than astronomy is about telescopes.
― Edsger Dijkstra

CS106B: Learn core ideas in how to model and solve complex problems with computers

Complex Problem #1: Self Driving Cars

Self driving Delorean from Stanford Source

Video of self-driving Delorean

Slide 7

What is CS 106B?

The most important property of a program is whether it accomplishes the intention of its user.
― C.A.R. Hoare

CS106B: Learn core ideas in how to model and solve complex problems with computers

Complex Problem #2: Compressing Data

Video size calculator showing that 1 second of 1280x720 pixels would take 663Mbps of bandwidth Source

Slide 8

What is CS 106B?

Speech recognition and the understanding of language is core to the future of search and information, but there are lots of hard problems such as understanding how a reference works, understanding what ‘he’, ‘she’ or ‘it’ refers to in a sentence. … That’s just one of the millions of problems to solve in language.
― Ben Gomes, Head of Search at Google

CS106B: Learn core ideas in how to model and solve complex problems with computers

Complex Problem #3: Speech Recognition

iPhone screen showing 'What can I help with?' text

Slide 9

CS 106B Goals

A goal without a plan is just a wish.
– Antoine de Saint-Exupéry

I think goals should never be easy, they should force you to work, even if they are uncomfortable at the time.
–Michael Phelps

One of CS 106B's goals: Learn core ideas in how to model and solve complex problems with computers

Slide 10

Explore Common Abstractions

Abstraction is one of the greatest visionary tools ever invented by human beings to imagine, decipher, and depict the world.
― Jerry Saltz

The first programming assignment I had in high school was to find the first 100 Fibonacci numbers. Instead, I thought it would be cooler to write a program to get the teacher's password and all the other students' passwords. And the teacher gave me an A and told the class how smart I was.
―Kevin Mitnick

How are user passwords kept secure when logging into a website (or, why shouldn't a website ever be able to send you your password?)

Zoom login screen

Slide 11

Explore Common Abstractions

The radio doesn't want to play you until you're No.1 on Shazam, and you can't get No.1 on Shazam without getting played.
―Tones and I

How does Shazam figure out what song is playing by listening through your microphone?

Shazam iPhone app screenshot

Slide 12

Explore Common Abstractions

I'm so fast that last night I turned off the light switch in my hotel room and was in bed before the room was dark.
―Muhammad Ali

Diagram showing key value pairs Source

Slide 13

Explore Common Abstractions

The best book on programming for the layman is 'Alice in Wonderland'; but that's because it's the best book on anything for the layman.
―Alan Perlis

What is a digital signature, and how can it be used to prove that I was the person that sent an email, or signed a document?

Image showing how a digital signature works using Alice and Bob from Alice in Wonderland Source

Slide 14

Common Abstractions

The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer.
–Edsger Dijkstra

  • How are user passwords kept secure when logging into a website (or, why shouldn't a website ever be able to send you your password?)
  • How does Shazam figure out what song is playing by listening through your microphone?
  • How can it be possible to search for a value in a data structure without having to look at any of the other values (or at least only a few other values)? I.e., how can we program super fast search?
  • What is a digital signature, and how can it be used to prove that I was the person that sent an email, or signed a document?

Slide 15

CS 106B Goals

CS106B: Learn core ideas in how to model and solve complex problems with computers

In order to understand recursion you must first understand recursion.
― Unknown

Slide 16

Harness the power of recursion

When students first encounter recursion, they often react with suspicion to the entire idea, as if they have just been exposed to some conjurer's trick rather than a critically important programming methodology.
― Eric S. Roberts

A recursively generated tree

Slide 17

Harness the power of recursion

Learning to think in this new way requires students to examine recursion from several different perspectives.
–Eric Roberts

Recursion recursion recursion...

Slide 18

CS 106B Goals

CS106B: Learn core ideas in how to model and solve complex problems with computers

I took a computer-science course to fill a prerequisite at Stanford, and I realized that every day was a new problem, and every day you got to think about how to solve something new, how to reason through something new, how to develop an algorithm to solve for something you hadn't worked on before.
―Marissa Mayer

Slide 19

CS 106B: Learn Efficient Algorithms

Efficiency is intelligent laziness.
– David Dunham

9-tile puzzle game with tiles that must be matched together to create the entire puzzle

Slide 20

CS 106B: Learn Efficient Algorithms

I will be ruthless in cutting out waste, streamlining structures and improving efficiency.
– Theresa May

9-tile puzzle game with tiles that must be matched together to create the entire puzzle that is solved

Slide 21

CS 106B: Course Information

The Google algorithm was a significant development. I've had thank-you emails from people whose lives have been saved by information on a medical website or who have found the love of their life on a dating website. Tim Berners-Lee
– Tim Berners-Lee (inventor of the World Wide Web)

Slide 22

CS 106B: Course Components

Many jobs at Google require math, computing, and coding skills, so if your good grades truly reflect skills in those areas that you can apply, it would be an advantage. But Google has its eyes on much more.
– Thomas Friedman

Assessments: Assignments (55%), Mid-quarter assessment (15%), Final Assessment (20%), Section Participation (10%)

Slide 23

CS 106B: Assignments in CS 106B

When I've least expected it, an enormous opportunity or stroke of luck has crossed right under my nose. So I tell everybody, if you're passionate about what you do and you love it, do it. But do your homework. Because you'll never know when the opportunity is going to happen.
– Julie Andrews

Slide 24

CS 106B: Grading Style

Style is the substance of the subject called unceasingly to the surface.
– Victor Hugo

Grade   Description
+   Exceeds requirements.
✓+   Satisfies all requirements of the assignment.
✓   Meets most requirements, but with some problems.
✓-   Has more serious problems.
-   Better than nothing.

Slide 25

CS 106B: Sections

Poetry comes alive to me through recitation.
– Natalie Merchant

A group of section leaders

Slide 26

You need to ask questions if you are confused

The best scientists and explorers have the attributes of kids! They ask question and have a sense of wonder. They have curiosity. 'Who, what, where, why, when, and how!' They never stop asking questions, and I never stop asking questions, just like a five year old.
– Sylvia Earle

Slide 27

Getting Help

I am going to change the world, and I'm talking to everybody in the possible world that I can get to that can help me to do that.
– Abby Wambach

  1. Ed Discussion
  2. Sign in to the LaIR / Instructor Office Hours
  3. Contact your Section Leader
  4. Email Chris, Julie, or Nick

Slide 28

One Last Detail…

Writing in C or C++ is like running a chain saw with all the safety guards removed.
– Bob Gray

Within C++, there is a much smaller and cleaner language struggling to get out.
– Bjarne Stroustrup (the creator of C++)

C++: an octopus made by nailing extra legs onto a dog.
– Steve Taylor

C++

Slide 29

C++

Writing in C or C++ is like running a chain saw with all the safety guards removed.
– Bob Gray

The TIOBE Programming Community Index, ranking programming languages by use

Slide 30

CS 106/107 languages

If someone claims to have the perfect programming language, he is either a fool or a salesman or both.
– Bjarne Stroustrup

The TIOBE Programming Community Index, ranking programming languages by use

Class    Language    Year Created
CS 106A   Python   1990
CS 106AX   Javascript   1995
CS 106B/X   C++   1983
CS 107   C   1972!

Slide 31

Your First C++ Program!

And programming computers was so fascinating. You create your own little universe, and then it does what you tell it to do.
– Vint Cerf (the "father of the internet")

The Qt Creator logo. Qt Creator is the Integrated Development Environment that is used in CS 106B

Slide 32

Your First C++ Program!

There are two ways to write error-free programs; only the third one works.
– Alan Perlis

Slide 33

Your First C++ Program!

When someone says: "I want a programming language in which I need only say what I wish done", give him a lollipop.
– Alan Perlis

// Our first C++ program!

// headers:
#include <iostream>
#include "console.h" // Stanford library

using namespace std;

// main
int main()
{
    cout << "Hello, World!" << endl;
    return 0;
}

Output:

Hello, World!

Slide 34

Your Second C++ Program!

If people built houses the way we write programs, the first woodpecker would wipe out civilization.
– Dennis Hall

A table describing a vector with indexes in the top row, starting from 0 and ending at 9. The bottom row has the following numbers: 42 18 12 9 0 -5 13 -8 12 23. Underneath the table, there is the C++ expression A[6] == 13

Slide 35

Your Second C++ Program!

Software and cathedrals are much the same – first we build them, then we pray.
– Sam Redwine

// Populate a Vector

// headers:
#include <iostream>
#include "console.h" // Stanford library
#include "vector.h" // Stanford library

using namespace std;

const int NUM_ELEMENTS = 100000;

// main
int main()
{
    Vector<int> myList;
    cout << "Populating a Vector with even integers less than "
         << (NUM_ELEMENTS * 2) << endl;

    for (int i=0; i < NUM_ELEMENTS; i++){
        myList.add(i*2);
    }

    for (int i : myList) {
        cout << i << endl;
    }
    return 0;
}

Slide 36

The Importance of Data Structures

Beware of bugs in the above code; I have only proved it correct, not tried it.
– Donald Knuth

Slide 37

The Importance of Data Structures

Computer Science is embarrassed by the computer.
– Alan Perlis

Structure         Overall(s)
Unsorted Vector:  1.45973
Linked List:      8.17542
Binary Tree:      0.02734
Hash Table:       0.01316
Sorted Vector:    0.22202

Slide 38

The Importance of Data Structures

On two occasions I have been asked, – "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" In one case a member of the Upper, and in the other a member of the Lower House put this question. I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
– Charles Babbage

Structure         Overall(s)    Insert(s)     Search(s)     Delete(s)
Unsorted Vector:  1.45973       0.00045       0.92233       0.53694
Linked List:      8.17542       0.00688       5.92075       2.24779
Binary Tree:      0.02734       0.02415       0.00199       0.00120
Hash Table:       0.01316       0.01116       0.00088       0.00112
Sorted Vector:    0.22202       0.14747       0.00206       0.07248

Slide 39

HW 0

If you lie to the computer, it will get you.
– Perry Farrar

Thursday night there will be a special LaIR to help install tools if necessary.

Due: Friday, April 10th, at Noon AoE