[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Bring your answers to the class if you are having trouble posting them on the blogRe: Blog Qn 1: What's good for sorting must be good for searching too!




Folks
 
 Some of you said you have had trouble posting on the blog. I suggest that you just bring a printout of your answers to the class on Friday. 

thanks
Rao


On Fri, Aug 31, 2012 at 9:57 AM, Subbarao Kambhampati <rao@asu.edu> wrote:
Folks

 Here is your first blog assignment. You should answer the question by entering your answer as a comment to the question on class blog.

Here is the question.

In the class today, you heard that one way of solving a problem is to (a) write a test procedure that tests to see if a potential solution is a real solution
and (b) embed this test in a loop over all potential solutions. At some level this would be the possibly dumbest zeroth algorithm for solving the problem.

We saw, for sorting, that testing if a sequence with n elements is sorted can be done with n-1 (or O(n)) comparisons. We also saw that every permutation of the
n-element sequence is a potential solution. So we can loop over each of these permutations until we find one that succeeds the "is this sorted?" test. This "algorithm" does
O(n! * n) comparisons. (We noticed, by the end of the class, that this is a truly rotten algorithm, since we can do sorting with just O(n^2) comparisons by repeatedly finding the smallest 
element in the list. 

Now for the question. I want you to do this generate-test analysis for searching.

The problem of searching is this: Given a set of n elements with associated keys (e.g., [(A 4) (B 9) (C 15) (D 23) ]), you want to search for an element given its key. Specifically, if I give you the key 9, you should give me back (B 9). 

Qn 1: Tell me (in english) an algorithm for testing a potential solution. Specifically  if you are looking for a key k, and a potential solution is (M j), how do you tell if (M j) is a solution or not

How many comparisons did you have to do for this test?


Qn 2. Now embed this into a generate/test. How many potential solutions are there in an n-element set? So, how many comparisons will your generate-test algorithm do in the worst case? 

Note that your answer to 2 is in some sense the worst any searching algorithm can do (it is the counter-part of the O(n! * n) sorting algorithm).   

Can you compare this algorithm to how one would search for a word in a hard-copy dictionary? 

Qn 3. Do you know if it is possible to do search faster than this?


Remember that you are graded on participation; you don't necessarily have to get the "correct" answers; I want you to think about it. 

cheers
Rao