Assignment 3 – Search Algorithm

Objectives

1. Manipulate an array to create entries
2. Perform a search on a sorted array
3. Determine the complexity of search on a sorted array

Supports Outcome 3: Implement data structures and algorithms in computer code.

Summary

You are going to have to be able to understand algorithms and ways to implement them through functions and methods. This is covered extensively in Topic – Algorithms and Programming . You should go through this topic thoroughly and then return to complete exercises in the assignments section.

Here is a basic algorithm to help you do this;
1. Determine Max and Min values in array
2. Pick point at midpoint of max and min numbers
3. Check the midpoint against user entered number
4. If midpoint > guess; max = midpoint; repeat from 2
5. If midpoint < guess; min = midpoint;  repeat from 2
6. If midpoint = guess; done

Lectures

All Course Lectures should help you get started on this assignment.

Lecture 2.2 Lists and Arrays (Brightcove | Youtube) – As with the last assignment, you will need to understand Lists and Arrays.

This is also a great time to start working on debugging in Javascript. Here is some help on that (Youtube )  LEARN TO DEBUG

Assignment

Using your JSFiddle account, you are going to create a guessing game, only it will be the computer doing the guessing. Here is how it works – the computer will ask you for a number between 1 and 1000, and it will check first to ensure your input is within the bounds.

Once you enter the number, it will guess the number and compare it with the number you entered. It will output the guess results and continue to do this until it gets the correct answer. NOTE: THE USER IS NOT THE ONE  GUESSING – THE USER ENTERS A NUMBER AND THE COMPUTER OUTPUTS ITS GUESSES

This is what the program’s output will look like (if I enter 329). Once again – the user inputs the number, and the computer searches for it in the Array.

User Input	Input: 329
Computer Output	Guessed 500 – too high.Guessed 250 – too low. Guessed 375 – too high. Guessed 313 – too low. Guessed 344 – too high. Guessed 329 – Got It! It took me 6 Tries.

You can probably figure out how my algorithm works, yours should use the same basic logic. You will want to create an efficient algorithm (lowest possible O).

Programming parameters:

1 – This will be coded in Javascript.

2 – You should create a dimensioned array of 1000 elements.

3 – You should fill in the elements from 1 to 1000 in order before implementing the search

4 – State the Big O complexity of the algorithm after your results

Here is some html code you can use for the HTML portion of the Assignment

<h1>Guessing Game Assignment 3</h1>
Enter Number :<input type="textbox" value="329" id="number"/>
<input type = "button" id="button" value="Guess Entered Number" onclick="GuessNumber()"/>
<div id="output"></div>

Submission Instructions

You will submit a link to your code in JSFiddle.

Assignment Grading Criteria

The program must work successfully for credit. If the program gives the output shown above for the guess shown above, then you know it is working correctly.

Additional Information

You should be able to figure out the Big-O for this problem compared to the other problems. You are now getting into some of the computing mathematics and should probably get a better understanding of Complexity. The following youtube video does a great job of explaining the P vs. NP

https://www.youtube.com/watch?v=YX40hbAHx3s 

All COP3530 Assignments