COP2500 - Searching an ordered list

COP2500 Assignment 7

Deliverables: To complete this assignment you must --
1.) Write the HTML and JavaScript page described below and demonstrate to the lab instructor that it operates correctly.

Introduction: The main goal of this assignment is to give you an idea of how quick O(logn) algorithms are compared to O(n) algorithms. We learned in class that Unordered Search is O(n) while Ordered Search is O(logn). In this assignment you will use the html page provided you to investigate the difference. The page provided to you allows you to create an unordered list and an ordered list. It then allows you to search for elements within the list. I have provided functions to make the lists and perform the ordered search. You must program the function that performs the unordered search (use the algorithm provided below). Then create the lists and experiment with searching through them. Finally, fill in the blanks on the questions at the top of the page by editing the HTML document.

Procedures:

Use a text editor to complete your assignment.
Save the source code of this page as "cop2500lab8.html" on your computer.
Program the UnOrderedSearch() function within "cop2500lab8.html". Take your time and make sure you are using the names provided within the form when you are getting input from the text boxes in the form. (Easy place to have a typo).
Create four different sized lists (100, 200, 500, and 1000 elements, for example). Then perform searches on the lists using the form text boxes as input. The web page should output the approximate number of operations required for the search to be performed. Try searches that you know will succeed, and searches you know will fail. Use scrap paper to keep track of your results.
Edit the HTML document again to answer the questions at the top of the page. Use the results from your experiments.
Open a browser and verify that everything displays properly. Keep this window open until the instructor has had time to verify your work. In order to obtain full credit for the lab you need to show that your code works in the lab, or submit your working assignment via email by 11:55 pm on Sunday Oct 28.

UnSortedSearch(): Searching for a key in a list of numbers.

Section Pseudocode Comments

INPUT: Integer list[n];
Integer key; This represents a list of n numbers
and a key.

OTHER VARIABLES: Integer i;
Integer ops;
String result; i is the loop variable.
ops counts the number of operations required.
result is true or false.

INITIALIZATION: Assume the list is given
Assume the key is given
result = "False";
ops = 0;
The list is given to us by the
MakeList() function so we don't need to do anything
The key is also provided in the function call.
As usual we assume the result is "False" until proven otherwise.
The ops variable will track the number of operations required.

COMPUTATION: FOR i = 0 to (n - 1) DO
ops = ops + 3;
IF ( list[i] == key ) THEN
result = "True";
break;
ENDIF
ENDDO Quite a bit going on here.
The loop shouldn't surprise you.
The 'ops' summation simply counts
approximate number of operations
performed per loop iteration. The
"break;" statement terminates the loop if the key is found.

OUTPUT: document.lab8.uresult.value = result;
document.lab8.u_ops.value = ops; These commands simply paste
the results to the form text
boxes (Note: I sometimes get a
typo in the name of the box).

Section	Pseudocode	Comments
INPUT:	Integer list[n]; Integer key;	This represents a list of n numbers and a key.
OTHER VARIABLES:	Integer i; Integer ops; String result;	i is the loop variable. ops counts the number of operations required. result is true or false.
INITIALIZATION:	Assume the list is given Assume the key is given result = "False"; ops = 0;	The list is given to us by the MakeList() function so we don't need to do anything The key is also provided in the function call. As usual we assume the result is "False" until proven otherwise. The ops variable will track the number of operations required.
COMPUTATION:	FOR i = 0 to (n - 1) DO ops = ops + 3; IF ( list[i] == key ) THEN result = "True"; break; ENDIF ENDDO	Quite a bit going on here. The loop shouldn't surprise you. The 'ops' summation simply counts approximate number of operations performed per loop iteration. The "break;" statement terminates the loop if the key is found.
OUTPUT:	document.lab8.uresult.value = result; document.lab8.u_ops.value = ops;	These commands simply paste the results to the form text boxes (Note: I sometimes get a typo in the name of the box).