Objectives Develop a recursive algorithm that involves backtracking Description This activity is similar to the previous assignment - you will be analyzing a problem and then solving it using recursion. This time there's only one problem, and it's a little more complicated than the previous problems. It will involve backtracking, which simply means reversing an action performed earlier in the algorithm The Problem By now, you should be familiar with the concepts of files and directories (folders) as they relate to computers. Everything on your hard drive is stored in files, which are organized into directories (which can also contain other directories). The directories inside of a directory are called its "subdirectories", and the directory containing them would be their "parent directory The fact that directories can be nested within each other makes recursion a useful tool for interacting with them. Many recursive algorithms involving files take the form of do X for each file in this directory, then repeat this algorithm in each subdirectory'. Your task will be to write an algorithm that recursively searches a directory (and all of its subdirectories, and all of their subdirectories, etc.) for files with a specific name. If there are multiple files with that name, this algorithm should locate all of them Rather than using the normal file operations, you're going to be writing code to control an object called a "FileCrawler" (included in starter code). The FileCrawler class contains methods covering most of the operations you'll need to perform as part of this algorithm. Your algorithm will have to move the FileCrawler through all of the directories within the starting directory, check the names of those files, and tell the FileCrawler to 'collect each file with a name matching the one you're searching for File Crawler Operations . . When outlining and designing your recursive algorithm, it will help to keep each step simple and, as much as possible, phrase it in terms of operations we can perform with the file crawler. Here is a list of its operations (each corresponds to a method in the FileCrawler class): Get a list of subdirectories in the current directory Get a list of files in the current directory Collect a file (should only be used on the files you're searching for) Enter a subdirectory Return (backtrack) to the parent directory of the current directory In addition, it has the following methods for debugging/testing purposes. You can use them to test your algorithm, but don't put them in the final version that you submit: Print the current directory Print all of the collected files Print its traversal history Note that two of those operations involve lists (arrays) of File objects. You'll need to use those lists in your algorithm, and that means you'll need to use loops to iterate over those lists. The recursion in this program isn't replacing loops, like in the simpler examples we've used before. . Algorithm Outline The same questions we used for the previous problems can be useful for designing a solution to this problem. 1. Break the problem into two parts: a smaller version of the problem you're attempting to solve (or in this case, a list of smaller problems), and a trivial problem that can be solved with no recursion 2. Restate the problem in terms of the smaller recursive problem and the trivial problem from step 1. 3. What is the base case for this problem? This would be a set of input or a scenario where you only need to solve the trivial problem, or you don't need to do anything. The smaller recursive problem should not need to be solved in order for you to solve the base case. 4. In order for this algorithm to be practical, we need to guarantee that we always reach our base case. How do you know that the base case will always be reached? Do you need to make any assumptions about the input to guarantee this? Algorithm Design . . Suggestions for designing the algorithm: Start with a list of input for your algorithm. State the name, type, and purpose of each input value. Write step by step instructions for solving the problem. If a step involves calculating a new value, make sure you provide a name for that value so that it can be referred to in later steps. These instructions should be in English, NOT code. Your input and instructions should be consistent with your answers to the questions in part 1. If you can't write directions consistent with those answers, you may need to go back and At some point you will need to backtrack. If the FileCrawler enters a subdirectory, it eventually needs to leave so that it can explore other files within the directory it came from. Think carefully about when backtracking is appropriate, and remember that your recursive calls will of your algorithm is structured correctly) backtrack on their own The algorithm must be recursive. If you don't have a step that performs the entire algorithm again with different input, then your algorithm isn't recursive. revise them. . Algorithm Implementation Once you've designed your algorithm, write out each step as a comment and try coding the comments. If your steps are vague or contain too many instructions, you may need to revise and break them into smaller pleces first Advice Don't try to modify the FileCrawler class. Your recursive method will be tested with my Objectives Develop a recursive algorithm that involves backtracking Description This activity is similar to the previous assignment - you will be analyzing a problem and then solving it using recursion. This time there's only one problem, and it's a little more complicated than the previous problems. It will involve backtracking, which simply means reversing an action performed earlier in the algorithm The Problem By now, you should be familiar with the concepts of files and directories (folders) as they relate to computers. Everything on your hard drive is stored in files, which are organized into directories (which can also contain other directories). The directories inside of a directory are called its "subdirectories", and the directory containing them would be their "parent directory The fact that directories can be nested within each other makes recursion a useful tool for interacting with them. Many recursive algorithms involving files take the form of do X for each file in this directory, then repeat this algorithm in each subdirectory'. Your task will be to write an algorithm that recursively searches a directory (and all of its subdirectories, and all of their subdirectories, etc.) for files with a specific name. If there are multiple files with that name, this algorithm should locate all of them Rather than using the normal file operations, you're going to be writing code to control an object called a "FileCrawler" (included in starter code). The FileCrawler class contains methods covering most of the operations you'll need to perform as part of this algorithm. Your algorithm will have to move the FileCrawler through all of the directories within the starting directory, check the names of those files, and tell the FileCrawler to 'collect each file with a name matching the one you're searching for File Crawler Operations . . When outlining and designing your recursive algorithm, it will help to keep each step simple and, as much as possible, phrase it in terms of operations we can perform with the file crawler. Here is a list of its operations (each corresponds to a method in the FileCrawler class): Get a list of subdirectories in the current directory Get a list of files in the current directory Collect a file (should only be used on the files you're searching for) Enter a subdirectory Return (backtrack) to the parent directory of the current directory In addition, it has the following methods for debugging/testing purposes. You can use them to test your algorithm, but don't put them in the final version that you submit: Print the current directory Print all of the collected files Print its traversal history Note that two of those operations involve lists (arrays) of File objects. You'll need to use those lists in your algorithm, and that means you'll need to use loops to iterate over those lists. The recursion in this program isn't replacing loops, like in the simpler examples we've used before. . Algorithm Outline The same questions we used for the previous problems can be useful for designing a solution to this problem. 1. Break the problem into two parts: a smaller version of the problem you're attempting to solve (or in this case, a list of smaller problems), and a trivial problem that can be solved with no recursion 2. Restate the problem in terms of the smaller recursive problem and the trivial problem from step 1. 3. What is the base case for this problem? This would be a set of input or a scenario where you only need to solve the trivial problem, or you don't need to do anything. The smaller recursive problem should not need to be solved in order for you to solve the base case. 4. In order for this algorithm to be practical, we need to guarantee that we always reach our base case. How do you know that the base case will always be reached? Do you need to make any assumptions about the input to guarantee this? Algorithm Design . . Suggestions for designing the algorithm: Start with a list of input for your algorithm. State the name, type, and purpose of each input value. Write step by step instructions for solving the problem. If a step involves calculating a new value, make sure you provide a name for that value so that it can be referred to in later steps. These instructions should be in English, NOT code. Your input and instructions should be consistent with your answers to the questions in part 1. If you can't write directions consistent with those answers, you may need to go back and At some point you will need to backtrack. If the FileCrawler enters a subdirectory, it eventually needs to leave so that it can explore other files within the directory it came from. Think carefully about when backtracking is appropriate, and remember that your recursive calls will of your algorithm is structured correctly) backtrack on their own The algorithm must be recursive. If you don't have a step that performs the entire algorithm again with different input, then your algorithm isn't recursive. revise them. . Algorithm Implementation Once you've designed your algorithm, write out each step as a comment and try coding the comments. If your steps are vague or contain too many instructions, you may need to revise and break them into smaller pleces first Advice Don't try to modify the FileCrawler class. Your recursive method will be tested with my