Data Structures and Algorithms (Practical Task 1.1)-SIT221

General Instructions
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:
 Vector()
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
2
 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.
 void Clear()
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.
 string ToString()
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.
Further Notes
 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
3
 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.
Expected Printout
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
4
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);’
:: SUCCESS
Test B: Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5
:: SUCCESS
Test C: Remove number 3, 7, and then 6
:: SUCCESS
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’
:: SUCCESS
Test E: Insert number -1 at index ‘vector.Count+1’
:: SUCCESS
Test F: Remove number at index 4, then number index 0, and then number at index ‘vector.Count-1’
:: SUCCESS
Test G: Remove number at index ‘vector.Count’
:: SUCCESS
Test H: Run a sequence of operations:
vector.Contains(1);
:: SUCCESS
vector.Contains(2);
:: SUCCESS
vector.Contains(4);
:: SUCCESS
vector.Add(4); vector.Contains(4);
:: SUCCESS
Test I: Print the content of the vector via calling vector.ToString();
[2,8,5,1,8,50,5,60,5,4]
:: SUCCESS
Test J: Clear the content of the vector via calling vector.Clear();
:: SUCCESS
——————- SUMMARY ——————-
Tests passed: ABCDEFGHIJ