# Question
Title: Best Fit Memory Allocation Algorithm Statistical Analysis
I've been reading book on Operating System, in which author writes :

> Somewhat surprisingly, it(Best fit) also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on average.

I want to understand how generating larger holes would be better. It would be helpful if someone can share a link of article about statistical analysis of best fit, first fit.

# Answer
You want your "holes" to be bigger because a big hole is more likely to be useful for an allocation in the future. For example, if you have 2 128-byte holes that are not adjacent then you can't satisfy a request for 160 bytes. If the 2 128-byte holes are adjacent and coallesced into a single 256-byte hole, then you could satisfy a future request for 160 bytes with that hole.

Here's the best article I know of on memory allocation policies:

Paul R. Wilson, Mark S Johnstone, Michael Neely, David Boles: Dynamic Storage Allocation: A Survey and Critical Review, *Int'l Workshop on Memory Mgt*, 1995.

They followed up with a more detailed experimental study a few years later:

Mark S Johnstone, Paul R Wilson: The Memory Fragmentation Problem: Solved?, *First Int'l Symposium on Memory Mgt*, 1998.

In the papers they find that best fit works quite well in practice. Another lesson of both papers is that statistical analyses don't work (usually). You need to run experiments on real traces of the `alloc`/`free` calls from real workloads.

A very good public domain `malloc` implementation was written in the mid '90's by Doug Lea: http://g.oswego.edu/dl/html/malloc.html. It's essentially an approximation of best fit.
> 1 votes

---
Tags: operating-systems, memory-management, statistics
---


# Question
Title: Matrix Chain Multiplication Greedy Approach
In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic Programming but I have found a greedy approach to this problem.

For example a chain of Matrices of the size of:

```
   A        B       C       D
40 * 20  20 * 30 30 * 10 10 * 30

```

First list all of the possible consecutive pairs, and the 2 different dimensions of the pair:

```
        X
AB:  40 * 30
BC:  20 * 10 <----
CD:  30 * 30

```

Then multiply the pair that has the lowest product in the X column and the list will turn into:

```
   A       BC      D
40 * 20 20 * 10 10 * 30

```

Repeat the first 2 steps until all of the matrices are multiplied together:

```
          X
A(BC): 40 * 10 <----
(BC)D: 20 * 30

  ABC      D
40 * 10 10 * 30

             X
(A(BC))D: 40 * 30 <----

```

This have a time complexity of $O(2n^2 + 2n\log n)$.

I have tested a Java implementation on smaller test cases and it runs fine.

Does this method work, or is there a something I have overlooked?

# Answer
You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $24$. In contrast, the other option has complexity $10 + 10 = 20$.

According to Wikipedia, Hu and Shing came up with an $O(n\log n)$ algorithm, which is more efficient than your algorithm, and moreover is provably correct.
> 9 votes

---
Tags: algorithms, algorithm-analysis, greedy-algorithms, correctness-proof
---


# Question
Title: Proof that there are same number rotation moves in any binary tree with both children compulsory
I am working on this project where I am required to find the theoretical proof for following.

I have a particular type of binary trees, where

1) each internal node will definitely have two children.

2) There are n leaf nodes and can be assumed in order 1 to n from left most to right most.

Now this is clear that there are multiple such trees. And I am performing tree rotation (https://en.wikipedia.org/wiki/Tree\_rotation) operation in any of one internal node of the tree.

I was thinking that in any such type of tree with n leaf nodes there will be guaranteed n-1 internal nodes and total n-2 possible rotation moves. (The rotation is only valid if the rotated tree also has the two given properties i.e. an internal node with just left node as leaf node cannot be right rotated.)

I have tried various resources but couldn't find any proof for it. I have tried it myself but not able to reach to a solution. I'd be glad if someone can help me out here.

EDIT:

I could get to one possible proof, please see if it's correct.

There are 3 parts of the proof:

a) With these rotation moves, you can convert to any of the tree into a completely left branching tree, I have the proof for it and it's well known in graph theory.

b) Any rotation moves preserves the number of possible rotations in the tree. This is critical, I will prove it in the end.

c) In any left branching tree, out of total n-1 internal node, everyone except one can be right rotated. So total n-2 rotations.

All 3 together gives that total n-2 rotations possible.

Now the critical (b) part:

From the wikipedia image on the link (https://en.wikipedia.org/wiki/Tree\_rotation), the number of rotations for subtrees A, B ,C remains the same and reverses for P and Q. So the total moves will remain same.

I can give more details for the above statement if required, but it's hard to write it here.

# Answer
> 3 votes
Each rotation involves a node and its left or right child. We can associate this rotation with the child – the rotation is fixed once the child is known. In your case, a child can be rotated as long as it is an internal node. So the number of possible rotations is the number of non-root internal nodes. A simple induction shows that a full binary tree having $n$ leaves has exactly $n-1$ internal nodes, and so $n-2$ non-root internal nodes.

---
Tags: proof-techniques, trees, binary-trees
---


title: Adding orders of growth

text:
# Question
Title: Adding orders of growth
I am confused as to how this is true: O(n log n) + mO(log n) = O((m + n) log n)

I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n).

# Answer
We can prove that if $f(n)$ is $O(\log{n})$ and $g(m)$ is $O(m)$ then $f(n)g(m)$ is $O(m \log{n})$. To say that $mO(\log{n}) = O(m \log{n}))$ is an abuse of notation.

See Wikipedia for similar properties of big O: http://en.wikipedia.org/wiki/Big\_O\_notation#Properties.
> 1 votes

---
Tags: asymptotics, landau-notation
---


title: Caches and reading a PDF

text:
# Question
Title: Caches and reading a PDF
I am currently learning about caches in Systems class, and I had a few doubts about what exactly happens when a Computer reads a PDF. This is the sequence that happens in my mind:

1. The CPU checks if the pages of the PDF I want to read are there in cache.
2. It is not, so we keep going down the Cache hierarchy until we get to the Hard Drive, from where the PDF is located and read into main memory.
3. From main memory, it goes all the way back to L1 cache, and the CPU reads it.

Is there anything wrong with the simplification I have given above?

I know that Cache entries use the effective memory address of its data to determine where the data will be placed in the structure. Here, in this example, what exactly will be the memory address of the PDF?

# Answer
When a computer reads a PDF... You can take several perspectives.

From Acrobat reader, it asks the operating system to read a file, copies it to memory then interprets drawing commands. From applications POV, caches don't exist.

Of course, there is nowadays a disk cache in RAM, where the last used sectors are kept for shorter access time. Some OS even trick the MMU between the disk cache and application address spaces so that data is not even copied. That cache is not visible to applications (which can also have their own caching, for example pre-rendered pages...)

From the operating system, CPU caches needs sometimes to be manually managed, on some platform, particularly when there are peripherals that are modifying memory without CPU intervention ("non coherent DMA"). It could be the disk controller reading that PDF file. On current high performance CPUs, the kind you find in computers or tablets where Acrobat can be installed, the CPUs practically manage their caches transparently.

So, CPU caches are mostly hidden to software.

Cache are made of two parts : the datas, and the tags. Datas contains a portion of RAM area. Tags indicate which part of the RAM is in the cache. Data is grouped in chunks ("cache line"), usually 32 to 128 consecutive bytes.

When a CPU accesses its caches, it lasts usually less than 5 cycles for L1 caches, and less than 20 cycles for L2 caches. Accesssing DRAM can waste hundreds of cycles. Despite being very small (for example 32kB L1 compared to 4GB DRAM), they are incredibly efficient, because, in reality, accesses are often grouped, or consecutive, or repetititve, so that the same parts of main memory are accesses several times.
> 1 votes

# Answer
Whatever the context, the concept of a cache works as follows:

* when you want to access an item, you first check if it is stored in the cache;
* if yes (cache hit), you can access the object in the cache, at a low cost;
* if no (cache miss), you load the item from another level (at a higher cost) and copy it to the cache (possibly discarding another item to make room); then you are back in the first situation.

---

When modifying the item, you have the option to write it only to the cache (write-back), or to the other level through the cache (write-through). In the first strategy, the write to the other level is deferred until the item is discarded from the cache.

---

A cache is beneficial in case of data *reuse*. That means if you don't just read or write an item once, but do it several times in a relatively short delay (before the item is superseded by others).

In some situations, you have the possibility to fill the cache ahead of time (in parallel with other tasks), so that when the data is needed, access is fast.
> 1 votes

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: What is meant by a language have a "finite specification"?
I'm studying my notes for a formal language course and it them it states

> The vast majority of languages over a finite alphabet cannot be represented by a finite specification.

I don't understand this. What is meant by "specification"? It then goes on to show why this is true by showing some sets of the alphabet are countably infinite and others are uncountably infinite.

# Answer
> 8 votes
A specification in this sense is any description of the language that allows you to determine exactly what strings are in the language and what strings are not. We're usually quite vague about what exactly constitutes a specification since, ultimately, it doesn't matter. A specification must be describable by some finite string of characters, whether those characters represent English words ("The set of all strings consisting of some number of $a$s followed by the same number of $b$s"), mathematics ("$\\{a^nb^n\mid n\geq 0\\}$") or somethign else. As your notes go on to say, whatever reasonable meaning you give to "finite specification", there will only be countably many of them, whereas there are uncountably many languages.

---
Tags: formal-languages
---


# Question
Title: greedy algorithm for Maximum directed cut
Maximum directed cut: Given a directed graph $G = (V, E)$ with nonnegative edge costs, find a subset $S \subseteq V$ to maximize the total cost of edges out of $S$: $\mathrm{cost}( \\{ (u \to v) \mid u \in S \text{ and } v \in \bar{S} \\})$.

I am trying to come up with a greedy algorithm for Maximum directed cut with factor 1/4.

# Answer
The starting point is the trivial *random* algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.

We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we know which of $1,\ldots,i-1$ are in $S$ and which are in $\bar{S}$. If we put $i \in S$, then we can compute the expected cost of the output given that all further choices are made randomly; and we can do the same if we put $i \in \bar{S}$. One of these choices cuts at least $1/4$ of the edges (in terms of weight), and this is the one we choose.

We can further optimize this algorithm. Consider the following two expressions: $$ A = \sum\_{\substack{j\<i\\j\in\bar{S}}} w\_{ij} + \frac{1}{2} \sum\_{j\>i} w\_{ij}, \\ B = \sum\_{\substack{j\<i\\j\in S}} w\_{ji} + \frac{1}{2} \sum\_{j\>i} w\_{ji}. $$ (Here $w\_{ij}$ is the cost of the edge from $i$ to $j$.) If $A\>B$ then the derandomized algorithm puts $i$ in $S$, whereas if $A\<B$ it puts $i$ in $\bar{S}$ (if $A=B$ it doesn't matter). We can perhaps think of this algorithm as a greedy algorithm.

---

As an aside, the so-called *double greedy* algorithm gives a $1/2$ approximation algorithm. The greedy algorithm you suggest in the comments is good in combination with the random algorithm: if you run both and choose the better solution, you get a $2/5$ approximation (see Feige's paper). The semidefinite relaxation gives the (probably) optimal approximation ratio, which is roughly 0.874.
> 6 votes

---
Tags: algorithms, algorithm-analysis, greedy-algorithms
---


title: Why won't a Turing machine halt?

text:
# Question
Title: Why won't a Turing machine halt?
I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on some inputs. The language to be precise is $L=\\{\langle M,w \rangle| \ M \text{is a turing machine and } w \text{ is a string M accepts} \\}$. Let $D$ be the turing machine that recognises $L$. Inability of $D$ to halt on some inputs is due to the fact that there exist Turing Machine $M$ which do not halt on some input. Thus the reason for not halting is kind of recursive ( if I consider only this example ). I am still not able to understand in crux why a turing machine won't halt. But can't come up with language over $\\{0,1\\}$ which is turing recognisable but not decidable. What are all the reasons a Turing machine won't halt ?

# Answer
A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following:

```
while (true)
{
   do_nothing
}

```

, then it will never halt!

The language $L$ goes over **all** possible machines $M$, and therefore it must encounter some machines that don't halt, for instance, the one stated above.

There is a deep difference between the reason the above machine doesn't halt (it is just programmed to do so), and the reason that any machine for $L$ will not halt–no machine for $L$ exists since that language is undecidable.

regarding your question about finding a more "natural" language that is undecidable, see Is there a “natural” undecidable language?. You may get some more intuition about undecidable languages here.
> 19 votes

# Answer
A Turing machine doesn't halt if it never reaches a halting state. For example, it might keep moving its head to the right, never stopping. Or it might count $1,2,3,\ldots$, never halting. It doesn't need a reason not to halt.

What we know about the language $L$ is that there is no machine $T$ that satisfies the following two properties:

1. If $\langle M,x \rangle \in L$ then on input $\langle M,x \rangle$, $T$ halts and outputs YES.
2. If $\langle M,x \rangle \notin L$ then on input $\langle M,x \rangle$, $T$ halts and outputs NO.

How do we know that? Sipser proves it in his textbook. The naive attempt at deciding $L$, that is simulating $M$ on $x$, doesn't halt when the answer is NO; but there could be a completely different algorithm whose principle of operation is different and doesn't suffer from this problem. What Sipser shows (following Turing) is that no matter what you do, you cannot come up with a machine $T$ deciding $L$.
> 10 votes

---
Tags: turing-machines, halting-problem
---


title: Regular languages and sets proof

text:
# Question
Title: Regular languages and sets proof
I just have general questions about sets and determining if they are regular languages.

i) If A is regular, and A is a subset of B, then B must be regular.

ii) If B is regular, and A is a subset of B, then A must be regular.

iii) If A and AB are regular, than B must be regular

iv) If Ai is an infinite family of regular sets, than the union of all those sets is regular.

For the third one, I know that AB can only be regular if B is regular, because a regular set * a irregular one is not regular.

Lost for the other ones.

# Answer
> 3 votes
Always think of boundary cases. In this case - the languages that contain every string or no string.

Also, let $N$ be some arbitrary non-regular language.

i) The language that contains no strings, which is regular, is a subset of $N$.

ii) $N$ is a subset of the language that contains all strings, which is regular.

iv) For every string $S\_i$ in $N$, construct a set $L\_i$ that contains only $S\_i$. Note that all of these constructed sets are trivially regular. But the union of all of these (infinite number of) constructed sets is $N$, which is not regular.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Algorithm for finding maximum mutually coprime subset of a multiset of integers
For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble thinking of a good general algorithm for this, and everything I've found online seems to relate to problems that are slightly different to what I'm going for. For example, given the multiset of integers A = {12, 15, 15, 16}, I would like the algorithm to return {15, 16}.

The first naive solution I could think of was to order the numbers in increasing order, take the first number into my set, then take any number after that which is coprime with all of the numbers in the set. This works for things such as {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, but it would erroneously give {12} in my example above.

Besides that, the best idea I have is to create a list of sets of the factors of each number, at which point this problem can be reduced to the exact cover problem. However, I feel like this would have a relatively large amount of overhead, especially given the fact that the data sets I'm operating on won't be very large (~1000 elements somewhere in between 1 and 500).

Is there any algorithm I could apply here that would be more simple to implement (even if it is slightly slower) and would guarantee an optimal solution?

# Answer
Your problem is equivalent in complexity to the maximum set packing problem. Unfortunately, maximum set packing is NP-hard. Therefore, you'll need to use one of the methods in Dealing with intractability: NP-complete problems.

---

Here's the gist of the equivalence. Each integer in your set A corresponds to a set of its prime factors; now you're looking for a maximum-size collection of those sets that are pairwise disjoint. That's exactly maximum set packing. This is only the gist of the idea; this reduction doesn't quite work, because as you noticed, factoring each element of A can take quite a bit of time (there's no known polynomial-time algorithm for factoring).

It's possible to fix up the reduction as follows. Given an instance of your problem, factor A into a coprime base. A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base. For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}. Note that the elements of the coprime base do not need to be prime. There are efficient algorithms for finding a coprime base for A. Now, associate to each number x in A the set of elements of the coprime base that are divisors of x. Then you have an instance of the maximum set packing problem.

(Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.)

---

So given that you basically have an instance of maximum set packing, what should you do? Well, maximum set packing has been well-studied, so you can use the literature on that problem. Here are some candidate approaches:

ILP: It's easy to formulate the maximum set packing problem as an instance of integer linear programming. You have a zero-or-one variable $x\_i$ for each integer $i$ in A, with the idea that $x\_i=1$ means that $i$ is included in the output list. You add a constraint $x\_i+x\_j \le 1$ for every pair of numbers $i,j$ that have a common factor. Then, you try to maximize the objective function $\sum\_{i \in A} x\_i$. Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find.

If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet. It'll be easy to implement. There's no guarantee that it'll be efficient -- it's an NP-hard problem, after all -- but it might work well enough in practice if the problems sizes are small enough.

Heuristics: You can use any of the known heuristics for set packing. See, e.g., https://en.wikipedia.org/wiki/Set\_packing#Heuristics, or search the research literature.

Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set. (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.) If the numbers in A aren't too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective. Wikipedia doesn't say what the algorithm is, so you'll have to do some research in the literature.
> 3 votes

# Answer
Please, identify constraints on the size of multiset and its values.

If they are not very large, you can use Knapsack (Dynamic programming) method to solve this problem.

In this method, you can choose a number in the multiset or not. Therefore, one of the item, which must be considered in the dynamic programming solution, is the position of numbers in your multiset.

The other item is a value which holds LCM (lowest common multiple) of added numbers to an answer. This number, indeed, maintains the LCM of those numbers, which have been used in the current state.

As a result, the number which is going to be added as an element to the optimal set must not have any common factor with the LCM number.

something like that (consider this only a pseudo code): $dp \[pos\]\[LCM\] = max (dp \[pos - 1\]\[LCM\] , dp \[pos -1\]\[\frac{LCM}{factors\\\_of\\\_number \[pos\]}\] + 1)$, where

* $pos$ stands for the position of a number in a given multiset
* $number \[pos\]$ means the value of a number in the position $pos$ of the multiset
* $factors\\\_of\\\_number \[pos\]$ is the product of all prime numbers, by which $number \[pos\]$ is divisible; for example, if $number \[pos\]$ is equal to $12$, the set of prime numbers, which can make $12$, will be $\\{2,3\\}$, i.e., $factors\\\_of\\\_number \[pos\]$ will be $6 (= 2 \times 3)$
> 2 votes

---
Tags: algorithms
---


# Question
Title: Testing regular expressions algorithmically
Is it possible to test algorithmically whether the language of a given automaton is empty?

If I have a language L, could I say that L intersection with the empty set is L?

# Answer
Hint: Check whether there is a path from the starting state to some accepting state.
> 1 votes

---
Tags: algorithms, automata, regular-expressions
---


title: When does a PDA split?

text:
# Question
Title: When does a PDA split?
In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. In case of PDA where transitions are of the type $a,b \to c$, with $a$ being the input alphabet being read, $b$ being the stack element being read and popped and $c$ being the stack element being pushed. In NFA I understood the splitting upon $\epsilon$ as the ability to guess. So I assumed that a PDA in a state $r$ with stack being $S$ splits into two PDA only when the transition is $\epsilon,\epsilon \to \epsilon \\\$ ( that is when $a=b=c=\epsilon$ in the figure below the PDA splits into two with one being in state $r$ and other in $s$ with same stack $S$ ). But now I am a bit doubtful, about when does a PDA split. I feel I am wrong and am misunderstanding something trivial. ( The figure below just shows the part of a larger PDA ). How would it affect the power of a PDA if it were only allowed to split on $\epsilon,\epsilon \to \epsilon$ transition?

# Answer
> 2 votes
A PDA (or an NFA) doesn't split. At any given point in time, it non-deterministically chooses a valid next step, if any. If there are several options, you can say that the PDA "splits" if you wish, trying all of them in parallel.

A PDA (or an NFA) could have more than one possible move even if it has no $\epsilon$ moves, and conversely, there might be situations in which an $\epsilon$ move is the only possible move of the automaton (can you think of such a situation?). So your identifying $\epsilon$ transitions with "splitting" is wrong.

---
Tags: automata, finite-automata, pushdown-automata, nondeterminism
---


# Question
Title: Maximum flow, where such paths as source$\to$node$\to$sink must be ignored
How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths as $\text{source} \to \text{node} \to \text{sink}$, where $\to$ is a single edge?

A valid path containing a positive flow can be $source \to v$, $v \to w$, and $w \to sink$ where $v \neq{w}$.

I am not sure whether it's helpful, but the graph is a DAG (directed acyclic graph).

# Answer
Let $G=(V,E)$ be some directed graph where every node $v\_i$, except for the source $s$ and sink $t$, has an in-edge $(s,v\_i)$ and an out-edge $(v\_i,t)$.

To compute the desired flow, we can reduce the problem to a new directed graph $G'=(V',E')$, where every node of the original Graph, except for $s$ and $t$, is replaced by two new nodes $v\_i'$ and $v\_i''$. The source is now connected to $v\_i'$ and the sink to $v\_i''$. Thus, we have new edges $(s,v\_i')$ and $(v\_i'',t)$. Furthermore, we connect every $v\_i''$ with the corresponding $v\_i'$ via an edge $(v\_i'',v\_i')$ of very high capacity. Finally, we add an edge $(v\_i',v\_j'')$ for every edge $(v\_i,v\_j)$ of the original graph. The capacity of every edge in $G'$ is equal to its counterpart in $G$, except for the edges $(v\_i'',v\_i')$, wich correspond to nodes in $G$ and therefore have arbitrary high capacity.

Note that flow that enters $v\_i'$ via the source can not directly escape to the sink but must traverse an edge $(v\_i',v\_j'')$ to another vertex $v\_j''$ first. From $v\_j''$ the flow can either go to the sink, or continue onwards via $v\_j'$. Thus, by computing a maximum flow in $G'$ we obtain a solution for $G$ where all flow that leaves the sink must traverse at least three edges before it reaches the sink.
> 1 votes

---
Tags: graphs, network-flow
---


# Question
Title: State of the art time complexity for getting (tree) descendants by type/attribute
Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only have one type. Let's also assume that our tree is somewhat balanced, and that there are far more nodes in the tree than there are unique types. Assuming I have already created some sort of index on the tree, I need to know the state of the art time complexity for the following types of queries (using whatever type of index / data structure you like):

Where **A** is some arbitrary node in the tree and **T** is some arbitrary type:

1. find all descendants of node **A** that are of type **T**
2. find the *number* of descendants of node **A** that are of type **T**

If the tree is static and no updates to the index are required, I have a data structure that will do 1 and 2 in $O(1)$. If the tree can have nodes added/removed, I also have a data structure that will do 1 and 2 in $O(\log m)$ where m is the total number of nodes of type T in the tree ($m \<\< n$), and that can update the index when changes are made to the tree in $O(k\log m)$ where k is the number of nodes affected.

Are my data structures state of the art for these types of queries, or on par with state of the art? What existing work is out there that can match or beat this performance, if any?

(assume that any indexing structure we use must take less than $O(n^2)$ time and memory to construct)

(assume that any indexing structure we use for the case where the tree/index can be modified, that modifications can be handled in better than $O(n)$)

My understanding is that XML indexing generally has the state-of-the-art indexing schemes for dealing with trees where there are typed nodes, so I assume something with XML indexing will crop up here. I've tried looking through a number of papers myself but it's very difficult to get actual time complexities out of people in that field for some reason.

# Answer
> 1 votes
For the static case, if you have a solution with $O(1)$ running time, I can't see any opportunity for improvement in the running time, as you can't do better than $O(1)$. So I'll focus on the dynamic case, i.e., where we want to support insertions and deletions.

One strategy is to augment the tree, so that for each type $T$ each node $x$ contains:

* A count of the number of descendants of type $T$
* A pointer to each immediate type-$T$ descendant of $x$ (i.e., a link to each $z$ such that $z$ has type $T$, $z$ is a descendant of $x$, and there is no descendant $y$ of $x$ such that $y$ has type $T$ and $z$ is a descendant of $y$)
* A pointer to the immediate type-$T$ parent of $x$ (i.e., the lowest ancestor of $x$ that has type $T$)

This allows 'count' queries to run in essentially $O(1)$ time: given a node $x$, you can count the number of type-$T$ descendants of $x$ in $O(1)$ time. (Simply find $x$'s immediate type-$T$ parent, then use the field in the parent that stores the count of number of type-$T$ descendants.)

Also, 'enumerate' queries run in $O(k)$ time: given a node $x$, you can enumerate all type-$T$ descendants of $x$ in $O(k)$ time, where $k$ is the number of type-$T$ descendants of $x$. (Simply find $x$'s immediate type-$T$ parent, then traverse the fields that list the immediate type-$T$ descendants, recursively.)

The running time to insert a new leaf at depth $d$ in $O(d)$ time, since you only need to update the fields in the nodes along the path from that leaf to the root. If the tree is balanced, this is $O(\log n)$ time.

The running time to delete a leaf at depth $d$ is the same, for the same reasons.

This is the best I know how to do. I don't know if it is possible to do better.

---
Tags: data-structures, time-complexity, trees, database-theory, balanced-search-trees
---


# Question
Title: Trying to code for calculating cosine series
I was trying to calculate cosine series : cos x = 1 - x^2/2! + x^4/4! - x^8/8! .... , where x is in radians: include iostream

include math.h

using namespace std;

long factorial (long num)

{

if (num \>1)

return num\*factorial(num-1);

else return 1;

}

int main()

{int X,sum=0;

cout\<\<"Enter value of x in radians : ";

cin\>\>X;

for (int i = 0; i\<=4; ++i)

```
{

    int z = pow(-1,i);

    int p = (pow(X,2*i)*z)/factorial(2*i);

    sum += p;

}

```

cout\<

return 0;

} on putting x as 1.57( 90 degrees), I am getting 1, instead of 0. Can anyone explain why?

# Answer
You are using integer arithmetic rather than floating point arithmetic. Make sure you understand the difference.
> 1 votes

---
Tags: algorithms, programming-languages
---


title: All Pairs Shortest Path Fewest Stops

text:
# Question
Title: All Pairs Shortest Path Fewest Stops
I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex to any other vertex. If I choose to refuel, I can fill the tank completely.

My thought is to modify the Floyd - Warshall Algorithm to keep track of both number of refills, and amount of gas left. However, I am not sure how to proceed.

Note: This is NOT a HW question. I was reading To Fill or not to Fill: The Gas Station Problem and began to wonder.

# Answer
This problem cannot be solved using a (modified) Floyd-Warshall Algorithm. The underlying assumption in F.-W. is that all paths arriving at a given node can be extended along the *same* path to the destination. Therefore choosing the shortest path that arrives at a node is also optimal for all paths that pass *through* the node. By adding the fuel constraint, this assumption is broken.

More generally, problems of this form are called the Resource-Constrained Shortest Path Problems and are, in general, $\mathcal{NP}$-hard. A generic solution to this problem is to enumerate all feasible paths that lead to any node in the graph, which obviously leads to exponential time complexity. In practice, "dominance" rules are applied to prune partial paths that are clearly inferior to other partial paths; in your case such a dominance rule could be to throw away all paths arriving at a node with more refills and less fuel than another path arriving on the same node.
> 1 votes

# Answer
I think you can run BFS or DFS method $N$ times for each vertex as a source, where $N$ is the number of vertices. The thing you should consider is the fact that each state in BFS or DFS method comprises two items. The first one is the vertex number and the second is the remaining fuel. Let state $(3, 50)$ denote we are in vertex $3$, and the remaining fuel is $50$. If vertex $4$ is an adjacent vertex, and the required fuel for the path $3 \to 4$ is $60$, then refueling is required. On the contrary, if fuel for the path $3 \to 4$ was $40$, we could reach vertex $4$ with state $(4, 10)$.
> 0 votes

---
Tags: algorithms, graphs, optimization, shortest-path
---


title: Almost Hamiltonian

text:
# Question
Title: Almost Hamiltonian
A graph is *almost Hamiltonian* if it contains a cycle that visits every node at least once and at most twice.

Is the problem of determining whether a graph is almost Hamiltonian NP-complete?

# Answer
> 4 votes
Yes it is NP-complete. Membership in NP is trivial. Thus, we must only show NP-hardness. To do so, we use a reduction from the original Hamilton cycle problem.

Given a graph $G=(\\{v\_1,\dots,v\_n\\},E)$, we can construct a new Graph $G'=(\\{v\_1,\dots,v\_n\\}\cup\\{v\_1',\dots,v\_n'\\},E \cup \\{(v\_i,v\_i')\mid 1\leq i\leq n\\} \cup \\{(v\_i',v\_i)\mid 1\leq i\leq n\\})$. Note that in order to reach one of the nodes $v\_i'$, one must visit $v\_i$ twice on a cycle $v\_i - v\_i' - v\_i$. Apart from that, the edges in $G'$ are the same as in $G$. Thus, $G'$ is almost Hamiltonian if and only if $G$ is Hamiltonian, which completes the proof.

---
Tags: graphs, np-complete, hamiltonian-path
---


# Question
Title: Why are there $2^{2^{n}}$ possible boolean functions of n inputs?
Why are there $2^{2^{n}}$ possible boolean functions of n inputs? How to derive that?

For 3, I can only write down 16 and cannot go further.

8 of

$f(x\_{1},x\_{2},x\_{3})=0$

000 = 0

001 = 0

010 = 0

110 = 0

111 = 0

110 = 0

101 = 0

011 = 0

and

8 of

$f(x\_{1},x\_{2},x\_{3})=1$

000 = 1

001 = 1

010 = 1

110 = 1

111 = 1

110 = 1

101 = 1

011 = 1

That's the maximum I can go. How do I proceed?

# Answer
Hint: let $f$ be a boolean function with $n$ inputs i.e $f(b\_{1},b\_{2},b\_{3}...b\_{n})$ For example, when $n=3$, $(1,0,1)$ and $(1,1,0)$ are different inputs to $f$. Each input maps to an answer. Also there are limited values that $f(b\_{1},b\_{2},...,b\_{n})$ can take.

Now consider the definition of a function: $f\colon A \to B$

Define the size of both sets $A$ and $B$ and you will arrive at your answer.
> 4 votes

# Answer
There are $2^{2^3}=256$ different boolean functions of 3 inputs. The $2^3$ here represents the number of rows in the truth table.

Here is the truth table for one of the functions.

Every different assignment of column $X$ is a different function. There are a total of 256 assignment.
> 2 votes

# Answer
For any function f, we are being provided n inputs i.e. f(x1,x2,x3,...,xn). Now, it's not important that that function f uses every input provided to produce an output i.e. f may only use a certain subset of inputs from the set of given inputs. The number of possible ways of selecting distinct subsets from a given set of n elements = 2^n. (common set property). Now another thing is the function is boolean. So for every set of inputs it uses, there can be two functions f1 and f2, one which provide true and other which result out for false. Hence there can be 2^(2^n) possible ways for generating boolean functions given n inputs.
> 1 votes

# Answer
Three input variables form $8$ distinct combinations and you can freely associate $0$ or $1$ to each of them. That makes $2^8$ distinct functions.

$$000\ 001\ 010\ 011\ 100\ 101\ 110\ 111\\\downarrow\\ f\_0:0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\\ f\_1:0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\\ f\_2: 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\\ f\_3: 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\\ \cdots\\ f\_{255}:1\ 1\ 1\ 1\ 1\ 1\ 1\ 1$$

For example,

$$f\_\lor=0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\ f\_\land=0\ 0\ 0\ 0\ 0\ 0\ 0\ 1$$
> 1 votes

# Answer
Even though it is frequently easy to use a formula in order to represent a Boolean function, Boolean functions are defined by their truth tables. Further, if two Boolean functions differ in at least one row of their corresponding truth tables, then we are really talking about different functions (as the functions return a different value at that point), so your problem really asks how many Boolean functions can be defined in $n$ boolean variables.

Now, pick an arbitrary Boolean function with $n$ boolean attributes; that is $f(x\_1, x\_2, \ldots, x\_n)$. The number of rows of its corresponding truth table is $2^n$ (there are $2^n$ different truth assignments as inputs). However, in every such row (think truth assignment) you can fill in a $0$ or a $1$ which is the actual value of the function at that point. In other words we have two choices per row. Thus, by a counting argument we have $$ \underbrace{2\cdot2\cdot\ldots\cdot2}\_{2^n \ \mbox{times}} = 2^{2^n} $$ different Boolean functions that can be defined on $n$ boolean variables.
> 1 votes

---
Tags: combinatorics
---


# Question
Title: Does a Hadamard Gate have uses outside of pure and evenly mixed states?
The standard usage cases for the Hadamard gate seem to be passing a pure $|0\rangle$ or $|1\rangle$ state in to get an even amplitude (probability) mixed state which has either matching or mismatching phase.

The other use of course, is to take such an even amplitude mixed state, pass it through the Hadamard gate, and get back a pure $|0\rangle$ or $|1\rangle$ state.

This of course scales up to multiple qubits.

Are there any other usage cases for the Hadamard Gate? I'm wondering if say you had an uneven amplitude qubit, would passing it through a Hadamard Gate do anything useful? Or the same question with multiple qubits, that had varying amplitudes of states.

Thanks!

# Answer
I don't know of any explicit use of the Hadamard gate in circuits other than to introduce or take away superposition, but here are some interesting applications:

1. The Hadamard gate is the single-qubit version of the Fourier Transform\*, and the Fourier Transform is very useful.
2. Instead of using the Hadamard at the end of a computation to get back the original basis, you can *measure* the system in the Hadamard basis instead of the standard basis.
3. The set of $\\{\text{CNOT}, \text{Hadamard}, \text{rotation by 45 degrees}, \frac{\pi}{8}\text{-gate} \\}$ is a universal quantum gate set. That is to say, any quantum gate can be approximated arbitrarily well by repeated application of gates from this set.
4. If you prepend and append two Hadamard gates to a CNOT gate, you reverse the role of control bit and target bit.

\*Demonstration: The quantum Fourier transform is defined as follows. Take a system of $n$ particles in the standard basis, and put it in state $|k\rangle, 0 \leq k \leq 2^n-1$. Then applying the Fourier Transform $F$ yields a big superposition:

$$ F|k\rangle = \sum\_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot k}{2^n-1}}|u\rangle $$

Take $n=1$ and $k\in\\{0,1\\}$, and you see that $F|0\rangle = |+\rangle$ and $F|1\rangle=|-\rangle$. As you can see, it is performs exactly the same transformation as a Hadamard gate. Moreover, for any number of qubits $n$, the Fourier still behaves as the Hadamard only for the state $0$, on which it acts as follows:

$$ F|0\rangle\_n = \sum\_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot 0}{2^n-1}}|u\rangle\_n = \sum\_{u=0}^{2^n-1}e^{0}|u\rangle\_n = \sum\_{u=0}^{2^n-1}|u\rangle\_n $$

I have not normalized my states in these examples, but you should definitely do so on an exam.
> 6 votes

---
Tags: quantum-computing
---


# Question
Title: Why some rules in Elementary Cellular Automata halt and others don't?
I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps and 100 steps are the same, like Here}.

Unlike rule 110 which shows different behavior when N = 20, 100 or 200, i know that it is universal but does that mean if a cellular automaton structure does not halt {continue to show different pattern when changing N steps} does that means it is always universal ?

# Answer
Your problem is formalized in research as follows: given a CA, is it "Turing complete"? This has been proved for a limited set of CAs including rule 110 in the early 2000s by Cook in a notable proof. it was probably first proved for a CA for the game of life by Conway in the 1970s. There are empirical ways of analyzing CAs that can rule out Turing completeness, and "signs/ circumstantial evidence" that a CA *might* be Turing complete, but no CA can be proved Turing complete or not from a finite number of example cases.

TMs can execute an arbitrary number of steps and then halt, so that is a characteristic required of the CA simulation. But there is no standard way of defining whether a CA "halts" and thats up to the universality mapping. There is currently no general theory of CA←→TM mappings. There are different mappings in the literature and Cooks mapping is also called "weakly Turing complete" because it requires infinitely recurring patterns specified on the CA input.

There is no general way to find whether particular CAs and rules are universal. This is essentially equivalent to the halting problem in general.

Unfortunately Wikipedia does not highlight Turing completeness in CAs. Here are two useful alternative references.
> 2 votes

---
Tags: computability, cellular-automata
---


# Question
Title: Bounds on the number of rotations in the insertion operation of a Red Black Tree
I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree.

From what I've gathered, there are several special cases to take into consideration in the `fixUp` algorithm posterior to the standard BST insertion on the tree. But from all those cases, only one will put the grand-parent node as red, so only this case may require subsequent work (if the grand-grand parent exists and is a red node).

Consider this (extreme) case:

This tree would force an lot of rotations, as the black nodes will keep moving down and creating a red-red collision upper in the tree.

I can only imagine that such a tree cannot effectively be built, so that this is not a situation that could feasibly arise?

Thanks

# Answer
> 2 votes
First of all, as pointed out in the comments, your tree is not a valid Red-Black tree. Here is why:

1. By definition, every path from the *root* of the tree to its leaves contains the exact same number of black nodes.
2. By definition, every red node has a black parent.

So, suppose you have a path with $n$ black nodes. How much longer can another path in this tree be? This other path has exactly $n$ black nodes too, so it can be longer only by having more red nodes. How many more? Well, you can add $n$ red nodes (in the alternating manner) to it (totalling $2n$ nodes) but as soon as you try to add $n + 1$ red nodes you are out of luck: some red node will have a red parent. Finally, this means that for any path in the tree there is no path that is more than twice as long.

Now, suppose you are looking at a subtree of a Red-Black tree. Also suppose that the root of this subtree is black (a formality). Then this subtree is also a Red-Black tree:

1. The root of the subtree is black (we chose it that way)
2. Every red node has a black parent (because it is so in the original tree)
3. Every path from the root of the subtree contains the same number of black nodes

The last statement is true because when we look at a subtree, we actually look at all the paths from the original tree that go through the root of the subtree. So, we essentially subtract the same number of black nodes which are above the root of the subtree.

Since the subtree is also a Red-Black tree, we already know that:

> for any path in the tree there is no path that is more than twice as long

Now look at your drawing, consider the subtree in the intermediate black node. It should be a Red-Black tree, yet it is not. There are at least two reasons:

1. There is a path (left-left) with one black node and there is a path (left-right-right-left) with two black nodes.
2. There is a path with $2$ nodes and there is a path with $5$ nodes and since $ 5 \> 2 * 2$ which breaks the height property.

---

Another mistake you are making: you are inserting a red node as a right child of a red node. This is the third insertion case according to wikipedia which triggers *color propagation* first, not a rotation. A rotation might or might not take place further up the tree.

---
Tags: binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Counting the number of tree when the set of the subtrees is given
There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the size of $A$. A brute-force way is making a graph of the trees. For each root node in $B$, find a tree that contains the node, if there exists such a tree, then make a link from the root node's tree to the containing tree. Finally I can obtain the number of trees in $A$ by counting the number of connected components in the graph. However, this may not be so efficient. How can I do it efficiently?

# Answer
You can't do it at all, let alone do it efficiently. Consider a tree $T$ and let its set of subtrees be $S$. If you're told $B=S$, the cardinality could be anything between $1$ and $|S|$, inclusive, because $A$ could be any subset of $S$ that contains $T$.
> 1 votes

# Answer
In addition to David's answer I wanna say that, if B was a **multiset** (meaning you can store several trees that are the same in that set) then you could do it by taking the biggest size tree in B and generating all it's subtrees and removing them from B, then taking the next biggest subtree in B (out of what's left) and doing the same thing until your multiset is empty.

All that can be efficiently achieved with a priority queue.

It's similar to this problem: codeforces.com/problemset/problem/582/A?locale=en .
> 1 votes

---
Tags: algorithms, trees, counting
---


# Question
Title: Can a functional language be homoiconic?
According to the wikipedia page on homoiconicity:

> In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself.

I was wondering if the lambda calculus was homoiconic (I assume not, because applications are not data (which, for the calculus, would mean variable or abstraction?)), and if not, what it would take to make it homoiconic (wrap all applications in an abstraction with a useless variable, a la `\a.b c`?).

But the more important question is this: If the only primitive data type in the language is the function, is it possible to achieve homoiconicity? (Does homoiconicity even make sense if all you have are functions?) If not, then is there some formal definition of what data-properties must be present in order to achieve homoiconicity?

# Answer
> 11 votes
The definition implies not only that programs are represented by a "primitive" datatype, but presumably also that it is possible to inspect the elements of this type, i.e., one can actually get at the code (otherwise I can just declare a primitive abstract type `code` and never let you look at it).

In general, the construct you are looking for is known as `quote`. It takes a piece of code (in $\lambda$-calculus or anywhere else) and returns its representation, either as an abstract syntax tree, a string, or just an integer (because integers can encode syntax trees). Of course, in the case of $\lambda$-calculus such trees, strings or numbers would be encoded in the usual way that we encode datastructures in $\lambda$-calculus.

It is known that having `quote` in general increases the expressive power of the language. For example, in $\lambda$-calculus we cannot implement the statement "all functions are continuous" but we can if we also have `quote` at our disposal (this is the essence of Kreisel-Lacombe-Shoenfield-Tseitin theorem).

The opposite of `quote` is `eval`, which many languages have. However, `eval` does not add to the expressive power of a language because it can be implemented within the language, assuming the language is general enough (`eval` is essentially an interpreter for the language).

It is worth mentioning that `quote` is an abstract way of making a programming language be a lot more like the Turing machine model (TM) of computation. In the TM model a piece of code is a Turing machine, and it is represented on the tape as a sequence of symbols, which is the only datatype that Turing machines know about.

**Note:** it is common knowledge that "all models of computation are equivalent". What this means is that they compute the same class of *functions from numbers to numbers $\mathtt{nat} \to \mathtt{nat}$*, but they are *not* equivalent when it comes to higher-order functions such as $(\mathtt{nat} \to \mathtt{nat}) \to \mathtt{nat}$.

---
Tags: programming-languages, lambda-calculus, functional-programming
---


title: Basic Myhill-Nerode Theorem Practice

text:
# Question
Title: Basic Myhill-Nerode Theorem Practice
I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so.

> L = (a $+$ b )

Clearly, this language is regular. So, I should be able to establish a finite number of equivalence classes by using this method.

I start with a suffix of length 0, which is only $\lambda$:

a$\lambda$ = a $\in$ L
b$\lambda$ = b $\in$ L

For all suffix strings of length $\nu \gt 0$, both are not elements of L. Therefore, there are no distinguishable strings. I suspect this means there are 0 equivalence classes, and since 0 is a finite number, the language is regular. What might be missing from this analysis?

Note: I made sure to do some online research already and feel comfortable with the ideas of distinguishable strings. The equivalence class bit is what I probably need some clarification on.

# Answer
> 2 votes
What you show is that $a$ and $b$ belong to the same equivalence class. Indeed, in this case there are exactly three equivalence classes: $\\{\lambda\\}$, $\\{a,b\\}$, and $\\{ w : |w| \geq 2 \\}$ (that's assuming the alphabet is $\\{a,b\\}$). I'll leave it as an exercise to prove that.

The Myhill–Nerode equivalence classes are intimately related to the minimal DFA. Indeed, given the minimal DFA, the number of equivalence classes equals the number of states, and each equivalence class consists of all strings which end up at that state. That's the quickest way to find the equivalence classes in simple cases such as $a+b$.

---
Tags: formal-languages, regular-languages
---


title: Size of Propositional Formula

text:
# Question
Title: Size of Propositional Formula
I am study this lecture The Complexity of Propositional Proofs. Here there is a term size of propositional formula (page 2),

> Every tautology $\tau$ on $n$ variables has an $F$-proof in which thera are at most $2^{O(n)}$ formulas, each of which has size polynomial in the size of $\tau$

but here doesn't define that term. I have googled this term and I have found something similar length of propositional formula, which is defined as

> The function $L(P)$ giving the length of a formula is defined by structural induction as follows:

* $L(p\_i) = 1$, for all atomic formulas $p\_i$
* $L(P ∧ Q)$ = 1 + $L(P ) + L(Q)$,
* $L(P ∨ Q) = 1 + L(P ) + L(Q)$,
* $L(¬P) = 1 + L(P)$.

My question is: Is the length and size of a formula the same?

# Answer
> 1 votes
There are two possible ways of defining what the *length* or *size* of the formula is:

1. According to the size of a reasonable (and fixed!) binary encoding.
2. According to the size of a reasonable (and fixed!) encoding over an infinite alphabet which includes symbols for all possible variables.

The definition you mention, for example, is what you get if you apply the second type of definition with respect to the prefix or postfix encoding of a formula.

Note that these two "approaches" don't by themselves defined a concrete measure of size. In cases where it matters, a concrete definition will appear, for example the one you quote. In many cases, however, the exact definition makes no difference since all definitions are "polynomially related", that is, the size of a formula varies at most polynomially between the different definitions. Your quote, for example, cares only about the size of the formulas being polynomial, and so an exact definition isn't important.

In other places, however, it is mentioned that some formula has size $O(n)$. Here the exact encoding still doesn't matter, but there is a real difference between the two options mentioned above. Consider for example the formula $x\_1 \lor \cdots \lor x\_n$. Under the second option, such a formula has size $\Theta(n)$. However, any reasonable binary encoding of this formula will have size $\Theta(n\log n)$, since storing the indices also takes space. From the author's statement it follows that he uses a definition of the second kind.

---
Tags: complexity-theory, logic, propositional-logic
---


# Question
Title: Non-deterministic algorithms and Tautologies
I am studying the lecture The Complexity of Propositional Proofs. Here there is a definition together with a discussion (page 3). I don't understand that discussion.

> Let $F$ denote the set of propositional formulas over the connectives $\wedge$, $\vee$, $\rightarrow$ and $\lnot$, with a countably infinite supply of propositional variables. An abstract propositional proof system is a polynomial time function $V: F \times \\{0,1\\}^\* \to \\{0,1\\}$ such that for every tautology $\tau$ there is a proof $P \in \\{0,1\\}^\*$ with $V(\tau, P) = 1$ and for every non-tautology $\tau$, for every $P$, $V(\tau, P)=0$. The size of the proof is $|P|$.
>
> Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies.

* Why does the author conclude "Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies."?

# Answer
An algorithm computing $V$ can be thought of as a non-deterministic algorithm which gets only the first parameter $\tau$ and guesses $P$, verifying that $P$ is a proof of $\tau$.

If you've ever seen the definition of NP using witnesses, in this definition $V$ is accepts the language of all tautologies $\tau$ with proofs in a certain proof system. The witness that such a proof exists is the proof itself $P$, and the function $V$ verifies that the proof is valid for $\tau$.

Another equivalent way of defining a proof system is as a polynomial time function which accepts a proof $P$ and outputs a proposition $\tau$. The two properties satisfied by such a system $S$ is (i) for all $P$, $S(P)$ is a tautology, (ii) for every tautology $\tau$ there exists a proof $P$ such that $S(P) = \tau$. It is an easy exercise to convert between the two definitions.

If you want to learn more, look up Cook–Reckhow proof system.
> 1 votes

---
Tags: logic, satisfiability, nondeterminism, propositional-logic
---


# Question
Title: Running an algorithm on data remotely and ensuring answer has not been tampered with
I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this problem belongs to exactly.

In a nutshell: person A has a list of data, another person (B) has an algorithm that gives each item on this list a score and then sums all these scores to provide an overall score for the whole list. How can we run the algorithm on the data list so that the data is kept extremely secure (preferably never leaving person A) but so that person B can be certain the algorithm ran properly and was not tampered with.

Here is an example: Anna and Bob live in a large village. Anna has a list on her computer of all the things she has done in the village, both good and bad. Bob has made a very simple scoring algorithm for such lists, which runs on each item on the list and gives it a score and then adds all these numbers up to give Anna a final score. This score lets Bob know how beneficial Anna is to the village community and is specific to Bobs opinion. (This is more than an example as this is actually the system I want to make)

However Anna does not want to give Bob her list, as then he has access to potentially embarrasing info in there (everyone has skeletons in thier closet). Bob however does not trust Anna to run his algorithms herself, as she may just lie and tell Bob the score was very high so that Bob is more likely to help her.

There are a few solutions I have already thought of, but all have problems:

A. Find a random person to take the data and run the algorithm and send the score back, but it may be difficult to ensure that this random person do not know Anna and try to help her or make a copy of the data and later try to trace it back and blackmail Anna.

B. Let Anna run the algorithm but somehow encode a check code into the scores, for example, instead of rating an event as 1 rate it as 1.0000000000797, in such a way that Bob can later use this as a checkcode to see if the given score is correct. However this check could also be misused by Bob to indicate what specific things Anna has done. Also I can imagine such a system would be trivial to reverse engineer so that Anna can give a false score with a correct checkcode, considering that Anna must have full access to Bob´s algorithm to run it.

C. The village creates a secure server to take such data and algorithms and run them together. However Anna and Bob both don´t really trust anyone enough to do this and not make a copy of the data or modify the scores, unless there is some fundamentally secure architecture for doing so. Also I would prefer this to be a P2P system.

# Answer
> 9 votes
In the crypto community, this task is known as **delegated computation**, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you some proof that it actually performed the computation (and didn't just output a random output, and ran away with your money).

A pointer, off the top of my head, is "Delegating computation: interactive proofs for muggles" (Goldwasser, Kalai, and Rothblum, J. ACM (62), 2015). Other solutions probably exist, look inside.

# Answer
> 1 votes
There is a new field of homomorphic encryption that generally fits your requirements:

> Homomorphic encryption is a form of encryption that allows computations to be carried out on ciphertext, thus generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext.

The processing entity cannot know "anything" about the cyphertext, it only appears as random data, it can only corrupt the computation, and the client needs some way to detect/ defend against corrupted data/ calculations. this can be done with message digests and fault tolerant computing.

Homomorphic encryption was only demonstrated as theoretically possible somewhat recently hence is more in conceptual stages and does not appear to be implemented much in practice so far, but eventually the idea is that it might show up as a capability (eg similar to other standard services like virtualization) on large standardized compute clusters eg Amazon ECC or google compute engine.

---
Tags: cryptography, security, protocols, encryption
---


title: Is log n! = Θ(n log n)?

text:
# Question
Title: Is log n! = Θ(n log n)?
Why is $\log(n!)=\Theta(n\log n)$?

I tried: $\log(n!) = \log1 + \dots + \log n \leq n \log n \Rightarrow \log(n!) = O(n \log n)$.

But how can we prove $\log(n!) = \Omega(n \log n)$ without Sterling's approximation?

# Answer
$$\begin{align\*} \log n! &=\sum\_{i=1}^n\log i \\ &\geq \sum\_{i=\lceil n/2\rceil}^n \log i \\ &\geq \sum\_{i=\lceil n/2\rceil}^n \log \tfrac{n}{2} \\ &\geq \tfrac{n}{2}\log \tfrac{n}{2} \\ &= \tfrac{n}{2}\big(\log n - \log 2)\\ &= \Omega(n\log n)\\,. \end{align\*}$$
> 13 votes

# Answer
For all integers $n$, if $n \geq 16$ then

$$ \begin{align\*} \log(n!) \\; & = \\; \log(1)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\ & \geq 0\hspace{.04 in}+\hspace{.04 in}...+\hspace{.04 in}0+\log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\; \\ & = \\; 0+\log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\ & = \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\; \\ & \geq \\; (1\hspace{-0.05 in}+\hspace{-0.02 in}n\hspace{-0.04 in}-\hspace{-0.05 in}\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \cdot \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \\ & = (1\hspace{-0.05 in}+\hspace{-0.05 in}\lceil n\hspace{.02 in}/\hspace{.02 in}2\rceil) \cdot \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \\; \\ & \geq \\; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}2)\hspace{-0.03 in}-\hspace{-0.04 in}(1\hspace{.02 in}/\hspace{.02 in}2)) \\ & = (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}(n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}-\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)) \\; \\ & \geq \\; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}-\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)) \\ & = (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}0) \\; = \\; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(n\hspace{.02 in}/\hspace{.02 in}4) \\; \\ & \geq \\; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(\sqrt n) \\; = \\; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log\hspace{-0.05 in}\left(\hspace{-0.02 in}n^{1/\hspace{.02 in}2}\hspace{-0.03 in}\right) \\ & = n\cdot (1\hspace{.02 in}/\hspace{.02 in}2) \cdot (1\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(n) \\; \\ & = \\; n\cdot (1\hspace{.02 in}/\hspace{.02 in}4) \cdot \log(n) \\; \\ & = \\; (1\hspace{.02 in}/\hspace{.02 in}4) \cdot n \cdot \log(n) \end{align\*} $$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Subset sum algorithms, their time complexity
The algorithm is in Python. Seems correct to me, ideas how to prove it? And what would be its time complexity?

```
from bisect import bisect

# Implements the decision version of subset sum.
# The subset sum problem: given a set and a number find a subset of the set which sums to the given number.
# Inputs: an ordered list of integers xs, and an integer n which is the target sum.
def subset_sum(xs, n):
    if n < sum(filter(lambda x: x < 0, xs)):
        return False
    if n > sum(filter(lambda x: x >= 0, xs)):
        return False
    xs = xs[:]
    u = {}
    def rec(i, n):
        if not (i, n) in u:
            u[i, n] = False
            k = bisect(sums[:i], n)
            while k > 0:
                k -= 1
                u[i, n] = u[i, n] or sums[k] == n
                u[i, n] = u[i, n] or rec(k, n - sums[k])
        return u[i, n]
    sums = xs
    return rec(len(sums), n)

```

It has been answered below that **the above algorithm is exponential time**.

That being so, I have a follow up question: Is the algorithm still exponential time if the rec sub-routine above is changed into the following?

```
def rec(i, n):
    if not (i, n) in u:
        u[i, n] = False
        k = bisect(sums[:i], n)
        k -= 1
        if k >= 0 and n >= sums[0]::
            u[i, n] = sums[k] == n or rec(k, n - sums[k]) or rec(k, n)
    return u[i, n]

```

The recurrence $T(i, n) = T(i - 1, n - 1) + log\_2(i)$ is what I came up with for worst case running time. Maybe that's far off. But from that it seems it is $|S|log(|S|)$.

New information: I have been able to solve a problem instance involving a set of 8192 integers equal to the range (1, 9, ... 65537) and the target n = 65525 in one and a half minute on my laptop. The resulting list consists of 125 integers. That makes the algorithm (with the above changes applied) sub-exponential, certainly not $2^{|S|}$ . The time taken is for the search version which applies the decision version discussed here $|S|$ times.

Here is a link to the full source code of my test set-up:

http://codepad.org/5s5lkHAm

# Answer
Your algorithm is very similar to exhaustive search. It is basically the following approach:

> In order to check whether some subset of $S$ sums to $n$, go over all $i \in S$ and check whether some subset of $S \setminus i$ sums to $n - i$.

The actual algorithm uses memoization and a few other optimizations. Its complexity is exponential in the size of $S$ (probably roughly $2^{|S|}$ in the worst case).
> 2 votes

# Answer
I think you are looking for a subset sum problem. This video explains a DP solution to the problem.

https://www.youtube.com/watch?v=s6FhG--P7z0
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: In principle, what is the relation between Artifical Intelligence and Turing machine?
I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a set of problems together and i am getting AI as: (the machine is 'programmed' on a certain algorithms to solve problems or to show intelligent behavior when solving a specific problem).

> Artifical Intelligence is usually defined as the science of making computers do things that require intelligence when done by humans.

On the other hand, Turing machine just manipulates data of {0 & 1} on a tape according to a table of rules to solve a problem {calculate the input}.

> A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

So, generally speaking both AI and Turing machines are meant to compute the input and transfer it to a right answer {output} so here is what iam confused about :

1. What a formal defination would relate both of them ?
2. Can i say that both algorithms of AI and a table of rules of a Turing machine are the same ?
3. Can i also say that AI is about choosing the best solution between different solutions to the input and turing machine just shows a solution of the input ?

# Answer
> 8 votes
Turing machines are a model of computation, one way of formally defining the concept of an *algorithm*. While Turing machines are usually defined using barebones input/output capabilities, it is not difficult to extend them so that they can apply to the kind of problems that AI is after.

The relation between AI and Turing machines is thus:

> Artificial intelligence is implemented by algorithms. Algorithms can be described by Turing machines.

Note, however, that Turing machines are not a great model for describing practical algorithms, since they work rather differently than actual machines, and as a consequence the *complexity* of algorithms is somewhat different when implemented in Turing machines compared to their real-world implementations. You should replace Turing machines with your favorite programming language.

Now I can answer your actual questions:

1) *What a formal definition would relate both of them?* Artificial intelligence is not a formal concept, so none.

2) *Can I say that both algorithms of AI and a table of rules of a Turing machine are the same?* Artificial intelligence is about algorithms performing some tasks, and Turing machines are a way of describing algorithms. So the answer to this question is positive.

3) *Can I also say that AI is about choosing the best solution between different solutions to the input and Turing machine just shows a \[sic\] solution of the input?* No, this is a false dichotomy. Algorithms implementing AI and algorithms implemented on Turing machines (with I/O) are exactly the same. There is absolutely no difference. Also, there is no such thing as a "best solution". So the answer to this question is negative.

---
Tags: turing-machines, artificial-intelligence, computation-models
---


# Question
Title: Confused about proof that $\log(n!) = \Theta(n \log n)$
So I was able to show that:

$\log(n!) = O(n\log n)$ without any problems.

My question is when trying to prove that $\log (n!) = \Omega(n\log n)$.

I was able to show that:
$$\begin{align\*} \log n! &= \log(1 \cdot 2 \cdot 3 \cdots n )\\ &= \log 1 + \log2 + \log3 + \dots + \log n \\ &= \log 1 + \dots + \log\tfrac{n}{2} + \dots + \log n\\ &\geq \log\tfrac{n}{2} + \log\big(\tfrac{n}{2} + 1\big) + \dots + \log n &&\text{(i.e., the larger half of the sum)}\\ &\geq \log\big(\tfrac{n}{2}\big) + \log\big(\tfrac{n}{2}\big) + \dots + \log\big(\tfrac{n}{2}\big)&&\text{(adding $\tfrac{n}2$ times)} \\ &= \log\big(\tfrac{n}{2} \cdot \tfrac{n}{2} \cdots \tfrac{n}{2}) &&\text{($\tfrac{n}{2}$ times)} \\ &= \log\Big(\tfrac{n}{2}^{\tfrac{n}{2}}\Big)\\ &= \tfrac{n}{2} log\big(\tfrac{n}{2}\big) &&\text{(by log exponent rule)} \end{align\*}$$

Thus, $\log(n!) \geq \tfrac{n}{2}\log\big(\tfrac{n}{2}\big)$, so we conclude that $\log(n!) = \Omega(n\log n)$.

I don't understand how finding the lower bound of $\log(n!)$ is found by getting the larger half of the sum. Why is that chosen to find $\Omega(n\log n)$? I feel like it's probably something obvious but it's the only thing keeping me from fully grasping the proof. If someone can enlighten me, I would appreciate it!

# Answer
Consider the sum $S = \log(1) + \dots + \log(n)$. We're going to break it into two parts: $S=T+U$, where

\begin{align\*} T &= \log(1) + \log(2) + \dots + \log(n/2)\\ U &= \log(n/2+1) + \dots + \log(n-1) + \log(n). \end{align\*}

Basically, $T$ has the first $n/2$ terms of $S$, and $U$ has the remaining $n/2$ terms.

Now we'll lower-bound each of them. Start with $T$. Each term in $T$ is at least $\log(1)$, so we get

$$T \ge \log(1) + \log(1) + \dots + \log(1) = 0 + 0 + \dots 0,$$

so $T \ge 0$. Next look at $U$. Each term in $U$ is at least $\log(n/2)$, so we get

$$U \ge \log(n/2) + \log(n/2) + \dots + \log(n/2) = (n/2) \times \log(n/2).$$

Now $S = T+U$, so plugging in the lower bounds obtained above, it follows that

$$S =T+U\ge 0 + (n/2) \times \log(n/2).$$

This is exactly the result you wanted to prove. Also, $(n/2) \times \log(n/2)$ is $\Omega(n \log n)$, so this proves that the sum $S$ is $\Omega(n \log n)$.
> 13 votes

# Answer
$\dfrac n2$ is chosen so that you have sufficiently many factors ($O(n)$) that are sufficiently large ($O(n)$), so that the product remains $\sim n^n$ while being a lower bound to $n!$
> 4 votes

# Answer
The intuition is that $\log x$ is slowly-growing, and consequently "most" of the terms will be around $\log n$ in size.

More precisely, if there are $\Theta(n)$ terms that are all $\Theta(\log n)$ in size, then their sum will indeed be $\Theta(n \log n)$ and we can conclude $\log n! \in \Omega(n \log n)$.

Taking half of the terms is merely the simplest idea to describe and calculate, and fortunately it satisfies the needed conditions.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Kleene algebra - powerset class vs class of all regular subsets
I am currently studying materials for my uni subject. There are two examples of Kleene algebras, but I don't see what is the difference between them.

* Class ${2^{\Sigma}}^{\*}$ of all subsets of $\Sigma^{\*}$ with constants $\emptyset$ and $\\{\varepsilon\\}$ and operations $\cup$, $\cdot$ and $\*$.
* Class of all regular subsets of $\Sigma^{\*}$ with constants $\emptyset$ and $\\{\varepsilon\\}$ and operations $\cup$, $\cdot$ and $\*$.

What is the difference between ${2^{\Sigma}}^{\*}$ and all regular subsets of $\Sigma^{\*}$? What is that difference I don't see? Thanks in advance.

# Answer
The difference between the two is that $2^{\Sigma^\*}$ contains *all* languages over $\Sigma$, whereas the class of all regular subsets of $\Sigma^\*$ contains only the *regular* languages over $\Sigma^\*$. So if $L$ is a non-regular language over $\Sigma$ then $L \in 2^{\Sigma^\*}$ while $L$ doesn't belong to the set of all regular languages over $\Sigma$. For any $\sigma \in \Sigma$, you can take $L = \\{ \sigma^{n^2} : n \geq 0 \\}$, for example.
> 0 votes

---
Tags: formal-languages, regular-languages
---


title: Set of all Languages

text:
# Question
Title: Set of all Languages
Sorry if the Question sounds a little trivial. Let A\* be the set of all languages over A={a,b}. Then A can be written as {aUb}\* which is a regular expression.So this is the set of all languages(actually set of all strings) regular.Am i thinking in the right direction.

# Answer
> 3 votes
You're almost there, but you need the right notation. Let's start with the alphabet $\Sigma = \\{a,b\\}$. Then the regular expression $(a+b)$ represents a set of two strings, namely $\\{a,b\\}$. The expression $(a+b)^2$ represents the set of the strings $\\{aa, ab, ba, bb\\}$. The expression $(a+b)^3 \ldots$ The expression $\\{a,b\\}^\*$, also denoted $\Sigma^\*$, represents the union of all these sets. Each of these sets is called a *language*, and so $\Sigma^\*$ is also a language. So $\Sigma^\*$ is *one* language, not the set of all languages, over the alphabet $\Sigma$, and it contains all the strings you can form out of that alphabet.

The set of all languages you can form using that alphabet is the *power set* of $\Sigma^\*$, denoted by $\mathcal{P}(\Sigma^\*) = \\{L | L \subseteq \Sigma^\*\\}$. That is, if $L$ contains only strings from your alphabet, then $L$ is a language over $\Sigma$, so $L$ is an element of the set $\mathcal{P}(\Sigma^\*)$. Now, some of these languages are regular, and some are not. Certainly the language $\Sigma^\*$ is a regular language, and $\emptyset$ is a regular language (you can draw their finite automata and see that they are the two simplest automata). Other languages, such as $\\{a^nb^m|n+m \text{ is prime}\\}$ are not regular. I hope that clears some things up.

---
Tags: regular-languages, regular-expressions
---


title: Remove Edge From Adjacency List

text:
# Question
Title: Remove Edge From Adjacency List
INPUT: weighted undirected graph in the form of adjacency list

OUTPUT: adjacency list without the edge e

Naive approach is:

```
for(int i = 0; i < adj.get(e.s).size(); i++) { // loop through adjacent of s
  if(adj.get(e.s).get(i).v == e.t) {           // find t and remove it
    adj.get(e.s).remove(i);
    break;
  }
}
for(int i = 0; i < adj.get(e.t).size(); i++) { // loop through adjacent of t
  if(adj.get(e.t).get(i).v == e.s) {           // find s and remove it
    adj.get(e.t).remove(i);
    break;
  }
}
O(k) - k is number of adjacent vertices

```

A faster approach is to use adjacencyMatrix but my algorithm has alot of traversals involved and looping through each dimension in the adjMat costs more despite a O(1) edge removal.

**How can I speed up removing an edge? (used in generating a MST (kruskal))**

# Answer
I didn't realize what is your problem with Kruskal algorithm. To me, a usual Kruskal has time complexity $O(E \ log E)$ that $E$ is the number of edges in a graph, and I don't have any difficulty to ignore those edges which make a cycle.

To answer you question, all adjacency lists, maintaining adjacent vertices, can be sorted in an ascending order. Then, you can find the position of each adjacent node with $O(log N)$, where $N$ is the number of vertices.

You should also define two one-dimensional arrays, $nex$ and $pre$ for each adjacency list, where $nex$ maintains the position of next vertex in an adjacency list, and $pre$ holds the previous position.

When edge $e = (a, b)$ is about to be removed, the position of $b$ in the adjacency list of $a$ can be found with $O (log \ N)$.

Then, do two following steps to remove $a \to b$:

* $nex \[ \ pre \[b\] \ \] = nex \[b\]$
* $pre \[ \ nex \[b\] \ \] = pre \[b\]$

Do it also in the adjacency list of $b$ to remove $b \to a$.

If you want to traverse in an adjacency list, the next index can be reached by the means of $nex$ array.

*To traverse an adjacency list from the beginning a random value, as a dump, can be utilized since the first node might be removed.*
> 1 votes

---
Tags: graphs, minimum-spanning-tree, adjacency-matrix
---


# Question
Title: How do I get the solution for a recursion with n! using Master Theorem?
The problem in my book is T(n) = 16T(n/4) + n!

I don't know how to get at the correct solution my book has, which says Θ(n!)

here are pictures of the master theorem and the problem in my book.

# Answer
> 1 votes
Suppose for simplicity that we only consider $n = 4^k$, and that $T(1) = 1$.

Let us guess that $T(n) \leq Cn!$ (where $C\>0$), and try to prove it by induction. For the inductive step we need $$ 16C(n/4)! + n! \leq Cn!, $$ that is, $$ 16C(n/4)! \leq (C-1)n!. $$ For the base case we need $C \geq 1$.

Let us write the inductive constraint for $n = 4$: $$ 16C \leq 24(C-1) \Longrightarrow C \geq 3. $$ This prompts us to choose $C = 3$. For $n \geq 4$ we then need $$ 48 (n/4)! \leq 2n! \Longleftrightarrow \frac{n!}{(n/4)!} \geq 24. $$ It is easy to check that this always holds – for $n = 16$ it's a simple computation, and for $n \geq 64$ we have $n!/(n/4)! \geq n \> 24$.

---

Intuitively, what is happening here is that $(n/4)!$ is much much smaller than $n!$, and so $T(n) \approx n!$, since all other summands (which you see if you unroll the recursion) are so much smaller.

---
Tags: master-theorem
---


# Question
Title: How do you apply a multi qubit gate to specific qubits in a multi qubit circuit?
Let's say that you have a 6 qubit system and you want to apply a Hadamard gate to qubits 2 and 4.

How would you construct a matrix that did that, while leaving the state of the other qubits alone?

# Answer
> 3 votes
Imagine that the qubits were $0$ and $1$ (or $1$ and $2$, depending on your numbering scheme). You want to apply the Hadamard gate on the first two coordinates, and nothing – the identity – on the rest. This leads to a block diagonal matrix whose second block is the $4\times 4$ identity.

Now make the necessary arrangements for the qubits you're interesting it.

---
Tags: quantum-computing
---


title: Is this language semidecidable?

text:
# Question
Title: Is this language semidecidable?
I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following .

---

If $L\_1$ is semidecidable and $L\_2$ is decidable, what can one say about the language set defined by their difference $L\_3 = L\_1 \text{ \ }L\_2$ ?

---

I'm inclined to believ that $L\_3$ is semidecidable, but I can't think of a way to prove it.

Any ideas?

# Answer
> 1 votes
If $L\_1$ is semidecidable, there's a TM $M\_1$ that takes a string $x$ and always reliably halts and answers "yes" if $x\in L\_1$. If $L\_2$ is decidable, there's a TM $M\_2$ that always halts and reliably answers "yes" if $x\in L\_2$ and "no" if $x\notin L\_2$.

Make a new machine $M$ that when given an input string $x$ first runs $M\_2(x)$. If the answer is "yes" then you know $x\notin L\_1\setminus L\_2$ so have $M$ halt and answer "no". If, on the other hand, $M\_2(x) = "no"$ then $x$ may or may not be in $L\_1\setminus L\_2$, so then run $M\_1(x)$ and do whatever $M\_1$ does. It may never halt or it may answer "no", but if $x\in L\_1\setminus L\_2$ your $M$ will correctly answer "yes", proving that $L\_1\setminus L\_2$ is indeed semidecidable.

---
Tags: formal-languages, semi-decidability
---


title: Can OR be "undone"?

text:
# Question
Title: Can OR be "undone"?
Suppose that $Z = X \vee Y$, where $X$, $Y$ and $Z$ are 96-bit binary numbers. If I'm given the values of $Z$ and $Y$, is it possible to work out what $X$ is?

I know this is possible with XOR but can it be done with OR?

# Answer
> 7 votes
It is easy to find out that there can be more than one value, used as $X$, to satisfy $Z = X \vee Y$. When a specific bit of $Y$ is $1$, there are two possibilities for such bit in $X$, i.e., $0$ or $1$.

Let's make a simple example with a 2-bit number:

$Y$ = $10$ and $Z$ = $11$

The possible values of $X$ are:

* $11$
* $01$

because:

* $11 \vee 10 = 11$
* $01 \vee 10 = 11$

In short, you don't have the certainty that the end result of the reverse operation of $\vee$ will be a unique result.

---
Tags: logic
---


# Question
Title: How to revert a carryless polynomial multiplication?
In the carryless multiplication of two polynomials in a 8-bit environment, is it possible to obtain the original 8-bit values from the result?

As an example:

$$\begin{align} (x^{11} + x^{10} + x^9 ) + (x^7 + x^5 + x^4 + x^3 + x^1) &= (x^6 + x^5 + x^1) \times (x^5 + x^3 + x^2 + x^0)\\ (x^{11} + x^{10}) + (x^6 + x^4 + x^2 + x^1) &= \text?\times\text?\quad \hbox{(each value must fit in 8 bits)} \end{align}$$

I know that I can try every possible value (it's only two 8-bit values) but that seems blunt!

# Answer
> 2 votes
Yes, there are efficient algorithms for this. All you need to do is factor the resulting polynomial, but taking all coefficients modulo 2. This is known as polynomial factorization in the field $GF(2)$. There are standard algorithms for polynomial factorization, and they are quite efficient. For instance, you could look at Sage or another mathematical computation toolkit; it's likely to have an existing implementation of those algorithms.

Note that after you've factored the polynomial, there may still be some ambiguity about what the original two polynomials were. For instance, if you are given the polynomial $x^5+x^3$, the two polynomials might be $x^2+1$ and $x^3$, or they might be $x^3+x$ and $x^2$, etc. You won't be able to tell, given just the product.

---
Tags: algorithms, arithmetic, polynomials, encryption
---


# Question
Title: If we sort a table column-wise and then row-wise why the table is still sorted column-wise?
Say we have a $n \times n$ table which elements are sorted column-wise, for example:

$$ \left( \begin{array}{ccc} 2 & 4 & 1 \\ 3 & 5 & 6 \\ 7 & 9 & 8 \end{array} \right) $$

I would like to prove that if we sort this table row-wise, it will be still sorted column-wise.

---

*This is one of the steps to prove the shell sort correctness.*

# Answer
> 4 votes
Consider some column $i$ and some rows $j \< k$. Let $x$ be the element at row $j$ column $i$ after the final sorting, and let $y$ be the element at row $k$ column $i$. We want to prove that $x \leq y$.

Since $x$ ended up in column $i$, there must have been $n-i$ elements in row $j$ larger than $x$. Together with $x$ itself, these are $n-i+1$ elements in row $j$ that were at least as large as $x$. The corresponding elements in row $k$ were also at least as large as $x$, since the columns were sorted. Summarizing, row $k$ contains at least $n-i+1$ elements which are at least as large as $x$. That means that after sorting, the element at position $i$ on row $k$ (that is, $y$) is at least as large as $x$

---
Tags: algorithms, sorting, correctness-proof
---


title: How to prove membership of NP

text:
# Question
Title: How to prove membership of NP
My tutor often says that proving membership of **NP** is the easy part of proving that a problem is **NP**-complete, and that this should only take a minute. What I don't understand is what exactly you're suppose to do at this step I understand that you're suppose to verify the correctness of a solution but how do I do that?

# Answer
> 0 votes
Here are several examples:

1. MAX-CLIQUE: The witness is a set of vertices of given size. The verifier checks that edges connect all pairs of vertices in the set.
2. SAT: The witness is a satisfying assignment. The verifier checks that it satisfies all clauses in the formula.
3. 3COL: The witness is a 3-coloring of the graph. The verifier checks that all edges connect vertices of different color.
4. SUBSET-SUM: The witness is a subset of the set. The verifier checks that the subset sums to the target number.

---
Tags: algorithms, np-complete, complexity-classes, np
---


# Question
Title: Can input to a Turing machine be of infinite length?
Considering only the alphabet $\Sigma = \\{0,1\\}$, the strings which can be given as input to the Turing machines are from the set $\Sigma^{\*}$. But does it make sense for the input to be an infinite binary string ? For example if a Turing machine accepts all strings starting with a 0, does a binary string of infinite zeros also belong to the language accepted by the Turing machine ?

# Answer
There is no problem in running a Turing machine on a tape initialized with an infinite string, although this is not usually considered. We still need the machine to terminate in finite time, though. There are also notions of infinite-time computation, which may be appropriate here.
> 22 votes

# Answer
That's one of the features of Type 2 Turing Machines. They're used, among other things, to analyse the computability of functions between real numbers. Even more interestingly, they're used to analyse the computability of operators like integration.

Cool fact: Exact numerical integration is computable.
> 17 votes

# Answer
To answer the question "does it make sense", this can even be useful if you consider Turing machines that run in finite time.

Specifically, this is a very useful way to think of **prefix-free Turing machines**. These are machines whose set of halting inputs is prefix-free; that is, no input that causes the machine to halt is the prefix of another. These are equivalent in power to regular Turing machines, but only if we allow the Turing machine to decide its own halting inputs: ie. the user has no idea what inputs the machine will halt on (and this is an undecidable property).

One way to see this is as a regular Turing machine with a one-way infinite input tape with a tape head that can't move back. The user fills the tape with bits and runs the machine. This is by definition a prefix-free Turing machine. If the machine halts, it must have read only a finite number of bits, and no prefix of that part of the tape can be a program, or the machine would have halted there instead.

This is a good way to talk about computable probability distributions: the user fills the tape with random bits (the machine's source of randomness), and the machine spits out a random bitstring. The set of all such Turing machines corresponds to the set of computable distributions (specifically the lower semicomputable semimeasures).

The advantage of the infinite input is that we don't have to specify what the machine does if we give it a prefix of a halting program, ie. the machine tries to read beyond the end of the input we've given it.
> 5 votes

# Answer
Even if you do not have such a tape, you can employ another Turing machine to produce it.

A Turing machine has an access to the empty, but infinite data tape (or some sources says "the machine just has a small tape factory built in"). So it can initialize it with some programmable pattern of data, and then the tape could be consumed as an input of another Turing machine.

Of course, if your content is such that no algorithm could be defined how to produce it, such content cannot be created by Turing machine.
> 3 votes

# Answer
There are some cases where infinite input can be considered and reduced to the action of a "standard" Turing machine. For example, consider an infinitely repeating finite pattern specified on the input. A Turing machine can be created that keeps track of how much of this infinite pattern has been modified by the current actions of the tape head using a finite amount of memory/ tape storage. In other words, it "equivalently simulates" an infinite size pattern on the tape.

Another case where "infinite input" has been considered is the analysis of the Turing equivalence/ completeness of cellular automata. in a complex proof, Cook introduced a concept now referred to by some as "weak Turing equivalence" in converting CA 110 rule operations into Turing machine operations that start on an infinite-specified initial tape but with (repeating) finite-size patterns.
> 2 votes

# Answer
In formal languages, a string is, by definition, a **finite** sequence of symbols. A classic Turing Machine has an infinite tape with a finite input string. As such, while there is no limit to how long the input can be, it cannot be infinite.

Having said that, there are many alternative machines that work similarly to a TM but with infinite input sequences.

Whether it makes sense to have input of infinite length depends on the purpose. Strictly within the context of Turing Machines, it makes no sense (since it is not possible), but in the context of Turing-like Machines, it does make sense and it has many applications.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How to prove closure property of regular languages using regular expressions?
I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular expressions, specifically proving that reversal of a regular language is closed using regular expression?

# Answer
> 4 votes
You can prove it using this approach:

if $E$ is a regular expression then you can recursively define its reverse in this way:

* if $E = \emptyset$ then $E^R = \emptyset$
* if $E= (E\_1)$ then $E^R = (E^R\_1)$
* if $E = a \in \Sigma$ then $E^R = a$
* if $E = E\_1 \cdot E\_2$ then $E^R = E^R\_2 \cdot E^R\_1$
* if $E = E\_1 \cup E\_2$ then $E^R = E^R\_1 \cup E^R\_2$
* if $E = E\_1^\*$ then $E^R = E^{R\\,\*}\_1$

You can prove that each "step" is correct and after a finite amount of transformations the procedure ends. At the end you get a regular expression (recursively built from $E$) that defines $E^R$.

---
Tags: formal-languages, regular-languages, proof-techniques, regular-expressions, closure-properties
---


title: Sorting an array of boolean values

text:
# Question
Title: Sorting an array of boolean values
im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues.

so if given this: a = {true, true, false, true, false}

it would return: a = {false, false, true, true, true}

here is the exact question: Suppose you have an array of booleans of size n. Give an algorithm that sorts the array so that all false elements come before all true elements.

Thanks for any help you can give me!

# Answer
> 6 votes
With only 2 possible values, you want to use an algorithm such as Counting Sort.

Since you only have 2 possible values, true and false, it's easy to just count how many true/false values you have. But to be more efficient, you can just count how many trues you have (or falses) instead. Because size - numTrue = numFalse.

# Answer
> 4 votes
You can do this in linear time.

Algo:
1. Initialize an another array of same size(`n`) lets name it `A[n]`.
1a. countF = 1 and countT = 1
2. Loop over elements with `i` going from `1:n` on the original array lets name it `B`:
2a. If B\[i\] = false, then A\[countF\] = false and increment `countF`
2b. If B\[i\] = true, then A\[n-countT + 1\] = true and increment `countT`
3.END

And in the array `A`, you have the answer. Here, its done in one scan but with a space overhead of `n`

Note another way, would to scan over the array and count the number of `False` and `True`. And on another run over the array you put `False` from starting to the count of `False` in original array and `True` in the remaining places. This method requires two runs over the array but with no overhead of spaces.

---
Tags: algorithms, sorting
---


title: 3-SAT for variables appearing 3 times

text:
# Question
Title: 3-SAT for variables appearing 3 times
I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity.

For example, https://people.maths.ox.ac.uk/scott/Papers/restricted3sat.pdf says

> instances of 3-SAT in which every variable occurs three times are always satisfiable (this is an immediate corollary of Hall’s Theorem), while it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times

so apparently when variables appear 3 times it's an easy problem (?).

But the following two references seem to say something else:

From here, http://www.csie.ntu.edu.tw/~lyuu/complexity/2008a/20080403.pdf,

> 3sat is NP-complete for expressions in which each variable is restricted to appear at most three times, and each literal at most twice.

and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.319.8796&rep=rep1&type=pdf Lemma 5:

> The SAT-3 problem is NP-complete even when each variable appears 3 times.

So is this problem NP-complete for when variables appear 3 times or 4 times? I'm pretty confused.

# Answer
> 9 votes
There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.

> Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable.
>
> \[...\]
>
> **Theorem 2.1.** Boolean satisfiability is NP-complete when restricted to instances with *2 or 3* variables per clause and at most 3 occurrences per variable.
>
> \[...\]
>
> **Theorem 2.4.** Every instance of r,r-SAT is satisfiable.

The reason there's no conflict is that you need to allow 2 *or* 3 literals per clause to make 3-SAT $NP$-complete when restricted to at most 3 occurrences per variable. The trivially satisfiable bit only kicks in when you have exactly 3 literals per clause and at most 3 occurrences per variable.

---
Tags: np-complete, 3-sat
---


# Question
Title: Using closure properties to show that $a^n b^m a^{n+m}$ is not regular
I want to show that $L = \\{a^n b^m a^{n+m} \mid n, m \geq 0\\}$ is not regular.

Can I say that the complement of $L$ intersected with $a^\*b^\*$ equals $\\{a^n b^n \mid n \geq 0\\}$ and since I know that $\\{a^n b^n \mid n \geq 0\\}$ is not regular, then $L$ is not regular?

Or would I have to use the pumping lemma?

# Answer
That line of reasoning can work in principle; you are trying to use closure properties of REG for a proof of contradiction. Make sure you understand that that's what you're doing.

Unfortunately, you do not get $\\{a^nb^n\\}$. For instance, $a^3 b^4 \in \overline{L} \cap a^\*b^\*$. Check out our reference question for more techniques you can try.
> 2 votes

# Answer
**Hint:** What do you get when you intersect $L$ with the language denoted by $b^\*a^\*$? It won't be quite what you need, but it's close. You can then get the $b^ma^m$ language by subtracting (i.e., set difference) some regular language from that.
> 2 votes

---
Tags: formal-languages, pumping-lemma
---