Due at 11:59pm on 06/23/2016.

Starter Files

Download lab01.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

  • Questions 1, 2, and 3 must be completed in order to receive credit for the lab.
  • Questions 4, 5, and 6 (What Would Python Display?) are optional. It is recommended that you work on these should you finish the required section early, or if you are struggling with the required questions.
  • Questions 7, 8, 9, 10, and 11 (Coding) are optional. It is recommended that you complete these problems on your own time.

Logistics

Using Your Class Account

Follow the directions on Piazza to register for an instructional account. Your username will be of the form cs61a-xx. These accounts allow you to use instructional machines in the CS department, which can be useful if you do not have regular access to a computer. You will also use your instructional account to receive and review your grades.

This UNIX Tutorial explains the basics of how to use the Terminal.

You can refer to Lab 0 for help logging into your class account.

Using Python

When running a Python file, you can use options on the command line to inspect your code further. Here are a few that will come in handy. If you want to learn more about other Python command-line options, take a look at the documentation.

  • Using no command-line options will run the code in the file you provide and return you to the command line.

    python3 lab01.py
  • -i: The -i option runs your Python script, then opens an interactive session. To exit, type exit() into the interpreter prompt. You can also use the keyboard shortcut Ctrl-D on Linux/Mac machines or Ctrl-Z Enter on Windows.

    If you edit the Python file while running it interactively, you will need to exit and restart the interpreter in order for those changes to take effect.

    python3 -i lab01.py
  • -m doctest: Runs doctests in a particular file. Doctests are surrounded by triple quotes (""") within functions. Each test consists of >>> followed by some Python code and the expected output.

    python3 -m doctest lab01.py

Using OK

In 61A, we use a program called OK for autograding labs, homeworks, and projects. You should have OK in the starter files downloaded at the start of this lab. For more information on using OK commands, learn more here. To use OK to run doctests for a specified function, run the following command:

python3 ok -q <specified function>

By default, only tests that did not pass will show up. You can use the -v option to show all tests, including tests you have passed:

python3 ok -v

Finally, when you have finished all the questions in lab01.py, you must submit the assignment using the --submit option:

python3 ok --submit

Helpful Hints

OK has a new feature for the "What would Python display?" questions. As you go through the question's prompts OK may give you a hint based on your wrong answers. Our hope is these hints will help remind you of something important or push you in the right direction to getting the correct answer. For example:

Foo > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> not False or False
? False

-- Helpful Hint --
What about the | not |?
------------------

-- Not quite. Try again! --

? 

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

Division

Let's compare the different division-related operators in Python:

True Division: /
(decimal division)
Floor Division: //
(integer division)
Modulo: %
(remainder)
>>> 1 / 5
0.2

>>> 25 / 4
6.25

>>> 5 / 0
ZeroDivisionError
>>> 1 // 5
0

>>> 25 // 4
6

>>> 5 // 0
ZeroDivisionError
>>> 1 % 5
1

>>> 25 % 4
1

>>> 5 % 0
ZeroDivisionError

Notice that Python outputs ZeroDivisionError for certain cases. We will go over this later in this lab under Error Messages.

One useful technique involving the % operator is to check whether a number x is divisible by another number y:

x % y == 0

For example, in order to check if x is an even number:

x % 2 == 0

Boolean Operators

Python supports three boolean operators: and, or, and not:

>>> a = 4
>>> a < 2 and a > 0
False
>>> a < 2 or a > 0
True
>>> not (a > 0)
False
  • and evaluates to True only if both operands evaluate to True. If at least one operand is False, then and evaluates to False.
  • or evaluates to True if at least one operand evaluates to True. If all operands are False, then or evaluates to False.
  • not evaluates to True if its operand evaluates to False. It evaluates to False if its operand evalutes to True.

What do you think the following expression evaluates to? Try it out in the Python interpreter.

>>> True and not False or not True and False

It is difficult to read complex expressions, like the one above, and understand how a program will behave. Using parentheses can make your code easier to understand. Just so you know, Python interprets that expression in the following way:

>>> (True and (not False)) or ((not True) and False)

This is because boolean operators, like arithmetic operators, have an order of operation:

  • not has the highest priority
  • and
  • or has the lowest priority

It turns out and and or work on more than just booleans (True, False). Python values such as 0, None, '' (the empty string), and [] (the empty list) are considered false values. All other values are considered true values.

Short Circuiting

What do you think will happen if we type the following into Python?

1 / 0

Try it out in Python! You should see a ZeroDivisionError. But what about this expression?

True or 1 / 0

It evaluates to True because Python's and and or operators short-circuit. That is, they don't necessarily evaluate every operand.

Operator Evaluates from left to right up to: Example
AND The first false value False and 1 / 0 evaluates to False
OR The first true value True or 1 / 0 evaluates to True

If and and or do not short-circuit, they just return the last value. This means that and and or don't always return booleans when using values other than True and False.

return and print

Most functions that you define will contain a return statement. The return statement will give the result of some computation back to the caller of the function and exit the function. For example, the function square below takes in a number x and returns its square.

def square(x):
    """
    >>> square(4)
    16
    """
    return x * x

When Python executes a return statement, the function terminates immediately. If Python reaches the end of the function body without executing a return statement, it will automatically return None.

In contrast, the print function is used to display values in the Terminal. This can lead to some confusion between print and return because calling a function in the Python interpreter will print out the function's return value.

However, unlike a return statement, when Python evaluates a print expression, the function does not terminate immediately.

def what_prints():
    print('Hello World!')
    return 'Exiting this function.'
    print('61A is awesome!')

>>> what_prints()
Hello World!
'Exiting this function.'

If Statements

You can review the syntax of if statements in Section 1.5.4 of Composing Programs.

Tip: We sometimes see code that looks like this:

if x > 3:
    return True
else:
    return False

This can be written more concisely as return x > 3. If your code looks like the code above, see if you can rewrite it more clearly!

While Loops

You can review the syntax of while loops in Section 1.5.5 of Composing Programs.

Error Messages

By now, you've probably seen a couple of error messages. They might look intimidating, but error messages are very helpful for debugging code. The following are some common types of errors:

Error Types Descriptions
SyntaxError Contained improper syntax (e.g. missing a colon after an if statement or forgetting to close parentheses/quotes)
IndentationError Contained improper indentation (e.g. inconsistent indentation of a function body)
TypeError Attempted operation on incompatible types (e.g. trying to add a function and a number) or called function with the wrong number of arguments
ZeroDivisionError Attempted division by zero

Using these descriptions of error messages, you should be able to get a better idea of what went wrong with your code. If you run into error messages, try to identify the problem before asking for help. You can often Google unfamiliar error messages to see if others have made similar mistakes to help you debug.

For example:

>>> square(3, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: square() takes 1 positional argument but 2 were given

Note:

  • The last line of an error message tells us the type of the error. In the example above, we have a TypeError.
  • The error message tells us what we did wrong — we gave square 2 arguments when it can only take in 1 argument. In general, the last line is the most helpful.
  • The second to last line of the error message tells us on which line the error occurred. This helps us track down the error. In the example above, TypeError occurred at line 1.

Required Questions

What Would Python Display?

Question 1: WWPD: Veritasiness

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q short_circuiting -u
>>> True and 13
______
13
>>> False or 0
______
0
>>> not 10
______
False
>>> not None
______
True
>>> True and 1 / 0 and False
______
Error (ZeroDivisionError)
>>> True or 1 / 0 or False
______
True
>>> True and 0
______
0
>>> False or 1
______
1
>>> 1 and 3 and 6 and 10 and 15
______
15
>>> 0 or False or 2 or 1 / 0
______
2
>>> not 0
______
True
>>> (1 + 1) and 1
______
1
>>> 1/0 or True
______
Error
>>> '' or None and 1/0
______
Nothing
>>> (True or False) and 0
______
0
>>> -12 and (1 - 1)
______
0

Question 2: WWPD: Loops

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q loops -u
>>> n = 3
>>> while n >= 0:
...     n -= 1
...     print(n)
______
2 1 0 -1

Hint: Make sure your while loop conditions eventually evaluate to a false value, or they'll never stop! Typing Ctrl-C will stop infinite loops in the interpreter.

>>> n = 4
>>> while n > 0:
...     n += 1
...     print(n)
______
5 6 7 # continues forever
>>> def go(n):
...     if n % 2 != 0:
...         print(n / 2)
...         return
...     while n > 0:
...         print(n)
...         n = n // 2
>>> go(4)
______
4 2 1
>>> go(5)
______
2.5
>>> zero = 2
>>> while zero != 0:
...    zero = zero // 2
...    print(zero)
______
1 0
>>> positive = 28
>>> while positive:
...    print("positive?")
...    positive -= 3
______
Infinite Loop
>>> positive = -9
>>> negative = -12
>>> while negative:
...    if positive:
...        print(negative)
...    positive += 3
...    negative += 3
______
-12 -9 -6

Coding Practice

Question 3: Repeated

Implement the repeated function, which takes a one-argument function f, a positive integer n, and a parameter x. It returns the result of composing, or applying, f n times on x, i.e., f(f(...f(x)...)).

def repeated(f, n, x):
    """Returns the result of composing f n times on x.

    >>> def square(x):
    ...     return x * x
    ...
    >>> repeated(square, 2, 3)  # square(square(3)), or 3 ** 4
    81
    >>> repeated(square, 1, 4)  # square(4)
    16
    >>> repeated(square, 6, 2)  # big number
    18446744073709551616
    >>> def opposite(b):
    ...     return not b
    ...
    >>> repeated(opposite, 4, True)
    True
    >>> repeated(opposite, 5, True)
    False
    >>> repeated(opposite, 631, 1)
    False
    >>> repeated(opposite, 3, 0)
    True
    """
"*** YOUR CODE HERE ***"
result = x while n > 0: result = f(result) n -= 1 return result

Use OK to test your code:

python3 ok -q repeated

Optional Questions

What Would Python Display?

Question 4: WWPD: Truthiness

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q truthiness -u
>>> 0 or True
______
True
>>> not '' or not 0 and False
______
True
>>> 13 and False
______
False
>>> False or 1
______
1
>>> '' or 1 and 1/0
______
Error
>>> not 0 and 12 or 0
______
12

Question 5: WWPD: What If?

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q what_if -u

The functions below are already defined in lab01.py. If you get stuck, try python3 -i lab01.py and experiment.

>>> def xk(c, d):
...     if c == 4:
...         return 6
...     elif d >= 4:
...         return 6 + 7 + c
...     else:
...         return 25
>>> xk(10, 10)
______
23
>>> xk(10, 6)
______
23
>>> xk(4, 6)
______
6
>>> xk(0, 0)
______
25
>>> def how_big(x):
...     if x > 10:
...         print('huge')
...     elif x > 5:
...         return 'big'
...     elif x > 0:
...         print('small')
...     else:
...         print("nothin'")
>>> how_big(7)
______
'big'
>>> how_big(12)
______
huge
>>> how_big(1)
______
small
>>> how_big(-1)
______
nothin'
>>> def so_big(x):
...     if x > 10:
...         print('huge')
...     if x > 5:
...         return 'big'
...     if x > 0:
...         print('small')
...     print("nothin'")
>>> so_big(7)
______
'big'
>>> so_big(12)
______
huge 'big'
>>> so_big(1)
______
small nothin'
>>> def ab(c, d):
...     if c > 5:
...         print(c)
...     elif c > 7:
...         print(d)
...     print('foo')
>>> ab(10, 20)
______
10 foo
>>> def bake(cake, make):
...    if cake == 0:
...        cake = cake + 1
...        print(cake)
...    if cake == 1:
...        print(make)
...    else:
...        return cake
...    return make
>>> bake(0, 29)
______
1 29 29
>>> bake(1, "mashed potatoes")
______
mashed potatoes "mashed potatoes"

Hint: print (unlike return) does not cause the function to exit!

Question 6: How to get Seven?

In each of following, what does the list indexing look like to get the number 7? Ex. x = [7], answer would be x[0]. You can use the interpreter or Python tutor to experiment with your answers.

Use OK to test your knowledge with the following "How to get Seven?" questions:

python3 ok -q sevens -u
>>> x = [1, 3, [5, 7], 9]
______
x[2][1]
>>> x = [[7]]
______
x[0][0]
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
______
x[1][1][1][1][1][1][0]
>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
______
Error
>>> lst = [3, 2, 7, [84, 83, 82]] # Write the code that indexes into lst to output the 82
______
lst[3][2]
>>> lst[3][0]
______
84

Coding Practice

Question 7: Fix the Bug

The following snippet of code doesn't work! Figure out what is wrong and fix the bugs.

def both_positive(x, y):
    """Returns True if both x and y are positive.

    >>> both_positive(-1, 1)
    False
    >>> both_positive(1, 1)
    True
    """
return x and y > 0 # You can replace this line!
return x > 0 and y > 0

The original line (return x and y > 0) will check that two things are true:

  1. x
  2. y > 0

When will x be considered True? In Python, any number that is not 0 is considered True. Thus, the first doctest will fail: x = -1 and -1 != 0, and y = 1 > 0, so both clauses are True.

Use OK to test your code:

python3 ok -q both_positive

Question 8: Falling Factorial

Let's write a function falling, which is a "falling" factorial that takes two arguments, n and k, and returns the product of k consecutive numbers, starting from n and working downwards.

def falling(n, k):
    """Compute the falling factorial of n to depth k.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 0)
    1
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    """
"*** YOUR CODE HERE ***"
total, stop = 1, n-k while n > stop: total, n = total*n, n-1 return total

Use OK to test your code:

python3 ok -q falling

Question 9: Perfect Number

In lecture, we wrote the factors_list function, which takes in a number n and returns a list of all of the factors of n that are less than n. Using this function, implement a function perfect_number which takes in a number n and determines whether the number is a perfect number. A perfect number is equal to the sum of its factors. For example, 6 is a perfect number since 6 = 1 + 2 + 3.

def factors_list(n):
    """Return a list containing all the numbers that divide `n`
    evenly, except for the number itself. Make sure the list is in
    ascending order.

    >>> factors_list(6)
    [1, 2, 3]
    >>> factors_list(8)
    [1, 2, 4]
    >>> factors_list(28)
    [1, 2, 4, 7, 14]
    """
    all_factors = []
    x = 1
    while x < n:
        if n % x == 0:
            all_factors += [x]
        x += 1
    return all_factors

def perfect_number(n):
    """Returns True or False indicating whether `n` is a perfect 
    number. A number is a perfect number when the sum of all its 
    factors equal the number itself.

    >>> perfect_number(6)
    True
    >>> perfect_number(8)
    False
    >>> perfect_number(28)
    True
    """
    all_factors = factors_list(n)
"*** YOUR CODE HERE ***"
sum_of_all_factors = 0 for factor in all_factors: sum_of_all_factors += factor return n == sum_of_all_factors

Use OK to test your code:

python3 ok -q perfect_number

I Want to Play a Game

Now that you have learned about call expressions and control structures, you can code an algorithm! An algorithm is a set of steps to accomplish a task. You use algorithms every day — from adding numbers by hand to getting to your next lecture.

Let's play a number guessing game with Python! Pick a number and Python will guess randomly until it guesses correctly.

All the code for this guessing game will be in lab01.py. In your terminal, start an interactive session with Python:

$ python3 -i lab01.py

The guess_random function will prompt you for a number, ask if its guess is correct (many times) and return the number of guesses Python had to make. To tell Python if its guess is correct, just enter y at the [y/n] prompt. If it's wrong, enter n. Python isn't very good at guessing yet, so if it's taking too long, you can type Ctrl-C to make it stop.

>>> guess_random()
Pick an integer between 1 and 10 (inclusive) for me to guess: 7
Is 1 your number? [y/n] n
Is 5 your number? [y/n] n
...

Randomly guessing works, but you can create an even better guessing strategy.

Question 10: Guess Linear

One weakness in the guess_random strategy is that it can repeat (incorrect) guesses. Rather than guessing wildly, let's guess numbers in increasing order.

Note: is_correct is a function that will ask the user if the guess is correct and return True if the user confirms that the guess matches the correct number. Feel free to reference the implementation of guess_random as you implement guess_linear.

def guess_linear():
    """Guess in increasing order and return the number of guesses."""
    prompt_for_number(LOWER, UPPER)
    num_guesses = 1
    guess = LOWER
"*** YOUR CODE HERE ***"
while not is_correct(guess): guess += 1 num_guesses += 1
return num_guesses

The best way to test this function is by playing with it interactively. See if your algorithm does what you expect!

Question 11: Guess Binary

This question is not required for submission. However, we encourage you to try it out on your own time for extra practice.

Challenge question. The guess_linear function can take a long time if your number is large. However, a strategy called binary search can find the correct number faster. The idea is to start in the middle of the range and after each incorrect guess ask if the guess is_too_high or too low. Either way, you can eliminate half the remaining possible guesses.

Hint: Try using the is_too_high function to implement a faster strategy. is_too_high will return True if the guess is greater than the correct number.

>>> result = is_too_high(5)
Is 5 too high? [y/n] y
>>> result
True

Hint: You may want to update other variables besides guess.

def guess_binary():
    """Return the number of attempted guesses. Implement a faster search
    algorithm that asks the user whether a guess is less than or greater than
    the correct number.

    Hint: If you know the guess is greater than the correct number, then your
    algorithm doesn't need to try numbers that are greater than guess.
    """
    prompt_for_number(LOWER, UPPER)
    num_guesses = 1
    lower, upper = LOWER, UPPER
    guess = (lower + upper) // 2
"*** YOUR CODE HERE ***"
while not is_correct(guess): if is_too_high(guess): upper = guess - 1 else: lower = guess + 1 guess = (lower + upper) // 2 num_guesses += 1
return num_guesses

If you choose a number between 1 and 10, this approach should need no more than 4 guesses to find your number.

The best way to test this function is by playing it interactively. Try to think of edge cases — numbers that might cause your algorithm to do the wrong thing. If you edit the Python file while running it interactively, you will need to exit() and restart the interpreter in order for those changes to take effect.

So far, your algorithms have only had to find a number between 1 and 10. What if we expanded the possible range of numbers to be between 1 and 100? How many guesses would each algorithm make if you picked 100 to be your number?

A Second Look

Let's try to visualize the two algorithms you've just written! We've provided code that will run each algorithm 1000 times and plot the number of guesses the algorithms had to make. The numbers are randomly chosen from between 1 and 100.

$ python3 guessing_game_graph.py guess_linear
$ python3 guessing_game_graph.py guess_binary

Each bar represents the number of guesses the algorithm took to find the correct number. The height of each bar represents the frequency of each number of guesses. Look carefully at the axes when comparing the two graphs! You should see that guess_linear sometimes took up to 100 guesses; what was the highest number of guesses that guess_binary took?

You can see our plots for guess_linear and guess_binary. If your plots only have one bar, make sure your functions are returning the correct number of guesses!

Before you dive into the extra questions, be sure to run python3 ok --submit!