EGR 103/Concept List/F22

Lecture 1 - 8/29 - Course Introduction

• Main class page: EGR 103L
  • Includes links to Sakai, Pundit, and Ed pages
• Sakai page: Sakai 103L page; grades, surveys and tests, some assignment submissions; first day slideshow in Resources section

Lecture 2 - 8/27 - Programs and Programming

• Almost all languages have input, output, math, conditional execution (decisions), and repetition (loops)
• Seven steps of programming The Seven Steps Poster. Also, for Monday's class:
  • Watch video on Developing an Algorithm
  • Watch video on A Seven Step Approach to Solving Programming Problems
• Problem: Consider how to decide if a number is a prime number
  • Some "shortcuts" for specific factors but need to have a generalized approach
  • See if number is evenly divisible by any integer between 2 and the square root of the number - but how do we ask the computer to do that?
• Quick tour of Python
  • Console (with history tab), variable explorer (with other tabs), and editing window
  • Main numerical types: whole numbers (int) and numbers with decimals (float)
  • Can use % (called "mod") to get "remainder"
    • If both items are integers, result is an integer; if either is a float, result is a float
  • Relational operators: < <= == >= > !=
    • Result is is either True or False
• Comments in code:
  • If there is a #, Python ignores everything remaining in that line after the #
  • If there are """ or , Python ignores everything until the closing """ or
  • If you use # %% in Spyder, the editing window will set up a cell and light up the cell your cursor is in. Cells have no impact on how the code runs, just how the code appears in the window

Lecture 3 - 9/5 - "Number" Types

• Python is a "typed" language
  • Focus of the day: int, float, and array
    • 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
  • Focus a little later: string, list, tuple
  • Focus later: dictionary, set
  • Focus way later: map, filter, zip
• Basic operations and types
  • + - * // (rounded division) and % (remainder / modulo) produce int if both sides are an int, float if either or both are floats
  • / (regular division) and // (rounded division) produces float with ints or floats
  • ** to do powers
  • VAR = input("prompt: ") will ask the user for a value and stores whatever they type as a string (broken in some versions of Spyder!)
  • NUM = int(VAR)
    • If VAR is an int or a float, it will return an int rounded towards 0
    • If VAR is a string, it will return an int only if the string looks exactly like an integer
  • NUM = float(VAR)
    • If VAR is an int or a float, it will return a float with the same value
    • If VAR is a string, it will return a float if the string looks like a float, including scientific notation such as float("1.23e4")
• Arrays
  • Python doesn't know everything to start with; may need to import things
    • import MODULE means using MODULE.function() to run
    • import MODULE as NAME means using NAME.function() to run
  • Organizational unit for storing rectangular arrays of numbers
  • Generally create with np.array(LIST) where depth of nested LIST is dimensionality of array
    • np.array([1, 2, 3]) is a 1-dimensional array with 3 elements
    • np.array([[1, 2, 3], [4, 5, 6]]) is a 2-dimension array with 2 rows and 3 columns
• Math with "Number" types works the way you expect
  • ** * / // % + -
  • With arrays, * and / work element by element; *matrix* multiplication is a different character (specifically, @)
• 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 a 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 - 9/9 - Other Types

• 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 and mutable items within lists can be changed. Lists can be "grown" by using += with the list or l.append().
• 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 but mutable items within tuples can be
• Strings are set off with " " or ' ' and contain characters; string items cannot be changed
• For lists, tuples, and strings:
  • Using + concatenates the two collections
  • Using * with them makes creates a collection with the original repeated that many times
  • Using += will create a new item with something appended to the old item; the "something" needs to be the same type (list, tuple, or string); this may seem to break the "can't be changed" rule but really a += b is a = a + b which creates a new a.
• Characters in strings have "numerical" values based on the ASCII table (https://www.asciitable.com/)
  • Numbers are earlier than lower case letters; lower case letters are earlier than upper case letters
  • Strings are sorted character by character; if one string is shorter than another, it is considered less
    • " Hello" < "Hi" is True since the "e" comes before the "i"
    • "Zebra" < "apple" is True since the upper case "Z" is before the lower case "a"
    • "go" < "gone" is True since the first two characters match and then the word is done
• To get the numerical value of a single character, use ord("A") or replace the A with the character you want
• To get the character a number represents, use chr(NUM)
• To apply either ord or chr to multiple items, use a map; to see the results, make a list out of the map
• Trinket

• 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
• Creating formatted strings using {} and .format() (format strings, standard format specifiers) -- focus was on using s for string and e or f for numerical types, minimumwidth.precision, and possibly a + in front to force printing + for positive numbers.
  • Using {} by themselves will substitute items in order from the format() function into the string that gets created
  • Putting a number in the {} will tell format which thing to get
  • Format specification comes after a : in the {}; if you do not specify a location index, you still have to put a colon in the {}
  • {:s} means string and {:Xs} where X is an integer means reserve at least that much space for a left-formatted string
  • {:f} means floating point (default 6 digits after decimal point) and {:X.Yf} reserves at least X spaces (including + or - and the . if it is there) with Y digits after the decimal point for t right-justified number
  • {:e} means floating point (default 6 digits after decimal point) and {:X.Ye} reserves at least X spaces (including + or - and the . if it is there and the letter e and the + or - after the e and the two or three digit number after that) with Y digits after the decimal point for t right-justified number
• Aside - Format Specification Mini-Language has all the possibilities; we will cover some but not all of these in later classes
• You can enter numbers in scientific notation with a number followed by the letter 3 and then a number or negative number for the power of 10; for example, x = 6.02e23 or e = -1.6e-19
  • float can convert scientific notation as well:

float("1e-5")

Lecture 5 - 9/12 - Functions

• Defined functions can be multiple lines of code and have multiple outputs.
• The function can see everything in main, but main cannot see things created in the function.
  • Best bet is to pretend the function cannot see things in main - pass everything in that you need to see!

•  def FNAME(local1, local2, ...):
       CODE
       return THING1, THING2, ...
  

  • Four different types of input parameters - we only really talked about the first three kinds:
    • 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 and returned 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
• Dictionaries
  • Object where the index (called the key) can be any immutable (integer, float, string, or tuple); the value can be anything.

Lecture 6 - 9/16 - Loops and Decisions

• The Price is Right!
• Logic
  • <= < == >= > != work with many types; just be careful about interpreting
  • not can reverse while and and or can combine logical expressions; most expressions can be written in two ways (while/if TRUE or while/if not FALSE)
• 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 loops using while
  • Must have logic; gets evaluated at start and not again until branch ends
  • Useful when you do not know how many times a loop will run (input validation example)
  • break in a loop can break out early
  • continue in a loop goes back to the top early
• Basics of loops using for
  • for VAR in ITERABLE
    • VAR will take on each item in ITERABLE one at a time; ITERABLE can be a string, list, tuple, array, or range
      • range(N) creates something similar to [0, 1, 2, 3, 4, ..., N-1]
      • range(M, N) creates something similar to [M, M+1, M+2, ..., N-1]
      • range only creates integers

Lecture 7 - 9/19 - Loops and Accounting

• Looked at looping through letters in a phrase
• Logic: ITEM in THING will be true if ITEM is a subunit of THING
  • "a" in "subway" would be True
  • "way" in "subway" would be True
  • "as" in "subway" would be False
• Many ways to keep track of items
  • Counter variable
  • List with different indices to track different items
• Many ways to evaluate items
  • For loop with an if tree
  • For loop with another for loop

Lecture 8 - 9/23 - 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
• Storing values in a dictionary
  • Different loops
  • zip
• Translation demo with Morse code and NATO phonetic alphabet
  • Loading lines of text from a file
  • Splitting strings with split
• Don't copy code from a PDF!
  • waffle versus waffle versus waffle
    • waffle versus waffle versus waffle
  • In the first version, the f-f-l are three separate characters, in the second version it is ff-l and in the third, it is ffl; if you try to copy/paste these into Spyder, the words are 6, 5, or 4 characters, respectively!

Lecture 9 - 9/26 - Random Numbers and Logical Masks

• np.random.randint(low, high, size)
  • low defaults to 0
  • number is an integer [low, high)
  • if size is 2 dimensions or more, must be in a tuple
• np.random.uniform(low, high, size)
  • low defaults to 0, high defaults to 1
  • number is a float [low, high) with a uniform distribution over range
  • if size is 2 dimensions or more, must be in a tuple
• np.random.normal(loc, scale, size)
  • loc (average) defaults to 0, scale (spread) defaults to 1
  • number can be anything; concentrated around loc depending on how big scale is
  • if size is 2 dimensions or more, must be in a tuple
• Basics of Python:Logical Masks

Lecture 10 - 9/30 - Iterative Methods

• 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 11 - 10/3 - Binary

• Different number systems convey information in different ways.
  • Roman Numerals
  • Chinese Numbers
  • Binary Numbers
    • We went through how to convert between decimal and binary
• 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

• 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 12 - 10/7 - Monte Carlo Methods

• From Wikipedia: Monte Carlo method
• Several demonstrations in class (coins, dice, darts)

Lecture 13 - 10/14 - Comprehensions, Maps, Filters, and Zips

• 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)]
• map(fun, sequence) to apply a function to each item in a sequence

Lecture 14 - 10/17 - Plotting Surfaces

• subplots
• Python:Plotting Surfaces

Lecture 15 - 10/21 - Matrix Operations and Linear Algebra

• 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 16 - 10/24 - 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 17 - 10/28 - Recursion

• Need base cases and recursive step
• May be simple to program; also may take a long time to compute!
• Memoization can solve the latter problem
• Examples: factorials, fibonacci sequence, Koch snowflake

Lecture 18 - 10/31 - 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 19 - 11/4 - Statistics and Curve Fitting II

• Definition of a linear fit (in contrast to a linear system)
• Walkthrough of a general linear fit
• "The Math" - General Linear Regression

Lecture 20 - 11/7 - Linear Regression

• Code for linear regression:
  • Polynomial fitting: Python:Fitting#Polynomial_Fitting
  • General linear regression: Python:Fitting#General_Linear_Regression
  • General linear regression on surfaces: Python:Fitting#Multidimensional_General_Linear_Regression

Lecture 21 - 11/11 - Nonlinear Regression and Optimization

• Optimization routines
  • Nonlinear regression
    • Common linearizations of nonlinear models: See MATLAB:Fitting for math parts; ignore code-specific parts
    • Python code for nonlinear regression: Python:Fitting#Nonlinear_Regression
  • 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
  • Finding extrema
    • Python:Extrema
    • SciPy references (all from Optimization and root finding):
      • scipy.optimize.fmin - unbounded minimization
      • scipy.optimize.fminbound - bounded minimization

Lecture 22 - 11/14 - Numerical Integration and Differentiation

• Newton Interpolating Polynomials
• Overview of integration
  • Riemann sums
  • Trapezoidal Rule
  • Simpson's 1/3 and 3/8 Rules
• Overview of differentiation
  • 2pt forward first derivative
    • Exception at first point
  • 2 pt backward first derivative
    • Exception at last point
  • 3pt centered first derivative
    • Exceptions at first and last points
  • 3pt centered second derivative
    • Exceptions at first and last points

Lecture 23 - 11/18 - Object Oriented Programming and Classes in Python

• Create new variable type, or class, in Python
• Think about structure of data and processes that might apply
• Sample code at EGR_103/Spring_2022/Lab_12

Lecture 25 - 11/28 - Object Oriented Programming and Classes in Python

• Vectors and vector operations
• Vector class

Lecture 26 - 12/2 - 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

Lecture 27 - 12/5 - Initial Value Problems (cont'd)

• Python:Ordinary Differential Equations examples