texts: Reconstructing an Array via Time-Intensive Subset Queries

texts:
I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.
I am given access to an array of numbers. However, I am only allowed to query it by specifying an arbitrary subset of indices, in response to which I am then given the sum of the elements at those positions. These queries are quite costly, specifically they run in time $\tilde{O}(n^2)$ time (where $\tilde{O}(\cdot)$ hides polylogarithmic factors). I want to determine the element at each index in the array (i.e. reconstruct the array) using as little time as possible.
Of course, it is possible to do this by querying each element on its own. This algorithm does $n$ queries and hence has total running time $\tilde{O}(n^3)$. I am wondering if there is a faster way. Adaptivity does not help with this problem, so any algorithm would have two steps: First, it executes a fixed sequence of queries, and then reconstructs all elements using the query answers. Ideally, both steps run in time $o(n^3)$. So far, any set of $o(n)$ queries that I looked at makes recovery impossible. This might be the case for any such set of queries (and my intuition screams that this is probably the case), but I cannot see a proof for this.
I'd love an answer that either shows a faster algorithm or proves that $o(n)$ queries are impossible, but answers with partial insights would also be great.


texts: CSMA/CD with binary exponential backoff: Do both back off or just the loser?

texts:
I've been given two PC's that are connected via Ethernet, and as such are using CSMA-CD with binary exponential backoff.

Now, both PC's, let's call them $A$ and $B$, are trying to send data simultaneously. So, the first time both randomly choose a number from $\{0,1\}$. Let's say $A$ wins (i.e. $A$ picks 0 and $B$ picks 1) and sends the first frame of its data.

Instantly after sending the frame, the next collision between $A$ and $B$ occurs.
Now, in my given scenario, for some reason $A$ only picks from $\{0,1\}$, while $B$ picks from $\{0,1,2,3\}$.

Why is that the case? I don't see how this algorithm is any better than if $B$ gave up right away after losing once.
First: Just using a wider range doesn't stop the two PC's from colliding at all. If only $A$ has enough frames to send, the next collision will occur eventually anyway.
And for every collision afterwards, the chance of $B$ losing just ever increases.
So, $B$ will starve and give up eventually anyway as well.

Why not just let $B$ give up instantly, and let $B$ wait till $A$ certainly has finished? Is my given scenario somehow wrong, or am I missing the point?


texts:
According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no information online regarding a possible equality between $L$ and $NP$.

Such an equality doesn't directly violate the space-hierarchy theorem or the time-hierarchy theorem, and so I don't have any idea how to disprove it.


texts:
I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.

1) What is the exact memory usage of a BST or hash table, for storing $n$ values? For instance, if we consider a BST, are $n$ pointers sufficient for storing it? (We can neglect the size of the stored values. The only thing that interests me is the storage overhead involed by the use of a specific data structure)

2) If the choice has to be determined by the cost in space, subject to the constraint of a fast enough access time, what is the best data structure to use?

For the space cost criteria, I would like a precise description. I'm interested in two types of usage: static and dynamic. I ask this question in the context of a C implementation.

I'm mostly interested in values around $n=100000$.


texts:
I understand that a computer memory sequential word must always include at least two bits so it must be binary and therefore cannot be unary.
Must a word be binary (and never unary)?
That is to ask; can there be a "unary" computer memory sequential word?

This question might relate to my other question - Must a Turing machine tape be binary?


texts:
This is a follow up to the How does Stack Inspection work? that explores the notion in more detail

Stack inspection is a mechanism for ensuring security in the context of the JVM and CLR virtual machines when externally downloaded code modules of different levels of trust may be running together. That system libraries need some way of distinguishing between calls originating in untrusted code and calls originating from the trusted application itself. This is done by associating with code the principal corresponding to its origin. Then access permissions are recorded on the stack and whenever a call to a sensitive, system method is made, the stack is traversed to see whether the appropriate permissions for the principal making the call are present on the stack.

  What are the limitations of stack inspection? What mechanisms have been proposed to replace it? Have any significant changes been made to the model since it was introduced in the late 90s?


texts: Regularity of “middles” of words from regular language

texts: I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$ is regular, where $\Sigma$ is the alphabet. In other words $P$ is the language of all substrings of words from $L$.  How do I prove that $P$ is regular?


texts: Constructing a context free grammar with starting state

texts:
I'm supposed to construct a context-free grammar generating all strings in :
{(ab)$^{m}$c$^{n}$(ba)$^{m}$ : m, n, ≥ 0}
So far I have V = {A, S, a, b, c}, Σ = {a, b, c}, and R = (1) S -> A (2) S -> abSba (3) A -> cA and (4) A -> e
but I'm not sure what to do for the starting state, S. Also, I'm not sure if V should actually be {A, S, ab, ba, c} because the a's and b's always appear as ab or ba.


texts: undecidable problem and its negation is undecidable

texts:
A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.

However, can anybody give me an example in which both a problem and its complement are undecidable and not semidecidable? I thought about the diagonalization language Ld, but it does not seem to me that the complement is undecidable.

In that case, does that mean that a Turing Machine M can "lose" some strings that instead should be recognized, since they're part of the language we're trying to indentify?


texts: Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?

texts:
I had a question regarding CNF (Chomsky normal form) in formal language theory.

I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.

In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production

$$S_0 \rightarrow S$$

but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S_0 \rightarrow S$ production). Also, the textbook that I'm using (Formal Languages and Automata, 6e - Peter Linz) allows the start symbol to be on the right side of a production.

What's the reason that this production is frowned upon?

Thank you.


texts: Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

texts:
According to this statement:

Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.

$\{a^n b^n c^n \mid n\ge0\}$ is not deterministic context-free language so is $\Sigma^* \setminus \{ a^n b^n c^n \mid  n \ge 0\}$ a deterministic context-free language?
If it is, how does it look like?
($\Sigma^*$ means every possible string that can be generated with $\{a,b,c\}$.)


texts: Finding recurrence relations for dynamic programming algorithms

texts:
Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by the recurrence: $T(n) = n  + T(1) + T(2) +...+ T(n-1)$. This is $O(2^{n})$.

One can use dynamic programming to store the values of $f(1),f(2),..,f(n-1)$  in an array so that computation of $f(n)$ only requires $O(n)$ time as long as the values of $f(1),f(2)...,f(n-1)$ are already stored in an array. The total time complexity of such a dynamic programming algorithm would be $O(n^{2})$ which makes sense if you consider the actual psuedocode of such an algorithm. But what would be the recurrence? Would it be $T(n) = n + \max(T(1),...,T(n-1))$ ?


texts: Terminology for vertices in graph connecting vertices "in" and "outside of" a given component

texts:
Basically, I am looking for a (well-defined) term for some "borderline" vertexes interconnecting other vertices in and outside of a given connected component.

More specifically, given directed graph $G = (V_G, E_G)$ and (strongly) connected component $C = (V_C, E_C)$, how do people refer to such vertices $x$, where,

$x \in V_C$;
$\exists\ v \in V_G \setminus V_C$ such that $(x, v) \in E_G \setminus E_C$;

My friends have suggested names such as gateway vertex and border vertex. But I feel obliged to make sure we are not reinventing something well-known / well-defined.

It would be helpful if someone can help identify an equivalent (or likewise) definition of this concept in the literature. Thanks a lot.

EDIT:

Please note that -- unlike the well-defined concept of cut vertex -- the concept of borderline vertex (or whatever it should be called) is with respect to a specific given component, not the entire graph.


texts:
Possible Duplicate:
  Pumping lemma for simple finite regular languages

The pumping lemma says that for any regular language $L$, there exists a constant $p$ such that any word $w$ in $L$ with length at least $p$ can be split into three substrings, $w = xyz$, where the middle portion $y$ must not be empty, such that the words $xz, xyz, xyyz, xyyyz, \ldots$ constructed by repeating $y$ an arbitrary number of times (including zero times) are still in $L$.

Consider a regular Language which contains only one string - the alphabet $a$. ie, $L = \{a\}$.

Now, in this $L$, what would be the value of $p$, and possible values of $x$, $y$ , $z$?

I am confused to the boundary cases of the pumping lemma.


texts: TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

texts:
So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$  $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The latter requires demonstrating an algorithm which computes the L in polynomial space. This is usually achieved by having recursive calls such that is re-used.

In TBQF proof, the equation $\phi_{i+1}(A,B)$= $\exists Z [\phi_{i+1}(A,Z)
 \land \phi_{i+1}(Z,B) ]$ ($Z$ is mid-point )is default recursive relation for computing TBQF truth. In any standard proof, it is said that $\phi_{i+1}(A,B)$ is computed two times and for $m$ nodes, this formula explodes hence, other recursive-relation should be used to bound.

However in Savitch's proof, the recursive relation is $Path(a,b,t)$ = $Path(a,mid,t-1)$ AND $Path(mid,b,t-1)$ accepts then ACCEPT. In proof, it is stated that this relation reuses-spaces.

My Question is Why in TBQF relation space explodes while in Path, it is reused? Both of these relations looks more or less same to me because both refers to i-1 instances and will need space to store them?.


texts: What ist the time complexitiy of an algorithm with the running time of $a^{n^b}; a,b>1$? And how is it compared to factorial complexity O(n!)?


texts: Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals

texts:
Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line.

Suppose we have four integer numbers, A, B, C and D.

For example:

_________________A___________________________B__________________
___________________________C__________D_________________________

or

_________________A___________________________B__________________
___________________________C____________________________D_______

Consider the notation AB as the set of all consecutive numbers A, ...., B, and the interval CD as the set of all consecutive numbers C, ..., D.

I would like to know a simple yet abstract and generalizaed resoning (mathematical demonstration would be really apreciated) that we can apply if we want to find all intervals consisting of the "disjoint" numbers and the "overlapping" numbers between both set of numbers, AB and CD.

Example 1: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7}, we have the following subsets for each set AB and CD:

for AB: {2, 3}, {4, 5, 6, 7} and {8, 9}
for CD: {4, 5, 6, 7}

Example 2: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7, 8, 9, 10, 11, 12}, we have the following subsets for each set AB and CD:

for AB: {2, 3}, {4, 5, 6, 7, 8, 9}
for CD: {4, 5, 6, 7, 8, 9} and {10, 11, 12}

But, which one would be a great and yet simple reasoning behind disjoint and overlapping sets of numbers between two given set of integer numbers?

Thanks very much for any clue!!


texts:
I have $m$ equations of the following form:
$$x_1+x_2+\cdots+x_n=s,$$
where each variable is either 1 or 0, and the total number of variables is $m\approx3{,}000$. So I’m thinking of modeling each variable as a binary variable and each equation as a CNF formula so that, once I combine all formulas into one CNF, I can solve it using a SAT solver.

I’ve tried to solve the system of equations using Gaussian elimination, but it was too slow since the time complexity is $m^3\approx27{,}000{,}000{,}000$.

My problem is how to encode addition efficiently and simply. My only known approach is to model $a+b$ as a circuit and then convert the big totality of $n$ circuits to a CNF. Is there a better way?


texts: What is determinism in computer science?

texts: I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number generator to make branching unpredictable, it is still really non-deterministic (but harder to prove so).


texts: Number of Configurations of LBA(Linear Bounded Automaton)

texts:
The lemma is:

  Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet.
  There are exactly $qng^n$ distinct configurations of $M$ for a tape of
  length $n$.

I want know why LBA has $qng^n$ configurations.

Following is the proof:

  A configuration of $M$ is like a snapshot in the middle of its computation. A configuration consists of the state of the control, position of the head, and contents of the tape. Here, $M$ has $q$ states. The length of its tape is $n$, so the head can be in one of $n$ positions, and $g^n$ possible strings of tape symbols appear on the tape. The product of these three quantities is the total number of different configurations of $M$ with a tape of length $n$.


texts: Call-by-push-value vs Fine-grain Call-by-value

texts: It seems to me that Fine-grain call-by-value already subsumes CBV and CBN, using lambdas as thunks. What does CBPV improve upon FG-CBV or in what way is it "better"?


texts: Context-free grammar for $\{a^x b^y : x \neq y\}$

texts:
I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of b's. With the special condition that the number of b's has to be unequal to the number of a's.

Thus, the grammar should generate words like:

aaaabbb
aaabb
abbb

So basically I could do something like this:

$\ G=(N,T,P,S)$

$\ N = \{S\}$

$\ T = \{a,b\}$

$\ P = \{S=aa(S|\epsilon)b\}$

But then the words would always have $\ 2n$ a's and n b's:

aab
aaaabb
aaaaaabbb

So how is it possible to make the number of a's uncorrelated of the number of b's, without being equal?


texts: What does 'Describe the language of this automaton' mean?

texts:
I've been asked to do this as part of an assignment. Here is the automaton:

I understood it as describing in terms of the 5 tuples so I wrote:
The states are as follows:  Q = {A, B, C}
The alphabet is as follows: Σ = {0,1}
The start state is A
The accepting state is C
The transition function is as follows:

Is this what is meant by describing the language or am I supposed to answer using different metrics?


texts: Binary integer programming problem without exponential memory

texts:
Consider binary integer programming problem with n variables.
I think the branch and cut algorithm takes exponential memory. What are
existing algorithms without much memory? Please suggest.


texts:
In Reinfrocement Learning (RL) in Neural Networks (NNs), I've seen two approaches to Q-learning.

The first is to tile the state space with basis functions using Spiking Neural Networks (SNN) to represent reward. This approach is used in "A neural reinforcement learning model for tasks with unknown time delays" by Daniel Rasmussen and is expanded upon in "A neural model of hierarchical reinforcement learning" by the same author.

The second is to use Deep Neural Networks (DNN) to map the state space to the reward space, such as the various publications used by Deep Mind.

From what I've read so far, I believe the differences between these two approaches are as follows:

SNNs take less long to train
SNNs can be deployed on existing neuromorphic hardware
SNNs are more easily extended into continuous cases
SNNs do more inference between states
DNNs can map larger and higher dimensional state spaces
DNNs require less knowledge of the task for the programmer

Is this analysis accurate? Are there other differences that I've missed?


texts: When do structural hazards occur in pipelined architectures?

texts:
I'm looking for some relatively simple examples of when structural hazards occur in a pipelined architecture.

The only scenario I can think of is when memory needs to be accessed during different stages of the pipeline (ie, the initial instruction fetch stage and the later memory read/write stage).

I'm thinking that there are many more structural hazards in more complex architectures, such as superscalar. Does it class as a structural hazard when an instruction is dispatched to an execution unit but is queued because the unit is in use?

If this is highly architecture-specific, then just assume MIPS or something similar.


texts:
I was reading a paper about the PageRank algorithm and it mentions $ 2 $ ways to compute the weighted score for each vertex: If $ M_{n \times n} $ is a positive column stochastic matrix that represents the transition state for each vertex in the graph, then we know that the sequence $ Mz, M^{2}z, \dots, M^{k}z $ converges for $ z = [\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}]^{T}. $ This is the first way to compute the final weighted score. The second way is to find the probabilistic eigenvector $ v^{\ast} $ corresponding to the eigenvalue $ 1 $ of $ M $ (we know that $ M $ must have $ 1 $ as one of its eigenvalue from the P-F Theorem).

For the first approach, the rate of convergence is $ \frac{1}{|\lambda_{2}|} $ where $ \lambda_{2} $ is the second largest eigenvalue (in magnitude) of $ M $ and for the second approach, computing $ v^{\ast} $ has runtime complexity of $ O(n^3) $ where $ n $ is the size of the matrix $ M. $

So my question is suppose I want to determine which approach requires less time to perform, is there any metric to compare the $ 2 $ approaches?

This is how I understand the notation of "rate of convergence" and its relation to big-O notation, but there's no explicit function for the iterative method to do the limit computation, so I am currently stuck. Is that what you have in mind when you say about the concept of convergence? If no, can you tell me how you understand this concept?


texts:
I was trying to prove the next exercise 1

It's not look so hard, but with some tries, I couldn't find out a way to show it, I was supposed wrong assumptions.

To convince myself if that relation really happened, I use Mathematica to plot some a range.

Do you have some ideas?

1 Ian Parberry and William Gasarch. Problems on algorithms, volume 50. 2 edition, 2002.


texts: Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

texts:
I was told this question may be better received here.

  Prove that the probability that an insertion into a cuckoo hash table
  probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, where $n$ is the number of elements in the set.

I'm trying to use induction, but I don't know if this is the best method to go about proving this.

The worst case to probe $1$ array location would be when all $n$ element are stored in the first table, and we get probability $\frac{n}{2n} = \frac{1}{2} = O(\frac{1}{\sqrt{2}})$ for insertion.

The worst case to probe $2$ array locations would be when all $n$ elements are stored in the first table, we hit the first table, and we succeed in the second table. This has the same probability as it does to probe $1$ array location.

However, I don't know how to continue the analysis. For example, what's the worst case probability to probe $4$ array locations? The question statement implies that the worst case is $O(\frac{1}4)$, but how do we achieve this result? If the first and second tables each have $\frac{1}4$ of their array locations occupied, then the worst case to probe $4$ elements would be hitting in the first table, hitting in the second table, hitting in the first table again, then finally inserting into the second table $\Rightarrow \frac{1}4\cdot\frac{1}4\cdot\frac{1}{4}\cdot\frac{3}4 = \frac{3}{256} \not = \frac{1}4$.

Does anyone have a clearer way of thinking about this problem?


texts: finding amount of errors that can be fixed based on code length

texts: i tried to look online and search this site and others but haven't found any good explanation to the following simple question: how many errors can a code with length k(k>2)fix?


texts: Relationship between Undecidable Problems and Recursively Enumerable languages

texts:
I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting problem belongs to a class of languages which are not even recursively enumerable. But the article suggests that the halting problem is recursively enumerable. My doubt is about the relationship between undecidable problems and recursively enumerable languages. Are all undecidable problems recursively enumerable languages?

If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?

Also could any one suggest a problem which is not even recursively enumerable?


texts: Regularization term moving the hyperbolic plane

texts:
When we train a network, we usually have an error function which usually looks like this:

$$Error = (output - target)^2$$

When we add a regularization term, it looks something like this:

$$Error = (output - target)^2 + reg term$$

I understand that there are many different ways of defining the reg term, but in this example, we can make it the sum of all weights.

When we do this, are we just not moving the hyperbolic plane up and down? The slope of it should stay the same everywhere and thus not really make a difference in finding a minimum of the error function.


texts: Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ Regular?

texts:
Question

Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ regular?

My Understanding/Doubt
We can say that Language

$L_{2}=\left \{ wxw \,\,|\,\,w,x \,\in  \left ( a+b \right )^{*}\right \}$ is regular

By making  $x=(a+b)^{*}$ and $w=\epsilon$
Based on above Understanding , i can say that $L$ is regular?

My regular expression will be-:
$L=a(a+b)^{+}a+b(a+b)^{+}b+a(a+b)^{+}b+b(a+b)^{+}a$
Am i right?


texts: Finding a correct regex for the strings with at least two $0s$

texts:
I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $0$'s over the alphabet $\Sigma = \{0,1\}$."

I made this: $(0+1)^*0(0+1)^*0(0+1)^*$

I checked the answer and it is: $1^*01^*0(0+1)^*$

Is there any difference between the two?

If mine is also correct, what should be the CFG for it?


texts: What is f(x,y) in Digital Image Processing?

texts: I am a novice in Digital Image Processing, and while reading the book of DIP by Gonzalez and Woods, I find that they have represented digital image as $f(x,y)$ but nowhere it is mentioned what is $x$ and $y$ actually that we are passing to the function $f?$ Does $f(x,y)$ represent the intensity of the points located at point $(x,y)$, so does $f$ actually returns the intensity of the pixel at that point or is it something else that I am missing?


texts:
Currently I'm trying to understand a proof of the statement:

"A language is semi-decidable if and only if some enumerator enumerates it."

that we did in my lecture. One direction of the proof goes as follows:

Let E be an enumerator that enumerates L. We construct a TM M, that semidecides L in the following way:

Given an input string x, we design M in the following way :

Run E to enumerate the next string y of L. Compare it with x.
If x=y accept, else goto 1

Am I right if I say, that it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis?
Furthermore is there anything to take care of when constructing an algorithm in such a context as not to hurt the "definition" of intuitively computable?

Thanks for any answers.


texts: How to chose the condition for expand in hash-table?

texts:
How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the next cell that contains elements?

And in addition, I want that - the number of cells that I need to move about them between cell without elements to other cell with elements is O(1) too?


texts: What is the role of abstract machines in the Curry-Howard isomorphism?

texts:
By abstract machines I mean things like the SECD machine, Krivine's machine or more generally machines with states/memory/registers/stack/accumulator...

According to Wikipedia page of the Curry-Howard isomorphism, we have a correspondence with the Sequent Calculus where the left/right introductions rule matches with the constructors of codes and evaluation stacks. And the priority of rules application is related to call-by-value and call-by name reduction.

So I'm looking for more information than what we can find in Wikipedia.


texts: I know that $O(\max(m, n)) = O(m + n)$, but is there a similar simplification for $O(\min(m, n))$? It could be $O(n) \cap O(m)$ but it does not simplify the notation that much…


texts: Proving the (in)tractability of this Nth prime recurrence

texts:
As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm curious as to its name, its reductions, and its tractability towards the solvability of the gap between prime numbers.

Tersely speaking, we can define the gap between each prime number as a recurrence of preceding candidate primes. For example, for our base of $p_0 = 2$, the next prime would be:

$\qquad \displaystyle p_1 = \min \{ x > p_0 \mid -\cos(2\pi(x+1)/p_0) + 1 = 0)  \}$

Or, as we see by plotting this out: $p_1 = 3$.

We can repeat the process for $n$ primes by evaluating each candidate prime recurring forward. Suppose we want to get the next prime, $p_2$. Our candidate function becomes:

$\qquad \displaystyle \begin{align}
p_2 = \min\{ x > p_1 \mid f_{p_1}(x) + (&(-\cos(2\pi(x+1)/p_1) + 1) \\
                                   \cdot &(-\cos(2\pi(x+2)/p_1) + 1)) = 0\}
\end{align}$

Where:

$\qquad \displaystyle f_{p_1}(x) = -\cos(2\pi(x+1)/p_0) + 1$, as above.

It's easy to see that each component function only becomes zero on integer values, and it's equally easy to show how this captures our AND- and XOR-shaped relationships cleverly, by exploiting the properties of addition and multiplication in the context of a system of trigonometric equations.

The recurrence becomes:

$\qquad f_{p_0} = 0\\
\qquad p_0 = 2\\
\qquad \displaystyle
  f_{p_n}(x) = f_{p_{n-1}}(x) + \prod_{k=2}^{p_{n-1}} (-\cos(2\pi(x+k-1)/p_{n-1}) + 1)\\
 \qquad \displaystyle
 p_n = \min\left\{ x > p_{n-1} \mid f_{p_n}(x) = 0\right\}$

... where the entire problem hinges on whether we can evaluate the $\min$ operator over this function in polynomial time. This is, in effect, a generalization of the Sieve of Eratosthenes.

Working Python code to demonstrate the recurrence:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

A quick example:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

The trouble is, I'm now in way over my head, both mathematically and as a computer scientist. Specifically, I am not competent with Fourier analysis, with defining uniform covers, or with the complex plane in general, and I'm worried that this approach is either flat-out wrong or hides a lurking horror of a 3SAT problem that elevates it to NP-completeness.

Thus, I have three questions here:

  Given my terse recurrence above, is it possible to deterministically compute or estimate the location of the zeroes in polynomial time and space?
  If so or if not, is it hiding any other subproblems that would make a polytime or polyspace solution intractable?
  And if by some miracle (1) and (2) hold up, what dynamic programming improvements would you make in satisfying this recurrence, from a high level? Clearly, iteration over the same integers through multiple functions is inelegant and quite wasteful.


texts:
I want to map the various combinations to an unique index:
 For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$:

Ex: For n = 6, r = 3
[012,
013,
014,
015,
...,
345]
So, for any given arrangement [012] the index would 0 as its the very first element.
Similarly, the index for arrangement for [015] should be 3. Trying to come up a formula to determine the correct index for a given arrangement.


texts: Computing a Sequence of People Entering and Leaving a Room

texts:
I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows.

  You start with an empty room and a group of n people waiting outside. At each step, you may either admit one person into the room, or let one out. Please design an algorithm which generates a sequence of $2^n − 1$ steps, so that every possible combination of people is achieved exactly once. For example, for $n = 3$, one possible sequence would be

  $\qquad\displaystyle e_1, e_2, x_1, e_3, e_1, x_2, x_1$.

  where $e_i$ means person $i$ enters the room and $x_j$ means person $j$ exits
  the room

  Hint: study the Hanoi Tower algorithm.

In my research on the prompt, I've found many people referencing Gray Code, but I don't understand how to implement it in an algorithm to compute this combination. I also found a very similar problem, but there wasn't an actual implementation of it.

It would be greatly appreciated if you could point me in the right direction on where to go with this algorithm.


texts:
I have a DAG of tasks designed as:

DAG {
  Dictionary<NodeAddresses,Node>
}
Node {
  List<Node> Parents;
  List<Node> Children;
  Task T;
}

This DAG is assumed to never change over time.

Now, I want to create an algorithm that, when given a NodeAddress, will execute the corresponding task, and all subsequent tasks in the graph. But the catch is that while this is running, I also want to allow another thread to be able to add another NodeAddress to the algorithm, and the algorithm will execute all the tasks and subchildren tasks of that node. If some tasks are children of both nodes, they should not be executed twice.

Does anyone know of a good algorithm to do this? The graph may be fairly big, so I want to use a memory size that is O(n) (n being the number of nodes in the graph). and then the faster the better...

Example:

Task A --> Task B --,
                    +---> Task D
Task C -------------'

Scneario 1:

The caller asks: Execute('A'):

The algorithm executes A, then B, then D.

Scenario 2:

The caller asks: Execute('A'):

The algorithm executes A, then B, then while B is executing, the caller asks: Execute('C').

The algorithm executes C (while B is still executing), waits for both to finish, and then executes D.


texts: What is the name for the recursion scheme in which data flows top-down exclusively?

texts:
This is a question that is in a sense a follow-up of a question I asked earlier, and which was answered.

In that question, the answer to "in which recursion scheme does data only flow bottom up, and in no other way?" was "a catamorphism".

Here, I am looking for the name for (and hence: theory about) the reverse recursion scheme, the one where data flows top-down, and in no other way.

I don't think I am looking for "anamorphism" ... but perhaps there is an error in my thinking. If so, I'd love to hear how. The reason is that an anamorphism is also in a sense a reverse of a catamorphism, but in a different sense than I'm looking for: it's its reverse because rather than collapsing a compound datastructure, it builds one.

As an example of what I'm looking for (in Python), consider the following mechanism that annotates all nodes with their depth:

def annotate_with_depth(node, parent_value=-1):
    my_value = parent_value + 1
    children = [annotate_with_depth(child, my_value) for child in node.children]
    return Node(children, my_value)

The more generic case of this could be something along these lines:

def calculate_depth_from_parent(parent_value, node_):
    return parent_value + 1

def the_generic_thing(mechanism_of_calculation, node, parent_value):
    my_value = mechanism_of_calculation(parent_value, node)

    children = [the_generic_thing(mechanism_of_calculation, child, my_value) for child in node.children]
    return Node(children, my_value)

annotate_with_depth = lambda node: the_generic_thing(calculate_depth_from_parent, node, -1)

As a more interesting example, consider the following task: in a directory tree, annotate each directory (of which you know the name) with its full path.


texts:
Here's a simple question which made me confused.

Please tell me if my analysis of the problem and my conclusions are correct.

For an optimization problem $\sf Gap-A[a,b] \in L$ for $b>a$. I want to discuss what I can know about $\sf Gap-A[a/2,b/2]$.

$\sf(i)$ Is it correct to say that $\sf Gap-A[a/2,b/2]$ is not in $\sf NP-Hard$ and it is easy only because the realtion $\frac{a/2}{b/2}=\frac{a}{b}$ and we already know that it is easy to approximate $A$ with  factor of $a/b$?

$\sf (ii)$ Is it true that I can't say though that $\sf Gap-A[a/2,b/2]$ is in $\sf L$ since there is no intersection between the gaps? In order that gap $B$ would be in the exact class that gap $A$ is in, we have to have $A \subseteq B$?


texts: Does the product of two functions equal the product of their Big-O's?

texts:
let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$

is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?


texts: Given $g(n) = \omega(f(n))$, then $g(n) + f(n) = \Omega(g(n))$?

texts:
I have a proof but I don't know if the assumptions I did are correct.

I know that $g(n)$ dominates $f(n)$, since $g(n) = \omega(f(n))$ and I did the assumption that $g(n) + f(n) = g(n)$. So, by reflexivity, $g(n) = \Omega (g(n))$.

Is this correct?


texts: What is the relation between a web server and a local file serve in distributed systems?

texts: I am learning distributed systems ( although I am an Electrical engineer ) using the book distributed systems concepts and design. The author says that "A web server is often a client of a local file server that manages the files in which the web pages are stored." I cant understand in the first place what is the relation between a web server and a local file server. So please someone explain this statement using a simple example. Thank you very much.


texts: Capacity of a discrete memoryless channel

texts:
For an integer $I$, the input-output relationship of a discrete memoryless channel is given by:

$Y = X + Z$ (mod $I$, i.e. sum indicates a modular addition)

where $I ≥ 2$,
and

• $X$ is an integer chosen from the alphabet $A_x = \{1,\dots,2I\}$,

• $Z$ is noise which is a uniform Bernoulli random variable. This means that $A_z = \{0,1\}$, and

$$\Pr\{Z = 0\} = \Pr\{Z = 1\} = 0.5.$$

How can we calculate the capacity of this channel?


texts:
I want an algorithm to decide whether a theorem holds in propositional Intuitionistic logic ($IL$). We know $IL$ is $PSPACE$-complete, so we should be able to reduce $IL$ to $QBF$.

In Literature i only found reductions the other way around, so im assuming this is not  the way to go for writing an algorithm deciding $IL$. Am i right about this?

Another way would be to use the Gödel-McKinsey translation into $S4$ and using a $CTL^*$ solver, but im trying to keep it simple.

My question is, is there an easy (not necessarily fast) way to decide $IL$? Can the reduction to $QBF$ still work?


texts: 3-SAT reduction to jobs scheduling problem (np-completeness)

texts:
In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also np-complete. An instance of 3-SAT is given as below:

and this is the instance of the scheduling problem defined as: Single Execution Time Scheduling Problem with a variable number of processors.

I can not totally understand the mapping between the two problems. Any hints that could help me getting the idea?


texts: If P = NP, why does P = NP = NP-Complete?

texts:
If P = NP, why does P = NP also then equal NP-Complete?

I.e. Why would it then be the case that P = NP = NP-Complete?

Assuming P != NP , there were problems in NP not in NP - Complete. When P = NP, all NP problems are actually now P.

Shouldn't there still be P = NP problems not in NP - Complete?


texts: Using the proof for NP-hardness for another problem

texts:
I already asked similar question here. However, now I restate the question. Let say that $P$ is an NP-hard optimization problem and $Q$ is a problem with unknown complexity. Additionally, we have an algorithm for solving problem $Q$. We can solve problem $P$ with input $x$ in the following manner:

    max = -inf - the optimal value for P
    n = size of x
    for (i = 1; i <= n; i++)
         val = solveQ(x, i)
         if (val > max) max = val

This is an oracle reduction, and therefore it does not follow that $Q$ is NP-hard, but that $P$ is Turing reducible to $Q$.

I found the proof that $P$ is at least weakly NP-hard. The proof uses many-one reduction from the
weakly NP-complete problem $R$. For each instance $y$ of $R$ there exist polynomial-time algorithm which transforms it to instance $x$ of $P$. Instance of $R$ is positive iff $P$ instance obtained using the transformation has a solution with =1.

Incidentally, I noticed that instance $x$ is always
an instance of $Q$ with $i = 2$. To clarify, algorithm transforms any $R$ instance $y$ to $P$ instance $x$, which corresponds to $Q$ instance $z = (x, 2)$.

At this point, can we claim that $Q$ is at least weakly NP-hard?


texts: The set of valid sentences in FO is not decidable as a consequence of rec. inseparability

texts:
Two given languages $L_1$ and $L_2$ are called recursively separable iff there exists a recursive languge $R$ such that $L_1 \subseteq R$ and $L_2 \cap R = \emptyset$.

Now consider first order logic, and some finite axiomatisation of $\mathbb N$ in it (surely this is way to weak, as we have no induction). Then we have three sets, 1) the set of valid sentences, i.e. the ones derivable the the rules of first order logic, 2) the set of provable sentences using the axioms of $\mathbb N$, and the set of truth sentences, i.e. the ones fullfilled by $\mathbb N$. Also as a superset of all these, we have the set of first order sentences that have some model, and contrary to that the set of sentences that are unsatisfiable, i.e. have no model, which equals (by Completeness of first order logic) the set of inconsistent sentences.

Now, the following holds:

Theorem: The set of unsatisfiable sentences and the set of sentences provable from the choosen axioms of $\mathbb N$ are not recursively separable.

From this it follows that the set of provable sentences from the axioms itself, as well as the set truth sentences, as well as the set of satisfiable sentences, are all not recursive/decidable.

But does this implies that the set of valid sentences is not decidable? This is states in the classic text Computational Complexiy by Cristos H. Papadimitriou, on page 133. But as this set is a proper subset of the provable sentences, I do not see that this is implied by the above Theorem? Or am I missing anything?


texts: proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

texts:
I came across this problem which asks to prove:
$$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$

for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible...

As an attempt, isn't the proof for this problem almost exactly the same as the proof for

$$
DSPACE(S(n)) \subseteq DTIME(c^{S(n)})
$$

The proof for $DSPACE(S(n)) \subseteq DTIME(c^{S(n)})$ says that given $S(n)$ space, one can come up with a finite number of $TM$ configurations that can be expressed as $c^{S(n)}$, for some constant $c$. Since $c^{S(n)} \in o(n)$, we can use a 'clock' to count up to $c^{S(n)}$ to make the $TM$ a decider ....

But I seem to see that the same logic also holds for $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$ ... since whether it is deterministic space or non-deterministic space, the number of configurations within space $S(n)$ remains finite and can be counted up to $c^{S(n)}$ .... am I correct or am I missing something ?


texts: maximum matching in a bipartite graph for solving a chess rook maximization problem

texts: There's an n x n chessboard where some cells are instead holes. I want to have as many rooks as possible in a way that the rooks won't be able to capture each other. Rooks cannot be placed on the holes but can jump over them. How can I solve this problem using the finding maximum matching principle in a bipartite graph?


texts: Surprisingly high collision rates when hashing a short list with few buckets

texts:
I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- it's been a long time since I did this stuff). And the output from the hashing function is an int modulo 4000.

Her naive hash function gets about 1500 collisions. To get something for comparison, I found a handful of hashing functions here and here. I ended up trying almost all of them (oat, fnv, djb, another djb, sax, elf, jsw, and a crc adaptation), because every single one of them got about 1500 collisions. That sure seems like a lot. I'm starting to think maybe we're missing something fundamental. Or not. I don't know.

(I was able to reduce collisions significantly by increasing the number of output buckets to 200k, and returning hash mod 200k from the functions. Naturally, this isn't allowed for the assignment.)

I'm not sure what questions to ask, but the first one that comes to mind is, does 1500 collisions sound about right when using such a small number of output buckets? Or does it sound more like we're doing something totally wrong outside the hashing function? (Presumably not inside it, given that we tried so many different ones.) Or maybe I should ask, is there a way to find out whether 1500 collisions is about right?


texts:
Fix an optimal solution G∗ to k-Cycle-Free Subgraph. Partition the vertex set V of G randomly into two subsets, A and B, each of size n/2, and remove edges internal to A or B. In expectation, the fraction of edges in G∗ that remain after this process is 1/2. With probability at least 2/3 the fraction of edges in G∗ that remain is at least 1/4; here we apply the Markov inequality on the fraction of edges inside A and B.

I know Markov inequality in context of probability theory I don't know what it means here.

APPROXIMATING SUBGRAPHS WITHOUT SHORT CYCLES


texts: Why is converting a suffix tree to a suffix array not O(nklogk) time

texts:
Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia:

A suffix tree can be built in $O(n)$ and can be converted into a suffix array by traversing the tree depth-first also in $O(n)$, so there exist algorithms that can build a suffix array in $O(n)$.

but in order to do this, the suffix tree must be traversed in lexicographical order. It is my understanding, that in order to do this, at each depth you must sort the outgoing edges and pick whichever is lexicographically the smallest, which would mean ultimately you end up sorting the entire alphabet (denoted as $k$) of whatever string you constructed the tree from, so hence $O(nk\log k)$ (assuming a well picked sorting algorithm).
I don't see how you could construct the suffix array in $O(n)$ time, even if when creating the suffix tree you sorted the edges, it would then take $O(nk\log k)$ time to make the suffix tree.
Any clarity or help on this would be much appreciated!


texts: When are range-based for loops better than regular for loops?

texts:
Is it when you need faster performance, to iterate over a container, or when you don't need an index variable?

From my understanding it should be when you need to iterate over a container.

Am I understanding this properly?


texts:
Let $P$ be a regular language and $Q$ be a context-free language such
  that $Q \subseteq P$(For example, let $P =  a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always regular?

  $P \cap Q$
  $P - Q$
  $\Sigma^* - Q$
  $\Sigma^* - P$

Option 1
$P \cap Q = Q$ as $P \subseteq Q$. Thus $P \cap Q$ is context-free.

Option 2
I was not able to generally reason here. I used the example mentioned in the question.
Let  $P =  a^*b^* $ and $Q = \{ a^nb^n | n \ge 0\}$.
$P - Q = \{a^nb^m | n \neq m\}$ which is not regular but only context-free.

Option - 3
Let $\Sigma = \{ a, b\}$ and $Q = \{ a^nb^n | n \ge 0\}$.
Again $\Sigma^* - Q =  \{a^nb^m | n \neq m\} $ which is not regular but only  context-free.

Thus, the 4th option must be right, $\Sigma^* - P$ is regular. I am however unable to understand this result intuitively. Could somebody explain?


texts: Arbitrary fault abstraction in 'Reliable and Secure Distributed Programming'

texts:
In the book by Cachin, Guerraoui, Rodrigues they discuss an arbitrary fault abstraction. It seems to me that this abstraction does not include crashes in its behavior. I think this because they propose an algorithm as follows:

Send all messages infinite times.
Keep a list of received messages in volatile memory, and only pass non-duplicates to the application level.
Use message authentication codes for verification.

This means all sent messages are delivered exactly once within the system (given a non-zero chance of transmission between nodes). However this fails on a crash as volatile memory will be lost and duplicate messages will be passed to the application.

Is this correct?

Sorry for the book specific question.

Thank you.


texts: Why do we still use a Von Neumann Architecture in modern computers?

texts:
The Von Neumann architecture was first created in the mid 40s for use in a computing system known as ENIAC for research into the feasibility of thermonuclear weapons.

To this day the Von Neumann architeture is still primary foundation in the majority of modern computers. I have listened to a few historians and scientists mention that there is likely more efficient architectures and that Von Neumann himself didn't believe in its universal capability(unfortunately cannot remember enough to find a link).

So why do we still use this architecture in the majority of modern computing?


texts: calculating the string similarity of an optimal alignment

texts:
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the substring of s2, that has the biggest similarity to s1. The following alignments are possible:
[s2[:i] for i in range(len_s1)] + [s2[i:i+len_s1] for i in range(len_s2))]

e.g. for s1="ab" and s2="abcde" the following alignments should be considered:
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

The similarity between s1 and the substring s2_substr of s2 is defined in terms of a normalized version of the InDel Distance. The InDel-Distance is a variation of the Levenshtein distance, that only allows the use of insertions and deletions (this can be e.g. achieved using a weight of 2 for substitutions). The distance is normalized in the following way: $1 - dist / (len\_s1 + len\_s2\_substr)$. I am using a bitparallel algorithm to calculate the InDel-Distance in $O([len_s1/w]len_s2)$ with the computer wordsize w (64 bit or higher when using SIMD). The algorithm is described in the paper New Bit-Parallel Indel-Distance Algorithm by Heikki Hyyrö.
Example
Here is a small example that shows how this algorithm works:
For this example I am using the same example string shown above (s1="ab" and s2="abcde").
As shown above this generates the possible substrings of s2:
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

These substrings have the following similarities to s1

s1
len_s1
s2_substr
len_s2_substr
distance
similarity

'ab'
2
''
0
2 DEL -> 2
1 - 2 / (2+0) = 0

'ab'
2
'a'
1
1 DEL -> 1
1 - 1 / (2+1) = 0.66

'ab'
2
'ab'
2
0
1 - 0 / (2+2) = 1

'ab'
2
'bc'
2
1 INS, 1 DEL -> 2
1 - 2 / (2+2) = 0.5

'ab'
2
'cd'
2
2 INS, 2 DEL -> 4
1 - 4 / (2+2) = 0

'ab'
2
'de'
2
2 INS, 2 DEL -> 4
1 - 4 / (2+2) = 0

'ab'
2
'e'
1
1 INS, 2 DEL -> 3
1 - 3 / (2+1) = 0

In this case the alignment 'ab' <-> 'ab' has the biggest similarity, so the function should return a similarity of 1.
Naive solution
A naive sliding window approach could calculate the distance in the following way:
max_similarity = 0
for s2_substr in variations:
    substr_similarity = similarity(s1, s2_substr)
    max_similarity = max(max_similarity, substr_similarity)

However this would have to test len_s1 + len_s2 possible alignments, so
it has a complexity of O([len_s1+len_s2]*[len_s1/w]*len_s2. This becomes very slow for longer strings.
Different implementations of this algorithm
A relatively similar implementation is included e.g. in the Python library FuzzyWuzzy, which searches for the longest common substrings of s1 in s2. The starting points of those substrings are then used to calculate the best alignment. However it is not guaranteed, that the optimal alignment starts with one of the longest common substrings and therefore calculates a wrong similarity in many cases.
Question
Is there a faster algorithm to calculate this kind of similarity?
The algorithm has the following requirements:

defines similarity in Terms of the normalized InDel-Distance
allows Gaps at start and end of s2
when s2_substr is not placed at the start or end of s2 it requires the length len_s1

As suggested by D.W. the smallest distance with gaps at start and end can be found by making insertions to the smaller string free in the start (init first row of the distance matrix with 0 instead of insertion costs). The smallest value in the result row is the distance for the smallest alignment. However this approach has a couple of problems:

it does not guarantee, that the length of the substring s2_substr is len_s1 for substrings that do not start at the start or end of s2. (Maybe this could be guaranteed with a modification, that I am just not aware of)
it searches for the alignment with the smallest InDel Distance. However I am trying to optimize the normalized InDel Distance as described above. Since the normalization depends on the length of the substring s2_substr, which is not constant (at start/end of the string it can be smaller than len_s1), this does not always give the correct results.


texts: How equality of item (production state) is defined in LR parser?

texts:
Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):

Expr -> Expr '+' . Term
Term -> '+' . Term
Term -> . Factor

Usually it is all about SLR(0) equality so in short, two items are equal if they have all the same symbols and they are in the same state (the dot is in the same place). I didn't see anything else than such notion/definition.

My new approach is somewhat different -- let's add user actions:

Expr -> Expr '+' . Term @user_func1
Term -> '+' . Term @user_func2
Term -> . Factor  @user_func3

I would say that two items are equal, if:

LHS symbol is the same
and the number of seen symbols is the same (*)
and the unseen symbols are the same
and the user action is exactly the same

For example -- such items would be the same:

elem -> ASTERISK . ID @func1;
elem -> ID . ID @func1;

This change of equality idea gave me 10% gain on table sizes, and now I wonder if I miss something:

maybe there is even "better" definition of equality (like dropping (*) condition)
or -- my definition is wrong

?


texts:
Who were the first researchers to prove the Complementary Slackness condition for linear programming?

I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't find anywhere the reference for complementary slackness...


texts: Pumping lemma -- Is this enough to prove that the language L is not regular?

texts:
I have a language $L$:

$$L = \{w :  a^ib^j; i > j \}$$

I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly:

$L$ Is assumed to be regular. A regular language means that a DFA exists that can produce all the strings in $L$. So I need to find a string that exists in L but cannot be represented by a DFA.

So I need to prove that L is not regular by finding a counter example,

I need to find a suitable $w$, where $|w| \geq p$ (the pumping length). I choose:

$$w = a^{(p + 1)}b^p$$

This string can be broken up into $3$ substrings ($x, y$ and $z$), where $|y| > 0$.

$k = 2$:

$$xy^2z = a^{(p + 1)}b^{(p + |y|)}$$

Since $p + 1$ is not greater than $p + |y|$, then $L$ is not a regular language.

Would this be enough to prove that the language is not regular? Here, I assumed that $|y|$ could be $1$, since the number of $a$'s is a minimum of $1$.


texts: Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time?

texts:
Given the grammar of the Python language, is there a concise way to specify the space of all possible (and correct) Python programs?

To avoid the underlying halting problem, the specification would include a user-definable maximum program size and running time. This concise specification could then be fed to another program, a search/optimization algorithm to be precise, as the domain to operate in. And yes, I'm aware of how intractable such a space would be.

I don't know much about computer science or language theory, so any help would be appreciated.


texts:
(weak) Church-Turing thesis states every physically realizable computation device can be simulated by a Turing machine (not necessarily efficiently).
(1) Then Does any model that is not physically realizable and cannot be simulated by Turing machine?
(2) Is there any evidence for this thesis?


texts: Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

texts:
I have recently been working on an applied project where I have to solve optimization problems.

I have found that it is much easier to solve an integer linear program (ILP) as opposed to a mixed-integer linear programs (MILP), in the sense it is faster for me to find feasible solutions as well as to prove optimality.

I am wondering if there is some kind of formal result that confirms this (i.e. on the time complexity of ILP vs. MILP).

To be clear, when I am refering to an ILP I mean an optimization problem of the form

$$\begin{align} \min_{x} \quad & c^Tx \\ \text{s.t.} \quad & Ax = b \\ \; & x\in\mathbb{Z}^N\end{align}$$

where the variables are integer-valued so that $x\in\mathbb{Z}^N$ but the parameters are real valued so that $c \in \mathbb{R}^N$, $A \in \mathbb{R}^{M \times N}$, $b \in \mathbb{R}^M$. In turn, an MILP would be different in that at least one of the variables would take on a real value.


texts: If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that they are equal to their deterministic counterparts.


texts:
It is given in the book by El Gamal that

The capacity region of the DM-BC depends on the channel conditional
pmf $p(y_1 , y _2 |x)$ only through the conditional marginal pmfs $p(y_1 |x)$ and $p(y_ 2 |x)$

The statement made is about the entire capacity region. Every point in the capacity region means that there exists a sequence of $(2^{nR_1},2^{nR_2},n)$ (considering only private messages) codes with 0 error. I am wondering about the converse.
For a given sequence of codes, would broadcast channels with identical marginals have the same achievability, ie, if it is achievable in the first channel, would it be achievable in the second channel and vice versa?


texts: Prove that $\text{EF p}$ can't be written in LTL

texts: Why can't we somehow represent it's negation in LTL and go from there? I think maybe because it has (effectively) two existential quantifiers, so negating it does not work. But how do I prove it?


texts: How to ensure that no manipulation to data records has been made

texts:
Let's say I have a transaction history, like this:

Transaction #1: Add 5
Transaction #2: Add 8
Transaction #3: Remove 2
Transaction #4: Cancel Transaction #2

Is there a way to guarantee that no transaction will ever be removed, or at least I will notice a missing transaction?

Basically I want to enforce to make a transaction to reverse an other transaction, instead of just deleting it.

Would saving a hash of the previous transaction help here?


texts: What is the point-free version of f(x,y)?

texts:
What is the point-free version of

f(x, y)

? Is it just f or some kind of function composition, since when curried there is an implicit function which is made out of applying f to x?


texts: How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine

texts: I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An example would be nice. Actually, a worked out example that shows how to go from TM that has $k$ tapes to one that has 1 tape is what I'm really looking for. I have been unable to find one so far. I'm also not looking for any proofs.


texts: Measure two qubits, one from entangled pair, in Bell basis?

texts:
In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta_{00}\rangle$ Bell state. Then, if Alice wants to teleport a quibt $|v\rangle$ to Bob, she needs to measure $|v\rangle$ and her qubit from an entangled pair in the Bell basis. Such measurment requires her to perform a CNOT on the two qubits with $|v\rangle$ being the control qubit and then apply Hadamard transformation to $|v\rangle$.

I can't understand how can she perform the above. If we represent quantum gates as matrices, what vector would represent the input to the CNOT matrix (the pair $|v\rangle$ and Alice's qubit from an entangled pair?) In other words, how can we represent a pair that Alice wants to apply CNOT to (when performing measurement in the Bell Basis?)

I know that Bell measurement does not require CNOT in general, but this is one of the ways it could be implemented (assuming we just want to get the classical 2-bit value).

My intuition is that because we need to operate on a tensor product of $|v\rangle$ and the entangled pair, we need to create a matrix representing an operation performing CNOT on $v\rangle$ and first qubit from the pair, and I on the second qubit from the pair, so it would be like $CNOT \otimes I$. Is this correct?


texts: What other involutions are there besides xor?

texts:
There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number.

The key properties used here are the involution of xor (i.e. a number's inverse is the same number) and the closure over integer range of the variable.

Now, are there any other operations that could be used for this? I could only find 1/x which, unfortunately, cannot be used due to precision erros.


texts:
The following exercise is difficult for me:

  Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$.

  Hint: A $k$-clique denotes $k$ verteces within a graph that are all connected with each other.

  Annotation: if the question also considers $k$ as parameter, then the problem is $\text{NP}$-complete.

So $\text{L}$ is "the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space". Now I'm wondering if this exercise isn't a catchy question, since I've found this paper and it says "We give an algorithm for $k$-clique that runs in (...) $O(n^{\varepsilon})$ space, for all $\varepsilon > 0$, on graphs with $n$ nodes"?

Furthermore, I also don't understand the annotation, because how should it be possible to not consider $k$ for the $k$-clique problem?


texts: Complexity of deciding if a formula has exactly 1 satisfying assignment

texts:
The decision problem

  Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment?

can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything more known about its complexity?


texts: Algorithm for finding the best “route” of tasks

texts:
I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x coordinates per second. Every task has:

A coordinate where it can be completed (for example (40/50))
A importance value ranging from  0  to X (for example importance = 5)
A time that is needed to complete this task

Also, some tasks can only be done if a certain other task has already been completed.
Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.

I tried to bruteforce it, but that didn't work out. There are around 11 tasks usually and 4-6 can be done, resulting in up to a million and something possiblities. Also, I had a solution without calculating the time needed to travel between the points which was basically calculating a importance per time value and just doing the tasks based on this value... which won't work for the full problem.


texts: If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

texts: I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?


texts: Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$

texts:
I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a CFL.

Now, in the book they do it in a way that I understand but I think it can be simplified, so here goes:

Assume by contradiction that $L\in CFL$ with pumping constant $p$ and let   $\omega = a^p b^p c^p$. Clearly $\omega \in L$ and $\| \omega \| \ge p$. Let $\omega = uvxyz$ a division such that

$\| vy \| > 0$
$\| vxy \| \le p$

Condition 1 stipulates that for every $i \neq 1$ pumping will actually change the substring $vxy$.
Condition 2 stipulates that the substring $vxy$ is comprised of at most two type of alphabet symbols. For now we assume that these symbols are $a$ and $b$.

Combine these two facts and we see that for every $i \neq 1$ the string $uv^i xy^i z$ has a different number of $a$'s and $b$'s than $c$'s.

Again, the proof in the book is a bit more complexed, which leads me to think that I might have a mistake here.

Any thoughts? thanks!


texts: Why contraction and weakening rules are the upside down?

texts:
On the A taste of linear logic paper, the author claims that:

  A rule consists of zero or more judgements written above a line, and one
  judgement written below. If all the judgements above the line are derivable, then the judgement below is derivable also.

He then proceeds to show the following rules:

He then describes those rules as:

  Contraction expresses that any hypothesis may be duplicated, and Weakening expresses that any hypothesis may be discarded.

That looks upside down. Reading the "Contraction" rule in English, we have that "if assumptions Γ, A, A imply B, then assumptions Γ, A also imply B" - notice that we discarded an assumption instead of duplicating it. Similarly, the "Weakening" rule adds an assumption to the conclusion, rather than discarding one from the premises as the author seems to suggest. Why?


texts: algorithm to find shortest path connecting EVERY node

texts:
I have received a problem to solve and I am not sure what algorithm to use.
TLDR; Find the shortest path to get to every node in a undirected graph

The problem states that one must visit every station in the shanghai metro in the shortest path possible. Interchange Stations ('edges') can be reused and you can start / stop anywhere.
I have created a lookup table that shows connected stations as well as the distance to travel (not shown)
"Xinzhuang": [
  "Waihuan Rd." : 1
],
"Waihuan Rd.": [
  "Xinzhuang": 2.2,
  "Lianhua Rd.": 3
],
"Lianhua Rd.": [
  "Waihuan Rd.": 4,
  "Jinjiang Park": 5,
],
"Jinjiang Park": [
  "Lianhua Rd.": 9.1,
  "South Railway Station": 10.3
],
"South Railway Station": [
  "Jinjiang Park": 4.1,
  "Caobao Rd.": 1.1,
  "Shilong Rd.": 2.5
],
...

I found this leetcode problem but it did not mention any specific algorithm and since it was O(2^N * N) I wondered if there was a faster method than BFS.
https://leetcode.com/problems/shortest-path-visiting-all-nodes/solution/
Since my graph is so big, I was going to reduce the lines with a single path to a single node.
What algorithm can I use that will work in Polynomial time, OR has the least time complexity?


texts: comparison in speed between the processor and the hard disk

texts:
I'm reading through William Stalling's operating system intrnals and design principles book. Talking about interrupts, it gives the following examples when comparing the speed of a processor and a hard disk:

  To give a specific example, consider a PC that operates at 1 GHz, which would
  allow roughly 10^9 instructions per second. A typical hard disk has a rotational speed
  of 7200 revolutions per minute for a half-track rotation time of 4 ms, which is 4 million
  times slower than the processor.

My question is how was the result calculated? How did we know that the hard disk is 4 million times slower?


texts: Converting along regular expression to NFA

texts:
I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):

(0+1+ϵ)4+(11100+ϵ)r(0011100r)*(00111+ϵ)

r=11+(110+ϵ)s(0110s)*(011+ϵ)

s=(0+10)*(1+ϵ)

How should I convert this into an NFA? Please explain the steps behind it as well!


texts: P/NP - Proof that SAT-TM is NP-complete uses certificate

texts:
To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard
$$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$
my professor used the following proof.

Suppose $L$ in NP and $V$ is a verifier for $L$ running in polynomial time of power k.
$$L \leq _P \text{SAT-TM} $$
Polynomial reduction function content:

Build a TM $V_w$ that takes a certificate $c$ as input and executes $V$ on $\langle w,c\rangle $.
Function output: $\langle  V_w,q,1^{|w|}\rangle $

Then:

If $w\in L$, then $V_w$ accepts $c$.
Else $w\notin L \rightarrow$ No certificate makes $V_w$ accept, so $\langle  V_w,q,1^{|w|}\rangle \notin \text{SAT-TM}$. □

Say we have $L_1 \leq _P L_2 $, my understanding is that the function receives an input of $L_1$ and transforms it so that the existing solution of $L_2$ outputs the same as a solution for $L_1$ would. We have no information about a potential solution and we're extracting it from $L_2$'s output.
But about the certificate, where does he get it and how can it be known inside the polynomial reduction function? Shouldn't the input only be the word $w$?


texts: An algorithm for k-way array partitioning

texts:
I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all have values in the range of $[s_i, s_{i + 1})$ (let $s_0 = -\inf, s_n = \inf$).

My question is: how to implement this efficiently, preferably in place?

I can't even figure out how to do it out of place, other than allocating $n$ dynamic sized arrays and finally concatenating them together. In the case of single splitter, we can successively push the values smaller and larger than the splitter to the two ends respectively, but for more splitters, I don't know how to do it efficiently.


texts: Unrecognizable languages relationship to NP-hard languages

texts:
I would like to know if there exists an NP-hard language which is also a member of co-RE\R?
I think it depends if P=NP or not, but i'm not sure.

Can I simply assume NP-hard is in R?

Can you direct me how to think about it?


texts: Why do I need a base case for n=3 when solving a d&c recurrence?

texts:
I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example:

$T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$  where
$T(1) = 1$

They assume that $T(n) = O(n \log n)$ and go on to prove it by using induction.

I understand the inductive step, but I do not understand how they find the base case.

For $n=1$ we have $T(1) \leq c1 \log 1 = 0$, which is wrong because $T(1) = 1$. So we can not use $T(1)$ as a base case.

For $n=2$ we have $T(2) = 2T(1) + 2 = 4$, so $4 \leq c2 \log2$. The last inequality holds for every $c \geq 2$.

In the book they write that we also need $n=3$ to be the base case. However, they do not really explain why. Why isn't $n=2$ sufficient?


texts: Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

texts:
I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons.

There are some instructions on this page (see the heading entitled "Decompose into Simple Pieces") however my current implementation is falling short (see img below).

While I'm able to find all the self-intersecting points I'm not able to construct the desired outputs when there are multiple self-intersections on a single segment.

Here is what I'd expect to get

I'm struggling to find any other papers which describe the process or required data structures in any more detail. The blog post references a linked list which could mean a Doubly Connected Edge List although I'm not 100% sure, the other challenge with that is that I don't think there is a suitable js implementation of that data structure.

Any advice on how I might reconstruct the desired output would be appreciated


texts: Finding most/least frequent elements with one loop

texts:
This question could be trivial but I have tried to come up with an algorithm to list the most and least frequent elements in an array of int with just one loop, i.e O(n).

[1,2,1,1,3,3]:

Most frequent: [1,1,1]
Least frequent: [2]

I'm aware that it's possible to do that with two loops. One to aggregate the count of each element and next to find the most / least frequent ones but I was wondering if I could do both in one loop.


texts:
Suppose we define a CFG such that it is possible to produce strings of the form $a^nb^n$ (in this case, I would think, we would need epsilon-productions).
Then one such $L(CFG)$ is $a^nb^n$.

However, let's say it is also possible to produce strings not of the form $a^nb^n$ from this grammar.

Can we still call $a^nb^n$ a language generated by the grammar, even if it is not the only/unique language accepted by the grammar?

In other words, is the language accepted by a CFG the set of all strings that can be derived from the grammar? Or can it also be a proper subset of these strings, fulfilling some desired criterion?


texts: How to learn computer science the right way

texts:
I looked through the sites and this seems to be the best place to ask this question. I am sure it has been asked 10000 times but I am looking for a tailored answer to me and my situation. I currently work as a project manager for a startup. I have a working knowledge into many different fields ranging from HTML, CSS, PHP, JS, MySQL, Server Administration, Marketing, SEO, Etc. I have been working in the web development industry for the last 10 years, I started when I was 11. I have associates level education but no BCS. I don't have the time right now to pursue that as much as I would love to in my current situation(newborn son) and my wife is pursuing her eduction currently. I knew all these language but I don't really know them. I wanna truly understand them, why they work the way they do and how I can master them. This is more of a personal desire then one driven by money, as they most likely wont affect my career. I really would like to learn a new language.

I have about 3-5 hours every week night while I have my son and my wife is in school to study at home. I can't really afford college or guarantee that I will have that time available to make that commitment so I would like to have a no pressure solution. I have completed a lot of treehouse and didn't find much of a challenge.  The courses really didnt drive into the languages either and teach me anything new.

I am looking to start learning things like computer logic, but I need some pointers of where to start and what terms to search to find this education info. After I truly understand the inner workings of a computer from the microprocessor to ram to harddrive to interpreter to etc, I would like to learn a new programming language. My current PHP skills arent great, and its more of a working knowledge then understand so treat me as a new programmer.

To sum things up

Can I have some recommendations of key concepts to learn for new software engineers
If anyone can provide good education sources, please do so
I would like some recommendations of languages to learn that are in demand and are new, and arent going anywhere anytime soon. From my current research it looks like Java or C# are my best options. Anything I should know about those, any assume the previous questions apply to them.
I am willing to pay for this


texts:
I'm doing this challenge on Hacker Rank that wants me to implement a linked list.

It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. Therefore the last instance added would have head=None (I'm using Python).

This is the pic they provide -

Wouldn't it make more sense to create a node instance with its head linked to the previous node? That way the only node with head=None would be the first node created.

I've seen conflicting suggestions so far. I'm not a CS student or developer.

EDIT -

This example from Youtube (1.36) suggests the second method.

EDIT -

Sorry if this seemed like a programming question. I'm trying to see if there's a logical way to set up linked lists for my own benefit... solving the HackerRank challenge is not the issue.


texts: What can be said about the Fourier expansion of compositions of Boolean functions, if anything?

texts:
Let $\chi_S: \mathbb{F}_2^n \to \{\pm 1\}, x \mapsto (-1)^{\sum_{i \in S}x_i}$ for every $S \subseteq [n]$ denote the parity functions from $\mathbb{F}_2^n$ to $\{\pm 1\}$. Then, of course, every $f: \mathbb{F}_2^n \to \{\pm 1\}$ can be written as a linear combination (over $\mathbb{R}$) of the parity functions. I have tried (without much ease or success), to produce the Fourier expansions of compositions of even simple Boolean functions, in particular of conjunctions of parity functions, like $\chi_S \wedge \chi_T$ (where under the encoding of $1_{\mathbb{F}_2^n} \mapsto -1,0_{\mathbb{F}_2^n} \mapsto +1$, $\wedge$ is just $\max_2$).
So, my questions are:

Are there good techniques/tools in general for computing/estimating the Fourier expansion of $f \circ g$ when we know both of the expansions for both $f,g$?
Is there something we can say about the particular case of conjunctions/disjunctions over parity functions?


texts: Finding the similarity between large text files

texts:
My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.

Let's say I have two large text files (original file A and new file B). Each file is English prose text (including dialogue) with a typical size 256K to 500K characters.

I want to compare them to find out how similar the contents of B are to A.

Similar in this case means: all, or a significant part, of B exists in A, with the condition that there may be subtle differences, words changed here and there, or even globally.

In all cases we have to remember that this is looking for similarity, not (necessarily) identity.

Preprocessing for the text:

Remove all punctuation (and close up gaps "didn't" -> "didnt");
Lowercase everything;
Remove common words;
Reduce all whitespace to single space only, but keep paragraphs;

Other possible optimisations to reduce future workload:

Ignore any paragraph of less than a certain length. Why? Because there's a higher probability of natural duplication in shorter paragraphs (though arguably not in the same overall position).

Have an arbitrary cut-off length on the paragraphs. Why? Mostly because it reduces workload.

Finally:

For every word, turn it into a Metaphone. So instead of every paragraph being composed of normal words it becomes a list a metaphones which help in comparing slightly modified words.

We end up with paragraphs that look like this (each of these lines is a separate paragraph):

WNT TR0 ABT E0L JRTN TTKTF INSPK WLMS E0L UTRL OBNKS JRL
TM RL SRPRS LKT TRKTL KM N SX WRT
LT ASK W0R RT WRKS T ST N WLTNT RT 0M AL

But I admit, when it comes to the comparison I'm not sure how to approach it, beyond a brute force take the first encoded paragraph from B (B[0]) and check every paragraph in A looking for a high match (maybe identical, maybe very similar). Perhaps we use Levenshtein to find a match percentage on the paragraphs.

If we find a match at A[n], then check B[1] against A[n+1] and maybe a couple further A[n+2] and A[n+3] just in case something was inserted.

And proceed that way.

What should be detected:

Near-identical text
Global proper noun changes
B is a subset of A

Thanks.


texts: How do we determine how much time a multi-tape DTM saves over a one-tape DTM?

texts:
Note: This is a part of a homework question

Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}

Then it says "Discuss how much time your machines saves over a one-tape DTM using the same algorithm"
Any hint?

Here's my algorithm:

(1) Cut-and-paste c's to tape 3

(2) Cut-and-paste b's to tape 2

(3) Cross out each triplets, accept if last round cuts all three, reject if there's leftover

Which seems like it has a time complexity of $O(n+n+3n)=O(5n)$
Then how do we determine the time complexity for the one-tape version?


texts: Meaning of the "why not" modality from linear type theory?

texts:
In linear type theory there is a modality written ! where !T can be read as "infinite copies of T".

According to ncatlab, there is a dual to this modality which is sometimes written ?T and referred to as the "why not" modality. What is the meaning of this modality? How does ?T behave as a type?


texts: Generate Regular Grammar for a Language with Modular Condition

texts:
This is a homework problem.  I've wrestled with it for quite awhile and can't come up with a valid solution.  The problem is:

Find a regular grammar that generates each of the following languages:
$$L = \{ w \in {a,b}^* \mid \text{na}(w) – \text{nb}(w) = 1 \mod 3 \} , $$

where $\text{na}(w)$ is the number of $a$s and $\text{nb}(w)$ the number of $b$'s occurring in $w$, respectively.

It seems as though a DFA can't accept this language since any difference of $a$'s and $b$'s resulting in 1 will be in the language, but that gives an infinite number of possibilities.

Any help pointing me in the right direction for this problem would be much appreciated.


texts: Dependent Type Theory Implementation of a Graph

texts:
In Haskell you find graphs defined like this:

data Graph a = GNode a (Graph a)

Or this:

data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

Or this:

type Graph = Table [Vertex]
type Table a = Array Vertex a
type Bounds = (Vertex, Vertex)
type Edge = (Vertex, Vertex)
type Vertex = Int

I am wondering why it is not implemented more like this (this is JavaScript):

class Graph {
  constructor() {
    this.nodes = []
    this.edges = []
  }
}

Or perhaps in Haskell-ish:

data Graph = Graph
  { nodes :: [Node]
  , edges :: [Edge]
  }

For example, in this Graph in Coq, it looks more like the JavaScript version (though I don't understand the Structure in Coq):

Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

Finally, here seems to be a complete Coq graph definition:

Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

My question is, what a proper definition of a graph is in Dependent Type Theory in formal type theory notation. Mathematically $G = (V, E)$, but in Coq and Haskell, things are a lot more functional/recursive. It seems weird that Haskell is defining it sometimes as a recursive structure. Wondering how to model this using the abstract type theory notation (using dependent types) and recursion if necessary, to get a better sense of realistic data structures in dependent type theory, and how to parse the formal notation. The types of graphs I am thinking about are directed, cyclic, and finite, non-hypergraphs.


texts: Multi-Interval Discretization of Continuous-Valued Attributes for Classification Learning

texts:
I'm trying to figure out Fayyad and Irani (1993) MDLP discretization of continuous variables (here is link to the original paper).
I understand how algorithm works, but I have some doubts about first step, sorting of variable and finding potential cut-points.
My doubt is what happens if we have multiple occurrence of same value of variable in the dateset and those occurrences have different target variable associated with them? This can happen quite often in practice, e.g. we have table of clients with some properties which is 0 for some large number of them and there are multiple different events associated with those clients, some of them belonging to one class and others belonging to different class.
Here is a dummy table with sorted Variable X and 2-class classification problem:

If we apply heuristic like it is suggested in the paper, value 0.6 will end up in multiple different potential bins since it contains both class 0 and 1. What's even worst, it seems that potential cutoffs and bins will be different if we sort target variable (ascending, descending or unsorted)...
Any help with this, someone maybe already tried to figure out this?


texts: Calculating physical address from Logical Address

texts:
I have been give a page table logical address of 0011 0110 1010 1010 and have been told that there are 512 entries into this page table in which the frame number is two times smaller that the page number.
I have looked at previous posts but I am still not understanding what steps I must do in order to translate this logical address into physical address.
I understand that the logical address is 16 bits long and that the frame number is twice as small as the page number, however I am unsure what to do with this information. Any help would be greatly appreciated.


texts: Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable?

texts:
This question was made during a class of Computer Theory in Rome, Italy.

Let $G$ be a regular grammar, $\Sigma$ its alphabet and $L(G)$ the language generated by $G$

  Given a regular grammar $G$, is $L(G) = \Sigma^*$ a decidable property?

My approach

I can design a Finite State Automaton that recognize the strings in the language $G$. Because regular languages are closed under the iteration operation, the FSA recognize also string in $\Sigma^*$ alphabet


texts: Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$

texts:
I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=\Omega(n^{\lg_b^{a+\epsilon}})$. However, I have tried to prove this statement, and was unable to do so.
The question is how to prove that the regularity condition of master theorem case 3 always holds on the two above-mentioned functions.


texts: Floyd–Warshall algorithm on undirected graph

texts:
I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm.

In case of undirected graphs should I change the assignment statement inside the if condition to

dist[i][j] = dist[j][i] = dist[i][k] + dist[k][j]

or they are equivalent?


texts: Finding a minimal containing rectangle from a given set of rectangles

texts:
The problem is as follows:

Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations:

Check, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns true iff there is a rectangle $c\in S$ so that $r_x \leq c_x$ and $r_y \leq c_y$.
Get, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns the minimal member of $S$ (that is, a member with a minimal area - $c_x c_y$) that contains $r$ (i.e., $r_x \leq c_x$ and $r_y \leq c_y$).
Insert, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and adds it to $S$.
Remove, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and removes it from $S$.

The four procedures have to be efficient, measuring efficiency by $m$ and $n$, where $m$ is the number of different widths in $S$ and $n$ is the number of different heights in $S$.

Space efficiency has to be no worse than $O(mn)$ (that is, linear to the number of elements in $S$).


texts: How to count near circular objects in image

texts:
I have a image similar to below. In that I need to find all red circles and count them.
So, I am thinking to use MATLAB R2011a with Image Processing Toolkit for it. How could I possibly extract them?


texts: What is the difference between dynamic programming and a mere caching?

texts: I mean why should we use such epic buzzword when you can say: "cache your results!".


texts: Real world applications of first order logic

texts: I study an AI course and we done some lectures about first order logic and the first thing that I was thinking is, what are the real world applications of first order logic and generally logical languages , especially in AI ?


texts: L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma

texts:
L ={ $a^{m^n}$ | $m$>$n$ }
I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR  L = $a^{\left(m^n\right)}$.

If it is considered as L = $(a^m)^{n}$ then want to check it is Regular or not by Pumping Lemma.
I tried by following way.

$m$ > $n$ so we can take $m's$ value as $n+1$.
So $L$  = $(a^{n+1})^{n}$

Let n be the Pumping Lemma Constant.
Then by pumping Lemma $u$$v^{i}$$w$ in $L$ for every $i$ $>=$ $0$.

$1<= |v| <= n$

$uv <= n$.

So here $u$ = $(a^{n+1})^{n-1}$

$v$ = $(a^{n+1})^{i}$  and

w = $\epsilon$

By taking $i = 2$ ,
I am getting string as $(a^{n+1})^{n+1}$Which is not possible. Because it means $m=n$.
So above string is not Regular.

But different solutions giving different answers. So confused whether it is Regular or not. And is there any problem in my solution ?


texts: Algorithm for finding the minimum index in array with value exceeding x

texts:
Given a set $S = \{s_1, \ldots, s_k\}$, find the minimum index $j$ such that $\sum_{i = 1}^j s_i \geq \frac{1}{2}\sum_{i = 1}^k s_i$.

I was reading in a paper about an algorithm for this problem that is described as follows:

  The idea is to construct an array of size $k$, whose $j$th position contains $\sum_{i = 1}^j s_i$. Then one can find the appropriate index $j$ in $O(\log(\min\{j, k - j\}))$ time by using a form of binary search simultaneously from both ends of the array.

Can someone explain how the binary search might work? I know that constructing the array still takes $O(k)$, but I want to use this in an algorithm where the array would be computed just once and used with recursive calls to this algorithm.


texts: Alternatives to multiplication/division/modulo for encoding choices?

texts:
The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % n, x = x / n.

Is this optimal if the only constraint is that the encoded result must be a bitstring? Would *+/% still be the choice if they were not available as instructions?

I know arithmetic coding (and ANS) exists, but it also can't avoid big integer arithmetic without giving up some entropy.


texts:
Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and 3, and an edge between 5 and 2. What is the length of the shortest path between 0 and 1?
My method to get the answer is to apply the definition of congruence. The edge exits iff $7 | x + 3 - y$. Thus, I got one cyclic graph and then get the answer is 2. Is there any method I can play with modular arithmetic without drawing a graph so that I can get shortest path between node 0 and node 1?


texts:
A company has some workers who need to perfrom some jobs. Each job requires workers of a combination of departments and seniority.
Departments : HR, Legal, Product, Development
Seniority : Junior, Mid Level, Senior
For example, a job might have the following minimum requirements.
Job1:

Total Workers - 8
Atleast 2 workers from Development
Atleast 2 workers from Product
Atleast 4 Senior workers
Atleast 1 Junior worker

If there are not sufficient workers available, we can hire outside contractors. Our objective is to allocate workers to jobs so as to minimize the number of contractors we have to hire.
What is a good algorithm to allocate workers to jobs optimally?


texts: Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are

texts:
I have an array of elements $A = [x_0, x_1, \ldots, x_n]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, how many there are aside from the given bounds. I have a function which can, in $O(1)$ time, check if something is 'bad' or 'good'. As $A$ is an array, I have the ability to access any element of $A$ in $O(1)$ time if I know the index.

My goal is to devise a procedure which, in $O(n)$ time and $O(1)$ space, returns the index of a randomly-selected 'bad' element in $A$, or $-1$ if no such element exists. Any 'bad' element should have an equal chance of being selected. My current approach was something like this, assuming coin is a procedure that returns 0 or 1 with equal probability:

function randombad(A):
    result := -1
    for (i from 0 to (length(A) -1))
        if (A[i] is bad and result = -1)
            result := i
        else if (A[i] is bad)
            flip = coin()
            if (coin = 1)
                result := i
    return result

However, if $k > 2$, this obviously gives later 'bad' elements a higher chance of being chosen, which is not what I want. Is there a way to do what I want without having to store every 'bad' element as I find them (which violates the $O(1)$ space constraint)?


texts: Does Gale-Shapley work when the number of men and women are not equal?

texts:
According to the Wikipedia page on the Stable Marriage Problem, the problem is presented in a way in which the number of men and women are both the same.

  Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

And then later on the Gale-Shapley algorithm is presented as a solution. However, based on my thinking, I believe the Gale-Shapley algorithm would work on inputs where the number of men and women do not have a 1:1 ratio. The reasoning for this is because by definition, if you look at the while loop's predicate, the men keep on proposing until they have either proposed to all of their preferences or are matched. This means that the algorithm will necessarily terminate as the men have a finite number of preferences. In the end, the men only end up matched to a woman if another man couldn't "out-bid" them for that woman. Thus it must be stable as if it were not we would have a contradiction as that man/woman that is unmatched should have proposed or been proposed to. (In general, it may be useful to let the side with a smaller number of people propose since the while loop would terminate sooner in expectation).

Overall, I'm just wondering whether the condition that the number of men and women are the same for the GS algorithm is superfluous.


texts: What is MongeElkan distance between words?

texts: i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it calculates the distance between two words. Can anyone explain how MongeElkan distance calculates the similarity.


texts: A number of points on a line, with initial positions and speeds - find a minimum time that any two points meet

texts:
How can I compute the minimum time for two points to meet in $O(N)$ time?

All I can think is to compute the time for all the point pairs and get the minimum.

Can anyone give me some hints?