Eric Roberts Handout #31CS106B April 29, 2009Section Handout #4More Recursion and Simple ClassesParts of this handout were written by Jerry Cain and David Borowitz.Problem 1. Creating Word Wreck TanglesSeveral summers ago, my colleague Jerry Cain discovered a dashboard element for hisGoogle Home Page that served up a new type of puzzle every week. One of thesepuzzles was the Word Wreck Tangle, and it looked like this:The goal of the game is to slide each of the 18 letters around the perimeter into the boardin such a way that you’re left with a grid of nine overlapping words—four across and fivedown. Here’s the solution:Here’s what I want to know! How do people find these boards in the first place? Aresome people so inventive that they can just see that scabs stacked on top of tacit on topof array and geese just so happens to give you five four-letter words as well? Is it reallythat obvious?Perhaps to some, but it needn’t be, because we have recursive backtracking and theprogrammatic ability to generate a word wreck tangle, see what it gives us, and thenpretend we didn’t use a computer but just found it own our own.– 2 –Your job here is actually a pretty tough one: write a recursive procedure that takes anempty Grid<char> (actually, it’s a Grid<char> of space characters), and populates itwith an assortment of letters that just happens to be four words across and five wordsdown. Here’s the prototype:bool CreateWreckTangle(Grid<char> & board, Lexicon & lex);If the top-level call to CreateWreckTangle returns true, then we can safely assume thatthe Grid<char> referenced by board was seeded with a solution that could be the goalboard of the puzzle. There’s no real reason to assume the grid is always 4 by 5, becauseit’s trivial to frame the implementation in terms of whatever the grid dimensions happento be. Here’s what my solution generated (the word stag is big today):You can assume you have access to:void AddPermutationOfAlphabet(Vector<char> & letters);It takes the specified Vector<char> and populates it with one of the 26! permutations ofthe alphabet. (Without it, your code would generate the same wreck tangle every time.)As it turns out, generating a board is often a very time consuming process. What couldyou do to speed up the search? In other words, what heuristics might you use—beyondcalling containsPrefix—to reduce the branching factor and/or identify bad decisionsmore quickly?Problem 2: Priority QueueThe standard queue from chapter 4 is a collection of elements managed in first-in/first-out(“FIFO”) manner. The first element added to the collection is always the first elementextracted, the second comes out second, and so on.In some cases, a FIFO strategy may be too simple. A hospital emergency room, forexample, needs to schedule patients according to priority. A patient who arrives with amore serious problem should preempt others even if they have been waiting longer. Aqueue that implements the notion that some elements take precedence over others iscalled a priority queue. When you add elements to the queue, you also specify anumeric priority; when you remove elements from the queue, you always dequeue thehighest priority item first. For consistency with the way we talk about priorities inEnglish, lower priority numbers correspond to higher priorities. Thus, an element that isenqueued with priority 1 will be dequeued before any elements with priority 2.– 3 –Priority queues are useful in a variety of applications. You can, for example, use apriority queue to implement sorting. All you need to do is insert the values into a priorityqueue and then extract them one by one to get them in sorted order. At the end of thequarter, you will use priority queues on Assignment #6 as part of an algorithm for findingshortest paths.For this section problem, your first task is to implement the template class PQueue, whichhas the following definition:template <typename ElemType>class PQueue { public: PQueue(); ~PQueue(); int size(); bool isEmpty(); void clear(); void enqueue(ElemType elem, int priority); ElemType dequeue(); ElemType peek(); private: // Add this section after you choose the data structure};Note that PQueue is a template class in which the element type is specified using theplaceholder ElemType, just like the original version of Queue. In fact, the only differencein the interfaces is that the enqueue method for the PQueue class takes an integer toindicate the priority.Although there are more efficient implementation strategies for implementing priorityqueues, the strategy we recommend for this section is to store the elements in an arrayalong with their priority. Elements are removed from the end of the array, just as theywere in the stack implementation we did in class. To preserve the semantics of a priorityqueue, new elements must be added to the array in priority order, with high priority itemsat the end and low priority items at the beginning.Before you jump into writing code, you should give some thought to the following points:• You will need to store each priority alongside its element so that you can figure outwhere to put each new value.• You need to think about what private variables and types you will need to store thepriority queue internally.• Don’t use Vector. For maximum guaranteed efficiency, you’ll need to use your ownmemory management.• Recall that the syntax for defining a method for a template class istemplate <typename ElemType>ElemType PQueue::dequeue() { // Fill in your implementation here}Once you have implemented the priority queue interface, answer the following thoughtquestions:– 4 –1. In terms of N, the number of elements in the priority queue, what is the big-O runtimeof each of the methods of the PQueue class?2. Consider an implementation where instead of maintaining the elements in sortedorder at insertion time, elements are stored unsorted in the vector. How does the big-O runtime of each method change?3. Suppose you know in advance that all the priorities will be confined to a small rangeof values, say the values 0-9. Can you modify your PQueue implementation toguarantee O(1) runtime for both enqueue and dequeue, particularly if you don’tspecify how elements with the same priority are stored in the