Programming Exercise III: My bus itinerary: Part III

Programming Exercise III: My Bus Itinerary: Part III
(Industry-Level, Second-to-None Comprehensive Specifications)

Absolutely no copying others’ works
Development Requirements
When start developing the exercise, follow the requirements below:

Have to use the Java language mainly and may use Perl or other languages to connect the Web to Java.

All software requires to include user interfaces, and three approaches are available for user interface construction for this exercise. The grading would not be affected by the approach chosen, but user-friendliness will be heavily considered.

Internet-enabled interface: It is the most popular one and a trend for current IT systems. The system entry page must be located at http://undcemcs02.und.edu/~user.id/280/3/ and all pages must be hosted by http://undcemcs02.und.edu/~user.id/ .
Graphical user interface: It is the most difficult one (e.g., using AWT, Abstract Windowing Toolkit).

Text user interface: It is the least favorite one and an obsolete method. An example is a 1-2-3 system like

  Start Using the System.
  1. Enter routes
  2. List all routes
  3. Show a specific route
  4. Reset the system
  5. Exit
  Select (1/2/3/4/5): 3¶
            ⇓
  Show a specific route.
  Enter the route: 2¶
            ⇓
  Route 2: South Middle School, Choice Fitness, Hugo, Columbia Mall, Altru, UND, Ralph, BK, Aerospace

  1. Enter routes
  2. List all routes
  3. Show a specific route
  4. Reset the system
  5. Exit
  Select (1/2/3/4/5): 2¶
            ⇓
           ...

Due Date and Submission Methods
Due on or before Monday, November 15, 2021:

For the above Approach a, send the password for displaying the source code online to the instructor at wenchen@cs.und.edu (only one password for all interfaces and all exercises).

For the above Approaches b and c,
- Send an email to the instructor at wenchen@cs.und.edu to set up an appointment to demonstrate your exercise to the instructor individually, so misunderstanding would be minimized. The instructor will prepare a set of test data to be used by all students.
  (Zoom at https://und.zoom.us/j/2489867333 will be used for demonstration.)
- Submit all source code via Blackboard.

Objective
This is the third part of the problem of finding a bus itinerary, and its objective is to have students practice Java programming. Keep in mind that the only effective way to learn a programming language is practicing, instead of studying concepts or writing some testing programs.

No pain, no gain 😂

Requirements
The requirements have to be followed precisely even though the developers may not agree with them. This is the third part of a bus-itinerary problem, which is to find the shortest bus itinerary. The exercise includes the following requirements:

(Violated: -20%)
The input data should not be erased unless specified, so the testing could be applied many times.

(Entering bus routes (given): 05%) (Given code)
Enter routes one by one. A route is a bi-directional sequence of bus stops, unique names, separated by commas such as

South Middle School, Choice Fitness, Rydell, Hugo, Columbia Mall, Altru, UND, Ralph, Burger King

(or South Middle School ⇔ Choice Fitness ⇔ Rydell ⇔ Hugo ⇔ Columbia Mall ⇔ Altru ⇔ UND ⇔ Ralph ⇔ Burger King)

Also, a bus stop can not be repeated in a sequence.

(Listing all routes: 05%) (from Exercise I)
List the bus-stop sequences of all bus routes.

(Listing a specific route: 05%) (from Exercise I)
List the bus-stop sequence of a specific bus route.

(Finding the shortest itinerary: 70%)
By giving a start stop (like Altru) and a final stop (like Menards), give the shortest bus itinerary which is a sequence of bus stops (and bus routes) such as

Altru (3) (start) ⇒ UND (3) ⇒ Ralph (3) ⇒ Burger King (3|1) ⇒ Aerospace (1) ⇒ Alerus Center (1) ⇒ Menards (1) (final)

The itinerary is the one with the following features:

Commence with the start stop and conclude with the final stop.
It is the shortest itinerary; i.e., the one with the lowest number of bus stops among all valid itineraries.
An itinerary is a one-way sequence of bus stops, and no bus stops could be repeated.
A passenger can only change her/his bus route at a bus transfer stop which is passed by more than one route, and at most 2 routes could be taken in an itinerary.
A bus route could only be taken once.
Display “Not found!” if no itinerary is found.

Examples are given next:

Six routes are as follows:

South Middle School, Motel 8, Hugo, Columbia Mall, Altru, KFC, BK, Alerus Center, Ralph
Discovery Elementary School, Target, Menards, Aerospace, UND, Union, YMCA, Starbucks, City Hall
Subway, Choice Fitness, McDonalds, Columbia Mall, Altru, ACME, Ralph, BK, Aerospace, Scheels
Union, City Hall, Discovery Elementary School, Menards, Pizza Hut, Canad Inns, Walmart
McDonalds, Choice Fitness, Target, Walmart, UND, Scheels, Subway, Red Lobster, Aerospace
Starbucks, BK, Menards, Alerus Center, Ralph, Union, YMCA

Six queries are as follows:

Walmart to Starbucks: Walmart (5) ⇒ UND (5|2) ⇒ Union (2) ⇒ YMCA (2) ⇒ Starbucks (2)
Altru to YMCA: Altru (3) ⇒ ACME (3) ⇒ Ralph (3|6) ⇒ Union (6) ⇒ YMCA (6)
Scheels to Hugo: Scheels (3) ⇒ Aerospace (3) ⇒ BK (3|1) ⇒ KFC (1) ⇒ Altru (1) ⇒ Columbia Mall ⇒ Hugo (1)
Canad Inns to Starbucks: Canad Inns (4) ⇒ Pizza Hut (4) ⇒ Menards (4|6) ⇒ BK (6) ⇒ Starbucks (6)
Target to Hugo: Not found!
Canad Inns to Altru: Not found!

(Instructor’s requirements: 15% total)
Other than the above system requirements, the instructor has the following requirements:
- (User-friendliness: 10%) User-friendliness will be heavily considered when grading. In the past, some exercises were awkward, which made the grading or browsing difficult.
- (System reset (given): 05%) (Given code) The system can be reset, which is to clear all data stored in the database, files, or any data structure, so the instructor can test the system by using only his own test data. That is the system has to include a button such as “Clear system” at the system entry page.

Programming Hints
The four essential components of software are (i) algorithms, (ii) data structures, (iii) programming languages, and (iv) code, where algorithms are the most critical one. Finding a best bus itinerary is very complicated, and is most likely an NP-complete problem, which may not be solved in polynomial time. That is you have to find an approximation method to solve the problem because if it is not carefully planned, a brute-force or exhaustive method may take infinite time to find the answer. However, a brute-force or exhaustive method may just work well for a small amount of data.

This exercise is made simple on purpose, so it is not an NP-complete problem. Using appropriate data structures for this exercise could save a great deal of effort from you. An example of using the dynamic array ArrayList could be found at A travel-agent case study.

A User Interface
An example of the exercise’s interface is shown below:

Plagiarism-Proof
If the web interfaces are used, the instructor has the following requirements. It is for the instructor to find any plagiarism. Each interface includes a button “Display source,” which is to list ALL the source code for implementing the functions of this interface. Only one password is for all exercises and interfaces. The system will be highly suspected if fail to implement this button. The source code will be studied carefully for any suspected plagiarism. Besides, the exercise is suspicious if the results are substantially different from the assumed results from the code. The interface can be found from here.

~/public_html/course/280/exercise/3/check.html

Password: Interface:

Evaluations
The following features will be considered when grading:

Specifications:
- The instructor (or your assumed client) has given the exercise specifications as many details as he possibly can. If you are confused about the specifications, you should ask in advance. Study the specifications very carefully. No excuses for misunderstanding or missing parts of the specifications after grading.
- The specifications are not possible to cover every detail. You are free to implement the issues not mentioned in the specifications, but the implementations should make sense. Implemented functions lacking of common sense may cause the instructor to grade your exercise mistakenly, and thus lower your grade.
- The exercise must meet the specifications. However, exercises with functions exceeding the specifications will not receive extra credits.

Grading:
- This exercise will not be graded if the submission methods are not met. Students take full responsibility if the website/system is not working.
- A set of test data will be used by all students. The grades are primarily based on the results of testing. Other factors such as performance, programming styles, algorithms, and data structures will be only considered minimally.
- After the data is entered, it should NOT be erased unless specified.
- Before submitting the exercise, test it comprehensively. Absolutely no extra points will be given after grading.
- This course is about the Java language, so Java should be used to implement all functions, except the functions related to web (like connecting the Web to Java by using Perl or PHP).
- The total weight of all four exercises (06%, 09%, 12%, and 13%, respectively) is 40% of the final grade.
- If not specified, no error checking is required; i.e., you may assume the input is always correct for that case. For example, the bus stops entered will always be unique names.
- Feel free to design your own interfaces; user-friendliness will be heavily considered; each function/button will be tested extensively; and from the source code submitted, the programs will be examined.
- The newest Firefox browser will be used to grade exercises. Note that Internet Explorer, Edge, Chrome, and Firefox are not compatible. That is your exercises may work on the IE, Edge, or Chrome but not Firefox.
- The systems have to be active until the end of this semester. They will be re-checked for plagiarism from time to time.
- The instructor will inform you the exercise evaluations by emails after grading.

Comments:
- The exercises are related, but you are NOT allowed to submit one exercise to cover two or more exercises.
- Make the exercise work first. Do not include extra features, such as fancy interfaces, in the beginning. By the way, you will not receive credits for the extra features.
- Time management is critical for software development. If you are not able to complete the exercise, display whatever you have accomplished, so the instructor can give partial credit to your exercise.
- One way to build a website/system from scratch is to design the user interfaces first and then implement the system button by button or step by step. By doing this way, it could simplify the construction. The recommended construction steps are
  1. Examine the specifications very carefully.
  2. Build the user interfaces (Java or Web including HTML, CSS, and JavaScript).
  3. Implement the system button by button (Java or Web including Java and Perl).
  4. Test the exercise thoroughly.