Logic behind choosing the exponent bias as $2^7 -1$ instead of $2^7$ in $32$ bits IEEE-754 floating point representation The $\text{IEEE-754}$ uses $32$ bits to represent single precision floating point numbers. The partitions of the register are as follows:
        Biased
 sign  Exponent  Mantissa
+-----+--------+---------+
|1 bit| 8 bits | 23 bits |
+-----+--------+---------+

Now in general $8$ bits can represent $2's$ complement numbers in the range $-2^7$ to $2^7 -1$. Now the bias is added to aid in comparison purposes. In general to make the entire range non negative we can add a bias of $2^7$ to the exponent so that the range becomes $0$ to $2^8 -1$. But again the IEEE uses implicit normalization of mantissa as a result of which we need explicit representation of $0$ or $\pm \infty$. So biased exponent $E'=0$ or $255$ is reserved for this purpose.
So we have,
$$1 \leq E' \leq 254$$
$$\implies 1 \leq E+127 \leq 254$$
$$ ,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(where E is the actual exponent)}$$
$$\implies -126 \leq E \leq 127$$
But had we used a bias of $128$ instead of $127$ then after reserving $E'=0 \text{ or } 255$
We would have got $$ -127 \leq E \leq 126$$
So my question is, Is there any technical reason for choosing $2^7-1$ instead of $2^7$ or it is just a convention followed by IEEE? Because using the bias of $128$ we could as well allow the required reservation for the special numbers, I see that the only difference comes in the range of the exponent, which shall become $[-127,126]$ instead of $[-126, 127]$

Jerome T. Coonen, "An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic," Computer, Vol. 13, No. 1, January 1980, pp. 68-79
provides the following rationale:

Because of the care taken in the treatment of Underflows, the range of
normalized numbers in single, double, and quad formats has been
chosen to diminish slightly the risk of Overflow compared with the
risk of Underflow. This was done by picking the exponent bias and
alignment of the binary point in the significant digit field in such a
way that the product of the largest and smallest positive normalized
numbers is roughly 4 in each of the basic formats.

David Stevenson, "A Proposed Standard for Binary Floating-Point Arithmetic," Computer, Vol. 14, No. 3, March 1981, pp. 51-62
provides a somewhat different but related reasoning:

For the 32-bit format, precision was deemed the most important
criterion, hence the choice of radix 2 instead of octal or
hexadecimal. Other characteristics include not representing the
leading significand bit in normalized numbers, a minimally acceptable
exponent range which uses eight bits, and an exponent bias which
allows the reciprocal of all normalized numbers to be represented
without overflow.

David Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic", ACM Computing Surveys, Vol. 23, No. 1, March 1991, pp. 5-48
combines the above two explanations as follows:

Referring to Table 1, single precision has emax = 127 and
emin= -126. The reason for having |emin| < emax is so that the reciprocal of the smallest number (1/2emin) will not overflow. Although it is
true that the reciprocal of the largest number will underflow,
underflow is usually less serious than overflow.


why are WAW and WAR hazards not possible in mips architecture i have read about data hazards and then came across that mips architecture doesn't allow WAR AND WAW hazards can someone please help me understand it? the reason is not given in the book the MIPS pipeline is divided into :

1.IF(instruction fetch) 2.ID(decode the instruction) 3.EX(execute instruction) 4.MEM(write or read from the memory) 5.WB(write back to the register file)
for eg in case of  WAW hazards :

I1:  LOAD R1,0(R2)

I2:  ADD R1, R2, R3

I1:  |IF|ID|EX|MEM|WB |
I2      |IF|ID|EX |MEM|WB|

The above is expected way in which the instructions execute without data hazards
but here the second instruction has to wait till the WB phase of the instruction I1  for getting the value of R1  hence it will stall till the value of R1 is available in register file i.e till WB phase of the I1. here what my doubt is in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM  will this give rise to a hazard?

in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM will this give rise to a hazard?

I2 reads the register R1 at its ID phase. Therefore, if implemented directly, we must have time(I2.ID)>time(I1.WB).
A more sophisticated solution would bypass the register file and take the values directly from the Memory output. In this case we need
time(I2.ID)>time(I1.MEM) and the controller becomes more involved.

If I understand your question correctly, you ask whether I2 must take 5 clocks although it doesn't use the MEM phase. The answer is YES or otherwise, it may conflict with other instructions that would try to use MEM at the same time (unless the pipeline controller stalls them when congestion appears).


Is there a class of formal grammars that generate Recursive Languages only? Is there a class of formal grammars that generate Recursive Languages only?
(ie with which it is not possible to generate non recursive languages.)

If so what kind of production rules/restrictions do they have?

And why are they not a part of Chomsky Hierarchy?

I cannot answer the question as asked, but here is what partial result I found,
which may interest you.

I will first address the following problem.

Is there a formal family of automata recognizing all and only recursive languages?

The answer to that question is no. This can be proved by diagonalization.

Suppose such a family F of automata, They can be enumerated as
integers like TM, and there is a F-universal Turing Machine U that can
simulate them given their integer representation. So given such an
automaton M and an input X, U(M,X) can tell wether X in in the
recursive language recognized by M, and always halt. Now, we modify U
into a machine U' that lies when X=M. Then consider the language
string X recognized by executing U'(X,X). By construction, the TM U'
will always halt with an answer (yes or no), thus recognizing a
recursive set. But it gives for any X an answer different from the one
given by automaton X. So the language recognized is different from any
of the languages recognized by the automata in the family F. So the
family F cannot recognize all recursive languages. This establishes
the result by contradiction.

However, this is not the question asked. The question is :

Is there a formal family of grammars generating all and only recursive languages?

This question is about a generative device rather than a
recognizer. Simulating a generative device will always halt and give
me an answer if a string is in the language. But it will tell me
nothing when a string is not in the language. Simulating generation
will just give a non-halting computation if used for recognition.

To do better, I would have to pair each grammar with the grammar for
the complement language, in which case I would have a recognizer, by
simulating both in parallel, being sure that one will find the input
string. But we have seen that such a recognizer cannot exist. So
pairing such grammars for complementarity is not possible.

Given such a grammar, we would know there is another one that is its
complement, but it would be undecidable whether any given one is the one generating the
complement language.

But I do not know at this point whether such a grammatical formalism can exist.


Not understanding this way of proving undecidability of the termination problem I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following:
– Assume termination(P) always terminates and returns true iff P always terminates on all input data;
– The following program yields a contradiction
while termination(P) skip;

But I do not see what kind of contradiction there. Any idea?

This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints.
Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid program, that takes as input another program $P$, and works as above.
Now ask yourself - what would $Q$ do if you gave it its own encoding $Q$? Would it terminate or not?

If $Q$ terminates when given $Q$, then the "while" condition would stay true, meaning $Q$ would not terminate when given $Q$, but this is a contradiction.
If $Q$ does not terminate when given $Q$, then the while condition is false, so $Q$ does terminate when given $Q$, which is again a contradiction.

Therefore, a procedure such as "terminate" cannot exist.
Again, I cannot stress this enough -- read this proof elsewhere, watch youtubes of it, read textbooks. It's one of the most fundamental and exciting results in computer science!


Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time.

I've managed this in $O(nk)$ time, but can't figure out how to do it in the required performance.

The Misra-Gries summary is a simple technique which will find, for a given $k$, all elements in a sequence of $n$ elements which occur more than $\lfloor n/k \rfloor$ times, introduced in the 1982 paper Finding Repeated Elements as a generalization of the more well-known Boyer-Moore majority vote algorithm, which is essentially the case where $k = 2$.

The Misra-Gries summary can be computed in $O(n\log k)$ time and $O(k)$ space with a single scan of the sequence. However, it always returns $k-1$ distinct values without any guarantee that any of them satisfy the criterion; it only guarantees that if a value satisfies the criterion, it will appear in the list. Reducing the summary to the required values requires a second scan of the sequence to count the occurrences of each candidate value. This scan can be performed in $O(n \log k)$ time by the simple expedient of putting the $k$ values into an associative array implemented with a balanced binary search tree, such as a red-black tree.

In fact, constructing the BST for the second scan is not really necessary because the $O(n \log k)$ Misra-Gries computation actually produces such a tree. The computation can be performed as follows:

Initialise an empty associative array $\mathit{C}$ which maps sequence elements onto non-negative integers. The array will have a fixed capacity of $k$ elements, but may contain empty slots.
For each element $a$ from the sequence in turn:

Precondition: $C$ contains at most $k-1$ pairs.
If $a\text{ is in }C$, increment its associated value.
Otherwise, add $\langle a, 1\rangle$ to $C$.
If $C$ now has $k$ pairs, decrement all of the associated values and remove all keys whose associated value is $0$. [Note 1]
Postcondition: $C$ contains at most $k-1$ pairs.

At the end of the scan, $C$ contains at most $k-1$ pairs with distinct keys, which include all elements which appear in the sequence more than $\lfloor n/k \rfloor$ times.

The proof of the postcondition is simple: If step 2 was performed, the size of $C$ was not changed, so it is still at most $k-1$ because of the precondition. Otherwise, step 3 is performed, after which $C$ contains at most $k$ because step 3 adds exactly one pair to $C$. If step 4 is performed, there must be at least one pair whose associated value is $0$ and will be deleted from $C$, because step 4 can only be performed if step 3 was performed and step 3 adds a pair with associated value $1$ to $C$.

The intuitive explanation of why any element repeated more than $\lfloor n/k \rfloor$ times must be in $C$ at the end of the scan is explained by @YuvalFilmus in this related question.

The fact that the scan takes $O(n \log k)$ time can be seen from a simple amortised time analysis of the iteration. Every element from the sequence will be added to $C$ exactly once, either in step 2 or step 3, each of which take $O(\log k)$ since $C$ has at most $k$ pairs. Furthermore, each element (except for the $k-1$ final candidates) will be decremented exactly once in some occurrence of step 4. (Step 4 decrements $k$ values, but each decrement pertains to a different element of the original sequence, so the total number of decrements is $O(n)$. Another way to look at this is to observe that step 4 can be performed no more than $\lfloor n / k\rfloor$ times.)

Each decrement in step 4 consumes $O(1)$ time, but at least one pair must be deleted from $C$, which requires $O(\log k)$ time. Again, we rely on amortised analysis to see that the total number of deletions is $O(n)$.

In practice, this algorthm will usually be implemented with a hash table rather than a balanced binary tree. The hash table implementation replaces the guaranteed $O(\log k)$ steps with expected $O(1)$ (but worst case $O(k)$). Since the worst case is extremely unlikely, the hash table algorithm is generally cited as linear-time, although strictly speaking it is linear expected time.

Notes

As an optimisation, it's possible (and, I believe, common) to avoid adding and removing $a$ in a single iteration. It is also unnecessary to remove pairs which have been decremented to 0 provided you can find such a pair in $O(1)$ for step 2. This can be done with a bit of bookkeeping. You can also implement "decrease all counts by one" by using a base value (so that the values are the stored value minus the base value) and incrementing it by one to effectively decrement all counts. All that will change the iteration step from amortized $O(1)$ to guaranteed $O(1)$ but the extra bookkeeping is likely to result in a slower total execution time.


Log reduce PATH to DISTANCE-PATH An instance of PATH is given by  where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t.

DISTANCE-PATH is similar, but with an extra requirement d and on an undirected graph. A true instance of this would be  where G is an undirected graph and there exists a path of length d from s to t, and there isn't a shorter path.

Given directed , construct an undirected G' such that G' has a path from s to t of shortest length d iff G has a path from s to t.

The idea is to construct G' by making n copies of G, and each edge in G' connects one copy to the next.

I don't understand how d comes into play and how to ensure there are no shorter paths, should d be the number of copies of G made? Should G' connect the copies of G by connecting one t node to the next s node? I'm not sure how to approach this problem

The idea is to build a layer graph $G'=\left (V_1,...,V_n\right)$ with $n$ layers, where each layer is a copy of $V$. For each $(u,v)\in E$ we add the edges $\left\{(u_i,v_{i+1}) | 1\le i \le n-1\right\}$, where $u_i$ is the copy of $u$ in $V_i$. In addition we add self edges $\left\{(u_i,u_{i+1}) | u\in V, 1\le i\le n-1\right\}$. You then want to know whether there exists a path $s_1\rightsquigarrow t_n$. Since $G'$ is a layer graph, any path from $s_1$ to $t_n$ is of length $n-1$ (so you dont need to worry about shorter paths anymore). You should now be able to complete the details yourself.


Linear time algorithm for finding $k$ shortest paths from $s$ to $t$ Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$,
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths
  between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem.

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem?

First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I describe the best worst-case bound (to the best of my knowledge) but also an algorithm that might run in linear time in some specific cases.

But before describing the latest developments in the state of the art, I wanted to emphasize the importance of simple paths in this specific problem. As a matter of fact, many people overlooks the importance of this requirement and some do not even understand it at first glance.

When computing the shortest path from a start vertex to a goal vertex, the optimal path is necessarily simple, i.e., it does not repeat any vertices. However, when computing $k$ optimal paths, the second, third, ... best paths might not be simple. To prove it, I provide here an example that has been slightly adapted from Hershberger, Maxel & Suri, 2007:

The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $\pi_1 : \langle s, A, B, C, D, t\rangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$ and $\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $\pi_2 : \langle s, F, t\rangle$ and $\pi_3 : \langle s, G, t\rangle $ with costs 10 and 11, respectively.

Given a graph $G(V, E)$ where $V$ is the set of vertices and $\langle u, v\rangle\in E, u, v\in V$ if there is an edge between vertices $u$ and $v$,  the current state of the art for this problem to the best of my knowledge is described below:

The first significant improvement to solve the $k$ optimal paths problem is Eppstein's algorithm (Eppstein, 1998) which runs in $O(|E|+|V|\log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths.

In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|\log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen's algorithm to $O(k(|E|+|V|\log |V|))$ time. While Yen's asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice.

One of such works is due to John Hershberger et al., who introduced a replacement paths algorithm which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized.

Hope this helps,

Bibliography

Aljazzar, H. & Leue, S. (2011). $K^*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154.

Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427.

Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405.

Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716.

Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20.


Define the time complexity of Kruskal's algorithm as function I am trying to define the time complexity of Kruskal's algorithm as function dependant on:

the number of vertices V
the number of edges E
the time complexity of verifying, whether two edges don't form a cycle Ec(V)
the time complexity of connecting two sets of vertices Vc(V)

The edges are unsorted and I know the time complexity of sorting edges, which is Big O(E * log E).

I don't really know, how to solve this problem and I would be grateful for any help. Thanks!

After sorting the edges, which takes $O(E \log E)$ time, Kruskal's algorithm adds the next cheapest edge which doesn't cause a cycle.  The question is what data structure can be used to check if a given edge causes a cycle.

At any given point during the execution of the algorithm, the set of edges chosen by the algorithm forms a forest.  Initially, the forest contains $n$ trees, where $n:=|V|$.  If the next cheapest edge is $ab$, and vertices $a$ and $b$ belong to different trees in the forest, then the two trees can be combined into a larger tree.

A data structure for storing the above tree information is to store a parent value for each vertex.  Following the parent pointer leads to the root node of the tree. If vertices $a$ and $b$ have different roots, then they belong to different trees.  One can merge the two trees by making $b$ the parent of $a$.  This allows us to maintain a collection of disjoint sets (each set is the vertex set of a tree), whose union is the vertex set of the graph.

So that the merging of two trees into one tree is done efficiently, the smaller tree can be put under the larger tree (i.e. the one with the smaller rank has its root node point to the other root).  This ensures that the trees have small heights, and the path that is followed from a node to find its root has small length.  Also, in order to not have to follow the same long sequence of parent pointers in subsequent iterations, one can store the root node's value after it is found.  These are the "union-by-rank" and "path compression" heuristics, which efficiently implement Kruskal's algorithm, so that it runs in $O(E \log E) = O(E \log V)$ time.


Correctness of asymptotic expression from exact expression I have the expression:
\begin{equation}
  |Q|f(n)|\Gamma|^{f(n)}
\end{equation}

Here is my solution to convert the above into an asymptotic expression:
$|Q| = 2^l$ for some $l\in\mathbb{R}$
$|\Gamma| = 2^k$ for some $k\in\mathbb{R}$

Therefore we have $2^lf(n)(2^k)^{f(n)} = f(n)2^{kf(n)+l} = f(n)2^{O(f(n))}$

Is this correct? I just want to verify my understanding of a discussion in Sipser's Theory of Computation text.

What you wrote is correct under the assumption that $|\Gamma|$ and $|Q|$ are constant (which, from the context, is indeed the case), but can be taken a bit further, and can be made more explicit:

For every $x>0$ it holds that $x=2^{\log x}$. Therefore you get

$$f(n)|Q||\Gamma|^{f(n)}=2^{\log f(n)}2^{\log |Q|}2^{f(n)\log |\Gamma|}=
2^{\log f(n)+\log |Q|+f(n)\log |\Gamma|}=2^{O(f(n))}$$

which is somewhat cleaner.


What is "time-slice multi-threading"? My goal is to understand the exact differences between SoEMT, SMT and "time-slice multi threading".

Thus far I already found information on SoEMT and SMT and it does not seem to hard to find more on google. However my problem is: Time-slice multithreading. The best I found - apart from a long winded book, was:

– Processor switches between software threads
after a predefined time slice
– Can minimize the effects of long lasting events
– Still, some execution slots are wasted
For Time-slice multithreading I found:

However, this doesn't really go into detail how this things are achieved, for what purpose, its pros, cons and implementations etc.

I would thus be quite happy, if someone knew a good resource, that read up further on that topic. Bonus, if it also compares SoEMT, SMT. As always thanks in advance.

Time-slice multithreading is the convectional multithreading where CPU creates an illusion of executing more than once program at a time but the CPU can execute only one of these programs at a time. The OS maintains the illusion of concurrency by rapidly switching between running programs at a fixed interval, called a time slice. Time slice multithreading works similar to RoundRobin fashion.

For detailed understanding refer

Definition (Convectional multithreading)
Stackoverflow answer


CNF and small-depth circuits I'm reading on small-depth circuits. Since every formula can be turned into a CNF formula, which has depth at most 3, why should we study deeper circuits? Is it because convertion to CNF may result in an explosive blow-up? If so, can you give an example?

Much of the interest in circuits stems from the following implication:
$$
\mathsf{NP} \not\subseteq \mathsf{P/poly} \Longrightarrow \mathsf{P} \neq \mathsf{NP}.
$$
In words, if we show that some problem in NP doesn't have polynomial size circuits then we have proved that P≠NP.

Unfortunately, we don't really know how to prove lower bounds on general circuits. We do know how to prove lower bounds for constant depth circuits and for monotone circuits, which is the main reason we are interested in these models at all.

We already know of functions in $\mathsf{NP}$ which don't have polynomial size constant depth circuits. Unfortunately, these functions are in $\mathsf{P}$, and so won't help in proving $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. What we want is to improve our techniques so that they apply for circuits with polynomial depth — that would show that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$.

Now, to your question. While it is true that every function can be represented as a CNF and so as a constant depth circuit, sometimes allowing larger depths makes a big difference. For example, Parity has an exponential size CNF (and even exponential size constant depth circuits), but has a polynomial size circuit of logarithmic depth (and even a polynomial size formula). In other words, Parity exhibits an exponential blowup when converting from circuit to CNF. This shows that lower bounds on CNFs (probably) won't be able to separate P and NP according to the program laid out above.


Converting Base 16 to Base 8? I understand the basic but what I dont understand is this:

so base 16 to base 10

357/16 = 22.3125 but on this example im looking at says remainder 5?

The trick in converting from hexadecimal (base 16) to octal (base 8) is using a (perhaps imaginary) binary (base 2) intermediate. To demonstrate this, let's convert from base 10000 to base 1000, where the intermediate would be decimal (base 10). Consider this number, whose digits are separated by a space:

  3 1415 9265 3589 7932 3846

The corresponding number in base 1000 is

  314 159 265 358 979 323 846

This example is not completely academic. In some situations one converts between base 1000, used in many European languages, and base 10000, used in Chinese.


Complexity of Hamiltonian path and clique problem I came across this question. If we want to check if a graph contains both Hamiltonian path and clique. Would this problem be NPC.

I knew that clique contains a Hamiltonian path and both problems are NPC, but I am uncertain if something would be different if we check it in same time.

In the clique problem we are required to determine if there exists a clique of a certain size (given as input), so the observation that every clique contains a Hamiltonian path won't help much (a graph $G$ with $n$ vertices may contain cliques of size $<n$, but not have a Hamiltonian path).

$Clique=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k\right\}$

$HPath=\left\{G | \hspace{1mm} G \text{ contains a Hamiltonian path}\right\}$

Since the instances to the problems are not of the same type, it isn't really interesting to talk about their intersection (which is empty), so what you probably have in mind is the set:

$L=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k \land G \text{ contains a Hamiltonian path}\right\}$.

$L$ can be shown to be NP-complete using a simple reduction from $HPath$ (think about how to change the instance to the HPath problem, to an instance of $L$, without ruining the properties of the graph).


Do data points mean Eigenfaces in higher dimensional space? I saw the following animation at making sense of PCA
, which shows blue data points.

I am reading a paper on Eigenfaces which says that:

  "a typical image of size 256 by 256 becomes a vector of dimension
  65536 or equivalently a point in 65536 dimensional space"

The paper is available at the following link:
Eigenfaces for Recognition

My question is that in the context of Eigenfaces is each blue point an image?

Somebody please  guide me.

Zulfi.

Each blue data point in the animated picture stands for an image of a face whose dimension is much higher in the context of Eigenfaces for Recognition. They are the original data points. It does NOT mean Eigenfaces.

When the long swinging black solid rod becomes still under the "viscous friction" exerted by the red lines, its direction is the most significant eigenface in that context, which is defined as an eigenvector of the biggest eigenvalue of the covariance matrix of the face images. The projection of the blue points onto that long black rod viewed as vectors starting from the center of the blue points is the first principal component.


Lower bound on number of comparisons needed to search for a number in a sorted 3-d array Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. However are $\Omega(N^2)$ comparisons needed in the worst-case? For an $N \times N$ 2-d sorted array I recall a proof that $\Omega(N)$ comparisons are needed; I'm having trouble seeing how to extend to the 3-d case though

Let's suppose that the array is indexed using $\{1,\ldots,N\}$, and assume for simplicity that $N$ is odd. Divide the cells in the array into three parts:
$$
\begin{align*}
X &= \{ (i,j,k) : i+j+k < 3 \tfrac{N+1}{2}, \} \\
Y &= \{ (i,j,k) : i+j+k = 3 \tfrac{N+1}{2}, \}, \\
Z &= \{ (i,j,k) : i+j+k > 3 \tfrac{N+1}{2}, \}.
\end{align*}
$$
Consider a 3D array $A$ with $A(i,j,k) = -\infty$ for all $(i,j,k) \in X$ and $A(i,j,k) = \infty$ for all $(i,j,k) \in Z$ (you can think of $-\infty,\infty$ as stand-ins for large negative and positive numbers). We claim that any such array is sorted. Indeed, suppose for example that $i_1 < i_2$ and $j,k$ are given. If $i_1 + j + k < 3\frac{N+1}{2}$ then $A(i_1,j,k) = -\infty \leq A(i_2,j,k)$. If $i_1 + j + k \geq 3\frac{N+1}{2}$ then $A(i_1,j,k) \leq \infty = A(i_2,j,k)$.

It follows that you cannot rule out that a finite number is in $A$ without checking all entries in $Y$ (formally this can be proved using an adversary argument). The number of entries in $Y$ is at least $N^3 / (3N-2) = \Omega(N^2)$.

The same idea extends to give a lower bound of $N^{d-1}/d$ in the $d$-dimensional case.


Bit Blasting Algorithm I found a pseudo algorithm which describes bit blasting: click (page 156,157). I am trying to implement it in C, but I don't understand it yet completely. Let's make an example:
Assume our bit-vectors have only a length of 2 bits (for simplicity) and they are unsigned and out bit-vector formula looks as follows: $\phi = x \,\,\,\wedge\,\,\, y\mid 2 = z \,\,\,\wedge\,\,\, 1 < 3$.
Let's describe Boolean variables with $b_0, b_1,...$ ($x,y$ and $z$ are bit vectors).
The set of atoms would be $At(\phi) = \{ x,\,\,\, y\mid2=z,\,\,\, 1<3 \}$ and therefore the initially $\beta = e(\phi) = b_0 \,\,\,\wedge\,\,\, b_1 \,\,\,\wedge\,\,\, b_2$.
The set of terms would be $T(\phi) = \{ x,\,\,\, y, \,\,\, 2,\,\,\, z,\,\,\ 1,\,\,\,3 \}$.
Algorithm
Line 2: $\beta$ is already set.
Line 3-5: We set the $t \in T(\phi)$ to Boolean variables, hence $x \rightarrow b_3, b_4\,$ - (because we said our bit-vectors only have a length of 2 bits), the same with $y$ and $z$, but what happens with constants? I would guess: $2 \rightarrow 1,0$ or more precise $2 \rightarrow b_7=1, \, b_8=0$.
So after line 5, our $T(\phi) = \{ b_3, b_4,..., b_{14}\}$.
Then I stuck, how does it go on? And how would the equisatisfiable Boolean formula $\beta$ look like after the algorithm? Other references to other algorithms would be also nice.

I assume the formula is

$$(x \ne 0) \land (y|2 = z) \land (1<3).$$

We can handle each clause of the conjunction separately.  If $x=(b_3,b_4)$, then $x \ne 0$ translates to

$$b_3 \lor b_4.$$

If $y=(b_5,b_6)$ and $z=(b_7,b_8)$, then $y|2$ translates to $(b_5|1,b_6)$, which simplifies to $(1,b_6)$ (if you are doing simplification).  Now $(1,b_6) = (b_7,b_8)$ translates to

$$(b_7=1) \land (b_6 = b_8),$$

which in CNF form is

$$b_7 \land (b_6 \lor \neg b_8) \land (\neg b_6 \lor b_8).$$

Finally, $1<3$ translates to True, if you are doing simplification.  So, the final result is the conjunction of those:

$$(b_3 \lor b_4) \land (b_7) \land (b_6 \lor \neg b_8) \land (\neg b_6 \lor b_8).$$


Proving the correctness of a square summing algorithm int sumHelper(int n, int a) {
   if (n==0) return a;
   else return sumHelper(n-1, a + n*n);
}

int sumSqr(int n) {
    return sumHelper(n, 0);
}

I am supposed to prove this piece of code which uses tail recursion to sum up the squares of numbers. That is, I need to prove that for $n ≥ 1$, $sumsqr(n)=1^2+2^2+\dots+n^2$. I have figured out the base case but I am stuck at the induction step. Any hints or help will be appreciated.

Assuming $n ≥ 0$,
let $$ P(n) \;≡\; ∀ a.\, sumHelper(n, a) = a + ∑_{i = 0}^n i² $$

Then we prove this is always true by induction on $n$.

The base case, n = 0:

  sumHelper(n, a)
={ Case n = 0 }
  sumHelper(0, a
={ Definition }
  a
={ Arithmetic }
  a + 0²
={ Arithmetic }
  a + ∑_{i = 0}^0 i²
={ Case n = 0 }
  a + ∑_{i = 0}^n i²

The induction step, assuming P(n) let us show P(n+1),

 sumHelper(n+1, a)
={ Definition }
  if   (n+1==0) a
  else sumHelper(n+1-1, a + (n+1)*(n+1))
={ Since we assumed n ≥ 0, we have n+1 ≠ 0.
   Hence we have the else-branch. }
  sumHelper(n+1-1, a + (n+1)*(n+1))
={ Arithmetic }
  sumHelper(n, a + (n+1)*(n+1))
={ Apply the inductive hypotheis with a ≔ a + (n+1)*(n+1) }
  (a + (n+1)*(n+1))) + ∑_{i = 0}^n i²
={ Arithmetic: Bringing the `n+1` term back into the sum }
  a + ∑_{i = 0}^{n+1} i²

We're done :-)


Is the isometric path cover problem NP-complete? Isometric path (like geodesic) is yet another name for shortest path. An isometric path cover is a set $S$ of isometric paths such that every vertex $v ∈ V$ belongs to at least one isometric path of $S$. The isometric path cover problem is to find a minimum cardinality isometric path cover of $G$. Is the isometric path cover problem  NP-complete for general graphs?

This question is mentioned in a recent (2017) paper, Strong geodetic problem in networks:
computational complexity and solution for
Apollonian networks by Paul Manuel, Sandi Klavžar, Antony Xavier,
Andrew Arokiaraj, and Elizabeth Thomas. On page 8, they state:

  To our knowledge, the complexity status of the isometric path problem is
  not known.


About computable sets Let TOT be the set of all Turing Machines that halt
on all inputs.
Find a computable set B of ordered triples such that:

TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]

This definition means that TOT is a set of all Turing machines e such that they halt on all inputs. The "for all" x denotes all inputs to that machine, and "there exists" a y denotes that e halts under y steps.
x consists of 0s and 1s, y and e are Natural numbers too ( e denotes Turing machine $T_e$ if we were to number all our turing machines)

EDIT: SOLVED

Let $T$ be the set of all Turing machines.

Let $B = \{ (e,x, y) \in T \times \{0,1\}^* \times \mathbb{N} : e(x) \text{ halts in $y$ steps}\}$, and define $C = \{e \in T : \forall x \in \{0,1\}^*, \; \exists y \in \mathbb{N}, \; (e, x, y) \in B]$.

We start by proving $\text{TOT}=C$.

If $e \in \text{TOT}$ then, $\forall x \in \{0,1\}^*$, $e(x)$ halts. Let $y_x$ be the number of steps needed for $e(x)$ to halt. Then $ \forall x \in \{0,1\}^*$ there is a choice of $y \in \mathbb{N}$, namely $y = y_x$, such that $(e,x,y) \in B$, showing that $e \in C$ and hence $\text{TOT} \subseteq C$.

If $e \not\in \text{TOT}$, then $\exists x \in \{0,1\}^*$ such that $e(x)$ does not halt. Then $\exists x$, such that $\forall y \in \mathbb{N}$, $(e, x, y) \not\in B$, showing that if is false that $\forall x \in \{0,1\}^*, \exists y \in \mathbb{N}$ such that $(e, x, y) \in B$. As a consequence $e \not\in C$ implying $\text{TOT} \supseteq C$.

It remains to show that $B$ is computable.
To decide whether any given triple $(e, x,y) \in T \times \{0,1\}^* \times \mathbb{N}$ belongs to $B$  it suffices to consider a Turing machine $T'$ that simulates $e(x)$ for $y$ steps. If $e(x)$ halts, then $T'$ accepts. Otherwise, if $e(x)$ does not halt by the end of the $y$-th step, $T'$ rejects.


What is the purpose of manipulating trained layers? In my course there are a number of exercises which amount to taking a trained residual network and deleting, swapping or repeating layers (without retraining).
Is there any real application for doing this? An exercise might say to swap two specific layers and I will find that the performance will increase (on a very small test set) but if I try to swap any other two layers the performance decreases.
To me it seems that operations in the exercises are chosen to increase the performance on the specific test set that we have but I don't see how it would improve generalisation. In answering the exercises I can say that the performance increased but I can't say why (because to me it seems to be an arbitrary manipulation of the network).

No.  I've never heard of this being used for a published task.  Neural nets are trained with optimization (SGD) rather than by swapping/deleting/repeating layers.


$L$ is decidable. Prove that "similar" language is also decidable Assume that $L$ is decidable. Is the following language decidable? $$ L' = \{w | \text{ there is } u \in L \text{ such that u and w are equal to at most two positions.}\}$$

For example, let $u=abcd$. The following words are equal to $u$ at most two positions: $\{aba, agg, ab, zzz, dsa, ...\}$, but not $\{ abc, zbcd \}$

My approach:

  A language is decidable iff some enumerator enumerates the language in
  lexicographic order.

I use above theorem.

So, $L$ is decidable. Therefore, let's take enumerator $E$ for it. Let We construct a $TM'$ for $L'$. Let enumerator $E$ be connected to $TM'$. For every input $w$ given to $TM'$ the $TM'$ compare it position by position with every string $v$ generated by $E$ in lexicographical order till $|v|\le|w|$
If number of the same positions $>2$ reject $w$. Otherwise, accept.

Ok?

Let's consider for simplicity the language
$$
L'' = \{ w : \text{there exists $u \in L$ such that $u,w$ disagree on all positions} \}
$$
instead of your more complicated one.

Consider the language
$$
L = \{ 0^n10^m : \text{the $n$th Turing machine halts on the empty input after exactly $m$ steps} \},
$$
which is computable. You can check that $1^n0 \in L''$ iff the $n$th Turing machine halts, hence $L''$ is not computable.

In order to answer your original question, just repeat each bit 3 times.


How can I write a genetic programming algorithm, given that the Halting problem is unsolvable? I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as abstract syntax trees.

However, one of the functors is the while loop. Of course, in assesting a tree's fitness, I have to evaluate the program: but the halting problem is unsolvable. How can I tell if a given tree stops? Of course I can't, so what are some practicals ways to approach this problem?

Should I make my simple tree-language not turing complete? Or maybe give a timeout to each tree?

It is very unlikely indeed that finiteness is truly what you are looking for. Would you really be happy with a program that takes $10^{10^{40}}$ steps to complete?

If I am right, "non-haltingness" is not the real quality you are looking for. It is "halting within a reasonable time".

The best way to express this is not as a pure timeout, but by defining a measure of utility which declines with an increasing number of steps. That will give your evolutionary mechanism a steady "push" in the right direction. As for whether it is $1/n$, $1/\sqrt n$, $2^{-n/c}$, that is something you can decide.

Of course in practice a program that takes more than a certain number of steps is going to carry on going for ever. But you can encapsulate this intuition into the algorithm by saying that if, after $n$ steps, the overall utility has declined to a point when it is too low to be worth considering and it is never going to increase if you carry on stepping. Thus the timeout is still there, but as an implementation detail and not as a primary principle-in-itself.


Given a sorted array with n integers, how to find the element that has no duplicates? I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-conquer algorithm. I have noticed that n needs to be odd to satisfy my condition. I thought about doing this: divide my array in two parts from the mid, if from [0, mid] or [mid, end] I have odd number of elements then my elements is in that half. So, recursively divide also that subarray and so on.

How to decide which part of the array to look at first?
Does this solution take O(logn)?
Is there other effective approach?

This is a classical problem when the array isn't sorted, which has a surprising, almost magical linear solution.
But here, with a sorted array, your idea is great.
The unique element will have an index $u$, and every element $a[i]$ will be exactly the same as either $a[i-1]$ or $a[i+1]$ (which are different).
Assuming that arrays start at $0$, the shape of the (sorted) array is first a list of elements where $a[2i] = a[2i+1]$, then $a[u]$, then a list of elements where $a[2i-1] = a[2i]$.
So to decide where $u$ is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes).
This takes a constant number of operation by question, and each question reduces the size of the search array by $2$ (if you sample in the middle, of course).
So, to synthesize :

By looking in the middle, you ensure that the next part you have to look at will be as small as possible
This yields a $\log(n)$ algorithm
This approach is probably optimal, but the proof that there isn't something better to do must be quite hard, so I leave it to someone else ^^


Understanding definition of NP and co-NP From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we have the following, where $n$ is the length of the input:

$$
\text{NP}=\bigcup \text{NTIME}(n^k)
$$

This means that one way a  problem can be shown to be $\in \text{NP}$ is if we can construct a non-deterministic TM $N$ using a polynomial time verifier $V$ on a certificate $C$, or:

TM $N$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$, accept

But if I use the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$, wouldn't this imply that $\text{co-NP} \subseteq \text{NP}$, since I can construct a TM $N'$ that can recognize co-NP:

TM $N'$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$ for any branch, reject
3. if all branches reject the guessed certificates, accept

In this case, since all branches of $N'$operate in polynomial time, $N'$ should also be able to solve problems for co-NP in non-deterministic polynomial time.

But since it is not yet sure if NP=co-NP, how should I understand the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$?

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine.

Rather, it's a "co-nondeterministic Turing machine" (if that were a term). Unsurprisingly, co-NP is exactly the set of languages accepted by some co-nondeterministic Turing machine, and the fact that NP=co-NP is open means exactly that it is not currently known whether nondeterministic and co-nondeterministic machines can compute the same things in polynomial time.


Is order of bits in byte really not of concern? What I can't wrap my head around is sentence repeated everywhere I look, that order of bits in byte is not important(not of my, as a programmer, concern).
My question then is if there is possibility that it makes difference?

For example, I crate a binary file with just 0x1 in it (represented on my machine as 00000001). What keeps other machine to read the same byte as 128(10000000) ?
Is there standard for msb placement in file, memory that guarantees compability or am I missing something trivial/obvious along?

EDIT:
Thanks to dirk5959's answer I found out that my machine is little-endian for bytes and the same is for bits in byte. Additional question is, if it is a rule or there is some architecture that behaves different?

Bytes are transferred from memory to disk using an I/O protocol (e.g. SCSI) that specifies the bit order of transmission in the case of a serial protocol, or for parallel protocols specifies which pin upon which each bit in a byte should be transmitted. For bytes moved from memory over the network, the network link level protocol (e.g. Ethernet) specifies the bit order.  In either instance, an application programmer need not concern herself with the details; the operating system in concert with disk or network controllers will maintain the correct bit order end-to-end so that the correct values are transmitted/received or store/retrieved.

N.B.: byte order is another matter altogether.


What is the difference between superposition and paramodulation? I am currently writing a paper about automated theorem proving in first-order logic. Equality is not uncommon for mathematical problems and almost every theorem prover like VAMPIRE or SPASS has a calculus for equality. But the most paper are always writing about the term "superposition" calculus. A simple google search did not help to find any information about this term, only the wikipedia website which means "it can be used for first-order logic with equality".

Another paper referneced to the Paramodulation-based theorem proving which describes the concept of paramodulation for theorem proving. It seems that the superposition is some modified version of paramodulation, but I don't understand why and in which way.

So, is there any explanation of this calculus or can someone give me some hints what is different from paramodulation?

This is late for you, but probably might be of help to others. I myself had asked this question and I wrote the summary of my findings to the acl2-help mailing list on 8 and 9 September 2013: https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00005.html
https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00006.html

Disclaimer: What follows is my understanding of the subject and I am not an expert.

I assume you are familiar with what is called
term-rewriting. Informally its a very simple notion where one uses a
rule to reduce or rewrite another expression.

A rewrite rule is usually a universally quantified formula of the form
$C \Rightarrow l=r$, where $C$ is a formula and $l$ and $r$ are terms. One says that a
rule $R$ applies to another formula $\Phi$, if there is some subterm $s$ of
$\Phi$ and some substitution $\sigma$ such that $l\sigma = s$ (this process
is called matching) and $C\sigma$ is true. If $R$ applies to $\Phi$, then
one can rewrite $\Phi$ to $\Phi\sigma$. Demodulation is another name for
unconditional term-rewriting, i.e., $C$ is simply true and so $R$ is just
$l=r$.

Rewriting involves matching,i.e., one-way unification.
Paramodulation involves full unification.  Moreover, the equality
($l=r$) that is used to perform paramodulation, is not directed, either
lhs or rhs can be unified with a subterm in the other literal
paramodulated upon.

Superposition is a restriction of Paramodulation. In particular, the
rules of inference named 'Superposition (left/right)' are restrictions
of "ordered" paramodulation, i.e., the paramodulation rule is applied
only when equation $l=r$ (to be instantiated/unified) satisfies certain
properties: $l >> r$ for a given reduction order $>>$, $l=r$ is maximal (wrt
$>>$) in the clause etc etc.

Here are some fundamental papers that are interesting from a historical point of view.

[1] The concept of demodulation in theorem proving - L Wos, GA
Robinson, DF Carson, L Shalla - Journal of the ACM (JACM), 1967

[2] Handbook of Logic and Automated Reasoning - J Harrison.

[3] Paramodulation and theorem-proving in first-order theories with
equality- G Robinson, L Wos - Machine intelligence, 1969

[4] Rewrite-based equational theorem proving with selection and
simplification - L Bachmair, H Ganzinger - Journal of Logic and
Computation, 1994

[5] Simple word problems in universal algebras - DE Knuth, PB Bendix -
Computational problems in abstract algebra 1970

[6] A superposition oriented theorem prover - L Fribourg - Theoretical
Computer Science, 1985 - Elsevier

[7] Completion without failure - L Bachmair, N Dershowitz, DA Plaisted -1989


Is a push-down automaton with two stacks equivalent to a turing machine? In this answer it is mentioned

  A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine).

I wanted to know regarding the truth of the bold part above. Is it in fact true or not? What is a good way to reach at an answer to this?

Two bits to this answer;

Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata).

The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume that we're using the model of TMs that has a tape that's infinite in one direction only (though both directions is not much harder, and equivalent).

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. You start off like so:

Push the normal "bottom of stack" markers on both stacks.
Push the input to the left stack (use non-determinism to "guess" the end of the input).
Move everything to the right stack (to keep things in the proper order).

Now you can ignore the input and do everything on the contents of the stacks (which is simulating the tape). You pop to read and push to write (so you can change the "tape" by pushing something different to what you read). Then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

For a full formal proof, see an answer to another question.

The relationship the other way should be even more obvious, i.e. that we can simulate a two-stack PDA with a TM.


What exactly is Symbolic Model Checking? I know that Symbolic Model Checking is state space traversal based on representations of states sets and transition relations as formulas like in CTL using models like Kripke Model. I know the theory. But I'm finding it hard to understand the actual application. Where exactly is it used? What exactly does it do and how does it work?

Can someone explain with a real example and relate theory to practice?

Symbolic model checking can be very useful for verifying the correctness of communications and security protocols. For example:

A symbolic model of an OAUTH2 implementation could help check for unintended consequences where an adversary obtains secret authentication tokens or related circumstantial data that could help them contravene the process.
A symbolic model of a cryptographic protocol, such as a TLS handshake, could help verify that the cryptographic design doesn't have any unintended consequences.

This works by writing a symbolic description of all the primitive functions and protocol algorithms, and then having a symbolic model checker, such as ProVerif, traverse the state space and attempt to detect state combinations that produce unfavorable results. In the case of ProVerif, symbolic models are described using the applied Pi calculus as the modeling language. This allows the description of protocols in a functional, ML-like syntax.


Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n) I'm working on some lecture notes and wondered if there was a good example algorithm for the recurrence equation

$$T(n) = T(n/2) + n$$

I know that I can do selection in this running time, but that is a probabilistic algorithm, and I was hoping not to introduce this algorithm at this point in my lecture notes. I plan to introduce the selection problem in a later chapter after describing quick-sort. Is there a good example of an algorithm that has this recurrence equation as worst-case?

Bottom-up heap construction. Choose one application of sift-down as your unit of measurement. Then the recurrence is $T(n) = T(n/2) + n$.

If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to

$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum_{h=0}^{\lg n} h\frac{n}{2^h} < n\sum_{h=0}^\infty \frac{h}{2^h}$$

and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.


Would you ever use a skip list over a treap? Skip lists are taught as a standard of the undergrad CS curriculum at many major universities.  However, from my reading* I can't find any practical situation where you would use a skip list over  a treap. Also they have the same asymptotic performance  for all the main operations.

As a result this left me wondering:

  Should you ever choose a skip list over a treap?

*A few web links that suggest that treaps are faster in practice or a just very fast in practice.

http://pinporelmundo.blogspot.co.uk/2011/06/skip-lists-compared-with-treaps-and-red.html
https://stackoverflow.com/a/16009599/2179021
https://stackoverflow.com/a/18303163/2179021

and here is a link suggesting that skip lists are almost never useful

https://www.quora.com/Why-arent-skip-lists-used-more-often-instead-of-balanced-trees

here is an extensive 13 page analysis of considerations in this area including empirical analysis. coders sometimes ask for "one size fits all" answers. of course "best" implementation depends on the actual "forces" applied on the implementation. a single implementation may even behave ("dramatically") differently on different amounts of data and different conditions. for some data structures there is no significant difference and either can be acceptable.

raw performance is not the only factor. factors might involve how hard it is to implement/ test the structure vs whether it is already implemented etc. and this paper also considers caching considerations effect on performance. this research finds that skip lists have good variable-node-size performance (ie not all nodes have same size) and paged skip lists outperforms B+-trees in their case.

see p7 and fig6 p 10.

  The AVL tree is the best
  performing fixed-node-size data structure, and
  the paged skip list is the best performing
  variable-node-size data structure. Moreover, the
  gap between the cache-conscious data structures
  and their counterparts is growing, as shown by
  the 100 cycle memory latency configuration.
  The paged skip list outperforms the sequential search
  B+-tree by 12% on the Intel processor.

T-treap and Cache Performance of Indexing Data Structures /
Joshua P. MacDonald and Ben Y. Zhao


Check array in linear time with a constant space complexity Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.
E.g.
[1, 1, 1, 1] - all the elements are the same, so it is true
[12, 20, 1, 23] - all the elements are different, so it is also true
[12, 20, 1, 1] - we have just two 1, so it is false
The easy thing I was able to come up with is to use a hashmap to map an integer to a number of occurrences of that integer in the array. And then to iterate over the hashmap and check if there is at least one entry whose value is greater than 1 and is not equal to the length of the array, then I return false. Otherwise, I return true after the iteration.
The problem with my solution is that it has a linear space complexity and I feel that it should be possible to somehow solve the problem using a constant space complexity and linear time complexity.
So, could someone help me come up with an O(1) space complexity and O(n) linear complexity with respect to the array size solution, please?
I am working on this problem just for fun.

The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity. More technically, your problem can be reduced to element distinctness problem in linear time.
Therefore, the best possible solution here is $O(n \log n)$ time algorithm. For that, you can employ merge sort algorithm using a linked list. It also has an $O(1)$ space complexity.


What's the reason for the second condition of the pumping lemma(s)? For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq p$
$ \forall i\geq 0: xy^iz\in L$

Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

$|vy|\geq 1$
$|vxy|\leq p$
$ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: Why do we have condition 2 in the lemma (for either case)? I understand that condition 1 essentially says that the "pumpable" (meaning nullable or arbitrarily repeatable) substring has to have some nonzero length, and condition 3 says that the pumpable substring can be repeated arbitrarily many times without deriving an invalid string (with respect to $L$). I'm not sure what the second condition means or why it is important. Is there a simple but meaningful example to illustrate its importance?

Consider the language of words over $\{a,b\}$ consisting of words with an equal number of $a$s and $b$s. This language is context-free but not regular. To show that it is not regular using the pumping lemma, you start with the word $a^pb^p$ and pump $y$, which must consist solely of $a$s. Without condition (2), this wouldn't work: you can pump $ab$ (in the middle) and remain inside the language. Moreover, for any word that you start with, you will be able to find one of the substrings $ab,ba$ which you could then pump.

Similar considerations show that condition (2) is needed for proving that the language over $\{a,b,c\}$ consisting of those words having an equal number of $a$s, $b$s and $c$s is not context-free.


Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|>n-1$  edges.

I am not sure what bothers you but as I see it you are confused about the following two facts

If a graph is connected then $e \geq n-1.$
If a graph has more than $e > \frac{(n-1)(n-2)}{2}$ then it is connected.

Notice that the implications in 1 and 2 are in opposite directions.

For a proof of 2. you can check out this link.


Proof of Simple Properties About Terms, Position of Subterms and Replacement of Subterms I am studying term rewriting by reading Baader/Nipkow's book: "Term Rewriting and All That".
I want to prove a lemma about terms, position of subterms and replacement of subterms. The notation is as follows:

$s|_{p}$ denotes the subterm of $s$ at position $p$.
$s[t]_{p}$ denotes the term obtained from $s$ by replacing the subterm at position $p$ by $t$.

The lemma I want to prove is:

Lemma 3.1.4 Let $s, t, r$ be terms and $p, q$ be strings over the positive integers.

If $pq \in Pos(s)$, then $s|_{pq} = (s|_{p})|_{q}$.

If $p \in Pos(s)$ and $q \in Pos(t)$, then
2.1 $(s[t]_{p})|_{pq} = t|_{q}$
2.2 $(s[t]_{p})[r]_{pq} = s[t[r]_{q}]_{p}$

If $pq \in Pos(s)$, then
3.1 $(s[t]_{pq})|_{p} = (s|_{p})[t]_{q}$
3.2 $(s[t]_{pq})[r]_{p} = s[r]_{p}$.

If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then
4.1 $(s[t]_{p})|_{q} = s|_{q}$
4.2 $(s[t]_{p})[r]_{q} = (s[r]_{q})[t]_{p}$

The book provides proof for the first item:

As an example, we show, by induction on the length of $p$ that $s|_{pq} = (s|_{p})|_{q}$ holds for all $pq \in Pos(s)$.
For $p = \epsilon$, we have $pq = q$, and thus $s|_{pq} = s|_{q}$. In addition, $p = \epsilon$ implies $s|_{p} = s$, which shows $s|_{q} = (s|_{p})|_{q}$.
Now assume that $p = ip'$. Because $ip'q \in Pos(S)$, we know that $s$ is of the form $s = f(s_1, \ldots, s_n)$ with $i \leq n$. By definition, $s|_{pq} = s|_{ip'q} = s_{i}|_{p'q}$, and by induction $s_{i}|_{p'q} = (s_{i}|_{p'})|_{q}$. Again, by definition, we obtain $s_{i}|_{p'} = s|_{ip'} = s|_{p}$, which finishes the proof of the induction step.

I want to prove that the other items are also true. I wrote my attempt as an answer, but of course, I welcome other solutions or feedback. Thanks in advance.

Item 2. If $p \in Pos(s)$ and $q \in Pos(t)$:
2.1 $(s[t]_{p})|_{pq} = t|_{q}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
$(s[t]_{\epsilon})|_{\epsilon q} = t|_{\epsilon q} = t|_{q}$.
Case $p = ip'$:
$(s[t]_{ip'})|_{ip'q} = f(s_1, \ldots, s_i[t]_{p'}, \ldots, s_n)|_{ip'q} = (s_{i}[t]_{p'})|_{p'q}$. By induction hypothesis, $(s_{i}[t]_{p'})|_{p'q} = t|_{q}$.
2.2 $(s[t]_{p})[r]_{pq} = s[t[r]_{q}]_{p}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
Notice that $(s[t]_{\epsilon})[r]_{\epsilon q} = t[r]_{q}$ and also that: $s[t[r]_{q}]_{\epsilon} = t[r]_{q}$.
Case $p = ip'$:
$(s[t]_{ip'})[r]_{ip'q} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{ip'q} = f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{p'q}, \ldots, s_n)$. By induction hypothesis,
$$(s_{i}[t]_{p'})[r]_{p'q} = s_i[t[r]_{q}]_{p'}$$
and hence $f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{p'q}, \ldots, s_n) = f(s_1, \ldots, s_i[t[r]_{q}]_{p'}, \ldots, s_n) = s[t[r]_{q}]_{ip'}$.
Item 3. If $pq \in Pos(s)$, then :
3.1 $(s[t]_{pq})|_{p} = (s|_{p})[t]_{q}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
notice that $(s[t]_{\epsilon q})|_{\epsilon} = s[t]_{q}$ and also that $(s|_{\epsilon})[t]_{q} = s[t]_{q}$.
Case $p = ip'$:
$(s[t]_{ip'q})|_{ip'} = f(s_1, \ldots, s_{i}[t]_{p'q}, \ldots, s_n)|_{ip'} = (s_{i}[t]_{p'q})|_{p'}$. By induction hypothesis:
$$(s_{i}[t]_{p'q})|_{p'} = (s_{i}|_{p'})[t]_{q}$$
But $(s|_{ip'})[t]_{q} = (s_{i}|_{p'})[t]_{q}$ and thus the result holds.
3.2 $(s[t]_{pq})[r]_{p} = s[r]_{p}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
$(s[t]_{\epsilon q})[r]_{\epsilon} = r = s[r]_{\epsilon}$.
Case $p = ip'$:
$(s[t]_{ip'q})[r]_{ip'} = f(s_1, \ldots, s_{i}[t]_{p'q}, \ldots, s_n)[r]_{ip'q} = f(s_1, \ldots, (s_{i}[t]_{p'q})[r]_{p'}, \ldots, s_n)$. By induction hypothesis:
$$(s_{i}[t]_{p'q})[r]_{p'} = s_{i}[r]_{p'} $$
and therefore we have $f(s_1, \ldots, (s_{i}[t]_{p'q})[r]_{p'}, \ldots, s_n) = f(s_1, \ldots, s_{i}[r]_{p'}, \ldots, s_n) = s[r]_{ip'}$.
Item 4. If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then
4.1 $(s[t]_{p})|_{q} = s|_{q}$
We prove by induction on the length of $p$:
Case $p = \epsilon$: This case can't happen, as $p$ and $q$ would not be parallel positions.
Case $ p  = ip'$:
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

There are two possibilities, according to whether $i = j$ or not.
Case $i = j$:

$(s[t]_{ip'})|_{iq'} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_{n})|_{iq'} = (s_{i}[t]_{p'})|_{q'}$. We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis:
$$(s_{i}[t]_{p'})|_{q'} = s_{i}|_{q'}.$$
Since we also have $s|_{iq'} = s_{i}|_{q'}$ the result holds.

Case $i \neq j$:

Let's suppose without loss of generality that $i > j$. Then:
$$(s[t]_{ip'})|_{jq'} = f(s_1, \ldots, s_{j}, \ldots, s_{i}[t]_{p'}, \ldots, s_{n})|_{jq'} = s_{j}|_{q'}.$$
Since we also have $s|_{jq'} = s_{j}|_{q'}$ the result holds.

4.2 $(s[t]_{p})[r]_{q} = (s[r]_{q})[t]_{p}$:
Case $p = \epsilon$: This case can't happen, as $p$ and $q$ would not be parallel positions.
Case $ p  = ip'$:
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

There are two possibilities, according to whether $i = j$ or not.
Case $i = j$:

$(s[t]_{ip'})[r]_{iq'} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{iq'} =
f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{q'}, \ldots, s_n)$.
We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis:
$$ (s_{i}[t]_{p'})[r]_{q'} = (s_{i}[r]_{q'})[t]_{p'} $$
and hence $$f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{q'}, \ldots, s_n) = f(s_1, \ldots, (s_{i}[r]_{q'})[t]_{p'} , \ldots, s_n)= f(s_1, \ldots, s_{i}[r]_{q'}, \ldots, s_n)[t]_{ip'} = (s[r]_{q})[t]_{p}.$$

Case $i \neq j$:

Let's suppose without loss of generality that $i > j$. Then:
$$(s[t]_{ip'})[r]_{jq'} = f(s_1, \ldots, s_{j}, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{jq'} = f(s_1, \ldots, s_{j}[r]_{q'}, \ldots, s_{i}[t]_{p'}, \ldots, s_n) = f(s_1, \ldots, s_{j}[r]_{q'}, \ldots, s_{i}, \ldots, s_n)[t]_{ip'} = (s[r]_{jq'})[t]_{ip'}.$$


Why is NFA minimization a hard problem when DFA minimization is not? I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs?  I'm not looking for a proof or anything like that--unless a proof is simpler to understand.  I just want to understand intuitively why NFA minimization is so hard when DFA minimization is not.

For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA.

For NFA the situation is complicated as there is no unique minimal NFA in general.

Here is an example for the finite language $\{ ab, ac, bc, ba, ca, cb\}$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat.

This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity.


Computational complexity for more general problems When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three problems have a combinatorial structure, what I mean is selecting a finite number from a finite set.

How about problems in continuous domains like finding the minimum or maximum of a function in real numbers? Or solving a differential equation to find a function? Can we prove that these problems too are hard or easy in a computational complexity sense?

Finally how do I know, by looking at a problem, if asking "is the problem NP-hard?" is a valid question?

I can answer for the first part.

Computational completely is usually defined using Turing machines, that operate over finite alphabets, so questions about algorithms over the reals cannot be answered in that framework.

With regards to possible approaches to machines over the reals, they can be broadly divided into machines that work over representation and machines that can directly and atomically manipulate real numbers.

See also this question here on SE.


A doubt in Ladner's Proof I got stuck in Ladner's Proof while reading "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. Pardon me if I'm missing something really obvious here but the authors do the following:

For every function $H\colon\mathbb{N}\to\mathbb{N}$ define

$$SAT_H=\{\psi01^{n^{H(n)}}: \psi \in SAT \ and \ n=|\psi|\}$$

Now $H$ is defined as follows:

$H(n)$ is the smallest number $i<\log \log n$ such that for every $x\in\{0,1\}^*$ with $|x|\le \log n$, $M_i$ (TM encoded by binary representation of $i$) outputs $SAT_H (x)$ within $i|x|^i$ steps. If there is no such number $i$ then $H(n)=\log \log n$.

$M_i$ outputs $SAT_H (x)$ is equivalent to the statement that: The machine $M_i$ on an input $x$ outputs a 1 $\iff$ $x \in SAT_H$.

My question is:
By definition of $SAT_H$, every string in it will have length exactly $n+1+n^{H(n)}$.

For every string $x\in\{0,1\}^*$ with $|x|\le \log n$, we note that $|x|<n+1+n^{H(n)}$. So there does not exist any string $x\in\{0,1\}^*$ with $|x|\le \log n$ and $x \in SAT_H$.

This would mean that the machine $M_i$ should trivially output 0 for every string $x\in\{0,1\}^*$ with $|x|\le \log n$. But then how would such an argument be used for a proof? Where exactly am I going wrong?

Every string in $SAT_H$ has length $m+1+m^{H(m)}$ for some $m$. In particular, there will be strings of length at most $\log n$ whenever $m+1+m^{H(m)} \leq \log n$. For some reason you insist that $m$ equal $n$. Perhaps you should consider the following equivalent definition of $SAT_H$:
$$SAT_H = \{\psi01^{|\psi|^{H(|\psi|)}} : \psi \in SAT\}. $$
There is, however, a subtle point: the definition of $H(n)$ relies on the set $SAT_H$, whose definition in turn relies on the definition of $H(n)$ in what seems to be a circular fashion! However, if you work out the details you see that $H(n)$ relies on those parts of $SAT_H$ which depend on $H(m)$ for much smaller $m$. Indeed, we need to know the members of $SAT_H$ of size at most $\log n$. Each such member comes from a $\psi$ of size $m+1+m^{H(m)} \leq \log n$, and in particular $m \leq \log n$. So we only need to know the value of $H$ on the much smaller values up to $\log n$.


floating point normalised value of -1 I have, lets say, 8 bits mantissa and 4 bit exponent. Then,

-1=1111 1111
there are no 0s so how can I normalise -1 in 2's complement form?

Sorry, I found out the answer myself. It is 1000 000 manitssa and 0000 exponent.
for mantissa, 1.000 0000 = -128 *power(2,-7).

for exponent, 0000 = 0.
So, result= -128 * power(2,-7)


Cormen problem 13-1 part d I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
PERSISTENT-TREE-INSERT(T,z)
y= T.nil
x=T.root
while x != T.nil
   y=x
   if z.key < x.key
       x = x.left
   else x = x.right
if y == T.nil
    T'.root = z
    return T'
else if z.key = y.key
    y'=copy(y)
    y'.left = z
    z.p = y'
else y'= copy(y)
     y'.right=z
     z.p = y'
x = y'
while x.p != T.nil
  if x.key < x.p.key
     x' = copy(x.p)
     x'.left = x
     x.p = x'
 else x' = copy(x.p)
    x'.right = x
    x.p = x'
T'.root = x
return T'

Now the copy procedure is :
copy(x)
 w.p = x.p
 w.right= x.right
 w.left = x.left
 w.key = x.key
 return w

Now this means that I only need to copy the node that is going to be the father of the key that I'm adding and its ancestors. The book however says that additional copying is needed just because we have a reference to the parent, but I don't see it. If someone could point me in the right direction I would be much grateful.
For reference this is the exercise:
During the course of an algorithm, we sometimes find that we need to maintain past
versions of a dynamic set as it is updated. We call such a set persistent. One way to
implement a persistent set is to copy the entire set whenever it is modified, but this
approach can slow down a program and also consume much space. Sometimes, we
can do much better.
Consider a persistent set S with the operations INSERT, DELETE, and SEARCH,
which we implement using binary search trees as shown in Figure 13.8(a). We
maintain a separate root for every version of the set. In order to insert the key 5
into the set, we create a new node with key 5. This node becomes the left child
of a new node with key 7, since we cannot modify the existing node with key 7.
Similarly, the new node with key 7 becomes the left child of a new node with
key 8 whose right child is the existing node with key 10. The new node with key 8
becomes, in turn, the right child of a new root r0 with key 4 whose left child is the
existing node with key 3. We thus copy only part of the tree and share some of the
nodes with the original tree, as shown in Figure 13.8(b).
d) Suppose that we had included the parent attribute in each node. In this case,
PERSISTENT-TREE-INSERT would need to perform additional copying. Prove
that PERSISTENT-TREE-INSERT would then require .n/ time and space,
where n is the number of nodes in the tree.

Alright, it was all in the diagram:

We need to copy the descendants of the nodes in the path to make sure we don't end up with a single node having two parents


Nandgame--I am not sure I understand the Data Flip-Flop specifications Nandgame (nandgame.com) has you solve puzzles of increasing complexity which culminate in constructing a simple CPU. You start at the level of nand gates, and build everything else up out of those.

I'm having trouble understanding the specifications for the Data Flip-Flop puzzle. If I'm reading it correctly, when the "clock" bit changes from zero to one, the storage device should send its value to output, but while the "clock" bit remains either one or zero, nothing should change the output value.

What I'm stuck on is this idea of having output change when and only when the clock changes from zero to one I can't see a way to do that which doesn't allow the output to change any time the clock bit is equal to one (or trivially, equal to zero if I thrown an inverter on it fsr). But that results in a failure when I submit such solutions.

Could I just be reading the specifications incorrectly somehow?

Here is a transcription of the specification:

A DFF (Data Flip-Flop) component stores and outputs a bit, but only change the output when the clock signal change from 0 to 1.

When st (store) is 1 and cl (clock signal) is 0 the value on d is stored. But the previous value is still emitted.

When the clock signal changes to 1, the flip-flop starts emitting the new value.

When st is 0, the value of d does not have any effect.

When cl is 1, the value of st and d does not have any effect.

I have worked 20 years as FPGA logic designer but I stop at task Data Flip-Flop!
It is possible to build Data Flip-Flop. Two latches is required (sequential connection). First latch stores input data when st&!cl, second latch stores result of first latch to output when st&cl. Unbeliveable! Thanks to google...


What does exactly theoretical computer science entail? I am confused by the term "theoretical computer science". How can I distinguish which part of computer science are considered "theoretical" and which not?

To expand further, take Machine Learning. Is the study of Machine Learning Theoretical Computer Science? To me it is, because we are studying the computational qualities of learning, without declining our study into a particular technology or application, but usually, I hear machine learning spoken as a part of applied CS or engineering.

CS isn't neatly divided into "applied" and "theoretical".  Work that seeks to build systems and solve practical problems tends to get described as "applied"; work that seeks to increase our knowledge of computation tends to get described as "theoretical". Machine learning covers a spectrum that includes both.

If somebody said to me "I'm a theoretical computer scientist", I probably wouldn't assume they did machine learning – but only because people who do machine learning tend to say "I do machine learning."


1D Peak-finding problem, how to derive the formula? I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem.

About the problem

Basically, there's an array of numbers and we want to find a peak in this array (a peak is a number higher than the two numbers to the left and right of it).

The formula

  $T(n) = T(n/2) + \Theta(1)$

I watched the MIT video on "1. Algorithmic Thinking, Peak Finding" but the formula was just written as though it was something really obvious. I guess it might be, anyone kind enough to explain it?

I can sort of guess that $n/2$ comes from the fact that we are always choosing only one side of the array, but this is really just a guess and I get totally lost when suddenly the formula is expanded and we get

  $\Theta(\log_2 n)$

instead...

Your guess is absolutely correct. The time taken to process an array of length $n$ is the time taken to choose which half to recurse on, plus the time taken to do the recursion. Doing the recursion takes time $T(n/2)$, since $T(m)$ is, by definition, the time taken to process an array of length $m$. Choosing which half to recurse on takes some constant number of steps, which is what $\Theta(1)$ means.  So this gives us that $T(n) = T(n/2) + \Theta(1)$. And, implicitly, $T(1)=\Theta(1)$ since, if the array has length one, there's no recursion to do.

How to solve that recurrence to get $T(n)=\Theta(\log n)$ is covered by our reference question. A rough-and-ready way to see it is to observe that the length of the array halves on each recursive call, so the number of recursions before we reach a single-element array is the answer to the question "How many times can I divide $n$ by two before I get $1$?", which is $\log_2 n$.


Why is the Mersenne Twister regarded as good? The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list properties of this generator, most of what I can offer is bad:

It's massive and inflexible (eg. no seeking or multiple streams),
It fails standard statistical tests despite its massive state size,
It has serious problems around 0, suggesting that it randomizes itself pretty poorly,
It's hardly fast

and so on. Compared to simple RNGs like XorShift*, it's also hopelessly complicated.

So I looked for some information about why this was ever thought to be good. The original paper makes lots of comments on the "super astronomical" period and 623-dimensional equidistribution, saying

  Among many known measures, the tests based on the higher dimensional
  uniformity, such as the spectral test (c.f., Knuth [1981]) and the k-distribution test, described below, are considered to be strongest.

But, for this property, the generator is beaten by a counter of sufficient length! This makes no commentary of local distributions, which is what you actually care about in a generator (although "local" can mean various things). And even CSPRNGs don't care for such large periods, since it's just not remotely important.

There's a lot of maths in the paper, but as far as I can tell little of this is actually about randomness quality. Pretty much every mention of that quickly jumps back to these original, largely useless claims.

It seems like people jumped onto this bandwagon at the expense of older, more reliable technologies. For example, if you just up the number of words in an LCG to 3 (much less than the "only 624" of a Mersenne Twister) and output the top word each pass, it passes BigCrush (the harder part of the TestU01 test suite), despite the Twister failing it (PCG paper, fig. 2). Given this, and the weak evidence I was able to find in support of the Mersenne Twister, what did cause attention to favour it over the other choices?

This isn't purely historical either. I've been told in passing that the Mersenne Twister is at least more proven in practice than, say, PCG random. But are use-cases so discerning that they can do better than our batteries of tests? Some Googling suggests they're probably not.

In short, I'm wondering how the Mersenne Twister got its widespread positive reputation, both in its historical context and otherwise. On one hand I'm obviously skeptical of its qualities, but on the other it's hard to imagine that it was an entirely randomly occurrence.

The initial Mersenne-Twister (MT) was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs.
This page lists the Mersenne-Twister features in detail:
Positive Qualities

Produces 32-bit or 64-bit numbers (thus usable as source of random bits)
Passes most statistical tests

Neutral Qualities

Inordinately huge period of $2^{19937} - 1$
623-dimensionally equidistributed
Period can be partitioned to emulate multiple streams

Negative Qualities

Fails some statistical tests, with as few as 45,000 numbers. Fails LinearComp Test of the TestU01 Crush and BigCrush batteries.
Predictable — after 624 outputs, we can completely predict its output.
Generator state occupies 2504 bytes of RAM — in contrast, an extremely usable generator with a huger-than-anyone-can-ever-use period can fit in 8 bytes of RAM.
Not particularly fast.
Not particularly space efficient. The generator uses 20000 bits to store its internal state (20032 bits on 64-bit machines), but has a period of only $2^{19937}$, a factor of 263 (or 295) fewer than an ideal generator of the same size.
Uneven in its output; the generator can get into “bad states” that are slow to recover from.
Seedings that only differ slightly take a long time to diverge from each other; seeding must be done carefully to avoid bad states.
While jump-ahead is possible, algorithms to do so are slow to compute (i.e., require several seconds) and rarely provided by implementations.

Summary: Mersenne Twister is not good enough anymore, but most applications and libraries are not there yet.


Lambda calculus simplification excercise 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.
(λx.λy.yx)z (λw.w)
I am lost with this.
if anyone could lead me in the right direction that would be much appreciated

It is better to remind ourselves the Lambda calculus precedence rules first. See https://stackoverflow.com/q/4794330/9939883 for better details about precedence.
Application has higher precedence than Abstraction. Application is left associateive and Abstraction is right associative.
(λx.λy.y x) z (λw.w)

Since application has higher precedence,
(λx.λy.(y x)) z (λw.w)

Since application is left associative
= ((λx.λy.(y x)) z) (λw.w)

Applying repeated abstractions
= (λy.(y z)) (λw.w)

= (λw.w) z

= z


Running Time for Finding Maximum Consider the algorithm findMax that finds the maximum entry in an integer array.

Algorithm findMax($A$)
    Input: An integer array $A$
    Output: The maximum entry of $A$

1. m <- A[0]
2. for i <- 1 to A.length - 1 do
3.     if A[i] > m then
4.        m <- A[i]
5. return m

Show that there are constants $c_1,d_1,c_2,d_2 \in \mathbb{N}$ such that $c_1n + d_1 \leq T_{findmax(n)} \leq c_2n + d_2$ for all $n$, where $n$ is the length of the input array.
Argue that for every algorithm A for finding the maximum entry of an integer array of length $n$ it holds that $T_A$$(n)$ $\geq n$.

NOTE: The (worst-case) running time of an algorithm A is the function $T_A: \mathbb{N} \rightarrow \mathbb{N}$ where $T_A$$(n)$ is the maximum number of computation steps performed
by $A$ on an input of size $n$.

My intuition was that $c_1$ and $c_2$ correspond to the number of times the next element of the array is greater than the current maximum, but I don't see how to fit it in the equation.

1 - executed $1$ time
2 - executed $n$ times
3 - executed $(n-1)$ times
4 - executed $c$ times - - - best case: $0$ times / worst case: $(n-1)$ times
5 - executed $1$ time

In the total sum of steps:

Step 1 + Step 5 = 2 times
Steps 2,3,4 $\leq 3n$ times

Therefore, $c_1 = 1$, $d_1 = 2$, $c_2 = 3n$, $d_2 = 2$.

For the second question, would it be enough to show that the best-case scenario (array sorted in non-increasing order) takes at least $n$ steps?

Question 1

I think you are overcomplicating things, the question is about $\mathcal{O}$-notation, you don't need any meaning attached to these constants. Try making your life easy and pick simple ones:

You only need a lower bound, so just set $c_1 = d_1 = 1$, clearly $n + 1 \leq T_{\text{findMax}(n)}$.

Similarly you only need an upper bound, set $c_2 = 4$ and $d_2 = 42$, giving you $4n + 42 \geq T_{\text{findMax}(n)}$.

Question 2

It's not clear how $T_A$ is defined, so it's hard to answer Question 2.

Assume there is an algorithm $A$ with $T_{A(n)} = t < n$. So this algorithm is restricted to read/compare at most $t$ elements of $a_1,\dots,a_n$ and therefore there is always a sequence $a_1,\dots,a_n$ where the algorithm will fail, ie. the actual maximum is not among the $t$ elements. $\Rightarrow\!\Leftarrow$


Symmetric functions in NC¹ A boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$.
It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there is a circuit of depth $O(\log n)$ computing it.
What is known about the constant inside the $O()$ notation? Specifically, can one construct, for every $c$, a symmetric function requiring a circuit of depth at least $c \log n$? Or there is some constant $c_0$ such that every symmetric function has a circuit of depth at most $c_0\log n$?

We can treat the input $x$ as a boolean array. Using an $O(\log n)$ depth sorting network (such as the AKS network), we can sort $x$ in nonincreasing order. Calling the result $y$, using $O(1)$ more depth we can compute $z_i = y_i \land \lnot y_{i+1}$ (extended in the right way to the boundary). The vector $z_0,\ldots,z_n$ is the indicator vector of the Hamming weight of $x$. At this point you can compute any symmetric function using $O(\log n)$ more depth.
This shows that there is a universal constant $C$ such that all symmetric functions can be computed in depth $C\log n$ using constant fan-in circuits.


Insertion and deletion complexities for a linked list and array I have the following table that compares different operation complexities for a linked list and array:

                        Linked List |   Array   |   Dynamic Array
Deletion at ending      O(n)        |   O(1)    |   O(n)
Insertion in middle     O(n)        |   O(n)    |   O(n)
Deletion in middle      O(n)        |   O(n)    |   O(n)

Can anyone please explain why:

Deletion for Dynamic Array is O(n)?
Insertion and deletion in middle for all data structures is O(n)?

Thanks

The array may need to be reallocated if there are too many free cells, and this costs $O(n)$ (non-amortized)
For arrays, the array portion which comes after the affected element must be moved one position left or right, so that's $O(n)$. For lists, it depends. If you have the pointer to the previous cell w.r.t. the inserted/deleted one, this can be done in $O(1)$. If you don't, and you only have the pointer to the list head, then you have to scan the list -- half the list, on average, will be scanned, costing $O(n)$.


Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$? By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).

The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s terminated by an end-of-string character. The tape head starts at the beginning of the string. The goal is for the tape to contain the original string in reverse order, terminated by an end-of-string character, with the tape head returned to the beginning of the string when the Turing machine finally halts.

The Turing machine can use as large an alphabet as we like (so long as it contains $0$, $1$, and an end-of-string character), and can have as many states as we like. Is there a fixed Turing machine that can complete this task in time $o(n^2)$?

It's easy to do this in time $O(n^2)$ using just a few states and symbols. It seems intuitively clear that something prevents us from doing it more than a constant factor faster, but I've never been able to prove it, and I often worry late into the night about miraculous applications of network coding or voodoo magic that somehow get a logarithmic speedup...

The standard way to prove things like this is to show that $\Theta(n)$ bits of information must cross at least $\Theta(n)$ points.

That is, if you're reversing it "in place", the first third of the bits must cross all $n/3$ middle cells and end up in the last $n/3$ cells. Since the head moves $O(1)$ bits a distance at most $1$ cell each step, this requires $n^2/9$ steps. If the reversed copy ends up in a different set of cells, a very similar argument gives an $\Omega(n^2)$ lower bound.

It takes some work to make this intuitive idea rigorous, but it has been done, although I don't have enough time to locate the papers these results appeared in. If anybody can point to a relevant paper, please edit this answer to do so.


Is physical pages zeroed out before it's mapped to a virtual page? I don't how this works. According to me if the physical memory is not cleared then there is some security risk as there may be some sensitive information in it from the other processes. How does the kernel take care of this?

Yes, the kernel zeroes out pages before allocating them to a user-level process.  The details depend on the specific operating system; some may zero it out when the page is needed, others might run a separate thread that periodically zeroes out pages in anticipation that they'll be allocated.


DFA for a language that accepts the addition of multiple of 2 and multiple of 5 I am trying to draw a DFA that accepts the following language:

$L=\{a^{2i+5j} : i , j \geq 0\}$

I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is correct.

All natural numbers are expressible in the form $2x+5y$, except for $1,3$. You can check this directly, of use the solutino of the Frobenius problem for two denominations. Therefore another way to write your language (assuming the alphabet is $\{a\}$) is
$$
\overline{\{a,a^3\}}.
$$
You can construct a DFA for this language using 5 states, that count up to 4 and then saturate.

If you want to implement the constraint $2x+5y$ directly as an NFA (which is more economical for larger values of $2,5$), then you construct the following NFA:

States: $q_0,a_1,b_1,b_2,b_3,b_4$.
Initial state: $q_0$.
Final states: $\{q_0\}$.
Transition function:
$$
\begin{array}{c|cccccc}
q & q_0 & a_1 & b_1 & b_2 & b_3 & b_4 \\\hline
\delta(q,a) & a_1,b_1 & q_0 & b_2 & b_3 & b_4 & q_0
\end{array}
$$

In words, there is a 2-cycle and a 5-cycle sharing a vertex $q_0$, which is also the initial state and the unique final state.


MLTT not being Turing Complete Where can I find a proof that Martin-Löf Type Theory isn't Turing Complete, if such proof exists?

It is a general feature of reasonable total programming languages that they do not have self-interpreters, but interpreters for reasonable programming languages are Turing-computable. So, a concrete example of a total computable function which is not definable in a total programming language is an interpreter for that programming language.

See Definition 2.1, Theorem 2.2, and Corollary 2.3 of this note. It proves that a self-interpreter for Gödel's T is not definable in Gödel's T. You can use the exact same proof for MLTT.

It is generally well known that a confluent terminating normalization system such as that of MLTT leads to a Turing-computable normalization procedure.