USA: +1(669)289-8683 
Sign in
In this project, you will develop algorithms that find road routes through the bridges to travel between islands.
The input is a text file containing data about the given map. Each file begins with the number of rows and columns in the map considered as maximum latitudes and maximum longitudes respectively on the map. The character “X” in the file represents the water that means if a cell contains “X” then the traveler is not allowed to occupy that cell as this car is not drivable on water. The character “0” in the file represents the road connected island. That means if a cell contains “0” then the traveler is allowed to occupy that cell as this car can drive on roads.
The traveler starts at the island located at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upper left corner, and the goal is to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from an island is to move left, right, up, or down to an immediately adjacent cell that has road connectivity which means a cell that contains “0”. Moving off any edge of the map is not allowed.
Input: The map files
Output: Print paths as explicitly specified for all the functions in
Part A
,
Part B
, and extra credit on the console.
You should have single main function that calls all the required functions for Part A, Part B, and extra credit for all the 3 given input map files one by one.
Coded graph.h file for your reference and provided it for you to refer to and download on canvas. You do not have to use this file mandatory, but if you are struggling to even start the project then this should definitely make your life much easier.
Part A
Consider the following class map,
{
public:
map(ifstream &fin);
void print(int,int,int,int);
bool isLegal(int i, int j);
void setMap(int i, int j, int n);
int getMap(int i, int j) const;
int getReverseMapI(int n) const;
int getReverseMapJ(int n) const;
void mapToGraph(graph &g);
bool findPathRecursive(graph &g, stack
bool findPathNonRecursive1(graph &g, stack
bool findPathNonRecursive2(graph &g, queue
bool findShortestPath1(graph &g, stack
bool findShortestPath2(graph &, vector
void map::printPath(stack
int numRows(){return rows;
};
int numCols(){return cols;};
private:
int rows; // number of latitudes/rows in the map
int cols; // number of longitudes/columns in the map
matrix
matrix
vector
vector
};
1. Using the above class map, write function void map::mapToGraph(graph &g){…} to create a graph g that represents the legal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move between adjacent cells.
2. Write a recursive function findPathRecursive(graph &g, stack
3. Write a function findPathNonRecursive1(graph &g, stack
4. Write a function findPathNonRecursive2(graph &g, queue
The code you submit should apply all three findPath functions to each map, one after the other.
The map input files named map1.txt, map2.txt, and map3.txt can be downloaded from the canvas. Example of a map input file:710Start – 0XXXXXXXXX 00000000XX 0X0X0X0XXX 0X0X0X0000 XX0XXX0XXX X0000000XX XXXXXXX000Z – Destination
Part B
The shortest path on a map is a path from the start to the destination with the smallest number of intermediate islands, that is the path with the least number of intermediate “0”.
1. Write two functions findShortestPath1(graph &g, stack
Note: The use of the additional functions of class map is optional but highly recommended.
Extra Credit
1. Optimize Bellman-Ford algorithm to reduce the number of iterations and compare the runtime of the unmodified and modified algorithm for three given input maps. Your optimized Bellman-Ford algorithm should call map::print() function. It should also print the runtime of the unoptimized and optimized versions.
Thus, You should submit a single zip folder within which you need to have 4 files including, 1) a single “.cpp” code file that includes all the above-required functions called from a single main function, 2) a single “.h” header file, 3) README file with the compile and execution instructions, and 4) your pre-compiled “.exe” executable file. On top of your .cpp code file, .h header file, and README file, you need to mention your name as comments. You may have an additional PDF file if you want to narrate your additional observations about running the functions of this project, e.g., drawing the graph to compare the runtime and explain the results. All submitted code files must be named as “
Some header files you may need are following, that can be found in you header files zip folder available to you to download on Canvas.
#include
#include “d_except.h”
#include
#include
#include “d_matrix.h”
#include
#include
FAQ – Final Project Solution
Q1. I am confused about an apparent “matrix” data type mentioned in the assignment
instructions (matrix matrix). While none of the steps directly refer to this
“matrix” data type, I am confused to why it is in the class map at all, as “matrix” does not
seem to be a real data type in C++. Is there a specific “matrix” data type in C++ that I
am not aware of? Or is this “matrix” data type included in the assignment for some other
reason.
A1. “matrix” is defined in the header files made available to you as zip file to
download. This is to help you to save your graph as an adjacency matrix.
Q2. Should the graph be constructed in a particular way? Or is any form of a graph
acceptable? Currently, I have the graph struct set up as a vector of vertex structs, which
each have pointers to other vertices. I am unsure how much flexibility we are allowed to
have with this assignment.
A2. How to store your graph is the design decision you need to make in this
project thinking of the efficiency of the operations you will have to perform on
that graph. Adjacency matrix and Adjacency list are two most commonly used
ways as we discussed in class.
Q3. Are we allowed to change the names, parameters, or types of the required
functions or variables? (ie, can I name the function required in Part A: Step 3 to
findPathStack instead of findPathNonRecursive1, or make the function return a stack
instead of a boolean value). Is it possible, for example, to change the data type of the
stack in findPathRecursive, or to change the argument variable name in
findPathNonRecursive2.
A3. No, you cannot change the function names, arguments, and return type for
functions – mapToGraph, findPathRecursive, findPathNonRecursive1,
findPathNonRecursive2, print, findShortestPath1, and findShortestPath2. The use
of the other supplementary functions in the class is optional but highly
recommended. If you use them, then keep the function names the same.
Regarding the arguments and return types of supplementary functions, unless,
you have a solid reason for change and a better plan software design, do not
change. In case you change, then justify and explain your reason clearly as
comments in the code.
Q4. I am also confused about the two “print” functions mentioned in the class map (void
print(int,int,int,int); and void printPath(stack &s);). The assignment instructions
state to use the print function to print a sequence of correct moves; however, it is not
exactly clear which of the two print functions is being referred to in the instructions. In
addition, it is not exactly clear what the difference between the two functions is.
A4. printPath(stack &s) is supposed to Print the path in stack s, and print(int
goalI, int goalJ, int currI, int currJ) is supposed to print out the
visualization/simulation of a map, with the goal and current cells marked. Thus, in
each case, if a solution exists the solver should call the map::printPath() function
that should print a sequence of correct moves (Go left, Go right, Go down, Go up,
etc.). If no path from the start to the destination exists, the program should print,
“No path exists”. If a solution exists the solver should also simulate the solution
to each map by calling the map::print() function. Each function should return true
if any paths are found, and false otherwise. Your printPath function may call
function map::print( ) to print out a map visualization, with the goal and current
cells marked to show the progress.
Q5. In addition, the functions findPathNonRecursive2(graph &g, queue &moves)
and findShortestPath2(graph &, vector &bestMoves) store their sequences of
moves in a queue and vector respectively. For printing these two paths, can
we have an overloaded print function that accepts vectors and queues? Or should the
paths in the vector and queue be converted to a stack (via another function) in order for
all the functions to use the same print method?
A5. You got it right. Either of the above-mentioned approaches is acceptable.
Q6. I am also confused with how the graph data type is being implemented in the given
class map. As “map” is an object that is initialized with graph data from an input, one
would assume that the graph data would be stored within the map object, as any other
form of storing the data would be redundant if a graph was going to be made anyway
via mapToGraph. However, some functions take a graph as an input argument, which
implies that the graph should not be stored within the map class. At the same time
however, every path function – which is a function of class map – that uses the graph
accepts a graph as an input argument. As such, I am confused. It seems illogical for the
graph to be stored outside of the map object, as all the path functions in the map class
use the graph. At the same, some functions take a graph as an input argument, which
implies that the graph should not be stored within the map class. As such, I am
confused of the intention of the assignment regarding how the graph of a map be
handled.
A6. “map” is a class with public and private functions and data members as given
to you. Within class map you also have a public function named “map(ifstream
&fin)” that initializes a map by reading values from input file named fin. Finally,
your class map also contains a private data member of type “matrix” called
“matrix mapping”, which is to mapping from map (i,j) values to node index
values. You function mapToGraph( ) should create a graph g that represents the
legal moves in the map m. Graph g may be stored as an adjacency matrix or
adjacency list depending up what you think is a good design choice.
Q7. In the instructions, it says that we need to include #include “graph.h” I could not find
a header with this name, only “d_graph.h”. Or we need to create it? Since in the
submission instructions you ask us to submit “a single “.h” header file” what is this
header file and what should be in it? I’m getting errors if I use d_graph.h.
A7. The “graph.h” will be the header file that you need to create for your program.
This header file will have declarations of all your functions in one location and
then import this in your solution C++ code. You may or may not import d_graph.h
within your header file.
Q8. The goal is to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in
the lower right corner. But the “map1.txt”, “map2.txt”, and “map3.txt” files have the
character “Z” at the lower right corner. So, does this mean that reaching “Z” is the goal?
A8. Yes, correct. That’s exactly right. Your solver should reach the island located
at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner, which is signified
by character “Z” in the input files.
Q9. Can you please give an example of the expected output for the print( ) function?
A9. Let’s assume you input file map.txt is 2
4
0X0X
0000Z
then the expected output to print your initial map m using function
“m.print(m.numRows()-1,m.numCols()-1,0,0)” will be the following where “+”
represents your current status of car, “*” represents your final destination, and ”
” (space) represents the road,
+X X
*
Similarly, after your other functions such as “findPathRecursive”,
“findPathNonRecursive1”, “findPathNonRecursive2”, “findShortestPath1”,
“findShortestPath2”, etc. you need to call print() and your expected output will
look like following where you see the position of “+” simulates the solution to the
given map from its source to its destination,
Finding shortest path using BFS
Shortest path found
+X X
*
XX
+ *
XX
+ *
XX
+*
XX
*
Q10. Can you please give an example of the expected output of the printPath()
function?
A10.
Let’s assume you input file map.txt is 2
4
0X0X
0000Z
then, the expected output of the printPath function for the map while finding
shortest path using BFS (also refer the Q9) will be,
Finding shortest path using BFS
Shortest path found
“Go Down, Go Right, Go Right, Go Right”
7
10
OXXXXXXXXX
OOOOOOOOXX
OXOXOXOXXX
OXOXOXOOOO
XXOXXXOXXX
XOOOOOOOXX
XXXXXXXOOOZ20
20
OOOOOOOOOOOOOXOOOOOX
OXXXOXXXXXXXOXXOXXOX
OXXXOOOOOXXXOOOOXXXX
OXXXOXXXXXXXOXXXXOOX
OXXXOXXXXXXXOXXOOOXX
OOOOXXXOOOOOOOOOXOXX
OXXXXOXOXXXXXXXXXOXX
OOOOOOXOXOOOOOOOOOXX
XXXXXXXOXXOXXXXXXXXX
OOOOOOOOXXXXOOOOOXXX
OXXXOXXXXXXXOXXXOOOO
OXOXOXOOOOOOOXXXOXXO
OXOXXXOXOXXOXOOOOXXO
OOOOOOOXXXXXXOXXOXXO
XOXXXXXXOOOOXOXXOXXX
XOXOOXXOOXXOXOOXOOOX
XOXXOXXOXXXOXXXXXXOX
XOXXOOOOOXXOXXOOOOOX
XOOOOXXXXXXOXXOXXXXX
XOXXOXOOOOOOXXOOOOOOZ
20
20
OOOOOOOOOOOOOXOOOOOX
OXXXOXXOXXXXOXXOXXOX
OXXXOOOOOXXXOOOOXXXX
OXXXOXXXXXXXOXXXXOOX
OXXXOXXXXXXXOXXOOOXX
OOOOXXXOOOOOOOOOXOXX
OXXXXOXOXXXXXXXXXOXX
OOOOOOXOXOOOOOOOOOXX
OXXXXXXOXXOXXXXXXXXX
OOOOOOOOXXOOOOOOOXXX
OXXXOXXXXXXXOXXXOOOO
OXOXOXOOOOOOOXXXOXXO
OXOXXXOXOXXOXOOOOXXO
OOOOOOOXXXXXXOXXOXXO
XOXXXXXXOOOOXOXXOXXX
XOXOOXXOOXXOXOOXOOOX
XOXXOXXOXXXOXXXXXXOX
XOXXOOOOOXXOXXOOOOOX
XOOOOXXXXXXOXXOXXXXX
XOXXOXOOOOOOOOOOOOOOZ
EECE2560 Fundamentals of Engineering Algorithms
Department of Electrical and Computer Engineering
Style and Documentation Guidelines
All code you submit must meet the requirements listed below. The functions and declarations at
the bottom give examples of how your code should look.
• Each file should begin with a comment that explains what the file contains. The top of each
file should include your name and the problem set number.
• Your code and documentation should be no more than 80 columns wide. Text should also not
usually be wrapped around at a width of less than 80 columns. In other words, use the full
80 characters. Do not put function parameters or long expressions on separate lines unless
you have to.
• Each function must be documented as shown below. At the top of the function (or in the
prototype), precisely describe what the function does, what the input parameters are, and
what assumptions the function makes, if any. These comments should be placed immediately
after the function name or prototype. You do not need to document code in libraries that I
have given you.
• Within the code, put comments that describe how the function works.
• Put spaces on either side of arithmetic (⇤, /, +, ), logical (&&, ||, !), relational (=
, ==, ! =) and assignment operators (= + =, =, ⇤ =, / =), and the > operators.
• Put brackets { } on lines by themselves, and indent them as shown below.
• Avoid using global variables, except for certain constants. Global identifiers should be declared starting in the leftmost column. All other identifiers, including local variables, should
be indented at least 3 columns.
• All #include statements should be at the top of each file. Global variables should also be
placed at the top of each file.
• Comments on lines by themselves should be indented the same amount as the lines they refer
to, and should have a blank line before them. Multi-line comments usually should have an
empty space after them. For instance, instead of:
x = 0;
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// next code
use
x = 0;
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// next code
• if statements, for-loops, while-loops and do-while loops should be preceded by a blank line
and followed by a blank line (or a line with a bracket).
• Put spaces before, but not after, the arguments of for-loops, and put a space after the “if,”
“for,” and while keywords. For instance, instead of
for(int pos = size;pos>=index ;–pos)
use
for (int pos = size; pos >= index; –pos);
• Final brackets } that are more than about 10 lines from the initial bracket should be commented, as shown below.
• Comments within the class declarations (at the end of the lines) should be lined up as much
as possible.
• Do not put extra spaces between parentheses in expressions:
For example, instead of
while ( (x N) ),
use
while ((x N)).
• The commas separating the list of parameters in function calls and prototypes should be
followed by a space, as in the following:
void swap(int &x, int &y)
2
// Homework 1
Ningfang
Mi
Janki Bhimani
//
ningfang@ece.neu.edu
janki.bhimani@fiu.edu
//
// Main program file for homework 1. Contains declarations for Node,
// linkedListInsert, insert, and find.
//
#include “ListException.h”
#include
using namespace std;
typedef desired-item-type ItemType;
struct Node
// The basic Node type used in the linked list
{
ItemType item;
Node *next;
}; // end struct
void List::linkedListInsert(Node *headPtr, ItemType newItem)
// Inserts a new node containing item newItem into the list pointed
// to by headPtr.
{
int x,y;
float f = 1.2;
if ((headPtr == NULL) || (newItem < headPtr->item))
{
// base case: insert newItem at beginning
// of the linked list to which headPtr points
Node *newPtr = new Node;
if (newPtr == NULL)
{
cout
\\ getLength()+1.
{
success = bool( (index >= 1) && (index = index toward the end of the
// list (no shift if index == size+1)
for (int pos = size; pos >= index; –pos)
items[translate(pos+1)] = items[translate(pos)];
// insert new item
items[translate(index)] = newItem;
++size; // increase the size of the list by one
} // end if
} // end insert
ListNode * List::find(int index) const
// Locates a specified node in a linked list. Index is the number of the
// desired node. Returns a pointer to the desired node. If index < 1 or
// index > the number of nodes in the list, returns NULL.
{
if ((index < 1) || (index > getLength()))
return NULL;
else // count from the beginning of the list
{
ListNode *cur = head;
for (int skip = 1; skip < index; ++skip)
cur = cur->next;
return cur;
} // end if
} // end find
4
//
//
//
//
Header file TableH.h for the ADT table.
Hash table implementation.
Assumption: A table contains at most one item with a
given search key at any time.
#include “ChainNode.h”
#include “HashTableException.h”
typedef KeyedItem TableItemType;
class HashTable
{
public:
// constructors and destructor:
HashTable();
HashTable(const HashTable& table);
~HashTable();
// table operations:
virtual bool tableIsEmpty() const;
virtual int tableGetLength() const;
virtual void tableInsert(const TableItemType& newItem)
throw (HashTableException);
virtual bool tableDelete(KeyType searchKey);
virtual bool tableRetrieve(KeyType searchKey,
TableItemType& tableItem) const;
protected:
int hashIndex(KeyType searchKey); // hash function
private:
enum {HASH_TABLE_SIZE = 101};
// size of hash table
typedef ChainNode * HashTableType[HASH_TABLE_SIZE];
HashTableType table;
int Size;
}; // end HashTable class
// hash table
// size of ADT table
// End of header file.
5
Guidelines for Software Engineering Techniques
Specification: You must first understand exactly what the problem is that you are solving. You
may get an initial program specification from a customer or another non-technical person, so
it may at first be imprecise. Specification requires that you have a complete understanding of
many issues including: what the input data is, what types of data are valid, what sort of interface
the program will have, what input errors need to be detected, what assumptions are made, what
special cases need to be handled, what is the output, what will be documented, what changes
might be made after completion, etc. Note that the specification should not include the method
of solving the problem.
Design: After you know exactly what problem is to be solved, a solution to the problem can
be designed, encompassing both algorithms and abstract data types. For large programs, this is
usually broken down into well-defined smaller problems that can be solved using modules that
are reusable and (somewhat) independent. (For example, a sorting routine can be used by many
programs but, aside from the interface, is independent of them.) A module can be a single
function or a group of functions. The input, output, purpose, and assumptions of each module
should be specified. The design should be independent of the implementation.
Verification: It is possible, in some cases, to prove that an algorithm is correct. For example,
design test cases with different input data and validating the expected output with the output
of algorithm.
