texts:
So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form.
$$
\forall x\in\{0,1\}^n, b\in\{0,1\}: |x,b\rangle\mapsto|x,f(x)\oplus b\rangle
$$

Because such oracle should linearly extend to superposition inputs, we must detangle the output bit with internal (intermediate) qubits. Then one way is to "un-compute"  the entire program, namely for BQP circuit $\tilde{f}$ computing $f$.
First compute $\tilde{f}$, then apply a CNOT on the answer bit, finally uncompute everything except the CNOT-source bit.

So my problem is, in the previous paragraph, he just simulate the measurement gate by a unitary gate. When we perform the un-computing step, we also uncompute that "fake measurement gate". However, it seems not even make sense to un-measure a state. How should I argue that these techniques would work and eventually take us to $BQP^{BQP}=BQP$ result?


texts: Difficulty understanding the solution of heap problem in CLRS book?

texts:
I am reading the solution of this problem in CLRS:

Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.
Solution: All the nodes of height $h$ partition the set of leaves into sets of size between $2^{h-1}$ and $2^h$, where all but one is size $2^h$. Just by putting all the children of each in their own part of the partition. Recal from 6.1-2 that the heap has height $\lfloor\lg(n)\rfloor$, so, by looking at the one element of this height (the root), we get that there are at most $2^{\lfloor\lg(n)\rfloor}$ leaves. Since each of the vertices of height $h$ partitions this into parts of size at least $2^{h-1}+1$, and all but one corresponds to a part of size $2^h$, we can let $k$ denote the quantity we wish to bound,  so,
$$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$$
so
$$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$$

But I don't understand how to come up with the fact that $(k-1)2^h + k(2^{h-1} + 1)$ is less than the number of leaves.


texts: Explaining SAT to high school science teachers

texts:
I am a high school sophomore who is interested in computer science. I developed a cool algorithm for #SAT, and I'm implementing and doing a science fair project on it. My adviser, who is the best science teacher at my school and is also the AP Comp Sci teacher, told me that she has absolutely no idea what my project is about, and that I need to be able to briefly explain her why #SAT is important in under 5 minutes. I told her SAT reduces to #SAT and tried to explain why SAT is important: I gave her some examples of NP problems, explained her how problems in NP reduce to SAT, and explained how with binary search you can reduce certain optimization problems to SAT, which allows you to fold proteins and make powerful AI models. Unfortunately, she didn't understand me at all. Could you give me a few pointers?

P.S. My adviser asked me what useful problems reduce to #SAT that don't reduce to SAT (assuming some problems in #P are harder than their corresponding NP versions). All I could come up with was finding how many models for a given data set are better than a given model (assuming each parameter of the model is smaller than a given number of bits). I looked for other ones on the web but I couldn't find anything I could understand. Are there any other good applications?


texts: Does $O(1) * o(1)$ equal a $o(1)$ function?

texts:
Say I have two functions $f(x) = O(1)$ and $g(x) = o(1)$. Let $h(x) = f(x)g(x)$. Is $h(x) = o(1)$?

By definition of small-o $g(x)$ must approach 0 as $x \rightarrow \infty$, so I think yes. However, how can I formally prove it? Is my intuition correct?


texts: Identify the function call statement in the following snippet

texts: I know that the main(sys.argv[1:]) is the function call statement but I have no idea about the other two variables and why it's used. Can anyone explain?


texts: Practice of setting parallelism as the default behaviour

texts:
This is a soft, and probably also an opinion based question.
Suppose I am writing a library in C++ for the purposes of working with financial data. My goals are:

Since I work with big data, I want to make it as fast as possible by using parallel computing principle inside the functions.
I want my colleagues to use this library without understanding/tweaking the parallelism underneath the functions.

The resulting questions are:

Is this a good idea to make parallelism the default behaviour? For instance sum(vector) to parallelise the summation without asking the user.
If yes, is there any rule of thumb that would cover the default behaviour of the task split between the processors? I.e. how many processors I should use?

Thanks in advance.


texts: Why is the graph inside Graham Scan always planar

texts:
One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's formula the number of edges can never be more than $3*n$ (where $n$ is the number of vertices). My question is, how do we know that the edges examined by Graham Scan never intersect (hence always form a planar graph)?
Here is the screenshot of this being discussed in the course "Computational Geometry" from Tsinghua University (from EdX.org). The lecturer just mentioned it being true, but did not give the proof.


texts: Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$

texts:
I have a sum:
$$S = \sum_{i=1}^n{\lfloor a/i \rfloor i^2},$$
where $a$ is a constant.
Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in logarithmic or better time, something manageable when $a$ is big, n = a/2? I tried lots with pen and paper, but I cannot see how to do this faster than $O(a)$ time.


texts: Circuit depth of computing the continued fractions of a rational number

texts:
If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input?

I was reading through some notes which mentioned that the work being done while computing the continued fraction is basically the same as the work being done while computing a GCD. Are their circuit depths similar?


texts: An opposite method of padding argument on N/DTIME complexity class

texts:
Is there a method to prove things with longer input in complexity theory?
For example, using padding argument it's trivial to show that
$\text{NTIME}(n^2) \subseteq \text{DTIME}(n^4) \Rightarrow \forall k \ge 2, \text{NTIME}(n^k) \subseteq \text{DTIME}(n^{2k})$
Is there a common method for the opposite direction, i.e., for something like
$\text{NTIME}(n^4) \subseteq \text{DTIME}(n^{12}) \Rightarrow \forall 1 \ge k < 4, \text{NTIME}(n^k) \Rightarrow \text{DTIME}(n^{3k})$?


texts: Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

texts:
I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].

Why Isn't this construction considered a counterexample to P = NP? And if it is not, can it be strengthened into one? It seems tome that we have constructed a languge recognizable in NP time but not in P time.
In the proof there is the sentence "If P_i^B(i) accepts 0^n, then place no string into B at this stage." How can this possibly happen?

I figured that, since B is intially empty, the oracle B(i) ALWAYS rejects. So the only reason why P_i would accept is some reason OTHER than a  question to B(i). Please correct me if I am wrong.

The proof in question is verbatim reproduced here. The original paper is here.


texts: Complexity of the Kitten Adoption problem

texts:
This came up while I was trying to answer this question on  Wiring Length Minimization.  I was going to call this the "polygamous marriage" problem, but the internet, so kittens.  Yay!

Suppose we have $M$ kittens that need to be adopted by $N$ people, $M > N$.  For each kitten, $i$ and each person $j$ there is a cost $c_{ij}$.  We would like to minimize the total cost of getting all the kittens adopted.  There is also a set of constraints: each person $j$ is able to adopt no more than $u_j$ kittens.

Without the constraints the problem is easy; each kitten $i$ goes with the person $j$ for which $c_{ij}$ is minimal.  With the constraints is there an efficient algorithm for this problem or is it NP-hard?


texts: Independent Set Problem Variant, Induction

texts:
So the question gives us some mysterious algorithm, that given a graph G and an integer k, it outputs true/false to whether there is an independent set of size k in G.

So we have to design an algorithm that can call this mysterious algorithm within a polynomial number of times, to return an independent set of size k from G if it exists, or outputs impossible. The hint is induction.

I'm having trouble figuring an algorithm to solve this. I know however, that the proof for this algorithm involves removing or adding a vertex in the inductive step.


texts: Is the number of tests needed to know if a program computes the identity computable?

texts:
Given a $\lambda$-term $t\in \Lambda$ and an integer $k$, we say that $t$ behave likes the identity when applied to $k$ if $tk\to_\beta^*k$ (where the integer is represented as a church numeral). We will write $BI(t,k)$ for this property.

Given a term $t$, we define $a(t)$ as the smallest natural number that allows to distinguish $t$ from the identity. More formally, it is the element of $\mathbb N\cup \{+\infty\}$ such that for all $k< a(t), BI(t,k)$ and $\lnot BI(t,a(t))$. For example, $a(\lambda x. 0)=1$ and $a(\lambda x.x)=+\infty$. More generally terms $t$ such that $a(t)=+\infty$ are exactly those that behave like the identity for all integers: $a(t)=+\infty \iff \forall k, B(t,k)$.

Define the size $|t|$ of a term $t$ as the number of nodes in the corresponding abstract syntax tree.

Define $f(n):=\max\{a(t)\mid t\in \Lambda \land |t|\le n \land a(t)<+\infty\}$. It's the upper bound on the number of tests (assuming that we test by comparing $t0$ with $0$, then $t1$ with $1$ etc.) that it can take to distinguish a term of size at most $n$ from the identity. Given a term $t$, we have $a(t)\ge f(|t|)\iff a(t)=+\infty$, i.e. if it could not be distinguished from the identity by the first $f(|t|)$ tests, then it can not be distinguished from the identity by any of the tests.

Is $f$ bounded by a computable function? (And if yes, is it computable?)

Remark: The first thing I thought of is that it would imply decidability of the set of terms that behave like the identity $S_{BI}=\{t\mid a(t)=+\infty\}$, which can't be true by Rice's theorem. But the obvious argument doesn't work: given $t$, to know if $t\in S_{BI}$ even though I only need to test if $BI(t,k)$ for each $k\le f(|t|)$, I still can't do it because testing if $BI(t,k)$ (i.e. $tk\to_\beta^* k$) is undecidable (because $t$ could diverge).


texts: Prove that A* is the smallest reflexive and transitive set containing A

texts:
I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question:

We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$

  Show that A* is a reflexive and transitive set containing A and if B is any other reflexive and transitive set containing A, then $A^*\subseteq B$.

I've shown that Kleene star satisfies these two conditions. I've tried partitioning B into two sets with $A = B \cup C $ and trying a constructive proof but this hasn't led any where. I also am considering a proof by contradition but don't know where to start.

Can you help me with a hint on how to approach this problem?


texts: Why are struct and class essentially the same in C++?

texts:
struct and class in C++ are nearly identical (as covered for example here).

But why is this so? What did happen when C++ was developed and eventually standardized, that struct was allowed to define a full OOP class, yet class keyword was also added? There must be a historical reason for this, but I did not find an answer by searching.

In contrast, for example C# uses these keywords too, but there they have different and distinct meaning. I would say this is quite a valuable feature in that language.

In hindsight, it would have for example made sense to keep C++ struct be always compatible with similar C struct in memory layout, and only those class features that are compatible with that would have been supported (so no "virtual" stuff, value always copyable by memcpy, maybe even some kind of C interoperability for struct methods). Or something else perhaps; point is, the distinction could have meant something and added to the language, instead of being a (small) source of confusion it is now.

So I am looking for some historical record, quote or story, which would explain this.


texts: Deciding if a finite automata accepts strings of any length

texts:
Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not.

What I doing was, I have algorithm to count the number of all strings of some fixed length $n$. Now let there are $k$ states. Suppose we got a positive result (i.e the number of strings is $> 0$) for all $n$ up to $k$. Then check $k+1$: if it gives a positive result then we can say, at least one state is visited twice by that path of length $k+1$. That means we'll get $x$ such that all of $k+1+nx$ for all $n\geq 0$ will get accepted if $x=1$ then done. If not then check again $k+2$ again we'll get a $y$ like that. So for all $n>k$ we're getting APs of lengths which are acceptable but then can we say after some finite state we can say all numbers are accepted ?


texts:
I am trying to understand bits, operations and masking. I have a hard time to get this thing into my head. I have tried to read at many different websites without luck.

I have 8 states, going from 1 to 8:

state 1 = 0001
state 2 = 0010
state 3 = 0011
state 4 = 0100
state 5 = 0101
state 6 = 0110
state 7 = 0111
state 8 = 1000

Now I want to get state 1, 3, 6 and 8. I am unsure how to set this state in the bits. Either I can do this:

state 1 = 0001
state 3 = 0011
state 6 = 0110
state 8 = 1000

Which would turn out like this:

combinedStates = 1111

The problem is, if I send in this, state 5 will get triggered as well as:

state 1 = 0001
state 3 = 0011
state 5 = 0101
state 6 = 0110
state 8 = 1000

Because both state 5 and 6 has a 1 in the same place. The second thing would be to add all the state numbers together (1, 3, 6 and 8, which is 18):

combinedStates = 0001 0010 (18)

But then looking at state 6 would not work as:

state 6 = 0110
combinedStates = 0001 0010

There will be a missing 1.

How would I proceed if I want to get states 1, 3, 6 and 8: combine their bits, or add them all together and use that one's bit value? Any other approach? Any operand I should use?


texts: Given a number, getting a grid position in a spiral pattern


texts: What is the best complexity of finding a minimum in a matrix?

texts:
Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value?

Here is a pseudo code:

function find_min(a)
    imin, jmin = 1, 1
    for k = 1 to K
        for n = 1 to N
            if a[k, n] < a[imin, jmin]
                imin = k
                jmin = n
    return imin, jmin

The above function needs $O(K\cdot N)$ operations. However, I think we can reduce the complexity to $O(\lg K\cdot N)$ using a heap. Am I right? Can we do better than a heap? If so, what is the best complexity of such a function?


texts: Choose the kth choice of choosing n things out of m

texts:
Say I have a list, L, of m things.

I want to pick n things out of the total of m things in the list.

Suppose there are W ways of doing this. I want to choose the kth way where k is in the range 1..W.

i.e. my function is this:

ChooseKthChoiceOf(L,n,k){
   ....
}

Any good algorithms for this?


texts:
DEFINITION: $f = O(g)$ if positive integers c and $n_0$ exist such that for every integer $n$ $\geq$ $n_0$, $f(n) ≤ c·g(n)$

so:

$n^2 \leq c·log(n)$

$\frac{n^2}{log(n)} \leq c$

is this enough proof? since the fraction will grow larger and larger depending on n>1, so its false?


texts: n*log n and n/log n against polynomial running time

texts:
I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\log n)$ with $\Theta(n^f)$ where $0 < f < 1$.

For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$

I would like to have some directions towards proceeding in such cases. Thank you.


texts: There is an $n^k$ prover if and only if $P = NP$

texts:
I am studying computational complexity using Papadimitrious's book: "Computational Complexity".
I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some hint on how to proceed.
Problem 8.4.9:

"Let $f(n)$ be a function from integers to integers. An $f(n)$-prover is an algorithm which, given any valid expression in first-order logic that has a proof in the axiomatic system in Figure 5.4 of length $l$, will find this proof in time $f(l)$. If the expression is not valid, the algorithm may either report so, or diverge (so the undecidability of validity is not contradicted).
(a) - Show that there is a $k^n$ prover, for some $k > 1$.
In a letter to John von Neumann in 1965, Kurt Gödel hypothesized that an $n^k$ prover exists, for some $k \geq 1$. For a full translation of this remarkable text, as well as for a discussion of modern-day complexity theory with many interesting historical references, see:

M.Sipser "The history and status of the P versus NP problem" Proc. of the 24th Annual ACM Symposium on the Theory of Computing, pp.603-618, 1992.

Problem: Show that there is an $n^k$ prover, for some $k > 1$, if and only if $P = NP$."

Figure 5.4 that he mentions contains the standard logical axioms for first-order logic (I can post the picture here, if you like).
I tried reading the mentioned article, and although it is very interesting from the historical point of view, it didn't help me figure out the solution. My first attempt was to use the result that a formula $\phi$ is valid if and only if its negation $\neg \phi$ is not satisfiable and try to connect this problem to $SAT$, which we know is $NP$-complete. However, using this result I obtain something about a formula NOT being satisfiable, while $SAT$ is about satisfiability.
Can anyone help me with this statement? Thanks in advance.
PS: Not closely related to what I am asking, but I think I was able to solve letter (a) by noticing that if a formula is valid, then we can apply the logic axioms (and the number of logic axioms is constant) without worrying about how we instantiate variables since a valid formula is true under all possible interpretations.


texts: On complexity of the sieve, start crossing at the square of $p$

texts:
This question is about a common optimization in the basic sieve of Erathostenes.

If we look at this paper (page 3, footnotes), the author says:

  If we start crossing off at $p^2$ rather than $p$, the number of composites
  we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our
  sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor

Similarly, I have seen the same conclusion in other places, so according to them we have that the total cost counting crossings is about (ignoring the $\sqrt n$ optimization):

$\sum_{p\leq n}(\frac{n}{p}-p+1)$

Where $p$ is prime.

But if we look at this algorithm (in pseudocode) implementing this same optimization:

//omitting sieve[2..n] initialization
for p:=2 to n
   if (sieve[p] is prime)
      for k:=p^2 to floor(n/p)
         sieve[k*p] := not prime     //cross multiples of p

I would say the total cost is:

$\sum_{p\leq n}(\frac{n}{p}-p^2+1)$

because the cost of the inner loop is

$\sum_{k=p^2}^{\frac{n}{p}}=\frac{n}{p}-p^2+1$

Am I wrong?


texts: Optimal linking in synchronous environment for shortest path tree problem

texts:
I am dealing with the Shortest path tree problem in the specific synchronous environment.

In the following algorithm, initiator begin the execution calling primitives Construct. This primitive  offers every neighbors but its father to be linked to the tree by a construction message cons.

Construct()
    Begin
        For all j in neighbor_i\{father_i}
        send_to(j,cons,distance+1));
    End For
End

Receiving a message, the site looks if the distance is the best put forward is better than the current distance. If it is the case, then it accepts the proposition and calls itself Construct to offer to its neighbors to become their father because it got closer to the root.

In a synchronous environment, the algorithm is the same but we have to notify that as far as the environment is synchronous, the first linking proposition is unavoidably the best.

I don't understand this assumption.
We notice that root is linked to pulse $0$, but I don't understand
    why sites at the distance $i$ are linked to pulse $i$.

Ask me if you need some more details.


texts: Why is casting float to double applicable?

texts:
This is indeed a Computer Science Question.
As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits.

e.g

Long: 0x00000000ffffffff casts down to
Int:  0xffffffff

However, this does not work with the representation of double and float:

Double:  b = 0xa000 0001 1000 0001 should cast down to

Float:   c = 0x1000 1001

which is not the same, even if the double is in the boundaries of float.

So how is Casting from any type to another defined?


texts: What are different ways to provide a semantics to a language?

texts:
Suppose you have 1. a grammar for terms of a language; 2. type-assignment rules, 3. a set of reduction rules. You want to prove that your language is adequate for mathematical reasoning. If I understand correctly, the right way to do it is to develop a semantics for it, and then prove certain desirable properties such as soundness and consistency.

I've seen different approaches to this. Usually, a model in set theory is involved. But I believe that is not the only way to do it. Wouldn't, for example, an interpreter for that language on the untyped λ-calculus count as a semantics? So, my question is: what are the different ways to provide a semantics to language?


texts:
I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus protocol.

I could not understand what consensus has to do with your writing on disk, where you seem to have only a single node writing a contigous piece of information (I asked this Q at dba but they blocked my account saying that it is a violation) but, anyway, let's take a distributed DB. I read that consensus allows me to agree upon a single value (without resorting to any locks). But, atomicity means that you should agree upon many values at the same time. How do you exploit the consensus algorithms for updating multiple values atomically?

I see in computerphile about Paxos that you can use consensus to take locks.
Do you use consensus just to take them and commit a transaction under the locks?


texts: NFA-$\epsilon$ extended transition function for inverted strings

texts:
It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows:
\begin{align*}
\hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\
\hat\delta(q,\epsilon) &= ECLOSURE(q) \\
\hat\delta(q,\alpha x) &= \bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(p_i,x))
\text{ for } \alpha \in \Sigma^* \text{ and } x \in \Sigma
\end{align*}

I would like to give an equivalent definition for the function but now considering an string $w \in \Sigma^* $ such that $w = x\alpha$ with the same definitions for $x$ and $\alpha$ given above. But what I've only got is the base case (i.e. $w = \epsilon$) which is pretty the same. Any hints to define the function like that?


texts: Proving the regularity of a certain language

texts:
I've been fumbling around with this problem for the last hour, and I'm incredibly stumped.

Let $A = \{\; 0^ku0^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$. Show that $A$ is regular.

The language obviously satisfies the Pumping Lemma, but that is not conclusive for regularity. How on earth do I prove that this language is regular? I'm aware of all the normal methods (closed-under, etc), but I cannot for the life of me figure out the appropriate condition to continue.


texts: Polynomial Identity Testing Evaluating a polynomial on a circuit

texts: Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of bits required for the intermediate calculations is too high i.e How can we guarantee that the evaluation does not require more than polynomial bits (polynomial in the size of the circuit) ?


texts:
Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially.
(So if, for example, my 3SAT formula has 16 variables and 32 clauses, a transformed 2SAT formula would have 2ˆ16 variables and / or 2ˆ32 clauses)

An example of a 3SAT formula I would like to convert is:

A xor B xor C

Or the same in CNF:

(A or B or C)
and (A or !B or !C)
and (!A or !B or C)
and (!A or B or !C)


texts: Scenarios where merge sort is preferred over quick sort

texts: As merge sort and quicksort both have the same average time complexity of $O(n \log(n))$. In which scenarios would merge sort be preferred over quicksort when sorting data?


texts: nlp: phonetic edit distance between a word and the closest of a set of words

texts:
Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large set of words and I'm certain the speaker is trying to say one of these words. However, the voice recognition system is not perfect, so sometimes the voice recognition engine will spit out a word that is phonetically similar to what the user intended, but that is not in the set.

In other words, I have a word X, and a set of words Y. I want the member of Y which sounds the most like X.

I know that phonemes are the most basic sound unit of sound, so I've attempted to use CMU's Pronouncing dictionary to break X into phonemes, and use something similar to an edit distance algorithm to alter these phonemes until they match one of the members of Y. However, there are some huge issues:

There are at least 40 phonemes in CMU's system, which makes for a huge branching factor when you consider adding or replacing at any given position. I can't thoroughly search beyond three changes or so, which isn't sufficient.
Phonemes are perhaps too 'low-level' in the sense that there are many combinations of phonemes which are not words at all.

Building on complaint #2, I was thinking it would be nice to have a weighted graph of at least the most common words to other reasonably similar words, and I could run a search algorithm on this graph to find words in Y more quickly, and with a less explosive branching factor. Precomputing such a graph is on the table, as it could just be loaded at runtime.

Are there any sort of methods for doing this which exist currently? Or should I be thinking in a different direction?


texts:
I have been looking into the history of programming, and everybody and their grandmothers begin the subject with a claim more or less similar to the following:

  At first, programmers used machine code. Later, there were assemblers. Then, pseudo code, and finally Fortran came.

With some Google-fu I can very easily find examples of punch cards containing Fortran statements, COBOL statements, and some Assembly statements. Wikipedia has some punch card examples for short code.

But I am yet to find a reliable source explaining how programmers entered machine code into computers using punch cards. Or pseudo code using punch cards.

Were there really punch cards for machine code? Or when stored programs appeared they were already programmable with Assembly?


texts: B+tree implementation using single file on disk

texts:
I'm studying B+trees and I'm trying to understand how actual data can be stored in a physical file and still allow fast lookups. None of it would be in memory, all of the pointers would be "seeks" to different portions of the file.
Specifically I'm trying to figure out a way to do text searches. Hence the leaf nodes would be an inverted index:

Because I'm storing this all in a single file I'm having problems understanding where in the file the actual tree should go (the pointers) and where the actual data should go. Should the tree simply be the first part of the file and then just have the data? Are there standards for this?


texts: Is it decidable whether a TM reaches some position on the tape?

texts:
I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.

  For an integer $c>1$, and the following three problems:

  Is it true that for every input $x$, M does not pass the $|x|+c$ position when running on $x$?
  Is it true that for every input $x$, M does not pass the $\max \{|x|-c,1 \}$ position when running on $x$?
  Is it true that for every input $x$, M does not pass the $(|x|+1)/c$ position when running on $x$?

  How many problems are decidable?

Problem number (1), in my opinion,  is in $\text {coRE} \smallsetminus \text R$ if I understand correct since, I can run all inputs in parallel, and stop if some input reached this position and for showing that it's not in $\text R$ I can reduce the complement of Atm to it. I construct a Turing machine $M'$ as follows: for an input $y$ I check if $y$ is a history of computation, if it is, then $M'$ running right and doesn't stop, if it's not, then it stops.

For (3), I believe that it is decidable since for $c \geqslant 2$ it is all the Turing machines that always stay on the first cell of the stripe, since for a string of one char it can pass the first cell, so I need to simulate all the strings of length 1 for $|Q|+1$ steps (Is this correct?), and see if I'm using only the first cell in all of them.

I don't really know what to do with (2).


texts:
I am aware that the question is asked before but i there is still a confusing part for me.

In book the solution is like that:

$T(n) = 2T(\sqrt{n}) + \log(n)$
$m = \log n$ yields
$T(2^m) = 2T(2^{m/2}) + m$
Then $S(m) = T(2^m)$ produces the recurrence:
$S(m) = 2S(m/2) + m$
So $T(n) = T(2^m) = S(m) = O(m\log m) = O(\log n (\log {\log n}))$

But i can't understand in part $5$, how $2T(2^{m/2})$ is converted to $2S(2m/2)$ ? If $S(m)$ is $T(2^m)$, then $S(m/2)$ must be $T(2^{m-1})$? Can you verify me that why the book's solution is correct, and i am wrong?


texts:
Given a LTL formula $\phi$ and a transition system $T$ we have to do following steps:

Build a (non deterministic) Büchi automaton for $T$
Build a (non deterministic) Büchi automaton for $\phi$
Compute the intersection of these automatons and check for emptyness

Step 1 can be done in $\mathcal{O}(|T|)$ time and space. I also know and understand that step 3 requires $\mathcal{O}(log^2n)$ space. But what about step 2? The size of the resulting Büchi Automaton from a LTL formula can be exponential in $|\phi|$. Writing that down requires more then polynomial space. So what am I missing here?

Do you may have any papers or books I could read on this topic?


texts:
Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$.

This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. The author provides the following answer: $\overline L = \{\lambda, a, b, ab, ba\} \cup \{ w \in \{a, b\}^+ : |w|\geq 3\}$. Mine on the other hand is the following: $\overline L = \Sigma^* - L = \{w \in \Sigma^* : w \neq aa, w \neq bb\}$. Is my answer wrong? Thanks in advance.


texts:
I'm trying to teach myself a bit about machine learning, so one of the first things I did was implement a KNN classifier in ruby. My goal was to classify text product reviews into 8 classes:

books-positive
books-negative
kitchen-positive
kitchen-negative
dvd-positive
dvd-positive
electronics-positive
electronics-negative

I created features from my reviews by converting them into a set of bi_grams, removing stop words and then using a bag of words model. I calculate the closeness of feature by euclidean distance.

However the result wasn't very good, the max percentage of correct classifications I've gotten is about 28% which is little better than just guessing. Are there any one know of anymore improvements I can make to my classifier to make it better? Or any resources I can use to research from. I've included my source code and training/testing data below if anyone wants to take a look.

https://pastebin.com/x6DbQtts

https://pastebin.com/jDBsndPx

https://pastebin.com/SKikxz5G


texts: Formulating a constraint to exclude a single point from the feasible region of an IP?

texts:
Consider a basic integer program such as:

$$\begin{align}
\min_x & \quad c^Tx \\
\text{s.t.} & \quad Ax \leq b \\
&\quad x_i \in \{-100,\ldots,100\}
\end{align}
$$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a point $y \in \mathbb{Z}^n \cap [-100,100]^n$ that I would like to exclude from the feasible region.

I am wondering if there is an elegant way to do this without introducing new variables to the formulation? If there is no way to exclude $y$ from the feasible region without adding new variables to the formulation, then is an approach that allows me to do this by adding the fewest possible variables?

I should add that this question is loosely related to a different question that I posted here a few months ago (though there was no concrete answer given to that one either).


texts: Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)

texts:
So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book :

  The idea is to cycle through all possible configurations $\sigma$ of $M$, for each one checking whether it is a final configuration that is reachable from the initial configuration by a computation of $M$. In case no such accepting configuration is found we know $x\notin A$ so we let $\overline M$ accept $x$.

My question here that the machine $M$ may not halt for a string $x\notin A$. Then the logic of "cycle through all possible configurations" won't make any sense. What am I missing here?

On a side note is this book too high level for me? (I am graduate in Computer Science) Getting stuck at page 12 is not a good sign right?


texts: I am building a 64 bit CPU in Minecraft and I'm stuck on adding division into the ALU. I was told I should ask this here. Does anyone know how to divide in binary using only logic circuits? I can't use any counters or registers, just logic gates.


texts: Finding fixed size submatrix with highest sum

texts:
I have a matrix, which has N rows and M columns. I need to find n rows and m columns, which has the highest sum. Matrix consists of positive numbers. Not optimal solutions are ok. For example N=M=4; n=m=3

A=$\begin{bmatrix}13 & 83 & 93 & 1
\\70 & 84 & 37 & 38
\\24 & 68 & 78 & 25
\\30 & 47 & 87 & 89\end{bmatrix}$

The highest sum (571) is by removing 1st row and 0th column. Currently I take first n rows by sum and m first columns by sum within current n rows. What alternative methods could I use?


texts:
What complexity class results would be implied by a proof of the existence of one way functions. (Apart from the obvious $P \neq NP$)

I thik it would imply $P \neq UP$, but what else?


texts: Chomsky form for language of single alphabet member

texts:
I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}

My approach was

S -> AB | e
A -> a

Now here's the part I'm confused, how do I represent B? If B -> a then I get only even strings, if B -> e then it's not in normal form. :| Any help would be appreciated.


texts: Can a recurrence relation be translated to a composite function of itself?

texts:
Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions.

Having as an example this recurrence relation:

$\qquad \begin{align}a_0 &= a_1 = 1 \\ 2a_n &= 3a_{n-1}-2a_{n-2}\end{align}$

I would like to transform it into a recursive function $f$, able to be called to itself a number of times (composite), i.e.  $f \circ f \circ f \circ \dots \circ f$  ($n$ times), getting the same result as with the $a_n$ relation.

Any ideas about it?


texts: How can the initial "booting" state of a computer be different at different time points?

texts:
In my experience, sometimes a computer boots normally, and in a time span of days, the computer won't boot, then again, it will boot normally again. I am not a computer science expert so I assume that if a computer boots normally one time and then it doesn't, it must be due to any changes made into the computer between those time points.

My question has the motivation of understanding the booting process of a computer at a basic level as to know how to debug such a behavior.

For a concrete example, I got a new computer with Ubuntu 18.10 that presented this behavior, all the time without access to internet, so no updates/upgrades possible.

Can anything change in a computer without the user modifying something, also while not having internet connection?


texts: Does a reentrant list for signal queue in a single-thread environment exist?

texts:
I need to handle Unix signals in a single-threaded application with the following goals:

Signals doesn't mask on receive (thus, the signal handler must be reentrant).
I am not allowed to lose signal data (thus, if a new signal comes before the handler of the previous returned, it also must be handled correctly).

I have the common multi-threaded primitives (spinlocks, semaphores, etc). But they doesn't seem enough, because my higher-level data structures (even a such simple as a list) aren't thread-safe.

My initial idea was the following:

I use a list, in which I store the data of the incoming signal fast,
and process them (call the possibily much slower running handlers) later, out of the critical section.

The main problem with that, that the list data structure isn't thread safe. If I lock it, I can't store a second signal anywhere. I can't wait until the previous handler exits, because on the second signal it is essentially suspended in a critical section.

Simply I don't have any idea, how to handle the following scenario:

signal1 comes, the process suspends, and the handler of signal1 starts
signal2 comes, the handler of signal1 suspends, and the handler of signal2 starts
Handler of signal2 returns, execution returns to the handler signal1
Handler of signal1 returns, execution returns to the main program.

After thinking a lot on it, I have an impression, maybe my problem is unsolvable. Am I right? How do operating systems handle similar problems (for example, possibily bursting interrupts from hardware)?


texts: Maximum number of not overlapping cycles in an undirected graph

texts:
Basically, when given an Undirected graph, the problem of getting maximum cycles is known.
This case is quite different.
The graphs I'm dealing with are made by converting geometric polygons to vertices and edges, so vertices relative position matters, and there are weights on the edges representing the distance between 2 vertices.
The are 2 problems:

Problem 1:
finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other.

for example:

as you can see, the the above graph has a maximum of 5 not overlapping cycles:

purple - (a,b,e,x,d,a)
green - (d,x,n,f,k,i,d)
orange - (x,e,f,n,x)
pink - (b,c,g,f,e,b)
red - (f,g,h,m,k,f)

My way of tackling this was:
Given a Graph G = (V,E). randomly pick a vertex v and
(1) execute DFS(v) on it, hoping it will eventually reach v and that would be the one of the cycles.
meanwhile, for every vertex u it encounters, execute (1).
I'm think it's a good way but I hope to find better (neater) solutions from you.

Problem 2:
finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other, and for each polygon, it's perimeter is bigger than some pre-defined threshold.

For that problem, I can honestly say I have no clue on how to solve it. ;)
I'll be happy learn about solutions for both problem 1 and problem 2
Thanks!


texts: (Un)computability of a restricted Halting Problem

texts:
Before I start with my question, I want to state some notation I am using. I fix some arbitrary but fixed enumeration of Turing Machines (TMs) and denote with $\Phi_i : \mathbb{N}\to\mathbb{N}$ the function that is computed by the $i^\text{th}$ TM in this enumeration. Furthermore $\Phi_i(x) \downarrow$ denotes that the computation of $\Phi_i(x)$ terminates with some result $y$, i.e., $\Phi_i(x) = y$. Furthermore, $\Phi_i(x) \uparrow$ denotes that the computation of $\Phi_i(x)$ never terminates.
I know that the following function is not computable:
$$
f(x) = \begin{cases}
1 & \text{if } \Phi_x(x)\downarrow \\
0 & \text{otherwise}
\end{cases}
$$
Now, suppose we fix some $n \in \mathbb{N}$ and define:
$$
h(x) = \begin{cases}
1 & \text{if } \Phi_x(x)\downarrow \text{ and } x \le n\\
0 & \text{otherwise}
\end{cases}
$$
I found some lecture notes which state that $h$ is computable because it is the characteristic function of a recursive set (because it is finite) and is therefore computable. Is this claim correct?
If $h$ is actually computable I can't think of an algorithm because one simply can't decide if $\Phi_x(x)$ diverges to return $0$ in the case that $x \le n$.


texts: Variant of TSP: allow each vertex to be visited at most twice

texts: We are given a finite set $V$ and a set of distance $d : V\times V \rightarrow R\ge 0$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we prove this is NP complete?


texts: Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?

texts:
Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent are not back edges (lets assume undirected graph). In an undirected graph we have an edge back and forth between 2 vertices $x$ and $y$. So after visiting $x$ when I process $y$, $y$ has $x$ as an adjacent vertex, but as its already visited, the code will mark it as a back edge. Am I right in saying that? Should we add any extra logic to avoid this, in case my assumption is valid?

DFS(G)
    for v in vertices[G] do
         color[v] = white
         parent[v]= nil
         time = 0

    for v in vertices[G] do
        if color[v] = white then
            DFS-Visit(v)

Induce a depth-first tree on a graph starting at $v$.

DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
        if color[a] = white then
            parent[a] = v
            DFS-Visit(a)<br>
            v->a is a tree edge
        elseif color[a] = grey then
            v->a is a back edge
    color[v] = black
    time = time + 1

white means unexplored, gray means frontier, black means `processed'


texts: Circuits vs Turing Machines in the "nonuniform model of computation"

texts:
I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the problem. The authors refer to this as a nonuniform model of computation.

My question is: why do we need to use circuits for this type of model? Couldn't we just as well allow for a different Turing machine for each input size? Is there some subtle reason for why we need to use circuits in order to study this model of computation?


texts: Master Method to solve recurrences is 'a' related to 'b'?

texts:
The master method allows us to solve certain recurrences of the form

$$T(n) = aT(n/b)+f(n)\,,$$

where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further restrictions that aren't important for this question.

The above recurrence describes the running time of an algorithm that divides a problem of size $n$ into $a$ subproblems, each of size $n/b$. This is intuitive in the case that $a=b$ (for example, merge sort divides the list into two parts of size $n/2$) but are there any examples of recursive algorithms that follow this schema but where $a\neq b$?


texts: Is matching with mismatches a special(parametrized) case of Closest String problem?

texts:
I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the connection. The Closest String problem is defined as :

Instance: Strings $S_{1},S_{2}...S_{n}$ over alphabet $\Sigma$ of length $L$ each and a non-negative integers $d$ and $n$.
Parameters: $n,d$
Question: Is there a string $s$ of length $L$ such that $\delta(s,S_{i})\leq d$ for all $i=1..n$?

Note: $\delta(x,y)\leq d$ is the Hamming distance between $x$ and $y$.
This problem is proven to be NP-complete.
On the other hand we have a problem of matching with mismatches, which is described as:

The problem of string matching with $d$ mismatches consists of finding all occurrences of a pattern of length $m$ in a text of length $n$ such that in at most $d$ positions the text and the pattern have different symbols. In the following, we assume that $0 < d < m$ and $m\leq n$.

Landau and Vishkin gave the first (to my knowledge) efficient algorithm to solve this problem in $O(kn)$ time.
Now my question is:
Is matching with mismatches, or can it be seen, as a special parametrized case of the Closest String problem and how is this connection made?


texts: I have checked many websites but did not get the right answer. what is the meaning of constructor in java?


texts: Max-Heap PriorityQueue to keep the k highest items and return them in descending order

texts:
I have created a custom implementation for PriorityQueue using max-heap and everything works fine.
But now i want to change it and keep only the k highest objects in the heap after every insertion. I have to use only one instance of my PriorityQueue and no other helping data structure.
So my problem is how should i know if the object that I want to insert is "better" than the "worst" in the priority queue. It's max-heap implemention so the get(first) returns the "best" object and the get(last) it is not the "worst" necessarily.
I need to keep the complexity of insertion at O(nlogn).
Any idea?


texts: Hoare triple: Loop invariant and partial correctness

texts:
Below there is Hoare triple in which variable $a$ is an array of integers, $len$, $x, i$ are integer-valued variables, and $r$ is a Boolean-valued variable. I have to provide a loop invariant (using predicate logic) suitable for proving partial correctness and explain in words why it is a loop invariant and why it is sufficient to prove partial correctness.

$$\begin{align*}
&\{0 ≤ len \} \\
&i = 0;  \\
&r = \textbf{false}; \\
&\textbf{while}\;(i < len)\;\{ \\
&\quad\textbf{if}\;(a[i] = x)\;\{ \\
&\quad\quad r = \textbf{true}; \\
&\quad\quad i = len; \\
&\quad \}\;\textbf{else}\;\{ \\
&\quad\quad i = i + 1;\\
&\quad \} \\
&\} \\
&\{(r=\textbf{true})\iff(\exists k \in \mathbb{Z}: (0 \le k \land k < len \land a[k] = x ))\}
\end{align*}$$

I tried to use loop rule and get the invariant I by the third premise:

$$\{I \land \lnot b\} \; [] \; S \; \{Q\}$$

What I did:
$$\{I \land i < len \} \implies \{(r = \textbf{true}) \iff (\exists k \in \mathbb{Z}:(0 \le k \land k < len \land a[k] = x ))\}$$

I can not go anymore at here, because I do not know how to find an invariant $\land$  $a[ i ] \neq x$ $\implies$ postcondition. And if $a[ i ] \neq x$ that means this it does not find $x$ in array $a$. But the postcondition said it will find $x$ because $r = \textbf{true}$.


texts: Superdense coding - What are the individual qubits A and B?

texts:
With reference to this  PDF discussing Superdense coding, it is mentioned that there are two qubits A and B whose superposition gives the system $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$. It is said that Alice has A while Bob has B. What are the individual qubits A and B?

Since the system is entangled, can there exist two qubits A and B such that their superposition is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ ? If the answer is no, how is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ actually shared between Alice and Bob (or maybe how is it realized in practise)? Is it just that A and B cannot be written using the standard basis?


texts: Is there any problem that is R-complete and RE-complete

texts:
R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition?

RE-complete is described on wikipedia. But what kind of reductions is used? Since we are already out of the set R, does it still make sense to define by many-one reduction?


texts: Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$

texts:
The following problem is from CLRS (31.1-13, Page 933, 3rd edition):

  Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $Θ(M(\beta)\log \beta)$. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)

By a simple divide and conquer (by dividing $\beta$-bit integer into two $\beta/2$-bit integers), I obtain the recurrence $T(\beta) = 2T(\beta/2) + M(\beta)$. However, how to argue that it is $O(M(\beta) \log \beta)$?

My attempt: I think the result relies on $M(\beta)$. If $M(\beta) = \Theta(\beta)$, then $T(\beta) = \Theta(M(\beta)\log \beta)$. But, if, for example, $M(\beta) = o(\beta)$ or $M(\beta) = \omega(\beta^2)$, you may not obtain $T(\beta) = \Theta(M(\beta)\log \beta)$.

According to the hint, it seems that we should use different recursions to obtain $O(M(\beta)\log \beta)$ and $\Omega(M(\beta) \log \beta)$, respectively. But how?


texts: Conditions for maximum period of quadratic congruential method (PRNG)

texts:
$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$

Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):

  $c$ is relatively prime to $m$
  $d$ and $a-1$ are both multiples of $p$, for all odd primes $p$ dividing $m$
  $d \equiv a-1$(mod 2) when $2|m$; $d$ is even and $d \equiv a-1$(mod 4) when $4|m$
  $d \not \equiv 3c$ (mod 9) when $9|m$

Knuth writes in the answer to exercise 8:

  If $p \leqslant 3$, it's easy to establish the necessity of condition (iii) and (iiii) by trial and error method

I do try to find my own way to prove (the necessity of) condition (iii) and (iiii). Here's how i prove the first one:

Assume $m=p^e$. Firstly, we consider the case when $p=2,e=1$

So, the sequence $X_n$ with ($X_0 = 0$ and $m=2$) has the period of $2$ when:
$$X_2 = X_0 = 0 $$

We can prove: $X_2=dc+a+1 \operatorname{mod}$ 2 (due to the relatively prime $c$)

Obviously, we have: $$d \equiv a-1 (\operatorname{mod} 2)\space \tag1$$

If $e \geqslant 2$ then $4|m$. The same sequence $X_n$ with $(X_0=0,m=4)$ must have the period of 4 which means: $X_0\not=X_1\not=X_2\not=X_3$

$X_2 \not=X_0$. So, $X_2 = 2$ and $X_3 \not=X1$. The fact then implies:
$$aX_2 \not\equiv 0 (\operatorname{mod} 4)\space\tag2$$

Due to (1), (2), $a \operatorname{mod} 4$ and $d \operatorname{mod} 4$ can only adopt odd and even values. After some trials on $X_2 = dc + a + 1 \operatorname{mod} 4= 2$ (c is odd), we easily prove: $d \equiv a-1(\operatorname{mod} 4)$

I have also proved the condition (iiii) by my "trial and error method" but i'm not sure if they are what Knuth mentions. So my first question:
1. What's exactly "trial and error method" applying for this situation?

Finally, the proof of condition (ii) confuses me:

  If $d \not\equiv 0(\operatorname{mod} p)$ then $dx^2+ax+c \equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ for some integers $a_1$, $c_1$ and for all integers x

$d\not\equiv 0 (\operatorname{mod} p)$ leads to d relatively prime to $p^e$. But i can't go on any further from this.

Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ hold when $d \not\equiv 0(\operatorname{mod} p)$ ?


texts: Are there any functions with Big O (Busy Beaver(n))?

texts:
So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than exponentials, faster than the Aaronson sequence, and faster than a recursive use of Knuth's up-arrow notation.
This led me to a thought: are there any algorithms that grow in size with Big O (Busy Beaver(n)), aside from the Halting Problem? Is it even possible to design such an algorithm on that would run on a Turing Machine-equivalent computer?


texts: Differences between basic, complex and terminological facts in a Knowledge Base using First-Order Logic

texts:
I've been reading the excellent book Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque.

In the beginning of Section 3.2 "Vocabulary" of Chapter 3 "Expressing Knowledge" they state:

  In creating a KB (Knowledge Base) it is a good idea to start with the set of domain-dependent predicates and functions that provide the basis for the facts about the KB's domain.

In the same section these facts are separated in three categories:

Basic facts
Complex facts
Terminological facts

After reading the entire chapter I could not entirely understand the differences between these types of facts.

Can someone help me to understand the differences in these concepts?


texts: Please explain a greedy algorithm in a naive manner

texts:
I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms.

From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local maxima/minima, we become 'greedy' and declare that as the global maxima/minima.

I suppose that is wrong?


texts: Disadvantages to using simple step functions for activation in neural networks?

texts:
From what I have read, the main advantage to using tanh(x) or sigmoid(x) as an activation function for neural networks is that it is very easily differentiable.

I am trying to implement a neural network that uses a genetic algorithm for optimisation rather than backpropogation, and therefore it doesnt matter if my activation function is differentiable or not

When running my algorithm on matlab/octave, it seems like there is a massive bottleneck in the computation when it is trying to calculate sigmoid of the input to the neuron, so I was wondering if there would be any disadvantage to using a simple step function instead of the more complex sigmoid or tanh functions to activate the neuron?


texts: Optimizing convex function in an online manner

texts: I have a convex function of $n$ variables, $f(x_1,x_2,\dots,x_n)$ and need to find its minimizer. Are there algorithms that can retrieve the minimizer in an online fashion? i.e. solve for $x_1^{(opt)}$, $x_2^{(opt)}$ and so on in a sequential manner?


texts: Generalized steps to find tree traversal for any m-ary tree

texts: So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I got confused, Is there any generalized steps that we can follow to find traversals for any $m-ary$ tree.


texts: "P may collapse" vs. Time hierarchy theorem

texts:
https://en.wikipedia.org/wiki/P_versus_NP_problem states:

  If graph isomorphism is NP-complete, the polynomial time hierarchy
  collapses to its second level.

They further state that this may be unlikely, but at least it's a possibility. However, https://en.wikipedia.org/wiki/Time_hierarchy_theorem states:

  The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME($n^k$) for any fixed k. For example, there are problems solvable in $n^{5000}$ time but not $n^{4999}$ time.

Why don't the above two quotes contradict each other?


texts: Consutrcting a transition diagram of a deterministic Turing machine

texts:
I'm having some issues constructing a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$

The point where I get stuck is how I should make sure that $i = j + k$

My thoughts:

My thought was to initially do something similar to do something including an addition turing machine where I check that the final tape is of the structure generated by the language i.e we should have 2 $0$s, 1 $1$, 1 $2$ and 3 $1$s = 6 and if it is correct then we'd go through checking if $0$s come before $1$s, $2$s before $1$s and $3$s before $2$s.

I think this is a really complicated way to do it, and that's why I'm asking.

Question: Construct a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$. What I'm asking is for some guidance.

Thanks in advance!


texts:
I was solving problems related to P and NP where I encountered the following problem:

Given a standard definition of NP,
 if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = 1;
if x does not belong to L then for every y with |y| <= |x|^d we have A(x, y) = 0.

1. what is the new class formed when we don't include the second statement?
2. what is the new class formed when we don't include the first statement?
I am well versed with the definitions of P and NP but unable to figure out how to determine these new classes.
 Any help in understanding these concepts would be appreciated.


texts: Print maximum frequency number in an array(with slight modification)

texts:
There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.


texts: Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement

texts:
While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:

Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets dynamic.

I felt a bit odd after reading the statement that "set" in Mathematics and in CS are different from the mutable point of view. Now in Mathematics what we deal with are theoretical aspect of things and as such "set" is a theoretical concept and so it is in Theoretical CS. If it is immutable in mathematics then so it is in CS. Mathematics and Theoretical CS are interlinked. So given a graph algorithm which say finds the minimum shortest path between a pair of vertices , we can't say whether it belongs to Mathematics or CS.
Often in algorithms we write statements as :
$$S  = S \cup \{a\} \quad \text{view $1$}$$
Which seems to sort of change our set $S$, but if we look it in this way:
$$S'= S \cup \{a\} \quad \text{view $2$}$$
$$S=S'$$
So in the second situation we are not modifying our actual set $S$ we are forming a new set $S'$ with $S$ augmented with $a$ and then after that we are making the variable $S$ refer to $S'$.
What I feel is that the concept of the set being mutable or immutable is solely dependent on the data-structure of representation of the abstract concept of "sets" and since in data-structure the two steps in view $2$ are combined and implemented, so they are called dynamic sets.
In short I feel that Dynamic Sets are data-structure implementation of sets and not the abstract sets.


texts: What are the advantages of online learning when training neural networks?

texts: Stochastic gradient descent with a batch size of 1 is apparently used to learn from single examples as they arrive, but I don't understand why you would use such a small batch size instead of batching training inputs together.


texts:
I came up with following subproblem while working on another problem. Can someone confirm if its a recognized problem. I have spent months but couldn't make any progress.

Design a data structure that maintains a directed graph. A node with node_id=0 is created by default, having no edges. The data-structure supports following queries:

Create() : Create a new node with node_id assigned from an auto-incrementing counter. Add a directed edge from node-0 to this new node; return node_id of new node.
Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there is already an edge from x to y.
Delete(x, y) : Delete the directed edge from node-x to node-y and also delete all the nodes (and their edges) of graph which are not reachable from node-0. return the list of deleted edges and nodes.

All queries should work in amortized complexity O(log(N)), where N is the number of nodes in the graph at the time of query.

PS: Its not a homework problem (obviously).


texts:
System is in safe state if there exists a safe sequence of all processes.
Sequence $[P_1, P_2 …P_n]$ is safe, if for each $P_i$ the resources that  can still request can be satisfied by $P_i$ currently available resources + resources held by $P_j$ with $j \lt i$

The above is from a presentation distributed by my OS II teacher. Assuming it is true, then doesn't this mean that the system is always in a safe state?
I conjecture that $\forall$ set of processes $X = [P_1 ... P_n]$ requesting for a set of resources $[R_1 ... R_n]$ $\exists$ a safe sequence $S = \{P_i ... P_k\}, S: S$ is a permutation of $X$.
Reasoning behind my conjecture. Suppose I had $n$ processes and $1$ resource(each process requesting it.) I could order these processes in order of priority, or ascending order of size and run them. If resources were increased to $k$, there will still be a sequence such that every process completes in finite time. The challenge merely finding it.
Am I wrong?


texts: Are finite state transducers and Mealy machines the same machines?

texts:
There are several versions of the definitions of the FST and the Mealy machine.
Some of the definitions are almost same. Some have a little differences.
But it seems that they both are a kind of DFA with an output function $G \colon \Sigma \times Q \rightarrow \Gamma \times Q$, where $\Sigma$ is the input alphabet and $\Gamma$ is the output alphabet.

I'm not sure about the differences between them.

Are they the same machines? Why is there two different names?

BTW, I found that there is not the set of final states in the definition of Mealy machines or Moore machines. On the other hand, final states do exist in the definition of FST, although Mealy machine is one type of FST. Does it mean that final state is not important when we are talking about the Mealy machines?


texts: Why Right-Division of regular language with RE\E language is regualr?

texts:
I think I can't understand the meaning of language being decidable.
The next case makes no sense to me:

Considering I have language L1 which is regular, and language L2 which is in RE\R (in particular, it cannot be decided).

The right-division of any regular language with some language is regular, and in particular in R.

so:

L1/L2={x ∈ Σ* | ∃ y ∈ L2 : xy ∈ L1}

is decidable.

But I can't see why. I can't describe an algorithm that decides L1\L2, so how come this language is decidable?
I know how to define the transition function, but does it means that the language is decidable?
After all, I can also define a transition function to the accepting problem, it still does not make it decidable.

After all, to check if x belongs to L1 \ L2 I need to go over words and check if there is a word in L2 that completes x to a word in L1, but if there is none, I will run forever.

I think I'm missing something, so I'm very confused. Would appreciate help!


texts: Time - Complexity Convex Optimization and Eigen Decomposition

texts:
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be?  Is the improvement in speed by many factors!?

Minimizing a convex function $L(X)$ in one matrix variable with orthogonality constraints over the matrix-essentially in my case this ends up to solving an eigen-decomposition.
Minimizing the same convex function $L(X)$ with linear constraints in $X$.

I know that 2.) should be faster. But what is the direction of work I need to do- to compare the improvement in speed-especially in terms of using the fastest available eigen solver for 1.)-what would be the corresponding fastest approach to solve 2.)?


texts: Symmetric Roles of the two problem solutions in RINS

texts:
Currently, I am reading the paper "Exploring relaxation induced neighborhood to improve MIP solutions" by Danna et.al. from 2004 and they are talking about a symmetric role of incumbent and the relaxed solution. Which I understood as following:

An incumbent of poor quality can be improved because the respective relaxation is leading into a good direction. And vice versa, a loose relaxation can be compensated by an incumbent of good quality.

How does it work? Can it not happen that it still continues into a completely bad direction?


texts: Mapping reduction from $A_{TM}$ exercise

texts:
Let $L = \{\langle M \rangle \mid \text{M is a TM which accepts only the string  "010"}\}$. Prove that $L$ is undecidable.

This is my solution, reducing $A_{TM}$ to $L$:

  $R(\langle M,w \rangle)$ outputs $M'(x)$, such that:

  if $(x == "010")$: run $M$ on $w$ and do on $x$ what $M$ does on $w$

  else reject $x$

The language $L(M')=\{010\} \iff M$ accepts $w$. Is the mapping reduction well done? Thank you.


texts: How can I evaluate an algorithm for a NP-Hard problem?

texts:
I have written a program to calculate the number of stable partition in a graph.
 ( That is: find which partition of the nodes does not have edges between nodes of the same block. )

The professor, asked me a way to evaluate the performance of my algorithm (not the program), but my algorithm is simply a brute force of all the possible cases, and I don't think you can do any better without heuristics, therefore I think the questions makes no sense (at least to me).

Am I wrong?


texts: Maximum coloring of a graph with paths through uncolored vertices

texts:
Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one:

When I woke up, I wondered why some of the cells in the grid were empty. But it makes perfect sense!  If the grid were full of words, like this one:

The spider would be unable to express statements such as "Hello! How's it going?" because it would crawl over other words while doing so.
This led me to the following question: for a $w$ by $h$ grid, what is the maximum number of words you can fit in the grid, such that there is a path between any two words which does not go through another word? (Let's assume the spider can't move diagonally)
Or in general, given a graph, what is the maximum number of vertices you can color, such that for any pair of two colored vertices, there is a path between them which only goes through uncolored vertices?
In the specific case of a 4x4 grid, the optimal layout is this:

And I think that this might be the optimal one for 9x9:

And for 10x10:

And for 11x11:

And I will conjecture that you can create the optimal coloring for an $n$x$n$ grid by just taking one of these patterns, depending on $n \mod 3$, and extending it (i.e. adding groups of three rows with one uncolored, and two colored, except for the last cell in the row). I have not however found a proof of this, and it is very possible that I'm wrong. But from this, we can get a lower bound on $S(N)$, the maximum number of colored cells for an $N$x$N$ grid:

It is possible that this should be $=$, not $\geq$, but I have not found a proof of this.
Here are some questions I have about this problem:

Is this already a well-known problem? (I couldn't find anything about it online)
Can you prove that the formula shown above is always optimal, or find a counter-example to it?
Can you extend this formula to any $w$x$h$ grid? (It shouldn't be too hard...)
Can you find a similar method/formula for the case where the spider can move diagonally?
I have written a program to solve this, but its running time is $O(2^V E \log* (E))$, so I have only been able to run it on a 5x5 grid in a reasonable amount of time. Can you find a better algorithm and/or prove that this problem is NP-hard/complete?

Edit: The above formula and diagram for 10x10 are wrong (well, not optimal). Here is a 10x10 grid with 59, instead of 57 words:

Perhaps adding 2 to the $N \equiv 1 \mod 3$ case does make it optimal...
Edit 2: The paper linked to by Peter Taylor was very helpful; bounds should actually help a lot with this problem, because once you have a lower bound $L$ and an upper bound $U$, you can, instead of searching all possible colorings, only search colorings with $U < V < L$, where $V$ is the number of colored vertices. In the case of 6x6, the bounds (22-24) that paper gives reduces the number of possibilities from  $2^{36} = 68719476736$ to ${36 \choose 22} + {36 \choose 23} + {36 \choose 24} = 7358764500$ -- a nearly 100-fold reduction. With this, I was able to confirm that the maximum for 6x6 is indeed 22, but their lower bound is actually slightly better than mine for numbers  $\geq 8$. They also provide bounds for any rectangular grid, not just squares.
Also, here are the optimal configurations for squares where moving diagonally is allowed:
3x3
111
101
111

4x4
1111
1010
1101
1011

5x5
11111
10101
11011
10101
11111

6x6
111111
101101
110101
111011
100101
111111

It seems like the optimal thing for squares with odd side lengths is to create a border of 1s around a checkerboard pattern of 1s and 0s.


texts: Mutable Object Values in a Functional Interpreter

texts:
I am writing a functional style interpreter for a non-functional programming language that supports both primitive and object values. Primitives are passed by value while objects are passed by reference. I understand how to deal with primitive values but cannot find any good resources on handling mutable object values.

For example, take this ECMAScript inspired language:

var a = {'x': 1};
var b = a;
a.x = 3;

print a.x; // outputs 3
print b.x; // outputs 3

What is not clear to me is where the object's internal representation should live in the interpreter's non-mutable state. I can store non-mutable values in lexical environment records but I believe I need another level of indirection for storing objects because they are mutable.

I have considered having the interpreter state store a record of active objects, with lexical environments then storing a reference to one of these objects. Such references would need to be resolved dynamically against the current state object.

How has this been addressed in other works?


texts: Given NFA to recognize a language, construct a new NFA for that language without the empty string

texts:
Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with:  M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or may not accept ε, while M’ does not!

My solution is to discuss the different cases. If M doesn't contain ε, then, don't need to produce a new M', but if M contains ε-transition, then convert it to DFA. I'm not sure my procedure is right or not.

Can someone come up with some more effective idea?


texts:
The Hessian of multi-layered network exhibits known behaviour at critical points as shown in [1].
The tools of random matrix theory allow [2] to deduce the asymptotic distribution of the eigenvalues of the Hessian.

There are some numerical experiments with distributed Newton type stochastic methods. The scalability (ability to perform computations in parallel architecture ) is achieved under certain assumptions on the eigenvalues. I am just wondering about two questions:

1) Can one describe the eigenvalues distribution for the Hessian obtained from average reward function in reinforcement learning?

2) If yes, are there any scalable iterative methods (apart from SGD) that can optimise the average reward function and exploit the structure of the eigenvalues of the hessian if possible.

I beg my apology for possible misleading formulations. Please feel free to express your comments/concerns to me and I will edit the post accordingly.

Many thanks.

[1] L. Sagun, L. Bottou, and Y. LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016.

[2] J. Pennington and Y. Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pages 2798–2806, 2017.


texts: Why does my answer sheet say the set of computable functions is uncountable?

texts:
I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox.

I was thinking that, because Gödel numbering, I could consider the set of computable functions as numerable (and with cardinality equal to $\mathrm{card}(\mathbb N)$). However, I have an  answer sheet that says otherwise, and makes a proof of that I'm pretty sure that is wrong. At least I don't trust it:

  Suppose that the computable functions set is enumerable, and $f_n$ is a function of the set. Consider $g(n)=f_n(n)+1$, its not in the set, therefore contradiction. Because that proof then the computable functions aren't countable, so they can't fit in the Hilbert Hotel.


texts: proof of undecidability of computer viruses

texts:
I have been reading the paper of F. Cohen about viruses, here is the link:

https://web.eecs.umich.edu/~aprakash/eecs588/handouts/cohen-viruses.html

I quite not get the following part:

Detection of Viruses

    In order to determine that a given program 'P' is a virus, it must be
    determined that P infects other programs. This is undecidable since P
    could invoke the decision procedure 'D' and infect other programs if
    and only if D determines that P is not a virus. We conclude that a
    program that precisely discerns a virus from any other program by
    examining its appearance is infeasible. In the following modification
    to program V, we use the hypothetical decision procedure D which
    returns "true" iff its argument is a virus, to exemplify the
    undecidability of D.

program contradictory-virus:=
{...
main-program:=
 {if ~D(contradictory-virus) then
    {infect-executable;
    if trigger-pulled then do-damage;
    }
 goto next;
 }
}

I mean, why does P (which I believe is the program called contradictory-virus) has to decide if it is a virus or not? or in other words, why will only infect other programs if D determines that P (contradictory-virus) is not a virus? I kind of feel that this part of the proof is a little bit awkward and forced to get a contradictory result.

Any detailed explanation about this it would be great. Thanks.


texts: Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

texts:
Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$.

Given this pseudocode:

func wibble_wobble(List<Integer> input):
    Integer constant = input.length;
    return List<Integer> { item * constant foreach item in input };

Since the loop inside the new list initialization is $O(n)$, but the multiplication operation inside is $O(n^2)$, is this function considered to have a time complexity of $O(n)$, $O(n^2)$, or maybe even $O(n*n^2)=O(n^3)$?

My gut instinct says it is $O(n)$ because a change in input would not change the time complexity of the multiplication operation, and thus would not need to be considered, but I am not sure.


texts: The pumping lemma - Proving that this language is NOT context free

texts:
I would like to find out if this language is context free or not:

$\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$.

I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ which is in the language, where $n$ is the natural number given by the lemma. I can write $w=uvwxy$ such that $|vx|≥1$ and $|vwx|≤n$. But I didn't get to any contradiction yet.

Any ideas?


texts:
The question is: We need to design a cache with cache size of 128K bytes, block (line) size of 8 words, and word size of 4 bytes. Consider a computer with 64-bit physical address. The cache is addressed by physical address

I need clarification on this: if we have 128k bytes and each block equals 32 bytes (8*4), do we have: 1.($128$ x $2^{10}$)/$32$ or 2. $128k/32$. The problem is that the first gives 4096 blocks and the second gives 4000 blocks. Which is the correct one?


texts: Difference in Sorting 32- and 64-bit Integers

texts:
In 2007, Barrack Obama was interviewed at Google.

The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a different way to sort integers of different sizes (i.e., 64- or 32-bit)?


texts: LZ-type compression vs. entropy-encoding of BWT data

texts:
Why does there seem to be a preference for using Huffman (or Arithmetic) coding instead of a Lempel-Ziv type compression algorithm for Burrows-Wheeler Transformed data?

I noticed that data compressors such as Bzip2 or ZZip use mainly a combination of BWT, RLE and Huffman/Arithmetic coding. I would like to know what are the reasons against using a LZ-type algorithm instead of entropy encoding.


texts: What will a given CPU architecture do in the event that we were to invert all of the instruction bits to a given instruction?

texts:
Given an arbitrary CPU - Architecture and its instruction set... What would be the outcome of the given inverted instruction within that Architect?
For simplicity, let's use an 8-bit CPU architecture that has an 8-bit Bus design where that bus is used for both addressing and data transfer operations. A single instruction or micro instruction will act on an 8-bit string of binary digits per clock cycle. Each clock cycle may consist of 3,4,or 5 micro instructions before incrementing the instruction register for the next full instruction to be processed. These would account for the Fetch, Decode, and Execute phases of a single CPU clock cycle instruction.
The following is a mock-up only to demonstrate or illustrate my curiosity and concern while designing the layout of a given ISA(Instruction Set Architecture)...
Here we have the range of possible instructions from [0000 0000, 1111 1111] which are all of the possible permutations that this arbitrary CPU-Architecture's Machine Language can support. We could use Ben Eater's 8-bit Bread Board CPU and its ISA as an example... You can find that here along with other useful videos from his YouTube channel: Comparing C to Machine Language, and Programming 8-Bit Computer. With his given implementation, the first 4 bits are used to define the instruction and the second 4 bits are used for data {either memory address or immediate value}...
Now to my question: Given a specific instruction word and its accompanying data field, what would be the resulting outcome if we invert all of the instruction bits?
First, I know that this would be independent on each Architecture's ISA design implementation... Second, I'm just curious to what the ramifications would be when designing your own specifications in that, would it be possible to carefully design and layout your bit fields per instruction in a manner that you could have a special invert operation, that would automatically invert a given instruction where that inversion would produce the opposite or inverse effect of the given incoming instruction? Now, the inversion won't necessarily happen to the entire instruction string that includes all 8-bits, but only to the bit-fields that pertain to the instruction type while preserving the data field... For example:

If we have an Add instruction, the invert op would turn this to a Sub...
If we have an And instruction, the invert op would turn this to an Or instruction...
If we have either a Bit Shift Logical Left or Bit Shift Arithmetic Left, the invert op
would respectively turn these into Bit Shift Logical/Arithmetic Right operations...
And so on...

Would such a design be possible to have perfect symmetry within it's ISA?
-Note- I don't know if this is the correct StackExchange site for this question... if it is not please don't down vote it due to being irrelevant and be kind enough to point me in the right direction letting me know where the appropriate site for this question would be.


texts: Word ladder problem for words with different length

texts:
Is there some one who know any algorithm for word ladder problem with words of different length?

Actually we have some strings with same length and some strings with one length longer but not from any size(any size means:  one string with size 10 and one string with size 1000).

any link or advise is acceptable.

my solution is this: build a graph with strings in the nodes and nodes are connected if their strings can be converted to each other just by changing one letter, then using BFS.

word ladder problem


texts: How does Grover's Quantum Sorting avoid reading the list?

texts: It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ operation. How does Grover's algorithm avoid reading the list? Is there a special representation that can be used classically as well? I understand any such representation will not help the classical case. However I am curious to understand how Grover avoids reading the list?


texts:
On my lecture note it was written that "Finding a clique of size $k$ in a graph is NP".

Later in an example for reduction the following was written:

"Assume we know how to answer "Is there a clique of size $k$ in a graph", then each time we will hide one node of the graph an on the newly created graph we will check Is there a clique of size $k$ in a graph:

If there is a clique of size $k$ and the node is not a part of the clique

If there is no clique of size $k$ and the node is part of the clique

I have read more about it, and wanted to be sure I have understand this example.

Given a graph, answering the question whereas or not it has clique of size $k$ is NP
Given a graph, printing a clique of size $k$ is P

If it is correct then this is an example why NP is a problem (1) that the verifier (2) is P?


texts: Find non-overlapping subsets that maximize the sum of their values

texts:
Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value.

Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?


texts:
I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not preferred in this case? In particular, I'm writing a project in which I need to distinguish between problems solvable in space $c_1\cdot n$ and problems solvable in space $c_2\cdot n$ for $c_2>c_1$.

Which notation should I use? $SPACE(n)$ or $SPACE(O(n))$?
And how to distinguish between space $c_1\cdot n$ and $c_2\cdot n$ without confusion?


texts: How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?

texts:
Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:

  Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
  Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
  For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values. Play the guess with the highest score (minimax).
  Go back to step 2 until you have got it right.

I am curious: what would be the maximum number of guesses necessary to win a Mastermind-like game with 5 pegs instead of 4? How about 1,000 pegs, or a million?


texts: Is there any difference between these two languages?

texts:
If I have the following two languages:

$L_1= \{ w \in \{a,b\} |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$

$L_2= \{ w \in \{a,b\}^* |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$.

Is there any difference between $L_1$ and $L_2$? I understand the impact of the Kleene star, but I don't see what difference it makes here.


texts: What is different between "Arithmetic Calculation" and "Calculation" in computer science?

texts:
What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science?

The "arithmetic" in the former seems needless to me since all calculations are arithmetic.

Is there some meaning that is enhanced by adding "arithmetic" in this case?

Thank you in advance.


texts: Algorithm for splitting an array into k sub-arrays

texts:
We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized sub-arrays (+-1), that each value in the i'th sub-array will be larger than any value in the (i-1)'th sub-array, and smaller than any value in the (i+1)'th sub-array. This method need to be applied in complexity of O(n log k).

Insert(x)- Gets a value x which isn't in our data structure, and adds it. This method need to be applied in complexity of O(k logn).

I did the init method using Medians- ofMedians QuickSelect, by dividing the array into k' sub arrays when k' equals to the closest power of 2 for k, and then I adjusted my pointers to the dividers by using Select on the smaller arrays which added me only O(n).

With the Insert part I'm having some trouble and would appreciate any help, Thanks:)


texts: How is β-reduction a 2-morphism in Category theory?

texts:
According to Categorifying CCCs: Computation as a Process, computation or β-reduction process in untyped-lambda calculus is in fact a 2-morphism in category theory.

Can someone please describe me how is it so and elaborate on it?

P.S. I understand that category theory is a mathematical concept but since this specific question is about β-reduction and lambda calculus I have posted it in computer science section.


texts: After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

texts:
Preface: This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying answer.

Over the years, two novel encryption techniques have come to mind and been implemented as programming libraries that could be integrated into applications. However, how to analyze their security and vulnerability characteristics has never been very clear, and their usage has been limited to mainly experimental tests. Are there tools available for automated examination of such parameters one may be interested in understanding for an encryption library? Are there bodies of people who are interested in being introduced to new encryption concepts for the purpose of executing their own personal analysis on such a process? I'm not sure where to look.

The first encryption algorithm is a mono-alphabetic simple substitution cipher. It requires two keys to operate and is designed to frustrate frequency analysis. The longer of the keys forms a table by which plain-text has a normal substitution cipher applied. Each encoded byte is then split into four values of two bits each. The second, shorter key is then used to allow a random selection from four groups of sixty-four unique bytes each. Each two bit value from the encoded byte is used to select which group of sixty-four bytes to use. Encoding has two disadvantages: the output is four times larger, and repeated data encoding may allow some frequency analysis.

The second encryption algorithm is a stream cipher like the first but internally operates on blocks of data. It utilizes two keys to operate: the first is a two-dimensional array that describes how to construct a (virtual) multidimensional grid, and the second is an initialization vector for the encoding/decoding engine. It attempts to overcome frequency analysis by encoding bytes with a window of preceding bytes (initialized from the second key). A byte with its preceding window of bytes form a multidimensional index into the aforementioned grid. Unfortunately, encoding duplicate blocks of data longer than the window size starts yielding equivalent data.


texts: What other instructions are stored in the ROM?

texts: Apart from the start-up instructions, what other programs are stored in the ROM?


texts: Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

texts:
Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can be reduced if it causes a very significant increase in performance). These vertices are currently stored as floats from 0-255, but this range can also be changed if need be, assuming it will not reduce accuracy too drastically. Also, I can store these objects in any data structure that would be beneficial for this algorithm.

I am given another such object, also with the same number (8) 3-D vertices, but of which in general it must be assumed that none of the vertices are common with any vertices included in the list of stored previous objects.

With all of this in mind, I need an algorithm that will return an object from that list that is optimally close to the test case object (close being defined in the normal, euclidean distance, sense). By optimally close, I mean that it does not have to be the global optimum if this will greatly increase performance, although if there is a quick algorithm that will always return the global optimum i would love to hear it.


texts: Why does Min-Max algorithm delays a good move indefinitely?

texts:
Consider a simple chess example:

Q is white Queen.

K, R is black King and black Rook respectively.

  A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R

1,2...8 is the rank and A and B are the files of the chessboard.

Assume the king can only move horizontally for this example.

Here, if we search to depth 0, the best move should be Qxb8 (queen takes rook on B8)

But if we search for depth 2, then one line goes:

1. Qa1+ Kb3 2. Qxa6 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxb8 Ra4 2. Qb1 (evaluation of the position +100 as rook is taken)

And since both have the same evaluation we select the first variation and play Qa1+ and let's say opposing player plays Kb3.

And now, if we again search to depth 2, same situation arise:

One line:

1. Qb1+ Ka3 2. Qxb8 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxa6 Rb4 2. Qa1 (evaluation of the position +100 as rook is taken)

And again since both lines have the same evaluation we select the first variation and play Qb1+ and let's say opposing player plays Ka3.

And this will keep repeating and the queen will never capture the rook and just keep checking the king in the hope of capturing the rook in the next move but again repeats the same idea.

I hope this example makes it much clear what I am trying to say.


texts: What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU?

texts:
Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive because that's a separate component.
I'm not sure if the exact number is known or provable, but an upper bound could be proven by implementing one or pointing to a known implementation.
I am assuming a binary computer with empty memory. You can, of course, load a program to make it work, but said program must be finite in length. Something like Wolfram's (2, 3) UTM, which requires the whole unbounded tape to be initialized, is out.
The first commercial microprocessor was the Intel 4004, with a transistor count of 2,250 (not sure if that's exact), so that's an upper bound.
But that already had a 4-bit data width and multiple opcodes, probably much more than is required for the theoretical minimum CPU. I have heard of 1- and 2-bit CPUs and one-instruction set architectures like Subleq, so I think we can do a lot better than the 4004. I suspect the true answer is < 1000 switches, but I'm not sure.


texts: What is the origin of the client server model?

texts: I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?


texts: Is this equivalent to any famous NP-complete problem?

texts:
Given the following problem.

  Given an $n\times n$ matrix $A := \{a_{ij}\}$. Find an $n\times n$ matrix $X := \{x_{ij}\}$, where $x_{ij} \in \{-1, 1\}$ for $i, j \in [n]$, that minimizes the following expression. $$\sum_{i,j}a_{ij}x_{ij} - \sum_{|i-k|+|j-l|=1} x_{ij}x_{kl}$$

My question is: is this problem equivalent to any "famous" NP-complete problem? I was able to find a number of similar minimization questions for MAXCUT-type tasks or for Ising model formulations in physics, but never this particular one.

Edit for clarification - by minimization here I meant finding a set of optimal $x_{ij}$ (output) given a certain set of $a_{ij}$ (input).

To give a concrete example: let $A$ be equal to $\begin{vmatrix}3 & 1 \\-1 & -2 \end{vmatrix}$. We want to find a matrix $\{x_{ij}\}$ that would minimize the following expression:

$3x_{11} + x_{12} -x_{21} - 2x_{22} - x_{11}x_{12} - x_{11}x_{21}- x_{12}x_{22}- x_{21}x_{22}$.

Since $x_{ij}$ can only be equal to +1 or -1, for this small $n = 2$ case we can scan through all sixteen possibilities to find the solution: $x_{11} = x_{12} = -1$, $x_{21} = x_{22} = 1$.


texts: What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

texts:
Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).

It requires that for each pair of processes $P$ and $Q$ all messages send by $P$ to $Q$ are received and processed by $Q$ in the same order. E.g. if $P$ sends messages $m_1$ and $m_2$ in that order, $Q$ cannot receive $m_2$ before receiving $m_1$.

I would like to see how it breaks if I remove that First-In-First-Out condition and allow reordering. The only counterexample I was able to built uses two processes who want to acquire the shared resource:

$P$ starts with clock 10 and sends request $m_1$ to $Q$
$Q$ starts with clock 1 and sends request $m_2$ to $P$
$Q$ receives request $m_1$ with timestamp 10 and sends acknowledge message $m_3$ to $P$
$P$ receives message $m_3$ before $m_2$ and enters critical section. As  far as $P$ is concerned, it's the only process wanting the resource
$P$ receives message $m_2$ and responds to $Q$ with acknowledge
$Q$ enter critical section as $Q$'s request has timestamp 1 and $P$'s request has timestamp 10, so $Q$ has priority

However, that requires $P$ to respond to $Q$'s request $m_2$ while in critical section. Otherwise, $Q$ will receive acknowledgment when $P$ is no longer in critical section and there will be no conflict.

Question being: how to construct a counterexample where processes do not respond to external messages while in critical section?


texts: How does "language" relate to "problem" in complexity theory?

texts:
I am looking up the meaning of reduction in complexity theory:

On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem

On the Princeton's notes on NP-Completeness, it says: reduction is whereby given all x $\in $ language L1, for instance f(x) $\in$ L2, apply decision algorithm to f(x), then L1 $<=$ L2

Can someone make clear how a language (which is just a bunch of numbers) relates to a problem? If they are used interchangeably, can someone show how does I can conceptualize a language as a problem?

Thanks