Lecture

Median Search Algorithm

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the median search algorithm, which involves finding the median of a list by searching for a specific number x. The algorithm also includes finding the smallest element in a list by precisely searching for x. Different strategies are discussed, such as choosing x based on the position in the list and repeating the search process. The lecture delves into the Hoare algorithm, which selects a number randomly in the list and creates three sub-lists based on this number. The complexity of the algorithm is analyzed, considering different scenarios and probabilities.

Official source

Related concepts (32)

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

Selection algorithm

In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Related lectures (60)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Linear Algebra: Efficiency and Complexity

Explores constraints, efficiency, and complexity in linear algebra, emphasizing convexity and worst-case complexity in algorithm analysis.

Improved Algorithm: Three-Color Parity Games

Introduces an improved algorithm for three-color parity games, focusing on progress measures, acceleration, and practical speed-up.

Generator of a Group

Explores checking a generator of a group, the Diffie-Hellman key exchange, and cryptographic algorithms.

Distinct Elements: Count and Hash Functions