Please see the course page for timing and instructions for the midterm. The midterm will involve writing code for little coding problems like the practice problems below. The exam will be 60 minutes long, with something like 6-8 questions. We'll use a system where you type code on your computer, but the format is the same as a traditional pen-and-paper exam, so there is no "Run" button. We do not grade the questions all-or-nothing like a computer — instead, we look at the code carefully, identifying each part that is right to award partial credit. We also don't mark off for syntax. So if a student wrote this for a list
lst =  lst.add('i'}
We could still give that full credit, even though the name of the function is wrong and one parenthesis is a curly bracket. If we can see the right idea in there, that's good enough for us. We are interested in the algorithm in the solution code, not the syntax.
Topics on the exam: simple Bit (hw1), images/pixels/nested-loops (hw2), 2-d grids (hw3), strings, loops, simple lists (hw4)
Topics not on exam: bit decomposition problems, bluescreen algorithm, writing main(), file reading
We will provide a basic reference for the Python functions we've used (shown below), but other than that the exam is closed-note. Closed-note exams are actually better for the students, though you may not feel that way at first! With an open note exam, the exam questions cannot resemble the lecture examples too closely, leading to weird, complicated questions. With a closed-note exam, we can take nice, normal example functions from lecture, e.g. brackets(s), and just make the exam out of those. You will notice that the practice problems below resemble the lecture examples and homework problems. You should be able to solve any problem 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 produces the correct output.
The exam will provide enough time to write solutions, but not lots of time. Part of practicing your code writing is building skill and quickness. You want to be able to write the easy parts quickly, so you can take your time on the hard parts.
What is the goal of CS106A? 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 in lecture with some understanding
2. Write code in section or on homework while looking at lecture examples
3. Write code on blank sheet of paper without any references
The bad news: It's a trap to get stuck at step 2. Your brain will look at one of our examples and think "oh yeah, I see how to do that." On the day of the exam, you may look at that first blank screen, and find yourself completely stuck. The key is, you need to practice with the blank sheet, writing the code out, not just looking at it. The good news..
(1) We publish many examples of the code patterns we care about. (2) We are providing many practice problems for you to use. (3) We will be 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:
We have a new feature on the experimental server. Go to a section, like Bit Puzzles:
Go to the first problem. At the bottom of the screen, turn on Practice Mode. In this mode, your previously entered code is temporarily blocked, so you can try practicing things fresh again and again. It keeps a timer of how long you've been coding and how many problems you have solved. Many of the sections on the experimental server are perfect for studying for the midterm: bit puzzles, image nested, image section, string2, string3, string4, list1, strlisthw. Practice to build speed, skill, and confidence.
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 Bit: bit = Bit(filename) bit.front_clear() bit.left_clear() bit.right_clear() bit.move() bit.left() bit.right() bit.paint('red') [bit.erase()] General functions: len() int() str() range() [list() sorted()] String functions: isalpha() isdigit() isspace() isupper() islower() find() upper() lower() [strip()] List functions: append() index() [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) Grid 2D: grid = Grid.build([['row', '0'], ['row', '1']]) grid.width, grid.height - properties 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) as f: for line in f:
We have a selection of practice problems below. Homework problems are also an excellent, and the exam problems will often be similar to homework problems. Section problems are also a good source of practice.
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.
>>> 3 + 4 - 1 + 2 ?? >>> >>> 1 + 2 * 3 ?? >>> >>> 3 + 51 // 10 ?? >>> >>> s = 'Summer' >>> s ?? >>> >>> s[:2] ?? >>> >>> s[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)
Bit is in a world that contains a single rectangle of filled squares. Bit is to the right of the rectangle, facing a block on its right side as shown in this representative example:
Move bit forward to the edge of the rectangle. Then move bit down past the lower right corner of the rectangle. Finally, move bit to the left side of the world, painting every square occupied blue. Your code should work for any position and size rectangle, and bit will always start facing a block on the right side of the rectangle as in the example above.
def do_midterm(filename): bit = Bit(filename) pass
The provided code loads the image for the given filename. The int parameter n will be between 0 and the width of the image. Consider two vertical stripes, n pixels wide, running down the left and right sides of the image. Write nested loop code to set all the red values within the stripes to 0. Return the changed image.
def stripes(filename, n): image = SimpleImage(filename) # your code here return image
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. Return the out image.
def mirrorish(filename): image = SimpleImage(filename) # your code here return out
Given an image and int n which is zero or more. Create a new 'out' image which is n pixels wider than the original. In a vertical stripe, n pixels wide, running down the left side of the output, set all the green values to 0, making it purple. Copy the original image to the area to the right of the stripe. Return the output image.
def wider(filename, n): image = SimpleImage(filename) # your code here
For the Grid problems you should understand the Peep and Movie lecture examples and your solution to the Sand homework: 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.
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, ?? >>> ??
There are two functions for this problem, and you can get full credit for each function independent of what you do on the other function.
We have a Grid representing Yellowstone park,
and every square is either a person
a yelling person
'y', a bear
'b', or empty
a. is_scared(grid, x, y): Given a grid and an in-bounds x,y. Return True if there is a person or yelling person at that x,y, and there is a bear to the right of x,y or above x,y. Return False otherwise. (One could check more squares, but we are just checking two.)
b. run_away(grid): This function implements the idea that when a person is scared of a bear they they begin yelling and try to move one square left. Loop over the squares in the grid in the regular top to bottom, left to right order (this loop is provided in the starter code).
For each square, if is_scared() is True, (1) First set the person stored in the grid to 'y' (i.e. they are yelling). (2) Second, if there is an empty square to their left, then move the person to that square leaving their original square empty. You may call is_scared() even if you did not implement it.
def is_scared(grid, x, y): pass def run_away(grid): for y in range(grid.height): for x in range(grid.width): pass
str1. Given a string s. Return a string made of the upper case chars from s, so 'Hi TherE' returns 'HTE'.
str2. Given a string s. Find 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
str3. 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).
str4. 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
str5. Given a string s. Consider all the digit chars in s. Construct and return a list of all the digit chars in s. So for example 'A34and6' returns ['3', '4', '6']. Return the empty list if there are no digits.
This problem is similar to the Crypto homework with the simplification that the encryption is done entirely with lowercase chars.
This "double" encryption uses two source lists, src1 and src2, and two slug lists, slug1 and slug2. All the lists contain lowercase chars and are the same length. Here is the double_encrypt() algorithm: use the lowercase version of the input char, which may be uppercase. If the char is in src1, return the char at the corresponding index in slug1.
If the char is in src2, return the char at the corresponding "reverse index" in slug2, e.g. like this for lists length 4:
index reverse-index 0 3 1 2 2 1 3 0
If the char is not in src1 or src2, return the char unchanged. No char appears in both src1 and src2.
Double Encrypt Example (len 4) src1 = ['a', 'b', 'c', 'd'] slug1 = ['s', 't', 'u', 'v'] src2 = ['e', 'f', 'g', 'h'] slug2 = ['w', 'x', 'y', 'z'] encrypt 'A' -> 's' encrypt 'e' -> 'z' encrypt 'f' -> 'y' encrypt '$' -> '$'
def double_encrypt(src1, slug1, src2, slug2, char): pass
a. Python expressions
>>>>>> 3 + 4 - 1 + 2 # by default proceeds left-right 8 >>> >>> 1 + 2 * 3 # */ go before +- 7 >>> >>> 3 + 51 // 10 # int divide // truncates downward 8 >>> >>> s = 'Summer' >>> s 'u' >>> >>> s[:2] 'Su' >>> >>> s[2:] 'mmer' >>>
The output is 1 2 3 Key idea: the variable names in each function are independent
def do_midterm(filename): bit = Bit(filename) # up to block while bit.front_clear(): bit.move() # down the side bit.left() while not bit.right_clear(): bit.move() bit.right() bit.paint('blue') while bit.front_clear(): bit.move() bit.paint('blue')
def stripes(filename): image = SimpleImage(filename) for y in range(image.height): for x in range(n): # setting both left and right sides # with one loop. Could be solved with # multiple loops. pixel_left = image.get_pixel(x, y) pixel_left.red = 0 pixel_right = image.get_pixel(image.width - 1 - x, y) pixel_right.red = 0 return image
def mirrorish(filename): image = SimpleImage(filename) # your code here out = SimpleImage.blank(image.width * 3, 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 - 1 - x, y) pixel_out.red = pixel.red pixel_out.green = pixel.green pixel_out.blue = pixel.blue return out
def wider(filename, n): image = SimpleImage(filename) # your code here out = SimpleImage.blank(image.width + n, image.height) # purple stripe at left for y in range(image.height): for x in range(n): pixel_stripe = out.get_pixel(x, y) pixel_stripe.green = 0 # copy image to space n pixels over for y in range(image.height): for x in range(image.width): pixel = image.get_pixel(x, y) pixel_out = out.get_pixel(n + x, y) pixel_out.red = pixel.red pixel_out.green = pixel.green pixel_out.blue = pixel.blue return out
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 grid to_x = x + 1 # using vars, though not required 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]]
def is_scared(grid, x, y): # pass # A person there if grid.get(x, y) == 'p' or grid.get(x, y) == 'y': # bear to the right! if grid.in_bounds(x + 1, y) and grid.get(x + 1, y) == 'b': return True # bear above! if grid.in_bounds(x, y - 1) and grid.get(x, y - 1) == 'b': return True return False def run_away(grid): for y in range(grid.height): for x in range(grid.width): # pass if is_scared(grid, x, y): grid.set(x, y, 'y') # begin yelling if grid.in_bounds(x - 1, y) and grid.get(x - 1, y) == None: # Move the 'y' one to the left grid.set(x - 1, y, 'y') grid.set(x, y, None)
def uppers(s): result = '' for ch in s: if ch.isupper(): result += ch return result
def foo(s): start = s.find('<') end = s.find('>') if start == -1 or end == -1 or end < start: return '' return s[start + 1:end]
def nutty(s): result = '' for i in range(len(s)): # using for/i/range, but # for/ch/s works fine too if s[i].isdigit(): val = int(s[i]) if val < len(s): # valid index result += s[val] return result
def foo(s): if len(s) <= 2: return s first = s last = s[len(s) - 1] mid = s[1:len(s) - 1] halfway = len(mid) // 2 # int div needed return first + mid[halfway:] + mid[:halfway] + last
def digits(s): result =  for ch in s: if ch.isdigit(): result.append(ch) return result
def double_encrypt(src1, slug1, src2, slug2, char): """ # No Doctests needed for your solution, but we use them # to write the question >>> # Make len-4 lists for testing >>> src1 = ['a', 'b', 'c', 'd'] >>> slug1 = ['s', 't', 'u', 'v'] >>> src2 = ['e', 'f', 'g', 'h'] >>> slug2 = ['w', 'x', 'y', 'z'] >>> double_encrypt(src1, slug1, src2, slug2, 'A') 's' >>> double_encrypt(src1, slug1, src2, slug2, 'e') 'z' >>> double_encrypt(src1, slug1, src2, slug2, 'f') 'y' >>> double_encrypt(src1, slug1, src2, slug2, '$') '$' """ lower = char.lower() if lower in src1: idx = src1.index(lower) return slug1[idx] if lower in src2: idx = src2.index(lower) rev = len(src2) - idx - 1 return slug2[rev] return char