# CS101 Final Exam

Stanford CS101 Final, Spring 2015-16

Name (last, first): ___________________, __________________________

I agree to the letter and spirit of the honor code, that no illicit aid has been used or provided:

(signed)______________________________________

This exam is out of 200 points, so each

SA 1. ____ / 30
SA 2. ____ / 30
IM 1. ____ / 10
IM 2. ____ / 10
IM 3. ____ / 15
IM 4. ____ / 20
IM 5. ____ / 15
IM 6. ____ / 20
TA 1. ____ / 10
TA 2. ____ / 15
TA 3. ____ / 10
TA 4. ____ / 15
_____ / 200

• This is a closed note, closed computer, closed phone, closed calculator exam
• Just you and your pen or pencil!
• Time is 90 minutes
• The exam is about twice as long as the midterm
• We will not mark off for superficial syntax errors, so long as we can discern the right idea
• For answers involving math, you can write an expression, such as "100 * 6 / 20"
• For all image problems, you may omit the final `print(image);` line
• When using the avg detection technique, you may omit the `* 1.2` factor
• Good luck!

Code reference "cheat sheet" to be printed with exam:

```// Basic image for-loop example
image = new SimpleImage("something.jpg");
for (pixel: image) {
pixel.setRed(0);
}
print(image);

// If-Statement example:
if (100 > 50) {
// body lines
}

Functions:
-pixel.setRed(val)  // likewise for green and blue
-pixel.getRed()     // likewise for green and blue
-pixel.getX(), pixel.getY()
-image.getWidth(), image.getHeight()
-image.getPixel(x, y)
-image.setAsBig(other_image)

Table loop:
table = new SimpleTable("baby-2010.csv");
table.convertToLowerCase();
for (row: table) {
print(row);
}

Table functions:
-table.convertToLowerCase()
-row.getField(field_name)
-s1.startsWith(s2), s1.endsWith(s2)

Table field names:
baby: name, rank, gender, year
survey: color, tv, gender, movie, book, sport, soda

=sum(B1:B10)    // sum up column of numbers
=A1 + A2 * 10   // arithmetic based on other cells
```

```table = new SimpleTable("baby-2010.csv");
// Location 1
for (row: table) {
// Location 2
if (row.getField("name").endsWith("x")) {
print(row);
// Location 3
}
}
// Location 4
```

a. There are 2000 names (rows) total, and 12 names end with "x". Suppose the above code runs 4 times, each time with the following line at one of the Location N spots:
`print("nom");`

How many "nom" print for each location?

```Location 1:
Location 2:
Location 3:
Location 4:
```

b. What exactly goes in the cell B6 to add up the Magic numbers?

c. Suppose the "Super Magic" value should be the B6 value multiplied by 1000. What exactly goes in the B8 cell to compute this?

d. About how many bytes are required to encode the text of this message: WooHoo

e. 10 bits can store 1024 different patterns. How many patterns can 11 bits store?

f. In order to create a revised version of a computer program, you need access to its (2 words):

g. Suppose we have a series of samples representing a sound, and a program goes through and halves each of the sample numbers. What effect does this have on the sound?

h. Suppose we have 9 samples, and use a compression scheme that throws away sample #2 #4 #6 and #8. The resulting compressed form of the signal is: 2 8 12 10 4. The decompression scheme restores each missing sample as the average of the sample before and after the missing one. what is the decompressed form of this signal, and is this compression scheme lossy or lossless?

i. Suppose we have 20,000 images, and each image is 4 MB. How many GB do they take up in total?

j. A 64 GB storage card costs about \$16 in 2016 (just looked it up on Amazon). According to the 2-year version of Moore's law, about what should a 64 GB card cost in 2020?

a. Suppose a network has 600 mbps of bandwidth. Assuming 50% of the bandwidth is available and the other 50% goes to overhead, how many MB per second can be sent on the network?

b. True current event: NASA's New Horizons space probe flew past Pluto in 2015, taking many high-resolution pictures. A Fox news correspondent recently complained that NASA is incompetently taking too long to release these images. The probe is incredibly far from Earth. Its weak radio signal at that distance can only transmit 2,000 bits per second. At that transmission rate, how many seconds does it take for the probe to send a single 100 MB image to Earth?

c. One source of password weakness we discussed was "the password is a word". List 3 other distinct sources of password weakness:

e. Suppose Alice, Bob, and Carl each have public and private keys in a public-key cryptography scheme (here each key is just 4 characters):

```Name     pub     priv
Alice    ax23    zk92
Bob      f5tz    m4rs
Carl     yu3x    ay92
```

Carl wants to send encrypted bytes to Alice so that only Alice can decrypt them. What key does Carl encrypt with and what key does Alice decrypt with?

f. We've talked about bad guys crafting an "exploit" to attack software. What is the word for the weakness that such exploits target?

g. What does the word "organic" mean in the context of web-search results?

h. In lecture we talked about "war" as one possible metaphor for web economics. What was the other important metaphor for web economics?

i. Below is a line of HTML code. Draw what this HTML looks like when rendered by a browser.
<p>Here we have <a href="http://video.org/LOL.mp4">LOL</a>

Image 1 (10 points)

Write code to change the image as follows: for each pixel change the blue value to be half the green value. Also double the red value.

```image = new SimpleImage("donut.jpg");
for (pixel: image) {
```

Image 2 (10 points)

Suppose the donut.jpg image is 400 pixels wide by 200 pixels high. Write code to make a pure-black, vertical stripe going down the far right 25% of the image. It's fine to use literal numbers in your code to identify the stripe (as we did in lecture), or any other technique which gets the correct result.

```image = new SimpleImage("donut.jpg");
for (pixel: image) {
```

Image 3 (15 points)

The banana.jpg image shows a yellow banana in front of a green background. Write bluescreen code to replace the green background with pixels from the paris.jpg image. Use a red-low avg strategy to detect the green background.

```image = new SimpleImage("banana.jpg");
back = new SimpleImage("paris.jpg");
back.setAsBig(image);

for (pixel: image) {
```

Image 4 (20 points)

The grapes.jpg image shows a bunch of green grapes in front of a blue background. Write code code to detect the green grapes. We'll say that any pixel with green over 200 is a grape pixel. For each grape pixel, change the corresponding pixel in the back image, converting it from color to grayscale.

```image = new SimpleImage("grapes.jpg");
back = new SimpleImage("paris.jpg");
back.setAsBig(image);

for (pixel: image) {
```

Image 5 (15 points)

The purple-flower.jpg image shows a purple flower in front of a blue background. Write code to detect the purple flower using the avg technique. Change the flower pixel values to be a blend: 90% of the original flower values and 10% of the corresponding back pixel values.

```image = new SimpleImage("purple-flower.jpg");
back = new SimpleImage("pebbles.jpg");
back.setAsBig(image);

for (pixel: image) {

```

Image 6 (20 points)

The carrot.jpg image shows a carrot in front of a blue background. Here we'll assume that any pixel from the carrot image with red greater than 100 is the carrot. Write code to detect the carrot pixels. For each carrot pixel, do something different for each color:

-red: copy the red value from the carrot pixel to the corresponding back pixel
-green: reverse of above, copy the green value from back to image
-blue: change the blue value of both the carrot and back pixels to be the carrot pixel's original green value

```image = new SimpleImage("carrot.jpg");
back = new SimpleImage("pebbles.jpg");
back.setAsBig(image);

for (pixel: image) {

```

Table 1 (10 points)

Write code to print the 10 most popular girl names.

```table = new SimpleTable("baby.csv");

for (row: table) {
```

Table 2 (15 points)

We'll say that a name is "lucky" if it does not end with "y" or "z" and it is not "Nick". Write code to print all the lucky boy names.

```table = new SimpleTable("baby.csv");

for (row: table) {
```

Table 3 (10 points)

Write code to count the number of baby names that start with "B" and end with "y". Print the total count in the form "count: 42".

```table = new SimpleTable("baby.csv");

for (row: table) {

```

Table 4 (15 points)

This question uses the survey fields "tv" and "color". Looking only at people who identified "blue" as their favorite color, count how many picked "game of thrones" vs. "modern family" as their favorite TV show. Print the game of thrones count, then the modern family count, like this:

```game of thrones: 17
modern family: 18

```
```table = new SimpleTable("survey.csv");
table.convertToLowerCase();

for (row: table) {
```

## Solutions

```SA1
a. 1, 2000, 12, 1
b. =sum(b2:b5)
c. =b6 * 1000
d. 6
e. 2048 or could write 2^11
f. Source code
g. Quieter or reduces amplitude
h. 2 5 8 10 12 11 10 7 4, lossy
i. 80 GB
j. \$4

SA2
a. 37.5  MB/s
b. 400,000 seconds
c. Too short; all lowercase; common password; word ending in a digit; a pun…
d. Phishing, dictionary attack, keylogger, hack the site, social engineering…
e. Carl: ax23; Alice: zk92
f. vulnerability
g. Not ads; a result of genuine interest to the user
h. Bees and flowers; symbiosis
i. Here we have LOL   (LOL may be underlined or blue or what have you)

IM 1
pixel.setBlue(pixel.getGreen() * 0.5);
pixel.setRed(pixel.getRed() * 2);

IM 2
if (pixel.getX() > 300) {
pixel.setRed(0);
pixel.setBlue(0);
pixel.setGreen(0);
}

Notes:
-2:  Set colors to wrong value such as 255, etc.
-3:  Used getY instead of getX
-3:  Incorrect value used in the if statement or incorrect sign

IM 3
avg = (pixel.getRed() + pixel.getGreen() + pixel.getBlue())/3;
if (pixel.getRed() < avg) {
pixel2 = back.getPixel(pixel.getX(), pixel.getY());
pixel.setRed(pixel2.getRed());
pixel.setGreen(pixel2.getGreen());
pixel.setBlue(pixel2.getBlue());
}

Notes:
-4:  Flipping pixel and pixel2 inside the if block
-1:  Dividing the average by some other number other than 3
-3:  Using some other value to compare red values in the if statement other than avg
-4:  Detecting high green instead of low red
+2: Correct avg calculated
+4: Correct low red detection
+2: Get correct X and Y values from pixel
+4: Get back pixel from X and Y values correctly

IM 4
For (pixel: image) {
if (pixel.getGreen() > 200) {
pixel2 = back.getPixel(pixel.getX(), pixel.getY());
avg = (pixel2.getRed() + pixel2.getGreen() + pixel2.getBlue()) / 3;

pixel2.setRed(avg);
pixel2.setGreen(avg);
pixel2.setBlue(avg);
}
}

Notes:
Not getting grayscale value by averaging
Getting grayscale value of wrong pixel
Not setting correct pixel’s color values
Not using average to set pixel to grayscale

IM 5
avg = (pixel.getRed() + pixel.getGreen() + pixel.getBlue()) / 3;
if (pixel.getRed() > avg) {
pixel2 = back.getPixel(pixel.getX(), pixel.getY());

pixel.setRed(0.9*pixel.getRed() + 0.1*pixel2.getRed());
pixel.setGreen(0.9*pixel.getGreen() + 0.1*pixel2.getGreen());
pixel.setBlue(0.9*pixel.getBlue() + 0.1*pixel2.getBlue());
}

Notes:
Need to check pixel’s red value to determine if it’s purple
Changing color values of wrong pixel
Incorrect blend arithmetic

IM 6
if (pixel.getRed() > 100) {
pixel2 = back.getPixel(pixel.getX(), pixel.getY());

pixel2.setRed(pixel.getRed());  // setRed

pixel.setBlue(pixel.getGreen());  // setBlue 2x
pixel2.steBlue(pixel.getGreen());

pixel.setGreen(pixel2.getGreen());  // setGreen
}
-Subtle that setBlue should be done before setGreen - we don't
mark off if they miss that.

TA 1
Solution:
if (row.getField("gender") == "female" && row.getField("rank") < 11) {
print(row.getField("name"));
}

Notes:
-0:  Printing row instead of name only
-1:  Using <10 instead of <=10 or <11
-1:  Missing print statement
-3:  Using >11 instead of <=10 or <11
+5: For correctly detecting gender "female"
+5: For correctly detecting rank

TA 2
Solution:
if (row.getFields("gender") == "male" && !row.getField("name").endsWith("y") &&
!row.getField("name").endsWith("z") && row.getField("name") != "Nick") {
print(row.getField("name"));
}

Notes:
-3:  Substituted || instead of && (between endsWith("y") and endsWith("z"))
-5:  Substituted || instead of && twice
-6:  Substituted || instead of && thrice
-5:  Missing detecting gender to be "male"
-5:  Completely missing any of the constraints
-3:  Not separating endsWith("y") and endsWith("z") (i.e. endsWith("y", "z"))
-1:  Missing print statement

TA 3
Solution:

Table = new SimpleTable(“baby.csv”);
count = 0;
for (row: table) {
if (row.getField(“name”).startsWith(“B”) && row.getField(“name”).endsWith(“y”)) {
count = count + 1;
}
}
print (“count: “ + count);

Notes:
-2 fail to initialize count
-1 initialize count inside the loop
-3 not &&
-2 incorrectly/fail to increment count
-1 printing incorrect/missing

TA 4
Solution:

fable = new SimpleTable(“survey.csv”);
table.convertToLowerCase();
Count1 = 0;
Count2 = 0;
for (row: table) {
if (row.getField(“color) == “blue” &&
row.getField(“tv”) == “game of thrones”) {
count1 = count1 + 1;
}

if (row.getField(“color) == “blue” &&
row.getField(“tv”) == “modern family”) {
count2 = count2 + 1;
}
}

print(“game of thrones: “ + count1);
print(“modern family: “ + count2);

Notes:
-3 fail to initialize two counters
-2 initialize inside the loop
-6 for incorrect checks
-3 fail to increment count
-1 fail to print
```