# Question
Title: Disjoint Set Connected Components With Weighted Graph
I have been trying to solve this HackerRank problem (link).

The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken to be the MAXIMUM cost of any edge in the path. I will be given a series of queries in the form of `[L, R]` and I have to output how many paths in that tree have a cost in the provided inclusive range.

This is the code I've written -

```
class DisjointSetRep():
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

class DisjointSetNode():
    def __init__(self, val):
        self.val = val
        self.next = None
        self.head = None

class DisjointSetLinkedList():
    def __init__(self):
        self.rep = DisjointSetRep()

    def add_node(self, node):
        if not self.rep.head:
            self.rep.head = node
        self.rep.count += 1
        self.rep.tail = node
        node.head = self.rep

def make_set(v):
    new_linked_list = DisjointSetLinkedList()
    new_head_obj = DisjointSetNode(v)
    new_linked_list.add_node(new_head_obj)
    return new_linked_list, new_head_obj

def find_set(v, node_map):
    return node_map[v].head

def union(u, v, node_map, sets_map):
    u_node, v_node = node_map[u], node_map[v]

    if u_node.head.count > v_node.head.count:
        small_rep = v_node.head
        large_rep = u_node.head
    else:
        small_rep = u_node.head
        large_rep = v_node.head

    # update all nodes to point to new rep
    temp = small_rep.head
    while temp:
        temp.head = large_rep
        temp = temp.next
    # update last node in first list to point to head of second list
    large_rep.tail.next = small_rep.head
    # update new tail
    large_rep.tail = small_rep.tail
    # update count
    large_rep.count += small_rep.count
    del sets_map[small_rep]
    return large_rep

def create_data(edges, node_map, sets_map):

    # sort the edges first, according to cost
    edges.sort(key=lambda x:x[2])
    cost_map = {} # key - cost, value - no of paths
    largest_cost = edges[-1][2]

    for edge in edges:
        if find_set(edge[0], node_map) != find_set(edge[1], node_map):
            unioned_set = union(edge[0], edge[1], node_map, sets_map)
            cost_map[edge[2]] = unioned_set.count - 1

    prefixed_cost_data = {0: 0}
    for i in xrange(1, largest_cost+1):
        val = cost_map.get(i, 0)
        prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

    return prefixed_cost_data

if __name__ == '__main__':
    n, q = map(int, raw_input().split())
    sets_map = {}
    node_map = {}
    for i in xrange(1, n+1):
        new_set, new_node = make_set(i)
        sets_map[new_node.head] = new_set
        node_map[i] = new_node
    edges = []
    for _ in xrange(n-1):
        edges.append(map(int, raw_input().split()))
    prefixed_cost_data = create_data(edges, node_map, sets_map)
    for _ in xrange(q):
        l, r = map(int, raw_input().split())
        print prefixed_cost_data[r] - prefixed_cost_data[l-1]

```

Let me explain the logic above, which I have derived from this comment \-

I sort the edges according to their cost. I then iterate over them and construct the tree edge-by-edge by `union`ing each vertex, which is initially a disjoint set containing itself (`make_set`). At any point, `no_of_vertexes - 1` gives the no of paths in the tree that contain the maximum cost, which is what I use in `unioned_set.count - 1`.

This gives me a `cost_map` with keys as the costs and the values as the number of paths. I also generated a prefixed sum array so that to get the output for `[L, R]`, instead of calculating the no of paths for each value in the range, I can just do `prefixed_cost_data[r] - prefixed_cost_data[l-1]`.

The implementation of the disjoint set is taken straight from CLRS (Section 21.2).

I think the above logic is correct, but I guess it's too slow since most of the test cases timeout.

Can anyone help me in optimizing it? I guess the entire logic needs to be revamped.

# Answer
Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.

Here's a resource to start off with:- Disjoint Set Union

```
for edge in edges:
    if find_set(edge[0], node_map) != find_set(edge[1], node_map):
        unioned_set = union(edge[0], edge[1], node_map, sets_map)
        cost_map[edge[2]] = unioned_set.count - 1

```

`cost_map[edge[2]]` will not be equal to the size of resultant set after union - 1.

It will be equal to the product of size of two individual sets.

Over here,

```
for i in xrange(1, largest_cost+1):
    val = cost_map.get(i, 0)
    prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

```

`largest_cost` can be `>10^9`. Neither can you store an array of that size, nor can you execute a loop with 10^9 operations with a time limit of `1sec`.

Try using binary search on the `L R` query.

If you implement disjoint union set with arrays and make the above corrections , then I believe the code should work.
> 1 votes

---
Tags: algorithms, graphs, data-structures, trees, sets
---


# Question
Title: Proof on lower bound of search in unsorted array with information theory?
I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound for a search in an unsorted list using information theory.

# Answer
Here is an informal proof, which you can try to formalize.

Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)

Given the transcript of the algorithm, you can either recover the position of a 1, or deduce that the array consists only of 0s. Since typically there are only few 1s, the entropy of the answer should be $\Theta(\log n)$.

On the other hand, each position you query only gives you $h(1/n) = \Theta(\log n/n)$ information. Hence you need to query $\Omega(n)$ bits.
> 3 votes

---
Tags: complexity-theory, algorithm-analysis, search-algorithms, information-theory
---


# Question
Title: Optimal Page Replacement Algorithm - If more than one frame will not be used again, which one gets replaced?
This may not make a difference in the end, but not knowing is driving me insane. When using the Optimal algorithm for page replacement, if you need to put something new into a frame and you have more than one frame that will not be used again, how does it prioritize which one to replace? In other words, if you have three frames and you enter in 1, 1, 2, 3, and neither 1 or 2 ever appears again, which one gets bumped when you try to put in 4?

Does it go by FIFO and kick out 1, does it go by most used and kick out 2 or does it go by least recently used and kick out 1?

# Answer
Wikipedia says

'The Optimal Page Replacement Algorithm **cannot be implemented** in a general purpose operating system because it is impossible to compute reliably how long it will be before a page is going to be used, except when all software that will run on a system is either known beforehand and is amenable to static analysis of its memory reference patterns, or only a class of applications allowing run-time analysis. Despite this limitation, algorithms exist that can offer near-optimal performance — (i.e. less page faults).'

Hence, it is an ideal algorithm for page replacements and causes the least no. of page faults to occur. So, you should not be worried about which frame will be popped out if more than two frames are not used in near future because as you mentioned, it does not matter (since no. of page faults will remain the same no matter which one you pop out) and you cannot implement it in real life. Moreover, this algorithm can be used to compare the efficiency of other algorithms.
> 3 votes

# Answer
The optimal algorithm uses whatever is optimal (or one of the optimal possibilities, in case there are several), i.e. whatever produces the least page faults. There isn't necessarily any simpler description of its behavior, though there might be. In general, it depends on the problem; for this specific problem, I don't know whether a simple description exists, though there is probably a simple algorithm that finds an optimal sequence.

*FIFO*, *most used* and *LRU* are heuristics that are useful for the online version; it's not necessarily true that they can be used in any shape or form to obtain optimal page replacement sequences (but you might be able to describe rules for obtaining an optimal sequence using them; I just don't know).
> 2 votes

---
Tags: algorithms, algorithm-analysis, memory-management
---


# Question
Title: How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?
In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies the following two inclusions:

1. $\Sigma\_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$
2. $\mathsf{ZPP}^\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$

They also cite this enhancement of the Karp-Lipton theorem, in which the collapse of $\mathsf{PH}$ is to $\mathsf{ZPP}^\mathsf{NP}$. I suspect the theorem is behind the inclusions in some way, but I just can't make the connection.

What am I missing?

# Answer
> 5 votes
If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}\[O(n^k)\]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and then replacing every call to the $\mathsf{SAT}$ oracle with the assumed small circuit for $\mathsf{SAT}$.

---
Tags: complexity-theory, circuits
---


# Question
Title: Büchi automaton to Linear Temporal Logic
Given a Büchi automaton what is the procedure to build an equivalent LTL formula? And what is its size?

I'm looking for references but I haven't found them so far.

# Answer
Since Büchi automata are strictly more expressive than LTL, such a translation is not possible in the general case.

For instance, the language $L = \\{w\_0 w\_1 w\_2 \ldots \in (2^{\\{a\\}})^\omega \mid \exists^\infty i \in \mathbb{N}. w\_{2i} = \\{a\\} \\}$ is representable by a Büchi automaton with 3 states, but is not expressible in LTL as it is a *counting* language.
> 4 votes

---
Tags: automata, linear-temporal-logic, buchi-automata
---


# Question
Title: Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
Let be $(I\_n)\_n$ a set of $p$ intervals each contained in $\[0, L\]$ for $L \geq 1$.

I define $(J\_n = \[a\_n, b\_n\])\_n$ the set of intervals which have empty intersection with $I\_n$ for all $n \in \[\[1, p\]\]$.

I'd like to efficiently compute $\max\_n (b\_n - a\_n + 1)$.

A basic idea I'd try would be to:

(1) Create a segment tree for $(I\_n)\_n$ in $O(p \ln p)$

(2) Iterate over $\[0, L\]$ and count the longest line before encountering an interval covered by $(I\_n)\_n$ (resetting the "max value" to 0 until the next of a certain $J\_q$)

Which could give me an algorithm in $O(L + p \ln p)$, the problem is that $L$ is really big in my instances, I'd like to have an algorithm which does not depend on $L$.

# Answer
> 5 votes
(From your notations, I assume the intervals are all discrete as otherwise some of the $J\_n$ would not be closed. Furthermore, the length of the intervals would not be $b\_n-a\_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case).

1. Consider all intervals $(I\_n=\[\\!\[s\_n,e\_n\]\\!\])\_{0\leq n\<p}$, and sort them by increasing start time $s\_n$, breaking ties arbitrarily **\[time $\mathcal{O}(p\cdot \log p)$\]**
2. Build a stack containing only the first interval (i.e. the one with the smallest start). For each subsequent interval: if \[the interval doesn't overlap with the head of the stack\] then \[push it\] else \[merge it with the head of the stack\] **\[time $\mathcal{O}(p)$\]**

*What we've done here is merge the intervals $(I\_n)\_n$ so as to rewrite $\bigcup I\_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}\_n=\[\\!\[\tilde{s}\_n,\tilde{b}\_n\]\\!\])\_n$*

Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $\[\\!\[0,\tilde{s}\_0\[\\!\[$ and $\]\\!\]\tilde{s}\_{-1},L\]\\!\]$) **\[time $\mathcal{O}(p)$\]**

Overall the runtime is $\mathcal{O}(p\cdot \log p)$.

---
Tags: search-trees, counting, intervals
---


title: question about algorithm

text:
# Question
Title: question about algorithm
as you know we have equivalent condition for graphs so I want to ask a very basic question and please help me what is exactly w1(e1) and w1(e2) and w2(e1) and w2(e1) ? If e1 means path from A to B so w1 means the weight of the path e1 and so what about w2 and what does it mean means ? is there any link for this kind of topic to understand better ?

thank you so much

this is main question

# Answer
**The solution provided here is highly inelegant as it uses a lemma which is a more general result. This 'solution' should instead be considered as more of a hint: a minimal solution can instead be found by extracting the most relevant parts of the proof of the lemma.**

Note that $w\_1(e\_1)\<w\_1(e\_2)\Leftrightarrow w\_2(e\_1)\>w\_2(e\_2)$ implies that $w\_1(e\_1)=w\_1(e\_2)\Leftrightarrow w\_2(e\_1)=w\_2(e\_2)$. In particular, if we order the edges in a non-decreasing order according to $w\_1$, then we have also ordered them in non-increasing order according to $w\_2$.

Now, recall that any minimal spanning tree (for $(G,w\_1)$) can be found by Kruskal's algorithm (lemma -- https://cs.stackexchange.com/a/95625/109876), so in particular there is an order on the edges which is non-decreasing for $w\_1$ such that $\mathcal{T}(\mathcal{V},\mathcal{E}')$ is selected. This same order is non-increasing for $w\_2$, and can therefore be used to find a maximum spanning tree (for $(G,w\_2)$) using Kruskal's algorithm. But since Kruskal's selection process is independent of the actual weights (and depends only on the ordering and whether the current edge creates a cycle or not), the algorithm will output $\mathcal{T}(\mathcal{V},\mathcal{E}')$ again.
> 0 votes

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Equivalence from multi-tape to single-tape implies limited write space?
Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:

$A$: "adds a $ at the beginning of the tape."

So we have: $$ \begin{array}{lc} \text{Before }: & 0101\sqcup\sqcup\sqcup\ldots\\ \text{After }A: & \\$0101\sqcup\sqcup\ldots \end{array} $$

And it is running on a multi-tape turing machine. The equivalence theorem from Sipser book proposes we can describe any multi-tape TM with a single-tape applying the following "algorithm", append a $\\#$ at every tape and then concat every tape in a single tape, and then put a dot to simulate the header of the previous machine, etc, etc.

With $a$ and $b$ being the content of other tapes, we have: $$ a\\#\dot{0}101\\#b $$ If we want to apply $A$ or another subroutine that uses more space, the "algorithm" described in Sipser is not enough, I can intuitively shift $\\#b$ to the right, but how to describe it more formally for any other subroutine that uses more space in the tape? I can't figure out a more general "algorithm" to apply in this cases.

# Answer
> 2 votes
Sipser's book handles this case:

> If at any point $S$ moves one of the virtual heads to the right onto a $\\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\\#$, one unit to the right. Then it continues the simulation as before.

---
Tags: turing-machines, automata
---


# Question
Title: Is there a concept called "white waveforms" in computer science?
It sounds like the lecturer is speaking

> If you for example want to play a music file, mp3 file, well you know, given that you've taken a programming course before, all right? How would you do this?
>
> Well, you would look up on Wikipedia, what are the specifications of an mp3 file, and then you would sit down over a long weekend and you could probably write something in Python or in C, takes the file decodes it generates the **white waveforms** and so on.
>
> and it's not a big deal right after a couple days you will have a program that takes that date and generates the output, that's fine.

The lecturer used a term "white waveforms".

I know the visual of a waveform may look like this figure.

I also know `.wave` is one type of audio filename extension.

I am trying to figure out what "white waveforms" is.

I understand the approximate meaning that the lecturer is trying to say is playing mp3 file.

So, what is "white waveforms"?

# Answer
> 5 votes
I suspect you might have misheard. I suspect the lecturer said "takes the file decodes it generates the **right waveforms** and so on" (right, not white).

# Answer
> 2 votes
I was listening that lecture and I think that was just a slip of the tongue. I don't think such thing exists. The closest thing coming to my mind is "**White Noise**". In signal processing, white noise is a random signal having equal intensity at different frequencies, giving it a constant power spectral density.

However, it doesn't really matter in that machine learning concept. It could be any sort of waveform.

---
Tags: terminology
---


title: Directed graph reachability

text:
# Question
Title: Directed graph reachability
Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?

# Answer
> 1 votes
Use depth-first search, or breadth-first search, or any other graph search algorithm. You don't need Tarjan's algorithm.

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Greedy Heuristics with an Altered Subset Sum/Partition Problem
Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, the function outputs False.

Suppose we can use this function at any time, with any set of integers. Can we make a greedy algorithm using this function that will output one of the *specific* subsets that sum to half of a particular positive integer set?

The heart of the question: If we know at any time the boolean result of canPartition() on any set of integers, can we greedily use that to output the specific values of a partition?

# Answer
Suppose that a set $S$ of size more than 2 can be partitioned into two subsets of identical sum. One of these subsets contains at least two elements. If you merge these two elements (that is, replace them with a new element whose value is the sum of the values of the two elements), then the partition property still holds; and furthermore, given a partition of the new set, you can construct a partition of the original set.

You can find two elements in the same part by considering any three elements – two of them will be in the same part and so can be merged. This gives an algorithm for your problem with $O(n)$ oracle calls, where $n$ is the number of elements in the original set.
> 3 votes

---
Tags: algorithms, greedy-algorithms, heuristics
---


# Question
Title: How to write a coterminating, effectful program?
<sup>\[Using Idris for code examples and terminology, but the question is not about Idris *per se*\]</sup>

In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in operating systems and interactive applications" is to be modeled mathematically using codata, and that these sorts of programs can even written in a total functional programming language if they found to coterminate. Though I don't yet understand this to the depth in which he lays it out, the idea makes sense, and I'm familiar with the fact that Idris' totality checker (for example) considers cotermination. Thus, we might write the Unix `yes` program thus:

```
yes : Stream String
yes = "yes" :: yes

```

—except that this is not Unix `yes`, but intra-Idris `yes`. I cannot run this program and have it *do* what `yes` does: I need an effectful program. `Stream` is a `Functor`; it seems I want a `main : Stream (IO ())`. Let me make the example slightly more compelling by making this an interactive program, as @sigfpe speaks of:

```
stopOrPrint : String -> IO ()
stopOrPrint s = do
  maybeQ <- getChar
  if maybeQ == 'q'
  then pure ()
  else putStrLn s

main : Stream (IO ())
main = map stopOrPrint yes

```

But Idris does not accept programs whose main function has type `Stream (IO ())`. No problem, maybe if I used `traverse_ : Foldable t => Applicative f => (a -> f b) -> t a -> f ()` instead of `map`, I could get a `main` with the right type, `IO ()`. However `Stream` is not a `Foldable`, and I'm thinking it's not just because Brady forgot to implement it: how do you guarantee that you can fold a potentially infinite value into a finite value? Isn't that kind of crossing over from infinitude to finitude the *opposite* of totality?

So I'm stuck. I love the idea that with codata and cotermination, we could write a total operating system or even server. But when I actually go to write a socket server in Idris, I end up marking stuff `partial`; yet Idris' totality checker respects these ideas.

Am I running into a limitation of Idris (or any languages currently in existence), or a more fundamental limitation? If Idris just learned to take a `Stream (IO ())` for its `main`, would that solve it? I have a feeling that still doesn't address the underlying issue, because now you have a bunch of disconnected `IO`s: don't you actually want an infinite `IO` monad (can there be such a thing?)?

Is it possible to mix cotermination and effects, in a pure, total functional language? Has it been done? If not, what would it have to look like?

# Answer
In these sorts of cases, one idiomatic way is to run it with gas, and to create one non-total gas value to let you finish the program. Yes, perhaps Idris should offer a combinator for IO that allows full streams to be run, but this is sufficient, and doesn't affect the validity of anything else.

Seeing this, I'd agree that the IO monad should be coinductive, not inductive.

```
%default total

data Gas : Type where
  More : Lazy Gas -> Gas
  Done : Gas

runStream : Gas -> Stream (IO ()) -> IO ()
runStream (More g) (i :: is) = i >>= \_ => runStream g is
runStream Done _ = pure ()

partial
unbounded : Gas
unbounded = More unbounded

```
> 4 votes

---
Tags: functional-programming, halting-problem, turing-completeness, coinduction
---


# Question
Title: What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?
Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively. The time quantum is 2s.

After excuting for two seconds, will the processor excute p2 or continue excuting p1?

# Answer
> 0 votes
P1 arrives at time 0 and needs 3 seconds to process.

P2 arrived at time 2 and needs 1 second to process.

**Processing**

P1 arrives first and will process 2 second because time quantum is 2s. 1s left.

After processing P1 (2 seconds later), P2 will arrive.

It will completely process it and then return back to P1.

1 second later both processes are processed.

---
Tags: scheduling, process-scheduling
---


# Question
Title: Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?
Imagine trying to pick a random number from a pool of numbers that contains:

i1 times the number 1
i2 times the number 2
i3 times the number 3
... etc

For example picking a random number in a pool of
30 times the number 1
90 times the number 2
would yield 1 with 25% probability and 2 with 75% probability.

let NU be the number of unique numbers
let NT be the total number of numbers
In our example NU=2, NT=120.

Is there a way to achieve this in O(1) time and less than O(NT) space?

Edit: corrected probabilities in example.

# Answer
Why is $1$ returned with probability $33\\% \< \frac{1}{3}$ and not with probability $\frac{30}{30+90} = \frac{1}{4}$?

Anyway, this can be done in $O(NU)$ space (assuming $i\_1, \dots, i\_{NU}$ each fit in $O(1)$ memory words) and $O(1)$ time (assuming you can sample an integer between $1$ and $\sum\_{j=1}^{NU} i\_j$ uniformly at random in $O(1)$ time) using the alias method.

The Wikipedia page includes a pseudocode that uses rational numbers (which might lead to a loss of precision, depending on their representation). If you are interested in a C++ implementation that uses integers, like in your description, see here.
> 3 votes

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


# Question
Title: What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?
In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length $n$?

**If there is only a single non-terminal $A$**, then there are only two kinds of rules:

1. Intermediate rules of the form $ S \to \sigma S $.
2. Terminating rules of the form $ S \to \sigma $.

Such a grammar can then be rewritten in shorthand with exactly two rules, thusly:

$$\left\\{\begin{align} &S \enspace \to \enspace \\{\sigma, \tau, \dots\\} S = ΤS\\ &S \enspace \to \enspace \\{\sigma, \tau, \dots\\} = Τ'\\ \end{align}\right.\\ \space \\ (Τ, Τ' \subset \Sigma) $$

So, we simply choose one of the $Τ$ *(this is Tau)* symbols at every position, except for the last one, which we choose from $Τ'$.

$$ d = \frac {\lvert Τ\rvert^{n - 1} \lvert Τ' \rvert} {\lvert\Sigma\rvert^n} $$

I will call an instance of such language $L\_1$.

**If there are two non-terminals**, the palette widens:

1. Looping rules of the form $ S \to \sigma S $.
2. Alternating rules of the form $ S \to \sigma A $.
3. Terminating rules of the form $ S \to \sigma $.
4. Looping rules of the form $ A \to \sigma A $.
5. Alternating rules of the form $ A \to \sigma S $.
6. Terminating rules of the form $ A \to \sigma $.

In shorthand: $$\left\\{\begin{align} &S \enspace \to \enspace Τ\_{SS} S \\ &S \enspace \to \enspace Τ\_{SA} A \\ &S \enspace \to \enspace Τ\_{S\epsilon} \\ &A \enspace \to \enspace Τ\_{AA} A \\ &A \enspace \to \enspace Τ\_{AS} S \\ &A \enspace \to \enspace Τ\_{S\epsilon} \\ \end{align}\right.\\ \space \\ (Τ\_{SS}, Τ\_{SA}, Τ\_{S\epsilon}, Τ\_{AA}, Τ\_{AS}, Τ\_{S\epsilon} \subset \Sigma) $$

Happily, we may deconstruct this complicated language into words of the simpler languages $L\_1$ by taking only a looping rule and either an alternating or a terminating shorthand rule. This gives us four languages that I will intuitively denote $L\_{1S}, L\_{1S\epsilon}, L\_{1A}, L\_{1A\epsilon}$. I will also say $L^n$ meaning all the sentences of $L$ that are $n$ symbols long.

So, the sentences of this present language *(let us call it $L\_2$)* consist of $k$ alternating words of $L\_{1S}$ and $L\_{1A}$ of lengths $m\_1 \dots m\_k, \sum\_{i = 1 \dots k}m\_i = n$, starting with $L\_{1S}^{m\_1}$ and ending on either $L\_{1S\epsilon}^{m\_k}$ if $k$ is odd or otherwise on $L\_{1A\epsilon}^{m\_k}$.

To compute the number of such sentences, we may start with the set $\\{P\\}$ of integer partitions of $n$, then from each partition $P = \langle m\_1\dots m\_k \rangle$ compute the following numbers:

1. The number $p$ of distinct permutations $\left(^k\_Q\right)$ of the constituent words, where $Q = \langle q\_1\dots\ \rangle$ is the number of times each integer is seen in $P$. For instance, for $n = 5$ and $P = \langle 2, 2, 1 \rangle$, $Q = \langle 1, 2 \rangle$ and $p = \frac{3!}{2! \times 1!} = 3$
2. The product $r$ of the number of words of lengths $m\_i \in P$, given that the first word comes from $L\_{1S}$, the second from $L\_{1A}$, and so on *(and accounting for the last word being of a slightly different form)*:

$$ r = \prod\_{i = 1, 3\dots k - 1}\lvert L\_{1S}^{m\_i} \rvert \times \prod\_{i = 2, 4\dots k - 1}\lvert L\_{1A}^{m\_i} \rvert \times \begin{cases} & \lvert L\_{1S\epsilon}^{m\_k} \rvert &\text{if $m$ is odd}\\ & \lvert L\_{1A\epsilon}^{m\_k} \rvert &\text{if $m$ is even}\\ \end{cases} $$

If my thinking is right, the sum of $p \times r$ over the partitions of $n$ is the number of sentences of $L\_2$ of length $n$, but this is a bit difficult for me.

**My questions:**

* Is this the right way of thinking?
* Can it be carried onwards to regular grammars of any complexity?
* Is there a simpler way?
* Is there prior art on this topic?

# Answer
> 2 votes
If I understand the question, your problem is the following:

> Given a regular language $L$ over alphabet $\Sigma$ and a positive integer $n$, compute the probability that a word chosen uniformly at random from $\Sigma^n$ will be in $L$.

That's equivalent to computing $|L \cap \Sigma^n|$, i.e., the cardinality of the language $L \cap \Sigma^n$. Note that $L \cap \Sigma^n$ is regular, so your problem is equivalent to the problem of counting the number of words in a finite regular language. This is a standard problem that is well-studied; see https://cstheory.stackexchange.com/q/8200/5038, https://cstheory.stackexchange.com/q/32473/5038, Why isn't it simple to count the number of words in a regular language?, Counting the number of words accepted by an acyclic NFA. Here are some results:

* If the language $L$ is specified as a DFA or as an unambiguous regexp, then the problem can be solved in polynomial time.
* If the language $L$ is specified as a NFA and $n$ is specified in unary, the problem is $\\#P$-complete. Thus, there is an exponential-time algorithm but you should not expect a polynomial-time algorithm.
* If the language $L$ is specified as a NFA and $n$ is specified in binary, the problem is $PSPACE$-complete. Thus, you should not expect a polynomial-time algorithm.

There are approximation algorithms that you might be able to use in practice to estimate the probability you're seeking (using a SAT solver as a subroutine).

---
Tags: regular-languages, formal-grammars, combinatorics, probability-theory
---


# Question
Title: Why $o(\log n)$ bits instead of $O(\log n)$ bits needed for succinct data structure?
Succinct data structure = succinct representation of data + bits for indexing. Link

Let $S$ be subset of of $\\{1,2,\ldots,n\\}$ then $\lceil \log (2^n) \rceil + o(\log n )$ bits are needed in succinct representation. The $o(\log n)$ bits needed for the indexing of the succinct data structure. I have a doubt, why $o(\log n)$ not $O(\log n)$ bits? Where $O(\log n)$ do not play any role when talking about conventional representation of data.

# Answer
Note that $\lceil \log(2^n) \rceil = n$.

An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure). An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine.

An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure). Similarly, an algorithm that uses $1.01n$ bits would not be fine.

This is just what the definition says. You could imagine some other definition, but that's what the standard definition of "succinct data structure" is saying. It is saying that you can use a little bit more space than required by the information-theoretic lower bound, but not too much -- not a multiplicative factor.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Time-complexity for basic multiplication and division algorithms
The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen.

p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ additions of bits are required for all n additions".

Why isn't this algorithm $O(n)$? I can see only two non-nested for loops.

p.254 says that "this means that we need $O(n^2)$ bit operations to find the quotient and remainder when a is divided by d".

Why isn't this algorithm $O(n)$? I can see only one while loop.

# Answer
Time complexity is often about the number of loop operations, but not always.

In the multiplication algorithm, the step $b := b + c\_j$ is actually adding two n-bit numbers. Adding two n-bit numbers is not an elementary operation, but takes itself O(n) steps, so the second loop has n iterations, each iteration runs in O(n), therefore a total of $O(n^2)$.

The division algorithm is totally off. There is only one loop (but same as before, each iteration takes O(n)). However, look carefully how many iterations the loop has. It doesn’t have n iterations, the number of iterations can be much much higher. The algorithm is very much suboptimal. How many iterations for 64 bit signed integers if $a = 2^{63}-1$ and d = 1?
> 2 votes

# Answer
The one loop that you see is for number of additions. But it is also assuming number of bits to be to the order of n. For one iteration, you will perform operation over O(n) bits. For n iterations, it will be to the order of n squared.
> 2 votes

---
Tags: algorithms, time-complexity, big-o-notation
---


title: Black Box Decision problem for NFA

text:
# Question
Title: Black Box Decision problem for NFA
Suppose we are given an NFA $M$ (without $\epsilon$-transitions) that we only know the alphabet $\Sigma$ and the number of states $|Q|$ but we do not know any other details of the NFA. We want to develop a black box algorithm that can test if $L(M)=\Sigma^{\*}$. My idea is that we can feed every string up to size $|\Sigma|^{|Q|-1}$, if every strings are accepted, then $L(M)=\Sigma^{\*}$. Since all strings up to size $|\Sigma|^{|Q|-1}$ must go through every reachable state in $M$, if all of them get accepted then no matter what string is input, it will be accepted. Am I correct?

# Answer
> 2 votes
Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of length $n$ can be converted to an NFA having $O(n)$ states, this gives, for infinitely many $n$, an NFA having $n$ states such that the shortest string not accepted by the NFA has length $2^{\Omega(n)}$.

Conversely, if an NFA having $n$ states doesn't accept all strings, then it must reject some string of length shorter than $2^n$. This follows from the pumping lemma once you convert the NFA to a DFA. Hence the construction in the paper mentioned above is optimal up to the constant in the exponent.

# Answer
> 1 votes
No, that is not correct. Consider the following NFA over the one-symbol alphabet $\Sigma=\\{1\\}$:

```
      ,-----------------------.
      |-----------.           |
      v           |           |
a --> b --> c --> d --> e --> f
|
V
g

```

Assume that all edges are labelled with the symbol $1$, except that the edges $a\to b$ and $a \to g$ are $\epsilon$-transitions. Assume that states $c,d,e,f,g$ are accepting states, and $a,b$ are non-accepting states. This NFA has 7 states. It also accepts all strings of length up to 6 (in fact, all strings of length up to 14). However, it does not accept the input $1^{15}$ (of length 15).

However, your method *does* work for a DFA. It just doesn't work for a NFA.

# Answer
> 0 votes
No, you need to search up to exponentially long strings. See this answer to a related question on cstheory.SE: https://cstheory.stackexchange.com/a/3502/2367

---
Tags: automata
---


# Question
Title: Is the $k$P$k$N-3SAT problem NP-complete?
Consider the following 3-SAT variant defined over the variables $x\_1,\ldots,x\_n$. In the $k$P$k$N-3SAT problem each variable $x\_j$, $j \in \[n\]$, occurs exactly $k$ times as a positive literal in $\phi$, and exactly $k$ times as a negative literal in $\phi$, where $\phi$ is a 3-CNF formula. The problem is then to decide if such a formula has a satisfying assignment.

> Is the $k$P$k$N-3SAT problem NP-complete?

In the $m$P$n$N-SAT problem each positive literal occurs exactly $m$ times in $\phi$, and each negative literal occurs exactly $m$ times in $\phi$, where $\phi$ is a CNF formula. It was shown in \[1\] that $2$P$1$N-SAT is NP-complete. This hints that the $k$P$k$N-3SAT problem is hard as well.

The $1$P$1$N-SAT is apparently easy, see a related question and answer here. Is $k$P$k$N-3SAT perhaps hard already for $k \geq 2$?

---

\[1\] Yoshinaka, Ryo. "Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete." Term Rewriting and Applications. Springer Berlin Heidelberg, 2005. 235-249.

# Answer
1) 2P2N-3SAT is NP-complete

(Edit to take into account all comments below)

Take a 2P1N-SAT instance, check the all-1 vector is not a model, then add the clause with all variables negated to the formula to transform it into a 2P2N-SAT instance.

For each 1-clause $(a)$ in the new 2P2N formula, replace it by the three following 3-clauses : $(a \lor x \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)$ where $x,y$ are fresh 2P2N variables (i.e. appearing twice as positive literals and twice as negative literals).
For each 2-clause $(a \lor b)$ in the formula, replace it by the six following 3-clauses : $(a \lor b \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)(x \lor z \lor \lnot z)(z \lor t \lor \lnot t)(\lnot z \lor t \lor \lnot t)$ where $x,y,z,t$ are fresh 2P2N variables.
Keep all 3-clauses in the formula.
For each $k$-clause ($k\>3$) in the formula, transform it into a set of 3-clauses by the usual way, which does not change the number of occurences of positive (negative) literals of the taken $k$-clause, but add only extra variables which appear once as a positive literal and once as a negative literal. For each such new variable $x$, add the two following clauses to the 3-CNF formula : $(x\lor y \lor \lnot y)$ and $(\lnot x \lor \ y\lor \lnot y)$ where $y$ is a fresh 2P2N variable.

All these transformations can obviously be done in polynomial time and transform the 2P1N-SAT instance into a 2P2N-3SAT instance. The NP-complete 2P1N-SAT problem is then reducible to the 2P2N-3SAT problem.

2) The extension to $k$P$k$N-3SAT can be done in the same spirit (a bit longer) to prove it is NP-complete as well.
> 4 votes

# Answer
As confirmed independently in another answer, 2P2N-3SAT is already NP-complete. Another name for the fragment you are interested in is (3, B$k$)-SAT where "B" stands for Balanced and indicates that there are the same number of positive and negative occurences of the variables, $k$ is the number of positive and the number of negative occurences, and the 3 indicates the size of clauses: we are indeed in a fragment of 3SAT.

In particular, 2P2N-3SAT is the same as (3, B2)-SAT and this fragment was proven NP-complete as Theorem 1 in \[1\].

A related natural question is: given that 2P2N-3SAT is NP-complete, and given that 2P1N-SAT is NP-complete, what about about 2P1N-3SAT? This one turns out to be trivial: all instances are always satisfiable, Theorem 2.4 in \[2\]. If you allow some clauses to have fewer than 3 variables, then the satisfiability problem is NP-complete as observed in Theorem 2.1 in \[2\].

\[1\] Piotr Berman, Marek Karpinski, Alexander D. Scott. Approximation hardness of short symmetric instances of MAX-3SAT, Electronic Colloquium on Computational Complexity, Technical Report TR03-049 (2003)
\[2\] Tovey, Craig A. A simplified NP-complete satisfiability problem, Discrete applied mathematics 8.1 (1984): 85-89.
> 3 votes

---
Tags: complexity-theory, np-complete, satisfiability, decision-problem
---


# Question
Title: Derive a while loop runs in $\Theta( \sqrt{n} )$
I know for a fact that algorithm **A** runs in $\Theta(\sqrt{n})$, but how does one derive that fact?

Algorithm **A**

```
i = 0
s = 0
while s <= n:
    s += i
    i += 1

```

Here is what I am thinking. We know that **A** is upper-bounded by O(n), as we increment $s$ by more than 1 in each iteration. We also know that it must be lower-bounded by $\log n$, as we increment $s$ with by something less than $2^i$ in each iteration. (Correct me if I am wrong, these are just my thoughts ...).

Now, what else can we say about **A**? How do we derive that its time complexity is $\Theta(\sqrt{n})$?

# Answer
Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$.

$$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \Theta(\sqrt{n})$$
> 5 votes

# Answer
After the first sqrt(n) iterations, s is increased by more than sqrt(n) in each iteration. Therefore at most 2 sqrt(n) iterations are needed to make s \> n.

On the other hand, in the first sqrt(n) iterations, s is increased at most by sqrt(n) in each iteration, so sqrt(n) iterations are not enough.

This means the number of iterations is $\Theta(n^{1/2})$.
> 0 votes

# Answer
## Process of elimination

A, perhaps, easier method to derive the time complexity is by process of elimination. This is especially the case if you get this type of question in a multiple choice exam. That said, this method is far from as rigorous as OmG's answer.

Okay, we know that **A** is upper-bounded by O(n), as we increment $s$ by more than 1 in each iteration.

We also know that **A** must be lower bounded by $\log n$, as we increment $s$ by something less than $2^i$ each iteration.

Okay, so far so good.

Knowing our table of common time complexities, we can deduce that the time complexity of our loop must be either polylogarithmic time ($(\log n)^2$) or a fractional power. We now notice that we are not dealing with polylogarithmic time as that would imply having some variables doubbeling, for instance:

```
i = 1                // O( (log n)^2 )
while i ≤ n
  j = i
  while j ≤ n
    j = 2 ∗ j
  i = 2 ∗ i

```

, which is far from what we are dealing with, so we can eliminate this possibility.

... We are left with one possibility: a fractional power, aka. a squareroot of some sort.
> 0 votes

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


# Question
Title: Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$
I know for a fact that algorithm **A** runs in $\Theta(n)$, but how does one derive that?

Algorithm **A**

```
i = 1
while i ≤ n
  s = 0
  while s ≤ i
    s = s + 1
  i = 2 ∗ i

```

The inner loop is clearly $O(i)$ (linear time).

The outer loop is clearly $O(\log n)$ (logarithmic time).

A visualitation of the loop in terms of an input $n$ would look as follows:

, the black lines represents the amount of work or iterations required in terms of $n$.

# Answer
$\sum\_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.
> 2 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, big-o-notation
---


# Question
Title: How to find out the complement of a language of turing machines?
With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example.

L={M∣M is a TM that halts on empty tape after even transition steps} What's the complement of L would it be:

1. L={M∣M is a TM that does not halt on empty tape after even transition steps}
2. L={M∣M is a TM that halts on empty tape after odd transition steps}

Please give me your train of thought when coming up with a complement for an automaton.

# Answer
You cant find the complement of a $TM$ for undecidable languages. A decidable language is such that a $TM$ which recognizes language membership, always halts with a *yes*. In this case finding the complement of the machine is simple, just reverse the *yes* with the *no*, obtaining the complement of the original decision problem. I leave to you the task of determining whether the language of your example is decidable or not.

**HINT**: you can compare it with the **Halting problem** or $ATM$
> 1 votes

---
Tags: turing-machines, automata
---


title: Why do errors occur in programming?

text:
# Question
Title: Why do errors occur in programming?
I like to reduce the number of exceptions raised in my code, and I thought it might help to consider why these exception are raised in the first place, and whether they are a really a fundamental part of code or just an artefact of not really finishing the program.

As a related note I hear OS programming requires avoiding errors where possible, perhaps there are some answers there.

# Answer
> 3 votes
Errors occur in programming because programs are written by humans and humans make errors.

# Answer
> 0 votes
It's not completely clear what type of exceptions you are asking about, but defensive programming may be relevant.

---
Tags: software-engineering
---


title: Possessive Kleene star operator

text:
# Question
Title: Possessive Kleene star operator
Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"?

In other words, if `*` would always match as much as possible and no backtracking is allowed, would I still be able to express any regular language?

Let's say that `@` is the possessive `*` operator.

There are cases where it doesn't matter: `a*b` and `a@b` both will match any string with 0 or more $a$ followed by a $b$.

However there are cases where being possessive is relevant: `a.*b` will match any string that starts with $a$ and ends with $b$ but `a.@b` will never match any string as the greedy `@` will eat any character, including the ending $b$. The equivalent expression would be `a[^b]@b`.

One may be tempted to think that for any non-possesive expression there is an equivalent possessive expression and viceversa but I wasn't able to find any proof of this.

I'm limiting myself to `*` considering `a+` equivalent to `aa*`.

As D.W. suggested in the comments below, I tried to start from the DFA. I didn't go much far, as this seems to have more to do with the way the non-determinism is handled, rather than with the structure of the automaton.

Could anyone point me in the right direction?

**EDIT 3**

I've posted an answer that I believe is correct.

**EDIT 2**

(REMOVED)

**EDIT 1**

(It has pointed out to me that the right term to use would be "possessive" (http://www.regular-expressions.info/possessive.html) rather than "greedy". Thanks.)

# Answer
> 5 votes
I will share below my attempt to prove that you can express every regular language as a regular expression using just the $+$ and $@$ operators. Unfortunately, my attempt at a proof has a gap. Perhaps you can repair the gap. My attempt based upon Brzozoswki's method for generating regular expressions, so I'll assume you are already familiar with how that works.

---

First, some definitions and other preliminaries.

**Definition.** Define $A^+$ to be the language of one or more words from $A$, i.e., $A^+ = \\{a\_1 a\_2 \cdots a\_k \mid k \ge 1, a\_1,\dots,a\_k \in A\\}$. In other words, $A^+ = A^\* \setminus \\{\epsilon\\}$.

**Definition.** $\newcommand{\rp}{\backslash\backslash}$ For sets $A,B \subseteq \Sigma^\*$, define $A\rp B$ by $A\rp B = (A^\*\backslash B) - (A^+ \Sigma^\*)$, where $A\backslash B$ is the left quotient, and $-$ represents the difference of two sets. In other words, $A\rp B$ is the smallest set $C \subseteq \Sigma^\*$ such that $A^\* B = A^\* C$ and such that no word in $A^+$ is a prefix of any word in $C$.

Example: $\\{01\\}\rp \\{0101010,101\\} = \\{0,101\\}$.

Note that if $A,B$ are regular languages, then $A\rp B$ is also a regular language and can be computed effectively from $A,B$. (This follows from the standard closure properties of regular languages.)

**Definition.** The semantics of regular expressions using the $+$ and $@$ operators are defined inductively:

* $L(w) = \\{w\\}$ if $w \in \Sigma^\*$
* $L(A\_1+A\_2+\dots+A\_k) = L(A\_1) \cup L(A\_2) \cup \dots \cup L(A\_k)$
* $L(A^@ B) = \\{ab : a \in L(A^\*), b \in L(B), b \notin L(A^+ \Sigma^\*)\\}$
* $L(w B) = \\{wb : b \in L(B)\\}$ if $w \in \Sigma^\*$
* $L(A^@) = L(A^\*)$
* $L((A\_1+A\_2)B) = L(A\_1B + A\_2 B)$, $L(A(B\_1+B\_2)) = L(AB\_1 + AB\_2)$
* $L(A\_1 A\_2 \cdots A\_k) = L(A\_1 (A\_2 \cdots A\_k))$

(As a consequence, every regular expression using $+,@$ can be equivalently written as a sum of terms of the form $A\_1 A\_2 \cdots A\_k$ where each $A\_i$ is either of the form $w\_i$ or $C\_i^@$ for some $w\_i \in \Sigma^\*$ and some regular expression $C\_i$ using $+,@$. Once it is rewritten in that sum-of-products form, the semantics of the resulting expression is given by the definition above.)

For instance, we have the following property: if there is no word in $L(A^+)$ that is a prefix of any word in $L(B)$, then $L(A^@ B) = L(A^\* B)$.

In what follows, I won't try to distinguish between a regular expression $E$ and its corresponding language $L(E)$.

Now we can prove a generalization of Arden's lemma.

**Lemma 1.** Let $A,B \subseteq \Sigma^\*$ be given, and assume $\epsilon \notin A$ and no word in $A^+$ is a prefix of any word in $B$. Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$). Then the least solution to this equation is $X=A^@ B$.

Proof. Arden's lemma says the least solution is $X=A^\* B$. Now, since no word in $A^+$ is a prefix of any word in $B$, in fact $A^\* B = A^@ B$, as there can be no ambiguity about how much the $\*$ operator gobbles up.

**Lemma 2.** Let $A,B \subseteq \Sigma^\*$ be given, and assume $\epsilon \notin A$. Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$). Then the least solution to this equation is $X=A^@ C$ where $C=(A\rp B)$.

Proof. Arden's lemma says the least solution is $X=A^\* B$. As noted above, $A^\* B = A^\* C$. Moreover, no word in $A^+$ is a prefix of any word in $C$, so $A^\* C = A^@ C$.

Now given any regular language $L$, we can apply Brzozoswki's method to it, but using Lemma 2 above instead of Arden's lemma. It's tempting to hope that the result will be a regular expression for $L$ that uses only the operators $+$ and $@$, but unfortunately there's a gap: I don't know whether one can prove that $A\rp B$ can be represented as a regular expression using only the $+$ and $@$ operators. So, this proof method has a big gaping hole in it.

But perhaps someone will see a way to build on this and prove the desired result.

# Answer
> 0 votes
I believe I can prove that:

* a RE using only *possessive* operators is equivalent to a RE without *possessive* operators.
* any RE can be *rewritten* to an equivalent RE that uses only *possessive* operators.

For two expressions $A$ and $B$ to be equivalent means that they define the same language: $$A\equiv B \implies L(A) = L(B)$$

Let's mark with "$\hat{\ }$" the possessive operators.

I will use regular expression extended with the $\cap$ and $\neg$ operators.

### 1. Possessive Alternation

$$ A\ \hat{|}\ B \equiv A \ |\ (B \cap \neg A) $$

Which express the fact that if $A$ matches, $B$ is not even tried. In fact, if $A$ fails the only elements of $B$ that can match are those that are not in $B\cap A$, otherwise $A$ would have matched.

Actually, it's easy to see that: $$ A\ \hat{|}B\ \equiv A\ |\ B $$

because any string $s\in B$ will match $A\ |\ (B\cap \neg A)$, either because it is in $A\cap B$ (and hence in $A$) or because it's in $(B\cap \neg A)$. This means that it's not important to say if $|$ is possesive or not.

### 2. Possessive Repetition

$$ A \hat{\*} B \equiv A * (B \cap \neg A) $$

In words: "$A\hat{\*}B$ matches a, possibly empty, sequence of $A$ followed by an element of $B$ which is not in $A$".

The reason is that $A\hat{\*}$ will consume any possible element of $L(A)$, including those element of $L(B)$ wich are in $L(B\cap A)$.

It's easy to see that: $A\cap B = \emptyset \implies A\hat{\*}B \equiv A * B$

and that: $B\subset A \implies A\hat{\*}B = \emptyset $

The last expressions explains why an expression like `.@x` can never match.

It is also clear that at the end of an expression $A\hat{\*}\equiv A\*$.

As usual, $A\hat{+} \equiv A A\hat{\*}$

### 3. Non-possessive Repetition

We can also express the "greedy non-possessive repetition" using only possessive operators: $$A * B = A\hat{\*} B\ |\ ((A\cap \neg B)\\;\hat{\*}\\;(B \cap A))\hat{+} $$

The first term of the alterantion will match any sequence of $A$ followed by a $B$ that do not match $A$, the second will match the longest sequence of $A$ that end with a $B$ which is also in $A$ (otherwise it would have matched in the first alternation).

The non greedy version of $\*$ (let's denote it with $\*^?$) would be: $$A {\*^?} B = A\hat{\*} B\ |\ (A\cap \neg B)\\;\hat{\*}\\;(B \cap A) $$

### 4. Optional Match

Reasoning in the same way, we can see that: $$ A \hat{?} B = A B \ |\ (B \cap \neg A) \\ A ? B = A \hat{?} B \ |\ (B \cap A) $$

### 5. Conclusions

Considering point 1-4 above, and reasoning by induction, we can prove that we can define any possible regular language using only possessive operators. Which answers my question.

### 6. Open points

* **Formality** I'm well aware that what I wrote above is not a formal proof. I'm sure the reasoning is correct but a formal proof could highlight further details or additional hypotesis that are needed and I might have missed. Also, the properties of the possessive operators should be formalized (are they associative, left distributive, ...?).
* **Practicality** Since I've used $\cap$ and $\neg$, it is left to determine if it is practical to use only possessive operators. There might be some RE that would become extremely complex to write with only possessive operators.
* **Speed** Since there will be no ambiguities and the only source of backtracking is the alternate operator. I'm pretty sure that this means that the match can be done in linear time but it should be proven.

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


title: What kind of error are these?

text:
# Question
Title: What kind of error are these?
I was following a discussion on a forum where a person has asked whether the following generates lexical errors or not,

> (1) char p="gate;
>
> (2) int /\* n;
>
> (3) printf("%d, n);

When I tried to run them on my CPP compiler I got these errors respectively for the following 1, 2 and 3

When I looked them up on the internet they all are appearing to be Syntax errors.. Am I right? or are they lexical errors?

# Answer
The C standard does not bother to distinguish between different kinds of errors encountered during parsing, but it is possible to categorise errors according to which clause of the standard applies.

The second line in your query (`int /* n;` -- assuming that there is no `*/` in the remaining program text) is covered by a requirement in the description of phases of translation, §5.1.1.2/1; in particular, in phase 3: (emphasis added)

> 3. The source file is decomposed into preprocessing tokens and sequences of white-space characters (including comments). **A source file shall not end in a partial preprocessing token or in a partial comment.** Each comment is replaced by one space character. New-line characters are retained. Whether each nonempty sequence of white-space characters other than new-line is retained or replaced by one space character is implementation-defined.

The other two errors are also produced in phase 3, because the unmatched quote cannot be decomposed into a preprocessing token. The error is mentioned specifically in §6.4/3:

> 3. A *token* is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. **If a `'` or a `"` character matches the last category, the behavior is undefined.**

That probably justifies the use of the phrase "lexical error", at least as an informal description.
> 2 votes

---
Tags: syntax
---


# Question
Title: Is Newton's algorithm really this much better than conjugate gradient descent?
I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm.

I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, while the conjugate gradient takes 2000 iterations (and regular gradient descent takes 5000 iterations).

I know what's causing the problem too: the learning rate. In Newton's method, a learning rate of $\alpha = 1$ works. But I can't use this in the gradient descent methods, where such a choice of $\alpha$ diverges. In these methods, I am forced to use $\alpha = 0.01$.

But anyways, 5 iterations vs thousands of iterations is still an absurd difference. Is Newton's method really this good??!

# Answer
> 1 votes
The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing. We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me.

There are some functions where Newton's method will be vastly better. For instance, with a quadratic function, where a few iterations of Newton's method will suffice to get a very precise answer; yet gradient descent might take many iterations to get similar precision. This can be partly explained theoretically by understanding that Newton's method often converges quadratically or faster (though for some bad cases it can converge more slowly), while gradient descent typically converges sub-linearly for convex functions or linearly for strongly convex functions (and for bad cases it can converge much more slowly), so in a theoretical sense Newton's method often requires fewer iterations than gradient descent.

Conversely, there are also some functions where (conjugate) gradient descent will be better, for instance because one iteration of gradient descent is much faster than one iteration of Newton's method. One example would be training deep neural networks, where gradient descent works very well but Newton's method would be painfully slow due to the very high dimensionality and the time it takes to do a single iteration of Newton's method.

I would caution against drawing a conclusion about the performance of Newton's method on all functions, based on an empirical observation of its performance on one particular function (a sample size of $n=1$).

---
Tags: optimization, gradient-descent
---


# Question
Title: What is a sticky bit in computer architecture?
I am reading about a counter implementation in RISC Architecture. The specification reads,

> Sticky overflow bit is set when the counter wraps through zero.

I can infer that the overflow bit is set when the counter reaches maximum value(all 1's) and another increment makes it 0(all 0's). What is the meaning of the sticky overflow bit?

# Answer
A sticky overflow bit means that the next operation that does not overflow (but would set the bit if it did) will not clear the bit. The value is sticky/persistent and must be cleared to detect newer overflows.
> 3 votes

---
Tags: computer-architecture
---


title: Range intersection with bounding box?

text:
# Question
Title: Range intersection with bounding box?
I have a lexicographical order on integer $n$-tuples, where $(x,y,\dots) \> (a,b,\dots)$ if $x\>a$ or if $x=a$ and $y\>b$, and so on to the end of the tuple (I called it lexicographic because of its similarity to the natural order on strings of $n$ characters). In this order I have a range, defined inclusively by a pair of tuples.

I also have a rectangular box in $n$ dimensions defined by a pair of integer $n$-tuple corners. A tuple is in the box if every one of its elements is greater than the corresponding element in the first corner, and also less than the corresponding element in the second corner.

Given two tuples to serve as the ends of the range (under the lexicographic ordering), and another two tuples defining the corners of the box, I would like to determine if there is any overlap between the tuples in the range and the tuples in the box. What is the most elegant way to do this?

# Answer
> 1 votes
I think you can answer this in $O(n)$ time with a recursive algorithm, as follows. It basically boils down to an ugly case analysis.

# Over the real numbers

Let me start by assuming you are working over the real numbers, to make it easier to present the ideas.

Suppose the range is $(r\_1,r\_2,\dots,r\_n) \ldots (s\_1,s\_2,\dots,s\_n)$ and the bounding box has corners $(b\_1,\dots,b\_n)$ and $(c\_1,\dots,c\_n)$ with $b\_i \le c\_i$ for all $i$. There are four cases:

* If the intervals $\[r\_1,s\_1\]$ and $\[b\_1,c\_1\]$ don't overlap, then there is no overlap between your range and your bounding box.
* If $r\_1=s\_1$ or $r\_1=c\_1$, then check whether $b\_1 \le r\_1 \le c\_1$ and then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $r\_1$ (i.e., the range is $(r\_2,\dots,r\_n) \ldots (\infty,\dots,\infty)$ and the box has corners $(b\_2,\dots,b\_n)$ and $(c\_2,\dots,c\_n)$).
* If $r\_1\<s\_1$ and $s\_1=b\_1$, then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $s\_1$ (i.e., the range is $(-\infty,\dots,-\infty) \ldots (s\_2,\dots,s\_n)$ and the box has corners $(b\_2,\dots,b\_n)$ and $(c\_2,\dots,c\_n)$).
* Otherwise, the intervals $\[r\_1,s\_1\]$ and $\[b\_1,c\_1\]$ overlap at more than two points. In this case, there is guaranteed to be an overlap between your range and your bounding box. In particular, pick a value $x\_1$ that is in the overlap and such that $r\_1\<x\_1\<s\_1$; then $(x\_1,b\_2,\dots,b\_n)$ is in the range and in the bounding box.

It is easy to see that this runs in $O(n)$ time, because the running time satisfies the recurrence $T(n) = T(n-1) + O(1)$.

# Over the integers

If you are dealing with integers, then it suffices to add the following cases just before the "Otherwise":

* If $s\_1=r\_1+1$, recurse twice: recurse on the range $(r\_1,r\_n,\dots,r\_n)\ldots (r\_1,\infty,\dots,\infty)$ and recurse again on the range $(s,-\infty,\dots,-\infty) \ldots (s\_1,s\_2,\dots,s\_n)$ (leaving the bounding box alone). If either of them finds a point of overlap, then you have found an overlap between your range and your bounding box. (\*)
* If $c\_1=b\_1+1$, then there is a point of overlap. (If $r\_1\<b\_1\<c\_1\le s\_1$, use $(b\_1,\dots,b\_n)$); if $r\_1 \le b\_1\<c\_1 \< s\_1$, use $(c\_1,\dots,c\_n)$); those are the only two possibilities.)

The running time with this modification remains $O(n)$. It takes a little more work to see why, though. Naively, we obtain the recurrence $T(n)=2 T(n-1) + O(1)$, due to need to recurse twice in the case marked (\*); and this recurrence satisfies $T(n)=O(2^n)$, which is very bad. Fortunately, this is an overly loose upper bound. Note that when $(r\_1,\dots,r\_n) = (-\infty,\dots,-\infty)$ or $(s\_1,\dots,s\_n)=(\infty,\dots,\infty)$, then we never invoke the case (\*) in any subsequent recursion. So, when running on one of those inputs, the running time is $O(n)$. Moreover, the case (\*) recurses on inputs of this form. Thus, we will never invoke case (\*) more than once in the entire recursion tree. Thus, the entire recursion tree can involve at most $2n$ recursive calls. Thus, the total running time remains $O(n)$.

This algorithm looks a pretty messy, with at least 6 different cases. Perhaps there is a cleaner way to do it.

---
Tags: algorithms
---


# Question
Title: No FSM/Regex exists for this language right?
The language is this:

$L = \\{w \in \\{a,b\\}\*:$ each $a$ has a matching $b$ somewhere in $w$ $\\}$

This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, right?

# Answer
> 2 votes
Expanding on Daniel Martin's answer. None of the following interpretations yields a regular language:

* $L = \\{ w \in \\{a,b\\}^\* : \exists n \ge 0, \\; w = a^n b^n \\}$
* $L$ contains all the words $w \in \\{a,b\\}^\*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$.
* $L$ contains all the words $w \in \\{a,b\\}^\*$ such that the number of $a$s in $w$ is equal than the number of $b$s in $w$.
* $L$ contains all the words $w \in \\{a,b\\}^\*$ such that there is a injective/bijective mapping that maps each a $a$ that appears in a generic position $i$ in $w$ with a $b$ in $w$ that appears in a position $j\>i$.

The proof is the same for all cases: if $L$ was regular then, for a sufficiently large $n$, the word $w = a^n b^n \in L$ could be written as $w = a^{n-k} a^k b^n$ (with $1 \le k \le n)$ in such a way that $a^{n-k}a^{k \cdot h} b^n \in L$ for all choices of $h \in \mathbb{N}$ (see pumping lemma for regular languages). This is a contradiction since $a^{n-k}a^{2k} b^n = a^{n+k}b^{n} \not\in L$.

# Answer
> 1 votes
As the comments say, it isn't completely clear what you mean by "matching", but if you mean that for any positive integer $n$, the string $\mathtt{a}^n\mathtt{b}^n$ (that is, the string of $n$ "$\mathtt{a}$"s followed by $n$ "$\mathtt{b}$"s) is in the language, but $\mathtt{a}^n\mathtt{b}^{n-1}$ is *not* in the language, then what you say is correct: $L$ is not a regular language because you would need an infinite number of states, at least one for every string of the form $\mathtt{a}^n$.

---
Tags: finite-automata, regular-expressions
---


# Question
Title: What is the meaning of uniform distribution of elements in an array?
I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?

# Answer
> 2 votes
Suppose that the array $A$ is chosen in the following way:

1. Sample $n$ real numbers uniformly from the interval $\[0,1\]$.
2. Sort the $n$ samples.

Suppose that you choose a further uniform random variable $x$ from the interval $\[0,1\]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.

# Answer
> -2 votes
Usually an array is considered as uniformly distributed when the difference between the elements are equal or almost same. Example 1: 1,2,3,4,5,6 (Difference is 1)

Example 2: 10,20,31,40,55,60,73,80(Here the difference between the two adjacent elements are almost close to 10).

Interpolation search is to be used when the given array is both sorted and uniformly distributed to have log(log n) time complexity.

---
Tags: algorithms, data-structures, search-algorithms, arrays
---


# Question
Title: What is the sequence of numbers for N = 6?
The numbers in the table below are the result of executing an algorithm that has one parameter N, a non-negative integer, and produces sequences of integers as outputs. For values of N from 0 to 5, the algorithm produces the following sequences of numbers as outputs.

# Answer
Here is one possible algorithm:

* If $N = 0$, output the empty string.
* If $N = 1$, output "0 1".
* If $N = 2$, output "0 2 2 3".
* If $N = 3$, output "0 2 4 3 4 5".
* If $N = 4$, output "0 2 4 6 4 5 6 7".
* If $N = 5$, output "0 2 4 6 8 5 6 7 8 9".
* Otherwise, output the empty string.

Now, this is probably not the answer they were expecting, but it's perfectly valid.

(The answer they expected was: output the first $N$ even integers starting with zero, and then the first $N$ integers starting with $N$.)
> 8 votes

---
Tags: algorithms, logic-programming
---


# Question
Title: Minimizing the iterative sum of pairs of numbers in a list
Given the tuple (list, value):

$$\left(\left\[x\_1, x\_2, \cdots x\_n\right\], y\right)$$

You may choose two adjacent values in the list to modify the tuple as:

$$\left(\left\[x\_1, x\_2, \cdots x\_{i-1}, (x\_i + x\_{i+1}), x\_{i+2} \cdots x\_n\right\], y + x\_{i} + x\_{i+1}\right)$$

Iterate until:

$$\left(\left\[\sum\_i x\_i\right\], y + z\right)$$

What is the optimal set of choices that minimizes $z$?

Intuitively, you never want to operate on the largest number in the list. But the largest number in this list changes as you add values together. In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.

A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers. This solution, while close, is not equivalent to the value returned by brute force search. This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.

# Answer
> 2 votes
I will assume that initially $y=0$, as this makes no difference in your problem.

Look at the very last two elements $a,b$ that you will apply your operation on: The tuple is $(\[a,b\], y$) and, at the next iteration, it will necessarily be $(\[a+b\], $y+a+b$)$, since $a+b = \sum\_{i=1}^n x\_i$ is a constant, you only want to minimize $y$.

Notice that $a$ (resp. $b$) must have been obtained as a sum of some **contiguous** sequence of elements of your list starting from $x\_1$ (resp. ending in $x\_n$).

Calling $OPT\[i,j\]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $(\[x\_1, \dots, x\_j\], 0)$, we then obtain (for $n \> 1$):

$$ OPT\[1,n\] = \sum\_{h=1}^n x\_h + min\_{h=1,\dots,n-1} \left\\{ OPT\[1,h\] + OPT\[h+1,n\] \right\\} $$

and, in general:

$$ OPT\[i,j\] = \begin{cases} \sum\_{h=i}^j x\_h + min\_{h=i,\dots,j-1} \left\\{ OPT\[i,h\] + OPT\[h+1,j\] \right\\} & \mbox{if } j-i\>0 \\ 0 & \mbox{if } j-i = 0 \end{cases}. $$

There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.

# Answer
> 1 votes
Your problem is known as optimal alphabetic binary tree (or various similar names). This is an ordered version of Huffman coding, in which the two numbers being added don't have to be adjacent. The problem can be solved in $O(n\log n)$ using either the Hu–Tucker algorithm or the Garsia–Wachs algorithm.

---
Tags: algorithms, lists, subset-sum
---


# Question
Title: Does this shuffle have non-zero probability for all permutations?
I was trying to do some code golf, when I created the following algorithm to shuffle a string:

```
for(;k-->0;y=s,s="")for(var c:y.split(""))s=Math.random()<.5?s+c:c+s;

```

To explain better what it does, I've recreated it in Python:

```
import random
str = "Randomize me!"
print('[',str,']',sep='')
temp=""
for _ in range(len(str)): # repeat as many times as the string is long
  for char in str:        # take the string's chars and randomly construct a temporary
    temp = temp + char if random.choice([True, False]) else char + temp
  temp, str = "", temp    # use the temporary as the basis for the next iteration
print('[',str,']',sep='')

```

Also, per request, here it is in pseudocode:

```
SHUFFLE(STR)
 0 TEMP ← ""
 1 LOOP STR.LENGTH TIMES:
 2     FOR EACH CHAR ∈ STR:
 3         IF COIN-FLIP
 4             TEMP = TEMP + CHAR
 5         ELSE
 6             TEMP = CHAR + TEMP
 7         END IF
 8     END FOR
 9     STR ← TEMP
10     TEMP ← ""
11 END LOOP
12 RETURN STR

```

The output looks randomized to me. However, if you only consider one iteration of the algorithm, the first character put into `temp` is always `str[0]`. The second character put into `temp` on this iteration is always `str[1]`, which *must* be next to `str[0]` according to the way characters are appended. Therefore, after one iteration, the probability that the shuffled string has the first character outside of the center is 0, and the probability that it is not adjacent to the second character is 0.
I tried to remedy this problem by repeating the shuffle once for each character in the string. Intuitively, it seems to work, but I can't seem to prove that all permutations of the input string can show up.

So, here's the question: do all permutations of the input string have non-zero probability as output from this shuffle?

# Answer
Yes. Your algorithm can return all permutations. You can prove it by fixing any arbitrary permutation $\pi$ of the input string `str` and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of `str` can match the last $i$ characters of $\pi$.

For $i=0$ this is trivial. For $i\>0$: Let $n$ be the lenght of `str`, $x$ be the character in position $1+n-i$ of $\pi$ (indexing positions from $1$), and $j$ be the index of the first occurrence of character $x$ in `str` with the additional constraint that $j \ge i$ (this index always exists by induction hypothesis). A string `temp` that will satisfy the induction thesis (as it will be assigned to `str`) can be found as follows:

* copy the first $j-1$ characters from `str` to `temp` (by appending them to `temp`). In particular this copies the first $i-1$ characters of `str` which, by induction hypothesis, match the last $i-1$ characters of $\pi$.
* prepend the $j$-th character of $x$ of `str` to `temp`.
* append the remaining $n-j$ characters of `str` to `temp`.
> 4 votes

---
Tags: algorithms, strings, probability-theory, randomized-algorithms
---


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

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

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

Does this mean the following?

1. Split my training set T into training set T1 & validation set V1
2. Find the mean/var of T1, mean\_T1, var\_T1
3. Normalize T1, V1, and my testing set with mean\_T1, var\_T1.
4. Train & test accordingly...

Thanks...

# Answer
Yes, that's what it means. Basically, mean\_T1 and var\_T1 become part of the model that you're learning. So, same as you'd apply machine learning to the training set to learn a model based on the training set, you'll compute the mean and variance based on the training set.
> 1 votes

# Answer
"Must" is not a compelling scientific argument; producing a link to a document that also uses "must" as argument does not make the argument stronger unless mathematical proof or, at least, an illustrative counterexample are provided.

Using *training dataset* statistics to normalize *validation/test data* allows for information leak from train to validation and to the test data which may lead to optimistic fit/validation errors.

Taking this practice further to the new (unobserved) data will imply unchecked membership of the new data to the training population (used to built the model).

I think this practice is incorrect as it forces the stationarity assumption according to which new data is a member of the training population, by this proving the stationary of the process (circular reasoning).

Stationarity violation: when underlying processes (instantiated by training data and described by the model) have shifted, the model becomes obsolete and in need of re-training as the new data no longer belongs to the training population.

Using the old model to predict on these new data results in high prediction errors.

A correct procedure would require the stationarity assumption be checked with each prediction by testing the membership of new data to the training population. A powerful test would require that no information from training to validation to test data is leaked through normalization or otherwise.

As a matter of fact, this happens with models not using normalized data.
> 1 votes

---
Tags: machine-learning, neural-networks, statistics
---


# Question
Title: Search Algorithm with two areas of solutions
I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute force method. So I just enhance the variable by a factor, enter the variable to the algorithm till I get a true. This really needs a lot of run time. Then I switched to the bisection method. Here I had the problem that sometimes the function is true for some values and then switches again to false. This means if the area is before the half of the interval, the bisection method can not find the area before because the bisection method doesn't get the true in therefore took the second half of the interval.

My question is now: does sb has an idea how I could fix that? Are there any search algorithms which are exactly for that problem?

# Answer
> 0 votes
With no other given assumptions, it is a linear solution in the most optimal scenario. One can have better solution (binary search) in problems where all the values after first true are true. But if there is only one element, it is a O(n) solution.

---
Tags: algorithm-analysis, search-algorithms, iteration, b-method
---


title: Modifying the genetic algorithm

text:
# Question
Title: Modifying the genetic algorithm
I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm.

I have 3 "areas" of optimization, say parameters `a`, `b` and `c`, so cost function for my problem is `C(F) = a + b + c -> min`.

I want to somewhat modify the genetic algorithm. In the classic workflow, the initial population is created randomly. For my problem, I want to create a "smart" initial population. Since I have 3 parameters to be optimized, I wanna create 1/3 of the initial population optimized for parameter `a`, 1/3 optimized for parameter `b`, and 1/3 optimized for parameter `c`. Then, in the while loop just "mix" these good individuals. Is this a good way to go? Is this still considered the genetic algorithm? Is this a good modification?

P.S. I'm doing research for my master's project so I need to provide some novelty in my solution. Would this modification be considered fine for that?

Thanks in advance.

# Answer
> 1 votes
Yes, this is absolutely still considered a genetic algorithm. In fact, it is quite common to experiment with various strategies of obtaining an initial population. As you say, it is reasonable to start with a completely random population unless you have a reason to try something else.

Whether this is a good way to go is anybody's guess, really. It depends heavily on your problem and problem instances. Give it a try and see how it compares to a random initial population. Further, whether this is a modification that is considered fine, trust your advisor more than random people on the internet.

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: Distributed algorithm can be executed in a single process
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency primitives (i.e channels and goroutines)

AFAIK "distributed" means things are happening on multiple machines. But this is running in a single process. (the fact that all threads are sharing memory is irrelevant since the algorithm's implementation doesn't depend or make use of it)

So can we call the system consisting of the threads + channels a distributed system? This seems to have all characteristics:
\- threads run independently and in parallel much like nodes (assuming enough processors)
\- communication via message-passing

If we choose to not call it a distributed system, then why is the algorithm labeled distributed if it can run on a non-distributed system?

# Answer
> 1 votes
From Wiki:

> Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing.

It is inherent type of algorithm to be run independently with no requirement that processors are in the same machine. Think of it as the type of workload being cut into independent pieces.

From Wiki:

> A distributed system is a network that consists of autonomous computers that are connected using a distribution middleware. They help in sharing different resources and capabilities to provide users with a single and integrated coherent network.

So the algorithm is distributed, but the system you have described is not. This is just algorithm with different purpose run in less distributed environment with potential to be sub-optimal in such setting.

Another example: you can run sorting network (say bitonic sort) in one thread, it doesn't make it serial algorithm, but overhead is costly in such case.

---
Tags: algorithms, terminology, distributed-systems, concurrency
---


# Question
Title: How is β-reduction a 2-morphism in Category theory?
According to Categorifying CCCs: Computation as a Process, computation or β-reduction process in untyped-lambda calculus is in fact a 2-morphism in category theory.

Can someone please describe me how is it so and elaborate on it?

P.S. I understand that category theory is a mathematical concept but since this specific question is about β-reduction and lambda calculus I have posted it in computer science section.

# Answer
> 2 votes
Here is a new paper that covers a similar topic. The idea is that by doing algebra in enriched categories (2-categories are like categories enriched in categories), you can talk about more fine grained semantic structure on the algebra. (I haven't read through the whole paper myself, but I know enough to see some of the ideas behind it.)

The way it relates to your question is thus: ordinary categories are, "set enriched," meaning the homs are sets. When giving a categorical semantics of a type theory (say), the (open) terms are interpreted as arrows, the idea being that the domain of an arrow is the context, and the codomain is the type of the open term.

$$ Γ ⊢ e : T \ \ \ \ \ \Longleftrightarrow\ \ \ \ \ e \in Hom(Γ, T)$$

The important thing is that both the terms in the language and the semantics of those terms will form (enriched) categories, and the interpretation of those terms into the semantics will be functors that must preserve the structure of the hom collections. For sets, the structure is just equality of elements. So, equal terms must be assigned equal semantic values.

However, this means set enrichment isn't very good at letting us have structured semantic requirements. If we have β equivalent terms:

$$ (λ x → (x, x))\ e\\ (e,e) $$

then with set enrichment, we have two choices:

1. They are not equal, so the semantic values assigned can be totally unrelated.
2. They are equal, so the semantic values must be the same.

However, option 2 basically means that our syntactic category has arrows that are β equivalence classes of terms (or whatever equivalence you wish to require of the semantics). We have pre-quotiented the syntax by all the reductions that hold.

Instead, think about poset enrichment (which is like a 2-category in which there is at most one 2-morphism between any two 1-morphisms). Now there is an additional partial order $\prec$ on elements of the sets, and the semantic assignment must respect that partial order. Now we have a third option, which is to say these two terms are not *equal*, but they are related:

$$(λ x → (x, x))\ e \prec (e, e)$$

And the semantics can no longer assign them completely unrelated values, they must assign them values that are 'connected' in the semantics.

With posets we are basically only able to represent whether or not a term is reducible to another. With enrichment in a category (like a 2-category), we are able (I think) to keep track of multiple potentially different ways in which reductions can occur, and how to compose them. Vertical composition is like:

$$ e\_1 \rightsquigarrow e\_2 ∧ e\_2 \rightsquigarrow e\_3 ⇒ e\_1 \rightsquigarrow e\_3$$

And horizontal composition is rather like:

$$f\_1 \rightsquigarrow f\_2 ∧ x\_1 \rightsquigarrow x\_2 ⇒ f\_1 x\_1 \rightsquigarrow f\_2 x\_2$$

Although you should take that with a grain of salt, because that gets into the part of the paper I haven't really read yet.

So, by using 2-categories or enriched categories, we can explicitly represent richer structure on our terms, and talk about semantics that preserves that structure.

---
Tags: lambda-calculus, type-theory, category-theory
---


title: Time complexity of matrix subtraction

text:
# Question
Title: Time complexity of matrix subtraction
If I have (I-Z) where I is a 3x3 identity matrix while Z is a 3x3 lower triangular matrix, how many subtractions that I should count from this process? Is it costs K subtractions or (K^2+K)/2 subtractions?

Thank you.

Huda

# Answer
> 1 votes
It’s a 3x3 matrix, so it can be done in constant time O(1). I can’t see where a “k” comes into this problem.

# Answer
> 0 votes
Since you are subtracting $Z$ from $I$, you must compute the lower part of the matrix. If it was reversed, you only had to compute the new diagonal. The total number of subtractions is therefore $(k^2 + k)/2$.

---
Tags: complexity-theory, matrix
---


# Question
Title: Difference between Image Analysis and Computer Vision
I have searched the web and I have only found the differences between Image Processing and Computer Vison (also in this website too). In addition, sometimes Image Analysis is confused with Image Processing, which is untrue. Reading the Wikipedia article, it makes me thing that Image Analysis is another name for Computer Vision. Therefore I am confused. What is the real difference of those two?

# Answer
Maybe the web does not have an answer, but the classical book of *Image Processing by Gonzalez and Woods* has. I will summarize a part from a chapter that I have read.

There is **no clear boundary** between the three areas of Image Processing, Image Analysis and Computer Vision. Some say that, what inputs and outputs images is Image Processing, but should the simplest task of computing the average of an image (that is a number) be excluded? **Computer Vision though, is a branch of AI**, that is much different from the other two fields, since it focuses on learning, making inferences and taking actions based on visual inputs. Image Analysis (a.k.a Image Understanding) **is between** Image Processing and Computer Vision, but with **no clear boundaries**. However, one could define three distinct processes based on a hierarchy level. The low-level processes consume and produce images (e.g noise reduction, contrast enhancement, image sharpening), the mid-level processes take images and output attributes (e.g edges, contours, object identities). Example tasks include image segmentation and object description and recognition. Lastly, high-level processes try to comprehend the recognized objects and at the far end, introduce cognitive functions for emulating human vision.

For more details, one can go and read the source, because luckily, that chapter is available online as a sample. The particular content lies in *page 18* beginning from the third paragraph "*There is no general agreement...*" until the end of the next page's first paragraph "*...for the methods used in this application area*". I would have quote the whole content in case the website shuts down in the future, but I don't know if this is legal.
> 4 votes

---
Tags: computer-vision
---


# Question
Title: Average codeword length in Huffman encoding at most log n
I am interested in the following question:

> Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords.

I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $n-2$, but I still have to take the letter frequency into account, and I am stuck.

(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)

# Answer
> 6 votes
Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).

Let us notice now that there is a code in which each codeword has length $\lceil \log n \rceil$, and in particular the average codeword length is $\lceil \log n \rceil$ (with respect to any distribution). Hence Huffman's algorithm produces a code in which the average codeword length (with respect to the input distribution) is at most $\lceil \log n \rceil$.

Here are two comments. First, we cannot replace $\lceil \log n \rceil$ with $\log n$. For example, if $n = 3$ and you consider the uniform input distribution, then the optimal average codeword length is $5/3 \> \log 3$.

Second, the average codeword length is only guaranteed to be small with respect to the input distribution. For example, if the input distribution is $1/2, 1/4, 1/8, \ldots, 1/2^{n-1}, 1/2^{n-1}$ then the optimal code has codeword lengths $1,2,3,\ldots,n-1,n-1$, and so the average codeword length with respect to the uniform distribution is roughly $n/2$. The average codeword length with respect to the input distribution, however, is constant (tends to 2).

---
Tags: algorithms, proof-techniques, information-theory, huffman-coding
---


# Question
Title: If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

* Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.
* If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

# Answer
A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if a solution $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution which whose representation grows at an exponential rate $2^n$.
> 3 votes

# Answer
There are special cases of convex problems that can be solved in polynomial time, e.g. a convex QP defined over a simplex. In general, however, convex programming is NP-hard. However, NP-hard by no means means unsolvable.

Although theorists would probably cringe at the term, there are NP-hard and what I coin as "NP-harder" problems. What I call an NP-harder problem is one that requires the combination of numerous NP-hard algorithms to solve, sometimes evoking each other exponentially many times. Although this is still NP-hard, it's much more intractable than any of its components. Deterministic global optimisation is a great example of this.

With that in mind, there are two main classes of convex problems: (i) continuous and (ii) mixed integer.

For mixed integer convex problems, we need to use methods such as branch-and-bound, so intuitively we can see why this is NP-hard and difficult in practice. In fact, solving a mixed integer convex problem is usually much harder than solving a nonconvex NLP to local optimality.

For convex NLPs, it comes down to solving a local optimisation problem, however satisfying the optimality conditions is also NP-hard. So why is this easier than mixed integer or non-convex?

The answer is that it's not "NP-harder". There are fewer NP-hard components in a convex NLP solver than in, say, a global solver. We need to satisfy the optimality conditions and that's it. We don't need to search for integer feasible points, we don't need to branch, we don't need to worry about missing the basin of attraction because of the step size, and so on, and this makes the problem much more tractable in practice.
> 1 votes

---
Tags: algorithms, complexity-theory, optimization, np-hard, convex-hull
---


title: find maximum sum of xors

text:
# Question
Title: find maximum sum of xors
we are given an Array

Array size \<= 10^4 .

0 \<= A\[i\] \<= 15

We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum those xors.

for example, one subset could have indices 0, 3, and 7, and another subset could have indices 1, 2, and 4 find the max sum.

4^n approach is very expensive.

there are only 16 different values of xor so for each value of xor=X we can search in array if is it possible to partition the array such that we get xor=X.

# Answer
For every $i \in \\{0,\ldots,n\\}$ (where $n$ is the length of the array) and for every $a,b,c \in \\{0,\ldots,15\\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can determine the possible XORs resulting from partitions of the array into four subsets, and so calculate the maximum sum. The resulting algorithm runs in linear time.
> 1 votes

---
Tags: algorithms, data-structures, subset-sum, bit-manipulation, xor
---


# Question
Title: Showing the language of TMs that halt on a decidable set of words is not in RE
I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a reduction that is similar to the one used in the proof for Rice's Theorem in Sipser's 3rd edition (page 243). I couldn't think of a proper proof by myself. I assume L $\notin RE\cup CO-RE$ so there's no point in trying to prove $\bar{L}$ is in RE to show L is not in RE. Can anyone help?

# Answer
Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $L$. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

* Run $M$ on the empty input.
* If $M$ halts, interpret the input as a Turing machine and run in on the empty input.

If $M$ doesn't halt on the empty input, then the set of words on which $M'$ halts is the empty set, which is decidable, and so $M' \in L$. If $M$ does halt on the empty input, then the set of inputs on which $M'$ halts is HALT, which is not decidable, and so $M' \notin L$.
> 1 votes

---
Tags: complexity-theory, turing-machines
---


title: How to Get Started in Computer Science

text:
# Question
Title: How to Get Started in Computer Science
I am wondering how to get started in studying theoretical computer science and how to apply it to my programming. I am fairly comfortable with basic programming, having been programming in mainly C++ but also Java for the past couple of years, so I don't necessarily need an introduction to programming.

What I am looking for to start is perhaps something fairly broad, so that it gives a wide overview of computer science, as I don't know exactly where I want to study within it yet. But it could also be nice to have directions of where to look to continue studying a specific aspect of it. However, this is just what I think could be helpful, and I am open to any recommendations.

# Answer
> 2 votes
Theoretical computer science means different things to different people. However, here are some areas which are commonly taught in undergraduate theoretical computer science classes:

* Combinatorics and elementary set theory. This serves as prerequisite to all that follows.
* Data structures and algorithms. One standard textbook is Introduction to algorithms, but it might be too advanced if you're just starting out.
* Computability and automata theory. One standard textbook is *Introduction to the theory of computation* by Michael Sipser.

In some places, another core subject is functional programming and labmda calculus.

An undergraduate degree in computer science typically deals with several other topics, such as operating systems, networking, and sometimes compilation.

---
Tags: software-engineering
---