Eric Roberts Handout #23CS106B April 20, 2009Section Handout #3—Recursion and Big OParts of this handout were written by Julie Zelenski and Jerry Cain.The purpose of this section is to give you some additional practice solving recursiveproblems and to test your understanding of complexity classes and Big-O notation.Problem 1. Shortest path (Chapter 7, exercise 2, page 273)In many mazes, there are multiple paths. For example, the diagrams below show threesolutions for the same maze:Θ××××××××××××××××××××××××××××××××××××××××××××××××Θ××××××××××××××××××××××××××××××××××××××××××××××××Θ××××××××××××××××××××××××××××××××××××××××××××××××××××××××length = 13 length = 13length = 15None of these solutions, however, is optimal. The shortest path through the maze has apath length of 11:Θ××××××××××××××××××××××××××××××××××××××××Write a functionint ShortestPathLength(pointT pt);that returns the length of the shortest path in the maze from the specified position to anyexit. If there is no solution to the maze, ShortestPathLength should return the constantNO_SOLUTION, which is defined to have a value larger than the maximum permissiblepath length, as follows:const int NO_SOLUTION = 10000;Problem 2. Filling a region (Chapter 7, exercise 6, page 275)Most drawing programs for personal computers make it possible to fill an enclosed regionon the screen with a solid color. Typically, you invoke this operation by selecting apaint-bucket tool and then clicking the mouse, with the cursor somewhere in yourdrawing. When you do, the paint spreads to every part of the picture it can reach withoutgoing through a line.For example, suppose you have just drawn the following picture of a house:– 2 –If you select the paint bucket and click inside the door, the drawing program fills the areabounded by the door frame as shown at the left side of the following diagram. If youinstead click somewhere on the front wall of the house, the program fills the entire wallspace except for the windows and doors, as shown on the right: In order to understand how this process works, it is important to understand that thescreen of the computer is actually broken down into an array of tiny dots called pixels.On a monochrome display, pixels can be either white or black. The paint-fill operationconsists of painting black the starting pixel (i.e., the pixel you click while using the paint-bucket tool) along with any pixels connected to that starting point by an unbroken chainof white pixels. Thus, the patterns of pixels on the screen representing the preceding twodiagrams would look like this: Write a program that simulates the operation of the paint-bucket tool. To simplify theproblem, assume that you have access to the enumerated type– 3 –enum pixelStateT { WHITE, BLACK };and the following functions:pixelStateT GetPixelState(pointT pt);void SetPixelState(pointT pt, pixelStateT state);bool OutsidePixelBounds(pointT pt);The first function is used to return the state of any pixel, given its coordinates in the pixelarray. The second allows you to change the state of any pixel to a new value. The thirdmakes it possible to determine whether a particular coordinate is outside the pixel arrayaltogether, so that the recursion can stop at the edges of the screen.Problem 3. Generating a knight’s tour (Chapter 7, exercise 7, page 276)In chess, a knight moves in an L-shaped pattern: two squares in one direction horizontallyor vertically, and then one square at right angles to that motion. For example, the knightin the upper right side of the following diagram can move to any of the eight squaresmarked with a black cross:The mobility of a knight decreases near the edge of the board, as illustrated by the bottomknight, which can reach only the three squares marked by white crosses.It turns out that a knight can visit all 64 squares on a chessboard without ever moving tothe same square twice. A path for the knight that moves through all the squares withoutrepeating a square is called a knight’s tour. One such tour is shown in the followingdiagram, in which the numbers indicate the order in which the squares were visited:52 56 54 2244 4 14 657 53 23 2547 45 5 1348 46 26 1258 50 24 2043 3 41 751 55 21 1536 42 62 1624028859 37 33 1949 27 11 2938 32 10 3060 34 18 6413931935 61 63 17Write a program that uses backtracking recursion to find a knight’s tour.– 4 –Problem 4. Generating multiword anagramsEvenn before we got to recursion, I showed how it was possible to use the map datastructures to find all anagrams of a given word, which means a word that has the sameletters possibly in a different order. Recursion makes it possible to do much more withthe anagram idea. In particular, you can write programs that extend the idea of anagramsto multiple words. Dan Brown used several multiword anagrams as clues in his 2003best-selling thriller The Da Vinci Code, so that (if you ignore spaces) you discover thato draconian devil → leonardo da vincioh lame saint → the mona lisaso dark the con of man → madonna of the rocksYour job in this problem is to write a functionbool FindAnagram(string letters, Lexicon & english, Vector<string> & words);that takes a string of letters with all spaces and punctuation removed, the well-wornlexicon of English words, and a vector to hold the words of the generated anagram. Assoon as FindAnagram discovers a series of English words that are an anagram of thespecified letters, it should return true with those words stored in the vector. If noanagrams exist, FindAnagram should return false. To avoid returning anagrams thatconsist of boring short words, you should also include a constant in your implementationsetting the minimum size of a word. The following sample run was generated with aminimum word length of four: Anagram Generator: Welcome -------------------------- Please enter a string of letters: ericroberts >> bisect error Please enter a string of letters: leonardodavinci >> rancid avoid leno Please enter a string of letters: davidborowitz >> bozo virid dawt Please enter a string of letters: fredwulff >> drew fluff Please enter a string of letters: xyzzy Nothing. :( Please enter a string of letters:Problem 5. Complexity classesChapter 8 introduces several different