CS101 Midterm

< CS101

CS101 2016 Midterm with Solutions


The median was 90, so people did well on the exam. CS101 grades are a combination of a curve and my judgement, mostly giving A's and B's. Looking at the curve, I'd be a little worried about a score below 70. For people who do much better on the final exam than the midterm, we will count the midterm less in their final grade. The final will be cumulative, combining all the midterm material plus the post-midterm material.

Stanford CS101 midterm, Spring 2015-2016

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. ____ / 31
2. ____ / 8
3. ____ / 8
4. ____ / 8
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 (31 points)

a. What are the three main systems of a computer? In your answer, circle the one system that still functions even when it is not powered.




b. How many different patterns can be represented with 8 bits?

c. About how many bytes are required to encode the text of this message: LOL!

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

e. What is the total capacity of one 500 GB hard drive plus 100 20 MB usb flash drives, in GB:

f. Stanford stadium holds about 50,000 people. About how much space is required to hold a separate 100 KB image of every person in the stadium?

g. Suppose a standard RGB digital image is 400 pixels wide by 200 pixels high. How many bytes are required to store its image data without compression?

h.The machine code that comprises a runnable program is produced from what code?

i. What does an "D/A converter" do (one sentence):

j. Suppose it is "opposite day", and so we design a compression scheme which modifies the samples to take up more space, as follows: each sample is replaced by 2 samples, the first new sample is 1 less than the original, the second is always the number 42. For a particular signal the resulting "compressed" form is: 3 42 7 42 14 42 15 42 22 42 41 42. What was the original signal, and is this lossy or lossless compression?

2. Basic (8 points)

Suppose the cronut.jpg image is 400 pixels wide by 200 pixels high. Write code to change the right half of the image to grayscale. 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("cronut.jpg");
for (pixel: image) {
  // your code here


3. Basic (8 points)

Here we'll apply puzzle logic to the cronut. Write code to change the image by multiplying its red, green, and blue values up by 5, 10, and 20 respectively.

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


4. Basic (8 points)

Here we'll apply more logic to the cronut. Write code to change the image as follows: change the red to be double the green and the blue to be half the green.

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


5. Advanced (15 points)

The carrot.jpg image shows an orange carrot with a blue background. Write bluescreen code to replace the blue background with pixels from moon.jpg. Use the avg technique with a red-low strategy to detect the blue background.

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

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



6. Advanced (15 points)

The flower.jpg image shows a green flower in front a red background. For this problem, assume that any pixel from the flower image with green greater than 100 is of the green flower. Change the back image by blending the green flower pixels into the back image, dividing the flower color values by 2.

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

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


7. Advanced (15 points)

The image cat.jpg shows a cat's face, and the cat has blue eyes. Assume that any pixel with blue over 100 is part of the cat's eyes. Change the cat eye pixels as follows: for each of the color values, change the value to be 50% of the original value plus 50% of the corresponding back image pixel value.

image = new SimpleImage("cat.jpg");
back = new SimpleImage("leaves.jpg");
back.setAsBig(image);

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

Solution Notes

Problem 1. Short answer
Each 3 points, except the last which was 4.

a. CPU, RAM, (persistent storage)
last one is circled. Some people wrote "hard drive" or
"flash drive" for persistent storage, which was ok.

b. 2^8 or 256

c. 4 bytes to encode "LOL!"
1 byte per typed letter is the rule of thumb for the traditional
A-Z roman alphabet.

d. 1 GB to 32 GB is 5 doublings. Each doubling is 2 years, so 10 years

e. 100 * 20 MB is 2000 MB which is 2 GB, so 502 GB

f. 50,000 * 100 KB is 5,000,000 KB, is 5,000 MB, is 5 GB

g. 400 * 200 = 80,000 pixels
3 bytes per pixel (one byte for each of R G and B) is 240,000 bytes

h. source code

i. D/A converts digital sample numbers to analog signal
(A/D converter goes the opposite direction)

j. 4 8 15 16 23 42
the scheme is lossless because the original signal is
reproduced perfectly.
As one student wrote on her exam: Not Penny's Boat!



Problem 2.

avg = (pixel.getRed() + pixel.getGreen() + pixel.getBlue())/3;
if (pixel.getX() > 199) {
    pixel.setRed(avg);
    pixel.setGreen(avg);
    pixel.setBlue(avg);
}

-1 for dividing avg by a value other than 3
-2 for setting color to a constant value (per line)
-3 for using height instead of width in if conditional (i.e. 99 or 100)
-3 for using getY() instead of getX()
-3 for not finding X value of pixel using getX()
-3 for not calculating avg



Problem 3.

pixel.setRed(pixel.getRed() * 5);
pixel.setGreen(pixel.getGreen() * 10);
pixel.setBlue(pixel.getBlue() * 20);

-1 for not getting color or correct color (per line)
-1 for not setting color correctly (per line)


Problem 4.

pixel.setRed(pixel.getGreen() * 2);
pixel.setBlue(pixel.getGreen() * 0.5);

4 points for each line
-2 for not setting correct color (per line)
-2 for not getting green color (per line)


Problem 5.

avg = (pixel.getRed() + pixel.getBlue() + pixel.getGreen())/3;
if (pixel.getRed() < avg) {
//get pixel2 from back
pixel2 = back.getPixel(pixel.getX(), pixel.getY());

//copy rgb values from pixel2
pixel.setRed(pixel2.getRed());
pixel.setGreen(pixel2.getGreen());
pixel.setBlue(pixel2.getBlue());
}

-2 not calculating avg
-2 using “pixel.getRed() > avg” instead of “pixel.getRed() < avg”
-2 using blue-high instead of red-low strategy
-2 not using pixel.getX() and pixel.getY() to get coordinates for pixel2
-4 not setting pixel’s RGB values to those of pixel2



Problem 6.

if (pixel.getGreen() > 100) {
    pixel2 = back.getPixel(pixel.getX(), pixel.getY());
    pixel2.setGreen(pixel2.getGreen() + pixel.getGreen()/2);
    // A reasonable alternate reading of the problem was that the "green flower pixels"
    // meant only the green values, not red and blue, so we did not
    // mark off if the next 2 lines were omitted.
    pixel2.setBlue(pixel2.getBlue() + pixel.getBlue()/2);
    pixel2.setRed(pixel2.getRed() + pixel.getRed()/2);
}

-1 for small errors in if statement, or in defining pixel2
-1 for dividing pixel2 by 2 instead of pixel
-4 for setting the color of the wrong pixel
-9 for copying the color rather than blending, or for using the average color


Problem 7.

if (pixel.getBlue() > 100) {
  pixel2 = back.getPixel(pixel.getX(), pixel.getY());
  pixel.setRed(pixel.getRed()/2 + pixel2.getRed()/2);
  pixel.setGreen(pixel.getGreen()/2 + pixel2.getGreen()/2);
  pixel.setBlue(pixel.getBlue()/2 + pixel2.getBlue()/2);
}

-do the if-check
-do the modification on pixel
-form the 50% + 50% blend