20872  MATHEMATICAL METHODS IN COMPUTER SCIENCE
Department of Decision Sciences
ELIA BRUE'
Mission & Content Summary
MISSION
CONTENT SUMMARY
Topics in linear algebra:
1. Review of basic concepts:
 Real and Complex vector spaces
 Linear operators
 Eigenvalues, eigenvectors
2. The Geometry of linear algebra:
 Real and Hermitian inner product
 Orthogonality, orthonormal bases
 Projections, orthogonal projections, variational characterization
 The Unitary and Orthogonal Group
3. Matrix norms
 Norms, pnorms
 Operator norms
 HilbertSchmidt inner product
 Spectral radius, Gelfand formula, variational characterization of the spectral radius*
4. Hermitian and Normal operators
 Hermitian operators
 Normal operators
 Spectral Theorem
 Variational characterization of eigenvalues, Rayleigh quotient, generalized Rayleigh quotient
 Spectral mapping theorem
 Complements*: Infinite dimensional spaces, compact operators, Laplacian and Poincarè inequality
5. SVD Decompositiona and applications
 Singular Values, variational characterization
 SVD decomposotion
 EckartYoung, the closest rank kmatrix
 Least square method, pseudo inverse
6. Multilinear Algebra*
 Multilinear forms
 Exterior product, exterior algebra
 Determinant, volume
 Crossproduct in R^3, applications, and relations with projections
Topics in discrete mathematics:
1. Review of basic concepts
 Set theory
 Functions and relations
 Counting methods
2. Graph theory
 Review of the basics: Terminology, type of graphs, connectivity
 Representation of a graph: Adjacency matrix, Incidence matrix
 Spectral graph theory: The Laplacian matrix and its eigenvalues
 Cheeger inequalities*
3. More on counting*
 Generating functions
 Recurrence relations
4. Asymptotics
 Basics of asymptotic analysis: big O notation, hierarchy
 Big O manipulation, examples
 Asymptotic combinatorics: examples
Intended Learning Outcomes (ILO)
KNOWLEDGE AND UNDERSTANDING
 Comprehend the geometric concepts involved in the formalism of linear algebra.
 Understand scalar products, norms, and operator norms in real and complex settings.
 Develop familiarity with the spectral theorem for normal and Hermitian operators.
 Understand the SVD decomposition and its applications.
 Acquire a basic understanding of graph spectral theory.
APPLYING KNOWLEDGE AND UNDERSTANDING

Perform diagonalization and matrix decompositions, both real and complex, and utilize these tools to compute projections and matrix functions.

Use scalar products, norms, and operator norms in optimization and variational problems.

Manipulate expressions involving exterior products, inner products, trace operators, and operator functions.

Solve counting problems using and determine the asymptotic growth in recurrence relations and combinatorial problems.
Teaching methods
 Practical Exercises
DETAILS
Students are assigned weekly exercises that are directly related to the concepts taught during the week. These exercises are meant to be solved independently by the students.
During the subsequent week's class, we will collaboratively solve and engage in discussions on the assigned exercises.
This approach promotes active learning, as students have the opportunity to engage in collaborative problemsolving. By discussing the exercises, students can clarify any misconceptions, deepen their understanding, and learn alternative approaches to problemsolving.
Assessment methods
Continuous assessment  Partial exams  General exam  


x  x 
ATTENDING AND NOT ATTENDING STUDENTS
 Partial exams consist of two written exams, one at the midpoint of the course and one at the end. The final grade is calculated as the average of these two scores.
 General exam: written exam at the end of the course that contributes to the overall assessment.
Each written exam comprises five exercises with multiple bullet points covering all the presented material.
A total of 34 points will be assigned, with scores above 34 receiving the maximum grade. The exam evaluates the acquisition of basic knowledge and problemsolving abilities. The exercises vary in difficulty, with the first three emphasizing fundamental concepts and accounting for 25 out of 34 points, while the last two require more problemsolving and critical thinking, accounting for the remaining points.
Teaching materials
ATTENDING AND NOT ATTENDING STUDENTS
 Lecture notes of the course
 Introduction to linear algebra. Gilbert Strang
 Linear algebra and learning from data. Gilbert Strang
 Concrete Mathematics. Ronald L. Graham, Donald E. Knuth, Oren Patashnik