How to determine the polynomial runtime of an NP reduction? To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$  , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-complete problems in CLRS they just state the reduction algorithm for $L$ to convert to $L'$ is polynomial. How can one prove it's polynomial time, provided an example such a clique or ham cycle kind of problem?

The problem here is a misunderstanding of the point of the reduction. NP-complete problems are not known to have polynomial time algorithms. If they do, then P $=$ NP, if they don't then P $\neq$ NP - this is the BIG question of theoretical computer science.

The point of the reductions you're looking at is to show that the problem $L'$ is NP-complete, and thus at least as hard as anything else in NP. It does this by demonstrating that if you could solve $L'$ in polynomial time, then using the reduction you could solve $L$ in polynomial time too (take the instance of $L$, convert it to an instance of $L'$, solve that, then use that solution to get the solution to the original instance).

As $L$ is NP-complete, this also means that if we could solve it in polynomial time, we could solve every problem in NP in polynomial time (hence the intuition that NP-complete problems are in some sense the "hardest" problems in NP).

Just to add some technical bits on top of that, a problem $\Pi$ is NP-complete if:

$\Pi \in$ NP, and
$\Pi$ is NP-hard.

A problem $\Pi$ is in NP if there is an non-deterministic algorithm that solves $\Pi$ in polynomial time in the size of the input or equivalently we can check an answer to an instance of $\Pi$ in deterministic polynomial time.

A problem $\Pi$ is NP-hard if for every problem $\Phi \in$ NP, there exists a polynomial time reduction such that $\Phi \leq_{p} \Pi$ (this can be a different reduction for each $\Phi$). In practice what we do is actually chain these reductions together, so say we have an NP-hard problem $\Pi'$, then we know that there's reductions from everything in NP to it, so if we can show that $\Pi' \leq_{p} \Pi$ then by composing the reductions, we can show that there's a reduction from everything to $\Pi$ (we just go via $\Pi'$).

So just to come back to the original question, we don't know if there's a polynomial time algorithm for $L'$ - most(?) people would probably suspect that there isn't, as lots of people have spent lots of time trying to find even one polynomial time algorithm for any NP-complete problem and there's been no luck so far (of course such an algorithm for any of them means a polynomial time algorithm for everything in NP). The reduction 'just' shows that $L'$ is one of these hard problems.


Is any State Space Tree always Binary Tree? A backtracking algorithm generates, explicitly or implicitly, a
state-space tree.
Introduction to the design & analysis of algorithms / Anany Levitin

I wonder that whether the saying always holds. If yes, is it always binary tree?  For any problem which can be solved by backtracking, skeleton of the solution can be generalized?

Think about the chess problem or more simple 8-Queen problem are Tic Tac Toe game. The states are not binary trees. As seen from Quoara  ;

  A state space tree is a tree constructed from all of the possible states of the problem as nodes, connected via state transitions from
  some initial state as root to some terminal state as a leaf.


Finite automaton - language acceptance In the book "The New Turing Omnibus", an excercise reads as the follows:

  "Show that no finite automaton can accept the language consisting of
  all words of the form $a^n b^n, n=1,2,3,...$ The formula represents
  $n$ a's followed by $n$ b's."

I have no idea why a finite automaton shouldn't accept such words. Couldn't one simply design an automaton that reads a word and always outputs "Accepted"?

Check the definitions. The language accepted by an automaton is the set of strings it accepts. So, for an automaton to accept a particular language (e.g., $\{a^nb^n\mid n\geq 1\}$), it must not only accept every string in the language, but also reject every string not in the language. Your suggestion of the automaton that just accepts every input meets the first criterion but not the second.


Why is the processes address space a continuous block in RAM? I need some clarification regarding how the process address space is organized in memory. I went through basic concepts of virtual memory and adress translation and according to the size of the page, it seems that a virtual adress can have its equivalent physical address located anywhere in RAM, it that right ?

I saw the following representation of RAM :

It seems that processes address space is continuous in RAM, how come ? I though that we could have, for example, the stack of a process(or some part of it) located at a totally different region of RAM than, for example, the heap.

The term virtual memory applies as soon as there is a mapping from logical (process specific) addresses to physical one.  The mapping may be as simple as adding a base to the logical address to get the physical one or as complex as the segmentation followed by paging of x86.  The representation you show seems to assume the first.


Proof that circuit design problem is NP-hard I have the following problem, and I want to show that it is NP-hard (or NP-complete).

Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus y_4)$. Will the assignment of literals such that the equation given by the conjunction of such clauses, e.g. $c_1\wedge c_2 \wedge c_3 \ldots$ is satisfiable or not a problem in NPC or P?

I suspect that the CIRCUIT SAT can be reduced to it, but I am unable to reach there.

If all clauses have the form $y_i \lor y_j \lor (y_k \oplus y_l)$, your problem is in P: simply setting all of the $y_i$ to 1 will satisfy all of the clauses, always.  Therefore, it's unlikely to be NP-complete, and you're unlikely to find a reduction from 3SAT (well, unless P=NP).

But if you additionally allow some clauses to take the form $y_i \oplus y_j$, then your problem becomes NP-complete.  This follows from Schaefer's dichotomy theorem plus a reduction to double the number of inputs (to enable one to express negated literals); or you can find a direct reduction.


Relation between size of address bus and memory size; memory Segmentation in 8086 My question is related to memory segmentation in 8086. I learnt that,

  8086 has a 20 bit address bus. And so it can address 2^20 different addresses. Which means it has an memory size of 2^20, i.e, 1MB.

I have a few doubts:

What I understand from the fact that 8086 has a 20 bit address bus is that it could have 2^20 different combinations of 0s and 1s, each of which represents one physical address. What I don't understand is that how does 2^20 different address locations mean 1 MB of addressable memory? How is total number of different addresses locations  related to memory size (in Megabytes)?
Also, correct me if I'm wrong, the 16 bit segment registers in 8086 hold the starting address of the different segments in the memory (Code, Stack, Data, Extra).My question is, aren't the addresses in memory of 20 bits? Then how can the 16 bit register hold 20 bit addresses? If it contains the upper 16 bit of the 20 bit address, how does the processor make out to which exact address location it has to point?

P.S: I am a beginner is micro-processors and total reliant on self study, so kindly excuse if my questions seem a bit silly.

Thanks in advance.

That's the beauty of cisc machines.
For starters as you can see address bus is 20bit wide but resisters are 16bit wide, so microprocessor will process 16bit at a time.

Now let's answer your questions :

1) Address size has nothing to do with architecture size. You can have instructions that can map 64bit or 128 bit address space in instructions. For example mov   can be hard coded in hardware itself to fetch next addressing scheme as required which eliminates requirements of same size bus and resistors. The same mov command with proper bit masking can use address of special resistors instead of memory spaces. It drills down to the choice of system architecture. Thus the name complex instruction set.
It goes beyond this simple explanation, but to give an idea, instructions are flexible enough to understand addressing schemes.

So answer is no when you are storing resistor data into memory, it refers to 16bit wide data bus. It is still storing data as usual way. But micro processor can operate on 8bit, 16bit or divide 32bit operation in sub operations as well depending on instruction.

It uses segments to divide memory into  usable chunks which is mapped by combing 16bit address scheme but by shifting it to 4bit and adding offset bits to get actual physical address. Modern cpu uses dedicated hardware called memory management unit having multiple operating mode of direct memory access and IO access as well.

Here's the quote :

  Rather than concatenating the segment register with the address
  register, as in most processors whose address space exceeds their
  register size, the 8086 shifts the 16-bit segment only four bits left
  before adding it to the 16-bit offset (16×segment + offset), therefore
  producing a 20-bit external (or effective or physical) address from
  the 32-bit segment:offset pair. As a result, each external address can
  be referred to by 212 = 4096 different segment:offset pairs.

2) Answer to this question is linked on how 8086 translates address to segments. As you can see it doesn't add offsets immediately but directly uses address schemes to map physical address without adding extra hardware. It's a clever way of addressing and doesn't require offset as it's already mapped to stored address space which is kind of 32bit wide when you add address+offset, enough to store 4GB space which you can see in 80386 models. Making it backward compatible as well.


give potential function - binary heap - extract-min in amortized const time and insert in log amortized time Consider an ordinary binary min-heap data structure with n elements supporting
the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a
potential function $\Phi$ such that the amortized cost of INSERT is $O(\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$.

I try to solve it, but I got in stuck:

Attempt
Let $c_i$ denotes real cost of $i-th$ operation, and $a_i$ denotes amortized cost.
Let $\Phi(D_i) = \text{number of elements after i operations}$
INSERT:$$a_i=c_i+ \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + (i)\log(i) - (i-1)\log(i-1) \le 3\log(i+1) = O(\log(i))$$
EXCTRACT-MIN:$$
a_i=c_i + \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + i\log(i) - (i+1)\log(i+1) =\log(i) + i\log(i) - i\log(i+1) - \log(i+1) < 0
$$

As you can see, my problem is that I get number lower than $0$. Can you help me ?

Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a_i = c_i + \Phi_i - \Phi_{i-1}$. Then
$$
\sum_{i=1}^n a_i = \sum_{i=1}^n (c_i + \Phi_i - \Phi_{i-1}) = \sum_{i=1}^n c_i + \Phi_n - \Phi_0 \geq \sum_{i=1}^n c_i.
$$
This means that the total amortized cost $\sum_{i=1}^n a_i$ is an upper bound on the actual cost $\sum_{i=1}^n c_i$, which is what we want.

In this argument there is no need to assume that the amortized costs are non-negative – the argument works even if they can be negative. However, if some amortized costs are negative, then you can probably improve the amortized analysis.

Back to your case. Suppose that inserting the $n$ element costs $\log n$, and extracting the minimum when there are $n$ elements also costs $\log n$. This suggests a charging argument in which we charge the insertion of the $n$th element by $2\log n$, and discharge the extra $\log n$ when extracting the minimum the next time that there are exactly $n$ elements. This gives an amortized time of $O(\log n)$ for insertion, and $0$ for extract-min.

We can give a similar argument using a potential function. We choose a potential function of the form $\sum_{i=1}^n \log i$, where $n$ is the current number of elements. Under this potential function, insertion costs $2\log n$ and extract-min costs $0$.

Note that $\sum_{i=1}^n \log i = \log n! \approx n\log n$, so this differs from your suggestion (appearing in the comments) of using $n$ as a potential function; your suggestion doesn't work, since under it extract-min costs
$$
\log n + n - (n-1) = \log n - 1.
$$
Taking a closer look at your question, you are actually using the potential function $n\log n$, which is very similar to what I suggest. This potential function does work.


Conjunctive Query Containment as SAT The problem of conjunctive query containment is known to be NP-Complete (originated at Chandra&Merlin 1977). Typically it's shown by reducing 3SAT or 3-colorability into this problem, and the other direction is typically proven by declaring it "trivial" (as it indeed looks trivial to see that the problem is in NP).

My question is how to practically translate the problem of query containment of two datalog rules (plain, without constraints or equalities) into the boolean satisfiability problem (not necessarily in CNF),
 and by listing the solutions of that latter problem, to see which variable substitutions would recover the containment? In other words, how to solve this problem using a SAT solver in practice?

I will try to answer your question limiting to Datalog without recursive predicates. Indeed, I suspect that recursive predicates are beyond conjunctive queries (conjunctive queries are a subset of FOL, and Datalog with recursion can compute Transitive Closures, which are impossible to express in FOL). Furthermore, I will assume that all derived datalog predicates have been unfolded.
As you probably know, a conjunctive query CQ1 contains CQ2 if you can establish an homomorphism of terms from CQ1 into CQ2. Hence, a possible reduction into SAT can be done by considering a boolean variable v for each pair of terms from Terms(CQ1)xTerms(CQ2). Intuitively, the meaning of such variables would be "we map term t1 to term t2". Then, we must ensure that the set of all variables "v" that evaluates to true encodes a correct homomorphism.
More formally, the reduction can be done as follows:

For each term $t^1_i \in Terms(CQ1)$, and for each term $t^2_j \in Terms(CQ2)$, consider a boolean variable $v_{t^1_i, t^2_j}$. Note that all the boolean variables evaluating to true encodes a mapping.
The encoded mapping must be functional. That is, for each term $t^1_i$, we need a constraint to state that $t^1_i$ is mapped to one term, and only one. Hence, we should add, for each term $t^1_i$, a constraint $(v_{t^1_i, t^2_1} \lor v_{t^1_i, t^2_2} \lor ... \lor v_{t^1_i, t^2_n})$, and for each triple of terms $t^1_i$, $t^2_j$, $t^2_k$ (with j!=k), $(\neg (v_{t^1_i, t^2_j} \land v_{t^1_i, t^2_k}))$
The encoded mapping must preserve constants. Hence, for each constant term $t^1_c$, we add the constraint: $(v_{t^1_c t^2_c})$
The encoded mapping must be a homomorphism. To do so, for each literal $L^1 \in Literals(CQ1)$, let $\{L^2_1 ... L^2_n\}$ be the set of all literals from $Literals(CQ2)$ with the same predicate. Then, we must ensure that, when mapping the terms of $L^1$ we obtain one literal from $\{L^2_1 ... L^2_n\}$. To do so, we build a disjunction where each disjunct $i$ means "$L_1$ is mapped to $L_i$". In particular, each one of these disjuncts can be built by iterating all the variables from $L^1$ and mapping them to $L^2_i$ variables. For instance, consider $L^1$ to be  $P(x, x, y)$, and considere $\{L^2_1 ... L^2_n\}$ to be $\{P(a, b, a), P(c, c, d)\}$; in this case we would build the constraint: $(v_{x a} \land v_{x b} \land v_{y a}) \lor (v_{x c} \land v_{x c} \land v_{y d})$

This reduction is polynomial. Indeed, the number of boolean variables is quadratic (w.r.t. the number of terms in CQ1 and CQ2), and all the constraints considered can be built with a several (nested) foreach loops that iterates the conjunctive queries terms and literals.


All languages are regular, as unions of singleton languages We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.

Suppose there is a non-regular language $L$. For every finite subset $\{x_1,x_2,\ldots,x_i\}$ of elements of $L$, we can take the corresponding singleton languages and compute their union. This new language (which is a subset of $L$) should be regular. Now we do the same with rest of the language.

Finally, we must have $sL_1, sL_2,\dots, sL_n,\dots$ which are all subsets of $L$ that are finite regular languages. If we take the union of $sL_1, sL_2,\dots, sL_i$, where $i$ is finite, we again have a regular language. We do this for all languages obtained from $L$.

If we keep doing such "finite" unions of regular languages, we will eventually obtain $L$, which must be regular because we obtained it from a finite union of regular languages.

This obviously isn't right, but I don't understand why.

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.


What can't you do without Turing-completeness? I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.

I also know that some non-Turing-complete languages can't use unbounded loops, and I suppose that making unbounded loops forbidden is enough to make a language non-Turing-complete. But it doesn't mean that it's the only way.

So, in general, what common properties or abilities of general purpose languages are only possible with a Turing-complete language?

If I decide to design a non-Turing-complete language, what common purpose functions won't I be able to implement with it?
Which common source code structures should I forbid?

Real world computers are not Turing complete (they have a finite amount of memory) and are equiparable to Linear Bounded Automata.

So the easiest way to design a non-Turing-complete language is to design a language that has only a limited amount of memory (the memory can also be a function of the input length) and don't worry about other restrictions.

But as soon as you allow some kind of unboundness it's not an easy task to avoid Turing completeness, for example two variables that can store an arbitratrily large integer, a JUMP operator, an IF condition and a + operator already defines a  Turing complete language (Counter mmachines).

It's curious that even some games (Chess, Magic The Gathering, Minecraft, ...) if you allow level/boards of unbounded size.

The common way is to use bounded loops or bounded recursion; you can take a look to some real-world non Turing-complete languages: SQL, data languages (e.g. Regular expressions,HTML,...), LOOP language, Charity, ...


How does MCTS handle games with large numbers of poor moves? I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by other types of agents.

For example, imagine a hypothetical game with a single player. At game start, the player can choose between move A or move B.

Move A results in a fair coin flip that determines win/loss.

Move B results in a second set of 10 possible moves for player A, one of which is a win (move C, let's call it), and the other 9 a loss.

Random playout will have move A winning 50% of the time, and Move B winning 10% of the time, even though the ability to always pick the winning move B->C is within the player's power.

Can MCTS handle games of this nature well? How does it do so?

Obviously this toy example can trivially be solved by other search methods, but the real game I'm interested in has a prohibitive branching factor for things like depth- or breadth-first search, and a proper evaluation function is difficult.

Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being succesful more often will have a larger likelihood of being picked. This process of positive reinforcement means that nodes that always lead to a victory will, over the course of many playthroughs, approach a 100% pick rate.

In your example, node A will have a rougly 50/50 success/failure ratio throughout any number of playthroughs (due to the coinflip). Node B will have a 10/90 ratio of success/failure at first but will approach a 100/0 ratio as the number of playthroughs nears infinity (node C will end up always being picked due to the 100% success rate, and this propagates to node B).

The result is that node B will gradually end up being picked more often than node A, reinforcing the effect and causing it to be picked even more often.

The image on the wikipedia page illustrates it very well; the nodes with a high chance of success gradually make up a larger fraction of the total 'node weight' on a level, thus increasing the odds that it is picked with every playthrough.


Give a recursive function $r$ on $A$ that reverses a string I really need help with this task here. Im stuck at it and I really would appreciate your help
Here is the task:

Give a recursive function $r$ on $A$ that reverses a string. For instance,
$r(logikk) = kkigol$ and $r(moro) = orom$. (given that $A$ the amount of
letters in the Norwegian alphabet which has 29 letters.). Define the
function in such a way that it is correctly regardless of what $A$ are.

Also $logikk$ means $logic$ in norwegian, and $moro$ means $fun$ in norwegian in case you're wondering.
Edit:
I tried to solve one of the recursive functions, $r(logikk)$, but i'm not sure if all of it is correct:

$\Lambda =$ The empty string
$r(\Lambda) =$ $\Lambda$, $r(k) = k$, $r(k) = k$, $r(i) = i$, $r(g) = g$, $r(o) = o$, $r(l) = l$
For any word $w$ and letter $a$, $r(wa) = wa$

Can someone please check if this is correct for $r(logikk)$ I feel like i'm missing something but i'm not sure what.

A recursive function requires base cases and recursive rules. Depending on how your system works, your base cases might include:

$r(\lambda) = \lambda$
$r(\sigma) = \sigma$ for $\sigma \in \Sigma$
etc.

You then need a general rule for more complicated cases. You're on the right track; you need a rule that takes something of the form $\sigma w$, where $\sigma \in \Sigma$ is a single letter and $w \in \Sigma^*$ is some arbitrary string, and produces the correct output. You will likely find, and should try to prove, that a rule like the following works:

$r(\sigma w) = w \sigma$

Fits the bill. Putting it all together, in pseudocode, you should arrive at something roughly like the following:

Reverse(string[1...n])
1. if n = 0 then return the empty string
2. else if n = 1 then return string[1]
3. else return the concatenation of Reverse(string[2...n]) with string[1]


Polynomial time reducibility $L_1$ and $L_2$ are two languages defined on the alphabet $\sum$.
  $L_1$ is reducible to $L_2$ in polynomial time. Which of the following
  cannot be true?

  $L_1 \in P$ and $L_2$ is finite
  $L_1 \in NP$ and $L_2 \in P$
  $L_1$ is undecidable and $L_2$ is decidable
  $L_1$ is recursively enumerable and $L_2$ is recursive

My reasoning is as follow,

If $A \le_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.

However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.

I was unsuccessful in reasoning anything about the 1st choice.

To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.

Three of the options use the same trick: if $C1,C2$ are two classes of languages and $C1 \subseteq C2$; then $L1 \in C2$ doesn't imply that $L1 \notin C1$.

The only choice that cannot be made true is 3: if there is a polynomial time reduction from an undecidable language $L_1$ to a decidable language $L_2$ then $L_1$ becomes decidable, too  (just build a Turing Machine that computes the reduction and then solve the problem using the decider for $L_2$) and this is a contraddiction.


Can PDA model Turing Complete objects if the objects' state are finite? I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract.

I am trying to understand the proofs of Chapter 6.
In particular, I cannot understand the premise of proofs 6.2. Indeed, the authors use a variant of SMAC, an Object-oriented and Turing Complete (SMAC) and they claim that (I underlined the suspicious claim with bold)

  Thus, we focus on verifying $sECF$, namely, statically verifying whether all executions of an object are $dECF_{FS}$ or $ECF_{C}$, where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA). Such a PDA for an object o is
  able to simulate any modular well-formed execution $\kappa \in \pi$
  where the active object of all states in $\pi$ is o.

In my understanding, this premise should be wrong, because although the state of this SMAC program is final, it is not computable by Push-Down-Automata (which compute total functions).

Foo:
     int x = 0 // field of the object
     enter // enter the single method of the object/contract
         while true do
             x = 1
     return

where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA).

You are correct that if you understand it as using a pushdown-automaton to model the full behavior of the object, since as you indicated, you can put a Turing complete Turing machine inside any object.

However, I would believe that the authors intend to use a pushdown-automaton to mode an object in the domain with its possible states as defined by the values of its fields and its execution stack, since the whole paper is focusing on the ECF(Effectively Callback Free) property for objects. The actual moments when the object is still in the middle of changing from one state to another state are ignored/irrelevant/transparent/skipped. More specifically, the following shows the purpose of the object.

  Such a PDA for an object o is able to simulate any modular well-formed execution $\kappa \in \pi$ where the active object of all states in $\pi$ is o


Examples of context-free languages with a non-context-free complements Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For
$$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ_0\},$$
both $A$ and $B$ are context-free, but their intersection $A ∩ B$ is not. Since context-free languages are closed under unions, they can’t be closed under complementation as well.

However, this only shows that one of the three languages $A$, $B$, and $\overline A \cup \overline B$ is a context-free language with a non-context-free complement, but not for which one of these this is true. So what is it?

Also, is there a minimal and elegant example of a context-free language with a non-context-free complement, maybe over a binary alphabet?

The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here).  Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here).  This gives a simple and elegant example of a context-free language (over a binary alphabet) whose complement is not context-free, as you requested.


NFA-style representation of regexps which includes AND I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine.  I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for various reasons, I can't use Brzozowski's technique and bump into state explosion when using a DFA.

I know about the cross-product construction to compute the intersection of two NFAs, but there as well: while the state explosion is not as severe as when going through a DFA, it is sometimes still too severe for my needs, so I'd like an NFA-like representation that lets me build the cross-product "on the fly", kind of like "Thompson's NFA" matching constructs the DFA states on the fly.

It is a bit  difficult to answer you because you state that you are using NFA
to do the matching. NFA being non deterministic, that leave the
interpretation technique open, depth first, breadth first, or
variants. So I am trying to give you an answer that should fit any
interpretation of the NFA. This technique should be applicable to
other constructions than intersection.

You have 2 NFAs, $A_i=(Q_i,\Sigma,\delta_i,\hat q_i, F_i)$ for
$i=1,2$. The intersection is a NFA $A=(Q,\Sigma,\delta,\hat q, F)$
defined as usual for the intersection, notably with $Q=Q_1\times
Q_2$.

The idea of the technique is to implement the transition function
$\delta$ not as a table, but as a function $\delta: (Q_1\times
Q_2)\times\Sigma\to 2^{(Q_1\times Q_2)}$, that calls in turn the
function $\delta_1$ and $\delta_2$.

function delta((q1,q2),a)
{ return (delta1(q1,a), delta2(q2,a))}

This is to be read as a non deterministic program, in the sense
described in this answer to How does one formulate a backtracking
algorithm? That means that, in actual interpretation, the functions
are actually returning sets of results, one by one if backtracking, or
together if breadth-first.

The rest is up to the way you translate non-determinism into
determinism, either by a compiler, or by hand. It can be done
depth-first or breadth first. It can even use memo function to compute
incrementally and remember the part of the transitions of the
automaton $A$ that is needed for the string at hand, and possibly keep
it for future strings to be matched.

Of course, if your automata are DFAs, this is much simpler to read as
usual deterministic functions (possibly implemented by tables for
delta1 and delta2. Then memoisation of delta will construct
incrementally the table for the cross product.

The can be seen as an incremental construction, or as a generalisation of call by need. Rather than building the automaton up-front, you build the parts you need when you need them (and you can even forget some, if you run out of space). This can also be used for the powerset construction, and in many other circumstances.


Force-directed graph optimization with step-wise costs and constraints Introduction
I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can potentially affect each other in the optimization problem it is safe to model this as a complete, undirected graph.
In most modes of this optimization problem there are between 2-3 regions extending out infinitely from the origin separated by straight lines, i.e.
 A | B
--------
   C

Each region exactly encompasses one or more Cartesian quadrants. Each imposes a fixed cost or benefit to each node, but this cost does not change the "farther into the region" a node gets.
Costs
This is the exhaustive list of costs and constraints on the nodes; all factors are cost multipliers (higher is worse). Distances are shown in metres but are really just discrete integers.

The distance between any two nodes must be at least 4m
For each node pair within 25m, there is a factor of 1.04
For each node, if there are three or fewer other nodes within 120m, there is a factor of 0.90
Depending on what region a node is in, the node has a factor between 0.90 and 1.10
For every node, there is an individual edge factor to every other node within 25m of between 0.90 and 1.10
The product of all of the above factors, for each node, will have a set minimum of 0.67 and a set maximum of 1.50

So none of the factors are continuous, and none are differentiable in space since they are all step-wise.
Search space
The 2D coordinates of each node are discrete and unbounded. Since there are 25 nodes, there are 50 integer variables (xy for each node) to optimize. The hope is that even though there are no bounds, there will be enough sub-1.0 factors to have the optimization converge rather than force the nodes to fly apart.
If I get this working well enough for a given region configuration, I might expand this to selection of a region configuration, for which there are currently 46 possibilities.
Optimization
Since none of the cost factors are space-differentiable, something like Gradient Descent would not be possible.
I have read about force-directed graph drawing; in particular this is interesting:

using the Kamada–Kawai algorithm to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm to improve the placement of neighbouring nodes.

Unfortunately, it seems that these methods have no notion of cost tied to absolute location, only distance of nodes relative to each other.
Implementation
I will probably end up implementing this in Python.
Any hints on how to approach this would be appreciated.

This is a discrete optimization problem.  I think one possible approach would be to approximate the discrete elements with continuous, differentiable functions and then optimize the resulting substitute problem.
Consider the function $f(x)=1$ if $x\ge 0$, or $f(x)=0$ if $x<0$.  This is a discrete function, which can be approximated by the sigmoid function $S_\alpha(x) = 1/(1+e^{-\alpha x})$.  The sigmoid is effectively a "softened" version of $f$.  The larger that $\alpha$ is, the better the approximation.  And notice that the sigmoid function is continuous and differentiable and monotonic.  Similarly, the function $f(x)=c$ if $x \ge t$, or $f(x)=0$ if $x<t$, can be approximated by $c/(1+e^{-\alpha (x-t)})$.
So, take your problem, and replace each of the discrete decisions with a softened version.  For instance, you have a rule that says "if a pair of nodes is at distance $\le$ 25m, then multiply a factor of 1.04".  I suggest you replace this with the rule "multiply a factor of $1.04/(1+e^{-\alpha(25-d)})$ where $d$ is the distance between those two nodes".  In this way, each rule can be replaced with a "softened" version, where the parameter $\alpha$ determines how soft it is: the smaller $\alpha$ is, the smoother the function; the larger $\alpha$ is, the better an approximation it is to the discrete rule.  Your requirement that the product be between 0.67 to 1.5 can be replaced with a version that applies a penalty if the product is below 0.67 or above 1.5, and then you compute a softened version of this penalty for each node.  Finally, the objective function can be the sum of these penalties.
Once you've done that, you have a continuous, differentiable objective function, so you can minimize it using gradient descent.  I suggest that you initially set $\alpha$ to be a fairly small value, and during gradient descent you gradually increase $\alpha$ until finally it is a very large value (i.e., slightly increasing $\alpha$ after each iteration of gradient descent).
As a side note, instead of working with the product of factors, I recommend you take the log of everything, so that work with the sum of log factors.  Usually summations behave more nicely with gradient descent than products.
I suggest that you use gradient descent with random restarts.  For instance, you might do 1000 trials, where in each trial you start with randomly chosen initial positions, and then do gradient descent from there until convergence; and you take the best result across all of these 1000 trials.
You could also try replacing gradient descent with any other iterative method, such as Newton's method.
I don't know whether this will work well for your particular problem, but it is one thing you could try that might work.


Does P=NP imply polynomial solutions to #P? Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so even if P=NP it may not necessarily be true.  My confusion is over how we write the answer to a $\#P$-complete problem since it may be exponential in the size of the input (for example up to $2^n$ truth assignments to a SAT instance on $n$ variables).  Therefore, I cannot understand how, even if we find a fast way for computing something like the permanent of a matrix, we could still expect to write the answer in polynomial time. Am I missing something about the definition of $\#P$?

Your confusion is that the class #P only asks you to count the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of satisfying assignments to a formula of $n$ variables, you need $n$ bits, because there are at most $2^n$ solutions (i.e. in the case of a tautology). Another example: the number of isomorphisms between two graphs is at most $n!$, which requires $\log(n!)\approx n\cdot \log(n)$ bits to write down. All these number of bits are polynomial in the size of the input

#P can be solved in polynomial time if and only if P=PP. This is a stronger statement than P=NP, because P=PP implies P=NP (and hence, it is less likely). If P=NP, then all #P problems can be approximated to within a constant factor by a deterministic algorithm.


Are QR codes Turing-complete under the rules of Conway's Game of Life? This is a bit of a weird question, but I was wondering earlier if QR codes are Turing-complete when interpreted as initial states for Conway's Game of Life.

My intuition is "yes", as there are infinitely many QR codes (they just get bigger as you add more information), and the Game of Life itself is Turing-complete. However, it's not inconceivable that the restrictions imposed by the QR code format mean that no QR codes are Turing-complete.

Another way to phrase the question would be "can all Turing machines be encoded as a string which, when converted into a QR code and used as the initial state for Conway's Game of Life, produces equivalent output to the original Turing machine"

QR codes are limited to a maximum size 172x172, which is not nearly large enough to built a Turing complete state machine in.
A current implementation of a Turing machine in GoL takes 1714 by 1647 cells.
It is undoubtedly sub optimal, but compressing it to 172x172 seems a stretch.

However let's assume the QR code is a little larger than 1714 square.
All of the elements in the listed Turing machine are constructable using gliders and besides much larger universal Turing machines have been constructed that are fully replicable.
Given a large enough QR code most of the key space is arbitrary.
There are some fixed elements that would have to be destroyed.
There are no known patterns that cannot be destroyed by a well timed glider salvo and certainly the fixed patterns in the QR codes have been explored.

Given the amount of redundant parent patterns that reduce to the same child pattern it is quite likely it is possible.
Furthermore the error correction only has a local effect, so changing a pattern in the top corner does not affect data at the bottom.

If you change the question to:

  If I stamp my GoL grid with many QR codes, can I built a turing machine?

Then the answer is yes, because its trivial to collapse a QR code to a glider and a Turing machine can be constructed using gliders and only gliders.


If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard? Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?

If $B$ is NP-hard then $A$ is NP-hard.

Can some explain this intuitively?

B being NP-hard does not say anything about A. The problem says that there is a way to reduce A to B in polynomial time.
But on the other hand, it is also not given that A getting reduced to B is the only pathway for solving A. So, there can be other ways of solving A in polynomial time.
Hence, the implication that A is NP-hard is false.


How do balancers work in the context of counting and balancing networks? I was learning what balancing networks are and at some point the art of multicore programming talks about balancers. The text book says:

  A balancer is a simple switch with two input wires and two output
  wires, called the top and bottom wires (or sometimes the north and
  south wires). Tokens arrive on the balancer’s input wires at arbitrary
  times, and emerge on their output wires, at some later time.
  A balancer can be viewed as a toggle: given a stream of input tokens, it
  sends one token to the top output wire, and the next to the bottom,
  and so on, effectively balancing the number of tokens between the two
  wires

from the discussion above it would seem that a balancer simple has a state up and down and it alternates between them and send tokens up and down (depending what state it is). Consider how the figure in the textbook defines a balancer:

It says that no matter the order and time, the tokens are split (balanced) as equal as possible between the above wire and the bottom wire. Therefore, no matter how the wires arrive, the balancer should maintain the invariant that the difference between top and bottom is at most 1.

The issue that I have is that it seems to describe the balancer as a state machine than alternates between up and down, but such a machine wouldn't actually be able to properly balance. It has to have some sort of state counting how many tokens it has sent up and how many it has sent down (so that it can balance).  The code presented by the book seems to do the alternating up and down (unless I misunderstood it):

It doesn't quite have a counter than makes sure that it maintains, the balancing invariant. If not, then how does it actually do it?

The book is correct, and the algorithm works as advertised. See if you can prove that it does. No explicit counting is necessary.

A very similar situation occurs for languages: $(ab)^*(a + \epsilon)$ is regular even though  $\{ w : 0 \leq \#_a(w) - \#_b(w) \leq 1 \}$ is not.


Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$ I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method:

$$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$

First, we have:

$a = 10,\ b = 2$ so we have $n^{\log_2^{10}} = n^{\lg10}$

Now we need to find how $f(n)$ compares to $n^{\lg10}$.

And here I'm stuck. What do I have to pay attention to in order to know whether I'm dealing with Case 1 (and look for $O(n^{{\lg10} - \varepsilon}))$ or Case 3 (and look for $\Omega(n^{{\lg10} + \varepsilon})) $ of the method?

My attempt:

From what I know $\log(n) < n^\varepsilon\quad \forall \varepsilon > 0$. So

$$\frac{1}{\log(n)} > \frac{1}{n^\varepsilon}$$
$$\frac{n^4}{\log(n)} > \frac{n^4}{n^\varepsilon}$$

$$\implies \frac{n^4}{\log(n)} = \Omega( n^{4-\varepsilon})$$

but I have no idea how to relate this (assuming no mistakes) with one of the two cases. In Case 1 we deal with $O(\cdot)$ and not $\Omega(\cdot)$ while in the 3rd Case the form of the exponents doesn't seem to match.

In order to apply Case 3, you have to show that $\frac{n^4}{\log n} = \Omega(n^c)$ for some $c > \log_2 10$, as well as the regularity condition (which holds for functions of the form $n^\alpha \log^\beta n$).

You take it from here. Hint: $4 > \log_2 10$.


Prove that context free languages are not closed under swapping prefixes and suffixes Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $

Obviously, we need to find a context free language $L$ such that $A(L)$ isn't context free. Here are some of my failed attempts:

Take the language $ L = \{\ 0^n1^n \mid n \in N \} $ and then (since the intersection of a context free language with a regular language is context free) we get: $ A(L) \cap 1^*0^*1^*0^*  = \{\ 1^{m}0^{n-k}1^{n-m}0^{k} \mid n,k,m \in N, m,k\le n \} $ which might look promising at first, but unfortunately this language is context free...

I also tried my luck with the following languages:
$ L = \{\ 0^n1^m0^m1^n \mid n,m \in N \} $
$ L = \{\ ww^R \mid w \in \{0,1 \}^* \} $

but these languages didn't help me either...

Did you try $\{\ a^nb^nc^md^m \mid m,n \ge 1 \}$?

Or, if you insist on alphabet $\{0,1\}$,
consider $\{\ (01)^n(011)^n(0111)^m(01111)^m \mid m,n \ge 1 \}$?

And be shure to intersect with a nice regular language after the operation, but from your question I see that you know how that works.


Minimal set of subintervals that 'covers' any subinterval in K subintervals I have a big interval $I = [a, b]$ of size n.

I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most $K$  subintervals - specifficaly I'm interested in $K = 3, K=5$ only, but general solution would be interesting too.

In other words, for any subinterval $i$ of $I$ I want to take at most $K$ (3, 5) elements of $S$ to get $i$. So if $i = [2, 28]$, one can take for example $[2, 10], [10, 20], [20, 28]$, if such subintervals exists in $S$ and $K=3$.

I've come up with solutions that are in $O(n^2)$ where $n = |I|$, but that is the same as naive approach of taking all the subintervals. I can get to about $1/K$ of that by having intervals of size $m$ to generate also the $K$ bigger intervals, but it seems it is in the spirit of the puzzle to have asymptotically better solution than $O(n^2)$, at least for $K=5$.

Let's consider the case $K = 2$. Given an interval $[1,n]$ of length $n$, we can construct the required set as follows:

If $n = 1$, take the entire interval.
Otherwise, let $m = \lfloor n/2 \rfloor$, and take the following intervals:

A solution for $[1,m]$.
A solution for $[m+1,n]$.
All intervals of the form $[i,m]$.
All intervals of the form $[m,j]$.

Denoting by $A(n)$ the number of intervals constructed in this way, we get the recurrence
$$
A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n,
$$
with initial value $A(1) = 1$. The solution of this recurrence is $A(n) = \Theta(n\log n)$.

Now let us proceed to prove a matching lower bound. Let $\ell_i = 2^i-1$, and let $I$ be the maximum value such that $\ell_i \leq n/2$; note that $I = \Theta(\log n)$. For each $1 \leq i \leq I$, consider the $n/2$ intervals $[1,\ell_i],\ldots,[n/2,n/2+\ell_i-1]$ of length $\ell_i$. Each of these is the union of at most two intervals in $S$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $2^{i-1} > \ell_{i-1}$. In total, this gives a collection of $n/2$ intervals in $S$ of length between $\ell_{i-1}+1$ and $\ell_i$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $n/2$ intervals). This shows that $S$ must contain at least $n/4$ intervals of size between $\ell_{i-1}+1$ and $\ell_i$, and so $\Omega(nI) = \Omega(n\log n)$ overall.

Here is a better construction for $K=4$. Divide the interval $[1,n]$ into $m=n/\log n$ subintervals $I_1,\ldots,I_m$ of length $\log n$. We construct the required set as follows:

Apply the construction recursively inside each $I_i$.
Every prefix and suffix of each $I_i$, $2n$ intervals in total.
The $K=2$ construction applied to $[1,m]$ and then blown up to $I_1,\ldots,I_m$ by replacing each interval $[i,j]$ to $I_i,\ldots,I_j$.

Let us first show that we can cover each interval $I$ using at most 4 intervals in the set. If $I \subseteq I_i$ for some $i$, then this is clear. Otherwise, suppose that $I \subseteq I_i \cup \cdots \cup I_j$, where $i$ is maximal and $j$ is minimal. So $I$ consists of a suffix of $I_i$, all the intervals $I_{i+1},\ldots,I_{j-1}$ (if any), and a prefix of $I_j$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $B(n)$ the number of intervals used in this construction. This quantity satisfies the recurrence
$$
B(n) = \frac{n}{\log n} B(\log n) + O(n).
$$
Opening this up, we get
$$
B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots,
$$
where the hidden constant is the same for all big O’s. The number of summands is $\log^* n$ (which is the number of $\log$s you have to apply to $n$ to reduce it below some constant), and so
$$
B(n) = O(n\log^* n).
$$
We can repeat this construction once again, for $K=6$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $O(n)$ intervals for $K=\omega(1)$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.


Sieve of Eratosthenes vs. Sieve of Sundaram Relevant Information:
Sieve of Eratosthenes
Sieve of Sundaram

Suppose I want to generate all primes in [2,n], and I have both of these algorithms at my disposal to get the job done. Which is preferable under what conditions?

I read that Sundaram runs in O(n log n) time, whereas Eratosthenes runs in O(n log log n) time, so it seems that Eratosthenes is preferable. However, that is just a very superficial evaluation. Are there other factors (aside from ease of implementation) to be considered? Which is the 'better' algorithm?

Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes.  In this evaluation, it is important to note that these intense considerations are only necessary for ranges of primes in the order of a hundreds of millions or more:  A simple trial division algorithm can be sufficient for a range of up to about a million and just about any properly optimized sieve can sieve to a billion in a few seconds to tens of seconds in just about any language that is not interpreted (compiled or Just-In-Time - JIT - compiled to native code).  It is large ranges of a billion an up where things get interesting in that the amount of memory used becomes a consideration such that it may be a requirement to implement page segmentation so as to be able to efficiently use the available memory.

First, note that there are three considerations on what makes a particular sieve fast, as follows:

The number of operations and how these operations increase for increasing ranges for a particular sieve, which latter evaluation is what is indicated by the big-O value for asymptotic execution complexity for large ranges.
The complexity of each individual culling operation as in machine cycles per operation which usually isn't considered in given big-O functions as per point 1.
The ability to add page segmentation without impacting excessively on the above two requirements, which segmentation is necessary to reduce memory requirements for large ranges so the sieve can be run at all, to achieve better cache associativity which otherwise will have a (large) negative impact on point 2 above.

Many mistakenly think that the best big-O performance is the best algorithm, but that is an error in analysis:  An algorithm may have the best big-O performance as in (say) O(N) for sieving (where N is the sieving range) but require either many more operations or such complex operations that the execution time for each operation is so high that the total time to execute to a given range may be much higher than for an algorithm with less operations/complexity such that it can never catch up to an algorithm with worse big-O performance for practical achievable sieving ranges; thus, it is usually not the best or only consideration for comparison and is more useful for predicting the performance of a given algorithm with increasing range as compared to itself.

The main three contenders are usually the following with the given big-O performance characterizations following:

The Sieve of Eratosthenes (SoE) - O(N log(log (N)))
The Sieve of Sundaram (SoS) - O(N log(N))
The Sieve of Atkin (SoA) - O(N) (i've added this one as it is usually considered...)

Let's consider these in order:

First, it is pointless to implement the SoE without including the very simple "odds-only" optimization that reduces the number of operations by a factor of about two and a half to about the same number of culling operations as the sieving range.  However, there is no reason to stop there, and with a little added complexity in using the maximally wheel factorized "combo sieve" as per the Wikipedia article, one can reduce this to about a quarter of the sieving range for ranges of about a billion to about a third of the sieving range for sieving ranges of about a trillion.  Thus, with maximum wheel factorization the number of culling operations aren't much more than the best of the other algorithms.  The majority of the inner culling loop(s) in which the SoE spends most of its time can be reduced to a very simple native code single clock cycle read/modify/write instruction with maximum optimization techniques so that even when averaged across supporting code and parts of the code that can't use this optimization, the average is still only two to three CPU clock cycles per culling cycle for ranges of trillions.  While it's true that operations get gradually a little slower on the average for larger ranges, they increase relatively slower than the practical application of the other algorithms.
The unmodified SoS algorithm can never approach the performance of other sieves due to not specifying the proper limits for the i and j variables, which can easily be limited so that the culling function i + j + 2ij never exceeds one half of the culling range value as larger values exceed the sieve buffer range.  However, the SoS still has many more operations than the "odds-only" SoE as it culls by the factors of all odd values rather than only the prime factors as for the SoE, which is why it has the O(N (log N)) performance rather than O(N ((log (log N))) performance; this makes a significant difference in the number of culling operations for culling ranges of a billion and above, and while the number of operations can be reduced by such techniques as pre-culling for small values of factor, this optimization (and more) can also be applied to the SoE.  Now, it could be improved by using a recursive loop so that it uses a secondary source of primes to generate the i values and letting the j values start from i up to maximum, and then observing that every increment from i + j + 2ij to i + (j + 1) + 2i(j + 1) is just i + j + 2ij + (1 + 2i) or just the value of the sieving base prime/factor, but that is exactly the algorithm for the "odds-only" SoE.  Once we've optimized the SoS into the SoE, we can apply the same further optimizations as it now identical.  So the SoS can not be considered as a competitor as in its simple form it is much less efficient and in its maximally optimized form it is the SoE.
The SoA is by definition a wheel factorized sieve by the prime factors of 2, 3, and 5.  The SoA once (and perhaps still does) enjoy quite a bit of Internet hype due to it's very good big-O performance of O(N).  However, while it does perform according to that relation with a constant about 0.2517 times N number of culls starting at a very low N value, all is not so rosy as believed:  It doesn't match that combined performance for any reasonably large range requiring page segmentation where primes squares-free spans get huge as compared to the page segment range and the complexity of the continuously increasing culling span means that the true combined big-O performance is much worse than that of the fully wheel optimized Sieve of Eratosthenes while the code complexity in implementing it even this efficiently is worse than the maximally wheel factorized SoE.  Much of the confusion comes about due to the reference page segmented implementation of the SoE by Atkin and Berstein, which, while reasonably fast in sieving to a billion, did not prove (even close) its claim of linear asymptotic big-O complexity with increasing range as it is very slow for larger ranges, and only beat the reference SoE to which it is compared for a range of a billion by artificially limiting the level of wheel factorization of that implementation.  As to the culling speed, due to the increased complexity of the span increasing with every successive operation, typical speed is about twice as slow as for the SoE in CPU cycles per operation, so it would have to have half the number of operations as the maximally wheel factorized SoE, which it never does within practical ranges.

In conclusion, for large sieving ranges using page segmentation, the Page Segmented SoE is a clear winner with the number of cull operations ranging only up to about 0.35 to very large ranges of 1e16 or more and the number of machine cycles when efficiently compiled to native machine code as little as under two CPU clock cycles per operation for small ranges under a billion and only increasing to the order of ten CPU cycles per operation for very large ranges (of about 1e19) in some common implementations such as primesieve, which can also be multi-threaded for even faster execution times.  Even when compiled in Just-In-Time (JIT) environments such as the Java Virtual Machine (JVM), Microsoft's DotNet, or even JavaScript engines as are builtin to modern browsers, the performance is still only about ten CPU cycles per operation with the number of operations the same.  In contrast, the unmodified SoS is many times slower and when fully optimized just becomes the SoE with its only feature over the SoE that it doesn't need the secondary primes feed for a page segmented version and thus the code optimized to the same extent is somewhat simpler, and the SoA never comes anywhere close to the number of CPU clock cycles per cull operation at any point as  for larger culling ranges such that the reduced number of culling operations is never enough lower to make up for this discrepancy nor for the increased complexity of implementation.


Difference between time complexity and computational complexity For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?

I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about space complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.

So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.

Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...).  It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).


functional vs state-based As mentioned in Lambda Calculus - Computerphile,

  Alonzo Church's method is functional where a function as a blackbox,
  takes an input, processes, and produces an output, and Turing machines
  have internal state.

First, I would like to know what does it exactly mean by functional and state-based?
Are they the same as the terms stateful and stateless?
And how are they related, similar and different from one another?

Not quite sure if this question is to be asked here or in Stackoverflow.

Ref: https://www.revolvy.com/main/index.php?s=State+(computer+science)
Ref: Learning fundamental differences between functional programming and Object Oriented Programming

The terminology isn't absolute when applied to actual languages. Usually "stateful" refers to holding the "state of the computation" largely in variables of some sort (variables = changeable references to values). These can be ordinary variables (C) or fields of objects (C++, Java). It is possible in many such languages, however, to minimize such state and to program largely with constants only and with parameters of functions and methods. The latter can be variables or constants, depending on the language.

The reason that stateful languages can be programmed this way is that they also employ a run time stack in which values can be maintained.

Stateless programming in most commonly done in functional languages that minimize the use of variables, depending on constants and constant function arguments. The computation "state" is the stack itself. However, most functional languages do have some mechanism for declaring variables (things which vary), though they also tend to call names that refer to constants as "variables" confusing the issue somewhat.

In "pure functional programming" you utilize only constants and immutable function arguments to move values around the computation. The "State of the Computation" is the state of the run time stack. This is true Stateless programming.

Most imperative and OO programming, on the other hand is stateful. The "State of the Computation" is comprised of both the state of the run time stack and the currently referenced values of the variables.

Another way to think of it is that in stateless programming, the state is "implicit" in the stack and the current program pointer. In stateful programming, the state is explicit in the variables and fields (to a large part - there is also the stack).


How many different trees can we form from given graph? I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$

In this graph I want to count the sub-sets of edges such that each subset will have exactly $N-1$ edges and the edges forming the subset will form connected graph.

Example

Let's say we have the following graph

We can count a total of 3 subsets: {1,2,3,5}, {1,2,3,4}, {1,2,4,5}. Please note the the numbers from 1 to 5 are marking the edges, not the nodes.

What I think

Let's say our graph is complete graph, it is the worse case. If we have 500 nodes and 499 nodes going out from each node, I think that there could be $500^{500}$ possible combinations which is huge number.

There is a simple algebraic algorithm based on the Matrix Tree Theorem.  Just make the Laplacian matrix of the graph and compute $N^{-1}$ times the product of its non-zero eigenvalues.


Depth of a pipeline in a CPU's architecture I follow a course on CPU architectures and I'm making exercises at the moment. Now I encountered the word "depth of a pipeline" in one of the exercises, but I don't know what's meant by the depth of a pipeline. Is it the number of stages of the pipeline or something else? I can't find it anywhere in the syllabus.

I think that depth is a measure of the overlapping of instructions while number of stages is a hardware constant. When you increase the number of stages, you usually make the CPU faster but it is with dimishing margin. See Almdahl's law about this and the book "Computer Organization and Design" by Pattersson and Hennesay.

The more stages, the larger the depth but it is stated that there can be optimal number of stages or optimal depth:

According to (M.S. Hrishikeshi et. al. the 29th International Symposium on Computer Architecture)

  The difference between pipeline depth and pipeline stages; is the
  Optimal Logic Depth Per Pipeline Stage which about is 6 to 8 FO4
  Inverter Delays. In that, by decreasing the amount of logic per
  pipeline stage increases pipeline depth, which in turn reduces IPC due
  to increased branch misprediction penalties and functional unit
  latencies. In addition, reducing the amount of logic per pipeline
  stage reduces the amount of useful work per cycle while not affecting
  overheads associated with latches, clock skew and jitter. Therefore,
  shorter pipeline stages cause the overhead to become a greater
  fraction of the clock period, which reduces the effective frequency
  gains.


UCT (Upper Confidence bounds applied to Trees) For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ?

Besides, I do not quite understand how UCT deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves.

This result is stated in:

Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.

It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.

The main reference for this is:

Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3), 235-256.

To give you some intuition about the convergence given infinite time, you need to understand the UCB1 formula: it makes a tradeoff between exploring the best move and exploring the least explored moves. As the term for exploring the least explored move can grow arbitrariy large and the payoff is smaller than 1, if you have infinite time, you will end up exploring it infinitely many times, even if its payoff is $0$.

Therefore, at a fixed node, given infinite time, you will explore infinitely many times each possible move. Repeat this by induction : you will explore the whole tree in infinite time. So in the end, what actually matters is the score of each node, as the exploration bias will go to $0$.

In short : what removes the MCTS flaw is the fact that you have infinitely many moves, it removes the randomness.


Complexity of special instance of Knapsack Consider the following algorithmic task:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\prod_i p_i^{d_i}$, subject to the requirements that $0 \le d_i \le e_i$ and $\prod_i p_i^{d_i} \le M$.

What is the complexity of this problem?  Is it NP-hard?

This problem is equivalent to the following:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\sum_i d_i \log p_i$, subject to $0 \le d_i \le e_i$ and $\sum_i d_i \log p_i \le \log M$.

This can be seen to be an instance of bounded knapsack with $k$ items, where the $i$th item has weight $\log p_i$ and value $\log p_i$ and can be used at most $e_i$ times, and where the capacity of the knapsack is $\log M$.  (See the footnote below for a more careful statement.)  Thus, my problem is a special case of bounded knapsack.  It follows that my problem is in NP.

But is my problem NP-hard?

For instance, is there a way to reduce from bounded knapsack to my problem?  It's not clear, because my problem limits the weights and values to be something specific related to the log of primes, rather than arbitrary values.

Footnote: strictly speaking, the bounded knapsack requires item weights and values to be integers, whereas $\log p_i$ isn't an integer.  However, we can fix this up by picking a sufficiently large constant $K$ and using $\lfloor K \log p_i \rfloor$ as the weight and value of the $i$th item, and use $\lfloor K \log M \rfloor$ as the capacity of the knapsack.  With this fix-up, my problem now becomes a special case of bounded knapsack, or reduces to bounded knapsack.

Your problem is at least as hard as the known-prime-factor version of this problem. Shor's reduction also applies to that version, and can be made effective by using this answer rather than the Wikipedia link in Shor's answer.


Finding the values for a particular bucket in a list I have a list of n items. I need to find the items that will be present in a given range, if the list were to be sorted. Sorting the entire list is not required and not desired, the buckets can be evenly spaced, but if an approach can handle a particular bucket starting at index i and ending at index j it would be preferred.

The ultimate goal is to have a sorted subset starting from index i and ending at index j. Though for the above problem sorting isn't required.

Example:

i := 2
j := 4
a := [9,0,1,8,2,7,3,6,4,5]
b := selectBucket(a, i, j)

[2,3] // b
[3,2] // also could work

I found an answer about dividing a list into k buckets, this approach is alright, but if there is a better way to get only a single bucket it would be preferred (that is of course faster).

You should use the Quick Select algorithm. I will spare you the details and let you look up the algorithm on your own if you do not know it, but quick select roughly does the following:

Given a list A of size n and and index i, the algorithm will return the ith smallest element of A. Additionally, A will be such that this ith element is in index i, all element earlier in the array are less than or equal to this element, and all later element are greater than or equal to this element. And it does this in O(n) time!

So, just use this algorithm twice on the two indices (you will need to restrict which part of the array you are using for the second query and change the index appropriately, but you can work this out), and you will get what you want! Hope that helps.

Here is a link to the Quickselect Wikipedia article (I have not read it to verify its accuracy): http://en.wikipedia.org/wiki/Quickselect


Removing lambda-productions when it's at the start symbol I had a question regarding removing lambda-productions from context-free grammars.

I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and replace them with the version of the same production when we use lambda. However, I had a question regarding special cases.

For example:

$$S \rightarrow aSSS$$
$$S \rightarrow bb\ |\ \lambda$$

How do I remove the lambda-production here? Is it even allowed to be removed? If we remove this, then we're fundamentally changing the grammar from one that accepts the empty string to one that doesn't.

This question has been really confusing me, and any help would be greatly appreciated.

thank you!

You cannot, in general, remove all $\lambda$ productions. Indeed, if you grammar produces the empty string, then somewhere in the grammar there must be a $\lambda$ production.

There are two ways to handle this problem:

Consider only grammars not producing the empty string. Such a grammar won't contain the product $S \to \lambda$.
Allow arbitrary context-free grammars, and also allow the production $S \to \lambda$ (but not $A \to \lambda$ for $A \neq S$). If the grammar does contain the rule $S \to \lambda$, then we also ask $S$ not to be on the right-hand side of any production. Such grammars behave very similarly to grammars without $\lambda$ productions, since the production $S \to \lambda$ can only be used in the derivation $S \Rightarrow \lambda$.


Number of states in an AND-OR DAG Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND node or an OR node.

Under this setting, I define a notion of a feasible state. A state is a feasible if and only if:

for every AND node in the true state, all of its parents are in the true state.
for every OR node in the true state, at least one of its parents are also in the true state.

(Note that a state can still be feasible even if some AND node is false but all of its parents are true.)

As an example, consider the following DAG. Grey nodes are leaf nodes (nodes 1 and 2), orange nodes are OR nodes (node 3), and red nodes are AND nodes (nodes 4,5, and 6). Note that nodes 4 and 5 can be classified as either AND nodes or OR nodes since they only have one parent.

There are 18 feasible states of this DAG if I counted right, as seen below. Nodes with a dark interior are true; nodes with a white interior are false.

Question: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?

Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no efficient algorithm for solving your problem. In particular, you won't find any closed form.

Roth showed that the number of satisfying assignments is even NP-hard to approximate within $2^{n^{1-\epsilon}}$ for any $\epsilon > 0$. This means that even finding a decent closed-form approximation can be ruled out.


Curry Howard correspondence to Predicate Logic? So I'm trying to get my head round Curry-Howard. (I've tried at it several times, it's just not gelling/seems too abstract). To tackle something concrete, I'm working through the couple of Haskell tutorials linked from wikipedia, esp Tim Newsham's. There's also a useful discussion when Newsham posted the tutorial.

(But I'm going to ignore Newsham's and Piponi's data wrappers, and talk about the underlying types.) We have Hilbert's axiom scheme (expressed as S, K combinators); we have propositions as types; implication as function-arrow; and Modus Ponens as function application:

axK :: p -> q -> p
axK  = const
axS :: (p -> q -> r) -> (p -> q) -> p -> r
axS     f                g          x  = f x (g x)

modPons = ($);   infixl 0 `modPons`          -- infix Left, cp ($) is Right

Then I can derive the identity law:

ident     = axS `modPons` axK `modPons` axK  -- (S K K)
-- ident :: p -> p                           -- inferred

Having these types as bare typevars merely corresponding to propositions seems rather unimaginative. Can I use more of the type system to actually construct the propositions? I'm thinking:

data      IsNat n  = IsNat !n                -- [Note **]

data      Z        = Z
axNatZ ::            IsNat Z
axNatZ             = IsNat Z

data      S n      = S !n
axNatS :: IsNat n -> IsNat (S n)
axNatS   (IsNat n) = IsNat (S n)

twoIsNat = axNatS `modPons` (axNatS `modPons` axNatZ)
-- ===> IsNat (S (S Z))

[Note **] I'm using strict constructors, as per the discussion thread, to avoid introducing _|_.

Where:

IsNat is a predicate: making a proposition from a term.
n is a variable.
S is a function, making a term from a variable.
Z is a constant (niladic function).

So I seem to have embedded (First-Order) Predicate Logic(?)

I appreciate my types are not very hygienic; I could easily mix up a typevar-as-proposition with a typevar-as-term. Perhaps I should use the Kind system to segregate them. OTOH my axioms would have to be spectacularly wrong to get to any conclusion.

I haven't expressed:

universal quantifier: it's implicit for the free vars;
existential quant: in effect constants could act as skolemised existentials;
equality of terms: I've used repeated typevars in implications;
relations: this seems to work, or is it fuddlement? ...

    data          PlusNat n m l  = PlusNat !n !m !l

    axPlusNatZ :: IsNat m       -> PlusNat Z m m
    axPlusNatZ   (IsNat m)       = PlusNat Z m m

    axPlusNatS :: PlusNat n m l -> PlusNat (S n) m (S l)
    axPlusNatS   (PlusNat n m l) = PlusNat (S n) m (S l)

    plus123 = axPlusNatS `modPons`
              (axPlusNatZ `modPons`
               (axNatS `modPons` (axNatS `modPons` axNatZ)) )
    -- ===> PlusNat (S Z) (S (S Z)) (S (S (S Z)))

Writing the axioms is easy, courtesy of Wadler's Theorems for Free!. Writing the proofs is hard work. (I shall drop the modPons and just use function application.)

Is this actually achieving a logic. Or is it crazy stuff? Should I stop before I do any more harm to my brain?

You're supposed to need Dependent Types to express FOPL in Curry-Howard. But I don't seem to be doing that(?)

To explain why I'm uncomfortable with Newsham's and (especially) Piponi's data wrappers ... (This is going to be more question than answer, but perhaps it'll work towards explaining what's wrong with my IsNat even though it seems very similar to Newsham.)
Piponi page 17 on has:
data Proposition = Proposition :-> Proposition
                  | Symbol String
                  | False deriving Eq

data Proof = MP Proof Proof
     | Axiom String Proposition deriving Eq

I see no types here. Spelling a data constructor :-> does not make it function arrow; and spelling a data constructor MP (for Modus Ponens) does not make it function application. There's a 'smart constructor' operator (@@) for MP, but that doesn't apply no function: it merely does pattern matching on the :-> constructor.
Newsham has (I'll start with the Implication section/Modus Ponens):
data Prop p = Prop p

data p :=> q = Imp (Prop p -> Prop q)

impInj :: (Prop p -> Prop q) -> Prop (p :=> q)
impInj p2q = Prop (Imp p2q)

impElim :: Prop p -> Prop (p :=> q) -> Prop q
impElim p (Prop (Imp p2q)) = p2q p

This looks more like it: we have types, function arrows, function application in impElim. The type constructor Imp with its injection and elimination rules mirror the proof tree structures in the Lectures on Curry-Howard isomorphism. But I'm nervous: why does Imp need a type constructor and data constructor? Again, spelling as :=> doesn't make that a function arrow. Why all this wrapping and unwrapping Prop constructors? Why not plain Prop (p -> q)?
So when I look at the 'Conjunction' section (which actually comes first):
data p :/\ q = And (Prop p) (Prop q)

andInj :: Prop p -> Prop q -> Prop (p :/\ q)
andInj p q = Prop (And p q)

andElimL :: Prop (p :/\ q) -> Prop p
andElimL (Prop (And p q)) = p

andElimR :: Prop (p :/\ q) -> Prop q
andElimR (Prop (And p q)) = q

Those Elim functions don't use function application. They merely pattern match on the constructors. There's no implicational structure for conjunction: we rely entirely that the 'programmer' has used only the andInj rule to build a type (p :/\ q).
So when Newsham gets to the commutativity of conjunction:
commuteAnd :: Prop (p :/\ q) -> Prop (q :/\ p)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

And claims

Notice that our Haskell proof did not contain any reference to the internal structure of the (:/\) data type. Having defined and proven our rules "andInj", "andElimR" and "andElimL" we shouldn't ever have to peek into the implementation of the (:/\) data type again.

I plain disagree:

The signature for commuteAnd does rely on the internal structure of the :/\ type constructor.
Although the function definition looks like merely function application, in fact the andElims do "peek" into the structure.

I'd expect we could prove the commutativity of conjunction from its definition, without needing an axiom to say so(?)
OK if I'm being so purist, what do I expect? This for conjunction is based on the Church encoding for pair:
type Conj p q r = Prop ((p -> q -> r) -> r)     -- not right, see later

andInj :: Prop p -> Prop q -> Conj p q r
andInj (Prop p) (Prop q) = Prop (\elim -> elim p q)

andElimL :: Conj p q p -> Prop p
andElimL (Prop conj) = Prop (conj axK)    -- axK is `const`

Now I can write commuteAnd using 'proper' function application:
--  commuteAnd :: (Conj p q r) -> (Conj q p r)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

That function definition is the same as Newsham's. But I've commented out the signature because GHC's inferred type is not general enough. It wants Prop ((p -> p -> p) -> p) -> ((p -> p -> p) -> p). Which is only a fancy variation on the Identity law.
Edit: (After @DerekElkins first comment here.) Scrap all this:

I've ended up in deep (and murky) water. I think my type for Conj needs to be more polymorphic, possiby Impredicative. I've mucked about trying to give a higher rank type:
type Conj p q = Prop (forall r.((p -> q -> r) -> r))

But GHC isn't playing. (And support for Impredicative polymorphism is "flaky".) And a forall-quantified thing like that looks suspiciously like the definition for False/uninhabited that I was expecting to use.

I do need a higher-rank type, but not Impredicative. And not on the type for Conj but for commuteAnd
commuteAnd :: (forall r. Conj p q r) -> (Conj q p r')
-- (same function for `commuteAnd` as above)

OK. I can happily swap arguments ad infinitum.
[End of Edit]
So my question: if it's legit what Newsham is doing with nesting constructors and pattern matching everywhere, then what's not legit about my IsNat and pattern matching?


Mapping reducibility from recursive to recursively enumerable language I want to find out whether, assuming a language $L_1$ being mapping reducible (i.e., $L_1$ maps to $L_2$ and the complement of $L_1$ maps to the complement of $L_2$) to a language $L_2$ and $L_2$ being recursively enumerable, $L_1$ is recursive or not.

I tried creating a recursive Turing machine for $L_1$ by using the recursively enumerable machine of $L_2$, but if the input belongs to the complement of $L_1$, its mapping will also be in the complement of $L_2$ and we cannot say anything about it.

So I tried proving by contradiction instead: Assuming $L_1$ is recursive, show that our assumption that $L_2$ is recursively enumerable is wrong. However, this will require an inverse mapping.
Alternatively, we could also try assuming $L_1$ is recursive and show that such a mapping cannot exist, but I can't think of any approach to it.

Can someone help me?

Mapping reducibility of two languages $L_1$ and $L_2$ is defined as a function which, when given a string in $L_1$, gives as output a string in $L_2$ and, when given as input a string in $L_1$ complement, gives as output a string in $L_2$ complement.

If $L_1 \le_m L_2$, that is, $L_1$ is many-one (i.e., mapping) reducible to $L_2$ and $L_2$ is recursively enumerable (r.e.), then $L_1$ must also be r.e. This is because an acceptor for $L_1$ can be derived by reducing any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ and then simulating the acceptor for $L_2$ (which exists on grounds of $L_2$ being r.e.) on $w'$.

However, in general, $L_1$ does not have to be recursive (which is strictly stronger than r.e.). In fact, any language $L$ is (trivially) many-one reducible to itself, so just take your favorite r.e. but not recursive language $L$ and note that $L \le_m L$ holds despite $L$ not being recursive.

Honestly, I believe your confusion arises from your unnecessarily complex view of many-one reducibility (i.e, on the basis of $L_1$, $L_2$, and their complements). Note that you can think of a reduction of $L_1$ to $L_2$ instead as mapping any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ under the condition $w \in L_1 \iff w' \in L_2$. Stating this based on the equivalence sign "$\iff$" avoids having to think about the complements of $L_1$ and $L_2$, thus avoiding unnecessary "clutter" in your thought process.


Variation of omega definition The same question has been asked here

  Some authors define $\Omega$  in a slightly different way: let’s use
  $ \overset{\infty}{\Omega}$
  (read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$
  if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq   0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n_0$.

  Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative,
  either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$

The solution given in the link hints that we can negate the definition of $ \overset{\infty}{\Omega}$ which gives us the definition of big O.

But negation of the definition of $ {\Omega}$ also gives us the same result, doesn't it?

I cannot wrap my head on how the condition of infinitely many integers makes difference rather than saying for all n greater than certain $n_0$.

Please help me understand this.

When you negate $\Omega$ you get $\stackrel{\infty}{O}$, the analog of $\stackrel{\infty}{\Omega}$. I suggest writing the definition of $\Omega$ as a first-order formula and then negating it.

To see the difference between $\Omega$ and $\stackrel\infty\Omega$, consider the functions $f(n) = n$ and $$g(n) = \begin{cases} 1 & \text{$n$ even,} \\ n^2 & \text{$n$ odd.} \end{cases}$$
You can check that $f(n) \neq O(g(n))$ and $f(n) \neq \Omega(g(n))$, whereas $f(n) = \stackrel\infty O(g(n))$ and $f(n) = \stackrel\infty\Omega(g(n))$.


Will MST find the shortest path for each pair $(r,v)$? Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes A,B and thus would make the path from root to A and B respectively not the global minimum?

This is Prim's algorithm, at page 634 (655 is pdf reader page):

While this is Dijkstra, at page 658 (679 is pdf reader page):

Book: Introduction to Algorithm 3ed.

No, the MST may not find the shortest path for each pair of nodes $(r,v)$.

For example, consider a graph of three vertices $A,B,C$ with edge weight $AB\mapsto 2, AC\mapsto 2, BC\mapsto 3$. Its MST is edges AB and AC. However, the shortest path between $B$ and $C$ is the edge BC.


What is the difference between Big-O and worst-case run time? Big-O describes an upper bound on run time. Is that not the definition of "worst-case"?

For example, how can we say that a hash table insertion require O(1) time on average? Constant time is the best case, n time is the worst case. How can an upper bound describe an average run time? In what sense is that bound "upper"?

Wikipedia says:

  Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

So it is not the definition of the "worst case".

Wikipedia defines best, worst, and average cases as

  In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

By resource we usually refer to time or/and space (memory) required to solve a certain problem.

It also says:

  Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case - for example, the worst-case scenario for quicksort is $O(n^2)$, but the average-case run-time is $O(n\log{n})$.

To sum up: Big-O notation is a pure mathematical concept and notation, which is used in Computer science to express the worst-case scenario for a given algorithm.

Here we have some useful posts:

How does one know which notation of time complexity analysis to use?
How do O and Ω relate to worst and best case?
Sorting functions by asymptotic growth


Can algorithms of arbitrarily worse complexity be systematically created? We’ve all seen this:

Can we get worse?

Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation?

Part 2: If they can, can algorithms of arbitrary complexities be systematically generated?

Part 3: If such algorithms can be generated, what about programs implementing those algorithms?

Yes, of course.  $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times.

The answer to your other questions are also yes, by the time hierarchy theorem.


Reason for differences between ways of specifying trees Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in another matter, emphasizing the root first (moving inward), you must specify any number of child nodes for each node? Seems like the second method requires more data to specify the same tree than the first. Or perhaps that’s not the case for all trees?

You're right. You need less space to save a tree with an adjacency list. But (like Dave Clarke's comment already says) there are more interesting fields, not only the space-complexity. Sometimes it is useful to spend more space to reduce for example the time-complexity of a problem. An easy example makes that point clear: If you represent your tree by saving the children of each node, you can compute the children of a given point in constant time (just looking which children are saved for the particular node). If you otherwise save the parent of each node, then you have to check every node in your tree (except the given point) to compute the children of a given node. In the first case you need more space and less time. In the second case you need less space, but more time.


Flajolet-Martin Algorithm : question about use of certain hash functions this is a question given in a PDF about streaming algorithms (this isnt an assignment but im trying to understand)

  Exercise 4.4.1 : Suppose our stream consists of the integers 3, 1, 4,
  1, 5, 9, 2, 6, 5. Our hash functions will all be of the form h(x) =
  ax+ b mod 32 for some a and b. You should treat the result as a 5-bit
  binary integer. Determine the tail length for each stream element and
  the resulting estimate of the number of distinct elements if the hash
  function is:

  (a) h(x) = 2x + 1 mod 32.

  (b) h(x) = 3x + 7 mod 32.

  (c) h(x) = 4x mod 32.

  ! Exercise 4.4.2 : Do you see any problems with the choice of hash
  functions in Exercise 4.4.1? What advice could you give someone who
  was going to use a hash function of the form h(x) = ax + b mod 2k ?

I have already resolved the first exercise, finding a max R tail length of 0 for (a) and 4 for (b) and (c), therefore the resulting estimation of distinct elements is respectively 1,16,16. (it is not asked to do averages/medians of the hash functions to find a better value)

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

Thank you in advance

you can observe the results of each hash functions by running this code : https://onlinegdb.com/rJXC4f4VL

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

You have the right idea. I believe what the question is trying to suggest is that this hash function has a problem with certain values of $a$ and $b$. Consider, in particular, $a = 16$. What will happen to the hash function in that case? How many possible values are there?

So, to pick a good value of $a$, we should probably make sure that $a = 16$ is not allowed. $a = 8$ is not good either. What do you suggest is a good choice for $a$?


What is the advantage of Greibach Normal Form over Chomsky Normal Form? I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.

There are actually several variants for these normal forms, so it might be useful to first recall the definitions. A context-free grammar is in Chomsky normal form if all of its production rules are of the form:

  $X \to YZ$
  $X \to a$
  $S \to 1$

where $X, Y$ and $Z$ are nonterminal symbols, $S$ is the start symbol, $a$ is a letter and $1$ is the empty word. A grammar is in Chomsky reduced form if its productions are of the form 1 or 2, but with $X$ and $Y$ being possibly equal to the start symbol.
The Chomsky Normal Form has been used to give a polynomial-time parsing algorithm (the CYK algorithm).

A grammar is in Greibach normal form if its productions are of the form

  $X \to aX_1 \dotsm X_k$
  $X \to b$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$ are letters. It is in Greibach quadratic normal form if $k \leqslant 2$ in all rules. It is in Greibach two sided normal form if its productions are of the form

  $X \to aX_1 \dotsm X_kb$
  $X \to c$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$, $c$ are letters. It is in Greibach quadratic two sided normal form (or Hotz normal form) if $k \leqslant 2$ in all rules. These normal forms have important applications in formal language theory. See for instance the article Towards an algebraic theory of context-free languages.


Trilinear interpolation for distorted cubes? Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)?

I know that I could use the inverse of the distance to each of the 8 corners as weights to get an interpolated point within the distorted cube, but that would involve taking a lot of square roots which would slow my algorithm way down. I like the elegant way of trilinear interpolation but I can't figure out how to adapt it to a distorted cube. Any hint on a fast interpolation method for this situation would be much appreciated.

Imagine a cube with each corner a different RGB color value - as you know you could interpolate the colors inside the cube using trilinear interpolation.

You can reuse this same logic for coordinates as well -- set the RGB values of the corners to be the XYZ coords of your distorted cube's corners.

Now the RGB "color" you sample in this cube is the distorted coordinate -- eg, it is the coordinate of your sampling point after that point has been "remapped" to the now-distorted cube, using the normal trilinear algorithm.

Hope this helps.


What is space complexity of shrinking one array to increase another? Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, I'm trying to convert a list to a string. I know that if I do the following, the space complexity will be O(N):

a = [1,2,3,4]
b = set(a)

But if instead I incrementally shrunk a, what would the space complexity be?

a = [1,2,3,4]
b = set()
for _ in range(len(a)):
    b.add(a.pop())

Now b has what I want and a is empty. Does that make it O(1) in space complexity?

If the language matters, I'm most interested in Python, but I would like to know the most general answer as well.

Space complexity is all very well on something like a Turing machine: you just define the space complexity to be the number of different tape cells that the tape head visits.  For real computers, things get much more complicated and very implementation-dependent.

It is possible that the algorithm you describe runs in constant space. If the array a is stored earlier in memory than the string b, the system could, in principle, delete the last character of a, shuffle everything after it back one memory cell, then add a character onto the end of b, so no extra memory is used.

In reality, though, it's much more likely that the system doesn't keep moving things around and just allocates new memory each time a character is added to b, which is probably linear space. Except it could be worse. Maybe, every time you try to make b bigger, the system actually allocates completely new storage for the extended string, which could give quadratic space usage.  Or maybe it's not that dumb and, each time you extend the string beyond its current memory allocation, it allocates a new chunk of memory that's double the size, so it can do lots of appends without reallocating memory every time. That would be linear, again.

And in real reality, what actually happens probably depends very much on what else is running on the machine. If there's lots of free memory, the system might be very happy to allocate fresh memory each time you extend the string, and it might only free the memory used by the old versions right at the end. If there is little free memory, it might free up unused memory much more aggressively.

So your code probably uses at least a linear amount of memory, but it's not really possible to be more precise than that.


Which article in front of O(.), Ω(.), ...? Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a $O(\sqrt{n}/\varepsilon^2)$ algorithm". And I am struggling to decide whether I should use "a" or "an" in front of these: is there a consensus/precedent?

(in hindsight, this may not be the best place to raise such profound questions; I was just unable to find any better one)

Write it as you pronounce it: "an omega". Or, especially when it can be pronounced with a vowel or consonant, rephrase to avoid the issue: "a bound of..."