Exam Information

Exam Information

Material covered

The exam will focus on the material that we have discussed in class during weeks 1-5 of the course. These topics include:

Variables and arithmetic
Strings and lists – indexing and slicing, iterations with loop
Functions – parameters and return values
If/else logic
Recursion (processing numbers, strings, lists), and producing results as numbers, strings, or lists
List comprehensions
Iterative programming with definite loop (for) and indefinite loop (while), accumulator variables
Lists and 2d lists

Exam details

The exam will be held on Tuesday, October 15, 2019, from 3:35-5:05pm at CAS 522.
You may not use any electronic devices during the exam.
The exam will include questions similar to the ones posed in class.
In addition, there will be questions that ask you to write explain the output of a function or section of code, or to trace a function, similar to the problems from the homework.

Practice Problems

Given the string s = 'Columbus', evaluate the following:
1. s[0]
2. s[0:1]
3. s[1:]
4. s[-1]
5. s[3: :-1]
6. s[2: :2]
Given the list myList = [3, 2, -1, [4, 7], 5], evaluate the following:
1. myList[0]
2. myList[0:1]
3. myList[-1]
4. myList[3]
5. myList[:2]
6. myList[2: :2]
Evaluate the following:
1. 'a' in 'backache'
2. [1, 2, 3] + [[11, 13, 12][1]] + [22, 33, 44, 55][1:]
3. [3 for x in range(6)]
4. [2*y + 1 for y in [1, 3, 5, 7]]
5. [x for x in range(3, 10) if x % 2 == 0]
6. [len(w) for w in ['Go', 'Terriers']]
Write a function count_ones(s) that takes in a string s of '0's and '1's and returns the number of '1's in the input.
1. Use recursion.
2. Use a list comprehension.
3. Use a definite loop.
Write a function swap_bits(s) that takes in a string s of '0's and '1's and returns a string in which each bit in s has been swapped/replaced with the other bit. For example, swap_bits('101011') should return '010100'.
1. Use recursion.
2. Use a definite loop.
Write a function num_divisors(n) that returns the number of integers from 1 to n (inclusive) that divide n evenly. For example, num_divisors(42) should return 8, because 1, 2, 3, 6, 7, 14, 21, and 42 are all divisors of 42.
1. Use recursion.
2. Use a list comprehension.
3. Use a definite loop.
Use the above num_divisors(n) function in order to write a function most_divisors(lst) that takes in a list of integers lst and returns the integer from that list with the most divisors. For instance, most_divisors([2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]) should return 12.
Write a function count_transitions(s) that takes in a string s of '0's and '1's and returns the number of times there is a transition from a '0' to a '1' or vice-versa in that input string. For example, count_transitions('1110110000') should return 3.
1. Use recursion.
2. Use a definite loop.
Write a function longest_string(lst) that takes in a list of strings lst as input and returns the longest string from that list. For example, longest_string(['short', 'longer', 'sesquipedalian']) should return 'sesquipedalian'.
Write a function cycle(s, n) that takes in a string s of '0's and '1's and an integer n and returns the string in which s has shifted its last character to the initial position n times. For example, cycle('1110110000', 2) should return '0011101100'.

What is printed by the following working Python program?

def dog(x):
    print('in dog, x is', x)
    y = cat(x - 1) + cat(x + 2)
    print('in dog, y is', y)
    return y

def cat(y):
    print('in cat, y is', y)
    x = rat(y * 2) + 3
    print('in cat, x is', x)
    return x

def rat(x):
    print('in rat, x is', x)
    return 2 * x

y = dog(3)
print('at this level, y is', y)

What is printed by the following working Python program?

def mystery(x):
    print('x is', x)
    if x < 1:
        return 2
    else:
        p = 6 - mystery(x - 1)
        print('p is', p)
        return p

y = mystery(3)
print('y is', y)

Write a Python function years_needed that takes three inputs:
- principal, which is the initial amount of money deposited in an interest-bearing account
- rate, which is the annual interest rate in decimal form
- target, which is the final value that the investor wants to reach
The function should use a loop to determine the number of years of compounded annual interest that are needed for the investment to reach or exceed the specified target. Note: After each year, the new principal is computed as
```
principal = principal * (1 + rate)
```
Write a Python function find(ch, s) that returns the index of the first occurrence of a character ch in a string s, or −1 if the character is not found. You may assume that ch is a single character.
1. Use recursion.
2. Use a definite loop.
Write a Python function count_vowels(s) that counts and returns the number of vowels in a string.
1. Use recursion.
2. Use a list comprehension.
3. Use a definite loop.
Write a Python function stars(n) where n is a positive integer. It should print n lines of stars with 1 star on first line, 2 stars on second line, and so forth. For example, stars(4) should print
```
*
**
***
****
```
Use nested loops. You are not allowed to use the * operator (*). You should use print('*', end= '') to print a single asterisk at a time while remaining on the same line, and an empty print() to go down to the next line.
Write a function index_nearest(n, lst) that takes a number n and a list of numbers lst and returns the index of the element in lst whose value is closest to n. Use one or more loops.

What is printed by the following Python program?

def loopy(x, y):
    print('starting loopy:', x, y)
    while x < y:
        x += 1
        y -= 2
    print('after loop:', x, y)
    return x

x = 1
y = 8
y = loopy(x, y)
print('after first call:', x, y)
loopy(y, x)
print('after second call:', x, y)

Hint: Use two different tables – one for the global scope and one for loopy – to keep track of the values of the variables.

Draw one or more memory diagram (the text uses the term “box-and-arrow” diagram) to illustrate the execution of the following Python program:
```
a = [1, 2, 3, 4]
b = a
a[3] = 5
b[1] = 7
print('a is', a)
print('b is', b)
```
In addition, write a few sentences that refer to your diagram(s) and that explain the result of the program.

Draw memory diagrams that demonstrate why we get different results from the following two Python programs:

### Program 1 ###
def foo(a):
    a = 2 * a
    return

b = [1, 2, 3]
for i in range(len(b)):
    foo(b[i])

print('b is', b)

### Program 2 ###
def bar(lst, i):
    lst[i] = 2 * lst[i]
    return

b = [1, 2, 3]
for i in range(len(b)):
    bar(b, i)

print('b is', b)

In addition, write a few sentences that refer to your diagrams and that explain the difference in output.

What does the following code print?

a = [1, 2, 3, 4]
b = a
b[2] = 6
print('a =', a, 'b =', b)

Using a memory diagram and a couple of sentences, explain the result printed in problem number 1.

What is printed when you invoke prob3() below?

def eat(x):
    x[1] = 9
    x[3] = 11

def prob3():
    food = [4, 5, 6, 7]
    eat(food)
    print('food =', food)

Using a memory diagram and a couple of sentences, explain the result printed in problem number 3.
Write a function create_2d that takes as input two integers height and width, and that creates and returns a 2D list (i.e., a list of lists) with values that are the row number multiplied by the column number. For example:
```
>>> create_2d(3, 5)
[[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 4, 6, 8]]
```
Write a function add_one that takes an input grid that is a 2D list (a list of lists). Your function should add 1 to each element of grid, but it should not return anything. For example:
```
>>> my_grid = create_2d(3, 5)
>>> add_one(my_grid)
>>> my_grid
[[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 5, 7, 9]]
```