Does my "hollow list" structure exist already? I came up with an implementation in c for arrays which can be extremely large yet only use an amount of memory proportional to how much data you have written to it. What I want to know is if there is a name for this kind of list or structure. Here is my code in C for the structure and example use:

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

int main(){
    int a = 221;
    int b = 222;
    int c = 9;
    int d = 89;

    hollow_list h;
    h = hollow_list_create(30);

    hollow_list_write(&h, 221999999, &a);
    hollow_list_write(&h, 9999, &b);
    hollow_list_write(&h, 22999999, &c);
    hollow_list_write(&h, 1, &d);

    printf("%d\n", *((int *) hollow_list_read(&h, 221999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 9999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 1)));
    printf("\n");
    printf("\n");
    printf("\n");
    printf("%d\n", a);
    printf("%d\n", b);
    printf("%d\n", c);
    printf("%d\n", d);

    c = 56;
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
}

These lists seem to be really useful alternatives to linked lists, and fast too: the worst case scenario for a read or write to a list is O(log n) for a list of n elements. I'd be surprised if this kind of structure didn't already exist, but I would simply like to know what it is called so I could refer to it by it's proper name haha.

This is a sparse array data structure, but I haven't seen this exact data structure before.  It looks like your code builds a balanced binary tree, but with a particularly clever representation in memory.

One difference between other balanced binary trees is that the running time of your approach is $O(\lg m)$ where $m$ is the largest index written, whereas other balanced binary tree data structures (e.g., red-black trees) have a $O(\lg n)$ running time where $n$ is the number of indices written to.  Since $m \ge n$, in principle your approach might be slower if $n$ is small (few elements have been written) but the indices are large.  However in practice I don't expect this to make much difference, ordinarily.


XOR of three integers where each pair's XOR is the other integer I have three positive integers, a, b, and c. I know that $a\oplus b\oplus c=0$, so I got that each pairwise xor has to be the other positive integer. $a\oplus b=c$, $b\oplus c=a$, and so on, but I can't find a, b, and c.

There are lots of solutions, (I'm pretty sure), I'm just trying to code a quick way to find all of the solutions

There are infinitely many solutions: choose $a=b\in\mathbb N, c=0$ and then $a\oplus b\oplus c=0$.

To find all solutions, choose an arbitrary $c\in\mathbb N$. We want to find all $a,b$ with $a\oplus b=c$. Its equivalent to $a=b\oplus c$, so for every $b\in\mathbb N$ we would choose $a=b\oplus c$ and $a,b,c$ would be a valid solution.

All of the solutions are of this form - and therefore thats how you can iterate through every possible solution to the question


Algorithm to compute sum of cost of all path between pair of unique vertices of a tree Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.

Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the pseudocode.

//Final Result
sumAllPair = 0;

//Total Number of vertices
N

//Adjacency List
adjacencyList: array of linked list

//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N

//Initialize Matrix
loop ii from 0 to N-1 {
    loop jj from 0 to N-1 {
        if(ii equals jj) {
            weightedGraph[ii][jj] = 0
        }else {
            weightedGraph[ii][jj] = INFINITY
        }
    }
}

currentVertex = 0
visitedSet: LinkedHashSet of Size N
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)

print sumAllPair

/*
 * Say graph has vertices 1,2,3,4,5,6,7
 *
 * allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
 *              21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
 *              where ij represents cost of path from vertex i to vertex j
 *
 * Time Complexity:
 *      N(N-1)/2 or Combination(N,2)
 */
function allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {

    for each  visitedVer in visitedSet{
        cost = weightedGraph[visitedVer][lastVisitedVertex] +  weightedGraph[lastVisitedVertex][currentVertex]
        sumAllPair = sumAllPair + cost
        weightedGraph[visitedVer][currentVertex] = cost
        weightedGraph[currentVertex][visitedVer] = cost
    }

    add currentVertex to visitedSet

    for each neighbourVert in adjacencyList[currentVertex] {
        if(neighbourVert not equals lastVisitedVertex) {
            //neighbourVert becomes currentVertex
            //currentVertex becomes lastVisitedVertex
            call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
        }
    }
}

Here is an example:

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$.

Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$:

$I(R)$, the cost of all inner paths of the sub-trees (computed with recursion),
$S(R)$, the cost of all paths starting on $R$: $(R, i)$ for any $i \ne R$,
$C(R)$, the paths between the different sub-trees.

Once you recursively have computed the 3 components for each of these vertex $k$ in its own sub-tree $T_k$. Let's call $E(k, R)$ the cost of the edge $(k, R)$ and $n_k$, the number of vertices in $T_k$.

You can compute $N(R)$:

$I(R) = \sum_k N(k)$
$S(R) = \sum_k S(k)+n_k E(k, R)$,
$C(R) = \sum_{k1, k2, k1 \ne k2}(S(k1)+n_{k1}E(k1, R))(S(k2)+n_{k2}E(k2, R))$

Note that if $R$ is connected to only one other vertex, $C(R) = 0$. You also can track $n$ with $n_R = \sum_k n_k + 1$.

This has a linear time and space complexity.


Why are these states equivalent on this translation table Full disclosure: I am trying to understand an answer from the Stanford Automata MOOC.

Why are states F and G equivalent here, such that they would get merged in a minimization process? They both differ on their transitions on 0, so I thought they were distinguishable?

    0   1
->A E   D
*B  A   C
C   G   B
D   E   A
*E  H   C
F   C   B
G   F   E
H   B   H

The two states F and G on similar inputs leads to a final state.
     w(F)+0*1 = w(final-state);
     w(G)+0*1 = w(final-state);
Here, w(X) is the string that leads to the state X, and
      + is concatenation operator.

Due to the above proposition, it is clear that the two states behave in the same manner and the system's functionality will be unaffected because of merging of these states.


For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time? For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

This question popped into my head yesterday. I've been thinking about it for a bit now, but can't figure it out. I don't really know how I'd google for this, so I'm asking here. Here's what I've come up with:

My first thought was that the answer is yes: For every computable function $f$ the problem "Output $f(n)$ dots" (or create a string with $f(n)$ dots or whatever) can obviously not be solved in $o(f(n))$ time. So we only need to show that it can be solved in $O(f(n))$ time. No problem, just take the following pseudo code:

x = f(n)
for i from 1 to x:
    output(".")

Clearly that algorithm solves the stated problem. And it's runtime is obviously in $\Theta(f(n))$, so problem solved. That was easy, right? Except no, it isn't because you have to consider the cost of the first line. The above algorithm's runtime is only in $\Theta(f(n))$ if the time needed to calculate $f(n)$ is in $O(f(n))$. Clearly that's not true for all functions1.

So this approach didn't get me anywhere. I'd be grateful for anyone pointing me in the right direction to figure this out properly.

1 Consider for example the function $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$. Clearly $O(p(n)) = O(1)$, but there is no algorithm that calculates $p$ in $O(1)$ time.

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

If $f$ is a time-constructible function, then the Time Hierarchy Theorem says that there are problems that require $O(f(n))$ time, and cannot be solved with time $o\left (\frac{f(n)}{\log(f(n))}\right )$. Specifically,
$$ \text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$$

This consider only decision problems, and does not regard the time it takes to generate the output.


Formal model of execution for Java (or general imperative language) I'm trying to prove some statements about execution in Java programs under some heavy restrictions (basically I have a conjecture that if two methods satisfy a set of constraints for a given input then the are they equivalent - i.e., that return value and state after execution are identical). To prove this I'm looking for some sort of formalism that will let me talk about this.

I'm familiar with the operational semantics of functional languages and I could possibly translate for loops/while loops to recursive functions... I'd rather not do this and it would be nice to have some machinery so I could stay in imperative land.

More specifically, I want to reason about the state of a method at the kth step of execution. This includes global state:

Calls like this.field = 2 update our class state
Calls modifying parameters update state outside of our method:

myParam.setFoo(...)
myParam.x = y

Calls to static methods

Blah.static_side_effects()

I am assuming that all of this is deterministic. That is, I want to formalize the assumption that if any of these global updates to state occur in two methods, both of whose global and local execution states are identical, then the new state will also be identical - that each step of computation is determined precisely by global state and local state. This obviously precludes RNGs and parallelism (but I may deal with this later...).

Any ideas or sources on how I could approach this? My only thought is to treat methods as a list of statements and try to describe a statements semantics formally.

If possible I'd love to do this at the Java language level rather than the JVM level. This may not be feasible but my goal for now is to make some reasonable assumptions about my operational semantics and then take it from there.

Oh, one final note - any suggestions on how I can improve this question would be greatly appreciated. I'm kind of flailing around trying to find the right language to ask the question and if I'm abusing terminology (like local/global execution state...) I'd love to correct this.

There is an (operational) semantics for Java 1.4 formulated in the $\mathbb{K}$ framework. Associated to this framework is a proof system called Matching Logic. While that page describes a prototype implementation, it seems that the functionality is being incorporated into the $\mathbb{K}$ framework tools themselves as kprover. Unfortunately, it seems the framework is in the middle of being updated, and getting the framework to build and work appropriately is a bit of a chore, and I'm not really sure how practical and/or functional kprover currently is. You could, however, manually prove things referencing the operational semantics (and also using the Matching Logic proof system if you like). The paper describing the Java semantics, K-Java: A Complete Semantics of Java, references some other systems that are less complete, but may be complete enough for your purposes. That said, they may well not be geared toward proving properties about Java programs. Indeed, in the paper, the semantics is being used for model checking rather than correctness proofs.

This is an answer if you want a high degree of confidence that the actual Java code behaves as you intend. If the goal is more verifying the algorithm than the specific realization into Java, then this is likely overkill. That said, you could easily formalize a simple imperative language in $\mathbb{K}$ if you only need basic imperative/OO features. Indeed, this is done as an exercise in the $\mathbb{K}$ framework tutorial. In fact, if you can reformulate your problem into the fragment of C the Matching Logic prototype supports, you could possibly use that as-is.


Is $2^{1+\sqrt{mn}}$ an upper bound for the size of the DFA resulting from the determinisation of n DFAs of size m (all automata sizes are expressed in number of states in this question)

There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.

Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ DFAs $D_i=\{Q_i, q^0_i, F_i , \delta_i \}$ whose size are bounded by $m$.

We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\{Q=\bigcup Q_i, q^0, F=\bigcup F_i , \delta \}$ where $\delta = \bigcup \delta_i$ with the additional constraint that $\forall \sigma \in \Sigma \, \delta(q^0, \sigma) = \{q |  \delta_i(q_i^0, \sigma)=q \,  \, 0 \leq i \leq n \}$ (note that in $N$ the $q^0_i$ are not anymore initial states since there is a unique initial state $q^0$).

Let $D_N$ be the DFA resulting from the powerset construction of $N$ and $D_N^M$ be the DFA resulting from the minimisation of $D_N$.

Is the size of $D_N^M$ at most $2^{1+\sqrt{mn}}$ ?

An equivalent question is : let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz

No.  Asymptotically, the size can be as large as $\sim m^n$.

Let $p_1,\dots,p_n$ denote the $n$ largest prime numbers that are at most $m$.  Let

$$L_i = \{x : x \not\equiv 0 \pmod{p_i}\},$$

where we assume the number $x$ is expressed in unary.  Then $L = L_1 \cup \dots \cup L_n$ has the form

$$L = \{x : x \not\equiv 0 \pmod q\},$$

where $q = p_1 \times \dots \times p_n$.

Note that, with this construction, each $L_i$ has a DFA of size at most $m$ (in particular, of size $p_i$).  However, the minimal DFA for $L$ has size $q$, which is close to $m^n$.  In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).


Are "logarithm types" a thing? I'm attempting to formalize some thoughts I've had about paths into data structures. For example, a path into a list of Ts might be a pair of an index with a path into a T; a path into a pair (A, B) would be the tagged union of a path into A or a path into B. Think of a path as a way to specify some small (atomic?) piece of a larger data structure—not unlike a lens, but here I'm emphasizing the structural decomposition of a data type as opposed to an arbitrary computation that satisfies the lens laws (maybe every path is usable as a lens, but not every lens corresponds to a path).

Strictly speaking, my first example about lists of Ts is a little sloppy, since a path into such a list l should have its index bounded by the length of l. The pair (Nat, path T) is more properly a path into an infinite list of Ts—or, equivalently, a path into a function Nat -> T.

So my first interesting observation is that I have an operator that turns exponentials into products and products into sums in a way that's awfully reminiscent of logarithms:

path (T^Nat) = Nat * (path T)
path (A * B) = path A + path B

That got me thinking about whether there's an exp T type as well. Leaving aside all restraint and sense of rigor, the terms of the usual series expansion for $e^x$ offer a hint:

$$e^x = \sum_{n\ge0} \frac {x^n} {n!}$$

A type-theory interpretation of $\frac {x^n} {n!}$ might be a bag (as in multiset) of $x$s of size $n$ (it's an $n$-tuple $x^n$ but we don't care about the $n!$ ways the tuple can be ordered), so then a value of type $e^x$ would be a bag of $x$s of any size.

So if bag and path might be inverses, then that's saying something like, the type of all bags of paths into a type T, if it exists, is isomorphic to T. For example, there's an obvious isomorphism between (bag A) * (bag B) and bag (A + B) (an isomorphism that doesn't work if you replace bag with list or set or some other collection type, which reinforces my intuition that bag is the correct interpretation of $e^x$).

Of course, this is all appealing-sounding nonsense. I haven't even formally defined what a path is, never mind all the abuses involved in pretending the series expansion of $e^x$ is an algebraic data type. path may also be an idea of limited use, since it's not at all clear to me what to think about something like path (A + B) or path Bool. But has anyone made a more careful study of these ideas? Searching for "type theory" or "algebraic data types" along with "logarithms", "paths", "bags", "multisets", etc. hasn't yielded anything like what I'm attempting to describe here.

Logarithm types are definitely a thing and have been noticed before by a number of people. In functional programming, a Type -> Type functor has a logarithm if it's representable, and then the logarithm is the representing object. See also this, this, and this. You are correct about the exponential functor being the bag functor, see e.g. this, where it's described as the fixed point of the derivative operation on endofunctors.


What is the time complexity of this atrocious algorithm? This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it:

def sort(list):
    if len(list) < 2:
        return list
    else:
        if list[0] <= minimum(list[1:]):
            return list[0:1] + sort(list[1:])
        else:
            return sort(list[1:] + list[0:1])

def minimum(list):
    return sort(list)[0]

I'm interested in working out the worst-case, best-case and average-case time complexity, but I've found myself insufficiently practiced to do so.  I originally thought it would be O(n!), which would be equivalent to cycling through all possible permutations of the list, but because the results aren't even memoized I believe it's actually worse than that.

Mitigating that is the fact that not all of the recursive calls can possibly be worst-case, so I'm not even sure what the worst-case input is for the function overall.

However—even a sorted input of size 5 results in a total of 64 recursive calls, or $2^{n+1}$.  This is best-case time complexity.

What is the worst case input for this algorithm, and what is the time complexity for worst case and average case?

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling sort on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of minimum, and so takes $T(n-1) + O(n)$. The final one descends to sorting a list of length $n-1$. In total, we get the recurrence
$$
T(n) = n T(n-1) + O(n^2).
$$
Opening this recurrence, we get
$$
T(n) = O(n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n!) = O(n!).
$$
(We get $O(n!)$ since the terms decrease very quickly from $n!$ to $n^2$, faster than a geometric series.)

Of course, without giving a matching lower bound, we don't know whether this analysis is tight.


Maximising a particular colour in a vertex colouring I'm looking for a paper that discusses the maximising of one colour in a vertex colouring.

Suppose that for an unweighted, undirected graph $G=(V,E)$ we define a vertex colouring as a function $c : V\to\mathbb N$ (where we use $\mathbb N$ for the colours). I would then like to maximise $\#\{v\in V\mid c(v)=n\}$ for particular $n\in\mathbb N$. The algorithm should return the size of the largest set of vertices that can be coloured with the same colour.

Has there been any literature on this topic?

Your problem is just the (maximum) independent set problem.


Simple example for Higher Order Abstract Syntax (λ-tree syntax) I am reading https://www.cs.cmu.edu/~fp/papers/pldi88.pdf and https://en.wikipedia.org/wiki/Higher-order_abstract_syntax for trying to understand encoding of linear logic using HOAS into Coq. But I still cannot grasp whats going on? Is there simple concrete example available for using HOAS? E.g. exmaple in concrete syntax, example of abstract syntax and example of encoding in HOAS? Or maybe there is available good in-depth explanation of HOAS with multiple examples?

Well, this is a bit broad but the basic idea is the following. In First-order abstract syntax (FOAS) we model lambda terms following their syntax tree. E.g., in Coq we would write

(* FOAS *)
Definition variable := string .
Inductive term: Set :=
  | var: variable -> term
  | app: term -> term -> term
  | lam: variable -> term -> term
.

Definition example: term := lam "x" (app (var "x") (var "x")) .

Note how we model $\lambda x. xx$ by storing the name "x" explicitly.
In a sense, a lambda is represented as a pair (variable name, body).

In FOAS we need to carefully handle alpha-conversion and capture-avoiding substitutions.

In HOAS, we model lambdas as functions, not pairs, exploiting the functions in the host language.

(* HOAS *)
Inductive term: Set :=
  | var: variable -> term    (* vars are usually removed in HOAS *)
  | app: term -> term -> term
  | lam: (term -> term) -> term

Definition example: term = lam (fun x: term => app x x) .

(Note that this won't type check in Coq since it does not use positive recursion, as Mario Carneiro points out below. Still, you get the idea.)

No need to handle alpha-conversion (or substitutions) here since the name "x" is no longer stored in the term.

What we lose in HOAS is the ability to dissect the term representation (e.g. structural induction on the syntax tree) as easily as we could in FOAS.


Determining the number of walks between two vertices in a graph Given a graph G and a set of vertices $(v_1, v_2)$.

How can you determine whether there is $\textit{one}$ unique walk between $v_1$ and $v_2$?

The following answer assumes that by walk you mean path. If you really mean walk, then if $v_1$ and $v_2$ are connected, there are always infinitely many walks between $v_1$ and $v_2$. (A path is a walk without repeated vertices.)

Run DFS from $v_1$, and consider the resulting DFS tree. We can assume that $v_2$ appears in the tree, since otherwise there is no path between $v_1$ and $v_2$. There is always one path from $v_1$ to $v_2$, namely along the tree edges. When is this path unique?

Let us show that the path is unique iff there are no back edges whose target is between $v_1$ (inclusive) and $v_2$ (exclusive). (The target of a back edge is the vertex closer to $v_1$.)

Suppose first that there is a back edge from $y$ to $x$. The following is another path from $v_1$ to $v_2$:
$$ v_1 \leadsto x \to y \leadsto v_2, $$
where $\leadsto$ is a path along the tree edges, $x \to y$ is the back edge. (There are really three different cases here: $y$ above $v_2$, below $v_2$, and equal to $v_2$.)

In the other direction, suppose that $p$ is a path from $v_1$ to $v_2$ which is not solely along tree edges. The first edge in $p$ which is not a tree edge must be a back edge. A short case analysis (considering the direction in which the back edge is taken) shows that the target of the back edge must be between $v_1$ (inclusive) and $v_2$ (exclusive).


How to calculate machine epsilon In a binary system we know that the next floating point number after 4 is 4+1/32. What is the machine epsilon? Is it 1/32 and if yes, why?

First note that $eps$ is not necessarily the same on every machine, it depends on architecture and precision. Also, the definition of $eps$ is not unique in literature. Often it is defined as the difference between $1$ and the next greater number that can be represented exactly, sometimes it is half of this difference (as it is the maximal relative error). In general, if you look at a machine number with base $b$, mantissa $m$ (and exponent $e$), you can define $$eps := \frac{b^{1-m}}{2}.$$

To your example: You would probably represent $4$ normalized as $(0.10000000)_2 \cdot 2^3$. The next number $4+ \frac{1}{32}$ is then represented as $(0.10000001)_2 \cdot 2^3$, i.e. you have $m = 8$ and thus $eps = 2^{-8}$.


Counting on a matrix I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.

If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are considered to be the same.

I know that I can easily computed the numbers of the different matrices out in $O((n\times m)^k)$ time, but is there any better algorithms for this problems?

Also, I am wondering whether $\texttt{Burnside's lemma}$ or $\texttt{Polya's Theorem}$ work here. I am having no ideas with them.

Copied from here.
The mathematics
Consider the group  $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices.
Each matrix is a function $f:X\to S$, and element $f\in S^X$.
So, the problem consists of computing the cardinality
$$\left|S^X/G\right|$$
Cycle index polynomial of a group of permutations
For a permutation group $G$ acting on a set $X=\{1,2,3,\ldots,n\}$ define the polynomial
$$Z(G,s_1,s_2,s_3,\ldots,s_n)=|G|^{-1}\sum_{g\in G}\prod_{k=1}^{n}s_k^{c_k(g)}$$
where $c_k(g)$ is the number of cycles of length $k$ in the cycle decomposition of the permutation $g$.
Polya's enumeration theorem tell us that
$$\left|S^X/G\right|=Z(G,s,s,\ldots,s)=|G|^{-1}\sum_{g\in G}s^{c_k(g)}$$
Cycle index of the Cartesian product
In our case, $G$ is the Cartesian product $S_w\times S_h$. In this paper they prove the following formula
$$Z(G_1\times G_2,s_1,s_2,\ldots,s_{n_1\cdot n_2}) = Z(G_1,s_1,\ldots,s_{n_1})\otimes Z(G_1,s_1,s_2,\ldots,s_{n_2})$$
where the product $\otimes$ (In the paper they use the symbol text reference mark) of polynomials is defined by:
If
$$f(x_1,x_2,...,x_m)=\sum a_{i_1i_2\ldots i_m}x_1^{i_1}x_2^{i_2}\dotsm x_m^{i_m}\text{ and }g(x_1,x_2,...,x_n)=\sum b_{j_1j_2\ldots j_n}x_1^{j_1}x_2^{j_2}\dotsm x_n^{j_n}$$
then
$$f(x_1,x_2,\ldots,x_m)\otimes g(x_1,x_2,\ldots,x_n)=\sum a_{i_1i_2\ldots i_m}b_{j_1j_2\ldots j_n}\times\prod_{\substack{1\leq r\leq m\\1\leq s\leq n}}(x_{r}^{i_l}\otimes x_{s}^{j_s})$$
where
$$x_{r}^{i_l}\otimes x_{s}^{j_s} = x_{\operatorname{lcm}(r,s)}^{\gcd(r,s)i_rj_s}$$
Cycle index of the symmetric group
For the case of the symmetric group $S_n$ acting on $\\{1,2,3,\ldots,n\\}$ we have
$$Z(S_n)=\frac{1}{n}\sum_{k=1}^{n}s_kZ(S_{n-k})$$
or explicitly
$$Z(S_n,s_1,s_2,\ldots,s_n)=\sum_{r_1+2r_2+3r_3+\ldots nr_n=n}\frac{s_1^{r_1}s_2^{r_2}\dotsm s_n^{r_n}}{1^{r_1}r_1!2^{r_2}r_2!\dotsm n^{r_n}r_n!}$$
Solution of the problem
Combining the results above we obtain that the number of classes of $w\times h$ matrices on $s$ symbols up to permutations of the rows and columns is
$$N=\frac{1}{w!h!}\sum_{\substack{i\in P(W)\\j\in P(H)}}\frac{w!}{1^{i_1}i_1!2^{i_2}i_2!\dotsm w^{i_w}i_w!}\frac{h!}{1^{j_1}j_1!2^{j_2}j_2!\dotsm h^{j_h}j_h!}s^{\sum_{\substack{a\in i\\b\in j}}\gcd(a,b)}$$
where the outer sums runs over the partitions $i=(i_1,i_2,\ldots,i_w)$ and $j=(j_1,j_2,\ldots,j_h)$ of $w$ and $h$, respectively. This is, $i_1+2i_2+\ldots+wi_w=w$ and $j_1+2j_2+\ldots+hj_h=h$. The inner sums run over the elements $a$ and $b$ of the partitions $i$ and $j$. This is, $a$ takes the value $1$, $i_1$ times, the value $2$ $i_2$ times, and so on and likewise $b$ takes the value $1$ $j_1$ times, the value $2$ $j_2$ times, etc.
Implementation
As seen in the final formula, we need to compute:

Partitions of a number
Greatest common divisors (gcd) of many numbers.
Factorials of many numbers.

For these, we can do:

To compute all partitions one can use the iterative algorithms here.
An efficient way to compute gcd one could use Euclidean algorithm. However, since we are going to need the gcd of all pairs of numbers in a range and each one many times. It is better to pre-compute the full table of gcd all at once by dynamic programming. If a>b, then gcd(a,b)=gcd(a-b,b). This recurrence equation allows to compute gcd of larger pairs in terms of that of smaller pairs. In the table, one has the initial values gcd(1,a)=gcd(a,1)=1 and gcd(a,a)=a, for all a.
The same happens for factorials. The formula will require the factorials of all numbers in a range many times each. So, it is better to compute them all from the bottom up using that n! = n(n-1)! and 0!=1!=1.
The powers of $s$, which are also needed repeatedly in the sum could also be pre-computed.

An implementation in Python could look like this. Feel free to improve it.


Problem that is only solvable in a given space I was wondering if a computational problem exists with the following properties:

It should be solvable only having $K$ bytes of memory, or solvable with $K' < K$ bytes of memory only in exponential time on $K - K'$ (or such an high degree polynomial in $K - K'$ that for any practical purpose the computation is unfeasible).
The input to the problem should not be bigger than $O(\ln(K))$.
The output to the problem should not be bigger than $O(\ln(K))$.
The time complexity of the problem should be less or equal than $O(K \ln (K))$.

I have thought of many possible solutions but could always find a counterexample. Any sub-optimal suggestion or pointer is also very appreciated.

This kind of question is studied in the cryptography literature under the name "memory-bound computation" or "memory-hard function".  Such a function is one that can be computed efficiently using $K$ bytes of memory but takes much longer to compute if you have significantly less than $K$ bytes of memory.  So, I suggest that you take a look at cryptographic constructions for memory-hard functions.  It's an active area of research, and researchers focus more on practical complexity (concrete running time, not asymptotic running time) than on complexity theory, but you might find it useful.

See https://en.wikipedia.org/wiki/Memory_bound_function#Using_memory_bound_functions_to_prevent_spam for a high-level overview.


Generating symbol matrices that satisfy regular expressions row- and column-wise I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^*ab^*$ for rows and $b^*ac^*$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix}
  a & b & b \\
  c & a & b \\
  c & c & a
\end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.

Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.

Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\$ \not\in \Sigma$ between rows.

We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions.

Let $r$ resp. $c$ be the row resp. column regular expression

Clearly, $r_N = (r \cap \Sigma^N\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r_N$ into an NFA $A_{r,N}$.
Denote with $A^{(i)}_{c,N}$ the automaton that matches only every $N$-th
input symbol (ignoring $\$$) against $c$, starting with the $i$-th.
I will leave the construction as an exercise; suffice to say that we
need at most $N$ copies of $A_c$.

Now, $A_{c,N} = A^{(1)}_{c,N} \cap \dots A^{(N)}_{c,N}$ accepts the set of all matrices each column of which matches $c$.
The automaton $A_{r,c,N} = A_{r,N} \cap A_{c,N}$ accepts all the matrices
you want.
A simple graph traversal finds an accepting path in $A_{r,c,N}$ finds
a solution matrix, if any.

The blowup in size is mild (i.e. at most a factor $N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor $2^N$ for automaton size.

That's still way better than checking all $\Sigma^{N^2}$ possible matrices.


$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work.

How many arrays exist in each step in the recursion tree?

Or can I solve this problem some other way?

Thanks.

At level 0, the top level, you'll have $1$ array, of size $n$.

At level 1, you'll have $n^{1/2}$ arrays for each array at level $0$, for a total of $n^{1/2}$ arrays, each of size $n^{1/2}$.

At level 2 you'll have $n^{1/4}$ arrays for each array at level 1 for a total of $n^{1/2}n^{1/4}$ arrays, each of size $n^{1/4}$.

At level 3 you'll have $n^{1/8}$ arrays for each array at level 2 for a total of $n^{1/2}n^{1/4}n^{1/8}$ arrays, each of size $n^{1/8}$.

In tabular form we have for the first few levels,
$$\begin{array}{ccccc}
\mathbf{level} & \mathbf{arrays} & \mathbf{size} & \mathbf{contribution/array} & \mathbf{total\ contribution}\\
0 & 1 & n & n\lg n & (1)(n\lg n)=n\lg n\\
1 & n^{1/2} & n^{1/2} & n^{1/2}\lg n^{1/2} & (n^{1/2})(n^{1/2}\lg n^{1/2})=n\lg n^{1/2}\\
2 & n^{1/2}n^{1/4} & n^{1/4} & n^{1/4}\lg n^{1/4} & (n^{1/2}n^{1/4})(n^{1/4}\lg n^{1/4})=n\lg n^{1/4}\\
3 & n^{1/2}n^{1/4}n^{1/8} & n^{1/8} & n^{1/8}\lg n^{1/8} & (n^{1/2}n^{1/4}n^{1/8})(n^{1/8}\lg n^{1/8})=n\lg n^{1/8}
\end{array}$$
So the total runtime, $T(n)$, will be the sum of the contributions at each level, namely
$$
n\lg n + n\lg n^{1/2} + n\lg n^{1/4} + n\lg n^{1/8} +\dotsb
$$
Use a property of the log function and you'll see that this simplifies to a simple expression.


Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression Union-By-Rank and Path Compression is supposed to improve the performance of a tree implementation of a disjoint set.

However, in looking at the UNION(x, y) operation, I noticed that if x and y are actually the roots of the 2 trees being merged, no path compression actually takes place. The resulting tree would simply have a depth equal to the larger depth of the 2 trees.

Is my understanding of the algorithm correct?

I assume you are talking about Union Find data structure. When you do UNION($x,y$), you just change the parent pointer of one of $x$ and $y$ to root of the other. The depth of resulting tree is not exactly equal to larger depth of two trees because, initially if the depth of two trees are equal, then the depth of new tree formed will be $1$ plus the old depth.

Coming to the original question, path compression takes place when we do FIND operations and not during UNION operations. When we do FIND($x$), we first find root $p$ of $x$ and for all ancestors of $x$ and also for $x$, we change the root pointer to $p$. You can see that this can reduce the height of tree drastically. After some FIND operations, next FIND operations will take time close to $O(1)$. This is formalised by saying that $n$ FIND operations take time $O(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.


Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free? Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?

I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers are co-prime or not.

I tried using the pumping lemma to no avail.

Any help would be gladly appreciated.

Edit:

Here is one of my failed attempts with the pumping lemma:

Let $N$ be a constant. Take a prime $p$ such that $p > N!$ and then take the word $z = 0^p 1^{p+N!} \in L$. Let $ z = uvwxy $ be a decomposition of $z$ satisfying the conditions in the pumping lemma.

If $ vx $ contains only zeros then $ |vx| = k $ is an integer between $1$ and $N$. Define $m$ as $m = N!/k$. For $i = m+1$ the word $ uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L $

However, I've failed to find such an integer $i$ for the other decomposition cases.

Ridiculous that I didn't see this earlier...

The proof that the language (call it $\mathcal{L}$) isn't context free is by contradiction. Assume $\mathcal{L}$ is context free, by the pumping lemma for CFGs there is a constant $N$ such that each string $\sigma \in \mathcal{L}$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = u v x y z$ with $v y \ne \epsilon$ such that for all $k \ge 0$ the string $u v^k x y^k z \in \mathcal{L}$. Take $m, n$ different primes (such that $\gcd(m, n) = 1$) and $m, n > 2N$, and take $\sigma = 0^m 1^n$. The pumped string will be $0^{m + k a} 1^{n + k b}$ for some constants $a$, $b$, not both zero, and such that $a < m$ and $b < n$ (we have $a, b \le N < m / 2, n / 2$ by the way $m$, $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$. Now:

$$
\begin{align*}
m + k a &\equiv 0 \pmod{n} \\
n + k b &\equiv 0 \pmod{m}
\end{align*}
$$

This has a unique solution $k^*$ modulo $m n$ by the chinese remainder theorem
(we have $a < n$, and as $n$ is prime, $\gcd(a, n) = 1$; similarly $b$ and $m$),
and thus we can write:
$$
\begin{align*}
m + k^* a &\equiv 0 \pmod{mn} \\
n + k^* b &\equiv 0 \pmod{mn}
\end{align*}
$$
i.e., $m n \mid \gcd(m + k^* a, n + k^* b)$. Contradiction.


Is the language of TMs that accept finite languages in $\mathbf{0}'$? In this question it is asked, "Is the language of TMs that accept finite languages Turing-recognizable?".
It turns out this language $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not.
I ask this: We know that the halting problem is Turing-reducible to $L$ but is $L$ Turing-reducible to the halting problem?

Your language $L$ is usually known as Fin or FIN, and is $\Sigma_2$-complete; see for example lecture notes of Cohen Wallace. Since the halting problem is in $\Sigma_1$, it follows that $L$ cannot be reduced to the halting problem.


$O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $. You can't use the summation formula $\frac{N \cdot (N+1)}{2}$ as it would result in an overflow. Even you can't run sums such as sum1 and sum2, it's still going to overflow.

Example:
(6,8) (35,49) (204,288) are the first three Magic Pairs.
P.C: This was our recent examination question, I am curious to know the algorithm.

There are different ways you can use to solve that problem.

One simple but inefficient solution is just that of just computing the two sums in parallel while only keeping track of the difference between their partial sums. I.e., if you added the first $x$ terms of the first sum and first $y$ terms of the second sum, then you'll only remember $x$, $y$, and $\Delta = \sum_{i=1}^x i - \sum_{k=a+1}^{a+1+y} k$.  If $\Delta$ is non-positive, then consider the next term of the first sum (i.e., increment $x$ by one and add $x$ to $\Delta$). If $\Delta$ is positive, then consider the next term of the second sum (i.e., increment $y$ by one and subtract $a+1+y$ from $\Delta$). In this way $|\Delta|$ will never exceed $\max\{a,b\}$.

Another more efficient solution is as follows. Using the summation formula you can write:
$
\sum_{i=1}^{a-1} i = \frac{a(a-1)}{2} = \frac{b(b+1)}{2} - \frac{a(a+1)}{2}
= \sum_{k=a+1}^{b} k$, and some simplifications lead to:
$2a^2 = b(b+1)$.

This means that, once you fix $b$, you can find the corresponding value of $a$ as follows:
$$
a= \frac{1}{\sqrt{2}} \cdot \sqrt{b} \cdot \sqrt{b+1}.
$$

Notice that $\sqrt{b} \cdot \sqrt{b+1}$ must always be greater than $b$ and smaller than $b+1$, meaning that  $\frac{b}{\sqrt{2}} < a < \frac{b}{\sqrt{2}} + \frac{1}{\sqrt{2}}$ and, since $\frac{1}{\sqrt{2}} < 1$, there is at most one integer in that interval, namely $ 1+  \left\lfloor \frac{b}{\sqrt{2}} \right\rfloor = 1+  \left\lfloor \frac{\sqrt{2} b}{2} \right\rfloor $.


Reference request: Category theory as it applies to type systems I keep hearing about how one must learn category theory to truly understand programming language theory. So far, I've learned a good deal of PL without ever stepping foot into the realm of categories. However, I figured it was time to take the leap to see what I had been missing.

Unfortunately, none of the sources I can find seem to make any connections to type systems or programming. They say it's an introduction to category theory for computer scientists, but then veer off into general abstract nonsense (I say this lovingly) without giving any practical examples or applications.

I guess my question is actually two-fold:

Is category theory essential for understanding the "deep concepts" in PL?
What's a source that explains category theory from the viewpoint of practical applications to type systems and programming?

So far, the furthest I've gotten is to a vague conception of functors (which don't seem to be related to functors in ML, as far as I can tell). I'm dreading the abstraction I'll need to keep in my head to understand monads from a category-theoretic view.

Category theory is not necessary to understand programming languages, it's not even necessary to do advanced research on programming languages. Most programming language people don't know (much) category theory.

Category theoretical methods have been useful mostly in a small part of programming language research, namely in the analysis of functional programming, particularly, since Moggi's great discovery that some computational effects have monadic structure. In the 1990s, following Moggi's breakthrough, a lot research was done to extend categorical methods to other forms of programming languages. However, to the best of my knowledge categorical methods have not been found all that useful for  OO, concurrent, parallel and distributed computation, timed computation or compilers. For this reason, people have mostly abandoned extending categorical methods.

Categorical approaches to typed programming work well in pure functions. Indeed some simple typing systems are categories. This is described in e.g.

Categories for Types by Roy Crole
Introduction to higher order categorical logic by Joachim Lambek and Phil Scott.

There is now a lot of work on types for concurrent processes (e.g. session types) and none of that is categorical in nature as of Sept 2016.

That said, one can never know too much mathematics, and knowing category theory is useful. So it's a question of cost/benefit. If you like maths, if maybe you have a bit of background in algebra (e.g. what's the free group over a set, free ring etc) then learning category theory will be easy, and if you plan on doing work that is (inspired by) functional programming, knowing categories will be useful.

Finally, category theory is beautiful mathematics, and worth studying simply because it's so neat.

See Uday Reddy's contribution in this discussion for a different view.


Find a vertex that is equidistant to a set of vertices? I need help with the following problem:

  Input:  An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.

  Question:
  Find a vertex $v$ of $V$ such that the distance from each vertex of $F$ to $v$ is the same and all the distances are minimized?  Return None if there is no such $v$.

The runtime should be $O(|V| + |E|)$.

My thoughts were to do a breadth-first search for each vertex in $F$, so for each vertex in $F$, you store all vertices with their distances, then find the intersection of all these.

Is there a better way?

Starting with $i=0$ and going up, for every $f \in F$ consider a subset of $V$ containing points at the exact distance of $i$ from $f$. Look at intersection of all of those subsets. If you're lucky, as $i$ grows, you'll find this intersection non empty - those will be the solutions.

For the actual implementation, I'd suggest removing vertices closer than $i$ to any of $f$ at every iteration. To find intersection you could simply increment a counter on a vertex, whenever it is included in one of the subsets. When for some vertex v.count = |F|, you are done.

One way to implement it could be as follows

For each v in V, v.count = 0.

For each f in F,
    f.subset = {f},
    f.count = f.count + 1
    if f.count = |F|, return f.

While V is not empty,
    For each f in F,
        old_subset = f.subset,
        f.subset = the set of neighbors of vertices in old_subset,
                   (consider only vertices in V and not in old_subset)

        For each v in old_subset,
            if v.count == 1, remove v from V,
            else v.count = v.count - 1

        For each s in f.subset,
            s.count = s.count + 1
            if s.count = |F|, return s.

return "no such vertex"

While the running time of the above algorithm depends a lot on chosen graph representation, it can be as good as $O(|V| + |E|)$ assuming that you can find the neighbors of a vertex $v$ and remove it from the graph in $O(\deg(v))$ time. In that case, because $\sum_{v \in V} \deg(v) = 2 |E|$, most of the cost of the algorithm is covered by the $|E|$ term.


Finding any path between nodes of implicit, finite, regular, undirected graph Consider a 4-regular, finite, non-directed, integer-weighed graph $G$. Let each node carry an integer value indicating its distance from zero on a hypothetical axis $X$. Take a given node $N$ for which we know its distance from zero (either negative or positive) and the weights on the edges incident to it. Note, that for each node, two of the edge weights are positive and two are negative. All four are integers.  Let $N_0$ denote the node with distance zero on the $X$-axis. In the graph there is at least one $N_0$.

To better illustrate it see an outline diagram (apologies to readers with impaired eyesight for not including high contrast image).

Central blue node in the example has some negative distance from zero (black axis). Now, this node (like each node in this graph) has four edges with weights: w1 and w2 are positive-valued (so that if you choose to move along w1 and w2 this will bring you closer to zero on the axis), while w3 and w4 are negative. In the picture the blue node is connected with the target node with distance zero, but this is of course just for illustration.

Although the graph is finite, it is very large ($>10^{500}$ nodes or so), so one cannot represent the entire graph at once in RAM.

Take any initial node $N$ with weights $w_1,w_2,w_3,w_4$ and distance $d$. If one traverse along either of the four edges towards neighbour node, then all remaining weights in this neighbour can be easily calculated based on the weighs of the initial node (they form some arithmetic sequences, formulae of which are given).

Problem: Find any path (not necessarily the shortest) from $N$ to $N_0$ for the graph described above. The algorithm should basically provide values of subsequent edges (with their weighs) constituting the relevant path to $N_0$. What is the expected computational time complexity?

Additional - strictly related to the problem: Does one need to map the entire graph into memory in order to launch any suitable search algorithm?

The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.


Topological sort where some nodes can't come in between two other nodes I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node X or node Y. In other words, Y < X OR Z < Y.
I've thought about several approaches to this, but can't find a solution. Maybe I can turn every NonBetween relation into "regular edges" and then do a standard topological sort?
Have you heard of any similar problem or solution to this?

EDIT: As pointed out in the comments this doesn't work!
Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.
This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.
If your relation NotBetween is not a black box and actually has some "known shape" you might be able to skip some triples and do better.


One-dimensional packing problem: Optimal decomposition of music structure I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.
Problem Description
Given a section range in a song in seconds (or samples) , e.g. [10,20], I can look up where this section is repeated. Then we end up with a set of repeating sections like: [[10,20], [40,50], [70,80]]. We call this a group. A group has a certain fitness given to it.
(As a sidenote, the fitness of a group is defined as a combination of the sum of similarity values and how much of the song they cover alltogether)
Our goal is to find a set of disjoint groups that altogether have the highest fitness; the optimal decomposition of the repetitions. Below are two different valid decompositions of the same song, one course, and one fine decomposition.

We are provided with a set of all candidate groups, here's a small selection, sorted top to bottom by fitness:

Current Greedy Method

Sort all candidates by fitness
Pick group G with the highest fitness
Remove any groups from candidates if they have overlap with G
Repeat from step 2 until no candidates are left

Bonus
Sometimes the candidates overlap every so slightly, which in the context should perhaps not immediately lead to disqualification.

There are options to relax the no-overlap rule. Note that each of the sections in a group has a different brightness. This brightness corresponds to a confidence, so in a group some sections are more certain to be proper repetitions than others.
For a group of sections G that we wish to add to a set of groups of sections S, we can:

simply remove sections from G if they overlap with any sections in S
trim the sides of to-be-added sections from G if they overlap with any sections in S
keep the overlapping sections in G

I hope this problem is interesting enough to you to give it a shot!
Thank you!

If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails.
Let $G = (V, E)$ be an undirected graph with $n$ vertices $v_1, \dots, v_n$ and $m$ edges $e_1, \dots, e_m$.
Construct an instance of your problem  by creating $n'=n$ groups as follows:

For each vertex $v_i \in V$, add a new group with fitness $1$ containing all intervals $[j-1, j]$ where $j$ is such that $v_i$ is an endpoint of $e_j$.

Any independent set $S \subseteq V$ of $G$ induces of collection of non-intersecting groups (except for the boundaries of the intervals) with total fitness $|S|$.
On the converse, any subset of $S'$ non-intersecting groups must have total fitness $|S'|$ and induces an independent set of size $|S'|$ in $G$.
The claim follows since, assuming the ETH, there exists no $2^{o(n)}$-time algorithm for independent set.
Moreover, assuming $\mathsf{P} \neq \mathsf{NP}$, the above reduction also shows that for any constant $\epsilon>0$ there exists no polynomial-time $n^{1-\epsilon}$-approximation algorithm for your problem, even in the special case of unitary fitness. See, e.g., here.


Complexity as it relates to verifiers of languages So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time verifiers". Is there an analog statement that can be said about a P-class verification complexity? Because P is a subset of NP, I understand that the statement of NP still applies to P. Still, my intuition is that there is something more that can be said about a verifier for P that relates to oracles. Is there more that can be said?

It is an open question whether $P=NL$, where $NL$ is the class of languages verifiable in logarithmic space. It is known that $NL \subseteq P$ (why?), and strongly suspected that $NL \neq P$, but we don't know for sure.


Is legislation NP-complete? I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?

There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?

It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".

The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.


Quicksort's asymptotic performance for array of [50,...,50,100,...100] Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort.

I think it it should be $O(n^2)$ as for array of same elements the complexity is $O(n^2)$ and this particular problem could be rewritten as sorting the first half + sorting the second hald $O(2*(\frac{n}{2})^2 + n)$ which is still $O(n^2)$.

But my schoolmates claim it should be $O(n log(n))$.. so which one is correct?

That depends very much on exactly what quicksort variant you use. Perhaps you should take a peek at Sedgewick "Quicksort with equal keys", SIAM J. Comp 6:2 (jun 1977), pp 240-267 (get it here) or Bentley, McIllroy "Engineering a sort function", Software: Practice & Experience 23:11 (nov 1993), pp 1249-1265.


PERMUTE-BY-SORTING with similar priorities Let $a$ and $b$ be integers, and let $\text{RANDOM}(a,b)$ be a method returning an integer from the range $[a,b]$ uniformly at random. Now consider the following program, that takes as input an array $A$ of integers.

PERMUTE-BY-SORTING(A)
    1. n = A.length
    2. let P[1..n] be a new array
    3. for i = 1 to n
    4.     P[i] = RANDOM(1, n^3)
    5. sort A, using P as sort keys

I'm solving the problem 5.3-6 in CLRS, which is asking me to explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. In other words, the algorithm should produce a uniform random permutation, even if two or more priorities are identical.

Because priorities are repeated in $P$, we will not get a uniform random permutation. I thought of adding i to step 4 but that doesn't produce the uniform random permutation. More specifically, the problem is that if two or more priorities are identical we will not get a uniform random permutation since the probability is not same for all the numbers. Ex 1,2,2,3 the probability of 2 in the example is 1/2 and the probability of 1 is 1/4 and 3 is 3/4.

The easiest way is to generate a random permutation in $P$. Here is pseudocode:

Initialize $P$ with $P[i] = i$ for $i = 1,\ldots,n$.
Repeat for $i = 1,\ldots,n-1$:

Let $j$ be a random number in the range $i,\ldots,n$.
Swap $P[i]$ and $P[j]$.


Perpendicular vectors out of a set I stumbled on this problem and I wanna know if there is a better solution.
There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. Is there any better way than to verify all possible pairs of 3 vectors, some kind of optimization (not the obvious ones)?

The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:

Agarwal, Partitioning arrangements of lines II: Applications.
Chazelle, Cutting hyperplanes for divide-and-conquer.
Matoušek, Range searching with efficient hierarchical cuttings.

There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's problem. See also Williams and Yu, Finding orthogonal vectors in discrete structures.


Non-constructive $NP$-completeness proof Is there any known $NP$-complete problem which hardness proof is non-constructive.

A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument therein, one can extract two polynomial-time algorithms $f$ and $g$ such that:

  For every instance $x\in L_1$, given a certificate $w_1$ for $x$, we
  must have that $w_2=f(w_1)$ is a certificate for $r(x)\in L_2$

  For every instance $x\in L_1$, given a certificate $w_2$ for $r(x)\in L_2$, we  must have that $w_1=g(w_2)$ is a certificate for $x\in L_1$.

In $NP$-completeness result, that does not describe $f$ and $g$, we can say that it is a non-constructive proof. Given a certificate for an instance of $L_1$, one does not know how to construct a certificate for the corresponding instance of $L_2$ and vice versa.

In a sense, the proof only establishes the existence of corresponding certificates.

More specifically, do we have an existence-only proof for some $NP$-complete problem?

If worst-case one-way permutation exists (which exists iff. $P\neq UP\cap coUP$, proven here), then there exists inefficient reduction proof for some $NP$-complete problem.

We denote $\pi$ the one-way permutation above.

Specifically, for each proven $NP$-complete $L$, we can define:

$PERMUTED-WITNESS(L)=\{\pi(x)\mid x\in L\}$

with the certificate for $y\in PERMUTED-WITNESS(L)$ as: $(x,c)$ where $\pi(x)=y$ and $\pi(c)$ is a certificate for $x\in L$ (the "original" certificate). In other words, $c$ is the pre-image of the "original" certificate.

So, given a certificate $c'$ for $x\in L$, we cannot efficiently find $c$ (the pre-image of $c'$) for $\pi(x)\in PERMUTED-WITNESS(L)$


How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more Taken from Artificial Intelligence A Modern Approach :

Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this :

Now obviously this is not true as in the following example :

Bucharest will be added to the frontier first with path sibiu->fagaras->bucharest, while the second path which is more optimal will be omitted.

Am i missing something or is just a false claim?

A* isn't based on the GRAPH-SEARCH algorithm but on the UNIFORM-COST-SEARCH one:

function UNIFORM-COST-SEARCH(problem) returns a solution or failure
   node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
   frontier ← a priority queue ordered by PATH-COST,
              with node as the only element
   explored ← an empty set

   loop do
     if EMPTY?(frontier) then return failure

     node ← POP(frontier)  /* chooses the lowest-cost node in frontier */
     if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

     add node.STATE to explored
     for each action in problem.ACTIONS(node.STATE) do
         child ← CHILD-NODE(problem, node, action)
         if child.STATE is not in explored or frontier then
             frontier ← insert(child, frontier)
         else if child.STATE is in frontier with higher PATH-COST then
             replace that frontier node with child

Uniform cost search algorithm is identical to the general graph search algorithm (in your question) except:

for the use of a priority queue and
the addition of en extra check in case a shorter path to a frontier state is discovered.

A* is identical to UNIFORM-COST-SEARCH except that uses $g + h$ instead of $g$.

So assuming the following distances (straight-line distance to Bucharest) for the h heuristic function:

Sibiu          253     Fagaras 176
Rimnicu Vilcea 193     Pitesti 100
Bucharest        0

the second path will NOT be omitted. Stages in an A* search for Bucharest  are (numbers show $f = g + h$):

(a) Sibiu 0 + 253 = 253
(b) Fagaras = 99 + 176 = 275, Rimnicu Vilcea = 80 + 193 = 273
(c) Pitesti = 177 + 100 = 277
(d) Bucharest (via Fagaras) = 310 + 0 = 310

A* search keeps going, choosing Pitesti for expansion:

(e) Bucharest (via Pitesti) = 278 + 0 = 278


What is a preterm parser? I am working with HOL-Light parser and keeping seeing references to preterm parser.

What is a preterm parser?

The most informative statement I find is from the HOL-Light reference for the parse_pretype function.

  This is mostly an internal function; pretypes and preterms are used as
  an intermediate representation for typechecking and overload
  resolution and are not normally of concern to users.

Since HOL Light is based on $\lambda$ Calculus and HOL Light is typed and as we know there is untyped $\lambda$ Calculus and typed $\lambda$ Calculus, HOL Light starts by parsing something close to untyped $\lambda$ Calculus, creating pre-terms. Then it applies a typing checking and typing phase, along with resolving overloaded operators resulting is something closer to typed $\lambda$ Calculus. Obviously HOL is much more than typed $\lambda$ Calculus, but the point here is to understand what pre-term means with regards to parsing.

The only reference I have found for this is in

Lectures on the Curry-Howard Isomorphism
Section 1.2 Pre-terms and $\lambda$-terms.

Specifically how this is done in HOL Light is in the parser module:

The pre-terms are created with

let ptm = (parse_pteterm << lex << explode) input

and the type checking, etc. is done with

let term = (term_of_preterm << (retypecheck [])) ptm


Finding number not in list with wildcards I have a list like this:

1*0*0
1**0*
0*0**
001**

Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time algorithm that can determine if there exists an $n$-bit number that does not equal any of the rows. Does anyone know of an algorithm that could do this? I've been thinking about evaluating the total number of possible solutions for each row and subtracting from $2^n$ but I can't figure out how to delete duplicates in polynomial time.

Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows:

For each clause $C_i$, create a row (i.e. binary string) $B_i = b_1 b_2 \ldots b_n$, where

$$ b_k = \begin{cases}
1 & \text{if }\overline x_k \in C_i \\
0 & \text{if } x_k \in C_i \\
* & \text{if } x_k, \overline x_k \notin C_i
\end{cases}$$

We can preprocess $\phi$ to remove any clauses that contain both a literal and its negation, as these will of course always be satisfied and do not affect the result.

Any binary string $S$ that solves your problem also yields a satisfying assignment to $\phi$, using the reduction that sets  $x_i$ to the value of $S_i$.

Thus your problem is $NP$-hard. Since it is also clearly in $NP$, it is also $NP$-complete.


Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)? Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w that are in the language of G? And can I get parse trees for those substrings? What would be the time complexity for these things?

You can do this in $O(n^2)$ time using an advanced version of Earley. See this answer for this advanced version.

This algorithm can parse any $LR(k)$ grammar in linear time. While doing so, it also parses all prefixes of the string (if no lookahead is used - for lookahead you would need to also perform actions that would be performed at end-of-string tokens) and puts 'I am finished' items in item sets whose index corresponds to an index in the string at which a prefix was recognized to be in the language.

We can therefore start this algorithm at every position in the string, parsing the remainder of the string, for a total running time of $O(n^2)$. As we can have $O(n^2)$ matches, this is in a sense optimal.

You could also change the algorithm and run it once: you can insert an 'I've started here' item at every index, and then parse the string running the Early version only once. This may be faster in practice, but I'm not sure what its running time would be.

Note that recovering a parse forest from an Earley parse is not the simplest thing in parsing. The above algorithm probably needs augmenting if you also want all the parses of the substrings (rather than just what substrings match). Note that on grammars that are not $LR(\pi)$ for some regular partition $\pi$ (which includes all $LR(k)$ languages), the above algorithm may not run in quadratic time.


Big-O and little-o notation I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following:

$$O(n^c) = o(n^k) \text{ for } k > c$$

For example, $O(n^2) = o(n^3)$ since $3 > 2$. Basically, any constant times $n^2$ will still grow more slowly than any constant times $n^3$ for large enough $n$.

Does it make sense to have both sides of an equation consist of big-O and/or little-o notations like this, or does one side of the equation have to consist of a bare function only? Thanks.

Many people cringe at the notation $n^2=O(n^3)$, since, strictly speaking, $O(n^3)$ is a set of functions, defined by
$$
O(n^3)=\{f\mid \exists k>0, N\ge 0\, [f(n)\le kn^3\text{ for all }n\ge N\}
$$
In other words,
$$
O(n^3)=\{1, n, n^2, n^2\log n, n^3, 3n^3+15n^2,\dotsc\}
$$
which is to say $O(n^3)$ consists of all functions $f(n)$ that are eventually less than a constant multiple of $n^3$.

With this understanding, to be precise we should write $n^2\in O(n^3)$, rather than the sloppier $n^2=O(n^3)$. This means that it is indeed notationally correct to ask whether $O(n^2)=o(n^3)$, since they are both sets of functions.

[Note, by the way, I'm not asserting that $O(n^2)=o(n^3)$. I'll leave that to you to prove or disprove.]


Prove or Disprove: an infinite intersection of regular languages is a context-free language Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language.
I know that statement is false, but couldn't find an example to disprove it.
Would appreciate your help:)

"I know that this statement is false, but couldn't find an example to disprove it."
It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet $\Sigma$.

Let $L$ be a language. Then there exist regular languages $L_1, L_2,...$ such that $L=\cap_{k=1}^{\infty}L_k$.
Proof. The other answer indicates how to construct $L_i$. For clarity, here is the construction.

Let $L_i$ be the words in $L$ with length at most $i$ together with all the words with length greater than $i$. More formally, let $L_i=\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}\cup\{w\in\Sigma^*:|w|\gt i\}$. Then $L=\cap_{k=1}^{\infty}L_k$.
Each $L_i$ is regular since $L_i$ is the union of two regular languages.

$\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}$, as a finite set, is regular.
$\{w\in\Sigma^*:|w|\gt i\}$ is regular.

So, even if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, $L=\cap_{k=1}^{\infty}L_k$ can be non-regular, non-context-free, non-context-sensitive, etc.


PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$? In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:

  Requiring solutions to all type equations may seem suspicious, because
  we know by Cantor’s Theorem that an isomorphism such as $X \cong (X \rightarrow \mathbf{2})$
  is set-theoretically impossible. This negative result tells us not that our requirement
  is untenable, but rather that types are not sets.

I understand why solving such an isomorphism is set-theoretically impossible, and therefore why being able to solve it means that "types are not sets". However, I cannot think of any possible type $X$ that would actually solve this isomorphism.

Can anyone give an example of such a type (and ideally, some advice for more generally solving such type isomorphisms)?

To say that we cannot solve $X \cong (X \to 2)$ in sets means that we have to do it in another category. And because we're talking programming languages, we should be looking for one in domain theory. The buzzword to look for is recursive domain equation.

There are several kinds of domains, but to give you an idea of what they are, perhaps we can recall the definition of $\omega$-cpos. An $\omega$-cpo $(P, {\leq})$ is a set $P$ with a partial order $\leq$ which has a least element $\bot \in P$ and such that every increasing sequence $x_0 \leq x_1 \leq x_2 \leq \cdots$ in $P$ has a supremum.

In the particular case we look for a domain $X$ which satisfies
$$X \cong [X \to 2_\bot]$$
where:

the domain $2_\bot = \{0, 1, \bot\}$ is ordered by $\bot \leq 0$, $\bot \leq 1$ (i.e., $\bot$ is below $0$ and $1$, and $0$ and $1$ are incomparable). The domain $2_\bot$ corresponds to the datatype bool: $0$ and $1$ are the boolean values, while $\bot$ represents a non-terminating program.
the domain $[E \to D]$ is the domain all all continuous maps from $E$ to $D$, where a map is said to be continuous if it is monotone and it preserves suprema of increasing chains.

Now, the reason why an equation such as $X \cong [X \to 2_\bot]$ has a solution is complicated. Figuring out that soultions exist when we take a good enough notion of "domain" was done in the early 1970s, with poineering work of Dana Scott and several other people. It takes a short course on domain theory to get to the point where the construction of solutions becomes explainable.

Perhaps I can comment on why domain theory avoids the usual problem from set theory, where Cantor's diagonal argument shows that $X$ always has fewer elements than $X \to 2$. In domain theory $[X \to 2_\bot]$ is not the set of all maps, but just the continuous ones, and there are many fewer of those.

Let's attempt a more familiar setup. Consider the real number $\mathbb{R}$ and the Sierpinski space $\mathbb{S}$, which just the set $2 = \{0, 1\}$ with the topology in which the open sets are $\emptyset$, $\{1\}$ and $\{0, 1\}$. It is well known that the set of continuous maps $\mathcal{C}(\mathbb{R}, \mathbb{S})$ is in bijective correspondence with the open subsets of~$\mathbb{R}$, of which there are $2^{\aleph_0}$, and so we have "solved" $X = X \to 2$ in sets by restricting to continuous maps:
$$\mathbb{R} \cong 2^{\aleph_0} \cong \mathcal{C}(\mathbb{R}, \mathbb{S}).$$
This is not a solution, however, because the bijection between $\mathbb{R}$ and $\mathcal{C}(\mathbb{R}, \mathbb{S})$ can never be a homeomorphism.

Sometimes we can actully solve a recursive equation with much less work. For instance, working in topological spaces, we have
$$\mathbb{N} \cong 2^{2^\mathbb{N}}$$
because $2^{\mathbb{N}}$ is the Cantor space, whose set of clopen sets is countable and discrete (under the compact-open topology), therefore homeomorphic to $\mathbb{N}$.

Yet another example comes from ordinal arithmetic (not cardinal arithmetic!) where have $2^\omega = \omega$, so that is maybe the closest to what you're asking for.


When is it useful to split critical edges? Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and transformations. In what cases would splitting critical edges be useful?

An easy google search shows in Muchnick, Advanced Compiler Design & Implementation, Section 13.3 Partial-Redundancy Elimination, pp 407-408:

  A key point in the algorithm is that it can be much more effective if the critical edges in the flowgraph have been split before the flow analysis is performed.

So the notion is useful to increase the efficiency of certain flow analyses in redudancy elimination, which aims to find portions of code with common sub-expressions and hoist them out into a single computation, which is facilitated in the absence of critical edges.


Method for combining derivative free optimization results of different data inputs I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as possible.

What I found, is that when optimizing the parameters for a specific time period, these parameters don't necessarily work well when used on another time period.

The way I see it, is that there are two possible solutions to this problem:

use a longer time period when optimizing the parameters
find a method of combining the optimal parameters for different time periods, such that these "averaged" parameters work well on all time periods

Option 1. would be incredibly expensive in terms of computational time. And although it makes intuitive sense that this should fix the problem, I am not sure that this would indeed be the case.

Option 2. reminds me of training neural networks, where one would feed in a large number of "data points" and somehow take a (weighted) average of the results to find a set of parameters that work well for all data points. Unfortunately, I know very little to nothing about the algorithms used for this kind of optimization/learning.

Any help or suggestions are greatly appreciated. Please let me know if there is anything you'd like me to expand upon.

Thanks!

EDIT:
As suggested in the comments, here is some additional information:

my loss function is not an actual mathematical function, so I don't know exactly what it looks like, this also means that I can't compute the gradient.
The optimization method I currently use is differential evolution using the best1bin strategy.
The reason the predictions fail is because of overfitting.
There are ~10 parameters
One iteration takes about 5-8 seconds

You say you are overfitting.  The usual solution is to use more training data and/or regularization.

The easiest solution is probably going to be to train on all data, not just a limited time window.  Perhaps you can find a better mathematical optimization algorithm. You don't give any details on the optimization algorithm you are using or how you compute the loss function; perhaps using a stochastic version (e.g., analogous to SGD instead of GD) would provide better efficiency.  You could also consider Bayesian optimization, which constructs a differentiable model to estimate/predict the output of your loss function, and then uses SGD on it.  Another option is to use gradient-based methods and estimate the gradient using finite differences; if you have 10 parameters, you can estimate the gradient by evaluating the function 11 times on 11 different inputs.  Then you could combine that with gradient descent.

Or perhaps you can use regularization; for instance, if you have a prior on parameters, you might be able to choose a suitable regularization method.  I suspect it's going to be hard to say without getting into the specifics.


What is the fastest way to bytewise examine the contetnt of quadword I have the following byte: 0x0A and I need to test if a quadword contains it or no using standard bitwise operarion (or, nor, xor). For instance:

0x1689FFBB768922AC ---> false
0x106489320A792399 ---> true

Unfortunately I cannot use intel SSE2 extension because this will make the code heavily depndent on the platform.

Can we find some bitmask to bitwise or with? Or maybe something else...?

Yes, it can be done.  Here is one reasonable approach.  First XOR the value with 0x0A0A..0A:

t = x ^ 0x0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A;

So now the problem becomes testing whether y contains a zero byte.  First we'll replace every byte with a single bit that is 1 if the byte is non-zero, or 0 if the byte is zero:

u = t | (t>>4);
u = u | (u>>2);
u = u | (u>>1);

(Here we only care about the least significant bit of each byte; the remaining bit positions hold garbage that we don't care about.)  Now we'll flip each of those bits:

v = ~u;

At this point the LSB of each byte is 1 if the original value contained a 0x0A there, or 0 otherwise.  So, we'll test whether any of these bits are 1:

w = v | (v>>64);
w = w | (w>>32);
w = w | (w>>16);
w = w | (w>>8);
y = w & 1;

At this point, y is the result you are looking for: it will be 1 if the original value had a 0x0A byte anywhere, or 0 otherwise.


Decidability of bitstring languages with no ones' complements For any string $s \in \{0,1\}^*$, let the ones' complement of $s$, denoted $1_c(s)$, be the string obtained by flipping all bits in $s$. For example, $1_c(001100) = 110011$. Now call a language $L \subset \{0,1\}^*$ ones' complement asymmetric or OCA  for short, if for every string $s \in \{0,1\}^+$, precisely one of $s$ and $1_c(s)$ is in $L$.

I want to come up with a mapping reduction from a language $L \subset \{0,1\}^*$ to an OCA language (and vice-versa) so as to prove the existence of decidable/recognizable and undecidable/co-recognizable and undecidable, etc., OCA languages. My problem is especially that we require every string in $\{0,1\}^+$ to be such that either it or its ones' complement appears in any OCA language. This seems particularly problematic if $L$ lacks strings of a particular length, meaning it isn't obvious how we'd go about constructing an OCA language from $L$.

I don't think there exist recognizable-but-undecidable OCA languages, because if we have a Turing machine M that recognizes a given OCA language, then we can create a derived Turing machine that incrementally simulates M on both its input and its one's-complement (flipping back and forth, trying a finite number of steps in each simulation) until one input or the other has been recognized.

(Note: the derived Turing machine will also need to be given specific logic to decide the empty string; but that's obviously possible to do for any given language.)

Therefore, you can't construct any reduction mapping that would let you prove the existence of recognizable-but-undecidable OCA languages.


sentiment analysis by sentence similarity How can sentence similarity be used for sentiment analysis? I know we have sentence Bert which can use cosine sim to measure the distance between to vectors (the sentence embeddings), but has anyone used to for sentiment analysis specifically?

I expect that measuring the similarity of two sentences probably isn't a useful way to do sentiment analysis.  There are better methods for sentiment analysis, so rather than adopting the artificial constraint that it must work by measuring the similarity of two sentences, it's better to use standard methods (I expect they will perform better).


Predication execution I was studying branch prediction & predication execution and faced a trouble..

I'm not quite sure whether I understood the concept of predication but based on what I have learned it is taking both taken and not taken at the same time.

For example, let's assume we have 'if' and 'else' each filled with 3 instructions.

For branch prediction, if prediction is correct, we won't have any loss in performance. But if prediction is wrong, there's a waste of 3 instructions.

For predication, either right or wrong, we will have waste of 3 instructions.
Then what is the use of predication?

Branch prediction has an accuracy over 90%(I don't know if this only applies to branches with many instructions that can learn from history).

If so, we have a low chance of wasting.

But even besides that, only when prediction accuracy is 0%, branch prediction will be same as predication.

SO where am I getting wrong?

The cost of a branch misprediction depends on the depth and width of the pipeline and not the amount of code guarded by a condition. A processor keeps fetching and decoding down the wrong path until the branch is resolved and the correct target determined. In a two-wide processor with five stage before branch resolution (a "moderate performance design", say two instruction fetch stages, a decode stage, a register read stage, and an execute stage with a branch resolving at the end of the execution stage), a mispredicted branch could lose up to nine instruction execution opportunities:

br+w1       IF IF ID RR EX
w2+w3          IF IF ID RR EX
w4+w5             IF IF ID RR EX
w6+w7                IF IF ID RR EX
w8+w9                   IF IF ID RR EX
c1+c2                      IF IF ID RR EX

In most real code, two consecutive instructions would not always be able to execute in parallel, so the actual lost performance would be lower. (If the branch was the second instruction of a pair, only 8 instruction execution opportunities would be lost.)

In a fully predicated ISA, the predicated form could also have one less instruction (a branch instruction might include a comparison that would have to be provided as a separate instruction to provide a predicate but often normal instruction results provide a predicate).

Another consideration is that predication avoids fetch redirection. Some implementations have had a one cycle taken branch fetch penalty; for a two-wide processor, this would allow two predicated instructions to execute "for free".

(Out-of-order execution complicates the tradeoffs in providing and using predication. Predication turns an instruction with two dynamic sources into one with three dynamic sources, so the scheduler has to monitor the availability of an additional source (the predicate). In addition, predication converts a control hazard (which can often be bypassed using prediction) into a data hazard (if the predicate is not available, the instruction will not execute and its dependencies cannot execute). In theory, predicates can be predicted just as branch direction is predicted with the prediction only used if the data hazard is expected to introduce excessive slow-down, but this requires both a confidence estimate for the prediction and an estimate of the costs for using and not using the prediction when the prediction is right and when it is wrong.)

Furthermore, not all branches are equally predictable. Some branches approach fifty percent predictability. It is even possible to always mispredict (e.g., with two-bit counters initially at weakly wrong for the first encounter and a branch that alternates between taken and not-taken), though this is a rare occurrence.

Predication of nested conditions can also exponentially increase the number of executed instructions. Branch prediction would choose one path for a switch statement; complete predication would follow all the paths.

Another factor is that processing extra instructions can be relatively inexpensive if the processor has otherwise idle resources. E.g., if one path is stalled waiting for the result of a long latency instruction (or cannot fully utilize available execution width), (predicated) instructions from the other path may be able to execute "for free" (power and other costs would still apply).

Predication also makes more sense with vector/SIMD operations where per-element predication can facilitate the use vector operations that would otherwise need to be executed in a scalar fashion. (Even without predication, one can use bitwise SIMD operations to select operands, choosing between the true operand and the identity value for the operation.)


How to show that the product of two binary numbers can be determined in AC1? I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?

Multiplication can be done even with stronger restrictions, like $AC^1$ with bounded fan-in.

Proof is little hard to typeset here, but I will outline the sketch and give a link.

You shall prove, that addition of two m-bit numbers have $O(m)$ size and constant depth circuit and thus is in $AC^0$. This is pretty simple (start with looking for $O(m)$ depth and then simplify)
Then you need to generalize this result to addition of many m-bit numbers and show that it have logarithmic depth and thus in $AC^1$
And finally what you are looking for (product in $AC^1$) is simple corollary

Look into those lecture notes for example, where this proof is done in great details.


Occupancy of a B+ Tree If a B+ tree has an occupancy of 67%, does that mean the tree holds all of an index, and has additional empty nodes taking up the remaining 1/3rd?

B+ trees, like all B-tree variants, are typically page-structured. A page size is chosen (which is a multiple of the disk page size and the CPU's page size). Each node or leaf is a page in size. Organising the tree this way eliminates external fragmentation.

We pay for it with internal fragmentation.

Each node and leaf can have a variable amount of data stored inside it. So for if a node is not full, some of that page is unused. When we say that a B+ tree has 67% occupancy, this means that 1/3 of the allocated space is unused memory at the end of pages.


Why multiple return values is not a common thing? I would like to ask a question about multiple return values, why this construct is not preferrable in programming languages (conceptual and/or technical difficulties). I've heard something about stack frames and how they reserve memory for return value and variable return values could make this problematic, but if someone could explain this better, this would be much appreciated.

In conctanetative languages (like FORTH), having multiple return values from a function is a common and very useful thing, and I imagine something like this in java/c-like languages would be useful too (a very basic example):

x, y = multRet(5);
multret(int x) {
    return x+1;
    return x+2;
    exit;
}

To clarify: I am not asking how to return multiple values (this is a known question with known answers), but I want to get a clarification about why this practice is not common in programming languages.

Functions are traditionally thought of as returning a single value - in math. Of course several values form a tuple, but oftentimes in math we are dealing with real-valued functions. I suspect that this origin of functions is the reason why multiple return values are not so common. That said, it's easy to emulate them in several ways (by returning a tuple, or by having several output parameters, i.e. ones passed by reference), and some common modern languages (such as Python) natively support this construction.


Algorithm to check Gibbs' Phase Rule I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have a set of species made from a number of components.
Let's number each component $0, 1, 2 ... n$.
So now each species can be described as a set of these components. Each species is unique.
I am given a set of species, and I need to check whether any subset of these species fulfills the following condition: that the number of species in this subset is greater than the number of unique components in this subset.
For example: the set of species {[0, 1, 2], [0, 2], [1, 2], [0, 1]} fulfills the criterion, as the set has 4 species and 3 unique components. The set of species {[0, 1, 2], [0, 2], [1, 2], [0,1], [3,4]} also fulfills the criterion, as a subset of the set fulfills the criterion. The system {[0, 1, 2], [0, 2]} does not fulfill the criterion, as there are 2 species and 3 unique components.
In case it is relevant: there can be many species and components (20) but the number of components per species remains relatively small (2-5)
An easier version of this problem is also of interest to me: I have system which I know does not fulfill the criterion. The question is: if I add this species, will it fulfill the criterion?
This problem is equivalent to determining if a system of equations is over determined.
Edit: The criterion is equivalent to checking if the Gibbs Phase Rule is being violated in a system with only pure solid phases with at least 1 degree of freedom in addition to pressure and temperature. In this situation the number of phases is equal to the number of solids. There has a 0 or positive number of degrees of freedom left in the system or it becomes over constrained, so $0 \geq \text{number of components} - \text{number of species}$

The gibbs phase rule is simply a way of determining whether the system of equations which describes the system will be overdetermined.
As we are talking about (usually) solids, this system of equations looks like $K=A^nB^m...$
If we take the log of both sides, this can be simplified to $\log{k}=n\log{A}+m\log{B}...$.
If we substitute $a=\log{A}, b=\log{B}$ then this becomes a system of linear equations $\log{k}=n*a+m*b...$
Now we can represent this system of linear of equations as a coefficient matrix and then use the Rouche Cappeli Theorem to determine whether the system is overdetermined. Since each species each unique in your system, you simply need to determine if there are any rank deficiencies in your coefficient matrix.
In the first example: {[0, 1, 2], [0, 2], [1, 2]} can be represented as the matrix
$$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 1\\
0 & 1 & 1\\
0 & 1 & 0
\end{bmatrix}$$
Which has a rank deficiency, therefore is overdetermined.


Is there any published paper about automated planning software used in the ESA Rosetta mission? The Rosetta spacecraft has reached a comet in August 2014 and sent a
lander on its surface. It was one of the greatest science news of the year.

Automated Planning and Scheduling techniques are really important in the operations of these kinds of missions. At the last ICAPS there was even an invited talk by one of the staff members involved in the automated planning technologies used in the spacecraft.

Is there any published paper on the planning technologies used in the spacecraft? I've only found this one, but it does not appear to have been published in conferences or journals. Has it or something similar been published somewhere?

Well, as far as I can tell, there was no specific automated planning tool for the Rosetta mission as we understand automated planning systems in ICAPS, which is the most prominent conference on Automated Planning and Scheduling.

The hardest part was to plan the journey from earth to a common location where both the spacecraft and the comet could meet and this was done mainly in two stages: one making the spacecraft orbit around some bodies to save energy (cruise phase) and this was mainly done with astronomical computations; after hibernating for a good number of years, it had to wake up and fly (now using its own power) to meet the comet. There was, additionally, another scheduling problem in the final landing operation of Philae. The last two operations were self-automated.

I asked someone with a better knowledge of Rosetta and this person told me (right now) that there were mainly scheduling systems (as they are also called in the paper you mention) and that most of the operations were self-automated (ie., the main difficulty was that Rosetta was so far that it had to be able to take some decisions on its own, but still it received orders from the ground segment chiefs in ESTEC, Germany).

This said, I do not think we will ever see a paper about how to use PDDL (Planning Domain Definition Language) for Rosetta, or how to use LAMA, Fast-downward, FF (or any temporal PDDL planner) or anything of the kind (I mean, the kind of research we all do at ICAPS) but something instead far more domain-dependent.

On the other hand, it is rather unusual for engineers and scientists at ESA to publish papers at scientific venues such as ICAPS, ECAI (European Conference on Artificial Intelligence), AAAI (Association for the Advancement of Artificial Intelligence), IJCAI (the International Joint Conferences on Artificial Intelligence). They instead submit their papers to the SpaceOps symposium. I found a number of papers there:

Geurts K., Fantinati C., Ulamec S., Willnecker R. Rosetta lander: On-comet operations preparation and planning. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Haddow, CR., Werner D. Mission planning framework - Building the rosetta and bepicolombo planning systems. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Moussi, A. Fronton JF., Gaudon P., Hallouard D., Mangeret M., Delmas C., Lafaille, V., Durand J. PHILAE lander: A scheduling challenge. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Eiblmaier MG., Blake R., Williams A., Lodiot S., Godfrey J., Bartesaghi M. Automating ESA's planetary missions: From concept to conclusion. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Hope this helps,


Prove that Language is not Regular using closure(s) I'm having a really tough time trying to comprehend proofs via closure and pumping lemma.
None of the examples I can find are similar to the one's im looking to prove.  Can anyone explain if I'm totally missing the mark here or is this valid?

Question:
Prove that
$$
L = \{0^x 1^y 2^{x+y} \mid x \ge 0 \text{ and } y \ge1\}\qquad\text{is not Regular.}
$$

Must use Closure(s).
Your "destination" should be
$$
\{ a^z b^z \mid z \ge 1\}, \qquad\text{ which we know is not Regular.}
$$

Start with $L$

(show a sequence of operations and results)

End with $\{a^z b^z\}$ which is not regular

Answer:

If $L$ is regular then $L'$ must be regular
$$
L' = \{(0^x)' (1^y)' (2^{x+y})' \mid x \ge 0, y \ge1 \}
$$
Let $E$ be an element of $L'$ where $E = \{a^z b^z \mid z\ge 1\}$. Since we know $\{a^z b^z \mid z\ge 1\}$ is not regular from using pumping lemma, etc.
$L$ is not regular

What is your " ' " operator? Could it perhaps be the homomorphism $0\rightarrow a, 1\rightarrow a, 2\rightarrow b$? If not, consider this as a hint, since regular languages are closed under homomorphisms.