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.

vectorAdditon.png

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.

vectorSubtraction.png

  • 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

vectorConvex.png

  • 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.