# Lab 8: Algorithm Efficiency

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:

• LinearSearch
• BinarySearch
• StudentSearch
• Recursive Fibonacci generator
• Iterative Fibonacci generator

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... ```

## Setting up the project

In your Student Repository, open the CS250-Lab08-AlgorithmEfficiency project. It will have the following files:

• main.cpp
• EfficiencyExperiment.hpp
• EfficiencyExperiment.cpp
• Timer.hpp

## LinearSearch

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`

#### Linear search algorithm:

1. Create a for-loop that begins at i=0 until i=m_array.size(), going up by one each time.
1. If the element at position i (`m_array[i]`) is equal to the `findMe` parameter, then return `i`.
2. If you've finished the array and nothing has been returned yet, that means the item wasn't found in the array. Return `-1` in this case.

## BinarySearch

#### Binary search algorithm:

1. Create an integer variable called `left` and set it to 0.
2. Create an integer variable called `right` and set it to `m_array.size() - 1`.
3. Create an integer variable called `mid`. It does not need to be initialized.
4. While left is `left` than or equal to `right`...
1. Set `mid` to the value of `left + ( right - left ) / 2`.
2. If the array at position `mid` (`m_array[mid]`) is equal to `findMe` then return `mid`.
3. Or, if the array at position `mid` is less than `findMe`, then set `left` to `mid` plus 1.
4. Or, if the array at position `mid` is greater than `findMe`, then set `right` to `mid` minus 1.
5. Outside the loop, if nothing has been returned, that means the item wasn't found. Return `-1`.

## StudentSearch

Implement your own search algorithm. If the item is found, return the item's index. If it isn't found, return -1.

## Iterative Fibonacci

A Fibonacci sequence begins with two numbers: 1 and 1. Then, each subsequent number is the sum of the previous two. In math terms...

fibn = fibn-1 + fibn-2

#### Iterative Fibonacci algorithm:

1. Create three unsigned integers variables and initialize each of them to 1: `next`, `previous`, and `current`.
2. Create a for loop. For `i` goes from 3 to n (inclusive), going up by one each time...
1. Set `next` to the sum of `current` and `previous`.
2. Set `previous` equal to `current`.
3. Set `current` equal to `next`.
3. Once the for loop is over, return the value of `next`.

## Recursive Fibonacci

#### Recursive Fibonacci algorithm:

• Terminating cases:
1. If `n` is less than or equal to 0, return 0.
2. If `n` is equal to 1, return 1.
• Recursive cases:
1. Return a recursive call: `Fibonacci_Rec( n-1 )` plus `Fibonacci_Rec( n-2 )`.

## Observing efficiency

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.

### Searching

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 algorithmList sizeMilliseconds
Linear1,000
Binary1,000
Student1,000
Linear1,000,000
Binary1,000,000
Student1,000,000
Linear10,000,000
Binary10,000,000
Student10,000,000
Linear1,000,000,000
Binary1,000,000,000
Student1,000,000,000

Q: Which algorithm seemed to take the least amount of time for large numbers?

### Fibonacci

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:

ImplementationnValueMilliseconds
Iterative10
Recursive10
Iterative20
Recursive20
Iterative30
Recursive30
Iterative40
Recursive40
Iterative45
Recursive45

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# DuplicatesNotes
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

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.