Data Structure and Algorithms- Tasks to be completed
n_dhruva
archive1.zipSIT221-Practical Task 1.2.pdf
SIT221 Data Structures and Algorithms Trimester 2, 2019
1
Practical Task 1.2 (Credit Task)
Submission deadline: 10:00am Monday, July 29 Discussion deadline: 10:00am Saturday, August 10
General Instructions
1. Your task is to extend the functionality of the generic data structure Vector<T>, which you should have already developed as part of the pass task 1.1.
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, or alternatively, alter the project inherited from task 1.1. Note that file Tester.cs contains a prepared main method important for the purpose of debugging and testing the extended version of the Vector<T> class. Another file, Vector.cs, contains a template of the Vector<T> class and gives an example of the following method:
T Find(Func<T, bool> searchCriteria) Searches for an element that matches the conditions defined by the specified delegate searchCriteria, and returns the first occurrence within the entire Vector<T>. If there is no element matching the search criteria, the method returns the default value for type T. It thows ArgumentNullException when searchCriteria is null.
The given prototype of the Vector<T> class should help you with development of the functionality required in this task. Explore the existing code and adapt it for other methods.
3. Implement the following methods as part of the Vector<T> class:
T Max() This method returns the maximum value in a generic sequence. If the source sequence is empty, it returns value which is default for the type T.
T Min() This method returns the minimum value in a generic sequence. If the source sequence is empty, it returns value which is default for the type T.
Vector<T> FindAll(Func<T, bool> searchCriteria) Retrieves all the elements that match the conditions defined by the specified delegate searchCriteria. This method returns an object of the Vector<T> as a newly created vector that contains all the elements that match the conditions, if found; otherwise, an empty Vector<T>. It throws ArgumentNullException when searchCriteria is null.
int RemoveAll(Func<T, bool> filterCriteria) Removes all the elements that match the conditions defined by the specified delegate filterCriteria. This method returns the number of elements removed from the Vector<T>. It throws ArgumentNullException when filterCriteria is null.
In order to implement the Min and Max methods properly, use the Comparer<T> object that you can obtain from the Default property of the Comparer<T> class as follows:
Comparer<T> comparer = Comparer<T>.Default;
The comparer allows you to call its Compare() method to compare two variables of type T. This is useful when you need to determine whether one variable is greater than another. To read more about the Default property, check the reference
https://msdn.microsoft.com/en‐us/library/cfttsh47(v=vs.110).aspx
SIT221 Data Structures and Algorithms Trimester 2, 2019
2
Furthermore, explore related articles in MSDN service. In addition, read about the default value for type T to complete these two methods. See, for example,
https://github.com/dotnet/docs/blob/master/docs/csharp/programming‐guide/statements‐ expressions‐operators/default‐value‐expressions.md
To complete other methods, you should review some advanced concepts such as delegates and Lambda expressions, which you have already studied in SIT232 unit on Object‐Oriented Programming last trimester. Thus, you may use the lecture notes of that unit or go through the following tutorial
https://www.codeproject.com/Articles/47887/C‐Delegates‐Anonymous‐Methods‐and‐Lambda‐ Expressio
Note that you should focus on the use of anonymous delegates as they serve as an argument for search criteria in methods such as Find, FindAll and RemoveAll.
4. As you progress with the implementation of the Vector<T> class, you should start using the Tester class to extensively 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.
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 this 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 must 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.
SIT221 Data Structures and Algorithms Trimester 2, 2019
3
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.
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 solution after the submission deadline and will not discuss it after the discussion deadline. If you fail one of the deadlines, you fail this task that may impact your performance and your final grade in 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. 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: 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: Run a sequence of operations:
Find number that is greater than 3 and less than 7, i.e. 'e => e > 3 && e < 7'
:: SUCCESS
Find number that is either 10 or 8, i.e. 'e => e == 10 || e == 8'
:: SUCCESS
Find number that is not 2, i.e. 'e => e != 2'
:: SUCCESS
Find number that is greater than 20, i.e. 'e => e > 20'
:: SUCCESS
Find the first odd number, i.e. 'e => (e % 2) == 1'
:: SUCCESS
Find the number that is divided by 11 without remainder, i.e. 'e => (e % 11) == 0'
:: SUCCESS
Test D: Find the minimum of the sequence
:: SUCCESS
Test E: Find the maximum of the sequence
:: SUCCESS
SIT221 Data Structures and Algorithms Trimester 2, 2019
4
Test F: Find all numbers that are greater than 3 and less than 7, i.e. 'e => e > 3 && e < 7'
:: SUCCESS
Test G: Find all numbers that is either 10 or 8, i.e. 'e => e == 10 || e == 8'
:: SUCCESS
Test H: Find all odd numbers, i.e. 'e => (e % 2) == 1'
:: SUCCESS
Test I: Find all odd numbers that are divided by 11 without remainder, i.e. 'e => (e % 11) == 0'
:: SUCCESS
Test J: Remove all even numbers, i.e. 'e => (e % 2) == 0'
:: SUCCESS
------------------- SUMMARY -------------------
Tests passed: ABCDEFGHIJ
SIT221-Practical Task 3.1.pdf
SIT221 Data Structures and Algorithms Trimester 2, 2019
1
Practical Task 3.1 (Pass Task)
Submission deadline: 10:00am Monday, August 5 Discussion deadline: 10:00am Saturday, August 31
General Instructions
The purpose of this task is to study implementation of classical sorting algorithms such as Bubble Sort, Insertion Sort, and Selection Sort.
1. Explore the program code attached to this task. Create a new Microsoft Visual Studio project and import the Vector.cs file, or alternatively, extend the project inherited from Task 2.1 by copying the missing code from the enclosed template for the Vector<T> class. Import the Tester.cs file to the project to access the prepared Main method important for the purpose of debugging and testing the required algorithmic solutions.
2. Your first step in this task is to figure out how particular sorting algorithms represented via unique classes can be linked to the Vector<T> class you should have completed through Tasks 1.1 and 1.2. The Vector<T> class must have ability to flexibly switch between possible algorithms at any time when a user wants to change the sorting technique in use. In fact, a simple solution to implement this linkage is an interface that every class providing sorting functionality must implement. Such interface, named ISorter, is already prepared for you as part of the ISorter.cs file. Study the method’s signature that the interface ensures. This method is generic and has the following purpose:
Sort<K>( K[] sequence, IComparer<K> comparer ) Sorts the elements in the entire one‐dimensional array of generic type K using the specified comparer IComparer<K>. When the comparer is not specified, i.e. is null, the default comparer Comparer<K>.Default is applied.
Note that it imposes a constraint on the type K such that K must implement the IComparable<K> interface. This is done to guarantee that the actual data type substituting K in practice implements a default comparer, therefore the Sort<K> can sort elements of that type according to the default ordering rule determined by the IComparable<K>.
3. Now, switch to the attached template of the Vector<T> class. The given class has a public property, named Sorter, implementing the aforementioned ISorter interface. The purpose of the property is to refer to a particular instance of the sorting algorithm that is currently in use by the Vector<T> class. Note that it realizes so‐called Class Aggregation as a particular form of class relationship in terms of object‐oriented programming design. This makes the chosen sorting algorithm encapsulated as a class, e.g. BubbleSort or InsertionSort, so that it becomes “a part of” the Vector<T> class. (To review possible class relationships, explore Chapter 4 of the SIT232 Workbook, page 99). One may read and write to this property; that is, to get/set a reference to the object serving as a sorting algorithm. Obviously, by changing the value of this property, one may also switch the sorting approach in use.
By default, this Sorter property of the Vector<T> class refers to the built‐in internal class DefaultSorter, which implements the Sort<K> method prescribed by the imposed ISorter interface. The DefaultSorter class delegates sorting to the Array.Sort method, which you should be familiar with based on Task 2.1. Because of this, by default, the both Sort() and Sort(IComparer<T> comparer) methods guarantee exactly the same behaviour as supposed in Task 2.1.
4. Implement three sorting algorithms: Bubble Sort, Insertion Sort, and Selection Sort. For this purpose, create three new classes, i.e. BubbleSort, InsertionSort, and SelectionSort, respectively. Ensure that the new classes implement the ISorter interface along with its prescribed method Sort<K>. Each class must have a default constructor. You may add any extra private methods and attributes if necessary. You should
SIT221 Data Structures and Algorithms Trimester 2, 2019
2
rely on the code of DefaultSorter as an example of how your classes are to be implemented. Therefore, explore the code of the method and how it deals with the default comparer, i.e. the Comparer<K>.Default.
5. As you progress with the implementation of the algorithms, you should start using the Tester class in order to test them for potential logical issues and runtime errors. This (testing) part of the task is as important as coding. You may wish to extend it with extra test cases to be sure that your solutions are checked against other potential mistakes. To enable the tests, remember to uncomment the corresponding code lines. Remember that you may change the sorting approach for an instance of the Vector<T> class by referring its Sorter property to a new object. For example,
vector.Sorter = new BubbleSort();
should enable the Bubble Sort algorithm encoded via the BubbleSort class. Check whether you test the right algorithm.
Further Notes
Explore Chapter 7 of SIT221 Workbook available in CloudDeakin in Resources Additional Course Resources Resources on Algorithms and Data Structures SIT221 Workbook. It starts with general explanation of algorithm complexity and describes Bubble Sort, Insertion Sort, and Selection Sort algorithms. Study the provided examples and follow the pseudocodes as you progress with coding of the algorithms.
The implementation of the Insertion Sort algorithm is also detailed in Chapter 3.1.2 of the course book “Data Structures and Algorithms in Java” by Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser (2014). You may access this 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.
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.
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
SIT221 Data Structures and Algorithms Trimester 2, 2019
3
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.
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. 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: Sort integer numbers applying Default Sort with AscendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]
:: SUCCESS
Test B: Sort integer numbers applying Default Sort with DescendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]
:: SUCCESS
Test C: Sort integer numbers applying Default Sort with EvenNumberFirstComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [724,596,958,752,120,122,966,772,722,100,780,312,236,213,995,263,175,299,511,333]
:: SUCCESS
Test D: Sort integer numbers applying BubbleSort with AscendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]
:: SUCCESS
Test E: Sort integer numbers applying BubbleSort with DescendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
SIT221 Data Structures and Algorithms Trimester 2, 2019
4
Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]
:: SUCCESS
Test F: Sort integer numbers applying BubbleSort with EvenNumberFirstComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [724,596,958,752,120,122,966,772,722,100,780,312,236,213,995,263,175,299,511,333]
:: SUCCESS
Test G: Sort integer numbers applying SelectionSort with AscendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]
:: SUCCESS
Test H: Sort integer numbers applying SelectionSort with DescendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]
:: SUCCESS
Test I: Sort integer numbers applying SelectionSort with EvenNumberFirstComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [236,312,780,100,722,966,724,122,120,752,958,596,772,175,511,333,213,299,995,263]
:: SUCCESS
Test J: Sort integer numbers applying InsertionSort with AscendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [100,120,122,175,213,236,263,299,312,333,511,596,722,724,752,772,780,958,966,995]
:: SUCCESS
Test K: Sort integer numbers applying InsertionSort with DescendingIntComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [995,966,958,780,772,752,724,722,596,511,333,312,299,263,236,213,175,122,120,100]
:: SUCCESS
Test L: Sort integer numbers applying InsertionSort with EvenNumberFirstComparer:
Intital data: [333,236,312,780,100,722,511,966,213,724,122,120,263,175,752,958,596,299,995,772]
Resulting order: [236,312,780,100,722,966,724,122,120,752,958,596,772,333,511,213,263,175,299,995]
:: SUCCESS
------------------- SUMMARY -------------------
Tests passed: ABCDEFGHIJKL
Practical Task 1.2-resources.rar
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 { Console.WriteLine("\nTest A: Create a new vector by calling 'Vector<int> vector = new Vector<int>(50);'"); vector = new Vector<int>(50); 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 an 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: Run a sequence of operations: "); Console.WriteLine("Find number that is greater than 3 and less than 7, i.e. 'e => e > 3 && e < 7'"); if (vector.Find(e => e > 3 && e < 7) == 6) Console.WriteLine(" :: SUCCESS"); else throw new Exception("The right number is 6"); Console.WriteLine("Find number that is either 10 or 8, i.e. 'e => e == 10 || e == 8'"); if (vector.Find(e => e == 10 || e == 8) == 8) Console.WriteLine(" :: SUCCESS"); else throw new Exception("The right number is 8"); Console.WriteLine("Find number that is not 2, i.e. 'e => e != 2'"); ; if (vector.Find(e => e != 2) == 6) Console.WriteLine(" :: SUCCESS"); else throw new Exception("The right number is 6"); Console.WriteLine("Find number that is greater than 20, i.e. 'e => e > 20'"); ; if (vector.Find(e => e > 20) == 0) Console.WriteLine(" :: SUCCESS"); else throw new Exception("There is no such number. The right number is 0 as zero is the 'default(T)' value for type 'int'"); Console.WriteLine("Find the first odd number, i.e. 'e => (e % 2) == 1'"); ; if (vector.Find(e => (e % 2) == 1) == 5) Console.WriteLine(" :: SUCCESS"); else throw new Exception("The right number is 5"); Console.WriteLine("Find the number that is divided by 11 without remainder, i.e. 'e => (e % 11) == 0'"); if (vector.Find(e => (e % 11) == 0) == 0) Console.WriteLine(" :: SUCCESS"); else throw new Exception("There is no such number. The right number is 0 as zero is the 'default(T)' value for type 'int'"); result = result + "C"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\nTest D: Find the minimum of the sequence"); int min = vector.Min(); if (min != 1) throw new Exception(min + " is an invalid minimum number of the sequence"); 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: Find the maximum of the sequence"); int max = vector.Max(); if (max != 8) throw new Exception(max + " is an invalid maximum number of the sequence"); Console.WriteLine(" :: SUCCESS"); result = result + "E"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 6 try { Console.WriteLine("\nTest F: Find all numbers that are greater than 3 and less than 7, i.e. 'e => e > 3 && e < 7'"); if (!CheckIntSequence(new int[] { 6, 5, 5, 5, 5 }, vector.FindAll(e => e > 3 && e < 7))) throw new Exception("Operation returns an 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: Find all numbers that is either 10 or 8, i.e. 'e => e == 10 || e == 8'"); if (!CheckIntSequence(new int[] { 8, 8 }, vector.FindAll(e => e == 10 || e == 8))) throw new Exception("Operation returns an incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "G"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 8 try { Console.WriteLine("\nTest H: Find all odd numbers, i.e. 'e => (e % 2) == 1'"); if (!CheckIntSequence(new int[] { 5, 5, 1, 5, 3, 5 }, vector.FindAll(e => (e % 2) == 1))) throw new Exception("Operation returns an incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "H"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 9 try { Console.WriteLine("\nTest I: Find all odd numbers that are divided by 11 without remainder, i.e. 'e => (e % 11) == 0'"); if (!CheckIntSequence(new int[] { }, vector.FindAll(e => (e % 11) == 0))) throw new Exception("Operation returns an incorrect sequence of integers"); 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: Remove all even numbers, i.e. 'e => (e % 2) == 0'"); int check = vector.RemoveAll(e => (e % 2) == 0); if (check != 4) throw new Exception(check + " is a wrong number of removed integers"); if (!CheckIntSequence(new int[] { 5, 5, 1, 5, 3, 5 }, vector)) throw new Exception("Vector stores an incorrect sequence of integers"); 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; private set; } = 0; // 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[data.Length + 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 == data.Length) 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; } public T Find(Func<T, bool> searchCriteria) { if (searchCriteria == null) throw new ArgumentNullException("Search criteria is null."); for (int i = 0; i < Count; i++) { if (searchCriteria(data[i])) return data[i]; } return default(T); } // 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) //For Test D, Test E and Test H { if( index == Count ) { Add(element); } else if ( index > Count ) { throw new IndexOutOfRangeException(); } else { T prev = data[index]; data[index] = element; for (var i = index + 1; i < Count; i++) { T next = data[i]; data[i] = prev; prev = next; } Add(prev); } } public void Clear() //For Test J { data = new T[0]; //can change values and try so many different things Count = 0; } public bool Contains(T element) //For Test H { for (var i = 0; i < Count; i++) { if (data[i].Equals(element)) return true; } return false; } public bool Remove(T element) //For Test C { int index = IndexOf(element); if( index != -1) { RemoveAt(index); return true; } else { return false; } } public void RemoveAt(int index) //For Test F and Test G { if( index >= Count ) { throw new IndexOutOfRangeException(); } T[] newData = new T[Count - 1]; for (var i = 0; i < index; i++) { newData[i] = data[i]; } for (var i = index + 1; i < Count; i++) { newData[i-1] = data[i]; } data = newData; Count = Count - 1; } public override string ToString() //For Test I { StringBuilder sb = new StringBuilder(); sb.Append("["); for (var i = 0; i < Count; i++) { if( i == 0 ) { sb.Append(data[i]); } else { sb.Append("," + data[i]); } } sb.Append("]"); return sb.ToString(); } public T Max() { // You should replace this plug by your code. throw new NotImplementedException(); } public T Min() { // You should replace this plug by your code. throw new NotImplementedException(); } public Vector<T> FindAll(Func<T, bool> searchCriteria) { // You should replace this plug by your code. throw new NotImplementedException(); } public int RemoveAll(Func<T, bool> filterCriteria) { // You should replace this plug by your code. throw new NotImplementedException(); } } }
Practical Task 3.1-resources.zip
Vector.cs
using System; using System.Collections.Generic; using System.Text; namespace Vector { public class Vector<T> where T : IComparable<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; } public ISorter Sorter { set; get; } = new DefaultSorter(); internal class DefaultSorter : ISorter { public void Sort<K>(K[] sequence, IComparer<K> comparer) where K : IComparable<K> { if (comparer == null) comparer = Comparer<K>.Default; Array.Sort(sequence, comparer); } } public void Sort() { if (Sorter == null) Sorter = new DefaultSorter(); Array.Resize(ref data, Count); Sorter.Sort(data, null); } public void Sort(IComparer<T> comparer) { if (Sorter == null) Sorter = new DefaultSorter(); Array.Resize(ref data, Count); if (comparer == null) Sorter.Sort(data, null); else Sorter.Sort(data, comparer); } } }
ISorter.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Vector { public interface ISorter { void Sort<K>(K[] sequence, IComparer<K> comparer) where K : IComparable<K>; } }
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; } } class Tester { private static bool CheckAscending(Vector<int> vector) { for (int i = 0; i < vector.Count - 1; i++) if (vector[i] > vector[i + 1]) return false; return true; } private static bool CheckDescending(Vector<int> vector) { for (int i = 0; i < vector.Count - 1; i++) if (vector[i] < vector[i + 1]) return false; return true; } private static bool CheckEvenNumberFirst(Vector<int> vector) { for (int i = 0; i < vector.Count - 1; i++) if (vector[i] % 2 > vector[i + 1] % 2) return false; return true; } static void Main(string[] args) { string result = ""; int problem_size = 20; int[] data = new int[problem_size]; data[0] = 333; Random k = new Random(1000); for (int i = 1; i < problem_size; i++) data[i] = 100 + k.Next(900); Vector<int> vector = new Vector<int>(problem_size); // ------------------ Default Sort ---------------------------------- try { Console.WriteLine("\nTest A: Sort integer numbers applying Default Sort with AscendingIntComparer: "); vector = new Vector<int>(problem_size); vector.Sorter = null; for (int i = 0; i < problem_size; i++) vector.Add(data[i]); Console.WriteLine("Intital data: " + vector.ToString()); vector.Sort(new AscendingIntComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckAscending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "A"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } try { Console.WriteLine("\nTest B: Sort integer numbers applying Default Sort with DescendingIntComparer: "); vector = new Vector<int>(problem_size); vector.Sorter = null; for (int i = 0; i < problem_size; i++) vector.Add(data[i]); Console.WriteLine("Intital data: " + vector.ToString()); vector.Sort(new DescendingIntComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckDescending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "B"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } try { Console.WriteLine("\nTest C: Sort integer numbers applying Default Sort with EvenNumberFirstComparer: "); vector = new Vector<int>(problem_size); vector.Sorter = null; for (int i = 0; i < problem_size; i++) vector.Add(data[i]); Console.WriteLine("Intital data: " + vector.ToString()); vector.Sort(new EvenNumberFirstComparer()); Console.WriteLine("Resulting order: " + vector.ToString()); if (!CheckEvenNumberFirst(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS"); result = result + "C"; } catch (Exception exception) { Console.WriteLine(" :: FAIL"); Console.WriteLine(exception.ToString()); result = result + "-"; } // ------------------ BubbleSort ---------------------------------- //try //{ // Console.WriteLine("\nTest D: Sort integer numbers applying BubbleSort with AscendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new BubbleSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new AscendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckAscending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "D"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest E: Sort integer numbers applying BubbleSort with DescendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new BubbleSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new DescendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckDescending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "E"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest F: Sort integer numbers applying BubbleSort with EvenNumberFirstComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new BubbleSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new EvenNumberFirstComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckEvenNumberFirst(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "F"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} // ------------------ SelectionSort ---------------------------------- //try //{ // Console.WriteLine("\nTest G: Sort integer numbers applying SelectionSort with AscendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new SelectionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new AscendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckAscending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "G"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest H: Sort integer numbers applying SelectionSort with DescendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new SelectionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new DescendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckDescending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "H"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest I: Sort integer numbers applying SelectionSort with EvenNumberFirstComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new SelectionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new EvenNumberFirstComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckEvenNumberFirst(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "I"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} // ------------------ InsertionSort ---------------------------------- //try //{ // Console.WriteLine("\nTest J: Sort integer numbers applying InsertionSort with AscendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new InsertionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new AscendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckAscending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "J"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest K: Sort integer numbers applying InsertionSort with DescendingIntComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new InsertionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new DescendingIntComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckDescending(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "K"; //} //catch (Exception exception) //{ // Console.WriteLine(" :: FAIL"); // Console.WriteLine(exception.ToString()); // result = result + "-"; //} //try //{ // Console.WriteLine("\nTest L: Sort integer numbers applying InsertionSort with EvenNumberFirstComparer: "); // vector = new Vector<int>(problem_size); // vector.Sorter = new InsertionSort(); // for (int i = 0; i < problem_size; i++) vector.Add(data[i]); // Console.WriteLine("Intital data: " + vector.ToString()); // vector.Sort(new EvenNumberFirstComparer()); // Console.WriteLine("Resulting order: " + vector.ToString()); // if (!CheckEvenNumberFirst(vector)) throw new Exception("Sorted vector has an incorrect sequence of integers"); // Console.WriteLine(" :: SUCCESS"); // result = result + "L"; //} //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 4.1.pdf
SIT221 Data Structures and Algorithms Trimester 2, 2019
1
Practical Task 4.1 (Pass Task)
Submission deadline: 10:00am Monday, August 18 Discussion deadline: 10:00am Saturday, August 31
General Instructions
A skip‐list is a probabilistic linked‐list‐like data structure that expects, for an ordered sequence of elements, a log runtime complexity for basic operations such as searching, insertion and removal. Importantly, it supports a quick insertion that is not possible for a simple array. Fast operations are made possible by maintaining a linked hierarchy of layered linked‐list subsequences, with each successive subsequence skipping over fewer elements than the previous.
1. This task asks you to conduct a small research about this data structure. You can find its detailed explanation in chapter 10.4 of the course book “Data Structures and Algorithms in Java”. You, of course, may explore and refer to any other resources covering this topic. We expect you to grasp the idea and structure of a skip‐list along with standard operations on it. As the results of your study, you must be able to answer the following questions and discuss the related issues:
‐ How exactly is a skip‐list constructed from a series of linked‐lists? What does each of the linked‐lists constituting a skip‐list store?
‐ What is a height of a skip‐list? How can we determine the height when adding new elements? ‐ What is the runtime complexity for searching, insertion, and removal operations on a skip‐list? What
does it mean when we say that the complexity of these operations is ‘expected’? What is the difference between an expected bound on runtime complexity and a worst‐case bound?
‐ Compare a skip‐list to other data‐structures that you should already know, e.g. sorted arrays, singly and doubly linked lists. What are the advantages and disadvantages of a skip‐list? Compare the complexities of the basic operations offered by a skip‐list to those of the mentioned data structures.
‐ How exactly does each of the standard operations work? Here, you should be ready to explain the sequence of actions required to perform searching, insertion, and removal from a skip‐list.
2. Solve the following numeric example. Given the following sequence of coin tosses, where H stands for head and T stands for tails:
T H T T H H T T H T H T H H T H H T T H H T H T T H T T T H T H T H T T H T H H T T.
Build a skip‐list containing the following values:
1 40 11 85 86 5 0 8.
Show the full state of the skip‐list after each insertion. Note that you must explicitly state the meaning you attach to heads and tails at the start of your answer. Remember that you must start tossing the coin from left side of the sequence and may not need to use all the tosses to build the skip‐list. You may assume as a height resolution policy that we allow a tower to grow as long as heads keep getting returned from the given sequence, which emulates a random number generator.
Further Notes
You will find the answer to this task by reading chapter 10.4 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.
SIT221 Data Structures and Algorithms Trimester 2, 2019
2
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. Note that this is a theoretical task, thus we do not expect you to write any program code.
Meet with your marking tutor to explain your solutions. When the solution is hand‐written, do not forget to bring it with you.
Show to your tutor how the standard operations on a skip‐list are performed. Cloud students must record a short video explaining their work on the numeric instance along with execution of searching, insertion and removal operations based on the example.
Answer all additional (theoretical) questions that your tutor may ask you. 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.
