What determines the number of inputs and outputs when initialising weights in a convolutional neural network? Following Deep MNIST for Experts tutorial on Tensorflow, I realize I don't understand where the choice of numbers comes from when initializing weights.

In the tutorial, they first show the below function for creating random weights.

def weight_variable(shape):
  initial = tf.truncated_normal(shape, stddev=0.1)
  return tf.Variable(initial)

However, the shape parameter has me confused when the tutorial shows the next line of code:

W_conv1 = weight_variable([5, 5, 1, 32])

The tutorial says the following:

  The first two dimensions are the patch size, the next is the number of input channels, and the last is the number of output channels.

I don't understand the significance of the last two values, 1 and 32.

What decides what values you input there? And what do they affect?

When I'm designing my own neural network, could I put any value I like for the last two, or if I were to change them in a neural network would it 'break' the entire network?

The question is about basic principles of Convolutional Neural Networks, specifically how the layers are organized (it's best explained here, in fact I highly recommend to complete the whole CS231n course, it's amazing!).

  What decides what values you input there? and what do they affect?

W_conv1 = weight_variable([5, 5, 1, 32])

The input channel of the first convolutional layer is the depth of MNIST images. Since they are grayscale, there's only one channel. If you had colorful CIFAR-10 images, you'd use 3 channels (R, G, B).

The 5x5 filters in this layer (32) would be the the output of this layer and input to the next layer. Indeed, as you can see the next layer defines

W_conv2 = weight_variable([5, 5, 32, 64])

  When I'm designing my own neural network, could I put any value I like
  for the last two, or if I were to change them in a neural network
  would it 'break' the entire network?

Yes, you have freedom here, you only need to make input-output channels consistent. If you decide to use 48 filters instead 32, you would write:

W_conv1 = weight_variable([5, 5, 1, 48])
b_conv1 = bias_variable([48])
...
W_conv2 = weight_variable([5, 5, 48, 64])
b_conv2 = bias_variable([64])

Like I said before, the first 1 is determined by your data. But you can change the filter size as well, from 5x5 to 3x3.

Note that if the number of channels doesn't match, the graph won't simply compile. You'll see an error even before the training starts, so don't be afraid to experiment.


Lexicographical position of a string in its type class I have the following problem:

Given a string $x\in\{1,...,M\}^+$ of length $n$.
Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists of all permutations of $x$. We call this set the type class of $x$.

My question:

  How to compute the position of $x$ in the lexicographical ordering of $S$?

I found the paper "Enumerative source coding" written by Thomas M. Cover, where this position function $i_{S}$ is shown for binary alphabets (in the following the alphabet is  $\{0,1\}$):

$i_S(x_1x_2\cdots x_n)=\sum\limits_{k=1}^{n}x_k\cdot$ $n-k\choose n(w,k)$

with $\;\;n(w,k)=w-\sum\limits_{j=1}^{k-1}x_j\;\;\;$

and $\;\;w$ is the number of occurrences of $1$ in $x\;\;$ ($w=\sum\limits_{k=1}^{n}x_k$).

Unfortunately, i do not know how to extend this formula to alphabets of size $M$. Any help?

This is yet another example of enumerative encoding. Suppose that $x$ has $\alpha_i$ symbols of type $i$. The size of $S$ is then the multinomial coefficient $\binom{n}{\alpha_1,\ldots,\alpha_M}$. Pascal's identity reads
$$ \binom{n}{\alpha_1,\ldots,\alpha_M} = \sum_{i\colon \alpha_i \neq 0} \binom{n-1}{\alpha_1,\ldots,\alpha_i-1,\ldots,\alpha_M}. $$
In the lexicographic ordering of $S$, the strings starting with $1$ (if any) constitute the first $\binom{n-1}{\alpha_1-1,\ldots,\alpha_M}$ positions, the strings starting with $2$ (if any) constitute the following $\binom{n-1}{\alpha_1,\alpha_2-1,\ldots,\alpha_M}$ positions, and so on. So $x_1$ already gives you an interval of length $\binom{n-1}{\alpha_1,\ldots,\alpha_{x_1}-1,\ldots,\alpha_m}$ to which $x$ belongs in the lexicographical ordering of $S$. To find its location within the interval, recurse: examine $x_2$, then $x_3$, and so on.

Here is the resulting algorithm, returning a $0$-based position:

Set $P \gets 0$.
For $i=1,\ldots,n$:

Set $P \gets P + \sum_{j < x_i, \alpha_j \neq 0} \binom{n-i}{\alpha_1,\ldots,\alpha_j-1,\ldots,\alpha_M}$.
Set $\alpha_{x_i} \gets \alpha_{x_i} - 1$.

Return $P$.


Which complexity class $3^{n/3}$ Assuming a problem has complexity $O(3^{n/3})$,

Which is its class of complexity ?

Despite that it is not as $2^{n}$ ,we can say  is an exponential ?

Yes, that is exponential. Something is exponential if it is $2^{O(n^k)}$ for some $k$. You can write $3^{n/3}$ as $2^{n\frac{\log 3}{3 \log 2}}$, so it fits.

It would be more common to write $(3^{1/3})^n \approx 1.44^n$.


A voting scheme where votes are scriptable I am looking for literature on mathematical models of (political) voting schemes. Concretely, I am interested in models that allow votes of the following form:

"I am voting for $X$, but only if $>40\%$ of my peers vote for them, too. Otherwise, I'd like to vote for $Y$ instead."

In that sense, I'd like to consider votes to be scripts over some language. I got this idea from Bitcoin where money isn't actually sent to specific accounts, but rather scripts are given that determine who may redeem that money.

A naive model
To give you a more precise idea, I have come up with the following (naive) model of scriptable votes:
Let $C$ be a set of candidates, e.g. $C = \{\text{rep},\text{dem}\}$ for republicans and democrates. An election outcome $O \in \mathrm{ProbDists}(C)$ is a probability distribution on $C$. For finite $C$, this is known as a normalized histogram.
A vote $v$ is a mathematical function $v\colon \mathrm{ProbDists}(C) \to C$, which – given a putative outcome – decides which candidate to vote for.
In most elections around the world, all votes are constant functions: e.g. if you mark your cross for republicans, in the above model you would cast the constant function $v \equiv \mathrm{rep}$. And if you marked democrates, you would cast $v' \equiv \mathrm{dem}$ instead.
Importantly, our model also supports votes as in the quote above: $$v^\text{example}(O = \{p_\mathrm{rep}, p_\mathrm{dem}\})=\begin{cases}
  \mathrm{rep} & \text{if } p_\mathrm{rep} > 0.4\\
  \mathrm{dem} & \text{else}
\end{cases}$$
where the notation $O = \{p_\mathrm{rep}, p_\mathrm{dem}\}$ is syntactic sugar for extracting the probabilities assigned to $\mathrm{rep}$ and $\mathrm{dem}$, respectively. Here, you see that $v^\text{example}$ is a script over the usual mathematical language. But given some votes how do we determine the (final) outcome?
Let $V = v_1,\ldots,v_N$ be the multiset of cast votes. An admissible outcome of an election $(C, V)$ is an election outcome $O \in \mathrm{ProbDists}(C)$ such that the multiset $\{v_1(O),\ldots,v_N(O)\}$, interpreted as a normalized histogram on $C$, equals $O$. We can see this as some kind of fixpoint.
Examples. Let $C$ and $v := v^\text{example}$ as above.

For the election $(C, \{v\})$, i.e. with $v$ being the only vote, we have two admissible outcomes: $O_1 = \{p_\mathrm{rep} \mapsto 1, p_\mathrm{dem} \mapsto 0\}$ and $O_2 = \{p_\mathrm{rep} \mapsto 0, p_\mathrm{dem} \mapsto 1\}$. For $(C, \{v, v\})$, we have the same two outcomes. The same holds true for three, four, and arbitrarily many copies of $v$.

Consider a new kind of vote $w(O) \equiv \mathrm{dem}$ that always votes for democrates. The election $(C, \{v,w\})$ has two admissable outcomes: $O_1 = \{p_\mathrm{rep} \mapsto 0.5, p_\mathrm{dem} \mapsto 0.5\}$ and $O_2 = \{p_\mathrm{rep} \mapsto 0, p_\mathrm{dem} \mapsto 1\}$. In the latter case, the vote $v$ "noticed" that they will never be surrounded by a like-minded peer group of size $> 40\%$ and hence switched its candidate it voted for.

Research Questions
Concerning scriptable votes, some broad questions I'd be interested in are:

Does every election have at least one admissible outcome? If not, can we relax the conditions on admissible outcomes to just choose the best ones?

How much influence do individual votes have? Is the function that maps $(C, V)$ to a set of admissible outcomes continuous in some sense?

Are mathematical functions for votes really the best model? While if conditions like $p_\mathrm{rep} > 0.4$ sound reasonable (and interesting), should we perhaps disallow conditioning on equalities such as $p_\mathrm{rep} = 0.4578$? Perhaps votes should be scripts over a tailored domain-specific language. How do their properties such as being total (exceptions?) or deterministic (probabilistic?) affect the questions above?

Broad context
First off, the field in which this sort of research would be carried out is called computational social choice (theory). Searching for papers or books in that field will give you exactly what you ask for: literature on mathematical models of (political) voting schemes, and related topics like resource allocation and judgement aggregation. As for a reference, I'd recommend the Handbook of Computational Social Choice. As a sidenote, if you want to ask questions about these things, the tag social-choice-theory on math.stackexchange.com might be a good idea.
Your voting rule
Now, as for your specific idea, there are some unclear parts. You consider probabilities, but are unclear on what exactly those probabilities mean. You imply that they're based on the proportion of votes any candidate gets, but the voters don't simply vote for a candidate. I'd recommend trying to really formalize your idea and see if it has some interesting properties. I'm not aware of any serious research effort in this sort of direction.
One thing to consider is the reason for such a system. That is, why would a voter want to vote for X only with a certain level of support, and Y otherwise? Is it 1.) because they prefer X but are scared that a vote for a minor candidate might be a waste, or is it 2.) because the level of support somehow changes the desirability of the candidate? In the case of 1.), the voter really just supports X, and has Y as their second favorite candidate. A solution might not involve a complicated ballot, as you propose, but perhaps just a good voting rule that fits in the existing mathematical frameworks. In the case of 2.), where a voter's true preferences might rely on other's preferences, making such a complicated ballot might indeed be a good idea.
Importantly, you must consider that every voter can submit such a ballot, and therefore changes in outcome might beget changes in preference which beget changes in outcome and so on and so forth. It might not be possible to make any decent voting rule within this system that is guaranteed to converge to some outcome. You'll even have to be careful that the outcome is not just well-defined, but computable.
Regardless of all this, we might already be able to answer one of your research questions. Unless I misunderstand things, there is not always an admissable outcome. Consider a single voter who votes X only if X has less than half of the votes, and Y otherwise. Now, if X would win, they would prefer Y, and vice versa. I don't have any direct ideas on how to relax admissibility to guarantee one exists.


Calculating probability of reaching state in DTMC Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov Chain (DTMC) property: for each state the outflow transition weights are reals (or just rationals, if that makes a difference) in [0,1] which sum to 1, and the transition weights stay constant in time. So a finite state machine where the system moves through the states probabilistically, basically. For example:

Where $a_{0,1} + a_{0,2} = 1$, $a_{1,0} + a_{1,3} = 1$ etc.

Assume we start the system in the state where $x = 0$; what is the probability that the system reaches the state where $x = 3$, and what is the algorithm for determining that probability? From my small knowledge of probability, the algorithm requires summing of the probabilities of all finite paths that eventually reach $x = 3$; for example:

$P[F (x = 3)] = a_{0,1}\cdot a_{1,3} + a_{0,2}\cdot a_{2,3} + a_{0,1}\cdot a_{1,0} \cdot a_{0,1} \cdot a_{1,3} + \ldots$

Since it's possible for the system to loop indefinitely before reaching $x = 3$, this equation includes an infinite sum of infinite products and is beyond my ability to solve. How is something like this calculated?

The answer to your question very much depends on the values of the probabilities $a_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of reaching $x=3$ is therefore $1$ (it is $1$ for any state in such a case in fact). This result comes from the Long-run theorem, which says that any finite DTMC eventually reaches a bottom SCC and visits all its states infinitely often.

Have a look at the lecture slides and notes of a course on probabilistic systems. Especially the third and fourth lecture.

In a general case, you would find with a graph analysis states that reach $x=3$ with probability $1$ denoted $S_1$ and those with probability $0$ denoted $S_0$. Then you have a set of states $S_?$ for which you don't yet know the probability. For them you construct a matrix $\mathbf{A}$ of transition probabilities (it will be a square matrix of size $|S_?|\times |S_?|$). Then you construct a vector $\mathbf{b}$ with one-step probability to reach $x=3$. A solution to $\mathbf{A}\cdot \mathbf{x} = \mathbf{b}$ gives you the probabilities for states in $S_?$.


Information capacity of Ternary-based system over Binary-based Some researchers are trying to get a memory cell capable of having 3 states instead of 2.

1) How many memory cells, in principle and as a rough estimate, does a typical 1 megabyte memory chip has? is it 8*1024 cells?

2) If you have N memory cells, each has x logical levels, what is the number of possible representations that we can get out of it? is it x^N representations?

Let's take Binary system as an example. Say we have 8*1024 memory cells. We can store
only one of the possible 2^N representations in each cell, so at the end the number of stored bits is just N=8*1024.
Now, for Ternary system, the gain is log2(3) ~ 1.58 times so we can store ~ 1.58 * 8 * 1024 "bits" or 8*1024 "trits".

Correct?
EDIT: sorry I meant 8*1024*1024.

Binary (two states)

1 Megabyte = 1,048,576 bytes = 8,388,608 bits = 8,388,608 cells.  See https://en.wikipedia.org/wiki/Megabyte and https://en.wikipedia.org/wiki/Byte.  1 byte = 8 bits.

There are $2^{8,388,608}$ different possible values that can be stored in this much memory.

Ternary (three states)

Now a cell can have 3 possible values.  If we have 8,388,608 cells, each of which can have 3 possible values, then the entire memory can hold $3^{8,388,608}$ possible values.  This is the equivalent of $\lg 3^{8,388,608} = 8,388,608 \times \lg 3 \approx 8,388,608 \times 1.58 \approx 13,295,629$ bits.  This corresponds to $13,295,629/8 = 1,661,953$ bytes.

Therefore, this many ternary cells can store the same  amount of data as 1,661,953 of ordinary binary cells (as 1,661,953 MB of memory).


Dynamic Programming, Counting Independent Sets My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But
my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to approach this. Any ideas would be great.

Let $OPT_N[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that neither of the leftmost two vertices can be selected into an independent set.

Let $OPT_T[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the top of the leftmost two vertices must be selected in the independent set.

Let $OPT_B[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the bottom-most of the leftmost two vertices must be selected in the independent set.

According to the above definitions $OPT_N[1] = OPT_T[1] = OPT_B[1] = 1$ while, for $i>1$:
$$
\begin{align*}
OPT_N[i] &= OPT_N[i-1] + OPT_T[i-1] + OPT_B[i-1]\\
OPT_T[i] &= OPT_N[i-1] + OPT_B[i-1]\\
OPT_B[i] &= OPT_N[i-1] + OPT_T[i-1]
\end{align*}
$$

The number of independent sets on a graph with $2i$ vertices is then $OPT_N[n] + OPT_T[n] + OPT_B[n] = OPT_N[n+1]$.

You can simplify the above formulas by noticing that you must have $ OPT_T[i] = OPT_B[i]$.


Circle Intersection with Sweep Line Algorithm Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it clearer I try to solve as many exercises as I can. But, really interesting and important tasks are still a challenge for me.

The following exercise I found in lecture notes of Line Segment Intersection by omnipotent Jeff Erickson.

  Exercise 2. Describe and analyze a sweepline algorithm to determine, given $n$ circles in the plane, whether any two intersect, in $O(n \log n)$ time. Each circle is speciﬁed by its center and its radius, so the input consists of three arrays $X[1.. n], Y [1.. n]$, and $R[1.. n]$. Be careful to correctly implement the low-level primitives.

Let's try to make a complex thing easier. What do we know about intersection of circles? What analogue can be found with intersection of lines. Two lines might intersect if they adjacent, which property two circle should have in order to intersect? Let $d$ be the distance between the center of the circles, $r_{0}$ and $r_{1}$ centers of the circles. Consider few cases:

Case 1: If $d > r_{0} + r_{1}$ then there are no solutions, the circles are separate.
Case 2: If $d < |r_{0} - r_{1}|$ then there are no solutions because one circle is contained within the other.
Case 3: If $d = 0$ and $r_{0} = r_{1}$ then the circles are coincident and there are an infinite number of solutions.

So, it looks like conditions of intersection are ready, of course it may be wrong conditions. Please correct if it's so.

Algorithm. Now we need to find something in common between two intersecting circles. With analogue to line intersection, we need to have insert condition and delete condition to event queue. Let's say event point are x coordinate of the first and the last points which vertical sweep line touches. On the first point we insert circle to status
 and check for intersection (3 cases for checking are mentioned above) with nearest circles, on the last point we delete circle from status.

It looks like is enough for sweep line algorithm. If there is something wrong, or may be there is something what should be done different, feel free to share your thoughts with us.

Addendum:

I insert a circle when vertical sweep line touches the circle for the first time, and remove a circle from the status when sweep line touches it for the last time. The check for intersection should be done for the nearest previous circle. If we added a circle to status and there was already  another circle which we added before and it was still there, therefore the pervious circle was not "closed", so there might be an intersection.

You're definitely on the right track. The big question is: when you insert a circle, which other circles do you check for intersection? How do you perform this check?

In the line segment intersection case, the line segments at any given x coordinate are totally ordered. (You can list them from lowest to highest Y coordinate). Thus, you can maintain the line segments in a binary search tree, and when you add a new segment, you only need to find out where it belongs in the binary search tree, and check its neighbors for intersection events.

In the circles case, its not immediately clear which circles to check. If your answer is "all of them" then your algorithm needs some work.

Can you figure out a way to represent the circles so that they are totally ordered, like the line segments are?

   Try representing the circles as two half-circles. Each insert event is actually two events: insert top half, and insert bottom half.


Solving T(n) = T(n-1)*T(n-2) So, this is how I solved

$\displaystyle
        T(n-1) \approx{}  T(n-2)
    $

$\displaystyle
        T(n) = T(n-1)^2
    $

Add log in both sides

$\displaystyle
        log(T(n)) = 2log(T(n-1))
    $

$\displaystyle
       Let\:\: log(T(n)) = S(n)
    $

$\displaystyle
S(n) = 2(S(n-1))
    $

We know that from Fibonacci series

$\displaystyle
S(n) = O(2^n)
    $

$\displaystyle
log(T(n)) = O(2^n)
    $

$\displaystyle
(T(n)) = O(2^{2^n})
    $

Ok, so where did I go wrong here??

What is wrong?

So, this is how I solved
$T(n-1) \approx{}  T(n-2)$
$T(n) = T(n-1)^2$

An equality is the most precise and most powerful entity in the world. Please treat it with due respect.
Let me show how wrong it is if you use approximation liberally with equalities. If your argument above is sound, we can also do the following.
$\quad T(n) \approx{}  T(n-1)$
$\quad T(n-1) = T(n-1)*T(n-2)$
$\quad T(n-2) = 1$  if $T(n-1)$ is not 0.
So $T(n)$ must be 0 or 1 from time to time . That is obviously false, however.  For example, we can let $T(1)=T(2)=2$.

What to do?
What you can do is, as gnasher729 suggested, "taking logarithm on both sides immediately", assuming $T(1)>0$ and $T(2)>0$, which can be assume generally when we are analyzing recurrence relations in computer science.
You can also, of course, dive into analysis by cases when $T(1)$ and $T(2)$ might be 0 or even negative.


Inverting an image, as a matrix I am curious about something pretty simple, though I have never heard, read and more sadly seen any example of it.
Take any image, represent it as a matrix, invert the matrix (assuming the inverse exists) and represent it as an image again.
This in some sense visualizes the process of inverting a matrix. It would be pretty easy to code this, but before doing that I just wanted to ask if anybody has examples at hand or can say anything about this. Thanks!

I tried it on square grayscale images myself (just hoping they would be invertible, which was always the case (not much luck involved here, since invertible matrices lie dense)). I added a few examples so you can judge the inverses yourself. Their precise look of course depends on the particular normalization (I used cv2.normalize and also normalized manually by

as done here (I used this to create the LaTeX expression)).

Moreover, I ran this procedure on all test/cat images from CIFAR-10. You can find the results here. Notice that actually a lot of these 32x32 images were (as a matrix) not invertible.
As was asked for by user fiveclubs, here are the normalized inverses of the normalized inverses. They are nowhere near their originals.
Dolphin inverse of inverse:

Painting inverse of inverse:

Tower inverse of inverse:


Floating point normalised numbers in binary Many text books state that for a binary floating point representation in a computer byte, that if the mantissa is normalised,  then a positive number must start with 01 from the left or a negative number with 10 from the left.This is nothing to do with IEEE standard but a common statement in English A level computing books. (A levels are the school leaving exams in most of the UK, and some other countries.)

They then ask you to spot normalised representations:

1) 100000000

2) 011111111

3) 110000000

In the rule above 1 and  2 would be normalised but not 3.

Why does it have to be 10 and 01? How is this rule derived?

I'm assuming you're talking about IEEE754. Unless I'm missing something, your book is wrong.

Every number in IEEE754 is represented as normalized (starting with a 1), unless your number is subnormal. A number is only subnormal if the mantissa is minimal (all zeroes). Since the first bit is the sign bit, $10$ could be the start of a subnormal number.

For example $10000000000000000000000000000001$ is the subnormal number $-2^{-149}$.


Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to enumerate assignments one-by-one in increasing order of their weights using methods like Murty's algorithm, where each new enumeration takes polynomial time.

We can assume that there are 2n vertices in the bipartite graph and that the weights on all present edges are non negative integers less than some value k. Missing edges will need a higher weight or infinity.

My questions is, is it possible to find an assignment of a particular weight (that is not minimal), say W, in polynomial time? Naively, if one tries to enumerate assignments, it may take exponential time to find an assignment of weight W since there may be exponentially many assignments of weight less than W.

Further, if it is possible to find an assignment of weight W in polytime, is it possible to enumerate all assignments of weight W, similar to Murty's algorithm?

I know that we can formulate the assignment problem as a linear program

$\min \sum_{i,j} w_{i,j}x_{i,j} $

such that

$\sum_i x_{i,j} =1$
$\sum_j x_{i,j} =1$
$x_{ij} \ge 0$

I am not sure whether we can directly add the constraint
$\sum_{i,j} w_{i,j}x_{i,j} \ge W$
and still obtain integral solutions for $x_{i,j}$s. Thoughts?

The problem becomes NP - Complete when the weights are exponential in the number of variables. This can be shown by a reduction from the subset sum problem described in the paper "Planarizing gadgets for perfect matching do not exist" by Gurjar et al. (link)


Is there any efficient way of calculating the n-th fibonacci number modulo another number? With efficient I mean of a big O of polynomial time in the number of digits each number has.

Here are two suggestions:

The linear algebra approach. It is known that
$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n &F_{n-1} \end{bmatrix}. $$
You can compute the matrix power using repeated squaring, doing all the calculations modulo your modulus.

Closed form. If your modulus is odd and 5 is a quadratic residue (i.e., 5 has a modular square root) then you can use the explicit formula
$$
F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}.
$$
You can then use Carmichael's function to reduce $n$, and then repeated squaring. Care must be taken when the modulus isn't a prime power.

It is possible that a similar approach works more generally.


Do there exist "O(1)-complete" problems? Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time?

A complication is that this class depends on the model of computation; a problem can be solvable in $O(1)$ time in one reasonable model of computation but not another, given that "reasonable" typically means polynomial-time equivalence with a Turing machine. However, it could still be worked out for specific reasonable models.

I think it makes the most sense to look at constant-time many-one reductions. However, I'm also open to looking at other sensible reductions if there is literature on them.

Does anything like this exist, or has it been studied, for any model of computation?

Since reading the input is necessary for almost all problems, we need at least $\Omega(n)$ time for nearly all problems, where $n$ is the size of the input.
Therefore, you may think of the class of linear time problems, which is already defined.

However, we still do not know any $O(n)$-complete or $O(n^2)$-complete problem. The field of fine-grained complexity has some new results in this area, but the classes are problem-based (for example, APSP is equivalent to Radius, Negative Triangle, ...).


CFG of all regular expressions over a binary alphabet I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), *, +, e} (e for epsilon).
Some examples I know that should be accepted are things like:

e
0
01
1010
0*1*0*1*
0*11+(10)*+(e+1*0*)
((100*)*(10*)*)*

While things such as these would be rejected:

ee
)(e+1*)*
(10)*++(

et cetera
I've been building up case by case and I have this rather ugly looking CFG that prevents most incorrect cases, but it does not come close to getting all the correct ones
S → (N) | M+M | N | (N)*
M → 0N | 1N | 0N | 1N | (N) | (N)* | M+M | e
N → 0N | 1N | 0N | 1N | ɛ
Apologies if this has been asked before, I tried searching everywhere here and on Google and I was not able to find someone else trying to create the same or similar CFG, but if this is a repeat I'd appreciate being pointed to the original!!
If helpful, I've been using this tool to test my CFG: https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

You are quite close to the solution. We will use a few variables, each corresponding (intuitively) to some other "thing". Specifically, we will use the variables $S,E,A,B$.
$S$ is the starting variable. $E$ is a variable that will produce a valid regular expression (its called $E$ as short for "expression"). $A$ will be some valid string over the alphabet $\{0, 1\}$, and $B$ will be a non-empty string over that same alphabet.
The CFG will now be:
$S\rightarrow E$
$E \rightarrow (E)(E) \space | \space E+E \space|\space E^* \space | \space (E) \space|\space A$
$A\rightarrow B\space |\space e$
$B \rightarrow 0B \space | \space 1B \space | \space 0 \space | \space 1$
I hope this CFG is what you are looking for! (I don't know if it is, since you didn't state the definition of the syntax of a regular expression using this alphabet, so I have only tried to go by the examples)


Is it possible to have a zero knowledge proof with a P Prover? In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.
Is it necessary for the prover to have higher computational power than the verifier?
If it is, is there any variant that does not need this property?
If any of the answers is yes can you give me references?

If the prover has the same power as the verifier, then the verifier can simulate the entire interaction himself, which makes the interactive proof unnecessary. For example, if we have an interactive proof with a probabilistic polynomial verifier and a polynomial prover for some language $L$, then $L\in BPP$. When dealing with interactive proof systems with a polynomial verifier it suffices to consider PSPACE provers, since a PSPACE prover can find and send the messages that maximize the verifier's acceptance probability.
Note that the above refers to interactive proof systems in general, there's nothing specific to zero knowledge (zero knowledge simply adds the condition that for yes instances, the entire communication of the protocol can be generated by a simulator who only has access to the input).


CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$ How do I construct a context-free grammar for the following language?

$$L = \{w\#x \mid w, x \in \{0, 1\}^*, |w| = |x|, w \neq x^R \} $$

A word belongs to your language if it has one of the following forms:
$$
\Sigma^i 0 \Sigma^j \# \Sigma^j 1 \Sigma^i \\
\Sigma^i 1 \Sigma^j \# \Sigma^j 0 \Sigma^i
$$
Given this, you should be able to construct a context-free grammar for $L$.


Maximum entropy probability distribution among Solomonoff priors If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words.
But, the pmf isn't completely determined until we fix a universal Turing machine (UTM) $U$.
Say $m_U$ is the normalized prior with respect to a UTM $U$.
Is there a $U$ such that $m_U$ has maximum entropy?

All versions of Solomonoff's prior have infinite entropy.
We supply a proof.
Let $m: \mathbb{Z}_+ \to [0,1]$ be Solomonoff's prior, where inputs are
encoded as integers.
Then there is $c>0$ such that
$$m(n) \geq c\frac{1}{n (\log n)^2},$$
Let $S$ be the set of all $n$ such that
$$m(n) \geq \frac{1}{n}.$$
Since $\sum m(n)$ is convergent,
$$\sum_{s \in S} \frac{1}{s} \leq \sum_n m(n) < \infty.$$

The entropy of $m$ is
$$
\begin{align*}
\sum_n m(n) \log(1/m(n)) &\geq \sum_n c\frac{1}{n (\log n)^2} \log(1/m(n)) \\
&\geq \sum_{n \not\in S} c\frac{1}{n (\log n)^2} \log(1/m(n)) \\
&\geq \sum_{n \not\in S} c\frac{1}{n \log n}.
\end{align*}
$$

Now
$$
\infty = \sum_{n} c\frac{1}{n \log n} =
\sum_{n \in S} c\frac{1}{n \log n} +
\sum_{n \not\in S} c\frac{1}{n \log n},
$$
and
$$\sum_{s \in S} \frac{1}{s \log s} \leq \sum_{s \in S} \frac{1}{s} < \infty,$$
so
$$
\sum_{n \not\in S} c\frac{1}{n (\log n)} = \infty.
$$


How does the NFA decide in a state where there are multiple equally valid "next states"? How does the NFA decide in a state where there are multiple equally valid "next states"?

Such as here:

How does it decide on which state it takes to with 1?

It doesn't decide. Nondeterminism isn't intended to be a realistic model of computation. Check the definition: a nondeterministic automaton accepts if there's any valid sequence of transitions that reach an accepting state.


Is two arrows on each state necessary in DFA? In DFA, is two arrows on each state necessary?

Or it depend on language alphabets? I mean if there is $\Sigma = \{a\}$ then there should be one arrows on each state.

OR if there are $\Sigma = \{a , b\}$ then there should be two arrows on each state.

OR if there are $\Sigma = \{a , b , c\}$ then there should be three arrows on each state.

and so on...

You are correct.

In an NFA, there might be more arrows (for epsilon transitions, or multiple transitions on the same symbol) or fewer arrows (for undefined transitions) than there are symbols in the alphabet. In a DFA, neither of these is allowed: in fact, a DFA is specifically defined as an NFA where neither of these things happens.

Therefore a DFA will always have exactly as many arrows from each state as there are symbols in the alphabet.


Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient? Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching.

In short, the regular expression a+b, when running on the string aaaaaaaaaaaaaac, runs in $O(n^2)$ time where $n$ is the number of a characters, because it uses backtracking.

You can reproduce the issue with the following Python code, which on my computer, takes over 4 seconds to run:

import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x')
print(time.time() - start)

This was very surprising to me; I'd have thought that a regex matcher works more efficiently, e.g. by constructing a DFA from the regex and then running the wanted string through it, which I'd have thought would be $O(n)$ (not including the DFA construction).

(For instance, the book Introduction to Algorithms by Cormen, Leiserson, Rivest goes through a similar algorithm on the way to introducing the Knuth-Morris-Pratt algorithm).

My question: Is there something inherently difficult in regular expression matching that does not allow an $O(n)$ algorithm, or are we simply talking about an inefficient implementation (in Python, in whatever StackOverflow uses, etc.)?

If you only wanted to parse regular expressions then you wouldn't have such problems (unless you were a really incompetent programmer, I guess). Caveats include the time needed to build an automaton; an asymptotically worse algorithm may outperform the automaton approach in many cases in practice.

The real issue is probably that they use library functions that deal with regexps which are way more powerful than plain regular expressions. Also, features like matching groups introduce further complexity.

In this case, trouble arose because these engines match substrings (with plain regular expressions, we typically only match whole inputs) and use backtracking; long partial matches that eventually mismatch cause long backtracks. In essence, this is the worst-case for naive, quadratic-time string matching.

Can this be improved? Maybe. Using the ideas from string matching automata we would backtrack not to the second symbol, but to the start of the longest suffix that matches a prefix of the pattern. But since the pattern is not fixed anymore, it's certainly not trivial to extend the ideas.


Is a KNN-Classifier memory intensive? In my opinion it seems fairly obvious that a $k$ nearest neighbours (KNN) Classifier would be fairly expensive in terms of memory, as the model is the training set itself. However, any notes I've read have only mentioned that the KNN-Classifier is computationally expensive, and have not mentioned any memory requirements as a disadvantage. I assume this to be true, but I wouldn't want to mention it in any exams or anything without proper confirmation. Are the memory requirements implicit and not worth mentioning, or am I overlooking something?

KNN is a memory intensive algorithm and it is already classified as instance-based or memory-based algorithm. The reason behind this is KNN is a lazy classifier which memorizes all the training set O(n) without learning time (running time is constant O(1)).

Inversely, When it comes to querying new points to find the nearest K, the query time will be  expensive O(n) in terms of the running time.


What is the knowledge required to understand the formal definition of a Turing Machine? As a computer science student I consider is essential to completely understand how a Turing machine is defined.

What mathematical knowledge is required in order to understand the formal definition of a Turing Machine, as explained in this Wikipedia link.

All you need is some basic discrete mathematics.

The states, tape alphabet and states are finite sets; the blank symbol, starting state, accepting state and rejecting state are elements of one of those sets.

The transition function is a function on finite sets, defined using a Cartesian product of finite sets.

The tape is a sequence of elements of one of the sets.


Searching for an item over a non-uniform query distribution If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, $O(\ln n)$.

What happens now, if the items are not queried uniformly? As a silly example, say that one item is queried 1000 more frequently than any other item. Would it make sense check for that item first and independently, before looking in a search tree of the other items (the so-called LenPEG method)?

For concreteness, let's say the items are queried with a likelyhood that is static, and drawn from a Poisson distribution. What would be the optimal way to structure the data so that the average search time is minimized?

The Optimal Binary Search Tree is exactly what you need.

Welcome to the site!


Proof that quicksort's running time is ∼1.39 n log n In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this.

All I know is that the total running time obeys $$C_n = C_{\mathrm{partitioning}} + C_{\mathrm{leftArray}} + C_{\mathrm{rightarray}}$$

and that quicksort's average case is about $2n\log_\mathrm{e}n$.

it's claimed that the running time of QuickSort is $∼1.39\,n\log_2n$

I don't have the book handy, but it it most certainly does not claim this. That figure is the result of a close analysis of a very specific cost measure (which "time" is not); expected number of comparisons, if I remember correctly.

The proof is given in the book, if I recall correctly.

  quicksort's average case is about $2n\log_e n$.

This is basically the same figure since $1.39 \approx \frac{2}{\log_2 e}$, the difference probably being a rounding artifact.

From your comment, quoting Sedgewick/Wayne:

  In summary, you can be sure that the running time of algorithm 2.5 (quicksort) will be within a constant factor of $1.39n \lg n$ whenever it it used to sort n items.

This only states that the (expected) running time is in $\Theta(n \lg n)$; this follows from the (expected) number of comparisons being what it is, plus that comparison is a dominant operation in Quicksort.

For what it's worth, the formulation "you can be sure" without context is misleading since it seems to ignore the worst-case, and the asymptotic nature of the result.


Regular expression of 011=110 in string What is the regular expression for language containg no.  of 011 equal to 110 in string ?

Usually, languages of the form "The number of $x$s is equal to the number of $y$s" aren't regular because you could have an arbitrarily long sequence of $x$s with no $y$s but a finite state automaton can't remember how long that sequence was.

However, in this case, any time you see $011$, either the rest of the string contains only $1$s or the string looks like $0111^k0\ldots$ for some $k\geq 0$ and you've found the matching $110$.  If you think about this for a bit, and try some examples, you should be able to figure out some simple rules that determine whether a string is in the language, and then implement that as a regular expression.


Graph add at most 2 edges to make all graph nodes degree even Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all the degrees of nodes even. Keep in mind that in the resulting graph there should be at most one edge between any pair of nodes.
For
graph = [[false, true, false, false],
         [true, false, true, false],
         [false, true, false, true],
         [false, false, true, false]]

the output should be true.
This is my proposed broken solution:
boolean addEven(boolean[][] graph) {
    int odd = 0;
    int even = 0;
    for (int i = 0; i<graph.length; i++) {
        int k = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                k++;
            }
        }
        if (k%2==1) {
            if (k == graph[0].length-1) {
                return false;
            }
            odd++;
        } else {
            even++;
        }
    }
    if (odd == 2 && even == 3) {
        return false;
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd <=4) {
        return true;
    } else {
        return false;
    }
}

Your proposed "broken" solution is actually quite close to the actual solution. You don't need any well known algorithm to do it, but instead you have to notice the following things:

Given that odd == 2, and the two odd vertices are $v,u$ - then we can "fix" them by either connecting them if they are not connected, or by finding another vertex $w$ such that $(v,w),(w,u)\notin G$ and then add the two edges.
Given that odd == 4, the only way to "fix" them is by connecting them to each other, in 2 groups of 2: each edge on two different vertices.

Then, the actual code would look like this:
boolean addEven(boolean[][] graph) {
    int odd = 0;
    List<Integer> odd_vertices = new ArrayList<Integer>();

    for (int i = 0; i < graph.length; i++) {
        int deg = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                deg++;
            }
        }
        if (deg % 2 == 1) {
            odd++;
            odd_vertices.add(i);
        }
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd == 0) {
        return true;
    } else if (odd == 2) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        for (int k = 0; k < graph.length; k++) {
            if (!graph[a][k] && !graph[b][k]){
                return true;
            }
        }
        return false;
    } else if (odd == 4) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        int c = odd_vertices.get(2);
        int d = odd_vertices.get(3);
        if ((!graph[a][b] && !graph[c][d]) ||
            (!graph[a][c] && !graph[b][d]) ||
            (!graph[a][d] && !graph[b][c])) {

           return true;
        }
        return false;
    } else {
        return false;
}

Of course, this code is just to illustrate how the changes are reflected in the code. You can change it to be more general or optimize it, but I will keep it as is (especially because its hard to write code without a proper editor)


Why decision tree method for lower bound on finding a minimum doesn't work (Motivated by this question. Also I suspect that my question is a bit too broad)
We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison and each leaf is a permutation. Since there are $n!$ leaves, the minimum tree height is $\Omega(\log (n!)) = \Omega (n \log n)$.
However, it doesn't work for the following problem: find a minimum in the array. For this problem, the results (the leaves) are just indices of the minimum element. There are $n$ of them, and therefore the reasoning above gives $\Omega(\log n)$ lower bound, which is obviously an understatement.
My question: why does this method works for sorting and doesn't work for minimum? Is there some greater intuition or simply "it just happens" and we were "lucky" that sorting has so many possible answers?
I guess the lower bound from decision tree makes perfect sense: we do can ask yes/no questions so that we need $O(\log n)$ answers: namely, we can use binary search for the desired index. My question still remains.

In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which then implies the bound that you got on the height of the tree. This is Lemma 2 in the linked document. They call this an information theoretic argument.
The reason why it gives such a conservative lower bound for the height of the trees, is that the bound on the number of leaves is too conservative. So, Lemma 1's fault of not being strong enough.

I was curious to see if this method could give a better lower bound if one manages to bound better the number of leaves. For this what we need to do is to have some control on the number of times an outcome of the algorithm is repeated across the leaves.
Suppose a comparison-based algorithm for minimum has decision tree with a maximum of $K$ leaves corresponding to the same outcome.
Then the tree has at most $Kn$ leaves and at most height $\log(n)+\log(K)$. If $n>2(\log(n)+\log(K))$, then none of the paths from root to leaf compares all elements of the array. Since the height of the path is bounded by $\log(n)+\log(K)$, then there are at most that many comparisons in the path. Each comparison looks at $2$ elements, so at most $2(\log(n)+\log(K))$ are inspected. Then we can keep the elements compared in one of the paths fixed and make the other elements smaller than the element that that path chooses as minimum. This input would result on the same output from the algorithm but have a different minimum. So, the algorithm must be incorrect. So, the inequality above must be false. This argument has the flavor of the adversary argument, which applied directly gives the best lower bound for this problem.
Hence $n\leq 2(\log(n)+\log(K))$. From this we get that $\log(K)\geq n/2-\log(n)$, or in other words
$$K\geq 2^{n/2-\log(n)}$$
Now, this tells us that the decision trees for these algorithms will always have at least $K+(n-1)\geq 2^{n/2-\log(n)}+(n-1)$ leaves. So, their height is at least
$$\log\left(2^{n/2-\log(n)}+(n-1)\right)\geq n/2-\log(n)$$


Algorithm for executing a command against a million hosts Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the moment, let us suppose you want to run one command at a time. How to do that efficiently?

Is also desirable to have the ability to query at any moment the progress (status of execution on each host), as well as to consult afterwards the outcome of each individual execution (both exit code and stdout/stderr); hence, the outcome must be persisted somewhere.

Ideally, if you could deliver instantaneously the command at all the hosts, and coordinate them to start at the same time, you would have an ideal time of the command duration (assuming command takes same time on every host). Thus, I presume that a big part of the problem is how to deliver as fast as possible the command to all the hosts; the problem may get more elaborated if we add the quality of being fault-tolerant (that is, to ensure that the execution does take place on all available hosts even if some of the auxiliary machines used for the delivery fail or have issues).

If I execute a dummy echo command using ssh on an intranet I have access to (after having automated the authentication with keys); the time for getting back a response is at best 0.25 secs. Thus, running one million times ssh against each one of the hosts does not sound promising if done serially (it would take almost 3 days to finish the execution serially on this environment).

Even if we could deliver the command within a few milli-seconds to each machine using a custom protocol other than ssh, doing the delivery from a single source may not be the best approach. I suppose that the problem may benefit from some parallel/distributed algorithms, as well as network/graph theory. It would also be nice to avoid using a centralized approach too, if one does not want to rely on the availability of a fixed set of machines for doing the delivery (which ideally should be a subset of the one million hosts, so we do not need additional infrastructure machines).

Is there an standard name for this kind of problem? Any known algorithms or approaches?

Assuming the hosts and network are reliable, and that the cost of sending a message from any machine to any other machine is the same, then you would use some sort of broadcast tree.  For example, if the machines are all numbered 0, ..., 7, then node 0 would send to node 4, 2, and 1, node 4 would send to nodes 6, and 5.  Node 2 would send to node 3. Node 6 would send to node 7.

Generalize that to $2^n$ nodes, and the total time is $O(n)$.  So with 220 nodes, node 0 would send about 20 messages, rather than 1 million.

As you make the assumptions weaker, the problem gets increasingly more difficult.

If the cost of sending messages is different for different pairs of machines, then you would want to do some kind of minimum spanning tree based algorithm, maybe.

If you don't know anything about the network as a whole, but each node knows something about its neighbors then you might use some kind of flooding algorithm.

If the network is not reliable (links can appear and disappear) then the problem gets quite difficult.  I think there are various ways of posing the problem as a Steiner tree problem, but now you are way outside my area of expertise.


Can parameters other than $n$ be always ignored in big $O$ notation? The Bentley–Ottmann algorithm, for example, has time complexity of $O((n + k) \log n)$. Is the statement $O((n + k) \log n) = O(n \log n)$ true? I know that $k$ is there because it has big enough of an impact on the overall time complexity that it's relevant to include it. But can it be ignored, so that the previously stated equivalence holds, and hence we can without any reservations say that the algorithm has time complexity of $O(n \log n)$?

In general you cannot erase things. A bivariate function $f$ is $O((n+k)\log n)$ if there exists a constant $C>0$ such that for all legal settings of the parameters $n,k$, we have $f(n,k) \leq C(n+k)\log n$. Here a setting of parameters is legal if it can actually happen – for example, if $V,E$ are the number of vertices and edges in a simple graph, then we always have $E \leq V(V-1)/2$, any other setting being illegal. If in some context you know that $k \leq Bn$, then in that context (which restricts the set of legal settings of parameters) $f = O(n\log n)$. In any other context, you cannot drop the $k$.

In your particular case, the Bentley–Ottmann algorithm, it is generally not the case that $k = O(n)$, and so $k$ cannot be dropped.


Summation of a Random Variable I'm having trouble grokking Cormen's Algorithms book on pg. 120.  The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up:

  "Let X be the random variable whose value equals the number of times we hire a new office assistant."

and later on:

  "...we let $X_i$ be the indicator random variable associated with the event in which the $i$th candidate is hired ... [so that] $X = X_1 + X_2 + \ldots + X_n$"

In particular, Cormen defines $X_i$ as follows:

$$
  X_i =
  \begin{cases}
    1 & \text{if candidate $i$ is hired} \\
    0 & \text{otherwise}
  \end{cases}
$$

Question: Why does $X = X_1 + X_2 + \ldots + X_n$?

First, this equation only makes sense if $X$ and each of the $X_i$ have the same domain. Here I'm assuming the domain of $X$ is $\{1,2, \ldots , n\}$ (i.e., each number representing the number of assistants hired).

That implies that the domain of each $X_i$ must be $\{1,2, \ldots , n\}$. Then it seems that, i.e., $X_2$ will satisfy $X_2(2) = 1$ and be $0$ everywhere else.

But if that's the case, then $X_1 + \ldots + X_n$ will satisfy $X(i) = 1$ for all $i \in \{1, \ldots , 6\}$, which means that $X \ne X_1 + \ldots + X_n$ (since, for example, $X(2) = 2$). What am I missing?

EDIT: The more I think about it, the more I'm convinced that my misunderstanding lies with the way $X$ itself is defined. Is it true that i.e. $X(2) = 2$?

Your outcomes are not the number of candidates but rather which candidates were hired: $\Omega = \{0,1\}^n$. Then you have $X_i(a_1, \dots, a_n) = a_i$ and $X(a_1, \dots, a_n) = \sum\limits_{i=1}^n X_i(a_1, \dots, a_n) = \sum\limits_{i=1}^n a_i$.


Worst-case complexity in terms of n? I have this algorithm taken out from the Manual of Algorithms Analysis:

function pesky (n)
r:=0
for i:=1 to n do
  for j:=1 to i do
    for k:= j to i + j do
      r := r + 1
return (r)

I understand the time complexity of this algorithm for any given input size n > 0 will be O(n^3) since the 3 for loops will always be executed and the inner loop carries out the sum operation n x n x n times (this is of course not exact, but I say it in asymptotic terms taking out constants and lower degree terms of n); however, during a lecture we were asked to express the complexity of the worst-case in terms of n instead of in big oh notation (they left this exercise for next session).

The worst case I can think about for this algorithm would a really large integer as input n which in fact could be so large that it approaches infinity (since no restrictions for the input were stated). Even in this worst case we know time complexity would behave in O(n^3), but how would I express this "in terms of n", the best thing I could come up with is this:

But I feel like I'm just making that up and that there might be another more correct way to express it. Does anyone know the correct way to express worst-case complexity in terms of n?

EDIT: I must make it clear that I found the equation that puts n in function to the r output by means of summation resolving, however I did not consider that function as the time complexity function (and hence not the answer for "worst-case in terms of n") since that function describes output on a given input and not the time it takes to run the algorithm itself.

Moreover I had the idea to try to calculate the complexity counting each operation and I got something like this.

I am not sure if thats correct, if it is I could use that expression to state the worst-case complexity in terms of n, and also I could make my initial statement about big oh notation for the worst case more precise since this would be O(n).

Let us interpret for i:=1 to n inclusively. That is, i will take values $1, 2, \cdots, n$.

Let us check how many operations are done in pesky(n).

r:=0: 1 assignment.

for i:=1 to n do:
$n$ assignments of i.

for j:=1 to i do:
$\sum_{i=1}^ni=\dfrac{n(n+1)}2$ assignments of j.

for k:= j to i + j do: $\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ assignments of k.

r := r + 1:
$\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ additions by 1.  $\dfrac{n(n+1)(n+2)}3$ assignments of $r$.

There are $1+n+\dfrac{n(n+1)}2+\dfrac{n(n+1)(n+2)}3\cdot2=\dfrac{(n+1)(n+2)(4n+3)}6$ assignments in total.

There are $\dfrac{n(n+1)(n+2)}3$ additions in total.

If we treat the computation cost of one assignment as that of one addition, we have $\dfrac{(n+1)(n+2)(4n+3)}6+\dfrac{n(n+1)(n+2)}3=\dfrac{n(n+1)(2n+1)}2$ operations.

That is answer. Note that it is a fixed number given $n$. That is, there is no distinction of best-case, worse-case or average-case.

Or is it? If we ignore over many important details, yes. However, let us take a close look. Does for i:=1 to n do involve assignment only? Mostly like not. We have to produce 1, 2, 3, $\cdots$, n in the first place. If we produce them by addition by 1, we have $n-1$ more additions. How do we make sure we will stop when $i$ reach $n$? Probably we have to compare i with n for about $n$ times. Comparison takes time of course. We should include that cost. Wait, there is more. It is unreasonable to expect that $n$ is in the right position to be compared with $i$; We have to fetch $n$ from somewhere so that we can compare it with $i$. Now, we are not even sure how to describe that fetching and its computational cost. There are, in fact, many more important details that could be taken into consideration.

You might be wondering now. Do we have an answer or not? Yes and no.

Yes, we have an answer, assuming some assumptions. I will not be surprised that your instructor might come up with a different number of operations under a different set of assumptions, though.
No, the answer cannot stand up to scrutiny in many situations. That is one of the reasons why we use the big $O$-notations. We can say the computation cost is $\Theta(n^3)$ under a set of very general assumptions (a.k.a. model of computation).

By the way, if you check what I had written before, you will notice and understand that I have been rather careful, saying that I am only computing how many times the innermost iteration are executed. In general, the asymptotic time complexity of a nested loop is determined by the product of that number with the average cost of one innermost iteration.

Here is a similar exercise for you to practice.

Exercise. Express the best-time complexity of the following function in terms of $n$ instead of in big $O$-notation. Only the operation r := r + 1 is counted.

function pesky2(n)
  r := 0
  for i := 1 to n do
    for j := 1 to i do
      for k := 1 to j do
        r := r + 1

  return r


Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language? I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an inherently ambiguous language?

1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: n\geq 0\}$

2) $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$

3) $L = \{a^n b a^{2n}: n \geq 0\} \cup \{a^{2n} b a^n: n\geq 0\}$

4) $L = \{\omega: \omega \in \{a,b\}^*: \omega \text{ does not have substring $baba$}\} \cup \{\omega : \omega \in \{a,b\}^*: \omega \text{ does not have substring $abab$} \}$

If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for $L_1,L_2$ with start symbols $S_1,S_2$ (respectively) and otherwise disjoint non-terminals, you can construct an unambiguous grammar for $L_1 \cup L_2$ by adding a new start symbol $S$ and the productions $S\to S_1|S_2$. This takes care of 1) and 3), once you construct unambiguous grammars for the constituent languages.
As Palec mentions, 4) is regular, and so admits a regular grammar which corresponds to a DFA accepting it. This grammar has as non-terminals the states of the DFA, and productions $A \to aB$ if the DFA moves from $A$ to $B$ upon reading $a$. For each final state $F$ we add a production $F\to\epsilon$, and the start symbol is the start state. This description should make it clear that the grammar is unambiguous.
Intuitively, 2) could be inherently ambiguous since words of the form $a^n b^m c^p$ with $n \neq m \neq p$ could have two different parse trees, corresponding to the two constituent languages. Proving this formally could be tedious. The only method I know consists of coming up with two words $x,y$ that can be pumped to the same word $w$ in such a way that makes it clear that the corresponding parse trees are different. If you want to pursue this further, a good first step will be to read some examples of this method.


How to prove equivalence relation in this case? I am working on $\lambda$-terms and trying to prove the $=$ is an equivalence relation on $\lambda$-terms. My problem is proving reflexive relation.

$\frac{}{\theta \vdash x = x}$

$\frac{ \theta,x \# N, y \# M \vdash  M  = [y := x]N }
          { \theta \vdash  \texttt{$\lambda x.M$ $=$ $\lambda y.N$}   } $

$\frac{\theta \vdash  M_1 = M_2 \quad N_1 = N_2  }
          { \theta \vdash  \texttt{$M_1 \, N_1$ $=$ $M_2 \,N_2$} }$

I put two restrictions on such $\lambda$-terms.First, bound variables are distinct.
For example, there are no two terms such as $\lambda x.M$ and $\lambda x.N$.
Second, multiple bindings of a variable is not allowed.
For example, $\lambda x. \lambda x.M$ should be written as $\lambda y. \lambda x.M$.
To sum up, every bound variable should be distinct.
$[y := x]N$ means variable $x$ replaces variable $y$ in term $N$.
$x \# N$ means $x$ does not occur in $N$.
$\theta$ is a set of $\#$.
Also, $\alpha$-equivalence is assumed for the terms.
For example, $\lambda x.x = \lambda y.y$

I tried to prove that the $=$ shown in above rules is an equivalence relation on such terms.

For equivalence relation, I have to prove the following three relations.

reflexive: $\theta \vdash M=M$.

symmetric : $\theta \vdash M=N$ implies $\theta \vdash N=M$.

transitive: $\theta \vdash M=N$ and $\theta \vdash N=P$ implies $\theta \vdash M=P$.

The proof of reflexive relation is the following.

when $M$ is a variable such as $x$, then $x = x$.

when $M$ is an application such as $M_1 \,N_1$), then I have
$M_1 \,N_1$ = $M_1 \,N_1$, so it is true.

when $M$ is an abstraction such as $\lambda x.M$, from $\lambda x.M = \lambda x.M$, I have $ x \# M \vdash | M=[x:=x]M $, which is not true becuase $x \in M$.
Also, as I said, there are no two terms such as $\lambda x.M$ and $\lambda x.M$, so I cannot show $M=M$ for an abstraction.

Since $\alpha$-equivalence is assumed for terms. I assume that $M=\lambda x.M_1 =\lambda y.M_2$. Therefore, I will have $x \# M_2, y \# M_2 \vdash  M_1=[y:=x]M_2$? is this the right way to prove  reflexivity?

I would appreciate your kind help.

I will only prove reflexivity $A=A$. We proceed by induction on the structure of $A$.

If $A\equiv x$, then $x=x$ follows from rule 1.

If $A\equiv \lambda x. M$, then by induction hypothesis we can assume $M=M$ is provable. Now, take any $y$ not free in $M$. We have $M \equiv [y:=x][x:=y]M$ by construction. Let $N \equiv [x:=y]M$. Rule two states

$$
\dfrac{
  x\# N, y\# M \vdash M=[y:=x]N
}{
\vdash \lambda x.M = \lambda y.N
}
$$

We indeed have $x\# N$, since the $x$ variable was renamed as $y$ in $N \equiv [x:=y]N$. We also have $y\# M$ by our choice of $y$. Induction hypothesis states $M=M$, which is $M=[y:=x]N$. Hence, the conclusion of the rule holds, which is $\lambda x. M = \lambda y. [x:=y]M$. If terms are identified up-to $\alpha$, then this equality is the same as $\lambda x.M = \lambda x.M$.

If $A=MN$, the induction hypotheses and rule 3 suffice.


Solving the Path Explosion Problem in Symbolic Execution Looking at the Symbolic Execution limitations, there are some good solutions to the "Environment interactions" problems. However, the solutions to the path explosion problem are less than ideal.

  Solutions to the path explosion problem generally use either heuristics for path-finding to increase code coverage,[2] reduce execution time by parallelizing independent paths,[3] or by merging similar paths.[4]

The parallelizing is just adding more power to the situation which doesn't really solve it. The first and third suggestions I am not to familiar with. The first sounds like it has similar problems to testing, in that they are just opting into certain paths based on heuristics, which also doesn't seem to solve it. I am wondering if the solutions to the path explosion problem could be explained here a little bit, either the solutions listed above or anything else. Specifically I am interested in the heuristics one, and what kind of things can be done here.

The heuristic approach to solving the path explosion problem picks the next branch to explore based on some function. A simple heuristic function, yet pretty effective, would be to assign the score of a branch based on how many times it has been seen before, and then pick the one with the lowest score. This ensures that branches which haven't been seen yet are explored first instead of getting stuck in a path explosion, whose branches would have been seen many times.


Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$? If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq coRP}$ and hence $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq ZPP}$?

If you could prove that implication, then lower bounds such as $NEXP \neq BPP$ would hold unconditionally. (proof: $NEXP = BPP$ implies $NEXP = \Sigma_2 P$ and $NP \subset BPP$, and if the latter also implies $NP$ is in $coRP$ then UNSAT is in $NP$. So $NEXP = \Sigma_2 P = NP$ which is false by the nondeterministic time hierarchy). Good luck!


Explaining why a grammar is not LL(1) I need some help with explaining why a grammar is not LL(1).

Let us take the following grammar:

$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
B \rightarrow & b \\
\end{align}
$$

This is my attempt:

For the grammar to be LL(1) it is a necessary condition that for any strings $c_1γ$ and $c_2β$, derivable from $S \rightarrow aB$ and $A \rightarrow aS$ respectively, we have $c_1 \ne c_2$.

But, $S \rightarrow aB$ and $A \rightarrow aS$, hence $c_1 = c_2$ and the grammar is not LL(1).

Is my reasoning right?

Thanks in advance.

If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).

In general, you compute the LL(1) parse table and use it to answer the question. Your grammar is LL(1) if each cell in the table has at most 1 grammar rule. In other words, at least one table entry has more than 1 rule implies that your grammar is not in LL(1): http://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL.281.29_parsing_table


Turn biased random number generator into uniform I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution:

$P(X = 0) = p,\;\;P(X=1)=1-p,\;\;0<p<1$,

then we can use rand() as a subroutine to create a unbiased sampler from the set {0,1}. My idea for this is along the following lines:

Choose some fairly large even integer n.
Create a table "t" containing two integers.
Loop over $i=1,\ldots,n$ sampling $x=rand()$ for each $i$. When $i$ is even increment $t[i]$ and when odd increment $t[1-i]$.
Return $0$ if $t[0]\geq t[1]$ and vice versa.

Now the expected value for $t[0]=t[1]=n/2$, so this should give a value very close to the uniform distribution. The only problem is that the set of outcomes in (4) is biased towards $0$, so for any fixed $n$, we do not get a uniform distribution, although we do get it in the limit. There has to be a way to get $n$ to depend on some random value to balance it out, but I can't figure out how.

Anyone have any other ideas how to approach this? The key in the problem was that we do not know $p$.

For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c_k$ be the number of inputs of Hamming weight $k$ which will cause you to return $1$. For your generator to be unbiased, you need
$$ \frac{1}{2} = \sum_{k=0}^n c_k p^k (1-p)^{n-k} = \sum_{\ell=0}^n \left(\sum_{k=\ell}^n c_k (-1)^{\ell-k} \binom{n-k}{\ell-k} \right) p^\ell. $$
If $p$ is transcendental or of the form $a/b$ for odd $b$ then the equation $\frac{1}{2} = \sum_{\ell=0}^n d_\ell p^\ell$ has no integer solutions $d_0,\ldots,d_n$. In particular, even if you know $p$, then in these cases no finite number of samples can be used to extract even one uniformly random bit.

The standard solution, attributed (IIRC) to von Neumann, is to use the following algorithm:

Repeatedly sample two biased samples $r_1,r_2$ until $r_1 \neq r_2$.
Return $r_1$.

Conditioned on $r_1 \neq r_2$, the two outcomes $(r_1,r_2)=(0,1)$ and $(r_1,r_2)=(1,0)$ have the same probability, and so the result is an unbiased bit.

How efficient is this generator? The probability that $r_1 \neq r_2$ is $2p(1-p)$, and so on average you will need $1/(2p(1-p))$ samples per bit. Compare that to the optimal extractor given by Shannon's source coding theorem: extracting $n$ bits should take $n/H(p) + o(n)$ samples with high probability (when $p$ is known).

The plot shows that the von Neumann algorithm is reasonably good but not optimal.


Which is the equivalent processing of human brain in terms of computer processing? How many flops my brain can process, or how many GHz is a human brain capable of?
Is it valid to think that each celular brain is like a small cpu? (like cuda architecture). Our brains works in parallel, right?

Here is what we know for sure. The largest neuronal network simulation to date was achieved using the K Japanese supercomputer (see the Top500) during summer 2013, a few months ago.

Using the open-source software NEST, the scientists simulated a network consisting of 1.73 billion nerve cells connected by 10.4 trillion synapses. To realize this feat, the program recruited 82,944 processors of the K Computer and used 1 petabyte of memory. The process took 40 minutes, to complete the simulation of 1 second of neuronal network activity in real, biological, time.
Although the simulated network is huge, it only represents 1% of the neuronal network in the brain.

K is a peta-scale supercomputer, so, we need an exa-scale machine to completely simulate the whole human brain. These machines will be (probably) available between 2017-2020.


Can intersection of non-context-free languages be context-free? For two languages over the same alphabet that are not context-free, can their intersection be context-free, Or does at least one of them have to be context-free?

Let $L$ be an arbitrary language. Then
$$ \{ 0x : x \in L \} \cap \{ 1x : x \in L \} = \emptyset. $$


How many vertices should be disconnected to make a graph acyclic? Given an undirected graph with some cycles:

we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.
My questions:

What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

The circuit rank is the number of edges that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
The vertex connectivity is the number of vertices that have to be removed to make the graph disconnected.)

A set of vertices whose removal makes the graph acyclic is called a feedback vertex set (FVS). What you seem to be doing is finding the smallest FVS, subdividing all edges incident to each vertex in the FVS, and finally deleting the vertices in the FVS.
Computing the smallest FVS is NP-hard, but it admits 2-approximation.


When do we need to change the state of a push down automata? I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition operation. An explanation would be appreciated. Thanks!

Also, my understanding of states is that they're basically the indicators in the machine, which let it know which operation is going on. Is this the correct analogy? If not, can you give a better one?

Edit: Regarding finite automata, I can understand when to change the state. But I'm confused in push down automata. Do you change the state only during push and pop, and during introduction of a new character? Or are there more reasons to change the state?

As Renato suggests, you never need to change state in a PDA. Even without useing a CFG as an intermediate, we can take a PDA and construct another that does the same job with using only a single state (a proof can be found here). The basic trick is to use the tape alphabet to encode the state of the original machine (and part of the transition). This works perfectly well for both deterministic and non-deterministic PDAs.

This is a little unsatisfying however, as a single state machine with a huge tape alphabet is not a particularly natural way to design a PDA (at least if you're like most humans I have met, there might be someone who thinks that way, if so, well done[!|?]). One intuitive reason to change state is as you suggest, because the machine is meant to be doing something different. Analogously to how we would talk about what we as humans are doing, for example, when we're working. We might break a task into steps, and perform them in a "sensible" sequence. The idea is the same with designing PDAs, break the recognition task into a series of steps, and change state when you move from one step to another.

As an example, consider the canonical non-regular context free language $\{a^{n}b^{n}\mid n\in\mathbb{N}\}$. In processing this language, we might have a starting state, a state for processing $a$s, a state for processing $b$s and an accept state. We move from the start state to the "$a$" state by pushing a botoom-of-the-stack symbol, then process the $a$s (probably by pushing a symbol for each $a$), then move to the "$b$" state using a $\varepsilon$-transistion, process the $b$s (popping off the symbols we put on for the $a$s), then move to the accept state if we have reached the end of the input and can see the bottom-of-the-stack symbol.

This is not the only way to build a PDA for this language, but the changing of states has a natural, intuitive meaning that is useful to us as humans in the design process (and for others trying to understand or implement it).

Unfortunately there's no simple "this is when to change states" rule. As the single state example shows, you can design things in a very arcane, incomprehensible manner, but they are still correct. Like a number of things in maths, CS and programming, you really have to just practice it a bit, look at other solutions and develop your own intuition. It is in many ways like programming (funnily enough) - there's lots of ways to solve a problem, only some are good ways, but there is at best only general guidelines to what to do when and where.


Verification condition in case of array theory As far as i can understand the problem of checking safety property, can be reduce to solving for inductive invariants in VC's and there is following parts to it:

Generate VC's from the program.
Solve it: If user provide inductive invariants just check the Validity of the whole VC formula.
Inferring problem : simultaneously solve the VC's taking these predicates as uninterpreted function that make all the VC's valid.

How hard the problem of checking 2. (User provide the inductive invariant) in the case of array theory? For example: Array sorting.

Sure, if the user provides inductive invariants, you can try to check the validity of the verification conditions.  However, this remains undecidable, as it requires checking the validity of a formula in first-order logic (with quantifiers and array expressions), and that's undecidable.

It might be feasible often enough in practice to be useful, especially since we might hope that programmers have a reason why their code is correct and won't write code that requires overly complex reasoning to prove correct.  But in general, it is undecidable.


Pumping Lemma for regular languages proof doubt - Sipser Book I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.

In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ places, we have $l \le p+1$". Here, does $l$ denotes the number of states visited?

Also he wrote  "We know that $j \neq l$, so $|y| > 0$; and $l \le p+1$; so $|xy| \le p$"

What I didn't understand is

$j \neq l$
$j \neq l$, so $|y| > 0$
$l \le p+1$; so $|xy| \le p$

You missed what $j$ and $l$ are. Read the paragraph again. They are the two indices of the same state in the list of visited states. For example if some  automata goes from $s_1$ to $s_3$ to $s_5$ to $s_3$ to $s_7$, then you could pick $j = 2$ and $l = 4$, because both $2$nd and $4$th elements in the sequence are $s_3$.

They are always (and, assuming $n > p$, can always be) chosen different.
$y$ was defined as the substring which takes $r_j$ to $r_l$. $j \neq l$ and you need at least one symbol to change state, hence $|y| > 0$.
The substring $xy$ takes $r_1$ to $r_l$. A string of length $x$ visits $x+1$ states, so if we know that $xy$ visited $l \leq p+1$ states then $|xy| = l-1 \leq p$.


Why does soundness imply consistency? I was reading the question Consistency and completeness imply soundness? and the first statement in it says:

  I understand that soundness implies consistency.

Which I was quite puzzled about because I thought soundness was a weaker statement than consistency (i.e. I thought consistent systems had to be sound but I guess its not true). I was using the informal definition Scott Aaronson was using in his 6.045/18.400 course at MIT for consistency and Soundness:

Soundness = A proof system is sound if all the statements it proves are actually true (everything provable is True). i.e. IF ( $\phi$ is provable) $\implies$ ($\phi$ is True). So IF (there is a path to a formula) THEN (that formula is True)
Consistency = a consistent system never proves A and NOT(A). So only one A or its negation can be True.

Using those (perhaps informal) definitions in mind I constructed the following example to demonstrate that there is a system that is sound but not consistent:

$$ CharlieSystem \triangleq \{ Axioms=\{A, \neg A \}, InferenceRules=\{NOT(\cdot) \} \}$$

The reason it's I thought it was it was a sound system is because by assumption the axioms are true. So A and not A are both true (yes I know the law of excluded middle is not included). Since the only inference rule is negation we get that we can reach both A and not A from the axioms and reach each other. Thus, we only reach True statements with respect to this system. However, of course the system is not consistent because we can prove the negation of the only statement in the system. Therefore, I have demonstrated that a sound system might not be consistent. Why is this example incorrect? What did I do wrong?

In my head this makes sense intuitively because soundness just says that once we start from and axiom and crank the inference rules we only reach at destinations (i.e statements) that are True. However, it does not really say which destination we arrive. However, consistency says that we can only reach destination that are reach either $A$ or $\neg A$ (both not both). So every consistent system must include the law of excluded middle as a axiom, which of course I did not and then just included the negation of the only axiom as the only other axiom. So it doesn't feel I did anything too clever, but somehow something is wrong?

I just realize it could be a problem because I am using Scott's informal definition. Even before I wrote the question I did check wikipedia but their definition didn't make sense to me. In particular the part that they say:

  with respect to the semantics of the system

their full quote is:

  every formula that can be proved in the system is logically valid with respect to the semantics of the system.

I recommend looking into formal logic beyond vague, hand-wavy descriptions. It's interesting and highly relevant to computer science. Unfortunately, the terminology and narrow focus of even textbooks specifically about formal logic can present a warped picture of what logic is. The issue is that most of the time when mathematicians talk about "logic", they (often implicitly) mean classical propositional logic or classical first-order logic. While these are extremely important logical systems, they are nowhere near the breadth of logic. At any rate, what I'm going to say largely takes place in that narrow context, but I want to make it clear that it is happening in a particular context and need not be true outside of it.

First, if consistency is defined as not proving both $A$ and $\neg A$, what happens if our logic doesn't even have negation or if $\neg$ means something else? Clearly, this notion of consistency makes some assumptions about the logical context within which it operates. Typically, this is that we are working in classical propositional logic or some extension of it such as classical first-order logic. There are multiple presentations, i.e. lists of axioms and rules, that could be called classical propositional/first-order logic but, for our purposes, which doesn't really matter. They are equivalent in some suitable sense. Typically, when we are talking about a logical system we mean a (classical) first-order theory. This starts with the rules and (logical) axioms of classical first-order logic, to which you add given function symbols, predicate symbols, and axioms (called non-logical axioms). These first-order theories are usually what we're talking about as being consistent or inconsistent.

Next, soundness usually means soundness with respect to a semantics. Consistency is a syntactic property having to do with what formal proofs we can make. Soundness is a semantic property that has to do with how we interpret the formulas, function symbols, and predicate symbols into mathematical objects and statements. To even begin to talk about soundness, you need to give a semantics, i.e. an interpretation of the aforementioned things. Again, we have a separation between the logical connectives and logical axioms, and the function symbols, predicate symbols, and non-logical axioms. What makes connectives connectives and logical axioms logical axioms from the semantic point of view is that they get treated specially by semantics while function symbols, predicate symbols, and non-logical axioms do not. The typical semantics for classical first-order logic is to interpret formulas as set-theoretic relations on some (power of a) set called the "domain" given as part of a particular semantics, and the connectives as the more or less obvious set-theoretic analogues, e.g. $[\![\varphi\land\psi]\!]=[\![\varphi]\!]\cap[\![\psi]\!]$ where I use $[\![\varphi]\!]$ as the interpretation of the formula $\varphi$. In particular, $[\![\neg\varphi]\!]=D\setminus[\![\varphi]\!]$ where $D$ is the domain set. The idea is a formula is interpreted as the set of (tuples of) domain elements that satisfy the formula. A closed formula (i.e. one with no free variables) is interpreted as a nullary relation which is to say a subset of a singleton set which can only be that singleton or the empty set. A closed formula is "true" if it isn't interpreted as the empty set. Soundness is then the statement that every provable (closed) formula is "true" in the above sense.

It is easy from here, even from the sketch I've given, to prove that soundness implies consistency (in the context of classical first-order logics and the semantics I've sketched). $$[\![\varphi\land\neg\varphi]\!]=[\![\varphi]\!]\cap(D\setminus[\![\varphi]\!])=\varnothing$$ If your logic is sound, then every provable formula interprets as a non-empty set, but $[\![\varphi\land\neg\varphi]\!]$ is always interpreted as the empty set no matter what formula $\varphi$ is, and so it can't be provable, i.e. your logic is consistent.


Containment of ACC$^0$ in TC$^0$ The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits.  However, what the linked paper proves is that depth-3 threshold circuits of quasipolynomial size can simulate ACC$^0$ circuits.

Wouldn't it be necessary to prove that constant depth threshold circuits of polynomial size simulate them rather than quasipolynomial?  Is it obvious how to do the simulation with just a polynomial number of gates?

You can show directly how to simulate a polynomial fan-in modular gate using polynomially many threshold gates. The idea is that given inputs $x_1,\ldots,x_m$, you can use two threshold gates and an AND gate to determine whether $x_1 + \cdots + x_m = w$ for any $w$. Taking at most $m+1$ copies of this gadget and ORing them, we can simulate a single modular gate.


recursively enumerable sets closed under concatenation I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I must  consider the Cartesian product $S_1\times S_2$ of two recursively enumerable sets $S_1$ and $S_2$. Then I construct the function $f':S_1\times S_2\rightarrow \lbrace 1\rbrace\cup\lbrace\perp \rbrace$ (where $\perp$ is undefined) such that: $$f'(x,y)=\begin{cases}
 1 &\text{  if } x\in S_1 \text{ and } y\in S_2\\
 \perp&\text{ otherwise}
\end{cases}$$
Does the mere existence of this function $f'$ show that $S_1S_2$ is recursively enumerable?
I'm still new to these proofs, so any help would be appreciated.

What you need to show is that given an algorithm that enumerates a (possibly finite) sequence $a_1,a_2,a_3,\ldots$, and another algorithm that enumerates a (possibly finite) sequence $b_1,b_2,b_3,\ldots$, then you can come up with another algorithm which enumerates all words of the form $a_i b_j$.

The simplest approach is to use the same idea that Cantor used to prove that the rationals are equinumerous with the integers, namely to come up with an algorithm that enumerates $a_i b_j$ in the following order:
$$
a_1 b_1, a_1 b_2, a_2 b_1, a_1 b_3, a_2 b_2, a_3 b_1, \ldots
$$
I'll let you to fill in the details.


How to evaluate the learned prototypes for multivariate time-series (e.g. motion)? Consider a method which finds prototypes for multivariate time-series (MTS) data, and is designed to find prototypes for each class of data.
For example, the {walking} class consists of some slightly different types of {walking} sub-classes, but they are not annotated. So i want to check if my prototypes can adequately represent the variations within each class and to measure the quality of the estimated prototypes.

In fact, I can calculate the distance of the prototype to the data points, but since it is possible to have more than one prototype per class/cluster, i cannot decide to which data point i should calculate this distance.

If the data is related to motion data, it is possible to watch the resulted prototypes to check how sensible they are. However, i'm not sure how to measure their quality in a numerical way?

You note " but with more than one prototype per class/cluster."

We often call this a polymorphic class. Consider the analogue in text..

C1 = { dpacekfjklwalkflwalkklpacedalyutekwalksfj}
 C2 = { jhjhleapashljumpokdjklleaphfleapfjjumpacgd}

Here the class 1 prototypes are polymorphic {walk OR pace}, and so is class 2 {leap or jump}.

You can learn these prototypes with a dictionary building method, and "measure their quality in a numerical way" with just classic accuracy (or precision recall etc).

Using nearest neighbor, the distance between and unknown item, say 'balk' is just defined as:

dist('balk', C1) = min(dist('balk','walk'),dist('balk','pace'))
and
dist('balk', C2) = min(dist('balk','leap'),dist('balk','jump'))

Paper [a] explains one nice dictionary building method, but there are other ways.

[a] http://www.cs.ucr.edu/~eamonn/SDM_RealisticTSClassifcation_cameraReady.pdf


Recurrence formula for optimal binary search tree This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For each key $k_{i}$, where $1\leq i \leq n$, we have a probability $p_{i}$ that a search will be for $k_{i}$.
We let the sequence $d =\{ d_{0},d_{1},\dots,d_{n} \}$, where $d_{0}<d_{1} <\dots<d_{n} $, be for values not in $k$.
For each key $d_{i}$, where $0\leq i \leq n$, we have a probability $q_{i}$ that a search will be for $d_{i}$.
The goal is to construct an optimal binary search tree.
Let us define $e[i,j]$ as the expected cost of searching an optimal binary search tree containing the keys $k_{i},\dots,k_{j}$.
Let $w(i,j) = \sum_{l=i}^{j} p_{l} + \sum_{l=i-1}^{j} q_{l}$.
The book gives the following equation as the recurrence formula for forming the optimal binary search tree:
$$
e[i,j] = \begin{cases}
q_{i-1} & \text{if } j = i-1, \\
\displaystyle\min_{i\le r\le j} \{e[i,r-1]+r[r+1],j]+w(i,j)\} & \text{if } i \leq j.
\end{cases}
$$
This formula makes sense for $i\leq j$, but I don't understand the case $j = i-1$.

Why is $e[i,i-1] = q_{i-1}$?

Quoting Introduction to Algorithms:

The easy case occurs when $j = i-1$. Then we have just the dummy key $d_{i-1}$.
The expected search cost is $e[i,i-1] = q_{i-1}$.

In slightly more detail, $e[i,j]$ is supposed to be the cost of the optimal binary search tree for $k_i,\ldots,k_j$. It is important to understand what cost means here. The cost is with respect to the following distribution on the input:

With probability $p_i$, key $k_i$ is being searched.
With probability $q_i$, a dummy key $d_i$ between $k_i$ and $k_{i+1}$. (When $i = 0$, it is a key smaller than $k_1$, and when $i = n$, it is a key larger than $k_n$.)

Unfortunately, the textbook is being extremely sloppy, and never bothers to explain what they mean by "the cost of the optimal binary search tree for $k_i,\ldots,k_j$". It seems that they are measuring the expected cost with respect to the stated keys as well as with respect to the dummy keys $d_{i-1},\ldots,d_j$. That is, they want to minimize
$$
q_{i-1} \mathit{cost}(d_{i-1}) + p_i \mathit{cost}(k_i) + q_{i+1} \mathit{cost}(d_{i+1}) + \cdots + q_{j-1} \mathit{cost}(d_{j-1}) + p_j \mathit{cost}(k_j) + q_j \mathit{cost}(d_j).
$$
When $j = i-1$, there are no real keys, but there is a dummy key $d_{i-1} = d_j$, and so the cost is $q_{i-1} \mathit{cost}(d_{i-1})$. The optimal cost here is clearly $1$, and that's how they get $q_{i-1}$.


Can a unnormalized floating point number be recognized also when exponent is not zero? From Tanebaum's Structed Computer Organization.

  Exercise 4 of Appendix B

  The following binary floating-point number consist of a sign bit, an excess $64$, radix $2$ exponent, and a $16$-bit fraction. Normalize $0$ $1000000$
  $0001010100000001$ ($\star$).

As far as I've studied, the number ($\star$) is already normalized and it is a representation of the number $1.0001010100000001 \times 2^0$.
Moreover, according to the IEEE754, if one is meant to represent an unnormalized number, she would have to set the exponent-related bits at $0$ --which is not the case.

My question is: what is the exercise asking to me? Can that be an unormalized number?

Maybe Tanebaum's simply asking the reader to multiply ($\star$) by $2^3$ then to subtract $3$ from the exponent. Yet to me, that has no sense at all --instead, you're really changing the value ...

I had to re-read your question a few times to have an opinion. The question states that there exists a sign, an excess 64 exponent, and a 16-bit mantissa. It then asks you to normalize a given bit pattern. It's my opinion that you are supposed to make some inferences.

First off, an excess 64 suggests that you have a 7-bit mantissa. (It's not certain as one technically could have an excess 64 applied to an 8-bit or even a 9-bit mantissa, but those are all highly unlikely in normal circumstances.) This appears to be confirmed in the sense that they supply what appears to be one bit, followed by 7 bits, followed by 16 bits.

Second, you are being asked to normalize a value. This is commonly asked by providing you with the signed number and a positioned radix, leaving you to figure out the sign, exponent, and mantissa. But in this case, their question must be taken to imply that they are giving you a denormalized value. So I believe they want you to accept the last 16 bits just as it is given to you and to do the necessary shifting to put it back into a properly normalized form. And I therefore think they want you to accept the given exponent as a starting point that you assume is correct for the given value.

This leads to the third problem. You inserted a hidden bit on your own, on the assumption that the denormalized value carries a hidden bit. But denormalized values, even in FP formats supporting hidden bits (and not all do that) do not have an implied hidden bit. So I wonder why you inserted one on your own, writing "$1.0001010100000001\times 2^0$." If you were right about that, then why in the world would they now ask you to normalize it?? It doesn't make any sense, neither in the format of the question nor in actual experience with common cases. So I think here you must assume the opposite... that the 16 bit mantissa they gave you is instead just a pure 16-bit integer that has not been normalized and doesn't imply a hidden bit. Otherwise, what could they possibly be asking you to do?

That said, I haven't worked from your book. So I don't know the context here. You will have to use your own judgment about what I write here and see if you think I might be right about it.

If I am right, then you are being told $sign=0$, $exponent=0$ as it is in excess 64, and $value=5377$ (decimal.) And you are then asked to normalize it and create a proper 24-bit FP formatted value. Since you mentioned IEEE754, which uses hidden bit notation, I'd assume that this novel 24-bit FP format also uses hidden bit notation. I wish I had your book, as that would help to gain context, but I get something like the following: $0 \,\, 1001100 \,\,\, 0101000000010000$


Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph Is there any efficient algorithm to find shortest distance between all pairs of vertices?

The graph is:

Cyclic
Sparse (each vertex has either 2 or 3 edge)
undirected(bidirectional)
weighted
non-negative

Since Floyd-Warshall algorithm and Johnson's algorithm are best for finding shortest path for every pairs but:

Johnson's algorithm works on directed
Floyd-Warshall algorithm is best for dense graphs

I couldn't find any algo that is efficient for above graph conditions.

Mikkel Thorup's paper Undirected Single-Source Shortest Paths with Positive
Integer Weights in Linear Time shows an $O(m)$ time algorithm for single-source shortest paths on undirected weighted graphs. That immediately implies an $O(mn)$ time algorithm for all pair shortest paths, which is the optimal $O(n^2)$ in your scenario.


Efficient algorithm for rectangle containment Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988).  Is there a $O(n \log n)$ algorithm for axis-aligned rectangles in higher dimensions?

I did some search on the internet, and tried to think about it myself, but could not find a generalization for higher dimensions.  For example, given $n$ axis-aligned rectangles on the plane, the task is to find which rectangles are contained in other rectangles.

Have you considered multi-dimensional indexes? They are usually quite efficient to find overlapping or included rectangles.

I personally wrote a kind of prefix-sharing binary quadtree: Java sources
It has an API for rectangles with a special method for searching rectangles included in another rectangle: PhTreeSolidF.queryInclude().

I'm not sure what the complexity is but it's roughly something in the order of O(n*k*log n) to build the tree and O(k*log n) for each query (k is the number of dimensions). For strongly clustered datasets it may even become something lose to O(1) for each query (I tested this with n=10.000.000 and 2<=k<=15).