Recursion Theorem : why does $SELF$ need $A$ and $B$ parts? I read in Sipser's book that a machine can make copies of itself using a special function $q(w)$ which takes a string $w$ as input and prints out the string $w$.

A $TM$ $SELF$ can print out its own description $AB$ using two parts. For the first part $A$ prints out $<B>$ since it has the description for $B$ inside its finite control. For the second part, $B$ looks at the tape for its own description $<B>$, and uses $q$ to come up with $<A>$. Both descriptions are then concatenated to come up with $<AB>$.

I understand the proof above, but I couldn't get it yet why $SELF$ should have two parts. If its own description is writtten in its finite control, couldn't it just use $q$ to print out its own descrition?

No, it can't.

Intuitively, $A$ can be described by print "B". Whatever $B$ is, there is such an $A$. Note that, by construction, $A$ is a program "longer" (roughly speaking) than $B$.

If we try to write $A$ as print "A", we incur in a problem, since $A$ should be "longer" than itself. Hence, such a definition is ill-posed.

For the same reason, you can't write a description of a TM inside its own finite control: you would need an infinite amount of states for that.

You can search the web for "quines": programs printing their own source code. Virtually all of them have to workaround the fact that they can't include their own source code in themselves, and have finite length. Hence, they must exploit something analogous to the $q()$ function you mention.

A typical quine can be designed as follows. Start from a clumsy attempt:

myself=""
print myself

Obvious partial fix: copy its source code within myself

myself="myself=\"\" \n print myself "
print myself

Not yet there: we should replicate the source code inside the innermost quotes, and so on, infinitely many times. Not good.

Instead, we use a placeholder for that "infinite" replication, which we replace at runtime with the whole code.

myself="myself=\"PH\" \n print myself "
print replace(myself, "PH", myself)

Obvious fix

myself="myself=\"PH\" \n print replace(myself, \"PH\", myself)"
print replace(myself, "PH", myself)

Assuming that replace only replaces the first occurrence of the placeholder PH, and that we fix the whitespace precisely in myself, this is now a program printing itself -- a quine.

Note how the replacement of PH must be done at runtime. Similarly, in the Sipser proof, we must compute q() at runtime -- we can't encode that in the finite control.


Myhill-Nerode equivalence classes of $\{1^n0^n\}$ I have the following task and its solution.
Question

Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
give all equivalence classes of the Myhill-Nerode relation.

Solution

$[1^k]_{\equiv A} = \{1^k\}$ for $k \in \mathbb N$.
$[1^\ell0]_{\equiv A} = \{1^{\ell+i-1} 0^i \mid i \geq 1\}$  for $\ell \in \mathbb N^+$.
$[0]_{\equiv A} = \{ 0x, 1^n 0^m, x01 y \mid x,y \in \Sigma_A^* \land n,m \in \mathbb N^+ \land m > n \}$.

What are they doing in the second bullet of the solution?
The first and third bullets are clear. In the first they construct the
equivalence classes of all $1$'s including $\lambda$.
In the third bullet they construct just one equivalence class with all the words which are not in the language $A$.
But what are they doing in the second bullet?
What does the exponent $\ell+i-1$ mean?
Why don't they write $[1^n0^m]_{\equiv A} = \{1^n 0^m \mid n,m \in \mathbb N^+\}$?

I think it makes sense to answer your subquestions out of order.

  Why they don't write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

They're supposed to be equivalence classes. $[1^n0^m]$ would break up lots of classes, and duplicate lots of the states from line 3.

  What does the Exponent $n+i-1$ mean?

Firstly, $n+i-1 \ge i$, so there are at least as many $1$s as $0$s.

Secondly, $n$ is the parameter which defines the class.

So $\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}$ is the set of states which need $0^{l-1}$ to reach the accepting state.


Why top down merge sort is popular for learning, while most libraries use bottom up? Most libraries use some variation of bottom up merge sort, but top down merge sort seems to dominate web sites and forums.

Assume reasonably optimized implementations, where a single working array is used in addition to the original array, and copy or copy back avoided in top down merge sort by tying the direction of merge (to or from the working buffer) based on level of recursion (bottom up does this based on merge pass), then the key differences are the generation and storage of indices for runs via recursion and storage on the stack for top down versus iteration and storage possibly in registers for bottom up, and cache locality affected by the order of merge operations (top down is depth first, left first, while bottom up is breadth first).

For cache locality issues, assuming at least a 4 way set associative cache, that's enough for 2 lines for input, and 1 line for merged output, and the merge operation is a sequential operation for the 2 input runs and the merged output run. It's not clear to me if there are a few levels of recursion for top down versus passes for bottom up where top down is more cache friendly.

In all the benchmarks I've run, bottom up merge sort is faster than top down, which would explain why most libraries use some variation of bottom up merge sort. As array size increases, the relative difference decreases because most of the time is spent in a merge function that can be identical for top down and bottom up.

From a historical perspective, going back to the days of disk or tape sorts, merge sort started out as bottom up merge sort (or a variation called polyphase merge sort).

My questions are when and why top down merge sort became more popular in a classroom environment, or later on the web?

Update - I'm also wondering why bottom up merge sort seems to be so rarely seen in a classroom environment, web sites, or forum sites. My guess is that 80+% of the questions about merge sort at Stack Overflow are about top down merge sort. I only recall one question about bottom up merge sort in the last month or so.

Because top-down mergesort is conceptually simpler, and fits right into the curriculum of new computer scientists that learn about recursion. A small constant performance difference between top-down and bottom-up is irrelevant for its educational value.


What specifically makes quantum computers useful? I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.

That seems to be what people point to as being what makes quantum computers special or useful.

However after you have processed the superpositional inputs, you have a superpositional result, of which you can only ask a single question and it collapses into a single value.  I also know that it isn't (currently?) possible to clone the superpositional state, so you are stuck with getting an answer to that one question.

In both cases, it looks like that multi processing ability really hasn't gotten you anything since it's effectively as if only one state was processed.

Am i misinterpreting things, or does the real usefulness of quantum computing come from something else?

Can anyone explain what that something else is?

Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. In a quantum computer, it can make the outcome less likely.

Quantum algorithms are carefully designed so that wrong answers tend to be destructively interfered, leaving only the desired solutions as measurement outcomes. This is tricky to do, and not every problem allows for it. Grover's Search Algorithm is an excellent example of this effect, so here's a beginner-level post about Grover's algorithm.

Other useful properties quantum computers have access to:

Entanglement for coordination and communication improvements (e.g. symmetry breaking, superdense coding, beating bell tests).
The uncertainty principle for cryptography (e.g. quantum key distribution, Einstein-certified random numbers).
Manipulating actual physical states to implement quantum sensors and other lab equipment (who wouldn't want a counterfactual bomb tester?).

(Scott Aaronson likes to say everything interesting about quantum is due to superpositions preserving the 2-norm instead of the 1-norm like probability distributions do. All the more specific useful effects I mentioned do derive from the underlying math.)


Reduction between parametrized problems Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers?

That is given two parametrized problems whose unparametrized version is $NP$-complete when can we construct reductions between them?

In general NP complete problems the reductions are polynomial time.

What is the corresponding analogue in parametrized problems?

You are asking two questions, I will answer the second. Parameterized reduction from problem $P$ to $Q$ is a function $\phi$ with the following properties :

$\phi(x)$ can be computed in time  $f (k)·|x|^{O(1)}$, where $k$ is the parameter of $x$,
$\phi(x)$ is a yes-instance of $Q$ if and only if $x$ is a yes-instance of $P$.
If $k$ is the parameter of $x$ and $k′$ is the parameter of $\phi(x)$, then $k′ ≤ g(k)$ for some function $g$.

  Note that $f(k)$ need not to be a polynomial function in $k$, it could be like $2^k$ or $c^k$, where $c$ is constant.

Example: INDEPENDENT-SET instance $(G,K)$ into CLIQUE instance $(G',K)$ is a parameterized reduction. You can verify all three conditions mentioned above.

Reference : http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt3


Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate? Suppose I have 100 qubits that I want to entangle and put into superposition. To do so I construct a Hadamard gate to do this. By definition, the Hadamard is going to be a 2^100 X 2^100 matrix - which is huge.

How does one go about actually performing this operation? The size of the Hadamard matrix is exponential relative to the number of qubits (ie 2^100 X 2^100). Is there a way to perform this operation without actually making this huge matrix? Or can we only work with a 'small' number of qubits at once?

Follow up question: does using 100 4x4 Hadamard gates (one for each qubit) do the same thing as using a single 2^100 x 2^100 Hadamard gate? If so, how do these qubits become entangled?

It does require that, but you get it for free.

When you apply a 2x2 gate to a single qubit, the gate you are applying to the $n$-qubit system that qubit is in is automatically $2^n$ x $2^n$. If you apply an $H$ to the third qubit out of six, then the operation you applied to the six qubits is $I_2 \otimes I_2 \otimes H \otimes I_2 \otimes I_2 \otimes I_2$. That's a 64x64 matrix; exactly what you needed.

So performing a Hadamard transform on $n$ qubits is actually very easy, even though some very large matrices are being thrown around if you think about what's happening in that way. Just independently hit each qubit with the usual single-qubit $H$ gate.

Note that Hadamarding each qubit doesn't entangle them, though. It puts them in a superposition, but the state still factors. If you want to entangled all the qubits, you could instead hit one of them with a Hadamard then use Controlled-Nots to toggle each of the other qubits based on that Hadamard'ed qubit.


How to construct object oriented programming in pseudo code? I am studying a data structures course in which we have given many assignments on constructing data structures (like trees, arrays, and linked lists).

In class template, what kind of notation should I write for these operators (::,->) and the others operators which are used in C++? Can anyone elaborate more about writing pseudo-code for object oriented programs?

Pseudocode has no formal definition. Use whatever notation you want, as long as it is either self-explanatory (even for people unaware of C++) or explained in the text.

I suggest looking at several textbooks and papers to see what the "industry standard" is, and using something similar.


What is the origin of dot notation? In object-oriented programming, dot notation is used when accessing the properties or methods of a class:

Dog dog
print dog.name
>> "Fido"
dog.walk()
>> Walking the dog now...

What is the origin of that syntax and why the . to notate it? It must date to some early object-oriented language, but I couldn't find mention of it anywhere.

In [1] (authored by one of the co-creators of Simula), there is a suggestion that Simula 67 may have been the first to use this dot notation. Given that Simula is widely credited for being the first OO language, it may be tricky to find an earlier example specifically in an OO context.

EDIT:
On DiscreteLizard's suggestion in comments, I took a peek at the use of this dot notation for specifying fields in a record. As it turns out, according to this specification of the PL/I language for the IBM System/360 from July 1965, the dot notation was indeed used to identify fields within structures:

  A qualified name takes the form:

  identifier {. identifier} ...

  Examples:
  1. A program may contain the structures:

  DECLARE 1 CARDIN, 2 PARTNO, 3 DESCRIPTION, 2 PRICE;

  DECLARE 1 CARDOUT, 2 PARTNO, 2 DESCRIPTION, 2 PRICE;

  Elements are then referred to as:

  CARDIN.PARTNO

  CARDOUT.PARTNO

  CARDIN.PRICE

Dahl, Ole-Johan. "The Birth of Object Orientation: the Simula Languages." From Object-Orientation to Formal Methods. Springer, Berlin, Heidelberg, 2004. 15-25.


Why N-Queens Problem is not used as experiment in CSP thesis? I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems.

If so,when I do master thesis in CSP,it is reasonable to experiment algorithms with N-Queens.

How can N-Queens problem be changed CSP parameters like Tightness,Constraint Density to experiment?

I wonder why many researchers test their CSP algorithms with Zebra problem, sudoku ,random CSP but why not N-Queens problem? Is N-Queens problem with CSP does not give better results?

n-queens problem can be solved quite efficiently with a very simple algorithm (finding all solutions takes ages, because the number grows exponentially).

Getting anywhere near that efficiency with a general method is impossible.


Min cut of at most k edges I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.

Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow \mathbb{N}$, find an efficient algorithm to determine whether the graph has a min cut of at most $k$ edges (assume $k=100$).

My thinking was computing a min cut, then for every edge on that cut, increase it by 1 and compute the min cut again - if the max flow has risen, that means that that edge exists in every single min cut. And If I found there to be over 100 of these edges, then there is no min cut of at most $k$ edges.

However, I don't think that if I found there to be less 100 of these edges, there's necessarily a min cut of at most 100 edges.

Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.


definition of formula validity I read in some sources that valid formulas are tautologies (valid under every evaluation). In the others, I read that these are formulas that have conclusions true when premises are true. Are these just equivalent definitions because ⊨ P → Q is equivalent to P ⊨ Q?

Yes. These definitions are equivalent,  noting that not all valid formula have the form $P\to Q$, though any formula $Q$ is equivalent to $\top\to Q$.


Appreciation of the 5 state process model I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class.

A process state model is an abstraction (or model) which is used to explain what can happen to a process. Give a state of the process, it tells you what is the next allowed states and what causes the process to be in that state, and so on. A model is only at a certain level of abstraction. In this question, we will be focusing on the 5-state process model from the lecture.

(a) Is it possible for a process to never go to Terminated state. If so, give 3 possible scenarios when this can occur. If not, explain your reasoning.

(b) Suppose a process is in terminated state. Discuss whether you should be able to check at any time if a process is in terminated state at all times. Are there any implications?

5 state process model

I have attempted to answer all these questions, but because of their theoretical nature, I think there might be a lot more dimensions to these.

a)
I think it is not possible for a process to never go to termination, given enough time, because there are multiple ways a kill() or exit() command can be called, depending on their policy and mechanism in the operating system?

b)

I think it is important because a process in termination state still holds some data and requires the OS to do some cleanup. A process might not be running for other reasons other than termination, it could be in a blocked state without any IO activity or just be inside the ready state.

  Can someone check my understanding on these questions? Thanks.

a) A process does not necessarily have to terminate, it only reaches the terminated state if it exits voluntarily. If a process has no exit statement (e.g. a server), it would never reach the terminated state unless killed by the OS. Other ways for a process to never reach termination include not being scheduled when ready because some other process with higher priority is always scheduled before it (starvation), or being stuck in the blocked state waiting for some resource but never getting it, for example, trying to obtain a lock (deadlock/livelock).

b) If we cannot check wether the process has reached the terminated state or not, we can never free up its resources (stack, data, process table entry). It is important for the OS to be able to tell what state a process is in for the scheduler to work properly. If a child process terminates and reaches the 'Z' state, the operating system needs to have this information when it tries to pick a process to schedule. This prevents processes that no longer need CPU time from being scheduled. If the OS did not have this state information available at all times, the implications would be wasting memory space and CPU time.

I suggest reading up on the wiki for the
exit,
wait and
fork syscalls for better understanding :)


Simplify the definition of substitution in Lamdba calculus Substitution in untyped Lambda calculus is complicated by variable capture.
Can this boring technical complication be entirely avoided by some restriction on the standard formation rules? Something that prevents the dangerous symbol duplication. If so, how? Otherwise why not?
Alternatively, can the complication be avoided by uniformly alpha-converting every Lambda abstraction of the final composite, to ensure that every binding/bound variable symbol only appears locally (and therefore never as a free variable in the argument of an application term). If so, it seems that the substitution rules could be simplified.

Yes, there are several techniques, such as de Bruijn indices and explicit substitutions. Actual implementations, at least those that actually have to work efficiently, use such techniques and never implement substitution by renaming variables.


What's the relationship of $n^n$ and $n!$ complexity with respect to EXPTIME? We know that:

$k^n = o(n!)$
$n! = o(n^n)$

where $o$ refers to "little o notation" (i.e. bounds that are asymptotically not tight).

With that in mind:

Are there any defined or academically established classes for problems with complexity of at most $O(n!)$ and $O(n^n)$?
What is the set relationship for these classes of problems with respect to $\mathsf{EXPTIME}$ or e.g. $\mathsf{2\mbox{-}EXPTIME}$?

$\mathsf{EXPTIME}$ is the class of problems solvable by algorithms whose running time is $O(2^{n^c})$ for some $c>0$. In contrast, $\mathsf{E}$ is the class of problems solvable by algorithms whose running time is $O(2^{cn})$ for some $c>0$.

These definitions show that problems solvable in time $O(n!)$ or $O(n^n)$ are in $\mathsf{EXPTIME}$, but not necessarily in $\mathsf{E}$.


Boolean variable true iff equation is satisfied in ILP Assuming $y$ is a boolean variable in an ILP program (that is $y \in Z$, s.t. $0 <= y <= 1$) and $x_1$, $x_2$ are bounded integer variables between $0$ and $M$. I want to encode the following high level constraint:

$$y = 1 \iff x_1 \le x_2$$

So far I've got this:

$$x_1 \le x_2 + (M+1)y$$

This enforces that whenever $x_1 > x_2$ is true, $y$ must be $1$ or the equation won't hold. However, if $x_1 \le x_2$, nothing is restricting $y$ and thus could either be $0$ or $1$.

What other equation could I add in order to encode the constraint?

You can do this by introducing the two inequalities

$$x_1 \le x_2 + M (1-y)$$

and

$$x_1 > x_2 - M y.$$

The former encodes the requirement $y=1 \implies x_1 \le x_2$ (you can see that if $y=1$, then the $M(1-y)$ term disappears; if $y=0$, then $M(1-y)$ becomes something huge and the inequality is automatically satisfied).  The latter encodes the requirement $y=0 \implies x_1 > x_2$ (for similar reasons).

Hopefully this gives you an idea how to handle other kinds of implications as well, should they arise.  Basically, multiply by something big, and add it/subtract it somewhere.


What data size is sent to and read from physical RAM? When you have a cache mis, you need to fetch a block from RAM. If said block is 64 bytes big, do you need to have buses that are 512 bits (= 64 bytes) wide to transfer data from the RAM to the cache? And when writing to RAM do you write to the whole 64 byte block?

There is no requirement that a transfer between memory and cache use one line per bit. In fact, DDR3 DRAM uses a burst length of eight, meaning that eight bits are transferred per line in four cycles at double data rate. (DDR3 supports burst chop of only four transfers, but this has the same timing constraints for a read following a read and a write following a write. Burst chop can reduce energy use and other DRAM ranks can use the memory channel during the inactive time.) By requiring burst transfers, memory chips can be made more cheaply while still providing high bandwidth.

The write interface to DRAM is likewise constrained. In addition, the modified nature of portions of cache smaller than a cache block is usually not tracked, so the cache would not know that it actually only needs to writeback part of the cache block. (Such constraints are not inherent in memory systems. Caches could track validity or cleanness at any granularity, at the cost of addition storage and complexity. Interfaces could be defined to support arbitrary sized transfers, including the use of mask bits to tell the memory chips to ignore specific data, but the complexity is generally not considered worthwhile.)

One advantage of a narrower interface is that synchronization of all the lines is easier, making it easier to produce an interface with a fast clock providing higher bandwidth with the same number of lines.

Note also that more than one memory channel can be implemented in a CPU. It is also possible to gang two or more memory channels together to form a single interface.


How to find a minimum set of axioms within a set of propositions? I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want to find a subset of the propositions to be defined as axioms, in the sense that, these propositions being true imply that all the others are true. The number of axioms should be as small as possible. I want to know whether there are some methods?

Determining whether a proposition follows from a set of axioms is an NP-Complete problem. Finding a minimal set of axioms from a set of propositions naturally invokes this problem many times as a subroutine.

For example, consider the following set of propositions:

$$P = \{v_1, v_3 \vee v_2, v_1 \wedge v_3\} $$

A minimum set of axioms from this set is $\{v_1 \wedge v_3\}$. But to find it, you have to prove $v_1$ and $v_3\vee v_2$, and those proofs are in general hard to find. The problem is there a set of axioms $A$ for a set of propositions $P$ with at most $k$ axioms? is in $\Sigma_{3}^{p}$, which means it's in the third level of the polynomial hierarchy, which means that it's two levels higher than NP in the way that NP is one level higher than P, to give you an idea of its complexity. I do not know if it is also in a lower level. Browsing through this survey (link) [1] of problems that are complete for various levels of the polynomial hierarchy, I do not see this problem among them, so it's possible that it's not $\Sigma_{3}^{p}$-Complete, but it wouldn't surprise me.

Before you go out to look for a set of axioms, you may want to know whether the set of propositions is sound and any subset is complete (untrue propositions cannot be proved, all true propositions can be proved). These problems have similar NP-scary complexity. First, Is this set of propositions complete? is a problem in $\Pi_{2}^{p}$ of the polynomial hierarchy, because it asks, for all $p\in P$, can $p$ be proved from propositions $P\setminus \{p\}$? Completeness of your system is in co-NP as it asks, Forall all $p\in P$, can $p$ not be proved from $P \setminus \{p\}$? So it seems that checking for soundness and completeness is easier than finding a minimal axiom set, but not by much. (I'm less sure about this paragraph. Is it true that a logical system of propositions $P$ is sound iff for all $p\in P\colon \neg p$ cannot be proved from $P\setminus \{p\}$?)

The comments to your question pertain to the context of database entries, but they are purely syntactic and only establish redundancy in the database, whereas if your question is about propositions, as I understand it, then the contents of the database must be inspected semantically, and this leads you to this complexity nightmare.

[1] M. Schaefer, C. Umans, Completenss in the Polynomial Hierarchy, A Compendium, 2008.


Tallest Person Average Memory Updating? We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?

A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$  enter a room. We want to find the index, $i$, of the tallest person in the room. We have one variable for saving that index, which is updated when we see a person who
is taller than the maximum height so far. We want to calculate the average number of times our variable is updated. For simplicity, assume that $p$ is a permutation of $\{1, 2, \dotsc, n\}$

Short answer: it is close to $\ln n$. (i.e: natural logarithm)

How can one solve such a question?

Let $T(n)$ denote the total number of updates to the variable when $n$ people have entered the room. For example, with $n=3$ there will be $3!=6$ possible orders where the heights are $1, 2, 3$. Notice that once the height 3 person enters, no further updates will occur, so let's group the six possible arrangements by when the height 3 person enters:
$$\begin{array}{ccc}
\mathbf{3}21 & \mathbf{3}12 \\
1\mathbf{3}2 & 2\mathbf{3}1 \\
12\mathbf{3} & 21\mathbf{3} \\
\end{array}$$
For each of these arrangements, let's count the number of updates we have to make before we see the tallest person. In the two arrangements where the height-3 person arrives first, there are 0 earlier updates. In the second row above, there will be 1 update we have to make before the tallest person arrives and in the third row there will be either 1 or two updates before the tallest person arrives: arrangement $12\mathbf{3}$ will require 2 updates (one for the height-1 person and another for the height-2 person and the arrangement $21\mathbf{3}$ will require 1 update, for the height-2 person. In this $n=3$ case, then, we'll have $0+2+3$ total prior updates (0 in row 1, 2 in row 2, and 3 in row 3). To this add the $3!=6$ updates for the tallest person, giving us a total $T(3)=5+6=11$.

Now let's look at the general case for $n$ people. As we did above, let's group the $n!$ possible arrangements by when the height-$n$ person arrived. Denote this tallest person by $X$ and the rest of the people by dots. As we did above, we'll defer counting the last update until later.

We'll have these possibilities, each of which can happen in $(n-1)!$ ways:
$$\begin{array}{cc}
\text{arrival of }X & \text{arrangement}\\
1 & X\circ\dotsc\circ \\
2 & \circ X\circ\dotsc\circ \\
3 & \circ\circ X\circ\dotsc\circ\\
\dotsm & \dotsm \\
n & \circ\dotsc\circ X
\end{array}$$

For each row above we'll count the total updates before the tallest person arrives: Obviously if the tallest person arrives first, we'll have no prior updates, so the first row above will give a total count of 0. Each of the following rows will look like this:
$$
\underbrace{\circ\dotsc\circ}_k\ X\ \underbrace{\circ\dotsc\circ}_{n-1-k}
$$
The first set of $k$ dots can be filled with the heights $\{1, 2, \dotsc, n-1\}$ and there are $\binom{n-1}{k}$ ways to choose these sets, each of which will contribute $T(k)$ updates. The last set of $n-1-k$ dots can be filled with the remaining numbers in $(n-1-k)!$ ways. Thus each row in the table will contribute
$$
\binom{n-1}{k}T(k)(n-1-k)!
$$
to the total of prior updates. Adding these and including the $n!$ updates for the tallest person we have the recurrence relation
$$\begin{align}
T(n) &= n! + \sum_{k=1}^{n-1}\binom{n-1}{k}T(k)(n-1-k)!\\
 &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}T(k)(n-1-k)!\\
 &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!}T(k)\\
 &= n!+ (n-1)!\sum_{k=1}^{n-1}\frac{T(k)}{k!}\\
\end{align}$$
Divide both sides by $n!$ to get
$$
\frac{T(n)}{n!} = 1 + \frac{1}{n}\sum_{k=1}^{n-1}\frac{T(k)}{k!}
$$
and remember that the average number of updates, $U(n)=T(n)/n!$ which gives us.
$$
U(n) = 1 + \frac{1}{n}\sum_{k=1}^{n-1}U(k)
$$
Now we'll find a simple closed form for this:
$$\begin{align}
U(n) &= 1+\frac{1}{n}\sum_{k=1}^{n-1}U(k)\\
 &= 1+\frac{1}{n}\left(\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1) &\text{pulling out the last term}\\
 &= 1+\frac{n-1}{n}\left(\frac{1}{n-1}\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1)\\
 &= 1+\frac{n-1}{n}(U(n-1)-1)+\frac{1}{n}U(n-1) & \text{definition of }U(n-1)\\
 &= U(n-1)\left(\frac{n-1}{n}+\frac{1}{n}\right)+\left(1-\frac{n-1}{n}\right)\\
 &= U(n-1) + \frac{1}{n}
\end{align}$$
Whaddya know? With $U(0)=0$ we just have
$$
U(n) = 1 + \frac{1}{2}+\frac{1}{3}+\dotsm+\frac{1}{n} = H(n)
$$
the $n$-th harmonic number, as it's known and it's also known that $H(n)$ is asymptotic to $\ln n$.


What is a rewrite-based system? I am reading about this in the context of the K semantic framework. I keep encountering terms such as rewrite-term and rewrite logic. My main aim is to understand what is K doing and how it works, so maybe this would be a bit off-topic.

I am assuming that you have some background in a functional programming language like Haskell or ML or OCaml because that is the easiest thing for me to explain this in terms of.

Haskell is, or can be viewed as, a rewrite system. When you simplify little expressions you are rewriting the expression in little steps until you get to the final result (normal form).

For instance a list like [1, 2, 3] can be denoted by the term (1 : (2 : (3 : [])))

Another term is a term like

(1 : (2 : [])) ++ (3 : [])

which can be reritten as

1 : ((2 : []) ++ (3 : []))

which can in tern be rewritten as

1 : (2 : ([] ++ (3 : [])))

which can (finally) be rewritten as

(1 : (2 : (3 : [])))

This was all based on the following rewrite rules

(x:xs) ++ ys -> x : (xs ++ ys)
[]     ++ ys -> ys

where x -> y can be thought of as "if you see 'x' replace it with 'y'"

So basically a rewrite system is a system that has a set of rules that explain how to rewrite certain subterms of a term in a system. Once there are no rules left that apply the term is in normal form. Some times terms have no normal form however, these are either errors or infinite loops in systems like Haskell.

example:

addLots x -> 1 + addLots x

addLots 0 (this expression has no normal form as we just have to keep adding 1s on)

Haskell also gives us some guarantees on the order that it will apply the rewrite rules (but does not fully define it). For instance

case 1 : (addLots 0) of {x : xs -> 2}

will evaluate to 2. If the order was either unspecified or chose to fully evaluate 1 : (addLots 0) then it would have not ever reached it's normal form.

A rewrite system does not in general have to have such an order however; it just has to say which rewrites are valid. Another example of a rewrite system is first order logic. You are given a set of rewrite rules called "inference rules" and a set of terms called "first order logic terms". You can derive tons of expressions from other expressions in just such a way. Like the following two rewrite rules.

~~x -> x
x -> ~~x

we could keep gong back and forth between these and we would get an infinite loop but a human knows how to apply these in just the write way to derive interesting theorems.

edit:
It seems to me (from a brief look) that the K semantic framework is a system for defining what terms on in the language (quite like data expressions in Haskell but more advanced) and then it lets you define rewrite rules on these expressions (a bit like functions in Haskell). In the K semantic framework syntax and rules are totally separated where as in Haskell data expressions define the syntax of normal forms and function definitions define a new bit of syntax along with a reduction rule on that new syntax.


Is Maximum Independent Set in coNP I need to determine whether the following problem $X$ is in coNP:

  Given a graph $ G=(V,E) $ and a positive integer $s\leq|V| $, is there an independent set that is the largest for $G$ of size at least $s$?

My solution for this was that in fact the above problem is in coNP because we can provide an NP solution for $\overline{X}$ which has the following certificate and certifier.

The certificate being a set of vertices $V'$.

The certifier does two things:

Checks if  $V' \subseteq V$.
Checks for each pair of vertices in $V'$ if there exists no edge.
Checks if  $|V'|<s$.

The certifier computes this in $O(V+E)+O(1)$.

Is this the right way to show if X is in coNP?

Edit: The independent set is required to be the largest possible for graph $G$.

Independent set is NP-complete, so it's unlikely to be in coNP.

Moreover, the complement problem would sound like "all independent sets have size at most $s$".


How DMA improves I/O operation efficiency? I am reading Computer Architecture & Organization by William Stallings to understand I/O operations. Stallings pretty well explains why Programmed I/O (CPU keeps checking the I/O module register status) & Interrupt I/O (CPU still has to over look data transfer between I/O module & memory) are not efficient & introduces to DMA, where DMA itself handles everything.

But, however, he also mentions that during a DMA operation, CPU sits idle & has no control over memory bus. If CPU has to sit idle, then how it is better than other two methods ?

Page no. 415, Computer Architecture & Orgazination by Morris Mano:

  During the DMA transfer, the CPU is idle and has no control of the memory.

Only way it make sense to me is that, CPU can perform any operation which does not involve memory bus during a DMA operation. So, CPU will not be idle. Or am I missing something ?

I think author has formulated in a bad way. It can be phrased like:

  During DMA transfer, the CPU has no control of memory buses and thus cannot perform any operations involving memory. However it can perform other operations like arithmetic, logical or can operate on data in cache.

Am I right?

The DMA engine doesn't grab the bus for the duration of the whole transfer, only while specific data is being transferred. Yes, that means CPU acces to memory is hampered, but not shut off completely. The CPU can also work with data from its cache in the meantime.


Where can I find a study on the amount of different word frequencies in a corpus? I need to know how many different values the frequency of a certain word in a corpus can there be for a natural language processing problem. Is there any study or site that has such estimation?

What you're asking directly refers to Information Retrieval. Information Retrieval directly creates models for such things as frequency of words in a corpus and so on.

In a corpus, different indicators are estimated in order to create a score. Two indicators are predominant in those models :

Inverse document frequency (idf)

This model aims at attenuating words that appear too often and considered irrelevant to judge the score of a word.

$ idf_{t} = log\frac{N}{df_{t}}$ where $N$ stands for the total of document in a collection and $df_{t}$  the number of documents in a collector that contain the term $t$

Term frequency (tf)

This is the most basic way to modelize word frequency in a corpus. It can be computed by saying that:

$tf_{t,d} = \frac{t_{occ}}{N}$ where $t_{occ}$ is the occurence of the term divided by the number of words in the document.

More information on this subject can be found here :

Scoring, term weighting and the
vector space model


How to show composition of one way function is not such? I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?

Specifically: Say $f$ and $g$ are one-way functions (either weak or strong).
How do I prove that their composition $g(f(x))$ is not necessarily a one-way function?

You come up with an example: two functions $f,g$ which are one-way functions, but $f \circ g$ is not. To show that the latter is not a one-way function, you come up with an algorithm breaking it.

Here is an example. Choose some genuine one-way function $h$.  Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y = 0^{|x|}$ (we break the input in such a way that $|x|=|y|$). Note that the composition is just the zero function.


NFA that accepts all numbers not divisible by 105 I have to create an NFA that accepts the following language L with no more than 15 states.

$L = \{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \}$.

To me it seems that all multiples of 105 have the same properties:

sum of digits is divisible by 3
the last digit is 0 or 5

I would appreciate if someone could help me here.

Here is a hint.

$L$ is the union of the following three languages.

$L_3=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 3}\}$,
$L_5=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 5}\}$,
$L_7=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 7}\}$.

Construct the DFA for the above three languages. Then combine them together.

Exercise. (It may take some time to do this exercise.) Show that no NFA with less than 15 states accepts $L$ exactly.


What is the time complexity of this piece of code? def find_perms(s):
    """
    Finds permutations of the given string.
    >>> find_perms("abc")
    ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']
    """
    if len(s) == 1:
        return [s]
    elif len(s) == 2:
        return [s[0]+s[1], s[1]+s[0]]
    else:
        perm = find_perms(s[0:len(s)-1])
        last_char = s[len(s)-1]
        lst = []
        for strings in perm:
            for index in range(len(strings)+1):
                string = strings[:index] + last_char + strings[index:]
                lst.append(string)
        return lst

I am trying to figure out the time complexity of this piece of code as I'm working on studying coding questions and their time complexity and I managed to solve this permutation problem using recursion as was required but I am wondering how do I accurately determine the big-$O$ time complexity for this as it is a mix of recursion followed by an iterative loop. I would really appreciate some helpful input on this.

Let $f(n)$ be the answer for an input of size $n$.
then we have the following equation:

$f(n) = f(n - 1) + (n - 1)! * n = f(n - 1) + n!$

That's because you call the function for an input of size $n - 1$ which gives $f(n - 1)$, then you iterate over all permutations of size $n - 1$ which there are $(n -  1)!$ such permutations, and then you iterate over the position of the new element, which there are $n$ such positions. This gives us:

$f(n) = [\sum_{i=1}^n i!] < (n + 1)!$

You can easily prove this by induction.
So $f(n) = O((n + 1)!)$.


Complete Graph & Connected Component There seems to be various implementations of algorithms that find the connected components of a graph.

I have not found, however, an algorithm or implementation for finding which of the connected components are also complete. Does anybody know of one?

Thank you!

Most graph libraries will find the connected components of a graph G as a list of connected subgraphs [H1, H2, H3, ...] and most of these libraries will have the functionality to obtain the number of nodes and number of edges in a graph. Assuming H is a simple graph (no loops, no multiple edges) with m edges and n vertices, one can say it is complete if

m == n*(n-1)/2

So, given the output of connected components, you should do:

for each graph H in [H1, H2, ...]
  int n = H.getNumVertices()
  int m = H.getNumEdges()
  if (n*(n-1) == 2*m)
    state that H is complete
  else
    state that H is not complete


Are regular grammar languages defined from "accepting" states? In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular grammars too? They are defined by using 4 sets (terminal, non-terminal, initial non-terminal, rules) so there is no such thing as "accepting states" at the definition. The language of a regular grammar are the words that can be produced from that grammar, but do they always end in an "accepting" state?

There is a one-to-one correspondence between NFAs and right regular grammars without productions of the form $A \to a$.
Given a right regular grammar with productions of the form $A \to aB$ and $A \to \epsilon$ and starting symbol $S$, create an NFA in which:

The states are all nonterminals.
The initial state is $S$.
A state $A$ is final if there is a production $A \to \epsilon$.
There is an edge labeled $a$ from $A$ to $B$ if there is a production $A \to aB$.

This NFA accepts the same language as the grammar.
You can also easily carry out the transformation in the other direction.
This shows that in the absence of rule of the form $A \to a$, the analogs of accepting states are nonterminals with productions of the form $A \to \epsilon$.
We can replace a production $A \to a$ by a pair $A \to aX$, $X \to \epsilon$, where $X$ is a nonterminal which is common to all such productions, but doesn't appear anywhere else. We can think of $X$ as the accepting sink. A production $A \to a$ signifies a possible transition to the accepting sink.


Can FPSPACE give exponentially long outputs? I can't comment on this question, so I ask it here as a new question:

Ricky Demer states there in a comment to the first answer

"[...] since FPSPACE can give exponentially long outputs [...]"

How can this be? How can an algorithm in FSPACE give an exponentially long output? Does this mean, that we do not count the output space in the definition of FSPACE (contrary to what I have believed so far)?

Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only allowed to use a bounded amount of space.  This definition is necessary for something like LOGSPACE to make any sense: if you counted the output as part of the space used, then even an algorithm such as "just output the input" wouldn't run in LOGSPACE. That's important because we often want to use LOGSPACE reductions between problems.

A simple example of a (nontrivial) FPSPACE algorithm that produces exponentially much output is a SAT solver that just tries every possible combination of values for the variables and outputs the combinations that satisfy the formula.  This will produce exponentially long output for the class of inputs $X_1\lor\dots\lor X_n$.

Note that, for TIME-bounded complexity classes, we don't have this kind of problem since, on a Turing machine, writing $\ell$ symbols of output always takes at least $\ell$ time steps so, e.g., a polynomial time machine can only produce polynomially much output.


Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative? The following is an excerpt from CLRS:

The definition of $\Theta (g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$). Consequently, the function $g(n)$ itself must be asymptotically nonnegative, or else the set $g(n)$ is empty.

Intuition suggests that having one function with a positive domain while the other with a negative one perverts the purpose of asymptotic analysis (a measure of the order of growth) as the positive function can be an upper asymptotic bound of the negative function simply on merit of it being positive, even in cases where the negative function grows faster.
In cases where both functions have negative domains, asymptotic analysis would still be a valid measure of the order of growth, making the restriction of both functions having to be positive appear useless.

Mostly for convenience's sake.  Since big-theta notation specifically tends to be used mostly for algorithmics (as opposed to $O()$ and especially $o()$, which make occasional appearances in more 'traditional' mathematics for talking about goodness of estimates) and is generally used to measure 'usage' quantities of some sort (e.g. CPU cycles, memory, comparisons, etc) there's generally little lost by requiring the quantities involved to be non-negative, and it simplifies some of the definitions and results.

Note that unlike with $\Theta()$, the definitions of $O()$ and $o()$ are often phrased in terms of absolute value, making this point moot - can you see why that idea doesn't make sense for $\Theta()$?


Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book? As per this explaination, it defines applicative and normal order evaluation in one form saying:

  This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation.

while this explanation defines the other way around

  applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed

They seem to contradict each other. Do these definitions mean the same thing?

Those definitions are saying the same thing (at the level of precision of the English description).

An example from the book

Normal-order evaluation goes “fully expand and then reduce”, meaning that function calls are expanded before reducing the arguments, and the reduction only happens when the value is needed. Let's take one of the examples in the book: start from (sum-of-squares (+ 5 1) (* 5 2)). First, we fully expand the definition of sum-of-squares:

(sum-of-squares (+ 5 1) (* 5 2)) → (+ (square (+ 5 1)) (square (* 5 2)))

Since + is a primitive, we can't expand it. It requires integers as arguments, so here we have no choice: we must reduce the arguments. To reduce (square (+ 5 1)) in normal order, we start by expanding:

(square (+ 5 1)) → (* (+ 5 1) (+ 5 1))

Then we have the primitive *, also requiring integers as arguments, so we must reduce the arguments.

(+ 5 1) → 6
(+ 5 1) → 6

and so

(* (+ 5 1) (+ 5 1)) →→ (* 6 6) → 36

and likewise for (square (* 5 2)), so the original expression finally evaluates thus

(+ (square (+ 5 1)) (square (* 5 2))) →→ (+ 36 100) → 136

In contrast, applicative-order evaluates the arguments when the function is applied, before expanding the function call. So to evaluate (sum-of-squares (+ 5 1) (* 5 2)), we first need to evaluate the arguments:

(+ 5 1) → 6
(* 5 2) → 10

and then we can expand the function call:

(sum-of-squares (+ 5 1) (* 5 2)) →→ (sum-of-squares 6 10)
                                 → (+ (square 6 6) (square 10 10))

The next step is to evaluate the arguments of +; they're function calls, and in each case the arguments are already fully evaluated so we can perform the function call right away:

(square 6 6) → (* 6 6) → 36
(square 10 10) → (* 10 10) → 100

and finally

(+ (square 6 6) (square 10 10)) →→ (+ 36 100) → 136

An example with side effects

The order of evaluation doesn't make any difference when the expressions have no side effect. (Except with respect to termination, if you don't consider non-termination a side effect: an expression may terminate in some evaluation orders and loop forever in others.) Side effects change the deal. Let's define a function with a

(define (tracing x)
  (write x)
  x)

If we evaluate (square (tracing 2)) in applicative order then the argument is evaluated only once:

(tracing 2) → 2 [write 2]
(square (tracing 2)) → (square 2) [write 2]
                     → (* 2 2)
                     → 4

In normal order, the argument is evaluated twice, so the trace is shown twice.

(square (tracing 2)) → (* (tracing 2) (tracing 2))
(tracing 2) → 2 [write 2]
(tracing 2) → 2 [write 2]
(* (tracing 2) (tracing 2)) →→ (* 2 2) [write 2, write 2]

You can observe this in Scheme. Scheme applies applicative order to function evaluation, but also has a macro facility. Macro calls use normal order.

(define-syntax normal-order-square
  (syntax-rules () ((normal-order-square x) (* x x))))

At a Scheme prompt, you can see that (square (tracing 2)) prints 2 once whereas (normal-order-square (tracing 2)) prints 2 twice.

Towards theory

Let's present the rules of evaluation in a more formal way (with small-step semantics). I'm going to use a notation that's closer to what is commonly used in theory:

$(\lambda x y. A)$ is (lambda (x y) A), where $A$ is an expression.
$B[x\leftarrow A]$ means to take the expression $B$ and replace all occurrences of $x$ by $A$.
$[\![ \ldots ]\!]$ is an integer obtained by some mathematical computation, e.g. $[\![ 2+2 ]\!] = 4$.
$A \xrightarrow{\;t\;} B$ means that the expression $A$ evaluates to the expression $B$, and in doing so prints the trace $t$.

I'll simplify away everything that's related to variable binding: a variable is considered equivalent to its definition.

Evaluation rules come in two flavors. There are head rules, that explain how to make progress on the evaluation of an expression by looking at the topmost node in the syntax tree.

$$ \begin{align}
  ((\lambda x. B) \: A) &\longrightarrow B[x \leftarrow A] && (\beta) \\
  ((\lambda x_1 x_2. B) \: A_1 \: A_2) &\longrightarrow B[x_1 \leftarrow A_1, x_2 \leftarrow A_2] && (\beta_2) \\
  (* \: i \: j) &\longrightarrow [\![ i \times j ]\!] && (\delta_*) \\
  (\texttt{tracing} \: x) &\xrightarrow{\;x\;} x && (\delta_{\texttt{tracing}}) \\
\end{align} $$

$(\beta)$ is the rule the application of a user-defined function. I've defined a variant for two arguments (there are other, better ways to treat functions with multiple arguments but that's a topic for another day). The $(\delta)$ rules are for the evaluation of primitives (I'm treating tracing as a primitive because expressing it in terms of progn and write would unnecessarily complicate this presentation).

There are context rules, that explain how to look for things to evaluate deeper inside the evaluation syntax tree. The notation $\dfrac{P}{C}$ means “if there's a way to do the reduction $P$ according to the rules, then $C$ is also a valid reduction”. In other words, assuming that the premise above the line holds, the conclusion below the line holds.

$$
  \dfrac{A \xrightarrow{t} A'}{(F \, A \xrightarrow{t} F \, A')} (\texttt{App}^1_1)
  \qquad
  \dfrac{A_1 \xrightarrow{t} A_1'}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1' \, A_2)} (\texttt{App}^2_1)
  \qquad
  \dfrac{A_2 \xrightarrow{t} A'_2}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1 \, A_2')} (\texttt{App}^2_2)
$$

For example the rule $(\texttt{App}^1_1)$ means that to evaluate a function call, we can evaluate the argument. In a full treatment, there would be a similar rule for the function part, but we don't need it here.

The arrow $\longrightarrow$ means “evaluates in a single step to”. We can derive the notion of “evaluates to” (in any number of steps):
$$
  \dfrac{}{A \xrightarrow{} A}
  \qquad
  \dfrac{A \xrightarrow{\;t\;}^* B \text{ and } B \xrightarrow{\;t'\;} C}{A \xrightarrow{\;t,t'\;}^* C}
$$
The first rule means that an expression evaluates to itself (in zero steps). The second rule allows adding one more step to a sequence of evaluations.

These rules are non-deterministic: there can be more than one applicable rule for a given expression, and thus there are multiple possibilities to evaluate an expression. This is where evaluation strategies come into play. An evaluation strategy defines a priority on the rules.

In normal order, $(\beta)$ (the application rule) is applied before context rules that would affect the arguments. This is what the first quote means by “fully expand [apply head rules] and then reduce [in context]”, and what the second quote means by “delay the evaluation of procedure arguments until the actual argument values are needed” (don't apply context rules until forced by a $\delta$ rule). (In the first quote, the use of the word “expand” is somewhat jarring — applying $(\beta)$ is a reduction too!)
In applicative order, the context rules are applied first, and $(\beta)$ is only applied if the arguments can't be evaluated anymore. This is what the first quote means by “evaluate the arguments [in context] and then apply [head rules]”, and what the second quote means by “all the arguments (…) are evaluated when the procedure is applied [before performing the actual application]”.

Let's look at (square (tracing 2)) in this model. In the notation I've presented, that's $((\lambda x. (* \: x \: x)) (\texttt{tracing} \: 2))$. In normal order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))
  &\longrightarrow (* \: (\texttt{tracing} \: 2) \: (\texttt{tracing} \: 2)) && \text{by \((\beta)\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: (\texttt{tracing} \: 2)) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_1\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_2\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
In applicative order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x))\:  (\texttt{tracing} \: 2))
  &\xrightarrow{\;2\;} ((\lambda x. (* \: x \: x)) \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^1_1\)} \\
  &\longrightarrow (* \: 2 \: 2) && \text{by \((\beta)\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
(I used left-to-right evaluation for function arguments; specifying this is necessary to get a fully deterministic evaluation order.)
This shows how $((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))$ evaluates to $4$ with the trace $2,2$ under normal order, but to $4$ with the trace $2$ under applicative order.


Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$ $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$
I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard time in proving that $L$ is not a Context Free Language using Pumping Lemma.
Could please anybody please give me a hint?

Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for all $i \geq 0$. If $|vx| = \ell$ then $1 \leq \ell \leq p$, and for all $i \geq 0$, $q^2 + (i-1)\ell$ is composite. Since $\ell \leq p$ and $q$ is prime, $(q^2,\ell) = 1$, and so Dirichlet's theorem about primes in arithmetic progressions shows that for infinitely many $i \geq 0$, $q^2 + (i-1)\ell$ is prime. We have reached a contradiction.

An easier argument uses Parikh's theorem, which states that a unary language (a subset of $a^*$) is context-free iff it is regular. In particular, it is enough to show that $L$ isn't regular. Since the complement of a regular language is regular, it's enough to show that $\overline{L} = \{ a^k : k \text{ is prime}\}$ is not regular. It is easier to use the pumping lemma for this language. Given a pumping length $p$, choose a prime $q > p$. As before, there must exist $\ell \leq p$ so that $q + (i-1)p$ is prime for all $i \geq 0$. However, for $i = q+1$ we get $q + (i-1)p = q + qp = q(p+1)$, which isn't prime.


Ambiguous grammar? Could the grammar be parsed by SLR parser? I got one grammar:

re2: re1 $

re1: expr == expr | expr != expr | expr < expr | expr <= expr | expr >= expr | expr > expr | expr

expr: expr + term | expr - term | term

term: term * factor | term / factor | factor

factor: (expr) | num | id

num: (0|1|2|3|4|5|6|7|8|9)num | ε

id: (a|b|....|z|A|B|....|Z|)id | ε

Here are the FOLLOW sets:

FOLLOW(r2) = {}
FOLLOW(r1) = {$}
FOLLOW(expr) = {=,!,<,>,+,-,)}
FOLLOW(term) = FOLLOW(factor) = FOLLOW (id) = FOLLOW (num) = {=,!,<,>,+,-,),*,/}

Now this grammar clearly got reduce-reduce conflict from
num: ε and id: ε because FOLLOW(num) ∩ FOLLOW(id) != empty set

Now let's say I fix the grammar by  doing the following (I assume it is mistake in the grammar because (ε == ε) makes no sense):

num: (0|1|2|3|4|5|6|7|8|9)num | (0|1|2|3|4|5|6|7|8|9)
id: (a|b|....|z|A|B|....|Z|)id | (a|b|....|z|A|B|....|Z|)

Now my question is, is this grammar SLR i.e can it be parsed by SLR parser? I know by building the parser I can find out but on exam I can not make the whole parser and then determine (I would lose lot of time).

Your grammar indeed is ambiguous as it currently is, but not because the follow sets of two nonterminals have common elements. The ambiguity I see is that both re2 -> re1 -> expr -> term -> factor -> num -> ε and re2 -> re1 -> expr -> term -> factor -> id -> ε derive the empty word. If you require that num and id are both nonempty, then your grammar is SLR(1) (unless you do weird things to make num and id nonempty).

As an example where your 'follow test' does not work is the following:

S -> A c
S -> B c
A -> a
B -> b

The follow sets of A and B both contain c, but the grammar is SLR(1).

Unfortunately, the only three options I know to test whether a grammar is SLR(1) all have downsides: generating the table and doing the polynomial time test both take quite some time for an exam, and the third method, visual inspection of the grammar, is not very accurate. Finally, 'quickly' writing down the LR(0) automaton (by omitting the items in the states of the automaton) is possible but requires a lot of practice and is still somewhat inaccurate.


Framework or tools to generate theorem prover/solver/reasoner for new logic I have new logic which has syntax and semantics in usual natural languages and I have to create theorem prover/solver/reasoner for this logic. Is there framework or tool set that can generate such prover from the formal definition of grammar and semantics? I have heard about Isabelle/HOL, is this right set of tools. Is such generation a common path to proceed. Are the metalogical framework, prover compilers suitable for any kind of new logic?

Of course, I can create parser and encode all the algorithms by myself from scratch but this is not the common practice, I guess?

There are many related ways  you can mechanise your logic.

Deep embedding into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is (almost) always possible, but makes using the embedded logic awkward.
Shallow embedding into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is only possible when the embedded and embedding logics are sufficiently similar, but when it works it tends to work well.
Embedding into Isabelle. Note that Isabelle is a meta-tool for embedding logics, and Isabelle/HOL is but an implementation of HOL using the Isabelle tool. This is probably a lot of work, and moreover, most of the proof automation available for Isabelle/HOL is targetxing the logic HOL, so is unlikely to work for your specific logics.
Roll your own. It's quite easy to build a proof checker, should be just a few lines of code, especially if you take the LCF approach. More advanced tools are rather difficult, a modern SAT solver is probably > 10k LOC and that's for propositional logic, which is the simplest logic.
Logical frameworks. Some $\lambda$-calculi have been built particularly to enable the embedding of logics. Most well-known might be the Edinburgh Logical Framework and Pure Type Systems. Some mechanismation of those is available, but whether that is usable for you I don't know.


How is Rice's theorem applicable to this decision problem? I recently had a test in introduction to computability and I got the following question wrong.

The question

Input: A classical Turing machine $M$ with a 2-dimensional tape.

output: Does there exists a Turing machine $H$ that runs in polynomial time such that for any input $x$, if $M$ halts then $M(x)=H(x)$

Which of the following is correct?

(a) This decision problem is trivial.

(b) This decision problem is decidable, but not trivial.

(c) This problem is undecidable, according to Rice's theorem.

(d) This problem is undecidable, but Rice's theorem is not applicable.

My answer

I chose option (d) because the polynomial time requirement is not semantic, but the professor marked option (c) as the correct answer. Could anyone explain this?

Background

Rice's theorem and the terms "trivial" and "semantic" are explained here.

As you correctly mention, polynomial running time is not a semantic property.

However, the property required here is not polynomial running time (of $M$), but functional equivalence to a TM with polynomial running time (on those inputs where $M$ halts). It is of no importance, how long $M$ runs on those inputs. This is a semantic property, since every other TM $M'$, that computes the same function as $M$ will have the property as well: $M'$ halts on exactly the same inputs $x$ as $M$ and on these inputs $M'(x) = M(x) = H(x)$.


Maximum induced tree Given an undirected graph $G(V, E)$, how hard is it to decide whether it has an induced tree consisting of $k$ vertices, where $k$ is also given in the input?

This is $\mathrm{NP}$-complete. Reduce from Independent Set instance $(G, k)$. Add a new universal vertex $v$ to $G$. Connect $v$ with a very long path (only to $v$ not to any original vertex of $G$). And set $k' = k + 1 + \mathrm{length\:of\:the\:long\:path}$, where length of the long path is the number of vertices in it.

Clearly, if the induced tree does not touch $v$ then it either only stucks in the long path or being confined to $V$. So, in order to have $k'$ vertices, it must include $v$ and the long path. Since $v$ is connected to all $V$, the set of vertices in $V$ that are included the induced tree must form an independent set.


Peterson algorithm for mutual exclusion In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen atomically.

To me, this is not a superficial assumption , cause it's another mutual exclusion issue .
In which way we make the operations with the shared global variables happen atomically ?

The Peterson Algorithm uses only memory read and memory write operations, which are atomic in almost every computer ever built.  (All the bits in a word are read or written on the same cycle, and the memory bus of the computer is built in such a way that only one of the processors has access on any specific cycle.)
That said, the atomicity of the write operations is not necessary.  Leslie Lamport is quite clear about this in his commentary on his web page about his classic "Bakery Algorithm" for mutual exclusion (http://lamport.azurewebsites.net/pubs/pubs.html#bakery):

Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm".  I find that deplorable.  There's nothing wrong with publishing a simplified version, as long as it's called a simplified version.
What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion.  Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location.  So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion.  Such an algorithm cannot really be said to solve the mutual exclusion problem.  Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion.  Brinch Hansen said exactly this in a 1972 paper.  Many people apparently still believe it.

(emphasis added)
For more details about this aspect of the problem see Lamport's 1991 paper, "The Mutual Exclusion Problem Has Been Solved," http://lamport.azurewebsites.net/pubs/pubs.html#lamport-mutual-solved.


What would dynamically-typed languages actually do if type enforcement was removed? I program in Python, which is a well-known dynamically typed language. I understand dynamic typing to mean mainly that "operations" (in a loose sense) in the language are either allowed or denied (raise an exception) based on the type of their operands, and that this type-checking is deferred as long as possible. My question is this: if that is what a fair characterization of dynamic languages, what would happen if the run-time type checking was removed?

It seems to me that if you want to make a meaningful distinction between a dynamically typed language like Python and an untyped language, you would have to define what actually would happen in the untyped language in situations in which the type system of a dynamic language would take action. For example, in Python, if I attempt to subtract an Integer from a String, e.g., "spam" - 5, I receive a TypeError. If that's what makes Python dynamically typed, what would an "untyped Python" do in that situation?

A language in which automatic type checking is not available, an operation would make assumptions about the types of its operands. On the event that these assumptions are false, the operation, not knowing anything about this, may produce nonsense results.

Assembly is such language. It has, for instance, separate addition operations for integers and floats. If you perform integer addition on floating point values you will get a result which is correct as neither integer nor float. Depending on your definition of correct.


Algorithm for mapping objects of list without mapping to itself? I want to map objects of a list, to objects of that same list, randomly, without ever mapping any given object to itself.

So given a list of objects [a, b, c] valid maps would be, for example:

   a -> b,
   b -> c,
   c -> a

or

   a -> c,
   b -> a,
   c -> b

an invalid mapping would be:

   a -> a,
   b -> c,
   c -> b

I just cannot figure out how to implement such an algorithm.

(This is for a small Secret Santa app that I am building where each person will be assigned to buy gift to one of the other participants.)

If you want a cyclic permutation with no trivial cycles (i.e., the only cycle involves all elements) see Sattolo's algorithm.

If you only want to avoid trivial cycles (but you are fine with cycles of length at least $2$), the mathematical object is called a derangement.

See: https://math.stackexchange.com/questions/302057/generating-a-random-derangement

Since the probability  $p_n$ that a random permutation on $n$ elements is a derangement approaches $\frac{1}{e}$ as $n \to \infty$, you can easily get a randomized algorithm by simply generating a random permutations (e.g., using Fisher-Yates shuffle) until you find a derangement.

The above bound is asymptotic but this works even for small values of $n$.
This is because the number of derangements on $n \ge 2$ elements is $!n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$ (see,e.g., here).
Since $p_n = \frac{!n}{n!}$, we can explicitly compute $p_2 = \frac{1}{2}$, $p_3 = \frac{2}{6} = \frac{1}{3}$, and for $n \ge 4$ we have:

$$
p_n = \frac{!n}{n!} = \frac{\left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor}{n!}
> \frac{\frac{n!}{e} - \frac{1}{2}}{n!}
= \frac{1}{e} -\frac{1}{2 \cdot n!}
\ge \frac{1}{e} -\frac{1}{2 \cdot 24}
> \frac{1}{3}.
$$

This shows that, on average, you will not reject more than $2$ permutations. In general, the probability that you will look at more than $2t$ permutations will always be at most $(2/3)^{2t} \le 2^{-t}$.


Proof involving asymptotic complexity The question in Proof of big-o propositions asked to prove:

  $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$

The accepted answer starts the proof with:

  Suppose that $O(f(n))=O(g(n))$. It is easy to check that $g(n)=O(g(n))$ ...  and so $O(f(n))=O(g(n))$ implies that $g(n)=O(f(n))$.

I believe that there is a mistake in quoted part of the answer above.

It claims that $O(f(n))=O(g(n))\tag{1}$

and $g(n)=O(g(n))\tag{2}$

implies

$g(n)=O(f(n))\tag{3}$

Using the interpretation given in "Introduction to Algorithms (CLRS) Edition 3, page 50",  (1) is interpreted as $\forall\Phi(n)\in O(f(n)), \exists\Psi(n)\in O(g(n))$ such that $\Phi(n)=\Psi(n)$.

Additionally, the definition of $O$-notation given in "Introduction to Algorithms (CLRS) Edition 3, page 47" states:

  $O(g(n))=\{f(n):$ there exist positive constants $c$ and $n_0$ such that $0 \leq f(n)\leq c\cdot g(n)$ for all $n\geq n_0\}$

Considering the counter example whereby $f(n)=n$ and $g(n)=n^2$. Then $O(n)=O(n^2)$ and $n^2=O(n^2)$ hold, but $n^2\neq O(n)$, thereby contradicting the assertion given in the accepted answer. Note: "$\neq$" in this case refers to "$\not \in$".

Therefore, I would like to ask if the answer provided is wrong or my interpretation and/or reasoning is wrong.

The notations $a(n) = O(b(n))$ and $O(a(n)) = O(b(n))$ have different meanings:

$a(n) = O(b(n))$ means that $a(n)$ belongs to the collection of functions $O(b(n))$. That is, $a(n) \in O(b(n))$.
$O(a(n)) = O(b(n))$ means (in this particular case) that the two collections of functions $O(a(n))$ and $O(b(n))$ are the same. That is, $c(n) = O(a(n))$ iff $c(n) = O(b(n))$.  (Usually $O(a(n)) = O(b(n))$ actually means $O(a(n)) \subseteq O(b(n))$.)

Big O notation is thus ambiguous, but in practice there is usually no confusion.


How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network? Suppose we have a simple Bayesian network with two rows of nodes:  $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$.  Each node $x_k$ takes a state of either 0 or 1 with equal probability.  Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

Is exponential time required to compute the probability that all $y_k$ are 1?  Please provide a proof either way.

Exponential time is not required for finding the requested probability.  In fact, only linear time is needed, as we will see below.

First let's define some additional notation.  Let $X = (x_1, x_2, \ldots, x_n)$ and $Y = (y_1, y_2, \ldots, y_n)$ -- that is, two $n$-tuples of our variables.  Let $\mathbf{1}$ denote an $n$-tuple of 1s, $ (1, 1, \ldots, 1)$.  And let $S_n$ denote the set of all possible $n$-tuples of $0$ and $1$.  In CS literature, the elements of $S_n$ are sometimes called "strings".  If $\sigma$ is one such element, we write $\sigma(k)$ for its $k$th component.

In this new notation, the task is to compute $\Pr(Y = \mathbf{1})$.  We can marginalize out the configuration of 0s and 1s on $X$ as follows:
$$\Pr(Y = \mathbf{1}) = \sum_{\sigma \in S_n} \Pr(Y = \mathbf{1} | X = \sigma) \Pr (X = \sigma).$$

From the prompt we know that each $x_k$ is 0 or 1 with equal probability, so $\Pr (X = \sigma) = 2^{-n}$ for every $\sigma \in S_n$.  Additionally, for any given $\sigma \in S_n$, we know that $\Pr(Y = \mathbf{1} | X = \sigma) = \prod_{k=1}^n p_{k,\sigma(k)}$, since the probabilities $p_{k,\sigma(k)}$ are independent.  Combining these observations, we obtain
$$\Pr(Y = \mathbf{1}) = 2^{-n} \sum_{\sigma \in S_n}  \prod_{k=1}^n p_{k,\sigma(k)}.$$

Our next step is to show that we can factor the left-hand side of this equation as follows:
$$\sum_{\sigma \in S_n}  \prod_{k=1}^n p_{k,\sigma(k)} = \prod_{k=1}^n (p_{k,0}+p_{k,1}).$$
We prove this inductively.  When $n = 1$, both sides are $p_{1,0}+p_{1,1}$, so the base case holds.  For the inductive case, we assume the $(n-1)$th case and write the $n$th case as
$$(p_{n,0}+p_{n,1}) \sum_{\sigma \in S_{n-1}}  \prod_{k=1}^{n-1} p_{k,\sigma(k)} = (p_{n,0}+p_{n,1}) \prod_{k=1}^{n-1} (p_{k,0}+p_{k,1}).$$
Both sides simplify to those of the above identity, respectively, so the identity is proved.

This leaves us with the result that $\Pr(Y = \mathbf{1}) = 2^{-n} \prod_{k=1}^n (p_{k,0}+p_{k,1}).$  For a hash table representation, look-up times are $O(1)$ for each $p_{k,0}$ and $p_{k,1}$, so we can compute this product with a simple for-loop in a runtime of $O(n)$.


How to find the number of intervals containing a point when given a static set of intervals? I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.

I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where each interval has a starting point $b_i$ and an ending point $r_i$. Also, the set is not changing meaning no new intervals are inserted or removed, and no end/start points are identical.

I want to be able to return the number of intervals in $O(\log(n))$ time. I am aware of an interval tree however I actually don't have to worry about insertions and deletions so there might be something simpler.

Also, say I use an AVL tree where I use the start points as keys, and in each node I hold:

start - the start point of the interval
end - the end point of the interval
max - the max end point of an interval that is contained in the tree initiated at this node

And I search like so:

Given a point $p$, I start at the root and go down based on the max value compared to the point. If $p$ is greater than the max of the node, I'm currently at I consider it's right sub-tree. If $p$ is smaller than max, I consider the right sub-tree until I hit null or I find an interval that contains the point(based on start and end points).

This algorithm can return an interval that contains $p$ in $O(\log(n))$ time, but what if I wanna return the number of all intervals that contain it?

I understand it can be done in $O(\log(n)+k)$ time, where $k$ is the number of intervals containing the point but can't see really how.

It is a very strong assumption that the time it takes to preprocess is not a concern.

Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.

Sort all $b_i$ and $r_i$ into an increasing sequence $A=(a_1, \cdots, a_{2n})$.

Let $c_1=1$. For $i$ from 2 to $2n-1$, let
$$c_{i}=\begin{cases}
c_{i-1}+1&\text{ if } a_{i}\text{ is a starting point of a given interval,}\\
c_{i-1}-1&\text{ if } a_{i}\text{ is an ending point of a given interval.}
\end{cases}$$
$c_i$ is the number of the given intervals that contain the open interval $(a_i, a_{i+1})$ for $1\le i\le 2n-1$. Let $C$ be the sequence $(c_1, \cdots, c_{2n-1})$. The combination of $A$ and $C$ is what we wanted from preprocessing.

Given any number $p$, if $p \gt a_1$ and  $p\lt a_{2n}$, we can find the largest index $i$ such that $p\ge a_{i}$ by binary search in $O(\log n)$ time. Then the number of given intervals that contain $p$ is given by
$$\begin{cases}
0&\text{ if } p<a_1,\\
1&\text{ if } p= a_1,\\
c_{i}&\text{ if } a_i<p\lt a_{i+1}\text{ or } p=a_i\text{ and } c_i>c_{i-1},\\
c_{i}+1&\text{ if } p=a_i\text{ and } c_i<c_{i-1},\\
1&\text{ if } p=a_{2n},\\
0&\text{ if } p>a_{2n},\\
\end{cases}$$
In other words, we can get the answer in $O(\log n)$ time once $A$ and $C$ are known.


Possibility to prove that a function in big-theta is in big-O and little-o I understand that many similar questions of this sort have been asked, but in this case, the solution does not appear to be provable - or is it?

Question: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = O(h(n))$

Current solution:

$f(n) = \Theta (g(n))$ implies that $c_1 . g(n) \le f(n) \le c_2 . g(n)$ for $c_1, c_2 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $1$.

$g(n) = o(h(n))$ implies that $g(n) < c_3 . h(n) $ for $c_3 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $2$.

Multiply $2$ by $c_2$.

$c_2 . g(n) < c_2 . c_3 . h(n)$ Call this equation $3$.

From $1$ and $3$ it can be inferred that:

$f(n) \le c_2 . g(n) < c_2 . c_3 . h(n)$

Which means that $f(n) \not\le c_4 . h(n)$ (where $c_4 = c_2 . c_3$) and therefore $f(n) \not = O(h(n))$. Is this way of approaching the problem correct, or is it - as my intuition tells me - I've missed something entirely obvious?

Yes, it looks like that you missed something obvious.

A stronger claim: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = o(h(n))$.

Sketch of a proof: $f$ is bounded both above and below (up to a constant factor) by $g$ asymptotically, which is informally understood as $f$ and $g$ are the same asymptotically. $g$ is dominated by $h$ asymptotically. Hence $f$ is dominated by $h$ asymptotically.

(Sure, the above sketch is no more than rephrasing the claim in English. Well, that is how you (or at least I) would like to understand and reason about the situation)

Here is a detailed proof.

$f(n) = \Theta (g(n))$ implies that $c_1g(n) \le f(n) \le c_2 g(n)$ for some $c_1\gt0,\,c_2\gt0,\,k_1$ and any $n \gt k_1$.

$g(n) = o(h(n))$ implies that $|g(n)| < c_3 h(n) $ for some $c_3\gt0,\,k_2$ and any $n \gt k_2$.

Let $k_3=\max(k_1,k_2),\, c_4=\max(c_1,c_2)c_3\gt0$. Then for any $n\gt k_3$,
$$\begin{align}
|f(n)|&\le \max(|c_1g(n)|, |c_2g(n)|)\\
      &\lt\max(c_1c_3h(n),c_2c_3h(n))\\
      &=\max(c_1,c_2)c_3h(n)\\
      &=c_4h(n)
\end{align}$$
Note the first inequality above is guaranteed by the fact that $f(n)$ is bounded between $c_1g(n)$ and $c_2g(n)$ since $n>k_1$.

Finally, note that $f(n)=o(h(n))$ implies $f(n)=O(h(n))$.

P.S. There is some typo in your question. For example, "$c_1, c_2\in\mathbb{N}$" should be "some $c_1,\,c_2\in\Bbb{R}^+$" or "some $c_1>0,\,c_2>0$". If you let $f(n)=n, g(n)=2n$, then there is no natural number $c_1$ such that $c_1g(n)\le f(n)$ for even one positive $n$.


Roadmap to formal verification I would like to learn about different approaches to formal verification of software programs that goes beyond what Wikipedia has to offer. Ideally one would not only get an overview but also recommendations which books and articles to read next.

My goal is to be able to judge what parts of formal verification I could apply to my job as a software/network engineer. So if the overview had a practical slant it would be a plus. But I also don't mind theory at all since I have a rather solid background in pure maths.

My goal is to be able to judge what parts of formal verification I
  could apply to my job as a software/network engineer.

If you plan to use formal verification as black boxes, then I would suggest using some tools to have an idea how they work. Here are some open source tools:

Error Prone of Google
Nullaway of Uber
Facebook Infer
Ikos of NASA
Java PathFinder developed by NASA, now maintained by community.
Clang Static Analyzer of Apple
...

If you want to understand their basics, you can start with the book "Principal of Program Analysis". It covers many basic topics from Type Theory to Abstract Interpretation etc.

The book doesn't discuss anything deeply. For example, it doesn't discuss any abstract domains, the key part in abstract interpretation. Recent topics such as separation logic, which Facebook Infer is based on, are not covered either.

If you want to learn advanced topics, the only way is to read the proceedings of top conferences, e.g. POPL, PLDI, CAV, VMCAI, SAS, ICSE, FSE, ASE, ISSTA, etc etc.

A comment by @DmitriChubarov

  As I understand this is a question of why there is so little use of
  formal methods in the practice software development, ... or is there?

There are companies that are earning hundreds of millions a quarter by selling static analysis tools (I work for one of them), so I believe the number of companies that use formal verification is not little at all.


What is extra thread for idle time Here http://tomstechnicalblog.blogspot.com/2016/02/rxjava-understanding-observeon-and.html I've found a sentence which I do not understand:

  If you have a quad-core, you can optimally support 5 computational threads (4 cores + 1 extra thread for idle time).

What is that 1 extra thread for idle time for? Is it similar to those "normal" 4 cores?

What I think they mean is that while you only have 4 cores to do computation on sometimes they will halt, pause, or "idle". When they do that the OS will run another thread on that core. As such you should be able to have 1 more thread to fill in the periods where a core is not doing anything.


Genetic algorithm - fit max circles inside box - what chromossomes? I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y coordenates in order not for the to converge but to keep a distance.

Can someone please shed some light? Thank you

This is where I am getting at:

Now I am getting this:

But there is the last ball always overlaps. I think my problem is with the crossover.

So far and by gathering all the ideas here this is what I have reached:
Given a fixed number of circles (easier to explain) this is what I am doing.

Create a random set of circles for each individual in the population

Calculate the fitness of every individual base on the overlaping area are and area outside the box.
I then order the individuals by their fitness
Do a cross over. For that I am using a cumulative sum to choose randomly but with priorities which individuals are likely to go through to the next generation based on the fitness. The fittest have a higher probability of being chosen.
After choosing them indivudals I am aplying the crossover to I randomly choose the chromosse to which I do the single point cross over.
Then repeat for n generations

I am doing this but not getting to any convergion in terms of solution.

You can define chromosome as array - coordinates of the center of a circle - [(x1,y1), (x2, y2),..,(xn,yn)]
One required condition for every circle- no intersection between sides of rectangle and circle - the circle must be inside the rectangle.

Start from one circle (n=1) and create population with chromosomes of size 1 [(x1,y1)].

Your fitness function - number of intersections between circles - for n=1 fitness function always return 0.

You continue with 2 circles: and generate population of chromosomes [(x1,y1), (x2,y2)]. For every chromosome you calculate fitness - number of intersection between circles.

Crossover:

You can use different algorithm to generate new population:

1) Single point.

First point - from first chromosome, second point from second chromosome.

For example, two chromosomes with coordinates:

[(x11,y11), (x12, y12)]

[(x21,y21), (x22, y22)]

Crossover - two chromosomes:

[(x21,y21),(x12,y12)],

[(x11,y11),(x22,y22)]

For n>2:

[(x11,y11),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x21,y21),(x22,y22), (x23,y23),..,(x2n,y2n)]

Crossover:

[(x21,y21),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x11,y11),(x22,y22), (x23,y23),..,(x2n,y2n)]

etc.

See https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) about crossover algorithms.

Mutation:

For every chromosome from population choose randomly some circle and change coordinates.

New population:

select chromosomes with minimal fitness value.

If you found out chromosome with fitness value is 0 - increment n (number of circles) and repeat this procedure: create population with chromosomes with size n, etc.


What, if any, is the term for a node whose children are all leaf nodes? More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.

They are classified as nodes of height 1 by convention in the case of a rooted tree.

The height of a node $N$ is the number of edges on the longest downward simple path from $N$ to a leaf, according to Introduction to Algorithms by CLRS as well as the Wikipedia entry.

You might want to use penultimate nodes as suggested by Orlp. Please note some papers define a penultimate node slight differently on general graphs as a nonleaf node that is adjacent to a leaf node. For example, Patrolling Games.


In a $k$-way set associative cache,main memory block mapping in range? In a $k$-way set associative cache, the cache is divided into $v$ sets, each of which consists of $k$ lines. The lines of a set are placed in sequence one after another. The lines in set $s$ are sequenced before the lines in set $(s+1)$. The main memory blocks are numbered 0 onwards. The main memory block numbered $j$ must be mapped to any one of the cache lines from:

$(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
$(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
$(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
$(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

My attempt:
Somewhere it explained as : Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1).
(Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

Can you explain it in a formal way, please?

Number of sets in cache = v. So, main memory block j will be mapped to
  set (j mod v), which will be any one of the cache lines from (j mod v)
  * k to (j mod v) * k + (k-1). (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence
  reduces the chances of replacement.)

This is a simple concept of k-way set associate mapping.

To understand it better I would like to take an example:

Example:

2-way set associative
4 blocks
Lines of a set are placed in sequence one after another (as in the
question)
The main memory blocks are numbered 0 onwards (as in the
question)

Empty 2-way set associative Cache Memory :

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   -   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Memory reference (data asked for processing) in the order:

4, 5, 9, 7

Reference 4:

4 % 4 = 0 (goes to Block 0 Set 1) Cache miss as it doesn't already present in the cache

As it had 4 blocks, we mod it the reference address to know which location of cache should I put it.

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 5:

4 % 5 = 1 (goes to Block 1 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 9:

4 % 9 = 1 (goes to Block 1 Set 2) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 4:

4 % 7 = 3 (goes to Block 3 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   7   │   -   ║
╚═══╧═══════╧═══════╝

Visualization of Cache memory for you undersatnding:

╔═════════════════════════════════════════════════════╗
║                    Cache Memory                     ║
╠════════════════╤════════════╤═══════════════════════╣
║ Memory address │ References │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       0        │     4      │                       ║
╟────────────────┼────────────┤ Cache line 0 elements ║
║       1        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       2        │     5      │                       ║
╟────────────────┼────────────┤ Cache line 1 elements ║
║       3        │     9      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       4        │     -      │                       ║
╟────────────────┼────────────┤ Cache line 2 elements ║
║       5        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       6        │     7      │                       ║
╟────────────────┼────────────┤ Cache line 3 elements ║
║       7        │     -      │                       ║
╚════════════════╧════════════╧═══════════════════════╝

Both of the two set of cache line 1 is full, therefore calculation the location of first and last element of line gives us the answer.

Lets now check if the answer is option (1) as you mentioned

  (j mod v) ∗ k  to  (j mod v) ∗ k + (k − 1)

Given:

v = 4 (four blocks)

k = 2 (two-way)

First element of cache line 1 = (j mod v) ∗ k = (5 mod 4) ∗ 2 = 2 yes, its located at memory location 2.

Last element of cache line 1 = (j mod v) ∗ k + (k − 1) = (9 mod 4) ∗ 2 + (2 - 1) = 3 yes, its located at memory location 3.

Done.

Answer: (j mod v) ∗ k to (j mod v) ∗ k + (k − 1)


Single-source shortest paths with even weight I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even.
In another words, we have to find the shortest way with the minimum even weight.

I'd like to have some ideas how we solve this.

Thanks.

Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works.  As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far).

Modify it so there are three types of vertex: ones for which you've figured out the shortest even-length path, ones for which you've figured out the shortest path but it was odd, and ones for which you only have an upper bound for the shortest path and shortest even path.


Counting frequencies of Element in an array Given an array of size $N$. I need to find the count of values in range $[L, R]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).

For eg-
\begin{align*}
    A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\
    L&=0,\ R=3\,,
\end{align*}
the answer would be 1 (1,1,1) and 2 (2,2,2).

I tried it by doing the following:

  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.

How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?

Update :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.

add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR <= R:
    add(currentR)
    currentR++
  while currentR >R+1 :
    remove(currentR)
    currentR--
  output answer

I need to calculate for many pairs of L,R .So I need an efficient algorithm.
The above algorithm seems to do so.

But How do I differentiate the contiguous triplets here ?

Maybe this:

answer = 0
lastVal = -1    //some value not inside [L,R]
count = 0
for i in {l..r}:
  if (array[i] != lastVal)
     count = 1
     lastVal = array[i]
  else
     count++
     if (count == 3)
        count = 0
        answer++

Edit: This code assumes that the set (1,1,1,1) is counted as one triplet not two.
i.e.: (1,1,1) and (1), not (1,1,1) and (1,1,1)


How to prove that language is decidable? Prove or disprove:
The following language $L$ is decidable:

$\{ \langle M, x\rangle: M \text{ is a Turing machine and } M(x) \text{ halts in less than } |x|^2 \text{ steps} \}$

So for proving I need to construct a TM $U$ if it accepts $L$, so $L$ is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, x\rangle$:

$i:=1$;

$n := |x|^2$
Simulate one step of $M$ on $w$.
If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ n$ then $U$ rejects.
Else $i:=i+1$; goto step 2."

Because $U$ is a decider machine, $L$ is a decidable language.

Is this solution correct? Or I should do it in another way?

If you want to prove that a language is decidable, it is sufficient to construct a Turing Machine that accepts if the input is in the language. It MUST reject if the input is not in the language.

Additionally, you are required to argue/prove that the Turing Machine constructed does that. Here's a hint: M must just halt on x, for it to be in L. Consider all possibilities of halting.


Is there a DFA with $k+2$ states which its reverse has $2^k$ states I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.
I am trying to find an example of such a DFA, any help?

This is related to the usual NFA to DFA complexity problem. Strings over $\{a,b\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|>1$.


Kleene's Theorem and TMs I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this implication valid or are we not entirely sure about this? (ambiguous/unclear given the theorem). Kind of like the Church-Turing thesis about computation in the future and all computation in general.

We can prove the following theorem:
Theorem: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$.
Turing machines are more powerful than DFAs and NFAs. In particular,  every finite state automaton can be simulated by some Turing machine.
So, according to the above propositions, the answer to your question is yes: every regex has a Turing machine whose language is identical.