Lab 1: Expressions and Control Structures
Due at 11:59pm on 01/29/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 3, 6, 7, and 8 must be completed in order to submit the lab.
 Questions 1, 2, 4, and 5 (What Would Python Print?) are designed to help introduce concepts and test your understanding.
 Question 9 is completely optional coding practice. It is recommended that you complete this problem on your own time.
Using Your Class Account
Register for a class account info through this link. After logging in through CalNet, request an account by clicking on the link under Your Inidividual Account. After accepting the conditions, fill out your information (name, student ID, email) under Account Registration. Then go to See Account under Your Individual Account. You will be presented with a course account and your username will be of the form cs61axxx. These accounts allow you to use instructional machines in the CS department and are useful if you do not have regular access a computer.
If you do not have a CalNet account, see your TA to get a course account.
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 commandline options, take a look at the documentation.
Using no commandline options will run the code in the file you provide and return you to the command line.
python3 lab01.py
i
: Thei
option runs your Python script, then opens an interactive session. To exit, typeexit()
into the interpreter prompt. You can also use the keyboard shortcutCtrlD
on Linux/Mac machines orCtrlZ 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
Division
Let's compare the different divisionrelated operators in Python:
True Division: / (decimal division) 
Floor Division: // (integer division) 
Modulo: % (remainder) 




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 toTrue
only if both operands evaluate toTrue
. If at least one operand isFalse
, thenand
evaluates toFalse
.or
evaluates toTrue
if at least one operand evaluates toTrue
. If all operands areFalse
, thenor
evaluates toFalse
.
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 priorityand
or
has the lowest priority
It turns out and
and or
work on more than just booleans (True
,
False
). Other Python values can be considered "falsey," including 0
,
None
, and ''
(the empty string). All other values are considered "truthy."
Question 1: WWPP: Truthiness
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok q truthiness u
>>> 0 or True
______True
>>> not '' or not 0 and False
______True
>>> 13 and False
______False
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 shortcircuit. That is, they don't necessarily evaluate every operand.
Operator  Evaluates from left to right until:  Example 

AND  The first "falsey" value  False and 1 / 0 evaluates to False 
OR  The first "truthy" value  True or 1 / 0 evaluates to True 
If and
and or
do not shortcircuit, they just return the last
value. This means that and
and or
don't always return booleans when using truthy
and falsey values.
Question 2: WWPP: Veritasiness
Use OK to test your knowledge with the following "What Would Python Print?" 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
Question 3: 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:
x
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
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.
Hint: 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!
Question 4: WWPP: What If?
Use OK to test your knowledge with the following "What Would Python Print?" 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'
Hint:
return
) does not cause the function to exit!
While Loops
You can review the syntax of while
loops in
Section 1.5.5
of Composing Programs.
Question 5: WWPP: Loops
Use OK to test your knowledge with the following "What Would Python Print?" 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 become falsey, or they'll never stop! TypingCtrlC
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
Here's some food for thought: is it possible for a program to detect if there is an infinite loop in any program? Put another way, can you create a program that determines if another program will halt?
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 atline 1
.
Coding Practice
Question 6: Factor This!
Implement a function factors
which takes in a number n
and prints out (in
descending order) all of the numbers that divide n
evenly. For example, the
factors of 20 are 20, 10, 5, 4, 2, 1.
def factors(n):
"""Prints out all of the numbers that divide `n` evenly.
>>> factors(20)
20
10
5
4
2
1
"""
"*** YOUR CODE HERE ***"
x = n
while x > 0:
if n % x == 0:
print(x)
x = 1
Use OK to test your code:
python3 ok q factors
Question 7: 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, nk
while n > stop:
total, n = total*n, n1
return total
Use OK to test your code:
python3 ok q falling
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 CtrlC
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 8: 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 returnTrue
if the user confirms that the guess matches the correct number. Feel free to reference the implementation ofguess_random
as you implementguess_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 9: 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 returnTrue
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
!