Reputation
1,431
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
8 14
Newest
 Guru
Impact
~41k people reached

  • 0 posts edited
  • 0 helpful flags
  • 8 votes cast
Dec
4
comment Algorithm for an exact solution to the Travelling Purchaser Problem
Since the decision version of this problem (is there a tour with cost at most k) is in NP, and since you can reduce this problem to that decision problem via binary search in polynomial time, you should easily be able to find an O(poly(n)2^n) algorithm for this problem. Alternatively, you could reduce the decision to a 3SAT problem and use any of the 3SAT solvers to solve this problem. If I have time, I may answer with an algorithm tailored for this problem. Note that unless P=NP, no algorithm will be very fast.
Nov
21
comment best and most used algorithm for finding the primality of given positive number
Do you want to generate prime numbers, find the factorisation of a number of find if a number is prime? These three questions are completely different and have wildly different answers.
Nov
17
comment Can anyone help solve this complex algorithmic problem?
@JackV.: see my update for a modified algorithm that also handles the case where the gas tank isn't infinitely large.
Nov
17
revised Can anyone help solve this complex algorithmic problem?
Added limited gas tank size case
Nov
16
comment Closest location - Heapify or Build-heap
The problem with heaps is this: your heap will have to store the distances to your current point. If your current point changes, all the distances in the heap are now wrong, which means you have to completely recreate your heap to contain the distances to the new point.
Nov
16
comment Can anyone help solve this complex algorithmic problem?
@mattnz: on one hand, you're right: as a software engineer, you should always make sure your requirements are clear and appropriate for the situation. However, this question is clearly not a real-life situation: why'd we want to drive in a circle on this road? Why can we start at any station we like? Does an airplane drop us off at a station? Either the question was purely to test algorithmic skills, or the question is a reformulation of an actual question, and in the actual question the equivalent of the gas tank has unlimited capacity. Or at least, that's how I look at it.
Nov
16
answered Closest location - Heapify or Build-heap
Nov
16
awarded  Nice Answer
Nov
15
answered Can anyone help solve this complex algorithmic problem?
Nov
13
awarded  Yearling
Nov
11
comment How many copies are needed to enlarge an array?
Because then the i*n/2^i terms make sense: if i = 1, then you talk about 1 * n/2, which would correspond to half the input being copied once. In his example, there are four x positions that get copied once, and 8/2=4, so n=8 would make more sense. If n=16, then 16/2=8 elements would supposedly be copied once, which simply doesn't match the example.
Nov
11
comment How many copies are needed to enlarge an array?
Thank you, it looks much nicer now - I'm used to LaTeX formatting, and I don't think that's possible on Programmers.SE.
Nov
11
revised How many copies are needed to enlarge an array?
added 1002 characters in body
Nov
11
answered How many copies are needed to enlarge an array?
Oct
31
comment Best way to parse optional grammar rules?
You can quite naturally handle these kinds of rules in various parsing algorithms, Earley being one of them, but I'm not aware of a similar method for LL parsing.
Oct
7
answered Do real-world algorithms that greatly outperform in the class below exist?
Aug
28
comment Should a competent programmer be able to come up with his own shortest path algorithm?
I was thinking more along the lines of timing attacks etc, stuff almost no programmer knows about. It's not always an issue, but an important one nonetheless. Also, combining cryptographic primitives usually doesn't work like one expects, this is also a hard part of security.
Aug
27
answered Should a competent programmer be able to come up with his own shortest path algorithm?
Aug
12
awarded  Commentator
Aug
12
comment Does having a funny or silly name hurt a project?
One of the more well-known and often-used proof assistant programs is called Coq (coq.inria.fr). It looks like the webmasters of that site are French, which may have something to do with their choice of the name, but I'd be uncomfortable to say 'I proved this theorem using Coq'...