CS173: Intro to Computer Science - Searching: Dropping the Lowest Score (100 Points)
Assignment Goals
The goals of this assignment are:- To search an array using iterative approaches
The Assignment
If (and only if) you are using GitHub to submit, you can clone this assignment from GitHub Classroom at https://classroom.github.com/a/XWrevmFf. Otherwise, you may skip this step!In this lab, you will write and test functions to drop the lowest score in an ArrayList<Double> of test scores, and then return the average of the remaining items.
Step 1: Searching the Array for the Smallest Item
First, linearly search the array to find the index of the smallest item. Remove the lowest item from the array, and print it. You can print an ArrayList by calling .toString() on the ArrayList variable, and printing that.
Step 2: Counting the Number of Iterations
In addition, count the number of times your loop iterates to find the smallest item. You can use an int counter that you increment each time you execute the loop. Following the loop, print out the count of the number of times you execute inside a loop.
Put all of the above code into a function, and you will call that function from main().
Step 3: Calling This Function and Plotting Your Results
Within main(), call this function several times, each with a different sized array. You will plot the number of steps that were needed against the size of the array. You can use a loop with a random number generator to generate scores. I suggest creating a function that generates and returns an ArrayList<Double>, in which you pass the desired size of the array as a function parameter. The function then uses a random number generator to fill the array and return it. Then, you can call this from main() within a loop, so that you try it multiple times without having to copy and paste your code!
To plot your results, you can copy or type the iteration counts you receive into Microsoft Excel and generate a line graph. Your first column will be the size of the array that you used, and your second column will be the number of iterations that were required to find the smallest element in that array. Thus, your x-axis will be the size of the array, and your y-axis will be the number of iterations. What do you notice about the shape and direction of this graph?
Submission
If you wrote code as part of this assignment, please include a README in which you describe your design, approach, and implementation. Additionally, please answer any questions from the assignment, and include answers to the following questions:- If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who?
- Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
- Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
- Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).
Assignment Rubric
| Description | Pre-Emerging (< 50%) | Beginning (50%) | Progressing (85%) | Proficient (100%) |
|---|---|---|---|---|
| Algorithm Implementation (60%) | The algorithm fails on the test inputs due to major issues, or the program fails to compile and/or run | The algorithm fails on the test inputs due to one or more minor issues | The algorithm is implemented to solve the problem correctly according to given test inputs, but would fail if executed in a general case due to a minor issue or omission in the algorithm design or implementation | A reasonable algorithm is implemented to solve the problem which correctly solves the problem according to the given test inputs, and would be reasonably expected to solve the problem in the general case |
| Code Quality and Documentation (30%) | Code commenting and structure are absent, or code structure departs significantly from best practice, and/or the code departs significantly from the style guide | Code commenting and structure is limited in ways that reduce the readability of the program, and/or there are minor departures from the style guide | Code documentation is present that re-states the explicit code definitions, and/or code is written that mostly adheres to the style guide | Code is documented at non-trivial points in a manner that enhances the readability of the program, and code is written according to the style guide |
| Writeup and Submission (10%) | An incomplete submission is provided | The program is submitted, but not according to the directions in one or more ways (for example, because it is lacking a readme writeup) | The program is submitted according to the directions with a minor omission or correction needed | The program is submitted according to the directions, including a readme writeup describing the solution |