CS106A Midterm Preparation

The midterm will be at our regular class time - we'll publish the location + overflow room on the course front page. The exam format will involve you writing solution code to little coding problems as seen below. We're going to use a system where you type code on your computer, but the format is the same as the paper-style questions below. We will grade the problems by hand, just as with a paper exam.

The exam will concentrate on coding problems very similar to the functions you have seen:

Topics not on exam since we only have 50 minutes: Bit, writing a main()

The great thing about a closed-note exam is that it is not necessary to take a normal lecture example, e.g. at_words() from our previous lecture and twist it into weird, unrealistic pattern. On a closed note exam, we can just use the at_words() function right out of lecture. You should be able to solve everything we did in lecture, or section, or on a homework.

The exam grading will focus on getting the correct output, so if you use a 'for/range' to get the right output, and our solution uses a 'while' .. either solution can get full credit so long as it works correctly.

How To Study for a Coding Exam

What are we trying to accomplish with CS106AP? We want everyone to pick up core coding knowledge and skills. These core skills are what we do in lecture, and section, and then on the homeworks. The exams are .. the exact same topics. The exams, lectures etc. .. all resemble each other. The topics on the exam are predictable. Predictable = studying will pay off.

Three levels of working a code concept...

1. See a code concept in lecture

2. Write code in section or on homework while looking at lecture examples

3. Write code on blank sheet of paper exam

These 3 are very different. It's a trap to get stuck at step 2. Your brain will just say "oh yeah, I see how to do that." The blank sheet of paper has a way of emptying out all that stuff you thought you knew. The good news..

(1) You can repeatedly practice these code patterns so you really know them. (2) We are providing a ton of practice problems for you to use (with autograding or not). (3) We will be very forgiving of wrong syntax when grading. We want the right algorithmic ideas, and we give partial credit for partially correct code (unlike the autograder!).

How to study:

Midterm Reference

The midterm will include printed on it a few reminders of python functions we have used. Of course the key is knowing how to call them. We will not generally grade off for syntax. The emphasis is on passing the right numbers to range() or in a slice, and example problems below all feature that sort of complexity. If a problem requires some boilerplate, the problem statement will likely just include the boilerplate for you. Functions in square brackets below may have been mentioned briefly, but we haven't really used them yet, so none of the problems need them for a solution.

# CS106A Exam Reference Reminder
# [square brackets] denote functions listed here that we have not used yet
# Exam questions will not depend on functions we have note used yet
General functions:
  len() int() str() range() list() [sorted()]
String functions:
  isalpha() isdigit() isspace() isupper() islower()
  find() upper() lower() [strip()]
List functions:
  append() extend() pop() [insert()]

SimpleImage:
  # read filename
  image = SimpleImage(filename)
  # create blank image
  image = SimpleImage.blank(width, height)

  # foreach loop
  for pixel in image:

  # range/y/x loop
  for y in range(image.height):
      for x in range(image.width):
          pixel = image.get_pixel(x, y)

Canvas Draw
  canvas.draw_line(x1, y1, x2, y2)
  # x,y is upper left, optional color='red' parameter
  canvas.draw_rect(x, y, width, height)
  canvas.fill_rect(x, y, width, height)
  canvas.draw_oval(x, y, width, height)
  canvas.fill_oval(x, y, width, height)

Grid 2D:
  grid = Grid.build([['row', '0'], ['row', '1']])
  grid.in_bounds(x, y) - True if in bounds
  grid.get(x, y) - returns contents at that x,y, or None if empty
  grid.set(x, y, value) - sets new value into grid at x,y


Read lines out of a text fie:
  with open(filename, 'r') as f:
      for line in f:

Practice Exercises From Lecture and Section

For most of the problems below, you have watched someone walk through a solution, or you have solved it possibly glancing at a similar lecture example. That was fine then. But for the exam, you should be able to solve any of these without access to anything - just your knowledge of Python and maybe making a little drawing to think about your code. Below are section problems which make excellent practice. You should also be able to do the problems linked from each lecture, which often introduce the ideas then seen in section and on the homeworks.

Section Problems: all of the sections and their solutions are listed off our course page.

Problems marked SKIP are not needed for the midterm - they are topics that this year we are not doing before the midterm. In particular, this quarter we are doing "dict" and "bluescreen" algorithms after the midterm.

Midterm Sample Problems

Here are 16 additional problems for more blank-paper practice and to give a sense of the exam structure. These problems are from previous quarters, so they vary slightly from our emphasis this quarter. Some problems have been added to reflect topics novel to this quarter. The in-class exam will likely have fewer than 15 problems. These don't have auto-grader output. Do these on a blank sheet of paper like on the exam. Some of these problems were created by taking a homework or lecture or section problem and changing it a little. The midterm problems may be created that way too.

Warmup Trace Problem

a. For each ??, write what value comes from the Python expression on each line. Note that list(range(xxx)) creates a list of the numbers in that range() sequence.

>>> 1 + 2 - 3 + 4
??
>>> 
>>> 1 + 2 * 3
??
>>> 
>>> 3 + 51 // 10
??
>>> 
>>> s = 'Summer'
>>> s[1]
??
>>>
>>> s[:2]
??
>>>
>>> s[2:]
??
>>> 
>>> list(range(5))
??
>>>
>>> list(range(5, 10))
??
>>>
>>> list(range(6, 10, 2))
??
>>>

b. Function Call - what 3 numbers print when the caller() function runs. This code runs without error.

def one_more(a):
    b = a + 1
    return b


def caller():
    a = 1
    b = 2
    c = one_more(b)
    print(a, b, c)

Grid Problem

(New Oct-2019) For the Grid problems you should understand your solution to the Sand problem and the Movie lecture example: code that returns a Boolean test about the grid, code that potentially changes the grid, and the ability to write a Doctest about the grid.

Suppose we have a program similar to Sand, but where 's' is smoke. Every square in the grid is either 's' smoke, 'r' rock, or None empty.

The "upright" move, is a diagonal move, moving an 's' up one square and towards the right one square.

Reminder of Grid functions:

grid = Grid.build([['row', '0'], ['row', '1']])
grid.in_bounds(x, y) - True if in bounds
grid.get(x, y) - returns contents at that x,y, or None if empty
grid.set(x, y, value) - sets new value into grid at x,y

Before upright move at 0,1:

---
r r
s
---

After upright move:

---
rsr
   
---

a. Write the code for do_upright():

def do_upright(grid, x, y):
    """
    Given an x,y which will be in bounds.
    If there is a smoke at that x,y,
    and the destination "up-right" square is empty and in-bounds.
    Move the smoke from x,y to the upright square.
    Otherwise do nothing.
    """
    pass



b. Write 1 Doctest for the 3 by 2 case shown above. Some code is included, fill in the ?? of each line.

>>> grid = Grid.build(??
>>> do_upright(grid, ??
>>> ??

"Quilt" Problem

(New Oct-2019) You should understand your drawing code for the Quilt program. We are somewhat forgiving about off-by-one errors for coordinates in drawing, which as a practical matter are very hard to see in the output.

Reminder: the canvas draw_line function:

canvas.draw_line(x1, y1, x2, y2) - draws a line from x1,y1 to x2,y2

As on the Quilt homework, the function will take an x,y width,height of a figure positioned on the canvas, and draw lines within that figure.

Given int n which is 2 more, draw n Lines each starting at a point halfway down the left edge of the figure, and extending to points evenly distributed along the bottom edge of the figure. The first point at the leftmost edge, the last point at the rightmost edge, and the other points distributed evenly.

def draw_tri(canvas, x, y, width, height, n):
    pass




Graphics Problems

g1. (SKIP) Bluescreen. We have two image variables, image and back. The images are the same size. Write nested-range loops to access the right half of image. Detect redish pixels using the avg technique. Blend the redish pixels into the analogous pixels of the back image. Instead of regular bluescreen, copy only the red values.

image =  SimpleImage(xxx)
back = SimpleImage(xxx)

# your code here



g2. Given an image, write nested-range loop code to set a 10 pixel wide stripe running down the right side of the image to pure black. Ideally, the code should access only the pixels which need to be changed. The image will be at least 10 pixels wide. (Combines non-1-param range() with images.)

image = SimpleImage(...)
# your code here



g3. Given an image, create a new 'out' image which is three times as wide as the passed in image. Copy the original image to the rightmost third of the out image, but with left and right reversed.

def mirrorish(filename):
    image = SimpleImage(filename)
    # your code here




g4. A sort of funhouse-mirror effect governed by the int parameter n: e.g. if n is 2, squeeze width by 2x. Create a new 'out' image the same height as the original, but with width divided by int n. Copy the original image to out, squeezing it horizontally. For example for n=4, out pixel at x=0 comes from original x=0, x=1 comes from x=4, x=2 comes from x=8, and so on. n=1 should copy the image without squeezing. (Added from section-1, since we did this space-warp type this quarter)

squeeze_width(filename, n):
    # some boilerplate provided
    image = SimpleImage(filename) 
    out = SimpleImage('', width=       , height=         )



Range/Loop/String Problems

p1. Given a string s, return a string of its even index chars followed by its odd index chars. so 'abcde' yields 'acebd'. (Combines non-1-param range with strings.)

def foo(s):
    # your code here



p2. Given non-negative int n. Return a list of n "inner" lists. The first inner list is [50, 51, 52, ... 60], The next inner list is [49, 50, ...59], and so on to make n lists. For n=0 return zero inner lists. So n=3 returns [[50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60], [49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59], [48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58]]

def foo(n):
    # your code here



p3. Given a string s, return a string made of copies of s of steadily decreasing length, so 'abcd' yields 'abcdabcaba'. (range + string problem.)

def foo(s):
    # your code here



p4. Consider the sequence 100, 200, 300, ... n*100. For each number in that sequence, consider the 10 numbers that lead up to that number, inclusive. Return a list of all these numbers, e.g.. n = 4: [91, 92, .. 100, 191, 192, .. 200, ... 300, .. 400]. N will be a positive int. (nested range + list problem.)

def foo(n):
    # your code here



p5. Given a string s, use the string find() function to find the first '<' and the first '>' in the string. If these chars are not present or the '<' is not before the '>', return the empty string. Otherwise, return the chars that are between '<' and '>'. So 'xx<yyy>xxx' returns 'yyy'.

def foo(s):
    # your code here



p6. This nutty function returns a string made up of chars from s. For every char in s, if the char is a digit, compute the int value of that lone digit. If that int is a valid index number into s, append the char at that index to the result. So for example 'xyz029', returns 'xz' since 'x' is at index 0 and 'z' is at index 2. (Old exam problem that plays with char/int fluidity).

def nutty(s):




p7. Given a string s, return a string made of all the chars that are a digit and have an '@' immediately to their left.

def foo(s):
    # your code here



p8. Every '>' in s is followed immediately by a number. The number is made of digit chars. Find all such numbers in the string, and return a list of their int values. (clarified wording, all > have a number). So 'xx>122xxx>66xx' returns [122, 66].

def foo(s):
    # your code here



p9. We have int numbers scattered within a string separated by arbitrary non-digit garbage characters. Each number guaranteed to be exactly 3 digits long. Return a list of all the number's int values.

def foo(s):
    # your code here



p10. Given a string s of even length, if the string length is 2 or less, return it unchanged. Otherwise take off the first and last chars. Consider the remaining middle piece. Split the middle into front and back halves. Swap the order of these two halves, and return the whole thing with the first and last chars restored. So 'x1234y' yields 'x3412y'.

def foo(s):
    # your code here



p11.

(SKIP) Given a list of numbers, build a "counts" dict counting how many times each number appears in the list. After counts is built, loop over the numbers in increasing order, print out each number once followed by its count, like this: Here we are printing the output instead of "return". (This is just the standard dict-count algorithm.)

1 43
2 167
...

def count_nums(nums):
    # your code here



Solutions

Solutions: Warmup

a. Python expressions

>>> 1 + 2 - 3 + 4   # by default proceeds left-right
4
>>> 
>>> 1 + 2 * 3       # */ go before +-
7
>>> 
>>> 3 + 51 // 10    # int divide // truncates downward
8
>>> 
>>> s = 'Summer'
>>> s[1]
'u'
>>>
>>> s[:2]
'Su'
>>>
>>> s[2:]
'mmer'
>>> 
>>> list(range(5))
[0, 1, 2, 3, 4]
>>>
>>> list(range(5, 10))
[5, 6, 7, 8, 9]
>>>
>>> list(range(6, 10, 2))
[6, 8]

b. Function-call

The output is
1 2 3

Key idea: the variable names in each function are independent

Solutions: Grid

a. Write the code for do_upright():

def do_upright(grid, x, y):
    """
    Given an x,y which will be in bounds.
    If there is a smoke at that x,y,
    and the destination "up-right" square is empty and in-bounds.
    Move the smoke from x,y to the upright square.
    Otherwise do nothing.
    """
    if grid.get(x, y) != 's':
        return
    to_x = x + 1
    to_y = y - 1
    if grid.in_bounds(to_x, to_y):
        if grid.get(to_x, to_y) == None:
            grid.set(to_x, to_y, 's')
            grid.set(x, y, None)
    return grid

b. Grid doctest

    >>> grid = Grid.build([['r', None, 'r'], ['s', None, None]])
    >>> do_upright(grid, 0, 1)
    [['r', 's', 'r'], [None, None, None]]

Solutions: Quilt Draw

def draw_tri(canvas, x, y, width, height, n):
    pass
    for i in range(n):
        x_add = (i / (n - 1)) * (width - 1)
        canvas.draw_line(x, y + height // 2, x + x_add, y + height - 1)

Solutions: Graphics Problems

g1.

# g1
image =  SimpleImage(xxx)
back = SimpleImage(xxx)

midx = image.width // 2
for y in range(image.height):
    for x in range(midx, image.width) :
        pixel = image.get_pixel(x, y)
        avg = (pixel.red + pixel.green + pixel.blue) // 3
        if pixel.red > avg:
            back_pixel = back.get_pixel(x, y)
            back_pixel.red = back_pixel.red*0.5 + pixel.red * 0.5

g2.

image = SimpleImage(...)
for y in range(image.height):
    for x in range(image.width-10, image.width):
        pixel = image.get_pixel(x, y)
	pixel.red = 0
        pixel.green = 0
        pixel.blue = 0

g3.

def mirrorish(filename):
    image = SimpleImage(filename)
    # your code here
    out = SimpleImage('', width=image.width * 3, height=image.height)
    # loop x,y over original image
    for y in range(image.height):
        for x in range(image.width):
            pixel = image.get_pixel(x, y)
            # key: locate pixel in out image
            pixel_out = out.get_pixel(out.width - x - 1, y)
            pixel_out.red = pixel.red
            pixel_out.green = pixel.green
            pixel_out.blue = pixel.blue

g4.

def squeeze_width(filename, n):
    image = SimpleImage(filename)
    out = SimpleImage('', width=image.width // n, height=image.height)
    # strategy: iterate x,y over the out pixels, compute
    # scaled * n pixel in original image.
    for y in range(out.height):
        for x in range(out.width):
            pixel_out = out.get_pixel(x, y)
            pixel = image.get_pixel(x * n, y)
            
            pixel_out.red = pixel.red
            pixel_out.green = pixel.green
            pixel_out.blue = pixel.blue
    print(out)

Solutions: Range/Loop/String/Dict Problems

p1.

# p1
def foo(s):
    result = ''
    for i in range(0, len(s), 2):
        result += s[i]
    for i in range(1, len(s), 2):
        result += s[i]
    return result

p2.

def foo(n):
    outer = []
    for i in range(n):
        inner = []
        for j in range(50 - i, 61 - i):
            inner.append(j)
        outer.append(inner)
    return outer

p3.

def foo(s):
    result = ''
    # use the string out to 'end' which we decrease as we go
    for end in range(len(s), 0, -1):
        result += s[0:end]
        # instead of a slice here, you could write a loop
        # to copy the chars 0..end, but the slice is a lot easier)
    return result

p4.

def foo(n):
    result = []
    for i in range(1, n + 1):
        hundred = i * 100
        for j in range(hundred-9, hundred+1):
            result.append(j)
    return result

p5.

def foo(s):
    start = s.find('<')
    end = s.find('>')
    if start == -1 or end == -1 or end < start:
        return ''
    return s[start+1:end]

p6.

def nutty(s):
    result = ''
    for i in range(len(s)):
        if s[i].isdigit():
            val = int(s[i])
            if val < len(s):  # valid index
                result += s[val]
    return result

p7.

def foo(s):
    result = ''
    # Use 1 as start so we can refer to i-1 safely.
    for i in range(1, len(s)):
        if s[i].isdigit() and s[i-1] == '@':
            result += s[i]
    # Alternately could have looked for the '@' and then
    # checked the following char, taking care not to
    # go past len-1.
    return result

p8.

def foo(s):
    result = []
    search = 0
    while True:
        start = s.find('>', search)
        if start == -1:
            break
        end = start + 1
        while end < len(s) and s[end].isdigit():
            end += 1

        num_str = s[start+1:end]
        num = int(num_str)
        result.append(num)
        search = end  # not + 1 why?
    return result

p9.

def foo(s):
    result = []
    search = 0
    while True:
        # find start of number
        start = search
        while start < len(s) and not s[start].isdigit():
            start += 1
        if start >= len(s):
            break
        # Know that len is 3
        num_str = s[start:start + 3]
        result.append(int(num_str))
        search = start + 4
        # what would happen with +0 or +3 here instead?
    return result

p10.

def foo(s):
    if len(s) <= 2:
        return s
    first = s[0]
    last = s[len(s) - 1]
    mid = s[1:len(s) - 1]
    halfway = len(mid) // 2  # index of halfway
    return first + mid[halfway:] + mid[:halfway] + last

p11.

def count_nums(nums):
    counts = {}
    for num in nums:
        if not num in counts:
            counts[num] = 0
        counts[num] += 1
    for num in sorted(counts.keys()):
        print(num, counts[num])