For this project you need to develop
1. A complete working algorithm with explanation of each line in the Pseudocode.
2. Writing a program in C++ based on your Algorithm with comments for each line of code.
Deliveries
1. A complete working algorithm with explanation of each line in the Pseudocode must be
typed using Microsoft word document , Save the document as (group No_Your name_algorithm)
2. Writing a program in C++ based on your Algorithm with comments for each line of code. You
need to upload the source code in addition we need you to copy your code to Note pad and
save it as your (group No_Your name_projectcode)
NOTE:
I. Late submissions will not be accepted.
Project narrative
When searching for a sequence of fights between cities, you must take into account the
possibility that the algorithm will make wrong choices. For example, the algorithm must
be able to backtrack when it hits a dead end, and you must eliminate the possibility that
the algorithm will cycle.
This project considers an organized way to make successive guesses at a solution. If a particular guess
leads to a dead end, you back up to that guess and replace it with a different guess. This strategy of
retracing steps in reverse order and then trying a new sequence of steps is called backtracking .You can
combine recursion and backtracking to solve the following problem. You may use stack also in your
solution.
Searching for an Airline Route
This project will introduce you to a general type of search problem. In this particular project, you
must find a path from some point of origin to some destination point. We shall solve this problem by
using recursion.
The High Planes Airline Company (HPAir) wants a program based on Algorithm to process customer
requests to fly
from some origin city to some destination city. So that we can focus on recursion, we will simplify the
problem: For each customer request, just indicate whether a sequence of HPAir flights from the origin
city to the destination city exists.
Imagine three input text files that specify all of the flight information for the airline as follows:
MCIS 6204 Data Structures and Algorithm
Term Project Specification
(Up to 5 students per team)
(All documentation Due: 11/21/2016)
(Term Project technical Report Due: 11/21)
( Term project implementation Due:11/21)
• The names of cities that HPAir serves
• Pairs of city names, each pair representing the origin and destination of one of HPAir’s flights
• Pairs of city names, each pair representing a request to fly from some origin to some
Destination
The program should then produce output such as
Complete the solution to the HPAir problem. The input to the program consists of three text fi les, as
follows:
Request is to fly from Providence to San Francisco.
HPAir flies from Providence to San Francisco.
Request is to fly from Philadelphia to Albuquerque.
Sorry. HPAir does not fly from Philadelphia to Albuquerque.
Request is to fly from Salt Lake City to Paris.
Sorry. HPAir does not serve Paris.
Representing the flight data. The flight map in Figure 1 represents the routes that HPAir flies.
An arrow from city C1 to city C2 indicates a flight from C1 to C2 . In this case, C2 is adjacent to C1 and
the path from C1 to C2 is called a directed path . Notice that if C2 is adjacent to C1 , it does not follow
that C1 is adjacent to C2 . For example, in Figure 1 , there is a flight from city R to city X , but
not from city X to city R .
The nature of the search. When processing a customer’s request to fly from some origin city to
some destination city, you must determine from the flight map whether there is a route from the origin
to the destination. For example, by examining the flight map in Figure 1 , you can see that a customer
could fly from city P to city Z by flying first to city W , then to city Y, and finally to city Z; that is,
there is a directed path from P to Z : P→W , W→Y , Y→Z. Thus, you must develop an algorithm that
searches the flight map for a directed path from the origin city to the destination city. Such a path
might involve either a single flight or a sequence of flights. The solution developed here performs an
exhaustive search . That is, beginning at the origin city, the solution will try every possible sequence
of flights until either it finds a sequence that gets to the destination city or it determines that no such
sequence exists.
First consider how you might perform the search by hand. One approach is to start at the origin
city C0 and select an arbitrary flight that departs from the origin city. This flight will lead you to a new
city, C1 . If city C1 happens to be the destination city, you are done; otherwise, you must attempt to get
from C1 to the destination city. To do this, you select a path to travel out of C1 . This flight will lead you
to city C2 . If C2 is the destination, you are done; otherwise, you must attempt to get from C2 to the
destination city, and so on.
A recursive strategy. To fly from the origin city to the destination city by first flying from the origin
city to a city C and then by flying from C to the destination has a distinct recursive flavor. We can restate
this strategy as follows:
To fly from the origin to the destination:
Select a city C adjacent to the origin
Fly from the origin to city C
if (C is the destination city )
Terminate— the destination is reached
else
Fly from city C to the destination
Consider the possible outcomes of applying the previous strategy:
1. You eventually reach the destination city and can conclude that it is possible to fly from the
origin to the destination.
2. You reach a city C from which there are no departing flights.
3. You go around in circles. For example, from C1 you go to C2 , from C2 you go to C3 , and from C3
you go back to C1 . You might continue this tour of the three cities forever; that is, the algorithm
might not terminate.
If you always obtained the first outcome, everyone would be happy. This outcome corresponds to a
base case of the recursive algorithm. If you ever reach the destination city, no additional problems of the
form “fly from city C to the destination” are generated, and the algorithm terminates. However, because
HPAir does not fly between all pairs of cities, you certainly cannot expect that the algorithm will always
find a path from the origin city to the destination. For example, if city P in Figure 1 is the origin city
and city Q is the destination city, the algorithm could not possibly find a path from city P to city Q .
Even if there were a sequence of flights from the origin city to the destination, it would take a bit
of luck for the previous strategy to discover it the algorithm would have to select a “correct” flight at
each step. For example, even though there is a way to get from city P to city Z in Figure 1 , the algorithm
might not find it and instead might reach outcome 2 or 3.
You thus need to make the algorithm more sophisticated, so that it always finds a path from the
origin to the destination, if such a path exists, and otherwise terminates with the conclusion that there
is no such path.