Comparing two recurrence relations w.r.t. asymptotic growth I have two functions $T_1(n),T_2(n)$. How do I decide which is asymptotically faster?

One is given by the recurrence relation

$$ T_1(n) = \sqrt{n} T_1(\sqrt{n}) + 3 n, \quad T_1(1) = T_1(2) = 1. $$

The other is given by the recurrence relation

$$ T_2(n) = 3 T_2(n/3) + 2n \log n, \quad T_2(1) = T_2(2) = 1. $$

For the first function I guess there is $O(\sqrt{n} \cdot \sqrt{n})$ for loop, and $O(n)$ for the $c$; which becomes $O(n^2)$ in total.

For the second one, the Master's theorem is applicable, but as I assume the complexity becomes $O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$ for loop, and $O(n\log n)$ for $c$.

So if I am comparing both $O()$'s, we can in total see that

$$ O(n^2) < O(n^2 \cdot \log n) $$

Was there any mistake, or is this not how recurrence unrolling is done?

You can sort of get a feel of the asymptotic behavior of a recurrence by flatting out the recurrence into an equivalent problem of the form $A_k = c_1(k) A_{k-1} + c_2(k)$.

First of all, to see that $O(n^2)$ is an extremely loose bound, notice how $T_1(16)$ expands out:
\begin{align*}
T_1(16) &= 4 T_1(4) + 3 \cdot 16 \\
&= 4 (2 T_1(2) + 3 \cdot 4) + 3 \cdot 16 \\
&= 8 + 2 \times (3 \cdot 16)
\end{align*}
Similarly, you'll find that $T_1(256)$ expands out to
\begin{align*}
T_1(256) &= 16 T_1(16) + 3 \cdot 256 \\
&= 16 (8 + 2 \times (3 \cdot 16)) + 3 \cdot 256 \\
&= \frac{256}{2} + 3 \times (3 \cdot 256)
\end{align*}
This strongly suggests that $T_1(2^{2^k}) = 2^{2^{k-1}} + 3k 2^{2^k}$, or $T_1(n) \approx \frac{n}{2} + 3 n\log_2 \log_2 n$. We can show this by first relaxing the domain of the function to those of the form $2^{2^k}$. Since $\sqrt{2^{2^k}} = 2^{2^{k-1}}$, we have
$$
T_1(2^{2^k}) = 2^{2^{k-1}} T_1(2^{2^{k-1}}) + 3 \cdot 2^{2^k}
$$
Let $A_k = T_1(2^{2^k})$, then
\begin{align*}
A_k &= 2^{2^{k-1}} A_{k-1} + 3 \cdot 2^{2^{k}} \\
&= 3 \cdot 2^{2^{k}} + 2^{2^{k-1}}(3 \cdot 2^{2^{k - 1}} + 2^{2^{k - 2}}A_{k-2}) \\
& \cdots \\
&= 2^{2^{k - 1}}A_{0} + 3 \cdot 2^{2^{k}} + 3 \cdot 2^{2^{k}} + \stackrel{k}{\dots} + 3 \cdot 2^{2^{k}}
\end{align*}

which shows that when $n = 2^{2^k}$, then $T_1(n) = \Theta(n\log\log n)$. Suppose we now open $T_1(n)$ over the whole real domain (that is, we relax the domain restriction imposed previously), then it should be easy to show that if $T_1(x) = 1$ whenever $x \in [1, 2]$, then $T_1(n) = \frac{n}{2} + 3n \log_2\log_2 n$ extends uniformly. (Proof: Use the same derivation above, but for some other $p \in [1, 2]$, do the case analysis on $p^{2^k}$ instead)

Therefore, we have $T_1(n) = \Theta(n \log\log n)$ and $T_2(n) = \Theta(n^2 \log n)$. Asymptotically, $T_2$ still dominates $T_1$.


Fixpoints of a transformation of an extended WHILE program I am doing some excercises to train myself in computability.
There is one that I am not able to solve, here it is.

Consider the following transformation associated to an extended WHILE program:

For all $x \in \mathbb{N}$,
$\begin{cases}
  A f(x) = x \cdot f((x+3)/2) & \text{if \(x\) is odd} \\
  A f(x) = f(x+1) & \text{otherwise} \\
\end{cases}$

How many fixed points does $A$ have?
Is there a maximum fixed point?
Find the minimum fixed point.

I know that a fixed point is a function $f$ such as $A f = f$.

I would say there is an infinite fixed point. But how to prove it?

To calculate the minimum, I would make a table with on each row: $\bot$, $A \bot$, $A^2 \bot$, ... and if there are two similar lines, that's our minimum. But once again I am not sure this is enough to do this.

Suppose $f$ is a fixpoint of $A$. First,
$$
f(0) = f(1) = f(2) = f(3) = 3f(3),
$$
and so $f(0) = f(1) = f(2) = f(3) = 0$. Second,
$$
f(5) = 5f(4) = 5f(5),
$$
and so $f(4) = f(5) = 0$. Third, if $n = 4m+3 \geq 7$ then $$f(n) = n f(2m+3),$$ while if $n = 4m+1 \geq 9$ then $$f(n) = n f(2m+2) = nf(2m+3).$$ In both cases, $2m+3 < n$, and so you can prove by induction that $f(n) = 0$ for all odd $n$. That implies that $f(n) = 0$ also for all even $n$, and we conclude that $f(n) = 0$ for all $n$.

Edit: This is the maximal fixpoint. The minimal fixpoint is $\bot$. There are two other fixpoints: $f(n) = 0$ for $n \leq 3$ and undefined otherwise, and $f(n) = 0$ for $n > 3$ and undefined otherwise.


Can we build computer without instruction pointer register (PC/IP)? I am studying computer architectures in university and my teacher asked me if we can create a computer without PC/IP register?

One possible thought could be a data-flow architecture.

Here the various processing elements are wired together to implement the desired algorithm and rather than an IP register, each processing element (add, subtract, multiply, and, or, compare etc) acts when data is presented.

This sort of things is mostly seen today in fast algorithms embedded in FPGAs. I understand, but have no direct info, that crypto-currency miners are designed along these lines.

So, is this still a computer? Well. oddly enough, a popular way to program these machines uses "C" source code to describe what needs to be done and a sophisticated compiler to design the data-flow machine needed to get the job done.

On a similar note, the LabView programming environment presents a similar model with interconnected elements driven by the data and not an instruction address concept.


A question about decidable and undecidable problems Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem.

This is the context:

  Consider the problem of determining whether a number belongs to a set. This
  problem is easy for the following sets:

  The set of odd numbers
  The set of even numbers
  The set of prime numbers
  The set of numbers that can be written as a sum of five square numbers

  For every one of these sets, a program can be written that accepts a whole number as input and—depending on whether the input is in that set—outputs a yes or no answer.

  However, there are other types of sets. This chapter has shown that there are
  certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not. For example,

  The set of numbers of programs that will output 42 for some input
  The set of numbers of programs that always output a 0"

  The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us by Noson S. Yanofsky

First of all, I should say that I am a self-learning in this area, so I don't have very good knowledge about this stuff. so, in this context, I don't get two parts. If anyone could help me, I would very appreciate it.

the first part is: "there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." what are they. is the writer talking about inputs/ arbitrary whole numbers or certain sets of whole numbers?

second, I don't get this part at all and somewhat, this part is making me confused about the former question:

  The set of numbers of programs that will output 42 for some input
  The set of numbers of programs that always output a 0"

if you rewrite this part in another form, I think I would comprehend it because I think this is a grammatical confusion. thank you in advance

When the author talks about "number of programs", they mean numbers that represent programs. Normally, we think about programs of being strings of characters (e.g., Java programs) but we can also represent programs as numbers. The easiest way to see this is to think how they're represented inside your computer. That string of characters is just a big list of zeros and ones inside the computer, and a "big list of zeros and ones" is just a number written out in binary. Formally speaking, "programs" here are probably Turing machines but it won't hurt you to think of computer programs in whatever language you're familiar with.

The technique of using natural numbers to represent arbitrary objects like this is sometimes called "Gödel numbering", as it was first used by Kurt Gödel to prove things about logic. He encoded logical formulas as numbers, which allowed him to write formulas about formulas, in much the same way as a compiler is a computer program that operates on computer programs, and a universal Turing machine is a Turing machine that operates on Turing machines.

  "... [T]here are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." What are "they"? Is the writer talking about inputs/arbitrary whole numbers or certain sets of whole numbers?

That's not a very well-written sentence. The interpretation that makes most sense to me (the only one I can think of that makes the statement true) is, "There are certain sets of whole numbers for which no computer program can be written that decides whether its input is in that set."


Do functional algorithms require more memory than imperative algorithms? Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example.

The imperative approach would as follows:

wordcount = {}
for word in words:
    wordcount[word] += 1

The functional would be:

uniquewords = set(words)
wordcount = [words.count(w) for w in words]

For each word w we are doing a full scan on the words array, while the imperative approach goes over each word just once. Am I right to suppose that the functional way of doing it will consume a lot more resources than the imperative one?

Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in words and behind the scenes set(words) is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses imperative features dressed up as functional programming. Have a look at Ocaml or Haskell.

As for your question, people have thought about just how efficiently one can implement functional programs on standard hardware (which I think is what you're asking). At LICS 2015 the following paper has been accepted:

  B. Accattoli, C. Sacerdoti Coen. On the Relative Usefulness of Fireballs. LICS 2015.

In it the authors show that a RAM machine (standard hardware) can simulate $\lambda$-calculus (functional programming) with a linear-time overhead with respect to the number of computation steps ($\beta$-reductions) of the functional program. This shows that functional programs can be efficiently implemented on existing hardware and will not in general consume a lot more resources.

Let me also point out that you cannot make the comparison you're trying to make in a sensible way. You are comparing two different algorithms that compute the same function. Instead, you should be comparing two implementations of the same algorithm in an imperative and a functional style. For instance sorting algorithms would do. And you should use a language that supports both imperative and functional programming. For instance, we could take merge sort and use the rosettacode.org functional implementation of merge srot in OCaml. Perhaps someone has the time to play with this and post some comparisons.


Identify objects (bus) on the map based on coordinates (lat, lon) Let's say I have an android app that frequently sends current GPS location of the user. If person is driving with bus, I can easily get GPS location of the bus and display it on the map and update it accordingly every 30 seconds.
Let's say that instead of one bus there are 3 buses driving along same route. My problem is to display real time location of every bus on the route. In this case there are X users on every bus all having my android application installed on their phones. Here is the picture that could represent the problem:

As you can see, every mobile application will send GPS location of the user to my server. Server receives and saves data.
Based on the server data I should create a web app that should display map whith position of every bus in real time.
One possible way to do this is to to try to cluster GPS data and based on clusters to conclude where is position of every bus. This approach has few problems:

This algorithm could be slow if there is lot of data (then I can't
update position of every bus every 30 seconds)
Second problem is that I don't know number of clusters (buses). There might be 2, 3, 4 or N buses

Is there any other better approach to this problem?

Have the app record the GPS location once per second, save it, and once every 30 seconds, update that trace of the locations over the past 30 seconds.  Or, just upload the location every second.  The bandwidth requirements for that are small.  Then, if you have multiple users in the same location (within a fixed radius, say within 100 ft of each other), and with a velocity within some fixed range (say, between 20-60 mph), declare them to be on a bus together.  That should be fast, and doesn't require knowing the number of buses.

This problem doesn't need a solution with a fancy algorithm; straightforward solutions should suffice.


If $n^{\log n}$ is not polynomial or exponential, then what this function is called? I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability".

  Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm (although it should be noted that this definition includes certain non-polynomial time complexity functions, like $n^{\log n}$, which are not normally regarded as exponential functions).

My question as following,

If $n^{\log n}$ is not polynomial nor exponential, then what this function is called? Does this have a name or special cases or not?

Thank you.

There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.


What is the complexity of this algorithm for sparse matrices? I am reading a paper on sparse matrices and there is an algorithm for sparse lower triangular systems. In the below pseudo-code $l$ is a sparse matrix and $x,b$ are sparse vectors.

x=b
for j=0 to n-1 do
    if x[j] != 0
        for i=j+1 to n-1 do
            if l[i][j] != 0
                ~5 operations.

The paper claims that this algorithm is $\mathcal{O}(n+|b|+f)$, where $|b|$ is the number of non-zero entries in $b$ and $f$ is the number of floating point operations carried out.

I do not understand why this algorithm is not $\mathcal{O}(n|b|f)$.

Reference:
Chapter 3 - Section 2 of
https://epubs.siam.org/doi/book/10.1137/1.9780898718881

Some context on sparse matrices:
Sparse matrices usually appear when solving problems using numerical schemes such as the finite element method. These matrices usually have a very small number of non-zero entries per row. For instance, a $n$-by-$n$ matrix might only have $\mathcal{O}(1)$ entries per row. The situation might not be as good as this in the algorithm above (there is no mention of a definition of sparse matrices in the book, as far as I can see.)

They say the running time is $O(n+|b|+f)$, where $f$ is the number of floating point operations taken during the entire computation.  This takes some careful reading to understand what they mean.

They mean, if you take the total number of floating-point operations that are performed inside the innermost loop, and call that $f$, then the running time is not too much more than $f$.  In other words, they are saying we do $O(n+|b|)$ operations for updating the loop indices, plus the time taken by the body of the innermost loop (summed over all the iterations).

The body of the innermost loop might indeed take $5 n|b|$ operations in total (say), in which case the total running time would be $O(n + |b| + 5n|b|) = O(n|b|)$, as you had expected.

Note that $f$ is not the number of floating point operations in a single iteration of the innermost loop; it is the total across all iterations of the loop.  So $f$ is not 5.

Why do they count it this way?  Presumably, the floating point operations are ones that we'll have to do no matter what, because they are essential to the operation you're doing; they instead want to focus on the extra book-keeping needed to update loop indices etc. and make sure that doesn't add too much extra cost.

Finally, I'll note that you changed the pseudocode.  The pseudocode they show is not the same as what you listed in the question.  In the book the pseudocode of the innermost loop is not "for $i=j+1$ to...", but rather "for each $i>j$ for which $l_{ij}$".  That's not the same.  Since $l$ is a sparse matrix/vector, there are more efficient ways to iterate over the non-zero entries of $l$ than iterating over all possible values of $j$ and testing whether that element is non-zero.  This also affects the running time.


Need help for maximizing solution Suppose there exists a list of unsorted int numbers [91,89,90,90,90,89,91].
I need to maximize the profit by selecting an element, in as many steps as needed, which satisfies the condition that,
when element(i) is chosen, the profit would be value of element(i) multiplied by its frequency/occurrence in list, an extra condition is that element(i), element(i)-1 and element(i)+1 should be removed as well.
So for the given array [91,89,90,90,90,89,91], if I choose 90 and remove it, my profit will be 90*3=270 and my array reduces to [], because I remove (90-1) and (90+1) in the same step.
However, if I had chosen, 89 then profit would be 89*2 and upon removing 89 and 89+1(There is no element corresponding to (89-1)), I am left with [91,91]. In the next step, I remove 91, this results in a total profit of 89*2+91*2. The profit is greater than the one obtained after selecting 90.

Another example is list [3,4,2], suppose I select 3, this means profit is 3*1 and I remove 3, 2 and 4 which results in empty list and profit is 3. Now, I choose 2, this results in removal of 2 and 3, profit will be 2*1. List will be [4]. Next step profit will be 4*1, so total profit will be 2+4=6.

I tried to select max element in array and remove it, but it will not work for list [1,1,1,1,1,1,1,1,1,2]. Here, 1 needs to be selected, instead of 2.
Because selecting 2, would result in a profit of 1 versus selecting 1 which would give 1*9.
What approach would be ideal to solve this? Please provide your opinions.
Thank you

This is a special case of maximum weighted independent set on an interval graph. Another way to phrase your problem is as follows: choose a subset of your neighbors of maximal sum in which no two elements have difference exactly 1.

One simple way to solve your problem is using dynamic programming. First sort the list, and remove duplicates (but remember how many of each number appear in the original list). Now use dynamic programming to calculate the optimal solution for every prefix of the sorted list.


What does this performance formula mean? I have to make a quick clustering program but the following formula is gibberish to me:

  $\operatorname{Perf}(X,C) = \sum\limits_{i=1}^n\min\{||X_i-C_l||^2  \mid  l = 1,...,K\}$

  where $X$ is a set of multi-dimensional data and $C$ is a set of centroids for each data cluster.

This formula is a fitness function for an artificial bee colony clustering algorithm as a substitute for k-means clustering algorithm. It is described as a total
within-cluster variance or the total mean-square quantization error (MSE).

Can anyone translate it to pseudo-code, normal human English, or at least enlighten me?

Just break it down into parts:

  $  \{ f(l) \mid l = 1,...,K \} $

This is a simple set construction. The above would simply create a set with all the elements from 1 to K. In your case the f(l) is the function:

  $ ||X_i-C_l||^2 $

Given the || means the norm, these are vectors you are subtracting (rows of the X and C matrices). So subtract the vectors, take the norm, and square it. That produces a new set, of which you want to take the minimum.

  $ \sum\limits_{i=1}^n $

This part is then just the sum of above min calculation for every index $i$ from $1$ to $n$.


Proof for values of d with d:= ||L|| - N(L) with $d \in \mathbb{Z}$ and N(L) Nerode Index Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $\equiv_L$ from Myhill–Nerode theorem. Proof, which values d can have with $d:=||L||-N(L),d\in\mathbb{Z}$
Some conclusions I came up with so far:

|L|| is infinite, when L is infinite. Then d is not defined.
When N(L) is infinite for any non regular language, so L is infinite as well and $\infty - \infty $ wouldn´t be defined.
So say ||L|| is finite then N(L) is finite as well because every word hase to be in a certain class. If not ||L|| would be infinite. Though when N(L) is finite, ||L|| doesn´t have to be finite since we might have some symbols looping over states.
d is probably never negative, because if N(L) > ||L|| we would have classes which don´t belong to words in L.
When d = 0 then, N(L) = ||L|| and there would be a class for every word in L.

So d can be anything from $\{ 0,...,\infty \}$
Might this be enough for an answer or am I missing any cases/details? Where could I be proofing more formally?

In order to make the question nontrivial, you have to assume that $L$ is finite. You haven't specified what the alphabet is, so I will assume that the alphabet is arbitrary.
First, let us show that $N(L) \leq \|L\|+2$. We can construct a DFA for $L$ whose states consist of all prefixes of words in $L$, together with a failure state. This DFA contains an initial state (corresponding to the empty prefix), a failure state, and one state for every non-empty prefix. In particular,
$$
N(L) \leq 2 + \sum_{w \in L} |w| = 2 + \|L\|.
$$
In other words, $d \geq -2$.
Second, let us consider the language $L_\Sigma = \{\sigma : \sigma \in \Sigma\}$ over an alphabet $\Sigma$. The minimal DFA for this language contains three states, and so the value of $d$ for $L_\Sigma$ is
$$
\|L_\Sigma\| - N(L_\Sigma) = |\Sigma| - 3.
$$
As $\Sigma$ ranges over all possible alphabets, we obtain all values which are at least $-2$.


Updating connections weights in neural networks I am learning about neural networks and have a couple of things I don't understand.

Firstly, in competitive learning I understand that only the neuron with the strongest output is reinforced. That is done in a manners imilar to:

Δwi*j = I(j)*h(i)

Where w* indicates the 'winning' neuron, j indicates the input we are considering, I(j) is the value of such input and h(i) is the sum of all weighted inputs. This is repeated for each connection leading to the winning neuron.

My question is... Why? Why not simply, for example, increase the connection by an arbitrary amount? Or by another function? I have done quite some research, but still can't make sense of this.

Thanks!

You actually can increase it by an arbitrary amount. The reason you are increasing it by the sum of all weighted inputs is so that the number you increment by is actually related to the neural network and the input. At least in that case, what you are incrementing by something that is related to what's going on. Otherwise, the behavior may be more random.

There are several functions you could choose to increment by instead. You could also choose to create new neurons (mitosis) where a neuron exceeds an arbitrary threshold. The method you're following is just another method that is being tested in trying to properly represent neural networks.


LR(0) parsing: how can I know sets of items corresponding to states? I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items corresponding to I1, I2, I3, ... , and I11 can be calculated?

In addition, is closure of item sets related to with calculating them? If so, what exactly every item in I1, I2, ... , and I11 is?

An item is a rule with dot marker in it.  Think of the dot marker as what you've seen so far and what you are hoping to see in the future.  Itemsets are sets of items.  In the diagram above they are the boxes with all the items (nodes in the graph).  The kernel (or core) of an itemset are the rules that are in white.  Those items are given to us (rule 1) in CLOSURE from a different part of the table building algorithm.  Taking closure of all the kernel items gives you the full itemset and includes non-kernel items (the darker ones in your diagram). The CLOSURE(I) operation is this expansion algorithm.

Take I7 for example.  We start with only one kernel item.

T -> T * . F

Step 2 of CLOSURE is saying that since F is in front of the dot we have to expand it, adding those items to the itemset. Hence, we add items the following items.

F -> . ( E )
F -> . id

This is everything that F can expand to.  So the full itemset is now:

T -> T * . F
F -> . ( E )
F -> . id

We reapply rule (2), but see that the . is not in front of any new non-terminals that we haven't expanded, we are done.  The itemset is now closed.

The other half of the parse table building algorithm generates new itemsets.  This involves moving the dot across each symbol of each item.  For example, moving the dot over the 'F' gives you the itemset with the kernel item below.

T- > T * F .

This is I10 in your diagram.  Note, that edges from I7 to I10 is labeled F (since the dot crossed that symbol).  You'd reapply the same closure algorithm here and loop this process.

See the Wikipedia entry on this for more information.


Can maximum matching algorithms be used for maximum weight matching? There are two fast algorithms for maximum matching on general graphs:

Micali and Vazirani in $O(E\sqrt{V})$.
Mucha and Sankowski in $O(V^{2.376})$.

Can these be also used for maximum weighted matching on general graphs? Note that Edmonds' Blossom algorithm can be used to solve both problems.

Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms for maximum weight matching in general graphs.


Give a grammar to show whether a language is regular or context-free I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N},  w \neq w^R\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align}
  S &\to aSa \mid bSb \mid aAb \mid bAa \\
  A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon
\end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?

Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\{w : |w| \equiv 0 \pmod{2}\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.


Parallel Computing: Past Vs Present Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on chip designing e.g power dissipation limits forcing to manufacturers to move to multicore CPUs.

My question is how is the parallel computing different now from what they used to do 30 years back?

30 years ago research into cache-coherent shared memory was just beginning.  There were machines where you could send messages between processors.  By 1983 there were a few (room sized) machines where processors could communicate through a shared memory interface (for example, the Cray X-MP), but they didn't have cache coherence.  Most communication between processors in the early to mid '80s was done using message passing APIs.  Today almost everyone uses the MPI standard for message passing APIs.  The MPI standardization process started in 1992.

Cache-coherent shared memory multiprocessors and shared memory programming (for performance (as opposed to multi-threaded programming, which can be a convenient way to organize programs that need to interact asynchronously with the outside world)) started becoming somewhat common in the 1990s for systems with 10s of processors.  The OpenMP standard for specifying parallel computation in Fortran or C was first published in 1997.  Today (2013) you can buy a shared-memory machine with 8 hardware contexts for a few hundred dollars, and you can buy a shared-memory machine with 10s of hardware contexts for a few thousand dollars.

Hardware offload (to GPUs) started becoming popular when NVidia released the CUDA SDK for their GeForce GPUs in 2007.  The computing model with hardware offload is heterogeneous and in flux (currently some computing is done on the main processor, which tends to be shared-memory, then data gets copied back and forth between the processor and the GPU, some computing is done in the many vector lanes on the GPU, which can share some memory, but also have some private memories, and then the results are copied back to the main processor.) It appears as if most vendors are trying to come up with approaches to make the movement between cpu and gpu more streamlined.

Meanwhile in the last 30 years the advent of techniques to dramatically improve single-thread performance have also internally leveraged a great deal of parallelism.  Deep pipelining, superscalar and branch speculation techniques allow tens of instructions from a single thread to be in flight simultaneously.  Each CPU in the Cray X-MP in 1983 could complete a theoretical peak of 200MFLOPS with a 105MHz clock, whereas a single core today might be able to do 12 GFLOPS with a 3GHz clock.  So, many computations that would have needed to be hand-parallelized 30 years ago do not need to be explicitly parallelized today.


Why can level-triggered interrupts be shared but not edge-triggered interrupts? A key difference between the edge-triggered and level-triggered interrupts is interrupt sharing. Level-triggered interrupts can be shared. Edge-triggered interrupts cannot be shared.

I read the line above in an IBM document. Need help to understand why is it so.

Consider the scenario where an interrupt IS shared by two devices with the following scenario:

Device 1 requests service.
The processor starts serving device 1.
        Device 2 requests service.
Device 1 no longer requests service.
The processor finishes serving device 1.
        The processor starts serving device 2.

Here device 1 will assert an interrupt request in step 1. It de-asserts that request in step 5, but the request remains asserted due to step 3.

Now in step 6, if level triggered requests are used, the processor will service the other device since the request level is still asserted. With edge triggered requests, nothing will happen because there will be no new "edge" to be detected. The request remained asserted throughout the scenario. This is a failure of the interrupt system.

This is why only level triggered interrupts, in general. may be shared.


Symmetry of NP completeness To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to all NP-complete problems.

If both statements above are correct, then the above "proof approach" (showing that "solving X" $\implies$ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X.
In general reductions are not symmetric, so why is this the case here?

[...] an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

Be careful with this! In the context of NP-completeness we work with many-one reductions, not Turing reductions. This means you are not allowed to assume the existence of an efficient algorithm for $X$; this is too strong an assumption since it would allow you arbitrary access to the algorithm deciding $X$. Rather, you must reduce SAT to an instance of $X$. In fact, it is irrelevant whether $X$ can be solved efficiently or not (or even solved at all!). This establishes NP-hardness; for NP-completeness you also need to show $X \in \textbf{NP}$.

Note it is only once you have established NP-hardness of $X$ that you can say the existence of an efficient algorithm for $X$ implies the existence of an efficient algorithm for SAT (or any problem in NP). However, this is only an implication of the NP-hardness of $X$, not the actual requirement for $X$ being NP-hard.


What is the time complexity of this method? On CodingBat.com there's a problem that asks for the length of the longest sequence of repeating characters within a string:

(https://codingbat.com/prob/p179479)

Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same.

maxBlock("hoopla") → 2

maxBlock("abbCCCddBBBxx") → 3

maxBlock("") → 0

This is the solution I wrote:

public int maxBlock(String str) {

  int max = 0;

  for(int i = 0; i < str.length(); i++)
  {
    char c = str.charAt(i);
    int j = i + 1;
    int possibleMax = 1;

    // iterate through a "block"
    while(j < str.length() && str.charAt(j) == c)
    {
      possibleMax++;
      j++;
    }

    // if the block's length is greater than any found, save it
    if(possibleMax > max)
      max = possibleMax;
  }

  return max;
}

The time complexity is at least O(N) but I'm not sure if the while loop inside makes it O(N^2).

The worst-case time complexity is $O(n^{2})$.

Consider the example string "aaaaaaaaaa" — that is, 10 'a's. This happens to be the worse case edge scenario, because j++ has to run for every remaining character in the string, at every position. When i=0, the while loop will run 9 times; when i=1, 8 times; so on until when i=N-1, the loop runs 0 times. Therefore, the total number of times the while loop has to run (over all i) is given by the sum from 0 to N-1, which, with arithmetic series, is $S = \frac{N}{2}(N-1)$. This simplifies to $\frac{N^{2}-N}{2}$; however, when writing time complexity with big-O notation, we ignore constant or slower-growing factors. Therefore, as $N$ grows asymptotically large, the total time complexity reduces to $O(N^{2})$, although in reality it is something closer to $O(\frac{N^{2}}{2})$.

Another way to look at it is that the outer for loop runs exactly $N$ times, and the number of times the inner while loop runs does depend on $N$ (and linearly at that), so the time complexity must be at least greater than $O(n)$.


Limited number of calls to a black box for finding longest path in graph given an access to oracle I'm given a black box that on graph $G = (V,E)$ and integer $0< K<|V|$ outputs $1$ iff there is a simple path of length greater than $K$ in $G$. I want to find the actual edges of the longest path in $G$ using as few calls to my black box as possible.

What I've come up with thus far is using the same method as when binary searching, i.e. first calling my black box with $K = |V|/2$ and so forth, but I'm not really sure what to do once I've found the $K_{max}$.. I'd really want to go in and change the black box to output the actual edges but that's impossible.

Edit: So I can delete any edge $e_i$ from $G$ and see if my black box still returns 1 (once I've found the maximal length path) - if it still returns 1 i know $e_i$ isn't part of the longest path, and if it returns 0 I know $e_i$ is part of the longest path(s) and I append it to my data structure holding the longest path. But what should I do if there are several paths of the maximum length? It feels as if I will return all the edges of all the longest paths and not just one specific.

Since you can find the actual length of the longest path using binary search, in $\log |V|$ steps, I'll assume you have access to an oracle which tells you the length of the longest path. Given a graph $G$ lets denote the length of the longest path in $G$ by $L(G)$.

If you remove an edge after finding out that it does not affect the length of the longest path in $G$, then you avoid the issue of having to commit to some specific longest path. Suppose you keep iterating over the remaining edges, and for each remainning edge $(u,v)$ you check if
$L(G)=L\left(G\setminus\left\{(u,v)\right\}\right)$. If they are equal, remove $(u,v)$ from $E$ and return to the main loop. When there are no more edges to delete, $E$ consists of a longest path in $G$.

To prove this, let $\mathcal{P}$ be the set of longest paths in $G$. Note that in any iteration $i$ (each iteration consists of removing an edge which does not affect the longest path length), there exists some $P\in\mathcal{P}$ such that $P$ is a path in $G_i$. Using this observation, you can show that when there are no more edges to delete, your graph is a longest path.


Closure of regular languages under interchanging two different letters Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For example, if $M$ only accepts $101$, $M'$ should only accept any element from $\{011, 110\}$.
Suppose a string accepted by $M$ has $n$ letters, I tried to construct an FSA with a parallel structure, with initial state $q_0$ that has $\epsilon$ transition to $M_1, M_2, \dots, M_{\binom{n}{2}}$, where each $M_i$ accepts strings with two letters at two unique positions interchanged. The final states should be $F_1, F_2,\dots,F_{\binom{n}{2}}$. Then I may claim that $M'$ should accept their union.
But I am not sure how to construct this parallel structure. Specifically, how should I construct the transition function of this parallel structure that restricts a single interchange only for any $M_i$?

Suppose that you guess that $\sigma$ and $\tau$ should be exchanged, where $\sigma$ appears before $\tau$ (in the original word).
You start reading the input word, letter by letter. When you encounter $\tau$, you can optionally act as if you read $\sigma$. Later on, when you encounter $\sigma$, you can optionally act as if you read $\tau$. From that point on, you accept the word if the original DFA accepted it.
Here is how to implement this in an NFA. Let the original DFA have states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct a new NFA whose states are $\Sigma \times \Sigma \times Q \times \{0,1,2\}$. The initial states are $\{(\sigma,\tau,q_0,0) : \sigma \neq \tau\}$. The final states are $\Sigma \times \Sigma \times F \times \{2\}$. The most complicated bit is the transition function $\delta'$:

For $\kappa \neq \tau$, $\delta'((\sigma,\tau,q,0),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),0) \}$.
$\delta'((\sigma,\tau,q,0),\tau) = \{ (\sigma,\tau,\delta(q,\tau),0), (\sigma,\tau,\delta(q,\sigma),1) \}$.
For $\kappa \neq \sigma$, $\delta'((\sigma,\tau,q,1),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),1) \}$.
$\delta'((\sigma,\tau,q,1),\sigma) = \{ (\sigma,\tau,\delta(q,\sigma),1), (\sigma,\tau,\delta(q,\tau),2) \}$.
$\delta'((\sigma,\tau,q,2),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),2) \}$.


What is the average size of a jump in a binary tree? Assume that a full binary tree is layed out in memory recursively in the following way.
First the Root followed by Tree representation of left subtree followed by tree representation of right subtree.  Assume tree is complete and full.

If a search path requires to go from array location $a[i]$ to $a[k]$, then its referrred to as a jump and its of size $k-i$, since you travelled $k-i$ units of memory.

Given this arrangement of the tree, what is the expected size of a jump in this tree?

Consider a binary search tree with layers $0,\ldots,h$, where layer $\ell$ contains $2^\ell$ nodes. The left child of a node $x$ is located next to it (at distance 1). If $x$ is at layer $\ell$, then its left subtree contain $2^{h-\ell}-1$ nodes, and so the right child of $x$ is at distance $2^{h-\ell}$. These observations are illustrated in the figure:

Here $h = 3$, and the root ($\ell = 0$) has a left child at distance $1$ and a right child at distance $2^{h-\ell} = 8$.

We will calculate the average size of a jump in a random root-to-leaf path. This corresponds to searching for a random leaf.

The expected jump at level $\ell$ is thus $\frac{1+2^{h-\ell}}{2}$. Since there are $h$ jumps overall (at levels $0$ to $h-1$), the average jump is
$$
\frac{1}{h} \sum_{\ell=0}^{h-1} \frac{1+2^{h-\ell}}{2} =
\frac{1}{2} + \frac{1 + \cdots + 2^{h-1}}{h} =
\frac{1}{2} + \frac{2^h-1}{h}.
$$
Since the number of nodes in the tree is $n := 2^{h+1}-1$, the average jump is $\Theta(n/\log n)$. The same holds for the number of leaves $m := 2^h$.


Turing machine that accepts $L = \{a^{n^2} | n ≥ 1 \}$ I have the following language:

  $L = \{a^{n^2} | n ≥ 1 \}$

I am trying to construct a Turing machine that accepts L. My basic idea (without success) is to use a 2-tape TM where in the 2-tape compute the string with length $n^2$. After that, I wish to compare the length of the input string in the 1-tape with the length of the string on the 2-tape.

Note that $1 + 3 + 5 + \cdots + (2n+1) =(n+1)^2$. The input is in unary on one tape, the other tape is a counter, initially containing a single marker. Both heads start at the left of their tapes. A step consists of;

If both heads are at the right end of their markers, quit; input is a square.
Add two markers to the right of the counter tape.
Return to the start of the counter tape.
Advance both heads as long as the counter tape still has unvisited markers.

All you're doing is computing the sum of odd numbers above until you either match the input tape (accept) or exceed it (fail).


Is there a faster algorithm for constructing the adjacency list of this graph? My problem is to find a better algorithm to fill the adjacency list.

specs:

G = (V , E ) //the graph
V ={w} //vertex in this case each vertex is an array
E={⟨u,v⟩| u,v ∈V ∧ u>v} // edge only if u > v
u > v only if  foreach i u̸=v ∧ u[i]≥v[i]. // (u>v and v>w => u>w)

my naive code whit complexity O((v+1)*v/2) ≈ O(n^2) is

private void riempiAdj() {
    for(int i=0;i<nodi.length;i++)
        for(int j=i+1;j<nodi.length;j++)
            if(nodi[i].eMaggiore(nodi[j]))
                nodi[i].adj.inserisci(nodi[j]);
}

nodi is the array of vertex

adj is the adjacency list

AdjList.inserisci(Vertex t) add a vertex t into adjacency list O(1)

Vertex.eMaggiore(Vertex t) returns true in this > t O(1)

exist an algorithm whit complexity of O(v) or O(v*log()v)?

Since the relation is transitive, in the worst case you have $\frac{|V|(|V|-1)}{2}$ edges and so, if you want to add all edges of the graph in the list, you cannot achieve better than $O(|V|^2)$

PS: This problem is similar to an Algorithm project in my University, what a coincidence! ( ͡° ͜ʖ ͡°)


AND operator of many functions Suppose we have a set of functions $f_i: \mathbb Z \rightarrow \{0,1\}, i=1, \dots,n $, with the following property:

For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f_i(x)=0$ and $f_j(x)=1$ for each $j\in \{1,\dots,i-1,i+1,\dots,n\}$. Also, there exists an $x \in \mathbb Z$ such that $ f_i(x)=1$ for each $i$.

Let $x\in \mathbb Z$. In order to determine whether $f_1(x)$ AND $f_2(x)$ AND ... AND $f_n(x)$, is it necessary to compute each $f_i(x)$ until one of these functions is found to be zero or until all functions are found to be one, which would take $\Omega(n)$ time in the worst case scenario?

Added to clarify: The functions $f_i$ are known. The input is $x \in \mathbb Z$.

When $f_i$ are given as black boxes, it takes $\Omega(n)$ in the worst case to compute their AND.

The constraints that the question puts on the functions $f_i$, don't really tell anything about $f_i$ and their behavior, maybe except for a very small subset of inputs. For instance, we can assume that over the inputs $x=0,...,n$ each $f_i$ is 1, except for the case where $x=i$. This satisfies all the constraints stated. But if $x>n$ we have no idea how $f_i$ behaves. As a trivial example, it can be that each $f_i$ has some infinite kernel (=values of $x$ that zeroize it), but the union of all the kernels doesn't cover the entire $\mathbb{Z}$. As a block box, it is not clear that you even have a compact way to describe each kernel, and you have no choice but querying the black box.

Even if the kernel of each function is known (and has a compact description), it can be that the most compact description of their union is "the union of the kernel of $f_1$ and $f_2$ and ...", which hints that one must compute each $f_i$ separately to know their AND value. For instance, if $f_1$ is the indicator function of all the prime numbers, and $f_2$ is the indicator of all odd numbers whose binary representation has an equal number of ones and zeros. Probably simpler examples can be found.


Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium? I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.

However, I understand that maintaining it is a lot of work, which explains why it is not up to date in some cases. By not up to date, I do not mean non-exhaustive, but that better results on some problems are not included.

Does anyone know an equivalent and more specific website focused only on approximation, which would be more up to date ?

I am not really asking the same question as this one, or this one, but I understand that they may bring the same answer.

Remark: The last example I found was on the Minimum Steiner Tree with distance 1 and 2 on complete graphs, which is said to be approximable in 1.28, but there is a paper from 2009 which provides a 1.25 ratio. It may have been updated.

You're expecting too much to expect there to be a single web page that is somehow always updated with the latest in the research literature on the subject.

Let me teach you how to figure out this information for yourself, instead of relying on someone else to have done it for you.  The general approach is to find one paper on the approximability of your problem; then use Google Scholar to track down related papers.

How do you find one paper on the problem?  Perhaps that web page will show you one, even if it's not the latest on the topic.  Perhaps you can search using Google Scholar to find such a paper.  Perhaps you'll have to try other methods.

Then, how do you find other papers on the subject, to find what is the latest and greatest state of the art?  Read the introduction and related work section of that paper, and it should give you an entryway into previous results.  Also, search for that paper on Google Scholar and find what papers cite it; that should give you an entryway into newer results, and you can scan the title and abstracts of those papers to see if they are relevant.  Then, proceed recursively from each paper you've determined to be relevant.


Is $n^2 \log n$ in $O (n^2)$ am confused I graphed the functions and when $n_0$ is greater than $3$, $cg(n)$ is always greater than $n^2 \log n$ so it would seem to me by definition that $m^2 \log n$ is in $O (n^2) $. I tried to prove it by dividing both sides of inequality by $n^2$ . The $c \ge \log n $. As n tends to infinity there will be values of c that are > than logn . I have to say if $n^2 \log n $ is in $O(n^2)$ . My classmate says it isn't to me it looks like it is.  It is 6.00 am here and my brain is mush so apologies if this is a really trivial questions and you are all laughing at my stupidity. It is a little confusing I admit. It seem to me that $n^2 \log n$ above $n_0= 3$ is always greater than $n^2$

$n^2\log(n)$ isn't $O(n^2)$. You need to have a constant $c$, so since $\log(n)$ tends to infinity, for any fixed $c$ you will choose, at some point $\log(n)$ will pass $c$, that is: $\forall n>n_0: c < \log(n)$ for some $n_0$. This directly means that $\forall n>n_0: cn^2  < n^2 \log(n)$ which means that $n^2 \log(n)$ is asymptotically bigger than $cn^2$.


Regularity of a language with odd and even positions containing an even number of 1's Given an alphabet $\Sigma = \{0, 1\}$ and
a formal language $$L = \{ w \in  \Sigma^* |\ |\mathrm{odd}(w)|_1, |\mathrm{even}(w)|_1 \text{are even numbers} \}$$

That means that the number of 1's in the odd and even positions of a given string are always an even number. I've tried using the Pumping-Lemma on a $1^{4n}$ string but to no avail.

Any ideas how I can proove it is not regular. (I strongly assume it isn't regular).

To create the DFA, just start doing it. I assume there is no requirement that the number of elements in the string is even.

You start in the state A. In state A, you have an even number of 1's in the even and odd positions (initially, both counts are 0), so A is an accepting state. To get to an accepting state again, there must be a string following with an even number of 1's in the even and odd positions.

In state A, the next symbol can be 0 or 1. In case of 0, you have the exact same situation again, you need another string following with an even number of 1's in the even and odd positions. So A followed by 0 goes to A.

If the next symbol is 1, then the rest of the string must have an even number of 1's in even positions, and an odd number of 1's in odd positions. That's another state B.

In state B, if the next symbol is 0 then you now need an even number of 1's in odd positions, and an odd number of 1's in even positions. That's a new state C. In state B, if the next symbol is 1 then you now need an odd number of 1's in even and odd positions. That's a new state D.

Now you do the same for states C and D, and you find that whatever the input, you'll end up in one of the states A, B, C and D.

Don't think about "state" as some abstract state in a DFA. Think of it as something that you can describe in words. From any state, which you can describe in words, you get to another state, which you can describe in words again. If you compare those descriptions, and they are the same, then the state is the same.

The case where you don't get a DFA is when the number of states is not finite. For example, for $0^n1^n$, the initial state is "I need any number n of 0's and the same number n of 1's". If you get a 0 then you get a state where you need any number n of 0's and n+1 1's. Another 0 and you need n 0's and n+2 1's. And so on. The number of states is not finite. In your problem, there are only four states needed.

If that's too practical, then given any prefix X of a string in the language L, define the set of suffixes Y such that XY is in the language. Any such set of suffices is a state.  An accepting state is one where the set contains the empty string. The initial state is the set of suffices when X is the empty string. In your case, there are only four different sets of suffices.


What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)? This is a real-world application, not a student assignment.

Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
The boxes have the same height, but variable width.
When a box doesn't fit, it should wrap to the next line (just like text).
After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.

The input is, simply:

double colWidth = …;
List<double> boxWidths = [ … ];

And the output could be:

List<int> result = [ … ]; // Number of boxes in each line.
double minWidth = …;

An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:

| ** *** ***** |
| ** *         |

This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

| ** ***       |
| ***** ** *   |

The result is 2 boxes in the first line, and 3 boxes in the second line: List<int> result = [2, 3]. Widths are now 5 and 8. Difference is 3, and minWidth is 8.

Please note, we cannot change their order. If we could, then the difference would be 1 and minWidth would be 7:

| ** *** *     |
| ***** **     |

My question:

What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines".

https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md
https://github.com/baskerville/paragraph-breaker
https://cs.uwaterloo.ca/~dberry/ATEP/StudentLectures/Ananya.pdf
https://news.ycombinator.com/item?id=1134342
https://www.tug.org/TUGboat/tb21-3/tb68fine.pdf

Remco Bouckaert. "A Probabilistic Line Breaking Algorithm".

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

"Knuth & Plass line-breaking Revisited" in Java
"The linebreaking algorithm of Knuth and Plass" in Java (via Generalized Knuth-Plass Linebreaking Algorithm)
"rosettacode: Word wrap" has implementations of the Knuth Plass algorithm in a variety of languages


What kind of model is used by 20 Questions? Which kind of machine learning concept / model is used in 20 Questions?
Is this kind of thing best solved by a neural network?
Where I can read something about it?

You just play once with it, observe it, and you have the model. Try
something non obvious, or simply cheat with answers.

The game: you think of something, and 20Q asks questions to find what
it is.

They just collect the answers from the players.  They have a
collection of questions that are supposed to discriminate solutions.
They ask questions to users, who chooses among 7 possible answers. Recall that with just 20 yes/no answers, you can discriminate 1 million different objects. And their questions have more answers that just two.
The combinatorics of the answers will identify the right "something"to
be guessed in the available collection. If the thing they are supposed
to identify has not appeared before, they do not find it, recognize
that they lost, ans ask what it is.  Then it goes into the database,
with all the user's answers to identify it the next time.

So they fail, but not twice on the same "something/someone/somewhere"
to be guessed.  Unless users give wrong answers to questions (the
first time, or afterwards ...?).

It is probably slightly subtler, but I doubt it has much artificial
intelligence, neural network or otherwise.  A most elementary and
simplistic form of machine learning, if one dares use the expression
for it.

This is all pure guesswork from what I observed. No idea where you
could read about it. Not sure there is anything worth reading anyway.


Why " every non-prime attribute of R is non-transitively dependent on every key of R" in the original def of 3NF? I have read the definition in of Third_normal_form here
, which shows

  The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.[2] Codd's definition states that a table is in 3NF if and only if both of the following conditions hold:

    The relation R (table) is in second normal form (2NF)
    Every non-prime attribute of R is non-transitively dependent on every key of R.

From the book Database Systems The Complete Book 2nd Edition, key means candidate key.

And I got the definition of transitive dependent here.
So my problem is this:
From the quoted definition, if we denote any non-prime attr as $x$, any key of $R$ as $K$, suppose $x$ is subset of an attributes group $A$, we can easily construct some $A$ satisfied $$K \rightarrow A \wedge A \nrightarrow K \wedge A\rightarrow x  $$ so where am I wrong?

In K→A, the K and A stand for sets of attributes. Let's suppose K is {j, k} and A is {x, y, z}. Then we have

{j, k} → {x, y, z}

Then x is dependent on the key, and that dependency is non-transitive.

A (i.e. {x, y, z}) is not a key for R (we're supposing), so the fact that {x, y, z} trivially Functionally Determines {x} (search for 'trivial' here) does not fall under the 2nd bullet that you quote from wikipedia on 3NF.

You might prefer to work with the Zaniolo 1982 definition that wikipedia gives. Because this is self-contained/doesn't need cross-referring to 2NF. (It'll also help you see the difference to BCNF, sometimes called "twothree-and-a-half Normal Form".)

Be careful to observe that given some set of FDs for a relation, you can derive further FDs, including the trivial FDs. (See Armstrong's Axioms and 'Closure' on the FD's article.) Then the fact that you can derive some dependency transitively which is the same as a non-transitive dependency already given, is just a tautology.

Addit: in response to comments "transitive dependent ... I still need some authoritative expression"

Ok. Looking at the wikipedia definition of 'Transitive Dependency' you have linked to in the q:

  A transitive dependency can occur only in a relation that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation.

Your formula mentioning K, A, x is not "three ... distinct collections of attributes": specifically x is not distinct from A; x is an element of A. Therefore your K → A ∧ A /→ K ∧ A → x does not represent a transitive dependency. But we do have that K→x. Therefore x's dependency on K must be non-transitive.

So in wikipedia's definition of 3NF, its definition of transitive dependency is sloppy.

To put it in sharp focus: imagine your K contains only a single attribute k; imagine your A contains only a single attribute x. Now you can't apply the definition of transitive dependency: R contains less than 3 attributes.


Recognizing waterways in an aerial photo -- polygons from edge detection images I am trying to recognize waterways from aerial photographs (say from Google Maps). Local governments often have GIS data that says where the waterways (and roads, buildings etc) are, but the water data in them is often somewhat inaccurate, and we might be able to improve them using aerial imagery. So we have some data already that isn't always to be trusted.

I know how to do some basic image processing on the data (unfortunately I don't have sample images to show here yet, I'm trying to imagine how I could do this, no working code yet):

I can collect some set of color values using bits of waterway in images, and figure out which pixels are closest to these colors, possibly also for other types of feature (grass, roads, buildings etc). If I set a threshold on which pixels are "close enough", I get a set of pixels that are probably waterways (but there will be a lot of noise).
I can turn the image into grayscale and use a standard edge detection algorithm to figure out where the edges are. Again, this gives me a set of pixels of like boundaries, but there will be noise and edges will be too think and/or have gaps.

What I want to have as output is a set of polygons that outline the probable waterways.

Intuitively I'd like to use the detected edges to create polygons, and the colour information to decide which of them are water, possibly making use of the government data we already have.

Is there a known way to get from the result of an edge detection algorithm to a nice set of closed polygons? Or any other tips on how to attack this problem, if there's a better way?

This is hard to do with color information alone. Color variations between (or even within) aerial and satellite imagery can be huge. Ideally you will want hyperspectral or at least infrared imagery (see this paper).

Assuming your edge detection can snap to pixel boundaries, you can take each pixel's borders as a closed polygon and union them together to form a polygon (depending on your union implementation you may end up with a polygon with inner rings or holes) or a collection of polygons. The Java Topology Suite and other computational geometry implementations can make this much easier for you. If you want to use sub-pixel boundaries you will need to be very careful that you have a good epsilon value set so you can snap edges that are very close but not exactly touching.

If you want to take the edges and combine them yourself you will want to build a graph of intersecting edges and implement code that traverses the graph (e.g. counter-clockwise) to find where it closes in on itself to form a polygon. This is how some of the union implementations of polygons works.


Prove that every CFL is decidable in O(n) space this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was:

  Prove that every context free language $A$ is in $\mathrm{SPACE}(n)$. You can assume that $A$ is given in CNF (Chomsky Normal Form)

I saw CYK algorithm but it's space complexity is $O(n^2)$.

Let $G$ be a context-free grammar in Chomsky normal form. We will show how to determine whether a nonempty word $w$ of length $n$ is accepted by $G$.

Every parse tree for $w$ is first of all a full binary tree with $n$ leaves. It is known that the number of such trees is $C_{n-1}$. Moreover, there is a bijection with words containing $n-1$ pairs of balanced parentheses and full binary trees with $n$ leaves. We can go over all full binary trees with $n$ leaves in space $O(n)$ by going over all words of length $2(n-1)$ over the alphabet $\{(,)\}$, converting each of them which is balanced to a full binary tree.

For each full binary tree $T$, we consider all possible labelings of nonterminals to the vertices of the tree in which the root is labeled using the start symbol, which can be done in $O(n)$ space (here the constant depends on $G$). We check each such parse tree for validity: for each internal vertex labeled $A$ with children labeled $B,C$, we check that $A \to BC$ is a production, and for the $i$'th leaf labeled with $A_i$, we check that $A_i \to w_i$ is a production. If we find a valid parse tree in this process, then $w \in L(G)$. Otherwise, $w \notin L(G)$.


Lambda calculus :Will there be any x left after first substitution? I found the following set of lemma in my lambda calculus textbook :

  Lemma 1.16 Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then

  (a) $[P/v][v/x]M \equiv [P/x]M$ if $v \notin \mathrm{FV}(M)$;

  (b) $[x/v][v/x]M \equiv M$ if $v \notin \mathrm{FV}(M)$;

  (c) $[P/x][Q/y]M \equiv [([P/x]Q)/y][P/x]M$ if $y \notin \mathrm{FV}(P)$;

  (d) $[P/x][Q/y]M \equiv [Q/y][P/x]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;

  (e) $[P/x][Q/x]M \equiv [([P/x]Q)/x]M$.

I am stuck at (e) .I wonder if there is any order to be followed while evaluating this kind of expressions or there isn't any .What I think is that in $[P/x][Q/x]M $ we would replace all the $ x $ in $ M $ by $ Q $ and as such we wouldn't be having any more $ x $ to be replaced by $ P $ . Then there is no point in the the exterior substitution expression ,i.e. $ [P/x] $ . How to explain this ?

After $[Q/x]M$ we no longer find free occurrences of $x$ ... unless $x$ is free in $Q$! The simpler example is $Q=x$, where $[x/x]M=M$ can have free occurrences of $x$.

In such case, the free $x$s due to $Q$ can be replaced by $[P/x]$ in your example.

E.g. $[z/x][(\lambda y.\ x)/x](x(yx)) = ((\lambda y.\ z)(y(\lambda y.\ z)))$.

According to (e) we have indeed

$$
\begin{array}{l}
[z/x][(\lambda y.\ x)/x](x(yx)) \\
= [[z/x](\lambda y.\ x)/x](x(yx))\\
= [(\lambda y.\ z)/x](x(yx))\\
= ((\lambda y.\ z)(y(\lambda y.\ z)))
\end{array}
$$

Finally, note that when $x$ is not free in $Q$, we have
$[[P/x]Q/x]M = [Q/x]M$ as an immediate consequence of $[P/x]Q=Q$.


Indexing a dependent type on a value? If i'm recalling from Robert Harper's lectures Homotopy type theory A dependent type is a family of type index by a type. If we allow index to be just a value can we gain something instead of allowing to be a type ?

Is that the same thing they did in DML?

Wikipedia definition states in this regards :

  A dependent type is a type whose definition depends on a value.

If i have a specification stating : "list of Strings" rather than " a List of Strings of n length", are't i'm still stating something about the value  ? Is this definition enough to distinguish dependent types ? thanks

The best answer I can give is that you are confused about the meaning of words. I tried to explain this already in another answer to you, so let me be more explicit this time.

To say

  type $A$ indexed by type $B$

and

  type $A$ indexed by values of type $B$

is the same thing. People say both of these to mean one and the same thing.

The important thing is to think of $A$ as a function with domain $B$ and codomain $\mathsf{Type}$ (the "type of all types" or a "universe of types"). So, whatever people say and however you are getting confused about "value" vs. "type" here, a dependent type is a function from a type (the indexing type) to the universe of types. Thus:

  A dependent type $A$ indexed by $B$ has as its domain the type $B$, therefore it takes as inputs values of type $B$.

You cannot index a dependent type by just a single value, that makes no sense. That would be like saying "the dependent type of lists of length 7". That is not dependent on anything because "7" is fixed. If you say "the dependent type of lists of length $n : \mathsf{nat}$" that is the same thing as saying "the dependent type of lists whose length is indexed by type $\mathsf{nat}$". Here $n$ is not fixed, it is just a sloppy way of introducing an unecessary variable. To be less sloppy, you would have to say "the dependent type which, for any $n : \mathsf{nat}$, gives the lists of length $n$". This is more correct because it explains that the dependent type is a function taking any $n$ to a type.

I hope that helps.

Just to be sure, let me also say explicitly that in set theory and ordinary mathematics the domain of a function is a set (and not an element of a set). Is that clear?


Shortest path given correct order of colours? I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, c_{2},... c_{n})$. The edge weights $\omega_{v_{a} \to v_{b}}: f(x, y, z)$ are purely a function of three of the four dimensions, as this is a physical problem.

Trouble is, I wish to find the shortest path given a specific sequence of colors (eg. $c_{2}, c_{5}, c_{1}, c_{1}, c_{3}, c_{4}$). It's difficult to incorporate this into the weight function as it is non-physical. Are there well-established path traversal algorithms that find the shortest path through coloured vertices, given the starting vertex, ending vertex, and the sequence it needs to pass through? I wonder if there is already a family of algorithms that describe this problem?
I've considered something like a Hidden Markov Model that abstracts vertices of colours into hidden states, but I am not sure how to prevent one state from being visited again (whereas in a directed acyclic graph I can prevent revisiting the same vertex).

Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that sequence).  Then, find the shortest path in this new graph using any standard shortest-path algorithm.  If all weights are non-negative, you can use Dijkstra's algorithm on this graph; otherwise you can use Bellman-Ford on this graph.
See How hard is finding the shortest path in a graph matching a given regular language?.  Your problem is a special case of the problem solved there.  (Possibly also useful: Product construction for given two finite automata .)
Specifically, here is how the product construction works in your setting.  Let $(c_1,c_2,\dots,c_q)$ be the desired sequence of colors.  Then, for each $k=1,2,\dots,q-1$, you'll have an edge $(x,y,z,k) \to (x,y,z,k+1)$ in the new graph if there is an edge $(x,y,z,c_k) \to (x,y,z,c_{k+1})$ in the original graph; the weight of the edge is copied over from the corresponding edge in the original graph.  Now, find the shortest path from $(x_0,y_0,z_0,1)$ to $(x_1,y_1,z_1,q)$ in the new graph, where $(x_0,y_0,z_0,c_1)$ is the starting vertex in the original graph and $(x_1,y_1,z_1,c_q)$ is the ending vertex in the original graph.


About the behaviour of multi-layer perceptrons I have a multilayer perceptron. It has an input layer with two neurons, a hidden layer with an arbitrary number of neurons, and an output layer with two neurons.

Given that randomboolean and targetboolean are random boolean values, and the network operates as such:

input(randomboolean); //Set the input neurons to reflect the random boolean
propagateforwards(); //Perform standard forward propagation
outputboolean = output(); //To get the networks output
ideal(targetboolean); //Performs connection updating via back-prop

Is it possible to get the network to map the randomboolean value to the targetboolean value in such a way as the the outputboolean value will correctly match the targetboolean while running in an 'on-line' (where prediction occurs along with continued learning) mode after some arbitrary number of training cycles.

I hear that the network needs to be recurrent to process this as it may be temporal behaviour, however the MLP is a universal computing platform and I assume it should be able to approximate the temporal behaviour needed for this task.

The answer is no. What you want to do is to predict randomness. The perceptron network takes randomboolean(true/false) and it outputs outputboolean(not random!!). The random generation of targetboolean is independent from the generation of outputboolean.

Perceptrons generally learn functions. If you have $f(A)=B$ and $f(A)=C$ and $B\neq C$, then $f$ is not a function.

EDIT: To predict temporal behavior you should add some time dependent variable in the input of the network.


Finding a minimal subset of strings whose bitwise OR is the all ones string Consider we're given a set $S\subset \{0,1\}^n$ and we want to find a minimal subset $A \subset S$ under the property that if we bitwise OR all of the strings in $A$ we get the all ones string $1^n$. I have been having trouble finding a polynomial time algorithm for this or finding evidence that one doesn't exist (e.g.- by showing this problem to be NP-Complete). Does anyone have any ideas or references which may help answer my question?

This is the set cover problem, a well-known NP-complete problem, in disguise.


Computing Von Neumann Entropy Efficiently The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as probabilities. So $S(\rho) = -\sum_k \lambda_k \lg \lambda_k$.

Clearly the Von Neumann entropy can be computed by first extracting the eigenvalues and then doing the sum. But extracting eigenvalues is quite expensive. Is there a faster way to compute the entropy?

(For example, computing the sum of the eigenvalues is much easier than computing the individual eigenvalues. You just return the trace of the matrix. The product of the eigenvalues, the determinant, is also easier to compute than the individual eigenvalues. Is there also a shortcut for the entropy?)

A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix to sum the results of applying that polynomial to each of the eigenvalues.

(The polynomial-via-power-and-trace thing works because density matrices have orthogonal eigenvectors. Raising the matrix to a power will raise its eigenvalues to that power. Then the trace gives you the sum of the eigenvalues at that power.)

Sounds fun. Not going to let the paper spoil it.

The derivatives of $f(x) = x \ln x$ are:

$$\begin{align}
f^0(x) &= x \ln x\\
f^1(x) &= 1 + \ln x\\
f^2(x) &= x^{-1} \\
f^3(x) &= -x^{-2}\\
f^4(x) &= 2 x^{-3}\\\
f^5(x) &= -6 x^{-4}\\\
...\\
f^k(x) &= (-1)^k \cdot (k-2)! \cdot x^{1-k}
\end{align}$$

The derivatives don't always exist at $x=0$, but they do at $x=1$, so we can make a Taylor series from there:

$$\begin{align}
x \ln x &= \sum_{k=0}^\infty \frac{(x-1)^k}{k!} f^k(1)
\\
&=
(1 \ln 1)\frac{(x-1)^0}{0!} + (1 + \ln 1)\frac{(x-1)^1}{1!} +  \sum_{k=2}^\infty \frac{(x-1)^k}{k!} (-1)^k 1^{1-k}(k-2)!
\\
&=
x - 1 + \sum_{k=2}^\infty \frac{(1-x)^k}{k(k-1)}
\end{align}$$

So now we have a nice series $\frac{(1-x)^1}{-1} + \frac{(1-x)^2}{2} + \frac{(1-x)^3}{6} + \frac{(1-x)^4}{12} + \frac{(1-x)^5}{24} + ...$ that we can approximate by cutting off at some index $c$. Except that would converge like $O(c^{-1})$ when $x=0$, so we should probably try to account for the excess when the numerator is stuck at $1$:

$\begin{align} x \ln x
&=
x - 1 + \sum_{k=2}^\infty \frac{(1-x)^k}{k(k-1)}
\\
&=
x - 1 + \sum_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum_{k=c}^\infty \frac{(1-x)^k}{k(k-1)}
\\
&\approx
x - 1 + \sum_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum_{k=c}^\infty \frac{(1-x)^{\Huge c}}{k(k-1)}
\\
&=
x - 1 + \left( \sum_{k=2}^c \frac{(1-x)^k}{k(k-1)} \right) + \frac{(1-x)^c}{c-1}
\end{align}$

Here's a graph of the difference between $x \ln x$ and the approximation when $c=10$:

And voila, just write code to evaluate that polynomial over the eigenvalues by using traces of the matrix powers:

import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)
    result -= numpy.trace(power) / (cutoff - 1)
    return result / math.log(2)  # convert from nats to bits

The convergence is still kinda terrible near $x \approx 0$, though. I tried replacing the last correction with some doubling steps like this:

import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)

    # Twiddly hacky magic.
    a = cutoff
    for k in range(3):
        d = (a+1) / (4*a*(a-1))
        result -= numpy.trace(power) * d
        power = power.dot(power)
        result -= numpy.trace(power) * d
        a *= 2
     result -= numpy.trace(power) / (a-1) * 0.75

     return result / math.log(2)  # convert from nats to bits

And that improved things a bit more, so that the maximum offset vs $-x \ln x$ across the [0, 1] range was $3.5 \cdot 10^{-3}$ instead of $2.9 \cdot 10^{-2}$ (for the given cutoff of 10).

(The plot is reversed.)

Of course, the paper I linked at the start of the answer probably has a much better polynomial.

For example, my error analysis should have been in terms of the total entropy instead of the individual value. And I should have used tricks like computing the trace of $AB$ from $A$ and $B$ in $O(n^2)$ time without doing the multiplication. And I should have thrown some simulated annealing at the coefficients.


What is the difference between finite automata and Büchi automata? as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented.

From an assignment I'm working on, this automaton can be depicted as both infinite automaton and Büchi automaton.

Can you give me an example for each of those automatons to understand the differences?

There is no difference in the specification (syntax). The only difference is in the interpretation (semantics). The language accepted by a DFA consists of finite strings defined in a certain way given the DFA, and the language accepted by the corresponding Büchi automaton consists of infinite strings defined in a certain way.

Indeed, you can leverage this connection to prove results such as:

  An $\omega$-language is recognizable by a deterministic Büchi automaton iff it is the limit language of some regular language.

For a proof, see Wikipedia.


Proving Monotonicity of Softmax Layer In the book here: http://neuralnetworksanddeeplearning.com/chap3.html

If you scroll down to Exercise 2 in the Softmax Section, it says

  Show that $\partial a^L_{j}/\partial z^L_{k}$ is positive if $j=k$ and negative if $j \neq k$. As a consequence, increasing $z^L_j$ is guaranteed to increase the corresponding output activation, $a^L_j$, and will decrease all the other output activations.

Here,
$$a_j = \frac{e^{z^L_{j}}}{\sum_{k}{e^{z^L_{k}}}}$$

I managed to prove the part when $j \neq k$ by differentiating as normal to get
$$-\frac{e^{z^L_{j}}}{\left(\sum_{k}{e^{z^L_{k}}}\right)^2}$$

which is obviously always negative. However I'm having trouble with when $j=k$.
When I differentiated I got an inequality which simplified to proving
$$\sum_{k}{e^{z^L_k}}>1$$
I am unsure of how to do this.

Let's remove the $L$ superscripts. The derivative with respect to $z_L$ is
$$
\frac{\partial a_j}{\partial z_j} =
\frac{e^{z_j} \sum_k e^{z_k} - e^{z_j} e^{z_j}}{\left(\sum_k e^{z_k}\right)^2} =
\frac{e^{z_j} \sum_{k \neq j} e^{z_k}}{\left(\sum_k e^{z_k}\right)^2} > 0.
$$


Constructing languages in NPI other than through Ladner's Theorem I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP.  However, I was wondering if there are any other constructions using the fact that sparse sets cannot be NP-complete assuming P $\neq$ NP (Mahaney's Theorem).  Specifically, is it definite (assuming P $\neq$ NP) that the intersection of an infinite decidable sparse set and an NP-complete language lies in NPI? It seems to me that it cannot be in P, but I don't know how to prove it. (Note: I am asking about taking a given NP-complete language and its intersection with a sparse set, not about $\textsf{NPC} \cap \textsf{SPARSE}$ which must be empty, again by Mahaney's Theorem.)

It is perfectly possible that the intersection of an infinite decidable sparse set and an NP-complete set lies in P. Take your favorite NP-complete set $L$, and consider $L' = 0L \cup 1^*$, which is still NP-complete. The intersection of $L'$ with the infinite decidable sparse set $1^*$ is $1^*$, which is certainly in P.

Mahaney's theorem shows that sparse sets cannot be NP-complete, but to construct an NPI language you will need to show that your sparse set is not in P, which will probably require diagonalization. Your diagonalization will somehow have to ensure that the resulting language is sparse, while still being in NP and outside of P. Perhaps this can be done, but I'm not aware of any such proof. (That said, my knowledge of the relevant literature is sparse.)


What is meant by "uneven spacing" on number line when dealing with floating point numbers in computers? I read some examples online on this subject, but none of them really gave an explanation. When I visualize the number line all I can see is evenly spaced numbers, I'm not grasping the notation of "uneven spacing" when It comes to plotting the floating point values from a machine's perspective. Perhaps I am thinking about this too literally.

Let's look at a single-precision floating point number (as specified by IEEE 754). It is made up of 32 bits. Therefore, there are exactly $2^{32}$ floating point numbers that dots the number line.

What does it mean when we say that the floating point numbers are "unevenly" distributed on the number line? It means that they are not uniformly distributed. But why?

Well, let's consider the case where these numbers are distributed uniformly on the number line. Then there's some constant finite gap between successive numbers, $\Delta$. Since there are $2^{32}$ points on this line, then these uniformly distributed numbers span an interval of $\Delta \times 2^{32}$ width.

How big is $2^{32}$? Well, it's about 4 billion. Do you see the problem with uniformly distributed representations of numbers? If you want to even be able to represent the number $\pm 2$ billion in your uniform system, then you need to make sure that both $-2 \times 10^9$ and $2 \times 10^9$ are within your representable interval. Therefore, we need $\Delta \times 2^{32} \ge 4 \times 10^9$, so that we must space our numbers around $\Delta \approx 1$ apart. But if $\Delta \approx 1$, how are you going to represent both $1$ and $0.5$ precisely? Their difference is smaller than the gap!

Herein lies the rationale for having non-uniformly distributed representations such as floating point numbers. Uniformly distributed representations (or fixed-point numbers) cannot represent both big numbers and small numbers in a "good-enough" manner.


Closure of CFL against right-quotient with regular languages Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$.  Show that if A is context free and B is regular, then $A/B$ is context free.

My interpretation of this is is that we need to show that if a string $wx$ is accepted by a CFG, and we know that $x$ is accepted by a regular language (and therefore is also accepted by a context-free language), then $w$ must also be accepted by a CFG.

My initial thought on how to solve this would be a proof by contradiction in which we assume that $A$ is context free, $B$ is regular, and then assume that $A/B$ is not context-free.  Since $A$ is context free, we can construct an equivalent PDA that accepts $A$.

From here, my thought was to take an arbitrary $wx$ that is accepted by $A$, such that $x \in B$.  We can then construct another PDA based on the first that only accepts $wx$.  We could then break the PDA into two pieces: one that accepts $w$ and one that accepts $x$ (with the two pieces concatenated together).  Since there then would exist a PDA that accepts just $w$, and $w$ is arbitrary insofar as $wx$ was arbitrary, $A/B$ must therefore be context-free after all (contradiction).

Will this approach work? (Is this a good general approach?)  If so, how would I go about breaking the PDA that accepts $wx$ into chunks formally?

Imagine you have a pushdown automaton (PDA) $X$ for $A$ and a DFA $Y$ for $B$.

You want to build a PDA $Z$ for $A/B$. You can do as follows:
the states $Q_Z$ of $Z$ are $Q_X\times Q_Y$. There are two phases:

Phase 1: You just read the input word and advance in $X$, states of $Y$ are ignored. This corresponds to the word $w$ of your language.

Phase 2: When you reach the end of $w$, you are allowed to perform $\epsilon$-transitions in order to reach an accepting state of $X\times Y$. So you guess a word $x$ that will continue to advance in $X$ and start to advance in $Y$, and that has to reach acceptance in both automata simultaneously. If there is an accepting run of this automaton, then the input word $w$ is in $A/B$ since you guessed the witness $x$ (and vice-versa, if $x$ exists, then it can be guessed by your automaton $Z$).

The reason why $B$ has to be regular instead of CFL is that you cannot manage two stacks at the same time, if you want to stay CFL.


Introduction into first order logic verification I am trying to teach myself different approaches to software verification. I have read some articles. As far as I learned, propositional logic with temporal generally uses model checking with SAT solvers (in ongoing - reactive systems), but what about first order Logic with temporal? Does it use theorem provers? Or can it also use SAT?

Any pointers to books or articles for beginners in this matter is much appreciated.

After reading your question the only way I could see and had enough knowledge to tie the topics together was to give a hi-level set of articles that drill down from software verification ending up with trying to unite model checking and theorem proving. Hopefully my comment did that:

Take a look at Software verification  then Formal verification then Model checking  and Formal Software Verification: Model Checking and Theorem Proving

Dave has given a good answer for which I cannot do much more justice to the first part of the question than Dave had done, since I am also new to this.

Since this is your first question at an SE site, the reason I did not give an answer but a comment is because here an answer cannot be just a set of links, but must give a written answer and use links in support of the answer; thus a comment instead of an answer.

With regards to:

  Any pointers to books or articles for beginners in this matter is much
  appreciated.

Books I would suggest and use are:

Logic in Computer Science - Modelling and Reasoning about Systems 2nd Ed. by Huth and Ryan This introduces logic and moves up to model checking, but doesn't go into theorem proving. So this should cover all of your basic questions related to logic and model checking.
Principles of model checking by Baier and Katoen I just started reading this one, and it is much better than reading lots of papers and trying to see how they all fit together. This is one of the most, if not the most recommended book on the subject of model checking. It should answer your more advanced questions on model checking.
Temporal logic and state systems by Kroger and Merz I often like to have books by different authors when self-learning a subject. This one is to complement/round out "Principles of model checking"
Handbook of practical logic and automated reasoning by Harrison Being a programmer I can't recommend this book enough. The book starts off with introducing logic and moves all the way through the point of creating the kernel for a theorem prover based on the work of HOL Light. Just to highlight that the book uses working OCaml code, explains the theorems in terms I find friendly and gives you what you need to know but not so much that you can't make the connection or feel like you are running down side tracks. If is a very focused book on going from logic to a specific type of theorem prover.
How to prove it : a structured approach by Velleman To get into the Proof assistants for theorem proving you will need to live and sleep theorems.
A Introduction to Proofs and the Mathematical Vernacular by Day This is a free book that not only complements "How to prove it", it goes beyond it in sum regards. I would not be surprised to see this one become popular.

At present I cannot expand more on theorem proving because I am still learning the pro/cons and differences of each one, but the ones I am focusing in are

HOL Light because of the book by John Harrison.
Coq because it is based on Calculus of constructions
Isabelle because it is based on higher-order unification.

These proof assistants also typically have book(s), are current, popular, open-source, maintained, and have active support communities.

Note: I used worldcat.org to reference the books, but you can review them using Amazon's look inside feature.


Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices
So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?

Considering the strongly connected component is a good start if graph $G$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.

Here is the outline of an algorithm that does the job.

Find one root $r$ of $G$ by repeatedly going to the ancestor of a node. Mark $r$ as an wanted vertex.
Remove all vertices reachable from $r$.
Go to step 1 unless there is no more vertex.
return all vertices that are marked as wanted.

Exercise. Given a directed graph (that may have cycles), describe an algorithm that finds a minimum set of vertices from which all vertices can be reached. (Hint, strongly connected components are useful now. Try reducing the problem to the current question.)


Petri nets boundedness I want to ask about petri net(PN) boundedness. When I have a state s1 = (2 0 0) then i  find state s2 = (2 0 1) so since s1 < s2 can I declare PN as NOT bounded ? Because when  I have this PN:

PN is bounded but u can find there (2 0 0) < (2 0 1).
So my question is. Am I wrong about boundedness of petri net or is something wrong with PT on the picture ?

For the given Petri Net, the number of tokens for P_1,P_2  and P_3  is represented by m_1,m_2  and m_3  respectively. Based on the definition of boundedness of a Petri Net by Popova-Zeugmann (2013), the given Petri Net is bounded because m_1 ≤ 2,m_2 ≤ 2 and m_3 ≤ 2. In other words, there is a natural number (2 in this case) such that the number of tokens in P_1,P_2  and P_3  never exceeds the number.

I am also providing an example of an unbounded Petri Net and an example of a bounded Petri Net. Regardless of the initial marking, the Petri Net in Figure 1 is not bounded (or it is unbounded) because m_0 → ∞ when T_0  keeps firing.

For the given initial marking, the Petri Net in Figure 2 is bounded because m_0 ≤ 1 and m_1 ≤ 2. In general, the Petri Net in Figure 2 is bounded: let the initial value of m_0 = q_0  and the initial value of m_1 = q_1; m_0 ≤ q_0  and m_1 ≤ 2q_0+q_1

References

Popova-Zeugmann, L. (2013). Chapter 2 The Classic Petri Net [Electronic version]. Time and Petri Nets. Berlin; Heidelerg: Springer-Verlag.


How to answer multiple queries efficiently? I am given a $N$-length integer array. For each integer, I am given 4 values:

$$[\mathit{left},\mathit{right},t,\mathit{value}]$$
$$1\leq \mathit{left},\mathit{right},t\leq N$$

For each query, I have to find the sum of values which have $x$ in the range $[\mathit{left},\mathit{right}]$ and that satisfy $t\leq t_1$.

Example query: $x=5$, $t_1=4$.

So I have to find out sum of all the values satisfying $\mathit{left} \leq 5 \leq \mathit{right}$ and $t \leq 4$.

When the value of $t_1$ is not present you are just given weighted intervals from left to right with weight value, and you should ask questions of the form, what is the sum of the weights of intervals that contains x.

If we know all intervals/weights before hand this whole task is easy without any fancy data structure, just adding the beginning of the interval with weight +value and the end with weight -value and accumulate all such values. The answer will be constant in intervals and to find the value at $x$ you can binary search for the interval that contains $x$. Will not go deep into this solution since it will not allow us to solve the problem when $t_1$ constraint is used again.

Assume we don't know all intervals before hand and we have a mix in of, add new interval, find sum of all intervals containing $x$. You can solve this problem using segment tree with lazy propagation to add a value on intervals fast, and query sum on points (actually with segment tree you can query in intervals but it isn't required here). Both queries are done in $O(log N)$ where $N$ is the number of intervals.

Let's call all given intervals in the input updates. To solve the problem with $t_1$ back, sort all queries and updates by $t$ value. And process them in such order. When you are processing each query of type $(x, t_1)$ only intervals with lower $t$ are present in the data structure, so we have an instance of the previous problem, ask for all intervals containing $x$, whenever you get an update, add it to the data structure.

This solution is offline, since you require to know all queries beforehand. This can be solved online using persistent segment trees. The overall complexity of the solution described here is $O((N+Q) log N)$.


How to show all possible implied parenthesis? Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ?

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

I am not able to find out the right states for the recursion to proceed. As at any point we wouldn't know if it would have two open parenthesis or two closed parenthesis. I am just looking for ideas.

I'm assuming the input expression does not contain parentheses.

The idea is that for each binary operator we pick it as the principle operator (which is at the root of the parse tree) and split the expression into two subexpressions.
Then we solve the subproblems recursively.
After that we combine those solutions prepending and appending parens and inserting the principle operator in the middle. Notice that there could be multiple solutions for both subproblems.

Also you need to figure out the base case for recursion.


Why classification represents all computations? I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me if I'm wrong) Turing machine  could do any computation that is possible to compute. But for all examples in computing, what my instructor takes are classification (deciding whether the input has a certain characteristic or not) problems.

Does being able to classify anything mean you can do any computation? For example, addition subtraction etc? What is the connection between classification and computation in general?

I referred few books but I couldn't find an answer. Please help.

Thank you,
PPG

First, you're not entirely correct when you say that a "Turing machine could do any computation that is possible to compute". What you're referring to is known as the Church-Turing thesis and it's not a statement of fact, but more like a statement of confidence. A better way of stating it would be "Any task that we would agree would be described as 'computation' can be accomplished by a TM". This wouldn't be true or false until we could somehow formalize the part "... we would agree  would be described as computation ...".

One reason that we have for being confident in the C-T thesis is that people have come up with many apparently different ways of modeling what we call computation and in every case it has turned out to be the case that anything that these models can do can also be done by a TM.

Take, for instance, addition. While your instructor may not have shown you, it's not difficult to build a TM that when given two (binary, say) representations of integers, produces on its tape a representation of the number that is the sum of the two original inputs. Any text I know of includes examples of such computations and there are literally hundreds of online examples of TMs that can add, subtract, multiply, compare numbers, and do other tasks that we'd call computation.

In a sense, you can do these computational tasks without explicitly showing how as long as you can decide whether an input string was in a language, which is what you mean by "classification". The classification problems you've seen take the form, I suspect, of "Given a language $L$, make a TM that determines whether of not an input string is in the language". These decision problems are just disguised forms of what you've described as "computation".

Here's an example: Suppose you had a language, $A$, consisting of all triples, $(x,y,z)$ where $x,y,z$ were binary representations of integers such that $x+y=z$ and you had a TM, $M$, that when given any such triple, could decide whether or not that triple was in $A$ or not. From this TM, you could make another, $M'$, that would do addition. All it would have to do to add $x$ and $y$ would be to try all possible strings $z$ and for each one use $M$ to decide whether $(x,y,z)$ was in the language $A$. Sure, it would take a long time to come up with an answer, but once you hit upon the right $z$, all that $M'$ would have to do would be to write the $z$ it found on its tape.

That equivalence, between classification and computation, gives some justification for the apparent approach your instructor has adopted (though a weak justification, in my opinion). My advice to you would be to search out some examples of computation, like addition, that would give you an idea about the tasks TMs can do.


How to search an almost sorted array faster than O(n) time? Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1.

Develop an efficient recursive algorithm to find j such that A[j] = z, where A[1] ≤ z ≤ A[n]. The algorithm must be more efficient that O(n).

Binary search was my first thought but you would still have to search through both halves because it doesn't have to be from low to high.

Let's say you have n = 100, $a_1 = 50$, $a_{100} = 100$, and $a_{50} = 73$. You would then know that the range from $a_1$ to $a_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a_{50}$ to $a_{100}$ contains all numbers from 73 to 100, and maybe some others.

I think binary search will actually work, if the number you are looking for is within the interval from the first to the last array element. You will always know one half which must contain the number you are looking for, and one half which might contain the number so obviously you search the half that must contain it.

If the number is outside that range, you may have to check every single item: You could have $a_i = 0$ for every $i$ except $a_k = 1$. You can examine $n-1$ items $a_i$ which are all 0, and you still don't know if 1 is in the array or not; the one remaining element could be $-1$, $0$ or $+1$.