1,163 reputation
613
bio website http://-
location Eindhoven, The Netherlands
age 24
visits member for 3 years, 8 months
seen May 3 at 20:57

I'm a Design Engineer at ASML, Veldhoven. I'm a graduee of the university of Technology in Eindhoven, The Netherlands.

I have a publication! http://arxiv.org/abs/1306.4919 - ESA2013, co-won best paper award.


Feb
5
awarded  Analytical
Jan
17
answered Is there a general method to evaluate the optimality of an optimization algorithm?
Jan
16
comment A good schema to represent integer numbers from 0 to infinity, assuming you have infinite linear binary storage?
Assuming you generate 128 bit numbers sequentially: if we upper-bound the computation capacity of all computers by giving every human a petaflop-computer, then it would take 9 million years before these numbers run out. If on the other hand every human would randomly generate 600 million 128 bit numbers, there's a 50% chance they generate 1 duplicate. Is that good enough for you? (en.wikipedia.org/wiki/Universally_unique_identifier) If not, using 256 bits multiplies both these figures by 2^128=3.4*10^38, which is more than the square of the age of the universe in seconds.
Jan
15
comment Is there a general method to evaluate the optimality of an optimization algorithm?
How do you define the 'optimality' of an optimization algorithm? Do you want to do analysis on its source code and then report what its approximation factor is?
Jan
13
comment Find all points within a certain distance of each other?
@psr: you might be talking about programmers.stackexchange.com/questions/120012/…?
Jan
13
answered Find all points within a certain distance of each other?
Jan
12
comment Is it bad interview practice to have candidates write a linked-list implementation?
The question I have in mind is 'why even consider using a data structure that is in just about all cases inferior to another data structure'? Linked list are slower for most operations than lists based on arrays; the only thing linked lists are good for is deletion in constant time, but there are very few situations in which that is needed. Note that I'm not talking about whether it'd be a good data structure for an interview question: the concepts involved might be a good test, I don't know.
Jan
11
comment Is it bad interview practice to have candidates write a linked-list implementation?
'C# (...) natively use lists extensively' and 'efficiency via pointers isn't the issue it used to be': you do know that these native lists are not linked lists but rather lists based on arrays? Arrays tend to perform better because of caching. In fact, IIRC the .NET framework didn't even have linked lists until 2.0. I'm pretty sure the majority of the C# programs out there don't use linked lists.
Jan
9
comment Algorithmic problem: Picking Cards
This answer is correct: you can reduce the running time to linear by using counting sort on the cards, precomputing the answers of countLessOrEqualThanMax and then iterating over the cards in their sorted order.
Jan
1
answered Smallest lexicographical rotation of a string using suffix arrays in O(n)
Jan
1
answered Writing a lexer in C++
Dec
28
answered InterviewStreet (Vertical Sticks) just a tip where to get started
Dec
28
comment InterviewStreet (Vertical Sticks) just a tip where to get started
I'm trying to understand what this code is doing, and I can't see how the expression 'x+y' can possibly mean something: you add a length of a stick to its position in the input, which are two unrelated values, unless I'm missing something. Does anyone understand this bit?
Dec
21
revised Is there a subset of programs that avoid the halting problem
added 86 characters in body
Dec
20
comment Is there a subset of programs that avoid the halting problem
@SK-logic: I'm not sure what you mean. Presuming your comment was aimed at me: I don't call any programming language 'amazingly useless'. I merely think that the algorithm presented in the paper is amazingly useless, since the set of programs it works on correctly is highly uninteresting. That has nothing to do with programming languages.
Dec
19
revised Is there a subset of programs that avoid the halting problem
added 227 characters in body
Dec
19
comment Is there a subset of programs that avoid the halting problem
As for your second issue: the states I'm talking about is not the same as the 'state of a machine' one usually talks about (which involves the state of everything that can have state), but rather the state the finite state automaton used to control the Turing machine is in, which roughly corresponds to the line of code a program is working on at any point during execution. On repeating a line of code the contents of your memory may be different, so this does not immediately imply halting at all. I'll update my answer to make this more clear.
Dec
19
comment Is there a subset of programs that avoid the halting problem
As for your first issue: as remarked in the paper, showing that some model of computation is Turing complete does not preserve how many programs exactly halt, so the result they prove does not immediately mean anything for other models of computation. I'm well aware of Turing completeness, and I'm not completely sure why it makes my answer 'wrong'.
Dec
19
answered Is there a subset of programs that avoid the halting problem
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.