ThePrimeagen
terminal
The Last Algorithms Course You'll Want (Part 2)
3 hours, 10 minutes CC
Course Description
Advance your algorithmic skills with an in-depth exploration of essential data structures and algorithms. Delve into binary and M-Way search trees, AVL and red-black trees, understanding their insertions, deletions, and balancing mechanisms. Master graph theory, from basic concepts to complex traversals like breadth-first and depth-first searches, and algorithms including Prim's and Kruskal's. Learn dynamic programming with real-world examples like factorial, Fibonacci, and the coin change problem. The course concludes with practical applications of Bloom Filters, offering insights into efficient data handling and optimization techniques.
This course and others like it are available as part of our Frontend Masters video subscription.
Preview
CloseCourse Details
Published: January 22, 2024
Learning Paths
Learn Straight from the Experts Who Shape the Modern Web
Your Path to Senior Developer and Beyond
- 200+ In-depth courses
- 18 Learning Paths
- Industry Leading Experts
- Live Interactive Workshops
Table of Contents
Introduction
Section Duration: 1 minute
ThePrimeagen introduces the new algorithms course and mentions that they will be using various algorithms and the ones they find the most fun. They also mention that a basic understanding of algorithms, including walking a tree and recursion, is expected from the students.
Binary Search Trees
Section Duration: 23 minutes
ThePrimeagen introduces the concept of binary trees and binary search trees. They explain the structure and properties of binary trees, including full binary trees and complete binary trees. They also demonstrate how to search for a value in a binary search tree and discuss the efficiency of binary search trees in terms of search time.
ThePrimeagen discusses the concept of traversals in binary trees and explains the three types of traversals: pre-order, in-order, and post-order. The instructor demonstrates how each traversal works by visually walking through a binary tree and explaining the steps taken to visit each node. They also provide insights on representing nodes in code and offer tips for translating the concepts into code.
ThePrimeagen discusses the three cases of deletion from a binary tree. They explain how to handle each case, including deleting a node with no children, deleting a node with one child, and deleting a node with two children. The instructor also introduces the concept of in-order successor and in-order predecessor and explains how they can be used in the deletion process.
AVL & Red-Black Trees
Section Duration: 26 minutes
ThePrimeagen explains the concept of AVL trees and their balancing algorithm. They discuss the history and origin of AVL trees, as well as the balance factor and rotation operations involved in maintaining balance in the tree. The instructor also demonstrates the process of inserting nodes and performing rotations to fix violations and achieve a balanced AVL tree.
ThePrimeagen discusses the more complicated case of inserting nodes into an AVL tree. They explain the process of performing rotations to maintain the balance of the tree and demonstrate how to handle specific scenarios. The instructor also mentions the benefits and use cases of AVL trees, as well as the time complexity of insertion and deletion operations.
ThePrimeagen briefly introduces the concept of red-black trees and mentions some of the rules associated with them. They explain that the root and nil nodes are always black, all nodes are either red or black, and there cannot be a red parent with a red child. The instructor also mentions that red-black trees maintain the properties of a binary search tree and that all paths in the tree have the same number of black nodes.
M-Way & B-Trees
Section Duration: 31 minutes
ThePrimeagen introduces the concept of M-Way search trees, which are a variation of binary trees that allow for more than two children per node. The instructor explains that M-Way search trees can hold a larger number of items without increasing the height of the tree significantly. They also mention that each node in an M-Way tree will have one more child than the number of items it holds. The instructor clarifies that the value of M determines the maximum number of children a node can have.
ThePrimeagen introduces the concept of B-trees and explains the rules of B-trees, including the order and minimum requirements for keys and children. They also clarify that B-trees grow upwards and that the root can have one key. The lesson concludes with a discussion on the division used to calculate the minimum key requirement.
ThePrimeagen explains the process of inserting elements into a B-tree. They demonstrate the insertion of various numbers and explain how the tree grows and maintains its properties. They also discuss the concept of splitting and promoting nodes when necessary. The lesson concludes with a brief mention of expanding the tree and dividing children.
ThePrimeagen explains the process of deleting keys in a tree data structure. They discuss different cases and demonstrate how to handle each case, including borrowing keys from siblings and merging nodes. The lesson also emphasizes the importance of maintaining the rules and requirements of the tree structure throughout the deletion process.
ThePrimeagen explains the process of deleting internal nodes in a B-tree. They discuss the three cases of deletion and demonstrate how to handle each case using the in-order predecessor or in-order successor rule. They also mention the possibility of merging nodes when necessary and emphasize the importance of testing when implementing B-trees.
Graphs
Section Duration: 1 hour, 12 minutes
ThePrimeagen introduces the concept of graphs and explains the terminology associated with them, such as vertices, edges, directed graphs, undirected graphs, and weights. They also mention the concept of connected components in a graph. The instructor uses visual aids and humor to engage the students and make the lesson more enjoyable.
ThePrimeagen explains how to represent a graph using an adjacency list and an adjacency matrix. They demonstrate how to map the vertices of the graph to positions in the list or matrix and show how to indicate the connections between the vertices. They also discuss the advantages and disadvantages of each representation method.
ThePrimeagen discusses the two types of traversals in a graph: breadth-first search and depth-first search. They explain the basic concepts of each traversal and demonstrate how they work using a graph example.
ThePrimeagen explains the concept of depth-first search (DFS) in graph traversal. They demonstrate how to perform a DFS using a recursive approach and explain the rules for visiting nodes in the correct order. The instructor also introduces the concept of topological sorting, which is a variation of DFS used to sort nodes in a directed graph.
ThePrimeagen discusses Prim's Algorithm by defining a spanning tree and its purpose in connecting all nodes in a graph. They then demonstrate how to use Prim's Algorithm to find the minimum spanning tree of a graph by selecting the smallest edges and adding them to the tree.
ThePrimeagen explains the concept of a heap and its application in a priority queue. They discuss the heap condition and how elements are stored in an array. The instructor also introduces the idea of a priority indexed queue (PIC) and explains how it can be used to optimize the runtime of an algorithm. They demonstrate how to use the PIC to implement Dijkstra's algorithm and achieve a runtime of E log V.
ThePrimeagen explains Kruskal's algorithm for finding the minimum spanning tree of a graph. They start by sorting the edges of the graph and then proceed to add the edges one by one, making sure not to create cycles. They also introduce the concept of union-find data structure and explain how it can be used to efficiently implement Kruskal's algorithm. Finally, they discuss the time complexity of Kruskal's algorithm and compare it to Prim's algorithm.
ThePrimeagen introduces the Ford-Fulkerson algorithm, also known as the max flow min cut algorithm. They explain that this algorithm is used to maximize the flow through a network or graph, and it involves finding a path from a source to a sink while maximizing the flow along that path.
ThePrimeagen explains the concept of maximum flow and minimum cut in graph theory. They demonstrate how to find the maximum flow in a graph by using the Ford-Fulkerson algorithm and augmenting paths. They also discuss the concept of minimum cut and how it can be used to separate the source and sink nodes in a graph.
Dynamic Programming
Section Duration: 29 minutes
ThePrimeagen introduces the concept of dynamic programming and explains that it involves using past results to compute future values. They provide examples of dynamic programming solutions for factorial and Fibonacci sequences, showing both recursive and iterative approaches. The instructor emphasizes the advantage of using dynamic programming to avoid redundant computations and improve efficiency.
ThePrimeagen introduces the concept of finding the maximum subarray within an array. They explain a naive solution that has a time complexity of O(n^3) and then propose a more efficient approach using dynamic programming. They walk through an example to demonstrate how to use previous values to compute forward values and emphasize the difficulty of solving dynamic programming problems.
ThePrimeagen introduces the concept of dynamic programming by solving the maximum coin change problem. They ask the audience to provide four values between one and ten, and then demonstrate how to calculate the different ways to make change for a given number using those coins. The instructor explains the process of using previous solutions to calculate future values and highlights the efficiency of dynamic programming compared to other approaches.
ThePrimeagen introduces the concept of a Bloom Filter, which is a fast way to determine if something is not in a set. They explain how a Bloom Filter works by using hash functions to mark elements in a set, and how it can provide a high probability of an element being in the set, but no false negatives. The instructor also discusses the practical applications of Bloom Filters, such as in caching and checking for malicious websites.
Wrapping Up
Section Duration: 5 minutes
ThePrimeagen wraps up the course by summarizing the topics covered, such as trees, graphs, analysis of algorithms, and useful algorithms like union find path compression and B-trees. They also answer some questions from the audience, including the difference between dynamic programming and recursion, the drawbacks of dynamic programming, and the best programming languages for implementing data structures.
Learn Straight from the Experts Who Shape the Modern Web
- In-depth Courses
- Industry Leading Experts
- Learning Paths
- Live Interactive Workshops