1,153 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
2
comment How to extract operators from the grammar productions for conflict resolution in LALR parser?
In that case, this is how Bison handles it: gnu.org/software/bison/manual/html_node/…. Specifically, the last token (so terminal, not nonterminal) of a production is used to determine its precedence. For "E + E", this would be "+".
Feb
1
comment How to extract operators from the grammar productions for conflict resolution in LALR parser?
Might you be asking the following: suppose we have a shift-reduce conflict, say between shifting '*' and reducing "E * E", how do I determine the 'operator' of "E * E" so that I can apply the priorities that the user defined? In other words, are you having trouble unifying that you only define priorities between operators, while shift-reduce conflicts are conflicts between operators on one hand and productions on the other hand?
Jan
19
comment First and Follow Sets for a Grammar
When I said "I'm not entirely sure how to answer your question", I meant that I'm not sure how to 'prove' that your solution is really correct. I'm quite sure they are correct though, having implemented a compiler and multiple parsing algorithms myself. Anyway, I hope you did well on your exam.
Jan
19
comment First and Follow Sets for a Grammar
I've checked your solution by hand and ran it in my parsing library, and it is correct. I'm not entirely sure how to answer your question.
Dec
1
comment How lookaheads are propagated in “channel” method of building LALR parser?
I think cs.stackexchange.com is probably the site where you're most likely to get a good answer for these kinds of questions.
Nov
20
comment LL(∞) and left-recursion
I think three of your questions are answered by this post: cs.stackexchange.com/a/48/92. For the rest I also recommend you start questions over at that site. Don't forget to specify 'better' more precisely.
Oct
2
comment Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?
For proofs that deciding running times is in general impossible, see here and here - the answers there prove even more than you ask for, actually.
Apr
27
comment Merge sort versus quick sort performance
Try this question: cs.stackexchange.com/questions/3/…
Feb
12
comment What language does Introduction to Algorithms by Cormen use?
I'm pretty sure they use the language 'English' in that book, but translations are probably available.
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
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.
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
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
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
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.