15-110: Principles of Computing

15-110 Spring 2011 Midterm 1
80 minutes

1. [10 pts; 1 pt each] True or False (circle one):

a. TRUE or FALSE: Any binary number that ends in a 1 must be odd.

b. TRUE or FALSE: Any binary number that contains exactly one 1 must be a power of 2.

c. TRUE or FALSE: ASCII is a code for converting text, images, sounds, and other media to integers.

d. TRUE or FALSE: Selection sort is one of the fastest sorting algorithms.

e. TRUE or FALSE: A Turing Test uses a human judge, but a Reverse Turing Test does not.

f. TRUE or FALSE: eTeRNA uses crowd-sourcing to sequence DNA.

g. TRUE or FALSE: Short-circuit evaluation refers to return statements that occur prior to the last line of a function.

h. TRUE or FALSE: We read about a case where modeling a law in a programming language and then translating it back into law led to the passage of a streamlined version of that law.

i. TRUE or FALSE: Ex-President Mubarak of Egypt promoted the use of social media which, ironically, helped lead to his downfall.

j. TRUE or FALSE: Top-down design helps identify appropriate helper functions for solving a given problem.

2. [10 pts; 2 pts each] Very Short Answers:
Answer each of the following with only one or two words or numbers. Longer answers will be incorrect.

a. Partway through sorting a list of random numbers, you notice that the first half of the list is sorted, and the second half of the list is also sorted. What sorting algorithm do you suppose is running?

b. A truth table for a boolean function has 32 rows in it. How many variables does the function take?

c. Name the Google tool that allows users to study how word frequencies evolve over time.

d. Some RGB values use one byte, or 8 bits, to represent each red, green, and blue component. What is the largest unsigned value that can be represented in 8 bits?

e. What property must a list have so that binary search will work properly on it?

3. [10 pts; 1 pt each] Indicate what each will print:

Statement:	Prints:
print "Spring Break is almost here!"[1:3]
print 5/2 + 5/2*1.0 + 5.0/2
print "32", 32
print 53, str(5)3
print len(str(float(2)))
print 1234%10, 1234/10
print len([[2,3,4],[5,6,7]])
print range(abs(min(1,max(-4,5),-3,2)))
print [52]2
print ((2 <= 3) or (6/0 > 8)) and ("a" <= "q")

4. [20 pts; 4 pts each] Indicate what each will print:

x = 5
if (x % 2 == 1):
    print "w", x
    x = 16
elif (x > 5):
    print "x", x
if (x % 2 == 1):
    print "y", x
print "z", x

x = 5
while (x%2 == 1):
print "in:", x
x += x/2
print "out:", x

# hint: prints 3 lines!

x = 2
for y in range(2,8):
   if (x < y):
        x += y
        print "in:", x, y
print "out:", x, y

# hint: prints 3 lines!

#4 continued. Indicate what each will print:

def f(s):
    result = 0
    for i in range(len(s)):
        if (s[i] == str(i)):
            print i
            result += 1
    return result

print f("A42 is 7 away from 3!")

def f(s, x, y):
    result = []
    for c in s:
        if ((ord(c) >= x) and
            (ord(c) <= y)):
            result += [c]
    return result

s = "Ace E. Ventura!"
x = ord(s[1])
print f(s, x, x+2)

5. [20 pts; 4 pts each] Reasoning about code
In these exercises, you should provide the arguments that cause the function to return the specified value. In most cases, there are many valid answers. You only need to provide one of them.

def f(a):
    rows = len(a)
    cols = len(a[0])
    if ((rows < 2) or
        (cols < 2)):
        return 0
    x = a[0][cols-1]
    y = a[rows-1][0]
    return x*y

# for what value of a
# will f(a) return 5?

def f(x, y):
    result = 0
    while (y > 0):
        d = y % 10
        y /= 10
        if (d == x):
            result += 1    return result

# for what value of
# x and y will f(x,y)
# return 5?

def f(a):
   result = []
   for i in range(len(a)):
      if (a[i] < i):
         result += [a[i]]
   return result

# for what value of a
# will f(a) return [2,3]?

#5 continued. Reasoning About Code
In these exercises, you should provide the arguments that cause the function to return the specified value. In most cases, there are many valid answers. You only need to provide one of them.

def f(s, t):
    result = ""
    b = True
    for i in range(min(len(s), len(t))):
        if (b == True):
            result += s[i]
        else:
            result += t[i]
        b = not b
    return result

# for what value of s and t
# will f(s,t) return "abc"?

def f(x):
    result = 0
    for z in range(x):
        if (str(z).find("3") >= 0):
            result += 1
    return result

# for what value of x
# will f(x) return 5?

6. [10 pts] Free Response: hasNoDigits
Write the function hasNoDigits(s), which takes a string s and returns True if s does not contain any digits and False otherwise. For example, hasNoDigits(“abc”) returns True but hasNoDigits(“a1”) returns False. You are not responsible for malformed input.

7. [20 pts] Free Response: hasMagicDiagonals
Write the function hasMagicDiagonals(a), which takes a 2d list and returns True if the list has magic diagonals, and False otherwise. We will say that a 2d list has magic diagonals (an invented term) if the list is square (same number of rows as columns) and if the sums of the values along each diagonal are equal to each other and that sum also equals the sum of the values in the first row. You are not responsible for malformed input.

Continued on next page

8. Bonus/Optional

a.       Bonus/Optional: [2.5 pts] What is a better name for this function?

def f(a):
    b = []
    for c in range(len(a[0])):
        b += [[]]
        for r in range(len(a)):
            b[c] += [a[r][c]]
    return b

b. Bonus/Optional: [2.5 pts] What will this print?

def f(x,y,z):
    if (x+y+z < 3):
        result = 1
        print "base:",result
    elif (y % (abs(x)+1) > z % (abs(y)+1)):
        result = f(y-1,x-1,z/2) + f(z-1,x/2,y-2)
        print "elif:", result
    else:
        result = 1 + f(x/2, y-3, z/4)
        print "else:", result
    return result

print f(7,5,5)