# The Last Algorithms Course You'll Want (Part 2)

Learning Paths:

Topics:

Table of Contents

## Introduction

## Binary Search Trees

### Binary Search Tree Overview

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.### Traversals

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.### Deletions & Insertions

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

### Balance Factor

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.### AVL Complexity

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.### Red-Black Trees

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

### M-Way Tree Structure

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.### B-Trees

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.### B-Tree Insertions

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.### B-Tree Leaf Deletion

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.### B-Tree Internal Deletion

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

### Graphs Overview

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.### Adjacency Lists & Matrices

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.### Breadth-First Search

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.### Depth-First Search

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.### Spanning Trees & Prim's Algorithm

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.### Priority Queues

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.### Kruskal Algorithm

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.### Ford-Fulkerson: Max Flow

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.### Ford-Fulkerson: Min Cut

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

### Factorials & Fibonacci

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.### Max Subarray

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.### Coin Change Problem

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.### Bloom Filter

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.