Fundamentals of data structures- Vectors
Table of Contents
1 Abstract data type - Vectors
Vector application
- used in games and modelling: simulate character/object movements
- robotics: control movements or autonomous movement in an environment
Vector Notations
- Vectors can be represented as:
a list of numbers
:- [3, 5, 2.3, 9.4]. This a 4-vector over R which can be written as R4
- in Python, this can be a list or one dimensional array
a function
:- f: S->R where -> means maps to, S ={0,1,2,3} and R is a collection of real numbers. Therefore, using the real number list R above, 0->3, 1->5, 2->2.3, 4->9.4.
- This can be represented using a dictionary: {0:3, 1:5, 2:2.3, 4:9.4}
a point in space
:- vector A =(6,9), vector B=(7, 3) in the diagram below.
Vector additon, subtraction, scaling, convex and dot product
vector addition
- as shown in the above diagram, A+B = (6+7, 9+3). This ressults in a new vector C = (13,12)
vetcor subtraction
- A-B=(6-7, 9-3) = (-1, 7). Let D = (-1,6). The resulting vector is shown in the diagram below.
vector scaling
:- a vector can be scaled up or down by nultiplying its x, y value by the same number.
- the resulting vector will have the same direction E = A*5 = (30, 45)
Convex combinations of two vectors
- F = x*A + y*B where x + y = 1
- the resulting vector F will always be inside the area defined by vector A and B
- F = x*A + y*B where x + y = 1
dot product/scalar product
of two vectors A.B = [6,9].[7,3]=6*7+9*3=42+27=69 <- a scalar NOT a vector
Vector in parity checking
- a bit pattern can be represented as a vector, for example, V=[1,0,0,1]
- using another vector with all 1s, W=[1,1,1,1]
- V.W = (1 AND 1) XOR (1 AND 0) XOR (1 AND 0) XOR (1 AND 1)= 0 XOR 1 XOR 1 XOR 0 = 0
- The resultinhg bit 0 can be used as either an indication of even parity (1 for odd) or as the parity bit needs to be added to achieve even parity.