This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Table of Contents
Introduction
Bloom Filters
Bloom Filters Setup
Brian introduces bloom filters and how they give you a very fast way to make sure something isn't in a set.
Bloom Filters Diagramed
Using arrays and hashing functions, Brian diagrams how the bloom filter works internally to quickly identify if something isn't in a set.
Bloom Filter Caveats
You can never remove anything from a Bloom Filter. You can't expand a Bloom Filter. Trade offs can be made with how many hashing functions you use.
Hashing Functions Explained
How a string gets transformed from a string to a number which corresponds to the index in an array.
Bloom Filters Exercise
Setup for the Bloom Filters exercise in CodePen and how to run the tests. In the exercise you'll implement the add and contains methods.
Bloom Filter Solution
Brian shows you how to code the adds and contains functions to implement a Bloom filter.
Tree Traversals
Tree Traversals Introduction
Trees are an essential part of storing data as data structures optimized to be searchable.
Depth-first Traversal
Depth-first traversal is a way to process the tree into a data structure. Brian shows different ways to process the tree data structure into an array.
Depth-first Traversal Exercise
In the exercise you'll write a function that takes in a tree array and processes the tree into a flat array.
Depth-first Traversal Solution
Brian codes the preorder, inorder and postorder traversal methods to process the tree data structure into a flat array
Breadth-first Traversal
Breadth-first is a way to traverse in order to stay closer to the root node vs going deep in the tree like depth-first does. With breadth-first, you use a queue to maintain the correct order to process the tree
Breadth-first Traversal Exercise
In the exercise you'll code the breadth-first traversal method to process the tree data structure into a flat array.
Breadth-first Traversal Solution
Brian implements the recursive and iterative versions of breadth-first traversal.
Tree Queue Diagram
How does a tree becomes a queue? Brian explains using a diagram and walks through how queues work.
Pathfinding
Pathfinding & Demonstration
Pathfinding is a way to find the shortest path between two points. He shows different search algorithms using the pathfinder visualizer.
Pathfinding Exercise
Brian sets up the exercise to find the amount of steps to find a path between two points.
Pathfinding Solution
Solution to the pathfinding challenge to crawl the graph and find the path between to points.
Graphs
Graphs
Graphs are a central concept to computer science. Social networks use graphs famously. There are bi-directional and uni-directional graphs.
Graphs Exercise
Find the most common job in your social graph.
Graphs Solution
Coding a graph search in order to find the most common job title.
Generating a Maze
Generating a Maze
Visual demonstration of generating randomized mazes with various generation algorithms.
Generating a Maze Exercise
Generate a maze.
Generating a Maze Solution
Brian codes the solution to generating a maze.
Tries
Tries
Trie is a type of tree data structure that makes it easy to search and retrieve data.
Tries Exercise
Create a trie to autocomplete search the list of city names in the United States.
Tries Solution
Create the trie structure to return the auto complete search results of city names.
Searching for an Element in an Array
Searching for an Element in an Array
Looking at a few different strategies for finding a particular element in an array using linear and binary strategies. In binary you are splitting the sorted array in half in order to not have to iterate through every element in the array.
Searching for an Element in an Array Solution
Code out linear and binary searching on an array to find a particular element.
Heap Sort
Heap Sort
Heap is a tree that you can represent as an array that comes with the guarantee of the first index of a max heap is the largest number.
Heap Sort Solution
Code out heapify which creates a heap data structure and can be dequeued until everything is sorted.
Radix Sort
Radix Sort
Radix sort allows you to sort without actually comparing two indexes of the array. It is a "non comparative" sort.
Radix Sort Solution
Code out the radix sort.
