Serving the Quantitative Finance Community

Search found 63 matches

by cdmurray80
January 14th, 2007, 5:54 am
Forum: Brainteaser Forum
Topic: Tournament by K.O.
Replies: 21
Views: 90149

Tournament by K.O.

Hmm, sorry this is approximate and not exact, but I know for the complete ranking you don't need more than O(N log N) since that's the lower (and upper) bound on comparison sortinghttp://en.wikipedia.org/wiki/Comparison_sort
by cdmurray80
December 4th, 2006, 10:46 pm
Forum: Brainteaser Forum
Topic: Algorithms - Drawing from a multi-nomial distribution
Replies: 9
Views: 88885

Algorithms - Drawing from a multi-nomial distribution

<t>That's cool. That was suggested to me by my graduate algorithms teaching assistant, and he knows his stuff!For a slightly harder problem, try my other post "Drawing from a multi-nomial distribution...part II"I think Aaron and Peterw basically gave optimal answers to this question...thank you!! </t>
by cdmurray80
December 4th, 2006, 12:33 am
Forum: Brainteaser Forum
Topic: Algorithms - Drawing from a multi-nomial distribution
Replies: 9
Views: 88885

Algorithms - Drawing from a multi-nomial distribution

<t>Aaron, that's pretty interesting. That's one way to take advantage of special problem structure. Here's anotherIF you can approximate the probabilities with rational numbers, and there is some constant integer a, and "a" items fit in memory, then there are integers x1 ... xN so thatp(1) ~= x1 / a...
by cdmurray80
December 3rd, 2006, 11:47 pm
Forum: Brainteaser Forum
Topic: Algorithms - Drawing from a multi-nomial distribution
Replies: 9
Views: 88885

Algorithms - Drawing from a multi-nomial distribution

That's cool, I've never heard of that. Can you give a short description, or do I need to refer to a paper??
by cdmurray80
November 29th, 2006, 1:31 am
Forum: Brainteaser Forum
Topic: Algorithms - Drawing from a multi-nomial distribution
Replies: 9
Views: 88885

Algorithms - Drawing from a multi-nomial distribution

Anyone wanna take a shot at the "discretized" version: p(1) = x1 / a , p(2) = x2 / a, p(3) = x3 / a, ... and the parameter "a" fits in memoryO(1) is possible
by cdmurray80
November 29th, 2006, 1:30 am
Forum: Brainteaser Forum
Topic: Machine Scheduling
Replies: 1
Views: 87517

Machine Scheduling

Hint:Define L_(max) = MAX_i ( L_i )So L_(max) is the amount of machine time required by the job which needs the most machine timeDefine W_(avg) = (1/M) * SUM_i( L_i )W_(avg) = the total amount of machine-time required, divided by the number of machines
by cdmurray80
November 29th, 2006, 1:28 am
Forum: Brainteaser Forum
Topic: Ants III
Replies: 8
Views: 88328

Ants III

I was getting stuck for like 15 minutes before I realized...don't try to cover a square with 17 circles...that can't be done (or at least I don't know how to). Try with 25...
by cdmurray80
November 27th, 2006, 1:58 am
Forum: Brainteaser Forum
Topic: Machine Scheduling
Replies: 1
Views: 87517

Machine Scheduling

<t>[From an algorithms class with Gary Miller, does NOT require knowledge of algo)Your factory has M identical machines. There are N > M jobs to do. Each job must be scheduled to a single machine, cannot be split, and each job i requires L_i units of dedicated machine time . A machine can do only on...
by cdmurray80
November 22nd, 2006, 9:54 pm
Forum: Careers Forum
Topic: How quant are asset mgmt groups ?
Replies: 6
Views: 88974

How quant are asset mgmt groups ?

<t>I am now taking a class at CMU MSCF taught by a Goldman Asset Management guy. He was a math professor at CMU for 9 years developing interior point algorithms and stuff...an insanely smart guy, and every bit as "quant" as anyone on this board I'm sure. He said (I'm HEAVILY paraphrasing) that there...
by cdmurray80
November 22nd, 2006, 9:27 pm
Forum: Brainteaser Forum
Topic: An old tree (problem) with a new twist
Replies: 5
Views: 88691

An old tree (problem) with a new twist

Got it...now I understand thanks
by cdmurray80
November 22nd, 2006, 3:45 pm
Forum: Brainteaser Forum
Topic: Drawing from a Multinomial Distribution - part 2
Replies: 7
Views: 88820

Drawing from a Multinomial Distribution - part 2

<t>Sure, you can wait until there have been N^2 updates, and your searches are still O( log(N^2)) = O(2 logN) = O(logN). It's so nice how logs work with asymptotics.I still think the regenerations would be O(1), however, I'm not familiar with asymptotic bounds below O(1) so I can't say for sureAnywa...
by cdmurray80
November 22nd, 2006, 5:06 am
Forum: Brainteaser Forum
Topic: An old tree (problem) with a new twist
Replies: 5
Views: 88691

An old tree (problem) with a new twist

<t>Sorry, gambler B bets max every time??? it's not clear from the statementIf so, his probability to have any money at the end is 2^-100If he does win every bet, his wealth will be 50*3^100, since he triples his money each time. The product of these should give the expected value for gambler B. But...
by cdmurray80
November 22nd, 2006, 12:47 am
Forum: Brainteaser Forum
Topic: Drawing from a Multinomial Distribution - part 2
Replies: 7
Views: 88820

Drawing from a Multinomial Distribution - part 2

<t>That's very clever...I didn't think of anything like that! It's sort of an O(1) update with a lag once in a whileI think, if all of the probability updates increase, rather than decrease, event probabilities, you can get guaranteed asymptotic average update time of O(1). All you do is wait until ...
by cdmurray80
November 21st, 2006, 9:16 pm
Forum: Brainteaser Forum
Topic: Drawing from a Multinomial Distribution - part 2
Replies: 7
Views: 88820

Drawing from a Multinomial Distribution - part 2

<t>The first thing you said is what I meant...sorry. You needn't keep the sum of all the weights constant. In fact I'd suggest you don't, since otherwise any update would be O(N). Assume that we always keep track of the sum of the weights. Then, when we draw from the distribution, we draw a random u...
by cdmurray80
November 21st, 2006, 3:19 pm
Forum: Brainteaser Forum
Topic: Drawing from a Multinomial Distribution - part 2
Replies: 7
Views: 88820

Drawing from a Multinomial Distribution - part 2

<t>You are given some multinomial distribution over N events. That is, you are given p(1), p(2), ..., p(N), where all of the p(i) are real and non-negative. The p(i) do NOT sum to 1...that is they are not normalized. There is a reason for this...of course you can normalize them yourself.The goal is ...