texts: Authority section in DNS packet always contains NS records?

texts: I'm new to DNS and I'm trying to understand the DNS packet format. From what I understand, the authority section of a DNS packet gives information about servers that are authoritative for the domain name in question. From playing around with dig on UNIX (and from intuition), it seems as though records in the authority section are always NS records. However, I couldn't find confirmation of this anywhere. Is this correct? If not, what does it mean for an authority record to not be an NS record?


texts: Karp hardness of two vertex sets in a digraph

texts:
Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that:

$|S|+|T|=k$
For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming from $T$. In other words, from $v$'s point of view, $S$ is the source, $T$ is the terminal. Hence their names.

So, can this be solved by an efficient algorithm or it is NP-complete?


texts: What is the meaning of the "*" in names of various learning/search algorithms?

texts:
For example, consider L* algorithm for learning a regular language, or A* search algorithm. What do these names - in particular, the star character - mean?
It looks like it might be the case that the star is used in a way similar to the Kleene star - e.g. apparently, A* was preceded by A1 and A2.


texts: Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

texts:
This question is related to my previous question:

Looking for a set implementation with small memory footprint

I'm looking for information about combined data structures, which can efficiently represent a set S of non-intersecting sub-intervals of the given integer interval [0, MAX) with the single operation:

testAndInsert(min, max) - test if the interval [min, max] intersects with any of already existing intervals in the S; if no intersections are found, then insert the interval [min, max] into the set S, potentially merging it with one or two neighbor intervals; return success, if and only if the insertion was done.

I'm asking about combined data structures, because it looks like we have two evident choices - linked data structures (for example, various binary trees) and array-based data structures (bitmaps). However, both of them have their own shortages:

Balanced binary trees will have O(log(n)) time complexity and look good, when number of intervals in the S is much less than the MAX. However each node of the tree will take at least 16 bytes (for links) on 64-bit machine. For example, if we represent all   odd integers in the interval [0, 1000), then we'll need 8000 bytes only for links.
Bitmaps will have O(1) time complexity, but take constant memory, which depends only on   the MAX. Representation of all the odd integers in the interval [0, 1000) needs only 125 bytes. However, when the MAX is large and the number of existing intervals is much less than the MAX, then most of the memory, taken by the bitmap, will be wasted.

I'm not actually focused on the time complexity - something between O(1) and O(log(n)) is acceptable, but in real situations the memory footprint of the data structure plays a very important role. If machine begins swapping because of lack of memory, then even O(1) data structure will work for ages.

Are there any data structures, which could automatically adapt themselves to the size of the S in this problem? For example, when we start with the empty S (no intervals at all), the data structure is linked, then it becomes array-based (piece by piece?), then it probably switches to storage of the S complement (free space is small) and becomes linked again?

P.S.: I know about the Boost ICL interval set and use it now, but I'm interested in other possible approaches.


texts: How can a 32bit CPU have an addressable memory size of 16TB?

texts:
Frequently, on a 32-bit CPU, each page-table entry is 4 bytes long, but that
size can vary as well.

A 32-bit entry can point to one of $2^{32}$ physical page frames.

If frame size is 4 KB (212), then a system with 4-byte entries can address $2^{44}$ bytes
(or 16 TB) of physical memory.

The above statement is taken from the book "Operating System Principles" by Galvin.

If all 32 bits in a 32-bit CPU are used to refer to pages , then we can have $2^{32}$ pages. But then no more bits will be left to point to memory inside a page of size $2^{12}$ bits since all 32-bits have been used up.

How can we thus say that $2^{44}$ bytes are addressable?


texts: Efficient algorithm to find a $C_{k}$ in an undirected graph, that has no $C_{k-1}$

texts:
Suppose that $G = (V, E)$ is an undirected graph, and $G$ is promised not to contain $C_{k-1}$.

Goal is to find any $C_k$ in $G$ using an efficient algorithm. Efficient, in this scope, meaning that finding all cycles and excluding all $C_{m>k}$ is out of question.

First thing comes in mind is to use depth-first search, and return if a cycle is found.

Since the problem is not finding all the $C_k$s, the algorithm should run approximately in $\mathcal{O}(|V| + |E|)$.
Is this really lower bound, or do we need an algorithm that has higher asymptotic bound?


texts:
A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing.  When there are many data items then a Bloom filter can result in a significant memory saving over a hash table.  The main feature of a Bloom filter, which it shares with a hash table, is that it always says "not new" if an item is not new, but there is a non-zero probability that an item will be flagged as "not new" even when it is new.

  Is there an "anti-Bloom filter", which has the opposite behaviour?

In other words: is there an efficient data structure which says "new" if an item is new, but which might also say "new" for some items which are not new?

Keeping all the previously seen items (for instance, in a sorted linked list) satisfies the first requirement but may use a lot of memory.  I am hoping it is also unnecessary, given the relaxed second requirement.

For those who prefer a more formal treatment, write $b(x) = 1$ if the Bloom filter thinks $x$ is new, $b(x) = 0$ otherwise, and write $n(x) = 1$ if $x$ really is new and $n(x) = 0$ otherwise.

Then $Pr[b(x) = 0 | n(x) = 0] = 1$; $Pr[b(x) = 0 | n(x) = 1] = \alpha$; $Pr[b(x) = 1 | n(x) = 0] = 0$; $Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$, for some $0 < \alpha < 1$.

I am asking: does an efficient data structure exist, implementing a function $b'$ with some $0 < \beta < 1$, such that $Pr[b'(x) = 0 | n(x) = 0] = \beta$; $Pr[b'(x) = 0 | n(x) = 1] = 0$; $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$; $Pr[b'(x) = 1 | n(x) = 1] = 1$?

Edit: It seems this question has been asked before on StackExchange, as https://stackoverflow.com/questions/635728 and https://cstheory.stackexchange.com/questions/6596 with a range of answers from "can't be done" through "can be done, at some cost" to "it is trivial to do, by reversing the values of $b$".  It is not yet clear to me what the "right" answer is.  What is clear is that an LRU caching scheme of some sort (such as the one suggested by Ilmari Karonen) works rather well, is easy to implement, and resulted in a 50% reduction in the time taken to run my code.


texts: Every AVL tree can be colored to be a red-black tree

texts:
I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately.
Let $h$ be the height of a subtree of an AVL tree.
It is given that such a coloring is constrained by these cases:

$h$ even $\implies$ black height $=$ $\frac{h}{2} + 1$, root node black
$h$ odd $\implies$ black height $=$  $\frac{h+1}{2}$, root node red

After that the root node is colored black.

I'm trying to prove this inductively. Let's start with the base case $h=1$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.
Now suppose the statement is true for some $h \geq 1$. Then for any node $u$ in the AVL tree, the height difference between their children is less than $1$. That is, for an AVL tree of height $h+1$ either both subtrees of the root node have height $h$ or one has height $h-1$.
By the induction hypothesis we know how to color the subtree of height $h$, depending on the parity of $h$. I'm unsure if I should use strong induction instead because it is not given in the hypothesis how to color a subtree of height $h-1$.
If we would know how to color both subtrees, then consider the following cases:

$h+1$ is even

one subtree has height $h$, the other height $h-1$
both subtrees have height $h$

$h+1$ is odd

one subtree has height $h$, the other height $h-1$
both subtrees have height $h$

For case 1.1 we would get
$$
  \begin{align*}
\quad & h+1 &\text{even} \\
\implies \quad & h &\text{odd} \\
\implies \quad & \text{black height} = \frac{h+1}{2} \\
\implies \quad & h-1 &\text{even} \\
\implies \quad & \text{black height} = \frac{(h-1)}{2} + 1 = \frac{h+1}{2}
  \end{align*}
$$
So their black heights differ by $1$. How would I take that into consideration?


texts: Comparing floating-point numbers as integers

texts:
In the article http://floating-point-gui.de/errors/comparison/, a method for comparing floating-point numbers is suggested:

There is an alternative to heaping conceptual complexity onto such an apparently simple task: instead of comparing a and b as real numbers, we can think about them as discrete steps and define the error margin as the maximum number of possible floating-point values between the two values.
This is conceptually very clear and easy and has the advantage of implicitly scaling the relative error margin with the magnitude of the values. Technically, it’s a bit more complex, but not as much as you might think, because IEEE 754 floats are designed to maintain their order when their bit patterns are interpreted as integers.

So instead of some complex variant of abs(b - a) < ε, we interpret a and b as integers and find abs(b - a) < ε(steps(a, b)) where ε is somehow variable with regards to the density of floating-point numbers in the vicinity of a and b. But how exactly?
Also, does this method really alleviate checking for NaNs and Infs? Or are some of these "heaps of conceptual complexity" inevitable if you want a solid, generic method of floating-point comparison?
The following C code produces 1677722:
#include <stdio.h>

int main(int argc, char *argv[])
{
    double x, y, z, a, b;
    int steps;

    sscanf("0.1", "%f", &x);
    sscanf("0.2", "%f", &y);
    sscanf("0.15", "%f", &z);

    a = x + y;
    b = z + z;
    steps = *(int*)&b - *(int*)&a;

    printf("%d\n", steps);
}

Edit: Rephrased so the word "discrete" is not misused. Rewrote "steps(a, b) < ε(a, b)" into "abs(b - a) < ε(steps(a, b))" to indicate that it may still just be floating-point operations, but that ε is chosen variably.


texts: Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters

texts:
I always wondered what the algorithm might be to generate graphs such as those found on Sedgewick's algorithms books (consider the picture on the left):

Could any one point me to the name (or algorithm) that creates such a graph over a 2D region? I am not interested in how to draw it or display it (or in any library).

From all I can see the (x, y) points are probably just randomly generated, but the edges between vertices don't seem to be randomly connecting any two vertices. Maybe the closer two veritces are the bigger the odds of a connection existing between them is?

Thanks


texts: Minimise the maximum degree of a vertex in a connected graph

texts: Given $N$ vertices and $M$ edges, how to create a connected graph so that I can minimize the maximum degree of every vertex. A vertex can have at most degree $N$ (self loop and other $N-1$ edges). Find the maximum degree of vertex in that graph. Consider all possible values of $N$ and $M$.


texts:
Suppose I have these values with weights --
$$
x_1 = 2\\
x_2 = 4\\
x_3 = 5\\
$$
There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\cdot,\cdot)$, lets say the function values are like this --
$$
f(x_1,x_2) = 10\\
f(x_2,x_3) = 12\\
f(x_3,x_1) = 14\\
$$
What I am doing is running $O(n^2)$ loop (trying all combinations) and keeping the best pair, i.e. $\{x_3, x_1\}$

Is there any faster way to do this ? because my dataset can get arbitrarily large (10,000) and instead of 2 elements, I may need to compute the same with k elements ($k < \text{number of data points}$)

Sorting: Unfortunately, sorting is not possible, actually the weights that I am getting is from a function, the function takes $k$ data point (any combination) at a time and returns a value, i.e. $w = f(x_i, x_j, \ldots, x_k)$ so I need to pick the $k$ subset with the best (or you can say highest) $w$ value.

please help.


texts: Strongly connected components of a graph just a disjoint union of cycles

texts:
While reading corman book, i just came across examples to find strongly connected components in a directed graph. But it turns out be disjoint union of cycles. Is this true for all directed graphs?

What about biconnected components? are they also disjoint union of cycles? please correct me if am thinking wrongly


texts: Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

texts:
I have a question about my solution to a problem from Hackerrank.  The problem is, given $R,C,H,W$ with

$1\le R,C\le 100$,
$1\le H\le R$,
$1\le W\le C$,

an $R\times C$-matrix $L$ and an $H\times W$-matrix $S$, to find $i,j$ with $0\le i\le R-H$ and $0\le j\le C-W$ which minimize the sum $$\sum_{0\le k< H,0\le l< W}(L_{i+k,j+l}-S_{k,l})^2$$ (where I use 0-based indexing).

My first attempt, which performed best, was to try out all $i,j$, store the best result so far in a variable, and stop calculating each sum as soon as it exceeds the best result from the previous runs.

Then I thought of something else (which unfortunately didn't perform that well): I want to run all the sums in parallel and advance those first which look most promising for returning a small result.  So I make a list containing $[i,j,c,m,p]$ for all $i,j$, where $c$ stores how many indices I already calculated of the sum, $m$ stores the intermediate value of the sum and $p$ stores the interpolated value of the finished sum (scaled by $HW$), which I set as $m/c$ for $c>0$ and some arbitrary $x$ else.  So in the beginning all elements will look like $[i,j,0,0,x]$.  I will then advance the first element of the list, which means I increment $c$ by one, $m$ by a new square and then recalculate $p$.  Afterwards I move the first element upwards so that the list is always sorted by $p$.  I also keep track of the best finished sum so far together with its $i,j$-indices.  If the new first element is a finished sum ($c=HW$) then I throw it away (and possibly update the best result).  After the list is empty, the indices of the best result get returned.

I guess the resorting process takes too much time for this to perform well.  I also tried using for $p$ a different function $f(m,c)$ which puts more emphasis on $c$ so that less resorting takes place.  If $f(m,c)=1/c$ and $x>1$, this gives roughly the first algorithm I described, with the good performance.

My question: Is this idea any reasonable?  If yes, what values for $f(m,c)$ (and possibly $x$) could yield better performance than $1/c$?


texts: Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

texts: Is there any known polynomial time algorithm to solve a problem which that  problem is in NP. I was told is False but can't think of any counter example now.


texts: Why frame must be longer than generator polynomial?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

  When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, $G(x)$, in advance. Both the high- and low-order bits of the generator must be $1$. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is why to compute the CRC for some frame with $m$ bit corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial?

I tried to search for the reason but couldn't really find the exact answer, so in my opinion, if the generator polynomial is longer than the frame, it will create check bit that is more than data bit which is redundant because CRC is used in error detecting code and error detecting code is used in places where fewer error occur. But is that true?


texts: Where in the Chomsky Hierarchy are Regular Expressions as a language?

texts:
I'm referring to regular expressions as language: \begin{equation*}
 \Sigma = \{ ``a", ``b", ``(", ``)", ``*", ... \}
\end{equation*} and \begin{equation*}
 L = \Sigma^* \text{, which form a legal regular expression}
\end{equation*} I am not referring to their computational power. I did some research, but wasn't able to find anything relevant. Intuitively, I would imagine they're context-free, but am not sure how to attempt a proof.

I am trying to use this as a lemma, so a reference, or recommendation for how to attempt a proof would be extremely helpful.


texts:
Are $O(n+m)$ and $O(n+2m)$ the same?
If $m>n$, then both complexities are $O(m)$. Likewise, if $n>m$, then they are $O(n)$. Is this correct?


texts:
Suppose I have an algorithm that reads lines in a file(linear) and for each line in the file, it sorts each word(nlogn).  This algorithm is mnlogn, where m is the number of lines and n is the number of characters in a word.

Asymptotically, as the file gets longer the number of lines becomes small in comparison to the number of characters, so the running time of this algorithm is O(nlogn)?  How do you determine big O like this where the inputs are different?


texts: General Approach To Calculate Minimum Number Of Flip-Flops Required

texts:
In the previous two years of the GATE exams, a question has been asked for finding number of flip flop's for counting sequence $0−1−0−2−0−3$ in 2016 and $0−0−1−1−2−2−3−3−0−0$ in 2015. But still, the approach discussed in these questions hasn't arrived at Common answer (or) solution.

For $0−1−0−2−0−3$, there are $6$ different states, and thus it acts as a mod−6, counter So, 3 FF's are suffice. In another approach it is said that $2$ bits are used to distinguish three $0$′s and $2$ for $1,2,3$. So number of FF's required =2+2=4

Similar is the case in $0−0−1−1−2−2−3−3−0−0$, one approach says setting clock such that output of FF will be sampled at twice the input frequency makes me think 2 FF's would suffice. But on the other-hand using 2 FF's for $1,2,3,4 $ and 1 FF for identifying which 1 out of two 1′s makes me think $3$ is also right.

So, I want to be sure in answering these type of questions as they have been asked in recent past [GATE][3] Exams.Please tell the general approach to solve these type of questions also please comment about minimum number of JK
FF's required for following counting sequence so that i will be able to work out myself using the technique provided by you and evaluate my understanding.

$0−0−0−1−1−2−2−3−3−...$
$0−1−0−2−0−2−0−3−0−2−...$
$1−2−3−0−0−1−0−2−2−...$


texts: Truth and lie in infomation theory: negative amount of information

texts:
How does information theory deal with truth?

Does disinformation or lie have negative amount of bits of information?


texts: Algorithm for placing circles of Diameter d around the edge of another circle with diameter D

texts: Hi i'm struggling with what i think may be simple maths. I need to place circles of a small size around the edge of larger circle.. is there an algorithm to calculate the angle for each small circle from the x-axis, counter clockwise? then using this angle i can find the Cartesian coordinates (x,y) of the enter of each circle.


texts: Preparing precedence graph from fork and join code

texts:
I was referring to this page which defines fork, join and precedence graph as follows:

  When the statement Fork(label) is executed by a thread of control, a second thread of control is started from the statement with the specified label. The two threads execute concurrently.
  When the statement Join(count) is executed, where count is an integer variable, the value of count is decremented. If the resulting value is positive the executing thread is terminated.
  A PRECEDENCE GRAPH is a directed, acyclic graph where nodes represent sequential activities and where arcs, say from node i to node j, require that activity i complete before activity j can start.

Base upon this I have been asked to draw precedence graph for a code containing fork and join constructs. For simple code, I can do. Also once given both code and precedence graph, I can see how the two correspond to each other. However when the code gets little bit complex, it becomes difficult to prepare precedence graph for me. Also doing reverse, from precedence graph preparing fork-join code is almost always difficult for me.

Can anyone give me intuitive stepwise procedure explaining how to obtain fork-join code from any given precedence graph?

Can we take example of following graph to apply the steps and get the fork and join code:


texts:
I've got this question from a course:

Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.

And it seems like this has been poorly explained and I am getting conflicting answers on how to answer. For explanation purposes I will consider my problem to be f(x) where given a truthy value for x f(x) will output 1 and the opposite for falsey values.
In plain English, a certificate is a variable x such that the verifier for a problem can output 1 or 0.
In the case of f, a certificate would be x=1 or x=0 or similar.
Is this correct?
The problems are made of a few parts:

The problem, given x can we do y.
A certificate, an x.
A verifier, given y is it an actual answer for x.


texts: Rigorous reason against the seemingly wrong way of substitution

texts:
Let us consider the lambda calculus expression .

$ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$

Now $\lambda x.x$ is seen as an argument . How to decide which bound variable should the value of the argument go to ?

The books I am going through suggest that in this kind of case when there is one argument available  the first bound variable should take that arguments value .

To the best of knowledge I don't remember reading anything rigorous till what Ii have covered of these books that would provide rigorous reasoning as to why the first argument should go to the first bind variable .

I understand it makes sense and a meaningful expression when seen as a function demanding two arguments but being provided one as it makes a function again demanding one more argument . This thing is provided in every introduction to functional programming but still somehow I wonder if we can rigorously show that the first bound variable should be taking the value of the first argument .

I have read about beta reduction and I tried applying that to the above expression :

so  $ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$
can be seen as $ (\lambda func.(\lambda arg$ $( func$ $ arg))$ $\lambda x.x)$
and will be in a form $ (\lambda x$$.M) N$ form  so here I can justify the first argument being used for  $func$.

But can I not see it as follow :
$ (\lambda func.((\lambda arg$ $( func$ $ arg))$ $\lambda x.x))$ thereby making it in a form  :

$ \lambda func.($ $( \lambda x .M)N$) thereby allowing the second bound variable to take the value of the argument ?

So how to provide a rigorous reason for the first bind variable taking the first argument ?


texts:
The integer feasibility problem is NP-complete:

$Ax=b, x \geq 0, x \mbox{ integer}$

$A$ contains elements in $\mathbb{R}$

If we restrict this:

$A$ contains only elements in:

$\{1,0\}$
$\{1,0,-1\}$
$\mathbb{N}$
$\mathbb{Z}$

Does this change anything in term of hardness?

Can all these problems be reduced to each other?

(Can it be for example that there is polynominaltime-algorithm for 1. but not for 4.?)


texts:
From Reading 17 of 6.005 — Software Construction:

Exercise Reading a Grammar 4:
Which strings match the root nonterminal of this grammar?
root   ::= (A B)+
A      ::= [Aa]
B      ::= [Bb]

aaaBBB

abababab

aBAbabAB

AbAbAbA

Answer: 2 and 3

So far so good.

Exercise Reading a Grammar 3:
Which strings match the root nonterminal of this grammar?
root    ::= integer ('-' integer)+
integer ::= [0-9]+

617

617-253

617-253-1000

---

integer-integer-integer

5--5

3-6-293-1

Answer: 2, 3, and 7

In the last question, why doesn't integer-integer-integer match the root if it can be our first step, i.e.
root ⇒ integer-integer-integer
Sure, it would not be the end of the story (i.e. it would contain some non-terminals) but neither was aBAbabAB in the question above and yet it was accepted as a string that matched the root.
Many thanks!


texts: I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular

texts:
Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$.
So I applied the pumping lemma to see if it is non regular, and I get:

given a pumping length p I should have a string $z\in L$ such that $\mid z \mid \ge p$
I choose $z=a^pa^pa^pa$ such that $z\in L$ and $\mid z \mid = (3p + 1)\ge p$
now I can slipt the string in 3 parts, $z=uvw$ with $u=a^{p-1}, v=a,w=a^{2p}a$ and it satisfies the two following conditions of the lemma $\mid uv \mid \leq p$ and $\mid v \mid > 0$
then given $z = uv^iw$, if I pump $v$ I see that $z \notin L$ because if for example I choose $i=2$ than $\mid z \mid = (p-1)+i+2p+1=3p+2 \geq 3p+1$

So $z \notin L$ and it means that $L$ is not regular, but I noticed that I can construct a DFA that accepts this language:

So now I'm really confused. Probably I'm applying the pumping lemma in the wrong way but I don't understand where.
UPDATE
Now, thanks to all of you, I think I understood my mistake. So to prove that a language is not regular I have to show that every decomposition fails to satisfy the pumping condition for some pumping number $i$. But in this case there is a decomposition that satisfies the pumping condition so I can't prove that the language is regular (but we know it is regular because we can construct a DFA that accepts it).


texts: Measuring Complexity of Boolean Satisfiability Problem

texts: How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. If the formula can contain duplicate sub-expressions, e.g., $(A \land B) \lor (A \land B)$, then the formula's maximum size is unbounded. In this case, wouldn't the complexity be better measured in terms of how complex the formula is, rather than how many variables it takes?


texts: Denotational semantics of command sequencing

texts:
Moved from cstheory.stackexchange upon request

Winskel, in his book The formal semantics of programming languages, on page 58, writes:

C[c0;c1] = C[c1] o C[c0] a composition of relations, the definition of which explains the order-reversal in c0 and c1

For me C[c0] is the relation of pairs (s,s') where starting from state s executing the command c0 we arrive at state c1

and C[c1] is of pairs (s',s'') so their composition would be {(s,s'') | exists s' so (s,s') in C[c0] and (s',s'') in C[c1]}.

So it would be C[c0] o C[c1], just the opposite as in the book.

Is my thought wrong? Why?


texts: Why CLRS example on residual networks does not follows its formula?

texts:
I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure:

That is:

  A flow in a residual network provides a roadmap for adding flow to the
  original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in
  the corresponding residual network $G_f$, we define $f \uparrow f'$,
  the augmentation of flow $f$ by $f'$, to be a function from $V \times V$ to
  $R$, defined by

  $$(f \uparrow f')(u, v) = \begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> \text{if (u,v) $\in$ E} \\ 0 & \text{otherwise} \end{cases}$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ?
If we follow the formula, it must have a flow 5:
$8 + 5 - 8 = 5$


texts: Prove that all non-recursive languages are infinite

texts:
I am wondering this statement above [the title] is true or not.

Here is what I've already had : non-recursive means undecidable.

I've read this Are all infinite languages undecidable?

which says:

If a Language is undecidable(non-recursive), there must be some strings make the TM fail to halt.SO IT MUST HAVE INFINITE OF THEM WHICH MAKE THE TM FAILS TO HALT.

How could this prove my statement[title]? Can anyone explain it to me a bit more clearly?

Thanks

TM means Turing machine. And too be clear My question is : Does ALL non-recursive languages are Infinite?


texts: how to understand time complexity from a plot?

texts:
This is my first question here. I'm not a CS at all, so it might be quite trivial.

I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear algebra subroutine with. I'm having big troubles in understanding how to identify time complexity for these operations from a plot. Particularly, I'm interested in identify how CPU time scales as a function of n, where n is my size.

To do so, I created an array of n = 2, 4, 8, ..., 512 and I computed the CPU time for both the operations. I repeated this process 10000 times for each n and I took the mean eventually. I therefore come up with a second array that I can match with my array of n.

I've been suggested to print in double logarithmic plot, and I read in Wolfram that, using this way, "powers shows up as a straight line". This is the resulting figure (dgesv is the linear algebra subroutine I used).

Now, I'm guessing that my time complexity is $O(a^n)$ since I get straight lines for both my operations (I do not take into consideration the red line). I saw the shapes differences between, say, linear complexity, logarithmic complexity etc. But I still have doubts if I should say something about the time complexity of dgesv, for instance. I'm sure there's a way that I don't know at all, so I'd be glad if someone could help me in understanding how to look at this plot properly.


texts: What is hiding behind amortized constant delay enumeration?

texts:
The following may contain errors. It is precisely because I am not
sure I understand the topic that I am asking questions. I do not have
books about it and could not find an adequate reference on the web.

I am discussing a problem regarding an enumeration of strings that
should be in amortized constant delay. From what I understood (but
understanding that is part of my question), this means that the average
time taken for each answer should be independent of the size of the
answer, so that the total cost is $O(n)$ where $n$ is the number of
answers.

My discussion partner went on to assert (I believe) that amortized
constant delay is possible for enumerating the strings accepted by a
trie, but not for enumerating the paths of a DAG. And I am at loss to
see a significant difference, since proper use of a stack should let
me explore the DAG as if it had been exploded into a trie (by
duplicating whatever is below a merge vertex).

The only real difference I can see is that the accepting nodes of a
trie can be labeled with a single symbol identifier characterizing the accepted word (turning the trie
into a Moore machine) so that the total cost is only a traversal of
the trie, with single step output of the symbol label when traversing an
accepting node.

Such labeling identification is not possible for a DFA structured as a DAG, since an
accepting node can correspond to different paths. The only way to name
paths is to describe them in extenso (or nearly so: enough to disambiguate merges), so that the cost
of the output by itself is already something like $O(n\times s)$ where
$s$ is the size of the longest path, thus entailing the same time cost
just for doing the output.

Where do I err, and what is the accepted wisdom and knowledge on this topic?
Pointers to web references are useful too.


texts: Is peer to peer and client-server a type of network or protocol? Because my book mentions this under types of network heading under the subsection of "Types of network on the basis of component roles", (with other two subsections, i.e. "Types of network on the basis of geographical spread" and "Types of network on the basis of communication channels"), but in another book it says it says they are protocols.


texts: Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

texts: $\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly unintuitive consequences of that bizarre claim.


texts: Determining an appropriate number of buckets for a hash function

texts:
I would like to select an appropriate number of buckets in my hash table for this scenario:

A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed by the 2-character initials of the customer's name, transformed into integers using the mapping: A=01, B=02,..., Z=26. It is expected that on average no more than 8 comparisons is made every time a search is requested.

How would you select an appropriate number of buckets for a division hash function, and a multiplication hash function, based on this scenario?


texts: How to compute the number of occurrences of a cron schedule over a time span?

texts:
For example, given a cron schedule such as: 0 * 1 7 6 and a time span, like the next year, can you directly compute the number of times the schedule will fire? It can be brute forced pretty trivially but I'd like to use this to sort a list so I'd rather not just brute force it. It's pretty easy to compute the trivial cron patterns:
fn('* * * * *', 1 day) -> 60 * 24
fn('0,30 * * * *', 1 day) -> 2 * 24

It's easy up until the calendar gets involved with different length months and then you have to worry about days or the week coinciding with days of the month.


texts: Example of two undecidable languages that cannot be mapping reduced to each other

texts: I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. One of my thought is to let $A$ be the halting problem, let $B$ be some non-Turing-recognizable language, then it is clear that $B$ cannot reduce to $A$, but I don't know which $B$ can I pick to show that $A$ cannot reduce to $B$


texts: Why there is no Turing Machine that accepts the Diagonal Language?

texts:
Given the diagonal language
$$L_d = \{ i : \sigma_i \notin L(M_i) \}$$
Where $M_i$ are all Turing Machines and $\sigma_i$ are all the words, if you put in in a Matrix like this:
$$\begin{array} {|c|c|c|c|c|c|c|}
\hline
& \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 & ...\\ \hline
M_1 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_2 & 0 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_3 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline
M_4 & \vdots & \vdots & \vdots & 1 & \dotsb & \dotsb \\ \hline
M_5 & \vdots & \vdots & \vdots & \vdots & \ddots & \dotsb \\ \hline
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\\ \hline
\end{array}$$
Then $L_d$ is represented by the numbers in the diagonal of the matrix.
In class I was told that there is no TM that accept $L_d$, but I do not quite understand why is that, could somebody help?
PS: The above explanation was included because I did not know if this is called Diagonal Language in English, Spanish is my mother tongue.


texts: What is softmax in reinforcement learning?

texts:
There are multiple very complicated articles about softmax online. I just want to know a few things about it:

Why do we need softmax? What is the "problem"? What does it do?
How does it do it?

I find it very hard to get through all the math when I don't really get what it is all about. The problem is that all the things I read online is very complicated written and no one seems to just get to the point.
I hope you can help.


texts: Difference between spanning tree and a tree?

texts:
Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem relevant to computer science. My professor in my algorithms class makes the distinction between a spanning tree and a regular tree; but never says what the difference really is. The only thing I notice is that he uses the word spanning tree when he is talking about graphs.

Is a spanning tree simply when a graph takes on a tree structure? In other words, the raw data structure under the hood is a graph, but it takes on some characteristics of a tree? Or is it something else?


texts:
Wikipedia says that weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). However, I can't seem to get the terms yet. There are even these symbols that looks like a T turned counterclockwise.

In simple terms, what are weakening and contraction? Can they even be described without the symbol that looks like a T turned counterclockwise?


texts: Can deep learning be applied to nonlinear parameter estimation problems?

texts:
Suppose $y=f(x,p)$ while $x$ and $y$ are variables and $p$ is the parameter (all in vector form), and $f$ is an explicit nonlinear function. We have:

$$y_1^{(1)} = f(x_1^{(1)},p_1), y_1^{(2)} = f(x_1^{(2)},p_1), ..., y_1^{(n_1)} = f(x_1^{(n_1)},p_1)$$

$$y_2^{(1)} = f(x_2^{(1)},p_2), y_2^{(2)} = f(x_2^{(2)},p_2), ..., y_1^{(n_2)} = f(x_1^{(n_2)},p_2)$$

$$...$$

$$y_i^{(1)} = f(x_i^{(1)},p_i), y_i^{(2)} = f(x_i^{(2)},p_i), ..., y_1^{(n_i)} = f(x_1^{(n_i)},p_i)$$

$$...$$

If given a set of $(x_i^{(1)},y_i^{(1)}), (x_i^{(2)},y_i^{(2)}), ...$, we can estimate the value of $p_i$ by means of optimization such as gradient descent or any other algorithms.

My question is : Can the parameter estimation problem described above, which is conventionally solved by optimization methods, be solved by deep learning?

Since $f$ is an explicit math formula, a very large training set can be easily generated by sampling $x$ and $p$ from some sort of prior distribution.

The difficulties I met during searching the answer on google:

Since DL itself is an optimization problem (or parameter estimation problem), what I found is mainly basic tutorials of DL rather than something directly relevant.
A similar question on Quora: How can I apply machine learning to parameter estimation problem in control theory? Is there any example study you can suggest?. The only answer to this question is very brief and only provides a 132-page thesis. I scanned the thesis and found that it seemed to solve a rather complicated image processing problem by reinforcement learning. I'm not sure if it is relevant.
A similar question on StackOverflow: Can I do nonlinear regression with deep learning ? How?. But the author tried to use deep learning to find the relationship between $x$ and $y$, which is different from my question: the function $f$ is already known, I just want the $p$.

The intuition of solving parameter estimation by deep learning instead of direct optimization could be:

Optimization methods such as gradient descent is prone to find a local optima. Maybe DL will have some magic.
In practice, the parameter estimation problem may need to be solved many times for different set of $(x,y)$, which requires speed. So conventional optimization methods may be too slow for this. In a real case that prompts me to ask this question, each parameter estimation takes 0.6s by the lsqnonlin function of MATLAB. In contrast, although training a neuron network is time-consuming, getting the output from the input only takes several milliseconds for a pre-trained network.
The formula $y=f(x,p)$ may be used in practice for many years and proves to be very effective. The parameter $p$ also has clear physical meanings and can indicate the actual conditions of the system/machine/experiment. Both $x$ and $y$ can be easily obtained. So I want to reserve the formula rather than use a blackbox-like network to predict $y$ from $x$ as most DLs do.

The difficulties I met when solving the problem myself:

Suppose the size of the $(x_i,y_i)$ set is $n_i$: $(x_i^{(1)},y_i^{(1)}), (x_i^{(2)},y_i^{(2)}), ..., (x_i^{(n_i)},y_i^{(n_i)})$. The problem is: $n_i$ is not fixed. If $n_i=5$, we may estimate $p_i$ with a great error. And if $n_i=1e6$, we may get a very precise estimation of $p_i$. But in both case we can get an estimation of $p_i$ at last. However, multi-layer perceptron (MLP) or convolution neuron network (CNN) both accept fixed number of inputs. If you do image processing, you even need to resize every image to the same size first. It seems that MLP and CNN don't suit for this question.
The $(x,y)$ set has no order as time-series. The 1 and 2 in $(x_i^{(1)},y_i^{(1)})$ and $(x_i^{(2)},y_i^{(2}))$ are just indices, which don't imply that $(x_i^{(1)},y_i^{(1)})$ is necessarily before $(x_i^{(2)},y_i^{(2}))$. So recurrent neuron network (RNN) doesn't seem to be a natural option.


texts: Powerlaw graphs : Number of hubs and fraction of edges incident on them

texts:
As per the definition of power law, the fraction P(k) of nodes with k degree for large values of k , given by

P(k) ~k ^-r .

In this definition, the term large value is not clearly defined. Does large implies  100 or 10^3 or 10^6?

Does the definition implies that vertices in power law graphs have almost constant degree with only few exceptions called hub nodes which have very degree may be 100times higher than other vertices?

If the above statement is true, then why do the degree distribution graph for powerlaw graphs do not have only few points with high value of degree and other nodes at the end of disconnected curve compared to close points on decaying curve as in this plot yahoo_web_graph

Is this definition enough to get the number of hub vertices present in the graph or fraction of edges incident on them, given the number of vertices in the graph?


texts: Is "sparse subtree" an appropriate term for what I describe in this question?

texts:
Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original tree. But I'd like to check with y'all because I plan to use the term in writing for an audience that will include CS savvy folk.

If not, I think "tree formed by the annotated subset of the nodes of the tree" will work but am hoping one of y'all will suggest something snappier than that.


texts: Relationship between circuit size and formula size in Sipser text

texts:
The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can be done in polynomial time.

First question: is it correct to say that if a circuit C of polynomial size exists, then there must exist a formula $\varphi$ of polynomial size where C is satisfiable if and only if $\varphi$ is satisfiable?

Second question: is the Boolean formula $\varphi$ still of polynomial size if C is of polynomial size and C is derived from a deterministic Turing machine M? This seems to be described in the proof of the earlier theorem in Sipser where (by building C from a tableau of M) it is shown that if $\mbox{A $\in$ TIME$(t(n))$ for $t(n) \geq n$ and $n \in \mathbb{N}$}$ then A has circuit complexity $O(t^2(n))$.


texts: checking whether a language is turing recognizable

texts:
After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept.

so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}", then it should be a turing recognizable language since there can be a turing machine that halts and accepts strings in it, and for strings not in that language it doesn't halt or just skip them.

however, how can i build such a turing machine(i mean the pseudocode for it)?

i know it's quite a simple question, but i rose it out of curiosity so i could learn and from that to adapt to more complicated problems.

thank you very much for helping me


texts: An algorithm to drop low-priority items from a heap-based priority queue

texts:
I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value.  (Or, equivalently, to drop from a priority queue realised by such a heap all items whose priority is too low.)

It is easy to make an algorithm that walks the heap level by level from bottom up, comparing the item weights to the threshold value and doing dropping-and-swapping.  It will turn out to be extremely inefficient though if, for example, all items in the heap need to be dropped.

It looks better to start by finding an item at the bottom level that is heavier than the threshold value and walk upwards from it until finding the highest element that needs to be dropped.  Then the whole sub-heap under that element needs to be dropped.  The space taken up by this sub-heap can be filled with elements moved from one or two bottom levels that are not in this sub-heap, and the sub-heap can be rebuilt.  However, this method does not look perfect either, as most likely the dropped sub-heap will be filled with elements some of which need to be dropped too.

Are there any efficient or well-studied algorithms for this?


texts: Complexity of brute force primality test in the number of digits

texts:
I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime by checking if there is a number $k$ from $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ that cleanly divides $n$. How would I go about expressing the complexity of this algorithm in the number of digits $n$ has?

My initial thought would be that in the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$. Is my thought process correct?


texts: How to choose the number of HOG pyramid layers?

texts:
Reading Histograms of Oriented Gradients for Human Detection, I cannot see any discussion of how many layers there should be in the HOG pyramid. OpenCV offers a scaling factor of 1.05 which would mean 15 layers between each halving and Object Detection with Discriminatively Trained
Part Based Model suggests 10 layers, but that is for their specific algorithm, I believe.

However, with 1280 x 960 source images these values become prohibitively expensive regarding performance. How does decreasing the number of layers affect detection rates? What exactly am I trading off?


texts:
I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better than IDA).

I am looking for online articles that have done similar experiments, comparing variations of A* with respect to expanded nodes, but have not come across anything concrete.


texts: Doubts about infinite language decided by a turing machine

texts:
Assume you have an infinite language $L$ over alphabet $\Sigma=\{a,b\}$
For example, $L=\{ax \mid x \in \Sigma^*\}$

Can a Turing Machine, $M$ decide this language?

(Generalizing, are all the recursive languages finite?)

In my opinion, it can, since I can enumerate all the strings and say if they are in the language or not. However, enumerating all the strings will take infinite amount of time, so I will never end up enumerating them.

Can someone clarify this doubt?


texts: Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$

texts:
I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input.

The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$.

It seems that $T(n) \leq \log^{\beta}{n}$ for some $\beta$ depends on $a$.
But I can't prove this inequality. How to solve this recurrence relation?

I just want to get an upper bound polylogarithmic in n.


texts: How to find a path in maze with navigator physical size constraints?

texts:
Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it?

Additional specification:

The object shape - it is a single entity, not a swarm/fleet. A shape of something one could cut out of cardboard, no infinite areas, no infinitely asymptotic corners. The shape and size relative to maze is fixed.
The object movement - it can move as a cardboard shape would without leaving its plane. Continuous movement in any direction, no jumps through space. Rotate around any point in plane as one would rotate cardboard shape without lifting it off plane. Can move and rotate simultaneously.
The maze is fixed in size relative to object. The maze does not change as the object moves through it and does not interact with object in any way apart from not allowing any part of object to move through maze walls.
The maze is finite.
The maze is represented as a set of straight lines in 2D space. No curves, as those can be approximated with many straight lines. The data structure is irrelevant, should be translatable to any other data structure. Can assume non-zero maze wall thickness if that is relevant to answer.
The maze can contain loops through which object can pass through. Can contain loops that allow a smaller object to pass but not the one we need.
The maze has one entrance and N>0 exits although I think any algorithm that can find a path to exit should also be able to identify if a path does not exist.
The goal is to find any one path from entrance to exit that the object can move through

P.S.
If there is existing literature on this, please add it in comments or answers as I might have used the wrong keywords and could not find it.


texts: How to pick a random index in an array based on the index's value?

texts:
While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows:

Given an array w of positive integers, where w[i] describes the weight of index i(0-indexed), write a function pickIndex which randomly picks an index in proportion to its weight.

For example, given an input list of values w = [2, 8], when we pick up a number out of it, the chance is that 8 times out of 10 we should pick the number 1 as the answer since it's the second element of the array (w[1] = 8).

My solution is:
from typing import List
import heapq

class Solution:

    def form_cycle(self):
        self.cycle = []
        for element, w in enumerate(self.weights):
            heapq.heappush(self.cycle, (-1*w, element))

    def __init__(self, w: List[int]):
        self.total_weight = 0
        self.weights = w
        for element, weight in enumerate(w):
            self.total_weight += weight
        self.form_cycle()

    def pickIndex(self) -> int:
        if not self.cycle:
            self.form_cycle()
        picked_element = heapq.heappop(self.cycle)
        picked_weight = picked_element[0]*-1
        picked_element = picked_element[1]
        if picked_weight > 1:
            heapq.heappush(self.cycle, (-1*(picked_weight-1), picked_element))
        return picked_element

I form a max-heap, insert values in it. I then pop the largest value, return its index after decreasing that largest value by 1. How is this algorithm not working?
My solution has passed 43.57 test cases.
Currently failing at this as the test case is too long to paste it here.


texts:
I am working on my midterm sample problems and got stuck on this one. Is this language undecidable?

$\qquad  L = \{\langle G_1, G_2 \rangle: G_1, G_2 \text{  are CFG and have strings that can be parsed in both grammars }\}$

Is this one the same as $L' = \{\langle G_1, G_2 \rangle: L(G_1) \cap L(G_2) \ne \emptyset\}$? My professor said the above problem can be reduced to Post Correspondence Problem but I found it closer to the decidable of $L'$.


texts: Amortized time complexity for double stack emulated queue

texts:
Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many elements are in the $stack$, and can be accessed in constant time.

I want to emulate a $queue$ by using two stacks $queue = (stack_{push}, stack_{pop})$ with two operations $insert$ and $remove$

$insert(queue, e)$ is implemented as:

insert(queue, e) {
    push(stack_push, e)
}

$remove(queue)$ is implemented as:

remove(queue) {
    if (stack_pop.size > 0) {
        pop(stack_pop)
    } else {
        while(stack_push.size > 0) {
            push(stack_pop, pop(stack_push))
        }
        pop(stack_pop)
    }
}

It is obviously that $insert$ takes constant time and $remove$ takes $O(n)$ time in worst case. (where n is the size of the queue).

Now considering an sequence of queue operation with length $n$ (pop an empty stack is allowed), I want to get the amortized time complexity of this queue structure. My guess is that the amortized time complexity is $O(1)$, since it seems that the worst case of the sequence is first $insert$ n-1 elements then $remove$, so the total cost is $O(n)$ then the amortized time is $O(n)/n = O(1)$. However I cannot figure out how to prove it.

My question is that is the amortized time complexity of the queue's operation really $O(1)$ and how to prove it?


texts: Show {^i^j^k, != j and  != } is a context-sensitive language, what is the grammar? It is context free or nor?

texts:
I've been pondering this question for a long time, that ^i^j^k, !=j and  !=  is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a language.
In addition, how can we prove it is not context free language?
Thanks so much for your help.


texts: Fast searching time for nearest neighbours

texts:
I am using KD trees to do nearest neighbour searching. My understanding is that it takes $O(n \log n)$ effort to create the tree where $n$ is the number of points and that it takes $O(m \log n)$ to do nearest neighbour searching for $m$ query points.

In my application, $m$ is in the tens of millions and so most of the time is spent searching through the tree. Is there a quicker way? Any other algorithms where the total searching time is smaller?

the dimensionality $d$ is less than 4
the size of $n$ is in the thousands
all the query points are known ahead of time.

I use KD tree because it is simple but I am open to suggestions for other nearest neighbour algorithms where the total time (build time + searching time) is lower.


texts: Whether the given language is a CFL or not?

texts:
Let $L$ be a language defined over $\Sigma = \left \{ a, b \right \}$ such that
$L = \left \{ x\#y \mid x,y \in \Sigma^*, \# \text { is a constant and } x \neq y \right \}$
State whether the language L is a CFL or not? Give valid reasons for the same.

Now, I think that the given language is not a CFL. I have used the pumping lemma test for showing that L is not CFL.
Specifically, I have done the following-

Consider a string $w = abb\#aab$. Obviously, $w \in L$.

Let, $u = \epsilon \\ v = a \\ w = bb\#aa \\ x = b \\ y = \epsilon$

Here, $|vx| \geq 1$

But, $uv^2wx^2y = aabb\#aabb \notin L$
Therefore, pumping lemma test result is negative. Therefore, we can conclude that the given language is not a CFL.

Now, I have a doubt regarding the above method-
 I know that given a CFL, if we want to perform the pumping lemma test for the CFL, we must always use strings which are of length greater than or equal to the minimum pumping length. In fact, this also confirms to the condition that the length of the string $w$ used for the pumping lemma test (denoted by $|w|$) must be greater than or equal to n.

Therefore, when I use $w = abb\#aab$ for doing the pumping lemma test, I implicitly make the assumption that 7 is greater than or equal to the minimum pumping length (if $L$ were to be a CFL). Am I correct or incorrect in doing so?


texts: Is there a name for this traversal-optimized representation of a binary tree data structure?

texts:
I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ traversal upwards and downwards.

It is represented as a pair $(M, P)$, where $M$ is the marked sub-tree and $P$ is a list of parent segments. For example, in the following tree

, the blue subtree is "marked". Groups of nodes joined by solid lines are parent segments, and parent segments are separated by dotted lines.

The marked subtree could be represented as follows (where Terminal represents the absence of such a node in the diagram):

(Tree 17
    (Tree 19 Terminal Terminal)
    (Tree 23 Terminal Terminal))

The parents could be represented as:

[ (Right 13
      (Tree 29 Terminal Terminal))
, (Right 11
      (Tree 31 Terminal
          (Tree 37
              (Tree 41 Terminal Terminal)
              Terminal)))
, (Left 2
      (Tree 3
          (Tree 5
              (Tree 7 Terminal Terminal)
              Terminal)
          Terminal))
]

The marked node's value can be accessed and modified in $O(1)$ because it is at the top of the marked subtree.
Traversal downwards can be done by choosing one subtree and turning the previous node into a Left- or Right-valued tree that stores the other child, which is added to the list of parents.
Traversal upwards can be done by converting the most direct parent from a Left- or Right-valued tree to a full tree by filling in the other side, and then using the result as the new marked subtree.

I used the term AccessTree for this representation of the tree, but I decided the name was unclear.

Has this representation of a tree ever been given a name? If so, what is it?


texts: Finding alternative way of combinatorial counting

texts:
The question is related to databases:

  There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are?

I thought if any one of the $(n-2)$ attribute combinations is chosen then the number of superkeys that can be formed with it will be 4, as there will be $2^2$ combinations of remaining two attributes. So I gave answer $nC_{n-2}\times 2^2$.

But then the answer given was $nC_{n-2} + nC_{n-1}+ nC_{n}$ which is also quite obvious. But then I realized that my solution does not equate to this one and that my solution count certain superkeys more than once.

However I am not able to form an equation of the count of those duplicate superkeys so that I can subtract it from $nC_{n-2}\times 2^2$ in order to get another expression for the solution (somewhat inclusion-exclusion approach). What is that expression/equation which counts those duplicate superkeys?


texts: Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook!

texts:
In Vazrani's textbook, page 22, the following exercise:

  2.1 Given a n undirected graph G=(V,E), the cardinality maximum cut problem asks for a partition of V into sets S and G\S so that the number of edges running between these sets is maximized. Consider the following greedy algorithm for this problem. Here $v_1$ and $v_2$ are arbitrary vertices in G, and for $A \subset V$, $d(v,A)$ denotes the number of edges running between vertex v and set A.

  Show that this is a factor 1/2 approximation algorithm and give a tight example. What is the upper bound on OPT that you are using? Give examples of graphs for which this upper bound is as bad as twice OPT.

First: the upper bound on OPT is easily the number of edges.
Second: I have an example of graph that shows that we have 3/5 (so close to 1/2 but not exactly) I tired for several days to find 1/2 but no sign to find one. Now, can I use the limit to show that we have 1/2. i.e. lim as m goes to infinity, $\frac{m/2 + 1}{m} = \frac{m+2}{2m}=1/2$ Is this correct?!! if not, then why!
Third: I want to understand the different between "Give examples of graphs to show that this upper bound is as bad as twice OPT" and "tight example"! I mean Are they the same thing?!! For example: tight example would show an approximation ratio 1/2 for this algorithm while "Give examples of graphs to show that this upper bound is as bad as twice OPT" would give 1/2 approximation ratio for this algorithm. Also it seems from the context of the question that "upper bound" we use is not good! do you know any other better upper bound than the number of edges to give a better bound!!

I'm here not to ask for solving problem, instead I just want to understand what the question wants exactly and different between some parts of this question.

Thank you!


texts: Method for finding Hyperrectangle that a coordinate is within

texts:
I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to efficiently figure out which hyperrectangle a given coordinate is within.

I do not always have too many hyperrectangles, so just iterating through the set of partitioned hyperrectangles is often fine to see which one a given coordinate is in. However, I sometimes have larger quantities of hyperrectangles and I want to write something that scales better than simply iterating through the set.

My first thought is to consider some hashing approach analogous to spatial hashing but am not sure the best way to go about formulating this since the hyperrectangles could be any dimension. Any thoughts?


texts: Parallelising random reads seems to work well — why?

texts:
Consider the following very simple computer program:

for i = 1 to n:
    y[i] = x[p[i]]

Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-element array of words. Here $n$ is large, e.g., $n = 2^{31}$ (so that only a negligible fraction of the data fits in any kind of cache memory).

Assume that $p$ consists of random numbers, uniformly distributed between $1$ and $n$.

From the perspective of modern hardware, this should mean the following:

reading $p[i]$ is cheap (sequential read)
reading $x[p[i]]$ is very expensive (random reads; almost all reads are cache misses; we will have to fetch each individual byte from the main memory)
writing $y[i]$ is cheap (sequential write).

And this is indeed what I am observing. The program is very slow in comparison with a program that does only sequential reads and writes. Great.

Now comes the question: how well does this program parallelise on modern multi-core platforms?

My hypothesis was that this program does not parallelise well. After all, the bottleneck is the main memory. A single core is already wasting most of its time just waiting for some data from the main memory.

However, this was not what I observed when I started experimenting with some algorithms where the bottleneck was this kind of operation!

I simply replaced the naive for-loop with an OpenMP parallel for-loop (in essence, it will just split the range $[1,n]$ to smaller parts and run these parts on different CPU cores in parallel).

On low-end computers, speedups were indeed minor. But on higher-end platforms I was surprised that I was getting excellent near-linear speedups. Some concrete examples (the exact timings may be a bit off, there is a lot of random variation; these were just quick experiments):

2 x 4-core Xeon (in total 8 cores): factor 5-8 speedups in comparison to single-threaded version.
2 x 6-core Xeon (in total 12 cores): factor 8-14 speedups in comparison to single-threaded version.

Now this was totally unexpected. Questions:

Precisely why does this kind of program parallelise so well? What happens in the hardware? (My current guess is something along these lines: the random reads from different thread are "pipelined" and the average rate of getting answers to these is much higher than in the case of a single thread.)
Is it necessary to use multiple threads and multiple cores to obtain any speedups? If some kind of pipelining indeed takes place in the interface between the main memory and the CPU, couldn't a single-threaded application let the main memory know that it will soon need $x[p[i]]$, $x[p[i+1]]$, ... and the computer could start fetching the relevant cache lines from the main memory? If this is possible in principle, how do I achieve it in practice?
What is the right theoretical model that we could use to analyse this kind of programs (and make correct predictions of the performance)?

Edit: There is now some source code and benchmark results available here: https://github.com/suomela/parallel-random-read

Some examples of ballpark figures ($n = 2^{32}$):

approx. 42 ns per iteration (random read) with a single thread
approx. 5 ns per iteration (random read) with 12 cores.


texts: Why does Fully Utilized Thread Change over time?

texts:
While I was running a simple program which needed to run for a couple minutes, I made an observation I can't find an answer for on google.
Here is a snip of my system monitor which demonstrates my computer switching which processor is at full capacity while running my program.
This isn't causing me any trouble, but I find it interesting, because I would assume that switching between units would take more time than just running at 100% capacity the whole time on one unit.  Is there any simple explanation for this behavior?
Thanks!


texts: Number of different binary search trees storing n distinct keys?

texts:
How many different binary search trees are possible that store the values 1,2,...,n ?

So far I found a recursive formula for the number (by case distinction what's at the root):

$ T(n) = 2T(n-1) + \sum_{i=2}^{n-1}T(i-1)T(n-i), n > 1 $ and $ T(1) = 1 $

But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?


texts: How to prove that ε-loops are not necessary in PDAs?

texts:
In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a proof that uses only automata; therefore, I have to show that heap automata can be simulated by LBAs (or an equivalent model).

I expect the proof to work similarly to showing that pushdown automata accept a subset the context-sensitive languages. However, all proofs I know work by

using grammars -- here the fact is obvious by definition -- or
are unconvinvingly vague (e.g. here).

My problem is that a PDA (resp. HA) can contain cycles of $\varepsilon$-transitions that may write symbols to the stack (resp. heap). An LBA can not simulate arbitrary iterations of such loops. From the Chomsky hierarchy obtained with grammars, we know that

every context-free language has an $\varepsilon$-cycle-free PDA or
the simulating LBA can prevent iterating $\varepsilon$-cycles too often.

Intuitively, this is clear: such cycles write symbols independently of the input, therefore the stack (heap) content does only hold an amount of information linear in the length of the cycle (disregarding overlapping cycles for now). Also, you don't have a way to get rid of the stuff again (if you need to) other than using another $\varepsilon$-cycle. In essence, such cycles do not contribute to dealing with the input if iterated multiple times, so they are not necessary.

How can this argument be put rigorously/formally, especially considering overlapping $\varepsilon$-cycles?


texts:
Given this sort of dataset:

ID
Score1
P1
Flag

id1
0.01
0.2
False

id2
0.99
0.9
True

...
...
...
...

The limitations of each variable are:

ID: identifier if each object, unique in the table
Score1: A number between 0 and 1, that represent the value of the object
P1: probability of call, betwen 0 and 1
Flag: should the object be in group <b?

I want to split the dataset in 2 groups (A and B) given the rules:

The sum of P1 on group A should be at least n
The sum of P1 on group B should be at least m
The diference between the average Score1 in the two groups should be minimal
The average of Score1 on all the selected (group A + group B) should be maximum
We don't have to select all the rows
Rows with Flag = True can not be in group A

How can I do this in a smart/fast way?


texts: What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?

texts:
In our lecture notes on lamdba calculus, I encountered the sentence:

  Let $M$ be a set and $f\colon ℕ → M$ be computable.

Does this even make sense? Don’t we need aditional structure on $ℕ$ and $M$ to talk about computability and decidability? How can I make sense of this statement?


texts: Additional clarification about Simultaneous Multithreading

texts:
I was looking for comments about SMT and got several responses. The last one looks strange:

  Simultaneous multithreading, which can only be implemented on a multicore system, executes the different threads on different cores, or on different processing units on the same core ("superscalarity").

Why can SMT be implemented only on a multicore system? Hyperthreading is normally used to improve performances by filling the most possible the functional units? Not? So, it seems to me that we could have only one core with hyperthreading..

What have I not understood ? Is the term 'processing unit' referred to as 'functional unit'?


texts: Understanding leslie lamport's spacetime diagram with tick lines

texts:
I am trying to understand tick lines in Fig 2 on Page 2 of "Time, Clocks, and the
Ordering of Events in a Distributed System" paper [1]. Below are 2 things which I did not understand

What is the relation between the total no of tick lines and the events on different processes? According to his explanation (i) there must be a tick
line between any two events on a process line and (ii) every message line must cross a tick line. Did he choose the minimum number of tick lines which satisfied the above stated conditions for the events on different processes? Or did he choose an arbitrary number of tick lines Or something else?
Why is the spacing between tick lines un-even in that picture?

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf


texts:
Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{max}$).

The problem is to find a subset $U'$ of $U$ of size $n$ such that for each $v \in V$, the number of edges coming into $v$ from $U'$ is between $v_{min}$ and $v_{max}$.

Given a problem like this, can we determine efficiently whether there is a solution? And, if there is a solution, can we find one efficiently?

If we can't do so efficiently, is there an approximation algorithm?


texts: Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$

texts:
I am trying to either solve or find a tight bound $\Theta$ for the following recurrence relation:

$$T(n) = x + T(n-\log_2 n)\,.$$

For some nonzero constant $x$ (we can suppose it to be 1, for simplicity). Thus far, I have been able to prove the following:

\begin{align*}
T(n) &\in O(n)\\
T(n) &\notin \Omega(n)\\
T(n) &\in \Omega (n^p)\quad \forall p \in (0,1)\,.
\end{align*}

But I am now stuck, I cannot figure how to either solve the recurrence or find a $g(n)$ to prove a tight bound: $T(n) \in \Theta(g(n))$. May somebody know how to solve this?

If you want to know, this recurrence arises in the following context: in maxiphobic heaps[1] where the "weight" of the heap is its number of nodes, the merge operation is recursive, but its complexity is $\Theta(\log n)$, even in the worst case. If the meaning of the weight is changed to mean the height of the heap, the complexity for average random inputs remains $\Theta(\log n)$, but you can construct a worst-case pathological input where in each step merge calls recursively itself with almost all of its input, minus a degenerate subtree of at most $\log_2 n$ elements, approximately. I want to find a tight bound for the complexity of that worst case.

[1] C. Okasaki, 2005. Alternatives to Two Classic Data Structures. In Proceedings of 36th SIGCSE Technical Symposium on Computer Science Education, pp. 162–165. ACM. (ACM Digital Library)


texts: Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

texts:
I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow up with some more details.
In particular, they describe a scheme for iterated matrix multiplication (for the purposes of this post, multiplying $n$, $n \times n$ matrices) in log space, poly "catalytic space", and polynomial time. The argument to the best of my understanding can be sketched as follows.

Theorem 4 (second article) says any arithmetic formula (i.e. arithmetic circuit w/ fanout 1) of depth $d$ can be computed with a program of size $4^d$ (and all the previously mentioned space guarantees). Here, "program" is in the context of register machines, and the size is the number of instructions and equals the runtime.

Brent et al. 1973 proved that any arithmetic formula of size $s$ can be "balanced" to have depth $O(\log s)$, so combining with (1) it has a program of size $poly(s)$

For some reason, I cannot find this last, implied claim in either of the articles: there is a arithmetic formula of size $s = poly(n)$ for iterated matrix multiplication. This would imply the claim made by the papers -- that IMM can be done in polynomial time with the other space bounds, but for some reason I can't find the claim explicitly written out, which suggests I am missing something.

The smallest formula I can think of for iterated matrix multiplication is "divide and conquer" on the number of matrices, and results in size $n^{O(\log n)}$, and I don't see any way to improve on this.
The first linked article says "iterated matrix product can be computed transparently
by polynomial size programs", which would seem to follow by putting together 1,2, and 3, but it references an old thesis I can't find anywhere.
So, it's either the case that I've totally misread the argument, or there should exist a polynomial sized arithmetic formula for iterated matrix multiplication. Does anyone know of one?


texts: Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

texts: I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the proof using Myhill-Nerode and figuring out other methods to use generally.


texts: Cyclic coordinate method: how does it differ from Hook & Jeeves and Rosenbrock?

texts:
I have trouble understanding the cyclic coordinate method. How does it differ with the Hook and Jeeves method and the Rosenbrock method?

From a past exam text:

  Describe the cyclic coordinate method and outline the similarities and the
  differences between the Cyclic Coordinate method, the Hooke and Jeeves
  method, and the Rosenbrock method.

I would appreciate a good reference, I'm having trouble finding any.


texts: What is the difference between a function and a procedure

texts: In general, what is the difference between a function and a procedure when talking about programming languages?


texts: Proving that a language cannot be generated by linear grammar

texts:
We were said at school that the language $L$ over an alphabet $\sum = \{a,b\}$ where the number of $a$'s is twice the number of $b$'s, formally $L = \{ w \in \{a,b\}^* \mid |w|_a = 2|w|_b  \}$ cannot be generated by linear grammar.
I was wondering, is there a way to prove it, to make it clear why is that so?
I was thinking about applying the pumping lemma might work, but I wasn't succesful proving it.


texts: Solving multiple pathfinding problems efficiently

texts:
Let $V$ be a set of nodes, $c : V \times V \rightarrow \mathbb{R} \cup \{\infty\}$ be an edge cost function, and $h : V \times V \rightarrow \mathbb{R}$ be an admissible heuristic. Suppose we want to solve multiple independent least-cost path problems: from $a_1$ to $b_1$, from $a_2$ to $b_2$, and so on.
One approach is to run an all-pairs algorithm like the $\Theta(|V|^3)$ Floyd–Warshall algorithm or $O(|V|^2 \log |V| + |V| |E|)$ Johnson's algorithm, and then apply the results to each problem.
Another approach is to run separate algorithms like A* on each individual problem.
My question is: Can we do better than these? For example, is there a way we can reuse A* computations from prior problems to speed up the next problem? Perhaps we can exploit the Bellman optimality property of the recovered paths, or take advantage of other values that were computed by the preceding A* algorithm runs?


texts: Cellular Automata: Is there a decentral solution for the Firing Squad Synchronization Problem (FSSP)?

texts:
is there a decentral solution for the FSSP, that is, where it is arbitrary which of all the automata is the first general?
Thanks
von Spotz


texts: Using Clique decision to solve Clique optimization

texts:
How can you perform the clique decision algorithm fewer than $ O(n) $ times to solve clique optimization?

I'm not sure if my approach is right but this is my thought process: you would pick vertices in a graph and see if they form a clique, then keep picking more vertices until you have the max possible clique.

I'm not sure how it can be done less than $ O(n) $ times.

I can imagine an undirected graph such as:

where $ \{A, B, C\} $ and $ \{B, C, D\} $ would be cliques. The number of vertices is 4, and the number of vertices in the cliques is 3, which is $ n - 1 $. Would this count as being done in less than $ O(n) $ times, or is this the wrong approach to this problem?


texts: Prove the following problem is NL-complete

texts:
Suppose
$$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\;
\begin{array}{l}
  \text{\(G\) undirected}, \\
  \text{\(s\) and \(t\) are nodes in \(G\)}, \\
  \text{there is a path of length \(d\) from \(s\) to \(t\) and no path of shorter length}
\end{array}\right\}$$
I can easily see that this language is in NL, but I am having trouble proving that this is NL-complete.


texts: Deterministic algorithm to find number of collisions

texts:
Let $h:U \to[m]=\{0,1,\dots,m\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$

Let $D \subseteq U$ be a subset of size $n.$

I'm looking for a deterministic algorithm, efficient as possible, to find the number of collisions of $h$ on $D$

I thought to start operating $h$ on all elements in $D,$ place the results in an array and work with that, but not sure how to continue.

Any help is appreciated.


texts:
In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.

But this seems to be a fundamentally contradictory concept. Because a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

And yet he presented a slide such as this one, where final states are represented by two circles... How is it possible for B, D, E, and H to be final states when they're so clearly not?


texts: Memory address of variable after reassignment

texts: When a local variable is reassigned a different value/object, does its position/address change in the stack?


texts: Resources for connections between dependent type theory and LCCC

texts: Can someone recommend introductory articles/papers on the connections between dependent type theory and locally cartesian closed category? Many Thanks!


texts:
I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$
Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I tend to say that $f(n,m)$ is in $O(2^k)$.
Can anyone help me?


texts: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

texts: If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same weight as $e$ (including $e$ itself) is the same as the number of edges in $E_2$ with the same weight as $e$? If the statement is true, then how can we prove it?


texts: Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

texts:
For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the language is not regular. However, I am unsure how to formally prove this if that is indeed the case. I tried applying the pumping lemma but I am not completely sure how to apply it to this particular language.
Any help is appreciated!


texts: I'm searching for good resources on different graph labelling, especially Graceful, Antimagic and Antibandwidth Labelling. Could anyone please help me with that? It will be very much appreciated. Thanks in advance.


texts: Represent unsigned 12-bit octal numbers. Results in octal

texts:
I have an HW question where I found an answer that matches mine, but their breakdown confuses me.
Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should be written in octal.
I used binary and then looked up the Octal to obtain 753
Found solution: 4365-3412 = 0753
This is because 5-2 = 3 (makes sense), 6-1 = 5 (yep), 8+3-4=7 #we need a carry here, since 3<4 and 4-4=0
I can see where they got 8 (I think) 3+5=8, but why did they do that and how are we getting a carry for the ending of 4-4=0. Appreciate any help/reference.


texts:
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, including the two sets in question and some other ones too. I won't know anything about individual element membership, so need to operate at the set level, and would like to be able to determine whether $a \subseteq b$ is implied by the given constraints.

This sounds like the sort of thing that's been studied before (e.g., for SMT solvers or linear programming), but I can't seem to hit the right keywords to search on. Are there known efficient representations/algorithms for this sort of problem?

Here's what I've roughly thought of doing:

type Set = Symbol;
type Bound = {kind: 'upper' | 'lower', arg: Set};
type Constraint = {kind: 'lt' | 'gt', arg: Bound};

const max = (b1: Bound, b2: Bound): Bound => ...;
const min = (b1: Bound, b2: Bound): Bound => ...;
const checker = (a: Constraint, b: Constraint): bool => ...;

My idea would be to build two Constraints, one for $a$ and one for $b$. $a$ would have a lt constraint and $b$ would have a gt constraint. I suspect Bound forms an algebra with max and min, which would allow me to put two Bounds in quasi-canonical form and break things down that way.

I'm not certain this will work, so before I spend several hours fleshing this out figured I'd ask if this had been solved before!


texts: Are there any known AM-complete problems/is AM-complete well defined?

texts:
I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not a complete one.

I suppose I'm also wondering if a "complete" problem is well-defined for AM. Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes. So maybe since Karp reductions have no error, "Karp reducing to an AM problem" doesn't really have any meaning, thus invalidating the usual notion we use of a "complete" problem?


texts:
I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia)

I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding.

This is what I'm trying to 'digest':

Tabu Search is an improvement over the Hill Climbing algorithm (Ref-1).
The problem with Hill Climbing is that it does not guarantee about reaching the global optimum, because it only searches on a subset of the whole solution space. It will find the local optimum.
To get rid of this issue, Tabu Search maintains a 'Tabu List' of previously visited states that cannot be revisited (Ref-2).
If the tabu list is too large, the oldest candidate solution is removed and it’s no
longer tabu to reconsider (Ref-3).

My questions are,

How does Tabu Search cure the problem of getting stuck in a local
optimum? Does it increase the search-space?
What is the need of maintaining a list (i.e. Tabu List)? Why not
just remember the optimum solution found so far?
When the Tabu List is too large, the oldest candidate will be
removed. What if this oldest candidate is the global optimum?

If anyone could explain Tabu Search algorithm using an example, I'm sure these questions would be automatically answered.

References:

(Ref-1) Hill Climbing, Wikipedia Article (link)
(Ref-2) Russell, Stuart Jonathan, et al. Artificial intelligence: a modern approach. Vol. 74. Englewood Cliffs: Prentice hall, 1995. (WorldCat)
(Ref-3) Luke, Sean. "Essentials of Metaheuristics.". (pdf)


texts:
Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness?

Particularly looking for a proof that does not involve linear programming (if it exists).


texts:
Consider the following grammar:
S → bAb
  | bBa
A → aS
  | CB
B → b
  | Bc
C → c
  | cC

I have to provide the reasons as to why this grammar is not LL(1). So far all I can think of is that the grammar is not left factored given the productions:
S → bAb
  | bBa

But I am also wondering if the grammar is left recursive due to the productions:
B → b
  | Bc

Options provided are:

This grammar has left recursion. (Unsure)
This grammar has right recursion. (Would not make grammar not LL(1))
This grammar is ambiguous. (Unsure)
This grammar is not left factored. (Correct)
This grammar can produce infinitely many distinct strings. (This shouldn't affect a grammar right?)

As far as I can tell, the grammar is not ambiguous, I have tried 3 different inputs and all have resulted in a single parse tree.
So is this grammar not LL(1) just because of the lack of left factoring? or also because the grammar is left recursive?


texts: Searching through all program of a stack-based language with little memory

texts:
I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.

Given a program fragment, I can determine if it is terminated, and, if not, how many operands it requires.  Currently, my search strategy is:

 If program is terminated --> test it
 else --> add all programs with one additional operand to the queue

However, the queue ends up using too much space.  Instead, I'd rather keep the queue small, and find a way to produce all valid programs efficiently (more efficiently than just trying all program text).  What is a good strategy to generate all valid programs for a simple stack language?

UPDATE The language is guaranteed to halt (and is of course not Turing complete).

UPDATE: The approach I am working on is as follows:

Observe that, for certain program fragments, nothing that can be appended to them will make them valid
Define an ordering over each token that may appear in a program.
Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
For n = 0 to infinity:
Start with a program of n tokens; set each token to the first
Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
Etc. until the last token
Increment the last token until the program is valid; test that program
On to the next one


texts: Stereo-Camera: How do Bundle Adjustment and projective ambiguity fit together?

texts:
In the book Multiple View Geometry in Computer Vision Hartley and Zisserman write that given a stereo image pair, the viewed scene can only be reconstructed under projective ambiguity, i.e. is a projective transformation away from the true scene, no matter how many corresponding landmark matches are given.

When using Bundle Adjustment to find extrinsic + intrinsic camera parameters and the 3D coordinates of the scene, how can I be sure that the given values are meaningful? I know Bundle Adjustment is used for e.g. autocalibration, but the computed combination of parameters and coordinates could be wrong and just result in the same image. How is this solved in real applications?


texts: Error-correction code for transmission only with bit-flipping from 0 to 1

texts:
I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system.

For each bit [0,31], I add its index to the Bloom filter if the corresponding bit is set. The Bloom filter is then transmitted without error and the recipient tests the Bloom filter for each index [0,31] to reconstruct the 32 bits of data.

One problem is that the Bloom filter can have false positives, making it look like some bits are set when they shouldn't be. Another problem is that the Bloom filter may already have other entries in it, further making it look like more bits are set.

I wondered if error-correction codes could help here. The general idea would be to add more bits ([32,35] for example) the recipient could use to figure out the original 32 bits despite Bloom filter collisions.

After a little research I learned that Z-channels (or binary asymmetric channels) flip bits in one direction. Also I found that linear error-correction codes for Z-channels are often applicable to symmetric channels as well. So to exploit the asymmetry, the codes likely need to be non-linear. More info on the state of the art is appreciated (hoping for a simple algorithm...).


texts: Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

texts:
The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

to

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considering only $n=2^k$. We assure ourselved that this step is valid -- that is, $T \in \Theta(T')$ -- because $T$ behaves "nicely". In general, we assume $n=b^k$ for $b$ the common denominator.

It is easy to construct recurrences which do not allow this simplification by using vicious $f$. For example, above recurrence for $T\,$/$\,T'$ with

$\qquad f(n) = \begin{cases}
                 1 &, n=2^k \\
                 n &, \text{else}
               \end{cases}$

will yield $\Theta(n)$ by using the Master theorem in the usual way, but there is clearly a subsequence that grows like $\Theta(n \log n)$. See here for another, more contrived example.

How can we make this "nicely" rigorous? I am quite certain that monotonicity is sufficient, but not even the simple Mergesort recurrence is monotone; there is a periodic component (which is dominated asymptotically). Is it enough to investigate $f$, and what are necessary and sufficient conditions on $f$ that ensure the Master theorem works?


texts: How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

texts:
I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, t but the path should also contain two given arcs in a sequence. Say we are given arcs a1, a2, we want to find a simple shortest path that goes from s to tail of a1 and from head of a1 to tail of a2 and then from head of a2 to the sink t. I was wondering if there is any elegant algorithm or even a mixed integer programming approach to solve this problem.

I am currently planning to modify Dijkstras algorithm to forbid certain nodes that have been previously added to the path.

Edit: I want the whole path from $s$ to $t$ to be simple.


texts: Can an NFA have multiple accepting states?

texts: I am currently preparing for exam. While studying Finite Automata, i got confused. I know a DFA can have multiple accepting states, but can an NFA also have multiple accepting states?


texts: Is detecting "doubly" arithmetic progressions 3SUM-hard?

texts:
This is inspired by an interview question.

We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that

$a_k - a_j = a_j - a_i$
$k - j = j - i$

i.e, the sequences $\{a_i, a_j, a_k\}$ and $\{i,j,k\}$ are both in arithmetic progression.

There is an easy $O(n^2)$ algorithm for this, but finding a sub-quadratic algorithm seems elusive.

Is this a known problem? Can we prove 3SUM-hardness of this? (or maybe provide a sub-quadratic algorithm?)

If you like, you can assume $0 \lt a_1 \lt a_2 \lt ... \lt a_n$ and that $a_{r+1} - a_{r} \le K$ for some known constant $K > 2$. (In the interview problem, $K = 9$).


texts:
I am working on a homework assignment to create a function and it says to use a "pure recursive approach". I am trying to piece together what is actually meant by this. I am aware a recursive function calls it self, usually by reducing until it hits a base case and a pure function is basically a function that does not change the variable values.

I assume all that is meant by "pure recursive approach" is to use recursion that does not change the original values of the parameters out side of the function. Is there something I'm missing?


texts: Fermat's last theorem: How to (partially) solve by programs

texts:
No three distinct positive integers $a, b, c$ can satisfy the equation
  : $a^n + b^n=c^n$, if $n$ is an integer greater than two.

The above statement, known as the Fermat's last theorem is proven with rigorous mathematics. I happened to stumble on one particular statement:

  Proofs were eventually found for all values of $n$ up to around $4$
  million, first by hand, and later by computer.

What I understand is, somehow a computer program assured the theorem was correct upto some value of $n$.

Let us simplify and only stick to $n=3$ (the smallest possible value of $n$). Now my question is, how do I write a program that can ensure that there is no integer solution for $a,b,c$? A complete program is not required, rather some discussion (preferably in pseudocode format) would be appreciated.


texts:
Let $M_{1}$ and $M_{2}$ be two (non-deterministic) turing machines accepting the language $L \subseteq \Sigma^{\ast}$.

Is is right to claim that:

$\#M_{1} \in \textbf{#C}$ if and only if $\#M_{2} \in \textbf{#C}$ ?

where $\textbf{#C}$ is a counting complexity class, that is closed under reductions (such as $\textbf{#P}$, $\textbf{#P-Hard}$, $\textbf{GapP}$, $\textbf{GapP-Hard}$, $\textbf{PP}$, etc).

If so, can we use the notation "$\#L \in \textbf{#C}$" ?


texts:
What is the output distribution of a GI/M/1 (general input process and exponential service times) queue.

The GI/M/1 is according to Kendall's notation: arrivals are independent but we do not know the distribution of intervals, service time follows an exponential distribution, and there is only one server.

For the M/M/1 queue (exponential inter-arrival times input process), it is easy since the output process is exponential inter-departures. But, for a general input process, I don't know how to calculate the output process, i.e. the distribution of the time intervals between outputs.