Final: Questions

XF.1.

[6 pts] If nums is [11, 2, 7, 5, 3], what is the value of each of the following expressions?

a. nums[1] + nums[-1]

b. sum(nums[1:4])

c. nums[min(nums)]

XF.2.

[12 pts] The below program reads 50 integers from the user. Modify the program so that after reading the fiftieth integer, it displays the sum of all those integers that are less than 100. For example, if the user enters 200, 59, 99, 105, and 10, then enters 150 forty-five times, the output should be 168 (from 59 + 99 + 10).

for index in range(50):

    num = int(input())

XF.3.

[6 pts] Write a regular expression for all sequences of a's and b's that all a's precede all b's, including at least one of each. Examples include ab, aaab, and aaabb, but not aabbabb or aaaaa.

XF.4.

[8 pts] What single value for template would result in the following strings being produced? (Don't include the quotes.)

`template.format(212, 100)`	→	“`100.0 C = 212.0 F`”
`template.format(98.6, 37)`	→	“ `37.0 C = 98.6 F`”

XF.5.

[8 pts] What does the below program display? def go(x): y = step(x) z = step(y) print('{0} {1} {2}'.format(x, y, z)) def step(a): a = a + 2 return a + 3 go(5)

XF.6.

[14 pts] Write a function input_between, which should take two parameters, both numbers, and return a number typed by the user that is above the first parameter and below the second. It will continue to request a number from the user until the required number is given. (A number exactly matching the first number or the second will be accepted. You may assume that first number is below the second and that the user only types valid numbers.)

For example, suppose we have the following program using your function.

n = input_between(0, 40)

m = 1

for i in range(2, n + 1):

    m *= i

print('Factorial is ' + str(m))

The below shows one possible run of the program, with boldface indicating what the user types.

Number?
-5
Too low
Number?
50
Too high
Number?
42
Too high
Number?
4
Factorial is 24

XF.7.

[8 pts] Draw a recursion tree representing the recursive calls made when computing the value of f(60) using the following function. def f(n): if n < 10: return n else: a = f(n // 2) b = f(n // 3) return a - b

XF.8.

[14 pts] Suppose the file pops.txt is a tab-separated values file, where each line contains three values: a city name, a state name, the city's current population. Here are five example lines from the file.

Chicago        Illinois        9899902
Los Angeles    California      18238998
New York       New York        23362099
San Francisco  California      8370967
Washington     DC              9331587

Write a program that displays the name of each state represented in the file followed by the number of cities in that state with a current population exceeding 1,000,000. For example, if the file contained only the five lines listed above, the output of the program would be as illustrated below. (You don't need to worry about the order of the lines.)

Illinois 1 California 2 New York 1 DC 1

infile = open('pops.txt')

for line in infile:

    data = line.rstrip().split('\t')

XF.9.

[8 pts] In your own words, describe how merge sort works. What is the base case?

XF.10.

[8 pts] Define the function of a router in the Internet.

XF.11.

class TruncatedLog:

    def __init__(self, max_lines):

        self.max_lines = max_lines

        self.lines_done = 0



    def show(self, line):

        if self.lines_done < self.max_lines:

            self.lines_done += 1

            print(line)

XF.12.

[10 pts] Suppose a game player has constructed the following game tree.

In this tree, high numbers represent good boards for X, and it is currently X's move. (As you can see, X has three possible moves from which to choose, labeled A, B, and C.)

a. Fill in all empty circles with the values assigned them according to the minimax evaluation algorithm.

b. Which move will X choose?

XF.13.

[12 pts] Recall the two classes we defined for dealing with linked lists.

class Node: def __init__(self, value, next): self.data = value self.next = next class LinkedList: def __init__(self): self.head = None

The below function attempts to delete every node in a linked list that contains a negative number. There are several things wrong with it. Identify two distinct problems, and explain how to repair the function to address each issue.

def delete_negatives(list_obj):

    cur = list_obj.head

    while cur.next is not None:

        if cur.next < 0:

            cur.next = cur.next.next

        cur = cur.next

XF.14.

[14 pts] Using the Node and LinkedList classes defined previously, write a function count_long that takes a parameter referencing a LinkedList object whose values are strings and returns the number of string with more than five letters.

def count_long(word_list):

XF.15.

[8 pts] Modify the below program so that, should the filename typed by the user correspond to something that cannot be opened, the program displays “file not opened” and exits (without attempting to read the file). Recall that open raises an IOError exception if the named file is not accessible.

filename = input('Filename:')

infile = open(filename)

text = infile.read()

print('# characters: ' + str(len(text)))

Final: Solutions

XF.1.

a. 5

b. 14

c. 7

XF.2.

total = 0

for index in range(50):

    num = int(input())

    if num < 100:

        total += num

print(total)

XF.3.

a+b+

XF.4.

“{1:5.1f} C = {0:5.1f} F” (without the quotes)

XF.5.

5 10 15

XF.6.

def input_between(lo, hi):

    while True:

        print('Number?')

        n = int(input())

        if n < lo:

            print('Too low')

        elif n > hi:

            print('Too high')

        else:

            return n

XF.7.

XF.8.

states = {}

infile = open('pops.txt')

for line in infile:

    data = line.rstrip().split('\t')

    if int(data[2]) > 1000000:

        states[data[1]] = states.get(data[1], 0) + 1

for state in states:

    print('{0} {1}'.format(state, states[state]))

XF.9.

The base case is when the array has one element; in this case, nothing happens.

When there is more than one element, merge sort consists of three major steps. First, we split the array into two halves. Then we sort each half through recursively applying the merge sort algorithm to each. And finally, we merge the two halves together by successively “removing” the lesser of the two halves' first elements and placing the removed item into the array holding our result.

XF.10.

A router is a computing device that is attached to two or more separate networks. Any time it receives a message, it forwards the message to the appropriate computer on the other network as necessary.

XF.11.

XF.12.

a.
b.	`C`

XF.13.

In “if cur.next < 0”, cur.next is a reference to a Node object, not a number that can be compared to 0. To get the number within the node, we would need “if cur.next.data < 0”.
If the list is empty (head is None), then this function would end up setting cur to None in the first line and then the next line would try to retrieve the next attribute of None, which would lead to an exception. The solution would to add an if statement before the while loop to test for this: “if cur is None: return”.
If the list happens to start with a negative number, that will never be observed by the function, and the node would not be removed. To repair this, we could add a while loop at the beginning of the function (we need a while loop because there could be multiple negative numbers to be removed at the list's beginning):
while list_obj.head is not None and list_obj.head.data < 0: list_obj.head = list_obj.head.next
If the list has multiple negative numbers in a row (after the first node), then only every other negative number will be deleted: When cur is the node before the first of the sequence, the loop removes the first negative node and then steps cur forward to the next node (the second negative node), then the next iteration would delete the third negative node and step cur forward to the next node (the fourth negative node), and so on. The solution is to change cur only if we're not deleting the node after cur:
while cur.next is not None: if cur.next.data < 0: cur.next = cur.next.next else: cur = cur.next list_obj.head = list_obj.head.next

XF.14.

def count_long(word_list):

    count = 0

    cur = word_list.head

    while cur is not None:

        if len(cur.data) > 5:

            count += 1

        cur = cur.next

    return count

XF.15.

filename = input('Filename:')

try:

    infile = open(filename)

    text = infile.read()

    print('# characters: ' + str(len(text)))

except IOError:

    print('file not opened')