Lecture

Maximum Subarray Problem

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.

In course

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

Description

This lecture covers the Master method for solving recurrences, introducing the Master Theorem to analyze algorithms. It then delves into the Maximum Subarray Problem, explaining the optimal solution structure and the concept of finding the maximum subarray that crosses the midpoint. The lecture explores brute force approaches, the importance of considering all possibilities, and the solution to finding the maximum subarray. It concludes with a detailed explanation of the FIND-MAX-CROSSING-SUBARRAY algorithm. Real-world scenarios, such as stock trading, are used to illustrate the practical applications of the discussed concepts.

Instructors (3)

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Teaching & PhD PhD Students Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth Past EPFL PhD Students Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail Past EPFL PhD Students as codirector Paritosh Garg Courses Algorithms II CS-450 The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing alg

Ola Nils Anders Svensson

Official source

Related concepts (32)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

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.

Stock trader

A stock trader or equity trader or share trader, also called a stock investor, is a person or company involved in trading equity securities and attempting to profit from the purchase and sale of those securities. Stock traders may be an investor, agent, hedger, arbitrageur, speculator, or stockbroker. Such equity trading in large publicly traded companies may be through a stock exchange. Stock shares in smaller public companies may be bought and sold in over-the-counter (OTC) markets or in some instances in equity crowdfunding platforms.

Stock exchange

A stock exchange, securities exchange, or bourse is an exchange where stockbrokers and traders can buy and sell securities, such as shares of stock, bonds and other financial instruments. Stock exchanges may also provide facilities for the issue and redemption of such securities and instruments and capital events including the payment of income and dividends. Securities traded on a stock exchange include stock issued by listed companies, unit trusts, derivatives, pooled investment products and bonds.

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.

Related lectures (64)

Solving Parity Games in Practice

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

Dynamic Programming: Optimal Decision Making

Explores dynamic programming for optimizing decision-making processes over time, using real-world examples like oil extraction and stock trading.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Matrix Multiplication and Divide-and-Conquer Techniques

Discusses matrix multiplication using divide-and-conquer techniques and introduces Strassen's algorithm for improved efficiency.

Algorithms in Computer Science: Search and Sort Techniques