## Search found 467 matches

- 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...

- 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.

- 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 ...

- 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...

- 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...

- 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...

- 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...

- 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?

- 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...

- 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

- 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...

- 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...

- 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...

- 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

- 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_...

- 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...

- 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...

- 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.

- 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...

- 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...

- 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...

- 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

- 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...

- 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 ...

- 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!

- 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...

- 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?

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?

- 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...

- 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...

- Mon May 02, 2016 2:08 am UTC
- Forum: Mathematics
- Topic: Dottie Number
- Replies:
**3** - Views:
**1805**

### Re: Dottie Number

Here's an archive of the blog

https://web.archive.org/web/20140517164 ... gspot.com/

here's the page about the chord

https://web.archive.org/web/20110811013 ... ircle.html

https://web.archive.org/web/20140517164 ... gspot.com/

here's the page about the chord

https://web.archive.org/web/20110811013 ... ircle.html

- 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

808017424794512875886459904961710757005754368000000000

- 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 ...

- 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...

- 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.

- 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)...

- 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

- 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.

- 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...

- 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...

- 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...