CS101 Midterm

< CS101

CS101 2017 Midterm with Solutions


People did really well on this exam. The median was 96. But I felt the questions were a solid test of our material, so I guess people are just doing well .. fine with me! I would say a score of 90 and above is an A, and everyone passed. The final exam will be cumulative, combining all the midterm material plus the post-midterm material.

Stanford CS101 midterm, Spring 2016-2017

Name (last, first): ___________________,   __________________________
 

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


1. ____ / 37
2. ____ / 6
3. ____ / 6
4. ____ / 6
5. ____ / 15
6. ____ / 15
7. ____ / 15
   _____ / 100

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)

1. Short Answer (37 points)

a. Name the three main hardware systems of a computer. In your answer, circle the system that runs machine code:

b. Suppose you try to run a program on your computer, but the programs fails to start because your computer has run out of something. What has it most likely run out of:

c. What is the name of the system that manages the starting and stopping of programs on a computer:

d. One year I bought a 32 GB USB flash drive. According to the 2-year definition of Moore's law, how many years must pass until I can buy a 64 GB SD card for about the same price:

e. How many different patterns can be represented with 7 bits:

f. How many bytes are required to encode the text of this message: FOMO!

g. Suppose we have a video camera that records at a rate of 500,000 KB per hour. How many GB does it take to record 24 hours (in GB):

h. Suppose there are 20,000 people at Stanford, and a single picture requires 8 million bits. How much capacity is required to store a picture of each person (in GB):

i. Open source software is typically free to download and free to run. What is another right typically granted to users of open source software:

j. Give an example of a signal traveling by an analog process through at least 2 mediums:

k. In lecture we described a compression scheme that records the first sample number, and thereafter just the "delta" difference of each sample from the previous. Suppose we have these samples in compressed form: 1000, +2, +3, -1, +2. What were the original samples and is this a lossless or lossy compression scheme:

l. Suppose we have a pixel with these values: red:100 green:150 blue:50. What are the red, green, and blue values to convert this pixel to grayscale, as we did in lecture and on the homeworks:

2. Basic (6 points)

Suppose the spring.jpg image is 500 pixels wide by 250 pixels high. Write code to change the top half of the image as follows: double the green value of each pixel. It's fine to use literal numbers in your code to identify the parts of the image (as we did in lecture), or any other technique which gets the correct result.

image = new SimpleImage("spring.jpg");
for (pixel: image) {
  // your code here


3. Basic (6 points)

This is like a 5-10-20 puzzle, but not exactly. Write code to change each pixel in the image as follows: set both red and green to be 5 times the original blue value. Then multiply the blue value by 20.

image = new SimpleImage("spring.jpg");
for (pixel: image) {
  // your code here


4. Basic (6 points)

For this problem, the puzzle.png image has been distorted. Write code to fix the image by making the following changes to each pixel: set the red value to 0, and multiply the green and blue values by 10.

image = new SimpleImage("puzzle.png");
for (pixel: image) {
  // your code here


5. Advanced (15 points)

The bird.jpg image shows a red bird with a green background. Write bluescreen code to replace the green background with pixels from moon.jpg. Use the avg technique with a green-high strategy to detect the green background.

image = new SimpleImage("bird.jpg");
back = new SimpleImage("moon.jpg");
back.setAsBig(image);

for (pixel: image) {
  // your code here



6. Advanced (15 points)

For this problem, we have three images which are all the exactly same size: img.jpg img2.jpg img3.jpg. The provided code loads these images into variables image, image2, and image3. For every pixel in image, there are "analogous" pixels at the same x,y in image2 and image3. Write code to change image as follows: for every pixel in image where the red value is less than 100, change that pixel's red value to be the sum of the red values from the 2 analogous pixels.

image  = new SimpleImage("img.jpg");
image2 = new SimpleImage("img2.jpg");
image3 = new SimpleImage("img3.jpg");

for (pixel: image) {
  // your code here

7. Advanced (15 points)

This problem combines bluescreen and grayscale code. The flower.jpg image shows a blue flower against a green background. Write code to change the image as follows: replace each blue pixel in the flower with the analogous pixel from the back image. In addition, the pixels copied from the back image should be changed to grayscale in the flower image. For simplicity, assume that any pixel in the flower image with a a blue value greater than 100 is blue and so should be replaced.

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

for (pixel: image) {
  // your code here

Solution Notes

Problem 1:
a. CPU (circled), RAM, Persistent storage
b. RAM
c. Operating system
d. 2 years (32 GB to 64 GB is 1 doubling)
e. 128 (some wrote 2 to the 7th)
f. 5 (one byte per character)
g. 500,000 KB = 0.5 GB, so 12 GB
h. 8 million bits is 1 MB
* 20,000 yields 20 GB
i. The right to edit the source code
j. Violin: vibrations go from strings to wood to air
Analog phone: vibrations in air to microphone becomes voltage on wire
k. 1000 1002 1005 1004 1006 lossless
l. The pixel should be red:100 green:100 blue:100

Problem 2:

image = new SimpleImage(“spring.jpg”);
for (pixel: image) {
    //your code here
    if (pixel.getY() < 250) {
        pixel.setGreen(pixel.getGreen() * 2);
    }
}

Common errors:
-2 for if pixel.getY() > 250

Problem 3:
image = new SimpleImage(“sprint.jpg”);
for (pixel: image) {
    // your code here
    pixel.setRed(pixel.getBlue() * 5);
    pixel.setGreen(pixel.getBlue() * 5);
    pixel.setBlue(pixel.getBlue() * 20);
}

Common errors: 
-2 for calling getRed()/getGreen() instead of getBlue()
-1 for multiplying by the wrong factors (wrong numbers besides 5 and 20)

Problem 4: 

image = new SimpleImage(“puzzle.png”);
for (pixel: image) {
    \\ your code here
    pixel.setRed(0);
    pixel.setGreen(pixel.getGreen() * 10);
    pixel.setBlue(pixel.getBlue() * 10);
}


Problem 5:

image = new SimpleImage(“bird.jpg”);
back = new SimpleImage(“moon.jpg”);
back.setAsBig(image);

for (pixel: image) {
    // your code here
    avg = (pixel.getRed() + pixel.getGreen() + pixel.getBlue()) / 3;
    if (pixel.getGreen() > avg) {
        pixel2 = back.getPixel(pixel.getX(), pixel.getY());
        pixel.setRed(pixel2.getRed());
        pixel.setGreen(pixel2.getGreen());
        pixel.setBlue(pixel2.getBlue());
    }
}

Common Errors: 

5 points for average, 5 points for setting all the components, 5 points for getting the pixel from back

Problem 6: 

image = new SimpleImage(“img.jpg”);
image2 = new SimpleImage(“img2.jpg”);
image3 = new SimpleImage(“img3.jpg”);

for (pixel: image) {
    if (pixel.getRed() < 100) {
        pixel2 = image2.getPixel(pixel.getX(), pixel.getY());
        pixel3 = image3.getPixel(pixel.getX(), pixel.getY());
        pixel.setRed(pixel2.getRed() + pixel3.getRed());
    }
}

Commmon errors:
    8 points to correctly get pixel 2 and pixel 3
    6 points to set pixel correctly
    1 point for the if statement

Problem 7:

image = new SimpleImage(“flower.jpg”);
back = new SimpleImage(“paris.jpg”);
back.setAsBig(image);

for (pixel: image) {
    //your code here
    if (pixel.getBlue() > 100) {
        pixel2 = back.getPixel(pixel.getX(), pixel.getY());
        avg = (pixel2.getRed() + pixel2.getBlue() + pixel2.getGreen()) / 3
        // Crucial part of this solution was using pixel2 above not pixel (-8)
        pixel.setRed(avg);
        pixel.setGreen(avg);
        pixel.setBlue(avg);
    }
}