ML Wiki
Machine Learning Wiki - A collection of ML concepts, algorithms, and resources.

YADS Admission Program

yandex

Program for admission to the Yandex School of Data Analysis (YADS)

Algebra

  1. Substitutions. Definition of a substitution, parity of substitutions. Product of substitutions, decomposition of substitutions into a product of transpositions and independent cycles.
  2. Complex Numbers. Geometric representation, algebraic and trigonometric forms, extraction of roots, roots of unity.
  3. Systems of Linear Equations. Rectangular matrices. Reduction of matrices and systems of linear equations to row echelon form. Gaussian elimination.
  4. Linear dependence and rank. Linear dependence of rows (columns). The fundamental lemma on linear dependence, basis and rank of a system of rows (columns). Rank of a matrix. Criterion for the consistency and determinacy of a system of linear equations in terms of matrix ranks. The fundamental system of solutions of a homogeneous system of linear equations.
  5. Determinant. Determinant of a square matrix, its basic properties. Criterion for the determinant being zero. Formula for expanding the determinant of a matrix along a row (column).
  6. Operations on matrices. Operations on matrices and their properties. Theorem on the rank of a product of two matrices. Determinant of a product of square matrices. Inverse matrix, its explicit form (formula), method of expression using elementary row transformations.
  7. Vector spaces; basis. Vector space, its basis and dimension. Coordinate transformations in a vector space. Subspaces as solution sets of systems of homogeneous linear equations. Relationship between the dimensions of the sum and intersection of two subspaces. Linear independence of subspaces. Basis and dimension of a direct sum of subspaces.
  8. Linear maps and linear operators. Linear maps, their representation in coordinates. Image and kernel of a linear map, relationship between their dimensions. Dual space and dual bases. Change of the matrix of a linear operator when changing to a different basis.
  9. Bilinear and quadratic forms. Bilinear forms, their representation in coordinates. Change of the matrix of a bilinear form when changing to a different basis. Orthogonal complement to a subspace with respect to a symmetric bilinear form. Relationship between symmetric bilinear and quadratic forms. Existence of an orthogonal basis for a symmetric bilinear form. Normal form of a real quadratic form. The law of inertia.
  10. Eigenvectors and eigenvalues. Eigenvectors and eigenvalues of a linear operator. Eigenspaces of a linear operator, their linear independence. Condition for diagonalizability of an operator.

Mathematical Analysis

  1. Limits and Continuity. Limits of sequences and functions. Continuous functions.
  2. Series. Numerical and functional series. Convergence tests (d’Alembert, Cauchy, integral, Leibniz). Absolutely and conditionally convergent series.
  3. Differentiation. Differentiation of functions. Application of derivatives for finding extrema of functions. Taylor’s formula.
  4. Integration. Definite and indefinite integrals. Methods of integration. Antiderivatives of various elementary functions.

Combinatorics

  1. Basic rules of combinatorics. Rule for counting combinatorial objects. Pigeonhole Principle. Examples.
  2. Sets. Euler diagrams, set operations. Inclusion-exclusion principle. Examples.
  3. Combinations. Partial Permutations, permutations and combinations. Binomial Theorem. Pascal’s Triangle. Combinations with repetition.

Probability Theory

  1. Basic concepts of probability theory. Definition of a probability space, simplest discrete cases (ordered and unordered samples), classical probability model. Random variable, distribution function.
  2. Conditional probabilities. Definition of conditional probability, Law of Total Probability, Bayes’ theorem.
  3. Expected value, variance, correlation. Definition of expected value, variance, covariance and correlation, their properties.
  4. Independence. Pairwise independence and mutual independence. (Chain and Sum Rules in Probability.)
  5. Main theorems of probability theory. Chebyshev’s Inequality. Laws of Large Numbers. Central Limit Theorem.
  6. Distributions. Standard discrete and continuous distributions, their expected values, variances and properties:

Programming, Algorithms, and Data Structures

(Proficiency in one of the major programming languages is assumed; C/C++ is preferred)

  1. Basic language constructs. Loops, conditionals, recursion.
  2. Analysis of algorithms. The notion of time and space complexity. Asymptotics, Big-O notation. Invariants, pre- and post-conditions. Proof of algorithm correctness.
  3. Basic data structures. Arrays, stacks, queues, linked lists. Comparison of time costs for different types of operations.
  4. Strings and operations on them. String representation. Computing length, concatenation, fast substring search.
  5. Sorting. The information-theoretic lower bound on sorting complexity. Insertion sort, bubble sort, quicksort, merge sort algorithms. Complexity analysis.
  6. Pointers. Pointers and dynamic memory management.
✏️ Edit on GitHub