Subject Computer Science Data Structures and Algorithms

Question

Objective:    This assignment is designed to analyze and compare a variety of data structures for a set of operations. When choosing an abstract data structure for your programs, you should first determine the operations that must be performed by the structure. When you narrow down the data structures that support the operations needed, you can then determine which structure will allow for optimal performance. We are investigating the performance of these structures.

Problem:   Your program, when it is complete, should use the following data structures:
1. Stack (array implementation)
2. Queue (array implementation)
3. Unsorted Linked List

To measure the plausibility and performance of the following operations:
1. Insert a record
2. Update a record
3. Delete a delete
Input: All input for this program should come from an input file of your own making. Your program should allow the user to enter the input file name, so the program can work with any data file of the format given below.

Procedure:
Step #1: Read n, an integer. This tells you how many elements are to be read into your data structure.

Step #2: Read in the n elements. (Insertion)
Each element (one per line) will consist of:
LastNamexxxx FirstNamexxx YearlyIncome

-LastName and FirstName can have up to 12 characters each. Use fixed length strings separated by one space.
-YearlyIncome is float.
-Each record will be inserted in each of the three data structures. While inserting the elements, count how many individual comparisons, moves, and assignments are needed to accomplish the insertion.

Step #3: Print out the following table, which contains the number of comparisons for insertion of each record into each structure.   Find the average of each column.

Insertion Table
Record    Stack Queue Linked List
LastName1
LastName2
LastName3
LastName
Average

Step #4: Read m (an integer) (Last names should all be in the data structure)
Execute m commands of the following form:
Update LastName   x
where x is a float and indicates that LastName’s yearly income should be changed to x. You are to update LastName’s record in each of the data structures. Your data must match a name in the list.

Step #5: Print out a table with the number of comparisons, moves, and assignments to update each record in the update list for each structure.
Find the average of each column.
Update Table Record Stack Queue Linked List LastName1 LastName2 LastName3 .. LastName m Average

Step #6: Perform steps 4 and 5 again, except this time it is possible that the update list will have LastNames that are not in the data structures. Assume that 50% of the names you try to update are not in the data structure. The point of this exercise is to show how attempting to update values that are not in the list affects the performance of each of the three data structures.

Step #7: Read m (an integer)
Process m instructions of the form on all structures:
Delete LastName
Note: LastName may or may not be in the data structure.
Print out a table with the number of comparisons, moves, and assignments to delete each record in the deletion list for each structure.
Find the average of each column.
Delete Table Record Stack Queue Linked List LastName1 LastName2 LastName3 .. LastName Average

Step #8: Print the data in each of the three data structures in order from the beginning of the structure, with one entry per line. Stack LastName FirstLetterOfFirstName YearlyIncome Queue LastName FirstLetterOfFirstName YearlyIncome Linked List LastName FirstLetterOfFirstName YearlyIncome
Assisting Tutor

Related Homework Solutions

Big-O Complexity Series Question
Homework Solution
$13.00
Big-O
Complexity
Power
Serie
Sequence
Integration
Sum
Geometric
Differentiate
Exponential
Show
Calculation
Step
Detail
Answer
Programming Problems in C++
Homework Solution
$10.00
Programming
Computer Science
C++
Classes
Libraries
Command Line Arguments
Music Files
Statements
Variables
Scripts
Input
Output
Information
Underscores
Spaces
Track Numbers
Lexicographic Sorting
Songs
Computer Engineering Questions
Homework Solution
$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Address Enable Signal
Processors
States
Reading
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Sorting Algorithms in C++
Homework Solution
$25.00
Computer Science
Sorting Algorithms
C++
Selection Sort
Heap Sort
Counting Sort
Integers
Time Complexity
Dataset
Report
Maximal Element
Range
Statements
Variables
Loops
Get help from a qualified tutor
Live Chats