Why are computers so complicated? I'm not sure this is on-topic or even the right website, please point me in the right direction if not.

I was wondering why computers are so incredibly complex. This question is as naive as it sounds, I'm really just looking for a nice explanation of why computers can't be like the airplane from Blyton's The Faraway Tree, where you push a button to go up, down, left or right.

The main reason why computers are complicated is because they are really optimized to deliver the maximum speed. There are a lot of places in a computer where information is stored:

processor registers: here the speed of memorization is really high, but this memory is very expensive;
random access memory: slower and cheaper then processor registers, but more expensive and faster then hard disk memory
hard disk: one of the cheapest and slowest kinds of computer memory

There are also cache mechanisms in between of these levels.

The first definition of computer is that of a person computing some arithmetical operation. So a person could be seen as a very familiar kind of computer, or a biologically very complex one.

Not all computer models are complicated. It has been proved that the following models can compute the same types of problems:

Turing machines: just a tape and a finite state automata;
lambda calculus: few definitions are enough to achieve a system to manipulate symbols;
Godel's general recursive functions


Understanding memory leaks in C/C++ I was looking at an example here:
https://blog.parasoft.com/finding-memory-leaks-in-c

#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char *string, *string_so_far;
    int i, length;     length = 0;
    for(i=0; i<argc; i++) {
        length += strlen(argv[i])+1;
        string = malloc(length+1);

        /*  * Copy the string built so far. */
        if(string_so_far != (char *)0)
            strcpy(string, string_so_far);
        else *string = '\0';
        strcat(string, argv[i]);
        if(i < argc-1) strcat(string, " ");
        string_so_far = string;
    }
    printf("You entered: %s\n", string_so_far);
    return (0);
}

and read that when we execute the program with the following arguments:

hello this is a test

The variable string_so_far points to the string “hello” which was assigned as a result of the previous loop iteration. But I don't understand how? A step by step explanation would be really helpful.

Secondly, I came across this example in course material:

int countPrimes(int n)
{
   PrimeSet *p = new PrimeSet(n);
      return( p->countPrimeNumbers() );
}

It was stated that there's a memory leak here but I don"t really understand how, probably because I am not sure what exactly is happening here.

In your second example, you allocate space for a PrimeSet object and initialise it, then you call the countPrimeNumbers function. The PrimeSet object still exists, it still occupies memory, it probably allocated more memory, and all that memory is still occupied but not accessible. That’s a memory leak: Memory that is occupied but unusable.


how to approximate a very complex optimal policy when the distance function is unknown A policy $P$ is defined as a set of parameters. We want to know the optimal policy $O$, which certainly exists but unfortunately unknown.

$D(P)$ shows how far $P$ is from $O$. The function $D$ itself is unfortunately not known. However, $D(P) - D(Q)$ is known. That is, one can always know which among $P$ and $Q$ is closer to $O$.

What kind of approach can be done for such problem?

In my setting, a policy is in a form of a (convolutional) neural network. $D(P) - D(Q)$ is approximated by a simulation involving an agent with policy $P$ and an agent with policy $Q$. We repeatedly play a two-player game with a clear win/loss where $P$ plays against $Q$. The value of $D(P)-D(Q)$ is equal to the number of times $P$ wins against $Q$, divided by the number of games we play.

Let me start with some basic material that covers the case where you know how to compute $D(P)$; then speculate on some methods that might be applicable to your particular situation, where we only know how to compute $D(P)-D(Q)$.

Gradient descent. One reasonable approach is to use gradient descent to optimize the parameters.  If we have an objective function $\Phi(P)$ that tells us the penalty or loss associated with policy $P$, we use gradient descent to try to find parameters $P$ that minimize $\Phi(P)$.  This requires that $\Phi(\cdot)$ be continuous and differentiable.  Ideally, we'd have a way to compute the partial derivatives (the gradient) of $\Phi$ at any point; but if we don't, one possibility is to use standard methods to approximate the partial derivative, e.g.,

$${\partial \over \partial x} \Phi(P) = {\Phi(P+\epsilon x) - \Phi(P-\epsilon x) \over 2 \epsilon}.$$

Stochastic gradient descent. In your situation, stochastic gradient descent is an important optimization that provides significant speedups.  The basic idea is that, if we can decompose the objective function as a sum

$$\Phi(P) = \sum_i \Phi_i(P),$$

then we can speed up gradient descent.  In each step, we evaluate the gradient of $\Phi_i$ (rather than of $\Phi$, as ordinary gradient descent would do) and take a small step in the direction given by that gradient.  This can be a lot more efficient, if computing the gradient of $\Phi_i$ is more efficient than computing the gradient of $\Phi$.

In your situation, $\Phi(P)$ is defined to be

$$\Phi(P) = \sum_{i=1}^n {w_i(P) \over n},$$

where $w_i(P)$ is 1 if $P$ wins in the $i$th game and 0 otherwise.  Therefore, $\Phi$ has the required form to allow you to apply stochastic gradient descent, and you can expect this method to give significant speedups.  Effectively, you do only one game simulation per step of (stochastic) gradient descent rather than $n$ game simulations per step.

As a practical matter, there are many further improvements on stochastic gradient descent that are well-studied, including momentum, rmsprop, and many others.  Personally, I'd recommend trying the Adam solver; it seems to be state of the art.

So if you knew how to compute $D(P)$, the above would give you a reasonable method for optimizing $P$: simply define $\Phi(P)=D(P)$ and then apply stochastic gradient descent.  But you don't... so now we need a way to adjust.

Your situation.  Your specific situation is more challenging, but there are still some avenues you could explore.  For instance, here is one approach you could consider.  Fix a reasonable policy $Q_0$, and define

$$\Phi(P) = D(P) - D(Q_0).$$

Apply stochastic gradient descent to try to minimize $\Phi(P)$, i.e., to find $P$ that makes $\Phi(P)$ small.  Do that for a little while.  Then, pick a new policy, call it $Q_1$, and define

$$\Phi(P) = D(P) - D(Q_1)$$

and continue iterating.  Every so often, you replace $Q_i$ with a new (better) policy $Q_{i+1}$ that hopefully is closer to $O$.  This might work.

How do you choose $Q_{i+1}$?  One way would be to let $Q_{i+1}$ be the best policy seen so far.  So, effectively, you are constantly trying to find a policy that beats the best policy seen so far.  You'd need to tune how often you change $Q$ and play with some parameters.

Caveats.  However, I suspect that if you're actually dealing with a two-player game, things won't be this simple.  In particular, I suspect that your model of the situation is not accurate: that, for several reasons, the fraction of times that $P$ wins against $Q$ is not actually an estimator of $D(P)-D(Q)$.

The relationship between "fraction of wins" vs $D(P)-D(Q)$ is probably not linear.  For example, Magnus Carlsen (world chess champion; rated about 2800) will beat me 100% of the time in chess.  He will presumably also beat Arnold Schwarzenegger (rated about 1500) 100% of the time.  But Arnold will probably beat me 100% of the time, too, because I suck at chess.  Letting $P_M = $ Magnus Carlsen, $P_A = $ Arnold Schwarzenegger, and $P_D = $ me, it can't be simultaneously true that $D(P_M)-D(P_D)=1$, $D(P_M)-D(P_A)=1$, and $D(P_A)-D(P_D)=1$, yet that is what your assumption implies.
Strategies usually aren't totally ordered.  Sometimes we have situations where one strategy is especially effective against another strategy (more than you'd expect based on their overall strength).  For instance, we can have situations where Alice usually beats Bob, Bob usually beats Charles, and Charles usually beats Alice.  Your framework doesn't take this into account.

You'll probably need more sophisticated methods to deal with these challenges.  For instance, one possibility is to build a small collection of different baseline strategies $Q_1,Q_2,\dots,Q_k$.  Then, evaluate $P$ according to how well it does against all of these: e.g., have $P$ play $n/k$ games against each $Q_i$, count the total number of wins for $P$, and divide by $n$.

This leaves open the question of how you select the baseline strategies $Q_1,\dots,Q_k$.  You might want each $Q_i$ to be as strong as possible, but also want to have some diversity in the pool, so $Q_i,Q_j$ are as different as possible for all $i,j$.  That requires a way to measure how similar two strategies $Q_i,Q_j$ are.  One way might be to play a game between $P$ vs $Q_i$; at each board position reached, compare how often $Q_i$ would select the same move as $Q_j$.  To select a collection of baseline strategies, you could try to solve an optimization problem where you select among the s policies you've explored so far, while maximizing some objective function that rewards selecting strong strategies but penalizes similarity between selected strategies.

There are probably many challenges here, but hopefully this gives you some ideas you can try out.


What is a protocol for determining which of two numbers is larger, without sharing those numbers? Situation: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a > b$, $a = b$, or $a < b$, but neither wishes to reveal their chosen number to the other party.

How can Alice and Bob make this determination?

As pointed out by Luke Mathieson in the comments, this problem is called Yao's Millionaire Problem, for which protocols can easily be found by Googling.


Recurrence Substitution Method with multiple givens Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$
Given $T(0)=3$ and $T(1)=5$

I kind of understand it with only one given and one recurrence call by expanding the call using what is inside.
ex. if it was $T(n)=T(n-1)+3$
Given $T(1)=5$
I would take the $n-1$ and plug it into the the first equation $T(n)=T(n-1)+3$
and repeat until I can find a general case. After that simplify it to get my answer.

My problem is when I have two givens and two recurrences. I first though about solving each one separately using the first recurrence and then the second but it wasn't making any sense to me.

Let $S(n) = T(n) + 1.5$. Then
$$
S(n) = T(n) + 1.5 = T(n-1) + 2T(n-2) + 4.5 = S(n-1) + 2S(n-2).
$$
The recurrence $S(n) = S(n-1) + 2S(n-2)$ is homogeneous with constant coefficients, so we know how to solve it. We first solve the equation $\lambda^2 = \lambda + 2$, finding that the solutions are $2,-1$. This implies that there exist constants $A,B$ such that
$$
S(n) = A 2^n + B (-1)^n.
$$
Since $S(0) = 4.5$ and $S(1) = 6.5$, we see that $A + B = 4.5$ and $2A - B = 6.5$, from which we find that $A = 11/3$ and $B = 5/6$. Therefore
$$
T(n) = \frac{11}{3} 2^n + \frac{5}{6} (-1)^n - \frac{3}{2}.
$$


Number of possible min heaps The number of possible min-heaps containing each value from {1, 2, 3,
  4, 5, 6, 7} exactly once is --------------

According to me, the answer should be 48. The first element 1 is fixed as root. The next level contains elements 2 and 3. The third level contains 4,5,6,7.
Therefore, the total no. of cases should be 4! * 2!=48.

But my solution manual says that the answer should be 80.

Am I correct? If not, what am I doing wrong?

Thanks in advance

The second level can contain other numbers than 2 and 3. See for example

      1
     / \
    2   5
   / \
  3   7
 / \
4   6

It is also unclear if you count isomorphic trees. See this question for a related answer.


Small-step semantics: for-loops I'm trying to construct the small-step semantic rules involving the for-loops, but I can't find anything about it in the literature (only about while-loops).

I was wondering if anyone could help me out with this? This is a first attempt, where $s$ represents a statement and $e$ an expression:

$\quad \displaystyle\sigma, \text{for } s_1 \, e_1 \, e_2 \, s_2 \, \rightarrow \, \sigma, \text{if } e_1 \text{ then (} s_2 ; \, e_2; \, \text{for } s_1 \, e_1 \, e_2 \, s_2 \text{ ) else } skip$

Where $\sigma$ is a local value store, $s_1$ is for example $i = 0$, $e_1$ could equal $i < 4$ and $e_2$ $i=i+1$.

Your attempt does not work. Note that $s_1$ is never executed. (And if you prepend the right-hand side with "$s_1;$", it will be executed multiple times.)

What you can do is to translate the for loop into an equivalent while loop:

$$\sigma,\text{for } s_1, e_1, e_2, s_2 \text{ endfor} \to \sigma, s_1; \text{while } e_1 \text{ do } s_2; e_2 \text{ endwhile}.$$


Is Gale Shapley globally optimal? Let us have a set of N men and N women, and we have two matrices of affinities $M$ and $W$ such that $M(i,j)$ is the affinity of the ith man towards the jth woman and $W(i,j)$ is the affinity of the ith woman towards the jth man.

The problem at hand is to find an optimal stable marriage, which satisfies that:

There is no couple of man and woman not married such that they would prefer to be with each other (have higher affinity towards) rather than their actual partners.
The sum of the affinities of each couple is maximal among the stable marriages.

Does vanilla Gale Shapley solve this problem? If not, is it NP-complete or is there any hope of solving it polynomially?

No, Gale-Shapley optimizes a different set of criteria; see https://en.wikipedia.org/wiki/Stable_marriage_problem.  It maximizes the men's happiness, which doesn't necessarily maximize the total happiness sums.  It is easy to come up with counterexamples by taking any stable marriage solution where some woman doesn't get her first choice -- say, Alice's first choice is Bob, but she isn't assigned to Bob in the assignment output by Gale-Shapley -- and then making Alice's affinity towards Bob be some enormous number, far larger than all other affinities.

I don't know if it can be solved in polynomial time.  Without the stability requirement, it's an instance of the assignment problem.  With the stability requirement added on, I don't know whether it can be solved in polynomial time.


Find function that satisfy the relation Can you find the function that satisfy the relation?

$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$

Check the definitions (as commonly used in Computer Science, mostly for run time or other resource consumption):

$f(n) = O(g(n))$ if there is a constant $c_1 > 0$ so that for some $N_1$ we have for $n \ge N_1$ that $f(n) \le c_1 g(n)$

$f(n) = \Omega(g(n))$ if there is a constant $c_2 > 0$ so that for some $N_2$ we have for $n \ge N_2$ that $f(n) \ge c_2 g(n)$

$f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

$f(n) = o(g(n))$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 0$

$f(n) \sim g(n)$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 1$

$f(n) = \omega(g(n))$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = \infty$

You see that $f(n) = \Omega(g(n))$ (one part of $f(n) = \Theta(g(n))$) and $f(n) = o(g(n))$ can't be true simultaneously (check the definition of the limit).


Perceptron learning rule past exam question I'm struggling to solve this past paper question and my lecturer is being less than helpful. The question is:

Apply the perceptron learning rule to update the current weight vector (0.1, 0.3) when the learning rate is 0.01, the input vector is (2.0, 4.0), and the error vector is (1, -1).

What has me confused is the use of vectors for the current weight, input and error value. We've never used vectors for this before (only regular numbers) and no examples I can find online use 2D vectors like this.

I know the perceptron learning rule is:

New weight = old weight + (learning rate * perceptron input * error value)

But I'm not sure how to do this kind of maths with 2D vectors to get a 2D vector as my result (which is what I assume I want, since the question seems to be asking for the new weight).

Firstly let me say that I am not going to solve this for you. What I would do instead is help you figure out how to solve it all by yourself.

How many inputs will your perceptron have if your input vector is in n-D?
Conceptually, what does the output from a perceptron represent?
Following from the second point, what does updating the weights do to the output from your perceptron?
Ideally, what should the updating of the weights do to the output?
When do you need to update the weights?

Think about this by plotting the inputs and output from the perceptron on a graph.

These are some of the basic concepts you need to understand to get the basics of Artificial Neural Networks (ANNs).

Good Luck


Operating System Paging concept I am quoting a paragraph from the book "Operating System Principles" by Galvin.

  Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of $2^{32}$ physical page frames. If frame size is 4 kB, then a system with 4-byte entries can address $2^{44}$ bytes (or 16 TB) of physical memory.

Now, I know we have $2^{44}$ bytes of memory because we have $2^{32}$ page frames and each frame size is 4 kB, i.e. $2^{12}$ bytes of memory, so physical memory is $2^{32}\cdot2^{12} = 2^{44}$.

Please help me to understand the following:

How did we get the number of frames as $2^{32}$?
If the logical memory space is $2^{32}$ then what should the physical memory space be (considering both the fully used and partially used logical address space concept)?

I found (surprisingly many) copies of that text on the web (see
http://www.slideserve.com/janna/virtual-memory). That helps
ascertaining there is no vocabulary mismatch.

The 32-bit entry makes for $2^{32}$ physical (not logical as you write in
your comment) address space for pages, i.e. $2^{32}$ frames.  The address
of the logical page is used for indexing the page-table, and the 4
bytes content of the corresponding entry of the page table is the
address of a page frame, i.e. a physical page.

So you have $2^{32}$ physical pages. But there is nothing in the above text that tells the size of the logical space. It could be much larger, with logical page addresses of 8 bytes, or it could be smaller which did happen on some architectures. For more details on this, see this discussion regarding virtual memory on 32 bits hardware. There may be other issues with more recent 64 bits hardware. The size of the page-table would tell you what is the size of the virtual memory space, i.e. of logical addresses.

Does this clarifies the problem?


Fitting a polynomial to a set of points or to a skeleton Available data

Available to me is a set of points which can be represented as shown in image 1:

Also available to me is a non-continuous path derived from this data. It is not important how this non-continuous path is obtained. It is however important, that it roughly represents a curve I intent to approximate. This non-continuous path is shown in image 2:

Goal

I want to approximate this data using a polynomial of either second or third degree. Examples of these approximations are shown in images 3, 4:

Problem / question

Now I am looking for a way to obtain the red curve. Some details confuse me, where my knowledge is likely to be simply lacking. For example, how to fit a polynomial, when technically what I require is not a function, at least not in this coordinate system, because there will be situations where an x value is being assigned two y values.

I thought of possibly using the ends of my path to define a new x-axis, but I consider this approach faulty. Another consideration are Splines.

How should I go about obtaining this red curve from the non-continuous path (preferred) or from original data? What sources should I look into?

Apologies if this is an already answered question which I suspect it might be. However I have been issuing search queries for this without success, hence my question.

You can try fitting a multi-dimensional polynomial regression. It seems that for your data, a two dimensional regression model should be fine:
$$ (a)x^2 + (b)x + (c)y^2 + (d)y + (e)xy + (f) $$

In python for example, you can fit a proper model using:

import numpy as np
from sklearn.preprocessing import PolynomialFeatures

X = np.array([ [x0,y0], [x1,y1], ...  ])
poly = PolynomialFeatures(2)
poly.fit_transform(X)
poly = PolynomialFeatures(interaction_only=True)
poly.fit_transform(X)


How to find number of combinations of choosing one from k subsets Consider we have set S:

S = {1,2,3,4,5,6}

and 3 (say k) subsets of S:

S_1 = {1,2,3}

S_2 = {2,3,4,5}

S_3 = {1,3,6}

What is the total number of cases choosing one element from each subsets?

Same element cannot picked from different subset, and the order is not considered.

For example,

S_1 = {2}, S_2 = {3}, S_3 = {6}

and

S_1 = {3}, S_2 = {2}, S_3 = {6}

considered as same. And

S_1 = {3}, S_2 = {3}, S_3 = {1}

is invalid since S_1 and S_2 choose the same element.

How can I formulate this?

You can solve this problem with the inclusion exclusion principle.

Assume you have two subsets $S_1, S_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S_1$ multiplied by the number of ways of choosing an element from $S_2$ minus the number of ways of choosing the same number from $S_1$ and $S_2$.

Now given three sets $S_1, S_2, S_3$, the number of ways of choosing one element from each such that all elements are different is
$$|S_1||S_2||S_3| - |S_1 \cap S_2| |S_3| - |S_1 \cap S_3||S-2| - |S_2 \cap S_3| |S_1| + |S_1 \cap S_2 \cap S_3|.$$

Now given a family of $k$ subsets, you can use the inclusion-exclusion principle to prove that the count can be given by the formula
$$
\prod\limits_{i \in [k]}|S_i| + \sum\limits_{I \subseteq [k], |I|\geq 2}(-1)^{|I|} \left|\bigcap\limits_{i \in I}S_i\right|\prod\limits_{i \notin I}|S_i|
$$


Superposition calculus: Elimination of redundant atoms Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant atoms', discusses the question of when, having used one clause to derive another, you can throw away the first clause instead of ending up with both. As discussed in Redundancy elimination in the superposition calculus you cannot do this in the general case, but you can do it in some particular cases, such as when discarding tautologies or subsumed clauses.

"Let C = Γ, u ≈ v → ∆ be a clause in N. If N |= Γ → u ≈ v, ∆, then N |= Γ → ∆, so that C can be simplified to Γ → ∆. A particular case is the elimination of multiple occurrences of atoms in the antecedent. For example, if C = Γ, u ≈ v, u ≈ v → ∆, then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology and hence trivially implied by N. Redundant atoms in the succedent can be eliminated in a similar way."

Hang on. "elimination of multiple occurrences of atoms in the antecedent", "Redundant atoms in the succedent can be eliminated" - it would certainly be nice if you could do this, but as I understand it, as discussed in https://stackoverflow.com/questions/29164610/why-are-clauses-multisets you have to treat clauses as multisets, not sets, you cannot just throw away multiple occurrences of the same atom. What am I missing?

And "then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology" - as I understand it, this is true, a clause which contains both an item and its negation is indeed a tautology and you really can promptly discard tautologies, but what does that have to do with multiple occurrences of the same atom with the same polarity? How is that sentence connected to the rest of the paragraph?

This one seems to be a case of a not very careful choice of notation in this paper.

So we have a clause $C = \Gamma, u\approx v, u\approx v \to \Delta$ in $\mathcal{N}$.

We could use the simplification rule as follows. Let $\Gamma_1 = \Gamma, u\approx v$. Then the following two conditions hold:

$C = \Gamma_1, u\approx v \to \Delta$ in $\mathcal{N}$
$\Gamma_1 \to u\approx v, \Delta$ is a tautology therefore it can be added to $\mathcal{N}$ without loss of soundness.

Now applying the simplification rule we can replace $C$ with $\Gamma_1\to \Delta$. From the definition of $\Gamma_1$ we have replaced $C$ with the clause $\Gamma, u\approx v\to\Delta$. Effectively the second occurrence of the atom $u\approx v$ has been removed.

They also claim that the same procedure works for removing of multiple occurrences in the succedent.

Also note that this is not specific to equational theorem proving and applies to any atoms.


Complexity calculations, assumptions on basic costs Possible Duplicate:
  How can we assume comparison, addition, … between numbers is $O(1)$

When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions) on our calculation. For instance we say that assume basic arithmetic operations are all constant time and we assume reading/writing to a memory location is constant time.

I've worked on some algorithms where these assumptions don't hold. I'm looking for the background I need to properly approach/describe these algorithms. In particular I wish to know:

What is the generic name for such a simplification/assumption?
Is there a name for the basic model of simplifications we're using? (Assuming there is a common model)

Note: I've done work with cache-dependent/cache-oblivious algorithms. I understand how to calculate in that domain, but I'm lacking the terminology/background to properly compare/contrast such algorithm analyis with that which don't consider the cache.

It is generally referred to as "Random Access Machine" or RAM model. This model assumes that accessing any unit of data, irrespective of its position or type, takes the same constant amount of time. Now, what you take as a "unit" of data is important. For all practical purposes, we may consider the primitive data types, integer, float and characters (but not strings) as a unit of data. A single instruction on unit data is considered to take constant amount of time.


Prove no DFA with four states can accept L={111} Assume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?

This depends on your favorite definition for DFAs. If your definition allows the transition function to be undefined on some state-symbol pairs $(q, a)$ then your DFA in your comment does the trick. Otherwise, you would need a fifth state (a sink) that is not accepting and catches all missing transitions.
To show that there is no DFA with less than five states accepting $L = \{111\}$, we can check the Myhill-Nerode equivalence classes of $L$ which are

$[\varepsilon]_L = \{\varepsilon\}$,
$[1]_L = \{1\}$,
$[11]_L = \{11\}$,
$[111]_L = \{111\}$,
$[0]_L = \{w \in \{0, 1\}^\ast \mid w \notin \{\varepsilon, 1, 11, 111\}\}$.

(To show that these are indeed the five classes is left as exercise.)
The equivalence classes have a 1:1 correspondence to the unique minimal DFA of the latter definition (with transitions for all state-symbol pairs).


How can image processing neural networks be effectively trained? I was just thinking about image processing neural networks and how to effectively train them in regard of the available dataset.

Let's say you'd want to build a neural network which can distinguish between pictures showing a cat or a dog. I do not have much experience in the field, but I think it would take a pretty big dataset until the network comes to an acceptable success rate.

How could a big enough dataset be acquired? You can't just automatically generate pictures showing a cat or a dog. This means a human would be needed to catagorize thousands and thousands of pictures before the data could be fed to the untrained neural network.

How is it done in practice? Are small datasets (say 100 pictures) ran over and over again? Or is there an completely different, more effective approach?

Yes.  Typically a very large data set is required: tens or hundreds of thousands of labelled images, or perhaps even more.  No, 100 images almost certainly won't be enough.

Just running over the same 100 images won't help.  Doing that won't provide the machine learning algorithm any new information that it doesn't already have.

Where do we get these large data sets from?  Basically, through tedious human effort.  There are many variants of this:

Sometimes it involves people manually, tediously labelling images one by one.
Sometimes one can find an existing data set that someone else has already labelled for you (e.g., ImageNet).
Sometimes you can pay other people to do the labelling for you (e.g., crowdsourcing on Mechnical Turk or something like that).
Sometimes you can find images that are already labelled: for instance, if you do a Google Image search on "cat" it will find many, many images of cats for you.  Well, most of them will be cats; there may be a few other images in there (e.g., a picture of a tiger, a picture of someone named Cat), but the overwhelming majority will be cats.  How does Google Image search know to return these images, when you search for "cat"?  Google might be looking at the keywords on the same page where the photo is found.  So, basically, this is a case where we already have images on the Internet that have already been labelled by whoever made them available, so it's a particularly interesting special case of the above.

That's the basic idea.  There are variations, of course, but I hope it gives you the basic idea.  As you can see, coming up with the training set can be extremely tedious and/or expensive, and the availability of labelled data to use for training a machine learning classifier can be one of the main limiting factors on our ability to build better classifiers.  This is one of the reasons behind the current hype around "big data": labelled data is valuable (because it can be used to train interesting classifiers), so companies that already have lots of (labelled) data have a valuable asset.


Estimate the running time of counting nodes in a binary tree I am asked to write an efficient method that computes the number of nodes in T, and here is what I did:

public int numOfNodes(Node t)
{
    if (t==null)
        return 0;

    return numOfNodes(t.left) + numOfNodes(t.right)+1;
}

Every node needs invokes two recursive calls, so the running time is $O(2^N)$.

Is my estimation of the running time correct? It seems to be too slow.

Hint 1. You say the running time is $O(2^N)$ but what is $N$?  $2^N$ would indeed be bad if $N$ were the number of nodes.

Hint 2. How many times does your code visit each node in the tree?  How much time does it spend on each node?


Are all finite strings over some infinite alphabet countable? Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?

If the alphabet is uncountable then the set of all possible finite strings is uncountable. If you allow infinite length strings then by the diagonalization argument the set is also uncountable.

Assume the alphabet is countable and strings have finite length. Let's assign to each alphabet symbol a natural number, i.e., each symbol corresponds to a natural number and denote a string by a sequence of numbers. For example, if $a$ corresponds to $2$, $b$ to $5$, and $c$ to $11$ then $aabcb$ would be denoted by $2 \ 2 \ 5 \ 11 \ 5$ (I separate them by a single space to avoid confusion). We will prove that the set of all strings is countable.

We group every string of length $n$ whose individual symbols sum to $k$ into the set $C_{n,k}$. For example $000 \in C_{3,0}$, $1192 \in C_{4,13}$, and $1\ 13 \ 3 \ 1 \in C_{4,18}$. For each pair $\langle n,k \rangle$, $C_{n,k}$ is clearly finite and hence is countable. Furthermore, any string $a_1\dots a_n$ does belong to $C_{n,k}$, where $k=a_1+\dots +a_n$ which means every string is included in some set $C_{n,k}$. Since the set of all possible pairs $\langle n,k \rangle$ is countable the union of all possible $C_{n,k}$, i.e, $\bigcup_{\langle n,k \rangle \in N\times N}{C_{n,k}}$ is also countable.


Why is there no one to many Multithreading Model? I am studying various multi-threading models. Here the user threads are mapped to Kernel Threads. They are -

Many to one model.
Many to many model.
one to one model.`

What kept me wondering was why there is no one to many model ?

Actually, there is such a model, though it is typically not thought of as one of the "multi-threading models."

One to many would mean one thread distributed across many processors.  At first that should look silly.  After all, you only have one thread.  What are the other processors to do?  However, superscalar architectures are designed to do roughly this sort of operation.  In superscalar architectures, instructions are decomposed and the CPU identifies the best ways to do these decomposed pieces in parallel, utilizing as much of the hardware as possible.  As a trivial example, they might do a floating point operation and an integer operation at the same time.  Or they might take both branches of a conditional jump at the same time, only settling on one branch later when data becomes available.

This isn't quite a "multi-threading" model, because there's no crisp clean boundary between CPUs.  In superscalar architectures, the hardware utilization is much more fluid.  But it does accomplish something which is very similar in nature: it executes many instructions from one thread in parallel.


Number of spanning trees in undirected simple graph What is the number of spanning trees in an undirected simple graph?

My attempt:

Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.

Then number of spanning trees is $\binom{m}{n-1}$ minus the number of cycles of length $n-1$.

I read on Wikipedia that the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.

According to the formula I stated above, it should be $\binom{n(n-1)/2}{n-1} - \binom{n}{n-1} (n-1)!$.

How do I show that this is equal to $n^{n-2}$ for $K_n$?

You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need not be a cycle of length $n-1$.

In addition, the formula for the number of cycles of length $n-1$ is wrong. The number is $n(n-2)!$ rather than your $n(n-1)!$, and even this formula is only valid for $n \geq 4$ (for smaller $n$ there are no such cycles). However, even after replacing $n(n-1)!$ by $n(n-2)!$, the numbers don't match.


Help coming up with a solution to a combinatorial problem So here is the problem:

Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions.

I know this sounds confusing, but let me give an example:

Say we were trying to find the number of possible combinations to add up to the number 6 using, as stated above, only the numbers 1, 2, & 3 with exactly 2 additions.

The solution is easy:

Since we are trying to add up to 6 using exactly 2 additions with the only three numbers we are allowed to use (1, 2, & 3), we only get: {3 + 3}.

Similarly, If we were trying to find the number of possible combinations to add up to the number 4 with exactly 2 additions we get: {1 + 3} & {2 + 2}.

So, I am asking is there an algorithm out there that I can use to solve this when the numbers get bigger? Is there a clever way to solve this with code? I've been thinking about this for a while and can't seem to solve it.

Thanks!

One way to solve this is using generating functions.  The number of ways to get the number 6 using "2 additions" of 1, 2, or 3 is the coefficient of $x^6$ in $(x+x^2+x^3)^2$.   This generalizes: the number of ways to get the number $n$ using "$k$ additions" of 1, 2, or 3 is the coefficient of $x^n$ in $(x+x^2+x^3)^k$.  I'll let you play with some examples to see why this is so.

Once you know this fact, you can then use polynomial multiplication and repeated squaring to compute the polynomial $(x+x^2+x^3)^k$ and then read off the answer.

See also Calculating the number of multiplications necessary to evaluate a polynomial.


Sorting with a recursive oracle It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant time?

In this case, the runtime of merge sort becomes $O(n)$. The recursive calls are cheap and the runtime is dominated by the merging step.

Does there exist a more efficient algorithm for sorting, using these oracles? My guess is that the answer is negative, i.e. sorting with recursive oracles has runtime complexity $\Theta(n)$.  Is this correct?

NOTE: this is a special case of the following question from cstheory.SE L https://cstheory.stackexchange.com/questions/27094/are-there-problems-for-which-divide-and-conquer-is-provably-useless

If you can sort arrays of size $n-1$ then three recursive applications of this sorting procedure are enough, say prefix, suffix, prefix. You can see that using the zero-one sorting theorem, which states that a sorting algorithm works if it can sort zero-one inputs. I leave the case analysis to you.

This algorithm probably works for much smaller $k$. Moreover, it should be the case that given a sorting oracle for $k=cn$ you can sort in $O_c(1) $ time. One can even guess a formula, $O(c^{-1} \log c^{-1}) $.


Prove using pumping free lemma for context-free languages One of the exercises I tried to make I failed miserably.

The question was as follows:

Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ being the number of a's in the word, same for b's and c's)

For answers I first looked at common words not accepted by context free languages like $a^pb^pc^p$ with $p$ being the pumping length.

However I could not make a proof. Finally I got tired and with made the following construction. I assumed the length dynamic part of the ab's substring would only be one. (then it doesn't matter that much whether it is an 'a' or 'b', I chose the latter). And constructed my word like this:

$\theta b c^{n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$, with $\theta$ being some random string in $\{a,b\}^*$with 'b' being the dynamic substring v and $c^{n_a(\theta)}$ being the dynamic substring y.

With this construction $uv^0xy^0z = \theta c^{n_a(\theta)\cdot n_b(\theta)}$, which is in the language, and $uv^ixy^iz = \theta b^i c^{i\cdot n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$ is also in the language.

In other words, any string where I seperate the ab's from the c's I can prove that even by taking a v of size 1, I will always find u,v,x,y,z substrings that match.

At this point I don't really know how to construct a word any more to disprove the pumping lemma. It's very obvious that there has to be one, but not so obvious what I should look at.

Any help would be greatly appreciated.

i figured it out

$w = (ac^pb)^p $ cannot be split.

in the case that vxy consists of only a's and b's $uv^0xy^0z $ would have less a's and b's but not less c's.

in the case that vxy consists of only c's $uv^0xy^0z $ would have less c's but not less a's and b's.

in the case of a combination it might have an a or a b or both. if it has an a, the number of c's needs to increase by p, but $|vy| \le p$ and we'd need p + 1 terminals. for b the same holds, and for an a and a b it would need even more c's.

so we cannot split this word into 5 substrings  u,v,x,y,z such that $uv^ixy^iz$ is in L


Application of lambda function in Simply Typed Lambda Calculus I'm just getting started with STLC (Simply Typed Lambda Calculus) and I'm trying to understand an evaluation rule I've been given in some lecture notes by my professor. What it says is the following:

(λx. x(λx. x)) (u r) evaluates to (u r) (λx. x)

I don't really get this at all. Can someone point out which step I'm misunderstanding in my evaluation;

(λx. x(λx. x)) (u r) // Start state, not evaluated

(λx. λz. z) (u r) // Replacing occurences of x in first lambda function with the
                  // second lambda function, and then renaming the input variable x
                  // in the second lambda function (this is allowed, right?)

r                 // x gets replaced by u (no occurences) and z gets replaced by r
                  // - resulting in the final result r.

The term

(λx. x(λx. x)) (u r)

parses as

(λx. M) N
where M=(x (λx. x)) and N=(u r)

so, we can perform a $\beta$ step and obtain

M{N/x}
= (x (λx. x)){(u r) / x}
= (x{(u r) / x}   (λx. x){(u r) / x})
= ((u r)   (λx. x){(u r) / x})
= ((u r)   (λx. x))

The last term is also usually written as (u r) (λx. x) or even u r (λx. x).

A tricky part of this step is the substitution (λx. x){(u r) / x} = (λx. x). This derives from the general rule stating that for any terms A,B:

(λx. A){B / x} = (λx. A)

Indeed, the intuition here is that a substitution {B / x} only substitutes the free occurrences of x, and there are no free occurrences of x in (λx. A). This is coherent with the fact that the bound variable x in (λx. A) could be $\alpha$-converted to any fresh variable name y, obtaining (λy. A{y / x}), where x is no longer present at all (free or bound).

By comparison, this step is wrong

(λx. x(λx. x)) (u r) --> (λx. λz. z) (u r)

First, when you apply a $\beta$ step, the $\lambda x$ disappears. So, we can not have both $\lambda x$ and $\lambda z$ in the residual term. If we change the term, modifying the parentheses, we get

((λx. x)(λx. x)) (u r) --> (λz. z) (u r)

but the starting term is completely different from the original one, where
(λx. x(λx. x)) (u r) is read as ((λx. (x(λx. x))) (u r)) instead.


Finding all possible simple directed graphics given a set of nodes Is it possible to find all simple directed graphs given a set of nodes? I was thinking of just finding all permutations of an adjacency list of lists. For example, given nodes A, B I can have the adjacency lists:

A | \
B | \

A | B
B | \

A | \
B | A

A | B
B | A

The constraints are: no self loops, simple graph, directed edges

I can probably code up the way I described above, but I wanted to make sure doing this wasn't hitting some sort of fundamental boundary of graph theory or cs.

I was also thinking about using an adjacency matrix where I can store the matrix in row-major or column-major order in a uni-dimensional array of 0s and 1s - permute the uni-dimensional array (which has to be possible) and rebuild the NxM matrix to represent the graph that way.

Apologies that this is more of a discussion than a question, but any advice would be much appreciated!

Any of those will work, as long as you view the graphs $A\to B$ and $B\to A$ as different graphs. If you view them as being the same graph, then things are much more complex as you have to either do isomorphism testing or somehow enumerate in a way that doesn't produce isomorphic graphs more than once.

The fundamental barrier is that, in an $n$-vertex digraph has $n(n-1)$ possible edges, each of which may be present or not, so there are $2^{n(n-1)}$ possible digraphs on $n$ vertices. Your program must output all of these which is going to be infeasible for all but small graphs.


Runtime bounds on algorithms of NP complete problems assuming P≠NP Assume $P\neq NP$.

What can we say about the runtime bounds of all NP-complete problems?

i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal algorithm for any NP-complete problem runs in time of at least $\omega(L(n))$ and at most $o(U(n))$ on a input of length $n$?

Obviously, $\forall c:L(n)=\Omega(n^c)$.
Also, $U(n) = O(2^{n^{\omega(1)}})$.

Without assuming $QP\neq NP$, $ETH$, or any other assumption which is not implied by $P\neq NP$, can we give any better bounds on $L,U$?

EDIT:

Note that at least one of $L,U$ has to be far from the bounds I gave here, since being NPC problems, these problems has poly time reduction between each other, meaning that if some NPC problem has an optimal algorithm of time $f(n)$, then all problems has an algorithm (optimal or not) of runtime $O(f(n^{O(1)}))$.

My interpretation of the question is that is asks about the possibilities in relativized worlds. Suppose that in some relativized world, $P \neq NP$. Can we deduce anything non-trivial about the time complexity of NP-complete problems? The Baker–Gill–Solovay argument shows that we can "force" some NP problem to require exponential time, so the upper bound given in the question is essentially optimal.

Regarding the lower bound, we sketch below a proof that relative to some oracle, $NP = \mathrm{TIME}(2^{O(\log^2 n)})$. Assuming that the sketched proof is correct, we can also apply it to functions smaller than $2^{O(\log^2 n)}$, and this shows that the lower bound given in the question is also essentially tight.

Proof sketch. We construct two oracles $O_1,O_2$: the first behaves like a $\mathrm{TIME}(2^{O(\log^2 n)})$-complete problem, and the second implements the Baker–Gill–Solovay diagonalization. It is straightforward to pack both oracles into a single oracle.

The oracle $O_1$ consists of all pairs $\langle M, x \rangle$ such that $M$ is an oracle Turing machine that accepts $x$ in running time $2^{2^{\sqrt{\log |x|}}}$ when given access to the oracles $O_1,O_2$ restricted to inputs of length at most $2^{\sqrt{\log |x|}}$. (This is not a circular definition.)

The oracle $O_2$ is defined in the same way that the oracle is defined in Baker–Gill–Solovay: for each clocked oracle Turing machine $M$ running in time $T = 2^{o(\log^2 n)}$, we find some input length $n$ which is "untouched", run $M$ on $1^n$ for $T$ steps, and for each query to $O_2$ of size $n$, we mark that this input is not in $O_2$ (for other queries we also mark that the input is not there, unless we had already decided that it is in $O_2$). Queries to $O_1$ are handled similarly (as implicit queries to $O_1,O_2$ of smaller size, handled recursively); notice that such queries never mention strings of length $n$ in $O_2$, since $2^{\sqrt{\log T}} < n$. If the machine accepts, we mark all other strings of length $n$ in $O_2$ as missing, otherwise we pick some string of length $n$ and put it in $O_2$.

The class $P^{O_1,O_2}$ consists of all programs running in time $2^{2^{O(\sqrt{\log n})}}$, making queries to $O_1,O_2$ of size $2^{O(\sqrt{\log n})}$. The class $NP^{O_1,O_2}$ is of the form $x \mapsto \exists |y|<n^C \varphi(x,y)$, where $\varphi \in P^{O_1,O_2}$, and so it is contained in the class of all programs running in time $2^{n^C}$ and making oracle queries of size
$2^{O(\sqrt{\log n})}$. The latter is contained in $\mathrm{TIME}(2^{\log^2 n^C})^{O_1,O_2}$, since we can use $O_1$ to decide it. This shows that $NP^{O_1,O_2} \subseteq \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.

For the other direction, let $L$ be the language which consists of $1^n$ for each $n$ such that $O_2$ contains some string of length $n$. By construction of $O_2$, $L \notin \mathrm{TIME}(2^{o(\log^2 n)})^{O_1,O_2}$, while clearly $L \in NP^{O_1,O_2}$. This shows that $NP^{O_1,O_2} = \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.


Understand the DFA: accepting or not accepting "aa" or "bb" I want to discuss the strings accepted by couple of DFAs:

DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is not I want.

DFA in Figure 2 has one final state q0. Its good because it does not accept "aa" or "bb" but the problem is that it does not accept any string so its useless.

DFA in figure 3 accept a, aba. It looks like that it can accept any number of "ab" but does it accept "aa" or "aaa"? Can the start state generate any number of 'a's to be accepted by the final state? I am not sure somebody please guide me.
Somebody please guide me.
Zulfi.

It is not clear if you actually want to construct an automaton for some language, however I can provide some help with understanding the given ones.
The first automaton is a bit complicated.
The language it recognizes should be, in regular expression form,
$$((ab)^\ast (ba)^\ast)^\ast (a + b + \varepsilon)$$
where $\varepsilon$ denotes the empty word.
The second one, as you noted, has no edges returning to the only final state which also happens to be the initial state.
Hence the language it recognizes is $\{\varepsilon\}$, but it surely is a complicated automaton for doing this.
The third automaton recognizes the language $a(ba)^\ast$.
It does not accept any words containing substrings $aa$ or such as starting from any state, taking 2 consecutive $a$-transitions will land you in that bottom sink state from which the accepting state cannot be reached.
The fourth automaton is actually not a DFA but a NFA (but that makes no big difference).
It recognizes the language $a(baa^\ast)^\ast$, which is different from the expression you gave as yours is missing the possibility for taking the loop from the accepting state through the initial state via $b$ and back to the accepting state via $a$.
In particular, this loop shows that if the automaton accepts $w$, then it also accepts $w(ba)^\ast$.
In general, analyzing the language recognized by some DFA boils down to finding the paths from the initial state to a final state and then accounting for loops along the way, which sometimes can be a bit confusing, but try to do this for the third and fourth automata yourself. I am sure that you will be able to understand them that way in no time :)


Learning Specific Topics In Machine Learning I am a beginner in machine learning and I already have a good linear algebra/calculus background.

I am interested in being able to eventually understand and implement convolutional neural networks, feature-based classifiers, and boosting algorithms. Where should I start, and what steps should I take to reach my goal?

Thanks in advance.

First I'll say, because you didn't mention it, that you also need a strong probability and statistics background.

A good place to start with CNNs is (in my opinion) the highly praised Stanford course:
https://www.youtube.com/playlist?list=PL3FW7Lu3i5JvHM8ljYj-zLfQRF3EO8sYv

If you are looking for more practical stuff (and on more than just CNNs), there are many guides for different machine learning models in Kaggle, where you can also join challenges which you can learn a lot from.
https://www.kaggle.com/

If you are interested in theory, this book might help - but might also be difficult without a strong statistical background:
http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/index.html
(the book is free to download from there)


If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular? The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$.  Suppose that L is a regular language.  Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?  Explain.

Intuitively, I suspect that $L_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular.  However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L_1$.

It will be regular.

   Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).


Betweenness Centrality measurement in Undirected Graphs I'm working with graphs of a very large size (> 60k vertices), and want to speed up B.C. measurements. It is defined here: http://en.wikipedia.org/wiki/Betweenness_centrality The algorithm that I am using to compute B.C. is Brandes' algorithm: http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

For undirected graphs, would running the Betweenness centrality algorithm on each of its connected components (and then combine the results) give the exact same answer as computing on the whole graph at once? I would think so (but don't have a proof) because different connected components are not related.

Betweenness centrality is defined on connected graphs. Suppose a graph $G$ with two connected components, $G_1$ and $G_2$, and consider a node $v \in G_1$, then the betweenness centrality for $v$ is

$$C_B(u)=\sum_{s,t \in G}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=$$

$$\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{0}{0}}$$

But if you want to treat each connected component as a single graph, you can also calculate the betweenness centrality independently for each component.


Why should an average programmer learn automata theory? Good programming relies heavily on choosing an efficient algorithm for the task at hand and yet an average programmer hardly uses 50 pages worth of algorithms from the Cormen book in his/her career.

Recently I started reading some CS books, long after completing my bachelors degree. One of the books is the Theory of Computation by Micheal Sipser. Although I love the content and still am in the beginning chapters, I cannot imagine where I would use the information provided in this book in my job.

What is the use of Automata Theory in the industry?

Automata theory is rarely used by practicing programmers today.  It is in principle useful for building compilers and parsers (though most developers don't need to do that today, and often use tools to help them).  Some of the concepts can be useful for building state-machine based systems, which are widespread (including, e.g., embedded systems), though it's not clear you need to know all the ideas from automata theory to be successful at that.  Also, many people study theory even if there is not a direct practical application.


Finding three factors of a number with minimal sum Suppose that we have a number $x \in \mathbb{Z}^+$.

I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum.

Is this problem a variant of subset sum? Am I stuck with an exponential time algorithm?

Examples

$32 = 4 \times 4 \times 2$
$36 = 4 \times 3 \times 3$
$11 =  11 \times 1 \times 1$
$6 = 2 \times 3 \times 1$

The problem does not require exponential time. It can be solved in subexponential, but superpolynomial time.

The first step is to find the prime factorization of $x$, which can be done with the general number field sieve.

Next, enumerate all possible values of $a,b$ and for each tuple $(a,b)$ compute $c$ to find the triple with the minumum sum. A number $x$ has at most $\exp(O(\log x / \log \log x))$ divisors, so there are also at most $\exp(O(\log x / \log \log x))$ such tuples.


Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy? When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a  reduction that fulfills the following property:
If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is also $\Sigma_i^P$ or $\Pi_i^P$.

I can see how Karp-reductions fulfill this requirement for the complexity class $P$. How could one proof that Karp-reduction fulfill this requirement for all other complexity classes in the polynomial hierachy?

Suppose that $f$ is the polynomial reduction between $L'$ and $L$, i.e. $x \in L' \Leftrightarrow f(x) \in L$. If $L \in \Sigma_k^p$ then $y\in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(y, z_1, \ldots z_k) = 1$. Then $$x\in L \Leftrightarrow f(x) \in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(f(x), z_1, \ldots z_k) = 1 \Leftrightarrow \exists z_1 \forall z_2 \ldots P(x, z_1, \ldots z_k) = 1$$  $P$ first computes $f$, then applies $M$, so it's polynomial.


Are all hypothetical machine models for calculating runing time of an alogrithm same? Im learning about time complexity analysis, and cant seem to figure out why do we consider a hypothetical machine that takes 1 unit of time for arithemitic and logical instructions and 1 unit of time to for assignment and return statements.

Q) why does it have to be 1 unit of time?

Q) Also is it upto to the analyzer to define such parameters for hypotheical machine models or is there some sort "standard/convention" used instead ?

In RAM model, which is very close to our computers, standard arithmetic operations and assignments take same time disregarding values as far as they fit to computer word. This yields good estimate for runtime and apgorithm behaviour. When some operation takes $c$ time, but constant you may provide it in assymptotic analysis or omit it, becase such analysis takes into consideration length of the input as it grows.

For fine grained computation and small inputs it makes sense to check whether $\mathcal O(5n^2)$ is better than $\mathcal O(100n)$. In assymptotic case constants are dominated by input length, that is why there is no difference between 3 and 20000, so using 1 as time unit makes calculations easier.

It is up to analyzer, how fine grained is analysis, but also which model is chosen, differences here are huge. Between RAM model and Turing Machine model difference is polynomial. Between RAM and Real RAM or BSS machine are vast, instead of word-sized integers arbitrary real or respectively rational numbers could be stored with operations on them taking single time unit. This creates enormous computation gap. So the choice of model is crucial and models are nowhere near similar.

Convention is to use smallest plausible model.
If you sort integers in transdichotomous model, the size of numbers doesn't matter, in RAM it does, it takes unit cost if they fit word size or longer if they don't.


Mutual information and moment generating functions I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough knowledge to understand what it means. Then, I did some research but I still have some confusion. I am wondering if someone who has more knowledge about this can clarify things for me. Here are my questions:

Mutual information is usually calculated by bin functions to estimate the probability of two random variables which can be a case of two vectors $X$ and $Y$. Is the moment generating function another way to estimate probability?
If moment generating functions can present the probability of $X$ and $Y$, how do we calculate it?
Does a MI have a moment generating function?
If MI has a moment generating function, how can we present a MI of $X$ and $Y$ by its moment functions?

The moment generating function $M_X$ is a property of a random variable $X$. It's defined by the expected value of $e^{tX}$ (where $t$ is the argument).

Since the exponential function $e^x = \sum_0^\infty \frac{x^n}{n!}$ contains all natural powers of its argument as a summand, the expected value of a sum is the sum of the expected values ($\mathbb{E}(\sum_i X_i)=\sum_i\mathbb{E}(X_i)$) and the expected value of a natural power of $X$ ($\mathbb{E}(X^n)$) is called it's $n$-th moment, the $n$-th moment is present in the $n$-th summand:

$$M_X(t)=\mathbb{E}(e^{tX})=\sum_{i=0}^\infty \frac{t^i\mathbb{E}(X^i)}{i!} \quad .$$

If you now consider the $k$-times derivative of $M_X$:

$$M_X^{(k)}(t)=\mathbb{E}(e^{tX})=\sum_{i=0}^\infty \frac{\mathbb{E}(X^{i+k})}{i!} \quad ,$$

and use $0$ as an argument, you get
$$M_X^{(k)}(0)=\mathbb{E}(X^k)\quad,$$

so the $k$-th moment was generated.

Now look at the mutual information:

$$I(X,Y) = \sum_{(x,y)}P(X=x,Y=y)\log\left(\frac{P(X=x,Y=y)}{P(X=x)\cdot P(Y=y)}\right) = \mathbb{E}(\mathrm{PMI}(X,Y)), $$

which is the expected value of the pointwise mutual information (it's likely that they actually deal with the continuous case where $I$ and $\mathrm{PMI}$ are defined using integrals and densities, respectively). So mutual information does not have a moment (or moment generating function), but it is the first moment of a random variable, so:

$$I(X,Y) = M_{\mathrm{PMI}(X,Y)}'(0)\quad.$$


What are algorithms for computing contours from given edges? Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges!

I am looking at least for the name of the algorithm to further look how this problem is solved.

Here is the example (please don't mind the grid) -- input:

and output in pink (the pink is the real output, the rest is left for comparison -- it should be removed by algorithm I am looking for):

As you can see I have a lot of redundant edges, too long, internal ones.
Note also that this is not the convex hull problem; my shape is not convex.

The question: what are known algorithms for solving this problem?

This problem is not surprisingly called Concave Hull
You might be also interested in alpha shapes
CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS by Adriano Moreira and Maribel Yasmina Santos


Can regular languages be Turing complete? I was reading about Iota and Jot and found this section confusing:

  Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-branching. As a result, Iota is strictly context-free, but Jot is a regular language.

My understanding is that both Iota and Jot are Turing complete. But apparently, one is context-free, and the other is regular! Surely regular languages can't be Turing complete?

In short, the answer is yes.

But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing):

A set of strings. "Context-free language" means "a set of strings which can be recognized using a context-free grammar".
A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which the Turing machine can be specified".

Note that you can talk about "the C++ language" from two completely unrelated viewpoints, using the two unrelated meanings of the word "language":

C++ as a set of strings which are legal according to the C++ grammar
C++ as a way of specifying programs.

The traits of "the C++ language" from these two viewpoints are unrelated.

More examples to help you separate these concepts:

The expression "[a-z]+@[a-z].[a-z]" describes a set of strings recognizable by finite automata, i.e. a regular language. However, it's just that - a set of strings: is not a way of specifying programs (unless you ascribe a way to interpret each such string as a program), so it does not make sense to talk about whether or not it is Turing-complete.
The language of flowcharts is a way of specifying programs; depending on the particular flavor of flowcharts, it may or may not be Turing-complete. However, flowcharts aren't strings, so it makes absolutely no sense to talk about flowcharts in the sense "language as a set of strings".


How is the space complexity O(LogN) for rangeSumBST problem Recursive
class Solution {

    int ans;
    public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R)
                ans += node.val;
            if (L < node.val)
                dfs(node.left, L, R);
            if (node.val < R)
                dfs(node.right, L, R);
        }
    }
}

Iterative
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }
}

Source: https://leetcode.com/problems/range-sum-of-bst/solution/
Suppose L is Integer.MIN_VALUE and R is Integer.MAX_VALUE, then wouldn't it traverse through all the nodes. Since we need to check the worst case, shouldn't it be O(N) instead of O(logN)

The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $O(N)$ but the space complexity is $O(H)$ where H is the height of the tree.
Even following the link you provided, they state this:


Suboptimal Solution for a combinatorial problem I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of dimension $n\times s$. At the end, we are going to choose one matrix $X$ that generates the least cost $f(X)$ within all possible $n\choose s$ submatrices of B. And so, this is a combinatorial problem that becomes complicated mostly when $n$ is big.

So my question is can we find a suboptimal solution without going through all possible $n\choose s$ submatrices and what kind of algorithm that I can apply to find such solution.

My second question is can we apply a feature selection algorithm to find a suboptimal solution for a combinatorial problem.

If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once.

In a lot of practical situations I would expect the frobenius minimizer will be exactly the 2-norm minimizer, and is a common choice of norm to minimize in matrix completion problems.

edit: In a recent edit the original poster made it clear that what they are looking for is the frobenius norm, even though the notation $||\cdot||_2$ is traditionally used for the induced 2-norm. (the edit makes the problem much less interesting). Since the rest of this post is about justifying the Frobenius norm as an approximation to the induced 2-norm, it's basically irrelevant to the edited version of the question.

A little bit more on why the Frobenius norm could be a good approximation.

Since all norms are equivalent on a finite dimensional space, immediately we have
$$c(s)||\hat{X} - X||_{Fro} \le ||\hat{X} - X||_2 \le C(s) ||\hat{X} - X||_{Fro},$$

so the Frobenius minimizer will be within a constant of the $2$-norm minimizer when the dimensions of the matrix are fixed. The issue, as usual, is that the constants $c(s), C(s)$ depend on the number of entries in the matrix and go to zero/blow up as $s$ becomes larger and larger.

However, there is a situation where the constants do not blow up and that is, roughly, when

you are dealing with a sequence of matrices $\hat{X}_s, B_s$ that are stably larger and larger approximations of some extremely high dimensional (or infinite dimensional) true matrices (operators) $\hat{X},B$, and
the very large or infinite "true" problem has a solution in the sense that there exists $X_{optimal}$ such that $\hat{X} - X_{optimal}$ is compact.

A little bit more on these conditions: 1) is the case if, for example

your matrices are generated by incomplete sampling of data (eg., measurements from a scientific experiment where you could get better results by taking more data, or shopping data from a small subset of amazon's customers that are supposed to represent the customerbase as a whole), and you could get similar but bigger problems from the same distribution just taking more samples, or
the size $s$ of your matrices comes from the level of discretication of a continuum problem like a partial differential equation.

Furthermore, 2) must always be the case if you reasonably expect a solution, since if there is no approximation that makes $\hat{X} - X$ compact, then by definition it has no finite rank approximation, so you can never come up with a good result to the real problem by solving limited data versions with $\hat{X}_s, B_s$ nomatter how big $s$ is.

Now, assuming that the compactness condition holds, the singular values $\sigma_1, \sigma_2, \dots$ of $\hat{X} - X_{optimal}$ are summable (and thus square summable), and so we have the explicit equivalence,
$$||\hat{X} - X_{opt}||^2_{Fro} = \sum_{i=1}^{\infty} \sigma_i^2 = \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)\sigma_1^2 =  \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X} - X_{opt}||_2^2.$$

These constants are independent of $s$, and moreover the more compact the error, the faster the singular values decay, so the closer to 1 the equivalence constant is. Thus assuming that the matrices $\hat{X}_s, B_s$ come from stable sampling schemes or stable discretizations of $\hat{X},B$, we have the equivalence
$$||\hat{X}_s - X_{s,opt}||^2_{Fro} \le \gamma_1\left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X}_s - X_{s,opt}||_2^2 \le \gamma_2  ||\hat{X}_s - X_{s,opt}||^2_{Fro},$$
where $\gamma_1$, $\gamma_2$ come from the stability and coercivity constants of the sampling/discretization process.

So, since the assumptions above apply to a wide range of circumstances, replacing $2$-norm minimization with Frobenius norm minimization often makes sense in practical contexts.


In Big-O notation, what does it mean for T(n) to be upper bounded by something I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? from references, but I still do not understand (even graphically), what does it mean when we say:

  T(n) = O(f(n)) if and only if there are constants c and g such that:
  T(n) <= c*f(n), where n>=g

Specifically, we say that T(n) is upper bounded by c*f(n). What does that actually mean and why does it matter? Does it have to do with eliminating constant factors and low-ordered terms?

Sorry if question is kind of confusing, and thanks for the help!

Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$".

Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate choice of $C$. If $T(n) = n^3 + 2019n^2 + 99999n + 10^{10}$, for example, that will still eventually be dominated by $Cn^3$, as long as $C > 1$ and $n$ is large enough—the $n^3$ term in that expression will eventually outweigh everything else. So we say that $T(n) \in O(n^3)$. (Some people use an equals sign instead; the meaning is the same.)

The "sufficiently large $n$", by the way, is why it's called "asymptotic" complexity: we only care about what happens as $n$ goes toward infinity, not what happens for "small" values.


Question regarding languages and P According to this Wikipedia article on unary language every unary language has a binary variant. My question is that given a unary language is there an equivalent binary language in P that is P-Complete.

As said Yuval Filmus in the comment, some unary languages are undecidable, so they don't even have an equivalent binary language in P.


Data Hazard in Pipelining To be precise I am here for RAW hazard.
Consider a 5 stage pipeline .

In case of $I_4-I_1$ dependency , I am not sure if it is an $RAW$  hazard as $I_4$ does not depends on value of
$R_1$ that $I_1$ gives. and even if it fetches it ,it still be a wrong value as per the instruction sequence as $I_2$ is modifying it.

So , is $I_4-I_1$ a $RAW$ hazard ?
and if yes, then please give suitable explanation why so and related information about $RAW$  hazard as it happened even if $I_2$ modified the Value in between .

We can't say without knowing number of stages used in pipeline. If stages are not more than $3$, it's not RAW.

First of all, this statement of mine is incorrect if we talk about data dependency. Dependency is a matter of instructions itself, architecture doesn't come into play directly. Architecture can only ensure that stall not to happens even with dependencies but it doesn't change the fact of dependencies among instructions. But in a pipeline if any data dependency results into stall then it is called data hazard.

  and even if it fetches it ,it still be a wrong value as per the instruction sequence as I2 is modifying it.

Again, as I have explained above, the modification is irrelevant here if we are just talking about dependencies. To check data hazard What we need to do is to see whether dependencies result into stall in pipelining or not. If yes, it results, then it is data hazard.


LL(k) language and not LL(k) grammar I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?

Grammar:

S -> a b X c d | a X f

X -> b X c | ε

You can prove by contradiction, assuming there is a value of $k$ that allows you to anticipate the sequence of derivations that is guaranteed to produce a unique tree for any input string, given some unambiguous grammar that accepts the language.

You then prove that there is a string for which a lookahead  $>k$ will be needed, no matter how the grammar is constructed, because the derivation sequence is affected early in the process. A strategy similar to the pumping lemma for context-free languages comes to mind.

Incidentally, your grammar is equivalent to the following LL(1) grammar:

$\begin{align} S &\to aT \\
               T &\to f \mid bXcV \\
               X &\to bXc \mid \epsilon \\
               V &\to d \mid f \end{align}$

Perhaps a more interesting example would be

$\begin{align} S &\to T \mid U \mid V \\
               T &\to aTb \mid \epsilon \\
               U &\to aUc \mid \epsilon \\
               V &\to dVc \mid \epsilon \end{align}$

whose language is both not $LL(k)$ and not $RR(k)$.


Network throughput with random delay selected from uniform distribution Background:

I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the more that are received, the better. I previously had nodes continuously synchronise clocks in order to adhere to a TDMA schedule, but this added significant algorithmic complexity to an application where 100% successful transmissions is not required. I am therefore trying a new approach based on random transmissions.

Problem Setup:

Let there be $N$ nodes, and let each node broadcast a status message of duration $A$ at least $d$ microseconds after its previous transmission, and no more than $D$ microseconds later. The exact delay for each packet is selected randomly and uniformly from the range $[d, D]$.

If packet $k$ is transmitted from a node at time $t_k$, then the transmission time of the node's next packet $k+1$ is given by $t_{k+1} = t_k + \mathcal{U}(d,D)$.

The minimum delay $d$ is a constant given by the time required for the IoT device to acquire a new measurement and schedule the next packet.

The maximum delay $D$ is a variable which should be tuned to maximise network throughput (akin to ALOHA).

Problem:

I'm trying to derive an expression for the network throughput.

I can't find any material on ALOHA with periodic transmissions, and can only find material where the probability of transmitting is poisson, and where each transmission is independent of the last.

Thank you for your help in pointing me in the right direction.

Let $f(t)$ be the probability distribution function for the probability that the current cycle (from the moment when node 1 broadcast the last message to the moment when node 1 will start broadcasting the next message) has duration $A+t$.

For $d\leq t\leq D$, $f(t)$ must be proportional to $A+t$. We can use the fact that $\int_d^D f(t)\mathrm{d}t=1$ to deduce that $f(t)=\frac{A+t}{\lambda}$ for $d\leq t\leq D$, where $\lambda=D(\frac{D}2+A)-d(\frac{d}2+A)$. $f(t)=0$ if $t>D$ or if $t<d$.

Denote by $P_s$ the probability that node 1 is not broadcasting at any time during a given time period of duration $A$. It can be shown, by considering the conditional probability that node 1 does not broadcast during the given time period given that node 1 is in a cycle of length $t$ at the start of the time period, that $P_s=\int_A^D f(t) \frac{t-A}{t+A} \mathrm{d}t=\frac{1}{\lambda}\left(\frac{\max(A,D)^2}2-A\max(A,D)-\frac{\max(A,d)^2}2+A\max(A,d)\right)$.

The probability that a given message is transmitted successfully is $P_s^{N-1}$. The throughput is then $\frac{NP_s^{N-1}}{A+\frac{D+d}2}$, since the average length of a cycle is $A+\frac{D+d}2$.


Number of substrings with exactly k distinct characters Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return 0.
Input: s = "pqpqs", k = 2
Output: 7
Explanation: ["pq", "pqp", "pqpq", "qp", "qpq", "pq", "qs"]

I have this solution for it:
   def subarraysWithKDistinct(self, A, K):
        return self.atMostK(A, K) - self.atMostK(A, K - 1)

    def atMostK(self, A, K):
        count = collections.Counter()
        res = i = 0
        for j in range(len(A)):
            if count[A[j]] == 0: K -= 1
            count[A[j]] += 1
            while K < 0:
                count[A[i]] -= 1
                if count[A[i]] == 0: K += 1
                i += 1
            res += j - i + 1
        return res

What I don't understand is how does atMost(k) - atMost(k-1) gives the total number of substrings that have exactly k distinct characters? I tried different examples and it works. I understand how the code works but not how the final answer is computed after two-passes.
Can someone give me generic mathematical proof or intuition behind it?

atMost(A, K) computes the number of substrings with at most K distinct characters.
A substring with at most K distinct characters has either exactly K, or at most K-1, distinct characters. So, atMost(A, K) - atMost(A, K-1) is the number of substrings with exactly K distinct characters.


Reusing variable in converting grammar to Chomsky Normal Form I'm not sure if reusing variable is allowed in CNF.

For example, I have this grammar not in CNF. So I have to convert it to CNF.

1. S->abAB|abB|abA|ab
2. A->bAa|ba
3. B->BAa|bAa|ba|Ba|Aa|a

For conversion, I'm using a convention where new variables and terminals are in the form

(V1,V2,V3,...,Vk) for k > 0
Ti where i are terminals (a,b,c,...,z)

Introduce new terminals for each terminal in the grammar
S->(Ta)(Tb)AB|(Ta)(Tb)B|(Ta)(Tb)A|(Ta)(Tb)
A->(Tb)A(Ta)|(Tb)(Ta)
B->BA(Ta)|(Tb)A(Ta)|(Tb)(Ta)|B(Ta)|A(Ta)|a
Ta->a
Tb->b

For the purpose of my question, I'm only focusing only on B productions due to the repetition of A(Ta).

...
B->BV1|(Tb)V2|(Tb)(Ta)|B(Ta)|A(Ta)|a
V1->A(Ta)
V2->A(Ta)
...

See V1 and V2, they have the same right-hand side that is A(Ta).

"Chomsky normal form" is something a grammar is, rather than the specific procedure used to make it. So nothing prevents you from reusing a symbol like that; the grammar will still be CNF if you do.


Proving that a (tree) language is not Buchi recognizable I'm reviewing some notes about tree automata and I'm trying to conclude a proof that the professor left incomplete. The statement is:

  Let $A = \{a,b\}$ and $T = \{t \in T_A^{\omega} \mid \text{every path in $t$ contains a finite number of $a$}\}$.
  Prove that $T$ isn't Buchi recognizable.

Now we can define the following subsets of trees $t_n \subseteq T$ where $t \in t_n$ has one $a$ at positions: $\epsilon, 1^{m_1}0, 1^{m_1}01^{m_2}0, \ldots, 1^{m_1}01^{m_2}0\ldots1^{m_n}0$ with $m_i > 0$.

Now assume that $\mathcal{A} = (Q, A, \Delta, q_0, F)$ is the Buchi automaton that recognizes $T$ with $|Q| = n+1$ and $q_0$ appears only at the root of its computations. Let $t \in t_n$ and $r$ be a successful run of $\mathcal{A}$ on $t$.

Claim: $\color{red}{\text{There exists $u \leq v < w$ such that $r(u) = r(w) = s \in F$ and $t(v) = a$.}}$

Obviously if we show that the claim is true we can prove the initial statement: take the subtree $t_v$ and obtain a $t' \in t_{n+1}$ by replacing
the subtree $t_w$ with $t_v$. We have that there exist a run $r'$ which is identical to $r$ up to the position for $w$ and will follow the same sequence of states at $w$ as it did at $v$, and hence is accepting. Repeat the process and you obtain a branch with infinite $a$s that is accepted by $\mathcal{A}$. (This is just the rough idea, it requires a bit of formalism, but it's not the point of the question.)

My question is: how do I prove the claim?

I can show that there exist a $t' \in t_{2n}$ with that property (which is actually good enough for the rest of the proof), but not that given a fixed $t_n$ the statement holds for any successful run.

My idea is simply: given that $r$ is accepting there must exist a $s \in F$ repeated infinite times in a path passing through $1^{m_1}01^{m_2}0\ldots1^{m_n}0$. Then take a tree $t'' \in t_{n+1}$ that is
identical to $t_n$ up to the position $x$ where $r(x) = s$ on that path, and add an $a$ below such position. Now this tree is still accepted by the automaton and there exist an accepting run $r'$ identical to $r$ up to the position $x$,
but then $r'$ cannot reuse $s$ for accepting that same path (otherwise we have found the three states of the claim) and so it must use a different state $s'$. Repeat for all final states and you have that $t_{2n}$ must have a run with that property.

Is there any way to apply this kind of reasoning to $t_{n-1}$, $t_{n-2}$ etc to obtain the result for $t_n$? It looks like at most I may be able to prove that there exist a $t'' \in t_n$ with a run with that property, while the claim is stronger. Or am I going in the wrong direction?

The idea is to play with the $m_i$'s, as follows.

Consider a tree $t_1$, which has $a$ in $\epsilon$, and nowhere else. Look at the path $1^\omega$ — an accepting run on it has infinitely many accepting states. Wait until such an accepting state was reached, and only then put $a$ at $1^{m_1}0$, where $m_1$ is large enough.

Now look at the path $1^{m_1}01^\omega$, again, it has an accepting state eventually, denote the length up to it by $m_2$, put an $a$ at $1^{m_1}01^{m_2}0$ and look at $1^{m_1}01^{m_2}01^\omega$. By now you have almost what you wanted - two accepting states with an $a$ between them (informally speaking). But you are not yet guaranteed that both accepting states are equal. To enforce the latter, we repeat the process for $n$ times, thus exhausting the number of accepting states, and by the pigeonhole principle, two accepting states must be equal.


Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$ In any introductory course on the theory of computing, one encounters the language
$$L_k = \{a_1^n \cdots a_k^n \mid n \geq 0\}$$
as a canonical (or at least pedagogical) counterexample for a language which is not regular ($k=2$) or context-free ($k=3$). The next jump is usually to the turing machine, where $L_k$ is in the class for all $k$.

Is there a (sensible, e.g. defined in some terms of generating grammar or recognizing automaton) hierarchy of classes of languages $\mathsf{COMP}_k$ so that $L_j \in \mathsf{COMP}_k$ for $j < k$ and $L_j \not\in \mathsf{COMP}_k$ for $j \geq k$? Ideally it would also hold generally that $\mathsf{COMP}_k \subset \mathsf{COMP}_{k+1}$. Or, perhaps, is this distinction of being able to recognize $L_k$ not important/fundamental once $k \geq 3$ (in whatever sense you want to interpret that question)?

One example would be the hierarchy defined by blind counter automata.
A blind $k$-counter automaton has access to $k$ counters for which

there is an increment and a decrement instruction (and no zero-test),
a run is accepting if in the end, all counters are zero, and
during a run, the counters are allowed to be negative.

Let $\mathcal{B}_k$ denote the class of languages accepted by blind
$k$-counter automata. Then $L_{k}\in \mathcal{B}_{k-1}$: while you
read $a_1$'s, you increment all $k-1$ counters simultaneously; then each of the remaining $k-1$ letter blocks decreases one of the counters.

On the other hand, one has $L_{k}\notin\mathcal{B}_{k-2}$.
This can be shown, for example, using Theorem 6.4 in Fernau and
Stiebe's paper on valence
automata/grammars. This pumping lemma allows, in a blind $\ell$-counter automaton, the simultaneous repetition of $\le\ell+1$
non-empty factors. Hence, if we had $L_k\in\mathcal{B}_{k-2}$, we could repeat $\le k-1$ factors, which can span at most $k-1$ distinct letters
in a word $a_1^*\cdots a_k^*$. Hence, we could pump up powers of some $a_i$'s
without touching at least one letter $a_j$, which clearly leads out of
the language. In Fernau and Stiebe's paper, the class $\mathcal{B}_k$ is
denoted $\mathscr{L}(\mathrm{Val},\mathrm{Reg},\mathbb{Z}^k)$.


How huffman tree uses MinHeap? As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node closer to root have less length code than nodes below that level i.e., level 1 codes will have shorter codes than level 5; which means level 1 nodes are more frequently occurring than level 5 nodes. Also the numeric value after addition is also greater than that nodes at high level. I am confused, isn't that definition of max heap but they are using min heap. Please explain why they are using Min heap and not Max heap (considering nodes at lower level are more frequent than at higher level)

Building a huffman tree is bottom up.

You start with the all the leave nodes with their frequency.
Then you select and remove the 2 nodes with the smallest frequencies
create and insert a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes
if set has 2 or more nodes repeat from step 2

Selecting the 2 nodes with the least frequencies requires a min heap.


Neural Network Shape / Structure I am attempting to learn neural networks using the Keras libary on the MNIST hand written digit dataset, using dense layers only. I am trying to figure out what the best shape for the network should be but I can't seem to find any literature or discussion on the subject.

By shape, I mean should the hidden layers have more nodes as I go deeper, less nodes, or the same? I've taken to calling them square, pyramid, and reverse-pyramid because I couldn't find a better name. See the end of this post for clarification on shape

I've tried all 3 and the reverse pyramid is giving me the best at 80% accuracy but I can't imagine why. I feel like I would just be losing data and introducing noise by expanding the number of neurons as I go deeper.

Is there any literature or discussions about this subject? Perhaps, I'm not using the right keywords to look, I just don't know the correct terminology. I've tried neural network shape, structure, hidden layer layout, etc. with very little luck.

Thanks in advance.

Square - Hidden layers stay same size until the end

Pyramid - less neurons at each additonial hidden layer (pretend they are all hidden layers)

Reverse Pyramid - more neurons at each additiona hidden layer

Are you using the Training set for testing ? What is your train test split ?

With Neural Nets, it's always the pyramid shape that works. This is because as you go deeper, data about the input is condensed and we get a proper representation of the input for outputting the required class or regression value.

The only reason reverse pyramid nets will work well is overfitting, which accommodates noise and does not generalize well.

http://www.deeplearningbook.org/contents/mlp.html

Try the Bible of Deep Learning for more details.


Are some Integer programming formulations completely useless for relaxation? I was tasked with constructing an integer programming formulation for an NP-hard problem, and then with specifying its LP relaxation and the resulting approximation factor.

The problem is that, while my integer programming formulation is correct and clever (I like to think), it seams that its relaxation is completely useless. In fact, the LP relaxation seams like it would always lead to the worst possible solution to the original problem.

Is this possible? Is there some known way of deriving a proof that an LP relaxation of an IP problem can only be so good, some way of telling you when to quit looking?

Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding mechanism cannot guarantee an approximation ratio better than $k$.

As a simple example, consider the relaxation of the vertex cover IP $x_i + x_j \geq 1$ for every edge $(i,j) \in E$ (the variables are $x_i$ for every vertex $i$, and they are constrained to lie in $[0,1]$). A triangle has minimum vertex cover 2, but the LP has a solution with value only 3/2 (namely, all vertices get the value 1/2). This is an integrality gap of 4/3. There are more complicated integrality gaps of $2-\epsilon$ for every $\epsilon > 0$.


Extract Max for a max-heap in $\log n + \log\log n$ comparisons Given a max heap with extract-max operation.

The basic version takes $2 \log n$ comparisons.
How can I make the running time just $\log n + \log\log n$ comparisons?
How about $\log n + \log\log\log n $ comparisons?

I thought of putting $-\infty$ on the heap root but not really sure what to do with it as it can go anywhere.

To be more precise, I'm only counting comparisons between array item values. I'm reading CLRS Chapter 6 (MAX-HEAPIFY and HEAP-EXTRACT-MAX).

Explanation for log n + log log n comparisons:

1) First, remove the max element from the heap, leaving a hole at the root.

2) Next, remove the last element of the heap (at the bottom right), and hold it in a temp.

3) Reconstruct the heap by iteratively replacing the hole with the greater of its 2 children.  This loop takes log n comparisons (comparing the children at each level of the tree).  Here is an example implementation:

p = root;
while (p->left != NULL) {
    if (p->right == NULL || p->left->val > p->right->val) {
        p->val = p->left->val;
        p = p->left;
    } else {
        p->val = p->right->val;
        p = p->right;
    }
}

4) Now, you have a hole at the bottom of the heap, and you have an element that you removed in step #2.  Insert the element into the hole.  This element needs to be fixed because it could be greater than its parent.

5) Fix the heap in log log n time.  Where you inserted the element, if you take all of its parents, it forms a sorted list of log n elements.  You can do a binary search to find the correct position of the inserted element in this list of parents.  This takes log log n comparisons (binary search in a log n list).  Once you find the position, you can insert the element in the correct place, moving the rest of the elements down.

Total number of comparisons: log n (step 3) + log log n (step 5)


Interchangeable role of public/private key pair and encoding/decoding algorithms In designing a public-key cryptosystem, there are often two desirable properties:

Public/private key pair of each participant can be exchanged. Meaning that whenever a participant has generated a key pair $(a, b)$, it is free up to him to choose to public either $a$ or $b$ (but not both, of course)
Encoding/decoding algorithms $(E, D)$ are interchangeable. It is up to all participants to choose either $E$ or $D$ to be the encoding algorithm, then automatically, $D$ or respectively, $E$ will be the decoding algorithm. But the choice must be made prior to any communication.

Note that if $D$ and $E$ are identical, for e.g. $\mathrm{RSA}$, then the property 2 is vacuously true.

The question is: Assume that $E$ and $D$ are different, is there any known public-key cryptosystem that satisfies property 1 but violates property 2.

Informally, the cryptosystems that we are interested are the ones in which the key generation is in some sense symmetric, but the encoding and decoding algorithms are not.

EDIT: We only consider deterministic encryption scheme. To be meaningful, we assume $\mathrm{M} = \mathrm{C}$ and $\mathrm{PU} = \mathrm{PR}$ where $\mathrm{M}$ is the message space, $\mathrm{C}$ is the ciphertext space, $\mathrm{PU}$ and $\mathrm{PR}$ are public and private key space.

Any RSA variant that goes beyond textbook RSA (which is insecure) will probably not have symmetric encryption/decryption.

Examples are RSA + OAEP or RSA used to encrypt an AES key which is used to actually encrypt the message.


Two's complement Using ONLY Logic Gates How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?

(This question was redirected to CS from Stack Overflow)

A two's complement operation is simply a one's complement operation followed by the addition of 1 to the result. One's complement is easy: simply invert all of the input bits.

The addition of 1 must be done with a 4-bit adder. A 4-bit adder is constructed using four stages of a 1-bit full adder. The 1-bit full adder accepts two bits, plus a Carry input, and generates the sum of the two bits, plus a Carry output. The following diagram is a 1-bit full adder:

We can cascade four of the 1-bit full adder stages together, feeding the Carry output of each stage to the Carry input of the next stage. The inverted (one's complement) inputs are applied to the B inputs of the four stages. To perform an addition of 1, we apply the 4-bit binary value 0001 to the A inputs. The complete boolean circuit is shown below:

The above circuit can be reduced by noting that each XOR operation on the input of each adder stage can be replaced either with an inverter if the A input is a 0, or a NOP (no operation) if the A input is a 1. On further analysis, further reductions may be made to the circuit, as well.


Decidability language, intersection I have two langages $ A, B \in \mathrm{coRE}$.  How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?

The language $A = \Sigma^*$ is coRE. Since $A \triangle B = \overline{B}$, the statement you are trying to prove implies RE=coRE, which is known to be false: for example, the set of all programs that halt is in RE but not in coRE.


Justification for neglecting constant factors in Big O Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing is varying 3 times more rapidly than other! Why do we neglect this fact?

To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.

For instance, we say that a function that takes $3n$ steps is $O(n)$, because, roughly speaking, for large enough inputs, doubling the input size will no more than double the number of steps taken. Similarly, $O(n^2)$ means that doubling the input size will at most quadruple the number of steps, and $O(\log n)$ means that doubling the input size will increase the number of steps by at most some constant.

It's a tool for saying which algorithms scale better, not which ones are absolutely faster.


distinguishing between CTL* formulas $A[FG p]$ and $AFAG p$ using transition system It is to show, using a transition system, that the two formulas $A[FG p]$ and $AFAG p$ are not equivalent.

For me, it seems strange that they are not equivalent.

As the first one says that any computation path eventually has $p$ always true.

And the second one says that any computation path contains a state such that any path starting at this state has $p$ always true.

Aren't they equivalent?

(This is the "standard" example which proves that CTL is not a superset of LTL, in terms of expressiveness)

Consider this system:

state $q0$, transitions to $q0$ and $q1$
state $q1$, transition to $q2$
state $q2$, transition to $q2$

Let $p$ be true in $q0,q2$ but not in $q1$.

(p)     (not p)    (p)
 q0 ----> q1 ----> q2
| ^               | ^
\-/               \-/

State $q0$ does not satisfy formula $AF[AGp]$. Take the infinite path $q0,q0,q0,\ldots$. There is no state in the path satisfying $AGp$ since we can only pick $q0$ and from there the path $q0,q1,q2,q2,q2,\ldots$ does not satisfy $Gp$ since $q1$ does not satisfy $p$.

State $q0$ however satisfies $A[FGp]$. Take any infinite path starting from $q0$. Either it is of the form $q0,q0,q0,\ldots$ or of the form $q0,q0,q0,\ldots,q0,q1,q2,q2,q2,\ldots$. Both forms satisfy $FGp$.