Search found 467 matches

by >-)
Mon Mar 27, 2017 8:38 pm UTC
Forum: Computer Science
Topic: Deliberately bad algorithms
Replies: 120
Views: 26656

Re: Deliberately bad algorithms

because a binary counter going from 1 to n needs at least log n bits. I'm not sure how cpp iterators are implemented, but they are probably just 64 bit datatypes, in which case do not actually solve this problem correctly for graphs with more than 2^64 vertices ive always written it as log^2 n as op...
by >-)
Mon Mar 27, 2017 3:05 pm UTC
Forum: Computer Science
Topic: Deliberately bad algorithms
Replies: 120
Views: 26656

Re: Deliberately bad algorithms

Yes, that is indeed where the extra log factor comes from. And it does work for both directed and undirected versions -- I was just mentioning at the end that in the undirected case, there is an even more efficient algorithm which runs in just log n space.
by >-)
Sun Mar 26, 2017 10:12 pm UTC
Forum: Computer Science
Topic: Deliberately bad algorithms
Replies: 120
Views: 26656

Re: Deliberately bad algorithms

i learned this algorithm for finding a path from vertices s to t in a graph in class recently: //is there a path of length at most k from s to t? loop over vertices w in V: recursively compute if there is a path from s to w with length at most ceil(k/2) recursively compute if there is a path from w ...
by >-)
Thu Mar 16, 2017 7:55 pm UTC
Forum: Mathematics
Topic: behavior of best estimator on some constructed mixture distribution
Replies: 3
Views: 696

behavior of best estimator on some constructed mixture distribution

I'm taking a course in statistical inference. We showed in class that: 1. the best estimator for the mean of a normal distribution (and probably most common distributions?) is the sample mean 2. the best estimator for the range of a uniform distribution which goes from 0 to theta involves multiply t...
by >-)
Tue Mar 07, 2017 1:39 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 727

Re: vertex cut / graph / combinatorics problem

wow, that looks like a pretty solid proof to me, thanks! for the last part, we can do it rigorously by induction clearly, the first path of the villian is at least as high as q1 in all countries then when considering the qk and vk (the villian's kth path), we know that q(k-1) <= v(k-1) then delete a...
by >-)
Mon Mar 06, 2017 9:25 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 727

Re: vertex cut / graph / combinatorics problem

I'm not quite sure that works out for example, consider 3 countries and the elevation of their cities: country 1 has 10 5 4 country 2 has 9 8 3 2 country 3 has 7 6 1 then your method removes nothing, and shuts down 3 airports (either in country 1 or 3) whereas the greedy strategy removes the path 10...
by >-)
Mon Mar 06, 2017 6:05 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 727

vertex cut / graph / combinatorics problem

suppose there are a bunch of countries, each containing a set of cities, and each city has an elevation (all distinct). also suppose someone on a glider wants to visit exactly one city from every country. obviously, since she's on a glider, she can only go from higher elevation to lower elevation ci...
by >-)
Mon Feb 27, 2017 7:10 pm UTC
Forum: Mathematics
Topic: Help with a 9 Variable Equation
Replies: 6
Views: 932

Re: Help with a 9 Variable Equation

what exactly do you mean by proportion of a variable and H? is it the ratio?
by >-)
Mon Feb 27, 2017 12:36 pm UTC
Forum: Mathematics
Topic: WoW: A Strange Game. The only way to win is not to play.
Replies: 7
Views: 1027

Re: WoW: A Strange Game. The only way to win is not to play.

I would think evo algs are better than most optimization algs at dealing with highly nonconvex functions, since if an individual does take a step in the wrong direction and becomes terrible, it is immediately eliminated. plus in the vast majority of cases, deviating a strategy should result in prett...
by >-)
Wed Feb 22, 2017 10:43 pm UTC
Forum: Computer Science
Topic: Why don't we use composite hashes?
Replies: 5
Views: 974

Re: Why don't we use composite hashes?

yes in that case, where you want to fake a certificate, definitely makes the security at least as good as before, because any algorithm which can create fake certificate for the concatenated hash also makes a fake certificate for all the component hashes
by >-)
Wed Feb 22, 2017 2:06 pm UTC
Forum: Computer Science
Topic: Why don't we use composite hashes?
Replies: 5
Views: 974

Re: Why don't we use composite hashes?

i think it's possible that there could be some problems with this, even though it sounds pretty good in practice for example, suppose it just happened that (sha2(x) and md5(x)) xor sha1(x) = x (the first 256 bits of x, or something) [edit: just saw your bit in the post about m1 != m2, but isn't allo...
by >-)
Mon Feb 20, 2017 11:13 pm UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9656
Views: 1399867

Re: Coding: Fleeting Thoughts

That sounds pretty horrifying, and i'm not sure it would run faster after all the overhead. Luckily, I was dealing with prime gaps, so even though the primes themselves had to be put in int64's, the gaps were nice and small enough to fit in a float edit: hmm, so according to nvidia's cuda documentat...
by >-)
Sat Feb 18, 2017 6:53 pm UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9656
Views: 1399867

Re: Coding: Fleeting Thoughts

i've been playing around with brute force testing some open but obscure number theory conjectures on a high end GPU recently. the speedup is nice about 10x ... but not as much as expected. i think this is due to the relatively low int64 compute performance on a gpu compared to the float32 performanc...
by >-)
Tue Jan 31, 2017 1:15 pm UTC
Forum: Mathematics
Topic: variance of a sum of iid random variables
Replies: 2
Views: 937

Re: variance of a sum of iid random variables

ah, nice spot, I'd somehow forgotten about those terms
by >-)
Tue Jan 31, 2017 4:04 am UTC
Forum: Mathematics
Topic: variance of a sum of iid random variables
Replies: 2
Views: 937

variance of a sum of iid random variables

consider y_1 to y_n as i.i.d. random variables with mean u, and let X = sum 1 to n of y_i then E[X]^2 = (nu)^2 E[X^2] = E[(sum i = 1 to n of y_i)^2] = E[sum i, j from 1,1 to n,n of y_i y_j] = sum i,j from 1,1 to n,n of E[y_i y_j] (by linearity of expectation) = sum i,j from 1,1 to n,n of E[y_i] E[y_...
by >-)
Sun Dec 25, 2016 11:27 pm UTC
Forum: Mathematics
Topic: chain rules matrix derivatives
Replies: 2
Views: 993

chain rules matrix derivatives

I have trouble with taking derivatives / gradients / jacobians of matrix expressions. I don't have any "formal education" in this area, and when I search, i can find a lot of identities, which don't help that much. My (naive) approach to finding the gradient of expressions ∇_x f(x) is 1. t...
by >-)
Sat Dec 24, 2016 4:40 am UTC
Forum: Mathematics
Topic: Can't keep up with all the math behind machine learning
Replies: 3
Views: 985

Re: Can't keep up with all the math behind machine learning

I'm sort of in the same position as you, self-studying ML. I don't have much pedagogical knowledge, but my approach is to pick up a standard textbook (Bishop, Mitchell, or Murphy), and work my way through it. I skip through things I find boring if i want, until I have to come back to it to understan...
by >-)
Fri Dec 23, 2016 5:08 am UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 1061

Re: expected "lifespan" of a random process

yeah that sounds right, i'd just realized i had misread something. well that's a really disappointing result, i was really hoping that the lifespan could be finite.
by >-)
Fri Dec 23, 2016 1:19 am UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 1061

Re: expected "lifespan" of a random process

In your first equation, when you write T(n) = 1 + sum_{m=1}^{kn} B(kn,m) p^m T(m) . do you mean T(n) = 1 + sum_{m=1}^{kn} C(kn,m) (1-p)^(kn-m) p^m T(m) with C(kn,m) denoting kn choose m? I'm a bit confused by the B you use. I'm also a bit confused about how your approximation method works. I think y...
by >-)
Tue Dec 20, 2016 1:38 pm UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 1061

expected "lifespan" of a random process

Suppose we have x_0 = 1 and x_i ~ Binomial(k*x_{i-1}, p), where k and p are constants. I want to find the expected value of the largest value j such that x_j > 0. How do I do this? My attempt is to have an indicator random variable, z_i to denote the event that x_i > 0. Then i simply find the sum of...
by >-)
Wed Sep 28, 2016 3:00 am UTC
Forum: Science
Topic: Science-based what-if questions
Replies: 266
Views: 14535

what would happen if we squeezed 4000 people into the volume of 1

Since people are mostly water, and water is mostly incompressible, I'm not sure what would happen when you try to compress water by a factor of 4000. Would degenerate matter form? I think at lower pressures some exotic forms of ice would appear, but I don't think any of those ice types are 4000 time...
by >-)
Tue Jun 14, 2016 3:28 am UTC
Forum: Computer Science
Topic: standard approach to very high dimensional optimization by genetic algorithms / machine learning methods
Replies: 3
Views: 2677

Re: standard approach to very high dimensional optimization by genetic algorithms / machine learning methods

Thanks. I've seen of the examples of neural networks being used to paint one image in the style of another image, and it might be interesting to see if they can be purely creative
by >-)
Mon Jun 13, 2016 3:32 pm UTC
Forum: Computer Science
Topic: standard approach to very high dimensional optimization by genetic algorithms / machine learning methods
Replies: 3
Views: 2677

standard approach to very high dimensional optimization by genetic algorithms / machine learning methods

Suppose you want to generate images which are pleasing to the eye (a human judge does the fitness calculations). For a 1000 x 1000 image with RGBA channels, that's 4 million inputs, which IIRC wouldn't play well with most optimization methods / neural networks and what not. It seems that the algorit...
by >-)
Sat Jun 04, 2016 2:26 am UTC
Forum: Mathematics
Topic: distance between two vertices in a random binary tree
Replies: 1
Views: 1490

distance between two vertices in a random binary tree

Consider the following method of creating a random binary tree, given a set of leaf vertices. 1. Put all leaf vertices in a bucket called U 2. While there is more than one vertex in U 2. a. Remove two and attach them to a new internal vertex v 2. b. Put v back in U 3. return the only vertex in U as ...
by >-)
Wed May 25, 2016 6:22 am UTC
Forum: General
Topic: interpersonal relationships question
Replies: 7
Views: 2679

Re: interpersonal relationships question

Yeah i've heard about it discussed as male vs female but i also find that idea uncomfortable because it's kind of sexist, so I wasn't sure what to think of it. I'll take a look at the video as soon as I have some time ... thanks for the help!
by >-)
Wed May 25, 2016 5:04 am UTC
Forum: General
Topic: interpersonal relationships question
Replies: 7
Views: 2679

interpersonal relationships question

A seemingly accepted sentiment is the fact that when someone comes to you upset with something, you should not try to offer solutions because it will not comfort them further. However, I and some of my friends have noticed that we often enjoy giving and receiving advice from/to each other in these s...
by >-)
Thu May 12, 2016 11:03 pm UTC
Forum: Coding
Topic: arithmetic on functions in haskell
Replies: 4
Views: 2587

Re: arithmetic on functions in haskell

thanks.

about the sorting thing. i declared in GHCi

let id i = let xs = sort [10000000,9999999..0] in xs !! i

and then computed id 1 repeatedly, and it took about the same amount of time (a few seconds) each time.

although i suppose if i actually compiled the code this would be optimized out?
by >-)
Thu May 12, 2016 2:49 pm UTC
Forum: Coding
Topic: arithmetic on functions in haskell
Replies: 4
Views: 2587

arithmetic on functions in haskell

I have a function like this: foo :: Int -> Int foo X = div ((f X) + (g X) + (h X)) ((a X) + (b X) + (c X) where a,b,c,f,g,h :: Int -> Int and something about the code looks a bit clunky because X is repeated so much. Ideally I would like to have (+!) f g x = (f x) + (g x) (/!) f g x = div (f x) (g x...
by >-)
Sat May 07, 2016 1:55 am UTC
Forum: Mathematics
Topic: vector game
Replies: 0
Views: 4749

vector game

Let |v| denote the sum of components of v. Consider the following game. The game state is a vector M in R^n, and is initialized as the 0 vector. A valid move is a vector v in R^n such |v| = 1 and v >= 0 The game state after move v is s(M+v), where s(x) subtracts 1 from the largest component in x. Th...
by >-)
Mon May 02, 2016 2:08 am UTC
Forum: Mathematics
Topic: Dottie Number
Replies: 3
Views: 1805

Re: Dottie Number

by >-)
Thu Apr 07, 2016 6:00 pm UTC
Forum: Fictional Science
Topic: Big Magical Numbers
Replies: 12
Views: 4063

Re: Big Magical Numbers

The order of the monster group is a nice one:
808017424794512875886459904961710757005754368000000000
by >-)
Thu Mar 10, 2016 3:18 pm UTC
Forum: Mathematics
Topic: does every unit length curve lie inside the semicircle?
Replies: 12
Views: 2332

does every unit length curve lie inside the semicircle?

Closely related to Moser's worm problem Can every unit length curve in R ² be rotated and translated to fit inside a semicircle with diameter 1? If we use a circle with diameter 1 instead of a semicircle, this can be accomplished by placing the midpoint of the curve in the center of the circle. The ...
by >-)
Fri Feb 26, 2016 3:59 pm UTC
Forum: Mathematics
Topic: Help with the Chain Rule
Replies: 21
Views: 2632

Re: Help with the Chain Rule

the second equation is (without using prime notation) (d/dx) f(u) = (d/du) f(u) * (d/dx) u and it is not the case that (d/dx) f(u) = (d/du) f(u) = f'(u) so the substitution does not work intuitively, the tangent line lies "parallel" to the curve at the point it is touching, although wikipe...
by >-)
Fri Feb 26, 2016 2:14 am UTC
Forum: Mathematics
Topic: looking for a probability theorem
Replies: 3
Views: 1404

Re: looking for a probability theorem

Can you give a counter example? I can't seem to think of any off the top of my head.
by >-)
Thu Feb 25, 2016 4:16 am UTC
Forum: Mathematics
Topic: looking for a probability theorem
Replies: 3
Views: 1404

looking for a probability theorem

Let X = sum x_i, Y = sum y_i (over all i) where ∀i : x_i, y_i, X, Y are random variables If ∀i : E[x_i] > E[y_i], we can say E[X] > E[Y] This is by linearity of expectation. I'm looking for a theorem with a similar "structure" which I can use to show this: If ∀i,k : P(x_i > k) > P(y_i > k)...
by >-)
Fri Feb 12, 2016 4:17 pm UTC
Forum: Mathematics
Topic: Cardinality of subset of the powerset of naturals
Replies: 5
Views: 1203

Re: Cardinality of subset of the powerset of naturals

Ah, I think I understand now. Thanks
by >-)
Fri Feb 12, 2016 3:59 pm UTC
Forum: Mathematics
Topic: Cardinality of subset of the powerset of naturals
Replies: 5
Views: 1203

Re: Cardinality of subset of the powerset of naturals

But for c = 0, isn't there still no natural number k which describes the size of infinite elements of S? Yet, since there is only one, or a constant number of sets in S of size |k| for each k in N (because k^c = 1), S is now countable.
by >-)
Fri Feb 12, 2016 3:48 pm UTC
Forum: Mathematics
Topic: Cardinality of subset of the powerset of naturals
Replies: 5
Views: 1203

Cardinality of subset of the powerset of naturals

Let N denote the natural numbers and fix some constant c in N. Consider a subset S of P(N) such that for all k in N, there no more than O(k^c) elements in S of size k. In other words, for each k in N, our set S only has a polynomial number of elements of size k, as opposed to an exponential number s...
by >-)
Tue Feb 02, 2016 6:21 am UTC
Forum: Mathematics
Topic: Trying to divide a spherical shell into equal-volume "wedges
Replies: 4
Views: 2123

Re: Trying to divide a spherical shell into equal-volume "we

Pick any axis of the sphere which passes through the center. Then, to split the sphere into n regions, simply create n slices from pole to pole, each with angle 2pi/n in width. This sliced orange is an example where n = 8 (i think -- the image is too blurry to tell), and the width of each slice is p...
by >-)
Sat Jan 30, 2016 4:43 am UTC
Forum: Mathematics
Topic: Optimizing a growth model
Replies: 0
Views: 2416

Optimizing a growth model

This problem was probably inspired by a variety of games, especially those of the cookie-clicker variety. In fact, I remember one such game which revolved around a mathematician proving theorems at an super-exponential rate. There exists an initial quantity of goods. These goods can be exchanged for...

Go to advanced search