Deriving the Sobel equations from derivatives Many sites give the Sobel operators as the convolution mask for smoothing an image. However, I haven't found a single site that describes how you can derive the operators from partial first derivatives. If anyone can explain the derivation, I would highly appreciate it.

The Sobel operator is an approximation of the derivative in the X dimension followed by a simple smoothing operator in the Y dimension.  (Or derivative in the Y dimension and then smoothed in X).

Consider a one-dimensional signal $f(t)$.  The derivative of $f(t)$, $d f(t) / dt$ can be written as:

$$
\lim_{\Delta \rightarrow 0} \frac{f(t+\Delta) - f(t-\Delta)}{2\Delta}
$$

This is called the centered difference formula.

But with a discrete signal the smallest $\Delta$ you have at your disposal is the distance between samples, so you use that as an approximation of the limit.

We can see just how bad (or good) an approximation it is by looking at what it does to a complex exponential signal $e^{\omega i t}$.  The true derivative would give $\omega i e^{\omega i t}$.  The approximation gives
$$
\frac{e^{\omega i (t+1)} - e^{\omega i (t-1)}}{2} =
\frac{e^{\omega i}e^{\omega i t}-e^{-\omega i}e^{\omega i t}}{2} =
\frac{e^{\omega i} - e^{-\omega i}}{2}e^{\omega i t} =
i \sin(\omega)e^{\omega i t}
$$
so extremely accurate with low frequencies ($\omega$ near 0), but increasingly inaccurate as $\omega$ approaches the Nyquist frequency ($\omega \rightarrow \pi$).  This is about the best you are going to do with three samples.  It also has the advantage of over-attenuating the high frequency response rather than over-amplifying.

Now let's do some smoothing in the Y dimension.  We want something that only uses 3 points, and about the best you are going to get is $\frac{1}{4}f(t-\Delta) + \frac{1}{2}f(t) + \frac{1}{4}f(t+\Delta)$.  This filter has frequency response:
$$
\frac{1}{4}e^{\omega i (t - \Delta)} + \frac{1}{2}e^{\omega i t} + \frac{1}{4}e^{\omega i (t + \Delta)} =
\frac{1}{2}(1 + \frac{e^{-\omega i \Delta}+e^{\omega i \Delta}}{2})e^{\omega i t} =
\frac{1}{2}(1 + \cos \omega)e^{\omega i t}
$$
which smoothly transitions from passing low frequencies to completely attenuating high frequencies.

So convolve the derivative approximation in the X dimension with the smoother in the Y dimension and you get the kernel:
$$
\frac{1}{8}
\left[
\begin{array}{ccc}
1 & 0 & -1 \\
2 & 0 & -2 \\
1 & 0 & -1
\end{array}
\right].
$$


What properties of a discrete function make it a theoretically useful objective function? A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) global optimum which could be theoretically found by an exhaustive search of the candidate space. I'm also using "theoretically useful" in a slightly misleading way because I really couldn't understand how to phrase this question otherwise. A "theoretically useful cost function" the way I'm defining it is:

A function to which some theoretical optimisation algorithm can be applied such that the algorithm has a non-negligible chance of finding the global optimum in less time than exhaustive search

A few simplified, 1-dimensional examples of where this thought process came from:

Here's a function which, while not being convex or differentiable (as it's discrete), is easily optimisable (in terms of finding the global maximum) with an algorithm such as Simulated Annealing.

Here is a function which clearly cannot be a useful cost function, as this would imply that the arbitrary search problem can be classically solved faster than exhaustive search.

Here is a function which I do not believe can be a useful cost function, as moving between points gives no meaningful information about the direction which must be moved in to find the global maximum.
The crux of my thinking so far is along the lines of "applying the cost function to points in the neighbourhood of a point must yield some information about the location of the global optimum". I attempted to formalise (in a perhaps convoluted manner) this as:

Consider the set $D$ representing the search space of the problem and thus the domain of the function and the undirected graph $G$, where each element of $D$ is assigned a node in $G$, and each node in $G$ has edges which connect it to its neighbours in $D$. We then remove elements from $D$ until the objective function has no non-global local optima over this domain and no plateaus exist (i.e. the value of the cost function at each point in the domain is different from the value of the cost function at each of its neighbours). Every time we remove an element $e$ from $D$, we remove the corresponding node from the graph $G$ and add edges which directly connect each neighbour of $e$ to each other, thus they become each others' new neighbours. The number of elements which remain in the domain after this process is applied is designated $N$. If $N$ is a non-negligible proportion of $\#(D)$ (i.e. significantly greater than the proportion of $\#(\{$possible global optima$\})$ to $\#(D)$) then the function is a useful objective function.

Whilst this works well for the function which definitely is useful and the definitely not useful boolean function, this process applied to the random function seems incorrect, as the number of elements that would lead to a function with no local optima IS a non-negligible proportion of the total domain.
Is my definition on the right track? Is this a well known question I just can't figure out how to find the answer to? Does there exist some optimisation algorithm that would theoretically be able to find the optimum of a completely random function faster than exhaustive search, or is my assertion that it wouldn't be able to correct?
In conclusion, what is different about the first function that makes it a good candidate for optimisation to any other functions which are not.

No, I don't think your formalization is heading in a useful direction.  It seems convoluted and focused on one particular algorithm, but there might be other optimization algorithms that you haven't considered.
I don't expect there to be a useful characterization of which objective functions can and can't be optimized effectively.  It's a notoriously hard problem.  There is work on the literature on identifying classes of problems that can provably be optimized efficiently (e.g., convex objective functions, linear programming, semidefinite programming), but the reality is that what we can prove falls short of what empirically often seems to be feasible in practice.
For instance, what you're looking for is at least as hard as the P vs NP problem, since every NP problem can be expressed as an optimization problem; and I don't expect there to be a simple characterization of which NP problems are NP-complete.


Reasoning about resources: "resource logics"? Are there extensions of predicate logic which focus on resource models, possibly even in actor models?

And if so, would it be possible to reason on a meta-level on how many resources should be expended to find further proofs in the same or other systems?

Do you mean a resource-aware logic?
If so, yes, there's linear logic [Girard, 1987] (as was already noted in the comments). It has had a big influence on the study of concurrency and implicit computational complexity. You might be interested in the latter, where reasoning is focused on the efficiency of programs.

What do you mean exactly by "actor models"?
If you mean concurrency, please have a look at: What is the Curry-Howard analogue for linear logics?
If you mean identifying who/what uses/implements resources at the level of propositions, we explored an extension of linear logic for that [Carbone et al., 2016], but mainly for the notion of communication protocol (who performs which communications). Useful inspiration might also come from hybrid logics that support notions of "worlds", like this one: https://www.cs.cmu.edu/~rwh/theses/reed.pdf


Given asymptotic bounds, what can we say about small n? I am trying to wrap my head around these asymptotic notations. Given $f(n)$ and $g(n)$, one can write $f(n) = \Omega(g(n))$ as shorthand for $f(n) \geq c*g(n), n\geq n_0$. But what happens when $n<n_0$. What can we then say about $f(n)$ and $g(n)$? Do we just assume that $f(n)$ is a constant and the relation still works? Or does the question not even make sense to ask?

Nothing. If all you know about two functions is their $O$/$\Omega$ relations, you know nothing about how they relate to each other on any finite prefix.

Yes, this makes asymptotics of, say, runtime functions absolutely useless in terms of questions like, "which algorithm should I use in scenario X?" On first sight, that is.

Luckily, we usually do analyse with more detail but throw them away when formulating the theorem with coarse notation like Landau symbols. Many results about "practical" algorithms implicitly say, "and this behaviour can be observed for reasonable $n$".

Sometimes you get better theorems which use Landau notation for "error terms" only; authors like Knuth do not say "algorithm A runs in time $O(n \log n)$", but rather "algorithm A takes $2n\log n - 2n + O(1)$ comparisons". This does not completely do away with your issue, but mitigates it to some extent. If you know that that $O(1)$ stands for $\leq 1377$, you can make informed decisions based on that result.

Some of our reference material discusses facets of this issue.


Regular Expression simplification Does $(0 + 10^{*}1)^{*}$ simplify to the following language: Set of all binary strings with even number of ones.
In specific, does the * inside the brackets get evaluated first or the outer * gets evaluated first. Or does it even matter while simplifying as what we finally need is the set of all strings possible with this expression?

Yes, $(0+10^*1)^∗$ denotes the  set of all binary strings with even number of ones. Or more technically $L(\ (0+10^*1)^∗ \ ) = \{ w \ |\ w$ is a binary string containing even number of 1's $\}$. We denote language of a regular expression $E$ as $L(E)$.

To understand regular expressions, you need to understand the recursive definition of regular expressions.

if $E$ and $F$ are regular expressions $E$+$F$ is regular expression.
if $E$ and $F$ are regular expressions $EF$ is regular expression.
if $E$ is regular expression $E^*$ is regular expression.
For basis, $\epsilon$ and symbols from alphabet $\Sigma$ are also regular expressions.

Next language of regular expressions for each of the above operations is defined: union, concatenation and repetition, respectively. For basis, it is sets of empty string or a single symbol, as the case may be.

Now if $w \in L(E)$ then $L(E^*)$ is not just $wwwww...$, it is also any $w_1w_2w_3...$ (0 or more times) such that $w_1 \in L(E)$,   $w_2 \in L(E)$, $w_3 \in L(E)$, etc.

So $(0+10^*1)^*$ is really $(0+10^*1)(0+10^*1)(0+10^*1)...$ (0 or more times). Thus, you work with the outer $*$ operator first and then work with the inner $*$ operator.

Next comes the question of simplification. Either you want to describe the language of a regular expression in most simplest manner possible, or you want to describe the most simple regular expression for a given language. Both these are hard to do. Even if you are given a minimum DFA of the language, to compute minimum regular expression for it is NP-complete (the decision version: does there exist a regular expression of less than $k$ length for the given DFA).

We can minimize DFA but unfortunately we do not have efficient algorithms to minimize NFA or regular expressions unless $P = PSPACE$. See Minimizing NFA’s and Regular Expressions
Gregor Gramlich and Georg Schnitger.

However $(0+10^*1)^*$ is set of all binary strings with even number of ones. Yet another expressions are $0^*(10^*10^*)^*$, $(0^*10^*1)^*0^*$, $(0^*10^*10^*)^*$ and so on. The outline of proof that the regular expression  $(0+10^*1)^*$ is indeed the language mentioned above is as follows:

First we draw a DFA for the language. If we eliminate the state $q_1$ we get the equivalent (enhanced) DFA in the right. It is easy to see that the equivalent regular expression is same. This is kind of reverse-engineering.

Sometimes it is easy to go this way, rather than finding the language of regular expression by automated procedures. Sometimes we can use regular expression algebra also to analyze and simplify regular expressions.


Proving undecidability of a language with mapping reductions I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to prove is undecidable to solve a known undecidable language.
However, with mapping reductions, am I right in assuming these calls aren't needed? In addition, in the link provided, the solution pseudocode says
For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

How can you say "if it accepts"? How can you determine this, what if it loops forever and this is never found out? Why can you make such statements with a mapping reduction but not with Turing reductions? Could I make a statement like "if M halts on w, do ...". I mentioned this to my teaching assistant and he said you can't make any statements like these unless you're accessing an oracle and doing a during reduction, but I see loads of examples which seem to show otherwise. Hopefully this makes sense

Usually, when the context of the statement "if $M$ accepts $x$" is in a loop simulating the execution of $M$ on $x$, we just mean to say that if the simulation stopped and $M$ accepted/rejected then do something, otherwise just continue simulating (the more precise way of writing this would be to say "if $M$ accepted after $t$ steps then...").
Your pseudocode doesn't do anything magical, it simply checks at a specific point of the simulation whether or not $M$ already accepted/rejected.


Is the union of two non-regular context-free languages always non-regular? I had this question in my HW:

  Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular.

My intuition is that it is wrong. I thought about the following two languages:

$L_1 = \{a^ib^jc^k : 0 \leq i \leq j \leq k\}$ and
$L_2 = \{a^ib^jc^k : j<i \lor j>k\}$.

The union of these two languages is $a^*b^*c^*$ which is regular, but I didn't succeed to prove that $L_2$ is not a CFL (tried with the pumping lemma and stuck in the case that $vxy$ contains two types of letters).

Am I right with my intuition? if do so, how can I prove that $L_2$ isn't a CFL, or which other two languages disprove this claim?

Let $L$ be any non-regular context-free language over $\{0,1\}$, for example $\{ 0^n 1^n : n \geq 0 \}$. Take
$$
\begin{align*}
L_1 &= 0L \cup 1\Sigma^* \cup \{\epsilon\}, \\
L_2 &= 1L \cup 0\Sigma^* \cup \{\epsilon\}.
\end{align*}
$$
Then $L_1$ and $L_2$ are also non-regular context-free (exercise), but $L_1 \cup L_2 = \Sigma^*$.


Solving the recurrence formula $T(n) = 3T(n/2)+n^2$ What is the solution of the following recurrence?
$$
T(n) = 3T(n/2) + n^2, \quad T(1) = 0.
$$
I cannot use the master theorem since I need to know the exact final expression, not just it's big O, which I know is $O(n^2)$.
I'm stuck at the following, after 4 steps:
$$3^4T(n/2^4)+((3^6)n^2)/((2^6)2^6)+(3^3n^2)/((2^2)2^4)+(3n^2)/(2^2)+(n^2).$$


What was the first Turing-Complete programming language? What was the first turing-complete language? Know about the first machines
and computers, but not the programming language.

Why not read this Wikipedia article.

  The first programming languages designed to communicate instructions to a computer were written in the 1950s. An early high-level programming language to be designed for a computer was Plankalkül, developed by the Germans for Z1 by Konrad Zuse between 1943 and 1945. However, it was not implemented until 1998 and 2000.

Also, I think that it is wrong to consider a programming language as such to be Turing Complete since the concept of Turing completeness applies to a computational model, not to a programming language itself. For example, it is Turing machine, RAM machine, or Post systems that is Turing complete and not a set instructions or programming languages used to program them.

If our real life computers had infinite memory we could consider them a Turing machine equivalent to our abstract model we use in CS and Math, meaning that it is not programming languages or instructions sets used to program CPU that makes real life computers not equivalent to the abstract model.


Binary operators with higher precedence than unary operators Generally (perhaps always) in programming languages, unary operators have the highest precedence.  In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators at run time.

But what if we have a language where binary operators had higher precedence than unary ones?  Do such languages exist?  And how would we interpret certain cases?  For example, let's say binary + had higher precedence than unary prefix @.  In some cases this is obvious because it would mean that

@x+y

would parse as

@(x+y)

rather than

(@x)+y

BUT, how would we parse

x + @y

Would it be a syntax error (as in it cannot be parsed) or should it parse as x+(@y)?  I don't mean for this to necessarily be an opinion question; I am more interested to know if any real programming languages exist with high-precedence binary operators, and if so, what do they do.

In Perl, the 'not' operator has lower precedence than +. The expression (false + not 1) evaluates just fine.


Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently? Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that might happen in case of robbery, one problem came into my mind and it can be described as follows.

Suppose that you and your family decided to go on a trip abroad, that would last for around 7 days. After spending some nice time with your family, you return back only to realize that your home had been robbed. You call the police and the police asks for the data stored in the camera.

Now, you know for sure that the robbery happened during those 7 days that you were gone, and you definitely know that the camera will show the people doing the robbery at some specific point of time, problem is, you do not know when.

Now, assuming that no one had seen anything at all and that the only source of information would be the data stored by the camera, how would the police find the time during which the robbery happened? Can they do something better than watching every single second of the footage available?

In computer science terms, assume that you are given an array of size $N$, where all the elements are white, except for one which is black. Now you can imagine that the white elements are just images stored by the camera and the indexes of the array represent seconds. If no robbers are depicted in the image, then this image is white, otherwise it is black.

So now you want to find that second where the robbers are depicted in the image, so you are looking for the index of the black element in your array. Can you do better than actually scanning the entire array to find that index?

For your problem with the array: No, there is no better algorithm.  That's the best you can do.  Any deterministic algorithm will in the worst case have to look at every array element (technically: at least $n-1$ of the $n$ elements).

This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at $n-2$ elements and hasn't found the black element yet.  Then I claim a correct algorithm has to examine at least one more array element.  If it doesn't, then look at what output it produces, and see which of those two elements it blames; you can now construct an array that puts the black element at the other element (the one it didn't blame and hasn't looked at yet).  That array will be entirely consistent with everything the algorithm has seen so far, so the algorithm will produce the wrong output on that array.

For your problem with the camera video: In real life, there are much better techniques available.  For instance, you can do "change detection" to find the frames in the video that are different (show a change from the previous frame) and look only at those.  There are more sophisticated things you can do, but this illustrates that in practice you can often do much better, by taking advantage of domain-specific information about video surveillance.


Why do we believe that PSPACE ≠ EXPTIME? I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME.  If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, then how can there be a class of problems that experience greater exponential time blowup and do not make use of exponential space?

Yuval Filmus' answer is already extremely helpful.  However, could anyone sketch my a loose argument why it might be the case that PSPACE ≠ EXPTIME (i.e. that PSPACE is not a proper subset of EXPTIME)?  Won't we need exponential space in order to beat the upperbound for the total number of system configurations achievable with space that scales polynomially with input size?  Just to say, I can understand why EXPTIME ≠ EXPSPACE is an open matter, but I lack understanding regarding the relationship between PSPACE and EXPTIME.

Let's refresh the definitions.

PSPACE is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine that decides the problem using at most $p(n)$ tape cells when its input has length $n$, for some polynomial $p$.
EXP is the class of problems that can be solved on a deterministic Turing machine with exponential time bounds: for each such problem, there is a machine that decides the problem using at most $2^{p(n)}$ steps when its input has length $n$, for some polynomial $p$.

First, we should say that these two classes might be equal. They seem more likely to be different but classes sometimes turn out to be the same: for example, in 2004, Reingold proved that symmetric logspace is the same as ordinary logspace; in 1987, Immerman and Szelepcsényi independently proved that NL$\;=\;$co-NL (and, in fact, that NSPACE[$f(n)$]$\;=\;$co-NSPACE[$f(n)$] for any $f(n)\geq \log n$).

But, at the moment, most people believe that PSPACE and EXP are different.  Why?
Let's look at what we can do in the two complexity classes.  Consider a problem in PSPACE.  We're allowed to use $p(n)$ tape cells to solve an input of length $n$ but it's hard to compare that against EXP, which is specified by a time bound.

How much time can we use for a PSPACE problem? If we only write to $p(n)$ tape cells, there are $2^{p(n)}$ different strings that could appear on the tape, assuming a binary alphabet. The tape head could be in any of $p(n)$ different places and the Turing machine could be in one of $k$ different states. So the total number of configurations is $T(n) = k\,p(n)\,2^{p(n)}\!$.  By the pigeonhole principle, if we run for $T(n)+1$ steps, we must visit a configuration twice but, since the machine is deterministic, that means it will loop around and visit that same configuration infinitely often, i.e., it won't halt.  Since part of the definition of being in PSPACE is that you have to decide the problem, any machine that doesn't terminate doesn't solve a PSPACE problem.  In other words, PSPACE is the class of problems that are decidable using at most $p(n)$ space and at most $k\,p(n)\,2^{p(n)}$ time, which is at most $2^{q(n)}$ for some polynomial $q$. So we've shown that PSPACE$\;\subseteq\;$EXP.

And how much space can we use for an EXP problem? Well, we're allowed $2^{p(n)}$ steps and the head of a Turing machine can only move one position at each step. Since the head can't move more than $2^{p(n)}$ positions, we can only use that many tape cells.

That's what the difference is: although both PSPACE and EXP are problems that can be solved in exponential time, PSPACE is restricted to polynomial space use, whereas EXP can use exponential space. That already suggests that EXP ought to be more powerful.  For example, suppose you're trying to solve a problem about graphs.  In PSPACE, you can look at every subset of the vertices (it only takes $n$ bits to write down a subset).  You can use some working space to compute on each subset but, once you've finished working on a subset, you must erase that working space and re-use it for the next subset.  In EXP, on the other hand, you can not only look at every subset but you don't need to reuse your working space, so you can remember what you learnt about each one individually.  That seems like it should be more powerful.

Another intuition for why they should be different is that the time and space hierarchy theorems tell us that allowing even a tiny bit more space or time strictly increases what you can compute. The hierarchy theorems only let you compare like with like (e.g., they show that PSPACE$\;\subsetneq\;$EXPSPACE and P$\;\subsetneq\;$EXP) so they don't directly apply to PSPACE vs EXP but they do give us a strong intuition that more resource means that more problems become solvable.


Index matching algorithm without hash-based data structures? I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.

Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.

For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.

Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.

So my question is whether there is a linear algorithm for this task that does not use any hashsets.

If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $\Theta(n\log n)$ time in worst case for any algorithm.

This can be seen from the situation when array $a$ is sorted while array $b$ is arbitrary before we apply the algorithm. Knowing the index $I(k)$ of the element in $b$ which is the same as the $k$-th element of $a$ for all $k$, we can sort $b$ in $O(n)$ time by simply putting $b_{I(k)}$ in $k$-th position (using one temporary working space or a new result array of length $n$). However, it is well-known that it takes at least $\Theta(n\log n)$ time (comparisons) to sort $b$ in worst cases for any algorithm. So obtaining that knowledge, the index $I(k)$ for all $k$ must
take at least $$\Theta(n\log n)- O(n)=\Theta(n\log n)$$ time as well in worst cases.

The following is a formal formulation of the conclusion above in the comparison computation model.

Let $\mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,f\in E$, $\mathcal O$ outputs -1 if $e\prec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from $\{0, 1,\cdots, n-1\}$ to $E$. To output $I(0), I(1), \cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0\le k\le n-1$, it will take $\Theta(n\log n)$ queries against $\mathcal O$ in the worst case.

  whether there is a linear algorithm for this task that does not use any hashsets.

A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.


How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'? I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. For example

  (())()((()()))

is a correct string and

  )()()(

is an incorrect string.

An operation consists of taking a contiguous subsequence of the input string and 'flipping' every bracket in that subsequence.

Given an arbitrary string of brackets (of even length), the task is to find the smallest number of such operations needed to change it to a 'correct' string of brackets.

Another way to look at this problem is to have a string of +1s and -1s, and to try to find the smallest number of operations (of multiplying every number on an interval by -1) needed to make every prefix of this string nonnegative and every suffix nonpositive.

The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.

First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and $[\min(b, d), \max(b, d))$ that do not overlap, have shorter total length and cover exactly the same elements.

Replace opening brackets with $1$, closing brackets with $-1$. Now the problem corresponds to applying the minimum number of operations "multiply interval by $-1$" such that every prefix has nonnegative sum, and the sum over the entire array is zero.

We construct a solution left-to-right. At every position we can either start an interval, or end an active interval.

Let $DP[m][s][0]$ denote the minimum number of intervals we need to use such that every prefix sum in the first $m$ elements is nonnegative, the sum of the first $m$ elements is $s$, and we do not have an active interval. Similarly $DP[m][s][1]$ is the same value where we do have an active interval.

If the $m$th value is $1$, for $0 \leq s \leq m$ we set

$DP[m][s][0] = DP[m-1][s-1][0]$
$DP[m][s][1] = DP[m-1][s+1][1]$

Otherwise we set

$DP[m][s][0] = DP[m-1][s+1][0]$
$DP[m][s][1] = DP[m-1][s-1][1]$.

Then we end and start intervals, setting

$DP[m][s][0] = \min(DP[m][s][0], DP[m][s][1])$
$DP[m][s][1] = \min(DP[m][s][1], DP[m][s][0] + 1)$

The base case is $DP[0][0][0] = 0$, $DP[0][0][1] = 1$.

There are $\mathcal{O}(n^{2})$ states, and we do $\mathcal{O}(1)$ work to calculate each of them, therefore the algorithm runs in $\mathcal{O}(n^{2})$. The DP can be implemented to use $\mathcal{O}(n)$ memory by only storing the values of $DP$ for the current $m$.

Here is a C++ implementation of the algorithm.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}


How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input? I currently have a problem with the following question:

Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$.
Construct an NTM (non-deterministic Turing machine) that decides $L$.

My idea was to simulate every possible input of length $\le|w|^3$ on a given TM $M$ by using a separate band in my NTM for every single input word. If there is one band where $M$ halts, then the NTM accepts.

Is this the right way to go about it? My problem is that I don't see why I would need a NTM to decide $L$. A standard TM would be able to do the same thing.

$L$ is semi-decidable (or, synonymously, recursively enumerable). This can be proven (arguably) more easily by using an NTM which non-deterministically picks an input $w \in \{ 0, 1 \}^\ast$, simulates $M$ on it for at most $|w|^3$ steps, and accepts if and only if $M$ does. The NTM accepts exactly the language $L$ because, if there is no accepting branch of the NTM, then there is also no input $w$ for which $M$ halts in at most $|w|^3$ steps. For a properly written proof, it should also be said the semi-decidability of $L$ follows from the equivalence of DTM and NTM acceptors (remember (semi-)decidability is defined in terms of DTMs, not NTMs!).

Because of the equivalence of DTM and NTM acceptors, the above reasoning indirectly gives you a DTM which accepts $L$. The explicit construction could be picking an enumeration of inputs (e.g., lexicographical order), simulating $M$ on each input $w$ for at most $|w|^3$ steps, and accepting if and only if $M$ does. (Having to argue about the enumeration of inputs might be perceived as "hard" by some, hence why proving with an NTM could be considered "easier".)

A warning, however: $L$ is not decidable. This is because its complement is $\{ \langle M \rangle \mid \forall w: \text{$M$ does not halt for $w$ in at most $|w|^3$ steps} \}$ and, thus, a variant of the complement of the halting problem, which is notorious for not being semi-decidable.


The use of modal logic in computer science I have a tentative understanding of modal logic.  Can anyone explain modal logic as it is used in computer science?

I think you can find many good examples if you search a bit online.  Some very-easy-to-find examples are in the following list:
From Stanford Encyclopedia

In computer science, labeled transition systems (LTSs) are commonly used to represent possible computation pathways during execution of a program.

Wikipedia has some examples in its article modal logic:

Versions of temporal logic can be used in computer science to model computer operations and prove theorems about them. In one version, ◇P means "at a future time in the computation it is possible that the computer state will be such that P is true"; □P means "at all future times in the computation P will be true". In another version, ◇P means "at the immediate next state of the computation, P might be true"; □P means "at the immediate next state of the computation, P will be true".

Also, if you go to Logic in Action, you will find several examples, e.g.:

[Chapter 6] introduces dynamic logic, a system that was introduced in computer science for reasoning about the behaviour of computer programs, by Vaughan Pratt and others, in the 1970s.
In [Chapter 10] it is explained how predicate logic can be used for programming. The chapter gives an introduction to concepts used in automating logical theorem proving. This leads to computational tools underlying the well known logic programming language Prolog, popular in AI an in computational linguistics. The inferential mechanism behind Prolog is called SLD-resolution. This is the reasoning engine for a natural fragment of predicate logic (the so-called Horn-fragment).


CNN/Neural Network: Can I still estimate 3 parameters if my input data has insufficient parameter labels? I am trying to simplify a CNN model. Currently, I need to train 3 different models (with the same architecture) to estimate each parameter. I am just wondering if there is a way to just train one model that outputs 3 parameters, with input images containing only single parameter label.
Say the three parameters are some kind of measure of symmetry (sym), repetitiveness (rep), roundness (rd). Each of my input images will only give a label for one of the parameters. For each parameter, there is the same number of images.
I am thinking if there is a way to accomplish this using some kind of dummy variable to block out the unavailable parameters from backpropagation?

If anyone who has experience with this scenario could give me some advice, it would be super appreciated.

Yes, this can be done.  Basically, you define a custom loss function, and then train the neural network to minimize this loss function.  In particular, you construct a single neural network that has 3 outputs; the first output is a measure of symmetry, the second of repetitiveness, and the third roundness.  The custom loss function should look at the output for which you have a known label and penalize the model according to how much that output is in error (it ignores the other 2 outputs).  For instance, if you are currently using mean-squared error, your custom loss function would be equal to the square of the difference between the known label and the corresponding output of the network.  This custom loss function is differentiable, so all the standard training methods (backpropagation, gradient descent, Adam solver, etc. etc.) work directly, with no modifications needed.

Many libraries for training neural networks will let you specify a custom loss function.


Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$? I am having problems resolving the following question:

  Given some problem $X$. If there exists a polynomial time reduction from (for example) $\mbox{SAT}$ to $X$, $(\mbox{SAT} \leq_{p} X)$ and since we know that $\mbox{SAT}$ is $\mbox{NP-complete}$, to show that $X$ is $\mbox{NP-complete}$ is it necessary to show that $X\in \mbox{NP}$ via some third party algorithm?

If yes, then why?

the reduction only shows that X is at least as hard as SAT (NP-HARD). This could mean that X is in a class suspected to be harder than NP such as PSPACE or EXPTIME. To show that X is NP-complete you must show that it is also in NP. If you try it out you will see that you can easily reduce SAT to problems in EXPTIME that are not suspected to be in NP. The idea being that your reduction shows that X is at least as hard as SAT, but there are classes of problems harder than NP problems which X could fall into.


$L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$ Prove that $L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$.

I managed to prove the $(\impliedby)$ and I want to prove $(\implies)$.

I feel that we need to take the boolean circuit and duplicate the sub-circuits of $fan-out\gt 1$ into exact circuits but with $fan-out = 1$. I fail to argue why the resulting tree is of polynomial size and not of exponential one.

Let the size of a circuit or formula be the number of leaves. The total number of vertices in a formula is at most twice its size.

You can prove by induction the following claim:

  If a function is computed by a fan-in 2 circuit of size $S$ and depth $D$, then it is computed by a formula of size $2^D S$.

If $L$ is in NC1 then its $n$-bit fragments have circuits of size $n^{O(1)}$ and depth $O(\log n)$. The claim shows that there are equivalent formulas of size $n^{O(1)} 2^{O(\log n)} = n^{O(1)}$.


Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis? If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be correct for that analysis?

I have read the formal definitions for all of these and it does not help me to understand them.

I understand that Big-Oh is an upper bound but how do you know if the algorithm you analyze is an upper bound? I mean, if I analyze an algorithm and I come up with $5n^3 + 100n^2 + 32n$, how do I know to make this Big-Oh?

The key point is that $O(\cdot)$ and friends describe relationships between functions. Functions are purely mathematical objects and it doesn't matter what they're being used to measure. This is similar to the way that $<$ and friends describe relationships between numbers and it doesn't matter what those numbers are being used to measure.

So, in particular, it doesn't matter if your function is being used to measure the running time of some algorithm. It doesn't even matter if your function is being used to give, say, an upper bound on the running time of an algorithm. If I want to, I can give you an upper bound on a function that's a lower bound for the running time.  It's not very useful to do that but, because $O(-)$ doesn't care what the function is measuring, it makes perfect mathematical sense.  This is a bit like saying, "Jane is less than 1.75m tall and John is taller than her": I've given you an upper bound for Jane's height and Jane's height is, in turn, being used as a lower bound for John's. OK, John could have any height at all, but the mathematics makes sense.

So, all $T(n)=O(f(n))$ says is that the function $g$ is an upper bound for the function $T$, up to constant factors, for large enough inputs. It says nothing at all about any connection between the function $T$ and the real world: it doesn't say that $T$ is an upper bound for this or a lower bound for that.

With all of that out of the way, we can address the technical part of the question, but that really does just follow from the definitions, as I stated in comments.

Tou have a function $5n^3 + 100n^2 + 32n$ and you want to compare it to some other functions: $n$, $n^2$ and $n^3$. Let's call that function $T(n)$.  Apparently, the function $T$ is somehow related to the running time of some algorithm but that doesn't matter for what's about to happen.

$T(n) = O(n^3)$ because, for $n>100$, $T(n) \leq 5n^3 + n\cdot n^2 + n^2\cdot n = 7n^3$.
$T(n)\neq O(n^2)$ because, for any constant $c$, and any $n\geq c$, $5n^3 + 100n^2 + 32n > 5n^3 \geq 5cn^2 > cn^2$. Similarly, $T(n)\neq O(n)$.
$T(n) = \Omega(n^3)$ since, for any $n>0$, $T(n)> n^3$. Similarly, $T(n) = \Omega(n^2)$ and $T(n) = \Omega(n)$.
$T(n) = \Theta(n^3)$ because $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. $T(n)\neq \Theta(n^2)$ because $T(n)\neq O(n^2)$ and $T(n)\neq \Theta(n)$ because $T(n)\neq O(n)$.


How to construct a DFA for this? Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of
all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $b_1b_2 ··· b_k \in B$. Show that if A and B are regular then so is $C = shuffle(A, B).$

Suppose $A$ and $B$ are regular. Let $M_A$ and $M_B$ be DFAs for $A$ and $B$, respectively. We know $M_A$ and $M_B$ exists since every regular language is accepted by some $DFA$.

Let $M_A = (\Sigma, Q, q_0, A, \delta)$ and $M_B = (\Sigma', Q', q_0', A', \delta')$.

We define $M_C = (\Sigma'', Q'', q_0'', A'', \delta'')$ such that $L(M_C) = shuffle(A,B)$.

First, let $\Sigma'' = \Sigma \cup \Sigma'$.

Next, choose $Q'' = \{0, 1\} \times Q \times Q'$.

Now, choose $A'' = \{(0, q, q') \mid q \in A, q' \in A' \}$.

Let $q_0'' = (0, q_0, q_0')$.

Now the fun part: what is the transition function? Here's what it's going to do:

If $q'' = (0, q, q')$, then $\delta''(\sigma, q'') = (1, \delta(\sigma, q), q')$ if $\delta(\sigma, q)$ is defined, or undefined otherwise (we're going to get an NFA, but that's OK).
If $q'' = (1, q, q')$, then $\delta''(\sigma, q'') = (0, q, \delta'(\sigma, q'))$ if $\delta'(\sigma, q')$ is defined, or undefined otherwise (again, we're going to get an NFA, but that's good enough for establishing regularity).

Basically, we're using the state to encode whether the last symbol we saw was from a word in $A$ or from a word in $B$. We can only accept if the last symbol we saw was from a word in $B$, hence our set of accepting states requiring that we have 0 for the parity. Furthermore, we can only accept if we've seen a complete word from both $A$ and $B$, which is why we require the other components to be accepting states in their respective automata.

You can think of this as two simultaneous DFAs produced from the Cartesian-Product construction for the intersection of the languages. After evaluating each step, we jump to the other machine. The first machine accepts input corresponding to the language $A$, and the second machine accepts input corresponding to the language $B$.

The full proof that this construction yields a correct automaton is left as an exercise.

Note that this construction technically allows $k = 0$, which is not allowed by the language in the question. To complete the exercise, argue that the NFA obtained above can be converted to a DFA by a standard construction, and that intersecting the resulting DFA with a DFA for the language of positive-length strings gives a DFA for the desired language.


How to model a set of categorical values in the input of a neural network One of the inputs to my neural network is a set.  I have a set $S = \{s_0, s_1, ..., s_n\}$ in which all values $s_i$ are constant. An example of such a set could be the set of French wines (Beaujolais, Languedoc-Rousillon, Champagne) or the set of players in a sports event (Player A, Player B, ...). The input to the neural network is a subset $T$ of $S$ (e.g., Player A competing against Player B or Beaujolais wine being served at a table, but nothing else).

Due to the restrictions of my neural network design, all input values must be normalized within the interval $[0,1]$. How would I encode the set $T$ to obtain an input to the neural network?  How do I normalize the values in my set $S$ in a way to respect this condition?

My current idea is to use one boolean input per $s_i$: there would be $\#(S)=n$ boolean inputs, all set to 0 except for the values in $T$, which would be all 1. However, this presents the obvious flaw that for large $n$ there would be a lot of input neurons. Moreover, if one imposes the additional restriction of having at most $m$ elements in $T$, the resulting model would not efficiently correspond to the model (i.e. what if $m+1$ values were set to true)?

Is there a better way of modeling such a situation? Or better, is there a standard way for handling input sets with multiple possibilities?

Yes, the "one boolean per set element" is the standard way of encoding such a set.  This is known as a "one-hot encoding".  Yes, there will be a lot of input neurons, but that's not necessarily a serious problem; current procedures for training neural networks are able to handle millions of nodes with no problems.

If you know that $T$ will contain at most $m$ elements, in principle there are alternative encodings (e.g., use $m \lg n$ wires, where you use $\lg n$ wires for each element of $T$ to encode which element of $S$ it is)... but in practice I do not expect them to perform well.

In that case I think a better approach is to try to build a feature vector that is shorter than $n$ dimensions.  Do you have some domain knowledge you can use to identify attributes of the elements?  For instance, you could have a feature that says "how many elements of $T$ are red wines?" and "how many elements of $T$ are white wines?" and "how many elements of $T$ are dessert wines?" and so on.  You'll have to use your domain knowledge about the task to identify what attributes might be relevant to the classification task.  In this way, the number of input wires can be made much smaller than $n$.


Given two identical DOM trees find same node in tree B So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.
I can solve it in two ways -

Start at the given element and traverse up to the root of tree A - save the path and then follow the path down the second tree to the element.

Start at the root and traverse both trees at the same time using breadth first search - once I find nodeA in tree A return the current node in treeB.

The complexity for the second approach will be O(N) as worst case I could end up going through every node in the tree to find the element.
For the first approach is the complexity simply O(P) where P is the length of the path from the given node to the root? At most I will go up P nodes and then down P nodes in treeB and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.

You are right, the complexity of the second algorithm is $O(P)$ where $P$ is the depth of the given vertex in the second tree. Notice that, without additional assumptions, it might very well be $P=\Omega(N)$ (think, e.g., of a path rooted in one endpoint where the given vertex is the other endpoint).
If the second tree is somehow "balanced", for some reasonable definition of balanced* then its height will be at most $O(\log n)$, hence $P=O(\log n)$.
*Since your tree is not necessarily binary you'd have to provide a suitable definition of balanced. A sufficient condition for $P=O(N)$ would be for the heights of the two tallest subtrees rooted in two children of each node of the second tree to differ by at most an additive constant.


What algorithm is most suitable for large text compression? Currently, I am looking for an lossless compression algorithm that is suitable for a large amount of text, that will be further encrypt by AES and use as the payload in steganography.

Based on A Comparative Study Of Text Compression Algorithms, it seems that Arithmetic coding is preferable in Statistical compression techniques, while LZB is recommended for Dictionary compression techniques.

So now I am wondering whether Statistical compression or Dictionary compression is more suitable for large English text compression in terms of compression ratio and ease-to-implement.

I have search through but still barely have an idea of the suitable algorithm. Thank you very much for your time in answering. Have a nice day. :)

The Linux kernel has a huge source code, with about 3.2 million lines of code. Source code is totally text, so this can give you an idea about the level of compression that is possible. The entire source code is distributed as a .tar.xz file. Its size is close to 110 megabytes. This offers great compression. Decompress it and see the difference in file size!


algorithms, number of instructions in the code How many instructions as a function of the input size N?

int count=0;
for (int i=0; i<N; i++)
  for(int j=i+1; j<N; j++)
    if(a[i] + a[j] ==0)
       count++;

# of "less than" compare instructions  = 1/2(N+1)(N+2)   Can someone pl. explain why there is 1/2 multiplier?

# of "equal to" compare instructions = 1/2 * N * (N-1).
The same here why is there 1/2 * (N-1). Shouldn't it be just N?

also when do we increment j++?, after count++ or after we increment i?

Thank you!

The factors of $\tfrac12$ come from the fact that $1 + \dots + N = \tfrac12N(N+1)$.

j is incremented at the end of the loop. This is standard syntax for languages such as C and Java.


Expected Linear time Minimum Spanning Tree algorithm I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".

My findings:
I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.

Question:
In the original paper Section 3: The Algorithm "Step 2" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."

If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?

Nothing in particular happens if there is an isolated vertex. The algorithm is correct even if $H$ consists of no edges, or if it consists of all edges. The algorithm proceeds by finding a minimum spanning forest on $H$, and using it to prune the contracted graph. IF $H$ consists of no edges, then nothing is pruned, but the algorithm remains correct - this only affects the running time.

Note also that the algorithm is for the more general minimum spanning forest problem. Hence there is absolutely no problem if the graph is not connected. The algorithm will find a minimum spanning tree in each connected component.


Uncomputability of Busy Beaver Function https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S.28n.29_and_.CE.A3.28n.29
So this is wikipedia's proof of why Busy Beaver Function is uncomputable. But I don't get two things.

How do you know that < Create_n0 | Double | EvalS | Clean > has $N$ states? I understand that < Create_n0 | Double | EvalS > has $N$ states but I don't understand why adding Clean doesn't change the number of states.

Why do we need to make a Double function? Can't we prove like this: Let's say the Turing machine < EvalS | Clean > has $n_0$ states. Let $\textrm{BadS}$ denote < Create_n0 | EvalS | Clean >. $\mathrm{BadS}$ has $n_0$ states but has more than $S(n_0)$ shifts, therefore, contradiction.

Here's a simple proof of the non-computability of the Busy Beaver function:

Assume BB is computable. Then we can build a program that accepts a TM specification M and input x. Compute n = BB(|M|), where |M| is the number of states of TM M. Next, simulate M(x) for n time-steps. If M(x) halts, accept. If after n time-steps M(x) has not halted, reject. This program solves the Halting-Problem, a contradiction - QED.


ML function of type 'a -> 'b Our professor asked us to think of a function in OCaml that has the type

'a -> 'b

i.e. a function of one argument that could be anything, and that can return a different anything.

I thought of using raise in a function that ignores its argument:

let f x = raise Exit

But the professor said there was a solution that doesn't require any function in the standard library. I'm confused: how can you make a 'b if you don't have one in the first place?

 I'm asking here rather than on Stack Overflow because I want to understand what's going on, I don't want to just see a program with no explanation.

First, some remarks. Using only the core typed lambda calculus it's not possible to obtain 'a -> 'b because the typing system is in correspondence (via the Curry Howard isomorphism) to intuitionistic logics, and the corresponding formula A → B is not a tautology.

Other extensions such as tuples and matchings/conditionals still preserve some logic consistency adding product types * which correspond to the logical connective and, and sum types | which correspond to the or. Again, don't expect them to produce that 'a -> 'b type, as it would allow one to prove some formula which is not a tautology.

So your only chances are using other constructions which escape from the logics like raise (but you're not allowed to in this case)… or let rec! Recursion allows to build programs which never terminate, and their results can be given an arbitrary return type as they will never be produced. Now if you think about the most trivial non terminating function (the one which directly calls itself to return a result):

let rec f x = f x

You'll notice that its type is exactly 'a -> 'b: whatever is the provided argument, the result (which will never be computed) can be assumed to have any type.

Of course this f is not an interesting function, but that's the point. In OCaml, any function whose type does not look like a valid formula is a suspicious function.


"Definition of NP via relations and quantifiers; not via NTMs" I have the following question on an assignment, and despite asking my prof, I can't get a grasp on it..

  Let $L_1, L_2$ be languages in ${\sf NP}$. Using the definition of ${\sf NP}$ via relations and quantifiers (not the non-deterministic Turing machines) prove that the following language is in ${\sf NP}$:  $L=\{ x | x \in L_1 \text{ or } xx  \in L_2 \}$, where $xx$ is two concatenated copies of $x$.

Her notes say the following on this:

  Let $L\subseteq\Sigma^{*}$. We say $L\in{\sf NP}$ if there is a two-place predicate $R\subseteq\Sigma^{*}\times\Sigma^{*}$ such that $R$ is computable in polynomial time, and such that for some $c,d\in\mathbb{N}$ we have $\forall x\in\Sigma^{*},x\in L\iff\exists y\in\Sigma^{*},|y|\leq c|x|^d$ and $R(x,y)$.

I would imagine that this is a well known definition (though possibly worded differently)... but I don't know where else I can get details on it. My textbook has a somewhat similar definition, but it doesn't talk about this $c,d\in\mathbb{N}$ stuff..

  A verifier for a language $A$ is an algorithm $V$, where
  $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$
  We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

The $y$ in the first definition is supposed to be analogous to $c$ in the second; it is a certificate or witness used by the verifier. But that's all I can understand between the two.

Now... what I think I know about this question is that $R(x,y)$ is supposed to be a verifier for $L$, while $R_1(x,y_1)$ is a verifier for $L_1$ and $R_2(x,y_2)$ is a verifier for $L_2$. She said something about $y=\langle y_1, y_2\rangle$ being an encoding of the two certificates for the verifiers $R_1$ and $R_2$. But from there I'm lost. I have no idea how to answer this question even after asking for help two or three times.

Anybody here able to help? Thanks in advance.

I think I just realized, after finding a similar problem online, that this is asking to simply show that ${\sf NP}$ is closed under union. Can anybody give any insight into whether or not this is a proper solution, or if I'm missing anything? I mostly understand my answer, but I don't really know what I'm doing with the $c$ and $d$ constants... I put them in there because I feel like I'm going to need to.

  This question is asking to prove that ${\sf NP}$ is closed under union. It is the same as asking if $L=L_{1}\cup L_{2}$ is in ${\sf NP}$.

  Since $L_{1}$ and $L_{2}$ are both in ${\sf NP}$, it follows that they both have polynomial time verifiers $R_i(x_i,y_i)$ that evaluate to true when $y_{i}$ is a valid certificate/witness for $x_i\in L_i$, where $i\in \{1,2\}$.

  To show that $L=L_1\cup L_2$ is also in ${\sf NP}$, we need to construct a polynomial-time verifier $R(x,y)$. The certificate $y=\langle y_1,y_2 \rangle$ for $L$ will be an encoding of the two certificates $y_1$ and $y_2$ in such a way that $R(x,y)$ evaluates to true when $\displaystyle\bigvee_{1\leq i\leq 2} R_i(x,y_i)$ evaluates to true.

  Given that $R_{i}(x_i,y_i)$ for $i\in\{1,2\}$ are polynomial time verifiers with running time $O(c_i|x_i|^{d_i})$ for some $c,d\in\mathbb{N}$, $R(x,y)$ will have a running time of at most $O(2\cdot max(c_i)|x|^{max(d_i)})$, which is still polynomial. Therefore, $L\in {\sf NP}$.


How does an enumerator for machines for languages work? In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :

"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks."

How exactly do you do what he is talking about for any r.e. collection of functions/languages (or complexity class like P)--enumerate the machines that solve the languages in the collection? Normally, when speaking about an enumerator, you talk about enumerating the words of a language, not a collection of languages.

Kozen answers this in your quote: what you enumerate is Turing machines that accept all languages in P. This makes sense in many contexts, for example if you want to diagonalize against all languages in P.

It is not a priori clear how to enumerate P (as Turing machines). The problem is that given a Turing machine, it is (provably) impossible to tell whether it halts in polynomial time. The trick is to force the machine to halt in polynomial time.

The enumerator goes over all pairs $(T,p)$, where $T$ is a Turing machine and $p$ is a polynomial. For each such pair, it creates a new machine $M(T,p)$ which simulates $T$ for $p(n)$ steps (where $n$ is the input length), and then halts. The machine $M(T,p)$ is guaranteed to run in polynomial time, and so whatever language it accepts is in P. Conversely, for any P-time machine $T$, there is a polynomial $p$ such that $T$ and $M(T,p)$ are equivalent, and so the enumerator goes over all languages in P.


Finding trading cycles Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

person 1 has item A, C, D, and wants item F

person 2 has item B, C, and wants E

person 3 has item E, and wants G
...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.
So my question would be:

How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.

I'm assuming that items are always traded 1-for-1.

  How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?"

If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete.  If you are open to having multiple disjoint cycles of exchange and just looking for as many items as possible involved in the exchange, then it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature, and it is solvable in polynomial time.

P. Biro, D. F. Manlove, and R. Rizzi. Maximum weight cycle packing in
directed graphs, with application to kidney exchange programs. Discrete
Mathematics, Algorithms and Applications, 1(04):499–517, 2009.


Is Timsort more efficient than merge sort and why? I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.

In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements.

Given a particular input, a particular implementation of timsort may or may not be faster than a particular implementation of merge sort.

Timsort is designed to have a maximum overhead over merge sort, i.e. it won't be more than a certain constant factor slower than merge sort, because it's based on merge sort, and only uses other techniques for small parts of the data.

Timsort uses insertion sort for very small amounts of data; this is typically more efficient than a pure merge sort because the benefits of merge sort over insertion sort are asymptotic. Merge sort is asymptotically faster than insertion sorts, which means that there is a threshold $N$ such that if $n \ge N$ then sorting $n$ elements with merge sort is faster than with insertion sort. The numerical value of threshold depends on the specific implementations though. With typical optimized implementations, insertion sort beats merge sort for a small amount of data. Most sort routines in the real world are hybrid, using an $O(n \log n)$, divide-and-conquer technique for large amounts of data and using a different technique (usually insertion sort) when they've broken down the data into small enough pieces. Thus a properly implemented timsort is faster on average than a pure merge sort.

Timsort is furthermore optimized to deal well with real-world data. Real-world data is not randomly distributed: it's common to have sorted runs in the data to be sorted. Compared with a basic merge+insertion sort, timsort attempts to detect and make use of such runs. This adds a small overhead of checking whether parts of the data are already sorted, but with typical real-world data this saves some actual sorting work which more than compensates.


Infinite Boolean circuits as a model of computation Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a Turing machine that can output, for some input length N, the correct Boolean circuit for that N.

However, I wonder if it is instead possible, if not a bit abstract, to instead look at finite Boolean circuits that "converge" to some well-defined infinite circuit in the large limit of N, which can handle any input size of arbitrarily large but finite length, and get an equivalent model of computation.

My intuition is that this is often the case, because it is quite common for Boolean circuits to be able to handle not only their own input size, but all smaller input sizes as well. For example, an adder that works on inputs of N bits can handle inputs of length < N by zero-padding the highest undefined bits; this is equivalent to setting the undefined bits to zero by default. So we can easily imagine this series of circuits converging to something like ripple adder extending infinitely to the left, and for which we consider only those inputs with finitely many nonzero bits.

What I am really trying to understand is the simplest way to extend the notion of Boolean circuit to get something that is Turing-complete. For example, we can give a finite state machine an infinite queue and make it Turing complete. By looking at infinite Boolean circuits that can handle arbitrarily large input with finite support, can we likewise obtain Turing-completeness, with an analogue of the halting problem, etc? If not, how could we do it?

Your idea is equivalent in power to non-uniform circuits.  Thus, it doesn't formalize the concept you want it to formalize.  You were hoping that your notion of an infinite circuit would capture the power of uniform circuits / Turing machines, but it doesn't -- like non-uniform circuits, it is "too powerful" (more powerful than any uniform model).  Thus an infinite circuit is essentially still a non-uniform model of computation, even if it doesn't look like it on the surface.

Consider the following infinite circuit $C$: if the $i$th bit of the input is 1 and the $i+1$st bit is 0, then the $i$th output bit is $c_i$, otherwise that output bit is 0.  Here $c_i$ is a constant that is 1 if the $i$th Turing machine (in some canonical enumeration of all Turing machines) halts, or 0 otherwise.

This circuit is an infinite circuit, in your sense.  You can think of it as a sequence of circuits $C_1,C_2,\dots$, where $C_N$ is the circuit that takes $N$ bits of input and produces $N$ bits of output, obtained by zero-padding its input and feeding that to $C$.  Thus that sequence of circuits "converges" to $C$.

However, $C$ has the following peculiar property: given $C$, you can solve the halting problem.  In particular, if you feed in $i$ in unary as input to $C$, then the output will indicate whether the $i$th Turing machine halts or not.  Thus, infinite circuits can solve undecidable problems.  Like non-uniform circuits, infinite circuits are in some sense "too powerful" -- they're not realistic.

So your construction doesn't really eliminate any of the issues with the non-uniform circuit model.  It just recreates them, in a slightly different guise.

A separate challenge with your infinite circuit idea is that it is not clear how to handle circuits that produce a single bit of output.  Normally, in circuit complexity, we study circuits that take $N$ bits of input and produce a single bit of output.  It's not clear how such a sequence of circuits can "converge" to a single infinite circuit (what is its single output bit, and how is it computed?).


Do all DFA's containing an "accepting path containing a cycle" accept infinite languages? So I've seen this claim being made on different questions:

Do self-loops in DFA cause infinite languages?

I'd like to find formal proof for this.

I think I should also note that an "accepting path containing a cycle" is probably defined as a path in a graph so that the states in the DFA  are  nodes in the graph and there must be a cycle and at least one accepting state in that path.

If the DFA contains a path from the start node to an accepting state that contains a cycle, then the DFA is an infinite language.  The proof is easy: you can go around the cycle as many times as you like.  Depending on how many times you go around the cycle, you get a different word accepted by the DFA; the more times around the cycle, the longer the word (so it has to be different from any word where you went around the cycle a different number of times). There are infinitely many possibilities for how many times you can choose to go around the cycle, so infinitely many words accepted by the DFA.


Can we define the Functor Category in Haskell (or any other language with a more expressive type system)? Here I am talking about the Functor category, which is defined as a category whose objects are functors and morphisms are natural transformations.

For reference: https://ncatlab.org/nlab/show/functor+category

I was wondering if it is possible to define this in Haskell.

If we define category like this:

class Category cat where
   id :: cat a a
   (.) :: cat b c -> cat a b -> cat a c

Now how do we define Functor as an instance of this, given that Functor is itself a typeclass?

EDIT

I am not tied to the above definition of a Category. I see Edward Kmett represents a Category like this:

newtype Yoneda (p :: i -> i -> *) (a :: i) (b :: i) = Op { getOp :: p b a }

type family Op (p :: i -> i -> *) :: i -> i -> * where
  Op (Yoneda p) = p
  Op p = Yoneda p

class Vacuous (a :: i)
instance Vacuous a

class Category (p :: i -> i -> *) where
  type Ob p :: i -> Constraint
  type Ob p = Vacuous

  id :: Ob p a => p a a
  (.) :: p b c -> p a b -> p a c

I am not looking for Haskell specific implementation, but in any functional language in general.

Ed Kmett has actually defined this in his Hask library. The trick is to define a natural transformation as a data type and encoding the functors that this natural transformations map, in the type level like this:

class (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f
instance (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f

data Nat (p :: i -> i -> *) (q :: j -> j -> *) (f :: i -> j) (g :: i -> j) where
  Nat :: ( FunctorOf p q f
         , FunctorOf p q g
         ) => {
           runNat :: forall a. Ob p a => q (f a) (g a)
         } -> Nat p q f g

Now he defines the Natural transformation as instances of a Category like this:

instance (Category' p, Category' q) => Category' (Nat p q) where
   type Ob (Nat p q) = FunctorOf p q
   id = Nat id1 where
     id1 :: forall f x. (Functor f, Dom f ~ p, Cod f ~ q, Ob p x) => q (f x) (f x)
     id1 = id \\ (ob :: Ob p x :- Ob q (f x))
   observe Nat{} = Dict
   Nat f . Nat g = Nat (f . g)
   unop = getOp

All of this can be found here: https://github.com/ekmett/hask/blob/master/src/Hask/Category.hs


Is Finding A Hitting Set of Size n/2 NP-Hard? In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E.

In decision version of the problem, we are asked if there exists a hitting set H of size at most k.

This problem is known to be NP-hard. However, I wonder if the problem is still NP-Hard when are asked if there exists a hitting set whose size is strictly less than n/2, i. e., at most n/2 - 1, (where n is the size of V).

I'm currently working on another problem and I'm convinced that the problem is NP-hard. So I'm trying to find a reduction. I've realized that if the above problem is NP-hard, then I am done.

Any help is appreciated.

I think the easiest way is to reduce

  $ VC_{n/2}=\{G∣G=(V,E) $ has a vertex cover of size $|V(G)|/2\}.$ ( https://cs.stackexchange.com/a/90487/72705)

to

$ HS_{n/2}=\{(S,F)∣\exists H\subseteq S: $$H$ is a HS of $F$ of size at most $|S|/2 $$\}$.

In  https://cs.stackexchange.com/a/90487/72705 , they show that $VC_{n/2}$ is $NP$-hard.

Now, we reduce $VC_{n/2}$ to $HS_{n/2}$, which is the standard reduction from normal $VC$ to $HS$:

$S = V$
$F = E$, where $E:= \{e_1,e_2,\ldots,e_m\}$ with $e_i = \{v_j, v_k\}$ and $v_j, v_k \in V$

Clearly, this reduction can be done in poly. time and is correct, as one element in $F$ corresponds to one edge in $E$, so the HS can be mapped one to one to the vertex cover set and vice versa.

As you can see, the vertex cover set has the same number of elements as the corresponding hitting set (if there exists one). Also, $|S| = |V|$. Therefore, the Vertex Cover Set of size $|V|/2$ gives a HS of size $|S|/2$. To get a HS of size $(|S|/2) -1$, one could add two completely new elements $\alpha, \beta$ to $S$ (let this be $S'$) without changing $F$. Therefore, $\alpha$ and $\beta$ will never be in the HS of $F$, but the Hitting Set now has a size of $|S|/2 = (|S'| -2) / 2 = (|S'|/2) -1$.


Methods of finding a PDA I am working on finding a PDA that accepts the following language:

L = {0^i 1^j 0^k 1^l | i < j and k < l}

I am having trouble figuring out how to break this down/ where to start. I am able to form simpler PDA's such as when there are twice as many 0's as 1's but am drawing a blank on what approach to take to begin to solve.

Are there any methods or algorithmic approaches to forming a PDA for a given language?

edit: this is NOT a duplicate of the question that was flagged, that question asks how to determine if a grammar is context-free, this is completely different.

So far I have developed this PDA but for some reason it accepts 0101 which should fail, I haven't figured out how it manages to pass through the first portion from the first accepting state:

If you can find a PDA for the language $L_0 = \{ 0^i 1^j : i < j \}$, then you can probably find a PDA for your language as well, which is just $L_0^2$. Hence I suggest the following plan:

Figure out a PDA for $L_0$.
Figure out a general construction that, given PDAs for languages $L_1,L_2$, outputs a PDA for their concatenation $L_1 L_2$.
Apply the construction to the PDA you found in the first step.


Arithmetic Encoding vs Adaptive Arithmetic Encoding I am working on a personal project and I am having some conceptual level questions on arithmetic encoding.

Let's take a scenario where I have an array of sensors and the data collected is transmitted over the internet to Alice. Naturally to decrease transmission cost I would want to transmit data in compressed form. But the data source is non stationary in nature and I have read that we use Adaptive Arithmetic Encoding in such scenario. But I can do this trick that, collect sensor data in a fixed size buffer and when buffer is full then use Normal Arithmetic Encoding and send the encoded sequence over the internet. So my question is why would I want to use Adaptive Arithmetic Encoding in this scenario and what advantage will it serve me? If the above stated scenario is not applicable please explain using other example.
Have I understood both the concepts correctly? (By checking algorithms of both and please point out mistakes if any)

    Arithmetic Encoding

    start
        statistical_model = collect_stats(data) //we need to perform single pass over data to collect stats
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = artimetic_encoding(probability_distribution, previous_state)
        return current_state
    end

    Adaptive Arithmetic Encoding

    start
        statistical_model = init() // initialize the model in such a way which is known to both encoder and decoder (for example: zero initialization)
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = adaptive_artimetic_encoding(probability_distribution, previous_state)
            update_model(statistical_model, symbol)
        return current_state
    end

The pseudocode looks good to me, except of course that in static arithmetic coding, you need to transmit the model before the decoder can use it.
Exactly how to do that in a space-efficient way is not obvious. One of the advantages of adaptive coding is that it gives you that for free: the loss of compression while the model is "learning" should be (if you did it correctly) exactly the minimal cost of transmitting the model.
But, of course, it's not free because updating an adaptive model isn't free. You pay for it in the CPU and memory efficiency of the encoder and decoder.


Is there any difference between these two languages? If I have the following two languages:

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

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

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

Yes there is. $w \in \{ a, b\}$ means that $w$ may be either $a$ or $b$, while $w \in \{ a, b\}^*$ means that $w$ may be a string over $a$ and $b$ including the empty string $\epsilon$. In particular $L_1$ is a language having only $a$ and $b$, i.e, $L_1 = \{a, b\}$.


How do confluently persistent data structures handle merge conflicts? From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and also disallowing the remerging of these branches.

       o o o
      /
o o o o o o o o o
  \
   o o o

Confluently persistent data structures on the other hand seem to allow the merging of these branches even though over time they may accumulate conflicting modifications to the contents of their given nodes.

o o o o o o o o o o o o
  \
   o o o o o x x x
      \     /
       o o o

I think I've searched the given research for an algorithm about how to potentially handle merge conflicts arising from this situation but have come up with nothing. Real world examples like git appear to punt this question to the user for manual resolution. Is this really the only option? Thanks for reading!

Typically, confluently persistent data structures are built so that they will never have a merge conflict.  The details differ for each such data structure, but here are the broad outlines.  Basically, you define a semantics for what you want to happen during a merge, then devise a data structure with those semantics.  (The desired semantics depends on the kind of data stored in the data structure; there's no single answer.)

So what's a merge conflict?  A merge conflict arises when your semantics for the merge throws up its hands and says "I don't know what to do".  But normally, when we design confluently persistent data structures, we typically define merge semantics where that will never happen.  In other words, the semantics are well-defined for all possible cases.   Merge conflicts are only necessary when there are situations where the semantics aren't well-defined.

Why does git have merge conflicts?  Because it is a general-purpose tool used to store arbitrary data with unknown meaning/semantics.  Therefore, we can't know what the "right" semantics for merging is, in general.  But confluently data structures are typically designed for a narrower, more specific purpose.  Think, for instance, of a set; that has a well-defined semantics, and we can define a merge operator that fully specifies what the result of merging two sets should be for all possible cases.  So, it's feasible to define merge semantics that are well-defined for all possible cases, when the data structure handles such a specific, well-defined kind of data. Git has to deal with a harder problem, where it might not be possible to define a useful, sensible merge operator that is defined for all possible cases.


Why isn't chess an impartial game? In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games.  To be impartial, a game must satisfy these conditions:

(1) The game is finite; i.e. there is a constant $c$ such that all games end in $c$ moves or fewer.

(2) There are no draws; either player 1 or player 2 wins.

(3) The rules of the game draw no distinction between the players.  That is, given any position, if we switch the active player then the set of legal moves is still the same, and the player who wins the game under perfect play switches.

It is often said in introductory CGT resources (here for example) that a major class of games that violate condition (3) are those in which each player has their own piece set.  For example, chess violates (3) because the white player can only move the white pieces and the black player can only move the black pieces, so if we switch the active player then the set of legal moves changes.

However, it seems to me that this problem can be circumvented by the following trick.  Instead of defining a "position" as the locations of the white and black pieces, we define a position as the locations of the active player's pieces and the passive player's pieces.  Now the conditions in (3) are satisfied.

This trick seems too simple to be original, though, and I have read in many places about how chess is a classic example of a partisan game.  So what am I missing?

Aside: To circumvent (1) and (2), we need to modify chess in some reasonable way; i.e. forbid 3x repetition of a single position and declare stalemate to be a win for the stalemating player.  But that's beside the point of my question.

Years-later edit since this question has gotten some random attention lately: neither of the answers really understood the point of the question (which is probably my fault for an unclear OP).  My current understanding is that there is indeed a natural isomorphism between finite drawless chess and an impartial game, but impartiality is not a property that is always preserved under isomorphism, and my misunderstanding came from the assumption that it was.

Chess violates all three conditions, so I don't really understand what there is to ask.

(1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game under certain circumstances, they do not oblige the player to do so.

(2) The game has draws.

(3) As you have observed, the game definition distinguishes between the players. Your "active player" trick doesn't work because you've turned chess into a one-player game: the "active" player makes every move and the "inactive" player is a spectator.


Proving equivalence of two substitutions by induction I'm trying to prove the following reduction:
$$
     t\{x:=u\}\{y:=v\} = t\{y:=v\}\{x:=u\{y:=v\}\}
$$
under the following assumptions:

$x \neq y$
$x$ is not a free variable of $v$ (in symbols, $x \notin \operatorname{fv}(v)$).

My idea is to do it by induction, but I'm a bit stuck with the base case. I would appreciate if someone can explain to me how to write such a proof. I'm including what I tried, which is wrong or incomplete.
Base case: $t = m$ is just a variable.
On the left side we have:
if m = x ⟹ u{y:=v} (if u=y then v else u)
else     ⟹ m{y:=v} (if m=y then v else m)

On the right side we have:
if m=y ⟹ v{x:=u{y:=v}} (if u=y then v{x:=v} else u{x:=u}
  so we get either (v=x ⟹ v else v) or (u=x ⟹ u else u)
else   ⟹ m{x:=u{y:=v}} (if m=y then m{x:=v} else m{x:=u}
  so we get either v or m

I understand we end up getting the same four branches, but is that considered really a proof? Is this the proper way to write such a proof and conclude the base case? Also, the given assumptions didn't help much here, so I think I'm missing the part where I need to use those assumptions...
I think once the base case is proven, we can do the following:
Case $t = t_1t_2$:
$$t\{x:=u\}\{y:=v\} \Longrightarrow t_1t_2\{x:=u\}\{y:=v\}
\Longrightarrow \\ t_1\{x:=u\}\{y:=v\} t_2\{x:=u\}\{y:=v\},$$
and we have just proven in the base case that
$t_1\{x:=u\}\{y:=v\} = t_1\{y:=v\}\{x:=u\{y:=v\}\}$  and  $t_2\{x:=u\}\{y:=v\} = t_2\{y:=v\}\{x:=u\{y:=v\}\}$,
so
\begin{align}
&t_1\{x:=u\}\{y:=v\} t_2\{x:=u\}\{y:=v\} \\ =& t_1\{y:=v\}\{x:=u\{y:=v\}\} t_2\{y:=v\}\{x:=u\{y:=v\}\} \\
= &t_1t_2\{x:=u\}\{y:=v\} \\ = &t_1t_2\{y:=v\}\{x:=u\{y:=v\}\}.
\end{align}
Now only case left is $t= \lambda m . t$.
So we have $(\lambda m . t)\{x:=u\}\{y:=v\}$,
which can be directly re-written as $\lambda m . t\{x:=u\}\{y:=v\}$, which is the base case again...
Could someone please help me finish this proof correctly and explain to me the right way to do it?

First, let us show that the two assumptions are necessary. Here is an example showing what goes wrong when $x = y$. Take $t = x$, $u = 1$, $v = 2$. We have
$$
x\{x := 1\}\{x := 2\} = 1\{x := 2\} = 1,
$$
whereas
$$
x\{x := 2\}\{x := 1\{x := 2\}\} =
2\{x := 1\} = 2.
$$
Next, here is an example showing what goes wrong when $x$ is not free in $v$. Take $t = y$, $x = 1$, $y = x$. We have
$$
y \{x := 1\}\{y := x\} = y\{y := x\} = x,
$$
whereas
$$
y \{y := x\}\{x := 1\{y := x\}\} =
x\{x := 1\} = 1.
$$
Now let's do the base case more carefully. The term $t$ is just a variable. We have to consider three possibilities: $t=x$, $t=y$, $t \neq x,y$.
If $t=x$ then $t\{x := u\} = u$, and so the left-hand side is $u\{y := v\} = u\{y := v\}$. On the other hand, $t\{y := v\} = x$ (since $x \neq y$), and so the right-hand side is $x\{x := u\{y := v\}\} = u \{y := v\}$.
If $t=y$ then $t\{x := u\} = y$ (since $y \neq x$), and so the left-hand side is $y\{y := v\} = v$. On the other hand, $t\{y := v\} = v$, and so the right-hand side is $v\{ x:= u\{y := v\} \} = v$, since $x$ doesn't appear freely in $v$.
Finally, if $t \neq x,y$ then both sides are just equal to $t$, since the substitutions have no effect.
Next, the rest of the proof. The proof for function application is essentially as you wrote it. Let us denote the left-hand side by $L(t)$ and the right-hand side by $R(t)$. If $t = t_1t_2$ then
$$
L(t) = L(t_1) L(t_2) \stackrel{(\ast)}= R(t_1) R(t_2) = R(t),
$$
where $(\ast)$ is due to the induction hypothesis.
Finally, we need to handle abstraction. Let $t = \lambda m.s$. Applying $\alpha$-conversion, we can assume without loss of generality that $m \neq x,y$. This implies that
$$
L(t) = \lambda m.L(s) = \lambda m.R(s) = R(t).
$$
To see why $\alpha$-conversion is necessary, try doing the proof when $m=x$ or $m=y$. The case $m=x$ works out fine, but you will encounter a problem when $m=y$.


Is the language of all deciders recognizing empty language decidable? I TA for a course in theory of computation and this came up as an interesting question.

$E_{TM}$ is the set of TM descriptions where the machine's language is empty.

Of course, $E_{TM}$ is undecidable for arbitrary TMs (as well as $A_{TM}$).

Now suppose we restrict our attention to decider TMs (ones that always halt).

$A_{decider}$ is the set of TM decider descriptions and strings such that the TM accepts that string, and $E_{decider}$ is the same as $E_{TM}$ except for deciders.

Of course, $A_{decider}$ now is decidable because we just simulate the decider on the input, and it will always stop.

Is $E_{decider}$ decidable now, or does it remain undecidable?
The reduction to show that $E_{TM}$ was undecidable originally goes in the wrong direction here.

$E_{decider}$ is even unrecognizable.

Suppose a TM $E$ recognizes $E_{decider}$, we construct a TM $N$ recognizing $\overline{H}=\{\langle\langle M\rangle, w\rangle\mid M(w) \text{ doesn't halt}\}$, which is known as unrecognizable, thus a contradiction. $N$ works as follows.

On input $\langle\langle M\rangle, w\rangle$:

Construct a TM $M_w$ working on input $x$ as follows

Run $M$ on $w$ with at most $|x|$ steps.
If $M$ halts, loop; otherwise, reject.

Run $E$ on $\langle M_w\rangle$.
If $E$ accepts, accept; otherwise, reject.

If $M$ halts on $w$, then there exists some $x$ such that $M_w$ does not halt on $x$, which means $M_w$ is not a decider. Therefore $E$ does not accept $M_w$, so $N$ does not accept $\langle\langle M\rangle, w\rangle$.

If $M$ does not halt on $w$, then $M_w$ halts and reject any string $x$. Therefore $E$ accepts $M_w$, so $N$ accepts $\langle\langle M\rangle, w\rangle$.

Now the proof is complete.

In addition, your argument about $A_{decider}$ is wrong, because the TM in input may not be a decider and you should reject (not loop) on such case. In fact, you can prove $A_{decider}$ is also unrecognizable using similar technique.


Why can PDAs only write one symbol to the stack according to this definition? This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser.

The transition is defined as
$$
\delta: Q\times \Sigma_\varepsilon \times \Gamma_\varepsilon \to P(Q\times \Gamma_\varepsilon)
$$
where $Q$ is the set of states, $\Sigma = \Sigma_\varepsilon\cup \varepsilon$ is input alphabets, and $\Gamma_\varepsilon = \Gamma_\varepsilon\cup \varepsilon$ is the stack alphabets.

I think $\Gamma_\varepsilon$ in the co-domain of the transition should be replaced with $\Gamma_\varepsilon^*$; otherwise, I don't see how this definition can pop/push from/onto its stack.

Please help me clarify this.

The addition of $\epsilon$ to the alphabets allows the pop and push operations. For example, if you want to push the letter $a$ in state $q$, without reading anything from the input, you can have the transition $\delta(q,\epsilon,\epsilon)=\{(s,a)\}$, where $s\in Q$.

And if you want to pop $a$ without reading anything from the input, you can have $\delta(q,\epsilon,a)=\{(s,\epsilon)\}$.

Of course you can combine the two for a simultaneous pop/push, and you can do that while reading from the input.


What does $|V|=O(|E|)$ mean? I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it says that $O(|V|\log|V|+|E|\log|V|) = O(|E|\log|V|)$, because $|V|=O(|E|)$. What does $|V|=O(|E|)$ mean and why is it so?

First, $|V|$ is the number of vertices and $|E|$ is the number of edges.

The point is that if a graph is connected it must have at least $|V|-1$ edges.  Therefore, $|V|\leq |E|+1$, so
$$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$

Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about what happens as some variable becomes large, over some infinite family of instances.  So, here, we're supposed to imagine that the infinite family of instances is the set of all connected finite graphs. It would have been clearer to just write $|V|\leq |E|+1$.


Expected number of updates of minimum I came across the following problem in a exam.

We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ initially. Now during our inspection if we see a smaller value than MIN, then MIN is updated to the new value.

For example, if we consider the permutation,

$$5\ 9\ 4\ 2\ 6\ 8\ 0\ 3\ 1\ 7$$
the MIN is updated 4 times as $5,4,2,0$. Then the expected no. of times MIN is updated?

I tried to find the no. of permutations, for which MIN is updated $i$ times, so that I can find the value by $\sum_{i=1}^{n}iN(i)$, where $N(i)$, is the no. of permutations for which MIN is updated $i$ times.

But for $i\geq2$, $N(i)$ is getting very complicated and unable to find the total sum.

The trick is to use linearity of expectation. Let $E_k$ be the event that the $k$th input is a left-to-right minimum (i.e., requires an update), and let $X_k$ be an indicator variable for $E_k$, that is, $X_k$ is $1$ if $E_k$ happens and $0$ otherwise. Let $U = X_1 + \cdots + X_n$ be the number of updates. The expected number of updates is
$$ \mathbb{E}[U] = \sum_{k=1}^n \mathbb{E}[X_k] = \sum_{k=1}^n \Pr[E_k]. $$
It remains to compute $\Pr[E_k]$. We can construct a random permutation $\pi$ of $[n] = \{1,\ldots,n\}$ in the following way: take a random permutation of $[n]$, and randomly permute the first $k$ elements. This shows that the probability that $\pi(k) = \min(\pi(1),\ldots,\pi(k))$ is exactly $1/k$, and so $\Pr[E_k] = 1/k$. All in all, we get
$$ \mathbb{E}[U] = \sum_{k=1}^n \Pr[E_k] = \sum_{k=1}^n \frac{1}{k} = H_n, $$
the $n$th Harmonic number. It is well-known that $H_n = \ln n + \gamma + O(1/n)$ (Wikipedia contains the entire asymptotic expansion).

We can also compute the variance in this way:
$$
\begin{align*}
\mathbb{E}[U^2] &= \sum_{k=1}^n \mathbb{E}[X_k^2] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \mathbb{E}[X_k X_\ell] \\ &=
\sum_{k=1}^n \Pr[E_k] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell],
\end{align*}
$$
where $\land$ is logical AND. We already know that $\Pr[E_k] = 1/k$. In order to compute $\Pr[E_k \land E_\ell]$ (where $k < \ell$), we follow the same route as before. With probability $1/\ell$, $\pi(\ell)$ is a left-to-right minimum. Given that, the probability that $\pi(k)$ is a left-to-right minimum is $1/k$. Therefore $\Pr[E_k \land E_\ell] = 1/(k\ell)$, and so
$$
\begin{align*}
2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell] &=
2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \frac{1}{k\ell} \\ &=
\left(\sum_{k=1}^n \frac{1}{k}\right)^2 - \sum_{k=1}^n \frac{1}{k^2} \\ &=
H_n^2 - \sum_{k=1}^n \frac{1}{k^2}.
\end{align*}
$$
Therefore
$$
\begin{align*}
\mathbb{E}[U^2] &= H_n + H_n^2 - \sum_{k=1}^n \frac{1}{k^2}, \\
\mathbb{V}[U] &= H_n - \sum_{k=1}^n \frac{1}{k^2} = \ln n + \gamma - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right).
\end{align*}
$$
We can compute all other moments in a similar way using (essentially) the inclusion-exclusion principle and the formula
$$
\mathbb{E}[U^d] = \sum_{i_1,\ldots,i_d=1}^n \prod_{i \in \{i_1,\ldots,i_d\}} \frac{1}{i}.
$$
If we are careful enough then we can probably establish the asymptotic normality of $U$.


why does ${a^nb^n}$ fit the pumping lemma for context-free languages? I am writing somthing about Ppumping Lemma. I know that the language $L = \{ a^nb^n| n ≥ 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string $s = a^pb^p, |s| > p , |vxy| < p \land |vy| > 0$.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?

This language satisfies the conditions of the Pumping lemma. (By the way, your question title is wrong: you are not asking why it is context-free; you are asking why it satisfies the conditions of the lemma, which it does.)

Take the string s=a^mb^m and assume m>0. Don't use p or n, otherwise it is confusing, because those letters are used in the lemma. Now let v="a", y="b", x="", u=a^(m-1), z=b^(m-1).

You can definitely pump it as much as you want. In other words, you take a string such as aaaaaabbbbb, then you pick the two middle letters: aaaa ab bbbb. Then you pump them: aaaa aaabbb bbbb. Still in the language.


Data structure to query intersection of a line and a set of line segments We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries:
Given a query line $l$, report how many line segments in $S$ does it intersect.

It is required that the query should be done in $O(\log{n})$ time. The data structure itself should take up to $O(n^{2})$ storage and be built in $O(n^{2}\log{n})$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit:
Yes it is in $\mathbb{R}^{2}$. By query point I mean the query line dualised into a point on dual plane.

HERE is the solution I did in the homework but it still lose three points on:
(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.