CS计算机代考程序代写 AI algorithm REVIEW

REVIEW

Linear Algebra

1

Matrices

Notation:




Matrices are denoted by bold uppercase letters
Aij denotes the entry in i th row and j th column
If A is n × m, it has n rows an m columns
If A is n × m, then A

6.3 1.0 2.2
3.6 4.7 8.9

A11
3.3 5.3 4.5
1.0 4.5 3 .4 . A32

Rn m

A =
4 × 3

A matrix is a 2-dimensional array

Î ´

2

Vectors

Notation:


Vectors are denoted by bold lowercase letters
ai denotes the ith entry
If a is m dimensional, then a

3.3
1.0
6.3
3.6

.
a2

a =A vector is a matrix with
many rows and one column

RmÎ

3

Transpose
Swap the rows and columns of a matrix

3 × 2 2 × 3

3
4
1

1 3
6 1
3 5

3 × 1 1 × 3

(A⊤)21

Properties of matrix transposes:
• Aij = (A⊤)ji
• If A is n × m, then A⊤ is m × n

A12

4

Addition and subtraction
These are element-wise operations

3 5
6 1

+
4 5
8 12

=
3 +4
6 +8Addition:

Subtraction:
5
1


4
3

=
5 —4
1 —3

5

Matrix scalar multiplication
We multiply each matrix element by the scalar value

3 3 5 4
6 1 2

=
9 15 12

3 618

—0.5 3
8

=
—1.5
—4

6

Matrix-vector multiplication
Involves repeated scalar products

1 4 3
6 1 2

4
2
—7

=

1 x 4 +4 x 2 +3 x (—7)=—9

6 x 4 +1 x 2 +2 x (—7)= 12

7

Matrix-vector multiplication

=

A w y

n × m m × 1 n × 1

ith row

yi equals scalar
product between ith

row of A and w

To perform inner products, # columns
in A must equal # rows of w

We repeat for each
row of A, so if A has
n rows, so does y

8

Matrix-matrix multiplication
Also involves several scalar products

18

9

Matrix-matrix multiplication
A B C

m × pn × m n × p

=

To perform inner products,
# columns in A must equal

# rows of B

ijC is scalar product
of ith row of A and

jth column of B

We repeat for each
row of A, so if A has
n rows, so does C

ith row

jth col

We repeat for each
column of B, so if B has p

columns, so does C
10

Matrix-matrix multiplication

m × pn × m n × p

Associative, i.e., (AB)C = A(BC)

Not commutative, i.e., AB ≠ BA

CBA

11

Identity matrix
One is the scalar multiplication identity, i.e., c × 1 = c

In is the n × n identity matrix, i.e., InA = A and AIm = A forany
n × m matrix A

Identity matrices are square, with ones on the diagonal entries

9 3 5
4 1 2

1 0 0
0 1 0
0 0 1

=
9 3 5
4 1 2

12

Inverse matrix
1/c is the scalar inverse, i.e., c × 1/c = 1

Multiplying a matrix by its inverse results in the identity matrix


For an n × n matrix A, A-1 denotes its inverse (when it exists)

AA-1 = A-1A = In

Only a square matrix (when n = m) can have an inverse

13

Euclidean norm for vectors

14

REVIEW

Big O Notation

15

Big O Notation
Describes how algorithms respond to changes in input size


Both in terms of processing time and space requirements We
refer to complexity and Big O notation synonymously

Required space proportional to units of storage
• Typically 8 bytes to store a floating point number

Required time proportional to number of ‘basic operations’
• Arithmetic operations (+, −, ×, /), logical tests (<, >, ==)

16

Big O Notation

Notation:


For large enough x, these terms won’t matter
E.g., x2+3x ≤ Cx2

f(x) =O(g(x))
• Can describe an algorithm’s time or space complexity

Informal definition: f does not grow faster than g

Formal definition: |f(x)| ≤ C|g(x)|

Ignores constants and lower-order terms

Nx >”

Nx >”

17

O(1) complexity

Constant time algorithms perform the same number of operations every
time they’re called
• E.g., performing a fixed number of arithmetic operations

Similarly, constant space algorithms require a fixed amount of storage every
time they’re called
• E.g., storing the results of a fixed number of arithmetic operations

EXAMPLE 1 :

18

O(n) complexity

Linear time algorithms perform a number of operations proportional to the number
of inputs
• E.g., adding two n-dimensional vectors requires O(n) arithmetic operations

Similarly, linear space algorithms require storage proportional to the size of the
inputs
• E.g., adding two n-dimensional vectors results in a new n-dimensional vector

which requires O(n) storage

EXAMPLE 2 :

19

O(n2) complexity

Quadratic time algorithms perform a number of operations proportional to the
square of the number of inputs
• E.g., outer product of two n-dimensional vectors requires O(n2) multiplication

operations (one per each entry of the resulting matrix)

Similarly, quadratic space algorithms require storage proportional to the square of
the size of the inputs
• E.g., outer product of two n-dimensional vectors requires O(n2) storage (one

per each entry of the resulting matrix)

EXAMPLE 3 :

20

Time and space complexity can differ

Inner product of two n-dimensional vectors

O(n) time complexity to multiply n pairs of numbers O(1)
space complexity to store result (which is a scalar)

Matrix inversion of an n × n matrix

O(n3) time complexity to perform inversion O(n2)
space complexity to store result

21

Matrix-vector multiply

Goal: multiply an n × m matrix with an m × 1 vector

Computing result takes O(nm) time

There are n entries in the resulting vector
Each entry computed via dot product between two m-dimensional vectors
(a row of input matrix and input vector)

Storing result takes O(n) space
• The result is an n-dimensional vector

EXAMPLE 1 :

22

Matrix-matrix multiply

Goal: multiply an n × m matrix with an m × p matrix

Computing result takes O(npm) time

There are np entries in the resulting matrix
Each entry computed via dot product between two m-dimensional vectors

Storing result takes O(np) space
• The result is an n × p matrix

EXAMPLE 2 :

23