# Introduction to Computer Programming

## Problem Set 1

#### Instructions

• Your solution should be typed with plenty of spacing within and between problems and printed in black ink on otherwise blank paper that is stapled (assuming it is more than one page, which it should be). Make sure your name is on the first page.

### 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:
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
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()
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.