Problem Detail: there is some kind of priorities for the elements in propositional logic ? for example : p ∧¬q → r , given this ,we there may be two options (p ∧¬q) → r OR p ∧ (¬q → r) Read More …
Author: ignougroup
Computing the mode of XOR subsequences
Problem Detail: I was confronted with this problem in an online programming challenge and it has been bugging me since: In the problem, you are given a list of 16-bit numbers, say $a_0, a_1, …, a_n$. An “XOR subsequence” is defined Read More …
What is the difference between control flow graph & interprocedural control flow graph?
Problem Detail: I am doing research on control flow analysis on aspect oriented programs and I found in some papers an interprocedural approach for doing control flow analysis on others call graph or control flow graph. Is there a real difference Read More …
What is a computer year?
Problem Detail: In one of the text book its mentioned that ‘running time of this algorithm is 200 computer years’. Can somebody please explain what is the meaning of a computer year? Asked By : Kumar Answered By : adrianN Computer years, like Read More …
Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration
Problem Detail: I’m looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector, but it’s only for fast append. Scala’s Vector has effectively constant-time append Read More …
Union of two automata
Problem Detail: I need to find a minimal DFA given the following information: $ {a^nb : ngeq 0} cup {b^na: n geq 1}$ Now, maybe I’m not seeing this properly, but I don’t see how this is possible: the first one Read More …
Subset Sum: reduce special to general case
Problem Detail: Wikipedia states the subset sum problem as finding a subset of a given set of integers, whose sum is zero. Further it describes it as equivalent to finding a subset with sum $s$ for any given $s$. So I Read More …
Horn clause to Prolog
Problem Detail: At the needs of my HW at uni I need to transform some Horn clauses to Prolog but I cannot figure out how to do it. I found out some guides but they describe how to do it with Read More …
How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?
Problem Detail: According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine. Read More …
For what kind of data are hash table operations O(1)?
Problem Detail: From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad. Read More …
