**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 in computer science, including proofs, structures, algorithms, counting, and probabilities. It also delves into structural induction, recursive algorithms, and the time complexity of recursive algorithms. The lecture further explores the recursive definition of strings, the length of strings, and examples of recursive theorems. Additionally, it discusses the process of proving recursive algorithms correct and introduces the divide and conquer strategy, focusing on the merge sort algorithm. The complexity of merge sort and the process of merging two sorted lists are also explained.

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

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.

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.

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

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".

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

Related lectures (669)

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

Explores induction, recursion, and sorting algorithms, including merge sort and the proof of correctness for recursive algorithms.

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.

Cantor's Diagonal ArgumentCS-101: Advanced information, computation, communication I

Explores Cantor's Diagonal Argument and the concept of uncountability through binary digit sequences.

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

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