Topics: Algorithm Efficiency, Searching
Group work: Group work is allowed for the labs, but each person must do their own coding and each person must turn in an assignment. Copying other peoples' code / code files is not allowed. Copied assignments will receive 0% for everybody involved.
Assignments must build: Assignments that don't build will automatically just be given a flat 50% score. I may still give feedback on what went wrong, and 50% is better than 0%, so turn in something - but ideally, make sure it builds.
In this lab, we have a Timer
class which we can use
to time how long a function takes to run. The shell program is already
set up, and you will implement the following functions:
Then, you will run them with different sized arrays (for the searching) to see how long each algorithm takes.
When you run the program, you will select which thing to test:
-------------------------------------------------------------------------------- | CS 250 Lab 8 - Main Menu | ---------------------------- 1. Searching efficiency 2. Fibonacci efficiency 3. Quit >> 1
And then set the parameters for the search or fibonacci generation:
-------------------------------------------------------------------------------- | Searching Efficiency | ------------------------ [SIZE] Enter the size of the array size: >> 10000 [SEARCH] 1. Linear search 2. User's search 3. Binary Search (Requires sorted list) >> 1 [FIND] Enter an INTEGER value to find: >> 5 [MESSAGES] 1. Show status messages 2. No status messages >> 2 Searching with LINEAR SEARCH...
In your Student Repository, open the CS250-Lab08-AlgorithmEfficiency project. It will have the following files:
A Linear Search is just a simple search where you start at the beginning of your array (vector in this case) and look at each one, one step at a time, until you hit the end.
The EfficiencyExperiment
class that we're working in
contains the array we'll be working with:
vector<int> m_array
m_array[i]
) is equal to the findMe
parameter, then return i
.-1
in this case.left
and set it to 0.right
and set it to m_array.size() - 1
.mid
. It does not need to be initialized.left
than or equal to right
...
mid
to the value of left + ( right - left ) / 2
.mid
(m_array[mid]
) is equal to findMe
then return mid
.mid
is less than findMe
, then set left
to mid
plus 1.mid
is greater than findMe
, then set right
to mid
minus 1.-1
.Implement your own search algorithm. If the item is found, return the item's index. If it isn't found, return -1.
A Fibonacci sequence begins with two numbers: 1 and 1. Then, each subsequent number is the sum of the previous two. In math terms...
fib_{n} = fib_{n-1} + fib_{n-2}
next
, previous
, and current
.i
goes from 3 to n (inclusive), going up by one each time...
next
to the sum of current
and previous
.previous
equal to current
.current
equal to next
.next
.n
is less than or equal to 0, return 0.n
is equal to 1, return 1.Fibonacci_Rec( n-1 )
plus Fibonacci_Rec( n-2 )
.Once everything is implemented, run the program to test each function with different array sizes or n values. Log your observations in a text document.
Run searches for each search algorithm to compare speeds. Note that each time a search is done, a new list is created, so we are measuring not exact values but more generalized speed values. The speeds will differ depending on what computer you're on.
Fill out the table:
Search algorithm | List size | Milliseconds |
---|---|---|
Linear | 1,000 | |
Binary | 1,000 | |
Student | 1,000 | |
Linear | 1,000,000 | |
Binary | 1,000,000 | |
Student | 1,000,000 | |
Linear | 10,000,000 | |
Binary | 10,000,000 | |
Student | 10,000,000 | |
Linear | 1,000,000,000 | |
Binary | 1,000,000,000 | |
Student | 1,000,000,000 |
Q: Which algorithm seemed to take the least amount of time for large numbers?
Run both the Iterative and the Recursive Fibonacci functions with different n values to compare their speeds. Fill out the table given. The speeds will differ depending on what computer you're on.
Fill out the table:
Implementation | n | Value | Milliseconds |
---|---|---|---|
Iterative | 10 | ||
Recursive | 10 | ||
Iterative | 20 | ||
Recursive | 20 | ||
Iterative | 30 | ||
Recursive | 30 | ||
Iterative | 40 | ||
Recursive | 40 | ||
Iterative | 45 | ||
Recursive | 45 |
Q: Which algorithm appeared to be more efficient?
Q: For finding the 10th Fibonacci value, complete this table of recursive function calls:
(keep going until you hit terminating cases...)
Hopefully this illustration will show you why the Recursive algorithm's speed is what it is.
Q: In your Fib(10) recursive graph, how many function calls were duplicates? (e.g., the same Fib(5) being called multiple times?)
Function | # Duplicates | Notes |
---|---|---|
Fib(10) | 0 | Only called once |
Fib(9) | 0 | Only called once |
Fib(8) | 2 | Called by both Fib(9) and Fib(10) |
Fib(7) | ||
Fib(6) | ||
Fib(5) | ||
Fib(4) | ||
Fib(3) | ||
Fib(2) | ||
Fib(1) |
Turn in your EfficiencyExperiment.cpp file and the text document (.txt, .rtf, .docx, .odt, .pdf), or a hand-written document (scanned or photographed) with your observations.