CS 351/751: Data Structures & Algorithms Homework #4
Homework #4
due Monday, October 3, 10:00 PM
In this assignment we continue our investigation of implementing a “sorted sequence”
ADT. This week, it will be re-implemented using a linked-list. Read Chapter 4 carefully
and especially make sure that you read Section 4.5, pages 232– XXXXXXXXXX–231, 3rd ed.) which
specifically say how to implement Sequence with linked lists. We will be implementing
ApptBook with its different interface, and with a change in the data structure too.
Use this link to accept the assignment:
https:
classroom.github.com/a/MSlyiVCN
1 Concerning New Implementation of ApptBook
The ApptBook class will have the same public declarations as the ApptBook you implemented
efore (except no way to specify an initial capacity), but the data structure (private fields)
will be completely different. Declare a node class as a “private static class” inside the
ApptBook class. Such a class (one declared inside another class) is called a “nested” class.
The node class should have two fields: the data (of type Appointment) and the next node.
It should have a constructor that takes initial values for both fields, but no other methods.
Despite what it says in the textbook, do not write methods in the “Node” class.
The design in the textbook starting on page XXXXXXXXXX, 3rd ed.). We make the data
structure smaller by omitting a “tail” field. The tail is not needed for any of our methods,
so the burden of keeping it consistent outweighs the non-existent benefit. We still have
a precursor and a cursor (which implies some redundancy) but represent the “no cu
ent
element” condition differently:
We represent “no cu
ent element” by having the curor be null and the precurso
e the last node of the list (if there is one). For example:
cursor head
1 2 3
precurso
(The textbook has both precursor and cursor be null in this case which requires
more special cases in the code.)
Your wellFormed method will need to check the data structure (as always). And also as
usual, you are given a number of invariant tests to make sure that this is done. If you don’t
understand the test, and you have read the explanation of the fields in the textbook, please
post a question on Piazza about the test.
Fall 2022 page 1 of 3
https:
classroom.github.com/a/MSlyiVCN
CS 351/751: Data Structures & Algorithms Homework #4
The redundancy makes certain operations easier (especially ones that do not change
anything, such as isCu
ent), but complicates the work of those which make changes (such
as removeCu
ent).
Unlike in the past assignment, clone requires some (difficult!) work for you to do: the
list must be copied, cell by cell, and pointers of the clone made to point to the appropriate
copied nodes.
1.1 The Invariant
The invariant is more complex than in the previous implementation. It has the following
parts:
1. The list may not include a cycle, where the next link of some node points back to
some earlier node.
2. No data in the list may be null, and they must be in non-decreasing natural order. (As
efore, duplicates are permitted.)
3. The precursor field is either null or points to a node in the list. It cannot point to a
node that is no longer in the list—the node must be reachable from the head of the
list.
4. The cursor must be the first node if the precursor is null, and otherwise must be the
node after the precursor.
5. The field manyNodes should accurately represent the number of nodes in the list.
We have implemented the first part for you; you should implement the other parts yourself.
You should do this early on in developing the implementation—it will help you catch bugs
as quickly as possible. We provide code to test the invariant checker.
Be very careful that you never change any fields in the invariant checker, wellFormed. It
is ONLY supposed to check the invariant and return true or false (with a report). It should
never change things. It will need to define its own local variabloes of course, which may be
modified during the execution of the method. Local variables have no effect on any stored
objects.
2 Files
The repository homework4.git includes the following files:
src/TestApptBook.java Updated functionality tests.
src/TestInvariant.java Call out to the invariant checker tests.
src/edu/uwm/cs351/ApptBook.java Skeleton file.
li
homework4.jar JAR file containing the other ADTs, and random testing.
Fall 2022 page 2 of 3
CS 351/751: Data Structures & Algorithms Homework #4
This project also has random testing. It is implemented without change from Homework
#2 because the public interface (and meaning of the methods) of the ApptBook class is
unchanged. There are no efficency tests for thie assignment.
Fall 2022 page 3 of 3
Concerning New Implementation of ApptBook
The Invariant
Files