Yioop - PHP Search Engine

Midterm Clemency.

Originally Posted By: dburke

Hey all,

I think most of us are in the same pickle, trying to get through the midterm clemency, and in particular on problems

(note: ^ means next item is a superscript)

(c) Give an example of a function which is o(log^(k) n) for any fixed k, but is w(1).
(d) Prove your example from (c) works.

Dr. Pollett has indicated that we can collaborate for this so I thought I'd kick it off.

For (c) I think most everyone know by now that a good example function is iterated log:

log^* n

For (d) I've been working towards a proof in three parts

1) show that log^* n dburke — Fri May 02, 2014 3:35 pm <hr>

'''Originally Posted By: dburke''' Hey all, I think most of us are in the same pickle, trying to get through the midterm clemency, and in particular on problems (note: ^ means next item is a superscript) (c) Give an example of a function which is o(log^(k) n) for any fixed k, but is w(1). (d) Prove your example from (c) works. Dr. Pollett has indicated that we can collaborate for this so I thought I'd kick it off. For (c) I think most everyone know by now that a good example function is iterated log: log^* n For (d) I've been working towards a proof in three parts 1) show that log^* n dburke — Fri May 02, 2014 3:35 pm <hr>

-- Midterm Clemency

I indicated a few times people can collaborate on this. So feel free to work on the
problem here. Remember if you see an answer here or elsewhere you need to understand
it before coming to my office to try to get the points back.

I indicated a few times people can collaborate on this. So feel free to work on the problem here. Remember if you see an answer here or elsewhere you need to understand it before coming to my office to try to get the points back.

-- Midterm Clemency

Originally Posted By: tran_lam

I think in the order:
1/ we need to prove log(k+1) n = o(log(k) n)
we can prove it by lim (n -> infinite) = 0; however, we have to come up with n0 which depends on c.
2/ then log* n tran_lam — Sun May 04, 2014 7:18 pm <hr>

'''Originally Posted By: tran_lam''' I think in the order: 1/ we need to prove log(k+1) n = o(log(k) n) we can prove it by lim (n -> infinite) = 0; however, we have to come up with n0 which depends on c. 2/ then log* n tran_lam — Sun May 04, 2014 7:18 pm <hr>

-- Midterm Clemency

As a hint, try to carefully show just
log m cpollett — Tue May 06, 2014 9:13 am <hr>

As a hint, try to carefully show just log m cpollett — Tue May 06, 2014 9:13 am <hr>

-- Midterm Clemency

Originally Posted By: quoc

Wouldn't a good example function be log log n? It still serves as a function o(log^k n).

'''Originally Posted By: quoc''' Wouldn't a good example function be log log n? It still serves as a function o(log^k n).

-- Midterm Clemency

log log n is not an example function for this problem -- it grows too fast

-- Midterm Clemency

Originally Posted By: quoc

Awh. Okay. Back to the drawing board.

'''Originally Posted By: quoc''' Awh. Okay. Back to the drawing board.

-- Midterm Clemency

Originally Posted By: ahmed93

I got a question on part b of the question. What exactly does it mean by "Give an example of a random variable we used in one of our average case analyses algorithms this semester?"

'''Originally Posted By: ahmed93''' I got a question on part b of the question. What exactly does it mean by "Give an example of a random variable we used in one of our average case analyses algorithms this semester?"

-- Midterm Clemency

Originally Posted By: dburke

ahmed, see http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%287%29

'''Originally Posted By: dburke''' ahmed, see http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%287%29

-- Midterm Clemency

Originally Posted By: ahmed93

Yeah I did look at it and that is where I got the definition for random variable. But when is it asking for an example, I don't really understand it. Is the example the coin flip?

'''Originally Posted By: ahmed93''' Yeah I did look at it and that is where I got the definition for random variable. But when is it asking for an example, I don't really understand it. Is the example the coin flip?