
:::blockquote{.notes-only}
In the beginning was the Tao. The Tao gave birth to Space and Time.
Therefore Space and Time are the Yin and Yang of programming.
:cite[— [Tao of Programming](https://www.mit.edu/~xela/tao.html)]
:::

##  Binary Numbers 

In decimal system, a number is expressed as a sequence of digits $0$ to $9$.

For example, `Two thousand twenty one ⇔ 2021`

##

In binary number system the set of digits, is called binary digits or :sc[bits]: $\{0, 1\}$.  

A binary number is expressed as a sequence of bits.  

For example, $183$ in binary is $10110111$.

## Converting from decimal to binary

::decimal-binary

## Converting from binary to decimal

::binary-decimal

## Groups of bits

A group of $8$ bits is called a :i[byte]  e.g. $11010111$
- $1$ kilobyte (kB) = $1000$ bytes
- $1$ megabyte (MB) = $10^6$  (million) bytes
- $1$ gigabyte (GB) = $10^9$ (billion) bytes
- $1$ terabyte (TB) = $10^{12}$ bytes (1000 billion)

## What is programming? 

:::div{.gap1}
Programming is the process of creating a set of instructions — a program — to tell a computer how to perform a task.

Programs take input data, perform some computation — numerical or symbolic (text) — and produce output data.
:::

##

:::div{.gap1}
Computers can perform only basic binary operations (such as add or multiply two numbers)

How do we communicate complex instructions to computers? — Use a programming language!
:::

## Levels of programming languages

:::div{.my2}
| Low-level languages                                    | High-level languages                              |
|--------------------------------------------------------|---------------------------------------------------|
| Closer to machine, difficult for humans                | Closer to humans,  easier for humans to work with |
|                                                        |                                                   |
| Less portable, provide  less abstraction over hardware | More portable, more abstraction over hardware     |
| Examples: Assembly Language                            | Examples: Java, Python                            |
:::


## How do computers understand high-level languages?

:::div{.gap1}
High-level languages are translated into machine code (for CPU). 

Programming languages come in two main flavors — :i[compiled] languages or :i[interpreted] languages.

Compilers and interpreters are software tools responsible to translate source code into machine code.
:::

##

:::div{style="margin-bottom: 1em;"}
:sc[Compiled] languages (e.g. C/C++, Java)  

- High-level program (source code)  ➞  :sc[Compiler] ➞ Binary executable (e.g. .exe or .dmg)
- Once compiled, the binary program can be executed without compiler.
:::

:::div
:sc[Interpreted] (e.g. Python, Ruby)

- High-level program (source code) ➞ Executed directly by an :sc[Interpreter]
- The interpreter is required on the machine where the program is executed.
:::

::divider

## Data in binary

Computers can understand only binary numbers  

How can we encode data in the real world into binary numbers?

::img{src="module-1/data-in-binary.svg" style="margin: 2rem auto; width:100%;" }

## Integers in binary

We already saw how to represent positive integers in binary e.g.  
:div[$109 = 1101101_2$]{style="text-align: center;"}

For signed integers (to differentiate negative and positive), an extra leftmost bit is used for sign only, e.g.  
    :div[$-109 = \colorbox{lightblue}{1}1101101_2$]{style="text-align: center;"} 
    :div[$+109 = \colorbox{lightblue}{0}1101101_2$]{style="text-align: center;"}

::div[(For more info: https://en.wikipedia.org/wiki/Signed_number_representations)]{.smaller}

## Real numbers in binary

64-bit :sc[Floating point] format is used to represent numbers with decimal point, e.g.  
:div[$\colorbox{lightblue}{0}\colorbox{lightpink}{10000000000}\colorbox{lightgreen}{1001001000011111101101010100010001000010110100011000} = 3.141592653589793$]{style="text-align: center;"}

::div[(For more info: https://en.wikipedia.org/wiki/Double-precision_floating-point_format)]{.smaller}

##

Floating point format has a :i[finite precision], but digits of $\pi$ run forever: :div[$3.1415926535897932384626433832795028841...$]{style="text-align: center;"}

With only 64-bits, we can only have precision up to a fixed digits after decimal point: $3.141592653589793$



## Text in binary

::p[Letters and punctuations in human languages are encoded in binary using a :i[Character Encoding] such as ASCII or UTF-8 (Unicode).]{.ppt-m-3}

::image{style="margin: 0 auto; width: 80%;" src="module-1/ASCII-Table.png" .ppt-img50}  
::div[(source: https://simple.wikipedia.org/wiki/ASCII)]{style="font-size: 0.6em; margin: 0 auto;"}

## Images, audio & video in binary

Binary data is stored in a file using a specific format.

Programs know what to do (play music, show image, etc) based on the format.  

We already know some of these formats:
- Images: jpeg, png
- Audio: mp3, m4a, wma
- Video: mp4, avi, wmv


::divider

## Thonny Demo — Editor vs Shell

Python interpreter works in two modes:
- An interactive :sc[Shell] mode (with the prompt `>>>`)
    - Line(s) of code is executed immediately as soon entered and output is visible immediately
- :sc[Script] mode
    - Executes a Python file (`.py`) as a program.

Thonny allows us to use both modes in one graphical interface.

## Comments

Comments are annotations we add to our program and are ignored by the Python interpreter.

In Python, we start a comment using `#`.

```python
# Author: Deven
# My first program

# This is a comment on its own line & it will be ignored
print("Hello, world!")  # str
print(123)  # int
print(1.614)  # float 
```

##    
We use comments to:
- Make the code easier to read and understand by explaining how it works.
- Indicate authorship and license.
- Disable some code (prevent it from executing) but still keeping it in the file.


In Thonny, we can use `Edit menu -> Toggle comment` to comment/uncomment the selected lines.


## Objects and Data Types

All data in a Python program is represented by :sc[objects]. 

An object always has a :sc[type] (or :sc[class]) associated with it.

We can use `type()` function to know the type of an object.

:::hgrid{gap="7em"}
```python lineno=false
>>> type(5)
<class 'int'>
```

::image{style="margin: 0 auto; width: 40%;" src="module-1/int.svg" .ppt-img100}  
:::

##

::::div{style="display: grid; gap: 3em;"}
:::hgrid{gap="7em"}
```python lineno=false
>>> type(3.1415)
<class 'float'>
```

::image{style="margin: 0 auto; width: 40%;" src="module-1/float.svg" .ppt-img100}  
:::

:::hgrid{gap="7em"}
```python lineno=false
>>> type("Hello")
<class 'str'>
```

::image{style="margin: 0 auto; width: 40%;" src="module-1/str.svg" .ppt-img100}  
:::
::::

##

An object's type determines the operations that the object supports:

```python
#  objects of int type can be added using +
>>> 10 + 5
15

# But an object of type str cannot be added to an int using +
>>> "Hello" + 5
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: can only concatenate str (not "int") to str
```

## Summary
 
We saw the three basic data types in Python:
- `int`: Integers such as $..., -1, 0, 1, 2, ...$
- `float`: Floating-point numbers such as $-1.2, 3.14,$ etc.
- `str`: Text data (a sequence of characters) such as "hello world", "Python", etc.

The terms :sc[Object] and :sc[Value] are used interchangeably.  
So are the terms :sc[Class] and :sc[Type].


::divider

1 — Programming Basics


## Review of last week

All data in a Python program is represented by :sc[objects]. 

An object always has a :sc[type] (or :sc[class]) associated with it.

- `int`: Integers such as $..., -1, 0, 1, 2, ...$
- `float`: Floating-point numbers such as $-1.2, 3.14,$ etc.
- `str`: Text data (a sequence of characters) such as "hello world", "Python", etc.

In Thonny, we can use `Edit menu -> Toggle comment` to comment/uncomment the selected lines.

## Variables

In Python, a :sc[Variable] is a name that refers to an object in computer memory.  
A variable can be created using :sc[Assignment Statement]:  

:::div{.center .code .my3}
:span[variable_name = value]{.bgblue .p1 .br5}
:::

`=` is known as the :sc[assignment operator].

##

```python
# create a variable and assign it value 20
temperature = 20  

# variable temperature refers to 20 which is displayed
print("Today's temperature is", temperature)

# show type of the variable
print("Type of temperature variable is", type(temperature))
```

```output
Today's temperature is 20
Type of temperature variable is <class 'int'>
```

## Arithmetic with numbers
Calculations with numbers can be done using :i[arithmetic operators].

::::div{.hgrid}
:::div
```python
# Addition
print(1.5 + 1.5) # 3.0

# Subtraction
print(10 - 20)  # -10
```
:::
:::div
```python
# Multiplication
print(42 * 42)  # 1764

# Division
print(1 / 5)  # 0.2

# Exponentiation (x to the power of y)
print(2 ** 16)  # 65536
```
:::
::::

##

```python
temperature = 20
# Unary minus operator
print(-temperature)  # -20


# Computing rest mass energy of an electron
rest_mass = 9.109e-31  # Using scientific notation
speed_of_light = 3e8

rest_mass_energy = rest_mass * (speed_of_light ** 2)  # E = mc^2
print(rest_mass_energy)  # 8.198099999999999e-14
```

## Floor division and remainder

::img{src="module-2/divmod.svg" style="margin:2em;"}


```python
# floor division
print(20 // 3)  # 6

# remainder
print(20 % 3)  # 2
```

## 

```python
# Converting seconds to minutes

duration = 320
print(duration, "seconds equal", duration / 60, "minutes.")
# 320 seconds equal 5.333333333333333 minutes.


# Alternative approach:
minutes = duration // 60
seconds = duration % 60
print(duration, "seconds equal", minutes, "minutes and", 
      seconds, "seconds.")
# 320 seconds equal 5 minutes and 20 seconds.
```

## Result type of arithmetic operations

::image{style="margin: 0 auto; width: 65%;" src="module-2/result_type.png" .ppt-img80} 

##
```python
x = 2 + 1
print(x, type(x))  # 3 <class 'int'>

x = 2 + 1.0
print(x, type(x))  # 3.0 <class 'float'>

# Classic division always results in float
x = 1 / 2  
print(x, type(x))  # 0.5 <class 'float'>
```

:::div{.px2 .py1 .my2 style="border: solid 1px lightgray; border-radius:5px; background-color: #d6efd6;"}
:b[Try the above examples with other operators!]{.p0}
:::

##

Try the problem "Distance between two points" on Ed.

## Basic string operations

Strings are sequences of zero or more characters.

In Python, strings are enclosed by either single or double quotes.
 
```python
"Hello"
'everyone!'
"I'm Batman."  # single quote allowed inside double quotes,
'You can call me "Bruce".'  # and vice versa.
'123' # this is a string, not a number!
"" # this is an empty string
" " # this is a string with just one space
```

##
```python
# a multi-line string using triple quotes
lines = """The woods are lovely, dark and deep,   
But I have promises to keep,   
And miles to go before I sleep,   
And miles to go before I sleep.
"""
print(lines)

# We can also use single quotes for multi-line strings
print(
'''I hold it true, whate'er befall;
I feel it when I sorrow most;
'Tis better to have loved and lost
Than never to have loved at all.
''')
```

## String concatenation (joining) using `+` operator

```python
message = "Hello" + "everyone"
print(message)  # Helloeveryone

name = "Alice"
message = "Hello " + name
print(message)  # Hello Alice

string = "1" + "2" + "3"
print(string)  # 123 and not the number 6

price = 100
print(price + " USD")
# TypeError: unsupported operand type(s) for +: 'int' and 'str'
```

## String repetition
String can be repeated multiple times using `*` operator.

```python
print("Welcome! " * 3)  # 'Welcome! Welcome! Welcome! '

print(4 * "ha")  # 'hahahaha'

```

## String length
The function `len()` returns length of its argument string.

```python
password = "xyz1234"
print("Password length:", len(password))
# Password length: 7

print(len(1234))
# TypeError: object of type 'int' has no len()

```

## Order of Expression Evaluation

When we have multiple operators in the same expression, which operator should apply first?  

All Python operators have a :sc[precedence] and :sc[associativity]:
- Precedence — for two different kinds of operators, which should be applied first?
- Associativity — for two operators with the same precedence, which should be applied first?

##
Table below show operators from higher precedence to lower.

:::div{.my2 .hgrid}
| Operator            | Associativity |
|---------------------|---------------|
| `()` (parentheses)  | -             |
| `**`                | Right         |
| Unary `-`           | -             |
| `*`, `/`, `//`, `%` | Left          |
| Binary `+`, `-`     | Left          |
| `=` (assignment)    | Right         |
:::


##
```python
x = 3
y = 5
# Multiplication has higher precedence than addition
z = x + 2 * y + 1  
print(z)  # 14

# Need to use parentheses to enforce the order we want
z = (x + 2) * (y + 1)
print(z)  # 30

# Same precedence so left to right
z = x * y / 100  
print(z)  # 0.15
```

## 
```python
# Same as 2 ** (3 ** 2) because "**" goes right to left
z = 2 ** 3 ** 2
print(z)  # 512

# Using parentheses to enforce the order we want
z = (2 ** 3) ** 2  
print(z)  # 64

x = 5
x = x + 1  # addition happens first and then assignment
print(x)  # 6

```

## More on Variables

Let us write code that implements the following formula to convert fahrenheit to celsius:

$$c = \frac{5(f-32)}{9}$$


```python
print("10 F in C is", 5 * (10 - 32) / 9)
```

## :span[Variables allow "saving" intermediate results of a computation]{style="font-size: 0.83em;"}

We can use variable to store the result so that we can reuse it in the program later.  

```python
fahrenheit = 10

# Store the result of the expression
celsius = 5 * (fahrenheit - 32) / 9

print(fahrenheit, "F in C is", celsius)

# Use variable celsius for more calculations
print("Adding 10 degrees today:", celsius + 10)
```

## :span[Variables can be reassigned new values]{style="font-size: 0.85em;"}
```python
# Create variable name "number" and assign a value to it
number = 123  
print(number)  # displays 123

# Assign new value to existing variable "number"
number = -50

print(number)  # displays -50

# add 10 and assign the result value to existing variable "number"
number = number + 10

print(number)  # displays -40
```

##

New values can be of different type.  

<div style="margin-top: 2em; margin-bottom: 2em; width: 800;">
<iframe  width="800" height="500" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=number%20%3D%20123%20%20%23%20an%20int%20value%0Amessage%20%3D%20%22hello%22%20%20%23%20a%20string%0A%0Aprint%28number,%20type%28number%29%29%0Aprint%28message,%20type%28message%29%29%0A%0A%23%20Now%20variable%20number%20refers%20to%20the%20string%20%22hello%22%0Anumber%20%3D%20message%0A%0Aprint%28number,%20type%28number%29%29%0Aprint%28message,%20type%28message%29%29%0A&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
</div>

## 
However, variables should be changed with caution as it can produce errors or strange results.
```python
number = 123  # an int value
message = "hello"  # a string

# Now variable number refers to the string "hello"
number = message
print(number * 2) # String repetition!
print(number - 10) # minus won't work with string.
```

```output
hellohello
Traceback (most recent call last):
    print(number - 10)
TypeError: unsupported operand type(s) for -: 'str' and 'int'
```

## Example: Swapping values
Sometimes we need to swap (interchange) values of two variables.

::::div{.hgrid style="width: 110%;"}
:::div
A naive attempt (does not work):
```python
x = 137
y = 42

# Try swapping
x = y
y = x

print(x, y)  # 42 42
```
:::

:::div
The following will work:
```python
x = 137
y = 42

# Correct way to swap
temp = x
x = y
y = temp

print(x, y)  # 42 137
```
:::
::::

##

Try the problem "Textbox" on Ed.


## Rules for variable names

- A variable name can only contain alpha-numeric characters and underscores `A-Z, a-z, 0-9, _`
- A variable name cannot start with a number
- Variable names are case-sensitive
    - (`cat`, `Cat`, and `CAT` are three different variables)
- They cannot be keywords.
    - Python has 33 reserved keywords, you can see a list of them by typing `help("keywords")` in the Python shell.

:::div{.px2 .my2 style="border: solid 1px lightgray; border-radius:5px; background-color: #d6dcef;"}
Python filenames must follow the same rules as above.
:::

## Good practice for naming variables

- Name your variable something descriptive of its purpose or content.
- If the variable is one word, all letters should be lowercase. Eg: `hour`, `day`.
- If the variable contains more than one word, then they should all be lowercase and each separated by an underscore. This is called :i[snake case].  
    e.g. `is_sunny`, `cat_name`
- Good variable names: `hour`, `is_open`,  `number_of_books`, `course_code`
- Bad variable names: `asfdstow`, `nounderscoreever`, `ur_stupid`, `CaPiTAlsANyWHErE`




::divider


2.1 — Variables, Arithmetic & String operations


## Function calls
Function take zero or more input values, perform an action or computation, and return the result value. 

Input values passed to a function are called :sc[arguments].  

A :sc[Function Call] is an expression that looks like below:


:::div{.center .code .my3}
:span[function_name(argument1, argument2, ..., argumentN)]{.bgblue .p1 .br5}
:::
    
How do we say it? — function "takes" argument(s) and "returns" a result. The result is also called the :sc[return value].

## 
The number of arguments required by a function depends on how that function is defined. 

Following are some built-in functions available in Python:
```python
# min() function takes 2 or more numbers and returns the minimum 
x = min(1, -4, 6)
print(x)  # -4

# abs() function takes a number and returns absolute value of the number
y = abs(-6)
print(y)  # 6

# Gives an error if we do not give exactly one number
z = abs(-1, 4)
# TypeError: abs() takes exactly one argument (2 given)
```

## Expressions vs Statements
An :sc[Expression] is any valid combination of values, variables, operators, function calls.  

When executed, it always evaluates to a single object.

```python
x = 3
y = 4
z = x ** 2 + y ** 2  # this expression evaluates to an int object
print(z)  # 25

s = "hello"
s2 = s * len(s) # this expression evaluates to str value
print(s2)  # hellohellohellohellohello

```

## 
A statement is one or more lines of code that performs a task but does not evaluate to any value.  

So, statements cannot be used as a part of an expression.

```python
>>> x = 123  # Does not evaluate to anything so nothing shows below
>>> x  # This is an trivially an expression
123
>>> 10 + (x = 123)  # Trying to use assignment statement in an expression
    10 + (x = 123)
            ^
SyntaxError: invalid syntax
```

## Function composition
Function composition is calling a function with the result(s) of another function(s).

It is a very useful thing to do especially when we do not need to store intermediate results.

::::div{.hgrid}
:::div
::div[Using intermediate variables]{.b}
```python
x = -5
y = -8
a = abs(x)
b = abs(y)
z = min(a, b)
print(x, y, z)
```
:::

:::div
::div[Using composition]{.b}
```python
x = -5
y = -8
z = min(abs(x), abs(y))
print(x, y, z)
```
:::
::::

## 

Check :i[2.2 (B) — Built-in Functions] on Ed Lessons.


## `print()` displays a space between arguments

```python place="start"
num = 1.5e3
city = "New York City"
year = 2023
print(num, city, year)
```

First, the arguments of `print()` are evaluated as:

```python place="start"
print(1500.0, "New York City", 2023)
```

Then, `print()` function is executed, which would display:

:::div{.code style="background-color: white; border-radius:5px; padding: 0.25rem 1rem;"}
1500.0:span[&nbsp;]{style="background-color: red;"}New York City:span[&nbsp;]{style="background-color: red;"}2023
:::

::div[(Highlighted in red are spaces added by `print()`)]{.ppt-f90 style="margin-top: 0.5em;"}


##

```python place="start"
x1 = 1.5
y1 = 2

print("Point:", "(", x1, ",", y1, ")")
```

First, the arguments of `print()` are evaluated as:

```python place="start"
print("Point:", "(", 1.5, ",", 2, ")")
```

Then, `print()` function is executed, which would display:

:::div{.code style="background-color: white; border-radius:5px; padding: 0.25rem 1rem;"}
:span[Point:]:span[&nbsp;]{style="background-color: red;"}(:span[&nbsp;]{style="background-color: red;"}1.5:span[&nbsp;]{style="background-color: red;"},:span[&nbsp;]{style="background-color: red;"}2:span[&nbsp;]{style="background-color: red;"})
:::

::div[(Highlighted in red are spaces added by `print()`)]{.ppt-f90 style="margin-top: 0.5em;"}

## 

```python place="start"
x1 = 1.5
y1 = 2

point1 = "(" + str(x1) + ", " + str(y1) + ")" 
print("Point:", point1)
```

First, the arguments of `print()` are evaluated as:

```python place="start"
print("Point:", "(1.5, 2)")
```

Then, `print()` function is executed, which would display:

:::div{.code style="background-color: white; border-radius:5px; padding: 0.25rem 1rem;"}
:span[Point:]:span[&nbsp;]{style="background-color: red;"}(1.5, 2)
:::

::div[(Highlighted in red are spaces added by `print()`)]{.ppt-f90 style="margin-top: 0.5em;"}


## Defining a function

A function is a :i[named] block of code that performs a task.

So far we have been using (calling) functions to do specific tasks — `print()`, `input()`, etc.

We can also define/create our own function.


## Defining a function that takes no arguments

:span[Such functions always do the same thing each time they are executed.]{.ppt-f94}

::::div{.hgrid}
:::div
```python
# Function definition
def display_greeting():
    print("+------------+")
    print("|  Welcome!  |")
    print("+------------+")

# Function call
display_greeting()

# Call it again
display_greeting()
```
:::

:::div
```output
+------------+
|  Welcome!  |
+------------+
+------------+
|  Welcome!  |
+------------+
```
:::
::::


## :span[Functions with arguments and return value]{.ppt-f90}
A function can return a value using `return` statement.

::::div{.hgrid}
:::div
```python
def f(x):
    result = x * x - x - 1
    return result
    # OR: return x * x - x - 1

# Call the function f
y = f(5)
print(y)  # 19

# Call again
y = f(10)
print(y)  # 89
```
:::
:::div
```python
# two parameters
def mean(x, y):
    return (x + y) / 2


print(mean(3, 4))  # 3.5
```
:::
::::

##

:::div{.bgred .px2 .py025 .br5}
Parentheses `()` are required to call a function. Omitting them is a common mistake.

When a function is called, correct number of arguments must be passed. It is an error to pass too many or too few arguments than what a function definition expects.
:::

## Creating a function — general form/syntax

```python
def function_name(param1, param2, ..., paramN):  # function header
    # function body
    statement1
    statement2
    .
    .
    statementN
```

- `def` is a Python keyword used to define functions
- Notice how statements are indented by spaces, typically 4 spaces. In Thonny, we can just use tab key once to indent by 4 spaces.

##

- When we define a function using `def` keyword:
    - it is not executed.  
    - Only the function name is created, which refers to the code block inside the function.
- When we call a function, the code block inside the function is :i[actually] executed.


## Why create our own functions?

- Functions allow code re-use; duplication of code can be avoided.
- They help organize code into sections, which makes programs easier to read and understand.
- They make programs easier to fix.


## Docstrings

A :sc[docstring] (documentation string) is a multiline (triple-quoted) string that we write after the header of a function to explain how the function works.

It is an important part of programming to write such documentation.  
You will be expected do so in your assignments.

##

```python
def euclidean_distance(x1, y1, x2, y2):
    """
    Computes Euclidean distance between two 2D points.

    Parameters:
        x1 (float): x-coordinate of first point  
        y1 (float): y-coordinate of first point
        x2 (float): x-coordinate of second point
        y2 (float): y-coordinate of second point

    Returns: the euclidean distance as a float
    """
    d = (x1 - x2) ** 2 + (y1 - y2) ** 2
    return d ** 0.5
```

## Types of Errors

:b[Syntax Errors]: When syntax is incorrect such as wrong punctuations, invalid characters, missing quotes or parentheses etc.  
Program does not run at all in the case of syntax errors.
```python
# The following code has Syntax error due to missing double-quotes:
x = 5
print("Square of x is)
print(x ** 2)
```

##

:::div{.ppt-f94}
:b[Runtime Errors], also called :sc[Exceptions], occur when there is a problem in the program during execution.  
All code executes until an exception occurs.
```python
# The following code produces NameError because 
# variable y was not created before it is used.
x = 5
print("Value of x is", x)
print("Square of x is", y ** 2)
```

:b[Semantic] or Logic errors are said to occur when a program executes without a problem but does not produce correct output as expected.

:sc[Debugging] is the process of finding and removing errors in a program.
:::

::divider


2.2 — Function calls, Defining functions, Types of Errors


## :span[Debugging in Thonny to understand expression evaluation]{.ppt-f80}

:::div{.ppt-f87}
In Thonny, we can use debugging features to understand how expressions are evaluated:

- To show variables and their values, go to menu "View -> Variables"
- First, run program in :i[debug mode] by clicking the "Debug current script" button (located next to the "Run current script" button and looks like a bug)
- Then, we have two options:
    - Run the program line-by-line using "Step over" button next to the "Debug" button
    - Run program going inside each expression using "Step into" button (located next to "Step over" button)
:::

## 

Try the following examples in Thonny and use debug:

```python
x = 7

# Increment value of variable x by 1
x = x + 1

#
y = x * x + 2 * (x + 1) + max(x + 1, 5)

# Calling print() with 4 arguments
print("x =", x, "y =", y)
```

## 

```python
x1 = 1.5
y1 = 2

print("Given points:", "(", x1, ",", y1, ")")

point1 = "(" + str(x1) + ", " + str(y1) + ")" 
print("Given points:", point1)
```


##  Boolean Values

Python has two values `True` and `False` of type `bool`, which are useful for expressing and storing   yes/no or true/false kind of data.

```python
>>> True
True
>>> False
False
>>> type(True)
<class 'bool'>
>>> type(False)
<class 'bool'>
```

## Comparison Operators

:sc[comparison operators], also known as :i[relational operators], are used to compare two values, such as numbers or string.  
The result of such comparison is always a `bool` value i.e. `True` or `False`.

:::div{.hgrid}
```python
# are these numbers equal?
>>> 10 == 10  
True
>>> 10 == 20
False
```
```python
>>> x = 5
>>> y = 10
>>> x == y
False
>>> x < y
True
>>> x > y
False
```
:::

##

```python
# A variable can store the result of a boolean expression 
# (just like we did for arithmetic expressions)
>>> x = 3
>>> is_positive = (x > 0)
>>> is_positive
True

>>> x = 5
>>> y = 5
>>> is_equal = (x == y)
>>> is_equal
True
```

## Boolean Expressions
A :sc[boolean expression] is an expression that evaluates to either `True` or `False`.
Examples above show how boolean expressions are created using comparison operators.

:::div{.p1 .br5 .bgred}
- Common error is using `=` (single equals sign) instead of `==` (double equals sign)
- `=` is the assignment operator, used to create variable and assign it a value
- `==` is a comparison operator used to check for equality between two values
:::


## List of comparison operators
- `x == y` — `True` if `x` is equal to `y`, otherwise `False`
- `x != y` — `True` if `x` is not equal to `y`, otherwise `False`
- `x < y` — `True` if `x` is less than `y`, otherwise `False`
- `x > y` — `True` if `x` is greater than `y`, otherwise `False`
- `x <= y` — `True` if `x` is less than or equal to `y`, otherwise `False`
- `x >= y` — `True` if `x` is greater than or equal to `y`, otherwise `False`
    

## Order of operations

All comparison operators (e.g. `==`, `!=`, etc.) have same priority and are evaluated from left to right.

All arithmetic and string operators have higher priority than comparison operators.

```python
>>> x = 5
# + operator will be evaluated before ==
>>> x + 1 == 6
True
```

##

::::div{.p1 .br5 .bggreen}
Write a program that takes an integer as input from the user and displays on your screen whether it is true or false that such integer is even.

:::div{.hgrid}
```output
Enter a number: 5
5 is an even number: False
```
```output
Enter a number: 8
8 is an even number: True
```
:::

```python
num = int(input("Enter a number: "))
# Write code below
```
::::

##

:::solution
```python
num = int(input("Enter a number: "))

# a number is even if remainder is 0 when it is divided by 2
is_even = (num % 2 == 0)

print(num, "is an even number:", is_even)

# without using extra variable:
# print(num, "is an even number:", num % 2 == 0)
```
:::


## Comparing strings
Comparison operators work for strings as well.  
The comparison is done :i[alphabetically] i.e. following a dictionary order

:::div{.hgrid}
```python
>>> "cat" == "cat"
True
>>> "cat" == "dog"
False
>>> "cat" != "Cat"
True
```
```python
# "c" appears before "d" alphabetically
>>> "cat" < "dog"
True

# A-Z appear before a-z alphabetically
>>> "cat" < "Dog"
False
```
:::

##

```python
# Objects of different types are always not equal
>>> "cat" == 123
False

# inequality is not allowed 
# between a number and str
>>> "cat" < 123
TypeError: '<' not supported between instances of 'str' and 'int'

# All of the above examples work the same when using variables
>>> s1 = "cat"
>>> s2 = "dog"
>>> s1 == s2
False
```


## Equality and floating point numbers

Consider following example:

```python
>>> x = 1.1 + 2.2
>>> x == 3.3  # why is this False?
False
```

- As we saw earlier, a floating-point number is stored with 64-bit :i[finite precision].
- This means that a number may not be stored as precisely as we would like.

## Correct way to check if two `float` values are equal

We should check if they are "close enough".

```python
>>> epsilon = 0.000001  # define how close two numbers need to be

>>> x = 1.1 + 2.2
>>> x
3.3000000000000003

# Check if x and 3.3 are within epsilon distance
>>> abs(x - 3.3) < epsilon
True
```

The epsilon value depends on the application and how much error we are willing tolerate.

## Logical Operators
Logical operators are useful to combine multiple conditions.

Logical operators take boolean expressions as operands and produce a result of type `bool` when evaluated.

Python has 3 boolean operators:
- `not` — a unary operator
- `and` — binary operator
- `or` — binary operator

##

Suppose `x` is a variable of type `bool`:
:::div{.code .p1 style="font-size: 0.75em;"}
| x     | not x |
|-------|---------|
| False | True    |
| True  | False   |
:::

`not x` evaluates to the opposite value of `x`.

## 

Suppose `x` and `y` are variables of type `bool`:
::::div{.hgrid}
:::div{.code .ppt-py2 .ppt-f80}
| x     | y     | x and y |
|-------|-------|---------|
| True  | True  | True    |
| True  | False | False   |
| False | True  | False   |
| False | False | False    |
:::
:::div{.code .ppt-py2 .ppt-f80}
| x     | y     | x or y |
|-------|-------|---------|
| True  | True  | True    |
| True  | False | True   |
| False | True  | True   |
| False | False | False    |
:::
::::

`x and y` evaluates to `True` if and only if both `x` and `y` are `True`.

`x or y` evaluates to `False` if and only if both `x` and `y` are `False`.

## Order of operations

In order of higher to lower priority: `not`, `and`, `or`

As usual, we can use parentheses in order to change the priority.

:::::div{.hgrid}
::::div{style="border-right: solid 1px black;"}
What does `b and not a or b` evaluate to if `a = False` and `b = True` ?
:::div{.code}
- b and not a or b
- True and not False or True
- True and True or True
- True or True
- True
:::
::::
::::div
What does `a and not (a or b)` evaluate to if `a = True` and `b = False` ? 
:::div{.code}
- a and not (a or b)
- True and not (True or False)
- True and not True
- True and False
- False
:::
::::
:::::

## Updated operator precedence table

::::div{.hgrid}
:::div{.ppt-f80}
| Operator                         | Associativity |
|----------------------------------|---------------|
| `()` (parentheses)               | -             |
| `**`                             | Right         |
| Unary `-`                        | -             |
| `*`, `/`, `//`, `%`              | Left          |
| Binary `+`, `-`                  | Left          |
| `==`, `!=`, `<`, `>`, `<=`, `>=` | Left          |
| `not`                            | -             |
| `and`                            | Left          |
| `or`                             | Left          |
| `=` (assignment)                 | Right         |
:::

You don't need to memorize all this, use parenthesis when in doubt!

::::



## Try these examples in Thonny

Change the value of x and see results of boolean expressions.

```python
x = 30
# Is an even number greater than 20?
print(x % 2 == 0 and x > 20)

x = 10
# Is an even number or a multiple of 5 greater than 20?
print(x % 2 == 0 or x % 5 == 0 and x > 20)

# Is a multiple of 2 or 5, greater than 20? 
print((x % 2 == 0 or x % 5 == 0) and x > 20)
```

##

:::div{.px1 .py025 .bggreen}
:b[Try it!]

Write a program that takes 3 integers $x, y, z$ as inputs and prints out `True` if $y$ is an even number between $x$ and $z$, `False` otherwise. Assume all 3 numbers will be different.

```python
# Retrieve inputs from the user
x = int(input("Enter the x: "))
y = int(input("Enter the y: "))
z = int(input("Enter the z: "))

# Write code below
```
:::

##

:::solution
```python
# Retrieve inputs from the user
x = int(input("Enter the x: "))
y = int(input("Enter the y: "))
z = int(input("Enter the z: "))

# check if y is even
is_even = y % 2 == 0

# check if y is between x and z
is_between = (x < y and y < z) or (z < y and y < x)

print(is_even and is_between)
```
:::


## Flow of execution

- Flow of execution refers to order in which statements (lines of code) in our program are executed.
- So far in our programs, each line was executed unconditionally.
- For most programs, it is not enough as we need to make choices or run code repeatedly.

We need to control the flow of execution in our programs.

## Control flow

The control flow of a program determines:
- Which parts of the code should always be executed
- Which parts should be executed only under certain conditions
- Which parts should be executed repeatedly

All of these can be achieved using control flow statements:
- `if` statement for conditional execution
- `for` and `while` loops for repeated execution


## :code[if] statement — to execute or not to execute

:::::hgrid{cols="1fr 4fr" margin="0 0" gap="2em"}
::::hgrid
:::div{.px1 .py025 .br5 style="background-color: white; white-space: pre;"}
:code[if]{.bgred}  :code[condition]{.bggreen}  :code[:]{.bgyellow}
`    `{code}:code[code block]{.bgblue}
:::
::::
:::div
- :code[condition]{.bggreen} must be a boolean expression
- :code[code block]{.bgblue} is one of more Python statements
- :code[code block]{.bgblue} is executed only if the condition is True, otherwise it is skipped.
:::
:::::
:::div{style="margin-top: -1em;"}
Notice space before code block. It is called :sc[indentation]. 

:div[Indentation is required to tell Python that the code belongs inside `if` statement.]{.bgred .px1 .py025}

Typically, 4 spaces are used for indentation. We can use :i[tab] key to indent.
:::

##

Try the following examples with different values for variables.

```python place="start"
x = 10  
if x > 0:
    print(x, "is positive")
```

```python place="start"
num = -5.2

absolute_num = num

if num < 0:
    absolute_num = -num
    
print("Absolute value of", num, "is", absolute_num)
```

##

```python
x = 1000
y = 123

min_value = x

if y < min_value:
    min_value = y
    
print("Minimum of", x, "and", y, "is", min_value)
```


## `if` statement with `else` part

`if` statements can have `else` part to make a choice between two code blocks.

:::::hgrid{cols="1fr 4fr" margin="0 0" gap="2em"}
::::hgrid
:::div{.px1 .py025 .br5 style="background-color: white; white-space: pre;"}
:code[if]{.bgred}  :code[condition]{.bggreen}  :code[:]{.bgyellow}
`    `{code}:code[code block:sub[1]]{.bggreen}
:code[else]{.bgred} :code[:]{.bgyellow}
`    `{code}:code[code block:sub[2]]{.bgblue}
:::
::::

:::div
- When :code[condition]{.bggreen} is `True`, :code[code block:sub[1]]{.bggreen} is executed
- Otherwise (:code[condition]{.bggreen} is `False`) and :code[code block:sub[2]]{.bgblue} is executed 
- The code blocks are also called :sc[branches] of the if-statement.
:::
:::::
##

```python
x = 10  # change this to -5 and run

if x > 0:
   print("x is positive.")
else:
    print("x is not positive.")
```

## 

::::div{.p2 .bggreen}
Write a program that takes an integer as input from the user and displays whether the number is even or odd.

:::hgrid
```output
Please enter a number: 5
The number 5 is odd
```
```output
Please enter a number: 8
The number 8 is even
```
:::
::::

##

:::solution
```python
num = int(input("Please enter a number: "))

# a number is even if remainder is zero when divided by 2
if num % 2 == 0:
    print("The number", num, "is even")
else:
    print("The number", num, "is odd")
```
:::


::divider


3.1 — Order of Expression Evaluation, Comparing Values, Conditional Execution

3.2 — if statement, for loop, Indexing & Slicing Strings


## Assignment 1

- Read the instruction pages
- Ask questions on Ed Discussion — posts can be made anonymous
    - Make the post private when you want to include code
- It is not enough that your solution passes all the given "public" tests
    - Make sure your solution will work for other values not given in the examples
    - Q1: use the blood type compatibility table to test your code with different values
    - Q2: Try different strings of lengths 1–10
    - Q3: For small `n`, you can use the given formula to verify your solution 

## 

:::div{.ppt-scale-1_25}
:b[What does this mystery function do?]{.ppt-f80}

<iframe width="800" height="420" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=def%20mystery%28s%29%3A%20%20%20%20%20%0A%20%20%20%20result%20%3D%20%22%22%0A%20%20%20%20for%20i%20in%20range%28len%28s%29%29%3A%0A%20%20%20%20%20%20%20%20result%20%3D%20s%5Bi%5D%20%2B%20result%0A%0A%20%20%20%20return%20result%0A%0Anew_string%20%3D%20mystery%28%22hello%22%29%0Aprint%28new_string%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

## Functions and return value `None`

Functions that do not have an explicit `return` statement, return a special value `None`.

##

The following 3 functions are equivalent because
- Python implicitly returns `None` for a function that does not  use a return statement
- if the `return` statement is used without a value, `None` is returned.

```python
def greeting():
    print("Welcome!")
```

:::hgrid
```python
def greeting():
    print("Welcome!")
    return
```
```python
def greeting():
    print("Welcome!")
    return None
```
:::

##  

::::hgrid
:::div
:b[Function that prints]
```python
def f(x):
    result = x * x - x - 1
    print(result)

f(5)  # No print here

y = f(10) + 10  # TypeError
```
Less flexible to use; cannot be used with other expressions
:::

:::div
:b[Function that returns a value]
```python
def f(x):  
    result = x * x - x - 1
    return result

print(f(5))  # print here

y = f(10) + 10  # works
```
More flexible to use; can be used with other expressions
:::
::::

It is usually advisable to keep functions "pure" and do `print()`, `input()` outside the functions when possible.

##

Try the problem "Max of three numbers" on Ed Lessons.


## Short Circuit Evaluation

The evaluation of a boolean expression with `and` and `or` stops as soon as the end result can be inferred.

For example, in the expression below evaluates to `False` no matter what `not (x >= 1 or y == 3)` evaluates to.

```python lineno=false
>>> 2 < 1 and not (x >= 1 or y == 3)
False
```

##

In general, for any expression with `and` operator:

```python lineno=false
left_operand and right_operand
```

if `left_operand` is `False`, Python does not evaluate `right_operand`.

##

Similarly, for any expression with `or` operator:

```python lineno=false
left_operand or right_operand
```

if `left_operand` is `True`, Python does not evaluate `right_operand`.

For example,
```python lineno=false
# Evaluates to True no matter what (x < 5) evaluates to
>>> 1 == 1 or (x < 5)
True
```

## Why is Short Circuit Evaluation useful?

- It can save time, e.g. when `right_operand` has a computationally expensive function call.
- It can avoid unnecessary errors as show below.

```python
>>> x = 0
>>> 1 / x < 0.5  # cannot divide a number by zero
ZeroDivisionError: division by zero

>>> x != 0 and 1 / x < 0.5
False
>>> x = 3
>>> x != 0 and 1 / x < 0.5
True
```

## 

:b[Common mistake when using logical operators]

:::hgrid
```python lineno=false
x == "a" or "b"  # Incorrect

x == "a" or x == "b"  # Correct
```

```python lineno=false
x == "a" and "b"  # Incorrect

x == "a" and x == "b"  # Correct
```
:::

## `while` statement

`while` statement is another way to repeatedly execute a block of code.

General format of a while loop:

:::div{.px1 .py025 .br5 style="background-color: white; width: 90%; white-space: pre;"}
:code[Initialize variables so that ] :code[condition]{.bggreen .ibox} :code[is True]
:code[while]{.b} :code[condition]{.bggreen .ibox} :code[:]{.b}
`    `{code}:code[code block]{.bgblue .ibox}
`    `{code}:code[update variables that affect ] :code[condition]{.bggreen .ibox}
:::

##

What `while` loop does:
1. Evaluate the :code[condition]{.bggreen .ibox}
2. If :code[condition]{.bggreen .ibox} evaluates to `False`, loop body is not executed.
3. If :code[condition]{.bggreen .ibox} evaluates to `True`, run the loop body (all indented lines of code)  
    a) In loop body we perform some task, :code[code block]{.bgblue .ibox}, and update variables that may change the :code[condition]{.bggreen .ibox} value  
    b) Go back to step 1  

##

```python
# a program to compute sum of first N numbers
N = 10

total = 0

i = 1  # Set value so that condition below is True 
while i <= N:  # Check if condition is True
    # main task of summing numbers:
    total = total + i  
    
    # update i, affects value of condition i <= N 
    i = i + 1

# print result outside the loop   
print(total)
```

##

It is a common mistake to forget updating the condition inside loop body.  

See what happens when you remove/comment out the line `i = i + 1` in the previous example.  

The loop will never end — an infinite loop!


## Augmented assignment statements
Augmented assignment is the combination, in a single statement, of a arithmetic operation and an assignment statement:

::::hgrid

```python
x = 3
y = 5

x += 1  # same as: x = x + 1
x += y  # x = x + y
x += x * y  # x = x + x * y

x -= 5  # x = x - 5

x *= 2  # x = x * 2
```
:::div
- Similarly, other operators exist: `/=`, `//=`, `%=`, `**=`.
- These are very useful, especially when updating the condition in while loop.
:::
::::

##  Loops with indefinite number of steps

So far we have seen loops that work with fixed number of steps.  

But while loop can be used for repeating code for unknown number of steps.

:::greenbox
Write a program to keep asking for password until correct password is entered.

Assume that correct (secret) password is `abcd1234`.
:::


##

```python
password = input("Enter password: ")

while password != "abcd1234":
    print("Incorrect password, try again!")
    
    password = input("Enter password: ")
    
# Below line executes only after the above loop ends,
# i.e. when the correct password was entered.
print("Login successful!")
```

## `for` vs `while` loops

- `for` loops are better when we want to go over a fixed sequence such as a string or a sequence of numbers
- `while` loop is more flexible as it allows arbitrary conditions and number of steps. e.g. do something until user enters correct data


## Importing modules
A :sc[module] is a Python file (typically a `.py` file) containing function definitions, statements, etc.

Many modules such as `math` and `random` are already installed with Python.

## 

Using `import` statement, we can use functions, variables etc. from a module in our program:

```python
import math

# Call a function defined in a module using dot operator
x = math.sqrt(16)
print(x)

y = math.sin(math.pi / 2)
print(y)
```

##

Another way to import functions, variables from the module:
```python
from math import sqrt, sin, pi

# Now, we can call sqrt and sin without the "math." prefix
x = sqrt(16)
print(x)

y = sin(pi / 2)
print(y)
```

## 

Use `help()` function in Python Shell to see list of all function contained in `math` module:
```python lineno=false
>>> import math
>>> help(math) # will display a long doc, not showing here

>>> help(math.sqrt) # show help on a specific function
Help on built-in function sqrt in module math:

sqrt(x, /)
    Return the square root of x.
```


## `random` module
In Python, we can generate random numbers using the `random` module.

The module provides us with a lot of different functions but for the moment we’ll focus on the following:
- `random()` – It returns a random float value between $0.0$ (inclusive) and $1.0$ (exclusive)
- `randint(x, y)` – It returns a random integer between x and y, both included.

##

Each time we execute these functions, we will get a different value, try it!

```python
import random

print(random.random())  # 0.12826246225939641

print(random.randint(1, 10))  # 9
```


##

:::greenbox
Try the problem "Guessing Game" on Ed Lessons.
:::

::divider


4.1 — return vs. print, while statement, Modules


## `in` operator (membership operator)

- In Python `in` is a keyword.
- The `in` and `not in` operators test for membership.
- We can use them with strings to test if one string is a substring of another. This operation is case-sensitive.

```python
s = "Pineapple"

print("app" in s)  # True
print("pine" in s)  # False

print("x" not in s)  # True
print("P" not in s)  # False
``` 

##

:::greenbox
Try the problem "Remove Duplicates" on Ed Lessons.
:::

##

:::greenbox
Try the problem "Benchpress" on Ed Lessons.
:::

## String methods

A :sc[method] is similar to a function except that a method is :i[always] called on an object:

:::div{.px1 .py025 .code .br5 style="background-color: white; width: auto; white-space: pre;"}
object.method_name(argument1, argument2, ...)
:::

##

`str` type has several methods that we can call on a string object:
```python
print("hello".upper())  # calling method upper() on the string "hello"
# HELLO

message = "hello"
print(message.upper())  # using variable that refers to string
# HELLO

message = 10
print(message.upper())  # upper() only available for str objects
# AttributeError: 'int' object has no attribute 'upper'
```

## Useful string methods

```python
s = "Luke, I am your father"

# s.lower() : returns a copy of s, but with all lower case letters.
print(s.lower())
# luke, i am your father

# s.upper() : returns a copy of s, but with all upper case letters.
print(s.upper())
# LUKE, I AM YOUR FATHER
```

##

```python
s = "Luke, I am your father"
# s.replace(old, new) : returns a copy of s with all occurrences of 
# the substring old replaced by new.
print(s.replace("am", "am not"))
# Luke, I am not your father

# replace space with empty string
print(s.replace(" ", ""))
# Luke,Iamyourfather
```

## 

```python
s = "banana"
# s.count(c) : returns the number of non-overlapping 
# occurrences of substring c in s.
print(s.count("na"))
# 2

# s.find(c) : returns the index where the substring begins in s begins. 
# If c is not a substring of s, then -1 is returned.
print(s.find("an"))
# 1

print(s.find("naa"))
# -1
```

## :style{.ppt-f90}

```python
x = 1
y = 2.5
z = 3.14
name = "Reza"

# fmt.format(a1, a2, ...):
# returns a string where the placeholders {} in format string fmt
# are replaced by args a1, a2, etc.

print("x = {}, y = {}".format(x, y))
# x = 1, y = 2.5

print("Point: ({}, {}, {})".format(x, y, z))
# Point: (1, 2.5, 3.14)

print("Welcome {}!".format(name))
# Welcome Reza!
```

## Formatted Strings

```python
x = 1
y = 2.5
z = 3.14
name = "Reza"

print(f"x = {x}, y = {y}")
# x = 1, y = 2.5

print(f"Point: ({x}, {y}, {z})")
# Point: (1, 2.5, 3.14)

print(f"Welcome {name}!")
# Welcome Reza!
```

## Example

In just one expression, compare if two strings `s1` and `s2` are equal in a case-insensitive manner.

```python
s1 = "Hello Everyone"
s2 = "hello everyone"

is_equal = s1.upper() == s2.upper()

# OR
# is_equal = s1.lower() == s2.lower()

print(is_equal)  # prints True
```

## `break` statement

`break` statement can be used to terminate a loop before it normally ends.  
After a `break` statement is executed, no other code inside the loop is executed.

:::hgrid
```python
for i in range(10):
    if i > 5:
        break
    print(i)
    
print("Bye!")
```
```output
0
1
2
3
4
5
Bye!
```
:::


## 

:::greenbox
Write a function `is_prime` that takes an integer as argument and returns `True` if the number is prime, otherwise returns `False`.
To check if a number `n` is prime:
- Assume `n` is prime
- Divide `n` by each number `i` from `2` to `n-1`
    - if `n` is divisible by any `i` then `n` cannot be not prime

In other words, if `n` is not divisible by all `i`'s then `n` is prime.
:::

##

:::solution
```python
def is_prime(num):
    prime = True

    if num < 2:
        prime = False
    else:
        for i in range(2, num):
            if num % i == 0:
                prime = False
                break

    return prime

print(is_prime(7))  # True
print(is_prime(21))  # False
```
:::

## 

```python
password = input("Enter password: ")

while password != "abcd1234":
    print("Incorrect password, try again!")
    password = input("Enter password: ")

print("Login successful!")
```

:::greenbox
Change above program so that it keeps asking email and password until both are correct.  
Password comparison must be case-sensitive, while email comparison should be case-insensitive.  
For comparison, just choose any email, password that you like.
:::

##

:::solution
```python
email = input("Enter email: ")
password = input("Enter password: ")

while email.lower() != "abcd@gmail.com" or password != "1234":
    print("Incorrect email or password, try again!")
    
    email = input("Enter email: ")
    password = input("Enter password: ")
    
# If we reach this line it means both email and password were correct
print("Login successful!")

```
:::

## Using `break` in a `while` loop

We can simplify the login example using a `break` statement:

```python
while True:
    email = input("Enter email: ")
    password = input("Enter password: ")
    if email.lower() == "abcd@gmail.com" and password == "1234":
        break
    print("Incorrect email or password, try again!")

print("Login successful!")
```

## `continue` statement

`continue` statement is useful to skip some steps in a loop.

After a `continue` statement is executed, code that follows the statement is skipped and execution continues from the next step of the loop.

```python
for i in range(1, 50):
    if i % 2 == 0 or i % 3 == 0:
        continue
    print(i)
```
```output
1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
```

::divider

4.2 — String methods, break & continue statements



## Controlling the flow of execution with `return` statement

As we have seen, `return` statement allows us to return a value from a function back to the code that calls the function.

But at the same time return statement also ends execution of the function.  

##

When return statement is executed, no further code in the function gets executed.

:::hgrid
```python
def display(message):
    print("*** " + message + " ***")
    return
    print("This will never be displayed")
    
    
display("hello")
```

```output
*** hello ***
```
:::

`return` can be very useful when placed inside an `if` statement if we want to exit from the function under certain conditions.


## 
 
Using return statement, we can simplify the prime number example:

:::hgrid
```python
# We saw this before
def is_prime(num):
    prime = True

    if num < 2:
        prime = False
    else:
        for i in range(2, num):
            if num % i == 0:
                prime = False
                break

    return prime
```

```python
# Simplified version
def is_prime(num):
    if num < 2:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False

    return True
```
:::

##

:::redbox
:b[Important]: we must make sure that all branches/cases in the function return the correct values.  

In previous example, if we forget the last return statement in the simplified `is_prime` function, `return None` will happen implicitly, which would be incorrect.
:::

## Be careful — incorrect indentation changes logic (1)

:::hgrid{.ppt-f90 margin="0 0"}
```python
def remove_spaces(s):
    result = "" 
    for i in range(len(s)):
        letter = s[i]
        if letter != " ":
            result = result + letter

    return result
```
```python
def remove_spaces(s):
    result = "" 
    for i in range(len(s)):
        letter = s[i]
    if letter != " ":
        result = result + letter

    return result
```
:::

## Be careful — incorrect indentation changes logic (2)

:::hgrid{.ppt-f90 margin="0 0"}
```python
def remove_spaces(s):
    result = "" 
    for i in range(len(s)):
        letter = s[i]
        if letter != " ":
            result = result + letter

    return result
```
```python
def remove_spaces(s):
    result = "" 
    for i in range(len(s)):
        letter = s[i]
        if letter != " ":
            result = result + letter

        return result  # what will this do?
```
:::

## ASCII code and special characters

::div[Recall ASCII table from a previous lecture:]{style="margin: 0 auto;" .ppt-f80}

::image{style="margin: 0 auto; width: 70%;" src="module-1/ASCII-Table.png"}  

##
Python has built-in functions to convert ASCII code (decimal) to/from a single character.

```python
print(ord("a"))  # 97, the ASCII code for letter "a"
print(ord("A"))  # 65
print(ord("$"))  # 36

print(ord("hi"))  # doesn't work for more than one character
# TypeError: ord() expected a character, but string of length 2 found

print(chr(70))  # F, the character for ASCII code 70

print(chr(103))  # g
```

##

:::greenbox
Write a program that  shifts each letter in a string to the left by 3 steps according to ASCII table.  
i.e. :code[A → >, B → ?, C → @, D → A, E → B], etc.
:::


```python
word = "Python"

result = ""
for i in range(len(word)):
    code = ord(word[i])  # Get ASCII code for the letter
    code = code - 3  # Shift code by 3
    # Get letter for the code and add it to result:
    result = result + chr(code)  
    
print(result)  # Mvqelk

```

## 

Text is stored in a file as a sequence of character codes.

:::hgrid{margin="1em 0" gap="1em"}
```python lineno=false 
cat dog
```
::seqbox{text="99,97,116,32,100,111,103" margin="0" w="2.5" h="2"}
:::

Multiple lines in text:
:::hgrid{margin="1em 0" gap="1em"}
```python lineno=false
cat
dog
```
::seqbox{text="99,97,116,10,100,111,103" margin="0" w="2.5" h="2"}
:::

The :em[newline character], which represents "enter" or "return" key, is also stored when text contains multiple lines.

## Escape characters

There are special characters, which we may not directly include in a string, e.g.:
- :i[newline character]: This is the character representing "enter" or "return" key.
- :i[tab character]: This is the character representing "tab" key.

Such special characters can be used in a string using escape characters.

## 

```python
# Trying to enter a newline character directly fails:
message = "Hello
world"
```

```output
    message = "Hello
                   ^
SyntaxError: EOL while scanning string literal
```

## 

To include a newline character in a string we can use the escape character `\n` in the string:

:::hgrid
```python
message = "hello\nworld"
print(message)
```

```output
hello
world
```
:::

`\n` is stored as a single character even though it looks like two.

```python lineno=false
print(ord("\n"))  # 10
```

##

Another escape character is `\t` which represents the tab character.  
It is useful as a separator when displaying values:

:::hgrid
```python
# print uses space as separator by default
print("Khalid", 85)
print("Reza", 90)

# Using tab as separator
print("Khalid", 85, sep="\t")
print("Reza", 90, sep="\t")
```

```output
Khalid 85
Reza 90
Khalid	85
Reza	90
```
:::

## Controlling print() function

In previous example, we used a :sc[keyword argument] `sep=` to tell print which separator to use between values.  

Unlike the usual arguments, keyword arguments are given in the form `name=value`; in the example `sep` is the name of argument and `"\t"` is the value.

```python
# separator can be any string
print("Alice", 90, 3.14, sep=",")
# Alice,90,3.14
```

##

```python
print("Alice", 90, 3.14, sep="|")
# Alice|90|3.14

# even longer than one character
print("Alice", 90, 3.14, sep="-----")
# Alice-----90-----3.14

print("Alice", 90, 3.14, sep="")  # No separator!
# Alice903.14
```

##

By default, `print()` function displays a newline  character `\n` at end of line.  

:::hgrid
```python
print("Good", "morning")
print()  # no arguments, just prints "\n"
print(123, 3.14)
```

```output margin="-1em 0 0 0"
Good morning

123 3.14
```
:::

##

We can change the `end` character using another keyword argument to `print()` function, `end=`.  

:::hgrid
```python
print("A sequence of numbers:")
print(1, end=",")
print(4, end=",")
print(9, end=",")
```

```output
A sequence of numbers:
1,4,9,
```
:::

##

`end=` is useful in a loop:

```python
N = 10
for i in range(N):
    print(i*i, end=", ")  # comma and a space
```

```output
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 
```

:::greenbox
Change the above example to not print the last comma. E.g.,

```output
0, 1, 4, 9, 16, 25, 36, 49, 64, 81
```
:::

##

:::solution
```python
N = 10
for i in range(N):
    if i == N - 1:
        print(i * i)
    else:
        print(i * i, end=", ")
```
:::

## Multiline strings

Using `\n`, we can create a single string that contains all of the following lines:

```python
shopping_list = "Shopping list\n- Milk\n- Eggs\n- Apples\n"
print(shopping_list)
```

```output
Shopping list
- Milk
- Eggs
- Apples
```

##

Python provides a better create multiline strings using :i[triple quotes]: `'''` or `"""`.

```python
>>> shopping_list = """Shopping list
- Milk
- Eggs
- Apples
"""
>>> shopping_list
'Shopping list\n- Milk\n- Eggs\n- Apples\n'
```

## Nested Loops

We can have a for/while loop inside other for/while loops.

This is useful when we have two sequences and we need all combinations/pairs of items from the sequences.

##

:::greenbox
Write a program that prints all pairs of numbers that sum to $7$ when two six-sided dice are rolled.
:::

:::hgrid
```python
# outer loop for first die d1:
for d1 in range(1, 7):  
    # inner loop for second die d2
    for d2 in range(1, 7):
        if d1 + d2 == 7:
            print(d1, d2)
```

```output
1 6
2 5
3 4
4 3
5 2
6 1
```
:::


## 

:::greenbox
Write a program that takes two string—one with consonants and other with vowels—and combines each consonant with every vowel to print a syllable.
:::

:::hgrid{margin="0"}
```python
consonants = "bdfghjklmn"
vowels = "aeiou"
```
```output
ba be bi bo bu 
da de di do du 
fa fe fi fo fu 
ga ge gi go gu 
ha he hi ho hu 
ja je ji jo ju 
ka ke ki ko ku 
la le li lo lu 
ma me mi mo mu 
na ne ni no nu
```
:::

##

:::solution
```python
consonants = "bdfghjklmn"
vowels = "aeiou"

for i in range(len(consonants)):
    for j in range(len(vowels)):
        syllable = consonants[i] + vowels[j]
        print(syllable, end=" ")
    print()  # to start printing from next line

```
:::

## Lists

- A list is like a container that holds a sequence of objects.
- Objects contained in a list are called :sc[elements] or :sc[items].
- Lists are ordered! The order in which the items are stored in the list matters.
- Each item is associated with an index (index $0$: first item, index $1$: second item, etc.)

## Creating a list

A list is created using square brackets, with each item separated by a comma.

```python
prime_numbers = [2, 3, 5, 7, 11, 13]
print(prime_numbers)
# [2, 3, 5, 7, 11, 13]

print(type(prime_numbers))
# <class 'list'>
```

##
A list can contain items of any type. For example we can have a list of strings:

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

# Number of items in the list
print(len(days))  # 7

empty_list = []
print(len(empty_list))  # 0
```

A list can contain any number of items, from zero to as many as the computer's memory allows.

##
A list can contains objects of different types.

```python
# list with mixed types
numbers = [1, 'two', 3.75]
```

Items of a list don't need to be unique.

```python
# list with duplicate values
numbers = [5, "five", 5]
```

## Why use a list?

```python
# Suppose we want to store grades for multiple students

grades1 = 80
grades2 = 100
grades3 = 65
# ...
# How many variables?!!

# Use just one variable name "grades"
grades = [80, 100, 65]
```

## Indexing a list

We can access an item inside a list using indexing (square brackets), just as we did for strings.

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
first_day = days[0]
second_day = days[1]
last_day = days[6]
print(first_day, second_day, last_day)  # Mon Tue Sun

# No item at index 7
print(days[7])  
# IndexError: list index out of range
```

##
```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

# Negative indexing can be used as well
print(days[-1], days[-2])  # Sun Sat

numbers = [1, 'two', 3.75]
print(numbers[0] + numbers[2])  # 4.75

print(numbers[0] + numbers[1])
# TypeError: unsupported operand type(s) for +: 'int' and 'str'
```

## Modifying the content of a list

We can modify the content of a list after it has been created.

We can change a single item using its index and the assignment operator.

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
days[0] = "Sun"
print(days)
# ['Sun', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']

days[7] = "No such day"
# IndexError: list assignment index out of range
```



## 

`for` loops are very useful for looping through all the items in a list.

```python
# compute an average of grades
grades = [85, 78.5, 98, 75, 100]
total = grades[0] + grades[1] + grades[2] + grades[3] + grades[4] 
avg = total / 5
print(avg)  # prints 87.3
```
:::hgrid{margin="0.5rem 0"}
For instance, we could use a for loop to compute the average of grades.
```python
grades = [85, 78.5, 98, 75, 100]

total = 0
for i in range(5):
   total += grades[i]

avg = total / 5
print(avg)  # 87.3
```
:::

##

Generalized version:
```python
grades = [85, 78.5, 98, 75, 100]

total = 0
N = len(grades) 
for i in range(N):
   total += grades[i]

avg = total / N
print(avg)  # 87.3
```

##

:::greenbox
Try the problem "Dot product" on Ed Lessons.
:::


##

:::greenbox
Try the problem "DNA Cut-site" on Ed Lessons.
:::

##

:::greenbox
Try the problem "Palindrome" on Ed Lessons (from last week).
:::

:::hgrid{margin="1em 0" gap="4em"}
::seqbox{text="a,b,b,a" margin="1em 0"}
::seqbox{text="a,b,c,b,a" margin="2em 0"}
:::

:::hgrid{margin="0" gap="4em"}
::seqbox{text="a,b,a,a" margin="1em 0"}
::seqbox{text="a,b,c,c,a" margin="2em 0"}
:::

##

:::greenbox
Try the problem "Smallest and largest divisors" on Ed Lessons (from last week)..
:::


::divider


5.1 — Controlling print(), Nested Loops, Lists


## Scope of variables

- A variable name only exists inside the body of the function in which it is created.
    - It does not exist outside the function or in any other functions.

:::hgrid
```python
def f():
    x = 3
    print("In f(), x =", x)
    
f()
print(x)
```
```output
In f(), x = 3
NameError: name 'x' is not defined
```
:::

##

- The :sc[scope] of a variable consists of parts of the program where the variable name exists and can be used.
- Each function has its own :sc[local scope], which other functions cannot access.
- :sc[global scope] consists of names  accessible by the entire module (Python file).

A variable created inside a function is called a :sc[local variable].  

A variable created outside any function is called a :sc[global variable].

##

:::hgrid
```python
def f():
    x = 3  # local variable
    # local x is used below!
    print("In f(), x =", x)  


x = 100  # global variable
f()
print(x)  # global x is used
```
```output
In f(), x = 3
100
```
:::

- As we saw above, it is possible to create a local variable with the same name as a global variable.  
- These are considered two different variables, and inside the function only the local one will be used.

## 

:::hgrid
```python
def f():
    # global x is used below!
    print("Inside f(), x =", x)


x = 100  # global variable
f()
print(x)
```
```output
Inside f(), x = 100
100
```
:::

What will happen if the global variable `x` is created after the function call `f()`?


## How variable name is looked up?
- Inside a function, when a name is used:
    - First, name is searched within the function (local scope) to see if it exists.
    - If name is not found in the function, it is searched globally
- Outside a function, name is simply searched globally
- If a name cannot be found anywhere (local or global scope), we get `NameError` complaining that the name is not defined.

##

What will be printed in each case?

:::hgrid{margin="0" gap="5em"}
```python
def f():
    y = 5
    print(x)

x = 10
f()
```
```python
def f():
    x = 5 
    print(x)

x = 10
f()
print(x)
```
:::

##

::::solution
:::hgrid{gap="5em"}
```output
10
```
```output
5
10
```
:::
::::


##

:::div{.ppt-scale-1_25}
:b[Function parameters are also local to the function.]{.ppt-f80}
<iframe width="800" height="380" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=def%20f%28x%29%3A%0A%20%20%20%20print%28%22In%20f%28%29,%20x%20%3D%22,%20x%29%0A%20%20%20%20return%20x%20*%20x%0A%0Ax%20%3D%2010%0Ay%20%3D%20f%28x%29%0Aprint%28f%22Global,%20x%20%3D%20%7Bx%7D,%20y%20%3D%20%7By%7D%22%29&codeDivHeight=400&codeDivWidth=360&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

##

:::div{.ppt-scale-1_25}
<iframe width="840" height="420" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=def%20f%28x%29%3A%0A%20%20%20%20x%20%3D%203%0A%20%20%20%20print%28f%22In%20f%28%29,%20x%20%3D%20%7Bx%7D,%20y%20%3D%20%7By%7D%22%29%0A%20%20%20%20return%20x%20*%20y%0A%0Ax%20%3D%2010%0Ay%20%3D%205%0Az%20%3D%20f%28x%29%0Aprint%28f%22Global,%20x%20%3D%20%7Bx%7D,%20y%20%3D%20%7By%7D,%20z%20%3D%20%7Bz%7D%22%29&codeDivHeight=400&codeDivWidth=440&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::


## Best Practice
- Try to avoid using global variables within functions when possible.
    - It is okay to use variables that don't change (e.g. constants such as $\pi$)
    - It is also okay to use modules inside functions 


## Lists — Concatenation `+` and Replication `*`

```python
# lists a and b are joined to produce a third list c:
a = [1, 2]
b = [10, 11, 12]
c = a + b
print(c)
# [1, 2, 10, 11, 12]

a = [1, 2]
# resulting list consists of repeated items of list a:
c = a * 3 
print(c)
# [1, 2, 1, 2, 1, 2]
```


## membership operators: `in` and `not in`

We can use them to test if an object is present in a list.

```python
a = [1, 2]
b = [10, 11, 12]

print(1 in a)  # True
print(11 in a) # False
print(5 not in b) # True

x = 3.14
print(x in a or x in b)  # False
```

##

`in`/`not in` operators are very useful in simplifying code:

:::hgrid
```python
# Instead of long conditions like this:
if x == 5 or x == 7 or x == 10:
    # do something
```
```python
# Now we can do:
if x in [5, 7, 10]:
    # do something
```
:::


## Slicing a list

Similar to strings, we can also get a sub-list — parts of a list — using slice notation. Slicing creates a new list.

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

print(days[2:5])
# ['Wed', 'Thu', 'Fri']

print(days[:6:2])
# ['Mon', 'Wed', 'Fri']
```

##

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

# Make a copy of the whole list
print(days[:])
# ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']

# Makes a reversed copy of the list
print(days[::-1])
# ['Sun', 'Sat', 'Fri', 'Thu', 'Wed', 'Tue', 'Mon']
```

## Iterating through a list

We can either use an index or loop directly over items in a list:

:::hgrid{margin="0"}
```python
def average(nums):
    total = 0

    for i in range(len(nums)):
       total += nums[i]

    return total / len(nums)

grades = [85, 100, 98, 75]
print(average(grades))
```
```python
def average(nums):
    total = 0

    for x in nums:
       total += x

    return total / len(nums)

grades = [85, 100, 98, 75]
print(average(grades))
```
:::

##

But when we need to modify a list inside a loop we have to use an index:

```python
def add_bonus(grades, bonus):
    """ Add bonus to each grade in grades list
        (grade should not exceed 100)    
        Returns: None
    """
    for i in range(len(grades)):
        grades[i] = min(grades[i] + bonus, 100)
        
        
assignment_grades = [55, 60, 67, 97]
add_bonus(assignment_grades, 5)
print(assignment_grades)  # [60, 65, 72, 100]
```

## Built-in functions that work with lists

```python
grades = [90, 70, 60.5, 70, 80]

# len(x): 
#   Returns the number of items in the list x.
print(len(grades))  # 5

# sum(x): 
#   Returns the sum of all the numbers in list x.
#   A TypeError occurs when some item is not a number.
print(sum(grades))  # 370.5
```

##

```python
grades = [90, 70, 60.5, 70, 80]

# min(x) / max(x) : 
#   Returns the smallest/largest item in the list x.
#   A TypeError occurs if the items cannot be compared.

print(min(grades))  # 60.5

print(max(grades))  # 90

print(min(["90", 70, 60.5, 70, 80]))
# TypeError: '<' not supported between instances of 'int' and 'str'
```

## List methods
Python has several methods that we can call on a list object:

```python
# list.append(x): Adds the item x to the end of the list

grades = [90, 70, 60.5, 70, 80]
grades.append(100)
print(grades)  # [90, 70, 60.5, 70, 80, 100]

grades.append("30")
print(grades)  # [90, 70, 60.5, 70, 80, 100, '30']

grades.append(False)
print(grades)  # [90, 70, 60.5, 70, 80, 100, '30', False]
```

## 

:b[Example:]

```python
def filter_values(nums, threshold):
    ''' Return a new list to include numbers from 
        the list nums that are above threshold
    '''
    new_list = []
    
    for n in nums:
        if n > threshold:
            new_list.append(n)

    return new_list

print(filter_values([3, 1, 2, 5, 4], 3))  # [5, 4]
print(filter_values([3, 1, 2, 5, 4], 5))  # []
```

##

```python
# list.insert(i, x): Adds the item x to the list at index i

grades = [90, 70, 60.5, 70, 80]
grades.insert(0, 100)
print(grades)  # [100, 90, 70, 60.5, 70, 80]

# insert() works even when index is greater than length of list
grades = [90, 70, 60.5, 70, 80]
grades.insert(10, "B+")
print(grades)  # [90, 70, 60.5, 70, 80, 'B+']
```

##

```python
# list.remove(x): 
#   Removes the first occurrence of the item x in the list. 
#   A ValueError occurs if there is no such item.

grades = [90, 70, 60.5, 70, 80, 'B+']
grades.remove(70)
print(grades)  # [90, 60.5, 70, 80, 'B+']

grades.remove("B+")
print(grades)  # [90, 60.5, 70, 80]

grades.remove(60)
# ValueError: list.remove(x): x not in list
```

##

```python
# list.pop(i): 
#   Removes and returns item at index i 
# list.pop(): 
#   Removes and returns the last item from the list

grades = [90, 70, 60.5, 70, 80, 'B+']
last_item = grades.pop()
print(last_item)  # B+
print(grades)  # [90, 70, 60.5, 70, 80]

second_item = grades.pop(1)
print(second_item)  # 70
print(grades)  # [90, 60.5, 70, 80]
```

##

```python
# list.count(x) : 
#   Returns the number of occurrences of the item x. 

grades = [90, 70, 60.5, 70, 80, 'B+']
print(grades.count(70))  # 2
print(grades.count("B+"))  # 1
print(grades.count(60))  # 0
```

##

```python
# list.index(x) : 
#   Returns the index of the first occurrence of item x in list. 
#   A ValueError occurs if item x is not found in list.

grades = [90, 70, 60.5, 70, 80, 'B+']

print(grades.index(70))  # 1
print(grades.index(60)) # ValueError: 60 is not in list
```

##

```python
# list.extend(sequence) : 
#   Extend list by appending items from the sequence.

grades = [90, 70, 60.5, 70, 80]

grades.extend([100, 95])
print(grades)  # [90, 70, 60.5, 70, 80, 100, 95]

grades.extend("cat")
print(grades)
# [90, 70, 60.5, 70, 80, 100, 95, 'c', 'a', 't']
```

## Lists and Strings

There are built-in functions and string methods that allows us to transform strings to/from lists.

```python
# list(seq): built-in function which converts a sequence (such as
#   a string or a list) into a list

fruit = "apple"
letters = list(fruit)
print(letters)  # ['a', 'p', 'p', 'l', 'e']
```
##

```python
# s.split(): Breaks the string s using whitespace
#   (spaces, tab character and newline) as the separator and
#   returns a list of strings containing the separated parts

data = "Red Green Blue"
names = data.split()
print(names)  # ['Red', 'Green', 'Blue']

# Multiple spaces are also removed
data = "  Red    Green     Blue  "
names = data.split()
print(names)  # ['Red', 'Green', 'Blue']
```

##

```python
data = "Red\tGreen\tBlue" # separated by tab
names = data.split()
print(names)  # ['Red', 'Green', 'Blue']

data = """Red
Green
Navy Blue"""
names = data.split()
print(names)  # ['Red', 'Green', 'Navy', 'Blue']
```

##

```python
# s.splitlines(): Breaks a multi-lines strings into separate lines
#   and returns a list containing those lines.

data = """Red
    Green
Navy Blue
"""
names = data.splitlines()
print(names)  # ['Red', '    Green', 'Navy Blue']
```

##

:::hgrid{margin="0 0 0 -1em"}
```python
# s.strip():  Return a copy of the string with 
#     leading and trailing whitespace removed.
# s.lstrip(): removes leading whitespace only 
# s.rstrip(): removes trailing whitespace only 

name = "    Green    "
print("|" + name + "|") 
print("|" + name.strip() + "|")
print("|" + name.lstrip() + "|")
print("|" + name.rstrip() + "|")
```

```output
|    Green    |
|Green|
|Green    |
|    Green|
```
:::

##

:::hgrid{margin="0 0 0 -2em" .ppt-f95}
```python
# s.strip(chars):  Return a copy of the string 
# with leading and trailing chars removed.
# s.lstrip(chars): removes leading chars only 
# s.rstrip(chars): removes trailing chars only 

text = "...#some . text   #..."

print(text.strip("."))
print(text.lstrip("."))
print(text.rstrip("."))

# multiple chars to remove
print(text.strip(". #"))
```

```output
#some . text   #
#some . text   #...
...#some . text   #
some . text
```
:::


##

```python
# s.split(sep): Breaks the string s using the separator string sep
#   and returns a list of strings containing the separated parts

data = "Red,Green,Blue"
names = data.split(",")
print(names)  # ['Red', 'Green', 'Blue']

data = "Red,   Green,   Blue"
names = data.split(",")
print(names)  # ['Red', '   Green', '   Blue'] 
# notice space in strings above
```

##

```python
# sep.join(L): joins all the strings in the list L using 
#   the string sep and returns the joined string.

names = ['Red', 'Green', 'Blue']
joined = " ".join(names)
print(joined)  # Red Green Blue

# a comma
joined = ",".join(names)
print(joined)  # Red,Green,Blue
```

##

```python
# a comma and a space
names = ['Red', 'Green', 'Blue']
joined = ", ".join(names)
print(joined)  # Red, Green, Blue

# empty string, no separator
letters = ["a", "p", "p", "l", "e"]
joined = "".join(letters)
print(joined)  # apple
```

##

:::greenbox
Try the problem "Parsing a string" on Ed Lessons.
:::

##

:::greenbox
Try the problem "Puzzle: Switching 100 light bulbs" on Ed Lessons.
:::


::divider


5.2 — Scope of variables, List operations


## Tuples

- A tuple is an ordered collection of objects, like lists.
- A tuple is :i[immutable]. A tuple object cannot be modified after it is created.
- We create a tuple using parentheses `()`.

```python
tup = (1, 2, 3)
print(type(tup))  # <class 'tuple'>

# tuple with only one item
tup = (10,)  # comma is required!
print(tup, type(tup))  # (10,) <class 'tuple'>
```

##

We can use `tuple` function to convert other sequences such as lists and strings into a tuple.

```python
word = "apple"
tup = tuple(word)
print(tup)
# ('a', 'p', 'p', 'l', 'e')

primes = [2, 3, 5, 7]
primes = tuple(primes)
print(primes)
# (2, 3, 5, 7)
```

## Tuples are immutable

Items cannot be added, removed or changed in a tuple.

Therefore, unlike lists, none of the operations that modify a tuple are allowed.

```python
x = (1, 1, 2, 3, 5)
x[3] = 100
# TypeError: 'tuple' object does not support item assignment
```

## 

Assigning a new object to a variable does not affect/modify the current object the variable refers to.

```python
x = (1, 1, 2, 3, 5)

# This does not modify the above tuple object so
# it is allowed
x = (1, 2, 3)  
```

##

In general, operations that do not modify a tuple are available.

```python
tup = (45, 23, 'abc') 

# Indexing and slicing work the same way as lists.
print(tup[1])
# 23
print(tup[1:])
# (23, 'abc')

print(len(tup))  # number of items in a tuple
# 3
```

Similary `min()`, `max()`, and `sum()` functions work with tuples.

##

```python
tup = (45, 23, 'abc') 

# Following methods are available for tuples
print(tup.index("abc"))
# 2

print(tup.count(23))
# 1
```

##

Since a tuple is a sequence, we can use it in a `for` loop just like a list:
:::hgrid
```python
numbers = (10, 20, 30)

for n in numbers:
    print(n)
```
```output
10
20
30
```
:::

## Why use tuples?

If lists are more flexible than tuples, why should we use tuples?

- Immutability is useful to avoid changing data by mistake.
- We can use tuples as elements of sets and as keys in a dictionary.
- Programs are a bit faster when working with tuples.

##

:::greenbox
Try the problem "Euclidean distance using list/tuple" on Ed Lessons.
:::

## Object Identity

- Each object is assigned an :sc[ID] at its creation (think of a memory address).
- This ID is unique and constant for this object as long as the object exists.
- The built-in function `id()` can be used to retrieve the ID of an object.


```python
x = 1234
y = x
# x and y both refer to the same object, 
# therefore the IDs are the same.
print(id(x) == id(y))  # True
```

##

```python
# x and y point to two different objects, 
# therefore we expect x and y to have different IDs.
x = 1234
y = 5678
print(id(x) == id(y))  # False

# x and y point to two different objects (with the same value),
# therefore we expect x and y to have different IDs.
x = int("1234")  # integer 1234
y = int("12" + "34")  # integer 1234

print(id(x) == id(y))  # False
```


## Identity operators :style{.ppt-f95}

- `is` and `is not` are comparison operators used to check if the two operands refer to the same object.
- Using `is` operator means: are two variables referring to one and the same object?
- Using `==` operator means: are two variables referring to objects that contain same data?

:::hgrid
```python
x = int("1234")
y = int("12" + "34")
z = x 
print(x == y)  # True
print(x == z)  # True
```
```python
x = int("1234")
y = int("12" + "34")
z = x 
print(x is y)  # False
print(x is z)  # True
```
:::


## Mutable vs Immutable objects

:sc[Immutable]: the content of the object cannot be changed after the object has been created. 
- e.g. `str`, `int`, `float`, `tuple`

:sc[Mutable]: the content of the object can be changed after its creation without changing its identity.
- e.g. `list`, `dict`, `set`


## Strings are immutable

Unlike lists, we cannot use the square brackets to modify a character in the string.  

```python lineno=false
s = "cats"
s[0] = "r"  # TypeError: 'str' object does not support item assignment
```

##

All strings operations that seem to change a string actually :i[create] a new string.

:::hgrid
```python
s = "cat"
t = s
print("Before:", s is t)

s = s.replace('c','r')
print("After:", s is t)

print("s:", s)
print("t:", t)
```
```output
Before: True
After: False
s: rat
t: cat
```
:::

## Lists are mutable

The following code does not create a copy of the list `x`.  
It simply create a new variable name for the same list.

```python
x = [1, 2, 3]
y = x  # new name y for same list

print(x is y)  # True
```

Let us see some implications of this.

##

In the following illustrations, think about what is modified.
- Whether a variable changes its value i.e. the variable refers to a different value
- Whether a list object is modified i.e. some element of the list is changed.

##

:::div{.ppt-scale-1_25}
<iframe width="800" height="310" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=x%20%3D%205%0Ay%20%3D%20x%0Ay%20%3D%20y%20%2B%203%20%0Aprint%28x,%20y%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

##

:::div{.ppt-scale-1_25}
<iframe width="800" height="400" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=x%20%3D%20%5B5,%206,%207%5D%0Ay%20%3D%20x%0Ay%5B0%5D%20%3D%20y%5B0%5D%20%2B%203%0Aprint%28x%5B0%5D,%20y%5B0%5D%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

##

:::div{.ppt-scale-1_25}
<iframe width="800" height="400" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=def%20example%28x%29%3A%0A%20%20%20%20x%20%3D%20x%20*%205%0A%0Ax%20%3D%205%0Aexample%28x%29%20%0Aprint%28x%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

##

:::div{.ppt-scale-1_25}
<iframe width="800" height="500" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=def%20example%28x%29%3A%0A%20%20%20%20x%5B0%5D%20%3D%20x%5B0%5D%20*%205%0A%0Ax%20%3D%20%5B5,%206,%207%5D%0Aexample%28x%29%0Aprint%28x%5B0%5D%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=true&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::


## Sets

- A set is a an :i[unordered] collection of :i[immutable] objects.
- A set always contains unique elements, unlike lists and tuples which allow duplicates.
- A set is unordered i.e. we cannot use indexing or slicing on a set object

:::hgrid
```python lineno=false
numbers = {1, 2, 3}
print(numbers)  # {1, 2, 3}
print(type(numbers))  # <class 'set'>
```
```python lineno=false
# only unique values are kept
numbers = {1, 2, 3, 1, 3}
print(numbers)  # {1, 2, 3}
print(len(numbers))  # 3
```
:::

## Other ways to create a set

```python
# a set can be created from any sequence
# such as list, tuple or a string
things = set([10, 42, "apple", 42])
print(things)  # {'apple', 10, 42}

word = "pineapple"
letters = set(word)
print(letters)  
# {'p', 'n', 'l', 'i', 'e', 'a'}
```

##

```python
# create an empty set
empty_set = set()
print(len(empty_set))  # 0

# This does not create an empty set!
empty_dictionary = {}
print(type(empty_dictionary))  # <class 'dict'>
```

## Set elements must be immutable

A set can contain `int`, `float`, `str`, `bool` and `tuple` objects because they are all immutable.

But a set cannot contain a list because lists are mutable.

```python
# tuples are immutable so allowed in set
points = {(1, 1), (3, 10), (3, 10)}
print(points)  
# {(3, 10), (1, 1)}

# lists are mutable so not allowed
points = {[1, 1], [3, 10], [3, 10]}  
# TypeError: unhashable type: 'list'
```

## Set operators and methods

```python
# set.add(x):
#   Adds an element x to the set if x does not exist in the set. 
#   Does not return anything.

numbers = {1, 2, 3}
numbers.add(20)
print(numbers)  # {1, 2, 3, 20}

numbers.add(3)
print(numbers)  # {1, 2, 3, 20}
```

##

```python
# set.remove(x):
#   Remove an element x from the set. Does not return anything.
#   Throws KeyError if element x is not present in the set.

numbers = {1, 2, 3}
numbers.remove(2)
print(numbers)  # {1, 3}

numbers.remove(5)  # KeyError: 5
```

##

`in`, `not in` operators can be used to check if an element exists in a set.

```python
numbers = {1, 2, 3}
print(2 in numbers)  # True
print(5 not in numbers)  # True

shapes = {'circle', 'square'}
print("circle" in shapes)  # True
```

## 

:b[Sets cannot be indexed or sliced because they are not ordered.]

:::hgrid
```python
primes = {2, 3, 5, 7, 11}
primes[4]  # TypeError: 'set' object is not subscriptable
```
:::

But we can use for loop to iterate over the items:

:::hgrid
```python
# The order in which items will be printed 
# is not defined because sets are not ordered

numbers = {10, 1, 5, 20}
for n in numbers:
    print(n)
```
```output
1
10
20
5
```
:::

## Why use sets?

- Set are faster than lists and tuples, when inserting, removing and searching elements.
- When order of elements is important or when elements are mutable, use lists or tuples
- When only unique immutable elements need to be stored, use sets.


##

:::greenbox
Try the problem "Word count" on Ed Lessons.
:::

##

:::greenbox
Try the problem "List duplicates" on Ed Lessons.
:::


::divider


6.1 — Tuples, Immutable objects, Sets


## Updating multiple items in a list using slice assignment

The syntax of the slice assignment is as follows:

```python lineno=false
list_object[start:stop:step] = iterable
```

For now, think of `iterable` as a sequence/container such as a list, string, tuple etc.

##

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
print(days[1:3])
# ['Tue', 'Wed']

days[1:3] = [1, 2]
print(days)
# ['Mon', 1, 2, 'Thu', 'Fri', 'Sat', 'Sun']
```

##

```python
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
print(days[1::2])
# ['Tue', 'Thu', 'Sat']

days[1::2] = ["", "", ""]
print(days)
# ['Mon', '', 'Wed', '', 'Fri', '', 'Sun']

days[:3] = "MTW"
print(days)
# ['M', 'T', 'W', '', 'Fri', '', 'Sun']
```

## Other list methods

```python
# list.reverse() : Reverse the list "in place"
grades = [90, 70, 60.5, 70, 80]
grades.reverse()
print(grades)  # [80, 70, 60.5, 70, 90]

# list.clear() : Remove all items from list.
grades = [90, 70, 60.5, 70, 80]
grades.clear()
print(grades)  # []
```

## What modifies a list?

- Assigning a value to an element using its index. 
    ```python
    a = [1, 2, 3]
    a[0] = 5
    ```
- Using the slice assignment to modify the elements of a list. 
    ```python
    a = [1, 2, 3]
    a[:2] = [4, 5]
    ```
- Using methods like :code[append(), insert(), remove() , pop(), clear()], etc.


## What does not modify a list?
- Slicing! It is a useful tool to create new lists out of an existing lists.
    ```python
    a = [1, 2, 3]
    b = a[:]  # makes a copy of a
    print(a is b)  # False
    ```
- The `+` and `*` operators create a new list
    ```python
    a = [1, 2, 3]
    b = a  # does not copy, just a new name for same list
    b = b + [4]  # b now refers to a new list [1, 2, 3, 4]
                 # a still refers to [1, 2, 3]
    print(a is b)  # False
    ```

## Set methods

```python
# set.update(iterable):
#   Adds all items from the iterable to the set.

numbers = {1, 2, 3}
numbers.update([10, 2, 2, 3, 20])
print(numbers)  # {1, 2, 3, 10, 20}

numbers.update(("a", "b")) 
print(numbers)  # {1, 2, 3, 'a', 10, 20, 'b'}

primes = {2, 3, 5}
primes.update({5, 7, 11})
print(primes)  # {2, 3, 5, 7, 11}
```

##

```python
# set.clear(): Remove all elements from this set.

numbers = {1, 2, 3}
numbers.clear()
print(numbers)  # set()
```

##

```python
# For the following methods, suppose A and B are sets.

# A.intersection(B):
#    Returns a new set that contains elements that are
#    present in both A and B   

odd = {3, 5, 7, 9, 25}
squares = {4, 9, 25, 36}
odd_squares = odd.intersection(squares)
print(odd_squares)  # {9, 25}

# Intersection can also be done using operator &
odd_squares = odd & squares
print(odd_squares)  # {9, 25}
```

##

```python
# A.union(B):
#    Returns a new set that contains elements that are
#    present in  A or B or both

x = {1, 2, 3}
y = {2, 3, 5}
all_numbers = x.union(y)
print(all_numbers)  # {1, 2, 3, 5}

# Same above but using an operator |
all_numbers = x | y
print(all_numbers)  # {1, 2, 3, 5}
```

##

```python
# A.difference(B):
#   Returns a new set that contains elements that are
#   present only in A but not in B
x = {1, 2, 3}
y = {2, 3, 5}
diff = x.difference(y)
print(diff)  # {1}

# Same as above but using operator -
diff = x - y
print(diff)  # {1}
```

All of the `set` methods work the same when elements are of other types such as strings.

## Dictionaries :style{.ppt-f95}

Suppose we would like to store the following enrollment data:

:::hgrid{.ppt-f95 margin="0"}
| semester | no. of students |
|----------|-----------------|
| F2017    | 816             |
| W2018    | 613             |
| F2018    | 709             |
| W2019    | 590             |
:::

We can do this using two lists for the two columns:
```python
semesters = ['F2017', 'W2018', 'F2018', 'W2019']
students = [816, 613, 709, 590]
```



##

What should we do if we want to add new data?

```python
semesters = ['F2017', 'W2018', 'F2018', 'W2019']
students = [816, 613, 709, 590]

semesters.append("F2020")
students.append(550)
# ['F2017', 'W2018', 'F2018', 'W2019', 'F2020']
# [816, 613, 709, 590, 550]
``` 

##

What if we want to modify the value for a specific semester?

```python
semesters = ['F2017', 'W2018', 'F2018', 'W2019']
students = [816, 613, 709, 590]

idx = semesters.index("W2018")
students[idx] = 600
```

##

What we if try to add an entry for a semester that already exists?  

List allows duplicates so it does not check if a semester already exists.

```python
semesters = ['F2017', 'W2018', 'F2018', 'W2019']
students = [816, 613, 709, 590]

semesters.append("F2018")
students.append(500)
# ['F2017', 'W2018', 'F2018', 'W2019', 'F2018']
# [816, 613, 709, 590, 500]
```

## Use a dictionary!

- You can think of an item of a dictionary as a pair of objects:
    - The first object of the pair is called a :sc[key].
    - The second object is referred to as the :sc[value].
- A dictionary is called a :i[mapping] type because it maps key objects to value objects.

```python
# A dictionary is created using a sequence of key-value pairs
enrollment = {'F2017': 816, 'W2018': 613,
              'F2018': 709, 'W2019': 590}

print(type(enrollment))  # <class 'dict'>
```

##

```python
# Number of key-value pairs
print(len(enrollment))  # 4

# This is an empty dictionary, not a set!
empty_dict = {}
print(len(empty_dict)) # 0
```

## Dictionary Examples

```python
# Key: a number, Value: True if number is prime, else False
is_prime = {2: True, 3: True, 4: False, 5: True,
            7: True, 10: False}

# Key: inventory items, Value: count of items in inventory
inventory = {"sofa": 5, "table": 10, "chair": 20, "mattress": 5}

# Key: city name, Value: area of city
population = {"Montreal": 431.50, "Toronto": 630.20}

# Key: country name, Value: capital city
capitals = {"Canada": "Ottawa", "United States": "Washington, D.C.",
            "France": "Paris", "Germany": "Berlin"}
```

## Note on keys and values

- Keys
    - Have to be immutable objects.
    - Have to be unique in a dictionary. A dictionary cannot contain two items with the same key.
- Values
    - Values can be of any type; both mutable and immutable values are allowed.
    - Many keys can map to the same value. i.e. values need not be unique.

## Dictionary Lookup

With lists, we can access an item of the list through its index.

With dictionaries, we can access a value stored in the dictionary through the key associated with it.

```python
enrollment = {'F2017': 816, 'W2018': 613, 'F2018': 709,
              'W2019': 590, 'F2019': 744}

num_students = enrollment["F2018"]
print(num_students)  # 709

# Key must exist in the dictionary if we want to access its value
print(enrollment["F2020"])  # KeyError: 'F2020'
```

## Adding an item

We can add a new item by specifying a key and a value: `dictionary[key] = value`

```python
enrollment = {'F2018': 709, 'W2019': 590}

enrollment["F2020"] = 800  # add an item
enrollment["W2020"] = 900  # add another item

# {'F2018': 709, 'W2019': 590, 'F2020': 800, 'W2020': 900}

enrollment["F2018"] = 700  # change an existing item

# {'F2018': 700, 'W2019': 590, 'F2020': 800, 'W2020': 900}
```

## Removing an item

We can delete an item using the following syntax: `del dictionary[key]`

```python
enrollment = {'F2018': 709, 'W2019': 590, 'F2019': 744}

del enrollment["F2019"]

# {'F2018': 709, 'W2019': 590}

del enrollment["F2020"]
# KeyError: 'F2020'
```

## 

What will be printed in the following examples?

:::hgrid
```python
d = {'x' : 0, 'y' : 1, 'z' : 2} 
x = d['y']
print(x)
```
:::
:::hgrid
```python
d = {'x' : 0, 'y' : 1, 'z' : 2} 
x = d[0]
print(x)
```
:::

## Check for membership

We can check if a key is part of a dictionary using the `in` and `not in` operators.

```python
d = {'x' : 0, 'y' : 1, 'z' : 2} 
print('x' in d) #  True 
print(0 in d) #  False
print(0 not in d) #  True
```

## Iterating through a dictionary

We can use a for loop to iterate through all the keys in a dictionary.

```python
enrollment = {'F2018': 709, 'W2019': 590, 'F2019': 744}

for key in enrollment:
    print(key, "->", enrollment[key])
```

```output
F2018 -> 709
W2019 -> 590
F2019 -> 744
```

## Functions and methods for dictionaries

```python
# dict(L): creates and returns a dictionary using a list L of tuples, 
#   where each tuple is of length 2 in form of (key, value).

pairs = [("Montreal", 1.78), ("Rome", 2.87), ("Tokyo", 9.27)]
population_data = dict(pairs)

print(population_data)
#  {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}

print(population_data["Rome"])
# 2.87
```

##

```python
population_data = {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}

# dict.keys(): returns a iterable (sequence) of all keys

cities = list(population_data.keys())
print(cities)  # ['Montreal', 'Rome', 'Tokyo']

# dict.values(): returns a iterable (sequence) of all values

population = list(population_data.values())
print(population)  # [1.78, 2.87, 9.27]
```

##

```python
# dict.items(): returns a iterable (sequence) of tuples (key, value) 
#   for all items in the dictionary

population_data = {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}
pairs = list(population_data.items())

print(pairs)
# [('Montreal', 1.78), ('Rome', 2.87), ('Tokyo', 9.27)]
```

For more methods, use `help(dict)`.

##

Using the `dict` methods in `for` loop:

```python
population_data = {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}

total = 0
for population in population_data.values():
    total += population

print(total)  # 13.92
```

##

```python
population_data = {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}

# dict.items() returns an iterable of key-value tuples

for tup in population_data.items():
    city = tup[0]
    population = tup[1]
    print(city, "->", population)

# Montreal -> 1.78
# Rome -> 2.87
# Tokyo -> 9.27
```

##

Making use of tuple unpacking in the for loop:

```python
population_data = {'Montreal': 1.78, 'Rome': 2.87, 'Tokyo': 9.27}

for city, population in population_data.items():
    print(city, "->", population)

# Montreal -> 1.78
# Rome -> 2.87
# Tokyo -> 9.27
```

##

:::greenbox
Time for some problems on Ed Lessons.
:::


::divider

6.2 — More list & set operations, Dictionaries


## What's wrong in this example?

```python
def average(nums):
    total = 0

    for x in grades:
       total += x

    return total / len(grades)


grades = [85, 100, 98, 75]
print(average(grades))  # 89.5
```

##

- Try to avoid using global variables within functions when possible.
- Assignment autograder will fail if you use global variable(s) instead of function parameter(s) inside a function.

## Iterable

An :sc[iterable] is a kind of object that can produce a sequence of other objects and hence can be used in a `for` loop.

- range: sequence of integers
- strings: sequence of characters
- tuples: (immutable) sequence of any object
- lists: sequence of any object
- dictionaries: sequence of tuples (key, value)
- sets: collection of immutable objects (but order is not defined)


##

Iterables can be used as arguments of the functions `list()`, `set()`, `tuple()`, `dict()`, etc.

```python
# range object only stores start, end and step size.
print(range(10, 101, 10))  # range(10, 101, 10)

# list stores all objects in memory 
l = list(range(10, 101, 10))
print(l)
# [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

s = set(range(10, 101, 10))
print(s)
# {100, 70, 40, 10, 80, 50, 20, 90, 60, 30}
```

##

:::greenbox
"Performance of searching a list, a set and dictionary" from last week.
:::

## Sorting a list using `sort` method

```python
# list.sort() : 
#   Sorts the list "in place" i.e. list will be modified.
#   Returns None.
#   The list is sorted in ascending order.

grades = [90, 70, 60.5, 70, 80]
grades.sort()
print(grades)  # [60.5, 70, 70, 80, 90]


grades.sort(reverse=True)  # descending order
print(grades)  # [90, 80, 70, 70, 60.5]
```

##

```python
grades = [90, 70, 60.5, 70, 80, "A"]
grades.sort()
# TypeError: '<' not supported between instances of 'str' and 'int'


# Works with strings as well
fruits = ["banana", "orange", "apple"]
fruits.sort()
print(fruits)  # ['apple', 'banana', 'orange']
```

## `sorted` function

```python
# sorted(iterable): 
#   Return a new list containing all items from 
#   the iterable in ascending order.
#   If any items cannnot be compared to each other, TypeError occurs.

grades = [90, 70, 60.5, 70, 80]
sorted_grades = sorted(grades)
print(sorted_grades)  # [60.5, 70, 70, 80, 90]
print(grades)  # [90, 70, 60.5, 70, 80]

# Sort in descending order
sorted_grades = sorted(grades, reverse=True)
print(sorted_grades)  # [90, 80, 70, 70, 60.5]
```

##

```python
# string is iterable
word = "pineapple"
sorted_letters = sorted(word)
print(sorted_letters)
# ['a', 'e', 'e', 'i', 'l', 'n', 'p', 'p', 'p']


# set is iterable
fruits = {"banana", "orange", "apple"}
sorted_fruits = sorted(fruits)
print(sorted_fruits)  # ['apple', 'banana', 'orange']
```

##

```python
# dictionary is considered as an iterable of its keys
inventory = {"sofa": 5, "table": 10, "chair": 20, "mattress": 5}
sorted_names = sorted(inventory)
print(sorted_names)  # ['chair', 'mattress', 'sofa', 'table']

# same as above
sorted_names = sorted(inventory.keys())
print(sorted_names)  # ['chair', 'mattress', 'sofa', 'table']

# iterable of values in the dictionary
sorted_counts = sorted(inventory.values())
print(sorted_counts)  # [5, 5, 10, 20]
```

## Packing vs Unpacking

When we create a string, a list, or a tuple, we are packing several elements into a single object.

```python
s = "cat"
my_list = [5, 'a']
my_tuple = (0, 3, 7)
```

##

:sc[Unpacking] allows us to assign values in a string/list/tuple to multiple variables.  
We must know the exact length of the string/list/tuple.

```python
s = "cat"
a, b, c = s
# a, b and c are all strings
print(a)  # c
print(b)  # a
print(c)  # t

my_list = [5, 'cat']
x, y = my_list
print(x)  # 5
print(y)  # cat
```

##

```python
# Parentheses are optional in this context.
my_tuple = 0, 3, 7
x, y, z = my_tuple
print(x)  # 0
print(y)  # 3
print(z)  # 7

# Variables must match number of elements
tup = 1, 2, 3 
x, y = tup
# ValueError: too many values to unpack (expected 2)
```

## Multiple assignment using packing/unpacking on same line

```python
# We are creating a tuple on the right side and 
# unpacking it into 3 variables.
city, population, area = 'Montreal', 1704694, 431.5
print(city)  # Montreal
print(population)  # 1704694
print(area)  # 431.5
```

## Returning a tuple from a function and unpacking

```python
def min_max(mylist):
    # Return a tuple of two elements
    return min(mylist), max(mylist)
    
    
# Unpack the returned tuple into 2 variables
x, y = min_max([2, -3, 10, 20])
print(x)  # -3
print(y)  # 20
```


## Nested Lists

An element of a list can be another list!  
Such lists are called :sc[nested] lists.

```python
nested_list = [[1], [1, 2, 3], [1, 2]]
print(type(nested_list))
# <class 'list'>

print(nested_list[0])
# [1]
print(nested_list[1])
# [1, 2, 3]
print(nested_list[2])
# [1, 2]
```

##

Nested lists are useful to store data which come in form of a table or spreadsheet.

```python
#                      Name,     A1,  A2,  A3
student_grades = [["Student-A",  90,  95, 100], 
                  ["Student-B",  85,  90,  98], 
                  ["Student-C",  70,  75,  80]] 
```

##

We can perform same operations on nested lists as we saw earlier: indexing, slicing, etc.

```python
student_grades = [["Student-A",  90, 95, 100],
                  ["Student-B",  85, 90, 98],
                  ["Student-C",  70, 75, 80]]

# Print name of 2nd student
print(student_grades[1][0]) 
# Student-B

# Change A2 grade for Student-B
student_grades[1][2] = 100
print(student_grades)
# [['Student-A', 90, 95, 100], ['Student-B', 85, 100, 98], 
#  ['Student-C', 70, 75, 80]]
```

## Iterating in a :i[row-first] order

:::hgrid
```python
matrix = [[81, 75, 90, 60], 
          [80, 70, 85, 55],
          [40, 50, 45, 85]]

num_rows = len(matrix)  
num_cols = len(matrix[0]) 

print("Row-first order:")
for r in range(num_rows):
    for c in range(num_cols):
        print(matrix[r][c], end=" ")
    print()
```
```output
Row-first order:
81 75 90 60 
80 70 85 55 
40 50 45 85 
```
:::

## Iterating in a :i[column-first] order

:::hgrid
```python
matrix = [[81, 75, 90, 60], 
          [80, 70, 85, 55],
          [40, 50, 45, 85]]

num_rows = len(matrix)  
num_cols = len(matrix[0])

print("\nColumn-first order:")
for c in range(num_cols):
    for r in range(num_rows):
        print(matrix[r][c], end=" ")
    print()
```
```output
Column-first order:
81 80 40 
75 70 50 
90 85 45 
60 55 85
```
:::

## List of tuples

```python
points = [(1, 1, 3), (4, 10.5, 9), (7, 4.4, 9.7)]

# List element can be modified:
points[1] = (4, 12, 10)  # Assign new point
print(points)  # [(1, 1, 3), (4, 12, 10), (7, 4.4, 9.7)]

# Trying to change the second points's z-coordinate
points[1][2] = 20  
# TypeError: 'tuple' object does not support item assignment
```

##

Iterating over list of tuples:

:::hgrid
```python
points = [(1, 1, 3), (4, 10.5, 9), 
          (7, 4.4, 9.7)]

for p in points:  # p is a tuple
    print(p)

# Unpack a tuple into 3 variables
for x, y, z in points:  
    print(x, y, z)
```

```output
(1, 1, 3)
(4, 10.5, 9)
(7, 4.4, 9.7)
1 1 3
4 10.5 9
7 4.4 9.7
```
:::

##

:::greenbox
Time for some problems on Ed Lessons.
:::

::divider


7.1 — Iterables, Unpacking, Nested Lists


## List of dictionaries

A dictionary can be used to represent a data record such as student record in a course in the following example.

A list of such dictionaries can store multiple data records.

```python
student_records = [
    {"name": "Student-A", "ID": 2601234, "grades": [90, 95, 100]},
    {"name": "Student-B", "ID": 2601000, "grades": [95, 95, 97]},
    {"name": "Student-C", "ID": 2605000, "grades": [80, 85, 90]}
]

# Each "grades" list has grades for 3 assignments.
```

##

What are assignment 1 grades for "Student-B" ?

```python
student_records = [
    {"name": "Student-A", "ID": 2601234, "grades": [90, 95, 100]},
    {"name": "Student-B", "ID": 2601000, "grades": [95, 95, 97]},
    {"name": "Student-C", "ID": 2605000, "grades": [80, 85, 90]}
]

print(student_records[1]["grades"][0])  # 95
```

##

Display total grade for each student.

```python
student_records = [
    {"name": "Student-A", "ID": 2601234, "grades": [90, 95, 100]},
    {"name": "Student-B", "ID": 2601000, "grades": [95, 95, 97]},
    {"name": "Student-C", "ID": 2605000, "grades": [80, 85, 90]}
]

for record in student_records:
    name, total_grade = record["name"], sum(record["grades"])
    print(f"Total grade for {name} is {total_grade}")
```
```output
Total grade for Student-A is 285
Total grade for Student-B is 287
Total grade for Student-C is 255
```


## Comparing data structures

Data structures — list, tuples, sets and dictionaries can be compared for equality using `==` and `!=` operators.

```python
# Lists, order matters
grades1 = [85, 80, 100]
grades2 = [85, 80, 100]
grades3 = [85, 100, 80]

# True only when all elements are equal in order
print(grades1 == grades2)  # True
print(grades2 == grades3)  # False
```

##

```python
# Comparing tuples, order matters
point1 = (1, 1, 2)
point2 = (1, 2, 1)
print(point1 != point2)  # True


# Comparing sets, order does not matter
fruits1 = {"apple", "orange", "banana"}
fruits2 = {"orange", "apple",  "banana"}

# True only when sets are of equal length and 
# both sets contain same elements
print(fruits1 == fruits2)  # True
print(fruits1 == {"apple", "orange", "banana", "grapes"})  # False
```

##

```python
# Comparing dictionaries, order does not matter
phonebook1 = {"A": 5140001000, "B": 5140002000, "C": 5140003000 }
phonebook2 = { "B": 5140002000, "A": 5140001000, "C": 5140003000 }

# True only when dictionaries are of equal length and 
# both contain same key-value pairs
print(phonebook1 == phonebook2)  # True

print(phonebook1 == {"A": 4381001000, "B": 5140002000, 
                     "C": 5140003000 })  # False
```

## Comparison works for nested structures as well

```python
points1 = [(1, 1), (2, 10)]
points2 = [(1, 1), (2, 10)]
print(points1 == points2)  # True

print(points1 == [(1, 1), (2, 5)])  # False
print(points1 == [(1, 1), [2, 10]])  # False

student1 = {"name": "Student-B", "grades": [90, 100, 100]}
student2 = {"name": "Student-B", "grades": [90, 100, 90]}
print(student1 == student2)  # False
```

## `enumerate` function

```python
mylist = [10, 50, -3.14, 5]
print(enumerate(mylist))
# <enumerate object at 0x10e327100>

# enumerate creates an iterable of tuples (index, element), 
# which we convert to list
list_of_tuples = list(enumerate(mylist))
print(list_of_tuples)
# [(0, 10), (1, 50), (2, -3.14), (3, 5)]
```

##

:::hgrid
```python
mylist = [10, 50, -3.14, 5]

for i in range(len(mylist)):
    num = mylist[i]
    print(i, num)
```
```python
mylist = [10, 50, -3.14, 5]

for i, num in enumerate(mylist):
    print(i, num)
```
:::

## List, set and dictionary comprehensions

We often find ourselves repeating the following pattern to create a list. 

Python provides a simpler way to create a list using list comprehension.

```python
some_list = []
for i in some_iterable:
    some_list.append(some_expression)

# Using list comprehension
some_list = [some_expression for i in some_iterable]
```

##

```python
even_nums = [i for i in range(2, 20, 2)]
print(even_nums)
# [2, 4, 6, 8, 10, 12, 14, 16, 18]


# Need not use loop variable i in the expression
zeros = [0 for i in range(7)]
print(zeros)
# [0, 0, 0, 0, 0, 0, 0]
```

##

```python
import math

sine_values = [math.sin(x) for x in [-math.pi/2, 0, math.pi/2]]
print(sine_values)
# [-1.0, 0.0, 1.0]

string = "10.0,20.5,100.123"
numbers = [float(word) for word in string.split(",")]
print(numbers)
# [10.0, 20.5, 100.123]
```

## Using if-statement in list comprehension

```python
squares_of_odds = []
for x in range(1, 20):
    if x % 2 != 0:
        squares_of_odds.append(x * x)

print(squares_of_odds)
# [1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

# same as above but using list comprehension
squares_of_odds = [x * x for x in range(1, 20) if x % 2 != 0]
print(squares_of_odds)
# [1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

```

## Set and dictionary comprehension

```python
odd_squares = {i*i for i in range(1, 20, 2)}
print(odd_squares)
# {1, 121, 225, 289, 9, 169, 361, 81, 49, 25}


names = ["A", "B", "C", "D"]
names_to_index = {name: i for i, name in enumerate(names)}
print(names_to_index)
# {'A': 0, 'B': 1, 'C': 2, 'D': 3}
```

## Writing & importing modules

- What are modules exactly?
    - A module is simply a Python file containing definitions and statements.
    - Every `.py` file is a module. The name of the module is the name of the file.
- Name of a Python file (module) must follow same rules as variable names.
    - Module names can only start with letters a-z, A-Z or an underscore and must only contain these letters, digits and underscores.

##

Download files-7.2.zip from Ed Lessons. It contains `geometry.py` and `geometry_tester.py`

##

In `geometry_tester.py` file, we import and use the functions defined in the module `geometry`:

```python
# Import functions from the module
from geometry import euclidean_distance, sine

# Call the sine function
print(sine(90))

dist = euclidean_distance((1, 1), (2, 3))  # tuples
print(dist)  # 2.23606797749979

```

## Some observations

- When we import a module, all code inside that module is executed.
- Add some statement such as `print("hello")` in `geometry` module outside the functions. Then,
    - Run the `geometry.py` as the main program
    - Run another program which imports the module `geometry`.

## Running a file as main program vs importing it

- Sometimes, we may want to run some code only when a Python file is executed directly as main program but not when it is imported as a module.
- For example, suppose we want the following test cases in `geometry.py`
    ```python
    print(sine(-90))
    print(sine(180))
    ```
- How to make sure the test cases do not execute when `geometry` is imported as a module?

## `__name__`

- `__name__` is a special variable that the interpreter initializes whenever it executes a file.
- When a module is executed, the interpreter does the following: 
    - sets the value of `__name__` for that module using the filename
    - executes all the code in the module.
- Each module has its own `__name__` variable.
- Add `print(__name__)` in `geometry.py` and import `geometry` module in another program.

## `"__main__"`

- When we execute a file as the main program, then the variable `__name__` is set to be `"__main__"`
- Run `geometry.py` directly and see what value of `__name__` is printed.

## How to :i[not execute] code in a module when it is imported

Add the following at the end of the file `geometry.py`:

```python
if __name__ == "__main__":
    # Run the following code only when this file is 
    # executed as main program but not when it is imported
    print("hello from geometry!")
    print(sine(-90))
    print(sine(180))
```

##

:::greenbox
Time for some problems on Ed Lessons.
:::

::divider



7.2 — Nested data structures, Comprehensions, Modules


##

:b[How list is stored]{.sans}

:::hgrid{gap="1em" margin="0.5em 0"}
```python lineno=false
mylist = [3, 17, 42]
```

::image{style="width: 100%" src="lecture-8.1/mylist_actual.png"}  
:::

:::hgrid{cols="1fr 4fr" margin="0.5em 0"}
:b[Simplified: ]{.sans}
::image{style="width: 70%" src="lecture-8.1/mylist_simplified.png"}  
:::

##

:b[How :i[nested list] is stored]{.sans}

```python lineno=false margin="0.5em 0"
nested_list = [[3, 17, 42], [10, 20, 30]]
```

::image{style="width: 65%; margin: 1em auto;" src="lecture-8.1/nested_list.png"}  

##

:::hgrid{margin="0"}
```python lineno=false margin="0.5em 0"
zeros = [0] * 5
C = [zeros] * 3
C[1][3] = 100  
print(C)    
```
```python lineno=false margin="0.5em 0"
zeros = [0] * 5
C = []
for i in range(3):
    C.append(zeros)
C[1][3] = 100  
print(C)    
```
```output
[[0, 0, 0, 100, 0], 
 [0, 0, 0, 100, 0], 
 [0, 0, 0, 100, 0]]
```
:::

::image{style="width: 80%; margin: 0.5em auto;" src="lecture-8.1/nested_zeros.png"}  

##

:::hgrid{margin="0" cols="1fr 4fr"}
```python lineno=false margin="0.5em 0"
C = []
for i in range(3):
    C.append([0] * 5)
C[1][3] = 100  
print(C)
```

::image{style="width: 100%; margin: 0.5em auto;" src="lecture-8.1/nested_zeros_correct.png"}  
:::

## Nested list comprehensions

```python
matrix = [[10, 20, 30],
          [40, 50, 60],
          [70, 80, 90]]

squared = [[x ** 2 for x in row] for row in matrix]

print(squared)
# [[100, 400, 900],
#  [1600, 2500, 3600],
#  [4900, 6400, 8100]]

```

##

:::greenbox
Time for list comprehension problems on Ed Lessons.
:::

## How to work with a file in Python

A file is a sequence of characters or bytes stored on a storage device such as a hard drive.

- Open the file using the built-in function `open()`
- Read data from the file or write data into the file
- Close the file


## Opening a file with :code[open()]

Built-in function `open(filename, mode)`:
- `filename` (str): name of the file to read (if the file is in the current directory) or full path to the file.
- `mode` (str): `'r'` for reading, `'w'` for writing, `'a'` for appending. If this argument is omitted, it defaults to `'r'`
- Returns: a :sc[file object] which allows reading from/writing to the file.

```python
filename = "quotes.txt"
fobj = open(filename, "r") # mode "r" for reading
```

## Reading a file with :code[read()] method of file object

File objects have a method `read(size)` that takes one optional argument:
- `size`: the number of characters to read from the file
    - If omitted, the entire file will be read.
- Returns: a string containing the characters in the file

##  Closing a file with :code[close()] method of file object

- `close()` method takes no argument and returns nothing. It closes the file associated with the file object

##

For the following example, download the files from Ed Lessons and keep them in the same directory as the python program.

```python
filename = "quotes.txt"
fobj = open(filename, "r") # mode "r" for reading 

file_content = fobj.read() # read whole file as a string
print(file_content) # print the string 

fobj.close()  # close the file
```

## Why close a file?   

Closing the file is important for many reasons 
- Operating System (e.g Windows, Mac OS) may lock the file until it is closed (Other programs may not use the file as long as it is open)
- Too many open files may cause your program/computer to slow down


## Reading a file line by line

- The file object returned by `open()` is an iterable that can produce a sequence of lines in the file. So we can use it in a `for` loop.
- Each line will have a trailing newline (`"\n"`) character.

```python
filename = "quotes.txt"
fobj = open(filename, "r")

for line in fobj: # file object is iterable
    line = line.rstrip("\n")  # Remove trailing "\n" character
    print(line) 

fobj.close()
```

## Reading a file as list of lines

```python
filename = "quotes.txt"
fobj = open(filename, "r")

# Read whole file, split into lines and return a list of lines
all_lines = fobj.readlines() 

# Each line will have a trailing newline character "\n"

print(all_lines)

fobj.close()
```

## Writing text to a file in Python

To write to a file in Python:
- Open the file with open() using mode `'w'` for "write."
    - If the file does not exist, it will be created.
    - :span[If the file exists, it will be deleted and replaced with an empty file.]{.bgred .px05}
- Call `write(s)` method on the file object to write the string `s` into the file.
- Close the file.

##

```python
filename = "grades.txt"
fobj = open(filename, "w") # mode "w" for writing 

fobj.write("Name,A1,A2,A3\n") # write line to file
fobj.write("Student-A,90,80,100\n") # write another line
fobj.write("Student-B,100,90,100\n") # write another line

fobj.close()
```

## Appending text to a file in Python

Appending means adding text to the end of a file without changing/deleting text already present in the file.

- Open the file with open() using mode `'a'` for "append."
    - If the file does not exist, it will be created.
    - If the file exists, it is NOT deleted.
- Call `write(s)` method on the file object, to write the string `s` at the end of the file.
- Close the file.

##

```python
filename = "grades.txt"
fobj = open(filename, "a") # mode "a" for appending 

fobj.write("Student-C,85,90,97\n")
fobj.write("Student-D,95,90,97\n") 

fobj.close()
```

##

:::greenbox
Time for some problems on Ed Lessons.
:::

::divider



8.1 — Nested list comprehensions, Reading & Writing Files


## `with` statement to open files

```python
with open("myfile.txt", "r") as fobj:
    # file remains open here inside with-statement
    file_content = fobj.read()

# the file is automatically closed when
# the with-statement is done

print(file_content)
```

##

Any valid operations/methods can be performed on the file object inside the `with` statement.

```python
with open("myfile.txt", "r") as fobj:
    for line in fobj:
        line = line.rstrip("\n")
        print(line)
```

For the Write and Append modes, the `write` method can be used in the `with` statement.

##

```python
with open("myfile.txt", "r") as fobj:
    print("hello")

print(fobj.read())
```

```output
hello
Traceback (most recent call last):
  File "lecture_8.py", line 4, in <module>
    print(fobj.read())
ValueError: I/O operation on closed file.
```


## Reading & writing files using pathlib

To read a file entirely into a string:

```python
from pathlib import Path

file_content = Path("myfile.txt").read_text()
print(file_content)
```

##

To write text into a file:

```python
from pathlib import Path

data = """Name,A1,A2,A3
Student-A,90,80,100
Student-B,100,90,100
"""

# this will delete existing contents of the file
Path("grades.txt").write_text(data)
```

## Shallow copy

When we create a new list using slicing or  `list()` function on a nested list, inner lists are not copied but they are shared. Such a copy is called :sc[shallow copy].

```python
nested_list = [[3, 17, 42], [10, 20, 30]]

new_copy = nested_list[:]  # shallow copy

new_copy = list(nested_list)  # shallow copy
```

##

```python lineno=false
nested_list = [[3, 17, 42], 
               [10, 20, 30]]

new_copy = nested_list[:]
```

::image{style="width: 70%; margin: 1em auto" src="lecture-8.2/shallow_copy.png"}  

##

Changing values in a shallow copy affects the original nested list because inner lists are shared.

:::hgrid
```python
nested_list = [[3, 17, 42], 
               [10, 20, 30]]

new_copy = nested_list[:] 
# new_copy = list(nested_list)

new_copy[0][2] = 123

print(new_copy)
print(nested_list)
```
```output
[[3, 17, 123], [10, 20, 30]]
[[3, 17, 123], [10, 20, 30]]
```
:::

##

Similary `dict()`, `tuple()`, `set()` functions will make a shallow copy.

```python lineno=false
student = {"name": "Reza", "ID": 2601000, "grades": [95, 95, 97]}
student_copy = dict(student)
```

::image{style="width: 100%; margin: 1em auto" src="lecture-8.2/shallow_copy_dict.png"}  

##

Changing values via the shallow copy affects the original dictionary because grades list is shared.

```python
student = {"name": "Reza", "ID": 2601000, "grades": [95, 95, 97]}

student_copy = dict(student)
student_copy["grades"][0] = 100

print(student_copy)
print(student)
```
```output
{'name': 'Reza', 'ID': 2601000, 'grades': [100, 95, 97]}
{'name': 'Reza', 'ID': 2601000, 'grades': [100, 95, 97]}
```

## Deep copy :style{.ppt-f95}

`deepcopy` function from `copy` module can copy a nested structure recursively (all inner lists etc. are copied as well). Such a copy is called :sc[deep copy].

:::hgrid
```python
import copy

nested_list = [[3, 17, 42], 
               [10, 20, 30]]
new_copy = copy.deepcopy(nested_list)
new_copy[0][2] = 123

print(new_copy)
print(nested_list)
```
```output
[[3, 17, 123], [10, 20, 30]]
[[3, 17, 42], [10, 20, 30]]
```
:::

##

```python
import copy

student = {"name": "Reza", "ID": 2601000, "grades": [95, 95, 97]}

student_copy = copy.deepcopy(student)
student_copy["grades"][0] = 100

print(student_copy)
print(student)
```

```output
{'name': 'Reza', 'ID': 2601000, 'grades': [100, 95, 97]}
{'name': 'Reza', 'ID': 2601000, 'grades': [95, 95, 97]}
```

##

:::greenbox
Time for problems about file reading/writing on Ed Lessons.
:::

## Types of Errors

- Syntax Errors: When syntax is incorrect such as wrong punctuations, invalid characters, indentation etc.
    - Program does not even run in this case.
- Runtime Errors, also called :sc[Exceptions], occur when there is a problem in the program during execution.
    - All code executes until an exception occurs.
- Semantic or Logic errors are said to occur when a program executes without a problem but does not produce correct output as expected.

## :style{.ppt-f90}

In Python, all exceptions are objects of some exception type.  
Common exceptions are:

:::div
| Exception Type   | Meaning                                                               |
|-------------------|-----------------------------------------------------------------------|
| IndexError        | Index is out of range in a list or tuple                              |
| KeyError          | Specified key does not appear in a dictionary                         |
| NameError         | Specified local or global name does not exist                         |
| TypeError         | Operation or function applied to an inappropriate type                |
| ValueError        | Operation or function applied to correct type but inappropriate value |
| ZeroDivisionError | Second operand of division or remainder operation is zero             |
:::

## Exception Traceback

Traceback is an error message that allows tracing an exception back to its origin

:::hgrid{cols="1fr 2fr"}
```python
def func():
   return 5 / 0

def main():
   return func()

main()
```
```output
Traceback (most recent call last):
  File "myprogram.py", line 7, in <module>
    main()
  File "myprogram.py", line 5, in main
    return func()
  File "myprogram.py", line 2, in func
    return 5 / 0
ZeroDivisionError: division by zero
```
:::

## Using `try` statement to handle errors

```python
try:
    # try-block: code that may cause runtime error
except:
    # except-block: handle the error here
```

- Identify a code that can potentially produce errors
- Put that code in `try-block`. 
- Write code in `except-block` to handle the case when error occurs

## Example

Suppose we want to take a number from user input:

```python
number = float(input('Please enter a number: '))
```

```output
ValueError: could not convert string to float: 'abcd'
```

Since we know that `float()` function throws the `ValueError`, we can handle that error using `try` statement.

##

```python
try:
   number = float(input('Please enter a number: '))
   # the following line only executes when float() function
   # worked i.e. it did not throw ValueError
   print("You entered: ", number)  
except ValueError:
   print("Please enter valid number!")
```

There are two cases when we run the code above:

::::div{.flex .ml-2}
:::div{.flexc}

:div[No error occurs in try-block]{.sans}
except-block is not executed.

```output
Please enter a number: -3.1415
You entered:  -3.1415
```
:::

:::div{.flexc}

:div[Error occurs in try-block]{.sans}
except-block is executed.

```output
Please enter a number: abcd
Please enter valid number!
```
:::
::::

## 

:::greenbox
Using try statement in a loop, ask user to input a number (float) until they enter a valid number.  
You can use a break statement in the try-block.
:::

```output
Please enter a number: abcd
Invalid number!
Please enter a number: -1.61
Correct number entered: -1.61
```

##

:::solution
```python
while True: # Loop forever
   try:
       number = float(input('Please enter a number: '))
       break  # Get out of the loop
   except ValueError:
       print('Invalid number!')

print("Correct number entered:", number)
```
:::

## Unhandled exceptions are thrown as usual

If an exception occurs in try-block but it is not the same type as in the except part, the exception occurs as usual i.e. except-block is not executed and program crashes.

:::hgrid{.ppt-f80 margin="1em 0 1em -2em"}
```python
student_grades = {"Reza": 90.0}

try:
    name = input('Enter name: ')
    grade = float(input("Enter grade to add: "))
    student_grades[name] += grade
    print(student_grades)
except ValueError:
    print('Grade should be a number!')
```

```output
Enter name: Dev
Enter grade to add: 5
Traceback (most recent call last):
  File "myprogram.py", line 20
    student_grades[name] += grade
KeyError: 'Dev'
```
:::

## Catching multiple exceptions

Except blocks can be chained to handle multiple exceptions that may occur in try-block.

Depending on the exception that occurs, only one of the except-blocks executes. Others are skipped.

```python
try:
    # try-block: code that may cause runtime error(s)
except Error1:
    # handle the Error1 here
except Error2:
    # handle the Error2 here
```

## :style{.ppt-f90}

```python
student_grades = {"Reza": 90.0}

try:
    name = input('Enter name: ')
    grade = float(input("Enter grade to add: "))
    student_grades[name] += grade
    print(student_grades)
except ValueError:
    print('Grade should be a number!')
except KeyError:
    print(name, "was not found.")
```

::::div{.flex style="width: 110%; margin-left: -2em;"}
:::div{.flexc}
:span[No error]{.sans}
```output
Enter name: Reza
Enter grade to add: 5
{'Reza': 95.0}
```
:::

:::div{.flexc}
:span[ValueError]{.sans}
```output
Enter name: Reza
Enter grade to add: 10x
Grade should be a number!
```
:::

:::div{.flexc}
:span[KeyError]{.sans}
```output
Enter name: Dev
Enter grade to add: 5
Dev was not found.
```
:::
::::

## :style{.ppt-f95}

We can have a :b[default except block] without any exception type to handle exception of any kind. 

::::hgrid{cols="3fr 1fr" margin="0.5em 0 1em -2em"}
```python
student_grades = {"Reza": 90.0}

try:
    name = input('Enter name: ')
    grade = float(input("Enter grade to add: "))
    student_grades[name] += grade
    print(no_such_variable)  # error here
except ValueError:
    print('Grade should be a number!')
except KeyError:
    print(name, "was not found.")
except:
    print("Some error occured.")
```
:::div
```output
Enter name: Reza
Enter grade to add: 5
Some error occured.
```
(Again, only one of the except-blocks will execute.)
:::
::::

## 

:::redbox
In general it is :em[not a good practice] to catch all errors using a default block.  
Instead, specific errors should be handled explicitly by using an exception type.
:::

## `finally` block :style{.ppt-f95}

- We can have an optional `finally` block in a `try` statement; it is always executed whether an exception occurs in `try` block or not. 
- It is useful to clean up resources (e.g. closing a file), which needs to be done even when exceptions occur.

```python
try:
    # try-block: code that may cause runtime error(s)
except Error1:
    # handle the Error1 here
except Error2:
    # handle the Error2 here
finally:
    # this block always executes
```

## 

For this example, download the files `read_matrix.py` and `matrixdata.txt` from Ed Lesson and keep it in the same folder as the program.

## When to use try statement 

- It is a bad practice to use a try/except to "hide" bugs in the program!
- try/except should be used when we know that a specific error may occurs and there is no other way to handle it

## :style{.ppt-f90}

::::hgrid{margin="0"}
:::div
:span[Good practice]{.sans}
```python
try:
    number = float(input("Enter a number: "))
except ValueError:
    print('Number is not valid!')
```
:::
because there is no other better way to check if a string contains a valid number.
::::

::::hgrid{margin="0"}
:::div
:span[Not a good practice]{.sans}
```python
student_grades = {"Reza": 90.0}
try:
    name = input('Enter name: ')
    student_grades[name] += 10
except KeyError:
    print(name, "was not found.")
```
because there is another way to do this (shown on right ->)
:::
```python place="center"
student_grades = {"Reza": 90.0}

name = input('Enter name: ')

if name in student_grades:
    student_grades[name] += 10
else:
    print(name, "was not found.")
```
::::

## Where do Exceptions come from? 

`raise` statement is used to throw an exception from our code to tell Python that an unexpected case or error has occurred.

```python lineno=false
raise SomeException("Some message")
```

Check `euclidean_distance` function in `distance.py` and `distance2.py`.

An exception raised in this way must be handled using `try` statements, otherwise Python will stop execution with the error as usual.

## Example

How exceptions are raised in Python modules?  
Open the following link and search for `raise`: 
https://github.com/python/cpython/blob/main/Lib/random.py

## Checking type of an object

```python
# isinstance(obj, class):
#       Return whether an object is an instance of a class

x = 123
print(isinstance(x, int))  # True
print(isinstance(x, float))  # False

x = "apple"
print(isinstance(x, str))  # True

x = [1, 5, 9]
print(isinstance(x, list))  # True
print(isinstance(x, tuple))  # False
```

##

```python
# isinstance(obj, tuple_of_classes):
#    A tuple of classes, e.g. isinstance(x, (A, B, ...)), may be given.
#    Equivalent to isinstance(x, A) or isinstance(x, B) or ...

x = 3.14
print(isinstance(x, (int, float)))  # True

x = [1, 5, 9]
print(isinstance(x, (list, tuple)))  # True

x = (11, 51, 4)
print(isinstance(x, (list, tuple)))  # True
```

##

:::greenbox
Time for some problems on Ed Lessons.
:::

::divider



8.2 — Shallow vs. deep copy, Handling exceptions


## Objects

- An object consists of data and a set of methods can be provided to work with it. 
- For example, a string is a collection of characters and methods like :code[isupper] or :code[split] can be called :i[on it].
- Python is an object-oriented language. This means that it uses objects to represent data and provides methods related to them.

## Object-oriented programming (OOP)

- Up to now, we have been using functions to organize our code, and built-in types :code[(list, str, list, or dict)] to organize our data.
- OOP is a way to use programmer-defined data classes to organize code and data.


## Class and objects

- A class is like a :i[blueprint/template] for creating objects. It specifies what data the objects have and what methods can operate on the data.
- An object is an :sc[instance] of some class. The terms :i[instance] and :i[object] are used interchangeably.

## Example — Student

We want to define a class that would be a good template for objects representing students.

::::hgrid{margin="0"}
:::div
Useful data: 
- Name
- Student ID
- Current courses 
- Past grades
:::
:::div
Useful methods: 
- compute_GPA 
- add_course
- drop_course
:::
::::

Each instance of the class (i.e., each object) would represent one particular student.

## Defining a class

```python
# This class does not contain any useful code yet
class MyClass:
   """ a new data type """
   pass
```

- Class names should follow the UpperCamelCase convention.  
- In a Python file, we can define as many classes as we want.  

## Instantiating a class

```python
class Student:
    """ Represents a student """
    pass

# We can now create an object using the constructor Student()
student1 = Student() 
print(student1)  # <__main__.Student object at 0x7fa7806c9310>

student2 = Student() 
print(student2)  # <__main__.Student object at 0x7fa7806c9290>
```

The variables `student1` and `student2`refer to two different objects of class `Student`.  

## Attributes

- We can create a variable that belongs to a specific object. These variables are called :sc[attributes]. 
- We create an attribute by assigning it a value using the dot notation: `object.attribute = value`
- Attributes can be accessed only through the object they belong to, using dot notation: `object.attribute`

##

```python
class Student:
    """ Represents a student """
    pass

student1 = Student()
# Create an attribute inside the student1 object
student1.name = "Reza"

# Use the attribute inside student1 object:
print(student1.name)  # Reza

student2 = Student()
print(student2.name)
# AttributeError: 'Student' object has no attribute 'name'

print(name)  # NameError: name 'name' is not defined
```

## Visualization

:::div{.ppt-scale-1_25}
<iframe width="800" height="400" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=class%20Student%3A%0A%20%20%20%22%22%22%20Represents%20a%20student%0A%20%20%20%22%22%22%0A%0Astudent1%20%3D%20Student%28%29%0Astudent1.name%20%3D%20%22Deven%22%0Aname%20%3D%20student1.name%0Aprint%28name%29%0A&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::

## Try it!

- Define a class `Student`.
- Write a function that takes as arguments a string `name` and an integer `id_num` and returns a `Student` object with two attributes `name` and `id_num`.
-  Write a function that takes as arguments two Student objects and returns the `name` of the student with the larger `id_num`.
- Test the above functions by creating two objects of Student class.

Code available in the file `student_example1.py`.

##

:::redbox
So far, we saw how to create attributes in an object, from outside a class. That is not how we usually create attributes. It was done for demonstration purposes to understand what attributes are.
:::

## Constructor and `__init__` method

- A constructor in an expression of form `MyClass(arg1, arg2, ...)` which creates an object of class `MyClass`. For example, `Student()` or `Student("Reza", 1234)`
- In Python, we define a special method named `__init__` (known as initializer method). It is invoked automatically whenever a new object is created using a contructor.

```python
class MyClass:
    def __init__(self):
        # do something when the object is being created
```

##

Let's write an `__init__` method for the `Student` class that takes no arguments (besides `self`) and prints out "Creating a new student".

```python
class Student:
    """ Represents a student """
    
    def __init__(self):
        print("Creating a new student")


# constructor without arguments:
student1 = Student()  # __init__ will be called
```
```output
Creating a new student
```

## Constructor with arguments

The constructor can have arguments which are typically used to create the attributes and set their initial values.

Now, let's modify the `__init__` method to add more arguments:
- `name` (string) of the student and their `id_num` (int)
-  Create attributes `name` and `id_num` using `self` and set their values to the respective arguments.

Code available in the file `student_example2.py`.

What happens in example above if we do not create attributes in `__init__` ?

## Defining Methods

We can define methods inside a class using `def` keyword.

:sc[Instance methods] – methods that are associated or bound to instances of a class. 

- These methods are called on an instance (object) and they can access attributes specific to that instance.

##

```python
class MyClass:
    def my_method(self, argument1, argument2, ..., argumentN):
        # do something 
```

The first argument of every instance method is always refers to the object on which we are calling the method.
```python
obj = MyClass()  # Create an instance

# call my_method on obj
obj.my_method(argument1, argument2, ..., argumentN)  
```

By convention, the first argument is always named `self`. (`self` is not a keyword! If we use any other name instead of `self`, it would not be an error.)

## Example continued

Let's go back to the Student class:

- Add a method `display_info()` that displays the information of a student i.e. prints the attributes of the instance.

Code available in the file `student_example3.py`.

## 

:::div{.ppt-scale-1_25}
:span[Understanding `self`]{.sans .ppt-f70}
<iframe width="930" height="500" scrolling="no" style="overflow: hidden;" frameborder="0" src="https://pythontutor.com/iframe-embed.html#code=class%20Student%3A%0A%20%20%20%20def%20__init__%28self,%20student_name,%20id_num%29%3A%0A%20%20%20%20%20%20%20%20self.name%20%3D%20student_name%0A%20%20%20%20%20%20%20%20self.id_num%20%3D%20id_num%0A%20%20%20%20%0A%20%20%20%20def%20display_info%28self%29%3A%0A%20%20%20%20%20%20%20%20print%28%22Name%20of%20student%3A%22,%20self.name%29%0A%20%20%20%20%20%20%20%20print%28%22Student%20ID%3A%22,%20self.id_num%29%0A%0As1%20%3D%20Student%28%22Reza%22,%2026000%29%0As1.display_info%28%29%0As2%20%3D%20Student%28%22Jane%22,%2026001%29%0As2.display_info%28%29&codeDivHeight=400&codeDivWidth=450&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false"> </iframe>
:::


::divider


9.1 — Object Oriented Programming (OOP)



## Defining functions/methods with keyword arguments

A keywords argument has a default value in function or method definition.

```python lineno=false margin="1em 0"
def func(pos1, pos2, ..., name1=value1, name2=value2, ...):
```

Here, `pos1`, `pos2`, etc are positional arguments and  
`name1`, `name2`, etc are keyword arguments with default values `value1`, `value2`, respectively.

Keyword arguments cannot appear before positional arguments.

##

If the function is called without passing a keyword argument, that argument gets its default value.

```python
def greet(name, greeting="Hello", num_of_times=1): 
    for i in range(num_of_times):
        print(greeting, name)

# try the following one at a time:
# greet("Dev")
# greet("Dev", greeting="Hi")
# greet("Dev", num_of_times=3)
# greet("Dev", greeting="Hi", num_of_times=3)
# greet("Dev", num_of_times=3, greeting="Hi")
```


## OOP continued :style{.ppt-f90}

```python
class Student:
    """ Represents a student. """
    
    def __init__(self, student_name, id_num):
        self.name = student_name
        self.id_num = id_num
    
    def display_info(self):
        print("Name of student:", self.name)
        print("Student ID:", self.id_num)


new_student = Student("Bob", 260000000)
new_student.display_info()
# Name of student: Bob
# Student ID: 260000000
```

##

Let's add a new attribute to store courses and a new method which allows adding a course.

```python
s1 = Student("Robin", 26005)
s1.add_course("COMP 208")
s1.add_course("POLI 220", pass_fail=True)
s1.add_course("MATH 250")
s1.display_info()
```

```output
Name of student: Robin
Student ID: 26005
Courses: COMP 208, POLI 220 (pass/fail), MATH 250
```

##

- Add an attribute `courses`, initializing it to empty dictionary. This dictionary will store a course name as a key and a boolean value to indicate whether the course is registered as pass/fail.
- Update `display_info` method to also display a comma-separate list of course names. If there are no courses in the `courses` dictionary, do not display any line for it.
- Add a method `add_course` that takes as a course name (`str`) and a keyword argument `pass_fail` (default value: `False`) and adds them to the attribute `courses`.

Code available in the file `student_methods.py`.

## Displaying objects: `__str__` method

When we display `student1` we see what class the object belongs to, and the identity of the object.

```python
s1 = Student("Dev", 26001)
print(s1)
```
```output
<__main__.Student object at 0x7f8cd66aa890>
```

Wouldn't it be nice to display `name`, `id_num` and other attributes when we do `print(student1)`?


## `__str__` method 

- We can change the string representation of our class objects by implementing a method called `__str__` in our class.

    ```python
    def __str__(self):
        # must return a string
    ```

- If we do that, then when we call `print(obj)` or `str(obj)` with an instance `obj` of our class, `__str__` method is called automatically and the returned string is used.

## Try it!
In the `Student` class, add a `__str__` method that returns a string in the following format:
```
Name: <name attribute>
Student ID: <id_num attribute>
Courses: <comma-separated courses>
```

Then, try to use print with an object of Student class.

Code available in the file `student_str.py`.

## Example — List of Student objects

```python
students = [Student("Dev", 260001),
            Student("Reza", 260005)]

# Create a student object and append it to the list
students.append(Student("Alice", 260011))

print(students[2])  # uses __str__ of Student class
# Name: Alice
# Student ID: 260011
# Courses: None registered.
```

##

```python
# Continued from previous slide:

print(students) # Does not use __str__ of Student class
# [<__main__.Student object at 0x10ad16100>,
#  <__main__.Student object at 0x10ad169d0>,
#  <__main__.Student object at 0x10ad16a00>]


for s in students:
    print(s)  # uses __str__ of Student class
```

## 

Try questions on Ed Lessons.

## More on special methods

https://docs.python.org/3/reference/datamodel.html#special-method-names

"A class can implement certain operations that are invoked by special syntax (such as arithmetic operations or subscripting and slicing) by defining methods with special names."

See the files `point.py` and `point_tester.py`. 

## `zip` function

`zip(x, y)` function creates an iterable of tuples $(x_i, y_i)$ where $x_i$ is element from `x` and $y_i$ is element from `y`.

```python
x_values = [0.5, -2, 5, 10]
y_values = [-1.5, 3, -3.5, 20]

points = list(zip(x_values, y_values))
print(points)
# [(0.5, -1.5), (-2, 3), (5, -3.5), (10, 20)]
```

##

:::div{.flex}
```python
x = [1, 2.5, 5]
y = [2, 4, 10.5]

total = 0
for i in range(len(x)):
    total += x[i] * y[i]
    
print(total)
```
```python
x = [1, 2.5, 5]
y = [2, 4, 10.5]

total = 0
for x, y in zip(x, y):
    total += x * y
    
print(total)
```
:::


What happens when one of the argument lists of `zip` is shorter than the other?

## Truth Value Testing

Any object can be tested for truth value, e.g. when used in an if or while condition.

```python
x = [1, 2, 3]

if x:
    print("do something")
else:
    print("do other thing")
```

##

By default, an object is considered true 
- unless its class defines either a special  `__bool__()` method that returns False or a `__len__()` method that returns zero, when called with the object. 

Here are most of the built-in objects considered false:

- Constants defined to be false: `None` and `False`
- Zeros: `0`, `0.0`
- empty sequences and collections: `""`, `tuple()`, `[]`, `{}`, `set()`, `range(0)`

##

Incorrect:

```python
ans = input('Are you sure? ')

if ans == 'y' or 'yes':
    print('Installing...')
```

Correct:

```python
ans = input('Are you sure? ')

if ans == 'y' or ans == 'yes':
    print('Installing...')
```

::divider

9.2 — Keyword arguments, More on OOP


## What is NumPy?
- The core library for scientific computing
- Provides a new data structure called an "array"
    - It is like a list, but more efficient
    - Provides many functions that work with NumPy arrays
- https://numpy.org

## Installing NumPy

- If you use Thonny, go to Tools -> Manage packages. Type `numpy` in the
search bar and click "Search on PyPI". Then click Install.
- If you do not have Thonny, you can do so by typing the following commands in the terminal:
    ```
    python -m pip install -U pip  
    python -m pip install -U numpy  
    ```

## What is a NumPy array?
- A NumPy array is a multidimensional collection/grid of items of same type .
    - Multidimensional: it could be a linear array (like a list e.g. vector) or a 2D array (like a list of lists e.g. matrix), 3D array etc.
- Unlike a regular Python list,
    - All the values in a NumPy array must have the same type.
    - A NumPy array's size cannot be changed after creation.
        - All such operations that change the size (e.g. adding/removing items) result in a copy of the array.

## Creating an array

```python
import numpy as np

# Create a NumPy array from a Python list
arr = np.array([1, 2, 3])
print(arr)  
# [1 2 3] 
# note the lack of commas in the output

print(type(arr))  # <class 'numpy.ndarray'>

# convert a tuple object to numpy array
x = np.array((1, 10, 100))
print(x)  # [ 1 10 100]
```

##

We can specify the data type of elements when creating an array.

```python
import numpy as np

# these floats will be converted to ints (by truncation)
x = np.array([1.2, 3.14, 10.65], dtype=int)
print(x)  # [ 1 3 10]
print(x.dtype)  # int64

# We can also specify a NumPy-defined data type
x = np.array([10, 20, 30], dtype=np.float64)
print(x)  # [10. 20. 30.]
print(x.dtype)  # float64
```

## Shape and dimensions of a NumPy array

- The number of dimensions is how many levels of nested arrays there are. e.g. 1D array, 2D array, etc. It can be obtained by accessing the `ndim` attribute.
- `shape` attribute of a NumPy array is a tuple containing size/length in each dimension.

```python
import numpy as np

x = np.array([10, 20, 30])

print(x.ndim) # 1
print(x.shape) # (3,)
```

##

```python
import numpy as np

x = np.array([[10, 20, 30], [40, 50, 60]])
print(x)
# [[10 20 30]
#  [40 50 60]]

print(x.ndim) # 2
print(x.shape) # (2, 3) <-- row, col
```

## Indexing a NumPy array 

```python
import numpy as np

arr = np.array([2, 4, 8])
print(arr[0], arr[1], arr[2])  # 2 4 8

# we can modify existing elements.
arr[0] = 1
print(arr)  # [1 4 8]
```

## Other ways to create arrays

```python
import numpy as np

# create an array of 0's, with shape (2,).
x = np.zeros(2)
print(x)
# [0. 0.] 
# dots above mean float values

# create an array of all 1's, with shape (3,),
# of integer type.
y = np.ones(3, dtype=int)
print(y)  # [1 1 1]
```

##

```python
# create an array of shape (5,) filled with one value
x = np.full(5, 7)
print(x)
# [7 7 7 7 7]

# create an array of 4 random values in the interval [0.0, 1.0).
y = np.random.random(4)
print(y)
[0.70260439 0.68529032 0.59847495 0.88655089]
```

## Some useful numpy functions

```python
import numpy as np

# Similar to the built-in range() function, 
# we can use arguments start, stop and step.
x = np.arange(10)
print(x)
# [0 1 2 3 4 5 6 7 8 9]

# Unlike range(), float numbers are allowed.
x = np.arange(10.0, 20.0, 2.5)
print(x)
# [10.  12.5 15.  17.5]
```

##

When we want to create a list of evenly-spaced numbers, it is better to use `np.linspace()` than `np.arange()`.

```python
import numpy as np

# Create an array of 5 evenly spaced numbers in interval [0, 1]
x = np.linspace(0, 1, 5)
print(x)
# [0. 0.25 0.5 0.75 1. ]

# 7 evenly spaced numbers in interval [10, 100]
x = np.linspace(10, 100, 7)
print(x)
# [ 10. 25. 40. 55. 70. 85. 100.]
```

## Broadcasting operations

- An arithmetic operation between an array and a scalar (number) is applied to all elements of the array. It is known as :sc[broadcasting].
- It does not modify the given array; instead a new copy is created.

```python
import numpy as np
arr = np.linspace(-1.0, 5.0, 7)
print(arr)  # [-1. 0. 1. 2. 3. 4. 5.]

# Multiplication is broadcasted to each element.
print(arr * 6)  # [-6. 0. 6. 12. 18. 24. 30.]
```

##

```python
# Unary minus
print(-arr)
# [ 1. -0. -1. -2. -3. -4. -5.]

# Other operators work in same way
print(arr / 5)
# [-0.2 0. 0.2 0.4 0.6 0.8 1. ]

print(arr + 4)
# [3. 4. 5. 6. 7. 8. 9.]

print((arr + 3) * 2)
# [ 4. 6. 8. 10. 12. 14. 16.]
```

##

Unlike Python lists, NumPy arrays implement operators such as `*` to perform arithmetic operations.

```python
import numpy as np

x = [1, 2, 3] # Python list
y = x * 5
print(y)
# [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]

x = np.array([1, 2, 3])
y = x * 5
print(y)
# [ 5 10 15]
```

##

NumPy also defines math functions that broadcast to all elements in the array.

```python
import numpy as np

arr = np.linspace(-1.0, 5.0, 7)

print(np.sin(arr))
# [-0.841 0. 0.841 0.909 0.141 -0.757 -0.959]

print(np.exp(arr)) # e^x function
# [ 0.368 1. 2.718 7.389 20.086 54.598 148.413]
```

## Vector operations

An arithmetic operation between arrays is done element-wise.  It is also called a :sc[vectorized] operation. 

```python
import numpy as np

a = np.array([34.0, -12.0, 5.0])
b = np.array([68.0, 5.0, 20.0])
print(a + b)  # [102. -7. 25.]
print(a / b)  # [ 0.5 -2.4 0.25]
```

## Example

Write code to evaluate the expression below using NumPy:  
$$
s = \sum_{k=0}^{100} \sqrt{\frac{k \pi}{100}} sin \frac{k \pi}{100}
$$

##

:::solution
```python
import numpy as np

k = np.arange(0, 101)
x = k * (np.pi / 100)
s = np.sum(np.sqrt(x) * np.sin(x))
print(s)  # 77.51389798916512
```
:::

## Comparing the performance of numpy vs pure python solution

:::hgrid
```python
import numpy as np
import time

start = time.time()

N = 10000000
k = np.arange(0, N+1)
x = k * (np.pi / N)
s = np.sum(np.sqrt(x) * np.sin(x))
print(s) 

print("Time:", time.time() - start)
```

```python
import math
import time

start = time.time()

N = 10000000
s = 0
for k in range(0, N+1):
    x = k * (math.pi / N)
    s += math.sqrt(x) * math.sin(x)
print(s) 

print("Time:", time.time() - start)
```
:::

## Slicing NumPy arrays
Similar to lists, we can slice a 1D NumPy array.
```python
import numpy as np

y = np.array([0.0, 1.3, 5.0 , 10.9, 18.9, 28.7, 40.0])
print(y[1:4]) # print from index 1 until but not including index 4
# [ 1.3 5. 10.9]

print(y[::-1]) # reversed copy
# [40. 28.7 18.9 10.9 5. 1.3 0. ]
```

## Copying NumPy arrays
- We can use the `array.copy()` method to get a copy of an array.
- Changes to the copy will not affect the original array.

:::hgrid
```python
import numpy as np

a = np.array([[1, 2, 3], [4, 5, 6]])

b = a.copy()
b[1][2] = 100

print(a)
print(b)
```

```output
[[1 2 3]
 [4 5 6]]
[[  1   2   3]
 [  4   5 100]]
```
:::

## Matrix in form of a 2D NumPy array

```python
import numpy as np

# convert a list of lists into 2D NumPy array
m = np.array([[1, 2, 3], [4, 5, 6]])
print(m)
# [[1 2 3]
#  [4 5 6]]

# create an array of all 0's of shape (2, 2).
# By default, dtype is float64.
print(np.zeros((2, 2))) # (2, 2) is a tuple.
# [[0. 0.]
#  [0. 0.]]
```

##

```python
import numpy as np
# create an array full of 7's, of shape (2, 3).
print(np.full((2, 3), 7))
# [[7 7 7]
#  [7 7 7]]

# create an array of random values in interval [0, 1).
print(np.random.random((2, 2)))
# [[0.1782372 0.35920979]
#  [0.9368368 0.9005017 ]]

# create an identity matrix of shape (3, 3).
print(np.eye(3))
# [[1. 0. 0.]
#  [0. 1. 0.]
#  [0. 0. 1.]]
```

## Reshaping arrays
```python
import numpy as np

# We can also create a matrix from a 1D array, using np.reshape()
c = np.arange(6)
print(c)  # [0 1 2 3 4 5]

# change the shape to (2, 3).
d = np.reshape(c, (2, 3))
print(d)
# [[0 1 2]
#  [3 4 5]]
```

## Indexing a 2D array
We can index into a multi-dimensional NumPy array by providing a comma-separated list of the indices.

```python
import numpy as np

m = np.array([[1, 2, 3], [4, 5, 6]])
print(m.shape)  # (2, 3)

print(m[0, 0])  # 1
print(m[0, 1])  # 2
print(m[1, 0])  # 4
print(m[1, 2])  # 6
```

## Matrix (2D array) operations

```python
import numpy as np

# Broadcasting
b = np.array([[1, 4, 5], [9, 7, 4]])
print(2 + b)
# [[ 3 6 7]
#  [11 9 6]]

print(np.sin(b))
# [[ 0.841 -0.757 -0.959]
#  [ 0.412 0.657 -0.757]]
```

##

```python
import numpy as np

# Element-wise product of matrices
b = np.array([[1, 4, 5], [9, 7, 4]])
c = np.array([[0, 1, 2], [3, 4, 5]])

# Note: both matrices must have the same shape
print(b * c)
# [[ 0 4 10]
#  [27 28 20]]
```

##

To perform matrix multiplication, we use the dot() function.

```python
import numpy as np

b = np.array([[1, 4, 5], [9, 7, 4]])
d = np.array([[ 4, 2], [ 9, 8], [-3, 6]])

# shapes must be (M, N) dot (N, P) --> (M, P)
print(np.dot(b, d))
# [[25 64]
#  [87 98]]
```

## Slicing a 2D array

::img{src="week10/slicing.png" style="width: 85%; margin: 0.5em auto 0 auto"}
:span[(source: https://github.com/ContinuumIO/tutorials/blob/master/NumPy.pdf)]{.ppt-f80}

##

```python
import numpy as np

a = np.array([[ 1,  2,  3,  4,  5,  6],
              [11, 12, 13, 14, 15, 16],
              [31, 32, 33, 34, 35, 36],
              [41, 42, 43, 44, 45, 46],
              [51, 52, 53, 54, 55, 56],
              [61, 62, 63, 64, 65, 66]])

print(a[:, 1])
# [ 2 12 32 42 52 62]

print(a[::2, ::3])
# [[ 1  4]
#  [31 34]
#  [51 54]]
```

##

```python
import numpy as np

a = np.array([[ 1,  2,  3,  4,  5,  6],
              [11, 12, 13, 14, 15, 16],
              [31, 32, 33, 34, 35, 36],
              [41, 42, 43, 44, 45, 46],
              [51, 52, 53, 54, 55, 56],
              [61, 62, 63, 64, 65, 66]])

print(a[1, 2:5])
# [13 14 15]

print(a[3:5, 4:6])
# [[45 46]
#  [55 56]]
```

::divider



10.1 — NumPy



## Copies and views of Numpy array 

When manipulating arrays, their data may or may not be copied into a new array. Let’s look at different cases.

```python
x = np.arange(12)

# Just a new name, no data is copied
y = x

print(x)  # [ 0  1  2  3  4  5  6  7  8  9 10 11]
print(y)  # [ 0  1  2  3  4  5  6  7  8  9 10 11]
print(x is y) # True, as they are same objects
```

##

When we :b[index or slice] a numpy array, the resulting array :b[shares same data] i.e. the result array is a :sc[view] for the original array.

:::hgrid
```python
x = np.arange(1, 13).reshape((3, 4))
print(x)

y = x[:, 1:3]  # x and y share same data
print(y)

y[0, 0] = 123  # Changing the shared data
print(x)
print(y)
```
```output
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]
[[ 2  3]
 [ 6  7]
 [10 11]]
[[  1 123   3   4]
 [  5   6   7   8]
 [  9  10  11  12]]
[[123   3]
 [  6   7]
 [ 10  11]]
```
:::

##

`copy()` method of a numpy array can be used to create a new array which :b[does not share data] with the original array. 

:::hgrid
```python
x = np.arange(1, 13).reshape((3, 4))
print(x)

y = x[:, 1:3].copy()
print(y)

y[0, 0] = 123  # Changes the copy only
print(x)
print(y)
```
```output
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]
[[ 2  3]
 [ 6  7]
 [10 11]]
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]
[[123   3]
 [  6   7]
 [ 10  11]]
```
:::

##

`np.array` infers `dtype` based on types of numbers in the argument.

```python
import numpy as np

x = np.array([10, 20, 30])
print(x) #[10 20 30]
print(x.dtype) # int64

x = np.array([1.2, 3.14, 10.15])
print(x) #[ 1.2   3.14 10.15]
print(x.dtype) # float64

x = np.array([10.0, 20, 30])
print(x) #[10. 20. 30.]
print(x.dtype) # float64
```

##

```python
import numpy as np

# we can explicity specify what dtype we want:
x = np.array([10, 20, 30], dtype=float)
print(x) #[10. 20. 30.]
print(x.dtype) # float64

# float is truncated to int (not rounded)
x = np.array([1.2, 3.14, 10.65], dtype=int)
print(x) #[ 1  3 10]
print(x.dtype) # int64
```

## Different shapes for different purposes 

:::hgrid{margin="0" gap="1em"}
```
[1.0 5.0 3.5 4.0 5.0 1.2]
```
One point in 6D euclidean space
:::

:::hgrid{margin="0" gap="1em"}
```
[[1.0 5.0 3.5]
 [4.0 5.0 1.2]]
```
Two points in 3D euclidean space
:::

:::hgrid{margin="0" gap="1em"}
```
[[1.0 5.0]
 [3.5 4.0]
 [5.0 1.2]]
```
Three points in 2D euclidean space
:::

##

:::hgrid
```python
import numpy as np

x = np.arange(1, 13) # 1D array
print(x)

# 2D array, a 3x4 matrix
matrix1 = x.reshape((3, 4))
print(matrix1)

# 2D array, a 2x6 matrix
matrix2 = matrix1.reshape((2, 6))
print(matrix2)

 # 1D array
y = matrix2.reshape((12,))
print(y)
```

```output
[ 1  2  3  4  5  6  7  
  8  9 10 11 12]

[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

[[ 1  2  3  4  5  6]
 [ 7  8  9 10 11 12]]

[ 1  2  3  4  5  6  7  
  8  9 10 11 12]
```
:::

## Special values — `numpy.nan`, `numpy.inf`
Numpy has special values to represent invalid or extreme values that result from numerical computation
- `numpy.nan` (not a number)
- `numpy.inf`  (infinity)

```python
import numpy as np

arr = np.array([-1, 0, 1, 2, 3, 4])

print(np.log(arr))
#[  nan   -inf  0.  0.69314718 1.09861229 1.38629436]
```

##

```python
# Any operation on np.nan results in np.nan
print(np.nan * 10, 0 / np.nan)
# nan nan

# Some operations are allowed on np.inf

print(np.inf, -np.inf)
# inf -inf

print(0 / np.inf, 1 / np.inf)
# 0.0 0.0

print(np.inf * np.inf, 100 + np.inf)
# inf inf
```

## Slicing 2D array

::img{src="week10/course_array.png" style="width: 90%; margin: 0 auto"}

##

```python
import numpy as np

grades = np.array([[94, 84, 97, 79],
                   [81, 88, 93, 85],
                   [87, 95, 86, 77]])

print('Grades for student 1, course 2:')
print(grades[1, 2])  # 93


print('All grades for student 2:')
print(grades[2, :])  # [87 95 86 77]

print('All grades for course 0:')
print(grades[:, 0])  # [94 81 87]
```

## Assigning values using indices and slices

```python
import numpy as np

grades = np.array([[94, 84, 97, 79],
                   [81, 88, 93, 85],
                   [87, 95, 86, 77]])

# Setting same value to all indices in the slice
grades[0:2, 1:3] = 100
print(grades)
# [[ 94 100 100  79]
#  [ 81 100 100  85]
#  [ 87  95  86  77]]
```

##

```python
import numpy as np

grades = np.array([[94, 84, 97, 79],
                   [81, 88, 93, 85],
                   [87, 95, 86, 77]])

# Setting values from array of same shape
grades[0:2, 1:3] = np.array([[10, 20], [30, 40]])
print(grades)
# [[94 10 20 79]
#  [81 30 40 85]
#  [87 95 86 77]]
```


## Matplotlib

- Matplotlib is an extensive Python library commonly used to generate different types of plots.
- To install Matplotlib: if you use Thonny, go to Tools -> Manage packages. Type `matplotlib` on the
search bar and click "Search on PyPI". Then click Install.
- If you do not have Thonny, you can do so by typing the following commands in the terminal:
    ```
    python -m pip install -U pip  
    python -m pip install -U matplotlib  
    ```

## matplotlib.pyplot

- `matplotlib.pyplot` is a module in the package Matplotlib. 
- This is the module we'll be using to create plots.
- To use it, we first need to import it
    ```
    import matplotlib.pyplot as plt
    ```
- For more details: https://matplotlib.org/devdocs/api/pyplot_summary.html

## Example – A Line plot

We can use the function plot to create a line plot between the points in the input sequence.

:::hgrid
```python
import matplotlib.pyplot as plt

some_numbers = [3, 1, 5, 2, 9, 3] 
plt.plot(some_numbers)
plt.show() # display figure
```

::img{src="week10/line1.png" style="width: 100%;"}
:::

##

In the previous example:
- We provided only one input to the function `plot`.
- If we do that, then the input values are going to be considered as the y-coordinates. Their corresponding x-coordinates are the indices of the list.
- In the example, we plot the following points: $(0, 3), (1, 1), (2, 5), (3, 2), (4, 9), (5, 3)$


## Example - two inputs

:::div{.flex}
```python
import matplotlib.pyplot as plt

x_coord = range(0, 10, 2)
y_coord = [0, 0, 9, 8, 2]
plt.plot(x_coord, y_coord)
plt.show()
```

::img{src="week10/line2.png" style="width: 50%; margin-left: 2em;"}

:::

## Example - a linear function
Using pyplot, we can plot the graph of the linear function $y = x + 5$.

:::div{.flex}
```python
import matplotlib.pyplot as plt

x_coord = range(15)
y_coord = [x + 5 for x in x_coord]

plt.plot(x_coord, y_coord)
plt.show()
```

::img{src="week10/linear.png" style="width: 50%; margin-left: 2em;"}

:::

## Plot title and axis labels

`plt.title(label)`: takes as argument a string and adds the title label to the figure.

`plt.xlabel(label)`: takes as argument a string and sets the label for the x-axis. 

`plt.ylabel(label)`: takes as argument a string and sets the label for the y-axis.

We can choose the font size of the labels using the keyword argument: `plt.title("First plot", fontsize=22)`

##

:::div{.flex}
```python
import matplotlib.pyplot as plt

x_coord = range(15)
y_coord = [x + 5 for x in x_coord]
    
plt.plot(x_coord, y_coord)

plt.title("First plot", fontsize=20)
plt.xlabel("x", fontsize=14)
plt.ylabel("y = x + 5", fontsize=14)

plt.show()
```

::img{src="week10/linear2.png" style="width: 50%; margin-left: 1em;"}
:::

## Colors, markers and line styles

- We can chose the style/color of the plots, the style/size of the markers, etc. Here is just a taste:

:::hgrid{cols="1fr 1fr 1fr" margin="0.5em -2em" gap="0.5em"}
::img{src="week10/colors.png" style="width: 100%;" }
::img{src="week10/linestyles.png" style="width: 100%; "}
::img{src="week10/markers.png" style="width: 100%;"}
:::

:span[More info: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.plot.html]{.ppt-f80}


## Using color, marker and line style

- The function plot can take as arguments one or two lists (for x and y coordinates) and a format string. 
- The format string consists of three parts: `[marker][line][color]`. Each part is optional.

:::div{.flex}
```python
import matplotlib.pyplot as plt

some_numbers = [3, 1, 5, 2, 9, 3]

# circle marker, dashed line, green
plt.plot(some_numbers, "o--g") 
plt.show() # display figure
```

::img{src="week10/colorplot.png" style="width: 40%; margin-left: 2em;"}

:::

## 

:b[Multiple plots in same figure]{.sans}

:::div{.flex}
```python
import matplotlib.pyplot as plt
from math import sin, cos, radians

x_coord = range(0, 540, 20)
y_sin = [sin(radians(x)) for x in x_coord]
y_cos = [cos(radians(x)) for x in x_coord]
    
# + marker, blue color and use label for legend
plt.plot(x_coord, y_sin, '+b', label="sin(x)")

# magenta color and use label for legend
plt.plot(x_coord, y_cos, 'm', label="cos(x)")
plt.legend()  # show legend
plt.show()
```
:::

##

::img{src="week10/twoplots.png" style="width: 110%;"}

## Saving a figure

- `plt.savefig(filename)`: Save the figure in a file (.jpg, .png, etc.)

```python
import matplotlib.pyplot as plt
from math import sin, radians

x_coord = range(0, 540, 20)
y_sin = [sin(radians(x)) for x in x_coord]

plt.plot(x_coord, y_sin, 'm')

# the figure won't be displayed, but saved in y_sin.png 
plt.savefig("myplot.png")
```

## Bar Plots

When working with data that can be broken down into categories, it might be useful for us to use a bar plot instead. 

```python
import matplotlib.pyplot as plt

mtl_pop = [1293992, 1080545, 1015420, 1016376, 1620693, 1704694]
years = ['1966', '1976', '1986', '1996', '2006', '2016']

plt.bar(years, mtl_pop)

plt.title("Population of Montreal")
plt.show()
```

##

::img{src="week10/barplot.png" style="width: 110%;"}

##  NumPy and Matplotlib
Matplotlib functions work with NumPy arrays as well.

```python
import numpy as np
import matplotlib.pyplot as plt

x_values = np.linspace(0, 8, 501)
y_values = np.sin(x_values ** 2)  # computes sin(x^2)
plt.plot(x_values, y_values)
plt.show()
```

::divider



10.2 — More Numpy, Plotting using Matplotlib


## Numpy arrays and `for` loop

:::hgrid
```python
import numpy as np

x = np.arange(1, 13)
print(x)
print(x.shape)

for i in range(x.shape[0]):
    x[i] = x[i] ** 2
    
print(x)
print(x.shape)
```

```output
[ 1  2  3  4  5  6  
7  8  9 10 11 12]
(12,)
[  1   4   9  16  25  36  
49  64  81 100 121 144]
(12,)
```
:::

##

:::hgrid
```python
import numpy as np

matrix = np.arange(1, 13).reshape((3, 4))
print(matrix)
print(matrix.shape)

for i in range(matrix.shape[0]):
    for j in range(matrix.shape[1]):
        matrix[i, j] = matrix[i, j] ** 2
    
print(matrix)
print(matrix.shape)
```

```output
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]
(3, 4)
[[  1   4   9  16]
 [ 25  36  49  64]
 [ 81 100 121 144]]
(3, 4)
```
:::

## Comparison operation with NumPy array

When comparison operators are used with NumPy arrays, result is an array of boolean values.

```python
import numpy as np

arr = np.array([10, 11, 12, 13, 14, 15, 16, 17])
print(arr % 2 == 0) # produces numpy array of booleans
# [ True False  True False  True False  True False]

arr = np.array([-10, -20, 0, 24, -50, 33, 10])
print(arr > 0)
# [False False False  True False  True  True]
```

##  Using a list/array of booleans as index

```python
import numpy as np

arr = np.array([10, 11, 12, 13])
indices = [True, False, False, True]
# For each i, select arr[i] if indices[i] is True:
print(arr[indices])  # [10 13]

arr = np.array([10, 11, 12, 13, 14, 15, 16, 17])
print(arr[arr % 2 == 0])  # [10 12 14 16]

arr = np.array([-10, -20, 0, 24, -50, 33, 10])
print(arr[arr > 0])  # [24 33 10]
```

## Using a list/array of integers as index

Multiple elements of a numpy array can be selected using a list or an array of indices.

```python
nums = np.arange(10, 100, 10)
# [10 20 30 40 50 60 70 80 90]

indices = [0, 1, 5]
print(nums[indices]) # [10 20 60]

# Output will be in same order as indices
indices = np.array([2, 8, 5, 1])
print(nums[indices]) # [30 90 60 20]
```

##

Indexing 2D arrays with list/array of indices:

:::hgrid{margin="0"}
```python
import numpy as np
matrix = np.arange(1, 13).reshape((3,4))
print(matrix)

# Select rows 0 & 2
row_indices = [0, 2]  
print(matrix[row_indices, :])

# Select columns 1 & 2
col_indices = [1, 2]
print(matrix[:, col_indices])

# Select numbers at (0, 1) and  (2, 2)
print(matrix[row_indices, col_indices])
```
```output
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

[[ 1  2  3  4]
 [ 9 10 11 12]]

[[ 2  3]
 [ 6  7]
 [10 11]]

[ 2 11]
```
:::

## Vector and Matrix operations in NumPy

```python
import numpy as np
v = np.arange(10, 70, 10)  # 1D array as vector
print(v)  #[10 20 30 40 50 60]

M = np.arange(10, 100, 10).reshape((3,3))  # 2D array as matrix
print(M)
# [[10 20 30]
#  [40 50 60]
#  [70 80 90]]

# ndarray.size attribute — total number of elements in ndarray
print(v.size)  # 6
print(M.size) # 9
```

## Stacking new rows/columns into a matrix

Size of new row/col must match that of the matrix row/col.

:::hgrid
```python
import numpy as np
M = np.arange(1, 7).reshape((2, 3))
print(M)

v = np.array([-1, -2])
M2 = np.column_stack([M, v])
print(M2)

w = np.array([5, 7, -1])
M3 = np.row_stack([M, w])
print(M3)
```
```output
[[1 2 3]
 [4 5 6]]
[[ 1  2  3 -1]
 [ 4  5  6 -2]]
[[ 1  2  3]
 [ 4  5  6]
 [ 5  7 -1]]
```
:::

## Matrix Multiplication

- Interactive explanation for matrix multiplication: https://observablehq.com/@meetamit/matrix-multiplication

- The `@` operator performs matrix multiplication with NumPy arrays. 
    - `np.dot` can also be used to do matrix multiplication.

- Recall that `*` operator performs element-wise multiplication.

##

```python
import numpy as np
A = np.arange(10, 70, 10).reshape((3, 2))
B = np.arange(10, 70, 10).reshape((2, 3))
print(A)
#[[10 20]
# [30 40]
# [50 60]]
print(B)
#[[10 20 30]
# [40 50 60]]

C = A @ B
print(C)
#[[ 900 1200 1500]
# [1900 2600 3300]
# [2900 4000 5100]]
```

##

```python
import numpy as np

A = np.array([[83, 10, 39],
              [29, 67, 81]])
print(A @ A)
# ValueError: matmul: Input operand 1 has a mismatch in 
# its core dimension 0, (size 2 is different from 3)
```

## Example

Let's compute the following
$$
    \small
    2A + AB - 3I
$$
where given matrices A and B (I is the identity matrix). Shapes of all matrices must match.

##

:::solution
```python
import numpy as np

A = np.array([[1, 5], [-2, 9]])
B = np.array([[2, 5], [1, -2]])
I = np.eye(2) # 2x2 identity matrix

result = 2 * A +  A @ B - 3 * I
print(result)
```
:::

## Powers of a matrix

```python
import numpy as np
from numpy.linalg import matrix_power

A = np.array([[1, 5], [-2, 9]])

# Cube of the matrix A
print(A @ A @ A)
#[[-109  405]
# [-162  539]]

# Another way, using library function:
print(matrix_power(A, 3))
```


##

:h1[Random numbers and Monte Carlo methods]{.sans}


## Python random module

```python
import random

nums = [5, 4, 3, 2, 100, 1]

# Randomly choose one item from mylist
print(random.choice(nums))  # 5

# Randomly choose a list of 3 items from the list
# An element in the list is chosen only once.
print(random.sample(nums, 3))  # [4, 5, 100]
```


## Random numbers in NumPy

```python
import numpy as np

# All output numbers below will change each time your run the code.
# But shape of arrays should remain same.

x = np.random.random() # a random float in [0, 1)
print(x)  # 0.2894424639826647

# array of 5 floats, each value in [0, 1)
nums = np.random.random(5)
print(nums)
# [0.564407   0.36047169 0.68956636 0.11457356 0.26594372]
```

##

```python
import numpy as np

# 3x2 matrix, each float in [0, 1)
matrix = np.random.random((3, 2))
print(matrix)
# [[0.573776   0.37419411]
#  [0.23126045 0.32425979]
#  [0.81373111 0.33039031]]

# random integer  in [1, 5)
x = np.random.randint(1, 5)
print(x)  # 2
```

##

```python
import numpy as np

# random array of size 7, each integer in [1, 5)
nums = np.random.randint(1, 5, 7)
print(nums)  # [4 4 1 3 3 1 4]

# 3x2 matrix, each integer in [1, 10)
matrix = np.random.randint(1, 10, (3, 2))
print(matrix)
# [[4 7]
#  [4 6]
#  [3 9]]
```

##

```python
import numpy as np

nums = [5, 4, 3, 2, 100, 1]
# choose a single number from list
x = np.random.choice(nums)
print(x)  # 4

# Choose 10 numbers from the list.
# Each number is chosen independently, so numbers may repeat.
many = np.random.choice(nums, 10)
print(many)
# [3 4 3 3 3 1 5 2 4 2]
```


## Example: throwing an unbiased die 

- Let's throw an unbiased six-sided die and count the number of occurrences of 4.

- Unbiased or unweighted means that every integer from 1 to 6 is equally likely to roll. That is, the die is "fair".

##

```python
import random

options = [1, 2, 3, 4, 5, 6] # six faces of the die
num_rolls = 1000

num_fours = 0
for i in range(num_rolls):
   roll = random.choice(options)
   if roll == 4:
      num_fours += 1

print("Frequency of 4:", num_fours / num_rolls)
```

##

Let's do the same using NumPy:

```python
import numpy as np

options = np.arange(1, 7) # six faces of the die
num_rolls = 1000

rolls = np.random.choice(options, num_rolls)
freq = rolls[rolls == 4].size / num_rolls

print("Frequency of 4:", freq)
```

## Example: throwing a biased or weighted die 

- Let's throw a biased, or weighted, six-sided die where we favor number 3 over others by giving it more "weight" or probability. 
    - Such a die would be called "unfair."

##

```python
import numpy as np

options = [1, 2, 3, 4, 5, 6]

# Assign unequal weights or probabilties to each choices
# Weights must sum to 1.0
weights = [.1, .1, .5, .1, .1, .1 ]

num_rolls = 1000

rolls = np.random.choice(options, num_rolls, p=weights)
freq = rolls[rolls == 3].size / num_rolls

print("Frequency of 3:", freq)
```

## Monte Carlo methods

- A type of algorithm that uses random sampling to solve problems.

- There are Monte Carlo methods for many different problems in physics, chemistry, AI and engineering.
    - https://en.wikipedia.org/wiki/Monte_Carlo_method#Engineering

- We will see a simple case here with a Monte Carlo method for integration.


## Finding the area of a complex shape

- Let's say we have a complex shape and we want to find its area.

- We will draw a rectangle around this shape, then sample random points inside the rectangle.

- Then we can estimate the area of the inner shape by multiplying the rectangle's area by the fraction of points that land inside the shape.

$$
\small
\textup{area}_\textup{shape} \approx \textup{area}_\textup{rectangle} * \frac{\textup{points}_\textup{inside}}{\textup{points}_\textup{inside} + \textup{points}_\textup{outside}}
$$


## Monte Carlo integration

- We can use the above idea of finding area to numerically integrate a function.

- For a given function $f(x)$, we define a rectangle that bounds $f(x)$ along X-axis between $[a, b]$ and along Y-axis between $[0, c]$,  where 					   
    $$
        \small
        c >= \max_{x \epsilon (a, b)} f(x)
    $$

- Then we can estimate the integral by randomly choosing points inside the rectangle, and using the formula of area from the previous slide.

##

Example:

- Consider the following function:
    $$
        \small
        f(x) = \left | sin(2\pi x)^5 - 2cos(3cos( \frac{x}{\pi} )^2)^3     \right |
    $$

- We can’t integrate this analytically (i.e. representing it in terms of standard math functions).

- So let's use Monte Carlo integration instead.

##

```python
import numpy as np
import matplotlib.pyplot as plt


def f(x): # x is numpy array
    y = np.sin(2 * np.pi * x) ** 5
    y -= 2 * np.cos(3 * np.cos(x / np.pi) ** 2) ** 3
    return np.abs(y)


x = np.linspace(0, 10, num=1001)
plt.figure()
plt.plot(x, f(x))
plt.show()
```

##

::img{src="week13/function.png" }

##

- Suppose we want to calculate the definite integral of $f(x)$ in interval $[0, 10]$

- We then choose the rectangle bounds as:
    - $[0, 10]$ along X-axis
    - $[0, 3]$ along Y-axis because from the plot
        $$
            \small
            3 >= \max_{x \epsilon (0, 10)} f(x)
        $$

- Then, we compute number of points below the function f(x) in the above defined rectangle

- Check `montecarlo_integration.py` for the implementation.

##

::img{src="week13/mc_integration.png"}

##

- There are several methods that can perform Monte Carlo integration.
- The one we've seen is called the rectangle method, or dart method. 
- It can only be used for simple functions and its accuracy is not very high.


::divider



11.1 — More Numpy, Linear algebra, Random numbers



## Motivation 

- We often want to analyze data points in the form shown below, where we have some dependent variables $y_i$ corresponding to some independent variables $x_i$.

::::hgrid{margin="0"}
:::div{style="display: inline-grid; grid-template-columns: repeat(5, 2.5em); grid-template-rows: repeat(2, 1fr);border: 1px solid #666666; margin-left: 3em;"}
::div[$x_0$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$x_1$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$x_2$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$...$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$x_n$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}

::div[$y_0$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$y_1$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$y_2$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$...$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
::div[$y_n$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:2.5em; width: 2.5em;"}
:::
::::

- The goal is to find a function $f(x)$ that either
    - passes through all the points exactly (:i[interpolation])
    - approximates data in a "best" possible way but not exactly (:i[curve fitting])

##

::img{src="week11/interpolation_curve_fitting.png" style="width: 50%;  margin: 1.5em 0 0 1em;"}
:div[Image from Kiusalaas, chap. 3.]{style="font-size: 0.6em; margin: -1em 0 0 1em;"}

## How interpolation and curve-fitting are useful?

- If we can find a function $f(x)$  that interpolates or approximates the data well,
    - We can try to predict new data points $(x_k, y_k)$.
    - We can better understand the underlying process that might have generated the data.


## Polynomial interpolation

- The simplest form of interpolation function is a polynomial function. 
- It is always possible to construct a polynomial $P(x)$ of degree $n$ that passes through $n+1$ data points.

::img{src="week11/poly_interpolation.png" style="width: 50%;  margin: 1em 0 0 1em;"}


## Lagrange's method

- Suppose we have a dataset of $n+1$ points:
    $$
        (x_0, y_0), (x_1, y_1), (x_2, y_2), ..., (x_n, y_n)
    $$

- We construct an interpolation polynomial of degree $n$, called the Lagrange polynomial, using the formula:
    $$
        P(x) = c_0(x)y_0 + c_1(x)y_1 + ... + c_n(x)y_n
    $$

    where $c_i(x)$ are called the :sc[cardinal] functions.

##

The cardinal functions are given by:
$$
    \begin{aligned}
    c_i\left( x \right) &= \frac{(x-x_0)}{(x_i-x_0)} \cdots \frac{(x-x_{i-1})}{(x_i-x_{i-1})} \cdot \frac{(x-x_{i+1})}{(x_i-x_{i+1})} \cdots \frac{(x-x_{n})}{(x_i-x_{n})}\\[1em]
    &= \prod_{\substack{j = 0 \\[.1em] j \neq i}}^{n} \frac{(x-x_j)}{(x_i-x_j)}
    \end{aligned}
$$

- Numerator contains all terms except $(x - x_i)$
- Denominator contains all terms except $(x_i - x_i)$


## Claim: $P(x)$ passes through each data point

If $P(x)$ passes through all points $(x_i, y_i)$, then we must have:

$$
    P(x_i) = y_i 
$$

Let's see if this is true for the Lagrange polynomial we just found.

##

In the above equation for $c_i(x)$, setting $x=x_i$ and $x=x_j$, $i \ne j$, we have 

:::hgrid
$$
    c_i\left( x_i \right) = \prod_{\substack{j = 0 \\[.1em] j \neq i}}^{n} \frac{(x_i-x_j)}{(x_i-x_j)} = 1
$$

and

$$
    c_i\left( x_j \right) = \prod_{\substack{j = 0 \\[.1em] j \neq i}}^{n} \frac{(x_j-x_j)}{(x_i-x_j)} = 0\ ,\ j \neq i
$$
:::

Now, using the equation of $P(x)$ for $x=x_i$:   

$$
\begin{aligned}
P(x_i) &= c_0(x_i)y_0 & &+ ... + c_i(x_i)y_i & &+ ... + c_n(x_i)y_n
\\ &= 0 & &+ ... + 1\cdot y_i & &+ ... + 0
\\ &= y_i
\end{aligned}
$$


## Lagrange polynomial  — Example

Consider the following dataset. We have $4$ data points so the degree of the Lagrange polynomial $P(x)$ will be $n=3$.

::::hgrid
:::div{style="display: inline-grid; grid-template-columns: repeat(5, 3em); grid-template-rows: repeat(2, 1fr);border: 1px solid #666666; margin-left: 3em;"}
::div[$x_i$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em; background-color: #d0d0d0;"}
::div[$0$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$10$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$20$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$30$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}

::div[$y_i$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em; background-color: #d0d0d0;"}
::div[$-250$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$0$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$50$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
::div[$-100$]{style="border: 1px solid #666666; display: flex; align-items: center; justify-content: center;  height:3em; width: 3em;"}
:::
::::

##

We first write $4$ cardinal functions corresponding to these $4$ data points using x-values.

:::div{style="font-size: 0.6em"}
$$
\begin{aligned}
c_0(x) \ &= \ \frac{(x-10)}{(0-10)} \cdot \frac{(x-20)}{(0-20)} \cdot \frac{(x-30)}{(0-30)}   \ = \  \frac{-1}{6000}x^3 + \frac{1}{100}x^2 - \frac{11}{60} x + 1\\
c_1(x) \ &= \ \frac{(x-0)}{(10-0)} \cdot \frac{(x-20)}{(10-20)} \cdot \frac{(x-30)}{(10-30)}  \ = \  \frac{1}{2000}x^3 - \frac{1}{40}x^2 + \frac{3}{10} x\\
c_2(x) \ &= \ \frac{(x-0)}{(20-0)} \cdot \frac{(x-10)}{(20-10)} \cdot \frac{(x-30)}{(20-30)}  \ = \  \frac{-1}{2000}x^3 + \frac{1}{50}x^2 - \frac{3}{20} x\\
c_3(x) \ &= \ \frac{(x-0)}{(30-0)} \cdot \frac{(x-10)}{(30-10)} \cdot \frac{(x-20)}{(30-20)}  \ = \  \frac{1}{6000}x^3 - \frac{1}{200}x^2 + \frac{1}{30} x
\end{aligned}
$$
:::

We then use these four cardinal functions along with the y-values $y_i$ in the equation of $P(x)$:

:::div{style="font-size: 0.9em"}
$$
\begin{aligned}
P(x) &= c_0(x)y_0 + c_1(x)y_1 + ... + c_n(x)y_n \\
     &= -x^2 + 35x -250
\end{aligned}
$$
:::

##

Download file `lagrange_polynomial.py` from Ed to plot these points and the interpolation function to check if it works.


## Curve fitting

- If data is obtained experimentally, there could be random noise present due to measurement errors.
    - Interpolation would not be a good choice as it would fit all data points including noise as well. 
- Instead, we use :i[curve fitting], to find a smooth curve that fits the "average" of the data points, and that is less affected by the noise or "outlier" points.


## 

:::hgrid{cols="2fr 1fr"}
- :b[Linear regression] is a simpler case of curve fitting where a straight line is found that fits a set of data points. 
- Unlike interpolation, the line need not pass through the points.

::img{src="week11/linear_regression.png" style="width: 100%"}
:::

- Linear regression line is given by $f(x) = ax + b$,
    where $a$ is the slope of the line, and $b$ is the y-intercept.
- The main task will be to find $a$ and $b$ such that the line "fits" the data points in the "best" possible way.


## How to determine the "best" fit?

:::hgrid{cols="4fr 3fr"}
- To know how good a line fits the given data points, we compute error for each data point.

- :i[Error] is defined as the squared difference between the actual y-value $y_i$ and the y-value given by the regression line, $f(x_i)$.

::img{src="week11/best_fit_error.png" style="width: 100%;"}
:::

##

The total error $E$ for all data points is given by
$$
    \begin{aligned}
    E(a, b) &= \sum_{i=0}^{n} \left ( y_i - f\left ( x_i \right )  \right ) ^ 2 \\
            &= \sum_{i=0}^{n} \left ( y_i - \left ( ax_i + b \right )  \right ) ^ 2
    \end{aligned}
$$

##

One way to define "best" fit:
- Given all the data points $(x_i, y_i)$, we want to find a line (i.e. find $a$ and $b$) such that the error $E(a, b)$ is minimized.

To find $a$ and $b$ that minimize $E(a, b)$, we calculate the partial derivatives of $E$ with respect to $a$ and $b$ and solve for a and b when derivates are zero:
$$
    \frac{\partial E}{\partial a} = 0,\, \, \, \, \,  \frac{\partial E}{\partial b} = 0
$$


## Calculating the partial derivatives

:::div{style="font-size: 0.8em"}
$$
\frac{\partial E}{\partial a} = \sum_{i=0}^{n} 2 (y_i - (ax_i + b)) (-x_i)
$$

$$
\frac{\partial E}{\partial b} = \sum_{i=0}^{n} 2 (y_i - (ax_i + b))
$$
:::


Setting above derivatives to $0$ and solving for $a$ and $b$,

::::div{style="font-size: 0.8em"}
:::hgrid{margin="0"}
$$
a = \frac{\sum (x_i - \bar{x}) (y_i - \bar{y}) } {\sum (x_i - \bar{x})^2 }
$$

$$
b = \bar{y} - a\bar{x}
$$
:::
::::

where $\bar{x}$ and $\bar{y}$ are the averages of x-values and y-values of data points.

##

Finally, using these $a$ and $b$, we get the desired best-fit line as $f(x)=ax+b$. Here $a$ is slope of the line and $b$ is the y-intercept.

Download `linear_regression.py` from Ed, which plots data and regression line.


## Interpolation examples using Numpy/SciPy

- `numpy_linear_interpolation.py`: Piecewise linear interpolation.
- `cubic_spline_interpolation.py`: Cubic spline interpolation — piecewise polynomial interpolation where each piece is a cubic polynomial ($a+ b x + c x^2 + d x^3$, $d \ne 0$)


## Definite Integral

- The definite integral of a function of a single variable, $f(x)$, between two limits $a$ and $b$ can be viewed as the area $S$ under the curve.

- Numerical integration algorithms try to estimate this area

::img{src="week12/area_curve.png" style="width: 30%;  margin: 1em auto;"}


## Numerical Integration

Our approach will be as follows:
- Divide the region between $a$ and $b$ into $N$ segments
- We then estimate the area under the curve in each segment 
- Finally, we sum these areas

We will consider three algorithms for estimating this area in each segment:
- The Midpoint method
- The Trapezoidal method
- Simpson's method


## Example

We will use the following function in the interval $[0, 5]$ to compare the three algorithms:

::img{src="week12/example.png" style="width: 50%;  margin: 1em auto;"}


## The Midpoint Method

::img{src="week12/midpoint_10.png" style="width: 75%;  margin: 1em 0 0 1em;"}

##

- We first divide the region from $a$ to $b$ into $N$ equal rectangular segments 

- The width of each segment is $\Delta x = \frac{b-a}{N}$

- The endpoint of the segments are
    $$
        \small
        x_0 = a < x_1 < \cdots < x_{N-1} < x_{N} = b
    $$
	
    where

    $$
        \small
        x_i = a + i \cdot \Delta x, \quad i \in [0, N]
    $$  

##

- We estimate the area under the curve in each rectangular segment using the value of $f(x)$ at the midpoint of each segment.
    $$
        \small
        area_k = \Delta x \cdot f(x_k + \frac{\Delta x}{2})\ ,\ k \in [0, N)
    $$

- To compute an approximation to the integral, we just have to sum these areas

##

Approximation improves as the number of segments is increased.

::img{src="week12/midpoint_20.png" style="width: 75%;  margin: 1em auto;"}


## Implementation and Error analysis of Midpoint method

```python
def midpoint_integrate(f, a, b, N):
    area = 0.0
    dx = (b - a) / N
    x = a
    
    for k in range(N):
        area += dx * f(x + dx / 2)
        x += dx
        
    return area
```

##

We know the integral of the example function is given by:
$$
    \small
    \int_{0}^{5} \frac{1}{1+x^2} dx = arctan(5) = 1.37340076695
$$
    
So, we can compute error in the result produced by our implementation `midpoint_integrate`.

##

Error of Midpoint method for different values of $N$:

```output
    N       estimated_integral                error
-----     --------------------     ----------------
   10         1.3735434283e+00     1.4266136666e-04
   20         1.3734392602e+00     3.8493263529e-05
   40         1.3734103959e+00     9.6289197895e-06
   80         1.3734031745e+00     2.4075766312e-06
  160         1.3734013689e+00     6.0191232953e-07
  320         1.3734009174e+00     1.5047571300e-07
  640         1.3734008046e+00     3.7615273785e-08
 1280         1.3734007764e+00     9.4000809359e-09
 2560         1.3734007693e+00     2.3462840559e-09
 5120         1.3734007675e+00     5.8283222693e-10
10240         1.3734007671e+00     1.4196355203e-10
```

## Trapezoidal Method

::img{src="week12/trapezoid_area.png" style="width: 60%;  margin: 1em auto;"}

To approximate the area of each segment, use the area of trapezoid rather than the rectangle.

##
    
::img{src="week12/trapezoid_4.png" style="width: 75%;  margin: 1em auto;"}

The area of each trapezoidal segment is given by
$$
    \small
    area_k = \frac{\Delta x}{2} \left( f(x_k) + f(x_k + \Delta x) \right)\ ,\ k \in [0, N)
$$

##

::img{src="week12/trapezoid_10.png" style="width: 100%;  margin: 1em auto;"}


## 

Implementation and error analysis of the Trapezoidal method

```python lineno=false
area += dx * (f(x) + f(x + dx)) / 2
```

```output
    N       estimated_integral                error
-----     --------------------     ----------------
   10         1.3731040812e+00     2.9668571989e-04
   20         1.3733237548e+00     7.7012176612e-05
   40         1.3733815075e+00     1.9259456542e-05
   80         1.3733959517e+00     4.8152683754e-06
  160         1.3733995631e+00     1.2038458712e-06
  320         1.3734004660e+00     3.0096677106e-07
  640         1.3734006917e+00     7.5245528253e-08
 1280         1.3734007481e+00     1.8815126790e-08
 2560         1.3734007622e+00     4.7075219278e-09
 5120         1.3734007658e+00     1.1806169375e-09
10240         1.3734007667e+00     2.9889868358e-10
```

## Simpson's method

Given any three points there is a unique polynomial (parabola), called the interpolating polynomial, that passes through these points

::img{src="week12/simpsons.png" style="width: 40%;  margin: 0.5em auto;"}

##

- Simpson's method fits a parabola $P(x)$ through the curve at three points — the value of the function at the two endpoints, and at the midpoint of the interval:
    $$
        \small
        f(x_k),\ f(x_k + \frac{\Delta x}{2}),\ f(x_k + \Delta x)
    $$


- The area under the parabola in the interval $[x_k, x_k + \Delta x]$ is given by:
    $$
        \small
        \frac{\Delta x}{6} \left[f(x_k) + 4f(x_k + \frac{\Delta x}{2}) + f(x_k + \Delta x)\right]
    $$

- Adding areas of all the $N$ segments gives an approximation to the integral.

##

- Simpson's method generally finds a better approximation to the area under the curve in each segment than trapezoidal method which uses a line instead of parabola.

- For more details on where does the formula above come from: https://en.wikipedia.org/wiki/Simpson%27s_rule


## 

Implementation and error analysis of the Simpson's method

```python lineno=false
area += dx * (f(x) + 4 * f(x + dx / 2) + f(x + dx)) / 6
```

```output
    N       estimated_integral                error
-----     --------------------     ----------------
   10         1.3733969793e+00     3.7876621872e-06
   20         1.3734007584e+00     8.5498519375e-09
   40         1.3734007664e+00     5.3898707719e-10
   80         1.3734007669e+00     3.8371528177e-11
  160         1.3734007669e+00     7.0714545330e-12
  320         1.3734007669e+00     5.1121329392e-12
  640         1.3734007669e+00     4.9893422727e-12
 1280         1.3734007669e+00     4.9857895590e-12
 2560         1.3734007669e+00     4.9855675144e-12
 5120         1.3734007669e+00     4.9795723100e-12
10240         1.3734007669e+00     4.9829029791e-12
```

## 

Check implementation and example in `numerical_integration.py` and `integration_examples.py`

## Accuracy of the three methods

- For all the three methods we saw, as the number of subintervals $N$ approaches infinity, approximation improves and approaches actual integral.

- However, the speed of improvement differs:
    - Midpoint method — $error \propto \frac{1}{N^2}$
    - Trapezoidal method — $error \propto \frac{1}{N^2}$
    - Simpson’s method — $error \propto \frac{1}{N^4}$

- Simpson's method approaches the integral faster than other methods.


## Integration using scipy.integrate 

Check `scipy_integrate.py` file on Ed.


::divider



11.2 — Interpolation, Curve fitting, Numerical Integration


##

A :b[system of linear equations] is a collection of one or more linear equations: 

$$
\small
\begin{aligned}
a_{0,0}x_0 + a_{0,1}x_2 + \cdots + a_{0,n}x_n & = b_0 \\
a_{1,0}x_0 + a_{1,1}x_2 + \cdots + a_{1,n}x_n & = b_1 \\
& \vdots \\
a_{m,0}x_0 + a_{m,1}x_2 + \cdots + a_{m,n}x_n & = b_m \\
\end{aligned}
$$

In matrix notation, the linear system is given by $\mathbf{Ax = b}$, where

$$
\small
A = \begin{bmatrix}
a_{0,0} & a_{0,1} & \cdots & a_{0,n} \\
a_{1,0} & a_{1,1} & \cdots & a_{1,n} \\
\vdots & & & \vdots \\
a_{m,0} & a_{m,1} & \cdots & a_{m,n} \\
\end{bmatrix}
 \ \ , \ \
\mathbf{x} = \begin{bmatrix}
x_0 \\ x_1 \\ \vdots \\ x_n
\end{bmatrix}
 \ \ , \ \
\mathbf{b} = \begin{bmatrix}
b_0 \\ b_1 \\ \vdots \\ b_m
\end{bmatrix}
$$


## Gauss-Jordan elimination to solve linear system

High-level overview of Gauss-Jordan elimination:

1. Given the matrices $\mathbf{A}$ and $\mathbf{b}$ of the linear system $\mathbf{Ax = b}$ we obtain augment matrix $\mathbf{M = [A | b]}$ by stacking $\mathbf{b}$ as the last column to the matrix $\mathbf{A}$.
    $$
        \small
        M = \left[
        \begin{array}{cccc|c}
        a_{0,0} & a_{0,1} & \cdots & a_{0,n} & b_0 \\
        a_{1,0} & a_{1,1} & \cdots & a_{1,n} & b_1 \\
        \vdots & & & \vdots & \vdots \\
        a_{m,0} & a_{m,1} & \cdots & a_{m,n} & b_m \\
        \end{array}
        \right]
    $$

##

2. Using elementary row operations, convert the augmented matrix $M$ into reduced row-echelon form (RREF). 
    - In this form, the solution is simply the last column of the matrix $M$ (if  there is a unique solution). For example,
    :::div{.flex style="align-items: center;"}
    $$
        \small
        \left[
        \begin{array}{ccc|c}
        0 & 8 & 4  & 2 \\
        2 & 5 & 1  & 5 \\
        4 & 10 & -1  & 1 \\
        \end{array}
        \right]
    $$
    $ \implies $
    $$
        \small
        \left[
        \begin{array}{ccc|c}
        1 & 0 & 0  & 4.125 \\
        0 & 1 & 0  & -1.25 \\
        0 & 0 & 1  & 3. \\
        \end{array}
        \right]
    $$
    :::


## Reduced row-echelon form

A matrix is in reduced row-echelon form (RREF) if it satisfies all of the following conditions.

- In every row the leftmost non-zero entry is $1$ (called the leading $1$).

- If a column contains a leading $1$ (i.e. first non-zero entry in the column is $1$), then all other entries in that column is $0$.

- The leading $1$ of any given row is always to the right of the leading $1$ of the row above it.

- Any rows consisting entirely of zeroes are placed at the bottom of the matrix.

##

Examples:

$$
\small
A = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 2 \end{bmatrix} \quad , \quad B = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
$$

$$
\small
C = \begin{bmatrix} 1 &0 \\ 0 & 1\\ 0 & 0\\ 0 & 0\\ 0 & 0 \end{bmatrix} \quad , \quad D = \begin{bmatrix} 1 & 0 & 0 & 4 & 0 & 0 \\ 0 & 1 & 0 & 3 & 0 & 0\\ 0 & 0 & 1 & 3 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}
$$


## Elementary row operations

We use the following     operations to convert a matrix M into RREF:

1. :b[Row Swap.] Exchange any two rows:   $M[i] \leftrightarrow M[j]$

2. :b[Scalar Multiplication.] Multiply any row by a non-zero constant:  
    $M[i] \gets k \cdot M[i] ,  k \neq 0$

3. :b[Row Addition.] Add multiple of one row to another row:  
    $M[i] \gets M[i]  + k \cdot M[j] ,  i \neq j$

## 

Download file `elementary_row_ops.py` from Ed.

## Gauss-Jordan Elimination algorithm using NumPy

Check [this link](https://en.wikipedia.org/wiki/Gaussian_elimination#Example_of_the_algorithm) to understand how the algorithm works.

Check the program `gaussjordan.py` for an implementation of the algorithm. (Just for understanding; not for exam).  
- Based roughly on the pseudocode for ToReducedRowEchelonForm in  https://rosettacode.org/wiki/Reduced_row_echelon_form

## Using scipy to solve linear systems

```python
import numpy as np
import scipy.linalg as la

A = np.array([[0, 8, 4], [2, 5, 1], [4, 10, -1]], dtype=float)
b = np.array([2, 5, 1], dtype=float)

result = la.solve(A, b)
print(result)
# [ 4.125 -1.25   3.   ]
```



12.1 — Using SciPy, System of Linear Equations



## Roots of a function
- A root or zero of a function $f(x)$ is a solution of the equation $f(x)=0$

- Some functions can be solved in closed form i.e., their solutions can be represented in terms of functions that we know.
    - $f(x) = x^2 - 1$ can be factored to $(x-1)(x+1)$, with the solution of $f(x) = 0$ being $x = -1, 1$

- For the functions that cannot be factored or represented in closed form, we must use numerical methods to find their roots. 
    - See [this post](https://math.stackexchange.com/questions/9199/what-does-closed-form-solution-usually-mean/9203#9203) for a discussion on "closed form".


##

- In general, finding roots numerically involves a procedure which generates a sequence of approximations $x_1, x_2, ..., x_n$ until we obtain a value close to the actual root.

- Note that we will focus on finding the real roots to functions, not the complex roots


## 

:b[Single and double roots]{.sans}

::img{src="week11/single_double_roots.png" style="width: 80%; background-color: white; margin: 0.7em auto;"}

- The equation $f(x)=0$ has a single root for each x-intercept i.e. each time the function $f(x)$ crosses X-axis
- Double roots (two equal roots) occur when $f(x)$ touches but does not cross the X-axis

##

For example, $f(x) = x^2$ has a double root at $x=0$

::img{src="week11/square_func.png" style="width: 70%; margin: 0.7em auto;"}

## Methods of finding roots

- All the methods we will see require an initial estimate of the root — either a single number as an estimate or an estimated interval containing the root.

- Few different ways of estimating an initial root value or interval:
    - If the equation is associated with a physical problem its physical context may suggest the estimate.
    - A search can be carried out for estimated root values.
    - The function could be plotted (a visual procedure).

##

We will see the following methods in this lecture:
- Bisection method
- Secant method
- Newton-Raphson method


## Intermediate value theorem

:::hgrid
::img{src="week11/ivt.png" style="width: 100%; background-color: white;"}

(We will assume that all functions are continuous for root finding algorithms.)
:::

- Let $f(x)$ be a continuous function on the interval $[a, b]$ and let $s$ be a number where $f(a) < s < f(b)$, then there exists at least one $x$ with $f(x) = s$.

##

:::hgrid
::img{src="week11/ivt.png" style="width: 100%; background-color: white;"}

We will use Intermediate value theorem in some of the root-finding methods.
:::

- The main idea is that 
    - If $f(a)$ and $f(b)$ have opposite signs, e.g. $f(a) < 0 < f(b)$, then there is at least one $x$ in the interval $[a, b]$ such that $f(x) = 0$ i.e. there exists a root in $[a, b]$
- Note that since a double root does not lead to a change in sign, it won't be detectable using this method.


## Checking if an interval contains a root

Given a function $f(x)$ which is continuous in the interval $[a, b]$, if $f(a)$ and $f(b)$ have opposite signs, we have a root in $[a, b]$

```python
def f(x):
    return x ** 2 - 25

a1, b1 = [-4.0, 3.0]
print('Is root in [-4.0, 3.0]?', f(a1) * f(b1) < 0)
# False

a2, b2 = [3.0, 10.0]
print('Is root in [3.0, 10.0]?', f(a2) * f(b2) < 0)
# True
```


## Example

::img{src="week11/tan_func.png" style="width: 90%; margin: 0 auto;"}

##

In the previous graph,
- Since we have $tan$ function, which is not continuous, there are sign changes at discontinuities, e.g. in interval $[1, 2]$. 
- So the theorem doesn't work here and we can't use the root finding methods in the interval $[1, 2]$.
- But we can find root in the interval $[6, 7]$.


## Bisection method

- It is the simplest root finding algorithm which can be applied to any continuous function $f(x)$ on an interval $[a, b]$ where a root exists i.e. $f(a)$ and $f(b)$ have different signs.

- Therefore, the method relies on Intermediate value theorem.

- The general idea is to repeat the following
    - Divide the interval in two subintervals, one of which must contain the root.
    - Select the subinterval $[a_n, b_n]$ where $f(x)$ changes sign i.e. $f(a_n)·f(b_n) < 0$

##

:sc[Algorithm]

1. Choose an interval $[a_0, b_0]$ where sign of $f(x)$ changes i.e. $f(a_0) \cdot f(b_0) < 0$

2. Compute $f(m_0)$ for the midpoint $m_0 = \frac{a_0 + b_0}{2}$
3. Determine the next subinterval $[a_1, b_1]$ as follows:
    - If $f(a_0) \cdot f(m_0) < 0$, then $[a_1, b_1] = [a_0, m_0]$
    - If $f(m_0) \cdot f(b_0) < 0$, then $[a_1, b_1] = [m_0, b_0]$
4. Repeat steps (2) and (3) until the interval $[a_n, b_n]$ is small enough, i.e. its size is less than some value $\epsilon$
5. Return the midpoint value  $m_n = \frac{a_n + b_n}{2}$

##

To visualize this algorithm download `visualize_bisection.py` from Ed and run it.

##

:sc[Python implementation]

Check `bisection` function in `rootfinding.py` file.


## 

:sc[Example]

$$
f(x) = x^4 - 6.4x^3 + 6.45x^2 + 20.538x - 31.752
$$

::img{src="week11/example_poly.png" style="width: 60%;  margin: 0.5em auto;"}

There is a double root at $x=2$ and a single root at $x=4$.

##

Check Bisection method example in `rootfinding_example.py` file.


## Secant Method

- A :sc[secant line] is a straight line joining at least two points on a function.

::img{src="week11/secant.png" style="width: 40%;  background-color: white; padding: 1em; margin: 1em auto;"}

##

- The [secant method](https://en.wikipedia.org/wiki/Secant_method) is very similar to the bisection method.

- Instead  of choosing the midpoint, the secant method divides each interval $[a, b]$ by the x-intercept of the secant line connecting the endpoints $(a, f(a))$ and $(b, f(b))$. 

- However, unlike Bisection method, Secant method does not require that a root be present in the interval $[a, b]$. So the Secant method may not converge to any number.


## Formula for Secant line

- Let $f(x)$ be a continuous function on a closed interval $[a, b]$ such that $f(a) \cdot f(b) < 0$

- The secant line connecting the endpoints $(a, f(a))$ and $(b, f(b))$ is given by
    $$
        y = \frac{f(b) - f(a)}{b - a}(x - a) + f(a)
    $$

- By setting $y=0$  in above equation, we get the x-intercept of secant line as follows:
    $$
        x = a - f(a) \frac{b - a}{f(b) - f(a)}
    $$


## :style{.ppt-f90}

:b[Algorithm for Secant method]{.sans}

1. Choose an interval $[a_0, b_0]$ where sign of $f(x)$ changes i.e. $f(a_0) \cdot f(b_0) < 0$.
2. Compute $f(x_0)$ where $x_0$ is the x-intercept of secant line between $(a_0, f(a_0))$ and $(b_0, f(b_0))$ given by
    $$
        x_0 = a_0 - f(a_0) \frac{b_0 - a_0}{f(b_0) - f(a_0)}
    $$
3. Determine the next subinterval $[a_1, b_1]$ as follows:
    - If $f(a_0) \cdot f(x_0) < 0$, then $[a_1, b_1] = [a_0, x_0]$
    - If $f(x_0) \cdot f(b_0) < 0$, then $[a_1, b_1] = [x_0, b_0]$
4. Repeat steps (2) and (3) until the interval $[a_n, b_n]$ is small enough or some fixed number of steps have been taken.
5. Return the value $x_n$, the x-intercept of $n^{th}$ subinterval.

##

To visualize this algorithm download `visualize_secant.py` from Ed and run it.

##

:sc[Python implementation]

Check `secant` function in `rootfinding.py` file.

Check Secant method example in `rootfinding_example.py` file.

## Newton-Raphson method
- Simple, fast, and best-known method of finding roots.

- It uses derivative of the function $f(x)$ i.e. tangent line.
    - So, it can only be used if the function is differentiable in the given interval.

    - If it is costly to compute the derivative, Newton's method will be slow.

- It doesn't need an interval as an initial estimate, but only one estimate value $x_0$. 

##

- We start with an approximation of the root, $x_0$ and compute successive approximations as follows:
    $$
        x_n = x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})}
    $$

- The above formula comes from [Taylor series approximation](https://en.wikipedia.org/wiki/Taylor_series) of $f(x_n)$ given by:
    $$
        f(x_n) \approx f(x_{n-1}) + f'(x_{n-1})(x_n - x_{n-1})
    $$
    - Setting  $f(x_n)$ to $0$ and solving for $x_n$  would give the above formula for $x_n$.

- This method may not converge. To prevent an infinite loop, we use a fixed number of iterations, and stop if we do not find a root.

##

To visualize this algorithm download `visualize_newton.py` from Ed and run it.

##

:sc[Python implementation]

Check `newton_raphson` function in `rootfinding.py` file.

For Newton-Raphson we also need the first derivative of the function. For the exampl we have,

$$
f(x) = x^4 - 6.4x^3 + 6.45x^2 + 20.538x - 31.752
$$

$$
f'(x) = 4 x^3 - 19.2 x^2 + 12.9 x + 20.538
$$

Check the example in `rootfinding_example.py` file.

## Newton-Raphson divergence examples

::img{src="week11/newton_divergence.png" style="width: 90%;  margin: 1.5em 0 0 1em;"}

Although the Newton–Raphson method converges fast near the root, its global convergence characteristics are poor.


##  :style{.ppt-f90}

:::div{style="margin: 0 -3em;"}
| Method         | Assumptions                                                    | Convergence                                                             | Can find Double roots?       |
|----------------|----------------------------------------------------------------|-------------------------------------------------------------------------|------------------------------|
| Bisection      | $f$ is continuous, root exists in the initial interval         | Yes                                                                     | No                           |
| Secant         | $f$ is continuous, root need not exist in the initial interval | Not guaranteed but will converge if root is close to initial interval.  | Not guaranteed.              |
| Newton-Raphson | $f$ is continuous and differentiable                           | Not guaranteed, but will converge if initial estimate is close to root. | Yes but may converge slowly. |

Speed of convergence (single root): Newton-Raphson > Secant > Bisection
:::




## Root-finding using Scipy

Check the file `scipy_rootfinding.py`.



::divider



12.2 — Root Finding, Sorting algorithms



## Binary search algorithm

We have seen examples which perform linear search using a loop:

```python
def linear_search(sequence, target):
    for index in range(len(sequence)):
        if sequence[index] == target:
            return index

    return -1  # Not found
```

##

- Binary search is a faster algorithm to search an item in a sequence, provided the sequence is :i[sorted].
- Binary search is similar to looking up a word in an English dictionary. Suppose we are looking for the word "doctor"
    - We flip pages in the dictionary to find the "d" section but we may end up a little further to the right, say at "f" section.
    - Then we flip pages to the left and may end up at "da" section.
    - Then we flip pages to the right towards "do" and so on...
    - At each step, we decrease the number of pages to search.
    - The process works because the dictionary is sorted in alphabetical order.


##

:b[Visualize the binary search algorithm]{.sans}

<iframe width="900" height="600" frameborder="0" style="background-color: white;"
  src="https://observablehq.com/embed/@d3vp/binary-search-algorithm?cells=view%2Cviewof+sequence%2Cviewof+item_to_search%2Cbuttons"></iframe>


## 

:b[Implementation]{.sans}

```python
def binary_search(sequence, target):
    low = 0
    high = len(sequence) - 1

    while low <= high:
        middle = (low + high) // 2  # floor division

        if sequence[middle] < target:
            low = middle + 1
        elif sequence[middle] > target:
            high = middle -1
        else:
            return middle

    return -1  # Not found
```

##

- In general, if the length of sequence is $N$
    - Linear search takes time proportional to $N$
    - Binary search takes time proportional to $log(N)$


## Sorting algorithms

- Sorting algorithms sort a sequence into ascending or descending order.

    ::::pre{.code}
    [1, 3, 2, 0] → [0, 1, 2, 3]
    [‘a’, ‘c’, ‘b’, ‘d’] →  [‘a’, ‘b’, ‘c’, ‘d’]
    ::::

- There are many sorting algorithms which have different speed and computer memory requirements.

- We will only cover two — Selection sort and Insertion sort


## Selection sort algorithm and implementation

Visualize algorithm: https://visualgo.net/en/sorting


##

```python
def selection_sort(seq):
    N = len(seq)
    
    for i in range(N):
        # Assume that element at index i is minimum
        min_index = i
        
        # Find minimum of unsorted elements on right of i
        for k in range(i+1, N):
            if seq[k] <= seq[min_index]:
                min_index = k

        # Swap elements at i and min_index
        temp = seq[i]
        seq[i] = seq[min_index]
        seq[min_index] = temp
```

##

Run `selectionsort.py` to see the sequence after each iteration.


## Insertion sort algorithm and implementation

Visualize algorithm: https://visualgo.net/en/sorting

##

First let's look at a single step when we have a partially sorted list of size $k$ and want to move an element to have a bigger partially sorted list of size $k+1$.

##

```python
sequence = [9, 22, 51, 63, 10, 79, 60, 75]  # partially sorted list

i = 4
key = sequence[i]  # 10

# Elements on the left of key are sorted.
# We want to insert key on the left to keep the partial list sorted.
# Shift elements one place to the right if they are greater than key. 
j = i - 1
while(j >= 0 and sequence[j] > key):
    sequence[j+1] = sequence[j]
    j = j - 1

# Moving key to index j+1
sequence[j+1] = key
print(sequence)  # [9, 10, 22, 51, 63, 79, 60, 75]
```

##

Now, we can look at the final insertion sort implementation:

```python
def insertion_sort(seq):
    N = len(seq)
        
    for i in range(1, N):
        key = seq[i]
        
        # Elements on the left of key are already sorted.
        # Shift them one place to the right if they are greater than key.
        j = i - 1
        while(j >= 0 and seq[j] > key):
            seq[j+1] = seq[j]
            j = j - 1
        
        # After shifting right, index j+1 is now available for key
        seq[j+1] = key
```

##

Run `insertionsort.py` to see the sequence after each iteration.

## Iterables

https://docs.python.org/3/glossary.html#term-iterable

An object capable of returning its members one at a time. 
- all sequence types (such as list, str, and tuple) 
- some non-sequence types like dict, file objects
- objects of any class that implements `__iter__()` or `__getitem__()` method.

Iterables can be used in a for loop and in many other places where a sequence is needed (`zip()`, `map()`, etc.). 

##

- When an iterable object is passed as an argument to the built-in function `iter()`, it returns an :sc[iterator] for the object. 
- This iterator is good for one pass over the set of values.
- Repeated calls to the iterator's `__next__()` method (or passing it to the built-in function next()) return successive items in the stream.
- When no more data are available a `StopIteration` exception is raised instead by `__next__()` method.

##

```python
>>> rng = range(1, 6, 2)
>>> it = iter(rng)  # create iterator
>>> next(it)
1
>>> next(it)
3
>>> next(it)
5
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
```

##

- When using iterables, it is usually not necessary to call `iter()` or deal with iterator objects ourselves. 
- The `for` statement does that automatically for us, creating a temporary variable to hold the iterator for the duration of the loop.

:::hgrid
```python
for x in some_iterable:
    do_something(x)
```

```python
it = iter(some_iterable)
while True:
    try:
        x = next(it)
        do_something(x)
    except StopIteration:
        break
```
:::

## Our simple `range` implementation

:::hgrid
```python
class MyRange:  
    # assume step will be positive
    def __init__(self, start, stop, step):
        self.start = start
        self.stop = stop
        self.step = step
        self.value = start
        
    def nextValue(self):
        value = self.value
        if value < self.stop:
            self.value += self.step
            return value
```
```python
rng = MyRange(1, 8, 2)
while True:
    val = rng.nextValue()
    if not val:
        break
    
    print(val)
```
:::

##

:::hgrid
```python
class MyRange:  
    # assume step will be positive
    def __init__(self, start, stop, step):
        self.start = start
        self.stop = stop
        self.step = step
        self.value = start
        
    def nextValue(self):
        value = self.value
        if value < self.stop:
            self.value += self.step
            return value
        raise StopIteration()
```
```python       
rng = MyRange(1, 8, 2)
while True:
    try:
        val = rng.nextValue()
        print(val)
    except StopIteration:
        break
```
:::

##

:::hgrid
```python
class MyRange:  
    # assume step will be positive
    def __init__(self, start, stop, step):
        self.start = start
        self.stop = stop
        self.step = step
        self.value = start
        
    def __iter__(self):
        return self
    
    def __next__(self):
        value = self.value
        if value < self.stop:
            self.value += self.step
            return value
        raise StopIteration()
```
```python       
rng = MyRange(1, 8, 2)
for val in rng:
    print(val)
```
:::

##

```python
import random

class RandomIter:
    def __init__(self, num):
        self.num = num
        self.index = 0
        
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.index < self.num:
            self.index += 1
            return random.random()
        raise StopIteration()
        
        
for val in RandomIter(4):
    print(val)

```


## Generators using `yield` statement

```python
def myrange(start, stop, step):
    value = start
    
    while True:
        if value >= stop:
            break
        
        yield value
        value += step


for x in myrange(1, 8, 2):
    print(x)
```

##

```python
import random


def random_iter(num):
    for i in range(num):
        yield random.random()


for x in random_iter(5):
    print(x)
    

print(list(random_iter(4)))
```

## Functions are first-class citizens

Functions can be used in same way as any other Python objects:

- Functions can be passed function as arguments
- Functions can be created inside other functions
- A function can be returned from other function.

## Useful examples of passing functions as arguments

```python
points = [(1, 1, 3), (4, 10, 9), (7, 4, 11)]


def key_func(p):
    return p[1], p[0], p[2]


print(max(points, key=key_func))

print(sorted(points, key=key_func))
```

## lambda

An anonymous inline function consisting of a single expression which is evaluated when the function is called. 

The syntax to create a lambda function is 
```python
f = lambda param1, param2, ...: some_expression
```

Equivalent to

```python
def f(param1, param2, ...):
    return some_expression
```

##

```python
diagnostic_frequencies = {'pharyngitis': 1,
                          'meningitis': 1,
                          'food_poisoning': 2}

maxKey = max(diagnostic_frequencies,
             key=lambda k: diagnostic_frequencies[k])
print(maxKey)

maxKey = max(diagnostic_frequencies,
             key=diagnostic_frequencies.get)
print(maxKey)
```

##

```python
words = [("happy", 0.7), ("sad", -0.9),
         ("fun", 0.58), ("enemy", -0.4)]

words_sorted = sorted(words, key=lambda tup: tup[1])
print(words_sorted)
```

## Built-in `map` function

`map(func, iterable)` applies a function `func` to every item of an iterable, yielding the results.

In very simplified terms, `map()` does something like:
```python
def map(func, iterable):
    for item in iterable:
        yield func(item)
```

Examples:
```python
x = ["23", "3.14", "1.61"]
y = list(map(float, x))
print(y)
```

##
```python
inventory = {"sofa": 10, "chair": 5, "lamp": 3}
new_inventory = dict(map(lambda item: (item[0].upper(), item[1]+10),
                         inventory.items()))
print(new_inventory)
```

```python
persons = [['music', 'running', 'reading'],
           ['movies', 'boardgames'],
           ['boardgames', 'running', 'hiking']]

newlist = list(map(set, persons))
print(newlist)
```

## Other built-in functions that work with iterables

`filter(func, iterable)`: yields items from `iterable` for which `func(item)` is `True`. Equivalent to:
```python
def filter(func, iterable):
    for item in iterable:
        if func(item):
            yield item
```

```python
nums = [-2, 10, -5, 7]
positive = list(filter(lambda x: x > 0, nums))
print(positive)  # [10, 7]
```
##

`all(iterable)`: Return `True` if all items of the `iterable` are true (or if the iterable is empty). Equivalent to:
```python
def all(iterable):
    for item in iterable:
        if not item:
            return False
    return True
```

```python
nums = [2, 4, 6, 8]
print(all([x % 2 == 0 for x in nums]))  # True

nums = [1, 4, 6, 8]
print(all([x % 2 == 0 for x in nums]))  # False
```

##

`any(iterable)`: Return `True` if any item of the iterable is true. If the iterable is empty, return `False`. Equivalent to:
```python
def any(iterable):
    for item in iterable:
        if item:
            return True
    return False
```
```python
nums = [2, 3, 5, 7]
print(any([x % 2 == 0 for x in nums]))  # True

nums = [1, 3, 5, 7]
print(any([x % 2 == 0 for x in nums]))  # False
```

## Inner/Nested functions

- Functions can be defined inside other functions. 
- This is useful to create helper functions that are not used outside of a function — Encapsulates (hides) inner functions.

```python
def main_function():
    def helper(params):
        print("do something", params)

    helper("hello")
    helper(123)


main_function()
helper()
```

## Closure

An enclosed (i.e. inner/nested) function has access to local variables and parameters of outer (enclosing) function.

:::hgrid
```python
def create_quadratic(a, b, c):
    def quadratic(x):
        return a * x ** 2 + b * x + c

    return quadratic

# q1 and q2 are functions:
q1 = create_quadratic(1, 3, 10)
q2 = create_quadratic(-5, -1, 0)
```
```python
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-20, 20, 1000)
plt.plot(x, q1(x), "r")
plt.plot(x, q2(x), "b")
plt.show()
```
:::

## Last lecture next week

- Examples using SciPy
- Final exam overview
- Practice problems from past exams



::divider

