Objectives:
• Review programming in a high-level language
• Implement linear search and binary search algorithms
• Evaluate performance of linear and binary search algorithms
In-class Assignment:
1. Implement a method that will search a given array using the linear search algorithm.
2. Implement a method that will search a given array using a recursive binary search algorithm.
3. Write a driver program to test the methods implemented in questions 1-2. Note that you have to sort the input array before using the binary search algorithm, you can use any sort method available (e.g., sort method in the Java Collection Framework).
Homework Assignment:
1. You need to create multiple datasets to test the speed of your algorithms. Test the program for array sizes N = 16, 32, 64, 128, 256, 512, 1024, 2048, ……, 220. Initialize the array with random numbers between the ranges 1 through N (Please note that we will be using these datasets for both linear search and binary search. Remember to sort the array before using binary search. These datasets will be our dataset that we will be searching our keys inside those datasets
2. Use a text file with 1,000 random numbers in the range 1 through 1000 as the search keys. You need to search all those 1000 numbers inside every dataset.
3. Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time (you have to sort only once for each array size). Use a table or plot to summarize the results and document your observations and explanations in the report.
In short you need to calculate the computation times as follows;
Size of dataset Linear Search Binary Search
16
32
64
128
….
….
2^20
Spring 2023 – CS 303 Algorithms and Data Structures
Lab 1
Check the Canvas Files / Documents for the Sample report and create a similar report format.
Try to finish in class assignment part before the lab is over, I suggest you to start working on the lab assignments before you come to the lab.
If you have any questions about homeworks, report, the course structure…etc, feel free to ask your TA or Instructor
Good Luck J
Grading Rubric
Coding
Implementing Algorithms
20 points
Producing Correct Outputs
20 points
Report
Explaining the algorithms used
10 points
Displaying the output with a graph or table
20 points
Comparing the outputs and discussing the time
20 points
complexity of algorithms
Correct submissions of the files (ICF, Code.zip,
10 points
report.pdf)
