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

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

Consider this (extreme) case:

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

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

Thanks

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

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

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

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

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

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

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

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

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

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

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


Does a reduction from sorting imply an $\Omega(n \log n)$ time bound? I have come across a proof where a certain function ("compute a straight skeleton") is shown to take $\Omega(n \log n)$ time by reducing the problem of sorting to it. The overhead for the reduction itself is linear, thus negligible.

Now my question is: is this a valid argument?

The original proof appears in: Huber - Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice, page 19, last paragraph.

In summary:

Given a list of $n$ natural numbers, the author constructs a "Polygon with holes" $P$ of structural size $O(n)$ in linear time. The algorithm then computes a straight skeleton $S(P)$, which can be traversed to enumerate the original numbers in sorted order (with constant overhead per number). Thus, the problem of sorting is reduced to computing $S(P)$. The author claims that this implies computing $S(P)$ is in $\Omega(n \log n)$ due to the bound for sorting.

It is well know that comparison-based sorting algorithms have $\Omega(n \log n)$ worst-case bounds. However, there are $O(n)$ sorting algorithms such as radix sort or bucket sort which aren't based on comparisons and for which this restriction doesn't apply. As far as I can tell, these are all restricted to certain domains, such as fixed-length integers or strings.

I assume generalizing these algorithms to unrestricted domains would reveal hidden costs. If we consider arbitrary integers, some operations which are assumed to be constant cost would actually be logarithmic in the size of the integer. I don't know, however, if this necessarily has to be the case for all possible sorting algorithms.

I think the author's construction could be used for sorting real numbers (possibly requiring a variable-length encoding), if this strengthens the requirement on the sorting enough to rule out any $O(n)$ (or $o(n \log n)$) sorting algorithms.

Are there any information theoretic arguments showing that, for fully general inputs and all operations strictly accounted for, at least $\Omega(n \log n)$ basic units of work (whether they be comparison or something else) are always needed? If not, does that mean the argument of "by reduction from sorting" doesn't strictly prove a lower bound stronger than $\Omega(n)$?

It's not a valid argument.   What it does prove is that any comparison-based algorithm for Problem X must use at least $\Omega(n \log n)$ comparisons.  (There is a known algorithm for integer sorting whose running time is $O(n \sqrt{\log \log n})$, in some models of computation, but it is not a purely comparison-based algorithm; see here.)


How this proof of fractional knapsack works? I don't understand a step in my book proving the fractional knapsack problem:

Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by greedy, where $0\le x_i\le 1$ is the fraction packed into the knapsack.
Assume $j$ is the first index s.t. $x_j<1$. Let $Y=\langle y_1,\dots, y_n\rangle$ be any solution not $X$.
Consider $$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$
So $\displaystyle\sum_{i=1}^n v_i(x_i-y_i)=\sum\color{blue}v_i\dfrac{w_i}{\color{blue}w_i}(x_i-y_i)\ge\color{blue}{\dfrac{v_j}{w_j}}\sum w_i(x_i-y_i)\ge0.$

I can understand the blue part I highlighted, but can anyone help me understand the (????) part? Why it must hold?

The following condition is implicitly included in the question.

$$\dfrac{v_1}{w_1}, \dfrac{v_2}{w_2}, \cdots, \dfrac{v_n}{w_n} \text{ is in the descending order.}$$

Let $W$ be the total weight to be filled. The greedy algorithm for fractional knapsack problem is the following procedure.

Let $k$ loop through $1, 2, ..., n$ in that order.

Set $$x_k = \dfrac{W- \sum_{1\le i\lt k} x_i}{w_i}$$
If $x_k<1$, set $x_l=0$ for all $l>k$. Break the loop.

$$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$

There are three cases for $i$.

The case when i < j, i.e., $\dfrac{v_i}{w_i}\ge\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, $x_i=1$, i.e., $x_i-y_i\ge0$.
The case when i = j. Both sides are 0.
The case when i > j, i.e., $\dfrac{v_i}{w_i}\le\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, according to the definition of the greedy algorithm, $x_i=0$. That means $x_i-y_i\le0$.


Example for an undecidable language L such that L is reducible to its complement and vice versa I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$,
but I am not able to find a concrete language and reduction.
Is there anything like this?

Let $K$ be some undecidable problem, and define
$$
L = \{0x : x \in K \} \cup \{1y : y \notin K \}.
$$
(I'm assuming the alphabet is $\{0,1\}$.)
Then
$$
\overline{L} = \{\epsilon\} \cup \{0x : x \notin K \} \cup \{1y : y \in K \}.
$$
I'll let you take it from here.


Using oracle machine to speed up tree solution search Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for simplicity let's assume we do not apply any cuts).

Let $M$ be an oracle machine able to solve a problem $P^\prime$ sub-problem of $P$ of size $k < n$ in time $O(1)$

Is there a known approach of applying $M$ during searching for solution of $P$ in order to find it in time $O(2^{n-k})$? If speed-up of factor $O(2^k)$ is not possible, what is the best known achievable result for such problem? Are oracle machines limited to problem size $k$ useful at all to solve problems of size $n > k$?

Possible application of such approach could be solving NP-Complete problems using a quantum computer that is limited to $k$ cubits as oracle machine. Of course it wouldn't solve sub-problem in time of $O(1)$ but it is just for theoretical simplification.

This question was inspired by branch and price algorithm for integer programming, but instead of generating columns, at each node an technically advanced problem solving machine could be applied as an oracle.

Here is an algorithm that will work in some cases: guess the first $n-k$ bits of the solution; fix them; and then solve the sub-problem where you ask what the remaining $k$ bits are.  In other words, iterate over all $2^{n-k}$ possibilities for the first $n-k$ bits, and for each such choice, use your oracle to find the remaining $k$ bits.

This works assuming fixing some bits of the problem leads to a sub-problem of the sort that can be solved by your oracle.

(I'm also assuming you can verify whether a candidate solution is correct in $O(1)$ time, you can find a correct solution in $O(2^{n-k})$ steps.  This seems to be required to achieve your $O(2^n)$ running time for tree search.  If the problem is in NP, then there's a way to verify in polynomial time, so instead of $O(2^{n-k})$ you have $O(2^{n-k} \cdot \text{poly}(n))$.)


Space complexity of Chomsky Normal Form I'm trying to find sup of $\|\mathbb{G}\|$ where $\mathbb{G}$ is CFG in Chomsky Normal Form. So far i have done some work, but I'm really not sure in my proof. Let $G = \langle Q, N, S, R\rangle$ and
$$\alpha \rightarrow \beta \in R,\ |\beta| = n$$
$$\|\alpha\| \le \sum_{i=0}^{\log_{2}n}2^{n}\,.$$
I made this conclusion by observing the binary tree I get when I try substituting the right side of the rule with $$\beta =b_{1}b_{2}...b_{n}$$
$$\beta \rightarrow A_{1}A_{2},A_{1}\rightarrow B_{1}B_{2}, A_{2}\rightarrow B_{3}B_{4}$$ and so on until
$$Q_{1} \rightarrow b_{1}b_{2}, ...,Q_{[\frac{n}{2}]}\rightarrow b_{n-1}b_{n}$$

The result is binary tree with height $\log_{2}n$ which on each level has $2^{i}, i = {0,1,...,\log_{2}n}$ nodes.
Finally I claim that $$\|\mathbb{G}\| \le |N| + |N|\sum_{i=0}^{|N|-1}(\|\alpha\|),\ \exists (A \rightarrow \alpha) \in R\,.$$

It is well-known, and stated in Wikipedia (which gives a reference: Lange and Leiß), that there is an algorithm transforming an arbitrary context-free grammar $G$ into a grammar in Chomsky normal form of size $O(|G|^2)$.

The following grammar might be an example showing that the quadratic blow-up is necessary:
$$
\begin{align*}
&S \to A_1 \ldots A_m \\
&A_1 \to A_2 \mid \sigma_1 \\
&A_2 \to A_3 \mid \sigma_2 \\
&\cdots \\
&A_{m-1} \to A_m \mid \sigma_{m-1} \\
&A_m \to \sigma_m
\end{align*}
$$
This grammar has size $\Theta(m)$, and it seems that every grammar in Chomsky normal form for this language must have size $\Omega(m^2)$.


Solving a variant of interval scheduling problem I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset. And all the jobs in this subset are compatible

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    12       14

My required job set J is {2,4} since  all the jobs are incompatible with at least one job of the job set J. And all the jobs in the job set J are compatible. I tried using earliest deadline first and schedule but it doesn't work. Any suggestions?

Am I going the right way?

It seems that you are looking for the minimum maximal independent set of an interval graph. A minimum maximal independent set in a graph is the same as a minimum weight independent dominating set, with all vertices weights equal to 1. Since interval graphs are a special case of chordal graphs, Martin Farber's paper Independent domination in chordal graphs (Operational Research Letters, 1(4):134–138, 1982; ACM Digital Library) contains the algorithm you are looking for.


What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques? Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia):

BronKerbosch1(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

I have read that the time complexity of some modified versions of this algorithm is $O(3^{n/3})$, but I can't seem to find the running time complexity of the simple version anywhere.

The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is
$$
\sum_{k=0}^n n(n-1)\cdots(n-k+1) = \sum_{k=0}^n \frac{n!}{(n-k)!} = n! \sum_{k=0}^n \frac{1}{k!} \approx e \cdot n!.
$$
When the maximum clique has size $k$, the number of recursive calls is at most
$$
1 + n + n(n-1) + \cdots + n(n-1)\cdots(n-k+1) \leq 2n^k.
$$
Conversely, if you run the algorithm on a complete $k$-partite graph, then the number of recursive calls will be $\Omega(n^k)$.


Set Basis Problem Variant reference for NP-Completeness? Given: Collection $C$ of Subsets of a finite set $S$, positive integer $K <=|C|$

Problem Statement: Is there a collection $B$ of subsets of $S$ with $|B| = K$ such that for each subset $c$ in $C$, there is a sub-collection in $B$ whose union is $c$ ?

This Set Basis Problem is NP-Complete.

If we enforce an additional constraint that $B$ is a subset of $C$, is the problem still NP Complete?

My assumption is yes, but I could not find any reference to this problem. Can anyone please point out to one?

The problem is in fact solvable in polynomial time.

Let
$$C_0=\Bigl\{c\in C:c\supsetneq\bigcup_{\substack{c'\in C\\c'\subsetneq c}}c'\Bigr\}.$$

On the one hand, if $B\subseteq C$ has the property in the question, then $C_0\subseteq B$: since $c\in C_0$ cannot be written as the union of its proper subsets from $C$, a fortiori it cannot be written as a union of its proper subsets in $B$, hence the only possibility is $c\in B$.

On the other hand, $B=C_0$ does have the required property. We prove by induction on $|c|$ that any $c\in C$ is a union of a subcollection of $C_0$: if $c\in C_0$, this holds trivially; otherwise $c$ is the union of its proper subsets in $C$, which in turn can be written as unions of subcollections of $C_0$ by the induction hypothesis.

Thus, the problem is equivalent to $|C_0|\le K$, which can be checked in polynomial time.


Give a computation of the expression to normal form (Lambda calculus) Past exam question:

What my understanding of B-reduction is : Find all occurrences of the parameter in the output, and replace them with the input and that is what it reduces to

(λ param . output)input => output [param := input] => result

Example:

(λx.xy)z

= (xy)[x:=z]

= (zy)

= zy

But I do not know how to use B-reduction on the expression above. What is the input, output and the parameter.

Usually, a series of applications $f\,x_1\,x_2 \dots$ means $\big(\big((f\,x_1)\,x_2\big)\,\ldots\big)$. We say that application is left associative.

According to this convention, there is an extra set of parentheses that is implied in the expression you write. Here I've made it explicit:
$$\big((\lambda f.\lambda g.\lambda x. f \,(g\,x))\,(\lambda u.u)\big)\,(\lambda v.v)$$

The expression $(\lambda f.\lambda g.\lambda x. f \,(g\,x))$ is a function and it is applied on input $(\lambda u.u)$. Reducing this will result to a function of the form $(\lambda g. \lambda x. \langle\text{body}\rangle)$, which in turn gets applied to $(\lambda v.v)$.


Algorithms for graph generation using given properties There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc).

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e., every node in these graphs has the same number of neighbors) with different clustering coefficients and average shortest path lengths. More generally, by fixing a degree distribution, I want to generate graphs with different clustering coefficients and average shortest path lengths.

I wonder what are the well-known algorithms for doing this (or in fact, is there any?), and what are the recommended software for the same purpose?

There are no general algorithms for your problem but what one usually does (for graphs of small orders) is

Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..)
Use an external program to extract only the graphs you need with respect to some additional  properties that you want.

You can do both 1 and 2 in sage! For example consider that you want to generate all connected 5-regular graphs of order 20 that have average distance 10 (Wiener index??) and some clustering coefficient. You do the following

for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
    if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
       print G.adjacency_matrix()

Let me know if you need some more specific answers related to sage.


Proving a language is not decideable using a reduction from Busy Beaver? I was given this function:
$F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural number). I was asked to prove that this function is uncomputable using a reduction from the Busy Beaver. I'm still new to reductions and after sitting on this problem for a while I've gotten nowhere. I'd appreciate any help/guidance.

Hint: Why is the busy beaver function difficult (rather, impossible) to compute? Consider the following algorithm: given $n$, run all $n$-state Turing machines, and whenever one of them halts, update your estimate on the maximum number of steps. Eventually you will have found $BB(n)$, but you wouldn't know, since some of your machines are still running. Will any of them terminate, or have you discovered $BB(n)$? The function $F(n)$ given to you in the question could help in that respect.


How do I show that an equivalence class of a language containing an empty string is infinite The question is as follows:

  Let $L$ be a language (not necessarily regular) over an alphabet. Show
  that if the equivalence class containing the empty string $[ \epsilon ]$
  is not $\{ \epsilon \}$, then it is infinite.

How do I go about answering this? Would I need to use Myhill-Nerode theorem? From what I've read there's a corollary from the theorem that if a language defines an infinite set of equivalence classes, it is not regular. I'm not sure if that helps answer my question though.

Let $A$ be the alphabet. I suppose that the equivalence you are referring to is the equivalence $\sim$ defined on $A^*$ by $u \sim v$ if and only if, for all $x \in A^*$,
$$
  ux \in L \Leftrightarrow vx \in L
$$
Now suppose there is a word $u \in A^+$ such that $u \sim \varepsilon$. Then by definition, $x \in L$ if and only if $ux \in L$. It follows by induction on $n$, that for all $n > 0$, $x \in L$ if and only if $u^nx \in L$ and thus $[\varepsilon]$ contains $u^*$. If the alphabet is nonempty, it follows that $[\varepsilon]$ is infinite.


How are Signed integers different from unsigned integers once compiled How are Signed integers different from unsigned integers once compiled?

I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit integers when in binary eg 10000001 if this is a signed integer it would be equal to -127 but if it is unsigned it would be equal to 129. So my question is how can you tell the difference when presented with just 8 binary bits.

And also how are signed integers different from a compilers perspective, and how can a CPU tell the difference while performing arithmetic on them

There is no way to tell if 8 bits in memory are a signed integer, an unsigned integer, a character, or part of a bigger data. The knowledge is put in the instructions.

As stated by David Richerby, two's complement makes signedness transparent in most operations (addition, substraction, multiplication), but some are different: the bitwise shift may preserve or ignore the sign bit. Some processors implement arithmetic shift to preserve sign bit (acting like a division, even on negative numbers) and logic shift (which is suitable for unsigned integers). When you compile your source code, the compiler knows the type of your data, and generate the program with the instruction that fit with your use-case.

Please note that some processors implement only one type of bit shifts. In such case, to keep the same behavior, the compiler will add some extra instructions to do the same work (based on the compiler's knowledge of the data types). Some languages may avoid such extra work on the compiler by stating something like

  The result of E1 >> E2 is E1 right-shifted E2 bit positions. [...] If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Source : C language : ISO/IEC 9899:TC2 section 6.5.7 (Bitwise shift operators)

Type and signedness aren't part of the data itself. The knowledge was already used to generate the instructions that use the data according to their actual type. For dynamic type evaluation (at runtime, see dynamic programming language), some kind of tags (many implementations are possible) are added in the data structures to identify their type, and use the appropriate code to handle it.


Help with question involving k-regular graphs In my last test, our teacher gave us this question:

  In an conference with 90 participants, the staff wants to divide all
  participants in 6 groups of 15 participants each. Each participant of
  each group must have at least one article with exactly 7 other
  participants of the same group. Prove using Graph Theory that this
  division is impossible.

I spent a lot of time thinking about, but couldn't find an definitive answer. I think that this involve bipartite matching somehow, but I have no idea on how to proceed with the proof. I thought that maybe creating a k-regular graph would prove that this don't have a matching, but I couldn't come with the graph representing the problem.

Can I get some help with this?

There is no 7-regular graph on 15 vertices, since $7\times 15$ is odd.


Loop-Invariant for a program fragment Q) Consider the following program fragment:

var x,y:integer;
x:=1; y:=0;
while y < x do
begin
  x:=2∗x;
  y:=y+1;
end;

For the above fragment , which of the following is a loop-invariant ?

A) x=y+1
B) x=(y+1)2
C) x=(y+1)2y
D) x=2y
E) None of the above, since the loop does not terminate

Since, Loop-Invariant is something which is true before and after each iteration of a loop. So, according to the definition, I am getting answer as (D) but I have a doubt whether termination of that loop is necessary or not for the given code. One of the properties of algorithm says :- algorithm should always terminate after finite no. of steps. So, if the question is about Pseudocode then I will definitely mark answer as (D) but since it is program fragment, So I am confused between options (D) and (E).
So, My Doubt is definition of loop-invariant is also true for the loop in the code which is written in any language like C,C++ etc.
Please help.

The question asks for a loop invariant. This has nothing to do with termination. (D) does look reasonable but you may want to check with the usual tools such as Hoare logic, that (D) holds before the loop and is re-established by the loop body if the guard holds.

PS Your idea of an algorithm may need some work.


Where to find published research papers? Coming from the POV of someone who is thinking about pursuing a PhD in Computer science.

I am having trouble deciding what I would focus my research on when I go for my PhD. See also this question on academia.SE.

So I am thinking that reading/keeping current on what research is being done and what research papers are being released is a good source of....inspiration?  Plus good knowledge to know.

Is there central place/database of/good starting place to see recently published CS research papers, or are they all hidden deep within the websites of the University they were written at?

As AJed mentioned, ACM digital library and IEEE xplorer would be near the top of list.

Additionally Goggling with advanced search for the name of the reference with the option to search for PDF or PS increases the change of a hit.

Sometimes limiting the search to cs.xyz or xyz.edu increases the quality of results.

If you are just starting out on a subject, try adding the word survey as a search term because many researchers write survey papers so that someone new to the subject has an informed person guiding the way.

I also like to hit CitSeerX, WorldCat and Google Scholar

Don't forget to look at the patents in Google Scholar, I don't usually but every now and then companies have to give out something good they may not publish anywhere else.

If you don't attend school, you can see if a school provides access to their library for outside third parties. I found out that I can do this for Princeton University for $300 a year.

Added 3/2/2013

Microsoft Academic Search

This can also visualize publication trends in computer

Added 1/1/20016

arxiv.org - Open access to 1,106,143 e-prints in Physics, Mathematics, Computer Science, Quantitative Biology, Quantitative Finance and Statistics.

semanticscholar.org

This has a nice feature that list survey papers which is useful when you are starting on something new.


Measuring Fitness in Genetic Programming Functionology I recently begun working on a genetic algorithm to solve for patterns in data. More specifically, it solves for functions given a sample of ins and outs. So a possible solution would be X+2 = Y. The problem is scoring.

I began by trying to use the distance between the result and the expected result as a way of measuring fitness. The problem is the difference is not a reflection of the distance from a correct solution.

So the question: Given a random set of values, is it possible to measure how many operations(+,-,/,*) it would take to get to an certain number without using brute force. And of course, if so how?

EDIT The random set will always contain {0,1,2}.

I don't know how to solve your original problem, but I can describe how to solve a simpler version of it.  Given numbers $a_1,\dots,a_n$ and a target $y$, if you only allow operations +,-, you can count how many operations it will take to reach $y$.

In particular, this amounts to asking for integers $x_1,\dots,x_n$ such that

$$a_1 x_1 + \dots + a_n x_n = y,$$

while minimizing $|x_1| + \dots + |x_n|$.

This can be solved using integer linear programming.  Introduce variables $w_1,\dots,w_n$ and the constraints $w_i \ge 0$ and $-w_i \le x_i \le w_i$ as well as

$$a_1 x_1 + \dots + a_n x_n = y,$$

and then minimize the objective function $w_1 + \dots + w_n$.

While integer linear programming is NP-hard in the worst case, when the numbers aren't too large, I expect that this will yield an efficient solution.

Introducing the *,/ operators makes your problem much harder.

To deal with your full problem, you might consider using the A* algorithm.  For instance, you might build a heuristic function that estimates the distance to the target by using integer linear programming to get an overestimate of the distance to the target (you know that the distance using +,-,*,/ operators will be at most the distance using +,- operators, and the latter you can compute efficiently using ILP).  I don't know for sure whether this will work well or not, but it's something you could try.


Choosing nonzero entries from an array so no pair in same row or column Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$.  We want to find $n$ entries of the array $(x_1,y_1), \dots, (x_n,y_n)$ such that

each $A[x_i,y_i]>0$ and
no pair $(x_i,y_i),(x_j,y_j)$ are in the same row or column (i.e., $i\neq j$ implies that $x_i\neq x_j$ or $y_i\neq y_j$ or both).

How can we prove that such a set of entries always exists?

Here is an example solution with a $3\times3$ table.

The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.

If you don't want to assume this theorem, you can use Hall's theorem directly. Given your table $A$, define a bipartite graph by having $n$ row-vertices, $n$ column-vertices, and connecting row $i$ and column $j$ if the $(i,j)$th entry is non-zero. Your goal is to find a perfect matching in the graph.

According to Hall's theorem, the graph contains a perfect matching if for all subsets $S$ of row vertices, the number of neighbors of $S$ is at least $|S|$. That is, given a set $S$ of rows, we need to show that the set
$$T = \{ j : A_{ij} \neq 0 \text{ for some $i \in S$}\}$$
contains at least $|S|$ columns. Indeed, the sum of the entries in the rows in $S$ is exactly $|S|$, and the sum of the entries in the columns in $T$ is exactly $|T|$. Therefore the sum of entries in $S \times T$ is at most $|T|$. However, by definition this sum must equal $|S|$ (since all other entries in the rows in $S$ are zero), and so $|S| \leq |T|$, which is what we wanted.

This argument shows that you can use standard algorithms for finding maximum matchings in bipartite graphs to actually find your $n$ entries.

We are now at an excellent position to prove the Birkhoff–von Neumann theorem. The proof is by induction on the number of non-zero entries. The argument above shows that there are at least $n$ non-zero entries, and in that case it's not hard to see that the matrix must be a permutation matrix, completing the base case.

Now consider an arbitrary doubly stochastic $A$ with more than $n$ non-zero entries, and find a matching $(i,\pi(i))$ in $A$. This matching corresponds to sum permutation matrix $P$. Define $\alpha = \min_i A(i,\pi(i)) > 0$. The matrix $B = \frac{A - \alpha P}{1 - \alpha}$ is also doubly stochastic (since subtracting $\alpha P$ removes exactly $\alpha$ from each row and column), with at least one more zero entry. By induction, $B$ is a convex combination $\sum_t \beta_t P_t$ of permutation matrices. Hence so is $A$: $$A = \alpha P + (1-\alpha) \sum_t \beta_t P_t.$$

The Birkhoff–von Neumann theorem can be stated in many different ways. It states that the set of doubly stochastic matrices is the convex hull of the permutation matrices. It also states (with some more work) that the vertices in the polytope of doubly stochastic matrices are the permutation matrices.


Reducing the halting problem for a language with strings that include at least one 1 $L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence

$L_2$ = Turing machines that decide $L_1$

I think the first language is decideable, as the input string is of finite length and you can check every character in the string.

However, my intuition says the second language is undecideable. This would be like checking if a TM is equal to a TM that decides $L_1$.

Am I correct? And if so, how should I proceed to reduce the halting problem to $L_2$?

Original Question:

$L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$

$L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$

prove that $L_2$ is undecidable.

Answer:

For first part you are correct.
First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$.

Now coming to second one $L_2$. This language is as you said undecidable. And you can prove it by reducing halting problem which is known to be undecidable to this problem.

For doing this you have to create an instance of problem in question such that solving it gives us solution of halting problem.

Now formally we can define turing machine $\tau\langle M, w\rangle =M'$. Where $M'$ is a turing machine which started on input $x$ checks if $x$ is of form $1^+$. If no then it rejct it immediately. Otherwise it erases $x$ from it's tape then copies $M$ and $w$ on its tape and simulates $M$ on $w$. If $M$ stops then it accepts $x$(which it have erased).

Proof of validity of reduction:

$M$ halts on $w$ $\implies$ $M'$ accepts  all and only strings of form $1^+$.

$M$ does not halt on $w$ $\implies$ $M'$ accepts empty set. In particular it does not accept strings of form $1^+$.

So now if there would be any turing machine that decides $L_2$ then we can use it to find whether $M'\in L_2$ or not? If it outputs yes then we infer that original $M$ halts on $w$. Otherwise we infer that $M$ does not halt on $w$.

And because we know that halting problem is undecidable we conclude that no such turing machine exists which can decide $L_2$ and consequently $L_2$ is undecidable.

Hence proved.


A microkernel fully hardcoded in hardware? Does there exist a (micro-)kernel of an operating system that is fully implemented in hardware? That is, a kernel that is not stored in RAM, and loaded into CPU registers after an interrupt or system call, but is instead a fully hardcoded part of the CPU itself, so that a system call/interrupt never leads to a context switch?

The key search terms here are FPGA and ASIC, since at this point the OS is no longer running on instructions executed by a CPU in the conventional sense.

Here is a relevant result I found with a quick Google search on microkernel fpga and os kernel fpga:

Susanna Nordström et al. Application Specific Real-Time Microkernel in Hardware.

  In the RTU, the scheduling, inter process communication, interrupt management, resource management, synchronization and time management control are implemented in hardware (using VHDL).

This paper goes a step further and describes an OS-like environment for FPGA programs themselves: Kermin Fleming et al. The LEAP FPGA Operating System.

  Like a software operating environment, LEAP provides both basic device abstractions for FPGAs and a collection of standard I/O and memory management services.


P-Completeness and Reducibility I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance.

The problem I'm stuck on is proving that the empty language and $\{0, 1\}^*$ are the only languages in P that are not complete for P with respect to polynomial-time reductions (problem 34.3-6 in CLRS 3rd edition). The first part of the problem seems fairly straightforward enough (proving the empty language criteria). However, I'm not sure where to even begin when I have to prove the criteria for $\{0, 1\}^*$. I'm NOT looking for the answer, however I would appreciate some guidance on how I can begin to think about this problem.

Hint. The definition of reduction from $X$ to $Y$ requires that "yes" instances of $X$ be mapped to "yes" instances of $Y$ and "no" instances to "no" instances.


Recurrence Relation(with Square root) I came across a very peculiar recurrence relation :

  $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)}  $

with initial values $T(0) = T(1) = 1$

Any helps on how to find it

Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The  characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $(-1)^n,2^n$. After substituting the initial conditions you get $f(n)=\frac{1}{3}(-1)^n+\frac{2}{3}2^n$.


Showing a language is in co-NPC I need to prove that this language is in co-NPC:
$\{ \langle M,x,1^n \rangle \mid M $ is a TM and for all $c \in \Sigma^*$ , $M$ accepts in $ $$n$ steps when given $(x,c)$ as input $\}$.

I tried to do so by showing that the complement is in NPC, that is $\{ \langle M,x,1^n \rangle \mid M $ is a TM and there exists  $c \in \Sigma^*$ , s.t $M$ doesn't accepts in $n$ steps when given $(x,c)$ as input $\}$.

I can prove that it's in NP by giving a polynomial non-deterministic algorithm, but I get stuck in the reduction part and don't know from which language in NPC to do a polynomial reduction and how. Does anybody know how do deal with such reduction?

Hint:
While it's certainly possible to choose a concrete language and show a reduction from it, in this case it's actually easier to show a reduction from every language in NP.

As a starting point, recall that a language $L$ is in NP iff there exists a polynomial-time verifier for it.

Let $L$ be a language in NP, and let $M$ be a polynomial verifier for it, and let $f(n)\in O(n^k)$ be the runtime of the verifier. Observe that for every word $x$ we have that $x\in L$ iff there exists a witness $y$ such that $M$ accepts $(x,y)$ within $f(|x|)$ steps.

This looks a lot like your language, see if you can complete the proof from here.


Bloom Filter for 208 million URLs I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it resulted in too many false positives while reading.

I have a huge web corpus containing web content of billions of URLs. I need to process the web content of URLs satisfying certain criteria: the URL should have appeared in web search results in the past 7 days at least 5 times. This is represented by a list of 208 million URLs. Joining the list directly with the web corpus is not feasible because of volume. So I am considering creation of a bloom filter out of the list and then using the bloom filter to prune out unnecessary URLs from the web corpus.

Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%.  This assumes, among other things, that good hash functions are used.  The formula is:

$(1 - (1 - [1/m])^{kn})^k$

where $m$ is the number of bits in the filter, $k$ is the number of hash functions and $n$ is the number of entries in the filter.

Because items cannot be removed from a typical Bloom filter, if generation of the filter is too expensive, you might consider a counting Bloom filter to allow deletions.

(Although I have not read of it being used and do not know if it would be effective, one might use ORed signatures in each field instead of a set bit, where each signature has half or fewer of the bits set.  A possible match is found when ((entry_signature ^ test_signature) & test_signature) == 0 for each entry selected by a hash function.  If every signature has the same number of set bits, this would be like nesting a Bloom filter with a size equal to the signature size and the number of hash functions equal to the number of set bits.)


Maximizing entropy under constraint How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?

Suppose that $X$ is a random variable over the set $\{1,\ldots,n\}$ satisfying $\Pr[X=1] = a$. Let $Y$ be the indicator of the event $X=1$. Then
$$
\begin{align*}
H(X) &\stackrel{(1)} = H(Y) + H(X|Y) \\ &\stackrel{(2)}=
h(a) + aH(X|Y=1) + (1-a)H(X|Y=0) \\ &\stackrel{(3)}\leq h(a) + (1-a) \log (n-1).
\end{align*}
$$
Here (1) is the chain rule (using $H(X) = H(X,Y)$, since $Y$ is determined by $X$), (2) follows from $\Pr[Y=1]=a$ and the definition of $H(X|Y)$, and (3) follows from $H(X|Y=1) = 0$ (since when $Y=1$ we have $X=1$) and $H(X|Y=0) \leq \log (n-1)$ (since when $Y=0$, the r.v. $X$ only attains the values $2,\ldots,n$).

Furthermore, assuming $a \neq 1$, equality holds only if $X|Y=0$ is uniform, that is, if $\Pr[X=i|Y=0] = 1/(n-1)$ for $2 \leq i \leq n$, or in other words, if $\Pr[X=i] = (1-a)/(n-1)$ for $2 \leq i \leq n$.


Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology? Is the following true or false? Why?

Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.

The statement is: If a problem $P$ is $\mathbf{NP}$-hard, then there is a reduction from $\text{FALSIFIABLE}$ to $P$. ($\text{FALSIFIABLE}$ being the set of formulas for which there is an assignment which makes the formula false; this is trivially equal to the complement of $\text{TAUT}$.)

This statement is correct.

Why? Simply because $\text{FALSIFIABLE}$ is $\mathbf{NP}$-complete. You can prove this exactly the same way $\text{SAT}$ is proven to be $\mathbf{NP}$-complete, only inverting the truth values "true" and "false" (i.e., instead of searching for an assignment which makes the formula true, you search for an assignment which makes the formula false). This is not at all surprising; it is basically the duality principle of Boolean algebra.


Do all the cells in a recurrent neural network share learned parameters? Most descriptions of modern RNNs present a "folded" characterisation, that is to say, a single cell with a loop back to itself transmitting the hidden state from one step to the next. However, in implementations the RNN is computed "unfolded", so a new cell is created for every step of the sequence up to some maximum sequence length, and the state is passed from one cell to the next.

My question is: are the learned parameters shared between all the cells in the unfolded sequence? E.g. in the case of a stack of LSTMs, does each LSTM have its own set of forget, input-gate, candidate and output parameters, or does the whole stack share and update a common set?

Indeed, the copies of a cell in an unfolded version share their learning parameters.

Why is it done this way? If the sequence processed by the LSTM is always the same lenght, we could conceivably get a better result with different parameters, but there are two key caveats:

Shared parameters are faster to learn
We want to be able to process cases when the lenght of the sequence processed is not fixed!


What is the difference between Decision Support System and Machine Learning? I have started reading about Decision Support Systems which according to wikipedia is "a computer-based information system that supports business or organizational decision-making activities".

I have seen papers suggesting intelligent decision support systems, does that means a DSS necessarily utilizes Machine Learning ? How is a DSS different from Machine Learning or vice versa.

Decision Support Systems (DSSs) are devoted to the management of large volumes of data. Its main goal is to simulate decision-making procedures that actually simulate (or show) some intelligence. This is why the wikipedia see DSSs well related to business processes ---as they are, indeed.

Machine Learning (ML) is used to infer or derive new knowledge from existing one usually expressed in the form of static data and optionally, as dynamic data or rules. The new knowledge is also expressed in one or both forms.

In general, DSSs and ML are different in their scope. ML is not expected to serve to take decisions though some mechanisms produce new data in such a form that a recommendation becomes apparent (e.g., when using clustering algorithms). Instead, ML can serve in the back for DSSs which I see as a more general system: it is not only in charge of taking decisions but also of managing data, the human-machine interaction (e.g., implementing Mixed-Initiative procedures), and a number of additional modules such as an explanatory module which provides additional evidence of the decisions taken.

None of these processes (necessarily) exist in ML: no need to manage data in any particular way (and indeed data is usually assumed to come either in a declarative way, e.g., PROLOG, or in a large Database conveniently designed, e.g., as in RapidMiner); no particular interface is usually required since the interesting product is the new knowledge which is writen usually in the same format than the input; no need to produce explanations of the learnt knowledge (though, admittedly, some mechanisms produce a trace that can be revisited to verify the learnt knowledge).

Other than these rather theoretical (but not really) considerations, let me emphasize that many (if not all) DSSs usually consist of Expert Systems (even nowadays) while ESs are not a form of ML.

Hope this helps,


Generate a unique number for a set of sequences of letters A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I need to search if the $w$ exists in the database of words.

The framework of the database and the application is on the web and this job is part of an online game, So may be hundreds of requests come to website in a second so I need to do it as fast as possible. To do so as fast as possible, I want generate a unique number for every word in the database. For every string query, I generate its number using the algorithm used to generate numbers for the database, then check if the new number exists in the database or not using binary search tree.

Here is an algorithm that works perfectly to generate a unique number for a sequence:

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i \in \mathbb{Z^{+}}$ (it is easy to map every letter to a number) the unique number is

$$
\prod_{i=1}^{n}{p_i^{a_i}}
$$

where $p_i$ is the $i$-th prime number. But the problem is, the produced numbers are too large to be stored in current programming language variables.

My Solution

First I set the following mapping:

$MAP: [a=>2, b=>3, c=>5, \cdots, z=>101]$

So I set the $i$-th prime number to the $i$-th letter. (Actually it is not necessary to regard this order, more frequent characters can take smaller prime number)

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i$s are letters this is my formula:

$$
\prod_{i=1}^{n}{MAP(a_i)^i}
$$

For valid words, this formula generally, produces smaller numbers than the first one. I just wanted to know :

if this formula always generates a unique number? I couldn't generate two words with the same numbers, but clearly it is not enough to convince other people
Is there any solution that search for words in $O(\log n)$ (like binary search tree)?

thanks.

Use a hash function. Since you have less than $2^{16}$ words, if you use a hash of 32 bits then you are likely to not have any collisions. If you do get collisions, you can try varying the key (hashes usually use some magic numbers, which in some cases are known as keys), or you can just use a longer hash.

Another possibility is to store the dictionary as a decision tree. The decision tree contains a node for each prefix of a word in your dictionary, and as you read a new word, you travel along the decision tree until you hit a leaf (the word is in the dictionary) or you get stuck (the word is not in the dictionary). But that amounts to storing the entire dictionary, which perhaps you are trying to avoid for some reason.

If for some reason you don't like these solutions, I have two other solutions to offer, though I don't recommend using them. The first one is to encode your words in base 26. This will be much more efficient than your prime-based code, though still somewhat unwieldy (the result could be up to 71 bits long). A more economic but more complicated solution is to use a Huffman code, either first order (the same code for each letter), second order (one code for the first letter, and henceforth the code depends on the previous letter), or even higher order.


Why is the base used to compute hashes in Rabin–Karp always primes? The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is
$$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$
where $b$ is prime (all computations are module $2^w$, where $w$ is the width of a machine word). Why is it important for $b$ to be prime?

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring.

The efficiency of the algorithm depends on the ability to compute $h(S[r+1\ldots s+1])$ efficiently from $h(S[r\ldots s])$. This is called a "rolling hash". Note that any efficient rolling hash function will do, and it's still Rabin-Karp. The question that you're asking about is one particular choice of hash function, where you use:

$$h(S[r\ldots s]) = \sum_{i=r}^s S[i]\, p^{s-i} \bmod q$$

where $p$ is a prime number with roughly the same order of magnitude as the size of the character set, and $q$ is another prime number which defines the cardinality of the range of the hash function, typically of the same order of magnitude as a machine word divided by the character set size. If I'm reading it correctly, you're asking why $q$ has to be prime.

In fact, this is a more general question. In a lot of the old (and current) literature on hashing, the advice is that the hash function should be taken modulo a prime number (e.g. hash tables should have a prime size).

For a hash function to be as useful as possible, its range needs to be relatively uniform, even when its domain is not. Natural language text (say) doesn't have a uniform frequency distribution, but hash values should be.

If $q$ is a prime number, then a lot of other numbers are relatively prime to it, and in particular, the sum (especially if $p$ is also prime!). This makes the frequency distribution of the hash values more uniform, even though the hash function is relatively weak.

It's important to understand that we do this because the hash function is weak. If the hash function were stronger, taking the remainder when divided by a prime would not be necessary; you could, for example, take the remainder when divided by a power of two, which would be a much cheaper bit mask operation. However, it's hard to design strong rolling hash functions which are cheap enough to be done for every input character in the Rabin-Karp algorithm.

Something that's worth pointing out that this "remainder of a prime" technique used to be common in many hashing applications, but this advice is inadvisable on modern hardware. It advice made sense once upon a time, because while final integer division instruction was always expensive, so were the operations that you used to compute your hash function, such as integer multiplication. On modern CPUs, it is much more expensive to do an integer division even than an integer multiplication.

Modern carry-save adder multipliers are fully pipelined, so you can have several such instructions being executed at once. Modern dividers use the SPH or Goldschmidt algorithms, which are multi-cycle and impossible to pipeline. Goldschmidt dividers also tie up the multiplication unit, making the performance hit even greater.

I've had programs where this division instruction was the bottleneck, and the annoying part was that it was hidden inside the standard library.

On a modern CPU, it is worth using a more sophisticated hash function built out of fully pipelineable operations (e.g. multiplies or even table look-ups) and using hash tables which are powers of two, so the modulo operation is a bit mask. Do anything to avoid that division operation.

Just not for Rabin-Karp.


Proof of non-regularity, based on the Kolmogorov complexity In class our professor showed us 3 methods for proving non-regularity:

Myhill–Nerode theorem
Pumping Lemma for regular languages
Proof of non-regularity, based on the Kolmogorov complexity

Now the first two, Myhill-Nerode theorem and Pumping lemma, I understood well and I was also able to do the exercises to the first two methods. But I did not understand the third one. The Definition of the third method is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language.
Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.

Now I do not understand how to use this theorem to prove that a language is not regular, I don't really get the concept. We used the kolmogorov complexity before for determining the length of the shortest computer program of an object. How does one prove non-regularity with this theorem? And what is the thought behind it?
Thanks a lot!

To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.

This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

They give several examples where one can use the statement you mentioned instead of using the pumping lemma. For example, proving non-regularity of $L$ where

$L=\left\{1^p|\text{p is prime}\right\}$.

Given some $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Let us choose $x=1^{p'}$ where $p'$ is the $k$'th prime. Let $y_1$ be the first word in $L_x$. Obviously, $y_1=1^{p-p'}$ where $p$ is the $k+1$ prime. According to the statement you mentioned, $K(y_1)\le c$ ($n=1$), for some constant $c$ depending only on $L$ (see paper).

Since this holds for all $x$, we can bound the Kolmogorov complexity of all elements in $S=\left\{y_1^x| x=1^p \text{ for prime $p$ } \land \text{$y_1^x$ is the first string in $L_x$}\right\}$ by the same constant $c$. However, we saw that $S$ actually consists of differences between consecutive primes, i.e.
$S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ where $p_k$ is the $k$'th prime. Since we know $S$ cannot have bounded Kolmogorov complexity (prime differences get arbitrarily large), this means $L$ cannot be regular.


How would i go about calculating the Big Theta of the following nested loop? for i = 0 ... log(n) - 1
    for j = 2^i + 1 ... 2^(i + 1)
         [code with Big-Theta(1) running time]

Given this piece of code the outer loop runs log(n) times. But I'm confused as to how to try to calculate the running time of the second loop so as to multiply them. Thank you for reading.

Each internal loop does $2^i$ iterations of $\Theta(1)$ so it takes $\Theta(2^i)$.
Therefore the time complexity of the code is the $\Theta(\Sigma_{i=0}^{log(n)} 2^i)=\Theta(n)$.

You could intuitively think of summation here as writing in binary base a number where all its digits are 1, and has the same number of digits as n, it is linear to the size of n.


Finding max value algorithm with subset comparison I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison.

The intuitive algorithm would be comparing them linearly: compare two items, compare the biggest with the next one, repeat. That would give us a total of $N-1$ comparisons.

Since I couldn't come up with anything, I want to know if there is some algorithm to do this more efficiently (making fewer comparisons), taking advantage of subset comparison being allowed.

Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:

If one of the sets is bigger than the other, we say that its sum is larger.
If the two sets have equal size, we say that their sums are equal.

We can represent each comparison as a vector of length $n$: the comparison $\sum_{i \in A} w_i \gtrless \sum_{i \in B} w_i?$ (where $w_i$ are the weights) corresponds to the vector $1_A - 1_B$, i.e., the vector having value $1$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value $0$ elsewhere.

Let $\mathbf{x}_1,\ldots,\mathbf{x}_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m < n-1$), and let $\mathbf{1}$ be the constant $1$ vector. Since $m+1 < n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}_1,\ldots,\mathbf{x}_m,\mathbf{1}$. We can assume that $|v_i| \leq 1$ for all $i$.

Consider the vector $\mathbf{w}_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| < 1/n$. It is not hard to check that $\mathbf{w}_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}_\delta$ and $\mathbf{w}_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.

This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum_i x_i w_i)$.


How to convert NFA with null moves to NFA without null moves? I am converting NFA with $\varepsilon$-moves  to the NFA without  $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have to be repeated from $q_i$. And if the $q_j$ is a final state, then $q_i$ will also be a final state.

But, if $q_j$ does not contain any transition, i.e., there are no edges starting from $q_j$, then what has to be done?

If $q_j$ is a final state, you already said you would make $q_i$ into a final state. If there's no transitions from $q_j$ to another state in the FSM, then you are staying there forever- either as an accepting state or as a trap state. Either way, staying in $q_i$ is the same as staying in $q_j$ if you can't go anywhere from $q_j$.


Enumerating connected subgraphs Is there an efficient algorithm to visit/enumerate all unique connected subgraphs of a labelled graph?

E.g., when the graph is a path, $v_1v_2\dots v_N$, there are $N(N-1)$ unique connected graphs: for any $1\leq i<j\leq N$, the subgraph $v_i\dots v_j$. For graphs with denser edge structure, the number of unique connected subgraphs can be as high as $2^{|V|}$ (for cliques).

Fortunately, graphs I'm interested in have a lot of articulation points, so the total number of unique connected subsets should be polynomial in the size of the input.

For those who are interested, I'm modeling a problem in protein mass-spectrometry. Starting from a protein (chain of amino acids, with occasional long-distance bonds due to disulphide bonds), I'd like to generate a database of all possible sub-species that may result from breaks in peptide and/or disulphide bonds.

As explained in enumerating all connected induced subgraphs (on TCS.SE), there is an algorithm whose running time is polynomial in the number of connected subgraphs.  Therefore, if you know that the number of connected subgraphs is polynomial in the input size, there is an algorithm that is polynomial in the size of the input.  The polynomial might be fairly high degree, so I don't know whether the algorithm will be efficient in practice, but you could try it out and see.

See also https://stackoverflow.com/q/15658245/781723.


What is the importance of c in big O notation? From the definition of Big O, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not able to understand is what is its importance in Big oh notation. Every question explains what is big-Oh and what how it uses useful. But I'm not able to understand what is $c$ actually in big-oh. There might be answer which I'm not able to get it due to its technical jargon.
Can someone explain me this in simple terms?

Let's suppose the constant $c$ wasn't there: let's say that $f(n)=O'(g(n))$ if $f(n)\leq g(n)$ for all large enoun $n$. So, for example, $n=O'(n^2)$ and $\log n = O'(n)$, as you'd expect. But let's look at some functions whose growth rates are closer. First, let $f(n)=n+1$ and $g(n)=n$: well, $f(n)\neq O'(g(n))$ because $n+1 \not\leq n$ for all $n$.  Similarly, $2n\neq O'(n)$. SO, we see that the  constant $c$ is absolutely essential to the definition of $O(-)$: it just doesn't do what we want it to do if we remove it.

$O(-)$ measures the growth rate of functions ignoring constant factors. It gives you notation to say things like "$f$ is linear" or "$f$ is quadratic".  When we say "$f$ is linear", we don't distinguish between, say, $f(n)=n$ or $f(n)=4n$ or $f(n)=2n+12$: we ignore the constants. The constant $c$ in the definition of $O(-)$ allows it to ignore multiplicative constants and additive terms.


if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC? if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC ?

If yes then how can we generate a polynomial time verifier algorithm for the same ?

A polynomial from $3SAT$ to $A$ shows that $A$ is $NP$-hard.

A polynomial reduction from $A$ to $3SAT$ shows that $A$ is in $NP$.

So, the answer is yes.

You can construct a polynomial verification algorithm for $A$ by first reducing $A$ to $3SAT$, and then using the verification algorithm for $3SAT$.


How this expression leads to the given sequence Here given is a sequence from OEIS.

The sequence is triangle of coefficients from fractional iteration of e^x - 1. Few terms are:
1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674

The expression of finding the sequence is also given as:
A(n;x) for n-th row satisfies
 A(n;x) = Sum_{k=0..n-1} Stirling_2(n, k)*A(k;x)*x, A(1;x) = 1.

The tabular  view shows the entries row wise. Stirling_2(n,k) is most probably stirling numbers of the second type

I am not able to get how above expression is resulting in the given sequence.
In summation, k begins from 0, but nothing is mentioned about A(0;x). I assumed it to be 0, but still can't get the above values.
Please explain how the first few terms are resulting from the expression.

Stirling numbers of the second type satisfy
$$ \newcommand{\stirling}[2]{\genfrac\{\}{0pt}{}{#1}{#2}}\stirling{n}{0} = 0, \qquad (n \neq 0)$$
and so there is no need to define $A(0;x)$, and so the formula seems to work. You can also play with the Mathematica code which can be found in the entry corresponding to the sequence. I am puzzled, however, what is meant by "fractional iteration of $e^x-1$".

The recurrence given is for generating functions. Let's rewrite it:
$$
A_1(x) = 1, \qquad A_n(x) = \sum_{k=1}^{n-1} \stirling{n}{k} A_k(x) x.
$$
Using a table for the Stirling numbers, we get
$$
\begin{align*}
A_1(x) &= 1 \\
A_2(x) &= \stirling{2}{1} A_1(x) x = 1 \cdot 1 \cdot x = x \\
A_3(x) &= \stirling{3}{1} A_1(x) x + \stirling{3}{2} A_2(x) x = 1 \cdot 1 \cdot x + 3 \cdot x \cdot x = x + 3x^2 \\
A_4(x) &= \stirling{4}{1} A_1(x) x + \stirling{4}{2} A_2(x) x + \stirling{4}{3} A_3(x) x \\ &= 1 \cdot 1 \cdot x + 7 \cdot x \cdot x + 6 (x + 3x^2) x  = x + 13x^2 + 18x^3
\end{align*}
$$
and so on. The numbers in the table are $a(n,k) = A_n(x)|_{x^k}$ :
$$
\begin{align*}
a(2,1) &= 1, \\
a(3,1) &= 1, \\
a(3,2) &= 3, \\
a(4,1) &= 1, \\
a(4,2) &= 13, \\
a(4,3) &= 18,
\end{align*}
$$

If you prefer an actual recurrence on the coefficients, here is what you get:
$$
\begin{align*}
a(n,l) = \begin{cases} 1 & l = 1, \\ \sum_{k=l}^{n-1} \stirling{n}{k} a(k,l-1) & l > 1. \end{cases}
\end{align*}
$$


What is this data structure/concept where a plot of points defines a partition to a space I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.

Basically it's a plot of points, and the lines are drawn to be equidistant between two points. It forms a perfect partition where the lines around the point form the shape of area that is closest to that point. Does this ring a bell to anyone? I've had a tough time googling descriptions and getting results. And I don't know how else to describe it. Hopefully the picture helps.

What you described is Voronoi diagram.
Here is an excerpt from Wikipedia.

In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose distance to $p_k$ is less than or equal to its distance to any other points. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.


Why is there no regularity condition in case 1 of the master theorem? In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level is greater than that at the bottom levels, in addition to it being greater than work being done at last level. However, in case 1, which is applicable when most of the work is being done at the last level, we assume that it will be greater than all the previous levels. Why is that? Shouldn't there be a regularity condition for case 1 also?

You are asking why the regularity condition is absent in case 1. What you should be asking instead is why the regularity condition is present in case 3. Let's start with the latter question.

Consider the recursion
$$
T(n) = T(n/2) + f(n), \text{ where } f(n)=n^{1 + (\log_2 n \bmod 2)}.
$$
For simplicity I define the function $f$ only for powers of 2, and it is given by $f(2^{2k}) = 2^{2k}$, $f(2^{2k+1}) = 2^{4k+2}$. You can check that $T(n) = \Theta(n^2)$, and so it is not the case that $T(n) = \Theta(f(n))$ (since for $n = 2^k$, $f(n) = n$).

This shows that some regularity condition is indeed necessary in case 3. The proof shows that this particular regularity condition suffices for the conclusion $T(n) = \Theta(f(n))$ to hold.

In case 1, in contrast, the proof works for every function $f(n)$ satisfying the condition $f(n) = O(n^c)$, where $c$ is strictly smaller than the critical exponent. You can try to concoct an example like the one above, but you will necessary fail, since the master theorem states that the condition $f(n) = O(n^c)$ suffices for the conclusion $T(n) = \Theta(n^{c_{crit}})$ to hold.

You can still ask whether there is some deeper reason that the regularity condition is needed in case 3 but not in case 1. I think that the example above is very suggestive: the reason is that in case 3 the answer involves $f(n)$, whereas in case 1 it doesn't. Therefore if $f(n)$ is not well-behaved then it could show up in case 3, but is irrelevant for case 1.


sequential consistency is not composable I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question:

Is sequential consistency compositional? if yes explain why, if no give an example.

Now this is the only two slides that we have that explains why it is not composable.

And i am having trouble understanding why just from that example. I tried searching on the web for a better explanation but i could not find it. If you have a good example that you can describe and explain or if you have a good link or both please do provide it.

Composable means we can check for each object separately and exactly if the property applies to all of them separately then it applies to the whole of them at once.

To show that sequential consistency is not composable we can use an example where the ordering implied by the projections on one object contradicts the ordering implied by the projection on an other object.

Consider a history

A p.enq(x)
B q.enq(y)
A p:void
A q.enq(x)
B q:void
B p.enq(y)
A q:void
A p.deq()
B p:void
B q.deq()
A p:y
B q:x

when simply written down as code. Or visualized:

A: ---*1: p.enq(x)*---*3: q.enq(x)*---*5: p.deq()=y*---
B: ------*2: q.enq(y)*---*4: p.enq(y)*---*6: q.deq()=x*

where the operations start and end at the * and are arbitrarily numbered. Note that this looks like time axes, but that's not how it's necessarily executed. Now when you look at the object p, there must be an order 4-1-5 and for q it's 3-2-6. If the history is sequentially consistent, we also need order 1-3-5 and 2-4-6. But this is not possible, all possible interleavings of 4-1-5 and 3-2-6 contradict either of 1-3-5 or 2-4-6.

(example taken from private slides of a lecture I attended)


Parity vs Parity bit vs Parity sum Assume that $B_b$ denotes the finite set of bitstrings of length $b$, if we are given its subset $A = \{e_i\}, i \in \{0,... n\}$, such that $e_i \in B_b$, what is "the parity sum of As bitstrings" ($parity_A$)?

Is it a single bit $parity_A = parity(concat(parity(e_1), parity(e_2), ..., parity(e_n)))$?

Or is it a bitstring $parity_A = concat(parity(e_1), parity(e_2), ..., parity(e_n))$?

Or is it something else?

I don't think the term has a clear standard accepted meaning, so if you are reading it somewhere, you'll either have to infer from context or hope they defined the term.  But as a general guideline, I would guess your former choice is much more likely than your second choice; I think it's much more likely to be a single bit than a bitstring.

If you are thinking of using that term in your own writing, I encourage you to define that term before using it.


How is adversarial autoencoder better than an ordinary autoencoder? An adversarial autoencoder helps us to impose a prior distribution $p(z)$ on the encoded values of the inputs, or $q(z)$.

On the contrary, an ordinary autoencoder (which we train like an ordinary neural network (comparing output to input using mean squared error) does not give us any control over the encoded distribution.

How does imposing a prior distribution help improve the accuracy of the GAN? I know both entities (discriminator and generator) play a minimax game boosting each other's capability, but how does improving discriminator and generator improve the weights for encoder and decoder to match input image $x$ correctly with the output image?

(image taken from Makhzani et al)

In an adversarial autoencoder, the discriminator network can help generate a more suitable distribution of the latent parameters than would be produced through random selection. If the statistical distribution of the compressed representation is completely unaltered and done in a way as to maximize only the reconstruction accuracy, it is very hard to generate new, high-quality output images because we have to guess the distribution of these latent variables. In a variational autoencoder, this problem is solved by forcing the latent parameters (compressed representation) to conform to a normal (Gaussian) distribution, allowing us to easily generate new images. Using a discriminator to determine a suitable distribution increases the quality of the results produced because the constraints imposed are done in such a way that the reconstruction error can still remain very low and thus the output images are not blurry.


Keeping track of best algorithms Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems?

In the latter there exists a range of classic problems such as MIN st-CUT or MAX FLOW, for which the best algorithms seem to be somewhat hidden in the literature.

"Best algorithm" is a fuzzy term. The algorithm which is best for some particular case can very well be absolutely worst for another, similar problem. Problems differ in details (and not-so-details), in size, in available resources, sometimes an exact solution is essential, other times a rough approximation is good enough. And there are literally thousands of algorithms, with new ones added each day.


Is matrix "adjoint-squaring" faster than general matrix multiplication? The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are related to each other in some known way, it's sometimes possible to get a speedup. For example, computing $U \cdot V$ is quite easy if you're promised that $V = U^{-1}$.

I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication.

Can the special case $U \cdot U^\dagger$ be computed asymptotically more quickly than the general case $U \cdot V$?

It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".

Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:

$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$

$\mathfrak{F}(A - B) = AA^\dagger + BB^\dagger - A B^\dagger - B A^\dagger$

$\mathfrak{F}(A + i B) = AA^\dagger + BB^\dagger - i A B^\dagger + i B A^\dagger$

Thinking in terms of the basis $[x, y, z, t] \rightarrow x AA^\dagger + y BB^\dagger + z A B^\dagger + t B A^\dagger$, those three adjoint-squarings give us $p=[1, 1, 1, 1]$ and $q=[1,1,-1,-1]$ and $r=[1,1,-i,i]$ respectively. From that we want to recover the product $[0,0,1,0] \rightarrow AB^\dagger$. A bit of work will show that the linear combination $\frac{1-i}{4}p - \frac{1+i}{4}q + \frac{i}{2} r$ is exactly what we need.

Therefore we can compute the product $U \cdot V$ via $\mathfrak{F}$ by evaluating:

$$U \cdot V = \frac{1-i}{4} \mathfrak{F}(U + V^\dagger) - \frac{1+i}{4} \mathfrak{F}(U - V^\dagger) + \frac{i}{2} \mathfrak{F}(U + i V^\dagger)$$

Since the most expensive step of this reduction is the adjoint-squaring (it's certainly not the adding, conjugating, transposing, subtracting, or scaling), and the adjoint-squaring function $\mathfrak{F}$ is only used a constant number of times (3 times), general multiplication is no more asymptotically expensive than adjoint-squaring.

(Related: Is matrix squaring asymptotically faster? Nope. With a much simpler proof.)


Question on "Hitting the memory wall, implications of the obvious" I'm reading through a short paper about hitting the memory wall and I'm struggling to understand how exactly said wall will be hit.

The equation for average access time is fairly simple Tavg = p x Tc + (1-p) x Tm. (Tc = time for cache, Tm = time for DRAM mem, P = probability of cache hit)

What I don't understand is how as Tc and Tm diverge, we hit a wall. I recognize that Tc grows exponentially faster than Tm eventually Tm will play little to no role in access time, but it seems like me that average access time would then just continually increase. I can't seem to understand how a wall is hit.

Would anyone with a sharper mind or keener eye than mine help me to understand this concept?

You have it backwards. $t_m$ is what's growing exponentially relative to $t_c$. Or rather, $t_c$ is decreasing exponentially at a rate faster than $t_m$. $t_c$ and $t_m$ are the times the accesses take which gets smaller as the speeds improve. So, as the paper states, eventually memory performance, i.e. $t_m$ comes to dominate.

The "wall" is the point where having a faster processor, i.e. reducing $t_c$, makes essentially no difference to overall performance. The situation is an example of Amdahl's law. You are correct that things would improve as $t_m$ improves but look at the extreme scenario. Choose $t_c=0$, i.e. computation takes no time at all which is to say we have "infinitely fast" processors. Even with these magical processors, our programs would still run at some multiple of the memory bandwidth. In other words, at some point, if you have a slow program, buying a faster processor will not help. Or, put a different way, at some point, the exponential improvement in processor speeds will be meaningless. It will make no actual difference in program speeds.

And by "at some point", I mean a point we seemingly reached five or ten years ago. Modern (and not so modern) high-performance software design is significantly about, in the terms of this paper, reducing $1-p$. Many of the ideas suggested at the end of that paper have been adopted in some form. Multi-level memory hierarchies make even single processors look like non-uniform memory access architectures. Prefetching and careful data layout help increase cache hits, i.e. increase $p$. We're definitely much happier using designs that waste space if they can reduce cache misses. For example, if we have an object that optionally contains another object, we might store this as a dense array of pairs of the objects with a dummy object as the second when it doesn't exist. This is likely to reduce cache misses as compared to chasing pointers. (However, filling cache and/or cache lines with dummy data also can increase cache misses which is why this kind of design needs a lot of care.) Another way to decrease the effective $t_m$ and benefit from the extra computation speed is to store data compressed. When this saga unfolded with respect to disk v. RAM, it was faster to store inverted indexes for full-text databases utilizing compression and decompress them because the time spent decompressing the indexes was more than made up in the time saved in disk traffic. I can easily imagine a near future where RAM stores a compressed representation of, say, a cache line which gets decompressed transparently by the CPU.


When should we construct trees, graphs to analyse an algorithm? In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to put things analysed in them and use those structures to describe the property of the research object and prove some property of the structures to finally give an explanation why it works well...

When should we use trees, graphs to analyse an algorithm? Or equivalently, what property do trees or graphs do well in describing in theory?

Like, in sort algorithms, many algorithms are analysed with a binary tree, in 2SAT algorithms, the core of the problem is decribed as a graph.

Well, for the problems with fixed mode, the structures can be implied easily, like the problems in OI or leetcode, however, in research such situation is not so likely to happen.

If the best probably answer is: well, when you feel some structures are proper, you can try them, it is hard to say which must be used and which shouldn't. I accept it. I look forward to a more inspiring answer.

There's no hard-and-fast rule.  Use them if they are useful; don't if they are not.  As a broad guideline:

Graphs are often useful when you have relationships between a pair of items.

Trees are often useful when you have a hierarchical relationship.


Good snapshottable data structure for an in-memory index I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the database only supports:

get object/-s by attribute/set of attributes (there may be support for expressions, e.g. x.count < 5)
get object's attribute

A query is an imperative script composed of an arbitrary number of the above operations. The data size will be << memory, so all the object and indices on most of the attributes should fit comfortably without swapping.

What I need is a data structure for the object's attribute index, which can be O(n) on writes, not support write concurrency, but should support ideally O(1) snapshots (maybe copy on write) and O(logN) access. Ideally it would allow high concurrency on reads with maximal structural sharing between the versions.

I was looking at CTries, Concurrent BSTs and Concurrent Splay Trees but I'm not sure if I'm really looking in the right direction here. The above structures pay a lot of attention to the complexity of inserts which I don't care about.

The question: is there a known data structure that is a good fit for my use case out of the box?

EDIT: after thinking some more it seems that a persistent BST/Splay tree would work. The writer would update the 'master' copy and the queries would get the tree as of the start of execution and throw it away after they are done. However, I'm still interested if there's a better solution.

Use any kind of persistent/immutable (i.e., functional) tree-based data structure.  The key is getting the locking right, as @Raphael pointed out in the comments.

The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free.  Let's suppose you use a treap (randomized binary search tree) for your data structure.  Here's an example of one written in Go: https://github.com/steveyen/gtreap.  The author describes it thusly:

  By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.

At any point in time the "current" state of the tree is represented by a pointer to the root of the tree.  Insertions are non-mutating.  Instead an insertion keeps the previous version of the tree completely intact, creates $O(\log n)$ new nodes for the path from the root to the correct insertion point, with pointers back to the nodes of the previous version that can be shared.

You use a lock to protect the pointer to the root.  Since the data structure is immutable reads can be done concurrently, and you can save pointers to old snapshots.  A read is:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

Even though the search may take a while, you only hold the lock while copying the pointer, so the searches can happen concurrently.

A write is:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

In this version, writes do need to hold the lock during the entire process of creating the new version of the tree.  You can improve read performance (at the cost of sometimes having the write transaction fail) by changing the write to something like this:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

You may be able to do even slightly better (make it "lock free") if your programming language has atomic variables with an atomic compare-and-swap operation.  (For example by using C++11's atomic<T*>.)


Why isn't selection sort O(n log n)? We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$

Selection sort proceeds by finding the smallest unsorted element and adding it to the end of the sorted section of the array. You can't use binary search to find the smallest unsorted element, because binary search only works on sorted lists.

Your question seems to be based on the mistaken understanding that selection sort takes the first unsorted element and inserts it into the correct place in the sorted list. The correct place could then be found by binary search but the problem with that attempt at an algorithm is that you need array-like access to the sorted portion for binary searching it, and list-like access for inserting in the middle.


Can we prove mathematical induction statements in Lisp? My previous question Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? has a problem that it tries to cover too much ground.  Here is a related question motivated by the comments.

In Lisp and certain other languages code and data are put on equal footing.  Lisp  is certainly strong enough to define abstractions, lazy evaluation and define types.  I wonder if it is strong enough to prove simple statements about itself.

Important here... I only intend to prove specific theorems.  It is quite clear we can't prove all theorems using any programming language.

Let's try:  $1 + 2 + 3 + 4 + \dots + n = \frac{n(n+1)}{2}$.  Then we statement:

$$ P(1): 1 = \frac{1(1+1)}{2} \text{ and }P(n):1 + 2 + 3 + 4 + \dots + n = \tfrac{n(n+1)}{2} $$

We need to show that $\boxed{P(n) \to P(n+1)}$ this type of statement seems simple enough that we could try to verify it within Lisp itself.  I could be wrong.

This couldn't be so hard.  We have two functions:

$F_1(n) = 1 + 2 + 3 + \dots + n$ and $F_2(n) = \frac{n(n+1)}{2}$
In both cases there is some type of recursion $F(n+1) = (n+1) + F(n)$
Then we could show the implication $F_1(n) = F_2(n) \to F_1(n+1) = F_2(n+1)$

The induction step should be expressible as a recursion.  If the program itself can't prove induction statements, perhaps it can just summarize them in some kind of way.

In Haskell, the strong type means that once it compiles you have proven the types agree.  This may not be as strong as proving other types of theorems.

I am not an expert in proof-checkers so excuse me if I get the basic concepts wrong.

Let me try to clarify a point that seems to be confusing you: you seem to be conflating 2 related, but different concepts.

The first is the concept of a proof system, which allows you to specify and prove theorems about mathematics or computer science. Dependent types are one elegant way to do this, where the types are the specification language and the proofs are identified with programs, but this is not the only way to build a proof system! Isabelle allows you to specify and prove properties about programs, and is not based on dependent types or the Curry-Howard isomorphism/approach. The crucial takeaway is that these systems require the user to supply the proof.
The second is the notion of automatic theorem proof systems (or provers) which take a specification language and automatically attempt to divine a proof. This means that ATP systems are in particular proof systems, where the user input for proofs is just a click on the "prove" button (actually most ATP systems allow and require a lot more input from the user). This state of affairs is of course quite desirable in theory, as it greatly relieves the burden for the user, and most proof systems integrate some capabilities of ATP.

With these clarifications in mind, my first answer is that Lisp is neither a proof system nor an ATP system. It is a programming language. As such, it cannot be said to prove anything as is. The Lisp language is untyped, so it doesn't even make sense to ask if its type system can be seen as a specification language.

My second answer is that Haskell is neither a proof system nor an ATP system. This seems to contradict the answer given to you here, but the point is that the Haskell type system closely reassembles a dependently typed proof system, to the extent that "specification-like" types can be given and "proof-like" programs can be written. One important limitation is that Haskell is not consistent when viewed as a logic. In particular, $1+1 = 3$ can easily be "proven" in a variety of different ways. Actual proof systems like Agda and Coq, however, can be used to specify and prove things about programs, which themselves can be extracted to Haskell programs.

All this being said, there is a very notable ATP system that can specify and automatically prove things about (a small subset of) Lisp programs including your example: the ACL2 system. Hey, they even have your example in these slides! (They don't give the solution though).


Is it allowed to do a binary search with an oracle when proving NP-completeness? In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, implying that the original problem is in NP.

Why is that allowed? Why are you allowed to continue after the oracle returns false? Doesn't this defeat the whole idea of NPC versus co-NPC? You could then simply use an oracle for a NP-complete problem to show that NPC = co-NPC?

I would think that the whole reduction is wrong and that the original problem is probably not in NP. Or aren't they implying that?

Well, nowhere does the answer claim the reduction "implies that the original problem is in NP".  So, that explains your confusion.  You read something into the answer that isn't actually there.

Also, the answer says "Cook reduction".  This was a heads-up about the fact that it's not the Karp-style reduction you might be used to.  You might like to learn about the difference between a Cook reduction vs a Karp reduction.  Read https://en.wikipedia.org/wiki/Turing_reduction.  As you suspected, a Karp reduction is part of what is used in the definition of NP-completeness, but this answer isn't trying to prove NP-completeness, so the Cook reduction is "allowed".


Understanding the definition of Positivity Constraints in Coq In Interactive Theorem Proving and Program Development the authors explain constraints on constructors of inductive types in Coq.

For inductive type $T$, a constructor must have the form $t_1 \rightarrow t_2 \rightarrow ... \rightarrow t_l \rightarrow T a_1 ... a_k$ where $k$ is the number of arguments of the inductive type $T$.

There are some restrictions placed on the $t_i$s, which I cannot understand.

  If $t_i$ is the type of a constant, then $t_i$ can have the form "$g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k}),$" provided the expressions $b_{i,j}$ also satisfy the typing rules, and $T$ does not occur in these expressions or in $g$.

and

  If $t_i$ is the type of a function, this type can have the form $t_1'\rightarrow ... \rightarrow t'_m \rightarrow g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$ but the type $T$ cannot occur in the expressions $t'_1, ... t'_m$ or in the expressions $b_{i,j}$

I am confused on what it means for a type $t_i$ "to have the form of $g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$".

For instance, does nat (the type of natural numbers) have the form of $g(Tb_{1,1} ... b_{1,k})...(Tb_{l,1} ... b_{l,k})$"?

If so, how does nat obtain such a elaborate form? What is $g$ and what are the terms in the $(l,k)$ matrix $b_{i,j}$?

If not, am I prohibited from using nat in type constructors of inductive types? (That would seem absurd...)

Below I have uploaded a screenshot of the page in question.

Update: I was able to construct a counterexample to the textbook:

Definition g := fun x y z : Type => nat.

Inductive T : Set :=
  t : (g T T T) -> T.

Here $l = 1, k = 0$, and $t_1$ can only have the form $g(T)$ but I was able to use $T$ 3 times inside an actual Coq environment.

Edit 2:
I think what you guys are saying about the reduced form makes sense so I tried to make another "counterexample"

Inductive g (x y z: Type) : Set.

Inductive T : Set :=
  t : (g T T T) -> T.

Take $l = k = 0$, the matrix of $b_{ij}$'s has size $0 \times 0$, hence we do not have to defined any $b_{ij}$, and take $g = \mathbf{nat}$.


Merging balls interview problem Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.

  You are given $n$ balls on the table and all the balls are rolling towards the one end of the table with velocities $V_1, V_2, \dots, V_n$ and there is a bucket placed at that end. The distance of the ball with velocity $V_i$ from the end of the table where the bucket is placed is $D_i$. It is given that when two balls collide, both balls merge into each other and move with the velocity of the ball nearer to the bucket. So, at last, you have two tell the number of the balls which will fall into the bucket.

Here is what I am doing. First, I insert one extra ball in the array with zero velocity and distance zero. That is, I am inserting the bucket as a ball. We will find how many balls are getting merged with last ball.

Find a pair of adjacent balls which have the smallest value of
$T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$  and $V_i > V_{i+1}$ and remove ball with velocity $V_i$, that is, the first ball in the pair.
Now for each remaining ball, reduce its distance by its velocity times $T$,
and continue doing this process.

The number of time we will choose the bucket as the second ballwill be the final answer.

Can anyone suggest a better approach? My approach has time complexity of $O(n^2)$.

Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all unaffected pairs, using $D'_j = D_j - TV_j$. The affect this has on the ratios is
$$
 \frac{D'_j - D'_{j+1}}{V_j - V_{j+1}} = \frac{D_j - TV_j - D_{j+1} + TV_{j+1}}{V_j - V_{j+1}} = \frac{D_j - D_{j+1}}{V_j - V_{j+1}} - T.
$$
In other words, their relative order does not change. However, the removed ball $i$ does affect one of the other ratios: instead of $\frac{D_{i-1}-D_i}{V_{i-1}-V_i}$ we now have $\frac{D_{i-1}-D_{i+1}}{V_{i-1}-V_{i+1}}$. So we remove the former and insert the latter instead.

Constructing the min-heap in the beginning takes time $O(n\log n)$.
Afterwards, we perform $O(n)$ operations on the min-heap, each of which runs in $O(\log n)$, and so the total running time is $O(n\log n)$.


Are monoids useful in optimization? Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example).

There is one obvious way in which using monoids can be used to improve performance: the programmers is asserting the operation's associativity, and so operations can be parallelized.

I'm curious if there are any other ways a compiler could optimize the code, knowing that we're dealing with a monoid.

The compiler can optimize exponentiation with monoids. Let $\oplus$ be a binary operator calculateable in constant time such that $\oplus$ and $a_1, a_2, ... \in A$ form a monoid. Then the operation

$$\bigoplus_{[1..n]} a_k = \underbrace{a_k \oplus a_k \oplus \dots \oplus a_k}_{\text{$n$ times}}$$

which usually takes $\cal O(n)$ time can be evaluated with the square and multiply algorithm in only $\cal O(\log n)$ time if the compiler knows that $\oplus$ obeys the monoid laws.


to bail out vs to back out In a CS context, I have often come across the expression to back out meaning to say that a function is returned from before performing its actual task, as in this imaginary code comment:

double divide(double dividend, double divisor) {
  if (divisor == 0) {
    return 0; //divisor is zero => back out early
  }
  return (dividend / divisor);
}

Now I recently came across the expression to bail out in just the very same context. I know that to bail somebody out generally means to provide funds to get someone out of a difficult financial situation, so I was wondering if the writer confused to back out and to bail out or if to bail out really has this meaning, too.

Has any one ever heard or read a native speaker of English say or write to bail out of a function? Or, if you're a native speaker, would you say to bail out is also correct here?

I understand "to bail out" as to give up permanently; "to back out" is to give up some track, possibly to try something else.