Introduction to Computer Programming

Problem Set 0

Attempt seriously by Thursday, October 19, before lecture

Submit hard copy on Monday, October 23, at start of class


Instructions


The problems themselves

  1. For each of the following expressions, indicate to what the expression evaluates and explain, briefly, why that result might be surprising to someone first learning to program.

    '35' == 35
    
    'Walter' < 'jesse'
    
    'ABC'[2] == 'B'
    
    37 // 2 == 18.5
    
    'q' == chr(32 + ord('Q'))
  2. When implementing a REPL, does it make more sense to use a definite or an indefinite loop? Explain.

  3. The following function is intended to return the number of occurrences of character c in the string s:

    def count(s, c):
        counter = 0
        i = 0
        while i < len(s):
            if s[i] == c:
                counter += 1
        return counter

    However, it has a bug. Explain the bug. What does this example indicate about an important difference between definite and indefinite loops?

  4. Express 153 in binary. Show your work.

  5. Express the binary number 11001001 in base 10. Show your work.


  6. Consider this function:

    def multiway(s):
        x = 1
        if len(s) > 2 and (s[0] < s[1] and s[1] < s[2]):   # line A
            x += 2
        elif len(s) > 1 and s[0] > s[1]:                   # line B
            x += 4
        elif len(s) < 2 or s[0] == s[1]:                   # line C
            x += 8
        else:
            x += 16                                        # line D
        x *= 2                                             # line E
        return x
    1. Evaluate each of the following expressions (that is show what value the expression would return if evaluated in a Python program) and indicate which of the lines (A, B, C, D, E) would be executed on the way toward returning the final result.

      >>> multiway('')
      
      >>> multiway('ABC')
      
      >>> multiway('zygote')
      
      >>> multiway('Toy')
      
      >>> multiway('llama')
    2. What kinds of input strings (in terms of length) cause multiway to return 34? Give a specific example of a such a string.

    3. Suppose line C was changed to read:

      elif s[0] == s[1] or len(s) < 2:

      Would that change the result of evaluating multiway('I')? If so, how? What, if anything, does that illustrate about the or operator?


  7. Consider the following function:

    def alpha(m):
        t = 0
        j = 1
        for _ in range(m):   # line 4
            t = t + (j * j)
            j += 1
        return t
    1. Suppose the expression alpha(3) is evaluated. Show the values of j and t each time line 4 is executed.

    2. In a clear and concise sentence, explain what alpha computes.


  8. Consider the following function

    def beta(a, b):
        c = ''
        for d in range(b, len(a)):
            pass                    # line 4
            c += a[d]
        return c
    1. What types of data do variables a, b, c and d represent? How did you infer that?

    2. Suppose the expression beta('thread', 2) is evaluated. Show the values of c and d each time line 4 is executed.

    3. In a clear and concise sentence, explain what beta computes.

    4. Why might this function be less useful in Python than in other programming languages?


  9. Consider this list of 15 cities:

    cities = ['Bangkok', 'Boston', 'Cairo', 'Frankfurt', 'Havana',
              'Lagos', 'Lima', 'London', 'Manila', 'Monrovia',
              'Paris', 'Quito', 'Taipei', 'Tashkent', 'Zurich']
    1. Suppose we look for 'Lagos' in cities using binary search. Show the sequence of strings that must considered before determining that 'Lagos' is on the list.

    2. Suppose we look for 'Yonkers' in the list using binary search. Show the sequence of cities that must be considered before determining that 'Yonkers' is not on the list.

    3. Suppose that the number of cities on the list is expanded to 1000 (and the alphabetical order of the list is maintained). Roughly how many different cities would you expect to consider to determine that 'Zurich' is on that list? Explain your reasoning and what that indicates about the difference between binary search and linear search.


  10. Consider the following Python code:

    name = 'Mike'
    ns = [2, 3, 7, 11, 13]
    
    def gamma(xs):
        n = len(xs)
        if n > 0:
            t = xs[0]
            for i in range(n - 1):
                pass               # HERE
                xs[i] = xs[i+1]
            xs[n-1] = t
    
    def delta(xs, n):
        for _ in range(n):
            gamma(xs)
    1. Suppose the expression gamma(ns) is evaluated. Show the values of i and xs each time the line marked with the HERE comment is evaluated.

    2. In a clear and concise sentence what does gamma achieve?

    3. What happens if gamma(name) is evaluated? What does say about the difference between the kinds of data that name and ns represent?

    4. How does the function delta make use of functional abstraction?


  11. Write a paragraph response (minimum of 50 words, maximum of 200) to exactly one the following two prompts:

    1. Arghhh! Describe what you have found most frustrating about writing Python programs.

    2. Eureka! Describe what you have found most satisfying about writing Python programs.