Description and semantics of program graphs

Definitions

From "Principle of Model Checking" By Joost-Pieter Katoen and Christel baier:

  A program graph over a set Var of typed variables is a tuple $(Loc, Act, >Effect, \rightarrow, Loc_0, g_0)$ where:

  $Loc$ is a set of locations
  $Effect: Act \times Eval(Var) \to Eval(Var)$ is the effect function
  $\rightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the condition transition relation
  $Loc_0 \subseteq Loc$ is a set of initial locations
  $g_0 \in Cond(Var)$ is the initial condition

It is further noted that:

  $Eval(Var)$
  denote the set of (variable) evaluations that assign values to variables

  $Cond(Var)$ is the
  set of Boolean conditions over Var

Given these definitions, your definitions of $Loc$, $Act$ and $Effect$ are correct

Transitions

So, according to these definition the conditional transition relation must be:

$\rightarrow =\{(k1,α1, ? ,k2),(k2,β1, ?, k3),(k3,γ1, ?, k1)\}$

where each questionmark is a tautology, ie something always true (as there are no conditions in the figure). As the authors note,

  If the guard is a tautology ... we simply write $(l, \alpha, l') \in \rightarrow$.

So in conclusion your definition of $\rightarrow$ is correct

Furthermore, $Cond(Var)$ must consist of tautologies.

Initial Condition

To me it seems that there are no given initial conditions on the variables $x,y$ so $g_0$ must simply be a tautology as $g_0 \in Cond(Var)$. It seems undefined what specific tautology $g_0$ must be, but any tautology will do, if you apply the Structural Operational Semantics given in the book, as any location satisfies any tautology.

Execution and Traces

Both concepts are defined in the context of Transition Systems.

Executions:

  Executions  are alternating sequences consisting of states
  and actions

And traces:

  Thus, rather
  than having an execution of the form $s_0
\rightarrow^{a_0} s_1
\rightarrow^{a_1} s2$ . . . we consider sequences of the
  form $L(s_0)L(s_1)L(s_2)$ . . . that register the (set of) atomic propositions that are valid along
  the execution. Such sequences are called traces.

For reasoning about executions and traces you thus need to look at the transition system induced from the program graph (by the structural operational semantics given in the book).


Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1

Hint:
$$\begin{align*}
T(n) &= 2T(n-1) + n \\
&= 2^2 T(n-2) + (2n + n) - 2 \\
&= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\
&= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\
&= \cdots
\end{align*}$$

If you are familiar with the required methods, you can also solve it using generating functions (and, e.g., techniques from here or chapter 7 of "Concrete Mathematics" by Graham, Knuth, et al.).


Time complexity of a problem in probabilistic inference on a Bayesian network

Your problem is equivalent to:

Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$
Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $\sum_i a_i x_i \ge t$.

I think this problem is #P-complete, so you shouldn't expect any polynomial-time algorithm for computing it exactly.

Let me explain why.
Let $\ell(x,y)$ denote the likelihood of the states $x,y$, $\ell(x) = \ell(x,1^n)$, and $L(x) = \log \ell(x)$ its log-likelihood.  Then $L(x)$ has the form

$$L(x) = -n \log 2 + \sum_i \log p_{i,x_i}.$$

An assignment $x,1^n$ satisfies $E$ iff $L(x) \ge \log \epsilon$.  Note that

$$\log p_{i,x_i} = \log p_{i,0} + x_i (\log p_{i,1} - \log p_{i,0}).$$

Letting $a_i = \log p_{i,1} - \log p_{i,0}$, we have

$$\sum_i \log p_{i,x_i} = \sum_i \log p_{i,0} + \sum_i a_i x_i.$$

If we now let $t = \log \epsilon + n \log 2 - \sum_i \log p_{i,0}$, we find that $x$ satisfies $E$ iff $\sum_i a_i x_i \ge t$.  So, given $t$, we want to compute the probability that a random chosen $x$ satisfies $\sum_i a_i x_i \ge t$.  This is equivalent to counting the number of $x$'s that satisfy $\sum_i a_i x_i \ge t$.

According to https://cstheory.stackexchange.com/q/19758/5038, this problem is #P-complete, so you shouldn't expect to find any polynomial time algorithm to compute the answer exactly.

However, there are techniques for approximating it: for instance, you could use algorithms for estimating the number of lattice points in a convex polytope (see, e.g., https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf) or computing them exactly in super-polynomial time (https://cstheory.stackexchange.com/q/22280/5038, https://cstheory.stackexchange.com/a/6464/5038).


Hint: Consider a DFA for $L$, and some word $w$. Suppose that upon reading $w$, the DFA reaches some state $q$. Is knowing $q$ enough for deciding whether $w \in OP(L)$?


Can I notate time complexity depending on the result of an algorithm?

You can express algorithms costs in whichever parameters you desire, so long as you define them. The parameters don't even have to be known given the input; that gives your bound limited use, but well.

Warning: Landau bounds are asymptotic, that is they only hold meaning when you let the parameter(s) go towards infinity. That is you can not really use parameters that can not be arbitrarily large.

Warning: It's unlikely that your cost is independent of the input, which is what your bounds seems to suggest. You probably made a mistake.


Divide grid so that each box has only one object

I initially missed your remark about overlapping rectangles -- as orlp said in a comment, there's obviously no solution in those cases.  But I had already typed the rest of this answer out, assuming the input has no overlapping rectangles, so I'll leave it here in case it's helpful.

It sounds like your current method repeatedly looks for a guillotine cut: That is, a cut that goes all the way from top to bottom, or all the way from left to right.

Unfortunately, even if you split subproblems at as many places as possible within a single $O(n \log n)$-time scan along one dimension, this can result in $O(n^2 \log n)$ time overall, like for instances such as the following where each scan only succeeds in peeling off a single rectangle:

XXXXX

X   X
X X X
X
X XXX

But the real problem is that some instances can't be solved this way at all, even when no overlapping rectangles are involved.  For example:

XXX X
    X
X   X
X
X XXX


Minimal DFA with more states than its equivalent NFA

Consider the language $(0+1)^*0(0+1)^{n-1}$ over the alphabet $\{0,1,2\}$. It is accepted by an NFA having $n+1$ states, and its minimal DFA contains $2^n+1$ states.


I would like to point that determining the color temperature of the image is still an open problem.
If you convert the RGB image to CIE XYZ Tristimulus color then calculate normalized chromacity to get the temperature, it works for pixel, kinda, it is a lot of effort to simply feed it a mean. Indeed it cannot work. The average over all pixels gives artificial color (if you do it over RGB it is not even chromacity preserving).
Whenever it is possible use CIE RGB (it is physical based color space, using the actual human sensitivity to colors) or some color space naturaly separating hue and lightness like HSL.

perform image segmentation or alternatively perform edge detection and subtract edges from reduced image
take from results only big enough blobs - this is arbitrary and depends on the image resolution, but more than 50 pixels is good default value. Blobs are segments of the image with small inner variance - they pixels are similar to each other, not varying too much in intensity and chromacity.
Calculate the average of blobs in the HSL space. Take into account the area and assign greater weights to bigger blobs (if blob spans over 200px it will be better perceived than 4x50px).
take into account the placement of the blob (calculate how far it is from the center)
the the center is weight 1, slightly decreases to suddenly drop. This weights reflect what is better exposed (assuming that there are no important features at the corners, but it is safe to assume that the main focal points are in the center).
take this weighted areas (blobs) average them in HSL space and now calculate color temperature - sorry for obvious link but the equations are ok.
This method performs quite good experimentaly, some parameters should be adjusted per type of image, sorry I do not remember exact parameterts (proven to give good results experimentally).

Unfortunately your task must be heavily modified to reflect how people perceive images, how they neglect the color of edges (which give quite big boost RGB-wise). What they focus at and how they remember. By the way, the reception of the image tone is a bit skewed by the represented objects - the attraction makes the tone warmer while repulsion makes it colder.
So please take a look at awesome articles:

Kraft, T. W., Schneeweis, D. M., & Schnapf, J. L. (1993). Visual transduction in human rod photoreceptors. The Journal of Physiology, 464, 747–765.
Ho, H.-N., Iwai, D., Yoshikawa, Y., Watanabe, J., & Nishida, S. (2014). Combining colour and temperature: A blue object is more likely to be judged as warm than a red object. Scientific Reports, 4, 5527. http://doi.org/10.1038/srep05527
Evaluating color texture descriptors under large
variations of controlled lighting conditions


Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence

Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space.

Initialize a hashtable of counts $C$ to all zeros.  Then, repeat $t$ times: randomly pick $i,j$, compute $b_j-a_i$, and increment $C[b_j-a_i]$.  Finally, sort $C$ by counts, from largest count to smallest; then for each of the largest few values of $C[k']$, try $k'$ as your guess at $k$, and verify each guess.

Notice that in each iteration, the probability of incrementing $C[k]$ is at least $1/m$; whereas if $l\ne k$, we expect $C[l]$ to be incremented much more rarely (assuming the integers in the arrays are random and large enough).  Thus, after $t$ iterations, we expect $\mathbb{E}[C[k]] \ge t/m$ but $\mathbb{E}[C[l]] \ll t/m$.  So, once $t$ is large enough, $C[k]$ should be larger than every other entry in $C$.

How large does $t$ need to be?  I expect that $t = O(m \log m)$ should suffice, based on a central limit theorem approximation for the counts $C[l]$, assuming we are willing to accept a small probability of error (which can be driven exponentially small).  The constant factor hidden by the big-O notation might be non-trivial.

This is only a heuristic, and there will certainly be inputs where it fails.


What class this graph connectivity problem belong to

$G$ has $2^n$ vertices, and for any two vertices $v_i,v_j$ we can check whether $(v_i,v_j)\in E$ in polynomial time (since circuit value problem is in P). By executing DFS on $G$ from any vertex you can find out whether $G$ is strongly connected in $O(|V|+|E|)=O\left(2^{2n}\right)$ time, which puts your problem in $E$, as the circuit's description is of size $\Omega(n)$.
Your problem is PSPACE-hard. Given a machine $M$ which uses $\le n^c$ space and input $x$, denote by $G_x$ its computation graph, i.e. the graph whose vertices are all possible configurations using $\le |x|^c$ cells and $(C_i,C_j)\in E_{G_x}$ iff $C_i$ is followed by $C_j$ in the computation of $M$. Now adjust $G_x$ by adding edges from every vertex to $C_x$, the initial configuration of $M$ on input $x$, and from the accepting configuration $C_{acc}$ (assume without loss of generality that it's unique) to all other vertices. Clearly this new graph $G_x'$ is strongly connected iff there is a path from the from $C_x$ to $C_{acc}$ in $G_x$. Given $M,x$ you can construct in polynomial time a circuit $C_{G_x'}$ that takes two vertices $C_i,C_j$ of $G_x'$ and outputs 1 iff there is an edge from $C_i$ to $C_j$ (checking whether one configuration is immediately followed by another is easy). I leave it to you to complete the details here.


Every finite language is regular. The easiest way to prove it is to build the regular expression $w_1+w_2+\dots+w_n$ where $\{w_1,\dots,w_n\}$ is you finite language.

You can also build an automaton as you said. May be build a separate one  for each word and the do a finite union is the easiest.


Proving that a language of Turing machine descriptions is/is not Turing recognizable

The problem with your proposed algorithm is where you say

  ... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is not in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ is in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that  $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..


Just for convenience, I'll write out the code first.

for(int i = 0; i <= 4 * n;  i = i + 4) {
    for(int j = 0; j <= i + 1; j++) {
        meth();
    }
}

and meth() runs in constant time $O(1)$.

Right away we can use that the outer loop runs $n+1$ times (assuming $n$ is a non-negative integer) since we are doing $0$ to $4n$ inclusive in increments of 4. The inner loop runs $i+2$ times for each iteration of the outer loop since it goes from 0 to $i+1$ inclusive in increments of 1. So we can write the total number of times the inner loop runs as

$$\sum_{i=0}^{n} (4i+2) = \sum_{i=0}^n4i + \sum_{i=0}^n2 = 4\sum_{i=0}^ni + 2(n+1) = 4\frac{n(n+1)}{2}+2(n+1) = 2(n+1)^2$$

In the arithmetic, we first break up the sum into two parts. Then we factor out the 4 in the first term and use that that we added 2 $(n+1)$ times, aka 2(n+1). Next, we use the formula $\sum_{i=0}^n i = \frac{n(n+1)}{2}$ and then finally simplify.


Your method is reasonable.  There are other possibilities as well.

Randomized algorithm: locality-sensitive hashing

Here is a randomized algorithm that finds all matches with high probability (probability $1-\epsilon$ where $\epsilon$ is exponentially small, but not zero).  It will probably be more efficient.

Build 100 tables.  Each table is constructed as follows: Randomly pick a subset of 8 positions (out of the 64 possible positions).  Now a string is hashed by keeping only the 8 characters from those 8 positions, and the string is stored in the hashtable keyed on that hash.  For instance, if the positions associated with a particular table are $i_1,i_2,\dots,i_8$, then the string $S$ is hashed by hashing $S[i_1],S[i_2],\dots,S[i_8]$ and using that hash value as the key to store $S$ in the table.  Each table has a different and randomly generated subset of positions.

Store each of the millions strings in all 100 tables.  When you get a query string $Q$, look it up in each of the 100 tables to find all possible matches, take the union of those possible matches, and calculate the Hamming distance between $Q$ and each possible match.

This is very similar to your method, but each "part" is longer (8 characters instead of 4 characters), so there will probably be many fewer "false matches" from the hashtable.

There is no guarantee that this approach will find all valid matches, but most likely it will.  The probability that a valid match is not found is

$$(1-(49/64)^8)^{100} \approx 0.0000035,$$

so missing a match is unlikely.  You can tune the probability of a missed match by adjusting the number of tables, and you can adjust the parameters ($8,100$) to find the setting that gives you the best possible performance.

This is effectively a form of locality-sensitive hashing (LSH).  There may be other schemes worth investigating.  You could also look at MinHash.

Trie

Another approach is to store the dictionary of millions of strings in a trie data structure.  Given a query string $Q$, you can start traversing the trie, doing a recursive breadth-first search  to explore all paths that are at distance at most 15 from $Q$.  For many paths, you'll be able to immediately terminate the search.


Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?

Graph dynamical systems is a general term for systems where each vertex of a graph carries a state, and the system evolves in time so that the next state of a vertex only depends on the states in its neighborhood (possibly in a nondeterministic way). Boolean networks are a special case where the graph is finite and each state is either $0$ or $1$. Boolean networks are used e.g. as models of gene expression in cells, and a lot of practical and theoretical research exists on them.


Find perfect matching faster than MCM, in graph that has perfect matching?

Hopcroft-Karp isn't necessarily optimal, and you can already find asymptotically faster algorithms in the relevant Wikipedia pages: https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions.  Note that you can use any network flow algorithm to find a perfect matching.

For instance, you can achieve $O(n^{2.373})$ running time using fast matrix multiplication, though this is only a theoretical result; in practice it's slower.  However, this is already enough to demonstrate that there's no way we're going to prove that you can't do better than Hopcroft-Karp (because you can).  For sparse graphs ($|E|=O(n)$), Madry's algorithm achieves $O(n^{1.43})$ running time.  Neither of these use/exploit the fact that the graph already contains a perfect matching.


The statement is false. Consider the NFA on the alphabet $\{a\}$ having two states: an initial state $q_0$, and the unique final state $q_f$. The transition function is given by $\delta(q_0,a) = \{q_0\}$ and $\delta(q_f,a) = \{q_f\}$. For every word $w_2$ it is the case that $\delta(q_f,w_2) \cap F = \emptyset$, yet $w_1 w_2 \notin L(A)$ for all $w_1$.


Algorithm for weighted elliptic curve fit

Fitting an ellipse to a set of points is sometimes known as elliptical regression.  Doing a Google search on that phrase will find you many resources on the subject (e.g., 1, 2, etc.; I can't vouch for any of these).

Let's focus first on the case where you ignore outliers.  Then, there are two methods.  One way is to use least-squares fitting and directly compute a best fit (e.g., the method of Fitzgibbon et al).  An alternative method is to use iterative methods, where you write an objective function $\Phi(p)$ that captures how well the ellipse parameters $p$ fit the data and then use gradient descent, the Gauss-Newton method, or some other method of optimization.  See, e.g., the Levenberg-Marquardt algorithm.

You'll also need to decide on objective function, or equivalently, on the error model.  Standard methods typically measure the "goodness of fit" by measuring the vertical error: for each point, you measure the length of the vertical line from that point to the fitted ellipse, and that is the error associated with that point; then, you sum up the squares of those errors.  This is the right model if you think that your measurement of the $x$-coordinate is perfect and your measurement of the $y$-coordinate is corrupted by random errors.  However, in practice that's probably often not the case; rather, we probably think that the location of the point has been shifted from the ellipse in a random direction.  In that case, a better measure of "goodness of fit" would be to measure the distance from the point to the ellipse (in whatever direction makes that distance minimized; not restricting only to a vertical distance), and then take the sum of those squared distances.  This does require you to use iterative methods to minimize this objective function.  A similar issue arises in linear regression (see here) and it might be easier to understand in that scenario first.

OK, that should handle the case where you have no outliers.  What if you do have outliers?  Then there are multiple reasonable approaches.  One is to use an objective function that is robust to outliers: for instance, use the median of the squared distances rather than the sum of squared distances, or use the Huber loss function instead of the square.  The downside of these methods is that they make it harder to compute the gradient and thus harder to apply iterative methods (and the non-iterative methods probably can't be used at all).

An alternative way to deal with outliers is to use RANSAC, which is a general procedure for dealing with outliers.  An overview is that you pick a small random sample of the points, hope that the random sample has no outliers, tentatively fit an ellipse to the sample, use the tentative ellipse to classify the points into inliers vs outliers based on how far they are from the tentative ellipse, then fit a new ellipse to all the inliers; and repeat 1000 times with 1000 different random samples, taking the best solution found.  This is a generic method for dealing with outliers that has the advantage of being usable with existing non-robust methods for elliptical regression.  You don't need to modify the loss function, objective function, or algorithm at all, since you are only applying elliptical regression to inliers, so you can use any method for elliptical regression without needing it to be robust to outliers.


A language $L$ is semidecidable if there is a Turing machine that on input $x$, halts if $x \in L$, and doesn't halt if $x \notin L$. It is decidable if there is a Turing machine that on input $x$, halts at an accepting state if $x \in L$, and halts at a rejecting state if $x \notin L$. It's not hard to check that every decidable language is also semidecidable.

A logical system is semidecidable (decidable) if the language of all theorems in the system is semidecidable (decidable).

Being semidecidable is an upper bound on the complexity of a language. Being NP-hard is a lower bound on the complexity of a language. If all you know about a language is that it is semidecidable, you cannot deduce that it is NP-hard, just as you cannot conclude that $x \geq 0$ from the inequality $x \leq 1$.

The halting problem is $\Sigma_1^0$-complete, which means that it is semidecidable (an upper bound), and moreover, every semidecidable language can be reduced to it using a computable reduction (a lower bound). To be equivalent to the halting problem, you need both an upper bound on your language and a lower bound on your language. The language of theorems in a logical system is guaranteed (by definition) to be semidecidable, but it could also be decidable, in which case it is definitely not equivalent to the halting problem.

Finally, you don't explain what you mean by First Order Logic, but assuming that it can express propositional tautologies, then the corresponding language of theorems is definitely NP-hard, by reduction from SAT. In fact, the language of true quantified Boolean formulas, known as TQBF, is known to be PSPACE-complete.


What is the meaning of the mutation rate in genetic algorithms?

In general each child is mutated separately, only once at 'birth', and not during their 'adulthood'. Depending on how individuals are specified, '5% mutation' might mean that a random 5% of the bits in the individual's source code are flipped.


Math behind leetcode problem 47 permutations II

(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.


What does the number of bit of microprocessor mean?

How many bits wide its registers are: usually, its data registers (the ones which can load and store data and perform logical and arithmetical functions).

The 8086 has 16-bit data and address registers, and a 16-bit data path to external memory.

The 8088 has 16-bit data and address registers, but only an 8-bit data path to external memory. Because it is internally identical to the 8086, it is also considered to be a 16-bit processor.

The 8085 has 8-bit data registers and 16-bit address registers. The address registers (apart from SP) are made up of pairs of 8-bit data registers. The fact that it is possible to add one address register to another isn't enough to make the processor considered to be "16-bit".


Efficient Algorithms for Destroyed Document Reconstruction

Your problem is NP-Complete, even for strips (n strips yields (2n)!)  used, so people use heuristics, transforms like Hough and morphological filters (to match continuity of text, but this heavily increases complexity for matching) or any kind of genetic / NN search, Ants Colony Optimization.

For summary of consecutive steps and various algorithm I recommend An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms.

The problem itself may end up in nasty cases, when document is not fully sharp (blurred, printed with low resolution) and strips width is small and cut by physical cutter with dulled edges, because standard merging methods like panorama photo sticher gets lost and yield improper results. This is due to lost information by missing small strips, otherwise if you have full digital image cut into pieces, it is as hard as Jigsaw puzzle, non-digital image falls into approximate search.

To make algorithm automatic another problem is pieces feeding, rarely you can give axis aligned strips, so to start process it is nice to input all stripes as one picture with pieces lay by hand, this imposes another problem (this one is easy) to detect blobs and rotate them.

By special shredder instead of stripes yield very small rectangles. For comparison, P-1 class shredder gives stripes 6-12mm wide of any length (about 1800mm^2), class P-7 gives rectangles with area less than 5mm^2. When you get rectangles instead of stripes, problem yields (4n)! permutations, assuming one one-sided document, if there are lots of shreds from unrelated documents (no pictures, text only) in one bag, problem is not really tractable.


Difference in having * inside vs outside of brackets for NFA

Let "$\rightarrow$" stand for "denotes". Then we have

$0\cup 1\rightarrow \{0, 1\}$, so
$(0\cup 1)^*\rightarrow \{\epsilon, 0, 1, 00, 01, 10, 11, 000,\dotsc\}$, i.e., all words that can be made by concatenating any number of $0$s and $1$s.
$0^*\rightarrow \{\epsilon, 0, 00, 000, 0000, \dotsc\}$, all words that can be made of just $0$s.
$1^*\rightarrow \{\epsilon, 1, 11, 111, 1111, \dotsc\}$, all words that can be made of just $1$s, so
$(0^*\cup 1^*)$, the union of the two sets above
$\rightarrow \{\epsilon, 0, 1, 00, 11, 000, 111, 0000, 1111, \dotsc\}$.

So in particular $(0^*\cup 1^*)$ will never contain strings with both $0$s and $1$s, whereas $(0\cup1)^*$ will contain all of $(0^*\cup1^*)$ along with lots of other words.


Why $o(\log n)$ bits instead of $O(\log n)$ bits needed for succinct data structure?

Note that $\lceil \log(2^n) \rceil = n$.

An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure).  An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine.

An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure).  Similarly, an algorithm that uses $1.01n$ bits would not be fine.

This is just what the definition says.  You could imagine some other definition, but that's what the standard definition of "succinct data structure" is saying.  It is saying that you can use a little bit more space than required by the information-theoretic lower bound, but not too much -- not a multiplicative factor.


Tag, index and offset of associative cache

Before getting to your question, let's recall what set-associativity means, and how one can figure out how to split the address into tag, index and offset. If you prefer to learn by examples, jump to after the fold.

Cache

A cache is just a faster, yet smaller, memory.
It might take a long time to access data in the main memory, but it is very fast to access the cache. So we better save data in our small and fast cache rather than in our big and slow main memory.
However, the cache is small, so it cannot hold the entire data of the main memory.
Instead, it will hold some part of the data stored in the main memory.

Which part of the data?
We don’t know in advance - this would depend on the actual usage of the data (i.e., it depends on the software we run).
In general we would like to be able to put in the cache any part of the main memory,
and we would need to figure out where to put each memory-address in the cache, and how to identify which memory-address lies in each cache-cell. The index and tag bits will do just that (see below for a better explanation). But before we get there, let’s make things a bit more complex: we stop discussing addresses of the main memory and start discussing memory blocks.

Blocks and offsets

Many times, when we access the memory, we access consecutive addresses. That is, many times if we access address 0, then shortly after we will access address 1 (and 2, and 3....). So maybe when we first access address 0, and put it in the cache, it will be smart to bring along addresses 1 and 2 and 3 [...] and put them in the cache as well.
This "chunk" of information that we bring into the cache is called a block. The cache always hold blocks of consecutive memory addresses. It is possible that each block in the cache contains the data of only 1 memory-address. It is possible that a block contains the data of 2 (consecutive) addresses. Maybe it contains 128 consecutive addresses... Each cache has its own parameters.

Since the cache "knows" only blocks rather than specific addresses, we need a way to distinguish different addresses within a specific block. For this we have offset bits.
If a block contains $x$ addresses of the memory, then any $x$ consecutive addresses constitute a single block.
Given a specific address in the memory, we can look at its bits representation: the MSB will be the "block number" and the LSB would be the offset inside the block. That is, to get the block number out of a specific address we can simply ignore the last $\log_2 x$ bits (LSB), and the rest will indicate the number of the block associated with these $x$ addresses. The lower $\log_2 x$ bits are called offset bits and they are used to tell the cache which address within the block we wish to access.

Set Associativity

Now to the more interesting part of caching. Where does each block go within the cache? This seems like a stupid question: why don't any block go anywhere in the cache. The answer is that if any block can be anywhere, then it may be very difficult to locate that block when we need it -- we will have to search through the entire cache for that block, and this search may be slow/expensive.

The solution is that the cache is split into “sets”. Each memory block is assigned to one specific set. This assignment never changes.
Whenever you access that memory block: if it is in the cache it will be in that assigned set; if it is not in that assigned set, it is not in the cache and you need to bring it from the memory.

  Example: let's say the cache have a place for only 2 blocks (Place A, and Place B), and the memory contains 10 blocks (block0 to block9). We can decide that in the first “set” (Place A) we put only even blocks, and in the second set (Place B) only odd blocks. Now if we access block 5 (say), then we only need to check the second set (Place B), because it can only be there. This may save us HALF the search time (or half the cost of searching a block).

In the above example, each “set” could hold only one block, but in general, each set can hold $n$ blocks at the same time: this kind of cache is called $n$-associative.

In other words, an $n$-associative cache is split into sets, where each set holds $n$ memory blocks. This allows us to determine the amount of different sets: it is the size of the cache (in blocks) divided by $n$.

Let’s have two examples:

1-associative: each set can hold only one block. As always, each address is assigned to a unique set (this assignment better be balanced, or all the addresses will compete on the same place in the cache). Such a setting is called direct mapping
fully-associative: here each set is of the size of the entire cache. That is, if the cache is of size $t$ blocks, a fully associative cache is in fact a $t$-associative cache. How many sets are there? one! and all the blocks are assigned to this single set. Therefore, each blocks can be saved “anywhere” at the cache, because all the cells of the cache belong to the same set.

index and tag

We said that each block gets an assignment to one of the $k=size/n$ sets. To make things simple, this assignment is determined by looking at lowest $\log_2 k$ bits of the block number. These are called the “index” bits: they index to which set the block will go into.

  Pop Quiz 1: How many index bits are there in a fully associative cache?

Answer (think about it for a second before looking at the answer):

   In a fully associative cache there is only one set. So we don’t need an index to choose a set, there is only one! Formally, $k=1$ and we need $\log_2 k=\log_2 1=0$ index bits.

next,

  Pop Quiz 2: How many index bits are there in a direct mapping cache?

Answer

   In a direct mapping cache, we have $k=size/1$ different sets. Thus we need $\log_2 k$ index bits.

Next, there are the “tag” bits. To explain these, let’s think on a fully-associative cache.
To make things simple, let’s assume the cache is of size 2 blocks. Assume this two cache-cells are full with information from the main memory: the first cell holds block 0 and the second one holds block 190.
Now we access an address in block 220. But it is not in the cache, so we need to bring it from the memory and replace one of the blocks that are currently in the cache. But wait! How do we actually know that the cache doesn’t hold block 220?
Right. The cache must “remember” that the first cell holds block 0, and that the second one holds block 190. No other choice. This information (0 or 190) is called the tag: to each cell of the cache we add a little tag with that indicates what block is currently there. Simple, right?

But saving information in the cache is expensive, and we don’t want to save information we never use. In the above example every address could be placed anywhere in the cache, but this is not the case for other associativity levels: Each address can go only to its assigned set as determined by the “index” bits. So if there are two sets, where the first can hold only blocks 0,2,4,6,8, and the second set can hold only blocks  1,3,5,7,9, then we don’t need to save the entire block number in the cache-- block 4 can never appear in the second set, and block 7 can never appear in the first set. This means we don’t need to save the last bit (the one that determines the parity), but we need to save the rest. Indeed, the last bit serves as the index, and the rest serve as tag, thus, by knowing the set+the tag we know exactly which block  is currently kept in each cache-cell.

Now back to your question, which exemplifies the above ideas:

The 3-way associativity means that the cache is split into sets, and each set can hold up to 3 blocks. The question gives us that each block is 2 words.

So instead of having 3 sets, where each can hold 2 different addresses/block (as you had in the table you drew), the cache has a large number of sets, and each set has a room for 3 blocks.

How many sets exactly?  well, the cache has 24 words, that is 12 blocks, that is 4sets (of 3 blocks each!). This gives us the size of the index field: 2 bits. [The index decides which set we go into, and there are only 4 sets, so the index needs to be only 2 bits..].

This was the first part of the story. The other part is that a block is two words. Therefore, e.g., when the address 0 is accessed, the cache (set 0) will hold the first two memory words. Thus, if the address 1 is later access, it will be a hit. Since both addressed 0 and 1 are in the same block, we need a way to distinguish them. This will be the "offset" bit.

The above suggests that the 8bit address is to be parsed as

tttttiio

where o=offset  (distinguishes between the 2 words in each block), i is the index (specifies the set) and t is the tag (tells us which block is occupying each cache cell..

So, unless I'm being too careless in thinking it over, the mapping will look like this (building on your table).

Block   Add      Index     Hit/Miss   Set 0         Set 0      Set 0     Set 1      Set 1      Set 1     Set 2      Set 2      Set 2     Set 3      Set 3      Set 3
3   =00000011    01        miss      mem[00000]
180 =10110100    10        miss      mem[00000]                                                                     mem[10110]
43  =00101011    01        miss      mem[00000]     mem[00101]                                                      mem[10110]
2   =00000010    01        hit       mem[00000]     mem[00101]                                                      mem[10110]

etc... Note that by mem[ttttt] I denote the specific block by writing its 5-bit tag value.

tl;dr
A nice illustration to all this "set-associativity" thingy can be found here.


Graph Closeness - Different result with gephi and NodeXL

The closeness of a node in a graph is defined as the reciprocal of the sum of all distances to other nodes.

Since your example is completely symmetric, we only calculate the closeness centrality of $A$.

distance $A\to B$ is 1
distance $A\to C$ is 1
distance $A\to D$ is 2

Therefore the sum of the distances is 4, and the closeness of $A$ is $1/4$. This shows that the NodeXL results are correct. I would advise you to have a look at the manual of Gephi to check how the closeness is computed here. It should be definitely be smaller than 1.


Do Core Computer Programs Have To Function By Powers Of 2?

It is not essential. Most computers can handle no data smaller than a byte without extra effort (i.e. the memory is addressed by byte, not by bit). Hence there is generally no point in using less than a byte for anything, unless you're in a situation where memory consumption is crucial, such as network communication.


You can derive $aabbb$ which is not in the language, so your grammar is wrong.

How did I find this? I observed that $A \Rightarrow^* a^ib^i$ and $B \Rightarrow^* b^j$ for all $i \geq 0$, $j > 0$. It's clear that this is wrong, and I looked for the smallest counter-example.

You need to ensure that more than double as many $b$'s as $a$'s are generated.


Hint:

You are right on (a). The proof involves key results for Kleene star as follows.
$$
\Sigma^{*}=\bigcup_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{*}=\bigcup_{n\geqslant1}L\Sigma^{n}\quad\text{and}\quad \Sigma^{*}L=\bigcup_{n\geqslant1}\Sigma^{n}L
$$
Where $\Sigma^{n}$ can be considered as the set of the concatenation of i strings in $\Sigma$, and $L\subset \Sigma^{*}$.

For (a), $L_1\Sigma^{*}\subset\Sigma^{*}$ since for all $n,L_1\Sigma^{n}\subset\Sigma^{n}$. If $\Lambda\in L_1$, then $n,L_1\Sigma^{n}=\Sigma^{n}$ for all $n$. Thus $L_1\Sigma^{*}=\Sigma^{*}$.

For (b), notice that if $\Lambda\in L_1$ and $L_2$, then $L_1\Sigma^{*}=\Sigma^{*}$ and $\Sigma^{*}L_2=\Sigma^{*}$. Thus
$L_1\Sigma^{*}L_2=\Sigma^{*}L_2=\Sigma^{*}$.


How can an artificial neural net change the sign of a weight?

Your problem stems from the fact that the equations in the link you provide refer to linear neural networks. Your network is not linear, as it has a sigmoid activation function. So you need to include its gradient in weights correction. Wikipedia explains how to do it pretty well. Here is an example Python script, which learns your target function in 1000 epochs achieving average error of order $10^{-3}$ in exactly the same conditions as you describe. Increasing the number of epochs makes the error smaller.

Note: this is NOT a recommended implementation of a neural network - just a demonstration script written on a whim.

import math

def sigmoid(x):
    return 1.0 / (1.0 + math.exp(-x))

class Network:
    def __init__(self, w, b):
        self.w = w
        self.b = b

    def __call__(self, x):
        return sigmoid(self.w * x + self.b)

    def propagateError(self, x, error, output):
        dEdW = error * output * (1 - output) * x
        dEdB = error * output * (1 - output)

        self.w += 0.05 * dEdW
        self.b += 0.05 * dEdB

def target(x):
    return sigmoid(10 * x - 5)

n = Network(0.6, 0.2)
# Training
for it in range(1000):
    for i in range(100):
        x = 1.0 * i / 100
        output = n(x)
        t = target(x)
        error = t - output
        n.propagateError(x, error, output)
# Testing
te = 0
for i in range(100):
    x = 1.0 * i / 100
    output = n(x)
    t = target(x)
    error = t - output
    print("Desired:",t)
    print("Actual:",output)
    print("Error:",error)
    te += error
    print("---")

print("Average error:",te/100.0)

Output:

('Desired:', 0.0066928509242848554)
('Actual:', 0.012425919415559344)
('Error:', -0.005733068491274489)
---
('Desired:', 0.007391541344281971)
('Actual:', 0.013550016530277079)
('Error:', -0.006158475185995108)

...

('Desired:', 0.9918374288468401)
('Actual:', 0.9855607114050042)
('Error:', 0.006276717441835888)
---
('Desired:', 0.9926084586557181)
('Actual:', 0.9867575913715647)
('Error:', 0.005850867284153405)
---
('Average error:', -0.0013496485567271077)


Propositional logic --- syntactical completeness

You are not doing anything "wrong", you just missed the point of the incompleteness theorem, a bit.

What you claim (correctly) is that a proof system with no axioms is incomplete. You also say that this is not very impressive...

What Godel showed is something much stronger: consider the theory of Peano arithmetic, then there does not exist a complete axiomatization for it.

How does this relate to your post? Well, in your suggestion, even when you consider an empty set of axioms, there are still some true sentences (the tautologies), and there are axiom systems that capture exactly those sentences.


Find if a sequence of node is a result of a binary tree preorder traversal

Idea of a tree construction

If the length of the sequence is $1$ then just make the first symbol root and stop with SUCCESS. If the first symbol of the sequence is $0$ then construction is not possible, otherwise make it the ROOT and set the root to the ROOT.

for i = 2 to n
 if n[i] is 1 then
   if root.left is free
     root.left = make_node(n[i])
     root = root.left #go to left
   else if root.right is free then
     root.right = make_node(n[i])
     root = root.right #go to right
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 else if n[i] is 0 then
   if root.left is free
     root.left = make_node(n[i])
   else if root.right is free
     root.right = make_node(n[i])
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 end

 if root is nil then break
end

if i < n the construction impossible

Checking without a tree construction

The basic idea is at each step to count how many nodes we can add to the tree. When we read $1$, we add one internal node which allows to add two new nodes and hence $-1+2 = 1$ and so we increment the counter by one. When we read $0$ we add a new leaf and so we decrement the counter.

if a[0] == 0 then
  return FAILURE
else
  counter = 2

for i=2 to n
  if a[i] == 1 then
    counter = counter + 1
  else
    counter = counter - 1
  end

  if counter == 0 then break
end

if i < n then
  return FAILURE
else
  return SUCCESS
end

Construction example

$1,1,0,1,1,0,0,1$

  1 =>  1  => 1  => ... =>  1
       /     /             /
      1     1             1
           / \           / \
          0   1         0   1
                           / \
                          1   1
                         / \
                        0   0

Checking example

c=2, c=3, c=2,c=3, c=4, c=3, c=2, c=3, SUCCESS

At the end c=3 means we still can add 3 leaves.


Lower bound for finding majority element in a sorted array

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.


How a NTM reject an input / How a TM simulates a particular NTM

If we're only interested in computability, and not in the resources used by the computation (i.e., complexity), then we can simulate an NTM as follows. First, simulate every possible sequence of nondeterministic choices for one step. Then, start again and do them all for two steps. Then, start again and do them all for three steps, and so on.

There are three possible results of this simulation.

If any of the simulated computations accepts (so, in particular, it terminates), then we accept. In this case, it doesn't matter if some other computations would diverge.
If no computation accepts but, after some number of steps, all computations have rejected, we reject.
If no computation accepts and at least one computation diverges, then the simulation will also diverge.

This is a faithful simulation of the nondeterministic machine. If some computation path accepts, we accept, and this is the definition of acceptance for nondeterministic machines. If every computation path halts and rejects, we reject, as we should. Otherwise, we diverge, as does the nondeterministic machine.

However, the case you're looking at does include resource bounds. Papadimitriou is essentially comparing two different notions of the resources used by an NTM and showing that they're both the same. I'll talk about time for concreteness, but the same arguments apply to space. One way of defining $\mathrm{NTIME}(f(n))$ would be to say that every possible computation path must run within $f(n)$ steps, and the other would be to say that only the accepting paths need to. However, because we're only interested in constructible functions $f$, we can use the following idea to make the two notions identical. First, the machine deterministically computes $f(n)$ and then it does the nondeterministic computation, counting off the steps. If the step counter reaches $f(n)$, and the machine hasn't accepted, we must be either on a rejecting path or a diverging one. In either case, the path won't accept, so we can reject. Therefore, any language that's accepted by an NTM where every accepting path uses at most $f(n)$ steps is also decided by an NTM where every path uses at most $f(n)$ steps and no path diverges.

Technically, I've only shown that we can do it in something like $3f(n)$ steps, but the linear speed-up theorem says we can get rid of the constant $3$.


How to do if a potential function Does not work? Amortized analysis

When you delete, your $actual$ $cost$, or $c_n$ by your notation, is $log(n)$.

it means you want: $\Delta \phi = \phi_{n+1}-\phi_n \approx -log(n)$

Its not hard to find such potential function that satisfies both:

try $\phi = nlog(n)$

for insert:

$Cost_{insert} = log(n) + (n+1)log(n+1) - nlog(n)$

$= log(n)+log(n+1)+nlog(n+1)-nlog(n) = O(log(n))$

$Cost_{delete} = log(n) + (n-1)log(n-1) - nlog(n) $

$= log(n)-log(n-1)+nlog(n-1)-nlog(n) $

$\leq (log(n)-log(n)) +(nlog(n)-nlog(n)) = O(1)$

All potential functions that satisfy $\phi(i) \geq 0 $, $\phi(0)=0 $ are correct, they just may not prove the amortized time you have in mind.


Here is the idea of the proof. Let $a_i,b_i$ be the distance thrown by the $i$th male/female. Using FFT, we calculate
$$ \left(\sum_i x^{a_i}\right) \left(\sum_j x^{b_j}\right) = \sum_{i,j} x^{a_i+b_j}. $$
Each pair $i,j$ satisfying $a_i + b_j = k$ contributes one term $x^k$ to the polynomial on the right. Hence the coefficient of $x^k$ is the number of pairs $i,j$ such that $a_i + b_j = k$.

If things still aren't clear, I suggest you try a few examples.


Is it possible to prove Tarski's Undefinability theorem from Turing's Halting Problem?

As cody observed, the problem with that strategy is that definable relations need not be computable. For example, the Halting Problem is definable in $(\mathbb{N}; +,\times)$ (see Kleene's $T$-predicate).

That said, a relativized form of the incomputability of the Halting Problem, applied to iterates of the Turing jump, does do the job:

First, we show that for each $n$ and each $\Sigma_n$ formula $\varphi$ the set $\{x: \varphi(x)\}$ is computable from ${\bf 0^{(n)}}$, uniformly in $n$ and $\varphi$.
Next, we show that for each $n$ the set ${\bf 0^{(n)}}$ is itself definable by some $\Sigma_n$ formula $\psi_n$. This is an application of Kleene's $T$-predicate.
Now we're good to go. Suppose we had a $\Sigma_n$ formula $\varphi$ defining the set of (Godel numbers of) true sentences in the language of arithmetic. Then ${\bf 0^{(n)}}$ could compute ${\bf 0^{(n+1)}}$ as follows: given $k$, we ask ${\bf 0^{(n)}}$ whether $\varphi(\underline{\ulcorner\psi_{n+1}(\underline{k})\urcorner})$ holds. (Here "$\underline{i}$" denotes the numeral corresponding to the number $i$, and "$\ulcorner\theta\urcorner$" is the Godel number of $\theta$.)
But that gives ${\bf 0^{(n+1)}}=({\bf 0^{(n)}})'\le_T{\bf 0^{(n)}}$, a contradiction by the relativized unsolvability of the Halting Problem.


What is the difference between distributed representations and factors of variation in deep learning

Usually, factors of variation are independent from each other. However, sometimes in feature extraction, some combination of these factors can be helpful to detect better and accurate features to explain the behavior of the observation.

Therefore, factors of variation are used to explain distributed features, and their relation likes the relation between basis of a space and a vector which is defined in the space using these basis or prime factors.

Although, observations change base on the factors of variation and distributed features, distributed features change base on the factors of variation.
In the other words, features of variation are prime factors, and distributed features are defined base on the prime factors.


Define a configuration to be a state of the array $A[]$ after receiving some of the numbers.  Define a configuration to be obviously wrong if there exists indices $i<j$ such that $A[i],A[j]$ have already been filled in with numbers such that $A[i]>A[j]$.

A randomized algorithm

Here is a natural algorithm: guess where to put each number uniformly at random, conditioned on the one constraint that you never place a number in an obviously wrong position.

The analysis of this approach seems pretty tricky.  Based on some back-of-the-envelope estimates I conjecture that this attains a $\sim e^{-\Theta(n)}$ probability of placing all numbers in the correct position, which is better than the naive $1/n!$ algorithm.  However I have no proof, so this could be wrong.

A deterministic algorithm

Here's what I can show.  Let's consider a variation on the above algorithm: when you receive each number, find the range of array indices that wouldn't be obviously wrong, and then place that number in the exact middle (median) of that range.  This algorithm is now deterministic.

For this algorithm, I can show that the probability of placing all numbers in the correct position is asymptotically larger than $1/n!$.  In particular, it is at least something like $1/2^{\Theta(n)}$.  Here's a hand-wavy analysis.  For simplicity, let's assume $n$ is one less than a power of two.  Place all $n$ numbers in a complete binary search tree.  Now consider all sequences where you enumerate all the numbers at depth $1$ in some order, then all the numbers at depth $2$ in some order, then all the numbers at depth $3$ in some order, and so on.  A hand-wavy estimate suggests that there are something in the vicinity of $n!/2^{\Theta(n)}$ such sequences, i.e., a random permutation has very roughly a $1/2^{\Theta(n)}$ probability of having this form.  Moreover, the second algorithm above always succeeds in placing every number in the correct position.  Therefore, the second algorithm above achieves a success rate of something in the vicinity of $1/2^{\Theta(n)}$.  In particular, the success rate is significantly larger than $1/n!$.

For values of $n = 2^i-1$, we can characterize the exact probability of being correct: letting $P(n)$ denote the probability that the second algorithm succeeds in placing every number in the correct position, we find

$$P(n) = {1 \over n} \times P(\lfloor n/2 \rfloor)^2,$$

because the first element needs to be the median, and then you have two problems of half the size (the subsequence of numbers smaller than the median has to be a sequence with the same property, and the same for the subsequence of numbers larger than the median).  We have the base cases $P(1)=1$ and $P(3)=1/3$.   This recurrence relation grows like $P(n) \sim 2^{-e/2 \cdot (n+1)}$.   Here $e/2 \approx 1.359\ldots$, so $P(n)$ grows roughly like $2^{-1.36 n}$, and in particular, much faster than $1/n!$.

In particular, here's one way to analyze this recurrence relation.  Let $Q(n) = -\lg P(n)$.  Then we find

$$Q(n) = 2 Q(\lfloor n/2 \rfloor) + \lg n,$$

where $Q(1)=0$ and $Q(3) = \lg 3$.  Letting $R(i) = Q(2^i-1)$, we find

$$R(i) = 2 R(i-1) + \lg(2^i - 1),$$

with base case $R(1)=0$.  Expanding, we find

$$R(i) = 2^{i-1} \times \left(\lg(1) + {\lg 3 \over 2} + {\lg 7 \over 4} + {\lg 15 \over 8} + {\lg 31 \over 16} + \dots + {\lg (2^i-1) \over 2^{i-1}}\right).$$

Summing the series, we find that to an excellent approximation

$$R(i) \approx 2^{i-1} \times e.$$

Therefore, $Q(n) \approx e/2 \cdot (n+1)$ and $P(n) \approx 2^{-e/2 \cdot (n+1)}$.

Credits: My thanks to @Algorithms with Attitude for the recurrence relation and the idea of analyzing the probability in this way.


Coordinated Attack Problem Different Requirements

This looks like the Byzantine generals problem.  There's a lot written on that subject; I suggest you start by reading the available literature and material on that subject.

I'm not entirely clear on you mean by "solvable in system S" (system S says processes don't fail, but the weak termination condition refers to failures, so what's going on there?), so I can't confidently answer that part of your question.

There's an obvious algorithm for the case of two parties:

Each party continually broadcasts a message saying "my input is X" (fill in X with whatever its input bit is).
Whenever you receive one of those messages, you respond with an acknowledgement describing your input, what you received from the other party, and what you will output; then you immediately produce the appropriate output and halt.
If you receive an acknowledgement message and have not halted yet, then produce the appropriate output and halt.

It looks like this satisfies all three of your requirements, including weak termination, assuming that messages can be dropped/lost but are not modified in transit and no forged/fake messages are inserted by the network.


Finite State Automata for recognising consecutive characters

The FSA should have three states:

$q_a$ represents:  last character was not a b, and no bb yet
$q_b$ represents:  last character was a b, and no bb yet
$q_{bb}$ represents:  there was already a bb

Clearly, you start with $q_a$ and you accept in $q_a$ and $q_b$. Now try to figure out how to connect the states.


Borrowing bioinformatic methods in other fields

Of course! The perfect example is Gusfield book. Many of string algorithms came from bioinformatics. For example, sequence analysis algorithms are used in text editors.

PS: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield


Why is left recursion and left factoring no problem in bottom up parsing?

LL parsing must predict which production will be used before it starts parsing the contents of that production. (It is a top-down parse — it constructs the parse node and then fills in the children.)

LR parsing is bottom-up; first it lets the children be recognised, and only then does it apply the production and create the parse node. Consequently, it does not need to know which production will be used until the end of the production, so it can handle a grammar where two or more productions start with the same symbols.

Also, since LR parsing does not immediately expand the predicted production onto the stack (or recursively call itself to parse the predicted production) recursive productions are not problematic.


Prove that finding largest subset of undirected graph that is almost independent is NP-hard

The proof is by reduction from independent set. Given an instance $(G,k)$ of independent set, construct a new instance $(G',1000k)$ in the following way: each vertex $x \in G$ is replaced by an independent set $I_x$ of size 1000, and each edge $(x,y)$ is replaced by a complete bipartite graph $I_x \times I_y$.

If $G$ contains an independent set $S$ of size $k$, then $G'$ contains an independent set $\bigcup_{x \in S} I_x$ of size $1000k$. In the other direction, suppose that $G'$ contains an almost independent set $S$ of size $1000k$. Remove all vertices incident to any edges within $S$ to obtain an independent set $S' \subseteq S$ of size at least $1000k-200$. Let $T = \{ x : I_x \cap S' \neq \emptyset \}$, and note that $T$ is an independent set of $G$. Finally, since $S'$ can contain at most 1000 vertices from each $I_x$, we see that $|T| \geq \lceil |S'|/1000 \rceil = k$.


Representing chained XOR operations as linear inequalities

Introducing another integer variable $t$, you can express the condition $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ as in the following canonical form.
$$x_1 + x_2 + \dots + x_n - 2t \le 1$$
$$- x_1 - x_2 - \dots - x_n + 2t \le -1$$
$$(x_1, x_2, \cdots, x_n) \le (1,1,\cdots,1)$$
$$(x_1, x_2, \cdots, x_n, t) \ge \mathbf 0$$
$$(x_1, x_2, \cdots, x_n, t) \in \Bbb Z^{n+1}$$
You can also replace the first two inequalities by the following equality.
 $$x_1 + x_2 + \dots + x_n - 2t = 1$$
In other words, you can actually eliminate one of $x_1, x_2, \cdots, x_n$ by replacing it with $t$.

Note $t$ is an integer not bounded from above. However, you can also bounded it by the following inequality, which is implied by the existing inequalities.

$$0\le t\le \lceil \frac{n}2\rceil-1$$

The idea is that $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ if and only if the number of $x_i$'s that are 1 is odd. This answer is essentially the same as the answer you mentioned.


What does "Every CFL is decidable" exactly mean?

The phrase

  Every context-free language is decidable

has the following meaning:

  If the language $L$ is context-free, then $L$ is decidable

or in other words

  If $L$ is a context-free language then $L$ is a decidable language


Is the language of rectangular matrices in MATLAB-style syntax context free?

Delete all numbers from your language $L$, and replace $,$ with $a$ and $;$ as $b$.  Then intersect it with the regular language $a^*ba^*ba^*$.  You obtain a new language $L' = \{a^n b a^n b a^n : n \in \mathbb{N}\}$.  If $L$ is context-free, then $L'$ will be context-free too, as it has been obtained by applying a homomorphism and then intersecting with a regular language, both of which preserve context-freeness.  However, $L'$ is a standard example of a non-context-free language, so $L$ must be non-context-free as well.


Can the formalisms of category theory replace those of type theory?

My view is more or less similar to chi's. I see category theory as (roughly) being to type theory what model theory is to logic. Some of the consequences of that are, first, each can exist autonomously. Indeed, type theory predates category theory, and the creation of category theory was not motivated by these concerns. Second, many of the distinctions category theory/model theory are purposely trying to blur are of primary interest in type theory/logic.

As a very basic example, all presentations of the axioms of a group give rise to the same class of models (namely groups). From the perspective of universal algebra, a variety (in the universal algebra sense, or a finitary algebraic category from a CT perspective) forgets its presentation. Meanwhile, from the perspective of equational logic, presentation is all there is. A primary computational topic here is E-unification which operates entirely at the level of equational logic, i.e. presentation.

This is typical. We say the simply typed lambda calculus (with products) (STLC) is the internal language of Cartesian closed categories, but it is really just one presentation of the internal language and not even the most "direct" one. The Categorical Abstract Machine (CAM) is arguably a more "direct" representation. Even with the STLC, the arrows of corresponding syntactic category are $\beta\eta$-equivalence classes of lambda terms! (But see this.) So either we somehow directly describe the syntactic category as a mathematical structure whose hom-sets just happen to coincide with $\beta\eta$-equivalance classes of STLC terms and have no computational content, or we need to already understand the STLC external to category theory, or we need to talk instead of presentations of Cartesian closed categories which, taking a fairly natural approach, will lead to something CAM-like. In the last case, equality of arrows becomes something like an E-unification problem. Understanding and simplifying this process as well as placing the more ergonomic facade of the STLC in front of it, requires techniques that are the bread and butter of logic and type theory but are not particularly natural within category theory.

A massively over-simplified picture that may nevertheless give a better idea of how category theory and type theory interrelate is the following. You can imagine them as two dimensions. The tools, techniques, and notations of type theory are geared toward moving vertically between different presentations of the same object, meanwhile the tools, techniques, and notations of category theory and geared toward moving horizontally between different mathematical objects. You might even say that a category is a whole vertical line and that category theory talks about moving one vertical line to another but not how the points of the two lines correspond. In this picture, category theory is not even capable of talking about the distinctions type theory is making, but this is intentional because it means that the arbitrarily complicated mapping of points on one vertical line to points on another is just irrelevant to what category theory cares about and can be ignored.

In my blog post, Category Theory, Syntactically, I describe an approach that makes category theory look more like type theory (rather than the other way around). Unsurprisingly, what I'm really discussing there are presentations of categories. Further, you can see aspects of normalization enter the picture, e.g. in my discussion of "product theories", even though this is not a focus at all of that particular post.


number of connected subgraphs of $G$ with at most $ k>0$ vertices

Your argument doesn't really constitute a proof, so it is hard to evaluate it. It's not really clear where the maximum degree comes in. You write the inequality $d \cdot d^{k-1} \leq d^k$, but it isn't clear why we're multiply $d$ by $d^{k-1}$. It's not clear why DFS is relevant here (and why you mention connected components when you're interested in connected sub graphs), and it's not clear how you use the inductive hypothesis.

Here is a different argument which hopefully functions better as a proof. Before we can start the proof, we need to understand what we are trying to prove.

Definition. Let $G = (V,E)$ be a graph. An induced subgraph of $G$ is a graph of the form $(U, E \cap U \times U)$ for any non-empty $U \subseteq V$. A connected subgraph of $G$ is an induced subgraph of $G$ which is a connected graph.

Instead of connecting connected subgraphs directly, it is better to count trees instead. We can do this because every connected graph has a spanning tree. This is embodied in the following lemma.

Lemma 1. Let $G$ be a graph on $n$ vertices, and let $1 \leq k \leq n$. The number of connected subgraphs of $G$ having $k$ vertices is at most the number of trees of $k$ vertices contained in $G$. (A tree is contained in $G$ if all the edges of the tree are edges of $G$.)

Proof. Let $C_k$ be the set of connected subgraphs of $G$ having $k$ vertices, and let $T_k$ be the set of trees of $k$ vertices contained in $G$. Since each connected graph has a spanning tree, we can identify a tree of $k$ vertices inside each subgraph in $C_k$. This gives an injective function $f\colon C_k \to T_k$: if $f(c) = t$ and $t$ is a tree on the vertex set $U$, then $c$ is the subgraph induced by $U$. Therefore $|C_k| \leq |T_k|$. $\quad \square$

We can estimate the number of trees of size $k$ contained in $G$ using an appropriate encoding scheme. The basic idea is to pick a starting vertex inside the tree, describe the vertices adjacent to it in the tree, and so on. Each time we describe the adjacent vertices, we can use the fact that every vertex has at most $d$ neighbors.

Lemma 2. Let $G$ be a graph on $n$ vertices of maximum degree $d$. The number of trees of $k$ vertices contained in $G$ is at most $nd^{2k-2}$.

Proof. The lemma clearly holds for $k=1$, so suppose that $k \geq 2$.
Fix an arbitrary ordering on the vertices of $G$. We describe a procedure that receives as input a tree $T$ and a leaf $v$, and outputs a succinct numerical encoding of $T$. The procedure, Encode, uses a subroutine, Encode-child, which accepts $T$, a vertex $u \in T$, and another vertex $p$ which is adjacent to $u$ in the tree $T$.

Encode(T, v):
  Let u be the unique neighbor of v in T.
  Suppose that u is the i'th smallest neighbor of v in G.
  Output v, i, and run Encode-child(T, u, v).

Encode-child(T, u, p):
  Let u_1, ..., u_m be the neighbors of u in T other than p.
  Output the degree of u in T, i.e., m+1.
  For i = 1, ..., m:
    Suppose that u_i is the j'th smallest neighbor of u in G.
    Output j, and run Encode-child(T, u_i, u).

(We assume that $i$ in Encode and $j$ in Encode-child run from $1$ to $d$.)

What does the output look like? The first item in the sequence is a vertex, which we can identify as a number from $1$ to $n$ (using the order of the vertices of $G$). All other items are numbers from $1$ to $d$. Thinking of $T$ as rooted at the starting leaf $v$, for each non-root vertex we encode both its degree and its index as a child of its parent, for a total of $2(d-1)$ numbers.

We can reconstruct the tree from this encoding. Indeed, it is not difficult to explicitly spell out a decoding procedure which gets as input the sequence of $1+2(d-1)$ numbers, and outputs a tree. It is more challenging to prove that if we encode a tree $T$ and run the decoding procedure, then we get back the tree $T$; however, the challenge is mostly technical rather than conceptual, since intuitively it is clear that the decoding algorithm works. We therefore leave these steps to the curious reader.

We conclude that the encoding procedure described above is an injective mapping from the set of pairs $(T,v)$, where $T$ is a tree of $k$ vertices contained in $G$ and $v$ is a leaf of $T$, to the set of sequences lying in $[n] \times [d]^{2k-2}$ (where $[m] := \{1,\ldots,m\}$). Since every tree contains a leaf, this shows that the number of trees is at most $nd^{2k-2}$ (in fact, since every tree contains at least two leaves, we can improve this to $nd^{2k-2}/2$). $\quad\square$

As a conclusion, we can estimate from above the number of trees having at most $k$ vertices by
$$
\sum_{\ell=1}^k nd^{2\ell-2} = \frac{nd^{2k}-n}{d^2-1} \leq nd^{2k}.
$$
According to Lemma 1, this is also an upper bound on the number of connected subgraphs having $k$ vertices.

Is this bound tight? Probably not. Our encoding scheme is quite wasteful. For example, when encoding $j$ in Encode-child, we can use a number from $1$ to $d-1$, since we know that $u_i \neq p$. This improves the exponent to $d(d-1)$ from $d^2$.

In order to determine the optimal exponent, we can take as our graph $G$ the infinite $d$-ary tree, and count the number of trees of $k$ vertices rooted at a fixed vertex of $G$.
This is worked out in this math.se question, which shows that the optimal exponent is $(d-1)^{d-1}/(d-2)^{d-2}$. For example, when $d=3$ the optimal exponent is $4$ rather than $6$ (the well-known asymptotic of Catalan numbers), and when $d=4$ it is $6.75$ rather than $12$.


Trying to find two CFGs for the following languages

You can write the first language as
$$
\{ a^k b^r a^r a^k \mid k,r \geq 0 \}.
$$
The corresponding context-free grammar is exactly the one you give. If you apply $k$ times the rule $S \to aSa$ and $r$ times the rule $T \to bTa$, then you will get $a^k b^r a^r a^k$.
As for the second language, let us start with the slightly easier
$$ \{ a^n b^m \mid n \le 2m \}. $$
For each $b$ that you add, you can add up to two $a$'s. This leads to the grammar
$$ S \to Sb \mid aSb \mid aaSb \mid \epsilon. $$
In your case, you have to guarantee at least one $a$. Write this as follows:
$$
\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m+1 \} =
\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m \} \cup
\{ a^{n+2}b^{m+1} \mid 0 \leq n \leq 2m \}.
$$
Thus you can add the following rules to the preceding grammar, making $T$ the new starting symbol:
$$
T \to aSb \mid aaSb.
$$


they are known as the Learning factors: c1 and c2 usually equal to 2. However, other settings were also used in different papers. But usually c1 equals to c2 and ranges from [0, 4]

if you need more information about PSO i'd have a quick read of the tutorials at http://www.swarmintelligence.org/tutorials.php


With a static prediction of not-taken, when the branch is not taken (correct prediction) there is no penalty. When the branch is taken ("happens"), all the instructions that were fetched after the branch instruction are flushed from the pipeline (except for any branch delay slot instructions) when the branch instruction is evaluated. Instruction fetch restarts at the correct address.

With a simple five-stage pipeline (instruction fetch, decode, execute, memory, writeback) where branch direction and target are determined in the third (execute) stage and no branch delay slots are used, a taken branch will take three cycles (i.e., the instructions in the fetch and decode stages are flushed). If all other instructions have a cycles per instruction of one, then the total CPI would be the fraction of instructions that are taken branches times three cycles plus one minus that fraction (all other instructions including not taken branches) times one cycle (for 30% taken branches: 0.20*0.30*3 cycles + (1-(0.20*0.30))*1 cycle; for 70% taken branches: 0.20*0.70*3 cycles + (1-(0.20*0.70))*1 cycle). (This is simply the sum of the products for each instruction type of the number of cycles for that instruction type times the fraction of instructions of that type. For this case, the instruction types are taken branches (three cycles, 30% of 20%) and all other instructions (1 cycle, 100% - taken branch percentage).

The execution time (in cycles) is simply the CPI times the instruction count. The speedup factor would be the execution time for one case divided by the execution time of the other case. Subtracting one from the speedup factor and multiplying by 100 gives the speedup percentage. (If the factor is less than one, the speedup percentage will be negative. Negating this would provide the slowdown percentage.)


Recurrent relation for algorithms with two stages

Just solve both cases separately. I.e., consider cases for $m < k$ and $m = k$ separately. The solution for the first one (i.e., $T(n, k - 1)$) gives the starting point for the second recurrence (i.e., $T'(n) = T(n, k)$, presumably for $n \ge k$).


Maximum independent nodes subset algorithm with strong constraint

A set satisfying condition (3) is known as a dominating set. The exercise asks for a maximum weight dominating independent set.

If all node weights are positive, then every optimal solution is automatically a dominating set (why?), regardless of whether the graph is a tree or not. In the more general case in which negative weights are allowed, you can use a standard dynamic programming approach. Root the tree at an arbitrary node, and for every subtree rooted at some internal node $v$, compute the maximum weight independent set in the following three cases:

The independent set is dominating and includes $v$.
The independent set is dominating and doesn't include $v$.
The independent set is dominating if $v$ is removed (it is allowed to dominate $v$ as well), and doesn't include $v$.

I'll let you complete the details.


Compressing two integers disregarding order

Yes, one can.  If $x<y$, map the set $\{x,y\}$ to the number

$$f(x,y) = y(y-1)/2 + x.$$

It is easy to show that $f$ is bijective, and so this can be uniquely decoded.   Also, when $0 \le x < y < 2^{32}$, we have $0 \le f(x,y) < 2^{63} - 2^{31}$, so this maps the set $\{x,y\}$ to a 63-bit number $f(x,y)$.  To decode, you can use binary search on $y$, or take a square root: $y$ should be approximately $\lfloor \sqrt{2 f(x,y)} \rfloor$.


The intersection of two context-free languages can be non-context-free. The classical example is
$$ \{ a^n b^n c^m : n,m \geq 0 \} \cap \{ a^m b^n c^n : n,m \geq 0 \} = \{ a^n b^n c^n : n \geq 0 \}. $$
So in general you cannot simulate the intersection of two NPDAs with an NPDA.


Hint: Take a DFA for $L_1$. Check which states are reachable from the initial state via a word in $L_2$. Check from which states a final state can be reached via a word in $L_2$.


Real life applications of finite automata

As Yuval Filmus said, the KMP substring matching is widely used in practice because of its modularity and efficiency.

A maybe more "practical" exemple is lexical analysis.
(https://en.wikipedia.org/wiki/Lexical_analysis)

Depending on your application (let say or the compilation of a programming language) the parsing phase can be done with some various
generalisation of automatons (state transition machines or pile-automatons for instance). The language they accept is infinite (think of the set of all programs that are syntactically correct in your favorite language), yet
the recognition of a correct program should be done by an automata (or a generalisation of it) which is finitely presented.


Can preorder and postorder traversals be used on any type of trees?

Well, yea. But you need to define formally what a "type of tree" could be. General trees, are described by the mathematical notion of a tree graph. Given some ordering on the nodes of the tree, and some definition of which node is the root of the tree, you can perform the "pre-order" and "post-order" traversals.
The algorithms that computes them are also very similar to the ones you are probably familiar with, with the small change that you need to iterate all children instead of just traversing on the two children (since the number of children isn't restricted here).
However, the in-order is not defined properly for trees without also defining a notion of what children are "to the left" of the root and what children are "to the right" of the root. When you give a formal definition to this idea as well, you can perform the in-order traversal as well.


Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert each DFA to a canonical minimum DFA, then decide whether the two DFAs are equivalent. Each transformation preserves the language represented, so this ultimately decides whether the two grammars have the same language.


Formulating the master theorem with Little-O- and Little-Omega notation

I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than the more convoluted alternative?

That is indeed a natural attempt to understand that "convoluted" condition in simple terms. Unfortunately, it is not correct.
Here is a simple counterexample. Let $a=1$ and $b=2$, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = T(\frac{n}{2}) + f(n)$ and $T(1)=0$, where $f(n)=\frac1{\ln n} \in o(1)=o(n^{\log_21})$.
If the first case of master theorem still holds, we should have $T(n) \in \Theta(n^{\log_21})=\Theta(1)$. However,
$$T(2^m)=T(2^{m-1})+\frac1m=T(2^{m-2})+\frac1m+\frac1{m-1}=\cdots=\frac1m+\frac1{m-1}+\cdots+1.$$
Letting $m$ goes to infinity, we see that $T(n)$ is not bounded because the harmonic series diverges.

For the same or a variety of other reasons, the usage of an arbitrarily small positive constant, which is usually denoted by $\epsilon$ pops up constantly in different places, especially in asymptotic estimate and complexity analysis.  You may want to get used to it or even get addicted to it.

Exercise 1. Verify that for any $\epsilon>0$, it is not true that $\frac1{\ln n}\in o(n^{-\epsilon})$ although  $\frac1{\ln n}\in o(n^0).$
Exercise 2. Construct a counterexample for the master theorem where $a=4$, $b=2$ for

the first case where $f \in o(n^{\log_b{a}})$ instead of $ f \in O(n^{log_b{a}-\epsilon})$ for some  $\epsilon > 0$ and
the third case where $f \in \omega(n^{\log_b{a}})$ instead of $f \in \Omega(n^{\log_b{a}+\epsilon})$ for some $\epsilon > 0$

respectively.


In fast multiplier circuits, what is the difference between a Counter and a Compressor?

In multiplier design an (n,k) counter takes an n bit input and produces a k bit output which is the binary representation of the number of input bits that are 1s.  That is: it counts the number of input bits set to 1.

A (3,2) counter is just a full adder.

A (7,3) counter is a circuit with 7 input bits and 3 output bits.  The 3 output bits tell you (in binary) how many of the input bits are set to 1.

In an (n, k) counter it must be the case that $k = \lceil \log_2 (n+1) \rceil$.

A (n:k) compressor is any circuit that takes in n equal weight input bits (plus, possibly, some carry in bits) and outputs a k bit count, plus some additional carry-out bits.  The number of carry-in bits usually equals the number of carry-out bits, but you have to figure out the number by looking at the context.  (Hopefully there's a picture or a detailed description in the paper or book you are reading.)

So a (7,3) counter is also a (7:3) compressor.  But a (7:3) compressor could also mean something else, like something that takes in 7 input bits, plus a carry-in and outputs 3 output bits, plus a carry-out.

The most commonly used compressor is the (4:2) compressor.  This takes in 5 inputs, and output 3 outputs.  The reason it is not just a (5,3) counter is because the output is not a binary number in the range $[0, 5]$.  Rather the output is a 2-bit value in the range $[0,3]$ plus an additional carry-out.  So there are several ways of representing some of the outputs.  For example "2" can be represented as "0+carry-out" or as "2+no-carry-out".


Greedy Solution for Selecting Prefix Sum

Unfortunately, your greedy algorithm may return elements whose sum is not the maximum. For example, let $n=h=k=2$ and
$$\begin{pmatrix}
a_{11} & a_{12}\\
a_{21} & a_{22}
\end{pmatrix} =
\begin{pmatrix}
3 & 1\\
2 & 1
\end{pmatrix}.$$
Your algorithm will pick 3 and 1. The optimal elements should be 3 and 2.

The natural approach to this problem is dynamic programming.

Here are the subproblems.

For nonnegative integers $t$ and $j$ such that $0\le j\le n$ and $0\le t \le \min(nh, t)$, find $dp(t,j)$, the maximal sum of $t$ elements from the first $j$ arrays where all elements selected from the same array must be a prefix of that array. The wanted maximum sum is the maximum number of all $dp(t,j)$.

In order to select $t$ elements from the first $j$ arrays, we can select $i$ elements from the $j$-th array and $t-i$ elements from the first $j-1$ arrays for some $i$, $0\le i\le \min(t,h)$. Hence we have the following recurrence relation.

$$ dp(t,j) = \max_{0\le i\le \min(t,h)}\left(dp(t-i, j-1) + \sum_{1\le k\le i}a_{k,j}\right)$$

The base cases and the boundary cases can be figured out easily.


Reducing 3SAT to a Set Splitting Problem

Your problem is a generalization of NAE-SAT, an NP-complete version of SAT (see for example David Witmer's lecture notes in which we want each clause to have at least one satisfied literal and at least one falsified literal.

In order to convert NAE-SAT to your problem, identify literals with items, have a set per clause, and also have a set per variable, forcing the two literals to get opposite colors. Details left to you.


How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances?

A clause-learning SAT solver can be described approximately as follows. There is a stash of learned clauses, which starts empty. We run a recursive procedure, which at each point in time, first checks whether the current assignment (initially empty) contradicts an axiom or something in the stash. If so, there is no need to explore this branch. Otherwise, it picks a variable, and tries both assignment recursively. When a recursive call corresponding to a partial assignment $\alpha$ returns, we learn the clause $\lnot \alpha$. At any given point in time we are allowed to forget clauses. (It's important for the proof that each clause is learned, even if we forget it later on).

We now take the transcript of the algorithm and consider the clauses in the order in which they are learned. We prove that whenever a clause $c$ is learned, it can be derived using the rules of resolution from existing clauses or from axioms; in particular, at the very end we derive contradiction.

We allow the weakening rule in the refutation we construct; we can always get rid of weakening later on without increasing the refutation length (exercise).

There are three cases to consider. If the clause $c$ was learned because the corresponding assignment contradicted an axiom $c'$ or a clause in the stash $c'$, then $c$ is a weakening of $c'$. The interesting case is when $c = \lnot \alpha$ was learned since both assignment to some variable $x$ failed to produce a satisfying assignment. These assignments correspond to the learned clauses $c \lor x$ and $c \lor \lnot x$, from which $c$ follows by resolution.

Note that if we never use clauses in the stash then the resulting refutation is tree-like (every clause is used once), assuming we state each axiom whenever it's needed (rather than once and for all). Also, in any case the size (number of lines) of the refutation is the same as the number of recursive calls.


When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?

Your question is, essentiall, "How is this stuff implemented?", to which the answer is "However the implemnter chooses."

Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress.  In a concurrent environment, it would also limit you to doing only one search at a time.  Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A* search. This data structure will simply be deallocated when the search is complete.

If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.


Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?

Such constructions appear in papers of Seroussi and Bshouty, Alon, and Naor and Naor. See Bshouty for the latest on this topic.


Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I assume now that the question is the following:

  Given a binary tree with $n$ nodes, prove that it contains at most $\left\lceil \frac{n}{2} \right\rceil$ leaves.

Let us work with the tree definition $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid  \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$. For $T$ such a tree, let $n_T$ the number of nodes in $T$ and $l_T$ the number of leaves in $T$.

You are correct to do this by induction, but you will need structural induction that follows the tree structure. For trees, this is often done as complete induction over the height $h(T)$ of the trees.

The induction anchor has two parts. First, for $h(t)=0$ we have $T=\mathrm{Empty}$ with $l_T=n_T=0$; the claim clearly holds for the empty tree. For $h(t)=1$, i.e. $T = \mathrm{Leaf}$, we similarly have $l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$, so the claim holds for leaves.

The induction hypothesis is: Assume that the claim holds for all (binary) trees $T$ with $h(T)\leq k$, $k\geq 1$ arbitrary but fixed.

For the inductive step, consider an arbitrary binary tree $T$ with $h(T)=k+1$. As $k\geq 1$, $T=\mathrm{Node}(L,R)$ and $n_T = n_L+ n_R+1$. As $L$ and $R$ are also binary trees (otherwise $T$ would not be) and $h(L),h(R)\leq k$, the induction hypothesis applies and have

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

As all leaves of $T$ are either in $L$ or $R$, we have that

$\qquad \begin{align*}
  l_T &= l_L + l_R \\
      &\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\
      &\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\
      &= \left\lceil \frac{n_T}{2} \right\rceil
\end{align*}$

The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_R\in 2\mathbb{N}$. By the power of induction, this concludes the proof.

As an exercise, you can use the same technique to prove the following statements:

Every perfect binary tree of height $h$ has $2^h-1$ nodes.
Every full binary tree has an odd number of nodes.


Condition in Shamir Secret Sharing Scheme

I am not sure if this will completely answer the question, but I have a couple observations that might help.

First, note that for the random polynomial $q$, $q(0) = a_0$ is the key -- this is from the way that polynomial interpolation works.  So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 < i < n$.  This is also why it is important that the prime $p > k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.

Second, the polynomial $q$ is not just random, but also secret.  The fact that the degree of the polynomial $q$ is unknown matters.  When $n-1$ participants come together, they can do anything they want -- they are super clever.  They claim that the key is $w$.  However, there is a unique polynomial $g$ of degree $n-1$ such that
  $$g(i) = q(i)$$
and
  $$g(0) = w$$
However, this would be true for any $w$.  Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out.
   **Note however, that this is not true if the participants know the degree of the polynomial.


explaining $\lambda$-calculus/functional programming to someone used to Turing machines/procedural programming?

I'd like to second both Derek Elkins' and Chi's comments. You can do Functional Programming in most languages, but it requires the discipline to adhere to the functional principles. It's probably harder to learn FP in a language like Javascript\Python because you'll have to fight against the urge to do things the old way you already know.

In a Functional Programming Language (i.e. purely functional) you'll have to do stuff THE FUNCTIONAL WAY, without taking corners. Also, doing practical stuff means you'll have to learn some theory as well.

  make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.

Something I really like about functional languages (and is kinda contained in what you said about error-proneness) is they often have some pretty amazing Type Systems.

Let's look at a "Hello World" in C:

#include <stdio.h>

int main(){
    printf("Hello World\n");
    return 0;
}

The function main takes no arguments and returns an Int, but there's no way I would know that it is actually doing IO inside it's body, unless I look at the functions body.

I can even change it and only get a warning.

#include <stdio.h>

char* main(){
    printf("Hello World\n");
    return 0;
}

hello.c:3:7: warning: return type of ‘main’ is not ‘int’ [-Wmain]
 char* main(){

The same code in Haskell,

module Main where

main :: IO ()
main = do
  putStrLn "hello world"

The function putStrLn has type Str -> IO(), to put it simply, it takes a String and returns some IO() stuff. Main also returns IO().

If I try to change the main's type to main :: String I would get the following error:

module Main where

main :: String
main = do
  putStrLn "hello world"

hello/src/Main.hs:4:1: error:

    • Couldn't match type ‘[Char]’ with ‘IO t0’
      Expected type: IO t0
        Actual type: String
    • In the expression: main
      When checking the type of the IO action ‘main’
  |
4 | main = do
  | ^

hello/src/Main.hs:5:3: error:
    • Couldn't match type ‘IO ()’ with ‘[Char]’
      Expected type: String
        Actual type: IO ()
    • In a stmt of a 'do' block: putStrLn "hello world"
      In the expression: do putStrLn "hello world"
      In an equation for ‘main’: main = do putStrLn "hello world"
  |
5 |   putStrLn "hello world"
  |   ^^^^^^^^^^^^^^^^^^^^^^

That is, Haskell is telling me that putStrLn will return some IO(), so main is expected to do the same, since it returns putStrLn. Actually it wasn't even required to give main a type, since Haskell has a pretty powerful Type System based on Hindley–Milner Type Inference.

This was a really trivial example, but it is often the case that most Runtime Errors in many languages will be caught as Compilation Errors in pure functional languages. Some languages, like Coq, are so strong that you can prove theorems with it!

  or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

This is actually a problem with Haskell (Survey 2017)

  Most people want the Haskell community to be bigger. To that end, many
  people want the community to be less divisive (for example Stack
  versus Cabal) or less elitist (for example putting down other
  languages). Also more beginner and intermediate documentation and
  tutorials would help.

Some pure Functional languages you might want to give a try:

Haskell
Elm
Coq

Here are some references I've been using through the years to get some familiarity with FP and it's theory.

Some references on the $\lambda$-Calculus:

Books

Lambda-Calculus and Combinators: I've only read the first 3 chapters, but it's a pretty solid introduction to the theory of $\lambda$-calculus.

Lecture Notes

Lambda-Calculus and Types: Lecture notes from a Oxford class with the same name.
Lecture Notes on the Lambda Calculus: Lecture notes from the University of Ottawa.
Introduction to Functional Programming: Lecture notes from a Cambridge course.

Quick Talks

Adam McCullough - Greek Classics: Lambda Calculus For Beginners
Steven Syrek - Lambda Calculus For People Who Can't Be Bothered to Learn It - part 1 of 2
Steven Syrek - Lambda Calculus For People Who Can't Be Bothered to Learn It - part 2 of 2

Lectures

Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed : A five lecture series by Dana Scott.

Some theory about Functional Programming:

Books

The Algebra of Programming
Purely Functional Data Structures
Type Theory and Functional Programming
Software Foundations: A free course on Coq, Functional Programming, Logic and Program Correctness.

Implementation of Functional Programming Languages

Design Concepts in Programming Languages
Implementing functional languages: a tutorial

Lecture Notes

Foundations of Functional Programming


Morgenstern first defines the notion of a linear algorithm. A linear algorithm gets as input $x_1,\ldots,x_n$ and its goal is to compute some $y_1,\ldots,y_m$, each of which is a (specific) linear combination of $x_i$s. The algorithm proceeds in steps, starting with step $n+1$. At step $t$, the algorithm computes $x_t = \lambda_t x_i + \mu_t x_j$ for some $i,j < t$. At the end of the computation, for each $i$, $y_i = x_j$ for some $j$.

For example, here is an algorithm computing the unnormalized DFT on 2 variables:
$$
x_3 \gets x_1 + x_2 \\
x_4 \gets x_1 - x_2
$$
Similarly, the unnormalized two dimensional DFT on $2^2$ variables is computed by:
$$
x_5 \gets x_1 + x_2 \\
x_6 \gets x_1 - x_2 \\
x_7 \gets x_3 + x_4 \\
x_8 \gets x_3 - x_4 \\
x_9 \gets x_5 + x_7 \\
x_{10} \gets x_5 - x_7 \\
x_{11} \gets x_6 + x_8 \\
x_{12} \gets x_6 - x_8
$$

We can view each $x_t$ as an $n$-dimensional vector which gives the linear combination of $x_1,\ldots,x_n$ producing $x_t$; call this vector $v_t$. The vectors $v_1,\ldots,v_n$ are just the $n$ basis vectors.

Morgenstern defines the quantity $\Delta_t$, which is the maximum magnitude of the determinant of any square submatrix of the matrix $V_t$ whose rows are $v_1,\ldots,v_t$.

Lemma. Let $c \geq 1/2$. If $|\lambda_s|,|\mu_s| \leq c$ for all $s$ then $\Delta_{n+t} \leq (2c)^t$.

Proof. The proof is by induction on $t$. When $t = 0$, this is easy to verify directly since $V_n$ is just the identity matrix. Consider now any $t > 0$. Every square submatrix of $V_t$ is either a square submatrix of $V_{t-1}$, in which case its determinant is at most $(2c)^{t-1} \leq (2c)^t$ by induction, or it involves the new row $v_t = \lambda_t v_i + \mu_t v_j$. In the latter case, we can write the square submatrix $A$ as $A = \lambda_t B + \mu_t C$, where $B,C$ are square submatrices of $V_{t-1}$ (replace the relevant part of $v_t$ by the corresponding parts of $v_i$ and $v_j$). Since the determinant is a linear function of any of its rows, $\det(A) = \lambda_t \det(B) + \mu_t(C)$. By induction, $|\det(B)|,|\det(C)| \leq (2c)^{t-1}$, and so $$|\det(A)| \leq |\lambda_t| |\det(B)| + |\mu_t| |\det(C)| \leq c(2c)^{t-1} + c(2c)^{t-1} = (2c)^t.$$

Corollary. Computing the DFT on $n$ variables using a linear algorithm with bounded coefficients requires $\Omega(n\log n)$ steps.

Proof. The determinant of the DFT matrix is $n^{n/2}$. Hence any linear algorithm computing the DFT in $t$ steps satisfies $\Delta_t \geq n^{n/2}$. If the bound on the coefficients is $c$, then the lemma shows that $(2c)^t \geq n^{n/2}$ and so $t = \Omega(n\log n)$.

Remark.  Strassen has shown that any algebraic algorithm (algorithm involving $+,-,\cdot,/$) for computing the DFT can be transformed to a linear algorithm using the same number of steps.


Learning rule of multilayer neural networks

Have a look at backpropagation, which is essentially what you're trying to do here. Wikipedia has a good derivation that follows exactly your example. If you're more into blogs (and who isn't?) have a look at this one, which goes through the steps of backprop in detail.

Best of luck!


It is known that
$$
1 \leq g(n) < \sum_{m=0}^\infty c^m = \frac{1}{1-c}.
$$
You take it from here.