Divide and Conquer

In this example, we have defined a function with a conditional branch which checks for our base case, that of our input number having a value less than or equal to 1. As you might have noticed in the example Fibonacci sequence, if you think about the sequence of numbers as an array with starting index 0 and you try to access the 0 index or the 1 index, the number returned is the same number as the index. Because of that, our most simplified base case is that of returning n if n is 0 or 1 (less than or equal to one). If the input number is greater than 1, then you call the fibonacci function recursively twice substituting n for n-1 and n-2, respectively (which seeks to add the previous two numbers in the sequence). In our example, the input number is 9 and therefore the first thing that happens is our function calls itself twice and adds the results together fibonacci(8) + fibonacci(7). Because fibonacci of both 8 and 7 are not less than or equal to 1, they too must call themselves again twice: fibonacci(8) will call fibonacci(7) + fibonacci(6) and fibonacci(7) will call fibonacci(6) + fibonacci(5). These functions will continue to call themselves repeatedly, adding exponential function calls to the memory stack, until the base case is reached. Once the base case is reached and n is returned as either 0 or 1, each branch is able to start calculating actual values for their recursive call and it starts returning results up the function call chain. This recursive call nature is illustrated in Figure 13-1 for further clarity.

As you might have guessed, this implementation of a Fibonacci algorithm is not greedy. In fact, it has a time complexity of O(2ⁿ) which is the slowest program we have examined in this book so far. However, it is a great representation of how you can approach solving seemingly impossible problems by breaking them down into smaller and smaller sub-problems. Let’s combine this divide and conquer strategy with the two properties of greedy algorithms to solve our users’ requests for our model operating system.

Merge Sort

The first request from our users is to have the ability to sort the files in our operating system. Since we know that the insertion sort algorithm is not going to be fast enough to solve our users’ needs, we must identify an algorithm that can sort the files in our operating system in faster than O(n²) time. Merge sort uses a divide and conquer method that will end up yielding O(n∗log(n)) time, which is relatively fast compared to the naive solution of insertion sort. What a merge sort attempts to do is take in two lists that are already sorted and merge them together, taking the lesser of the first values of the two lists as it builds up a list. This satisfies the “Greedy Choice” property of the greedy algorithm pattern since it can take the locally optimal choice (the lesser of the first values of the two lists) and it will result in a globally optimal result.

For example, assume we have two previously sorted lists of files with values “Alpha.txt”, “Jason.txt”, and “Zordon.txt” in the first list and “Billy.txt”, “Kimberly.txt”, “Tina.txt”, and “Zack.txt” in the second list. The merge sort will examine the first item in both lists and determine that “Alpha.txt” should be added to its newly constructed list and not “Billy.txt”. Then the merge sort will examine what remains of the two lists and compare “Billy.txt” to “Jason.txt”, at which point it will add “Billy.txt” to its newly constructed list which now contains “Alpha.txt” and “Billy.txt” in sorted order. It will continue to examine both lists pulling the lesser value from the head of each list until an entirely new list is constructed in sorted order.

At this point, you might wonder how we can make the assumption that the two lists that are being merged are already in sorted order themselves. The answer to that comes from a recursive divide and conquer function. In our merge sort algorithm, we can continue to divide our list in half recursively until each list essentially contains only one item. This satisfies the optimal substructure property of the greedy algorithm pattern. In our example scenario, once the lists have been divided all the way down to their base case, we would have seven lists with only one item in each. From there, the recursive function that divided those lists will compare the two halves that it divided and merge them in sorted order.

In this example, instead of using a basic List data structure, the optimal data structure to use is an Array because we will need to continually access the midpoint of each list. To know the midpoint of a list, we must first determine its length, which takes O(n) time in a List but O(1) time for an Array. Using an array helps keep the operation cost of our algorithm down. You’ll notice that we are actually using an ArrayBuffer from the scala mutable collections library. The ArrayBuffer collection implements various methods for us to help the array grow and shrink (via index copying to new lists) that we don’t have to implement ourselves, for convenience.

In our first recursive function, mergeSort, we first check our base case, which is that of whether or not the midpoint is 0. The midpoint would be zero only if the length of the list were less than or equal to one, which would be the most basic list. In that scenario, we simply return the list as it is already sorted. If the midpoint of the list is anything besides zero, as denoted by the underscore operator, then we split the list into two lists, left and right, at its midpoint. From there, we call the merge function and pass a recursive call to mergeSort on the left list and a recursive call to mergeSort on the right list, which will continue to divide and merge all the way down to the base case.

The merge function is also a recursive function, but this one has two base cases. The first base case is a scenario that matches if the left list has values but the right list is empty. In this case, it simply returns the left list. The second base case is a scenario that matches if the right list has values but the left list is empty. In that case, the right list is returned. If both lists have values, then the heads of the two lists are compared. The head with the least value is added to a new ArrayBuffer and then that ArrayBuffer is added to the result of a recursive merge call on the remnants of the two lists. When all the recursive functions have been called down to their base cases, returned a value from the base case, and calculated back up the recursive chain, a new sorted ArrayBuffer will be returned in O(n∗log(n)) time. This should be fast enough to satisfy our users when using our file system.

Now the command for list splits the user input and calls a lift function on the results to pull out the value at index 1, if it exists. The result of the lift function is an Option type. An Option in Scala is a data type that wraps the underlying data that you are interested in (in this case, we are using an Option that wraps a String) and will indicate to the code whether the data in question exists or not. If it does exist, it is said to be of type Some; otherwise, it is of type None. Some and None are both wrapped up within the type Option, and we can use a pattern match to pull out whether the underlying data actually exists.

In the method signature of our list function, we have added the parameter sort: Option[String]. This tells Scala that we are expecting an Option type to be passed to this function, and if any underlying data exists, it will be of type String. We then pattern match on the sort parameter. If the underlying data of the Option is of type Some, meaning it does contain data, then we want to take the contents of the directory, add them to an ArrayBuffer, and pass them to the mergeSort function. This will sort them in descending order and print them to the console. If the underlying data of the Option is of type None, then we just want to print each item in the directory in its existing order. We can test this command by typing the command list in our Nebula shell without any additional arguments to see the list printed normally or the command list sort (or any other additional argument) to see the list sorted in descending order.

Binary Search

The next request from the users of our model operating system is to be able to search for a file to see if it exists. We could simply check every file in the directory to see if it matches a given search term, but how might we use the concepts of greedy algorithms and divide and conquer to perform this operation in a more efficient manor? The binary search algorithm will improve the performance of a search function over a sequential search algorithm from O(n) time to O(log(n)) time.

The input parameters to our search function are a keyword, which is the file that you are looking for, and optionally a file list (which is set to None by default), which is used during recursion but not for the initial call. The first thing our algorithm does is check to see if a file list was provided. If it is provided, then it sets the variable files to the provided value. If it is not provided, it initializes a new file list by pulling all of the files out of the current directory, adding them to an ArrayBuffer, and performing our mergeSort function on them. The result of the merge sort is then stored in the files variable. By performing the merge sort, we are satisfying the “Greedy Choice” property that allows us to choose a locally optimal path when we start dividing the list in half and searching through each half of the list. The fact that the sorted list can be continually divided and checked also inherently satisfies the optimal substructure property of the greedy algorithm requirements.

Next, the algorithm initializes a midpoint variable by performing integer division on the length of the list. This midpoint is used to check for values or continually divide the list in half, similar to how we used the midpoint in the merge sort algorithm. Finally, we perform a pattern match on the length of the file list that contains three cases. The first case is that the length of the ArrayBuffer is 1, in which case there is only one file to check the search keyword against. If that is the case, we perform the check, and if it matches, we return the value; otherwise, we return a message that says “No match found.” The next case is if the file list length is 2. In this case, we can simply check both files to see if they match the search keyword or return our failure message otherwise.

The final case matches all other lengths of the list. In this scenario, we initialize a left variable and a right variable by splitting the file list in half at its midpoint. Next, we check to see if the file matches at the midpoint. If so, we return it. If not, we check to see if the search term is larger than the word contained at the midpoint. If it is larger, then we recursively perform the search on the left half of the list (since it is sorted in descending order) by passing the keyword back to search along with Some(left) as the parameter for the optional fileList argument. If it is smaller, then we recursively perform the search on the right half of the list instead. This will continue recursively, giving us a half-life characteristic of the search space each time, until either the keyword is found or the value “No match is found.” is returned. A visual representation of this recursive strategy is provided in Figure 13-2.

In order to call this search function, we’ve added a command to our NebulaOS command list that checks if the user input contains the word “search.” If it does, we split the input into an array and pull out the second position of that array (index 1) as the search keyword to pass to the search function. Thus, if our user provides in the input “search sample.txt”, it will traverse all of the files in the directory, and if it finds a text file named “sample”, it will print “sample.txt” to the terminal; otherwise, it will print “No match found.”

This all works great if the users are happy to continue creating all of their files in a single directory. But at some point, for scalability’s sake, they are going to want to organize their files a little better to make them easier to search. Let’s take our operating system one step further and add the ability to create folders and navigate between them. Then we can put functions in place to search for files either within an individual directory or in the operating system as a whole. In order to do that, we must create a graph data structure to represent the folders in our operating system and implement graph traversal algorithms to search through them.

Depth First Search

Not all algorithms can be implemented in a greedy fashion. In the case of searching a graph for a value, it is not possible to use a divide and conquer strategy since the folders contain values independent of each other. Because of this, we are not able to sort the values in our graph to eliminate part of the search space as we traverse through the graph. Also, a graph similar to ours is not binary and therefore could have n number of child nodes for each node. This means that we cannot satisfy the optimal substructure or greedy choice properties required of greedy algorithms.

Because of this, we will need to resort to a more naive algorithm that checks every node for the values we are looking for. However, depending on the user’s knowledge of their file structure, they might be able to optimize their search by choosing one of two graph traversal algorithms. The first algorithm is called depth first search.

The depth first search algorithm is a strategy wherein we traverse the nodes of a graph one branch at a time, checking every node until we hit the leaf and then returning back up the branch to check additional branches. This algorithm is impactful if you know that the value you are looking for is nested deep within many layers of nodes. If we do possess this knowledge, there’s no reason to check the base of each branch in a broad sense before moving on to check the leaves as we know that would generate inefficiencies in our search. To further illustrate this point, consider the graph in Figure 13-4 and the order in which it visits each node.

In Listing 13-9, we start by adding a search command with a -dfs parameter, signifying that the user wishes to use depth first search. Ensure that this command is placed before the original search command in our pattern matching expression so that it does not match the original search command first and ignore our depth first search command. This depth first search command should take a keyword in index position 2 after the command keyword and the -dfs parameter. Next, we define our depth first search function that is referenced in the command. The only argument it takes is the keyword to be searched for.

We start the algorithm by initializing a Stack data structure, imported from the scala.collection.mutable library, and adding the root directory to it. We call this stack foldersToSearch. Next we initialize a variable called folderFound which we set to an empty string for now. After that, we start a while loop that will kick off our graph traversal. That while loop is going to continue to iterate until the stack is empty or the folderFound variable contains a value. In the while loop, we first pop the first item off the stack and then pass that value to our binary search algorithm to search for the keyword in that directory. If the value is found, it is added to the folderFound variable and our algorithm is done. If it does not find the keyword in this root directory, it passes the node that was searched to a helper called extractFolders. This function checks all the contents of the given folder and pulls out only the items that are other folders or other nodes in the graph. Once extracted, these nodes are all pushed onto the stack for future investigation, keeping the stack from being empty and therefor ensuring that the while loop will continue to traverse nodes. The loop will continue to iterate until there are no more nodes to visit or until it finds the folder that contains the keyword. Once we break out of the loop, we print to the terminal where the keyword was found or that it was not found at all.

Breadth First Search

If you know that the keyword you are looking for is likely to be housed in a fairly shallow node in the graph, it is likely better to use a breadth first search algorithm. In contrast to the depth first search algorithm, breadth first search checks each node in a layer before moving on to the next layer. Figure 13-5 provides an illustration of the order in which nodes would be visited in breadth first traversal.

Our users now have the ability to create folders, navigate between them, add files to folders, search within a folder, and search globally using both depth first search and breadth first search. However, their search is still predicated on matching a keyword exactly. We could add in some logic to match on sub-strings rather than full strings, but that does not protect our user in the event that they made a small typo. How might we still return a matching result in the event our user made a mistake? To do that, we could introduce fuzzy matching using an algorithmic strategy known as dynamic programming.

Levenshtein Distance

Given two strings to compare, the Levenshtein distance algorithm provides three operations to transform the first string into the second string: insertion, deletion, or replacement. Each operation that needs to be performed in the comparison incurs a cost that is counted. This dynamic programming algorithm tallies up all possible transformations to turn the first string into the second string and then returns a count of the minimum number of transformations required to satisfy the comparison.

In this example, the first thing that we do is initialize a hash map called memoizedCosts that will store the cost of operations for any two strings of given integer lengths. This satisfies the memoization property of the dynamic programming design pattern. Next, it creates an inner function that takes the length of the first string and the length of the second string as input parameters. The first thing the inner function does is check to see if it has already calculated a minimum cost for two strings of those lengths (with the characters defined at their given index position) that it has already stored in the hash table. If it has, then the inner function is complete. If it has not, then it must calculate the value and store it in the hash table. This is all wrapped in the getOrElseUpdate method call.

Next, the algorithm does a pattern match on the lengths of the strings which evaluates two base cases. First, a scenario wherein the first string has some length and the second string has length 0. The cost of transforming the second string of length 0 into the first string is the length of the first string since we will need to insert every character from the first string. Second, it performs this same logic but in reverse. After the base cases have been evaluated, in the event that both strings have some length, it initializes a list that contains three recursive function calls.

The first call represents a scenario wherein the last character position of the first string could be considered deleted. Such would be the only case if the first string were “turns” and the second string were “turn” and all we had to do was delete the last character in the first string. In that scenario, we count the cost (1) and then add in the cost of performing these evaluations on all the other characters in the remaining sub-string of string one and all the characters in string two.

The second call in the list represents a scenario where instead of deleting the last character position in the first string, we insert the last character in string two into the last position in string one. In that scenario, we now know that the last character from string two should now match, so we only need to finish comparing string one to a sub-string of all characters in string two except the last character. So we add one to a recursive call that removes one character length from string two.

The last recursive call checks to see if the last character positions in both strings actually match. If they do, the cost is zero, and if they don’t, the cost of replacement is 1. Once we’ve determined what the cost will be for a replacement operation, we subtract one from the character lengths of both strings and advance it through recursion. In our Fibonacci recursive function, you were able to see how each iteration through the recursion split out two additional function calls into a tree that evaluated all the way down to the base case in each branch. In this edit distance algorithm, each of these recursive calls will make three additional recursive calls all the way down to their base cases. However, in many of those calls, the cost will have already been calculated and stored in the memoization table, thus speeding up the algorithm. This is the power of dynamic programming.

It is worthy to note that the unique part of this algorithm is that through each iteration, as it starts to return values up through the recursion chain, the whole function will only return the minimum cost evaluated for the three scenarios in the list. This is denoted by the call to the min method at the end of the list initialization. This demonstrates how useful dynamic programming can be in optimization problems that seek to find a min or max value from a set of scenarios. You will see these types of strategies employed in many algorithms that seek to find the shortest path between two nodes on a graph.

After defining the inner function, we actually call that inner function with the lengths of the two strings provided to the outer function. This call to the inner function builds up our memoization table. Once it has been built, we can access the key in that table that represents the lengths of the two strings that we are comparing to find the minimum edit cost of the two strings, and return that as the overall value of the outer function.

Given this useful functionality, instead of comparing equality in our three search functions, you can check to see if the edit distance of the search keyword and the file being evaluated falls below a certain threshold (you can decide whatever threshold you want that to be). In my case, I elected to check if the edit distance between the words was less than 2, meaning that there could only be at most a one-character difference between the words for my operating system to consider it a match. Now my users have a small margin for error in spelling differences when searching for files which adds a marginal level of convenience that hopefully contributes to the overall user experience of the application.