DataStructures.

[Aakanksha]

Case Study MV Taxi

Overview

Transportation in and out of the St. Joseph, Maracas Valley continues to be a hassle for

daily non-driving commuters. Commuters fall into three categories students, residents

or workers. It has been observed that during the months of September to December

and January to May, a large portion of the commuting population consist of students

and employees of the university based in the valley.

In the absence of a University based solution to the transportation problem, twenty-five

(25) taxi drivers have formed themselves into a company – MV Taxi. Each participating

taxi driver is registered and holds a valid permit from the Trinidad and Tobago Licensing

Authority.

To ensure an efficient service is provided to customers and to maximize profits, the

company is determined to use software applications as a major part of their operations

which will provide services from scheduling to managing of fuel reserves and offering

emergency help.

Over the semester, the problem sets and project will be focused on creating simple

applications for MV Taxi which will not only provide practical experience with the data

structures discussed, but also provide you with a real world example.

Driver & Vehicle Data

MV Taxi keeps the following information about drivers and vehicles:

ï‚· Driver license number

ï‚· Driver experience novice or experienced

ï‚· Place where driver lives

ï‚· Driver status six status values: unavailable, on break, working, free, will

be free in 5/10 minutes, goes home

ï‚· Vehicle permit number

 Type of vehicle – cab, minivan, luxury

ï‚· Vehicle fuel capacity

ï‚· Vehicle license plate number

 Vehicle scanner number – scanner used for prepaid cards

ï‚· Capability to complete special jobs

Services

Taxi services are provided to customers via an order/pickup system. For each order

received the following information is collected:

ï‚· Place of pick-up and drop

ï‚· Kind of order customers are able to book two kinds of orders urgent or

booked in advance.

ï‚· Type of service – three kinds of services are provided cab, minivan or luxury

ï‚· Special Requirements – child seats, requiring transportation of pets, services for

the disabled or elderly

In the pickup system, commuters use the limited taxis that are parked in the designated

taxi stand in Curepe and these operate like the normal taxi service currently available.

On entry customers indicate their drop off point and the taxi leaves the stand when it is

full.

Customers can prepay for services or pay on delivery of service. Commuters can

register specially with the company to receive a prepaid service card. The card is

scanned each time the commuter uses the service and the appropriate amount is

deducted. Cards can be topped up either online or at the company office.

Question 1 (AVL and 2-3-4 Trees)

Consider the sequence of keys (5,16,22,45,2,10,18,30,50,12,1). Draw the result of inserting entries with these keys (in the

given order) into

(a) An initially empty AVL tree

(b) An initially empty 2-3-4 tree

Question 2 (Heaps)

When MV Taxi initially begins operation, taxis will be scheduled on a first come first serve basis for orders and on the taxi stand.

Driver priority is determined based on the time the driver indicates his status as either free or will be free in 5/10 minutes. The time

is converted into an integer which is used to determine driver priority.

Create a very simple application that uses a heap and the data provided in the two files driverStatus.txt and currentOrders.txt. to

print out a list of drivers and the assigned order for the dispatching clerk. The list should have the format shown in the example below.

Service_Requester Contact_Number Pick_Up_Location Drop_Location Assigned_Driver

Mitch Singh 345-9758 16 Francis Lane, Tunapuna

Question 1 (Hash Functions)

A. What would be a good hash code for a customer prepaid taxi – card, which is a

string of numbers and letters of the form “9XX9999,” where a “9” represents a

digit and an “X” represents a letter?

B. Draw the 11-entry hash table that results from using the hash function,

h(i) + (2i + 5) mod 11

to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions

are handled by chaining.

C. What is the result of part B, assuming collisions are handled by quadratic

probing?

Question 2 (Hash Tables)

In the further development of the taxi scheduling and information system, MV Taxi

wants to have quick and easy access to the information that pertains to a driver, vehicle

and orders. Three separate hash tables will be used for the temporary storage of the

data while permanent storage is implemented using files.

You are to create three text files with at least ten (10) records each with data pertaining

to the driver, vehicles and orders as given previously. Provide an application that reads

the data from the files and facilitates the following queries:

(a) Given a drivers license number, print a report with the following details:

ï‚· Driver license number

ï‚· Place where driver lives

ï‚· Driver experience novice or experienced

ï‚· List of vehicle permits registered to the driver

(b) Given a vehicle permit number, print a report with the following details:

 Type of vehicle – cab, minivan, luxury

ï‚· Vehicle fuel capacity

ï‚· Vehicle license plate number

 Vehicle scanner number – scanner used for prepaid cards

 Capability to complete special jobs – list all capabilities

(c) Given the type of service and special requirements from a customers order, print

a list of all the vehicle license plate numbers th

[Author]

Posts