Advanced Data Structures and Algorithms in Python

The video presents an algorithm using rolling hashes, for optimally determining the minimum number of characters we need, to append to a string, in order to turn it into a palindrome.

   •  Recap palindromes and briefly explain hashes

   •  Understand the math behind rolling hashes and the solution

   •  Implement the solution and discuss potential shortcomings

This video shows how we can draw on ideas from video 1.5 in order to efficiently count how many subarrays have a given sum.

This video combines the deque data structure introduced in video 1.4 with the binary search algorithm in order to solve a problem that asks to find the longest subarray with a tricky property.

In this video, we provide a very quick, “crash course” like tutorial on Manacher’s algorithm, with a focus on intuitively understanding the logic behind a rather difficult algorithm, to wrap one’s mind around.

   •  Define the basics required to understand Manacher’s algorithm

   •  Go over an example and arrive at some formulas

   •  Work an example by hand, and implement the algorithm

This video presents four implementations of the Sieve of Eratosthenes, each one improving the algorithm’s efficiency. The accompanying code also provides an example of how Python functions can be timed, in order to gauge its performance.

   •  Understand the idea behind the Sieve algorithm

   •  Understand two optimizations, using standard Python

   •  Understand a very powerful optimization using NumPy

This video extends the classical towers of the Hanoi puzzle, which is usually presented with only 3 pegs, by introducing a second auxiliary peg. A recursive solution similar to the recursive solution for the 3-peg problem is presented.

   •  Recap the problem and its 3-peg solution

   •  Explain the rationale behind the solutions

   •  Implement the 4-peg solution

This video shows how we can use mutually recursive functions, in order to evaluate simple arithmetic expressions, that involve additions, subtractions, multiplications, divisions, and parentheses.

   •  Understand what idea, the solution is based on

   •  Understand what a recursive descent parser is

   •  Implement the discussed solution

The video discusses some mathematical ideas, that allow us to efficiently compute a given term of a recursive function.

   •  Understand the problem requirements

   •  Understand the Fibonacci example

   •  Understand a more complex example and why matrix exponentiation helps

In this video, we will efficiently compute a sum of matrices using mathematical manipulations and ideas, from the exponentiation by squaring algorithm.

   •  Understand the problem and the mathematical manipulations required

   •  Understand the two possible recursive solutions

   •  Implement the optimal recursive solution

This video presents a recursive approach for a problem that asks us to permute the elements of an array, such that they are in a certain order. The necessary framework of thinking and common pitfalls is discussed. This is also a possible interview problem.

   •  Understand the problem with examples

   •  Understand a possible approach and why it fails

   •  Understand the correct approach and code it

This video introduces some of our terminologies and interpretation of existing theory, and contrasts it with alternatives used by other authors.

   •  Understand some common misconceptions

   •  Understand our own assumptions

   •  Understand how these assumptions will impact future videos

The video presents a classical DP problem that involves computing a minimum sum path in a matrix. We revisit the solution and implement it, along with an important practical optimization.

   •  Understand the problem and the recurrence relation

   •  Understand the memory optimization, which is an important shortcoming

   •  Implement the discussed solutions

In this video, we relax some of the restrictions that we had in the previous problem, which leads to a harder to solve problem. It also requires one more dimension in the DP solution.

   •  Understand the relaxed restrictions and why this problem is harder

   •  Understand the need for an extra dimension in the DP recurrence

   •  Implement the DP solution for this problem

This video shows how DP can be used for counting problems as well. We present a counting problem, a naïve DP recursion, and then we shall optimize the recursion by getting rid of an unnecessary dimension.

   •  Derive the naïve DP recursion

   •  Derive the optimal DP recursion from the initial one

   •  Implement the optimal algorithm

The video presents another counting problem, which is solved in two ways. The second way is more efficient, but it requires knowledge from section 6, to be fully implementable. We present the main idea here and we will return to it in that section.

   •  Derive the first recurrence relation

   •  Derive more efficient recurrence and understand its pros and cons

   •  Implement the second algorithm

This video introduces a new Dynamic Programing class of algorithms, with a counting problem that can also be solved with elements from the previous section, but less efficiently.

   •  Understand the problem and its naïve DP solution

   •  Understand the new DP approach, its advantages, and possible shortcomings

   •  Implement the new approach for the first time

In this video, we introduce the RMQ problem: How to efficiently answer multiple range minimum queries on a given array. We will also describe a precomputation strategy using DP.

   •  Understand the problem and its naïve solutions

   •  Understand the DP approach and use it to answer queries

   •  Implement the solution

The video revisits the problem from section 4, video 3, but changes the setting a bit. The same kind of solution as in the previous two videos is used, but the DP array definition is also a bit more complex here.

   •  Understand the pros and cons of the new approach

   •  Understand the DP definition and computation

   •  Implement the solution

In this video, we discuss a more classical problem: Counting binary search trees with n nodes. The DP solution is explained in detail and a related theory is mentioned: The Catalan numbers.

   •  Understand the problem and the terminology

   •  Understand the DP solution derivation

   •  Implement the solution and discuss the implementation

This video covers the dynamic programming approach for the travelling salesman problem (TSP). We explain and implement the solution, focusing on both the theoretical aspects, as well as, the details necessary for a proper implementation.

   •  Understand the problem requirements

   •  Understand the DP solution and derivation

   •  Implement the DP solution and understand its technical details

In this video, we revisit the RMQ problem, which we complicate a bit, by allowing updates that can change the value at a given index. We introduce segment trees that allow us to both answer queries, and execute updates efficiently.

   •  Understand the new problem requirements

   •  Understand the necessary segment trees theory and operations

   •  Implement the segment tree solution for the problem

This video continues exploring the application of segment trees for the RMQ problem. We further complicate the problem: The update operation now affects an entire subarray, not just a single element.

   •  Understand the new problem settings and the previous solution’s limitations

   •  Understand how lazy updates can be handled

   •  Implement the changes required for handling lazy updates

In this video, we introduce another data structure suitable for various queries and updates problems: Binary Indexed Trees (BITs). We briefly discuss their advantages and disadvantages and solve an example problem.

   •  Understand the new problem settings and some of the advantages of BIT

   •  Understand the internals of the BIT data structure

   •  Implement BIT for the given problem

This video presents an extension of BITs, that allows it to answer min/max queries as well.

   •  Understand the necessary extension

   •  Understand the advantages and disadvantages of this approach

   •  Implement a binary indexed tree for the RMQ problem

In this video, we cover an efficient and easy to implement Binary Search Tree (BST): The Treap. We apply it on a simple problem and go over its implementation details.

   •  Understand the shortcomings of the classical BST

   •  Understand Treap and its rotations

   •  Implement a Treap for a simple problem

In this video, we discuss some solutions for the Lowest Common Ancestor (LCA) problem and implement one of them, the one using the Euler tour and segment trees for RMQ.

   •  Understand the LCA problem

   •  Understand Euler tours and how they apply to LCA

   •  Implement the discussed solution

In this video, we discuss a lesser known shortest path problem, the shortest path and back, or the shortest round trip, that does not visit the same edge twice. We present the algorithm with examples and then implement it.

   •  Understand the problem setting and why greedy fails

   •  Understand the correct algorithms

   •  Implement the algorithm step-by-step