# Question
Title: "Which complexity represents a majority of algorithms?"
Student asked me this question. During lectures on algorithm complexity I've shown similar picture (source):

After I've explained and gave examples for each category, a student asked: "Which of these represent a majority of algorithms?" I guess that the question is not right in a sense that we are creating new algorithms and that it depends on the field - majority of sorting algorithms are more complex than nlogn.

What would be your answer?

This question is only about the Big O as that was the end of the lecture.

Thanks!

# Answer
My answer would be that there is no running time that represents the majority of algorithms. Some common algorithms (for example, BFS and DFS) run in linear time; some run in loglinear time (for example, sorting); dynamic programming algorithms run in superlinear polynomial time (for example, the standard algorithm for edit distance runs in quadratic time); algorithms involving matrix multiplication run (practically) in cubic time, and theoretically faster; SAT solvers have worst case exponential running time; and some algorithms involved in verification have even faster growing worst case running time, or are not guaranteed to terminate at all.
> 2 votes

# Answer
The hard part of addressing this question, I would imagine, is the problem of counting algorithms.

Nonetheless, here's an informal way to look at it:

If you pick any integer $n$, there are infinitely more integers larger than $n$ than there are integers smaller than $n$. Similarly, the time hierarchy theorem states that you can always solve more problems if you have more time.

This says nothing about the *number* of problems problems in each class, but nonetheless, given an infinite hierarchy of complexity classes, I would be very surprised if, given a complexity class, there are "more" problems outside it than inside it for an appropriate definition of "more".

For example, there are probably more (in the sense of cardinality) decidable problems that are nonelementary than there are in the complexity class ELEMENTARY.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What is the State of The Art of Writer AIs (Deep Learning)?
> Does anyone know if Deep Learning Bots can already, for example, train on many books of an author and output a similar but new book?

I've been wanting to get into ML for quite a while but was lacking a project to use as an incentive to keep learning, and this specific AI has caught my interest. It seems feasible from the little I know of ML so far (I'm a beginner who has taken the initial module of `Deeplearining.ai` course from Coursera), but so far from what I can scoop out of the internet it doesn't seem like AIs are quite there yet. They seem to be somewhat convincing, but sometimes a weird outlier appears in the text; strangely, music composition seems more convincing. Does anyone disagree?

Another relevant question: is this too difficult for a beginner? I've graduated from engineering 1 year ago, so I have some ease with programming, but I don't know how difficult Recurrent Neural Networks (RNN) and Natural Language Programming (NLP) can be.

> Also, on a sidenote, does a more experienced programmer have a suggestion of path I should take to learn the necessary skills to program such a bot, i.e., online courses and books?

# Answer
Researchers are trying it out, but RNNs learn character-by-character (sequences of characters), so it is difficult to get something that resembles a story plot, as a whole. This link by a Stanford researcher explains the current (2015) state of the art. Here is the code and here are some data sets for you to start experimenting with.

Another experiment involving the writing of a travel blog also concluded that you cannot really create a long passage that makes sense at the moment. The recommendation was to look at the word level, rather than character, and focus on something more manageable, such as sentence autocompletion.

When it comes to words, the more unique ones there are in the source data set (for example using the Game of Thrones books), the tougher it becomes to train a good model. Suggestions are to limit input to more basic words (think children's vocabulary) and to have at least a total training sample at least 100 times larger than the desired output.

A trained neural network could perhaps output smaller texts (\<10000 words) that make some sense, if they are of a rather structured nature. A whole book needs both a coherent plot from start to finish, as well as twists in-between. As a result, it is still way too difficult.

This guy tried it out and discovered that the AI would get sometimes stuck in loops. Furthermore, the draft produced did not always make sense in terms of the storyline and required heavy human editing.

Here is another example of an LSTM RNN outputting a Harry Potter chapter, where the sentences are grammatically correct, but sometimes make no sense.

If you want to learn more about RNNs, the Deep Learning book by Goodfellow, Bengio, and Courville comes highly recommended and has a relevant chapter.

For something more specific to writing, The Bestseller Code book uses text mining techniques and should be an interesting read.
> 5 votes

# Answer
No. As Yuval writes, this is way beyond what we know how to achieve with the state of the methods known today. Definitely too difficult for a beginner; too difficult for anyone right now.

I would suggest looking around; if you want to learn about deep learning and RNNs, there are lots of tutorials on deep learning and RNNs. I suggest starting with something more standard as your first project, until you get a better handle on what kinds of tasks are within reach of current methods.
> 3 votes

---
Tags: machine-learning
---


# Question
Title: Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages
How can I prove this identity of languages?

My aproach is the following:

Let A, B and C to be languages, and let x to be an arbitrary string.

(A ∪ B) ⇒ x ∈ A ∨ x ∈ B

How do you proceed?

# Answer
Just keep going. You've written what it means for $x$ to be in $A\cup B$. Now write out what it means for a string $y$ to be in $(A\cup B)\circ C$. Do the same kind of thing on the right-hand side and relate the two statements you get.
> 1 votes

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


title: Time complexity of set intersection

text:
# Question
Title: Time complexity of set intersection
This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below).

Problem 1: The input is a positive integer $m$, and two unordered subsets $A$ and $B$ of $\\{1,\dots,n\\}$. The size of the input is $n+ |A| +|B|$.

Output: The set $A \cap B$, the intersection of $A$ and $B$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Problem 2: The input is a positive integer $m$, and $j$ unordered subsets $A\_1, \dots, A\_j$ of $\\{1,\dots,n\\}$. The size of the input is $n+ |A\_1| + \cdots + |A\_n|$.

Output: $A\_1 \cap A\_2 \cap \cdots \cap A\_n$, the intersection of $A\_1, \dots, A\_j$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Are there references to the time complexity of these problems? I’m interested in the particular algorithms themselves, but if anyone knows that complexities above are linear-time or $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients, I’d be grateful to hear from you. ( I’m less interested in algorithms that involve hash functions, but as long as such an algorithm works on all possible inputs, a hash function algorithm is okay.) I’m not a computer scientist student but an older person learning things as they come along in work-in-progress.

# Answer
> 3 votes
Your post contains two problems. I will only address the first.

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.

# Answer
> 0 votes
You can’t give the time complexity because a set is not a primitive data structure, so you need to know how it is represented.

Why would n be part of the input size? Let A = { 1,000,000,000 } and B = { 1, 1,000,000,000 }, for example.

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


title: Is my interpretation correct?

text:
# Question
Title: Is my interpretation correct?
I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for recommendation systems.

This is the algorithm:

These are the necessary definitions for mathematical notations used in the algorithm to understand the algorithm.

> The distribution is defined as, for a nonzero vector $x \in R^n$, we denote by $\mathrm{D}\_x$ the distribution over \[1, ..., n\] whose probability density function is $$\mathrm{D}\_x(i) =\frac{x^{2}\_{i}}{\lVert{x}\rVert ^2} $$.
>
> If a matrix $A \in R^{m \times n}$, and let $A\_i$ refer to the $i$th row of $A$. Let $\tilde{A} \in R^m$ be a vector whose $i$th entry is $\lVert A\_i \rVert$.
>
> $\[p\] denotes \[1, 2, ... p\]$
>
> $s \sim \_u \[p\]$ denotes pulling an $s$ uniformly at random.

I am having a problem understanding the `Let the resulting p x p submatrix ...` step of the algorithm. According to the algorithm the rows of the submatrix are sampled from a distribution $\mathrm{D}\_{\tilde{A}}$ and the columns of the submatrix are sampled from a distribution $\mathcal{F}$.

1. I can't understand how can we form a submatrix with both rows and colums given ? I think we just need either rows or columns. Can someone clarify this to me, please ?
2. And I also don't understand the definition of $\mathcal{F}$. According to definition of $\mathcal{D}\_x$, $x$ has to be a vector then how can we choose a column from $D\_ \tilde{A\_{i\_s}}$.

# Answer
> 2 votes
Given a matrix $A$, you can form another matrix by taking only some of the rows and columns of $A$, possibly repeated. For example, suppose that $A$ is the following matrix: $$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$ If we take only rows 1,2 and columns 1,3, then we get the matrix $$ \begin{bmatrix} 1 & 3 \\ 4 & 6 \end{bmatrix} $$

For your second question, $\mathcal{D}\_x$ is a distribution on column *indices*. You don't choose a column directly – you only choose an index. This corresponds to 1,3 in the example above.

---
Tags: algorithms, complexity-theory, quantum-computing
---


# Question
Title: Is huffman coding tree a heap or a trie?
I study Huffman Coding tree from "Data Structures and Algorithm Analysis" of Shaffer and it says that Huffman Coding tree is an opportunity to experience a search trie. However, the code implements it with a heap class.

As a result, I wonder if Huffman Coding tree is actually a heap or a trie? If it is a heap, is it a mimHeap or a maxHeap. I'm somehow confused because there are some online resources calling it a minHeap, as it should be a maxHeap.

Anyway, thank you very much in advance.

# Answer
A Huffman tree is a trie: its edges are labeled by $0,1$, and its paths spell out binary words.

Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two items with minimal probability, and merge them.
> 5 votes

---
Tags: huffman-coding
---


# Question
Title: Does this constraint satisfaction problem have a name
I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution.

The problem is: I am making a card-playing AI, and at some point I need to guess a plausible solution to the other players hands. Given the history of the game, I can definitely say that some players *don't* have certain cards .

Put formally: I have a set of elements $S$ (the remaining cards in the game), and the goal is to partition $S$ into a fixed number of disjoint subsets $S\_i$, for $ i \in \\{1...n\\}$. For each subset, we have a set of elements $A\_i$ that they may not have, and a number of elements $N\_i$ that this subset must contain. Also, $|S| = \Sigma\_i N\_i$. Find a partition.

There are a number of extra conditions that could make this problem much easier:

* The initial conditions guarantee that there will always be a solution.
* All remaining cards are in other peoples hands. There is no deck, and so all other cards have either already been played, or are in my AI's hand.
* The number of cards to be distributed is $\<24$.
* There is always exactly 3 opposing players, i.e. $n = 3$.
* For any $i, j$, $abs(|N\_i| - |N\_j|) \<= 1$.

I am convinced that this problem has already been studied and has a name. Does anybody know if it exists? If not, is the problem is simple enough that there is a solution that does not require exponential search?

# Answer
This is a special case of perfect matching in bipartite graphs and could be solved using standard algorithms for that problem (e.g., the Hungarian algorithm). It is not the perfect matching problem (it looks easier; and it is much more specific), but it is a special case of it.
> 1 votes

# Answer
I couldn't quite understand how this problem was a special case of perfect matching, however, I found my own solution, which is too detailed to describe here.

Using pure set logic, I found a solution which runs in a time linear in the sizes of the sets $N\_i$, but combinatorial in the number of players. Given that the number of players is always 3, this algorithm is quite fast for my use case.

Thanks anyway
> 0 votes

---
Tags: algorithms, constraint-satisfaction
---


# Question
Title: Problem with understanding proof of the Space Hierarchy Theorem
The Space Hierarchy Theorem states that

> If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$

An example of a SHT proof can be found here or here but they are generally based on the same idea differing only in technical details. We would like to find a language $L$ such that $$L \in SPACE(f(n))$$ and $$\forall{g \in o(f(n))}: L \notin SPACE(g(n)).$$ So the proof claims that a language that fulfills these constraints is the following (for the sake of this post we do not care about $M$s whose description is too short for the asymptotic behavior of their space complexity to kick in) $$ L = \\{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\\} $$ and it describes a TM that accepts this language in $f(n)$ space. Then it tries to prove the second constraint using diagonalization argument in the following way:

> Suppose there is $M'$ such that $L(M') = L$ and $M'$ is of $g(n) \in o(f(n))$ space complexity. Then
>
> * If $M'$ accepts $\langle M' \rangle$ then (from assumption) $\langle M'\rangle \in L$ then (from definition of $L$) $M'$ rejects $\langle M' \rangle$
> * If $M'$ rejects $\langle M' \rangle$ then (from assumption) it does so in $o(f(n))$ space then (from definition of $L$) $\langle M'\rangle \in L$ then (from assumption) $M'$ accepts $\langle M' \rangle$
>
> Contradiction. Therefore such $M'$ does not exist.

So what bothers me is that in the argument above we could just as well take a TM $M''$ that runs in $f(n)$ space and the argument would still hold, therefore breaking the first constraint.

# Answer
> 1 votes
Apparently, there is a misunderstanding of the original proof from Sipser's book *Introduction to the Theory of Computation* that's been erroneously duplicated in a couple of sources including Wikipedia and Berkeley's CS172 lecture notes.

Namely, Sipser defines the language in terms of a TM $M$ that

* takes an encoded machine description $\langle M' \rangle$
* simulates $M'$ on input $\langle M' \rangle$ on a tape bounded by $f(|\langle M' \rangle|)$
* inverts the answer, if the machine stops.

The resulting $L(M)$ is different from

$$ L = \\{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\\} $$

because $M$ rejects $\langle M \rangle$ due to recurrent simulation that requires infinite space and therefore $\langle M \rangle \notin L(M)$ and $\langle M \rangle \in L$ from the definition of $L$.

As a result, in the diagonalization argument we should replace references to the definition of $L$ with references to the acceptance of $M$, which breaks the argument for $M$ itself.

---
Tags: complexity-theory, space-complexity
---


title: Candy Problem for k size window

text:
# Question
Title: Candy Problem for k size window
I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.

Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour.

So, the problem is basically for every i in range\[1, n\] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.

Is there any linear time solution for this?

# Answer
1. Compute the sorted scores (and associated children) in the first window with a persistent sorted tree. This step takes $O(k \log k)$ time.
2. Create a DAG on children and add a directed edge from each child to each other child who is between $p$ and $2p$ places lower than it. This step takes $O(pk)$ time.
3. Shift the window forward one child at a time. Incrementally update the tree to obtain a new one for this window in $O(\log k)$ time per tree.
4. In each tree in step 3, place directed edges between pairs of children of distance $p$ where the child that entered the window in this tree is in between the children in the pair. This can be done in $O(p)$ time per tree (avoiding a $\log k$ factor) if one starts at the node obtained by insertion in step 3.
5. Assign candies to children topologically: each leaf child gets 1 candy; each internal child gets max(child's candies) + 1 candies. This runs in $O(n)$ time.
6. Sum the candies.

Note: the DAG with all of the edges from steps 2 and 4 sorts children by relative number of candies.

The resulting algorithm runs in $O(n(p+\log k))$ time.
> 1 votes

---
Tags: algorithms, data-structures, greedy-algorithms, intervals
---


# Question
Title: why do we run out of heap space even if we have virtual memory?
Whenever we try to get space in heap(using malloc or new) we can get out of heap space error if it exceeds the limit. But, we have virtual memory so why can't OS allocate that much space and then do swapping when I need some part of it or not?

# Answer
> 3 votes
Firstly, even the virtual memory does not imply an infinite amount of memory. I have run out virtual memory quite a few times.

Secondly and more commonly, there is a limit on the amount of memory each process can own by itself and a limit on the amount of memory each process can share with other processes, which are usually defined before the start of the process, especially on a multi-user environment. Those limits will not be increased automatically even if the process is running out of the limits, because that is basic meaning of the limits! That is why the OS cannot (or, you may say, will not) allocate the requested space even if there are plenty of freely available virtual memory left.

Thirdly, it may also happen because of memory fragmentation.

Fourthly, Java virtual machines (as I last heard of them) have its memory usage limit specified when it starts. Whether it uses of virtual memory or not, its usage of memory will be bounded by that limit.

Lastly, which may or may not the least, there are other situations.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Solve Hamilton Circuit with Hamilton Path
I want to show the reduction $HC \leq HP$.
Let $G=(V,E)$ be my undirected graph.

My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\\{e\\})$ has a Hamiltonian Path. If this is true for all edges, we have a Hamiltonian circuit in $G$.

It is pretty trivial to proof the first direction (when we have a Hamiltonian circuit in $G$, we will always have a Hamiltonian path in $(V,E\backslash\\{e\\})$ - independent from the edge we choose).

I really have trouble finding a formal proof for the other direction (either

1. $\forall e\in E$ Hamiltonian path exists in $(V,E\backslash\\{e\\})$ $\Rightarrow$ Hamiltonian circle exists in $G$ or
2. There is no Hamiltonian circle in $E$ $\Rightarrow$ $\exists e \in E:$ $(V,E\backslash\\{e\\})$ has no Hamiltonian path

# Answer
> 0 votes
Here is a counter example:

take the graph $G=(V,E)$ which is a path

$v\_1-v\_2-v\_3-v\_4-v\_5$

and add two edges to it $e\_1=\left\\{v\_1,v\_4\right\\}$, $e\_2=\left\\{v\_2,v\_5\right\\}$.

Verify that $G \notin HC$, but $\forall e \in E$, $\left(V,E\setminus \left\\{e\right\\}\right) \in HP$

# Answer
> 1 votes
Does a graph have a hamiltonian cycle if for anyone of its edges, it has a hamiltonian path after the removal of that edge?

Note that any hypohamiltonian graph must be such a graph. Is it even true that every hypohamiltonian graph has a hamiltonian cycle?

**Not necessarily.**

A counterexample is the Peterson graph, which is hypohamiltonian but not hamiltonian.

---
Tags: np-complete, reductions, hamiltonian-path, hamiltonian-circuit
---


# Question
Title: Is there a name and efficient algorithm for this Tree Traversal method?
Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.

I want to traverse this type of tree giving **equal opportunity/priority/time(?)** for each group with respect to its parent.

For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.

This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?

Consider the following tree structure as an example:

So the traversal I am thinking about would be as following for this example.

1. Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
2. We follow as in depth-first to arrive at task A and select it (complete it)
3. Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
4. Level 1 second sub-tree has only one task, D, so we select it
5. Similarly we go in to the third sub-tree and find the task F and select it
6. Now we return to level 1 and try to find our second task from the first sub-tree
7. IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
8. Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
9. Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)
    10. Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
    11. Only the right is left, so we select first H and finally the J, completing our traversal.

Traversal of leaves: (A-\>D-\>F)-\>(E-\>G)-\>(B-\>I)-\>(C-\>K)-\>(H)-\>(J)

\[Adding this clarifying paragraph from the comments:\]

*Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.*

**So my questions are:**

1. *Is there a name for this kind of tree traversal. If not, what would you call it?*
2. *How would you approach traversing this tree in an efficient way and what would be the complexity?*

Big thanks!

**EDIT:** Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.

**UPDATE:** I have used the final algorithm from **Apass.Jack** and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.

JS Code can be found as a:

Here are some execution results for different depths (D) and leaf counts (L):

```
          D3L10   | D3L1000 | D6L10 | D6L1000
          ===================================
Push      |  35   |   3350  |  50   |  4698 |
Unshift   |  14   |   1150  |  17   |  1549 |
Splice    |  35   |   3350  |  50   |  4698 |
Access    |  35   |   3350  |  50   |  4698 |
Traverse()|  16   |   1351  |  20   |  1808 |
Zip()     |   5   |    151  |   8   |   550 |
          -----------------------------------

```

**NOTE:** My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.

# Answer
If we just mark a leaf as visited in this round instead of removing it so as to allow it to be listed in the next round, we will get an algorithm to traverse tree leaves with repetitions, which is called **"recursive round robin scheduler"** in the case of binary trees in a paper in *Computer Networks* in 1999, which I would also call "recursive round robin tree leaf sampling with replacement".

So I would call the output of the algorithm in OP's question **"recursive round robin tree leaf sampling without replacement"** or "**RRR tree leaf traversal**" or just "**RRR traversal**" in short. Indeed, I cannot think of any other algorithm that traverse tree leaves could rightfully claim being both "round robin" at subtrees of the same parent and "recursive".

(If the order in which each subtree of the same parent is selected is randomized instead of always left to right, we will have an algorithm that we may call recursive randomized round robin leaf traversal algorithm, or, an even more lovely abbreviation, ***RRRR traversal***.)

Here is the pseudocode of my recursive algorithm that has the same output as OP's algorithm and its auxiliary zip procedure.

```
procedure rrrTraversal(rootedTree):
  if rootedTree is just a root without children
    return a list with rootedTree as its only element

  ll := an empty list of lists

  foreach subtree s of rootedTree from left to right:
    ss := rrrTraversal(s)
    push ss to the back of ll

  return zip(ll)

procedure zip(listOflists):
  zipped := an empty list

  while listOflists is not empty:
    foreach list li in listOflists from front to end:
      if li is not empty:
        fi := first item in li
        remove fi from li
        push fi to the back of the zipped
      else:
        remove li from listOflists

  return zipped

```

OP asks "This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?" The algorithm listed above gives a positive answer to that. It also fully justifies the usage of "recursive" in our description of the algorithm.

This algorithm may be refined by merging a parent with its only child whenever that situation, a parent with only one child, is encountered.

Here is a sample implementation in JavaScript.

The average complexity of the algorithm is probably $O(n\log n)$, because of the similarity of the algorithm to merge sort. However, it is not clear what will be the worst cases and what will be complexity of the worst cases.

It looks like it is nontrivial to find a significant faster algorithm than the recursive algorithm above. In particular, is there a linear algorithm in term of the number of the leaves? That should be a new question, though.
> 2 votes

# Answer
Here is a simple algorithm using a stable priority queue, where elements of equal priority will exit the queue in the order they are inserted into the queue.

1. Let the priority of each node be its level, a.k.a. its depth from the root. Lower level means higher priority.
2. Initialize $Q$ to be a stable priority queue of nodes containing the root.
3. while $Q$ is not empty:
    1. Take a node $q$ from $Q$.
    2. while $q$ is not a leaf:
        1. Add $q$'s next right sibling, if any, to $Q$.
        2. Replace $q$ by its leftmost child.
    3. output $q$.

This traversal goes level by level, outputting the leftmost leaf of each subtree and keeping track of what to do next in each subtree in the stable priority queue. Note that the traversal uses each edge only once.

Here is a sample run of the algorithm.

```
1
├──2
│  ├──3
│  │  ├──A
│  │  ├──B
│  │  └──6
│  │     └──C
│  └──8
│     └──E
├──D
└──11
   ├──F
   └──13
      ├──14
      │  ├──G
      │  └──H
      ├──17
      │  └──18
      │     ├──I
      │     └──J
      └──K

Queue is not empty: [1]
1 has no more siblings.

Descending to the first child of 1: node 2
Added 2's sibling D to the queue.
The queue is now: [D]

Descending to the first child of 2: node 3
Added 3's sibling 8 to the queue.
The queue is now: [D, 8]

Descending to the first child of 3: node A
Added A's sibling B to the queue.
The queue is now: [D, 8, B]
Output leaf: A

Queue is not empty: [D, 8, B]
Added D's sibling 11 to the queue.
The queue is now: [11, 8, B]
Output leaf: D

Queue is not empty: [11, 8, B]
11 has no more siblings.

Descending to the first child of 11: node F
Added F's sibling 13 to the queue.
The queue is now: [8, 13, B]
Output leaf: F

Queue is not empty: [8, 13, B]
8 has no more siblings.

Descending to the first child of 8: node E
E has no more siblings.
Output leaf: E

Queue is not empty: [13, B]
13 has no more siblings.

Descending to the first child of 13: node 14
Added 14's sibling 17 to the queue.
The queue is now: [B, 17]

Descending to the first child of 14: node G
Added G's sibling H to the queue.
The queue is now: [B, 17, H]
Output leaf: G

Queue is not empty: [B, 17, H]
Added B's sibling 6 to the queue.
The queue is now: [17, 6, H]
Output leaf: B

Queue is not empty: [17, 6, H]
Added 17's sibling K to the queue.
The queue is now: [6, K, H]

Descending to the first child of 17: node 18
18 has no more siblings.

Descending to the first child of 18: node I
Added I's sibling J to the queue.
The queue is now: [6, K, H, J]
Output leaf: I

Queue is not empty: [6, K, H, J]
6 has no more siblings.

Descending to the first child of 6: node C
C has no more siblings.
Output leaf: C

Queue is not empty: [K, H, J]
K has no more siblings.
Output leaf: K

Queue is not empty: [H, J]
H has no more siblings.
Output leaf: H

Queue is not empty: [J]
J has no more siblings.
Output leaf: J

```

You can play with a JavaScript implementation by Apass.Jack of this algorithm

The only slowdown for this algorithm is the stable priority queue. Using generic stable priority queue will give you $\mathcal{O}(n \log n)$ total runtime, where $n$ is the size of the tree.

However, it is possible to cut the running time down to $\mathcal{O}(n)$. Note that once we take a node with priority $p$ from the top of the queue, we will then possibly add a node with priority $p$, then descend to the child, then possibly add a node with priority $p+1$ and so on. This gives an idea to implement the priority queue as a linked list:

1. Each element of the list is a queue of nodes with the same priority.
2. Top priority is at the head of the list. If we pop last node from the top queue, the head of the list is removed.
3. When we descend to a child, the (candidate) priority is incremented, so we should move through the list, if necessary.
4. When we push new node, we either insert new queue into the list, or push the element to existing one.

Here's the states of such a priority queue from the run above (asterisk means current queue for insertion):

```
Initial:
└─[1] *

After popping node 1 and descending to node 2:
└─[D] *

After descending to node 3:
├─[D]
└─[8] *

After descending to node A:
├─[D]
├─[8]
└─[B] *

Taking D from the top:
├─[8] *
└─[B]

And pushing 11 before [8] because of greater priority.
├─[11] *
├─[8]
└─[B]

Taking 11 from the top and adding 13, which has the same priority as 8:
├─[8, 13] *
└─[B]

Taking 8 from the top:
├─[13] *
└─[B]

Taking 13 from the top:
└─[B] *

Pushing 17 with the same as B priority:
└─[B, 17] *

Added H to after [B, 17] because we descended:
├─[B, 17]
└─[H] *

Took B from the top:
├─[17] *
└─[H]

Added 6:
├─[17, 6] *
└─[H]

Took 17, added K:
├─[6, K] *
└─[H]

Descended to the child:
├─[6, K]
└─[H] *

Added J to a new queue, because we descended:
├─[6, K]
├─[H]
└─[J] *

Exhausting the rest of the queue:
├─[K] *
├─[H]
└─[J]

├─[H] *
└─[J]

└─[J] *

```
> 2 votes

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


# Question
Title: Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?
Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing machines with an extra black box device that can be queried and give an output that normally would be uncomputable. For example, a halting oracle would tell the machine a bit encoding whether an input program would ever terminate. Such "hypercomputation" machines can calculate various forms of uncomputable outputs.

My questions are:

Is hypercomputation compatible with our laws of physics? What about other incomputable things like Russell's set (things which its result is not computable because it does not exist)? Or what about other uncomputable/illogical/impossible/non-existent/inconsistent things? Are there hypercomputational systems that could encode/compute them?

Thank you for your help

# Answer
It is a little hard to say for sure since since one has not found a final Theory Of Everything in physics. Mostly it seems that **hypercomputation is physically impossible**.

On the other hand, an amusing development is the work of Nemeti et al. on using time travel (closed timelike curves) to do hypercomputation.

The so-called Malament-Hogarth spacetimes are known for exactly this --- that one can compute forever in them and thus solve the halting problem.

Hogarth worked on this in the 90s and Welch showed that even a larger class of problems than those solvable using the halting problem (all hyperarithmetic problems) can be solved in MH-spacetimes. This does not include all oracles though, as there are uncountably many oracles and only countably many hyperarithmetic ones.

(As for things that are logically impossible, like Russell's set, they are also physically impossible since "physics obeys logic".)
> 4 votes

# Answer
Not only is hypercomputation believed to be physically impossible, but even more ambitiously, some people working at the intersection of physics and computer science think that P!=NP might be a physical principle.
> 2 votes

---
Tags: computability, quantum-computing, hypercomputation
---


title: Why is $n + 2n^2 + 10n^4 = O(n^5)$?

text:
# Question
Title: Why is $n + 2n^2 + 10n^4 = O(n^5)$?
I'm going through an algorithms text book. One of the questions asks:

> True or false?
>
> $n + 2n^2 + 10n^4$ is $O(n^5)$.

This is marked as true.

Shouldn't it be $O(n^4)$? What am I missing here?

# Answer
This is an unfortunate inconsistency (or at least a frequent confusion) in terminology. Formally speaking, people usually define big-oh to be an *upper bound*, so that means running in time $O(n^5)$ just means the running time is bounded by $n^5$ times some constant if $n$ is sufficiently large.

In other words, $n^4$ is $O(n^5)$ (and it's also $O(n^4)$, $O(n^9)$, and $O(n^{1000})$, as well as many other things). In your example, $n + 2n^2 + 10n^4$ is both $O(n^4)$ and $O(n^5)$.

The usual formal notation for an *exact* asymptotic analysis (i.e. something that is both an upper and lower bound) is big-theta, or $\Theta$. So you would say that $n + 2n^2 + 10n^4$ is $\Theta(n^4)$, but it's *not* $\Theta(n^5)$.

The reason I call this terminology "unfortunate" is that it confuses many people, including you (as evidenced by you asking this question). The problem is that in informal speech, and often even in papers, people say $O$ when they really mean $\Theta$: when someone refers to a $O(n)$ algorithm, or an $O(n^2)$ algorithm, they often really mean $\Theta(n)$ or $\Theta(n^2)$. While using $O$ is usually not technically incorrect, it is misleading when $\Theta$ would also be correct and more precise. This is something you have to get used to: recognizing whether the writer really means $O$, or whether they could have said $\Theta$.
> 5 votes

---
Tags: asymptotics
---


# Question
Title: Predicate Logic - Natural Deduction; Assumptions about exists-elimination
I am stuck on how to progress with this proof; i cannot see my next move.

The task is to show $S \to \exists x Q(x) \vdash \exists x (S \to Q(x))$ using natural deduction for predicate logic.

My first attempt was the following;

1: $S \to \exists x Q(x) \space \space \space \space \space \space premise$
2: $x\_{0} \space \space S \to Q(x\_{0}) \space \space assumption$ (start of scoped box, i do not know how to write them here)
3: $\exists x(S \to Q(x)) \space \space \exists x \space introduction \space 2$ (end of scoped box)
4: $\exists x(S \to Q(x)) \space \space \exists x \space elimination \space 1,2-3$

However, i am not so sure that this is correct. The rule for $\exists$ elimination is
$\frac{\exists x \phi \space \space(And \space we \space manage \space to \space infer \space \gamma \space from \space replacing \space x \space in \phi \space with \space a \space fresh \space variable)}{\gamma}$
I do not know how to render the rule here (bonus question), but here's a link to where it is better described (page 16).

In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Can anyone explain if my thinking is correct, and point out my next move, or if i am wrong please explain why i am wrong? (Incidentally the link above describes exactly those rules my course litterature allow me to use, so if i could get help in terms of those rules i would be doubly grateful).

# Answer
> In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Exactly right. Your second move was illegal for the reason you said.

The problem is a bit tricky because of the annoying $S \to$ in front of the $\exists x Q(x)$, which means we can't eliminate the existential just yet. In order to get to $\exists x Q(x)$, we need to first have a proof of $S$, or know that $S$ is true. But we don't!

So how do we remove $S$ in front if we don't know it's true? Try first proving, as a lemma, that $S \lor \lnot S$: the law of the excluded middle. Next, your proof will have two cases: one if $S$ is true, and one if $S$ is not true. If $S$ is true, you should be able to eliminate the existential to get your $x$. If $S$ is not true, you should be able to prove $\exists x (S \to Q(x))$ by taking any $x$ at all.

---

**By the way, in case you're interested:** one reason this inference is difficult to solve is that not all logicians agree with it! There are logicians who proposed something called "Free Logic", with the main idea being that it is possible for no objects to exist at all. If no objects exist at all, then $S \to \exists x Q(x)$ might be true (it will be true if $S$ is false), but $\exists x (S \to Q(x))$ is definitely false no matter what, because there does not exist any $x$ period.
> 3 votes

# Answer
I don't believe the Existential elimination in your step two is correct.

On page 16 of your text, the $\phi$ is scoped within the Existential Quantifier expression, and you've tried to eliminate it in the scope of the implication $S \rightarrow \exists x Q(x) $.

I believe you can use a subproof to show $\exists x Q(x) \dashv \vdash Q(x\_0)$. I.e. That the two well formed formulas are semantically equivalent. And the proof of each direction is $\exists$ introduction one way, and $\exists$ elimination for the other.

Then you could use that information to conclude $S \rightarrow Q(x\_0)$. Since the consequent of the premise's implication is semantically equivalent to it.

From there, you can use $\exists$ introduction, with $\phi=S\rightarrow Q(x\_0)$, to conclude $\exists x(S \rightarrow Q(x\_0))$, as you've already done.

Hope that helps!
> 1 votes

---
Tags: logic, natural-deduction
---


# Question
Title: Time complexity of transforming one string to another
Here is the problem:

Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production sequence, otherwise, output $-1$.

Example: $D$ = \[bat, cot, dog, dag, dot, cat\], $s$ = cat, $t$ = dog, the shortest production sequence would be \[cat, cot, dot, dog\], giving us an output of four.

Here is the algorithm (Breadth First Search):

```
private static class StringWithDistance {
    public String candidateString;
    public Integer distance;

    public StringWithDistance(String candidateString, Integer distance) {
    this.candateString = candidateString;
    this.distance = distance;
    }
}

public static int transformString(Set<String> D, String s, String t) {
    Set<String> visited = new HashSet<String>(D);
    Queue<StringWithDistance> q = new ArrayDequeu<>();
    visited.remove(s) // mark as visited by erasing it
    q.add(new StringWithDistance(s, 0);

    stringWithDistance f;
    while ((f = q.poll()) != null) {
        if (f.candidateString.equals(t)) {
            return f.distance;
        }

        for (int i = 0; i < str.length(); ++i) {
            String strStart = i == 0 ? "" : str.substring(0, i);
            String strEnd = i + 1 < str.length() ? str.substring(i + 1) : "";
            for (int c = 0; c < 26; ++c) {
               String modStr = strStart + (char)('a' + c) + strEnd;
               if (visited.contains(modStr)) {
                   visited.remove(modStr);
                   q.add(new StringWithDistance(f, f.distance + 1);
               }
            }
        }
    }

```

I'm having a hard time understanding why this algorithm is $O(n^2)$. I know that the time complexity of processing the vertices/words is $O(n)$, but based on the text I'm reading, processing the edges in the worst case would be $O(n^2)$, so we would have $O(n + n^2)$, giving us $O(n^2)$.

I just can't see how that is taking place. The second loop is a constant (right?), it doesn't change with the size of $n$, so I don't think that is a part of the calculation for the run time.

Any help would be greatly appreciated.

# Answer
As told by OP, the problem and its the solution come from *Elements of Programming Interviews in Java* by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

Here is the excerpt of the book that analyzes the time-complexity of the solution.

> The number of vertices is the number d of words in the dictionary. The number of edges is, in the worst-case, $O(d^2)$. The time complexity is that of BFS, namely $O(d + d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

**The above analysis in the book is correct**. Please note "word" and "string" are used interchangeably here.

Here is OP's analysis, with the only modification that I use $d$ to denote the number of words so as to be consistent with the book.

> The second loop is a constant (right?), it doesn't change with the size of $d$, so I don't think that is a part of the calculation for the run time.

**OP's analysis is not wrong, either**, if we assume that the length of the strings in the dictionary is bounded by a constant. This assumption is not unreasonable since it conforms to our ordinary experience about words in a normal dictionary. In fact, OP's analysis has been included in the book as well! It is the very last statement of the excerpt above.

**Is there a logical inconsistency between the bounds $O(d^2)$ and $O(nd)$? No**, since they apply to different situations with different assumptions. For example, in the worst case where every string differ in exactly one character with every other string, if we let $d$ go to infinity, then the maximal string length $n$ will goes to infinity as well. That is, "The second loop" does "change with the size of $d$"! Those strings are very unlikely to be words in our ordinary dictionary because of their huge lengths, of course.

In fact, in all cases, $d \leq 26n$. So $O(d^2)$ implies $O(nd)$.
> 2 votes

---
Tags: algorithms, graphs, time-complexity, runtime-analysis, search-algorithms
---


# Question
Title: How to show that i have significant improvements over the baselines?
I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines.

I tried my classification algorithm on some image datasets such as Extended Yale, and in the literature (other papers) i noticed the same amount of improvements in the results was assumed good enough (e.g. only 0.20 % improvements).

So, how should i convince the reviewers that my results are good enough according to the previous works?

# Answer
Odds are, you can't. That's a judgement call, and it's notoriously hard to get other people to change their judgement. The path is to find new evidence or facts they might not be aware of; assemble a persuasive argument; and see what happens.

But in this case, without knowing anything about the domain, I suspect the reviewers might be right. Why would a difference in accuracy of 0.20% make a practical difference? What new capability would it provide? How much money would it save? Often it's not that significant.

I see this misconception a lot. People see another paper was accepted (to a different conference/journal), see that it had improvement of X%, assume that it was accepted because of X% improvement, and assume that if they get X% improvement their paper will/should be accepted too. Neither of those assumptions is valid. You don't know why that other paper was accepted. Maybe it was accepted because the ideas it had were intriguing. Maybe it was accepted because the paper made other contributions. Maybe it was accepted because that conference/journal has lower standards. Maybe it was because that kind of improvement was worth one paper being published, once, but not two. Maybe it was because the reviewers were in a good mood that way. Maybe it was something else. Who knows. And just because reviewers want to accept one paper with X% improvement on task T, doesn't mean they'll want to accept 10 papers or 100 papers with X% improvement on task T.

Don't delegate your judgement to reviewers (that other paper was accepted, so it must be good). Form your own standards of what counts as valuable work. Then, strive to make your work meet those standards. That will enable you to articulate why your paper is significant and should be accepted, on its own merits.

This is a topic you should be discussing with your advisor/supervisor and your co-authors, as they know the work you're doing and (hopefully) know the domain area and can give you much more informed advice.
> 2 votes

---
Tags: classification, performance, evaluation-strategies
---


title: Maximal derangements

text:
# Question
Title: Maximal derangements
When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like to know whether there is a sensible general measure of derangements of n objects and efficient algorithm to compute that measure and eventually also to determine the set representing maximal derangements.

# Answer
> 5 votes
I second Raphael's remark that when shuffling cards, you don't want the deck to be "unsorted", but rather random. However, when analyzing any specific shuffle, there can be measures of randomness that can be used to *prove* that a small number of shuffles isn't enough to make the deck random enough.

As a simple example, consider the "top card shuffle", in which you repeatedly take the top card and place it at an arbitrary location. If you don't repeat this enough times, then the top $k$ cards will retain their relative order (since you never put the top card somewhere among the top $k$ cards). So a reasonable measure of "sortedness" would be the maximal $k$ such that the top $k$ cards retain their relative order - for a shuffled deck, we expect this to be very small.

There is a similar measure for riffle shuffle, namely the number of *ascents*, two adjacent cards which retain their relative order. A random permutation has $n/2$ ascents, while an (under-)riffle-shuffled deck will have too many.

All this and more is described in David Aldous and Persi Diaconis, *Shuffling cards and stopping times*.

# Answer
> 1 votes
Although Yuval Filmus' answer addresses the question behind the question, and comments partially answer the explicit question, there are other parts of the explicit question which remain unanswered by previous comments and answers.

> I like to know whether there is a sensible general measure of derangements of n objects

As previously mentioned in comments, the number of inversions is a general measure of how out-of-order a permutation is.

> and efficient algorithm to compute that measure

There is a standard algorithm to compute it in $\Theta(n \lg n)$ by adapting mergesort.

> and eventually also to determine the set representing maximal derangements.

The reversed permutation. And *this* is the big reason why, as Yuval Filmus says (in different words), the aim is to maximise entropy rather than to maximise the derangement. A reverse-ordered deck of cards is just as bad as an ordered deck of cards when it comes to playing games with it.

# Answer
> 0 votes
I am a total noob, but as I try to get some C++ chops in order before Data Structures and Algorithms Class this Fall I wrote a super easy disorder function in a Class named Array which generates int arrays filled with randomly generated numbers:

```
void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

```

Simply compares the value in each element to the index of the element + 1 so that an array in reverse order has a disorder value of 1, and a sorted array has a disorder value of 0. Not sophisticated, but working.

Michael

---
Tags: combinatorics, probability-theory, permutations
---


# Question
Title: Is a sum of n terms considered O(1) or O(n)?
Say I have $n$ numbers in an array and I have to compute the sum of those numbers. Is the complexity considered as $O(1)$ or $O(n)$?

**Clarification**

Say I have 10 constants, I could precompute the total and claim that overall, the complexity is $O(1)$. Yet, if I have 10 assigned variables, I would have to perform 10 additions to compute the total, which implies $O(n)$.

Another way to formulate my question is: Does $O()$ depends on the number of unknowns (i.e. variables) only? How are constants considered?

# Answer
> 8 votes
If you have ten elements, then that's a constant and considered $O(1)$. However, if you're given an input to a function, and want to analyze the running time of your algorithm in terms of the input length, then that's $O(n)$, provided that you at least read the entire array (and $n$ is the array length).

It all has to do with *what you measure your running time in*. In parameterized complexity, for instance, we typically measure the complexity in *two* parameters; the length of the input, and an additional *parameter* $\kappa$. Hence, there you will often see running times like $O(n \cdot 2^\kappa)$.

In your problem, we say $O(n)$ because we sometimes consider "summing integers" as a constant operation. That's obviously not possible if we allow arbitrarily large integers. If the max (absolute) integer is $N$, then your algorithm might be $O(n \log N)$.

---
Tags: complexity-theory, asymptotics
---


# Question
Title: number of random sets needed to generate subset
Let $A\subseteq \\{1\ldots n\\}$ with $|A|=\alpha n, 0\<\alpha\leq1$. Now we start generating random sets $B\_i \subseteq \\{1\ldots n\\}$ with $|B\_i|=\beta n$ where $0\<\beta\leq\alpha$.

How many $B\_i$ do we have to generate, so that there exists a $j: B\_j\subseteq A$ with decent probability (constant or overwhelming in $n$).

It holds that $\Pr\[B\_i\subseteq A$ for a fixed $i$\]=${\binom{\alpha n}{\beta n}}/\binom{n}{\beta n}$. If the probabilities for all $B\_i$ would be independent we could make use of the geometric distribution to calculate (or at least bound) the probability that after generating $N$ random $B\_i$ there is no $B\_i: B\_i\subseteq A$. But as soon as the $B\_i$ start intersecting the probabilities seem not to be independent anymore. Any help would be appreciated.

**Edit:**

Ok, I guess my problem is, that I do not understand, if we are facing dependencies or not. So let me give some more details: The set $A$ is unknown, but we get access to an oracle $\mathcal{O}(B\_i)$, that for input $B\_i\subseteq \\{1,...,n\\}$ with $ |B\_i|=\beta n$ outputs true, if $B\_i \subseteq A$ holds and false otherwise. The $B\_i$ are generated independently at random and tested sequentially for being a subset. So if the probabilities for all $B\_i$ being a subset of $A$ are independent it must especially hold, that $$\Pr\[B\_2\subseteq A | B\_1\not\subseteq A\]=\Pr\[B\_2\subseteq A\]$$

But doesn't the probability of $B\_2$ being a subset of $A$ conditioned on $B\_1$ being not a subset of $A$ depend on the size of the intersection of $B\_1$ and $B\_2$? So for example if $|B\_1\cap B\_2|=\beta n \Leftrightarrow B\_1=B\_2$ than $\Pr\[B\_2\subseteq A | B\_1\not\subseteq A~\wedge~ B\_1=B\_2\]=0$. Or does this just mean that all three events $(B\_2\subseteq A, B\_1\not\subseteq A, B\_1=B\_2)$ are not independent, but $B\_2\subseteq A$ and $B\_1\not\subseteq A$ can still be independent? If so, can we give a formal proof, that these events are indeed independent?

# Answer
The sets $B\_i$ can be independent but still have an intersection; just because they are generated independently doesn't prevent them having an element in common (in fact, it ensures that possibility exists). If you assume that the sets $B\_i$ are generated independently, then they are independent, period. If you don't assume that, you have to define how you assume that they are generated before you can calculate any probabilities.

---

Regarding your updated question: "But doesn't ... ?" - Answer: No, it doesn't. If the r.v.s $B\_1,B\_2$ are independent, then the events $B\_1 \not\subseteq A$, $B\_2 \subseteq A$ are independent.

If you want a formal proof, here is one. If $B\_1,B\_2$ are independent random variables and $f$ is any function, then $f(B\_1),f(B\_2)$ are independent random variables. (You should try to prove it; it is not hard.) Then let $f(X)$ be true if $X \subseteq A$, or false otherwise, and the claimed result follows.
> 2 votes

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


# Question
Title: How to construct a branching program for this function?
Suppose we have a formula $F(x\_1,x\_2,x\_3) = x\_1 \vee (x\_2 \land x\_3)$. $F$ outputs 1 when it has a satisfying assignment and 0 otherwise.

How can I convert the above formula(or any formula like this in general)to a branching program(constant width)?

# Answer
> 2 votes
Here is a general way to convert a formula to a branching program. The construction is recursive, and it constructs branching programs with an initial vertex and two terminal vertices, labeled 1 (true) and 0 (false).

* The formula is a variable $x$: the initial vertex queries $x$, and according to the answer proceeds to the two terminal vertices.
* The formula is of the form $\phi \lor \psi$. Construct branching programs $P\_\phi,P\_\psi$ to the two subformulas. Identify the 0 output of $P\_\phi$ with the initial vertex of $P\_\psi$, and the 1 outputs of both programs.
* The formula is of the form $\phi \land \psi$. Construct branching programs $P\_\phi,P\_\psi$ to the two subformulas. Identify the 1 output of $P\_\phi$ with the initial vertex of $P\_\psi$, and the 0 outputs of both programs.
* The formula is of the form $\lnot \phi$. Construct a branching program for $\phi$, and switch the labels of the terminal vertices.

---
Tags: algorithms
---


title: Sorting some set of number

text:
# Question
Title: Sorting some set of number
Let $U=\\{1,2,3\cdots m-1\\}$ and some $n$ keys from $U$. Is it possible to sort these $n$ keys in $O(n \log \log n)$ time using $O(n)$ space?

Model of computation is RAM.

# Answer
The algorithm is studied by Yijie Han in his paper \[1\].

There's also a relevant question on *cstheory*: Han's $O(n\log\log n)$ time, linear space, integer sorting algorithm.

---

\[1\] Han, Y. (2002, May). Deterministic sorting in O (n log log n) time and linear space. In *Proceedings of the thiry-fourth annual ACM symposium on Theory of computing* (pp. 602-608). ACM.
> 2 votes

# Answer
I think you may need to clarify your question. It is certainly not possible as written, because the running time and space usage should depend on $m$, not just on $n$.

In particular, if $m$ is very large, then $n$ numbers may take a large amount of space to write out in the first place, which immediately lower bounds the running time.
> 1 votes

# Answer
It is possible to sort them in $O(n)$ time using $O(1)$ extra space. So yes.
> 0 votes

---
Tags: sorting
---


# Question
Title: How is the (local) clustering coefficient defined for vertices with degree 1
We want to compute the clustering coefficient $C$ for an undirected graph $G = (V, E)$.

The clustering coefficient $C$ for a graph $G$ is the average over all local clustering coefficients $C\_i$, whereby $C\_i$ is the local clustering coefficient of a vertex $v\_i$ such that $i$ is a generic index and $v\_i$ is a member of the network, i.e. $v\_i \in V$.

The local clustering coefficient $C\_i$ is defined as the ratio between the number of existing edges within the neighborhood of a vertex and the number of possible edges within the neighborhood of a vertex. Therefore, $C\_i = \frac{2n}{k\_i (k\_i -1)}$, such that $n$ is the number of edges within the neighborhood of vertex $v\_i$ and $k\_i$ is the degree of vertex $v\_i$.

For vertices with $k\_i = 1$, the denominator becomes $0$ and the whole term becomes undefined.

Given that the clustering coefficient is the ratio between the number of possible edges in the neighborhood of a vertex and the actual number of edges, a vertex with $k\_i = 1$ cannot have any edges within its neighborhood, as there no such neighborhood. Hence, is it reasonable to use $C\_i = 0$ in cases where $k\_i = 1$?

# Answer
Yes, it is reasonable and common to have $C\_i = 0$ when $k\_i \< 2$. This is sometimes a matter of taste, and some software libraries like igraph lets the user define how to handle the small-degree cases (i.e., whether to return 0 or NaN).
> 1 votes

---
Tags: graphs, clustering
---


# Question
Title: Merge sort worst case running time for lexicographical sorting?
A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge step would be $O(n^2)$. So the recurrence should be of the form

> $$T(n) = 2T(\frac n2) + O(n^2)$$

By master's theorem it solves to $O(n^2)$.

Somehow some people on the internet claim the following explanation: Merge sort makes $O(nlogn)$ comparisons and since it is lexicographical sort each comparison take $O(n)$ time, so worst case time is $O(n^2logn)$.

Which of the above is correct and if at some point i am incorrect please correct me.

# Answer
The recurrence formula is incorrect.

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.
> 4 votes

---
Tags: algorithms, asymptotics, sorting, mergesort
---


# Question
Title: What exactly is the semantic difference between category and set?
In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of asking the same about categories:

Every time I read about category theory (which admittedly is rather informal), I can't really understand how it differs from set theory, **concretely**.

So in the most **concrete** way possible, what exactly does it **imply** **about $x$** to say that it is in the category $C$, compared to saying that $x\in S$? (e.g. what is the difference between saying $x$ is a group, versus saying that $x$ is in the Category $\mathrm {Grp} $?).

(You may pick any category and set that makes the comparison most clarifying).

# Answer
> 18 votes
In brief, set theory is about membership while category theory is about structure-preserving transformations – but only about the relationships between those transformations.

**Set theory** is only about membership (i.e. being an element) and what can be expressed in terms of that (e.g. being a subset). It does not concern itself with any other properties of elements or sets.

**Category theory** is a way to talk about how mathematical structures of a given type1 can be transformed into one another2 by functions that preserve some aspect of their structure; it provides a uniform language for speaking of a great range of types1 of mathematical structure (groups, automata, vector spaces, sets, topological spaces, … and even categories themselves!) and the mappings within those types1. Although it formalises the properties of mappings between structures (really: between the sets on which the structure is imposed), it only deals with abstract properties of maps and structures, calling them *morphisms* (or *arrows*) and *objects*; the elements of such structured sets are not the concern of category theory, and nor are the structures on those sets. You ask “*what is it a theory of*”; it is a theory of *structure-preserving mappings of mathematical objects of an arbitrary type1*.

The theory of **Abstract categories**3, however, as just stated, totally *ignores* the sets, operations, relations and axioms that specify the *structure* of the objects in question; it just provides a language in which to talk about how mappings that do preserve some such structure behave: without knowing what structure is preserved, we know that the combination of two such maps also preserves structure. For that reason, the axioms of category theory require that there be an associative composition law on morphisms and, similarly, that there be an identity morphism from each object to itself. But it does not assume that morphisms actually *are* functions between sets, just that they *behave* like them.

In **Concrete categories**, however, the objects really do correspond to sets and the morphisms to mappings of those sets, or they correspond to objects and morphisms of some other ‘base category’ than $\mathsf{Set}$. Concrete categories model the idea of adding structure to the objects of the base category, although we still ignore that actual structure: we consider only the morphisms of the base category and the abstract behaviour of the morphisms of the concrete category. For example $\mathsf{Grp}$, the category of groups, may be made into a concrete category (over $\mathsf{Set}$), by specifying the homomorphisms as mappings of the underlying sets of the groups; however, this tells us nothing about the group multiplication operations themselves.

As for the **implications** of your **formulations**, saying that “$G$ is a group”, that “$G$ is an element of the set of groups” (actually a proper class) or that “$G$ is (an object) in $\mathsf{Grp}$” (or a “$\mathsf{Grp}$-object”) mean the same thing logically, but talking about the category suggests you are interested in group homomorphisms (the morphisms in $\mathsf{Grp}$) and perhaps in what they have in common with other morphisms. On the other hand, saying $G$ is a group might suggest you are interested in the structure of the group (its multiplication operation) itself or perhaps in how the group acts on some other mathematical object. You would be unlikely to talk about $G$ belonging to the class (not really “set”) of groups, though you could easily write $ G ∈ S $ for some particular collection $ S $ of groups you are interested in.

### See also

1 Here and throughout I do not refer to “type” in the sense of type theory, but rather a set of properties required of the mathematical objects/structures, i.e. a set of axioms they satisfy. Normally these describe the behaviour of some operations or relations on elements of the sets considered to carry the structure, though in the case of sets themselves ($\mathsf{Set}$) there is no structure beyond the sets themselves. In any case, as said above, category theory ignores the details of this structure.

2 I should perhaps say “*into all **or part** of one another*”: one allows the homomorphism from $ \mathbb Z $ (integers) **into** $ \mathbb Q $ (rationals) given by $ n \mapsto \frac n 2 $ .

3 Without qualification, ‘*category*’ normally means ‘abstract category’, introduced, as far as I can see, in 1945 and developed in the 1960’s while *Concrete categories* seem to appear in the 1970’s.

# Answer
> 5 votes
Category theory is in some sense a generalization of set theory: the category $C$ could be the category of sets, or it could be something else. So, you learn *less* if you learn that $x$ is an object in some unspecified category than if you learn that $x$ is a set (since in the latter case it follows that $x$ is an object in specifically the category of sets). If you learn that $x$ is an object in a *particular* specified category (other than the category of sets), what you learn is different from learning that $x$ is a set (i.e., an object in the category of sets); neither implies the other.

There's no difference between saying that $x$ is a group vs saying that $x$ is an object in the category Grp. Those two statements are equivalent.

Note: we don't say that $x$ is in the category Grp; we say that $x$ is an *object* in the category Grp. A category has both objects and arrows. You need to specify which you are talking about.

# Answer
> 4 votes
A further point on D.W.'s explanation

> There's no difference between saying that $x$ is a group vs saying that $x$ is an object in the category $\mathsf{Grp}$. Those two statements are equivalent.

I'd like to make a stronger statement:

> A concept is defined by its category

Think of it from the pespective of an inventor wanting to explain his concept. Suppose your new concept is called $M$. First, you might have to specify how many variations of instances of things that are $M$ can there be. Let's call that collection of instances $M\_0$.

Now since you said that there are many things that are $M$, you have to explain each of them compares/relate to each other. You explain why do you think they are different instances of $M$. There might even be multiple ways in which $A \in M\_0$ could be compared to $B \in M\_0$ each other. Or in some cases, there might be no way to compare them at all. Let's denote that collection of ways to compare $A$ to $B$ as $M(A,B)$.

You probably notice already that $M\_0$ forms the collection of objects and $M(A,B)$ is the homset of a category. The laws of category theory then lays out the expected behaviour of 'comparison'.

Once you have that, the category gives you many default property of the concept. Examples range from

* "which instances are essentially the same --- isomorphism",
* "which of these two instance is more and which is less --- section-retraction pair",
* "How many of the basic elements are inside this instance? --- homset from terminal object"

and so on.

---

As for the question you ask in comment

> What mathematical process/structure is category theory a theory of?

You now know the drill. Want to know what a concept really is? Look at its category. In this case, $\mathsf{Cat}$ the category of small categories and functors between them.

# Answer
> 3 votes
**Sets**

*Basic concept*. membership relation $$x\in A$$

*Other concepts.* Function is explained in terms of membership relation as a set $f$ of ordered pairs with $$(x,y)\in f\text{ and }(x,z)\in f \Rightarrow y=z$$

*Philosophy.* Sets have an inner structure - they are completely determined by their elements.

*Remark.* An axiomatic system widely used by set theorists is ZFC. Its strength is the simplicity: there are only sets and a membership relation. On the other hand many mathematicians feel that this leads to a set concept that diverges from their understanding and usage of sets (compare below *Leinster*). In fact tha vast majority of mathematicians (except set theorists) seems not to use the ZFC axioms. However, *sets* do not necessarily refer to ZFC (see below *categories* and ETCS).

---

**Categories**

*Basic concept.* function (arrow, morphism) $$A\rightarrow B$$

*Other concepts.* Membership relation $x\in A$ is explained in terms of an arrow from a terminal object (in *Set* a terminal object is a singleton set $\\{y\\})$ $$x:1\rightarrow A$$

*Philosophy.* Objects of a category have a priori no inner structure. They are just characterized by their relations (morphisms) to other objects.

*Remark.* The basic concept of categories is *function* and this coincides with the usage of sets by the vast majority of mathematicians. Therefore you might see categories as a conceptual generalization of the way that (most) mathematicians from very different fields use sets in their daily work. Apart from categories (and toposes) as a generalization you might have a look at the axiomatic system ETCS that is axiomatizing sets (compare below *Leinster* and *Lawvere*).

---

> **Question.** What is the difference between saying x is a group, versus saying that x is in the Category Grp?

One might say the difference is not in the object $x$ itself but rather how you intend to deal with $x$.

(1) Do you ask for the inner structure of $x$? In this case it might appear natural to regard $x$ as a set.

(2) Do you ask how $x$ relates to other objects of same kind (via morphisms) or of other kind (via functors)? In this case you might tend to see $x$ as an object in the category of groups.

---

**Critics**

In case of ZFC and ETCS these approaches can be translated into each other, although ETCS is weaker than ZFC but (seemingly) covers most mathematics (see MathStackExchange and Leinster). In principle (using an extension of ETCS) you can prove the same results with both approaches. So the above mentioned philosophies of both concepts are not claiming a fundamental distinction in what you can express or what results you can prove.

The expressions *set* and *membership* in ZFC are abstract concepts just like the concepts of categories or any other axiomatic system and can mean anything. So from this formal viewpoint, to claim, that ZFC is concerned with the *inner* structure of sets whereas categories deal with the *outer* relations of objects to each other seems inappropriate. On the other hand this seems to be the philosophy or intuition of the regarding theories.

However in practice you will prefer a certain Approach for e.g. the sake of clarity or simplicity or because some concept or a connection to another area evolves more naturally than elsewhere.

---

**References**

Spivak.Category theory for scientists

Leinster.Rethinking set theory

Lawvere.An elementary theory of the category of sets

MathStackExchange.Category theory without sets

---
Tags: sets, category-theory
---


# Question
Title: what is the expected number of comparisons made before the algorithm terminates?
How to approach this question ? I have no idea regarding the method to be applied for solving such kinds of problems .

# Answer
> 2 votes
You can learn the meaning of (mathematical) expectation at wikibooks or check its definition at wikipedia.

A reasonable assumption is that each combination of the positions of the two x's has the same probability. There are total $\binom{n}{2}$ combinations. Among them, there are $n-i$ combinations in which the first occurrence of $x$ appears at the $i$-th position, each of which requires $i$ comparisons since the algorithm stops once it have found the the first occurrence of $x$. Let us compute **the expectation**.

$$\qquad \begin{align} E = i \sum\_{i=1}^n \frac{n-i}{\binom{n}{2}} &= \frac{1}{\binom{n}{2}}\left(n\sum\_{i=1}^ni -\sum\_{i=1}^ni^2 \right)\\ &= \frac{1}{\binom{n}{2}}\left(\frac{n^2 (n+1)}{2} - \frac{n(n+1)(2n+1)}{6}\right)\\ &=\frac{n+1}{3} \end{align}$$

Given that simple answer, we will wonder if there is **a simple explanation**. Indeed, there is one. The array $A$ is separated into three parts by the two $x$'s. The total number of values in those three part is $n-2$. Those three parts are symmetric with respect to the number of values in them. So the expected length of the first part is $(n-2)/3$. Adding the one comparison that finds $x$ made right after the end of the first part, we find the expected number of comparisons made by the algorithm is $(n+1)/3$.

In particular, the answer to the original question, "for $n=5$" is $(5+1)/3=2$.

Here is **a generalized version of the problem**. What is the expected number of comparisons made by an algorithm that stops right after it have found the $k$-th occurrence of $x$ in an array of $n$ numbers where $x$ appears $m$ times. It is left as an easy exercise for our readers to find its answer.

# Answer
> 0 votes
You can compute expectation by its definition. First compute the probaility of the first occurences would be in position $i$. As we have $\binom{n}{2}$ in total number of possibilities, this probaility is $\frac{n-i}{\binom{n}{2}}$. Hence the expectation is $\sum\_{i=1}^n \frac{n-i}{\binom{n}{2}} \times i = O(n)$ which $i$ inside the sum is the number of comparisons.

---
Tags: algorithms
---


# Question
Title: Average case of simple algorithm like binary search
These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me.

I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations.

Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.

This element may take tree label, say $L$, $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M$, then we found the solution. Else, if the label is $l$, then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R$, i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference that the first element is not the median of array. we can summarize the above statements as the following algorithm.

```
Input: An array $A$ with length $n$.
while length(A) > 1 do
 1.  choose an element $k$  (for example, randomly with uniform
     distribution) with $O(1)$. Find its label with $O(1)$.
 2.If the label is $M$, then stop
 3. else if the label is $l$ then  delete $k$ and all elements before $k$.
 4. else if the label is $r$ then  delete $k$ and all elements after $k$.
end while

```

I know that the worst case complexity is $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?

# Answer
> 3 votes
The average case time complexity is $O(\log n)$ (with a suitable implementation). Intuitively, each iteration typically removes a constant factor of the elements from the array.

Here's a more formal analysis. Consider an iteration to be "good" if it removes at least $1/3$ of the elements of the array. Then an iteration is good with probability $2/3$. Let $X\_1$ denote the number of iterations until the first good iteration; this is a geometric random variable, so its expected value is $1.5$. Let $X\_2$ denote the number of iterations after the first good iteration, until the second good iteration. Again, the expected value of $X\_2$ is $1.5$. And so on. Now note that after $j$ good iterations, only a $(2/3)^j$ fraction of elements remain, so after at most $k = \lg\_{2/3} n$ good iterations, the array will have only a single element and will terminate immediately. The total number of iterations is $X\_1 + X\_2 + X\_3 + \cdots + X\_k$. By linearity of expectation, the expected value of this sum is $1.5k$. Thus the expected number of iterations until this terminates is $1.5 \lg\_{2/3} n = \frac{1.5}{\log(2/3)} \log n = O(\log n)$.

You can implement this so each iteration takes $O(1)$ time. In particular, you don't actually remove elements in steps 3 and 4; you just keep track of the range of indices of non-removed elements. That's always a consecutive range, so everything is easy.

In this way, the algorithm takes $O(\log n)$ iterations on average, and $O(1)$ time per iteration, for an average-case running time of $O(\log n)$.

Incidentally, with this implementation, the worst case running time is $O(n)$ rather than $O(\log n)$. Each iteration of the loop removes at least one element from the array, so there can be at most $n$ iterations of the loop, and each iteration runs in $O(1)$ time, for a total of $O(n)$ worst-case running time.

---
Tags: time-complexity, randomized-algorithms, average-case
---


title: Super-strongly connected components?

text:
# Question
Title: Super-strongly connected components?
I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph.

I want to find subgraphs $G\_1,G\_2, \dots,G\_n$ of $G$ such that

* they do not overlap (i.e. don't share any nodes)
* each two nodes in a subgraph are connected by an edge, i.e. $\forall i \forall n,m\in V\_i$ then $\\{m,n\\}\in E\_i$ where $G\_i=(V\_i,E\_i)$.

My question is: How to solve this problem? Is there any specific name of this problem?

Edit: The graph I am dealing with is very sparse. Coloring based approximations may not work as the complement graph would be huge (not able to store it in memory).

# Answer
> 4 votes
This is called the Minimal Clique Cover Problem, and is NP-hard: as a matter of fact, the decision version ("can I do it with only $k$ subgraphs?") is one of Karp's original 21 Problems, the ones that first defined NP-completeness.

Since it's linked to graph coloring, you can't even get a good approximation in polynomial time, unfortunately: everything about this problem is hard.

For further reading, your "super-strongly connected components" are generally called *cliques*, and a *clique cover* is a way to "cover" the entire graph with non-overlapping cliques. A *minimal clique cover* uses the smallest possible number of cliques to do it.

# Answer
> 3 votes
There is no polynomial algorithm for the problem you mentioned (assuming $P\neq NP$).

You can use an algorithm for the problem you mentioned to compute the chromatic number of a given graph $G=(V,E)$.

Here is how: On input $G=(V,E)$, take the compliment graph $\overline{G}=(V,\overline{E})$ (where $\overline{E}$ is the compliment of $E$), so a partition of $\overline{G}$ into $k$ subgraphs is equivalent to $k$-coloring of $G$:

Given "super strongly connected" partition of $\overline{G}$ into $k$ subgraphs, you can color the vertices of each subgraph with a different color and get $k$-coloring of $G$.

In the other direction, given a $k$-coloring of $G$, you can partition $\overline{G}$ according to the colors ($\overline{G}\_i$ would be the subgraph containing all vertices which are colored with the $i$th color) and get a "super strongly connected" partition of $\overline{G}$ into $k$ subgraphs.

---
Tags: graphs
---


# Question
Title: How to calculate the weight between neurons in ANN?
I am currently learning Supervised ANN training using Backpropogation and I am stuck in this exercise. I calculated the δA using the equation at the bottom of the screenshot, however, I am unable to calculate δB because the weight of BD is not given. How do I find the weight of BD?

# Answer
> 0 votes
As far as I can tell, the information provided does not appear to be enough to answer your question, though I confess I am not familiar with what a "unipolar continuous threshold function" is, and it is not clear to me what $f(\text{net}\_A$) represents nor what the loss function for this task is. You might need to talk to your instructor or wherever you got that image from. You might ask them what a "-" over an edge means.

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


# Question
Title: Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$
> Find the asymptotic bound in terms of $\Theta$ (Theta) using the **master theorem** for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$$

I am a bit confused on how to approach such question, I did solve questions such as $t(n)=3t(n/4)+nlogn$, but never saw an example where $t(n)=at(\frac{n}{b})+ct(\frac{n}{d})+f(n)$.

Any solutions or hints on how to solve this problem would be appreciated.

# Answer
If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean $\Theta(n)$ or $\Theta(n\ln n)$ is an easy approach.

Otherwise, let us see how we can use the master theorem. We assume here $t(n)\geq 0$ for all $n \geq 0$, although the final asymptotic answer is actually valid without that non-negativity restriction. Let $c$, $m$ be two positive constants such that $t(n) \lt m$ for all $n \< c$.

To bound $t$ from below, let us define function $t\_1$ by $$t\_1(n) = \begin{cases} 0 & n \<= c\\ t\_1\left(\frac{n}{5}\right) + n & n\gt c \end{cases}$$

To bound $t$ from above, let us define function $t\_2$ by $$t\_2(n) = \begin{cases} m & n \<= c\\ t\_2\left(\frac{n}{5}\right) + (t\_2\left(\frac{n}{5}\right) + m) + n & n\gt c \end{cases}$$

The rest of this solution will be proving $t\_1(n)\leq t(n)\leq t\_2(n)$ for all $n\ge 0$ by induction followed by applying the master theorem to $t\_1$ and $t\_2$ to show that $t(n) = \Theta(n)$. It is left as an easy exercise for interested readers.
> 3 votes

---
Tags: asymptotics, master-theorem, divide-and-conquer
---


# Question
Title: Is the symmetric difference of a non regular language L and a finite language f non regular?
The symmetric difference of $L\_1$ and $L\_2$ is defined to be: $(L\_1-L\_2) \cup (L\_2-L\_1)$.

**Problem:** I’m trying to prove that given L a non regular language and F a finite language there symmetric difference yields a non regular language.

Although this looks like it should be a very simple problem and it seems very obvious to me since I’m only changing the language finitely, I can’t seem to prove it.

**My progress:**

we have: (L-F)U(F-L). the right hand side is a finite language. So this problem will be solved if we prove these two statements: A) L-F is non regular when L and F are non regular and finite (respectively). B) LUF is non regular when L and F are non regular and finite (respectively).

I originally thought I had a very simple solution for each of these using a proof by contradiction with the pumping lemma (based on the largest length of a word in the finite language) but I later remembered that the pl is not a sufficient condition to be regular thereby invalidating my argument.

Something that seemed like a good approach is the Myhill-Nerode theorem but I can’t seem to get anywhere because I wasn’t able to prove that there must be an infinite number of “dividing words” z which would mean the finiteness of F could not account for them.

In the end I came up with a simple proof by contradiction of A using regular expressions, But can’t seem to get B using a similar approach.

So, if you can help me solve B or the original problem that would be great.

# Answer
> 4 votes
Denoting symmetric difference by $\Delta$, note that $(L \Delta f) \Delta f = L$. This suggests the following strategy: show that the symmetric difference of a *regular* language and a finite language is regular. This implies your claim via proof by contradiction.

The product construction shows the stronger fact that the symmetric difference of two regular languages is regular. Hence you can strengthen your claim by replacing "finite" with "regular".

---
Tags: formal-languages, regular-languages, automata, finite-automata
---


# Question
Title: Skip List estimate number of elements less than (or greater than) a value
I am looking for a thread safe data structure where

1. an element can be searched in $O(\log n)$,
2. for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
3. an element can be inserted in $O(\log n)$, and
4. an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used? Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?

# Answer
> 1 votes
Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach. Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.). Annotate each node with the size of the subtree under that node. Then, make this data structure persistent. This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely. In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable. Instead, updates essentially work by creating a new copy of the data structure. Thus, each thread has its own copy of the tree. The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree. To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry). Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.

# Answer
> 1 votes
It is possible to extend skip lists with so called "width of the link". For each link it says how many elements are skipped by follow this link. From Wikipedia (section Indexable skiplist):

```
   1                               10
 o---> o---------------------------------------------------------> o    Top level
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
   1     1     1     1     1     1     1     1     1     1     1
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level

Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

```

These links are easy to update during (non-concurrent) traversals of insert and delete operations. It is as well easy to keep track of total number of skipped elements.

So yes, one can extend skip lists to find the position of the element in the list. But concurrent updates of the counters still might be a problem.

---
Tags: algorithms, data-structures, time-complexity, multi-tasking
---


# Question
Title: What does `Dv` mean in $F\star$ language?
In the $F\star$ tutorial it says

> `Dv`, the effect of a computation that may diverge;

what does *diverge* mean here? It's not explained and it confuses me.

I guess it means the type consists but the value varies, but if so why there isn't a non-diverge non-terminate effect?

# Answer
> 5 votes
In the theory of computation "diverge" means "does not terminate" or "runs forever". This is a computational effect (of a peculiar kind).

---
Tags: proof-assistants, fstar
---


# Question
Title: Why is fully homomorphic encryption so slow?
What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times compared to conventional calculations)?

Or there is some fundamental limitation and any FHE implementations will always be millions of times slower than usual calculations?

# Answer
I don't know how to answer why it's slow; it's slow because it's slow? The algorithm involves a lot of computation, and that takes a long time to do.

Is it possible to make a fast FHE? No one knows. It's an open problem. If it was easy, we would have done it so far. So either it's not possible; or it's possible but it's challenging and we currently don't know how to do it.

In some sense, it's not surprising that FHE is a lot slower than traditional cryptography. FHE imposes some very strong requirements on the encryption scheme. This constrains what kind of encryption scheme you can use. It's no surprise that if you add extra requirements, it's harder to make the scheme also be fast; and it feels reasonable that the stronger the requirements, the slower this might make the scheme. In this case, the FHE requirement is very strong indeed.

I'm not aware of any proof that FHE must be slow. However, there are some results that may be somewhat indicative. In particular, the following paper shows that any FHE scheme can be broken in subexponential time (while we believe that traditional encryption schemes require exponential time to break). This means that the FHE scheme will require larger parameter sizes to be secure. Usually, larger parameter sizes mean that the scheme will be slower. So, that is some weak indication that FHE schemes will need to be slower. However, it doesn't really answer the question; it's just a hint.

Algorithms for black box fields and their application to cryptography. Dan Boneh, Richard Lipton. CRYPTO '96.
> 3 votes

---
Tags: cryptography
---


# Question
Title: Algorithm to establish a global ranking given individual rankings
I am looking for an algorithm(s) that can compute a global ranking (partial ordering) given individual rankings, in some kind of principled manner.

I want to establish a partial-ordering of some projects, and had some users create their own partial orderings.

I've looked at these algorithms so far:

* borda-0
* borda-1
* Dowdall

My problem is that these algorithms were not really designed to establish partial-ordering and are instead for choosing N winners. I haven't been able to find any widely-used algorithms for this purpose.

I looked at adapting STV to this purpose, but raw STV gives no instructions on how to resolve ties, and it's unclear to me what properties it would have when applied to partial ordering.

Is there a widely-used algorithm/family of algorithms for the problem?

# Answer
There is an entire area, *rank aggregation* (in your case, *partial rank aggregation*) which deals with these issues. You can take a look at Dwork et al., Rank aggregation revisited and Ailon, Aggregation of partial rankings, $p$-ratings and top-$m$ lists and the pointers therein. There are many other relevant papers online.
> 5 votes

---
Tags: partial-order
---


title: OS process management

text:
# Question
Title: OS process management
Assume a process execution interrupted at the middle and CPU started executing a different process.How does the OS handle this situation?

# Answer
The way you worded the question, it sounds like the CPU starts executing a different process, and the operating system must react to this. But this is not how it works.

There are two ways to switch between processes. Both involve the operating system. One way is if the process calls the operating system. The other way is if an interrupt happens; in this case the CPU invokes an interrupt handler which is part of the operating system. In both cases, the operating system may take the decision to either return to the previous process, or to switch to a different process.
> 0 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Split graph in two parts, such that most nodes have even number of edges
We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between nodes of different parts are destroyed and not counted.

All possible splittings are allowed, even the one where all nodes are in one part. Each node should be in one part, we are required to print the nodes of one part.

This given graph has $5$ nodes, and the splitting made here is best because all nodes have even number of edges in the same part.

My idea was to do BFS over the nodes and when we find node with odd number of edges to put one node in the other part, but I can't come up with some strong idea.

# Answer
By induction , we can prove that a partition exists with all nodes having even degree within the partition.
If all vertices have even degree , then we are done (Just partition it into the whole graph and an empty graph)
Otherwise let $v$ be a node with odd degree , now modify the graph by inverting the neighbourhood of $v$ (If $a$ and $b$ are neighbours of $v$ , then if they have an edge , remove it otherwise add it) and also remove $v $ from the graph , for the new graph , split it into 2 parts $A$ and $B$ such that all nodes in $A$ and $B$ have even degree , add $v$ back to $A$ if $A$ has even neighbours of $v$ , else add it to $B$. This works because in $A$(Or $B$ if we added $v$ to $B$) all degrees are even except for neighbours of $v$ which become even after adding $v$
> 2 votes

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


# Question
Title: Finding a partition with minimum "maximal length"
We're given $n^2$ different points in $(0,1)$ : $x\_1\< x\_2 \< \dots \< x\_{n^2}$.

We are required to choose $n$ points $x\_{i\_1}\<\dots\<x\_{i\_n}$ such that the value of $\max\\,\\{x\_{i\_1}, x\_{i\_2}-x\_{i\_1}, x\_{i\_3}-x\_{i\_2},\dots,x\_{i\_n} - x\_{i\_{n-1}}, 1-x\_{i\_n}\\} $ is minimal.

It feels a lot like a dynamic programming problem, but I didn't manage to divide it into appropriate subproblems.

Any ideas?

# Answer
This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:

> How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question.

This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are **the subproblems stated explicitly**.

> Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$? $$ m(w,k) := \min\_{i\_0 = 0,\\,i\_k = w,\\,i\_1\lt\cdots\<i\_k} \max\\{x\_{i\_1} - x\_{i\_0},\\,x\_{i\_2}-x\_{i\_1},\\,\cdots,\\,x\_{i\_k} - x\_{i\_{k-1}}\\} $$ What is the technique? We replace the last item $1-x\_{i\_n}$ with $x\_k - x\_{i\_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'\<w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x\_{n^2+1} = 1$.
> 2 votes

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