texts:
Something is Turing Complete if it can be used to simulate any Turing Machine.

So, can a Finite Automaton simulate a Turing Machine?

On the question Can regular languages be Turing complete? they say a Regular Language can be Turing Complete, but it does not make sense to me. I am not talking about the Language being parsed, but the Finite Automaton itself.

Finite Automatons and Regular Languages are not Equivalents. Finite Automatons are machines which accept or reject some Language. But Regular Grammars and Finite Automata are equivalents because I can convert one to another. Then, the question is, are Regular Grammars Turing Complete? Are Type 0 grammars Turing Complete? i.e., can I use a Regular Grammar or a Type 0 Grammar to do any computation I would like?

Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?


texts:
An optimized algorithm for the 3-sum problem with an input array N has
O(N^2logN) however I read that the Big Omega for this algorithm could be Omega(N) because you have to touch all entries once. But to me this doesn't make sense.

If you have to perform the 3-sum operation on the entire array, wouldn't Big-O and Big-Omega be the same because regardless of the results the algorithm has to perform the same operations on the entire array?


texts: Why do depth-limited search algorithm and BFS have different memory complexity?

texts:
Let be $b$ the branching factor of the tree.

Let be $d$ the depth of the shallowest solution.

Let be $l$ the limit given to depth-limited search algorithm

Why is depth-limited search algorithm memory complexity $\mathcal O(b)$ times something (which is actually $\mathcal O(bl)$) whereas BFS is $\mathcal O(b)$ power something (which is actually $\mathcal O(b^d)$)?


texts:
When a virtual memory address outside the range of loaded into physical RAM is referenced and a page fault occurs, does the Memory Management Unit rely on DMA (Direct Memory Access) to swap the referenced page into RAM, or is an interrupt routine that uses the CPU to copy in the memory in some more mundane way occur?

Please assume the x86 architecture.


texts: How can I prove that the language of a read-only Turing machines is regular?

texts:
I find this,
but I can't complete it, is there any other solution for it?


texts:
I've read several sources of information that describe the process of Bayesian Monte Carlo Quadrature but am just not understanding the details enough to be able to implement it.

For instance two sources:

http://mlg.eng.cam.ac.uk/zoubin/papers/RasGha03.pdf
https://www.cs.toronto.edu/~duvenaud/talks/intro_bq.pdf

I get some high level ideas like:

It uses prior information better than other monte carlo algorithms such as Quasi Monte Carlo.
It can converge faster as a result, for integrands that are smooth.
It gives you a "confidence interval" so you can get an idea of how much variance / noise there is.
It seems to somehow use gaussian functions as basis functions.
every data point somehow fits the sum of gaussian basis functions to the actual function better?

Honestly, other than that it is pretty hazy.

Can anyone explain in a simple way how you could integrate a function over a specific domain, using Bayesian Monte Carlo Quadrature?  Or any links to drop dead simple explanations, or implementations would be helpful too.


texts:
We have a finite poset and its subset $S$.

We can enumerate elements of $S$ using an iterator.

I need to check if there are more than one minimal elements of $S$ (regarding the above poset).

The best thing I came up with is to construct the graph of all elements of $S$ and then check it for minimal elements. But this:

requires to enumerate all elements of $S$ (while I would prefer to interrupt the calculating in the middle as soon as we get $2$ minimal elements);
may use much memory.

Is there a better way (without enumerating all $S$)?


texts: Prove a characterisation of the minimum directed cycle mean cost

texts:
Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Set $p_i(0) = 0$ and $p_i(t+1) = \min_{j \in O(i)} \{ c_{i,j} + p_j(t) \}$ for all $i\in \mathcal V$.

I've proven by induction that $p_i(t)$ denotes the length of the shortest walk start starts at $i$ and traverses $t$ arcs.

Now, I want to prove that the minimum directed cycle mean cost $\lambda$ satisfies:

$$\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} (\frac {p_i(n) - p_i(k)} {n-k})$$, where $n$ is the number of vertices in the graph $\mathcal G$.

I see that traversing $n$ arcs will always create a directed cycle. However, I don't know how to continue from here.


texts: Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

texts:
I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.

I thought first to make a substitution: $m=\log n$. Then:
$$
T(2^m)=T(2^{m \over 2})+10\log m
$$
Let $S(m)=T(2^m)$:
$$
S(m)=S\big({m \over 2}\big)+10\log m
$$

Now we can use Master theorem.

Suppose it's the case when $f(m)=O(m^{\log_2 1-\epsilon})=O(m^{0-\epsilon})$. Let $\epsilon=0.5$ then:
$$
\lim_{n\to \infty}\frac{10\log m}{m^{0.5}}=0
$$
Hence according to the Master theorem $T(m)=\Theta(m^0)=\Theta(1)$.

Am I in the right direction?


texts: Analyzing the Runtime of Shuffling Algorithm

texts:
The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. Determine the runtime of the following algorithms.
Algorithm 1:
function Shuffle(A)
Split A into two equal pieces A, and B (this takes constant time)
A = Shuffle(A)
B = Shuffle(B)
for i = 0 to len(A)/2 − 1:
        for j = 0 to i − 1 do:
            B[j] = B[j] − A[i] + Random(10)
            A[i] = A[j] − B[i] + Random(10)
B = Shuffle(B)
A = Shuffle(A)
Combine A = A + B (this takes constant time)
return A

Algorithm 2:
function Shuffle1(A)
for i = 0 to len(A) − 1:
    for j = 0 to i − 1:
        for k = 0 to j − 1:
            A[k] = A[k] + A[j] + A[i] + Random(m)
return A

After a good amount of work, I believe that the runtime for Shuffle1$(A)$ to be $O(n^3 \cdot m^2)$ as there are three nested loops. In the innermost loop, the algorithm does the constant time array access and $O(m^2)$ work done. But, I am not quite sure. I am having difficulty tackling the runtime of Shuffle(A). Should I be using the Master Theorem in any way? Any advice and help would be greatly appreciated!


texts:
Given a bipartite graph $G=(U,V,E)$, find a maximum matching.

Algorithm G:

Let $S\gets\emptyset$
Mark all edges unmatched
For $i\gets1$ to $|E|$

If $i$ is unmatched

$S\gets S\cup\{i\}$

End If

End For

Proposition:
   Algorithm G is optimal.

Proof: Feasibility is easy by induction. We prove that $|S|$ is maximum. By contradiction. Assume that there exists a set $S'$ of edges that has more edges than $S$. Since $S$ is maximal, then no edge could have been added to it without violating its feasibility. Thus, $|S|$ cannot be increased. Since $|S'|>|S|$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?


texts:
I am new in this field. In the book Foundations of Machine Learning by Mehryar Mohri, Afshi Rostamizadeh, and Ameet Talwalkar. The authors define the generalized error of a hypothesis as

$ R(h) = \Pr_{x \sim D}[h(x) \neq c(x)] = E_{x \sim D}[1_{h(x) \neq c(x)}]$

which is a number. However in the Definition 2.3 a concep class $C$ is said to be PAC-learnable if

$Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] \geq 1 - \delta$

for any $m \geq poly(1/\varepsilon,1/\delta,n, size(c)) $. Since by definition $R(h) = \Pr_{x \sim D}[h(x) \neq c(x)]$ is a number, What does this mean $Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] $ and $h_{S}$ in formal terms? The authors explain that $h_{S}$ depends on the sample $S$, but the question is how?

Another reason I have this question is due to the fact that every $h$ is defined as a function $h: \mathcal{X} \to \mathcal{Y}$ and the distribution $D$ is defined on $\mathcal{X}$, not on the hypothesis set $H$ where for each $h \in \mathcal{H}$, $h: \mathcal{X} \to \mathcal{Y}$.


texts: How to find the least optimised database query?

texts:
A library uses a relational database to store data about library books, their members and lending (books, which are currently borrowed). The database relations of this system are given below. Lengths of attributes are given within brackets.

Book(bookno(13), title(20), author(30), edition(7))
Member(memno(4), name(26), category(5), address(40), phone(15))
Lending(memno(4), bookno(13), duedate(8))

  The library database currently has 10,000 book tuples and 1,000 member tuples. Assume that 400 book borrowings are on record and 10 copies of the bookno "81-203-1257-0" is on lend.

  The following SQL query has been written to retrieve borrower's name with due date given the book no "81-203-1257-0".

SELECT m.*, l.*
FROM Member m, Lending l
WHERE m.memno = l.memno and bookno = "81-203-1257-0";

  The following are relational algebra expressions to retrieve the information for the above query.

  JOIN(Member and Lending Over memno) where bookno="81-203-1257-0")
  JOIN(Member and (RESTRICT Lending where bookno="81-203-1257-0") over memno
  CARTESIAN(Member and Lending) where bookno="81-203-1257-0")
  RESTRICT(CARTESIAN (Member and (RESTRICT Lending where bookno="81-203-1257-0")) where Member.memno=Lending.memno
  PROJECT m.*, l.* (RESTRICT Member m and Lending l where m.memno = l.memno and bookno = "81-203-1257-0")

  which one is the least optimised and how to compare with it others?

I am newly comer to db and query optimization setup , I hope some expert, explanation answer with query trees?


texts:
As far as I am aware of, the beta-rule of the natural numbers type nat states that (please correct me if I am wrong)

natrec 0 t0 (lambda i ti. ts) := t0
natrec (succ k) t0 (lambda i ti. ts) := (fun i ti. ts)

But what does the eta-rule says? I wonder how the following formulation is correct / accurate / complete

natrec n 0 (lambda i ti. s i) := n


texts: Proving that it is undecidable if a Turing machine accepts a language that is its own reverse

texts: I have a Turing machine M. How can I prove that $L(M) = (L(M))^R$ is decidable by constructing a Turing machine that can do this? I know how to figure out if two DFA's accept the same language (using the symmetric difference) however I don't believe it works for Turing machines. Now I am able to design a Turing machine where, for a string w, I can determine whether or not the reverse of w is also accepted by the language. The problem is that I'm having trouble determining if the set of all strings is the same as the set of all reverse strings. If I design another TM then I feel like it's just going to infinitely loop. So how can I prove that this is decidable?


texts:
Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval.

What is a fast algorithm to find
$\{ k\oplus x\mid x\in [a..b]\}$ as a union of set of integer intervals.

One can prove that $[a+k..b-k]\subseteq \{ k\oplus x\mid x\in [a..b]\}$ by showing that $x-y\leq x\oplus y \leq x+y$.

Edit: I should specify the actually input and output to remove ambiguity.

Input: $k, a, b$.

Output: $a_1, b_1, a_2, b_2,\ldots,a_m,b_m$. Such that:

$$
\{ k\oplus x\mid x\in [a..b]\} = \bigcup_{i=1}^m [a_i..b_i]
$$


texts: How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma

texts:
Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?
Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one should be proved as false by considering the given language as regular by proof by contradiction.


texts: Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n))

texts:
Here is the question again : Give an example of two increasing functions f (n) and g(n) from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n)).
I tried with several functions such as sine and cosine, but they are not increasing functions but Oscillatory. Then I tried x + sinx and x + cosx. However for sufficiently large coefficients c and n0, they also fail two satisfy the criteria. I am starting to doubt if such pairs of functions even exist !?


texts:
Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?

I recently implemented a rope data structure in Lua as an AVL tree.

However, I realized a since the ropes are not interned, they can't be used efficiently as keys in a dictionary. (Lua walks over all new strings made by concatenation or slicing in order to intern them, making these $\Theta(n)$ operations, but guarantees fast dictionary lookup by only comparing addresses)

Can AVL tree ropes (or another type of balanced tree) be interned in a similar fashion in better than $O(n)$ time? Can fast interning be proved impossible?

Below is what I have thought of so far. I haven't found any resources about interning non-string data structures.

Hashing: You can efficiently determine the hash value of a concatenation or a slice with extra bookkeeping for some hash schemes (like Java's). However, you can't guarantee there are no collisions in these hashes (and actually their slicability/concateability can make them very easy to attack).
Normalizing: There are many different shapes that AVL trees with identical contents can take on. I could try to pick one special form for each size and designate it as the "canonical" form. When new trees are made when concatenating or slicing, in addition to balancing the tree, we reshape it to its canonical form. Naively this should not be efficient, because the vast majority of forms for a given size are $O(n)$ edits away from any particular canonical form. However, maybe if all subtrees are given some particular form, canonicalizing can be made efficient.

I tried the obvious perfectly-balanced tree as the canonical shape, but I couldn't make an efficient way to concatenate these. Another version I considered was "as left leaning as possible" but this had the same result.


texts:
Let $W(n)$ and $A(n)$ denote, respectively, the worst case and average case running time of an
 algorithm executed on an input of size $n$.
 Which of the following is always true?
(A) $A(n) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$

Answer: (C).

  What do all these options "mean"?
  I find it hard to reconcile the graphs exemplifying asymptotic notation and abstract situations such as this one.


texts: Remove duplicates of first elements of pairs

texts:
A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element it comes with. I am looking for an efficient solution that returns the pairs sorted.

>>> myfunc([[2, 0], [3, 0], [4, 0], [5, 0], [3, 2], [4, 0], [5, 3], [5, 3]])
[[2, 0], [3, 2], [4, 0], [5, 3]]


texts: How to calculate IV, EV and optimal k for K-means?

texts:
Could someone explain how to calculate the following 3 evaluative properties:

Intercluster Variability (IV) - How different are the data points within the same cluster
Extracluster Variability (EV) - How different are the data points that are in distinct clusters
Optimum value of k

The third one I believe is by min EV/IV

Anyway please advise.


texts: Need for Functions to be Increasing in Non-deterministic Time Hierarchy Theorem

texts:
I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here:
http://theory.cs.princeton.edu/complexity/book.pdf : page 67
https://blog.computationalcomplexity.org/2011/04/new-proof-of-nondeterministic-time.html
It seems to me that we need $f$ and $g$ to be increasing functions, in addition to the usual assumptions that $f(n+1)=o(g(n))$ and time-constructibility.
In the Arora-Barak proof, we divide the natural numbers into disjoint intervals. I'm not sure how one can find, given a number $n$, which interval it lies in, without assuming that functions are increasing.
In the Fortnow-Santhanam proof, this is needed to ensure that $t_1(i+m+2)$ (which I believe may be a typo and should be in terms of $t_2$) can be computed in time $O(t_2(n))$.
Just for reference, I also posted this on cstheory stackexchange here:
https://cstheory.stackexchange.com/questions/48318/increasing-functions-in-non-deterministic-time-hierarchy-theorems


texts: How to find out the complement of a language of turing machines?

texts:
With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example.

L={M∣M is a TM that halts on empty tape after even transition steps}
What's the complement of L would it be:

L={M∣M is a TM that does not halt on empty tape after even transition steps}
L={M∣M is a TM that halts on empty tape after odd transition steps}

Please give me your train of thought when coming up with a complement for an automaton.


texts: Least computationally expensive bitwise addition

texts: I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve simple addition modulo 2^n using bitwise operators.


texts: Finding the lower bounds of an algorithm

texts:
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.

For eg, I have the following algorithm

For i=1, 2,...,n
    For j=i+1, i+2,...,n
        Add up array entries A[i] through A[j]
    Store the result in B[i, j] Endfor
Endfor

How do I calculate the lower bounds of this algorithm


texts:
For a long time, computer scientists and logicians have noticed that law (statutes, contracts, adjudication, etc), has some similarity with formal logic and programming languages, and have approached law as a CS problem (computer scientists have used deontic logic to model legal documents, and have applied object-oriented design principles to analyse the "code" of legal documents, or have proposed how to translate legal documents into logic programs.)

One of the underlying interests of such research is the possibility of automating (parts of) law, and of writing contracts and laws as more unambiguously specified "code" (rather than semi-formal natural language).

But one of the problems with some of the earlier such CS research was that it ignored the fact that there is a complex, non-logical relation between legal concepts and the real world. For example, to decide whether a certain course of action by a person was "reasonable", cannot be decided on the basis of pure formal logic, yet it does have practical legal meaning.

There have at least been some proposals to solve this using machine learning (a deep neural network might decide whether a course of action was "reasonable").

I have delved into this research for a short amount of time, but I find it hard to recognize which sources are considered respectable, or out-of-date. (e.g. there has been some criticism of a lot of the work in the 80's, but I am not sure what the view is of current computer scientists working on this).

My question is the following: What are up-to-date and respectable sources for the theoretical study of law as a computer science problem?

I'd prefer to read texts that recognize how there are both symbolic/logical and non-symbolic elements of law, and think seriously about this relation. But as a secondary option, I'd also be interested in landmark references that study the topic from a more narrow perspective.
It is not necessary for the sources to be completely formalized. i.e. relatively more conceptual work is also welcome.
I'd especially like to know what the landmark papers and books are on this topic.


texts: Why quicksort instead of a B-tree construction?

texts:
As far as I know (despite some variations which provide empirical average-case improvements) quick-sort is worst case $O(n^2)$ with the original Hoare partition scheme having a particularly bad behavior for already sorted lists, reverse-sorted, repeated element lists.

On the other hand a B-Tree has $O(\log n)$ insertions, meaning worst-case $O(n\log n)$ to process an array of $n$ elements. Also an easy optimization to memoize the memory-address of the lowest and highest nodes (would make it possible to process sorted / reverse-sorted / repeated-element lists in $O(n)$).

While there are more favored sorting algorithms than quicksort now (e.g. timsort) what originally favored its use? Is it the susceptibility to parallelization (also in place swaps, lower memory complexity)? Otherwise why not just use a B-tree?


texts: Simple fixed block size allocator and block header

texts:
Let's say I want to implement my simple version of free/malloc

Let's assume I got a huge chunk of memory where I manage my free/malloc there.
and also I can only allocate fixed block size on each malloc (1 byte for example).

So in general I keep "free list" of free addresses of one byte, so whenever somebody do malloc, I just return the address in the head of list and take out the head .. (head=head->next) .

and when a user does free(ptr) I just add that address to the head of the list.

So both actions are $O(1)$.

Now, I see some implementation that puts "header" before each data to keep the next pointer there, and I don't understand why is it doing so? Because it's complicating things a bit, and I can't see where the advantage of doing that comparing to just use Linked list in different memory area.


texts: NP-hardness of an optimization problem with real value

texts:
I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$.

I have been able to reduce an NP-complete problem to my own problem in polynomial time. I also showed that my problem is NP.

Since the input to the decision problem is a real value, is this reduction valid and can I categorize my problem as NP-complete?

Edit: What if the precision of this real number is limited to $\frac{1}{polynomial(n)}$, which means that the solution is a real number with a polynomial precision.


texts:
I know that I cannot use Floyd's algorithm if I have a graph with at least one negative cycle, because
path-lengths between vertices can be arbitrarily small.

I am wondering, how the distance matrices at each iteration of $k$, where $k=0, \dots n$ will look like.
I now that there will be negative numbers on the main diagonal, but I do not know where they will be. Could somebody explain it to me, please?

I have example with 4 vertices and I know that matrix for $k=0$ is the same as in the case that there are no negative cycles in a graph.

My example (but you can use another graph):

Matrix for $k=0$ is:

\begin{bmatrix}
0 & -4 & \infty & 3 \\
1 & 0 & \infty & \infty \\
\infty & 2 & 0 & \infty \\
\infty  & \infty & 5 & 0
\end{bmatrix}


texts: Is there any kind of CPU which doesn't contain an ALU ?


texts:
I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but never has the occurrence of 123.

((1 or 3)*(211 or 231 or 233 or 2211 or 2231 or 2233))* 222

is as far as I could get, I can't see how to prevent 123 from happening while still allowing a string like 1223221222 to occur. Any thoughts?


texts: How to find the loop invariant in hoare triples

texts:
Hey I am new to Hoare triples, and I can't understand on finding the loop invariants in hypothesis. For example this while loop

[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].

The invariant is [2x + y > 5] but I don't understand on how to find it. A step by step explanation on how to find it will be greatly appreciated.


texts:
a spin lock solution to the critical path problem is shown below . my question is will this or will this not  result in starvation ?

    Thread A                Thread B
leave note A;           leave note B;
while (note B) {\\X     if (noNote A) {\\Y
    do nothing;             if (noMilk) {
}                               buy milk;

if (noMilk) {                  }
    buy milk;           }
}                       remove note B;
remove note A;

let me illustrate my point ,if thread A and B are scheduled as shown wont that result in starvation ?

note : those arrows are meant to indicate a cycle .

note: I'm following the online operating system course from Berkeley (http://www.youtube.com/playlist?list=PL-XXv-cvA_iCrnl0625nXp4GimjT-cv_1) .

In lecture 4 ,they talk about this as a correct solution to the critical path problem


texts: how to prove that a language is regular?

texts: I know that this language is not regular L = {w | na(w) = nb(w)} where na(w) is the number of a's in w. But what if now the language changes to that the number of a's has to be greater than b's? I think not, because we do not have finite number of prefix equivalence class. And in that case, how can I prove it? Or if it was regular, how would it be?


texts: Can abstract syntax trees be unparsed in subexponential time?

texts:
Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. parse(unparse(AST)) = AST should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

Questions

Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

I didn't receive an answer for this question on StackOverflow. It was suggested to ask here, but I hate redundancy, so I hope you forgive me for asking you to answer here.


texts: Non-deterministic Turing machine and palindromes

texts:
I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$.

I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(n)$ time – and then check both tapes (one from beginning and the second from the end) – $O(n)$ time again.

However, I can't picture how to do such procedure in a non-deterministic TM using only one tape. All the procedures I came up with take $O(n^2)$ steps. How can the non-determinism reduce the running time here?


texts:
I'm looking for a collection of SAT problems that are usable for a test suite, i.e.:

are small/easy to solve, that is, this is not a benchmark but a correctness test suite
some satisfiable, some unsatisfiable
answer and a possible assignment (for sat. ones) is known

All I find online are collections of benchmarks but heavy formulas are not what I need.
Any link?


texts: Given a binary min-heap, find the $k$-th element

texts:
I'm given a binary min-heap (implemented with an array) and need to come up with a (simple) efficient (no more than $k$ comparisons) to find the $k$-th minimal element.
My attempt was as follows:

check who is the smallest among the root children
scan the corresponding sub-heap maintaining a counter counting how many nodes are smaller than the larger child of the root (but larger than the smaller child). If the counter reaches $k-1$ return the value of the current node. other-wise after the scan is finished, call this method recursively on the larger root child to find the ($k$ $-$ couter_value + 1)-th minimal element of the larger child.

I just can't put this together formally and not sure this can be implemented with no more than $k$ comparisons.
Thanks for any help.


texts: Relationship between functions and formal languages?

texts:
PR is defined as "the complexity class of all primitive recursive functions"
and also equivalently as "the set of all formal languages that can be decided by such a function". (wiki:http://en.wikipedia.org/wiki/PR_(complexity))

Unfortunately I fail to understand, why these two are equivalent?


texts: Equivalence relations with $\cap$, $\cup$ and $\circ$

texts:
I have the relations $E_1$ and $E_2$.

A reflexive, symmetric and transitive property shows that two relations are equivalent to each other. I need to prove if this is true for the following

a) $E_1 ∩ E_2$

b) $E_1 ∪ E_2$

c) $E_1 ∘ E_2$

I found out that a) is true, but I am not sure about it.
This is my proof for transitivity:

$E_1 ∩ E_2 ⇒ (a, b, c) ∈ E_1 ∧ (a, b, c) ∈ E_2 ⇒ \\((a, b) ∈ E_1 ∧ (b, c) ∈ E_1 → (a, c) ∈ E_1) ∧
((a, b) ∈ E_2 ∧ (b, c) ∈ E_2 → (a, c) ∈ E_2)$

Also I found different arguments on the internet, so I'm pretty unsure about this.

Regarding b) $E_1 ∪ E_2$ a friend found out that this is not transitive and they wanted to prove it with an example.
The example is the following:

$A = \{1,2,3\}$

$E_1 = \{(1,2), (2,1), (2,2)\}$

$E_2= \{(1,3), (3,1), (3,3)\}$

$E_1 ∪ E_2 = \{(1,2), (2,1), (2,2), (1,3), (3,1), (3,3)\}$

This is transitive, isn't it? If not, what is it what I did not understand?

And maybe you can help me with with c), as well.


texts: Upper bound on the number of subgraphs in a tree

texts:
Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.
For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$,
$\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and
$\{S,T,B,H,G,Q\}$.
I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.


texts: Using bit arrays to solve crossword puzzles

texts:
I  have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data structure described on page 3, under "Lexicon". Could someone please give me an example?

PS: I have already implemented an efficient crossword solving algorithm but now I want to get even more serious in this difficult task.


texts: Chord protocol - How should I go about mapping nodes to placeholders on the ring?

texts:
In the real world, how is a node mapped to the position on the ring,
Each nodes's IP address is hashed using SHA-1 hashing algorithm which will produce this hash - 73.128.154.69 hashed into 60CBFB98C9052A425D684A2C3D8D8D38424129A3.
This should have been in the range of 0 to (2^m) - 1 where m is the number of bits. I have the following questions -

How should I convert this hashed value into a number?
Will the IP address after leaving and re-joining the ring get the same  placeholder position?
Are placeholders or node positions ordered numbers at all?


texts: Understanding pipeline stalls (bubbles) based on stage

texts:
I'm currently reading through x86 Assembly Language and C Fundamentals and came across this statement in the second chapter of the book:

  If the instruction required is not available in the cache, then a cache miss occurs, necessitating a fetch from main memory.  This is referred to as a pipeline stall and delays processing the next instruction.  Information is passed from one stage to the next by means of a storage buffer.

Having read the Wikipedia article associated to this, and the book covering one paragraph of this subject that I can find, I have a few glaring questions regarding this.

Would a pipeline stall occur if there were no further instructions to fetch from main memory, and if so, would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?
Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?
If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle for both/all of the stages that's trying to use the resource, or is there specificity involved based on stage that would allow for one of the stages to complete its instruction given that the cycle was the cycle in which the pipeline stall occurred?

Note: I'm not formally educated in Computer Science so I apologize if these are CS101 questions.


texts:
I am trying to work out the time complexity of my function but I'm not sure how it works with powers.
I've got $y=(\frac{x}{3})^n$ as one of my lines. How many basic operations is this? Would it be 2(n-1) for the power then 1 for the division and 1 for the assignment of y?
Also, is the square root of a number just 1 basic operation?


texts: Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity language? I also want to have consider $x_1+x_2\bmod N = x_1\bmod N+x_2\bmod N$ and $x_1x_2\bmod N = (x_1\bmod N)(x_2\bmod N)$.


texts: Info about dataset from which a Huffman tree was generated

texts:
I know that given the following huffman tree:

you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a level has a occurence that is greater than or equal to the rightmost?


texts: Selection over combinatorics that satisfies a distribution

texts:
I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.

Here is the problem :

Consider a list of M sets that ( M = 10000 )

each set contains integers in range 1... N. (Let's say N=50)
each set has the size of K. ( Let's say K=10)
each element in the set is distinct.

Sample sets are

{ 1,2,3,4,5,6,7,8,9,10}
{ 2,4,5,7,9,11,13,15,20,25}
{ 4,5,8,12,16,30,41,42,45,49}
{ 2,6,11,18,24,27,31,36,39,43}

....

{ 3,5,8,17,19,23,34,37,38,46 }

You should select L sets(Let's say L=1000) from given 10000 sets. This selection must approximately satisfy a distribution table like below

1=> 100 %
2=> 80 %
3=> 100 %
4=> 15 %

...

50=> 20%

It means that 1 should occur in all selections, 2 should occur 80% of the selections and goes on ... I will try to solve the problem by trying a random-walk algorithm that exchanges a set in each iteration.

I'm sorry if I did not express my problem well. It would be great if you could share similar problems with mine or could express your approach to the problem.


texts: What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

texts:
In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that

$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$.

However, I went through the following steps to conclude that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(\log{n})$. Where did I go wrong?

First, note that ${n \choose \frac{n}{2}} = \frac{n!}{\frac{n}{2}!\frac{n}{2}!}$. By basic logarithm laws, we get that this is equal to $\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)}$. From this it follows that:

$$
\mathcal{O}(\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)})\\
= \mathcal{O}(\log{(n!)}) \\
= \mathcal{O}\Big(\log{\big(n(n-1)(n-2)\cdots(1)\big)}\Big) \\
= \mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)
= \mathcal{O}(\log{n})
$$

So, what is wrong here? I've gone over it for a while and I can't see any mistakes. Plotting these functions, though, I can see quite clearly that there must be a mistake.


texts: Understanding of Turing's Answer to the Entscheidungsproblem

texts:
I apologize if this question has been asked before, but I was not able to find a duplicate.

I have just finished reading The Annotated Turing and I am a bit confused.

From what I understand, the Entscheidungsproblem is whether or not an algorithm exists that can determine whether a statement is provable. In the paper, Turing defines a K machine that will prove all formulae that are provable. This seems almost like a resolution to the problem, but later Turing writes:

  If the negation of what Gödel has shown had been proved, i.e. if, for
  each A, either A or -A is provable, then we should have an
  immediate solution of the Entscheidungsproblem. For we can invent a
  machine K which will prove consecutively all provable formulae.
  Sooner or later K will reach either A or -A. If it reaches A,
  then we know that A is provable. If it reaches -A, then, since
  K is consistent (Hilbert and Ackermann, p.65), we know that A is not provable.

Gödel's Theorem showed that some statements are true, but not provable. I guess what I don't understand is how Gödel's result prevents Turing's K machine from being a solution to the Entscheidungsproblem. Is it just as simple as that there are some formula that the K machine will never encounter, so it will keep running forever and never conclude that the formula is unprovable?


texts:
Exactly 1 in 3SAT (X3SAT) is known to be NP-Complete. It remains NP-Complete even if we only consider instances that are monotone and linear. Monotone means all of the literals are positive. Linear means no two clauses share more than one variable in common. If $n$ is the number of variables then the maximum number of clauses for $n$ is $O(n^2)$.

Let $m$ be the number of clauses in a linear, monotone X3SAT instance. There is only one instance each for $m=1, 2$. There are $2$ instances with $3$ clauses and $4$ instances with $4$ clauses.

(a,b,c)(c,d,e)(e,f,g)(d,h,i) - 3-chain with branch

(a,b,c)(c,d,e)(a,d,f)(f,g,h) - 3-loop with branch

(a,b,c)(c,d,e)(e,f,g)(g,h,i) - 4-chain

(a,b,c)(c,d,e)(e,f,g)(a,g,h) - 4-loop

Has there been any research into the maximum number of distinct monotone, linear X3SAT instances with $m$ clauses? By distinct I mean the ordering of the variables is ignored. Also assume the instance is connected.

Some corrections. There are 3 instances with 3 clauses and 6 instances with 4 clauses.

(a,b,c)(c,d,e)(e,f,g) - 3-chain

(a,b,c)(c,d,e)(a,d,f) - 3-loop

(a,b,c)(a,d,e)(a,f,g) - 3-star

(a,b,c)(c,d,e)(e,f,g)(g,h,i) - 4-chain

(a,b,c)(c,d,e)(e,f,g)(a,g,h) - 4-loop

(a,b,c)(a,d,e)(a,f,g)(a,h,i) - 4-star

(a,b,c)(c,d,e)(e,f,g)(d,h,i) - 3-chain with length 1 branch

(a,b,c)(c,d,e)(a,d,f)(f,g,h) - 3-loop with length 1 branch

(a,b,c)(a,d,e)(a,f,g)(g,h,i) - 3-star with length 1 branch


texts: Computing morphic word produced by uniform morphism

texts:
Let $\Sigma = \{a,b,c\}$, and consider the function $f\colon \Sigma \to \Sigma^*$ given by $f(a) = abc$, $f(b) = bac$, and $f(c) = cba$. We can extend $f$ to $\Sigma^*$ in the obvious way. Since $f(a)$ starts with $a$, it can be shown inductively that $f^{(n-1)}(a)$ is a prefix of $f^{(n)}(a)$ for every $n$, where $f^{(n)}(a)$ is the result of applying $f$ on $a$ for $n$ times:
\begin{align}
&f^{(0)}(a) = a \\
&f^{(1)}(a) = abc \\
&f^{(2)}(a) = abcbaccba
\end{align}
and so on. Hence the sequence $f^{(n)}(a)$ converges to an infinite limit word $f^{(\infty)}(a)$.

How do I compute the $i$'th symbol of $f^{(\infty)}(a)$?


texts: What precisely differentiates Computer Science from Mathematics in theoretical context?

texts:
I am a university level student of Computer Science having a great passion to study Mathematics. I have a firm belief that Computer Science or Theoretical Computer Science is a direct branch of Mathematics and Logic and also of the opinion that a Computer Science degree has always to be Math oriented as a matter of fact. Please correct me if I am wrong.

I frankly feel that there isn't a lot of difference in the 2 subjects to be frank as every "computation" involves "calculation", although every "calculation" might not be a "computation". Again please provide substantial information and evidence and do update me if I am mistaken here. Thank you


texts: Is call stack compile time or runtime detail?

texts:
I'm sorry if the question is quite naive, but I don't understand if a call stack is a language implementation detail or it depends on OS?

What I'm trying to understand is what decides how to store local variables and parameters of a function - the language's compiler or OS while running the application? Is it possible to write a C compiler, let's say, for Windows so that it won't be stack based? Or the language syntax dictates us that it must be stack-based language?

Sorry if I say something wrong, just trying to get the basic idea how everything works.


texts:
Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$

Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
If $NP=P$, does $MAX-CLIQUE\in P$?

I cannot think of a polynomial verifier for $MAX-CLIQUE$'s complement. There might not be a max clique of size k due to two reasons:

There's a bigger clique than k (and then the verifier will get such clique and verify it).
There's no clique of size k in the graph (and this is cannot be verified in polynomial time).

Regarding the second question: it's known that $MAX-CLIQUE$ is just $NP-HARD$ and not $NP-COMPLETE$. I understand from that that probably $MAX-CLIQUE \notin NP$, therefore even if $P=NP$, so $MAX-CLIQUE \notin NP=P$.
So does it mean that the answer to all the question is simply "no"?


texts: Order Notation - Why can't $c$ be in terms of $n$?

texts:
For $f(n)$ to be in $O(g(n))$, there must exist a $c > 0$ and $n_0 > 0$ such that

$$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\,.$$

I found a solution to a question where my $c$ is in terms of $n$, but my friend says you can't have that. I'd like to understand why.
My thought process is: if I am given an $n$, I can pick a distinct $c$ that will satisfy the requirements above by using the $c$ in terms of $n$ relationship.

Thank you.


texts: How to check if a specific ILP problem can be solved in polynomial time or not?

texts: How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?


texts: Prove that Big-O is transitive by relation. What does it mean by 'by relation'?

texts:
Prove $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

The question is

  Prove that Big-O is transitive by relation.

What does it mean by by relation??


texts: Algorithm Sequence classification(anomaly detection)

texts:
I have a problem statement where i am having many inputs lets say A,B,C,D.... and this inputs can take any real value(e.g A-a1,a2,a3, B-b1,b2). Now, i have file which will be have record of the all the inputs and there values at given point of time. I also know what should be the specific sequence for example A-a1,B-b1,C-c1. So, now my job would be to read the file and find whether anywhere the above sequence break. i.e. after A-a1,B-b2 came.

What would be the standard approach for solving this type of problems ? I have explained in simple terms but the inputs can be in 1000's and also the sequences will not be always simple it can contain many paths(for e.g sq1 - A->B->C->D..sq2 - A->B->E) etc. I am thinking of sequence classification but all the examples always state that we should have training data but for me there is no thing as training data it is a truth table.(It is other thing that many combinations can happen of the truth table)


texts:
Is it possible to solve every problem (solvable with turing machine) with only recursion ?
If yes, which principles or theories assure this ?
Thanks


texts:
I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are simple, and look something like this:

A -> aX | aY
becomes:
A -> aZ
Z -> X | Y

I understand that. However, my grammar looks more like this:

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

I'm not sure how to apply the simpler example to this. I've been trying for at least a couple of hours and I've lost track of all of the things I've tried. Generally, my attempts have looked something like this:

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

And I then try to convert the E rules into ones having only one production starting with + or -:

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

And then...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

And so on. But I continually end up with a lot of extra nonterminals, and some very long productions / chains of productions, without actually having left-factored it. I'm not sure how to approach this - I can't seem to eliminate some nonterminal having multiple productions starting with a + and with a -.


texts: What types of images should I use for negative examples in a classification problem?

texts:
I am doing a project to recognize a kind of leaf using ANNs with Emgu CV in C#. My project is to get frames from camera then present them to the ANN and have the ANN tell me if that frame contain a leaf or does not contain a leaf.

I am using 1000 images of leaves that I want to recognize, so if the frame contain a leaf, the ANN will tell me that frame contains one.  I do not know what kind of images I should use for the second class. I want to use images perhaps, for example, like pens, rocks, or telephones all together in the second class.


texts: A Question related to the method of find lower bound : Trivial lower bounds

texts: In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the sum of these two found numbers. My question is , we know that the time complexity = number of times the basic operation is repeated as a function of the input size * the time it is taken to preform the basic operation once. So as we can see from the formula of the time complexity that it depends on the basic operations  not on the number of inputs and output items. So how does the trivial solution is used to compute the lower bound ( worst time complexity of best algorithm) then ?


texts: Rule of thumb to know if a problem could be NP-complete

texts:
This question was inspired by a comment on StackOverflow.

Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like an NP-complete one?

I am not looking for something rigorous, but to something that works in most cases.

Of course, every time we have to prove that  a problem is NP-complete, or a slight variant of an NP-complete one; but before rushing to the proof it would be great to have certain confidence in the positive result of the proof.


texts: Question about RNN detecting toxic spans

texts: How can an RNN be used for detecting toxic spans (spans of words containing toxic language) in a social media comment? Specifically, what should be the input to the RNN at each time step t? How many outputs (i.e., yˆ) are produced given a comment containing n words? What is each yˆ(t) a probability distribution over?


texts: Indexing a huge dataset (that does not fit into central memory)

texts:
The problem.
Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are huge. In particular, neither the entire file nor the list of all distinct strings fit into central memory. The global file may be parsed and/or sorted (in external memory) a few times, though.
The goal is to build the file in which line $i$, for $i=1..m$, is integer $k$ if the string on line $i$ in the original file is the $k+1$-th distinct string appearing in the original file.
Example.
For instance, if the original file is:
bbb
cccc
cccc
bbb
aaa
ee
aaa
fff
dddd
cccc
bbb
fff

then $n=6$, $m=12$, and we should obtain:
0
1
1
0
2
3
2
4
5
1
0
4

My approach.
I take benefit of standard unix command-line tools, as follows.
I first build a numbered string occurence file:
zcat input.gz | awk '{print NR-1,$0;}' | gzip -c > occurrences.gz

I use it to build an index file for strings that respects occurence rank, and starts with character '-', lower than any occurence number:
zcat occurrences.gz |
  sort -T. -S1g --stable -k2,2 |
  awk 'BEGIN{old="none";}{if ($2!=old) print $0; old=$2;}' |
  sort -T. -S1g -nk1,1 | awk '{print "-",$2,NR-1;}' |
  gzip -c > index.gz

I merge the two files and sort the result to ensure that the line with a string index will be just before all other lines containing this string; I then replace each string, sort according to occurence rank, and I am done:
zcat occurrences.gz index.gz |
  sort -T. -S1g -k2,2 -k1,1 |
  awk '{if ($1=="-") i=$3; else print $1,i;}' |
  sort -T. -S1g -nk1,1 |
  cut -d" " -f2 |
  gzip -c > result.gz

Technical detail: to avoid encoding issues, first set environment variable LC_ALL to C.
Question.
Is it possible to do significantly better than my approach, or to achieve similar performances with a significantly different approach, in practice?
Notice that I am not interested in minor, technical improvements, like using mawk, sed, etc, instead of awk. I am not interested in a purely theoretical solution either, that would be better asymptotically but would turn out to be so complex than no implementation is reasonably feasible.
Instead, my concern is the relevance and overall effectiveness of my approach, or variants.
For instance, would any external memory data structure be faster, while using as little memory, with available implementation?


texts: Prove or disprove the bound given the recurrence relation

texts:
Given the following recurrence relation,

$T(n) = 2 T(\frac{n}{2}) + f(n)$,

where $f(n) = \Omega(n^2)$, I'm asked to prove or disprove that $T(n) = O(f(n))$.

If I'm allowed to restrict my discussion within the special cases in which that $n = 2^k$ for positive integer $k$, how can I prove or disprove the proposed bound, $T(n) = O(f(n))$?

As a side information, if $f(n) = \Theta(n^2)$, then we can show that $T(n) = \Theta(f(n))$ by the Master Theorem. But how should I handle the subtlety of this case with big-Omega and big-O?

Thanks for the help.


texts: Definition and example of search problem

texts:
I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me.
WIKIPEDIA:

In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if:
If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them)
If x is such that there is no y such that R(x, y) then T rejects x

If anyone can explain it to me easily and give a few examples, it will help me a lot.


texts:
Consider the following language:
$$
L = \{ G | G \text{ has a VC of size at most } \log n \}
$$

Does $L\in P$ or $L\in NPC$?


texts: Prove { | TM M on input 3 at some point writes symbol "3" on the third cell of its tape} is recursively enumerable but not recursive

texts:
Question: Let $$S =
\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape}
\}.$$ Show
that $S$ is r.e. (Turing acceptable) but not recursive (decidable).

I'm bit confused about this question, I'm not even sure how exactly should I start an approach to it. As I study from Sipser's book, in general when we prove a language is undeciable, we use contradiction to show that if $S$ is decidable, then by doing some trick, $A_{\text{TM}}$ is also decidable but it's not. Thus, $S$ is not decidable. However, this question also asked to show $S$ is acceptable. I'm thinking if we show that $S$ is undecidable, it's sufficient to see that $S$ is acceptable?(I'm totally not sure) Any suggestion?


texts: Operating Systems TestAndSet instruction

texts:
I was reading operating systems concurrency control topics where I came across TestAndSet() intruction. I first referred this book. But it has got very less coverage on TestAndSet and then I googled. Obviously I came across wiki page.

The wikipedia page gives two code excerpts.

The TestAndSet() function

#define LOCKED 1

int TestAndSet(int* lockPtr)
{
   int oldValue;
   oldValue = *lockPtr;
   *lockPtr = LOCKED;
   return oldValue;
}

Lock() built using TestAndSet()

function Lock(boolean *lock)
{
   while (test_and_set(lock) == 1);
}

I have two doubts:

It seems that the TestAndSet() does not actually have test, it does contain only set part and Lock() contains the set part. Is it like that?
Below first excerpt, wikipedia page days:

  The code also shows that TestAndSet is really two operations: an atomic read-modify-write and a test. Only the read-modify-write needs to be atomic. (This is true because delaying the value comparison itself by any amount of time will not change the result of the test, once the value to test has been obtained. Once the code writes the initial value, the result of the test has been determined, even if it has not been computed yet)

Does that mean we can call TestAnsSet() inside Lock(), save its return value and test against that return value anytime inside Lock()?


texts: How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

texts:
I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.

Here is a citation from the book "Algorithms on strings, trees and sequences" by Dan Gusfield (section 6.5.1):

  "... the Aho-Corasick, Weiner, Ukkonen and McCreight algorithms all either require $\Theta(m|\Sigma|)$ space, or the $O(m)$ time bound should be replaced with the minimum of $O(m \log m)$ and $O(m \log|\Sigma|)$".

  [$m$ is the string length and $\Sigma$ is the size of the alphabet]

I don't understand why that is true.

Space: well, in case we represent branches out of the nodes using arrays of size $\Theta(|\Sigma|)$, then, indeed, we end up with $\Theta(m|\Sigma|)$ space usage. However, as far as I can see, it is also possible to store the branches using hash tables (say, dictionaries in Python). We would then have only $\Theta(m)$ pointers stored in all hash tables altogether (since there are $\Theta(m)$ edges in the tree), while still being able to access the children nodes in $O(1)$ time, as fast as when using arrays.
Time: as mentioned above, using hash tables allows us to access the outgoing branches of any node in $O(1)$ time. Since the Ukkonen's algorithm requires $O(m)$ operations (including accessing children nodes), the overall running time then would be also $O(m)$.

I would be very grateful to you for any hints on why I am wrong in my conclusions and why Gusfield is right about the dependence of the Ukkonen's algorithm on the alphabet.


texts: Can we find the largest intersecting subfamily of convex polygons in quadratic time?

texts:
Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (you can assume general position, no two vertices are the same, no edges intersects a vertex other than its endpoints, no three edges intersect at the same point).
I'm curious to know if you can you compute a subfamily of largest cardinality possible such that all polygons share a single common intersection point in $\mathcal{O}(n^2)$ time? (In the Real RAM model, i.e. you can store an arbitrary precision real number in a register and perform arithmetic operations on them in constant time)
The best I've managed to come up with is $\mathcal{O}(n^2\log(n))$:

I can modify the Bentley-Ottman algorithm (with the segments being the polygon edges) so that at every event point $p$, I count the number of "lower hull" edges and "upper hull" edges under $p$ on the sweep line (modifying my search tree so this can be done in $\mathcal{O}(\log(n))$ time) and compute the difference, giving me the number of polygons containing $p$. I simply keep track of the "best" point $p$, then test every polygon against $p$ in $\mathcal{O}(n)$ total time.

Alternatively, by computing the $\mathcal{O}(m^2)$ points which are the leftmost in the intersection of a pair of polygons (which can be shown to be doable in $\mathcal{O}(nm)$ time) and then counting the total number of polygons which contains each point (in $\mathcal{O}(nm^2)$ time), you can solve the problem in $\mathcal{O}(nm^2)$ time, which is better for small $m$ (and you can probably also get $\mathcal{O}(n^\alpha m^\beta)$ for different values of $\alpha + \beta > 2$ using more sophisticated simplex range counting datastructures).
Is anything faster possible (asymptotically)?
Or is there some (conditional) lower bound showing that $\mathcal{O}(n^2)$ is hard/impossible to achieve?


texts: Number of IEEE 754 doubles between two adjacent single-precision floats

texts:
Between an adjacent pair of nonzero IEEE single precision real numbers, how many IEEE double precision numbers are there?

I was also wondering if this question has something to do with the hidden bit.

Can anyone help me?


texts: Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures

texts: Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to debug. But persistence requires more memory resources. On the other hand, wait-free versions of data structures guarantee that the crash of other threads will not affect the execution of a thread. Can anything be said about the circumstances that determine which solution is preferable?


texts:
I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization.

Am I understanding correctly? Or is DP something else?


texts: Counterexample to greedy solution for set cover problem

texts:
I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:

1-6. The set cover problem is as follows: given a set of subsets
$S_1,\dots,S_m$ of the universal set $U = \{1,\dots,n\}$, find the smallest subset
of $T \subset S$ subsets such that $\cup_{t_i \in T} t_i = U$. For example, there are the following
subsets, $S_1 = \{1,3,5\}$, $S_2 = \{2,4\}$, $S_3 = \{1,4\}$, and $S_4 = \{2,5\}$. The set
cover would then be $S_1$ and $S_2$.
Find a counterexample for the following algorithm: Select the largest
subset for the cover, and then delete all its elements from the
universal set. Repeat by adding the subset containing the largest
number of uncovered elements until all are covered.

My answer is as follows:

$S = \{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{5\}\}$, $U=\{1,2,3,4,5\}$.
The algorithm will use
the following sets: $\{\{1, 2\}, \{3, 4\}, \{2, 5\}\}$, while {{1, 2}, {3, 4}, {5}}$.
would be more minimal.

Do you think its correct? I assume here that algorithm minimizes number of uncovered elements in each iteration and not the entire size of set to choose – that's why it might choose $\{2,5\}$ instead of $\{5\}$.
I have found this answer online:

One counter-example consists of a series of subsets that increases in
size exponentially, plus 2 additional subsets that each cover half of
the elements. Example:
$S_1 = \{1,2\}$

$S_2 = \{3,4,5,6\}$

$S_3 = \{7,8,9,10,11,12,13,14,15,16\}$

$S_4 = \{1,2,3,4,5,6,7,8\}$
$
S_5 = \{9,10,11,12,13,14,15,16\}$
The greedy algorithm will choose
$S_3,S_2,S_1$, while the optimal solution is simply $S_4,S_5$.

My understanding is that the algorithm would choose $S_3,S_4$ and not $S_3,S_2,S_1$, since $S_4$ has more uncovered elements than $S_2$.


texts: Build transportation system to travel between cities

texts:
Given $n$ cities, I'm looking to build a transportation system that allows travelling between every two cities.
  For every two cities $i$ and $j$, a road can be paved in the cost of $c_{ij}$. Also, it is possible to establish an airport in city $i$ in the cost of $a_i$ (all costs are positive).
  One can travel between two cities if there is a road between them or if there are airports in both cities.
  I'm seeking for efficient algorithm to find transportation system in the minimal cost, such that it will be possible to travel between every two cities (Not necessarily directly).

My thoughts:

Generally, I thought to set $n$ nodes, one for each city, and connect each of them with weighted edges, such that the weight of each edge will be the cost of travel between two cities.

Then, I could run Kruskal's algorithm to find MST, which will be the transportation system I'm looking for.

I'm trying to figure out how to set the weight of every edge, which will indicate the cost of travelling between two cities.

First, I thought to calculate the $\min(c_{ij}, a_i + a_j)$, but then if I choose to establish an airport in some cities $i$ and $j$, it's going to effect the way I can travel between $i$ and some other city $k$.

So I got stuck in how to choose the weights of the edges, and I'm not sure how to continue from here.

EDIT: I thought of a different approach:

Build graph in which every node represents a node, and every edge's weight between two nodes (cities) $i$ and $j$ will be $c_{ij}$

In addition, I'll add another node which will be connected to all the other nodes, with weight $a_i$ to node $i$.

So the additional node will represent the airport.

Now, we can run algorithm to find MST, but this doesn't seem to work for some examples I've tried.

Any help appreciated.


texts: Proving Little-Oh notation by definition

texts:
I need to prove by definition (show that for every $C$ there exists a $n_0$) that: $$5n^2+3n= o(n^3-4n)$$

By trying to simplify the expression I get to the point where I should prove that: $$ \frac{5n^2+3n}{n^3-4n} < C$$.

Now, showing that $\lim\limits_{x\to\infty} \frac{5n^2+3n}{n^3-4n} = 0$ isn't a tough mission, but how do I prove it by definition? How do I point out specific $n_0$ for every $C$ that comes up? I'm asked to provide a tight answer and not let $n_0 = C^C$ so that the $n_0$ for sure will be large enough but to point out $n_0$ that is reasonably small.


texts:
I'm a bit confused about this question:

  "Multiple jobs can run in parallel and finish faster than if they had run sequentially. Suppose that two jobs, each needing 10 minutes of CPU time, start simultaneously. How long will the last one take to complete if they run sequentially? How long if they run in parallel? Assume 50% I/O wait."

Answer from textbook (Modern Operating Systems 4th edition by Tanenbaum)

  "If each job has 50% I/O wait, then it will take 20 minutes to complete in the absence of competition. If run sequentially, the second one will finish 40 minutes after the first one starts. With two jobs, the approximate CPU utilization is 1 − 0.52. Thus each one gets 0.375 CPU minute per minute of real time. To accumulate 10 minutes of CPU time, a job must run for 10/0.375 minutes, or about 26.67 minutes. Thus running sequentially the jobs finish after 40 minutes, but running in parallel they finish after 26.67 minutes."

I don't understand why it will take 20 minutes for each job to complete if the IO wait time is 50%. Doesn't that just mean 5 minutes of CPU time is spent waiting for I/O?


texts: Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

texts:
Problem

I have $J$ matrices $C_{j}$, which are $K \times M$.

Elements of each matrix $C_{j}$ are between 0 and 1.

I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that:

Elements of all matrices $A_{j}$ and matrix $B$ are between 0 and 1
$A_{j}B = C_{j}$ for all $j$.
Dimensions of each matrix $A_{j}$ is $K \times L$
Dimensions of matrix $B$ is $L \times M$
$L \lt M \lt\lt J$
$J$ is ~50,000. $K$, $L$, and $M$ are ~15.

Attempt

I thought about the following:

Randomly choose a matrix $B$ within bounds.
Fix $B$ and find least square solutions $A_{j}$ such that $A_{j}B \approx C_{j}$
Replace any element in $A_{j}$ that is not between 0 and 1 by a random value between 0 and 1.
Fix $A_{j}$ and find least square solution $B$ such that that $A_{j}B \approx C_{j}$
Replace any element in $B$ that is not between 0 and 1 by a random value between 0 and 1.
Repeat steps 2 to 6 till converge.

Since $J$ is large, this might take a long time.

Question

What is the standard way to do this?

Thank you.


texts: “Greater than 0” condition in integer linear program with a binary variable

texts:
How can one model the following condition in an integer linear program?
$$
y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases}
$$
Where $y \in \{0,1\}$ and $x \in \mathbb N$.


texts:
Let's say I have 100 sets of values, and each set contains roughly 100,000 values.  From these sets, I want to find the 10 sets that collectively have the largest number of unique values.

The brute force method of just checking all combinations is a combinatorial nightmare.  I also thought about doing a rough approach (solution doesn't have to be perfectly optimal) of just finding 'the next best set' to add in sequence.  So finding the largest set, then checking each of the rest of the 99 sets for smallest overlap, then checking the next 98 sets for smallest overlap, etc, but that's still 100+99+98+97+96+95+94+93+92+91 = 955 things to do.

Is there something more efficient?


texts: Data structure for testing all subsets of a query for membership

texts:
Is there a data structure that efficiently supports the following operations?

Add set
Query whether any subset of a set has been added.

This could be implemented with linear overhead by testing every added set during every query. Can it be implemented more efficiently? Small probabilities of false positives/negatives are acceptable (e.g. Bloom-filter style).


texts: Real world applications for Steiner Tree Problem?

texts:
Are there real-world applications of the Steiner Tree Problem (STP)?

I understand that VSLI chip design is a good application of the STP.  Are there any other examples of real world problems that people can suggest of that could be formulated in terms of the STP?

Background: I am beginning my PhD research and I am looking at using hybrid metaheuristics and primal-dual methods for the decomposition and solution of large-scale combinatorial optimisation problems.  I find the STP fascinating, and I'm wondering if there is much real-world motivation for studying it, or if it is primarily of theoretical interest.


texts: Examples of relatively complex truth tables/logic gates in real life?

texts: I'm researching truth tables, logical gates, and boolean algebra expressions. I'm trying to find specific real-life examples of logic gates and/or truth tables used in algorithm or circuit design in the real world. I've found things such as the adder circuit, but I was wondering if there were any logic puzzles or algorithms found in well-known programs (video games, for example) that could be represented by truth tables, or if you simply any more logic gates in a well-known piece of circuitry or hardware? I think it would be really cool to go and analyze practical examples in particular. Thanks for your help.


texts: Machine Learning vs System Identification?

texts:
Could anyone explain to me the differences & similarities between machine learning and system identifications? Are these just two names of the same thing? In this page, they say:

  Machine learning and system identification communities are faced with similar problems where one needs to construct a model from limited or noisy observations.

I've also read the early chapters of the famous book Pattern Recognition and Machine Learning by Christopher M. Bishop. So far, my conclusion is that the problem that system identification is trying to solve is a subset of what machine learning is trying to solve.


texts: Reduction from Steiner tree to minimum set cover

texts:
I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover
(given a set of items $I$, and a set $S$ of subsets of $I$ and an integer $k$, is there a subset $S'$ of $S$ such that $|S'|\leq k$ and $union(S')=I$)
 to weighted Steiner tree
(given a graph $G=(V, E)$, a weight function $w$, a subset $V'$ of $V$ and integer $k>0$, is there a subtree $G'$ of $G$ such that the sum of the weight of the edges in $G'\leq k$ and $V'$ is contained in $G'$?)
, but have gotten a bit stuck. I believe I am on the right path.

Here's what I have so far. Given an instance of minimum set cover, define a root node r, For every subset in $S_i\in S$, define a node $S_i$ and connect it by an edge to $r$ with weight one. For every element in $S_i$, define a node and connect them to $S_i$ via an edge of weight 0. This creates a tree. I believe something like this should work, but I cannot figure out how to define $G'$ for the constructed instance of STG such that there is an answer yes if there is a minimum set cover.

Any help would be greatly appreciated, thanks


texts: Minimum Spanning Tree with one particular edge minimised(continued)

texts:
I have recently encountered a coding problem, specifically, the CCC problem S4.

In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each and every home to one another. However, the tree is not the minimum spanning tree. You may use an enhancer, in exact words, with power D, to reduce the weight of one edge to what is max(0,weight-D). You have a number of days to make the given spanning tree a minimum spanning tree. During these days, you may deactivate any edge of the given spanning tree, and activate another edge of your choice. It does not matter if the tree is not a spanning tree in the process, however, at the end, it should be. You also want to minimize the amount of days you need to do this.

I have been struggling with the problem for a long time, and I cannot find any solution. I am able to find the minimum spanning tree, but I am struggling with the implementation of the enhancer.

I would appreciate any help to my problem, and sample codes will be even better.

I asked a similar question here as well:
Minimum spanning tree such that one edge can be minimised


texts: algorithm that removes extraneous connections from a graph

texts:
For a nondirection graph $G=(V,E)$, I need to write an algorithm that finds connections that can be removed without destroying the graph (ex: a connection from a child of a child back to the root of the graph). I have created an algorithm with a runtime of $O(|V|+|E|)$ (utilizing BFS):

    smallerGraph(G,s):
    for all vertex u from V[G]do
      color[u]=WHITE
      p[u]=NIL
      n[u]=NIL
    end for
    for all vertex u from V[G]do
      if color[u]==WHITE then
        modifiedDFSVisit(G,u)
       end if
    end for
    return 0
    modifiedDFSVisit(G,u):
    color[u]GRAY
    for all vertex v from Adj[u]do
      if color==BLACK and p[v]!=u and p[n[v]]!=v then
        removeLink(u,v)
      end if
      if color[v]==WHITE then
        p[v]=u
        n[u]=v
        modifiedDFSVisit(G,v)
      end if
    end for
    color[u]=BLACK

Additionally, I am also looking algorithm that can solve the same problem, however this time with a runtime of $O(|V|)$. If this is possible, if someone could point me in the right direction, I would appreciate it. If it isn't possible, why? Would the answer change if I was given a list of the connections (as well as the number of connections)?


texts:
I restate the question:
if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$
notice that $b(x)< f(x)$ and not $b(x) \leq f(x)$.
In other words what if

$f(x) \in \omega(b(x)) $ and

$f(x) \in O(g(x))$

can we state $f(x) \in \Theta(x)$?


texts:
I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.
Since the above classes are well-known, I will give a hand-wavy definition of $\text{IP}$. Then, I will state my question. Roughly speaking, a language $L \in \text{IP}$ iff there exist a pair of interactive algorithms Prover $P$ and Verifier $V$, with $V$ running in probabilistic polynomial time (in the length of the input $x$: $x$ is common to both $P$ and $V$), such that:

If $x\in L$, and the Prover $P$ follows the protocol, then the probability that the Verifier $V$ accepts is 1, and
if $x\notin L$, then for any Prover $P$ (even a cheating one), the
probability that the Verifier $V$ accepts is at most $\frac{1}{2}$.

I note that $P$ is allowed to be computationally unbounded.
Now to understand the power of interaction, I started to see what happens when restrict or give up the interaction between the prover and the verifier. I read the following in this lecture here, given by Jonathan Katz:
1- Assume that the verifier has input $x$. If the protocol is such that the prover $P$ sends a proof $\pi$ (to the fact that $x\in L$) to the verifier $V$, and then the interaction ends. The verifier has then to verify that $x \in L$, given $\pi$. If the verifier is deterministic and runs in polynomial time in $|x|$. Then, it is not hard to see that such interactive protocol is equivalent to the complexity class $\text{NP}$.
2- Now if we consider the interaction protocol in item 1, and additionally allow the verifier to be probabilistic, then we get more than $\text{NP}$. Specifically, it is known that in this case, any language in $L \in \text{BPP}$ can be handled by the protocol. Note that this actually suggest that we can eliminate the error when $x\in L$.
The protocol in item 2, can be thought of as a randomized version of $\text{NP}$.
Here comes my question: can the protocol given in item 2, handle any language in $\text{IP}$? That is, given a language $L\in \text{IP}$, can we give up the interaction entirely and still be able to verify that $x \in L$ in probabilistic polynomial time with completeness $1$, and soundness at most $\frac{1}{2}$? Intuitively, I think the answer is unknown because randomized complexity classes are conjectured to be contained in $\text{P}$ and we don't even know whether $\text{P}$ is a strict subset of $\text{PSPACE} = \text{IP}$.


texts: Set Intersection with asymmetric set sizes

texts:
I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large.

Due to the constraints of the problem I am solving, I cannot rely on an algorithm which sorts or depends on sorted elements.  Further, the simple method of performing $N_1$ hash look ups in a hash table of size at least $N_2$ will also not work.

Are there any non-naive approaches to this problem that I am missing?
They do not have to be as efficient as either approach, but obviously the more performant the better.

Edit:  Since my constraints were a bit vague, I'll go ahead and spell them out.

The application I have in mind is one type of MPC. Here, I would like to perform a set intersection while neither party reveals anything about the elements that are not in the intersection. One party will be performing the comparisons, and the other party will be transmitting the elements of their set in an encrypted format.

Sorting is out because an encrypted value cannot be evaluated for anything besides equality. Doing so would either reveal more about the elements in the set or would come with significant computational overhead.

Hash table look ups have great promise, but all approaches involving them require that both parties pretend they have a set size of $max(N_1, N_2)$. The most effective way to optimize the communication between the parties is hash tables, but privacy requires inserting enough false elements so that each bin of the hash table has the same number of items.

Bloom filters also suffer from similar problems as hash tables.  To be correct and secure, the size of the smaller bloom filter must be large enough to fit the larger set.

I'm really just looking for a fundamentally different algorithm that I can use to design a different approach to the problem. I would like for the communication and computation to be dominated by the size of the smaller set. I recognize that this is a research problem that no one will have a perfect solution to. Instead, I am trying to find different types of structure that can be used to improve on the naive approach.


texts: Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k?

texts:
Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the following problem.

Given a circuit of weft at most $t$, and depth bounded by a constant, decide whether there is a satisfying assignment of weight exactly $k$.

My question is whether it would be equivalent to define it using the same problem but with weight at most k instead.

This seems to be true for even levels, as there is a theorem (Theorem 7.1 in Parameterized Complexity, Flum and Grohe, 2006) stating that for such levels the problem of finding a satisfying assignment of weight exactly $k$, in a monotone circuit, is $W[t]$-complete. On monotone circuits there is a satisfying assignment of weight exactly $k$ iff there is one of weight at most $k$.

The same argument can't be used however on odd levels, but I would be very surprised if the result wasn't true, so I think there might be a simple proof.

Any help would be appreciated.


texts: count all possible paths of length n in an undirected graph with use of dynamic programming

texts:
Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths
of a given length n from a given start node, so that fjor every path applies:
a) no vertex may be visited twice within it
 and
b) never to go down an edge

I found out, that the number of possible paths corresponds to the row sums of the binomial coefficent, times 2 minus the center row, but if n is bigger than 3 other paths emerge which I struggle to include in my dynamic programming solution


texts: Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)

texts:
In the Geometric Spanner Networks book by Giri Narasimhan and Michiel Smid Page 153 says

  Definition 9.1.3 (Well-Separated Pair Decomposition). Let $S$ be a set of $n$ points in $\mathbb R^d$, and let $s > 0$ be a real number. A well-separated pair decomposition (WSPD) for $S$, with respect to $s$, is a sequence

  $\{A_1, B_1\},\{A_2, B_2\}, \cdots , \{A_m, B_m\}$

  of pairs of nonempty subsets of $S$, for some integer $m$, such that

  for each $i$ with $1 \leq i \leq m, A_i$ and $B_i$ are well-separated with respect to $s$, and
  for any two distinct points $p$ and $q$ of $S$, there is exactly one index $i$ with $1 \leq i \leq m$, such that

  $p \in A_i$ and $q \in B_i$ or
  $p \in B_i$ and $q \in A_i$

Look at the following image

The points $x_1, x_2, x_3$ are given in the plane and the split tree is drawn. Suppose for some $s$ the WSPD is built as shown. In this way the well separated pairs are going to be

$
A_1 = \{x_1, x_2\}, B_1 = \{x_3 \}
$

$
A_2 = \{x_1\}, B_2 = \{x_2 \}
$

The $x_1,x_2$ together are well separated to $x_3$ and $x_1$ is well separated to $x_2$. As you see $x_1 \in A_1$ and $x_1 \in A_2$, so it is in more than one pair which contradicts the definition.

I would like to know what is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

Thanks in advance.


texts: PERMUTE-BY-SORTING with similar priorities

texts:
Let $a$ and $b$ be integers, and let $\text{RANDOM}(a,b)$ be a method returning an integer from the range $[a,b]$ uniformly at random. Now consider the following program, that takes as input an array $A$ of integers.

PERMUTE-BY-SORTING(A)
    1. n = A.length
    2. let P[1..n] be a new array
    3. for i = 1 to n
    4.     P[i] = RANDOM(1, n^3)
    5. sort A, using P as sort keys

I'm solving the problem 5.3-6 in CLRS, which is asking me to explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. In other words, the algorithm should produce a uniform random permutation, even if two or more priorities are identical.

Because priorities are repeated in $P$, we will not get a uniform random permutation. I thought of adding i to step 4 but that doesn't produce the uniform random permutation. More specifically, the problem is that if two or more priorities are identical we will not get a uniform random permutation since the probability is not same for all the numbers. Ex 1,2,2,3 the probability of 2 in the example is 1/2 and the probability of 1 is 1/4 and 3 is 3/4.


texts: How to convert the following grammar to LL(1)?

texts:
The following grammar is given:

\begin{align*}
M &\rightarrow d M d \\
M &\rightarrow e M e \\
M &\rightarrow f M f \\
M &\rightarrow \varepsilon
\end{align*}

I've checked it with the LL(1) table and there are ambiguous cell entries.

Now, I've tried to convert it to LL(1), but without success. Is this not possible for this grammar? Why?


texts: Finding the size of the smallest subset with GCD = 1

texts:
This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd > 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 < g_1 < g_2 < ... < g_{10}$, where $\gcd(g_i,g_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g_2g_3...g_{10}$. But $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?


texts: Decision problems: Does a "constant" characteristic function describe a language in P?

texts:
I am new to complexity theory and I have some maybe stupid questions:

Are "decision problems" with the characteristic functions x(t)=1 or x(t)=0 "decision problems" or not?

If yes: Are the corresponding formal languages members of P or not?

(The calculation time needed is constant.)

If the answer is yes in both cases:

If $P\neq NP$ no P decision problem can be NP-complete. This is easy to prove.

I have read that if $P=NP$ all P decision problems would be NP-complete. This is easy to prove for all other problems however the problems described above cannot be complete in any way.

Are these problems an exception?


texts: Which neural network topology is the most efficient to generate randomly shaped letters?

texts:
I have created some unique shapes, so-called "letters" for a custom alphabet, all of which can fit into 9x9 pixels. Instead of drawing countless more, I try to combine two solutions I saw in a relevant part of Reddit, and decided to let a neural network create some additional examples.

Desconstructing the problem: letters are formed in a graph of 25 nodes (always ordered into a 5x5 square) by spontaneously connecting only the adjacent nodes - no diagonal or non-adjacent edges are present.

For a neural network input, I drew these runes into 9x9 blocks, where each row has 5 "pixels" for each nodes, and 4 more as a place for indicating connection.

Below is the current letter set, with an example of an empty graph and the only example generated by my network in the last line.

I've made a perceptron (tried 1, 2 and even 3 hidden layers) where input layer had 6 neurons, using them as a binary code (zero values mean -1 activation, and one values are the 1 activation), andthe output layer had 81 neurons. (9x9 to plot out the desired shapes)

My aim was to be able to produce additional letters by defining letters as sample and making the network to learn it. Then, I assumed that by activating the network with undefined inputs, I can find new letter shapes.

I used built-in functions froM JavaNNS and backpropagation as learning method.

Which are the parts of my topology, where I could possibly go wrong? What is the most suitable solution for this task?


texts: Cryptosystems whose hardness depends on solving the halting problem?

texts:
There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.
This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.
While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?
The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.
Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf
Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115


texts: Unification algorithm - need clarification

texts:
I have these two terms:

{P(a,x,x),P(a,b,c)}

I'm supposed to find if the terms and unifiable using the unification algorithm.

I'd do the following substitutions:

b/x, resulting in : {P(a,b,b),P(a,b,c)}

c/b, resulting in : {P(a,c,c),P(a,c,c)}

And thus the two terms are unifiable.
However, the solution in my book says that the terms aren't unifiable.
My intuition tells me that P(a,b,c) is not the same as P(a,c,c) and so I can't do the c/b substitution. However, I'd like some further more general clarification, which my book lacks.

Any help will be greatly appreciated.


texts: Difference between the tilde and big-O notations

texts:
Robert Sedgewick, at his Algorithms - Part 1 course in Coursera, states that people usually misunderstand the big-O notation when using it to show the order of growth of algorithms. Instead, he advocates for the tilde notation.

I understand the big-O is an upper bound for certain problem at certain condition.

What is the difference between the tilde and big-O notations?


texts: Odd cycle transversal and linear programming

texts:
Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ we add to LP the constraint $x_a+x_b+x_c+\dots +x_i≥1$ where $x_a,x_b,x_c,...,x_i$ are the vertices of the cycle. The objective function of LP is $\min \sum\limits_{1}^{n}{x_i}$.
Suppose $S$ is an optimal solution of LP. If a variable $x_v$ takes on a value $>0$ in $S$, is it guaranteed that there exists a minimum odd cycle transversal that contains $v$?  By minimum odd cycle transversal, I mean an odd cycle transversal with the fewest number of vertices.


texts: 2 Questions about Topological sorting in DAG

texts:
$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$.
Questions:

If we would do a topological sort on the given graph $G$, what can we say on the places of these $s,t$ vertices after the sort?

Write an algorithm that takes a DAG $G = (V,E)$ in the form of adjacency list (not matrix!) and returns 'True/Yes' if such $t,s$ exist, and 'False/No' otherwise. What is the time complexity?

I thought that for (1) they just stay in place because after the topological sort (which is just doing DFS multiple times) then there wouldn't be a path from each vertex to $t$ (Because $t$ would otherwise point to somewhere else that does not point to $t$ backwards because it is a DAG - no cycles)
for (2) I thought it would be $O(1)$ as we just check the length of the list at $s$ and check if it the same length of $|V|-1$ (every vertex except itself)
I am not sure about these small answers and I would appreciate if you would help me elaborate on these answers /give new ideas or solutions to these questions.
Thank you!


texts: This statement really made me confused, Is any superset of an undecidable set is uncountable?


texts: What is `wasted space` parameter and why is it O(n) for a linked list

texts:
I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values:

\begin{array}{cc}
    \text{Linked list} & O(n)\\
    \text{array}        & 0 \\
    \text{dynamic array}& O(n)
\end{array}

What is the wasted space parameter and why is it $O(n)$ for a linked list?


texts:
why you couldn’t use mmap to manage a rdbms buffer pool - or the whole rdbms itself just like NoSql stores?
I see that Cassandra, Hbase, Elastic do use mmap so why not use the same strategy for an RDBMS buffer pool?


texts: Defining polynomial hierarchy with oracle machines and quantifiers

texts:
While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between those definitions intuitively. What I want to know for now is the relation between oracle machines and existential/universal quantifiers from the viewpoint of polynomial hierarchy.

By Wiki, the polynomial hierarchy is the generalization of the classes P, NP, and co-NP to oracle machines. The addition of oracles (not sure this is a suitable expression) results in the increase of the hierarchy.

On the other hand, another way to define the polynomial hierarchy is to use the quantifiers $\forall$ and $\exists$. According to this lecture note (http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture5.pdf),
a language $L$ is in $\Sigma_i$ iff $\exists$ a polynomial time relation $R$ s.t. $x\in L$ iff
\begin{equation}
\exists y_1\forall y_2\cdots Q_iy_iR(x,y_1,\cdots y_i),
\end{equation}
where $Q_j=\forall$ if $j$ is even and $Q_j=\exists$ if $j$ is odd. And $L$ is in $\Pi_i$ iff its complementary $\bar{L}$ is in $\Sigma_i$.

From the above definitions, it seems that there exist a sort of one-to-one correspondence between the inclusion of oracle and the addition of quantifiers.

Can anyone help me understand how the oracles in a Turing machine plays the role of quantifiers in predicates?


texts: How to calculate the number of tag, index and offset bits of 2 different caches?

texts:
I have two exercises:
1) A 128KB direct-mapped cache, with lines from 32bytes/lines and 36-bit address.
2) A 512KB 2-way associative cache, with lines from 64bytes/lines and 36-bit address.
For both exercises i have to find the number of bits needed for the tag,index and offset fields.
I tried to do both exercises and i found these results:
1)5 bit offset, 17 bit index, 14 bit tag
2)6 bit offset, 12 bit index, 18 bit tag
First exercise:
128KB = 217
32 bytes = 25 so 5 bit offset
17 bit index
36-5-17=14 bit tag
 Second exercise:
64 bytes = 26 so i have 6 bit offset
512KB = 219
512/2 = 219/2 = 218 cache lines number
218/26= 212 so i have 12 bit index
36-(12+6)=18 bit tag


texts: If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

texts:
I was studying automata theory and formal languages and came across this question:
If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ?
I've searched the theory but I am missing something. And I cant find the answer anywhere, so I am asking here.
Definitions:
$P$ = set of rules
Right-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow Ba$ $(A, B \in N) \wedge (a \in T)$
Left-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow aB$ $(A, B \in N) \wedge (a \in T)$.
Left-regular grammar: a grammar where all the rules are left-regular rules.
Right-regular grammar: a grammar where all the rules are right-regular rules.
Example of a rule set $P$ with both left-regular and right-regular rules:
$P = \{ A \rightarrow a, B \rightarrow b \}$
And being both left-regular and right-regular makes the grammar regular and type 3


texts:
Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\in$ P then there is an algorithm that given $n$, it produces its decomposition into prime factors in polynomial time in the length of $n$.

I have tried to create this algorithm as follows:
Given $n\in\mathbb{N}$, if $\mathrm{Fact}(2,n)=1$ then $2\mid n$, in which case we take $n_1=\frac{n}{2}$, if $\mathrm{Fact}(2,n)=0$ then we see what happens with $\mathrm{Fact}(3,n)$ and we continue like this, my problem is that this algorithm is done in a time $O(2^n)$ which is not polynomial and all the algorithms that occur to me end in this problem is it possible to do this in polynomial time?


texts: How many syntax trees can be made by a BNF

texts:
An example of this would be:
1+2*3+4
Expression = Expression Arithmetic Expression | number
Arithmetic = + | - | * | /
Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 trees.

1+((2*3)+4)

((1+2)*3)+4

1+(2*(3+4))

(1+2)*(3+4)

(1+(2*3))+4
But doing it in this brute force manner wouldn't work on larger more complex BNFs.

I have tried using CYK to get 5 but haven't figured out how, even through they do seem similar enough. Any advice on using any algorithms or strategies to break down larger BNFs to see how many syntax trees they can make would be much appreciated.


texts: Is it possible to make data structure that will find MEX and support modification queries

texts:
Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX (Minimum EXcluded) meaning the smallest positive integer that is not present in the set. More info from wikipedia. The data structure should also support insert and remove elements from itself.
In other words, we have given a multiset with $n$ elements, we want to find its MEX, but we should support removing and adding elements.
What I was thinking was that we should first process the elements on some way, and then when adding new element in the set we should check if it is equal to the MEX, but there are many cases to worry about, so I couldn't come to complete solution.
The data structure should support both the queries/updates in $O(\log N)$ or similar time-complexity classes.


texts: When is epsilon a part of the result of computing the right quotient?

texts:
The right quotient of two languages is defined as

$$L_1/L_2=\{ x \mid  xy \in L_1 \text{ and } y \in L_2 \}.$$

Example:
$L_1=\{ab,aab,baa\}$ and
$L_2=\{b\}.$

I read somewhere that $L_1/L_2=\{a,aa,\varepsilon\}$ but I cannot understand why $\varepsilon$ is contained in the quotient.


texts: Is the the complement of the Halting problem NP-hard

texts:
Let us define the language (the complement of the Halting Problem):

$$
LOOPING = \left\{ \langle M,x \rangle | M \ doesn't \ halt \ on \ x\right\}
$$

The question is if $LOOPING$ is NP-Hard.
I'm pretty clueless about the answer. I know the the Halting problem is NP-Hard, but I can't seem to find a reduction from an NP-Hard problem to $LOOPING$.


texts: The same outgoing and incoming degree in graph

texts:
I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same outgoing and
incoming degree.


texts:
Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player
What is the optimal join order?
Based on the schema on the following picture:

I am suppoused (and that's what I tried) to use Dynamic Programming to obtain the result.
Considering only Deep-Left-Join Trees, and use the expected size (in number of rows) of intermediate results as costs.
How can I do this?
I really appreciate your help.
Thanks.


texts:
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$

$\text {Maybe we can say, that } w=a^{n}d^{m_s}b^{k} \text { and } d^{m_s} \text{ is a prime number with } |w| \ge n. \text{And we choose xyz arbitrarily with } w= xyz \text { } \wedge |y| \ge1 \wedge |xy| \le n\text {. And now I don't know how to go on. Maybe someone can help me, please.}$