Search found 31 matches

by godrik
Thu Nov 17, 2011 7:52 pm UTC
Forum: Computer Science
Topic: Strongly connected directed graph
Replies: 8
Views: 3316

Re: Strongly connected directed graph

2n-2 looks a lot like 2*(n-1) to me. From one root vertex to the other ones, you need an oriented tree of n-1 edges. Then you traverse the ancestor of the root vertex, ignoring the edges of the tree. Since no edges can be safely removed each edge you add connects a new vertex to the root. There are ...
by godrik
Wed Oct 26, 2011 3:59 am UTC
Forum: Computer Science
Topic: How to proof a lower bound for this problem?
Replies: 14
Views: 3293

Re: How to proof a lower bound for this problem?

I ma not sure if that information is enough, but there is an encoding factor to take into account. For each vertex, one need to can encode its symetric (if it exists) with a size O(log(n)). You need O(n) such encoding, so it costs O(n log n) bits to perform the encoding.
by godrik
Tue Sep 20, 2011 4:45 am UTC
Forum: Computer Science
Topic: Local Search Questions
Replies: 6
Views: 1914

Re: Local Search Questions

For a given problem, it is easy to write an abstraction in C++. Making an abstract algorithm on an abstract problem is pretty much pointless... That's pretty much: template<typename Problem, typename Solution, typename Neighborhood, typename Objective> Solution localsearch(const Problem& P, cons...
by godrik
Mon Sep 19, 2011 12:25 pm UTC
Forum: Computer Science
Topic: Local Search Questions
Replies: 6
Views: 1914

Re: Local Search Questions

For the first question "Does it exists in C++", the answer is no, but is so trivial to write that no one probably care. For what that algorithm is called. It does not look straight out of the book of something existing. But that definitly look like some gradient method or some interior poi...
by godrik
Mon Oct 05, 2009 5:16 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 0645: "RPS"
Replies: 185
Views: 47476

Re: "RPS" Discussion

The japanese are in advance: the reverse polish sushi would be a maki...
by godrik
Mon Jan 26, 2009 10:31 pm UTC
Forum: Computer Science
Topic: Approaching an Unusual Problem aka How To Reinvent the Wheel
Replies: 6
Views: 1399

Re: Approaching an Unusual Problem aka How To Reinvent the Wheel

I would say that the best way of not reinventing the wheel is to know the name of your problem. However, if your problem is weird, then probably a few people know about it. So my advise would be, know your data structure and the basic algorithmic problems: sorting, enumerating, path, covering, ... I...
by godrik
Sat Oct 11, 2008 11:05 am UTC
Forum: Computer Science
Topic: Good resources for parallel computing
Replies: 4
Views: 1439

Re: Good resources for parallel computing

If you are targeting SMP computer, then you should have a you at Cilk ( http://supertech.csail.mit.edu/cilk/ ) which is developed at MIT. It is an extension to the C language that allows to express asynchronicity in functions call. It is pretty efficient and the tradeoff performances vs development ...
by godrik
Sat Oct 11, 2008 10:58 am UTC
Forum: Computer Science
Topic: Knapsack problem
Replies: 22
Views: 6401

Re: Knapsack problem

The problem posed by MrRubix is clearly not knapsack. I found one point still strange: "So you wish to maximize overall value across these sacks by figuring out where to place which item, given that you are not violating the cost constraints of the sacks. The optimal solution for this problem i...
by godrik
Sun Sep 21, 2008 9:31 pm UTC
Forum: Computer Science
Topic: Book to learn java from?
Replies: 13
Views: 2397

Re: Book to learn java from?

I believe that "Thinking in java" is a free book designed to learn the basic of java. Since it is free, it should be easy to get a pdf version of it.
by godrik
Sat Sep 20, 2008 2:51 pm UTC
Forum: Religious Wars
Topic: The Scope Of Religious Wars
Replies: 37
Views: 60734

Re: The Scope Of Religious Wars

When i first saw "Religious Wars", i had read it like "Where to post your troll and flame in order not to post it elsewhere".
So i guess everything trolly enough should be accepted here.
by godrik
Sat Sep 06, 2008 8:49 am UTC
Forum: Computer Science
Topic: 9 questions I have somewhat relevant to CS
Replies: 10
Views: 2532

Re: 9 questions I have somewhat relevant to CS

I graduated in a french university in 2005 (MS in Operation Research) and i am currently finishing my PhD about parallel computing. I'm supposed to have an interview done for my high school engineering course, I'm running out of options and the paper is due in a few days. I don't mean to be rude, bu...
by godrik
Fri Sep 05, 2008 4:16 pm UTC
Forum: Religious Wars
Topic: Looking for an organiser/calendar
Replies: 7
Views: 2448

Re: Looking for an organiser/calendar

well, i am using calcurse ( http://culot.org/calcurse ) every day. It is a calendar based on ncurses that is easy to use and should provide almost all things you need. The tool is easy to use and modify. I am using it coupled with some tools to backup datas on a server and to send me reminder daily ...
by godrik
Mon Sep 01, 2008 8:19 pm UTC
Forum: Computer Science
Topic: Knapsack problem
Replies: 22
Views: 6401

Re: Knapsack problem

I would solve it by creating a tree of all unique outcomes. Start with one node for each price. Then, for each node, add child nodes for each price less than or equal to the node. Sum upwards from all the leafs and check if it is too large, if so, delete it (also see if it it matches). Rinse and re...
by godrik
Wed Aug 27, 2008 9:14 am UTC
Forum: Computer Science
Topic: Knapsack problem
Replies: 22
Views: 6401

Re: Knapsack problem

Knapsack is so well known that i don't believe metaheuristic are useful here. i am making reference to the FPTAS algorithms based on dynamic programming with rounding which performs very well in pratice or even this algorithm that considers all set of k objects and for each set consider the solution...
by godrik
Sun Aug 24, 2008 10:55 am UTC
Forum: Religious Wars
Topic: Best *nix Desktop Environment/Window Manager/whatever
Replies: 243
Views: 45885

Re: Desktops and UIs

Well, i should start with tools i use. I am mainly writing latex on my computer. So i use emacs, make, xfig for drawing, and xpdf to display the result. Sometimes i am doing some programming. Since i work on low level problems, i don't need graphical tool (and yes, i am perfectly confortable with gd...
by godrik
Sat Aug 23, 2008 7:47 am UTC
Forum: Religious Wars
Topic: I'm getting a laptop.
Replies: 20
Views: 7955

Re: I'm getting a laptop.

I know people that install wine on linux just to use foobar2000. So it should be a good music player. I believe the OP should try it.
by godrik
Thu Aug 21, 2008 4:13 pm UTC
Forum: Computer Science
Topic: Time to evaluate function
Replies: 5
Views: 2058

Re: Time to evaluate function

well, i don't think it is related to P and NP. I don't know how exactly things are done in maple but i did some numerical evaluation in the past. I'll give an example, you can compute an approximation of pi by measuring the ratio of area between the circle centered in 0 and the square -1,-1, 1, 1 Yo...
by godrik
Thu Aug 21, 2008 3:52 pm UTC
Forum: Religious Wars
Topic: What OS do you use?
Replies: 321
Views: 146259

Re: What OS do you use?

I voted for debian and other linux distribution. In fact i mainly use ubuntu and debian distribution. However, i use ubuntu repository but my machines does not really looks like an ubuntu one. (i mean that i don't use any ubuntu configuration helper anymore and i am considering migrating to debian s...
by godrik
Thu Aug 21, 2008 7:20 am UTC
Forum: Computer Science
Topic: Static Program
Replies: 11
Views: 2603

Re: Static Program

I was trying to think of something like this to understand P =? NP. I wanted to come up with a problem and a method of solution and somehow say "this solution is the only way to solve it". However I never could construct an example of a problem - of any complexity - and prove that it had ...
by godrik
Wed Aug 20, 2008 2:54 pm UTC
Forum: Religious Wars
Topic: Backwards Compatibility in Web Design
Replies: 10
Views: 3948

Re: Backwards Compatibility in Web Design

I believe a website should be used all the mess that have been invented to turn the web into a computer. I believe that a website i can't use just by parsing the HTML is badly designed. There can exist strange browser that will not decode javascript or css (such as webbrowser for blind people). So a...
by godrik
Mon Aug 18, 2008 11:10 am UTC
Forum: Religious Wars
Topic: Code folding
Replies: 26
Views: 7094

Re: Code folding

no, I mainly write C++ code or articles in latex. i don't see the point in folding when writing latex so let us focus on C++ code. my emacs buffer is usually 50 lines long (or 90 if i really need it). I believe that if a function takes more than 50 lines, it should be split. I use other tool like sp...
by godrik
Mon Aug 18, 2008 11:00 am UTC
Forum: Religious Wars
Topic: Antivirus program for windows yes? no? if so which?
Replies: 54
Views: 23011

Re: Antivirus program for windows yes? no? if so which?

i haven't used windows for 3 years so i am not really sure if this post is still relevant or not. When i used windows, i didn't install any anti-virus or protection software. I ran windows 2000 and kept it up-to-date and used some software to warn me for critical updates. My computer was behind a NA...
by godrik
Mon Aug 18, 2008 7:12 am UTC
Forum: Computer Science
Topic: Static Program
Replies: 11
Views: 2603

Re: Static Program

well, in that case, i think you should ask for intermediate result. But i believe you will not be able to verify that the "computer" did not cheat without doing the computation yourself.
by godrik
Sun Aug 17, 2008 11:58 am UTC
Forum: Computer Science
Topic: Static Program
Replies: 11
Views: 2603

Re: Static Program

it looks like certificates in complexity theory.
by godrik
Fri Aug 15, 2008 8:24 am UTC
Forum: Computer Science
Topic: Math related research in computer science
Replies: 7
Views: 2698

Re: Math related research in computer science

algorithms research is probably what you want. List of companies hiring algorithms theorists: 1) Major research universities 2) No Such Agency well in fact, most large companies need fine tuned algorithmics. For instance, most of telecommunication companies hire theoretical computer scientist to de...
by godrik
Thu Aug 14, 2008 12:46 pm UTC
Forum: Computer Science
Topic: Multiple Method Dispatch
Replies: 38
Views: 4335

Re: Multiple Method Dispatch

One of the given application was collisions in games. I believe you dont want to write a specific code per combination of type but per capabilities of object. Let us take an easy example with two properties, Destroyable and Mobile. When a Destroyable object collides it should lose some HP. When a M...
by godrik
Wed Aug 13, 2008 2:20 pm UTC
Forum: Computer Science
Topic: Multiple Method Dispatch
Replies: 38
Views: 4335

Re: Multiple Method Dispatch

You don't have to write a method for every possible specialization of each type passed into a generic function. You just write methods for the cases you want to handle, and either write a default case to handle other combinations of classes or let the language detect the lack of an appropriate meth...
by godrik
Wed Aug 13, 2008 10:15 am UTC
Forum: Computer Science
Topic: Multiple Method Dispatch
Replies: 38
Views: 4335

Re: Multiple Method Dispatch

I want to reply to the original question. Why not implementing it in languages. My point is that I am not sure it is necessary. You made a complete argument to express how the code source will grow if you don't use multiple method dispatch. You seem to have forgotten that you WILL write an equivalen...
by godrik
Wed Aug 13, 2008 9:58 am UTC
Forum: Computer Science
Topic: Procedural Generation Resources
Replies: 8
Views: 4067

Re: Procedural Generation Resources

perhaps you should look forward 64Kb games or demo-making. I have seen 64Kb games generate all their textures at runtime. In demo making, data size (code+data) used to be small. I guess they used generation techniques. I believe some graphical editor such as photoshop allow you to store the sequence...
by godrik
Sun Aug 10, 2008 10:49 pm UTC
Forum: Computer Science
Topic: Math related research in computer science
Replies: 7
Views: 2698

Re: Math related research in computer science

I don't quite know exactly how this us related to industrial jobs. But there are a lot of field related to mathematics. For instance, cryptography is closely related to arithmetic in finite field. There is also Operation Research in which optimization problems are solved. It involves the use of a bu...
by godrik
Sun Aug 10, 2008 3:27 pm UTC
Forum: Computer Science
Topic: "Random access" PRNG
Replies: 20
Views: 3344

Re: "Random access" PRNG

(sorry for the inconvienience, formulas are written in latex. I believe the explanation are still easy to read.) I would suggest to consider the problem of generating a one dimensional array of $n$ element of a finite field $F$ of size $p$. Let us consider $P_0$ and $P_1$ two PRNG that maps an eleme...

Go to advanced search