How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$? Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.

What are some efficient ways to enumerate all possible combinations of values of $X_i$'s subject to the constraint $\sum_{i=1}^n X_i = k$?

A naive way is to first enumerate one by one all possible combinations of values of $X_i$'s without the constraint  $\sum_{i=1}^n X_i = k$, and for each combination, check if it satisfies  $\sum_{i=1}^n X_i = k$ (if it does, keep it; if it doesn't, discard it).

That naive way may be inefficient.
For example, when $k=1$, a more efficient way will be for each $i$, letting $X_i=1$ and $X_j =0, \forall j \neq i$.

So I wonder for general $k$, what are some efficient ways to do the above task?

First, separate the set of variables $I = \{1,\dots,n\}$ according to their values:

$\qquad\begin{align}
  I_+ &= \{ i \mid X_i = 1\} \text{ and} \\
  I_- &= \{ i \mid X_i = 0\} \;.
\end{align}$

Let $n_+ = |I_+|$ and $n_- = |I_-|$.

Given $X_1, \dots, X_n$ and $k$, it is clear that we have to choose $k$ indices from $I_+$ and arbitrarily many from $I_-$. That means we will have to output

$\qquad \binom{n_+}{k} \cdot 2^{n_-}$

solutions. Note that if we assume $\binom{a}{b} = 0$ for $b<0$ and $b>a$, this extends nicely to inputs that allow no solution.

Generating all valid solutions in a list can be done by two nested recursions: the outer creates all $k$-subsets of $I_+$, the inner all subsets of $I_-$. This way, no illegal solutions are investigated, which is as efficient as you can expect (up to list operations).

  outer(I+, 0, I-) = inner(I-)
| outer(I+, k, I-) =
    result = []
    foreach ( i in I+ ) {
      suffices = outer(I+ - i, k-1, I-)
      result ++= (suffices map { [i] ++ _ })
    }
    return result

  inner([])      = []
  inner(x::rest) =
    smaller = inner(rest);
    return smaller ++ (smaller map { [x] ++ _ })

If you want an iterator, note that you can replace recursion with stacks (which allows you to compute it step by step) and emit solutions in the innermost call of inner. Of course, you'll have to reverse the way solutions are constructed (while descending, as opposed to during ascension as I did above).


Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations? I have been trying to understand the difference between normal polynomial evaluation and horner's method. usually it takes 3n-1 operations while horner's method reduces it to 2n operations. I tried a couple of explanations but they were too theoritical. I would be glad if somebody comes up with a decent and simple explanation.

Let's compute the polynomial $2+3x+x^2+15x^3$ using Horner's method:
$$ 2 + x(3 + x(1 + 15x)). $$
The complete set of steps is
$$
\begin{align*}
&t_1 \to 15 \times x \\
&t_2 \to t_1 + 1 \\
&t_3 \to t_2 \times x \\
&t_4 \to t_3 + 3 \\
&t_5 \to t_4 \times x \\
&t_6 \to t_5 + 2
\end{align*}
$$
Compare this to the "trivial" method:
$$
\begin{align*}
&t_1 \to x \times x \\
&t_2 \to t_1 \times x \\
&t_3 \to 15 \times t_2 \\
&t_4 \to 3 \times x \\
&t_5 \to 2 + t_4 \\
&t_6 \to t_5 + t_1 \\
&t_7 \to t_6 + t_3
\end{align*}
$$
Here the idea is to compute the powers $1,x,x^2,x^3$ and then take the linear combination corresponding to the polynomial. Since one of the coefficients is $1$ (coefficient of $x^2$), we only need $7$ rather than $8$ operations.


Recover the path to a goal state in A* search algorithm In the A* search algorithm, we use a priority queue with heuristic function to find optimum result with minimum cost. But, how do we get the path after reaching goal?

Every node should have been given a pointer to the node it was reached from. Then you only need to follow and reverse a linked list.


Finding many different minima of nonlinear cost function Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}_0, \vec{x}_1, \dots$ so that $\vec{x}_n$ is orthogonal to $\vec{x}_{n-1}, \vec{x}_{n-2}, \dots, \vec{x}_0$?

Sorry for the apparent lack of effort on my part, but the field of optimization is vast and I do not have a lot of experience. I have searched for variants of a nonlinear conjugate gradient method that have the above property, but haven't been able to find anything.

Suppose you have already found $x_0,\dots,x_{k-1}$ and now  your goal is to find $x_k$.  Let $\mathcal{R}$ denote the region of points that are orthogonal to $x_0,\dots,x_{k-1}$.  Then your problem is to minimize $G(x_k)$ subject to the requirement $x_k \in \mathcal{R}$.  This is a straightforward equality constraint in optimization, and can be handled in a number of ways.  Probably the simplest is to use projected gradient descent, which is like gradient descent but in each step you project the point onto the hyperplane $\mathcal{R}$.  Given how you have defined $\mathcal{R}$, the projection operation in this case is easy.


How does RAM is shared in multi core environment? I learnt that multi core processors have more than one processing units( i.e. the main executing units ALU etc.) and they are better at performance. I want to know how they share Physical memory. I'll take following example to make my question clearer - Say, There is a memory location M in physical memory and Two threads T1 and T2 running on different cores. Is it possible for T1 and T2 to access M at the same instance of time or do they have to wait for one other to complete access i.e. do they share the same memory bus so that they have to wait, for one another or Can they read M at same instance of time from two different memory buses? If former is the case, There is not much performance gain right, as they have to wait for memory bus to be free?

Summarising, Are memory operations independent of other cores or each core can only make a physical memory access when memory bus is free?

I learnt that multi core processors have more than one processing units

Well having more than one processing unit is something present even outside multi-code processors.  Processors which are able to start the execution of several instructions in the same clock cycle are called super-scalar (the first super-scalar processor of Intel in the x86 family is the first Pentium).

Multi-core processors are in fact several processors on the same chip. (Sharing between cores is limited to cache, when sharing more you have architectures called with names like SMT -- simultaneous multi-threading -- or hyperthreading -- which is the name Intel is using).

  I want to know how they share Physical memory.

Modern processors have usually cache (in the x86 family, that started again in the early 90's) so when a core need data, it is usually fetched from the cache without needing to access the main memory.  There is several levels of cache.  The lowest one being used only by a core.  The other can be shared (and how depend on the details of a given model, for example you can have a four core processors with level 2 caches shared between 2 cores).

  There is not much performance gain right, as they have to wait for memory bus to be free?

If one need to access the main memory, it's slow (my rule of thumb: level 1 cache access is 3-5 cycles, level 2 is 20-25 cycles, main memory is 100-150 cycles but again details may vary and I've not looked at them recently).


Proof for This Greedy Strategy for Equalizing An Array Recently the following problem was posed in a private coding competition at my workplace:

  An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

In discussion forums it was suggested to repeatedly find the difference of the smallest and largest elements and then greedily increment all but the largest element by this amount. An implementation using this strategy passed all test cases. However I'm unable to see how this strategy will indeed result in the smallest number of steps.

Actually I am not sure the greedy solution will always give the best solution?

Recall that the change making problem does not work for certain denominations in a greedy way. For example with denominations $1,3,4$ and a goal of $6$ the greedy solution will give $4,1,1$ whereas the optimal solution is $3,3$.

This can be translated into your problem. Start with array $A=[0,6]$ and steps $D=\{1,3,4\}$. Now your greedy solution seems to behave like change making. I am not certain about this, however, as your description does not precisely say by which amount the numbers are incremented. Perhaps your algorithm chooses $[0,6] \to [4,6] \to [7,6] \to [7,7]$ (which is also wrong, anyway).


How can I learn about CS? I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient programmer, but I know I would be a lot better If I was more confident in my ability  to swim on a lower level of the stack. I hardly know any C. (The syntax is easy, but I've never actually implemented anything in it besides some 100 level HW problems. I see this as a problem because so much is written in C.)

I want to be:

better at discrete math
More versed in algorithms
Have a more intimate understanding of how the higher level tools that I rely on actually work.

Basically, I know how to use logic, but I have become dependent on high level tools and I don't like that.

I also suck at math. I mean I understand it conceptually, and Im comfortable with set theory, so, Python's data structures are really all I need, but I want to be better at algorithms and math is necessary for that.

Are there any websites or other resources that stress an approach like this.

Here are a few books I recommend:

Discrete math: Concrete Mathematics: A Foundation for Computer Science, Don Knuth. (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025).

It's very complete and also pretty approachable for someone without much of a theoretical math background.

Algorithms: Algorithms, Kevin Wayne and Bob Sedgwick. Again, very complete and presents all algorithms with motivation and extremely well-written Java code. There's also a really good website with a lot of the info available for free (http://algs4.cs.princeton.edu/home/).

Systems: Computer Systems: A Programmer's Perspective, Bryant and O'Halloran. This one is a little more dense than the two above, but it's a great resource if you know what you want to learn about (e.g. processes, floating point arithmetic). (http://www.amazon.com/Computer-Systems-Programmers-Perspective-Edition/dp/0136108040)

I've had experience with all of these at the undergrad level, so they don't require an enormous amount of experience or higher-level coursework.


Array covering problem Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be
$$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y_1, ..., y_M$ ?

Thanks in advance.

P.S. The original problem is taken from here:
http://www.e-olymp.com/en/problems/3208

Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.


Separate Chaining hashing: time complexity of successful search In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to determine it.

I tried to calculate the cost of access of each node in the list and to divide it by the number of elements of the list, but it doesn't seem correct.
$$1+\frac{m}{n}\cdot \sum _{i=0}^{\frac{n}{m}}\frac{n}{m}-i=1+\frac{n+m}{2m}$$

The expected length of a chain when the $i$th element is added is $\frac{i-1}m$. So if we mentally re-order the elements in the hash map to be in order of insertion, we can calculate the expected length of a chain $E[l]$ when performing a search with $n$ elements in the map:

\begin{align}
E[l]&=\frac{1}{n}\sum_{i=1}^n \frac{i-1}m = \frac{1}{nm}\left(-n + \sum_{i=1}^n i\right) = \frac{1}{nm}\left(-n + \frac{1}{2}n(n+1)\right)\\
E[l] &= \frac{1}{m}\left(-1 + \frac{1}{2}n+\frac{1}{2}\right) = \frac{n}{2m} - \frac{1}{2m}
\end{align}

Now you can substitute $\alpha = \frac n m$ and find $E[l] = \frac \alpha 2  - \frac{\alpha}{2n}$.


How to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and set operations? I have to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and with set operations which contains only words

with even length
with odd length and first letter not equal to last letter

So my solution for part 1 is this. Am I rigth?

  $L_n = \{aa, bb, ab, ba\}* = (L_a.L_a \cup L_b.L_b \cup L_a.L_b \cup L_b.L_a)*$

Regarding to part 2, I dont have any simple solution. In this language must be words like these: $abb,bba,baaaa, ababb$ etc. So before first and last word must be only word with odd length. But I dont know how to write it.

Part 1. is ok. The idea behind is that you have to take the letters 2 by 2 and then make the star closure. Call $L_e$ the language of even words you just defined.

Part 2. Assume for a moment to have defined $L_o$ the language of words of even length from $L_a$ and $L_b$. Then to have even length and different initial and final letter you can just define

$L=L_a\cdot L_o\cdot L_b\cup L_b\cdot L_o\cdot L_a$

Remark that words in $L$ have length at least 3 since $a$ starts and finish with the same letter...

To define $L_o$ the idea is that an even word is just to exploit $L_e$:

$L_o=L_a\cdot L_e\cup L_b\cdot L_e$.


Merge Leaf labeled trees I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible.
Can somebody please help me to generate an algorithm for this task,
with good performance?

Leaf labelled tree is a tree in which all the data is held at leaves.

You can solve this using dynamic programming. Given trees $T_1,\ldots,T_n$, for each $1 \leq a \leq b \leq n$ compute the best way of concatenating $T_a,\ldots,T_b$. Details left to you.


NP-hardness language How to prove that language $L = \{G \; | \; \omega(G) \geq \frac{9}{10}\cdot n\}$, where $n$ - number of vertices in the graph, NP-hard?
$\omega$ - is a clique number.

Consider the following reduction from the NP-complete problem $Clique = \{ \langle G, k\rangle \ : \text{G is undirected Graph that has a clique of size at least k}\}$ to $L$. The reduction operates as follows.
Given input $\langle G = (V, E), k \rangle\in Clique$:

If $k < \frac{9\cdot|V|}{10}$, output $G' = G \cup K_{t}$, where $t= 9\cdot |V| -10k$, and $K_t$ is the complete graph over $t$ vertices. In addition, add edges that connect every vertex in $K_{t}$ with every vertex in $G$.

Othwerwise, if $k \geq \frac{9\cdot|V|}{10}$, output $G'$ that is defined as follows. $G'$ is obtained by replacing each vertex of $v \in V$ by a clique of size 9, denoted $c_9(v)$, and then for every edge $\{ u, v\}\in E$, the two cliques $c_9(v), c_9(u)$ in $G'$ are connected, that is, every vertex of $c_9(v)$ is connected by an edge with every vertex of $c_9(u)$. Also, add to $G'$ new $t$ isolated vertices, where $t= 10k - 9|V|$.

Correctness:

If $k < \frac{9\cdot|V|}{10}$, then note that $t = 9\cdot |V| - 10k >
    0$, and so the output of the reduction $G'$ is well-defined. Now if $G$
has a clique $C$ of size at least $k$, then $G'$ has a clique of
size at least $k+t$ (verify that $C\cup \{ v: \text{$v$ is a vertex
in $K_t$}\}$ is a clique of $G'$). Conversely, if $G'$ has a clique
of $C'$ of size at least $k + t$, then the set $C = C' \setminus \{
v: v \text{ is a vertex of $K_t$} \}$ is a clique of $G$. Indeed,
the reduction does not add new edges between the vertices of $G$.
Also note that $C$ is of size $|C| \geq |C'| - | \{ v: v \text{ is a
vertex of $K_t$} \}| = |C'| - t \geq k+t - t = k$ in $G$. All in
all, we have that $G$ has a clique of size at least $k$ iff $G'$ has
a clique of size at least $k+t$. Finally, note that
$\frac{k+t}{|G'|} = \frac{k+t}{|V|+t} = \frac{k + 9|V| - 10k}{|V| +
9|V| - 10k} = \frac{9|V| - 9k}{10|V|-10k} = \frac{9}{10}$. So, $G$
has a clique of size at least $k$ iff $G'$ has a clique of size at
least $k+t = \frac{9}{10} |G'|$.
If $k \geq\frac{9\cdot|V|}{10}$, then note that  $10k - 9|V| \geq 0$, and so the output of the reduction $G'$ is well-defined. For the first direction, if $G$ has a clique $C$ of size at least $k$, then $G'$ has a clique $C'$ of size at least $9k$. Indeed, we can take $C' = \bigcup_{v\in C} c_9(v)$, that is, $C'$ consists of the 9-cliques corresponding to the vertices in $C$ (verify that $C'$ is indeed a clique of size at least $9k$ in $G'$). The following holds $\frac{|C'|}{|G'|} \geq \frac{9k}{|G'|} =
\frac{9k}{9|V|+t} = \frac{9k}{9|V| +10k-9|V| }
 =
\frac{9}{10}$. So $G'$ has a clique of size at least $\frac{9|G'|}{10}$. Conversely, assume that $G'$ has a clique $C'$ of size at least $\frac{9|G'|}{10} = \frac{9\cdot (9|V| + t)}{10} = \frac{9\cdot(9|V| + 10k - 9|V|)}{10} = \frac{9\cdot 10k}{10} = 9k$. Clearly, none of the added isolated vertices are in $C'$, and thus $C'$ consists of vertices $p$ such that $p\in c_9(v)$ for some $v\in V$. In words, $C'$ consists of vertices $p$ such that $p$ belongs to one of the 9-cliques of $G'$. Note that there could be two vertices $p_1, p_2\in C'$ such that both $p_1$ and $p_2$ are in $c_9(v)$ for some $v\in V$ (that is, $C'$ can have vertices that correspond to the same 9-clique). Now consider the following set $C =\{ v\in V: \text{ there is $p\in C'$ such that $p\in c_9(v)$} \}$. We claim that $C$ is a clique of size at least $k$ in $G$, and thus we're done. To begin with, $|C|\geq k$ because for every $v\in C$ there are at most 9 $p$'s such that $p\in c_9(v)$ and $p\in C'$, and those 9 $p$'s correspond only to the vertex $v$ in $C$. So in the worst case, $C'$ consists of whole 9-cliques and we replace every 9-clique $c_9(v)$ with $v$ to get the set $C$. So, as $|C'|\geq 9k$, then $|C|\geq k$. Now to show that $C$ is a clique in $G$, let $v_1, v_2$ be two vertices in $C$. We need to show that $\{u, v \}\in E$. By definition of $C$, there are $p_1, p_2 \in C'$ such that $p_1\in c_9(v_1)$ and $p_2\in c_9(v_2)$. Since $C'$ is a clique of $G'$, we know that $\{p_1, p_2 \}$ is an edge of $G'$, and by definition of $G'$ this can happen only when $\{v_1, v_2 \} \in E$ (indeed, vertices of different 9-cliques are connected in $G'$ when the vertices defining the 9-cliques are connected in G).


If a language consists of an NP and coNP question, do we have to place it in P^NP^NP? If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?

No, because $A$ isn't necessarily $NP$-complete and $B$ isn't necessarily $coNP$-complete.  You'd need both to be true to force the implication $NP = coNP$ by $X$ being a member of both problem classes.  In fact $A$ and $B$ could both be in $NP$ and $coNP$.  E.g. $A$ and $B$ could both be in $P$.  $NP \cap coNP$ is not the empty set.


Finding a set of maximally different solutions using linear programming or other optimization technique Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is parallel to a constraint, there are infinite or many equally good optimal solutions. I am not asking about this latter case.

I am more interested in finding many solutions that are in the feasible region generated by my set of constraints. But I would like the solutions I find to be 'scattered' around the feasible region in the sense that they are maximally far from one another. Is there a known way to, without running a solver multiple times, generate multiple solutions and use the objective function to enforce that the solutions should be separated?

For example, any linear program with decisions a and b and constraints w <= a <= x and y <= b <= z can be 'duplicated' to find two solutions. Our new linear program has variables a1, a2, b1, and b2 and the constraints w <= a1 <= x and w <= a2 <= x and similar for b1, b2. However, when it comes to forming an objective function we run into trouble as we can not use norms other than the L1-norm without discarding linearity and we can not truly even use the L1 norm because it is not possible (so far as I know) to encode absolute values.

Perhaps I should look into convex optimization or semidefinite programming or something?

Is there a known way to generate a set of solutions to a linear program, and using an objective that enforces "distance" between the solutions?

A heuristic, using linear programming

One approach might be to pick a random objective function, and maximize it.  Then repeat, with a different set of objective functions each time.

In other words, suppose the unknowns are $x_1,x_2,\dots,x_n$, and you have some constraints $\mathcal{C}$.  In each iteration you pick $c_1,c_2,\dots,c_n \in \mathbb{R}$ randomly, then search for a solution that maximizes $c_1 x_1 + \dots + c_n x_n$ subject to the constraints $\mathcal{C}$.

I would expect this heuristic might often find a somewhat scattered set of solutions -- not necessarily maximally scattered (maximally far from each other), but probably not too close to each other, either.

Maximizing the average pairwise L2 distance, using quadratic programming

Alternatively, use quadratic programming.  For simplicity, let's look at the problem of finding two solutions.  Suppose you want two solutions $x,y$ that are as far apart from each other as possible, under the $L_2$ norm (Euclidean distance).  Then this can be formulated as a quadratic programming problem.

Basically, you want to maximize the squared distance $d(x,y)^2 = (x_1-y_1)^2+\cdots+(x_n-y_n)^2$ between $x$ and $y$, subject to the requirement that both $x$ and $y$ must satisfy the constraints.  This is the problem of maximizing a quadratic objective function, with linear constraints -- i.e., quadratic programming.

If you want $k$ points that are maximally scattered, this is also possible.  Say the points are $x^1,\dots,x^k \in \mathbb{R}^n$.  Then you could maximize the objective function

$$\sum_{i<j} d(x^i,x^j)^2,$$

i.e., the function

$$\sum_{i<j} \sum_\ell (x^i_\ell - x^j_\ell)^2.$$

This is a quadratic function, and you have linear constraints $\mathcal{C}$ on each of the points $x^i$, so this is a quadratic programming instance.  It finds you points that are maximally scattered in the sense that the average pairwise distance is maximized.

You can also formulate a greedy variant of this algorithm, where you already have $k$ solutions, and you want to find a $k+1$th solution that satisfies all the linear inequalities and also maximizes the average L2 distance from it to the other $k$ solutions.  That too can be formulated as a quadratic programming problem.

Quadratic programming is harder than linear programming, but there are off-the-self solvers that will solve quadratic programming problems for you.

Maximizing the minimal pairwise L2 distance, using QCQP

Finally, let's say you want your $k$ points to be scattered in the sense that you want to maximize the minimum pairwise distance.  In other words, let's say you want to find the largest possible threshold $t$ such that it is possible to find $k$ points $x^1,\dots,x^k \in \mathbb{R}^n$ that each satisfy the linear constraints, and such that each pair of points is at distance $t$ away from each other: $d(x^i,x^j) \ge t$ for all $i<j$.  Then this can be formulated as a quadratic optimization program with quadratic constraints, i.e., QCQP.  QCQP is even harder, but there are off-the-shelf solvers for QCQP you could try out, too.


Does last carry bit get added onto the sum calculated by full adder? Note: This problem is  from Introduction to Computing Systems: From Bits and Beyond(2nd) edition, 3.15, page 86.

The Problem:

I was able to do the problem and ended up with sum being 0010 and the last carry bit of 1.

Using a tow bit full adder, would the last carry bit be appended to the beginning of the sum, making it 10010(18 the correct answer with decimal alue addition)) or does it get omitted, making the answers different?

If it does get appended, how would I justify the answers are the same? The full adder takes account carry bits and binary bits?

Addition on $w$-bit registers (or memory locations) is effectively addition modulo $2^w$, that is the carry bit is thrown away. However, on x86 CPUs at least, before getting thrown away, it is copied to the carry flag or overflow flag (so the carry bit is actually not thrown away). An additional instruction, "add with carry", adds two inputs together with the carry flag. Using these instructions, you can (1) detect overflow (which happens if the carry flag is set), and (2) implement addition on multiples on $w$ bits. For example, suppose you want to add two integers $x_1x_0$ and $y_1y_0$, where $x_i,y_i$ is each a $w$-bit memory location. You first add $x_0$ and $y_0$, and then add $x_1$ and $y_1$ along with the carry.

To answer your specific problem, for 4-bit wide registers, 0111+1011=0010, and additionally the carry flag is set, if any.


Every AVL tree can be colored to be a red-black tree I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately.
Let $h$ be the height of a subtree of an AVL tree.
It is given that such a coloring is constrained by these cases:

$h$ even $\implies$ black height $=$ $\frac{h}{2} + 1$, root node black
$h$ odd $\implies$ black height $=$  $\frac{h+1}{2}$, root node red

After that the root node is colored black.

I'm trying to prove this inductively. Let's start with the base case $h=1$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.
Now suppose the statement is true for some $h \geq 1$. Then for any node $u$ in the AVL tree, the height difference between their children is less than $1$. That is, for an AVL tree of height $h+1$ either both subtrees of the root node have height $h$ or one has height $h-1$.
By the induction hypothesis we know how to color the subtree of height $h$, depending on the parity of $h$. I'm unsure if I should use strong induction instead because it is not given in the hypothesis how to color a subtree of height $h-1$.
If we would know how to color both subtrees, then consider the following cases:

$h+1$ is even

one subtree has height $h$, the other height $h-1$
both subtrees have height $h$

$h+1$ is odd

one subtree has height $h$, the other height $h-1$
both subtrees have height $h$

For case 1.1 we would get
$$
  \begin{align*}
\quad & h+1 &\text{even} \\
\implies \quad & h &\text{odd} \\
\implies \quad & \text{black height} = \frac{h+1}{2} \\
\implies \quad & h-1 &\text{even} \\
\implies \quad & \text{black height} = \frac{(h-1)}{2} + 1 = \frac{h+1}{2}
  \end{align*}
$$
So their black heights differ by $1$. How would I take that into consideration?

Here is a computer verification of your method.
The height discrepancies occur when we are making a red root, in which case the shorter child with the reduced black height would also have a red root. Since there can't be two consecutive red nodes, we need to turn the shorter child black, which increases its black height to match the taller child.


Analogy between Gödel's incompleteness proof and Richard's argument If we take a look at Gödel's paper “On formally undecidable propositions”,
the first self referential proof given in the paper, with the following formula:

$$n \in K \equiv \overline{\textit{Bew}}[R(n); n]$$

Which look like this in more modern mathematics:

$$K = \{n \in \mathbb N : \lnot\text{provable}(R_n(n))\}$$

Gödel says:

  The analogy of this argument with Richard antinomy leaps to the eye

I'm trying to figure out how this is the case:

I know Richard's Paradox basically uses Cantor's diagonal argument.

Which begins its set description like so:

$$X = \{s \in S : s \not\in f(s)\}$$

We can see the similarity between this and and Gödel's argument, especially given that both set/class descriptions end up with a self-referential contradiction.

However, I'm trying to construct a more rigorous comparison between Richard and Gödel's arguments, and how they are considered to be analogical of each other.

In particular, how the contradictions are seen to be analogous by Gödel.

Can anyone help out?

Both examples are instances of diagonalization, a technique also used to prove Cantor's theorem ($\kappa < 2^\kappa$ for all cardinals $\kappa$) and Turing's theorem that the halting problem is undecidable.

An analogy is by nature informal. It is not supposed to be rigorous.


How to calculate Huffman code length without generating the actual huffman code? Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself?

Using Matlab, I was able to compute the Huffman code and and get the length of the codewords but is it possible to get the lengths alone without computing the codewords?

You can count the distribution of frequency of the alphabet you want to Huffman encode.
If this distribution is skewed Huffman encoding will perform poorly.
See: When would the worst case for Huffman coding occur?

If this distribution is flat Huffman encoding will perform well.
The more letters in your possible alphabet do not occur in your text the better Huffman performs.

If however you have a flat distribution and most or all of the possible encoding space in your alphabet is used, then Huffman encoding will not be able to compress it.

If you want to generate the lengths of the codes that Huffman would create without actually doing Huffman encoding you will need to create a algorithm so close to Huffman as to not make very much difference, especially not in running time.

Note that the bulk of the running time of Huffman encoding is taken up by frequency counting.
For a text of length $n$ with an alphabet of $a$ characters the running time of Huffman is $O(n+a)$ and because $a$ is almost always insignificant (as well as being a constant) in comparison to $n$. The running time is $O(n)$.

You can skip the counting step if you want by making assumptions about your input.
For instance if you know your input is English text or C-source code, than you can simply use the average frequencies for typical English texts (or C-source code) to generate your Huffman code.
If so you will already know the lengths of your codes, because you are simply loading a precomputed table of Huffman codes.

Needless to say this risks suboptimal compression.


When can one use a $O(n)$ time sorting algorithm? Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time.

As I understand it, it's not always possible to use the $O(n)$ sorting algorithms. What are those cases when they can not be used?

In the comparison model, where all you are allowed to do is to compare two elements, and without further assumptions, we can prove that no sorting algorithm can do better than $O(n\log n)$.

If you want to sort in $O(n)$, you need either a stronger model, or additional assumptions.

For example, if you can bound the range of the numbers you are sorting, you can use bucket-sort, which is $O(n)$ (time).

A different example is spaghetti-sort: if you can implement the $\max$ function over $n$ elements in $O(1)$, then you can sort in $O(n)$.

You see here that different assumptions can allow you to sort in $O(n)$. There is no characterization of exactly which assumptions allow it.


Language which is recursively enumerable but not recursive Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable but couldn't find such examples anywhere.. :(

The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.


Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine? An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.)

However, there are
different kind of algorithms, such as deterministic, non-deterministic,
and randomized algorithms, and possibly others.

Are these algorithms running on deterministic Turing Machines, or do
they have to be run on specific machines? For example:

Are nondeterministic algorithm algorithms on a deterministic Turing
machine? I heard that they are not, but are on nondeterminisitic
Turing machines, but I forget where I heard it. Or I might be wrong.
Are randomized algorithms algorithms on a deterministic Turing
machine?

Broadly speaking, you can normally trade the word "algorithm" for the words "Turing Machine", in the sense that a Turing Machine is not a programmable computer like the one you have in front of you, it is a mathematical embodiment of an algorithm. So for the two cases you mention:

A nondeterministic algorithm is a nondeterministic Turing Machine.
A randomized algorithm is a probabilistic Turing Machine.


Halting problem theory vs. practice It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.

But that only applies to an arbitrary program.

Has there been any study regarding classes of programs humans usually make?

It can sometimes be easy to analyze a program and enumerate all of its degrees of freedom and conclude that it will halt.

For example, has there ever been an effort to create a programming language (scripting really) that guarantees halting? It would not be widely applicable but could still be useful for mission critical modules.

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a very desirable property in general in programming languages research.

I haven't seen a lot of success in catching infinite loops in practice however "Ensuring Termination in ESFP" by Telford and Turner shows a more robust termination checker that was able to prove that Euclid's algorithm always terminated and handles partial cases. Euclid's algorithm is a famously tricky example of a primitive recursive function that isn't straightforwardly provable to be primitive recursive. It fails checkers that simply look for a decreasing parameter (or some simple pattern of decreasing parameters like Foetus termination checker). To implement this using primitive recursive combinators you have to encode a proof of termination for the algorithm as a parameter in the function essentially.

I can't think of any results for procedural languages off the top of my head and most results in functional languages use some kind of restriction that makes the obviously terminate rather than trying to perform some kind of complex analysis to ensure that more natural programs terminate.


Math behind leetcode problem 47 permutations II Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it?
The problem is as follows:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Here is the code:
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;
    }

    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){

        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{

            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }
        }
    }
};

(1) You are sorting the vector so duplicate values will be consecutively present in the vector.
(2) Now we come to the logic behind that condition:

As the vector can contain the duplicates we should make sure not to repeat the same sequence by starting with the same element again(duplicate)

example :

1,1,2 (starting with first one) and 1,1,2 (starting with second one) => both are same (we should make sure this doesn't happen)

Example: In [1, 1, 2]

If the first element in the sequence is chosen as 1, then we should make sure we are not going to create another sequence starting with another 1 (duplicate of the element).

So for that, we need to skip the loop for all the consecutive duplicate elements.

In your case, after creating a sequence staring with first 1, when we enter the loop for the second time we check whether the current element is a duplicate nums[i] == nums[i - 1] (this is sufficient as you have already sorted the vector) and whether the current element is the first element of the sequence !used[i - 1].

In your case, due to this condition, the second one cannot be the first element of the sequence.


Poly-time reductions for proving EXPTIME-hardness are _not_ enough? Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me.

Suppose our problem can be solved in time $O(2^k)$, where $k$ is an input number to our problem instance; let it be in binary. Consider some EXPTIME-complete problem that takes a number $n$ as input. Consider a hypothetical reduction that creates our problem instance with $k=2^n$; it is is poly-time, because it computes $2^n$ by shifting $n$ times the letter $1$ to the right. Our reduction implies that the original problem can be solved in $2^{2^n}$ time. But that is not sufficient for proving EXPTIME-hardness of our problem, because we cannot derive the contradiction by assuming our problem is solveable in poly-time. Therefore, we cannot use poly-time reductions.

Where is the mistake? Is it about binary/unary encoding of numbers? Is it about meaning of $O(2^k)$ vs. $O(2^{|\text{string representing k}|})$?

If your problem can be solved in time $O(2^k)$, where $k$ is some number in the input, all you can say about its membership in conventional complexity classes is that it's in $\mathrm{2EXP}$, since an instance of length $\ell$ can be decided in time $O(2^{2^\ell})$.  You've not established that the problem is in $\mathrm{EXP}$.

$\mathrm{EXP}$, like all conventional complexity classes, is defined in terms of the length of the input, not the values represented in that input.


Where were the ideas of vote, accept and commit phases originally introduced? In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5.

Is this a novel introduction or has this been previously been introduced, and if so, where? More specifically, I refer to definitions of these given in section 5.

This dates back to the Byzantine broadcast algorithm of Bracha:

Bracha, Gabriel. "Asynchronous Byzantine agreement protocols." Information and Computation 75.2 (1987): 130-143.


Group points by given shapes I am using a sensing board able to detect magnetic signals between the board and a display.

I have a set of objects that are represented (each of them) by a unique set of points (magnets) with a particular shape. For example: object #1 is made by three points that form an equilateral triangle with side length 1cm; object #2 is made by three points that form a right triangle with sides 3cm, 4cm, 5cm; object #3 is made by three aligned points with distance 2cm; and so on. I can have a multiplicity of objects with unique patterns.

Now I have a list of points with the coordinates w.r.t. the Cartesian plane, and I need to match them referring to the patterns I got from the objects. I also know that every point must be matched, therefore I can minimize the overlapping errors. In practice, every point in the set can belong to maximum one object, and at the same time also it must belong to an object of the initial set.

Any idea on how to do that in an efficient way?

In the general case a problem like this is NP, however in the vast majority of real cases it should be easy.

20 points make 1140 triangles so it shouldn't be hard to pick out the triangles most similar to your basic shapes (unless the shapes can be more complicated). A little ugly backtracking may be needed when the top scoring triangles overlap.

Also, if most magnets move continuously, you can easily map old points to new points and old triangles to new triangles.

What I'm talking about are fairly obvious methods. There may be smarter ways to do this, but you don't necessarily need them.


What are the examples of the easily computable "wild" permutations? I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the input variable, ie.

for every $x_1$ and $x_2$ that are close $|x_1 - x_2| < 100$ the outputs of the function should differ very much $|f(x_1) - f(x_2)| > n/{100}$
changing any digit in the input should change most of digits in the output
Shannon's Confusion and diffusion: http://en.wikipedia.org/wiki/Confusion_and_diffusion
There should be very little or no fixed points (for every $x$: $f(x) \neq x$).

or any combination of the above conditions.

I don't need the inverse function. It should also be easy to compute from the closed form expression (a maximum of a few thousands simple computer operations like addition, multiplication, modulo etc.) for $n=10^{100}$.

I found some examples in Google:

Linear congruential generator. Equation:

$X_{n+1} = (aX_n + c) \mod m$

Wikipedia states that: "Provided that the offset $c$ is nonzero, the LCG will have a full period for all seed values if and only if:

$c$ and $m$ are relatively prime,
$a - 1$ is divisible by all prime factors of $m$,
$a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

I've tried using another function $f(x) = (ax + c) \mod m$, because I wanted to get rid of the recursion, and as long as $m$ is prime and $a \ge 1$ I get the permutation. However the result is not that "wild" or "chaotic" as I expect it to be.

Minimal perfect hash function

The concept is similar to what I'm looking for, but if I understand correctly the computation of this kind of function is very complicated and time-consuming and it cannot be expressed in a closed form as a simple expression for $n=10^{100}$.

Substitution-permutation network

I am not sure how to apply S-boxes and P-boxes to the interval [0,n), but maybe it could be used.

The question is: Could you give me some examples of functions that satisfy the above conditions (or some pointers like the mathematical term for the object I am looking for)?

Yes, such things exist.  They have been studied in the cryptographic literature: the key name is "format-preserving encryption".

To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto.stackexchange.com/q/20035/351 and https://crypto.stackexchange.com/q/18988/351 and
https://crypto.stackexchange.com/questions/tagged/format-preserving.  You could also construct a suitable block cipher yourself using a Feistel construction, but it's probably better to use a standard scheme that has been analyzed in the literature.

There are many constructions.  The best one will depend on the specific value of $n$ in your application.  Take a look at the schemes in the cryptographic literature, then if you have a more specific question about how to use one of those schemes, you can ask either here or on Crypto.SE.


How to sort objects based only on "less than" relationships? Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n objects, given only the matrix Z?

What you are looking for is a comparison sort. Please take a look at that article.

Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final sorted list. Object i should occur before object j if Z(i, j) = 1. Object i can occur before or after object j if Z(i, j) = Z(j, i) = 0.

As vonbrand mentioned, we should assume that the matrix Z specifies a well-defined "less than" relation or, in terms of math, a total strict-order on the values of the objects. Otherwise, the given objects may not be sorted.

Z[i, j] = 0 if Z[j, i] = 1. Otherwise, we cannot sort object i and object j.
Z[j, i] = 0 if Z[i, k] = 1 and Z[k, j] = 1 for some k. Otherwise, we cannot sort object i, j and k (think of paper-scissors-rock).

Assume that Z specifies a well-defined "less than" relation. Then it also defines a "$\le$" comparison operation naturally. Namely, if Z(j, i) = 0, then object i $\le$ object j. So we can apply any comparison sort to sort the given $n$ object.

Almost all sorting algorithms are comparison sorts. For example, quicksort, mergesort, insertion sort, selection sort and bubble sort. A notable exception is counting sort.


MST - algorithm to add an edge to the graph I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum spanning tree) of $G$. Now, we add a new edge $e'$ to $E$ with weight $w(e')$. Find an algorithm that updates $T$ so it will be a MST of the new graph $G' = (V,E \cup \{e'\})$. The time complexity of the algorithm should be $O(V+E)$.

Intuitively, the algorithm is quite simple: add $e'$ to $T$, and then we got one cycle closed. Remove the edge with maximal weight from this cycle, and obtain a MST of $G'$.

However, I had some difficulties prove the correctness of this algorithm formally, and would appriciate some help.

BTW. I have read this post: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? but unfortunately haven't fully got the proof there.

Update: I tried Steven's solution and it helped me a lot, thanks again. I also found this solution online (I add a picture), but didn't understand it well. I also don't understand why in this solution, $T'$ is the MST on $G'$ instead of a MST on $G'$. Can someone help me understand what is going on the proof there, please?

Let $T$ be the MST of the original graph $G$ and let $e'$ be the newly added edge.
Suppose for simplicity that all edge weights are unique (if they are not, fix any arbitrary linear order among $E(G)$ that prioritizes the edges in $E(T)$. Then break weight ties according to this order).

Let $e$ be the edge of maximum weight in the unique cycle $C$ of $T + e'$. And assume that $e \neq e'$ (otherwise the proof is trivial).

One way to prove that $T-e+e'$ is a MST of $G+e'$ is showing that no edge $f \in \{e\} \cup E(G) \setminus E(T)$ can belong to any MST of $G+e'$ using the cycle rule.

If $f=e$, $f$ cannot belong to any MST of $G + e'$ because it is the edge of maximum weight of the cycle $C \subseteq T+e' \subseteq G + e'$.

If $f \in E(G) \setminus E(T)$ then, since $f \not\in E(T)$, $f$ must be the edge of maximum weight of some cycle $C' \subseteq G \subset G + e'$ and hence it cannot belong to any MST of $G + e'$.


Is the language $L = \{a^nb^m : n = 2^m\}$ context-free? Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

Assume L is a context-free language. Then $\ \exists p\in \mathbb{Z}^{+}:\forall s\in L\left | s \right |\geq p. s = uvxyz,\left | vy \right |\geq 1,\left | vxy \right |\leq p. s_i = uv^{i}xy^{i}z\in L\forall i\geq 0\ $.

Let s = $\ a^{2^p}b^{p}\ $

Pumping i times will give a string of length $\ 2^{p} + (i - 1)*j\ $ a's and $\ p + (i - 1)*k\ $ b's where $\ 1 \leq j + k \leq p\ $

Case 1: $\ j \neq 0\ $ $\ k \neq 0\ $

??

Case 2: $\ j = 0\ $ $\ k \neq 0\ $

??

Case 3: $\ j \neq 0\ $ $\ k = 0\ $

??

It can be concluded from this that L is not a context-free language.

You have stated that pumping $s$ $i$ times will give a string which contains $2^p+(i-1)*j$ $a$'s and $p+(i-1)*k$ $b$'s where $1 \le j+k \le p$. For the given language $L$ to be a CFG, new string must also belong to $L$ for all valid values of $i$.

Put $i=2$. This gives a string containing $2^p+j$ $a$'s and $p+k$ $b$'s. For this to be of the form $a^{2^m}b^m$, we need $$2^{p+k} = 2^p+j$$ This implies $$j = 2^p*(2^k-1)$$

Case 1: If $k = 0$, then from the above equation, $j$ must be $0$. But, this implies, $|vy| = 0$. So, this case is not possible

Case 2: If $k \ne 0 $, then $j \ge 2^p \ge p$, but this is also not possible since $|vy| \le p$. So, the equation  $$j = 2^p*(2^k-1)$$ is not possible.

Therefore, we cannot split the string $s = a^{2^p}b^p$ satisfying all constraints. So, the language $L$ is not Context Free.


Longest double increasing subsequence (LIS variant) I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $2<i\leq k$ we have $p_{i-2} < p_i$. For example, if $S = 1 \space 4\space 2\space 7\space 1\space 6$, a possible double increasing subsequence is $P = 1\space 2\space 7\space 6$ because $7 > 1$ and $6 > 2$. (For every sequence $S$ with more than 2 elements, there's a trivial subsequence of length 2) The problem is to determine the length of longest double increasing subsequence (LDIS) of a given series of integers, $S$.

This is what I've done: I defined $C[i]$ to be the length of the LDIS of the series that ends with $s_i$, and $E[i]$ to be the element before the last element of the LDIS that ends with $s_i$. In the example aforementioned, $C[6] = 5$, and $E[6]=7$. If there are several options for $E[i]$, we'll take the minimal one. For example for $C[5] = 2$ we have 3 different options for LDIS, all of lengths 2: $4 \space 1$,  $2 \space 1$ and  $7 \space 1$ (Trivial LDIS's), so we'll define $E[5] = 2$.

Now my dynamic programming solution is just like LIS solution (the $n^2$, not the $nlogn$):
If $C$ and $E$ are my $n$-sized arrays, $C[1] = 1, E[1] = \inf$(meaning there's no previous value), $C[2]=2,E[2]=s_1$, and for every $2<i\leq n$ we finding $C[i]$ by iterating over the previous $i$ calculates values, and we take the maximum over the $C[i]$'s such that $s_i>E[i]$, plus 1. (Again, if there are several candidates, we take E[i] as the minimal of the possible options) After calculating all $n$ values, we iterate over the array and choose the index that hold the maximal $C[i]$.

This is my mind set in general, maybe I've missed several details but I believe I delivered the idea. Now these are my problems with my solution:
1) It misses strong, well defined recursive formula. I can phrase some sort of recursive relation according to the regularity of the question, but it feels kinda forced. (Despite of the iterative solution I've describe, which is fairly simple)
2) I've ran the algorithm on several examples and it seems to give a right answer, but as a consequence of 1, I have hard time "believing" my solution is correct. I feel like there's more simple and elegant solution to the problem.

Any ideas will be vastly appreciated, thanks in advance.

A counter example where your algorithm fails:
S = 0 7 1 4 6 5 3 2.

Expected : 5, your algorithm would produce 3

There is an O(n^3) dynamic programming based algorithm for this if you are interested :)


Page vs page table entry Im studying for OS-finals and I cant figure out the difference.

A page is a chunk of addresses e.g 0-4095. This maps to 4kB of memory.
This page is 4kB big. But according to the litterature the Page table entry is around 4 Bytes big. I thought Page Table Entry are the same as a page.

AFAIK, the page table entry doesn't contain the page itself. Rather, it contains the address of the physical memory chunk that the particular page in the table is mapped to. This address will be 32-bits (4 bytes).

In this example, the page table entry contains the address of the physical memory chunk (frame). Knowing the offset, we can find the actual address in the physical memory.

Hope it helps.


$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$? $A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial (empty or $\Sigma^*$).

BUT, if $B$ is NPC then $B\ne \emptyset, \Sigma^*$, so in which case there's is no polynomial reduction from $A$ to $B$?

I think you've confused the direction of the reductions. A reduction from $A$ to $B$ means that you could solve $A$ efficiently if you had an efficient way of solving $B$. It's certainly true that you could determine membership of a finite language efficiently if you could solve some NP-complete problem. After all, you can determine membership of a finite language efficiently already, without needing to solve, say, travelling salesman.

On the other hand, it would be surprising if there was a polynomial-time reduction from some NP-complete problem to the problem of determining membership of a finite language. That would be saying, "If I could determine membership of this finite language efficiently, I could solve every problem in NP efficiently."

In case you weren't confused about which way reductions go, here's a concrete reduction from the language $\mathcal{L} = \{\mathrm{elimination}, \mathrm{computer}, \mathrm{science}\}$ to Boolean satisfiability.  We will define a polynomial-time computable function $f$ from strings $\{a, \dots, z\}^*$ to Boolean formulae such that $f(w)$ is satisfiable if, and only if, $w\in \mathcal{L}$.

if w = "elimination" or w = "computer" or w = "science"
    return "X"
else
    return "X∧¬X"


Is relation following given characteristic already in 2NF, 3NF and BCNF? The definitions of 2NF, 3NF and BCNF goes like this:

  2 Normal Form (NF) definition
   A relation is in second normal form if and only if it is in first normal form and all the non-key attributes are fully functionally dependent on the candidate key.

  3 NF - definition
    A relation schema $R$ is in third normal form (3NF) if, whenever a nontrivial functional dependency $α→β$ holds in $R$, either

  $α$ is a superkey of $R$, or
  $β$ is a prime attribute of $R$.

  BCNF (Boyce–Codd normal form) - definition
  A relation schema $R$ is in BCNF, if whenever a nontrivial functional dependency $α→β$ holds in $R$, $α$ is a superkey in $R$.

Based upon these decision, I want to know if the relation having below characteristic is already in some normal form.

All candidate keys are of single attributes: this one is definitely in 2NF as there cannot be any partial dependency, but full functional dependency on CK. I am more confused about 3NF and BCNF. I feel its not in 3NF and BCNF since there can exist $\alpha \rightarrow \beta$, such that both $\alpha$ and $\beta$ are non key, violating 3NF and BCNF definitions.

Am I right with this?

Consider a relation schema R(A, B, C), with the functional dependencies:

A → B
B → C

In this schema there is only one candidate key (A), and it has a unique attribute. But the schema is not in BCNF, since B is not a superkey, neither in 3NF, since C is not a prime attribute.

So your intuition is correct.


Number of circuits with at most $m$ logic gates I'm working on the same exercise as described in this post:

How to show that hard-to-compute Boolean functions exist?

In the answer there I don't understand how the number of circuits with at most $m$ gates was found to be $O(m^{4m})$. My construction of the number of gates required:

Let any logic gate in the circuit take 2 inputs, which could be any of the $n$ inputs or any of the $m-1$ other logic gates. Then there are ${{m+n-1}\choose{2}}$ possibilities for the inputs into any logic gate. There are 16 different functions that act on 2 inputs, so let there be $16{{m+n-1}\choose{2}}$ possibilities for the inputs and type for any logic gate. Lastly, since there are $m$ gates, there will be $16^m {{m+n-1}\choose{2}}^m$ possibilities for the entire circuit.

Now we can say ${{m+n-1}\choose{2}}^m < \frac{1}{2^m}(m+n-1)^{2m} < \frac{1}{2^m}(2m)^{2m}$ when $m = 2^n/\log n$ (or $2^n/n$), so $16^m {{m+n-1}\choose{2}}^m < (32m^2)^m$. So we would want to show that $(32m^2)^m$ is less than $2^{2^n}$. This doesn't seem to be true anywhere, so I must have made a mistake somewhere.

I've looked online a bit and have found three different sources say that the number of circuits with at most $m$ inputs is $m^2$, $2^m$, and something similar to what I came up with. I understand that which gates to use is vague, but these are fundamentally different functions, and I'm very confused.

I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly.

You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves $16(m+n)^2$ possibilities for the type of each gate. Since there are $m$ gates, at first glance there should be $(16(m+n)^2)^m$ different circuits we could construct from these gates.

However, we should also specifically select for the output gate, so we multiply the number of circuits by $m$ to account for this choice: thus we have a bound of $m\cdot(16(m+n)^2)^m$ different possible circuits of size $m$.

The crucial step that you are missing is that the labels we assigned to each of our gates were arbitrary, and thus we can divide our bound by $m!$ to compensate for our overcounting.

We thus have a tighter bound of
$$\frac{m \cdot (16 (m+n)^2)^m}{m!}$$ for the number of circuits of size $m$.

If we assume $m = (1-\epsilon)\frac{2^n}{n}$, for any $\epsilon>0$, one can (and Katz does) show that this is less than $2^{2^n}$.


General term for map/fmap The general term for folds is a catamorphism. The general term for unfold is an Anamorphism. Is there an equivalent term for map?  I know that a map is a type of fold however restriction is significant.  Also it would be useful to have an alternative term to use when the word “map” is ambiguous.

In addition to being in agreement with Derek (that the ana/cata terminology doesn't bring much to the table) I'll note that the "category theoretic" terminology for the general map function of type
$$\mathrm{map}:\forall \alpha\beta. (\alpha \rightarrow\beta)\rightarrow(F\ \alpha\rightarrow F\beta) $$
for a functor $F$ is simply "the functorial action of $F$", and is often written as $F$! For example, on lists, map f l would be written $\mathrm{List}(f)(l)$.

For some reason, computer scientists seem to prefer to have a seperate name for the type constructor and the action on morphisms, but mathematicians do not really consider non-functorial constructors anyways.


Finding whether the language is CFL or regular $L = (0^i 1)^n$ where  i=1,2,3,4...n  and n>=0

For eg :- 00010001 doesn't belong to the language as n=2 but i=3 at the beginning.

001001001 belongs to L as n=3 and i=2 in all cases.

I know the above language is not regular for sure as value of 'i' depends on value of 'n' and it requires comparison. So DFA not possible.

Now I am not sure to which class of language does the above language belong because to check number of zeroes or 'i', we need value of 'n' which can be found out only after reading the entire string.

Can someone please help?

Suppose there exists a CFG whose language is $L$, and let $k$ be the pumping length. Consider the string $(0^k1)^k \in L$. Then, by pumping lemma, there exists a decomposition $(0^k1)^k = uvwxy$ where $|vwx| \leq k$, $vx \neq \varepsilon$, and for each $i \geq 0$, $uv^iwx^iy \in L$. Since $|vx| \leq |vwx| \leq k$, there are four types of values of $vx$: either $vx \in 0^+$, $vx \in 0^+1$, $vx \in 10^+$, or $vx \in 0^+10^+$. Try showing that in each of these cases, pumping $vx$ gives a string not in $L$, thus giving a contradiction and demonstrating that $L$ is not context-free.


Why do we need to take the derivative of the activation function in backwards propagation? I was reading this article here: https://towardsdatascience.com/how-does-back-propagation-in-artificial-neural-networks-work-c7cad873ea7.

When he gets to the part where he calculates the loss at every node, he says to use the following formula:

"delta_0 = w . delta_1 . f'(z)
where values delta_0, w and f’(z) are those of the same unit’s, while delta_1 is the loss of the unit on the other side of the weighted link."

And $f$ is the activation function.

He then says:

"You can think of it this way, in order to get the loss of a node (e.g. Z0), we multiply the value of its corresponding f’(z) by the loss of the node it is connected to in the next layer (delta_1), by the weight of the link connecting both nodes."

However, he doesn't actually explain why we need the derivative term. Where does that term come from and why do we need it?

My idea so far is this:

The fact that the identity activation function causes the term to disappear is a hint. The node doesn't feed into the next exactly as is, it depends on the activation function. When the activation function is the identity, the loss at that node just passes to the next one based on the weight.
Basically, you just need to factor in the activation function somehow, specifically in a way that doesn't matter when it's the identity, and of course the derivative is a way to do this.

The issue is that this isn't very rigorous, so I'm looking for a slightly more detailed explanation.

As a disclaimer, I didn't read that page, but I can certainly explain where the derivatives come from. The backpropagation algorithm is actually a variant of the gradient descent algorithm.

Think about a single function for the moment. Suppose you have a function which responds to a single input and a single weight: $f(w, x)$. We want to adjust $w$ so that it gives expected answers for various known values of $x$.

Then by Taylor's theorem:

$$f(w + \delta w, x) \approx f(w, x) + \delta w \frac{\partial f}{\partial w}(w, x)$$

Or to put it another way:

$$f(w + \delta w, x) - f(w, x) \approx \delta w \frac{\partial f}{\partial w}(w, x)$$

So if you find a value for $x$ which gives the wrong output, this gives you an estimate of how "wrong" $w$ is, and it's related to the derivative of $f$.

This idea extends to multi-variate calculus. If you have a vector of weights and inputs $\mathbf{w}$ and $\mathbf{x}$, then Taylor's theorem says:

$$f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) \approx f(\mathbf{w}, \mathbf{x}) + \nabla_{\mathbf{w}}f \cdot \delta \mathbf{w}$$

Where $\nabla_{\mathbf{w}}f$ is the gradient of $f$ with respect to the weights only.

Now let's think about your case, where the function $f$ has a specific form: it's a function applied to the dot product of $\mathbf{w}$ and $\mathbf{x}$:

$$f(\mathbf{w},\mathbf{x}) = h(\mathbf{w} \cdot \mathbf{x})$$

Then:

$$\begin{align*}
f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) - f(\mathbf{w}, \mathbf{x}) & = h((\mathbf{w} + \delta \mathbf{w}) \cdot \mathbf{x}) - h(\mathbf{w} \cdot \mathbf{x}) \\
& \approx (\mathbf{x} \cdot \delta \mathbf{w})\, h'(\mathbf{w} \cdot \mathbf{x})
\end{align*}$$

Again, this gives you an approximation to how "wrong" the weights are given a "wrong" observation.

The backpropagation algorithm works by combining all of the training data into a single loss function which measures how "bad" the current set of weights is in training the data, and then does more or less exactly the above procedure, estimating the gradient of the loss function with respect to the weights, and then moving all of the weights in that direction.


Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8 Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem?
I was thinking of constructing all possible numbers that fit into the integer size of the language that I am using, through a recursive procedure, but I am not sure how to do that. It seems complicated. Is there an alternative solution apart from taking some of the digits from the given set and constructing numbers?

This is much easier than inclusion–exclusion.  Compute the number of natural numbers smaller than $N$ that contain none of the digits 2, 4, 6, 8 and subtract that from $N$ (or $N+1$ if you're including zero).  To compute the number of naturals that contain none of 2, 4, 6, 8, observe that, if $M\leq N$ (padded with zeroes so $M$ also has $d$ digits) then $M$ and $N$ must agree on their first $i$ digits (for some $0\leq i\leq d$), then the $(i+1)$st digit of $M$ must be less than the $(i+1)$st digit of $N$ and the $(i+2)$nd, ..., $d$th digits of $M$ can be any of 0, 1, 3, 5, 7, 9.


Does classification of a problem also require the algorithm used? Just learnt that a problem in computer science can be divided into the following categories

Polynomial problems
NP problems
NP hard problems
NP complete problems

based on how long it takes to run the program

For example, suppose there is a problem P that can be solved with two algorithms say A1 and A2 where,

A1 is polynomial in nature,
A2 is non-polynomial

According to me, if P is solved using A1, then P is a polynomial problem and if P is solved using A2, then it must be an NP problem.

Am I right?

In other words, is it fair enough to say that classification of a problem does also require the algorithm that is being used to solve it?

No. The classification of problems into complexity classes is based on the amount of resources required to solve the problem, not the resources that some programmer decides to use. If you have a smart algorithm that solves a problem in polynomial time, and a dumb one that uses exponential time, the problem itself is in polynomial time because it can be solved within that resource bound.


Macro expansion is done in which phase of a compiler? This is question raised by my teacher in the class room. I don't have enough knowledge about phases of compiler and macro expansion. Could someone help me in finding out proper solution to this

It's completely dependent on the language. Different languages have wildly different notions of macros. I'll just give a few examples; other situations are possible.

The original C language (K&R C)

Macros are expanded by the preprocessor, which is a separate program that runs before the compiler proper. Macros perform a simple text substitution. This program prints 1, because PLUS()PLUS() expands to ++ which is the increment operator.

#include <stdio.h>
#define PLUS() +
int main()
{
    int x = 0;
    PLUS()PLUS()x;
    printf("%d\n", x);
    return 0;
}

The modern C language (ANSI C)

Macros are expanded by the preprocessor, which acts on tokens, after lexical analysis. Thus, a macro only expands to whole tokens, but can contain things like unbalanced parentheses. The program above prints 0, because each PLUS() expands to a + token, so the instruction is equivalent to + + x;.

Lisp

Macros act on the program's representation as an abstract syntax tree, i.e. after parsing. Thus a macro expands to a sexp (Lisp's term for an abstract syntax tree), and its arguments are themselves sexps. Macros are expanded before variable resolution. Such macros are said to be unhygienic. Care must be taken not to mix up variables introduced by a macro from the variables of the program fragments.

(defmacro repeat (count func)
  `(loop for i from 1 to ,count
      do (apply ,func nil)))
(repeat 3 (lambda () (print "hello")))
(let ((i 5))
  (repeat 3 (lambda () (print i))))

The first call to repeat prints hello three times as expected. The second call to repeat does not print 5 three times, it prints 1 then 2 then 3, because the variable i from the macro shadows the variable i from the context of the macro call.

Scheme

Scheme is similar to Lisp, but with a few differences. One of the differences is that Scheme macros are hygienic. The Scheme equivalent of the program above prints hello three times then 5 three times.

(define-syntax repeat
  (syntax-rules ()
    ((repeat count func)
     (do ((i 1 (+ 1 i)))
         ((> i count))
       (func)))))
(repeat 3 (lambda () (display "hello") (newline)))
(let ((i 5))
  (repeat 3 (lambda () (display i) (newline))))

TeX

TeX expands macros in its mouth but defines them in its stomach. But don't set too much store by this: from a language design perspective, TeX is weird.


Calculating integral without quadratures Is there any other options of calculating integral instead of using quadratures? I know that also we can calculate spline function or use monte-carlo method but do you know something else?

Another approach is to use a computer algebra to compute the integral exactly, symbolically.

See also Wikipedia's article on symbolic integration.  Wikipedia also has a list of techniques and computational methods for integration.


proving $E_{TM}$ is undecidable using the halting language How to prove that:

$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)

using the language:

$H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$.

I tried to prove by contradiction that assuming $E_{TM}\in R$ I have a Turing machine which decides $E_{TM}$ and to construct with it a turing machine which decides $H_{halt}$ but I don't know how to do so.

Suppose that there is a Turing machine $T$ that decides $E_{TM}$.

Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^*$ that decides whether $(M,w) \in H_{halt}$. $M^*$ operates as follows:

It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is complete, accepts.
It simulates $T$ with input $M'$ to decide whether $M' \in E_{TM}$.
If $M' \in E_{TM}$ then $M'$ does not accept any input, which implies that $M$ cannot halt on input $w$. In this case $M^*$ rejects.
If $M' \in E_{TM}$ then $M'$ accepts at least one input (and hence all inputs), meaning that $M$ must halt on input $w$. In this case $M^*$ accepts.


How good are current AI researchers at simulating complex, first-person emotional states? I just read that IBM's Watson would have a hard time answering questions like "tell me about your first kiss." If you asked a modern, state-of-the-art chatbot questions like "tell me about a song that means a lot to you and why" or "tell me about a time when you felt vulnerable" would the chatbot be able to answer in ways that would fool non-experts into thinking that it was human? Are questions like this good candidates for the Turing test?

I am not asking a philosophical question about if it is POSSIBLE to generate an AI that could represent a complex internal emotional state. I am asking: given the state-of-the-art research in 2013: how close are current researchers to generating AI that could pass the Turing test?

Great Question!  One area to look into is Cognitive Architectures.  These are computer programs that solve AI problems by modeling how humans think and feel (emotion).  Here is a brief overview.

Prior to the mid-1980s the study of AI was concerned with creating general intelligent systems modeled after flexible human thinking (Fahlman, 2012).  Researchers in AI used findings in cognitive psychology to guide their work.

Currently, there has been a shift away from this approach.  The current trend in AI research is towards solving problems with “knowledge-lean” statistical methods which are data intensive and learn less efficiently than humans.  (Langley, 2012).  Thus, the AI field has shifted away from human-like models and toward "ideal" models.

However, a few AI researches still focus on creating intelligent systems modeled after the way humans think.  These researches work with Cognitive Architectures--Computer programs modeled after humans. The Office of Navel Research's Human Computer Interaction lab is actively working to create intelligent agents that can interact with humans.

I believe that the study of Cognitive Architectures is an interesting area of research for investigating how to create human-like systems.

Fahlman, S. E. (2012). Beyone Idiot-Savant AI. Advances in Cognitive Systems 1, 15-21.

Langley, P. (2012). Intelligent behavior in humans and machines. Advances in Cognitive Systems 2, 3-12.

Taatgen, N. A. (1999). Learning without limits. From Problem Solving towards a Unified Theory of Learning(dissertation). Groningen: Rijksuniversiteit Groningen.

http://www.onr.navy.mil/en/Science-Technology/Departments/Code-34/All-Programs/human-bioengineered-systems-341/Human-Robot-Interaction.aspx


prove that {$↔,⊕$} is incomplete set? How do i prove that Is {$↔,⊕$} not a complete set  ? I have no clue how to prove it .

The universal method to check whether a set of connectives is complete in this sense is Post's classes: there are 5 function classes such that a set of functions is complete iff it isn't a subset of any of these 5. One of the 5 is affine functions, as described in Yuval's answer; the rest are monotone, self-dual, 0-preserving, and 1-preserving functions.

It's pretty easy to show that all 5 classes are closed: any composition of functions from one of them will also belong to the same class. So if your set is a subset of a Post's class, it can't be complete. Showing the other direction is more complicated, but likely you'll learn the proof in the near future.


Can we use Convolutional Neural Network for dataset containing numeric data? I am working on a project of " Fraud detection using deep learning" . For that I have a dataset containing some numerical attributes . Now the task is to use CNN for the above purpose. Please guide me how can we do that as I have observed that it can be used only for image classification. I would appreciate if I get some research paper or blogs related to that.

Convolutional neural networks are just one of many models for classifing data. All models can be used for any data and they differ only in performance.

When you feed an image to the CNN (or any other model), the model does not “see” the image as you see it. It “sees” numbers that describe each pixel of an image and does all calculation using those numbers.
As was pointed in the comments; at the end, everything is effectively a number in the computer.

Your task asks you to use CNN because it will most likely perform best (in comparisson to other models) at this specific task. CNNs are very good at classifying objects that are not too similar, but have some shared features presented in a not too obvious way.

You can read about classification models here and I found a paper about detecting fraud with CNNs that might help you.


How was multiprogramming brought into computer languages I am going through the book operating system principles by Hansen . Hansen begins the third chapter on concurrent programming by discussing interleaving of the machine instructions of processes being run at the same time .

Then it begins with providing the language notation for multiprogramming  and writes the following program whose purpose is to copy  records from one sequence to another .

procedure copy (var f, g: sequence of T);
var s, t: T;
     completed: boolean;
begin
    if not empty(f)
    then
        begin
            completed:= false;
            get(s, f);
            repeat
                 t:= s;
                 cobegin
                       put(t, g);
                       if empty(f)
                       then
                            completed:= true
                       else
                            get(s, f);
                 coend
            until completed;
        end
 end

(If possible please tell me the name of the language ,was it Algol60 ?Anyways let's call it X )

All fine till here , a keyword or statement was introduced into the language X , which would perform multiprogramming. But I would like to know how was the language changed so as to incorporate this new keyword or function for multiprogramming . What changes were done to language X,owing to which X which was capable of supporting one execution at a time could now support more than one at a time ?

P.S : Hansen described about a single -user operating system called "Solo ".There he somehow means Pascal supports development of concurrent programs. The answer to the question in this post can be approximated by an answer to "what were the differences between languages which supported concurrent programs and those who didn't "?

I could have written "what are the differences" in the auxiliary question but I wanted to know how languages started having constructs for concurrent programming ,that's why I wrote "What were the differences".

If you're really interested in all that's needed, your best choice would be to look at the standardisation process of C++11 by the ISO Working Group on C++ (WG21). All the relevant papers are available online.

Keywords are not important at all. In fact, C++ defined just one new keyword (thread_local) and that's mostly for convenience.

What is important is the memory model. Programs work by altering state, which logically exists in memory. With multi-programming, there are concurrent changes to the state of a program. This requires a reasonably precise definition of said state. To make things more complex, you want a definition of state that is compatible not just with the abstract language definition, but which is also implementable on real hardware. That gets you into problems like registers and  caches (state outside ordinary memory), the exact details of which vary significantly between real hardware architectures.

A key insight here is the sequenced concept. Two C++ operations can be sequenced, which means they cannot operate at the same time. This means they are allowed to use the same data in memory without risk. A special kind of sequencing is sequenced before, which means one operations happens before the other. This means a write sequenced before a read guarantees that the read sees the value of the write.

With C++11, there are library calls defined which can guarantee such sequencing across different threads of execution.

The comments of @rcgldr suggest that function calls like WaitForSingleObject alone are sufficient, but this isn't actually the case. You need an associated memory model. That's why you have Win32 macro's like InterlockedIncrement - these macro's provide the mapping between the language memory model and the hardware memory model. There's no Read(DWORD*) macro, though - the language memory model is that aligned DWORD reads are atomic, and it's implicitly assumed that the compiler can efficiently map every read to atomic hardware instructions.


Finding maximum subgraph with vertices of degree at most k Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset
of its vertices.  An induced graph $G[U]$ is graph created from $G$ by
removing all vertices that are not part of the set $U$.
I want to find a polynomial time algorithm that has graph $G = (V, E)$
and integer $k$ as input and returns a maximum set $U \subseteq V$ with
largest size such that all vertices of $G[U]$ have degree at most $k$.
My idea with greedy algorithm that removes vertices with largest degree
or vertices connected with most vertices with degree greater than $k$
doesn't work.
Does anyone know how to solve this problem in polynomial time?

Let $G$ be any graph and let $k = 0$.
This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.
It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.


Full Adder vs. Half Adder I'm having some trouble figuring out where the "Carry in" value comes from in respects to a one bit full adder diagram.  I understand the below half adder,

but my question is: is the the output of the bottom-most AND gate in the bottom diagram equal to the output "C" in the top diagram (Assuming A and B are constant throughout) - Is Cin from the bottom diagram equal to C in the top diagram?

The C's are not the same, but your statement about the AND gate is right.

Unfortunately, the people who drew your full-adder decided to save space instead of maximizing readability. This image does a better job of showing the relationship between half adders and full adders, even though the circuit is identical to the one above:

If they'd just put the wire splitting points inside the grey boxes showing the half-adders instead of outside, they'd be perfect.

Here's a block diagram you can use to see the exact relationship between a half-adder and an adder.  It shows clearly something I find quite interesting about adders.  The 'or' at the end looks like it could swallow a carry if both half adders were to emit a carry bit at the same time.  It seems like we might need another half adder to resolve this, in a never ending chain.  However, if you run the truth tables for the half-adder, you find that it is impossible for both half-adders to carry at the same time.  Rejoice!


Soft question: program result verification Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your program is something like "factorize 15672965357291016", then it's a perfect candidate for this service, because you can very quickly verify that a result handed back to you is correct. But if your program is long and complicated, and you can't think of a quick way to verify that a given input/output pair is correct, then you're stuck with running the program on your own machine to verify the results, which defeats the purpose.

One solution would be to use the blockchain and have a lot of people verify that some given input/output pair is correct--then you only accept the result as true when whatever block it's on has enough confirmations. The problem with this is that it could really slow down the network if your program is resource-intensive.

What would be nice to have is a programming language where a given program P, an input to it I, and a supposed output O, can be verified quickly (i.e. P(I) == O). That way, making confirmations would be fast, and the whole network would speed up.

I don't think this can be done in general because you could use it to solve the halting problem. If you have some function V(P, I, O), which verifies that P(I) == O, then running V(P, I, halts) would check that P halts on input I.

However, the fact that V does exist for every problem in NP makes me think that there has got to be some middleground, where you could make a really restricted language for which V always exists, and it can easily be determined from the structure of P (a trivial implementation is just V(P, I, O) = P(I) == O). I'm not really sure what my question is, but is this an existing problem? What search terms should I use to learn more about this?

I found out that this is called Verifiable computing:

  Verifiable computing (or verified computation or verified computing)
  is enabling a computer to offload the computation of some function, to
  other perhaps untrusted clients, while maintaining verifiable results.


Memory needed for computational graph Suppose we have a set of equations like this

p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f()

It can be represented by computational graph below

If each intermediate value takes 1 unit of memory, you need at least 4 units to compute p7 without any duplicate computation.

Is there an algorithm for estimating memory needed in this setting for a general DAG?

I found a paper called "Adjoint Dataflow Analysis" for estimating this for restricted set of graphs, but it feels like this ought to be a problem that is covered more generally in graph theory.

Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled Inapproximability of treewidth, one-shot pebbling, and related layout problems (J. Artificial Intelligence Res. 49 (2014), 569–600), show that it is (probably) hard to compute the optimal cost (which corresponds to your memory).


Functions with small support have small circuits I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $f\colon \{0,1\}^n→\{0,1\}$ has a support of size $k$, then it can be decided by a circuit of size $O(nk)$.
I understand that for any binary functions of this sort, the maximal size of the circuit is $O(n2^n)$, and I have a feeling that this could be useful for proving the statement, but I am not exactly sure where to proceed from there. Furthermore, I also understand that the "support" referred to in this question is actually the language defined by the function, but again, this leads me nowhere.
Any help on this would be much appreciated.

Consider the AND function:
$$
x_1 \land \cdots \land x_n.
$$
Its support size is $1$, and its circuit complexity is $O(n)$. By negating inputs, you can get a circuit for any function whose support size is $1$. By ORing together $k$ such functions, you can get a circuit of size $O(kn)$ for any function whose support size is $k$.


How to characterize equivalence classes induced by Myhill-Nerode theorem? Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$,  where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes induced by the relation on $\{0,1\}^\ast$ $$x \thicksim_{L} y \iff \forall z\in \{0,1\}^\ast \left(xz \in L \iff yz \in L\right)$$
The reference I have already shows that the (obviously, infinitely many) classes are of the form $C_k=\lbrace w\in \lbrace 0,1 \rbrace ^{\ast} : N_0(w)-N_1(w)=k  \rbrace $ and clearly $\bigcup_{k\in\Bbb Z } C_k = \{0,1\}^\ast $, but I have no idea how could I have deduced this correct characterization myself.

When given a regular language, I find it easier to construct a suitable minimal DFA and then "back engineer" each state to a useful characterization of its class. But for a non-regular language, I'm having a really hard time working with the relation definition. In this particular example, I don't understand how it applies to the classes $C_k$ above.

So for me there are two underlying questions here:

If given the equivalence classes, how can one prove that they are indeed induced from the relation?
However, if they are not given, is there a systematic\algorithmic approach to characterize all of these classes for a given language? mainly, a non-regular one.

To prove that the classes $C_k$ are equivalence classes for the Myhill-Nerode relation we need to show

For any strings $x,y \in C_k$ there does not exist a distinguishing extension of $x$ and $y$. This proves $C_k \subseteq [w]$.
For any $x \in C_j$ and $y \in C_k$ there does exist a distinguishing extension. Since every string $\omega$ belongs to some $C_k$ this shows that the $C_k$ form a partition of $\Sigma^*$.

These together show that the $C_k$ are exactly the equivalence classes under $\sim_L$.

Let $N(w)$ denote $N_0(x) - N_1(x)$.

For the first part, note that $x, y \in C_k \implies N(x) = N(y)$. Then for any extension $r$, we have that

$N(xr) = N(x) + N(r) = N(y) + N(r) = N(yr)$

and so $xr \in L \iff yr\in L$. Thus $r$ cannot distinguish $x$ and $y$.

For the second part, we have that $N(x) \neq N(y)$.
Assume WLOG $N(x) > 0$.

Then the extension $1^{N(x)}$ distinguishes $x$ and $y$ since $$N(x1^{N(x)}) = N(x) - N(x) = 0 \implies x1^{N(x)} \in L$$
while
$$N(y1^{N(x)}) = N(y) - N(x) \neq 0 \implies y1^{N(x)} \notin L$$

Intuitively, we interpret the equivalence classes as "states" of some machine for deciding the language. This is literally true in the case of regular $L$, but even in this infinite case we can interpret "state" to mean $k$. Once two strings are in the same state, there is no going back: there is no further information that we can feed to the machine and cause it to diverge.

In this particular case, we look at the definition of the language and note that the only information that we care about is $N(w)$. Since this information in some sense captures all we need to know about a string, it makes sense that strings that are identical under this classification can never be distinguished by the language.

There is certainly no algorithmic way of classifying $\sim_L$ in full generality since even deciding whether two strings belong to the same class is undecidable clearly for undecidable languages $L$.

In the restricted case of context free languages I don't know of any generic canonical characterization. There are some relevant discussions here and here


Shouldn't the "even parity" function map 1101 to 0? From the book Computer organization and design by Patterson&Hennessy:

  Parity is a function in which the output depends on the number of 1s in in the input. For an even parity function, the output is 1 if the input has an even number of ones. Suppose a ROM is used to implement an even parity function with a 4-bit input. Then the contents of the ROM is
  $$\text{Address} \ 0 : \ 0 \\ \text{Address} \ 1: \ 1 \\ \text{Address} \ 2 : \ 0 \\ \text{Address} \ 3 : \ 1 \\ \vdots \\ \text{Address} \ 13 : \ 1 \\ \text{Address} \ 14 : \ 0 \\ \text{Address} \ 15 : \ 1$$

As per my understanding, ROM which implements the even parity function should store 0 at both the Address 1 and the Address 2, 1 at the Address 3, ... 0 at both the Address 13 and 14, then 1 at the Address 15, for the Address $k$ to represent the map-value of $(k)_{\text{base}2}$.

According to this the concept defined above is not clear enough, Can someone clarify the doubt?

In this context, implementing something as a ROM just means a look-up table. If you want to know the parity of $x$, you put the binary coding of $x$ on the ROM's address wires and the value you read out is the value stored at that memory location within the ROM, which will be either 0 or 1.

And, yes, the contents of the ROM that you've quoted are wrong: they seem to be implementing parity in the sense that the output is 1 if, and only if, the input is an odd number, instead of implementing the even parity function.


Why can't we solve the Halting Problem by using Artificial Intelligence? Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a warning saying that my code was going to result in an infinite loop.

My question is, why can't this problem, be solved by using an "Intelligent" program to determine if another program will halt or end in an infinite loop? This hypothetical program could look for repetitive structures, conditions, etc and even predict under which circumstances (possible inputs) will halt, loop infinitely or end. Maybe like looking for the "acceptable range", like the domain of a mathematical function.

The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics.  It is an historically important example of an undecidable problem.

An artificial (or human) intelligence can certainly look for and find many sorts of different infinite loops in real programs.  And the halting problem doesn't say that such a thing is impossible or even very hard.

What the halting problem says is that given any program $I$ ("I" for "intelligent"), (say a really complicated AI program written in Netbeans) that looks for infinite loops we can produce a program that $I$ can't analyze.  The way we do this is a clever technique called diagonalization, which is described in the question @Raphael linked: How to show that a function is not computable?, and also in Why, really, is the Halting Problem so important?

The halting problem is similar to the Liar's Paradox in that it demonstrates the limits of mathematical and logical definitions of "truth", and "provability".  The Liar's Paradox is: suppose I say "this statement is a lie."  Is that statement true or false?  If it is true then it must be a lie, so must be false.  If it is false, then it is not a lie, so must be true.  Writing a complicated artificial intelligence (or relying on a really smart person) won't make the question about whether I lied or not any more meaningful.


Why is the Kleene star operator also called the Kleene 'closure' operator? I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept.

I don't understand why the Kleene star is also called the Kleene closure.
Is it related to closures in programming, a function with bound non-local variables?

... on reflection, maybe it is because it allows an open ended set to be written in a closed expression form?

... well in good old rubber-duck-explaining fashion, I'm now guessing that is it, but would still welcome an authoritative answer.

A set is closed under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a natural number.

The closure of a set $S$ under some operator is the smallest set containing $S$ that is closed under the operator. For example, the closure of the natural numbers under subtraction is the integers; the closure of the natural numbers under addition is just the natural numbers, since the set is already closed.

So, "Kleene closure" is not an alternative name for "Kleene star".  The Kleene star is the operator; the Kleene closure of a set is the closure of that set under the operator.


What does flow denotes in the minimum-cost network? What is flow in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to send d amount of flow from source to terminal node so that the total cost is minimized. My question is: what does flow denotes?

Flow is an abstraction of how much "stuff" you want to move through the network. Exactly what the stuff is depends on what you're modelling with the network - water pipes, transport networks, computer networks, etc.

The problem (or something close to it) can also be used to model other problems, in which case flow could be all kinds of things.


Is the intersection of infinitely many recursive sets recursive? Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable?
I know the union need not be recursive, because deciding if an element is in the set $U_i$ is the same as deciding the Halting Problem since you for each element you'll have to decide if the function that computes if $x \in U_i$ for some $i$  will terminate.

For each $i\in \mathbb{N}$, take $S_i = \mathbb{N}\setminus \{i\}$. You can now build any set you want as $X = \bigcap_{i\notin X}S_i$.

Similarly, an easier proof that a union of recursive sets can be anything at all is to let $T_i=\{i\}$ and now any set $X$ is $X = \bigcup_{i\in X}T_i$.


Algorithm for MST connecting a subgraph I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph.
However, this is a problem I have to deal with:

Given a weighted graph $G=\{V,E\}$ and one of its subgraph $H$. Find a subset $E'$ of $E$ such that

If we clear out every edge outside of $E'$, $H$ is still connected.

The total weight of $E'$ is lowest possible.

Note that $E'$ may contain edges that don't join two vertices in $H$, and any two vertices in $H$ may not necessarily be joined by an edge.

It is little different from the MST problem.
Firstly I thought that I only have to run MST algorithm in $H$, but I later found that this only work if any two vertices of $H$ is joined by an edge, not a series of edges.
How can I solve this problem? Thanks in advance.

This is the Steiner Tree problem, specifically the Steiner Tree problem in graphs: the vertices in $H$ are the terminals.  Unfortunately it's NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

If $E$ describes a metric, then the minimum spanning tree on $H$ gives a 2-approximation.


Use of Myhill-Nerode Theorem to prove minimal number of states I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\{a, b}\}$ and $C_k=Σ^*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C_k$ with fewer than $2^k$ states.

You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.