EGR 103/Concept List Spring 2021

This is a work in progress - check back soon for an accurate page!

Lecture 1 - Course Introduction

• Class web page: EGR 103L; assignments, contact info, readings, etc - see slides on Errata/Notes page
• Sakai page: Sakai 103L page; grades, surveys and tests, some assignment submissions
• Pundit page: EGR 103; reference lists
• CampusWire page: CampusWire 103L page; message board for questions - you need to be in the class and have the access code 0878 to subscribe.

Lecture 2 - Programs and Programming

• Almost all languages have input, output, math, conditional execution, and repetition
• Seven steps of programming
  • Watch video on Developing an Algorithm
  • Watch video on A Seven Step Approach to Solving Programming Problems
• Consider how to decide if a number is a prime number
• To play with Python:
  • Install it on your machine or a public machine: Download
• Quick tour of Python
  • Editing window, variable explorer, and console
• You are not expected to remember any of the specifics about how Python stores things or works with them yet!

Lecture 3 - "Number" Types

• Python is a "typed" language - variables have types
• We will use several types:
  • Focus of the day: int, float, and array
  • Focus a little later: string, list, tuple
  • Focus later: dictionary, set
  • Focus way later: map, filter, zip
• int: integers; Python 3 can store these perfectly
• float: floating point numbers - "numbers with decimal points" - Python sometimes has problems storing floating point items exactly
• array
  • Requires numpy, usually with import numpy as np
  • Organizational unit for storing rectangular arrays of numbers
• Math with "Number" types works the way you expect
  • ** * / // % + -
• Relational operators can compare "Number" Types and work the way you expect with True or False as an answer
  • < <= == >= > !=
  • With arrays, either same size or one is a single value; result will be an array of True and False the same size as the array
• Slices allow us to extract information from a collection or change information in mutable collections
• a[0] is the element in a at the start
• a[3] is the element in a three away from the start
• a[-1] is the last element of a
• a[-2] is the second-to-last element of a
• a[:] is all the elements in a because what is really happening is:
  • a[start:until] where start is the first index and until is just *past* the last index;
  • a[3:7] will return a[3] through a[6] in 4-element array
  • a[start:until:increment] will skip indices by increment instead of 1
  • To go backwards, a[start:until:-increment] will start at an index and then go backwards until getting at or just past until.
• For 2-D arrays, you can index items with either separate row and column indices or indices separated by commas:
  • a[2][3] is the same as a[2, 3]
  • Only works for arrays!

Lecture 4 - Other Types

• Strings are set off with " " or ' ' and contain characters; string items cannot be changed
• Lists are set off with [ ] and entries can be any valid type (including other lists!); entries can be of different types from other entries; list items can be changed
• Tuples are indicated by commas without square brackets (and are usually shown with parentheses - which are required if trying to make a tuple an entry in a tuple or a list); tuple items cannot be changed

• A string contains an immutable collection of characters
  • Using + with strings concatenates strings
  • Using * with strings makes a string with the original repeated
• A tuple contains an immutable collection of other types
  • Using + with tuples concatenates tuples
  • Using * with tuples makes a tuple with the original repeated
• A list contains an immutable collection of other types
  • Using + with lists concatenates lists
  • Using * with lists makes a list with the original repeated
• To read more:
  • Note! Many of the tutorials below use Python 2 so instead of print(thing) it shows print thing
  • Lists at tutorialspoint
  • Tuples at tutorialspoint

Lecture 5 - Printing, Input, and Functions

• Creating formatted strings using {} and .format() (format strings, standard format specifiers) -- focus was on using e or f for type, minimumwidth.precision, and possibly a + in front to force printing + for positive numbers.
• Also - Format Specification Mini-Language
• The input() command always grads a string; if the characters in the string perfectly represent an integer or a float, the numerical value can be found with

int(input("Prompt: "))
float(input("Prompt: "))

• • float can convert scientific notation as well:

float("1e-5")

works

• Defined functions can be multiple lines of code and have multiple outputs.
  • Four different types of input parameters:
    • Required (listed first)
    • Named with defaults (second)
    • Additional positional arguments ("*args") (third)
      • Function will create a tuple containing these items in order
    • Additional keyword arguments ("**kwargs") (last)
      • Function will create a dictionary of keyword and value pairs
  • Function ends when indentation stops or when the function hits a return statement
  • Return returns single item as an item of that type; if there are multiple items returned, they are stored in a tuple
  • If there is a left side to the function call, it either needs to be a single variable name or a tuple with as many entries as the number of items returned

Lecture 6 - Logic and Decisions

• <= < == >= > != work with many types; just be careful about interpreting
• not can reverse while and and or can combine logical expressions
• Basics of decisions using if...elif...else
  • Must have logic after if
  • Can have as many elif with logic after
  • Can have an else without logic at the end
  • Flow is solely dependent on indentation!
  • Branches can contain other trees for follow-up questions
• Basics of while loops
• Basics of for loops

Lecture 7 - More Loops, Dictionaries

• Dictionaries are collections of key : value pairs set off with { }; keys can be any immutable type (int, float, string, tuple) and must be unique; values can be any type and do not need to be unique
  • Dictionary at tutorialspoint
• The Price Is Right - Clock Game video demonstration

# tpir.py from class:

# %% Import modules
import numpy as np

# Create price
def create_price(low=500, high=1500):
    price = np.random.randint(low, high+1)
    return price

# Get guess
def get_guess():
    guess = int(input("Guess: "))
    return guess

# Check guess
# Give info about guess
def check_guess(actual, guessed):
    if actual < guessed:
        print("Lower!")
    else:
        print("Higher!")

if __name__ == "__main__":
    the_price = create_price(1000, 2000)
    #print(the_price)
    
    the_guess = get_guess()
    
    while the_price != the_guess:
        check_guess(the_price, the_guess)
        the_guess = get_guess()
    
    if the_price==the_guess:    
        print('You win!!!!!!!')
    else:
        print('LOOOOOOOOOOOOOOOSER')

• Basics of Python:Logical Masks
• Double for loop demo:

nrows = 15
ncols = 8
# Column indices
print("  ", end="")
for col in range(ncols):
    print("{:3}".format(col+1), end='')
    
print("")

# For rows
for row in range(nrows):
    # print row index
    print("{:2}".format(row+1), end='')
    # print column values
    for col in range(ncols):
        print("{:3}".format((row+1)+(col+1)), end='')
    print("")

Lecture 8 - Iterative Methods

• Storing values in a dictionary: bar chart demo
• Taylor series fundamentals
• Maclaurin series approximation for exponential uses Chapra 4.2 to compute terms in an infinite sum.

\( y=e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!} \)

so

\( \begin{align} y_{init}&=1\\ y_{new}&=y_{old}+\frac{x^n}{n!} \end{align} \)

• Newton Method for finding square roots uses Chapra 4.2 to iteratively solve using a mathematical map. To find \(y\) where \(y=\sqrt{x}\): \( \begin{align} y_{init}&=1\\ y_{new}&=\frac{y_{old}+\frac{x}{y_{old}}}{2} \end{align} \)
• See Python version of Fig. 4.2 and modified version of 4.2 in the Resources section of Sakai page under Chapra Pythonified

Lecture 9 - Binary and Data Representation

• Different number systems convey information in different ways.
  • Roman Numerals
  • Chinese Numbers
  • Binary Numbers
    • We went through how to convert between decimal and binary
  • Kibibytes et al
• "One billion dollars!" may not mean the same thing to different people: Long and Short Scales
• Floats (specifically double precision floats) are stored with a sign bit, 52 fractional bits, and 11 exponent bits. The exponent bits form a code:
  • 0 (or 00000000000): the number is either 0 or a denormal
  • 2047 (or 11111111111): the number is either infinite or not-a-number
  • Others: the power of 2 for scientific notation is 2**(code-1023)
    • The largest number is thus just *under* 2**1024 (ends up being (2-2**-52)**1024\(\approx 1.798\times 10^{308}\).
    • The smallest normal number (full precision) is 2**(-1022)\(\approx 2.225\times 10^{-308}\).
    • The smallest denormal number (only one significant binary digit) is 2**(-1022)/2**53 or 5e-324.
  • When adding or subtracting, Python can only operate on the common significant digits - meaning the smaller number will lose precision.
  • (1+1e-16)-1=0 and (1+1e-15)-1=1.1102230246251565e-15
  • Avoid intermediate calculations that cause problems: if x=1.7e308,
    • (x+x)/x is inf
    • x/x + x/x is 2.0
  • $$e^x=\lim_{n\rightarrow \infty}\left(1+\frac{x}{n}\right)^n$$

# Exponential Demo

<syntaxhighlightlang=python> import numpy as np import matplotlib.pyplot as plt

def exp_calc(x, n):

   return (1 + x/n)**n

if __name__ == "__main__":

   n = np.logspace(0, 17, 1000)
   y = exp_calc(1, n)
   fig, ax = plt.subplots(num=1, clear=True)
   ax.semilogx(n, y)
   fig.savefig('ExpDemoPlot1.png')
   
   # Focus on right part
   n = np.logspace(13, 16, 1000)
   y = exp_calc(1, n)
   fig, ax = plt.subplots(num=2, clear=True)
   ax.semilogx(n, y)
   fig.savefig('ExpDemoPlot2.png')

</syntaxhighlight>

• 

  estimates for calculating $$e$$ with $$n$$ between 1 and $$1*10^{17}$$

• 

  $$n$$ between $$10^{13}$$ and $$10^{16}$$ showing region when roundoff causes problems

• 
  • Wait - that's the simplified version...here:
    • 
• Want to see Amharic?

list(map(chr, range(4608, 4992)))

• Want to see the Greek alphabet?

for k in range(913,913+25):
    print(chr(k), chr(k+32))

Lecture 10 - Monte Carlo Methods

• From Wikipedia: Monte Carlo method
• Walker demo

Lecture 11 - 3D Plotting

• subplots
• Python:Plotting Surfaces

Lecture 12 - Matrices and Matrix Operations

• 1D arrays are neither rows nor columns - they are 1D!
• 2D arrays have...two dimensions, one of which might be 1
  • Python does mathematical operations differently for 1 and 2-D arrays
• Dot products as heart of matrix multiplication
  • Inner dimensions must match; outer dimensions equal dimensions of result
• To multiply matrices A and B ($$C=A\times B$$ in math or C=A@B in Python) using matrix multiplication, the number of columns of A must match the number of rows of B; the results will have the same number of rows as A and the same number of columns as B. Order is important
• Matrix multiplication (by hand)
• Matrix multiplication (using @ in Python)
• Reformatting linear algebra expressions as matrix equations
• Calculating determinants and inverses
• Determinants of matrices and the meaning when the determinant is 0
  • Shortcuts for determinants of 1x1, 2x2 and 3x3 matrices (see class notes for processes)

$$\begin{align*} \mbox{det}([a])&=a\\ \mbox{det}\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right)&=ad-bc\\ \mbox{det}\left(\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}\right)&=aei+bfg+cdh-afh-bdi-ceg\\ \end{align*}$$

• Don't believe me? Ask Captain Matrix!

• Inverses of matrices:
  • Generally, $$\mbox{inv}(A)=\frac{\mbox{cof}(A)^T}{\mbox{det}(A)}$$ there the superscript T means transpose...
    • And $$\mbox{det}(A)=\sum_{i\mbox{ or }j=0}^{N-1}a_{ij}(-1)^{i+j}M_{ij}$$ for some $$j$$ or $$i$$...
      • And $$M_{ij}$$ is a minor of $$A$$, specifically the determinant of the matrix that remains if you remove the $$i$$th row and $$j$$th column or, if $$A$$ is a 1x1 matrix, 1
        • And $$\mbox{cof(A)}$$ is a matrix where the $$i,j$$ entry $$c_{ij}=(-1)^{i+j}M_{ij}$$
  • Good news - for this class, you need to know how to calculate inverses of 1x1 and 2x2 matrices only:

$$ \begin{align} \mbox{inv}([a])&=\frac{1}{a}\\ \mbox{inv}\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right)&=\frac{\begin{bmatrix}d &-b\\-c &a\end{bmatrix}}{ad-bc} \end{align}$$

Lecture 13 - Norms and Condition Numbers

• Chapra 11.2.1 for norms
  • np.linalg.norm() in Python
• Chapra 11.2.2 for condition numbers
  • np.linalg.cond() in Python
  • Note: base-10 logarithm of condition number gives number of digits of precision possibly lost due to system geometry and scaling (top of p. 295 in Chapra)

Lecture 14 - Linear Algebra Recap

• Converting equations to a matrix system:
  • For a certain circuit, conservation equations learned in upper level classes will yield the following two equations:

$$\begin{align} \frac{v_1-v_s}{R1}+\frac{v_1}{R_2}+\frac{v_1-v_2}{R_3}&=0\\ \frac{v_2-v_1}{R_3}+\frac{v_2}{R_4}=0 \end{align}$$

• Assuming $$v_s$$ and the $$R_k$$ values are known, to write this as a matrix equation, you need to get $$v_1$$ and $$v_2$$ on the left and everything else on the right:

$$\begin{align} \left(\frac{1}{R_1}+\frac{1}{R_2}+\frac{1}{R_3}\right)v_1+\left(-\frac{1}{R_3}\right)v_2&=\frac{v_s}{R_1}\\ \left(-\frac{1}{R_3}\right)v_1+\left(\frac{1}{R_3}+\frac{1}{R_4}\right)v_2&=0 \end{align}$$

• Now you can write this as a matrix equation:

$$ \newcommand{\hmatch}{\vphantom{\frac{1_s}{R_1}}} \begin{align} \begin{bmatrix} \frac{1}{R_1}+\frac{1}{R_2}+\frac{1}{R_3} & -\frac{1}{R_3} \\ -\frac{1}{R_3} & \frac{1}{R_3}+\frac{1}{R_4} \end{bmatrix} \begin{bmatrix} \hmatch v_1 \\ \hmatch v_2 \end{bmatrix} &= \begin{bmatrix} \frac{v_s}{R_1} \\ 0 \end{bmatrix} \end{align}$$

• See Python:Linear_Algebra#Sweeping_a_Parameter for example code on solving a system of equations when one parameter (either in the coefficient matrix or in the forcing vector or potentially both)

Lecture 15 - Statistics and Curve Fitting I

• Definition of curve fitting versus interpolation:
  • Curve fitting involves taking a scientifically vetted model, finding the best coefficients, and making predictions based on the model. The model may not perfectly hit any of the actual data points.
  • Interpolation involves making a guess for values between data points. Interpolants actually hit all the data points but may have no scientific validity at all. Interpolation is basically "connecting the dots," which may involve mathematically complex formulae.
• Statistical definitions used (see Statistics Symbols for full list):
  • $$x$$ will be used for independent data
  • $$y$$ will be used for dependent data
  • $$\bar{x}$$ and $$\bar{y}$$ will be used for the averages of the $$x$$ and $$y$$ sets
  • $$\hat{y}_k$$ will be used for the estimate of the $$k$$th dependent point
  • $$S_t=\sum_k\left(y_k-\bar{y}\right)^2$$ is the sum of the squares of the data residuals and gives a measure of the spread of the data though any given value can mean several different things for a data set. It will be a non-negative number; a value of 0 implies all the $$y$$ values are the same.
  • $$S_r=\sum_k\left(y_k-\hat{y}_k\right)^2$$ is the sum of the squares of the estimate residuals and gives a measure of the collective distance between the data points and the model equation for the data points. It will be a non-negative number; a value of 0 implies all the estimates are mathematically perfectly predicted by the model.
  • $$r^2=\frac{S_t-S_r}{S_t}=1-\frac{S_r}{S_t}$$ is the coefficient of determination; it is a normalized value that gives information about how well a model predicts the data. An $$r^2$$ value of 1 means the model perfectly predicted every value in the data set. A value of 0 means the model does as well as having picked the average. A negative value means the model is worse than merely picking the average.
• Mathematical proof of solution to General Linear Regression
• Python:Fitting

Lecture 16 - Statistics and Curve Fitting II

• Clarification on how general linear regression works

Lecture 17 - Statistics and Curve Fitting III

• Linearized non-linear models
  • Borrowed from MATLAB:Fitting#Linearized_Models
• Non-linearized non-linear models
• Python:Fitting#Nonlinear_Regression

Lecture 18 - Finding Roots

• Python:Finding roots
• SciPy references (all from Optimization and root finding):
  • scipy.optimize.brentq - closed method root finding
  • scipy.optimize.fsolve - open method root finding

Lecture 19 - Level Setting, Finding Extrema

• Things to re-cover: String formatting, Dictionaries, Binary, Try/Except, Matrices, Meshgrid, Norms, Nonlinear Regression
• Things to cover: MATLAB, Machine Learning
• Python:Extrema
• SciPy references (all from Optimization and root finding):
  • scipy.optimize.fmin - unbounded minimization
  • scipy.optimize.fminbound - bounded minimization

Lecture 20 - Interpolation

• Python:Interpolation
• Interpolations are meant to estimate values between points in a data set.
• Interpolants must go through all the data points - different concept from a fit; also interpolation functions generally have different coefficients for the interpolant between every pair of points - very different from a fit
• Unlike a model, the functions used to interpolate may have no scientific validity; instead, they satisfy different mathematical conditions.
• The main interpolations we looked at are nearest neighbor, linear, and cubic spline with different conditions (not-a-knot, clamped, natural)
  • Most basic interpolation simply looks at most recent value of data (i.e. data point "to the left")
  • Next most basic is nearest neighbor - closest point
  • Next is linear interpolation - straight line between neighboring points
  • After that, using third-order polynomials is common
    • We went through process of coming up with coefficients using linear algebra

Lecture 21 - Comprehensions, Maps, Filters, and Zips

• Maps, filters, zips create a one-time-use iterable type
  • map(FUN, ITERABLE) applies a function to each element in an iterable and returns an iterable
  • filter(FUN, ITERABLE) applies a logical expression to each element and includes that element in the return only if the function is true
  • zip(A, B) takes corresponding elements from A and B and returns an iterable made up of tuples with the corresponding elements from A and B
    • Very useful for making a dictionary out of a collection of keys and a collection of values
• List comprehensions
  • [FUNCTION for VAR in SEQUENCE if LOGIC]
    • The FUNCTION should return a single thing (though that thing can be a list, tuple, etc)
    • The "if LOGIC" part is optional
    • [k for k in range(3)] creates [0, 1, 2]
    • [k**2 for k in range (5, 8)] creates [25, 36, 49]
    • [k for k in 'hello' if k<'i'] creates ['h', 'e']
    • [(k,k**2) for k in range(11) if k%3==2] creates [(2, 4), (5, 25), (8, 64)]
• Scrabble example

Lecture 22 - Initial Value Problems

• Introduction to IVP where $$\frac{dy}{dt}=f(t, y, C)$$ and $$y_0$$ is known
• Overview of particular and homogeneous solutions
• Euler-Cauchy method
• Runge-Kutta 4
• Python:Ordinary Differential Equations