Problem Detail: I have the following problem: Define the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function. How do Read More …
Category: Uncategorized
[Solved]: Are there undecidable properties of non-turing-complete automata?
Problem Detail: Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability). I would like to get an example (if possible) of an undecidable problem that is Read More …
[Solved]: Encoding the sequence 0110 and determining parity, data bit and value
Problem Detail: I’ve been struggling with several Hamming code/error detection questions because the logic behind it doesn’t seem to make sense. eg.1 eg.2 I don’t really understand the above two examples and the calculations taking place. How were the conclusions reached Read More …
[Solved]: Is there a data-structure for semilattices similar to a tree data-structure?
Problem Detail: If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (more or less) Read More …
[Solved]: Algorithms: Difference Constraints
Problem Detail: I’m currently studying for my algorithms final and I came across a practice problem that I can’t seem to figure out. Here’s the problem: Consider the following set of difference constraints: x1 – x4 <= 1 x2 – x1 Read More …
[Solved]: What is this fraction-like “discrete mathematics”–style notation used for formal rules?
Problem Detail: In the paper “A Conflict-Free Replicated JSON Datatype”, I encountered this notation for formally defining “rules”: What is this notation called? How do I read it? For example: the DOC rule doesn’t have anything in its “numerator” — why not? Read More …
[Solved]: Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
Problem Detail: We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I’m sure. But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus Read More …
[Solved]: How to decode multiple-digit gamma codes and get the gap sequence?
Problem Detail: How to decode gamma code ($gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($gamma$ codes) with a brief example of decoding can be found here. But in their example there is only one case Read More …
[Solved]: Returning a random subset with length k of N strings while only storing at most k of them
Problem Detail: Here’s the problem. I’ve written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$. The subset must contain Read More …
[Solved]: Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
Problem Detail: Tomorrow is my presentation and I want to clear my concepts… I’ve read that in DFA, “For each state, transition on all possible symbols (alphabet) should be defined.” Is for each state, defining transition on all possible symbols mandatory Read More …
