Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF) I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e
..." lines denoting which variables are to be existentially quantified and which variables are to be universally quantified.

For instance, a simple QDIMACS input such as:

p cnf 2 3
a 1 0
e 2 0
1 2 0
-1 0
-2 0

...would be correspond to the formula $\forall x \exists y \ (x \lor y) \land \neg x \land \neg y$ where $x$ and $y$ range over $\{T, F\}$. SAT is an instance of QBF where all the variables are existential.

The above is an example of 2QBF, where we have two layers of quantifiers. A more complex QDIMACS problem with alternating quantifiers might be:

p cnf 2316 15282
e 1 17 2 18 3 19 4 ... 0
a 1598 1599 1600 1601 1602 1603 0
e 65 81 66 82 67 83 68 ... 0
a 1610 1611 1612 1613 1614 1615 0
e 193 209 194 210 195 211 196 ... 0
a 1616 1617 1618 1619 1620 1621 0
-2 -18 0
-3 -19 0
-4 -20 0
-5 -21 0
-6 -22 0
-7 -23 0
...

Anyways, on to my question. I don't understand why 2QBF != QBF. It seems to me for any formula $F$ and variables $x$, $y$ ranging over the booleans that $\forall x \exists y \ F$ is equivalent to $\exists y \forall x \ F$.

To demonstrate my thinking, I will consider the Shannon expansion of the universal quantifier.

\begin{align}
\forall x \exists y \ F \iff& (\exists y \ F[x \to T]) \land (\exists y \ F[x \to F]) \\\\
\exists y \forall x \ F \iff& \exists y \ (F[x \to T] \land F[x \to F])
\end{align}

Suppose $\exists y \ (F[x \to T] \land F[x \to F])$ is satisfiable. Then the same assignment would extend to both $\exists y \ F[x \to T]$ and $\exists y \ F[x \to F]$.
Suppose $\exists y \ (F[x \to T] \land F[x \to F])$ is unsatisfiable. Then at least one of $\exists y \ F[x \to T]$ or $\exists y \ F[x \to F]$ is also unsatisfiable.

Thus $\forall x \exists y \ F \iff \forall y \exists x \ F$.

A similar question has been asked before here, but there appears to be ambiguity over the domain of the quantifiers. They should range only over true or false and not over other mathematical objects or propositional variables. This is in correspondence to the standard interpretation of the SAT problem.

For instance, $\forall x \exists y \ x \leftrightarrow y$ would not be true since setting $y$ to $x$ is not valid.

Is my interpretation of QBF correct? Is there a counterexample I'm missing?

Let me first give a concrete example of a formula $F(x,y)$ such that $\forall x \exists y. F(x,y)$ is true, but $\exists x \forall y. F(x,y)$ is false.
I'll then address the expansion of the universal quantifier in your question.

Take $F(x,y)$ to be a formula expressing the equality $x \oplus y = 1$, where $\oplus$ denotes exclusive-or.
We can explicitly write $F$ as $$F(x,y) = (x \land \neg y) \lor (\neg x \land y).$$

To see that $\forall x \exists y. F(x,y)$ is true, let $x$ be given and take $y = \neg x$.
Then $x \oplus y = x \oplus \neg x = 1$.

To see that $\exists x \forall y. F(x,y)$ is false, first take $x = 1$. Then for $y = 1$, we have that $F(x,y)$ is false, i.e., $F(1,1)$ is false.
By the same reasoning, $F(0,0)$ is false, so there is no $x$ such that $\forall y. F(x,y)$ is true.
Hence $\exists x \forall y. F(x,y)$ is false.

Your mistake is in the following argument.

  Suppose $\exists y\ (F[x \to T] \land F[x \to F])$ is unsatisfiable. Then at least one of $\exists y\ F[x \to T]$ or $\exists y\ F[x \to F]$ is also unsatisfiable.

The point is that $\exists y\ F[x \to T]$ and $\exists y\ F[x \to F]$ may both be satisfiable, but the choice of $y$ which satisfies them may be different.
In order to satisfy $\exists y\ (F[x \to T] \land F[x \to F])$, you must find a single value of $y$ that satisfies both $F[x \to T]$ and $F[x \to F]$ simultaneously.
This may not be possible, even if it is easy to satisfy one of $F[x \to T]$ and $F[x \to F]$ individually.

It may be helpful to expand your argument using the example I gave to see exactly where it breaks down.


Iterated multiplication of permutation matrices Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where

$m=\mathit{poly}(n)$
$m=\mathit{poly}(\log n)$ which means $m=O(\log^k n)$ where $k\in\mathbb N_{>1}$
$m=O(\log n)$?

Given $\mathit{poly}(n)$ inputs it is clearly in $\mathit{AC}^0$ to test the promise every input matrix is a permutation.
On other hand general iterated matrix multiplication is is $\mathit{NC}^2$.

Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.


Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution) Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?

(Thanks to many comments below, which suggest (and are invalidated by) the last update of this question)

There are lots of NP-complete problem where no algorithm will find an optimal solution - during your lifetime. Given the choice between a greedy algorithm that finds a solution quickly which is often good, and an algorithm that will find a guaranteed optimal solution, but not while you are waiting for it, what are you going to use?


How does O transform this sum like that? I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too.

I don't understand the math in CLRS section 6.4 where they go from:

$$ \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} O(h) $$

to:

$$ O\left(n \sum_{h=0}^{\lg n} \frac{h}{2^h}\right). $$

I understand that the $n$ is moved out to before the sum. But how does the remaining $1/2^{h+1}$ become $h/2^h$?

Intuitively, the $O$ can swallow any constant factor. Here, we do so because the sum we get is on the cheat sheet and we can proceed more easily.

Formally, we need to apply the definition of $O$, once in either direction. I do not think the first term makes a whole lot of sense. What the authors probably mean is

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)$

with some $f \in O(h)$. Then it remains to note that

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)
  \quad\leq\quad \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot c \cdot h
  \quad=\quad \frac{c}{2} \cdot n \cdot \sum_{h=0}^{\lg n} \frac{h}{2^{h}}$

for all $n \geq n_0$, with $c,n_0$ the constants from $f \in O(h)$ (unfold the definition).
Applying the definition again concludes the proof.

Note that if we had $f \in \Theta(h)$, we would get a similar lower bound and could thus show a $\Theta$-bound for the sum.


Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)? Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.

Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $x,y\in (\Sigma \cup N)^*$ and $\mathcal{S}(G)$ are the sentential forms of $G$.

Given $G$, I'd like to determine a set $C = \{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \}$.

To clarify, in this case, $w, x, y, z, a, b$ are strings of terminals and non-terminals and $b$ is of length one.

I can see how to do this if $a$ is also of length one; each $b$ is a member of the follow set of $a$ (including non-terminals).

However, I am curious if it's possible for a sequence of characters. For my application, the string $a$ is not much longer than the right hand side of the productions in $G$.

The distinction between terminals and non-terminals is somewhat mute in my application because I am using a generative grammar; and I believe that this won't lead to much trouble since $b$ is of length one.

I'll describe an algorithm that works. It's running time shouldn't be too bad. You can precompute quite a bit of this as well.

I'll assume that $a$ does not contain nonterminals (though it's probably easy to adapt to that case) and that you don't know $x$, $y$ or the derivation of $a$. I'll also assume your grammar doesn't contain productions that are never used in any derivation ($A \rightarrow A$ for example).

The main issue really is to parse $a$, as you want to know what kind of states you end up in, so you know what can follow $a$. This is not so easy as you don't know $x$.

We use an adaptation of Earley's algorithm. You'll want to understand that algorithm first. Our algorithm works in almost the same way, except our initialization and completion steps are different.

For the initialization, we seed our first set with an Earley item for every occurrence of $a_1$ (the first character in $a$) in any production of your grammar. We set the back pointer of this item to -1, an invalid value. This is important in our modified completion. Essentially, the -1 means 'I have no idea where this production was started'.

Now, we perform the Earley algorithm separately for every possible such initial Earley item. We can't simply do all of them at the same time, as the parses may interfere with each other. I can't easily see a faster method than backtracking here.

For the completion step, we only have to make a modification to handle -1 back pointers. As we've completed a production whose origin we don't know, we are in trouble. However, the method used to compute $LALR(1)$ lookahead sets by Pennello and DeRemer saves us: what we need here is exactly the $LALR(1)$ lookahead sets. Every item in these lookahead sets has a corresponding position in the grammar, which in turn corresponds to a possible continuation of the completed production.

Unfortunately, I don't really see any other choice than to backtrack once again here. For every position in the lookahead set, you perform the completion step with this position, and continue the parse from there. You do this separately for every parse. Note that if your grammar is $LALR(1)$, your lookahead will uniquely determine which position you have to go to, so you don't have to backtrack.

You continue the above algorithm one character beyond $a$, where you consider this extra, virtual character to be the 'any character', which immediately gives you the 'follow' set you are looking for - any time the scanner phase finds something for this final set, you can add this character to your answer set.

Edit: I think I've found the method that removes most of the overhead introduced by the backtracking. We associate with every Earley item a set of identifiers, which are strings, as we will need to use prefixes of these identifiers. On initialization, we add all initial items to the Earley set, and associate a unique identifier with every set.

On the scanner and predictor steps, identifiers are carried over to new items. Earley items in the same Earley set that only differ in their identifiers are merged together by merging their identifiers together. Note that we can perform scanner and predictor steps on these new items with identifiers, without having to perform this step for every identifier separately.

The completer considers the identifiers separately, and only completes an item if the corresponding item in the earlier itemset has an identifier that is a prefix of the identifier. For every possible completion (so for every item in the $LALR(1)$ lookahead set), we append a unique character to the identifiers of the completed items.

Essentially, we do the backtracking using these identifiers, so that we don't do double work in the scanner and predictor steps.


How does a computer remember the address of a data variable in a program, in the main memory? Suppose I write a program as below:

int main()
{
int a = 3;
int b = 4;
return 0;
}

Suppose the computer stores the address of 'a' as 0x00104. How does it associate 'a' with 0x00104?

Suppose the computer stores the address of 'a' as 0x00104.

No, 'computer'(?) nowhere stores the address of 'a'. Compiler or assembler converts source code into object modules. Those object modules have instructions and data. 'a' is symbolic address which is bound by compiler to relocatable address. The linkage editor or loader in turn bind the relocatable address to absolute address. So, there is no storage but binding. Note that the absolute binding can be done at either compile time, load time or execution time where relocatable address binding will be done in any case by the compiler.


Are all functions with constant space complexity in $REG$? The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?

A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation graph as one big finite automaton.


Why doesn't the string match the root? From Reading 17 of 6.005 — Software Construction:

Exercise Reading a Grammar 4:
Which strings match the root nonterminal of this grammar?
root   ::= (A B)+
A      ::= [Aa]
B      ::= [Bb]

aaaBBB

abababab

aBAbabAB

AbAbAbA

Answer: 2 and 3

So far so good.

Exercise Reading a Grammar 3:
Which strings match the root nonterminal of this grammar?
root    ::= integer ('-' integer)+
integer ::= [0-9]+

617

617-253

617-253-1000

---

integer-integer-integer

5--5

3-6-293-1

Answer: 2, 3, and 7

In the last question, why doesn't integer-integer-integer match the root if it can be our first step, i.e.
root ⇒ integer-integer-integer
Sure, it would not be the end of the story (i.e. it would contain some non-terminals) but neither was aBAbabAB in the question above and yet it was accepted as a string that matched the root.
Many thanks!

In the text, they seem to suggest that there is a way of quoting characters so that they can be used as terminals even if they have the visible form as a non-terminal. One common quoting form is quotes ('B') which is illustrated.

Character classes ([bB]) are another quoting form. The B in that character class cannot be a non-terminal because it is precisely a character. So the non-terminal B, although it looks very similar, is distinct, and the Bs in the strings are characters, necessary by the definition of string they are using.


Probability of Success in Slotted Medium Access Suppose you have a network which uses time division multiplexing (i.e. Slotted Aloha). There are $N$ nodes each transmitting in a given slot with probability $p$.

I understand that the probability a node is successful in a slot is $p(1 - p)^{N-1}$. This is just a geometric distribution. But our book then says that the probability there is success in a slot (i.e. no collisions) is $Np(1-p)^{N-1}$.

I don't understand:

What the difference between the two probabilities (how is the probability that a node is successful in a slot different from the probability of success in a slot).
Why you need to multiply the probability by the number of nodes $N$ since $p(1 -p)^{N-1}$ gives you the probability that one node transmits and all other nodes don't transmit. Could it be because this is the probability that node might transmit given that all other nodes don't transmit, which isn't guaranteed. But we want to find the probability that any of the nodes transmit when all other nodes don't transmit - hence the multiplication by $N$?

There is a clear explanation given in these lecture notes MIT course Digital communication systems (read by H. Balakrishnan and G. Verghese).
The specific part that you require is this>

If each node sends with probability $p$, then the probability that exactly one node sends in any given slot is $Np(1 − p)^{N−1}$.
The reason is that the probability that a specific node sends in the time slot is $p$, and for its transmission to be successful, all the other nodes should not send. That combined probability is $p(1 − p)^{N−1}$. Now, we can pick the successfully transmitting node in $N$ ways, so the probability of exactly one node sending in a slot is $Np(1 − p)^{N−1}$.


Is the exponent in floating point numbers signed or unsigned This may be sound like a stupid question, because, of course, it can be negative and, as Wikipedia states:

  A numeric variable is signed if it can represent both positive and negative numbers, and unsigned if it can only represent non-negative numbers (zero or positive numbers).

But is it really? Because it doesn't work like normal signed integer, because doesn't really have a sign, it's just an unsigned integer starting at a negative point, it seems to me. I guess the first character could indicate whether it's negative xor positive / zero.

For people who don't remember CS class:

exponent of -127: 0000 0000
exponent of zero: 0111 1111
exponent of one:  1000 0000
exponent of 128:  1111 1111

This is mostly a matter of interpretation. For IEEE 754 floating point numbers (one of the most common implementations), an exponent bias is used:

  In IEEE 754 floating point numbers, the exponent is biased in the engineering sense of the word – the value stored is offset from the actual value by the exponent bias. Biasing is done because exponents have to be signed values in order to be able to represent both tiny and huge values, but two's complement, the usual representation for signed values, would make comparison harder.

  To solve this problem the exponent is biased before being stored, by adjusting its value to put it within an unsigned range suitable for comparison.

For floating point numbers with single-precision, the effective exponent has 8 bits and ranges from -126 to 127. However, the internal exponent ranges from 1 to 254, meaning that 127 has been added to the effective exponent.
(This means it is valid to say that the exponents of floating point numbers are stored as unsigned integers, even though this is a matter of interpretation.)

In addition to the reasons outlined above, another good reason for this encoding is that two special exponents are required for floating point encoding according to IEEE 754: Floating point numbers can also store the values Infinity, NaN and denormalized values which would be too small to store them in the usual format.

The special constants used are the internal exponents $0$ and $2^r-1$ (where $r$ is the number of bits of the exponent), so in binary $0...0$ and $1...1$. These values are easy to recognize. Note that these exponents belong to effective exponents that are barely ever used. If we had used the internal exponent $0$ without shifting the range, it would be the same as the effective exponent $0$, making it difficult to encode common number ranges.


Is it possible to submit every March Madness bracket? A few years ago Warren Buffett started offering $1 billion to anyone who could correctly predict the winner of every game in the NCAA men's basketball tournament. A 64 team (we won't count the first four play-in games) single-elimination tournament bracket like "March Madness" has 2^63 possible bracket combination, putting the odds of correctly predicting a perfect bracket around 1 in 92 quadrillion.

But what if I don't want to leave this up to chance or skill? If I wanted to submit all 2^63 possible brackets to ensure that I submitted a winner, how improbable is this? I see two limiting factors - computational time and storage space, although I might argue that this is possible.

My question is two-fold:

Given current computing limitations, how long would it take to compute all possible brackets? Particularly, how long would it take to compute one bracket, and how quickly could the fastest computer compute them all?
How much space would storing these brackets take, and is it a feasible amount of storage?

For 2, my guess is that it's a lot of data, but it's feasible. A bracket can be represented by 63 bits, each bit representing a game in the tournament and the 1 or 0 signifying whether the high or low seed won. Thus we have 2^63 brackets, each at 7.875 bytes each, for a total of roughly 72.6 exabytes of data. Given that Google is estimated to have between 10-15 exabytes of data, this is an absurd amount of data but not out of the realm of storage possibility.

The rate-limiting factor is the cost of submitting each of those $2^{63}$ combinations.  Since submitting a combination probably requires (at minimum) opening a network connection and sending the combination to a remote server, you can generate combinations a lot faster than you can submit them.  Similarly, the cost of storing the submissions is probably negligible compared to the time it takes to submit them all.

In particular, if it takes one second to submit a proposed combination, it will take you $2^{63}$ seconds to submit all $2^{63}$ of them.  That's about 21 times the age of the universe.  If it takes you one millisecond to submit a single combination, it will take you $2^{63}/1000$ seconds to submit them all -- that's about 300 million years.  Obviously, not possible within your lifetime.

Also, note that the contest rules specified a maximum of one entry per person, as well as a maximum of 15 million submissions (not 15 million per person; 15 million total -- once there have been 15 million combinations submitted, the contest closes). Consequently, your proposed strategy simply wasn't possible.  The creators weren't dumb: presumably, they thought of that and made sure it wouldn't happen.


Right moving turing machines and FSA's I stumbled upon the following post while learning about turing machines:

Right moving turing machine

I kind of understand the intuition behind why a TM that only moves to the right works like a FSA but I can't think of a general way to create a let's say DFA (or NFA, doesn't really matter) which accepts the same language as a given right moving TM.

So my question would be:

Given an only right moving TM $M$, what would be a general method for constructing a DFA $D$ such that $L(M) = L(D)$?

Alternatively, given an only right moving TM $M$, how to construct a NFA $N$ such that $L(M) = L(N)$?

As Yuval indicated in the comment, a right-moving TM is already essentially a FA. Here's the construction:

Given a TM move rule $\delta(q, x)=(p, y, d)$ where, as usual, $q$ is the current state, $x$ is the contents of the current cell, $p$ is the new state, $y$ is the symbol replacing $x$ in the current cell, and $d$ is the direction to move the head. Since the machine can only move right, it is immaterial what gets overwritten on the current cell and since $d$ is always move right, we can ignore both of these, leaving us with moves of the form $\delta(q, x)=(p)$, i.e., the moves for a FA.

The construction above is for a DFA, the one for a NFA is essentially the same.


What is the relation between Time Sharing operating systems and Round Robin CPU scheduler? So i have asked this before, but i still didn't get my answer so I'll try to make my question more clear this time :

Based on my O.S book, Time sharing operating systems switch between processes very fast using a time slice and it uses interrupts when the time slice ends and switches to another process, so isn't this the definition of round robin CPU scheduling algorithm? so are they saying Time sharing O.S uses Round Robin cpu scheduling or what?

if not, then what is the relation? for example what happens if our O.S is time sharing and uses Round Robin cpu scheduling vs when it uses another algorithm like FCFS?

No.  A time-sharing computer switches between processes in some way or other.  A time-sharing computer with round-robin scheduling switches between processes in a particular way.  For instance, suppose there are three processes, A, B, and C.  A round-robin scheduler would switch between them in the order ABCABCABCABC etc.  Some other scheduler might switch between them in the order AABAABAACAABAABAAC (for instance).  Both are examples of time-sharing, but the latter is not a round-robin scheduler.

I suggest reading https://en.wikipedia.org/wiki/Scheduling_(computing).


Can we create faster sort algorithm than O(N log N) I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$

Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort this given array. The clear solution is to sort the array using the classic merge sort algorithm, which works in $O(N \log N)$ time and space complexity. I was thinking that this trick can improve the complexity.

Let $N_{1} = 10^5$, clearly $N = 10\cdot N_{1}$. Let's split the array $A$ in $10$ smaller array where each array consist of $N_{1}$ elements and sort those $10$ arrays with standard merge sort ( time complexity: $O(N_{1}\cdot\log N_{1})$), so we have 10 arrays where each array is sorted, we can merge those 10 array into one array in time complexity $O(N\cdot\log(10))$ using priority queue.

So the total complexity will be $O(10 \cdot N_{1}\cdot\log N_{1} +N\cdot\log(10))$. Now let's say we split the array in $\sqrt{N}$ arrays, so the complexity will look like: $$O(\sqrt{N} \cdot \sqrt{N} \cdot \log \sqrt N + N \cdot \sqrt N)\\ = O(N \cdot \log (\sqrt N) + N \log (\sqrt N))$$

Is everything in my algorithm correct, and is this trick efficent in memory usage?

You got a result of $O(N\cdot \log(\sqrt N)+N\log(\sqrt N))$.

But $\log \sqrt N = (\log N)/2$, so $N⋅log(\sqrt N)+N·\log(\sqrt N) = N·\log N$. So not only is it the same complexity class, where constant factors don't matter, it is even the same function, therefore the same constant factor.

But the underlying reason for any comparison based sorting algorithm to take $O(\log N)$ comparisons is that there are N! possible permutations of the array elements, each comparison can rule out at most half the possible cases, so you absolutely need at least $\log_2 N!$ comparisons in the worst case, which is $O(N\cdot  \log N)$. That $\log_2 N!$ is not a big-O, it is an absolute number. You cannot achieve for example $0.999 \log_2 N!$ comparisons in the worst case.

So you would have to come up with an algorithm that isn't based on comparison. For example, if an image contains pixels using 24 bits each, then you can sort the $N$ pixels of an image in $O(N)$ (see "The Player of Games" for reasons why you would want to sort all the pixels in a large library).


What's wrong with this LL grammar? (very short) S --> Ta | b | Sc
T --> Tc | λ

This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never manage to do make it an LL grammar. Can someone please help by making it a LL grammar? It isn't that big and I'm very confused.

First note that $T = c^*$ (using regular expression syntax). We can therefore rewrite your grammar to:

S --> c*a | b | Sc

Rewriting even further, we can say that $S = (c^*a | b)c^*$, so $S$ is regular. It is not hard to come up with a grammar for this language:

S --> T a T | b T
T --> c T | λ

More generally, when trying to rewrite grammars to $LL$ form, one first removes left recursion using standard techniques (for instance here). Then one tries to remove any conflicts that are left, for which no general techniques are known - just try to figure out what the conflict means, and try to solve it accordingly.


Check if a row is in the span of a matrix Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:

A xor B xor C = 1

A xor B xor D = 1

X xor A xor Z = 0

etc...

For a new external row, I want the ability to tell if it is a linear combination of the rows of the matrix, or not. I could do this by computing the augmented matrix, and solving it with Gaussian Elimination.

For example I want to know if this is true or not:

X xor B = 1

Now, suppose I have a lot of rows to test (8 billions). I do not wish to recompute a new augmented matrix each time. I heard there is a way to compute the echelon form once and use it to determine whether a given row is in the span of the matrix or not, but I cannot figure out how.

How easy is it to determine whether a given row is in the span of a matrix in echelon form?

Let your vector be $x$, and let the first row be $r$.

If $x_1 = 1$ and $r_1 = 0$, then $x$ is not in the span.

If $x_1 = 0$ and $r_1 = 1$, then $r$ cannot be part in any linear combination that results in $x$, so we can remove $r$ and continue.

If $x_1 = 0$ and $r_1 = 0$, then we can remove the first column and continue.

If $x_1 = 1$ and $r_1 = 1$, then for $x$ to be a linear combination of the rows, $r$ must be one of the rows in the linear combination. So we can replace $x$ with $x \oplus r$, remove the first row and column, and continue.

You can also present this algorithm in an iterative manner.

Let $i$ be the index of the first $1$ in $x$. For $x$ to be in the span, there must be a row whose first $1$ is also at index $i$. Find this row $r$, replace $x$ with $x \oplus r$, and continue, until eventually $x = 0$.


What's the best algorithm to find the shortest path between 2 vertices in a graph? Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?

At least in theory, the most appropriate algorithm is breadth-first search (BFS), which you execute by starting from your source vertex $s$. Once the BFS traversal hits your target vertex $t$, you halt and trace back a chain of predecessors originating from $t$. This procedure runs in linear time, which is optimal.

However, from a practical standpoint, the answer might depend on the topology of your graph. For instance, some other linear time procedure like a bidirectional search can be much more efficient but this is more challenging to determine apriori.


Bounds on update time in the RMQ problem subject to $O(1)$ query time? In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $A_i \leftarrow x $.

My question is : How fast can we update if we must answer queries in $O(1)$?

I can think of a solution which works in $O(\sqrt{n})$ per update :

We can answer queries in $O(1)$ using a sparse table. Since each element is a part of $O(n)$ ranges in the sparse table, we can clearly update a sparse table of an array of size $n$ in $O(n)$. Now, divide into $\sqrt{n}$ blocks. For each block, maintain the prefix and suffix minimums and also a sparse table. Clearly, a block can be updated in $O(\sqrt{n})$. On the upper level, maintain another sparse table which can answer minimum over a range of blocks. Clearly this can also be done in $O(\sqrt{n})$  and the query time is still $O(1)$. The memory used and precomputation done are both $O(n \log{n})$.

Can we do better, say $\text{polylog}(n)$, perhaps using more memory and/or precomputation? Is there a known lower bound?

You can divide the whole range into $n^{\frac{1}{3}}$ blocks, and for each block apply your $O\left(\sqrt{n}\right)$ approach. Then you can get $O\left(\sqrt{n^{\frac{2}{3}}}+n^{\frac{1}{3}}\right)=O\left(n^{\frac{1}{3}}\right)$ update time with constant query time.

Recursively, you can get $O\left(n^\epsilon\right)$ update time with constant query time for any constant $\epsilon>0$.


Graph ordering with smallest max vertex "discrepancy" Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.

Define the cost of an ordering of a graph to be:

$$\text{cost}(G,f) = \max_{(u,v) \in E} f(u)-f(v)$$

(I refer to $f(u) - f(v)$ in the title as "discrepancy" to avoid confusion with terms such as length or distance)

Intuitively, if we were to construct $G$ by adding on one vertex at a time and adding the appropriate edges to the already-existing vertices, the cost is how far back in our list of vertices we'd have to go and add edges to.

Question: How difficult is the problem of minimizing this cost? Is there an efficient algorithm for finding an optimal ordering? Also is there a name for this cost that i'm not aware of?

Ideas:

A BFS ordering can do arbitrarily bad on this problem: Consider a complete binary tree -- the optimal cost is $O(\log N)$ but a BFS ordering can cost up to $O(N)$.

A DFS ordering can do arbitrarily bad on this problem: Consider a path graph modified such that each vertex is connected to an additional leaf vertex -- the optimal cost is $2$ but a DFS ordering can cost up to $O(N)$.

Your problem is known as BANDWIDTH. Another way to describe it is: we are given a matrix, and we want to rearrange the rows and columns (in the same way!) so that the only non-zero entries lie across a narrow band around the diagonal.

BANDWIDTH is known to be NP-complete. Unger showed that it is NP-hard to approximate to within any constant factor.
Feige gave an $\tilde{O}(\log^3 n)$-approximation algorithm which uses metric embeddings.

Among the many variants of BANDWIDTH, let me mention the MINIMAL LINEAR ARRANGEMENT problem (known by various other names), in which the goal is to minimize $\displaystyle\sum_{(u,v) \in E} |f(u)-f(v)|$ rather than $\displaystyle\max_{(u,v) \in E} |f(u)-f(v)|$.


Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently? First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.

As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (https://en.wikipedia.org/wiki/Integer_factorization) puts it,

  When the numbers are very large, no efficient, non-quantum integer
  factorization algorithm is known; an effort by several researchers
  concluded in 2009, factoring a 232-digit number (RSA-768), utilizing
  hundreds of machines took two years and the researchers estimated that
  a 1024-bit RSA modulus would take about a thousand times as long.

So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.

The time it takes the code to check if a number is prime doesn't grow exponentially with the input.

function[]=prime(n)
tic
f=floor(sqrt(n));
for i=2:f
    if rem(n,i)~=0
        b=0;
    else
        b=1;
        disp(i)
        break
    end
end
if b==0
    disp('prime')
else
    disp('not prime')
end
toc
end

And so I go back to the question in the title. What is wrong with my reasoning?

Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm.

Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time proportional to $\sqrt{10^d} \approx 3.16^d$, i.e. exponential in $d$, the number of digits. That is by no means "fast" and grows very quickly as the numbers get larger.

It is polynomial with respect to the value of $n$, but not with respect to the size of $n$. This behavior is called pseudopolynomiality.

The "fast" prime testing algorithms use much more sophisticated approaches which can not be modified (easily) to also give a factorization. They just report yes/no whether the number is prime. The AKS primality test uses time proportional to $d^6$.


Anonymous Visibility Check in P2P networks I'm working on a problem for a P2P network for games. The problem is the following:
Consider two opponents on a grid, each stores it's own position.
Player 1 wants to know if it sees player 2. In other words, if player 2 should send it's positional data to player 1 without revealing it’s position in the process.

The problem is sort of obvious, in order to know if player 2 should send it's data it needs the position of player 1, thus player 1 has to reveal it's position. I'm wondering if anyone knows about a system which does this visibility check anonymously, without revealing the position of players.

Right now I have an algorithm/policy which only reveals if player 1 is above, below, to the left or to the right of player 2 but does not reveal the exact coordinates of player 1 to player 2. It's based on the homomorphic properties of certain cyphers, but this is still a big limitations in certain games, especially first person shooters where knowing the approximate direction of your enemy can be very helpful? Note, I am NOT looking for fully homomorphic cryptography here, only something which can solve this specific problem of checking whether a point is inside of a "visibility field" or not without revealing positional (or visibility field) information.

This question might be a stretch since there probably isn't such an algorithm out there, but I thought I'd ask anyway :)

Ok, so after realizing my previous solution didn't work I've put this problem on ice for a while, but now I have one in which I am fairly confident. If you find any obvious flaws, please let me know. This is the first time I'm answering a question, and I'm trying to be as transparent as possible where all my ideas came from so that anyone can find errors easier. Thus my answer will be quite long.

To start with, I've limited it to determining if the distance between two players (two points) is bellow a certain therhold. It can however be extended to a vision field.

My current solution relies on a homographic encryption which can do addition (such as Paillier).
To start with I note the expression which I ultimately want to evaluate, which is the distance between two points being within a certain distance:
\begin{equation}
(x_a -x_b)^2 + (y_a - y_b)^2 - d < 0
\end{equation}
However, since the distance you want to check will in many cases be very similar for both players, your opponent can make good guesses as to what $d$ is, which means your opponent has access to a boundary on your position (one equation, two unknowns in a 2D environment). Thus we need to add a slight modification to avoid this, and ultimately evaluate the following equation:
\begin{equation}
r(x_a -x_b)^2 + r(y_a - y_b)^2 - rd < 0
\end{equation}
The multiplication of $r$ here does not change the truth value of the expression, but it does add one unknown, thus the only constraint we can get is that the unknown point is on a plane, which does not add any new information.

In order to use the additive homographic property of our encryption we need to fully expand this equation:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd < 0
\end{equation}
Let us assume that we are player b. We have access to $x_b$ and $y_b$ and we are going to be choosing $r$ and $d$. From the equation above it's then obvious that player b needs information about $x_a$, $y_a$, $x_a^2$ and $y_a^2$, thus player a will now encrypt those values and send them to player b, together with the public key to for the encryption.

Here comes my breakthrough, player b is only able to do addition with the encrypted values we received from player a, thus the terms $rx_a^2$,$ry_a^2$,$-2rx_a x_b$,$-2rx_a x_b$ are impossible for player b to compute. However, if we restrict r to be integers player b can compute $rx_a^2$ and $ry_a^2$ by simply adding $x_a^2$ and $y_a^2$ to themselves $r$ times. In practice this would be multiplying the encrypted values $r$ times (assuming we use Paillier encryption).

This only leaves $-2rx_a x_b$ and $-2rx_a x_b$, which we can solve by letting player a do the actual multiplication. If player b sends:
\begin{equation}
-2rx_b
\end{equation}
\begin{equation}
-2ry_b
\end{equation}
Player a can preform the multiplication. However, we run into the same problem in the beginning, now player a can put a constraint on the position, since we are sending two equations and three unknowns, thus we need to modify what we send to keep our information hidden. Thus player b instead sends:
\begin{equation}
-2rx_b + C_1
\end{equation}
\begin{equation}
-2ry_b + C_2
\end{equation}
Where $C_1$ and $C_2$ are integers. Since they are integers, and we know they are going to be multiplied by $x_a$ and $y_a$ we can do the same trick as before and account for this in our addition of the encrypted values.

Thus the last thing to work out is what to encrypt and send back, which is rather easy. We simply have to account for the added $C_1$ and $C_2$ and subtract them. Thus player b sends:
\begin{equation}
\mathcal{E} (rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2)
\end{equation}
Where $\mathcal{E}$ stands for "encrypted". There's a note to be made here about speeding up the computation of $\mathcal{E} (rx_a^2)$ which using a naive approach would require us to do $2r + C_1 + C_2$ encryption computations, however this can be sped up considerably by simply adding the newly encrypted sum to itself, thus making the process exponential and reducing the computations down to somewhere above $ log_2 (r) + log_2(max(C_1,C_2))$, but this is only important for the implementation. Later I will represent this type of multiplication with $\times$.

Let's now look at all the transactions which take place:

Player b sends a request to Player a (this step can be skipped if the transactions are continuous)
Player a sends $\mathcal{E}(x_a)$, $\mathcal{E}(y_a)$, $\mathcal{E}(x_a^2)$, $\mathcal{E}(y_a^2)$ and  $\mathcal{E}$.
Player b sends:

$r \times (\mathcal{E}(x_a^2) \mathcal{E}(y_a^2))\mathcal{E}(rx_b^2) \mathcal{E}(ry_b^2)\mathcal{E}(-rd) C_1 \times \mathcal{E}(-x_a) C_2 \times \mathcal{E}(-y_a)$
$-2rx_b + C_1$
$-2ry_b + C_2$

Player a then:

Decrypts the encrypted part to get $[rx_a^2 +x_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2]$
Multiplies $-2rx_b + C_1$ and $-2ry_b + C_2$ with $x_a$ and $y_a$ respectively.
Adds this all together to get:
\begin{equation}
[rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2] + x_a[-2r x_b + C_1] + y_a[-2r y_b + C_2]
\end{equation}
which Equates to:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd
\end{equation}
Player a checks if this value is smaller than 0, if so player a sends it's position to player b, if not it sends a "false" message.

I hope this answer was clear, or at least understandable. When I used the [ ] brackets it was only to notate what came as one number, so from the perspective of player a, everything inside of a bracket is just one number.

A thing to note here is that it's player a can still cheat by just refusing to send the position ( and Player b could for example send vision checks where he shouldn't), but this sort of cheating can be caught by keeping a log of all player positions (and vision checks) throughout the game (or a subset of them to save memory) which when the game is over, or enough time has passed, can be used to verify that neither player was cheating. If a player disconnects suddenly they can just be asked to send their log when they go online again, thus sudden disconnects is not a problem either.


Graph where only two vertices have the same degree Let's say that $N$ is the number of vertices. We want to create a graph where only two vertices have the same degree. For what kind of $N$ is this possible?

I tried it and I've been able only to come up with such where $N$ is $3$ and $4$.

It is possible for every $N\ge 2$. We can prove it by mathematical induction.

For $N=2$, it is trivial.

Suppose there is such a graph for $N=n$, there are following two cases:

No vertex has degree $0$.
There is a vertex with degree $0$.

In case 1, we just add an isolated vertex. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

In case 2, no vertex has degree $n-1$. We add a vertex with edges to every vertex in previous graph. The new node has degree $n$. The degree of each vertex in previous graph is added by $1$, thus no one in the new graph has degree $n$. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

So such graph is possible for $N=n+1$.

As a conclusion, it is possible for every $N\ge 2$.

If you only care about connected graph (i.e. no vertex has degree $0$), the result is the same while the proof should be revised somewhat: the new graph for $N=n+1$ is constructed via first constructing an intermediate graph for $N=n$ from the graph for $N=n-1$ (this intermediate graph has a vertex with degree $0$), then constructing the graph for $N=n+1$.


Easy to state open problems in computability theory I was searching for interesting and easy to state open problems in computability (understandable by undergraduate students taking their first course in computability) to give examples of open problems (and obviously I want the students to be able to understand the problem without needing too much new definitions and also be interesting to them).

I found this list but the problems in it seem too complicated for undergraduates and will need spending considerable time giving definitions before stating the problem. The only problem I have found so far is

  Is Diophantine problem over rational numbers decidable?

Do you know any other interesting and easy to state open problem in computability theory?

One famous open question about the poset $(D, \leq_T)$ of Turing degrees is whether it has any non-trivial automorphisms. That is, does there exist a non-identity bijection $f\colon D \to D$ such that $a \leq_T b $ if and only if $f(a) \leq_T f(b)$?.


Usage of stacks and heaps in object-oriented programming. Reasons? In object oriented programming heaps are used for to store the actual objects. Stacks are used for storing reference-variables to the objects.

What's the concrete reasons for choosing those two specific data-structures?

What benefit has a heap in the described scenario? What benefit provides a stack?

I am not sure if choosing stacks/heap is related with object oriented programming. The stacks are adopted by many programming languages because they are perfect fit for scoped variables, e.g. create new stack frame at the beginning of a function, and discard it when leaving. They don't always store reference variables, but actual objects. In C++, you can allocate objects on stack and they will be destroyed when the control exits the scope.
While stacks are often used with scopes, which determines the variables lifetime, heaps are used for objects that live longer without predefined lifetime.


Show that { xy ∣ |x| = |y|, x ≠ y } is context-free I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?

Anyway, here's the question:

  Show that the language $L = \{xy \mid |x| = |y|, x\neq y\}$ is context free.

Claim: $L$ is context-free.

Proof Idea: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary.

Proof: For sake of simplicity, assume a binary alphabet $\Sigma = \{a,b\}$. The proof readily extends to other sizes. Consider the grammar $G$:

$\qquad\begin{align}
  S &\to AB \mid BA \\
  A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\
  B &\to b \mid aBa \mid aBb \mid bBa \mid bBb
\end{align}$

It is quite clear that it generates

$\qquad \mathcal{L}(G) = \{ \underbrace{w_1}_k x \underbrace{w_2v_1}_{k+l}y\underbrace{v_2}_l \mid |w_1|=|w_2|=k, |v_1|=|v_2|=l, x\neq y \} \subseteq \Sigma^*;$

the suspicious may perform a nested induction over $k$ and $l$ with case distinction over pairs $(x,y)$. Now, $w_2$ and $v_1$ commute (intuitively speaking, $w_2$ and $v_1$ can exchange symbols because both contain symbols chosen independently from the rest of the word). Therefore, $x$ and $y$ have the same position (in their respective half), which implies $\mathcal{L}(G) = L$ because $G$ imposes no other restrictions on its language.

The interested reader may enjoy two follow-up problems:

Exercise 1: Come up with a PDA for $L$!

Exercise 2: What about $\{xyz \mid |x|=|y|=|z|, x\neq y \lor y \neq z \lor x \neq z\}$?


The time complexity of finding the kth smallest number using buckets I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where current is a value starting possibly at 64 (for 64 bits integers at most) and decrements each iteration by 4 (nibble size).

I was wondering what is the time complexity (worst) of this implementation. I think it's O(n^log64/4) which is O(n^16), is that correct?

function nthSmallest(array, k, sizeOfInt) {
    let buckets = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
    // put numbers in buckets - O(n)
    for (let i = 0; i < array.length; i++) {
        const high = (array[i] >> sizeOfInt - 4) & 0xF; // 4 = nibble size
        buckets[high].push(array[i]);
    }
    let numbers = [];
    for (let i = 0; i < buckets.length && numbers.length < k; i++) {
        if (numbers.length === k - 1 && buckets[i].length === 1) {
            return buckets[i][0];
        }
        for (let j = 0; j < buckets[i].length; j++) {
            numbers.push(buckets[i][j]);
        }
    }
    return nthSmallest(numbers, k, sizeOfInt - 4);
}

Your algorithm is a variant of the radix sort.

Consider $k=n$ and the greatest two numbers differ by only the least 4 significant bits, then the two greatest numbers will be always in the last buckets in each iteration except the last. This means you have to iterate for sizeOfInt, sizeOfInt - 4, ... until 4, so the overall complexity is $O(nw)$ where $w$ is sizeOfInt.


Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language.

I'm just not sure how to use their properties to formally show this. Thanks for all the help in advance.

Hint: If $A$ is context-free and $R$ is regular then $A \cap R$ is context-free.


Find longest overlapping interval Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of [1..O(n)], preprocess $S$ so we can efficiently answer the following query:
Given an interval [i,j] output the interval from $S$ that has the longest overlap with [i,j] (i.e., their intersection is as large as possible). Note that [i,j] may or may not be one of the intervals in $S$.

It is relatively easy to get all overlapping intervals. You store an array Endpt[1..n] such that Endpt[t] equals the rightmost endpoint of all intervals in the set that begin at location t. You ask repeated Range-maximum queries on the range 1..j. As long as the answer is >j, you are getting an overlapping interval. This takes O(#answers) time since range-max is done in O(1) time.

The challenge of this question is that we want a more efficient way to find the interval with the longest overlap. To this end, we can consider 3 cases:

intervals that begin before i
intervals that end after j
intervals that begin after i and end before j (i.e., that are contained within [i,j]).

For case 1, we can query Endpt array for range-max in the range 1..i-1 and find the longest overlapping interval of type 1 efficiently.
Similarly, for case 2 we can store a Startpt array and query for range min.

Case 3 has me stumped.  We could store a length array for all intervals, and ask for the range-max in i..j; however, this will not give the longest overlapping interval, since there will be intervals that begin after i and end after j.  Is there a way to efficiently preprocess $S$ so that, given [i,j], we can efficiently find the longest interval contained within [i,j]?  Or is there some other efficient way to solve the original problem?

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array on the interval $[l, l']$ gives you the answer.


What does one mean by addressing capability of a microprocessor? I read in a book that the Intel 80286 microprocessor has an addressing capability of 16 MB. Does this mean it can process 16 MB of data at a time? Please explain what is actually meant by addressing capability.

It means that the CPU can access 16MB of memory directly, since each memory address is 24 bits long. This is although the registers are only 16 bits long (the trick is the segment registers).


Testing if a given DAG is a lattice I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice?

In other words, I need to test whether any two vertices have a unique least upper bound and greatest lower bound.

From brief browsing, I found an $O(n^3)$ algorithm that explicitly computes the least upper bound of every pair of elements. Is there a better test?

The DAG represents the covering relation $\lessdot$ of a partial order $<$, also known as its Hasse diagram. An element $y$ covers an element $x$, in symbols $x \lessdot y$, if $x < y$ and no $z$ satisfies $x < z < y$.

Suppose that $Y$ is a non-empty set of elements in the partial order which is upwards closed (if $z \in Y$ and $u > z$ then $u \in Y$), and in which any two elements have a join. Let $y \notin Y$ be such that $Y \cup \{y\}$ is also upwards closed. Then for all $z \in Y$,
$$
z \lor y = \min_{y \lessdot u} z \lor u,
$$
if the minimum exists.
(This is Lemma 1 in Fast recognition of rings and lattices by Goralcik, Goralcikova, Koubek, and Rodl.)

This suggests the following algorithm for finding whether any two elements have a join (we can similarly determine whether any two elements have a meet):

Arrange the elements in decreasing topological order $x_1,\ldots,x_n$.
For $i=1,\ldots,n$, attempt to compute $x_j \lor x_i$ for all $j < i$.
Return TRUE if all attempts were successful.

In order to compute $x_j \lor x_i$, we use the following algorithm:

Let $u_1,\ldots,u_m$ be the elements covering $x_i$.
Set $a \gets x_j \lor u_1$.
For $i=2,\ldots,m$, check whether $x_j \lor u_i \leq a$ (i.e., if $(x_j \lor u_i) \lor a = a$), and if so, set $a \gets x_j \lor u_i$.
Verify that $a \leq x_j \lor u_i$ (i.e., that $a \lor (x_j \lor u_i) = x_j \lor u_i$) for all $i=1,\ldots,m$.
If verification was successful, return $a$.

Finding a topological ordering takes time $O(n+|E|)$.
If we denote by $C(x)$ the number of elements covering $x$, then the rest of the algorithm runs in time proportional to $\sum_{i=1}^n iC(x_i) \leq n|E|$, since $\sum_i C(x_i) = |E|$. In total, we get a running time of $O(n|E|)$.

It is known that the covering relation of a semilattice contains $O(n^{3/2})$ edges (see Statement 3 in the paper mentioned above). Hence we can abort the algorithm if $|E|$ is larger, and otherwise we can assume that $|E| = O(n^{3/2})$, and so the algorithm above runs in time $O(n^{5/2})$. This is Theorem 2 in the paper mentioned above.

Concluding, we can determine whether a DAG is the covering relation of a lattice in time $O(n^{5/2})$. A recent survey by Freese, Algorithms for finite, finitely presented and free lattices mentions obtaining faster algorithms as an open problem (Problem 1 in the survey).


Can LP for matroid polytopes be solved using the greedy algorithm? For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, although it's not done often in practice, the ellipsoid algorithm).
Matroids are well known for the property that the greedy algorithm is optimal if and only if it is performed for a weight function defined on the bases of a matroid. (Or something similar.)
Question: In special cases where we can somehow create a correspondence between vertices of a polytope and bases of a matroid, does the greedy algorithm provide a solution for LP?
The answer to this seems like it might be yes based on the paper The Bergman Complex of a Matroid and Phylogenetic Trees by Federico Ardila and Caroline J. Klivans. However, the exposition does not confirm or deny this suspicion explicitly, and without an explicit statement either way, combined with the fact I am not 100% certain I understand the definitions, I am still unsure if it is true or not. Below I quote the portion with the relevant definitions and hint:

Let $M$ be a matroid of rank $r$ on the ground set $[n] = \{1,2,...,n\}$, and let $\omega \in \mathbb{R}^n$. Regard $\omega$ as a weight function on $M$, so that the weight of a basis $B=\{b_1,...,b_r\}$ of $M$ is given by $$\omega_B =\omega_{b_1} + \omega_{b_2} +\cdots+\omega_{b_r} \,.$$ Let $M_{\omega}$ be the collection of bases of $M$ having minimum $\omega$-weight... we can understand $M_{\omega}$ in terms of the matroid polytope. [emphasis mine] We will use the following characterization of matroid polytopes, due to Gelfand and Serganova:
Theorem. [6, Theorem 1.11.1] Let $S$ be a collection of $r$-subsets of $[n]$. Let $P_S$ be the polytope in $\mathbb{R}^n$ with vertex set $\{e_{b_1} +\cdots+e_{b_r} |\{b_1,\dots,b_r\} \in S\}$, where $e_i$ is the $i$-th unit vector. Then $S$ is the collection of bases of a matroid if and only if every edge of $P_S$ is a translate of the vector $e_i − e_j$ for some $i, j \in [n]$.
Let $P_M$ be the matroid polytope of $M$. We can now think of $\omega$ as a linear functional in $\mathbb{R}^n$. The bases in $M_{\omega}$ correspond to the vertices of $P_M$ which minimize the linear functional $\omega$. [emphasis mine] Their convex hull is $P_{M_{\omega}}$, the face of $P_M$ where $\omega$ is minimized. It follows that the edges of $P_{M_{\omega}}$, being edges of $P_M$ also, are parallel to vectors of the form $e_i − e_j$. Therefore $M_{\omega}$ is the collection of bases of a matroid.

You can associate with each matroid two polytopes in $\mathbb{R}^n$, where $n$ is the size of the universe over which the matroid is defined:

The matroid polytope is the convex hull of the characteristic vectors of all independent sets.
The base polytope is the convex hull of the characteristic vectors of all bases (maximal independent sets).

The maximum of a linear function over a polytope is always attained (not necessarily uniquely) at a vertex. Therefore maximizing a linear function over a base polytope is like maximizing it over the collection of bases, for which the greedy algorithm can be used. The same goes for the matroid polytope, with the necessary changes.


Having Moore's law is it worth looking for more algorithms? knowing that Moore's law states that is the observation that the number of transistors in a dense integrated circuit (IC) doubles about every two years. is it worth looking for more algorithms?

Yes.

Better algorithms, that run in less time complexity - work way better than just an increase in constant factor for large enough input, but more transistors is just a constant factor of work.
We have reached the "end" of this "law". Now we are in an era where its hard to make transistors smaller due to quantum effects on them.
Having newer and better algorithms will make programs run faster on current computers, and we wont have to always buy new ones.
Why not have both? more transistors + newer algorithms = even better performance!


Quantification in pumping lemma for regular languages The Wikipedia article on the pumping lemma
states:

  We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ:
$$
\begin{align*}
&(\forall L \subseteq \Sigma^*) \\
&\quad (\text{regular}(L) \Rightarrow \\
&\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\
&\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L))))))))
\end{align*}
$$
I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

The pumping lemma states that $p\implies q$.

To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it  implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.


Is this a generic way to convert any recursive procedure to tail-recursion? It seems that I've found a generic way to convert any recursive procedure to tail-recursion:

Define a helper sub-procedure with an extra "result" parameter.
Apply what would be applied to the procedure's return value to that parameter.
Call this helper procedure to get started. The initial value for the "result" parameter is the value for the exit point of the recursive process, so that the resulting iterative process starts from where the recursive process starts to shrink.

For example, here is the original recursive procedure to be converted (SICP exercise 1.17):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Here is the converted, tail-recursive procedure (SICP exercise 1.18):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Can someone prove or disprove this?

Your description of your algorithm is really too vague to evaluate it at this point.  But, here are some things to consider.

CPS

In fact, there is a way to transform any code into a form that uses only tail-calls.  This is the CPS transform.  CPS (Continuation-Passing Style) is a form of expressing code by passing each function a continuation.  A continuation is an abstract notion representing "the rest of a compuation".  In code expressed in CPS form, the natural way to reify a continuation is as a function that accepts a value.  In CPS, instead of a function returning a value, it instead applies the function representing the current continuation to the being "returned" by the function.

For example, consider the following function:

(lambda (a b c d)
  (+ (- a b) (* c d)))

This could be expressed in CPS as follows:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

It's ugly, and often slow, but it does have certain advantages:

The transform can be completely automated.  So there's no need to write (or see) the code in CPS form.
Combined with thunking and trampolining, it can be used to provide tail-call optimization in languages that do not provide tail-call optimization.  (Tail-call optimization of directly tail-recursive functions can be accomplished via other means, such as converting the recursive call into a loop.  But indirect recursion is not as trivial to convert in this manner.)
With CPS, continuations become a first-class objects.  Since continuations are the essence of control, this enables virtually any control operator to be implemented as a library without requiring any special support from the language.  For example, goto, exceptions, and cooperative threading can all be modeled using continuations.

TCO

It seems to me that the only reason to be concerned with tail-recursion (or tail-calls in general) is for the purposes of tail-call optimization (TCO).  So I think a better question to ask is "does my transform yield code that is tail-call optimizable?".

If we once again consider CPS, one of its characteristics is that code expressed in CPS consists solely of tail-calls.  Since everything's a tail-call, we don't need to save a return-point to the stack.  So all code in CPS form must be tail-call optimized, right?

Well, not quite.  You see, while it might appear that we have eliminated the stack, all we have done is merely change the way we represent it.  The stack is now part of the closure representing a continuation.  So CPS doesn't magically make all our code tail-call optimized.

So if CPS can't make everything TCO, is there a transform specifically for direct recursion that can?  No, not in general.  Some recursions are linear, but some are not.  Non-linear (e.g., tree) recursions simply must maintain a variable amount of state somewhere.


Definition of efficiency versus complexity of algorithm When I read introductory textbooks I get contradictory answers. In some cases efficiency and complexity are treated the same and the big-O notation is used to indicate that (for example) for an O(n) algorithm the time to execute is linearly proportional to the input dataset size.

From other sources I have read that efficiency is a measure of the computing resources required to execute an algorithm, but not the same as the complexity of the algorithm. So for example is it possible to have an algorithm (say to multiply two decimal numbers) that is efficient in terms of its resources (it does not need much to execute) but is complex in that as the input dataset increases in size the time to execute is O(n^2) ???

An algorithm is often called "efficient" if its runtime is short, compared to the inherent difficulty of the problem.

For example, you cannot sort arbitrary arrays by comparing keys in less than O (n log n). Once sorted you can lookup values in O (log n). Looking up a value in the sorted array by doing a linear search has lower complexity then sorting the array, but it is inefficient because linear search takes time O (n) and could be done in O (n log n).


Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms From my understanding, a problem amenable to a dynamic programming solution has these two properties:

Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps reappearing. Thus, memoization can be used to boost performance.
Optimal Substructure — The problem can be broken down into smaller components, which can then be solved independently and the results combined to produce the answer to the overall problem. This allows for subproblems and possibly overlapping subproblems.

I've read that Bellman-Ford and Floyd-Warshall are dynamic programming algorithms, but how do I think of them in terms of the two properties given above?

Floyd–Warshall algorithm

You can prove inductively that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that passes through the vertices $1,\ldots,k$. How does it do that? When $k = 0$, you can read this off the adjacency matrix. For larger $k$, there are two possibilities:

The shortest path from $i$ to $j$ through $1,\ldots,k$ doesn't use $k$. In this case it equals the shortest path from $i$ to $j$ through $1,\ldots,k-1$.
The shortest path does use $k$. In this case you can break it up to two parts: a part from $i$ to $k$, and a part from $k$ to $j$. In both parts, the path only goes through $1,\ldots,k-1$.

You can therefore compute the shortest past from $i$ to $j$ through $1,\ldots,k$ using shortest paths that go through $1,\ldots,k-1$. Taking $k = n$, we obtain the unrestricted shortest paths.

Bellman–Ford algorithm

Let us consider first a parallel version of the Bellman–Ford algorithm which updates all weights simultaneously. In this case, you can show that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that is of length at most $k$. When $k = 1$, this is easy. For larger $k$, there are two possibilities:

The shortest path of length at most $k$ actually has length at most $k-1$.
The shortest path of length at most $k$ has length exactly $k$. Let $v$ be the penultimate vertex in one such path. Then the length of shortest path from $i$ to $j$ of length at most $k$ is the length of the shortest path from $i$ to $v$ of length at most $k-1$, plus the length of the edge from $v$ to $j$.

Once again, this can be computed by induction on $k$. Taking $k = n-1$, we obtain the unrestricted shortest paths (assuming no negative cycles).

The usual algorithm, which is sequential, is a bit different, but you can show that it is at least as good as the parallel algorithm.


Find palindrome in directed Graph where edges are either blue or red This is the given task:
Suppose you are given an arbitrary directed graph G in which each edge is
colored either red or blue, along with two special vertices s and t.
Describe an algorithm that either computes a walk from s to t such that
the pattern of red and blue edges along the walk is a palindrome, or
correctly reports that no such walk exists.
I already know the solution involves DFS in some way but I don't know how to check if a palindromic path doesn't exist. Since it's not necessarily an acyclic graph there are infinitely many paths that can potentially form a palindrome. So how do I go about this problem?

Here's a possible algorithm.
Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, b) \to (c, d)$ in $G'$ where two edges $c \to a$ (note the order) and $b \to d$ exist in $G$ with the same color.
Then to find an odd-length palindrome you simply check if $(s, t)$ is reachable from any $(x, x)$ in $G'$. To find an even-length palindrome check if $(s, t)$ is reachable from any $(a, b)$ in $G'$ under the condition that $a \to b$ exists (regardless of color) in $G$.

The idea is to extend the palindrome from the middle out. The vertices $(l, r)$ in $G'$ represent the leftmost and rightmost symbol in our palindrome, and the way we constructed the edges in $G'$ corresponds to all valid ways to extend the palindrome.


Counting the nodes in a network in a distributed way There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters).

One of the nodes, say $s$, wants to know $n$. How can it do this?

Each node has $O(\log n)$ memory bits, so it can hold a counter, but not a list of all nodes.

If the network is a tree, I think the following (inefficient) protocol should work:

$s$ sends a "Count" message to itself.
When a node $v$ receives a "Count" message from node $u$, it acts in the following way:

Send every neighbour except $u$ a "Count" message and wait for the result.
Send $u$ a "Result" message containing the sum of all results (0 if there are no neighbours).

The problem with general graphs is that we may not remember which nodes we already counted, so we might count the same node twice. What to do?

For constant node degrees, the following simple algorithm seems to work:
The source node $s$ can initiate a BFS tree construction and then we simply accumulate the count upwards along the tree edges starting from the leafs and ending at $s$. Each node locally keeps track of its parent/children in the tree; note that we can do this using $O(\log n)$ space as the degree is constant and therefore each node knows if it is a leaf.

For arbitrary degree, there's also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds. (In each round, every node can reliably exchange $O(\log n)$ bits with each of its neighbors.)

Suppose that I have a network $G$ with diameter $Diam(G)$.

Each node $u$ generates a random value $x_u$ according to the exponential distribution with rate 1; we round $x_u$ to $\Theta(\log n)$ bits.
Node $u$ also has a local variable $minval_u$ where it keeps track of the minimum value encountered so far. Initially, $minval_u = x_u$.
For the next $Diam(G)$ many rounds, node $u$ sends $minval_u$ to its neighbors. Also, upon receiving $minval_v$ from some neighbor $v$, node $u$ sets $minval_u = \min(minval_u,minval_v)$.
After round $Diam(G)$, node $u$ computes its estimate of the number of nodes as $1/minval_u$.

Why does this algorithm work?

Our algorithm exploits the following nice property of the exponential distribution (see here):
If we have $n$ exponential random variables $X_1,\dots,X_n$ each of rate $1$, then the random variable $X = \min(X_1,\dots,X_n)$ is also exponentially distributed of rate $n$ and therefore has expected value $1/n$. At the end of the algorithm, the $minval_u$ variable corresponds to a sample of this random variable $X$. Therefore, to get the sought value $n$ (i.e. the number of nodes), we simply compute $1/minval_u$. To get a high probability bound, we can repeat the above $\Theta(\log n)$ many times and take the average of the produced estimates.


Best algorithm to make a smooth route through a raw set of GPS-points with some errors? We're developing a mobile application where one of it's functions is tracking user driving route.
The app simply pushes GPS-coordinates to the server, which stores them into a route.

Then we need to display that route gracefully on a map.

There are 2 problems:

Too many points to draw it all. I solve this by applying my variation of RDP algorithm
GPS coordinates aren't ideal, sometimes there is an error up to 100-200 meters. Which causes loops or zigzags on the map and no one of the polyline simplification algorithms which I know can deal with it.

Do you know a way or an algorithm how to deal with errors in coordinates data to draw smooth routes?

The black is the actual polyline. The red is kind of my desired simplification.

Use a Kalman filter.  This is a powerful way to smooth the data to eliminate noise, in a way that takes into account the dynamics of how physical objects move.


Computational complexity of Bell numbers I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B_{n}$ options, where $B_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, that dealing with $B_{n}$ possible solutions results in exponential (or worse?) computational complexity (in terms of $n$). If possible, I would also like to prove this in the context of NP-hardness.

As I am new to this, any hints would be greatly appreciated.

So to summarize, given an algorithm, prove that it will take exponential (or worse) time in terms of $n$, when $n$ corresponds to $B_{n}$.

Thank you very much.

Yes, the $n$th Bell number is exponential in $n$.  Wikipedia lists the following relation:

$$B_{n+1} = \sum_{k=0}^n {n \choose k} B_k.$$

It follows that

$$B_{n+1} \ge B_n + n B_{n-1} \ge n B_{n-1},$$

so

$$B_{n+1} \ge n(n-2)(n-4)\cdots \ge (n/2)^{n/4},$$

which is exponential in $n$.

This fact has little or nothing to do with NP-hardness; it is just unconditionally true, regardless of whether P = NP or not.

If you have a problem for which every algorithm takes $\Omega(B_n)$ time, then the problem is not in P; it requires exponential time.  It might or might not be in NP.

If you have a problem where the obvious algorithm takes $\Theta(B_n)$ time, that proves nothing (maybe there is some other algorithm you haven't thought of yet that is faster).


Does this article imply that Turing-Computability is not the same as "effectively computable"? I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, could be physically buildable.

First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.

As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)


In RegExr, why is regex OR in JavaScript sometimes not commutative? On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same.
The first one matches only $a$'s and the second one $b$'s.

Is this a bug?
Or does the site something different than evaluating regular expressions, as I learned them in class?

It is not a bug; it is rather the JavaScript RegEx engine tries to match as much of the first of the two expressions combined by the "|" operator as it can. Thus, instead of matching a word like "bbb" with as many "b"s as possible, it matches the pattern a* against the empty word (implicitly) at the beginning of "bbb". Granted, the RegExr interface does not highlight this properly, but that is more of a missing feature than a bug.

As mentioned in the comments, you should also be aware the engine tries to find (possibly) strings in the input text which match the pattern specified by the regex; the matches are what are highlighted by the RegExr interface. This is a different use of regexes than in formal language theory, in which regexes are used to specify formal languages, and in which an input (word) as a whole either matches the regex or not.

Caveat: If you are trying regexes verbatim from a formal languages class, you may run into trouble when trying to specify the empty word; the character ε is not interpreted as the empty word but as the Greek lowercase epsilon character instead. This question on SE contains some ways of correctly specifying (only) the empty word.

Warning number 2: If you write L(a*|b*) verbatim for your expression there, it is interpreted as a capital $L$ followed by the pattern (a*|b*), not as the language corresponding to the pattern (a*|b*)!


Simulated annealing to find the correct permutation of 20 words I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation.

I'm trying to figure out how to use simulated annealing to find the correct permutation of these 20 words. To begin with, I'm not even sure if I understand simulated annealing entirely, so I'll describe an algorithm that I think resembles simulated annealing.

For an arbitrary number (preferably a big number) of times, generate a random permutation and measure how correct it is. If the answer is more correct than any previous attempt, save the score and the sentence. Once we are done iterating, we have found something that it is probably close to the global maximum (the "correct" permutation).

I'm not sure where to go from there. Essentially, I have two questions.

Does that sound like a good approach?
Is my algorithm simulated annealing?

No, that's not simulated annealing.  It's not really even close.

Whether it will be a good enough approach will depend on your metric.  Since you haven't told us what the metric is, it's not really possible to say.  In the worst case, if your metric is sufficiently horrible, you might need to explore all $20!$ permutations.   In any case, usually the only reliable way to find out whether your approach is a good one is to implement and see what happens.  There are few theorems that gives useful provable results about how effective the approach will be; instead, you need to use empirical evaluation.


Maximize the number of satisfied disjunctions I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas, given the number of variables that I can set to 1.

Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?

You are addressing a problem of the same type. if you use De Morgan law your problem will become MIN-SAT which is  NP-HARD

checkout THE MINIMUM SATISFIABILITY PROBLEM


Is bounded waiting satisfied in this 2 process solution? Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2=false;
}
/* Remainder section */

Here, wants1 and wants2 are shared variables, which are initialized to false.

What i have tried =>

Here, mutual exclusion is satisfied and deadlock is there, so no progress .

I am only having a doubt that bounded waiting can also be satisfied here as according to the definition, bound is here 0, so waiting is bounded here ?

Is my understanding correct ?

Bounded waiting is satisfied, the process $p_i$ will never be bypassed by $p_{1-i}$ after changing the value of $w_i$ (wants $i$) to $1$.

If $p_i$ set the value of $w_i$ to $1$, then in order to enter the critical section, $p_{1-i}$ must pass the while loop. This cannot happen until the value of $w_i$ is set to 0. The only place where $w_i$ is set to $0$, is after $p_i$ has finished, which means he will never be bypassed by $p_{1-i}$.

When in doubt, try to prove it yourself. If you agree that the number of times a process may be bypassed is at most $0$, then yes, bounded waiting holds.


Why is this flow a max flow? According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?

You've left out part of the statement.  It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow."  If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$.  The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated.  The $s$ to $c$ link is saturated.


Select at least one from each category to minimize union, NP-hard problem? I have this problem that is very similar to the minimum k-union problem:

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is to select at least one $c$ from each category such that the size of their union is minimized.

Is this problem NP-hard?

Nice question! Let us call this problem the minimum label-covering problem.
We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating "intersecting the $i$-th set" in the hitting set problem to "labelled with the $i$-th label" in the minimum label-covering problem.
Given $V=\{V_1, V_2,\cdots, V_m\}$, which is a collection of subsets of a finite set $U$ and a number $k$, the hitting set problem is to find the smallest subset of $U$ which intersects (hits) every set in $V$. Let $S$ be the disjoint union of $U$ and $\{l_1,l_2,\cdots, l_m\}$, a set of $m$ labels. Let $C$ be the set of all subsets of $S$ of the form $\{u, l_i\}$ where $u\in V_i$.  Let the label for $\{u, l_i\}$ be $l_i$. Suppose we have solved the minimum label-covering problem for $C$, $S$ and the specified labelling, that is, we have selected at least one set from each category such that their union is minimized. Let $U'$ be the set of all elements of $U$ that are members of the selected sets. It is easy to verify that $U'$ is the smallest subset of $U$ that hits every set in $V$. Our proof is done.
An exercise
Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category, the maximum label-covering problem is to select at most one $c$ from each category such that the size of their union is maximized. Show the maximum label-covering problem is $\mathsf{NP}$-hard.


Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,C_2,\dots,C_k$ that you have not yet taken. There are no conflicts between courses in the same area of study, but there can be conflicts between courses in different areas of study. You have a list of $(class1, class2)$ pairs in different areas of study that are in conflict. Can you choose 1 course from each area so that there are no conflicts? Is this an NP-complete problem?

Here is what I have so far:
K-AREA-COURSE-REGISTRATION ∈ NP: Given a random list of k courses, we can check that we have one course from each area in O(k) time. We can also check for conflicts in O(k^2) time (check each pair of courses for conflict).

K-AREA-COURSE-REGISTRATION is NP-complete: Reduce 3-SAT to K-AREA-COURSE-REGISTRATION. Each 3-SAT literal becomes a course (same literal in different clause is a different course). Each clause becomes an area of study (clauses become the $C_k$ sets). Create conflicts between two courses $a,b$ if, in the original 3-SAT problem, $a=x$ and $b=\bar{x}$. Choosing one course from each set will set at least 1 literal in each 3-SAT clause true. The conflicts will stop us from setting a single literal both true and false

Question: Do I have/do you have any tips in accounting for the case of two courses $a,b$ which both map to the same literal $x$ in the original 3-SAT but are in different clauses (therefore in different $Ck$ sets). I may be able to use conflicts to make sure both $a$ and $b$ are chosen, but I was thinking I could just ignore this since all that matters in 3-SAT is at least one literal.

Assuming the sets $C_i$ are pairwise disjoint, this problem is very related to the independent set problem and is called maximum colored independent set (also called rainbow colored independent set). The problem goes as follows. Given a graph and a colouring function over the vertices of the graph. Find a maximum independent set with each vertex in the set having a different colour. The problem is NP-hard as well (try to reduce Independent set).

Assuming the sets are not disjoint the problem does not get easier since the version with disjoint sets is only a special case of this problem.


Visualize Graph Clusters I am working on my thesis which involves using ant based techniques for graph clustering. I am testing the algorithm currently and I was wondering if there is a way that I can visualize the clusters of a given graph.

In this case, I have the graph as a file and another file corresponding to the clustering where each node is given its cluster. Is there a software using which I can visualize this graph where nodes belonging to the same cluster have like the same color or something?

The graph is represented as an edge list, or in the ".net" format or Graph Modelling Language ".gml" format. I know there are a lot of programs out there for networks such as gephi, graphviz, networkx, pajek etc but I don't know how to do this. Any help/ideas would be greatly appreciated!

Thanks!

You could use graphviz.  Its input format allows you to specify the color for each vertex.  You could write a simple script to take the specification of the graph and the clustering, and output a .dot file that lists the vertices and edges and specifies an appropriate color for each vertex (based upon your clustering).


Context-free grammars and priority This grammar is supposed to give priority to multiplication:

E -> E + T | T.
T -> T * F | F.
F -> x.

A derivation for "x + x * x" would be (unless I'm wrong):

E => E + T => T + T => F + T => x + T => x + T * F => x + F * F => x + x * F => x + x * x.

So how is multiplication given priority over addition? It appears that the addition is produced first.

You are correct that additions operator is produced first when you
derive. But when you parse, you do the opposite (reduction), and the
multiplications are recognized first, wich is precisely what you want.

THis need a bit of discussion, when you compare top-down and bottom up
parsing, but basically the bottom of the tree must be know correct
before the top can be.

More to the point, this is a consequence of the fact that the parse
tree produced with such a grammar will be structured to conform the
operator operand structure defined by priorities, up to idosyncrasies
of a CF grammar definition, which are ironed out in an abstract syntax
tree (AST). In other words, this gives the parse tree a shape that is close
to the shape desired for the AST (Thanks to Raphael for suggesting
comparison with the AST).

This is why such a grammatical definition is simpler to use to
generate the AST. More importantly, it was much more convenient in
older compilers and interpreters that did not use AST, as the parse
tree reflected the priority structure.

For example, the parse tree for x + x * x is

   E
 / | \
E  +   T
|     /|\
T    T * F
|    |   |
F    F   x
|    |
x    x

And the AST for x + x * x is

   +
 /   \
x     *
     / \
    x   x

It is derivable from the parse tree by moving all operators up one
edge on the preceding node, and then ignoring all non-terminals,
making each linear downward path a single edge. Essentially the same
shape.

This AST is the expression tree defined by the priorities, from which the meaning of the expression can be derived (by homomorphism), from which it can be evaluated or compiled.


Get the nth lexicographic string of "all" possible combinations of an alphabet Is there a way to find the nth string of characters from an alphabet, without having to store "all" of the combinations?

Example:

Alphabet $A = \{a,b,c\}, n=12$.

All possible combinations in lexicographic order are $C = \{a, ab, abc, ac, acb, b, ba, bac, bc, bca, c, ca, cab, cb, cba\}$.

You can see that there's no repetition of characters in any string and the empty string is not a member of $A$.

So, the nth string is: $ca$.

Clearly, to find this I'm iterating over the set $C$.

The problem is that I have to generate all these strings, wich takes a really long time, and then search for the nth one. If the alphabet is large $(1 \leq A \leq 26 )$ the set $C$ grows too fast (not sure how much) and is impossible to store.

My questions is if exists a way to find these nth one, without generating all the strings.

Also, I'm not sure if this question goes in this StackExchange site.

It is better if you include the empty string as the $0$th string in lexicographic order. Here is how you convert an index into a word.

First, we are going to find the first letter of the word, and an internal index among all words starting with this letter. We do this by counting how many words start with each letter, including the "empty letter". I'll let you figure out how to do that. In your case, we get $1,5,5,5$. This means that $[0,1)$ corresponds to the empty sword, $[1,6)$ to words starting with $a$, $[6,11)$ to words starting with $b$, $[11,16)$ to words starting with $c$.

Given an index, you locate which interval it belongs to, and record the starting character and the internal index inside the interval. In your example, $12$ belongs to $[11,16)$ (and so starts with $c$), and its internal index is $1$.

If the index is $0$, then we are done. Otherwise, we recurse. In your example, we are left with the alphabet $\{a,b\}$ for which the intervals are $[0,1),[1,3),[3,5)$. The current index is $1$, so the word at this level of recursion starts with $a$, and the new index is $0$. That means that the recursion ends here. The outputs is thus $ca$.