This assignment is in C++. Please just do as simple as the sample attachedSubmit the PDF document of your Project Statement. "Project Statement - Sample1" and "Project Statement - Sample2" in Project Module can be used as an example of expectations from your submission. Ensure that the problem statement that you submit needs to be unique and definitely not the same as the samples given to you. Your project statement will be anonymously peer-reviewed, so do not include your personal details such as your name inside the PDF you submit.
Your Project Statement should clearly describe the following,
1. A general explanation of the problem, expected input, and output.
2. Part A - Explaining the data structures and functions required to approach the solution to the problem.
3. Part B - Explaining the algorithms that can be used to program the functions mentioned in Part A, and the techniques to improve the efficiency of these algorithms.
Sample Project Statement II In this project, you will develop algorithms that find paths through a maze. The input is a text file containing a collection of mazes. Each maze begins with the number of rows and columns in the maze and a character for every cell in the maze. A cell contains a space if the solver is allowed to occupy the cell. A cell contains X if the solver is not allowed to occupy the cell. The solver starts at cell (0,0) in the upper left, and the goal is to get to cell (rows-1, cols-1) in the lower right. A legal move from a cell is to move left, right, up, or down to an immediately adjacent cell that contains a space. Moving off any edge of the board is not allowed. Part a Functions to handle file I/O and a complete graph class, are included as part of the assign- ment. In the printout of the graph, the current cell is represented by + and the goal cell is represented by *. Add functions that: 1. Create a graph that represents the legal moves between cells. Each vertex should represent a cell, and each edge should represent a legal move between adjacent cells. 2. Write a recursive function findPathRecursive that looks for a path from the start cell to the goal cell. If a path from the start to the goal exists, your program should print a sequence of correct moves (Go left, go right, etc.). If no path from the start to the goal exists, the program should print, No path exists. Hint: consider recursive-DFS. 3. Write a function findPathNonRecursive that does the same thing as in 2, but without using recursion. Hint: consider either stack-based DFS or queue-based BFS. The code you submit should apply both findPath functions to each maze, one after the other. If a solution exists, the solver should simulate the solution to each maze by calling the maze::print() function after each move. Example of a maze input file: 7 10 OXXXXXXXXX OOOOOOOOXX OXOXOXOXXX OXOXOXOOOO XXOXXXOXXX XOOOOOOOXX XXXXXXXOOOZ Part b A shortest path in a maze is a path from the start to the goal with the smallest number of steps. Write two functions findShortestPath1 and findShortestPath2 that each find a shortest path in a maze if a path from the start to the goal exists. The first algorithm should use a breadth-first search. The second algorithm should use Dijkstra algorithm for shortest paths. In each case, if a solution exists the solver should simulate the solution to each maze by calling the maze::print() function after each move. Each function should return true if any paths are found, and false otherwise. 2 Sample Project Statement I Write a program that solves a word search puzzle. The program reads an n x n grid of letters from a file and prints out all the words that can be found in the grid. Words can be found in the array by starting from any letter and reading left, right, up, down, or along any of the four diagonals. Words can also wrap around the edges of the array. Words must be at least 5 characters long. The list of k possible words is included in the file dictionary. Several sample word search puzzles are also provided. The goal is to find an algorithm that solves this problem that runs as quickly as possible for large n and k. Part a 1. Implement a class called dictionary that reads the words from the dictionary file and stores them in a vector, and which includes: (a) a function to read the words from the dictionary file, (b) an overloaded output operator to print the word list, (c) a function that sorts the words using selectionsort, (d) a function to handle word lookups using binary search. 2. Implement a class called grid that reads the letters in the grid from a file and stores them in a matrix. 3. Implement a global function findMatches() that is passed the dictionary and the grid as parameters and which prints out all words that can be found in the grid. 4. Implement a global function search() which reads the name of the grid file from the keyboard and prints out all words from the word list that can be found in the grid. 15 15 n y d m k u a s l m o q y r c u o t e u i t n m o o t w w p e m r w t u h i d t n r m p h g s b t d a t q k i r a a y o d f q e h r c h f v i m u v i d g n e m e i u b a v s p c l q t j r q q a w d t p s b a j s b h y s f u s o e a r e r e o o r e n m j f t d d n s a p y e j n a c w j o e k n b w p v n f a k m k n c c r v r p c d e t n e l a t r c u n k i q z s c k q c d c n y l o t g n s p a q n a w c g s f c i l h h x p p i z u t w x b g m r a Part b In this part, solve the word search puzzle by using the quicksort algorithm and the heapsort algorithm to sort the words in the dictionary. 1. Implement a member function of dictionary that sorts the words using quicksort 2. Implement the template class heap
that stores objects in a heap of type vector, and which includes: (a) functions parent(int), left(int), right(int), and getItem(int n) which re- turns the nth item in the heap, (b) for a max-heap, functions initializeMaxHeap(), maxHeapify(), and buildMaxHeap(), (c) function heapsort(). 3. Implement a member function of dictionary that sorts the words using heapsort. Since the heap is only used to sort the word list, you can declare the heap within the dictionary::heapsort function, copy the unsorted words into the heap, sort the words, and then copy the words out. Then the dictionary::binarySearch function can be used to look up words. 4. Modify the global function search(int) which reads the name of the grid file from the keyboard and prints out all words from the word list that can be found in the grid. The integer parameter is used to select the sorting algorithm used. 2