CSCE 411 Lecture 38

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 $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 $T_2{n}^2$. Then the total number of instructions is given by

$T_1(n+1)+\sum _{k+1}^n{T}_2{k}^2$

Where $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

$\sum _{k=a}^{b}g(k)$

can be regarded as discrete analogs of integrals

$\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x$

We can evaluate the integral by finding a function $f(x)$ such that $\frac{\mathrm{d}}{\mathrm{d}x}f(x)=g(x)$, since FTC gives

$\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x=f(b)-f(a)$

Difference Operator

Represented as symbol $\mathrm{\Delta }$:

$\mathrm{\Delta }g(n)=g(n+1)-g(n)$

Let $E$ denote the shift operator $Eg(n)=g(n+1)$, and $I$ the identity operator, then

$\mathrm{\Delta }=E-I$

Examples:

1. $f(n)=n$: $\mathrm{\Delta }f(n)=n+1-n=1$
2. $f(n)=n^2$: $\mathrm{\Delta }f(n)=(n+1{)}^2-n^2=2n+1$
3. $f(n)=n^3$: $\mathrm{\Delta }f(n)=(n+1{)}^3-n^3=3n^2+3n+1$

Falling Power

The $m$-th falling power of $n$ is defined as

$n^{\underset{\_}{m}}=n(n-1)\dots (n-m+1)$

For $m\ge 0$

$\mathrm{\Delta }{n}^{\underset{\_}{m}}=m{n}^{\underset{\_}{m-1}}$

Proof. By definition

$\begin{array}{rl}\mathrm{\Delta }{n}^{\underset{\_}{m}}& =(n+1)n\dots (n-m+2)-n\dots (n-m+2)(n-m+1)\\ & =mn\dots (n-m+2)\end{array}$

What about negative numbers?

$\frac{n^{\underset{\_}{0}}}{n^{\underset{\_}{-1}}}=n+1$, so $n^{\underset{\_}{-1}}=\frac{1}{n+1}$

Continue recursively to define

$n^{\underset{\_}{-m}}=\frac{1}{(n+1)(n+2)\dots (n+m)}$

So for $m\ge 0$,

$\mathrm{\Delta }{n}^{\underset{\_}{-m}}=-m{n}^{\underset{\_}{-m-1}}$

Exponentials

$\mathrm{\Delta }{c}^n=(c-1)c^n$

In particular, $\mathrm{\Delta }{2}^n=2^n$... Hey!