In the field of computer science, a graph is an abstract data type that is widely used to represent connections and relationships. This post gives an overview about a selection of definitions, terms, and algorithms, which are related to graphs. The content was put together during preparation for a theoretical computer science test at Cooperative State University Baden-Württemberg and is mostly taken from either Wikipedia or lecture notes. Continue reading Graph Theory Overview

# Tag: Math

## Least Squares Derivation

The least squares optimization problem searches for a vector, that minimizes the euclidean norm in the following statement as much as possible: $$x_\text{opt}=\arg\min_x\frac{1}{2}\left\lVert Ax-y\right\rVert^2_2\,.$$This article explains how $x_\text{opt}=(A^{\text{T}}A)^{-1}A^{\text{T}}y$, the solution to the problem, can be derived and how it can be used for regression problems. Continue reading Least Squares Derivation

## Cubic Spline Interpolation

Cubic spline interpolation is a mathematical method commonly used to construct new points within the boundaries of a set of known points. These new points are function values of an interpolation function (referred to as *spline*), which itself consists of multiple cubic piecewise polynomials. This article explains how the computation works mathematically.

After an introduction, it defines the properties of a cubic spline, then it lists different boundary conditions (including visualizations), and provides a sample calculation. Furthermore, it acts as a reference for the mathematical background of the cubic spline interpolation tool on tools.timodenk.com which is introduced at the end of the article. Continue reading Cubic Spline Interpolation

## Guess Solutions of Polynomials

For a given polynomial of $n$th degree

$$P_n(x)=\sum_{i=0}^n a_ix^i = a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0$$

you can guess rational solutions $x$ for the corresponding problem $P_n(x)=0$ by applying the following two rules:

- $$x=\frac{p}{q}\text{, with } p \in \mathbb{Z} \land q \in \mathbb{N}\land p\mid a_0 \land q\mid a_n$$
- $$\lvert x\rvert\le2\cdot \max\left\lbrace \sqrt[k]{\frac{\lvert a_{n-k}\rvert}{\lvert a_n\rvert}}, k=1, …, n\right\rbrace$$

## Trigonometric Functions Formulary

This formulary has been created during the online onboarding process at Baden-Wuerttemberg Cooperative State University (DHBW). It is suitable for the related online tests and *might* be helpful for other people, seeking for formulas in this field of mathematics.

##### Basics

$$\begin{array}{l} \tan x = \frac{{\sin x}}{{\cos x}}\\ \cot x = {\tan ^{ – 1}}x = \frac{{\cos x}}{{\sin x}} \end{array}$$ Continue reading Trigonometric Functions Formulary