1. TASK1: SORTING BENCHMARKING
In this task we want to benchmark different sorting algorithms against Microsoft Array.Sort Method. The objective of this experiment is to assess the performance (execution time) of different algorithms on different datasets. You are provided with four input datasets - 1H.txt, 1T.txt, 100T.txt, 1M.txt (please make sure to download Task1 provided files). We have selected the following sorting algorithms to use in this experiment - Insertion Sort, Selection Sort, Merge Sort, and Quick Sort.
The intended experiment scenario is as follows:
1. Run the five sorting algorithms (insertion, selection, merge and quick + Array.Sort) on the four input datasets.
2. Measure/record execution timeand memory usage of these algorithms on the input un-sorted datasets.
3. Save the output, sorted dataset to S_1H.txt, S_1T.txt, S_100T.txt, S_1M.txt
4. Re-run the same algorithms on the four new datasets (sorted), from the last step.
5. Measure/record execution time and memory usage in the second experiment on the sorted datasets.
6. Plot outcomes/measurements from step 2 and step 5 using Excel (x-axis is for different input dataset size - 100, 1000, ... - and y-axis is time in seconds or space in Kilobytes). You should have four plots: two (time and memory) on the unsorted datasets, and the other two (time and memory) on the sorted datasets.
Copy your plots & measurements table to word, explain your findings from both (unsorted & sorted) experiments - what does the running time of these algorithms tell you regarding best and worst case running time, and what did you find. Can you comment on the memory usage?
HOW TO APPROACH TASK1?
Please use the same project template provided in this unit to complete your assignment.
In the DataStructures_Algorithms project, add a folder called "Project01".
- Create a folder "Task01"
- Add an Enum called SortingAlgorithm [INSERTION, SELECTION, MERGE, QUICK, MICROSOFTSORT] - in "Task01" folder
- Add ISorter interface (ISorter.CS) that has one method: public void Sort(Enum SortingAlgorithm)
- Copy Vector class into "Task01" folder
- Modify Vector class to implement the ISorter interface - which means you need to implement the sort method above.
- Add any necessary methods to do different sorting algorithms - I mean add methods to sort Vector data using merge, selection,...
In the Runner project, add a file called RunnerProject01Task01
- Pass two command line arguments (right click on project, display properties, select debug properties, and specify the following): (i) filename and (ii) Sorting Algorithm name as inputs.
- Your Runner class should read data from the input file - argument 1, create a vector object from the input file, and then call the Sort method using specified Algorithm name - argument 2
- Finally write your sorted data to a file called S_InputFilename - e.g. S_1H.txt, and your execution time & memory to AlgorithmName_Filename_Stats file - e.g. SELECTION_1H.txt.
2. TASK2: SET THEORY CALCULATOR
In mathematics, a set is defined asa collection of distinct (no duplication) elements . These elements could be anything - numbers, characters, strings, etc.There is no particular order of the elements in a set - e.g. set S1 = {1, 2, 3} is equivalent to set S2 = {2, 1, 3}. Set theory is the branch of mathematics that studies sets, and it has many applications in real life. Some of these applications include: relational databases - e.g. MS SQLSERVER, MySQL, etc.; computer graphics; basis of relations and functions; graph data structure; and many more.
In the set theory, we can apply a set of key operations including: membership, subset/superset, union, intersection, difference, complementation, Cartesian product, and power set. Below we quickly explain the key set operations:
1. Membership. An element e belongs to a set A, if it is a member of A
2. Subset. A is a subset of a set A, written A ⊂ B or B ⊃ A, if every element of A belongs to B.
3. Superset. A is a superset of another set B, if all elements in B belongs to A.
4. Powerset. P is a power set of A, if P is the set of all subsets of A
5. Intersection. A ∩ B of two sets A, B is the set of all elements that belong to both A and B
6. Union. A ∪ B of two sets A, B is the set of all elements that belong to A or B
7. Set Difference. A - B of two sets B and A is the set of elements of B that do not belong to A.
8. Symmetric Difference. of two sets A and B. Is the set of elements in A or B, but not in both (not in the intersection) - elements in A only or B only but not in A ∩ B.
9. Complement. of a set A is the set difference (see number 7) between U (universal set is the set of all possible elements) and set A - elements in U, but not in A.
10. Cartesian Product. A *B is the set of all pairs (a,b) where a belongs to A, and b belongs to B.
Task specification
We want to implement a generic collection class, SetClass, that represents a set of elements, and implement the set operations explained above. The SetClass should implement the above 10 set operations as follows:
|
SetClass
|
|
Data:
Add necessary data
|
|
Methods:
+ Membership(T element): bool
+ IsSubsetOf(SetClass B): bool
+ IsSupersetOf(SetClass B): bool
+ Powerset(): SetClass>
+ IntersectionWith(SetClass B): SetClass
+ UnionWith(SetClass B): SetClass
+ Difference(SetClass B): SetClass
+ SymmetricDifference(SetClass B): SetClass
+ Complement(SetClass U): SetClass
+ CartesianProduct(SetClass B): SetClass>
+ Add any necessary methods and/or properties
|
* Note: The Cartesian product method can be applied on sets of different types. This is why we define the CartesianProduct as a generic method.
HOW TO APPROACH TASK2?
Please use the same project template provided in this unit to complete your assignment.
In the DataStructures_Algorithms project, add a folder called "Project01".
- Create a folder "Task02"
- Add an Enum called SetOperation [MEMBERSHIP, SUBSET, SUPERSET, ..., CARTESIANPRODUCT] - in "Task02" folder
- Create SetClass class into "Task02" folder
- Implement the 10 operations specified above.
In the Runner project, add a file called RunnerProject01Task02
- Pass three command line arguments (right click on project, display properties, select debug properties, and specify the following): (i) operation_name, (ii) file_set_A, and (iii) file_set_B_or_U_or_Element [the third argument is the name of the file of another set - B, the universal set - U, or an element - e]
- Your Runner class should read data of set A from the input file - argument 2, read data of set B (or the universal set U, or any element) from the input file - argument 3 (if any), and use operation name as specified in argument 1.
- Finally,your runnershould write the result back to Project01Task02_OperationName_Result.txt - e.g. Project01Task02_Membership_Results.txt