## Monday

### More Strings: substrings, in operator

A substring of a string is a portion of the string that appears contiguously. For example, `blue` is a substring of `blueberries`. Python has some commands for accessing substrings.

The most relevant for us right now is the `in` operator. `in` takes a substring called the pattern and another string commonly called the target, and returns `True` if and only if the pattern appears as a substring in the target.

Sometimes, the pattern can be a single letter, but in general, the pattern can be any string.

```>>> 'a' in "apples"
True
>>> 'b' in "apples"
False
>>> "vark" in "Aardvark"
True
>>> "bbrries" in "blueberries"
False```

### While Loops

Another syntactic tool for designing programs in Python is the `while` loop. You’ve previously seen `for` loops, Boolean types, and `if` statements. The `while` loop is a mix of these three concepts. A typical `for` loop executes for a definite number of times. For example, programmers decide in advance to loop over things like finite lists, `range()` results, or the length of a string.

What if we are expecting a user to enter input in a specific format (e.g., a positive integer, a valid date, or a string with no punctuation)? We could trust the user not to make a mistake, but this approach is not very robust. Instead, if we detect that a user made a mistake in typing input, we could prompt the user again. But how many times should we ask? Once? Twice? 100 times? With a `for` loop, you’d have to set the number in advance.

A `while` loop can solve these types of computational problems by repeatedly looping until a Boolean condition is met. The general syntax of a `while` loop is:

```while <CONDITION>:
<BODY>```

The <CONDITION> is a Boolean expression. When the condition evaluates to `True`, the body of the loop will execute and then re-evaluate the condition. When the condition finally evaluates to `False`, Python skips the body of the loop and executes the next line after the body.

Note that a `for` loop can often be written as an equivalent `while` loop.

Let’s look at some examples in `while_loops.py`.

#### Try: Echo

Practice writing `while` loops, and using conditionals in a program called `echo.py`. The program should repeatedly prompt the user for an input string. If the user types anything other than `quit`, you should print their message back with a counter of how many times you’ve "echoed" a message:

``````$python3 echo.py Enter a string: hello Echo #1: hello Enter a string: test string Echo #2: test string Enter a string: quit Echo #3: quit good bye`````` Use a `while` loop to continue asking the user for strings indefinitely until they type `quit`. If you get this, next see if you can remove echo’ing the quit string (remove the `Echo #3: quit` output when the user enters `quit`). ### String Formatting The print statement is nice for outputting, but it is difficult to format the output in a way we prefer. For example, every time we put out a dollar amount, we can’t guarantee two digits after the decimal point for the cents and we also have to always leave a space between the dollar sign and the amount. String formatting allows us to define string templates:  %s string value %d int value %f float value String formatting also enables optional width and precision values: Feature Syntax Example Semantics width %<number>type %10s Format a number to a string with ten spaces minimum. precision (float only ) %.<number>f %.2f Require exactly two digits after a decimal point. Let’s look at some of the examples in `print_format.py` that show printing out the float variable `pi` from the math library using different formatting. This also shows some other examples. Note that you can combine multiple values in a single string format: ``````item = "dozen eggs" qty = 4 price = 2.49 print("%d %s cost$%.2f" % (qty, item, qty*price) )``````

#### Try

open the program `currency.py` to see what it is doing, and try running it a few times. Then modify the program to use a string formatting in the print statement to produce nicer looking output.

#### Try: Echo redux

Revisit your `echo.py` program, and try replacing the print statment with one that uses print formatting instead.

## Wednesday

### Functions

Today we’ll introduce another big, key computer science topic: functions. A function is a named sequence of statements that perform a particular operation. Some functions are built in (`int,str,float,input,print`), but you can also define your own functions. Defining your own functions has many benefits:

• Modularity and Readability: break program up into functional parts, make programs easier to read/understand/debug.

• Abstraction: hide low-level details of a function until you need to understand them; you can use a function without having to know how it is implemented (e.g., the `print` function).

• Code Reuse: put repeated code into functions: "write code once, use function multiple times".

• Minimize programmer error: write and test functions in isolation.

In fact, you’ve been defining and using your own functions for a couple of weeks now, with the `main()` function. This week, we’ll see many more examples of functions. You’ll see that functions can take input and return input, and even do other "side effects" in between.

### Function Syntax

Here is the syntax for how to define a function:

``````def <NAME>(<PARAMETERS>):
<BODY>``````

The `<NAME>` is the name of the function you define. The `<BODY>` is a series of statements that you want to execute each time you use your function. `<PARAMETERS>` is a list of zero or more inputs to the function. These parameters can be used inside the function just like any other variable.

Let’s look at some examples in `function_examples.py`. We have defined four functions so far: `printIntro, printStarRow(n), starBox(n)`, and `main()`. We will describe a few of these and then have you practice some.

Once a function is defined, you can call the function, by giving the name of the function and specific values for each parameter.

 vim shortcuts Once we start working with larger program files, it is helpful to use some vim shortcuts to move to certain parts of the file. Here are a few (in ESC mode): CNTRL-F move one page forward in the file CNTRL-U move one page backward in the file SHIFT-G moves to the end of the file : go to line number num (ex. :203 go to line number 203) / search for in the file (ex. /print search for print in the file) n find next occurance of the pattern moving forward in the file N find next occurrance of the pattern moving backward in the file

#### Exercise: practice function definition and calls

Practice defining and calling functions by modifying your program in `function_examples.py` to implement `starBox(n)`. Call `starBox` in `main` with different values of `n`. Try getting a value from the user with `input` in `main` and passing the value to `starBox`.

### What happens when a function gets called?

Python does a lot of behind-the-scenes work when a function gets called. Here is an outline of what happens:

Steps that occur when a function is called:

1. Suspend current function.

2. Evaluate arguments, copy them to parameters of the called function in order.

3. Execute called function using set values of parameters.

4. Return back to the calling function.

When calling a function, arguments are sometimes but not always plain values. Other times, they are complex expressions. These expressions get evaluated in Step 2 of the process above.

``starBox(2**3)``

### The `return` statement.

Often when you define a function, you want the function to return some value back to whatever program called the function. You can do this with the `return` command. For example, the built-in function `input` reads in a string of text from the user and returns it as a string. When a return statement is reached, the function stops and immediately returns the value indicated by the return statement.

For example, if you defined a function `def add(a,b)` to add the values `a` and `b` integers, you’ll probably want to define and return a variable `result=a+b`. Then, once you’ve added the numbers, the `return result` statement sends this value back to the calling function.

``````def add(a,b):
"""
Computes the sum of values a and b
Returns result

sample usage:
ans = add(3, 4)
print(ans)        # Should print: 7
"""

result = a + b
return result``````

### Stack Diagrams

A stack diagram is a way to visualize what happens with variables in memory as Python executes your program. Consider the following program:

``````
def main():
a = 6
b = 11
avg = average(a,b)

print("The average of " + str(a) + " and " + str(b) \
+ " equals " + str(avg))

def average(num1, num2):
"""
computes the average of two numeric values
param num1: one value
param num2: the other value
returns: the average of the two values
"""

toReturn = (num1 + num2)/2

return toReturn

main()``````

Now, on the whiteboard we’ll see how this computation happens in memory. The computer’s memory is where the program stores the state of a running program including the values of all variables and the stack of all functions currently waiting to finish. Here is the general procedure for how a function execute when called:

1. Pause the execution of the current function.

2. Create a stack frame for the called function.

• space for parameters are allocated in the function’s stack frame

• space for local variables are allocated in the function’s stack frame

3. Each argument’s value is passed to the corresponding parameter: the value of each argument (the reference in the box) is copied to the corresponding parameter in order. For example, the third parameter refers to the same value of as the third argument.

4. Execute called function step-by-step until the return or until it reaches the end of the function body.

5. Send back the return value to calling function.

6. Remove or pop the called function’s frame off stack.

7. Continue executing calling function that is now back on top of stack. (the called function now evaluates to its return value in the caller)

Some things to keep in mind as you draw your own stack diagrams:

• Function call stack is on left, values belong on the right

• Space for variables and parameters are inside stack frames, the values to which they refer are outside the stack

• The call stack always grows "up" when we call a function

• The call stack shrinks when a function returns.

• There is a separate box (frame) on the call stack for each function.

• Parameters point to the same value as the arguments in the calling function.

• The assignment operator changes the arrow.

• A function can only access/reference variable names in its own stack frame. These variables are said to be in the function’s scope

### Try: Stack Example 2

``````def main():

x = 5
y = 9

ans = addNumbers(x,y)
print("In main:")
print(ans)
print(total)       # Q2b: Gives an error. Q: Why?

def addNumbers(num1,num2):
"""
adds two numbers together
param num1: one value
param num2: the other value
returns: sum of num1 and num2
"""

total = num1 + num2
print("In addNumbers:")
print(num1)
print(num2)
print(total)

# Q1: Show the stack diagram as it exists at this point
return total

main()``````
1. Draw the stack up to the point right before `return total` is executed

2. Answer the following questions:

• (a) What is the scope, respectively, of `x`, `y`, `ans`, `num1`, `num2`, and `total`?

• (b) Why does the last line of `main()` give a runtime error?

## Friday

### Stack Review

Let’s review stack drawing with Stack Example 2

``````def main():

x = 5
y = 9

ans = addNumbers(x,y)
print("In main:")
print(ans)
print(total)       # Q2b: Gives an error. Q: Why?

def addNumbers(num1,num2):
"""
adds two numbers together
param num1: one value
param num2: the other value
returns: sum of num1 and num2
"""

total = num1 + num2
print("In addNumbers:")
print(num1)
print(num2)
print(total)

# Q1: Show the stack diagram as it exists at this point
return total

main()``````
1. Draw the stack up to the point right before `return total` is executed

2. Answer the following questions:

• (a) What is the scope, respectively, of `x`, `y`, `ans`, `num1`, `num2`, and `total`?

• (b) Why does the last line of `main()` give a runtime error?

#### Another Stack

Here is another one you can try on your own.

Trace through the execution of the program below, and draw the stack to the point `DRAW TO HERE`.

``````def main():

a = 10
b = 35
result = absval(a,b)
print("abs(%d-%d) = %d" % (a,b,result))

def absval(x,y):
"""
absval: computes absolute value of difference of two values
param x: one value
param y: the other value
returns: the absolute value of the difference of the two
"""

if (x > y):
aval = x-y
else:
aval = y-x

# DRAW TO HERE: draw the stack to this point!
#               (as it would look right before return)

return aval

main()``````

### Random Library

Python has a library for generating pseudo random numbers. This is useful if you want to write a program that does something different each time it runs. For example, game programs often use these to randomize game playing functionality like flipping a coin or rolling a die.

To use the random library, add the following to the top of your program:

``from random import *     # grab a bunch of useful functions``

The `randrange` function is one we will try out in `randomOps.py`:

``````randrange(start, stop)  # get the next random number in the range [start, stop)

randrange(stop)         # get the next random number in the range [0, stop)``````

Together: let’s modify `randomOps.py`, so that it keeps flipping coins until it flips 3 heads.

• "keeps flipping": what type of construct do we need?

• "until 3": how can we detect when 3 heads have been flipped?

### Function Practice

Today we are going to practice writing more functions.

#### Exercise: square the biggest

Together, we are going to start the design of the a function, named `square_the_biggest`, that computes the square of the larger of two values. You’ll finish the implementation in the `totally.py` file and test it out.

Let’s start by consider these two questions first:

1. Does this function take any input (do we need to pass it any values)? If so, how many? And what type of values?

2. Does this function return a value? If so, what does it return and what type of value does it return?

With this we can write the start of the function definition, and some example calls to it from `main`.

Now finish the fuction definition (its implementation) and test it out.

#### Exercise: totally

In `totally.py`, define another function named `total(n)`, which takes a positive integer as input and returns the sum of the first `n` positive integers.

Then, call your function from `main` on several different inputs to test it.

If you finish this early, try adding to `main` a call to read in a value from the user and test that it is a positive int value before calling your `total` function. If it is not, you can print out an error message. If it is, call your function.

#### Exercise: Syracuse Sequence: challenging!

This exercise combines while loops, functions, and the accumulator pattern!

In the `syracuse.py` file, add a function named `syracuseSeq` that takes as input a positive integer value, and returns the number of terms in the syracuse sequence starting at that value until the sequence reaches 1. Your function should also print out each term in the syracuse sequence. Add some calls to your function in `main` and print out the value that returned.

Starting with a value x, the next value in the syracuse sequence is determined by the following function (note that if x is even one function is applied to get the next value in the sequence, and if x is odd another is applied to get the next value in the sequence):

$\mbox{next value is} \begin{cases} x \div 2 & \mbox{ if x is even} \\ (3 \times x) + 1 & \mbox{ if x is odd} \end{cases}$

The entire syracuse sequence is generated by starting with a positive integer and repeatedly applying the function above until reaching 1. For example:

```The syracuse sequence of 4 is:  4, 2, 1
The syracuse sequence of 3 is:  3, 10, 5, 16, 8, 4, 2, 1```

It is an open question in mathematics whether this sequence always goes to 1 for every possible starting value.

Your main program should:

• ask the user to enter a starting point value x (you may assume they enter a positive int value

• call your `syracuseSeq` function that computes the syracuse sequence for x, printing out each term in the sequence until the sequences reaches 1 and returning the total number of terms in the sequence returning the total number of terms in the sequence (e.g., `syracuseSeq(4)` returns `3` and `syracuseSeq(3)` returns `8`).

• print out the value returned by the call.

Hints:

• All terms in the sequence are integers (no floats)

• The number of terms in the sequence until it reaches 1 varies for different values. Hence, you need a while loop not a for loop.

• Break solving this into 2 parts:

1. first, implement the function to print out all the terms the syracuse sequence for a passed value and test it

2. then add in the functionality to compute the total number of terms in the sequence and return that value and test it

• What pattern can you use to keep track of the total number of terms in the sequence?

#### Extra problems: stars, stars, stars!

These are some additional function writing problems that you can try out on your own. They combine functions, loops, and strings!

We don’t expect that you can necessarily solve all of these, but they are a good challenge to try in the context of getting some more practice writing functions.

In `stars.py` write a function named `pyramid` that takes a positive int value `n` and prints out the following pattern of stars:

```when n is 3:
*
**
***

when n is 5:
*
**
***
****
*****```

And then make some calls from `main` to your function.

Hints:

• You could solve this using string accumulator or a string operator. Try one, then try the other way.

• Remember you know how to print out a box of stars. In what ways is this similar? In what ways is it different?

• Think about what is printed each line, how many stars, and how that related to the loop iteration.

If you solve this one, add another function called `pyramid2` that prints out this challenging pattern of stars for different n values:

```when n is 3:
***
**
*

when n is 5:
*****
****
***
**
*```

Hints:

• This one is easier to solve using string operators vs. string accumulator.

And if you want a super challenge, here is another very challenging pattern to think about:

```when n is 3:
*
**
***

when n is 5:
*
**
***
****
*****```

Hints:

• think about some number of spaces being printed each line in addition to some number of stars. What is the pattern depending on the loop iteration?