CS 151: Homework

Homeworks

Homeworks are short assignments intended to reinforce concepts from lectures that are not necessarily covered in the weekly projects. Homeworks will be due via email or paper before class Friday morning. No credit will be given for late homework, as we will discuss the solutions at the beginning of class on Friday.

HW 1: Assignments and Functions

1. Given the following Python expressions, write down the expected value of each.
```5 - 4 + 3
5 - 4 * 3
5 / 4 + 3
5 / (4 + 3)
5.0 / (4 + 3)
```
2. Given the following Python code, write down what Python would print.
```a = 4
b = 5
print a / b
print float(a) / b
print a * "blah "
```
3. Given the following Python code, what values are printed by the program? What does the global symbol table contain at the end of the code? To test it out, add the line print dir() to the end of the code.
```def afunc( B ):
B = B * 2
print B

A = 3
afunc( A )
print A
```
4. Given the following Python code, what does the function bfunc symbol table contain at the return statement? What does the global symbol table contain at the end of the code? You can add print dir() to the function (before the return) and to the end of the code to check your answer.
5. ```def bfunc( x, y, z):
x = y + z
q = x + y
return q

x = bfunc(1, 2, 3)
print x
```

HW 2: Functions, loops, and assignments

1. Write down what the following code prints to the terminal. Also, list all of the variables in the symbol table at the end of the code.
```    def cfunc(a, b):
if a > b:
return 1
elif a < b:
return -1
else:
return 0

def dfunc(a, b):
if a > b:
print a, 'is bigger than', b
elif a < b:
print b, 'is bigger than', a
else:
print a, 'is equal to', b

a = cfunc( 1, 5 )
b = cfunc( 'A', 'a' )
c = cfunc( 6, 4.0 )

d = dfunc( 5, 1 )
e = dfunc('a', 'A')
f = dfunc(4.0, 6)

print a, b, c
print d, e, f
```
2. Write down what the following code prints to the terminal.
```    lots = 'many'
for i in range(5):
lots = lots + ' many'
print lots
```
3. Write down what the following code prints to the terminal. Make sure you are clear about the order of operations in the assignment statement inside the for loop.
```    def doublething( a ):
return a * 2

q = 2
for i in range(3):
q = doublething( q )

print q
```

HW 3: Lists

The first two problems are based on the following statements.

```a = [1, 2, 3, 4]
b = [ ['a', 'b'], ['c', 'd'], 'what?' ]
c = [ 'four', 'score', 'and' ]
d = []
e = [a, b, c, d]

for i in a:
d.append( i )
```
1. What do each of the following print?
• print a[2]
• print b[1]
• print b[1][1]
• print c[2]
• print d
• print d[10]
• print b[2][4]
• print a[-1]
• print e[0]
• print e[0][2]
• print e[-1][-1]
• print e[1][-2][-1]
• print c[0][0:3]
• print a[:2]
• print c[1:]
• print d[:-1]
2. What does the following print?
```print a + c
```
3. Write the symbol tables that describe the state of the computer at the first mark, then show what changes in the last statement.
```x = [1, 2]
y = x
z = [ x[0], y[0] ]
# write down symbol tables here
y[0] = 10
# mark down what changes
```

HW 4: Loops and Lists

```a = [ 1, 2, 3 ]
b = [ 4, 5, 6 ]
c = a + b
d = c[0:3]
e = d
a[0] = 10
c[-1] = 20
e[2] = 30
```
1. For each of the following expressions, write down what Python would print after executing the code above.
1. print a
2. print b
3. print c
4. print d
5. print e
6. print c[2:4]
7. print c[:-1]
2. How many different list objects exist after executing the code above?
3. Given the following code, write out the global symbol table at mark 1 and mark 2, as well as any other referenced symbol tables and their data (i.e. lists). Then write out what the program prints.
```def squash( bug ):
end = bug.pop()
print 'the end of', end

insects = [ 'cockroach', 'bee', 'wasp', 'beetle']
yuck = insects[:1]
moreinsects = insects
# mark 1

squash(insects)
squash(moreinsects)
# mark 2
```
4. Given the following code, what would Python print?
```people = [ 'Washington', 'Adams', 'Jefferson', 'Madison', 'Monroe' ]
sentence = ''
for name in people[:-1]:
sentence = sentence + name + ', '
sentence = sentence + ' and ' + people[-1]
print sentence
```

HW 5: Lists and Lists

Consider the following code.

```def FinishSentence( q ):
q[0].append( 'lived' )
q[1].append( 'hobbit' )

def NextSentence( words ):
s = [ ['Not', 'a', 'nasty,'], [ 'dirty,', 'wet,', 'hole' ] ]
s.append( [ words[0][0], words[0][2], words[0][3] ] )
s.append( [ words[0].pop(), words[0].pop() ] )
s[-1].append(  words[0][1]  )
s.append( words.pop() )
s.append( words.pop() )

return s

a = [ ['In', 'a'], ['hole', 'in'], ['the', 'ground'] ]
b = [ ['there'], ['a'], ['.'] ]
c = [ ['filled', 'worms', 'with', 'the', 'of', 'ends'],
['oozy', 'smell,...'], ['and', 'an'] ]

FinishSentence(b)
q = NextSentence( c )

# mark 1
print b
print c
print q

f = ''
for l in a + b + q:
for s in l:
f += s + ' '

print f
```
1. Write out the values of b, c, and q at mark 1 in proper Python syntax.
2. What data type is the variable l in the for loop given a, b, and q?
3. What data type is the variable s in the for loop given the code?
4. Explain how the program constructs the contents of f.
5. Run the code above to double-check your answers and explain any discrepancies.

HW 6: Transformers

Consider the following code.

```def transformer( optimus ):
prime = []
for part in optimus:
if part == 't':
elif part == 'u':
prime.append( 'arms' )
elif part == 'k':
prime.append( 'legs' )
elif part == 'r':
prime.append( 'sword' )
elif part == 'c':
prime.append( 'body' )

return prime

prime = transformer( 'big truck' )
print prime

bumblebee = [ 'yellow', 'car' ]
bumblebee.append( [ 'black', 'trim' ] )
print bumblebee

bumblebee[-1][1] = 'highlights'
print bumblebee

group = [ prime, bumblebee ]
friends = group

hyp = range(60, 91, 10)
print hyp
for ratings in range(100, -1, -20):
print ratings

print dir() # prints out the symbol table for the badMovie() function

```

What does each print statement write to the terminal? Write out your answer, then test it using Python and explain any differences.

HW 7: Files and L-Systems

1. Consider the following L-system

```base: X
X -> YF+F
Y -> XF-F
```

After one iteration of replacement, the base string becomes YF+F. Show the resulting string after three iterations.

2. Given the following code:
```s = 'rule F F[+F][-F]'
words = s.split()
print words
```

What does the print statement write?

3. Given the following code:
```s = 'orc'
for i in range(4):
s = s.replace( 'orc', 'orc-orc' )
print s
```

What does the print statement write?

4. Given the following code:
```
s = '''It had a perfectly round door like a porthole, painted green,
with a shiny yellow brass knob in the exact middle.'''
q = s[ s.find('shiny'):s.find(' in') ]
q += '.'

print s.find( 'perfect' );
print s.find( 'orc' );
print s.find( 'a' );
print s[-7:-1]
print q
```

What do the print statements write?

HW 8: Classes and Symbol Tables

Python gives you the ability to see all of the identifiers in a symbol table using the dir function. If you write print dir() in your code, it prints out a list of all of the symbols in the current symbol table at that point in the program's execution. If you give the function an argument, like dir(list), then it prints out the symbol table associated with the contents of the variable (a class, in the case of list).

Download and look at the student.py file from class. After you answer the questions, run the file and look at the result. Except for the __init__ and __str__ entries, ignore the symbols that start with __.

1. Write down the global symbol table at the end of the file. There should be four items in it [Hint: remember loop variables].
2. Write down the symbol table for the Student class. There should be nine items in it.
3. Write down the symbol table for the __init__ function after executing the first three lines of code (# mark 1).
4. Write down the symbol table for the first Student in the students list (Mary at # mark 2).
5. When the code calls the sort method on the students list (# mark 3), it passes the expression Student.compare as the argument. What does the expression Student.compare mean? Explain it by referring to a symbol table.

HW 9: Dictionaries

Answer the questions below given the following Python code. Answer the questions without executing the code, then execute the code and correct and explain any differences.

```a = {}
b = { 'fall' : 'leaves', 'winter' : 'snow', 'spring' : 'mud',
'summer' : 'lakes' }
c = dict()
d = dict( [ ['sunny', 'afternoon'], [ 'blustery', 'day' ] ] )
e = dict( b.items() + d.items() )
a[ 'cold' ] = 'winter'
a[ 'frozen' ] = 'trundra'
d[ 'cool' ] = 'breeze'
```
1. Given the above code, what does each of the follow lines print?
```print a.keys()
print b.keys()
print c.keys()
print d.keys()
print e.keys()
```
2. Given the above code, what does each of the following lines print?
```print a['cold']
print d.get( 'sunny', 'morning' )
print d.get( 'overcast', 'morning' )
print c[ 'day' ]
print e[ 'blustery' ]
print e[ 'summer' ]
```
3. Consider the following code for a simple class.

```class Agent:
def __init__( self, things ):
self.mystuff = dict( things )

def clone(self):
return Agent( self.mystuff.items() )

q = Agent( [ [ 'jacket', 'fleece' ], ['tshirt', 'cotton'],
['backpack', 'nylon'] ] )
r = q.clone()
s = q.clone()
s.mystuff['jeans'] = 'cotton'
r.mystuff['boots'] = 'leather'
print q.mystuff.keys()
print s.mystuff.keys()
print r.mystuff.keys()
```
4. Show the symbol table for the class Agent.
5. Show the symbol table for the object referenced by q.
6. Show the symbol table for the __init__ method.
7. What do the last three lines print.
8. How many Agent objects exist at the end of the code? Explain.

HW 10: More Dictionaries and Classes

Consider the following code.

```def moveEntries( buckets, fromBucket, toBucket, position ):
buckets[ toBucket].insert( position, buckets[ fromBucket ].pop() )

pails = {}
pails[ 'red' ] = [ 'shovel', 'fork', 'hat' ]
pails[ 'blue' ] = [ 'gloves', 'twine', 'knife' ]
pails[ 'green' ] = [ 'big rock', 'little rock', 'stone' ]

moveEntries( pails, 'red', 'green', 0 )
moveEntries( pails, 'red', 'green', 2 )
print pails[ 'red' ]
print pails[ 'green' ]

moveEntries( pails, 'blue', 'red', 0 )
moveEntries( pails, 'blue', 'red', 0 )
print pails[ 'blue' ]
print pails[ 'red' ]

moveEntries( pails, 'green', 'blue', 1 )
moveEntries( pails, 'green', 'blue', 1 )
print pails[ 'blue' ]
print pails[ 'green' ]
```
1. Explain what the moveEntries function does.
2. Write down what the above code prints when excuted. Then run the code and explain any differences between your answers the what Python prints.
3. Consider the following code.

```class parent:
def __init__(self, value):
self.value = value

def change(self, value):
self.value = value

def get(self):
return self.value

class child(parent):
def __init__(self, v1, v2):
parent.__init__(self, v1)
self.data = v2

def changes( self, v1, v2):
self.change( v1 )
self.data = v2

def stuff(self):
return ( self.get(), self.data )

q = child( 1, 2 )
r = child( 3, 4 )
q.change( 6 )
r.changes( 5, 6 )
print q.stuff()
print r.stuff()
```
4. Write out all of the symbol tables at the end of the code. There should be five, including the global symbol table.
5. What does the code print?

HW 11: Recursion

Answer the questions below given the linked Python code. Try to answer the questions without executing the code, then execute the code and correct and explain any differences.

1. Write out the symbol table (name and type) for the linearSearch function the first time it is called at mark 1. To check your answer, you can always add the code

print locals()

to the start of the linearSearch function.

2. Explain whether the linearSearch function is guaranteed to reach a point in the recursion where it will terminate without calling itself.
3. Explain whether the binarySearch function is guranteed to reach a point in the recursion where it will terminate without calling itself.
4. At mark 2, how many times do you think the linearSearch will execute? How many times do you think the binarySearch will execute? Explain.
5. Run the code and compare the performance of the linear and binary search. Both functions print out how many times they have been called. Will both algorithms always give the right answer? What is the difference between the two?

HW 12: Last Practice

Answer the questions below given the linked Python code. Answer the questions without executing the code, then execute the code and correct and explain any differences.

1. What does cbb contain at mark 1?
2. What does cbb contain at mark 2?
3. What does cbb contain at mark 3?
4. What does the function print out at the end?