Discussion 1: Control

What everyone will need:

  • A way to view this worksheet (printed, laptop, tablet, etc)
  • A way to take notes (paper or a device)

While and If

Learning to use if and while is an essential skill. During this discussion, focus on what we've studied in the first three lectures: if, while, assignment (=), comparison (<, >, ==, ...), and arithmetic. Please don't use features of Python that we haven't discussed in class yet, such as for, range, and lists. We'll have plenty of time for those later in the course, but now is the time to practice the use of if (textbook section 1.5.4) and while (textbook section 1.5.5).

Q1: Race

The race function below sometimes returns the wrong value and sometimes runs forever.

Run in 61A Code

Find positive integers x and y (with y larger than x but not larger than 2 * x) for which either:

  • race(x, y) returns the wrong value or
  • race(x, y) runs forever

You just need to find one pair of numbers that satisfies either of these conditions to finish the question, but if you want to think of more you can.

Notes:

  • x += 1 is the same as x = x + 1 when x is assigned to a number.
  • 0 is a false value and all other numbers are true values.
The value of race(x, y) is incorrect when it is not the first time the tortoise passes the hare. Try some small numbers (below 5) to see if you can find a case where tortoise has become larger than hare, but the expression tortoise - hare was not zero when it happened.

Q2: Fizzbuzz

Implement the classic Fizz Buzz sequence. The fizzbuzz function takes a positive integer n and prints out a single line for each integer from 1 to n. For each i:

  • If i is divisible by both 3 and 5, print fizzbuzz.
  • If i is divisible by 3 (but not 5), print fizz.
  • If i is divisible by 5 (but not 3), print buzz.
  • Otherwise, print the number i.

Try to make your implementation of fizzbuzz concise.

Run in 61A Code
Be careful about the order of your if and elif clauses: try first checking if the current number is divisible by both 3 and 5, then check for just divisibility by 3 and just divisibility by 5.

Problem-Solving

A useful approach to implementing a function is to:

  1. Pick an example input and corresponding output.
  2. Describe a process (in English) that computes the output from the input using simple steps.
  3. Figure out what additional names you'll need to carry out this process.
  4. Implement the process in code using those additional names.
  5. Determine whether the implementation really works on your original example.
  6. Determine whether the implementation really works on other examples. (If not, you might need to revise step 2.)

Importantly, this approach doesn't go straight from reading a question to writing code.

For example, in the is_prime problem below, you could:

  1. Pick n is 9 as the input and False as the output.
  2. Here's a process: Check that 9 (n) is not a multiple of any integers between 1 and 9 (n).
  3. Introduce i to represent each number between 1 and 9 (n).
  4. Implement is_prime (you get to do this part with your group).
  5. Check that is_prime(9) will return False by thinking through the execution of the code.
  6. Check that is_prime(3) will return True and is_prime(1) will return False.

Try this approach together on the next two problems.

Important: It's highly recommended that you don't check your work using a computer right away. Instead, talk to your group and think to try to figure out if an answer is correct. On exams, you won't be able to guess and check because you won't have a Python interpreter. Now is a great time to practice checking your work by thinking through examples. You could even draw an environment diagram!

If you're not sure about how something works or get stuck, ask for help from the course staff.

Q3: Is Prime?

Write a function that returns True if a positive integer n is a prime number and False otherwise.

A prime number n is a number that is not divisible by any numbers other than 1 and n itself. For example, 13 is prime, since it is only divisible by 1 and 13, but 14 is not, since it is divisible by 1, 2, 7, and 14.

Use the % operator: x % y returns the remainder of x when divided by y.

Here's a while statement that goes through all numbers above 1 and below n : 
i = 2
while i < n:
    ...
    i = i + 1

You can use n % i == 0 to check whether i is a factor of n. If it is, return False.

Run in 61A Code
Presentation Time: Come up with a one-sentence description of the process you implemented to solve is_prime that you think someone could understand without looking at your code. Present your solution to your group / present your group's solution to the class.

Q4: Unique Digits

Write a function that returns the number of unique digits in a positive integer.

Hints: You can use // and % to separate a positive integer into its one's digit and the rest of its digits.

You may find it helpful to first define a function has_digit(n, k), which determines whether a number n has digit k.

Run in 61A Code
One approach is to loop through every digit from 0 to 9 and check whether n has the digit. Count up the ones it has.

Q5: Ordered Digits

Implement the function ordered_digits, which takes as input a positive integer and returns True if its digits, read left to right, are in non-decreasing order, and False otherwise. For example, the digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.

Run in 61A Code

Use Ok to test your code:

python3 ok -q ordered_digits

def ordered_digits(x): 
"""Return True if the (base 10) digits of X>0 are in non-decreasing
order, and False otherwise.

>>> ordered_digits(5)
True
>>> ordered_digits(11)
True
>>> ordered_digits(127)
True
>>> ordered_digits(1357)
True
>>> ordered_digits(21)
False
>>> result = ordered_digits(1375) # Return, don't print
>>> result
False

"""
"*** YOUR CODE HERE ***"

Submit Attendance

You're done! Excellent work this week. Please be sure to ask your section TA for the attendance form link and fill it out for credit. (one submission per person per section).