Class 4 - Notes

White Belt Advancement

If you have not yet passed the white belt exam, here's what you should do:

  1. For each question you did not answer well on the original exam write up a good, correct solution to that question, as well as a brief explanation of why your previous answer was wrong (when possible this shouldn't just be about why it was incorrect, but what was confused in your understanding that led to the incorrect answer or inability to answer the question).

  2. Answer the following additional question:

    Describe the set of strings produced by the BNF grammar below starting from S (you can use clear English to write your description, or mathematical set notation).
    S ::= S S
    S ::= T
    T ::= 0
    T ::= 1

  3. Attach your writeup (including your answer to question 6 above) to the graded exam, and turn it in at Monday's class (or drop it off at my office before then).

You are allowed to discuss the questions and answers with anyone you want (including other students in the class), but must write your solutions and explanations yourself and completely understand everything in them.

Doing this well will be sufficient to earn the White Belt. Students who do not complete the White Belt exam this way, will have a final opportunity to do it via an oral exam during office hours or scheduled at another time.

It is necessary to complete the White Belt before advancing to the Yellow Belt.

Yellow Belt Requirements

To earn the Yellow Belt, you are expected to:

Project 1 is due on Friday, 5 February (that's one week from today!). Students who turn in exemplary Project 1 assignments will earn their Yellow Belt based on those; others will have an opportunity to earn the Yellow Belt by taking an exam the following week (more details on that upcoming). Completing a satisfactory Project 1 is a precondition for being able to take the Yellow Belt exam (that is, you can't take the exam to advance to the Yellow Belt until after you have submitted a satisfactory Project 1).


[Download (PPTX)]


If you are still using a username like mst3k in slack, please visit, click the "Expand" button on the right side of the "Username" field, and enter a more pronouncable username for yourself. It doesn't need to be your real name, but something more pleasant than your UVA ID.

Please post questions here — I will assume everyone understands everything in the readings and cs101 lessons unless there are questions about them. Its okay if you don't know how to formulate a good question - its enough to just say something like, "I'm confused about procedural abstraction", or to reply to someone else posting this with "me too!", so we know topics that it would be worthwhile to cover in class. (If you can state a clear question, of course, that's better, and someone may be able to answer it usefully.)

Notes and Questions

Given that a general-purpose computer can run any program (given enough time and memory), why does your smartphone have more than one of them?

Challenge Question. How does the computing power in each one of the 120 cores of your smartphone's graphics processing unit compare to the computing power NASA used in 1969 to go to the moon? (We didn't answer this in class, but a good answer, worthy of presenting to the class, would be worth an automatic belt promotion.)

What is an efficient way to hand back papers to a class?