Lecture

Efficient Algorithms and Median Search

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 various algorithms, including calculating the square of a large integer more efficiently than the product of two large integers, an ancient Egyptian recursive algorithm for integer multiplication, and a median search algorithm. It also discusses the efficiency of these algorithms compared to Karatsuba multiplication and their temporal complexity. The instructor presents exercises on these topics, such as testing algorithm correctness, linking with binary decomposition, and analyzing temporal complexity. Additionally, an in-place median search algorithm is proposed, involving subdivision of a list into three sublists. The lecture concludes with unconventional sorting algorithms and their temporal complexity analysis.

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Analysis of algorithms

Related concepts (28)

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.

In-place algorithm

In computer science, an in-place algorithm is an algorithm that operates directly on the input data structure without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called not-in-place or out-of-place. In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers.

Sorting

Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. ordering: arranging items in a sequence ordered by some criterion; categorizing: grouping items with similar properties. Ordering items is the combination of categorizing them based on equivalent order, and ordering the categories themselves. In , arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms have been developed to perform it.

External sorting

External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. External sorting algorithms generally fall into two types, distribution sorting, which resembles quicksort, and external merge sort, which resembles merge sort.

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes through the list are repeated until no swaps had to be performed during a pass, meaning that the list has become fully sorted. The algorithm, which is a comparison sort, is named for the way the larger elements "bubble" up to the top of the list.

Related lectures (64)

Algorithms in Computer Science: Search and Sort Techniques

Provides an overview of essential search and sort algorithms in computer science.

Recursion and Sorting Algorithms

Explores recursion, recursive algorithms, and sorting algorithms' efficiency for problem-solving and data organization.

Introduction to Algorithms: Course Overview and Basics

Introduces the CS-250 Algorithms course, covering its structure, objectives, and key topics in algorithmic problem-solving.

Parallel Sorting: Merge Sort Algorithm

Covers the implementation of a parallel merge sort algorithm in Scala, comparing its performance with quicksort.

Merge Sort: Sorting Algorithm