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

Implementation of the spacecraft feature

Assignment 1: The Diamonds of Doom - Discuss and brain-storm with your associates, you must ensure that your submission is your own individual work - implementation of the "Sp

Determine a discrete-time transfer function

Determine a discrete-time transfer function that approximates G(8) using the Adams-Schlumberger predictor as an operational substitution method. You may use a computer algeb

What is relationship between size and complexity and testing

What is the relationship between Size and Complexity and Testing? Do you agree: Better Code Coverage means better quality?  Based on the article what are the techniques that c

Provide a brief historical summary on sox enactment

Provide a brief historical summary on SOX enactment. Identify and explain the key ethical components of the SOX. Assess the social responsibility implications regarding mandat

What do you think might happen if situation does not change

What do you think might happen if this situation doesn't change? Is downloading music or videos without paying any different ethically than shoplifting CDs or DVDs from a st

Make any dfa in jflap software and run for several inputs

Make any DFA in JFLAP software and run for several inputs. Take a screen shot and include in your assignment. Keep in mind that this assignment is meant to make you all get

Designing a secure online data store

CKDF140 PROJECT Designing a secure online data store -  Risk analysis: which consists of asset evaluations, threat modeling, and vulnerability analysis and Security requiremen

Problem based on berkeley-based unix system

Consider a system such as a Berkeley-based UNIX system, in which users have secondary group identities that remain fixed during their login sessions - What are the advantage

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

 
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