Lab 1: Exception Handling Solution

Information




In-class labs are meant to introduce you to a new topic and provide some practice with that new topic.




Topics: Algorithm Efficiency




Solo work: Labs should be worked on by each individual student, though asking others for help is permitted. Do not copy code from other sources, and do not give your code to other students. Students who commit or aid in plagiarism will receive a 0% on the assignment and be reported.










Building and running: If you are using Visual Studio, make sure to run with debugging. Do not run without debugging!




Using the debugger will help you nd errors.




To prevent a program exit, use this before return 0;







cin.ignore(); cin.get();







Turn in: Once you're ready to turn in your code, prepare the les by




doing the following: (1) Make a copy of your project folder and name it




LASTNAME-FIRSTNAME-LABNAME. (Example: HOPPER-GRACE-LAB-UNIT-TESTS)




Make sure that all source les (.cpp, .hpp, and/or .h les) and the Makefile les are all present. (3) Remove all Visual Studio les - I only want the source les and Make les. (4) Zip your project folder as LASTNAME-FIRSTNAME-LABNAME.zip



Never turn in Visual Studio les!




Starter les: Download from GitHub.




Grading: Grading is based on completion, if the program functions as intended, and absense of errors. Programs that don't build will receive 0%. Besides build errors, runtime errors, logic errors, memory leaks, and ugly code will reduce your score.




Contents










1.1
About . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3


1.1.1
Setting up the project . . . . . . . . . . . . . . . . . .
3
1.2
Lab speci cations . . . . . . . . . . . . . . . . . . . . . . . . .
4


1.2.1
Testing the existing functions . . . . . . . . . . . . . .
4


1.1 About




In this short lab, you will implement a couple of searching algorithms and test out the time it takes to run them. A Binary Search, a Bubble Sort, and a recursive and iterative Fibonacci number nder are already implemented for you.




1.1.1 Setting up the project




Download the starter zip le, LAB-ALGORITHM-EFFICIENCY.zip, o GitHub.




This contains:




Menu.hpp




Searcher.hpp Timer.hpp




Timer.cpp main.cpp





1.2 Lab specifications




1.2.1 Testing the existing functions




There are several functions already implemented. When you rst run the program, you can set a list size and run Binary Search, Sort, Recursive Fibonacci, and Iterative Fibonacci.







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| I n i t i a l i z e |




- - - - - - - - - - - - - -







Enter a list size : 1000




Vector size : 1000










- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




| Main Menu |




- - - - - - - - - - - - -







Which function do you want to time ?




1. Search 1




2. Search 2




3. Binary Search ( for sorted lists )




4. Sort




5. R ec ur si ve F ib on ac ci




6. I te ra ti ve F ib on ac ci







Fibonacci Next, run the Recursive Fibonacci method several times. Find some value that takes a noticable amount of time.




Log its times, and then run the Iterative version for the same value.




n-th term
value
Recursive
Iterative








40
102334155
853 milliseconds
0 milliseconds











Figure 1.1: Example table, yours will be di erent depending on the computer.




Try out several values for n and log each. Why is the recursive one so much slower than the iterative one? Look up the Big O rating for the Recursive Fibonacci algorithm and write it down.













Sorting First start by trying out di erent list sizes and running Sort. Find a list size where it takes a noticable amount of time for the Sort function to complete.







Enter a list size : 10000










[...]







Sorting ...







Done , time elapsed : 609 m i l l i s e c o n d s













In a text editor, ll out a table with a list size. Increase the list size by some linear amount each time and compare the time to sort for each one.




List size
Time to sort




10,000
776 milliseconds




50,000
16365 milliseconds




100,000
78639 milliseconds







Figure 1.2: Example table, yours will be di erent depending on the computer.




What kind of e ciency does this seem like?




Look up Bubble Sort online and nd it's Big-O e ciency and write it down as well.









CS 250
Lab 1: Exception Handling












Searching The Binary Search algorithm is already implemented for you,




but you must have a sorted list before running it. There are also two blank




Search functions in the Searcher.hpp le that you will ll out:
1










int Searcher :: Search1 ( const
vector < int & arr , int






findMe )




2


{




3


// I mp le me nt a search

















}






5


6
int Searcher :: Search2 ( const vector < int & arr , int


findMe )
7
{
8
// I mp le me nt a search







}






The rst search can be a simple Linear search (from beginning to end, checking each value). Search2 doesn't have to be particularly e cient or elegant, but just experiment with some di erent ways you can think of to search an unsorted or sorted list.




Log the amount of time it takes to nd a given value for several list sizes and for each of the search algorithms. Since the list is lled with random integers, you might get di erent results each time.




Try to nd a list size so that each search takes a noticable amount of time.







1







Enter the INTEGER value to find :




999999




S ea rc hi ng with Search 1...







Done , time elapsed : 3 m i l l i s e c o n d s




Result : 999999 found at index 270650
















List size
Find...
Your Search 1
Your Search 2
Binary Search










1,000,000
999999
3 milliseconds
118 milliseconds
0 milliseconds













Figure 1.3: Example table, yours will be di erent depending on the computer.




Once you're nished, turn in the text document and your Searcher.hpp les.