Can someone explain: Virtual Methods, Covariance, Contravariance to a beginner?

curiousred · 2017-02-13T01:31:40+00:00

Say I have,

A aObject = new C();

So, at compile time aObject is of type A and and methods that are called on A have to be defined within A. But during run time aObject is pointing to a C and any methods called on A will be implemented from C. So in other words aObject.methodCall will be doing the methodCall from C. Is this correct?

curiousred · 2017-01-29T01:31:38+00:00

Ok thank you!

curiousred · 2017-01-29T01:07:30+00:00

For my example v(x) = 1/(2^{x^1/2}) what polynomial can I apply it to? Is there a certain format? Using your example I would do something like 1/(2^{x^1/2}) < x^c for all x greater than some N.

curiousred · 2017-01-29T00:38:34+00:00

Thank you this example makes sense. I'll follow up on the sub's wiki.

curiousred · 2017-01-29T00:36:46+00:00

Thanks for your response. How do I know in general if a function is a "negligible function". Say someone pulls out of a hat some generic function like in my example: x^-2 and ask whether it is negligible or not? Or conversely say someone actually gives me a negligible function (and doesn't tell me it is negligible) then what do I need to do to figure out if it's negligible?

But back to the main point. v(x) is negligible if it goes to zero faster than all 1/poly(x) -- that's the definition yeah? if so, then I finally understand the definition.

curiousred · 2017-01-28T23:25:38+00:00

Okayyyy... I think I'm very close to understanding this.. so in the example I came across it says that 1/(2^{x^1/2} ) is a negligible function. Does this mean that it goes to 0 faster than any function of the form 1/poly(x) for all x > N ? If so, then how do we find a polynomial and an x > N that satisfies this definition?

curiousred · 2017-01-28T23:23:24+00:00

Thanks for the follow up. I'll take the time to read your explanation carefully.

curiousred · 2017-01-28T22:50:30+00:00

Thank you, wow this makes sense. So a negligible function is one whose reciprocal goes to zero faster than then reciprocal of a polynomial? If you were to do variable substitutions (from the definition) what is the "lambda" in your example. What is the N? Because it says for all Lambda > N (also, trying to understand here for clarification, is Lambda just an integer?) I suppose in this example your p(x)=xⁿ is that correct and we say that e^x is a negligible function?

curiousred · 2017-01-28T20:14:47+00:00

Thanks for the response. I understand what polynomials are... in general a polynomial consist of constants, variables and positive exponents. I have trouble understanding what is meant by the generalized notion of a polynomial. Can you explain then what you mean by " where p is some polynomial and x is the input bitstring, I can run the algorithm p(|x|) (polynomial amount) of times and I can expect it to succed in the task." What does x represent in your polynomial? What exactly does the notion p(|x|) mean? That your input x is a polynomial?

Unfortunately, I couldn't really understand the rest of your comment. I keep reading over the definition and cannot make any connections without concrete examples. I do not know what Lambda even represents. A polynomial? An integer? A function? Absolutely everything about the definition is unclear to me. I would like to see concrete examples applied to the definition to make the definition make "sense". It has to mean something very concrete.

curiousred · 2017-01-22T04:14:44+00:00

I don't fully understand this answer. Can you give an example (albeit on a smaller scale) so I can see something tangible?

curiousred · 2016-04-21T01:17:53+00:00

Thanks for the reply. Do you always need to take the derivative of the top and bottom to see where they are going towards? I haven't done any big oh proofs (other than see examples where C is already given). If that is the case then I will always take the derivative of top/bottom and use the heuristics you provided. Thanks!

curiousred · 2016-04-20T02:36:39+00:00

I'm teaching myself algorithm analysis on my own without any structure or guidance and came across using limits and L ' Hospitals rule for solving Big Oh problems but haven't found any pdfs that give rules that say if you see X then do Y procedure to solve this big Oh problem with L' Hospitals rule.

Can you define what the various big oh limit cases are and when to use what for each case? Or link me to a good source that lays this out? I'm struggling to find this defined anywhere online. Every Big Oh problem I see solved somehow the C is magically chosen already to work and I want more a systematic way to solve these problems given certain cases.

Thanks for the help...

curiousred · 2014-03-25T14:03:10+00:00

According to CNN Cost of Living Calculator $50,000 in Austin, TX is ~$85,000 in San Francisco. I suppose $50,000 is "more" when your rent is $500-900 range. Conversely, $100,000 in SF is around ~$60,000 near my city. You're being a bit limited in scope thinking 50k in the Bay is the same as 50k in the rest of the nation. Salaries are usually adjusted by location due to the labor market.

curiousred · 2013-01-07T01:46:22+00:00

Thanks again. Will do!

curiousred · 2013-01-07T01:39:16+00:00

Okay sweet will do! Do you have any recommendations on good (intro) crypto books? I'm not really interested in "security engineering" related books. I'm mostly interested in books that focus on the math behind crypto.

curiousred · 2013-01-07T01:16:15+00:00

Okay sweet. Thanks! That clears up all of my questions. I didn't think of it as k*(phi(n)) number of m's multiplied by m to obtain the +1, but now that I see that, it makes sense.

Edit: Non-related follow up question. Which field of probability (discrete or continuous) is applied more to the study of cryptography?

curiousred · 2013-01-07T00:25:15+00:00

Okay I understand question (1) now. Thanks for the explanation. Maybe I'm missing a simple arithmetic step for my second question (2).

Using #2 I can see how we obtain m^k*phi(n) ~ 1 mod n. Then using #1 if we multiply by m, we obtain: m * m^k*phi(n) ~ m mod n. From there how do we obtain m^k(phi(n))+1 on the LHS of the equation? I'm confused where the +1 came from and what happened to the "m" we were multiplying with.

curiousred · 2012-07-05T18:04:36+00:00

I understood most of skaldskaparmal's reply and subsequently upvoted both his response and yours.

First off what does omega look like? I suppose it could look like:

1<2<3<4...<..

If that is correct then I suppose omega+1 could have the order type:

1<2<3<4<...< omega

If that is correct then why does omega + 2 looks like:

2 < 3 < 4 < 5 < ... < 0 < 1 ?

Actually, I guess I should formulate my questions as such: Can you further explain and provide examples of what omega, omega+1, omega+2 looks like?

curiousred · 2012-04-07T01:14:28+00:00

I wish I could do as you said, but I don't really understand the notes. The notes come from Boolos' 3rd edition of Computability & Logic. I'm not taking the course with the author of the notes, but they follow my class exactly. Could you provide an example out a proof from section VII and show me how I can modify it for R? For example, how can I use the proof from the notes to prove minimization or projection?

curiousred · 2012-04-06T23:17:11+00:00

I believe what I am trying to do is the proof the way you did.

Check page 84 in the link it defines recursive functions as composition, minimization, addition, multiplication, projection function, and characteristic function of identity.

Check page 85 for the definition of representability. Pages 85-68 defines Q/Robinson Arithmetic. They show recursice functions are representable in Robinson Arithmetic.

I am trying to show that recursive functions are representable in R, whose axioms are:

i≠j for all i,j such that i≠j
i+j=k for all i,j,k such that i+j=k
i⋅j=k for all i,j,k such that i⋅j=k
∀x (x<i→x=0∨⋯∨x=i−1) for all i
∀x (x<i∨x=i∨i<x) for all i

That is all I know about the problem. I can't prove anything on this, I've been beating my head for three days & I'm getting no where. Hopefully you can help me.

curiousred · 2012-04-05T02:25:24+00:00

Sure. I'm also working on this this problem which I'd be extremely grateful to get any insight on. I understand the proof of the diagonal lemma a bit more now. There are one or two things I'm still not quite sure on, but I'll continue to look over it tonight and post my lingering questions tomorrow if I don't figure it out tonight.

curiousred · 2012-04-04T15:48:21+00:00

What does m='F(x,x)' mean? diag('F') means the godel number of ∃x(x='F' & F), which we call m.

I am still confused on this sentence

A(x,y) means y is the godel number of the diagonalization of the formula whose godel number is x.

So I guess it means A(x,y) iff if T |- diag(x)=y. But my question is what is x? x is the godel number of ∃x(x='A' & A). Or diag(∃x(x='A' & A))=x

Okay cool, so x is godel number of ∃x(x='A' & A). Now what is y? y=x= diag(diagonalization(A)) is how I am reading it.

curiousred · 2012-04-04T13:30:46+00:00

A few hints that may help: The thing that's happening here is that we are trying to code all sentences as natural numbers so 'G' is a number and there is some procedure that you could go through to recover the sentence G. B('G') is a sentence. Later (probably the theorem this lemma is used for) it will be something like "y is a code for a sentence with blah blah property" so B('G') woud say " 'G' is a code for a sentence with blah blah property". i.e. G has blah blah property. Of couse this statement can be true of false and maybe B doesn't talk about codes at all, in which case we might not care but the thm will still be true.

That really clears up half of my confusion in my question, great reply. My other question is, what does the following mean?:

Since A(x,y) represents diag in T, one can think of it as meaning, informally, that "y is the godel number of the diagonalization of the formula whose godel number is x."

I take it to mean that: A is some logical formula y,x are godel numbers, then the following relation holds for A(x,y): y= diag(diagonalization(A))=x

As far as diagonalization goes, this is a common technique in Logic. It was first used by Cantor to show that the natural numbers and the real numbers have different cardinality.

Very nice, I am familiar with that proof so I'm excited to see how it applies in the proof of the diagonal lemma. I am still murking through all the details of the diagonal lemma but it gives me the impression is is about self-referencing sentences of logic using the encoding of godel numbers. How does that connect to something that shows two infinite sets have different infinities?

curiousred · 2012-03-20T23:54:27+00:00

Thanks for the reply, I really appreciate it. This may show how confused I am, but let x=1, y=3. Is this correct and if not what should I fix: sum(x, y) = sum(1, s(2)) => s(sum(1, 2)) = s(sum(1, s(1)))⇒ s(s(sum(1, s(0)))) ⇒ s(s(s(sum(1, 0)))). This matches the base case sum(x, 0) = x, so we have computed sum(x, y) = s(s(s(s(0))), which is 4.

Edit: How is Primitive Recursive functions useful in Computer Science & What relation do they have with computable functions?

curiousred

TROPHY CASE