Starting from:
$25
EE312-Project 5 Set Solved
This project will give you experience writing a data structure in C/C++. More importantly, you will get to put some serious effort into using good algorithms in your programs and analyzing their time complexity. Part of your grade for this project will be based on how efficient your programs are. We will attempt to ascertain if your algorithms require time proportional to N2, N log2 N, N, or log2N.
Your Mission: Edit the file “Project5.cpp”. You should not need to change any other files. You must implement all of the functions defined for the Set ADT (see Set.h for a complete list). I’ve taken care of several of these functions to get you started. However, the work that remains is substantial. Get started early.
General Design: I suggest (actually, I insist) that you keep the elements inside the Set sorted. For example, whatever is stored in elements[0] should be smaller than any other element in the set. Whatever is in elements[1] should be the second smallest, etc.
How Sets Work: Recall that a set is an unordered collection of things. Your Set class will hold a collection of ints. The operations you must implement include inserting and removing elements from the set. Please note that the same element cannot appear twice in the same set. If insertSet is called where the parameter is a number that’s already in the set, your function should do nothing. Similarly, removeSet should remove an element from the set. If someone attempts to remove an element that’s not in the set, then you should do nothing.
In addition to inserting and removing elements, you must provide a membership test. In other words, it must be possible to determine if some arbitrary number is a member in your Set. The isMemberSet function should provide this capability. Two sets can also be compared. If the sets have exactly the same elements then they are equal. Note that two sets that each contain zero elements are equal. A set, X is a subset of another set Y if all of the elements in X are also elements of Y. So, a set containing zero elements is a subset of every other set. Also, every set is a subset of itself.
The interesting functions for sets are intersection, union and subtraction. Recall that the intersection of two sets is the elements that are common to both sets. So, if X has the elements {1, 3, 5, 7} and Y has the elements {1, 2, 3, 4} then the intersection of X and Y is a set with elements {1, 3}. The union of two sets is the set of elements that are in either one of the two sets. So, for the same X and Y above, the union would be a set containing {1, 2, 3, 4, 5, 7}. Finally, set subtraction is defined as the set of all elements that are in the first set but are not in the second set. So, if we ask for X – Y we would compute the set containing {5, 7}. You must write all three of these functions.
Performance: For this project we are interested in how efficiently your programs will run. Specifically we’re interested in determining for each function you write whether the function takes time proportional to the number of elements in the set, the logarithm of the number of elements in the set, or the square of the number of elements in the set. The best way to determine the efficiency of your algorithm is to analyze the code by hand and count how many operations must be performed. We’ll be trying to write a program that will automatically guess the performance. Such programs are very difficult to write, so don’t put too much faith in the estimates it gives (it almost always is wrong for isEqualTo). Do your own analysis (besides it will be a great way to study for the next test). For each of the following functions, the worst-case time complexity must be as described below:
Function
Time Complexity (worst case, N is the number of elements in a set, for operations that apply to two sets, assume both sets have N elements).
insert
O(N)
remove
O(N)
isMember
O(log N)
isEqualTo
O(N) (not graded)
isSubsetOf
O(N)
unionIn
O(N)
intersectFrom
O(N)
subtractFrom
O(N)
Memory Leaks
Use Valgrind to check for memory leaks. If your solution is implemented correctly, you should pass every test case, meet the above time complexity numbers, and have no memory leaks of any kind, when run on the ECE Linux server.
Your Mission: Edit the file “Project5.cpp”. You should not need to change any other files. You must implement all of the functions defined for the Set ADT (see Set.h for a complete list). I’ve taken care of several of these functions to get you started. However, the work that remains is substantial. Get started early.
General Design: I suggest (actually, I insist) that you keep the elements inside the Set sorted. For example, whatever is stored in elements[0] should be smaller than any other element in the set. Whatever is in elements[1] should be the second smallest, etc.
How Sets Work: Recall that a set is an unordered collection of things. Your Set class will hold a collection of ints. The operations you must implement include inserting and removing elements from the set. Please note that the same element cannot appear twice in the same set. If insertSet is called where the parameter is a number that’s already in the set, your function should do nothing. Similarly, removeSet should remove an element from the set. If someone attempts to remove an element that’s not in the set, then you should do nothing.
In addition to inserting and removing elements, you must provide a membership test. In other words, it must be possible to determine if some arbitrary number is a member in your Set. The isMemberSet function should provide this capability. Two sets can also be compared. If the sets have exactly the same elements then they are equal. Note that two sets that each contain zero elements are equal. A set, X is a subset of another set Y if all of the elements in X are also elements of Y. So, a set containing zero elements is a subset of every other set. Also, every set is a subset of itself.
The interesting functions for sets are intersection, union and subtraction. Recall that the intersection of two sets is the elements that are common to both sets. So, if X has the elements {1, 3, 5, 7} and Y has the elements {1, 2, 3, 4} then the intersection of X and Y is a set with elements {1, 3}. The union of two sets is the set of elements that are in either one of the two sets. So, for the same X and Y above, the union would be a set containing {1, 2, 3, 4, 5, 7}. Finally, set subtraction is defined as the set of all elements that are in the first set but are not in the second set. So, if we ask for X – Y we would compute the set containing {5, 7}. You must write all three of these functions.
Performance: For this project we are interested in how efficiently your programs will run. Specifically we’re interested in determining for each function you write whether the function takes time proportional to the number of elements in the set, the logarithm of the number of elements in the set, or the square of the number of elements in the set. The best way to determine the efficiency of your algorithm is to analyze the code by hand and count how many operations must be performed. We’ll be trying to write a program that will automatically guess the performance. Such programs are very difficult to write, so don’t put too much faith in the estimates it gives (it almost always is wrong for isEqualTo). Do your own analysis (besides it will be a great way to study for the next test). For each of the following functions, the worst-case time complexity must be as described below:
Function
Time Complexity (worst case, N is the number of elements in a set, for operations that apply to two sets, assume both sets have N elements).
insert
O(N)
remove
O(N)
isMember
O(log N)
isEqualTo
O(N) (not graded)
isSubsetOf
O(N)
unionIn
O(N)
intersectFrom
O(N)
subtractFrom
O(N)
Memory Leaks
Use Valgrind to check for memory leaks. If your solution is implemented correctly, you should pass every test case, meet the above time complexity numbers, and have no memory leaks of any kind, when run on the ECE Linux server.
1 file (29.9KB)
