Implement a prototype

Assignment Help Computer Engineering
Reference no: EM131451310

Assignment Specification - Part A

For this part of the assignment you will implement a prototype that uses a BST to store welfare and tax data. The BST will consist of individual records where each record contains a tax file number (used as a key for the BST); the name of the individual (we will just prototype with a single name with no spaces); a list of years that the person received welfare payments; and a list of years that the person lodged a tax return.

The program will start by reading the data from the separate files into the BST (populating each list in turn). The program will then prompt for a tax file number and print a message displaying the years in which that person both received welfare payments and lodged a tax return. The program will terminate if the user enters a 0 as the tax file number.

Data Structure Requirements

You must use the BST and linked list code developed in the tutorials, however the data structures will be modified for the new types (and functions will also require minor modifications to accommodate these changes).

The following definitions MUST be used:

typedef struct listNode{ int data;

struct listNode*next;} *ListNodePtr;

typedef struct list{ListNodePtr head;
} List;

typedef struct taxRecord{ long tfn;

char *name;List welfare; List tax;
} *TaxRecordPtr;

typedef struct bstNode{TaxRecordPtr data;struct bstNode*left; struct bstNode*right;
} *BSTNodePtr;

typedef struct bst{BSTNodePtr root;

} BST;

The BST, BSTNodePtr, and TaxRecordPtr definitions, must be placed in a file called bst.h, along with the BST function prototypes. The modified BST functions must be placed in bst.c.

The List and ListNodePtr definitions must be placed in list.h, along with the list function prototypes. The modified list functions must be placed in list.c. No other code should be placed in these files.

All remaining code, should be placed in a file called main.c that contains the main function and program logic. Other functions may be added if required.

Program I/O

The welfare data consists of a text file, with the first line containing the number of entries. Each entry is then split over three lines. The first line contains a name, the second line contains a tax file number (no spaces), and the third line contains a single number indicating the number of years followed by an ordered list of that many 4 digit years separated by spaces. For example:

4 Robert

123456789

3 1991 1992 1993 Julian 987654321 1 1990

James 123581321

4 2012 2013 2014 2015 Joel

666666666

0

The tax data consists of a text file with the first line containing the number of entries. Each entry is split over two lines. The first line contains the tax file number (no spaces), the second line contains a single number indicating the number of years followed by an ordered list of that many 4 digit years separated by spaces. For example:

4

123456789

6 1993 1997 2011 2012 2013 2017

111000111

4 1995 1998 2000 2007

987654321

6 2011 2012 2013 2014 2015 2016

123581321

5 2013 2014 2015 2016 2017

We will use fscanf to read the input files. For example, to read the first three lines of the welfare file above, you could write:

FILE *filePtr;
filePtr = fopen("welfare.txt", "r"); // open for 'r'eading

fscanf(filePtr, "%d", &num_records); // num_records is an int or long
fscanf(filePtr, "%s", buffer); // buffer is a char array
fscanf(filePtr, "%d", &tfn); // tfn is a long
// ...
fclose(filePtr);

Note that there may be individuals with entries in one file and not the other. Your program only needs to keep track of individuals with an entry in the welfare file.

All interactions with the program will be via the console. The program will continuously ask for a tax file number. If the tax file number is not zero, it will either print the name of the person with that tax file number followed by the year that individual both received welfare and lodged a tax return; or it will print a message saying that individual has never received welfare payments. If the tax file number is zero, the program will exit. For example, given the data above, a session might look like this:

123456789 Robert 1993

111000111

No entry with that tax file number

987654321 Julian

123581321

James 2013 2014 2015

0

I/O Restrictions

You may assume that all input will always be in the correct format and contain no logical errors.

• Data files will always be in the correct format

• The user will only ever enter integers in the range 0 - 999999999

Algorithms

Aside from the basic algorithms for storing items in linked lists and binary search trees, the only other algorithm that needs to be developed is the one to determine which years appear in both linked lists. If the length of the first list is n, and the length of the second list is m, there is a simple method that is 0 (m ×n), but there is a much more efficient method that is O (m +n). You will get most of the marks for the linked list if you use the simple method, butto get a high distinction for the linked list task, you need to use the more sophisticated method.

Memory Management

Names should be stored in appropriately size dynamically allocated memory. Names will always be less than 100 characters long. For example, the name "robert" would be stored in a char string of length 7.

On termination, all dynamically allocated memory should be freed, including char strings, lists and the BST.

Assignment Specification - Part B (20%)

This part of the assignment should only be attempted once you have a fully implemented andthoroughly tested solution to part A. It would be better to submit a complete part A and nopart B than to submit a partially complete part A and part B.

The requirements for this part of the assignment are exactly the same as for part A except that an AVL tree must be used rather than the BST. The AVL files should be named avl.h and avl.c, but avl.h should #include the node and tax record definitions from bst.h (i.e. avl.h will only add the AVL function prototypes, the struct definitions are the same).

Minimal assistance will be provided for this part of the assignment. No assistance at all will be given unless you can demonstrate a fully implemented and thoroughly tested solution to part A.

Part B should be a separate submission - i.e. submit Part A and Part B as two separate Visual Studio projects.

Testing

It can be very time consuming to thoroughly test a program like this where large datasets are required.

At least one small pair of test files will be provided with sample output for a hypothetical session. It is recommended that you construct larger files to fully test your program (I use Python scripts to construct test files, but you could also use Excel or similar).

This is an important part of program development! It has been a common complaint from students that their code worked for "all of their tests", but not for the markers. Make sure that you allow enough time for testing so that this doesn't happen to you.

Assignment 1 - Data Structures

Synopsis of the task and its context

This is an individual assignment making up 10% of the overall unit assessment.

The assessment criteria for this task are:

1. Implement basic program functionality for a console driven application

2. Implement and test a linked list to store years

3. Implement and test a BST to store data

4. Implement and test an AVL tree to store data

Attachment:- tax1.txt

Reference no: EM131451310

Questions Cloud

Does walmart have any responsibilities to its suppliers : Despite PR posturing, corporate philanthropy is down from 25 years ago. To be taken seriously, companies should pledge 1 percent of pretax earnings.
What is one synonym and one antonym for armistice : What is one synonym and one antonym for armistice?
Does the fact that target and general mills donate five time : Does the fact that Target and General Mills donate five times more than the minimum 1 percent make them five times more socially responsible?
Support or oppose jays treaty and relationship with britain : Support or oppose French Revolution and relationship with France? Support or oppose Jay's Treaty and relationship with Britain?
Implement a prototype : KIT205 Data Structures and Algorithms - Assignment 1: Data Structures Implement basic program functionality for a console driven application - Implement and test a linked list to store years
How did the great wave of immigration affect city of chicago : HTY 110HA:How did the Great Wave of Immigration affect the city of Chicago ?What countries and ethnic groups comprise the Slavic peoples?
Explain reasons you would be of value to agency in meeting : Explain two or three reasons you would be of value to the agency in meeting those challenges.
Describe the social contract model of corporate management : One team must prepare a presentation advocating for the instrumental model of corporate management.
Should we focus on off-the-shelf technology : As you review all the programs in the DHS research and development budget in Chapter 12 of your primary text. Should we focus on off-the-shelf technology?

Reviews

len1451310

4/5/2017 3:48:39 AM

3. Implement a Correctly implemented BST functions covered in BST to store tutorials data Correctly read and inserted tax file numbers and names into BST Used correct data structures Weighting 40% Freed all BST memory (including name strings and attempting to free linked lists) Written BST code that is clear and easy to follow 4. Implement an Completed task 3 to HD level, but using AVL tree AVL tree to store data

len1451310

4/5/2017 3:48:31 AM

You have: 1. Implement Correctly implemented console application basic program Read files without errors (even if data is not stored in functionality linked lists and BSTs) Stored strings in appropriately sized dynamically Weighting 10% allocated memory Implemented a loop that repeatedly waits for input and exits when the input is 0 Organised data structures and other codes as required (even if implementations are not correct) 2. Implement a Correctly implemented linked list functions covered in linked list to tutorials store years Correctly read and inserted years into linked list Correctly implemented O(m+n) algorithm for Weighting 30% determining years in both lists Used correct data structures Freed all list memory Written linked list code that is clear and easy to follow

len1451310

4/5/2017 3:48:08 AM

On successful completion of this unit, you will be able to: Transform a real world problem into a simple abstract form that is suitable for computation Implement common data structures and algorithms using a common programming language Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms for specific tasks Use common algorithm design strategies to develop new algorithms when there are no pre-existing solutions Create diagrams to reason and communicate about data structures and algorithms

len1451310

4/5/2017 3:47:55 AM

KIT205 Data Structures and Algorithms: Assignment 1 - Data Structures Synopsis of the task and its context This is an individual assignment making up 10% of the overall unit assessment. The assessment criteria for this task are: 1. Implement basic program functionality for a console driven application 2. Implement and test a linked list to store years 3. Implement and test a BST to store data 4. Implement and test an AVL tree to store data A significant part of the assessment procedure will involve automated tests. Therefore, it is very important that your own testing is very thorough.

len1451310

4/5/2017 3:47:42 AM

Please confirm the expert's quote: Subject : data structure and algorithum - visual basic 2013 in C file . output file as well.and more output file also.Assignments will be submitted via MyLO (an Assignment 1 dropbox will be created). You should use the following procedure to prepare your submission: • Make sure that you project has been thoroughly tested using the School’s lab computers • Choose “Clean Solution” from the “Build” menu in Visual Studio. This step is veryimportant as it ensures that the version that the marker runs will be the same as theversion that you believe the marker is running. • Quit Visual Studio and zip your entire project folder • Upload a copy of the zip file to the MyLO dropbox History tells us that mistakes frequently happen when following this process, so you should then: • Unzip the folder to a new location • Open the project and confirm that it still compiles and runs as expected o If not, repeat the process from the start

Write a Review

 

Computer Engineering Questions & Answers

  Define the difference between testing and debugging

Why do companies usually release software that is not bug-free.

  Questionuse jsp to prepare an amortization table for a loan

questionuse jsp to prepare an amortization table for a loan. create a html form that uses-1. textbox to enter loan

  Which subnet mask should you select

Your company is assigned the network address 150.50.0.0. You need to create seven subnets on the network. A router on one of the subnets will connect the network to the Internet. All computers on the network will need access to the Internet. What ..

  Design the function "count" which takes a list of items

design the function "count" which takes a list of items and an item as arguments, and returns the number of times the item occurs in the list.

  Identify and analyze at least four digital payment concerns

with the increasing use of digital payments and the decreasing use of cash payments enhanced digital security and

  Create an expert system of your own application

Create an expert system of your own application (examples will be provided ) . Utilize at least 20 rules in your application and you must employ chaining between at least 10 rules.

  Question1 images can be stored as lossless or lossy bitmaps

question1. images can be stored as lossless or lossy bitmaps. explain differences why are most photographic images

  Propose how you would model the system behavior

Propose how you would model the system behavior to show suggested changes to the current process. Defend why you chose the model that you did to show the suggested changes.

  Who is developing software for a wireless system

In what way can a virtual hardware platform help a programmer who is developing software for a wireless system? What do you see as a potential problem of developing for a virtual hardware platform.

  Questionwrite down an interactive program that prompts user

questionwrite down an interactive program that prompts user for three real numbers and finds the sum average smallest

  Why prepaid cell phones make forensic investigation hard

Discuss about how can you quickly investigate and collect digital evidence for a crime what involves a phone call (e.g., you checked the victim's cell phone and you find a phone call from a phone number, this phone number could be a VoIP phone, a ..

  What tool is used to manage server roles

What tool is used to manage server roles from the graphical user interface of Windows servers and define an AD group in your own words.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd