Sorting and Searching Algorithms in Scala

In this video we define what we mean by substring searching. We give an example problem where substring searching would be useful.

• Learn what we mean by substring searching with an example
• Understand the problem through a sample text
• Compare different substring search algorithms 

In this video we show how the substring search can be implemented in a naïve simple manner.

• Understand the technique with a walk through
• See why naïve search is not very efficient
• Read the algorithm’s pseudocode

In this video clip we discuss what’s so special about the Scala’s string and implement the algorithm discussed in the previous video.

• Gain an insight to a feature found on the string class
• Find out about some functions available on Strings
• Watch a walkthrough of the implementation

Here we revisit the naïve substring search implementation and try to re-implement it in a more functional manner.

• Learn about how to use the find function on Strings
• Understand how the getOrElse works on Options
• See how easy it is to implement this search function

In this video we present an alternative faster technique to the substring search problem. The method can be split in two, building the prefix table and matching the substring. Here we explain both.

• Understand about the technique to avoid back tracking
• Learn how to build the algorithm’s prefix table
• See the algorithm’s Pseudocode

In this clip we implement the matching part of this KMP substring search problem in Scala.

• Revise many of the Scala tools we have used
• Watch the algorithm implemented
• Test and compare the implemented function

In this video we implement the generation of the KMP prefix lookup table for the substring search problem in Scala.

• Step through the implementation for the prefix table
• See how we combine both functions into one
• See our solution being used on an example

In this video we discuss the problem of organizing your data so it’s easily accessible. We introduce hash tables through an example problem and through a direct addressing technique.

• Understand the problem of organizing data through an example
• Learn about a direct addressing
• See how we extend direct addressing to create a hash table

In this video we show how to deal with the two aspects of hash tables, collisions and hashing. We mention two ways of handling collisions and various hashing techniques.

• Find out two solutions for dealing with collisions
• Read through the insert, search and delete operations
• Discover common hashing functions available 

In this video clip we present two types of Hash Table APIs, a mutable and an immutable version. We also see new Scala concepts such astype parameters.

• Understand the key interface difference between the mutable and immutable version
• Find out about type parameters in Scala
• Watch a walkthrough while we define the interfaces 

In this clip we show to implement a mutable hash table in Scala.

• Find out how to implement hashing functions working on any key
• See how to implement the insert, search and delete operations
• Test the implementation using some inserts and searches 

Here we explain the problem of building an efficient immutable hash table. We introduce the concept of persistent data structures and structural sharing.

• See the difficulty of implementing immutable data structures
• Learn how to use persistent tries for hash tables
• Understand which Scala construct we can use for tries 

After explaining persistent hash tables in the previous clip, in this video we show how to implement one of them.

• Find out about companion objects and the apply function
• Learn how to update elements in a vector object
• See how the different operations change in the immutable version 

In this video we introduce binary trees. We discuss how they can be used to organize your ordered data in an efficient manner.

• Discover what is a binary tree and terminology used
• Watch how searches and inserts work on the tree structure
• Understand the insert and search operations through their pseudocode 

Here we show how the traditional mutable binary tree operations can be adapted into an immutable manner. We do this by maximizing structural sharing.

• Understand the difficulty of implementing immutable binary trees
• Find out how we use structural sharing to improve performance
• Follow how we change the insert and search functions

In this video clip we demonstrate how to implement the search operation on binary trees in Scala.

• Learn how we use the ordering class to compare keys
• Discover how we model nodes using options and case classes
• Watch a walkthrough of the search function

In this clip we show how to develop the immutable insert operation for unbalanced binary trees.

• See how we can easily copy case classes
• Watch how we use option’s functions in the implementation
• Follow the walkthrough of the insert immutable operation

In this video we present algorithms that traverse binary trees. We explain how different depth first searches work and how their output differs. We also examine the breadth first search and discuss how it differs from depth first.

• Find out what we mean by traversing data structures
• Learn about different depth first search traversals
• Grasp the workings of the breadth first search traversal

In this clip we show to develop, in Scala, the traversal algorithms discussed in the previous video. We code both depth and breadth first search functions.

• Gain an insight about implicit parameters in Scala
• Uncover how to define higher order functions
• Watch how we implement both traversal functions

Here we introduce balanced binary trees. Specifically we talk about red black trees and the rules that govern them.

• Recognize the performance limitations of unbalanced binary trees
• Find out about the rules that Red Black trees follow
• Watch examples and pseudocode for tree rotations

In this video we implement the left and right tree rotations while maintaining tree immutability.

• Learn about enumerations in Scala to represent the node color
• See how we create the node structure in a case class
• Step through the implementation for both left and right rotations

In this video we show the insert in a red black tree works. We explain the four cases with inserting in the tree structure and in each case we describe what needs done to keep the tree balanced.

• Realize the complexity of inserting while keeping to the rules
• See the four red black insert scenarios to deal with
• Study the pseudocode broken down for each case

In this video we implement the functional insert algorithm we discussed in the previous section.

• Revise concepts such as guards and pattern matching
• Understand how we model each red black tree case
• Observe a simple and quick test on the balanced tree

In this video we present the closest pair problem and discuss a simple but inefficient brute force solution.

• Understand the closest pair problem through an example
• Learn how to measure Euclidean distances
• Discover a simple brute force solution to the problem 

Here we start building our general solution slowly. We do this by simplifying the problem to one dimension and discuss the technique of finding the closest pair.

• Uncover how slow the brute force solution is
• See how we can solve the problem in one dimension
• Study the one dimensional pseudocode 

In this video we show how to implement the algorithm for finding the closest pair in 1 dimension in Scala.

• Learn how we can access list indexes while iterating
• Discover how we implement the brute force function
• Watch a walkthrough for the rest of the algorithm 

In this video we extend the algorithm to handle an extra y dimension. We do this by highlighting the key differences from the one dimension and showing an example scenario.

• Compare the differences between the one and two dimensional algorithm
• Observe a solution to an example scenario
• Study the two dimensional pseudocode 

Here we do a code walkthrough for the final solution of the closest pair problem in two dimensions.

• Learn how we can partition a list into two
• See how we extend the one dimensional functions to two
• Notice the speed difference between brute-force and divide and conquer.