· 10 years ago · Sep 03, 2016, 07:56 PM
1ICOM 4035 Sem 16-1
2Specifications of Project 1
3 Page of
4
5
6NOTE: These are preliminary specifications for P1. Read immediately and report any error or inconsistency that you may find. Also, if you have any question regarding any part, please, come and ask for clarifications during office hours. You can also ask your lab instructor (Juan or Orlando) during his office hours.
7
8
91. Introduction
10In this programming project, you will implement three approaches to solve a simple problem: given a list of objects[1], count how many occurrences of each different object exist in that list; which is the same as determining the frequency distribution of different objects in the list. In addition to that, you will also implement a component whose goal is to experiment with those three alternatives to measure the efficiency of each strategy in terms of execution time.
11
12
131. Detailed Specifications
14You will implement three different strategies to solve the same problem: determine the frequency distribution of different objects in a given dataset (a collection) of objects. That is the same to say: count the number of occurrences of each different object in the dataset. The strategies should work for any dataset with objects of type Comparable and whose data type has overridden the equals method[2]. Each one of the strategies to be implemented gets as input a dataset and generates a final list of entries, each consisting of a different object (the key) and the frequency of that object in the list. No such entry should refer to an object that is not part of the list.
15Also, an experimentation component will be implemented with the goal to experiment with those three strategies and estimate their average execution times.
16
17
18Objects Frequency Determination
19The three strategies are as follows:
201. Sequential approach - This approach uses a list of entries, initially empty. Objects from the dataset are explored one by one. For each object, sequentially verify if there is already an entry whose key is that same object. If so, then the value in that entry (the frequency of the object that is its key) is increased by 1. If not, then a new entry is added to that list of entries with key equal to the object being tested and value set to 1. At the end, the list of entries will contain one entry for each different object in the data set. Each entry will contain a particular object (the key) and its frequency (the value) in the data set.
212. Ordered approach - This approach creates another list of objects, initially a copy of the current dataset. Sort that list of objects. Examine all objects in that sorted list, taking advantage of the fact that they are ordered, to determine the frequency of each different object. For each different object in the dataset, add an entry to the list of entries to be produced; as before, each entry consists of a unique object and its frequency in the data set.
223. Map approach - Here you will use a Java implementation of another type of collection named Map. See the Map interface in Java documentation library. In particular, you will use its implementation given by class HashTable. See documentation for that class in Java documentation library. An object of that type, initially empty, will be used in this approach. The approach processes each object from the dataset as follows. The object itself is used as a key. If not found int the map, then a new item is added to that collection. That new item will consists of the pair: the object itself is used as the key of that item and the value associated will be 1. If the object is found in the map, then the current pair in which that object is the key is modified by increasing its current value by 1. At the end, when all the objects in the original dataset have been processed, the entries in the map are placed into the final list of entries.
23
24
25The above mentioned entries are objects that your program manages. For that, you should use class AbstractMap.SimpleEntry in Java. This data type is implemented as a public inner class of class AbstractMap. Study its constructor and methods getKey, getValue, setValue.... More about this will be said later in the document.
26
27
28
29
30Experimentation Approach
31The general framework of the experiment is discussed next. The goal is to estimate the time each strategy takes for different dataset sizes. For each size, the experiment is conducted several times: generate a new dataset of that size, apply each strategy, measure the time each strategy take, compute the final average for each strategy, set that average as the time each strategy takes to solve the problem for a dataset of that size. At the end, the system should produce, for each strategy, a table relating size and time from the results produced by the system.
32
33
34The general procedure for the experimentation part is as follows:
351. For each value of n = 50, 100, 150, ..., 1000
36 1. repeat the following 200 times:
37 1. Generate a new list of n integers and store them in a list of type ArrayList<Integer>. That list cannot be altered by any of the strategies to count frequencies.
38 2. For each strategy do the following:
39 1. apply the described strategy to determine the frequency distribution of the different values in the generated list
40 2. measure the time it takes to accomplish the task
41 3. add the measured time to a total sum of times obtained for the current strategy, which is initially set to 0
42 1. For each strategy do the following:
43 1. Determine the average time that the strategy took for current value of n (divide the total sum of times by 200)
44 2. Store the values n and t, where t is the average time that was determined, in the list of results (the pairs being formed) corresponding to the particular strategy
451. Save the list of results for each strategy in a separate file.
46
47
48Once those files are generated you can use any tool, such as MS Excel, or the equivalent tool in Google Drive to analyze those results and compare the behavior of the three strategies tested.
49
50
511. General Implementation Requirements and Ideas
52In this section, we describe in more detail some requirements that you should comply with in your implementation. On the one hand, they will allow us to easily test your product, while on the other, it provides a schematic approach that is useful to manage the implementation process.
53
54
55As part of the project, you should comply with the following:
561. Your project has to include one Java package named testerClasses. In that package, for each strategy, there will be one tester class named xTester, where x is the name of the strategy (Sequential, Ordered, or Map). Each one of those tester classes include a main method, allowing the particular strategy to be executed from that class in the JVM. That class tests the particular strategy twice. One that reads its input dataset from a file of integer values named integerData.txt, and another that reads the input dataset from a file of strings named stringData.txt. These input files should exists in a local directory (inside your projects directory at the level of the src package) named inputData. You should carefully read about the File class in Java doc library to understand how path names are managed independently if the system where the program is run is Unix, Windows, etc. Output for these testers should be directly on the terminal window in the computer (or output window in Eclipse).
572. The project should include another package named experimentClasses. There, you will include a Java class named ExperimentalTrials, whose main method initiates the experimental process and finally generate the files with the experimental results for each one of the strategies discussed. Such files will be saved to a local directory to be named experimentalResults (at the same level of the inputData directory). The names of those files shall be:
58 * resultsSequential.txt
59 * resultsOrdered.txt
60 * resultsMap.txt
61
62
63 Each one of these files contains, for the corresponding strategy, and for each value n=50, 100, 150, ..., 1000, one line containing the two numbers n and t, separated by at least one space character. For each such pair, n is the dataset size and t is the particular average execution time (in milliseconds) that was determined by the experimentation process for that particular dataset size. Those files will be written to a local directory (at the same level of the inputData directory) named outputResults.
64
65
66
67
68Implementation Ideas
69First, let’s mention about some Java classes and interfaces that you should be using in this project.
70* Java interface Map.Entry<K, V>: The idea of an object of this type is that it contains a pair of values, one of generic type K and the other of generic type V. Any instance such type pair establishes an association or relation between the two objects that are its components: the key and the value. Usually, the first value (the one of type K) is a value that somehow differentiates the pair from other such pairs. It is usually referred to as the “key†of the entry. The other value (the one of type V is simply considered the “value†of the entry pair. Java provides an implementation for this: see class AbstractMap.SimpleEntry. You can use object of this type to represent entries used in the different strategies being implemented.
71* Class HashTable<K, V>: This is a type of collection that holds pairs of values as its elements. Each pair is internally stored as an entry, although most of the operations don’t directly deal with entries, but with the pair of values. The operations that you will need in this project are: default constructor, contains, entrySet, get, and put. You may use other operations as needed by your implementation, but at this moment I only foresee that the ones listed are the ones needed. Read their specifications of what they are suppose to do and the correct way to use them. Later in the course, we will study this type of collection in detail (See about Map ADT in the list of topics.).
72
73
74The following ADT (specified as an abstract class) corresponds to the datatype of a frequency counter object. For each of the described strategies there should be one subclass implementing the appropriate algorithm that such strategy uses to count the different object in a dataset. The dataset is given as an ArrayList object.
75public abstract class FrequencyCounter<E extends Comparable<E>> {
76 private String name; // the name given to this strategy
77
78 public FrequencyCounter(String name) {
79 this.name = name;
80 }
81
82
83 /**
84 Accesses the name of the particular strategy that the object instance corresponds to.
85 **/
86 public String getName() {
87 return name;
88 }
89
90
91 /**
92 Determines the frequency distribution of objects in a particular dataset using a valid
93 strategy. It is based on the algorithm defining the particular strategy to solve the
94 frequency counting problem.
95 @param dataSet the dataset of objects to be analized
96 @return a list of entries, where each such entry is a pair: key (of type E) is a reference
97 to one instance of a different object , and value is the frequency of that object in the
98 list being analyzed
99 **/
100 public abstract ArrayList<Map.Entry<E, Integer>> computeFDList(ArrayList<E> dataSet);
101}
102
103Under this approach, you can then implement one class for each one of the strategies. For example, the following is one (documentation is omitted for simplicity):
104
105
106public class Sequential<E extends Comparable<E>> extends FrequencyCounter<E> {
107
108
109 public Sequential() {
110 super("Sequential");
111 }
112
113
114 @Override
115 public ArrayList<Map.Entry<E, Integer>> computeFDList(ArrayList<E> dataSet) {
116 ArrayList<Map.Entry<E, Integer>> results =
117 new ArrayList<Map.Entry<E, Integer>>();
118 for (E e : dataSet) {
119 boolean entryFound = false;
120 for (int i=0; i<results.size() && !entryFound; i++) {
121 Map.Entry<E, Integer> entry = results.get(i);
122
123 if (entry.getKey().equals(e)) {
124 entry.setValue(entry.getValue()+1);
125 entryFound = true;
126 }
127 }
128 if (!entryFound) {
129 //need to create a new entry for the first instance found of object e
130 Map.Entry<E, Integer> entry = new AbstractMap.SimpleEntry<E, Integer>(e, 1);
131 results.add(entry);
132 }
133 }
134
135 return results;
136 } // end of method computeFDList
137}
138
139
140Other ideas are:
1411. To generate random numbers, see class Random in java.util.
1422. To estimate execution time of code X, we can do the following:
143
144
145long startTime = system.currentTimeMillis();
146
147
148 X
149
150
151long estimatedTime = system.currentTimeMillis() - startTime;
152
153
1541. ...
155
156
157
158
1591. Deadline for Submission
160The final date to submit your program will be at 11:59 pm on Sunday, September 18, 2016.
161
162
163We may send you more information in the coming days as to what exactly you need to submit, and how to do it. In particular, there are some important names that you must use for your project, and the internal organization of what you need to send. For the moment, you can start working as you want, and using the Eclipse system to implement and test your code. But at least it is expected that you submit the following:
1641. Zip file containing a directory inside which your project is located when extracted and saved. That zip file shall be named as: P1_4035_nnnnnnnnn_161.zip. (Where nnnnnnnnn are the 9 digits that form your student id number.)
165 1. It should contain your project directory, whose name shall be: P1_nnnnnnnnn.
166 2. Inside this last directory is where the different packages for your project will be located.
167NOTE: You should verify that your program runs correctly from the command prompt in the directory where it is found.
1681. Your project directory will also contain a text file named: README. There, you have to explain how your program can be compiled and executed. Make sure that your instructions work properly.
169
170
171Your code should include at least the proper documentation for its classes and methods, which must follow the standards required for the Javadoc tool.
172
173
174Once your zip file is ready, please, send it (as an attachment) by email to your lab instructor:
175Orlando Nieves (orlando.nieves4@upr.edu) or Juan López (juano.lopez@upr.edu).
176
177
178
179
180
181
182
183
184________________
185
186
187Final Comments
188The idea about these projects is for you to learn important topics and skills that you should learn and develop throughout your undergraduate studies. You need to work on these projects (etc.) in order to be successful on that. It is natural that you have doubts and that there are parts of the previous specifications that you may not understand. In that case, don't be afraid to come to office hours (mine or your lab instructor’s) and ask. Do it, that is precisely what we are supposed to be here for. However, you need to do your part. No explanation of hint that we may offer in the future is going to be useful if you do not read and try to understand first what is being asked to do in this project. Therefore, you need to read this document and try to take note of those parts that you do not understand. Start reading and do it consciously. If you need to, read again and again. You will eventually understand and ideas will flow to your mind...
189
190
191During lab hours, we will discuss more ideas about how to proceed. However, those won't be of benefit if you have not read this document or don’t have a clear perspective of what it is being specified. You should also have at least preliminary ideas of how to work on at least some parts of the project.
192
193
194
195
196IC4035 P1 Sem 16-1
197prof. Pedro I. Rivera Vega
198file: GDR/.../P1
199________________
200[1] It is assumed that the equality of two such objects is determined by the equals method. We shall also assume that the objects are of Comparable data type.
201[2] Classes in Java representing singly objects comply with this requirement: String, Character, Integer, Float, Double, ...