Table of Contents
IntroductionBianca 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 ScopeBianca 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 SucceedUsing 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.
Creating a Constructor SolutionBianca walks through the solution to the Creating a Constructor exercise.
Stacks & Queues
StacksThe 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.
Implementing a StackBianca 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.
QueuesQueues 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 QueuesIn 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.
Creating Stacks and Queues SolutionBianca 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.
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 ExecutionBianca 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 FunctionBianca 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.
Factorial with LoopUsing 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 RecursionBianca 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 QuestionsIn this exercise, you will implement a common recursion questions that are often asked during job interviews.
Recursive Reverse SolutionBianca 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.
Recursive Multiplier SolutionBianca 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.
MinStack SolutionNow 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.
Implementing a Queue with Two Stacks SolutionBianca 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.
Space vs. Time ComplexityTime 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 ComplexityBianca 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-OIn 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 LoopsCalculating 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.
Calculating Time Complexity SolutionBianca walks through the solution to the Calculating Time Complexity exercise.
Bubble SortBianca 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.
Stability and AdaptabilityA 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 SortBianca 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 SortIn this exercise, you will implement the elementary sorting algorithms covered in this section. These algorithms include Bubble Sort, Insertion Sort, and Selection Sort.
Bubble, Insertion, and Selection Sort SolutionBianca 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.
Merge SortThe 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 RoutineTo 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 SortBianca 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 SortWhile 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 OverviewThe 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 PartitionWhile 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 1Bianca 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 2Bianca 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 PseudocodeWith 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 AlgorithmAs 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 1Bianca 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 2Bianca 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
TreesBianca 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 ListsA 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 ListBianca 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 ListIn 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.
Implement a Linked List SolutionBianca 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.
Implementing a TreeNow 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 ComplexityBianca 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 SortingBianca 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: RecursionRecursion 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 SortBianca 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 1In 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: Stacks & QueuesBianca 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 ListsBianca 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 1In 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 2Bianca continues her review of Trees by diagramming the Tree structure she created in the first part.
Binary Search Tree OverviewTrees 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 TreesIn this exercise, you will create a Binary Search Tree. You will then implement the insert() and contains() methods.
Pseudocoding a Binary Search TreeBianca 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 ProcedureA 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 DiscussionBianca 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() MethodBianca 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 SolutionBianca 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.
In-Order TraversalSearching 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 1Bianca 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 2Bianca 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 TraversalWith 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 TraversalPost-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 BSTBefore 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 NodesBianca 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 ReviewBefore continuing with her min/max node deletion pseudocode, Bianca does a brief recap of Binary Search Trees.
Pseudocoding Min/Max DeletionBianca 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 1Bianca 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 2Bianca 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 NodesIn this exercise, you will begin implementing the deleteNode() method. The deleteNode() method will search the tree for the passed value.
Deleting BST Nodes Solution Part 1Bianca 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 2Bianca 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 ChildrenIn 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 SolutionBianca 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.
Analysis of Time ComplexityBefore 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 & RepresentationsA 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 ConstructorBianca pseudocodes the constructor for a Graph. The main function of the constructor is to initialize the storage matrix.
Pseudocoding the addNode() MethodNext, 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() MethodFinally, 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.
Adding Nodes and Edges SolutionBianca walks through the solution to the Adding Nodes and Edges exercise.
Adjacency ListFinding 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 ListBianca 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 GraphIn this exercise, you will implement the entire Graph class except for any removal or traversing methods.
Implement a Graph SolutionBianca 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.
Depth & Breadth-First Search
Graph Traversing & Depth-First SearchBianca 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 1Bianca 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 2Bianca 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 SearchUnlike 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 BFSBianca 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.
DFS Graph Stack Trace Part 1With 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 2Bianca continues tracing through her traversal of a Graph using the newly implemented traverseDepthFirst() method.
Depth-First Search with a Tree SolutionBianca 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.
Breadth-First Search SolutionBianca 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.
Breadth-First Search Stack TraceBianca 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.
Pseudocoding a Hashing FunctionBianca 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 TableThe 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()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 CollisionsBianca 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 TableIn 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 SolutionBianca 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 StepsBianca 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)