Polynomial-time algorithm with exponential space is eligible? I'm curious about two things.

When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For example, when algorithm is considered to be given a input from domain $\{0,1\}^n$,
what if the algorithm internally queries its exponential sized table (ex. $0^n\to0,0^{n-1}1\to1$ and so on..) and outputs the result? Does it still polynomial-time algorithm?
In theoretical cryptography, one-way function $f:\{0,1\}^*\to\{0,1\}^*$ has a requirement, which is related with hard-to-invert property, as following block.
If the answer to above question is yes, is it possible to construct algorithm $A'$ to simulate exactly same as $f$ for every value in $\{0,1\}^n$ using exponential table as described in above question? If then, it implies that it's impossible to design one-way function which is definitely not true. So what have i missed?

  For every probabilistic polynomial-time algorithm $A'$, every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,

  $Pr[A'(f(U_n),1^n)\in f^{-1}(f(U_n))]<\frac{1}{p(n)}$

  where $U_n$ is random variable uniformly distributed over $\{0,1\}^n$

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential size table takes exponential time.

On the other hand, your program could use a (supposedly) exponential amount of uninitialized space. Since its running time is polynomial, it only accesses polynomially many cells. You can implement memory access in such a way that if $T$ cells are ever accessed then $\tilde{O}(T)$ memory is used (exercise). The corresponding running time might become much worse, but still polynomial.

A third possibility are non-uniform computation models, which are popular in cryptography. Here the idea is that the algorithm is allowed to use a certain hard-coded amount of data which depends only on $n$. However, this data has to be polynomial size. This restriction comes from the interpretation of the model in terms of circuits. A machine running in polynomial time corresponds to circuits for every $n$ of polynomial size. If we now relax the constraint that all these circuits come from some single algorithm, then we get non-uniform polynomial time, which is the same computation with advice depending on $n$ of polynomial size (exercise).

The answer to the first question should obviate the second one. I would just mention that sometimes, instead of probabilistic polynomial-time algorithms, one considers (deterministic) polynomial size circuits.


How to eliminate for/if/while from algorithms when it's possible Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive functions, there must be a way to convert the program into ones that do not have for/if/while and so on (which is elementary recursive).

For/if/while are the main blocks that will check for a condition. Since a recursive function will keep recurring until a condition is met, you will at least need an if statement to tell the function when to return. Otherwise, you will essentially be stuck in an infinite loop.


Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make? I'd like your help with the following question:

Assume we proved that $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can you make?

BPP  is  the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances,

$\Pi_2$ is the class of all languages $L$ such that there's a polynomial algorithm $M$ and a polynom $p$ so that $\forall x.x\in L\Leftrightarrow \forall u\in \{ 0,1 \}^*.\exists v \in \{ 0,1 \}^*.M(x,u,v)=1$.

We already know that   $\mbox{BPP}\subseteq \Sigma_2$, so $\mbox{BPP}\subseteq \Pi_2\cap \Sigma_2$.

It is known.  As your final statement says, $\mbox{BPP} \subseteq \Pi_2 \cap \Sigma_2$.  It is called the Sipser–Gács–Lautemann theorem.  (All though your "so" is somewhat misleading.)

It can be strengthened to $\mbox{BPP} \subseteq \mbox{MA} \subseteq \mbox{S}^P_2 \subseteq \Pi_2 \cap \Sigma_2 \subseteq \Pi_2$ (see also Arthur-Merlin protocol).


What's the language of the NFA? Given is the NFA N:

What's the language of this NFA? What's its complement?

I'm learning for a test and I'd like to know if I solved this task correctly.

The language L of the NFA N should look like this:

L(N) = {x ∈ Σ* | x mustn't include 'aba' and x mustn't end with 'ab'}

I have tried several different words and I couldn't find any word that breaks my language L(N).

Assuming this is correct, how would the complement of L(N) look like?

It needs to be the opposite, right? So something like that (~ stands for complement):

~L(N) = {x ∈ Σ* | x must include 'aba' and x must end with 'ab'}

I tried expanding my comment to a proper answer. It was easier for me to write down the automata and the whole transformation process rather than using some software to generate it, thus I hope my handwriting is legible enough ;) (elsewise let me know)

The resulting Regular Expression is $[[b^*ba^*b]^*\cup[b^*aa^*ab^*b]^*]^*$

So the language accepted by your NFA ought to be something of the form $L = \{((b^lba^hb)^*(b^iba^jab^kb)^*)^*|i,j,k,l,h\ge 0\}^*$ (I've given a quasi-final form of the language).

The opposite of this language is $\sim L = \mathtt{REG} - L$

PS: Fortunately, a kind sir named Hendrik Jan observed that my conversion omits the fact that 2 is also a starting point. The solution is still holds for starting point 1. Now that you got an idea about NFA to REG conversions, I'll leave the REG determined by starting point 2 to you. :)


Name for this algorithm? I'm trying to figure out if there is a proper or commonly accepted name for this particular function (f).

float clamp(float min, float max, float v)
{
    if (v < min) return min;
    else if (v > max) return max;
    else return v;
}

float f(float min, float max, float v)
{
    float t = (v - min) / (max - min);

    return clamp(0.0, 1.0, t);
}

This is sometimes called "0-1 normalization" or "feature scaling".

http://en.wikipedia.org/wiki/Feature_scaling

http://en.wikipedia.org/wiki/Normalization_(statistics)

The entire function f() is a Piecewise function, which consists of 3 domains, defined separately for

v <= min
v is between min and max, and
v >= max.

The primary function is the normalization function when v is between min and max.  The other two functions just limit the range or codomain of the function.

Piecewise functions are used often in mathematics to make the whole function continuous over a larger domain or to handle special cases like divide by zero, which the original poster might want to handle when min == max.

And what does the function do?
Creates a function f(x) where f(min) returns 0.0, f(max) returns 1.0, and f(v) rescales the input v from 0.0 to 1.0 linearly. Anything less than min maps to 0.0; anything more than max maps to 1.0.

One application of this is to calculate the percentile of a data samples (but from 0.0 to 1.0 vice 0 to 100).


Why is the Nintendo Entertainment System (NES) referred to as an 8-bit system, rather than a 1-byte system? As far as I've understood it, referring to this system as an 8-bit system points out that one can access 8 bits of data in one instruction.

While I understand that we're not saving vast amounts of time by calling it "one byte" instead of "eight bits", is there a particular reason why the latter is/was preferred?

"Back in the day" computers were defined more by their word size, for example the PDP-8 had 12-bit words composed of two 6-bit "bytes". A "nibble" was half a byte, or 3 bits in this case (and here the op codes were 3 bits).

It is only in recent decades that 8-bit bytes became so prevalent as to make them the default.

Calling the NES 8-bit is less ambiguous than calling it 1 byte, keeping in mind we're talking about a system that came out in 1983.


Is type-checking "syntactic" or "semantic"? On the wikipedia page on compilers, it says:

  Semantic analysis adds semantic information to the parse tree and builds the symbol table. This phase performs semantic checks such as type checking (checking for type errors), or object binding (associating variable and function references with their definitions), or definite assignment (requiring all local variables to be initialized before use), rejecting incorrect programs or issuing warnings. Semantic analysis usually requires a complete parse tree, meaning that this phase logically follows the parsing phase, and logically precedes the code generation phase, though it is often possible to fold multiple phases into one pass over the code in a compiler implementation.

I was somewhat surprised that type checking is categorized as semantics rather than syntax. Usually my impression is that types are called syntactic objects. Is type checking syntactic or semantic?

Although I personally would describe type analysis as semantic, this question seems to start with the assumption that there is a clear, formally-definable dividing line between "syntax" and "semantics".

I don't think that is the case; even if most of us would put type-correctness  into one category and missing parentheses into the other one, there is a fuzzy area in the middle where the answer is much less clear.

Consider, for example, the common case of a language which requires identifiers to be declared in the scope in which they are used. Clearly, then, the following is an error: (leaving aside the precise syntax of the language)

function ilog2(a:int) => int
  if a > 0 then
    let log:int = 0
    while a > 1
      a = a / 2
      log = log + 1
    end
  end
  return log
end

Many people would argue that the use of log in the return statement is a semantic error, since it has to do with the set of definitions in the outer scope of the function. On the other hand, it is quite feasible to construct a grammar (not a context-free grammar, but a grammar nonetheless) which rejects this program. It's not a coincidence that this scoping rule is called "lexical scoping" rather than, for example, nested semantic scoping.

A context-sensitive grammar can accomplish that in a straight-forward fashion by scanning backwards (and forwards, if declarations are allowed to follow use) skipping over inner scopes until it finds a declaration for the used identifier. Of course, that's not a very efficient algorithm but it's reasonable to assume that there are more efficient ways to implement such a grammar.

Even more generally, in the lengthy discussions which lead to the formalism of Algol 68, Adriaan van Wijngaarden proposed a syntactic formalism (link taken from this Wikipedia article) powerful enough to not just encompass declarations, but also to encompass static type checking. Although not everyone will agree with the judgement, van Wijngaarden's proposal was considered readable enough that it was eventually used in the formal definition of Algol 68. In that definition, type agreement (other than discriminated unions) is guaranteed by the grammar, while semantics is reserved for questions like the precise meaning of the + operator.

In retrospect, Van Wijngaarden's formalism turned out to be far too powerful to allow for automated parser generation, but it did spawn a number of simplified and less powerful formalisms, collectively called "attribute grammars", which have the potential to expand the formal power of syntactic descriptions while remaining practical tools for compiler writers. (There are few practical demonstrations, but there is still hope. :-) )

In short, if you consider "syntax" to be intimately linked to a particular syntax formalism (and hence to a particular parsing algorithm), then you will probably be able to make a clear distinction between syntax and semantics, but it might turn out to be a different distinction made by someone using a different parsing algorithm. So it's hard to see how write universal and non-overlapping definitions of syntax and semantics.


Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (extracted from the final residual network) can also be used to determine the minimum vertex cover:

$$(X\cap T)\cup(Y\cap S)$$

If this expression is a correct alternative, I don't have an intuition for why it's true. The best intuition I've been able to come up with is: Select each vertex on the left (X) that has a positive flow leading up to it and select each vertex on the right if there is no flow leading up to it. Why is this set equal to the minimum vertex cover?

The set $(X \cap T) \cup (Y \cap S)$ is the same as the one given by the alternating path algorithm. Let $L_0,L_1,\ldots$ be the subsets considered in the alternating path algorithm (in the Wikipedia page they are called $S_0,S_1,\ldots$, but that will be confusing), and let $X_i = L_i \cap X$, $Y_i = L_i \cap Y$.

A vertex $x \in X_0$ is unmatched and so the edge from $s$ to $x$ is in the residual network, showing that $x \in S$. In other words, $X_0 \subseteq S$. Analogously, $Y_0 \subseteq T$.
A vertex $x \in X_1$ is connected to some $y \in Y_0$ via some edge not in the matching. Since $(x,y)$ is not in the matching, it belongs to the residual network. Since $y \in T$, also $x \in T$. In other words, $X_1 \subseteq T$. Analogously, $Y_1 \subseteq S$.
A vertex $x \in X_2$ is connected to some $y \in Y_1$ via some edge not in the matching. As before, $(x,y)$ belongs to the residual network, and so $y \in S$ implies $x \in S$. In other words, $X_2 \subseteq S$ and $Y_2 \subseteq T$.

Continuing this way, we conclude that
$$
\begin{align*}
S \cap X &= X_0 \cup X_2 \cup \cdots, & T \cap X &= X_1 \cup X_3 \cup \cdots, \\
S \cap Y &= Y_1 \cup Y_3 \cup \cdots, & T \cap Y &= Y_0 \cup Y_2 \cup \cdots. \\
\end{align*}
$$
Therefore
$$
(X \cap T) \cup (Y \cap S) = X_1 \cup X_3 \cup \cdots \cup Y_1 \cup Y_3 \cup \cdots = L_1 \cup L_3 \cup \cdots,
$$
which is the output of the alternating path algorithm.


Calculate the Time complexity $T(n)=\sqrt{2T(n-1)}$
what will be the time complexity if $T(n)$ is given as this?
I tried substitution but no result was reached.

The answer depends on the initial value. For example, if $T(0) = 2$ then you can prove by induction that $T(n) = 2$ for all $n$. More generally, let $S(n) = T(n)/2$. Then
$$
S(n) = \frac{T(n)}{2} = \frac{\sqrt{2T(n-1)}}{2} = \sqrt{\frac{T(n-1)}{2}} = \sqrt{S(n-1)}.
$$
Simple induction now shows that $S(n) = \sqrt[2^n]{S(0)}$, and so
$$ T(n) = 2 \sqrt[2^n]{\frac{T(0)}{2}}. $$
In particular, this shows that $T(n) \to 2$.

We can estimate the speed of convergence using the estimate
$$
\sqrt[2^n]{x} = \exp \frac{\log x}{2^n} = 1 + O\left(\frac{\log x}{2^n}\right).
$$
This shows that
$$ T(n) = 2 + O(2^{-n}). $$


How broken is LCG in the case of partial output? Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can only see the $k$ high-order bits of each of the $X_i$ for $i \geq 0$, the best algorithm I know of is a brute force which tries $O(2^{n-2k})$ possibilities, and this is exponential in $n$.

Compare this to the Mersenne Twister, whose initial state can be computed in polynomial time given only the high-order bits of each output (it reduces to solving a system of $n$ equations in $n$ unknowns). Is there a better algorithm out there which can solve for the initial state of an LCG given only the high-order bits of each output, and if not, is LCG actually broken?

Yes, there are techniques based on lattice reduction that are faster than brute force.  See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to $O(2^{(n - k)/2})$ if $k \ge n/2$: see https://crypto.stackexchange.com/a/10609/351.


Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied? Overview and Problem Description
Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in a particular time interval that would yield the highest profit at the end of the interval (assuming there is a transaction cost T associated with selling your holdings in a given time series). Problem Inputs include (i) transaction cost (volume-independent fixed cost) , (ii) price tables of alternatives (indexed by time step), and the (iii) time interval in question. Problem Output is a sequence of tuples (timestep, decision type) that maximizes returns at the end of the interval. Valid decisions include buying and selling ones funds from one alternative to another at discrete time steps.
Trivial Example
You have USD 1 in year 1 [Problem Input]. Given Stocks A and B prices in years 1, 2, and 3, determine the sequence of actions that will maximize your profit at the end of the interval [1, 3]. The transaction cost, independently of volume, is USD1 [Problem Input]. You can sell and buy into any time series by paying the transaction cost for the trade at any discrete time step.
Stock A [Problem Input]:
Year 1: USD 1
Year 2: USD 1.1
Year 3: USD 1.2
Stock B [Problem Input]:
Year 1: USD 1
Year 2: USD 1.2
Year 3: USD 0.9
Answer [Problem Output]: Buy Stock A in year 1.
Buying Stock B for the first year would result in a higher return from the stock itself. However, given the USD 1 transaction cost, it's better to hold Stock A.
Question
I have a feeling this problem is well-studied. I can see how it would have a lot of applications, even though one usually does not have perfect information.
If I'm correct about my hunch, what is this problem called?
Of course you could just formulate this as an integer program, but I'm looking for a solution approach that's less 'naive' (if that even exists).

This can be solved using dynamic programming.  Note that the optimal solution never requires holding more than one type of stock at a time; if you sell a stock, then you might as well sell all of it, and before buying a stock you should sell all existing stock.  This enables a nice solution using dynamic programming.

Here are the details.  Let $A[i,s]$ denote the maximum value of your assets that can be achieved by the end of year $i$, denominated in dollars, if you are holding stock $s$ at the end of year.  Then there is a simple recursive expression for $A[i,s]$ in terms of the values of the form $A[i-1,t]$, based on the idea that either you sell or buy at the start of year $i$:

$$\begin{align*}
A[i,s] = \max(&A[i-1,s] V[i,s]/V[i-1,s],\\
            &\max \{(A[i-1,t]/V[i-1,t] - C) V[i,s] : t \ne s\}),
\end{align*}$$

where $V[i,s]$ denotes the price/value of stock $s$ at the end of year $i$ and $C$ denotes the fixed transaction cost.  Now you can compute these values iteratively, by first computing $A[1,\cdot]$, then $A[2,\cdot]$, and so on.  You can also keep track of which choice was optimal at each step and thereby reconstruct the sequence of transactions as well if you like.


Finding a minimum equivalent graph of a digraph It is said that this problem is NP-complete but I couldn't find the proof.
Is there any paper on this problem or not?

This problem (or more precisely, its decision version) lies in NP, as a small enough equivalent digraph would give an NP-certificate.
What remains is to show that this problem is NP-hard.

This paper shows that finding a minimum equivalent digraph is NP-hard even when restricted to digraphs with cycles of length at most $5$, via a reduction from SAT. This means that the problem in general is NP-hard and therefore also NP-complete.


Which is the correct XOR Gate Symbol I'm confused between 2 XOR gate symbols, they have a minor difference but I'd still like to know if they truly are identical.

One looks like -

The other, like

Notice, how for one of them the input lines are connected all the way and for the other, it's not. Are they both identical, as I suspect or is there something I'm not aware about?

There is a standard for this, ANSI/IEEE Std 91a-1991. The second version is what that standard gives for the "distinctive shape symbol" (5.1-11). So if you want to know what one is "correct", it's arguably that.

The other version is not the standard, but it's extremely common and everyone knows what you mean by it. But it's not distinct.


Finding a series of numbers that maximise $\ \sum f_i(x_i) $ Let $\ f_1, f_2, ... f_m : \{0, ..., m \} \rightarrow \mathbb Z $
my task is to find an algorithm that find a series of numbers $\ x_1, x_2, ..., x_m \in \{ 0, ..., m \} $ that maximise $\ \sum_{i=1}^m f_i(x_i) $ and subjects to $\ \sum_i^m x_i \le m $
To be honest I can't really wrap my head around this problem. Any suggestions on ways to look at this problem differently?

Following is a trivial Dynamic Programming algorithm for your problem:
Let $T$ denote a table of size $(m+1)$ x $(m+1)$.
Here, $T[i][j]$ stores the maximum value of $\sum_{t = 1}^{i}f_{t}(x_{t})$ such that $\sum_{t = 1}^{i}x_{t} \leq j$.
Induction Case: Since there are $m+1$ possible choices for $x_{i}$, check each one of them.
$$T[i][j] = \max_{p \in \{0,\dotsc,m\} \textrm{ and } p \leq j} \Big\{T[i-1][j-p] + f_{i}(p)\Big\}$$
Base Case: For $i = 0$ means there is no function. Therefore, the value is $0$.
$$T[0][j] = 0 \quad \forall j \in \{0,\dotsc,m\}$$
Output: The algorithm will output $T[m][m]$ which is simply the maximum value of $\sum_{t = 1}^{m}f_{t}(x_{t})$ such that $\sum_{t =1}^{m} x_{t} \leq m$
Running Time Analysis: Since the size of the table is $O(m^{2})$ and computing each entry takes $O(m)$ time. The overall running time is $O(m^{3})$.


Why is the set of NFA that accept all words in co-NPSPACE? In Sipser's book there is a section describing how to decide

$\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$

in polynomial space. To do so, it shows $\overline{\mathrm{ALL}_\mathrm{NFA} }$ is in NPSPACE.

I don't understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that is rejected, some states would repeat. But why? Is there any alternative explanation that helps in understanding this part?

Your question is really about the following statement: If an NFA with $n$ states does not accept every string, then it rejects some string of length at most $2^n$.  (The rest of the proof comes from the fact that REACH is in NL.)

To see why this is so, first let's look at a DFA with $k$ states that does not accept every string.  The transition function of the DFA corresponds to a directed graph $G$ on $k$ vertices. DFA computations bijectively correspond to walks in $G$ starting from the vertex $s$ representing the start state.

Since the DFA does not accept every string, there is a vertex representing a non-accepting state $j$ reachable by a walk from $s$.  In particular, there is a simple path $P$ from $s$ to $j$, which can have length at most $k$ (e.g., DFS will produce one).  $P$ corresponds to a string of length at most $k$ that is not accepted.

The NFA question reduces to the DFA one.  Using the powerset construction, convert the NFA with $n$ states to a DFA with $k = 2^n$ states and then use the above argument.


Algorithm to find Dominance Frontiers The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9).  We start with the immediate dominators of each control-flow graph node B already calculated and stored in idom[B]:

for each B in all basic blocks
    if size of Predecessors(B) >= 2
        for each P in Predecessors(B)
            runner = P
            while runner != idom[B]    # idom is the immediate dominator
                DF(runner) += B
                runner = idom[runner]

My question is about the Predecessors set. Do they refer to the direct predecessors ("fathers") of B or to all of them that lead to B?

Predecessors(B) is just the set of direct predecessors of B.  The "fathers", not the more distant ancestors.

Dominance frontier nodes must be join points in the graph, and a node can only be a join point if it has more than one predecessor.


CFG where u has same number of 1s as v $$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$

Here is my attempt solution, but it is not completely correct, any hint is appreciated
(not sure how I can ensure that $u$ and $v$ to have the same number of 1).

\begin{align}
S &\rightarrow S_l \mid S \mid S_r\\
S_l &\rightarrow 0S_l \mid 1S_l \mid S_l0 \mid S_l1 \mid \varepsilon \\
S_r &\rightarrow 1S_r \mid 2S_r \mid S_r1 \mid S_r2 \mid \varepsilon
\end{align}

The idea is to extract a pair of 1s one by one, so the key grammar is

\begin{align}
S&\rightarrow S_01S1S_2 \\
S&\rightarrow S_0S_2
\end{align}

where $S_0$ represents $0^*$ and $S_2$ represents $2^*$.


how to represent Sparse Matrices I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.

Could you please suggest me some other way to store/represent sparse matrices?

As already indicated in the comments, the wikipedia article about Sparse matrix, Band matrix, and Skyline matrix cover the topic of the question quite well. Also, the computational science stackexchange site might be a better fit for such questions in general.

One might perhaps add that band matrices can't handle low rank modifications directly, so that one might want to use the Sherman–Morrison–Woodbury formula in this case. For the other representations, it is normally more beneficial to incorporate low rank modifications directly into the matrix via additional rows and columns, see below.

Some information about representations of Sparse matrices

A general Sparse matrix can be represented as a bipartite graph. This representation is useful for applying combinatorial algorithms like the Dulmage-Mendelsohn decomposition during preprocessing. In this case however, it is likely that you actually have a matrix pencil $A+\epsilon B$, which is important to know for the combinatorial algorithm, because this indicates which elements are expected to be small. A quick'n dirty fix is to apply the combinatorial algorithm to a related block Toeplitz matrix like $\begin{bmatrix}A\\B&A\end{bmatrix}$ or $\begin{bmatrix}A\\B&A\\&B&A\end{bmatrix}$ instead, but this is starting to get off-topic now.

If a "fixed" mapping between rows and columns is available, it makes sense to specify the symmetry type of the matrix as "general", "symmetric", "skew-symmetric" or, "Hermitian". If the symmetry type is more specialized than "general", then the matrix can be represented by a undirected graph, otherwise a directed graph can be used.

Note that these representations also apply to block-matrices (i.e. both the row indices and the column indices are partitioned into subsets), and encoding some a-priory information into such a block-structure can be a good idea both for speed and robustness.

I could also explain here how low rank modifications fit into such a general framework, but this section is already quite long. Often one can incorporate low rank modifications by just adding the corresponding row and column vectors as additional rows and columns with a small identity matrix between them. The advantage here is that the sparsity pattern of the original matrix is preserved.


Unambiguousness and determinism of CFGs for them to be LR I came across this statement:

  Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.

I was guessing what could be the characteristics of such grammars?

Then I came across this question which very well asks:

  Why does there exist a conflict even though it is not ambiguous grammar?

The answer does not give straight answer to above "Why". But definitely says this:

  A context-free language is LR(k) precisely if it is deterministic.

In this context, I have following guessings which I want confirmations for:

All LR grammars are unambiguous, merely because they need to be deterministic and set of deterministic languages is proper subset of unambiguous languages.
In other words, unambiguous languages which are non LR are those which are non deterministic.
Dragon book says we can enforce association and precedence to ensure unambiguousness of grammar by resolving conflicts. I also read that we do left factoring to convert non deterministic grammar to deterministic grammar.
I am quite confused about what actually converts non LR grammar to LR after considering above two sentences and point 2. Is it enforcing association and/or precedence or left factoring. I feel it should be left factoring given determinism is absolutely necessary than unambiguousness and there must exist some ambiguous grammars which do not turn to LR by enforcing association and/or precedence. Am I correct with this?
Left factoring eliminates FIRST-FIRST conflicts in LL grammarref. But does it help to eliminate SHIFT-REDUCE and REDUCE-REDUCE conflicts in LR grammars?

Your first and second points are correct, although you need to take more care distinguishing between properties of grammars and properties of languages.

A language is context free if (and only if) there exists a context free grammar for it. It is also deterministic if (and only if) there exists a deterministic context free grammar for it. That doesn't mean that all grammars for the language will be deterministic or even context-free; there are basically an infinitude of possible grammars for any language, deterministic and not, ambiguous and not, and not restricted to the smallest class in the Chomsky hierarchy.

In fact, figuring out whether a language has one of these properties is often not easy. While we can easily see which of Chomsky's classes a grammar belongs to, and we can easily determine whether or not a particular context-free grammar is, for example, $LR(k)$ for any given $k$, similar statements about languages are much harder. In particular, the following questions are undecidable, which means that no algorithm exists which will produce a correct answer for every possible input:

Does a context-free grammar exist for a given language?
Does an $LR(k)$ grammar exist for a given language?
Does a deterministic grammar exist for a given language?

Some questions about grammars are also undecidable:

Is there a $k$ for which an $LR(k)$ parser can be generated for a given grammar?
Do two context-free grammars recognise the same language?
Is a given context-free grammar ambiguous?

(There are many more, but these ones seemed relevant.)

Note that "undecidable" doesn't mean you can't ever figure it out. For certain languages and grammars it is quite possible to answer the above questions. But there is no algorithm which can generate a solution. Finding a solution requires luck and perseverance, and there's no guarantee you'll manage it. (This is somewhat like the problem of proving a given mathematical hypothesis.)

One of the consequences of all that undecidability is that there are no 100% reliable algorithms which can "remove ambiguity" from a grammar, make a grammar deterministic, and so on. All of the procedures recommended in the various textbooks you refer to (and internet sites) are just heuristics: they might work, but there are no guarantees. If you determine that a given grammar is not $LR(1)$, or not $LL(1)$, etc., you can try applying the various procedures mentioned, but you might not be able to find a transformation which works. And the mere fact that you didn't manage that transformation proves absolutely nothing about the language, although again there are cases in which you can prove that a given language has no deterministic grammar, or even that it has no unambiguous grammar. (Languages for which no unambiguous grammar exists are called "inherently ambiguous" and you can find examples by searching for that phrase, if you're interested.)

I understand that this may all seem unsatisfactory. I think you really want there to be some visible attribute of a grammar (or language) which you can point to and say, "because of this feature, this grammar is not $X$" (for some property $X$). But there really isn't a better characterisation of, for example, grammars which are not $LR(1)$ than "the $LR(1)$ parser generation algorithm failed to produce a parser for this language".

So, in short:

A grammar is deterministic if the $LR(k)$ parser generation algorithm works for some $k$, and non-deterministic if it doesn't work for any $k$. But you can't prove non-determinism that way, because you'd have to try all possible values of $k$ and that would literally take you forever.

Furthermore, even if a grammar is non-deterministic, it might or might not be ambiguous. There's no algorithm which can tell you that, either.

Finally, with respect to my answer which you quoted, I think it does explain why that particular grammar is non-deterministic: it's because you need to do the first reduction when you hit the middle of the sentence, but since you don't know where the middle of the sentence is until you reach the end (and the sentence could be arbitrarily long), you cannot know at which point in the input you need to do the first reduction. However, the language is certainly unambiguous: there is only one derivation which works.

(These statements are true of palindrome grammars regardless of how many symbols there are in the alphabet. But if the alphabet contains only a single symbol, then there is a different grammar which happens to be regular. In this particular case it's not hard to figure out what it is.)


type theory notation troubles I'm working through "Types and Programming Languages" by Benjamin Pierce and I don't quite understand the notation. Particularly on Page 106, (chapter 9 Simply Typed Lambda-Calculus) there is a lemma (9.3.7):

$$
\text{If } \Gamma \vdash t:T \text{ and } x \notin dom(\Gamma) \text{, then } \Gamma, x:S \vdash t:T.
$$

I understand the idea roughly but I can't quite read this statement out in english. How do I translate the turnstile symbol (\vdash in tex) in this context? In the book I've seen $$ \vdash t:T $$ translated as t is a closed, well-typed term but I don't quite see how to apply that in this context. Looking around apparently the turnstile symbol is also used to mean provable.

Gamma is the typing context and provides binding of variables and their types. t:T means the term t is has the type T. The function dom(gamma) is the set of variables bound by Gamma.

So my best guess for translating this is as follows:

If the term t having type T is a closed, well-typed term under the typing context gamma and x is not in the set of bound variables of gamma, then the term t having type T is still a closed, well-typed term in the typing context gamma after binding the term x having type S.

Is this roughly right? It makes sense but I still feel a bit shaky on the translation. Anyone have any other suggestions, corrections, or comments?
Thanks

$X \vdash Y$ means "The information in $X$ lets you prove that $Y$ is true." This is true in logic in general, as well as in type theory specifically. I often read this as "$X$ says that $Y$ is true."

So,

  If $\Gamma\vdash t\colon T$ and $x\notin\mathrm{dom}(\Gamma)$, then $\Gamma,x\colon S\vdash t\colon T$

translates as

  If we can prove that that $t$ has type $T$ using $\Gamma$, and $\Gamma$ doesn't directly assign a type to $x$, then adding to $\Gamma$ the assumption that $x$ has type $S$ doesn't change the type of $t$,

which is just my way of writing what you wrote.


Typical file structure Short version

The question & answers relate to the following topics:

File as a collection of records vs. file as a stream of bytes
Sequential File
Distinction between file data and metadata
Transfer of metadata along with the file
File size measurement

Original question

According to William Stallings' Operating Systems, the most common structure for a file is the sequential file, which consists of a collection of records. All files have the same amount of records and each record has a predetermined length. This seems very inefficient and doesn't match my previous understanding of files at all.

For example: if I have a JPG file, it would have records indicating things like resolution, creation date, etc. Some record fields would not be relevant for a JPG file and would be empty, but space would be reserved for those fields regardless. Since the actual data of the JPG file would be too large for any record, there would be an "overflow pointer" to where the data actually is.

Stallings also presents an alternative to file-as-a-collection-of-records: file as a stream of bytes. While the book claims it's rare, it is more in line with my understanding of files: a file is just raw data with no universal structure. However, if I move a file from one computer to another, things like "creation date" move along with it, indicating that files have some attributes which are saved within the file (as opposed to in the file management system). If all files have some header information like creation date, and that information is saved within the file, why is it that my Ubuntu claims an empty text file takes 0 bytes space?

I'm guessing that a typical file is simply a stream of bytes with no predetermined structure and that header information like the creation date is somehow transferred along with the file when it is moved. I'm guessing that the chapter about sequential files in the book is some kind of remnant from the 80's. Please correct any misconceptions that I have.

First, let me state that you may have things to unlearn. Files that are a stream of bytes are very much the rule, and have been for a long time. Almost all filesystems store a sequence of bytes, and leave the interpretation of that sequence of bytes up to applications or at least to higher-level libraries. Sequential files, consisting of a sequence (typically of variable length) of fixed-size records, went out of fashion in the 1980s if not in the 1970s. They still exist in big iron¹ (running VMS or “bigger” systems such as IBM mainframe OSes), but most programmers can go through their whole career without seeing one of those. Any book teaching sequential files as common is good only to teach operating system history, not operating systems.

Unix sees all files as byte streams. Simplifying operating system interfaces was one of Unix's major contributions, and that one stuck. Windows also sees all files as byte streams. Between them, that's essentially the whole server ecosystem, the whole workstation ecosystem, the whole mobile ecosystem², and a large chunk of the embedded ecosystem. Small embedded operating systems may have structured files, but if so I think they're generally files with a fixed structure (a single record, if you like, with set of possible formats imposed by the system) rather than a sequence of records.

In a sequential files, all the record play equivalent roles. There isn't a record for different kinds of data, but a record for different elements in a list. You can see an example in the VMS documentation. In modern terms, a sequential file is a table, a record is a row, and tables are stored in databases, not in filesystems. Although filesystems and databases are conceptually related, databases are focused on data with structure (and relations between data elements), while filesystems are focused on independent files. These approaches have different desirable security and stability guarantees, different interfaces, different performance goals, etc.

Things like the creation date³, the access permissions, etc. are generically called metadata. They are also stored in the filesystem, but outside the file's main data area. Operating systems generally report only the size of the “main” data when they report a file's size: the size isn't how much space the file occupies on the disk, but how much data is in the file. Accounting for disk usage completely accurately is rather complex — have a look at this, and keep in mind that this is only on one specific operating system.

A basic way to store files is to have every directory entry be a fixed-size structure containing the file name, other end-user metadata (timestamps, ownership information, access permissions, etc.), and some internal metadata that lets the operating system know where on the disk the file data is. A common extension to this approach is to create a level of indirection, where each directory entry contains just the file name and a pointer to another location (called an inode in the Unix world) containing the rest of the metadata.

The technical term for having multiple parts in a file with different roles (the data, the access control list, the timestamps, etc.) is a fork or stream (beware that both of these words also have different meanings). Many filesystems support only a single stream per file (the data stream), plus some fixed-size metadata. The metadata can be viewed as a stream from a conceptual point of view, but there's often no way to access it as a stream of bytes, only through dedicated functions. Some examples of uses of alternate streams are the resource fork on Mac OS, and extended (variable-size) security attributes on Linux.

The reason many file copy tools copy metadata together with the file content is that they're programmed to do so, i.e. rather than “open existing file, create new file, read data from existing file, write data to new file”, the copy algorithm also includes steps such as “read existing file's permissions, set new file's permissions to those, read existing file's timestamp, set new file's timestamp to that”.

¹  Mainframes — or mainframes emulated on x86 hardware, but running a 20-year-old emulator in which a 40-year-old operating system is running a 50-year-old application written in COBOL that nobody dares touch!
²  Maybe add Symbian — where files are byte streams too.


How does a computer play a video while doing something else? How is video playback done on a computer?  It's obviously not relying purely on the CPU, since video playback continues when a user performs another activity, such as typing into a YouTube comment field.  This task seems further complicated in the case of streaming video, where data presumably needs to be transferred from the network interface to the video/graphics controller.

EDIT: I should have made clear that I understand that the CPU switches among multiple processes and threads all of the time.  My question was meant to be more specifically about video playback.  Is the video processing done on the graphics chipset/card? Do those typically offer buffering? Or can it all be handled by a single-core CPU with time to spare for other tasks, or am I wrong to think that low-end CPUs can play back video without (not-network) delays?

This is implemented using several different techniques.  Within the application (for example, the web browser), the program can execute different threads of execution.  One thread can perform the video streaming/playback, while a different thread can handle the user typing into the comment field.

These threads, along with many other threads and processes, are in turn scheduled by the operating system (even if you only have the web browser open, the operating system has many background tasks running, such as the windowing manager, the print spooler, the USB device manager, etc).  It is the job of the OS scheduler to determine which thread can actively run, on which processor core, and for how long.  In a typical system, a thread can run for up to some threshold value, suppose 100 milliseconds, before the scheduler allows another task to run.

This task switching is fundamental to all modern operating systems (Windows, Linux, UNIX, etc), and is usually a significant portion of an undergraduate operating systems course.


Let $S(n) = T(4n-2)$. Then
$$
S(n) = T(4n-2) = 4T\left(\frac{4n-4}{2}\right) + \Theta(n^2) = 4T(2n-2) + \Theta(n^2) = 4S(n/2) + \Theta(n^2).
$$
The master theorem tells us that $S(n) = \Theta(n^2\log n)$, and so $T(n) = \Theta(n^2\log n)$.

More generally, the statement of the Akra–Bazzi theorem (specifically, the $h_i$ functions) makes it clear that the small perturbation in this recurrence ($\frac{n-2}{2}$ instead of $\frac{n}{2}$) doesn't change the asymptotics of the solution. From this theorem you can derive the solution directly without guessing the substitution $S(n) = T(4n-2)$.


CPU Scheduling - Round Robin order on ready queue I am attempting the question below:

  Assume a set of processes $P_1, P_2, P_3$ and $P_4$ arrive at different times in the ready queue. The table below shows the burst time, the priority (smallest priority number implies highest priority) and arrival time for each of the processes.
  \begin{array}{|c|c|c|c|}
\hline
Process & Burst ~ time & Priority & Arrival ~ Time \\ \hline
P_1 & 8& 2& 0\\ \hline
P_2 & 2 & 3 & 1 \\ \hline
P_3 & 4 & 1 & 3 \\ \hline
P_4 & 6 & 2 & 5 \\ \hline
\end{array}
  Draw a Gant chart, illustrating the execution of the processes, to demonstrate each of the following algorithms.

  First-Come, First-Served (FCFS)
  Round Robin(RR) with time slice of 3 time units.

Problem I am having is that my answer is not matching what I am getting form the simulator here.

The problem might be with the way I am handling my ready Queue. My workings and answer is below. The simulator shows that after first time P3 appears in the chart that P4 should start. But P1 was pre-empted and still had more execution hence I put P1 in there. Where am I going wrong?

Ready Queue (as I was working it out):
P1,P2,P3,P1,P4,P3,P1,P4

GANT CHART:

With round-robin, the scheduler always selects the process that's had the most time since it was last run, and new processes coming in are always assigned a last run time of 1 time unit before the oldest last run time in the current list. (There are other equivalent ways to state this, but this is the simplest one for me. One other way to phrase this that works for many people is "processes that haven't had a chance to run yet have priority".)

So at t=8, we have:

Process Last-run Time-left
P1      0        5
P3      3        1
P4      -1*      6

Note the -1 for P4. The oldest last run time is P1, with 0. So P4 gets assigned -1, and hence gets selected.


Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$ I'm being asked the following

  Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$

For the $L \notin \mathbf{P}$-part I have to show that there is no polynomial Turing Machine that could accept $L$.

I've been struggling with this problem for quite a while, so I would appreciate any help with it.

My attempt:

Let

$$L = \{0, 1\} \cup \{0^i| M_i\text{ does not accept }\langle M_i \rangle\}$$

Then $L^* = \{0, 1\}^*$. Since this language is regular, we can defined a TM that works on the word $w$ in just a single pass $\implies$ TM runs in $O(|w|) = O(n) \implies L^* \in \mathbf{P}$.

I take this $L$ as example because it seems to me easier to show that $L \notin \mathbf{P}$ by proving that indeed there is no MT that accepts $L$ than showing that it is not accepted by any polynomial MT. To prove the former I was thinking about applying a diagolization argument on $L$.

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked, so maybe there is a more straightforward way.

Thanks!

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked

That looks like an excellent approach. Proving something stronger is sometimes easier1 and usually useful.

What's particularly nice about your template for $L$ is that it opens up new questions about what happens if you generalise to $L = A \cup B$ where $A$ and $B$ are in different complexity classes and $B \subset A^*$. The extreme of $A$ regular and $B$ undecidable is good enough, but you could also consider $B \in NP^c$, $B \in EXP^c$, maybe specific context-free $A$, ... Perhaps it would be an interesting question to ask how close they can be to each other while still getting some kind of separation. If you enjoy this kind of thing, there may be a mini research project in it.

1 This is particularly true of proofs by induction, where proving a tight bound often makes the inductive step work where a loose bound wouldn't.


Extended knapsack: is it NP-complete? I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same:

Maximize the value of

($\sum_{i=1}^n v_i \cdot x_i) + B \cdot \frac{W}{r}$

subject to

$ \sum_{i=1}^n w_i \cdot x_i \leq W$.

Here, $W$ and $B$ are constants, and $r$ is an integer variable with $1 \leq r \leq n$, whose behavior vis-à-vis the variables $v_i$ and $w_i$ is unknown to me.

It is obvious that if $B$ is 0, this reduces to the classical knapsack and is hence NP-complete, but is it still NP-complete otherwise?  Can we say anything about this problem considering possible behaviors of $r$?

It's been a while since I studied algorithms; please bear with me if this looks too simple (let me clarify that this question arose from research; I'm not a kid trying to cheat on homework).  I have also not found an answer in the responses to other knapsack questions asked on this forum.

$B*\frac{W}{r}$ is a constant, so adding it to your objective function has no effect on the solution. The problem is NP-complete, regardless of the values of $B$ and $r$.


What is a symbol code? I am a physicist learning a bit of information theory.

I have encountered a term ("symbol codes") on Wikipedia, and cannot find what it means:

  Source coding theorem for symbol codes

  Let $\Sigma_1,\Sigma_2$ denote two finite alphabets and let $\Sigma_1^*$ and $\Sigma_2^*$ denote the set of all finite words over those alphabets (respectively).

  Suppose that $X$ is a random variable taking values in $\Sigma_1$, and let $f$ be a uniquely decodable code from $\Sigma_1^*$ to $\Sigma_2^*$, where $|\Sigma_2| = a$. Let $S$ denote the random variable given by the length of the codeword $f(X)$.

  If $f$ is optimal in the sense that it has the minimal expected word length for $X$, then (Shannon 1948): $$ \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} + 1, $$ where $\mathbb{E}$ denotes the expected value operator.

Please let me know what does symbol code mean.

"Symbol Codes" means codes that work over a (finite) alphabet with an arbitrary size. Many times people focus only on binary codes, and Shannon Thm says that the minimal code length of some random variable $X$ is between $H(X)$ and $H(X)+1$ bits.

But what if, instead of bits, you use trits, or symbols from a larger alphabet of size, say, $a$?  Then, the length of $X$'s coding needs to be adjusted since every symbol of the codeword now "contains"  $\log_2 a$ bits.
Then, the wikipedia page says, the minimal code length will be
between $H(x)/\log_2(a)$ and $H(x)/\log_2(a)+1$ symbols.

Multiply the equation by $\log_2 a$ to convert into information bits:
the codeword will have $S$ symbols, hence $S\log_2 a$ bits, and this amount, by Shannon's coding theorem, can be minimized so that it is almost $H(X)$ (maybe up to one additional symbol, i.e., additional $\log_2 a$ bits).


Seeding the Mersenne Twister Random Number Generator I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I noticed there were two ways to seed the MT: with a single integer seed or an array of integer seeds. What is the point in seeding with an array? Does it produce a better distribution or a longer period?

Also, I would appreciate it if somebody could explain to me what is meant by the "state" of the RNG, as I am seeing that word all over the source code. Is it like a finite state machine in a way?

Thanks for your time!

A random number generator has the following simplified pseudocode:

state S;

int random() {
  S = advance_state(S);
  return extract_integer(S);
}

The random number generator maintains an internal state, which in the case of MT consists of an array of words and an index. Every time you want to generate a new number, two things happen: (1) the state is modified in some devious way; (2) the state is compressed to the output word. The entire random number generator is thus a finite state machine which proceeds deterministically from state to state (there is no "input"), while also producing output.

MT is implemented slightly differently by generating several output words at once, but this is just an optimization - you can also implement it in just the way I described.

Here is a simple naive example. The internal state S is a 32-bit word. It is updated by increasing it by 1. The output is the least significant bit. If S is seeded by 0, then the first few outputs are 0, 1, 1, 0, 1, 0, 0, 1, ... (the first $2^{32}$ bits in the Thue-Morse sequence).

How does the internal state get initialized? There are two ways. One way is to give the entire internal state. The other way is to give a smaller "seed", and from the seed generating an internal state in some devious way. If we do it deviously enough, then the function associating a seed with the resulting internal state will look like a random function (in other words, it will seem as we're selecting $2^{32}$ different random internal states, when the seed is a 32-bit integer).

The cryptographic strength of the second way is only 32 bits - you only need to try all $2^{32}$ different seeds in order to complete a given sequence. If you care about that and the seed is too short for your taste, you can use the first method and come up with an entire internal state, though that's usually not necessary, and certainly isn't necessary if all you want is random numbers for simulation purposes. (If you want cryptographically secure random numbers, please don't use MT.)

Other ways of seeding a random number generator, which sit on top of these methods, include using a password or passphrase (which is converted to a seed using a hash function) and using random data from your computer (which again passes through a hash function which functions as a randomness extractor).


Two Dimensional Tape of Turing Machine I was looking at this: http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html

At the very beginning, they show a 2d tape and (I assume) it's 1d equivalent. However, I cannot figure out they got from the 2d case to the 1d case. I was hoping someone could elaborate.

The idea is very similar to the way we show that the rational numbers are countable.
Essentially, what you need to do is to find a (bijective) mapping of the 2D tape onto the 1D tape. Of course, you want this mapping to be computable, and it would be helpful if it is computable efficiently.

The illustrative way to think about this is in diagonals: the cell $(1,1)$ is mapped to cell $1$ in the 1D tape. Then the second diagonal, namely cells $(1,2)$ and $(2,1)$ are mapped to cells $2,3$ respectively. Continuing in the same manner, you can map the entire 2D tape to the 1D tape. Of course, any movement of the head needs to be translated to the correct position in the 1D tape, so a single movement in the 2D tape may actually take several operations to simulate in the 1D tape.

There are many explicit functions that compute such a mapping. See for example the Cantor pairing function.


What does "higher order address bits" and "lower order address bits" mean? "Assume a system with 4 GB virtual memory and 1 GB physical memory with 32 bit addresses. if the page size is 4 KB, How many bits will be allocated as the Higher Order Address bits and Lower Order Address bits to identify page numbers and corresponding words respectively?"
My question is, What does "higher order address bits" and "lower order address bits" mean in the above question?

According to the problem, the address itself is 32 bits long. Some of those bits (the higher order ones, i.e. closer to the msb) are used to identify a page, and some of those bits (the lower order ones, i.e. farther from the msb) are used to identify a word within that page. The question here is, how many bits should be allocated for each part, to ensure you can address as much of your memory as possible.

(The msb is the "most significant bit": the one that has the highest place value. We can't just talk about the "first bit" or the "last bit" because nobody can agree on whether the msb comes first or last. It's a headache for anyone doing network programming.)


Why we can't have some algorithm to be polynomial if there are generic conditions that make them so? I explain it better:
There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time.
An example is Bin Packing, the decision version of the problem is an NP-complete problem and it's defined as follows in the book "Computers and Intractability" by Michael R. Garey and David S. Johnson:

INSTANCE: Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.
QUESTION: Is there a partition of $U$ into disjoint sets $U_1, U_2, ..., U_k$ such that the sum of sizes of the items in each $U_i$ is $B$ or less.

And there is a comment that says "Solvable in polynomial time for any fixed $B$ by exhaustive search."
I have asked in math.stackexchange how it is possible and I get a clearly answer about that:
https://math.stackexchange.com/questions/3804912/bin-packing-problem-with-fixed-size-of-bins
Now I ask you why we can't applicate things like this to all instance of the problems? What is the thing that I don't get that makes this impossible?
For example, in the Bin Packing problem I think that I would can always enumerate the solutions and search into them because the $ B $ is always fixed once I get it, ok the number of the solutions could be a huge number, but it still remains a polynomial time algorithm. Or the "enumerate solutions" meanings that they are precomputated and the algorithm just has to check between them? And in this case, why we can't precomputate always?
I'm not saying something like $ P=NP $ because I'm sure not the first person that think about this thing and if the most accredited opinion is that $ P \not= NP $ it must be why this thought of mine is wrong and I want to understand why this isn't a generic solution for the problem, and where I'm wrong.

It's often the case that an NP-complete problem has some parameter $b$ that when fixed to a small constant makes an polynomial algorithm possible, yes.
However in fixing $b$ that problem (at least as of writing when $P =^? NP$) loses its completeness. That means when we want to do a reduction we (for at least some instances) need this parameter to be bigger than $b$.


Rational versus intelligent agents Question about "Artificial Intelligence: A Modern Approach by Russell and Norvig"

I have issue to distinguish clearly between intelligent and rational agent presented by Norvig and Russel. What I understand is that rational agent think and act like human but not intelligent agent. Thus, Russel present 4 types of intelligents agents
– Simple reflex agents
– Model-based reflex agents
– Goal-based agents
– Utility-based agents

My question is : could Goal-based agents be a rational agents at the same time ? Does this concept limite intelligence to just human intelligence ? Some paper do not make distinction between these two terms.

Before I go straight to your question, we have to get a clear picture of these two terms that might seem confusing;

1.rationality(an agent is able to perform given task x after analysing y,that is right fit for x).

2.intelligence.(an agent is able to perform given task x after analysing y inline with reasoning ie..why x?....).

could Goal-based agents be a rational agents at the same time ?
Basing on the above two hints,the answer is yes.

Does this concept limit intelligence to just human intelligence ?
According to artificial intelligence research,so far,we haven't reached at the level of human intelligence (artificial general intelligence).

Hope this can give you some insights.


Between every two MST's there's a series of "nearby" MST's Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T_1, T_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\{e\})\cup\{e'\}$.

Prove that for every $T, T'$ there exists a series of $T=T_1,T_2,...,T_k=T'$ such that every two consecutive MST's are nearby each other.

I started proving it using induction but it didn't work. Assume I have $T,T'$ that has $k+1$ distinct edges each, and I know (by induction assumption) that each two MST's with $k$ distinct edges has a series between them, what can I do next? All I know is that the sum of those $k+1$ edges in each MST is equal.

Thanks.

Here is how you make progress from $k+1$ distinct edges to $k$ distinct edges.

Suppose $T$ and $T'$ has $k+1$ distinct edges, which refer to $k+1$ edges in $T$ and another $k+1$ edges in $T'$ and they are all distinct. Among these $2k+2$ edges suppose $e\in T$ has the smallest weight.

Adding $e$ to $T'$ results in a cycle $C\subseteq T'\cup\{e\}$. If there is an edge $e'\in C$ such that $w(e')=w(e)$ and $e'\notin T$, then we are done: let $T''=(T'\cup\{e\})-\{e'\}$, and now $T''$ has $k$ distinct edges with $T$, while $T''$ and $T'$ are nearby.

The rest is to show that such an edge $e'$ always exists. Since $C$ cannot be entirely contained in $T$, there must be an edge $e'\in C$ that $e'\notin T$. I leave it to you to verify that either $w(e')<w(e)$ or $w(e')>w(e)$ cannot happen, so it must holds $w(e')=w(e)$ and that $e'$ is what we want.


Can we implement every algorithm using only immutable variables? Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?

Probably not, but I don't know if this has been definitely proven, and it depends on what you'll allow as "using only immutable variables".

In 1997 Pippenger published Pure versus Impure Lisp (Technical Report). This paper gives a negative answer when the programming language is Lisp with and without mutation (RPLACA and RPLACD) under some restrictions, namely the program consumes and produces sequences of atoms, and the program must be on-line meaning given potentially unbounded sequences as input, the program must output the $n$th output before consuming the $(n+1)$-th input. One thing to note, is that there is an unlimited supply of atoms, so each individual atom can contain an arbitrary amount of information. That said, it is difficult to get information out of an atom as it only supports equality. Part of the motivation for the first restriction is, as discussed in the papers introduction, "pure Lisp" can't make cyclic structures. If we allowed arbitrary structures as output, then there would be some (representations of) outputs that "pure Lisp" would simply be unable to make.

Now this is all well and good but also published the same year by Bird, Jones, and de Moor we have the paper More Haste, Less Speed: Lazy versus Eager Evaluation (PDF). This implements Pippenger's counter-example in the lazy language Haskell (but a lazy version of Lisp could also easily have been used) with the desired performance guarantees. (Not mentioned, but laziness also allows us to make cyclic structures.) That said, lazy evaluation, i.e. call-by-need not call-by-name, is usually internally implemented via mutation, but this internal mutation is unobservable from the language. I don't believe either paper discusses space usage.

More practically speaking, array algorithms are often the bread-and-butter of imperative programming, while in (pure) functional programming mutable arrays are awkward. (Graph algorithms are another area where pure functional programming struggles.) I'm pretty sure no one has demonstrated how to implement a persistent array with $O(1)$ lookups and updates to all versions. We can make persistent arrays with $O(1)$ lookups and updates to the latest version (and slower lookups/updates for older versions). Haskell's DiffArray implements this, though again the implementation utilizes mutation, but again this is not observable to the program. Since imperative programs are forced to use (mutable) data structures in a single-threaded manner anyway, this should allow any imperative array algorithm to be implemented in Haskell with no asymptotic slow-down (from the array at least).

The question gets murkier as we allow more features in the language. For example, the Clean programming language, another pure, lazy functional language introduced around the same time as Haskell, never had any trouble with arrays. Clean supports uniqueness typing which can guarantee that the reference you have to a data structure is the only reference. This allows operations to be implemented with in-place updates. The interface, though, is the same as the immutable interface except for an extra typing discipline. In particular, the updates could be implemented in an immutable fashion without the program being able to tell the difference.

Theoretically, I believe the question is still open, but it depends on what you consider the machine model. In some machine models it is answered. Practically, it's pretty clear that mutation is sometimes the only reasonable approach, but purely functional interfaces to mutation and mutable structures blur things a bit.


Max flow with priorities I'm studying a simple max flow problem:

Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph:

There are $|a_i|$ objects of the type $a_i$. Store $b_j$ can contain at most $|b_j|$ objects. This shows as capacity constraints on the graph. The other edges have no capacity constraint and just mean "this type of object can be stored in this store". We want to maximize the total number $N$ of objects being stored. Max flow on this graph answers to this question.

Now we add a priority idea. Each type of object $a_i$ has an integer priority $p(a_i)$ say from $1$ to $2$ for simplicity. Instead of maximizing the total number of objects, we want to maximize $(N_1,N_2)$ in lexicographical order where $N_p$ stands for the number of objects with priority $p$ being stored.

Do you see a way to formalize this problem as a flow problem (possibly with a broader meaning than just simple max flow)? Or a way to use max flow algorithms to solve it?

First, build an algorithm to solve the  following problem:

Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$.

That problem  can be solved using algorithms for minimum cost circulation, which is a generalization of max flow where we can also have lower bounds on certain edges.  (You'll set the cost of all edges out of the source to 1 and the cost of all other edges to 0, as you don't need different costs.)

Then, do binary search on $t$ to find the largest $t$ for which a solution exists.

How do you solve the problem above?  We need to modify the graph.  Instead of adding a single source vertex $s$, we'll add three vertices $s,s_1,s_2$.  Add an edge $s \to s_1$ with lower bound on capacity of $t$.  Add an edge $s \to s_2$ with lower bound 0.   Add edges $s_1 \to a_i$ for each $i$ where $p(a_i)=1$, and $s_2 \to a_i$ for each $i$ where $p(a_i)=2$.  All edges other than the $s \to s_1$ edge have lower bound on capacity of 0.  Now any valid flow for this problem that respects the lower bounds will satisfy $N_1 \ge t$.


How to convert $(0.11001100...)_2$ to a decimal number I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number.
But I have a hard time finding an algorithm for converting a binary number with infinite bits to a decimal number.
I will like to convert $(0.11001100...)_2$ to a decimal number.

Classical formula for proper fraction is
$$(0.a_{-1}a_{-2}a_{-3}\cdots)_2 = \left(\sum\limits_{k=1}^{\infty}\frac{a_{-k}}{2^k}\right)_{10}$$
Where for $a_{-k}$ we have $k \in \mathbb{N}$ and $a_{-k}\in \{ 0,1\}$.  As you see for indexing is taken negative numbers.
In your example
$$(0.11001100...)_2 =\left( \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^5}+\frac{1}{2^6}+ \cdots\right)_{10}$$


How to find a superstar in linear time? Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally:

$\qquad \displaystyle $v$ \text{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1$

with $n$ the number of nodes in the graph. For example, in the below graph, the unfilled node is a superstar (and the other nodes are not).

[source]

How can you identify all superstars in a directed graphs in $\mathcal{O}(n)$ time? A suitable graph representation can be chosen from the usual candidates; please refrain from using representations that move the problem's complexity to preprocessing.

No assumptions regarding density can be made. We don't assume the graph contains a superstar; if there is none, the algorithm should recognize it.

Notation: $\mathrm{outdeg}$ is a node's number of outgoing edges, $\mathrm{indeg}$ similar for incoming edges.

We can eliminate all but one of the vertices by checking for the existence of $n-1$ edges because we can eliminate one possibility for each edge we check. In particular, if there is an edge going from $x$ to $y$, we eliminate $x$ and move on to $y$ (as another vertex can be reached from it); if not, we eliminate $y$ (as it cannot be reached from $x$). Once we reach the last vertex, whichever vertex is not eliminated should be compared with each other vertex (ensure the superstar condition is upheld: there is an edge incoming but not outgoing) until it is eliminated or confirmed as the superstar. Some pseudocode:

vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

Let's walk through an example to illustrate the method. Take this array, with the source vertex on the top and destination on the side. 1 indicates an edge:

$$
\begin{array}{r|c c c c|r}
  & 1 & 2 & 3 & 4 \\
\hline
1 & - & 1 & 0 & 1 \\
2 & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

I'll grey out the vertices we have ruled out as potential superstars.
I'll use green and red to indicate the edges we are looking at when they do and do not contain the edge we're looking for, and blue to indicate where we have already looked.

We start by looking at vertices 1 and 2.

$$
\begin{array}{r|c c c c}
  & 1 & 2 & 3 & 4 \\
\hline
1 & - & \color{green}{1}
          & 0 & 1 \\
2 & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$
The green number shows there is an
edge from 2 to 1, so we eliminate 2 and look for an edge from 3 to 1:

$$
\begin{array}{r|c c c c}
  & 1 & \color{grey}{2} & 3 & 4 \\
\hline
1 & - & \color{blue}{1}
          & \color{red}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

We see there is no such edge, so we eliminate 1 and take 3 as our current
vertex. Recall that we have eliminated 2 already, so see whether there is an edge from 4 to 3:

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & 4 \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & \color{green}{1} \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

There is an edge from 4 to 3, so we eliminate 4. At this point we have
eliminated all but one of the vertices (3), so check out its edges and see whether it qualifies:

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{red}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & \color{green}{1} & 1 & - & \color{blue}{1} \\
\color{grey}{4} & 1 & 1 & 0 & - \\
\end{array}
$$

There is an edge from 1 to 3 but not the reverse, so 3 is still a candidate.

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & \color{red}{0}
              & 1 \\
3 & \color{blue}{1}
      & \color{green}{1}
          & - & \color{blue}{1} \\
\color{grey}{4} & 1 & 1 & 0 & - \\
\end{array}
$$

There is also an edge from 2 to 3 but not the reverse, so 3 is still a candidate.

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & \color{blue}{0}
              & 1 \\
3 & \color{blue}{1}
      & \color{blue}{1}
          & - & \color{green}{1} \\
\color{grey}{4} & 1 & 1 & \color{red}{0}
              & - \\
\end{array}
$$

There is an edge from 4 to 3 but not 3 to 4; that completes our check of 3's edges and we have found that it is, in fact, a superstar.

Since we eliminate one vertex as a possible superstar on each of the first
$n-1$ edge checks, the best case is that the $n$th check eliminates the
final vertex for a complexity of $n$. In the worst case (the last or
second-to-last vertex is a superstar, or the final check disqualifies it), after the first $n-1$ comparisons we compare the candidate
with $2\times(n-1)$ more vertices, for a worst case complexity of $3n-3$ ($O(n)$). So, this algorithm is
$\Theta(n)$.


Is inserting into an ordered array by swapping has downsides compared to inserting into a position and offsetting elements I'm thinking how I can insert an element into an ordered array. Assume the array has a capacity for one element. I've implemented two methods.

The one finds the position to insert, moves elements one position to the right and inserts the element into the position.

The seconds one which seems more intuitive to me is to put an element into the last position in an array and then put it in the correct position by swapping with the left element - the way it's done in the insertion sort.

However, I googled for the solution and almost all suggestions are some modification of the first algorithm. So I'm wondering if there's something I'm missing. Can you guys please help?

Both work.  Both approaches are approximately equivalent, in some sense.  However, your approach will do about twice as much work.

Think about an array that initially contains $[2,4,6,8,0]$ where the $0$ is the final empty element that can be filled in.  Imagine you want to insert the number $5$.

The standard method will read $8$ from index $3$, then write $8$ to index $4$, yielding $[2,4,6,8,8]$; then read $6$ from index $2$ and write $6$ to index $3$, yielding $[2,4,6,6,8]$; then write $5$ to index $2$, yielding $[2,4,5,6,8]$.  That's 2 reads and 3 writes -- 5 memory operations.
Your method will swap $8$ and $0$, yielding $[2,4,6,0,8]$ (this involves reading $8$ from index $3$, reading $0$ from index $4$, writing $8$ to index $4$, writing $0$ to index $3$); then swap $6$ and $0$, yielding $[2,4,0,6,8]$; then overwrite the $0$ with $5$.  Each swap requires 2 reads and 2 writes, so this does a total of 4 reads and 5 writes -- 9 memory operations. That's about twice as much.

Why is your method slower?  Because your method keeps reading the $0$ and writing it somewhere.  That is extra, unnecessary work.  If you care about optimization, that might matter.  If you just want a method that you can understand, either one should be fine.


How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$? I already saw this answer. But I didn't understand totally.

So I found the solution to this equation $T(n)=4T(n/2+2)+n$.

Here is the recursion tree. But I can't compute the height as $lgn$ from this tree.

How to compute height? (Image is from solution)

Suppose that $n = 2^m+4$. Then
$$
\frac{n}{2} + 2 = \frac{2^m+4}{2} + 2 = (2^{m-1} + 2) + 2 = 2^{m-1} + 4.
$$
We conclude that if $n = 2^m+4$ then the height is $m$ (or $m+1$, depending on how you count), with $T(5)$ in the leaves. This shows that for this type of $n$, the height of the recursion is $\log_2(n-4)$ (or $\log_2(n-4)+1$, depending on how you count).

For general $n$, the exact answer depends on the interpretation of $n/2$ — whether you take floor, ceiling, or anything else — but the height will still be very close to $\log_2 n$.


Why is MAX-2SAT not in P? Max-2-SAT is defined as follows. We are given a 2-CNF formula and a
  bound k, and asked to find an assignment to the variables that
  satisfies at least k of the clauses.

I can understand the trick used to prove 2-SAT is in P. You use get a contradiction by using unit propagation. But, I was wondering why does MAX 2-SAT escape this.

Also, I find it hard to believe this is NP-complete. Certainly, what is the problem that causes it to blow up.

Why wouldn't an algorithm like this work. Given a 2-SAT expression. Find it's length, which we can do in P. Need to check if there is at least k of the clauses.

So we just check $\binom n k$ posibilities and run like Horn algorithm on each sub expression of the n 2-SAT expression. Surely, where is the problem as we are just running a P algorithm a polynomial amount of time.

So I'm very confused. Sort of similar problem I have factorization and if that is in P or NP.

Observe that the expression ${n\choose k}$ may be exponential in $n$ (e.g. if $k=n/2$).

Factorization is surely in NP. We don't know whether it is in P or not. This is a major open question. The fact that factorization is in BQP gives evidence that it might not be NP-complete (as other NP complete problems are not known to be in BQP)


computationally efficient linear index to index pair mapping Consider two index sets $S = \{0, 1, 2, 3, 4, ..., N - 1\}$ and $Q = \{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\}$. Let $R = \{(a, b)\space |\space a, b \in S, a \ge b\} = \{(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), \dots\}$. There will be $\frac{N(N + 1)}{2}$ elements in $R$. Is there a one-to-one function $f : Q \to R$ that is computationally efficient?

One application is to map the linear memory index to row and column of a triangular matrix. Another application is to map thread numbers to work items in parallel programs where the work deals with pairs of items (triangular domain problems).

For a given $m \in Q$, we need to find the biggest $n \in R$, such that $\frac{n(n+1)}{2} \leq m$. Hence, the first element will be $n$ and the second elemnet is $\lfloor m - \frac{n(n+1)}{2} \rfloor$. Now, the question is how can we compute $n$ efficiently? Fortunately, it can be computed by testing some constant numbers and the specified pair will be $(n, \lfloor m - \frac{n(n+1)}{2} \rfloor)$ for a given number $m \in Q$.


Is resolution complete or only refutation-complete? Going through some knowledge representation tutorials on resolution at the moment, and I came across slide 05.KR, no77.

There it is mentioned that "the procedure is also complete".

I think this completeness can not mean that if a sentence is entailed by KB, then it will be derived by resolution. For example, resolution can not derive $(q \lor \neg q)$ from a KB with single clause $\neg p$. (Example from KRR, Brachman and Levesque, page 53).

Could anyone help me figure out what is meant in this slide? Is the completeness of slide refer to being refutaton-complete and not a complete proof procedure?

Resolution is complete as a refutation system. That is, if $S$ is a contradictory set of clauses, then resolution can refute $S$, i.e. $S \vdash \bot$.

This is sufficient since $T \vdash A$ is equivalent to $T \cup \{\lnot A\} \vdash \bot$. So if we want to see a formula $A$ is derivable from $T$, we only need to check if there is a refutation proof for $T \cup \{\lnot A\}$ which can be checked using resolution.


Is generalized XOR-SAT efficiently solvable? I've seen how XOR-3-SAT is efficiently solvable (for instance, see the "XOR-satisfiability" section in  the Wikipedia entry for Boolean satisfiability problem).

I'm wondering a basic question:  Is XOR-k-SAT efficiently solvable, for formulas with varying amounts of literals per clause?

I'd really like to know if we can increase the amounts of literals per clause beyond 3, and if we can have mixed clause lengths.

It looks like the Wikipedia article you linked to says that XORSAT (not just 3-XORSAT) is in P. The method by which they are solving that 3-XORSAT formula in their example very easily generalizes to formulas in which the clauses can have arbitrarily large numbers of variables and differing numbers of variables.

You just look at the formula as a system of linear equations where you have an equation for each clause, and a variable for each variable. For example, the formula:

$$(x_1\oplus x_2\oplus\lnot x_3\oplus x_5)\land (x_2\oplus x_3)$$

has a satisfying assignment if and only if the following system of equations has a solution:

$$x_1+x_2+(1+x_3)+x_5\equiv 1 \mod 2$$
$$x_2+x_3\equiv 1 \mod 2$$

And we can find solutions to linear systems of equations like these in polynomial time using Gaussian elimination!


Do an ambiguous grammar and its corresponding unambiguous version generate the same language? If I have an ambiguous grammar G and its disambiguated version D.
Then which one is true  L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)?

As I tried with some examples to transform a grammar to it unambiguous version but i found that both are equivalent.

I mean is there a specific set relation between both. Please help me and provide an example if possible.

When you disambiguate a grammar, you usually want at least to keep the language the same. So the answer is that you want  $\mathcal L(G)=\mathcal L(D)$.

If you accepted that $\mathcal L(G)\subset \mathcal L(D)$ then you could simply choose $\mathcal L(D)=\Sigma^*$, since $\Sigma^*$ has an unambiguous grammar. Of course $\Sigma$ is the terminal alphabet.

If you accepted that $\mathcal L(D)\subset \mathcal L(G)$ then you could simply choose $\mathcal L(D)=\emptyset$ since $\emptyset$ has an unambiguous grammar.

I assume you were considering context-free (CF) languages. You should have said so.

And you should remember some facts that will not help:

Some CF languages are inherently ambiguous, so that you cannot find an unambiguous grammar for them. Furthermore, it is undecidable whether a CF language is inherently ambiguous,
It is  undecidable to know whether a grammar is ambiguous, hence it is not clear when a disambiguating transformation is needed.

See also wikipedia page on ambiguous grammars.


Doubt regarding strong component in a graph I know that strong component in a graph means between any 2 vertices there should be bi-directional path.

My doubt is cycle is always a strong component. can there be any other subgraph with some property P so that it is strong component ie., P implies strong component.

Your question is a bit too broad. There can be a lot of properties $P$ such that if $H$ is a subgraph of $G$ and $P(H)$ holds then all vertices of $H$ are in the same strong component.

For example:

$P(H) = $ true iff H is a (directed) clique
$P(H) = $ true iff H contains only one vertex
$P(H) = $ true iff for every edge $(u,v)$ of $H$, $(v,u)$ is also in $H$.
$P(H) = $ true iff $H$ has $n>1$ vertices and more than $(n-1)^2$ edges.
...

You can prove that the last condition implies that the vertices of $H$ are in a strong component by induction on $n$.

If $n=2$ then the graph has more than $1^2 = 1$ edge, i.e., it has at least two edges. The claim trivially follows.

If $n>2$, then let $H'$ be any (not necessarily proper) subgraph of $H$ with $(n-1)^2+1$ edges. Pick a vertex $v$ of minimum degree in $H'$. The degree $\delta$ of $v$ is at most $\frac{(n-1)^2+1}{n}$. Therefore $H-v$ has $n-1$ vertices and at least $(n-1)^2 + 1 - \delta = \frac{n(n-1)^2+n - (n-1)^2 - 1}{n} > (n-2)^2$ edges. By inductive hypothesis $H-v$ is strongly connected. The claim follows since $\delta$ is at least $(n-1)^2 + 1 - (n-1)(n-2) = (n-1)(n-1 -n +2) = (n-1) + 1 = n$, showing that $v$ has at least one incoming and one outgoing edge.


Hadamard transformation and measurement of one qubit I also came across something, which is not completely understandable for me, so I ask here.

Given is a qubit in an entangled state, this is:
$$ \frac{1}{\sqrt{2}}(\left|00\right>-\left|11\right>) $$
Now it is said that one could also apply the Hadamard transformation to the first bit and measure the first bit of the pair.
That would mean so far:
$$ \frac{1}{\sqrt{2}}(\left|H(0)0\right>-\left|H(1)1\right>) $$
My question is, where does the measurement start now?

Do I have to measure H (0) and H (1) and if so how does that work?
For a single qubit, I know what a measurement looks like, say, we have
$$ \frac{1}{\sqrt{2}}(\left|0\right>-\left|1\right>) $$
Then my qubit is 50% in state 0 and 50% in state 1

But how is that applied to the entangled particle?

Alternatively, I've multiplied this step out
 $$ \frac{1}{\sqrt{2}}(\left|H(0)0\right>-\left|H(1)1\right>) $$
 $$ \frac{1}{2}(\left|00\right>-\left|01\right>+\left|10\right>+\left|11\right>) $$

Now my second question, what is the first bit of the entangled pair here?
and how is the probability that the first bit is in $ \left|0\right>$ calculated?

I hope you can help me a bit. Thank you!

I'm not the best person to answer your question but I'll give it a try.

1st Question:

You do not yet make a measurement after applying the Hadamard Operator on your first qubit. Afterwards say you make a measurement on your 1st qubit, the state you'll end up with is:

$|\psi>_{post-measurement}$ = $1/\sqrt{p_1(m)}$ $\sum_{j} c_{mj} |m>_1 |j>_2$

whereby $m$ is the measurement result of your 1st qubit (either 0 or 1) , $p_1(m)$ is the probability of getting that result on your 1st qubit, $c_{mj}$ the usual coefficient infront of your ket.

2nd Question:

This will answer how to get ${p_1(m)}$.
Write out the density matrix of $|\psi>_{pre-measurement}$, then trace out the 2nd qubit. Then apply bra-ket to your reduced density matrix:

${p_1(m)}$ = $<m|_{1}$ $\rho_{1} |m>_{1}$

Or equivalently:

${p_1(m)}$ = $\sum_{n}|<m|_1<n|_2 \sum_{ij} c_{ij} |i>_1|j>_2|^2$


What is a lay explanation for universal search? I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply haven't been able to find an explanation suitable for a reader without a background in statistics/computer science.

I've been reading this article on Universal Search from Scholarpedia, which seems to cover the topic. I'd appreciate an explanation for what Universal Search (or Levin Search) means.

Think of it like this.  You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine).

Now, take your favourite programming language (say Python), and create every single Python program consisting of at most 10 characters!  Then you run all those programs with your input for 10 seconds each, each on input $x$.  If none of them give you the answer, you go all the way to 11.  Run each program of at most 11 characters (including the ones you already tried, of course) for 11 seconds each, on input $x$.  If none of them give you the correct answer, you continue to 12 and so on.

More formally, in iteration $i$, you run all programs of length at most $i$ (finitely many, but of course exponential in $i$), each for $i$ seconds (or steps).

There is a program, say $P$ that gives the correct output in $s$ seconds.  When you have come to iteration $i = \max\{|P|, s\}$, this program will be run for at least $s$ seconds, and you will output both $P$ and the solution.


What is a "slice" of a parameterized problem $(Q, \kappa)$? In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:

Definition 1.10.
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\ell$th slice of $(Q, \kappa)$ is the classical problem

$$(Q, \kappa)_\ell := \{x \in Q\ |\ \kappa(x) = \ell\}$$

Which is also referred to in the following chapters. Although I can understand the topics fairly enough, I still cannot understand the term "slice" in detail.

I kind of "memorized" that a slice of an fpt problem is solvable in PTIME. However, I do not really understand the logic behind it.

So, my question is:

  What is a slice of a parameterized problem?

The way you state it, a slice of an parameterized problem is the problem where we use some fixed constant for our problem parameter, instead of a 'free' variable. In a sense, we are only considering the subfamily of the problem for this particular constant, which is probably the logic behind the name 'slice'.

Indeed, if a problem $(Q,\kappa)$ is fixed parameter tractable, there is an algorithm that solves this problem with running time $O(f(n)\cdot g(\kappa))$, where $f$ is (sub)polynomial and $g$ can be superpolynomial. So, if we take a slice of this problem, then there is an algorithm that solves the problem '$(Q,l)$' ($=(Q,\kappa)_l$) in time $O(f(n)\cdot g(l)) = O(f(n))$, as $l$ and therefore $g(l)$ is constant. So $(Q,\kappa)_l$ is indeed solvable in PTIME.


How do context switches factor into CPU utilization? When studying operation systems, is context switch time included in CPU utilization time? For example, if 5 percent of CPU time is wasted to context switching, is CPU utilization 95 percent?

What is measured as "CPU utilization" is (time CPU working) / (total time). The overheads (like context switches) are part of the (time CPU working). So you might have 50% CPU utilization, of which 5% is context switch time.


Stack Permutation Algorithm I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.

For example if the top of the stack is on the left, then say the N=3 rotate instruction would do the following:

A B C D -> C A B D

A few more examples:

A B C D -> B A C D (N=2)
A B C D -> D A B C (N=4)

In other words the Nth element is removed and put at the top of the stack.

The question arises where I need to be able to permute the top N stack elements, but using the minimum number of rotate instructions.

How do I find the optimal sequence of rotations to perform for any given permutation?

A naive algorithm would be the following:

Starting with the largest rotation (N=4 above), keep applying until the required element is in the 4th position.
Reduce the size of the rotation by one and apply 1) again.

An example of the naive algorithm would be:

Permute: A B C D -> D A C B

If we list the rotate instructions in order as a list of numbers, would give:

4 4 3 3

But in fact, the optimal rotates would be:

3 2 4

EDIT - Further Investigations

I thought I would initially just try to enumerate all the optimal sequences for a given size of permutation - i.e. brute force it. And then look for patterns.

Here is the list I generated for size 4. I've renumbered the stack elements starting from zero, as that is actually more natural (since the top stack element is never moved to the top). So a 1 operation would bring the secondmost element to the top etc.:

-   ABCD
1   BACD
12  CBAD
123 DCBA
13  DBAC
133 CDBA
2   CABD
21  ACBD
213 DACB
22  BCAD
223 DBCA
23  DCAB
232 ADCB
233 BDCA
3   DABC
31  ADBC
312 BADC
313 CADB
32  BDAC
322 ABDC
323 CBDA
33  CDAB
332 ACDB
333 BCDA

A few observations are immediately apparent:

The maximum number of operations needed is N-1 for a permuation of
size N.
There are more optimal sequences starting with 3 than with 2,
and more with 2 than with 1.
There is a regular pattern to the sequences starting in 1 or 3
The longer sequences contain the shorter ones to the left hand side. In other words if 322 appears then so will 32 and 3.
There is a unique optimal sequence for each permuation

The pattern seems to be the following for those starting with 3 for example:

3(123)(23) - where the brackets indicate a choice

or for 1

1(23)3

But the pattern is not so obvious for those starting with 2.

Still, all that doesn't help in finding the actual sequence for a permutation.

EDIT

Thanks all for your answers, it was fun!

I've now implemented the algorithm in my Forth compiler.

Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are equivalent problems because if we choose a prefix $\sigma(1)\sigma(2)\ldots \sigma(i)$ and right-cycle it, then we can reverse that by choosing the $\sigma(i)$ (now the leftmost point) and inserting it at position $i$. Likewise rather than start from the identity, we end at the identity.

Let $\sigma(i^*)$ be the right most element that is the beginning of an inversion, i.e., there exists $j>i^*$ with $\sigma(i^*)>\sigma(j)$ (if none exists then no moves are necessary because $\sigma$ is the identity permutation). For instance in 1 3 2 4 that would be 3 since it starts the inversion (3,2). And in 4 3 2 1 that would be 2.

Observation 1:  $\sigma(i^*+1)\sigma(i^*+2)\cdots \sigma(n)$ is sorted.

We must move all elements on the left side of $\sigma(i^*)$ to the right side of $\sigma(i^*)$. This is because we must correct the inversion and that can't happen until we perform a move with $\sigma(i^*)$ itself, which can't happen until $\sigma(i^*)$ is "uncovered" on the left side. While performing these hops over $\sigma(i^*)$ we can maintain the invariant that everything to the right of $\sigma(i^*)$ is sorted; this is just insertion into a sorted array.

So the number of moves necessary $= i^*$, since we hop everything to the left of $\sigma(i^*)$, and lastly move $\sigma(i^*)$ to its correct index.

Concluding note: to actually find the indices, we could use an order-statistic tree initialized with all values to the right of $\sigma(i^*)$. When we jump $\sigma(1)$ over $\sigma(i^*)$ we insert $\sigma(1)$ into the tree and call rank($\sigma(1)$); the rank can be used to compute the insertion index. Repeat with $\sigma(2), \ldots$.


Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$ How can I construct a PDA which accepts the language
$\{a^ib^j \mid 0 \leq j \leq 2i\}$?

The description of the PDA is easy:

  Read the input string. if read $b$ and the stack is empty, reject the string. If see $a$, push two $a$ to the stack. If read $b$, pop a value from the stack. Finally, if read the end of the string, it will be accepted.


Are there inherently ambiguous and deterministic context-free languages? Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.

Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous, and unambiguous otherwise.

An example of a deterministic, unambiguous language is the language: $$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$$
An example of a nondeterministic, unambiguous language is the language:
$$\{w \in \{a, b\}^{*} | w = w^{R}\}$$

From Wikipedia, an example of an inherently ambiguous context-free language is the following union of context-free languages, which must also be context-free:
$$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$$

Now for the questions:

Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
Is it known whether there exists a nondeterministic, inherently ambiguous context-free language? If so, is there an (easy) example?

Clearly, since an inherently ambiguous context-free language exists ($L$ is an example), the answer to one of these questions is easy, if it is known whether $L$ is deterministic or nondeterministic. I also assume that it's true that if there's a deterministic one, there's bound to be a nondeterministic one as well... but I've been surprised before. References are appreciated, and apologies in advance if this is a well-known, celebrated result (in which case, I'm completely unaware of it).

If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from Left to Right).

A language can be described by some context-free grammar if and only if it can be recognized by some nondeterministic automaton. As a special case of this, inherently ambiguous context-free grammars can be parsed by some nondeterministic automaton.

On a final note, any deterministic push-down automaton is also nondeterministic (this is the case for just about anything that can be nondeterministic, for a reasonable definition of nondeterminism).