Introduction to Computer Programming

Problem Set 1

Attempt seriously by Thursday, December 7, before lecture

Submit hard copy on Monday, December 11, at start of class


Instructions


The problems themselves

  1. Suppose the following lines of code have been executed in order:

    s = {3, 4}
    t = {4, 3}
    d = {'a': 1}
    e = d
    e['b'] = 2

    For each of the following expressions, indicate to what the expression evaluates and briefly, why that result might be noteworthy; or, if an error would result, explain, briefly, its cause:

    s == t
    s is t
    e is d
    s[0] == t[1]
    e['c'] == 0
    d['b'] == len(e)

  2. Consider this function:

    def rt(n):
        if n == 0:
            return True
        else:
            return not rt(n-1)

    In a clear and concise sentence, what does rt(n) return in regards to n? Can you think of a more efficient way to solve the same problem? Explain.


  3. Consider these three functions that manipulate "grids" (lists of lists where each "row" is of the same length):

    def a_grid(rows, cols):
        g = []
        for _ in range(rows):
            row = []
            for _ in range(cols):
                row.append(random.randrange(10))
            g.append(row)
        return g
    
    def b_grid(g):
        nothing = True
        y = 0
        while nothing and y < len(g):
            x = 0
            while nothing and x < len(g[y]):
                nothing = (g[y][x] == 0)
                x += 1
            y += 1
        return nothing
    
    def c_grid(g):
        for row in g:
            s = ''
            for x in row:
                s = s + ' ' + str(x)
            print(s)
    1. Explain in a clear and concise sentence what each function does.

      Now consider this function:

      def d_grid(g):
          for y in range(len(g)):
              for x in range(len(g[y])):
                  if y + 1 < len(g) and x + 1 < len(g[y]):
                      z = g[y+1][x+1]
                  else:
                      z = 0
                  g[y][x] = z

      Assume we have defined grid so that c_grid(grid) outputs:

      3 4 9 6 2
      5 1 1 8 1
      1 0 2 2 8
    2. Suppose d_grid(grid) is executed. Now what will c_grid(grid) output?

      Finally, consider this code:

      def e_grid(g):
          n = 0
          while not b_grid(g):
              d_grid(g)
              n += 1
          return n
    3. What value would you expect e_grid(a_grid(7, 4)) to return? Explain your reasoning.


  4. Consider this function:

    def a_mys(a):
        b = {}
        for c in a:
            d = c[0]
            if d in b:
               b[d].add(c)
            else:
               b[d] = {c}
        return b
    1. What types of data do variables a, b, c and d represent? How did you infer that?

    2. Give an expression that if passed as an argument to a_mys might cause it to return:

      {'t': {'time', 'to'}, 'b': {'be'}, 'o': {'or', 'on'}, 'n': {'not'}}
    3. Why in the previous exercise did I use the word "might"?

      Now consider this function:

      def b_mys(e):
          f = 0
          for g, h in e.items():
              if len(h) > f:
                  f = len(h)
                  i = g
          return i
    4. What types of data do variables e, f, g, h and i represent? How did you infer that?

    5. Is b_mys side-effecting, fruitful, neither or both? Briefly explain.

    6. What assumptions about its argument should be made to assure that b_mys does not result in an error?

    7. If words is a list of the words in the sentence "Now the time is near for the noisy cs students to celebrate the new year" (perhaps generated by using split), to what does b_mys(a_mys(words) evaluate?

    8. In a clear and concise sentence, what does b_mys return?


  5. Consider this class:

    class C:
        def __init__(self):
            self._c = 0
            self._n = 1
        def read(self):
            return self._c
        def bizz(self):
            t = self._n
            self._n += self._c
            self._c = t

    and this function that makes use of it:

    def f(n):
        c = C()
        for _ in range(n):
            c.bizz()
        return c.read()
    1. In a clear and concise sentence, explain what f(n) returns in terms of n.

    2. Is f's approach efficient? Explain.

      Now consider this function:

      def g(m):
          i = 0
          while f(i) < m:
              i += 1
          return (f(i) == m)
    3. In a clear and concise sentence, explain what g(m) returns in terms of m.

    4. Is g's approach efficient? Explain.

      Now consider this class:

      class D(C):
          def blitz(self, k):
              for _ in range(k):
                  self.bizz()
          def buzz(self):
              t = self._c
              self._c = self._n - self._c
              self._n = t
              return t
    5. List the regular methods available to objects of class D. (By regular, we mean those not named with leading underscore symbols.)

      Finally, consider this function:

      def h(m):
          a = []
          d = D()
          d.blitz(m)
          while d.read() > 0:   # <--- HERE
              a.append(d.buzz())
          return a
    6. Show the values of d._c and d._n each time the test on the line marked with the HERE comment is executed when evaluating h(6).

    7. In a clear and concise sentence, explain what h(m) returns.


  6. Consider these four functions:

    def what():
        n = 0
        while True:
            print(n)
            time.sleep(1)
            n += 1
    
    def gives():
        global g_n
        print(g_n)
        g_n += 1
        turtle.ontimer(gives, 1000)
    
    def now():
        global g_n
        g_n = 0
        gives()
    
    def really(n):
        print(n)
        time.sleep(1)
        really(n+1)

    Compare and contrast these expressions what(), now(), and really(0). You should assume that the modules time and turtle and have been imported.