EGR 103/Concept List Fall 2019

This page will be used to keep track of the commands and major concepts for each lab in EGR 103.

Lectures

Lecture 1 - 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
• Piazza page: Piazza 103L page; message board for questions

Lecture 2 - Programs and Programming

• To play with Python:
  • Install it on your machine or a public machine: Download
  • Use a Duke container with Spyder: Containers - note - these do not have access to your Duke files. More on how to connect that later.
• Quick tour of Python
  • Editing window, variable explorer, and console
  • Variable explorer is your friend
• From Dewey - programming language typically have ability to work with input, output, math, conditional execution, and repetition
• Hilton and Bracy Seven Steps
• Class work developing algorithm for program to determine if a number is prime

Lecture 3

• 7 Steps for finding prime numbers
• prime program -- includes intro to input(), if tree, for loop, print(), remainder %

Lecture 4

• Function definitions
  • Positional and key word arguments (kwargs)
  • Default values
  • Returns tuples -- can be received by a single item or a tuple of the right size
• Aquarium

Lecture 5

• print() and format specifications: link
  • Main components are width, precision, and type; sometimes initial +
  • e and f can print integers as floats; d cannot print floats
• relational and logical operators - how they work on item, string, list, tuple
• if trees
• while loops
• for loops
  • NOTE: in the case of

for y in x

If the entries of x are changed, or really if x is changed in a way that its location in memory remained unchanged, y will iterate over the changed entries. If x is changed so that a copy first has to be made (for example, it is set equal to a slice of itself), then y will iterate over the original entries. Note the differences between:

x = [1, 2, 3, 4, 5]
for y in x:
    print(x, y)
    x[4] = [0]
    print(x, y)

and:

x = [1, 2, 3, 4, 5]
for y in x:
    print(x, y)
    x = x[:-1]
    print(x, y)

• counting characters program

Expand

# letter_typing.py from class:

def check_letters(phrase):
    vowels = "aeiou"
    numbers = "0123456789"
    consonants = "bcdfghjklmnpqrstvwxyz"
    # vowels, numbers, consonants, and other in that order
    count = [0, 0, 0, 0]
    
    for letter in phrase:
        if letter.lower() in vowels:
            count[0] += 1
        elif letter.lower() in numbers: # .lower not really needed here
            count[1] += 1
        elif letter.lower() in consonants:
            count[2] += 1
        else:
            count[3] += 1
            
    return count

out = check_letters("Let's go Duke University 2018!")
print(out)

• Question in class: does Python have ++ or -- operators; it does not. You need x += 1 or x -= 1

Lecture 6

Florence - material moved to Lecture 7 and Lab 4

Lecture 7

• Distinction between == and i
• Iterable types and how they work (list, tuple, string
• Things that do not change memory address of a list (and therefore change what a loop iterates over):
  • +, .append(), .extend(), .insert(), .remove(), .pop(), .sort(), .reverse(), .clear()
• Things that do change memory address of a list:
  • Total replacement, replacement by self-slice, making a copy
• Singularity functions
  • Unit step \(u(t)\)
  • See Singularity Functions for way too much information - more in lab!
    • Singularity_Functions#Alternate_Names_for, Singularity_Functions#Building_a_Mystery_Signal, and Singularity_Functions#Accumulated_Differences might be particularly helpful!

Lecture 8

• Be sure to use the resources available to you, especially the Think Python links in the Class Schedule!
• When checking for valid inputs, sometimes the order of asking the question can be important. If you want a single non-negative integer, you first need to ask if you have an integer before you ask if something is non-negative. The right way to go is something like:

if not isinstance(n, int) or n<1:

because if n is not an integer, the logic will be true without having to ask the second question. This is a good thing, because if n is, for example, a list, asking the question n<1 would yield an error.

• We built up a program whose end goal was to compare and contrast the time it takes different methods of calculating Fibonacci numbers to run.
• The plt.plot(x, y) command has some near cousins:
  • plt.semilogy(x, y) will plot with a regular scale for x and a base-10 log scale for y
  • plt.semilogx(x, y) will plot with a base-10 log scale for x and a regular scale for y
  • plt.loglog(x, y) will plot with base-10 log scales in both directions
• Fibonacci comparison program

Expand

# Fibonacci program from class

# -*- coding: utf-8 -*-
"""
Created on Fri Sep 21

@author: DukeEgr93
"""

import time
import numpy as np
import matplotlib.pyplot as plt


def fib(n):
    if not isinstance(n, int) or n < 1:
        print('Invalid input!')
        return None
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


"""
fib_dewey based on fibonacci at:
http://greenteapress.com/thinkpython2/html/thinkpython2012.html#sec135
"""
known = {1: 1, 2: 1}


def fib_dewey(n):
    if not isinstance(n, int) or n < 1:
        print('Invalid input!')
        return None
    if n in known:
        return known[n]
    res = fib_dewey(n - 1) + fib_dewey(n - 2)
    known[n] = res
    return res


def fibloop(n):
    if not isinstance(n, int) or n < 1:
        print('Invalid input!')
        return None
    head = 1
    tail = 1
    for k in range(3, n + 1):
        head, tail = head + tail, head
    return head


N = 30
uvals = [0] * N
utimes = [0] * N

mvals = [0] * N
mtimes = [0] * N

lvals = [0] * N
ltimes = [0] * N

for k in range(1, N + 1):
    temp_time = time.clock()
    uvals[k - 1] = fib(k)
    utimes[k - 1] = time.clock() - temp_time

    temp_time = time.clock()
    mvals[k - 1] = fib_dewey(k)
    mtimes[k - 1] = time.clock() - temp_time

    temp_time = time.clock()
    lvals[k - 1] = fibloop(k)
    ltimes[k - 1] = time.clock() - temp_time

for k in range(1, N + 1):
    print('{:2d} {:6d} {:0.2e}'.format(k, uvals[k - 1], utimes[k - 1]), end='')
    print(' {:6d} {:0.2e}'.format(mvals[k - 1], mtimes[k - 1]), end='')
    print(' {:6d} {:0.2e}'.format(lvals[k - 1], ltimes[k - 1]))

k = np.arange(1, N + 1)
plt.figure(1)
plt.clf()
plt.plot(k, utimes, k, mtimes, k, ltimes)
plt.legend(['recursive', 'memoized', 'looped'])

plt.figure(2)
plt.clf()
plt.semilogy(k, utimes, k, mtimes, k, ltimes)
plt.legend(['recursive', 'memoized', 'looped'])

Lecture 9

• Different number systems convey information in different ways.
• "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
• List-building roundoff demonstration

Expand

# Roundoff Demo

import numpy as np
import matplotlib.pyplot as plt

start = 10;
delta = 0.1;
finish = 100;

k = 0
val_c = [start];
val_a = [start];

while val_c[-1]+delta <= finish:
   val_c += [val_c[-1] + delta];
   k = k + 1
   val_a += [start + k*delta];

array_c = np.array(val_c)
array_a = np.array(val_a)

diffs = [val_c[k]-val_a[k] for k in range(len(val_a))]

plt.figure(1)
plt.clf()
#plt.plot(array_c - array_a, 'k-')
plt.plot(diffs, 'k-')

• Exponential demo program

Expand

# Exponential demo

#%%
import numpy as np
import matplotlib.pyplot as plt
#%%
def exp_calc(x, n):
    return (1 + (x/n))**n
#%% Shows that apprxomation gets better as n increases
print(np.exp(1))
print(exp_calc(1, 1))
print(exp_calc(1, 10))
print(exp_calc(1, 100))
print(exp_calc(1, 1000))
print(exp_calc(1, 10000))
print(exp_calc(1, 100000))
#%% Shows that once n is too big, problems happen
n = np.logspace(0, 18, 1e3);

plt.figure(1)
plt.clf()
plt.semilogx(n, exp_calc(1, n), 'b-')

Lecture 10

• List comprehensions: info in Think Python and Section 7.1.1 in Punch & Enbody
  • Basic idea: make a list of [EXPRESSION for VARIABLE in ITERABLE if LOGIC]
  • Even numbers 0 through 10: [k for k in range(11) if k%2==0]
  • Non-vowels in a word: [letter for letter in word if not letter in 'aeiouAEIOU']
  • Square roots of nonnegative numbers in a list of numbers: [sqrt{n} for n in nums if n>=0]
  • Print all three digit numbers with each digit unique:

Expand

# unique_codes.py

nums = range(10)
for H in nums:
    for T in [k for k in nums if not k in [H]]:
        for O in [k for k in nums if not k in [H, T]]:
            print(H, T, O)

• Can also replace nums with whatever should comprise three element code; nums='hello' will make all three letter words out of h, e, l, and o (24 choices)

• Iterative solutions - where next approximation or guess is based on previous guess and some algorithm
  • Series method for finding exponential \(e^c\):\( e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!} \)

so

\( y_{new}=y_{old}+\frac{x^n}{n!} \)

and the initial guess for \(y\) is the \(n=0\) term, or 1.

• Newton method for square roots - to find \(y\) where \(y=\sqrt{x}\): \( y_{new}=\frac{y_{old}+\frac{x}{y_{old}}}{2} \)

and a good initial guess is \(y=x\). A bad initial guess is \(y=0\)

• Chapra Figure 4.2 (as translated in Python) can be very helpful! Now featuring 100% fewer semi-colons!

Expand

# Chapra Figure 4.2 from Applied Numerical Methods with MATLAB, 4th ed, translated into Python:

def iter_meth(x, es=0.0001, maxit=50):
    '''Maclaurin series of exponential function
    iter_meth(x,es,maxit)
    input:
    x = value at which series evaluated
    es = stopping criterion (default = 0.0001)
    maxit = maximum iterations (default = 50)
    output:
    fx = estimated value
    ea = approximate relative error (%)
    iter = number of iterations
    '''

    # initialization
    iter = 1
    sol = 1
    ea = 100
    # iterative calculation
    while 1:
        solold = sol;
        sol = sol + x ** iter / m.factorial(iter)
        iter = iter + 1
        if sol != 0:
            ea = abs((sol - solold)/sol)*100
        
        if ea<=es or iter>=maxit:
            break

    fx = sol

    return (fx, ea, iter)

• Only two changes in 4.2 to go from exponential calculation to finding a square root

• Change initial sol = 1 to sol = x to make x initial guess for square root
• Change

sol = sol + x ** iter / m.factorial(iter)

line to:

 sol = sol / 2 + x / (sol * 2)

Lecture 11

• Debugging
• Turtle basics

Lecture 12

See EGR_103/Fall_2018/Lec_12

Lectures 13

Review

Lecture 14

Test

Lecture 15

• Use NumPy for linear algebra - specifically, create 2-d arrays using a list of list as an input argument to np.array()
• Dot product defines as the sum of the products of the corresponding elements in two arrays with the same number of elements
• Element-wise operations work with corresponding elements in two same-shape array or with an array and a scaler; examples include (*, /, +, -, **, trig, etc)
• Matrix multiplication is a collection of dot products between rows of the first array and columns of the second. Pick a row from the first and a column from the second - the resulting dot product goes in the same row as picked from the first array and the same column as picked from the second array.
• In Python 3.5 and above, the @ operator will do matrix multiplication; the np.dot(a, b) command also does matrix multiplication if a and b are 2-D arrays. If not using numpy, need to have a triple loop.
• See Chapter 8 in Chapra.

Lecture 16

See EGR_103/Fall_2018/Lec_16

Lecture 17

• Statistical definitions: mean, model, estimate, St, Sr, r2
• Coding statistics to quantify goodness of fit: Python:Fitting#Example_Code
• Differences between "mathematically good" (high \(r^2\)) versus "scientifically good"

Lecture 18

• Recap of stats and polyfit/polyval code
• Reminder that mathematically best fit for a given model has smallest Sr value
• Linear algebra proof of how to calculate coefficients for best fit - punch line is to pre-multiply linear algebra equation by transpose of functions matrix
• Key code is to build functions matrix and use np.linalg.lstsq to calculate coefficients:

a_mat = np.block([[xv**1, xv**0]])
pvec = np.linalg.lstsq(a_mat, yv, rcond=None)[0]

• See Python:Fitting#Example_Code_2 for complete example

Lecture 20 - Zeros and Optimizations

• SciPy references (all from Optimization and root finding):
  • scipy.optimize.brentq - closed method root finding
  • scipy.optimize.fsolve - open method root finding
  • scipy.optimize.fmin - unbounded minimization
  • scipy.optimize.fminbound - bounded minimization