# Practical Problem Solving with Algorithms

Learning Paths:

Topics:

Table of Contents

## Introduction

### Introduction

Kyle Simpson begins the course by comparing the algorithms courses on Frontend Masters and shares a couple of recommended computer science books that outline data structures and algorithms.### Course Overview

Kyle summarizes this course's key takeaways, including balancing CPU and Memory usage, shaping data structures to fit a problem, and understanding the drawbacks of premature optimization.

## Primer

### Data Structures Overview

Kyle reviews common data structures found in computer science. These include Arrays, Stacks, Queues, Sets, Objects, Maps, Trees, and Graphs.### Algorithms & Techniques Overview

Kyle reviews common algorithms found in computer science. These include BubbleSort, QuickSort, Tree Traversals, Path Finding, and Binary Search. Techniques like Iteration, Recursion, Indexing, and Referencing are also discussed in this lesson.### Golden Weighted Ball Problem

Kyle explains the Golden Weighted Ball problem, a common interview question. Eight identical balls are presented, and one of the eight balls is lighter. A scale must be used to determine which ball is the lightest in the fewest number of attempts.

## Example Problems

### Packing Algorithms & Collision Detection

Kyle shares a few examples of problems that could be solved with algorithms. Problems include converting binary numbers to decimals, packing objects into the smallest container possible, and using collision detection to simplify UI markers.### Tetris, Puzzles, & Size Comparison

Kyle continues sharing examples of problems that could be solved with algorithms. Creating a bot for automating Tetris games, analyzing puzzle pieces, and determining the largest contiguous object in a group are among the examples provided.

## Periodic Table Speller

### Periodic Table Speller Setup

Kyle introduces the Periodic Table Speller project and provides instructions for cloning the project repository and running the code. In this project, a word entered in the text box will be spelled using element symbols from the periodic table. The "start-here" branch should be used to begin the project.### Lookup Function

Kyle implements the lookup function, which returns an element based on a specified symbol. The toLowerCase method is used to make the lookup case-insensitive.### Check Function: Recursion

Kyle begins implementing the check function. It loops through the elements in the periodic table and checks to see if any symbols match part of the submitted word. If so, the check function is recursively called on for any remaining characters in the word.### Check Function: Base Case

Kyle finishes the check function by adding base cases that stop the function from being recursively called. When a base case is reached, the recursive function calls are sequentially returned off the call stack, and the array of symbols is completed. The solution can be found on the option-1 branch.### Optimizing the Lookup Function

Kyle optimizes the lookup function by creating an index of symbols when the data is loaded inside the loadPeriodicTable function. This index can be used inside the lookup function, eliminating the need for a loop. The option-1 branch can be used as a starting point for this lesson.### Finding Candidates

Kyle creates a findCandidates function to recursively find a list of symbol candidates matching one and two-letter character combinations in the submitted word. Note: Better code optimizations can be found on the option-2b and option-3 branches.### spellWord Function with Character Sets

Kyle refactors the check function to use a spellWords function that recursively searches for matching symbols by prioritizing two-character matches. Note: Better code optimizations can be found on the option-2b and option-3 branches.### spellWord Function Q&A

Kyle answers optimization questions and discusses alternate implementations. A small refactor is performed for consistency, and a bug is addressed. Note: Better code optimizations can be found on the option-2b and option-3 branches.### Performance Characteristics

Kyle highlights the performance characteristics of the Periodic Table Speller and compares theoretical vs. practical performance. Note: Better code optimizations can be found on the option-2b and option-3 branches.

## Chessboard Diagonals

### Drawing the Chessboard

Kyle begins the Chessboard Diagonals project by writing a script that populates the webpage with a black and white chessboard. The board consists of eight rows and eight columns. DIV elements are used to represent each tile.### Traversing the Tiles

Kyle demonstrates how the querySelectorAll method can be used to traverse the tiles on the chessboard. The querySelectorAll method returns a NodeList of elements matching the supplied pattern. A loop goes through the list of elements and removes the "highlighted" class from each element.### Highlighting Diagonal Tiles

Kyle uses a series of for loops to search for diagonal tiles to highlight. Each loop traverses tiles in a different diagonal direction until an upper or lower bound is reached.### Optimizing DOM Traversal

Kyle optimizes the diagonal tile algorithm by reducing DOM traversals and saving a tile's row and column indices to dataset properties. Use the option-1 branch linked below as a starting point for this lesson.### Using Two-Dimensional Arrays

Kyle constructs a two-dimensional array to save references for each tile. Traversing and accessing the array is more performant than re-querying the DOM. Use the option-2 branch linked below as a starting point for this lesson.### Creating a Diagonal Data Structure

Kyle rethinks the current data structure and explains why using a diagonal data structure can optimize the algorithm. Use the option-3 branch linked below as a starting point for this lesson.### Refactoring the Highlight Function

Kyle refactors the highlight function to utilize the diagonal data structure. A Map variable is used to create references to store major and minor diagonal indices for each element. The final solution for the Chessboard Diagonals problem can be found on the option-4 branch.

## Knight's Dialer

### Knights Dialer Exercise

Kyle introduces the Knight's Dialer exercise. Algorithms will be written to count the number of distinct paths that can be traversed when starting from a specific key and which different paths can be taken without landing on any previously visited keys.### Reachable Keys Function

Kyle implements the reachableKeys function, which builds an array of nearby keys for each key on the dialer pad.### Optimizing with a Data Structure

Kyle refactors the code to replace the reachable keys algorithm with a static data structure. The reachable keys on the dial pad never change, so using a static data structure with the available values optimizes the overall application and eliminates the need to traverse the dialer when establishing the hops a knight can make.### Recursive Traversal

Kyle explains breadth-first search and implements the countPaths function, which is recursively called to determine the number of paths required to complete the specified hops.### Big O Complexity

Kyle introduces big O complexity and how it affects the performance of an algorithm. The current implementation of the Knight's Dialer code has a complexity of 2.222 to the N.### Acyclic Paths

Kyle implements the listAcyclicPaths function. It returns an array of distinct paths with no repeated hops. A followPath function is also created to recursively follow each hop and push it into the paths array if it doesn't exist.### Optimize Recursion with Memoization

Kyle explains how algorithms can be optimized by using memoization. When a path is followed, it can be saved using a combination of the starting value and the length as the index. The option-2 branch can be used as a starting point for this lesson.### Dynamic Programming Overview

Kyle introduces dynamic programming, combining the memoization or top-down approach with the tabulation or bottom-up approach. This combination creates an algorithm that is both memory efficient and performant. The option-3 branch can be used as a starting point for this lesson### Visualizing Dynamic Programming

Kyle visualizes how the dynamic programming approach will be applied to the counthPath function. Each iteration will tabulate the paths with a linear algorithmic complexity.### Coding with Dynamic Programming

Kyle refactors the counthPaths function to use the bottom-up tabulation method of dynamic programming to determine how many paths are required for each hop. The final solution can be found on the option-4 branch.

## Wordy Problem

### Wordy Unscrambler Overview

Kyle introduces the Wordy Scrambler problem and compares it to other word puzzles like Wordscapes where a scrambled list of letters must be decoded to make word combinations.### Wordy Unscrambler Algorithm

Kyle talks through the possible algorithms which could be used to solve the Wordy Scrambler problem initially. Finding every permutation of the submitted word requires N-factorial executions. This will lead to performance issues with longer words.### Divide & Conquer Solution

Kyle implements the initial solution to the Wordy Unscrambler problem. The algorithm uses a divide & conquer approach. Clone the repo linked below and checkout the start-here branch to begin the lesson.### Trie Tree Data Structure

Kyle walks through choosing a data structure and introduces the trie tree data structure. The loadWords function is implemented, which constructs the trie tree data structure. The option-1 branch can be used as a starting point for this lesson.### Finding Words in a Trie Tree

Kyle refactors the findWords function to utilize the trie tree data structure. If the current node in the tree is a word, the word is pushed into the words array. Otherwise, the function is recursively called with the remaining letters from the input.### Garbage Collection & Object Pool

Kyle introduces garbage collection and explains how object pooling reduces memory consumption by allocating the memory required to complete common operations and maintaining the pool size by recycling unused objects. The deepool library will be the object pool used in this application. The option-2 branch can be used as a starting point for this lesson.### Implement an Object Pool

Kyle refactors the findWords function to implement the deepool library's object pool. A try/finally block is used because the finally part of the statement will execute even when an exception occurs. Since it executes every time, it's ideal for handling garbage collection. The option-3 branch can be used as a starting point for this lesson.### Directed Acyclic Word Graph Overview

Kyle explains a radix tree is a trie tree that has been compacted. A radix tree would reduce the memory footprint in the application, however, the directed acyclic word graph structure is a better fit because it maintains a similar implementation while adding the memory optimizations.### Implementing a DAWG Data Structure

Kyle implements the directed acyclic word graph. A third-party library is added to the project and the loadWords function is refactored. The option-4 branch can be used as a starting point for this lesson.