15-112 Spring 2013 Quiz 3

* 25 Minutes.
* No calculators, no notes, no books, no computers.
* Show your work, circle your answers.

1. Quick Answers.  Be very brief. [10 pts]

   1. What does ("a%%bc%de%6.1fg" % (123, 45.67)) evaluate to?

   2. What is a magic number?  In just a few words, give one reason why are they ill-advised.
       

2. Code Tracing [20 pts]

   Indicate what each will print:

   import string
   def f(x, s):
       while ((x < len(s)) and (s[x] < s[-1-x])):
           s = s[x:len(s):3]
           x += 1
           print x, s
   print f(0, "abcde"*3)
   
   def g(s):
       u = ""
       for i in xrange(len(s)):
           for k in xrange(i+1, len(s)):
               if (ord(s[k]) == i + ord(s[i])):
                   print i, k
                   u += s[i] + s[k]
       return u
   print g("abcbcde")

3. Reasoning Over Code [20 pts]

   Find arguments for the following functions that make them return True.

   import math
   def f(s):
       assert(type(s) == str)
       x0 = 0
       x1 = 100
       epsilon = 0.0001
       while (abs(x1 - x0) > epsilon):
           xmid = (x1 + x0)/2.0
           y = 10*xmid - 2*math.pi  # 3.14159265358...
           if (y > 0):
               x1 = xmid
           else:
               x0 = xmid
       t = "%0.2f" % ((x1 + x0)/2)
       return (s == t)
   
   
   def g(s):
       t = ""
       for i in xrange(5):
           t = (chr(ord('H')+i) * i) + t
       return (s == t)
   

4. Free Response [50 pts]
   islower
   Note:  For this problem, you may not use any string methods (the kind you call like s.foo()) though you can use string functions (the kind you call like foo(s)).  Write the function islower(s) that takes a string s and works the same as the method s.islower().
   
   hasBalancedParentheses
   Write the function hasBalancedParentheses, which takes a string and returns True if that code has balanced parentheses and False otherwise (ignoring all non-parentheses in the string).  We say that parentheses are balanced if each right parenthesis closes (matches) an open (unmatched) left parenthesis, and no left parentheses are left unclosed (unmatched) at the end of the text.  So, for example, "( ( ( ) ( ) ) ( ) )" is balanced, but "( ) )" is not balanced, and "( ) ) (" is also not balanced.
    

5. Bonus/Optional: [5 pts]

   Indicate what this will print:

   def f(f,x):
       def g(y):
           s = 0
           for x in xrange(y): s += f(x)
           return s
       s = 0
       for y in xrange(x): s += g(y)
       return s
   
   def g(y):
       s = 0
       for x in xrange(y): s += x
       return s
   
   print f(g,7)