texts:
I am somewhat stuck in converting an expression with negative numbers from infix to postfix.

Suppose we have a expression like

a = -b - (-c - d) .

At some places I read that you can parathesize the negative numbers to solve the problem. But if I parathesize them as

a = (-b) - ((-c) - d), then at the beginning of the postfix expression I would get "ab-" which means a-b and is incorrect.

Can someone help me?


texts: If I randomly swap pairs of inputs how unbalanced will a binary search tree become?

texts:
Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no requirement for a self-balancing tree if the input is first randomly jumbled up first. However, one cannot shuffle a stream of data without waiting for all the data which is undesirable sometimes.

If I take inputs two at a time and randomly swap them before inserting them how unbalanced will the tree tend to become over time?


texts: how to check whether a flow network contains unique maximum flow?

texts: I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum flow or not. I have been search everything I could, and some people said run an algorithm that able to find a max flow first, then modified the edges capacity, and run the algorithm one more time to see if we get the same flow value. But this seems never works for me especially when we are given arbitrary flow network, like non-integer flow graph. How should I start a good approach? (Literally stuck for few hours)


texts:
Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.

Output: The set of closed walks in $G$ using $e$ and $f$ which contains $k$ faces of $G$. In other words the set of close walks in $G$ via $e$ and $f$ which each one partition $\Pi$ into two set of faces which one is of size $k$.

I'm wondering if this problem is solvable in poly-time!


texts: How to practically construct regular expander graphs?

texts:
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.

What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is proven to be a.a.s. an expander?

I also read about Margulis constructions and Ramanujan graphs that are expanders and a construction using a zig-zag product. Wikipedia gives a nice but very short overview: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10
But which method do I choose in practice?

For me, these methods seem all very complicated to implement and in particular to understand and maybe quite specific.
Aren't there easier methods, maybe based on permutations or so, to practically generate a sequence of d-regular expander graphs?

Is it maybe easier to construct d-regular bipartite expander graphs?

I also have another question: What about families of bad d-regular expanders? Does such a notion make sense? Can one construct a family of d-regular graphs (that are of course connected) that is as bad as possible in the sense of an expander?

Thanks in advance.


texts: Lower bound for finding kth smallest element using adversary arguments

texts:
In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument?

Wikipedia says that tournament algorithm runs in $O(n+k\log n)$, and $n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$ is given as lower bound.


texts: Combinatorics - how many $c$-distinct sets are possible?

texts:
I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here.
I am given two parameters $m\in\mathbb{N}$ and $\frac{1}{2}< p\le 1$, and I want to find the maximal value $k\in \mathbb{N}$, such that there are $A_1,\dots,A_k\subseteq [m]$ for $[m]=\{1,\dots,m\}$ and, we have the two following properties:

For every $1\le i\le k$, we have $|A_i| \ge p\cdot m$
For every $i\neq j$, we have $|A_i\cap A_j|\le (1-p)\cdot m$

Essentially, I'm trying to find the maximal number of sets with size $p\cdot m$, who are $c$-far from being distinct in pairs, where $c:=(1-p)\cdot m$.
Equivalently, I'm interested in finding for every $k$ what is the highest $p$ with this property.

My attempt
I tried to think of an approach similar to one where $p=1$, and the sets would be completely disjoint, therefore every $A_i$ would add an additional $p\cdot m$ new elements, and thus $k=\frac{m}{p\cdot m}=\frac{1}{p}$. But this approach didn't work for me, since even if I say each set adds an additional $p\cdot m - (1-p) \cdot m = (2p-1)\cdot m$ new elements to every other set, I can't guarantee those elements are not in other sets.

Some (additional) thoughts
After thinking additionally a bit, I think that one thing that would suffice for me is to show that the solution doesn't depend on $m$.
This is because in my usage of this problem, I actually try to find a $k$ such that this property won't hold, and I can choose my $k$ to be arbitrarily large but it would also increase $m$ arbitrarily. So - if the solution here won't depend on $m$, I don't need to worry about increasing $m$ arbitrarily.


texts: Inductive sequence of words in a biprefix code

texts:
Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) < m(X_2)$, i.e. the maximal length of the first is strictly lower than the second. Now, if $v \in X_2$ we define a sequence such that $v_0 = v$ and $v_{i+1} = 1$ if $v_i \notin X_1A^*$ and $v_{i+1} = y_ix_i$ if instead $v_i \in X_1A^*$, with $v_i = x_iy_i$ with $x_i \in X_1, y_i \in A^*$.
Now, let $u,v \in X_2$ and suppose there exist two integers $i \leq j$ such that $u_{i} = v_j$. Since $X_1$ is biprefix, this implies that $u_{i-1} = v_{j-1}$. Why does this imply that $u_0 = v_{j-1}$? The paper I am reading motivates this last deduction by induction, but I can’t see how $j-1$ could stay fixed in the process. Any hints?


texts: Relativized world where $LogCFL^A=PSPACE^A$

texts:
I wonder whether there is a known relativization barrier against proving $LogCFL\neq PSPACE$. Hence I'm looking for a language $A$ for which $LogCFL^A=PSPACE^A$.

One could try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But relativising space-bounded classes is a very tricky business, as Emil Jeřábek tried to explain to me.

Maybe it is easier to look at the problem from the other side: Both $NL\neq PSPACE$ and $CFL\neq PSPACE$ are known. I heard multiple times that one "usually considers LOGCFL instead of CFL, since it has nicer closure properties". So maybe $LogCFL\neq PSPACE$ is known. I noticed that the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, but I couldn't verify this. But if this should be known indeed, then I wonder whether it also applies to $AC^1$, or whether $LogCFL$ is really the current limit where separation from $PSPACE$ can still be proven.


texts: Why are those very similar languages in a different complexity class?

texts:
i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and lecture notes/books, but couldn't find a reason for it. the languages are:

1.$NONEMPTY-INTER_{DFA}\:=\:\left\{<A_1,...,A_k> |\:A_1,...,A_k\:are\:DFAS\:and\:L\left(A_1\right)\cap...\:\cap L\left(A_k\right)\:\ne \varnothing \right\}$

2.$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$

why is the second can be run in a polynomial time on a turing machine, and the first can not? would really appreciate an explanation for this.


texts: are these functions for open address hashing, proper?

texts:
I want to use these two functions in two hash-tables with open-addressing. Is there any problems with these functions? If yes, why they are not appropriate?

H(k,i) = (k mod m + 3i mod m) mod m

H(k,i) = (k^2 + 2k + i(k mod m)) mod m


texts:
In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:

  Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

But in this other Wikipedia article about the Clique problem in CS
 it says it is solving the problem for a fixed size k is a problem in P, it can be brute forced in polynomial time.

  A brute force algorithm to test whether a graph G contains a k-vertex clique, and to find any such clique that it contains, is to examine each subgraph with at least k vertices and check to see whether it forms a clique. This algorithm takes time O(n^k k^2): there are O(n^k) subgraphs to check, each of which has O(k^2) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. When k is part of the input to the problem, however, the time is exponential.

Is there something I am missing here? Maybe a difference in the wording of the problem? And what does the last sentence mean, that "When k is part of the input to the problem, however, the time is exponential."? Why is there a difference when the k is part of the input to the problem?

My idea is that to find a clique of size k in a graph G, is that we first choose a subset of size k of nodes from G, and test wether they are all related to the other k nodes, which can be done in constant time. And repeat this until we have a clique of size k. The number of sets of k nodes we can choose from G is n! / k!*(n-k)!.


texts: Looking for a ranking algorithm that favors newer entries

texts:
I'm working on a ranking system that will rank entries based on votes that have been cast over a period of time.  I'm looking for an algorithm that will calculate a score which is kinda like an average, however I would like it to favor newer scores over older ones.  I was thinking of something along the line of:

$$\frac{\mathrm{score}_1 +\ 2\cdot \mathrm{score}_2\ +\ \dots +\ n\cdot \mathrm{score}_n}{1 + 2 + \dots + n}$$

I was wondering if there were other algorithms which are usually used for situations like this and if so, could you please explain them?


texts: web content "mining" using supervised learning tequniques

texts:
We're accessing an API of a web system for obtaining product information. We require some additional information, which is not available through the API. This information is publically available for each product visually - through the source code for each item on its item page. We've written an algorithm which parses this information from the web page for each item, but that will be highly ineffective in the long run, since the algorithm will simply stop working if and when they decide to change the source code ( for example - redesign of the front end ).

I feel like there should be a supservised learning approach to this problem, however I'm unaware if there exist such solutions.

What are some good aproaches to this kind of problems ?

Regards.


texts:
There is an algorithmic problem $A(n)$, where $n$ is the size of the problem.

It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ is $T(n)$.

Does this imply a lower bound on the time it takes to find a correct solution to $A(n)$ (e.g. that it takes at least time $T(n)$)? This seems obvious to me, but obvious and true do not always coincide. Since $P \subseteq NP$, the implication probably holds if $T(n)$ means "polynomial time". But does it hold in general, for arbitrary complexity classes?
Does this imply any upper bound on the time it takes to the time it takes to find a correct solution to $A(n)$ (e.g. that it can be done in time $2^{T(n)}$)?


texts: Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup

texts:
I've been trying to solve the following question:

  Show a polynomial algorithm for the following problem. Let $G = (V,
> E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that
  for every vertex $v ∈ V$, $v$ meets or exactly $k$ edges from $E'$.
  (Namely, for $k = 1$ you get the perfect matching problem). hint -
  start with $k = 2$, duplicate vertices.

I was able to develop an algorithm which works but I couldn't prove it find the largest subgroup, your help is needed :)

The algorithm:

For every $v$ in $V$:

Check the degree, if it equal to k or not connected to any edge in
the subgroup - color it
Check if the colored $v$ has a colored vertex,
if it has the edge between them belongs to the subgroup.
Traverse on all vertices (BFS or DFS) When done you'll find the subgroup, the only one thing the prove it is the largest and I couldn't find any
proof for it.

Thanks in advance!


texts:
Let $L$ to be the following problem:
  $$L = \{ \langle M,x,1^t \rangle \mid \text{$M$ accepts $x$ after $t$ steps with probability at least $3/4$} \}.$$
  Show that if $L\in BPP$ then $NP\subseteq BPP$.

I already showed that $L$ is $BPP$-hard. I think a reduction from $3SAT$ to $L$ need to be shown (logarithmic/polynomial? not sure)

It's not clear to me how to do that - I'd be glad for guidance.


texts:
Define a function  ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w.

Thus:
 =0;
 0=−1;
 0=−1;

Let  = {∈ {0,1} * |   = 3 for some  ∈ ℤ}.

the teacher only explained to me in class the functioning of the DFA multiple of 3
https://cdncontribute.geeksforgeeks.org/wp-content/uploads/dfadivision-1.jpg, with this dfa I must build the day that from the subtraction of the ones and zeros in w accept multiples of 3.

I did not have the next class, the teacher sent a pdf with a complicated explanation about Proving Correctness of DFA

How define a deterministic finite automaton M such that L (M) = L?

How proving correctness of DFA if diff w is a subtraction?


texts: what is correct maximum number of subnetworks?

texts:
ip: 10.5.2.1

subnetmask: 255.255.255.240

{10.5.2.1/28}

what is correct maximum subnetworks ????

what is different between classful subnet and CIDR subnet ???


texts: Proving that two sets of strings are equal

texts:
I am stucked at this problem:

Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$.

Let's define foreach $i,j\in\{1,...,m\}$, $k\in\{0,1,...,m\}$

(Note: the $\delta$ below is the extension of $\delta$ to $\Sigma^*$)

$L_{i,j}^k=\{w\in\Sigma^*|\delta(q_i,w)=q_j \land \forall u\in PREFIX(w)-\{\epsilon,w\}, \delta(q_i,u)=q_x\to x\leq k\}$

Now let's define the following sets recursively:

For all $i,j\in\{1,...,m\}$:
$M_{i,j}^0=\{\sigma\in\Sigma|\delta(q_i,\sigma)=q_j\}\cup\begin{cases}
\emptyset, \text{if $i\neq j$} \\
\{\epsilon\}, \text{if $i=j$}
\end{cases}$

For all $i,j,k\in\{1,...,m\}$:
$M_{i,j}^k=M_{i,k}^{k-1}\cdot (M_{k,k}^{k-1})^* \cdot M_{k,j}^{k-1}\cup M_{i,j}^{k-1}$

Prove that for all $i,j\in\{1,...,m\}$ and $k\in\{0,1,...,m\}$ we get $L_{i,j}^k=M_{i,j}^k$.

I've tried to prove it by induction on $k$ but failed.

(Note: I've encountered these sets in the proof of the Theorem that says that every regular language has a regular expression)

Thanks a lot.


texts: Uniform random number generation from random bits

texts: I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me a possible range of 000 to 111 (0 to 7), inclusive. My intuition says after concatenating 3 random bits, if the result falls between 000 and 101, inclusive, I can just return that number plus 1 (which essentially gives me a number between 1 and 6, inclusive). If I get 110 or 111 (6 or 7) after concatenating 3 random bits, I can retry again until I the number generated is in my desired range. How can I prove (or disprove) that the number I returned is indeed random?


texts: Knight's Tour Parberry algorithm: 4 knight's tour merge procedure

texts:
I'm implementing Parberry's algorithm for closed Knight's tour problem.

Brief idea of the algorithm: split the board in $4$ parts, find the tour on them recursively then delete $1$ edge in each part and add $4$ edges that
 will connect each part with two adjacent parts.

At the end of page 5 (of the pdf viewer) the author estimates the time complexity of his algorithm. Namely, he writes: $T(n) = 4 \cdot T(n / 2) + O(1)$.

As I understood, the time complexity on each level of recursion is $O(1)$.

Parberry says nothing about the data structures he uses.

So, my question is:

How do I represent Knight's tour and how to merge $4$ Knight's tours to reach a $O(1)$ on each level of the recursion?

Thanks.


texts: Estimate entropy, based upon observed frequency counts

texts:
Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution.  I can count the frequency $f_s$ of each symbol $s \in \Sigma$ among the observations; how should I use them to estimate the Shannon entropy of the source?

The obvious approach is to estimate the probability of each symbol $s$ as $\Pr[X=s]=f_s/n$, and then calculate the entropy using the standard formula for Shannon entropy.  This leads to the following estimate of the entropy $H(X)$:

$$\text{estimate}(H(X)) = - \sum_{s \in \Sigma} {f_s \over n} \lg (f_s/n).$$

However, this feels like it might not produce the best estimate.  Consider, by analogy, the problem of estimating the probability of symbol $s$ based upon its frequency $f_s$.  The naive estimate $f_s/n$ is likely an underestimate of its probability.  For instance, if I make 100 observations of birds in my back yard and none of them were a hummingbird, should my best estimate of the probability of seeing a hummingbird on my next observation be exactly 0?  No, instead, it's probably more realistic to estimate the probability is something small but not zero.  (A zero estimate means that a hummingbird is absolutely impossible, which seems unlikely.)

For the problem of estimating the probability of symbol $s$, there are a number of standard techniques for addressing this problem.  Additive smoothing (aka Laplace smoothing) is one standard technique, where we estimate the probability of symbol $s$ as $\Pr[X=s] = (f_s + 1)/(n+|\Sigma|)$.  Others have proposed Bayesian smoothing or other methods.  These methods are widely used in natural language processing and document analysis, where just because a word never appears in your document set doesn't mean that the word has probability zero.  In natural language processing, this also goes by the name smoothing.

So, taking these considerations into account, how should I estimate the entropy, based upon observed frequency counts?  Should I apply additive smoothing to get an estimate of each of the probabilities $\Pr[X=s]$, then use the standard formula for Shannon entropy with those probabilities?  Or is there a better method that should be used for this specific problem?


texts: Neural network for PDE: Should we train the PDE using more initial and boundary data at the beginning?

texts:
I was trying to solve a partial differential equation (PDE) using a neural network. The solution to the PDE is not unique unless the boundary condition is determined.

In my case, the neural network takes $(x, y)\in [0, 10]\times[0, 10] = A$ and outputs a scalar. Suppose at the beginning of the training, I only sample from the middle of $A$, which will give us a neural network that satisfies the PDE except for the boundary condition. Then we sample from the boundary of $A$.

My question is, will it be costly to train using the algorithm above? My guess is yes since we have to drag that solution to somewhere else based on the boundary condition, causing large change to the output value. And intuitively, it's better to construct the solution on the boundary first to make the foundation of the solution correct.

I know that we can test it by experiments, but I'm more interested in a theoretical explanation, e.g., why / why not will it be costly to update parameters of the neural network after the boundary data get considered?


texts:
I am trying to understand the difference between byte addressing and word addressing.

  A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB.

No of sets in the cache $= (16 * 1024) / (4 * 8 * 4) = 2^7$

If word addressing is used :

Block offset $= 3 \ bits$

Since PAS is $4 \ GB$, total no of addresses = $2^{32} / 2^2 = 2^{30}$

So, total address bits $= 30\ bits$

Address structure :

Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $3 \ bits$

Now, suppose the CPU wants to access the 3rd byte of a particular word.

The cache controller will use the $7 \ bits$ set-field to index into a set and then comparing the higher $20\ bits$ tag-field with all of the $4$ blocks in the set. If a match is found, then cache hit occurs and the lower $3 \ bits$ block offset to put one of the word out of the $8$ words in one of the general purpose register. The CPU then extracts the 3rd byte from the word and perform the operation.
If tags are unmatched, then cache miss occurs, a memory read signal is sent and due to spatial locality of reference, a block containing the word is transferred into the cache.

If the CPU is byte addressable:

Total address bits $=32$

Address Structure :
Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $5 \ bits$

If the CPU wants to access 3rd byte of a word:

Same as in Step 1 of word addressable, but the CPU now can directly address the 3rd byte of the word, using the lower $2 \ bits$ byte offset. However, I'm confused how that would happen. Since, the CPU register size has a width of 1 word, similar to the word addressing, one word out of the 8 words in the block will be transferred to the register. But how would the "byte extracting" step be easier here? And why do we call it byte addressing if still we are actually addressing a word?
Same as in Step 2 of word-addressing. Block of data will be transferred from the memory to the cache in case of cache miss.

Also, this answer says that physical memory is always byte addressable. Now, what is the difference between the addressablity of the memory and addressablity of the CPU architecture?


texts: Point and Application of Recursive and Recursive Enumerable Languages

texts: What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for designing compilers but what about Recursive and Recursive enumerable languages?


texts:
In the script I am currently reading on the lambda calculus, beta equivalence is defined as this:

  The $\beta$-equivalence $\equiv_\beta$ is the smallest equivalence that contains $\rightarrow_\beta$.

I have no idea what that means. Can someone explain it in simpler terms? Maybe with an example?

I need it for a lemma following from the Church-Russer theorem, saying

  If M $\equiv_\beta$ N then there is a L with M $\twoheadrightarrow_\beta$ L and N $\twoheadrightarrow_\beta$ L.


texts: In what case would bi-directional BFS have a worse asymptotic run time than regular BFS?

texts:
I am trying to prove that bidirectional BFS could have a worse run time than regular BFS. I am confused on how this would be possible, considered bidirectional BFS always divides the run time in two, since it is executing two searches. Would a specific order of nodes and vertices have to take place in order to give bidirectional a worse running time? Or is it a quantity issue?

Edit:
Here is a graph I made. I'm assuming bi-directional BFS would infinitely search in this instance because if search one went right, and search two went left, they wouldn't find a path. Then, search one would go left, and search two would go right. Doesn't this mean that the search would run infinitely, because it doesn't stop until both have found the same path?


texts: Show that for A and B, a language J exists such that A $\leq_T$ J, B $\leq_T$ J

texts:
I am working on theory of computation problems, and I came across this one:

Show that for A and B, a language J exists such that $A \leq_T J$, $B \leq_T J$

The only $J$ I can think of for the moment is the language that uses a $TM$ $N$ which contains a recognizer $M1$ for $A$, and another recognizer $M2$ for $B$. $N$ uses oracle $J$ to check if input $x\in A U B$. If $J$ accepts, then it means that either $M1$ or $M2$ will halt, so $N$ can now simultate $M1$ and $M2$ simultaneously.

But I think there should be a simpler way to solve this..... any help?


texts: How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

texts:
Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle.

The proof in [1] makes use of binary search with a search space from weight $0$ to the sum of all weights. But I am struggling with the fact that the weights could very large. For example: Let $\{c_1, ..., c_m\}$ be a set of clauses where some clause $c_i$ has weight $w_i = 2^{2^{m}}$. Then binary search will take $log_2(2^{2^{m}}) = 2^m$ steps in the worst case, which is exponential in the input length $m$.

What am I missing?

Reference:
 [1] Papadimitriou - Computational Complexity (1994)


texts: How do we translate first order logic's universal quantifier (the $\forall$) and the existential quantifier (the $\exists$) to Prolog?

texts:
I'm trying to convert some English statements to first order logic statements and I'm trying to use Prolog to verify the translations. My question is: how do I convert a first order logic statement (having $\forall$ and $\exists$ quantifiers) into Prolog rules?

For example, there's this English statement:

  Every voter votes for a candidate which some voter doesn't vote for.

and here's my translation of the English statement into first order logic:

$$\forall x, y[Voter(x) \land Candidate(y) \land Votes(x, y) \rightarrow \exists z[ Voter(z) \land \lnot Votes(z, y) ] ]$$

Now I'm not sure if this translation is correct. That's what I want to find out. My question is: how do I convert this first order logic statement to a Prolog rule?

So first I'm trying to fill a Prolog database with some facts.

human(p1).
human(p2).
human(p3).
human(p4).
human(p5).
human(p6).
human(p7).
human(p8).
human(p9).
%humans who are neither voters nor candidates
human(p10).
human(p11).

%humans who are only voters
voter(p1).
voter(p2).
voter(p3).

%humans who are candidates and voters
voter(p4).
voter(p5).
voter(p6).
candidate(p4).
candidate(p5).
candidate(p6).

%humans who are only candidates
candidate(p7).
candidate(p8).
candidate(p9).

%some random votes
votes(p1, p6).
votes(p2, p6).
votes(p3, p6).
votes(p4, p7).
votes(p5, p8).
votes(p6, p5).

I'm using human, voter, candidate, and votes. Here are some attempts to model the statement into a Prolog rule:

rule1 :-
  foreach((voter(X), candidate(Y), votes(X, Y)),(voter(Z), \+votes(Z, Y))).

rule2 :-
  foreach((human(X), voter(X), candidate(Y), votes(X, Y)),(human(Z), voter(Z), \+votes(Z, Y))).


texts: Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search?

texts:
Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a depth of $2$, then $F$ has a depth of $3$). The beginning vertex has a depth of $0$. I need to show that every vertex must have a depth $\le \lfloor \frac{n}{2} \rfloor$.

I know that because the graph is only a cycle, every vertex must have a degree of $2$. And when performing a breadth first search, each vertex (except for the beginning vertex) will only have one vertex to choose, as the other connected vertex would be its parent. This would create a kind of "tree" shape where every node except the root has one child, and would mean that the maximum depth is $\le \lfloor \frac{n}{2} \rfloor$. I'm not sure how to phrase this as a proof, though.


texts: Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

texts:
If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).

Intuitively, it may feel it is, because it is like the reverse of build it up.

(Building a heap can be O(n) -- in Wikipedia).

If building a heap is O(n) in the worst case, including the numbers are all adding by ascending order, then taking the heap down is exactly the "reverse in time" operation, and it is O(n), but this may not be the "worst case" of taking it down.

If taking down a heap is really O(n), can't the selection problem be solved by building a heap, and then taking it down (k - 1) time, to find the kth max number?


texts: More Information about these Question Answering Systems

texts:
My question is about the multi-hop question answering systems described in the page https://hotpotqa.github.io/ and reproduced in the following picture:

I am interested in the models BFR-Graph, GSAN-large, ETC-large and AMGN.
I think the previous capital latters are the initials of the name of the models in the original paper but google does not retrieve my desired results.
Thanks in advance for any information about the four models cited above.


texts: Is there an example of a recursive language which is not context sensitive?

texts:
I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for context free languages and $a^nb^nc^n$ for context sensitive languages. I usually consider the language which is accepted by a universal Turing machine (UTM) as prototypical of recursively enumerable. However for the the recursive languages I don't have one. I used to think that $\{1^p | p \text { is prime}\}$ was recursive but verifying a number is prime can be done by a bounded Turing machine. I also had $\{1^{2^{n}}\}$ but again verifying this can be done by a bounded Turing machine.

On the other hand, the other options I have found are computing Turing machines that requiere that the output of the computation to be store somewhere in the machine, however the output is no part of the accepted language which makes every of those language regular or context free so far. For instance the machine that sums two numbers represented by 1s and separated by a space, and puts the result after. In this case, the accepted language is actually $1^*B1^*$ which is regular! If we try to do it like verification if become context free $1^nB1^mB1^{n+m}$ but no recursive!

So is it possible to talk about a recursive language which it might be regular in essence but since it is conditioned to do the computation and put a result in the output as a kind of recursive language? Those definitely can not be done in a bounded Turing machine.


texts: How can a computer deal with real numbers

texts:
Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in a decimal format, which is limited to very few decimal places, but as an integer instead, while keeping track of the number's precision.
Still, how can a computer simplify computations just like humans do? Take a look at this basic  example
$$\sqrt{3} \times (\frac{4}{\sqrt{3}} - \sqrt{3}) = \sqrt{3} \times \frac{4}{\sqrt{3}} - \sqrt{3} \times \sqrt{3}  = 4 - 3 = 1$$
That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.
It would surely defeat a human in terms of speed, but it would lack in terms of accuracy. The result will be really close to 1, but not 1 exactly. A computer has no idea that, for instance, $\sqrt{3} \times{\sqrt{3}}$ is equal to $3$. This is only one of the uncountable examples out there.
Did people already find a solution, as it seems elementary for mathematics and computations? If they didn't, is this because it didn't serve any purpose in the real world?


texts: Supporting data structures for SAT local search

texts:
WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the GSAT algorithm - How to select which literal to flip? and presented below.

procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

Here we flip the variable that maximizes the number of satisfied clauses. How is this done efficiently? The naive method is to flip every variable, and for each step through all clauses and calculate how many of them get satisfied. Even if a clause could be queried for satisfiability in constant time, the naive method would still run in $O(VC)$ time, where $V$ is the number of variables and $C$ the number of clauses. I'm sure we can do better, hence the question:

  Many local search algorithms flip the variable's assignment that maximizes the number of satisfied clauses. In practice, with what data structures is this operation supported efficiently?

This is something I feel like textbooks often omit. One example is even the famous Russell & Norvig book.


texts: Minimum spanning tree with small set of possible edge weights

texts:
Given a undirected graph which only has two different edge weights $x$ and $y$ is it possible to make a faster algorithm than Prim's algorithm or Kruskal's algorithm?

I saw on Kruskal's algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don't think there is any benefit, but I am not sure...


texts: Normalizing the mantissa in floating point representation

texts:
How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format

1 - Sign bit
7 - Exponent in Excess-64 form
8 - Mantissa

$(0.148)_{10} = (0.00100101\;111...)_2$

We shift it 3 bits to left to make it normalized $(1.00101\;111)_2 * 2^{11}$.

Exponent = $11+64 = (75)_{10} = (1001011)_2$ and Mantissa = $(01001\;111)_2$.

So floating point representation is $(0\;1001011\;00101111)_2 = (4B2F)_{16}$ Representation A

But if we store the denormalized mantissa into 8 bit register, then it won't have stored the last three $1$s and then the mantissa would have normalized from $(0.00100101)_2$ to $(1.00101\;000)_2$ by inserting 3 $0$s instead of $1$s.

The representation would have been $(0\;1001011\;00101000)_2 = (4B28)_{16}$ Representation B

So while normalizing, does the processor takes into account the denormalized mantissa bits beyond 8 bits too? Or just rounds it off? Which one is correct: A or B?

Does it store the mantissa in fixed point representation? How does it all work?


texts: Confusion about proving CIRCUIT-SAT is in NP

texts:
My textbook states that CIRCUIT-SAT is in NP because you can guess an input and verify it in polynomial time.

My textbook also states that a problem is in NP if and only it has a polynomial-time verifier V(I, X) such that:

if I is a YES instance, then there exists an X s.t. V(I, X) = YES
if I is a NO instance, then for all X, V(I, X) = NO

I see how the textbook explanation satisfies case 1. Just feed the variables' assignment to the circuit and check the output. But what if I is a NO instance? Then all X must be passed through V(I, X). And since there is an exponential number of X's (each variable can be 1 or 0, yielding 2^n combinations for n variables), then even assuming computing the circuit output happens in constant time, the overall verification is O(2^n).

On a side note: Decision problems return a boolean: YES or NO. Then, how can one even verify the output of such a problem, if the X itself is not known? The only way I can see verification possible is to simply re-run the algorithm. I.e. the explanation given by the textbook above is not plausible because CIRCUIT-SAT returns a boolean (I), not the specific variable assignment (X). Since we don't know X, we cannot just feed X through the circuit and obtain an answer.


texts:
Consider the following problem.

Given: A complete graph with real non-negative weights on the edges.

Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.)

Note: The maximum-weight subgraph will be a triangulation; if the complete graph is on $n$ vertices, it will have $m=3n-6$ edges.

Question: What is the best available algorithm for this problem? What is its time-complexity?


texts: What is the importance of c in big O notation?

texts:
From the definition of Big O, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not able to understand is what is its importance in Big oh notation. Every question explains what is big-Oh and what how it uses useful. But I'm not able to understand what is $c$ actually in big-oh. There might be answer which I'm not able to get it due to its technical jargon.
Can someone explain me this in simple terms?


texts: Given a valid combination, how to get its index in the sequence of integer partition

texts:
This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that answer also gives me the desired sequence - as much large numbers located in the front as possible, for example, we will get the following output for $F(7,3,4)$:

4>2>1
3>3>1
3>2>2

So here is the question, given a valid combination, is it possible to get its index in the result set without generating the whole result set and searching for it?


texts: Metrics for measuring the tradeoff between efficiency and effectiveness in Information Retrieval

texts:
I'm comparing several methods for building inverted indexes (n-grams, hash boundaries, etc.).
Given a set of queries, these indexes perform differently.
On one hand, I get performances metrics (efficiency) such as the time needed to execute the query.
On the other hand, I get metrics such as precision and recall (effectiveness) by checking the relevance of the results.
Depending on the method I use, there is a tradeoff between efficiency and effectiveness.
For example, some methods loose a little in term of effectiveness for a huge gain in term of efficiency.

Are there some metrics which puts the effectiveness (precision, recall, etc.) in perspective with the efficiency (throughput, memory, etc.)?


texts: Minimum number of nucleotides to force duplicate substring

texts:
There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T.

Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of nucleotides I would have to encounter before I'm pigeonholed into seeing a duplicate substring of length 3.

Observe that a string of 4 nucleotides could produce a duplicate substring of length 3 (although I'm not forced into a pigeonhole since there are other strings of length 4 that don't produce a duplicate).

AAAA

Substrings [0-3) and [1-4) are both "AAA", so a duplicate occurrence of a length 3 substring has appeared.

I originally tried concatenating together every combination of 3 nucleotides.

[AAA][CAA][GAA][TAA][ACA][CCA]
AAACAAGAATAAACACCA...

But this algorithm produces a duplicate rather quickly: substrings [0-3) and [10-13).

I know there are 4^3 = 64 different substrings of length 3, so an upper bound to force pigeonholing is a string of length (64 * 3) + 1 = 195 -> one of the 64 substrings must appear twice. I've convinced myself that this can be bounded tighter to length 67 since this could contain 64 different substrings that start at indexes 0-63 and one duplicate that starts at 64. The interleaving of the substrings with each other is what makes them hard to analyze. How much tighter can this bound go, and what is an algorithm for producing a sequence that forces a pigeonhole?


texts:
A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that it is decidable.

I know how to prove it with Turing Machines, but not DFAs. So here is my proof for TM:

Let $U_{\mathrm{TM}} = \{\left \langle M \right \rangle|M \text{ is a TM that  has a useless state}\}$. We show that $U_{\mathrm{TM}}$ is undecidable by a reduction from $\mathrm{HALT_{TM}}$ to $U_{\mathrm{TM}}$:

If $\left \langle A,w \right \rangle \in \mathrm{HALT_{TM}}$, then $A$ halts on input $w$ and $M_A$ visits all its states on every input; thus, $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. iIf $\left \langle A,w \right \rangle \notin \mathrm{HALT_{TM}}$, then $A$ loops on input $w$ and so does $M_A$; therefore, $M_A$ will never visit state $q_u$ and $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. Since $\mathrm{HALT_{TM}}$ is undecidable, $U_{\mathrm{TM}}$ is undecidable.

But for DFA I have to show that the language is DECIDABLE. Do you have any ideas how I can go with that?


texts: Identify balanced and full binary search tree insert order

texts:
I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create the binary search tree myself, starting with a root of 8, however I could never get it to be full; the depth would increase from three to four or sometimes five.

How can I come up with an order to insert these numbers into a binary search tree, and get it to be balanced and full?


texts: Why the multiplier and quotients can not store in the ACC?

texts:
When I study the Arithmetic Unit, there is the below information:

there I have some questions:

Why the multiplier must store in the MQ and the product must divide into the high part and low part?
Why the quotients must store in the MQ? why the multiplier and quotients can not store in the ACC?


texts:
How do you determine the Time Complexity of a Genetic Algorithm(in general)? If possible.

I have been thinking about this a lot, and all of the teaching I have had is related to determining the Time Complexity of problems that are much less stochastic in nature.


texts: Is the multiset - subset sum problem variant not in NP?

texts:
If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g.

Set $a = \{1282,1588,3590,5138,5505,5777,6198,7962,8827,9838,10137,12037,15296,16089\}$

Multiset $a = \{1282,1282,3590,3590,5505,5505,6198,6198,8827,8827,10137,10137,15296,15296\}$

(above sets are samples, the real sets have lengths up to 64 and each element is up to 64 bits, I'm working with density-1 instances).

In both cases $N$ is the same (183 bits if we use $\sum_{i=1}^n \log_2 a_i$ or 224 bits if we use a more generic approach $\mathrm{Length}(a)\cdot \log_2 \max\,\{a_1, \dots, a_n\}$.

Is there any chance the repetitions could affect the problem so bad that could move the multiset version out of NP?

Everything I know and have read about subset sum for long time says both instances are equally hard, and subset sum and all its variant are NP-Complete and just dependent on the input size but I'm getting a weird different result.

(I found this discrepancy when I was validating the solver works well with multisets.)


texts: Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?

texts:
My professor presented the halting problem as $K' = \{ w \in \{0, 1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent to $K = \{ \langle M,v \rangle | M $ Halts on $v \}$.

I tried to think it through and this is my understanding so far:

$(1)$ If $w \in K'$ then we can define $f(w)= \langle M_w,w \rangle$ then $w \in K' \Leftrightarrow  f(w) \in K$ so we have that $K'$ can be reduced to $K$

$(2)$ And for the other way around, we define $g(\langle M,v \rangle) = \langle M' \rangle$ where $M'$ is the TM that simulates the TM $M$ on input $v$ and halts iif $M$ halts on that input. So we get that both languages are reducible to each other thus equivalent.

But I'm not sure about part $(2)$, is the reasoning correct? Can someone shed some light on my problem?


texts: Question as regards a proof of the Time Hierarchy Theorem

texts:
I'm referring to the proof outlined here (and wikipedia.org):
https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem

In my understanding, if I relaxed the conditions such that $K$ decides the input in time $O(f(m)^3)$, there should not be a contradiction in the final step because an appropriate TM $K$ should really exist.

Under this condition, $N$'s running time should be $O(f(2n+1)^3)$.

Finally, I arrive at the conclusion:

If $N$ rejects $[N]$ (which we know it does in at most $f(2n+1)^3$ operations):
By the definition of $N$, $K$ accepts $([N],[N])$.
Therefore, by the definition of $K$, $([N],[N])\in H_f$.
Therefore, by the definition of $H_f$, $N$ does accept $[N]$ in $f(n)$ steps.

To me it seems that 1. and 4. would still contradict. What did I do wrong?


texts: People crossing a bridge (a proof for a greedy algorithm)

texts:
The problem

Some people are crossing a bridge. Each one takes a different time to pass.

Assume the people are sorted by their passing time increasingly.

These are the conditions of crossing the bridge:

only 1 or 2 people can cross the bridge at the same time in the same direction;
the speed of the two people crossing is the same as the slower one;
it is night and there is only one flashlight;
the people passing the bridge must carry the flashlight;
the flashlight cannot be thrown over the bridge so it must be carried back to the other end of the bridge.

My greedy solution

The obvious solution seems to be using the fastest guy to take every one to the other end and come back for the rest.

The proof

I tried to prove it like my text book CLRS:

  Cast the optimization problem as one in which we make a choice and are
  left with one subproblem to solve.
  Prove that there is always an optimal solution to the original problem
  that makes the greedy choice, so that the greedy choice is always
  safe.
  Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if
  we combine an optimal solution to the subproblem with the greedy
  choice we have made, we arrive at an optimal solution to the original
  problem.

I tried something like this:

If we assume the set of all people in the start is $P$ and the set of all people in the destination is $D$ and $O(x)$ is the function that gives the optimum time by getting the set of people and people $p_i$ and $p_j$ are chosen to pass the bridge and $d_k$ is chosen to return the light and $d_k \in D\cup \{p_i , p_j\}$ then:

$$O(P) = Max( t(p_i) , t(p_j) ) + t(d_k) + O(P-\{p_i , p_j\} \cup {d_k})\,,$$

where $t(p_i)$ is the time it takes for person $p_i$ to pass.

Now I have to assume I have an optimal solution $OS$ and show that I can use the greedy choice instead of the choice the $OS$ has made.

I do not know how to proceed further.


texts: Show that the collection of Turing-recognizable languages is closed under homomorphism

texts:
I have seen this question here,
Closure of Turing-recognizable languages under homomorphism
But actually this question answers the question of "What is the relation between homomorphism and concatenation?", so I still have a problem of how to show that the collection of Turing-recognizable languages is closed under homomorphism. Could anyone help me in doing so please?

In my opinion closure under homomorphism is very similar to closure under Kleene Star, but I am convinced that I have to put marks on any number of tape cells because my language $f(L)$ may contain many strings, am I right?

Many thanks!


texts: Image segmentation of a high resolution 2D binary image into clusters, threads and points

texts:
I use python3 script to find out the area proportion of pixel clusters, threads and points in my image. They are originally 8-bit greyscale TIFF images with a resolution of 2048x2168 pixels. I have binarised it into an image composing of the matrix (white) and component particles (black). The particles have random morphologies. I would like to widely categorise them as:

Points which can range between 1x1 to 3x3 blocks of independent square pixels completely surrounded by the matrix
Threads which are linear or diagonal sets of continuous pixels of at least 3 pixels in length and at most 3 pixels in width
Clusters which are any randomly shaped closed morphologies with more than 10 pixels in overall area (or any arbitrary high value)
Others which by any chance is not included the three listed above

Here is an Example(400x400) portion of the image.

First of all, I am confused about the order of progress in this situation. I could scan the whole image pixel by pixel and extract the points in my first step. A second scanning can see for threads and final scanning can look for clusters using boundary tracing.

As you can see, the component is spread in a very uneven manner. To a human eye, the threads appear as blocks with very low aspect ration (AR). Points as noises and clusters as blocks of distinguishable larger areas. Therefore the accuracy level of this classification scheme does not needfully be a high score. The objective, however, is minimal user interaction (fully automatic). One another thing to note is that holes within clusters or threads (that does not break it) can be ignored. The ultimate aim is to get the area percentage of each of the objects so that the detection method can be limited keeping it in mind.

Some specific questions:

Let us say that I identify a large cluster of pixels within the image. How can I split this into a component cluster (high AR) and thread (low AR)? (something similar to Watershed Algorithm)
Should I go for the OpenCV contouring method like Border Following or border tracing (and later ignoring the holes) or something more suitable
I was curious to know if there have been approaches in the past that used random sampling of pixels instead of a pixel by pixel scanning across the entire image.

I would like to know the steps a computer scientist would follow in such a scenario. I am a beginner in image processing and any reference material would be appreciated. For anybody interested in metallography, the images are micrographs and what we see are defects. I am trying to separate cracks, porosities and other openings based on pixel density.


texts:
I'm trying to figure out Time function and Big O of a nested loop code,

public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
  int n = first.length, count = 0;
  for (int i=0; i < n; i++) { // loop from 0 to n-1
    int total = 0;
    for (int j=0; j < n; j++) // loop from 0 to n-1
      for (int k=0; k <= j; k++) // loop from 0 to j
      total += first[k];
  if (second[i] == total) count++;
}
  return count;
}

According to my calculations the time function should lie in $n^4$, but the right answer is $n^3$.
Here are my solution steps,

Constant operations = 2 times
i-loop = 0 to n-1 = n times (although it's 2n+2, but I would pick the most higher order term)
Constant operation = 1 time
j-loop = 0 to n-1 = n x n times = $n^2$ times
k-loop = 1+2+3+...+n-1+n = n x n x $n\frac{n+1}{2}$ times = $\frac{n^4 + n^3}{2}$ times

What I'm doing wrong, can someone please point out.


texts: Reducing a graph without changing its chromatic number

texts:
Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name?

Take this cactus graph as an example (although my question is about an arbitrary graph):

The edges with vertex of degree 1 could be removed without affecting the vertex chromatic number. I think something similar should be possible with cycles e.g. removing the two vertices in the bottom of the cactus should not affect its chromatic number.

Are there polynomial algorithms that removes edges to the extent that no more edge can be removed without affecting an arbitrary graph chromatic number? I would prefer not to reinvent the wheel.

If the answer is no, are there algorithms that remove an arbitrary number of edges without affecting an arbitrary graph chromatic number?

My goal is to simplify graphs before feeding them into other algorithms.

I will also appreciate references to relevant literature. Thank you!


texts: Registering 3D-NIR image to thermal image and vice versa

texts:
In the past I have thought a bit about how to register a NIR-image and a thermal image and noticed that this is not trivial - one statement was that if I had the depth information for each pixel, the task would be much easier.

Now consider having a 3D-NIR camera (e.g. asus xtion) and a thermal camera and I want to map the thermal information to the depth map (the 3d cloud) or vice versa and the NIR information to the thermal information (and vice versa).

I thought I could do it simply like this:

Conduct a stereo camera calibration for the two cameras (-> R1,R2,T)
Use R1, R2 and T to transform the 3D points from 3D-NIR to the thermal camera's coordinate system
Use the camera matrix of the thermal camera to project the 3D points to its image plane
Now I know where the 3D points "fall" in the thermal image, which gives me a depth value (and intensity value, because the depth map and NIR-image are aligned) for each pixel in the thermal image.

Which to me sounds similar to the procedure described in this answer by D.W..
However, I can't find any article describing this method. Always there seems to be some form of feature matching step, e.g. here.

Also, thinking about this, the above solution can not really work, I believe. Consider the case where the two cameras look at an object from different sides. The 3D camera will calculate the depth for a point p1 in the world. When projecting p1 to the thermal camera's image plane it will fall in pixel x. However, since the thermal camera looked at another side of the object, another point in the world p2 actually formed pixel x when the thermal camera took the image - and thats what the measured temperature in x is for (i.e., p1 and p2 roughly lie on a line viewed from the thermal camera).

So, all in all:

Is my statement that the outlined solution can't always work correct?
Under which circumstances does the outlined solution work?
What do I need to keep in mind when building the setup?
How else to go about this problem?

Thanks for reading this long post!


texts: How do I form a parse tree for equations?

texts:
I have the following equation

if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }

I was thinking of something like this however I've never done it with actual functions so I'm not quite sure how to proceed.

What are the steps to take in creating a parse tree for something like this?


texts: find a regular expression and FA that each define $L_1 \cap L_2$

texts:
I am trying to find a regular expression and finite automaton that each define $L_1 \cap L_2$, where $L_1 = (ab^*)^*$ and $L_2 = b(a+b)^*$.

How would I start doing this problem?

So I would draw a FA and when I draw it I would have a complement meaning take anywhere you have a plus, get rid of it and anywhere you didn't have a plus add one in. Am I on the right track?


texts: What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams)

texts:
For example, this gate:

looks like an OR gate, except there's a dot to the right. The dot is reminiscent of the fact that there's a dot in the NOT gate, so I wonder if it has something to do with that. There's no NOT after this gate in the diagram I'm looking at, so this doesn't to be implementing NOT OR or something like that...


texts: Where is the register position in a CPU (real image illustration)?

texts:
I hear that register is in CPU, but the CPU iamge I generally see doesn't mark the position of register, can anyone provide a real image of CPU with mark of register (for example 32 registers in MIPS)?

CPU image example , but not marking register position.

Another site with 3D CPU Model also without register position.


texts:
I have a time series that I want to predict with an LSTM.  I am able to get very good results using 50 datapoints predicting 51, but I struggle to get any accuracy using something like 200 datapoints to predict 220.  After an epoch, my network outputs 0 for all inputs.  Is there a technique for predicting multiple timesteps ahead of the final output with a neural network?

For example, would it make more sense to predict 1 timestep ahead 20 times in a row feeding the outputs back in to get to that 20th timestep?  Training it on a sequence followed by the timestep 20 ahead does not seem to work so far.


texts:
I am reading the paper "A new approach to intrusion detection using Artificial Neural Networks and fuzzy clustering" by Gang Wang, Jinxing Hao, Jian Ma and Lihua Huang (Expert Systems with Applications, 37(9):6225–6232, 2010, available at Science Direct). I don't understand the term "detection stability". What does that mean?

The context is that existing intrusion detection systems are claimed to have poor "detection stability" when it comes to rare attacks.


texts: Are the capabilities of programming languages the same?

texts: Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could (theoretically) do the exact same thing with ever language, don't you?


texts:
I have a CFG:

S --> 0S1S | 1S0S | ε

I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me.

So if I pick a string, let's say 010110, I just have to show that there are two different parse trees for the string?


texts: How would one simulate the law of conservation of energy?

texts: I'm new to computer science, but I've studied physics for a while. I'm just curious, if one wanted to make a simulation of the law of conservation of energy, on a large scale, how would it be done? Most simulations take shortcuts for objects off screen, or may even skip them entirely during iterations. The objects may be frozen in place of screen, or grouped together if not interacting. Can these tricks be applied when simulating conservation of energy, without violating the law? Thanks.


texts:
I have a problem where I need to sort array of arrays.
For A being a array  arrays (a1,a2,a3,...an)
were each a = {0...d} d=fixed number of elements.
*The assumption all sublists will have fixed number & same of elements n. *sublists are already sorted from least to greatest
For example A = [{-2,-1,3},{-1,-2,INT_MAX},{1,2,5},{-50,10,75},{INT_MIN,11,65}], how this be sorted?

Should I consider the range as sorting criteria = MAX-MIN So [{-2,-1,3} range will have a range of 5 , and so on then I will sort each list on the increasing range?

Or, any ideas?
After sorting search will be easy, but how will i deal with duplicates.
For example, if i want to find -2 ,it occurs in both {-2,-1,3},{-1,-2,INT_MAX}.
The above problem is simplification of multiple binary trees that I have , for which I know their min and max node values, but I want to know which tree to start the search in.
Please just suggest algorithms efficient O(N log N) for sort & O(log N) for search, no need for implementation.
Thanks again.


texts: What are transitive successor and transitive predecessor in the graph?

texts:
I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are:

  transitive successor and transitive predecessor of a node $i$

I tried to find definitions of those online, but I'm having hard time with it. Everything I find talks about transitive reduction.

Can someone give a clear definition of this? Any help is appreciated.


texts: How to write a custom editor for a new programming language?

texts: Let's say I've finished my compiler for my new language. Next step is write a custom editor with syntax highlighting (type checking and semantic can wait), is there a cookbook or any kind of guidance to accomplish this project?


texts: For all nodes in a directed graph, find whether they are on a non trivial cycle (length > 2)

texts:
I'd like to find an efficient algorithm to answer this question:
For each node in a directed graph, find whether it is on a non trivial cycle (length > 2)

It sounds simple at first, but I still don't have an efficient sub-quadratic solution. I have some ideas but I'm pretty sure I'm trying to reinvent the wheel. Is there a well known algorithm for this?

For example, to answer the question: For each node in a directed graph, find whether it is on a cycle (of any length) - I just run strongly connected components, and remove all single element component that does not have a self loop, all remaining components have all their nodes in some sort of a cycle

Definitions

I'm not sure if this has any official meaning, but here is my interpretation to these terms for the context of the question:

Trivial Cycle:

A cycle of length 1 or 2 (e.g. only 1 edge in a self loop, or node A points to node B, and node B points to node A, total of 2 edges)

Non Trivial Cycle:

All cycles longer than 2 edges

Requirement

Given a Directed Graph, for each node, tell if it is on a non-trivial cycle

Examples

A = false //because it has no cycles

A<->A = false //because the only cycle is of length 1 edge (self loop)

A<->B = false //because the only cycle is of length 2 edges

A<->B<->C = false //because all cycles are of length 2 edges

A<->B, A<->C = false //because all cycles are of length 2 edges

A->B->C->A = true  // because e.g. A->B->C->A is length 3 edges

A<->B<->C->A = true // because e.g. A->B->C->A is length 3 edges

A<->B<->C<->A = true // because e.g. A->B->C->A is length 3 edges

What I tried

Brute Force: an (at least I think) $O(|E|\times(|E|+|V|))$ or something close to it, which I (probably incorrectly) file under an "~$O(N^2)$ish" algorithm:

for each vertex $v$

if it has a self loop, temporarily remove it
for each outgoing adjacent vertex $w$ (edge $v \rightarrow w$)

if there is a path from $w$ back to $v$ (edge $v \leftarrow w$) then temporarily remove that back edge.

do BFS/DFS to find whether there is a path starting from $w$ and ending in $v$, if there is one it must be a non trivial path (as we removed all trivial ones) so do an early exit and return true (otherwise return false in the end)

This actually sort of works (although I couldn't come up with a mathematical proof, at least all unit tests pass)

Sketch for a Linear Algorithm: Here is where I'm a bit stuck, I have a gut feeling this can be done in linear time, but I didn't find an existing algorithm for it (doesn't mean there isn't, perhaps I'm just not looking good enough).

The idea sketch is to run strong connected components, then for each component remove all of the forms of A<->A, A<->B, A<->B<->C, A<->B<->C<->D... which I have a feeling can be done in linear time too. Then for all nodes in all components that still have nodes in them, mark them as "true" for "is on non trivial cycle"
But this is where it feels that I'm reinventing the wheel. Also if I can't do the math for the Brute force proof, it will be harder for me to do the proof for this.

Questions

Just for sanity, is my quadratic-esque solution indeed ~$O(N^2)$? (assuming I know that the average out degree is some low constant C (e.g. 2) so any O involving V and E can be written as V, C*V)
Main question - is there a linear solution to his problem? Is there a subquadratic one at all? Is there a known algorithm for this? if not, is my sketch a good starting point? Do you think it can be linear? How do I prove it?


texts: Resetting Vector clocks in distributed systems

texts:
I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks.
What i dont understand is about the resetting of the vector clocks.
Why do the vector clocks overflow and how the resetting is done in such scenario?


texts: Is the weighted transitive reduction problem NP-hard?

texts:
The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$.

When $E^t \subseteq E$ it is NP-complete. When $E^t \subseteq V\times V$ but not necessarily of $E$, this problem is polynomial time solvable. I am wondering about the edge-weighted version without the subset requirement.

My initial feeling was that with weights, the problem is very similar to TSP. The greedy approach seems to be invalid when adding weights. But several articles (http://bioinformatics.oxfordjournals.org/content/26/17/2160.short for instance) seems to imply that the problem is solvable in polynomial time.

If it was easy, then you could just add arbitrarily large edge weights to each edge not in the original edge set and keep the weights at unity for the others. Then you would have a polynomial time algorithm for the subset constrained problem.

So this should mean it HAS to be NP, right?

edit: Are there immidiate examples that come to mind of problems whose unweighted version is easy, but gets hard when weights are added?

edit: by edge-weighted, I mean we are interested in finding the graph with the smallest total edge cost


texts: In type systems, is there a name for SQL's way of cutting and combining record types into new types?

texts:
I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it.  I'm talking about the ability to do this (in Scala-ish pseudocode):

// Define some types that correspond to table rows in relational DB
class User
   val id: Int
   val name: String
   val email: String
   val created: DateTime

class Comment
   val id: Int
   val text: String
   val userId: Int
   val created: DateTime

// Call a select/join query function
val list = select c.id, c.text, u.name
           from comments c join user u on c.userId = u.id ...

And then list gets a type of something like List[R] where R is an unnamed record type with properties id, text, name, or maybe c.id,c.text,u.name.

Some languages, like Scala, support you writing that select function so it returns a tuple type (Int, String, String), but not a type with named fields.

Is there a name for that?


texts:
According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe queries. (In other words, all SQL queries have a complexity in $\mathsf{Q(FO(COUNT))}$, and all problems in $\mathsf{Q(FO(COUNT))}$ can be expressed as an SQL query.)

Based on this result, from theoretical point of view, there are many interesting problems that can be solved efficiently but are not expressible in SQL. Therefore an extension of SQL which is still efficient seems interesting. So here is my question:

  Is there an extension of SQL (implemented and used in the industry) which captures $\mathsf{P}$ (i.e. can express all polynomial-time computable queries and no others)?

I want a database query language which stisfies all three conditions. It is easy to define an extension which would extend SQL and will capture $\mathsf{P}$. But my questions is if such a language makes sense from the practical perspective, so I want a language that is being used in practice. If this is not the case and there is no such language, then I would like to know if there is a reason that makes such a language uninteresting from the practical viewpoint? For example, are the queries that rise in practice usually simple enough that there is no need for such a language?


texts: Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2

texts:
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$

whereas $|w|_a$ is the number $a$'s in the word $w$ and $|w|_b$ is the number of $b$'s in $w$.

We should give a grammar (of any type) for $A4$.

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

I can't seem to be able to give a comprehensive grammar for this without breaking that rule. Any tip would be greatly appreciated.


texts: What is the complexity of finding the predecessor of a node in a doubly linked list?

texts:
This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node.

But the answers from the web suggest that it should be O(n). Where am I getting it wrong?

Can someone please help me out???

Thanks in advance!


texts: Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine?

texts:
Let $S_{n}$ be an input set whose elements are length $n$, namely $S_{n} = \Sigma^{n}$. For every probabilistic polynomial-time algorithm $A$ and any $u \in \Sigma^{*}$, there exists a function $f^{A}$ such that $f^A(u) = \mathrm{Pr}[A(u) = 1]$. And let $f^{A}_{n} = \left.f^{A}\right\vert_{S_{n}}$ be a function from $S_{n}$ to $[0,1]$.

Is there some properties about what $f^A_n$ looks like? Or is there some references that introduce about this?

Indeed, let $F_{n} = \{ f^{A}_n \mid A \text{ is a PPT algorithm} \}$. And if we define
$$\mathrm{Dist}_{n}(f^{A},f^{B}) = \sum_{u \in S_{n}} \left\vert f^{A}(u) -
 f^{B}(u)\right\vert$$
and
$$d_{1}(n) = \inf \{ \mathrm{Dist}_{n}(f^{A},f^{B}) \mid f^{A} \neq f^{B} \}$$
how does $d(n)$ grow?

How about
$$d_{2}(n) = \sup_{g} \inf_{A} \mathrm{Dist}_{n}(f^{A},g)$$
where $g$ is a function from $\Sigma^{*}$ to $[0,1]$.


texts:
Maximum directed cut: Given a directed graph $G = (V, E)$ with nonnegative edge costs, find a subset $S \subseteq V$ to maximize the total cost of edges out of $S$: $\mathrm{cost}( \{  (u \to v) \mid u \in S \text{ and } v \in \bar{S} \})$.

I am trying to come up with a greedy algorithm for Maximum directed cut with factor 1/4.


texts:
The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows:

  Let G be a directed graph and S be an empty stack.

  While S does not contain all vertices.

  Choose an arbitrary vertex v not in S.
  Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.

  Reverse the directions of all arcs to obtain the transpose graph.
  While S is nonempty:

  Pop the top vertex v from S.
  Perform a depth-first search starting at v in the transpose graph.
  The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

But in my textbook - Sedgewick's Algorithms (fourth edition) - it describes the steps of the algorithm as follows:

  Given a digraph G, compute the reverse post-order of its reverse digraph. GR
  Run a standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerial order
  The set of all vertices...

The conclusion drawn in the third step is identical, as are the operations performed in the first two steps, but it seems that those two steps are given in opposite orders: Wikipedia tells me to start by doing a DFS on G and then transposing it, doing the second DFS on GR, whereas my textbook suggests that I begin by transposing G, do the first DFS on GR and the second on G.

My primary question is: Am I understanding this correctly, or am I misinterpreting what one or the other is saying?

Secondly: Intuitively, it seems as though these operations are transitive and therefore that these two "different methods" are in fact equivalent, and will always yield the same final result. I've tested this intuition on a couple of digraphs and it seems to hold true - but is it?

Thirdly: Assuming it is, is there any objective reason to prefer one over the other, or is it simply a matter of preference?

  NOTE: As of now, this question is cross-posted on StackOverflow. I'm an established user there, so I know that cross-posting is generally frowned upon, but I've just joined this SE and am curious to gauge the response I get here relative to what I get there. I will delete one or the other after doing so. If you'd like me to do so immediately, please comment.


texts:
INPUT: weighted undirected graph in the form of adjacency list

OUTPUT: adjacency list without the edge e

Naive approach is:

for(int i = 0; i < adj.get(e.s).size(); i++) { // loop through adjacent of s
  if(adj.get(e.s).get(i).v == e.t) {           // find t and remove it
    adj.get(e.s).remove(i);
    break;
  }
}
for(int i = 0; i < adj.get(e.t).size(); i++) { // loop through adjacent of t
  if(adj.get(e.t).get(i).v == e.s) {           // find s and remove it
    adj.get(e.t).remove(i);
    break;
  }
}
O(k) - k is number of adjacent vertices

A faster approach is to use adjacencyMatrix but my algorithm has alot of traversals involved and looping through each dimension in the adjMat costs more despite a O(1) edge removal.

How can I speed up removing an edge? (used in generating a MST (kruskal))


texts: Is a two-opt move guaranteed to produce a non-worse tour?

texts: I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". However, from my understanding and subsequent experiments, it appears this heuristic does not give any guarantee to at least not lead to a worse tour. If this is so, I don't understand how a two-opt move is any better than a random swap of cities. I would really appreciate if this can be clarified for me. Thanks!


texts: How to speed up process of finding duplicates/similar items in a large amount of strings?

texts:
Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (within 80% threshold) to this document.

We implemented Levenshtein distance algorithm and we limit amount of documents current document has to look over (via a set of hash codes), but this solution is still horribly slow (since it's M*N problem) even after we launch it on multiple cores.

Are there any suggestions/techniques we can use to speed up the processing? The requirement for it is to work in near real-time (I guess we can accept up to 10-20 minutes gap). The only idea I have is to split exact duplicates and similar docs processing in two steps and use something like HyperLogLog for duplicates.

The texts are from social media (tweets, blog posts, etc.) so it's reasonable to assume that duplicates share are far greater than that of a similar docs.

I apologize if my usage of terminology isn't very accurate.


texts: Trading States for Symbols with a Turing Machine

texts:
Show that for each string $w ∈ \{0, 1\}^∗$ there exists a stay-put Turing machine

$$M_w = (Q, \{0, 1\}, \Gamma, \delta, s, q_{\mathit{accept}}, q_{\mathit{reject}})$$

with $|Q| ≤ 5$ states that starts on a blank tape in state $s$ and ends in state $q_{\mathit{accept}}$ with the
tape content $w$ beginning in the first cell and the head under that cell.

That is, starting on a blank tape, the machine outputs $w$ and stops in $q_{\mathit{accept}}$.

I know that if there were infinite states then we could put each letter into its own state so that we could print the letter when needed, but I don't know how to reduce it to 5 states.


texts: Inline caching in not object oriented languages

texts:
I've been recently studying inline caching as a technique to optimize method dispatch in object oriented languages. Basically, the idea is that one can remember what was previously dispatched and predict that things will go on in the same way.

My question is whether this technique has been used in pure functional languages (I'm a native of Scala which mixes both paradigms thus the uncertainty).


texts: Would f(n) = O(g(n) + h(n)) imply the relationship between f(n), g(n), and h(n)?

texts:
I come across the following claim:

For all positive, increasing function $f$, $g$, and $h$, if we have $f(n) \in O(g(n) + h(n))$, then we can conclude that either $g(n)\in \Omega(f(n))$ or $h(n) \in \Omega(f(n))$, or both of them are correct. (We say that a function $f$ is positive and increasing, if we can get that $f(x) \geq 0$ for all $x \geq 0$ and $f(x) > f(y)$ if we have $x > y \geq 0$.)

To me, it seems like it is a correct claim. Here are my thoughts.

From $f(n)\in O(g(n) + h(n))$, we get to know that $f(n)\leq c(g(n) + h(n))$. For $g(n)\in \Omega(f(n))$ and $h(n)\in \Omega(f(n))$, we get to know that $g(n)\geq c_2f(n)$ or $h(n)\geq c_3f(n)$. I just feel like in order to get $f(n)\leq c(g(n) + h(n))$, then at least one of $g(n)\geq c_2f(n)$ and $h(n)\geq c_3f(n)$ should hold. If not, then we can only get something like $g(n) + h(n)\leq f(n)$.

And I also can't think of a counter example about it.

I am not sure it is true or not? If it is false, could you please give out a counter example?


texts: Longest path in a directed acyclic graph with constraints

texts:
Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'.

What is the complexity of this problem?


texts: Quantum Algorithms and CT vs Classical counterparts

texts:
How is Quantum Algorithms and Complexity Theory essentially different from Classical Counterparts?
Also how are non-deterministic Turing Machines(NTM) different from Quantum Turing Machines(QTM)? More precisely, Is there an QTM that can solve the SAT 'fairly fast'?

I wanted to know how are QTMs different from NTMs, for instance we have parallelism in NTMs which (i think) are not exhibited by QTMs, also there are certain class of problems (in linear optics) that the QTMs can solve easier than NTMs..

So, what are their limitations and computational powers?


texts: If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

texts:
Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time.  Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, if someone shows that UNIQUE k-SAT is in P,  does it imply P=NP?

References

L. G. Valiant and V. V. Vazirani, "NP is as easy as detecting unique solutions." Theoretical Computer Science 47:85–93, 1986. (PDF on ScienceDirect.)
C. Calabro, R. Impagliazzo, V. Kabanets and R. Paturi, "The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs".  Journal of Computer and System Sciences 74(3):386–393, 2008. (PDF at ACM Digital Library; free PDF.)


texts: Proof of Strong Duality Via Farkas Lemma

texts:
I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:

Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$

Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$

Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.

The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.

Prove this using the following hint: If it is false, then there cannot be any solutions to

$$AX \ge b, \; A^tY \le c, \; X \ge 0,\; Y\ge 0, \; c^tX \le Y^tb.$$

My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.

Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.

Assume for contradiction that the hypothesis is wrong:

$$\begin{bmatrix}
A^t & -c\\
0 & -1
\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$

By Farkas' Lemma, we know the following system is solvable:

$$\begin{bmatrix} X & w_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w_2 \ge 0$.}$$

Now, from the system above, we may write $XA^t \ge b^t$, and
$Xc \le \lambda - w_2$.

If $w_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1.  However, one cannot reach that conclusion if $w_2$ is exactly $0$.

I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.


texts:
Is there any systematic (algorithmic) method to convert an $\omega$-regular expression like

$
(a^∗)(b)(b^∗)(a^∗)(c^\omega)
$

to an LTL property?


texts:
Note: I have posted a hugely expanded version of this question on cstheory.

Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{NSPACE}$$[O(k \cdot \log (n))]$. Since the region

X    X
X XX XX
X  X  X
XX    X
    XXX

has neither boxes nor storage locations and is such that a box can be pushed from the top to exit out the bottom but can't be pushed from the bottom to the top, the problem "Is there a matching from one given set of $k$ vertices to another given set of $k$ vertices in the transitive closure of the given directed grid graph?" can easily be reduced to the problem I am asking about.

  Is anything else known about the complexity of Sokoban with only $k$ boxes?

In particular, is it the case that solvable instances always have solutions of length $n^{o(k)}$?

I tried to construct a bounded-counter gadget, but aside from realizing that such a gadget would require a box being moved along it when the counter's value is sufficiently large (since otherwise the player could just "pretend" to have incremented or decremented the counter), I wasn't able to get anywhere with that.


texts: How is the data stored in AVL tree in a memory?

texts:
I have been struggling to visualize how is the AVL tree is stored in memory?
Does it store data in array or list, If so how is it connected with its child and parents.


texts: Selecting elements from two arrays to get a target sum

texts:
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.

Design an algorithm to solve the following problem.

For each index $i$ ($1\leq i \leq n$) either select $A[i]$ or $B[i]$ but not both such that the total sum of the picked elements from each of the arrays is at least $k$?

For example $A=[1,2,3,4,5,49]$ and $B=[1,10,10,10,22,12]$, target $k=50$.

Solution

Pick the first and the last elements from A whose sum is 50.

Pick the rest (all but the first and the last elements) from B. That sums up to 52.

So in both Arrays we get a sum at least the target value 50.

Can someone help me to find the algorithm to solve this problem?


texts: How to distinguish empty cells from cells outside of the input cells?

texts:
Setup

I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's.
My alphabet is {a,b}, and we use a diamond in class to represent an empty space.

Problem

The part I'm having trouble with is returning to the beginning of the string.

So far

At first I was planning on taking a character(a) marking it with a diamond, moving right until the other character(b) is found, marking that with a diamond, then moving left until the other's other character(a) is found, and repeating the process.
The parenthesis are for example, it could have been b,a,b just as well.

Then at the end if there is an outlier I will know the number of a's and b's was not similar.

But then I developed an example language
ab... and realized that this process will never end in this case, so instead I need a way of determining when I have reached the beginning of the string.

So now my question...

Is it possible to determine when I have reached the beginning of the string without introducing another letter into the alphabet, or another special character like the diamond?


texts:
Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm.
$$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$
$$T(1) = 0$$
Solution is given as:
$$T(n) = O(logn*log(log(n)))$$


texts: Algorithm to find non-overlapping intervals that minimize standard deviation

texts:
I am looking for the name of an algorithm category, or even specific algorithms, that solve the following problem.

I have noisy data.  For simplicity, let this data be represented by numbers.  I have the full data set in RAM.  In this noisy data, I want to find signal.  Signal is an interval of contiguous numbers that are close-enough to each other.  In other words, their standard deviation is below some threshold.  At the same time, I don't trust the signal if it is too short-lived, so it must be at least n contiguous numbers long.

In other words, I want to find non-overlapping intervals of values, where each interval has at least n values, and those values have a standard deviation of at most sd.

The intervals do not need to be contiguous.  (Signal is intermittent in all the noise.)

I want to minimize sd in these intervals, so given a choice of one interval with a higher sd or two intervals with a lower sd, I prefer the latter. (As long as both intervals have at least n values, as I said earlier.)

For example, suppose I configure a minimum interval size of 5, and I have the following list:

  7, 7, 8, 7, 7, 4, 5, 5, 5, 4, 6, 6

The sd for this whole interval is 1.31. If we split it into

  7, 7, 8, 7, 7

then drop the middle 4, and continue to the next interval,

  5, 5, 5, 4, 6

then drop the final 6, we get sd of 0.45 and 0.71, which intuitively seems optimal to me.

Had we kept the middle “4” in the second interval, that interval’s sd would have been 0.82. Had we kept the final “6”, that interval’s sd would have been 0.76. We could have decreased sd even further by removing more elements, except intervals in this example must have at least 5 elements.

(Note, I came up with this particular split intuitively, so it may not be the optimal split.)

What algorithm(s) can solve this problem?


texts: Kleene algebra - powerset class vs class of all regular subsets

texts:
I am currently studying materials for my uni subject. There are two examples of Kleene algebras, but I don't see what is the difference between them.

Class ${2^{\Sigma}}^{*}$ of all subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.
Class of all regular subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.

What is the difference between ${2^{\Sigma}}^{*}$ and all regular subsets of $\Sigma^{*}$? What is that difference I don't see? Thanks in advance.


texts: How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

texts:
I’m trying to design a DFA
which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table if the DFA has dead state.


texts: Improving Time Bound of this Algorithm past $O(n^2)$

texts:
I recently came across the following interesting problem - one is given a sequence of Xs and Ys such as XXYXYXYYXYXXXYX, and consider a sequence to be good if, as you start at the left and move right, the number of Xs is greater than or equal to the number of Ys at any point except at the very end, at which the two quantities must be equal.

One must determine the number of points at which changing either a single X to Y or a single Y to X in a given sequence will yield a good sequence.

I initially considered traveling through the sequence linearly and checking if toggling the letter at that point would yield a good sequence, however that approach is on the order of $O(n\cdot n)=O(n^2)$ in the worst case where n is the length of the sequence. However, I was wondering if there was some faster method to do it.

EDIT: I made the observation that for any sequence, if the number of possible changes is greater than 0, than only one type of change will work (either changing an X to Y or Y to X) given the condition at the end that the number of X and Y must be equal.


texts: State whether the language is in $R$, $RE$, etc. The intuition for the solution

texts:
I saw the solution but can't understand the intuition of the following question:
Let's define
$$L^{\ge k} = \{w\in L : |w| \ge k\}$$
and
$$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^{\ge k} \}$$
$L\in R$ because $L=\emptyset$, the proof is a bit long and anyway I understood most of the steps, My question is about the intuition, what is the hint here that $L=\emptyset$ or any other hints for the solution?
EDITED
$$
\overline{HP}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\}
$$
It's the complementary language of
$$
HP=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}
$$


texts: Numerical problem on Access time in Cache memory

texts:
For a system with two levels of cache, define:

$T_{c_1}$ is the first-level cache access time
$T_{c_2}$  is the second-level cache access time
$T_m$ is the memory access time
$H_1$ is the first-level cache hit ratio
$H_2$ is the combined first/second level cache hit ratio

Provide an equation for the average access time $T_a$ of a read operation.


texts: Are there any existing problems that wouldn't be solvable with a halting oracle?

texts:
I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible for a Turing machine also shows that it is impossible for a Turing+oracle to decide the Halting Problem for a Turing+oracle. Are there any actual, practical, examples of problems unsolvable by a halting oracle?

Note: by "oracle" I mean oracle for a standard Turing machine, not a TM with an oracle itself.


texts:
I'm looking for a computational method for projecting data from one grid onto another dissimilar grid while preserving the area of the original grid. I'm not quite sure what these methods would be called, but think draping a blanket over an uneven surface, a bit like what's being done here, except my original data set's grid extents will be smaller than the terrain data set's grid extents. I don't care about the fancy graphics portion of it, I'd just like to project my original (2D flat) data set onto the topologically varying data set.

My apologies if I'm being unclear or if I'm asking an obvious/simple question. Thanks!


texts:
I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of computing $g^{mn}$ directly.

My question stems from an implementation of the Paillier cryptosystem that I'm working on. Right now, I'm following the original paper "Public-key cryptosystems based on composite degree residuosity classes", scheme 3 with the recommendation of generating $g$ using DSA. I have looked at different methods of computing modular exponentiation directly such as square and multiply, k-ary, window sliding, etc.  I want an algorithm for computing $g^{mn} \bmod n^2$ that does not rely upon knowledge of the factorization of $n$.


texts: What is the time complexity of calling successor $n$ times during tree traversal?

texts:
According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(\log n)$.
Yet, according to this stackoverflow post on the time complexity of an inorder traversal of a binary search tree, if you call the successor function $n$ times, the time complexity is $O(n)$.

What resolves the apparent contradiction between:

  If I call the sucessor function once, the time complexity is $O(h)$, which could be $O(n)$ or $O(\log n)$, depending on the kind of tree.

AND

  If I call the successor $n$ times, the time complexity is $O(n)$ in a balanced tree.

Shouldn't tree traversal take $O(n^2)$ or $O(n\log n)$ time?


texts: Regular expression for binary words with few zeros

texts:
What is the regular expression for the set of binary strings with the property that

every $0$ is followed by exactly $m$ times $1$ and
every $0$ is preceded by at least $n$ times $1$?

$m$ and $n$ are integers.


texts:
I can define any boolean function (I think) using and and not, or using or and not (plus a constant 0 or 1).  And I can define or in terms of xor.  And then there are nor and nand.  So I am wondering:

Why are we traditionally taught boolean logic using and, or and not?
Is there a "simplest" set of boolean functions that can be used to define all the rest?  Or are there "families" of functions that are equivalent in some way?
Do we always need 0, 1 and 2-argument functions (eg 0 or 1 constants, not, and and) to define a family?  Or are there any boolean functions with more than 2 arguments that are fundamental (can appear in an answer to 2)?  Or well-known?  Or common?  If not, what's so special about 0, 1 and 2 arguments?
Is there some underlying mathematical theory (perhaps based on symmetry?) that makes these kinds of questions easier to answer?  For example, how do you rigorously derive all answers to questions 2 or 3?

(I know that a partial answer to 2 (equivalent families) is "yes" because I remember De Morgan's theorem from college, but that's about as far as I can get).


texts:
My question is a very basic one. It seems feasible to believe that $\mathsf{P = NP}$, because there is some "pathological" good algorithm for SAT, yet it is impossible to prove that the algorithm is actually correct and/or that it runs in polynomial time, in a standard axiomatic system like ZFC.

Let's fix a logic $L$ that is strong enough to encode statements about Turing machines. (Edit: I should have clarified that by this I mean the same requirements as Godel's second incompleteness theorem. For the purposes of this question, assume that $L$ proves the peano axioms PA.)

Then define
\begin{align*}
\mathsf{ProvableP} &:= \{A \mid L \text{ proves } [A \in P]\} \\
\mathsf{ProvableNP} &:= \{A \mid L \text{ proves } [A \in NP] \}
\end{align*}

Now we have that $\mathsf{ProvableP} \subseteq \mathsf{ProvableNP} \subseteq \mathsf{NP}$. But does $\mathsf{ProvableP} = \mathsf{ProvableNP}$? How does this relate to the original P vs NP question?

Partial answer: The SAT problem is $\mathsf{ProvableNP}$-complete, but $\mathsf{ProvableNP}$ is closed only under provably polynomial-time reductions, not necessarily all polynomial-time reductions. However, this does seem to show that if $\mathsf{ProvableP} = \mathsf{ProvableNP}$, then since SAT is in $\mathsf{ProvableNP}$, $\mathsf{P} = \mathsf{NP}$.

So what is remaining is the converse: if $\mathsf{P} = \mathsf{NP}$, does $\mathsf{ProvableP} = \mathsf{ProvableNP}$?

I picked the P vs. NP question because it's the "canonical" unsolved problem in complexity. But, a similar question could be asked about any two complexity classes.