20872  MATHEMATICAL METHODS IN COMPUTER SCIENCE
Department of Decision Sciences
ELIA BRUE'
Synchronous Blended: Lezioni erogate in modalità sincrona in aula (max 1 ora per credito online sincrona)
Mission & Content Summary
MISSION
CONTENT SUMMARY
Topics in linear algebra:
1. Review of basic concepts:
 Real and Complex vector spaces, complexification
 Linear operators
 Eigenvalues, eigenfuctions
2. The Geometry of linear algebra:
 Quadratic and Bilinear forms, reduction to canonical form
 Real and Hermitian scalar product
 The group of isometries, orientation*
 Projections, orthogonal projections, variational characterization
 Pseudo Euclidean spaces and Lorentz transformations*
 Affine spaces, affine transformations
 Complements*: Projective spaces, projective transformations, Hyperbolic Geometry
3. Hermitian and Normal operators
 Hermitian operators
 Normal operators
 Spectral Theorem
 Variational characterization of eigenvalues, Rayleigh quotient, generalized Rayleigh quotient
 Complements*: Infinite dimensional spaces, compact operators, Laplacian and Poincarè inequality
4. Jordan’s Theory
 Principal vectors, cyclic subspaces
 Jordan normal form: Existence and uniqueness
 Applications: Analytic functions of matrices, CaleyHamilton identity, semigroups of operators
5. Matrix norms
 Norms on vector spaces
 Ring norms of operators, operator norms
 HilbertSchmidt scalar product, nuclear norm
 Spectral radius, Gelfand formula, variational characterization of the spectral radius*
 Applications: Singular values, variational characterization, EckartYoung, the closest rank kmatrix
 Other applications*: Least square method, pseudoinverse
6. Multilinear Algebra
 Multilinear forms
 Exterior product, exterior algebra
 Determinant, volume
 Crossproduct in R^3, applications, and relations with projections
 Complements*: differential forms, nonlinear volume transformation, Plucker coordinates
Topics in discrete mathematics:
1. Review of basic concepts
 Set theory
 Functions and relations
 Counting methods
 Countable, uncountable sets
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 multilinear operators.
 Understand the application of generating functions and asymptotic arguments in combinatorics.
 Acquire a basic understanding of graph spectral theory.
APPLYING KNOWLEDGE AND UNDERSTANDING
 Perform diagonalization and reduction to normal Jordan form of matrices, both real and complex, and utilize this process to compute 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 generating functions and recurrence relations.
 Determine the asymptotic growth in recurrence relations and combinatorial problems.
Teaching methods
 Facetoface lectures
 Exercises (exercises, database, software etc.)
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