CSCE 411 Lecture 38

From Notes
Jump to navigation Jump to search
Lecture Slides

« previous | Wednesday, November 28, 2012 | next »


Race Conditions

A determinancy race occurs when two logically parallel insturcitions access the same memory location at at least one of the instructions performs a write. 

def race_example():
  x = 0
  parallel for i in [1..2]:
    x = x+1

What is the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ?

Matrix Multiplication

Simple divide and conquer algorithm: 

def matrix_add(C, T, n):
  # Adds matrices C and T in-place, producing C = C + T
  # n is a power of 2 for simplicity
  if n == 1:
    C[1, 1] = C[1, 1] + T[1, 1]
  else:
    partition C and T into 4 n/2 x n/2 matrices
    spawn matrix_add(C[1,1], T[1,1], n/2)
    spawn matrix_add(C[1,2], T[1,2], n/2)
    spawn matrix_add(C[2,1], T[2,1], n/2)
    spawn matrix_add(C[2,2], T[2,2], n/2)
    sync

def matrix_multiply(C, A, B, n):
  # Multiplies matrices A and B, storing the result in C. // n is power of 2 (for simplicity).
  if n == 1:
    C[1, 1] = A[1, 1] · B[1, 1]
  else:
    allocate a temporary matrix T[1...n, 1...n]
    partition A, B, C, and T into (n/2)x(n/2) submatrices
    spawn matrix_multiply(C11,A11,B11, n/2)
    spawn matrix_multiply(C12,A11,B12, n/2)
    spawn matrix_multiply(C21,A21,B11, n/2)
    spawn matrix_multiply(C22,A21,B12, n/2)
    spawn matrix_multiply(T11,A12,B21, n/2)
    spawn matrix_multiply(T12,A12,B22, n/2)
    spawn matrix_multiply(T21,A22,B21, n/2)
    spawn matrix_multiply(T22,A22,B22, n/2)
    sync
    matrix_add(C, T, n)


Calculus of Finite Differences

Lecture Slides

Motivation

Analyze running time of algorithms: count number of operations: 

for i in [1..n]:
  square(i)

where square(n) is a function that has running time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_2n^2} . Then the total number of instructions is given by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_1(n+1) + \sum_{k+1}^n T_2k^2}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_1} is the time for loop increment and comparison. (increment and compare happens an extra time to determine "break" condition.

How do you evaluate that monster‽

Find closed form representation other than looking it up or guessing the solution.


Discrete sums

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=a}^b g(k)}

can be regarded as discrete analogs of integrals

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b g(x) \, \mathrm{d}x}

We can evaluate the integral by finding a function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{\mathrm{d}}{\mathrm{d}x} \, f(x) = g(x)} , since FTC gives

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b g(x) \, \mathrm{d}x = f(b) - f(a)}


Difference Operator

Represented as symbol Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta g(n) = g(n+1) - g(n) \,\!}

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} denote the shift operator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Eg(n) = g(n+1)} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} the identity operator, then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta = E - I\,\!}

Examples:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = n} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta f(n) = n+1 - n = 1}
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = n^2} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta f(n) = (n+1)^2 - n^2 = 2n+1}
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = n^3} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta f(n) = (n+1)^3 - n^3 = 3n^2 + 3n + 1}

Falling Power

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -th falling power of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is defined as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{m}} = n(n-1)\dots(n-m+1)}

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ge 0}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta n^{\underline{m}} = mn^{\underline{m-1}}}

Proof. By definition

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \Delta n^{\underline{m}} &= (n+1) n \dots (n-m+2) - n \dots (n-m+2)(n-m+1) \\ &= mn\dots(n-m+2) \end{align}}


What about negative numbers?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{n^{\underline{0}}}{n^{\underline{-1}}} = n+1} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{-1}} = \frac{1}{n+1}}

Continue recursively to define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{-m}} = \frac{1}{(n+1)(n+2) \dots (n+m)}}

So for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ge 0} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta n^{\underline{-m}} = -mn^{\underline{-m-1}}}


Exponentials

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta c^n = (c-1)c^n\,\!}

In particular, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta 2^n = 2^n} ... Hey!

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_411_Lecture_38&oldid=3302"