Class 2 - Notes

White Belt Exam

Because of the snow day, the first opportunity to pass the white belt test will be in class this Wednesday, 27 January. The test will be a short, in-class, on-paper test that includes some short answer questions and a few questions where you have to understand and write short Python code snippets. The questions will cover these materials:

Everything covered in Class 1 and Class 2 (today).
Chapter 1 and Chapter 2 of the coursebook.
Udacity cs101 Lesson 1 and Lesson 1: Problem Set.
The Course Pledge.

If you have done and understand all of these before class Wednesday, you should be able to earn your white belt and be able to start working on your yellow belt. Please take advantage of the upcoming scheduled office hours (Tuesday at 3:30, Rice 507), ask questions in the Slack group, and all the on-line resources. If you don't pass the white belt test Wednesday, there will be later opportunities to pass it in different ways (which could involve an oral exam during office hours).

Slides

[Download (PPTX)]

Notes and Questions

What is Computer Science?

What is a language?

Languages are made of:

Primitives (almost all languages have these) – the simplest surface forms with meaning ( surprisingly it is possible to make a powerful language without any primitives. We will see one before the end of this class!)
Means of Combination (all languages have these) – rules of production (ways to make new surface forms from ones you already have)
Means of Abstraction (all powerful languages have these) – ways to use simple surface forms to represent complicated ones

Backus-Naur Form (BNF): A way of describing the surface forms in a language using replacement rules in the form:

non-terminal ::= replacement

The rule means whenever you have what is on the left side of the ::=, you can replace it with what is on the right side.

What strings can the following BNF grammar produce?

Sentence ::= Food Comparator Food
Food ::= Bodo’s Bagels
Food ::= Einstein’s Bagels
Comparator ::= are better than
Comparator ::= are worse than

What strings can the following BNF grammar produce?

Sentence ::= I like FoodList
FoodList ::= Food
FoodList ::= Food and FoodList
Food ::= Bodo’s Bagels
Food ::= Einstein’s Bagels

When learning a new language, which of primitives, means of combination, or means of abstraction is hardest to learn?

Are there any non-recursive natural languages?

What would happen to a society that spoke one?

See on-line version for fun links and quotes.

Fun Links

Full Python Grammar (This is a file that can be processed automatically by a a program to read Python programs, so it is a bit hard to read. But, it is essentially the same BNF notation we have seen in class and the book.)

The sentence, "Nine and a half turtles wearing orange aprons with watermelons on them began to simultaneously yodel as the conductor stepped on the kitchen table." is from the article Who’s afraid of George Kingsley Zipf? Or: Do children and chimps have language? (Charles Yang, Significance: The Magazine of The Royal Statistical Society, December 2013)

`Yes way!' added to OED! (December 2015) (You can access the OED through UVA libraries to confirm this: yes, adv

Computers are actually pretty simple. We’re sitting here on a bench in this cafe. Let’s assume that you understood only the most rudimentary of directions and you asked how to find the rest room. I would have to describe it to you in very specific and precise instructions. I might say, “Scoot sideways two meters off the bench. Stand erect. Life left foot. Bend left knee until it is horizontal. Extend left foot and shift weight 300 centimeters forward.” and on and on. If you could interpret all those instructions 100 times faster than any other person in this cafe, you would appear to be a magician: You could run over and grab a milk shake and bring it back and set it on the table and snap your fingers, and I’d think you make the milkshake appear, because it was so fast relative to my perception. That’s exactly what a computer does. It takes these very, very simple-minded instructions – “Go fetch a number, add it to this number, put the result there, perceive if it’s greater than this other number” – but executes them at a rate of, let’s say, 1,000,000 per second. At 1,000,000 per second, the results appear to be magic. That’s a simple explanation, and the point is that people really don’t have to understand how computers work.

Steve Jobs, Interviewed in Playboy Magazine (SSFW — no pictures, other than a fully clothed one of Steve, and just a little bit of bad language), February 1, 1985. (Note: 3 months later, in May 1985, Jobs was kicked-out of Apple. If you read the whole interview, especially the part about Edwin Land, keep this in mind.)