CAP 1 Flashcards
What is a matrix?
A matrix is an array of elements set out in a pair of brackets.
How many rows and columns does a MxN matrix have?
M rows and N columns
What is a square matrix
A matrix that has the same number of rows as columns
What is an identity matrix?
A matrix with 1s in the leading diagonals with all other elements as 0
What must be true for matrices to be added or subtracted?
The matrices must have the same dimensions.
What is a scalar?
A dimensional quantity - a number
What law is A * (B * C) = (A * B) * C ?
The associative law
What law is A * B = B * A
The commutative law
Is matrix addition associative/commutative?
Yes, both
Is matrix subtraction associative/commutative?
No. neither
Is matrix multiplication commutative?
Not in general
The composite matrix ABCD should be multiplied from…
… right to left
A(B(C(D)))
What point always maps onto itself after a linear transformation?
The origin
(k 0)
0 k
An enlargements by scale factor k
(k 0)
0 1
Stretch scale factor k parallel to X axis
(1 0)
0 k
Stretch scale factor k parallel to Y axis
Rotation, anticlockwise by θ
(cos θ - sin θ)
sin θ cos θ
G followed by H is …
H x G
P followed by Q is …
Q x P
(1 k)
0 1
A shear, x - axis fixed, with (0,1) mapped to (k,1)
(1 0)
k 1
A shear, y - axis fixed, with (1,0) mapped to (1,k)
A shear maintains…
area
Invariant points are…
points which map to themselves
How do you find points that are invariant under a transformation:
(a b)
(c d)
(a b) x (x) = (x)
c d) x (y) = (y
What is a plane?
A plane is a flat two-dimensional surface that extends infinitely far.
I3 with one -1 is a…
…reflection in a plane
I3 with two -1 is a…
…rotation 180 around an axis
What is an algorithm?
An algorithm is a FINITE sequence of operations for carrying out a procedure.
What are the three conditions for an algorithm?
- Must be unambiguous
- Must be deterministic (no chance or randomness)
- Must be finite
How do you find the lower bound for bin packing?
Add all of the lengths together and divide by the bin-size
First fit: remember to…
- Write “saturated”
First fit decreasing: remember to:
- Write out the ordered elements in decreasing order
2. Write “saturated”
True or False: Full Bin strategy is the most efficient bin packing algorithm.
False, because full bin strategy is not an algorithm
What is meant by a heuristic algorithm?
An algorithm that will usually find a good solution, although not necessarily an optimal solution.
Quick sort: remember to
- circle pivot
2. underline sorted values
What complexity does quick sort have?
quadratic complexity
What is the maximum number of comparisons for quick sort?
0.5 * n^2 * n
What is a minimum spanning tree?
A minimum spanning tree is the least weight connected graph that includes every vertex and contains no cycles
What is the complex conjugate of a + bi
a - bi
z = a + bi …
zz* = …
zz* = a^2 + b^2
What is the complex conjugate root theorem?
If a polynomial with real coefficients has a root z = a + bi, then z = a - bi is also a root.
(Roots always come in pairs)
What are the first 2 lines of working for the question…
A quadratic equation has a root 3-2i. Find the quadratic equation
, if 3-2i us a root, then 3+2i is also a root bit the complex conjugate root theorem.
(z - ( 3-2i )) ( z - ( 3+2i )) = 0
If a quadratic equation has roots P and Q, write the quadratic equation.
z^2 - (P+Q)z + PQ = 0
How do you square root 3+4i?
3+4i = (a+bi)^2
3 = a^2 - b^2
4 = 2ab
^equate real and imaginary parts
Solve sim eqs.
Multiplying by i… (in terms of argand diagram)
… rotates the number by 90 anticlockwise about the origin
180 degrees in radians
pi
2pi radians in degrees
360
90 degrees in radians
pi/2
What is the cartesian form of a complex number?
z = x + iy
If z = x + iy, what is θ?
θ = arg(z) = arctan (y/x)
If z = x + iy, what is r?
r = |z| = sqrt(x^2 + y^2)
What is the range of arguments θ in modulus argument form?
-pi < θ <= pi
aka the principal argument
Write z in modulus argument form
z = r (cosθ + i sin θ)
Multiplying two complex numbers together …
… multiplies their moduli (length) and adds their arguments
Multiplying two complex numbers together …
… divides their moduli (length) and subtracts their arguments
|z| = r represents …
|z| = r represents a circle centred at the origin with radius r
|z-a| = r represents …
|z-a| = r represents a circle centred at ‘a’ with radius r
arg(z-a) = θ represents the…
arg(z-a) = θ represents the locus of a half line of points from a measured θ from the positive horizontal axis.
z=a is NOT a part of the locus
|z-a| = |z-b| represents…
|z-a| = |z-b| represents all points which lie on the perpendicular bisector of a and b
What two ways are there to solve |z-a| = |z-b|
- Using the normal perpendicular bisector method
2. equate equations of circle
