Data Structures and Algorithms in JavaScript [2017, ENG]

Содержание

Table of Contents
Object Oriented JavaScript
Introduction
00:00:00 - 00:06:43
Introduction
Bianca Gandolfo begins her Data Structures & Algorithms course by sharing her background and how she developed this course. She will be using a cooking metaphor throughout the course because she believes learning these concepts involves understanding the "recipes", watching them in action, and getting time to try them out yourself.
Agenda and Scope
00:06:44 - 00:13:43
Agenda and Scope
Bianca quickly walks through the agenda and scope of this six-day course. The fundamentals introduced and practiced in the first day will be used throughout the rest of the course. This course is based on university-level computer science courses and covers the most common data structures and algorithms programmers use today.
How to Succeed
00:13:44 - 00:20:55
How to Succeed
Using a "fad diet" metaphor, Bianca explains what it takes to succeed in this course. She recommends pairing up with someone or a team of people to try the exercises and discuss the solutions. Ask questions and don't be afraid of failure.
Pseudoclassical JavaScript
00:20:56 - 00:34:42
Pseudoclassical JavaScript
JavaScript is often referred to as "pseudoclassical" because it's an object-oriented language but lacks a formal way of creating class constructors. While this changes in ES6, Bianca introduces this concept of pseudoclassical JavaScript and leads a discussion about why data needs structure.
Defining a Class
00:34:43 - 00:44:31
Defining a Class
Bianca presents her recipe for defining a class in JavaScript. She describes the constructor and properties as an object's "what it is" and "what it has". Methods on the object are "what it does".
Using a Class
00:44:32 - 00:46:22
Using a Class
Before moving into the first exercise, Bianca shares a few examples of how classes are used in JavaScript. She also talks about what parts of pseudoclassical JavaScript are typically required knowledge in job interviews.
Exercise: Creating a Constructor
00:46:23 - 00:46:51
Exercise: Creating a Constructor
In this exercise, you will create a unique constructor that creates a building of your choice. Your constructor will use the pseudoclassical JavaScript pattern.
Creating a Constructor Solution
00:46:52 - 00:50:56
Creating a Constructor Solution
Bianca walks through the solution to the Creating a Constructor exercise.
Stacks & Queues
Stacks
00:50:57 - 01:03:50
Stacks
The first data structure Bianca introduces is a stack. With each data structure, she will be drawing it out, pseudocoding it, then putting it to work with an API and any applicable algorithms. The stacks API follows a last-in-first-out model where the last item added to the stack is the first item removed.
Stacks Interface
01:03:51 - 01:10:12
Stacks Interface
The interface for a stack contains a constructor function for handling the storage along with push(), pop(), and size() methods for manipulating the stack. After introducing the interface, Bianca share an example of the methods defined in JavaScript.
Implementing a Stack
01:10:13 - 01:17:38
Implementing a Stack
Bianca implements each method of the Stack object. The constructor initializes the storage object. In this case, she's using a String for storing the stack data. She then implements the push() and pop() methods which add and remove items from the stack.
Queues
01:17:39 - 01:21:43
Queues
Queues are similar to a stack except for the order in which items are added. In the case of a queue, the first item in is the first item out. Rather than push() and pop() methods, a queue has an enqueue() method for adding items and a dequeue() method for removing items.
Exercise: Creating Stacks and Queues
01:21:44 - 01:23:57
Exercise: Creating Stacks and Queues
In this exercise, you will implement both the Stack and Queue data structures. Each data structure is stubbed out and commented with the instructions for what you need to complete. - https://github.com/kuychaco/algoClass/blob/master/data-structures/stack.js, https://github.com/kuychaco/algoClass/blob/master/data-structures/queue.js
Creating Stacks and Queues Solution
01:23:58 - 01:36:19
Creating Stacks and Queues Solution
Bianca walks through the solution to the Creating Stacks and Queues exercise. he code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/stack.js, https://github.com/kuychaco/algoClass/blob/solutions/data-structures/queue.js
Recursion
Why Recursion?
01:36:20 - 01:40:07
Why Recursion?
Recursion occurs when a function calls itself. Bianca makes a case for recursion and talks about why understanding the core concepts will make it easier to understand other use cases like recursive algorithms or recursive data structures.
Tracing Recursive Execution
01:40:08 - 01:50:48
Tracing Recursive Execution
Bianca explores a recursive function by tracing through each call. The callMe() function continues to call itself until the tracker variable satisfies the base case. If the function's base case is never reached, an infinite loop may occur.
Template for a Recursive Function
01:50:49 - 01:54:02
Template for a Recursive Function
Bianca summarizes her recursion introduction by sharing the recipe for a recursive function. You identify the base case, identify the recursive case, return when appropriate, and write procedures that bring you closer to the base case.
Looping
01:54:03 - 02:03:53
Looping
In JavaScript, loops can be created with statements like for() and while(). A loop can also be created with a recursive function. Bianca walks through an example of loop implementing through the use of recursion.
Factorial with Loop
02:03:54 - 02:08:33
Factorial with Loop
Using factorials as an example, Bianca first looks at how the factorial algorithm would be implemented with a for() loop. The loop starts at the number 2 and continues to multiply the numbers together until the desired factorial is reached. She will use this example as a baseline for implementing the recursive example.
Factorial with Recursion
02:08:34 - 02:19:52
Factorial with Recursion
Bianca now looks at the implementation of the factorial algorithm with recursion. The recursive computeFactorial(num) function continues to call itself while decrementing the num parameter. Once num is equal to one, the function returns and the results of all the calls on the stack are multiplied together.
Exercise: Recursion Interview Questions
02:19:53 - 02:23:10
Exercise: Recursion Interview Questions
In this exercise, you will implement a common recursion questions that are often asked during job interviews. - https://github.com/kuychaco/algoClass/blob/master/recursion/recursionIntro.js
Recursive Reverse Solution
02:23:11 - 02:33:53
Recursive Reverse Solution
Bianca begins walking through the solution to the Recursion Interview Questions exercise. The first question she answers is how to implement a recursiveReverse() function. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/recursion/recursionIntro.js
Recursive Multiplier Solution
02:33:54 - 02:49:29
Recursive Multiplier Solution
Bianca continues her demonstration of the solution to the Recursion Interview Questions exercise by implementing the recursiveMultiplier() function. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/recursion/recursionIntro.js
MinStack Solution
02:49:30 - 03:04:09
MinStack Solution
Now that recursion has been covered, Bianca jumps back to the Stacks & Queues exercise to demonstrate the solution to the MinStack object which contains a min() method that returns the minimum element in the stack. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/stack.js
Implementing a Queue with Two Stacks Solution
03:04:10 - 03:14:13
Implementing a Queue with Two Stacks Solution
Bianca continues working through the exercises left over from the Stacks & Queues topic. In this video, she looks at the solution to implementing a queue by using two stacks. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/queue.js
Time Complexity
Space vs. Time Complexity
03:14:14 - 03:21:13
Space vs. Time Complexity
Time complexity helps developers understand an algorithm's performance. Time complexity can be influenced by how many comparisons are made or how many swaps are necessary to complete a task. Bianca spends a few minutes introducing time complexity and discussing how it compares to space complexity.
Calculating Time Complexity
03:21:14 - 03:32:32
Calculating Time Complexity
Bianca uses a chart to plot the number of comparisons needed to complete various tasks. For example, how many comparisons would it take to determine the minimum value and the maximum value within a set of data. She uses these examples as a basis for understanding how time complexity is calculated.
Understanding Big-O
03:32:33 - 03:45:37
Understanding Big-O
In computer science terms, time complexity is represented as "Big-O". The Big-O notation describes the performance of various algorithms as constant, logarithmic, linear, quadratic, or exponential. Bianca plots these Big-O calculations on a graph to illustrate their effect on space and time complexity.
Calculating Big-O of JS Operations
03:45:38 - 03:52:56
Calculating Big-O of JS Operations
Bianca calculates the Big-O values for a few common JavaScript operations. She explores push(), pop(), incrementing a value, using a for() loop, and unshift(). With each operation, Bianca looks at how the Big-O value is calculated and its effect with larger data sets.
Calculating Big-O of Loops
03:52:57 - 04:05:47
Calculating Big-O of Loops
Calculating the Big-O value of a group of operations can be more complex. Especially if the group contains nested loops or multiple statements. Bianca walks through how to calculated the Big-O value for two nested for() loops which increment values.
Exercise: Calculating Time Complexity
04:05:48 - 04:06:21
Exercise: Calculating Time Complexity
In this exercise, you will calculate the Time Complexity for various JavaScript code snippets. The code snippets for his exercise are located in Bianca's slides. - http://slides.com/bgando/sorting#/0/20
Calculating Time Complexity Solution
04:06:22 - 04:09:40
Calculating Time Complexity Solution
Bianca walks through the solution to the Calculating Time Complexity exercise.
Elementary Sorting
Bubble Sort
04:09:41 - 04:23:39
Bubble Sort
Bianca begins the sorting unit by demonstrating the Bubble Sort algorithm. Bubble Sort is a comparison sort which repeatedly swaps adjacent elements that are out of order. To help illustrate the process. Bianca shares a Bubble Sort demonstration video with Hungarian dancers. She also briefly pseudocodes the Bubble Sort algorithm. - https://www.youtube.com/watch?v=lyZQPjUT5B4
Stability and Adaptability
04:23:40 - 04:27:39
Stability and Adaptability
A sorting algorithm can be described as stable if it preserves the order of equal items. The algorithm is adaptive if it becomes more efficient when the inputted data is already nearly sorted. Bianca spends a few minutes demonstrating stability and adaptability before moving on to the next sorting algorithm.
Selection & Insertion Sort
04:27:40 - 04:38:02
Selection & Insertion Sort
Bianca introduces Selection Sort and Insertion Sort. Selection Sort selects the smallest element in an array and pushes it into a new array. An in-place Selection Sort selects the largest element in the array and swaps it to the end of the array. Insertion Sort is similar to selection sort except it always selects the first element of the array and inserts it into the correct position in a new array.
Exercise: Bubble, Insertion, and Selection Sort
04:38:03 - 04:39:32
Exercise: Bubble, Insertion, and Selection Sort
In this exercise, you will implement the elementary sorting algorithms covered in this section. These algorithms include Bubble Sort, Insertion Sort, and Selection Sort. - https://github.com/kuychaco/algoClass/tree/master/sorting-algorithms
Bubble, Insertion, and Selection Sort Solution
04:39:33 - 04:42:31
Bubble, Insertion, and Selection Sort Solution
Bianca walks through the solution to Bubble, Insertion, and Selection Sort exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/tree/solutions/sorting-algorithms
Sorting Algorithms
Merge Sort
04:42:32 - 04:48:43
Merge Sort
The first complex sorting algorithm Bianca covers is Merge Sort. This algorithm takes a "divide and conquer" approach to sorting. After the data is separated into smaller lists, the merge step combines two sorted lists into one sorted list.
Pseudocoding the Merge Routine
04:48:44 - 05:00:21
Pseudocoding the Merge Routine
To further illustrate the merge routine, Bianca pseudocodes the merge() method. This method takes a left list and a right list and merges to the two lists together. Since the left and right list are already sorted, the merge() method is able to insert the elements in the correct order so merged list is also sorted.
Pseudocoding Merge Sort
05:00:22 - 05:12:03
Pseudocoding Merge Sort
Bianca pseudocodes the full Merge Sort algorithm. The first step is to divide the input array into subarrays. The second step is to repeatedly merge the subarrays and sort them as they are merged. This process continues until all subarrays are merged into a single sorted array.
Time Complexity for Merge Sort
05:12:04 - 05:22:59
Time Complexity for Merge Sort
While looking at the pseudocode for the Merge Sort algorithm, Bianca breaks down each operation and calculates the time complexity. She also spends a few minutes looking at the full code solution for the Merge Sort algorithm to explain the recursive calls to the mergeSort() method.
Quick Sort Overview
05:23:00 - 05:26:53
Quick Sort Overview
The Quick Sort algorithm is similar to Merge Sort except that the bulk of the work is done while dividing the data. The Quick Sort algorithm selects a partition or pivot point. It then rearranges all the elements that are greater than the pivot to the right and all the elements less than the pivot to the left.
Understanding the Quick Sort Partition
05:26:54 - 05:39:12
Understanding the Quick Sort Partition
While there are many ways to partition elements in the Quick Sort algorithm, Bianca gives a brief overview of the process. She also defines the terms "pivot point" and "pivot location" and describes the role they play as the Quick Sort algorithm sorts an array.
Pseudocoding Quick Sort Part 1
05:39:13 - 05:45:48
Pseudocoding Quick Sort Part 1
Bianca begins a lengthy pseudocode demonstration of the Quick Sort algorithm. In this first part, Bianca looks at how the pivot is initially selected and the pivot location is tracked as the algorithm loops through the array.
Pseudocoding Quick Sort Part 2
05:45:49 - 05:55:38
Pseudocoding Quick Sort Part 2
Bianca completes her pseudocode demonstration of the Merge Sort algorithm. In this part, she looks at swapping an element that is greater than the pivot.
Reviewing the Pseudocode
05:55:39 - 06:01:22
Reviewing the Pseudocode
With the Quick Sort pseudocode complete, Bianca takes a few minutes to review the entire algorithm. She asks the audience to guide her through the pseudocode and apply the algorithm to a small array.
Debugging the Quick Sort Algorithm
06:01:23 - 06:14:08
Debugging the Quick Sort Algorithm
As a bonus exercise, Bianca re-codes the Quick Sort partition() method with the group. As before, the partition method() is passed the array as well as first and last values. The first value is the pivot location. The last value is the pivot point. The method then proceeds to loop through the array to compare the elements to the pivot and make any necessary swaps.
Quick Sort Review Part 1
06:14:09 - 06:25:54
Quick Sort Review Part 1
Bianca combines the quicksort() method with the partition() method to perform a full code review of the entire Quick Sort algorithm. She continues tracing through the code and documenting each swap as she fields questions from the audience.
Quick Sort Review Part 2
06:25:55 - 06:37:47
Quick Sort Review Part 2
Bianca wraps up her coverage of the Quick Sort algorithm by finishing her full code review the partition() and quicksort() methods. She documents each step as an array is sorted.
Trees & Searching
Trees
06:37:48 - 06:41:38
Trees
Bianca introduces Trees and takes a look a what methods are required in the Tree interface. The constructor creates the storage and root properties. The Tree interface would contain methods like insert(), search(), min(), max(), and remove().
Linked Lists
06:41:39 - 06:50:13
Linked Lists
A Linked List is a tree structure with only one child per node. Each child in the list contains a node value and a link to the next item in the list. To illustrate how Linked Lists work, Bianca shares a couple diagrams of the adding and removing of nodes.
Pseudocoding a Linked List
06:50:14 - 07:02:09
Pseudocoding a Linked List
Bianca pseudocodes a Linked List. She creates a Node constructor for initializing Nodes. The Linked List constructor would instantiate Nodes for the head and tail. The Linked List object would also have methods for adding to the tail and removing nodes.
Exercise: Implement a Linked List
07:02:10 - 07:02:40
Exercise: Implement a Linked List
In this exercise, you will implement a Linked List. The code for this exercise is in the exercises Github repository. Comments are placed in the code under each method that needs to be implemented. - https://github.com/kuychaco/algoClass/blob/master/data-structures/linkedList.js
Implement a Linked List Solution
07:02:41 - 07:18:47
Implement a Linked List Solution
Bianca walks through the solution to the Implement a Linked List exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/linkedList.js
Implementing a Tree
07:18:48 - 07:24:12
Implementing a Tree
Now that Bianca has looked at the Linked List implementation, she spends a few minutes looking at how a Tree is implemented. The main difference between these two structures is a Tree cannot have any circular references. There is a root node in the tree and each node has a list of its children.
Reviewing Core Concepts
Review: Time Complexity
07:24:13 - 07:32:03
Review: Time Complexity
Bianca begins a unit which reviews all the topics she has covered up to this point. In this first video, she reviews Time Complexity. She looks at the Big-O calculations of common operations and reviews how to estimate the Big-O for any algorithm.
Review: Elementary Sorting
07:32:04 - 07:39:47
Review: Elementary Sorting
Bianca reviews the elementary sorting concepts she covered earlier in the course. She talks about stability vs. adaptability. She also reviews Bubble Sort, Insertion Sort, and Selection Sort.
Review: Recursion
07:39:48 - 07:44:05
Review: Recursion
Recursion is a common technique used throughout many sorting and searching algorithms. Bianca reviews some of the recursion topics covered earlier in the course.
Review: Merge Sort
07:44:06 - 07:51:48
Review: Merge Sort
Bianca reviews the Merge Sort algorithm. She reminds the group of the "divide and conquer" approach to sorting and reviews the merge routine.
Review: Quick Sort Part 1
07:51:49 - 08:05:30
Review: Quick Sort Part 1
In this two-part review of the Quick Sort algorithm, Bianca begins by looking back at how the partition routine functions. The partition routine chooses a pivot point and iterates the pivot location through the array swapping elements when necessary.
Review: Quick Sort Part 2
08:05:31 - 08:15:50
Review: Quick Sort Part 2
Bianca continues reviewing the Quick Sort algorithm by looking at the JavaScript implementations of the partition() and quicksort() methods. As with the other reviewed topics, she asks for some audience reflections at the end of the walk-through.
Review: Stacks & Queues
08:15:51 - 08:21:35
Review: Stacks & Queues
Bianca looks back at Stacks and Queues. Stacks implemented a last-in-first-out structure through the use of the push() and pop() methods. Queues use the dequeue() and enqueue() methods to implement a first-in-first-out structure.
Review: Linked Lists
08:21:36 - 08:32:47
Review: Linked Lists
Bianca reviews Linked Lists and demonstrates how they create ordered collections of nodes that are sequentially accessed and always contain a reference to the next node.
Review: Trees Part 1
08:32:48 - 08:40:15
Review: Trees Part 1
In this two-part review of Trees, Bianca demonstrates how to add branches to a Tree through the use of the addChild() method.
Review: Trees Part 2
08:40:16 - 08:52:09
Review: Trees Part 2
Bianca continues her review of Trees by diagramming the Tree structure she created in the first part.
Binary Trees
Binary Search Tree Overview
08:52:10 - 08:59:25
Binary Search Tree Overview
Trees have a parent-child relationship where a parent node can have any number of children. After reviewing the Tree structure, Bianca introduces a Binary Tree which adds a restriction that each node can only have two children. She then moves on to discuss Binary Search Trees which can be more performant than arrays since their nodes follow a specific structure.
Exercise: Binary Search Trees
08:59:26 - 09:00:09
Exercise: Binary Search Trees
In this exercise, you will create a Binary Search Tree. You will then implement the insert() and contains() methods. - https://github.com/kuychaco/algoClass/blob/master/data-structures/binarySearchTree.js
Pseudocoding a Binary Search Tree
09:00:10 - 09:08:24
Pseudocoding a Binary Search Tree
Bianca pseudocodes the constructor for a Binary Search Tree as well as the insert() method. The insert() method searches for the proper place to insert an element. If the value to be inserted is less than the current, the tree will move left. If the value is greater than the current, the tree will move right.
BST Search Procedure
09:08:25 - 09:19:29
BST Search Procedure
A major part of a Binary Search Tree's insert() method is the search procedure. The insert() method must determine the property place for the inserted value. Bianca diagrams the BST search procedure by looking at the resulting tree after as different values are added.
BST Review & Scoping Discussion
09:19:30 - 09:34:17
BST Review & Scoping Discussion
Bianca spends a few minutes asking the audience about which parts of the BST insert and search procedures are the most confusing or difficult to grasp. While responding to some questions, she reviews the BST insertion process and explains the "this" keyword and the role scope plays in the process.
Pseudocoding the BST contains() Method
09:34:18 - 09:45:45
Pseudocoding the BST contains() Method
Bianca pseudocodes the Binary Search Tree contains() method. The contains() method will return true when the supplied value is found. If the value is not found in the current node, the contains() method will recursively call itself to explore the left or right branch. If the value does not exist in the tree, it will return false.
Binary Search Tree Exercise Solution
09:45:46 - 09:56:49
Binary Search Tree Exercise Solution
Bianca walks through the solution to the Binary Search Tree exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/binarySearchTree.js
In-Order Traversal
09:56:50 - 10:07:06
In-Order Traversal
Searching through data structures like Arrays and Linked Lists are done with basic loops. A Binary Search Trees is more complex and is explored using in-order, pre-order, or post-order traversal. Bianca leads the audience in a short discussion about how the traversal of a BST might work before moving into a pseudocode example.
Pseudocoding In-Order Traversal Part 1
10:07:07 - 10:19:43
Pseudocoding In-Order Traversal Part 1
Bianca starts pseudocoding the in-order traversal algorithm for a Binary Search Tree. The in-order traversal algorithm will search to the left most node before traversing back to the right. Once the pseudocode is written, Bianca begins tracing out how it would execute with an example Binary Search Tree.
Pseudocoding In-Order Traversal Part 2
10:19:44 - 10:30:45
Pseudocoding In-Order Traversal Part 2
Bianca continues using the in-order traversal pseudocode to talk through an example Binary Search Tree. She traces out each step along the way and talks briefly about how in-order traversal compares to pre-order and post-order.
Pre-Order Traversal
10:30:46 - 10:39:39
Pre-Order Traversal
With pre-order traversal, rather than traversing to the left-most node first, the algorithm begins with the current node. After the current node is visited both left and right children are visited. Bianca modifies the in-order pseudocode to become the pre-order algorithm to further examine this difference.
Post-Order Traversal
10:39:40 - 10:43:52
Post-Order Traversal
Post-order traversal will fully explore the left and right children of a node before return to examine the current node. After looking at the post-order pseudocode, Bianca summarizes Binary Search Tree traversal by comparing the in-order, pre-order, and post-order prototype implementations.
Initial Time Complexity for a BST
10:43:53 - 10:52:44
Initial Time Complexity for a BST
Before moving on to deleting BST nodes, Bianca leads the group through the process of calculating the time complexity for a Binary Search Tree. Search the tree is a logarithmic process. Traversing the tree would typically be linear.
Deleting Min/Max Nodes
10:52:45 - 11:06:42
Deleting Min/Max Nodes
Bianca begins talking about how to delete nodes from a Binary Search Tree. The first deletion algorithm she wants to implement is deleting the min or max value. Deleting the min value involves moving left until the left is null. Then set the left pointer of the parent to null.
BST Review
11:06:43 - 11:11:35
BST Review
Before continuing with her min/max node deletion pseudocode, Bianca does a brief recap of Binary Search Trees.
Pseudocoding Min/Max Deletion
11:11:36 - 11:22:28
Pseudocoding Min/Max Deletion
Bianca pseudocodes the deleteMin() method which deletes the minimum value of a Binary Search Tree. This method is passed the parent node to traverse. It moves left until the left pointer is null. Once the minimum value is reached, the parents left is set to null to delete the minimum node.
Reviewing the Min/Max Pseudocode Part 1
11:22:29 - 11:32:04
Reviewing the Min/Max Pseudocode Part 1
Bianca reviews the min/max deletion pseudocode by walking through each step in the execution. She looks at a couple different scenarios to make sure the code accounts for any edge cases.
Reviewing the Min/Max Pseudocode Part 2
01:32:05 - 11:49:13
Reviewing the Min/Max Pseudocode Part 2
Bianca continues her review of the min/max deletion pseudocode. She checks the code against an edge case where BST nodes only have right children.
Exercise: Deleting Single-Child Nodes
11:49:14 - 11:50:49
Exercise: Deleting Single-Child Nodes
In this exercise, you will begin implementing the deleteNode() method. The deleteNode() method will search the tree for the passed value. - https://github.com/kuychaco/algoClass/blob/master/data-structures/binarySearchTree.js
Deleting BST Nodes Solution Part 1
11:50:50 - 12:02:09
Deleting BST Nodes Solution Part 1
Bianca begins walking through the solution to the Deleting BST Nodes exercise. In the first part, she checks to see if the node is a leaf or if it has one child.
Deleting BST Nodes Solution Part 2
12:02:10 - 12:09:33
Deleting BST Nodes Solution Part 2
Bianca continues the solution to the Deleting BST Nodes exercise. She finishes the pseudocode for deleting nodes with a single child. If the deleted node has a child, that child will be set to either the left or the right pointer of the parent. The location depends on the deleted node's relationship to the parent.
Exercise: Deleting Two Children
12:09:34 - 12:14:47
Exercise: Deleting Two Children
In this exercise, you will complete the third case for deleting a node from a Binary Search Tree. The third case involves deleting a node that has two children.
Deleting Two Children Solution
12:14:48 - 12:23:12
Deleting Two Children Solution
Bianca walks through the solution to the Delete Two Children exercise. In the solution, a node with two children must have it's subtree searched for the smallest value. That value will be moved to the position of the deleted node. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/binarySearchTree.js
Analysis of Time Complexity
12:23:13 - 12:27:59
Analysis of Time Complexity
Before moving to the next section, Bianca has a brief discussion about the time complexity of a Binary Search Tree. She also shares a few BST alternatives like AVL Trees, Red-Black Trees, and Splay Trees which may have better performance.
Graphs & Paths
Graph Vocabulary & Representations
12:28:00 - 12:39:21
Graph Vocabulary & Representations
A Graph is a collection of vertices connect by edges. A path is a sequence of connected vertices and a cycle is a path that is cyclical. Bianca outlines a few of these Graph vocabulary terms compares a Graph to an Adjacency Matrix.
Pseudocoding the Matrix Constructor
12:39:22 - 12:44:34
Pseudocoding the Matrix Constructor
Bianca pseudocodes the constructor for a Graph. The main function of the constructor is to initialize the storage matrix.
Pseudocoding the addNode() Method
12:44:35 - 12:53:53
Pseudocoding the addNode() Method
Next, Bianca pseudocodes the addNode() method for the Graph class. The addNode() method will determine how the node should be added and if a row or column is required in the matrix.
Pseudocoding the addEdges() Method
12:53:54 - 12:59:37
Pseudocoding the addEdges() Method
Finally, Bianca pseudocodes the addEdge() method. This method would receive the starting and ending vertices as parameters. Depending on if the matrix is directed or weighted, the matrix would then be updated to reflect the connection between to the vertices.
Exercise: Adding Nodes and Edges
12:59:38 - 13:02:32
Exercise: Adding Nodes and Edges
In this exercise, you will implement the Graph pseudocode in JavaScript. You will create the constructor, addNode(), and addEdge() methods.
Adding Nodes and Edges Solution
13:02:33 - 13:11:14
Adding Nodes and Edges Solution
Bianca walks through the solution to the Adding Nodes and Edges exercise.
Adjacency List
13:11:15 - 13:15:39
Adjacency List
Finding paths and neighbors are easier to do with an Adjacency List. In an Adjacency List the connections for each node are provided. After introducing Adjacency Lists, Bianca answers a few audience questions about their representation.
Pseudocoding an Adjacency List
13:15:40 - 13:19:44
Pseudocoding an Adjacency List
Bianca walks through the pseudocode for an Adjacency List. The constructor initializes the nodes array. The addNode() method adds the passed value ot the nodes array and the addEdges() method pushes the ending vertex to the starting vertices in the nodes array.
Exercise: Implement a Graph
13:19:45 - 13:21:29
Exercise: Implement a Graph
In this exercise, you will implement the entire Graph class except for any removal or traversing methods. - https://github.com/kuychaco/algoClass/blob/master/data-structures/graph.js
Implement a Graph Solution
13:21:30 - 13:32:42
Implement a Graph Solution
Bianca walks through the solution to the Implementing a Graph exercise. While she does not cover each method in the solution, the full codebase for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/graph.js
Depth & Breadth-First Search
Graph Traversing & Depth-First Search
13:32:43 - 13:35:51
Graph Traversing & Depth-First Search
Bianca gives a brief introduction to Graph traversal and depth first searching. Traversal algorithms help find paths, cycles, and connectivity. Depth-first search traverses to the bottom of the Graph before working its way back up and over to the other side.
Pseudocoding DFS Part 1
13:35:52 - 13:45:19
Pseudocoding DFS Part 1
Bianca begins pseudocoding depth-first search. Before writing the pseudocode she diagrams the depth-first search procedure and what the recursive callstack might look like.
Pseudocoding DFS Part 2
13:45:20 - 14:00:03
Pseudocoding DFS Part 2
Bianca continues pseudocoding the depth-first search algorithm. The base-case occurs when there is no longer any where to explore. Until the base-case is reached, the algorithm recursively loops through the edges. As nodes are explored, they must be flagged or marked as visited.
Breadth-First Search
14:00:04 - 14:05:10
Breadth-First Search
Unlike depth-first search, breadth-first search will fully explore a level of the Graph before diving deeper. Bianca reviews the procedure for breadth-first search and explains the use of a queue for managing the discovered nodes.
Pseudocoding BFS
14:05:11 - 14:18:06
Pseudocoding BFS
Bianca pseudocodes the breadth-first search algorithm. She also presents a few questions to the audience about how to get to the next layer and whether or not recursion is necessary.
Depth-First Search with a Graph Solution
14:18:07 - 14:23:01
Depth-First Search with a Graph Solution
Bianca looks and the final JavaScript solution for traversing a Graph with a depth-first-search. The code for the solution is located on the "solutions" branch in the Github exercise repository. Search the code for the Graph.prototype.traverseDepthFirst method. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/graph.js
DFS Graph Stack Trace Part 1
14:23:02 - 14:30:27
DFS Graph Stack Trace Part 1
With the traverseDepthFirst() method implemented, Bianca tests it out by tracing out each step as it traverses a graph. With each iteration she duplicates the code and adds comments for what the next recursive call would be.
DFS Graph Stack Trace Part 2
14:30:28 - 14:39:59
DFS Graph Stack Trace Part 2
Bianca continues tracing through her traversal of a Graph using the newly implemented traverseDepthFirst() method.
Depth-First Search with a Tree Solution
14:40:00 - 14:43:57
Depth-First Search with a Tree Solution
Bianca looks at the depth-first search algorithm for a Tree and compares the implementation to the Graph version. The code for the DFS Tree implementation is located in the Github exercise repository on the "solutions" branch. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/tree.js
Breadth-First Search Solution
14:43:58 - 14:51:23
Breadth-First Search Solution
Bianca shifts back to the breadth-first search algorithm and walks through the solution to the Graph implementation of breadth-first search. The code for the solution is located on the "solutions" branch in the Github exercise repository. - https://github.com/kuychaco/algoClass/blob/solutions/data-structures/graph.js
Breadth-First Search Stack Trace
14:51:24 - 15:06:34
Breadth-First Search Stack Trace
Bianca uses the traverseBreadthFirst() algorithm to traverse through a graph. She traces each iteration through the queue to reinforce the differences between depth-first and breadth-first traversal.
Hash Tables
Hash Tables
15:06:35 - 15:13:10
Hash Tables
A JavaScript Object is an example of a Hash Table because data is represented a key/value pairs. A hashing function can be used to map the key to an index by taking an input of any size and returning a hash code identifier of a fixed size.
Pseudocoding a Hashing Function
15:13:11 - 15:22:25
Pseudocoding a Hashing Function
Bianca pseudocodes the basics of a hashing function. The hashing function must always return the same output for any given input. The returned value could be based on mathematical operations performed on the ASCII values of each character from the input string.
Key Components of a Hash Table
15:22:26 - 15:34:07
Key Components of a Hash Table
The key components of a hash table include a storage object as well as a hashing function. A hash table should also be able to get, set, and remove properties from the storage object. Bianca uses these key components to demonstrate how a hash table accesses objects in memory.
Pseudocoding set(), get(), & remove()
15:34:08 - 15:42:33
Pseudocoding set(), get(), & remove()
Bianca pseudocodes the constructor, set(), get(), and remove() methods for a hash table. The constructor would initialize the storage object and hashing function. The get() and set() methods would use the hashing function to access the specified data from the storage.
Handling Collisions
15:42:34 - 15:47:32
Handling Collisions
Bianca spends a few minutes talking about handling collisions. A collision may occur if a weak hashing function is used and values are stored at the same location. With most modern hashing functions, collisions should not be an issue.
Exercise: Implementing a Hash Table
15:47:33 - 15:48:27
Exercise: Implementing a Hash Table
In this exercise, you will implement a Hash Table. The starting code is located in the Github exercise repository. Comments are added to each method which needs to be implemented.
Implementing a Hash Table Solution
15:48:28 - 15:55:37
Implementing a Hash Table Solution
Bianca walks through the solution to the Implementing a Hash Table exercise. The code for the solution is located on the “solutions” branch in the Github exercise repository.
Next Steps
15:55:38 - 16:05:09
Next Steps
Bianca wraps up the course by sharing some ideas on where to go from here. She revisits each topic covered in this course and provides links for further reading or additional resources. These links can be found in the slides linked with this video. (edited)

Скриншоты