Data Structure and Algorithms- Tasks to be completed

archive.zip

Home >Computer Science homework help >Data Structure and Algorithms- Tasks to be completed

Practical Task 2.1-resources.zip

Tester.cs

using System; using System.Collections.Generic; namespace Vector { public class AscendingIntComparer : IComparer<int> { public int Compare(int A, int B) { return A - B; } } public class DescendingIntComparer : IComparer<int> { public int Compare(int A, int B) { return B - A; } } public class EvenNumberFirstComparer : IComparer<int> { public int Compare(int A, int B) { return A % 2 - B % 2; } } public class Student { public string Name { get; set; } public int Id { get; set; } public override string ToString() { return Id + "[" + Name + "]"; } } public class AscendingIDComparer { } public class DescendingNameDescendingIdComparer { } // class Tester { private static bool CheckIntSequence(int[] certificate, Vector<int> vector) { if (certificate.Length != vector.Count) return false; for (int i = 0; i < certificate.Length; i++) { if (certificate[i] != vector[i]) return false; } return true; } static void Main(string[] args) { Vector<int> vector = null; string result = ""; // test 1 try { Console.WriteLine("\nTest A: Run a sequence of operations: "); Console.WriteLine("Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'"); vector = new Vector<int>(50); Console.WriteLine("Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9"); vector.Add(2); vector.Add(6); vector.Add(8); vector.Add(5); vector.Add(5); vector.Add(1); vector.Add(8); vector.Add(5); vector.Add(3); vector.Add(5); vector.Add(7); vector.Add(1); vector.Add(4); vector.Add(9); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }, vector)) throw new Exception("Vector stores an incorrect sequence of integers after adding new elements"); Console.WriteLine("Sort the integers in the default order defined by the native CompareTo() method"); //vector.Sort(); int[] array = new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }; Array.Sort(array, 0, 14); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckIntSequence(array, vector)) throw new Exception("Vector stores an incorrect sequence of integers after sorting them"); Console.WriteLine(" :: SUCCESS"); result = result + "A"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 2 try { Console.WriteLine("\nTest B: Run a sequence of operations: "); Console.WriteLine("Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'"); vector = new Vector<int>(50); Console.WriteLine("Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9"); vector.Add(2); vector.Add(6); vector.Add(8); vector.Add(5); vector.Add(5); vector.Add(1); vector.Add(8); vector.Add(5); vector.Add(3); vector.Add(5); vector.Add(7); vector.Add(1); vector.Add(4); vector.Add(9); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }, vector)) throw new Exception("Vector stores an incorrect sequence of integers after adding new elements"); Console.WriteLine("Sort the integers in the order defined by the AscendingIntComparer class"); //vector.Sort(new AscendingIntComparer()); int[] array = new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }; Array.Sort(array, 0, 14, new AscendingIntComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckIntSequence(array, vector)) throw new Exception("Vector stores an incorrect sequence of integers after sorting them"); Console.WriteLine(" :: SUCCESS"); result = result + "B"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 3 try { Console.WriteLine("\nTest C: Run a sequence of operations: "); Console.WriteLine("Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'"); vector = new Vector<int>(50); Console.WriteLine("Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9"); vector.Add(2); vector.Add(6); vector.Add(8); vector.Add(5); vector.Add(5); vector.Add(1); vector.Add(8); vector.Add(5); vector.Add(3); vector.Add(5); vector.Add(7); vector.Add(1); vector.Add(4); vector.Add(9); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }, vector)) throw new Exception("Vector stores an incorrect sequence of integers after adding new elements"); Console.WriteLine("Sort the integers in the order defined by the DescendingIntComparer class"); //vector.Sort(new DescendingIntComparer()); int[] array = new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }; Array.Sort(array, 0, 14, new DescendingIntComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckIntSequence(array, vector)) throw new Exception("Vector stores an incorrect sequence of integers after sorting them"); Console.WriteLine(" :: SUCCESS"); result = result + "C"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\nTest D: Run a sequence of operations: "); Console.WriteLine("Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'"); vector = new Vector<int>(50); Console.WriteLine("Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9"); vector.Add(2); vector.Add(6); vector.Add(8); vector.Add(5); vector.Add(5); vector.Add(1); vector.Add(8); vector.Add(5); vector.Add(3); vector.Add(5); vector.Add(7); vector.Add(1); vector.Add(4); vector.Add(9); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }, vector)) throw new Exception("Vector stores an incorrect sequence of integers after adding new elements"); Console.WriteLine("Sort the integers in the order defined by the EvenNumberFirstComparer class"); //vector.Sort(new EvenNumberFirstComparer()); int[] array = new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9 }; Array.Sort(array, 0, 14, new EvenNumberFirstComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckIntSequence(array, vector)) throw new Exception("Vector stores an incorrect sequence of integers after sorting them"); Console.WriteLine(" :: SUCCESS"); result = result + "D"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 5 try { string[] names = new string[] { "Kelly", "Cindy", "John", "Andrew", "Richard", "Michael", "Guy", "Elicia", "Tom", "Iman", "Simon", "Vicky" }; Random random = new Random(100); Console.WriteLine("\nTest E: Run a sequence of operations: "); Console.WriteLine("Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'"); Vector<Student> students = new Vector<Student>(); for (int i = 0; i < 14; i++) { Student student = new Student() { Name = names[random.Next(0, names.Length)], Id = i }; Console.WriteLine("Add student with record: " + student.ToString()); students.Add(student); } Console.WriteLine("Sort the students in the default order defined by the native CompareTo() method"); //students.Sort(); Console.WriteLine("Print the vector of students via students.ToString();"); Console.WriteLine(students.ToString()); Console.WriteLine(" :: SUCCESS"); result = result + "E"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 6 try { string[] names = new string[] { "Kelly", "Cindy", "John", "Andrew", "Richard", "Michael", "Guy", "Elicia", "Tom", "Iman", "Simon", "Vicky" }; Random random = new Random(100); Console.WriteLine("\nTest F: Run a sequence of operations: "); Console.WriteLine("Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'"); Vector<Student> students = new Vector<Student>(); for (int i = 0; i < 14; i++) { Student student = new Student() { Name = names[random.Next(0, names.Length)], Id = i }; Console.WriteLine("Add student with record: " + student.ToString()); students.Add(student); } Console.WriteLine("Sort the students in the order defined by the AscendingIDComparer class"); //students.Sort(new AscendingIDComparer()); Console.WriteLine("Print the vector of students via students.ToString();"); Console.WriteLine(students.ToString()); Console.WriteLine(" :: SUCCESS"); result = result + "F"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 7 try { string[] names = new string[] { "Kelly", "Cindy", "John", "Andrew", "Richard", "Michael", "Guy", "Elicia", "Tom", "Iman", "Simon", "Vicky" }; Random random = new Random(100); Console.WriteLine("\nTest G: Run a sequence of operations: "); Console.WriteLine("Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'"); Vector<Student> students = new Vector<Student>(); for (int i = 0; i < 14; i++) { Student student = new Student() { Name = names[random.Next(0, names.Length)], Id = i }; Console.WriteLine("Add student with record: " + student.ToString()); students.Add(student); } Console.WriteLine("Sort the students in the order defined by the DescendingNameDescendingIdComparer class"); //students.Sort(new DescendingNameDescendingIdComparer()); Console.WriteLine("Print the vector of students via students.ToString();"); Console.WriteLine(students.ToString()); Console.WriteLine(" :: SUCCESS"); result = result + "G"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } Console.WriteLine("\n\n ------------------- SUMMARY ------------------- "); Console.WriteLine("Tests passed: " + result); Console.ReadKey(); } } }

SIT221-Practical Task 2.2.pdf

SIT221 Data Structures and Algorithms Trimester 2, 2019

Practical Task 2.2 (Pass Task)

Submission deadline: 10:00am Monday, July 29 Discussion deadline: 10:00am Saturday, August 10

General Instructions In this task, answer all the following questions and complement each answer with a detailed explanation.

1. Conduct a small research on the Introspective Sort, which is a built‐in sorting algorithm of the Array.Sort method that you referred to in task 2.1P. Is it a unique algorithmic solution or a combination of several sorting algorithms? Does this method result in an unstable sort; that is, if two elements are equal, their order might not be preserved? Or does it perform a stable sort, which preserves the order of elements that are equal? What is the time complexity of this sorting algorithm?

2. Task 1.1P asked you to develop / provided you with a number of the Vector<T> class’s methods (and properties), such as Count, Capacity, Add, IndexOf, Insert, Clear, Contains, Remove, and RemoveAt. What is the algorithmic complexity of each of these operations? Does your implementation match the complexity of the corresponding operations offered by Microsoft .Net Framework for its List<T> collection? The following link should help you to answer this question

https://msdn.microsoft.com/en‐us/library/6sh2ey19(v=vs.110).aspx

3. Is it true that algorithm always takes longer to run than an log algorithm? Explain your answer. 4. Answer whether the following statements are right or wrong and explain your answers.

 10   

Further Notes  To get more insights on the Big‐O notation and algorithmic complexity, you may wish to watch the

YouTube recording available at https://youtu.be/yd8D2NjzqbU.  You may find the attached Asymptotic Cheat Sheet useful to clarify the mathematical notation.  You will find ultimate answers to these tasks by exploring chapters 4.1.‐4.3 of the course book “Data

Structures and Algorithms in Java” by Michael T. Goodrich, Irvine Roberto Tamassia, and Michael H. Goldwasser (2014). You may access the book on‐line for free from the reading list application in CloudDeakin available in Resources  Additional Course Resources  Resources on Algorithms and Data Structures  Course Book: Data structures and algorithms in Java.

Marking Process and Discussion To get this task completed, you must finish the following steps strictly on time:

 Submit your answers to the task via OnTrack submission system. You may submit a hand‐written and then scanned document, but ensure that the text is very clear to read.

 Meet with your marking tutor to explain your solutions.

SIT221 Data Structures and Algorithms Trimester 2, 2019

 Answer all additional (theoretical) questions that your tutor may 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 solutions after the submission deadline and will not discuss them 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.

6.042/18.062J Mathematics for Computer Science October 19, 2004 Tom Leighton and Ronitt Rubinfeld

The Asymptotic Cheat Sheet

Asymptotic notation consists of six funny symbols used to describe the relative growth rates of functions. These six symbols are defined in the table below.

f = Θ(g) f grows at the same rate as g There exists an n0 and constants c1, c2 > 0 such that for all n > n0, c1g(n) ≤ |f(n)| ≤ c2g(n).

f = O(g) f grows no faster than g There exists an n0 and a constant c > 0 such that for all n > n0, |f(n)| ≤ cg(n).

f = Ω(g) f grows at least as fast as g There exists an n0 and a constant c > 0 such that for all n > n0, cg(n) ≤ |f(n)|.

f = o(g) f grows slower than g For all c > 0, there exists an n0 such that for all n > n0, |f(n)| ≤ cg(n).

f = ω(g) f grows faster than g For all c > 0, there exists an n0 such that for all n > n0, cg(n) ≤ |f(n)|.

f ∼ g f/g approaches 1 limn→∞ f(n)/g(n) = 1

The ∼ and Θ notations are confusingly similar; qualitatively, functions related by ∼ must be even more nearly alike then functions related by Θ. The ω notation makes the table nice and symmetric, but is almost never used in practice. Some asymptotic relation- ships between functions imply other relationships. Some examples are listed below.

f = O(g) and f = Ω(g) ⇔ f = Θ(g) f = o(g) ⇒ f = O(g) f = O(g) ⇔ g = Ω(f) f = ω(g) ⇒ f = Ω(g) f = o(g) ⇔ g = ω(f) f ∼ g ⇒ f = Θ(g)

12 The Asymptotic Cheat Sheet

Limits

The definitions of the various asymptotic notations are closely related to the definition of a limit. As a result, limn→∞ f(n)/g(n) reveals a lot about the asymptotic relationship between f and g, provided the limit exists. The table below translates facts about the limit of f/g into facts about the asymptotic relationship between f and g.

limn→∞ f(n)/g(n) $= 0,∞ ⇒ f = Θ(g) limn→∞ f(n)/g(n) = 1 ⇒ f ∼ g limn→∞ f(n)/g(n) $= ∞ ⇒ f = O(g) limn→∞ f(n)/g(n) = 0 ⇒ f = o(g) limn→∞ f(n)/g(n) $= 0 ⇒ f = Ω(g) limn→∞ f(n)/g(n) = ∞ ⇒ f = ω(g)

Therefore, skill with limits can be helpful in working out asymptotic relationships. In particular, recall L’Hospital’s Rule:

If lim n→∞

f(n) = ∞ and lim n→∞

g(n) = ∞, then lim n→∞

f(n)

g(n) = lim

n→∞

f ′(n)

g′(n) .

Every computer scientist knows two rules of thumb about asymptotics: logarithms grow more slowly than polynomials and polynomials grow more slowly than exponen- tials. We’ll prove these facts using limits.

Theorem. For all α, k > 0:

(lnn)k = o(nα) (1) nk = o((1 + α)n) (2)

Proof.

lim n→∞

(lnn)k

nα =

(

lim n→∞

ln n

nα/k

)k ∗

(

lim n→∞

1/n

(α/k)nα/k−1

(

lim n→∞

(α/k)nα/k

= 0

lim n→∞

(1 + α)n =

(

lim n→∞

(1 + α)n/k

)k ∗

(

lim n→∞

(n/k) · (1 + α)n/k−1

= 0

The starred equalities follow from L’Hospital’s Rule.

The Asymptotic Cheat Sheet.pdf

Block Stacking

Harmonic Numbers

Products
Asymptotic Notation

Big-Oh notation

SIT221-Practical Task 2.1.pdf

SIT221 Data Structures and Algorithms Trimester 2, 2019

Practical Task 2.1 (Pass Task)

Submission deadline: 10:00am Monday, July 29 Discussion deadline: 10:00am Saturday, August 10

General Instructions 1. Your task is to enable sorting of generic data stored as part of the Vector<T> data structure, which you

should have already developed in task 1.1. You do not need to write lots of code for this task, but rather get a solid understanding of interfaces required to support sorting operations in .NET Framework, and how methods implementing these interfaces can be linked to your own code. This knowledge is crucial for you as a programmer.

2. Import the Tester.cs file to the project to access the prepared Main method important for the purpose of debugging and testing the advanced version of the Vector<T> class.

3. Start with the extension of your Vector<T> class and add the following two overloaded methods:

 void Sort() Sorts the elements in the entire Vector<T>. It relies on the static Array.Sort method, which applies the Introspective Sort. To determine the order of the elements, Array.Sort calls the default comparer Comparer<T>.Default for type T.

 void Sort(IComparer<T> comparer) Sorts the elements in the entire Vector<T> using the specified comparer. This method relies on the Array.Sort method, which applies the Introspective Sort. If the comparer is null, the method calls Array.Sort with the default comparer Comparer<T>.Default for type T.

Note that in this task you do not need to implement any sorting algorithm at all. Indeed, you should delegate sorting of generic data elements to the default built‐in sorting method realised within the Array class of .NET Framework. Specifically, you must call the Array.Sort method internally and pass the private data array of the Vector<T> as an input. Note that there are several overloaded versions of this method and you should choose two of them: One that accepts an array along with the starting index and the number of elements to define the range of sorting, and another one that expects all the mentioned parameters plus a comparer object. Read more about the standard methods of the Array class following the link:

https://msdn.microsoft.com/en‐us/library/system.array_methods(v=vs.110).aspx

When the two above methods are configured properly, you should be able to sort integers and successfully run the corresponding tests A, B, C, and D in the Tester class without compilation and runtime errors. To enable the tests, remember to uncomment the corresponding code lines.

4. Now proceed with the next step, and first explore the Student class presented in Tester.cs.

In order to make the Vector<T> class capable to perform default sorting operations on a set of generic elements of type T, you must ensure a mechanism that compares two T type elements. This mechanism will provide a default way to determine precedence for a pair of elements. To achieve this default logic, the T type itself must know how to compare one element (usually referred to this) to another given element of the same type. From the code perspective, this is enforced by the special IComparable<T> interface that type T must implement. Implementing the IComparable<T> also requires T to define the compulsory CompareTo(T another) method which eventually compares this (current) element to another element and returns an integer value that is

 less than zero, when the current instance precedes the object specified by the CompareTo method in the sort order;

SIT221 Data Structures and Algorithms Trimester 2, 2019

 zero, when this current instance occurs in the same position in the sort order as the object specified by the CompareTo method;

 greater than zero, when this current instance follows the object specified by the CompareTo method in the sort order.

Read the following article to get more insights about this interface

https://msdn.microsoft.com/en‐us/library/system.icomparable(v=vs.110).aspx

and make sure you understand all the remarks.

Hence, T refers to the Student as an actual class. You need to modify the Student class and implement IComparable<Student> interface along with its underlying CompareTo(Student another) method. Write the code so that the method arranges students in the ascending order of the ID attribute. Complete this part and pass Test E of the attached testing class. This test calls the Sort method of the Vector<T> class, which should currently delegate sorting to Array.Sort that implies IComparable<Student>. Again, uncomment the corresponding code lines to activate the test.

5. Finally, develop a so‐called comparator, a dedicated class whose purpose is ordering a pair of elements of specific type. Each comparator class implements the IComparer<T> interface, which you may learn exploring the following link:

https://msdn.microsoft.com/en‐us/library/8ehhxeaf(v=vs.110).aspx

Note that Tester.cs already has a number of examples used to sort integers in ascending, descending, or in the order that places even integers prior to odd in a sequence of numbers. Explore the enclosed code as it should help you with development of similar comparator classes for the Student class. You will see that the IComparable<Student> and the IComparer<Student> interfaces are quite similar as they both require you to provide a method for comparison of two students. The only difference is that the CompareTo(Student another) method of the IComparable<Student> operates on this and another objects, while the Compare(Student A, Student B) is to compare A and B, two objects, given as arguments. The Compare method follows the same logic as the aforementioned CompareTo method and returns an integer value indicating whether A is less than, equal to, or greater than B. For details, see

https://msdn.microsoft.com/en‐us/library/xh5ks3b3(v=vs.110).aspx

Develop two comparators for the Student class: One, say AscendingIDComparer, to sort a vector of students in ascending order of IDs, and another, say DescendingNameDescendingIdComparer, that sorts students in descending order of names, breaking ties by descending order of IDs. Check the correctness of sorting via tests F and G provided by the testing class. Make sure that students appear in the desired order. Note that the both comparators are to be the argument for the Sort(IComparer<T> comparer) method of the Vector<T> class.

Further Notes  Read Chapter 1.7 of SIT221 Workbook available in CloudDeakin in Resources  Additional Course

Resources  Resources on Algorithms and Data Structures  SIT221 Workbook. It provides a short discussion on IComparable<T> interface and implementation of collections.

 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.

SIT221 Data Structures and Algorithms Trimester 2, 2019

 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.

 Please, note that you are free in writing your own code internal (private) to the required classes and methods. Therefore, we do not give any particular instructions about this. The only important requirement is that you must fulfil the specified interface in terms of functionality (logic) and signatures of the requested methods.

 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.  Explain the implementation issues of the IComparer<T> and the IComparable<T> interfaces and the

difference between them to the 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.

Expected Printout This section displays the printout produced by the attached Tester class, specifically by its Main method. It is based on our solution. The printout is provided here to help with 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: Run a sequence of operations:

Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'

Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9

Sort the integers in the default order defined by the native CompareTo() method

Resulting order: [1,1,2,3,4,5,5,5,5,6,7,8,8,9]

:: SUCCESS

SIT221 Data Structures and Algorithms Trimester 2, 2019

Test B: Run a sequence of operations:

Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'

Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9

Sort the integers in the order defined by the AscendingIntComparer class

Resulting order: [1,1,2,3,4,5,5,5,5,6,7,8,8,9]

:: SUCCESS

Test C: Run a sequence of operations:

Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'

Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9

Sort the integers in the order defined by the DescendingIntComparer class

Resulting order: [9,8,8,7,6,5,5,5,5,4,3,2,1,1]

:: SUCCESS

Test D: Run a sequence of operations:

Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'

Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5, 7, 1, 4, 9

Sort the integers in the order defined by the EvenNumberFirstComparer class

Resulting order: [2,6,8,8,4,5,5,1,5,3,5,7,1,9]

:: SUCCESS

Test E: Run a sequence of operations:

Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'

Add student with record: 0[Vicky]

Add student with record: 1[Cindy]

Add student with record: 2[Tom]

Add student with record: 3[Simon]

Add student with record: 4[Richard]

Add student with record: 5[Vicky]

Add student with record: 6[Tom]

Add student with record: 7[Elicia]

Add student with record: 8[Richard]

Add student with record: 9[Cindy]

Add student with record: 10[Vicky]

Add student with record: 11[Guy]

Add student with record: 12[Richard]

Add student with record: 13[Michael]

Sort the students in the default order defined by the native CompareTo() method

Print the vector of students via students.ToString();

[0[Vicky],1[Cindy],2[Tom],3[Simon],4[Richard],5[Vicky],6[Tom],7[Elicia],8[Richard],9[Cindy],10[Vicky],11[Guy],12[Richard] ,13[Michael]]

:: SUCCESS

SIT221 Data Structures and Algorithms Trimester 2, 2019

Test F: Run a sequence of operations:

Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'

Add student with record: 0[Vicky]

Add student with record: 1[Cindy]

Add student with record: 2[Tom]

Add student with record: 3[Simon]

Add student with record: 4[Richard]

Add student with record: 5[Vicky]

Add student with record: 6[Tom]

Add student with record: 7[Elicia]

Add student with record: 8[Richard]

Add student with record: 9[Cindy]

Add student with record: 10[Vicky]

Add student with record: 11[Guy]

Add student with record: 12[Richard]

Add student with record: 13[Michael]

Sort the students in the order defined by the AscendingIDComparer class

Print the vector of students via students.ToString();

[0[Vicky],1[Cindy],2[Tom],3[Simon],4[Richard],5[Vicky],6[Tom],7[Elicia],8[Richard],9[Cindy],10[Vicky],11[Guy],12[Richard] ,13[Michael]]

:: SUCCESS

Test G: Run a sequence of operations:

Create a new vector of Student objects by calling 'Vector<Student> students = new Vector<Student>();'

Add student with record: 0[Vicky]

Add student with record: 1[Cindy]

Add student with record: 2[Tom]

Add student with record: 3[Simon]

Add student with record: 4[Richard]

Add student with record: 5[Vicky]

Add student with record: 6[Tom]

Add student with record: 7[Elicia]

Add student with record: 8[Richard]

Add student with record: 9[Cindy]

Add student with record: 10[Vicky]

Add student with record: 11[Guy]

Add student with record: 12[Richard]

Add student with record: 13[Michael]

Sort the students in the order defined by the DescendingNameDescendingIdComparer class

Print the vector of students via students.ToString();

[10[Vicky],5[Vicky],0[Vicky],6[Tom],2[Tom],3[Simon],12[Richard],8[Richard],4[Richard],13[Michael],11[Guy],7[Elicia],9[Cin dy],1[Cindy]]

:: SUCCESS

SIT221 Data Structures and Algorithms Trimester 2, 2019

------------------- SUMMARY -------------------

Tests passed: ABCDEFG

Practical Task 1.1-resources.zip

Tester.cs

using System; namespace Vector { class Tester { private static bool CheckIntSequence(int[] certificate, Vector<int> vector) { if (certificate.Length != vector.Count) return false; for (int i = 0; i < certificate.Length; i++) { if (certificate[i] != vector[i]) return false; } return true; } static void Main(string[] args) { Vector<int> vector = null; string result = ""; // test 1 try { int capacity = 50; Console.WriteLine("\nTest A: Create a new vector by calling 'Vector<int> vector = new Vector<int>(" + capacity + ");'"); vector = new Vector<int>(capacity); if (vector.Capacity != capacity) throw new Exception("Vector has a wrong capacity"); Console.WriteLine(" :: SUCCESS"); result = result + "A"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 2 try { Console.WriteLine("\nTest B: Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5"); vector.Add(2); vector.Add(6); vector.Add(8); vector.Add(5); vector.Add(5); vector.Add(1); vector.Add(8); vector.Add(5); vector.Add(3); vector.Add(5); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 5, 1, 8, 5, 3, 5 }, vector)) throw new Exception("Vector stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "B"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 3 try { Console.WriteLine("\nTest C: Remove number 3, 7, and then 6"); bool check = vector.Remove(3) && (!vector.Remove(7)) && vector.Remove(6); if (!CheckIntSequence(new int[] { 2, 8, 5, 5, 1, 8, 5, 5 }, vector)) throw new Exception("Vector stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "C"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\nTest 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'"); vector.Insert(6, 50); vector.Insert(0, 0); vector.Insert(vector.Count - 1, 60); vector.Insert(vector.Count, 70); if (!CheckIntSequence(new int[] { 0, 2, 8, 5, 5, 1, 8, 50, 5, 60, 5, 70 }, vector)) throw new Exception("Vector stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "D"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 5 try { Console.WriteLine("\nTest E: Insert number -1 at index 'vector.Count+1'"); vector.Insert(vector.Count + 1, -1); } catch (IndexOutOfRangeException exception) { Console.WriteLine(" :: SUCCESS"); result = result + "E"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine("Last operation is invalid and must throw IndexOutOfRangeException. Your solution does not match specification."); result = result + "-"; } // test 6 try { Console.WriteLine("\nTest F: Remove number at index 4, then number index 0, and then number at index 'vector.Count-1'"); vector.RemoveAt(4); vector.RemoveAt(0); vector.RemoveAt(vector.Count - 1); if (!CheckIntSequence(new int[] { 2, 8, 5, 1, 8, 50, 5, 60, 5 }, vector)) throw new Exception("Vector stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "F"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 7 try { Console.WriteLine("\nTest G: Remove number at index 'vector.Count'"); vector.RemoveAt(vector.Count); } catch (IndexOutOfRangeException exception) { Console.WriteLine(" :: SUCCESS"); result = result + "G"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine("Last operation is invalid and must throw IndexOutOfRangeException. Your solution does not match specification."); result = result + "-"; } // test 8 try { Console.WriteLine("\nTest H: Run a sequence of operations: "); Console.WriteLine("vector.Contains(1);"); if (vector.Contains(1)) Console.WriteLine(" :: SUCCESS"); else throw new Exception("1 must be in the vector"); Console.WriteLine("vector.Contains(2);"); if (vector.Contains(2)) Console.WriteLine(" :: SUCCESS"); else throw new Exception("2 must be in the vector"); Console.WriteLine("vector.Contains(4);"); if (!vector.Contains(4)) Console.WriteLine(" :: SUCCESS"); else throw new Exception("4 must not be in the vector"); Console.WriteLine("vector.Add(4); vector.Contains(4);"); vector.Add(4); if (vector.Contains(4)) Console.WriteLine(" :: SUCCESS"); else throw new Exception("4 must be in the vector"); result = result + "H"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 9 try { Console.WriteLine("\nTest I: Print the content of the vector via calling vector.ToString();"); Console.WriteLine(vector.ToString()); Console.WriteLine(" :: SUCCESS"); result = result + "I"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 10 try { Console.WriteLine("\nTest J: Clear the content of the vector via calling vector.Clear();"); vector.Clear(); if (!CheckIntSequence(new int[] { }, vector)) throw new Exception("Vector stores incorrect data. It must be empty."); Console.WriteLine(" :: SUCCESS"); result = result + "J"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } Console.WriteLine("\n\n ------------------- SUMMARY ------------------- "); Console.WriteLine("Tests passed: " + result); Console.ReadKey(); } } }

Vector.cs

using System; using System.Collections.Generic; using System.Text; namespace Vector { public class Vector<T> { // This constant determines the default number of elements in a newly created vector. // It is also used to extended the capacity of the existing vector private const int DEFAULT_CAPACITY = 10; // This array represents the internal data structure wrapped by the vector class. // In fact, all the elements are to be stored in this private array. // You will just write extra functionality (methods) to make the work with the array more convenient for the user. private T[] data; // This property represents the number of elements in the vector public int Count { get; private set; } = 0; // This property represents the maximum number of elements (capacity) in the vector public int Capacity { get { return data.Length; } } // This is an overloaded constructor public Vector(int capacity) { data = new T[capacity]; } // This is the implementation of the default constructor public Vector() : this(DEFAULT_CAPACITY) { } // An Indexer is a special type of property that allows a class or structure to be accessed the same way as array for its internal collection. // For example, introducing the following indexer you may address an element of the vector as vector[i] or vector[0] or ... public T this[int index] { get { if (index >= Count || index < 0) throw new IndexOutOfRangeException(); return data[index]; } set { if (index >= Count || index < 0) throw new IndexOutOfRangeException(); data[index] = value; } } // This private method allows extension of the existing capacity of the vector by another 'extraCapacity' elements. // The new capacity is equal to the existing one plus 'extraCapacity'. // It copies the elements of 'data' (the existing array) to 'newData' (the new array), and then makes data pointing to 'newData'. private void ExtendData(int extraCapacity) { T[] newData = new T[Capacity + extraCapacity]; for (int i = 0; i < Count; i++) newData[i] = data[i]; data = newData; } // This method adds a new element to the existing array. // If the internal array is out of capacity, its capacity is first extended to fit the new element. public void Add(T element) { if (Count == Capacity) ExtendData(DEFAULT_CAPACITY); data[Count++] = element; } // This method searches for the specified object and returns the zero‐based index of the first occurrence within the entire data structure. // This method performs a linear search; therefore, this method is an O(n) runtime complexity operation. // If occurrence is not found, then the method returns –1. // Note that Equals is the proper method to compare two objects for equality, you must not use operator '=' for this purpose. public int IndexOf(T element) { for (var i = 0; i < Count; i++) { if (data[i].Equals(element)) return i; } return -1; } // TODO: Your task is to implement all the remaining methods. // Read the instruction carefully, study the code examples from above as they should help you to write the rest of the code. public void Insert(int index, T element) { // You should replace this plug by your code. throw new NotImplementedException(); } public void Clear() { // You should replace this plug by your code. throw new NotImplementedException(); } public bool Contains(T element) { // You should replace this plug by your code. throw new NotImplementedException(); } public bool Remove(T element) { // You should replace this plug by your code. throw new NotImplementedException(); } public void RemoveAt(int index) { // You should replace this plug by your code. throw new NotImplementedException(); } public override string ToString() { // You should replace this plug by your code. throw new NotImplementedException(); } } }

SIT221-Practical Task 1.1.pdf

SIT221 Data Structures and Algorithms Trimester 2, 2019

Practical Task 1.1 (Pass Task)

Submission deadline: 10:00am Monday, July 29 Discussion deadline: 10:00am Saturday, August 10

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

 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  Course materials  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  Course materials  Materials 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 and install the community version of Microsoft Visual Studio 2017 available on the SIT221 unit web‐page in CloudDeakin at Resources  Course materials  Visual Studio Community 2017 Installation Package. You are free to use another code editor 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.

 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.

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 testing your code for potential logical errors. It demonstrates the correct logic rather than an expected printout in terms of text and alignment.

SIT221 Data Structures and Algorithms Trimester 2, 2019

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