Four Semesters of Computer Science in 5 Hours, Part 2
Table of Contents
IntroductionBrian Holt introduces the course, his background, and why computer science knowledge is important. Computer science will make you a better developer, make your apps better and allow you to pass difficult interview questions.
Bloom Filters SetupBrian introduces bloom filters and how they give you a very fast way to make sure something isn't in a set.
Bloom Filters DiagramedUsing arrays and hashing functions, Brian diagrams how the bloom filter works internally to quickly identify if something isn't in a set.
Bloom Filter CaveatsYou 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 ExplainedHow a string gets transformed from a string to a number which corresponds to the index in an array.
Bloom Filters ExerciseSetup 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 SolutionBrian shows you how to code the adds and contains functions to implement a Bloom filter.
Tree Traversals IntroductionTrees are an essential part of storing data as data structures optimized to be searchable.
Depth-first TraversalDepth-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 ExerciseIn the exercise you'll write a function that takes in a tree array and processes the tree into a flat array.
Depth-first Traversal SolutionBrian codes the preorder, inorder and postorder traversal methods to process the tree data structure into a flat array
Breadth-first TraversalBreadth-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 ExerciseIn the exercise you'll code the breadth-first traversal method to process the tree data structure into a flat array.
Breadth-first Traversal SolutionBrian implements the recursive and iterative versions of breadth-first traversal.
Tree Queue DiagramHow does a tree becomes a queue? Brian explains using a diagram and walks through how queues work.
Pathfinding & DemonstrationPathfinding is a way to find the shortest path between two points. He shows different search algorithms using the pathfinder visualizer.
Pathfinding ExerciseBrian sets up the exercise to find the amount of steps to find a path between two points.
Pathfinding SolutionSolution to the pathfinding challenge to crawl the graph and find the path between to points.
GraphsGraphs are a central concept to computer science. Social networks use graphs famously. There are bi-directional and uni-directional graphs.
Graphs ExerciseFind the most common job in your social graph.
Graphs SolutionCoding a graph search in order to find the most common job title.
Generating a Maze
Generating a MazeVisual demonstration of generating randomized mazes with various generation algorithms.
Generating a Maze ExerciseGenerate a maze.
Generating a Maze SolutionBrian codes the solution to generating a maze.
TriesTrie is a type of tree data structure that makes it easy to search and retrieve data.
Tries ExerciseCreate a trie to autocomplete search the list of city names in the United States.
Tries SolutionCreate 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 ArrayLooking 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 SolutionCode out linear and binary searching on an array to find a particular element.
Heap SortHeap 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 SolutionCode out heapify which creates a heap data structure and can be dequeued until everything is sorted.
Radix SortRadix sort allows you to sort without actually comparing two indexes of the array. It is a "non comparative" sort.
Radix Sort SolutionCode out the radix sort.