Data Structures and Algorithms (Practical Task 1.1)-SIT221
1. Your task is to implement a generic data structure Vector<T>, which is similar to the collection class List<T> offered within the Microsoft .NET Framework. Here, T refers to a generic type, which can be substituted in practice by a specific data type such as bool, int, string, an array, or any class. An object of the List<T> can maintain an arbitrary number of data elements and provide broad functionality including, but not limited to, such basic operations as accessing, recording, and deleting elements from the data collection. It is known that the core of the List<T> is a simple internal array wrapped by the class exposing special methods and properties. This is done to make work with the data structure more convenient for the user and to give illusion that it is dynamic so that you can add/delete elements as you go. Because of the similarity of the Vector<T> to the List<T>, we strongly recommend you to become familiar with the
specification of the latter class available at https://msdn.microsoft.com/en‐us/library/6sh2ey19(v=vs.110).aspx
You may then address to this description when are in doubt about how a particular method of the Vector<T> should behave.
2. Download two C# source code files attached to this task. These files serve as a template for the program that you need to develop. Create a new Microsoft Visual Studio project and import the files. Your newly built project should compile and work without errors. Note that file Tester.cs already provides you with a Main method as a starting point of your program. Another file, Vector.cs, contains a template of the Vector<T>, which has some functionality implemented for you for the purpose of example, in particular:
Constructor. Initializes a new instance of the Vector<T> class that is empty and has a default initial capacity, say 10 elements.
Vector( int capacity )
Constructor. Initializes a new instance of the Vector<T> class that is empty and has a specified initial capacity. As an input parameter, this constructor accepts a number of elements that the data structure can initially store. If the size of the collection can be estimated beforehand, specifying the initial capacity eliminates the need to perform a number of resizing operations while adding new elements to it.
Count Property. Gets the number of elements physically contained in the Vector<T>.
Capacity Property. Gets the total number of elements that the internal array can potentially hold without resizing.
Capacity represents the number of elements that the Vector<T> can store before resizing is required, whereas Count is the number of elements that are actually in the Vector<T>. Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array to one of a larger size before adding the new elements.
void Add( T item )
Adds a new item of type T to the end of the Vector<T>. If Count already equals Capacity, the capacity of the Vector<T> is increased by automatically reallocating the internal array, and the existing elements are copied to the new larger array before the new element is added.
SIT221 Data Structures and Algorithms Trimester 2, 2019
int IndexOf( T item )
Searches for the specified item and returns the zero‐based index of the first occurrence within the entire data structure. It returns the zero‐based index of the item, if found; otherwise, –1.
T this[ int index ]
Returns the element at a specified index of the sequence. As an argument, it accepts a zero‐based index of the element to retrieve. This method throws IndexOutOfRangeException when the index’s value is invalid.
The given template of the Vector<T> class should help you with development of its remaining methods.
Therefore, explore the existing code as other methods are to be very similar in terms of implementation.
3. You must complete the Vector<T> and provide the following functionality to the user:
void Insert( int index, T item )
Inserts a new element into the data structure at the specified index. If Count already equals Capacity, the capacity of the Vector<T> is increased by automatically reallocating the internal array, and the existing elements are copied to the new larger array before the new element is added. If index is equal to Count, item is added to the end of the Vector<T>. This method throws IndexOutOfRangeException when the index’s value is invalid.
Removes all elements from the Vector<T>. Count is set to 0, but capacity remains unchanged.
bool Contains( T item )
Determines whether a specified item is in the data collection. It returns true when the item is presented, and false otherwise.
bool Remove( T item )
Removes the first occurrence of the specified item from the data collection. It returns true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the Vector<T>.
void RemoveAt( int index )
Removes the element at a specified index of the Vector<T>. When you call RemoveAt to remove an item, the remaining items in the list are renumbered to replace the removed item. For example, if you remove the item at index 3, the item at index 4 is moved to the 3rd position. In addition, the number of items in the data collection (as represented by the Count property) is reduced by 1. This method throws IndexOutOfRangeException when the index’s value is invalid.
Returns a string that represents the current object. ToString() is the major formatting method in the .NET Framework. It converts an object to its string representation so that it is suitable for display.
Note that you are free in writing the code of your vector class unless you respect all the requirements in terms of functionality and signatures of the specified methods. For simplicity, you may assume that the value of Capacity can only be increased. The format of the string returned by the ToString() method is [a,b,c,d], where a, b, c, and d are string values returned by the corresponding ToString() method of the data type T.
4. As you progress with the implementation of the Vector<T> class, you should start using the Tester class to thoroughly test the Vector<T> aiming on the coverage of all potential logical issues and runtime errors. This (testing) part of the task is as important as writing the vector class. The given version of the testing class covers only some basic cases. Therefore, you should extend it with extra cases to make sure that your vector class is checked against other potential mistakes.
Read Chapter 1 of SIT221 Workbook available in CloudDeakin in Resources Additional Course Resources
Resources on Algorithms and Data Structures SIT221 Workbook. It will give you general understanding of the task and issues related to the use of arrays in practice.
SIT221 Data Structures and Algorithms Trimester 2, 2019
If you still struggle with such OOP concepts as Generics and their application, you may wish to read Chapter 11 of SIT232 Workbook available in Resources
Additional Course Resources
Resources on Object‐Oriented Programming. You may also have to read Chapter 6 of SIT232 Workbook about Polymorphism and Interfaces as you need excellent understanding of these topics to progress well through the practical tasks of the unit. Make sure that you are proficient with them as they form a basis to design and develop programming modules in this and all the subsequent tasks. You may find other important topics required to complete the task, like exceptions handling, in other chapters of the workbook.
We will test your code in Microsoft Visual Studio 2017. Find the instructions to install the community version of Microsoft Visual Studio 2017 available on the SIT221 unit web‐page in CloudDeakin at Resources
Additional Course Resources Software Visual Studio Community 2017. You are free to use another IDE if you prefer that, e.g. Visual Studio Code. But we recommend you to take a chance to learn this environment.
Marking Process and Discussion
To get your task completed, you must finish the following steps strictly on time.
Make sure that your program implements all the required functionality, is compliable, and has no runtime errors. Programs causing compilation or runtime errors will not be accepted as a solution. You need to test your program thoroughly before submission. Think about potential errors where your program might fail.
Submit your program code as an answer to the task via OnTrack submission system.
Meet with your marking tutor to demonstrate and discuss your program in one of the dedicated practical sessions. Be on time with respect to the specified discussion deadline.
For this task, during your discussion, you must demonstrate how you run your program in debug mode and how you can use it to detect and fix potential errors. Cloud students are allowed to record a video of debugging process complemented with their verbal explanation, upload the video to one of accessible resources, and refer to it for the purpose of marking. They must provide a working link to the video to the marking tutor.
Answer all additional (theoretical) questions that your tutor can ask you. Questions are likely to cover lecture notes, so attending (or watching) lectures should help you with this compulsory interview part. Please, come prepared so that the class time is used efficiently and fairly for all the students in it. You should start your interview as soon as possible as if your answers are wrong, you may have to pass another interview, still before the deadline. Use available attempts properly.
Note that we will not check your solution after the submission deadline and will not discuss it after the discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the unit. Unless extended for all students, the deadlines are strict to guarantee smooth and on‐time work through the unit.
Remember that this is your responsibility to keep track of your progress in the unit that includes checking which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack system and feedback provided by your tutor about your overall progress and quality of your solutions.
This section displays the printout produced by the attached Tester class, specifically by its Main method. It is based on our solution. It is likely you get a different printout as the ToString method written by you might differ from one in the official solution. This is certainly acceptable. The printout is provided here to help with SIT221 Data Structures and Algorithms Trimester 2, 2019
testing your code for potential logical errors. It demonstrates the correct logic rather than an expected printout in terms of text and alignment.
Test A: Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'
Test B: Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5
Test C: Remove number 3, 7, and then 6
Test D: Insert number 50 at index 6, then number 0 at index 0, then number 60 at index 'vector.Count-1', then number 70
at index 'vector.Count'
Test E: Insert number -1 at index 'vector.Count+1'
Test F: Remove number at index 4, then number index 0, and then number at index 'vector.Count-1'
Test G: Remove number at index 'vector.Count'
Test H: Run a sequence of operations:
Test I: Print the content of the vector via calling vector.ToString();
Test J: Clear the content of the vector via calling vector.Clear();
------------------- SUMMARY -------------------
Tests passed: ABCDEFGHIJ