**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# Recursive Algorithms: Induction & Sorting

Description

This lecture covers the concepts of induction and recursion, focusing on structural induction to prove properties of recursively defined sets. It also delves into the recursive definition of strings, the time complexity of recursive algorithms, and the merge sort algorithm for sorting. The instructor explains the process of proving recursive algorithms correct and demonstrates the application of divide and conquer strategies in sorting algorithms like merge sort.

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

Related concepts (123)

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

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.

Empty set

In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other theories, its existence can be deduced. Many possible properties of sets are vacuously true for the empty set. Any set other than the empty set is called non-empty. In some textbooks and popularizations, the empty set is referred to as the "null set".

Finite set

In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. The number of elements of a finite set is a natural number (possibly zero) and is called the cardinality (or the cardinal number) of the set. A set that is not a finite set is called an infinite set.

Corecursion

In computer science, corecursion is a type of operation that is to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data.

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics.

Related lectures (602)

Recursive Algorithms: Induction & SortingCS-101: Advanced information, computation, communication I

Covers induction, recursion, sorting algorithms, and the merge sort complexity in computer science.

Logic and AlgorithmsCS-101: Advanced information, computation, communication I

Covers logic, mathematical reasoning, basic structures, and algorithms, exploring proofs, sets, functions, and recursion.

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.

Logic and Sets

Introduces logic, sets, and their operations, including subsets, Cartesian product, and set equivalence.