A document from MCS 275 Spring 2022, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2022 Homework 2 Solutions

  • Course Instructor: David Dumas
  • Solutions prepared by: Johnny Joyce

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 25 January 2022.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Resources you may consult

The course materials you may refer to for this homework are:

Point distribution

This homework assignment has 2 problems, numbered 2 and 3. The grading breakdown is:

Points Item
2 Autograder
4 Problem 2
4 Problem 3
10 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

Problem 2: Local extremum count

An element of a list is a local extremum if one of these conditions holds:

  • The element is greater than or equal to its neighboring elements (i.e. it is a local maximum)
  • The element is less than or equal to its neighboring elements (i.e. it is a local minimum)

Note an element can be both a local maximum and local minimum!

In a file hwk2prob2.py, write a function LEC(L) that takes a list L whose elements are floats or integers and returns the number of local extrema in the list.

Suggested strategy: Test each element of the list to see whether it satisfies one of the conditions above, keeping a running count to return at the end.

Some cases to think about / test:

  • The first and last elements of a list have only one neighbor, so they are always either local minima or local maxima.
  • If all elements of the list are equal (e.g. L = [275,275,275,275,275]), then every element of the list is both a local maximum and a local minimum, and so the return value of LEC would be the length of the list. (Don't check for this separately; it should be a consequence
  • If L has 0 or 1 elements, then there are no neighbors so the definition breaks down. In these cases, just return len(L).

Sample return values for certain inputs are shown below.

Solution

In [13]:
def LEC(L):
    '''Given a list L, returns number of local extrema in list'''
    
    extremum_count = 0 # Counter for number of extrema found so far
    
    for index, value in enumerate(L):
    
        if index == 0: # If we are looking at the first value
            extremum_count += 1 # First value must be extremum (always >= or <= than its neighbor)
                
        elif index == len(L) - 1: # If we are looking at the last value
            extremum_count += 1 # Last value must be extremum (always >= or <= than its neighbor)
        
        # If we are not looking at first or last value
        else:
            
            # If value is local maximum
            if L[index - 1] <= value and L[index + 1] <= value:
                extremum_count += 1
                
            # If value is local minimum
            elif L[index - 1] >= value and L[index + 1] >= value:
                extremum_count += 1
                
    return extremum_count
In [14]:
LEC([])
Out[14]:
0
In [15]:
LEC([275])
Out[15]:
1
In [16]:
LEC([1,2,3,4])
Out[16]:
2
In [17]:
LEC([1,2,3,4,5,6,7,8,9,10])
Out[17]:
2
In [18]:
LEC([3,1,4,1,5,9,2,6,5,3,5,8]) # length is 12, but indices 4, 8, and 10 are not local extrema
Out[18]:
9
In [19]:
LEC([5,5,5,5,5,5,5]) # length 7, all equal, hence all extrema
Out[19]:
7
In [20]:
LEC([1,1,2,2]) # all are extrema: [local max and min, local min, local max, local max and min]
Out[20]:
4

Problem 3: Roll until break even

Imagine you have a standard cubical die whose six sides are labeled with these numbers:

-3, -2, -1, 1, 2,3

Using such a die you can play the following game: You start with a score of 0 points. Each time you roll the die, you add the number that shows up to your score. If your score ever returns to 0 points again, you win.

In a file hwk2prob3.py, write a program that plays this game 10 times, each time printing how many rolls it took to win. The output should look like this:

Game ended after 219 rolls
Game ended after 2 rolls
Game ended after 2 rolls
Game ended after 6 rolls
Game ended after 4 rolls
Game ended after 4 rolls
Game ended after 1202 rolls
Game ended after 2 rolls
Game ended after 37 rolls
Game ended after 4 rolls

Solution

In [12]:
import random

def roll_die():
    '''Randomly returns one of [-3, -2, -1, 1, 2, 3] with equal probability'''
    return random.choice([-3, -2, -1, 1, 2, 3])


def play_game():
    '''Plays the game where we roll dice until returning to 0. Returns number of times dice were rolled'''
    
    score = 0

    # Roll die once before starting the loop so we don't have a score of zero
    score += roll_die()

    times_rolled = 1 # Start at 1 since we just rolled the die

    while score != 0: # Keep rolling until we get back to 0
        score += roll_die()
        times_rolled += 1
        
    return times_rolled
        

for i in range(10): # Play 10 games and print the results
    result = play_game()
    print("Game ended after {} rolls".format(result))
Game ended after 25496 rolls
Game ended after 1598 rolls
Game ended after 7 rolls
Game ended after 3 rolls
Game ended after 61 rolls
Game ended after 53 rolls
Game ended after 5 rolls
Game ended after 44 rolls
Game ended after 11 rolls
Game ended after 2 rolls

Revision history

  • 2022-01-21 Initial publication