black-box and white box

black-box testing
-can work with code that cannot be modified
-does not need to analyze or study code
-code can be in any format(managed, binary, obfuscated)

White-box testing
-efficient test suite
-potentially better coverage

HttpPost localHttpPost = new HttpPost(...);
(new DefaultHttpClient()).execute(localHttpPost;

Automated testing is hard to do
probably impossible for entire system

A pre-condition is a predicate
A post-condition is a predicate

class Stack{
	T[] array;
	int size;

	Pre: s.size() > 0
	T pop() { return array[--size]; }
	Post: s'.size() == s.size() -1

	int size() { return size; }
}

int foo(int[] A, int[] B){
	int r = 0;
	for (int i = 0; i < A.length; i++){
		r += A[i] * B[i];
	}
	return r;
}

Software Testing

Learn methods to improve software quality
-reliability, security, performance
-Become a better software developer

Security Vulnerabilities
-Exploits of errors in programs

Dynamic, static, hyprid

An invariant at the end of the program

int p(int x){ return x * x; }
void main(){
	int z;
	if(getc() == 'a')
		z = p(6) + 6;
	else
		z = p(-7) -7;

	if (z != 42)
		disaster();
}
void main(){
	z = 3;
	while (true){
 	 if(x == 1)
 	 	y = 7;
 	 else
 	 	y = z + 4;
 	 assert (y == 7);
	}
}

Functions for Lines

from decimal import Decimal, getcontext

from vector import vector
getcontext().prec = 30


class Line(object):
	NO_NONZERO_ELTS_FOUND_MSG = 'No nonzero element found'

	def __init__(self, normal_vector=None, constant_term=None):
		self.dimension = 2

		if not normal_vector:
			all_zeros = ['0']*self.dimension
			normal_vector = Vector(all_zeros)
		self.normal_vector = normal_vector

Ax + By + Cz = k1
Dx + Ey + Fz = k2
[A B C], [D E F] not parallel
dx = vector from x0 to x
Since x0, x in plane 1, dx is orth to n1

-One equation in two variables defines a line
-One equation in three variables define a plane

Caution: Count variables with coefficient 0
x + y = 2 defines a line in 2D
x + y = 2 defines a plane in 3D

systematically manipulate the system to make it easier to find the solution
– Manipulations should preserve the solution
– Manipulations should be reversible

Intersections

Geometric object = a set of points satisfying a given relationship(e.g. equations)

“Flat” = defined by linear equations
Linear equations:
-Can add and subtract variables and constants
-Can multiply a variable by a constant

Linear: x + 2y = 1, y/2 – 2z =x
Nonlinear: x^2 -1 = y, y/x = 3

Equations come from observed or modeled relationships between real-world quantities.

ML for trading
stock:A, B
Wa = proportion of portfolio invested in A
Wb = proportion of portfolio invested in B
0 < Wa, Wb < 1 β value = measure of correlation of a stock's price movements with market movement β of portfolio = weighted average of individual components' β values Wa + Wb = 1 B portfolio = 2Wb - Wa = 0 Variables: weights of the stocks Constraints: equations representing physical realities or objectives Lines in Two dimensions Two pieces of info define a line -basepoint x -direction vector v x(t) = x + tv Ax + By = 0 (A and B not both 0)

Inner Products

Inner Products(Dot Products)
v*w = ||v||*||w||*cosΘ

def dot(self, v):
	return sum([x*y for x,y in zip(self.coordinates, v.coordinates)])

	def angle_with(self, v, in_degrees=False)
		try:
			u1 = self.normalized()
			u2 = v.normalized()
			angle_in_raddians = acos(u1.dot(u2))

			if in_degrees:
				degrees_per_radian = 180./ pi
				return angle_in_radians * degrees_per_radian
			else:
				return angle_in_radians

			except Exception as e:
				if str(e) == self.CANNOT_NORMALIZE_ZERO_VECTOR_MSG:
					raise Exception('Cannot compute an angle with the zero vector')
				else:
					raise e

Magnitude and Direction

P -> Q
magnitude of v = distance between P and Q
h^2 = (△x)^2 + (△y)^2
v = √(Vx^2 + Vy^2)

-A unit vector is a vector whose magnitude is 1.
-A vector’s direction can be represented by a unit vector.

Normalization: process of finding a unit vector in the same direction as a given vector.
[0 0 0] = 0
||0|| = 0
1 / ||0|| = ?

def magnitude(self):
	coordinates_squared = [x**2 for x in self.coordinates]
	return sqrt(sum(coordinates_squared))

def normalized(self):
	try:
		magnitude = self.magnitude()
		return self.times_scalar(1./magnitude)

	except ZeroDivisionError:
		raise Exception('Cannot normalize the zero vector')

def plus(self, v):
	new_coordinates = [x+y for x,y in zip(self.coordinates, v.coordinates)]
	return Vector(new_coordinates)

Operating on Vectors

– Addition
– Subtraction
[1 3] – [5 1] = [-4 2]
– Scalar Multiplication
2, 1, 1/2, -3/2

[8.218 -9.341]+[-1.129 2.111]=[7.089 -7.23]
[7.119 8.215] – [-8.223 0.878]=[15.342 7.337]
7.41[1.671 -1.012 -0.318]= [12.382 -7.499 -2.356]

def plus(self, v):
	new_coordinates = [x+y for x,y in zip(self.coordinates, v.coordinates)]
	return Vector(new_coordinates)

def minus(self, v):
	new_coordinates = [x-y for x,y in zip(self.coordinates, v.coordinates)]
	return Vector(new_coordinates)

def times_scalar(self, c):
	new_coordinates = [c*x for x,y in zip(self.coordinates, v.coordinates)]
	return Vector(new_coordinates)

def __str__(self):
	return 'Vector: {}'.format(self.coordinates)

def __eg__(self, v):
	return self.coordinates == v.coordinates

Point and Vectors

Points
-represent location
-written as (x,y,z…)
e.g. (2,-1)

Vectors
-represent change in location
-magnitude and direction
-written as [x,y,z…]

Common practice to interchange points and vectors
Technically different but often a useful shortcut
V=[-2, -3] P=(-2,-3)
P=(-4,-4), Q=(4,-2)
v=[-1,4],w=[-2,0]

class Vector(object):
	def __init__(self, coordinates):
		try:
			if not coordinates:
				raise ValueError
			self.coordinate = tuple(cordinates)
			self.dimension = len(coordinates)

		except ValueError:
			raise ValueError('The coordinates must be nonempty')

		except TypeError:
			raise TypeError('The coordinate must be an iterable')

	def __str__(self):
		return 'Vector: {}'.format(self.coordinates)

Branches

1.Conditional branches
2.Unconditional branches
3.Function Calls
4.Indirect Jumps

Branch Architecture
Speculation: predicting branches, executing in anticipation
Predication: removing branches, converting code into one that depends on outcome of a condition for a commit.

VLIW Data Path

The way things are organized inside processors to allow storage of data!

CISC and DSP
-Memory-to-memory and complex addressing modes
-Accumulator:a target register of ALU
-Some storage specialities force complier to make binding choice and optimizations too early

RISC and VLIW
-Registers-to-registers: large register files
-Decoupling scheduling and register allocation

Processor: 16×16 bit, 32x32bit
ARM7, ARM9E, ARMv5TE

VLIW Machine:A VLIW machine with 8 32-bit independent datapaths

In the embedded world, characteristics of application domain are also very important
Simple Integer and Compare Operations
Carry, Overflow, and other flags

Fixed Point Multiplication

Partial interconnect clusters promise better scalability
The bypass network of a clustered VLIW is also partitioned.

Index Register Files
illegal, outputs locals, static
-compiler can explicitly allocate a variable-sized section of the register file
-used in proc call and return for stack management

VLIW instructions are separated into primitive instructions by the compiler.
During each instruction cycle, one VLIW word is fetched from the cache and decoded.
Instructions are then issued to functional units to be executed in parallel.
Since the primitive instructions are from the same VLIW word, they are guaranteed to be independent.

VLIW is load/store architecture
– mostly reuse RISC memory-addressing concepts
– special addressing modes
– registers – data and address
– memory could be banked, power efficient
– X-Y memory
– GPUs constant memory, shader memory, shared memory, local memory