**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# Counting: Structures and Algorithms

Description

This lecture covers the fundamental principles of counting, including permutations, combinations, and their applications in algorithms. It explores the logic behind proofs, structures, and the scalability of solutions. The lecture also delves into probabilities, speed analysis of algorithms, and practical counting problems.

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 (269)

Probability

Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin.

Gaussian integer

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or Gaussian integers share many properties with integers: they form a Euclidean domain, and have thus a Euclidean division and a Euclidean algorithm; this implies unique factorization and many related properties. However, Gaussian integers do not have a total ordering that respects arithmetic.

Combination

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members.

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory.

Algebraic integer

In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients are integers. The set of all algebraic integers A is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers. The ring of integers of a number field K, denoted by OK, is the intersection of K and A: it can also be characterised as the maximal order of the field K.

Related lectures (1,000)

Counting Principles: Permutations & CombinationsCS-101: Advanced information, computation, communication I

Explores the basics of counting principles, including permutations, combinations, and rules for calculating possible outcomes.

Advanced Counting & ProbabilitiesCS-101: Advanced information, computation, communication I

Covers advanced counting techniques, probabilities, and their applications in computer science.

Advanced Counting: Combinatorial ProofsCS-101: Advanced information, computation, communication I

Delves into advanced counting methods, combinatorial proofs, recurrence relations, and the Generalized Pigeonhole Principle.

Cartesian Product and Induction

Introduces Cartesian product and induction for proofs using integers and sets.

Derangements: Permutations and ProbabilitiesCS-101: Advanced information, computation, communication I

Covers advanced counting, probabilities, and information theory, including solving linear homogeneous recurrence relations and hat-check problems.