Learning computer science makes you a better developer, makes your apps better, and allows you to answer difficult engineering interview questions. In part 2 of the series, you’ll join Brian Holt — returning Frontend Masters instructor and developer at Microsoft — as he unpacks 4 semesters of computer science in 5 hours. You’ll dive deeper into computer science concepts such as traversing binary search trees, pathfinding, traversing graphs, generating a randomized maze, plus more ways to search and sort!

This course and others like it are available as part of our Frontend Masters video subscription.

Published: April 2, 2018

Table of Contents## Introduction

## Bloom Filters

## Tree Traversals

## Pathfinding

## Graphs

## Generating a Maze

## Tries

## Searching for an Element in an Array

## Heap Sort

## Radix Sort

## Conclusion

### 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. - https://btholt.github.io/four-semesters-of-cs-part-two/bloom-filters### 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. - https://codepen.io/btholt/pen/JMebQd?editors=0010### Bloom Filter Solution

Brian shows you how to code the adds and contains functions to implement a Bloom filter. - https://codepen.io/btholt/pen/LeXRwq?editors=0010

### Tree Traversals Introduction

Trees are an essential part of storing data as data structures optimized to be searchable. - https://btholt.github.io/four-semesters-of-cs-part-two/tree-traversals### 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. - https://codepen.io/btholt/pen/jYpwQV?editors=0010### Depth-first Traversal Solution

Brian codes the preorder, inorder and postorder traversal methods to process the tree data structure into a flat array - https://codepen.io/btholt/pen/rprwwm?editors=0010### 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. - https://codepen.io/btholt/pen/wpEgdb?editors=0010### Tree Queue Diagram

How does a tree becomes a queue? Brian explains using a diagram and walks through how queues work. - https://codepen.io/btholt/pen/WdgRrB?editors=0010

### Pathfinding & Demonstration

Pathfinding is a way to find the shortest path between two points. He shows different search algorithms using the pathfinder visualizer. - https://btholt.github.io/four-semesters-of-cs-part-two/pathfinding### Pathfinding Exercise

Brian sets up the exercise to find the amount of steps to find a path between two points. - https://codepen.io/btholt/pen/BJMxVM?editors=0010### Pathfinding Solution

Solution to the pathfinding challenge to crawl the graph and find the path between to points. - https://codepen.io/btholt/pen/LeqeoQ?editors=0010

### Graphs

Graphs are a central concept to computer science. Social networks use graphs famously. There are bi-directional and uni-directional graphs. - https://btholt.github.io/four-semesters-of-cs-part-two/graphs/### Graphs Exercise

Find the most common job in your social graph. - https://codepen.io/btholt/pen/KZYdKW?editors=0010### Graphs Solution

Coding a graph search in order to find the most common job title. - https://codepen.io/btholt/pen/qpvdJJ?editors=0010

### Generating a Maze

Visual demonstration of generating randomized mazes with various generation algorithms. - https://btholt.github.io/four-semesters-of-cs-part-two/maze-generation/### Generating a Maze Exercise

Generate a maze. - https://codepen.io/btholt/pen/YeWjNO?editors=0010### Generating a Maze Solution

Brian codes the solution to generating a maze. - https://codepen.io/btholt/pen/rJxOyK?editors=0010

### Tries

Trie is a type of tree data structure that makes it easy to search and retrieve data. - https://btholt.github.io/four-semesters-of-cs-part-two/tries/### Tries Exercise

Create a trie to autocomplete search the list of city names in the United States. - https://codepen.io/btholt/pen/RQobyV?editors=0010### Tries Solution

Create the trie structure to return the auto complete search results of city names. - https://codepen.io/btholt/pen/PQGVxR?editors=0010

### 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. - https://btholt.github.io/four-semesters-of-cs-part-two/search/### Searching for an Element in an Array Solution

Code out linear and binary searching on an array to find a particular element. - https://codepen.io/btholt/pen/ZrKzea?editors=0010

### 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. - https://btholt.github.io/four-semesters-of-cs-part-two/heap-sort/### Heap Sort Solution

Code out heapify which creates a heap data structure and can be dequeued until everything is sorted. - https://codepen.io/btholt/pen/eVWRNP?editors=0010

### Radix Sort

Radix sort allows you to sort without actually comparing two indexes of the array. It is a "non comparative" sort. - https://btholt.github.io/four-semesters-of-cs-part-two/radix-sort/### Radix Sort Solution

Code out the radix sort. - https://codepen.io/btholt/pen/VQbMGJ?editors=0010