**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Algorithms & Growth of Functions

Description

This lecture covers the optimization algorithms, including Cashier's algorithm and the Gale-Shapley algorithm for stable matching. It also explains the concept of Big-O notation to analyze algorithm efficiency.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Related concepts (276)

Optimal control

Optimal control theory is a branch of mathematical optimization that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and operations research. For example, the dynamical system might be a spacecraft with controls corresponding to rocket thrusters, and the objective might be to reach the moon with minimum fuel expenditure.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Trigonometric functions

In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all sciences that are related to geometry, such as navigation, solid mechanics, celestial mechanics, geodesy, and many others. They are among the simplest periodic functions, and as such are also widely used for studying periodic phenomena through Fourier analysis.

Hyperbolic functions

In mathematics, hyperbolic functions are analogues of the ordinary trigonometric functions, but defined using the hyperbola rather than the circle. Just as the points (cos t, sin t) form a circle with a unit radius, the points (cosh t, sinh t) form the right half of the unit hyperbola. Also, similarly to how the derivatives of sin(t) and cos(t) are cos(t) and –sin(t) respectively, the derivatives of sinh(t) and cosh(t) are cosh(t) and +sinh(t) respectively. Hyperbolic functions occur in the calculations of angles and distances in hyperbolic geometry.

Dijkstra's algorithm

Dijkstra's algorithm (ˈdaɪkstrəz ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Related lectures (1,000)

Algorithmic Complexity: Big-O NotationCS-101: Advanced information, computation, communication I

Introduces Big-O notation for analyzing algorithm efficiency, covering logic, structures, and growth functions.

Proofs and Logic: Introduction

Introduces logic, proofs, sets, functions, and algorithms in mathematics and computer science.

Counting Principles: Sequences and FunctionsCS-101: Advanced information, computation, communication I

Covers counting principles, sequences, functions, and number representations in mathematics and computer science.

Complexity & Induction: Algorithms & ProofsCS-101: Advanced information, computation, communication I

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Complexity & Induction: Algorithms & ProofsCS-101: Advanced information, computation, communication I

Explores worst-case complexity, mathematical induction, and algorithms like binary search and insertion sort.