How to expand 2D graphic and functions to 3D? So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D.

I want to expand the 2D objects and functions to 3D which I don't expect to be too difficult, but still difficult enough that I don't want to reinvent the wheel.

  What is the process of migrating 2D to 3D algorythms called in
  computer engineering? And of course the follow-up question, if there
  is nothing on the web for that search term: What's it called in
  everyday computer engineering? Are there general concepts how best to
  expand a set of 2D-algorithms and -objects to 3D at all?

In most 3D graphics pipelines (e.g., OpenGL) points and direction vectors are represented with 4D homogeneous points (x, y, z, w) and their respective transformations are stored as 4x4 matrices. We can use the same representations for 2D and treat the z-value as the "stacking order" of our 2D shapes.

For example, for a 2D CW rotation about the origin we can use a 3D rotation about the z-axis:

       _                               _
      | cos(angle)  -sin(angle)  0   0  |
  M = | sin(angle)   cos(angle)  0   0  |
      |    0             0       1   0  |
      |    0             0       0   1  |
       -                               -

So to rotate a 2D point (x,y) about the origin we simply compute

  M * [x, y, 0, 1]^T

With 2D geometry we simply perform a orthographic projection into the rectangular region we wish to view. The pipeline is already designed to sort objects by their z-value for hidden-surface removal so defining a stacking order of 2D objects is trivial with the machinery in place.

Making the jump to 3D is a matter of generalizing the geometry and transformations with the added dimension. All of the usual affine transformations (rotation, scale, translation, shear, ...) generalize in a very simple way.

The biggest new concepts in 3D  is setting up a virtual camera (defined by a simple affine view matrix)  and you now have to project your 3D geometry down to 2D to create an image -- this can be done using parallel or perspective projections. Perspective projections require perspective foreshortening based on distance from the camera -- we can make very clever use of the homogeneous representation and a division by z to pull this off. This is standard material for most introductory graphics textbooks / courses.

Anyway, there's a start....


Are non-trivial sets formed by set operations on NPC sets still in NPC? I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union.  However, the answer used languages which form trivial languages under these set operations and trivial languages are of course not NP-complete.  If the intersection or union is non-trivial, does the result still hold?  Also, I'm also wondering about the Cartesian product of two NP-complete languages since that is another set operation.

Non-trivial sets formed from the unions and intersections of NP-complete sets are also not
necessarily NP-complete (of course this is all under the assumption
that P != NP).

Let $L$ be a NP-complete language, $A$ be any set in P, and $B:=
{\{0,1\}}^*$.  Then the following sets are all NP-complete since they
are just the disjoint unions of a sets based on $L$, $A$, and $B$.

$L_1 := 00L \cup 01A$

$L_2 := 11L \cup 01A$

$L_3 := 01L \cup 10B$

$L_4 := 10L \cup 01B$

Then $L_1 \cap L_2 = 01A$ and $L_3 \cup L_4 = 01B \cup 10B$
These results are both in P and and non-trivial sets.

On the other hand, as mentioned in a comment above, the Cartesian
product of two NP-complete sets is always NP-complete:  If $X$ and $Y$
are two NP-complete sets  then $X \times Y$ is in NP since a
NP-witness for $(x,y) \in X \times Y$ is simply a witness for $x \in
X$ along with a witness for $y \in Y$.  Furthermore, the map $x
\rightarrow (x,y_0)$ is a polynomial time reduction from $X$ to $X
\times Y$ where $y_0$ is a fixed member of $Y$.


Conceptual overview: Self-information, Mutual information, uncertainty, entropy I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x_i, y_i$  as events of experiments $X, Y$.

Self-information, denoted as $I(x_i)$
Mutual information, denoted as $I(x_i; y_i)$
Uncertainty (which is closely related to self-information and/or mutual information, I believe).
Average mutual information, denoted as $I(X, Y)$.
Entropy, denoted as $H(X)$, which is average self-information, I believe.

Next, there are a couple of "conditional ..." defined.

Can you sketch a compact overview of these concepts and how they relate, all intuitively?

Trying to answer the question myself, with my textbook at hand. So far, I am here:

Self-information of an event: uncertainty of an event.
$$I(x_i) = \log \frac{1}{P(x_i)} = -\log P(x_i)$$
Self information of a vector event:
$$I(x_i y_i) = -\log P(x_i,~y_i)$$
Mutual information between two events: the information one event (experiment outcome) gives us about the other event:
$$I(x_i;y_i) = \log \frac{P(x_i,~y_i)}{P(x_i) P(y_i)}$$
$$I(x_i y_i) = I(x_i) + I(y_i) - I(x_i; y_i)$$
Uncertainty: the formula of it is the same as self-information of an event. So I'll assume they are the same.
Average mutual information: The information one gives about the other when observer the former. Clumsy notation:
$$I(X; Y) = E[I(x_i; y_i)]$$
Entropy: the average amount of information that is revealed by observing an event. (I know the relationship to Huffman coding here.) Clumsy notation:
$$H(X) = E[I(x_i)]$$
Conditional entropy: the amount of information (about $X$) that is left to be discovered after observing the given ($Y$).
$$H(X|Y) = H(X) - I(Y;Y)$$

\begin{align}
I(X; Y) &= H(X) - H(X | Y) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}

Conditional self-information: the information that is contained within the outcome of a certain event ($x_i$), after already knowing the outcome of another event ($y_i$).
$$I(x_i | y_i) = -\log P(x_i | y_i)$$
Relations:
$$I(x_i | y_i) = I(x_i) - I(x_i; y_i)$$
\begin{align}
I(x_i; y_i) &= I(x_i) - I(x_i | y_i) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}


A 2D Layout Algorithm for Small, Sparse, and Undirected Graphs with a Specific Edge Length I would like to to draw a graph where every edge $e_m$ has a predefined length of $l$. Given that the graph is small and sparse, it should be feasable. However, I did not manage to find an algorithm which does this (or one that is suitable to modify) yet I'm sure that this is a solved problem. Does anyone know of such a layout algorithm and could point me to an implementation or paper?

"Planar Embeddings of Graphs with Specified Edge Lengths" by Cabello, Demaine, and Rote (or one of the references they cite) seems to solve your problem.

If you don't care about edges crossing too much, a simple heuristic approach could be gradient descent. Start with a random position and iteratively wiggle the nodes a bit to decrease the sum of differences of the current edge lengths to your desired lengths.


Computational complexity of generating a random vector I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not sure if my understanding is correct.
I want to know the complexity of generating a uniform random vector, over $[0, 1]$, of size $N$ using say a random number generator in Python or Matlab.
Is it $\mathcal{O}(N)$ cause I'm generating $N$ random numbers and the complexity of generating each one of them is $\mathcal{O}(1)$ or is it simply $\mathcal{O}(1)$?

You can't create a uniformly random number in $[0,1]$ in finite time, because that would require infinite precision.
Probably that's not what you want.  Probably you want to generate a random float in the range $[0,1]$.  Then we have to ask what assumptions you are willing to make about your pseudorandom number generator. For many of them it is probably reasonable to treat generating a random float in that range as taking $O(1)$ time.  If so, you can create a $N$-dimensional vector with $N$ calls to that pseudorandom generator, i.e., in $O(N)$ time.
See How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Is there a system behind the magic of algorithm analysis? and a good textbook for an overview of asymptotic running time analysis.


Understanding commutativity and associativity for primitive types In Elements of Programming Interviews, authors talk about a tip for understanding how to use primitive types (int, double, etc).

  Be aware that commutativity and associativity can be used to perform operations in parallel and reorder operations.

I'm having trouble even imagining what these means in the context of bits. For anyone who better grasps what this means, could you explain it and flesh it out with some examples?

Consider the following code:

  a = (b + c) + d

  e = c + (b + f)

Using associativity and commutativity, we can improve it to

  t = b + c

  a = t + d

  e = t + f

This uses one less addition. Since integer addition (ignoring overflow) is guaranteed to be commutative and associative, an optimizing compiler is allowed to use this optimization. The same isn't quite true for floating point addition, which is not associative.


Do there exist algorithms for which the Big-O cannot be found out? Just out of curiosity:

Do there exist algorithms for which the Big-O cannot be found out?

I have done a quick search in the google search bar:
"Big o, impossible to evaluate"
"algorithms without big o"

And these gave results which were unsatisfactory. Mostly, teaching me how to find the big o. Nothing I haven't learned earlier.

On a side note, it is my understanding that finding the big o requires us to assume the worst possible case. But, is that always a correct metric for efficiency? What is the likelihood a function is called with the worst possible argument?

There are some algorithms for which, as of today, we are not able to prove termination, much less to bound complexity.

A simple case is given by the Collatz function: in pseudocode

function Collatz(n):
  if n <= 1  then return 1
  if even n then return 1 + Collatz(n/2)
  return 1 + Collatz(3*n + 1)

It is believed that, for any natural $n$, Collatz(n) will eventually stop recursing. However, we do not know whether this is is the case. Consequently, we also do not know an upper bound for the time complexity of this algorithm.


Understanding lexical grammar for multi-line comments in JavaCC I'm struggling to understand why this piece of lexical grammar works for multi-line comments in JavaCC (posted here):

 "/*" (~["*"])* "*" (~["*","/"] (~["*"])* "*" | "*")* "/"

As I read it, the parser scans the input /*, and then zero or more optional occurrences of * can appear, followed by a *, and then zero or more optional occurrences of * and /, then zero or more occurrences of * followed by * or *, ended by a /. Specifically, this part boggles my mind:

 (~["*","/"] (~["*"])* "*" | "*")*

I'd appreciate some help understanding this.

Let's write this in a more manageable way. I'll use $x$ for any symbol other than $/$ and $*$. Your expression is
$$
/* (/+x)^* * (x(/+x)^** + *)^* /
$$
Now let us apply the following identity to the part "$*(x(/+x)^**+*)^*$":
$$
r(sr)^* = (rs)^*r
$$
We get
$$
/* (/+x)^* (*x(/+x)^*+*)^* */
$$
It's clear what the outer parts $/*$ and $*/$ do, so let's focus on the inner part
$$
(/+x)^* (*x(/+x)^*+*)^*
$$
which captures all strings not containing the substring $*/$. Using the identity
$$
(rs+r)^* = (r^+s)^*
$$
we can simply it to
$$
(/+x)^* (*^+x(/+x)^*)^*
$$
Essentially, each run of stars is "guarded" by a following $x$.


Is the BPP class closed for union and intersection? Just like the title says. I want to prove that given two languages $L_1,L_2 \in BPP$, $L_1 \cup L_2 \in BPP$ and  $L_1 \cap L_2 \in BPP$

Let $T_1$ (resp. $T_2$) a polynomial-time probabilistic Turing machine with error probability of at most $1/3$ for $L_1$ (resp. $L_2$).
Let $T'_1$ (resp. $T'_2$) be a Turing machine for $L_1$ (resp. $L_2$) obtained by running $T_1$ (resp. $T_2$) $9$ times and returning the majority result.
The error probability of $T'_1$ (resp. $T'_2$) is at most $p_F = \sum_{i=5}^9 \binom{9}{i} (1/3)^i (2/3)^{9-i} < \frac{1}{6}$.
A Turing machine for $L_1 \cup L_2$ (resp. $L_1 \cap L_2$) simulates $T'_1$ and $T'_2$ and accepts if and only if at least one of (resp. both of) $T'_1$ and $T'_2$ accept.
By the union bound, the probability of error of this Turing machine is at most $2 \cdot p_F < 2 \cdot \frac{1}{6} = \frac{1}{3}$.


$ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular Consider the alphabet $\Sigma = \{0, 1, +, =\}$ and the language $ADD = \{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\}$.

This is the (informal) solution I came up with (not sure about its correctness).
Using the pumping lemma:

Take $s= 1^p=0+1^p$, $s \in ADD$. $s$ can be divided into three parts so that $s=xyz.$
The pumping lemma says that $|xy| \leq p$ and $|y| > 0$ so $y$ must be in the first $p$  $1's$. Choose $i=0$. Then the equation is false, so the languge $ADD$ is not regular. $\square$

Even though I think this is correct, in the answers they use the string $1^p=10^{p-1}+1^{p-1}$ which is also a correct pick, is mine just another correct pick?

Your answer has a slight omission: If perchance $y$ is of length $p$ (note: $x$ is permitted to be empty), then choosing $i=0$ leaves one with, not a false equation, but no equation (the string begins with '=').  But of course the conclusion is the same.  You can avoid that nit by choosing $i=2$ (say) instead of $i=0$.

And yes, I think yours is just another correct pick.


Proof of correctness of A star search algorithm I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm looking for a proof that if the heuristic is admissible, A* will always give an optimal path.

Please help me understand.

To clarify, I want a proof that the path found by A* is correct (i.e., is the cheapest/shortest path to the destination), not a proof that the A* algorithm is optimal (i.e., that any other algorithm that uses the same heuristic will expand at least as many nodes as A*).  Also, I'm looking for a proof that only uses the assumption that the heuristic is admissible (without assuming that the heuristic is monotonic or consistent).  I've looked in CLRS and haven't found any such proof.

Check the original paper which talks about its correctness -

Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.

See especially Section II and Theorem 1.


Prove this language is non-regular I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated.

Prove using the Pumping Lemma that the following language is not regular.
{0^n^3 |n ≥ 0 is an integer}

From my understanding a language isn't regular if the power is linear. But I just cant get my head around using the Pumping Lemma to prove this even after reading other examples of Pumping Lemma.
I think most expressions require you to split them into seperate parts, but I just dont understand how this is possible for this expression.

Your language could be rewritten more clearly as:

$\{ a^m \mid m \text{ is a perfect cube} \}$

Now you'd have to find a word from this language, longer than the pumping length $p$, that can not be pumped. We choose as a candidate: $a^{p^3}$.
We name our three substrings $x, y, z$, which must be of the form:
$x = a^i$
$y = a^j$
$z = a^{(p^3 - i - j)}$

The pumping lemma restricts $j$ to be greater than $0$ and $i + j \le p$. It's sufficient to show that there exists at least one integer $k \ge 0$, such that $xy^kz$ is not a valid word in the language. Because of our separation, we need to find a $k$ such that $p^3 + (k - 1)j$ is not a perfect cube.
Let's say $k = 2$, which gives us $p^3 + j$, strictly increasing with respect to $j$, having a maximum value of $p^3 + p$.
We also know that the smallest perfect cube larger than $p^3$ is $(p + 1)^3 = p^3 + 3p^2 + 3p + 1$.

Because $p^3 \lt (p^3 + p) \lt (p+1)^3, \forall p \gt 0$, our pumped string's length can't be a perfect cube (because it's strictly between two consecutive perfect cubes).

So the language contains at least one word longer than the pumping length that can't be pumped, which means the language isn't regular.


Data structure for finding max, inserting and deleting in O(1) and O(n) space This is an interview question. I need to implement a data structure that supports the following operations:

Insertion of an integer in $O(1)$
Deletion of an integer (for example, if we call delete(7), then 7 is deleted from the data structure, if the integer 7 exists in it) in $O(1)$.
Return maximum integer in the data structure (without deleting it) in $O(1)$.

You can also use up to $O(n)$ space.

I thought of something similar to this question, but here we have $O(\mathrm{log}\ n)$.

Do you know how can we implement these operations in $O(1)$?

Edit: forgot important thing - you can assume the numbers that will be inserted are integers in the range $[0,n]$.

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data structure must take $\Omega(n\log(n))$ (like sorting, in general, can't be done better than $n\log(n)$. Hence, you might have some constraint on data).
Also, as deleting is in $O(1)$, means it must be found. Hence, Searching and Finding is in $O(1)$.

Therefore, you must know the position of each value (something like counting sort, but with this constraint that $max <= n$ to take the $O(n)$ space!). Hence, you can act like a counting sort by saving the max value in a variable besides the array, by accepting some constraint on data (not in general).


Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge? Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing the mapping between the graphs G and H or releaving the cycle in H.

It is said that we prove that that we know a hamiltonian cycle in G without revealing it.

But this assumes the verifier does not have unlimited computational power. If he had it, he could ask to reveal the cycle in H, and use his unlimited computational power to work out the isomorphism. I understand that if the verifier had unlimited power, he could find the cycle in G directly. But that's not my point. What I find strange is that we are relying on "hard problems" in the proof itself.

Are there ZKP protocols that do not rely on hard problems? Hard problems are only hard according to the state of the art. It is not proven that NP is not P, therefore, in my mind, this sounds like security through obscurity in some sense.

One of the most basic assumptions in cryptography is the existence of hard problems, even on a very conceptual level. For example, to establish a secure communication channel, you want your cipher to impose problems on eavesdroppers which they cannot solve.

The problem is that the existence of hard problems generally has (severe) impact to questions in complexity theory. The most attractive problems for cryptography are those in $\mathsf{NP}$, in particular because, assuming $\mathsf{NP}$ has intractable problems, these have nice asymmetrical properties: Although you can verify a solution efficiently, it is infeasible to find one. However, establishing intractable problems in $\mathsf{NP}$ necessarily entails proving $\mathsf{P} \neq \mathsf{NP}$.

Furthermore, some cryptographic primitives imply the existence of hard problems even without basing on the hardness of a particular problem. For example, the existence of one-way functions, which are essentially the most basic cryptographic primitive, implies $\mathsf{P} \neq \mathsf{NP}$. We also know one-way functions exist if and only if PRNGs exist, so it is clear one-way functions are not an isolated case (whose existence is hard to establish). Also, asymmetric cryptography implies the existence of either of these primitives. (Read more on Impagliazzo's five worlds if you are interested in these issues.)

Modern cryptography is highly dependent on complexity theory for its assumptions. Since that is the case anyway, it only seems natural to embrace the conjectures of complexity theory too.


Fast algorithm for clustering groups of elements given their size/time I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can.

I would like to cluster files into the specified number of groups, where each groups size (= the sum of sizes of files in this group) is as close as possible to each other group in this cluster (but not in other clusters). Here are the requirements:

The first group always contain one file, which is the biggest of all groups in the cluster.
Any other group but the first can have multiple files in it.
The number of groups in each cluster is constrained to a maximum specified by user (but there can be less groups if it's better or there's not enough files).
There's no constraint on the number of clusters (there can be as little or as many as necessary).
Goal (objective function): minimize the space left in all groups (of all clusters) while maximizing the number of groups per cluster (up to the maximum specified).

The reason behind these requirements is that I am encoding files together, and any remaining space in any group will need to be filled by null bytes, which is a waste of space.

Clarification on the objective and constraints that follow from the requirements and the problem statement:

Input is a list of files with their respective size.
Desired output: a list of clusters with each clusters being comprised of groups of files, each group having one or several concatenated files.
There must be at least 2 groups per cluster (except if no file is remaining) and up to a maximum of G groups (specified by user).
Each file can be assigned to any group whatsoever and each group can be assigned to any cluster.
The number of clusters can be chosen freely.

Here is a schema that shows one wrong and one good example of clustering schemes on 5 files (1 big file, and 4 files of exactly half the size of the big file) with a number of groups = 2:

The solution needs not be optimal, it can be sub-optimal as long as it's good enough, so greedy/heuristics algorithms are acceptable as long as their complexity is good enough.

Another concrete example to be clear: let's say I have this list of 10 files with their sizes, this is the input (in Python):

['file_3': 7,
'file_8': 11,
'file_6': 14,
'file_9': 51,
'file_1': 55,
'file_4': 58,
'file_5': 67,
'file_2': 68,
'file_7': 83,
'file_0': 85]

The final output is a list of clusters like this (constrained here to 3 groups per cluster):

{1: [['file_0'], ['file_7'], ['file_2', 'file_6']],
 2: [['file_5'], ['file_4', 'file_3'], ['file_1', 'file_8']],
 3: [['file_9']]}

And for example here (this is not a necessary output, it's just to check) the total size of each groups (ie, sum of file sizes for each group) for each cluster:

{1: [85, 83, 82], 2: [67, 65, 66], 3: [51]}

If the problem is NP-complete and/or impossible to solve in polynomial time, I can accept a solution to a reduction of the problem, dropping the first and fourth requirements (no clusters at all, only groups):

Here is the algorithm I could come up with for the full problem, but it's running in about O(n^g) where n is the length of the list of files, and g the number of groups per cluster:

Input: number of groups G per cluster, list of files F with respective sizes
- Order F by descending size
- Until F is empty:
    - Create a cluster X
    - A = Pop first item in F
    - Put A in X[0] (X[0] is thus the first group in cluster X)
    For g in 1..len(G)-1 :
        - B = Pop first item in F
        - Put B in X[g]
        - group_size := size(B)
        If group_size != size(A):
            While group_size < size(A):
                - Find next item C in F which size(C) <= size(A) - group_size
                - Put C in X[g]
                - group_size := group_size + size(C)

How can I do better? Is there a canonical problem? It seems like it's close to scheduling of parallel tasks (with tasks instead of files and time instead of size), but I'm not quite sure? Maybe a divide-and-conquer algorithm exists for this task?

Finally I could devise a better algorithm by turning the problem upside down (ie, using bottom up construction instead of top-down).

In my OP algo, I first create a cluster and its groups, and then I walk through the whole files list until I could either fill completely the groups sizes, or there's no file in the files list small enough to fit.

Here it's the other way around: I walk through the files list, and for each file I either assign it to a group if it fits, or if it's too big I create a cluster and init it with this file. To do that, I continually maintain a list of groups sizes to fill, using insertion sort so that when I pick a file to organize, I just need to check its size against the first item of the "to-fill" list.

Here's the algorithm, running in O(n log(g)) (thank's to insertion sort or binary search trees):

For each file:
    - If to-fill list is empty or file.size > first-key(to-fill):
      * Create cluster c with file in first group g1
      * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
    - Else:
      * ksize = first-key(to-fill)
      * c, g = to-fill[ksize].popitem(0)
      * Add file to cluster c in group g
      * nsize = ksize - file.size
      * if nsize > 0:
        . to-fill[nsize].append([c, g])
        . sort to-fill if not an automatic ordering structure

Since it's running in O(n log(g)), the number of groups has little impact on the running time, contrary to the algo in the OP. Maybe it's possible to do better, but for now it is fast enough for me, since it can reasonably work on lists of 10M files under 20 seconds.

For those interested, here's a working implementation in Python (I used the sortedcontainers module for the sorted list, which runs in O(log(g)) instead of O(g) for insertion sort):

from collections import OrderedDict
from random import randint
from lib.sortedcontainers import SortedList

def gen_rand_fileslist(nbfiles=100, maxvalue=100):
    fileslist = {}
    for i in xrange(nbfiles):
        fileslist["file_%i" % i] = randint(1, maxvalue)
    return fileslist

def group_files_by_size_fast(fileslist, nbgroups, mode=1):
    '''Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.'''
    For each file:
        - If to-fill list is empty or file.size > first-key(to-fill):
          * Create cluster c with file in first group g1
          * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
        - Else:
          * ksize = first-key(to-fill)
          * c, g = to-fill[ksize].popitem(0)
          * Add file to cluster c in group g
          * nsize = ksize - file.size
          * if nsize > 0:
            . to-fill[nsize].append([c, g])
            . sort to-fill if not an automatic ordering structure
        '''
    ftofill = SortedList()
    ftofill_pointer = {}
    fgrouped = [] # [] or {}
    ford = sorted(fileslist.iteritems(), key=lambda x: x[1])
    last_cid = -1
    while ford:
        fname, fsize = ford.pop()
        #print "----\n"+fname, fsize
        #if ftofill: print "beforebranch", fsize, ftofill[-1]
        #print ftofill
        if not ftofill or fsize > ftofill[-1]:
            last_cid += 1
            #print "Branch A: create cluster %i" % last_cid
            fgrouped.append([])
            #fgrouped[last_cid] = []
            fgrouped[last_cid].append([fname])
            if mode==0:
                for g in xrange(nbgroups-1, 0, -1):
                    fgrouped[last_cid].append([])
                    if not fsize in ftofill_pointer:
                        ftofill_pointer[fsize] = []
                    ftofill_pointer[fsize].append((last_cid, g))
                    ftofill.add(fsize)
            else:
                for g in xrange(1, nbgroups):
                    try:
                        fgname, fgsize = ford.pop()
                        #print "Added to group %i: %s %i" % (g, fgname, fgsize)
                    except IndexError:
                        break
                    fgrouped[last_cid].append([fgname])
                    diff_size = fsize - fgsize
                    if diff_size > 0:
                        if not diff_size in ftofill_pointer:
                            ftofill_pointer[diff_size] = []
                        ftofill_pointer[diff_size].append((last_cid, g))
                        ftofill.add(diff_size)
        else:
            #print "Branch B"
            ksize = ftofill.pop()
            c, g = ftofill_pointer[ksize].pop()
            #print "Assign to cluster %i group %i" % (c, g)
            fgrouped[c][g].append(fname)
            nsize = ksize - fsize
            if nsize > 0:
                if not nsize in ftofill_pointer:
                    ftofill_pointer[nsize] = []
                ftofill_pointer[nsize].append((c, g))
                ftofill.add(nsize)
    return fgrouped
fgrouped2 = group_files_by_size_fast(fileslist, nbgroups)

def grouped_count_sizes(fileslist, fgrouped):
    '''Compute the total size per group and total number of files. Useful to check that everything is OK.'''
    fsizes = {}
    total_files = 0
    allitems = None

    for fkey, cluster in enumerate(fgrouped):
        fsizes[fkey] = []
        for subcluster in cluster:
            tot = 0
            for fname in subcluster:
                tot += fileslist[fname]
                total_files += 1
            fsizes[fkey].append(tot)
    return fsizes, total_files

if __name__ == '__main__':
    nbfiles = 10000000
    nbgroups = 10
    fileslist = gen_rand_fileslist(nbfiles)
    fgrouped = group_files_by_size(fileslist, nbgroups)
    fsizes, total_files = grouped_count_sizes(fileslist, fgrouped)
    print total_files
    print fsizes


Proving there exists an infinite number of Turing machines is a decidable problem I have a Turing machine M and I have to answer the question are there infinitely many Turing machines that recognize L(M)? I also need to describe a Turing machine that solves this problem. My idea is to say that we can simply increase the number of states by adding a new unreachable state. Each time I add a new state, it's still considered a new TM and because they're unreachable, I can say that they still accept the same language.

The only problem I'm having is describing a TM that can solve the problem. I was thinking that if I create a new TM (let's call it N) that represents M, I could say that N just needs to modify the transition function to create an unreachable state and once it does that it can add an infinite number of unreachable states which means there exists an infinite number of TM's. My problem is that I'm not sure if this is all I have to do to prove this and if it is then is my TM N enough to solve the problem or does it need to do more than just modify the transition function? N has to be decidable so it can't just keep adding states or else it will go on forever.

Given $L(M)$, there are countably infinite number of Turing machines that accept this language. You already describe in your post how to generate these machines. Thus the problem

  are there infinitely many Turing machines that recognize L(M)

is decidable. The TM machine that decides it simply outputs $1$ (ACCEPTS) on any input $\langle M \rangle$.

Note that your TM $N$ does not need to construct all machines, it just needs to always response "YES" since for any $M$ indeed there exists infinite number of TMs accepting $L(M)$.


Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it? Maybe this is a very ignorant question. I don't understand imperative computing very well, would it be correct to think of it as simply scripting (as in, running one or a few commands at a time, typically run through a shell language, as opposed to writing a fully fledged program)?

Your understanding is not correct. There are two major programming paradigms: imperative programming and declarative programming.

In imperative programming you basically tell your computer what to do to solve a certain problem by providing an algorithm which might be implemented as a composition of different functions and/or methods. Often one distinguishes between object-oriented and procedural programming as the two main subparadigms of imperative programming, where the latter one is often scripting but the lines between scripting and "software engineering" (i.e. writing fully fledged programs) is blurry. Procedural programming can be engineerish, too.

In declarative programming you do not tell your computer how to solve the problem but rather what is the problem. Again, one might distinguish between subparadigms where one might be more frequent for hacky scripts where others are more profound.

You might want to check out C, Java, and Haskell (for instance) as procedural, object-oriented (i.e. the two mainly imperative languages) and a functional (i.e. a declarative language) language. Maybe implement functions to sort a list of integers in each of them, the differences between the latter as opposed to the first two should become very clear, but also the corresponding Wikipedia pages should provide good insights. However, e.g. in C++ (object-oriented) there are some features whose origins are in functional (declarative programming), e.g. lambda functions. On the other hand Haskell also has some sort of loops which are strictly speaking a rather imperative concept, so programming language designers adapt concepts from other languages from another paradigm, the line is blurred and not as clear as 30 years ago.

The difference between scripting and software engineering is even less clear. I would say it depends on the size of the program, reliability, use cases, how well it is documented, ... whether a certain program is a script or "fully fledged".


How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs? The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$.

I am confused because I do not know how to reduce this problem. Maybe it works with the complement of the Halting problem?

If it is decidable, let $M$ decide it.

Construct a decider $D$ that works on input $\langle w_1,w_2\rangle$ as follows:

Construct $M_w$ (as well as its encoding $w$) that works on input $x$ as follows:

Run $M_{w_1}$ on $w_2$.
Accept.

Run $M$ on $w$.
If $M$ accepts, accept; otherwise, reject.

We can see $D$ accepts if and only if $M$ accepts $w$, i.e. $M_w$ accepts infinitely many inputs, which means $M_{w_1}$ halts on $w_2$. Therefore $D$ is a decider for the halting problem, a  contradiction.

Hence the language given in OP is undecidable.


Find the closest string to a fixed set of strings I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the fixed size). For this problem you can assume the strings only contain the characters 0-9, and if needed, the length will never be longer than 32 characters.

I measure closest by hamming distance, the distance between two strings is the number of places the two strings differ. I don't care about how ties are resolved, any string with the minimum distance is acceptable.

For example, with s1 = "123" and s2 = "321", the distance between them is 2. (All the pseudo code is in Python)

def distance(s1, s2):
    return sum(a != b for a, b in zip(s1, s2))

I can complete a query in $O(n)$ time where $n$ is the number of strings in the set. The idea would be to loop over each string in the set and compute the distance between it and the target. The answer is the (first, with this implementation) string with the smallest distance.

def query(table, target):
    return min(table, key=lambda t: distance(target, t))

Is there a way to do this in less than linear time? Can the set of strings be pre-processed to allow for a faster search?

Here is a testcase/example

target = '91814154'
table = [
    '91812315',
    '77403499',
    '57579618',
    '92354796',
    '23425335',
    '97722442',
    '01824154']

distances = [4, 8, 8, 6, 8, 7, 2]

So the answer is the string '01824154'.

This is a nearest-neighbor problem, and there are a variety of algorithms for the problem.  The simplest is a k-d tree, and there are more sophisticated data structures as well.  Another approach is to use locality-sensitive hashing.

However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings).  Practical experience is that for dimension $\le 10$, these are better than the naive linear-time search, but for very high dimension, usually they perform no better than the naive algorithm.  This occurs due to the curse of dimensionality.  In your context, that means that if the strings are short and $n$ is large, these data structures will probably be effective, but if the strings are long, I would not expect too much hope.

In the special case where strings are long and you expect the nearest neighbor to have very low Hamming distance, whereas the distance to most other strings will be very large, then there are techniques you can use.  For instance, you might look into shingling the strings into $n$-grams, storing the $n$-grams in a hashtable, and doing a lookup on each $n$-gram from the query string.  You can view this as a form of locality-sensitive hashing for the Hamming distance.  Another approach is to use bit sampling as a locality-sensitive hash; this should be easy to implement.

I also recommend taking a look at our questions in the nearest-neighbor topic, especially Why Is KD-Tree-based Nearest Neighbor Exponential in K?, Best data structure for high dimensional nearest neighbor search, Why is exact nearest neighbor search hard in high dimensional spaces?,
What is the state of the art for k nearest neighbour search?.

We also have questions here about the harder problem of finding the nearest string, where nearest is measured by Levenshtein edit distance (e.g., Find all pairs of strings in a set with Levenshtein distance < d, How to speed up process of finding duplicates/similar items in a large amount of strings?, How fast can we identifiy almost-duplicates in a list of strings?, Matching strings in one set to strings in another based on Levenshtein distance).


Complexity of the decision version of determining a min-cut I was wondering what the complexity of the following problem is:

  Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$.
  Question: Is there an $s$-$t$ cut of capacity at most $k$?

Obviously, the problem is in P by standard methods. When trying to logspace reduce the P-complete LP-optimization problem, I encountered the following problems:

If the LP problem has no feasible solution, then $t$ should not be reachable from $s$. In this case, checking whether an LP problem has a feasible solution would be quite simple (don't know whether this is true).
If the LP problem is unbounded, then the min-cut should be unbounded as well. This could possibly be the case if $s$ and $t$ are identical. Again, checking whether an LP has an unbounded solution would be even easier.

For the lower bound, NL-hardness is quite easy: For a given directed graph $G$ with nodes $s$ and $t$, just take $G$ as a flow network and assign capacity 1 to each edge. Then ask if there is an $s$-$t$ cut of capacity at most 0. $t$ is reachable from $s$ if and only if the answer to this question is no. Since coNL=NL, we are done.

Moreover, the problem is NL-complete for outerplanar graphs. For this, $s$ and $t$ are joined by an edge of infinite capacity. This edge creates the two new faces $f_1$ and $f_2$. Now, answer the question whether there is a path of length at most $k$ from $f_1$ to $f_2$ in the dual graph.

I do not see how to generalize this to general graphs nor how to overcome the problems described when reducing LP optimization.

The described problem is problem A.4.4 of the book  "Limits to Parallel Computation: P-Completeness Theory" and is P-complete. It is proven via a reduction from Alternating Monotone Fanin 2, Fanout 2 CVP (problem A.1.4 of the same book).

The reduction described in this book originates from the 1990 Theoretical Computer Science paper "The Binary Network Flow Problem is Logspace Complete for P" (T. Lengauer, K. Wagner).

The reduction gets an Alternating Monotone Fanin 2, Fanout 2 CVP instance (a circuit $C$) and creates a flow network $N$ that allows a max flow of value $D 4^{k-1}$ where D is the number of input gates in $C$, iff $C$ evaluates to 1.

The idea is to construct the network by creating two nodes $(i,x,0)$ and $(i,x,1)$ for each gate $(i,x)$ (gate $x$ on the $i$th layer in $C$, one for each possible value 0 and 1). The input layer is layer 0. The source of $N$ is connected to $(0,x,0)$ ($(0,x,1)$) with capacity $4^k$ iff $(0,x)$ is a constant 0 (1) in $C$. Each edge $((i,x),(i+1,y))$ of $C$ is then replaced by a small subnetwork which sends 3/4 of the flow directly to the sink. The remaining quarter is sent to $(i+1,y,0) ((i+1,y,1))$, if $x$ in $C$ values to 0 (1). (At least the max flow needs to take these routes. Hence these small subnetworks simulate the gates.)

Now, the output gate $(k,x)$ is copied as well, but only the $(k,x,1)$ copy is connected to the edge. That is: Iff $C$ evaluates to 0, then exactly 1 flow unit cannot be sent to the sink. Hence, the flow in $N$ is $D 4^{k-1}-1$. If $C$ evaluates to 1, then the full $D 4^{k-1}$ flow units can reach the sink. This completes the reduction.


Implementation of Naive Bayes I am implementing a Naive Bayes algorithm for text categorization with Laplacian smoothing. The problem I am having is that the probability approaches zero because I am multiplying many small fractions. Therefore, the probability eventually yields zero. This is because there are several words within the documents and training sets.

Because of this, I am not able to categorize the texts. Is there a way I can get around this problem? Am I doing something wrong in my implementation?

The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i. $$
That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them.

Another approach, which is not so common, is to normalize the product manually. Instead of keeping just one floating point number $p$, you keep a floating point number $p_0 \in [1,2)$ (say) and a negative exponent $x$ such that $p = p_0 2^x$. After each operation you normalize the resulting number.


Comments on "Which combinatorial problem is similar to this problem?" Regarding the post Which combinatorial problem is similar to this problem?, it is quite hard to believe that, in the absence of information on the cost function, there is no algorithm better than exhaustive search to tackle this apparently easy-to-understand problem. I surfed the Internet and found something called the Weighted Constraint Satisfaction Problem, and I wonder whether this can be of any use in this case.
Any advise would be much appreciated.
EDIT: The problem I have at hand is a regression problem where each of $p$ inputs, $x_1, x_2, x_3, \cdots, x_p$, needs to undergo a variable transformation using one of $q$ functions from a set of available functions $F = \{ f_1, f_2, f_3, \cdots, f_q \}$. The cost function is the Mean Square Error (MSE) defined as $MSE = \frac{1}{n} \sum_{k=1}^n (y_k - \hat{y}_k)^2$, where $n$ is the number of samples and for each $k$, $y_k$ is an experimental value and $\hat{y}_k$ is the predicted value computed by some method (e.g., as from a Gaussian Process Regression) using the transformations ($f_j(x_i)$) as input variables. This method must be also selected from a set $M = \{ M_1, M_2, M_3, \cdots, M_m \}$ of widely different available methods. The objective is to decide which function transforms each one of the $p$ inputs and which method to use such that $MSE$ is minimum. There are no constraints whatsoever. I think in this case there is no structure to take advantage of since the cost function changes form depending on the choice of the method.

You are probably assuming that the cost function is efficiently computable, so that "does there exist a selection of the $n$ options with less than $c$ cost" is an NP decision problem. This assumption is not actually stated in the original question. The question merely states "The cost function can be any function, not necessarily linear."
As D.W.'s answer says, "you will need to know something about the cost function and take advantage of some structure or properties it has." Making the assumption that the cost function can be computed in time polynomial in $n$ gives it a little bit of structure. (Exactly how much structure this gives it is the essence of the P vs. NP problem.)


Optimize stacking time series by offsetting start times (feels like a backpack problem?) Given a time-series of data collected from a single running process that takes 8 hours to complete:

Minute
GB of Disk Space Used

0
0

1
8

2
15

3
22

...Etc.  It is sampled every minute, for 8 hours.  The # of GB used jumps up and down a lot, and ends back at 0, like a big spiky mountain shape.  I'm making a (large) assumption that running multiple instances of this process in parallel takes up proportionally more space, but doesn't slow eachother down.

I've also got a hard upper bound that the summed area graph (the total of all space usage at any given minute) can't go above.

My personal upper-bound is 780GB (the amount of spare disk space), and if I ran 53 processes in parallel starting at the same time, they would all add up at minute 2 to (53 * 15) = 795 (which is > 780), the disk would run out of space, and everything would crash.  Or if I ran 35 in parallel, they would crash at minute 3.  No crashing allowed!

The goal is complete as many runs of the process as possible within the next 7 days, by "packing them in" and running them in some overlapping manner by deciding when each run of the process starts.

First Attempt: Greedy
At first I thought it was a simple greedy problem:
At every minute, ask "can you start a new process without the total of all running processes exceeding the limit in the future?"  If yes, great! start a new one.  If not, wait a minute and try again.  This leads to "start 3 processes immediately.  Wait until they all finish.  Then do it again for 7 days."
Second Attempt: recursive?
Done!  wait... that feels wrong, backpack-packing style.  What about "If you line up runs A and B just right, they make a valley you could fit C in to."
Which makes it feel like a recursive solve problem.  Is there an accepted way to optimize this sort of thing?
Third Attempt: Minimize the Maximum (like Tetris?)
My best guess at this point is a simple optimization strategy:

Define a time bound (7 days)
Place the next process start time at whatever is the minimizes the "max space used on the drive, over all time"
If there are ties, move the graph to the soonest start point.
Repeat #2 until nothing more fits.

This would work out to:

First process starts immediately.
Second process starts before the first one finishes: Whenever is in the downslope of the first one exceeds the upslope of the second one.
Keep adding process start times until there isn't a place to slot in one more.

I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it.
Let $c_1, \dots, c_n$ be the series data. For each valid start time $i$, create a variable $x_i$ to hold the number of copies to start at this time and add the constraint $x_i \ge 0$. For each minute of time $i$ (now also including the 8 hours' worth after all valid starting times), add the constraint $\sum_j c_{i-j+1}x_j \le 780$. Objective: Maximise $\sum_i x_i$.
Although this will make for a fairly large ILP instance, my feeling is that will be a "nice" one that can be solved to optimality quickly by a commercial solver like CPLEX or Gurobi. But in case it's not: Even a free LP solver will solve the LP relaxation of this without difficulty; rounding down the $x_i$ gives a feasible solution. If there are few variables $\ge 1$, so that rounding gives an unhelpful answer, you can always just remove some of the variables (I suggest removing the ones with the lowest values) and re-solve.


Can we create recursive functions only by using if-else statements? I have to show whether a program containing only if-else statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I guess this is a recursive function.

How can I prove that formally?

If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.

In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (eval), etc. that let recursion in through a backdoor.

Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (if (x == y)), some primitives on base types (e.g. +, *). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g. x := y takes one unit, x := y + z takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.

Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).


DFA for even number of As, odd number of Bs and precisely one C Exactly as the title says, I'm looking for a DFA for an even number of A, odd number of B, and exactly one C, can anyone help with this?

Thanks

Divide and conquer. You could design a DFA over the alphabet $\Sigma = \{A,B,C\}$

for an even number of A, call it $M_1$
for an odd number of B, call it $M_2$
accepting exactly one C, call it $M_3$

Then design a new DFA equivalent to $M_1 \cap M_2 \cap M_3$ (by closure properties of regular languages).


Mistake in a proof of termination phase of Simplex algorithm in CLRS? There is a pseudo-code for Simplex algorithm in CLRS:

The proof consists from three-part loop invariant:

Proof We use the following three-part loop invariant:
At the start of each iteration of the while loop of lines 3–12,

the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
foreach $i \in B$, we have $b_i$ >= 0, and
the basic solution associated with the slack form is feasible.

The initialisation and maintenance phases are clear for me.
But, the termination case seems(not sure) wrong to me:

So, my question is:
It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?

Because of line 9, $\Delta_l$ is going to be $\infty$ if and only if all the $\Delta_i$ with $i \in B$ are $\infty$. This can happen only when all the $a_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}_i \ge 0$ for all $i$. Therefore it is both feasible and it has unbounded objective value.

If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.


Can truth tables be used in non-boolean algebra to derive functions? There are obvious analogs (pardon the pun) between Boolean algebra and algebra. They have similar laws, operators and properties. I can't figure out why Karnaugh Maps and sum of products, which are used to derive a Boolean function from a truth table, doesn't have an equivalent in algebra.  Perhaps it does, but I haven't seen it.

My only explanation is that if it were possible, you could theoretically find a function for any arbitrary series of numbers (0, 2, 4, 6, 8 f(n)=2n). Thus, you could solve a ton of very difficult problems. I'm not necessarily looking for a formal proof but an explanation.

Right now, I am having fleeting ideas that it has something to do with infinite outputs and inputs, something to do with place values, or true or false equivalents in algebra. There's something here that's difficult to put my finger on.

There are two possible ways to define a non-boolean algebra.

Stick with $\mathbb{F}_2 = \{0,1\}$ but choose base operations other than $\{\land, \lor, \lnot\}$.
Change the base set entirely.

For the whole concept of simplification to word similarly to boolean algebra, we need two binary operations with associativity, commutativity and distributivity. Fields are the natural choice and, I think, the only one. Commutative rings might work but I suspect you get into trouble composing functions in a regular way if you don't have multiplicative inverse elements.

Infinite fields do not make sense here -- you can not draw an infinite table. So finite fields remain, of which there is exactly one per size (up to isomorphy).

So let us, for example, consider $\mathbb{Z}/5$ (the smallest field over $\mathbb{Z}$ with more than two elements and interesting inverses). Now try and formulate a function in a way that looks like a boolean function provided by Karnaugh maps, that is in additive (disjunctive) or multiplicative (conjunctive) normal form. We get to the core question:

  What is the complement of a given element in a non-binary algebra?

The simple logic "if it's not one it's the other" does not work here. Note that the boolean complement does not correspond to the additive nor the multiplicative inverse, so there no hope there. So let's try and define a "complement"; say $\overline{a} = a + 1$ (which contains the boolean complement as special case). We note with unease that this new complement is not symmetric. I expect symmetry to be of essence; reading off from the Karnaugh map seems to rely on it.

So there is no way to get there with an odd number of elements; let's pick one with an even number (so we can pair elements for a complement relation). Now things become messy and I'll stop. After all, Wikipedia says that (emphasis mine)

  the solution can be found by eliminating extra variables within groups using the axioms of boolean algebra

which characterise boolean algebra. Therefore -- provided that all axioms are needed for Karnaugh maps to work -- the concept does not work for non-boolean algebras.


An interesting metric space related to Turing machines In this question we only consider Turing machines that halt on all inputs. If $k \in \mathbb{N}$ then by $T_k$ we denote the Turing machine whose code is $k$.

Consider the following function

$$s(x,y) = \min\{k \mid |L(T_k) \cap \{x,y\}| = 1\}$$

In other words, $s(x,y)$ is the code of the smallest Turing machine that recognizes precisely one of the strings $x,y.$ We can now define the following map

$$d(x,y) = \left\{
    \begin{array}{ll}
  2^{-s(x,y)}  & \mbox{if } x \ne y, \\
  0 & \mbox{otherwise.}
    \end{array}
\right.
$$

It can be quickly verified that $d(x,y)$ induces a metric space (in fact an ultrametrics) on $\Sigma^{*}.$

Now I would like to prove that if $f:\Sigma^{*} \mapsto \Sigma^{*}$ is a uniformly continuous function then for every recursive language L, $f^{-1}(L)$ is recursive as well.

In other words let $f$ be a map such that for every $\epsilon > 0$ there is a $\delta > 0$ such that if for strings $x,y \in \Sigma^{*}$ $$\quad d(x,y) \leq \delta$$ then $$ d(f(x),f(y)) < \epsilon.$$  Then we need to show that $f^{-1}(L)$ is a recursive language given that $L$ is recursive.

Now as already noted in this post one way to approach the problem is to show that there is a Turing machine that given a string $x \in \Sigma^{*}$ computes $f(x).$

I am stuck proving this claim and slowly wondering if there is some other approach to solve this?

Hints, suggestions and solutions are welcome!

Edit: removed hints, posted my solution.

Here is my solution. We're going to pick a reference point $x$ where $f(x) \in L$ and consider the universe from $x$ and $f(x)$'s points of view. It turns out that every "neighborhood" of a point corresponds to a recursive language. So $L$ is a neighborhood around $f(x)$, and there will be some neighborhood around $x$ that maps to it; this neighborhood is a recursive language.

Lemma. In this space, a language is recursive if and only if it is a neighborhood of each of its strings.

Proof. First, fix a recursive language $L$ and let $x \in L$. Let $K$ be the minimal index of a decider for $L$. Then we have that if $y \not \in L$, $s(x,y) \leq K$, so $d(x,y) \geq 1/2^K$. Thus $d(x,y) < 1/2^K$ implies that $y \in L$.

Second, let $x$ be an arbitrary string and fix $\varepsilon > 0$; let $K = \lfloor \log(1/\varepsilon) \rfloor$. Let $L_K = \{y : d(x,y) < \varepsilon\}$; then $L_K = \{y : s(x,y) > K\}$. Then we can write

$$L_K = \{ y : (\forall j=1,\dots,K) |L(T_j) \cap \{x,y\}| \neq 1\}.$$

But $L_K$ is decidable: On input $y$, one may simulate the first $K$ deciders on $x$ and $y$ and accept if and only if each either accepted both or rejected both. $~\square$

Now we're almost done:

Prop. Let $f$ be continuous. If $L$ is recursive, then $f^{-1}(L)$ is recursive.

Proof. Under a continuous function, the preimage of a neighborhood is a neighborhood.

Interestingly, I think that in this space a continuous function is uniformly continuous:  Let $f$ be continuous, so for each point $x$, for each $\varepsilon$ there exists a corresponding $\delta$. Fix an $\varepsilon$ and let $K = \lfloor \log(1/\varepsilon) \rfloor$. There are a finite number of balls of size $\varepsilon$: there is $L(T_1) \cup L(T_2) \dots \cup L(T_K)$; then there is $\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$; then $L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$, and so on. $f$ associates to each of these languages $L_i$ a preimage language $L_i^{\prime}$ with associated diameter $\delta_i$. For each $x \in L_i^{\prime}$, $d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$. So we can take the minimum over these finitely many $\delta$s to get the uniform continuity constant $\delta$ associated with this $\varepsilon$.


Unrestricted grammar for the language of strings whose length is not $2^n$ The following exercise is inspired by an old exam question (note that this is not the question):

Let us define a single-letter alphabet $\Sigma = \{a\}$ and the language $L = \{ w \in \Sigma^*: |w| = 2^n, n \in \mathbb Z_+\}$. (In other words, $L = \{a^2, a^4, a^8, \ldots \}$.) What is an unrestricted grammar for $L$?

I thought of a solution using binary number representation. Consider the grammar:

$S \rightarrow 10TaX$
$T \rightarrow 0T | \epsilon$
$0a \rightarrow aa0$
$0X \rightarrow X$
$1a \rightarrow a1$
$1X \rightarrow \epsilon$

$\epsilon$ signifies the empty string. Using the first two production rules, we can produce a string of the type $10^naX$, for example $100aX$. One route here to get rid of the non-terminal symbols is $100aX \Rightarrow 10aa0X \Rightarrow 1aa0a0X \Rightarrow 1aaaa00X \Rightarrow 1aaaa0X$ $\Rightarrow 1aaaaX \Rightarrow \ldots \Rightarrow aaaa1X \Rightarrow aaaa = a^4$.

Assuming that this solution is correct, one interesting thing about it is that by modifying the third production rule to $0a \rightarrow a^k0$ one can get a restriction-free grammar for strings of length $k^n$ instead. But maybe there is a cleaner solution, so I am interested in seeing other examples of unrestricted grammars for the language.

However, here comes the actual question: the existence of an unrestricted grammar for $L$ only proves that it is recursively enumerable. Therefore I would like to ask for an unrestricted grammar of $\overline{L}$ (then we have one proof that $L$ is a Turing-decidable language).

Edit: In case the question here is unclear, please read the discussion in the comments.

Your method is correct to generate $L$. But if you change the rule to $0a \to a^k0$ then the language you generate is $L^{'}=\{a^k,a^{k^2},a^{k^3}....\}$ ( $k >2$) .
You can show that language $L$ is indeed decidable. One way is to give an algorithm that halts on every input in $\sum^{*}$ and gives the correct result. Following is the approach

(1) If the input is empty reject.
(2) If not empty , check if there are even number of 'a' or odd. If only one 'a' is there accept. If odd 'a' ( > 1 ) are there reject.
(3) If even 'a' are there, go back to starting of input and cross off alternate 'a' from beginning to end of input. Go back to step (2).
The algorithm accepts the string $a$ in addition. You can always modify the above algorithm, keeping a special check that if the input is 'a' reject.


Randomly selecting element from data structure, probability based on weight I have a list of elements, each with an id and a weight.
A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as likely to be selected as an element with weight 5.
B: I need to add/remove elements and increase/decrease their weight dynamically.
I have already found a solution, if I exclude B:
1. fill array with id and weight
2. compute prefix sum
3. generate random number r between 0 and sum of weights - 1
4. binary search which element in the prefix sum corresponds to r

Let n be the number of elements, this solution would be able to retrieve the desired element in O(log(n)), precomputation is O(n). However I cannot add/remove elements or alter their weight without having to precompute the prefix sum again.
Can someone provide me with an approach working for A and B? I have tried using a segement tree but don't find a satisfactory solution.

I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children.
To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know where in the heap is stored an element with given id.

To know how to select an element, when exploring the tree t of weight t.weight, you can generate a number r between $0$ and t.weight, and go left if r < t.left.weight and right otherwise.
To insert, just put it at the last available leaf position and modify the weights of all its ancestors.
To delete, switch the position with the last leaf, and modify the ancestors of both the deleted node and the switched leaf.
To modify weight, use the corresponding structure to know the position of the element of given id, and modify the weights of its ancestors.

All operations can be done in $O(\log n)$.


Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima? Suppose we have a polynomial time algorithm for computing a function (we think of as existing on rational numbers between $0$ and $1$ of limited binary length n). We know that this function is made up of $m$ strictly monotone functions or equivalently that it has up to $m-1$ maxima/minima. Can we find these maxima in time that is polynomial in $m$ and $n$?

Hint: Consider a function that is increasing, except in the small interval $[a,a+\varepsilon]$, where it decreases slowly.  Assume $\varepsilon>0$ is very small and the value $a$ is not known a priori.  Can you find the maxima in polynomial time?


What is the most power/energy efficient sorting algorithm? I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. What algorithm is the most power efficient algorithm for sorting arbitrary text strings?

As concluded by this paper, the algorithm with the better asymptotic run time seems
to also have the better energy efficiency, which corroborates the assumption that an algorithm with a higher performance also has a higher energy efficiency.


Pairs distance to ordering? Thanks to anon for contributing this wording:

Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\pi(j)|$. I want an algorithm which takes as input a (possibly only-partially-filled in) $n\times n$ array $D$, and outputs a permutation $\pi$ that maximizes the number of entries common to both $D$ and $A(\pi)$.

Wording I can follow:

I'm looking for an algorythm that yields a permutation $P$ of the given set $L$.

Where $P$ minimally violates a given set of constraints $C$.

Where constraints $C$ each specify an absolute offsets for the indexes of a pair of elements of $L$.

For example:

Where:

$L = \{w, x, y, z\}\\C = \{\{w, x, 2\}, \{y, w, 1\}, \{y, z, 2\}\}$

Then a valid answer would be $P = \{w, y, x, z\}$

Because, as described in $C$:

$w$ and $x$ are now $2$ "index positions" apart.

$y$ and $w$ are neigbours at $1$ apart.

$y$ and $z$ also being $2$ apart.

The data for $C$ may contain contradictions, therefore the result may be an estimate.

Q: What is a good way to solve this?

I wondered about an approach where $L$ values are placed randomly along a 1D line. $C$ describing the end connections and rest length of connecting springs. Simulated until at rest. Could this produce a reasonably accurate result?

What other aproaches are recommended for finding $P$ from $L$ and $C$?

Apparently, we're given a collection of equations of the form

$$|x_i - x_j| = c_{i,j},$$

where the $c_{i,j}$ are given and $x_1,\dots,x_n$ are the unknowns to solve for.  We want to look for a valid solution that satisfies all of the equations, and where the values of $x_1,\dots,x_n$ are a permutation of $1,2,\dots,n$.

The kind of algorithm to use will probably depend upon how many equations we're given and the structure of the corresponding graph.  However, here is a simple case to start with, to give you some intuition:

Suppose that we are given a complete set of $n(n-1)/2$ equations: i.e., for all $i,j$, we are given $c_{i,j}$.  Then there is a polynomial-time algorithm to recover the $x_i$'s.  Basically, we'll leave $x_1$ as a variable, and we'll try to express every other $x_i$ in terms of $x_1$.  Define $\delta_i$ so that $x_i = x_1 + \delta_i$.  Here's how the algorithm works:

Guess $\delta_2$.  Note that it is either $c_{1,2}$ or $-c_{1,2}$, so there are only two possibilities.
Guess $\delta_3$.  Again, there are only two possibilities: $c_{1,3}$ or $-c_{1,3}$.
Check that $|\delta_2-\delta_3| = c_{2,3}$; if this doesn't hold, discard your current guess.  (This will eliminate $1/2$ of the wrong guesses.)
Guess $\delta_4$; there are only two possibilities.
Check that $|\delta_2-\delta_4| = c_{2,4}$ and $|\delta_3-\delta_4|=c_{3,4}$; if either doesn't hold, discard the current guess.  (This will eliminate at least $1/2$ of the wrong guesses.)
Continue in this way, alternately guessing $\delta_i$ and then checking the equations $|\delta_j-\delta_i|=c_{j,i}$ hold for all $j=2,3,\dots,i-1$.

What's the running time?  The expected running time to list all possible combinations for $\delta_2,\dots,\delta_n$ is $O(n)$.  In particular, at each step, we double the number of combinations we need to consider (since there are two possibilities for the guess), but then we halve the number of combinations we need to consider (since $1/2$ of the wrong guesses can be discarded by virtue of the fact that they violate at least one of the known equations).  Thus the expected number of guesses that remain at the $i$th step is a constant independent of $i$, which implies the running time bound above.

Finally, once you have a combination $\delta_2,\dots,\delta_n$, you can test whether it leads to a viable solution by checking all possible values of $x_1$, inferring the implied values of $x_2,\dots,x_n$ (using the known values for $\delta_2,\dots,\delta_n$), and then checking whether they are a permutation of $1,2,\dots,n$.  Each combination takes $O(n^2)$ time to check, so the overall running time of the algorithm is $O(n^2)$.  This can probably be reduced further, but it's enough to make it already a polynomial-time algorithm.

Now what if we're not given all of the equations?  Then we can apply a similar strategy, but the running time will depend upon the number of equations we're given and the structure of the graph they correspond to.  There's also some degree of freedom in the order that you guess $\delta_i$ values; it's not clear what the optimal strategy is, but probably it will involve looking for small highly-connected regions of the graph and starting with them first.  The best approach might depend upon the specific distribution on problem instances that arises in your practical setting.


Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem? Mahaney's theorem states that the existence of $\mathsf{NP}$-complete sparse language would lead to $\mathsf{P = NP}$. Is there any result result regarding the same for the complexity class $\mathsf{PSPACE}$, like "if there is a $\mathsf{PSPACE}$-complete sparse language, $\mathsf{PP = PSPACE}$" or the same for any other complexity class within $\mathsf{PSPACE}$?

A quick result is that $PSPACE=\Sigma_2$.
First show that $PSPACE\subseteq P/Poly$, and as a result $PSPACE\subseteq \Sigma_2$ (If finding an entry of a computation table is in P/Poly, then it is also in $\Sigma_2$, since we can guess a circuit and locally verify its correctness as described here).
To see why having a PSPACE-complete sparse language $S$ puts PSPACE in P/poly, given $L\in PSPACE$, let $f$ be a reduction from $L$ to $S$. Note that if $|f(x)|$ depends only on $|x|$, then $L\in P/Poly$ since we can concatenate the circuits for $f$ and for $S$ (which is in P/Poly due to being sparse). To overcome the fact that $f$ might vary in the output's length for same input size, note that on length $n$ inputs $f$ can produce output of length $\le n^c$, so given $x$ we can take as a hint all $|x|^c$ circuits for $S$ on input sizes $0,1,...,|x|^c$. Among these circuits, we have the "right" circuit which is able to determine the membership of $f(x)$ to $S$.


Finding $k$-th element in prefix of size $i$ Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of the array $A$ and we sort them we should return the one on index $k$ (we assume everything is 1 indexed).

I know that this can be solved in $O(Q\log N)$ if $Q$ is the number of our queries in offline way (we sort all queries by their index) and if we use persistent segment trees we can even make it work in online way (we can answer queries immediately), however I was wondering if there is simpler solution?

I misunderstood the original premise that A does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time selection algorithm on the original array for 0-i. This is O(i).

Assume A = [1, 0, 3, 5, 4, 7, 2, 1, 3] (inserted in that order)

There is a trivial solution to the problem at hand, and that is to store the data as so:

1
0 1
0 1 3
0 1 3 5
0 1 3 4 5
0 1 3 4 5 7
0 1 2 3 4 5 7
0 1 1 2 3 4 5 7
0 1 1 2 3 3 4 5 7

This is O(n^2) space and preprocessing, but is O(1) retrieval. It is very fast and simple, and honestly the best solution.

In order to achieve "subquadratic preprocessing", you can store this matrix type array in a sparse manner:

1,2
0,0
3,2
    0 1 3
5,4
4,3
7,5
    0 1 3 4 5 7
2,3
1,2
3,5
    0 1 1 2 3 3 4 5 7

This is O(nlog(n)) preprocessing and O(nlog(n)) space, but O(log(n)) time. You choose the gaps by computing floor(log(n)) (or ceil it does not matter) and then fill in the gaps with the elements deleted and the index that they were deleted from in the bigger array (not the smaller one). When searching given an i and k, compute ceil(i/floor(log(n))) to determine which array to start from, and then delete items from that array (do not copy it, as that will make this algorithm O(n)). When you delete an item to the right of your k, you do nothing. Delete an item to the left, and just increment your k to the next undeleted spot. By keeping track of where the last deleted item was you'll never have to traverse the array. Finally, when you reach your i, the k will be pointing to the answer. At this point, just unwind and reinsert the deleted values back in to the array.

Example with i = 7, k = 6:

Start with 0 1 1 2 3 3 4 5 7, with k pointing at 6
Delete at index 5, increment k: 0 1 1 2 3 _ 4 5 7 k=7, i=8
Delete at index 2, increment k: 0 1 _ 2 3 _ 4 5 7 k=8, i=7
i=i that we started at, so we return A[8] which is 7, and now unwind:
0 1 1 2 3 _ 4 5 7
0 1 1 2 3 3 4 5 7

This next solution was the one I was working on when I came up with the above solution (which I think is the best given the constraints). I will leave it in case if someone finds a use for it.

This solution is overly complicated for minimal gains, but matches the "subquadratic preprocessing" constraint. It is also O(n^2) space but is O(nlog(n)) preprocessing. It is O(log(n)) time.

Lets look at this problem in the simple i = n case: we need a data structure that is responsive to updates and can solve the selection problem fast. Here is such a data structure (sorted array for reference):

     1,1
  /       \
0,0       3,3
         /   \
       2,2   5,3
       /    /   \
     1,1  4,2   7,1
          /
        3,1

[0, 1, 1, 2, 3, 3, 4, 5, 7]

Let's say you want to find what was at index 2: start at 1,1 at the top; 1 < 2 so now you subtract 1 from the index you were searching for, and go to the right child. 3 > 1, so you go to the left child, and don't change your current index value. Same goes for 2,2, until you reach 1,1, which is at index 1 + 1 which is 2.

This structure is a binary tree that stores each value and its position relative to the nearest parent that it the right child of. This allows you to insert an item and have the changes be reflected across nodes you haven't touched during the insert. For example, if you insert -1 right now, which becomes 0s left child, you need to touch 1 and 0, and update their positions to 2 and 1 respectively. This automatically shifts everything to the right of 1 rightwards one as well. You can even balance this tree; just make sure to update the new parent by subtracting its left parent's value from it's value.

Now to solve the general case: instead of storing just one index, we store:

A number representing its position in the original A
A list of "previous indices" that the item was at in the sorted arrays

You build this tree just as you build a normal binary tree, except that every time you touch a node, you update it's relative position at that "time" i. Here is an example tree with a small array

A = [1, 0, 3, 5]

    1,0[0,1,1,1]
   /       \
0,1[0]     3,2[1,1]
              \
             5,3[1]

You find the kth index at "time" i by traversing the tree just as above, except you subtract the index you're looking for from the stored index at that node, then index into the list. Instead of going out of bounds, the list also stores the most recent entry. When you add a new entry, you fill in the most recent value for all i up to where you just inserted. If the i you're looking for exceeds the i stored at that node, just use the value at the array index 0 of the node and compare it to the index you're looking for (this only happens if you balance the tree). If this sounds familiar, it's because this is a type of union-set data structure.

For the above tree, finding i = 2, k = 2, you start at the top, subtract your i from 1s i, getting 2 - 0 = 2 and checking it's array at 2, which gives you 1. This is too small, so we subtract the k that we found from our k giving us 1, and move right. Next we encounter 3, we subtract our i = 2 - 2 = 0 and check the array at index 0 giving us 1 which matches our k, which is the answer.

Overly complex solution, but does manage to satisfy the requirements. Additionally, it can actually handle A changing! Balancing the tree is costly, however.


In Paxos, what prevents multiple values from being chosen? Say we have two proposers (P1, P2), one acceptor (A), and two learners (L1, L2).

What would prevent this sequence of events from occurring?

P1 initiates a round numbered 1. A agrees to participate, and reports that is has not voted on any proposals.
P2 initiates a round numbered 2. A agrees to participate, and reports that is has not voted on any proposals.
P1 asks A to vote for some value v1 in round 1.
A accepts v1 and tries to notify learners. L1 receives the message and declares that v1 is chosen.
P2 asks A to vote for some value v2 in round 2.
A accepts v2 and tries to notify learners. L2 receives the message and declares that v2 is chosen.

I'll assume this is Basic Paxos. Step (4) cannot occur - the acceptor A maintains in nonvolatile memory the largest promise it has made (the highest round it has agreed to vote on). At step (2), the max promise becomes 2. When A recieves P1's accept request in step (3) it will reject it because the accept request is from round 1 (this information is communicated in the accept request).


Name for value which may only be -1, 0 or 1? Is there a name for a value which may only be -1, 0 or 1?

Is there a name for a function which creates such a value from arbitrary numbers?

It would be implemented like this:

T Function( T value ) {
  return ( value < 0 ) ? -1 : ( value > 0 ) ? 1 :0;
}

There is no standard name, but the value can be seen as value in the balanced ternary numeral system or as the sign (sgn) function. IMHO, the name Sign() is more appropriate when working with calculations or ordering, the 'balanced ternary' is more appropriate when working with logic. For my purposes, I created a Tri enum in the C# language and, besides others, a generic mapping function with this code:

    // https://en.wikipedia.org/wiki/Sign_function
    public static Tri Sgn<T>( this T value ) where T : IComparable<T> {
        var t = value.CompareTo( default( T ) );
        return t < 0 ? Tri.Negative : t > 0 ? Tri.Positive : Tri.Zero;
    }

And, last but not least, there is the three-valued logic: https://en.wikipedia.org/wiki/three-valued_logic. Values of the 'Tri' type can be used to implement functions for three-valued logic.


Language of walks in a grid – context-free? Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square up, down, left and right, respectively.

Now consider the langauge of all strings representing closed walks (walks that end at their start point). To me, this would seem like any combination of $u$, $d$, $l$ or $r$. So would the language be represented as $L = \{u,d,l,r\}^*$? If so, this wouldn't be context-free right? Thanks.

If your language $L$ were context-free then so would $L \cap u^* l^* d^* r^*$ be. However, $L \cap u^* l^* d^* r^* = \{ u^n l^m d^n r^m : n,m \geq 0 \}$, which is known not to be context-free (this can be proved using the pumping lemma).


What is the approximation ratio of this randomized algorithm for finding matchings? I would like to analyze the following algorithm in terms of its approximation ratio.

Here is the algorithm:

Input: A positive number T and two disjoint sets of nodes V={v1,...,vn} and W={w1,...,wn}.
Output: A matching S.
1: O = [] # An empty array.
2: for t = 1 to T do
3:     Create a set E of edges from V to W randomly
4:     A = LA(G) # G is the bipartite graph G=(V U W, E) and LA is
                 # an algorithm that takes as input a bipartite graph
                 # and outputs a matching A.
5:     O[t] = A # Put the matching A in the t-th element of O.
6: end for
7: S = max(O) # S is the maximum cardinality matching in O.
8: return S

In the algorithm above, called BA, there is a call to another algorithm LA, on line 4. We know that LA is a constant factor approximation algorithm for an NP-hard problem $\Pi$. An instance of $\Pi$ is a bipartite graph and we would like to return a maximum matching that respects some constraints. Therefore, LA will return a matching of size no less than a constant factor times the size of the optimal matching.

Note that BA is trying to solve another NP-hard problem $\Pi_1$ that has an instance of two sets and we would like to return a maximum matching between these two sets that respects the same constraints as for $\Pi$. The only difference between $\Pi$ and $\Pi_1$ is that $\Pi$ has as input a bipartite graph (nodes and edges) whereas $\Pi_1$ has as input a set of nodes only.

I am not trying to hide the constraints. I still cannot write them explicitly in a readable way. I will give some examples to clarify the problem.

Say, for problem $\Pi$, we are given the following graph (it is represented by set of edges):

Instance of II = { {1, 3}, {2, 2}, {3, 1}, {4, 4} }

In this special instance, say, the optimal solution is

OPT of II = { {1, 3}, {2, 2}, {4, 4} }

Hence edge {3, 1} cannot exist in the solution because of the constraints.
If we apply LA to this instance we could have selected, say

A = { {1, 3}, {2, 2} }

Therefore, the algorithm failed to select the edge {4, 4}.
Now, for problem $\Pi_1$, we are given the following two sets:

Instance of II1 = (V = { 1, 2, 3, 4 } and W = { 1, 2, 3, 4 })

In this special instance, say, the optimal solution is (brute-force on all possible edges between V and W and apply the optimal algorithm for $\Pi$)

OPT of II1 = { {1, 4}, {2, 3}, {3, 1}, {4, 2} }

Hence, since we do not have the set of edges initially, the optimal solution for $\Pi_1$ is to select 4 edges unlike 3 edges for $\Pi$. In fact, it is clear that |OPT of II| <= |OPT of II1|.

Now, at iteration t=1, if we apply BA to this instance we could get, say

formed edges in line 3 of BA = { {1, 2}, {2, 2}, {3, 4}, {4, 3} }.

Now we apply LA to this instance and we could obtain
A = { {1, 2}, {4, 3} }

We continue until t=T, and then select the maximum cardinality set A obtained, which is S in line 7 of BA.

Knowing that LA is $O(1)$-approximation algorithm for $\Pi$, can I say that BA is an approximation algorithm for $\Pi_1$?

I think I can say that BA is something like $O(1+\frac{1}{T})$-approximation algorithm for $\Pi_1$ because as $T\to\infty$ and the 3rd line of BA is generated uniformly random, the solution produced by BA is no less than a constant factor times the optimal solution.

The pseudo-code is also given in more clearer way here:

Suppose that the only feasible solution are single edges and $\{(1,1),(2,2),\ldots,(n,n)\}$. The optimal solution thus has value $n$. On the other hand, the optimal solution on a random bipartite graph is $1$ with probability $1-2^{-n}$. Thus algorithm BA would have to take $T=\Omega(2^n)$ in order to guarantee a constant approximation ratio, even though algorithm LA always outputs the optimal solution.


Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos? I was reading the Paxos notes from yale from the following link:

http://pine.cs.yale.edu/pinewiki/Paxos

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was trying to better understand the revoting mechanism to avoid deadlocks in Paxos. The revoting mechanism is explained as follows in the article:

  The revoting mechanism now works like this: before taking a vote, a
  proposer tests the waters by sending a prepare(n) message to all
  accepters where n is the proposal number. An accepter responds to this
  with a promise never to accept any proposal with a number less than n
  (so that old proposals don't suddenly get ratified) together with
  the highest-numbered proposal that the accepter has accepted (so
  that the proposer can substitute this value for its own, in case the
  previous value was in fact ratified).

The bold section is the one that I was trying to understand better. The author tries to justify it with:

  "...so that the proposer can substitute this value for its own, in case the
  previous value was in fact ratified..."

But I didn't really understand why the proposer would want to ratify the previous value. By doing this, what crucial safety property is he guaranteeing? Why is he responding with that and not something else? Responding with the highest could be problem, right, since the current proposal would get lost?

As I was writing my question I realized what I believe to be the correct answer and wanted to share it just in case someone else was wondering this step in Paxos, or maybe correct it if its not 100% correct (or clear).

Recall that, in Paxos, the actual goal is to achieve some consensus (agreement) on some value. The actual value is not very important as long as its from the valid set of values. However, we only care that our protocol somehow achieves some agreement. Thus, if we are a proposer and want to propose a value, what we really care is that some value is agreed amongst the processes participating in the protocol (since that the goal of a consensus algorithm, that some valid value is accepted). If for some reason, we were desperate for our value to be accepted at some point, we could eventually re-run a different instance of Paxos later (or more instances of Paxos until that value is chosen), so its ok to try to suggest the value later (to a different paxos instance) if we really need to (but that will be a different set of rounds of Paxos, starting with round zero and doing Paxos all over again). Its crucial to understand that suggesting the value to the same paxos instance is pointless since the point is that once paxos reaches consensus, that it sticks to it. We have to run paxos for a different set of values if we want our value to still be decided at some point.

But, the point of the step that "acceptors respond with the highest-numbered proposal that the current acceptor has seen", is to guarantee that if a value in the past (with lower sequence number) had been ratified, then why complicate agreement by considering a different value? It's easier to eventually agree at some value if we just keep that ratified value instead. Furthermore, and the more important reason is, imagine if we decided to discard the value we had ratified previously and instead ratify the new incoming one. Well, if we did that and update our state it could be very bad, because, one important property we wish our algorithm to have is, "once an agreement by majority has been reached, we wish it to be impossible for our system to change its mind" (because consensus has occurred already, so a change in mind is completely unnecessary). If we take this new (wrong) approach I have suggested, then that property could not hold. However, if instead, we always just respond with the highest ratified value, then the proposer on the other side is bound to learn the chosen value, if one has been chosen (if he queries some majority). Thus, the safe thing to do is, just send the proposer the current ratified value with the highest sequence number, that way, if a value was chosen, then the system is not able to change its mind if a consensus occurred (since its not necessary for it to change its mind since some value has already been accepted by some majority!). The whole point of consensus means that we agree on something, so changing the value can be viewed as breaking consensus.


Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists? Here's the start and the vernacular I'm using.

# in class Scene
@staticmethod
def common_ancestor(item1, item2):
    if item1 is item2:
        return item1
    com = Scene.common_ancestor(item1.parentItem(), item2)
    if com is None:
        com = Scene.common_ancestor(item1, item2.parentItem())
    return com

Anyway, confusion sets in quickly with this one.  Any ideas how to proceed logically?

Steven's idea in the comments:

# in class Scene
@staticmethod
def is_ancestor_of(anc, item):
    if anc is None:
        return True
    if item is None:
        return False
    if item is anc:
        return True
    return Scene.is_ancestor_of(anc, item.parentItem())

@staticmethod
def common_ancestor(item1, item2):
    if Scene.is_ancestor_of(item1, item2):
        return item1
    if Scene.is_ancestor_of(item2, item1):
        return item2
    return Scene.common_ancestor(item1.parentItem(), item2.parentItem())

The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.)

A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers:

Compute the height of both target nodes.
Until the heights are equal, replace the deeper node with its parent.
Until the two nodes are the same, replace both nodes with their respective parent.

The time complexity of this solution is actually $O(h)$ where $h$ is the maximum height of the tree; by the same token, the time complexity of the solution in the question is $O(h)^2$. If the tree is known to be (somewhat) balanced, then $h = O(\log n)$. Even so, $O(\log n)$ is probably better than $O((\log n)^2)$.


Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything that's random enough to be thought as being random by the general population. I am thinking it is true, but I wouldn't be able to say the exact reason why it would be the case.

In principle yes, but in practice probably not; both of them are likely to be extremely fast.
You can randomly choose between two numbers by generating a random bit.  That is extremely fast in practice.
You can't "pick almost any number randomly".  Instead, all you can do is sample from a distribution. The time it takes to sample from a distribution depends on the specific distribution you have in mind.  However, for most cases commonly encountered, this too is very fast.  For instance, if you want to pick uniformly at random an integer from a particular range, that can be done in a standard way by generating some random bits and then using them to select an integer; it will be very fast in practice.
So, while picking between two numbers might be quicker, both operations are likely to be so fast that it's not clear it is worth worrying too much about which is faster.
If you want to understand why this is the case, I suggest you study algorithms for picking a random number and for sampling from various distributions; that will give you a concrete understanding.


Priority of symbols in a notation for projections We define an initial function called projection as $$I^k_i(n_1,\ldots,n_k) = n_i, \quad i \leq 1 \leq k, \quad k \in \mathbb{N}.$$

Suppose now that we want to define it in some programming language where we have no access to superscripting nor subscripting. Should we call it Iki or Iik?

My stand point is that it should be Iki so that we first describe the nature of function, that it comes from a set of functions that take k arguments. But, the other approach is also understandable because it emphasizes the purpose of function, that it returns the i-th coordinate.
It may also be that priorities don't go from left to right as I imagine it.

Is there any convention on priority of symbols in this type of notation?

No, there is no convention.

In some languages, there is an idiomatic name for the function that extracts the first element of the tuple (e.g., fst, hd) and/or the function that extracts the second element (e.g., snd).


If a decision problem is in $P$, must finding the solution be possible in polynomial-time? Function Problem that finds the solution

Given integer for $N$.
Find $2$ integers distinct from $N$. (But, less than $N$)
That have a product equal to $N$.

This means we must exclude integers $1$ and $N$.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)

for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
  OUTPUT YES

Question

Since the decision problem is in $P$ must finding a solution also be solvable in polynomial-time?

No, and the example you list is a classic example: as far as we know, factoring does not appear to be in $P$, but determining whether a number is prime is definitely in $P$.

Another example: Consider the game Hex.  Consider the decision problem: given $n$, determine whether the first player has a winning strategy for Hex on a $n \times n$ board.  There is a corresponding function problem: given $n$, find such a winning strategy.  Well, the decision problem is trivial (it is known that the answer is always "yes"), but the function problem is believed to be very hard (as far as we know).


Measuring the length of a "loop" in a linked list in $O(n)$ Time? I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop":
Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node3
Node1 and Node2 are considered elements of the "tail", while Node3, 4, 5 and 6 are considered elements of the "loop".
My task is to measure the length/number of elements in the "loop".
My approach was to go through the linked list and catch, when a node points towards a node, I have already passed.
However, to check if a node has been already passed, I have chosen to store all passed nodes into a list/array.
Whenever I approach the next node, I check, whether the next node is already stored in the list/array.
This approach does work, however I was hinted, that there is a way to solve this in linear complexity.
If the linked list consists of n nodes
I am adding 1 element to a list with each node
and I am also checking every element in this list with each node
I assume the complexity is something like : $\frac{n^2 + n}{2}$ which is clearly not ideal.
However I struggle to find a way to check whether I have already passed a node, without checking all previous nodes with every step. Which again would make it necessary to

Keep a list of all previous nodes and
Loop over this list in each step

which then again would increase the complexity.
Is there a way to check, whether I have already passed a node, without checking on all previous nodes?

There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm?
Start thinking from there: Understand this algorithm and why it works, and then you might get an idea or two for the problem