Is there an isomorphism between (subset of) category theory and relational algebra? It comes from big data perspective. Basically, many frameworks (like Apache Spark) "compensate" lack of relational operations by providing Functor/Monad-like interfaces and there is a similar movement towards cats-to-SQL conversions (Slick in Scala). For instance, we need natural join (assuming no repetitions on indexes) for element-wise multiplication of vectors from SQL-perspective, which could be considered as zip + map(multiply) (Spark's MLib, however, already has ElementwiseProduct) in Category Theory's applications.

Simply saying (following examples are in Scala):

the referenced subcase of join can be thought as applicative functor (over sorted collection), which in its turn gives us zip: List(1,2,3).ap(List(2,4,8).map(a => (b: Int) => a * b)) --> (List(1,2,3) zip List(2,4,8)).map(x => x._1 * x._2). Moreover, we can induce it to some other joins, assuming some preprocessing (groupBy operator or just surjection, or generally - an epimorphism).
other joins and selection can be thought as monad. For instance, WHERE is just: List(1,2,2,4).flatMap(x => if (x < 3) List(x) else List.empty) --> List(1,2,2,4).filter(_ < 3)
data itself is just ADT (GADT too?), which in its turn looks like a simple Set-category (or more generally speaking - Cartesian-closed), so it should (I suppose) cover Set-based operations (due to Curry-Howard-Lambek itself) and also operations like RENAME (at least in practice).
aggregation corresponds to fold/reduce (catamorphism)

So, what I'm asking is can we build an isomorphism between (maybe subset of) category theory and (the whole) relational algebra or is there something uncovered? If it works, what exact "subset" of categories is isomorphic to relalgebra?

You can see that my own assumptions are quite broad while formal solutions like Curry-Howard-Lambek correspondence for logic-cats-lambda are more precise - so actually, I'm asking for a reference to an accomplished study (that shows a direct relationship) with more examples in Scala/Haskell.

Edit: the accepted answer made me think that I went too far representing joins and conditions as a monad (especially using an empty value that effectively instantiates FALSE), I think pullbacks should suffice at least for relalgebra subset of SQL. Monads are better for higher order (nesting) stuff like GROUP BY, which isn’t part of relalgebra.

Let me articulate the Curry-Howard-Lambek correspondence with a bit of jargon which I'll explain.  Lambek showed that the simply typed lambda calculus with products was the internal language of a cartesian closed category. I'm not going to spell out what a cartesian closed category is, though it isn't difficult, instead what the above statement says is you don't need to know! (Or that you already know, if you know what the simply typed lambda calculus with products is.)  For some type theory/logic to be the internal language/logic of a category means 1) that we can interpret the language into the structure on the category in a way that preserves the structure of the language (in effect a soundness condition), and 2) and "essentially" all the structure arising from cartesian closure can be talked about in terms of this language (a completeness condition).

The relational algebra is equivalent to the tuple or domain relational calculus which is essentially first order logic.  This statement is roughly Codd's theorem, though a similar theorem was proved decades earlier by Tarski for FOL and cylindrical algebras.  There is a bit of a subtlety though.  We want the queries in the relational calculus to be domain independent, which is to say that expanding the domain of possible values doesn't change the results of a query.  An example of a relational calculus query that is not domain independent is $\{ x\mid x = x\}$.  Every relational algebra expression is logically equivalent to a domain independent query in relational calculus.

Putting that aside, the categories whose internal logic (which is essentially a decategorified or proof-irrelevant form of an internal language) are Heyting categories for intuitionistic FOL and Boolean categories for classical FOL.  (The categorified/proof relevant versions are described by hyperdoctrines.  Also very relevant are pretoposes of various sorts.)  Note, that FOL, the relational calculus, and the relational algebra do not support aggregation.  (They also don't support the recursion necessary to represent a Datalog query.)  One approach to GROUP BY and aggregation is to allow relation-valued columns which leads to higher-order logic (HOL) and the nested relational calculus (NRC).  Once we have relation-valued columns, aggregation can be formalized as just another "scalar" operator.

Your examples point to the fact that a monadic meta-language is a decent language for queries.  The paper Monad Comprehensions: A Versatile Representation of Queries (PDF) spells this out well.  A more comprehensive and modern look is Ryan Wisnesky's PhD thesis, A Functional Query Language with Categorical Types (PDF), which is related to David Spivak's work which itself seems rather relevant to any interpretation of your question.  (If you want to go more historical, there was the Kleisli, A Functional Query System.)  In fact, the monadic meta-language is a decent language for queries in the nested relational calculus.  Wisnesky formulates NRC in terms of an elementary topos whose internal language is the Mitchell–Bénabou language which basically looks like an intuitionistic set theory with bounded quantifiers.  For Wisnesky's purpose, he uses a Boolean topos which will instead have a classical logic.  This language is quite a lot more powerful than (core) SQL or Datalog though.  It is worth noting that the category of finite sets forms a (Boolean) topos.


Compilation speed dependent on CPU? Is the speed of compiling software very dependent on the CPU? I know this question is a bit broad, but I'm to find an answer to the case described below.

If I download a software project that makes use of Node.js, TypeScript, and JavaScript and compile it running yarn it takes a certain duration on machine A and another duration on machine B. In my test case machine A is equipped with an Intel i5-4570 and machine B is equipped with an AMD Ryzen 5 1600x. Both have 16 GB RAM and both also have similar SSD drives in use.

Now, if I run the software compilation on both machines, machine A takes about 1:30min and machine B takes about 1:20min. Hence, machine B is not significantly faster, even though the CPUs are quite different in capability and get different scores according to CpuBenchmark:

Intel i5-4570: 7109 CPU Mark
AMD Ryzen 5 1600x 13232 CPU Mark

The single core rating of both CPUs is quite similar at around 2000 Points, but when I run compilation all cores move up to 100% according to system power statistics.

I also checked the network usage, but doesn't move over 10kB/s and is therefore negligible. The RAM use fluctuates within about 1GB in both systems between 9GB and 10GB.

Now, as the expected results differ quite intensly to the reality, I obviously am missing a point. So, an experienced input of some of you guys would very much help.

Is there anything else I could measure? Is there anything I missed or maybe don't know and therefore should further test? I basically want to find out, why the Ryzen is not significantly faster than the Intel mentioned above.

Things you are missing is

RAM performance: Intel CPUs has lower memory latency, and compilation speed significantly depends on memory latencies
Amount of cores/threads: each Ryzen core is slightly slower than Intel core, but it has 1.5x more cores, and each core can run 2 threads. This makes it 1.5x faster for ideal multi-threaded tasks (like benchmarks), but real programs may be not ideally scale from 4 to 12 threads
SSD speed, in particular 4K IOPS (i.e. speed of reading many small files)

F.e. first test on this page compares C++ compile times on various Intel/AMD CPUs:

8700K: Intel 6-core
7820X: Intel 8-core with slower memory controller
2700X: AMD 8-core
2600X: AMD 6-core

As you can see, Intel 6 cores outperformed AMD 8 cores and even Intel's own 8 cores coupled with slower memory controller.

And this page discusses a lot memory/cache latencies.


What is the height of an empty BST when using it in context for balancing? Suppose the datatype for a BST is defined as follows (in SML)
datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

So there are two cases one in which the BST is Empty or it can have a (key,value) as well as two children.
Now, for the case of an AVL where the condition is

In an AVL tree, the heights of the two child subtrees of any node differ by at most one
- AVL tree Wikipedia

I want to able to create a height function for use to check whether the tree is balanced. My current setup is as follows
fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

I tried to separate the Tree into three conditions

A empty Tree
A Tree with a root node
A populated tree

The reason for this is that there does not seem to be a canonical source on what the value is for the height of an Empty Tree as opposed to one in which only has a root. For the purposes of my balance function it did the job, but I rather try to understand why there isn't a canonical answer for the height of an Empty Tree.
There is a canonical answer, in a matter of speaking on Wikipedia but while initially doing research on this on Stack Overflow I arrived at many comments stating this to be wrong/incorrect/unconventional

Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.)

I grabbed the question from which my uncertainty appeared
What is the definition for the height of a tree?

I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.
The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.

Any constant works as the height of Empty, because only the difference of heights is important for balancing. So, why not choose 0?


O(n) external intersection points? I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (external intersection meaning if the point is not contained in the interior of the union of all the squares).

Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$:

Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).


Prove the following language is in L (LogSpace) I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space):

$$A = \{ (C,x) \mid  C(x)=1\text{ and $C$ is a Boolean formula with depth }\log(n)\}\,,$$
where $n = |(C,x)|$. Equivalently, $C$ can be a Boolean circuit with maximum fan-out of $1$.)

Checking if a word $w$ is in "the right format" (meaning: $w=(C,x)$ for some $C$ Boolean formula/circuit, $x$ – input) takes $O(1)$ space. I'm not sure on how to check the value of the formula (thought of using recursion, but not sure how) such that it will need only $O(\log n)$ space. Also, how can I check that the depth of the circuit is $\log n$?

A Boolean formula is a circuit whose graph is a tree (each node has a single parent). Perform an in-order pass on the tree while remembering the current node and the last value.

When at a $\lor$ gate with a previous value $b$: If $b = 0$ leave the value the same and go to the node's parent. If $b = 1$ check the other (right) son. Same with $\land$ gate, and $\lnot$ gates are easier (check if $b = 0$). Accept $(C, x)$ if the value computed by $C$ (using the in-order search) is $1$.

Saving the current node takes $\log n$ bits, the current value takes $1$ bit and computing the parent also takes $\log n$. Overall there is a TM that uses $O(\log n)$ space that decides $A$, so $A \in L$.


Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam.

And I am having difficulties in digesting the correct answer of this problem. Why is my approach incorrect?

Here is my approach:
The divide part of the merge sort recursively divides the list of strings into sub-lists with half number of strings each.

Then the merge part takes sorted lists from two of its child node and merge them into its own sorted list. This merging propagates upwards towards the root and the entire list is eventually sorted.

The merging works this way:
The two child-lists together have $(n1+n2) = O(n)$ strings. And for comparing two strings as the part of merging, we need to compare at most $n$ positions (since the strings are of length $n$).

So the merging takes $\theta(n*n) = \theta(n^2)$

Now the recurrence equation looks like: $T(n)= 2T(n/2) + \theta(n^2)$

Using master method $n^{log_22}=n$
And $f(n)=\theta(n^2)=\Omega(n^{log_22})$

Which is case 3 of Master method. so $T(n)=\theta(f(n))=\theta(n^2)$ should be the correct answer.

The mistake and correction

$$T(n)= 2T(n/2) + \theta(n^2)$$

As you intended, $T(n)$ is the worst time of mergesorting $n$ strings of length $n$. Then, $T(n/2)$ on the RHS means the worst time of mergesorting $n/2$ strings of length $n/2$. So during the mergesort, the length of strings shrinks from $n$ to $n/2$!

What should have been done is using a different variable to express the number of strings at the start of each mergesort. Let us define $T(m, n)$ to be the cost of mergesorting $m$ strings of length $n$. Now, we will have

$$T(m, n)= 2T(m/2, n) + \theta(mn),$$

from which we can deduce $$T(m,n) = \theta(nm\log m).$$

Another correct approach

Mergesort of $n$ items takes $\theta(n\log n)$ time, assuming a unit cost of comparison. In fact, mergesort uses $\theta(n\log n)$ comparisons. Now that it costs $\theta(n)$ to compare two strings of length $n$ at worst time, the worst time of mergesort of $n$ strings of length $n$ should be $\theta(n\cdot n\log n)$.


Understanding Logical to Physical Addressing I am trying to understand the concept of logical to physical addressing.
I am given 72 physical addresses (0-71) with values

A virtual address = 2^(p+w)
p = page bits
w = word bits

I know the page table is of size 6 indexed 0-5

If a page size is 16 words does that mean that the offset(w)=4, giving me 2^(p+4).

If thats the case how do I determine what the page number (p) if given a logical address of 12?  I was thinking it would be 3 because I would need 3 bits to find the index of the page table 0-5, giving me 000 1100, index 0, offset 12. I feel like I might be missing something.

I think you are confused in how logical address is get converted into physical address of main memory.
Let's take a walk from basics:
logical and physical memory are divided into fixed size pages and frames respectively to remove external fragmentation.

As size of logical memory is generally bigger than physical memory so we can't bring all pages from logical memory into physical memory that's why we require a page table that contains the entry of pair(page no. , frame no.).

Now as always CPU generates a logical address of say 15 bits with 10bits for page size and 5bits for identifying frame no. from page table(5bits means that there can be maximum 2^5 pages), now using those 5 bits cpu index page table and find the frame no. in which the required page is residing say that's of 4 bits(that mean a maximum of 2^4 frames ) then the physical address will be made by replacing 5bits by those 4bits + 10bits in logical address.

Your interpretation in question is correct.


What happens when two processes hold an election using bully algorithm simultaneously A coordinator is used to sychronise the usage of resources in a distributed system.

The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator disappears for some reason.

I am just wondering what happens when two processes realise the demise of the coordinator simultaneously and both decide to hold an election using the Bully Algorithm?

Both processes will anounce themselves. However, the one with the highest indentifier will become the leader. For example, 3 and 4 announce themselves. 3 asks who has an id greater than me, and 4 responds. Then 3 knows 4 is the new leader. 4 does the same. No process replies. 4 tells everyone that he's the new leader.


Right linear grammar special case According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$,
does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$ can be written as $A\to \epsilon B$ though...

In your definition, $x$ must be a terminal symbol. In particular, it cannot be $\epsilon$, which is the empty string. The productions $A \to B$ and $A \to xy$ don't conform to the specifications you give, hence they don't belong in a right linear grammar according to the definition you provide.


How can I make sense of amortized accounting method? Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read).

In the example of the Stack with Multiple Pops (From CLRS, for reference: http://chuck.ferzle.com/Notes/Notes/AlgorithmAnalysis/Amortized.pdf), we arbitrarily "assigns" a credit of 2 two the Push operation, 0 for pop and 0 for multipop, and each push we arbitrarily "spend" 1 credit and the objected pushed onto the stack "stores" 1 credit.

This has to be the most insane thing I have ever seen in my life! Even if I get pass the "why 2 but not 100 credits" stage, how can I rationalize the fact that the object somehow stores a credit? How can we just arbitrarily assign these costs to these operations? Also how could you possibly gain anything insightful from this?

It is like imagining that typing on this computer will earn me $100 USD and shutting off the computer will make me spent 20 USD. Can someone please shed a light on how this technique works?

Amortized analysis is a strategy for analyzing a sequence of operations irrespective of the input to show that the average cost per operation is small, even though a single operation within the sequence might be expensive.

As it is shown in the above quote, amortized analysis is applicable particularly to a sequence of operations in which cheap operations occur frequently and expensive ones occur rarely. Moreover, in an operation sequence, the expensive operation is often related to (OR caused by) the cheap ones before it. For example, in your "Multi-Pop Stack", the cost of the expensive operation multi-pop(S,k) depends on the number of elements in the stack and thus on the earlier push(S,x) operations.

If we focus on a single multi-pop(S,k), we may be disappointed by its expensive cost. Worse still, its cost varies, depending on the current state of the stack when it is issued: if it has popped $t$ elements, then its cost is $t$. By accounting method, we turn to a sequence of operations and attribute (average) the varying cost $t$ of multi-pop(S,k) to the $t$ Push(S,x).

  Even if I get pass the "why 2 but not 100 credits" stage, $\ldots$

Yes, you can use 100 credits. However, 2 is tighter in terms of worst-case time complexity.

  $\ldots$ how can I rationalize the fact that the object somehow stores a credit?

"Credit" is only an analogy. We are charging the cost of some (expensive) operations to earlier (cheap) ones. From a different perspective, the earlier (cheap) operations had better save credits for further use of some (expensive) ones.

  How can we just arbitrarily assign these costs to these operations?

They are of course not arbitrarily assigned. Instead they are well chosen.


In Operating Systems, I can't understand why deadlock happens, why does a process not let go of a resource when it is done using it? I know deadlock occurs when Process A has resource R1 and is waiting for resource R2, while process B has resource R2 and is waiting for resource R1, however why don't both processes just let go of the resource they are currently owning before/while waiting for the other resource? How does A keep holding on to R1 even though it is waiting for R2.

To answer part of your question: Processes are not smart. Processes just execute the code of their program, so if the program of P1 has not been written to release R1 when it's done with it, it won't be released.
Besides, the classical setting in which a deadlock happens does not have to do with processes not releasing resources after they are done with them, but rather with competing processes trying to acquire the needed resources.
Process A needs both R1 and R2 to perform some task, so it starts acquiring them. It acquires R1, and tries to acquire R2.
Just before P1 gets to acquire R1, some process P2 that also needs both R1 and R2 tries to acquire them. This time P2 starts with acquiring R2, and succeeds.
At this point the following two things happen:

P1 tries to acquire R2 which is unavailable, so it waits for R2 be released.
P2 tries to acquire R1 which is unavailable, so it waits for R1 be released.

From this point on both P1 and P2 are stuck waiting for another resource that will never be released, i.e., they are in a deadlock.
Notice that no process ever held a lock on a resource that didn't intend to use.
The problem was that P1 and P2 tried to lock the resources in a different order.
Finally, you might think that when P1 tries to acquire R2, and finds that it is unavailable it could just temporarily release R1 and try to acquire both R1 and R2 at a later time.
However, without additional synchronization, this also doesn't ensure that P1 and P2 will manage to acquire the needed resources. The following could happen:

P1 acquires R1, P2 acquires R2.
P1 tries to acquire R2, and finds that R2 is unavailable.
P2 tries to acquire R1, and finds that R1 is unavailable.
P1 releases R1.
P2 releases R2.
P1 acquires R1 and is about to acquire R2.
P2 acquires R2 and is about to acquire R1.
P1 tries to acquire R2, and finds that R2 is unavailable.
P2 tries to acquire R1, and finds that R1 is unavailable.
....


Why isn't SAT in coNP? I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I'm missing why the following machine doesn't turing recognize the complementary of SAT:
Given a turing machine M that recognizes SAT, the following turing machine recognizes coSAT:

Run M on the input word w.
If M accepts - reject.
If M rejects - accept.

Because coSAT is the language of all unsatisfiable formulas, a formula is unsatisfiable if it doesn't have a satisfiable interpretation, which is exactly the opposite of what M outputs.
What am I missing in here?

You are missing a major part of the definition of $CoNP$: you need a proof that your machine $M$ runs in nondeterministic polynomial time for all "yes" inputs. Because you have simply taken the NP SAT algorithm and flipped it, it runs in nondeterministic polynomial time for all "no" inputs. But we have no such guarantees for the "yes" inputs.
The real answer is, nobody knows that SAT isn't in $CoNP$. If we knew that, we would know that $CoNP = NP$, but this is still an open problem. So, nobody can point to a specific reason that you can't build a machine that decides the complement of SAT it nondeterministic polynomial time. It's just that nobody has been able to do it yet, or prove that it's impossible.


What is the simplest algorithm to compress a string? I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call any library so I have to code my own data compression algorithm. What would be the simplest algorithm to achieve this goal?
I could code the smaz algorithm myself but it does not seem to work very well with long strings.

If you need something reasonably effective but not very taxing to implement, I would recommend LZW.
LZW has several advantages, not the least of which is that it uses fixed-width codes (the width strictly increases as compression proceeds), rather than Huffman or arithmetic coding. It also does not require string searching through a sliding window, instead performing hash table or tree lookup per input character. This means that it requires significantly less code to implement than methods based on LZ77.


Is the memory usage of total languages deterministic? I'm interested in the memory usage of various programming languages when implemented on actual hardware.

I believe that a Turing-complete programming language has, in general, unknowable memory usage since object lifetimes are not statically analyzable [1]. It also seems like a regular expression language (in the deterministic finite automata) has statically known memory use.

What is the most complex programming language for which that is true? And where do total languages [2] fall in relation to that?

[1] Given the caveat that we're implementing that programming language on a physical computer with all its requisite limitations.

[2] A total language is, for the purposes of this question, a language where all programs written in it are guaranteed to terminate.

Because total programs cannot run forever they cannot use infinite memory. You can know maximum, and best case cost from looking at what algorithm is implemented. Checkout these wikipedia pages to see the relationship between different grammars, algorithms, and machines:

"https://en.wikipedia.org/wiki/Complexity_class"
"https://en.wikipedia.org/wiki/Computational_complexity_theory"
"https://en.wikipedia.org/wiki/Chomsky_hierarchy"


Necessity of convolution operations for product of two polynomials via brute force method Reference: Page 4 of this document

Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$.

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

However, if we wanted to evaluate this product with some given input $x$, we can evaluate the two polynomials $p(x)$ and $q(x)$ separately and then multiply the two scalar results. Overall, this would take $\mathcal{\Theta}(n)$ time for two evaluations and a scalar multiplication. This lets us avoid having to do convolutions and would be faster than $\mathcal{\Theta}(n^2)$.

Question: When it comes to evaluation of the product of two polynomials, is it actually $\mathcal{\Theta}(n)$ using the method above or are we somehow still doomed to $\mathcal{\Theta}(n^2)$?

I'm aware there's a faster way to do this in $\mathcal{O}(n \log n)$ time via Fast Fourier Transform, but I'm more curious about the necessity of the convolution calculations. I suspect it's more if we care about getting the coefficients of the product than the actual evaluation, as in we more care about knowing $\{c_0, c_1, c_2, \dotsc\}$ than $c(x) = p(x)q(x)$.

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

That's not what it says. It says firstly that convolution is equivalent to polynomial multiplication (i.e. an algorithm for convolution is also an algorithm for polynomial multiplication and vice versa); and secondly that

  The direct approach is to compute all $c_k$ using the formula above

and that this approach has complexity $\Theta(n^2)$. The FFT approach calculates a convolution (and indeed, the continuous Fourier transform produces a convolution of two functions: the convolution of two coefficient sequences is a discrete analogue).


Is there an online algorithm for radix conversion? Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$.  The obvious algorithm is: interpret $P$ to obtain $n$, then calculate $Q$ from $n$.  This is easy.

But if $n$ is very large this could require a lot of memory, and it could require a large amount of processing before any of the digits of $Q$ are emitted.  In certain special cases we can do better; there is an online algorithm which can start producing output before all the input is read.  For example, if $p^i = q^j$ then the algorithm can read $i$ digits of $P$ and immediately produce $j$ digits of $Q$ without any further input and with only a constant amount of memory.  This method is used, for example, in converting generic computer data ($p=256$) to “Base64” format ($q=64$).

Is there a general online algorithm for radix conversion?  I expect that if there is such an algorithm, in the worst case it cannot emit any digits of $Q$ without first reading all of $P$, but are there algorithms that can often do better than this, in cases more general than the very unusual $p^i=q^j$ situation?  Or are there any other special cases of interest?

[ Related thread: The math behind converting from any base to any base without going through base 10? but all of the suggestions there ingest the entire input before producing any output. ]

This answer is not complete, but it is the start of a complete answer, and nothing else has been offered.  I hope to finish it another time.

I have found that an online right-to-left algorithm exists in a more general case than I mentioned in my original question.

I suspect that no such algorithm exists in general, for reasons I outlined in my comment.  What would the online algorithm produce first?

Units digit first

Suppose the algorithm wants to produce the units digit of $Q$ without reading all of $P$.  Represent $n$ in base-$p$ as $n = \sum_i d_ip^i$ where each base-$p$ digit $d_i$ is between $0$ and $p-1$ inclusive. The units digit of $Q$ is equal to $n\bmod q$ which is $$\Bigl(\sum_i d_ip^i\Bigr)\bmod q.\tag{$\star$}$$  The result depends on every one of the $d_i$ unless the corresponding term $d_ip^i$ has the same value $\bmod q$ for each possible value of $d_i$.  In particular we must have $$0\cdot p^i \equiv 1\cdot p^i\pmod q$$ so $p^i$ must be a multiple of $q$ in order for us to ignore the $i$th term of the sum.  Say $p^{k_0}$ is a multiple of $q$ for some $k_0$.  Then in computing the units digit of $Q$ we can disregard all the terms of the sum with $i\ge k_0$, and we need only examine the first $k_0$ digits of $P$.

To compute the next digit of $Q$ we can disregard all the terms of the sum with $i\ge k_1$ where $k_1$ is the smallest number for which $p^{k_1}$ is a multiple of $q^2$, and so on.

For example, suppose $p=6$ and $q=8$ and $n=3021213_6$.  $6^3$ is a multiple of $8$ so we can generate the units digit of  $Q$ just by examining the last three digits of $P$.  $2\cdot6^2 + 1\cdot 6 +3 \equiv 1\pmod 8$ so the units digit of $Q$ is 1.   Reading the next three digits of $P$ will allow us to compute another digit of $Q$, and so on.

This situation includes the case of $p^i=q^j$ that I discussed in the original question, but it is more general.

Note that although the $k_i = O(i)$ it may not increase smoothly.  We actually have $k_i = \lfloor c(i+1)\rfloor$ for some rational constant $c$ that depends on $P$ and $Q$.  For example, $24$ is a multiple of $4$, and so $24^2$ must be a multiple of $4^2$, but it is also a multiple of $4^3$.  Next $24^3$ is a multiple of $4^4$ but not of $4^5$.  So when converting from base $24$ to base $4$, reading the first digit of $P$ gets you one digit of $Q$, but reading the next digit of $P$ gets you not one but two more digits of $Q$. Reading the third digit of $P$ gets you only one more digit of $Q$.  Here $c = \frac32$.

(To come: most significant digit first; intermediate digits first.)


Primitive recursive plus Ackermann Let us consider the class $\cal F$ of functions that contains

all constant functions
all projections
the successor function
the Ackermann function

as basic functions, and that is closed under composition and primitive recursion.

(If we remove the line with the Ackermann function from this definition, then
this is the standard definition of the class of primitive recursive functions.)

  My question: What function class $\cal F$ do we get by adding the Ackermann function as basic function? Do we get all $\mu$-recursive functions, or do we get some strange sub-class?

A very nice question!

You just ventured into a large body of knowledge and research in computational theory around the concept of relative primitive recursiveness and hierarchy of total recursive functions such as fast growing hierarchy, which are full of interesting and mind-boggling facts.

  What function class $\cal F$ do we get by adding the Ackermann function as basic function?

Well, that is one of its own kind.

  Do we get all $\mu$-recursive functions?

No. What we get are far far from all $\mu$-recursive functions since all functions we get are still total recursive functions as primitive recursion preserves totality. Recall that $\mu$-recursive functions means partially recursive functions or, what is equivalent, all functions that can be computed by Turing machines.

You might ask, then, do we get all total recursive functions?

The answer is still no. What we get are far from all total recursive functions. For example, a "Ackermann modification of Ackermann function" is not included. Here is a version of that "doubly Ackermann" function.

Let us start from the usual two-argument Ackermann–Péter function.
$$A(m, n) =
\begin{cases}
n+1 & \mbox{if } m = 0 \\
A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\
A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.
\end{cases}$$
Let $f(n)=A(n,n)$ be the Ackermann–Péter function of a single-argument. Now let us define
$$D(m, n) =
\begin{cases}
f(n) & \mbox{if } m = 0 \\
D(m-1,1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\
D(m-1, D(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.
\end{cases}$$

Then $D(m,n)$ is a doubly Ackermann function, which cannot be obtained from composition and primitive recursion of Ackermann functions and all primitive recursive functions. This is not surprising, since a single Ackermann modification accelerates the growth of a strictly increasing function faster than arbitrarily finitely many compositions and primitive recursions.

You may continue to ask, what if we add that doubly Ackermann function? Then we are missing the "triply Ackermann functions". If you keep asking, then you will be building a growing hierarchy by Ackermann modification. Even if you have asked $\omega$ times this way, where $\omega$ is the first infinite ordinal, the growth rate of any function thus obtained is still dwarfed by most of functions in the fast growing hierarchy.

  or do we get some strange sub-class?

You may call it some strange sub-class as you like. However, as you might have expected, it is not unusual at all in the field of computation theory. Here is an excerpt from paper The Ackermann functions are not optimal, but by how much? by H. Simmons, slighted edited.

  5.1 DEFINITION. For each set $\Theta$ of functions, let
  $PR(\Theta)$ be the clone of those functions that can be obtained from members of $\Theta$ by primitive recursion. $PR(\Theta)$ is also called a primitive recursive degree. The primitive recursive degrees measure the complexity of functions up to primitive recursive equivalence.

The "strange sub-class" of yours is just $PR(\alpha)$, where $\alpha$ is the set of primitive recursive functions and the particular versions of Ackermann function you have in mind. In that paper, "by taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees."

Hopefully, I have shown you a glimpse of the fascinating theory around recursiveness and growth of total recursive functions. You may want to read some of the following articles as well as raise more interesting questions like this one.

Mind blown: the fast growing hierarchy for laymen — aka enormous numbers
Ackermann function
Higher-Order Recursion, How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking


Show that if Automata $A$ recognize language $L$, there also exists an automata $A′$ that recognize $Double(L)$ I don't know if this question should have better been on math.Stackexchange

Let be the operation $Double$ on the words on an $\Sigma$ alphabet which inserts after each character a copy of this character. Thus, $D(ab) = aabb$, $D(abaab) = aabbaaaabb$, etc... We had to prove that these regular expressions are closed by this operation and it was a sucess.

  We now have to prove this properties for automata. In other words, we have to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$.

  I shouldn't use equivalence between automatas and regular expressions

goal : I therefore deduce that I have to prove that autmomatas are closed by the Double operation.

the hypothese : is that it exists a language $L$ such taht it exists an automata $A$ which recognizes it.

proof attempt : $D(L)$ being a language, it must be a automata associated.

But:

has(have ?) every language(s?) an associated automata?
Isn't this proof too short or taking its goal has an hypothesis ?

Proof attempt n°2

Following Rick Decker's advises, here is the second attempt to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$ :

To prove it, we are goint to construct an automata $A'$ such that $A'=D(L)$.

The idea is to construct an input string of $w$ that we reads from left to right. After having read the entire string $w$, it checks whether the following char is the same. If it is the case we remain in the final state. Otherwise, we go to a transitional state and if the following char isn't exactly the same, we go to the bin state.

$Q=\{q_0, q_1, q_2, p\}$, $q_1,q_2$ are waiting states, $p$ is a bin state.

$\Sigma$ is the alphabet. For the example it is : $\{a,b\}$.

$\delta : Q × \Sigma → Q$ is a function, called the transition function,

$$\begin{array}{c|cc|c|c|}
& a & b\\
\hline
q_0 & q_2 & q_1\\
q_1 & p& q_0\\
q_2 & q_0&p\\
p & p & p\\
\hline
\end{array}$$

$q=q_0$.

$F=q_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.

You said you showed this result using regular expressions. Take the idea you used then and apply it to automata. You assume you're given an automaton $A$ for the language $L$. You need to construct an automaton $A'$ which accepts all and only the strings in $D(L)$.

Here's a hint to get you started: if you have a rule in $A$ of the form $\delta(p, a) = q$, meaning that in state $p$, seeing input $a$, you go to state $q$, how would you modify that rule so that from state $p$, seeing $a$ and $a$ again, will go to state $q$? Perhaps you might introduce another state along the way from $p$ to $q$?


A median of an AVL. How to take advantage of the AVL? Here is the source of my question.

  Given a self-balancing tree (AVL), code a method that returns the
  median.

  (Median: the numerical value separating the higher half of a data
  sample from the lower half. Example: if the series is

  2, 7, 4, 9, 1, 5, 8, 3, 6

  then the median is 5.)

I can offer the following solution:

Traverse the given tree, return the number of elements.
Traverse  n / 2 + 1 (if n is odd) the tree again applying an in-order tree walk. The value of the n / 2 + 1th element is the median.

But I can do it with a binary search tree, can't I?
Is there a better algorithm for an AVL?

If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $v$.

Suppose that the left subtree (if any) has $L$ nodes. If $k \leq L$ then we recurse to the left subtree. If $k = L+1$ then we return $v$. Otherwise we recurse to the right subtree, reducing $k$ by $L+1$.

The running time of this algorithm is linear in the height of the tree, which is $O(\log n)$.


Best practices for normalizing up training, validation, and test sets I was reading up on how to normalize my training, validation, and test sets for a neural network, when I read this snippet:

  An important point to make about the preprocessing is that any
  preprocessing statistics (e.g. the data mean) must only be computed on
  the training data, and then applied to the validation / test data.
  E.g. computing the mean and subtracting it from every image across the
  entire dataset and then splitting the data into train/val/test splits
  would be a mistake. Instead, the mean must be computed only over the
  training data and then subtracted equally from all splits
  (train/val/test).

(source: http://cs231n.github.io/neural-networks-2/)

Does this mean the following?

Split my training set T into training set T1 & validation set V1
Find the mean/var of T1, mean_T1, var_T1
Normalize T1, V1, and my testing set with mean_T1, var_T1.
Train & test accordingly...

Thanks...

Yes, that's what it means.  Basically, mean_T1 and var_T1 become part of the model that you're learning.  So, same as you'd apply machine learning to the training set to learn a model based on the training set, you'll compute the mean and variance based on the training set.


Find All permutation of String using Iteration How to find all permutation of a String in Iterative way ?

Code (Recursion) :

private void permute(String str, int l, int r)
{
    if (l == r)
        System.out.println(str);
    else
    {
        for (int i = l; i <= r; i++)
        {
            str = swap(str,l,i);
            permute(str, l+1, r);
            str = swap(str,l,i);
        }
    }
}

public String swap(String a, int i, int j)
{
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i] ;
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

Wikipedia describes several algorithms, including:

Heap's algorithm.
Steinhaus–Johnson–Trotter algorithm.


Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph? I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph.

My solution is to do a modification of breadth first search from the given node for $N$ iteration. Its time complexity is around $\theta(V+E)$. But the problem is $|V|$ & $|E|$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?

This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.

This problem is actually #P-hard wich is believed to be strictly harder than NP.

The version of the problem where you only look for the existence of such a path is called the longest path problem. A well-known problem in theory. It is fixed-parameter tractable when parameterized by the length of the path (check Parameterized Algorithms book by Cygan et al for description and methods).


Is this "superset existence" problem NP-complete? The "Superset Existence Problem":
Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets?
To me, this feels like it should be NP-complete (in $|S|$), since it seems intuitively related to covering problems and minimum $k$-union. But I'm not sure where to start with the reduction.
So: is this problem NP-complete?

The problem is NP complete.
It is trivially in $NP$ (a certificate is the collection of the $y$ selected subsets of $S$), and it is $NP$-hard since it is the decision version of the Maximum Coverage Problem.


Knapsack Problem with Vector Values I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being summed are vectors (and them sum is the Euclidean norm of the sum of the vectors). Formally, given a set of $m$ vectors $v \in \Re^{n}$, a set of non-negative weights $\alpha \in \Re_{0+}$, and a non-negative maximum Euclidean norm $W \in \Re_{0+}$,

$$Maximize: ||\sum_{i=1}^{m} v_{i}x_{i}||_{2}$$
$$S.T.:\sum_{i=1}^{m}\alpha_{i}x_{i}\leq W, x \in \{0, 1\}$$

What, if anything is known about the complexity of this problem? It seems like it should be NP-Hard at minimum (as a generalization of the 0-1 Knapsack Problem), but it is unclear to me whether the decision problem variant is NP-Complete.

Yes, the decision problem is NP-complete.  If $n=1$ it is exactly the knapsack problem, which is already known to be NP-complete.

Possibly related Given a set of 2D vectors, find the furthest reachable point.


Floating Point Systems - Rounding Error in Taylor series I have a question about  rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...).

This function works well for seemingly any positive value of x that i have tried, but when i try for instance -30, it does not give me anything even close to what exp(-30) gives me.

I am aware of how to solve this problem, but I'm more curious as to why this happens. Does it have something to do with the alternating + and - signs when summing the series? Thank you.

Yes, that's exactly why: it's due to floating-point roundoff error, due to the alternating signs.

Suppose you have $x=10^{100}$ and $y=10^{100}-1$, and you ask your computer to subtract $x-y$.  We know what the correct answer should be: it should be $1$.  However, when $x$ and $y$ are represented as floating-point numbers, you don't get $1$ as the answer.  Floating-point representation is not exact for large numbers, so $10^{100}$ will get rounded off to the nearest number that can be represented in the floating-point representation.  As a result, $x$ won't be exactly $10^{100}$; it'll be a bit larger or a bit smaller -- and while the relative error will be very small ($< 0.1\%$), the absolute error might be very large ($x$ might be $10^{100}+\delta$ where $\delta$ is in the billions or much larger).  The same is true for $y$.  Thus, when you subtract $x-y$, the result won't be exactly $1$; it could be off by an absolute error of billions or much more.  As a result, computing $x-y$ in floating-point arithmetic will give you answer that is wildly wrong.

In contrast, if you compute $x+y$ where $x=10^{100}$ and $y=10^{100}-1$, the answer will be reasonable.  It won't be exactly correct, but it will be very close to correct.

To put it another way: suppose you compute $x+y$ and $x-y$ where $x \approx y$ and $x,y$ are very large.  Then $x+y$ will be reasonably accurate, but $x-y$ will be wildly inaccurate.  In particular, suppose that the closest representable floating-point number to $x$ is $\tilde{x}$, and the closest representable floating-point number to $y$ is $\tilde{y}$.  We know that floating-point arithmetic has small relative error, so $\tilde{x} = x \times (1+\epsilon_x)$ where $\epsilon_x$ is small (say, $|\epsilon_x| \le 2^{-20}$), and $\tilde{y} = y \times (1+\epsilon_y)$ where $\epsilon_y$ is small.  Now

$$\tilde{x} - \tilde{y} = x - y + x \epsilon_x - y \epsilon_y \approx x-y + x \times (\epsilon_x - \epsilon_y),$$

so the absolute error could be as large as $x \times (\epsilon_x- \epsilon-y)$.  We know that $\epsilon_x - \epsilon_y$ will be no bigger than $2^{-19}$ or so, but if $x \approx 10^{100}$, their product will be enormous: the absolute error could be as large as $10^{100} \times 2^{-19}$, which is enormous.  Since the correct answer is $x-y \approx 0$,  the relative error will also be enormous.

In contrast,

$$\tilde{x} + \tilde{y} = x+y x \epsilon_x + y \epsilon_y \approx x+y + x \times (\epsilon_x + \epsilon_y),$$

and here $x \times (\epsilon_x + \epsilon_y)$ might be as large as $10^{100} \times 2^{-19}$ or so, which is enormous.  So, the absolute error in this case is also large.  However, the relative error is small: $10^{100} \times 2^{-19}$ is quite small compared to the correct answer, $x+y \approx 2 \times 10^{100}$.  In particular, the relative error will be on the order of $2^{-19}$ when computing $x+y$ using floating-point math.

So, that's why absolute signs cause problems but the same sign doesn't cause problems.

For further explanation, you might enjoy reading the following article, especially Section 1.4:

What Every Computer Scientist Should Know About Floating-Point Arithmetic.  David Goldberg.  ACM Computing Surveys, 23:1, March 1991.

Separately, one other thing to know about Taylor series approximations is to have a feeling for the range where they are likely to be accurate.  In practice, we always truncate the Taylor series after a finite number of terms -- the full Taylor series is infinite, so we can't sum the entire series; instead, we sum just the first $n$ terms, for some finite $n$.

If you truncate the Taylor series for some function $f(x)$ after $n$ terms, you get an approximation to $f(x)$.  How good an approximation is this?  There are various bounds on the error of this approximation.  One bound is

$$\text{error} \le {|x-a|^{n+1} \over (n+1)!} \times \max \{f^{(n+1)}(v) : a \le v \le x\},$$

where we're using the first $n$ terms of the Taylor series approximation around $a$, and where we evaluate this at $x$ for some $x\ge a$.  So, if you can upper-bound the value of the $n+1$-th derivative of $f(x)$, you can get a bound on how good an approximation the truncated Taylor series will be.  You can read more about this at https://en.wikipedia.org/wiki/Taylor_series#Approximation_and_convergence and http://norsemathology.org/wiki/index.php?title=Taylor_Series_as_Approximations and https://en.wikipedia.org/wiki/Taylor%27s_theorem#Example.

In general, when you use a Taylor series approximation centered around $a$, you usually want to choose $a$ to be near $x$: the closer it is to $x$, the more accurate the approximation will be.  Also, the more terms in your sum, the more accurate the approximation will be.

Once you have an upper-bound for the quality of the Taylor series approximation, you can now figure out how many terms you need to sum.  Note that this analysis assumes infinite-precision numbers and ignores the issues due to floating-point round-off.  So, to get an accurate answer, you need to ensure two things: (a) pick a Taylor series approximation with enough accuracy that it would give a good answer if you used infinite-precision numbers, and (b) you need to account for round-off error, to ensure that when you do the calculation with floating-point numbers you get a result that is close enough to what you would have gotten with infinite-precision math.


How to prove that a grammar is unambiguous? My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } S$$

and make this to an unambiguous grammar, I think its correct:

$ S → S_1 ∣ S_2 $
$S_1
→ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_1$
$S_2
→ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_2
∣ statement$

I know that a unambiguous grammar has one parse tree for every term.

There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:

Prove $L \subseteq \mathcal{L}(G)$.
Prove $[z^n]S_G(z) = |L_n|$.

The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.

The second step shows that $G$ has as many syntax trees for words of length $n$ as $L$ has words of length $n$ -- with 1. this implies unambiguity. It uses the structure function of $G$ which goes back to Chomsky and Schützenberger [1], namely

$\qquad \displaystyle S_G(z) = \sum_{n=0}^\infty t_nz^n$

with $t_n = [z^n]S_G(z)$ the number of syntax trees $G$ has for words of length $n$. Of course you need to have $|L_n|$ for this to work.

The nice thing is that $S_G$ is (usually) easy to obtain for context-free languages, although finding a closed form for $t_n$ can be difficult. Transform $G$ into an equation system of functions with one variable per nonterminal:

$\qquad \displaystyle \left[ A(z) = \sum\limits_{(A, a_0 \dots a_k) \in \delta} \
                \prod\limits_{i=0}^{k} \
                \tau(a_i)\
                : A \in N \right] \text{ with } \tau(a) = \begin{cases}
                                                            a(z) &, a \in N \\
                                                            z    &, a \in T \\
                                                          \end{cases}.$

This may look daunting but is really only a syntactical transformation as will become clear in the example. The idea is that generated terminal symbols are counted in the exponent of $z$ and because the system has the same form as $G$, $z^n$ occurs as often in the sum as $n$ terminals can be generated by $G$. Check Kuich [2] for details.

Solving this equation system (computer algebra!) yields $S(z) = S_G(z)$; now you "only" have to pull the coefficient (in closed, general form). The TCS Cheat Sheet and computer algebra can often do so.

Example

Consider the simple grammar $G$ with rules

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$.

It is clear that $\mathcal{L}(G) = \{ww^R \mid w \in \{a,b\}^*\}$ (step 1, proof by induction). There are $2^{\frac{n}{2}}$ palindromes of length $n$ if $n$ is even, $0$ otherwise.

Setting up the equation system yields

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

whose solution is

$\qquad \displaystyle S_G(z) = \frac{1}{1-2z^2}$.

The coefficients of $S_G$ coincide with the numbers of palindromes, so $G$ is unambiguous.

The Algebraic Theory of Context-Free Languages by Chomsky, Schützenberger (1963)
On the entropy of context-free languages by Kuich (1970)


Are "of the order of n" and "Big O" the same thing? I am learning from the MIT course Introduction to Algorithms.

The professor says:

  Now, remember $\Theta(n)$ is essentially something
      that says "of the order of $n$".

What does "of the order of $n$" mean? Are "of the order of $n$" and "Big O" the same thing?

Please provide the name of any widely recognized textbook that contains detailed explanation about this.

"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g., $10n \in O(n)$, despite $10n$ being 10 times as larger as $n$). They can hardly be considered the same things. What the lecturer is trying to do here is supposedly give you some (hand-wavy) intuition as to how Big O notation works, but that should not replace you actually sitting down and learning the precise definitions.

As for your request regarding further reading on Big O notation, (in addition to the linked Wikipedia article) I suggest you take a look at our reference question.

An addendum: After listening to the video again, you can make out the lecturer say "of the order of $n$". This is the British English version of American English "on the order of" and carries the same meaning.


If $f(n)$ is $O(g(n))$ is it also $O(g(n-d))$? When trying to prove that a recurrence $g(n)$ satisfies $g(n) = O(f(n))$, we sometimes are not able to find a valid $C$ to show the upper bound, so we try to prove it is $O(f(n-d))$ for some constant $d$ instead.

If we are able to prove that $g(n) = O(f(n-d)$, does this mean that it is also $O(f(n))$?
If so, does this go the other way too? That is, if $g(n)=O(f(n-d))$ for some $d$, then $g(n) = O(f(n))$ as well?

edit 1:
Here a valid $C$ means, $C$ such that $f(n) <= C*g(n)$ for all $n > n0$ for some $n0$

The answer to your first question (whether $f(n) = O(g(n))$ implies $f(n) = O(g(n-d))$) depends on the function $g$: indeed, what you want holds iff $g(n) = O(g(n-d))$. This is a relation that holds for many functions, for example polynomials and exponentials, but not for the function $g(n) = 2^{2^n}$.

As for your second question, if $f$ is monotone (increasing) then $f(n-d) \leq f(n)$, and in particular $f(n-d) = O(f(n))$. The same holds if $f(n) = \Theta(h(n))$ for some monotone $h$. For example, if $f$ is a degree $a$ polynomial then $f = \Theta(n^a)$, and so $f(n-d) = O(f(n))$, since $n^a$ is monotone.


Is there an algorithm to compute the shortest Hamiltonian path in an directed graph from one point to another in polynomial time? I am wondering whether the Shortest Hamiltonian Path (SHP) problem is NP-Complete, because I couldn't find a way of solving it in a polynominal time. if it is NP_Complete, it will be so kind of you to give me the proof or the relevent papers,thanks a lot

the problem explanation: Given a directed,weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u.
by the way,the graph must exit a hamiltonian path from v to u.

Here's a small hint.

Let $G$ be a directed graph with unit weights, and $u$ and $v$ be two vertices.  Suppose that I could solve SHP in polynomial time, say, $O(n^c)$.

Now, say that I would like to solve Hamiltonian Path on a directed graph.  Let me spend $O(n^2)$ time to "guess" your vertices $u$ and $v$, and for each of them run your algorithm for SHP.  Then, I would in $O(n^{c+2})$ time have either found a Hamiltonian path in $G$, or conclude that $G$ is not Hamiltonian.

That would mean that P = NP.

Now, this doesn't prove that your problem in NP-complete.  For that, you need to come up with a reduction.  But it does tell you that you should probably not spend too much time looking for a polynomial time algorithm.


Strict polynomial hierarchy and reduction The following exercise gives me headaches:

  Show: If the polynomial hierarchy is strict (i.e. $\forall k \in \mathbb{N}. \Sigma_k \neq \Sigma_{k+1}$), then there is no $\text{PH}$-complete problem for polynomial-time reductions (i.e. there is no problem $\text{P} \in \text{PH}$ such that each problem in $\text{PH}$ can be reduced to $\text{P}$ through a function $f \in \text{FP}$).

The exercise describes in detail what has to be shown, but my issue is that I don't know how to show this. Can somebody please help me?

$\newcommand{\PH}{\mathsf{PH}}$To expand the comments:

Suppose there did exist a $\PH$-Complete language $L \in \Sigma_i$ for some $i$. By definition of completeness $L' \leq L$ for all $L' \in \PH$. Therefore there exists some language $L' \in \Sigma_{i+1}$ that reduces to $L$. This is a contradiction with the strictness assumption. Indeed, we conclude that no such $\PH$-Complete language exists.


Simplifying Boolean Expression I am designing a 4-bit comparator with a look ahead unit using a bit slice approach. I have to break the propagation of the Logical expressions for (A<B)i and (A>B)i. The main question is, could I use the following to simplify the boolean expressions.. The i is a subscript meaning the ith bit. The i-1 is a subscript meaning the bit before the ith bit.

(A<B)i = ~Ai*Bi + ~Ai*(A<B)i-1 + Bi*(A<B)i-1

Could I Take ~Ai common from the first two expressions leaving me with

~Ai*(Bi + (A<B)i-1) + Bi(A<B)i-1

Let's call  Bi + (A<B)i-1) = Q

And let's call ~Ai = P

I'm left with P*Q + Q

Using the boolean law that Q + Q*P = Q

Can I simplify the expression to just

(A<B)i = Bi + (A<B)i-1

No, you cannot simplify to $(A<B)_i = B_i + (A<B)_{i-1}$, Take for example $A=11$ and $B = 10$.

Then $(A<B)_2$ = False, $B_2$ = True, and $(A<B)_1$ = False. If you substitute the values above then the equation is not satisfied. The original equation(s) is correct.

$(A<B)_i = \neg A_i B_i + (\neg A_i+B_i)(A<B)_{i-1}$
$(A<B)_1 = \neg A_1 B_1$

In your derivation of simpler formula, $B_i + (A<B)_{i-1} = Q$ but you are incorrectly substituting $B_i (A<B)_{i-1} = Q$ in rightmost term.


Algorithms - Solving recurrence-relations/Bounds? I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige.

Suppose we have this recurrence:

$$    T(n) = 2T(n/2) + \log n$$

How would we figure out running time for this, and specifically, how would we PROVE the upper and lower bounds (ideally as tight as possible)?

I tried working through my homework with the help of a few YouTube videos, but I don't seem to be following it. In giving an explanation, please try and be careful to explain why something is a certain time, as I haven't really gotten the hang of intuiting that yet.

I have some working knowledge of induction and calculus, but it seems like I'm missing a big chunk of context somewhere and I really need to get up to speed. Thank you for any assistance.

First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence.

Second, your recurrence only possibly makes sense for powers of 2, and even then, it needs a base case. I'll assume that $T(1) = C$.

You can use the master theorem to solve your recurrence, but you can also do it directly. First you expand it (for simplicity, I'm assuming the base of the logarithm is 2):
$$
\begin{align*}
T(2^k) &= k + 2T(2^{k-1}) \\ &=
k + 2(k-1) + 4T(2^{k-2}) \\ &=
k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ &=
(1+2+\cdots+2^{k-1})+(1+2+\cdots+2^{k-2})+\cdots+(1) + 2^k C \\ &=
(2^k-1)+(2^{k-1}-1)+\cdots+(2-1)+(1-1) + 2^kC \\ &=
(2^k+\cdots+1)-(k+1) + 2^kC \\ &=
2^{k+1}-k-2 + 2^kC.
\end{align*}
$$
If you want to be very pedantic, you can prove this by induction. In terms of $n=2^k$, this reads
$$
T(n) = (2+C)n-\log n - 2 \sim (2+C) n.
$$
In particular, $T(n) = \Theta(n)$. You could also get this conclusion from case 1 of the master theorem.


Finding minimum possible cost of road network between cities with distance from capital condition I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E).
Characteristics of the graph:

Each city is connected to the rest of the graph

Each city has an index value where the index is equal to minimum number of roads you need to use to get to the capital from this city. Capital has index of 0. The cities connected right to the capital will have index of 1 and so on.

Some of the roads will be selected to be changed into highways, creating some sort of network.

I would like to find minimum possible cost of said network based on these requirements:

It is possible to travel from any city to capital
When travelling from any city to capital, the sequence of indexes of visited cities during travel is non-increasing
The highway network has to be minimum possible

What I did so far:
I understood this does require MST solution and so I am using Prim's algorithm, but that is solving only part of the problem (req. 1. and possibly 3.) and I need to add something to my MST algorithm to ensure the 2. requirement is fulfilled, and that is my only problem.
I think starting from the capital city might be the first step (and I do so in Prim's), but how to deal with the indexation based on actual road distance from capital city?
Examples:
In the picture 1 below, fig. a) shows incorrect solution using MST algorithm only – one of the possible MST with weight of 35.
Opposed to this, fig. b) shows one of the possible correct solutions with paths with weight of 120.

The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree.
Let's call $T$ the solution for the input graph $G$. Let's also call $T_i$ the solution for the problem $G_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I will use the term "range index" to prevent confusion with the vertex indexing used for Prim's algorithm).
Trivially $T_0$ and $G_0$ contain only the capital. Now what about $G_1$ ?
The cities having a range index of 1 cannot use largest index cities to connect captial. Thus $T_1$, which is by the way MST of $G_1$, is a subgraph of $T$.
$T_{i+1}$ is built the same way using $T_i$ and $G_{i+1}$. The edges of $T_i$ are kept and only the new edges to connect the cities having range index $i+1$ are added using any MST algorithm.


Proving the algorithm that orders an array according to the specified positions I have the following task:

  Given an array a holding positions and array b holding values,
  order the elements in the array b according to the positions in the array a. For the
  input:

a = [3, 0, 1, 2];
b = ['a', 'b', 'c', 'd'];

  the output should be

[ 'b', 'c', 'd', 'a' ]

I have written a simple algorithm which simply an item into the specified position by swapping:

// a.lenght -1 since the last element will end up in the correct vacant position
for (let i = 0; i < a.length - 1; i++) {
    const position = a[i];
    swap(b, i, position);
}

Although I've tested it and it seems to produce correct results, I can't figure how to prove it works correctly. Can anyone please help with reasoning?

You can't prove a false statement to be true :P

Consider this example:

a = [1, 2, 0]
b = ['a', 'b', 'c']

Output should be:

b = ['c', 'a', 'b' ]

But your algorithm will output:

b = ['c', 'b', 'a']

This because when you swap an element in its "final" position a[i] it's possibile that in one of the next loops that element will be swapped again.

To solve this problem think about swapping a[ ] elements too. :)


Is the language $\{a^n b^n c^i | i \leq n\}$ context free? I'm trying to apply the CFL pumping lemma.
And, I've already tried words $a^pb^p$ and $a^pb^pc^p$.
Not sure where to go from here.

Classical pumping works. According to the pumping lemma we can find a segmentation $uvwxy$ such that $uv^iwx^iy$ is in the language for all $i$.

Start with your own suggestion $a^pb^pc^p $.

Three easy steps.

Each of the "pumping segments" $v$, $x$ can only be within the boundaries of one the "letter segments" $a^p$, $b^p$, $c^p$.
It is not possible to have one of $v$ or $x$ to be in the $a^p$ segment without the other being inside the $b^p$ segment. And the other way around. In that case pump down ($i=0$).
Final possibility both $v$ and $x$ are in $c^p$. Pump up.


Weakest reduction for 3-$\mathrm{SAT}$ Having read all these posts

Constant-depth threshold circuit for $\mathrm{PP}$

Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

I wonder about the weakest possible reduction for 3-$\mathrm{SAT}$ to be complete for $\mathrm{NP}$?

Having read all your answers to my questions, I come to the ultimately weakest reduction for 3-$\mathrm{SAT}$

The weakest reduction is $\mathrm{NC}_0^0$. This reduction does not use even $\mathrm{NOT}$  gate. Absolutely, almost nothing at all.

Consider the very first part of the very first row in your answer here. As you mentioned there, this only needs some indexing work of the $\mathrm{DLogTime}$-constructor. It turns out that all that is needed to be done is to put $\lnot$ symbol to the soon-to-be-reduced-to formula by copying the actual input bits themselves.

In particular, consider the 10th cell $c_{10}$ of the first row, this cell is equal to $x_{10}$ i.e. the 10th bit of the actual input.

Depending on whether $x_{10}$ is 0 or 1, the corresponding clause will be:

$$ \lnot c_{10} \lor \lnot c_{10} \lor \lnot c_{10} $$

or

$$ c_{10} \lor c_{10} \lor c_{10} $$

All the $c_{10}$'s are hard-coded similarly as the rest of the constructed constant-depth circuit. The $\lnot$ or nothing (actually a dummy symbol in the soon-to-be-reduced-to formula) is copied from the actual input bit $x_{10}$.

So, the weakest reduction is $\mathrm{NC}_0^0$. It copies the input bits to some output gates of the constructed 0-depth circuit. All the other output gates of the constructed 0-depth circuit are constantly hard-coded.


Succinct bounded-sum array with $O(1)$ access Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$.

Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written in $O(1)$ time), and that $M=n^{O(1)}$.

A standard implementation could allocate $\lceil \log_2 M\rceil$ bits per cell, resulting in a $n\cdot \lceil \log_2 M\rceil$ bits array.

Arithmetic encoding allows us to encode the array using
$$\left\lceil\log_2{n + M \choose M}\right\rceil\approx n\log\left(\frac{M}{n}\right)$$

bits, but does not allow $O(1)$ time operations.

  Is there a succinct encoding (say, of size
  $n\log\left(\frac{M}{n}\right)+O(n)$) that allows $O(1)$ time
  operations?

The required operations are standard array operations -- retrieving and setting the value of $A[i]$ for any $i\in[n]$.

Raman, Raman, and Rao is a standard reference for rank/select in O(1) time.  This solves your problem for the special case of a static array, i.e., you can retrieve $A[i]$ in $O(1)$ time, but not update $A$: see the third bullet item in their abstract.  The rank operation can be used to determine membership, and the select operation retrieves the $i$th element of the array.  Their data structure requires $o(n)+O(\lg \lg m)$ extra space beyond the minimum.

The conclusion of their paper also mentions a lower bound if you want to support insert, delete, rank, and select.  I don't know if that's applicable here.


what's analogy learning algorithm ? differences from induction learning algorithm? I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?

In a nutshell, (statistical) machine learning is a certain approach to artificial intelligence. Traditional artificial intelligence incorporates hard-coded rules which are written by humans. Statistical machine learning, in contrast, has the computer learning the rules by itself using statistical means.

There are several paradigms used for statistical machine learning, such as support vector machines, artificial neural networks, and genetic algorithms. Recently a certain type of artificial neural networks, deep neural networks, has come to the fore due to unprecedented performance. Machine learning using deep neural networks is known as deep learning.


Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1 I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak:

  [Q 4.1]
  Prove the existence of a universal TM for space bounded computation (analogously to the deterministic universal TM of Theorem 1.9).

That is, prove that there exists a Turing Machine $SU$ such that for every string $\alpha$ and input $x$, if the TM $M_\alpha$ -- the TM represented by $\alpha$ -- halts on $x$ before using $t$ cells of its work tape, then $SU(\alpha, t, x) = M_\alpha(x)$ and moreover, $SU$ uses at most $C\cdot t$ cells of its work tape, where $C$ is a constant depending only on $M_\alpha$.

After checking theorem 1.9 and the universal TM with time bound, I see that the construct $SU(\alpha, t, x)$ means that the Turing machine SU stops after $t$ steps. However if this is the case, then it means that we can create a Turing Machine equivalent to $M_\alpha$ such that the new Turing Machine stops in $t$ steps where $t$ is the "space" used in the original.

However, this seems a dubious interchange of space and time. If on the other hand, $t$ actually meant that the second machine stops within $t$ space, too, then the second part does not make sense any more because it says $SU$ uses $Ct$ cells, which is not $t$.

So my question is how do I interpret this? Is the first interpretation really possible?

I do not understand what you are trying to say after "--", but here is what you need to do:

Hopefully you understand the idea of turing machine encoding: i.e. you can assign a unique identifier (i.e. "label") $\alpha$ to each turing machine. So by $M_\alpha$ we mean the Turing machine labeled by $\alpha$. So you need to design a single turing machine $SU$ which takes three inputs $\alpha$, $t$ and $x$ ($\alpha$ is a turing machine label, $t$ is a space bound, and $x$ is an input string) and:

if $M_\alpha$ uses more than $t$ bits of workspace on input $x$ before it halts, then we have no requirement for $SU$
if $M_\alpha$ uses at most $t$ bits of workspace on input $x$ we have two requirements for $SU$:

$SU$ uses at most $Ct$ units of workspace where $C$ is a function of $\alpha$ but not $t$ or $x$
$SU$ outputs $M_\alpha(x)$

The idea is that for any machine and any input, $SU$ can simulate that machine while using only slightly more space than the original machine. Note that $t$ is a bound on the space that $M_\alpha$ uses, not the space that $SU$ uses. $SU$ cannot be exactly as space efficient as the original machine because simulation requires some overhead, but the point is that the overhead is small as $C$ is fixed for every $\alpha$, no matter how large $x$ is in size.

Theorem 1.9. also has some overhead: a machine which stops in $T$ time steps is simulated in $CT\log T$ time steps where $C$ is again some constant independent of $T$ or of the input string.


Can a Turing machine decide the language $L_\emptyset$ of machines with empty language? Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?

It seems that the same technique used to show that $\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$ should work here as well.

By marking, you probably mean reachability analysis - looking for a path from the initial state to an accepting state. Indeed, the language of a DFA is empty iff there is no such path.

Let's start with an example as to why this fails in TMs. Consider a TM that, in $q_0$, ignores it's input, but writes $a$ on it's tape, moves the head right and goes to state $q_1$, then in $q_1$ it again ignores the input, writes $a$, moves the head left and goes to $q_2$. In $q_2$, if it reads $a$, then it writes $a$, moves the head right and goes back to $q_1$.

That is, the machine just writes $a$ and alternates between two states ($q_1$ and $q_2$) and always has two adjacent $a$'s on the tape.

We now add a transition from $q_2$ that when reading $b$ goes to an accepting state and halts.

The language of this machine is empty. Indeed, the run always gets stuck in the $q_1-q_2$ loop, and will never get to the accepting state. Yet, there is a state-path to an accepting state. So what went wrong?

Well, intuitively, the ``state'' of a TM is not informative enough to describe the continuation of the run. In order to have all the information, you need the configuration of the TM, which includes the state, the position of the head, and the contents of the tape. If you find a configuration-path (which is called a run) to an accepting configuration, then indeed the language is non-empty, and it is an iff condition.

The problem with using reachability analysis on the configuration graph, is that it may be infinite. This is why deciding language emptiness is undecidable.

This is also why language non-emptiness is recognizable - you can perform a BFS on the infinite configuration graph. If there is a path to an accepting state, you will find it eventually. If there isn't, however, then you may get stuck in an infinite search.


Why is the word "calculus" used to describe systems of logic and computation? Why is the word "calculus" used in this context?

The reason I ask is because these usages of "calculus" seem unrelated to the far more popular use of "calculus" in "differential calculus" and "integral calculus" to which something like λ-calculus seems only very distantly related. This word choice seems very misleading yet very popular among many authors. Why?

The word calculus comes from the Latin word for limestone, because limestone pebbles were used for counting; you may have a renal calculus: a kidney stone$^1$.

In mathematics, the word is used to describe any system in which symbolic expressions are manipulated by fixed rules$^1$, so we may speak of tensor calculus, vector calculus, predicate calculus, $\lambda$-calculus and integral and differential calculus$^2$. The latter two are related to the former in the sense that both are sets of rules for manipulating expressions. Running a Google Books ngram search on these words, approximately 1890 was the first year in which both "vector calculus" and "tensor calculus" were mentioned, and they have been in frequent use ever since.$^3$

The reason that to you, these systems seem to be using the wrong meaning of calculus is probably that you grew up associating calculus with differentiating and integrating real-valued functions, but this is a bias.

References

[1] Wiktionary page for Calculus

[2] Wikipedia Disambiguation page for Calculus

[3] Google Books search for integral, differential, vector, tensor calculus


How can I prove the following problem is NP complete? The problem:
I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\{s_{i} ,s_{j}\} \in \mathbb{N}$. Also the pairs are only for $\displaystyle i\neq j$.
I have two numbers: $ $$\displaystyle b\in \mathbb{N}$, $\displaystyle p\in \mathbb{N}$.
The problem is to check wether it exist a combination of pairs such that:
$\displaystyle c_{1} +c_{2} +\dotsc +c_{m} \leqslant b$ and $\displaystyle g_{1} +g_{2} +\dotsc +g_{m} \geqslant p$. Where of course $\displaystyle c_{i} ,g_{i}$ are cost and gain of a used pair $s_i$.
To show it is NP-complete I have to show a Karp reduction.

There are some problems we've studies and so that I can use:
Clique, Composite, SAT - Satisfiability problem, 3SAT, CSAT, IS - Independent Set, VC - Vertex, Cover, DHC - Directed Hamilton Cycle, HC - Hamilton Cycle, DS - Dominating Set, SSS - Subset, Set, 3COL, Partition, Bin-Packing.
Since it's talking about a sum I thought of using Subset-sum. If I set $\displaystyle p=b=k$, and I set $\displaystyle c_{i} =g_{i}$ for each $\displaystyle i$, then it really is just a sum question, to find a combination of elements of sum $\displaystyle k$.
But what it's complicating it for me is that if I have $\displaystyle n$ elements, I will have $\displaystyle \frac{n^{2} -n}{2}$ pairs, and so these many different costs. How can I rewrite the $\displaystyle n$ elements of partition, into some $\displaystyle k$ elements here such that there are $\displaystyle \frac{k^{2} -k}{2} =n$ pairs?
I've thought maybe I can only assign the cost to the first $\displaystyle n$ elements, and then all the rest to $\displaystyle 0$, but then cost and gain must be natural numbers.
Any advice?

I think there is an easy reduction from Knapsack.

Knapsack:

Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$
Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$

Now given an input of knapsack, let's construct an input of your problem: add a $n+1$-th element, and consider:

$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $c\{i, j\} = \infty$  and $c\{i, n+1\} = w_i$
$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $g\{i, j\} = 0$  and $g\{i, n+1\} = v_i$
set $b = W$ and $p = V$

Then this instance has a solution of your problem if and only if the input of knapsack has a solution. Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem.


Multiplication function BDD size lower bounds Randal Bryant developed an exponential size lower bound for any BDD encoding the middle bit output of the multiplication function, regardless of variable permutation.

But at the same time the multiplication function is decidable in logarithmic space. Of course related to P versus NP, the lower bounds complexity of its inverse function is currently unknown. Having an efficient BDD encoding for multiplication also provides a mechanism for efficient factoring, so I understand that this would seem implausible.

However, if a function belongs to L (such as multiplication or so I think), it most certainly belongs to L/Poly which is (to my understanding) the class of polynomial sized BDDs.

From what I can discern, Bryant's proof relies on communication complexity rather than crypto-hardness assumptions or building upon mainstream conjecture. So what's going on here that seems a blatant contradiction in known lower bounds?

For some related background see this post:
https://cstheory.stackexchange.com/questions/3462/most-significant-bit-of-integer-multiplication-and-binary-decision-diagrams

I think the resolution to the paradox comes from looking more carefully what is meant when we say that multiplication can be performed in logarithmic space, and looking more carefully at what we mean by a BDD.

Suppose we want to multiply two $n$-bit numbers $a,b$, and suppose the two numbers $a,b$ are stored in read-only memory.  Then we can calculate any desired bit of the product using only $O(\lg n)$ additional bits of space.  However, this fundamentally requires us to have (read-only) access to the numbers being multiplied.

(Take a look at the formula in Wikipedia for $r_i$: $r_i$ depends on $a$, $b$, and $c_{i-1}$.  The carry $c_{i-1}$ needs only $O(\lg n)$ bits of space to store.  However, just storing the carry alone is not enough.  We also need to have the numbers $a,b$ stored, and that requires $\Theta(n)$ bits of storage.)

In short, multiplying two numbers takes $\Theta(n)$ bits (read-only) for the numbers being multiplied and $\Theta(\lg n)$ bits (read-write) of additional storage.  This does prove that multiplication is in $L$.  However, it doesn't prove that there is a polynomial-size BDD for multiplication.

First, let's understand what we mean by BDD.  There are many types of BDD, but the most relevant one here is the notion of a ROBDD (read-once binary decision diagram).  A ROBDD is allowed to read each bit of the input only once.  Normally, BDD means a ROBDD: for a reference, see, e.g., the Wikipedia article on BDDs, which writes "In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD".  Moreover, the lower bound for the size of a BDD for multiplication is actually a lower bound on the size of a ROBDD for multiplication.  Therefore, in this answer I'll assume BDD means ROBDD.

Now, here's why the above algorithm doesn't prove there is a polynomial-size (RO)BDD for multiplication.  Given an algorithm with space complexity $s$ and time complexity $t$, you can construct a BDD with something like $2^s \times t$ nodes (but here $s$ must include all input bits that might be read more than once, as well as all additional storage).  This means that the number of nodes in a BDD could be as much as exponential in $s$.  In the case of multiplication, we have $s = \Theta(n+\lg n) = \Theta(n)$, so from the existence of the multiplication algorithm above, all we can conclude is that the size of the BDD could be (at most) exponential in $n$.  This isn't enough to show that there exists a polynomial-size BDD.

What about L vs L/poly vs BDDs?  I don't think it's true that just because a problem is in L/poly, that means it has a polynomial-size BDD.

Roughly speaking (ignoring uniformity vs non-uniformity), a problem is in L or L/poly if there is an algorithm that has read-only access to the inputs and uses only $O(\lg n)$ additional bits of (read-write) storage.  If we also knew that this algorithm reads each bit of its input only once, then that would imply that there is a polynomial-size (RO)BDD for the problem.  But if the algorithm scans back and forth over the input bits, reading them many times, then I don't think there necessarily exists a polynomial-sized (RO)BDD for the problem.  At least, I don't know of any result that implies that.  I could be missing something.

I know Wikipedia says that L/poly is "a complexity class that captures the complexity of problems with polynomially sized BDDs".  I am not sure that is exactly correct.


Euclidean geometry theorem proving complexity Euclidean geometry is complete, so the problem of determining whether a statement $A$ is provable is computable. Do we know its time complexity?

It is common to prove the decidability of first-order Euclidean geometry by encoding the language of Euclidean geometry into the language of real closed fields and then showing that the latter is decidable. A singly-exponential space upper bound on deciding the first-order theory of real closed fields was proven in Ben-Or, Kozen, and Reif (1986). This implies a doubly-exponential time upper bound.
I believe this is the best known complexity for the decision problem for general first-order sentences in the language of real closed fields. However, I am not sure whether deciding real closed fields is equivalent (bidirectionally) to deciding Euclidean geometry, since a typical encoding of (say) the language of Tarski's axioms into the language of real closed fields only uses a small subset of the possible polynomials. So maybe first-order Euclidean geometry can be decided with lower complexity than this. It is at least PSPACE-hard, since TQBF is easily encoded into first-order Euclidean geometry.


Is my grammar correct for this context-free language? $\{a^nb^2a^n \mid n \ge0\}$

I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between.

I came up with the following grammar, but I think it accepts strings that it should not such as:
$abb, bba$, etc.

$$\begin{align}
S&\rightarrow X\\
X&\rightarrow XbbX \mid \epsilon\\
A&\rightarrow aA \mid \epsilon
\end{align}$$

In dealing with CFGs, it's often useful to work from the inside out. Clearly
$$
S\rightarrow aSa
$$
will generate all strings of the form $a^nSa^n$, for $n\ge 0$. Then all you have to do is allow the possibility that $S$ will also eventually generate $bb$, which we can do by the production $S\rightarrow bb$, giving the grammar
$$
S\rightarrow aSa\mid bb
$$
or, if you wanted to be explicit about the $bb$ central part, you could write
$$\begin{align}
S&\rightarrow aSa \mid T\\
T&\rightarrow bb
\end{align}$$
The problem with your grammar is that it can't guarantee that there will be the same number of $a$s on each end of a generated string.


The equational theory of regular languages has no finite set of axioms for general alphabets According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms.

  Why does this imply that it has no finite set of axioms over an arbitrary alphabet?

Suppose I have a finite set of axioms for the equational theory of an alphabet with more than one letter, how would this give a finite set of axioms for the single letter case? I mean in the single letter case we have additional equations which did not hold in the arbitrary case, for examle $AB = BA$ for two languages $A,B$, and therefore which could not be derived from the axioms, hence these axioms do not axiomatize the single letter case.

Some clarification as asked for in the comments: Given a fixed alphabet $\Sigma$ and a set of variables $X = \{A,B,C,\ldots\}$, the terms are inductively defined:

1) Every $a \in \Sigma$ is a term,

2) Every variable $X$ is a term,

3) If $s,t$ are terms, then $s + t, s\cdot t, t^{\ast}$ are terms.

The interpretation of the regular sets $\mathcal{Reg}(\Sigma)\subseteq \mathcal P(\Sigma^{\ast})$ is as usual. As written in the comments, as set of terms $\Gamma$ axiomises $\mathcal{Reg}(\Sigma)$, the regular languages over a given alphabet $\Sigma$, if
$$
 \Gamma \vdash t_1 = t_2 \mbox{ iff } \mathcal{Reg}(\Sigma) \models t_1 = t_2.
$$
Where $t_1, t_2$ are terms with alphabet letters from $\Sigma$, and variables are interpreted as universally quantified. The only rule of interference being substitution, that I mean by equational logic.

For each $k > 0$, the equation
$$
 A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1})
$$
holds for regular languages over every alphabet, hence if for some alphabet we have a finite axiomatization, this equation is provable from it. Now as shown in A. Ginsburg, Algebraic Theory of Automata, the following infinite system of axioms is complete for unary regular languages.
\begin{align*}
 A + B & = B + A \\
 A + (B + C) & = (A + B) + C \\
 A + A & = A \\
 A + \emptyset & = A \\
 AB &= BA \\
 (AB)C & = A(BC) \\
 A1 & = A \\
 A \emptyset & = \emptyset \\
 (A+B)C & = AC + BC \\
 1^{\ast} & = 1, \emptyset^{\ast} = 1 \\
 (AB^{\ast})^{\ast} & = 1 + AA^{\ast}B^{\ast} \\
 (A + B)^{\ast} & = A^{\ast} B^{\ast} \\
  A^{\ast} & = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}), \quad k > 0
\end{align*}
So we get a finite axiomatisation for unary languages, if we take but the last family of axioms, and all axioms from the finite axiom system for some alphabet that prove
$$
 A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1})
$$
for each $k > 0$. Then all of the above equations are derivable by this finite axiom system, and as the above one is complete, this finite axiom system would be complete, which is not possible. Hence there is no finite system of axioms for any alphabet.


Generalized sorting algorithm on partially ordered set generated by a relation Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). Recall:

reflexive: We always have $x\leq x$.

transitive: If $x\leq y$ and $y\leq z$ then also $x\leq z$.

anti-symmetric: If $x\leq y$ and $y\leq x$ then $x=y$.

I'm looking for an efficient algorithm that decides whether $\preceq$ extends to a partial order and if yes, returns one or one with uniform probability or all possible orderings of $X$ which respect the partial order.

This naturally decomposes into two subtasks (not claiming that the best algorithm decomposes this way):

Decision whether $\preceq$ extends to $\leq$ or, in other words, extending by transitivity does not violate anti-symmetry. If it does, describing the partial order $\leq$.
Finding the possible orderings.

The second points is related this question.

You can efficiently test whether $\preceq$ extends to a partial order using topological sorting.  Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$.  Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically sorting the graph).

Moreover, we can describe a minimal partial order $\le$ that is consistent with $\preceq$, as follows.  Compute the transitive closure of this graph. Now declare $x \le y$ iff there's an edge $x \to y$ in the transitive closure, or $x=y$.  (Equivalently, declare $x \le y$ iff $y$ is reachable from $x$ in zero or more steps, in the graph derived from $\preceq$.)  By construction, the relation $\le$ defined in this way will automatically be reflexive and transitive; if the original graph has no cycles, then it is easy to prove that the relation $\le$ will be anti-symmetric as well and thus will be a partial order.


Detect if a sentence is in passive voice Given an English sentence, I am looking for a programmatic way to tell whether the sentence is written in passive voice.

Currently, I just check if there is a was or were inside the sentence. If yes, then the function will say that the sentence is in passive voice (I do no not know even if this is true).  Is there a better approach?

I just want to make a simple detector for passive voice, I do not care much for accuracy and efficiency. Here what I ended up with:

// http://english.stackexchange.com/questions/472/how-can-i-reliably-and-accurately-identify-the-passive-voice-in-writing-or-speec

// forms of be, have and get
int auxilary_verb(char* str) {
    if(strstr(str, "be ") || strstr(str, "been ") || strstr(str, "being ") ||
            strstr(str, "have ") || strstr(str, "had ") || strstr(str, "was ") || strstr(str, "were ")
            || strstr(str, "wasn") || strstr(str, "weren") || strstr(str, "got ") || strstr(str, "get ")
            || strstr(str, "getting ")) {
        return 1;
    } else {
        return 0;
    }
}

// past participles of the verbs here http://web2.uvcs.uvic.ca/elc/sample/beginner/gs/gs_10.htm
int past_participle_transitive_verb(char* str) {
    if(strstr(str, "brought ") || strstr(str, "cost ") || strstr(str, "given ") || strstr(str, "lent ")
            || strstr(str, "offered ") || strstr(str, "passed ") || strstr(str, "played ") || strstr(str, "read ")
            || strstr(str, "sent ") || strstr(str, "sung ") || strstr(str, "sent ") || strstr(str, "taught ") || strstr(str, "written ")
            || strstr(str, "bought ") || strstr(str, "get done ") || strstr(str, "left ") || strstr(str, "made ")
            || strstr(str, "owed ") || strstr(str, "paid ") || strstr(str, "promised ") || strstr(str, "refused ") || strstr(str, "shown ")
            || strstr(str, "taken ") || strstr(str, "told ") ) {
        return 1;
    } else {
        return 0;
    }
}

// Once a week, the house is cleaned by Tom. <- passive
// By the end of the week, I'll be gone. <- not passive, but ok.
int contains_by(char* str) {
    return (strstr(str, "by ") != NULL);
}

// how to find No direct object -> I don't know.
// The subject of the verb phrase is the entity undergoing an action or having its state changed -> I don't know.

int passive_voice(char* str) {
    // relax conditions, by applying || isntead of &&
    if(auxilary_verb(str) || past_participle_transitive_verb(str) || contains_by(str)) {
        return 1;
    } else {
        return 0;
    }
}

I recommend you look at methods in the NLP literature for parsing a sentence and identifying its structure, classifying the tense of the sentence and the words present in it, and identifying the subject and object of the sentence.  That should help you build a more accurate classifier.  If you extract suitable features, given the parse tree, and then apply a suitable machine learning algorithm, you might get a more effective classifier.


Heap-like data structure allowing peek at largest & smallest For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations:

load from array
Peek at maximum element (but don't destroy it)
Peek at next-to-maximum element
Peek at minimum element
decrease the maximum element

Once initialized, the data structure always stores the same number of elements.

Currently I'm just using an unsorted array, and searching the array each time to find the max, next-to-max, and min elements, and updating the max element when necessary.

I considered using a heap / priority queue, but those don't seem ideal, as they support adding and removing elements, which I don't need to do. They also don't natively support "decrease the maximum element", just "increase an arbitrary element" so I'd have to extract-max and then re-add it.

I also considered a sorted array in a ring buffer, which seems like it would be better than just a sorted array, as I'd only have to move at most half of the list.

Wikipedia talks about some complicated data structures (Fibonacci heaps) that I vaguely remember from my sophomore algorithms class in college, but those seem like overkill (and they also support features I don't need and don't support features I need).

Well, now I search again and I find my question is sort of kind of a duplicate of Increase-key and decrease-key in a binary min-heap

One simple approach is to use a max-heap.  Separately keep track of the minimum element stored in the heap.  Then all operations can be done relatively efficiently:

Load from array can be done in $O(n)$ time, building Build-Heap.
Each of the peek operations takes $O(1)$ time.
Decreasing the maximum element can be done in $O(\lg n)$ time.  You decrease it and fix up the heap property (or extract it and re-insert it). Then, check whether it got reduced below the previous-smallest and if so update the minimum.

This seems likely to be reasonable for many workloads.

Alternatively, you could store the elements as a balanced binary tree with the leaves in sorted order.  Keep track of a pointer to the leftmost leaf and a pointer to the rightmost heap.

To load from array, sort the elements and then create a balanced binary tree; this can be done in $O(n \lg n)$ time.
All of the peek operations take $O(1)$ time.
The decrease operation can be implemented in $O(\lg n)$ time, by deleting the maximum and then inserting it in the new place, using standard data structures for balanced binary trees that support $O(\lg n)$ time insertion and deletion (e.g., AVL trees, red-black trees, etc.)

This too will likely be reasonable for many workloads.