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.


 

About

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
  • Menu.hpp
  • 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.