BSc:AnalyticalGeometryAndLinearAlgebraI-CS

Analytical Geometry and Linear Algebra

• Course name: Analytical Geometry & Linear Algebra – I (Computer Science Track)
• Course number: 492
• Subject area: Mathematics

Course Characteristics

Key concepts of the class

• The subject and importance of Linear Algebra and Algebraic Geometry, its connections with other areas of Mathematics, Science, Technology and Engineering.
• Linear vector spaces.
• Cartesian coordinates and the 3D linear vector space.
• The dot product and the cross product of vectors, and their geometric meaning.
• Linear transformations of coordinates and vector. Matrices, matrix-vector and matrix-matrix operations.
• 3D coordinate transformations in physics and mechanics. Curvilinear coordinates.
• Solving systems of linear equations. Determinants, the Kramer rule. The Gaussian elimination method. Solution spaces.
• Equations and geometry of planes and straight lines in the 3D space.
• Second-order curves in a plane (conics), their invariants and classification.
• Second-order surfaces in 3D.
• The two-body problem in celestial mechanic, Keplerian orbital motion and computation of spatial and apparent coordinates of Solar System bodies.

What is the purpose of this course?

The main purpose of this course is two-fold:

• to lay down a firm and solid understanding by the student of Linear Algebra and Analytical Geometry fundamentals which are absolutely essential for subsequent studies of virtually any discipline in Mathematics, Computer Science, Natural Sciences and Engineering;
• to provide the first-year BSc students with reasonably non-trivial and interesting applications of Analytical Geometry, such as Keplerian orbital motion.

.

- What should a student remember at the end of the course?

By the end of the course, the students should be able to:

• Know the fundamental definitions and typical examples of Linear Vector Spaces, including the 2D and 3D Euclidian spaces.
• Know the definitions of (geometric) vectors, matrices, vector and matrix operations, the matrix determinant, and the use of matrices for specifying linear transformations of vector spaces.
• Know and remember firmly and forever that matrix multiplication is in general non-commutative.
• Know the definitions and geometrical meaning of the scalar (dot) and the vector (cross) products of vectors.
• Know the multiple forms of linear equations for planes and straight lines in the 3D space.
• Know and remember the basic methods for solving systems of linear equations – Cramer’s rule and Gaussian elimination.
• Know the definitions and types of second-order curves in a plane (conics) and second-order surfaces.
• Know that conics are not just abstract mathematical concepts – they play a fundamental role in Celestial Mechanics.

- What should a student be able to understand at the end of the course?

By the end of the course, the students should be able to:

• Understand the fundamental importance of Linear Algebra and Algebraic Geometry and its connections to nearly all areas of Mathematics, Physics, Natural Sciences, Computer Science, Economics and Finance, etc.
• Understand and perform vector and matrix operations.
• Understand the linear transformations of Cartesian coordinates and vectors in 2D and 3D spaces, and the curvilinear coordinate systems (e.g. cylindrical and spherical).
• Understand the role of dot and cross products of vectors, and how the fundamental operations of matrix algebra can be expressed in terms of vector dot products.
• Understand the connections between algebraic and geometric properties of planes, straight lines, conics and 2nd-order surfaces.
• Understand the solvability conditions of systems of linear equations and the geometry of solutions spaces.

- What should a student be able to apply at the end of the course?

By the end of the course, the students should be able to:

• Apply transformations of vector spaces and linear and non-linear coordinates to various problems in analysis, physics, computational geometry etc.
• Apply methods of solving linear equations to a wide spectrum of problems where they occur.
• Apply the theory of 2nd-order curves and surfaces to optimization problems in mathematical analysis, various problems in physics and mechanics, etc.

Course evaluation

Course grade breakdown

		Proposed points
Assignments and Labs	30	30
Interim performance assessment	20	20
Final Exam (Test)	50	50

Grades range

Course grading range

		Proposed range
A. Excellent	85-100	85–100
B. Good	65-84	65–84
C. Satisfactory	50-64	50–64
D. Poor	0-49	0–49

Resources and reference material

• M. Postnikov, Lectures in Geometry, Semester I: Analytic Geometry, Mir Publishers, Moscow, 1982.
• A. E. Roy, Orbital Motion, 4th ed., IoP Publishing, Bristol, 2005.

Course Sections

The main sections of the course and approximate hour distribution between them is as follows:

Course Sections

Section	Section Title	Teaching Hours
1	Introduction into Linear Algebra and Analytical Geometry. Linear Vector Spaces, Bases and Coordinates.	6
2	Dot and Cross Products of Vectors. Orthogonal Bases.	6
3	Linear Transformations of 2D and 3D vector spaces. Matrices, Operations on Vectors and Matrices, Determinants.	12
4	Solving Systems of Linear Equations. Cramer’s Rule and Gaussian Elimination.	12
5	Planes and Lines in 3D, their Equations and Geometry.	12
6	2nd-Order Curves (Conics) in a Plane. Classification and Invariants. Geometry of the Ellipse in detail.	12
7	2nd-Order Surfaces in 3D. Classification and Invariants. Application to Optimization Problems.	12
8	Applications of Coordinate Transforms and Conics to Space Trajectories. 2-Body Problem and Kepler’s Laws.	12

Section 1

Section title:

Introduction into Linear Algebra and Analytical Geometry. Linear Vector Spaces, Bases and Coordinates.

Topics covered in this section:

• Why Linear Algebra is of paramount importance for all other areas of Mathematics, as well as for Computer Science, Natural Sciences, Economics, etc. The relationship between Linear Algebra and Analytical Geometry.
• The axioms of the Linear Vector Space. Examples: Euclidian spaces, spaces of polynomials, etc.
• Basis of a Linear Vector Space.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 1
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1

Typical questions for ongoing performance evaluation within this section

1. Why do we need to study Linear Algebra and Analytical Geometry in the first place? Arethey or purely academic interest?
2. Provide the definition of the Vector.
3. Provide the axioms of the Linear Vector Space.
4. Provide meaningful examples of Linear Vector Spaces.

Typical questions for seminar classes (labs) within this section

1. What is the Basis of a Linear Vector Space? Is it unique?
2. What is the Dimensionality of a Linear Vector Space? Does it depend on the choice of basis?

Test questions for final assessment in this section

1. Provide a non-trivial example of a basis of the Euclidin 3D space.
2. Provide an example of 3 vectors in the 3D Euclidian space which do not form a basis.
3. What is the basis of the linear space of all polynomials in 1 variable (${\textstyle x}$) of degree up to 3? And the basis of all polynomials in ${\textstyle x}$? Do all polynomials in ${\textstyle x}$ of degree exactly 3 form a linear vector space?

Section 2

Section title:

Dot and Cross Products of Vectors. Orthogonal Bases.

Topics covered in this section:

• Euler angles and directing cosines.
• Definition and geometric meaning of the Dot Product of vectors.
• Definition and geometric meanings of the Cross Product of vectors.
• The bi-linearity property of the dot and cross Products.
• Orthogonal Bases. Dot and cross products of vectors in orthogonal bases.
• Projection of vectors onto other vectors and planes.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 1
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0

Typical questions for ongoing performance evaluation within this section

1. Compute dot and cross products of given vectors.
2. Prove that the dot product is invariant under rotation of the coordinate axes. Is the cross product invariant as well?
3. Compute matrix sums, products, matrix-vector products.

Typical questions for seminar classes (labs) within this section

1. For a vector given by its length and Euler’s

Test questions for final assessment in this section

1. Comp

Section 3

Section title:

Linear Transformations of 2D and 3D vector spaces. Matrices, Operations on Vectors and Matrices, Determinants.

Topics covered in this section:

• Examples of Linear Transforms in 2D and 3D. Rotations and symmetries. Parallel shifts (translations).
• The Dot (Scalar) Product of vectors, its geometric meaning and invariance under rotation.
• First notion of the Cross (Vector) Product of 3D vectors, its geometrical meaning.
• Coefficients of linear transforms as dot products.
• Matrix notation for linear transforms. Matrix-vector multiplication. Matrix addition.
• Composition of linear transforms as matrix multiplication. The unit matrix.
• Inverse linear transform as matrix inversion. Existence of the inverse. Computing of the inverse in simplest cases. The Determinant in 2D and 3D cases.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 1
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1

Typical questions for ongoing performance evaluation within this section

1. Write down the formulas (in expanded form) for a 3D rotation around a given axis with a given angle.
2. As above, but in matrix form.
3. Compute matrix sums, products, matrix-vector products.

Typical questions for seminar classes (labs) within this section

1. Construct the inverse to a given linear transform and express it in matrix form.
2. Explain geometrical meaning of dot and cross products of vectors.
3. Derive the cross product formula from the orthogonality conditions expressed via dot products.
4. Construct linear transforms (and their matrices) for geometrically-presented rotations and shifts.

Test questions for final assessment in this section

1. Compute a composition of several linear transforms by matrix multiplication.
2. Derive the conditions under which multiplication of ${\textstyle 2\times 2}$ matrices would commute.

Section 4

Section title:

Solving Systems of Linear Equations. Cramer’s Rule and Gaussian Elimination.

Topics covered in this section:

• Connection between Entropy, Expected Code Length and the Data Compression Rate. The Shannon Theorem and the Gibbs Inequality.
• Huffman, Shannon-Fano, Arithmetic and Block codes.
• Lempel-Ziv compression algorithm (LZ78).

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0

Typical questions for ongoing performance evaluation within this section

1. Explain the connection between the source entropy and the expected codeword length.
2. Explain the principles of Huffman, Shannon-Fano, Arithmetic and Block codes.
3. Formulate the LZ78 algorithm.

Typical questions for seminar classes (labs) within this section

1. Estimate the expected codeword length for a given information source.
2. For a given message source, construct the Huffman encoding.
3. In a similar setup, construct the Shannon-Fano encoding.
4. Implement / elaborate the LZ78 algorithm.

Test questions for final assessment in this section

Similar to seminar (lab) questions above, but include elaboration of data compression algorithms on paper rather than computer implementations.

Section 5

Section title:

Planes and Lines in 3D, their Equations and Geometry.

Topics covered in this section:

• When lossy compression is applicable: Images, Audio and Video streams.
• Example: Compression of 2D images
• Fourier Transform and its applications
• The Fast Fourier Transform algorithms. The Cooley-Tukey FFT algorithm.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1

Typical questions for ongoing performance evaluation within this section

1. When would lossy compression algorithms be applicable?
2. Explain the principles of lossy image, audio and video compression.
3. How can Fourier Transform be used for (lossy) data compression?
4. Explain the rationale behind the Fast Fourier Transform algorithms.

Typical questions for seminar classes (labs) within this section

1. Implement the Cooley-Tukey FFT algorithm in software.
2. Apply the FFT method to compression and decompression of image files.

Test questions for final assessment in this section

1. Provide the formulas of direct and inverse Fourier Transform in 1 and multiple dimensions.
2. Elaborate the Cooley-Tukey FFT algorithm.

Section 6

Section title:

2nd-Order Curves (Conics) in a Plane. Classification and Invariants. Geometry of the Ellipse in detail.

Topics covered in this section:

• The motivation behind EDC/ECC.
• Examples of hardware and software implementations of EDC/ECC.
• Hamming Codes.
• Hashing Functions as non-linear EDC.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1

Typical questions for ongoing performance evaluation within this section

1. Provide a list of hardware implementations of ECC/EDC in commodity-of-the-shelf computers and communication devices.
2. Describe the principles of Hamming codes construction.

Typical questions for seminar classes (labs) within this section

1. Specify the encoding and decoding algorithms of the Hamming code (7,4) in the matrix form, including the error detection and correction operations. How many errors can it detect and correct?
2. Specify the desirable properties of a hashing function.
3. Provide a list of commonly-used “strong” hashing functions.

Test questions for final assessment in this section

• Specify the encoding and decoding algorithms of the general Hamming code of the order ${\textstyle (k,l)}$. What are the admissible values of ${\textstyle k}$ and ${\textstyle l}$? How many errors can it detect and correct?
• Suppose that we are building a hardware data integrity layer for an SSD (solid state drive) of 1 terabyte capacity, which must be able to preserve the data integrity even if an entire disk block (2 kbytes) is lost anywhere in SSD. How much data redundancy would this mechanism require? Which ECC/EDC would you use to that end?

Section 7

Section title:

2nd-Order Surfaces in 3D. Classification and Invariants. Application to Optimization Problems.

Topics covered in this section:

• Introduction into Cryptography and Cryptanalysis. The historical perspective: code books and Enigma.
• Foundations of the Pre-Shared (Symmetric) Key cryptography. The Feistel framework.
• The DES algorithm. The S-Boxes as a non-linear core of DES. Weaknesses of DES. Extensions and analogues of DES (3DES, Russian GOST).
• A recap of Higher Algebra: Groups, Rings, Fields
• Finite Fields: ${\textstyle Z_{p}}$ and Galois Fields ${\textstyle GF(p^{n})}$.
• Galois Fields in Cryptography: the modern AES algorithm.
• Introduction into public-key cryptography: the RSA framework.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1

Typical questions for ongoing performance evaluation within this section

1. Explain the difference between the terms “encoding” and “encryption”.
2. Explain the typical cryptanalysis techniques from the historical perspective.
3. What are the desirable properties of an encryption algorithm from the Entropy point of view?
4. Is the non-linearity property essential for an encription algorithm? Why or why not? How is this issue addressed in DES?

Typical questions for seminar classes (labs) within this section

1. Describe the DES algorithm in details.
2. Explain the weaknesses of DES, and how they can be rectified.
3. Provide the definitions and typical examples of Groups, Rings and Fields.
4. For which orders ${\textstyle n}$ a finite field of order ${\textstyle n}$ would exist?

Test questions for final assessment in this section

1. Construct the addition and multiplication tables for a given ${\textstyle Z_{p}}$ field.
2. Construct the addition and multiplication tables for a given Galois field.
3. Explain the details of the AES encryption algorithm.
4. Explain the principles of the RSA public-key cryptography framework.