### Data structures and algorithm design

Assignment Help Data Structure & Algorithms
##### Reference no: EM131058

Problem 1

In an advanced country, a point system is maintained to keep track of erring drivers, and vehicle owners. The objective for this lab is to comeup with a software to keep track of penalties incurred by the drivers, and help decide those drivers whose driving license should be revoked.

Each driver is assigned an initial score of ten. Every minor offense (parking ticket, overspeeding, underspeeding, etc.) will be awarded a penalty of -1. Every major offense (drunk driving, reckless driving, accidents) will be awarded a penalty of -5. If a driver's score becomes 0 or negative, his/her license will be revoked.

For this problem, it is assumed that the owner of the car is always going to be driving the car. The list of offenses is provided as a text file containing the vehicle number and the nature of offense(Minor, Major). The list of drivers along with their UID and license number is available as input in a file named drivers.txt. A file named owners.txt maps the vehicle number to the UID of the owner. For the sake of simplicity, license number is a 10-digit integer, and vehicle number contains 3 characters followed by 4 digits. UID is a unique identifier provided to every citizen in the country, and it contains 12 digits.

The data structures to be used, the file format for various files and the general step-by-step process for this lab's task are being stated in the remainder of this document.

Data structures to be used:

1) Vehicle: This contains the list of all vehicles along with the vehicle number and UID of owners, with UID as the key. Vehicle is maintained as a dynamic list.

2) Drivers: This represents the dynamic list of the tuples (license number, UID, score).

3) RevokeList: This list contains the current list of revoked drivers in the form of tuple (license number, vehicle number, UID).

File Formats:

The file format for the input files is as follows:

drivers.txt:

For ex:
182930101222,9929929921

The file format for owner.txt is as follows:
<UID,Vehicle Number>
Note: There is no space between number of items and item name. End Note.
For ex:
182930101222,KLA1512

The file format for offenses.txt is as follows
<Vehicle number> <Minor/Major>
For ex:
DNA1423 1
KAS1002 0
BEL1923 0
KAS1002 1

Note that 0 indicates Minor offense here, and 1 indicates a major offense.

Step 1:

Identify appropriate data structures relevant for the problem and write them in Offense.h

Step 2:

Design Offense ADT with the following operations (OffenseOps.h). The relevant operations are:

(a) populateVehicles - This function reads input from file and populates its content in the Vehicles list in lexicographic order of vehicle numbers. It then returns the populated list.

(b) populateDrivers - This function reads input from file and populates its content in the Drivers list in non-decreasing order of UIDs. It then returns the populated list.

(c) updateOffenses - This function reads the contents of the file containing offenses. It looks up the Vehicle list to find the UID of owner. Using the UID, it looks up the license number of the driver. It then updates the score in the corresponding tuple <license number, UID, updated score> in the drivers list.

(d) markRevokedDrivers - this function identifies all drivers whose license needs to be revoked, and puts them in the file named revoke.txt

You may need the following support functions:

i) insertVehicle - this function inserts a row of vehicle details in order

ii) insertDriver - this function inserts a row of driver details in order

iii) lookupUID - search for a UID from the Vehicles list given the vehicle number, and return it.

iv) lookupVehicle - search for a vehicle number from the Vehicle List given the UID of the owner, and return it.

v) lookupDriverDetails - search the Drivers list based on UID, and return the index of the entry containing that UID.

Step 3: Implement the above operations in the corresponding c files All relevant code must go to OffensesOps.c

All list creations must have filename as a parameter.

Step 4: driver file.

Create a simple driver file (revoke.c) that can read multiple input files corresponding to the various input files. The names of input files are passed as command line parameters. Note that if no input file is passed, the program should attempt to run with drivers.txt, owners.txt and offenses.txt for the relevant input set. The executable revoke generates output files revoke.txt that will contain the list of drivers (license number, UID, vehicle number) whose license is to be revoked.

For the purposes of testing, you may implement some functions to print the data structures or other test data. But all such functions must be commented before submission to server.

#### Questions Cloud

 Use cases perform a requirements analysis for the case study : Use Cases Perform a requirements analysis for the Case Study Using .net resources to teach .net : This project will use the .NET framework to produce a set of materials to demonstrate the fundamental principles of .NET. Ideally it should demonstrate some of the principles of the framework e.g. interoperability. State the multiple regression equation : State the multiple regression equation Write a report on a new photocopier : Write a report on a new photocopier which the accounting firm can purchase. Data structures and algorithm design : Data Structures and Algorithm Design Tax revenue : The Australian government administers two programs that affect the market for cigarettes Accounting for bad debt expense : Accounting for bad debt expense Identify a moral dilemma : Analyse the situation using Ethics Technique Determine the critical path : Determine the critical path and the expected project completion time

### Write a Review

#### Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

#### Survey of fault tolerance policy for load balancing scheme o

This paper investigates about fault-tolerance in load balancing schemes in distributed environment. There are some more parameters influencing QOS but our main focus is on fault tolerance and load balancing.

#### Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

#### Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

#### Write the selection sort algorithm

Write the selection sort algorithm

#### How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

#### Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

#### Currency conversion development

Currency Conversion Development

#### Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

#### Use a search tree to find the solution

Explain how will use a search tree to find the solution.

#### Data structures for a single algorithm

Data structures for a single algorithm

#### Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote