What is determinism in computer science? I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number generator to make branching unpredictable, it is still really non-deterministic (but harder to prove so).

I'd like to expand on @jmite's mention of non-determinism due to threading.  "Is your program deterministic?" is a question that might well be asked in a parallel programming class, and the answer with many multi-threaded programs is often "no."

In most multi-threaded programs the exact interleaving of instructions from different threads is indeterminate. We can't determine the order in which instructions are interleaved just by using the program and its input.  To actually figure out what order the instructions would interleave would require us to know the exact state of the caches and branch predictors and tlbs on every core, when all the external interrupts occur to the picosecond (mouse movements, external network traffic, timer interrupts) the exact position of the disk drive heads with respect to the spinning platter, the temperatures of every transistor (at least the transistors that drive the asynchronous busses) and the small fluctuations in voltage coming from the wall socket or battery.

Given that every time you run your multithreaded program the exact instruction interleaving is different, we are really interested in:

  can the multi-threaded program's output be exactly determined knowing only the input and the code?

For example, the following multithreaded program is non-deterministic:

thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

This program will sometimes print "0" and sometimes print "1".

The following multithreaded program is determinisitic

thread A
x = 0
fork thread B               thread B
acquire mutex m             acquire mutex m
x = x + 1                   x = x + 2
release mutex m             release mutex m
join with thread B          finished
print x

This program would usually be considered deterministic.  It always prints "3", although we don't know if the sequence of values of x was 0, 1, 3 or 0, 2, 3.

Things get even more interesting when we are talking about data structures like binary trees.  In a binary tree the exact shape of the tree usually depends on the exact order in which nodes were added.  But often you are using the binary tree to represent some abstract data type (like an ordered sequence) in which many different tree shapes represent the same abstract value.

For example, the binary trees

  0          1          2
   \        / \        /
    1      0   2      1
     \               /
      2             0

all represent the same ordered sequence "0, 1, 2".  So most people would still call this ordered-sequence type deterministic although if you have to debug the program (and thus deal with different runs having different actual representations of the data structure) you might also call it annoying.


Is there a data-structure for semilattices similar to a tree data-structure? If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (more or less) efficiently. In the case of a tree, a data structure which would enable this would be to store for each element in the corresponding node a pointer to the parent and a distance measure to the root. (Actually, a labeling based on topological sort usually used for "a distance measure to the root", effectively all that is needed is a compatible partial order which can be evaluated efficiently).

Each finite join-semilattice can be represented as a set of subsets of a finite set with containment as order such that the least upper bound is given by the union of the sets. Hence, representing each element by a finite number of tags, and computing the least upper bound by the union of the corresponding tags would be one possible data structure. (By looking at the complement, one sees that defining the least upper bound as the intersection of the corresponding tags would also be possible.) A much more common data-structure is to simply use a matrix to store all results of "a <= b" or even all results of "join(a,b)".

However, using such a data-structure to represent a tree would be sort of strange. Are there more tree-like data-structures for join-semilattices, which still allow (more or less) efficient computation of the (unique) least upper bound of two elements? (Perhaps some sort of directed acyclic graph with additional information in the nodes similar to the distance measure to the root for the tree?)

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg.
Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

The first two data structures discussed are the adjacency list representation of the transitive reduction graph (=Hasse diagram/cover relation) and transitive closure graph (=poset relation). A remark about the advantages of using a topological sort to label the nodes precedes that discussion. Note that the labels of topological sort would be good enough as "a distance measure to the root", which was one part of the data-structure for a tree in the question.

The other discussed representations are "Skeletal Representation", "Matrix Representation" and "Dimension Based Representation". The "Skeletal Representation" is interesting and useful, but based on a (=any) chain decomposition of the poset. The "Matrix Representation" might seem trivial, but its probably be the best representation for most practical problems. The "Dimension Based Representation" represents the poset as the subset of the Cartesian product of linear orders, but computing the minimal representation of this kind is NP-hard.

In conclusion, the most treelike representation of these is the adjacency list representation of the transitive reduction together with a labeling of the nodes by a topological sort (instead of "a distance measure to the root"). This is actually one of the representations used by Sage (the other is the "Matrix Representation").


Proving that NPSPACE $\subseteq$ EXPTIME I am following "Introduction to the theory of computation" by Sipser.

My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE.

$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$

I am trying to understand why the the following part is true $NPSPACE \subseteq EXPTIME$.

The explanation from the textbook is following:

"For $f(x)\geq n$, a TM that  uses $f(x)$ space can have at most $f(n)2^{O(f(n))}$ different configurations, by a simple generalization of the proof of the Lemma 5.8 on page 194. A TM computation that halts may not repeat a configuration. Therefore a TM that uses space $f(n)$ must run in time $f(n)2^{O(f(n))}$, so $NPSPACE \subseteq EXPTIME$"

I am trying to understand why it's true, why TM that uses $f(n)$ space must run in time $f(n)2^{O(f(n))}$. Let's try to reverseengeneer the formula: $n$ is the length of the input, 2 is the size of alphabet, $f(n)$ is the space that TM use on the second tape (operational tape) and $f(n) \geq n$, but how to explain what $O(f(n))$ means. Apparently, $2^{O(f(n))}$ expreses a configuration, so $O(f(n))$ must express union of transition function and alphabet, but actually it seems like I get it wrong. The most intriguing question why, in the end,  $f(n)2^{O(f(n))}$ expressed in the terms of time, the transition from space to time is very vague for me.

I will very appreciate if someone could explain me this relationship.

The expression $f(n)2^{O(f(n))}$ is simply an upper bound for the number of all configurations a $f(n)$-space bounded TM can have. Here is how to count: We have $|\Gamma|^{f(n)}=2^{O(f(n)}$ different ways how to fill the work tape, and the head can be on $f(n)$ different positions. There is also a constant number of states where we can currently be, but this is hidden in the big-O in the exponent.

If a TM takes more than $f(n)2^{O(f(n))}$ steps, then it has to visit one configuration twice. Hence it cycles and cannot stop.


Proving NP-hardness of Hamiltonian Cycle problem variant I need to prove that determining whether a graph has a  relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of $G$ exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated twice or even more times).
Note: In a closed walk we can visit a vertex or edge multiple times, but first and last vertex are same. In the relaxed-Hamiltonian cycle this first and last vertex being the same is not counted as repetition.

I am thinking reducing to relaxed-Hamiltonian cycle from Hamiltonian Cycle.
Claim: Construct graph $G'$ given $G$ such that $G$ has Hamiltonian cycle iff $G'$ had relaxed-Hamiltonian cycle.
My idea is that if a graph $G$ has one or more articulation points then it cannot have a Hamiltonian Cycle so simply give a $G'$ which does not have a relaxed-Hamiltonian cycle.
The problem is when graph $G$ does not have any articulation points. In this case the graph $G$ may or may not have an Hamiltonian Cycle. I cannot think of a construction for this case such that my claim holds.
Is my approach correct? If yes please suggest how I could take care of the mentioned case? Otherwise, please hint me towards the correct direction of thinking to get the right construction.

Your definition:

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times).

I'll call this revisited vertex (for a given $C$) the nexus of $C$ and look at a case that shows that even if we know which node must be the nexus of any relaxed-Hamiltonian cycle, the problem is still NP-hard.
Consider two graphs $G_1,G_2$ for which finding a Hamiltonian cycle is NP-hard (which may be two copies of the same graph). Then we create $G$ by identifying a vertex in $G_1$ with a vertex in $G_2$, with the single vertex thus created called $w$. $w$ is an articulation vertex so $G$ cannot have a (standard) Hamiltonian cycle.

If a relaxed Hamiltonian cycle exists in $G$, it must have $w$ as its nexus. To visit all nodes in $G$, we have to visit $w$ and that is the only node which allows us to cross into $G_2$ and visit all nodes there. So we have the second (minimum) visit and $w$ is the nexus.
The definition of the relaxed Hamiltonian cycle means that we could in principle find disjoint cycles all including $w$ within either $G_1$ or $G_2$ and still meet the relaxed-Hamiltonian standard. We can avoid this case by ensuring that nodes in $G_1$ and $G_2$ that we pick for identification to create $w$ are maximum degree $3$, so we cannot re-enter a second cycle in the same graph part from $w$.
Then the problem of finding a relaxed Hamiltonian cycle in $G$ is as hard as finding Hamiltonian cycles in both $G_1$ and $G_2$ which we know can be NP-hard.
Further to your claim, we therefore know that if we find a relaxed Hamiltonian cycle for $G$ we have found a Hamiltonian cycle for both $G_1$ and $G_2$ (and $G_2$ is allowed to be a copy of $G_1$).


What is the average search complexity of perfect hashing? The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?

Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.


How to prove LastToken problem is NP-complete Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $G$ and an initial number of tokens $t(v) \ge 0$ for each vertex $v$, there is a sequence of moves that results in only one token being left in $G$. Prove that LastToken is NP-complete.

I'm learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it's in NP and choose a NP-complete problem that can be reduced from. I'm stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I'm guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don't see any connection between them so far. How should I start a good approach?

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$.

Claim. The previous reduction is correct. Try to prove it formally as an exercise.

Edit. Here is a brief proof of correctness. We have to prove that the created instance is a yes-instance of your problem, if and only if the given instance is a yes-instance of the Hamiltonian path problem. First, let $G$ be a yes instance of the Hamiltonian path. Let $v_1, \dots v_n$ be a Hamiltonian cycle in the graph. Now we describe a winning strategy for the last-token, where in the step $i$ we take two tokens from the vertex $v_{i-1}$ and add one to the vertex $v_{i}$. It is easy to prove by induction, that in step $i+1$ all vertices $v_0, \dots v_{i-1}$ have no tokens in them, the vertex $v_i$ has two and all vertices $v_{i+1}, \dots v_n$ have exactly one token. In the $n-th$ step we take the two tokens left in $c_n$ and put one token in $v_0$ and we are done. Note that $v_i$ has always a common edge with $v_{i+1}$ since the are consecutive in a Hamiltonian path.

On the other hand, assuming the reduced instance is a yes-instance, we prove that the given graph is Hamiltonian. Since all but one vertex have exactly one token. We have only one choice for the first vertex. In each step we take two tokens from a vertex and add a token to another one. It is easy to prove inductively that in each step all but at most one vertex have at most one token in them. One vertex can have two tokens wich is the only choice for the next step. Using this claim, it is also easy to prove that to vertex can be chosen twice. Hence, if we were able to choose $n+1$ vertices, we must have a permutation of the $n$ vertices with $v_0$ starting in $v_0$ and this permutation must be a Hamiltonian path since we always have an edge between two consecutive choices in the game.


Tracing a polynomial algorithm for the problem of maximum-weight independent set It should be a very easy question, but I am a little bit confused.
According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using Dynamic Programming (the Algorithm is also explained on page 562 of the book Algorithm Design). Now, imagine that we want to trace the algorithm on a random graph like the figure below where the numbers in the balls show the weight.

I want to know, does it matter which node I am selecting as the root?
Can you please guide me through the steps of this algorithm's tracing on this graph?

It won't matter which node you select as the root, in the sense that the algorithm will always find a maximum-weight independent set. The actual set of nodes selected by the algorithm might differ, if there are multiple maximum-weight solutions.

Let's say the root is the node with weight 2. Either it is in the optimal solution, or it isn't.

If it is, then 7, 10, and 7 are not; the remaining tree only contains 4. Thus this solution has weight 2 + 4 = 6.
If it is not, then the answer is the maximum-weight independent set on the forest in which the components are the subtrees with weight 7, 10, and (7, 4). Solving the problem recursively on the subtrees gives 7 + 10 + 7 = 24.

Since 24 > 6, the answer is 24.


Number of Combinations of Connected Bipartite Graphs Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?

Obviously there are $2^{n m}$ different set of edges but many will be disconnected.

The answer is was given by David Eisenstadt in his answer to my question.
The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).
While I don't fully understand everything about this problem, the intuitive reasoning is as follows:
Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.
Note:
If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.


Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a} I have the following question :
\begin{align}
L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\
\text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\}
\end{align}
I know that $L_2 \in$ NPC.
Show that $L_2 \in$ NP is relatively easy, I'll skip that part.
I try to show that $L_2 \in$ NPC using a reduction from VC $\leq_p L_2$ (VC is vertex cover which we know in its NPC)
I defined the following function $f$ :
$$f(G,k)=(a,k)$$
I thought of something like that for each node $i$ in $G$ will define a literal $x_i$, and make it in 3DNF format, $a=\bigvee(x_i \wedge x_i \wedge x_i)$ where $1 \leq i \leq n$ where $n$ is the number of nodes in $G$.
We can define that following $z$ such that $z$ safifies exactly $k$ clauses, just give $'1'$ literal $x_i$ such that the node $i$ is in the VC, and $'0'$ otherwise, so such $z$ exists.
So easy to see that $(G,k) \in$ VC $\implies (a,k) \in L_2$ since we showed explicitly such $z$ that safifies exactly $k$ clauses.
But I'm not sure the other side holds $(G,k) \not\in$ VC $\implies (a,k)\not\in L_2$ we given a graph that doesn't have VC in size $k$ but I think due to my building of a ($a=\bigvee(x_i \wedge x_i \wedge x_i)$) we can find $z$ that safifies exactly $k$ clauses (actually we can find $z$ that safifies $x$ clauses where $1 \leq x \leq n$ where $n$ is number of nodes in $G$.
So my reduction doesn't hold?

The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false.
So let $G = (V, E)$ be a graph and $X \subseteq V$ be a VC in $G$.
Then for any edge $vw \in E$ we must have $v \in X$ or $w \in X$, giving us 3 mutually exclusive possibilities (by essentially rewriting $v \vee w$ in DNF):

$v \in X$ but $w \notin X$,
$v \notin X$ but $w \in X$
$v \in X$ and $w \in X$

Hence the edge $vw$ is covered by $X$ if and only if the formula $\psi(vw) = (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$ has exactly one satisfied clause (under the assignment corresponding to $X$).
Constructing such a formula for every edge and taking their disjunction, we get the DNF formula
$$\psi^\text{VC}(G) = \bigvee_{e \in E} \psi(e) = \bigvee_{vw \in E} (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$$
and any assignment satisfying exactly $|E|$ clauses must be a VC of $G$.
Now we need a way to encode the size of the VC into it all, for which we can reuse your idea.
Define
$$\psi(G) = \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$
and note that the number of satisfied clauses in the second part is just given by the size of the set of vertices we select, so the total number of satisfied clauses under the assignment corresponding to some VC $X$ in $G$ is $|E| + |X|$.
There is only one problem remaining here.
We could get an assignment not corresponding to a VC but including more vertices to satisfy the same number of clauses that a desired VC would.
As a remedy, we can repeat the first formula some $|V| + 1$ times such that no matter how many vertices you chose, the total number of satisfied clauses will always be too low.
Hence we obtain the final formula
$$\psi^\ast(G) = \bigvee_{i = 1}^{|V| + 1} \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$
and note that if $G$ has a VC $X$ then the corresponding assignment will satisfy exactly $(|V| + 1) \cdot |E| + |X|$ clauses of $\psi^\ast(G)$.
For the reverse direction, let $\alpha$ be some assignment satisfying $(|V| + 1) \cdot |E| + k$ clauses of $\psi^\ast(G)$.
Then $\alpha$ must represent a VC in G as otherwise, the number of satisfied clauses in the first part of $\psi^\ast(G)$ is at most $(|V| + 1) \cdot (|E| - 1) = |V| \cdot |E| + |E| - |V| - 1$ and as $\alpha$ can satisfy at most $|V|$ clauses in the second part, the total number of satisfied clauses will be at most
$$(|V| + 1) \cdot (|E| - 1) + |V| = |V| \cdot |E| + |E| - 1 < (|V| + 1) \cdot |E|$$
However, this implies that the total number of satisfied clauses in the first part must be exactly $(|V| + 1) \cdot |E|$ and thus exactly $k$ clauses of the second part are satisfied by $\alpha$, so $\alpha$ corresponds to a VC $X_\alpha$ of size $k$ in $G$.
Note that for clarity I did not specify a $3$-DNF formula. However, as all clauses in $\psi^\ast(G)$ are of size at most $2$ you can just add redundant literals to the clauses to blow them up to size $3$ if need be.
I am not sure that this is the best way to do this, but it should work out. I omitted some details for brevity, please feel free to ask for additional clarifications if something is not clear to you :)


Finding square root without division and initial guess I am trying to look for a division-free algorithms which finds square-root using only addition and multiplication operations, with the initial guess as the number itself. Is there any such algorithms ?

OK, let's go with floating point. Any positive floating point number is of the form $m \times 2^e$ where $m$ is in the range $[1,2)$ and $e$ is an integer.

If $e$ is even, then:

$$\sqrt{m \times 2^{2p}} = \sqrt{m} \times 2^p$$

And if $e$ is odd, then:

$$\sqrt{m \times 2^{2p+1}} = \sqrt{m} \times \sqrt{2} \times 2^p$$

We can precompute $\sqrt{2}$. So we have reduced the problem to finding a square root of a number between 1 and 2. So far, so good.

We could use the Newton-Raphson method for square roots, but you specifically didn't want division, and it's a bad idea anyway; division is more expensive than multiplication on a modern FPU.

But we could use the Newton-Raphson method for reciprocal square roots. The iteration looks like this. If $x_0$ is an initial approximation to $\frac{1}{\sqrt{m}}$, then iterate:

$$x_{i+1} = \frac{1}{2} x_i \left( 3 - m x_i^2 \right)$$

When this has converged, $m x_k$ is an approximation to $\sqrt{m}$. No divisions here, and the problem is now just to come up with an initial estimate.

But wait, we can do better.

Given $b_0 = m$, let's suppose we could come up with a sequence of numbers $Y_i$ such that $b_i = b_0 Y_0^2 Y_1^2 \cdots Y_n^2$ approaches $1$. Then $x_i = b_0 Y_0 \cdots Y_{i-1}$ approaches $\sqrt{m}$ and $y_i = Y_0 \cdots Y_{i-1}$ approaches $\frac{1}{\sqrt{m}}$. Please pause for a moment and convince yourself that this is the case.

We already know such a sequence, because we can use the Newton-Raphson iteration for reciprocal square roots:

$$b_i = b_{i-1} Y_{i-1}^2$$
$$Y_i = \frac{1}{2}(3 - b_i)$$

And so:

$$x_0 = m Y_0$$
$$x_{i} = x_{i-1} Y_i$$

and:

$$y_0 = Y_0$$
$$y_{i} = y_{i-1} Y_i$$

But observe that $b_i = x_{i-1} y_{i-1}$. So we don't actually have to retain $b_i$:

$$Y_i = \frac{1}{2}(3 - x_{i-1} y_{i-1}) = 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1})$$

Substituting this into the equations for $x_i$ and $y_i$ gives:

$$x_{i} = x_{i-1} \left( 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1}) \right) = x_{i-1} + \frac{1}{2}(1 - x_{i-1} y_{i-1}) x_{i-1}$$
$$y_{i} = y_{i-1} \left( 1 + \frac{1}{2}(1 - x_{i-1} y_{i-1}) \right) = y_{i-1} + \frac{1}{2}(1 - x_{i-1} y_{i-1})y_{i-1}$$

Removing the redundant computation gives:

$$r_i = \frac{1}{2}(1 - x_{i-1} y_{i-1})$$
$$x_{i} = x_{i-1} + r_i x_{i-1}$$
$$y_{i} = y_{i-1} + r_i y_{i-1}$$

But we're not done! We can save the multiplication by a half by substituting $h_i = \frac{1}{2} y_i$.

Given $Y$ as an approxmiation to $\frac{1}{\sqrt{m}}$, set:

$$x_0 = m Y$$
$$h_0 = \frac{1}{2} Y$$

Iterate:

$$r_i = \frac{1}{2} - x_{i-1} h_{i-1}$$
$$x_{i} = x_{i-1} + r_i x_{i-1}$$
$$h_{i} = h_{i-1} + r_i h_{i-1}$$

Then $x_i$ converges to $\sqrt{m}$ and $y_i$ converges to $\frac{1}{2\sqrt{m}}$. Not only does the inner loop have no divisions, it can be implemented on modern FPUs using three fused multiply-adds and nothing else. Perhaps it's unsurprising that this algorithm, known as Goldschmidt's algorithm, is the one used in your FPU.

The final question: How do we come up with $Y$? Well, you could use $\frac{1}{m}$ or something if you want to allow one division. But you said no divisions. So since $m$ is known to be between 1 and 2, you could use its high-order bits to consult a lookup table, or use an interpolating polynomial approximation, such as a Chebyshev polynomial. I'll leave the details of that to you.


Why is the graph inside Graham Scan always planar One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's formula the number of edges can never be more than $3*n$ (where $n$ is the number of vertices). My question is, how do we know that the edges examined by Graham Scan never intersect (hence always form a planar graph)?
Here is the screenshot of this being discussed in the course "Computational Geometry" from Tsinghua University (from EdX.org). The lecturer just mentioned it being true, but did not give the proof.

The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest.

See this for a good visual.


Without fancy math, how does the MC-AIXI algorithm work? How does the MC-AIXI algorithm work? I tried to read the paper, but I got lost in the math. I understand the concept of AIXI very well, but I don't get two things:

1) Where does MC-AIXI get its models from?? Kolmogorov complexity is non-computable! Why can MC-AIXI get models?

2) How exactly does the decision tree work? I kinda get the concept, but how does it know what it will do in the future without doing another calculation, and so on ad infinitum?

I would like enough information do make my own version of it. Thank you so much for your help!

I'll assume that the paper you're referring to is Veness et al. (2011) - A Monte-Carlo AIXI Approximation. The paper (and the AIXI model more generally) is rather technical, and so it is difficult to talk about without using much math. I'll do my best to explain informally here.

The question is in two parts, so I'll address each separately.

Models

The full mathematical formulation of AIXI makes use of Solomonoff induction to model the environment. Informally, Solomonoff induction involves enumerating every possible model (program) that is consistent with what has been observed, and weighting their likelihood by the inverse of their length. Solomonoff induction can be thought of as a theoretical upper limit on how well you can learn in the general setting while making no assumptions. As the question points out, it is of course incomputable.

We can relax the requirement that we model the world only using the Solomonoff prior, and introduce some other model class, which we will call $\xi$. Our agent is still a Bayesian expectation-maximizing reinforcement learner, but we can now plug it into a less powerful and less general (but computable) model. Hutter calls these agents AI$\xi$. In Veness et al.'s paper, they adapt the Context Tree Weighting (CTW) compression algorithm so that it can be used as a predictive mixture model of the form of $\xi$.

CTW is essentially a mixture over $n^{\text{th}}$-order Markov Models over bits, up to some finite order $N$. Each so-called context tree models dependencies in sequences of bits up to some finite depth. The CTW algorithm weights each context tree by its complexity (essentially how many nodes are in the tree). In this way, the CTW compressor can be made into an efficient, general, and fully Bayesian approximation of Solomonoff induction, and is great at learning short-term dependencies in bit sequences.

Veness et al. call their algorithm MC-AIXI-CTW, to emphasize that it is a two-fold approximation of AIXI: both in the planner (MC), and in the modelling (CTW). They could have used a different model, but they chose CTW because it makes no assumptions about the environment, and so is a general and principled choice. This allowed them to use the same model to learn to play various games, like rock-paper-scissors, cheesemaze, Pacman, and Tic-tac-toe.

Planner

The other side of the MC-AIXI-CTW implementation is the Monte Carlo planner. The algorithm that the authors develop is a straightforward generalization of the commonly used expectimax algorithm, called Monte Carlo tree search (MCTS). MCTS has been used in various AI applications over the last decade or so, and there are lots of online resources about it; the Wikipedia page is a decent starting point. I'll give my own short overview:

If you've studied game theory or introductory AI, then you'll be familiar with minimax. This algorithm can be used to compute the optimal next move when playing a deterministic two-player game. In the case of AIXI interacting with some environment, we can model this as a two-player game, but we must lift the deterministic assumption, as the environment is unknown, and in general stochastic; our models (which we use to plan with) are probabilistic, and so minimax won't cut it here. We instead use expectimax, which is the stochastic generalization of minimax. Instead of the other player adversarially (and deterministically) choosing the min action every turn, we now have to sample from some probability distribution.

MCTS is a sampling algorithm for doing just this. The general idea is that we plan ahead by simulating potential outcomes, using our model. Our objective is to compute the value of each of the moves available to us, so as to pick the best one. The value is in general a random variable, since our model is probabilistic. Hence we should choose the action that maximizes our expected value. The MCTS algorithm repeatedly plays out (simulates) a game tree, but instead of adversarially picking the opponent's moves, they are sampled from AIXI's model. As we collect more samples, our estimate of the value of each move will become more accurate.

Of course, we don't have infinite compute power, and so we can't simulate the agent-environment interaction ad infinitum; we have to stop at some depth of the MCTS tree. In simple game-playing, like chess, we would use heuristics to generate some intermediate value at this finite depth, so that we have something to work with to propagate up the search tree. In this general setting that MC-AIXI is trying to plan in, we have no such heuristics, and so we have no choice but to stop the search once we reach some finite (and typically small) depth.

This is the biggest limitation of the algorithm: planning is a huge computational bottleneck for MC-AIXI. In the absence of heuristics, it's hard to perform well in environments that demand long-term planning, since MCTS treats $\xi$ as a black-box environment model. To answer your question: once the planner reaches its planning horizon, it has to stop simulating ahead and make do with whatever it's sampled from that play-out. This is of course very limiting, but is unfortunately necessary, since doing anything else would require some kind of domain knowledge, which defeats the purpose of having a maximally general reinforcement learner.

Sorry if this answer is a bit long and hand-wavy. I interpreted the direction 'without using fancy math' in the strongest sense that I felt I could get away with. Hope it helps! Also, because I'm a new user to CS.SE, I'm limited to two links per answer. Once I've accumulated some points, I'll go back and edit this answer to include more links to external resources.


What is the time complexity of this Factorization program? input: n-bit integer X

output: list of prime factors and their multiplicity

acc = X

for i = 2 ... sqrt( X )

--count = 0

--while acc % i == 0

------acc = acc / i

------count = count + 1

--if count > 0

------print i (count)

I know that for the worst case, a n-bit integer is 2^n maximum.

So the time complexity for for i = 2 ... sqrt( X ) is 2^(n/2)-1

Now I'm really confused with the time complexity of while acc % i == 0

For the worst case, let's say that the n-bit number X is a prime. Then the while loop will not be executed at all. How can I define its time-complexity?

How can I find the Big-O of this algorithm? Is iit O(2^n) or O(2^(n/2))

Your algorithm takes $O(X^{1/2})$ in the worst case, which isn't too bad, but it also takes $\Theta(X^{1/2})$ in the best case. That's because you always test divisibility by all numbers up to $X^{1/2}$ even when it is clear that you found all factors of X already.

The loop testing acc % i = 0 is negligible, because X has at most $\log X$ factors.


Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally? Perhaps this is the wrong exchange, so if there is a better place to post this please tell me!

The DataMatrix encodes diagonally in a sort of zig zag pattern, as shown below.

Why don't they encode horizontally or vertically, like how it's done in QR Codes? If they did this it would appear to eliminate the need for confusing diagonal wrapping. QR code encoding algorithm for reference below:

Not a full answer, but this AMS column considers the same question:
"The way in which bytes are stored as bitten squares might seem a bit peculiar, but if you think about how errors occur in the transmission of data matrices (for example poor printing, postage cancellation), it makes sense. The scheme is designed so that the minimum number of bytes are affected by such errors. Other features (the funny way in which `unrandomization' is applied) are not so clearly advantageous, and are pretty much a mystery to me."
http://www.ams.org/publicoutreach/feature-column/fcarc-data-matrix


Does finding a cycle with $\log n$ length in $\text{P}$? Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?

You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.


k-query oracle Turing machine A k-query oracle Turing machine can query its oracle for at most $k$ times. How could I show that assuming $\text{NP} \not= \text{coNP}$, we have $\text{NP} \cup \text{coNP} \subsetneq \text{P}^{\text{SAT},1}$ (query only once)? I tried to show this strict inclusion directly or its counterexample but to no avail... There was such a question on this site, but the top vote isn't a direct answer. Could somebody provide me more insight into this again? Thanks!
More specifically, I wonder how should I think of these $k$-query machines from machines with unlimited number of queries. I can see that they should have limited computation power, but I'm not sure how to utilize that for the proof.

Let's try to show the contrapositive. Since $\mathsf{NP} \cup \mathsf{coNP} \subseteq \mathsf{P}^{\mathsf{SAT},1}$, the contrapositive states that if $\mathsf{P}^{\mathsf{SAT},1} \subseteq \mathsf{NP} \cup \mathsf{coNP}$ then $\mathsf{NP} = \mathsf{coNP}$. Let us assume, therefore, that every problem in $\mathsf{P}^{\mathsf{SAT},1}$ is both in $\mathsf{NP}$ and in $\mathsf{coNP}$. We would like to show that this implies that $\mathsf{NP} = \mathsf{coNP}$.
We can imagine that the argument will have the following structure:

Come up with some language $L \in \mathsf{P}^{\mathsf{SAT},1}$.
The assumption implies that $L \in \mathsf{NP}$ or $L \in \mathsf{coNP}$.
Use these facts to say something about the relation between $\mathsf{NP}$ and $\mathsf{coNP}$.

Our goal is to show that $\mathsf{NP} = \mathsf{coNP}$, or equivalently $\mathsf{NP} \subseteq \mathsf{coNP}$. This, in turn, is equivalent to showing that $\mathsf{SAT} \in \mathsf{coNP}$. Considering the plan above, what we need is to find a language $L \in \mathsf{P}^{\mathsf{SAT},1}$ such that both $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$ imply $\mathsf{SAT} \in \mathsf{coNP}$.
We can take as $L$ the following language:
$$
L = \{(x,0) : x \in \mathsf{SAT}\} \cup \{(x,1) : x \notin \mathsf{SAT}\}.
$$
Details left to you.


Universal hash functions - Proof Problem statement
Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \{0, \ldots, m-1\}$. Now let $H = \{h \mid h : K \to I\}$, i.e. $H$ contains all hash functions which map the keys from $K$ to the set $\{0, \ldots, m-1\}$.
Prove or disprove that $H$ is universal.
Attempt
Reiterating the definition

A family of hash functions $H$ is universal if and only if for $\forall x, y \in K, (x \neq y)$ we have
$\left|\{h \in H : h(x) = h(y)\}\right| = \frac{|H|}{m}$

I know you can construct specific families of universal hash functions and there are families which aren't universal. But if you consider all of them how would you know which part would outweigh which to decide if this statement still holds?
I'm probably going the wrong way so I would appreciate any help or hints!

Let us first look at the total number of hash functions in $H$. Since each key can be mapped to $m$ different indexes and there $n$ different keys. We get:
\begin{align}
|H| = m^{n}
\end{align}
Now, without loss of generality, let us consider the first two keys $x = k_{1}$ and $y = k_{2}$. We will compute the number of hash functions where $x$ and $y$ will collide i.e., $h(x) = h(y) = i$ for any $i \in \{0,\dotsc,m-1\}$.
\begin{align}
|\{h \in H : h(x) = h(y) = i\}| = m^{n-2}
\end{align}
Therefore, summing up for all $i \in \{0,\dotsc,m-1\}$, we get:  $$|\{h \in H : h(x) = h(y)\}| = m^{n-1} = \frac{|H|}{m}$$
Hence, $H$ is a universal hash family.


Small space hash functions that are weakly but not strongly universal This is a follow up to this this question about weakly universal hash functions

A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

I previously asked for an example of a hash function family which is weakly universal but not strongly universal.  The very nice answer was:

  Take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$,
  given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i &
> \text{if } x = m+1. \end{cases} $$ The same approach can be used for
  arbitrary $|U|$: fix the first $m$ coordinates, and make all other
  coordinates uniformly and independently random.

For arbitrary $|U|$, it seems that in order to represent a single hash function in practice you would need to store a lookup table of size $|U|$ to ensure that the hashed values are independent and truly random. Then for every key, you would look up its random value in the vast lookup table to compute the hash function.

Is there a hash function family where the hash functions require constant or log space that achieves the same result of being weakly but not strongly universal?  In other words, are there any practical hash function families that are weakly not but strongly universal?

Let $H$ be a family of strongly universal hash functions from $U$ to $[m]$.
Construct a new family of hash functions from $U \cup \{x\} \to [m]$ by extending all functions $h \in H$ with $h(x) = 1$. The family is weakly universal since $h(u)$ is distributed uniformly for every $u \in U$, but it is clearly not strongly universal.


Are there more languages than functions? My gut says "no", but I don't know why.

For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(s)$, or the empty string if $f(s)$ is undefined.  So there at least as many languages as functions.  How can we define a function for every language?  (Forgive my ignorance about languages, automata, etc.  I have not studied in that area.  Perhaps my question is poorly constrained.)

It depends on the signature of the function.  In computability theory we typically deal with functions with the signature $f:\{0,1\}^* \to \{0,1\}$.  There is a one-to-one correspondence between functions $f:\{0,1\}^* \to \{0,1\}$ and languages $L \subseteq \{0,1\}^*$: in particular, the function $f$ corresponds to the language $L=\{x : f(x)=1\}$, and the language $L$ corresponds to the function $f(x) = 1$ if $x \in L$, $f(x) = 0$ if $x \notin L$.


Is there any strategy to brute force search? I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space.  This might be naive of me, but I imagine that how I choose to enumerate through the search space could greatly affect whether or not my algorithm works well in practice.

Consider the following decision problem as a simplified example.

Input: A polynomial $p(x)$ with integer coefficients and a natural number $k$.

Question: Does there exist $i \in [k]$ such that $p(i) = 0$?

Now, there could be many different algorithms for solving this problem, but I decide to choose a brute force approach.  Consider the following strategies for enumerating through the search space.

Ascending Strategy: I could check if $p(1)$ is 0, then $p(2)$, then $p(3)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Descending Strategy: I could check if $p(k)$ is 0, then $p(k-1)$, then $p(k-2)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Popularity Strategy: I could store a small list $L$ of most popular solutions and try those first before trying the numbers in $[k] - L$.

Sieve Strategy: I could do a sort of sieve enumeration.  I try all numbers divisible by 2 in $[k]$, then numbers divisible by 3 in $[k]$, then 5, then 7, then 11, then 13, and so on.  (Assuming that I have access to some large pre-computed list of primes.)

Randomness Strategy: Maybe there is an interesting enumeration strategy that utilizes a large string of random bits.

Basically, I'm looking to answer the following questions about brute force search algorithms:

Question A: Are there any benefits to choosing a specific enumeration strategy?

Question B: Are there any examples of search problems where in practice you would choose an interesting enumeration strategy?  I feel like there may be some search problems where in practice a variant of the Popularity Strategy works effectively.

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.


What is the significance of the following equation in computer vision? Say I have a set of sample measurements of a one dimensional curve in the image plane $f(x)$. What is the purpose of minimizing the following functional
$$E(S) = \int \left[\lambda(S''(x))^2 + (f(x) - S(x))^2 \sum_k \delta (x - x_k)\right]dx$$

I believe it has something to do with energy minimization and snakes.

I would agree - energy minimization for snakes (active contours).

It minimizes second derivative - bending of the curve.

Minimizes the difference between the image (probably it's edges) and contour (at discreet contour points - the reason for having Dirac impulse in the expression).

Usually one could expect also to have minimization of the first derivative - stretching of the snake.

More details and references on wiki - active contour


In place and Out place sorting meaning? What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.

In place sorting is sorting without using extra memory (mostly swapping elements till getting it right).

PS In many cases it's impossible to not use any extra memory, but usually in place sorting indicates to constant extra memory.


Modelling 2 object situation with Propositional Logic I'm reading up on propositional logic, and I'm completely stuck on this example - spent the past few hours trying to figure it out! Any pointers would be appreciated.

There's 2 trees, each with signs on.

Sign 1/Tree 1: There are leaves on this tree, and no leaves on the other

Sign 2/Tree 2: There are leaves on one of these trees, but none on the other.

Exactly one of the signs is true, and the other is false. Which tree has leaves on (without looking)?

I'm starting to doubt that it's possible to tell, but I'm sure there's some logic that says otherwise!

Let $P_1$ indicate that Tree 1 has leaves (i.e. $P_1$ is true if Tree 1 has leaves), and $P_2$ indicate that Tree 2 has leaves. Sign 1 states $S_1 = P_1 \land \lnot P_2$, and Sign 2 states $S_2 = (P_1 \land \lnot P_2) \lor (\lnot P_1 \land P_2)$. We are given that $R = (S_1 \land \lnot S_2) \lor (\lnot S_1 \land S_2)$.

In order to solve this, we simply calculate $S_1,S_2$ for each of the possible truth assignments of $P_1,P_2$:
$$
\begin{array}{cc|cc|c}
P_1 & P_2 & S_1 & S_2 & R \\\hline
F & F & F & F & F \\
F & T & F & T & T \\
T & F & T & T & F \\
T & T & F & F & F
\end{array}
$$
The only truth assignment for which $R$ holds is $P_1 = F$, $P_2 = T$. We conclude that Tree 1 has no leaves and Tree 2 does have leaves.


find separate pairs of points with minimal total distance I am looking for suitable algorithm how to solve the following problem.

For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \emptyset$) on two ordered sets and assignment $\pi$ between elements of these two sets, where the following conditions must be fulfilled:

$|A| = |B| = N$ where $N = \lfloor N_s/2 \rfloor$
$s_k \in S$ where $k = 1,2, ...,N_s$
$a_i \in A$ and $b_j \in B$ where $i,j = 1,2, ..., N$
$\sum_{i=1}^{N}|a_{\pi(i)} - b_i| \to min$

In other words, I am looking for method how to find set of separated pairs $[a_{\pi(i)},b_i]$ assignments.

Example:
$$S = [3.0, 2.1, 0.9, 2.9, 1.1], N_s = 5, N = 2$$
then
$$A = [3.0, 0.9]$$
and
$$B = [2.9, 1.1]$$ which produce following separate pairs:

$$[3.0, 2.9], [0.9, 1.1]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.

Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then:

If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more.
If $N_S$ is odd, enumerate over all possible items $s_i$ in $S$ and for each of them, compute the best partition of $S \setminus \{s_i\}$, which is an even-size set, using the previous case. Return the best partition among all $N_S$ cases.

The total cost of this procedure is $O(N_S \log N_S)$ when $N_S$ is even and $O(N_S^2 \log N_S)$ when $N_S$ is odd.


Complexity analysis of m!/n!(m-n)! Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else?
Please elaborate.
Thanks

The growths could be linear or constant depending on the relationship between $m$ and $n$ as they grow large. For example, if $n$ grows with $m$ as in $m=n+1$, then $\binom{m}{n}=\binom{n+1}{n}=n+1$.
Now, if you are interested in the maximum growth, then the binomial coefficients $\binom{m}{n}$ are largest when $n$ is half of $m$. Put $m=2n$ and use Stirling's approximation for the factorial. You get
$$\binom{2n}{n}=\frac{(2n)!}{(n!)^2}\sim \frac{(2n)^{2n}e^{-2n}\sqrt{4n\pi}}{n^{2n}e^{-2n}2n\pi}=\pi^{-1/2}2^{2n}n^{-1/2}$$


NPC PROBLEM minimum sum of vertex coloring For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don't understand how to do a reduction to check the minimum.
I got a hint to do a reduction from 3-NAE-SAT but I don't understand how.
would appreciate some help. even some source I can read about this problem if you know about something.

We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable?

Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are
$$
\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a < b \leq 3 \}.
$$
In words, we take three copies of $G$, and connect all copies of the same vertex.

If $G$ is 3-colorable then $G'$ can be 3-colored: given a 3-coloring $\chi$ of $V$, color $(i,a)$ with the color $\chi(i) + a \bmod 3$. The sum of the colors is $6|V|$.

Conversely, suppose that $G'$ has a coloring $\chi'$ whose sum is at most $6|V|$. Note that the three copies of each vertex $(i,1),(i,2),(i,3)$ must be assigned different colors, which sum to at least $6$. Therefore $\sigma \chi' \geq 6|V|$ for any coloring $\chi'$, and $\sigma \chi' = 6|V|$ iff $\chi'$ is a 3-coloring. Considering one of the copies of $G$, we see that $G$ is 3-colorable.


What is a the fastest sorting algorithm for an array of integers? I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:

Which is the fastest currently known sorting algorithm?
Theoretically, is it possible that there are even faster ones? So, what's the least complexity for sorting?

In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $\Omega(n\log n)$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements.

Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $\Omega(n!)$.

This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.


fully homomorphic encryption with information-theoretic security? An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can reduce your uncertainty about the plaintext.

Fully homomorphic encryption is, roughly, an encryption scheme where $\text{Encr}(T(x)) = T(\text{Encr}(x))$ for arbitrary transformations of the ciphertext and plaintext (this is not entirely accurate but that's not important for this question).

Is it theoretically possible to have an information-theoretically secure FHE scheme? That is, is it possible to encrypt a plaintext $x$, have an external party do computations on them in a fully homomorphic way, without them being able to gain ANY information about the plaintext even with infinite? computing power?

You said you don't need to conceal the set of transformations that have been applied.  In that case a simple scheme is

$$T(\text{Enc}(x)) = \langle T, \text{Enc}(x)\rangle,$$

where $\text{Enc}$ is information-theoretically secure encryption (e.g., the one-time pad).  In other words, you simply list in the cipher text which transformations should be applied to $x$ after it is decrypted.


Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography? I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography).
I have spent much time reading journals and papers but as yet have been unable to find any record of that performance complexity.
It is known that the algorithm is
encryption function is :

$C1 = k1 * m1$  mod  p

$C2 = k2 * m2$  mod p

The decryption function is:

$m1 = C1 * k1^ {-1}$ mod p.

$m2 = C2 * k2^{ -1}$ mod p.

I think the encryption function it take $O(N)^{2}$

where
$T(C1) = O(\log n)^2$ bit operations.

$T(C2) = O(\log n)^2$ bit operations.

and the decryption function it take $O(N)^{3}$.
where

$T(m1) = O(\log n)^2 + T(k1^{-1})$.

$T(k1^{-1}) = O(\log n)^3$, by extend Euclid’s method.

$T(m1) = O(\log n)^2 + O(\log n)^3$ bit operations.

$T(m2) = O(\log n)^2 + O(\log n)^3$  bit operations.

Is that true?.

Your bounds seem to be correct, assuming $n$ is the length of $p$, though writing $T(C1) = O(\log n)^2$ is wrong on two counts. First, it should be $O(\log^2 n)$ or $O((\log n)^2$) on the right. While $O(\log n)^2$ has the same meaning, it's not a "closed form", rather like writing $O(\sum_{k=1}^n k)$ instead of $O(n^2)$. Second, $T(C1)$ looks like $C1$ is some parameter like the input length or the number of vertices, whereas you intended $T(C1)$ to be the time needed to compute $C1$. Better notation would be $T_{C1}$, say, and you could include the input length $n$ as a parameter.

Moreover, note that there are faster integer multiplication algorithms, and some of them are used in practice in cryptographic contexts (not necessarily the ones which are asymptotically best). So you can get even better bounds on the running time depending on the implementation.

The reason you couldn't find the time complexity is that the algorithms use a constant number of two very common operations, namely multiplication and inverse modulo $p$, so the running times can be read immediately by experienced practitioners. This is even the case with more complicated operations such as modular exponentiation.


are regular languages closed under division I am trying to solve this question which appeared in previous exam paper

Can someone help me what i am failing to understand

For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy \in A \text{ for all } y \in B\}$.
If $R$ is regular and $L$ is any language, is it always the case that $R\div L$ is regular? Explain.

I am thinking as regular languages closed under right quotient hoping we can use the same proof here but I understand that in right quotient we prove it for any $y$ that belongs to $B$ but for division it is for all $y$ in $B$ .

Also if I have  $L_1$ is regular and $L_2$ is context-free, is $L_1/L_2$ Always regular? Always context-free but not always regular? Or not always context-free? Which one is true?

When $L_1$ is context-free and $L_2$ is regular, is $L_1/L_2$ always regular? Always context-free but not always regular? Or not always context-free?

Any ideas will really help me in preparing for my test.

If $L_1$ is regular and $L_2$ is any language, then $L_1 / L_2$ is regular. In fact, the construction of a DFA for $L_1 / L_2$ is almost trivial (with one caveat): It's the same as the DFA for $L_1$, except that the "final" states are the the states which can reach the original accepting states given a string from $L_2$.

Suppose that $M_1 = (Q, \Sigma, \delta, q_0, F_1)$ is the DFA which accepts $L_1$. Then a DFA which accepts $L_2$ is $M_2 = (Q, \Sigma, \delta, q_0, F_2)$, where:

$$F_2 = \left\{ q \in Q : \exists x \in L_2. \delta(q,x) \in F_1 \right\}$$

Now here's the caveat: this proof sketch is not constructive! To turn this into an algorithm requires some way to enumerate or recognise strings in $L_2$, and remember, $L_2$ can be any language.

If $L_1$ is context free and $L_2$ is regular, $L_1 / L_2$ is always context-free (proof left as an exercise), but it is not necessarily regular. (To see why, consider $L_2 = \{ \epsilon \}$.)

EDIT I've just noticed that the definition in the question is different from the usual definition of "right quotient". The usual definition is:

$$A/B = \left\{x\in \Sigma^{*} : \exists y \in B. xy \in A\right\}$$

The definition in the question is:

$$A\div B = \left\{x\in \Sigma^{*} : \forall y \in B. xy \in A\right\}$$

My answer us for the usual definition, because these are standard results. The answers are similar for the definition in the question, except that the construction is slightly different. (See David Smith's comment.)

I suspect there is a typo in the original question.


Showing party invitation problem is np-complete Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party.  Depending on how much you like housemate $i$, you pick an integer $m_i$ indicating the minimum number of people on $i$'s list that you'll invite.  Having selected these values $m_i$ already, you'd like to know whether it is possible to invite at most $n$ people to your party such that for each housemate~$i$, at least $m_i$ of the people in $P_i$ are invited.  We call this the Party Invitation problem.  Prove that Party Invitation is NP-Complete.

I am not really sure which problem to reduce from and how to construct the reduction. Thank you

Simple party invitation problem. Suppose there are $m$ housemates decide to throw a party. Each housemate $i$ specifies a group of people $P_i$ who could be invited, $1\le i\le m$. Is it possible to invite at most $k$ people to the party such that at least one person in $P_i$ for each $i$ is invited?

It is enough to show the simple party invitation problem is still NP-Complete, which is, in fact, true.

Let's try to do some pattern matching between the simple party invitation problem and the set cover decision problem.

In set cover, we are given many sets, and we want to find some sets that satisfy some constraints. In simple party invitation, we are given many persons, and we want to find some persons that satisfy some constraints. Hence it seems that a set among the given sets should correspond to a person that could be invited. (Yes, a set corresponds to a person, which might be counterintuitive and which might be why this problem is not immediate to solve.)

What about the constraints? In set cover, we want to find some sets the union of which will cover all elements. In simple party invitation, we want to find some persons to invite so that every lists of people will be covered, that is, there is at least one person invited in each list. It looks like an element in set cover corresponds to a list of persons in simple party invitation. (Again, an element corresponds to a list, which might not be straightforward and which might be why this problem is not immediate to solve.) The fact that an element is a member of a given set in set cover corresponds to the fact a list of persons contains a given person.

You take it from here.

You could also reduce the hitting set problem to the simple party invitation problem, which might be clearer intuitively if you are familiar with the former.

For the pattern matching part, I am following the great teaching style in this answer of Yuval.


Parallel algorithms on a fixed number of processors Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$.

This is great from a theoric point of view, but strange from a practical point of view, where the number of the processors that we can use is bounded by a constant. A corollary of the Brent Theorem allows us to simulate a parallel machine with less processors, but doesn't gurantee that the algorithm is still optimal.

Is there a branch of parallel algorithms that studies parallel algorithms that run on a number of processors bounded by a constant?

As commented below:

  If the number of processors is bounded by a constant, then any
  sequential algorithm will be asymptotically optimal.

I think that this fact implies that asyntotical optimality is not the best way to measure performances in real world parallel algorithms.

Is there another measure, like speedup or cost (defined as execution time multiplied by the number of processors) that can tell us how faster is an algorithm that runs on a constant number of processors?

A related question is: How to scale down parallel complexity results to constantly many cores?

There are several models, widely used in practice, that might be of interest to you.  Almost all of them could be viewed as generalizations of Amdahl's law.  They take two parameters, $P$ (number of processing elements) and $N$ size of the input.  Several conferences in which you are likely to find these types of analyses are the ACM Symposium on Parallel Algorithms and Architectures (SPAA), and the ACM SIGPLAN Symposium on the Principles and Practice of Paralllel Proogramming (PPoPP).

The goal with these models is generally to understand the tradeoff, for a specific algorithm, between the increased parallelism available from larger $P$ with the increased synchronization and communication costs that come along with larger $P$.

The first one that got major attention was

  Valiant, Leslie G: A bridging model for parallel computation, Communications of the ACM, 33(8):103-111, 1990.

Valiant assumes that your algorithm moves between phases of completely parallel work, a phase of barrier synchronization during which the processors communicate, and then the next phase of completely parallel work.  For each computation phase you assume it is going to take time inversely proportional to $P$.  For the synchronization phases you usually want to take into account load imbalance, and the latency of the communication phases is going to depend both on the structure of your communication network and how good a job you can do at minimizing the distance between communicating processors.

The paper

  Culler, D; Karp, R; Patterson, D; Sahay, A; Schauser, KE, Santos, E; Subramonian, R; von Eicken, T: $LogP$: Towards a Realistic Model of Parallel Computation, ACM Symp Principles and Practice of Parallel Programming, (PPOPP-4):1-12, 1993.

built on Valiant's model by carefully taking into account the $L$atency between nodes, the $o$verhead of sending a message, and the $g$ap required between send operations (a measure of bandwidth), in addition to $P$.  This is too detailed for some uses, but can be useful in cases where it is important for the algorithm designer to choose between many small messages and fewer long messages.

Finally I'll mention

  Blumofe, Robert D; Leiserson, Charles E: Scheduling Multithreaded Computations by Work Stealing, IEEE FOCS, 1994.

which gives a small generalization of Amdahl's law, pointing out that execution time is bounded (below) by $T_P = O(T_1/P + T_\infty)$, where $T_1$ is the minimum serial execution time and $T_\infty$ would be the minimum execution time with an infinite (i.e., arbitrarily large) number of processors and no communication delays.  (Another way to look at $T_\infty$ is that it is the critical path through the algorithm.)


Inserting values at maximal distance from current value I have the following problem.
Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules:

If all elements equal 0,set A[0] to 1
Next 1 should be set at maximal distance from any other 1s. At this
stage it will be A[size-1].
In case of equal distances, set 1 at the element with equal distance
AND with smaller index.
At any point of time, any 1 could be set back to 0 at random

Consider an example:

0000000 // initial
1000000 // just first
1000001 // second
1001001
1101001 // all given opportunities have distance 0 to any other 1, so pick up the smallest index
1111001 // again the smallest index
1110001 // we replaced a random 1 with 0
1110101 // at this step we have location with distance 1, so use it!

Input: a sequence of additions/removals of 1s.

Expected output: a sequence of accessed indices at each step.

My question is: how to compute index for a next request? Removals are trivial and it's not interesting (there is some bookkeeping, which is out of the problem's scope), but what about additions? I don't think that you can use dynamic programming or other approaches to compute next index from scratch because of randomized removals.

My idea is to maintain something similar to an interval tree, where each node correspond to 1, left subtree correspond to an interval to the left side, right subtree to right, but it lacks some important details.

Are there any already known approaches/algorithms to this problem? Or how should I proceed with my interval tree idea?

Use an interval tree to store a set of intervals, where you have one interval for each chunk of contiguous 0's.  Now to figure out where to put the next 1, you need to find the longest interval in the interval tree.  You can keep track of the longest interval in the interval tree by augmenting the data structure: store in each node the length of the longest interval under that node.  Each operation can be done in $O(\log n)$ time.


Adding the requirement of linear time on infinitely many inputs into the class $P$ Is the following problem computable in polynomial time?

Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$)

Output: $<M_2>$, encoding of a determinstic TM that runs in polynomial time ($L(M_2)\in P$), and satisfies:

$L(M_1)=L(M_2)$ (they decide the same language)
$\forall n\exists w\in\{0,1\}^n : \text {Time} (M_2,w)=n$ (there exists an input of any length on which the TM runs in linear time)

[EDIT 2]

No, and in particular $M_2$ does not exist in general.

Consider only TM's (and languages) that do not distinguish between the letters $0$ and $1$. Let's call them monochrome. Thus, membership of a word $w$ in a monochrome language depends only on $|w|$. Now let $L$ be a non-regular monochrome language in P. For example, $L$ can be the set of all words whose length is a square number.

Next, we exploit the fact that we use Turing machines (and not RAMs or whatever) and that the time bound is exactly $n$ (and not $O(n)$). In that time bound, all the TM $M_2$ can do on the witness word $w$ (by which I mean the special input of a given length $n$ for which $M_2$ runs in time $n$) is to read the input once from left to right. If at any step it does not go right, it cannot discern the length of $w$. As $L$ is by nature neither finite nor co-finite, $M_2$ must measure the length exactly.

So, at least on the witness words, $M_2$ acts like a DFA. Then, construct an NFA $A_1$ which simulates $M_2$ as long as $M_2$ only goes right. The NFA $A_2$ is obtained from $A_1$ by replacing all edge labels by $\{0,1\}$. Then $A_2$ recognizes $L$: For any input, $A_2$ behaves just like $A_1$ does for the respective witness word, including acceptance or rejection.

Thus, $L$ is regular, contradicting the choice of $L$.


Is there a name for a compiler that runs once at runtime right before a program is executed? I wrote a tiny compiler that is used to execute user-defined plugin code. The compiler is shipped as part of the application. When the user loads a plugin, the compiler runs first (once) and then the emitted code is executed.
I'm trying to describe this project in a blog post, and I'm unsure if calling this a "Just in Time" compiler (JIT) is accurate or not. The Wikipedia article indicates that a JIT typically uses runtime information to inform how/when the program gets compiled, and my project does not do anything that fancy.
Is there a common name for a compiler that executes at runtime but does not analyze the execution of the program?

Nope, it's not a JIT, it is just an ordinary compiler.  There's no special name needed -- it's a compiler.
In this context "run time" means when the program being compiled is in the middle of executing.


Is Dual Graph of a Triangulation of a Polygon Tree? I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the relation with the hole in it?
If anyone could explain it with a polygon contains hole. I would be very happy and thanks in advance.

Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree.

However, is this thing I've drawn here really a polygon? That depends on which definition of "polygon" you use. A polygon is often defined as an area bounded by a single polygonal chain that does not intersect itself. This type of polygon is also known as a simple polygon. Sometimes, we want to talk about generalizations of this simple polygon. A polygon with holes is a connected area bounded by several polygonal chains that do not intersect themselves or with each-other.
So, for this answer, I will define a polygon to be either a simple polygon or a polygon with holes. This means that above, I've shown an example of a polygon with a triangulation of which the dual graph is not a tree. This particular polygon is actually an example of something that holds more generally: the dual of a triangulation of a polygon is a tree if and only if the polygon is simple. (Proof idea: since a polygon is connected, the dual graph of the triangulation is also connected. Observe that the boundary of the polygon is disconnected if and only if the dual graph of the triangulation contains a cycle. Since a tree is defined as a connected acyclic graph, the claim follows.)


Constructing a decider for a language I'm confused about the idea of constructing a decider for a language and i need some help with it.

For example, if i have an enumerator M1 for a language L and another enumerator M2 for the complement of L, how do i construct a decider for L that uses both enumerator M1 and M2?

I understand that i would first introduce a Turing Machine with an input string and simulate it but I'm lost in the next stage of constructing a decider. By the way, enumerators are Turing Machines that outputs a sequence of strings.

Could anyone please explain on how do i construct a decider for the language L that uses both enumerators M1 and M2?

M1 and M2 together will eventually enumerate every possible string. So the trick is to alternate between them. Then you get an enumerator that enumerates all strings. Every time you compare the output string of the enumerator to your input string. At some point they will be equal. Then you just have to look whether you have used M1 or M2 in the last step.

You compute for input string w:

M1(0)=w?, M2(0)=w?, M1(1)=w?, M2(1)=w?, M1(2)=w?, M2(2)=w?,...


Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I keep getting stumped on this particular problem.

We define a question as a string over the alphabet $\{0,1, ?\}$ and say that a question covers all of the strings where substituting ?? with 0s and 1s yields a string such as $0??1$ covers the four strings $0001$, $0011$, $0101$, $0111$.

We have to reduce the 3SAT problem to QUESTION= {A : A is a set of questions, each of length $n$, such that there exists a string $w$ of length $n$ where no question in A covers $w$}. To show that it is NP-complete.

I recognize that some instance of QUESTION will "cover" less than $2^n$ strings but I'm pretty stumped on how to go forward as all of the things I've tried end up not working out.

The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what assignments won't work, and that's the insight you need to do the reduction.

Each clause will be converted into a QUESTION string of length $n$, where $n$ is the number of variables in the 3CNF formula.  Number the variables in the formula from 1 to $n$.  For each clause output a QUESTION string with a 0, 1 or ? in the position of the string corresponding to that variable's number.  Use 1 if the variable is negated in the clause, 0 if it is not negated and ? if it does not appear in the clause at all.

Example: the 3CNF formula has seven variables ($x_1$ ... $x_7$) and there is a clause ($x_1 \lor \lnot x_4 \lor x_7$) you would output the QUESTION string 0??1??0 .

Once all the clauses are converted to QUESTION strings, any $w$ string not covered by the QUESTION strings can be directly converted to a satisfying assignment for the 3CNF formula.  As in the QUESTION strings each position in $w$ corresponds to previously numbered variable.  But in $w$ each 0 represents a variable that should be negated in the satisfying assignment, and each 1 represents a variable that should not be negated.


What is the relation between an algorithm and its implementation at the level of code? Is there any isomorphism or equivalence relation? What strictly bind these two together?

An algorithm is a method for performing some task; an implementation is an expression of that method in a particular language.


Radix sort and changing bases I have recently learned about radix sort.
I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort.
Radix sort runtime is $O(d(n+k))$ where $d$ is the number of digits in the numbers, and $k$ is the base.
So shouldn't there be a permanent ratio between $d$ and $k$ so that the runtime is optimized?
How should I choose the base in any other way?

The asymptotic runtime ignores access times for the digits.  On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number.

If you have multiple CPUs, you can more easily exploit parallel processing by using a larger base.  The large base will spread the numbers across many buckets which can then be sorted in parallel.

Another reason to change bases is if you know your data has a bias (such as Benford's Law) that would cause the numbers to initially cluster into only a few buckets.


Count numbers less than $x$ co-prime to $p$ We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.

I know that we can solve the problem in $O(x\log x)$ with iterating over all numbers less than $x$ and check if their greatest common divisor is $1$.

Is there any way to solve this faster, because I think that we can reduce this somehow. Please give some hints on where to start working.

There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those floor ((x-1) / p) are divisible by p, so exactly (x-1) - floor ((x-1) / p) are co-prime with p. For simplicity, let f(n) = floor ((x - 1) / n), then for a prime p the result is f (1) - f (p).

If p has two prime factors a, b, then we would start with f(1) - f(a) - f(b) - take all numbers, except those divisible by a, except those divisible by b. But here is a mistake: Numbers divisible by ab have been removed twice, so we add them back: f(1) - f(a) - f(b) + f(ab).

For three prime factors a, b, and c, we use the same scheme and start with f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc). Numbers divisible by abc have been removed three times, added back three times, and therefore need to be subtracted once, giving f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc) - f(abc).

You can continue this. You'll have to figure out yourself what exactly to add or subtract. With k different prime factors, you have 2^k terms - but clearly with 10 different prime factors, and say x = 1,000,000, you have only 1024 different terms. Also, as soon as a product is greater than x, you can ignore it. For example, all prime factors ≥ x of p can be completely ignored. And all duplicate prime factors can be ignored.

Actually, the number of different prime factors grows very slowly, so this method is quite good unless x is small.

How many numbers less than a billion are co-prime with $10^{100}$? Prime factors of $10^{100}$ are 2 and 5, so the answer is 999,999,999 - 499,999,999 - 199,999,999 + 99,999,999 = 400 million.


Simple Recognition Algorithm, How Does It Work? I am trying to understand how a simple image recognition of an image with dynamic size could work. What I have seen is that parts of the images are taken and evaluated. For example a simple finger recognition could be done turning the image grayscale, taking parts of the image and evaluating them. What I understand is how these parts are evaluated and how this could be done on an image with dynamic size ratio. Is a kernel function needed, or how do you proceed when you take the different parts of an image?

Normally we build a classifier that accepts images of a fixed size: say, 100x100 pixels.  Given an image that is larger than that, we re-scale it to 100x100 pixels before feeding it into the classifier.

This is often combined with other techniques to locate where in a larger image the object is located.  For instance, if you want to detect the presence of a bus in a picture, you build a classifier that recognizes a picture of a bus (where the bus fills the frame).  Then, given a picture that might contain a bus and other stuff, you try cropping out different rectangles from within the image and feeding each one to the classifier.  There are other more sophisticated techniques as well based on deep neural networks and regression.

To learn more, I suggest you read about object detection and object recognition.  There's lots written about the subject in the research literature, and there are excellent tutorials available online.  The state-of-the-art methods use deep neural networks.


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

Model of computation is RAM.

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

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

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


Query regarding Integer factorization Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$.

For some (unknown) power $x$ we know the corresponding residue ($R_x$), i.e.:

$b^x\bmod P = R_x$.

Query 1: Without knowing (or calculating) the factorization of $P$ and value $x$, for a given $k$, (using $R_x$) is it possible to calculate $b^{(x-k)}\bmod P = R_{(x-k)}$ efficiently?

Query 2: Can the above procedure (if known/exists) help in factorization of $P$?

I am uncertain about how to achieve 1 and its relation to factorization if any.

You can calculate $b^k \bmod P$ efficiently for $k \geq 0$ using repeated squaring. There is no need to know the factorization of $P$. Furthermore, you can calculate $b^{-1} \bmod P$ (if it exists) efficiently using the Euclidean algorithm. This also doesn't require the factorization of $P$.


Computational indistinguishability for any distribution using a Chernoff bound I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. This is the statement:
For any distribution $D$ over  $\{0,1\}^{n}$, there exists a distribution $D'$ such that $D$ and $D'$ are $\epsilon$ indistinguishable with respect to any classical distinguisher of size $n^{k}$.
Let me restate the proof.

Let $D$ be any distribution over $\{0,1\}^{n}$. Then choose $w$ elements
independently with replacement from $D$, and let $D′$ be the uniform
distribution over the resulting multiset (so in particular, $H(D′) \leq
 \log_{2} n$). Certainly $D′$ can be sampled by a circuit of size $\mathcal{O}(nw)$: just
hardwire the elements. Now, by a Chernoff bound, for any fixed circuit
$C$, clearly $D$ and $D′$ are $\epsilon$-indistinguishable with respect to $C$, with
probability at least $1 − e^{-\epsilon^{2} w}$ over the choice of $D′$. But there
are “only” $n^{\mathcal{O}(n^{k})}$ Boolean circuits of size at most $n^k$. So by the union
bound, by simply choosing $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$, we can ensure that $D$ and $D′$ are $ε$-indistinguishable with respect to all circuits
of size at most $n^{k}$, with high probability over $D′$.

I do not understand how the Chernoff bound is applied. How do we know the action of the circuit $C$? I also don't understand why $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$ in the union bound. Since we need to "protect against" $n^{\mathcal{O}(n^{k})}$ Boolean circuits, shouldn't $w$ be something like $w = \Omega\left(\frac{n^{\mathcal{O}(n^k)} \log n}{\epsilon^2}\right)$?

How the Chernoff bound is applied
What does it mean for $D$ and $D'$ to be indistignuishable by a circuit $C$? It means that
$$
|\Pr_{x \in D}[C(x) = 1] - \Pr_{x \in D'}[C(x) = 1]| \leq \epsilon.
$$
Let $x_1,\ldots,x_w$ be the sampled elements. Then
$$
\Pr_{x \in D'}[C(x) = 1] = \frac{X_1 + \cdots + X_w}{w},
$$
where $X_i$ is the indicator of $C(x_i) = 1$. If we sample $x_1,\ldots,x_w$ at random, then $X_1,\ldots,X_w$ are independent Bernoulli random variables whose expectation is $\Pr_{x \in D}[C(x) = 1]$. Chernoff's bound shows that their average is concentrated around their expectation.
Applying the union bound
The probability that a choice of $x_1,\ldots,x_w$ is bad for a specific circuit $C$ is $e^{-\epsilon^2 w}$. The probability that a choice of $x_1,\ldots,x_w$ is bad for one of $N$ different circuits is at most $Ne^{-\epsilon^2 w}$. Hence if $Ne^{-\epsilon^2 w} < 1$, the probability that a choice of $x_1,\ldots,x_w$ is good to all $N$ circuits is positive, hence there exists such a choice which is good to all $N$ circuits.
Since $w$ is in the exponent, the minimal $w$ needed to satisfy $Ne^{-\epsilon^2 w} < 1$ scales only logarithmically in $N$.


Converting 4 variable if else condition to Linear integer program There are four variables: $x_1, x_2, x_3, x_4$.
If you choose either $x_3$ or $x_4$ or both — then you should choose exactly one of $x_1$ or $x_2$.
If you choose neither $x_3$ or $x_4$ — then there is no restriction in choosing $x_1$ or $x_2$.
I have come up with the following if else logic for this, but cannot proceed from there.

If $x_3+x_4 = 0$ then $x_1 + x_2 \ge 0$
If $x_3 + x_4 \ge 1$ then $x_1 + x_2 = 1$

Can you let me know how to come up with an integer linear program with this understanding?

Every logical formula can be converted to conjunctive normal form (CNF), that is, into a conjunction (AND) of clauses (OR). In turn, a clause $\ell_1 \lor \cdots \lor \ell_m$ can be expressed as the constraint $\ell_1 + \cdots + \ell_m \geq 1$. In this way, you can express any logical condition in an integer program.
As an example, consider the logical formula $x \oplus y$, that is, exactly one of $x,y$ is true. While it can be expressed directly as $x + y = 1$, let's see how to do it using CNF. Putting it into CNF, we get $(x \lor y) \land (\lnot x \lor \lnot y)$. Therefore we add the following constraints: $x + y \geq 1$ and $(1-x) + (1-y) \geq 1$, i.e., $-x-y \geq -1$.


What exactly is going on in a proof by induction of a recurrence relation? In CLRS, it works through an example going through a recurrence relation proof using the "substitution method".

We have the recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + n \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \   (4.19)$$

It claims:

  We guess that our solution is $T(n) = O(n \lg(n)).$

We assume that $T(m) \leq cm\lg(m)$ for all $m < n$ (in particular, for $m = \lfloor(n/2) \rfloor$, and need to show that $T(m) \implies T(n).$

I'm fine with this; this seems like a standard case of strong induction, but what I don't understand is the explanation of the base case (which we also need to prove):

Could someone explain this paragraph to me?
More specifically:

What are boundary conditions?
How do we know the base case? We're only given $T(n)$ recursively; there's no initial case when $n$ is, for example, $1$. How, then, do we know that
"$T(1) = 1$"?
I don't understand what the paragraph is getting at.  How do we determine the base case in the general case?

Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof; that is, they assume the inductive hypothesis, and prove that (for all $m<n$), $T(m) \leq \text{something} \implies T(n) \leq \text{something}$, but they leave it at that, as though that were sufficient for the proof.
In fact, these proofs don't even explicitly state the inductive hypothesis. For example, in the case of (4.19), they would write something like:
$$ \begin{align} T(n)  \leq c\lfloor( n/2) \rfloor \lg(\lfloor n/2\rfloor) \end{align} \\  \leq \ ... \\ \leq cn\lg(n) \ .$$

Is this acceptable, or would that constitute a sloppy proof?

What are boundary conditions?

Given a recurrence/function $f$ boundary conditions are simply a few points, usually small points such as 0,1 or 2, at which $f$ is specified. For example, in the Fibonacci sequence $$F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1$$
$F(0),F(1)$ are boundary conditions. In other words initial conditions, base conditions.

The excerpt you posted proves the upper bound for the recurrence relation $2T(\lfloor n/2 \rfloor) + n$. It is done using substitution method for solving recurrence relation where you first guess the solution (involving constant(s)) and then find constant(s) that would satisfy boundary conditions.

After you guessed the solution you get an explicit (as in your example) equality/inequality of the form $T(n) \leq cg(n)$ which you have to prove in order to establish the upper bound for the recurrence relation $T(n)$. That is usually done using induction. However, the original boundary conditions may fail when you use it with your guessed function $g(n)$ like in the example: $T(1) = 1$, but $c\log(1) = 0$. At this point you should kind of select new boundary conditions (initial points) to prove the inequality $T(n) \leq cg(n)$. Without base step you cannot complete induction proof.

So the example "overcomes this obstacle" by choosing a new value $n_0$ for the inductive proof. However, $T(1) = 1$ is still kept but it is removed from the inductive proof. The example then introduces new boundary conditions $T(2)$ and $T(3)$ instead of $T(1)$. Given $T(1)= 1$, we have $T(2)= 4$ and $T(3)=5$ and so for some constant  $c \geq 2$ the following conditions hold $T(2) \leq c2\log(2)$, $T(3) \leq c3\log(3)$.

Now you can prove that $T(n) < cn\log(n)$ using induction by taking base step $n=2$ and $n=3$ ($n \geq 2$).

  How do we know the base case?

If base case (boundary conditions) of the original recurrence relation fails, you can just remove them from the new equation/inequality and introduce new base case for which the equation/inequality holds.

  I don't understand what the paragraph is getting at.

This paragraph is just one simple example demonstrating how a new substitution function fails at the original boundary conditions and how to overcome that problem.

  How do we determine the base case in the general case?

There is no a standard way to do that, use you intuition, guess, and check if it works. You should choose your boundary conditions carefully. In the example you in your post $T(2)$ and $T(3)$ are chosen as new boundary conditions since values of $T(2)$ and $T(3)$ directly depend on the value of $T(1)$ which is troublesome. So we just put $T(2)=4$ and $T(3)=5$ without using $T(1)$.

Making a good guess

  Unfortunately, there is no general way to guess the correct solutions
  to recurrences. Guessing a solution takes experience and,
  occasionally, creativity. Fortunately, though, you can use some
  heuristics to help you become a good guesser.

  Is this acceptable, or would that constitute a sloppy proof?

This inequality should be proven. Assume that our claim is true for all integers less than or equal to $n$. We need to show that the inequality is true for $n+1$.

$$ T(n+1) = 2T((n+1)/2) + (n+1) \leq 2c\frac{n+1}{2}\lg{\frac{n+1}{2}} + (n+1) = c(n+1)\lg{\frac{n+1}{2}} + (n+1)=(n+1)(c\lg{\frac{n+1}{2}} + 1) \leq (n+1)(c\lg{\frac{n+1}{2}} + c) = c(n+1)(\lg{\frac{n+1}{2}} + 1) = c(n+1)(\lg{\frac{n+1}{2}} + \lg2) = c(n+1)\lg{(n+1)}$$


Find a minimum-weight perfect b-matching, where b is even How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?

A minimum-weight perfect b-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly b edges from M.

A subgraph in which each vertex has degree exactly $b$ is known as a $b$-factor. You are asking for something similar (but not identical) to the minimum weight $b$-factor.

Tutte showed how to reduce minimum weight $b$-factor to minimum weight perfect matching in his paper A short proof of the factor theorem for finite graphs.

We will split each vertex $v$ of degree $d(v)$ into $2d(v) - b$ vertices: $v_1,\ldots,v_{d(v)},v'_1,\ldots,v'_{d(v)-b}$ (we can assume that $d(v) \geq b$, since otherwise the graph has no $b$-factor). We lift each edge $(x,y)$ to an edge $(x_i,y_j)$ of the same weight in such a way that each $x_i$ and $y_j$ participates in exactly one such edge. We furthermore connect each $v_i$ to each $v'_j$ with a zero-weight edge, for all $i \in [d(v)]$ and $j \in [d(v)-b]$.

Each $b$-factor of the original graph corresponds to a matching in the new graph of the same weight. Indeed, lift the $b$-factor to the new graph, and for each vertex $v$, add an arbitrary matching between $v'_1,\ldots,v'_{d(v)-b}$ and the $d(v)-b$ new vertices corresponding to "unused ports".

Conversely, we can convert every matching in the new graph to a $b$-factor of the same weight in the original graph by undoing this construction.


Is it computable if a particular number follows the Collatz conjecture? I was attempting to write a computer algorithm to determine if a particular number breaks the Collatz conjecture.  It is very easy to determine if a particular number falls into a loop, however I cannot think of any way to determine if a particular number is on an infinite divergent trajectory.

Is it Computable to determine whether or not a particular number is on an infinite trajectory?

In short: we don't know :-)

There is a ((very) little) chance that the Collatz sequence is Turing complete (with probably some caveats like in the case of Two-counter Machines); i.e. there is an algorithm which for every turing machine $M$ outputs an $x$ such that:

$Collatz(x)$ is on a divergent trajectory if and only if $M$ doesn't halt on empty tape

in other words "deciding if a particular Collatz trajectory is divergent" could be undecidable.


Are references of any use without updating? Almost all type-theoretical treatments of references that I've studied introduce references as accompanied with at least three operations (sometimes including the fourth):

Construction (allocation): $ \text{ref } e $
Elimination (dereferencing): $ !e $
Updating: $ e_1 := e_2 $
(not as common) Destruction (deallocation): $ \text{free } e $

My question is this: Would references be of any use without updating (construct #3 above)? If so, what would be a common use? Does the ability to use updates with references lend any more "power" to a language? You can answer assuming either the presence or absence of construct #4 above; if it affects your answer, please explain how.

References are useful even if you don't update the object, since copying objects takes memory and time. When passing a reference, only a pointer is passed. But suppose that you were passing a string - it could take far longer to copy the entire string. This is why language like C++ support constant references, which are references that cannot be updated.


Edge-disjoint paths in trees How do I prove the following proposition?

Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x_i,y_i)$ such that the paths $x_i-y_i$ are edge-disjoint.

Here are some ideas:

Suppose that $\ell$ is a leaf of $T$ which doesn't belong to $S$. Then we can safely remove $\ell$.

Suppose that $\ell$ is a leaf of $T$ which does belong to $S$. If its unique neighbor is also in $S$, then we can safely pair them up.

Suppose that $\ell$ is a leaf of $T$ which belongs to $S$, but its unique neighbor $r$ doesn't belong to $S$. We can safely remove $\ell$ and replace it in $S$ by $r$.

(How to implement these ideas efficiently is a different matter, but for an existence proof these ideas suffice.)


How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $ I am trying to answer this question:
$3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$

My question is how to solve this question.

Here is what I have tried so far:

I applied the definition $3x^3 + 2x + 1 > c \cdot x\log x$ for all c, given $n \geq k$, for some k

I tried to apply the technique of applying the equality that:
$n < n^3$

Since n is less than the highest order term we can just move all terms to order n ??

Giving $6x < c \cdot x \log x$

Then you can choose:
$k < 2^\frac{6}{c}$

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$.

$$
\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} =
\lim_{x \to \infty} \frac{3x^3}{ x \log x} =
\lim_{x \to \infty} \frac{3x^2}{  \log x} =
\lim_{x \to \infty}  6x^2
= +\infty.
$$