data structures and algorithm

CSC301-Data Structures and Algorithms (Fall 2020) 1

In this programming assignment you are asked to expand the SortedArrayList data structure we have developed in class by adding the following new methods:

 void IncrementItems(T aValue) - Function: Increments all lists’ values by aValue. - Precondition: List has been initialized aValue has been initialized - Postcondition: Function value = elements of the list have their info incremented

by a Value.

 int CountEven() - Function: Returns the number of elements that appears an even number of

times the list. - Precondition: List has been initialized - Postcondition: Function value = number of even integers in the list.

 void ReverseOrder ( ) - Function: Reverses the order of the list’s elements. - Precondition: List has been initialized. - Postcondition: Function value = elements changed to descending order, if

elements are in ascending order, and vice-versa.

 SortedArrayList OddSubList()

- Function: Returns a sublist containing only the odd elements. - Precondition: List has been initialized - Postcondition: Function value = a sorted list containing only odd ones.

 void AddList(SortedArrayList l2) - Function: Adds all elements of l2 to the actual list. - Precondition: Actual list and l2 have been initialized. - Postcondition: Function value = elements of l2 are added to the actual list.

 void Undelete() - Function: recovers the last deleted element. - Precondition: Actual list has been initialized. - Postcondition: Function value = last element deleted from the list is reinserted

back to the list. Method can be called more than a time and it recovers all the previously deleted elements.

 void Undo() - Function: cancel the effect of the last executed method that has changed the

data structure. - Precondition: Actual list has been initialized.

Programming Assignment 2 CSC301: Data Structures and Algorithms

Deadline: October 20th 2020, 23:59

CSC301-Data Structures and Algorithms (Fall 2020) 2

Postcondition: Function value = last executed method effect is cancelled and the list is reversed back to the state before executing the last method. Consider undoing only the method listed above. Method can be called more than a time and it will undo all the previously executed methods.

You must do this lab in groups of at most two students. You should upload your work via Blackboard on time before October 20th, 23:59. Any late submission will be penalized (-0.25/day). Evaluation: You will be evaluated based on a demo during which you will be asked

individual questions. The weights are as follows: CountEven (1 mark), IncrementItems (0.5 mark), ReverseOrder (0.5 mark), EvenSublist (1 mark), addList (1 mark), Undelete (1.5 mark), and Undo (2 mark).

You should test your program using the following lists of integer: L1 = [1, 3, 6, 6, 6, 6, 7, 8, 11, 11, 14, 15, 20, 20]

L2 = [10, 20, 40, 60, 80]

L3 = [30, 50, 70]

 L1.CountEven() returns 3 L2.CountEven() returns 0

 L1.IncrementItems(10) gives L1 = [11, 13, 16, 16, 16, 16, 17, 18, 21, 21, 24, 25, 30, 30]

 L1. ReverseOrder() results in L1 = [30, 30, 25, 24, 21, 21, 18, 17, 16, 16, 16, 16, 13, 11] L2. ReverseOrder() results in L2 = [80, 60, 40, 20, 10]

 L4 = L1.OddSublist() results in L4 = [25, 21, 21, 17, 13, 11]

 L2.addList(L3) results in L2 = [80, 70, 60, 50, 40, 30, 20, 10] L3.addList(L2) results in L3 = [10, 20, 30, 30, 40, 50, 50, 60, 70, 70, 80]

 L2.DeleteItem(50) gives L2 = [80, 70, 60, 40, 30, 20, 10] L2.DeleteItem(10) gives L2 = [80, 70, 60, 40, 30, 20] L2.DeleteItem(80) gives L2 = [70, 60, 40, 30, 20] L2.Undelete() results in L2 = [80, 70, 60, 40, 30, 20] L2.Undelete() gives L2 = [80, 70, 60, 40, 30, 20, 10] L2.Undelete() gives L2 = [80, 70, 60, 50, 40, 30, 20, 10]

 L3.Undo() results in L3 = [30, 50, 70]

 L3.ReverseOrder() gives L3 = [70, 50, 30]  L3.IncrementItems(10) gives L3 = [80, 60, 40]  L3.Undo() results in L3 = [70, 50, 30]  L3.Undo() results in L3 = [30, 50, 70]