[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Blog Qn 1: What's good for sorting must be good for searching too!
- To: Rao Kambhampati <rao@asu.edu>
- Subject: Blog Qn 1: What's good for sorting must be good for searching too!
- From: Subbarao Kambhampati <rao@asu.edu>
- Date: Fri, 31 Aug 2012 09:57:13 -0700
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:x-google-sender-auth:message-id :subject:to:content-type; bh=uMu5+a64Q7aUXN2+bletSc05XFSaDKsrcFzo7FHtdLc=; b=J5Opiz6OQ7Z5b3ut+rQg2kkvcBb+sQDwtFFXxjrR5pQiQGE2GfBAnKllJIt2O7BxEc ZvNL/VBpneEz8LPhGrZCnsHhLsSQFFeaPrEP5lGb1kzMOB4TXF6aC5H9NzRU1kalSxjG +iDESu4+cIUhuNTbpcBM23egSQjCfSaHZ8Tp9lmLImcS5Gewx4OmSm5snkuWdzupNcmC xmeZb0jeIma95/cWM9SaWceXrNGqdCnVSoG5sP1NglNbbXelaNUw9vMCd0M8Olhst2Y/ /l0hPlZ27yM21iJiUNdfNTO7zzCy7pq7wkqOdiMe5EMTcVzsZKzTa12p3xSmZYX/oimW W81A==
- Sender: subbarao2z2@gmail.com
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