# Introduction to Computer Programming

## Problem Set 0

#### 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. 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.