Exercises - Week 4


Sequence ADT
Arrays and linked lists are two implementations of a data structure capable of keeping elements in sequence.
Let's call this abstract data structure  Sequence.

Its basic operations are therefore
add(int index, int value); // inserts element at position index. all elements starting at position
     index are moved forward one position
int get(int index);  // returns element at position index
int remove (int index) // returns element at position index and removes it (all
    elements past index are moved backwards one position)
int search(int value) // searches element with value 'value' and returns its index (-1 if not found)

add and remove are designed so that all elements are continuous, meaning that
if there is in the sequence an element at position i, there is also one at position i-1, i-2 etc
until 0.

Further, we want that
-the Sequence has no upper limit. It must be able to grow as needed.
-elements start from index 0

1 ArraySequence
Start from this project.
Define an implementation of the Sequence ADT using arrays. Note that the Sequence must be able
to grow without limit. Considering allocating an array of 10 elements at the first add. Then, at the11th
add you can allocate a 20 elements array and copy the first one on the second. And so on.
Discuss the complexity of the add, remove and search operations.

3 LinkedListSequence
Start from this project.
Define an implementation of the Sequence ADT using linked lists.
Discuss the complexity of the add, remove and search operations.

3 SequenceAdt - one instance
Start from this project.
Define an implementation that (upon initial choice of the programmer, function CreateArraySequence()
vs CreateLinkedListSequence()) implements the Sequence either as an array or as a linked list
Remark that it is possible to define and use  only one sequence at a time.

4 Sequence - many instances
Start from this project.
The implementation is as in point 3, but now many instances of a sequence can be generated and used at the
same time.

5 Sequence of students
Modify the sequence of point 4 to manage students instead of integers. The sequence should be able to
add, delete a student, search a student, sort and print all students.
Compare this solution with the one of Week 2, point 4.