texts: Data structure for efficient group lookup

texts:
I need a data structure, which allows efficient queries for 'give me the group of x'.
Let me give you an example:
Group 1: [a, b, c]
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -> [d, e]

There are no significant constraints on storage or construction time. I only need getGroupOf to be O(logn) or faster.
I am thinking about using a Dictionary<Element, Set<Element>> where entries for all elements in a group share the same set reference. This would make lookup effectively O(1) or O(logn) depending on the dictionary implementation, but would result in a lot of entries.
This feels fairly bloated, and I am wondering: is there is a more elegant data structure to accomplish this?
Edit: the elements in a group can be completely arbitrary and they have no ordering.


texts: Counting the number of permutations of string with given repeated interwoven subsequence

texts:
Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence.

Example. $S=abc$. There are 5 permutations: $abcabc$, $abacbc$, $ababcc$, $aabcbc$, $aabbcc$.

If each character of $S$ appears only once, the problem becomes easier. Consider all binary strings of length $2n$ with $n$ zeros and $n$ ones. Zeros represent the first subsequence and ones represent the second subsequence. Whenever there is a binary string with some prefix that contains more ones than zeros, we may repaint the binary string in a way that both the original binary string and the repainted binary string represent the same permutation, and that no prefix of the repainted binary string has more ones than zeros.

Therefore we may restrict ourselves to the binary strings where for each prefix the number of zeros equals or is greater than the number of ones. Because each character of $S$ appears only once, each such binary string represent a distinct permutation. There is a simple recursive method to generate such binary strings, and by applying dynamic programming it is possible to calculate $P_n$ in $O(n^2)$ time. Apparently for this special case $P_n$ eqals the n'th Catalan number $C_n$, so it should be possible to get it done with $O(n)$ multiplications.

When some characters of $S$ appear more than once, or there are common substrings, $P_n<C_n$. For $S=aaa$ the number is 1, for $S=aab$ it is 3, and for $S=aba$ it is 4. So now my questions are:

How to find $P_n$ in a way that is faster than generating all $C_n$ permutations and counting the unique ones?
The general case. Given $S$,$n$,$k$, count the number of distinct permutations of a string of length $kn$ such that each of them contains $S$ $k$ times as an interwoven subsequence. How to do this faster than generating all the plausible permutations and counting the unique ones?


texts: To calculate how many times a certain year repeats itself in the calendar within a given year range

texts:
Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $[A, B]$.

Is there any method to it without brute force, in a pretty efficient way?

NOTE: I'm talking about the Gregorian Calendar.


texts: Longest path in a strongly connected component

texts:
So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.
My idea is: In a strongly connected component we can get from one vertex to every other vertex.
If we start at some vertex u then we can visit each of the remaining n-1 vertices by going from the vertex we are currently on to some adjacent vertex, setting the vertex we reach as the current one and repeating until we have no unvisited vertices left. As such the longest path always has length n-1.
Another idea is that we can run depth first search on the connected component and the highest level found will be the length of the longest path.
Intuitively these ideas make sense to me but not sure how to structure them formally or even if they are right. Could I get some guidance on this?


texts: Regular language is generated by clear grammar

texts:
Given a regular language , how could we prove that it is alsways ( or can be always ) generated by clear grammar ( such as that for every sentence exists only one derivation tree ).

Could we prove it by creating minimalistic deterministic automata without epsilon transition ?


texts: Is NP-complete complexity defined in terms of polynomial reductions or polynomial transformations?

texts:
How do you know that a decision problem $X$ is NP-complete?, if all other NP-problems polynomially transform to $X$ or if all other NP-problems polynomially reduces (there exist a polynomial time oracle for any problem in NP using an oracle for $X$).

Definitions seem to differ all over the web.
Thanks!


texts:
I need to solve the following recurrece:

$T(n,m)=\begin{cases}
1, & m\leq 2(n-1)!\\
\min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else}
\end{cases}$

Note: in the first line beneath the $\min$ we have $a,b$ and in the next line it's $a\cdot b$.

I find it difficult to solve this recurrence as it contains $\min$, so I tried to calculate the minimum, but I didn't know how to prove it (I believe that the minimum occurs at $a=b=\sqrt{(n-1)!}$, but I don't know how to prove it...). So I am stuck with this.

Any help would be highly appreciated!

Edit:

Experiments show that

$T(n,m)=\begin{cases}1 & f(n,m)\leq 0\\ 3+2\Big\lfloor\frac {f(n,m)-1}{(n-1)!}\Big\rfloor & \text{else}\end{cases}$

for $f(n,m)=m-2(n-1)!$, and considering the $\min$ of an empty set to be infinity.


texts: Will MST find the shortest path for each pair $(r,v)$?

texts:
Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes A,B and thus would make the path from root to A and B respectively not the global minimum?

This is Prim's algorithm, at page 634 (655 is pdf reader page):

While this is Dijkstra, at page 658 (679 is pdf reader page):

Book: Introduction to Algorithm 3ed.


texts: What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

texts:
Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with Dijkstra's algorithm using Binary Heap ?

To clarify, Dijkstra's algorithm is run from the source and allowed to terminate when it reaches the target. Knowing that the target is a neighbor of the source, what is the time complexity of the algorithm?
My idea:
Dijkstra's algorithm in this case makes $O(n)$ inserts ( $n$ if the graph is complete) and 1 extract min in the binary heap, before calculate the shortest path from $u$ to $v$.
In a binary heap insert costs $O(\log n)$ and extract min $O(\log n)$ too.
So the cost in my opinion is $O(n \cdot \log n + \log n) = O(n \log n)$
But the answer is $\Theta(n)$, so there is something wrong in my thinking.
Where is my mistake?


texts: Recursive, Recursively Enumerable and None of the Above

texts:
Let

$A = \mathrm{R}$ be the set of all languages that are recursive,
$B = \mathrm{RE} \setminus \mathrm{R}$ be the set of all languages that are recursively enumerable but not recursive and
$C = \overline{\mathrm{RE}}$ be the set of all languages that are not recursively enumerable.

It is clear that for example $\mathrm{CFL} \subseteq A$.

What is a simple example of a member of set B?

What is a simple example of a member of set C?

In general, how do you classify a language as either A, B or C?


texts: What are some of the simplest applications of heavy hitter problem?

texts:
I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity.

I want to know what are some of the basic applications of HH problem.


texts: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs

texts:
I'm trying to solve a problem for class that is stated like so:

  A bipartite graph is an undirected graph in which every cycle has even
  length.  We attempt to show that the Hamiltonian cycle (a cycle that
  passes through each node exactly once) problem polynomially reduces to
  the Hamiltonian cycle problem in bipartite graphs. We need a function
  $T:  \{\text{graphs}\} \to \{\text{bipartite graphs}\}$ such that $T$ can be computed in
  polynomial time and for any graph $G$, $G$ has Hamiltonian cycle iff $T(G)$
  has a Hamiltonian cycle. Let $T(G)$ be the bipartite graph obtained by
  inserting a new vertex on every edge. What is wrong with this
  transformation?

I think the problem with the transformation is that for $T(G)$ you need to insert an edge between each pair of vertices and not just insert a new vertex on every edge. I'm actually a bit stumped by this one. Any advice would be much appreciated!


texts:
I have following grammar:

$$A \to a A a \mid \varepsilon$$

This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a shift-reduce conflict in LR(1) on this grammar.

Why does there exist an conflict even though it is not ambiguous grammar?


texts: Calculator for time complexity of recursive functions

texts:
Is there an online tool that returns the time complexity of recursion functions?
For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$.
I tried using Wolfram Alpha, but it doesn't return the above result I was looking for.


texts: How many restricted length strings are there without significant repetitions


texts:
I have spent an hour finding the answer to this problem but can't do it, this is the problem:
Determining whether the following semantic entailment holds or not by using the tableau algorithm
∀a∀b∀c((R(a,b) ∧ R(b,c)) → ¬R(a,c)) ⊨ ∀a¬R(a,a)


texts:
Let $\to_\beta$ be $\beta$-reduction in the $\lambda$-calculus. Define $\beta$-expansion $\leftarrow_\beta$ by $t'\leftarrow_\beta t \iff t\to_\beta t'$.

Is $\leftarrow_\beta$ confluent? In other words, do we have that for any $l,d,r$, if $l \to_\beta^* d\leftarrow_\beta^* r$, then there exists $u$ such that $l\leftarrow_\beta^* u \to_\beta^* r$?

Keywords: Upward confluence, upside down CR property

I started by looking at the weaker property: local confluence (i.e. if $l \to_\beta d\leftarrow_\beta r$, then $l\leftarrow_\beta^* u \to_\beta^* r$). Even if this were true, it would not imply confluence since $\beta$-expansion is non-terminating, but I thought that it would help me understand the obstacles.

(Top) In the case where both reductions are at top-level, the hypothesis becomes $(\lambda x_1.b_1)a_1\rightarrow b_1[a_1/x_1]=b_2[a_2/x_2]\leftarrow (\lambda x_2.b_2)a_2$. Up to $\alpha$-renaming, we can assume that $x_1\not =x_2$, and that neither $x_1$ nor $x_2$ is free in those terms.

(Throw) If $x_1$ is not free in $b_1$, we have $b_1=b_2[a_2/x_2]$ and therefore have $(\lambda x_1.b_1)a_1=(\lambda x_1.b_2[a_2/x_2])a_1\leftarrow(\lambda x_1.(\lambda x_2.b_2)a_2)a_1\rightarrow (\lambda x_2.b_2)a_2$.

A naive proof by induction (on $b_1$ and $b_2$) for the case (Top) would be as follows:

If $b_1$ is a variable $y_1$,

If $y_1=x_1$, the hypothesis becomes $(\lambda x_1.x_1)a_1\rightarrow a_1=b_2[a_2/x_2]\leftarrow (\lambda x_2.b_2)a_2$, and we indeed have $(\lambda x_1.x_1)a_1=(\lambda x_1.x_1)(b_2[a_2/x_2])\leftarrow (\lambda x_1.x_1)((\lambda x_2.b_2)a_2)\rightarrow (\lambda x_2.b_2)a_2$.
If $y_1\not=x_1$, then we can simply use (Throw).

The same proofs apply is $b_2$ is a variable.
For $b_1=\lambda y.c_1$ and $b_2=\lambda y.c_2$, the hypothesis becomes $(\lambda x_1.\lambda y. c_1)a_1\rightarrow \lambda y.c_1[a_1/x_1]=\lambda y.c_2[a_2/x_2]\leftarrow (\lambda x_2.\lambda y.c_2)a_2$ and the induction hypothesis gives $d$ such that $(\lambda x_1.c_1)a_1\leftarrow d\rightarrow (\lambda x_2.c_2)a_2$ which implies that $\lambda y.(\lambda x_1.c_1)a_1\leftarrow \lambda y.d\rightarrow \lambda y.(\lambda x_2.c_2)a_2$. Unfortunately, we do not have $\lambda y.(\lambda x_2.c_2)a_2\rightarrow (\lambda x_2.\lambda y.c_2)a_2$. (This makes me think of $\sigma$-reduction.)
A similar problem arises for applications: the $\lambda$s are not where they should be.


texts:
I've converted an NFA to a DFA.  But even after checking over it a few times, it still doesn't feel right.  I'm sure this is trivial, but I'd like someone to give me an idea where I went totally wrong on this.

NFA:

DFA:


texts: Data structure with insert, and delete-min (or max) in $O(1)$?

texts:
Is it possible to have a data structure that supports both insertion and delete-min  (or max) in $O(1)$?

You can assume the numbers that will be inserted are integers in the range [0,n] and that you will be inserting a maximum of n elements.


texts: LTL to automaton translation that can only read disjunctions of labels per transition

texts: Is there any automaton (or automaton translation) as expressive as LTL that can only read disjunctions of atomic propositions per each transition? Standard LTL-to-automaton algorithms allow the automaton to read conjunction as well as disjunction of atomic propositions.


texts: Is finding a single digit of a computation is as hard as finding the computation?

texts:
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages:

$$\begin{align*} L_1 &= \{ n \mid f(|n|) = n \} \\
L_2 &= \{ (n,k) \mid \text{the first digit of $n$ is the $k$'th digit of $f(|n|)$} \}\end{align*}$$

Are infinite.

Prove or disprove that $L_1 \leq_{P} L_2$ i.e there is a polynomial time reduction from $L_1$ to $L_2$.

Heuristically I am thinking that for any function it is impossible to compute a digit of the computation without generally computing the function so I am thinking it should be correct, though not sure how to prove it formally.


texts: Where are the address, control and data buses on a computer

texts:
So have been reading up on data buses, address buses and control buses and I understand what they do, but am confused about where they can physically be found. Some books/sites I have found state that they are inside of the CPU, some state that they transmit data all over the computer. E.g. the control bus can send signals to any other device within the computer, but then another book states that the control bus is inside of the CPU and synchronises the components of the CPU.

Can anyone help clarify this please?


texts: How to deal with character set in regular expression?

texts:
In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit or \w to represents word character.
I wonder how they are converted to DFA, since you cannot really create expand edges in alphabet(Unicode).

Take example as: x(2|\d)*y.
The dfa is generated as the following graph.

Apprently 2|\d is the same as \d, the edge '2' is not necessary since it is contained in '\d'. But DFA cannot realize it.

Is there any way to reduce such kind of redundancy?

It also seems regular expression compression becomes very difficult. If we don't expand \d to 0|1|2...|9
E.g. we can hardly say is \w+ equals a*\w+b* or not.

And does those regular expression implemention (e.g. re package in python) consider the redundancy?


texts: Tasks in which recursion is either the fastest or only way to produce a result

texts:
I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be performed faster, and in less code, using iterative means.
This was something the lecturer confirmed.

Could somebody please give me some examples of situations when recursion is a better solution than iterative techniques? Additionally, are there any situations in which recursion is the only way to sole a problem?


texts: Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid

texts:
An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:

the endpoints of the arc associated to an edge e are the points
associated to the end vertices of e,
no arcs include points associated with other vertices,
two arcs never intersect at a point which is interior to either of the arcs.

Two embeddings of a planar graph in the plane are called equivalent for every vertex of the graph the cyclic order of the incident edges is the same in both embeddings.

I am looking for a reference which shows that any Jordan arc embedding of a planar graph can be equivalently embedded as a straight line drawing with the $n$ vertices of the graph lying on the vertices of an  $O(n) \times O(n)$ grid. (Certainly any planar graph can be embedded with its vertices on the vertices of such a grid but I'm looking for an embedding that's equivalent to the originally given one.) Schnyder's algorithm seems to produce an embedding equivalent to the topological embedding given as its input but I've not managed to find a proof of this.

Does anybody know of such a theorem?


texts: Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

texts:
If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?
If it is true how to prove it?

Update

It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then $A$ is recursive. but by $A \leq_m\bar{A}$ I can't deduce that $\bar{A}$ is r.e.


texts: Unary function is partially n-computable

texts:
Please help me prove the following problem:
A unary function $f(x)$ is said to be partially $n$-computable if it is computed by some $\mathcal{S}$ program $\mathcal{P}$ such that $\mathcal{P}$ has no more than $n$ instructions, every variable in $\mathcal{P}$ is among $X, Y, Z_1, . . . , Z_n$ and every label in $\mathcal{P}$ is among $A_1,...,A_n,E$. Prove that if a unary function $f : N \rightarrow N$ is computed by a program with no more than $n$ instructions, then $f$ is partially $n$-computable.
This problem is in Chapter 2, Section 4 of Computability, Complexity, and Languages by M.Davis.
I am quite confused by this problem because the statement at the beginning and the question that needs to be proved are just two ways of saying the same thing. The statement is "q if p" and the question is "if p then q" which both mean "p implies q". So I totally don't understand what is asked to be proved here.


texts:
I was reading the book by Jurafsky and this is written by the author on HMM

Although in principle the forward-backward algorithm can do completely unsu-
pervised learning of the A and B parameters, in practice the initial conditions are
very important. For this reason the algorithm is often given extra information. For
example, for HMM-based speech recognition, the HMM structure is often set by
hand, and only the emission (B) and (non-zero) A transition probabilities are trained
from a set of observation sequences O.

My question is, what exactly is the author trying to say? What is the extra information given? And in the example, I don't see any extra information. What does it mean to set the HMM structure by hand?


texts: Figuring out whether LL(1) grammar has an $\varepsilon$-free variant

texts:
This question arose out of a concrete problem I had, which was to find an $\varepsilon$-free variant of the following LL(1) grammar $G_0$ that I developed for a Lisp-like language $L$ (I found a monotone LR(0) variant):

$$
\begin{array} \\
P & \rightarrow & (EP \\
  & | & \varepsilon \\
E & \rightarrow &iE \\
  & | &sE \\
  & | &nE \\
  & | &(EE \\
  & | &)
\end{array}
$$
where the start symbol is $P$. With this grammar, the leftmost derivation of $\omega = (i()sn)(inn)$ is
$$
\begin{array} \\
P & \Rightarrow_L (EP \\
  & \Rightarrow_L (iEP \\
  & \Rightarrow_L (i(EEP \\
  & \Rightarrow_L (i()EP \\
  & \Rightarrow_L (i()sEP \\
  & \Rightarrow_L (i()snEP \\
  & \Rightarrow_L (i()sn)P \\
  & \Rightarrow_L (i()sn)(EP \\
  & \Rightarrow_L (i()sn)(iEP \\
  & \Rightarrow_L (i()sn)(inEP \\
  & \Rightarrow_L (i()sn)(innEP \\
  & \Rightarrow_L (i()sn)(inn)P \\
  & \Rightarrow_L (i()sn)(inn)
\end{array}
$$
My problem is that the parser generated by this grammar accepts the empty string, and I would like to exclude that.
So I am looking for an $\varepsilon$-free LL(1) grammar $G_1$ that generates $L-\{\varepsilon\}$. I have tried several times without success, leading me to doubt whether $L-\{\varepsilon\}$ is simple deterministic.


texts: How would a CPU designed purely for functional programming be different?

texts:
CPU's are to an extent designed with in mind the software that people will write for it, implicitly or explicitly.

It seems to me that if you look at the design of instruction set architectures, they are very "imperative", in the sense that each instruction encodes an imperative style command. It also seems to me that the current instruction set architectures have evolved partly based on the type of code programmers produce.

If one would design a CPU from scratch, knowing that it would only ever run programs written in a functional programming style, how would that CPU be designed differently from existing CPU's?


texts:
Let's say we have a simple connected and undirected graph $G(V,E)$. The game is played with two players. For each game, player A starts at a node $t$, and player B at a node $v$. There is also a node $d$ which is the same for every game.

In the game, player A always plays first. His goal is to reach node $d$ before player B reaches him (player B can't go to node $d$). Player B's goal, on the other hand, is to reach the node where A is. If players A,B have been in nodes $x,y$, respectively, in a previous round, and these positions are repeated again, the match ends in a tie.
In every round the player which has priority must move to a neighboring node.

What I need is to make an algorithm that gives as output the result of this game for every possible starting combination $t,v \in V$ (where $t\ne v$).

What I've done so far is a dynamic programming $O(|V|^3)$ solution. We can record all possible states of this game as (position of player A, position of player B, next player to move), and find all the possible resulting states for every state.

Could this be done any better?


texts: Cook–Levin theorem and reduction as injective function

texts: I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?


texts: Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

texts:
Let $\mathcal C$ be a circuit of $m=f(n)$ input wires

where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily needs to be utilized if $f(n)=o(n)$)

where every layer of the circuit is all $AND$ or all $OR$ gates having fan-in $2$ and fan-out $1$, and the AND and OR layers alternate

depth of the circuit is $\leq\log^kn$ at a $k\geq0$

(essentially an $NC^k$ circuit having gates of fan-out $1$).
The question is whether $\exists x_1,\dots,x_n\in\{0,1\}:\mathcal C(x_1,\dots,x_n)=1$.
Usual $NP$-completeness is for $CIRCUITSAT$ where depth can be $poly(n)$ without restricting to fan-out $2$ and fan-in $1$. If depth is $k=O(\log n)$ do we still get $NP$-completeness if gates are fan-in $2$ and fan-out $1$ and number of input wires $poly(n)$?

Is it $NP$-complete at all fixed $k\geq1$ if $f(n)=poly(n)$?

If $k=0$ the problem is in $P$ because the number of input wires is $O(1)$.

Is there a complexity class for the problem if $0<k<1$ holds?


texts: $\epsilon$ - Nash Equilibrium exceeds Nash Equilibrium

texts:
I wonder if there exists a game in which $\epsilon$ - Nash equilibrium leads to a much higher payoff than any other Nash equilibrium.

Show, for every $\epsilon$ > 0, a two player game where there is an $\epsilon$-Nash equilibrium in which  both players have a much higher payoff then in any Nash equilibrium.

What is $\epsilon$ Nash - equilibrium.$\sigma$ is $\epsilon$-Nash equilibrium, if $ u_i(\sigma) \geq u_i(\sigma_i, \sigma_{-i}) - \epsilon, \forall \sigma_i \in \Delta(S_i), \forall i \in N$.

It sounds very counter-intuitive, in other word I have to show the game where $\epsilon$ - Nash equilibrium, which is according to the definition not the best strategy to play indeed leads to the best payoff.

Could you give such en example?


texts:
Why is $\text{BPP}=\text{co-BPP}$?
I tried to find a proof online but couldn't.
Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to a proof?


texts: Applying SVD compression to integral point images

texts:
Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular values to construct the the best rank-$k$ approximation of $A$ to accomplish compression for data storage.

I understand that for a floating-point image, the compression rate for SVD is

$$\frac{mn}{k(m+n+1)},\tag{1}$$

as mentioned in a lot of places including some textbooks. For example, a quick internet search gives us this article and this convenient demo link.

Coming back to our case, the entries of $A$ are 8-bit unsigned integers, while we still need to use floating points (32 bits or 64 bits) for the storage of the singular values and vectors (because 8-bits do not seem enough for the precision), it would seem that the compression rate for this case should become

$$\frac{mn}{4k(m+n+1)}, \quad\text {or} \quad \frac{mn}{8k(m+n+1)}.\tag{2}$$

This would render this compression scheme not practical in most cases. For example, using the demo link above, for that default image there, we need at least the first 100 singular values for a less-than-satisfactory compressed image. Using Formula $(1)$, that is assuming the original image is using the floating point data type, the compression rate is $2.40$; but assuming the original image is using the 8-bit unsigned integer data type, using Formula $(2)$, the compressed image becomes at least $0.6$ times bigger than the original one.

Does SVD compression only work for floating point images? What am I missing here?


texts: Why 'let' can not be reduce to a lambda application in (extended) Calculus of Constructions

texts:
I do not understand the difference highlighted in the chapter 2.5 of the book Theorem Proving in Lean:

  Notice that the meaning of the expression let a := t1 in t2 is very similar to the meaning of (λ a, t2) t1, but the two are not the same. In the first expression, you should think of every instance of a in t2 as a syntactic abbreviation for t1. In the second expression, a is a variable, and the expression λ a, t2 has to make sense independently of the value of a. The let construct is a stronger means of abbreviation, and there are expressions of the form let a := t1 in t2 that cannot be expressed as (λ a, t2) t1. As an exercise, try to understand why the definition of foo below type checks, but the definition of bar does not.

def foo := let a := nat  in λ x : a, x + 2
def bar := (λ a, λ x : a, x + 2) nat

What is the explanation behind this?


texts: generic technique to build LTL/CTL formula that satisfy specific inputs to a model

texts:
I have an automaton, for example the below automaton and would like to generate a single formula (LTL or CTL, or some other representation) that satisfy exactly the traces provided. e.g.,

$t_1 = i^*f_4f_5f_7f_8f_7f_5f_4i^+$

$t_2 = i^*f_4f_6f_7f_9f_7f_6f_4i^+$

$t_3 = t_1^*t_2^*t_1^*$

$T = \{t_1 ...t_x\}$

I may have the notation wrong here, what I am trying to express is that any combination of $t_1$ and $t_2$ is acceptable, so long as INIT is visited between each. There could be any number of $t_x$, but they will all be known.

for example the traces

$i^*f_4f_5f_7f_9f_7f_5f_4i^+ \not\in T$ and

$i^*f_4f_5f_7f_8f_7f_5f_4f_5f_7f_8f_7f_5f_4i^+ \not\in T$ and

$i^*f_4(f_5f_7)^+ \not\in T$

Is there a technique of building a single formula(LTL, CTL, etc) $\psi$ such that $t \models \psi \iff t \in T$


texts: What do "patterns, which separately match parts of a page" and "interactions between patterns" mean?

texts:
Database System Concepts by Abraham Silberschatz, Henry F. Korth and S. Sudarshan says

  Information extraction using simple patterns, which  separately
  match parts of a page, is relatively error prone. Machine-learning techniques
  can perform much more sophisticated analysis, based on interactions between
  patterns, to minimize errors in the information extracted, while maximizing the
  amount of information extracted.

What do "patterns, which  separately match parts of a page" and "interactions between patterns" mean respectively?


texts:
Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to one of the numbers $\{p-1,p,p+1\}$. Am I correct?

I've been struggling to reduce standard Subset-sum to this variation, but for no good so far. Can you see any other reduction? Or could give me a hint on this  one? Perhaps I'm fixed for that Subset-sum and don't some other obvious possibility.


texts:
Consider a graph $G$ with minimum degree $d$, we know through sets cover, it's possible to find the one dominating set $S$ that covers $G$ such that $$S\leq O(\log n)\frac{n}{d}
$$ with high probability, But is it possible to find a deterministic algorithm that achieves this bound in polynomial time?


texts: Mapping several memories to one address space

texts:
I am trying to understand deeply how memories work in computers, and I faced the next difficulty.

Let's say we have a device with two memory chips but only one address space (for example, 0x00000000 to 0x10000000 will be memory1 and 0x10000000 to 0x20000000 will be memory2). In case an assembly code does a load/store instruction to memory2 to the address 0x10000004, who's responsible it is to change the address so it will be absolute to the memory chip?
I assume that the memory chip doesn't know it's relative address space, and in our example memory2 expects a load/store from/to 0x00000004.


texts: Figuring out when one algorithm will be slower than another algorithm

texts:
I'm studying for a computing exam and came past the following question on a past paper and need help with it.

When would algorithm A be slower than algorithm B? Demonstrate your answer with the help of an example. Also what will the value of SUM be at the end of each algorithm if the size is set to $10'000$?

Algorithm A:

SET sum TO 0
FOR i=1 to size
  FOR j=1 to 10000
    sum=sum+1

Algorithm B:

SET sum TO 0
FOR i=1 to size
  FOR j=1 to size
    sum=sum + 1

I came up with this answer but not sure if it is correct:

The algorithm A will be slower than algorithm B when the performance of the algorithm is directly proportional to the cubed or more of the size of the input data set, for example if the Big O notation becomes $O(N^3)$ or $O(N^4)$ or $O(N^5)$ etc. The Big $O$ notation $O(N^3)$ nesting the for loops in two more for loops:

Set Sum TO 0
For i=1 to size
  For k=1 to size
    For l=1 to size
      For j=1 to 10000
sum=sum+1


texts: Prefix/suffix property of language containing only empty word

texts:
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?

The definition says that language has prefix/suffix property requires that there is no code word in the system that is a prefix (initial segment) of any other code word in the system.

So if we have this finite language with $\varepsilon$ this mean that, there arent any prefix/suffix of empty word so our language has or not prefix/suffix property?


texts: Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

texts:
The protocol is defined here, but I'll give a summary here.

Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, something that can optionally benefit everyone once constructed.) It costs $P$ to construct this good. The agents each give an interval that they are willing to pay. Agent $i$'s interval is $[m_i,M_i]$. (In the case of a rational agent, $m_i=0$, but if the agent is somewhat altruistic, $m_i>0$. It has been proven that $M_i$ will always be how much value a rational agent $i$ expects to extract from the public good.)

Now, in this protocol, each person pays the same price $p$, or $m_i$, whichever is greater, or pays nothing at all if $p > M_i$. (Those who pay get access to the good, those who don't are excluded from the good.) What I am trying to do is find the minimum $p$, such that the total amount paid (let's call it $F(p)$) is equal to or greater than $P$, efficiently.

If all $m_i$ are $0$ and there are $n$ agents, I can do it $\mathcal O(n \log n)$. I first sort the agents by $M_i$. Then starting with the agent with least $M_i$, I figure out how much funds will be available with $p=M_i$. If $F(M_i) \gt P$, than $M_i$ is the minimum $p$. Otherwise, we go to the next agent, and so on. $F(M_i)$ can be calculated in $\mathcal O (n)$, by multiplying $M_i$ by how many agents come after (or are) agent $i$ (for each agent $j$ that comes after $i$, $M_j \ge M_i$. Since $p=M_i$, not $p>M_j$, and agent $j$ pays $p=M_i$.) (Note, I've left out the analysis for when $p$ is between the $M_i$'s; it doesn't change the it too much.)

My question is, how does one solve this problem efficiently in general, when the $m_i$ may not be $0$?

Note: Sorry if I didn't phrase this clearly. Feel free to ask for clarification in the comments.


texts: Complexity of Verification for Clique with Adjacency Matrix

texts:
I am having trouble getting my head around what the complexity of the verification step for the CLIQUE problem would be -- specifically if an adjacency matrix is used. I know in general the complexity for this problem would be O(k^2) * edges in G.

This is the specific question I am attempting to solve:
Select the correct complexity of the verification step for CLIQUE problem. Assume that the candidate solution is size k, and that the Graph with n vertices is represented by an adjacency matrix (i.e., constant time edge lookups).

My thoughts:
If there are k vertices in the candidate solution, I will need to iterate k times. For each of those vertices I will need to check that corresponding row in the adjacency matrix to see if the sum of that row is k - 1. in other words checking to see if the deg(k) for each k is k-1.

Should I consider that k^2? Or would it be (k^2 * n) since I would need to add 1 for each of the n vertices on that row to find out if the row sum is k-1?


texts: Can we use exponential function in a reduction?

texts:
If I have an NP-complete graph problem $P1$ whose instance, say, a graph $G$ and a positive integer $k$ and I have another graph problem $P2$ whose instance is a graph $G'$ and a positive integer $k'$. I would like to prove that $P2$ is NP-complete. The reduction is as follows:

set $G'= G$ and
set $k'= f(k)$.
$P1$ is solved iff $P2$ is solved.

My question is: is this reduction correct when $f(k)$ is exponential function?, For simplicity, say, $f(k)=2^k$. I am afraid that this is no longer polynomial-time but then again calculating $2^k$ or $k!$ is polynomial-time problem.

My whole question is general as the title mentions:  Can we use exponential function in a reduction to create some parameter in the instance of the concerned problem?

EDIT

My question is motivated by the validity of using exponentiation in polytime reduction on cstheory.SE where the OP asks about a specific reduction used in some paper. My question is general about using exponentiation in reduction.


texts:
Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, should be eliminated right?

UPDATE:
My solution to the question in the comment


texts: Doubt regarding binary trees and counting

texts:
Question:

A binary Tree T is semi-balanced, if for every node m  in T:
$$
\frac{R(m)}{2} <= L(m) <= 2*R(m)
$$
where, L(m) is the number of nodes in the left sub-tree of m and

R(m) is the number of nodes in the right sub-tree of m.

Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

My Attempt:

Let T(N) denote the number of semi-balanced trees with N nodes.

For N = 1, T(N) = 1 (Trivial)

For N > 1, T(N) can be found by splitting N into 3 parts, a root, a left subtree and a right subtree, let M be the number of nodes in the left portion, then the N - M - 1 is the number of nodes in the right portion, so by the constraint in the question,

$$
\frac{N-1}{3} <= M <= \frac{2*(N-1)}{3}
$$

So for N > 1,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} T(M) * T(N-M-1)
$$

However, the answer is given as,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} 2 * T(M) * T(N-M-1)
$$

Why is there a factor of 2 in the solution?


texts:
Suppose we have binary search tree with $n$ nodes. For each node $u$
we define weight of $u$ is number of nodes in sub tree of $u$ with
$u$. if  ratio of weight of each internal node $u$  of right sub tree
and left sub tree be at least $0.5$ and at most 2, then what is worst
case of searching for a element in such binary search tree?
The answer is $2\log n$.

How it be $2\log n$? I think this tree is weighted binary search tree not AVL tree. But in proving worst case that mentioned get  stuck. Any hint be appreciated.
My attempt:
I try to use formula that we use for minimum number of nodes we need to construct a AVL tree, Prove that AVL tree has this kind of property with Fibonacci sequence, but i can't draw any relation between my problem and AVL tree.


texts: What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

texts:
I have two large files containing paragraphs of English text:

The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long).
The second text contains almost precisely the same paragraphs and text as the first. It is also 200 pages long with 10 paragraphs per page. However, the paragraphs are randomized and in a different order when compared to the first text. Also, a large percentage of the paragraphs have small changes in wording compared to similar paragraphs. For example, a paragraph in the first text might have a sentence like Like Jimmy, I wanted to go to the palace while the corresponding sentence in the paragraph of the second text would read Like Jimmy, I really wanted to go to the castle.

I want to be able to capture the changes here like the addition of really and the deletion of palace with replacement of castle. If the paragraphs were roughly aligned, then this would be pretty trivial as there are plenty of ways to diff text. However, since the paragraphs aren't aligned, that isn't the case.

If the files were small (handful of paragraphs), Levenshtein Distance probably would work fine, but because the files are huge, it would be inefficient to compare each paragraph of text 1 to each paragraph of text 2 to find out which paragraphs match.

What would be some other approaches to this problem to handle it efficiently?


texts: Counting inversions with index constraint

texts:
I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$

$a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis.

The question is how to find a algorithm that is strictly cheaper than $O(n^2)$ and it yields number of pairs $i,j$ such that $l_j$ completely contains $l_i$ and $j>i$.

I know that without the second constraint, we can just sort the segments by their starting points and do the inversion counting for the ending points.

However, if we want to satisfy the second constraint, what is the optimal way? I was thinking maybe I could maintain an augmented BBST and the key is just the starting point of each segment, once we insert a new segment, there may be some efficient way to count how many nodes in the tree have smaller ending points than the one I just insert.


texts: How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

texts:
I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.

The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should choose which symbols to mark.

I tried with all the first $N$ $a$s (and also other combinations), but then for $v=a^j$ and $x=a^j$ (and $w=b^{N+1}$) pumping doesn't get a string out of $L$.
My idea is that I should involve both $a$s and $b$s between the marked symbols and somehow force the pumping for both, but I don't know how.


texts: Optimal solution to Cartesian Product of two sets (computationally)

texts:
Given two large sets (say 1 million items each), what is the fastest way to compare the values with each other.

This is a typical join problem, for which there are two standard solutions:

nested loop join
hash join

The nested loop is naive because it compares every value to every other value. This makes it slower than optimal. But it allows doing arbitrary comparison types like >=, in addition to just =.

The hash join is better because you can take one set, compute the hash for the value, then go through the second set and compute the hash to lookup if the element exists. But this only allows for comparison to be equality check =. It doesn't allow for >=, for example.

Wondering if there is a current optimal solution that allows for doing the Cartesian Product comparison without naively iterating through both sets, while also allowing for arbitrary comparison types like >=, <, etc.

Update

By optimal I mean anything better than comparing everything to everything else. At least more optimal than that. The hashing example is more optimal because it only has to scan both lists once (I think) rather than n x m times or however.

By "allowing for arbitrary comparison types like >=" I am referencing that, for example, hash joins can only be applied on equality comparison, since you are doing a hash to get an index in the build and probe tables; you can't do >=, <=, >, <, ! (not), etc. with a hash join (from my understanding). But you can with nested loops. So I am looking for the join operator being able to perform all of the comparison types, not just equality. By all we can just say range queries >=, <=, >, < and not queries !. I guess a hash join could handle ! as well probably.


texts: Why are $L$-reductions defined the way they are?

texts:
I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the definition.
Recall that a problem $A$ is $L$-reducible to another problem $B$ if there exist polynomial-time computable functions $f$ and $g$, and positive constants $\alpha$ and $\beta$ such that:

If $x$ is an instance of problem $A$, then $f(x)$ is an instance of problem $B$.
If $y'$ is a solution to the instance $f(x)$ of problem $B$, then $g(y')$ is a solution to the instance $x$ of problem $A$.
$OPT_B(f(x)) \leq \alpha OPT_A(x)$.
$|c_A(g(y'))-OPT_A(x)| \leq \beta |c_B(y')-OPT_B(f(x))|$.

where $c_A$ and $c_B$ are the cost functions for the problems $A$ and $B$, and $OPT_A$ and $OPT_B$ have their usual meanings.
Points 1, 2, and 4 seem completely natural to me. We want some way to map instances of $A$ to instances of $B$ in polynomial time. $f$ takes care of that. Additionally, we want some way (again in polynomial time) to map solutions to instances of $B$ to solutions to instances of $A$. $g$ takes care of that. Finally, we want the mapped solutions to preserve some notion of "quality" so that we can make statements like "if $y'$ is a "good" solution, then $g(y')$ is not "too bad" of a solution". Point 4 takes care of that. But what do we need point 3 for? It seems to me that points 1, 2 and 4 suffice for the definition of a "natural" approximation-preserving reduction.
I know that for $L$-reducibility to imply $PTAS$-reducibility, we need point 3. But is that the only reason for adding point 3 to the definition?


texts: What is the efficiency of Concorde TSP solver program. And is it have any weaknesses? I build my own exact solver and I want to compare it to Concorde. What would be the best way to do this?


texts: Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC

texts:
Consider an equation of the form:

$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$

where A-F are integer coefficients (binary quadratic Diophantine equation). I consider here the most general form, so assume all coefficients are non-zero.

Is there an efficient algorithm which can compute integer solutions for this type of equation?


texts: Quantum circuits for multiply-accumulation

texts:
Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. Using that algorithm, combined with uncomputing, you can make a quantum multiply-accumulate circuit with the same bound: $O(n \ \lg(n) \ 8^{\lg^* n})$ gates.

But quantum circuits have more options available. Maybe they can multiply in some better faster way, instead of just copying the classical algorithm.

Are there more efficient quantum circuits for multiply-accumulating?


texts: Whatever that can be done using algorithm can be done using Turing machine

texts:
In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine?
Since that period many new algorithms were implemented. What was his hypothesis behind this theory ?


texts: Proving that no two state DFA accept the language L = {$0^i : \forall i \ge 0$} $\lor$ {$^i : \forall i \ge 0$}

texts:
how do i prove that no DFA with two states can accept the language

$$ L = \{0^i : i \ge 0\} \cup \{ 1^i : i \ge 0\}. $$

I had a lot of troubles coming up with anything that made sense.


texts: Dynamic programming: Maximize total value

texts:
I was trying to solve this problem using dynamic programming.
We have $n$ objects in a row where each object has a value represented with a positive number.
This is encoded with an array $V[1], . . . , V[n]$ where $V [1]$ is the value of the first object in the row,
$V [2]$ is the value of the second object in the row and so on. We want to select a set $I \subseteq \{1, . . . , n\}$
of objects in such a way that the sum of its values, $\sum\limits_{i\in I} V [i]$, is as large as possible. However,
we cannot select objects that occupy consecutive positions in the row. That is, if we select object
$i$, then we cannot select object $i − 1$ nor object $i + 1$. For example, if $V = (6, 4, 3, 7, 3)$ then the
best option would be to select the first object (with value $6$) and the fourth object (with value
$7$). It is easy to see that any other option would have smaller total value.
We want a dynamic programming algorithm that, given as input array $V$ , computes the value
of the set with highest value. Note that, in order to simplify matters, we do not ask that the
algorithm returns the set, only its total value.
The probleem comes when it says "we cannot select object $i − 1$ nor object $ i + 1$". For $i-1$, the recursive case should be Optimal$(j-2)$+Value$(j)$, but no idea about $i+1$.


texts: Why isn't a binary counter used for generating $k$-combinations?

texts:
I have been looking at algorithms that allow you to generate $k$-combinations of a given string.

My question is that why isn't the algorithm used to generate power sets used to generate the combinations of a given string? That is, we can just use a binary counter of length $n$ with $k$ ones set to select $k$ elements from a length $n$ string. The method is very simple.

I mean, the power set can represent all $k$-combinations of the input. So why use complex algorithms like the ones described here (e.g., Gray codes)?


texts: I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* over Dijkstra. To my understanding, Dijkstra gives a best path and D* works backwards from the end goal, but unlike A* it seems to do many calculations, so it doesn't seem as efficient.


texts: Can't tell whether the following language is regular or not:

texts:
I have to decide if the following language is regular or not.

I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on this language would be appreciated:

$$\{{a^{n^2+2n}|n\ge 0}\}$$

I assume the language is regular.

I assume p is the pumping length.

I use the word ${a^{p^2+2p}}$ which is equal to ${a^{p^2}*a^{2p}}$

But after that i don't know how to end up in a contradiction to prove that it is not regular.


texts: Why it is important to understand when a particular problem is algorithmically “unsolvable.” How should I deal with this type of problems?

texts: So I learned that there are some problems that cannot be solved in computer science but I want to know why is it important to understand the unsolvable algorithm and how should I deal with it.


texts: How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

texts:
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.

Question : How to prove that it is impossible to multiply two 2 x 2 matrices in 6 multiplications?

Please note that matrices are over integers.


texts: Is there a language which enforces "no escape" of variables?

texts:
Many languages with GC perform escape analysis to reduce heap allocations. Is there a language with a "no-escape" construct that tells the programmer during compile time to not escape certain variables? This way they could be guaranteed to be allocated on the stack instead of the heap.
Compare with value types in Java (not realized in any VM yet, AFAIK). In Go it's possible to debug and adjust the program to decrease heap allocations: https://segment.com/blog/allocation-efficiency-in-high-performance-go-services/


texts: How to find more than 1 successive shortest paths between two vertices in unweighted and undirected graph using BFS?

texts:
I have tried to find and print more than one successive shortest paths between two vertices in the undirected graph. Using BFS as DFS will not be optimal in this case, as it can go deep into the stack.

Wrote this function but not getting the correct response and also tried to find help over StackOverflow and other platforms but did not find a solution for undirected graph.


texts: How to group intervals which overlap by some amount?

texts:
I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is possible to add the run ID to the tuple (though I don't think it helps).
The goal is to "clean" spurious ranges (appearing in few runs) and to find groups of at least k almost perfectly overlapping intervals out of m runs of the algorithm, where k is close to m. E.g. if we have 10 runs, k will be 7-9.
By almost perfectly overlapping I mean >0.95 overlap, but exact requirement is user-defined (won't be 0.5 or such). The overlap should be between all intervals in the group (i.e. intersection). However, since I am trying to translate an eyeball analysis into exact requirements this requirement might be too strong ..
The differences in the intervals generated by multiple runs of the algorithm stem from a random factor (seed) as well as slightly different ranges may passing requirements, therefore there is some 'wiggling room' in the results. It also detects some ranges infrequently (think local minima), ranges which should be ignored as spurious.
The origin of the problem is running multiple times some algorithm that searches a range for "interesting" areas. By the nature of the algorithm, each run may return slightly different ranges as well as, at times, a range not seen before.
The intervals can be viewed as integers, though in reality the intervals I get may be real number in any range. I assume I can always use a min-max scaler to, for example, have the ranges have (approximated) integer values in the 0-1000 range or similar.
Below is a (very simple) example of the problem marked as I would do manually. The three green intervals and the three red intervals should be reported as groups, whereas the other three are a group on their own. The overlap of the blue interval is too small. The Yellow interval is not "similar" to the red ones in size.

There may be problems like in the diagram below which I am not sure how to address.
The green (bottom) interval and the one above it are certainly "the same" as are the red one and the one below, however the green and red are already too far apart to be considered a group.

My initial idea was to build an interval graph. On that I can greedily find the point at which most intervals intersect, than somehow (no clear idea how yet) I would remove intervals which should not belong to the group. Once done I remove the group from the graph and repeat.
Another method I thought about, but which is O(N^3) (and not guaranteed to yield a good result) is to calculate the overlap of all pairs, selecting the best and merging (union? intersection? average start/end?) then repeating until there are no more "interesting" overlaps.
I consider an overlap interesting if it is larger than some percentage, e.g. 95%.
Are there any algorithms already achieving something similar?
Any direction someone can point me in?


texts: More than one NFA accepting a given language

texts:
While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so?

For example for drawing: NFA ending with 1 where $\Sigma=\{0,1\}$ is

and also we can draw one without 0 from the edge P to P!

Which one should be considered "more" correct?


texts: Using analog values with Algebraic Normal Form?

texts:
Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates.

The below is an example of an ANF expression which evaluates to true if two or more of it's three inputs are true ($\oplus$ being XOR, implicit multiplication being AND)

$x_0x_1 \oplus x_0x_2 \oplus x_1x_2$

When a digital circuit is expressed this way, you can evaluate it as a polynomial, taking 1 or 0 as inputs for the variables, doing a multiplication for an AND gate, addition for an XOR gate, and doing a modulus by 2 on the final result.

$y = x_0x_1 + x_0x_2 + x_1x_2$

you can verify a truth table by plugging in 0s and 1s for the various $x$ parameters and seeing that it comes out to the correct values.

What I'm curious about is what if we don't use whole numbers?  I'm sure that's a well studied thing but I haven't been able to find any information about it.

it seems sort of like fuzzy logic, but fuzzy logic is a well defined thing with different operations.

Here's some values plugged in and their output.

\begin{array}{|c|c|c|c|}
\hline
x_0 & x_1 & x_2 & output & output \% 2 \\
\hline
0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 3 & 1 \\
0.5 & 0.5 & 0 & 0.25 & 0.25\\
0.9 & 0.9 & 0.9 & 2.43 & 0.43 \\
1.0 & 1.0 & 0.5 & 2.0 & 0.0  \\
\hline
\end{array}

The analog value input gives output that seems especially wrong in the last two rows.

It seems like maybe this just "doesn't work", but it also feels like maybe it does work, or does do something interesting, perhaps with some modifications?

Has anyone come across non digital values used in ANF or similar?

Thanks!


texts: Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

texts:
Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively
account for at least three-fourths (3/4) of the edges in an arbitrary undirected
graph.

The algorithm I have come up with is a greedy algorithm that iterates through the graph choosing the node with the largest number of incident edges and then updating the adjacent vertices with their new incident edge count.

I am fairly confident this algorithm will work, however I am struggling with the proof that I will always account 3/4 of the edges.

What I have so far is that because the sum of the degrees of all the edges in the graph is equal to 2E then on average every node will contribute at least a degree of 2E/n to that summation.  2E/n x n/2 vertices provides me with just E. Is this correct or am I missing something?


texts: Order notation subtractions in Fibonacci Heap

texts:
Can order notation on its own imply:

$O(D(n)) + O(t(H)) - t(H) = O(D(n))$

My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0.

Well, this is actually the case, but there are underlying factors. This equation appears in Fibonacci heap analysis in CLRS (518). The justification for this step comes from the underlying potential function. According to the authors, "we can scale up the units of potential to dominate the constant hidden in $O(t(H))$". I want to know how this happens, but don't really know how to ask this complicated question.


texts: Theoretical performance measures other than worst case

texts:
Suppose that $P \neq NP$, and $P = BPP$.
Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's relevant since I assumed $P= BPP$).
How can she compare between two algorithms $A_1, A_2$? Clearly, $A_1$ and $A_2$ cannot be correct for every input (they must run in polynomial time). Does it make sense to define the better algorithm as the one which answers correctly on more inputs? (And two algorithms will be equal when they answer correctly on the same number of instances).

Are there known methods to do so?


texts: Proving that the language SPACE TMSAT is PSPACE-complete?

texts:
I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete.

My solution is as follows:
SPACE TMSAT $= \{<M,w,1^{n}> :$ DTM $M$ accepts $w$ in space $n\}$ can only be computed by running machine $M$ on $w$. As this forces the allowance of the computation of any PSPACE language, SPACE TMSAT is PSPACE-complete.

Does this solution make sense? Am I being too hand wavy? Any other suggestions or critiques? Thanks!


texts: If $L^*$ or $L^+$ is empty, can L be an infinite language?

texts:
I have to prove or disprove the implications in these two situations

$L^* = \emptyset$ $\rightarrow$ $L$ is infinite
$L^+ = \emptyset$ $\rightarrow$ $L$ is infinite

Here are my thoughts.

I would say Kleene star operation (*) is union of

$\qquad L^0 \cup L^1 \cup L^2 \cup \dots$

and since $\_^0 = \{\epsilon\}$ (even $\emptyset^ 0 = \{\epsilon\}$), there is no language $L$ such that $L^* = \emptyset$.

How to prove finiteness/infiniteness?
Only language $L$ where $L^+ = \emptyset$ is $\emptyset$ which is a finite language. But how to prove there is no other language that is inifinite and the argument is valid for it?

EDIT: will it help if I rewrite the implications $A \rightarrow B$ to $\neg B \rightarrow \neg A$ ?

$L$ is finite $\rightarrow$ $L^* \neq \emptyset$
$L$ is finite $\rightarrow$ $L^+ \neq \emptyset$

2) can be now interpreted as $\emptyset^+ = \{\epsilon\}$ and $\emptyset$ is a finite language. So the implication doesn't work.


texts: Process graphs and finding infinite processes

texts:
I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively.

Most of the material I have found is not for beginners. I am looking for references / algorithms that can help me understand:

What are process graphs?
How to search for infinite processes in these graphs?

Thanks in advance


texts: Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable

texts:
So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way:

let's suppose that $g$ is the computable function that represents $D$ $$g(x) = \left\{\begin{array}{rcl} 1 & \mbox{if} & \Phi_x(x)\downarrow\ \\ 0 & \mbox{if} & \Phi_x(x)\uparrow\ \end{array}\right.$$
let's suppose that it exists a Turing machine of index $i_0$ such that $g = \Phi_{i_0}$, than it is possible to define the function: $$g'(x) = \left\{\begin{array}{rcl} \uparrow & \mbox{if} & g(x)=1=\Phi_{i_0}(x) \\ 0 & \mbox{if} & g(x)=0=\Phi_{i_0}(x) \end{array}\right.$$
so $g'$ is also computable thus there is a Turing machine of index $i_1$ such that $g' = \Phi_{i_1}$, but then we will have that:
$$\Phi_{i_1}(i_1)\downarrow \iff g'(i_1) = 0 \iff g(i_1) = 0 \iff \Phi_{i_1}(i_1)\uparrow $$
$$\Phi_{i_1}(i_1)\uparrow \iff g'(i_1) \uparrow \iff g(i_1) = 1 \iff \Phi_{i_1}(i_1)\downarrow $$

which is a contraddiction. So an index $i_1$ doesn't exists that is the index $i_0$ that computes $g$ doesn't exists, that is $g$ is not recursive so $D$ is not recursive enumerable.

I'm quite confused on this topic, so tell me if I made any kind of error.


texts:
Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.

  How to prove that this algorithm has an approximation ratio of 2?

Suppose that once the algorithm is completed, processor $1$ is the busiest and assume task $l$ is the last task assigned to it. Let $s$ be the time that was used on processor $1 $ before adding task $i$. The algorithm has therefore found a valuable solution $u_1 = s + t_\ell$.

I'm stuck on how to show that:

for every $1 \leq j \leq k$ we have $s \leq \sum_{i: \alpha(i)=j}t_i$.
$s \leq 1/k \; \sum_i t_i \leq u^*$ and $t_\ell \leq u^*$ and use these results to limit $u_1$ ($u^*$  is  the optimal value).

Here is the definition of the Job Scheduling problem

Input: A set of $n$ tasks of length $t_1, t_2, \ldots, t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha\colon \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$  which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.


texts: Methods for proving upper bound on a-approximiation algorithms?

texts:
I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance.

For example, there's a simple randomized algorithm for the MAX-E3SAT problem, where there are $m$ clauses each consisting of three distinct 3 variables in $\{x_1, ..., x_n \}$.

There's a theorem that if there exists an algorithm which is $(\frac{7}{8} + \epsilon)$-approximation, then $P = NP$.

What method can and should I use for proving such theorems?
Could you please provide an example?

More over, regarding the MAX-E3SAT problem, what method can and should I use to prove such claim:

For any instance of MAX-E3SAT the optimum is at least $\frac{7m}{8}$ ?
I'm not looking for the proof of this claim, just the method for proving it.

Thanks a lot


texts: Calculating error in the Input to a convolutional layer

texts:
Say I have a incredibly simple input to a convolutional layer: [In1] <----- 1*1 input matrix
I have two filters applied this input:[F1] and [F2]
They give the results: [F1 * In1] and [F2 * In1]
Then let [F1 * In1] = [Out1] and [F2 * In1] = [Out2]
I then calculate ∂C/∂In1 for each filter: [∂C/∂Out1 * ∂Out1/∂In1] and [∂C/∂Out2 * ∂Out2/∂In1]
This leaves me with two matrices above for ∂C/∂In1 do I sum or average these two matrices to get the final value for ∂C/∂In1
(Also I understand that this is an incredibly simple example in terms of convolution I'm just more concerned with the summing or averaging. Thanks for any help!)


texts:
Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?
Using similar ideas like Cook-Levin (or $P\subseteq \mathbf{P/poly}$), I can show that given $x\in\{0,1\}^n$, there exists a (easily computable) poly-sized circuit that can compute each bit of the reduction, say $R(x)$. The issue for me is that the size of $R(x)$ may depend on $x$ and not only $n$ (since we only require it to be bounded by $\mathrm{poly}(n)$). In such a case, it is not clear how to what input length circuit for the language $B$ to use.


texts: Is Supervised Learning Better than Unsupervised Learning (For Recommendation Systems)

texts:
I am working on a Recommendation System as a personal project (I finish it on time, I'll present it as my final year project). I devised mathematical methods that estimated User's ratings of products based on their previous ratings, without using ML. I developed a host of such algorithms for recommendation (I developed a paradigm that allowed me to generate an infinite number of distinct recommendation systems). I intended to assign weights to a select few of them (maybe the ones with the highest accuracy), and take the weighted average of the estimated user ratings.

I realised that Machine Learning could be used to best determine the appropriate weight to assign each of the algorithms on a per user basis, and decided to start learning ML yesterday. It seems what I'm intending to do, is supervised learning.

From what I can tell, it seems existing recommendation systems on the market use unsupervised learning. I am curious to how the two paradigms compare in my case. Would supervised learning work better than unsupervised learning, or is unsupervised learning a better paradigm for recommendation systems?


texts:
I studied that Integer problems are properly NP-HARD problems. I know that NP-HARD include problems that arent solvable, like the halting problem.
This mean that there are instances of Integer problems that arent solvable ?


texts: How a Data Compression Software Reads a File as pure Binary File and makes Output?

texts:
I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,

I read texts from a text file  ->

then convert it to a binary string ->

then convert it to an encoded binary string.

At this point, I can save the encoded binary string in a text file, but I want to know what is done in general.

For example, when we use Winrar software, it -

does not read as I said above, it compresses any file
makes .rar file as output

So, how a compressor "read" any file as a pure binary form, and how it makes output file?

In another way, what i want is to know how to read any file as a pure binary form and make a output file given that I have a encoding and decoding scheme. Please comment anything related to question, I am new to the topic.


texts: Asymmetric Transition Probability Matrix with uniform stationary distribution

texts:
I am solving a discrete  Markov chain problem. For this I need a Markov chain whose stationary distribution is uniform(or near to uniform distribution) and transition probability matrix is asymmetric.

[ Markov chains like Metropolis hasting has uniform stationary distribution but transition probability matrix is symmetric ]


texts: How to model this constraint using integer linear programming?

texts:
Suppose we have $S=\{1,2,\ldots,n\}$, a binary variable $x$ and an integer $p$. I would like to model the following constraint using integer linear programming:

  If $x = 1$, then there must exists a unique $i\in S$ such that: $x_j=1$ for all $j\in\{i,i+1,\ldots,i+p-1\}$.

How can I do this?


texts: Is the set of languages recognized by a Turing machine with an oracle countable?

texts:
I am currently taking a class in complexity theory and I am struggling with this question.

We define a TM with Oracle per. Sipser 6.18 as:

"An oracle for language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$. An oracle Turing machine is a modified Turing machine that has the additional capability of querying an oracle. We write $M^b$ to describe an oracle Turing machine that has an oracle for language B."

I think that the answer is potentially false. We know that the set of languages is uncountable and suppose we had a Oracle Turing machine that accepts if the oracle answers YES, reject otherwise. Wouldn't that mean that then the set of languages recognized by TM with an oracle be uncountable?


texts: An approximation for the sum of k largest elements of n-sorted arrays?

texts:
Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements.

All elements are between 0 and 1, and the the sum of all elements in array $i$ equals to $S_i$.

Instead of  using a min-heap to find the $k$ largest elements (and thus, deriving the sum of the $k$ largest elements), one way for approximating the sum is to select the $k \cdot \frac{S_i} { {\sum_{i=1}^n} S_i} $ largest elements from array $i$.

We assume that $k \cdot \frac{S_i} { {\sum_{i=1}^n} S_i} $ is an integer, for every $i$.

Is the above algorithm is a constant-factor approximation algorithm? I think it is 0.5-approximation algorithm, but not sure yet.

Note that if the arrays have arbitrarily array sizes, then the claim is not true. For example, if there are $n=2$ arrays, one with $k$ elements equal to $1$, and the other with $k \cdot t^2$ elements of $1/t$, then while the sum of the $k$ largest elements is equal to $k$, the approximation will approach to $0$, as $t$ approaches to infinity. This why we assume that the array sizes are both equal to $k$.


texts: How does computer store non-repeating decimal very accurately?

texts:
Maybe it is not accurate at all, but it looks very accurate for me.
I'm making a scientific calculator for my portfolio, and I found an interesting phenomenon.

Because computers store decimals not accurately but approximately, I thought that asin(sin(30rad)) wouldn't give 30rad, and sqr(sqrt(7)) wouldn't give 7, etc..

However, it seems that every kind of calculations like above gives an accurate result. (I used cmath header of c++, and I checked that python math modules also gives the same)

This consequence seems even arcane to me. Does the computer really store those non-repeating deicmals? or is it just a matter of implementation of math libraries, like substituting a special symbol for them?


texts: Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I found discuss only treewidth.


texts: What is the reason behind getting same result by maximum likelihood estimate and smoothing?

texts:
I know that Good-Turing smoothing helps us to trim a bit of probability from some more frequent events and give it to the events we've never seen. Thus it keeps our model from assigning zero probabilities to unobserved events. But while dealing with a dataset, I encountered an interesting result. Here is the data I observed about national teams that win a yearly competition:

9 USA, 3 China, 2 France, 1 Japan, 1 Russia = 16 teams.

When I use Good-Turing smoothing to estimate how likely that next winner is Russia it gives the same result with MLE.
$C^*(Russia)=2*\dfrac{1}{2}=1\;\;,\quad P^*_{GT}(Russia)=\dfrac{1}{16}$
I just couldn't understand how it is possible to get the same result even if carrying some probability for unseen events. Thanks in advance.


texts: How do you derive a type $∃e(e)$ in terms of universally quantified types, without invoking Void initially?

texts:
I wrote a "proof" for this, and though it was enough to convince myself, there are a few things that bother me about it. Primarily I'm not sure about the loose way in which I'm swapping between first-order logic and the Curry-Howard correspondence, and some ancient and brief exposure to first-order logic as an undergraduate. I'm looking to keep the proof fairly intuitive, and avoid any overly clever invocations if possible (though I don't mind hearing about them).

I'm using a possibly non-standard convention that the syntax $∃e(e)$ means $∃e(P(e))$ where $P(e)$ means there exist a value of type $e$. Let $\texttt{Void}$ denote a type devoid of any values, and assume it can be expressed as $∀a(a)$ in the type system, which seems a legitimate take on affairs as it would be seemingly impossible to construct a value simultaneously inhabiting every type. Then a function from $T → \texttt{Void}$ is equivalent to $¬T$ by Curry-Howard, I believe.

Rather than going about it the hard way and trying to find a universal-only sentence that is implied by $∃e(e)$, then proving a logical equivalence, I'll start with a universally quantified type I've been given by an oracle, then show how this implies $∃e(e)$.

$$
\begin{multline}
\shoveleft
\begin{aligned}
∀r[∀a(a → r) → r] \\
∀r∀a(a → r) → ∀r(r) \\
∀r∀a(a → r) → \texttt{Void} \\
¬∀r∀a(a → r) \\
∃r[¬∀a(a → r)] \\
∃r[∃a(¬(a → r))] \\
∃r[∃a(¬(¬a∨r))] \\
∃r[∃a(a∧¬r)] \\
\text{(provable identities) }  ∃r[∃a(a)∧¬r] \\
\text{(eliminate conjunction) } ∃r[∃a(a)] \\
\text{(eliminate redundant quantifier) } ∃a(a)
\end{aligned}
\end{multline}
$$

(Apologies for the Unicode symbols, I gather it isn't the norm, but I'm trying to collect some notes in a markdown document.)


texts: Determining if a list contains two numbers whose difference is less than k

texts:
Given a list with $n$ positive elements and positive number $k$, determine whether there are two numbers whose difference is less than $k$.
The average time complexity should be $O(n)$, and the memory should be $O(n)$ as well.

My attempt: initialize a hash table, and insert every element from the list to the hash, all of this takes $O(n)$ time on average.
Now, scan the list. Say the the elements are $x_1,x_2, \dots, x_n$.
Assume we scan $x_i$ then if we have in the list an appropriate element, it should fulfill $|x_i-x_j|<k$, so I have to check $2k$ different elements, which isn't good enough.
Does anybody have any other idea?


texts: Algorithm for guessing a word in a dictionary with weighted operators

texts:
Suppose I am given a dictionary of words which contains no more than 100 words, and each word has a maximum length of 50 characters. I want to write a program to guess an unknown word, call it S, that is in the dictionary using 2 weighted operators:

int getOccurrences(char x): return the frequency of the character 'x' in S. This operator costs 1 for each query.
char getChar(int k): return the character at the position 'k' of S. If the length of S is less than k, it will return '#'. This operator costs 10 for each query.

(those functions will give me feedback when I call them)

It is preferred that the average cost to guess S is minimal.

I completely have no idea with this problem. My thought is that given a list of strings, which operator I should use to divide the set by half like in binary search, but I have no luck yet.

Thank you.

PS: Assume that the words in the dictionary are only containing  a-z.


texts:
Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the fewer operations used the better.

$$ \left((a \rightarrow b ) \downarrow b \right) \wedge \left(c \vee d\right) \wedge \left( \left(e \leftarrow f\right) \vee f \right) \tag{IND} $$

This would be valid because all instances of each variable exist in only 1 of the "factors" even if it appears in that factor multiple times.

$$\left((a \rightarrow b ) \downarrow b \right) \wedge \left(a \vee b\right) $$
This would be invalid because the $a$ (or the $b$) appears in multiple AND "factors"

I have called this (IND) because each of the factors is independent of each other. I'm mainly interested in a way to convert 3-CNF to (IND), if it is possible.

Edit for clarification:

Consider $\left( a \vee b \vee c\right) \wedge \left(a \vee d \vee e \right)$. The $a$ appears on both sides of the $\wedge$ I would like to convert it into format: $ f(a,b,c) \wedge g(d,e)$ where $f(a,b,c)$ and $g(d,e)$ can use any operations.

Similarly

Given $\left( a \vee b \vee c\right) \wedge \left(a \vee b \vee d \right)$ I would like the $a$ and $b$ to be on the same side of the $\wedge$. It doesn't matter how they are separated, or if any of the other variables move. All that matters is that each instance of a variable appears in only 1 "factor"

$\underbrace{\left( a \vee b \vee c\right)}_{factor} \wedge \underbrace{\left(d \vee e \vee f \right)}_{factor} \wedge \underbrace{\left(g \vee h \vee i \right)}_{factor}$


texts: Matrix equality up to row/column permutations problem name

texts:
Sorry for the trivial question; has the following decision problem an "official" (possibly short) name?

Given two  $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same up to row and column permutations.

(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)


texts: Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

texts:
Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at most distance $d$ from some vertex in $D$. Prove that if $\delta$, the minimum degree of $G$, satisfies $\delta > 50$, then $G$ has a distance $d$-dominating set of size $O(n/\delta)$.

I am considering a greedy algorithm to construct $D$. In each step, pick a vertex that covers the maximum number of "uncovered" vertices (i.e., vertices that are of distance $> d$ from any element in $D$). For each vertex $v$, let $C(v)$ be the set consisting of $v$ together with all of that vertices that are at most distance $d$ from $v$. Suppose that during the process of picking vertices the number of vertices $u$ that do not lie in the union of the sets $C(v)$ of the vertices chosen so far is $r$. Then by assumption, the sum of the cardinalities of the sets $C(u)$ over all uncovered vertices $u$ is at least $r x$....

The drawback of this approach is that I don't see how $x$, a lower bound on the number of vertices within distance $d$ of a vertex in $G$, can be more than $\delta + 1$ (i.e., the order of the complete graph $K_{\delta + 1}$). Unfortunately, if we use this lower bound for $x$ in general, we won't get a dominating set of size $O(n/\delta)$.


texts: A polynomial time reduction and the size of problem (exact cover)

texts:
An exact cover problem is one of the NP-complete problems.

Given a family $\mathbb{I}$ of subsets of a set $[n]=\{1,\dotsc,n\}$, whether there exists a subfamily $\mathbb{I}'\subseteq \mathbb{I}$ such that sets in $\mathbb{I}'$ are disjoint and $\cup\mathbb{I}' = \cup\mathbb{I} = [n]$.

e.g., $\mathbb{I}=\{\{1,2,3\},\{3,4\},\{2,4\},\{4,5\}\}$ and $n=5$, then $\mathbb{I}'=\{\{1,2,3\},\{4,5\}\}$.

I am trying to prove that a problem I am working on is NP-complete by showing a polynomial-time reduction from an arbitrary exact cover problem to my problem. What's not obvious to me is that without constraining the size of $\mathbb{I}$, it is impossible(!) to reduce in a polynomial-time  $O(\mathrm{poly}(n))$.

It seems that I am missing something about the polynomial-time reduction.
Is it more like $O(\mathrm{poly}(n + |\mathbb{I}|))$ or $O(\mathrm{poly}(n + n|\mathbb{I}|))$ since each element in $\mathbb{I}$ can have up to $n$ elements?


texts: Minimising total access time to elements in an array which is accessed sequentially

texts:
Starting with two examples:

for(i = 1; i<10; i++) {B[i] = 0;}
for(i = 1; i<10; i++) {B[2i] = 0;}

In the first example, the successive accesses to the array are in contiguous locations whereas in the second example they are at alternating locations. Therefore, the total access time is lesser in the first case.

Now, if we have two arrays in one loop like:
for (i=0; i<10;i++) {A[i] = 0; B[2i] = 0;}

It would be efficient to interleave the elements of both the arrays to reduce the total access time. We can also split it into two different loops, I don't understand how.

However, what do I do in case of more than one loop and more than one arrays? The primary thing that comes to my mind is always interleaving them. Another problem posed is that we can't interleave like this in memory so what am I supposed to do?

tl;dr

How exactly do I reduce the total access time for more than one loops and arrays? An example would really help me.
Even if I find out how to do so, how do I store them in the memory?


texts: Recognizable vs co-recognizable languages

texts:
I understand following about recognizable (aka recursively enumerable) and co-recognizable languages:

Definition 1: Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
For recognizable language, we can specify Turing machine which can enumerate the language elements.
Given the string in the recognizable language, Turing machine can eventually confirm that the string indeed belongs to the language.
Language L is called co-Turing-recognizable, if L’ is Turing-recognizable.
Given the string not in the co-recognizable language, Turing machine can eventually confirm that the string indeed does not belong to the language.

Doubt

Q1. What is definition 1 equivalent of co-recognizable languages?

Q2. Do they also have one-to-one correspondence to natural numbers?

Q3. Do they also have Turing machine associated with them which can enumerate their elements?

Q4. If answer to Q2 and Q3 is true, then doesnt it make them same as recognizable?


texts: What precisely is infinite ambiguity in a grammar?

texts:
From what I've read, an example of infinite ambiguity is usually given in a form of a loop:

$S \rightarrow aA \\
A \rightarrow B \\
B \rightarrow A \\
B \rightarrow b$

But a grammar is called ambiguous if there's more than 1 way to derive the input string ω. What if I then take this well-known ambiguous grammar:

$S \rightarrow SSS \\
S \rightarrow SS \\
S \rightarrow b$

and extend it with $S \rightarrow \epsilon$
so that for any member of $\left\{ b^n \middle| n \geq 0\right\}$ there's infinitely many ways to derive it? Does this make the grammar infinitely ambiguous?


texts: Dijkstra's algorithm for undirected graphs with negative edges

texts:
INPUT: "an undirected, weighted graph (negative weights allowed)"

Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?


texts: Maximum Independent Subset of 2D Grid Subgraph

texts:
In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.

However consider the following subset of graphs:

Create an $N \times N$ grid of unit square cells.
Build a graph $G$ by creating a vertex corresponding to every cell.  Notice that there are $N^2$ vertices.
Create an edge between two vertices if their cells share a side.  Notice there are $2N(N-1)$ edges.

A Maximum Independent Subset of $G$ is obviously a checker pattern.  A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.

Now we create a graph $G'$ by copying $G$ and removing some vertices and edges.  (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)

By what algorithm can we find a Maximum Independent Subset of $G'$?


texts: State machine with knowledge of prior states?

texts:
I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.

Below is an example graph descibring the process. The essence is: If both State Q1 and State Q3 recieve an input of one, after State 3, transition to State Q4, otherwise transition to State Q5.

I understand that it would be possible to model this using a finite-state machine where we duplicate any states between those that we are interested in. The example below demonstrates this with States Q2a and Q2b corresponding to the differences in input at state Q1

However, as the number of conditions and the gaps between them grows (both of which are possible in the process I'm looking at), the number of states grows exponentially.

The question is, what other computational models could be used to describe a process where an arbitrary number of inputs could be used to control transition between states?


texts: Explain the difference between Turing Complete and Turing Equivalence

texts:
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.

A computational system that can compute every Turing-computable
function is called Turing-complete (or Turing-powerful).
A Turing-complete system is called Turing-equivalent if every function
it can compute is also Turing-computable; i.e., it computes precisely
the same class of functions as do Turing machines.

I'm not sure if I understand the difference between these two terminologies properly and what "Turing-computable" means. So for example if I have a programming language $X$, it is Turing complete if it can do any and everything that a Turing Machine can do? And it $X$ ends up being Turing complete and it can be shown that all of the functions that it computes are Turing computable, then $X$ is also Turing equivalent?


texts: Operator-precedence grammar`s symmetrical rule

texts:
I have a basic question, but I cannot find an answer anywhere on the Web. I have the following grammar rules:

S -> if C ;
C -> O < O
O -> O + i
O -> i

The part than I`m interested in is at rules 1,2 and 4.

I have calculated First(O) = {i, +} and Last(O) = {i}.

So, First(C) = {i,+,<} and Last(C) = {<, i}.

Also, if  <*  First(C) and Last(C)  >*  ;

I have build the precedence table and now I want to parse the input: if < ;

So when i parse it, I first have if on top of my stack. Then I look at <, if <* <, so I push < on top of the stack. So now I compare < to ;, ; has higher precedence according to the rules, so I must pop. The last part is trivial, and leads me to S, thus accepting the sentence.

BUT, as we can clearly see from the rules, this sentence should not be accepted (we only have 1 <, not enough to form C in order to reduce it).

I have noticed that this happens because there is a symmetrical rule (rule 2 in our case), which means that if <* {i, <} >* ;, so we cannot verify that there was indeed an < or only an i.

What is the solution to this problem? How do we handle these special cases where symmetrical rules`s precedence relations overlap? I`m sure there must be one, because this grammar is conceptually close to a programming language parsing problem itself.

Thank you for your time!


texts: Given two $a^n b^n$-style languages, how do I find out if their intersection is regular?

texts:
I have two languages as below.

$$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$$
$$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$$

Now, I wonder what is $L_1\cap L_2$. Is it a regular language? Is it context-free?

To solve the problem, I feel like I need to solve the following system of equations, but I'm not sure.

$$
\begin{cases}
2n=2m+1\\
2m+1=\frac{2n}{2}
\end{cases}
$$


texts:
This one goes both ways at this point in my computer science studies... Is it scripting in the same sense as a Python script (for example)?

Are they the same?

I'm learning Javascript at the moment as part of a Web design textbook but at the very start of my programming lessons I got quite far in programming with Python and would like to finish it IF it is conducive to Web design.

Many thanks in advance to anyone who can help me here and I'll be sure to vote up the best answer for reputation.


texts: Proving the loop invariant for a simple program in Hoare logic

texts:
I was studying loop invariant and came across Tomas Petricek's example. Here's the equivalent(I believe) program after I revised it a bit for proof in Hoare logic:

j = 9;
i = 0;
while (i < 10)
{
    i = i + 1;
    j = j - 1;
}

The loop invariant given by Petricek is i + j == 9, which makes sense to me. And the pre-condition and post-condition, seems to me, is (|T|) and (|i = 10 and j = -1|), respectively. Here's my attempt:

(| T |)
(| eta[j/9][i/0] |) Implied
  i = 0;
(| eta[j/9] |) Assignment
  j = 9;
(| eta |) Assignment
  while (i < 10)
  {
    (| eta and i < 10|)
    (| eta[j/j-1][i/i+1] |) Implied
      i = i + 1;
    (| eta[j/j-1] |) Assignment
      j = j - 1;
    (| eta |) Assignment
  }
(| eta and not i < 10 |) While
(| i = 10 and j = -1 |) Implied

For the three Implied rule, with eta being i + j = 9, the first two are straightforward to me:

|- T => 0 + 9 = 9
|- i + j = 9 and i < 10 => i+1 + j-1 = 9

But I can't see how do I get from i + j = 9 and not i < 10 to i = 10 and j = -1. Am I setting the wrong post-condition? I could get j <= -1 trivially, but I don't think that's how it should work, right?

I thought that, without setting j to 9 and i to 0 in first two line, what this while loop does is to set i to 10 and j to j-(10-i). In that case, if we set the initially value of i to 0 and j to 9, j would be set to 9-(10-0) = -1, which is what I intended. I'm not sure what went wrong in my reasoning. May I have a hint? Thanks!


texts: Stable matching with dynamic preference lists

texts:
I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same preference list over the families, but the families have different preference lists.

Our objective is to select from the set $M$ a stable matching. It is clear that the family with rank 1 will be matched with the child she ranks the best among those that is matched with them in $M$, the family with rank 2 will be matched with the child she ranks the best among those that is matched with them in the matchings selected for family 1 and so on.

When the preference lists are fixed, the constraint can be modeled as follows:

$ 1 \leq \sum\limits_{j'\in J^{\leq}_{C_j^i}(i)}x_{ij'} + \sum\limits_{i'\in F^{\leq}_{i}}x_{i'C_j^i} $; $i \in F$, $j=1,\ldots,i$

with

$x_{ij}$ equals one if family $i$ is matched with rank $j$.
$C_j^i$ is the child with rank $j$ for family $i$.
$ J^{\leq}_{s}(i)$ is the set of children that family $i$ ranks at the same level or better than child $s$.
$C^{\leq}_{i}$ is the set of families that are at the same level or better than family $i$.

How to modify this constraint to take into account the changes in the preference lists?


texts: Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path

texts:
I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better  states  when  there  is  no  available  heuristic. It uses nested levels of random games in order to guide the search. It consists in two functions : nested(position, level) and sample(position)

The basic sample function just plays a random game from a  given  position,  we  use  the  function play(position,  move) which plays the move in the position and returns the resulting position.

int sample (position)
1  while not end of game # I don't understand why did he wrote a while
2    position = play (position,random move)
3  return score

If it just played a random game from a given position, shouldn't it have been without a while and only this : position = play (position,random move) ? And where does he get the score ?

The  Nested  Monte-Carlo  Search  function  plays  a  game, choosing  at  each  step  of  the  game  the  move  that  has  the highest score of the lower level Nested Monte-Carlo Search. At each step the algorithm

tries all possible moves
plays a nested search at the lower level after each move
memorizes the move associated to the best score of the lower level searches.

As the samples are randomized, it is not guaranteed that a nested search will always improve on previous searches or  even  lower  level  searches.   In  order  not  to  lose  the  best moves of the best sequence found by a previous search, the algorithm memorizes the best sequence. If none of the moves improve on the best sequence, the move of the best sequence is  played,  otherwise  the  best  sequence  is  updated  with  the newly found sequence and the best move is played:

int nested (position, level)
1  best score = -1
2  while not end of game
3    if level is 1
4      move = argmax_m (sample (play (position, m)))
5    else
6      move = argmax_m (nested (play (position, m), level - 1))
7    if score of move > best score
8      best score = score of move
9      best sequence = seq. after move
10   bestMove = move of best sequence
11   position = play (position,bestMove)
12 return score

In the following example he claims that if depth first search has one chance out of two of choosing the wrong move at the root, A level 1 Nested Monte-Carlo Search will always find the best score.

Yet I don't get why for the first step. I have some difficulties when starting playing move = argmax_m (sample ( play (position, m)))
$$move = \underbrace{argmax_m (\overbrace{sample ( \underbrace{play (position, m)}_{(1)})}^{(2)})}_{(3)}$$

so we move first for a given unkown position m. I believe it is
chosen by argmax_m. Yet, how can it chose between both nodes ? Where
do we test the score ?
Why randomness here ?
Where can we test the argmax_m ?


texts: Is busy beaver the fastest growing function known to man?

texts:
I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver?

We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.

Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.

At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)


texts: VC dimension of finite unions of one-sided intervals

texts:
What is the VC dimension of $k$ finite unions of one-sided intervals:

If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these intervals can shatter $4
$ points as below, assuming that $a_1>a_2>a_3>a_4$:

Point $p_1$ at interval $(-\infty, a_1]$
Point $p_2$ at interval $[a_1, a_2]$
Point $p_3$ at interval $[a_2,a_3]$
Point $p_4$ at interval $(-\infty, a_3]$

For $k$ finite unions I think answer is $k+1$, am I right?


texts: Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?

texts:
Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a counterexample string in $L$ which I can use to disprove (via a contradiction proof using the pumping lemma for CFLs) that $L$ is a CFL. This suggests that $L$ may be recognized by a nondeterministic PDA.

Now, if $\#_a(w) = i\cdot \#_b(w)$ for some $i \geq 0$, then I can perfectly match every single $b$ with $i$ $a's$. The problem is that since $i$ can be any nonnegative integer, there are strings in $L$ for which I'd need to match every one $b$ with one $a$, strings for which I'd need to match every two $a$'s with one $b$, and so on. I don't see how a nondeterministic PDA has the capacity to cover all such (i.e., infinitely many) matchings.


texts: How to express the existence of winning strategy of the starter of a game in temporal logic?

texts:
Consider a two-player game. A winning strategy of a player is a strategy following which the player can always beat his opponent, no matter how his opponent responds.

A game can be unfolded to a state space consisting of the possible ways of both sides of the game. How to express the existence of winning strategy of the starter of a game, say player 1, in temporal logic, defined on such a state space? The temporal logic formula can be used for model checking.

Using CTL, I get $\exists \Box (\exists \Diamond \textsf{Win}_1)$, meaning that there exists a path (from the initial state) such that from each state of this path there exists a path that eventually leads to a winning state for player 1. Is this correct?

Can it be expressed in LTL or any other variants of temporal logic?


texts: A Problem on Time Complexity of Algorithms

texts:
For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?

By verifying, I mean that given a candidate solution $y$, we can judge whether $y$ is correct or not in time $O(n^s)$.