Lower Bound Proofs

Ricky · 2007-07-12 15:22:29

As started here with the Tower of Hanoi, this thread will be for lower bounds proofs. Lower bounds are used to tell how difficult a problem is. The solution to the TOH was in the form of 2^n meaning that no matter what you do, you can't solve it faster than 2^n steps. If, for example, you could solve it in n steps, we would say this is a much easier problem.

So the question is where to go from here. Most lower bounds proofs have to do with things in computer science: insert, sort, search, etc on different data structures. For example, proving that (with a few basic and almost trivial assumptions) you can't sort any faster than n*log(n).

So the question is do you want to look at computer science related questions, or should we keep this more general? In the mean time, here is a problem to keep you busy while we decide.

You have a robot in an infinitely long hallway and your task is to find a door in the wall. You may walk how ever far you wish to your left or right, and turn around whenever you please. Each time you take a step, you check to see if the door is in your new location. The door is an unknown (but finite) number of steps away. What is the minimum number of steps you must take? That is, using the best algorithm, what is the most number of steps you will ever possibly have to take?

a. You know the door is to your left.
b. You don't know what direction the door is, but you do know it is n steps away.
c. You don't know where the door is, but it is within n steps away.
d. You neither know where the door is, nor how far away it is.

mikau · 2007-07-12 17:02:29

cool stuff, ricky.

For anyone who does this, please use the hide tag as not to spoil it for others.

mikau · 2007-07-12 17:30:55

Okay, here is

and

still thinking on c and d.
again i don't know much about how non mathematical proofs are done so i apologize for any noobishness. If i'm making some assumptions on a and b, please tell me and give me a hint or two, ricky. Hopefully it will help me get the hang of these.

Last edited by mikau (2007-07-12 17:32:45)

mathsyperson · 2007-07-13 00:03:45

Ricky wrote:

The solution to the TOH was in the form of 2^n meaning that no matter what you do, you can't solve it faster than 2^n steps.

I can do it in (2^n)-1.

For the robot-door problem, do the steps have to be one wide? For example, if you make the robot walk a distance of 2 but don't care about whether or not there is a door at the intermediate position, then would that count as one step or 2 steps?

Also, does the robot need to be next to the door to finish or is it enough for you to just know where the door is?

Ricky · 2007-07-13 02:38:25

You know the door is a finite distance away, so it might make sense to let the door be d steps away, then express your answer in terms of d. So far you're 1/2 mikau. I would have said 2/2, but in light of mathsyperson's question below, b is wrong.

I can do it in (2^n)-1.

I was writing in big-theta notation...

For the robot-door problem, do the steps have to be one wide? For example, if you make the robot walk a distance of 2 but don't care about whether or not there is a door at the intermediate position, then would that count as one step or 2 steps?

Nope, every step you take is one step, and on that step you always check.

Also, does the robot need to be next to the door to finish or is it enough for you to just know where the door is?

Wow! I'll accept knowing where the door is. Never thought of that one, great job. Of course, you can only use it on one of them.

mikau · 2007-07-13 06:57:13

are you saying b is wrong because we now want how many steps to find the door instead of how many to reach the door?

Last edited by mikau (2007-07-13 06:57:29)

Ricky · 2007-07-14 16:44:17

No answers to (c) or (d)?

mathsyperson · 2007-07-14 19:59:28

mikau · 2007-07-15 12:57:17

I was away all weekend, and haven't had much time to think on this one.

is this right, ricky?
edit:

I'll work on C tommorow.

Last edited by mikau (2007-07-15 14:10:57)

Ricky · 2007-07-16 08:05:32

mikau · 2007-07-16 14:46:08

Thanks, Ricky!

Last edited by mikau (2007-07-16 14:51:23)

Ricky · 2007-07-17 14:56:23

Ricky · 2007-07-17 16:09:56

The previous problem asked you to do a worst-case analysis of an algorithm for a problem. In this, you are simply looking at what the worst possible situation for your algorithm is and how much it "costs". It is very useful because as it is the worst case, any time you are asked to solve the problem, it must cost less than this.

However, there are other types of analysis. Best case cost is what it will cost in the best case for a given problem. This isn't quite as useful, but it can be used to compare two different algorithm. Again, remember that best case cost is algorithm specific. What is best for one algorithm need not be best for another.

Then of course, there is the average case cost. Typically, the average is hard to compute, even for simple problems, until you get used to summation notation and evaluation. Like worst-case cost, it can be extremely useful in determining if one algorithm is "better" than another.

Do the robot problem above, but instead, for best cost with the algorithm you've used. Then do average cost for parts (a), (b), and (c). You can try (d) if you wish, but I'm fairly certain it won't be easy. When doing this, can you think of a better algorithm in each part? Note by better, I'm referring to in the best and then average case only.

mikau · 2007-07-17 16:16:46

x_x NOOOO!!! (dies)

Ricky · 2007-07-17 16:56:17

Too much? Want to move on to a different problem and away from robots? Just say the word.

mikau · 2007-07-17 17:18:00

Mmmm... I would like to see something different now actually. I'll think about those later I guess. The reason they frighten me is they obviously involve probability and permutations. Things I haven't done since precalc and i don't know much beyond what you'd learn at that level.

Last edited by mikau (2007-07-17 17:20:59)

Ricky · 2007-07-17 17:51:53

Not exactly. Assume the door occurs in position n. f(n) is the cost of finding the door there. Then the average cost is:

But I'll post another problem dealing with this in the morning. Computer science related questions are ok, I take it?

mikau · 2007-07-17 18:32:04

certainly!

Ricky · 2007-07-18 12:29:48

Here is some code for bubble sort:

swapMade = true
While swapMade is true
   swapMade = false
   for j = 0 to j = list.size-1
      if list[j] < list[j+1] //This is the only list comparison
         swap list[j] with list[j+1] //This is the only swap made on the list
         swapMade = true
      endif
   endfor
endwhile

Find out what the best and worst case are for this sort, and find the cost in number of comparisons between list elements. I'll be attempting to work out the average case, so feel free to do that as well if you want to give it a shot.

mikau · 2007-07-19 18:54:13

the old bubble sort, eh?

Well i'll work on it when i get some time. I've been teaching myself linnear algebra and C++ over the summer and its consuming a lot of my freetime. I'll tackle this next chance I get.

Question, i'm not sure what language you are using. Do I need to consider that a for loop makes a comparison for the entry condition on every itteration of the loop?

Ricky · 2007-07-20 03:58:51

Nope, it's only comparisons between list elements. Note my comment on line 4.

John E. Franklin · 2007-07-20 10:29:57

Read Me--Editted also
Just one more thing Ricky...
Subtract one more at the end of the inner loop so when the comparison is made on the last two elements, you don't overstep the array boundary.
Isn't it neat the way items get moved along and dropped when a more significant value is found and then that is moved along and dropped off?? Pretty cool and easy to write.

Last edited by John E. Franklin (2007-07-21 03:16:30)

Ricky · 2007-07-20 13:22:45

Actually, best to take out the outer loop and change it to a while. Changes made.

mikau · 2007-07-29 13:51:44

hey, Ricky! I finally got a chance to work on this. here are my solutions

Ricky · 2007-07-29 14:52:15

Your worst case is right, but what happened with your best case? You talk about swapping, but I need a number of comparisons.

Math Is Fun Forum

#1 2007-07-12 15:22:29

Lower Bound Proofs

#2 2007-07-12 17:02:29

Re: Lower Bound Proofs

#3 2007-07-12 17:30:55

Re: Lower Bound Proofs

#4 2007-07-13 00:03:45

Re: Lower Bound Proofs

#5 2007-07-13 02:38:25

Re: Lower Bound Proofs

#6 2007-07-13 06:57:13

Re: Lower Bound Proofs

#7 2007-07-14 16:44:17

Re: Lower Bound Proofs

#8 2007-07-14 19:59:28

Re: Lower Bound Proofs

#9 2007-07-15 12:57:17

Re: Lower Bound Proofs

#10 2007-07-16 08:05:32

Re: Lower Bound Proofs

#11 2007-07-16 14:46:08

Re: Lower Bound Proofs

#12 2007-07-17 14:56:23

Re: Lower Bound Proofs

#13 2007-07-17 16:09:56

Re: Lower Bound Proofs

#14 2007-07-17 16:16:46

Re: Lower Bound Proofs

#15 2007-07-17 16:56:17

Re: Lower Bound Proofs

#16 2007-07-17 17:18:00

Re: Lower Bound Proofs

#17 2007-07-17 17:51:53

Re: Lower Bound Proofs

#18 2007-07-17 18:32:04

Re: Lower Bound Proofs

#19 2007-07-18 12:29:48

Re: Lower Bound Proofs

#20 2007-07-19 18:54:13

Re: Lower Bound Proofs

#21 2007-07-20 03:58:51

Re: Lower Bound Proofs

#22 2007-07-20 10:29:57

Re: Lower Bound Proofs

#23 2007-07-20 13:22:45

Re: Lower Bound Proofs

#24 2007-07-29 13:51:44

Re: Lower Bound Proofs

#25 2007-07-29 14:52:15

Re: Lower Bound Proofs

Board footer