Algorithm to save state of array as it changes There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be retrieved upon querying.

For ex -

Initially, the array is [7, 8, 9]. This is version 1.
Next, 90 was added. Version 2 is [7, 8, 9, 90].
Next, 23 was added. Version 3 is [7, 8, 9, 90, 23].
Next, 90 was deleted. Version 4 is [7, 8, 9, 23].

And so on.

I need to write a function, get_version(ver_num), which returns the state of the array for each version. So, running get_version(3) should return [7, 8, 9, 23].

I have thought of saving incremental changes to the array in each iteration, in the form of an array maybe.

For ex -

[("add", [7, 8, 9]), ("add", [90]), ("add", [23]), ("subtract",[90])]

This will save space but in order to recreate the array for a specific version, I have to iterate over this array until I reach the required version. Is there a way better than this?

Thanks

In the following we assume that whenever we make a delete-operation, the value to delete is guaranteed to exist in the array, and if multiple copies of it exist, we should remove its leftmost appearance.

The problem can be solved in $\mathcal{O}(\log n)$ per update, and in linear time (with respect to the output size) per query with standard persistent trees (tree traversal is linear time). The only issue is that since our ordered set is ordered by index, not value, we need a map (that doesn't have to be persistent) that translates from index to value. To not degrade the complexity, add a two-way link between nodes representing the same value in the current persistent tree and the map. These links are easy to maintain with no overhead.

If the input values are bounded, since the only query we are interested in is outputting the entire list at a specific time, we can improve on this. If the values are at most $m$, and we can use $\mathcal{O}(n + m)$ memory, we can make $n$ operations in $\mathcal{O}(n)$ time, and answer queries in linear time (with respect to the output size). To do this, we store snapshots of the array and the incremental changes between them.

Let $k$ be the highest amount of elements that have been on the current list since we last took a snapshot. We will take a new snapshot when we have deleted at least $\lceil\frac{k+1}{2}\rceil$ elements. This way we only need to apply a linear number of operations (in output size) to produce any array: if the output size is $n$, we apply at most $n+1$ deletions (since $\frac{n + (n+1) + 1}{2} = n+1$), and thus at most $2n+1$ insertions.

How to then produce the array? Start from the latest snapshot before it, then apply all of the insert-operations. Then, for each delete-operation, increment the delete-count of its respective value (stored in an array of size $\mathcal{O}(m)$. Replacing this with a map would give a $\mathcal{O}(\log n)$ overhead to both operations and queries). Then loop through the array produced after all insertions, at each point checking if the delete count of the value there is nonzero. If it is, we delete that value and decrement the count. Otherwise we proceed as normal. This takes linear time in the size of the snapshot and the number of operations we apply, which is linear in the size of the output.

It remains to show that this method of storing snapshots only uses $\mathcal{O}(n)$ memory. We show this by induction: After $n$ operations, the total size of snapshots up to that point is at most $n$. This holds initially, since we have no operations and one snapshot of size $0$. Say the previous snapshot was at time $n_0$ and was of size $s_0$, and now after $a$ insertions and $b$ deletions, we are taking another snapshot. The size of this new snapshot is then $s_0 + (a - b)$, and by induction the total size of snapshots at most $n_0 + (s_0 + (a - b))$. Thus it suffices to prove that $n_0 + a + b \geq n_0 + s_0 + (a-b)$, but this is equivalent to $2b \geq s_0$, which trivially holds, since $2b \geq 2\lceil \frac{s_0 + 1}{2} \rceil \geq s_0 + 1$.


Fastest static associative map Let's say that I wanted to build a key to value associative map where the only requirement was that lookup times were fast.

Once built, the associative map would not allow inserts, deletes, or modifications, so is a static data structure.

What would the best algorithm be for making and using such a thing?

I'm interested to know if there is a provable "best solution", or if it's provably NP-Hard or similar.

Here are some ideas of my own:

Minimally Perfect Hash

My best idea would be to use minimal perfect hashing.  I would find a hashing algorithm that hashes the $N$ known inputs to $[0,N)$, that resulting value being able to be looked up in an array.

I would want to find the computationally cheapest (average time) hashing algorithm for my data set.

However, finding a minimally perfect hash function is a challenging problem already without wanting the computationally cheapest one.

Feature Based Indexing

Another thought I have would be to look at my input and find bits which are differing between items.  For instance, file paths may have a lot of the same characters in them, especially if they are absolute paths to the same deep folder.

I could find where the bits are that matter and make a tree of objects out of them.

The challenge here I think is that I would ideally want a balanced tree, and it might be hard to test all the permutations of bits that actually matter, to make the tree as balanced as possible.

I think Ideally, my hope is that the entire tree could go away, and I could instead take the bits that mattered and make some equation like "xor bit 2 against bit 3 and add bit 5" to come up with an index into an array.

Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $[0,N)$ using only those features.  This is effectively a way of building a perfect hash, where the hash function is expressed as a decision tree applied to the feature vector constructed from the input.

Building the smallest decision tree is NP-hard in general, but there are heuristic algorithms that do a reasonable job.  You might look at the ID3 algorithm, for instance; in many settings it does a pretty good job of building a small (though not necessarily minimal) decision tree.  You can compare that to other ways of building perfect hash functions and see which is computationally more efficient for your particular data set.  Probably the only way to know is to try it out; I'm not sure there is any theory that will give you a definitive answer, as the answer probably depends on characteristics of your dataset that will be hard to model in a theoretical setting.


does the order of the rows matter? from my understanding the truth table is supposed to generate every possible combination of true and false values without the order of the combination taking into account.

however one of my teachers said that their is a particular order to each row that is used to generate multiple combinations.

can you please explain this to me.

"The order of the row don’t matter, as long as you cover every possible combination of input values. Doing this without an order in mind, does not make it incorrect, but it does make it easier to miss some entries. I think your prof is suggesting using a order so you cover all the combinations in a systemic way. What I do, if I have N Boolean inputs for example, I start with the first row have all values assumed false. In the next row, I make the Nth bool true, then only the N-1  true, then both N and N-1 true, then N-2  true with N and N-1 false, and so on. Any such system is fine."
-@Scottk

"@ScottK Summary: you order the rows to be the binary representation of the numbers $0, \dots, 2^N-1$.
"
-@DavidRicherby

"Your prof seems to be wanting you to follow the binary ordering that @DavidRicherby pointed out earlier: either starting with all true or all false. All orders are correct but go with the binary order since that is what your prof seems to be teaching you, and it is was most pros use. There are other useful orderings that engineers use for circuit simplification for example Karnaugh  Maps https://en.m.wikipedia.org/wiki/Karnaugh_map"
-@Scottk


coding theory- perfect codes I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows:

You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$.

I have been using the fact that $C$ is a perfect code so it attains the Hamming bound then saying that it is less than the Hamming bound for $D$, but you get an inequality involving a binomial sum on both sides, which is really messy. I'm not really sure what other properties I can use to work this out. Any help would be really appreciated, thanks

Guidelines for the future: start with reviewing the definitions.

According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w_0$."

OK, but this is cheating.

So let's start with an equivalent definition:

  A code $C$ is perfect if it attains the Hamming bound

what is this Hamming bound? Basically, it's a counting argument. If you have a word $w\in F^n_q$, how many words are there with in $F^n_q$ whose distance from $w$ is at most $e$?
If you do the counting, you will get there are exactly $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ such words. [Why? If the distance is $i$, choose $i$ indices (out of the $n$ possible indices), each such index can get any of the $q-1$ different values from $w$ in that index.]
The bound then says that if we split the universe into disjoint "balls" where each ball contains a center $w$ and all the $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ words within distance $e$ from $w$, we will have at most $$\frac{|F^n_q|}{size(ball)} = \frac{q^n}{\sum_{i=0}^e \binom{n}{i} (q-1)^i}$$ such (disjoint) balls.

A code that attains the Hamming bound means that any word is within distance $e$ of some codeword. That is, if you think on each codeword in $C$ as a center of a ball with radius $e$, then the codewords cover the entire universe: no word in $F^n_q$ is left outside some ball. Note that the distance of this code is $2e+1$: two codewords belong to two different "balls", and each ball is of radius $e$ (in Hamming distance).

But if the entire space is covered with balls, it means that any word is within distance $e$ of some codeword. This is exactly the first definition I wrote in this post. Thus, if you take any other word and make it a codeword, this word already belongs to some ball, so it is within distance $e$ from the center of that ball, and the new code cannot have a minimal distance greater than $e$.


Safety property vs Liveness property If i take a safety property $SP$ and a liveness property $LP$, is it true that the result of their intersection is a safety property (and not a liveness property) ? Why ?

Thanks

No, it is not. If you have a look at the Decomposition theorem for example, then you will find, that there are properties you cannot express as neither a SP or LP, but as an intersection of a SP and LP.

There exist such SP and LP, that their intersection is a safety property. For example the property of all possible traces, the result is again the property of all possible traces. Which incidentally is the only property that is both safety and liveness.


Is it possible to create a regular language from an non regular language? (details inside) I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?

say L is irregular, if we add or remove finite number of words can we create a regular language?

i might be mistaken, but since all regular languages are finite - if we add a finite amount to a non regular language - it still stays non regular, but if we substract, let's say a finite amount from infinity, it is still infinity.

so is it safe to say that in both cases a regular language cannot not be obtained by adding/substracting a finite amount of words?

i was told to ask this question here rather then in softwareengineering.

thank you very much for your help. really curious about that

We have a language $L$ which is non-regular. We subtract a finite subset $S \subset L$ of words in $L$ to get the rest: $R = L \setminus S$.

Assume that $R$ is regular. Since regular languages are closed under union, and finite sets of words are trivially regular, we can construct a language $L' = R \cup S$ which is also regular.

Since $S \subset L$, we have $(L \setminus S) \cup S = L$, thus $L' = L$. But $L'$ is regular while $L$ is not - a contradiction. Thus our assumption that $R$ is regular was wrong.


"Unusual" coupling between a decision problem and a corresponding optimization problem There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case?

  Are there examples where the typical "tight coupling" between a decision problem and the correponding optimization problem breaks down or behaves in an unusual way, e.g. have significantly different complexity?

Or, maybe there is a case where there is a cluster of problems that are all closely related, but the "best" or "definitive" version is not obvious or apparent? Also, I am looking for any survey or broad overview or discussion of this apparent basic connection between decision and optimization problems.

A similar question was asked here, but the answers were highly theoretical and it did not seem to yield any specific or tangible examples.

The answer does indeed depend on how you define a "corresponding" problem.

For example, it is well known 2-SAT is easy ("Given a 2-SAT formula, is it satisfiable?"). However, the optimization problem MAX-2-SAT ("Given a 2-SAT formula, find an assignment maximizing the number of clauses") is NP-hard. Even MIN-2-SAT is NP-hard.

For a given decision problem, you can have "corresponding" optimization problems which are either easy or hard, depending on whether we consider a minimization or a maximization problem. The st-connectivity problem is mentioned in the comments: deciding the existence of such a path is easy, finding a shortest st-path is easy, but finding a longest st-path is hard. Another graph theoretic example is with cuts: computing a minimum cut is easy, but computing a maximum cut is again hard.

You also have decision problems that don't have a corresponding optimization problem, such as primality testing.


Decide if a specific Turing machine halts on a specific string Can you always decide if a specific Turing machine accepts a specific string?

I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which seams to you can.

If this is true, intuitively, it seams it would be implied that HALT could be decided, which is obviously not true.  Otherwise what is the difference?

The problem you are referring to is sometimes known as the Acceptance problem. It is indeed undecidable.

Let me attempt to find the source of your confusion. I assume by linking the other thread you are referring to the following decidable language:

$$
L_{HP-M'-x} =
\begin{cases}
1 &  \text{M' halts on x} \\
0 &  \text{otherwise}
\end{cases}
$$

The reason this language is decidable is because, given any $M'$ and $x$, this language must be either $\{1\}$ or $\{0\}$. In particular, this MUST be a finite language, and ALL finite languages are decidable.

Note that this doesn't mean we can solve the Acceptance problem. Using classical logic, we deduce that either a machine accepts a string or it does not. The hard part is figuring out which case it is! We know that the language is decidable, but we do not know what a machine that accepts this language looks like because we don't know what the language itself looks like.


All soldiers should shoot at the same time When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was that the soldiers stand in a general network instead of a row. I am sure this is a classical problem, but I cannot remember its name. Can you remind me?

The problem is known as Firing squad synchronization problem. The problem itself, is strictly related to finite state automata. Here, each soldier is a finite automaton; you know that the next state of each soldier depends on its current state and the current states of its two neighbors (except for the first and last soldier). The first soldier in this setting can be though of as the soldiers general who is in charge of starting the attack. The last soldier knows it is the last one. No global communication is available; however, a global clock can be used to synchronize the state transitions of the soldiers. The problem require designing a soldier automaton whose goal is for all soldiers to enter the "SHOOT" state on exactly the same clock tick. By the way, the problem can be solved in $\Theta(n)$ time for $n$ soldiers.


A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher Referring to these notes regarding DFS - Click Here

They refer to the following claim that follows Definition 0.2. as observation:

  A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher.

However, I don't really understand why is that obvious or how can it be proved.

I'd appreciate a proof of this claim.

We must prove two directions: (i) if $uv$ is a cut edge, then there is no edge from $v$'s subtree to $u$ or higher and (ii) if there is no edge from $v$'s subtree to $u$ or higher, then $uv$ is a cut edge.

For (i), if there was an edge from $v$'s subtree to $u$ or higher, then the removal of $uv$ would not increase the number of connected components contradicting the fact that $uv$ is a cut edge. To prove (ii), since every path from any vertex in a subtree of $v$ to a vertex that is $u$ (or higher than $u$) must use the edge $uv$, we see that $uv$ is indeed a cut edge.


Is the base of natural logarithms $e$ efficiently computable? Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a polynomial time algorithm that takes a positive integer $C$ as input and outputs a rational number $y$ such that $r−\frac{1}{C}\leq y \leq r+\frac{1}{C}$.
If it is computable, what would the high-level algorithm be? Or how do we argue that it is not computable?

It is not hard to check (for example using a Taylor expansion of $e^x$ at $x=0$) that for all $n \geq 0$,
$$
\sum_{k=0}^n \frac{1}{k!} < e < \sum_{k=0}^n \frac{1}{k!} + \frac{e}{(n+1)!} < \sum_{k=0}^n \frac{1}{k!} + \frac{3}{(n+1)!}.
$$
Moreover,
$$
\sum_{k=0}^n \frac{1}{k!} = \frac{\sum_{k=0}^n \prod_{i=k+1}^n i}{n!}.
$$
This formula gives an algorithm, running in time $\mathit{poly}(n)$, for computing $\sum_{k=0}^n \frac{1}{k!}$. This quantity satisfies your requirements if $\frac{3}{(n+1)!} \leq \frac{1}{C}$, that is, if $(n+1)! \geq 3C$. Since $(n+1)! \geq 2^n$, it suffices to choose $n = O(\log C)$. This gives an algorithm running in time $\mathit{poly}(\log C)$. Since the length of the encoding of $C$ is $\Theta(\log C)$, the resulting algorithm runs in polynomial time.


Firefly algorithm number of objective function calls Reading an article (arXiv) about the Firefly optimization algorithm, it is stated that the objective function is called only once per firefly per iteration, but following both the pseudo-code in the article and some implementations I found online I do not understand why this is the case..

As I understand the following holds:

The objective function is called whenever we want to update the light intensity $I_i$ of firefly $i$
In a given iteration and firefly $i$, for every firefly $j$, if $I_j>I_i$ we move firefly $i$ and immediately re-calculate the intensity.

From this, if the fireflies' intensities are ordered as $1,2,3,\dots,n$, and the updated intensity increases by each movement are small (i.e. each movement will increase the intensity by at most 1), in one iteration the first firefly will move $n-1$ times, the second $n-2$ times,... each movement calling the objective function for a total of $n(n-1)/2$ calls. Where does the figure of $n$ objective calls per iteration comes form?

It seems to me that you are correct. I haven’t read the whole algorithm carefully though. One alternative is that maybe they intend for the movement to be simultaneous, so that the firefly that’s currently being placed moves towards all the bright fireflies at once, then recalculates once for the new position?

But as is, it seems like the pseudo code for the algorithm and the description don’t line up.


Inverting a band matrix I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following:

Here, the area under the blue stripes is the non-zero elements; everything else is zero

Is there an algorithm to invert this kind of matrix that is simple yet more efficient than Gaussian elimination and LU decomposition?

Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did).

Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve a linear system $A x = b$.

Using the algorithm in this paper, a general band-limited matrix $A$ of size $n \times n$ with bandwidth $k$ can be decomposed into triangular $k$-bandwidth matrices $L$ and $U$ in $O \left( k^2 n \right)$ time. From there, $L U x = b$ can be solved quickly in $O(k n)$ time. So overall, the runtime will be $O\left(k^2 n\right)$. As a followup, if $k$ is constant, that means that the system can be solved in linear time (highly useful).


Deadlock vs "Progress" requirement of the solution to the critical section problem I came across following problem:

  Consider following code:

()
{
    [] = ;
    ([]);
    /*   */
    [] = ;
    /*  */
}

  Let flag is declared as Boolean flag[2] and Pi denote one process while Pj denotes other process and i=1-j. Both processes execute concurrently, then does the progress requirement of the solution to the critical section problem satisfied in the above case?

Doubt

The solution says that both processes Pi and Pj can simultaneously execute flag[i]=true and then both may busy wait on while(flag[j]), thus leading to deadlock and hence progress requirement of the solution to the critical section problem is not satisfied.

I know the normal / day to day meaning of "progress" gives us feeling that if there can be deadlock, then there may not be the progress. But Galvin's book defines "Progress" as this:

  If no process is executing in its critical section and some processes
  wish to enter their critical sections, then only those processes that
  are not executing in their remainder sections can participate in
  deciding which will enter its critical section next, and this
  selection cannot be postponed indefinitely.

So I am guessing whether progress has anything to do with deadlock. And whether the code indeed satisfies progress requirement of critical section problem.

and this selection cannot be postponed indefinitely

In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.


Algorithm for shortest continuous line to join N points I have a set of points in a 2D plane. I'm searching for an algorithm that:

Draws a continuous line passing through all the points starting from a
random point.
Optimizes for the minimum total line length in Euclidean distance.
The line should end at the point it started but not cross any
other point more than once.

In plain terms, suppose we had a paper with N dots on it. We'd take a pencil starting from a random point and try to go through all the points without lifting the pencil and conclude by reaching the point we started at.

I looked into Euclidian minimum spanning tree, but what I'm looking for is a closed loop and not a graph-tree like line. What I'd like in approximation is a Convex Hull that would go through all the points and not just form the perimeter.

Can someone direct me to the right family of algorithms?

Turns out what I'm looking for is the Travelling salesman problem.


Reducing max flow to bipartite matching? There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item to be matched, then add appropriate edges.

There's certainly a way to reduce maximum flow to maximum bipartite matching in polynomial time, since both of them can be each individually be solved in polynomial time. However, is there a "nice" polynomial-time reduction from max-flow (in general graphs) to maximum bipartite matching?

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs.

In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows: the input is a graph (in our case, a bipartite graph), $G=(V,E)$, and a set of integral demands for each vertex, with the demand of vertex $v$ denoted by $b_v$. The goal is to find a largest possible set of edges $S$ such that no vertex $v$ has more than $b_v$ edges in $S$ incident on $v$. It is a simple exercise to generalize the reduction from bipartite matching to maximum flows and show a similar reduction from bipartite $b$-matching to maximum flows. (One of) the surprising result(s) of Madry's paper is that in some sense these problems are equivalent, giving a simple reduction which reduces maximum flow in unit-capacity graphs (generally, graphs where the sum of capacities, $|u|_1$ is linear in the number of edges, $m$) to a $b$-matching problem in a graph with $O(m)$ nodes, vertices and sum of demands.

If you're interested in details, see section 3, up to Theorem 3.1 and section 4 (and proof of correctness in Appendix C) of the ArXiv version of Madry's paper, here. If the terminology is not self-evident, see section 2.5 for a recap concerning the $b$-matching problem, and bear in mind that $u_e$ is the capacity of edge $e$ in the original max flow instance.


Proving Turing Completeness by creating a compiler to a Turing Complete language Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the formal thinking behind the idea?

No. It's usually relatively easy to compile a language (Turing complete or otherwise). At a very simplistic level, a compiler flattens an abstract syntax tree into a list of instructions. This can usually be done by a simple structural induction over the syntax tree. Optimization passes often do data flow or control flow analyses that would be harder to represent as a simple structural induction.

You can make a practical demonstration by programming a compiler for the untyped lambda calculus into some simple Turing complete stack-based machine in Agda or some other non-Turing complete language.

However, just as an extreme example, the "compiler" could be the identity function. If you meant that you could write a compiler for any Turing complete language, then that wouldn't be possible simply because the semantics of the language may require executing arbitrary code (e.g. Common Lisp macros) to elaborate the syntax or otherwise to produce a correct compiler.


Digraph without circuits with negative cost Let $D=(V,E)$ be a digraph and let $a\colon E\to\mathbb{R}$ be a cost function on the edges.

How can I prove that $D$ has no circuits with negative costs only if there exists a function $\pi\colon V\to\mathbb{R}$ such that $a(uv) + \pi(u) − \pi(v) \ge 0$, for all $uv\in E$?

I realised that this is true by some examples, but I can't realise how can I prove that this is true in general?

Sum up the value of $a(uv)+\pi(u)-\pi(v)$ over all the edges in some circuit.  What can you say about the result?  What does this imply about whether that circuit was a negative circuit?


What is my error in reasoning about the complexity class $n^{o(1)}$ I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

Certainly the limit of $n^{1/n}$  is 1.

But it can't mean that, because the next question (and yes, this is homework) is to find a function in $n^{o(1)}$ such that its limit is infinity.

So clearly I'm making an error in my reasoning. What am I doing wrong?

$n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

You can't take the limit of one part without taking the limit of the other part, that doesn't give any useful information. If you take the limit of both parts, you get $\infty^0$, which is an indeterminate form.

It's easier to reason about exponentials with a constant base.
$$n^{o(1)} = e^{o(1) \cdot \ln(n)}$$
This way you can see that what matters is how fast the $o(1)$ function converges to $0$ relative to a logarithm.


Context free grammar for {a^mb^n | m ≠ n} I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$.

This is what I have so far, but it clearly doesn't satisfy the above condition:

$\begin{align}
   &S \rightarrow aAb &\\
   &S \rightarrow a &\\
   &S \rightarrow b &\\
   &A \rightarrow aA &\\
   &A \rightarrow bA &\\
   &A \rightarrow \lambda \\
\end{align}$

I have spent about an hour on this, and haven't found a solution. Any ideas?

Hint: Start with a CFG for the language $\{ a^{n+t} b^n : n \geq 0, t \geq 1 \}$.


Difference between "information" and "useful information" in algorithmic information theory According to Wikipedia:

  Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible self-contained representation of that string.

What is the analogous informal rigorous definition of "useful information"? Why is "useful information" not taken as the more natural or more fundamental concept; naively it seems a purely random string must by definition contain zero information, so I'm trying to get my head around the fact that it is considered to have maximal information by the standard definition.

The central concept here is Kolmogorov complexity, and more specifically compressibility. To get a intuitive feeling of compressibility, consider two strings $A \in \mathbb{B}^*$ and $B \in \mathbb{B}^*$, where $\mathbb{B} = \{ 0,1 \}$. Let

$A = 1010$ $1010$ $1010$ $1010$, and
$B = 1011$ $0110$ $0111$ $1001$.

Note that $|A| = |B| = 16$. How could we quantify how much information $A$ or $B$ has? If we think about classical information theory, in general, transmitting a string of length $n$ takes $n$ bits on average. However we cannot say how many bits we need to transmit a specific string of length $n$.
Why is the information content of a random string not zero?
On a closer look, we can see that in fact $A = 10^8$. However, it is much harder to say if $B$ has any obvious patterns in its structure, at least it seems and feels more random than $A$. Because we can find a pattern in $A$, we can easily compress $A$ and represent it with less than $16$ bits. Likewise, since it is not easy to detect any patterns in $B$, we cannot compress it as much. Therefore we can say that $B$ has more information than $A$. Moreover, a random string of length $n$ has maximal information since there is no way we can compress it, and hence represent it with less than $n$ bits.
What is useful information, then?
For useful information, yes, there is a definition using a Turing machine $T$. The useful information in $x \in \mathbb{B}^*$ is
$$\min_T \space \{\space l(T) + C(x|T) : T \in \{ T_0, T_1, ... \} \},$$
where $l(T)$ denotes the length of a self-limiting encoding for a Turing machine $T$. The notation is usually such that $C(x)$ denotes the Kolmogorov complexity of $x$ and $C(x|y)$ the conditional Kolmogorov complexity of $x$ given $y$.
Here $T$ embodies the amount of useful information contained in $x$. What we could ask is which such $T$ to select among those that satisfy the requirement. The problem is to separate a shortest program $x^*$ into parts $x^* = pq$ s.t. $p$ represents an appropriate $T$. This is actually the very idea that spawned minimum description length (MDL).


Rényi entropy at infinity or min-entropy I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. It then says that the limit as $n\to \infty $ is $-\log_2 \left( p_1 \right)$. I saw another article that uses the maximum of the ${{p}_{i}}'s$ instead of ${{p}_{1}}$. I think that this works out fairly easily if all of the ${{p}_{i}}'s$ are equal (a uniform distribution). I have no idea how to prove this for anything other than a uniform distribution. Can anyone show me how it's done?

Suppose $p_1 = \max_i p_i$. We have
$$ p_1^n \leq \sum_{i=1}^N p_i^n \leq N p_1^n. $$
Therefore
$$ \frac{n \log p_1 + \log N}{1-n} \leq H_n(X) \leq \frac{n \log p_1}{1-n}. $$
As $n \rightarrow \infty$, $\log N/(1-n) \rightarrow 0$ while $n/(1-n) \rightarrow -1$.


Undecidability of REGULAR_TM (Detail within Proof) I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.

The example shows how $REGULAR_{TM}$, defined as the problem of determining if a Turing machine recognizes a regular language, is undecidable. The way they do it is by showing a reduction from $A_{TM}$, which is the acceptance problem for Turing Machines (the acceptance problem for some computational model is the task of determining whether or not it accepts a given input string).

From what I understand, all that needs to be done is show that if $REGULAR_{TM}$ was decidable by some TM $R$, then another TM could use $R$ to decide $A_{TM}$, which would be a contradiction, since $A_{TM}$ is undecidable.

They construct a TM $S$ that can be used to decide $A_{TM}$. Where I'm lost is through their use of an intermediate TM, $M_2$. Here is the full description:

$S$ = "On input $\langle M, w\rangle$, where $M$ is a TM and $w$ is a string:

Construct the following TM $M_2$.

$M_2$ = "On input $x$:

If $x$ has the form $0^{n}1^{n}$, accept.
If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$."

Run $R$ on input $\langle M_2 \rangle$.
If $R$ accepts, accept; if $R$ rejects, reject."

My two main questions are:

Why are we allowed to do step 2 in the construction of $M_2$? If we could just say "run $M$ on $w$ and accept if $M$ accepts", then wouldn't that be a way to show that $A_{TM}$ is decidable?
What exactly is the role of step 1 in the construction of $M_2$? The book says that the purpose of this TM is not to be run, but just to feed its description into $R$. The TM recognizes $\{0^n1^n\mid n \ge 0\}$ if $M$ does not accept $w$, and $\Sigma^*$ if it does, but I don't see how it does that from the description. Also, I don't see how $A_{TM}$ can be decided by using this (I'm thinking it's that the TM $M_2$ only outputs a regular language if the TM $M$ accepts $w$, but I don't understand how it can do that).

Any help is greatly appreciated, thanks!

This proof assumes, for the purpose of contradiction, that there exists a Turing machine
$R$ deciding $R_{TM}=\left\{\langle M\rangle | \hspace{1mm} L(M) \text{ is regular}\right\}$, and uses the existence of $R$ to construct a Turing machine deciding $A_{TM}=\left\{\langle M,w\rangle | \hspace{1mm} M \text{ accepts $w$}\right\}$.

$R$ halts on every input (since it decides $R_{TM}$), so there is no problem running it (it will finally halt and either accept or reject the input). This avoids the problem of running $M$, some arbitrary Turing machine, on some input $w$, since we do not know that $M$ will finally halt.

Now, Sipser constructs a new Turing machine, $M_2$, such that:

$L(M_2) \text{ is regular} \iff M \text{ accepts $w$}$

If the above holds, then you would have $\langle M_2\rangle\in L(R) \iff M \text{ accepts $w$}$, so you could find out if $M$ accepts $w$ simply by running $R$ (which always halts) on $M_2$.

To see why this property holds, note that $M_2$ always accepts strings of the form $0^n1^n$, and it accepts any string not of this form iff $M$ accepts $w$. This means that $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, and $\Sigma^*$ (which is regular) otherwise.


Finding recursion for runtime of code This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he put up a basic example, but this one has lots of recursive calls in it.

I know that the first part len(lst)$ \leq 1$ will be linear time because of it will just return whatever in the conditional. How do I tackle the rest, and ultimately come up with the recursive $T(n)$? The question is below:

Base cases: $T(0) = T(1) = a, T(2) = b$. How did we get these base cases? Well, from the code:

if len(lst) <= 1:
    return

This tells us that for n < 2, T doesn't depend on the input list size; hence, the function takes some constant amount of time for these input sizes.

if lst[0] > lst[-1]:
    ...

if len(lst) >= 3:
    ...

This part tells us that for input sizes between 1 and 3, exclusive (i.e., for 2) we do some more work than in the n <= 1 case but not as much as in the n >= 3 case. THe amount of work done still doesn't depend on the input size, so it's constant, but it might be difference from that of the n <= 1 case.

Now we consider the n >= 3 case.

Recursive part: $T(n) = 3T(\frac{2}{3}n) + c$. Notice that the three recursive calls each use a list two thirds the size of the input list. To see this, let's consider the code:

if len(list) >= 3:
    split = len(lst) // 3
    do_something(lst[0..len(lst) - split - 1])
    do_something(lst[split..len(lst) - 1]
    do_something(lst[0..len(lst) - split - 1])

First off, we see that split will be equal to one third the length of the input list, rounded down (we assume // means integer division). We then have three recursive function invocations. To get the input size for these recursive calls, we have to see how big the lists we're passing are. All three are slices of the original input list; we can determine the size of the lists being passed to recursive calls by computing the indices used to determine slices. Observations:

The first and third slices use the same indices.
0 .. len(lst) - 1 is the entire list, size n.
split is one third the list size, equal to n/3.
The second slice uses split .. len(lst) - 1; to get the size of this slice, we can use simple subtraction of the size of the smaller interval (0..split) from the bigger interval (0..len(lst) - 1): n - n/3 = 2/3 n.
The first and third slices work similarly: if we take a slice of size n and stop it n/3 indices earlier, we get n - n/3 = 2/3 n.

Now that you have a recurrence relation, you can resolve it using any of a several of techniques.


find the actual size of an object from pixel coordinates I am quite new to vision and OpenCV, so forgive me if this is a stupid question but I have got really confused.

My aim is to detect an object in an image and estimate its actual size. Assume for now I only want length and width, not depth.
Lets say I can detect the object, find its size(length and width) in pixels and I have both the intrinsic and extrinsic parameters of the camera.

The documentation of camera calibration as I understand says that the intrinsic and extrinsic camera parameters can be used to transform from camera coordinate system to world coordinate system. So this should mean converting from pixel coordinates to real coordinates right? And so I should be able to use pixel size and these params to find the real size?

But, say the object is photographed at different depth (distance from camera), then its size would come out different using above method. So.....what does it mean transforming from camera to world coordinates?

Any kind of explaination/links/help would be highly appreciated.

Unfortunately you can't estimate the real size of an object from an image, since you do not know the distance of the object to the camera.

Geometric Camera Calibration gives you the ability to project a 3D world point onto your image but you can not project a 2D image point into the world without knowing its depth.


Table-Driven Lexer and the Classification Table I'm trying to implement a compiler for a custom language as part of an assignment.
I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 tables:

Classification Table
Transition Table
Token Type Table

My problem is mainly coming from the fact that the only example I've seen of the concept of a table-driven lexer is the "famous" (because I see it in every University's online notes) Cooper & Torczon DFA for reading digits. Page 25
From what I gather, the purpose of each of these is as follows:

1: To classify the atomic parts of the language, such as digits (0,1,2,3....) and letters (a,b,c,...)
2: To define what should happen next according to what's just been classified (If digit, go to state X, if letter, go to state Y)
3: Apparently this is used to check whether or not the string is accepted. Honestly I don't even know what the point of this is.

The grammar I'm trying to build a compiler for is much more complicated than the examples I've seen online. It contains more "atomic" symbols, such as operators (*,+,-,/,>, etc..) and reserved keywords (if, for, while, etc...)
By atomic, I mean symbols that stand on their own. (I.e. if is a symbol in its own right, not i and f)
This poses a problem for me, since I won't be able to know if I'm reading if or a string of the form aifb
Here's what I'm currently trying to do:

First, I'm building a CAT (classifier table) for all the atomic symbols of the language. I don't know if this is the right thing to do, especially when I have 52 letters (English alphabet), 10 digits and reserved words.
I will then merge all the CATs together. So I will have one big CAT that covers letters, digits, and reserved words.
Then, I will build a (big) transition table, so that when I read a character and determine its classification (problem: What about reserved words that take more than 1 character?) I will know where to transition to next.
These tables are used by a simple DFA class which, once the lexeme is read, will spit out a token.

The assignment specifies that I have to use a table-driven lexer.

A table-driven lexer is just a way of simulating a DFA. Lexer generators build DFAs from a lexical description, and then compile the DFA into the tables necessary to produce a lexical scanner.

Note that the goal is to not just identify lexemes, but to classify them by lexical type. Some lexemes have a unique spelling (like if and <=); others represent classes of symbols which have the same syntactic significance but different semantics. (That would be, for example, IDENTIFIER and NUMBER, which are two lexical types, each with a potentially unlimited number of different associated tokens.)

Lexical analysis with a state machine is slightly different from using a DFA to recognise strings, because the point of lexical analysis is to divide the input into a sequence of substrings, each of which is a token. It's important that this sequence is a partitioning of the string; every character is part of some token. That means that each successive token starts exactly where the previous token finished. In particular, that means that you don't have to worry about the if in the middle of different, but you do have to think about the for in fortunate. (All the same, it doesn't present a huge problem.)

As the Dragon book notes (and so do Cooper&Torczon IIRC), the vast majority of lexers use the "maximal munch" procedure (sometimes with a few exceptions), in which the lexeme produced at some point in the input is the longest one matchable with some lexical pattern.

In some cases, it is possible that the lexical analyser will overreach. As an example, consider lexing C, where . and ... are both possible lexemes, but .. is not. If the input contains .., the lexical analyser needs to try to match the pattern .... If that fails, if the input contains .. followed by something other than another  . (for example, ..345), the lexical analyser will have to backtrack. It will accept the first . as a token, and then restart the scan with the second . (which will turn out to lead to recognizing the number token .345 in this case).

So the precise algorithm used by the analyser when it is asked to produce the next token is:

Run the DFA until it reaches a state in which the next character has no valid transitions.
While running the DFA, always remember the last accepting state encountered.
When the DFA cannot be advanced any further, if it is not in an accepting state, back up to the last accepting state and return the corresponding token.

It's always a good idea to try to avoid this backtracking, but it is not always possible as the above C example indicates.

We said earlier that the goal of the analyser is to identify the lexical type of the token. How does it do that? Simple. The various patterns are combined into a single DFA, using the standard NFA->DFA transformation. (That's in the Dragon Book.) In the DFA which results from that transformation each state is a set of states from the original NFA, and is an accepting state if any of the associated NFA states is accepting. We map that onto a token type by noting which of the NFAs contains the associated accepting state. If there is more than one NFA which has contributed an accepting state, then we choose one of them arbitrarily. (Usually, we've arranged the patterns in priority order so that we can simply say that the first pattern wins.)

That gives us a mapping from DFA state to pattern number, and that is the role of the Token Type table.

In case that explanation was too theoretic, I've created two graphs. The first one shows DFAs for four patterns: the token <, the token <=, the token if and the token ID (any identifier). In the transitions, please interpret "letter" as meaning "any letter other than i or f", which was just too long to put on the graph. And see the paragraph below about character classification.

In the second graph, I show the DFA which results from combining these. I leave it as an exercise to construct the Token Type table.

The Transition table is simple: it just represents the DFA. It maps a pair <state, character> to a new state. Unfortunately, there are a lot of different possible characters -- 256, if we use 8-bit characters -- and usually quite a few states, and that would make for quite a large table, since it is essentially a two-dimensional array. To make the table smaller, we note that many characters have precisely the same transitions in every state. As a simple example, most of the 256 possible input characters are only valid inside character string literals or comments, and in those contexts all of them are effectively identical.

That's what the character classification table is. We gather the possible input characters into a set of equivalence classes, where each equivalence class has exactly the same transitions in every state. Any character with a specific transition -- including the i and the f in if, for example -- will be in an equivalence class by itself. But even then, we'll find that many alphabetic characters are not present in any keyword (upper-case characters, for example). And while some digits may have specific transitions -- 0 is a common case -- there are very few lexicons in which 2 and 3 have specific transitions. So we can probably reduce the number of possible transition characters from 256 to maybe 40 or 50, which is an 80% reduction in size of the transition table. In any case, if you don't want to do that, it's just an optimisation. The analyser will work fine either way.


Constructing orthogonal latin square Parker/Knuth method I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square.

The text of Knuth's explanation is available in this PDF, starting on page 16 (pp 6) and continuing to the next page: http://www.cs.utsa.edu/~wagner/knuth/fasc0a.pdf

The square he uses in his example is this one:

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

and its orthogonal mate is this one:

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

I've checked it, and it is indeed orthogonal. I just can't figure out how he produced it from the instructions he gave.

The general procedure he describes is to calculate all the transversals and then find a set of those that are disjoint, and that makes an orthogonal square. A transversal is a sequence of ten values, one from each column that are each also in a separate row, and that have no repeated values. For example, 0859734216 is one transversal of the 808 in the original square.

I've worked out how to calculate the transversals and I come up with the exact same number Knuth describes of each starting number, so I feel confident about that part.

It seems the problem I'm having is how to combine those to make the orthogonal mate. The way I interpret his instructions is that you find one of the 808 that starts with 0 and that's the first row, then find one that starts with 1 and that's the second row. If you can find such a row for each of the ten values such that each column has exactly one of each value, that's a latin square orthogonal to the original. (The transversals already only have one of each value.)

Where his description doesn't square with the example orthogonal is that one can see by inspection the first row of the orthogonal square is not a transversal of the original square. In fact, none of the first five rows are; I stopped checking after that :)

So I must be getting something wrong.

I've worked out an algorithm for finding a disjoint set of transversals and it does indeed produce only a single solution, as Knuth claims, and it is a latin square (kind of by definition) but it neither matches this solution nor is the resulting matrix orthogonal to the first.

Does someone understand the Parker method well enough to point out where I've gone wrong in the procedure?

Note: I originally submitted this question on the Mathematics site, but got no takers; I'm submitting it here thinking this might be the more appropriate site.

Find 10 transversals that don't intersect; these cover all the cells of the square.  Fill the transversal that starts with 0 will all 0's; fill the transversal that starts with 1 with all 1's, and so on.  In the example, the transversal that gives rise to the position of the 0's in the second square is 0349728615.

It seems to me that it would be clearer to use the row numbers, rather than the number stored in that row, to indicate the transversal, but of course, I've used Euler's notation above.


Why can't we detect infinite loops in the busy beaver problem? I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at each new machine state to see if it exactly matches a state we've previously seen. That ought to tell us there's an infinite loop, no? Then following this, shouldn't we be able to solve the problem for any given Turing machine, instruction set and tape?

The state of a TM includes its tape contents. Since the tape is infinite, the number of different tape contents we may encounter is infinite as well. So a TM is not required to repeat a state in order to never halt.

As a very simple example, consider the TM that will in each step write a character on the tape and move to the right. -- It will never halt but also never repeat a state.


How can I determine the start non-terminal of a CFG? Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint).

$A ::= x|y|z$
$B ::= a|b|c$
...
$N ::= l|m|k$

Further suppose that I cannot simply merge these production rules together as they are used in different parts of the grammar.
How can I hence determine or rather choose, the start non-terminal $S$, for purposes of $LL(1)$ parsing?
Thanks

By definition a grammar is a tuple $(N,T,P,S)$ where $N$ is the set of non-terminals, $T$ is the set of terminals, $P$ is the set of productions, and $S \in N$ is the start symbol.

Therefore if you have a grammar you already have $S$ (and if you don't know $S$ then you don't have a grammar).


Why should leaf nodes in a red-black tree be black? From the property of Red-Black Trees we know that:

All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms")

But what is the reason that we should enforce them as Black, even though they're NILL's?

Take a uncolored leaf node, now you can color it as either red or black. If you colored it as red then you may have chance that your immediate ancestor is also red which is contradicting(according to basic principle). If you color it as black then no problem even though the immediate ancestor is red. And also no change in the number of black nodes from root to leaf paths(i.e every path get +1). This may be the possible reason behind that.


Turing Recursive Definition vs General Perception So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input strings output of the machine should be equal to output of the function given the same input).

But in general, we say that a function is recursive if it calls itself or maybe firstly another function and then that other function calls our initial function again and again until some initial condition.

So these two definitions are seems to be different. Should I choose the meaning of recursion based on context or am I missing something ? Thanks in advance

A function is recursive if it can be defined using certain constructs, one of which is recursive calls.

A function is computable if it can be implemented by a Turing machine.

Theorem: A function is computable if, and only if, it is recursive.

Because of the above theorem people are sometimes a bit imprecise about using the correct words and definitions, and they conflate recursive and computable functions. They should not. It confuses students.


How can I find the center character of a two-tape Turing Machine in n transitions? The problem I have been given is to find a two-tape ND Turing Machine over {a,b,c} that only accepts odd length strings with a c in the middle position. The problem with this is that the question specifies that it must be done in n+2 transitions.

I can figure out how to do it in 1.5 * n transitions, by iterating over the tape and writing every other character to the second tape, then reversing at a space input and going back the same number of characters that are on the second tape. There are some other methods I thought of, but the lowest number of transitions I can get to is 1.5 * n which is not low enough.

This is homework so I am not looking for a full resolution or a walkthrough, but if anyone can point be in the right direction I would be very grateful as this has been irritating me for half a day now.

You explicitly try to find the middle position and then check whether it has a $c$ at that position. You can save some time by using the power of nondeterminism here. Choose any $c$ and check whether the number of symbols after that position matches the number before that position.

When the computation makes a wrong choice it will not accept. If there is indeed a $c$ at the middle position there is a guess that will accept.


Determinant computation is equivalent to matrix powering It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.

https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf

Does anybody why is this the case?

It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $\mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft


How does data travel in a butterfly network? I'm trying to learn how communication works in a butterfly network.

The following is a butterfly network of order 3. I'm given the following description:

  Each processor is connected to an output switch in rank 0 and to an input switch in rank k (in this case 3). In other words the switch in column j and rank 0 gets its input message from processor j and the switch in column j and rank k delivers its message to processor j. Messages only travel in one direction - towards switches of increasing rank.

I'm having trouble interpreting what it means by the input and output switches. At first I thought the messages were traveling from bottom to top, but the last statement makes it sound like it's traveling from top to bottom. Is the processor j mentioned found on top in rank 0? I'm trying to grasp how messages travel from one processor to another.

The description you were given is indeed phrased in a confusing way.  I suspect they're talking about messages travelling from top to bottom.

I suspect by "output switch" they might mean "output from the processor" (input to the butterfly network), which is pretty confusing.  That explanation could have been phrased better.

Butterfly networks are described in many places.  You might want to find another description of butterfly networks and read that.


How is Dynamic programming different from Brute force I was reading up on Dynamic Programming when I came across the following quote

  A dynamic programming algorithm will examine all possible ways to
  solve the problem and will pick the best solution. Therefore, we can
  roughly think of dynamic programming as an intelligent, brute-force
  method that enables us to go through all possible solutions to pick
  the best one. If the scope of the problem is such that going through
  all possible solutions is possible and fast enough, dynamic
  programming guarantees finding the optimal solution

The following example was given

  For example, let's say that you have to get from point A to point B as
  fast as possible, in a given city, during rush hour. A dynamic
  programming algorithm will look into the entire traffic report,
  looking into all possible combinations of roads you might take, and
  will only then tell you which way is the fastest. Of course, you might
  have to wait for a while until the algorithm finishes, and only then
  can you start driving. The path you will take will be the fastest one
  (assuming that nothing changed in the external environment)

Brute Force is trying every possible solution before deciding on the best solution .

How is Dynamic Programming different from Brute Force if it also goes through all possible solutions before picking the best one , the only difference i see is that Dynamic Programming takes into account the additional factors ( traffic conditions in this case).

Am  i correct to say that Dynamic Programming is a subset of Brute Force method ??

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.

This statement is just plain wrong.

Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all partial problems with each other and pick the best -- it combines only optimal partial solutions (and picks the best out of those).

The fact that this yield an optimal solution for the original problem is not trivial and does, in fact, only hold for some problems. Namely those that fulfill the Bellman principle of optimality (one of the most fishy, misunderstood "definitions" that are regularly quoted). See here for some more thoughts on that.

As a concrete example, consider the Bellman-Ford algorithm on a complete graph $K_n$ with unit weights: it only ever considers paths of length one and two (i.e. $\Theta(n^2)$ many) because those using one edge are all optimal. But there are infinitely many solutions if you don't bound the maximum number of edges allowed, and still $\gg (n-1)!$ many if you allow every node to be used only once. So clearly, Bellman-Ford -- a dynamic programming algorithm -- does not perform a brute-force search.


Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$? I'd like to  prove that $\sqrt n\log{\sqrt n}=\Theta(n)$ but I'm not sure how to do it.

This is my attempt:
$$
\lim_{n \to \infty}\frac{\log{\sqrt n}}{\sqrt n}=0 \Rightarrow \log{\sqrt n}=o(\sqrt n) \text{(Little o)}
$$

Therefore:
$$
\sqrt n\log{\sqrt n}=o(\sqrt n\cdot \sqrt n)=o(n)
$$
But this is too much as I need theta.

$$\lim_{n\to\infty} \frac{\sqrt n \log\sqrt n}{n} = 0$$

Since this $\Theta(\sqrt n \log \sqrt n) = o(n) < \Theta(n)$.

Two functions $f(x), g(x)$ are asymptotically equal iff

$$\lim_{x\to\infty} \frac{f(x)}{g(x)} = c,\ c \in \mathbb{R},\ c > 0$$


Relating indexes for parameters and variables I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.

I have the following binary variable

x(r,m) = 1 if referee r is assigned match m

and the following parameters:

time(m,t) = 1 if match m takes place at time t
avail(r,t) = 1 if referee cannot officiate a game at time t

I want to define my x variable to 0, when avail(r,t)=1, but is this even possible?

Yes.

This appears to be an instance of the assignment problem.  In the assignment problem, you construct a bipartite graph.  The vertices on the left represent referees.  The vertices on the right represent matches.  You draw an edge from a referee $r$ to a match $m$ if the referee $r$ is potentially available to officiate in that match.  You can use the time() and avail() parameters to work out which edges to draw.  Then, a solution to the assignment problem (a maximum matching in this bipartite graph) will represent a way to assign referees to matches.  Thus, this captures the restrictions you want to enforce in a simple and natural way.


Why do I get different results from two calculation methods? I am wondering what the reason for the following is

We know that ,

exponential has a taylor representation :
$$exp(x)=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+...$$

Using the first n  terms , in R , I compute

$\exp(-10)$ and get one answer.

However, if I compute $\frac{1}{\exp(10)}$, I  get a slightly different answer.

For example, when I use the first 30 terms of the Taylor Series,

I get

$\exp(-10)=0.0009703416$

but $\frac{1}{\exp(10)}=4.539993\times10^{-5}$

Once I get to a large enough number of iterations, both converge to the correct value.

So why do we get differing answers when I use the same method, only replacing by a division of 1 over?

Thanks!


Can one count the number of n points in m triangles in less than O(nm)? We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The triangles may overlap so each point may be counted  multiple times.

The naive way is to check each pair of a point and a triangle and count +1 if the point is inside the triangle. Is it possible to do it more efficiently than $O(nm)$?

Pragmatic solution that's easy to implement

If you care more about a pragmatic solution that will likely work well enough in practice in most cases, and is easy to code, I would suggest storing each point in a quadtree.  Then, for each triangle $T$, recursively search the quadtree to find all points within the triangle $T$.  (This recursive search is pretty easy; at a node that represents a split of the space, check whether the triangle intersects the rectangular regions corresponding to the node's two children, and recurse on whichever node(s) it intersects.)

I don't know of any reason to think that the worst-case asymptotic running time will be better $O(nm)$ (e.g., it might perform poorly if you have many long, skinny, diagonal triangles), but it might work well in practice in many cases.

Sweepline algorithm

Alternatively, you could use a sweepline algorithm, similar to the Bentley-Ottman algorithm for detecting intersections among line segments.  Unfortunately, it seems it might take quadratic time in the worst case.

Each triangle is defined by three line segments, so build the Bentley-Ottman data structures from these line segments.  Also, you'll have an interval tree; for each triangle, it stores the interval of $y$-values that are obtained by intersecting that triangle with the current sweepline.  Each point and each vertex of any triangle triggers an event when the sweepline hits that point or vertex.  When you hit a point $p$, you can quickly count the number of triangles it is contained in: check the interval tree to see how many intervals in the tree contain it.

Each operation can be done in $O(\log(n+m))$ time.  Unfortunately, there could be as many as $O(n+m^2)$ events (since there can be $O(m^2)$ intersections among the line segments), so in the worst case the total running time could be as bad as $O((n+m^2)\log(n+m))$.  If you care only about typical running time, this might often do a lot better than that, as the number of intersections among the triangles might often be as little as $O(m)$, which would lead to a $O((n+m)\log(n+m))$ running time; but that's not guaranteed, and there exist inputs where it is much slower.


Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion We know that the number of permutations possible for $n$ unique items is $n!$.
We can uniquely label each permutation with a number from $0$ to $(n!-1)$.
Suppose if $n=4$, the possible permutations with their labels are,
0:  1234
1:  1243
2:  1324
3:  1342
4:  1432
5:  1423
6:  2134
7:  2143
8:  2314
9:  2341
10: 2431
11: 2413
12: 3214
13: 3241
14: 3124
15: 3142
16: 3412
17: 3421
18: 4231
19: 4213
20: 4321
21: 4312
22: 4132
23: 4123

With any well defined labelling scheme, given a number $m, 0 \leq m < n!$, we can get back the permutation sequence. Further, these labels can be normalised to be between $0$ and $1$. The above labels can be transformed into,
0:       1234
0.0434:  1243
0.0869:  1324
0.1304:  1342
0.1739:  1432
0.2173:  1423
0.2608:  2134
0.3043:  2143
0.3478:  2314
0.3913:  2341
0.4347:  2431
0.4782:  2413
0.5217:  3214
0.5652:  3241
0.6086:  3124
0.6521:  3142
0.6956:  3412
0.7391:  3421
0.7826:  4231
0.8260:  4213
0.8695:  4321
0.9130:  4312
0.9565:  4132
1:       4123

Now, given $n$ and $m^{th}$ normalised label, can we get the $m^{th}$ permutation while avoiding the expansion of $n!$ ?
For example, in the above set of permutations, if we were given the $m^{th}$ normalised label to be $0.9$, is it possible to get the closest sequence 4312 as the answer without computing $4!$ ?
Math SE crosspost

Well, from the clarifications made in the comments, then this could be a solution.
I haven't checked for correctness. Specifically the requirement of choosing the closest label to the one input. I think I am taking the one immediately below the number input. Probably that can be fixed by using closest integer, instead of floor below.
Let $L=L_1$ be the input label, which is a real number. Maybe we can just assume that it is in $[0,1]$.
We begin with the full collection of numbers say $C_1=\{1,2,3,...,n\}$ from where one will be eliminated at each step.
In the first step we compute $a_1=\lfloor L_1\cdot n\rfloor$. We pick the $a_1$-th element $p_1$ of $C_1$ to be the first element of the permutation and remove it form $C_1$. So, define $C_2=C_1\setminus\{p_1\}$. Define $L_2=L_1\cdot n-a_1$.
Continue in this way, in the $k$-th step, for $k=2,3,...,n$, put $a_k=\lfloor L_k\cdot (n-k+1)\rfloor$, take $p_k$ to be the $a_k$-th element of $C_k$ and define $C_{k+1}=C_k\setminus\{p_k\}$ and $L_{k+1}=L_k\cdot(n-k+1)-a_k$.
Finish when there are no more elements in $C_k$, or maybe when there is just one which will be forced to be the last element in the permutation.

See also factorial number system. Since this is essentially what we are doing.


Agda: Which part does this type introduce universe inconsistency? I was trying to prove following lemma,

  my_thm : ¬ (∀ {M : Set} (P Q : M → M → Set) →
    (∀ x → ∃ M , λ y → P x y ∨ Q x y) →
    (∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x))
  my_thm = ?

while Agda gives following mistake:

Set₁ != Set
when checking that the expression
{M : Set} (P Q : M → M → Set) →
(∀ x → ∃ M , λ y → P x y ∨ Q x y) →
(∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x)
has type Set

honestly, in my untrained eyes, this type looks entirely routine to me, and it shouldn't introduce universe inconsistency.

all extra quantifier and connectivities are defined as following,

  data _∨_ : Set → Set → Set where
    inl : {A B : Set} → A → A ∨ B
    inr : {A B : Set} → B → A ∨ B
  infixl 20 _∨_

  ¬_ : Set → Set
  ¬ P = P → False
  infix 40 ¬_

  data ∃_,_ : (A : Set) → (A → Set) → Set where
    ex : {A : Set}{P : A → Set} → (x : A) → (ev : P x) → ∃ A , P
  infix 10 ∃_,_

which part introduces Set1 in this code?

ok, it turns out it's caused by negation: ¬_ : Set → Set. However, I still not understand. why this innocent looking function does not do what I want? what's the correct way of implementing it?

The term you're applying ¬_ to is large: it quantifies over all M : Set and therefore has type Set 1. So instead of ¬_ : Set -> Set you need ¬_ : Set 1 -> Set 1.

A more general solution it to make ¬_ level polymorphic as in the standard library: you will be able to use this definition of negation across the board no matter how large the thing you're negating is.


Expressing that a function converges to 1 with linear rate using Landau notation I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is approximately $1/n$.

Initially, I wrote that the algorithm achieves an approximation of:

$$\Omega(1-1/n)$$

But, now I am not sure this notation is correct: it is just like writing $\Omega(1)$ (the smaller element is swallowed in the larger element, which is 1).

Should I write:

$$1-O(1/n)$$

Or maybe:

$$1-1/\Omega(n)$$

Which of these is the correct notation?

Both of the options you listed are acceptable. They have the same meaning; $f\in O(1/n)$ if and only if $1/f \in \Omega(n)$.

Let $f\in O(1/n)$. Then there exist $n_0,M>0$ such that for all $n>n_0$, $f\leq M/n$. Then $1/f\geq n/M$ for all $n>n_0$, thus $1/f\in \Omega(n)$, since for $n>n_0$, $1/f \geq 1/M \cdot n$.

The other direction is similar.


How to find closed form solution of linear recursion using recursive tree method I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this

$$T(n)=\begin{cases}
    1         &\text{if }n=1,\\
    T(n−1)+3n &\text{if }n>1.
\end{cases}$$

However, I am confused about how to plot a tree. I know how to find runtime using tree if problem is divided into half. But here problem is just reduced by one. How does it work?


Is applying a formula a kind of reasoning? Supposed I have a set of simple rules, e.g.

if A is between 10 and 20 and B is between 3 and 5, then use 3

and this rules are used in some kind of (more or less) mathematical formula (for example, A + B = C), would you count this as a form of reasoning or inference of a knowledge based system?

You have a knowledge base (the rules) and you get a result (a decision) by applying this rules in a specific way.

I'm curious about your opinions.
Thanks!

You describe what is called expert system in AI. As such, they are artifacts of articial intelligence research.

As far as the Wikipedia definition goes,

  a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction,

which is vague enough to cover expert systems.

Is there any "intelligence" or independent reasoning in these systems? Certainly not; they are "stupid" in the sense that they just look up values in a table; no learning happens.

You will have to decide which frame of terminolgy reference you want to apply: academic AI or common sense?


As a Teacher: Choosing a suitable programming language I'm not sure if it's the right place for this question. Sorry if going a bit off-topic.

Choosing a suitable Language for the first programming course is one of the most important things that every related teacher/lecturer should bear in mind; especially if the students are young or having a limited math knowledge.

I'm currently teaching a group of highly enthusiastic young people (about 16 to 17 years old) with a medium knowledge of math. They're attending High School at 10th grade class right now. I'm going to start teaching a programming language for the upcoming semester.

They're a group of handpicked students throughout the city with a extraordinary level of creativity and diligence, so i see that working with a real programming language would not be a hard task for them. So, choosing simple graphical and drag'n'drop solutions like Turtle Art, Scratch, and Tynker are not considered as options.

There are a few factors that should be checked before making a choice:

Simplicity: Most of them probably have not experienced any kind of real coding action before.
Simplicity, Again: One of the main ideas is teaching how to think algorithmic. Having a sophisticated or hardly-syntaxed language will divert them out of the path.
Generality: It's better that the language not be designed for special development cases. Take PHP and MATLAB as examples which are respectively designed for Web Development and Calculation/Modeling.
Minimum Objective stuff: No forced OO programming (like Java). Or at least with the minimum dependency to OO concepts.
Platform: It's important to have Windows as a supported dev environment, as neary all of them are on Windows.
Easy to Set-up: It's better to have a straightforward way of setting up the dev environment.
Industry preference: Not a serious problem. But it should be at least a currently-active language allowing students to reach nearly-real dev experiences.
Hardware Portability: It's important (but not required) that the language be flexible enough to be used on Hardware programming. (I'm not speaking of Hardware Description languages like Verilog and VHDL.) The aim is programming for more simple processor-based hardware like AVR Microprocessors or Raspberry Pi GPIO interface.

I want to know that

is there any other factors that i'm missing?
And, what languages do you suggest as choices?

My answer? Python.

Let me explain by tackling all your points.

Simplicity. Python code reads like English. Seriously, how simple is
print("Hello World!")
Generality. Python can be used for web development (via. Flask/Django), data analysis (via. NumPy/Pandas/SciPy), games (via. PyGame), as well as a multitude of other tasks because of the sheer amount of libraries there are.
Minimum Objective stuff. You can do some OOP in Python but it isn't required.
Platform. Python2.7 is in pretty much on every Linux distro and there are plenty of YouTube videos on setting it up on Windows/Mac. If anything, you can use the online interpreter that Repl.It offers.
Industry Preference. Correct me if I'm wrong, but Python has consistently been ranked as one of the most popular languages.

In my experience teaching, it is extremely important to make sure that the syntax is as easy as possible to write and understand. For a new programmer, it can be pretty discouraging when he/she writes code only to see an error message (especially if he/she does not have the skill to read an error message and debug).

Side note, PythonTutor will be really helpful in explaining some major computer science/programming concepts.


How would you identify the size of a circular turing tape? Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that circular array.

The array consists only of binary digits. Lets say you are currently at one of the cells. You can read and write on the current cell you are on. You can rotate the array towards the left or right, and you have a counter with you which tells you how far away are you from the original cell that you started off with. So if you go right by x units, the counter will read x units and -x if you go x units to the left. However, you cannot store the value of previous cells you encountered. You may have at max only one unit of external memory at your disposal. For example, if you are at +x, you could compare the value at that +x with the one value you have stored in the external memory. Given that currently all the cells have been randomly assigned either a 0 or a 1.

How would you identify the size of this circular array?

This answer was inspired by YuvalFilums's comment.

I will denote values in the cells with $t$ and $f$ and locations on the tape with $0, 1, 2, \dots$ to avoid confusion.

First, check that the length $\neq 1$. To do this, set the cell under the counter to $f$. Then, move right $1$ cell and set that cell to $t$, and return to $0$, checking if that is $t$. If so you have your answer, otherwise move to $2$ and set that to $f$, and return to $0$.

Second, check that the length $\neq 2$ similarly.

Then repeat the following procedure indefinitely:

Move right until encountering an $f$. Set this to $t$.
Move right one cell and set it to $f$.
Return to $0$. If it is $t$, find the first $f$ after $1$, and move left one cell. This is your answer. Otherwise, repeat.


Can you build a solver from a verifier? Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or generate / get back the language L itself?
At a glance, the answer seems to be yes--you could just try every word, certificate pair; however, there is a part I'm not sure about with this process: sure there are only a finite number of words of each size, but there are an infinte number of words that are poly|w| for any given size |w| that are potential certificates. So, without the certificates, you could be trying different strings as the second input for the same word as first input forever to no avail.
Thanks!

Having a verifier for a language in general is known as semidecidability, which is actually weaker than decidability. So in general, the answer is no, we can't build a decider for $L$.
But if the verifier is efficient (i.e., $L \in $ NP), then indeed $L$ is decidable, and your argument is pretty close for why that is.
Let's say we have an efficient verifier $V(x,c)$.
Given an $x \in \Sigma^*$, the "certificate space" is $C=\{c \in \Sigma^* \mid |c| \leq p_L(|x|)\}$, where $p_L$ is a polynomial. That means the certificate space is actually finite. $x \in L$ if and only if there exists a $c \in C$ such that $V(x,c)$ accepts. So indeed we can just check every possible certificate for a given input $x$ to construct a decider for $L$.
In fact with a bit more work you can show that $L \in$ EXP, meaning $L$ is decidable in exponential time.


If a machine recognizes language L, can it also recognize L*? This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings in L* will be accepted as well. One problem I see with this is that a machine can only accept one language, so it might be problematic...

One problem I see with this is that a machine can only accept one language, so it might be problematic.

You are answering your own question: by definition¹, any given automaton accepts $L$ and $L^*$ if and only if $L = L^*$. This can happen -- examples include $L = \{ \varepsilon \}$ and $L = \Sigma^*$, for instance, but not as a rule.

It is not clear from your question if you understand the acceptance criterion of finite automata. The automaton has to be in a final state after reading the whole input, not in the beginning or at any time.

The language accepted by automaton $A$ is uniquely defined to be the set of words $w$ for which $A(w)$ is (an) accepting (computation).


IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory Recently it's been in the headlines that IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory. This is several thousand times smaller than one would expect the memory requirements of such a simulation to be. How were they able to do this? Did their simulation run correspondingly faster? Does the capacity to simulate quantum computers this way using conventional algorithms have any impact on our current understanding of the capabilities of quantum computers when compared to classical ones?

This blog post by Scott Aaronson gives a overview of why this simulation does not change anything about our understanding of quantum computers.

Maybe the best way to understand why is to understand what computer scientist are trying to prove at the moment: "quantum supremacy". The idea is to show that quantum computers can solve some problems much faster than classical computer (I insist on some because we know quantum computer only provide a speedup for some classes of problems but not all.) Now in theory we already have strong evidence that this the case because of Shor's algorithm:

a quantum computer can factor a $b$-bit integer in time roughly $O(b^3)$
the best known classical algorithm to factor $b$-bit integer runs in time $e^{kb}$ for some constant $k$
one can verify if a factorization is correct with a classical computer in time $O(b^3)$

From this one can derive a "practical proof" that quantum computers provide a speedup of classical computers as follows:

generate a random integer with $b=10000$ bits
run Shor's algorithm to factor it: this takes maybe a few seconds (or minutes)
verify answer with a classical computer: takes a few seconds (or minutes)
factorize the number with a classical computer: takes a millions of years or more

The important fact in this example is that the incredible difference between the quantum and classical computers: a few seconds vs a few million years.

There is one major problem though: to factor an integer that size with a quantum computer, we need to build a quantum computer with many thousands of qubits. At the moment, the largest quantum computer ever built does not even have a hundred. Thus we cannot run the above experience (yet).

This is where Scott Aaronson and the IBM experiment enters the picture. Instead of trying to factor numbers, we want to find another problem as above but where the quantum computer is much smaller so that we can actually build it. One such problem is quantum simulations:

simulating a quantum system with a quantum computer is very easy (polynomial time)
simulating a quantum system with a classical computer is very hard (exponential)

So we go ahead and redo our experiment:

pick a quantum system at random of size $b=100$ qubits
simulate it with a quantum computer: takes a few seconds/minutes
simulate it with a classical computer: takes a few million year

Since we can build a quantum computer of that size (~100 qubits), we are done right? Well no because how do we know the simulation with the quantum computer was correct? Sure it's fast, but maybe it's wrong! In this case we have not proven anything. You see with factorization, verifying the result is easy, but for simulation it is as hard as the simulation itself... This is the crucial issue.

In order to fix this, we want to find a value of $b$ such that the classical computer can still find the answer so that we can verify it but it has to be long enough to demonstrate that the gap between quantum and classical is huge. Researcher are trying to find this sweet spot, and think it is around $b=50$ where a supercomputer will take may a few months or year. The IBM paper shows that $50$ is too small. But remember that the simulation for $b=100$ is trillions of times harder than for $b=50$ (exponential), thus may the sweet spot is at $b=60$, but it is unlikely that we can ever reach $b=100$.

NOTES: I simplified most of the actual complexity bounds. I ignored the fact that quantum computations only give the correct answer with high probability, one may have to re-run the algorithm several times.


How to prove that this language is not recursive enumerable? I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable:
$L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle $ M $\rangle$ does not receive any input $\}$.
Should I use reduction from the halting problem in this case?

You can directly use the extension of Rice's theorem to prove that $L\notin RE$


Show that regular languages are closed under Mix operations Let $L_1, L_2$, two regular languages and the operations:

$$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in L_1 , b_1b_2\ldots b_n\in L_2\}$$

$$Mix_2(L_1, L_2) = \{ x_1y_1x_2y_2\ldots x_ny_n | n\ge 0 \land x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n\in\Sigma^* , x_1x_2\ldots x_n\in L_1 \land y_1y_2\ldots y_n\in L_2\}$$

  Prove that regular languages are closed under $Mix_1$ and $Mix_2$ operations.

So for the first operation:
Let $D_1, D_2$, two DFA's accepting $L_1, L_2$, respectively. We define $D = (Q,\Sigma, \delta, q_0, F)$.

Where $Q = Q_1 \cup Q_2$. The transition function, $\delta$ will behave as $\delta_1$ and $\delta_2$. But in addition, Let's define $n = \left|\Sigma\right|$, then we make $n$ transitions from every $q_i\in Q_1$ to $q_j\in Q_2$ (and vice versa) for every $\sigma \in \Sigma$.

So it's pretty easy to see that $D$ accepts $Mix_1(L_1, L_2)$.

Question:
How can I show that regular languages are closed under $Mix_2$?

Take any string over the alphabet $\Sigma$. Colour some of the letters red and the remaining letters green. Accept the original string if the red letters form a string in $L_1$ and the green ones are in $L_2$.

More technically, regular languages are closed onder intersection and under (inverse) homomorpisms.

Let $\Gamma = \Sigma \times \{1,2\}$ be an alphabet with colours.

Define the homomorphisms $h_i:\Gamma^* \to\Sigma^*$, $i=1,2$ by $h_i(a,i) = a$ and $h_i(a,j) = \varepsilon$ for $i\neq j$. These keep only letters of their assigned colour, whereas their inverses colour the letters into that asigned colour while inserting arbitrary letters of the other colour.

Finally let $g:\Gamma^* \to\Sigma^*$ be the morphism $g(a,i) = a$ (which removes the colour).

Then $Mix_2(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \;)$.

PS. Let $R_{12}$ be the regular language $[(\Sigma\times \{1\})(\Sigma\times \{2\})]^*$.
Then $Mix_1(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap R_{12} \;)$.

Just for fun,  $L_1 \cdot L_2 = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap (\Sigma\times \{1\})^*(\Sigma\times \{2\})^* \;)$. Regular languages are closed under concatenation :)


Can expected "depth" of an element and expected "height" differ significantly? When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that

$\qquad\displaystyle \mathbb{E}[d(k)] \in O(\log n)$

where $d(k)$ is the depth of the element with rank $k$ in the set of $n$ keys.
Intuitively, this seems to imply that also

$\qquad\displaystyle \mathbb{E}[h(T)] \in O(\log n)$

where $h(T)$ is the height of treap $T$, since

$\qquad\displaystyle h(T) = \max_{k \in [1..n]} d(k)$.

Formally, however, there does not seem to be an (immediate) relationship. We even have

$\qquad\displaystyle \mathbb{E}[h(T)] \geq \max_{k \in [1..n]} \mathbb{E}[d(k)]$

by Jensen's inequality. Now, one can show expected logarithmic height via tail bounds, using more insight into the distribution of $d(k)$.

It is easy to construct examples of distributions that skrew with above intuition, namely extremely asymmetric, heavy-tailed distributions. The question is, can/do such occur in the analysis of algorithms and data structures?

Are there example for data structures $D$ (or algorithms) for which

$\qquad\displaystyle \mathbb{E}[h(D)] \in \omega(\max_{e \in D} \mathbb{E}[d(e)])$?

Nota bene:

Of course, we have to interpret "depth" and "height" liberally if we consider structures that are not trees. Based on the posts Wandering Logic links to, "Expected average search time" (for $1/n \cdot \sum_{e \in D} \mathbb{E}[d(e)]$) and "expected maximum search time" (for $\mathbb{E}[h(D)]$) seem to be used.
A related question on math.SE has yielded an interesting answer that may allow deriving useful bounds on $\mathbb{E}[h(D)]$ given suitable bounds on $\mathbb{E}[d(e)]$ and $\mathbb{V}[d(e)]$.

In chained hash tables with uniform hashing a similar question arises. Given a table with $n$ elements hashed into $m$ buckets, the expected number of elements per bucket is $n/m$, but what is the expected length of the longest chain?

I found a Stackoverflow question about chained hash tables. The answer by btilly argues that for fixed ratio $n/m$ the expected worst case longest chain is $\Theta(\log n/ \log\log n)$.  (Since $n/m$ is fixed, $m$ doesn't need to come into the answer.)

And the answer by templatetypedef references the following paper for a more detailed analysis:
Gaston H. Gonnet: Expected Length of the Longest Probe Sequence in Hash Code Searching.
J. ACM_ 28(2):289-304, 1981.
[Free techreport version at University of Waterloo]

Slightly more generally I found a math.stackexchange question about the balls and bins problem.  The answer by Yuval Filmus cites the following paper, which gives even tighter bounds:
Martin Raab; Angelika Steger: Balls into Bins - A Simple and Tight Analysis. 2nd Intl Wkshp on Randomization and Approximation Techniques in Computer Science, pp. 159-170, 1998.

Finally, there is apparently a branch of statistics called extreme value theory culminating in the Fisher-Tippett-Gnedenko theorem, which, I think, gives expected maxima for a huge variety of distributions.


Is there a meaningful difference between O(1) and O(log n)? A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ elements to process, even an $O(1)$ operation such as an index lookup will start to take longer as the index has to be calculated in multiple operations. I think it will take at least $O(\log n)$.

Similarly even if an algorithm has $O(\log n)$ complexity, $\log n$ cannot possibly grow larger than about a hundred, so could be ignored as no larger than a small constant.

So, is it really meaningful to treat $O(1)$ and $O(\log n)$ as different?

The same applies of any difference of $\log n$, like between $O(n)$, $O(n\log n)$ and $O(n/\log n)$.

There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of bits in the integer, which can get up to 4096 or higher in practice. Those bits will be spread out over many machine words, so the $\log n$ term refers to how many machine words the number occupies and therefore definitely has an impact on the runtime.

Similarly, $O(1)$ does not mean "constant time only if $n < 2^{64}$." Yes, the computer has a fixed word size, but that doesn't mean that an $O(1)$-time algorithm given a gigantic input can't run in a fixed amount of time. Taking large integers as an example, consider the problem of checking whether an integer is even or odd. That just requires you to look at the last digit, which takes time $O(1)$ even if the number is spread out over thousands of machine words.

The last detail is that typically, we assume that we work with a machine model where the word size scales with the log of the size of the input. This allowance a to safely assume that you can do array accesses in time $O(1)$ because array indices are assumed to fit into a constant number of machine words.


Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits? I'm working on exercise 4.29 of Nielsen and Chuang:

  Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits.

As part of solving this exercise, I'm trying to figure out if the task of making a NOT-controlled-by-N-bits is possible classically (i.e. without using single qubit gates, except the NOT gate).

This is trivial to do if you have work bits initialized to 0 available, but I haven't been able to figure out how to do it without work bits. I'm also not sure how to approach an impossibility proof.

The main thing I've figured out is that, if I could make $Increment$ and $Decrement$ gates, then I could do it like this:

   ____    ____
--|    |--|    |---    --•--
--|    |--|    |---    --•--
--| +1 |--| -1 |--- == --•--
--|    |--|    |---    --•--
--|    |--|____|---    --•--
--|____|-----------    --X--

But I also can't figure out how to make those gates, at least not without the many-controlled-not gate I'm trying to make.

Is this even possible (the limited-to-classical case, not the exercise)?

It's not possible.

A reversible computation always corresponds to a permutation of the state space. When working on three bits, a Toffoli corresponds to a single swap in the state space (it swaps 111 for 110). When working on four or more bits, a Toffoli gate always corresponds to an even number of swaps in the state space. This is because it performs a swap for each possible state of the uninvolved bits, and there are an even number of such states. For example, a Toffoli applied to the first three bits of a four bit system swaps 111_0 for 110_0 and swaps 111_1 for 110_1. Even number of swaps.

Permutations have a parity. A permutation that can be implemented with an even number of swaps has even parity. Permutations that can be implemented with an odd number of swaps have odd parity. The composition of two even parity permutations will also be an even parity permutation. Odd parity permutations can't be reached by composing even parity permutations.

This means the Toffoli gate can't perform a CCCNOT without workspace, because the action of the CCCNOT on the state space is an odd parity permutation but the action of the Toffoli is an even parity permutation. The single CNOT and NOT gates have the same problem. You need an extra work bit (or quantum gates like $X^{1/8}$) to break the parity barrier.


Examples of non-sparse languages All I could find is an example of sparse language.

I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the languages string generation is bound to at least one polynomial, so I am unable to design a language L whose strings are not bounded to a polynomial function.

For a language $L$, let's write $\|L\|_n$ for the number of length-$n$ strings it contains.  So $L$ is sparse if there is a polynomial $p$ such that $\|L\|_n\leq p(n)$ for all $n$. The key point is that, for a language to be sparse, we must be able to pick just one polynomial that works for all $n$: you're not allowed to use a different polynomial for each $n$.

For example, suppose that you wanted to prove that the language of strings over $\{0,1\}$ with at most two $1$s is sparse.  You can't say "Well, for $n=3$, there are seven valid strings, and $7 < n+5$ for $n=3$. And for $n=4$, there are eleven valid strings, and $11 < n^2-4$ for $n=4$, and..." You have to pick just one polynomial that works for all values of $n$: in this case, $n^2$ works, so the language is sparse.

So, for a non-sparse language, $\|L\|_n$, when considered as a function of $n$, must grow faster than any possible polynomial. The simplest examples of functions that grow faster than polynomials are exponentials. Conveniently, $\{0,1\}^*$ has $\|\{0,1\}^*\|_n=2^n$ for all $n$. So, whatever polynomial $p$ you pick, $\|\{0,1\}^*\|_n>p(n)$ for all large enough $n$. Therefore, $\{0,1\}^*$ is not sparse.

Another example of a non-sparse language is the complement of a sparse language. If $\|L\|_n\leq p(n)$ for all $n$, then $\|\overline{L}\|_n\geq 2^n-p(n)$ and this grows faster than any polynomial if $p$ is a polynomial.