texts: Prove using pumping free lemma for context-free languages

texts:
One of the exercises I tried to make I failed miserably.

The question was as follows:

Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ being the number of a's in the word, same for b's and c's)

For answers I first looked at common words not accepted by context free languages like $a^pb^pc^p$ with $p$ being the pumping length.

However I could not make a proof. Finally I got tired and with made the following construction. I assumed the length dynamic part of the ab's substring would only be one. (then it doesn't matter that much whether it is an 'a' or 'b', I chose the latter). And constructed my word like this:

$\theta b c^{n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$, with $\theta$ being some random string in $\{a,b\}^*$with 'b' being the dynamic substring v and $c^{n_a(\theta)}$ being the dynamic substring y.

With this construction $uv^0xy^0z = \theta c^{n_a(\theta)\cdot n_b(\theta)}$, which is in the language, and $uv^ixy^iz = \theta b^i c^{i\cdot n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$ is also in the language.

In other words, any string where I seperate the ab's from the c's I can prove that even by taking a v of size 1, I will always find u,v,x,y,z substrings that match.

At this point I don't really know how to construct a word any more to disprove the pumping lemma. It's very obvious that there has to be one, but not so obvious what I should look at.

Any help would be greatly appreciated.


texts: What do complexity classes look like, if we use Turing reductions?

texts:
For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions).  This leads to pictures like this:

(under standard conjectures).  I'm sure we're all familiar with this sort of thing.

What picture do we get, if we work with Turing reductions (i.e., Cook reductions)?  How does the picture change?

In particular, what are the most important complexity classes, and how do they relate?  I am guessing that $P^{NP}$ plays the role that used to be taken up by $NP$ and $coNP$ (because $P^{NP}$ is closed under Turing reductions in the same way that $NP$ is closed under Karp reductions); is that about right?

So should the picture look like $P \subset P^{NP} \subset PH \subset PSPACE$ now, i.e., something like the following?

Is there some new sequence that plays a role that corresponds to the polynomial hierarchy?  Is there a natural sequence of complexity classes $C_0=P$, $C_1=P^{NP}$, $C_2=?$, ..., such that each complexity class is closed under Turing reductions?  What is the "limit" of this sequence: is it $PH$?  Is it expected that each class in the sequence is different from the previous one?    (By "expected", I mean under plausible conjectures, similar to the sense in which it is expected that $P \ne NP$.)

Related: Many-one reductions vs. Turing reductions to define NPC.  That article explains that the reason we work with Karp reductions is that it gives us a finer-grained, richer, more precise hierarchy.  Essentially, I am wondering what the hierarchy would look like if we worked with Turing reductions: what the coarser, less rich, less precise hierarchy would look like.


texts: check if a binary tree is a binary search tree

texts:
I have some doubts about this algorithm which checks if a binary tree is a binary search tree:

isAbr(x)
    {
            if(x == NULL)
                    return <true, -∞, +∞>;
            if(x.left == NULL && x.right == NULL)
                    return <true, x.key, x.key>;

            <abrLeft, minLeft, maxLeft> = isAbr(x.left);
            <abrRight, minRight, maxRight> = isAbr(x.left);
            abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
            min = MIN(minLeft, minRight, x.k);
            max = max(maxLeft, maxRight, x.k);

            return <abr, min, max>
    }

in particular, it is not clear to me what happens when a node has only one child:

for example, here, the node with the value 6 returns $<true, 6, 6>$, and the NULL node to the right of the root returns $<true, -∞, + ∞>$; but with the instruction abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
don't we get FALSE $(8 < -∞)$?


texts: How can P =? NP enhance integer factorization

texts: If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer factorization better?


texts:
This is a homework problem and I'm not sure if I am doing it correctly.

  Show that $\log(n^2+1)\in \Theta(\log n)$.

I got:

$$ \log (n^2) \leq \log(n^2+1) \leq \log (n^2+n^2) $$
$$ 2\log n \leq \log(n^2+1) \leq \log(2\cdot n^2) $$
$$ 2\log n \leq \log (n^2+1) \leq \log 2 + \log(n^2)$$
$$ 2\log n \leq \log(n^2+1) \leq 1 + 2\cdot\log n$$

I'm not sure if I have proved it according to the definition that a function $f(x)$ is in  $Θ(g(x))$ if there exist positive constants $a,b$, and $n_0$ such that $a\cdot g(x) ≤ f(x) ≤ b\cdot g(x)$ for all $n > n_0$.

I feel like I did something wrong here.


texts: Examples for Partial Combinatory Algebras

texts:
I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), which I want to get out here, as neither of my supervisors could help me.

In Total Maps of Turing Categories [2] necessary and sufficient conditions for a category to appear as subcategory of total maps of some Turing category are given. As a corollary, the category of PTIME-functions, LOGSPACE-functions, LTIME-functions etc. can appear as total maps of some Turing category. Does this imply that these classes can be characterized by a specific PCA and (if so) how does it relate to Kleene's first model? In other words, are there complexity classes which can be represented by sub-PCAs of Kleene's first model?
Are there models of PCAs which are not a priori inspired by computability theory? The general setting of applicative system and computable function (see [1] section 4) seems to be rather general such that it may be applicable in general categories. However all my attempts to find a PCA in categories like Top, K-Vec, R-Alg, R-Mod etc. have failed. I am well aware of Kleene's second model, Scott's graph model and the $\lambda$-calculus as they are stated in Realizability - An Introduction to its Categorical Side [3]. I am just curious whether this notion of computability naturally arises anywhere else in ordinary mathematics...

I hope anybody can help me out. No matter what, thank you all for your time.


texts: Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

texts:
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.

I tried to look it up at a few places (including Sipser) but I could not make out a lot of sense from the proofs. I would appreciate it if someone can give me a proof (or clear intuition) on this.


texts: What are the irrational numbers that are generatable by a Turing machine?

texts:
Assume generating means that for all $k$ there exists $N_k$ such that after $N_k$ steps the $k$th cell on the tape consists of the $k$th digit of $\pi$'s binary expansion and will stay there forever.
Can such a machine exist? can it not?
EDIT
Is this true for every irrational number?
So this is true for $\pi$ since there exists a Turing machine to calculate the $k$th digit of $pi$ so we can construct a machine that calls the prior machine to calculate digit by digit.
But this can not be true for all irrational numbers since there are uncountably many irrational numbers and only countably many turing machines.
From this we can conclude that $\pi$ is among a special countable set of irrational numbers, call it $G$, that are generatable in the sense above.

Do we know what is the set $G = \{ g \in \mathbb{R} \setminus \mathbb{Q} : g$ is generatable $\}$ in a mathematical sense or a more informative way? We know $\pi \in G$ and we know $G$ is countable. Is there more to the picture?


texts: Is there a repository for the hierarchy of proofs?

texts:
I am self-learning proof assistants and decided to start on some basic proofs and work my way up. Since proofs are based on other proofs and so form a hierarchy, is there a repository of the hierarchy of proofs?

I know I can pick a particular proof-assistant and analyze its library to extract its hierarchy, however if I want to find the next proof in a chain to prove, I can't when it is not in the library.

In my mind I picture a graph, probably a DAG, of all of the known mathematical proofs that can be expressed using English statements, not proofs using pictures. This would be the master map (a map in the sense of starting at one point and traveling to another point via intermediate points), and for a particular proof assistant, one would have a subgraph of the master map. Then if one wanted to create a proof using a proof assistant found on the master not on the subgraph, by comparing the two graphs one could get an idea of the work needed to create the missing proof(s) for the proof assistant.

I am aware that mathematical proofs are not necessarily easily convertable for use with a proof assistant, however having a general idea of what to do is much better than none at all.

Also by having the master map, I can see if there are mulitple paths from one point to antoher and choose a path that is more amenable for the particualr proof assistant.

EDIT

In searching I found something similar for mathematical functions. I did not find one for proofs at the NIST


texts: Finding path that minimizes largest of the sum of weights of each group in a directed multigraph

texts:
Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group?  All weights are non-negative integers in the range 0..30,000.

Let me put an example for $n=2$ groups to understand it better:

If we were to find the shortest path from s to t of this multigraph, that would be easy. Just run a Floyd-Warshall algorithm and in case there is more than 1 edge for a pair of vertices, get the one with lowest weight.
The shortest path in this case would be getting all the red edges (s-1-2-t)

This would give us 2 groups with following weights:

Blue: 0
Red: 5+5+5 = 15

So the largest of this groups is max(0,15) = 15

But in this problem, we want to minimize the largest of the sum of weights of the two groups, so the path that minimizes this in this example is s-1-2-t (red-red-blue).

This would give us 2 groups with following weights:

Blue: 10
Red: 5+5 = 10

So the largest of this groups is max(10,10) = 10

I guess this problem is NP-hard, because the partition problem can be reduced to this problem. Given an instance of partition, i.e., a multiset $S$ with $k$ elements, just build a graph with $k+1$ vertices and two edges between each pair of consecutive vertices (both edges having weight equal to the corresponding element of $S$; one red, and one blue).  Or, you can reduce $n$-way multi-way partition to this problem.  Again, build a graph with $k+1$ vertices, and between each pair of consecutive vertices add $n$ edges (one for each group in the partition problem) with weights equal to the numbers in the multiset. Here is a diagram that tries to explain this reduction:

But just like there is an easy greedy approximation for the partition problem, there might be something simple for this problem aswell.
To be honest, I don't even know how to approach this problem. Any ideas?

And even though it would be great to have a general case approximation, an approximation for the case where n=2 groups would be enough for me right now.


texts: Context free grammar transformation to Normal Form

texts:
I found a task where you need to transform context free grammar to normal form.
I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to explan this, this is why I'm writting this question.
This is the task description: A chainless G grammar equivalent to G' grammar, all symbols of which can be used.
And the task is:
G : S → BC | DB
A → BD
B → b | D
C → CD | BC
D → bC | a | bB

If anybody can help me, please write a comment.
Thanks :)


texts: Does this classify as Information retrieval?

texts:
I’m trying to figure out if what I’m doing would classify as Information Retrieval. According to this Thread:

  Information retrieval is based on a query - you specify what information you need and it is returned in human understandable form.

I’ve a script that reads unstructured text (titles of books) and extracts names (which I gathered in a list beforehand) from the titles and outputs a CSV with all matched names. Would that be a simple use case of Information Retrieval or is this called „tagging“? If both not, what would one call this technique?

Thanks for your help!


texts: Which are the most effective sorting algorithms for a large dataset?

texts:
A bit of background, the work that I currently and will be doing involves sorting very large amounts of data (in this case, grayscale pixels in descending order), sometimes up to 4 million.

Which are the most effective and efficient sorting algorithms that could handle multiple large datasets (such as descried in the 1st paragraph)?  Is there an algorithm that could simultaneously sort through 2 or more sets of pixels?


texts: Minimum sub-tree of a graph that covers each color at least once

texts:
I have a connected graph $G$ with $k$ different colors assigned to $n$ nodes where $k<n$. All edges have unit weight.

I want to figure out an algorithm to find a minimum sub-tree of $G$ that covers all $k$ colors (i.e., such that for each color, there is at least one node of this sub-tree with that color; and minimizing the number of nodes in this sub-tree).

I have tried a lot about solving this problem. For $k=2$, the problem will have just one edge, and for $k=3$, it becomes tricky. For $k = n$, the problem becomes as simple as reporting any spanning tree of the graph. For any other $k$, I am not able to think of a definite solution.

Is the problem NP-hard? If so, I will be very grateful if someone can explain or a hint as to which NP-hard problem can be reduced to this problem.


texts:
In descriptive complexity, we have theorems that look like $\mathrm{ESO} = \mathrm{NP}$ or "on linearly ordered structures, $FO(LFP) = P$", but I don't really understand the proofs of those.

For the latter, the intuitive equality really means that the statement "$\mathcal A\models \varphi$" can be verified to be true on a linearly ordered structure $\mathcal A$ in time $n^k$ iff $\varphi$ is expressible in some fixpoint logic. The right-to-left inclusion then reads $\forall M\; \mathrm{polytime \;TM}, \exists \varphi\in\mathrm{FO(LFP)} \quad \left[\mathcal A \models \varphi \Leftrightarrow M(\mathcal A) = 1\right]$.

The proof I have been taught in class for the right-to-left inclusion goes as follows: from a Turing machine M (with set of states $S$), we build a formula on the language $\{T_0,T_1\} \cup \{H_i : i\in S\}$, where all relations are of arity $2k$. This formula says that the structure it's being evaluated on is a correct computation of $M$ which ends in an accepting state. How does this prove the theorem? Of course, there is a bijection between accepting computations of $M$ and structures $\mathcal A$ s.t $M(\mathcal A) = 1$, but the statement of the theorem doesn't mention this bijection. In my opinion, the formula $\varphi$ that we create should really check properties of $\mathcal A$, and not properties of the computation of $M$ on $\mathcal A$... Where is my mistake? Am I overthinking this?


texts:
I am reading Decompositions of Triangle-Dense Graphs by Gupta et al.

On page 2, in Definition 1 what is a wedge in a graph?

I know what triangle is but I don't know what wedge is and google isn't helping!


texts: Exponential averaging for SJF CPU scheduling

texts:
Calculate the exponential averaging with $T_1 = 10$, $\alpha=0.5$ and the algorithm is SJF with previous runs as $8,7,4,16$.

  9
  8
  7.5
  None

I am getting 4. None as the answer.

But it is given that 3. 7.5 is the correct answer.
I think I am missing something here.

Because I only used the formula, $S_{n + 1}{}{}{}{} = a(T_n) + (1-a)*S_n$.


texts: Why return address may be lost and information in mask, processor registers may be ambiguous if an interrupt is acknowledged in following situation?

texts:
In the text Computer System Architecture (3rd Edition) by M Morris Mano , on pg. 415 under the section parallel priority interrupts I came across the following statements.

The bit in the interrupt register belonging to the source of the interrupt must be cleared so that it will be available again for the source to interrupt. The lower-priority bits in the mask register (including the bit of the source being interrupted) are set so they can enable the interrupt. The return to the interrupted program is accomplished by restoring the return address to PC. Note that the hardware must be designed so that no interrupts occur while executing steps 2 through 5; otherwise, the return address may be lost and the information in the mask and processor registers may be ambiguous if an interrupt is acknowledged while executing the operations in these steps. For this reason IEN is initially cleared and then set after the return address is transferred into PC.

My question is if an interrupt occurs again in the steps mentioned, why shall be the return address be lost? Could we just store the return address onto the stack as we have for handling a higher priority interrupt?
I could not understand how the information in the mask and processors might get ambiguous?
To understand the concepts better, here I include the entire detail of the context from the said text. It is a bit long, but please bear with me!!


texts: Are all $\Sigma^0_1$ sets of infinite sequences infinite?

texts:
I think I figured out some things about $\Sigma^0_1$ and $\Pi^0_1$ in the arithmetical hierarchy, for sets of infinite sequences, and I'm hoping I can get confirmation that I'm right, or can understand the ways in which my thinking is incorrect.
What I think I have figured out is that every set of infinite sequences in $\Sigma^0_1$ must be infinite in size--in fact uncountable--since a sentence containing only existential quantifiers over indexes into a sequence can only require that some digits satisfy a predicate.  Therefore, any sequence satisfying the sentence would do because of a property of a finite number of locations in the sequence.  All subsequent digits after those locations would be allowed to vary freely, in which case the number of sequences with the same initial pattern would be uncountable.
By contrast, sets of infinite sequences in $\Pi^0_1$ may be either be finite or infinite, I think.  For example:
$\{x: (\forall n)\, x[n]=0\}$ contains only one element, $000\ldots$ .
$\{x: (\forall n)\, x[n]=0$ if $n$ is odd$\}$ allows the digits at the even-numbered locations to vary freely, so the number of sequences that satisfy this predicate for all $n$ is uncountable.
Is this correct?  Are there ways in which I'm confused, or some obvious nuance that I'm missing?


texts: Problems that are easy on boolean formulas but become NP-hard on circuits?

texts:
Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input?

In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is 1.

For example, evaluation (when also given an input to the boolean formula or circuit, evaluate the output) is easy (in P) in both cases.
On the other hand, guessing the input (when given an output of the formula or circuit) is NP-hard in both cases. For example, 3-SAT is such a problem on formulas that's NP hard.
Do we have examples, preferably "non-contrived", that are easy (in P) on boolean formulas but NP hard on boolean circuits?
Since treewidth is NP hard to compute on general graphs and 1 on trees (/formulas), this might be an example, but I find this "contrived" as now we're treating the input as a graph instead of inherently as something that can compute something: we're basically ignoring the difference in AND and OR gates. In the same way graph problems that are polynomially computable for trees and NP hard for general graphs might be such "contrived" examples.


texts: Minimizing the sum of differences in a pair

texts:
You have two arrays, a and b

Both contain n elements, all positive and distinct.

you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs are minimized.

for example, a = [1, 2, 3], b = [4, 5, 6]

one possible set of pairs = (1, 4), (2, 5), (3, 6)

sum of differences = |1 - 4| + |2 - 5| + |3 - 6| = 9

And now the sum of the differences has to be as small as possible

Desing an algorithm that those this is O(nlogn) time

So far, I have sorted both these arrays. I am unsure how to proceed now


texts:
I have the following diagnosis problem:
h(A): z1 = not(in1)
h(D): z2 = not(in2)
h(B): z3 = z1 or z2
h(C): out1 = not(z3)
h(E): out2 = not(z3)

This is an image of the system:

I have an observation where I know that:
in1 = false
in2 = false
out1 = true
out2 = true

I want to check if {B} is a diagnosis of the system, meaning that I assume that A,D,C,E are valid, while I don't assume the same about B.
This I want to turn into a sat problem. So first I map each variable in my system to a literal:
in1: 1
in2: 2
z1 (the output of A): 3
z2 (the output of D): 4
z3 (the output of B): 5
out1: 6
out2: 7

So to check if {B} is a diagnosis of the system (meaning that if I remove the assumption about {B} the system will be OK) I create a CNF like so:

not(1) AND not(2) AND 6 AND 7 - this represents my observations, the variables whose value I know for sure.

Now I want to add a representation for my constraints. For example, I know that 6 = not(5), but I don't know the value of 5 (because I can't assume the validity of component B).
My question is how do I add this knowledge to my CNF representation? If I add "not(5)" to my CNF then I assume the output of B is always false, and this isn't correct.

Thank you very much.


texts: Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$?  If not true in general, is it true if $a$ and $b$ are elegant programs?


texts: Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

texts:
I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?

For people who were following in the original question about heaps, it has been moved here.


texts:
For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete?

Is it enough to be able to access just the top-most item? Two items? Three? Any item?

In the case of Forth, is it necessary to have rot, pick, roll? Why does rot operates with exactly top three items?


texts: Closest pair of points between two sets, in 2D

texts:
I have two sets $S,T$ of points in the 2-dimensional plane.  I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as possible.  How efficiently can this be done?  Can it be done in $O(n \log n)$ time, where $n = |S|+|T|$?

I know that if I'm given a single set $S$, then it's possible to find the closest pair of points $s,s' \in S$ in $O(n \log n)$ time using a standard divide-and-conquer algorithm.  However, that algorithm doesn't seem to generalize to the case of two sets, because there's no connection between the distance between the two closest points within $S$ or $T$ vs. the distance between the two closest points across those sets.

I thought of storing the set $T$ in a $k$-d tree, then for each $s \in S$, using a nearest-neighbor query to find the closest point in $T$ to $s$.  However, the worst-case running time of this might be as bad as $O(n^2)$ time.  There are results saying that if the points of $T$ are randomly distributed, then the expected running time for each query is $O(\log n)$, so we'd obtain an algorithm with expected running time $O(n \log n)$ if we were guaranteed that the points are randomly distributed -- but I'm looking for an algorithm that will work for any collection of points (not necessarily randomly distributed).

Motivation: An efficient algorithm would be useful for this other question.


texts: Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?

texts:
One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the page. When one tries to model natural language (e.g. as http://www.grammaticalframework.org/ tries to do it), then one usually aims for the most expressive formal language that is still decidable and recursive languages are exactly such languages - they are the most expressive decidable languages. But GrammaticalFramework instead narrows the scope and uses the mildly context-sensitive language instead for doing its modelling. Why it is so? Why one elaborates the hierarchy of languages, what compromises he or she tries to make?

As far as I understand from my studies, then the complexity issue is the single most important issue. One can try to use recursive language, but recognition and parsing of such languages are very slow. Or maybe there are different reasons? Maybe there are not even algorithms how convert recursive language into total Turing machine (and vice versa) or maybe there are not even algorithms for the parsing of recursive language. So - why not to use recusive language? Due to lack of algorithms? Or due to nonpolynomial/exponential complexities of those algorithms? And that is why the hierarchy is so elaborated - one can try to find the most expressible language with the best complexity properties.

It is somehow different with logics. In logics one can tolerate the complexity issue and one is required to make compromises between expressibility and decidability. For recursive languages the recognition is decidable and so one should seek compromises between expressibility and complexity. Am I right?

The key point of my question is this: what obstacles prevent the practical use of recursive languages and why one is required to elaborate hierarchy of languages and to use less expressive languages? Complexity? Lack of algorithms? Something different?


texts:
I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives.

Can anyone tell me how i can prove this?


texts: Floating point operations; Exception, Flags, and Trap Handlers

texts:
I am reading over the article found here specifically §D.4.4 Exceptions, Flags and Trap Handlers and am confused by the table D-4 in that section.

Specifically the arguments sent to the trap handler for the overflow and and underflow exceptions.

It shows round(x2-α) as the argument for both the over and underflow conditions (EDIT: It is not). I am not sure what x2 is at all, I see no reference to it in the section.

As for α footnote says:

  *xis the exact result of the operation,  α= 192 for single precision, 1536 for double, and xmax= 1.11 …11 ×2^e_max.

So it says  "α = 192 for single precision, 1536 for double" which is also confusing. Where do these values come from?

I am not looking for anything super in-depth, just something succinct.


texts: Instantiating a class with a sig'd type in Coq

texts:
I can easily define a class that corresponds to the notion of a "monoidal structure" on a type M via
Definition associative {X:Type} (f : X -> X -> X) : Prop := forall x y z:X, f (f x y) z = f x (f y z).

Definition opId {X:Type} (f : X -> X -> X) (e : X) : Prop := forall x:X, f e x = x /\ f x e = x.

Class Monoid (M:Type) :=
  { binM : M -> M -> M ; idM : M ; assocMProof : associative binM ; idMProof : opId binM idM }.

and then instantiate it, for instance, with the type of endomorphisms over a given type with operation being composition:
#[refine] Instance compMon {X:Type} : Monoid (X -> X) :=
{
binM f g := fun x => f (g x) ; idM := fun x => x
}.
Proof.
  - unfold associative. reflexivity.
  - unfold opId. intro. split. reflexivity. reflexivity.
Defined.

but how would I, for example, go about defining the monoidal structure on the set of injective endomorphisms over a type? (Or even better, formalizing the notion that binM in compMon restricts to such a monoidal structure?) I presume I would want to define injective and then instantiate Monoid {f : X -> X | injective f} but not only would that seem to entail defining a new binary operation (which takes functions f, g and proofs of injectivity i, j and produces a new function with a new proof of injectivity) and a new identity, it seems that said binary operation wouldn't even be associative (of course $f \circ (g \circ h) = (f \circ g) \circ h$ as functions, but the proofs of injectivity aren't the same?). What am I missing?


texts: Counting the number of occurences - loop invariant

texts:
I'm trying to come up with loop invariant for the following program.

k = a[0]
m = 1
p = 1
while p < n:
    if a[p] == k:
        m += 1
    p += 1
return m

I belive this program returns the number equal to the number of occurences of element a[0] in my array "a".

I thought maybe this is a good cadidate:

|{i: 0 <= i <= n and a[0] == a[i]}| = m

Am I ok? If not, is this even the right direction to go?


texts:
Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is:

a) 94

b) 416

c) 464

d) 512

My approach:- I have read in the book that minimum frame transmission time is atleast twice the round trip time.So by that logic i can say that the answer will be 464.As soon as the first bit of jamming signal reaches the sender,it know about the collision. But I need to know whether time to transmit jamming signal over the link should also be included in this case?I mean whether the first bit of the jamming signal is sufficient to for the sender to detect the collision or the complete jamming signal needs to be received at sender side,which will make the answer as 512.

I dont have the answer as this question was in some exam in 2005 and there was no answers available to this.


texts: Design a Turing machine that accepts L={ww^r | w:(0,1)*}?

texts:
Can anyone help :(

L = {ww^r | w element of (0,1)*}

Would it be like in :pseudo code, check if the string is equal to itself in reverse?


texts: CYK algorithm - how to handle unknown terminals given in a sentence to parse?

texts:
There is a given treebank which we derive the Probabilistic context free grammar.
I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules?
Is there a kind of smoothing for this case?
Considering we use CYK to get the parse tree of the given sentence.


texts: Fuzzy string matching algorithm with allowed events?

texts:
I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions were used for any match.

Using brute force backtrack I can find the matches, but I cannot guarantee that the match was produced using the fewest permutations possible.

Using dynamic programming I can find the matches and guarantee that the match was produced using the fewest permutations possible, but I cannot specify a number of allowed mismatches, insertion and deletions - only a total edit distance.


texts: Is the problem "find the sequence of $N$ numbers between 1 and $D$ with least cost", NP-hard?

texts:
Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(q)\neq c(p), \forall p,q\in\{1,\dots,D\}^N$ with $p\neq q$. The problem is to find $p\in\{1,\dots,D\}^N$ with least cost $c(p)$. I want to show that this problem is NP-hard.
In my opinion, since all costs are different, there is no other way but to check all possible ($D^N$) combinations to find the optimum. Should this be enough to conclude that this problem is NP-hard? If so, what is the "formal argument" under this line of reasoning?
Alternatively, is there a standard reference which state that a problem like this is NP-hard? Which other NP-hard problem can be reduced to this one?


texts: Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas

texts:
I recently asked a similar question, however, I'd like to address it in a more mathematically precise setting.
In that paper, on page 5, it talks about a rigorous definition of what it means to $\epsilon$-refute random 3CNF formulas. For that, I will provide a screenshot of the exact part I want to address:

The problem of refuting random 3CNF concerns efficient algorithms that provide a proof that a random 3CNF is not satisfiable, or far from being satisfiable. This can be thought of as a game between an adversary and an algorithm. The adversary should produce a 3CNF formula. It can either produce a satisfiable formula, or produce a formula uniformly at random. The algorithm should identify whether the produced formula is random or satisfiable.
Formally, let $\Delta\colon \mathbb N \to \mathbb N$ and $0 \leq \epsilon < \frac14$. We say that an efficient algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if its inputs is $\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$, its output is either "typical" or "exceptional", and it satisfies:

Soundness: If $\operatorname{Val}(\phi) \ge 1-\epsilon$ then $$ \Pr_{\text{Rand. coins of $A$}}(A(\phi)=\text{"exceptional"}) \geq \frac34.$$

Completeness: For every $n$, $$ \Pr_{\substack{\text{Rand. coins of $A$}\\ \phi \sim \operatorname{Uni}(\mathrm{3CNF}_{n,n\Delta(n)})}}(A(\phi)=\text{"typical"}) \geq 1 - o(1). $$
By a standard repetition argument, the probability of $\frac34$ can be amplified to $1-2^{-n}$, while efficiency is preserved. Thus, given such an (amplified) algorithm, if $A(\phi)=\text{"typical"}$, then with confidence of $1-2^{-n}$ we know that $\operatorname{Val}(\phi) < 1-\epsilon$. Since for random $\phi \in \mathrm{3CNF}_{n,n\Delta(n)}$, $A(\phi)=\text{"typical"}$ with probability $1-o(1)$, such an algorithm provides, for most 3CNF formulas, a proof that their value is less than $1-\epsilon$.

The exact part I want to address is the properties soundness and completeness of the algorithms.
First, what does it mean that the output is "typical" or "exceptional"? I don't think the authors define that precisely. I am guessing from context, if the algorithm returns exceptional then it found a boolean formula that is unsatisfiable? Though I am just guessing from the definition of the word refute.
From the definition of $\operatorname{Val}(\phi)$ (=the fraction of clauses that are satisfiable, so its 1 when the whole thing is satisfiable) I am assuming that if the algorithm is sound then if it returns an answer, then the answer must be correct (i.e. the formula must be unsatisfiable). However, from the definitions given, it seems that if the formula is nearly satisfiable, then it says with high probability (greater than 3/4) that its "exceptional" (whatever that means)?
For completeness, what that usually means for me is that, if there is a correct answer, then the algorithm will return it. In this case, if we give it a boolean formula, if it's unsatisfiable, then it will say so. Thats what completeness usually means for me. In this case, the conditions given in the paper for completeness are hard for me to understand.
I think maybe the main source of confusion might be what the word "exceptional" and "typical" mean. My intuition says that most boolean formulas are unsatisfiable, so in fact, "exceptional" should mean satisfiable and "typical" means unsatisfiable? Which is kind of opposite of what a refuting algorithm would do in my head.
Anyway, anyone have any ideas of how to resolve this in a mathematically precise way?


texts: Handling dead state in NFA to DFA conversion

texts:
I want to convert below NFA into DFA:

I prepared below tables and finally the NFA:

NFA

However I feel I am wrong here, since original NFA does not have any transitions defined for state C and my final DFA does not have any dead state. However I dont understand where I am going wrong.


texts: Iteration vs Recursion question in Lisp method

texts:
I am curious if the following method would be called iterative or recursive:

(define (deep-reverse items)
  (define (iter things answer)
    (cond ((null? things) answer)
          ((pair? (car things))
            (iter (cdr things) (cons (deep-reverse (car things)) answer)))
          (else (iter (cdr things) (cons (car things) answer)))))
  (iter items ()))

I am confused because iter only calls itself with the state variables things and answer as arguments, and modifies those each run, so that I think it is iterative. It is defined in a method deep-reverse that does recursively call itself... This is confusing to me because there are elements both of iteration and recursion in this method, so that I don't know in the end how I would classify it... Is deep-reverse recursive? Is iter iterative?

Thank you.


texts: Is the identity function a many-one reduction from a language to super-set?

texts:
I need help with a question.

Prove or disprove the following claim:

  Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?


texts: What is the size of the Perfect binary tree with n nodes in last level

texts: I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be calculated


texts: Turing Machine to Accept String from a 3 character alphabet

texts: I need to create a turing machine that accepts the language $a^ib^jc^k$ where $i \ge j \ge k$, but I am not even really sure how to start. Turing machines in this context are a hard concept for me to grasp for some reason.


texts: Maximum Enclosing Convex Polygon of a Given Area

texts:
My question is very similar to another solved question. As the title indicates, the major difference in my question is that I need to find the convex polygon that encloses the maximum number of points with a given area (instead of finding the circle that encloses the maximum number of points with a given radius).

So my question is as the following:

  Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a convex polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

I already checked on the Minimum bounding box algorithms and Convex hull algorithms. I also found some implementations for Minimum bounding polygon. However, those previous algorithms don't consider the concept of determining the convex polygon that encloses as many points as possible of a given set of points and a given area. Finally I invented an approach to solve the problem but it doesn't work in some cases.

The idea of my approach is to start by finding the minimum bounding box for all the points. If the resulting polygon's area is greater than the given area, I cut off one of the edge points according to some technique, then I re-compute the minimum bounding box and test the area. I keep looping until I reach the desired area. I won't get into details with my approach as it's not working properly.

EDIT

As a simplified solution, finding any rectangle (it doesn't have to be axis-aligned) that encloses the maximum number of points with a given area would be very beneficial and works as a temporary solution for my problem.


texts: How can we show that Halting Problem for one-counter additive machines is decidable ?


texts: What does the three schema architecture of DBMS refer to?

texts:
This architecture contains three layers or levels of the database management system:

External level

Conceptual level

Internal level

Can some one explain to me with a practical real example so that i can understand this?
Before constructing a data model does enterprise's architects consider to make a three schema architecture of DBMS. But I am totally confused with this abstract model.


texts: How to compute all primes between upto $n$ in time $O(n)$ time?

texts:
Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$.

For $j=2$ to $j=\sqrt n$
mark multiples of $j$ from $A$

Running time of this algorithm is $O(n \log n).$ It is easy to see that after first iteration there will be $n/2$ many unmarked elements and so on.

The problem with this method is that some of the elements may be marked more than one time.

Question : How to compute all the primes upto $n$ in $O(n)$ time?


texts: What is the status of the TSX-related Skylake errata SKL-105?

texts:
(Copy of https://stackoverflow.com/questions/38868226/what-is-the-status-of-the-tsx-related-skylake-errata-skl-105 which didn't get much attention).

As is well known, Intel had to disable TSX in the Haswell-series of processors via a microcode updates. This was due to a bug in the TSX implementation that could give erroneous results if these instructions were used.

What seems to be less well known is that there is apparently also an errata affecting TSX on the newer architecture, Skylake. Specifically the errata "SKL-105" mentioned here:

http://www.intel.com/content/www/us/en/processors/core/desktop-6th-gen-core-family-spec-update.html

It specifically states that using TSX can lead to unpredictable system behavior. However, it also notes that it is possible for the BIOS to carry a fix. However, the question is then what this fix entails. Does it disable TSX altogether like the Haswell microcode "fix"? Googling "SKL105" gives no results so it seems the community is generally unaware of it?

Some users have noticed the TSX feature getting "steathily" disabled (but seemingly being unaware of the errata above):

https://www.reddit.com/r/hardware/comments/44k218/intel_disables_tsx_transactional_memory_again_in/

It is strange if only certain variants of the CPUs are affected, since one would presume they would all share the same microarchitecture and hence be equally affected by this bug.

By the way another way such a microcode "fix" could operate and which could be even more stealthy: I suppose it would be possible to make a microcode update that would still expose the presence of TSX (making it seem the feature was still enabled) but would override the implementation of the new TSX instructions with "dummy implementations" that actually would never elide the locks and essentially just execute the code the old-fashioned way, thereby avoiding the bug but also foregoing the performance improvement TSX could offer. The only way to determine if this happened would be through performance measurements.

Anyone has more info on the status of TSX in Skylake? In any case it is strange that not more info is released and one has to guess what is affected and what is not. And indeed if the feature is safe to use.

I have a 6700K and the feature is still there. But this also depends on whether the BIOS manufacturer has taken in the microcode updates and also I haven't actually measured the performance so I can't exclude it could still have been disabled cf. the previous paragraph.


texts: Selective Background Updating in Running Gaussian Average Method for Background Subtraction

texts:
I am studying the Running Gaussian Average Method for background subtraction. One alternative, as described in Wikipedia, also known as Selective Background Updating, is to only update the distribution of background pixels.

I have two questions on this topic:

(1) To determine whether a pixel is foreground or background, we need to calculate ${\mu}_t$ as follows:
$${\mu}_t = M{\mu}_{t-1} + (1-M)(I_t{\rho}+(1-{\rho}){\mu}_{t-1})$$

But the $M$ in this formula depends on whether the pixel is foreground (in this case, $M=1$) or background (in this case, $M=0$). So it becomes a circular dependence. Currently I tried to solve this by calculating:
$$(I_t{\rho}+(1-{\rho}){\mu}_{t-1})$$

Then after deciding the pixel is foreground or background, I determine $M$ and use the first formula to update the value of ${\mu}_t$. Is this correct?

(2) The Wikipedia page only suggests to update the mean of each background pixel using the first formula above. Shall we update the variance as well, like as follows?
$${\sigma_t}^2 = M{\sigma^2_{t-1}} + (1-M)(d^2{\rho}+(1-{\rho}){\sigma^2_{t-1}})$$


texts: Pumping Lemma for single character language

texts:
I have a question about the Pumping lemma. Condition $2$ of the pumping lemma for a string division $xyz$ states that the middle portion of the string $y^i$ can be 'pumped' for any $i$ greater than or equal to $0$. This means that y can be the empty string and yet still belong to the language. At the same time, the cardinality $|y|$ has to be at least $1$.

How would I be able to apply this if the regular language is only a single character? i.e. $L = \{a\}$. Here, I can set $y = \{a\}$ so that the cardinality is greater than zero --- however, it fails to meet the condition that $y$ can be 'pumped down' to the empty string....

But obviously, $L =\{a\}$ is a regular language.

And there's also something obvious that I missed ...


texts: Representing chained XOR operations as linear inequalities

texts:
I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met:

$x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$

where $\oplus$ is the binary xor operator.

The answer to this question shows how to represent $y = x_1 \oplus x_2$ with linear inequalities. In an answer to this question there is an attempt to generalize the representation to more than two inputs, but the two answers seem to be inconsistent, since the latter doesn't even use inequalities.

So, the question is: how can I represent $y = x_1 \oplus x_2 \oplus \cdots \oplus x_n$ as set of linear inequalities?


texts:
I'm wondering if there are any universally accepted "best" algorithms for syncing data sets.

I imagine there would be different solutions depending on circumstances:

Are all peers online all the time or not?
Are we more limited by bandwidth or processing power?
Are data items large or small?
Does data get modified and deleted or are we just accumulating a growing collection of data?

My question is what are the equivalents to Djikstra's and Kruskal's algorthim of my problem?

You might say the two well known algorithms mentioned solve problems which are much more specific. That's probably true, so let me narrow down my question:

What is a good way to calculate a diff between two versions of a large growing set of very small chunks of data? Assume data is never deleted or modified, synchronisation happens between a limited number of peers, somewhat regularly but there is no real server and client situation, any peer could have some new data.

I feel I just don't know where to start looking, what papers to read.


texts:
I know the fact that you cannot run the same machine code on two different machines,

so the software must be machine dependent (i.e Arm program cannot run on either powerpc or x86).

but in reality the software is OS dependent (i.e linux programs cannot run on windows or mac).

how does this happen? my best guess for now is that every OS behaves like a virtual machine and the source is compiled for windows-machine,may be??
and this machine has its own assembly code?


texts: Training algorithm for Manual error correction in text

texts:
I want to work on a model where I make some manual corrections in my clinical notes data and want the neural network to learn those corrections.The algorithm will be supplied with both corrected and initial documents for supervised learning.

I am now looking for some survey or research papers to start with. I have searched and downloaded tens of articles but none of them seems related.

I would appreciate if someone could provide a few good starting points (papers, books).

also I suspect that I am not using the correct keywords for my search. I'll appreciate if you could also suggest suitable search keywords.


texts: Limiting memory usage while keeping score

texts:
For an assignment we are asked the following(simplified) :

A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is given:
new_a = (c1 * (previous_a or first_a) + c2) mod c3
Write, in C#, a sufficiently fast and memory efficient algorithm that tells how many iterations of the function does it take before new_a is within a specified range of any previous ones?

Now I have already made a "naive" solution as follows: I create an array of size c3 and for every new_a I check whether its corresponding index is set to true. If so, the number of iterations is returned. If not, the index and the given range around it is set to true. This goes on until there is a hit.
This solution is very fast but the downsize is that for large enough sizes of c3 there is just not enough memory available.
I have been thinking about a week now on how to solve the memory problem, but I just am stuck figuring out how to do it? The only thing I can think of is that given the function there is some kind of assumption I should/can make about the distribution of its outcomes but I just am stuck.
Any ideas on the direction I should take?


texts: call by name : how are clashing variables handled?

texts:
In call by name : In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

ref : http://www.cs.sfu.ca/~cameron/Teaching/383/PassByName.html

Now consider the following code :

global int i = 100, j = 5;

void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}

main()
{
    P(i + j);
}

Will the variable i declared in function P get renamed before execution ?
Which i ( global or local ) is accessed by x in print(x + 10) ?
Which i ( global or local ) will get updated by (i = 200) ?
What will be the output of the second print statement (220 or 120 ) ?


texts: Prove 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1

texts:
So I am trying to work on a problem and honestly... I am so lost with this one. I will try to ask it the best I can.

Exact text of the problem: "Prove the following directly from the definition of Big Theta; 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1"

Additionally, the definition in question is [Click here to see definition]

Basically, I don't understand the definition and I don't understand the question. I understand that this chapter is talking about asymptotic behavior, and how given 2 different functions these 1 number could "grow" faster than the other up to a certain point and then it would switch. Example, Using 1 and 100,000,000 as n. In the following 2 functions 1 is larger number using 1... and then the other one is larger when you 100,000,000.

1,000,000n and n^2

Perhaps someone can help put the definition and question into words I can understand a little better.


texts: Can a dynamic language like Ruby/Python reach C/C++ like performance?

texts:
I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, compiling Ruby code can't ever be efficient because the way Ruby handles reflection, features such as automatic type conversion from integer to big integer, and lack of static typing makes building an efficient compiler for Ruby extremely difficult.

Is it possible to build a compiler that can compile Ruby or any other dynamic languages to a binary that performs very closely to C/C++? Is there a fundamental reason why JIT compilers, such as PyPy/Rubinius will eventually or will never match C/C++ in performance?

Note: I do understand that “performance” can be vague, so to clear that up, I meant, if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y? Where X is everything from device drivers and OS code, to web applications.


texts: Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?

texts: If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq coRP}$ and hence $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq ZPP}$?


texts: Possible to use master method on T(n)/g(n)=aT(n/b)+f(n)

texts:
The master theorem can be used in case of a recurrence relation of the form

1) $T(n) = aT(\frac{n}{b}) + f(n)$

My question is whether it can be applied if

2) $\frac{T(n)}{g(n)} = aT(\frac{n}{b}) + f(n)$.

My gut feeling is that is should be possible: just solve equation 2 by solving equation 1, and then multiply the asymptotic bound I receive by $g(n)$

I just can't prove it


texts: Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number encoded by the k-length bitstring to outputs of the die by dividing the range $[0,2^k-1]$ into 6 intervals each of length $m$. However, this is not possible, since $2^k$ has two as its only prime factor but the prime factors of $6m$ include three. There should be some other simple way of doing this, right?


texts: "Greater than" condition in integer linear program with a binary variable

texts:
How can one model the following condition in an integer linear program?

$$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$ and $B, C \in \mathbb N$. We have upper and lower bounds on both $B$ and $C$.


texts: Algorithm for deciding alpha-equivalence of terms in languages with bindings

texts:
I am interested in the alpha equivalence relation in languages with variable bindings, such as:

t := x:y    'x belong to y'
  | bot     'False'
  | t -> t  'implication'
  | Ax.t    'forall x, t'

Or the pure lambda calculus:

t := x       'variable'
  | (t t)    'application '
  | Lx.t     'abstraction: \x -> t'

I am looking for an algorithm allowing me to determine whether two terms of the language are alpha-equivalent or not. Any published reference is very welcome too. I am assuming a data representation of the terms as a standard
recursive type, for example in Haskell:

newtype Var = Var Int
data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term


texts: Gradient Direction Equation: Color Value

texts:
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

On computing the gradient direction, given the equation:

theta = arctan( Gy / Gx )

where:

theta = is the resulting angle
Gx = is the X gradient component
Gy = is the Y gradient component
(both Gx and Gy are from the gradient maps)

Now, my question is, are the values of Gx and Gy in RGBA (or ARGB) Color Space? or  since the values of R,G and B are equal due to gray scaling, are we going to use the (8 bit) value from any of the color components (R,G, or B)?


texts: Worked out example of Slepian-Wolf Theorem

texts:
Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.

The Slepian-Wolf theorem states that sequences of outputs from two separate random variable sources A and B that have a joint probability distribution defined on them, if encoded with the following rates, can be completely retrieved when decoded together:

$$
R_A \geq H(A|B) \\
R_B \geq H(B|A) \\
R_A + R_B \geq H(A,B)
$$

$R_x$ refers to the bits required for encoding one symbol of $X$, assuming all logarithms are taken to the base 2.

Given this, I wanted to try out an example, especially because I find fractional number of bits per symbol slightly confusing to think about.

Consider two sources $A$ and $B$, that either sprout out 0 or 1 following this probability distribution:

A \ B   0    1
  0    0.5   0
  1    0.25 0.25

We calculate the entropies as follows:
$$
H(A,B) = 3/2  = 15/10\\
H(A|B) = 7/10 \\
H(B|A) = 1/2 = 5/10\\
$$

Now, assume that the a certain sequence of bits that A and B give out are as follows:

 A  B
 0  0
 0  0
 1  0
 1  1
 1  0
 0  0
 0  0
 1  1
 1  0
 0  0

I should be able to find an encoding that allows A to send atleast 7 bits, B atleast 5 and a total of atleast 15, such that they can be decoded completely, right?

Unfortunately I am unable to think of an encoding where they send less than 10 bits each.

For example, B does not have to send anything when A sends 0, however B does not know when A sends 0.

I would also like to know if this is the wrong way to interpret the theorem (perhaps a longer sequence is required), or if there is another way to see its working.


texts: Optimal locations for vertices of a polygon with given area

texts: I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their initial locations. I'm looking for an optimization algorithm that looks at the change in the area of the sub-triangle associated with that vertex to minimize the area difference A-A'.


texts: What does Godels Incompleteness theorem "true but unprovable" mean?

texts:
I have asked this on the "computer science chat" ( vzn tried to explain me ) . I even watched a couple a videos to understand the theorem but still cannot convince myself. The following is the way the Godel's Incompleteness theorem is proved in Sipsers, where it is shown not all true statements are provable:

Notations, assumptions and preliminaries

The statements being considered are assumed to be in prenex form ( with boolean operations $\neg,\vee,\wedge$ ). The model is $(\mathbb{N},+,*)$ ie. variables can take values from the set of natural numbers and relations are addition and multiplication. The set of true statements in this model is denoted by $Th(\mathbb{N},+,*)$. $Th(\mathbb{N},+,*)$ is shown to be undecidable by reducing $A_{TM}$ to it. The reduction is given as, on input $\langle M,w\rangle$ construct statement $\psi=\exists c [ \phi_{\langle M,w \rangle}]$, where,
$\psi$ is true if and only if $c$ is an accepting computation history of string $w$ given as input to turing machine $M$.
Proof of a statement $\phi$ is ( loosely speaking ), a sequence of statements, $S_1, S_2, . .. ,S_i$, where $S_i = \phi$. Each $S_i$ follows from the preceding statements and certain basic axioms about numbers, using simple and precise rules of implication. The proof a statement is denoted by $\pi$.
The language $L=\{\langle \pi,\phi \rangle | \; \pi \text{ is a proof for } \phi \}$ is decidable ie. I can check the correctness of a proof for a statement. The Turing machine deciding $L$ is denoted by $D$.
All provable statements are true.
$P$ is a Turing machine that takes as input a statement $\phi$ tries to find a proof for it by giving $\langle \pi,\phi\rangle$ as input to $D$ for all proofs $\pi$ and accepting if $D$ accepts $\langle \pi,\phi\rangle$ for some $\pi$  ( if proof does not exist for $\phi$ $P$ does not halt ).

Proof

Construct the Turing machine $S$ such that
$S$ = "On input any input

Obtain own description $\langle S \rangle $.
Construct the statement $\psi=\neg \exists  c [ \phi_{\langle S,0\rangle} ]$ ( $0$ is some specific input string ).
Give statement $\psi$ as input to $P$.
If preceding step accepts, accept. If it rejects reject. "

The reasoning given by Sipsers is if $P$ is able to find a proof for $\psi$ it means $S$ will accept $0$, but then statement $\psi$ will be false and a false statement can't have a proof which is a contradiction. The only option is that $P$ does not find a proof for $\psi$, but then $S$ won't halt on $0$ and $\psi$ becomes true. Thus $\psi$ is a true but unprovable statement.
My doubt is, isn't the reasoning given above  that $\psi$ is true  a proof in itself ? I expected the proof would be of sort where I am able to construct a statement $s$ and prove that neither $s$ nor $\neg s$ is provable. Am I misunderstanding something ?
I can improve if my explanation of the problem is incorrect or vague.

EDIT

In the proof $\phi_{\langle S,0 \rangle}$ is a formula with a single free variable
$c$, such that the sentence $\exists c [\phi_{\langle S,0 \rangle}]$  is true if and only if there is an accepting computation history $c$ of input $0$ to Turing machine $S$.


texts: how does Kleene-Post show two languages that are not Turing reducible to each other?

texts:
I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.
I've seen it in many places: for example a very brief summary here (where it is used to answer a different question about mapping reducibility), and also in page 2 here and also page 40 of here. There's also a prior thread on Kleene-Post, but that asks something very specific about one component of Kleene-Post, not how the entire proof works.
Very roughly speaking, it seems to be something about constructing a pair of sequences of languages (or sequence of sets of languages, I'm not too sure) such that for each "step" in the sequence, there's at least one oracle TM (i.e. a TM that is able to query some oracle) for which an oracle for one "side" cannot be used to decide the other "side". Once these sequences are done, we take the intersection of every element in the sequence, and by construction all the languages in this intersection will fail to be mutually Turing reducible by every single possible oracle TM.
While I believe the general argument follows the above, I don't understand the details at all, since the proofs I've linked to use terminology (e.g. recursive, characteristic function, etc.) that differs significantly from those used by Sipser, the textbook I'm following (e.g. Turing recognizable, Turing decidable). There's also a few other proofs I've seen which I have not linked, and in those proofs I found the notation and exposition still difficult to understand.
My question is: how does the Kleene-Post proof work? What are the details of the construction, presented carefully in a way that is unambiguous and easily understood, preferably using terminology from Sipser as opposed to equivalent but different terminology?


texts:
I keep seeing 3 X 8, 4 X 16, etc. kind of decoders explained on youtube
4 is the input (address bus) and 16 is the output.
4 X 16 can only access 16 unique addresses.
What if I have thousands of memory address like 4096, 65,536, etc.
How many address bus and output is required in these decoders?
.
.
.
.
If I put 12 bits address in a "12 x 12 encoder" it will need to output the same value to able to access it in 4,096 unique addresses.
But I if reduce the number of the input (address bus) e.g 8 x 12, then I have limited the possible addresses I can access since 8 bits can only output 256 unique values.
Which is what 3x8, 4x16 decoders I'm seeing are like. So why the need of decoder?
.
.
.
.
.
.
Let's say I have a memory with 4,096 addressable location, doesn't matter how wide those memory addresses are (8 bit wide, or 16, or 64) I only care about their location.
To be able to locate all the addresses specifically, I will need 12 address bus for the address encoder since 12 bit can have 4,096 unique values. Right?
Same if I have 65,536 memory addresses, I'm gonna need 16 address bus since 16 bits can have 65,536 values.
So 2 billion (2,147,483,647 or 2 GB) memory address needs 32 address bus?
So the address encoder will look something like this for 4,096 memory addresses? Still unsure how many output needed though.
https://i.imgur.com/7HI34dU.jpg


texts: Recursively enumerable but non recursive subset of an infinte recursive language

texts:
How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive?

I think we need to show there's a list of natural numbers that can't be ordered but I don't know how to build such a subset.

Is there another way of arguing or another type of argument in order to prove such subset exists?


texts: How does a nondeterministic Turing machine work?

texts: What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"? How to use it right, and examples of wrong usage. My goal is to create a reference question.


texts: Internal tangent intersection of two point sets in linear time

texts:
I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable, so I think the internal tangents are uniquely defined as the two lines which are tangent to each of the convex hulls of the sets, such that each set is on a different side. This is the point marked green here:

This paper ("Computing Plurality Points and Condorcet Points in Euclidean Space") I'm currently reading (paywalled, unfortunately...) says in a sort of side note that this problem can be solved using linear programming, in linear time in the number of points, but doesn't describe how.

For constructing a linear program, I thought about describing lines by $F(x, y) = ax + by + c= 0$, and optimizing a function of $a, b, c$. Then the obvious constraints would be $\forall v \in V_a: av_x + bv_y + c \geq 0$ and the according thing for $V_b$, to force the lines to go between the two sets.

But now I am stuck. For one, we need to constrain the space of lines somewhat; $\lVert (a, b) \rVert = 1$ would be natural to require, but that's not linear.  Also, I'm not sure about the cost function; I thought about using

$$\min_{a,b,c} \sum_{v\in V_a} F(v_x, v_y) - \sum_{v\in V_b} F(v_x, v_y),$$

since $F$ is somehow a distance from the line (although not in the strict sense, I guess). But that is just guessing and also doesn't work -- I tried some things like I described in JuMP, but it always returned "infeasible".

How can this be formluated as a linear program? Alternatively, I can accept an algorithmic solution with linear time. Or a disproof, of course.


texts: Simulate NPDAs with DTMs using only polynomial overhead

texts:
We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$.

Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \subseteq \mathrm{P}$ and $\mathrm{CFL} \subseteq \mathrm{NP}$,
respectively. We simply use the TM tape as stack, readig and writing only at one end of the used area. The only element we can not immediately translate is transitions which push more than one symbol on the stack; for such we add intermediate states. We get a TM that stays within a constant factor both in terms of size and runtime of the original PDA.

As a follow-up to my overly optimistic answer here (thanks @A.Schulz for exposing my mistake) I wonder: can we combine the two? That is, is there a (more or less) direct simulation from NPDA to DTM?

Naive translations as the above do not work because of the blow-up needed to resolve the nondeterminism. We may be able to make use of some normal forms such as absence of $\varepsilon$-transitions (are there others?), though.


texts: A continuous optimization problem that reduces to TSP

texts:
Suppose I am given a  finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. Assuming $p_i=(x_i,y_i)$ and $x_i<x_{i+1}$, I can formalize this problem as:

 Problem 1 (edited in response to Suresh's comments) Determine  $C^2$ functions $x(t),y(t)$ of a parameter $t$ such that the arclength $ L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$  is minimized, with $x(0) = x_1, x(1) = x_n$ and for all $t_i: x(t_i) = x_i$, we have $y(t_i)=y_i)$.

  How do I prove (or perhaps refute) that Problem 1 is NP-hard?

 Why I suspect NP-hardness    Suppose the $C^2$ assumption is relaxed. Evidently, the function of minimal arclength is the Travelling Salesman tour of the $p_i$'s.  Perhaps the $C^2$ constraint only makes the problem much harder?

 Context  A variant of this problem was posted on MSE. It didn't receive an answer both there and on MO. Given that it's nontrivial to solve the problem, I want to establish how hard it is.


texts: Resolution complexity versus a constrained SAT algorithm

texts:
EDIT: ad hoc speed-ups are excluded.

We have the result that propositional resolution requires exponential time. The resolution result uses the proof of the pigeonhole principle as an example of a proof that takes exponential time.

Let's also say we have a hypothetical algorithm M for SAT that runs in polynomial time.
EDIT : M is correct, complete, sound, and general-purpose; it contains no ad hoc speed-up rules for the pigeonhole principle or any other theorem that requires exponential length in resolution. M takes its input in clausal form; we'll set up the input like a resolution proof where the consequent is negated to lead to unsatisfiability if the theorem is true. Now let's consider how the proof of the pigeonhole principle works in algorithm M with a strong condition C added:

C. We are given that M simply transforms one clause (or set of clauses) to another clause (or set of clauses). Every such transformation is logically sound.

Some questions; please point out the most fatal flaws:

Given condition C above, and since M's rule system must be finite, correct, and complete, can we conclude that there is a translation from M's rule system to an equivalent set of expansions based on resolution?
Are we now in a place where we can conclude that M would produce a computation that could be mapped by the translation in point 1 above into an impossible polynomial-time resolution proof of the pigeonhole principle?


texts: Maximize the number of edges in subgraph

texts: We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph made with vertex set $U$.


texts:
In preparation for my design and algorithms exam, I encountered the following problem.

  Given a $2  \times N$ integer  matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the maximum cost path from the top left corner $(a[1][1])$ and the bottom right corner $a[2][N]$, given the following:

$\bullet$ The path may not go through the same element more than once

$\bullet$ You can move from one cell to the other vertically or horizontally

$\bullet$ The path may not contain more than $k$ consecutive elements from the same line

$\bullet$ The cost of the path is determined by the sum of all the values stored within the cells it passes through

I've been thinking of a simple greedy approach that seems to work for the test cases I've tried, but I'm not sure if it's always optimal. Namely, while traversing the matrix, I select a the maximum cost cell on the vertical or horizontal and then go from there. I've got a counter I only increment if the current cell is on the same line with the previously examined one and reset it otherwise. If at some point the selected element happens to be one that makes the counter go over the given value of $k$, I simply go with the other option that's left.

However, I feel that I'm missing out on something terribly important here, but I just can't see what. Is there some known algorithm or approach that may be used here?

Also, the problem asks for an optimal solution (regarding temporal complexity).


texts: Optimal upper bound on the number of states in the complement of an NFA

texts:
I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.

My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.

If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?


texts: What limits the implementation of proximity operators for text indexing and searching?

texts:
I was asking on academia.se, if anyone knows scientific search engines offering a proximity operator like Google Web Search does, while Google Scholar Search does not. That's sad, because this operator would be most useful for literature research offering you a nearly semantic/context-sensitive search and I've seen requests for this feature in many blogs.

The answer on my question linked above shows that 2 search engines offer something similar, but those operators also only work on titles and abstracts of papers, if I understand correctly.

The wikipedia article doesn't explain what exactly limits the implementation of this kind of operator (exponentially rising indexing time, index size,... I'm no search algorithm expert), but when Google Web Search offers it (the amount of web-text is much bigger), what possibly hinders the scientific search engines from offering it for full article text (cost-benefit ratio? I doubt this, as 99,9% of Google Web Search user don't know the AROUND(X) operator and the majority doesn't use many operators at all)?

PS: If this question better fits SO, move it there, but I'm more looking for a general explanation, what parameters determine and limit the implementation of an proximity operator.


texts: Are there functions in the same Θ-class that are not linear transformations of each other?

texts:
looking for some help, or at least if I'm going the right direction...

  Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c_1$ and $c_2$ exist for which $f(x) = c_1 \cdot g(x) + c_2$?

I want to say that there is not, because the definition of big O states that if $f(x)$ is $O(g(x))$ then $|f(x)| \leq c_1 \cdot |g(x)|$ for all values $x > k$

and if $f(x) = c_1 \cdot g(x) + c_2$ then $g(x) = \frac{f(x) - c_2}{c_1}$

and thus $0 \leq f(x) \leq c_1 \cdot g(x)$

$0 \leq c_1 \cdot g(x) + c_2 \leq c_1 \frac{f(x) - c_2}{c_1}$

$0 \leq c_1 \cdot g(x) + c_2 \leq f(x) - c_2$

$0 \leq c_1 \cdot g(x) \leq f(x)$

Which contradicts the initial definition of $f(x)$ being $O(g(x))$.

Am I on the right path, here?


texts: Spatial data structures are part of Computational Geometry?

texts:
Are spatial data structures like BVH - Bounding Volume Hierarchy ,kD-Trees etc are part of Computational Geometry( http://graphics.stanford.edu/courses/cs268-14-fall/) or of

Data structures and Algorithms( http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/index.htm ) or of

Geometric modelling( https://graphics.stanford.edu/courses/cs348a-12-winter/ ) ?

If Spatial data structures are not part of neither of these 3, Can you tell which branch of computer science deals with the spatial data structures?


texts: Reframing decision, counting, enumeration, and search as optimization

texts:
The top accepted answers to the questions below allude to two complexity classes of optimization problems:  NPO and PO (in relation to NP and P for decision problems):

Decision problems vs "real" problems that aren't yes-or-no
Optimization version of decision problems
“NP-complete” optimization problems

The way these questions and answers are written, I get the impression that many problems such as counting, enumeration, or searching problems could be framed as general optimization problems even if their formulation does not have an explicit objective function (i.e. mathematical programming problems). Is that correct?

Take decision problems for example, one often casts decisions in machine learning (ML) as those that minimize regret, or e.g. an expected error in the evaluation against a loss function (e.g. 0/1 for decision problems).

These types of decisions or search as-optimization formulations for a wide variety of problems are fairly ubiquitous in ML.

Take some other common examples:

Find the $n$th Fibonacci term
Find the GCD of a set of numbers
Enumerate the subsets for which 3SUM answers "Yes"
Count all hamiltonian cycles in a graph
etc.

Couldn't one easily reframe many of them as optimization problems using a loss function as well? e.g. $\text{argmin}_x f(x)$, where $f$ is a measure of error defined on the solution space of the desired problem? Or is that reduction, despite its prevalence in e.g. ML, not always "easy", feasible or useful?

More generally, how does the family of complexity classes (and their associated types of reductions and definitions) for search, enumeration and counting relate to the family of their "reduction-equivalent" optimization problems?


texts: Alternative to Hamming distance for permutations

texts:
I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it would find the minimum number of translocations required to go from string a to string b.

My strings are always of the same size and I know there are no errors/substitutions.

Example:

1 2 3 4 5
3 2 5 4 1

This would give me two:

3 2 5 4 1 (start)
-> 3 2 1 4 5
-> -> 1 2 3 4 5

If this is already implemented in R that would be even better.


texts:
Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer.com/chapter/10.1007/3-540-40030-3_8 Grammar Induction as Substructural Inductive Logic Programming - if substructural Prolog is possible then one can implement substructural inductive logic programming in it (e.g. http://ilasp.com/ for the answer set version of ILP over Prolog in the non-substructural setting) and apply, e.g. in grammar induction case.

How hard the usual (e.g. SWI) Prolog should be remade to be used as substructural Prolog?


texts: Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

texts:
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the title, please tell me in your answer then I will try to make the title much clearer.
Suppose we have a list of integers $x_1, x_2,\ldots,x_n$, what we want to find is the smallest integer $y$ such that all the given integers can be found through the process of dividing $y$ by 2 (on the division tree). More specifically, the results of dividing $y$ by 2 are 2 integers: $⌊y/2⌋$ and $⌈y/2⌉$.
Example: for integers 1, 1 and 3, it is easy to prove that the lower bound of y is the sum of them, 5. As for 5, we can get all the integers we want by dividing itself: dividing 5 we get 2 and 3, where 3 is an integer we want; dividing 2 we get 1 and 1, all of which are expected results. Therefore, all the integers we want can be found in the process, 5 is the smallest integer $y$ we want.
Another example: for integers 2, 2 and 6, the lower bound of y is 2+2+6=10, but 10 is not a suitable candidate for y since 10÷2=5<6, it cannot generate 6 in the process. However, if we plus 1, then 11 is the dream y we want. An illustrational graph is shown in the link:
Notice that once we get an integer we want on the division
tree (i.e. for the 2nd example above, get 6 in a branch of 11), we should accept it as a part of the result, stop dividing it and concentrate on results on the other branch. There also could be some redundant integers generated (i.e. 1 for the 2nd example above), and we just leave them alone.
In all examples above, the smallest integer $y$ is found by trials, not a systematical algorithm. I just cannot come out with an algorithm to find $y$ systematically, and my question is how to find the algorithm.


texts: Assigning keys to the nodes of a Binary search tree given its shape

texts: Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of the keys to the nodes unique, given its shape. What is a good $O(n)$ algorithm for assigning each node its correct key? For example, the trees with $n=3$ nodes are shown below. Even if I  removed the keys assigned to each node, I could have labeled them manually. Now, I want an algorithm for this. The motivation here is that I'm obtaining a Binary search tree through some mechanism (and the tree has the right shape), but that mechanism is labeling the nodes incorrectly. See: https://math.stackexchange.com/questions/4051677/converting-a-dyck-path-to-corresponding-binary-search-tree.


texts: Maximum value of LOOP-Program turing-computable

texts:
Lets consider the class of "simple" LOOP-Programs.

A LOOP-Program P is inducively defined as:

$P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$  where $l(P_1) = l(P_2) = 1$

P: $P_1;P_2$ is also LOOP. (sequential execution of statements). The length of these programs is $l(P) = l(P_1)+l(P_2)$

P: $LOOP\ \  x_I \ \  DO  \ \ P_1 \ \ END $ (execute P a fixed amount of times, this program will execute P  exactly $x_i$ times.) The length of this program is $l(P) = l(P_1)+1 $

The input of a LOOP-Program is passed as as $f(n_1 \cdots n_k) \rightarrow x_1 \cdots x_k$ and the output is alsways stored in $x_0$

Lets further consider $S(n)$ the function which computes the maximum value of a simple LOOP-Program of maximum length $n$ with input $n$.

It is known that $S(n)$ is not LOOP-computable. ( can write proof if needed)

The question stands wether $S(n)$ is Turing-computable.

First we can note down the following theorems:

a LOOP-Program always halts after a finite amount of steps.
a function is turing-computable if a Turingmachine $M$ exists which computes $S(n)$ given the input $n$ after a finite amout of steps.

My solution to the question wether $S(n)$ is turing-computable is:

We construct a TM $M$ which enumerates all LOOP-Programs of length $n$ onto the tape.:

We know this is possible because there is only a finite amount of LOOP-Programs of length $n$ using the variables $x_1 \cdots x_{2n}$.
We will use a suitable encoding method  which encodes a LOOP-Program syntactically onto the tape.

This step of the algorithm will halt after a finite amount of steps.

Then we simulate the LOOP-Programs on the tape and write the results onto the tape. This step also terminates after a finite amount of steps.

We then have the output of every single LOOP-program of length $n$ with input $n$ on the tape and we know we can find the largest value in a finite amount of steps.

Thus $S(n)$ is computable.

My question is: does my answer hold up and can one poke any holes in this logic ?


texts: First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

texts:
I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true?

What I tried was to do both DFS and BFS on a couple of graph and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ, that's why I ask here.

Thanks


texts:
Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of [1..O(n)], preprocess $S$ so we can efficiently answer the following query:
Given an interval [i,j] output the interval from $S$ that has the longest overlap with [i,j] (i.e., their intersection is as large as possible). Note that [i,j] may or may not be one of the intervals in $S$.

It is relatively easy to get all overlapping intervals. You store an array Endpt[1..n] such that Endpt[t] equals the rightmost endpoint of all intervals in the set that begin at location t. You ask repeated Range-maximum queries on the range 1..j. As long as the answer is >j, you are getting an overlapping interval. This takes O(#answers) time since range-max is done in O(1) time.

The challenge of this question is that we want a more efficient way to find the interval with the longest overlap. To this end, we can consider 3 cases:

intervals that begin before i
intervals that end after j
intervals that begin after i and end before j (i.e., that are contained within [i,j]).

For case 1, we can query Endpt array for range-max in the range 1..i-1 and find the longest overlapping interval of type 1 efficiently.
Similarly, for case 2 we can store a Startpt array and query for range min.

Case 3 has me stumped.  We could store a length array for all intervals, and ask for the range-max in i..j; however, this will not give the longest overlapping interval, since there will be intervals that begin after i and end after j.  Is there a way to efficiently preprocess $S$ so that, given [i,j], we can efficiently find the longest interval contained within [i,j]?  Or is there some other efficient way to solve the original problem?


texts: Context-free language and regular expressions

texts:
I have the following context-free language:

S -> ASa | b
A -> aA | a

I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -> ASa | b
A -> aA | e

e stands for the empty string. I don't understand their differences.


texts: Problem in understanding approach of binary search w.r.to question

texts:
Monk and his best friend Micro were taking a stroll, when they found an array A having N integers lying on the road. The array was injured badly, so they took it with them and treated it.

When the array came back to senses, it told them, that some crazy guy came and started beating it. The array started crying and while Monk and Micro were comforting it, the last element of the array informed that the special integer is missing from its pocket. After hearing that, the array started crying even louder because it is supposed to appear in the next Code Monk Challenge with that Special Integer.

Special integer, K, of an array, is an integer such that none of its subarray of size K has sum of elements greater than X. To calm the array down, Monk decided to gift it the maximum possible value of special integer K. Now since Monk is busy with Code Monk he asked Micro to find the maximum value of special integer but right now, all Micro can think of is a Potato, so Micro asked for your help.

Input Format:
First line consists of two space separated integers denoting N and X.
Second line consists of N space separated integers denoting the array A.

Output Format:
Print the maximum possible value of special integer.

sample input:

4 8

1 2 3 4

sample output

2

Above question is on hackerearth:
https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/monk-and-special-integer-code-monk/description/

I am not able to get the approach, even editorial is mentioned, and this is to be solved by binary search. What I understood was it was solved using sum of preceding values and comparing but still not very clear, please help


texts: Converting a 32-bit bit pattern into floating point number

texts:
In The Scientist and Engineer's Guide to
Digital Signal Processing
By Steven W. Smith, Ph.D. i have read something like that,

Single precision or 32-bit floating point forms the floating point number, $v$, by the following relation:
$$ v = (-1)^S \times M \times 2^{E-127} $$

The term: $(-1)^S$, simply means that the sign bit, $S$, is $0$ for a positive number and $1$ for a negative number. The variable, $E$, is the number between $0$ and $255$ represented by the eight exponent bits. Subtracting $127$ from this number allows the exponent term to run from to In other words, the exponent is stored in offset binary with an offset of $127$.

Everything I have understood but this,

  Subtracting 127 from this number allows the exponent term to run from 128 to −127. In other words, the exponent is stored in offset binary with an offset of 127.

I need an easy to understand explanation of subtracting 127 from $E$ and binary offset.


texts:
Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow can be found?

It seems that the Dinic Algorithm will accomplish this $O \left( m n^{2/3} \right)$ where $n$ is the number of nodes and $m$ is the number of vertices. From table 1 in this paper, it seems reasonable to guess this was still the state of the art in 2001. Is this the best that is currently known?


texts: Context-free grammar of the concatenation of a string S and subsequence of reversed S

texts:
I have to find a Context-Free grammar that generates the language:

$L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$

The concatenation of two mutually reversed strings are pretty simple, but I just can't figure out how to express "plugging in random terminals in $x$" so that $x^R$ could contain $y$ as its subsequence.


texts: Clock page replacement policy vs LRU page replacement policy, is Clock more efficient?

texts:
I'm currently learning about database systems and they mention a buffer management system which brings in pages from disk to memory. This buffer manager allows higher layers to operate as if the entire database on disk is actually in memory.

The video I am watching talks about LRU and Clock as the page replacement policies when a page doesn't exist in the buffer pool.

However what I am confused about is that this video mentioned that LRU was log n in efficiency, but Clock is a better algorithm.

Specifically, imagine the buffer pool being a hash table with page id as the key. The value is dependent on if we are doing LRU or Clock.

If LRU was implemented with a heap data structure, maintaining this structure would be O(log n). ie A read of a page is constant to see if it's in the hash table. If it is, the value points to somewhere on the LRU data structure, which needs an update since the 'last used' time has changed. This means every read, updates the LRU so this is O (log n).

For a clock page replacement policy, modifying a page's last used bit to 0 is constant time, because the page id is a key in the hash table and modifying it's value is O(1).

However for a clock replacement policy, finding a page with a last used bit = 0 requires scanning the buffer pool. That is o(n). For LRU, we just grab the root node which is O(1) and delete it which is log(n) and insert a new node which is log(n). So LRU should be O(log n) to replace a page.

So I'm confused why people would use a Clock page replacement policy and believe it is better than a LRU page replacement policy? Did the educational video I watch make an error in stating Clock is more efficient?

Or am I missing something?


texts: Removing left factoring from Context-Free Grammar

texts:
I know that, removing left factoring is a simple task.
And i understand following procedure:

$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$

Yet I'm running into problems with this particular grammar:

$S→AD|bbS|bScS|BS $
$A→aAbb | abb$
$B→aB|ba|b$
$D→cDd|cccd$
How to remove left factoring from it, I'm trying to convert  it into LL(1) grammar


texts: Databases - How to generalize an sql query from a specific input? find project number, number of employees

texts:
Schema:
http://comet.lehman.cuny.edu/jung/cmp420758/DBMidexamFa14-SelectedSolution.pdf

Write SQL code to find the following details:
For each project: find the project number and the number of employees who do not work on the project but who work on a different project controlled by the same department.

Edit:
Here is my solution so far.

In the relation PROJECT, observe that each dnum has multiple pnumber's but each pnumber can only have one dnum. i.e. there are several projects per department but only one department for a project.

For a fixed project, say pnumber = 1, we can find other pnumber's in the same department excluding the fixed pnumber.

SELECT pnumber FROM PROJECT WHERE dnum IN (SELECT dnum FROM PROJECT WHERE pnumber=1) and pnumber NOT IN (1);

Now, we can find the number of employees who work in the pnumbers listed in the query above using the relation WORKS_ON(essn, pno, hours). An essn is a foreign key for each employee.

SELECT count(*) from WORKS_ON WHERE pno in (...above query...);

This is where i'm stuck. In my example i can only find the project number and the number of employees who work in other projects in the same department for a given pnumber only. However, I can't think of a way to produce a table that runs the same algorithm for every single pnumber. Perhaps my approach might be wrong or I am unaware of an sql function that can do this.

Questions:
1) How can I generalize my sql to generate the same result for ALL pnumbers, not just pnumber = 1?
2) For the first section of my code, is there a cleaner/faster way to find all other projects in the same department, given a fixed project? It seems a bit inefficient at the moment, having to nest 2 select queries and adding more select queries later on.


texts: Is There A Difference Between Search And Optimization?

texts:
Is one a subset of the other? Two differentiable processes? The same thing?

In the textbook "AI: A Modern Approach", the terms seem to be used interchangeably.


texts: Prove np-hardness of dividing items from the lists

texts:
I have the following problem.

Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with 3 colors, such at least two colors appear in each list.

I would like to show that this problem is NP-hard. I would like to provide reduction from the 3-coloring problem which seems to be similar.

I think I could make items as nodes and link every item with every other from the shared lists, but then the condition of 3-coloring would be too demanding in comparison to my problem. What should I do differently in order to create the reduction?


texts: Are there any algorithms or researches on finding local alignments in partially ordered sequences?

texts:
The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of information on that.

However, recently, I had to tackle a problem in which sequences had partial orders - meaning that some parts of the sequences (if you can even call it that) was not imposed a strict restriction of ordering.

For example, we could have a protein sequence of GAC(AG)TT, where the brackets denote that any elements within them can be freely reordered. Hence, the sequence can be viewed as either GACAGTT or GACGATT.

A naive way to approach the problem is to compare all possible configurations of sequences, but the problem size becomes exponentially larger as the number of brackets (clusters of freely interchangeable elements) and the numbers of elements in each bracket increase.

I have tried looking up in algorithm textbooks, googling in general webpages and publications, but I could not find the slightest hint of such problem. It seems very peculiar (or very unlikely) that such a general problem has not been mentioned anywhere until now. So please, could anyone here shed some light on my question? Thank you.


texts: Functionning of the eviction set for Prime and Probe

texts:
I have to write a report about Prime and Probe, more specifically about its eviction set method, and there are two notions that remain blurry for me :

To find the set, we use huge pages like it's described in the second link but I don't understand what the '2MB page offset' corresponds to. And why does the physical address of the huge pages contains the organization (6bits for the offset, 12bits for the set index) of the small pages (link 1) ? Are there two different types of offsets ?

To find addresses of the same slice we use the method described in the link overhead but I don't understand why :

Between the steps 2 to 4 why is x evicted, if x is still in the S set it could remain in it when we access the whole set and in this case it wouldn't be evicted when we evict it again after that ?
And if we remove an address from the same slice (in step 5), then all the addresses of the other slice remain so shouldn't they evict the x ?

Sorry for the confused way I must present my questions but thank you for the help :)