Computer Science

« first day (1543 days earlier) ← previous day next day → last day (2894 days later) »

emab

10:26 AM

@vzn the paper is published in CIKM, identifying str

Topk-k structural holes in social networks

Ground-truth communities in snap benchmarks

4 hours later…

vzn

2:09 PM

@emab nice, plz put a link for it, wanna see it :)

sasha

3:00 PM

Q: How to compute the sum of this series involving golden ratio, efficiently?

Definitions Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series can also be looked up here : A004957, with first few terms being $3,6,8,11,14...$ . Let $t$ be the...

any hints ?

this problem is feeding on me :D

3 hours later…

EvilJS

5:49 PM

@sasha hey, could you explain how you do matrix exponentiation to reccurence? It seems that not only you do it. I asked around, searched, thanks to Rick I tried Fibonacci, and now I am lost.

It seems like heavy work, the only thing that might benefit are large matrices done in parallel, but otherwise I barely survived the example...

@sasha sorry from debouncing, but maybe feed it more? A bit more, like three days more?

You know, many of the math problems are cool, and when you know how to solve them, it is easy, but there is a cost (I paid too much), that when you take shortcut, obtain equation or the name of problem, it is like "ok, I feed this data to that equation, solved, no sweat". I do not know for sure whether it works that way (you should ask professional mathemathician which I am not) so you gather vast amount of algorithms, problems or equations and then connect them.

But I can tell you for sure, professionaly, that the more time you think about it and try yourself, the actual synaptic response is stronger, so you will remember it so much better.

sasha

6:07 PM

@EvilJS sure I will change the question a bit.

I agree with you.

EvilJS

And when I encounter Project Euler task (mostly thanks to you) and I have no idea what is the background, I try anyway, think about it, never fall to brute force, and solve it with some idea (maybe not the best one) but at least this is training to me - make optimal solution.

sasha

As far as matrix exponentiation is concerned if you have done it for fibonacci

EvilJS

@sasha hey, it is not about this question, I really like to understand why matrices are used for recurrence.

sasha

then its preety much the same

wait I will paste a link

A: Modulus of sum of sequence of Fibonacci numbers

Let $S(n)$ be the sum of first $n$ fibonacci modulo MOD( in you case MOD=1000000007). What you want to find is $answer=(S(M)-S(N-1)) \% { MOD}$. If $awswer$ if negative, then $answer=answer+MOD$. So we have to basically find $S(n)$ for any $n$ efficiently. This can be done in $O(logn)$ by matrix ...

@EvilJs here you go

EvilJS

@sasha yeah, I tracked solution and then tried myself, but I do not see why it is superficial, beneficial, and I have learned it like yesterday.

sasha

6:11 PM

Its useful because say you want the n=10^16 th fibonacci number

if you go by matrix exponentiation you can find it in O(log(n))

which is far better than the obvious linear method

so basically its use ? speed if you ask me

EvilJS

But the answer below yours reduces the sequence and it shows how to generate sum from element

sasha

there is a matrix in the question

EvilJS

Maybe I messed something, but using Binnet formula and the solution below, it is less than nlogn

sasha

all whose entries are constant

thus I can just raise it to the power n-2 ( which can be done in O(logn) )

@EvilJS comeoncodeon.wordpress.com/2011/05/08/…

here is a good link

hope it helps

EvilJS

@sasha ok, but my point of uncertainity comes from the second answer, which is constant time...

@sasha wow, yes, exactly thank you, it finally kicked-in.

sasha

6:21 PM

also there is no better way than to implement.

here is a basic question where

you can implement this idea

spoj.com/problems/FIBOSUM

EvilJS

@sasha yes, for some people (like me) it is good way.

@sasha well, that is my problem, I am so sure that matrix-free code will be faster...

1 hour later…

EvilJS

7:50 PM

@Raphael if you are interested at C exp, give some task, I can provide results from students, from someone else students, my own and unfortunate but with very high exp not so many.

I can do one purely practical contest, that the fastest (and proper) code gets benefits, so they would participate ;)

Raphael

8:06 PM

@EvilJS Nah, that would be unethical. ;D

EvilJS

It will be hard anyway, to make a good setting: the same amount of time, same compiler? No algorithms available, no way to solve it differently, no external libraries, no inline asm? lookup tables made in advance? [...] etc. No optimizer? Or let us check the binary from runtime? And I will just assume that if any paper or resource shows shortcut or something was not forbidden, this will be exploited by some people... But at least two real homogenous groups.

@Raphael well, it really depends on how it is done.

Raphael

@EvilJS I'd say you have to have at least 20 people per language, all with roughly the same prior knowledge in their respective one, all in one room. Pick a task that does not per se favor one of the languages. Then given them X minutes. Count how many have something correct, and time the functional solutions.

EvilJS

Oh, this comes unhandy

I would say more than 25 wouldn't harm, but totally doable with C, but if I take some other language, they either did C course or are not fresh (got longer exp in respective language, which I cannot for sure measure)

Mhm, R or python count?

The only group of more than 5 people that started about the same time without prior exp, but it would just give really different results, in advance not fair ;)

And yeah, 100% ethical to give students oportunity to compete in the fastest solution contest, which is not obligatory, and will give them feedback how good they are and the winner deserves good score anyway ;)

Just years X solution goodness is easier to measure, and obviously with limited time to minutes... Every one-liner language would benefit in actually finishing the task in time...

What can be done in C that cannot be done in C++?

You can name your variable "new" or "delete" ;)

@vzn did you got answer for "community" or read my links?

2 hours later…

Raphael

10:12 PM

@EvilJS Yea, I don't think students are a good population for most languages. It's hard to controll the parameters.

1 hour later…

EvilJS

11:23 PM

@Raphael I want a special badge :] is it doable?

Don't get me wrong, just wanted to start the topic, there are pro tempore, mod, area51, retired faq.... It seems that there are some unique ones that are not achiveable any more. It seems like some of them are, well, promoting bad behaviour? So...

And I have read like book ot two, maybe no more than 20 about gammification...

« first day (1543 days earlier) ← previous day next day → last day (2894 days later) »

all rooms