Data Structures of Technology in The Current Century Project

https://online.fiu.edu/videos/?vpvid=c82dbc87-819f…

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.

These are the concepts, data structures, functions and algorithms we’ve learned to add to project:

-recurssion and backtracking

-overloading

-stacks

-queues

-linked lists

-bubble sort

-insertion sort

-selection sort

-merge sort

-quick sort

-heap sort

-tree traversal

-binary search tree

-hashing and hash tables

-graph traversal – Depth First Search

-graph traversal – Breadth First Search

-Dijkstra’s Algorithm

-Bellman Ford Algorithm

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
u o t
e m r
g s b
d f q
d g n
q t j
s b h
o o r
y e j
v n f
d e t
z s c
s p a
h x p
m
e
w
t
e
e
r
y
e
n
a
n
k
q
p
k
u
t
d
h
m
q
s
n
a
k
e
q
n
i
u
i
u
a
r
e
q
f
m
c
m
l
c
a
z
a
t
h
t
c
i
a
u
j
w
k
a
d
w
u
s
n
i
q
h
u
w
s
f
j
n
t
c
c
t
l
m
d
k
f
b
d
o
t
o
c
r
n
g
w
m
o
t
i
v
a
t
e
d
e
c
c
y
s
x
o
o
n
r
i
v
p
a
d
k
r
u
l
f
b
q
t
r
a
m
s
s
r
n
n
v
n
o
c
g
y
w
m
a
u
p
b
e
s
b
r
k
t
i
m
r
w
p
y
v
c
a
r
a
w
p
i
g
l
r
c
p
h
o
i
l
j
e
p
p
c
q
n
h
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 returns 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
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 assignment. 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
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.
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