# Question
Title: Delete a range of keys in a binary search tree in better than $O(n\lg n)$?
Obviously, the brute force method of:

```
DeleteRange(root, low, high)
    for n = low to high
        if n == root.key // key found
            return DeleteNode(root) // O(lg n) to delete
        elseif n < root.key // in left sub-tree
            root.left = DeleteRange(root.left, n, high) // recur into left sub-tree
        elseif n > root.key // in right sub-tree
            root.right = DeleteRange(root.right, n, high) // recur into right sub-tree
        else // root.key == null, key not found
            return null
   return root

```

would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.

# Answer
> 4 votes
You might be interested in a data structure called TeardownTree. It supports `delete_range` operation that works in $O(k + \log n)$ time, where $n$ is the initial number of items in the tree and $k$ is the number of items deleted (and returned to the caller). Full disclosure: I am the author.

I have to emphasize that the data structure does not support the `insert` operation, but is optimized for `clone` and `delete_range`. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.

---
Tags: algorithms, binary-trees, search-trees
---


# Question
Title: Blocking because of concurrency correctness condition
I am confused about a statement in *The Art of Multiprocessor Programming*:

> Theorem 3.6.2: Let `inv(m)` be an invocation of a total method. If `<x inv P>` is a pending invocation in a linearizable history `H`, then there exists a response `<x res P>` such that `H · <x res P>` is linearizable.
>
> ...
>
> This theorem implies that linearizability by itself never forces a thread with a pending invocation of a total method to block.

(*The Art of Multiprocessor Programming*, Herlihy & Shavit, 2008 Edition, page 58)

I understand that partial methods might need to block for correctness reasons. For example, it is reasonable to block a dequeue operation until there are elements to remove.

However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?

Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

# Answer
> 2 votes
For your first question

> *Q:* However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

> *A:* Serializability is inherently a blocking property: under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

```
x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

```

> Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.

---

For your second question

> *Q:* Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

*A:* An operation is blocked in a history if its `invocation` event has no matching `response` event.

I am not able to answer the question "Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?". My opinion is that it may or may not cause effects in the history. It is non-deterministic.

---
Tags: concurrency
---


# Question
Title: Associativity vs blocks per set in fixed size caches
I am trying to understand the following claim:

> For a fixed size cache, each increase by a factor of two in associativity doubles the number of blocks per set (i.e., the number or ways) and halves the number of sets – decreases the size of the index by 1 bit and increases the size of the tag by 1 bit.

I am just wondering if someone can clear this up for me. For example, if there is a cache with 16 cachelines and it's 2-associative the number of blocks per set is 8, but if we increase by a factor of two associativity then the number of blocks per set decreases to 4.

# Answer
> 1 votes
Actually he was referring about the blocks that can be placed in the cache from the Main memory. from your example 16 cache lines - 2 way set associative | assuming 32 blocks in Main Memory

so there are 8 blocks per set so each set will have 32/8 = 4 blocks now, made into a 4 way set associative | same 32 blocks of main memory

so there are 4 blocks per set so each set will have 32/4 = 8 blocks they are doubled so you need 1 more bit to represent it by having same tag but appending it with 1 or 0 at the front

Similarly the sets are getting halved, i think you got that part

# Answer
> 1 votes
The number of sets determines the size of the index, because the index tells you what set to refer to. If you increase associativity by giving more blocks to each set then you run out of blocks sooner and so you can afford fewer sets. If you have fewer sets then you have a smaller index.

If half the sets disappear then those addresses have to be handled by the remaining sets. Because each set now has more addresses that it serves, it needs an extra bit of tag to distinguish them.

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Does mutual exclusion hold in this case?
I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds:

Consider two processes:

> $s\_1$ and $s\_2$ are two variables, set equal initially.
>
> P1:
>
> 1. while $s\_1 = s\_2$: wait.
> 2. /*execute critical section*/
> 3. $s\_1$ is set such that it is not equal to $s\_2$
>
> P2:
>
> 1. while $s\_1 = s\_2$: wait.
> 2. /*execute critical section*/
> 3. $s\_1$ is set such that it is not equal to $s\_2$

My friend argues that mutual exclusion holds. His explanation:

> Mutual Exclusion holds if the following implication holds: If a process is in its critical section, then other processes should not be allowed in their critical sections.

Consider this implication as $P \to Q$. He argues that since the premise $P$ is wrong (because none of P1 and P2 are in their critical sections), the implication is true and hence mutual exclusion holds.

Whereas my thinking is that when none of the processes get to enter their critical section, talking about mutual exclusion is pointless and hence the property doesn't hold.

Is the implication way of thinking the correct approach? I feel that it's not, but I have not been able to prove my intuition.

# Answer
Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.

You state that you feel that this interpretation is wrong, but you have not been able to prove your intuition. *You cannot prove a definition!* What you are really saying is that the concept of mutual exclusion is vacuous if no process is ever in a critical section. To some extent you are correct—this agrees with colloquial usage. The same colloquial usage also states that "A or B" has the connotation of "A or B, but not both". When dealing with formal concepts you have to forgo the colloquial point of view, trading it with the mathematical point of view.
> 7 votes

# Answer
A mutual exclusion solution should satisfy not only the mutual exclusion property but also *the deadlock property*. Deadlock occurs when one or more processes are "trying to enter" their critical sections, but no process ever does. See Lamport@JACM'86; Page 6.

Although the algorithm you describe trivially satisfies the mutual exclusion property (and the implication proof of your friend is correct), it does not satisfy the deadlock property. Thus, strictly speaking, this algorithm is *not* a sensible mutual exclusion solution.
> 4 votes

---
Tags: operating-systems, concurrency, propositional-logic, mutual-exclusion
---


# Question
Title: Least number of comparisons to identify 6 numbers with values from 1 to 6 (without repetition)
Variabled $x\_1, \dots, x\_6$ have hidden, distinct integer values from \[$1,\dots,6$\]. How to identify each variable's value with minimum number of comparison operations?

# Answer
> 1 votes
According to Wikipedia, the minimum number of comparisons needed to sort 6 numbers is 10. The lower bound follows from the usual decision tree argument.

---
Tags: algorithms, sorting
---


# Question
Title: Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$
I am trying to implement a context-free grammar for $L=\\{a^n b^m \mid n \neq 2m\\}$.

I have a difficulty trying to implement it because I don't know how to ensure that $n \neq 2m$.

I can easily implement $n=2m$ but the other way around doesn't seem intuitive. How can I approach this problem?

# Answer
*Hint:* A string of the form $a^nb^m$ where $n \neq 2m$ can be either

* A string with too many $a$'s, or
* A string with too few $a$'s

Create production rules for each of these cases.
> 2 votes

---
Tags: context-free
---


title: Example of a direct-mapped cache

text:
# Question
Title: Example of a direct-mapped cache
Please can any one describe this picture? I am not getting that 4 entries to 001.

# Answer
> 1 votes
There are 8 blocks in cache which are represented as (000,001,...111 ) There are 32 blocks in Memory which are represented as (00000,00001,...11111) So in Direct Mapped cache the 0 th block will have all the entries of main memory where 0,8,16,24 this is by 0 mod 8 = 8 mod 8= 16 mod 8 = 24 mod 8 =0

Here the entries will be for 1 th block of a cache (001) will have entries of main memory where 1,9,17,25 this is by 1 mod 8 = 9 mod 8= 17 mod 8 = 25 mod 8 =1

---
Tags: computer-architecture
---


# Question
Title: Why deadlock in cigarette smokers problem
"The Little Book of Semaphores" (2nd Ed. by Allen B. Downey, section 4.5.1) as well as Wiki (link) mentioned that a trivial solution (as shown below) to the 'Cigarette smokers problem' will cause a deadlock. Somehow I couldn't wrap my head around it. Pls help me undersatnd how deadlock can occur for the below solution. P.S. We assumed agent code cannot be modified and We're free to use semaphores and other variables as needed

Code sample (*from the book*):

```
     Agent A                 Agent B          Agent C
1 agentSem.wait()     agentSem.wait()      agentSem.wait()
2 tobacco.signal()    paper.signal()       tobacco.signal()
3 paper.signal()      match.signal()       match.signal()

     Smoker I           Smoker II               Smoker III
1 tobacco.wait()       paper.wait()           tobacco.wait()
2 paper.wait()         match.wait()           match.wait()
3 agentSem.signal()    agentSem.signal()      agentSem.signal()

    Assume semaphores 'tobacco', 'paper', and 'match' are  initialized with
    zero, and 'agentSem' is initialized with one.

```

# Answer
> 4 votes
Agent A consumes agentSem, and produces tobacco and paper.

That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco.

Now, all the smokers are stuck, and the agents as well.

---
Tags: concurrency, deadlocks
---


title: Eliminate left recursion from grammar

text:
# Question
Title: Eliminate left recursion from grammar
Consider the following grammar:

$$ A\to Ba|Aa|c \\ B\to Bb|Ab|d $$

How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?

I have tried applying the rule which converts $A \to A\alpha|\beta$ to $A \to \beta A'$ and $A' \to \alpha A'$:

* For $A \to Ba|Aa|c$, $\beta = Ba|c$ and $\alpha = a$.
* For $B \to Bb|Ab|d$, $\beta = Ab|d$ and $\alpha = b$.

In this way I eliminate direct recursion from each one, but then when I try to substitute A or B with its product and eliminate indirect left recursion, the parsing table finds collisions so the grammar is not LL(1). Any ideas?

# Answer
Mutual recusive definitions are tricky to eliminate. You'll have to work with the unwieldy expanded form of one of the rules. Here, let's expand $B$ \begin{align\*} B &\to Bb \mid Ab \mid d \\ & \to (Bb \mid Ab \mid d)b \mid Ab \mid d \\ &\to ((Bb \mid Ab \mid d)b \mid Ab \mid d)b\mid Ab \mid d \\ & \to ~\cdots \\ &\to (d \mid Ab) \mid (db \mid Abb) \mid (dbb \mid Abbb) \mid \cdots \\ &\to (d \mid Ab)b^\* \end{align\*} In general, $B \to B(x\_0 \mid x\_1 \mid \dots) \mid (y\_0 \mid y\_1 \mid \dots)$ will have an expanded form of $B \to y\cdot x^\*$. Things get even more complicated if $B \to z B x \mid y$ and $z$ is nullable. But let's not worry about that just yet, instead, let's turn our attention back to $B$.

Now, notice that I have used the term $b^\*$, this is actually just the nonterminal $b^\* \to \epsilon \mid b b^\*$; this is a standard trick that many "extended" BNF based parsers use as well.

Finally, we can inline $B$ into $A$ to get \begin{align\*} A &\to Ba \mid Aa \mid c \\ &\to db^\* a \mid Abb^\*a \mid Aa \mid c \\ &\to (c \mid db^\*a)(bb^\*a \mid a)^\* \end{align\*}

where once again $(bb^\*a \mid a)^\* \to \epsilon \mid (bb^\*a \mid a)(bb^\*a \mid a)^\*$.

Now, if all you need is $A$, then this is already fine and dandy. However, if you need to expose $B$ as a public method as well, then you'll notice that there is a slight hitch: $\text{follow}((bb^\*a \mid a)^\*) = \text{follow}(A) = b$, since $B \to Abb\*$. But since $\text{first}((bb^\*a \mid a)^\*)$ also contains $b$, then we can't decide whether we should shift to $\epsilon$ or $bb^\*a$ when we encounter a $b$. You might try to inline $A$, so that $$ B \to (d \mid (c \mid db^\*a)(bb^\*a \mid a)^\*b)b^\* $$ but you still have the same problem. Now you can reason that $(bb^\*a \mid a)^\*bb^\* = b^\*(ab^\*)^\*$, but this is not very generalizable, and it breaks down fast when your language takes a step out of its regular territory. Instead, you'll want to start from the beginning. Expand $A$ first, and inline into $B$.
> 1 votes

---
Tags: formal-languages, context-free, formal-grammars, parsers
---


title: Optimal way for the remainder

text:
# Question
Title: Optimal way for the remainder
I want to know if for any base the most significant digit is 1 or not. Here is the code:

```
for(int i=3;i<=a;i++)
  {
    int x = i;
    int r = a;
    while(r/x)
    {
      r = r/x;
    }
    int rem = r%x;
    if(r==1)
    {
      count++;
    }
  }

```

is there any optimal way to replace the while loop nested in the for loop.

# Answer
You would pick some number a, run the code, and see if you can find a pattern. There will be an obvious pattern. Then you think how you can use that pattern to find long ranges of numbers i where r ends up being 1, and long ranges where r does not end up being 1.

When you've done that, all you do is add up the number of values in those ranges of values i that end up being 1.

The best way unless you are a super genius (in which case you wouldn't be asking here) is to play around with the code, figure out its behaviour, and think about ways to take shortcuts.
> 2 votes

---
Tags: algorithms, discrete-mathematics, number-theory, base-conversion
---


# Question
Title: What we lack to do automatic programming?
From time to time I am trying to implement automatic programming system. We already have the formalization of norms (laws/legislation, business policies and rules) as some kind of deontic logic (there have been endeavours to convert deontic logic formulae into executable rules). We have ontology of GUI elements. So - we have specification. But how to convert this specification into executable code? What we lack to do automatic programming at least in the domain of business software (that is specified by legislation and enterprise rules)?

# Answer
> 3 votes
> We already have the formalization of norms

I don't think we do. Norms are written in natural languages (e.g. English). And truly understanding text written in a natural language (even a subset of it, such as the one used to write norms) is still not something that can be done.

Even if you solved that, business policies and rules usually aren't detailed enough to directly create useful programs out of them. That's another hurdle that's not going to be easy to cross.

---
Tags: programming-languages, software-engineering
---


# Question
Title: Iteratively find and modify a certain element in a set in $\log n$ per iteration
I've looked around and can't find my answer.

I have a set of $n$ numbers. In each iteration I would like to find an arbitrary number and change it. Is it possible to perform each iteration in $\log n$ time?

There are data structures like a min-max heap which allow insertion and deletion in $\log n$ time, but that only allows deletion on the min/max values.

# Answer
> 1 votes
Yes, you can achieve that running time if you use the right data structure. You might want to look at some other data structures, such as AVL trees, red-black trees, or other similar techniques. See, e.g., https://en.wikipedia.org/wiki/Search\_data\_structure, https://en.wikipedia.org/wiki/Self-balancing\_binary\_search\_tree, or your favorite data structures book.

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: Is finding arbitrary-but-fixed length cycles in a graph NP-Hard?
My intuition says yes. I think so because if we could find arbitrary length cycles, couldn't we just look for an n length cycle and then solve **HAM-CYCLE**? But I saw a post that seems to suggest a polynomial time method for finding cycles! I feel as if perhaps I do not understand something here.

# Answer
> 4 votes
The algorithms mentioned are all fixed-parameter tractable in the size of the cycle. This means that if you fix the cycle size $k$, there's a polynomial time algorithm for finding the cycle as the number of vertices or edges increases, but the run time still increases exponentially as $k$ increases. The big-O notation you're looking at only specifies asymptotic run times as the number of edge and vertices increase, but leaves out the possibly large but constant $k!$ factor.

---
Tags: graphs, np
---


# Question
Title: Determining if a digraph has any vertex-disjoint cycle cover
> Given a digraph, determine if the graph has any vertex-disjoint cycle cover.

I understand that the permanent of the adjacency matrix will give me the number of cycle covers for the graph, which is 0 if there are no cycle covers. But is it possible to check the above condition directly?

# Answer
Your problem is answered in the Wikipedia article on vertex-disjoint cycle covers. According to the article, you can reduce this problem to that of finding whether a related graph contains a perfect matching. Details can be found in a paper of Tutte or in recitation notes of a course given by Avrim Blum.

As a comment, in the graph-theoretic literature a vertex-disjoint cycle cover is known as a *2-factor*.
> 3 votes

---
Tags: graphs, adjacency-matrix
---


# Question
Title: What is a Huffman tree for a Block-Code?
We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ".

I have created a Huffman tree for the string w.

We get the following table:

Now I want to create a Huffman tree for a Block-Code with length of block $4$.

Do we maybe take each consecutive 4 letters, i.e., {aabc, eefg, eebd, aabb, ceef, fghd, cbbe, efbb, bbgh, hie} to make the tree?

But then the last one is of length 3 and not 4.

So, do we choose in an other way the blocks?

# Answer
> 1 votes
In your context, a block code of length $\ell$ encodes $\ell$ letters at a time. The domain thus consists of all words over the alphabet of length $\ell$. Unless you're told otherwise, the assumption is that the individual letters are independent - the probability of a word $\sigma\_1 \dots \sigma\_\ell$ is the product of the probabilities of the individual letters.

---
Tags: data-structures, trees, binary-trees, huffman-coding
---


# Question
Title: Precise relation between complexity classes(focus on P, NP and EXPTIME)
I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes.

What I know so far:

1. $P \subseteq EXP$ (from Time Hierarchy Theorem \[1\])
2. We don't know an exact relation between $P$ and $NP$, and between $NP$ and $EXPTIME$. What do we know:

2.1 $\forall problem \in P \Rightarrow problem \in NP$ (Any problem in $P$ is in $NP$.)

2.2 $\forall problem \in P \Rightarrow problem \in EXPTIME$ (Any problem in $P$ is in $EXPTIME$.)
3. In $P$ vs $NP$:

3.1 We haven't found an $ NP $ $complete$ $problem $ that we can solve in polynomial time (this would imply $P = NP$)

3.2 We haven't found a proof that states that we can't find an polynomial (running time) algorithm for an $NP$ $complete$ $problem$ (this would imply $P \neq NP$)

3.3 From 3.1 and 3.2 we can't state anything about the cardinality of $NP-P$. Most of scientists belive that $P \neq NP$ so there are $NP$ problems that we can't solve in polynomial time.

First, if you find and "hole" in what is stated above, please correct me.

Now for my questions:

A. What can we say about $NP$ vs $EXPTIME$? Are there $EXPTIME$ $complete$ problems not in $NP$? For me it sounds like the $P$ vs $NP$ problem just one "level" (in the hierarchy) higher.

B. How does one go about finding a proof like in 3.2? Obviously we haven't found such a proof but I am looking to understand. The first idea that comes to mind is to go with a proof by contradiction. Not finding such a proof doesn't say much (maybe we are not "smart" enough). What else could we try? The problem reduces, in my opinion, to proving that an algorithm in "elegant" (in running time; that means that it is "the fastests")

Kind of bonus question:

C. How does this relate to Godel's incompleteness theorem? Maybe the better question (quite outside of the scope of the original question) is how much of the math we use on answering these questions can be considered a formal system(so we can apply Godel's result)? What parts are not "formal"?

D. I wasn't able (yet) to look very far into \[1\]. If possible, can someone give me an informal insight on how it handles defining a strict lower (time) bound for a certain problem?

\[1\]https://en.wikipedia.org/wiki/Time\_hierarchy\_theorem

# Answer
The Wikipedia page on EXPTIME summarizes all the known relationships:

* $\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}$.
* $\mathsf{P} \subsetneq \mathsf{EXPTIME}$ due to the time hierarchy theorem.

You can find more information on the time hierarchy theorem in Wikipedia, in textbooks, and in online lecture notes. It is a very standard topic.

The P vs NP question is about the first two levels of the polynomial hierarchy. It is conjectured that all levels are distinct and different from $\mathsf{PSPACE}$, which is an upper bound on the hierarchy; and that $\mathsf{PSPACE}$ is distinct from $\mathsf{EXPTIME}$ (it is known that $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$).

The proof of the time hierarchy theorem uses diagonalization in a straightforward manner (at least conceptually), and in this regard it is part of a line of results that includes Gödel's (first) incompleteness theorem and Turing's undecidability of the halting problem. In fact, it is a time-bounded version of the latter.

Finally, while some people have some ideas on how to prove $\mathsf{P} \neq \mathsf{NP}$, we mostly know a few general methods which *cannot* prove $\mathsf{P} = \mathsf{NP}$. These are known as *barriers*, and include diagonalization (used to prove the time hierarchy theorem), natural proofs (used to prove lower bounds in circuit complexity), and arithmetization (used to prove $\mathsf{IP}=\mathsf{PSPACE}$). The Wikipedia article about the P vs NP problem has a nice summary about these barriers.
> 2 votes

---
Tags: complexity-theory, complexity-classes, logic, time-complexity, lower-bounds
---


# Question
Title: Could we write $(a+b)^* = (\epsilon + a + b)^+$?
I have read that $L^\* = L^+ - \epsilon$, but if we write $(\epsilon + a + b)^+$, is it equivalent to $(a+b)^\*$?

# Answer
> I have read that $L^∗=L^+−\epsilon$

That's definitely not true, since $\epsilon\in L^\*$ but $\epsilon\notin \[\text{anything}\]-\epsilon$. If you still know where you read this, I suggest you check to see if you've misremembered what was written.

> but if we write $(\epsilon+a+b)^+$, is it equivalent to $(a+b)^∗$?

Yes. The first regular expression matches any string that can be broken up into one or more units, where each unit is either empty, an $a$ or a $b$. That matches the empty string (every unit is empty) or any string of positive length containing only $a$s and $b$s (every unit is $a$ or $b$). The second regular expression matches any string that can be broken up into zero or more units, each of which is an $a$ or a $b$. That matches the empty string (no units at all) or any string of positive length containing only $a$s and $b$s (one or more units).
> 4 votes

# Answer
I think you're having a bit of a semantic confusion. It's not true that $\epsilon \notin e^+$, because the definition of $e^+$ is not $e^\* - \\{\epsilon\\}$; rather $e^+$ is $e \cdot e^\*$. It's a bit nuanced, but these two definitions disagree whenever $e$ is nullable, because $ee^\*$ is still nullable while $e^\* - \\{\epsilon\\}$ is no longer nullable by definition.

Here's one way to test this hypothesis, assuming that $e^+ = ee^\*$. Recall that regular expression forms roughly what we would call a semiring in that operations are associative ($\small(a + b) + c = a + (b + c) = a + b + c$, $\small(ab)c = a(bc) = abc$) and $\cdot$ distributes into $+$ ($\small l(a + b) = la + lb, (a + b)r = ar + br$). Unfortunately, it is not commutative, since ordering in words matter, but it is a $+$-idempotent (semi)ring in that $a + a = a$.

Given this ring-like characterization, we're allowed to borrow any numerical tools that doesn't rely on commutativity in our analysis.

**Hypothesis**: $(a+b)^\* = (\epsilon + a + b)^+$ for all regular expressions $a, b$

*Proof*: Let's start by expanding the left side. $$ (a + b)^\* = \epsilon + (a + b) + (a+b)^2 + \cdots $$ Similarly, we can expand the right side as \begin{align\*} (\epsilon + a + b)^+ &= (\epsilon + (a + b))^+ & \text{associativity} \\ &= (\epsilon + (a + b)) + (\epsilon + (a + b))^2 + \cdots \\ &\text{ by the binomial theorem} \\ &= \sum\_n \left(\sum\_k^n {n \choose k} \epsilon^{n - k} (a + b)^k\right) \\ &= \sum\_n \left(\sum\_k^n {n \choose k} (a + b)^k\right) & \text{since }\epsilon e = e \\ &= \sum\_n \left(\sum\_k^n (a + b)^k\right) & \text{since }na = a, \text{ if } n \> 0 \\ &= \sum\_k (a + b)^k & \text{again by idempotence} \\ &= \underbrace{(a + b)^0}\_{\epsilon} + (a + b)^1 + (a + b)^2 + \dots \end{align\*} Since the two sides agree, they are necessarily equivalent, though the right side is necessarily "ambiguous." $\square$

There's a few ingredients of this proof. The main one is how we absorb redundant subexpressions via idempotence, but the ability to use the binomial theorem is pretty cool too.
> 0 votes

# Answer
A more general theorem, which holds for any regular expression $r$, is

> $r^\* = (r+\epsilon)^+$.

The proof is straightforward, using the definitions of $s^+,s^\*$. The exact proof depends on your exact definition. A related theorem is

> $r^\* = (r+\epsilon)^\*$.

I encourage you to prove these results using the definitions you learned in class.
> 0 votes

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


# Question
Title: Find minimum number of time points that cross out all intervals
Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of the intervals using the least amount of time points. E.g. if all of the intervals have not finished at time 6, one point is enough, as point 6 it marks all of the intervals of the problem. Starting and ending time points ( `[s(i),e(i))` ) for each interval `i` are given. Time points are integer values.

The point `i` marks intervals that have started before `i` and finish after `i`, or intervals that started exactly at `i`.

Obviously, I would like something better than plain out trying all possibilities.

I have tried a greedy algorithm, more specifically choosing the point that marks the most intervals at a time (it is easy to see that it is only worth considering points at which an interval starts), removing the intervals it marks and repeating with the remaining intervals. I have found counter-examples showing it does not always give correct results.

The next try would be dynamic programming, which I am breaking my head with right now. However it gets too complex. In the recursive calls I have to make a call for the possibility that the time point checked will be included, and one for the possibility that it will not. However, I must find a way to select a time point anyway, in the case not selecting it will lead to intervals not being marked at all - in that case, I must recognize that before proceeding to the next recursive calls, as I will get false results. It also is a problem how I will keep a record of which intervals proceeded to the recursive call unmarked, without taking too many actions that will increase complexity.

Interval graphs might give me some ideas. If we are talking about interval graphs the problem can be expressed like this: Suppose we have a graph. The nodes are NOT the intervals, but the starting points of each interval. If a **starting point** of an `interval 1` intersects with an **interval** (at any of its points) `interval 2`, then its node is connected to the starting point node of that `interval 2` with a **directed edge**. Choosing to mark a node removes the said node and all the nodes it is connected to. What is the least number of markings I must execute in order to erase the whole graph?

# Answer
> 1 votes
The solution is as follows. As I have said in the question, we need not check all the time axis explicitly, but we may only traverse the starting and ending points, and if we assume that only starting points can be used to mark the intervals that pass through them, we are right, since the number of intersecting intervals only decreases at ending points.

Since we need as few points selected in the end as possible, the idea is to postpone the selecting of a time point in our final solution as much as possible. Therefore, the suitable algorithm for this problem is greedy. We traverse the starting and ending points in sequential order. When we meet an ending point, we put in the solution the last starting point we met before the current ending point,mark out all the intervals that pass through it, and continue with the remaining intervals. The result is correct because, if we chose some later point, the interval that was about to end would not be crossed out, and if we used an earlier point, we might need some extra points for the rest of the solution than we would have with our algorithm, as we would just increase the number of intervals to be taken care of for the rest of the problem, and for sure that would mean the number of points in the final solution would not be less than that of our algorithm - remember, we want the minimum number of points needed.

Deleting the intervals that are marked by a point is easy, if we keep a list of all the intervals that are "active" at any moment, adding one when we meet its starting point. So when we meet an end point, we put the starting point of the last added in the solution, and clear the list of its intervals.

# Answer
> 1 votes
Hint:

> Try some more greedy algorithms; keep trying, and don't give up yet. You might try solving some small examples by hand, to get some intuition for what is going on, and see what strategies you end up developing. The way to look for a greedy algorithm is to try *all* greedy strategies you can think of -- it's not enough to just try one particular strategy and if that doesn't work give up on the entire paradigm of greedy algorithms.

This looks like a nice learning exercise, so keep at it. You can do it. (We're glad to help you understand concepts but just solving this exercise for you probably won't help with that.)

---
Tags: dynamic-programming, greedy-algorithms, intervals
---


# Question
Title: How to model a set of categorical values in the input of a neural network
One of the inputs to my neural network is a set. I have a set $S = \\{s\_0, s\_1, ..., s\_n\\}$ in which all values $s\_i$ are constant. An example of such a set could be the set of French wines (Beaujolais, Languedoc-Rousillon, Champagne) or the set of players in a sports event (Player A, Player B, ...). The input to the neural network is a subset $T$ of $S$ (e.g., Player A competing against Player B or Beaujolais wine being served at a table, but nothing else).

Due to the restrictions of my neural network design, all input values must be normalized within the interval $\[0,1\]$. How would I encode the set $T$ to obtain an input to the neural network? How do I normalize the values in my set $S$ in a way to respect this condition?

My current idea is to **use one boolean input per $s\_i$**: there would be $\\#(S)=n$ boolean inputs, all set to 0 except for the values in $T$, which would be all 1. However, this presents the obvious flaw that for large $n$ there would be a lot of input neurons. Moreover, if one imposes the additional restriction of having *at most* $m$ elements in $T$, the resulting model would not efficiently correspond to the model (i.e. what if $m+1$ values were set to true)?

Is there a better way of modeling such a situation? Or better, is there a *standard* way for handling input sets with multiple possibilities?

# Answer
> 2 votes
Yes, the "one boolean per set element" is the standard way of encoding such a set. This is known as a "one-hot encoding". Yes, there will be a lot of input neurons, but that's not necessarily a serious problem; current procedures for training neural networks are able to handle millions of nodes with no problems.

If you know that $T$ will contain at most $m$ elements, in principle there are alternative encodings (e.g., use $m \lg n$ wires, where you use $\lg n$ wires for each element of $T$ to encode which element of $S$ it is)... but in practice I do not expect them to perform well.

In that case I think a better approach is to try to build a feature vector that is shorter than $n$ dimensions. Do you have some domain knowledge you can use to identify attributes of the elements? For instance, you could have a feature that says "how many elements of $T$ are red wines?" and "how many elements of $T$ are white wines?" and "how many elements of $T$ are dessert wines?" and so on. You'll have to use your domain knowledge about the task to identify what attributes might be relevant to the classification task. In this way, the number of input wires can be made much smaller than $n$.

---
Tags: artificial-intelligence, neural-networks, neural-computing
---


# Question
Title: term vs clause in the context of normal forms
In the context of disjunctive normal forms, which terminology do you use for the conjunction of atoms? E.g., for the disjunctive normal form $(x₁ ∧ ¬x₂ ∧ x₃) ∨ (¬x₁ ∧ x₂ ∧ x₃)$, how are the constituents "$x₁ ∧ ¬x₂ ∧ x₃$" and "$¬x₁ ∧ x₂ ∧ x₃$" called? Terms or clauses? I saw boths variants as well as "disjunctive clauses", and I wonder which variant is right.

There are lots of non-native English computer scientists around, so please reply only if you are an established computer scientist who actually taught this and have an excellent command of English.

# Answer
> 1 votes
They're often called a "clause", "conjunctive clause", or sometimes a "conjunction" (if it is clear from context what that is referring to).

See, e.g., https://en.wikipedia.org/wiki/Disjunctive\_normal\_form.

---
Tags: terminology, normal-forms
---


title: Deadlock not possible?

text:
# Question
Title: Deadlock not possible?
> System is in safe state if there exists a safe sequence of all processes.
>
> Sequence $\[P\_1, P\_2 …P\_n\]$ is safe, if for each $P\_i$ the resources that can still request can be satisfied by $P\_i$ currently available resources + resources held by $P\_j$ with $j \lt i$

The above is from a presentation distributed by my OS II teacher. Assuming it is true, then doesn't this mean that the system is *always* in a safe state?

I conjecture that $\forall$ set of processes $X = \[P\_1 ... P\_n\]$ requesting for a set of resources $\[R\_1 ... R\_n\]$ $\exists$ a safe sequence $S = \\{P\_i ... P\_k\\}, S: S$ is a permutation of $X$.

Reasoning behind my conjecture. Suppose I had $n$ processes and $1$ resource(each process requesting it.) I could order these processes in order of priority, or ascending order of size and run them. If resources were increased to $k$, there will still be a sequence such that every process completes in finite time. The challenge merely finding it.

Am I wrong?

# Answer
Lets say for the sake of argument we have 6 units of memory available and three processes in a current state where each holds 2 resources. Each process needs 3 resources to finish and release its memory units to use by the others. This state is not safe, in fact this state is deadlock. Each needs one extra memory unit to finish, but this would require another process to release its units. No ordering of these 3 processes will be safe.

You are not looking at the state of the program, but the entirety of the program, in which case, with no new resource creation and single threading, every state is safe.

**Edit for clarity**: From the definition of a state: "In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given instant in time, to which the circuit or program has access".

The import point is "given instant". The state could be at the initial state as your argument would require, or it is at some arbitrary point in execution
> 1 votes

---
Tags: concurrency, deadlocks
---


# Question
Title: Falsifying the "Circular Wait" Condition - Deadlock Prevention
In the *Circular Wait* condition for `Deadlock Prevention` section of this, it is described as follows:

> One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration. To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one-to-one function F: R → N, where N is the set of natural numbers.
>
> For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows: F (tape drive) = 1 F (disk drive) = 5 F (printer) = 12 We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration.

My question is that whether these numbers are assigned as **fixed** for all processes or when each process is called, it assigns a **new** number to each resource each time that process is called?

Because if these are fixed, then let suppose there is a process which requires `disk drive` first (whose number is let's say 5) and then it requires `tape drive` (whose number is 1 and which is less than 5); then how can it access tape drive? Because whenever it will run, it will find the same ordering / numbering of resources and it will never be able to access the tape drive.

# Answer
It's fixed. Your example violates the protocol. If the process needs mutually exclusive access to both the tape drive and the disk drive, then it needs to take locks in increasing order, i.e. *first* the tape drive then the disk drive. If it wants to use the disk drive before the tape drive, that's fine, it will just be holding the tape drive lock in the mean time.

The ordering and protocol is a *global* invariant. All code everywhere at all times needs to follow the protocol to avoid deadlock. In practice, this is pretty difficult to enforce in realistic code unless there's a manager that handles resource access.
> 2 votes

# Answer
With deadlocks, you need to distinguish between two situations: One, that a deadlock is possible. Two, that a deadlock actually occurs. For example, if process A locks X, then Y, and process B locks Y, then X, a deadlock is possible. But a deadlock only actually occors if process B manages to lock Y between X locking X and trying to lock Y, or vice versa. This may only happen very rarely. When a deadlock is possible, you can bet that there will be no actual deadlock occuring when the developer tests the software, but as soon as a customer uses it, the deadlock will occur.

Problems with software are no problem if they can be found through testing, because then they will be fixed. That's what this method achieves: It can demonstrate that when you ran the software, there was no possible deadlock.

What happens if you see that two resources were requested in the wrong order? You don't deadlock, but you notify the software developer. Then one of two actions are taken: It may be possible to fix the problem by changing the ordering of the deadlocks. Or this may not work, in which case you need to change the software.

A system could be in one of four states: 1. Proven that no deadlocks are possible. 2. No evidence that deadlocks are possible. 3. Evidence that deadlocks are possible. 4. Actual deadlocks happening. Instead of waiting for the fatal and rare (4) to happen, we detect the much less rare (3) and then modify the system to get into state (2). (1) would be really difficult to achieve.
> 0 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Mean and median distance in unweighted graph
I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph.

I need to find the mean and median distances of the graph (median and mean distances over all shortest-path distances of the graph). I need the exact mean/median, not an approximation. This problem must be related to all-pairs shortest paths. But the only algorithms I know of for this problem are: Floyd Warshall, Dijkstra starting from each vertex, and Breadth First Search starting from each vertex. However, their running time is $\Omega(V^2)$ for all three of these algorithms, so for such a large graph they are too slow.

Can this problem be solved in linear or linearithmic time? If not, what is the fastest algorithm for this problem, in asymptotic complexity?

# Answer
(This is not a full answer.)

The median distance is necessarily an integer \[footnote 1\]. Therefore, it might be possible to use an approximation algorithm for the median to compute the *exact* median, if the approximation is sufficiently precise.

Suppose the true median is $\xi$. Then if we can efficiently compute a $1+1/3\xi$-approximation to the median, we can reconstruct the exact median from that.

I suspect it is possible to get a $\tau$-approximation to the median efficiently through random sampling. In particular, consider the following procedure:

* Repeat $k$ times: in the $i$th iteration, pick a random vertex $v\_i$, compute single-source shortest paths from $v\_i$ to every vertex, and find the distribution of these distances.
* Aggregate these distributions and output the median of this aggregated distribution.

One might hope to get an approximation whose quality increases rapidly with $k$, and where if we want a constant approximation factor $\tau$, then a constant $k$ suffices. I have no proof that this is possible, though.

We can consider a simpler situation, where given an integer $x$ we are trying to approximately count the fraction of distances that are at most $x$. If the fraction of such distances is approximately $1/2$ (e.g., because $x$ is approximately the median), then one approach is random sampling: repeat $k$ times where we pick a random pair of vertices $u,v$ and compute the distance from $u$ to $v$ (say using BFS), then count what fraction of those $k$ distances are at most $x$. The additive error is typically about $1/2\sqrt{k}$; it exceeds $c/\sqrt{k}$ with probability exponentially small in $c$ (it's basically the probability of a Gaussian being more than $2c$ standard deviations away from the mean). Thus, we can get a $1+\epsilon$-approximation to this count using $O(1/\epsilon^2)$ iterations. Each iteration takes at most $O(E)$ time, so with $O(E/\epsilon^2)$ time we can get a $1+\epsilon$-approximation to this count. The probability that our approximation is wrong can be made exponentially small; an error probability of $1/2^{100}$ is so small as to be negligible in practice (e.g., it is smaller than the probability of a cosmic ray causing a bitflip error that causes an error in your code), and this will increase the running time by only a constant factor (say, 100, or something like that). In this case it might be sufficient to also take $\epsilon$ to be a small constant.

Intuitively, it feels like if we can get a good approximation to this count, it might be possible to extend this to a good approximation to the median. For instance, if we hypothesize that the median is $x$, we can count the fraction of distances that are $\le x-1$, the fraction that are $\le x$, and the fraction that are $\le x+1$. If $x$ is indeed the median, hopefully the first fraction will be noticeably smaller than $1/2$ and the latter fraction will be noticeably larger than $1/2$. I don't know how to turn this into an algorithm that I can prove will always work on all graphs, but I suspect this might work well enough in practice.

---

Computing the (exact) mean seems like it might be harder, as the mean isn't necessarily an integer.

---

Footnote 1: The median is either an integer or halfway between two integers. In the latter case, the rest of the answer carries through if you divide everything by two.
> 3 votes

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


title: Reasoning on Efficiency (2)

text:
# Question
Title: Reasoning on Efficiency (2)
Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective one is than the other.

Is there a yard stick that can be applied to *ALL* algorithms, with *ALL* time complexities, that can be used to evaluate the efficiency of two algorithms?

I actually developed a method for this, but it applies only to polynomial algorithms.

MY METHOD.

> Suppose we want to compare two algorithms for accomplishing a task $f\_i(n), g\_i(n)$. $f\_i(n) = o\left(g\_i(n)\right)$
> A simple way to compare $f\_i$ and $g\_i$, is to find their ratio $r\_i(n)$
> $$r\_i(n) = \frac{g\_i(n)}{f\_i(n))}$$
> Express $r\_i(n)$ as a polynomial of ,$n$.
> $$r\_i(n) = n^{k}, \\{k: k \in \Bbb R\\}$$
> $$m = \lceil{k}\rceil$$
>
> $R\_i(n) = m^{th}$ derivative of $r\_i(n)$.
> It follows that $R(n)$ is a constant.

My method works nicely for polynomial algorithms, but is completely useless for other time complexities. Is there a more effective yardstick? One that applies to all complexities?

# Answer
The concepts of asymptotic running time analysis and Landau notation *already* provide a way to compare the asymptotic running time of two algorithms, as long as (a) you are happy to ignore constant factors, (b) only care about asymptotics (limiting behavior as problem size gets large), and (c) you want to evaluate them according to their worst-case running time. It sounds like you are happy with (a), (b), and (c), so you should be happy with existing tools. They *do* tell you how much more efficient one algorithm is than the other. You just might not have appreciated yet how to fully use these mathematical tools and concepts, which is understandable.

In particular, if we can express the running time of algorithm A as $\Theta(f(n))$ and the running time of algorithm B as $\Theta(g(n))$, we already know how to compare them. We know that the ratio of their running time is $\Theta(f(n)/g(n))$. In particular:

* If $f(n)/g(n) = \Theta(1)$, we know that their asymptotic worst-case running times are equivalent.
* If $f(n)/g(n) = o(1)$ (i.e., $f(n) = o(g(n))$), we know that A is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(f(n)/g(n))$.
* If $f(n)/g(n) = \Omega(1)$ (i.e., $f(n) = \Omega(g(n))$, or equivalently, $g(n) = o(f(n))$), we know that B is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(g(n)/f(n))$.

You might want to read How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Sorting functions by asymptotic growth, How do O and Ω relate to worst and best case?, and Justification for neglecting constants in Big O. That will give you some essential background to help you understand how these concepts fit in.

(I'm simplifying a bit, and casting this at the level that it sounds like you're ready to absorb. Once you understand the basics, read Are the functions always asymptotically comparable? if you want to read some more precise statements -- but beware that right now this might just cause more confusion than it's worth.)
> 5 votes

# Answer
All you're doing is comparing two functions by taking their ratio. The only reason you think this is restricted to polynomials is that you want to express the ratio as a polynomial. If you don't restrict the ratio to be a polynomial, you can relate arbitrary functions. (Actually, it's not restricted to polynomials since, e.g., if $f(n)=n^22^n$ and $g(n)=n2^n$, $f/g$ is still a polynomial.)

But, in general, the ratio of two polynomials *isn't* a polynomial; rather, it's a so-called rational function. For example, $(x^2+1)/x = x+\tfrac1x$, which isn't of the form $x^k$ for any real $k$, and which has no constant derivatives.
> 2 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, asymptotics
---


# Question
Title: Computing the minimal flexible distance of two vectors using dynamic programming
I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim to minimize the total sum of distances between matched points with the following constraints:

* Every point from both vectors has to be matched at least once, but can be matched multiple times.
* A point `i` can only be matched with a point `j` if no point `o` is matched with a point `u` such that `i < o` and `j > u` or `i > o` and `j < u`, i.e., the ‘lines’ of the matches are not allowed to cross.

In order to compute the distance between two matched points, we use the absolute difference.

(Easy) Example input:

```
1.0 2.0 2.4 3.5
2.0 2.1 2.0 3.2

```

Should output:

```
1.8

```

Because in this example `|1.0 - 2.0| + |2.0 - 2.1| + |2.4 - 2.0| + |3.5 - 3.2|` is optimal

The assignment hints to sequence alignment which I thoroughly studied and came across the Needleman-Wunsch algorithm. However, I can't figure out how to adapt it to this problem.

# Answer
> 2 votes
Since this is a programming assignment, I only show some hints.

Consider two vectors $\vec{a} = a\_1 \cdots a\_i \cdots a\_m$ and $\vec{b} = b\_1 \cdots b\_j \cdots b\_n$.

First, please prove the following

> *Observation:* $a\_m$ must be matched with $b\_n$.

Second, consider the following subproblems,

$$D(i,j) \triangleq \text{the optimal (matching) distance between } a\_1 \cdots a\_i \text{ and } b\_1 \cdots b\_j.$$

and answer the following question

> Given the observation above, what is the relationship between $D\_{i,j}$ and $D(i-1, j)$, $D(i, j-1)$, or maybe $D(i-1, j-1)$?

---
Tags: recurrence-relation, dynamic-programming, recursion
---


title: What is a homogenous half-space?

text:
# Question
Title: What is a homogenous half-space?
I can't think of any definition for half-space that would involve some sort of quantity not being homogenous.

This term is used in the paper Robust Concepts and Random Projection in the following paragraphs:

> The next problem we consider is learning an intersection of t half-spaces in Rn, i.e., the positive examples all lie in the intersection of t half-spaces and the negative examples lie outside that region. It is not known how to solve the problem for an arbitrary distribution. However efficient algorithms have been developed for reasonably general distributions assuming that the number of half-spaces is relatively small \[8, 44\]. Here, we derive efficient learning algorithms for robust concepts in this class.
>
> We assume that all the half-spaces are homogenous. Let the concept class of intersections of half-spaces be denoted by H(t,n). A single concept in this class is specified by a set of t half-spaces P = {h1, . . . , ht}, and the positive examples are precisely those that satisfy hi · x ≥ 0 for i = 1 . . . t. Let (P, D) be a concept-distribution pair such that P is -robust with respect to the distribution D. We assume that the support D is a subset of the unit sphere (and remind the reader that this as well as homogeneity are not really restrictive, as they can be achieved by scaling and adding an extra dimension, respectively; see e.g. \[44\]).

It's not clear to me from context, not defined in the paper and I haven't been able to find a clear definition from searching for it.

# Answer
> 6 votes
A half-space is said to be homogeneous if the hyperplane that defines it contains the origin.

(Source: S. Vempala, *A Random Sampling based Algorithm for Learning Intersections of Half-spaces*. *Journal of the ACM* 57(6) article 32, 2010. PDF.)

---
Tags: machine-learning, perceptron
---


# Question
Title: how to prove the following is a bijection?
I have a translation function which translates $\lambda$-terms to another representation let me call it $G\_\lambda$, as follows.

$\chi(x)$ $=$ $ X^2$ if $ x \notin \Gamma$

$\chi(x)$ $=$ $X$ if $ x:X \in \Gamma $

$\chi(\lambda x.t\_1)$ $=$ $abs(X^1,\chi(t\_1))$ and do $\Gamma,x:X^1$

$\chi(t\_1 \\, t\_2)$ $=$ $app(\chi(t\_1),\chi(t\_2))$

where to translate $\chi(\lambda x.t\_1)$, it creates a distinct $X^1$ and add a pair $x:X$ to set $\Gamma$.

$\chi(x)$ look $x$ in $\Gamma$, so we can use already added $X^1$ as bound variable or create a distinct $X^2$ for the free variable $x$.

so, a $\lambda$-term $\lambda x.yx$ will be $abs(X^1.app(Y^2,X^1))$.

I think $\chi$ is a bijection. It is obvious that function $\chi$ maps one $\lambda$-term to one $G\_\lambda$ representation, so it is injective.

My problem is that since $X^1$ and $X^2$ are created fresh, if you translate a $\lambda$-term $\lambda x.yx$ twice, then you will have two representation such as $abs(X^1.app(Y^2,X^1))$ and $abs(A^1.app(B^2,A^1))$, which are equal terms but not syntactically same.

But how can i prove from $G\_\lambda$ to $\lambda$-term is a surjective?

# Answer
> 1 votes
One option could be adding more parameters to $\chi$ so to make both $\Gamma$ and a fresh name source $\phi \in {\sf Names}^\infty$ explicit:

$$ \begin{array}{l} \chi(\Gamma, x, X;\phi) = X \mbox{ if } x \not\in\Gamma \\ \chi(\Gamma, x, \phi) = X \mbox{ if } x:X \in\Gamma \\ \chi(\Gamma, \lambda x. t, X;\phi) = abs(X, \chi(\Gamma;x:X, t, \phi)) \\ \chi(\Gamma, t\_1 t\_2, \phi) = app(\chi(\Gamma, t\_1, \phi^1),\chi(\Gamma, t\_2, \phi^2)) \\ \qquad \mbox{where } \phi = \phi^1\_0 \phi^2\_0 \phi^1\_1 \phi^2\_1 \phi^1\_2 \phi^2\_2 \ldots \end{array} $$

You can then state a form of injectivity as $$ \chi(\Gamma, t\_1, \phi) = \chi(\Gamma, t\_2, \phi) \implies t\_1 = t\_2 $$ and surjectivity as $$ \forall T.\ \exists \Gamma, t, \phi.\ \chi(\Gamma, t, \phi) = T $$

Note that some stronger forms of injectivity do **not** hold. E.g. $$ \chi(\Gamma\_1, t\_1, \phi) = \chi(\Gamma\_2, t\_2, \phi) \implies \Gamma\_1 = \Gamma\_2 \land t\_1 = t\_2 $$ is false since $$ \chi(x:X,x, \phi) = \chi(y:X,y, \phi) \land x:X \neq y:X $$ Similarly, this does not hold: $$ \chi(\Gamma, t, \phi\_1) = \chi(\Gamma, t, \phi\_2) \implies \phi\_1 = \phi\_2 $$ since only a finite portion on $\phi$ is needed by $\chi$.

---
Tags: lambda-calculus, discrete-mathematics
---


# Question
Title: To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements
This problem is from codechef.Can anyone please help me out with this one as I am unable to find out the subproblem.Thanks in advance!

Problem -: In IPL 2025, the amount that each player is paid varies from match to match. The match fee depends on the quality of opposition, the venue etc.

The match fees for each match in the new season have been announced in advance. **Each team has to enforce a mandatory rotation policy so that no player ever plays three matches in a row during the season.**

Nikhil is the captain and chooses the team for each match. He wants to allocate a playing schedule for himself to maximize his earnings through match fees during the season.

**Input format**

Line 1: A single integer N, the number of games in the IPL season.

Line 2: N non-negative integers, where the integer in position i represents the fee for match i.

**Output format**

The output consists of a single non-negative integer, the maximum amount of money that Nikhil can earn during this IPL season.

Sample Input 1

5

10 3 5 7 3

Sample Output 1

23

(Explanation: 10+3+7+3)

Sample Input 2

8

3 2 3 2 3 5 1 3

Sample Output 2

17

(Explanation: 3+3+3+5+3)

# Answer
> 0 votes
Let $X\_k$ be the largest sum up to the k-th element that follows the rules and doesn't include the k-th element itself. Let $Y\_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, but not the one before. Let $Z\_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, and the one before as well. Let $a\_k$ be the array elements.

Then $X\_{k+1} = max (X\_k, Y\_k, Z\_k)$, $Y\_{k+1} = X\_k + a\_{k+1}$, and $Z\_{k+1} = Y\_k + a\_{k+1}$. Start with $X\_0 = Y\_0 = Z\_0 = 0$, calculate $X\_n, Y\_n, Z\_n$ and the solution is $max (X\_n, Y\_n, Z\_n)$.

---
Tags: dynamic-programming
---


# Question
Title: What is the difference between "strict schedule" and "cascadeless schedule"?
In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts?

Could you give an example of a schedule that is secured against cascade aborts but is not strict?

I found these slides that give definitions but it's still not clear to me where is the difference (they just seem differently worded).

# Answer
On a cascadeless schedule a transaction $T\_2$ cannot read a value $a$ if a transaction $T\_1$ wrote $a$ before that and didn't commit. On a strict schedule $T\_2$ also wouldn't be able to write $a$ after $T\_1$ wrote it (even if it read $a$ before $T\_1$ wrote it).

If you read carefully, the definition of strict says "not read **or overwritten**". That's the difference.

I reproduce here an example of cascadeless but not strict schedule, from the Wikipedia page on the subject:
> 7 votes

# Answer
Definitions from the books by Korth et. al. and Elmasri et al.:

> **Cascadeless schedule**
> A cascadeless schedule is one where, for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti , the commit operation of Ti appears before the read operation of Tj .
>
> **Strict schedule**
> If in the given schedule, each transaction Tj neither reads nor writes any data item ‘x’ until the last transaction Ti that has written ‘X’ is committed or aborted then it is strict.

Notice:

* Definition of cascadeless schedule only puts restriction on where in the schedule the reads of transaction Tj can appear.
* Definition of strict schedule only puts restriction on where in the schedule the reads and write of transaction Tj can appear.

Thus following schedule is allowed under cascadelessness definition but not under definition of strict schedule:

```
| T1       | T2       |
|----------|----------|
| write(x) |          |
|          | write(x) |
|          | commit   |
| read(x)  |          |

```

as `write(x)` of `T1` appears before `commit` of `T2`. Evidently cascadeless schedule can contain blind writes !!!
> 2 votes

# Answer
Lets say T1 and T2 are two transactions. T1 is scheduled first and T2 next. Assume they gonna read a variable **a**

Now lets see how it works.

**Cascadeless schedule:**

> T2 can read **a** only after commit action from T1. But some transaction write and read. T2 can write **a** before commit action from T1

now lets look what is strict schedule:

> **Strict schedule:** T2 can read and write **a** only after commit action from T1.
> 1 votes

---
Tags: database-theory
---


# Question
Title: How to represent a double push or double pop operation in push down automata
I want to know the theoretical representation of a double push or a double pop in pda

# Answer
There are several different definitions of pushdown automata. In the definition I know, every transition pops one stack symbol and pushes an arbitrary number of stack symbols. Thus you cannot "double pop", but you can push more than one element. You can simulate a double pop using $\epsilon$-transitions, but I'll let you figure that out.
> 2 votes

---
Tags: pushdown-automata
---


title: Reasoning on Efficiency (3)

text:
# Question
Title: Reasoning on Efficiency (3)
This is my third installation of my "Reasoning on Efficiency" series. This question builds on my first question in the series: "Reasoning on Efficiency (1)"

The question in this installment builds on the ideas developed in the first question.

Advertising out of the way, let's proceed. My question is this:

> Giving a particular problem $P\_i$. Let the most optimum possible algorithm\* for solving $P\_i$ be $A\_{ij}$,
> $$A\_{ij} \rightarrow H(x)$$
>
> My question is this: Is it possible to prove that $$H(x) = \Theta\left(f(x)\right)$$
> Where $f(x)$ is a function with known time complexity.

\*If for any Problem $P\_i$, $K\_i$ is the set of all possible algorithms(both known and unknown) for solving $P\_i$. A given algorithm $A\_{ij} \in K\_i$ is said to be the "most optimum possible" if: $$\forall A\_{ix} \in K\_i, A\_{ij} = o\left(A\_{ix}\right)$$

# Answer
The answer depends on your computation model. Let's consider the case of Turing machines, and the language $L$ over $\\{0,1\\}$ of words ending in $1$. This language has time complexity $n+1$.

Blum's speedup theorem states that optimal algorithms don't exist for all problems, in a very strong sense (which is explained in the Wikipedia article).

Finally, let me mention that your notion of optimality is too restrictive. Given an algorithm with running time $T(n)$ for any problem, it is easy to construct (in the Turing machine model) another algorithm whose running time is also $T(n)$. So no language can have an optimal algorithm in this very strong sense. Even if you consider only running times, it is easy to construct (in the same model) another algorithm with the different running time $T(n)+1$. So no non-trivial language can have an optimal running time in your very strong sense.
> 4 votes

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


# Question
Title: Efficiently inserting into list keeping number of inversions minimal
Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u.

I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u).

Basically I would like to insert objects into a list while keeping it "as sorted as possible" while keeping the order of the first list.

Example:

```
u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

```

As you can see there is no unique optimal solution.

I'd be glad for any sort of ideas or direction to look into.

# Answer
This is an elaboration on on trevore's answer. It's too long to fit in a comment and contains the proofs of his solution (or at least how I understand it).

**You can show that in any optimal solution, the elements of $s$ will appear ordered.** If not, assume $s\_1 \< s\_2$ and they appear in reverse order in an optimal solution. Let $\sigma\_1$ be the number of elements between $s\_1$ and $s\_2$ that are less than $s\_1$ and $\beta\_1$ be the number of those that are bigger than $s\_1$. Define $\sigma\_2$ and $\beta\_2$ similarly for $s\_2$. Note that $\sigma\_1 \leq \sigma\_2$ and $\beta\_2 \leq \beta\_1$. Swapping $s\_1$ and $s\_2$ will change the number of inversions by $-\beta\_1 + \beta\_2 - \sigma\_2 + \sigma\_1 - 1$ which is at most -1.

**It is not hard to see that elements of $s$ can be inserted independently.** Since they appear ordered, the elements of $s$ do not "feel" each other's presence. That is, pairs of elements from $s$ do not contribute to the inversion count. To do that, insert the median of $s$ optimally in linear time. Then, recursively, insert elements of $s$ less than the median to the left of the median and elements bigger than the median to its right.

Let the median be inserted in position $k$, the runtime of this satisfies, $T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$, the linear $|s|$ factor is for finding the median and shuffling the elements of $s$. It is easy to show by induction that $T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$.

Note that the dependence on $|s|$ here is optimal. Since solving the problem with empty $u$ is equivalent to sorting $s$ using only comparisons. The dependence on $|u|$ is also optimal, since the problem for a singleton list $s$ and a list $u$ must require linear work.
> 2 votes

# Answer
Ok, here is my solution:

An observation (which I more or less proved) is that an optimal solution will always be one in which s is sorted ascendingly. This gives rise to an O((|u|+|s|)\*log(|s|)) algorithm.

To find the optimal solution for a single element, do as I said in my comment: Take one element from s, compare it to each element in u from left to right, increment a counter is an inversion and carry the previously calculated number over. Then traverse the list from right to left with the same element, increasing the counts for each position.

This is O(|u|).

Sort s.

For the middle element of s at position m: Find the best position b in u (using the method from above).

Split s at m and u at b and recursively call with the left and the right parts, concatenating the results with m in the right order.

Stop as soon as u or s are empty.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Maximum waiting time between events such that k events are not missed
I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:

> In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.
>
> * Lap times last exactly a minute, and they are booked for the full minute.
> * If we use a free lap time slot, we must wait *x seconds* until we can use another.
>
> We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.
>
> Example:
>
> With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.

So I tried hard and came up with this recurrence: $$X\[i,m\] = \max\_{1 \leq j \leq i}\ (\min\ (X\[j,m-1\],\sum\_{k=j}^{n-1}abs(s\_{k+1} - s\_k)))$$ Where X\[i,m\] means "the maximum distance that I can pick in the subset $\\{s\_1,s\_2,...,s\_i\\}$ so that I lap at least m times".

Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X\_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).

Any ideas or hints?

Thank you.

# Answer
The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.
> 0 votes

---
Tags: algorithms, dynamic-programming, efficiency
---


# Question
Title: How long does the Collatz recursion run?
I have the following Python code.

```
def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

```

What is the running-time of this algorithm?

Try:

If $T(n)$ denotes the running time of the function `collatz(n)`. Then I think I have \begin{cases} T(n)=1 \text{ for } n\le 1\\ T(n)=T(n/2) \text{ for } n\text{ even}\\ T(n)=T(3n+1) \text{ for } n\text{ odd}\\ \end{cases}

I think $T(n)$ will be $\lg n$ if $n$ is even but how to calculate the recurrence in general?

# Answer
This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.
> 31 votes

# Answer
You translated the code correctly. There are many methods for solving recurrences.

However, it is currently unknown if `collatz` even halts for all `n`; the claim that it does is known as Collatz conjecture. Therefore, no known method will work on this recurrence.

> I think $T(n)$ will be $\lg n$ if $n$ is even

How so? I guess you are thinking of $n=2^k$, for which your claim is correct. This goes to show that this recurrence is *not* one we can solve up to $\Theta$ by investigating exponentially few points (see also here).
> 15 votes

# Answer
The time complexity function is

\begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases}

which can be rewritten as the following if you are interested in asymptotic time complexity.

\begin{cases} T(n)= 1 \text{ for } n\le 1\\ T(n)=T(n/2) + 1 \text{ for } n\text{ even}\\ T(n)=T(3n+1) + 1\text{ for } n\text{ odd}\\ \end{cases}

It is not even known that the resulting TM $\langle M,1^n\rangle \in Halt$ (See Halting Problem) for every $n$. So naturally we can't measure the time taken to halt if we do not even know if it halts for every $n$. Also refer https://math.stackexchange.com/questions/2694/what-is-the-importance-of-the-collatz-conjecture.

Collatz conjecture is a very famous conjecture which Collatz proposed in 1937. Many eminent mathematicians have spent (read wasted) countless hours in trying to solve this conjecture but to little avail. Even Paul Erdős said about the Collatz conjecture, "Mathematics is not yet ready for such problems."
> 13 votes

# Answer
I would add to the other answers the fact that the third branch of the function i.e the case of $n$ is $odd$ suggests that in that case the function will be computed on a larger instance ($n$ is lower than $3n+1$). So there is more work to be done on that computation branch.

Other recurrence relations that we encounter (for example in the case of merge sort $T(n) = 2T(n/2) +n$) adhere to the division of a problem into subproblems for instances with smaller size. Those reccurences degenerate naturally into base case(s), namely $T(0)$ or $T(1)$ which are known. So, standard mathematical tools for analyzing the reccurence can be used, like the master theorem.

In the case of collatz function we are not able to infer directly from the reccurence that the case of $3n+1$ will eventually deteriorate using standard mathematical tools of reccurences. This is a topic to be resolved by looking at the problem itself, not the reccurence that describes it.
> 2 votes

# Answer
You have T (n) = T (n/2) + 1 if n is even. But then n/2 is quite likely not even, so you are stuck there.

What happens is that the nice little rules that you learned are confronted with a real problem, and they don't work. They hit a brick wall, face first, and it hurts. Do yourself a favour, and follow the recursion for T (7) manually, and then you tells if you still believe this is related lg n.

If you think this isn't related to the original question because 7 is not even: Whenever n is odd, T (n) = T (3n + 1), and 3n + 1 is even, so if T (n) were log n if n is even, it would be log (3n + 1) + 1 whenever n \> 1 is odd.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Meaning of $\triangleright$ in programming language semantics
What does the symbol "$\triangleright$" mean programming language semantics? I've seen it in the context of datatypes in and the evaluation of expressions in environments.

For example :

$$tenv \triangleright erht \implies tval $$

or

$$tenv\[tval/x\]\triangleright ebody\implies t\\,.$$

Here, $tenv$ is an environment and $ebody$ is the body of some expression.

# Answer
> 3 votes
Most probably, in your context, ▹ is just a syntactic separator, meaning "in the environment to the left of ▹, the formula to the right of ▹ holds".

However, ▹ has no fixed meaning in general. I used it myself with completely different definitions.

---
Tags: terminology, logic, semantics
---


# Question
Title: Does the order in which qubits are measured matter in quantum computing?
I’ll define my question more specifically:

Lets suppose we have an $n$ bit quantum computer, with qubits labelled $q\_{1},…,q\_{n}$, and let $b$ be any bit string of length $n$ (let’s assume we’ve labelled each qubits’ states $0$ and $1$ so that we obtain an $n$ bit bit string when we measure the qubits).

The question is, is the probability that we obtain $b$ when we measure each qubits’ state dependent on the order in which we measure the qubits? I have a feeling the probability would be independent of the order the qubits are measured, but am struggling to prove this.

# Answer
> 9 votes
No, the order doesn't matter.

**Proofs**

* *Algebra*. Take an input state $\sum\_k c\_k |k\_0 k\_1 k\_2 ...\rangle$. Apply the definition of measurement from your textbook to it. Compute the expression for the probabilities and outputs of each case when measuring qubit 0 then qubit 1. Do the same for measuring qubit 1 then qubit 0. Notice that the two expressions are equal. Generalize.
* *Circuit moves.* Measurement is equivalent to a CNOT gate from the target qubit onto an ancilla qubit that you simply don't use for anything else:

So if you think you can change the outcome statistics by reordering measurements, you should think you can do the same without involving measurements at all (until a simultaneous measurement of all qubits at the end of the circuit). All you should need is independent CNOTs. But clearly independent CNOTs can be re-ordered.
* *Play*. For me, the fact that ordering doesn't matter wasn't proven so much as experienced. I dragged gates around in Quirk and noticed that measurement is easily the most boring operation. All measurement does is throw away off-diagonal density matrix elements. Even for the *target* qubit, measurement doesn't change the computational basis probabilities.

---
Tags: quantum-computing
---


title: Lower bounds and $P$ vs $NP$

text:
# Question
Title: Lower bounds and $P$ vs $NP$
I know $P$ vs $NP$ is an open problem in Computer Science. However the people concerned (at least according to Wikipedia) believe $P \neq NP$.

I have two questions:

$(1.)$ Given that it is possible to prove lower bounds for problems. Does there exist any problem(s) for which the solution can be verified in polynomial time but no ***known*** algorithm can solve it in polynomial time which has a ***proven*** lower bound?

$(2.)$ Is this ***proven*** lower bound polynomial or exponential?

# Answer
1. Every $NP$-complete problem is an example of this! It's just a question of how good the lower bounds are.

For example, there's an $\Omega(n)$ lower bound on basically every problem, since you need to read your entire input to solve it. This is a very imprecise lower bound, but it does exist.

So, you're not going to get a good list of a bunch of problems like this, because such a list would be too large, and uninformative.

Whether there are problems with *notable* lower bounds is a different issue. I don't know of any that fit your criteria (sorting is the most famous one, but it's in $P$). Here's an example question about bounds on 3SAT:

Not very informative, as you can see.
2. The known lower bounds in such a case will always be polynomial. If there were any problems verifiable in polynomial time (in $NP$) with an exponential lower bound, that would imply that $P \neq NP$.
> 6 votes

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Is there a task that is solvable in polynomial time but not verifiable in polynomial time?
A colleague of mine and I have just hit some notes of one of our professors. The notes state that there are tasks that are possible to solve in polynomial time (are in the class of PF) but that are NOT verifiable in polynomial time (are NOT in the class of NPF).

To elaborate about these classes: We get some input X and produce some output Y such that (X,Y) are in relation R representing our task. If it is possible to obtain Y for X in polynomial time, the task belongs to the class of PF. If it is possible to verify polynomial-length certificate Z that proves a tuple (X,Y) is in relation R in polynomial time, the task belongs to the class of NPF.

We are not talking about decision problems, where the answer is simply YES or NO (more formally if some string belongs to some language). For decision problems it appears that PF is a proper subset of NPF. However, for other tasks it might be different.

Do you know of a task that can be solved in polynomial time but not verified in polynomial time?

# Answer
This is only possible if there are many admissible outputs for a given input. I.e., when the relation $R$ is not a function because it violates uniqueness.

For instance, consider this problem:

> Given $n \in \mathbb{N}$ (represented in unary) and a TM $M$, produce another TM $N$ such that $L(M)=L(N)$ and $\\# N \> n$ (where $\\# N$ stands for the encoding (Gödel number) of $N$ into a natural number)

Solving this is trivial: keep adding a few redundant states to the TM $M$, possibly with some dummy transitions between them, until its encoding exceeds $n$. This is a basic repeated application of the Padding Lemma on TMs. This will require $n$ paddings, each of which can add one state, hence it can be done in polynomial time.

On the other hand, given $n,M,N$ it is undecidable to check if $N$ is a correct output for the inputs $n,M$. Indeed, checking $L(M)=L(N)$ is undecidable (apply the Rice theorem), and the constraint $\\#N \> n$ only discards finitely many $N$s from those. Since we remove a finite amount of elements from an undecidable problem, we still get an undecidable problem.

You can also replace the undecidable property $L(M)=L(N)$ to obtain variations which are still computable but NP hard/complete. E.g. given $n$ (in unary) it is trivial to compute a graph $G$ having a $n$-clique inside. But given $n,G$ it is hard to check whether a $n$-clique exists.
> 44 votes

# Answer
This is merely an elaboration of the first sentence of @chi's answer, since I did not find it obvious.

The idea is, if you have an algorithm that finds the answer to some problem in polynomial time, then there are two possibilities:

1. You have previously proven (mathematically) that the algorithm's output is a solution to the problem, in which case, the algorithm's steps themselves form the proof of correctness.
2. You have a different algorithm for checking that the output is indeed a solution, in which case you must be running this algorithm (otherwise you'd be falling under case #1), which implies you're doing it in polynomial time.

Therefore, there can be no such problem.
> 1 votes

---
Tags: complexity-theory, np
---


title: reduction from MAX-CUT to MAX-3-CUT

text:
# Question
Title: reduction from MAX-CUT to MAX-3-CUT
MAX-3-CUT gets a graph and a number $k$, and determines whether three sets of vertices can be found within that graph, where at least $k$ edges are in the cut. We define the cut as all edges $(u,v)$ where $u$ and $v$ are in a different set.

MAX-CUT also gets a graph and a number $k$, and does the same but by dividing it to two sets of vertices.

It is known that MAX-CUT is NP complete and I'm trying to show that MAX-3-CUT is also NP Complete by reducing from MAX-CUT.

What I've done so far:

1. Showing that MAX-3-CUT in NP is easy using a verifier.
2. I think the reduction should be, given $\langle G=(V,E),k \rangle$ return $\langle G',k+|V| \rangle$, where $G'=(V'=V+{w}, E'=E+\\{(w,v) : v \in V\\})$.
3. Proof of correctness: doing so, It's easy to show that if $\langle G,K \rangle$ is in MAX-CUT then $\langle G',k+|V| \rangle$ is in MAX-3-CUT by setting the third group to be $\\{w\\}$. The problem is I can't do the opposite direction: if $\langle G,k \rangle$ isn't in MAX-CUT than $\langle G',k+|V| \rangle$ isn't in MAX-3-CUT. I also tried to show that if $\langle G',k' \rangle$ is in MAX-3-CUT then $\langle G,k \rangle$ is in MAX-CUT but I get stuck with how to turn 3 sets into 2.

Note: I was able to show that MAX-3-CUT is NPC by reducing from 3COL (pretty straightforward), but I need it to be reduced from MAX-CUT.

# Answer
Hint : Consider $G '=(V'=V \cup\\{w\_i|i\in \[1,|V|\]\\},E'=E\cup\\{(w\_i,v)|v \in V , i\in \[1,|V|\]\\})$ and $k'=|V|^2+k $

Consider a partition of V' in 3 parts, call $P $ the one with the smallest number of nodes in $V $.

Note that by putting a w in P , if it were not in it, you increase the number of edges in your 3cut.

Then, note that if all the ws are in the same part, then removing a node of V from that part increases the number of edges in your 3cut.
> 1 votes

---
Tags: complexity-theory, time-complexity, np-complete, reductions
---


# Question
Title: In a DAG, does there exist a sink for all vertices in the DAG?
The following statement is considered true:

> In a DAG, for every vertex $v$, there exists a sink $s$ such that there is a path from $v$ to $s$.

However, my counter example to this is a binary search tree. The leaf nodes in a binary tree do not have a path from themselves to a sink. Hence, am I interpreting this statement incorrectly?

# Answer
> 2 votes
A sink is a vertex with an out degree of zero. The leaf nodes of a binary search tree are the sinks. This is the trivial case of the statement as a path always exists from a node to itself, this path contains no edges, however the statement never said for vertex $v$, the sink $s$ could not be itself. Without this not only is the statment not true, but for every graph it is untrue since all DAGS have at least one sink and that sink could not be paired with another sink since that defeats the nature of a sinc.

---
Tags: graphs
---


# Question
Title: Using analog values with Algebraic Normal Form?
Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates.

The below is an example of an ANF expression which evaluates to true if two or more of it's three inputs are true ($\oplus$ being XOR, implicit multiplication being AND)

$x\_0x\_1 \oplus x\_0x\_2 \oplus x\_1x\_2$

When a digital circuit is expressed this way, you can evaluate it as a polynomial, taking 1 or 0 as inputs for the variables, doing a multiplication for an AND gate, addition for an XOR gate, and doing a modulus by 2 on the final result.

$y = x\_0x\_1 + x\_0x\_2 + x\_1x\_2$

you can verify a truth table by plugging in 0s and 1s for the various $x$ parameters and seeing that it comes out to the correct values.

What I'm curious about is what if we don't use whole numbers? I'm sure that's a well studied thing but I haven't been able to find any information about it.

it seems sort of like fuzzy logic, but fuzzy logic is a well defined thing with different operations.

Here's some values plugged in and their output.

\begin{array}{|c|c|c|c|} \hline x\_0 & x\_1 & x\_2 & output & output \\% 2 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 3 & 1 \\ 0.5 & 0.5 & 0 & 0.25 & 0.25\\ 0.9 & 0.9 & 0.9 & 2.43 & 0.43 \\ 1.0 & 1.0 & 0.5 & 2.0 & 0.0 \\ \hline \end{array}

The analog value input gives output that seems especially wrong in the last two rows.

It seems like maybe this just "doesn't work", but it also feels like maybe it does work, or does do something interesting, perhaps with some modifications?

Has anyone come across non digital values used in ANF or similar?

Thanks!

# Answer
Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement:

> Every function from $\mathbb{Z}\_2^n$ to $\mathbb{Z}\_2$ can be represented uniquely as a multilinear polynomial.

Here $\mathbb{Z}\_2$ is the field with two elements, and a polynomial is multilinear if all monomials are products of distinct variables (so you can't have $x\_i^2$ in a monomial).

The upshot is that the *modulo 2* operation is not the most natural way of understanding the computation involved in algebraic normal form; rather, addition is done over the field $\mathbb{Z}\_2$. It seems rather unnatural to apply the *modulo 2* operation to real numbers in this context.

One generalization of algebraic normal form to real numbers is the Fourier expansion over the Boolean cube:

> Every function from $\\{-1,1\\}^n$ to $\mathbb{R}$ can be represented uniquely as a multilinear polynomial (with real coefficients).

Here $\mathbb{R}$ is the field of real numbers.

Another generalization is the Hermite expansion in Gaussian space:

> Every function from $\mathbb{R}^n$ to $\mathbb{R}$ can be approximated arbitrarily well by a polynomial (with real coefficients).

Here *arbitrarily well* means up to $\epsilon$ distance in $L^2$ with respect to Gaussian measure (e.g., see this Wikipedia article).
> 3 votes

---
Tags: computation-models, digital-circuits
---


# Question
Title: How best to statistically verify random numbers?
Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the standard deviation and mean value, what are my options for a robust verification process?

# Answer
You can't. Randomness is a property of the *source*, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question.

Or, to quote Dilbert:

What you *can* do is perform some kind of statistical test, with the properties that (a) if it is truly random, it'll probably be accepted, (b) if it is not truly random, it might be accepted or might be rejected (no guarantees). In other words, if the statistical test *rejects* it, then odds are it wasn't random. However, if the statistical test doesn't reject it, you can't conclude anything -- it might be random, or it just be a good enough mimic to fool that one statistical test. Such statistical tests are often sufficient that they can reject many obviously-bad generators.

If that sounds like the kind of thing you're looking for, look up the DIEHARD test suite and related tools.

See also How can it be detected that a number generator is not really random?.
> 10 votes

# Answer
The best-effort verification is to estimate min-entropy. There are many, many ways to do that, each having their own pitfalls.

One interesting approach is to use algorithms that try to predict the next value using the previous values, as was explored in the paper Predictive Models for Min-Entropy Estimation. The paper also references the NIST Special Publication 800-90b (draft) which covers some methods for estimating min-entropy. You can find more information about random number generation at NIST's Random Number Generation page.

This is all much more relevant to random generators meant to be used in cryptographic contexts.
> 2 votes

---
Tags: randomness, statistics, entropy
---


# Question
Title: Constructing a Pixel Image from Rectangles and Row or Column Rotations
The most recent challenge on Advent of Code involves constructing an image in a binary pixel array from a sequence of instructions:

1. **rect AxB**, which sets all of the pixels in a rectangle A pixels wide by B tall at the top left corner of the array.
2. **rotate row y=A by B**, which performs a circular rotation of row A by B pixels.
3. **rotate column x=A by B**, which performs a circular rotation of column A.

As part of solving the problem, I produced the following image:

```
####..##...##..###...##..###..#..#.#...#.##...##..
#....#..#.#..#.#..#.#..#.#..#.#..#.#...##..#.#..#.
###..#..#.#..#.#..#.#....#..#.####..#.#.#..#.#..#.
#....#..#.####.###..#.##.###..#..#...#..####.#..#.
#....#..#.#..#.#.#..#..#.#....#..#...#..#..#.#..#.
####..##..#..#.#..#..###.#....#..#...#..#..#..##..

```

This got me wondering:

* How is the inverse problem solved? i.e. given an image, what sequence of instructions generates that image?
* Are there any images which cannot be created with this set of instructions?
* Is there a polynomial-time algorithm to find a minimal sequence of instructions that generate a target image? That is, where there is no shorter set of instructions that generates the same image. If not, is there a polynomial-time algorithm for deciding if a given sequence of instructions is minimal?

I've done some Google searches but turned up nothing. I would appreciate any links to materials describing this or similar problems.

# Answer
> 1 votes
Yes. For every image, there exists some sequence of operations that generates that image.

I'll describe how to implement a **set (x,y)** operation, which sets the pixel in the xth row and yth column (and leaves all other pixels unchanged). It should be clear that you can construct any image you want by repeatedly applying this primitive.

Here's how to implement the "**set (x,y)**" operation using the 3 operations you gave us:

1. Rotate column y upwards by x-1 positions, so that position (x,y) moves to position (x,1).
2. Rotate row 1 leftwards by y-1 positions, so that position (x,1) moves to position (1,1).
3. Set the pixel in the upper-left corner (the pixel at position (1,1)).
4. Rotate row 1 rightwards by y-1 positions, so that position (1,1) moves back to (x,1).
5. Rotate column y downwards by x-1 positions, so that position (x,1) moves to position (x,y).

It is easy to see that each of these 5 steps can be done using one of your three operations, and that afterwards, the pixel at (x,y) is set and all other pixels are left unchanged.

This shows that given a image with dimensions mxn, we can create it using at most 5mn operations. Of course, this sequence of operations probably isn't the shortest possible. I don't know whether there is an efficient algorithm to find the shortest sequence of operations to generate a target image.

---
Tags: algorithms, graphics
---


title: What does "AF AX p" mean in CTL?

text:
# Question
Title: What does "AF AX p" mean in CTL?
Both *Logic in Computer Science* (Huth and Ryan, 2004) and *Branching vs. Linear Time: Final Showdown* (Vardi, 2002), state something to this effect (paraphrased):

> In LTL, X F *p* and F X *p* are equivalent, meaning "*p* is eventually true in some state that is not the current state". In CTL, AX AF *p* and AF AX *p* are not equivalent. AX AF *p* does mean the same as the above LTL formulas, but AF AX *p* means something different, which we leave as an exercise to the reader.

Both works emphasize that the meaning of AF AX *p* is something very strange.

From what I understand of CTL, AF AX *p* would mean "all paths from this state eventually reach a state where *p* is true in all next states", but that doesn't seem particularly strange. Am I correct in that understanding?

# Answer
Your understanding of $AF AX p$ is correct (in my opinion). But whether it seems *particularly strange* or hard to understand is rather subjective. The argument you quote compares the expressiveness or usability of LTL and CTL, and tries to convince readers that LTL is easier to understand (especially for engineers in practice).

In my experience, it indeed takes more time for me to figure out and confirm the meaning of $AF\\,AX\\,p$ than that of $AX\\,AF\\,p$, which is in turn more than that of $X\\,F\\,p$ or $F\\,X\\,p$. By the way, if $AF\\,AX\\,p$ were easier to understand than the other three formulas, you would probably not bother asking for confirmations here.
> 4 votes

---
Tags: formal-languages, formal-methods, software-verification, linear-temporal-logic, computation-tree-logic
---


# Question
Title: Why is the k-bounded spanning tree problem NP-complete?
The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$.

I realize that for the case $k=2$, this is the Hamiltonian path problem. However I'm having trouble with cases where $k\>2$. I tried thinking about it in the sense that you can add more nodes onto an existing spanning tree where $k=2$ and maybe since the base is NP complete, adding things on will make it NP-complete as well, but that doesn't seem right. I'm self-studying CS and am having trouble with theory, so any help will be appreciated!

# Answer
The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path.

Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning tree exists. So we can determine the minimum degree of a spanning tree up to an uncertainty of $1$.
> 10 votes

# Answer
My understanding is if you have an algorithm that can solve k-bounded spanning tree problem with any k, you can use that algorithm to solve a special case with k=2, which is essentially a Hamiltonian path. So if your algorithm can achieve polynomial time, then it can be used to solved Hamilton path in polynomial time, which is equivalent to solving any np-complete problems in polynomial time. So the k-bounded spanning tree problem must be np-complete. Note that this is a general idea, not a complete proof.

Also note that being np-complete doesn't mean that there's no polynomial time algorithms that can solve the problem. No one has proven this yet. It only means that all problems that are np-complete are equally hard and if one can be solved in polynomial time then all can be solved in polynomial time.
> 1 votes

---
Tags: spanning-trees
---