COP3530 Assignment 3
COP3530 – Assignment 3
Objective
Students will be able to conduct a comparison study of the performance of searching algorithms. An
experiment will be implemented to analyze the running times of well-known searching algorithms in a
given scenario.
Assignment Problem
Consider the following problem. A large set of integers, stored in an a
ay named dataset, must be
searched continuously to determine the presence of values coming from a certain source dataSource. It
is understood that the set of values in dataset will not change ever. Suppose that after careful analysis,
you are left with two final candidates for algorithms:
Algorithm A1: For each value of dataSource, search for its presence in dataset using linear search.
Algorithm A2: Sort dataset with quicksort once, and then search each value of dataSource in dataset,
using binary search for each.
Task: design and implement an experiment to empirically estimate the number of elements k in
dataSource, so that the running time of Algorithm 2 outperforms Algorithm 1 for any number of values
in dataSource greater than or equal to k.
In the example below (the numbers are not taken from a real example; they are offered to illustrate the
problem), such a k would be 145. Note that the values under the second and third columns represent
seconds.
k Algorithm A1 Algorithm A2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
6 – 144 A1 takes less time A2 takes more time
XXXXXXXXXX
146 A1 takes more time A2 takes less time
Requirements
• Type of the elements both in dataset and dataSource: int
• Size of dataset: 2 × 107
• Range of values in dataset: random integers in [0, size of dataset], generated with the nextInt
method of the Random class
• The data source, dataSource, will be an a
ay
• Range of values in dataSource: random integers in [0, 2 × size of dataset], generated with the
nextInt method of the Random class
• Units of time: seconds (note that Java offers time measuring utilities in milliseconds and
nanoseconds; conversion to seconds must be performed by your program)
• Sorting algorithm: quicksort; implementation in separate file (you are required to use the
provided implementation)
• Your program will save the results to a .csv file. Use Excel to depict graphically the results of
your experiment (Excel can open .csv files).
Example of the content of .csv file:
1, 0.012, 0.606
2, 0.02, 0.648
3, 0.018, 0.632
4, 0.03, 0.768
5, 0.019,0.828
. . .
• A Conclusions document will be submitted, which will include:
a) What was the value of k obtained?
) Explanation on the results obtained.
c) The Excel picture(s), chart(s), or diagram(s).
d) What did you learn?
• Students are required to structure the code as indicated in the UML class diagram:
Main
+static void main(String[] args)
+Main()
SearchingAlgorithms
+static boolean binarySearch(int[] list, int x)
+static void fillA
ay(int[] list, int range)
+static void printA
ay(int[] list)
+static boolean sequentialSearch(int[] list, int x)
+static void quickSort(int[] list)
-static void quicksort(int[] list, int begin, int end)
-static int findPivotLocation(int b, int e)
Guidelines
• The assignment is to be completed individually or in teams of two students. Only one member of
a team will submit the assignment.
• The given problem is based on the content studied in class on searching algorithms.
• You are allowed to use all of the code discussed in the lectures. In those cases, make sure you
properly credit its source.
Deliverables:
• A compressed folder, PID Assignment 3 (e.g XXXXXXXXXXAssignment 3), containing
- all of the source code of the exercise
- Conclusions (Word or PDF file) document with the content and structure indicated above
- the .csv file
- the Excel file
• Include only the .java files mentioned above; do not include other files or folders generated by
the IDE.
• Make sure you write name(s) and Panther ID(s) in the class comment section of each Java file.
• In teams of two students, make sure the member who submits the assignment writes names
and Panther IDs of both students in the comment section of the submission window.
Grading Ru
ic
The assignment is worth 115 points (out of 1000 total course points). Grade components:
Component Points Description
Submission 5 The student has submitted the project solution using the
equirements for deliverables specified in the Deliverables section.
Organization 5 Code is expected to be neat, organized, and readable.
Content 105
Deliverable Points
source code 65 pts
conclusions 20 pts
.csv file 10 pts
Excel file 10 pts
/**
* Recursive quickSort algorithm
* @author Prof. A. Hernandez
*
public static void quickSort(int[] list)
{
XXXXXXXXXXquicksort(list, 0, list.length - 1);
}
private static void quicksort(int[] list, int begin, int end)
{
XXXXXXXXXXint temp;
XXXXXXXXXXint pivot = findPivotLocation(begin, end);
swap list[pivot] and list[end]
XXXXXXXXXXtemp = list[pivot];
XXXXXXXXXXlist[pivot] = list[end];
XXXXXXXXXXlist[end] = temp;
XXXXXXXXXXpivot = end;
XXXXXXXXXXint i = begin,
XXXXXXXXXXj = end - 1;
XXXXXXXXXXboolean iterationCompleted = false;
XXXXXXXXXXwhile (!iterationCompleted)
{
XXXXXXXXXXwhile (list[i] < list[pivot])
XXXXXXXXXXi++;
XXXXXXXXXXwhile ((j >= 0) && (list[pivot] < list[j]))
XXXXXXXXXXj--;
XXXXXXXXXXif (i < j)
{
swap list[i] and list[j]
XXXXXXXXXXtemp = list[i];
XXXXXXXXXXlist[i] = list[j];
XXXXXXXXXXlist[j] = temp;
XXXXXXXXXXi++;
XXXXXXXXXXj--;
} else
XXXXXXXXXXiterationCompleted = true;
}
swap list[i] and list[pivot]
XXXXXXXXXXtemp = list[i];
XXXXXXXXXXlist[i] = list[pivot];
XXXXXXXXXXlist[pivot] = temp;
XXXXXXXXXXif (begin < i - 1) quicksort(list, begin, i - 1);
XXXXXXXXXXif (i + 1 < end) quicksort(list, i + 1, end);
}
/*
* Computes the pivot
*
private static int findPivotLocation(int b, int e)
{
XXXXXXXXXXreturn (b + e) / 2;
}