Sequences

Question 0

Fill out what python would display at each step if applicable.
Note:​ (keep in mind list slicing creates a brand new list, does not modify existing list)
i.

1 Mutation

Let’s imagine you order a mushroom and cheese pizza from La Val’s, and that they represent your order as a list:

1

>>> pizza = ['cheese', mushrooms']

A couple minutes later, you realize that you really want onions on the pizza. Based on what we know so far, La Val’s would have to build an entirely new list to add onions:

Q1: Acorn Finder

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain acorns. Define the function acorn_finder, which takes in a tree and returns True if the tree contains a node with the value ‘acorn’ and False otherwise.

Lecture Code

1
2
3
4
5
6
7
8
9

# Slicing

odds = [3, 5, 7, 9, 11]
list(range(1, 3))
[odds[i] for i in range(1, 3)]
odds[1:3]
odds[1:]
odds[:3]
odds[:]

Q1: List Indexing

For each of the following lists, what is the list indexing expression that evaluates to 7? For example, if x = [7], then the answer would be x[0]. You can use the interpreter or Python Tutor to experiment with your answers.

1
2
3
4
5
6
7
8
9
10
11

>>> x = [1, 3, [5, 7], 9]
x[2][1]

>>> x = [[7]]
x[0][0]

>>> x = [3, 2, 1, [9, 8, 7]]
x[3][2]

>>> x = [[3, [5, 7], 9]]
x[0][1][1]

Lecture Code

1
2
3
4
5
6
7

def fib_iter(n):
    i = 0
    curr, next = 0, 1
    while i < n:
        curr, next = next, curr + next
    	   i += 1
    return curr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Rational arithmetic

def add_rational(x, y):
    """The sum of rational numbers X and Y."""
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def mul_rational(x, y):
    """The product of rational numbers X and Y."""
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def rationals_are_equal(x, y):
    """True iff rational numbers X and Y are equal."""
    return numer(x) * denom(y) == numer(y) * denom(x)

def print_rational(x):
    """Print rational X."""
    print(numer(x), "/", denom(x))

Higher Order Functions

Question1

Write a make_skipper, which takes in a number n and outputs a function. When this function takes in a number x, it prints out all the numbers between 0 and x, skipping every nth number(meaning skip any value that is a multiple of n).

Assorted ADTs

A list is an ordered collection, or sequence.

1
2
3
4
5
6

interface List<E> {
  boolean add(E element); // add element to the end of the list
  void add(int index, E element); // adds element at the given index
  E get(int index); // returns element at the given index
  int size(); // the number of elements in the list
}

1 Assorted ADTs

A list is an ordered collection, or sequence.

1
2
3
4
5

List
  add(element); // add element to the end of the list
  add(index, element); // adds element at the given index
  get(index); // returns element at the given index
  size(); // the number of elements in the list

Stable Marriage

Consider the set of men $M={1,2,3}$ and the set of women $W={A,B,C}$ with the following preferences.

Run the male propose-and-reject algorithm on this example. How many days does it take and what is the resulting pairing?(Show your work.)