Distinct Binary Heaps I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.

My analysis : I started with $n$ distinct elements. Since root is fixed( maximum element) we can choose $l$(found using deducting total elements from elements in penultimate level) from remaining $n-1$ elements and recursively choose for Left Sub-tree and Right Sub-tree.

Recurrence Relation :

  $T(n)={n-1 \choose l} * T(l) * T(r)$

Now for $n-1$ distinct elements(given), for root we have $2$ options i.e. maximum elements and we can recurse as above for left and right sub-tree. But since the repeated element is also there I am not able to figure out exact way to do so.

Eg: $A=[2,6,6] =>$
There are 2 distinct max heaps $ => [6,2,6] , [6,6,2]$

I am unable to think of the way to find out the number of max heaps in this case. Can someone think of algorithm/recurrence relation to find so ?

If the duplicate element is the maximum element, the answer is the same as when all numbers are distinct. Let's say the duplicate element is $a_1, a_2$. Even though they are the same, we can treat it as $a_1 > a_2$, and then remove the duplicate heaps where the only difference is the exchange of $a_1, a_2$, but that is not possible because $a_1$ is always at the root. So no duplicates found.

If the duplicate element is the minimum element, the problem gets more interesting. Let $S(n)$ be the number of max heaps such that the minimum element is duplicated, and $T(n)$ be the number of max heaps such that there are no duplicates. We already know that

$$T(n) = {{n-1}\choose {l}} \times T(l) \times T(r)$$

with base case $T(1) = 1$.

For the duplicate case, we have 3 cases. We can put them both into the left subtree, both into the right subtree, or one in each subtree. Hence, the recursion is

$$S(n) = {{n-3}\choose {l-2}} S(l) T(r) + {{n-3}\choose {r-2}} T(l) S(r) + {{n-3}\choose {l-1}} T(l) T(r)$$

with base case $S(1) = 0, S(2) = 1, S(3) = 1$.


Why F-bounded polymorphism and F-bounded quantification are called, well, F-bounded It's claimed in Wikipedia that:

  F-bounded quantification or recursively bounded quantification,
  introduced in 1989, allows for more precise typing of functions that
  are applied on recursive types. A recursive type is one that includes
  a function that uses it as a type for some argument or its return
  value

Here's the article which Wikipedia refers to, and F-bounded quantification is introduced in that article in following fashion:

  F-bounded  quantification  is  a  natural  extension  of bounded
  quantification  that  seems particularly  useful in  connection  with
  recursive  types.

My question is - why though it's F-bounded, what does "F" stands for in this particular context?

It appears that "F" does not stand for anything in particular: rather, it is the metavariable symbol that is used in the definition of F-bounded quantification. In the paper in which F-bounded quantification was introduced, F-Bounded Polymorphism for Object-Oriented Programming, the authors write:

  To solve this problem and related difficulties with other forms of recursive types we introduce a generalization of bounded quantification which we call F-bounded quantification, for want of better terminology.

suggesting that they do not view the name as particularly descriptive. Later, when they define F-bounded quantification explicitly, they write:

  We say that a universally quantified type is F-bounded if it has the form
  $$\forall t \subseteq F[t] . \sigma$$
  where $F[t]$ is an expression, generally containing the type variable $t$.

As far as I can tell, the paper contains no other explanation and the most apparent explanation is that the "F" in the terminology is chosen to coincide with the symbol $F$ chosen, arbitrarily, for the definition.


Proof of $f(n) + ο(f(n)) = \Theta(f(n))$ Can you please help me prove this? I am trying to set $o(f(n))= g(n)$ and then try to solve the equation $f(n) + g(n) = \Theta(f(n))$ but I don't know if it is the correct way, and if it is I don't know how to continue my solution. Thank you

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$.
Actually, in the same way you can easily prove also this stronger claim: $f(n)+O(f(n))=\Theta(f(n))$.

If $h(n)=o(f(n))$, then $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$, so there exists $n_0$ such that for all $n\geq n_0$ you have $h(n)\leq f(n)$ (actually, we can prove a stronger statemen, namely that for all $\varepsilon>0$, we have $h(n)< f(n)$, but here we not need it). This means that for all $n\geq n_0$ you also have $f(n)+h(n)\leq 2f(n)$, and then $f(n)+h(n)=O(f(n))$.

If you don't want to explicitely assume positiveness of the functions involved; I suggest to use limits (I like limits).
Remember that $f(n)=O(g(n))$ means
$$
\limsup_{n\to+\infty} \frac{|f(n)|}{g(n)}<+\infty
$$
while
$f(n)=\Omega(g(n))$ means
$$
\liminf_{n\to+\infty} \frac{|f(n)|}{g(n)}>0
$$
(use $|g(n)|$ instead of $g(n)$ if you want to take into account also negative functions). Notice that I'm not assuming that $\lim_{n\to+\infty} \frac{f(n)}{g(n)}$ exists, indeed $\liminf$ and $\limsup$ are used to deal with this case.
Now, as above, let $h(n)$ be an $o(f(n))$, e.g. $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$.
Finally
$$
\limsup_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}<\limsup_{n\to+\infty} \frac{|f(n)|+|h(n)|}{|f(n)|}=\limsup_{n\to+\infty}\left( 1+\frac{|h(n)|}{|f(n)|}\right)=1<\infty
$$
while
$$
\liminf_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}=\liminf_{n\to+\infty} |f(n)|\cdot\frac{\left|1+\frac{|h(n)|}{|f(n)|}\right|}{|f(n)|}\geq 1>0.
$$
Also observe that in the first limit, we only need $\limsup_{n\to+\infty} \frac{|h(n)|}{|f(n)|}$ to be finite, so $h(n)$ can be also a $O(f(n))$.


Closure properties of non-context-free languages (concatenation & complement) I am trying to proof the properties of the complement and concatenation of two non-context-free languages $L_1$ and $L_2$.
I believe that both of these languages are closed under complement and concatenation but can't seem to find a solid proof for it. I'm leaning towards them being closed because I can't find any counter examples.
I already proved that non-context-free languages are not closed under union and intersection, so I can use those properties (if applicable).

So in short what I want to proof, given $L_1, L_2$ are non-context-free languages:
$L_1L_2 \in S_{nonContextFree}$
$\overline{L_1} \in S_{nonContextFree}$

As for closure under complementation -- consider the following hint: context-free languages are not closed under complementation.

Regarding concatenation, this is slightly more tricky, but non-context free languages are not closed under complementation.

There are many ways of finding counterexamples for the latter, one is the following "trick":

Let $L$ be some non-context free language over some alphabet $\Sigma$, that does not contain $0,1$. Now define two languages: $A=(1\cdot \Sigma^*)\cup (0\cdot L)\cup \{\epsilon\}$ and
$B=(0\cdot \Sigma^*)\cup (1\cdot L)\cup \{\epsilon\}$

It is not hard to prove that neither $A$ nor $B$ are context free, basically due to presence of $L$.

However, we have that $A\cdot B=\{0,1\}\cdot \Sigma^*\cup \{\epsilon\}$, which is regular (and in particular context-free).


Type inference in compiler is context sensitive? Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler with this feature? How is it done in popular programming languages like C?

The context that is needed tells us the types of known variables. Suppose We want to infer the type of

if b or 2 = x then a else b

To make sense of this we need to

Check that the type of b is bool
That the type of x is numeric
That a and b have the same type.

To answer these three questions, we look up information about variables in a typing context, which is a mapping from variables to their types. Furthermore, the result is context-sensitive, as the type of the whole expression is the type of a (and b), which is given by the information in the context.

Now you are also mentioning grammars. These are not really relevant here, because we are talking about a stage of compilation which comes after parsing. I think you just got confused by the word "context" being used outside of the subject of grammars. Or you are reading a very strange book. By the way, there is a reason scientists want other scientists to give precise references to their sources. So instead of saying "I read a compiler book", you should have given the author and the title. Now I am just guessing.


Efficient Algorithm to Find the n-th Odious Number An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script is also wanted, but I can write it myself once the algorithm is found.
More description can be found on formula section in OEIS: A000069.

Here is the recursive formula for odious numbers,
$$\begin{align}
a_1&=1,\\
a_{2n} &= 6n-3 -a_n,\\
a_{2n+1} &= a_{n+1} + 2n.
\end{align}$$
The formula can be proved easily by observing, as greybeard pointed out, there is exactly one odious number among $2k-1, 2k$ for all positive integer $k$.
Here is a simple algorithm in Python to compute the $n$-th odious number.
def odious_number(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 3 * (n - 1) - odious_number(n // 2)
    else:
        return odious_number((n + 1) // 2) + n - 1

if __name__ == "__main__":
    for i in range(1, 16):
        print(odious_number(i), end=", ")
    # Output: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28,

There is also a "closed" formula.
$$a_n = 2n - 1 - \text{hamming_weight}(n - 1)\ \%\ 2$$
So, we have the following one-liner.
def odious_number(n):
    return 2 * n - 1 - (n - 1).bit_count() % 2

 int.bit_count(), which returns the Hamming weight of an integer, is available since Python 3.10. Before that version of Python, we can use, for example, bin(i).count('1').


What is the difference between Transitive Closure and Join? In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?

No, it is not. Transitive closure is the closure of composition on binary relations; composition can be expressed as a rename (to make join operate on the right attributes), followed by a join, followed by a project to remove the common attributes.

So composition can be expressed in terms of join, but (as Erwin Smout says) its transitive closure can not, and join (or composition) cannot be expressed in terms of transitive closure, either.


What is the difference between "deadlock prevention" and "deadlock avoidance" I have studied about both of these on many places like this, this and this, but still it is not that much clear that what the actual difference is between these two.

The Wikipedia links (first and second links mentioned above) say about deadlock prevention that:

  The hold and wait or resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations)...

and the deadlock avoidance section of the same page says:

  Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources, such as which resources a process will consume in its lifetime...

so almost in both of these situations we require the processes to provide information about resources in advance.

So can anyone kindly explain in easy-to-understand words that what the actual difference is in between both of these.

It seems that deadlock prevention and deadlock avoidance are two names for the same concept. Indeed, the Wikipedia section on deadlock avoidance has been marked as redundant. While the distinction might be taken from the literature, some people at least are arguing that this distinction is superfluous. See the paper The classification of deadlock prevention and avoidance is erroneous by Neumann Levine, which is mentioned in the Talk part of the Wikipedia article.


NP Problem definition – verifiable on DFA vs. solvable on NFA So in complexity theory, I've run across different definitions for NP problems --

Decision problems where a solution can be verified by a DFA in polynomial time
Decision problems where a solution can be found by an NFA in polynomial time

Is there one of the above that is generally more accepted as the "go-to" definition in the academic community? If so, is there a reason? (If these "definitions" are incorrect – please feel free to correct me).

To me, the second definition makes more sense intuitively.

First, let me correct you: instead of a DFA there should be a deterministic Turing machine running in polynomial time, and instead of an NFA there should be a non-deterministic Turing machine running in polynomial time.

As you mention, both definitions are equivalent, and for this reason there is no single "go to" definition – you can use whatever definition is more appropriate in any single case.

Any formal development of complexity theory would necessitate picking one of these and then showing that the other is equivalent, but this is best left to the developers of these formal frameworks.

There are in fact many variants of Turing machines, so there are more than two definitions of NP. Even more equivalent definitions are provided by other models of computation such as RAM machines. Since all these definitions result in the same complexity class, they are all equally well definitions of NP.


Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem? Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$:

$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n} $$

In human language, what does non-polynomial difference mean? Why was $n/\log n$ compared to $n^{\log_ba}$ in the first place?

In addition, what happens if I replaced $n/\log n$ with $n/\log^*n$, where $\log^*n$ is the log-star function. Would a similar type of analysis take place?

A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply the master theorem.

Case 2 states that if $f(n) = O(n^{\log_b a} \log^k n)$ for some $k \geq 0$ then $T(n) = O(n^{\log_b a} \log^{k+1} n)$. In our case we can choose $k = 0$ and obtain the bound $T(n) = O(n\log n)$. If we also had $f(n) = \Omega(n^{\log_b a} \log^k n)$ then $T(n) = \Omega(n^{\log_b a} \log^{k+1} n)$, but this doesn't hold in our case.

Case 1 states that if $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = O(n^{\log_b a})$. In our case $c = 1$ so this case doesn't apply.

Case 3 states that if $f(n) = \Omega(n^c)$ for some $c > \log_b a$ then $T(n) = \Omega(n^c)$. In our case $c < 1$ so this case also doesn't apply.

Summarizing, the master theorem only gives the upper bound $T(n) = O(n\log n)$. We trivially have $T(n) = \Omega(n/\log n)$, but this doesn't match the upper bound.

We can determine the exact asymptotics using the Akra–Bazzi method. In our case $p = 1$ and $g(x) = x/\log x$, so $T(n) = \Theta(n(1+G(n))$ where
$$ G(x) = \int_1^x \frac{g(u)}{u^2} \, du = \int_1^x \frac{du}{u\log u} = \log\log x. $$
(Formally, we have to change the lower bound of the integration from $1$ to $e$.) We conclude that $T(n) = \Theta(n\log\log n)$.


Time complexity of minimizing Boolean expression Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used.

The following Wikipedia article only talks about the space complexity of the problem (which is PSPACE), but does not talks about the time complexity.

https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions

The Wikipedia article states that the problem is $\Sigma_2^P$-hard, and in particular it's NP-hard. Therefore it's probably not solvable in polynomial time (unless P=NP).


Is the Projection Matrix estimated using least-squares pose specific? I am calibrating a camera and estimating the projection matrix using the least-squares technique described here.

So far, I thought that the projection matrix that I got with this method was invariant, e.g., I could use it disregarding if the camera was moved or not.

However, I have been doing some additional reading, and I came across a set of slides that led me to believe that, if the camera is moved, then I'd have to estimate the projection matrix all over again.

Can someone please clarify this?

Thank you.

Yes, that is correct.  If you move the camera, the projection matrix changes.

However, fortunately you don't have to start from scratch.  If you know the new position of the matrix relative to the old one, you can adjust the projection matrix.  Or, if you don't know how the camera has moved, you'll need to re-estimate the extrinsic parameters, but the intrinsic parameters will remain unchanged (the projection matrix is the composition of an intrinsic matrix and an extrinsic matrix, and only one depends on the camera's position).

See https://en.wikipedia.org/wiki/Camera_matrix and https://en.wikipedia.org/wiki/Camera_resectioning.


How to simplify context free grammars? How to simplify this context-free grammar?
$$
S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b
$$

Can the simplification result in this CFG?

$$
S \to AC \\ S \to A \\ A \to a \\ C \to E \\ E \to b
$$

Starting point:
$$
S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b
$$
Substitute values of $A,B,E$:
$$
S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b
$$
Substitute values of $D$:
$$
S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon
$$
You can generate $bb$ from $C$ even without the rule $C \to bb$:
$$
S \to aCC \mid aCb \\ C \to bC \mid \varepsilon
$$
You can generate $b$ from $C$:
$$
S \to aCC \\ C \to bC \mid \varepsilon
$$
The language of $C$ is $b^*$, so $CC$ generates exactly the same words as $C$:
$$
S \to aC \\ C \to bC \mid \varepsilon
$$

The grammar generates the regular language $ab^*$.


Strings which are not in a language generated by a Grammar I have the following question and its solution

Here  T -> XTX
since T -> X and X->b
      S ->XbX
since X->a
      S->aba

So,why is option 3 not accepted ?

Read the question again, this time focus better. Take the grammar of the question, not the grammar in your mind.

I only need to see the rules for S to know that the strings in (3) are not part of the language.

S is the start symbol. Look at the rules for S. Think why I'm saying that aba and aa cannot possibly be in the language, without me having to look at any other rules whatsoever. You should be able to say "Looking at the rules for S, it is obvious that all strings in the language either xxx or yyy".


Types of reductions and associated definitions of hardness Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. The types of reductions:

Turing reduction: $M_{A}$ can make multiple queries to $O_{B}$.
Karp reduction: Also called "polynomial time Turing reduction": The input to $O_{B}$ must be constructed in polytime. Moreover, the number of queries to $O_{B}$ must be bounded by a polynomial. In this case: $P^{A} = P^{B}$.
Many-one Turing reduction: $M_{A}$ can make only one query to $O_{B}$, during its the last step. Hence the oracle response cannot be modified. However, the time taken to constructed the input to $O_{B}$ need not be bounded by a polynomial.
Equivalently: ($\leq_{m}$ denoting many-one reduction)

  $A \leq_{m} B$ if $\exists$ a computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

Cook reduction: Also called "polynomial time many-one reduction": A many-one reduction where the time taken to construct an input to $O_{B}$ must be bounded by a polynomial.
Equivalently: ($\leq^{p}_{m}$ denoting many-one reduction)

  $A \leq^p_{m} B$ if $\exists$ a poly-time computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

Parsimonious reduction: Also called "polynomial time one-one reduction": A Cook reduction where every instance of $A$ mapped to a unique instance of $B$.
Equivalently: ($\leq^{p}_{1}$ denoting parsimonious reduction)

  $A \leq^p_{1} B$ if $\exists$ a poly-time computable bijection $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

These reductions preserve the number of solutions. Hence $\#M_{A} = \#O_{B}$.

We can define more types of reductions by bounding the number of oracle queries, but leaving those out, could someone kindly tell me if I have gotten the nomenclature for the different types of reductions used, correctly.
Are NP-complete problems defined with respect Cook reduction or parsimonious reduction? Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

If I am not wrong, the class #P-Complete is defined with respect to Karp reductions.

Your definition of parsimonious reductions is incorrect. You are confusing it with polynomial-time one-one reductions which is a special case of Karp reductions. They don't preserve the number of "solutions". Please see this answer for more about reductions considering the number of certificates.

The rest seems fine although it is usually better to view them in a two dimensional chart:

the complexity of reduction: computable, polynomial time, logarithmic space, etc.
type of access: Turing, many-one, one-one, etc.

  Are NP-complete problems defined with respect Cook reduction or parsimonious reduction?

$\mathsf{NP}$ hardness and completeness are defined w.r.t. Karp reductions (polytime many-one), not Cook nor parsimonious reductions.

  Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

Take the complement of SAT, it is complete for $\mathsf{NP}$ under Cook reductions, it is not believed to be complete for $\mathsf{NP}$ under Karp reductions. Karp reductions include polytime one-one reductions.

  the class #P-Complete is defined with respect to Karp reductions

Note that $\mathsf{\#P}$ is not class of decisions problems, it is a class of function computation problems. Its hardness and completeness are usually defined w.r.t. Cook reductions (polytime Turing). See e.g. Arora and Barak, page 346.


detectEigenFeatures with polygon ROI I am using detectEigenFeatures in the Matlab command to obtain the corner points. This function only can provide the corner points within a rectangular boundary region. But I want to extract the corner points within a polygon. I have thought about using small rectangles in order to obtain a polygon. But it seems time-consuming.

Find the bounding box of the polygon.  Find all corner points within the bounding box.  Iterate over the resulting corner points, test each one to see whether it is within the polygon, and if not, throw it away.

Or, implementing your own code to do corner point detection.


Simplifying the boolean expression xy + (!x)z + yz with boolean algebra? So using K-maps I was able to simplify xy + (!x)z + yz to xy + (!x)z, and I double-checked that the truth tables are the same.
I'm having trouble understanding how I would have used boolean algebra to get this result. I tried my usual tricks of adding zero, letting addition distribute over multiplication, etc., without avail.
Any thoughts appreciated.
Thanks.

$$
xy + \bar{x} z + yz =
xy + \bar{x} z + (x+\bar{x})yz =
xy + \bar{x} z + xyz + \bar{x}yz =
xy(1 + z) + \bar{x} z(1 + y) = xy + \bar{x}z.
$$


rolling around running numbers I'm numbering generated files with two digits 00-99 and I want to retain the last 50.
The algorithm should tell me the number of the current file that I'm about to save and which of the previous files to remove.

If I scale it down to a toy version with one digits, here's how I want it to behave.

As long as there are fewer than 5 files, we can just add files.
This is represented in the first block below.
Once there are 5 previous files, the oldest one should be deleted.
This is trivial as long as we haven't reached the maximum number, here 9. This is represented in the second block below.
Once the highest numbers has been reached, the numbering should roll around, and here is where things get tricky. See the third block below.

__prev__    __curr__   __drop__
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

0 1 2 3 4      5          0
1 2 3 4 5      6          1
2 3 4 5 6      7          2
3 4 5 6 7      8          3
4 5 6 7 8      9          4

5 6 7 8 9      0          5
6 7 8 9 0      1          6
7 8 9 0 1      2          7
8 9 0 1 2      3          8
9 0 1 2 3      4          9

Some pseudocode to illustrate my progress:

if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

... and this is where I'm stuck. I've experimented with subtracting 10 from each element in prev.

I'm sure it's trivial and that It'll hit me when I least expect it. I also have a nagging feeling I'll find an expression that generalizes both cases (with and without max in prev).

What you have been trying to implement is a first-in-first-out(FIFO) fixed-sized data structure, which is commonly called a circular queue, circular buffer, cyclic buffer or ring buffer.

In addition to the requirement of circular queue, you want the numbers rolling around an interval such as from 0 to 99. Since all the numbers in use are contiguous, it is enough to use just two numbers, the smallest of them and the largest of them to represent them.

In fact, since the number of files is a constant once the maximum number of files have been reached, it is enough if we keep track of the count of all numbers ever used. So we can construct a much simplified special implementation of the circular queue.

Similarly to your code, we should use the modulo technique. Here is a simple and fully-working Javascript implementation. Both get operation and update operation runs in $O(1)$.

// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

The above implementation works for all possible integer pairs limit >= maximumKept. In particular, it works even if limit is maximumKept.

Here is a sample usage:

function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());


How does Knuth measure the running time of this program? I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand for the number of times around the loop, and where instruction fetch and memory accesses cost one unit, so for example $r2\gets m$ costs two units because it's an instruction fetch, and you need to fetch $m$ from memory.

My question is what does $a$ mean in these equations? How can the instructions associated with the not found label execute more than once, rather than $a$ times? Given the nondeterminism of whether you'll execute the not found instructions depending on the contents of $A$, I can expect there's a special way of dealing with it in the analysis, but I don't follow him in the paper where he claims the total running time based on this analysis is $6n+10$. He says (+ 3 if not found), implying that $a$ is $1/2$, but using that assumption, the total sum comes out to $6n+8.5$, (+3 if not found). Is this some common notation I'm missing? No where in the paper is $a$ defined.

Knuth's $a$ is not standard notation. Here it's just a flag which is $0$ if the element was found and $1$ if it wasn't found. When I sum the elements in his table I get $6n + 10 + 3a$, so it's $6n + 10$ if the element is found and $6n + 13$ if it's not found (which is $3$ more).


How exactly Hashing performs better than a Binary Search? The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see that log n, when n is around 30 million, is roughly equal to 25.

If for such a large value of n, log n is just 25, then isn't O(log n) roughly the same as O(1)? Because O(1), basically means that the time complexity is constant. So, it could be bigger than or same as 25!?!(here I am assuming that the coefficient of log n, in the actual time usage/consumption function for Binary Search, is less than or equal to 1)

A related question I have, is regarding the calculation of time complexity of a hash algorithm. In all the literature, I barely find any mention of the time complexity of the hash function used and the division required thereafter(to calculate the index of the bucket).

So, exactly how do memory reads/access and computing a fairly complex mathematical operation(as in hash function), compete against each other, w.r.t. time consumption? One memory read/access roughly equates to what kind of basic mathematical operation, in terms of performance?

You are asking excellent questions!

The answer to your first question, regarding the difference between $O(\log n)$ and $O(1)$, is that whereas binary search scales with the size of the array, searching for an item in a hash table scales with the size of the data item, which we often think of as constant. In practice, calculating the hash also takes time (as you also mention), and so to know which data structure has better performance, we need to empirically compare implementations of both data structures.

The answer to your second question, about the time complexity of computing the hash function, is that it takes time linear in the size of the data item. Most hash functions used in this context are "rolling hash", in which a small has value is being updated as the data item is read. This ensures that the time complexity is indeed linear. Hash functions for such uses are designed with speed in mind, and so usually memory access is not an issue. The division operation at the end – if at all – is not too costly for modern CPUs, and can be avoided entirely if the size of the hash table is a power of 2.


What is the best algorithm for multiple matches? What is an algorithm that can find the best possible matches given a set of data. I have read up on stable roommates problem and or stable marriage problems. However, from my understanding, these type of algorithms only output a specific match (pairings) and not a set of possible matches. For example, say we have a group of users each with a desire to trade one particular fruit for another.

[] - Has/Have
() - Wants

User 1:
[Apples, Bananas]
(Grapes)

User 2:
[Bananas, Grapes, Peaches]
(Apples)

User 3:
[Grapes, Oranges]
(Bananas)

User 4:
[Mango, Pineapple]
(Strawberry)

User 5:
[Raspberry]
(Pineapple)

User 6:
[Pineapple]
(Raspberry)

In this scenario, matches should be (->)

     User 1 -> (User 2 and User 3)
     User 2 -> (User 1)
     User 3 -> (User 1)
     User 4 -> None
     User 5 -> (User 6)
     User 6 -> (User 5)

Irving's algorithm requires that a solution have a unique pairing. What is an algorithm that could give me a solution set like above?

Use an algorithm for bipartite matching.

Build a graph with one left-vertex per (user, fruit that user has) pair.  For instance, in the example above, we'd have one vertex for (User 1, Apples) and another vertex for (User 1, Bananas).  Add one-right vertex per user.  Draw an edge from (user $i$, $f$) to user $j$ if user $i$ has fruit $f$ and  user $j$ wants fruit $f$.

Now find a maximum matching in this bipartite graph.  The set of edges in that matching will be exactly what you want.

This does allow one user to be matched to multiple other users: for instance, the vertex (User 1, Apples) might be matched to the vertex User 2, and the vertex (User 1, Bananas) might be matched to the vertex User 3.


Check if given language is CFL Assume language $L$ as follow:-
$$
L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\}
$$
Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. But is it possible with "or"?

My approach:- 1. Push all $a$'s to the stack.

At $b$ define non deterministic behavior as follow:-

2.1. Assume we are checking for $n=m$.So skip all the $b$'s.

2.1.2.Whenever $c$ is encountered, pop $a$ for $c$.

2.1.3. When $d$ is encountered check if stack is empty, if yes, then accept else reject.

2.2. Assume we are checking $x=y$. So push all the $b$'s to the stack. Now when $c$'s are  encountered skip them.

2.2.1. When $d$'s are encountered, count them with $b$'s which are on top of stack.

2.2.2. When input is finished and stack is empty or contains only $A$, then accept else reject.

Note that
$$
L = \{ a^n b^x c^n d^y : n,x,y \geq 0 \} \cup \{ a^n b^x c^m d^x : n,m,x \geq 0 \}.
$$
Try showing that each of these is context-free individually.


What is the relationship between tail recursion with other recursions? I'm rather confused by the recursion theory.

From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But where is tail recursion? can this concept parallel to these concepts? what else concept goes parallel to tail recursion?

 1.1 The Initial Functions
 1.2 Iteration
 1.3 Primitive recursion
 1.4 Primitive recursion with parameters
 1.5 Course-of-value recursion
 1.6 Double recursion
 1.7 Minimization (least search)

We need to distinguish two things:

Tail-calls are calls to functions that are made in tail position. Tail-recursion is a recursive tail-call.
Tail-call optimization is the process by which tail-calls are turned into loops or GOTOs in compilers.

The second, as others have stated, is an implementation detail that falls in the theory of compilers, and isn't really recursion theory.

However, it is absolutely possible to study tail calls in the context of computability. In particular, there is something called Continuation Passing Style.

There exist CPS-transformations which can turn any lambda-function into one in continuation passing style. So the set of languages computed using only tail-calls is equivalent to the set of recursively-enumerable languages.

CPS has many applications in the theory of programming languages, and the concept of tail recursion is useful for more than just the tail-call optimization.


When does a Monte Carlo algorithm solve a problem? When can we say that a Monte Carlo algorithm solves a problem?

To quote from Wikipedia on Monte Carlo algorithms

  For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least ½ and true with probability less than ½.

What would happen if the Solovay–Strassen Test would answer true for only 1% of composite inputs?

Would we then still say that it solves the problem of testing primality?

Or is there some requirement like that a Monte Carlo algorithm has to answer true for more than half the cases?

In general Monte Carlo is used to solve a wide variety of different types of problems. In this particular case you want to learn if a random variable is the constant 1, or not. The idea is straightforward, sample the random variable multiple times, (each sample independently from previous sample to avoid bias) and check if all results were 1. If at least some of the result was 0, we know for sure the random variable is not constant 1 (in Solovay-Strassen Test context, the number is composite).

It is important to emphasize, since Monte Carlo is a randomized algorithm, that it is said to solve the problem if the probability of returning the wrong answer is below some threshold (a small number we will call $\epsilon$).

What happens if all outcome were 1? There is a chance that it is the constant 1, but also there is a chance we were not lucky and all outcome were 1 when they can also be 0. If the probability of sampling a 1 is $p < 1$, then after $n$ samples the probability of getting all 1 is $P_n = p^n$. Note that while $n$ increase $P_n \rightarrow 0$. We can specify a threshold, let's say $\epsilon = 10^{-10}$, such that if $P_n < \epsilon$ (i.e. the probability of having a false positive is less than $\epsilon$) we are ok with that result.

Now the answer to your question. $\forall p < 1, \epsilon > 0 \space \exists n \space p^n < \epsilon$. What is this telling you exactly?

Whatever the success probability is, as far as it is less than $1$ (for example $p = 0.99$ or $p=0.01$ or $p=0.5$) and threshold $\epsilon$ there exist an $n$ such that if we run the experiment $n$ times (sample $n$ times the random variable independently) we are going to fail with probability at most $\epsilon$. So Monte Carlo can be applied for non-degenerated values of $p$, just the number $n$ of sample must be adjusted to satisfy the $\epsilon$ threshold requirement.


PCAs and Kleene's Recursion Theorem I might need some help with the following question.

Given a Partial Combinatory Algebra, we can define the fixed point combinator $Y := [\lambda^{*}xy.y(xxy)][\lambda^{*}xy.y(xxy)]$. How does this relate to Kleenes recursion theorem, aka. fixed point theorem?

In the setting of Kleenes first PCA, ie. the PCA of computable functions on $\mathbb{N}$, given a (partial) computable function $f = \varphi_c$ the fixed point combinator satisfies $Yc = c(Yc)$. As I understand it this means that taking d := Yc it translates to $f(d) = \varphi_c(d) = cd = d$, ie. $f$ having a fixed point.

However Kleene's recursion theorem originally gives a weaker assertion, namely that for every total computable function $g$ there is some $n$ such that $\varphi_{g(n)} \simeq \varphi_n$ (cf. Odifreddi - Classical Recursion Theory, Theorem II.2.10).

This really confuses me and I couldn't make up my mind what to do about it. I hope someone can help me out. Anyway, thank you for your time.

As I understand it this means that taking $d := Yc$ it translates to $f(d)=φ_{c}(d)=cd=d$, ie. $f$ having a fixed point.

Not every recursive function has a fixed point in the sense of $f(n)=n$ - for example, $f(n)=n+1$. Therefore, there must be something wrong with this proof. As noted in comments, this proof works only if $d=Y c$ is defined.

As you've noticed, you can work around this issue by using a variant of the Y combinator:

  Just taking Ycc′=c(Yc)c′ doesn't seem to make your problem any better

But it does! To avoid confusion, I'll call this combinator Z. We have

$Zcc′=c(Zc)c′$.

Let's take a function $f=\varphi_c$ and let $d = Z c$, just like in the previous proof. Now, $d$ is guaranteed to be defined. We have

$d c' \equiv c d c'$

By the definition of application in the Kleene's first algebra this means:

$\varphi_{d}(c')$ $ \simeq \varphi_{\varphi_{c}(d)}(c')$

$\varphi_{d}(c')$ $ \simeq \varphi_{f(d)}(c')$

$\varphi_{d}$ $ \simeq \varphi_{f(d)}$

which is the Kleene's recursion theorem.

  Well, literally the same problem arises in the proof of the Recursion theorem in Odifreddi's Classical Recursion Theory, Theorem II.2.10. There he takes $b$ to be a code satisfying $\varphi_{b}(e) \simeq f(\varphi_e(e))$.

No, $b$ is defined in Theorem II.2.10 using the equation:

$\varphi_{\varphi_{b}(e)} \simeq \varphi_{f(\varphi_e(e))}$

Importantly, $b$ is a code - it is a well-defined natural number that encodes a specific program. Furthermore, for every $e$, $\varphi_b(e)$ is also a code - it is not the result of running $f(\varphi_e(e))$, it is merely a code of a function which given $n$, runs the function $\varphi_{f(\varphi_e(e))}$ on $n$. (This difference mirrors the difference between Y and Z combinators.)


Vectorization vs Asynchronous parallelism I have taken a course "Programming for Performance" in my college and in the first week of the course, I have come across vectorization and Asynchronous Parallelism. But I am unable to figure out what is the relation and difference between the 2 of them. In the slides, the professor has provided something like this-->

What does it actually mean that parallelism is finer-grained and course-grained?
Also here is another instance where he has tried to point out the difference, here we are given 2 code instance and tried to explain the concept, but I am not able to get that.

What I got is that, in the first one both vectorization and asynchronous parallelism is not possible, since there is a data dependency, but in the second one vectorization can be done as there is no dependency, but asynchronous parallelism is not achievable since, say we have this 2 instances
A(1) = A(2) + B(2) |  A(2) = A(3) + B(3)
So in this case the A(2) may get overwritten by the second instance even before the 1st instance of the code is executed, hence Asynchronous Parallelism is not possible.
Is my understanding of this right?

Vectorization and asynchronous parallelism are not exactly comparable. Its like comparing apple and orange. Have a look at Difference between parallel, concurrent and asynchronous.
Vectorization uses the support for different vector instruction in modern processors. For e.g. Intel support AVX512 and AVX256 instructions. Here 512 and 256 are number of bits. So if the operand are 64 bit double values, the hardware can process 8 or 4 set of operands, parallelly.  Operation(+,-,* ...) are applied on vector inputs (8 or 4 set of operands) instead of (8 or 4 times) on  scalar (single set of operands) inputs.
for(int i=0;i<1000;i++)
for(int j=0;j<8;j++)
c[i][j]=a[i][j]+b[i][j]
On a Intel processor this code fragment will be replaced by vector instructions by the optimizing compiler . So it is equivalent to something like:
for(int i=0;i<1000;i++)  { c[i][0]=a[i][0]+b[i][0] , c[i][1]=a[i][1]+b[i][1], ..., c[i][7]=a[i][7]+b[i][7] }
This require that there should be no dependency among consecutive iteration instructions. All eight addition operation execute in parallel by the vector processing hardware of the processor on eight different operand sets. Granularity in vectorization is at the level of 'instructions'.
Asynchronous operations can happen on even single core systems. For e.g., I/O processing. Yes it is the case that, two or more set of operations happen in parallel, but it is not necessary that both are computation operation. It could a memory operation and computation Or a I/O operation and computation. Granularity in Asynchronous operation is 'set of instructions' like a program or a interrupt vector routine.


Are there 3-colorable maps that can never be colored? I just watched this explanation of zero-knowledge proofs with Avi Wigderson: https://www.youtube.com/watch?v=5ovdoxnfFV
Key claims from the video:

Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

If every formal statement can be translated to a map, and suppose there's a true statement that can't be proven true by Gödel's incompleteness theorems, then doesn't that mean that no algorithm whether P, NP, or worse can exist to color it? Does that mean that there are some 3-colorable maps that can never be colored?
This seems wildly counterintuitive (which maybe is just the nature of Gödels' incompleteness theorems, which I haven't tried to understand the proof of). Or maybe I don't understand Gödel's incompleteness theorems (also likely). If I'm misunderstanding something though, it'd be helpful to know what to look into more.

Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

Every formal statement in propositional logic can be translated to a map 3-coloring instance. The video is being very sloppy with calling this 'every mathematical statement', as there's many mathematical statements that aren't captured in propositional logic.
Propositional logic is decidable (it's equivalent to the SAT problem).


Maximal expansion of a convex polygon There is a convex polygon $X$ contained in another polygon $Z$ (which can be non-convex and even have holes). I would like to expand $X$ to a larger convex polygon $Y$ such that:

$X\subseteq Y\subseteq Z$
$Y$ is maximal, i.e, there is no other convex polygon $Y'$ such that $Y\subsetneq Y' \subseteq Z$

NOTE: $Y$ does not have to have maximum area; it only has to be maximal.

What is an algorithm for finding such $Y$?

Algorithm. We maintain a set $S$, which is initially a set of vertices of $X$. Let $CH(S)$ be the convex hull of $S$. We want to find $S$ such that $CH(S) \subset Z$ is a maximal polygon.
We first define operation $extend(s,t)$ which

Finds a point $x$ on the ray starting from $s$ and going through $t$ such that $CH(S \cup \{x\}) \subset Z$ and $x$ is the farthest from $s$ (i.e. it's the most we can extend the polygon in direction $s \to t$).
Add $x$ to $S$.

$extend$ is the only operation we'll use. Therefore, $CH(S) \subset Z$ by construction. We only need to select a sequence of extensions so that $CH(S)$ is maximal.
The algorithm consists of $2$ phases:

Let $c$ be any point strictly inside the $X$. For each vertex $v$ of $Z$ (including inner vertices), perform $extend(c, v)$
For all edges $(u,v)$ of $CH(S)$, while possible, perform $extend(u,v)$ and $extend(v,u)$.

The following example demonstrates the algorithm (I omit steps which don't modify $S$, but we should try all vertices of $Z$ (including holes' vertices) and all edges of $CH(S)$):

Proof of maximality.

Let $x \in Z$ be a point such that $x \in Z \setminus CH(S)$ and $CH(S \cup \{x\}) \subset Z$.
Let $u \in S$ be a vertex s.t. $(u,x)$ is an edge in $CH(S \cup \{x\})$. We can assume that $x$ is arbitrarily close to $u$. It's clear that when $x$ is sufficiently close to $u$, one of two neighbors of $u$ in $CH(S)$ becomes a neighbor of $x$ in $CH(S \cup \{x\})$. We call this neighbor $v$. Let $u'$ be another neighbor of $u$, and $v'$ be another neighbor of $v$.
Since we can't extend $(v', v)$ and $(u',u)$, there must exist a vertex $y$ of polygon $Z$ lying strictly between lines $(v', v)$ and $(u',u)$ (it's cumbersome to explain, but it's kind of obvious). Then line $(c,y)$ either intersects $(u,x)$ or $(v,x)$. Let $z$ be the intersection point. Then this point 1) lies outside of $CH(S)$, 2) lies in $CH(S \cup \{x\})$ and 3) lies on line $(c,y)$. This means that during phase $1$ we didn't fully extend to $y$, contradiction.
Complexity.
We first need to estimate the complexity of $extend$. One can do this with a binary search: for a candidate, build a convex hull and check if it lies inside of $Z$. The convex hull can be built in $O(n)$ (since we only need to add one point) and an intersection with $Z$ can be checked in $O(n)$, so the total time is $O(n \log (precision))$. I suspect that it's possible to get rid of binary search and get $O(n)$ or $O(n \log n)$ time.
Now, we need to estimate the number of calls of $extend$. There are $O(n)$ calls of $extend$ in the first phase.
In the second phase, each time we successfully perform $extend$ (i.e. the area of $CH(S)$ increases), one of two things happen:

A vertex of $CH(S)$ which was not on the boundary of $Z$, now lies on the boundary of $Z$.
A vertex of $Z$ which was not on the boundary of $CH(S)$, now lies on the boundary of $Z$.

Since there are $O(n)$ vertices of $Z$ and $CH(S)$ (it can't have more vertices than $Z$), we call $extend$ at most $O(n)$ times.
Therefore, the total running time is $O(n^2 \log (precision))$


How to solve for a problem using a primitive function in toc I have been searching on the internet how to multiply a function but I cannot find any. I have only found solution in adding but not in multiplication.

$add(2,3) = s(s(s(add(2,0)))) $

$add(2,3) = s(s(s(I(2))) $

$add(2,3) = s(s(s(2)) $

$add(2,3) = s(s(3)) $

$add(2,3) = s(4) $

$add(2,3) = 5 $

For example, Using the multiply primitive function, how to compute $multiply (5, 3)$.

Does anybody know?

Hint:

You probably have:
$$add(0, n) = n$$
$$add(m+1, n) = S(add(m,n))$$

Now you know the base case for addition is adding zero. What's the base case for multiplication? Multiplying by zero.

$$mul(0,n) = 0 $$

I will not do the last part,because you must do your own homework,  look at your example and the addition definition, the $mul$ function must work like this:

$$mul(3,5) \longrightarrow 5 + 5 + 5 + 0 $$


Functional Programming and Category Theory I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked through most of "Categories for the Working Mathematician" as well as more specialized topics in Homological Algebra). Is there some good intro to functional programming that emphasizes the link with category theory in the process?
Context: In my workplace I've run into people that are into functional programming and like throwing around category theory jargon, but when you ask for details they typically fail to even be able to define what a category is. I'm hoping that there's more to it in programming than just abstract nonsense. In other words, for someone who actually knows category theory and has done some functional style programming (immutable classes, map, filter, reduce etc.) in imperative languages is there a good intro to FP in the context of category theory?

These colleagues of yours, would they happen to be Haskell aficionados?
They might have told you that Hask was a category made from Haskell, but that is a lie, notheless a very useful one that inspires new programming techniques.
If you would like to find out how category theory informs functional programming, I can recommend Bartosz Milewski's Category theory for programmers.
There is also the older Category theory for computer science by Michael Barr and Charless Wells, which is more of a straight introduction to category theory. It might be a good book for functional programmers who only ever learned the bastardized category theory through functional programming.


Are Petri Nets actually used in the industry I'm having a hard time finding any prominent applications of Petri nets in the industry. Can you name some, or are Petri nets still just an academic curiosity?

Petri-nets are e.g. used for Businees Process Modeling with BPMN. Of course Petri Nets are an abstract idea that lends itself to modelling a wide variety of dynamic and/or distributed systems - but especially for business processes, the provable reachability, liveness and boundedness are useful properties.


What is an asymptotically tight upper bound? From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation.
But what does asymptotically tight upper bound mean for Big-O notation?

Saying that a big-O bound is "asymptotically tight" basically means that the author should have written $\Theta(-)$.  For example, $O(x^2)$ means that it's no more than some constant times $x^2$ for all large enough $x$; "asymptotically tight" means it really is some constant times $x^2$ for large enough $x$ and not, say, some constant times $x^{1.999}$.


How to calculate complexity of an algorithm which calls a subroutine? Consider the following example:

Algorithm $A$ has Algorithm $B$ as its subroutine. The running time of algorithm $A$ without counting the time spent running the algorithm $B$ subroutine is $O(n^4)$. One call of algorithm $B$ takes $O(n^3)$ time. In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times.

What is the running time of algorithm $A$ including subroutines?

a. $O(n^4)$

b. $O(n^9)$

c. $O(n^7)$

d. $O(n^6)$

This sentence: "In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times" is vague. If it means in each iteration of $A$, then as each time the calling $B$ takes $10n^2\times O(n^3) = O(n^5)$, we can say $A$ will be run in $n^4 \times O(n^5) = O(n^9)$.

On the other hand, if it means in all round of $A$, it calls $10n^2$ times $B$, as you said the time complexity would be $O(n^5)$.


Do there exist coding languages where the halting problem is solvable but not trivial Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages that don't allow loops, even if finite are right out.

I think I understand what you are trying to ask. But you may have to work
harder on the asking to get a non-trivial answer. As it stands, your question
has a trivial answer. Take a language that always terminate, and add a command
that never terminates and is syntactically constrained to be used first if at
all in a program. To check termination, you only have to check whether the
program contains the non-terminating command.

In some sense, I think you can only have trivial answers. Consider some
language L that meets your definition of halting being decidable, though not always
terminating or always non-terminating. Given the halting decision procedure for L,
we can always change that language L into an almost identical one L' that will
always terminate, though by returning a new special value $\perp$ (read
'bottom'), when language L does not terminate. Now we can look at our
contraption from the other end, and see L as a language derived from the always terminating language L', in a
way that replaces all computations producing a specific result, namely $\perp$,
by an infinite loop. So L is a trivial answer derived from L'.


MTBF calculation with 2 units connected in series Me and a friend have a opinion difference regarding a question that got asked in a previous IT test.

The short version:

2 units, n and m are connected in series but operate as one system. n has a MTBF of 200, m of 300. What is the MTBF of the entire system?

possible solutions:

200
250
300
500

I am convinced (as is the guy who made the question) that the correct answer is 250.

My friend is convinced it is 120 and the question contains a mistake.

How were I to calculate this?

If the MTBF of a device is $N$, then the probability that the device will fail in 1 time unit is $1/N$. With two devices in series with failure probabilities $p_1$ and $p_2$, the system will fail in one time unit if device 1 fails or if device 1 doesn't fail and device 2 fails. The probability of that happening is
$$
p_1 + (1-p_1)p_2=p_1+p_2-p_1p_2
$$
In your problem, $p_1=1/200, p_2=1/300$ so the probability that the system will fail in one time unit is
$$
(1/200)+(1/300)-(1/200)(1/300)=499/60000\approx0.00832
$$
and so the MTBF of the whole system is $1/0.00832\approx120.24$. Your friend is right: none of the proposed solutions are correct.


Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable How would you go about showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable?

Intuitively my thoughts are that you might be able to show that $\bar{L} = \{\langle M, w \rangle\ |\ M$ moves left at most twice while computing $w \}$ is undecidable as you wouldn't ever be able to definitively know if the machine will move left a third time so it would end up looping instead of rejecting. I don't know if that's on the right track though.

Thanks in advance!

I strongly believe it is decidable, but I found it quite convoluted. I'll give a sketch of proof.

Lemma: Every Turing Machine that doesn't terminate either moves left at some point or is very silly.

Let $M_\leftarrow$ be a TM that never moves left. If $M_\leftarrow$ never moves left, we don't care about what it writes on the tape, because it can only ever read the last symbol it wrote. In particular, we may see $M_\leftarrow$ as a finite transition system which set of states are the pairs $(q \in Q, \sigma \in \Sigma)$ where $q$ is the current state of $M_\leftarrow$ and $\sigma$ is either the last symbol written by $M_\leftarrow$ or the blank symbol if $M_\leftarrow$ just moved to the right. Therefore, checking if the graph of the transition system is cyclic decides whether or not $M_\leftarrow$ terminates, qed.

Theorem: $L$ is decidable.

Let $H$ be the problem of deciding whether or not a machine that never moves left terminates. By the lemma above, there exists a machine $M_H$ that takes as input another machine $M$, some input $x$ and:

if $M$ never moves left on input $x$, returns $\textsf{YES}$ if $M$ terminates and $\textsf{NO}$ otherwise,
if $M$ on input $x$ moves left at some point, returns $\textsf{YES}$.

We will show that we can use $M_H$ to construct a family of machines $M_k$ that decides whether or not a machine moves left at least $k$ times. Let $\langle M, x \rangle$ be the input.

First of all, we have $M_k$ construct a universal machine $U$, and use $U$ to compute $M_H$ on input $M$. If the result is $\textsf{NO}$, it means that $M$ never moves left on input $x$: we accept $\langle M, x \rangle$. If the result is $\textsf{YES}$, it means that either $M$ terminates on input $x$ or moves left at some point.

We use $U$ to simulate $M$ on input $x$. After finitely many steps, either $M$ terminates or moves left. In the first case simply accept. If a left move happens, we save the current state of the tape, and return the result of $M_{k-1}$ with the modified tape as input, which is by inductive hypothesis computable, qed.


Assign numbers to letters with respect to lowest graph peaks I have string which is composed of letters. I want to assign each letter a unique number (letters that repeats should have assigned same number as first unique letter occurrence) and plot those numbers on graph. X-axis will represent the particular letters of string (read from left to right) and y-axis will represent the particular value assigned to letter. The problem is that I want to have graph with minimum peaks. String can be long sequence with repeating letters. In other words I need to assign to letters such numbers that will cause that the plot change over time will be minimal.

So basically this is OK:

STRING
123456

But this not, because graph does not grows/decreases continuously and there are peaks e.g. between S-T, T-R, R-I and I-N (actually it fits criteria only for N-G)

STRING
162534

More complicated example: imagine string "STRINGS" and those two possibilities:

##############
# 1s example #
##############

Letter-Number mapping:
######################
STRINGS
6431256

Distances:
##########
S-T:2
T-R:1
R-I:2
I-N:1
N-G:3
G-S:1

Peak changes:
#############
2-1:T
1-2:T
2-1:T
1-3:T
3-1:T

###############
# 2nd example #
###############

Letter-Number mapping:
######################
STRINGS
1356421

Distances:
##########
S-T:2
T-R:2
R-I:1
I-N:2
N-G:2
G-S:1

Peak changes:
#############
2-2:F
2-1:T
1-2:T
2-2:F
2-1:T

Then the winner is 2nd example because it's maximum distance is less than the maximum distance in 1st example. I can imagine situations where both max distances can be same then the criteria should be the peak changes. In this case 2nd also beats 1st (F - does not change, T - change) because 1st is always changing and 2nd does not change in 2/5 cases

1st: TTTTT
vs
2nd: TFTFT

Is there any theory related to this? Is this even CS theory or some genetic algorithm or what problem set is this? Some library that already does this would be fine e.g. for python, perl etc.

PS: Sorry but I did not know which tags or what title describe this problem the best.

This smells like it might be hard (e.g., NP-hard).

Therefore, I suggest solving it with a SAT solver.  SAT solvers implement a number of clever optimizations.  Rather than trying to devise custom optimizations for this specific problem, you might try using an off-the-shelf SAT solver: that might be a much more efficient use of your time.  In particular, here's what I would try.  I would formulate the problem as follows:

Input: a string $S$ with $n$ unique letters, an integer $d$

Question: is there an assignment that maps each letter to a different number in $\{1,2,\dots,n\}$, such that any pair of adjacent letters are mapped to numbers that differ by at most $d$?

You can then formulate this as a SAT instance, in a fairly straightforward way.  For instance, you can use a one-hot encoding: introduce boolean variables $x_{c,j}$, where $x_{c,j}=$ True means that the letter $c$ is mapped to the number $j$.  Now if letters $c,c'$ are adjacent in the string $S$, you get a constraint $\bigvee_{|j-j'|\le d} (x_{c,j} \land x_{c',j'})$.  You also get constraints forcing different letters to map to different numbers.

Finally, throw this to an off-the-shelf SAT solver.  If it finds a solution, you know that distance $d$ is achievable.  Otherwise, it's not: distance $d$ is unattainable.  You can now iterate over $d=1$, $d=2$, $d=3$, etc., until you get the first solution.  (You can also try binary search, but I suspect it might be less efficient.)

This doesn't account for peaks, because I couldn't understand your definition of the peak stuff.


Is there a human-friendly version of the Pumping-Lemma? I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the different notations surrounding logic and quantifier.
$(\forall L \subseteq \Sigma^*)(regular(l)\Rightarrow((\exists p\geq1)((\forall w\in L)$
$((|w|\geq p)\Rightarrow((\exists x,y,z\in \Sigma^\ast )(w = xyz \land(|y|\geq 1\land|xy|\leq p \land(\forall n\geq 0)(xy^nz\in L))))))))$

I agree that the way the lemma is written is confusing, a more friendly way to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more human readable now):
The Pumping Lemma: for every regular language $L\subseteq \Sigma^*$, there is a positive pumping constant $p$ such that for every word $w\in L$ with $|w|\geq p$ (that is, for every long enough word in the language $L$ ), the following holds. There exists a partition of $w$ into three words over $\Sigma$, $w = xyz$,  such that:

$|xy|\leq p$ (that is, $y$ lies in the prefix of length $p$ of $w$).

$|y| > 0$ (that is, $y$ is nonempty).

$xy^iz\in L$, for every $i\geq 0$ (that is, if you take the word $w$ and pump the infix $y$ in $w$, $i$ times, the word $w$ remains in the language $L$).


How to optimally seperate a student body? Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with students from Group 2.

I was thinking about creating a source node s, and creating a node for each person ($p_i$) - followed by hooking up the s to each $p_i$. Then I would create, another series of nodes for each person ($q_i$) and hook up each $p_i$ to each $q_i$ if $p_i$ doesn't want to work with $q_i$. Then, I would hook up each $q_i$ to a terminal node t. Each of the edges would have weight 1.

I was thinking about running Edmonds–Karp on it. Now, the solution would yield the maximum bipartite matching of the group (see e.g. here). For each active arc from $p_i$  to $q_i$ in the final diagram, I would separate those two students.

However, I have a bad taste in my mouth after running this algorithm; the bad taste stems from modeling the instance with respect to my intention: If I maximize the complement (the desire not to work with someone), do I really minimize the desire of students to work with each other across the two groups?

If my hunch is correct (in that I'm wrong), please point me in the right direction.

It sounds like you have properly reduced the maximum bipartite matching problem to the maximum flow problem, all you need is the reasoning to convince yourself why it is true. You are worried about the complement, so let's consider that. Remember that there is a duality among the minimum cut problem and the maximum flow problem so in finding the minimum cut you will equivalently find the maximum flow. For the definition of minimum cut:

  a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.

The minimum cut for the graph you have constructed will have the smallest number of edges since all the weights are uniform and therefore the smallest number of people from the two sets who want to work togethers given that:

$w(p_i, q_j) = 1 \Leftrightarrow$ person $p_i$ does not want to work with person $q_j$


Proving satisfiability using resolution and variable elimination I don't 100% understand this. But I have a entailment, and I want to prove whether it is satisfiable or not, and I will do this using resolution and variable elimination.
Here is the formula:
$$
(x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_5 \lor x_7) \land (\lnot x_4 \lor x_6 \lor x_8) \land ( x_5 \lor \lnot x_6) \land \\(\lnot x_6 \lor x_7 \lor \lnot x_8) \land (x_7 \lor \lnot x_8 \lor \lnot x_{10}) \vDash \lnot(x_7 \lor \lnot x_9 \lor x_{10})
$$
First I negate the conclusion and move it into the premises. If I can prove this to be ⊥ using Resolution, I have proven that the original entailment IS satisfiable. So this is what I want to refute by using resolutin (and variable elimination to simplify).
$$
(x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_5 \lor x_7) \land (\lnot x_4 \lor x_6 \lor x_8) \land ( x_5 \lor \lnot x_6) \land \\(\lnot x_6 \lor x_7 \lor \lnot x_8) \land (x_7 \lor \lnot x_8 \lor \lnot x_{10}) \lor (x_7 \lor \lnot x_9 \lor x_{10})
$$
So I start off by eliminating all clauses with $x_7$ since it's a pure literal, which leaves me with
$$ (x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_6 \lor x_8) \land (x_5 \lor \lnot x_6) $$
Here $x_5$ is a pure literal, so that one clause can be removed.
$$ (x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land (\lnot x_4 \lor x_6 \lor x_8) $$
Now $x_6$ is a pure literal, which would leave just the two clauses
$$ (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) $$
However, here $x_8$ is a pure literal, thus leaving us with only one clause, and that clause contains pure literals. Can it really be simplified into nothing? It feels like I'm doing something wrong but I'm not sure what it is that's wrong.
If I really can simplify into nothing, would that mean that the original formula is satisfiable or not satisfiable?
Since all the clauses contain a pure literal, wouldn't that make it impossible to resolve?

If $x_7$ is a pure literal, then this means that you can satisfy all clauses containing $x_7$ by setting it to true. Accordingly, we set $x_7,x_5,x_6,x_8$ to true, satisfying all clauses apart from $\lnot x_2 \lor \lnot x_3 \lor x_4$, which we can satisfy by setting $x_4$ to true (for example).
If you set $x_4,x_5,x_6,x_7,x_8$ to true, then the left-hand side of your original formula is satisfied (once you correct $x_1 \lor x_2$ to $x_1 \lor x_2 \lor x_6$ and $\lnot x_5 \lor \lnot x_6$ to $x_5 \lor \lnot x_6$), while the right-hand side is falsified, and so the entailment is false. (In contrast to your post, there is no "formula" there which can be satisfied or not.)


To what factor can I compress information from binary to Quinary I am trying to think if we can have an injective mapping $\mathcal{f}$, say something like $\Sigma_{bool}= \{0,1\}^* $ to $\Sigma_{5} = \{0,1,2,3,4\}^* $ such that $|x| \leq 2.|\mathcal{f}(x)|$

The motivation here is simple, consider I have a word $110110110110110110110$, so i can compress and represent that as $(110)^7$ or $110,111$ so what can i do if i am allowed to use symbols from $\Sigma_5$?

I hope my question made sense :)

Here is a simple way to get the inequality $|f(x)| \leqslant {1 \over 2}(|x| + 3)$. Just encode words by blocks of length $2$ using the coding $00 \to 0$, $01 \to 1$, $10 \to 2$ and $11 \to 3$ and add the suffix $40$ or $41$ for the last letter if the length of the word is odd. For instance,
$f(11011000) = 3120$, $f(11011000\mathbf{0}) = 3120\mathbf{40}$ and $f(11011000\mathbf{1}) = 3120\mathbf{41}$.

One can improve this inequality to
$$
  (*) \qquad|f(x)| \leqslant \biggl\lceil{1 \over \log_2 5}|x| + C\biggr\rceil
$$
where $\log_2 5 \approx 2.3219\cdots$ and $c = \frac{3}{\log_2 5}-1 \approx 0.2920\cdots$. Indeed, the number of words of length $\leqslant n$ in $\Sigma^*$ is $\frac{|\Sigma|^{n+1}-1}{|\Sigma|-1}$. Therefore, there is an injection from $\Sigma_2^{\leqslant n}$ to $\Sigma_5^{\leqslant m}$ if and only if
$$
2^{n+1} - 1 \leqslant \frac{1}{4}(5^{m+1} - 1)
$$
which gives $4(2^{n+1} -1) \leqslant 5^{m+1} - 1$, or equivalently, $2^{n+3} \leqslant 5^{m+1} + 3$. This inequality is already satisfied if $2^{n+3} \leqslant 5^{m+1}$, that is, if $n+3 \leqslant (m+1)\log_2 5$. In particular, if you choose $m = \lceil {1 \over \log_2 5}n + C\rceil$, one can build an injection $f$ from $\Sigma_2^*$ to $\Sigma_5^*$ satisfying $(*)$ as follows. Recall that the shortlex (or radix) order is the order $\leqslant$ on $\Sigma^*$ defined by $u \leqslant v$ if and only if $|u| < |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. The shorlex order is a total order on $\Sigma_k^*$ and hence each word $u$ has a rank $r_k(u)$ in this order. For instance, for $k = 2$ you get $r_2(\varepsilon) = 0$, $r_2(0) = 1$, $r_2(1) = 2$, $r_2(00) = 3$, $r_2(01) = 4$, $r_2(10) = 5$, $r_2(11) = 6$, $r_2(000) = 7$, etc. For $k = 5$, you have $r_5(\varepsilon) = 0$, $r_5(0) = 1$, $r_5(1) = 2$, $r_5(2) = 3$, $r_5(3) = 4$, $r_5(4) = 5$, $r_5(00) = 6$, $r_5(01) = 7$, etc. Given $u \in \Sigma_2^*$, you now define $f(u)$ has the unique word $v \in \Sigma_5^*$ such that $r_5(v) = r_2(u)$ or, if you prefer, $f(u) = r_5^{-1}(r_2(u))$. This $f$ will satisfy $(*)$ but is of course more difficult to compute than the first coding.


Proof Carrying LLVM? I am intrigued by and understand the very basics of Proof Carrying Code (PCC) and I recognize that LLVM is a machine-independent intermediate language.  LLVM is the intermediate form of many languages, including the new Rust language.  Typed Assembly is another style of intermediate form which can be used to generate PCC proofs but it has not gained the same popularity/utility.  I've heard of Singularity, Verve and JX.

As I understand it, generating PCC proofs are within practicality even for large programs, but that their resulting size and verification burden (necessary only once per "installation") are non-negligible.  I don't care about 10x (discardable) proofs nor several hours of verification - I'm very interested in a provably-safe operating environment.

Is there anything missing from the LLVM language or type system that would prevent us from emitting such proofs?  Or can you tell that am I missing something about the bigger picture?

More

  PCC for what properties? Memory safety?

Yes, memory safety which I believe is a minimum policy required to ensure that a process cannot take over the kernel or another application.  Seems to me that (popularly) a message passing interprocess-communication scheme restores some of the functionality taken away by direct memory access (Erlang, Singularity OS).

  Do you have a citation/reference for your statement about practicality?

Here's something that suggests its practicality to me: "It has been shown that proofs for Java type safety can be compressed to 12%–20% of the size of x86 machine code ... but unfortunately this increases the proof checking time by a factor of 3".
-- Interpretation of Necula, Oracle-Based Checking of Untrusted Software by Franz

  What research have you done?

I've been following this topic (including the names I mentioned previously) over the years reading and absorbing what I can comprehend.

  I think it helps to separate "is it possible to do PCC for LLVM bitcode?" from "why doesn't the Clang compiler currently implement PCC?"

Yes, I'm mostly interested in "is it possible to do PCC for LLVM bitcode?" - but I'm not being too specific because I'm not confident that I understand how all the pieces fit together which is why I'm here trying to get an answer from a human who already gets it and can contribute to the understanding of people who are merely at my stage of understanding.

But see, related to your "why doesn't the Clang compiler currently implement PCC?", I would have assumed that the LLVM compiler (the one that goes from LLVM to assembly) would be the one capable of emitting the proof, since it still has higher level concepts of the code before it gets erased in the final binary (as does, I believe, TAL) and of interest because type-safe languages like C# and Rust compile to LLVM, possibly with enough type information to unify the approach among all LLVM languages.  So had I been more specific, I'd be getting shat on for that.

  I think it would help to clarify exactly what you're asking about

That's pretty much what I'm looking for!

This is a project I've been thinking of venturing into for a few years now, and I was fortunate to have a very useful discussion about it at the time I started planning it with Chris Lattner (at the time, one of the main architects of LLVM, although better known these days perhaps for his work on Swift).

It does seem that there is a possibility of producing correctness proofs for a subset of C (or potentially C++) using LLVM.  There has already been some work done which would be useful:

As discussed in comments, memory safety is critical.  Without memory safety, type safety is essentially irrelevant.  A number of memory-safety related analyses and transformations have already been implemented for LLVM that could help.  These include:
"fat pointers", i.e. transformation of C style pointers into pointers into areas of defined size, in order to catch bound errors
a transformation applied to dynamic memory allocation that enables detection of use of pointers after they have been freed.  These two features are described in this paper.

For the subset of C programs that perform no type casts, applying these transformations may be adequate.  Of course, real C and/or C++ code often uses typecasts, and adding this facility is more challenging.  For performance sake, as many of these cases as possible must be caught at verification time rather than runtime, although in the end of the day the use of runtime type information and a dynamic casting implementation would be enough to allow for entirely safe C code.


Having problem understanding the formal definition of NP So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff;

there exists a "certificate" string $t$ such that $|t| \le p(|s|)$ for a polynomial function $p$ and an input string $s$.
there exists an efficient certifier $B$ that takes $s$ and $t$ as inputs and has polynomial time complexity.

I'm having a hard time understanding this problem in a more practical sense. Say for example I had to verify a solution for a Graph Coloring problem. Then I would take the graph $G = (V, E)$ and the number of allowed colours $K$ as input (the problem instance) aswell as the proposed solution (Let's call it $S$) that consists of the coloring of the graph $G$. In this example, what would be $s$ and what would be $t$?

For Graph colouring problem

Input : A graph $G(V,E)$ and $k$.

Decide : Is $G$ $k$-colourable?

Certificate : A map $\phi : V \mapsto C $, where $C = \{R,B,Y,\cdots ,P\}$ is the set of colours and $|C| = k$.

For example for any $v \in V$, $\phi(v) = Y$ means $v$ has assigned color $Y$.

Example: let complete graph $K_4 (\{v_1,v_2,v_3,v_2\},E)$ is input graph and $k=4$ i.e. is it 4-colorable? A possible certificate in this case is $\{v_1(R),v_2(B),v_3(Y),v_4(P)\}$,($v_1(R)$ means vertex $v_1$ has color $R$),  which is polynomial in input size.

Now you can see that the size of $|\phi| \le p(|G|)$, where $|G|$ is a input graph size. As you have given a map $\phi$, now you can verify in polynomial time whether colouring is valid or not.


Why isn't it simple to count the number of words in a regular language? Given a DFA, A, let L(A) denote the number of words A accepts.
I think it's easy to calculate L(A):
Translate the encoding of A into a regular expression.
If the Kleene star appears anywhere in the expression - the language is infinite.
Else:
Go through and count all the combinations of words that are possible to make using the expression (basically if there is a + operator on the expression, multiply the amount of legal words by the amount of strings connected by the +..)

Is this wrong?
Thanks in advance

Yep, this is wrong, because of ambiguity.

Consider the following language:
$(a + aa) + a(a + \epsilon)$.

With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.

A better method is to use dynamic programming on an minimal DFA for your language, with no "dead" states. If the minimal DFA is cyclic, the language is infinte, so we can assume there's no cycles. Using a DFA is key, because the determinism means there's exactly one path through the DFA for each word.

What you do is build up a recurrence for the number of words that end at a given state:

1 words ends at the start state: $\epsilon$
For each state $q$, the number of words ending there is the sum of the number of words ending at each state with a transition into $q$.

The total number of words is then the sum of the number of words ending at each final state.


Proof via induction for small-step semantics I'm doing a course in Computer Programming Languages and I'm trying to prove the following (roughly following Pierce's Types and Programming Languages book):

if $t \rightarrow^* t'$ then $if\; t\; then \; t2 \; else \; t3 \rightarrow^* if\; t'\; then \; t2 \; else \; t3$

I'm a little confused about where to start; as far as I know, I'm supposed to define a base case, then prove it via induction.

I've started my proof by assuming these base cases:

$P(\frac{}{true \rightarrow^* true})$ and
$P(\frac{}{false \rightarrow^* false})$.

I'm stuck at this point, and I don't really how know to proceed.

edit: I've added the syntax in an effort to clear things up.

The induction should be on the derivation of $t \to^* t'$:

If $t \to t'$ in one step, then we get the desired result by the E-IF rule.
Suppose $t \to^* t'$ because $t \to t'' \to^* t'$. By the E-IF rule we have
$$(\mathtt{if}\;t\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to
    (\mathtt{if}\;t''\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)$$
and by the induction hypothesis
$$(\mathtt{if}\;t''\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to^*
    (\mathtt{if}\;t'\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3).$$
These two together give us the desired
$$(\mathtt{if}\;t\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3)
    \to^*
    (\mathtt{if}\;t'\;\mathtt{then}\;t_2\;\mathtt{else}\;t_3).$$


Why splitted text files is bigger than a large one with the same content? I have this large text file that when unzipped has about 2GB.
I split this one into multiple(more than 5 million) files and now I have a folder of about 20GB, how is this possible?

Filesystem overhead.

Every time you create a file, the filesystem reserves space on disk to store the file name, and other metadata like its permissions, creation date, etc. It also has to maintain a sort of index of all the (possibly sparse) blocks occupied by each file. The index might be a simple list or a tree, depending on the filesystem.

Finally, note that most filesystems can not allocate only a portion of a block for a file, so the allocated space needs to be rounded up to the block size. This rounding affects both the file blocks, and the index blocks.


Is NAE-HORN-SAT in P or NP-hard? I am interested to know the complexity of the NAE-HORN-SAT problem
(not all equal).  We know that HORNSAT is $\mathsf{P}$-complete, but
on the other hand, NAE-SAT is $\mathsf{NP}$-complete.  I want to know
what can we say about NAE-HORN-SAT problem.  Let me define the problem
formally:

  Given: One Boolean formula $\phi$ is given to us in CNF where each
  clause has at most one positive literal (HORN-property).
  Question: Is there any assignment for the input variables of
  $\phi$ such that any clause has at least one False and at least one
  True literal (NAE-property) ?

N.B.:

Positive literal: any variable directly,
Negative literal: negation of any variable.
True literal: literal is assigned to Boolean True by any assignment,
False literal: literal is assigned to Boolean False by any assignment.

According to Schaefer's dichotomy theorem, this problem must be either
in $\mathsf{P}$ or $\mathsf{NP}$-complete.  I can just find one
polynomial reduction from HORNSAT to this problem, which proves
actually nothing.  Is there a polynomial time algorithm to solve this
problem?

Or, is there any way to prove this problem to be $\mathsf{NP}$-hard?
Any thoughts about this ?

Your problem, NAE-HORN-SAT is $NP$-complete. Monotone NAE-SAT is $NP$-complete and it is a special case of your NAE-HORN-SAT. Literals in monotone SAT formula are either all positive or all negative.

Take any instance of Monotone NAE-SAT problem (all its literals are negative) then this formula is an instance of NAE-HORN-SAT problem.


Given computable function, what are conditions for computability of inverse function? If $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and has an inverse, under what conditions is $f^{-1}$ also computable? I couldn't find that in a textbook, and googling gets some vague suggestions about bijective, but I couldn't find a clearly stated theorem to that effect. Offhand, bijective seems sufficient but not necessary, e.g., $f(n)=2n$ isn't surjective but is computably invertible (for a total function inverse, use lifted domain $\mathbb{N}_\perp$ and map odd numbers back to $\perp$). In addition to an answer, a reference to a theorem/proof would be great, or just the name of a relevant theorem so I can successfully google it.

This question came to mind regarding the following thought (which I also wasn't able to find in a textbook or google anything about). The distinction between $f$ computable and $f^{-1}$ not, versus both computable, seems kind of analogous to an r.e. versus recursive distinction. Can that be expressed rigorously?

For example, consider $f:E\rightarrow E$, with $f\in D=[E\rightarrow E]$ the (Scott- or Lawson-continuous) function space domain of some domain $E$. Let $K_D$ be $D$'s compact elements, $\downarrow f=\lbrace g\in K_D\mid g\sqsubseteq f\rbrace$, whereby $f=\sqcup\downarrow f$, all in the usual way. Then $f$ is computable if an enumeration of $\downarrow f$ is r.e. Similarly, $f^{-1}$ is computable if an enumeration of $\downarrow f^{-1}$ is r.e. So if both are computable, meaning both enumerations r.e., then that seems (to me at least) kind of analogous to recursive.

Of course, it's not quite the same thing as recursive, since if $\mathbb{N}_f\subseteq\mathbb{N}$ is an enumeration of $\downarrow f$, and similarly for $\mathbb{N}_{f^{-1}}$, then $\mathbb{N}_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}_f$ (at least I don't suppose so). But there seems to be some kind of analogous idea trying to express itself. So how could you formulate that kind of thing rigorously? Among the first steps, I'd think you'd want to express $\mathbb{N}_{f^{-1}}$ in terms of $\mathbb{N}_f$, but I'm not seeing how to go about setting that up (any suggestion how to do that?).

So, is this idea also well-known and discussed? A textbook or google reference (or google-able search term) would be great. Thanks.

Let us say that a computable function $f$ is invertible if there is another computable function $g$ that on input $y$ either finds $x$ such that $f(x) = y$ or returns $\bot$ when $y$ has no preimage.

For this definition, one can show that a computable function $f$ is invertible if and only if its range is decidable, that is, we can decide whether a given input has a preimage under $f$.


How to model "name similarity"? I am new to machine learning. But have basic understanding of the concepts.

Problem statement : We humans won't perceive much difference between "Tim Cook" and "Tim C0ok". ( 0 is been replaced with zero ). I am trying to model this.

Task is to come-up with a model which can predict if two names are visually similar. The system will be configured with a predefined set of names. When the system is online, it should predict whether a given name is similar to one of the configured name or is not similar to any of the configured name.

My current approach: I'm trying to come up with a two-stage model. First stage is a binary classier which predicts name is know to system or not. Second stage is a multi-class classifier, which tells to which configured name given name is similar.

Features : Using string distance measures Levenshtein Distance, Damerau-Levenshtein Distance, Jaro Distance, Jaro-Winkler Distance and Hamming Distance as the feature vector. Feature vector is computed between a reference string ( Ex : 'aaaaaaaaa' )  and the name.

There are existing dictionaries that list pairs of characters that are visually similar.  See, e.g.,

https://security.stackexchange.com/q/36257/971
https://security.stackexchange.com/q/128286/971
https://stackoverflow.com/q/4846365/781723

Therefore, I suggest you try modified edit distance: compute the edit distance, but with a cost function that treats the distance between a pair of visually similar characters as zero or much smaller than the distance between a pair of different characters.

I recommend using the Damerau–Levenshtein edit distance. It includes transpositions among the changes it considers.  There's some reason to believe this corresponds better to mistakes made by humans.  So, maybe it'll correspond better to what humans consider similar.

Another plausible approach would be to render the two strings to images (using whatever font you think will be used to display them), then compare the images.

To compare how visually similar the images are, a basic starting point would be to use L1 or L2 distance (both have been shown to correspond well to human perception in some situations).  This probably won't be enough because it will fail badly if the images aren't perfectly aligned.  To address that, I suggest you apply a sort of edit distance that allows inserting or deleting entire columns of pixels (a full-height column), in addition to changing individual pixels.

It's not clear whether machine learning will be useful here.  The obvious approach to try first would be to compute the edit distance and compare it to some threshold.  That might be sufficient.


Recover a matrix with minimum number of queries Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob can ask Alice is: "Does $\sum a_{i,j} = 0$" for some subset $\{a_{i,j}\}$ of size $n$. How fast (i.e. minimum questions) can Bob recover the ones (even with high probability)?

Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed.

Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $N$ are successful. This is the same as making $N$ queries, each of which involves $n$ zero positions at random. The probability that a particular zero position is never queried is
$$
\left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}.
$$
Therefore after $(2+\epsilon) n\log n$ queries, the probability that a particular zero position is never queried is at most roughly $n^{-2-\epsilon}$, and so the probability that not all zero positions are revealed is at most $n^{-\epsilon}$. We conclude that $(2e+\epsilon) n\log n$ queries suffice to reveal the matrix with probability $1-o(1)$.

We can repeat the calculation for general $m$, but the bounds no longer match. For example, when $m$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.


Deciding if a finite automata accepts strings of any length 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 ?

Let $L$ the language accepted by your DFA. The question amounts to ask whether $\{ |u| \mid u \in L \} = \mathbb{N}$. To check this, just identify all letters to a single letter, say $a$, in your DFA. You will get a NFA on the alphabet $\{a\}$. It now remains to check whether this NFA accepts $a^*$.


Find a MST such that it's mostly red (original graph's edges are colored red and blue) Consider the following problem:
Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight).
Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges.
However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

Please advise.

Hint: Add $\epsilon>0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)


$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.

In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$ contains a pointer to the block of storage representing the table. The field $num[T]$ contains the number of items in the table, and the field $size[T]$ is the total number of slots in the table. Initially, the table is empty : $num[T] = size[T] = 0$.

$\text{Table-Insert(T,x)}$
$1\quad \text{if $size[T]=0$}$
$2\quad\quad \text{then allocate $table[T]$ with $1$ slot}$
$3\quad\quad size[T] \leftarrow 1$
$4\quad\text{if } num[T] =size[T]$
$5\quad\quad\text{then allocate $new{\text{-}}table$ with $2 \cdot size[T]$ slots}$
$6\quad\quad\quad\text{insert all items in $table[T]$ into $new{\text{-}}table$}$
$7\quad\quad\quad\text{free $table[T]$}$
$8\quad\quad\quad table[T] \leftarrow new{\text{-}}table$
$9\quad\quad\quad size[T] \leftarrow 2 \cdot size[T]$
$10\quad \text{insert $x$ into $table[T]$}$
$11\quad num[T] \leftarrow num[T] + 1$

For the amortized analysis for the a sequence of $n$ $\text{Table-Insert}$ the potential function which they choose is as follows,

$$\Phi(T) = 2.num[T]-size[T]$$

To analyze the amortized cost of the $i$th $\text{Table-Insert}$ operation, we let $num_i$ denote the number of items stored in the table after the $i$ th operation, $size_i$ denote the total size of the table after the $i$ th operation, and $\Phi_i$ denote the potential after the $i$th operation.
Initially, we have $num_0 = 0, size_0 = 0$, and $\Phi_0  = 0$.
If the $i$ th Table-Insert operation does not trigger an expansion, then we have $size_i = size_{i-i}$ and $num_i=num_{i-1}+1$, the amortized cost of the operation is $\widehat{c_i}$ is the amortized cost and $c_i$ is the total cost.

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

If the $i$ th operation does trigger an expansion, then we have $size_i = 2 . size_{i-1}$ and $size_{i-1} = num_{i-1} = num_i —1$,so again,

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

Now the problem is that they do not make calculations for $\widehat{c_1}$, the situation for the first insertion of an element in the table (line 1,2,3,10,11 of code only gets executed).
In that situation, the cost $c_1=1$, $\Phi_0=0$ and $num_1=size_1=1 \implies \Phi_1 = 2.1-1 =1$
We see that $\Phi_1=1 \tag 1$
So, $$\widehat{c_1}=c_1+\Phi_1-\Phi_0=2$$
But the text says that the amortized cost is $3$, (I feel they should have said the amortized cost is at most $3$, from what I can understand)
Moreover in the plot below,

The text represents graphically the $\Phi_1=2$ which sort of contradicts $(1)$, but as per the graph if we assume $\Phi_1=2$ then $\widehat{c_i}=3, \forall i$
I do not quite get where I am making the mistaken.

You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.
To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=3$ for all $i$.
The first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation is indeed very special. It is not considered as an expansion, an event that is defined as "in which lines 5–9 are executed". However, it does not maintain $size_i = size_{i-1}$, either. So neither computation for $\widehat{c_i}$ in the textbook is fit for $\widehat{c_1}$.
That error is confusing given that we tend to trust fully an exemplary textbook where so much attention have been paid to detail and correctness.
On the other hand, that error is not very significant since, as you noted, it still holds that "the amortized cost is at most 3".
By the way, if you take a closer look at the figure at the end of question, it shows the potential at the end of first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation, $\Phi_1=1$, the correct value.


How can we prove that an enumerable/decidable group of languages is closed under an operation? For example:

If the XOR operation on two languages, A and B, is described as:
$A\;\mathrm{XOR}\;B = (A \cup B) \setminus (A \cap B)$,

1) How can we prove that the set of enumerable languages is closed under the XOR operation?

2) How can we prove that the set of decidable languages is closed under the XOR operation?

Here is a similar example, with the minority operator: the minority of three languages $A,B,C$ consists of words belonging to at most 1 of $A,B,C$.

If $A,B,C$ are decidable then so is their minority. Indeed, given a word $w$, first determine whether $w$ belongs to $A$, to $B$, and to $C$. You can do this since $A,B,C$ are decidable. Depending on this data, either accept or reject $w$. This is an algorithm deciding the minority.

If $A,B,C$ are enumerable, then their minority need not be so. Indeed, let $A$ be a language which is enumerable but not co-enumerable (for example, the set of halting programs). The minority of $A,A,A$ consists of all words not in $A$, i.e., the complement of $A$. By assumption $A$ is not co-enumerable, so the minority of $A,A,A$ is not enumerable.