Final Exam Review Guide

Where and When

Test date/time: Tuesday, December 13, 2016 at 7:00 PM
Test location: Some of us are in different rooms for the final!

  • CS 1110 w/ Ibrahim - GIL 190
  • CS 1110 w/ Sherriff - GIL 130
  • CS 1111 w/ Praphamontripong - MEC 205 (normal classroom)

Test duration: 3 hours
Review session: Monday, December 12, 12:00-1:30 PM, CHM 402

Conflicts

All conflicts should have been reported to the form posted on Piazza and sent out via email. Contact Prof. Sherriff if you have questions.

What to bring

  • A writing utensil - pen or pencil
  • Your UVa student ID - you will need to show your ID to turn in your final exam

No laptops, calculators, scratch paper, backpacks, books, or anything else should be brought. These items will be left in the back/front of the room if you bring them. It is also highly recommended to dress in layers. It is likely to get quite warm in the room.

Test Specifics

We are writing the test to be 1 1/2 times the length of the previous two tests. So, we are writing the test to take 1 1/2 hours, but you will have all 3 hours.

The format of the test will be similar to what you have seen, but with basically a few more pages. You can expect similar multiple choice, short answer, code reading, and code writing questions to previous tests.

Major things you can expect:

  • A "long" coding question, one that asks you to solve a problem and will encourage you to use the various tools you've picked up this semester
  • Reading and evaluating methods / code snippets
  • Some questions related to material from the first two thirds of the class
  • Some questions specifically about the final third of the class

Things that we will definitely not ask:

  • How to use specific libraries, such as gamebox, cImage, Turtle, beautifulsoup4, etc. without providing the API
  • Chase activities
  • Professor AMAs

Topics

All topics from the previous two tests are fair game. You can find their lists here:

Additional Topics:

Gamebox

  • We won't ask you to code any gamebox/pygame code
  • It would be good to consider some of the basic algorithms used such as taking a moving character and looping over all of the walls/platforms to see if it is touching any of them

Testing

  • Know the difference between a fault and a failure.
  • Be able to describe the three categories of failures from earlier in the semester: syntax, runtime, logical.
  • Be able to identify a set of good test cases to fully test a simple function.

Algorithms

  • Be able to describe the basic algorithms for bubble sort, insertion sort, and selection sort.

Image Manipulation

  • The concept of a picture and pixel as represented in Python (basically, a 2D list of pixels, where a pixel is a single color point)
  • General idea of the various image algorithms work
  • You may have to read and interpret image algorithms on the test, so understand the basics of how code and algorithms we have done works!

Study Hints

Example questions to look at

Link to Coding Questions from Fall 2015 Final Exam

Link to Key to Fall 2015 Coding Questions

Link to Coding Questions from Spring 2016 Final Exam

Link to Key to Spring 2016 Coding Questions

Here are some questions from the Gaddis book that we think are good ones to review with:

  • Chapter 5 (p. 229) - 4, 5, 7, 13
  • Chapter 6 (p. 288) - 1, 4, 5, 10
  • Chapter 7 (p. 334) - 2, 3, 6, 7
  • Chapter 8 (p. 366) - 2, 4, 6, 9
  • Chapter 9 (p. 416) - 3, 4, 5, 7

Remember: You have more time!

Take the time to write out your code/algorithm on scratch paper FIRST! You've got the time on the final to really work through the options here and write better (and hopefully easier to read) code. So use it!

Check out the lab code

We will be adding example solutions to past labs - so check the Previous Labs page!

Practice coding on paper

You'll be writing code on paper. This feels different than writing it in Eclipse. You don't want to be surprised by how different it feels. Practice writing code by hand.

A few small syntax errors is OK. But if you are really off we will take off points. Try to write correct code.

We'll give you any imports you might need - so don't worry about memorizing those.

Try re-solving the POTD and Lab problems on paper without looking at your code or textbook.

You can find more sample problems in Programming Challenges in the textbook. We do not, however, have the answer key to share with you.

Practice reading code

We will show you code and ask you what it does. You won't be able to have Python run it. Practice thinking through code without running it.

Review the Lectures

Not everything in the book is equally important. Review the lecture notes to see what we emphasized. If you are confused by some point, check the audio. You might want to listen to the audio of the other instructor (the one you didn't hear in class) so that you can get a different perspective on the material.

more ...


Lecture 40 (Sherriff) - Programming Review

Lecture Date: Wednesday, November 30

We'll do some example programs from previous exams and talk about some of the things you might expect programming-wise on the final. Consider this exam review part 1.

Link to Coding Questions from Fall 2015 Final Exam

Link to Key to Fall 2015 Coding Questions

Rotate an image:

from cImage import *

# Prompt the user for a filename
file_name = 'mtn.gif' #input("Filename?: ")

clockwise = int(input("0 for Clockwise - 1 for Counter Clockwise:  "))

# Open an image
old_image = FileImage(file_name)

# Open a window that is twice the size of the original image
image_window = ImageWin("Image Processing", old_image.width, old_image.height)

# Draw the image on the window
old_image.draw(image_window)

# Create a new, blank image
new_image = EmptyImage(old_image.height, old_image.width)

new_image_window = ImageWin("Rotated", old_image.height, old_image.width)

# For each pixel in the original image...
for row in range(old_image.height):
    for col in range(old_image.width):
        # ... get the original pixel ...
        oldPixel = old_image.getPixel(col, row)

        # ... and draw it in the correct place in the new image!
        # Fill in your code here!

# Draw the new image
new_image.draw(new_image_window)

# Wait for a user to click the window to close the image
image_window.exitOnClick()

more ...

Lecture 39 (Sherriff) - Image Manipulation 2

Lecture Date: Monday, November 28

More image manipulation algorithms today!

Our main algorithms for the day will be:

  • Grayscale
  • Resizing
  • Green Screen
  • Edge Detection
  • Image Differences (if time)

Grayscale

The basic idea here to get the overall intensity of the color by adding up the red, green, and blue values and then taking the average. Remember that for a pixel to be gray (or black or white), all three RGB values have to be the same.

# Here we define a method that will take a pixel
# and return a pixel that is the right intensity of gray
def negative_pixel(old_pixel):
    intensity = (old_pixel.getRed() + old_pixel.getGreen() + old_pixel.getBlue()) // 3
    new_pixel = Pixel(intensity, intensity, intensity)
    return new_pixel

Resizing

With resizing, we will either be taking a fraction of the pixels (to make the image smaller) or duplicating pixels (to make the image bigger). We begin by creating a new image at the new size. Then, as we adjust the looping through our original image based on the scaling factor - we either skip pixels to make a smaller image or grab the same pixel multiple times to enlarge it.

from cImage import *

# Open an image
old_image = FileImage('rotunda.gif')

image_window_old = ImageWin("Original", old_image.width, old_image.height)

# Draw the image on the window
old_image.draw(image_window_old)

scale = float(input("Scale?: "))

new_image = EmptyImage(int(old_image.width* scale), int(old_image.height* scale))

image_window_new = ImageWin("Scaled", int(old_image.width* scale), int(old_image.height* scale))

for row in range(int(old_image.height*scale)):
    for col in range(int(old_image.width*scale)):
        old_pixel = old_image.getPixel(int(col/scale), int(row/scale))
        new_image.setPixel(col, row, old_pixel)

new_image.draw(image_window_new)

image_window_new.exitOnClick()
image_window_old.exitOnClick()

Green Screen

Take two pictures, one in which the background is completely one solid color that you wouldn't normally find in a "typical" picture. (This is one reason TV weathermen don't wear green...) Then, as you loop through both pictures, pick the pixels from the background image if the matching pixel from the foreground image is green. Otherwise, take the pixel from the foreground image. Here are two images we can work with:

Code:

from cImage import *

def isGreen(greenPixel):
    if greenPixel.getGreen() > greenPixel.getRed() + greenPixel.getBlue():
        return True
    return False

green_image = FileImage('ninja.gif')
background_image = FileImage('mtn.gif')
image_window = ImageWin("Green Screen", green_image.width * 3, green_image.height)
green_image.draw(image_window)
background_image.setPosition(green_image.width + 1, 0)
background_image.draw(image_window)

combined_image = EmptyImage(green_image.width, green_image.height)

for row in range(green_image.height):
    for col in range(green_image.width):
        if isGreen(green_image.getPixel(col, row)):
            new_pixel = background_image.getPixel(col, row)
            combined_image.setPixel(col, row, new_pixel)
        else:
            new_pixel = green_image.getPixel(col, row)
            combined_image.setPixel(col, row, new_pixel)

combined_image.setPosition(background_image.width + green_image.width + 1, 0)
combined_image.draw(image_window)

image_window.exitOnClick()

Edge Detection

The edge detection algorithm will show us where the edges of objects are in an image and highlight them. The basic idea is that we can look at every pixel and then see if the pixels next to it are substantially different in intensity. To do this, we will apply a set of convolution matrices called Sobel operators to each pixel. The set consists of two matrices: one that looks for differences on the x axis and one on the y axis.

/images/mask_s.jpg

The steps of the algorithm are:

  • Convert the original image to grayscale
  • Create an empty image of the same size as the original
  • Then, for each pixel:
  • Convolve the pixel with the x_mask, resulting in an int called gX

  • Convolve the pixel with the y_mask, resulting in an int called yY
  • Compute the square root of the sum of squares of gX and gY called g
  • Based on the value of g, assign the corresponding pixel in the new image to black or white

One example would be if g > 175, make the pixel black and otherwise white.

import cImage
import math

from cImage import *

def convolve(image, pixel_row, pixel_col, kernel):
    k_col_base = pixel_col - 1
    k_row_base = pixel_row - 1

    sum = 0
    for row in range(k_row_base, k_row_base + 3):
        for col in range(k_col_base, k_col_base + 3):
            k_col_index = col - k_col_base
            k_row_index = row - k_row_base

            pixel = image.getPixel(col, row)
            intensity = pixel.getRed()

            sum = sum + intensity * kernel[k_row_index][k_col_index]

    return sum

def grayscale_image(image):
    new_image = EmptyImage(image.width, image.height)

    for row in range(image.height):
        for col in range(image.width):
            old_pixel = image.getPixel(col, row)
            intensity = (old_pixel.getRed() + old_pixel.getGreen() + old_pixel.getBlue()) // 3
            new_pixel = Pixel(intensity, intensity, intensity)
            new_image.setPixel(col, row, new_pixel)

    return new_image

# Open an image
old_image = FileImage('whiteside.gif')

image_window_old = ImageWin("Original", old_image.width, old_image.height)

# Draw the image on the window
old_image.draw(image_window_old)

new_image = EmptyImage(int(old_image.width), int(old_image.height))

image_window_new = ImageWin("Edges", int(old_image.width), int(old_image.height))

new_gray_image = grayscale_image(old_image)

black_pixel = Pixel(0,0,0)
white_pixel = Pixel(256, 256,256)
x_mask = [[-1,-2,-1],[0,0,0],[1,2,1]]
y_mask = [[1,0,-1],[2,0,-2],[1,0,-1]]

for row in range(1,new_gray_image.height -1):
    for col in range(1,new_gray_image.width -1):
        gx = convolve(new_gray_image, row, col, x_mask)
        gy = convolve(new_gray_image, row, col, y_mask)
        g = math.sqrt(gx**2 + gy**2)

        if g > 50:
            new_image.setPixel(col, row, black_pixel)
        else:
            new_image.setPixel(col, row, white_pixel)

new_image.draw(image_window_new)

image_window_new.exitOnClick()
image_window_old.exitOnClick()

Image Difference

Image subtraction shows us the difference between two images, highlighting what has changed. The Pixel class provides a method to determine the distance between two colors. We can use this to loop over the images.

more ...

Lecture 38 (Sherriff) - Image Manipulation

Lecture Date: Monday, November 21

For the next few days, we are going to look at the algorithms behind some basic image manipulation.

First thing's first: we need to know how to load in a picture into our Python programs. We will be using a library called cImage that was written at Luther College specifically for use in CS 1 courses.

To get started, download these files and move them into your PyCharm project:

We are going to be working mainly with .gif files. If you would like to use something else (like .png or .jpg), you need to install the pillow Python library. (In PyCharm, open your Preferences/Settings, and use the Project Interpreter screen to install pillow, just like you did with the other libraries we have used.)

Drawing with Pixels

We started our programming journey by learning to draw pictures with the Turtle. But what exactly is a "picture" in the context of a computer program?

In effect, it's a 2D array of pixels.

Well, what's a pixel?

A pixel is the smallest display element of a picture. It could be dots on your monitor or TV, or how small an ink jet printer can put a dot on your paper (although we still typically call that "dots"). The pixel specifies what color (or components of colors) should be used to display that particular location in accordance with a color model. "Pixel" is short for "picture element."

Printers (and paints and crayons...) use a subtractive color model. That is, as you add more color (paint), more light is absorbed. Thus, adding in all the colors makes the color black, as shown in the CMYK model below.

CMYK

However, computer monitors (and all forms of light, like stage lighting) use an additive color model, like RGB.

RGB

So, as we add more and more colored lights, we get closer to white, not black!

In RGB, each of the three primary colors (Red, Green, and Blue) can have a value from 0 to 255. This allows for 16,777,216 colors (in theory)!

For example, (255,0,0) is red. But (128,0,0) is also red. It's just not a "saturated" or bright as the first red. If all three values of R, G, and B are the same, you get some shade of gray (or white or black).

Many pixels also have a fourth value - alpha. That tells the pixel how much to blend with any images behind the one that is currently "on top" and about to be drawn.

How many pixels?

It's a big question when you buy a new camera. "How many megapixels is this thing?"

For reference:

  • An old, standard TV is about 852 x 480 = 400K pixels
  • A 1080p HD TV is 1920 x 1080 = 2M pixels
  • Many laptop monitors are 1680 x 1050 pixels
  • A "retina" MacBook has 2880 x 1800 pixels
  • An 8 megapixel camera has 3264 x 2448 pixels

So, why does resolution really matter if the monitors can't display all that information? The more information you have, the more options you have, in a sense. Imagine you wanted to crop a picture. Well, with more pixels, the resulting image you end up with will still have a lot of data in it, providing a clearer picture. Also, the more pixels you have the better a print version of the image will be. This helps eliminate that "blocky" look you see when you try to print a picture at the wrong resolution.

cImage

The cImage library we will use has several objects in it that we can use to manipulate pictures:

  • FileImage - creates an image from a file you open
  • EmptyImage - creates a blank image that you can change
  • ImageWin - creates a window you can display an image inside

When you make an image you can use the following to manipulate it:

  • getPixel(col, row) - gets the pixel at that position
  • setPixel(col, row, pixel) - puts a new pixel at that position

See the example code for more examples!

Example Code

Flipping an image:

# Flipping an image
from cImage import *

# Open an image
old_image = FileImage('uva.gif')

# Open a window that is twice the size of the original image
my_image_window = ImageWin("Image Processing", old_image.width * 2, old_image.height)

# Draw the image on the window
old_image.draw(my_image_window)

# Create a new, blank image
new_image = EmptyImage(old_image.width, old_image.height)

# For each pixel in the original image...
for row in range(old_image.height):
    for col in range(old_image.width):
        # ... get the original pixel ...
        oldPixel = old_image.getPixel(col, row)

        # ... and draw it in the opposite place in the new image
        new_image.setPixel(old_image.width - col-1, row, oldPixel)

# Make sure to put the new image over to the side the right number of pixels
new_image.setPosition(old_image.width + 1, 0)

# Draw the new image
new_image.draw(my_image_window)

# Wait for a user to click the window to close the image
my_image_window.exitOnClick()

Taking the negative of an image:

from cImage import *

# Here we define a method that will take a pixel
# and return a pixel that is "flipped" as far as RGB is concerned
def negative_pixel(old_pixel):
    new_red = 255 - old_pixel.getRed()
    new_green = 255 - old_pixel.getGreen()
    new_blue = 255 - old_pixel.getBlue()
    new_pixel = Pixel(new_red, new_green, new_blue)
    return new_pixel

# Open an image
old_image = FileImage('uva.gif')

# Open a window that is twice the size of the original image
image_window = ImageWin("Image Processing", old_image.width * 2, old_image.height)

# Draw the image on the window
old_image.draw(image_window)

# Create a new, blank image
new_image = EmptyImage(old_image.width, old_image.height)

# For each pixel in the original image...
for row in range(old_image.height):
    for col in range(old_image.width):
        # ... get that pixel ...
        old_pixel = old_image.getPixel(col, row)
        # ... flip the pixel ...
        new_pixel = negative_pixel(old_pixel)
        # ... and put that pixel in the new image
        new_image.setPixel(col, row, new_pixel)

# Make sure to put the new image over to the side the right number of pixels
new_image.setPosition(old_image.width + 1, 0)

# Draw the new image
new_image.draw(image_window)

# Wait for a user to click the window to close the image
image_window.exitOnClick()

more ...

Lecture 37 (Sherriff) - Algorithm Design

Lecture Date: Friday, November 18

Okay, computer scientists! I've got two new algorithms for you! Let's see if we can code them up and figure out what the complexity is!

I call them yolo_search and yolo_sort.

Here's the pseudocode for yolo_search:

while(I haven't picked the number I'm looking for yet) {
    pick a number at random from the list
}

We can even do advanced_yolo_search!

make a copy of my list
while(I haven't picked the number I'm looking for yet) {
    pick a number at random from the list
    if it's not the number {
        delete it from the list
    }
}

There's a slight problem with this algorithm. Every time we delete something from the list, all the indices change... so if we are looking for a particular index, this doesn't work. If we are looking for a particular item from the list, it works fine.

What's the complexity of these two searching algorithms? How do we know? Can we code them up?

Let's take a look at yolo_sort now:

while(the list isn't in order) {
    shuffle the list
}

How about this one? What's the complexity? How can we code it up? How long will it take to run?

import random

def check_list_order(list_to_verify):
    index = 0
    while index < len(list_to_verify) - 1:
        if list_to_verify[index] > list_to_verify[index + 1]:
            return False
        index += 1
    return True


def yolo_search(list_to_search, item_to_find):
    steps = 1
    random_index = random.randint(0,len(list_to_search)-1)
    while list_to_search[random_index] != item_to_find:
        random_index = random.randint(0, len(list_to_search) - 1)
        steps += 1

    return random_index, steps


def advanced_yolo_search(list_to_search, item_to_find):
    temp_list = list_to_search.copy()
    steps = 1
    random_index = random.randint(0, len(temp_list) - 1)
    while len(temp_list) > 1:
        steps += 1
        if temp_list[random_index] != item_to_find:
            del temp_list[random_index]
            random_index = random.randint(0, len(temp_list) - 1)
        else:
            return temp_list[random_index], steps

    return "Not here!", steps



def yolo_sort(list_to_sort):
    temp_list = list_to_sort.copy()
    steps = 1
    while not check_list_order(temp_list):
        random.shuffle(temp_list)
        steps += 1
    return temp_list, steps



def bubble_sort(list_to_sort):
    steps = 1
    temp_list = list_to_sort.copy()
    for i in range(len(temp_list)):
        for j in range(i+1, len(temp_list)):
            steps += 1
            if temp_list[j] < temp_list[i]:
                temp_list[j], temp_list[i] = temp_list[i], temp_list[j]

    return temp_list, steps


# Using the min function is slightly cheating as 
# it optimizes a bit more than what we did in class
def selection_sort(list_to_sort):
    steps = 1
    temp_list = list_to_sort.copy()
    for i in range(len(temp_list)):
        steps += 1
        mini = min(temp_list[i:])
        min_index = temp_list[i:].index(mini)
        temp_list[i + min_index] = temp_list[i]
        temp_list[i] = mini

    return temp_list, steps


my_list = [4,5,2,3,7,9,6,1,8]
short_list = [3,2,1]

print("yolo_search", yolo_search(my_list, 8))
print("advanced_yolo_search",advanced_yolo_search(my_list,8))
print("advanced_yolo_search",advanced_yolo_search(my_list,10))
print("yolo_sort",yolo_sort(my_list))
print("bubble_sort", bubble_sort(my_list))
print("selection_sort", selection_sort(my_list))

more ...

Lecture 36 (Sherriff) - Algorithms

Lecture Date: Wednesday, November 16

Today we'll look at four particular algorithms that have been important in computing (well... at least in CS1) for a very long time.

Specifically:

We'll do some in-class activities to show exactly how these algorithms work. We won't really look at code yet - the purpose is to figure out just how "good" each of these algorithms is in various circumstances.

To search a list, we could:

  1. Look at each element in turn, stopping when/if we find it. In python, this process becomes a simple for loop and is called Linear Search. If the list has n elements, the loop might repeat as many as n times.

  2. If we know the list is in some kind of order, look at the middle element and then consider only half the list, repeating until we find the element we want. This is called Binary Search If the list has n elements, we can cut it in half at most log2(n) times.

To sort a list, we could:

  1. Compare neighboring elements, swapping them if they are out of order. This is called Bubble Sort. In general, this requires us to look across the list repeatedly; roughly speaking, we have to walk the entire list (n elements) n times, so the program might take as much as n2 times.

  2. Find the smallest value and move it to a new list, the repeat until we can moved them all. This is called Selection Sort. Finding an element (linear search) takes n time, and we have n of them to find, so we are still in n2 time overall, like bubble sort.

  3. Take the next item in the list and then move it to the correct place by shifting the previous items. This is called Insertion Sort. Moving down the list (linear search) takes n time, and we may have to move n of them to find the right spot, so we are still in n2 time overall, like bubble sort.

  4. Split the list in half, sort each half, and then merge the two halves in order. This is called Merge Sort. Merging in takes time proportional to n, and we can split at most log2(n) times, for a total of n log2(n) time.

As a point of context,

  • There are around 8,000,000,000 people on Earth
  • Suppose we can handle a million people per second
  • Then we expect

    • linear search to take 8,000 seconds or about 2 hours
    • binary search to take 0.000033 seconds
    • bubble or selection sort to take over a trillion years, more than 70 times larger than the current estimated age of the universe
    • merge sort to take 264,000 seconds or about 3 days

    Note that all of these are approximate, but they within an order of magnitude of the right answers

more ...


Lecture 34 (Sherriff) - Testing

Lecture Date: Friday, November 11

Software is everywhere, and therefor when software fails, it can have an impact on your life. From something as simple as having to reboot your phone or computer to something much more serious like the phone or electric grid going down... or Netflix...

How might a software failure affect you? What things might affect your day-to-day life?

Famous Software Failures

  • (1997) Ariane 5 explosion: Exception-handling bug forced self-destruct on maiden flight (64-bit to 16-bit conversion), causing $370 millions
  • (1999) NASA’s Mars lander: Crashed due to a unit integration fault
  • (2003) Northeast blackout: The alarm system in the energy management system failed due to a software error and operators were not informed of the power overload in the system – affected 40 million people in 8 US states, 10 million people in Ontario, Canada
  • (2012) Knight Capital’s trading software: Faults in a new trading algorithm causes $440 millions
  • (2014) Dropbox’s outage was due to a fault in a maintenance script
  • (2016) Information lost after clicking the back button while using TurboTax web software

We have already discussed failures. A failure is incorrect behavior with respect to the requirements or other descriptions of the expected behavior. We looked at three different categories of failures:

  • syntax - a problem with the code you wrote such that the system doesn't even run
  • runtime - a problem with the code such that it crashes upon execution
  • logical - a problem with the code in that it doesn't "do what it is supposed to"

The "problems" mentioned in these definitions are called faults or more commonly bugs. Mistakes by the program lead to leaving faults in the code, which turn into errors upon execution that can lead to failures in the system.

tests.png

Testing is the process of finding input values that exercise the various parts of your code to ensure there are no faults and that no failures occur. It's important to note that it is (in general) difficult at best to find all of the faults in a system. We are trying to improve the quality of the system and reduce overall software development costs.

When do you test and how much do you test? Who does the testing?

Let's consider some simple examples!

more ...