How to Find the minimum permanent which is pumping lemma for language context-free? Suppose we have context-free language and we know the Context-Free-Grammar, how do i found the  minimum permanent which is pumping lemma for language ?

for example let sat i have this Grammar:
$$\begin{align}
S&\rightarrow AA\mid B\\
A&\rightarrow 0A\mid A0∣1\\
B&\rightarrow 00B0\mid 1\\
\end{align}$$
whats is the best way to find this Minimum permanent?

I presume by "permanent" you mean the integer of the Pumping Lemma, that is the integer $p>0$ such that for any string $s$ in the language with length $p$ or greater we can express $s=uvxyz$ with . . . [blah blah blah, I'm not going to write the statement here].
If you've read the proof of the PL, you know that it relies on guaranteeing that in a parse tree for a string of sufficient length, there will always be some path from the root to a leaf which contains a repeated variable. When that happens, we can replace the subtree rooted at the "lower" repeated variable with a copy of the subtree rooted at the "upper" repeated variable and have a parse tree for a new string also in the language: i.e., you've pumped the string.
For the grammar you've given, it is particularly easy to find the shortest strings in the language with a repeated variable in a path from the root to a leaf. Here are the trees for the shortest such strings:

There are two other of the right-hand form, but because of the way your grammar is formed, any string of length greater than or equal to 3 generated by the grammar must be formed by extending one of these two. In other words, the integer of the pumping lemma can be 3 or greater. It can't be 1 or 2, since while the strings $1$ and $11$ are in the language, there are no repeated variables in their parse trees (meaning they can't be pumped). Finally, then, the integer you want is 3.


algorithm complexity calculation T(n) = 2T(n/2) + n*log(n) I guess I lack at understanding basic things at algorithm calculations, while learning for an exam.

at the result, does one write like O(ld n) or just log instead of ld ?
regarding the following calculation (not from me) at the yellow mark - why is it Theta(n) ? why not O(n) ? I dont get it..

big thanks in advance !

Let's start at the beginning.

Basically, there are 3 very popular notations to express time complexity of algorithms:

$\Theta(g(n))$,
$\mathcal{O}(g(n))$ (this is the well-known Big O notation),
$\Omega(g(n))$.

The first thing that is in most cases a little bit confusing (and misused), that these notations denote sets - sets of functions. For example, the interpretation of $\Theta(g(n))$ is as follows:

$$\Theta(g(n)) = \{ f(n) \; | \; \text{There exist } n_0, c_1 \text{ and } c_2 \text{ constants so that } 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n > n_0. \}$$

So, $\Theta(g(n))$ is a set of $f(n)$ functions for that $g(n)$ can be used as both an upper and a lower bound (with the use of the given $c_1$ and $c_2$ constants). In other words, if you plot these 3 functions, $f(n)$ is going to be between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ - at least, for all inputs larger than or equal to $n_0$. (It's worth taking a look at figures about these in Google so that you can get a better understanding of it.)

Note: because of the use of $n_0$ and all larger inputs than it, these notations are also called asymptotic notations.

The interpretation of $\mathcal{O}(g(n))$ and $\Omega(g(n))$ are very similar to the one above, but they only refer to either the upper bound or the lower bound, respectively. (Of course, the existence of only one $c$ constant is enough for these 2 definitions.)

Just in case, see the definition of $\mathcal{O}(g(n))$ below:

$$\mathcal{O}(g(n)) = \{ f(n) \; | \; \text{There exist } n_0 \text{ and } c \text{ constants so that } 0 \leq f(n) \leq c \cdot g(n) \text{ for all } n > n_0. \}$$

In other words, $g(n)$ is an upper bound for all the functions in the set $\mathcal{O}(g(n))$. For example, let's denote the time complexity of the insertion sort with $T(n) = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2}$ (you can derive this easily if you think through the algorithm). Now, here $T(n) \in \mathcal{O}(n^2)$ means that the time complexity of the algorithm is quadratic - so if the size of the input is $n$ (we have an array to be sorted consisting of  $n$ elements), the algorithm must perform the most expensive operation at most $c \cdot n^2$ times (where $c$ might be 1). Three notes here:

Typically, we don't care about the "weaker" members of the equations, like $\frac{n}{2}$ in the example above, because of the asymptotic property I mentioned earlier (that wants to say something like "for large enough inputs always the strongest members will only count").
Typically, we only consider the most expensive operations of an algorithm, i.e., in the case of sorting algorithms, the number of comparisons.
Many times, people use the notations of $T(n) \in \mathcal{O}(g(n))$ and $T(n) = \mathcal{O}(g(n))$ like they were equivalent (basically, they aren't, but it's a common thing since the use of the latter can be advantageous as well).

So now, that hopefully we are done with the basics, you can see, that if a function $f(n) \in \Theta(g(n))$, it is also true that: $f(n) \in \mathcal{O}(g(n))$ and $f(n) \in \Omega(g(n))$ (in most textbooks, this is presented as a theorem with its proof, as well). In most cases, people don't care about the lower bounds of an algorithm's time complexity - so, it shouldn't really matter whether you see $\mathcal{O}$ or $\Theta$ (this would be the answer to your second question). I think that $\Omega$ is much less frequent than the other two.

I haven't ever seen the $ld$ notation you mentioned. However, I would prefer to use $\log_2$, it will be clear for anyone. Of course, you can use the one you would like to, but make sure to put them into either $\mathcal{O}$ or $\Theta$ (I can't recall a case when only the function was indicated).

Truly hope that I managed to provide a detailed answer you find useful enough. If you have any further question, please feel free to ask.


Problem understanding DFA & NFA equivalence in Theory of Computation Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction

but my question is a bit different from that. I was reading Michael Sipser's Introduction to Theory of Computation and I came to a problem. I couldn't understand as to how he is taking his act on equivalence between NFA and DFA.

I have problem understanding this para :-

  Next, we determine the start and accept states of D. The start state
  is E({1}), the set of states that are reachable from 1 by traveling
  along ε arrows, plus 1 itself. An ε arrow goes from 1 to 3, so E({1})
  = {1, 3}. The new accept states are those containing N4’s accept state; thus {1}, {1,2}, {1,3}, {1,2,3}.

My assumption---> As {2} is not in the list of accepted states,so {1,2} should not be considered as new accept state in equivalent DFA.Also,{1} and {1,2,3} and {1,3} stand out as new accept states as per me because traversing from 1 to reasonable nodes lets the final accept state be reached---here,{1},accept state--->{1,3}---accept state as on inputting a from node 3 makes arrive at {1} which is an accept state,hence accpeted,and similarly for {1,2,3}.

So,point at my wrong thinking PLEASE. I have understood that while making transitions only those states are considered final states which are accept states in NFA.Am I wrong???So,how come {1,2} be the new accept state in the equivalent DFA?

Secondly, why he has mentioned that

  The start state is E({1}), the set of states that are reachable from 1 by traveling
  along ε arrows, plus 1 itself`.

I couldn't derive a meaning out of this statement,the reason might be my poor understanding of English language(I am non-native English speaker).Means start state is E({1})---fine upto here. Now, the set of states that are reachable from 1 by travelling along ε arrows,plus 1 itself---It doesn't make any meaning standing as an independent sentence. Someone make me understand the meaning of this line,PLEASE!

Someone please make me understand and elaborate a bit. I feel that author might be wrong there,pardon my noobiness or for any mistake!

Motivation. In this construction, the intent is to make a DFA equivalent to a given NFA. In the original NFA, look at what happens when we're in state 2 and we see input $a$: we could either stay in state 2 or make a transition to state 3. If we want to eliminate nondeterminism, we could say that from state 2 looking at input $a$ we move to the single new state $\{2,3\}$, meaning that in this case, we're either in state 2 or state 3. In other words, in the constructed DFA we'll have the transition $\delta'(\{2\}, a)=\{2, 3\}$. The important thing to notice is that this transition in the new FA is deterministic: from the state $\{2\}$ on reading $a$ we move to the single state denoted by $\{2, 3\}$. Guided by this convention, we will build the DFA by defining the states to be all possible sets over 1, 2, 3, namely
$$
\emptyset, \{1\}, \{2\},\{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}
$$

Final States. Let's start with an example: what does the NFA do on input $baa$? We'll have, in order

In state 1, looking at $b$. Go to state 2.
In state 2, looking at $a$. Go to state 2 or state 3.
Looking at the last input, $a$ we could be in either state 2 or state 3. If we're in state 2, go to state 2 or state 3 as before. If we're in state 3, go to state 1.

In other words, at this stage, after having read $baa$ we could find ourself in states 2, 3, or 1.

In the DFA, we have, equivalently, the transitions $\delta'$ defined as

$\delta'(\{1\}, b) = \{2\}$.
$\delta'(\{2\},a) = \{2, 3\}$.
$\delta'(\{2, 3\}, a) = \delta'(\{2\},a)\cup\delta'(\{3\},a) = \{2, 3\}\cup\{1\}=\{1, 2, 3\}$.

Now the question is, should state $\{1, 2, 3\}$ be considered as a final state? Sure, since the NFA, reading $baa$ has at lest one possible collection of transitions that leads to the accepting state 1. In a similar way, any state of the DFA containing 1 will be a final state, so in the DFA there will be four final states:
$$
\{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\}
$$
Now it turns out that in the DFA the state $\{1,2\}$ is never used, but that doesn't negate the fact that it's a final state (since it contains 1). All it means is that there is no transition that takes you there. It's what we call an unreachable state. This, I hope, answers your first question.

Start State. This answer to your first question has little to do with the answer to your second question. The answer for your second question is: just as we did to determine the final states of $D$, we also need to know what the start state of $D$ is, and in this case it will be the set of states containing the start state of $N_4$, along with any other states that can be reached from that start state via $\epsilon$-moves, namely $\{1, 3\}$ (which of course will also be a final state, though that's not important here).


How to use Latin hypercube sampling with fixed points? I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points.

I thought about taking the min distance between the points, and if I have an already evaluated point that is near on LHS point, I remove the LHS to minimize the number of evaluations.
Sadly this is not how LHS works, and the results are not very good.

You've divided the x values into 10 columns, and divided the y values into 10 rows, so we have a 10x10 grid.

Take any row that is already covered by some already evaluated point, and remove it from the set of rows.  Do the same with the columns.  In your picture, we are left with 6 rows and 6 columns.  Consider the 6x6 grid obtained by looking only at those 6 rows and 6 columns.

Now use your Latin hypercube sampling strategy on a 6x6 grid, to cover each of those 6 rows and each of those 6 columns.  This gives you 6 points that cover the 6x6 grid.  Now this can be interpreted as 6 points in the 10x10 grid, and if you combine those 6 points with the 4 existing points, you'll see that the result covers every row and every column exactly once.


Dijkstra's algorithm to compute shortest paths using k edges? I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ edges. Assuming we have no negative edge weights at all, can we use Dijkstra's algorithm for the same?

My thoughts/algorithm:
I was wondering if instead of having a $dist[u$] array (storing the best known distance from s to u), we could use a $dist[u][k]$ table to store the best known distance from $s$ to $u$ using at most $k$ edges (dynamic programming maybe?), and similarly have the priority queue with $(u,n)$ tuples as keys. We can then terminate the algorithm when the tuple popped off the priority queue is $(t,n)$ where t is the target destination and $n <= k$?

If the graph has no negative edges, the problem can be solved in $O(k \cdot (|V|+|E|) \lg |E|)$ time using Dijkstra's algorithm combined with a product construction.  We construct a new graph $G'=(V',E')$ with vertex set $V' = V \times \{0,1,2,\dots,k\}$ and edge set

$$E' = \{((v,i), (w,i+1)) : (v, w) \in E\}.$$

In other words, for each edge $v \to w$ in $G$, we have edge $(v,i) \to (w,i+1)$ for all $i$ in $G'$.

Now use Dijkstra's algorithm to find the shortest path in $G'$ from $(s,0)$ to a vertex of the form $(t,i)$ where $i \le k$.  This will be the shortest path in $G$ that uses at most $k$ edges.


Is there a name for the problem of spatially organizing a graph as to minimize total edge length? The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined length of all lines (edges) is the minimal.

I want to know if that problem has a name, and how complex it is. I also would like to know if this problem is easier if done incrementally (i.e., starting with an empty graph and adding/removing nodes as to maintain that property).

This is a version of graph drawing, restricted to vertices being on a grid, but allowing more than two dimensions.  The one-dimensional case is an example of a graph layout problem, known as Minimum Linear Arrangement. In all of these problems, one is interested in minimizing some metric of the resulting diagram, which could be the number of edge crossings or, in your case, the total length of the edges.

These kinds of problem are very often NP-hard, even in the one-dimensional case: in particular Minimum Linear Arrangement, the 1D version of your problem, is NP-hard. There's a survey of graph layout problems by Díaz, Petit and Serna (ACM Surveys, 34:313–356, 2002; .ps.gz).


Is $O(|V||E|)$ polynomial time? If an algorithm runs in $O(|V||E|)$, is its running time bounded by some polynomial of $|V|+|E|$? If not, what is its running time called?

Since $(a+b)^2 = a^2 + 2ab + b^2 \geq 2ab$, it is indeed true that $|V||E|$ is bounded by a polynomial in $|V|+|E|$.


Maximum length path between any two nodes in a tree with possible negative edge weights Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)

You can find this path in linear time:

If the tree is unrooted, pick an arbitrary node as root.
Traverse the tree in postorder and for each node:

2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.


How can we assume that basic operations on numbers take constant time? Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$.  For example, we assume this when we say that comparison-based sorting is $O(n\log n)$, but when numbers are too big to fit into registers, we normally represent them as arrays so basic operations require extra calculations per element.

Is there a proof showing that comparison of two numbers (or other primitive arithmetic functions) can be done in $O(1)$? If not why are we saying that comparison based sorting is $O(n\log n)$?

I encountered this problem when I answered a SO question and I realized that my algorithm is not $O(n)$ because sooner or later I should deal with big-int, also it wasn't pseudo polynomial time algorithm, it was $P$.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM.  The model is intended to reflect the behavior of real computers more accurately than the Turing machine model.  Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size.  Each memory address holds a single $w$-bit integer, or word.  In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words.  Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model.  To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word.   Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input.  Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case.  One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model.  But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model.  The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly.  If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.


MILP problem NP-hard proof Since a MILP problem is not necessarily NP hard. How could I demonstrate that a  MILP problem is actually NP hard? There exists some smart and easy method to do that?
Many thanks!

In general, a general MILP was proved to be NP-Hard. This is a well-known proof and can be easily found in any textbook (or even on Wikipedia).
However, you can see one specific MILP problem as an 'instance' of the general MILP problem. Thus, you still need to show its complexity.

In fact, several MILP problems are NP-Hard:

Elementary Shortest Path (if the graph has negative cycles)
Degree-constrained Minimum Spanning Tree
Vehicle Routing Problem

However, many others are shown to be solvable in polynomial-time:

Job scheduling
Minimum Spanning Tree
Aircraft scheduling problem

You can demonstrate that a MILP problem is NP-Hard in the same way you do with any other optimization problem.

All you need to do is to reduce an NP-Hard optimization problem $\sigma$ to your MILP, construct a solution for MILP, and shows a polynomial-time transformation of your obtained solution to a solution of $\sigma$.

Sadly, there is no standard technique or proof method that can be applied to show the complexity of any MILP problems and you need to use your creativity (and mathematical skills, in many cases) to proof the complexity of your problem.


Count the number of integers satisfying two conditions using DP Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in the integer is at most $m$?

The integer cannot start with a $0$. All digits from $0$ to $n-1$ must be present.

Example: for $n = 3$ and $m = 6$ there are $18$ such numbers ($210, 2101, 21012, 210121 \ldots$)

I know there is a dynamic programming method to solve this. After looking the solution, I am not able to understand it. Can anybody please give any good solution to me?

Hint: The table consists of cells $T(S,d,\ell)$, which count numbers of length $\ell$ in which the last digit is $d$ and the set of digits is $S$. Unfortunately this solution is exponential in $n$.


Difference between page table and inverted page table I do not understand the difference between page table and inverted page table.
I know that both are used to translate the logical addresses into physical addresses produced by the processes necessary to store data in memory.

This is what I know on the page table.

Generally each page table contains an element for each virtual page and a table exists for each process.
This can lead to huge tables (programs with many pages).

I can imagine a page table like this:

Instead, this is what I know on the inverted page table.

It has only one page table for all processes.
This table has an entry for each real page (block of physical memory).
Each element contains the virtual address of the page stored in that physical location, with information about the process that owns that page.

So I represent the inverted page table like this:

Am I doing it right? Did I get it right?

Thank you

I don't understand if the information I have learned theoretically then I understood well.

I do not think that is more efficient an interved page table than a normal page table, indeed I find it most confusing.

As I understand it, each frame of the physical memory has a corresponding entry in the inverted page table.
I suppose that the memory has a large number of frames, then the inverted page table is huge and how do I keep it in RAM?
While if you use the page tables "normal", I do not keep all of them in memory at the same time, you just keep those of the currently active processes, or not?

And it is reversed (the arrows are reversed), as I map a logical address into a physical?

An inverted page table is just a hash map.  An inverted page table always fits in DRAM because it is proportional in size to the DRAM.

A DRAM total space is divided into $N$ page frames. If the size of a page frame is 4096 bytes, then the DRAM is of size 4096 $N$ bytes.
Assuming that an inverted page table entry is 16 bytes, and considering that there is an entry for each physical memory frame, then the page table is of size 16 $N$. This corresponds to 16/4096 = 1/256 $\approx$ 0.4% of the memory.

Your picture of the inverted page table is not correct.  Here is the picture from the original paper about inverted page tables (Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993. doi:10.1145/165123.165128.)

It's a hash table.  Each entry of the hash table needs to store both a virtual address and a physical address.  The virtual address is there to check for hash conflicts.

The reason you can guarantee the total number of entries for the HPT (hash page table) plus the collision resolution table is just $N$ (the number of physical pages), is that there can be only one entry in the tables for each physical page.


Incorrect Answer Trying to Find Hamming Distance A 010101
B 110011
C 111000
D 000111

The minimum Hamming distance of those code words is 3 as the minimum difference is 3 but the correct answer is 2.

How can I find the correct Hamming distance?

A 010101
D 000111

There are two bits different (namely the bold ones). So the hamming distance is 2.


Counterexample for simple parity automaton reduction I am dealing with deterministic parity automata and state space reduction (not minimization).

If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those states the automaton recognizes the same $\omega$-language, merging those states is in general not an operation that preserves language. The canonical example is a parity automaton with two states $q_a, q_b$ that moves to $q_a$ whenever reading an $a$ and to $q_b$ whenever reading a $b$. Giving both states a different parity yields a counter example.

Now what if we refine this relation so that $p \sim q$ is true iff $p \equiv_L q$ and in addition the two states have to have the same color assigned to them. I feel like there has to be a counter example but I can't think of one. That is my question; what is a simple counter example that shows that merging states like this can alter the langauge?

(in case it is not clear what I mean by "merging": merging $p$ and $q$ means removing $q$ from the automaton and redirecting all transitions that would move into $q$ to target $p$ instead)

After some thought, I found a counter example. It has four states and there might be one with only three states, but this one works too.

States 1, 2, and 3 are language equivalent. 1 and 3 also have the same color, so they can be merged. If we merge 3 into 1, this is the result:

In the original automaton, $(aab)^\omega$ has the run $(103)^\omega$ which only sees color 1. In the reduced automaton, $(aab)^\omega$ has the run $101(201)^\omega$, which also visits color 0 infinitely often.


Why are sensors transducers when analogue-to-digital-converters (ADC) do the actual conversion? As sensors only sense continuous quantities whereas an ADC is a device which actually converts one form of input to another.

A sensor is a kind of transducer that converts physical quantity like temp or pressure into electrical signal (voltage, current or charge). ADC converts the electrical signal generated from sensors to an equivalent binary code,  that can be then processed by a logic processor (microcontroller, DSP, FPGA ...).


Operating Systems TestAndSet instruction I was reading operating systems concurrency control topics where I came across TestAndSet() intruction. I first referred this book. But it has got very less coverage on TestAndSet and then I googled. Obviously I came across wiki page.

The wikipedia page gives two code excerpts.

The TestAndSet() function

#define LOCKED 1

int TestAndSet(int* lockPtr)
{
   int oldValue;
   oldValue = *lockPtr;
   *lockPtr = LOCKED;
   return oldValue;
}

Lock() built using TestAndSet()

function Lock(boolean *lock)
{
   while (test_and_set(lock) == 1);
}

I have two doubts:

It seems that the TestAndSet() does not actually have test, it does contain only set part and Lock() contains the set part. Is it like that?
Below first excerpt, wikipedia page days:

  The code also shows that TestAndSet is really two operations: an atomic read-modify-write and a test. Only the read-modify-write needs to be atomic. (This is true because delaying the value comparison itself by any amount of time will not change the result of the test, once the value to test has been obtained. Once the code writes the initial value, the result of the test has been determined, even if it has not been computed yet)

Does that mean we can call TestAnsSet() inside Lock(), save its return value and test against that return value anytime inside Lock()?

You are right, TestAndSet doesn't test the value of the flag, it merely sets it, but returns the previous value, which must be tested elsewhere.

The trick is that as the assignment is atomic, only one process can cause a transition from 0 to 1 (others only cause a "transition" from 1 to 1), and only it can pass the while.


Is the image of a total, non-decreasing function decidable? This is an exercise I've been struggling with for a while:

  Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of $g$ a recursive set?

Intuitively, I know that the image $I_{g}$ is not recursive, as $g$ is not strictly monotonic. In fact, it's because that $g$ is not strictly monotonic that $g$ could be a constant function so testing if $y \in I_{g}$  may not finish as it could be that $\forall x, g(x) = c$, $c$ being a constant s.t. $c < y$. Then, testing if there is an $x$ s.t. $g(x) = y$ incrementing $x$ as the $g(x) < y$ may go forever.  On the other hand, it could be that after a while, (for a sufficiently greater $x$) it happens that $g(x) > c$ and $g(x) = y$. If it were stricly monotonic, though, then it would be recursive as I would be able to test if $y = g(x)$ incrementing $x$ until the equality is satisfied or $g(x) > y$ (then $g(x)$ wouldn't get stuck in the same value because $x_1 > x_2$ implies $g(x_1) > g(x_2)$).

However, I haven't been able to prove this formally. Can this intuition become part of a formal proof? Or at least could you give me some help in proving it in some other way? A hint or some outline of a proof would be great.

I am assuming in my answer that $g$ is to be taken as computable, given the comments in the question. For non-computable $g$ see David's answer.

There are two answers:

There is no uniform decision procedure for membership in the image of a non-decreasing function. For suppose we had a decision procedure $P$ which would decide whether $n \in I_g$ on input $\langle\ulcorner g \urcorner, n\rangle$. (Here $\langle\ulcorner g \urcorner$ is a suitable encoding of the Turing machine that computes $g$.) Then we could implement the Halting oracle as follows. Given a Turing machine $T$ let $g$ be
$$g(n) = \begin{cases}
1 & \text{if $T$ halts in $\leq n$ steps}\\
0 & \text{if $T$ does not halt in $\leq n$ steps}\\
\end{cases}
$$
Clearly, $g$ is a monotone map and so we would have
$$\text{$T$ halts} \iff P(\langle\ulcorner g \urcorner, 1\rangle).$$
For each such $g$ its image is decidable, but non-uniformly in $g$. (This means my proof will somewhere make a non-computable step.) Consider any non-decreasing $g$. Then either $I_g$ is finite or $I_g$ is infinite (that was the non-computable step):

if $I_g$ is finite then it is recursive
if $I_g$ is infinite then we can use the usual trick: given and $n$, enumerate the values $g(0), g(1), g(2), \ldots$ and wait until they get larger than $n$, which they will as $I_g$ is infinite. Once they do, see whether $n$ has been enumerated.


Relations among different boolean approximations Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p_{0,\epsilon}$ be the minimum degree (of degree $d_{0,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree (of degree $d_{1,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$?

Above holds if $\epsilon\in(0,\frac{1}{2})$ as mentioned here in link Different boolean degrees polynomially related?.

However what happens if $\epsilon\in(0,1)$ instead of $(0,\frac{1}{2})$ (does polynomial relation still hold)?

That is we consider $0<\epsilon<\frac{1}{2}\leq\delta<1$.

Note that defining $p_\delta$ makes little sense if $\delta\in[\frac{1}{2},1)$.

I am most interested in $\delta=1-\frac{1}{h(n)}$ with some function of $n$ (logarithmic/polynomial/exponential).

The new parameters are polynomially related to the old parameters. In fact, for every $0<\delta,\epsilon<1$ it is the case that $d_{0,f,\epsilon} = \Theta_{\delta,\epsilon}(d_{0,f,\delta})$. This is proved in the same way that the usual relation regarding $d_{f,\epsilon}$ is proved, as detailed below.

Suppose we are given $0<\delta,\epsilon<1$. Let $g$ be some continuous function satisfying $g(0) = 0$ and $g(x) = 1$ for $1-\delta \leq x \leq 1+\delta$. The Weierstrass approximation theorem shows that there is some polynomial $G$ such that $|G(0)| \leq \epsilon/2$ and $|G(x)-1| \leq \epsilon/2$ for all $1-\delta \leq x \leq 1+\delta$. Let $G_0(x) = G(x) - G(0)$, so that $G_0(0) = 0$ and $|G_0(x)-1| \leq \epsilon$ for all $1-\delta \leq x \leq 1+\delta$. The polynomial $P = G_0(p_{0,\delta})$ has degree $(\deg G_0)d_{0,f,\delta}$ and satisfies $P(x) = 0$ whenever $f(x) = 0$, and $|P(x)-1| \leq \epsilon$ whenever $f(x) = 1$. This shows that $d_{0,f,\epsilon} \leq (\deg G_0) d_{0,f,\delta}$. Since $G_0$ only depends on $\delta,\epsilon$, this proves that $d_{0,f,\epsilon} = O_{\delta,\epsilon}(d_{0,f,\delta})$.


what is the difference between memory access and data memory access? what is the difference between memory access and data memory access?

for example, here are the examples of register transfer language instructions:

     $R1 ←[18]$
     $R2 ←[R1 +3]$
     $R1 ← R1 +2$
     $[8] ← R1$

From my understanding, memory access is where load/store occurs, like these instructions $R1 ←[18]$$R2 ←[R1 +3]$$[8] ←R1$

But what about data memory access? what is it?

thanks!

A memory access happens when the CPU loads bits from main memory or stores bits to main memory. The CPU will first check to see if it can load the bits from a cache, in which case it will skip the (slow) memory access entirely.

One kind of memory access is a data memory address, when the CPU runs an instruction that explicitly loads or stores data from/to memory. In your examples, the arrows request data memory accesses (or cache accesses). "Data" is a very general term but here it means the bits that the program is operating on, as distinct from the bits that convey the program itself.

Another kind of memory access is an instruction fetch, which happens when the program counter gets a new value as part of running the instructions in the program. It usually just steps forward but a branch instruction can jump to a new location. Either way, no memory access is needed when the instructions are already cached.

In your example, the sequence of register/memory instructions have to load into the CPU before it can execute them. That requires instruction fetches.

(A Harvard architecture CPU has one bus to/from data memory and a second bus to/from instruction memory, so it can fetch from both in parallel. In that case the distinction between an instruction fetch and a data fetch is starker.)

The instructions themselves had to get into memory somehow. An interpreter or loader put them there, treating those instructions as data.

The distinction is whether the data is loading by the explicit request of the program instructions vs. the implicit need to load instructions themselves. The former are easier to cost out. The latter costs depend on the size of the instruction caches, on interruptions taken that might spill this program's instructions from the cache, etc.


Is this language recognizable? Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable.

I don't think it's even recognizable, but I'm not sure. Regardless, I think I can show it's undecidable. Suppose $L$ is decidable by machine $D$. Then we can construct machine $S$ that decides the accepting problem, i.e. $\mathrm{ACC} = \{(M,w): M\text{ accepts }w\}$, which is undecidable.

For $S$ on input $(M,w)$, construct machine $M'$ with input $x$ such that if $x \neq 1100$, then loop, and if $x = 1100$, run $M$ on $w$. If $M$ accepts, then $M'$ halts. Next, run machine $D$ on $M'$. If $M'$ halts, then $D$ accepts. Otherwise, $D$ rejects.

So, if $M$ accepts $w$, then $x=1100$ and $M'$ halts, so $D$ accepts. On the other hand, if $M$ does not accept $w$, then $M'$ loops (and does not accept anything), and $D$ rejects. But then $D$ decides $\mathrm{ACC}$, which is undecidable. Hence, $L$ is undecidable.

Am I on the right track?

To show that $L$ is not recognizable, you can reduce the complement of the halting problem to it. $\overline{\mathrm{HALT}}$ is not recognizable because, if a language and its complement are both recognizable, then they're both decidable, and we know that $\mathrm{HALT}$ isn't recursive.

Given a Turing machine $M$ and input $w$, you want to accept iff $M(w)$ loops. So construct the machine $M'$ which halts if its input is $1100$ and simulates $M(w)$, otherwise. If $M'\in L$, then $M'$ cannot halt on $0011$ or $1000$,* which means that $M(w)$ doesn't halt.

* It seems there's a typo in the question, which mentions $0011$ twice. Obviously, this doesn't make any real difference.


Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.

I know this is refutation, but I could not find a good example of refutation.
I would be happy if you would help me.

Consider the following graph. The min-cut is $[s][a,b,c,d,t]$ with value 3. After the weights of all edges are increased by 1, the min-cut becomes $[s,a,b,c,d][t]$ with value 5.

It does not matter whether you are considering cuts with terminals or without terminals (if with terminals, the terminals are $s$ and $t$).


What is this algorithm? Create a tree's equivalent hierarchical network This question was originally posted here: https://stackoverflow.com/q/20735339/2305618

I am surely not the first to have implemented code to perform the following graph transformation. But try as I might, I can't find a previous reference to it.

The transformation arises when creating a single graph that simultaneously models hierarchical inclusion relationships and other pairwise relationships between nodes.

The algorithm transforms a rooted directed tree DAG into an equivalent hierarchical network DAG. Equivalence in this sense - if the meaning of the tree structure is that parents 'consist of' or 'contain' their children the equivalent network structure would carry the same 'consisting of' or 'containment' information.

The tree hierarchy is represented in the network as sub-networks and sub-sub-networks. The tree's exterior nodes are copied across and each interior node X is represented by the pair: X' and X''

Does anyone know the name/reference of this transformation/ algorithm? :-)

Illustration image of this transformation:

Thanks

David

Your question contains the implicit assumption/premise that this transformation has a name.  I don't know why you would expect it to have a special name.  The transformation is not anything special or complicated and as far as I know it does not have any special name.  It appears that you are just taking a tree, and making a second copy of it (with all edges reversed; with all nodes cloned), and then just gluing the two copies together (identifying both copies of each leaf).

For future reference, I don't think questions like "please tell me if this function has a special name" are a good fit for this site.  This site is for technical questions that admit an objectively evaluable answer and that relate to a real problem you have.  How do you expect to evaluate an answer that says "No, it doesn't have a special name"?  There is no reference one can cite to back up that answer, and no objectively verifiable evidence one can provide to support such an answer.  Moreover, questions about naming aren't a very good fit.  How will knowing whether there is a special name help  you solve a real problem?  (If you were thinking "it might help me find references that help me solve problem X", then you would be better off by just describing problem X.)


Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, what word should I choose? Or should I use closure-properties and if so what irregularity should I show? I am genuinely so confused. Any help is appreciated.

Let $L = \{0^i1^j : i \neq j\}$. You can prove that $L$ is not regular in many ways. Here are some examples.

Closure properties

If your language were regular then so would $0^*1^* \setminus L$ be, but that language is $\{0^n1^n : n \in \mathbb N\}$, which presumably you already know isn't regular.

Myhill–Nerode

The words $\{0^i : i \in \mathbb N\}$ are pairwise distinguishable modulo $L$: if $i \neq j$, then $0^i1^i \notin L$ but $0^j1^i \in L$. It follows that $L$ isn't regular.

Pumping lemma

If $L$ is regular then it satisfies the pumping lemma, say with constant $n$. Consider the word $w = 0^n 1^{n+n!} \in L$. According to the pumping lemma, there should be a decomposition $w = xyz$ such that $|xy| \leq n$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \in \mathbb N$. Let $|y| = \ell$, so that $y = 0^\ell$. Pick $i = 1 + n!/\ell$. Then $xy^iz = 0^{n+n!} 1^{n+n!} \notin L$, contradicting the pumping lemma.


De morgan's law in formal language I found in some exercise in computation the following step:

I can't understand why is it equal terms, based of what I know about De morgan's law:

OR should be replaced by AND
where $w=\varepsilon$ come from

Let $\Sigma$ be the alphabet on which $A_{TM}$ is defined over, and assume w.l.o.g that:

$A_{TM}\cup \overline{A_{TM}} = \Sigma^*$, and
$0, 1 \notin\Sigma.$

The set $J$ can be written as:
$$
J = \{0\}\cdot A_{TM} \ \cup \{1\}\cdot \overline{A_{TM}}
$$
where $J$ is defined over the alphabet $\Sigma \cup \{ 0, 1\}$.
Now, using De morgan's law, it holds that:
$$
\overline{J} = \overline{\{0\}\cdot A_{TM}} \ \ \cap \overline{\{1\}\cdot \overline{A_{TM}} } \\
$$
$$
=\left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^*\right) \ \cap \\
\left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right) \\
$$
$$ = \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \left[\{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^* \right] \cap \left[ \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right] \right)
$$
$$
= \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \{ 0\}\cdot \overline{A_{TM}} \cup \{ 1\}\cdot A_{TM} \right)
$$
So, we have that $w \in \overline{J}$ iff $w$ does not encode a bit followed by a word of the form $\langle M, w \rangle$, or $w = 1x$ for some $x \in A_{TM}$ or $w = 0y$ for some $y \in \overline{A_{TM}}$.
Finally, note that they're implicitly assuming w.l.o.g that every nonempty word in $\{0, 1\}\cup \Sigma^*$ is of the form "$\text{bit} \cdot \langle M, w\rangle$". This assumption is okay, as checking whether a word respects some encoding can be easily done by a TM.


Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm.

Here is my solution:

If we denote $^t A$ the transpose of the finite automaton then in order to see if $A$ accepts a palindrome we need to look at the product automaton of $A$ and $^t A$ and find if this product automaton accepts a word. If yes then this is word is a palindrome.

Finding the transpose of a finite automaton takes $O(|V|)$ where $V$ is the number of transition of our finite automaton. Take the product of $A$ and its transpose takes $O(|V|^2)$. And looking if an automaton accept a word takes $O(|V|^{|S|})$, where $|S|$ is the number of states of our finite automaton. So the final complexity I get for the algorithm I described above is:
$$O(|V|^{3 + 2|S|})$$

Now my question is:

Is it possible to improve the complexity? And is it possible to give a proof (using I guess adversary argument) to prove that there isn't a better algorithm (in the sense of complexity) to find if a finite automaton accepts a palindrome?

You can solve this in $O(n^2)$, where $n$ is the number of states in the original DFA (or NFA), using your idea. Compute the product automaton of the original automaton and its reverse. The new automaton contains $O(n^2)$ states. As to the number of edges, in the original DFA, each state has $|\Sigma|$ outgoing edges, and in its reverse, there are $|\Sigma|n$ transitions overall. Let us denote by $a(q)$ the number of outgoing transitions from $q$ in the original DFA, and by $b(q)$ the number in the reverse DFA. Using $Q$ for the set of states, the total number of transitions in the product automaton is
$$
\sum_{q_1,q_2 \in Q} a(q_1) b(q_2) =
\sum_{q_1,q_2 \in Q} |\Sigma| b(q_2) =
|\Sigma| n \sum_{q_2 \in Q} b(q_2) =
|\Sigma|^2 n^2.
$$
Assuming $|\Sigma|$ is constant, this is $O(n^2)$.
Now check whether some final state is reachable from some initial state, using BFS/DFS, in  time $O(n^2)$.

We can prove an essentially matching lower bound given SETH. Recall that SETH states that for every $\epsilon > 0$ there is $k$ such that $k$-SAT cannot be solved in time $O(2^{(1-\epsilon) n})$, where $n$ is the number of variables. We will show how to reduce $k$-SAT to your problem.

Given a $k$-SAT formula $\phi$ with $n$ variables and $m = O(n^k)$ clauses, consider the following language $L$ of all words of the form $\alpha x \beta \gamma y \delta$, where:

$|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$, $|x| = |y| = m$.
We think of $\alpha$ as an assignment for the first $n/2$ variables. If $x_i = 0$ then $\alpha$ must satisfy the $i$th clause.
We think of $\beta$ as an assignment for the last $n/2$ variables. If $y^R_i = y_{m+1-i} = 1$ then $\beta$ must satisfy the $i$th clause.

Any word in $L \cap L^R$ must be of the form $\alpha x \beta \beta^R x^R \alpha^R$, and so by construction $\alpha\beta$ satisfies $\phi$. Conversely, if $\alpha\beta$ satisfies $\phi$, then we can choose $x$ so that the corresponding word is in $L \cap L^R$, Hence $\phi$ is satisfiable iff $L \cap L^R$ is non-empty.

How many states do we need to accept $L$? We can read and store $\alpha$ using $O(2^{n/2})$ many states. Therefore using $O(2^{n/2} m)$ states, we can verify the second condition (on $\alpha x$). Similarly, we can verify the third condition (on $\beta y$) using $O(2^{n/2} m)$ more states. Verifying the first condition takes $O(n+m)$ more states, for a grand total of $O(2^{n/2} m) = O(2^{n/2 + o(1)})$ states.

If your problem could be solve in time $O(N^{2-\delta})$ (where $N$ is the number of states in the input automaton), then we would get an algorithm for $k$-SAT running in time $O(2^{(1-\delta/2)n + o(1)})$, and so obtain a contradiction if $\delta/2 \geq \epsilon$. This shows that assuming SETH, your problem cannot be solved in $O(N^{2-\delta)}$ for any $\delta > 0$.


Subset Sum for {1,...,n} In general, the subset sum problem is NP-Complete. However, what if we say that our set is $\{1,...,n\}$? Is there a formula/combinatorial calculation that says how many subsets of $\{1,...,n\}$ have their sum equal to $k$?

This is A053632. The prefixes of this sequence convergence to the more well-known A000009, the number of partitions into distinct (or odd) parts. You shouldn't expect a clean formula, though it's of course easy to calculate small terms using dynamic programming.


What is the number of degrees of freedom of my problem in this Simulated Annealing context? I'm trying to apply a Simulated Annealing technique to solve my (NP-complete) optimization problem. I'm using this book to help myself out.

In the section on Simulated Annealing and more specifically in the section on practical suggestions for beginners, the authors state:

  Change in temperature stage: can take place as soon as one of the 2 following conditions is satisfied during the temperature stages:
  - $ 12 \cdot N$ pertubations accepted;
  - $ 100 \cdot N$ pertubations attempted,
  $N$ indicating the number of degrees of freedom (or parameters) of the problem

Because I'm still relatively new to Simulated Annealing, I'm willing to trust this guideline blindly for a first implementation.

A (non-optimal) solution to the problem is represented by a vector of integers $\mathbf{[a_1, a_2, a_3, ..., a_n]}$ with $ 0 < a_i \leq f(i), \forall i \in \mathbb{N} : 0 < i \leq n$.

What is the degree of freedom ($N$) here? Is it $n$?

Additionally, for this not to be a yes/no question:
Intuitively, why is this a bad/mediocre/good (pick one) guideline  ?
(i.e. why $\underline{12} \cdot N$ and $\underline{100} \cdot N$?)

The parameter $N$ is the length of the vector you're running simulated annealing on. In your case, $N = n$. The values $12,100$ are completely heuristic, and were probably chosen experimentally.


Calculating the structural integrity of a pixel grid Preface
So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been reached.
I know Medieval Engineers and 7 Days to Die implemented something along these lines, though I would like to see if I can solve this (with some help) before ripping someone's implementation.
Of course links to more examples are appreciated.
Problem
In a 2D grid of constant size, there exists an anchor which all pixels/nodes must connect to. For example the bottom row will act as the "ground" and anchor all nodes. Finding unanchored nodes is easy, so assume all nodes are anchored.
Each node/pixel will have a mass, for simplification, this will be "1 block" of mass.
From there we need to find how much load each node is under (i.e. the amount of mass the node is supporting), and therefore how much "stress".
In this problem load and stress are the same.
My Implementation
For every node:

Split the mass of a block based on its valid connections i.e. paths that are not a dead end.
The fraction of mass on the neighbor node represents the fraction of weight of the source node it supports.
Repeatedly traverse splitting the mass until you get every path to an anchor node.

You should end up with a total number on each node representing how much "mass" it is supporting.
Example:

Mass distribution of one node
Each color represents the initial path from the source node/pixel for clarity.
The source mass is divided into three since the bottom path (in this example one block) cannot reach the anchor without going back on itself.
From this we can see the node with the most stress from the source node is D2, with the runner-up being C2. B3 is not affected by the source because it is not supporting it.
Of course there are limitations with this solution:

Bad time complexity
Scales poorly with #nodes
adding or removing one node is expensive

My solution involves finding every path from source to anchor for every block, which is bad.
I made a (very slow) example below, where the bottom of the grid is the anchor.
[Codepen Example]
Question:
How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?

So I found a solution using maximum flow algorithm with some tradeoffs.
The setup involves:

Connecting the source node to every node in the grid with an edge capacity equal to the nodes mass.
Connecting the sink to the bottom layer
Connecting every node in the grid to each other with some capacity defined by the node (i.e. the maximum stress/load from that direction)

After Dinic Max Flow algorithm runs, I traverse the residual graph starting at nodes which do not get the maximum flow from the source (i.e. nodes that can't apply their full mass) and find all nodes which have an edge with max capacity.
[CodePen Example]
Example configuration:

So the algorithm works much faster than mine, and that is because it does not spread mass evenly. As shown above the white squares are nodes which have edges with maximum flow. This does not necessarily mean that the node is overloaded, and as you can see there are alternative flows that are not at full capacity.
However since my goal was to simply find the overloaded nodes and destroy them (and floating parts) this does not matter so much.


Error-correction code for transmission only with bit-flipping from 0 to 1 I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system.

For each bit [0,31], I add its index to the Bloom filter if the corresponding bit is set. The Bloom filter is then transmitted without error and the recipient tests the Bloom filter for each index [0,31] to reconstruct the 32 bits of data.

One problem is that the Bloom filter can have false positives, making it look like some bits are set when they shouldn't be. Another problem is that the Bloom filter may already have other entries in it, further making it look like more bits are set.

I wondered if error-correction codes could help here. The general idea would be to add more bits ([32,35] for example) the recipient could use to figure out the original 32 bits despite Bloom filter collisions.

After a little research I learned that Z-channels (or binary asymmetric channels) flip bits in one direction. Also I found that linear error-correction codes for Z-channels are often applicable to symmetric channels as well. So to exploit the asymmetry, the codes likely need to be non-linear. More info on the state of the art is appreciated (hoping for a simple algorithm...).

This is not possible.  There's no free lunch. You are looking for a compression scheme that is guaranteed to compress 32 bits down to less than 32 bits.  That's not possible in general, unless you have prior knowledge that lets you rule out some of the possible 32-bit values.

In particular, if you want to send 32 bits of information, and all $2^{32}$ possibilities are equally likely, and errors are not allowed, you'll have to send at least 32 bits over the communication channel.  This is a basic theorem of information theory.  No amount of error-correcting codes will get you past this.

If you want to avoid this, you'll either need prior knowledge on the 32-bit value (e.g., to rule out some as impossible, or less likely than others), or you'll need to accept lossy compression (where the recipient's received string might not exactly match what the sender wanted to send).


Transitions between lexicographical orders I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ lexicographically and each sequence will have unique number $1 \dots catalan(n)*3^n$. Than I want to get sequence by its number.
Problem: If I have another order, for example '}' < '[' < ')' < '(' < '{' < ']', then all balanced parenthesis sequences again are stored in lexicographical order, but the same sequences will have different numbers, according to these two orders. If I'm given a number of a sequence in second order, can I efficiently recalculate it to the number of the same sequence but in the first order? The main problem is that I don't know the sequence which corresponds to given number in second order. (I wish to find it)
Example: First order: '(' < ')' < '[' < ']' < '{' < '}'
Second order: '}' < '[' < ')' < '(' < '{' < ']'
I get number 1 for sequences with 1 pair of parthenses, the corresponding sequence is [] in the second order. I want to calculate number of [] in first order --- it is 2.
But I don't know how sequence for number 1 in seconds order looks like. I want just by number get the number of the same sequence in first "canonical" order.

Aside from trivial cases, transforming lexicographic order indices from one ordering to another ordering can can rarely be done more efficiently than unranking the index using the original alphabet ordering, and then ranking the resulting sequence using the new alphabet ordering.
That works fine in this case, because after precomputation of a table of size $O(N^2)$ (which doesn't depend on the chosen ordering), you can rank and unrank an element of the lexicographic sequence with an arbitrary lexical ordering in $O(N)$ time. (The naïve proof-of-concept code I wrote does the ranking and unranking in $O(Nk)$ time, where $k$ is the size of the bracketing algorithm. But it should be possible to get rid of the $k$.)
The algorithm can be found in Ranking and unranking of a generalized Dyck language and the application to the generation of random trees, Jens Liebehenschel (1999). Liebehenschel's algorithm uses a fixed ordering but extending it to arbitrary orderings is straight-forward.
Liebehenschel's generalisation of Dyck languages allows the use of an arbitrary many-to-many relation between opening and closing symbols (although it requires that the set of opening symbols and the set of closing symbols not have common elements). Restricting the relationship to an isomorphism doesn't significantly simplify the algorithm.


Question about DFA for exact string matching In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as:

for

q in Q (q is a prefix of x)
a in $\Sigma$
(q, a, qa) is in E if and only if qa is also a prefix of x
otherwise (q, a, p) is in E such that p is the longest suffix of qa which is a prefix of x.

I'm having difficulty understanding the last statement. Why would there be a state transition to a suffix?

Assume that you build an automaton for finding occurrences of $bububa$ in the input string. When the automaton reads the input string $bubububa$, then it after reading $bububu$, it must not just return to state $\epsilon$, as otherwise an occurrence of $bububa$ is not detected. Also, jumping back to state $bu$ is would not do the trick, as then again, the $bububa$ starting in letter 3 of the word would be missed. Rather, after seeing a $u$ in state $bubub$, the automaton must transition to $bubu$ in order to no miss the possibility that only the first two letters are to be ignored.

The last line in the definition of $E$ describes how the back transitions in the automaton are found: in order not to miss any occurrence of $bububa$, the state in the automaton jumps back as little as possible.


'Stones' game complexity I'm trying to find complexity class of finding winning strategy for first player in following game:

Intance of 'Stones' game is:

finite set $X$
relation $R \subseteq X^3$
set $Y \subseteq X$ and node $f \in X$

At the beggining we place stone in every element of $Y$.
Every player in his turn can move stone from $x$ to $z$ iff. $\exists y.R(x, y, z) \wedge y\ has\ stone\ placed\ in\ it$.
Player who places stone in $f$ wins.

I think it's $PSPACE-complete$, but I was trying to proove this for some time, and I run out of ideas.

I won't lie, it's homework assignment for my complexity class. Any help will be highly appreciated.

The game is actually an instance of two-persons Pebble game, as @HendrikJan pointed out, and as such is proven to be $EXPTIME-complete$. The following is a summary based on a proof by Kasai, Adachi and Iwata in SICOMP 8 (4).

For starters, it's pretty obvious that the game is in $EXPTIME$ - we can simply check all the possible games and see if there is winning strategy. To proove it's $EXPTIME-hard$ is a little bit more challenging.

First we need to know the notion of Alternating Turing machines (or ATMs for short). We will further tighten the definition to get so-called standard ATM:

We say an ATM $M$ is standard if

$M$ has only one work tape with the head initialized to the first cell of the tape,
if a configuration $C$ of $M$ is existential (universal), then every configuration $C’ \in Next_M(C)$ is universal (existential),
the initial state is existential and the accepting state is universal, and
$Next_M(C) = \emptyset$ if and only if $C$ is an accepting configuration.

Where $Next_M(C)$ deontes set of possible configurations after one move starting from configuration $C$

Now there come two important lemmas proven by Chandra, Kozen and Stockmayer in Journal of the ACM 28(1):

Lemma 1

For every $S(n) \geq log (n)$, if $L \in ASPACE(S(n))$, then $L$ is accepted by a standard ATM within space $S(n)$.

Lemma 2

$EXPTIME = APSPACE$

Having those two in mind, we now see that, given a standard ATM $M = (Q, \Sigma, \Gamma, \delta, b, q_1, q_a, U)$ such that only $p(n)$ cells are
available on the work tape for some polynomial $p$ in $n$, and a word $w = w_1 w_2 ... w_n$, we need to construct, in logarythmic space, an instance of pebbles game $G$ such, that $w$ is accepted by $M$ iff. first player has winning strategy in $G$.

In order to do that we will need

set of fields $X$ consisting of

fields representing the state of working tape ($\{1..p(n)\} \times \Gamma$)
fields representing current state of machine and it's heads ($Q \times \{1..n\}  \times \{1..p(n)\}$)
fields representing work tape transitions ($Q \times \{1..n\}  \times \{1..p(n)\} \times \Gamma^2)$
three additional fields $s_1, s_2, t$ to ensure that correct player wins the game

Set $R$ of rules that translates $\delta$ into our game:

For each element of $Q \times \{1..n\}  \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a', (d', d'')), a \neq a'$ then this transition can be encoded with the following rules:

$([q, i, l], [l, a], [q, i, l, a, a'])$
$([l, a], [q, i, l, a, a'], [l, a'])$
$([q, i, l, a, a'], [l, a'], [q, i+d', l+d''])$

For each element of $Q \times \{1..n\}  \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a, (d', d''))$ we need just one rule:

$([q, i, l], [l, a], [q, i+d', l+d''])$

Finally we need to have "game finishers" rules:

for each $i$ and $l$ there should be rule $([q_a, i, l], s_1, s_2)$
we also add rule $(s_2, s_1, t)$

And to start the game properly we need the set $S = \{[q_1,1,1],s_1\} \cup \{[l,b] | 1 \leq l \leq p(n)\}$, which denotes that we're in initiall state, both heads are at the beggining of the tapes, and the working tape is empty.

From this, the proof of the fact that $w$ is accepted by $M$ iff. first player has a winning strategy in $G$ should be pretty straightforward.


Which properties of context sensitive languages are decidable? There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable?

$L_1 = \emptyset$
$L_1 = \Sigma^*$
$L_1 \cap L_2 = \emptyset$
$\overline{L_1}$ is also a context-sensitive language.
$L_1 = L_2$

When considering questions like this you need to make explicit what representation you are using for your languages. In the following I will assume you are using context-sensitive grammars as input for your problems.

1) is a well known undecidable property of context-sensitive grammars.

2) as well as 3) and 5) are obviously undecidable as they are undecidable for a proper subclass of context-sensitive grammars, namely the context-free grammars.

4) is trivially decidable as the answer is always yes because the complement of a context-sensitive language is itself context-sensitive.


How do I visit all edges incident to a vertex in a DCEL data structure? In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which has v as its origin, that is, v.inc.origin == v. However, there may be multiple half-edges which have v as its origin.

How do I access or iterate all half-edges which have v has their origin?

We can do that by exploiting the structure of the DCEL.

Recall first that each half-edge h has a pointer to its twin half-edge, h.twin. Each half-edge h also has a pointer to its successor, h.next, and predecessor, h.prev, half-edges, which lie on the boundary of its incident face (that is, on the boundary of h.face), assuming that the incident face of h lies to its left (if we walk, in a counter-clockwise matter, along the edges incident to h.face by following the "next" pointers).

So, how do we visit all half-edges which have a vertex v as their origin?

The solution consists in exploiting the pointers h.twin and h.next.

Let h be the half-edge such that a vertex v stores h as its own incident half-edge (that is, h == v.inc), where v is the vertex that we want to know all half-edges which have v as its origin, where h is one of those half-edges. We can then access h.twin, which has v as its destination. Hence, h.twin.next is a half-edge which also leaves v. Unless  v is adjacent only to one vertex u, which implies that v.inc == h is the only half-edge leaving v (and we are done), then h.twin.next is different from h. In that case, let w = h.twin.next. Then w.twin is a half-edge which has v as its destination (i.e. like h.twin). Hence, w.twin.next is also a half-edge which leaves v. We can proceed in this matter until w.twin.next is equal to h.

In a more formal way, the algorithm may look as follows.

function all_half_edges_leaving(v):
    h = v.inc
    list = [h]
    w = h.twin.next
    while w != h:
        list.append(w)
        w = w.twin.next
   return list

Clearly, once we have the half-edges leaving v, we can access in constant time also its twins (given that each half-edge stores a pointer to its twin). Alternatively, we may also store the twins in a list during the procedure above.


Issue in comparing classifiers for pattern recognition I have designed a classifier M which recognizes gestures and classifies it under any category always. A gesture is classified based on the hamming distance between the sample time series y and the training time series x. The result of the classifier are probabilistic values. There are 3 classes/categories with labels A,B,C which classifies hand gestures where there are 100 samples for each class which are to be classified (single feature and data length=100). The data are different time series (x coordinate vs time). The training set is used to assign probabilities indicating which gesture has occured how many times. So,out of 10 training samples if gesture A appeared 6 times then probability that a gesture falls under category A is

  P(A)=0.6
   similarly
  P(B)=0.3

and

  P(C)=0.1

Now, I am trying to compare the performance of this classifier with Bayes classifier, K-NN, Principal component analysis (PCA) and Neural Network.

On what basis,parameter and method should I do it if I consider ROC or cross validate since the features for my classifier are the probabilistic values for the ROC plot hence what shall be the features for k-nn,bayes classification and PCA?
Is there a code for it which will be useful.
What should be the value of k is there are 3 classes of gestures?

Please help. I am in a fix.

There isn't an easy way to do this. In fact a recent paper by Charles Parker explains some of the problems with using ROC curve measurements (there's a friendly overview at my blog - self promotion alert!!). His paper does make some recommendations on the best ways to compare different classifiers, so you will find something useful there.


Homomorphism Languages Let $h$ be a homomorphism and let $L$ be a language.  Writing ${}^*$ for Kleene star, I want to show that $(h^{-1}(L))^* \neq h^{-1}(L^*)$.  Can I prove this just by showing that we can have  $h^{-1}(L)$ to be empty (because no strings are mapping into $L$) and therefore the right side is the empty set? Doing the same to the left side gives $\emptyset^* = \{\epsilon\}\neq\emptyset$.

Unfortunately both sides contain the empty string. As you say, the Kleene star of the empty set also contains the empty string: $\varnothing^* = \{ \lambda\}$. The Kleene star of a language $L$, equals $L^* = \cup_{i\ge 0} L^i$, where $L^0 = \{\lambda\}$ and $L^i = L \cdot L^{i-1}$ for $i\ge 1$.

On the other hand $h(\lambda) = \lambda$ for any morphism $h$, so $\lambda \in h^{-1}(K)$ whenever $\lambda \in K$. As $L^*$ contains the empty string this is the case here.

However, this does not mean the two sets are equal.
Consider $h:\{a,b\}^*\to \{a\}^*$ defined by $h(a) = a$ and $h(b) = aa$ and $L=\{a\}$.


Is this phrase structure grammar from my textbook correct? I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.

On page 12, the authors start describing a set of rules that can be used to generate the set of all enumerations of names of the type "tom, dick and harry": the rules allow single names (e.g. "tom") as well as repetitions ("tom, harry, dick, dick and harry"); multiple names in an enumeration are separated by commas except the last two names which are separated by "and", so the following aren't valid: ("tom, harry, dick") or ("harry and tom and dick").

A few pages later, and after having defined some more terms and formalisms, the authors come up with the following replacement rules (parse structure grammar) to generate the sentences of the desired type:

0. Name -> tom | dick | harry
1. Sentence-> Name | List End
2. List -> Name | Name, List
3. , Name End -> and Name

In the above, Sentence is the start symbol.

However it seems to me that these rules can generate incorrect sentences: if we replace Sentence by List End and List by Name we end up with Name End for which no replacement rule is defined.

It seems to me that the 2nd line in the rules above, if replaced by

Sentence -> Name | Name, List End

would fix this problem.

Am I correct that the authors have made an oversight, and is my modification correct? Or have I misunderstood something?

I don't have a CS background and this is the first time I'm reading about parsing, so please keep that in consideration in your replies. Thanks!

You are correct, in a sense. Speaking in formal notation, you have

$\qquad \displaystyle \mathtt{Sentence} \Rightarrow \mathtt{List}\ \mathtt{End} \Rightarrow \mathtt{Name}\ \mathtt{End}$

and we can not get rid of $\mathtt{End}$. We have not generated a wrong word, but a sentence that can not be derived further to any word. That is not a mistake in the grammar itself (with respect to the generated language), but certainly nasty if you think of parsing.

Your modification is valid. In particular, we do not need to generate lists of length one using rule 2 (which you make impossible by your modification) because we can just alternative 1 of rule 1.

Note that the grammar given is not the greatest (for parsing). For example, it is not context-free (rule 3). A better way to implement detection of the end is to generate the list the other way round ($\_$ denotes a space):

$\qquad \displaystyle \begin{align}
  \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\
  \mathsf{List} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{,\_}\ \mathsf{Name} \\
  \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry}
\end{align}$

Of course, this grammar is now left-recursive which is problematic for some parsing strategies (e.g. LL). So it may be useful to create the list from left to right after all, but keep generating the $\mathtt{and}$ at the start:

$\qquad \displaystyle \begin{align}
  \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\
  \mathsf{List} &\to \mathsf{Name} \mid \mathsf{Name}\ \mathtt{,\_}\ \mathsf{List} \\
  \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry}
\end{align}$

Now a parser working from left to right can always identify the next rule (with a lookahead of two to catch whether there is a comma behind a name).


Approximate time to execute algorithm Suppose a comparison between elements takes 1ms to execute. If an algorithm is O(logN), for example, deletion in an AVL Tree, and the AVL Tree contains 100 elements. Does that mean that the time to execute the algorithm would be log100 * 1ms? Do I need more information to calculate this or is this enough?

If an algorithm is $O(\log n)$, then you can conclude absolutely nothing about the running time of the algorithm. This is due to many factors, one of which is that $O(\log n)$ hides an arbitrary constant factor: both $\log n$ and $100\log n$ are $O(\log n)$ (not to mention functions such as $10^6\log\log n + 10^{15}$). There are also other reasons, but this reason is probably enough.


How to calculate point in 3D space from multiple perspective I have multiple camera in different points.

I have their position and rotation as $(x,y,z)$ , $(\alpha,\beta,\gamma)$ or $( roll, pitch,  yaw)$ .

And I have output like this :

Feed from camera-1, I know length of yellow and green.

How can I calculate position of the object, in this case head in 3D space.

For each camera, you can compute the direction on which is detected the object. The position and orientation of the camera let you find the direction of the center of the image. Depending on camera aperture, each pixel of the image corresponds to a slightly different direction. I don't know which definition you use for your angle so I won't risk any expression of it but you should convert the angle to obtain a vector in cartesian coordinates.

So from a camera with position at $(x_c, y_c, z_c)$ and detecting the object in the pixel of direction defined by the unitary vector $(x_d, y_d, z_d)$, you know the object is along the direction:

($x_c + x_d \times d, y_c + y_d \times d, z_c + z_d \times d$) with $d$ being the distance camera-object.

Now if you have 2 cameras, you can look for the nearest points from each line to the other and take their center as position of the object (see skew lines).


CPU Registers and Computation How exactly does the control unit in the CPU retrieves data from registers? Does it retrieve bit by bit?
For example if I'm adding two numbers, A+B, how does the computation takes place in memory level?

The CPU has direct access to registers.  If A and B are already in the registers then the CPU can perform the addition directly (via the Arithmetic Logic Unit) and store the output in one of the registers.   No access to memory is needed.  However, you may want to move your data A and B from memory or the stack into the registers and vice-versa.  These are separate operations.
Registers can be of different sizes 8 to 64 bits, this depends on your CPU architecture. On a x86-64 CPU registers are 64bit thus addition of two 64bit numbers is a single operation.


Analysis of very simple algorithm I need to find the time complexity of the following simple algorithm.

Calculate the time complexity of the following algorithm:
void f(int n) {
  int i, x;

  for (i = 1; i <= n; i++)
    if (i % 2 == 1)
      x++
}

It obvious that the time complexity of this algorithm is $\Theta(N)$, but how I prove it formally?
I know that the loop will do $N$ iterations, so the total number of operations will be $N \times \text{(number of operations inside the loop)}$.
Here the tricky part, I know that for each iteration will be one operation for the comparison and one operation only if $i$ is odd.
So it's something like this:
$\sum_{i=1}^{n}(1+\frac{1}{2})$? I'm not sure, it's seems too strange and I'm not sure how to continue.
What is the best way to write it formally?
Also, I would like to ask if there are books with many examples of analysis of simple algorithms like this and proofs of their complexity. The most recommended book seems to be CLRS, but I didn't found many examples of this kind there and from what I understand it can be very complex topic (depending on the series you need to calculate in the end).
Thank you.

One important thing to understand here is that the asymptotic analysis happens with respect to the parameters that are of interest to you. Here, for example, we are interested in the complexity with respect to the input $n$.

Typically, we assume that arithmetic operations (like the modulo or addition, etc) take a constant number of time. In a real system, one operation might indeed be more expensive than another. But, the important detail is that the time required by these operations does not depend on the input parameter $n$: it could be $1$, $100$, or $10^{\#\text{stars}}$, but it is still a constant as long as it does not scale with the parameter of interest.
So again, in summary, when we compute the asymptotic complexity of the function with respect to $n$, we can consider that all these operations take a constant time.

Based on the above, the code inside the for-loop also takes a constant time. Whether the condition is true or not is irrelevant. If it is false it will take some constant time, and if it is true it will take again some constant time (maybe more than before, but still constant).
Hence, overall, the time for one iteration is $\Theta(1)$.

Then, as you said, the overall complexity will be $\Theta(n) \cdot \Theta(1) = \Theta(n)$.


Proving this language is not context free using the pumping lemma I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages.

To prove something with the pumping lemma, we firstly need to choose an arbitrary m > 0. After that we need to formulate the string (alpha below) we are going to reach a contradiction with. But how do I formulate that string? Rational thinking lead me to believe it's the following:

What do I do next?
I have no idea about the length of $w$, and therefore the above approach seems kind of useless.

Is the solution to constrain $w$ to be of length at most $m$?
But again, I wouldn't know what to do from there.

Here in the notation of the language superscript $R$ is not a number; you cannot choose it to be a length $m$.

Instead $R$ usually denotes the operation of "mirror image" which inverts a string: $(abbaa)^R = aabba$.

Now start rereading your notes on the Pumping Lemma.


Can CPU's 'shortcut' adding 0, multiplying by 1, and multiplying by 0? I am currently writing a program where a lot of adding 0 to numbers and multiplying by 1 and 0 occurs and it got me to wondering if the CPU 'shortcuts' (drops), these operations. I'm a CS student and this hasn't been brought up ever.

Can a CPU do this? What are the trade-offs in designing a CPU that detects +1, *1 and *0 and executes them faster?

Yes, there are processors which detect some kind of do-nothing operations, handle them specially so that they take less time than what they would take if they were handled naïvely.  In some cases, there are even recommended instructions to use for NOP (NOP are sometimes useful to align the code with a memory boundary, having NOP of various lengths available help the relieve the decoding part), the wikipedia page for NOP has a list which gives the normal meaning for some of them.

But

what you think as a do-nothing operation may not be one if you take into account things like resetting flags or the side effects of memory accesses -- and a processor should behave correctly in such matter;
I'd not rely on this as an optimization; more as an encoding trick or as a way to reduce the op-code pressure;  they are working when the operands are statically known to have no effect and in such cases, the code writer -- human or compiler -- should avoid the operation if possible;
detecting dynamically that the value has no effect is probably more costly than what would be gained by doing so.  That said, some relatively simple processors have operations which take a time which depend on the arguments (for arithmetic operations, don't think I've seen this for something else than integer multiplication and division, or for floating point operations)


In cache addressing, what value is placed in the offset field? There is a 64 KB 1-word cache, and a word is 32 bits.  From that I can derive that the length of the tag field is 16 bits, the length of index field is 14 bits, and, as my professor taught me, there is always 2 bits left behind for a byte offset.

Why the offset field is 2 bits, other than it fills in the remaining 2 bits of the word, and what its contents is was never covered in the course.

But when I looked around on Google, I read, and correct me if I am wrong, that the length of the offset field can vary.  Although I have found answers on how to determine the length, I could not find anything about determining its contents when a read hit/miss is performed.  My professor merely said "the byte offset is not used to select the word in the cache".

Just looking for clarification.

Paul A. Clayton gives the answer in a comment.

You say a word has 32 bits. An implicit assumption is that we want to be able access every of the four bytes, so we need two bits to make this distinction.


Dijkstra's Algorithm I have recently implemented Dijkstra's Algorithm to the shortest path between all pairs of nodes in the graph. I have implemented this code in Java. As instructed I am using a linked list to represent the adjacency matrix. As instructed, I am running my algorithm for a complete graph. The running time for a 1000 node complete graph is about 361 minutes. For 2000 nodes, my program has been running for close to a day, and it is still running.

I would like to run this for a complete graph of 6000 nodes but the running time is going to be too long. I am wondering, if this is too be expected.

Bob

Dijkstra has running time $\mathcal{T}(G) \in \Theta(|E| + |V| \log |V|)$. If the graph is dense then $|E| \in \Theta(|V|^2)$, which means that $\mathcal{T}(G) \in \Theta(|V|^2)$.

A quadratic running time means that a graph with twice as much nodes will take four times as much time to be processed. If $1000$ nodes required $6$ hours, then it is not surprising that $2000$ nodes will take about one day.

As you know, constants depend on the machine you're running your code on, it is therefore impossible to judge the speed of your code having the clock running time as the only datum; however your times strike me as particularly high for a reasonably modern personal computer, I would expect them to be a couple of orders of magnitude lower.


Minimal number of comparisons - sorting $6$ elements I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?

Algorithm
1. Sort $a_1, a_2, a_3$ and $a_4, a_5, a_6$.
Number of comparisons: $3+3=6$.
2. Merge two subarrays.
Number of comparisons: $3 + 3 - 2 = 4$.
Total number of comparisons: $6 + 4 = 10$.

According to A036604, 10 comparisons are indeed optimal. The link probably contains a citation to a paper proving this.


Common method for solving satisfiability problems which lie in P I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete.  However, all of the algorithms I know for them use specific techniques unique to that type of problem- e.g. unit propagation for Hornsat,  linear algebraic techniques mod 2 for XORSAT, and various other techniques for 2-sat.  Is there one general polytime algorithm which works for all of these problems in P?  Thanks.

Schaefer's dichotomy theorem is proved by dividing CSPs into two types: those that can be reduced to one of a few specific problems in P, and the other to which SAT can be reduced (and so are NP-complete). Specifically, every CSP of the former type is either trivial (always satisfied by the constant 0 or the constant 1 assignment), can be reduced to 2SAT, can be reduced to HORN-SAT, or can be reduced to XOR-SAT. These are the only algorithms you need to solve these CSPs. There is no one single algorithm – there is a finite list of algorithms.


Reducing minimum vertex cover in a bipartite graph to maximum flow Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds).

Intuitively: for each flow, pick one endpoint, then it is a minimum vertex cover in bipartite graph. But can it be shown rigorously?

According to König's theorem, the size of minimum vertex cover in bipartite graph $G$ equals to the size of maximum matching in $G$, and there is an obvious reduction from maximum matching in bipartite graph to maxflow problem.


Does DPDA accept all regular languages? A DPDA which accepts by empty stack cannot accept all Regular Languages?
Is it true that the DPDA cannot accept all regular languages?

I am not able to understand this.As per my knowledge DPDA are more powerful than regular languages as they have finite automate and also the stack.So finite automate can handle all the regular languages.So why above statement is true?

It is the property "accepting by empty stack" what makes the DPDA weaker. If a language $L$ is accepted by a DPDA by empty stack, then $L$ has the prefix property. The following language $L = \{ b^n \mid n \geq 0\}$ clearly does not have prefix property since if $b^k \in L$ then $b^m \in L$ as well for $m < k$. So this language is not accepted by a DPDA by empty stack.

Assume that $w \in L$ and $wv \in L$ and $L$ does not have prefix property. Assume also that $L$ is accepted by some DPDA $M$ by empty stack. Since $w$ is accepted by $M$, there is a computation path from $(q_0, w, S_0)$ to $(q_k, \epsilon, \epsilon)$. Since $M$ is deterministic, the only possible computation for input $wv$ is $(q_0, w, S_0) \Rightarrow^* (q_k, v, \epsilon)$. But $M$ has already had empty stack and so it cannot move further from $(q_k, v, \epsilon)$ and hence does not accept $wv$.

Definition: A language $L$ has prefix property if $w \in L$ implies no proper prefix of $w$ is in $L$.


Finding the longest common subsequence algorithm using hash table Slow I've designed an algorithm to find the longest common subsequence. these are steps:

Starts with i = 0

Picks the first letter from the first string start from ith letter.
Go to the second string looking for that picked letter.
If not found return to the first string and picks the next letter and repeat 1 to 3 until it finds a letter that is in the second string.
Now that found a common letter in the second string, adds that to $common_subsequence.
Store its position in $index.
Picks next letter from the first string and do step 2 but this time starts from $index.
Repeat 3 to 6 until reached end of string 1 or string 2.
If length $common_subsequence is greater than length of common subsequence so far add that  change lcs to the $common_subsequence.
Add 1 to the i and repeat 1 to 9 while i is less that length of the first string.

This is an example:

X=A, B, C, B, D, A, B
Y=B, D, C, A, B, A

First pick A.
Look for A in Y.
Now that found A add that to the $common_subsequence.
Then pick B from X.
Look for B in Y but this time start searching from A.
Now pick C. It isn't there in string 2, so pick the next letter in X that is B.
...
...
...

The complexity of this algorithm is theta(n*m).

I implemented it on the two methods. The second one uses a hash table, but after implementing I found that it's much slower compared to the first algorithm. I cant undrestand why.

Here is my implementation:

First algorithm:

import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

Second one using hash table:

import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

One optimization is to replace the access to reached_index[item] by a local variable which is initialized from the hash table at the beginning of the for item loop, and stored back to the hash table at the end of the loop.

Another optimization which will speed up things is to replace the hash tables with arrays of size 256.


How are programs split up into pages in Memory Paging? I am a bit confused about how the logical addresses are generated in a paging memory architecture and where and when a program is split up into pages.
I understand how logical addresses are translated to physical addresses and everything that happens after that. I just don't understand how a program is split into distinct pages and where and how this happens.
For example, if we consider a non-paging architecture which uses contiguous memory and execution-time binding, a CPU instruction like JUMP 8, where 8 is a logical address, I understand how an MMU with a base register can dynamically relocate a program anywhere in main memory by changing the value stored in base register, while the object code stored in memory is still using the logical address of 8. However, how is this JUMP 8 instruction handled in a paging architecture, as in when will all these simple logical addresses like 8 be converted into logical addresses suitable for paging (with a page number and offset value), does the compiler split the program into pages?
Also, how is the program stored in memory, are the simple logical addresses stored like in execution-time binding, or is the program in memory stored with the paging logical addresses?

The program is not really split up into pages. The program is unaware of where it lands in physical memory. This is all the essence of paging.
For example, if you take Linux on x86 CPUs and the C++ language, you will have the compiler generating machine code which will be linked into a final executable which has a .ELF extension.
ELF files support virtual addresses. ELF files specify the virtual addresses at which the code is going to land. The linker or compiler is going to write the starting virtual address at which the code is going to land. The default virtual address is 0x400000 with ld and g++.
So basically, the ELF executable specifies where the program lands in virtual memory. Since the default virtual address is always 0x400000, then a lot of programs will have that starting virtual address. The kernel thus creates page tables for each process (each executable that you start). These processes will land at different places in memory even if they all have the same virtual address. This is due to the fact that they have different page tables.
In fact Linux holds a page struct for every physical page in the system. This takes up quite some space and there have been discussion to change this pattern. I don't know if it is yet done. The page struct allows the kernel to map all physical pages to know what every page is used for.
So when you start an executable/process the kernel determines what physical pages are available and set up the page tables for that process so that virtual address 0x400000 lands there once translated by the MMU.
The JMP 8 instruction will be translated by the MMU before being placed on the address bus. So the 8 is a virtual address. This virtual address is determined by the compiler and the linker.
There are 2 different kinds of JMPs. Relative JMPs and absolute JMPs (far JMPs). Relative JMPs are calculated as an offset from the current position in the code. Far JMPs in the meantime are calculated as absolute address. They contain a virtual address where the JMP should go. They can JMP anywhere in RAM.
For example,
label:
jmp label

is a relative JMP, while
jmp 0x8000

is an absolute JMP. These jumps are calculated by the compiler and linker. The compiler places the functions you call from main at different positions in the code that it places in the relative JMPs. Far JMPs are mostly used in operating-system development.
The linker plays the role of linking several files. So you have a symbol section in the ELF file. This symbol section contains entries which associate each symbol with an address. I'm not totally aware since I never wrote an ELF interpreter. What I can tell is that the address is the address of the beginning of something like a variable or mostly functions. What happens is that the linker takes the symbol and checks it against other object files you included in the linking command. If it finds the symbol in another file, it places the address of the code in the relative JMP to tell the code where to JMP to get to that function. That is why it is called a linker, because it resolves links. This is why you have to include header files in C++. You tell the linker where to find these other symbols (functions, variables, classes).


What is the worst case for C++ "sort" function? So, what is the worst case for C++ "sort" function, when does it go to O(n^2) time? I know it's QuickSort, therefore, it's very fast in most cases, but it gets to O(n^2) in special cases. I've tried to figure it out via measurements, but I have trouble interpreting the results.

The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from $\Theta(n \log n)$ (if you choose the pivot to be the median) to $\Theta(n^2)$ (if the pivot is always a constant number of elements away from the minimum/maximum element).

That said, C++ standards do not mandate any particular implementation of the sort() function. So it is just a "coincidence" that your implementation happens to use Quicksort.

The answer to your question about the worst case depends on which C++ standard you are referring to. Before C++11, sort() was required to take "approximately $O(n \log n)$ comparisons on the average" (whatever "approximately" means) but, since no particular implementation is mandated, you'd have to look at the sources of the standard library you are using.

If you are referring to C++11 or later, then sort() is required to perform $O(n \log n)$ comparisons in the worst case (see Section 25.4.1.1).
To be pedantic, you'd still need to inspect the implementation to know what the worst case is (I could imagine a conforming implementation that first checks whether the input array is any specific permutation (or class of permutations), and then sorts it in linear time).

To be even more pedantic: the standard mandates an asymptotic number of comparisons, so I'm not sure whether a sort() function with a running time of $O(2^n)$ (or some weird function of the input) would conform to the standard, as long as it only performs $O(n \log n)$ comparisons...


If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$? I am confused interpreting the statement of this question:

"If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?"

Should the symbol "|" (such as) be understood as an logical and?

The language L1, so,  would be $ L \cap L^R $ - a subset of L?

Or should the symbol "|" be understood as an logical or?

The language L1, so,  would be $ L \cup L^R $?

In both cases it is regular (I believe), since the languages $L$ and $L^R$ are regular, and the union or intersection will be also regular.

Am I understanding this right?

The notation $L_1 = \{ w \in L \mid w \in L^R \}$ means "the collection of all $w \in L$ that satisfy the condition $w \in L^R$". In other words, $L_1 = L \cap L^R$.