Perfectly Secure Ciphers known other than the OTP By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define

OTP: An enc/dec function, $f:\mathcal{P} \times \mathcal{K} \rightarrow \mathcal{C}$
Perfect Security: Given $m, m^* \in \mathcal{M}$,
$$P\big(m=m^* \mid E_\mathcal{K}(m) = c\big) = P(m=m^*) $$

I ask, Are there any more Perfectly Secure Ciphers known other than the OTP?

I have looked into this question before and came up very short. From it, I believe that it may be the case that a cipher with this property is simply the Vernam Cipher (OTP) in disguise. It is still an interesting question as to how the use of additional resources or changes in protocol can potentially implement an equivalent to OTP with less effort. While it, itself, might not be exactly considered a cipher (or even a huge deviation from the one time pad), I found the following information theoretically cryptosystem to be incredibly interesting when I stumbled upon it a couple years back:

There is a more recent scheme (early 2000's), by Michael Rabin, called hyper-encryption, that can be shown to be information theoretically secure given the assumption that your adversary is space bounded (most others have assumptions on time bounds). As required by the scheme, there must be a very large, public, source of random bits.

The basic premise is for the sender and recipient to use the key to methodically pick out a one time pad from the random source of bits (using randomness extractors). In order to get this pad, the adversary would have to not only store the ciphertext, but also would need to store almost all of the random bits for use later. Their limited ability to store information would prevent them from doing this.

After the transmission is complete, access to the random bits is closed. The theory here is that, even if the key was revealed afterwards, that the adversary would not have enough information to establish anything about the plaintext. This remains true even if they had unlimited computational power, since no amount of post-analysis will get around the fact that the one time pad used depended on information that the adversary did not store. Since this security is not compromised even if the key is revealed after the transmission, the scheme is said to have perfect forward secrecy.


Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free? I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that gives rise to meaningful $L\cap L^2$.

Any hint would be appreciated!

You can take
$$
L = \{ a^n b^n : n \geq 1 \} \cup \{ a^k b^n a^n b^\ell : n,k,\ell \geq 1 \}.
$$
You can check that
$$
L \cap L^2 = \{ a^n b^n a^n b^n : n \geq 1 \}.
$$


Mathematical Problem Solving Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an optimal algorithm?

I think that proofs should yield interesting insights, and therefore can be used in designing algorithms. Since the program is expected to return a true response for every input, proof must be, in some way, built into the program. Is there any text I can refer to in this regard which will help in real problem solving?

Will a study of the mathematical proof of a problem [..], highlight peculiar properties of the problem which may help in designing an optimal algorithm?

Often they do. But not necessarily (unless you're a scholar of constructivism), for example when using the probabilistic method to show that a solution to said problem exists, then the proof will not help you designing any algorithm since it does not give you a construction.

  Since the program is expected to return a true response for every input, proof must be, in some way, built into the program.

That would be nice if it were the case, but often proving correctness (see formal methods) of an algorithm is rather difficult and/or a real pain. That said, there is such a thing as proof-carrying code which does exactly that, but the proofs are not given to you for free.


Closed form solution for a single layer linear perceptron Let f be a one-layer neural network which is linear (ie. no activation function). Let it have $p$ inputs and $q$ outputs. These are fully connected by weights $W$. We have $n$ inputs $x \in \mathbb{R}^d$ and $n$ outputs $y \in \mathbb{R}^{d'}$. We arrange these (column) vectors into matrices $Y$ and $X$, and the weights into a matrix, so that we can express the computation of the network on the whole dataset as $WX = Y$ (that is, if we could find the perfect $W$). Just to clarify, the network contains no hidden layer, just the input and output layers.

Training the network is a matter of choosing $W$ to minimize $e_W = \sum_{i=1}^n||y_i - Wx_i||^2$.

It seems to me that this problem should have a closed form solution that can be solved by a linear solver in some way. Unfortunately, my linear algebra is lacking. Is there a closed form solution? If not, where is the difficulty?

Yes, there is a closed form solution.

In the most general terms, $WX = Y$ is a linear equation, so it can be solved as $W = X^{-1}Y$. If $X$ has no inverse, using the pseudo-inverse $X^\dagger = X^T(XX^T)^{-1}$ will give the $W$ that minimizes $\sum_i||Wx_i - y_i||^2$.

For practical computation, it's best to compute the pseudo-inverse from a matrix decomposition, rather than multiplying the matrices explicity. The safest option is the singular value decomposition. The wikipedia article details the procedure.

The principle behind this solution used only basic calculus. Calling the error $E$, we set $\frac{\partial E}{\partial w_{ij}} = 0$ and solve for $w_{ij}$. This is detailed in [1, pages 89–93) and [2], both available online.

Alternative phrases for this problem are multivariate linear regression and affine registration.

[1] Neural Networks for Pattern Recognition, Christopher M. Bishop.

[2] Fitting affine and orthogonal transformations between two sets of points, Helmuth Späth, 2004


Check whether it is possible to turn one BST into another using only right-rotations Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, T2 and T3:

For example, given three binary search tree T1, T2 and T3:

 Tree 1                Tree 2              Tree 3
    a                    b                   a
   /                    / \                 /
  b                    d   a               d
 / \                      /                 \
d   c                    c                   b
                                              \
                                               c

T2 can be right-converted from T1, T3 can be right-converted from T1. But T3 cannot be right-converted from T2, T2 cannot be right-converted from T3.

Given two arbitrary BST, how to determine whether they are right-convertible with respect to each other?

If $T_1$ and $T_2$ don't encode the same sequence, they are not right-convertible into each other (obviously). This can be tested in linear time by inorder traversal of both trees.

The following procedure tests, if $T_1$ can be right-converted into $T_2$:

If both trees are empty, $T_1$ is right-convertible into $T_2$.
Right rotations move the root of the left subtree to the root of the complete tree. Thus, only nodes on the left flank of the tree can be rotated to the root. If the root node of $T_2$ is not on the left flank of $T_1$, $T_1$ is not right-convertible into $T_2$.
If the root $r_2$ of $T_2$ is on the left flank of $T_1$, obtain $T_1'$, by rotating $r_2$ up one level repeatedly, until $r_2$ is the root. Now $T_1$ is right-convertible into $T_2$, if and only if the left and right subtree of $T_1'$ are right-convertible into the left and right subtree of $T_2$, respectively.

Runtime:

Since each node will be rotaded up only once and by at most as many steps as the height of the tree, we need at most $O(n^2)$ rotations. If in $T_1$ all nodes are on the left flank and in $T_2$ all nodes are on the right flank, we will need $\frac {n(n-1)}2$ rotations, so the worst case runtime is in $\Theta(n^2)$.

Correctness:

If the algorithm finds a sequence of rotations, there obviously is one. To see the other direction, note the following:

If we rotate $r_2$ off the left flank, we immediately destroy right-convertability. So such rotations can never be necessary.
Any rotation not involving $r_2$ will affect a subtree, that is not changed by moving $r_2$ to the root. (It may be moved around as a whole, but this is independent of rotations within the subtree.) So if this rotation is necessary, we can still do it at a later time.

From these points correctness follows by structural induction.


Relations between statements involving universal quantifier, conditional and biconditional If we consider two predicates:

$b(x)$: x is a boy

$c(x)$: x is clever

Then, there are four statements involving $∀, b(x), c(x), →$ and  $↔$ . These are below along with my interpretation of their meaning. Correct me if I am wrong in any of these interpretations.

(a) $∀x(b(x)→c(x))$ - All boys are clever

(b) $∀x(b(x))→∀x(c(x))$ - If all are boys, then all are clever

(c) $∀x(b(x)↔c(x))$ - All boys are clever & all those who are clever are boys

(d) $∀x(b(x))↔∀x(c(x))$ - If all are boys, then all are clever & if all are clever then all are boys

I am trying to determine all conditional $(→,↛)$ / bi-conditional $(↔)$ relations between each two of above four. Between any two of these, if there is $↔$, then there is only one relation. However, if there is conditional relation in one direction, then conditional relation in other direction will be invalid. That is there can be $(→,↛)$. So at max there will be $4C_2\times 2=12$ such relations.

Now to understand these relations, I prepared below table. I considered that there are only two person in the universe $x_1,x_2$. $\{(b,c),(¬b,¬c)\}$ means $x_1$ is boy and is clever and $x_2$ is not a boy and is not clever.
The truth values (in table) in boldface (all other than vi, viii and xiv) are one which I feel are correct, though I am not sure. The non bold-faced truth values (vi, viii and xiv) are ones which I am unsure. So, I am more likely make mistake with them.

Based on the truth values in above table, I prepared following relations:

Q. Are relations 1 to 12 correct?

Q. Also is there some fault in the example predicates $b(x)$ and $c(x)$ themselves?

Actually, I must doing similar for existential quantifier. But afterwards. But am I correct with all this thinking or am just over thinking? Or am severly screwed with my logics?

Reasoning based on examples is fine for disproving implications, as you have done. In order to prove that an implication holds, however, you need something more elaborate. One possibility, as mentioned in the comments, is to use resolution to prove the implications. For example, suppose you want to show that (a) implies (b), i.e. that

$\varphi:=(\forall x.(b(c)\to c(x)))\to((\forall x.b(x))\to(\forall x.c(x)))$

is valid. We will do this by deriving a contradiction from $\neg\varphi$, which (using standard equivalences) is equivalent to

$\forall x.(\neg b(x)\vee c(x)))\wedge\forall x.b(x)\wedge\exists x.\neg c(x)$.

Skolemization results in

$(\neg b(x)\vee c(x))\wedge b(x)\wedge\neg c(a)$,

from which resolution derives first $\neg b(a)$ and then an empty clause, i.e. false. Therefore the original implication is valid.

As for your table, note that the example I gave also shows that (d) does not imply (a); the remaining 5 implications look ok.


Do CFGs generate many languages? Suppose we define a CFG such that it is possible to produce strings of the form $a^nb^n$ (in this case, I would think, we would need epsilon-productions).
Then one such $L(CFG)$ is $a^nb^n$.

However, let's say it is also possible to produce strings not of the form $a^nb^n$ from this grammar.

Can we still call $a^nb^n$ a language generated by the grammar, even if it is not the only/unique language accepted by the grammar?

In other words, is the language accepted by a CFG the set of all strings that can be derived from the grammar? Or can it also be a proper subset of these strings, fulfilling some desired criterion?

Every grammar, by definition, generates a single, unique language.

The definition of "generating $L$" includes that $\overline{L}$ has to be not generated. That's obviously not the case for any proper subset of the "largest" generated language.

The definition has not been chosen without reason: using your approach, every formal language would be regular (as subset of $\Sigma^*$). That would not be a useful model at all.


How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases".  This is a great heuristic: it's a great way to quickly weed out many incorrect attempts at an algorithm, and to gain understanding about why the algorithm doesn't work.

However, when learning algorithms, some students are tempted to stop there: if their algorithm works correctly on a handful of examples, including all of the corner cases they can think to try, then they conclude that the algorithm must be correct.  There's always a student who asks: "Why do I need to prove my algorithm correct, if I can just try it on a few test cases?"

So, how do you fool the "try a bunch of test cases" heuristic?  I'm looking for some good examples to show that this heuristic is not enough.  In other words, I am looking for one or more examples of an algorithm that superficially looks like it might be correct, and that outputs the right answer on all of the small inputs that anyone is likely to come up with, but where the algorithm actually doesn't work.  Maybe the algorithm just happens to work correctly on all small inputs and only fails for large inputs, or only fails for inputs with an unusual pattern.

Specifically, I am looking for:

An algorithm.  The flaw has to be at the algorithmic level.  I am not looking for implementation bugs.  (For instance, at a bare minimum, the example should be language-agnostic, and the flaw should relate to algorithmic concerns rather than software engineering or implementation issues.)
An algorithm that someone might plausibly come up with.  The pseudocode should look at least plausibly correct (e.g., code that is obfuscated or obviously dubious is not a good example).  Bonus points if it is an algorithm that some student actually came up with when trying to solve a homework or exam problem.
An algorithm that would pass a reasonable manual test strategy with high probability.  Someone who tries a few small test cases by hand should be unlikely to discover the flaw.  For instance, "simulate QuickCheck by hand on a dozen small test cases" should be unlikely to reveal that the algorithm is incorrect.
Preferably, a deterministic algorithm.  I've seen many students think that "try some test cases by hand" is a reasonable way to check whether a deterministic algorithm is correct, but I suspect most students would not assume that trying a few test cases is a good way to verify probabilistic algorithms.  For probabilistic algorithms, there's often no way to tell whether any particular output is correct; and you can't hand-crank enough examples to do any useful statistical test on the output distribution.  So, I'd prefer to focus on deterministic algorithms, as they get more cleanly to the heart of student misconceptions.

I'd like to teach the importance of proving your algorithm correct, and I'm hoping to use a few examples like this to help motivate proofs of correctness.  I would prefer examples that are relatively simple and accessible to undergraduates; examples that require heavy machinery or a ton of mathematical/algorithmic background are less useful.  Also, I don't want algorithms that are "unnatural"; while it might be easy to construct some weird artificial algorithm to fool the heuristic, if it looks highly unnatural or has an obvious backdoor constructed just to fool this heuristic, it probably won't be convincing to students. Any good examples?

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases.

Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$,
express $n$ as a sum of $d_i$:s with as few coins as possible.

A naive approach is to use the largest possible coin first,
and greedily produce such a sum.

For instance, the coins with value $6$, $5$ and $1$
will give correct answers with greedy for all numbers between $1$ and $14$
except for the number $10 = 6+1+1+1+1 = 5+5$.


Hamiltonian path and minimum spanning tree Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to find the Minimum spanning tree

but

in declarative language(specially prolog, we can apply same algorithm but those are limited) , If i want to find a minimum spanning tree on the same graph, If i collect all possible hamiltonian paths using findall/3 predicate then chose the one with smallest accumulated cost, is it then also a minimum-spanning-tree?

More specifically , Can we transform the problem of finding minimum spanning tree to the hamiltonian path finding problem but not in other direction?  Because normal algorithms return one specific minimum spanning tree of a graph but i am more interest in finding more than one minimum spanning trees.

No.  Every path is a tree, but not every tree is a path.  Therefore,  the minimum spanning path might be more expensive than the minimum spanning tree.

If you work through some examples you should be able to find an explicit counterexample.  I'll let you have the joy of finding it on your own.


How can we compute how many processes should be in memory at a time to make CPU utilization max? From the given formula, we can compute the CPU utilization:

  CPU Utilization = 1 - P^n

Where p is the probability of I/O and n is the total number of processes.

E.g, If we were to find CPU utilization if the computer has enough room to hold four programs in its main memory. These programs are idle waiting for I/O half of the time. that would be:

  CPU Utilization % = 1 - (.5)^4 = .93

But If CPU utilization was given e.g. 0.93 and probability of I/O e.g. 0.5 then how can I find n?

This is what I tried:

  Log(CPU Utilization) = Log(1) - nLog(.5)

  Log(.93) / Log(.5) = n

But that gives me about

  -0.10470

which is nowhere close to 4.

What am I missing?

Let $U$ indicate the CPU utilization in percent. What you have calculated is:
$$\log(U) = \log(1 - P^n) \stackrel{!}= \log(1) - \log(P^n) = \log(1) - n \log(P)$$

However, the equality marked with an exclamation mark is incorrect since $\log(a - b)$ is, in general, not equal to $\log(a) - \log(b)$.

The correct line of reasoning is restating the original equality as $P^n = 1 - U$ and then:
$$n \log(P) = \log(P^n) = \log(1 - U)$$
Thus:
$$n = \frac{\log(1 - U)}{\log(P)}$$

(Of course, this all assuming $P > 0$ and $U < 1$; otherwise, there is no (unique) solution.)

Tip: when reformulating mathematical expressions, always do it one step at a time, and question every single step! Else you are bound to make mistakes. (Source: personal experience)


Is a physical process with unbounded input Turing equivalent? Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A.

Now if this process has an unbounded number of states (for example we could think of an engine in a car and take the geographic coordinates of the car as its states) we could say that A is also Turing complete.

And therefore Turing equivalent.

Edit: Let's try to see more precisely how A could be considered as Turing complete even if the physical is continuous. Let's for example consider a car moved by an engine. And let's consider a planet where towns' names are built with the classic alphabet A, B, C etc. following rules that make the number of towns on that planet potentially infinite or unbounded. Now let's imagine that my vehicle is programmed by an algorithm to drive from town to town indefinitely. Let's call these towns the states of my system. Now I am certain (but please correct me if I am wrong) that my physical system is indeed Turing complete - and not just a push down automaton. Now if you accept that any state an observer (typically a physicist) will use to describe a physical system can be coded in a finite alphabet i.e. an integer (even if the physical world is continuous) then surely we could use the vehicle experience to say that in human eyes the physical world is Turing complete.

Is that correct?

No.  You can't just sweep everything under the rug like that.  The answer depends on what model of reality / physics you subscribe to.

If your model of reality is continuous (e.g., Newtonian physics), then it's not necessarily true that that every physical machine is computable by a TM.  TM's are discrete, not continuous; if physics is actually continuous, then your assumption is probably not correct.  (It might be true that the outcome of a process can be computed to an arbitrary degree of accuracy by a TM, but that's a subtly different statement.  TM's compute discrete values, not continuous values.)

If your model of reality is discrete and finite, then it might be true that that every physical machine is computable by a TM.  But now the number of states is not unbounded.

You can't have it both ways.  Or, to put it another way, you can't just assume things without justification.


Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm I have a collection of $n$ vectors $x_1, ..., x_n \in \mathbb{R}_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to the uniform norm. That is, find the (possibly not unique) set $W^* \subset \{x_1, ..., x_n\}$ such that $\left| W^* \right| = k$ and

$$W^* = \arg\min\limits_{W \subset \{x_1, ..., x_n\} \land \left| W \right| = k} \left\lVert \sum\limits_{v \in W} v \right\rVert_{\infty}$$

The brute-force solution to this problem takes $O(dkn^k)$ operations - there are ${n \choose k} = O(n^k)$ subsets to test, and each one takes $O(dk)$ operations to compute the sum of the vectors and then find the uniform norm (in this case, just the maximum coordinate, since all vectors are non-negative).

My questions:

Is there are a better algorithm than brute force? Approximation algorithms are okay.

One idea I had was to consider a convex relaxation where we assign each vector a fractional weight in $[0, 1]$ and require that the weights sum to $k$. The resulting subset of $\mathbb{R}^d$ spanned by all such weighted combinations is indeed convex. However, even if I we can find the optimum weight vector, I am not sure how to use this set of weights to choose a subset of $k$ vectors. In other words, what integral rounding scheme to use?

I have also thought abut dynamic programming but I'm not sure if this would end up being faster in the worst-case.

Consider a variation where we want to find the optimal subset for every $k$ in $[n]$. Again, is there a better approach than solving the problem naively for each $k$? I think there ought to be a way to use the information from runs on subsets of size $k$ to those of size $(k + 1)$ and so on.
Consider the variation where instead of a subset size $k$, one is given some target norm $r \in \mathbb{R}$. The task is to find the largest subset of $\{x_1, ..., x_n\}$ whose sum has uniform norm $\leq r$. In principle one would have to search over $O(2^n)$ subsets of the vectors. Do the algorithms change? Further, is the decision version (for example, we could ask if there exists a subset of size $\geq k$ whose sum has uniform norm $\leq r$) of the problem NP-hard?
Suppose we now know that our vectors $x_i$ all come from $\{0, 1\}^d$. Does anything change?

The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent_set_(graph_theory) or set packing.

One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$.  Note that $\|\sum_i v_i x_i \|_\infty \le t$ iff $-t \le \sum_i v_i x_{ij} \le t$ for all $j$, so this can be expressed using linear constraints.  Then, apply an off-the-shelf ILP solver and hope it terminates in a reasonable amount of time.

(The ILP solver will probably apply methods such as solving the associating linear program and then applying randomized rounding, so you don't need to implement it yourself.)

If $d$ is very small, it might be possible to solve the problem in something like $\tilde{O}(dkn^{k/2})$ time using meet-in-the-middle search combined with a nearest-neighbor data structure, but I haven't worked out the details, and I expect it won't scale to large $d$.


Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete I'm a little stuck on this question, any help would be appreciated!

Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is NP-complete.

HCE: Given an undirected graph G and an edge e of G, does G have a Hamiltonian circuit/cycle that uses e?

I've tried to approach this by showing that HC $\leq$ HCE, but I'm wondering if my approach is too convoluted.

EDIT:

I think I have a solution.
Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$,
and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat*}{1}
V'= & V\cup\{v_{\alpha},v_{\beta},v_{\gamma}\},v_{\alpha},v_{\beta},v_{\gamma}\notin V\\
E'= & E\cup\{(v_{\alpha},v_{\beta}),(v_{\beta},v_{\gamma})\}\cup\{\bigcup_{i\in\{\alpha,\gamma\},v\in V}(v,v_{i})\}
\end{alignat*}

Let the edge $e=(v_{\alpha},v_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v_{\alpha}$
and $v_{\gamma}$ are connected to all the vertices in $G$ and $v_{\beta}$.
$v_{\beta}$ has a degree of 2, and is only connected to $v_{\alpha}$and
$v_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v_{1},v_{2},...,v_{n}$.
Then $G'$ will also have a path $v_{1},v_{2},...,v_{n}$ with each
vertex only appearing once in the path. In order to turn this path
into a HC, the three additional vertices will have to be included.
In order to do so, the path has to be extended in either $v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$
or $v_{n},v_{\gamma},v_{\beta},v_{\alpha},v_{1}$. $G'$ thus have
a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP $\implies$$f(G)=G'\in$ HCE

Consider some $G'$ with a HCE along some path $v_{1},v_{2},...,v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$.
Since $G$ has vertices $V=V'\backslash{v_{\alpha},v_{\beta},v_{\gamma}}$,
$G$ has a HP along vertices $v_{1},v_{2},...,v_{n}$.

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time,
HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.

Given: a graph $G$, an edge $e$, and a length $k$.

Optimization problem output: a cycle of length $k$, containing $e$ (or none, if there is none).

Decision problem output: "yes" if such a cycle exists, "no" otherwise.

Now, it is obviously in NP, as you can simply check any answer to the optimization problem; see if it is a cycle, see if the cycle contains $e$, and check that the length of the cycle is $k$.

There are two easy ways to prove it is NP-hard. Imagine you had a magic algorithm, ${\rm M{\small AGIC}}(G,e,k)$, that can answer this for you.

Method 1 hint: In the k-SAT to DHC  (directed Hamiltonian cycle) reduction, aren't there some edges that must occur? (and don't these carry over to UHC (undirected Hamiltonian cycle)?)

More hints (mouseover):

   The reduction from k-SAT to DHC (directed Hamiltonian cycle) involved a root node, and a sink node. The sink node has an edge to the root node; and it is the only incoming edge to the root node; hence, the sink-root edge must be used in the DHC.

 Furthermore, in the reduction from DHC to UHC, each node gets split into 3 nodes, and the middle one is connected to the two outer ones with a single edge. Well, as a general rule, any degree-2 nodes make it easy to solve this problem (because the cycle must pass through it).

Method 2 hint: What happens if you pick a node. The Hamiltonian Cycle must pass through one of its edges. How many edges can a node have?

More hints (mouseover):

   Maybe you can solve a regular UHC with some calls to ${\rm M{\small AGIC}}(G,e,k)$.


Is this language depending on P = NP recursive? Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language

$$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$

A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?

If P=NP, then $L = (0+1)^*$ which is regular grammar. Hence, it is recursive.

If P!=NP, then $L = \phi $   which is also a regular grammar. Hence, recursive.

In both the cases, $L$ will be a recursive language.

PS I see a lotta GATE problems these days :D


Recurrence for recursive insertion sort I tried this problem from CLRS (Page 39, 2.3-4)

  We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively sort A[1... n-1] and then insert A[n] into the sorted array A[1... n-1]. Write a recurrence for the running time of this recursive version of insertion sort.

The recurrence I formed was

$$
T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\
       T(n-1) + \Theta(n) & \textrm{if } n > 1.
\end{cases}
$$

My reasoning

the base case of $n = 1$ the list is sorted so there is no work hence constant time.
For all other cases the time depends on sorting the sequence A[1...n-1] and then insertion into that sequence. Hence it should be their sum, i.e., $T(n-1) + \Theta(n)$.

I wanted to know whether the recurrence relation is correct. If not what are the mistakes and how to correctly formulate a recurrence relation?

According to the description you provided the recurrence is correct.
you might think it should be
 T(n)=\begin{Bmatrix}
1 & ,\ n=1\\
T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise
\end{Bmatrix}

because you can find the insertion place by using Binary-Search, however in order to actually insert the element you'll have to move away all the elements in the worst case.


Failing to solve a recurrence by induction My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which implies
$$0\geq 1$$
which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.
However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don't understand how should I be able to justify that, is this a scenario in which "induction fails" ? because I've never heard of such one.

Ok lets try solving this by substitution ,
$T(n) = 2T(n-1) + 1$
from this we know , $T(n-1) = 2T(n-2) + 1$
so $T(n) = 2(2T(n-2) + 1) + 1$
$T(n) = 2^2T(n-2) + 3$
lets substitute one more time
$T(n-2) = 2^2T(n-3) + 1$
$T(n) = 2^2(2T(n-3)+1) + 3$
$T(n) = 2^3 T(n-3) + 7$
Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$
So , for $k = n$
$T(n) = 2^{n}T(n-n) + 2^{n}-1$ , we know that $T(n-n) = T(0) = 1$
$T(n) = 2^{n} + 2^{n}-1$
so clearly , $T(n) = O(2^n)$


difference between minus and subtract microoperation While reading Computer Architechture book by M.Mano. I came across Arithmetics Microoperations sections which has two microoperations which confuses me a lot,

R3 <- R1 - R2      ( Minus Microoperation )

R3 <- R1 + complemented(R2) + 1   ( Subtract Microoperation ).

Can someone tell me the difference?

Suppose we're working with unsigned bytes, e.g. modulo 256.

Let's say R1 = 100 and R2 = 70. Direct subtraction should give us 100 - 70 = 30:

01100100
01000110 -
========
00011110

Modulo 256, subtracting 70 is the same as adding 256 - 70 = 186, because -70 is +186. The complement of 70 is 255 - 70 = 185, which is just one less. Therefore, the following sum produces 100 + 185 + 1 = 286 which is the same as 30 (modulo 256). Of course, the ninth bit 'falls off' when doing 8-bit arithmetic, so we get 30 as a result.

 01100100
 10111001
 00000001 +
 ========
100011110

So both methods give the same result, just in a different way.


Does there exist an algorithm to generate the production rules of CFG, given a sample production? Lets say, we provide the algorithm a set of tokens.

e.g.

x + y - z
x - x - x

It will then try to generate a CFG which fits all the provided examples

S -> S O T | T
T -> x | y | z
O -> + | -

It feels like a data compression problem but I could be wrong.

Does anybody know any existing literature or a starting point to solve this problem?

Does this problem have a name? What should I Google?

Any interesting grammar will generate an infinite language. There is always the trivial grammar with a start symbol that generates each example string on it's own. Checking if two grammars generate the same language, and thus in any sense finding "the smallest" (or whatever other measure you care about) grammar for a language is unsolvable. Inferring the grammar (in any meaningful sense) is probably impossible.


how to deal with mismatched tag bits in cache I was reading a textbook which describe general organization of cache as:

Then an exercise is, given m=32, C = 1024, B = 8,E = 4, S = 32, so s = 5, b = 3, therefore t = 32-5-3 = 24
I am a little bit confused here, since E = 4, we only need 2 bits to differentiate it, so t should be 2, if t is 24, isn't that we waste 22 bits?

For every cache set, there are $2^t$ blocks that can potentially be stored in there. However, only $E$ of them are actually stored at any particular time - typically, these would be the "most recently used" ones.
Incidentally, the whole reason for storing the tags themselves inside the cache is to be able to tell which ones are currently cached. The block's tag is not the "index" of a cache line, it's a $t$-bit identifier which is literally compared against every tag in the set in order to check whether this block is available or not.


Names of Softwares used for modeling Which tools or softwares are mostly used for the purpose of modeling a computer network?

I suppose you mean simulating computer networks? because modelling is different (you can model your network as a graph for instance). If this is the case have a look at these simulators:

NS2: built with C++, a discrete-event simulator, open source, and perhaps the most useful. You would need to use Tcl to write the script of the simulation experiments. New open source libraries are always added. I suggest it, however, i know many consider it a bet complex. Good knowledge in C++ is required if you want to maximally exploit it (at least to print your statistics and analyze them). The newer version is NS3 (i have nt used it yet), but from what I read, you can write your simulation experiments using python or c++.
Opnet: I am not a fan, and it is not open-source. I think there is a student-version.
simjava: if you are a java person, then use this. (I haven't used it, but i saw it being cited in many research papers).

but be careful before starting working with any "network simulator" because in many cases you don't need complex simulators. A simple C++, Java or Python code would be sufficient. (Actually, it is always a good programming exercise to create your own discrete-event simulator for a network).

If you are interested in distributed processors simulation (from a theoretical point of view), then I would suggest erlang (a programming language). It is functional language very similar to Haskell (created by Eriksson). it is very easy to create processes with identities. But even more, you can let the processors exchange messages by sending/receiving messages in a very simple way.


A closed form expression for # of inputs of a binary tree and its number of nodes Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes?

In case that the binary tree is a full tree, it is easy to find the number of input pins. In this case we will have $2^{H-1}$ nodes at the last level of the tree ($H$ is the height of the tree). Thus, the # of input pins will be $2^H$ because each node has 2 input pins.

How can we generalize this for a binary tree which is not a full trees?

There is a known expression linking the number of input pins and the number of nodes in a binary tree. It does not use the height of the tree.

For any binary tree the number of leaves equals the number of internal nodes plus one.

We can prove this by induction. Basis. A tree with one node has two leaves. Induction step. Whenever I replace a leaf by a new node, both the number of nodes and the number of leaves increase by one (we lose a leaf, and get two new leaves in return).


What is the complexity of Hamming nearest neighbor to a subspace ...? Suppose that $F_2$ denotes the field with $2$ elements. We are given $m$ vectors $\{x_1, \ldots, x_m\}$ in $F_2^d$ which are a basis for a subspace $W$.

Suppose we have a vector $v \in F_q^m$, and we want to find a $w \in W$ that is closest to $v$ in the Hamming metric.

What is the complexity of this problem, as a function of $md$?

1) It's clear that there is an algorithm taking exponentially many steps. $W$ has $2^m$ elements, each of which takes $d$ bits to describe. So we just search through them.

2) It's unclear to me if this problem is even in $NP$. I can verify in polynomial time whether one vector in $W$ is closer to $v$ than another vector in $W$, but I do not know how to verify if one is the closest (or minimizes the distance). I suspect that it is impossible to do. Can anyone outline or refer me to a proof that this problem is not in $NP$?

3) If it is in $NP$, then is it $NP$-hard?

I guess this is well known, and presumably already discussed on this webpage. I poked around for a bit and couldn't find it, however. A reference would be welcome.

Your problem is known as the nearest codeword problem, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the distance is at most a given distance. Regarding algorithms, I suggest taking a look at a paper of Alon, Panigrahy and Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem.


What's Big O of $\log(n+7)^{\log(n)}$? As part of my continual improvement plans, I'm reviewing algorithm analysis and I've hit a roadblock. I cannot figure out how to determine the Big O complexity of $\log(n+7)^{\log(n)}$. I've spent the last few days rolling this over in my head and I still haven't made any progress in solving it. Could someone tell me what the Big O of this algorithm is, and explain how you solved it?

If you meant what $\mathcal{O}((\log (n+7))^{\log (n)})$ is (so the power applies to the logarithm itself, not its argument), then we simplify that to $\mathcal{O}((\log (n))^{\log (n)})$; as per a suggestion by Saeed Amiri, here a proof for this equality:

Since $(\log (n))^{\log (n)}) \leq (\log (n+7))^{\log (n)})$ for all $n$, we have $\mathcal{O}((\log (n))^{\log (n)}) \subseteq \mathcal{O}((\log (n+7))^{\log (n)})$.

For the other direction, consider

$\qquad
\begin{align}
(\log (2n))^{\log (n)} &\leq c(\log (n))^{\log(n)} &\iff \\
\frac{\log(2n)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\
1+\frac{\log(2)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\
\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} &\leq c
\end{align}
$

What we now notice is that $\log n$ is a non-integer bound, so we can't directly expand to a polynomial here. We could if we knew that

$\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil}$

Therefore, a small proof of the monotonicity of that function:

$\frac{d}{dx}\left(1+\frac{\log(2)}{\log(x)}\right)^{\log(x)} = \frac{\left(\frac{\log (2x)}{\log (x)}\right)^{\log (x)}\left(\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)\right)}{x \log (2x)} \geq \frac{\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)}{x (\log (x))^{\log (x)}} > 0$

for all $x > x_0$ for some $x_0$ [specifically, for $x_0 = 2$; check the link to math in the comment section].

Since we now know that the function is monotonically nondecreasing for all $n > 2$, we can choose our $c$ slightly differently:

\begin{align}
\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil} &\leq c &\overset{\text{rewriting the polynomial}}{\iff} \\
\sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq c
\end{align}

Now we use the inequality $\binom{n}{k} \leq \frac{n^k}{k!}$ and see that
\begin{align}
\sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\lceil\log(n)\rceil)^i}{i!}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i \\
&= \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\log(2))^i}{i!} \\
&\leq \sum_{i=0}^{\infty}\frac{(\log(2))^i}{i!} \\
&= e^{\log(2)}
\end{align}

So we know that $\mathcal{O}((\log (n+7))^{\log (n)}) \subseteq \mathcal{O}((\log (n))^{\log (n)})$ since we can choose a finite $c$ in the above inequation.

If we try to express $(\log (n))^{\log (n)}$ as a power of $n$ now, we get

\begin{align}
n^{f(n)} &= (\log (n))^{\log(n)} &\iff \\
\log(n^{f(n)}) &= \log ((\log (n))^{\log(n)}) &\iff \\
f(n) \cdot \log(n) &= \log(n) \cdot \log (\log (n)) &\iff \\
f(n) &= \log (\log (n))
\end{align}

, and so we get $\mathcal{O}((\log (n))^{\log (n)}) = \mathcal{O}(n^{\log(\log(n))})$, if that is any improvement.

(Credit where it's due: I copied this way of expressing our function as a power of $n$ from here, so google can help with this stuff, sometimes.)

Now where does this place $\mathcal{O}((\log n)^{\log n})$ in terms of complexity? We know that $\forall c \in \mathbb{R}: \lim_{n \to \infty} \frac{c}{\log \log n} = 0$, which means that $n^c \in \mathcal{o}((\log n)^{\log n}) = \mathcal{o}(n^{\log \log n})$; the small $\mathcal{o}$ is intended here, it means that $n^c$ grows strictly slower than $n^{\log \log n}$. [A small remark about that at the end of all this; if this is not relevant to your needs or confuses you, you can - apart from those in the remark at the end itself - replace every $\mathcal{o}$ with $\mathcal{O}$, all statements will still be true.]

On the other hand, we have for any constant base $b > 1$:

\begin{align}
n^{\log \log n} &\leq b^n &\iff \\
(\log \log n) * (\log n) &\leq n * \log b
\end{align}

This tells us that instead of $n^{\log \log n}$ and $b^n$, we can equivalently compare $(\log \log n) * (\log n)$ and $n$ by just ignoring the constant (!) factor $\log b$. Using the limit rules for asymptotic notation as well as l'Hôpital's rule, we get

\begin{align}
\lim_{n \to \infty} \frac{(\log \log n) * (\log n)}{n} &\leq \lim_{n \to \infty} \frac{(\log n) * (\log n)}{n} \\
&\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2*\log n}{n} \\
&\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2}{n} = 0
\end{align}

Therefore we know $(\log n)^{\log n} = n^{\log \log n} \in \mathcal{o}(b^n)$ for any base $b>1$ of the exponential, meaning it grows strictly slower than any exponential function with constant base that we would be interested in. (What I mean by this is that in the analysis of the complexity of algorithms, we don't care about exponentials with negative bases because those aren't even real functions, much less functions over the naturals, or exponentials with bases between $0$ and $1$ because those all converge to $0$.)

In summary, we now know that in terms of complexity:

\begin{align}
\mathcal{O}(n^c) \subsetneq \mathcal{O}((\log n)^{\log n}) = \mathcal{O}(n^{\log \log n}) \subsetneq \mathcal{O}(b^n)
\end{align}

for any constants $c > 0$ and $b > 1$. What you have is a function strictly between polynomial and exponential growth.

Now the remark about Big-Oh and small-oh: $\mathcal{o}$ is a stronger statement than $\mathcal{O}$, because if $f(n) \in \mathcal{o}(g(n))$ then we know $g(n)$ grows strictly (meaning by a non-constant factor) faster than $f(n)$, but if $f(n) \in \mathcal{O}(g(n))$ we only know that $g(n)$ grows at least as fast as $f(n)$, so there may only be a constant factor. For example, $n \in \mathcal{o}(n \log n)$ and $n \in \mathcal{O}(n)$, but $n \not \in \mathcal{o}(n)$.


Order of given value in AVL tree given an AVL tree with $size$ value to any vertex $v$ in the tree (which is the size of the tree rooted in $v$), is it possible to tell for a given value in the tree, what its order in the sorted group in $log (n)$ time complexity?

Searching for the value in the tree is a $O(\log n)$ task.

Then, we can visit the path leading to the value, from the leaf (the value), to the root. At every intermediate node, we know how many other values there are further on the left: none, if we moved up from the left subtree, and left.size (which is assumed to be stored in each node) otherwise.

So, we can add all the relevant size values, counting up how many other values we have on the left of our value, so retrieving the order of the value in $O(\log n)$.


What is the difference between assignment, valuation and name binding? I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, which was not assigned a value whereas bound variable has its value assigned?

Binding has to do with giving names to things (or values) in a given well delimited context. Assignment is about storing things (or values) in some location (a variable). Another assignment can replace a previous value with a new one. Valuation consist in binding all the identifiers of a formal text with something (with a value).  In mathematics these identifiers are often called variables, which causes a confusion with the concept of variable (i.e. memory storage) in computer science.

Trying to give more intuitive details

Name binding attaches a meaning to identifiers within some part
(called scope) of the concerned mathematical or programming text.
This meaning can indeed be seen as a value in some domain when the
text is interpreted.

For example, if you declare foo as an integer variable, the value
attached to foo within the scope is an integer variable. An integer
variable may be seen informally a a container that can carry an
integer value, which may be changed. You can also see it as the address of a
place in memory where the content may be stored.

But if you declare foo as the integer 25, then whithin the scope,
any use of foo is identical to a use of 25. If you declare foo as an
integer constant, it cannot change and thus its value must be
specified.

Binding is attaching a name to some value that does not change within the scope of the name. An example is a legal documents stating that "for the purpose of this document, Mr. Brown, and the Smith family shall be called the beneficiary." The scope is the legal document. And everywhere in the document, the use of the word beneficiary means Mr. Brown, and the Smith family. You can see it as a definition of a local terminology. It has to do with giving names to things. Binding is about speaking, reading or writing. It is not about executing or moving values around: that corresponds to assignment.

A variable may be seen as a chunk of memory that can contain a value,
When you have a variable, you can change the value contained in this variable
contains with an assignment. If foo is bound to (or denotes) a variable in
the current scope, you can assign a value to foo, i.e. to the
variable denoted by foo, or read the value contained in that
variable. And you can change that value with a new assignment.

So binding is an operation that tells what is the meaning of names in
the text of the program or of the mathematical discourse. It is
static, in the sense that the text does not change. But
assignment is a programming concept that consist is storing a value in
a variable, i.e. a container, which is usually a place in memory. It
is a dynamic concept related to how (representations of) values are
stored in memory, which changes as the program progresses.

Note that a variable may exist independently of any name to which it could be bound. This is the case for an element of an array, to take a simple example.

In various contexts, one may consider expressions or texts that use
names that have not been defined. For example you can write
$(a^2-b^2)/(a-b)$ which is an arithmetic expression. Then you may
valuate the variables by associating an environment (you may read
approximately a scope) where the variables $a$ and $b$ are bound to some
values, for example 3 and 12, and be interested in the value taken by
the exression.  A valuation is such an association of a set of names,
each with a specific value. The name valuation is used more in formal mathematics, while assigment is a programming concept.


Reduction of Circuit Satisfiability to CNFSAT CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce Circuit-SAT to CNFSAT, it may result in an exponential algorithm but the instance map should be done in polynomial time.

How should we approach it then?

The exponential blowup when converting circuits to conjunctive normal form is avoided by introducing new variables to represent the output of each sub-circuit plus a simple set of rules represent each sub-circuit and force their output into the variables (see Tseitin transformation).  The size of the resulting CNF formula is linear to the size of the circuit, and grows linearly as the circuit size is increased.


Transforming the sorting problem into Dijkstra To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem.

I know you need to do create a graph based on the numeric values and that Dijkstra will traverse it in order, any help with the rest and how to evaluate it?
Thank you.

What you want is to reduce sorting (or element uniqueness) to the single source shortest path problem (rather than to Dijkstra's particular algorithm!) using an $o(n\log n)$ time reduction whose output has size $O(n)$. Then you will get a tight decision tree lower bound in the algebraic decision tree model for constant degree (Dijkstra's algorithm can be implemented using a linear algebraic decision tree).

Such a reduction is probably not known. See for example D.W.'s question on cstheory.


LSTM : What should I do if I am always getting an output too close to one value? I am training a model for ham and spam classification using LSTM. I am indicating the spams as 0, and the hams as 1. However, the dataset has much more hams than spams, so I tend to get an output very close to 1. That means the output is almost always above 0.5. So I have two questions about this :
Q1. Should I rate my answers based on the ratio between ham and spam in the dataset?
(etc. If there are 4000 ham and 1000 spam, then should I count an output higher than 0.8 as ham and lower than 0.8 as spam?)
Q2. If this is not a legitimate way, do you have any solutions for my problem?

The usual starting point is that if the score is above 0.5, classify it as ham, otherwise as spam.  If most emails are ham, then it makes sense that most emails give you a score above 0.5, so you have not said anything that indicates there is a problem.
This approach assumes that the proportion of ham vs spam in the training set is the same as the proportion at test time.
If that doesn't work, one standard approach is to choose a threshold, and everything with a score above the threshold is treated as ham, everything below as spam.  A standard way to set a threshold is, after you've trained the LSTM, choose the optimal threshold based on the training set (i.e., that maximizes the accuracy on the training set, etc.), or on a validation set.


An algorithm that finds ord(a) in $O(\log n)$ Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^*_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$).
I showed that if $n$ is the above then $φ(n)$ is power of 2.
For example:
let $m=k=2$ so $n=5\cdot4=20$ and $φ(20) = |{1, 3, 7, 9, 11, 13, 17, 19}| = 8 = 2^3$
Let $a=7$:
$7^1 \bmod 20 = 7$,
$7^2 \bmod 20 = 9$,
$7^3 \bmod 20 = 3$,
$7^4 \bmod 20 = 1$
so $\operatorname{ord}(7) = 4$
But I don't get how can I use that to find such algorithm.

Suppose that $\phi(n) = 2^m$; note $m \leq \log n$. The order of $a$ is thus $2^k$ for some $k \leq m$; in fact, it is the minimal $k$ such that $a^{2^k} \equiv 1 \pmod{n}$. You find find this $k$ by repeatedly squaring $a$.


Lambda Calculus simplification Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.

$$(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)(\lambda sz.sz)$$

I am lost with this.

if anyone could lead me in the right direction that would be much appreciated

Lambda terms are simplified by the β-reduction rule:
$$(\lambda x.M)N\,\rightarrow_\beta\,M[x:=N]$$

It means, if you have a subterm that looks like $(\lambda x.M)N$ (called redex) you can replace it by $M[x:=N]$, which is $M$ with $N$ substituted for $x$. The replacement $M[x:=N]$ is often called contractum. (Capital letters likes $M$ and $N$ are used to denote terms.)

In your case, the first reduction would be:

$$(\underbrace{(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)}_{\mbox{redex}})(\lambda sz.sz)
\rightarrow_\beta \underbrace{(\lambda n.(\lambda sz.(\lambda sz.sz)s(nsz)))}_{\mbox{contractum}}(\lambda sz.sz)$$
where we replaced $m$ with $\lambda sz.sz$. Note that we now have $\lambda sz$ inside $\lambda sz$ which isn't very convenient (yet allowed). It is better to rename bound variables ($\alpha$-conversion) to be distinct, for example to:

$$(\lambda n.(\lambda uv.(\lambda sz.sz)u(nuv)))(\lambda sz.sz)$$

Some notes:

Substitution applies only to free variables. Bound variables stay always intact.
Sometimes substitution is not directly possible. For example, you cannot substitute $x:=y$ into $\lambda y.xy$ because $y$ is bound under $\lambda$. You'd get $\lambda y.yy$ which would change the meaning of the term. So first, you have to rename the bound variable first, for example to $\lambda z.xz$ and then you can safely substitute $x:=y$ to get $\lambda z.yz$. The Wikipedia article gives formal definition of substitution and shows when it's necessary to rename bound variables.
Lambda associates to the right, so $\lambda sz.sz$ is $\lambda s.(\lambda z.sz)$.
Application associates to the left, so $xyz$ is $(xy)z$.


Are counting problems the same as problems involving listing all possible combinations? I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of possible combinations that add up to the target. So if my target is 5 and my set is { 1, 2, 5, 10 } then the solution is 4. More information can be found on: http://www.wcipeg.com/wiki/Change_problem

Although the solution to this particular problem is a single number, I instead decided to list all possible combinations. My reasoning was that if I list all combinations then it'll be easier for me to work out whether or not my algorithm is working. I assumed that these two problems are identical other than the obvious difference that the form of the output is different. But I really struggled with coming up with a dynamic programming solution for listing all combinations (recursive algorithm wasn't an issue). Since then I've been trying to find such an algorithm online but I'm surprised that it doesn't seem to exist. So I'm wondering if my assumption is incorrect and these are actually two separate problems.

I'm aware that when solving problems like this I should focus on just what's required to make things a little easier, but I didn't think it'd result in two completely separate problems. So there are actually THREE variants of change problem:

optimisation problem where I work out the smallest number of coins required to meet my target (the same algorithm can be used for both working out the minimum number of coins required AND also the actual minimum set of coins)
counting problem which lists number of possible combinations (can be solved using dynamic programming AND recursion)
listing set of possible combinations (can only be solved using recursion)

Is this correct? Are these separate problems?

Edit:
I should mention that I did come up with this algorithm that uses dynamic programming but I think it only works for certain sets of denominations hence why I said that I failed to come up with an algorithm.

int main()
{
    std::unordered_map<int, std::vector<std::pair<std::vector<int>, int>>> m;
    m[1].push_back({ { 1 }, 1 });

    const int target = 25;
    const std::vector<int> coins = { 200, 100, 50, 20, 10, 5, 2, 1 };

    for (int i = 2; i <= target; i++) // N
    {
        std::unordered_set<int> s;

        for (auto coin : coins) // M
        {
            if (coin > i) continue;
            if (coin == 1)
            {
                m[i].push_back({ { i }, 1 });
                s.insert(1); // constant
            }

            for (auto v : m[i - coin]) // N
            {
                if (s.find(v.second + 1) != s.end()) continue; // constant
                std::vector<int> temp_v = v.first;
                temp_v.push_back(coin); // constant
                m[i].push_back({ temp_v, v.second + 1 }); // constant
                s.insert(v.second + 1); // constant
                std::cout << i << ": ";
                PRINT_ELEMENTS(temp_v);
            }
        }
    }

    return 0;
}

The trick I'm using is that for a given target, each combination has a unique number of elements. E.g. for target 5 the combinations are {5}, {2, 2, 1}, {2, 1, 1, 1}, and {1, 1, 1, 1, 1} and as you can see the cardinality of each set is unique. This won't work if, let's say, the denominations were {1, 2, 3, 5, 6} and the target was 8. In that case I can store use arrays/vectors to represent combinations and store them in a set but I'd have to sort each vector first (so that they can be easily compared) and that increases the complexity of my solution quite a bit I think.

First of all note it is an NP complete problem if you are searching for a specific subset of denominations that sums to a particular integer.

You could solve this problem by brute-force simply generating all subsets of coins checking each time that the set adds up to the target. Time complexity of this algorithm is terrible, though there are pseudo-polynomial solutions too.

A counting problem which lists the number possible outputs doesn't have to be solved using recursive algorithm though a recursive algorithm in particular for generating subsets is much more shorter, intuitive, and readable.

Any recursive algorithm may be rewritten in a nonrecursive form. Similarly, there is nothing special with dynamic programming, it is just a way to solve a problem. But not all counting problems (or any problem) are solved or have to be solved using DP.

Also, once you generated a list of sequences or sets then of course you could count, in other words your listing solves corresponding counting problem. However, if you are interested just in the number of elements/sequences/sets then you don't have to list/generate sets. For example given $n$ you could compute that the total number of binary strings of length is $2^n$ without generating these strings. Computing $2^n$ is easier than listing all strings. Similarly, if you are interested in the number of subsets of size $m$ of a set of size $n$, then that value is $\binom{n}{m}$ which may be calculated using the Stirling's approximation. But listing all possible subsets is harder.

Thus counting problems ARE NOT always same as problems involving listing all possible combinations.


quicksort recurrence relation In Concrete Mathematics
Textbook by Donald Knuth and Oren Patashnik ,
ch.2 Sum ,sec2.2
He wrote:

  The average number of  comparison steps made  by quicksort when it's applied to $n$ items in random order satisfies the recurrence :
  $$C_0=0;$$
  $$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$

The question is how he get the relation :

$$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$?

Unfortunately, that textbook says nothing about how to deduce that particular recurrence relation, although it has plenty of examples on how to obtain a recurrence relation. In fact, I cannot understand $C_1=1+1+C_0 =2$, which says that we need two comparisons to sort 1 item using quicksort.

If OP's intention is emphasizing how he (meaning them, Donald Knuth and Oren Patashnik) get the recurrence relation, then I can only honestly say I have no credible idea beyond a few educated guesses.

If OP's intention is just to know how to deduce the recurrence relation, then the wikipedia item on quicksort is a nice answer, which I have copied below with minor modification to fit current question.

   Assume that there are no duplicates. When the input is a random permutation, the rank of the pivot is uniform random from 0 to $n − 1$. Then the resulting parts of the partition have sizes i and $n − i − 1$, and $i$ is uniform random from 0 to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the following recurrence relation.

$$
C(n)=n-1+{\frac 1n}\sum_{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac 2n}\sum _{i=0}^{n-1}C(i) $$

Please note that in the wikipedia item, $C(1)=1-1+0=0$, which say that we need no comparison to sort 1 item, which looks much more reasonable to me


Priority inversion in Hoare and Mesa monitors I understand the difference between Hoare and Mesa monitors. However I don't understand why priority inversion (when a lower priority process gets done before a higher priority process) is possible in the Hoare type but not possible in the Mesa type. Can someone explain this?

Unless you are careful priority inversion is possible in either Hoare type or Mesa type monitors.  This is because monitors implement a form of mutual exclusion (only one process can be "in" the monitor at a time), and mutual exclusion and priorities don't mix well.  Boosting the priority of the thread in the monitor, mitigates (but does not completely solve) the problem.  Priority boosting is typically done either with a priority ceiling, or priority inheritance, or both.

Hoare type condition variables introduce an additional priority inversion problem, though.  In Hoare type condition variables a low-priority thread may WAIT on the condition variable (thus giving up the monitor lock), then a high-priority thread could run, make the condition true and SIGNAL the condition variable.  In a Hoare type condition variable, the high priority thread immediately loses the monitor lock and gives it to the lower-priority thread.

In a Mesa type condition variable this particular priority inversion won't happen.  The low-priority thread WAITs on the condition variable, giving up the monitor lock.  Then a high-priority thread runs, makes the condition true and NOTIFYs the condition variable.  The high-priority thread does not give up the monitor lock, and keeps running.


Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce the recurrence relations in context of a branching algorithm:

$T(n) \leq T(n-t_1) + T(n-t_2) + \dots T(n-t_r)$

To solve this equation we assume $T(n) = c^n$, then $c$ should be a (complex) root of $x^n - x^{n-t_1}-x^{n-t_2}-\dots-x^{n-t_r}=0$ ⇾ the running time of this branching algorithm is thus governed by the largest (real) root of this equation. We call $\tau(t_1,t_2,\dots,t_r)$ the branching factor of these $t_r$ numbers which is thus the largest positive real root of the corresponding equation. The branching vector is defined as $t = (t_1,t_2,\dots,t_r)$

I am mainly interested in editing such branching algorithms in order to reduce the running time. Often, I get in a situation where I can either do:

(1) Remove a branch entirely (i.e. make the number of arguments in the branching factor lower)

(2) Have a choice between two branching vectors, say $x$ and $y$. The branching vectors are equal except for two elements: we have $x_i < y_i$ and $x_j > y_j$ with $i \neq j$. ($x_i$ is thus element at position $i$ of branching vector $x$).

I have two questions:

(1) Intuitively, it seems to me that if I remove a branch entirely, this lowers the running time of the algorithm. We essentially try to find the number of leaves of the branching algorithm; per definition if we remove an entire branch the number of leaves should lower, hence should the running time. However, I can find no such theorem/proof in the literature.

Mathematically, you essentially have a equation of the form $\sum a_i x^{n - c_i} = 0$, where we only care of the largest positive real root. Now if I create the same equation, but now lower one of the $a_i$ values, does my positive real root decrease? I assume this is some fundamental/elementary theorem somewhere but cannot seem to find it.

(2) The book has a Lemma (2.3): $\tau(i,j) \ge \tau(i + \epsilon, j - \epsilon)$ for all $0 \le i \le j$ and all $0 \le \epsilon \le \frac{j-i}{2}$. I cannot use this lemma in most cases of this problem. I am going to assume that I will just have to calculate the roots for each branch, right? And then take the minimum? Or is there some more fundamental theorem to this?

Let's start with your first question. You are considering two polynomials,
$$
P(x) = x^n - a_r x^{n-t_r} - a_{r-1} x^{n-t_{r-1}} - \cdots - a_1 x^{n-t_1}, \\
Q(x) = x^n - a_r x^{n-t_r} - \cdots - b_i x^{n-t_i} - \cdots - a_1 x^{n-t_1},
$$
where all $a_i$ are positive, and $0 < b_i < a_i$. Thus $Q$ results from replacing the term $-a_i x^{n-t_i}$ with $-b_i x^{n-t_i}$.

Let $\tau$ be the largest real root of $Q(x)$; note that $\tau > 0$. Thus
$$ P(\tau) = Q(\tau) + (b_i - a_i) \tau^{n-t_i} < 0. $$
On the other hand, $\lim_{x\to\infty} P(x) = \infty$. Therefore $P$ must have another root beyond $\tau$.

You can try attacking your second question using similar reasoning.


Meaning of , and ; in relation to defining context I have seen use of , and somewhere use of ; when defining context :

$$\dfrac{\phi \ ,  \ \Gamma \  \vdash }
        {}
       $$

somewhere else i have seen :

$$\dfrac{\phi \ ;  \ \Gamma \  \vdash }
        {}
       $$

What is the difference between both. I have read something like extension of context. Then what second one means.

You'd have to check whatever you're reading, but the way I've most commonly seen it used is to separate different contexts.  The rules will then behave differently if a variable or formula is in one context versus another.  mobileink mentioned substructural logics which are often formulated with a context for linear variables and a different context for non-linear variables.

However, ; could simply be being used to separate other things so you don't confuse it with context extension.  Or it could just be part of a term.  Or it could be some operator on contexts distinct from context extension.  Or it could just be this author decided to use ; instead of , for context extension.  Again, what it means is whatever it is defined to mean, which may be nothing on its own.  For example, used to separate different contexts, it's just part of the syntax of a judgement, e.g. the judgement may be 3-ary relation $(-);(-)\vdash (-)$ in which case it makes no more sense to ask what ; means than it would to ask what $.$ means in $\forall x.P(x)$.  See my answer to a similar question for more elaboration on this.


A hangman variation: determining a string by guessing substrings contained in it I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I will get a positive result, and if I guess "arb" I get a negative result. When I guess the word I win.

My first question is if anyone knows whether this problem is known and has been solved before?

I came up with an algorithm, which seems to operate in sub-quadratic* number of guesses (by input length) by iteratively generating graphs of 1..n length substrings. In this graph the nodes are the positively guessed k-length substrings and the edges connect to possible continuations. New k+1-length guesses are generated by appending to these possible continuations, giving one new guess per edge. Once the graph becomes a loop you can try appending all nodes in order, until you solve the word. Here's a Java implementation.

My second question is if anyone can help me figure out the time complexity of this algorithm? As there can be at most n graphs, with n being the input length, each having up to n^2 edges, then multiplied by the n time needed for the substring function gives an upper bound of O(n^4). This is assuming a constant-sized alphabet. However, I doubt this is the tightest upper bound possible.

*experimentally, with a constant-size alphabet

This problem can be solved with O(n * s) queries, where n is the input length and s is the alphabet size. First, determine some single character substring by trying all possibilities. Then extend that into a length 2 substring by trying to append characters to it. Continue extending the string by appending until it's not possible anymore. If it's not possible to append anymore and the length is not n, do the same strategy but prepending. In this way you reach the length n substring in n steps that each take at most s queries.


"taintedness" vs. "taintness" In the context of information flow, when you talk about the property of variables being tainted, do you speak about "taintness" or "taintedness"? Both occur online, both sound weird to me.

An example from http://www-verimag.imag.fr/~potet/PUBLI/mdv10.pdf:

  To achieve that, we propose to perform a taint dependency analysis
  whose objective will be twofold: 1) to compute the variable taintness
  at each program location; 2) to extract from the program source the
  whole dependency chains between each vulnerable statement and the
  corresponding inputs leading to this vulnerability.

Which should you use?  Neither.  Personally, I think the words "taintness" and "taintedness" both look awkward.  I would recommend rephrasing the sentence to avoid using either of those words.   Instead, you might try to use something like "whether the variable is tainted".  Or, if you desperately need a noun phrase and can't make the prior suggestion work, try something like "taint status".

For example, I might rewrite the quoted sentence as something like:

  To achieve that, we propose to perform a taint dependency analysis whose objective will be twofold: 1) to compute which variables are tainted at each program location; 2) to extract from the program source the whole dependency chains between each vulnerable statement and the corresponding inputs leading to this vulnerability.

(I added italics to highlight the part that I changed.)


Recurrence: space complexity to Tournament Method Tournament method have this structure to found min and max (function getMinMax):

  mid = (low + high)/2;
  mml = getMinMax(arr, low, mid);
  mmr = getMinMax(arr, mid+1, high);

  /* compare minimums of two parts*/
  if (mml.min < mmr.min)
    minmax.min = mml.min;
  else
    minmax.min = mmr.min;

  /* compare maximums of two parts*/
  if (mml.max > mmr.max)
    minmax.max = mml.max;
  else
    minmax.max = mmr.max;

Time complexity is , but how can I found the space complexity? You stack  values, plus  values, plus  values... until  values. So  (log n times). . That's right?

First of all, when talking about space complexity, we need to make sure what exactly we are counting. There are two main issues:

Are we counting the space taken by the input?
How much space does a variable like mid or mml take? How much space does the return address take?

Regarding the first issue, usually we're not counting the space taken by the input; this space should be accounted for in the procedure creating the array. This convention is important in complexity theory for handling space complexity classes with small working space, and also makes practical sense.

Regarding the second issue, we actually have two kinds of variables here:

Addresses – the return address, mid, and perhaps other temporary values.
Array elements – the two components of mml and mmr.

The usual convention counts machine words rather than bits. Without explaining what exactly machine words are, it is usually assumed (and practically justified) that addresses take $O(1)$ machine words.

Regarding array elements, it depends on the type of the array. Here presumably the array elements are machine integers of machine floating points, and so they also take $O(1)$ machine words.

Having clarified these issues, let us get back to the algorithm. When analyzing the time or space complexity of an algorithm, we usually measure the complexity with respect to the input size $n$ (in machine words). In this case, we can identify the input size with the size of the array (measured in number of elements), although the input is actually a bit larger.

Suppose for simplicity that $n$ is a power of 2, say $n = 2^m$. When we trace the execution of the algorithm, we discover recursive calls for the following subarrays are made:

$A[0,2^m)$
$A[0,2^{m-1})$
$A[0,2^{m-2})$
$\ldots$
$A[0,1)$

(Here $A[a,b)$ consists of the elements $A[a]$ up to $A[b-1]$.) After the call on $A[0,1)$ executes, we get another call to $A[1,2)$, and so on and so forth.

At the particular point in time illustrated in the call stack above, the call stack is $m+1$ levels deep, and so the stack consists of $\Theta(m)$ machine words. That already shows that the algorithm requires $\Omega(m)$ space. Since the space taken by local variables is part of the call stack, the memory usage at any point in time is big Theta of the depth of the call stack (since each level requires $\Theta(1)$ machine words). It's not hard to check that the call stack never gets more than $m+1$ levels deep, and so the space is $\Theta(m)$.

When $n$ is not a power of 2, a very similar analysis shows that the space usage of the algorithm is $\Theta(\log n)$.


Are the sets of all finite automata and pushdown automata countable? So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering that we can build all of them with Turing machine?

The set of all finite automata is indeed countable, but that has nothing to do with the set of all TMs being countable. The two models are only related by the set of languages they accept, but both have infinitely many machines per language so we can't immediately conclude anything about the sets of machines.

You can prove countability with the usual means: working from the formal definition of FAs (something like $A = (Q, \Sigma, \delta, Q_F)$), construct an injection into $\mathbb{N}$. That's tedious, but elementary. For PDAs, it works just in the same way.


Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2) I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I thought I'd solicit your feedback. I appreciate any help with this.

Problem. We have a data structure supporting some number of operations. Given a sequence of n such operations, we're to determine the amortized cost of each operation using the Accounting Method [CLRS, 17.2]. The actual cost of $i^{th}$ operation is defined as follows:

$$
cost(i) =
\begin{cases}
i  & \text{if $i$ is an exact power of 2} \\[2ex]
1 & \text{otherwise}
\end{cases}
$$

Assume that exact powers of 2 form the sequence: $1, 2, 4, 8, \ldots$.

Solution. (My attempt) For the sake of concreteness, consider a sequence of 10 operations:

$$
\begin{array}{c|ccc}
i & cost(i) & notes\\
\hline
1 & 1 & 1 = 2^0\\
2 & 2 & 2 = 2^1\\
3 & 1 &\\
4 & 4 & 4 = 2^2\\
5 & 1 &\\
6 & 1 &\\
7 & 1 &\\
8 & 8 & 8 = 2^3\\
9 & 1 &\\
10 & 1 &\\
\end{array}
$$

The approach is predicated on the observation, based on this data, that between consecutive power of 2 operations (say, 1 and 2 or 2 and 4 or 4 and 8, etc.) there are exactly $i-1$ unit-cost operations. For example, if $i=1$, then between operations 1 and 2 there should be $1-1 = 0$ unit-cost operations and indeed there are none. Another example, consider $i=4$. We again verify that between 4 and 8 there are $4-1 = 3$ unit-time operations.

Based on that hypothesis, we assign the following "charges" ($\widehat{cost}$) to each of the operations:

$$
\widehat{cost}(i) =
\begin{cases}
i + (i - 1)  & \text{if $i$ is an exact power of 2} \\[2ex] \tag{$\alpha$}
0 & \text{otherwise}
\end{cases}
$$

The idea is that each power of 2 operation pays for itself (that's the $i$ summand) and leaves credit just enough to cover the $cost$ of the next $(i-1)$ unit-cost operations. Visually:

$$
\begin{array}{c|ccc}
i & cost(i) & \widehat{cost(i)} & \text{"remaining credit"}\\
\hline
1 & 1 & 1 & 0\\
2 & 2 & 3 & 1\\
3 & 1 & 0 & 0\\
4 & 4 & 7 & 3\\
5 & 1 & 0 & 2\\
6 & 1 & 0 & 1\\
7 & 1 & 0 & 0\\
8 & 8 & 15 & 7\\
9 & 1 & 0 & 6\\
10 & 1 & 0 & 5\\
\end{array}
$$

At the end of the sequence, we're left with 5 units of credit, which will pay the price of the next 5 unit-cost operations ($i = 11, \ldots, 15$).

The amortized cost of a given operation is $i + (i - 1)$, which is bounded by $2n$. The book has a $3n$ in the analysis, so I'm wondering where I'm messing up.

An amortized cost is just the average cost of a sequence of $n$ operations (in the worst cases). If I remember correctly, its definition is defined as

$$
\hat c(n) \sim \frac{\sum\limits_kc(k)}{n}
$$

Now,
$$
\hat c(n) = \begin{cases}
2n - 1 & \text{if $n$ is a power of 2} \\
0 & \text{otherwise}
\end{cases}
$$
obviously fits that description. In the same vein, so does
$$
\hat c(n)_{\text{alt}} = \begin{cases}
n & \text{if $n$ is a power of 2} \\
1 & \text{otherwise}
\end{cases}
$$
which is just our original cost function ;)

In fact, many such cost functions exist. However, none of them clearly spells out a tight bound on the cost of any arbitrary instruction.

For example, to say that $\hat c(n) \sim 2n$ is to say that the total cost of $n$ operations is approximately $\sum_k^n 2k = 1 \times n^2$. On the other hand, the true total cost of $n$ operations is
\begin{align*}
\sum_k c(k) &= n + (2^0 - 1) + (2^1 - 1) + \dots + (2^{\lfloor\log_2(n)\rfloor} - 1) \\
&= n + 2^{\lfloor \log_2(n) \rfloor + 1} - 1 - (\lfloor\log_2(n)\rfloor + 1) \\
&\le n + 2n - \log_2(n) - 2 \\
&\le 3n
\end{align*}

This means that a good "amortization" technique here would give an amortized cost of $\hat c(n) = 3$ for any arbitrary $n$.

Now, why is $\hat c(n) = 3$ more "elucidating" than $\hat c(n) = \text{n is a power of 2} ~?~ 2n - 1 ~:~ 0$? Well, because it gives a uniform amortized value for every $n$. This then forms the (unspoken) cardinal rule of amortized runtime analysis:

  Good amortized cost functions are not piecewise.

Why? If $\hat c(n) = \square$ uniformly, then we can easily say that each and every operation is bounded by the same $\square$.

Now, I can definitely hear some readers protest: "but I see case analyses in CLRS itself!" Do you? Well, for algorithms with multiple operations (say PUSH, POP, and MULTIPOP), then we need to give a cost function for each individual operation. However, the amortized cost function given for each operation is "continuous"!

Fret not, this is a pretty common problem. I haven't gone through CLRS myself, but I've stumbled upon these confusions as well when I first went through this technique.

We've already seen that $\hat c(n) = 3$ provides a valid bound, but it doesn't really give us any intuition about the problem (beyond pushing around some inequalities). Why 3? How do we get to that answer without working with (or around) arithmetic and geometric series?

There are good news and bad news. Bad news first: the most general framework you have here is the vague phrase that you already know; just figure out how much you have to pay upfront so you can cover the up to the next "big shock." While this might not seem like very much to work with, it does give us some general intuitions: the important aspect of the problem is not only the magnitude of these shocks (heh), but also their location.

In our case, we know that the location of these shocks are logarithmically distributed, which means that most of the time, you just incur a cost of one. However, these shocks are also pretty big, so you'll need to pay enough up-front to cover for them. In particular, after $2^k$ operations, you'll have to pay at least $2^k - 1$ operations and a further $2^k$ operations. This immediately suggests that $2^{k} + 2^{k} - 1 \le \hat c(2^k)$. Following a similar argument, we also have $\hat c(2^k) \le 2^{k} - k + k \times 2^k$. This refines our bound to $2n -1 \le \hat c(n) \le \lfloor \log_2 n + 1\rfloor n - \lfloor \log_2 n\rfloor$. After this, you can keep refining this bound until you get something as tight as possible. Unfortunately, there's really no way to do this unless you stumble onto the geometric series and realize that $\sum_k^n 2^k = 2^{n+1} - 1$, but at least this should give you a way to make gradual progress in your analysis.

Good luck!


Why is selection sort faster than bubble sort? It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort even though both of them have:

Worst case time complexity: $\mathcal O(n^2)$
Number of comparisons:      $\mathcal O(n^2)$
Best case time complexity :

Bubble sort: $\mathcal O(n)$
Selection sort: $\mathcal O(n^2)$

Average case time complexity :

Bubble sort: $\mathcal O(n^2)$
Selection sort: $\mathcal O(n^2)$

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted.

To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books.  I'll use results from Knuth's Art of Computer Programming.

Average number of comparisons:

Bubble sort: $\frac{1}{2}(N^2-N\ln N -(\gamma+\ln2 -1)N) +\mathcal O(\sqrt N)$
Insertion sort: $\frac{1}{4}(N^2-N) + N - H_N$
Selection sort: $(N+1)H_N - 2N$

Now, if you plot those functions you get something like this:

As you can see, bubble sort is much worse as the number of elements increases, even though both sorting methods have the same asymptotic complexity.

This analysis is based on the assumption that the input is random - which might not be true all the time. However, before we start sorting we can randomly permute the input sequence (using any method) to obtain the average case.

I omitted time complexity analysis because it depends on implementation, but similar methods can be used.


Research regarding algorithm generation/discovery/heuristics Say I have a specification of preconditions and postconditions for a function. Is there a field of computer science that studies the automated generation of functions that satisfy those specifications?

For example:
Preconditions:

I is a list
Q is a binary relation specifying a total order on the
elements in I

Postcondition:

O is a list
There exists a bimap B (and its complement B') such that

O[B[j]] = I[j], and
O[j] = I[B'[j]],
for every j, 0 <= j < n,

For every x, 0 < x < n, Q(O[x - 1], O[x]) is true.

The set of functions that satisfy this (I hope unambiguous) specification are the sorting algorithms. So, how do we get a computer to take this specification, and give us a sorting algorithm?

The phrase to look for is "program synthesis".  There's lots of literature in the programming literature on this topic; I suggest using Google Scholar to search through the literature and find relevant publications.

These days one hot approach is using "program sketching".  In program sketching, the programmer specifies a template for the code: partial code, with some holes left blank.  The tool then automatically tries to fill in those holes in a way that is consistent with the preconditions/postconditions, or is consistent with some provided test cases.  There's lot of literature on this topic.  For an introduction to this line of work, I'll suggest the following tutorial:

The Sketching Approach to Program Synthesis.  Armando Solar-Lezama.  Tutorial at PLDI 2012.


Proving a language is not regular using the Myhill-Nerode Theorem I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.

$\{0^{n}1^{m}0^{n} \mid{} m,n \ge 0\}$
$\{w \in\{0,1\}^{\ast}\mid w\text{ is not a palindrome}\}$

For the first question, I did the following:

I considered the set $\{0^n1^m \mid{} m,n\ge 0\}$. To prove that this set is pairwise distinguishable by the original language, I said that for all $m$ and $n$, $0^n1^m$ is distinguishable from all previous $0^i1^m,\:0\:\le i\le n-1$ because there exists a $z=0^n$ such that $0^n1^mz$ is an element of the original language but $0^i1^mz,\:0\le i\le n-1$ is not an element of the original language.

I first want to ask whether this was indeed the correct way to do the proof?

I am also quite confused for the second question as I can't even seem to find a string that is part of the language but is a palindrome. All the strings other than the empty string in that language are not palindromes. So I am quite confused on how to approach the problem.

Any help would be highly appreciated!

The words $0^n1$ are pairwise distinguishable, since $0^n10^n$ is a palindrome but $0^n10^m$ isn't (for $n \neq m$).

With a bit more work, you can show that in fact all words are pairwise distinguishable. See for example here or here.


Can an optimization algorithm be "universal"? I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.

In trying to answer this question, I realized that I don't know enough about optimization theory to answer a more general question: Just how interchangeable are heuristic approaches for solving computationally hard optimization problems?

Coming from an ML background, I'm reasoning by analogy with supervised learning problems: In ML, some methods like Neural Networks (with a sufficient number of layers) or Support Vector Machines are universal, in that they can approximate any shape decision boundary or regression function up to an arbitrary level of precision.

Are there equivalent algorithms in optimization theory that can be used to solve any optimization problem (linear, non-linear, continuous, discrete, etc...), e.g. can Genetic Algorithms or Particle Swarm Optimization be thrown at any optimization problem and give us a reasonable solution? SGD is used to solve NP-Complete problems (i.e. training a neural network) - does that mean that it can be used for any optimization problem?

I assume that the reverse is true: Not all optimization are universal, for example methods that work for LP or QP don't necessarily work for harder problems.

If it is indeed the case that some optimization algorithms are universal, is Bayesian Optimization one of these universal algorithms? Can be used to approach LP, QP, MIP, TSP, and NP-Hard problems in general?

There is no heuristic that is "universal" in practice.  Which heuristic works best in practice often depends on the specific problem you're dealing with.  There's no one "silver bullet" heuristic that works great on every optimization problem.


If the two generals problem is unsolvable how can we human beings agree on things? If the two generals problem is unsolvable how can we human beings agree on things?

I mean, we communicate everyday and have the same limitations as any communication problem handled by computer science. Why doesn't it affect us?

I disagree with other answers that the communication channel needs to be modelled differently. Malice is irrelevant, simple lost messages with any non-zero probability are sufficient to create the two generals problem. e-mail and IM, for example, have a low but not zero chance of dropping messages. Phone calls can suffer interference, so as with the two generals problem you need to somehow confirm whether the other person heard what you said, ad infinitum. And yet I frequently use these channels to make agreements with other people.

What the insoluble "two generals" problem fails to solve, is to get guaranteed common knowledge. In real life we don't require formal common knowledge in order to proceed. Therefore the goal in most practical situations needs to be described differently from the goal in the two generals problem.

We settle for agreement being "sufficiently likely". I might not be willing to attack unless I'm certain you will attack, but I'm willing to walk to the coffee shop to meet you provided that the probability of a communications failure isn't grossly higher than the probability of you failing to arrive due to traffic. Unlike the generals, I'll take a chance on you meeting me.

If you've ever had someone explain something three times to you in different ways when you got it the first time, or ever had someone ask you to confirm something that you've already confirmed twice, then it's because you reached your threshold of "sufficiently likely" before they reached theirs.

Take your pick of psychology, philosophy, or evolutionary biology as the correct realm in which to look for an answer to the next question, why we don't really need a full guarantee of common knowledge :-)

It also relates back to practical problems in computing. For example when we use a single-error-correcting code to "validate" that a symbol in a message has arrived correctly, all we're doing is accepting that the probability of a double-error is negligible for the time being. Then later in the protocol we might have a CRC, to further reduce the probability of undetected error. None of this solves the two generals problem, but it is sufficient for me, my bank and a merchant all to "agree" that a credit card transaction has occurred, with a small probability that we disagree.


One-shot Private Randomness Extractor Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping
$f:\mathcal{Y}\to \{0, 1\}^k,$ for some integer $k>0$ such that
$$f(Y)\perp X, \qquad \text{i.e.}, \quad f(Y)\text{ is independent of } X,$$ and
$$H(f(Y))>0.$$ The second condition is just to rule out the degenerate functions $f$.

For example if $X\sim\mathsf{Bernoulli}(p)$ and $P_{Y|X}$ is an erasure channel* with erasure probability $\delta>0$, then $f:\{0,\text{e},1\}\to \{0,1\}$ where $\text{e}$ is the erasure, defined as
$$f(1)=f(0)=1,\qquad f(\text{e})=0,$$ satisfies the above condition.

What is a necessary and sufficient condition on $P_{XY}$ for the existence of such deterministic map?

*By erasure channel, I mean the following conditional distribution:
$$P_{Y|X}(y|x)=(1-\delta)1_{\{y=x\}},$$ and
$$P_{Y|X}(\text{e}|x)=\delta, ~~~~\text{for}~~~~x=0,1.$$

If such a mapping $f$ exists at all, there always exists such a mapping with $k = 1$: you can always collapse a larger function in such a way that doesn't make the mapping constant. In other words, a mapping $f$ exists if there is some non-trivial event $E$ depending only on $Y$ which is independent of $X$. The converse is also true.


Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free? I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma.

I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but someone told me I might want to consider another string. Why is this? Any way in which I divide the string and then pump the string results in the balances between the $w^r$on either side of the string being thrown off, no?

For $p>0$, you can always split $0^{3p}$ into $uvxyz$ such that $u=x=\varepsilon$, $v=0$, $y=0^2$, and $z=0^{3p-3}$. Such a split clearly satisfies $|vxy|\leq p$, $|vy|\geq1$. Finally, for all $n\geq0$, $uv^nxy^nz=0^{3(p-1+n)}$, which is in $L$, since $0^{3m}\in L$ for all $m$.

Since you want to show, that for an arbitrary split satisfying the length conditions, there is some $n$ for which $uv^nxy^nz\notin L$, the choice of $0^{3p}$ is unfortunate.


Faster way of calculating how many ways can $2n$ elements be paired? So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$.

$(2n-1)*(2n-3)*...*1$
but my professor claimed it can be done much faster in algorithmic sense, but I don't really see the way to do so. Any hints? Thanks!

There is one algorithmic improvement if $n$ is large and you want to express this number for example as a decimal or binary number without any rounding errors: Let's say you have $n$ equals one billion. You will do about 500 million multiplications, and if you do this in a straightforward way, you will multiply various numbers from 1 to a bit over 4 billion digits by some small number. Multiplying an $n$ digit number by a small number takes $O(n)$ steps, so your product all in all takes $O(n^2)$ steps.

It's faster if you calculate 250 million products of up to 9 digit numbers giving 250 million 18 digit numbers, then 125 million products of 18 digit numbers giving 36 digit numbers and so on, until finally you multiply two numbers of 2 billion digits each. Multiplying $k$ digit numbers can be done in $O (k \log k)$ instead of $O (k^2)$, and therefore the total work is $O (n \log^2 n)$.

A completely different improvement for large $n$ is to use the Stirling approximation $n! \approx n^n \mathrm{e}^{-n} (2\pi n)^{1/2}$, and substitute that in the formula in Yuval's comment. Obviously that gives an approximation only.


Why do some architectures use a CMP instruction before branching while others just branch? My initial guess is that you will have more instruction space for the immediate in your branch instruction when you first use a CMP instruction. However, you have to use 2 instructions each time you want to branch: a CMP and then the branch instruction.

So are there any advantages to using CMP?

Every architecture may offer different flags and condition registers. It also may implement operations (e.g. addition) affecting these flags one way or another. Say an architecture A you mention does not need CMP; this means all flags and registers are set predictably in an orthogonal fashion for each operation (or else that particular jump/branch instructions must be enforced). An architecture B could not have this guarantee and use different flags for each operation and/or offer more generic jump/branch - then B offers a CMP instruction that makes sure flags are set as expected by the programmer/compiler.

There are several differences between A and B. For example, an architecture may offer more registers (X, Y not just ACC) which you could directly run operations on (therefore appropriate CMP instructions makes sense to select register etc). Architecture A may have to implement additional logic or even offer more flag registers to accomplish its aforementioned guarantee. Some processors want an instruction to do minimal register transfers/operations to maintain a given command execution cycle/clock.

These are a few things there are of course much more that turn this and other design choices to a successful architecture for compilers and intended users. Each choice reflects on the instruction set. What is important is to take advantage of each instruction the way it is intended in the best way and produce correct and fast code easily even in an automated way (from compiler).

All of the above possible reasons aside, note that you do not always have to use CMP (or have two instructions to branch) if your flags, condition registers are treated as you need them from the previous operation - you use CMP only if previous operation set flags are not set as expected for a subsequent branch.

Indeed sometimes in assembly written by humans (not compiler) we often just add a CMP in there, even if unnecessary, just to make sure because we may not remember the flags each operation affects (so that is a waste and not the way CMP is intended at least not for performance programming)!