CMU 17-630 Data Structures and Algorithms for Engineers Fall 2019
ASSIGNMENT 2 List ADT
Learning Objectives:
The purpose of this assignment is to practice the concepts associated with:
dynamically allocated linked lists and pointers
designing, implementing, and analyzing ADTs
coupling and cohesion in ADT design
utilizing a structured language (for those who do not know C)
Assignment Description:
Note that all your work must be your own work. You are not permitted to use code you find on the web. You are not permitted to share code with other students.
You will design and implement a linked list ADT using the Java Language. You are not allowed to use or extend any existing list (or comparable) class. You will create a test harness to test and demonstrate your ADT. Each of these parts is described in detail below.
List ADT
Design and build a linked list data structure that stores the following information in each element of the linked list:
First Name
Last Name
Birthday in the format: MM-DD-YYYY
Your list ADT should provide the following basic services:
append – Adds an element to the end of the list. Should also work with an empty list.
insert – Inserts an element at any specified position number i 1
delete at position i – deletes the element at position number i 1
delete first occurrence – Deletes the first occurrence of element that has the specified Last
Name.
delete any – Deletes any elements that have the specified Last Name.
search first occurrence – Searches for the specified Last Name or Birthday in the list.
search for all occurrences – Searches for all occurrences of the specified Last Name or
Birthday.
replace data in the element at position i – Replaces the data in the element at position i 1
with a new data record.
length – Returns the number of elements in the list.
These are all mandatory services that must be provided by your ADT. You may create other separate and distinct functions as necessary to meet the requirements outlined in Part 2 above especially to maintain separation of concerns.
1 ( i {0-n} where i is an element position Ʌ n = length of the list ).
Part 2: Test Harness
Design and build a separate test harness (application) to test your list ADT. Provide a basic textual interface (no GUIs) that enables a user to do the following.
Options:
1. Create new list from a file (user provides a string path name and then reads data from the file into the list).
2. Append an element onto the list (user provides the data via keyboard then appends an element to the list – if the list doesn’t exist, create a new one).
3. Print the contents of the list in numbered order front to back AND the total number of elements in the list.
4. Delete an element from the list by element number (user provides an element number via keyboard).
5. Delete an element from the list by last name (user provides a last name via keyboard).
6. Delete all elements from the list by last name (user provides a last name via keyboard).
7. Swap elements (user provides two positions in the list via keyboard).
8. List names for all those have a birthday on a specified date (user provides a date via keyboard).
X. Exit (properly dispose of the list and end the program).
A user may define only one list at a time. When the user starts the program, they must be able to select one of the above options. After selecting the option, the application will prompt the user for any further information required and/or execute the operation. After executing the operation, the application will present the menu of options and wait for the user to make another selection. If the user enters ‘X’ or ‘x’ the program will end.
For option #2 above you will read the data into the list from a file using the following format:
Neil
Armstrong
8-5-1930
Alan
Shepard
11-18-1923
John
Glenn
7-18-1921
Gus
Grissom
4-3-1926
Story
Musgrave
9-19-1935
:
Do not deviate from this file specification. We will test your code with our input file.
Guidance:
1. Carefully analyze the requirements. Make sure you understand what you are being asked to do. Sketch out the services you will provide to the programmers using your ADT. Follow the design practices discussed in class. Your list ADT must be as decoupled as possible from your test harness. Imagine that this ADT was going to be used by dozens of other programmers. Your ADT should hide the details of all the list operations. The test harness (and programmers using your ADT) should have the minimal visibility into the list ADT’s variables, datatypes, and functions to the greatest extent possible. Try to expose only those services that a programmer might need in order
to use your ADT to create a list and operate on it (per the requirements in part 1). Be very careful about introducing any kind of I/O dependencies (terminal, file, etc.) in your ADT that make it difficult to use in a general way. For example if your ADT prints data to a console, then you can never use the ADT it when you don’t have a console.
2. Once you have designed the algorithms for each of your operations, perform performance analysis on each of them. Each operation will have a Big-Oh performance complexity associated with it. Be able to describe it as we have in the classroom lectures, videos, exercises, and examples.
3. Once you have designed the algorithms for each of your operations, perform correctness analysis on each of them. Be able to explain how each will terminate and return a valid value. You many use any of the methods described in the classroom lectures, videos, and exercises, and examples.
4. Make sure that you design ample error handling in your application (test harness and ADT).
5. Make sure you document your software. The demo code provided is a good exemplar for reasonably well documented code.
6. Make sure you name is on ALL OF YOUR FILES INCLUDING YOUR SOURCE CODE. We will deduct points for nameless artifacts (once we determine who it is).
Assignment Preparation and Setup
You must use the console java compiler, javac to compile your code. We will test your code by putting all of your source code (*.java files) into a test directory and compiling it as follows:
javac *.java
We will then execute your program and test your application against your test plan with the provided data. You must follow these instructions precisely – if we can’t figure out how to build your app and run it, we won’t. Note that we will not install any additional tools. You may use any tools you like to write/edit your source code, build, and test your application. However, what you submit to us must adhere the guidelines outlined here.
If you are not familiar with Java, there is a nice tutorial here: https://www.tutorialspoint.com/java/ Deliverables:
For this assignment you will create the list ADT and the test harness per the requirements outlined above. You will also provide a BRIEF (no more than 3 page) write-up to accompany the source code that includes the following:
Brief instructions for compiling and executing your code: If we can’t figure how to build and run your app, we won’t and you will lose points. We will only compile your code using the command line gcc compiler. We will only execute your code on the command line. We will not install any additional tools or libraries.
Brief describe the design of your application: Show the static structure and relationship of the code modules you design. Provide a brief prose explanation of the design. Include rationale for why you designed the program the way you did.
Summary of algorithmic analysis of the ADT: Describing the time complexity and space requirements for each of the services in your ADT (do not worry about the test harness) using Big-Oh notation and explain how each of the services in your ADT terminate and provide the correct answer (again, do not worry about the test harness).
Packaging and Submitting Your Work
Post a single archive file of your report and code on canvas. Please use Windows or Mac OS compressed folder to create your archive – other archive formats (rar, pkzip, 7zip, etc. are not acceptable). Please include your name on all of your work including your source code. Name your archive as follows:
A2+
For example, my archive name for assignment 1 would be A1+mbass. You will lose points for not following these directions. Please check with the instructor or TA if you are unclear.
Grading:
This assignment is worth 100 points as follows:
○ Application: 75 points: Correct functionality, robustness, and the quality of design with respect to how well the list ADT you create hides complexity and is decoupled from the test harness; The quality of comments in the source code.
○ Quality of Report: 25 Points: Grammar, format, content, and thoroughness of the write-up.