How to find long trails in a multidigraph I have a certain directed multigraph (a multigraph is graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I want to find its longest directed trails (a directed trail is a directed walk in which all edges are distinct). I.e., I'm looking for long walks with repeated nodes, but distinct edges.
Note that this is an NP-hard problem, otherwise I would have asked for the longest trails, not merely long trails.
My graph has no weights and it is weakly connected (that is, if each edge were converted to an undirected edge, that undirected graph would be connected).
I define walk/trail/path length as the number of edges in the walk.
My current program is based on traversing the graph in a DFS-like manner. If allowed to run for, e.g., half an hour, it produces trails of less than satisfactory length, and I know that longer trails should be possible in that time-budget.
Note that this problem is quite similar to the problem of finding the longest path of a directed graph, but with each edge having a max allowed visits number associated with it, equal to the cardinality of the corresponding edge set in the multidigraph.
In fact, it's possible to transform my problem to the longest path problem by producing the line graph of my graph and then finding its longest paths. However, I'm hoping for a smarter, more efficient solution.
The reason I'm mentioning the digraph longest path problem is that there are certain smart solutions to that problem, but they don't seem to translate to my multidigraph longest trail problem, sadly. In particular, I'm thinking of Miguel Raggi's Arxiv paper "Finding long simple paths in a weighted digraph using pseudo-topological orderings" (1609.07450). Those and other solutions are based on finding the longest path of a DAG subgraph (or, equivalently, some feedback arc set), which seems inapplicable to my problem (unless I do the mentioned line graph transformation), but I'd be happy for somebody here to prove me wrong.
What am I looking for, then?
Either of these two:

some method of finding long trails in my multidigraph, smarter than the naive approach
some method of finding long paths in my multidigraph's line graph; but it should be more efficient than just looking for an arbitrary digraph's longest paths, i.e., it should take into account the fact that the graph that is being searched through is a line graph.

Some characteristics of my graph
It's got around 500 nodes and around 20000 edges. If the multiple edges are accounted for, the graph's got around 160000 edges.
Some characteristics of my graph's condensation
I don't know if the info on the condensation is relevant, but it might be. See the Wikipedia page for strongly connected components for definitions and examples of graph condensations: https://en.wikipedia.org/wiki/Strongly_connected_component
There are less than 200 strongly connected components (equivalently, the condensation has less than 200 nodes), and the condensation's got around 220 edges. A certain SCC consists of more than 300 original nodes, while the other SCCs only have a single original node.
Info about node in-degree and out-degree over all nodes
This too, is of dubious importance, but it may be useful. The images are just thumbnails which link to the full-sized plots (made with Vega Lite):

Note about the scatterplots: each point in the scatterplots is "transparent", so that if there's only one datapoint in the same point of the plot it's displayed less prominently than if there are multiple in the same position.

Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of any edge in the cycle, so looking for cycles in which all edges have large multiplicity may be a good strategy:

Order edges in the big SCC in decreasing order by multiplicity. Call this list of edges $X$. (Note: Each edge appears in $X$ just once, regardless of its multiplicity.)
Set $Y$ to be an empty list of edges.
If no edges remain in $X$, go to 7.
Choose the edge $e$ with highest multiplicity remaining in $X$. Remove it from $X$ and add it to $Y$.
Test whether $Y$ now contains a cycle (since this cycle must contain $e$, this check can be done quickly using a union/find data structure): If so, let $Z \subseteq Y$ be the edges in this cycle. Add the pair $(Z, m)$ to the set $C$, where $m$ is the minimum multiplicity of any edge in $Z$, clear out $Y$ and start over (recurse) with $X\setminus Z$.
Otherwise, go to 3.
At this point, we have a set of edge-disjoint cycles in $C$, as well as the maximum number of times each can be completely traversed. Note that if $(Z, m) \in C$, then the cycle $Z$ can be entered at any of its vertices, traversed $m$ times, and then exited at the same vertex; or entered at any vertex, traversed $m-1$ times, then (possibly after a further partial traversal) exited from any vertex, giving us some flexibility.
Find the vertex $v_1$ that is shared by the largest number of cycles in $C$; let these cycles be $C_1 \subseteq C$. If $C_1 = C$ then stop here: We can start at $v_1$ and traverse each cycle the full number of times in any order.
Otherwise, find the vertex $v_2$ that is shared by the largest number of cycles in $C\setminus C_1$ and is adjacent to $v_1$. Repeat this for $v_3$, etc., until $C$ is exhausted.
Starting at $v_1$, for each $i$ in increasing order, and for each cycle $C_{ij} \in C_i$ (in no particular order), add either $m_{ij}$ or $m_{ij}-1$ traversals of $C_{ij}$ to the the trail, whichever is larger and still allows us to stop at $v_{i+1}$ in preparation to begin traversing the following set of cycles.

Since the procedure is fairly quick, it may be worthwhile to rerun it many times, choosing a different order of edges each time, and pick the best overall.


Why clear the child's and not the parent's mark in Fibonacci heaps? According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the resulting merge. I just don't get it, why should we bother clearing this mark? In particular:

What happens if we leave their marks as is?
Why clear the child's mark rather than the parent's?

A reminder of FIB-HEAP-LINK:

FIB-HEAP-LINK($H$, $y$, $x$)

Remove $y$ from the root list of $H$
Make $y$ a child of $x$, incrementing degree[$x$]
Set mark[$y$] to FALSE

To understand Fibonacci heaps, it may help to understand binomial heaps first.

A binomial heap is a forest of heap-ordered binomial trees. A binomial tree of degree k is a node whose children are binomial trees of degree k-1, k-2, ... 0. Note that the number of nodes in a binomial tree of degree k is $2^k$.

If you never do any decrease key operations (or delete operations of nodes other than the minimum), then the Fibonacci heap is a binomial heap.

Conceptually, a Fibonacci tree is a binomial tree which allows for a controlled amount of "damage".

The degree of a Fibonacci heap node is redefined to be the number of children that it has. The structural constraint is designed so that the tree can tolerate a certain amount of deviation from the binomial heap constraint. Most textbooks don't precisely define it, but the key property is this:

  Suppose that x is any node in a Fibonacci heap. If you order its children in the order that they were linked to x, then the ith child has a degree at least i-2. If it has degree equal to i-2, the node must be marked. If it is greater than i-2, then it may or may not be marked.

In particular, a mark signifies that a node may be one degree too "small" for its parent. (Note that this property is almost lemma 1 from the original paper.)

The first thing to notice is that when we cut a node, we unmark it. The reason for this should be obvious: it has no parent, so it can't possibly be too "small".

Now think about the link operation. We only ever link two nodes together if they have the same degree. Let's suppose that d is the degree of x and y, and we want to make x the new parent of y.

Since we are adding a child to x, so this changes the degree of x to d+1. The node y is the (d+1)th child linked to x, so to preserve the structural constraint, it must be marked if it has degree d-1. However, by construction it has degree d. It is not too "small", so we unmark it.

Of course, the structural constraint is preserved whether or not y is marked. Why, then, do we clear the mark? Intuitively, it's because encountering a mark during an unlink operation triggers a cascading cut. We want to avoid those, so we want to have as few nodes marked as possible. At any point, if we can tell that a node doesn't have to be marked, we make sure it's not marked.

Did that help?


Construction of binary random variable We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$.
Each of the 4 elementary events has a probability $1/4$.
how can I construct 3 binary random variable $x_1$, $x_2$, $x_3$ about this event space, which are 2-fold independent, but not independent.

Let $E = \{ZZ,WW,ZW,WZ\}$. A binary random variable is a mapping $X\colon E \rightarrow \{0,1\}$. The probability of an event, say $X=0$, is defined as
$$ \Pr[X = 0] =\frac{|\{e \in E : X(e) = 0\}|}{4}. $$
For example, let $C_1(ZZ)=C_1(ZW) = 0$, $C_1(WZ)=C_1(WW) = 1$. Then $\Pr[C_1=0]=1/2$.

Two (binary) random variables $X_1,X_2$ are independent if for every $b_1,b_2 \in \{0,1\}$,
$$\Pr[X_1 = b_1 \text{ and } X_2 = b_2] = \Pr[X_1 = b_1] \Pr[X_2 = b_2]. $$
For example, if $C_2(ZZ) = C_2(WZ) = 0$ and $C_2(ZW) = C_2(WW) = 1$, then you can check that $C_1$ and $C_2$ are independent, by checking that $\Pr[C_1 = b] = \Pr[C_2 = b] = 1/2$ and $\Pr[C_1 = b_1 \text{ and } C_2 = b_2] = 1/4$. On the other hand, $C_1$ and $C_1$ are not independent since $\Pr[C_1 = 0 \text{ and } C_1 = 0] = 1/2$.

Similarly you can define when more than two random variables are independent. It should be clear that there are no three binary random variables $X_1,X_2,X_3$ with $\Pr[X_1 = 0] = \Pr[X_2 = 0] = \Pr[X_3 = 0] = 1/2$ which are independent, since that would imply $\Pr[X_1 = X_2 = X_3 = 0] = 1/8$, which is impossible (the only values that $\Pr$ can obtain are $0,1/4,1/2,3/4,1$). On the other hand, any three constant random variables are independent.

A set of random variables is $k$-wise independent if any $k$ of them are independent. The question asks you to find three random variables $X_1,X_2,X_3$ so that any two are independent, but all three aren't. My hint is that there is a solution with $X_1 = C_1$ and $X_2 = C_2$.


What is the meaning of phenotype could be represented by a number of different genotype I found this sentence in multiple sources but I didnt understand
in one thesis

With a neutral representation each phenotype could be represented by a
number of different genotype

and in another thesis

it may be possible for neural networks with functionally equivalent
topologies to be represented by a number of different genotypes

And in another source

the genotypical representation:
010 001 100 0000 1100 0000 0000 0000 0011 0100 0000 0000
However, the graph (phenotype) can also be represented by a number of
different genotypes. E.g:

010 001 100 0110 1100 0000 0011 0000 0011 0100 0000 0000

010 001 100 0000 1100 0000 0000 0000 0011 0100 1110 0100

Up to my understanding the first phenotype is the representation of the graph, so why the second or third phenotypes are different representations. how did we come up with the bold genotypes

The same function can be described in several ways.
If you're familiar with finite automata, then you should know that the same regular language ("phenotype") can be represented by many different finite automata ("genotype").
The same holds in many other cases, unless you choose an encoding which guarantees that every function has a unique description. It is not clear whether this is even desirable. For example, the genetic code has some redundancy which causes the same DNA sequence to encode the same proteins.


Alternative proof for the undecidability of $A_{TM}$ The proof of the undecidability of $A_{TM}$ in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

*Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179. On this page, Sipser uses the term halting problem for the language $A_{TM}$. The proper name for this language is acceptance problem, see the footnote on page 188.

There is no paradox. We have made an assumption, namely that the halting problem is solved by some Turing machine, and using it reached a paradox. Hence our assumption must be wrong. In the same way, Russell's paradox is a proof that the collection of all sets not containing themselves is a proper class.

In both cases, the paradox is solved by concluding that some object cannot exist. In the case of Russell's paradox, we can give a description of the object - properties it satisfies - but it doesn't exist as a set. In the same way, the halting problem is definable, but there is no Turing machine that accepts it.

In recursion theory we can breathe life into it by making it an oracle, and consider the implications. Similarly, in set theory we can consider relativized versions of Russell's set (relativized to some set "sub-universe"), though due to the axiom of regularity the result isn't interesting.


Algorithm to use for a TSP variant What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many times we want on every vertices and/or edges. Let's say, on my graph, that I want the minimum distance for visiting every blue node. What algorithm and heuristic would you recommand me? An approximation running in reasonable time would be acceptable.

For this example, this is an undirected graph, the vertices are points in the plane and the cost of an edge is the distance between its endpoints.

The minimum weight connected subgraph that includes all the blue vertices is known to be a tree, called a Steiner tree.  A depth-first search of the tree will give you a route that visits every blue vertex and whose length is twice the weight of the Steiner tree, since you walk along each edge of it exactly twice.  Hence, DFS of a Steiner tree is at most twice the length of the shortest route.

However, computing Steiner trees of general weighted graphs is NP-hard (the decision version was one of Karp's 21 problems). Sanjeev Arora has shown there's a polynomial time approximation scheme for the the Euclidean version of the problem, which is close to the case you're interested in: paper. The Euclidean version corresponds to your version where every possible edge is present (i.e., you have a collection of points in the Euclidean plane and there's an edge between every pair of points, with the weight of the edge equal to the distance).


Very divisible subsets I've recently come across the following problem.

We're given up to $10^4$ distinct positive integers $a_1,\dots , a_n$, each of them below $10^6$. Let's call a subset $S \subset \{a_1,\dots,a_n\}$ a very divisible subset if any number in this subset divides the product of other numbers in this subset.

The task is to find the largest such subset. It is guaranteed that there is at least one with at least $3$ elements. If there are several such subsets we can output any of them. For example if we're given numbers $2, 3, 4, 5, 7, 8, 9, 10$ then the algorithm might output $2, 4, 5, 8, 10$.

It's neither a homework nor an ongoing contest. I'm just curious how to solve it. Unfortunarely for now i can't see any solution better than brute force through all the subsets. And such approach is unfeasible under given limitations. Any ideas will be highly appreciated. Thanks in advance.

P.S.
Here's an original statement of this problem: https://www.e-olymp.com/en/problems/7331

Here is an idea. By factoring the numbers, we are reduced to the following problem:

  Given a set $S$ of vectors in $\mathbb{N}^k$, find a maximum-size subset $T \subseteq S$ such that for every $x \in T$ we have $x \leq \sum_{y \in T - x} y$ (pointwise).

If there is some $x \in S$ and some coordinate $i \in [k]$ such that $x_i > \sum_{y \in S - x} y_i$, then clearly $x_i$ cannot belong to any such set $T$, and we can simply remove it. Keep removing such elements from $S$ until no such elements exist. Then for every $x \in S$ and $i \in [k]$ it is the case that $x_i \leq \sum_{y \in S-x} y_i$, and so the filtered set $S$ is the unique solution.

Let me demonstrate this solution using your example $2,3,4,5,7,8,9,10$. Only 4 prime factors appear here (2,3,5,7), and converting $2^x3^y5^z7^w$ to the vector $xyzw$, we obtain the following vectors:
$$
\begin{align*}
2 &= 1000 \\ 3 &= 0100 \\ 4 &= 2000 \\ 5 &= 0010 \\
7 &= 0001 \\ 8 &= 3000 \\ 9 &= 0200 \\ 10 &= 1010
\end{align*}
$$

We remove 7 due to the 4th coordinate. We then remove 9 due to the 2nd coordinate. We then remove 3 due to the 2nd coordinate. We cannot remove any more numbers, and so are left with the answer 2,4,5,8,10.

The challenge is to implement this greedy algorithm efficiently, which you can do by maintaining the sum of all elements left in the set, and using several priority queues (though perhaps there is a better solution). Details left to you.


Does the databus size matter for determining the range of the memory addresses? If you have byte addressable memory, does it matter if you have a 32 bit or 64 bit databus for the range of the memory addresses for the words of the memory?

E.g.
: Assume a 32-bit word. If you have a processor connected to a byte addressable $2^{32}$ byte memory,

Would the address of the lowest word be 0 and the address of the highest word simply be $2^{32}-4$  (0xFFFFFFFC), regardless of whether your databus size is 32 bit or 64 bit?

What difference would it make when you assume a 64-bit word or a 16-bit word?

On most general purpose CPUs since the '70s, addresses are byte addresses.
This includes 6800, 680X0, PowerPC, x86, ARM, MIPS, SPARC, SuperH, Z80, PA-RISC...

There are sometimes exceptions with DSPs that are not meant for processing bytes. (example : Analog Devices SHARC)
Some small embedded CPUs may also have different addressing, or separate address spaces for instructions (example : Microsemi PIC)
Some CPU support address spaces where data is aliased and expanded. For example mapping each bit at a different byte address (example : Some ARMs)

The actual width of the data bus is not directly related to the CPU internal architecture, wether it is a 8bits, 16bits or 32bits CPU.

For example:

The MC68008 was a 16/32bits CPU with a 8 bits bus.
The G3/G4 PowerPCs (PPC603, MPC755, MPC7450...) are 32bits CPUs with a 64bits data bus.

With a 32bits CPU, aligned 32bits word adresses are 0000_0000, 0000_0004, 000_0008 ... to ... FFFF_FFF0, FFFF_FFF4, FFFF_FFF8, FFFF_FFFC.

Some CPUs can do unaligned accesses, usually slower than aligned ones. An example : x86.

In that case, you could access a 32bits value at address 0000_0001.


General Number Field Sieve Big O Clarification This paper states that the general number field sieve is of order:

$$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$$

However several sources (e.g. Wolfram) give it as:

$$O\left( \exp\left((64/9)^{1/3}\,(\log n)^{1/3}\,(\log\log n)^{2/3}\right) \right)$$

To my knowledge L-notation and big O notation are exactly the same, so is this paper incorrect, or am I missing something?

It also gives the binary length of the number being factored, $n$, as being converted from its decimal length via:

$$n=k\,\ln(10)$$

I'm aware that if you can multiply by a constant factor then how the complexity is expressed doesn't matter (e.g. you can pick any log base so long as you're consistent), but since the correct way of doing this would be:

$$n = \lfloor k\, \log_2(10)\rfloor + 1$$

Is their stated conversion to $n$ acceptable?

There is a small difference between these two:

$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$. Here $n$ is a number of bits needed to represent given number $N$.
$O\left( \exp\left((64/9)^{1/3}\,(\log N)^{1/3}\,(\log\log N)^{2/3}\right) \right)$. Here the number $N$ itself is used in notation.

This is true since length of number grows logarithmically of the number itself. Just put $n$ instead of $\log N$ or vice versa and you see that they are equal.

In terms of big O notation constants are uninteresing, so, base of logarithm also is uninteresting. That's why it doesn't make sense whether you interpret number in decimal or binary or any other (except unary) system.

$n=k\,\ln(10)$: here  $\ln(10)$ is constant and we can get rid of it. Also, $k$ depends linearly on $n$, so $k = O(n)$.

$n = \lfloor k\, \log_2(10)\rfloor + 1$: and here both $\log_2(10)$ and $+1$ are removed when written as big O: it still equals $O(n)$.


The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable? I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they mention that?

I ask this before I've recently found a paper where such a type system is presented and an algorithm based on the search of a fixed-point allows type inference for the type system. The trick is that you can fix a number $k$ of iterations for the search to maintain decidability of such a type system. If you cannot find a fixed point you can use the usual ML rules to try to type the program disallowing polymorphic recursion.

The authors proved that, given a well-typed expression $s$ there exist $k \in \mathbb{N}$ such that you can type the expression with the correct type limiting the number of iterations to $k$.

Now, I think this implies semidecidability of type inference with polymorphic recursion in such a case. If we allow $k = +\infty$ what would happen is that the algorithm would always terminate for well-typed expression, but could not terminate for non-well typed expressions.

Am I correct in this conclusion or is there some hidden issue I didn't understand?

The answer you gave is right, but I'd like to stress the relationship between the two terms.

A formal language is decidable if and only if there exists an algorithm which correctly accepts or rejects every input in finite time. We also say it's computable.

A formal language is undecidable if and only if it is not decidable.

A formal language is semidecidable if and only if an algorithm exists that recognizing an input that is in the language. In particular, all decidable languages are semidecidable! However the halting problem is an example of a semidecidable language that is also undecidable. The complement of the halting problem is not even semidecidable.

We say type inference is undecidable rather than semidecidable (even though both characterizations are true) because the former is usually more relevant.


Can the Dijkstra algorithm work with a negative arc? When there is no negative circle in the graph?
And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?

The most common implementation of Dijkstra's algorithm (for example, the one you find on Wikipedia), will not work correctly in this case, because once a node is extracted from the priority queue, its label (distance from the source) will never be revised.  Consider the following example: there are four nodes $a,b,c,d$ (node $a$ is the source), and four arcs: $a \rightarrow b$ with cost 10, $a \rightarrow c$ with cost 4, $b \rightarrow c$ with cost -8, and $c\rightarrow d$ with cost 1. With the classic implementation, Dijkstra's algorithm will extract node $c$ from the queue before node $b$, and hence will report 5 as the length of the shortest path from $a$ to $d$, while the correct answer is 3.

There is, however, a conceptually simple modification that guarantees correctness of the algorithm on any instance with negative weights but no negative cycles. You simply put back a node in the priority queue after you discovered a shorter path to it. In the above example, after the node $b$ is expanded we discover a shorter path to $c$, and put $c$ back in the queue. Expanding $c$ one more time allows to find the correct path to $d$.

Note however that, while correct, the running time of this "revised Dijsktra" is no longer the same as the original implementation, because now we may have to expand the same node multiple times. In fact, the running time can be exponential in the number of nodes.


What is the purpose of M:N (Hybrid) threading? In other words, what advantages does Hybrid threading have over 1:1 (kernel only) and N:1 (user only) threading?

This is a follow-up to What is the difference between user-level threads and kernel-level threads?

I think hybrid threading is very similar to a thread pool.

In thread pool, you are using $N$ kernel threads to execute $M$ “tasks”, where $M$ can be much higher than $N$. The advantage over using one thread for each task (kernel only threading) is that you consume less resources, like memory (both virtual and physical) and kernel objects (at least in the specific case of Windows threads, but I imagine other OSes are similar in this regard). You also get less context switches, which increases performance (in the ideal case, where you have as many running threads as you have processors, you may have almost no context switches).

The advantage over user only threading is that you can take advantage of multiple CPUs or multiple CPU cores. And if one task blocks, you can create another kernel thread to use the available CPU more efficiently.

So, you get the advantages of both approaches, at the expense of some additional user-mode scheduling.

A disadvantage over kernel only scheduling is possibly bigger latency: if all the threads in the pool are busy and you add new short task, you may wait a long time before it starts executing.


Store array of sequential intervals I need to store a list of sequential intervals.
So for example I would to say:

{0-5} = a
{6} = b
{7-10} = c

and so on.
I need to add and remove items from this list:
.insert(d,{1,3})

will make our array:

{0} = a
{1-3} = d
{4-5} = a
{6} = b
{7-10} = c

Morehover you may need to check what items cover a range:
.itemsIn({6,8}) will return b,c.

I can keep an array with pointers to the same object instance for each value in a range but I suppose I can do a better job.
Interval tree?

If every interval begins immediately after the previous one ends, then you only need to store the start point of each interval (and the endpoint of the very last interval), which you can do with a self-balancing binary search tree.  Inserting and deleting intervals is then $O(\log n)$-time, and identifying the intervals overlapping a query interval is $O(\log n + k)$-time, if the answer includes $k$ intervals.


Prove $\log(n^2 + 1)$ is $Θ(\log n)$ This is a homework problem and I'm not sure if I am doing it correctly.

  Show that $\log(n^2+1)\in \Theta(\log n)$.

I got:

$$ \log (n^2) \leq \log(n^2+1) \leq \log (n^2+n^2) $$
$$ 2\log n \leq \log(n^2+1) \leq \log(2\cdot n^2) $$
$$ 2\log n \leq \log (n^2+1) \leq \log 2 + \log(n^2)$$
$$ 2\log n \leq \log(n^2+1) \leq 1 + 2\cdot\log n$$

I'm not sure if I have proved it according to the definition that a function $f(x)$ is in  $Θ(g(x))$ if there exist positive constants $a,b$, and $n_0$ such that $a\cdot g(x) ≤ f(x) ≤ b\cdot g(x)$ for all $n > n_0$.

I feel like I did something wrong here.

In order to prove that $\log(n^2+1) \in \Theta(\log n)$ according to your definition, you have to produce $a,b,n_0$ such that $a \log n \leq \log(n^2+1) \leq b\log n$ for all $n \geq n_0$. This is not what you did. What you have shown is some other inequality.

To help you in future such questions, here is a complete proof. We choose $a = 2$, $b = 3$, and $n_0 = 2$. So we have to show that for $n \geq 2$,
$$
2\log n \leq \log(n^2+1) \leq 3\log n.
$$

The first inequality follows from
$$
\log(n^2+1) \geq \log(n^2) = 2\log n.
$$
You did that part correctly.

The second inequality follows from
$$
\log(n^2+1) \leq \log(n^2+n^2) = \log(2n^2) \leq \log(n^3) = 3\log n.
$$
This is the part you did incorrectly.


Decision problem that can be verified but not run in n^2 time A much much weaker idea similar to the P=NP question, is there a decision problem that can be verified in $O(n^2)$ time, but it can be proven that there is no algorithm that decides it $O(n^2)$ time?

The answer depends a lot on the model of computation.

On one extreme: in the decision tree model, many lower bounds can be proven.  For instance, consider the 3SUM problem.  You can verify an alleged solution to the 3SUM problem in $O(n)$ time, but it's conjectured that no algorithm can solve the 3SUM problem in $O(n^{2-\epsilon})$ time for any $\epsilon>0$.  One can prove this holds in some version of the algebraic decision tree model; one can prove that any algorithm to solve it in this model must take $\Omega(n^2)$ time.  This provides a gap of $O(n^2)$ vs $O(n)$ for solving vs verifying solutions, if the verifier is limited to the algebraic decision tree model.  This is a pretty limited result; in this case, the model means that we're restricting attention to algorithms of a particular form.  So, it doesn't rule out the possibility of some other algorithm (that does something weird) being faster.

On the other extreme: if we allow arbitrary (non-uniform) boolean circuits, then there is no explicitly stated function $f$ on $n$ bits where we can currently prove that every circuit for computing $f$ needs $\ge 3.1n$ gates.  In other words, this is saying that we have no clue how to prove lower bounds for circuits.  Roughly speaking, we have no known result of a problem where we can prove that solving it requires circuits of size $\omega(n)$.  See, e.g., https://cstheory.stackexchange.com/a/8005/5038 and https://cstheory.stackexchange.com/q/21400/5038.  So, given our current state of knowledge, we have no hope of proving a result like that if the model of computation is unrestricted boolean circuits.


What is meant by "solvable by non deterministic algorithm in polynomial time" In many textbooks NP problems are defined as:

  Set of all decision problems solvable by non deterministic algorithms in polynomial time

I couldn't understand the part "solvable by non deterministic algorithms". Could anyone please explain that?

Adding to Shitikanth's answer,
a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an arbitrary choice among the possibilities can be made in a given run of the program. Thus multiple runs of the same algorithm on the same input can result in different outputs.

The point of using a non-deterministic algorithm is that it can make certain guesses at certain points during its computation. Such algorithms are designed so that if they make the right guesses at all the choice points, then they can solve the problem at hand.

A simple example is primality testing. To decide whether a number $N$ is not prime, one simply selects non-deterministically a number $n\le\sqrt{N}$ and checks whether $N$ is divisible by $n$. For any composite number, this algorithm finds a factor of the number by making the right guess.

The polynomial time part means that if the nondeterministic algorithm makes all the right guesses, then the amount of time it takes is bounded by a polynomial.


Check if a lambda constructor is well-typed In basic type inference for -calculus with parametric polymorphism à la Hindley–Milner,
when can we say that we cannot give a type to a lambda constructor?
For example
$$(λx.λy.y(x\ y))(λz.z)$$

A term $M$ is well-typed if and only if there is a type derivation that leads to a judgement of the form $\Gamma \vdash M : \tau$ for some context $\Gamma$ and some type $\tau$. (I use the word “type” in its general sense which can include quantified variables; in the terminology commonly used with Hindler-Milner, that's a type scheme.) So, to prove that you cannot give a type to a lambda term from first principles, you prove that there is no type derivation that leads to such a judgement.

Hindley-Milner has a nice property in this respect: it's syntax-directed, i.e. it's presented as a set of deduction rules such that for any term, there is a single rule that can be used to end a deduction of this term. (Being syntax-directed is actually a property of a presentation of the type system, not a property of the type system. In this post, I use the classical syntax-directed presentation which builds generalization into the let rule, rather than having a separate rule for generalization.)

Another nice property (shared by almost every type system) is that unused variables can always be removed from the context. So for example, if $(\lambda x y.y (x y)) (\lambda z.z)$ is well-typed, it must have a type derivation ending with the App rule and, since the term has no free variable, an empty context:
$$
\dfrac{\vdash (\lambda x y.y (x y)) : \tau_1 \to \tau_0 \qquad
       \vdash (\lambda z. z) : \tau_1}
      {\vdash (\lambda x y.y (x y)) (\lambda z.z) : \tau_0}
$$

You can of course make use of any theorem that you already know. In particular, the principal typing theorem can be useful: if a term is well-typed then all of its types are instances of a particular one. For example, the identity function $(\lambda z.z)$'s possible types are all instances of $\forall \alpha. \alpha \to \alpha$. Similarly, it's easy to see that the function $(\lambda x y.y (x y))$ has the most general type $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$.

In order to find a type for $(\lambda x y.y (x y)) (\lambda z.z)$, we saw above that we need to find types $\tau_0$ and $\tau_1$ such that $\tau_1 \to \tau_0$ is an instance of $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$ and $\tau_1$ is an instance of $\forall \alpha. \alpha \to \alpha$. This means that there must exist base types $T_1$, $T_2$ and $T_3$ which satisfy the equations
$$ \begin{align}
\tau_1 &= \forall \alpha \beta \gamma. (T_2 \to T_3) \to T_2 \\
\tau_0 &= \forall \alpha \beta \gamma. (T_2 \to T_3) \to T_3 \\
\tau_0 &= \forall \alpha \beta \gamma. T_1 \to T_1 \\
\end{align} $$
Hence $T_3 = T_1 = (T_2 \to T_3)$. But this is impossible due to the structure of types: a type can't be a strict subterm of itself. Therefore the premise of was wrong: the term $(\lambda x y.y (x y)) (\lambda z.z)$ is not well-typed.

chi's answer shows how to use another theorem about Hindley-Milner to shorten the proof: subject reduction, i.e. the property that if a term is well-typed and it reduces to another term then that other term also has the same type. Since $(\lambda x y.y (x y)) (\lambda z.z) \to_\beta^* \lambda y. y y$, if the original term has a type then so does $\lambda y. y y$. By contraposition, if $\lambda y. y y$ is not well-typed then neither is the original term. You can show that $\lambda y. y y$ is not well-typed by a shorter application of the methodology above: note that if it is well-typed, it must be an application of the lambda typing rule, which leads to a type equation of the form $T_1 \to T_1 = T_1$, which has no solution for the same reason as before.

There are, of course, other type systems where the term in question is well-typed. These type systems must have some additional ways of typing terms that Hindley-Milner doesn't have. I'll give two examples:

If you extend the syntax of types to allow them to be recursive (as with ocaml -rectypes), then the reasoning about the type equation having no solution because a type can't contain itself breaks down, and indeed both $\lambda y. y y$ and the original term are well-typed in this system. For example, the most general type of $\lambda y. y y$ is $\forall \alpha \beta [\alpha = \alpha \to \beta]. \alpha$.
If you add a rule that allows intersection types:
$$
  \dfrac{\Gamma \vdash M : \tau_1 \qquad \Gamma \vdash M : \tau_2}
        {\Gamma \vdash M : \tau_1 \wedge \tau_2}
  $$
then the reasoning above breaks down because the presentation of the type system is not type-directed. The intersection rule can be used with any language construct. With this type system, $y : \alpha \wedge (\alpha \to \beta) \vdash_{\wedge} y : \alpha$ and $y : \alpha \wedge (\alpha \to \beta) \vdash_{\wedge} y : \alpha \to \beta$ and so $\lambda y. y y$ has the type $\forall \alpha \beta. (\alpha \wedge (\alpha \to \beta)) \to \beta$. The original term is also well-typed. With a rule that departs so radically from being syntax-directed, you might think that it's difficult to prove that a term is not typable, and you'd be right: the intersection rule is so strong that it causes all strongly normalizing terms to be well-typed. Conversely, intersection types with base types (but without quantifiers or a top type) only allow strong normalizing terms, so to prove that a term is not typable in that system, it's sufficient to prove that a term is not strongly normalizing.
See Does there exist a Turing complete typed lambda calculus?) for more information about intersection types.


Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs?

Long version and some background:

Before anyone asks, YES, it is a homework and I am not here to find an answer, but only clues to help me get this question right !

I'll translate the question from French :

  We call a universal program (also called interpreter) a program that
  accepts, as an input, another program and simulates it to produce the
  output of this simulated program. A universal program can also be used
  to simulate programs written in this very same language or in another
  language.

  You can suppose, using Gödel's coding, that the program to be
  simulated is given to the universal program in the register r1, and
  the input on which this program but be simulated in the register r2.
  The coding of the program could simply give out the characters of the
  program to be simulated in a table as well as its input registers in
  another table.

  Answer the following questions:

  a. It is possible to write a universal loop program for if-then
  programs?

  b. Is it possible to write a universal loop program for loop
  programs?

  c. Is it possible to write a universal while program for while
  programs? To reach a satisfying answer/proof lever, you could use
  the Church-Turing thesis.

Now the question, is where do I start with this ? My head's going in every direction at the same time, I'm just going crazy.

NOTES :

if-then programs are defined like this :

We consider a if-then program to be defined like a loop program, excepted that there are no loops, but an instruction "if rj then []" (rj is the register "rj", the j'th register)

I know for sure this has something to do with imbricated loops...

Any clues would be greatly appreciated !

Thanks a lot

For part (a), there are (at least) two approaches:

Outline a LOOP program which simulates a given IF program. Seems pretty messy.
IF programs can be simulated by a WHILE program, i.e. they are recursive. Moreover, the running time of such a simulator is very manageable. A recursive function with a primitive recursive bound on the running time is primitive recursive, and so implementable as a LOOP program.

For part (b), there are again two approaches (leading to the same result):

Suppose that you had a universal LOOP program. Try running the argument used to prove that the halting problem is undecidable, and see what you get.
The running time of every LOOP program is on some level of the primitive recursive hierarchy, and the latter is strict and has infinitely many levels. Consider the running time of a universal LOOP program and see what happens.

Part (c) is about universal Turing machines.


Algorithm - Checking if an unconnected graph is cyclical I have an algorithm for finding if there is a cycle in a connected graph by depth first path creation of a graph until there is a duplicate in the path. Beside simply starting this algorithm at all possible points for an unconnected graph, how can I find if an unconnected graph is cyclical in good time and in a simple way?

As part of the cycle checking, you already need to keep track of which vertices have been visited. So just restart at the first unvisited vertex each time you exhaust a component.


How do I calculate offset from virtual address? If the page size is 4Kbyte and the physical size of the main memory is 32Kbyte.
Now if I consider virtual address of 37064..
The page number is then 37064/4096 = 9
And according to my diagram page 9 is mapped to frame 6
But how do I calculate the offset? According to exercise it should be 200.
Thank you

The page size indicates how much bits represent the offset in the physical frame. In this case you have pages of 4KB that means you need 12 bits because 2^12 = 4096. The offset in the physical frame always starts at the least significant bits. So for your example with
37064 = 0b1001 0000 1100 1000,

0000 1100 1000 = 200 in decimal is the offset in the physical frame. Since you have only one level of page tables, the rest of the bits to the left represent the actual physical page. You should not see it as a division even though it works. So the offset in the page table is 1001 = 9.


How to find the language of a CFG from Production rules I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid bb
\end{align}
How can I find the language it describes?

The idiom "$X \to YX \mid \epsilon$" (or "$X \to XY \mid \epsilon$") means that $X$ generates $Y^*$ (assuming there are no other productions for $X$). This means that your grammar generates $A^*$. You know what $A$ generates. Putting everything together, you should be able to find a very concise description of the language generated by your grammar.


Representing chained XOR operations as linear inequalities I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met:

$x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$

where $\oplus$ is the binary xor operator.

The answer to this question shows how to represent $y = x_1 \oplus x_2$ with linear inequalities. In an answer to this question there is an attempt to generalize the representation to more than two inputs, but the two answers seem to be inconsistent, since the latter doesn't even use inequalities.

So, the question is: how can I represent $y = x_1 \oplus x_2 \oplus \cdots \oplus x_n$ as set of linear inequalities?

Introducing another integer variable $t$, you can express the condition $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ as in the following canonical form.
$$x_1 + x_2 + \dots + x_n - 2t \le 1$$
$$- x_1 - x_2 - \dots - x_n + 2t \le -1$$
$$(x_1, x_2, \cdots, x_n) \le (1,1,\cdots,1)$$
$$(x_1, x_2, \cdots, x_n, t) \ge \mathbf 0$$
$$(x_1, x_2, \cdots, x_n, t) \in \Bbb Z^{n+1}$$
You can also replace the first two inequalities by the following equality.
 $$x_1 + x_2 + \dots + x_n - 2t = 1$$
In other words, you can actually eliminate one of $x_1, x_2, \cdots, x_n$ by replacing it with $t$.

Note $t$ is an integer not bounded from above. However, you can also bounded it by the following inequality, which is implied by the existing inequalities.

$$0\le t\le \lceil \frac{n}2\rceil-1$$

The idea is that $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ if and only if the number of $x_i$'s that are 1 is odd. This answer is essentially the same as the answer you mentioned.


How do I construct a doubly connected edge list given a set of line segments? For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \right \}$. Construct a DCEL data structure for the planar subdivision, describe an algorithm, prove it's  correctness and show the complexity.

According to this description of the DCEL data structure, there are many connections between different objects (i.e. vertices, edges and faces) of the DCEL. So, a DCEL seems to be difficult to build and maintain.

Do you know of any efficient algorithm which can be used to construct a DCEL data structure?

Data structure (conventions consistent with the Wikipedia article):

struct half_edge;

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
};

struct face {
    struct half_edge *rep;  /* rep->left == this */
};

struct half_edge {
    struct half_edge *prev;  /* prev->next == this */
    struct half_edge *next;  /* next->prev == this */
    struct half_edge *twin;  /* twin->twin == this */
    struct vertex *tail;     /* twin->next->tail == tail &&
                                prev->twin->tail == tail */
    struct face *left;       /* prev->left == left && next->left == left */
};

  Algorithm

  For each endpoint, create a vertex.
  For each input segment, create two half-edges, and assign their tail vertices and twins.
  For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.
  For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.
  Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e->twin->next = e and e->prev = e->twin). The next pointers are a
  permutation on half-edges.
  For every cycle, allocate and assign a face structure.


How to deal with questions having two or more asymptotic notations The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions,

Let $f(n)$ and $g(n)$ be two functions from $\mathbb{N}^+$ to $\mathbb{R}^+$. Prove or disprove the following assertions. To disprove, you only need to give a counter example for functions $f(n)$ and/or $g(n)$ which make the assertion false. Consider the following.

$$\Omega(\Theta(f(n))) = \Omega(f(n))$$

According to me the answer is false in this case, my reasoning is that whenever we say $f(n)=\Theta(g(n))$ we are saying that $f(n)$ will always lie between the limits of $g(n)$.
Here, let's say $x(n) = \Theta(f(n))$ so it will always lie between the function $f(n)$ then we take $\Omega(x(n))$ which would mean that $y(n)$ will always be greater than $x(n)$, and on the right hand side we compare it to some $a(n)$ which is equal $\Omega(f(n))$ meaning that $a(n)$ will always be greater than $f(n)$. Hence we cannot say correctly if the relation will hold, it may or may not be true.

Is this the correct way of looking at the problem, is there a better way to solve these questions?

No, this is not the right way to think about this question. To get you on the right track notice that $f(n) \in \Theta(f(n))$ no matter what. This should give you the right intuition. However, you can't prove equality with just one function taken from $\Theta(f(n))$ you have to consider an arbitrary function.

If you work through carefully (I won't give you the step-by-step since active learning is important), you will see that $\Omega(\Theta(f(n))) = \Omega(f(n))$. To test your understanding after you figure this out, make sure that you can also show that $\Omega(O(f(n))) \neq \Omega(f(n))$.

The intuition you should keep in mind (that you have to make rigorous by carefully understanding this table) is that $\Omega$ is kind of like $\geq$, $O$ is kind of like $\leq$ (for lower case of both, make them strict inequalities), and $\Theta$ is kind of like $=$. But this is only heuristic intuition. Make it precise on your own, and see if you can find any weird functions that might serve as counter-examples.


Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible combinations. How can I make this with maybe dynamic programming?

Your condition on the graph is the same as requiring its complement to be triangle-free. It is known that there are a lot of triangle-free graph. Indeed, since every bipartite graph is triangle-free, if we fix a partition of the vertex set into two sets of size $n/2$ (assuming for simplicity that $n$ is even), then we already get $2^{n^2/4}$ triangle-free graphs. It turns out that there aren't that much more, see this question on mathoverflow.

Perhaps you'd be interested in a paper on generating maximal triangle-free graphs up to isomorphism (in your case, you will be generating minimal graphs satisfying your condition), whose number is more manageable.


An efficient algorithm to find a shortest cycle including a specific vertex We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.

We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.

This answer on SO explains why neither BFS or DFS work. However, I still think that DFS could be helpful in finding a minimun such cycle. Is there a way to make it work?

You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).

An important property of BFS is that if it runs from vertex $v$, then every vertex $s$, when it is first reached, then the path that was found from $v$ to $s$ is minimal. Thus, reaching $v$ from $v$ with BFS finds the shortest path from $v$ to itself, namely the shortest cycle that contains $v$.


Why is finding the closest pair of points by brute force search O(n^2)? If I have n points A, B, C, D it seems like finding the closest pair via  brute force search would go like:

Compare A to every item (n-1)
Compare B to every item (except A which it has already been compared to)
etc for every element.

This seems like it would be less than $O(n^2)$ because the you are comparing to a progressively smaller number of elements each time you go to the next element.

Can someone explain to me why this is $O(n^2)$?

It's not clear what you think $O(n^2)$ means.  $O(n^2)$ means that there is a constant $c$ so that, when $n$ is large enough, your algorithm takes no more than $cn^2$ time.

As you observed, the algorithm takes  $(n-1)+(n-2) + \ldots + 1 $ time.  This is equal to $\frac12 (n^2-n)$.  This quantity is less than $2n^2$ whenever $n$ is larger than $10$.  So it is indeed $O(n^2)$.

Another way to understand $O(n^2)$ is: if $n$ doubles, the algorithm will take about four times as long.   For $n=10$, your algorithm takes $9+8+\ldots + 1 = 45$ steps.  When $n=20$, it takes $ 19+18+\ldots + 1 = 190$ steps.  That is indeed pretty close to $4\cdot 45=180$ steps.  Similarly when $n=40$ it takes $780$ steps, which is again pretty close to $4\cdot 190 = 760$.


Isn't NP problems always also co-NP problems? I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?

The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it.  The formal definitions are given at our reference question on NP.

A decision problem is in NP if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that:

For every "yes" instance $x$, there is some $y$ with $|y|\leq p(|x|)$ such that $M$ accepts the string $x,y$;
For every "no" instance $x$, $M$ rejects all strings $x,y$.

So, for example, 3-COLOURABILITY is in NP: the string $y$ is just a description of a $3$-colouring and $M$ accepts $x,y$ if $y$ is a valid $3$-colouring of the graph $x$ and rejects otherwise.  The point is not that you can "verify 'yes' instances" but, rather, that every "yes" instance has a certificate $y$ that you can use to easily prove that it really is a "yes" instance.

But there's a significant asymmetry in the definition.  If you give $M$ a "yes" input and a certificate $y$, then $M$ will say "I agree – that's a 'yes' instance." However, there's no input you can give it that will cause it to say "I agree – that's a 'no' instance." For any certificate you try, it will just say "That doesn't convince me it's a 'yes'." You could, of course, try all possible certificates. That would certainly prove that you had a "no" instance but there's a problem: there are exponentially many possible certificates to try, so trying all of them doesn't give you a polynomial-time algorithm.


What are staged functions (conceptually)? In a recent CACM article [1], the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction.

They give a short explanation (emphasis mine and reference number changed; it's 22 in the original)

  In the context of program generation, multistage programming (MSP, staging for short) as established by Taha and Sheard [2] allows programmers to explicitly delay evaluation of a program expression to a later stage (thus, staging an expression). The present stage effectively acts as a code generator that composes (and possibly executes) the program of the next stage.

However, Taha and Sheard write (emphasis mine):

  A multi-stage program is one that involves the generation, compilation, and execution of code, all inside the same process. Multi-stage languages express multi-stage programs. Staging, and consequently multi-stage programming, address the need for general purpose solutions which do not pay run-time interpretive overheads.

They than go on to several references to older work allegedly showing that staging is effective, which suggests that the concept is even older. They don't give a reference for the term itself.

These statements seem to be orthogonal, if not contradictory; maybe what Rompf and Odersky write is an application of what Taha and Sheard propose, but maybe it is another perspective on the same thing. They seem to agree that an important point is that programs (re)write parts of themselves at runtime, but I do not know whether that is a necessary and/or sufficient ability.

So, what is staging respectively are interpretations of staging in this context? Where does the term come from?

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs by T. Rompf and M. Odersky (2012)
MetaML and multi-stageprogramming with explicit annotations by W. Taha and T. Sheard (2000)

To the best of my knowledge, the term staged computation was first used by Bill Scherlis in this paper.  Prior to that, the term "partial evaluation" was used for much the same concept, but the idea of staged computation is subtly different.  Both the ideas are related to Kleene's S-m-n theorem.

If you have a function $\phi(m,n)$ of two arguments, but you know one argument, say $m$, then you can perform some of the computation of the function right away using the knowledge of the first argument.  What you are then left with is a function $\phi_m(n)$ whose computations only depend on the second, unknown, argument.

The idea of partial evaluation is to compute the specialized function $\phi_m(n)$ automatically.  Given the code for the original function $\phi$, partial evaluation does static analysis to determine which bits of the code depend on $m$ and which bits depend on $n$, and transforms it to a function $\phi'$ which, given $m$, constructs $\phi_m$.  The second argument $n$ can then be fed to this specialized function.

The idea of staged computation is to think about the function $\phi'$ first.  It is called a "staged" function because it works in multiple stages.  Once we give it the first argument $m$, it constructs the code for the specialized function $\phi_m$.  This is the "first stage."  In the second stage, the second argument is provided to $\phi_m$ which does the rest of the job.

So, the job of partial evaluation is to transform the code for an ordinary function $\phi$ to a staged function $\phi'$.  Scherlis envisaged that this transformation could be done by more general mechanisms than the earlier partial evaluation methods.  The subject of "staged computation" now deals with issues such as:

How to define staged functions?
What programming languages and type systems should be used for defining staged functions?
What is the semantics of such languages?
How do we ensure the coherence and correctness of staged functions?
What techniques are useful for automatically or semi-automatically constructing staged functions?
How do we prove the correctness of such techniques?

Staged computation can be very important in practice.  In fact, every compiler is in effect a staged computation.  Given a source program, it constructs a translated and optimized target program, which can then take the actual input and calculate the result.  It is hard to write staged computation programs in practice because we have to juggle the multiple stages and make sure that the right things are done at the right time.  Everybody who has written a compiler has struggled with such issues.  It is also hard to write programs that write other programs, may they be machine language programs (compilers), SQL queries (database manipulations) or HTML/Server Pages/Javascript code (web applications) and myriads of other applications.  The researchers in staged computation aim to create good languages and tools that make it easier and safer to create such applications.


Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular I have been looking around for a good source to answer the following question.
Have read a few different sources but have not found the answer I was looking for.

The question is:

  Give an example of an infinite set of:

  a. Regular languages whose union is a regular language

  b. Regular languages whose union is a non-regular language

  c. Non-regular languages whose union is a regular language

  d. Non-regular languages whose union is a non-regular language

I've used this post to answer part b, and I understand the method behind it (at least I think I do).

What is the right way to approach this question?

Wouldn't an infinite set of anything constitute a non-regular language, by definition?

a. is pretty easy. Just consider $\{a\}^\ast = \bigcup_{i \in \mathbb{N}_0} \{a\}^i$. This also answers the last question in your post (i.e., regular does not mean finite).

The answer to b., as you have said, can be found in the linked question.

Finally, for c. and d. you can use subsets of $\{ 0^n 1^n \mid n \in \mathbb{N}_0 \}$ and $\{ 1^n 0^n \mid n \in \mathbb{N}_0 \}$, which are both non-regular languages. Hint: The exercise text does not require the languages to be disjoint.


Batch regularization & L2 regularization Is performing batch regularization in addition to L2 regularization redundant?

Batch regularization: http://arxiv.org/abs/1502.03167

Notice how when performing batch regularization, you forgo using a bias term (and instead normalize your layer output, followed by scaling with a 'scale' term, and shifting with a 'beta' term.  I was under the impression that L2 regularization punishes large weights & biases... but if I'm not using biases because of batch regularization, then would I just punish the weights with L2 regularization?

Thanks--

No. They are not equivalent.  They are two different techniques, that each provide some kind of regularization, but using one doesn't necessarily make the other redundant.  For instance, in the paper you cite, the authors are using both (see Section 4.2.1 for mention of L2 regularization).

Specifically: whether or not it is more effective to use just batch regularization or to use both will probably depend on the specific learning task you have in mind.  But there is no theory that implies the two are equivalent.

Batch normalization still has a bias term that is added after the normalization step (the $\beta$); it does not eliminate it.  L2 regularization penalizes large weights and large biases.  As far as I can tell, batch regularization doesn't try to do either (at least not explicitly).

When using L2 regularization with batch regularization, I imagine you could either L2-penalize just the weights; or L2-penalize the weights, the $\gamma$ terms (scaling), and the $\beta$ terms (shift).  I don't know which will produce better results.  My intuition says the latter might be preferable, but experiments and data beat intuition any day.


Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation? Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing machines?

I see two ways of interpreting this question, but the answer is essentially trivial either way.

Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a Turing machine?

Yes, because that is the definition of a hypercomputation model.

A caveat: Technically, you could have a hypercomputation model that (as Wikipedia puts it) "can provide outputs that are not Turing-computable", yet cannot actually accept any nonrecursive language according to the definition of language acceptance for the model. This is because accepting a language is not the same thing as computing a function. This would probably require a contrived definition of language acceptance, though. For example, take any standard hypercomputation model and say that the acceptance criterion is that the machine rejects on all inputs.

Interpretation 2: Can some hypercomputation model decide every language that cannot be decided by a Turing machine?

No for any reasonable definition of a "model of computation", because the set $\mathrm{ALL} \setminus \mathrm{R}$ of all languages not decidable by a Turing machine is an uncountable set. So for almost every undecidable language, there is no way to write down a program that decides that language, no matter how powerful your model of computation is, as long as you require programs to be written using a finite number of symbols.


Closure on regular languages A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language.

Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse.

There is no need to write how to build formally or proof or correctness.

B) True or False: if $L$ is not regular then $L^R$ is not regular

My solution:

A) First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side.
but when it comes to changing it to NFA im a bit stuck.

B) I think its true since it doesnt matter if it reversed if its regular then of course $L^R$ will be regular as well.

Is this the way for A and B?

A)

  First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side.

You're almost there. What happens if you have multiple accepting states in the original DFA? That's where you need NFA capabilities to convert them.

Here is a spoiler in case you want to check your answer: Designing a DFA and the reverse of it on ComputerScience.SE.

B)

Your answer is true although you might want to phrase it a bit more carefully. We want to prove "if $L$ is not regular, $L^R$ is not regular". So let $L$ be not regular. If $L^R$ were regular, so were $(L^R)^R = L$, which is a contradiction. Hence, $L^R$ is not regular.


For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time? For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b > 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?

Note that $b$ is upper bounded by $\log n$, so you can go over all possible integers $x\in\left[1,\lceil\log n\rceil\right]$, and for each $x$ check whether the equation $a^x=n$ has an integer solution, i.e. whether or not $n^{\frac{1}{x}}$ is an integer. You might be interested in root finding algorithms.


Algorithm to determine if a top-down non deterministic tree automata accepts some tree? Given a non-deterministic top-down tree-automata.
is there an algorithm,
that can determine if there exists any tree that accepted by this automaton? if so, what is the most efficient algorithm known?
Thanks.

Yes, you can do it in linear time.  Associate to each pair of a state $q$ a boolean variable $x_q$; the intended meaning is $x_{q,s}$ should be true if there exists a tree that is accepted by the automaton if we start with state $q$ at the root.  Then, each transition rule of the automaton corresponds to a Horn clause on these boolean variables. For instance, the transition rule $f(q_1,\dots,q_n) \to q'(f)$ corresponds to the Horn clause $(x_{q_1} \land \cdots \land x_{q_n}) \implies x_{q'}$.  Now, solve the associated HornSAT problem using any standard algorithm to find the minimal satisfying assignment to all of these clauses; this can be done in linear time.  If you find any final state $q$ of the automaton such that $x_q$ is set to true by this assignment, then the answer is yes, there exists a tree that's accepted by this automaton; otherwise, the answer is no.


Is the exact cover problem NP-hard when there is a restriction on the size? The exact cover problem with restrictions on the size is:

Input: Given a set $U=\{1,2,\ldots,n\}$ and a collection of $C$ of subsets of $U$.

Question: Is there a subcollection $C^\star$ of $C$ such that

The intersection of any two distinct subsets in $C^\star$ is empty;
The union of the subsets in $C^\star$ is $U$; and
The size of any set $S\in C^\star$ is at most $\log_2 n$, i.e., $|S|\leqslant \log_2 n$ for all $S\in C^\star$.

Is this problem NP-hard?

Yes, it is still NP-hard.  In fact, it remains hard even if you replace $\log_2 n$ with the constant 3.  This follows by reduction from 3-dimensional perfect matching.

3-dimensional perfect matching is the following problem:

Input: disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$

Question: does there exist a perfect matching?  In other words, does there exist $S \subseteq T$ such that $|S|=|X|$ and the union of elements of $S$ is an exact cover for $X \cup Y \cup Z$?

From this statement of the problem, it is clear that 3-dimensional perfect matching is a special case of your problem: take $U=X \cup Y \cup Z$ and $C = \{\{x,y,z\} : (x,y,z) \in T\}$.

In contrast, if the size of every set is at most 2, then it can be solved in polynomial time, using algorithms for finding a perfect matching in an undirected graph.


Theoretical precision needed to get $n$-bits of the evaluation of some sum Let $P,Q$ two integral polynomials of height bounded by let say $H>0$ --- that is every coefficient of $p$ or $Q$ is bounded in absolute value by $H$ --- and degree at most $d$.

Let $A$ a set of $d$ reals.

I want to evaluate the sum:
$$
S = \sum_{\alpha \in A} P(\alpha)Q(\alpha),
$$
and more precisely I want to get the $n$ first bits of this value.

I can assert that this sum is bounded by a constant $K'>0$.

What would be the minimal number of bits of precision on the elements $\alpha\in A$ I need to be able to compute the $n$ first bits of $S$?

NB: The representation of the reals of $A$ can be whatever (fixed point, floating point, ... ) I'm able to efficiently compute them at arbitrary precision.

I may be misunderstanding the question, but I don't think we have enough information to tell.

Consider, for example:

$$A = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

and:

$$P(x) = \left( x - \frac{1}{4} - \varepsilon \right) \left( x - \frac{1}{2} + \varepsilon \right) \left( x - \frac{3}{4} - \varepsilon \right)$$
$$Q(x) = 1$$

for some small $\varepsilon$.

Assuming that $\varepsilon$ is small enough, both polynomials are height-bounded by 1.

The sum is:

$$S = - \frac{5}{16}\varepsilon + \varepsilon^3$$

The question is how you would evaluate $P$.

$$P(x) = \left(-\frac{3}{32} - \frac{5}{16}\varepsilon + \frac{1}{2}\varepsilon^2 + \varepsilon^3\right) + \left( \frac{11}{16} + \varepsilon - \varepsilon^2\right) x + \left(-\frac{3}{2} - \varepsilon\right) x^2 + x^3$$

The number of bits of precision on the elements of $A$ are not relevant here; they are precisely representable with two significant bits. It seems to me that the precision you need to do the intermediate computation is more important.

For a small enough $\varepsilon$, you are going to get catastrophic cancellation whether you use the factorised form of $P$ or you use a method such as Horner's rule. At the very least, you need enough bits to represent $-\frac{3}{32} - \frac{5}{16}\varepsilon$ such that you have $n$ significant bits in the $\varepsilon$ term, so you can subtract $-\frac{3}{32}$ to get a good enough answer.


Does using micro-operations require a higher clock rate than listed Say we have a modern (Skylake, say) Intel CPU running at a fixed 5GHz clock rate. Since Intel CPUs run micro-operations internally and reaches > 1 instructions per cycle, it needs to be able to run more than one micro-operation per cycle. But from how registers work we know that new data can only be stored and computation allowed to proceed at certain points of each clock cycle (e.g. the rising edge). Since the CPU internally does more than 1 micro-operation in sequence within a single clock cycle, doesn't that mean it would also need to have more than one internal clock cycle per "external" clock cycle, and hence an internal clock rate that is higher than the listed 5GHz?

That's not necessary, and also not how it is actually done. The way Skylake and most other microarchitectures executes multiple instructions in the same cycle is in parallel, not in sequence within a cycle.

So the registers would not be read at several different moments during a cycle, instead several reads are done simultaneously. That does not present a structural hazard: the read logic can be duplicated, as in multi-ported SRAM.
Clearly such duplication is not free, but it can be kept in check by exploiting the fact that most registers being read are "hot" (written to recently) and their value will be supplied by different mechanisms anyway (forwarded just-in-time or captured in the reservation station if applicable). Core2 for example could only read 2+1 different entries from its retirement register file (the +1 is for the special case of a register being used as the index in a SIB-encoded address), but for "hot" registers it had no particular limit (or none that I know of). From SandyBridge onward Intel has been using an alternative organization with more of a tag-indexed physical register file style and there seems to be no particular limit on reading from it (so maybe they just went with plenty of read ports there?). Anyway the TL;DR is that the multiple µops in a cycle and their register reads are not sequential and don't need a faster clock.

NetBurst (Pentium 4) actually did have a faster internal clock for its fast ALUs and AGU, but not for everything (excluding for example the register file), and the reason was not that register reads needed to be sequential (they weren't), just for raw computation speed with low latencies. There were two ALUs, so together they can execute 4 ALU operations per cycle, though the front-end cannot supply them with new operations that quickly so the peak throughput cannot be sustained and is only reached in bursts. It is more complicated than executing two operations per ALU in sequence within a "normal cycle" though. Instructions actually take 3 FLCK cycles, in the first cycle the low 16 bits of the result are computed, in the second cycle the high 16 bits are computed and a dependent instruction can already start (since it would also only compute the low 16 bits of its result in the first cycle, so for now it only needs the low 16 bits of its inputs) and in the third cycle the flags are computed.


Finding a language that is $NP^L$-complete I'm trying to prove a theorem and as a lemma I would like to identify an $NP^L$-complete language. I was thinking something like a machine that can decide $SAT$ equipped with an oracle for $L$ can decide every language in $NP^L$, but I'm not sure how to formalize this. Here's my attempt at doing so

$$ SAT^L = \{\text{satisfiable boolean formulas with some clauses as }L(x_1, \dots, x_k)\}$$

The clauses that are of the form $L(x_1, \dots, x_k)$ are queries that are true if and only if $(x_1 \cdots x_k) \in L$.

I think $SAT^L$ is $NP^L$-complete, for any language $L$, but I don't know how to prove this. It's of course in $NP^L$ since we can take a witness
assignment and check it, and we can check the $L(\cdot)$ predicates with a query to our oracle to $L$. I'm not sure how to prove $NP$-hardness though.

I was thinking of just modifying Cook-Levin's construction so that I could add additional clauses to the formula of the form $L(x_1, \dots, x_k)$ when encoding the computation graph of an NTM $M^L$  but I'm not sure if this works in general, and is honestly more of a rough idea than anything else. This construction seems to be pretty sensitive to the "implementation" of the oracle queries, so I'm not sure how to make this rigorous.

Is there a more standard example of a $NP^L$-complete language?

What you are looking for is a relativization of the Cook-Levin theorem in the sense that you consider SAT and NP relative to an oracle for $L$. You can find the answer to that in this answer, point number 2. There you get (an extension of) Circuit-SAT as a complete language; reducing this to your version of SAT should not be too hard.

Note that, as mentioned in the linked answer, this is a bit different than a relativization in the sense that it is the reduction which possesses an oracle for $L$.


How to show that A is not regular? Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “1011 = 1011 ⊕ 1011” is not

How can I show that A is not regular? How should I have the string?

Also, if the binary numbers are of fixed length, 64 bit long, would A then be regular or not?

Any regular language upholds the pumping lemma. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular.

Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated substrings $xyz$. Since $|xy| \leq p$, we see that $v=0^k$ for some $k$ greater than 0. If we choose to pump it $i$ times, we will then obviously obtain an $x$ which is longer ($i > 1$) or shorter ($i = 0$) than the other two operands and cannot then be the result of their XOR, hence proving that the language is not regular.

However, it may be that you forgot to add some clauses to the problem statement, since this seems quite trivial. Edit: my intention was not to point out that this is easy in general, the principle itself of the proof being rather non-trivial. However, some additional clauses, such as the strings having the same length would render this sensibly harder, and it may be what the problem had in mind.


Why use heap over red-black tree? Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time.

However, red-black tree supports insert/remove both in $O(\log n)$ time. We can just remove the first/last element in a red-black tree to remove min/max in $O(\log n)$ time.

I do understand that heaps are used specifically to remove the min/max, but it seems like red-black trees can do what heaps can do but just faster/equal.

Is there any distinctive advantage to using heaps over red-black trees?

Its about pragmatic efficiency.

The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very large N, but instead operate over particular ranges of N.

Heaps

A binary heap can be allocated as a single block of memory if the size of N is known. Even if not known a simple reallocation strategy of doubling the allocation is very efficient. Alternately the blocks can be designed to fit within a memory page having a well-known capacity, and then assembled into balanced block trees.

This has several advantages:

Keeping the data-structure dense and co-located decreases the likely-hood of a cache miss at the processor level, or a page miss at the memory level - both slow overall execution.
Organising the tree to follow a predictable memory addressing pattern permits the index to be calculated within the processor and does not require a memory load.
By minimising the need to reserve memory, memory management book keeping overheads are reduced.

And a few flaws:

A dense structure incurs an all or nothing memory overhead. An entire page/block must be allocated for even a heap of a single element.
Modification necessitates element copying - which may not be cheap. A complex object may have internal bookkeeping that is memory location dependent, and must be updated when moved/copied.
If the capacity of the heap is exceeded a costly re/allocation operation must be performed.

Trees

Conversely a tree is generally constructed of nodes which are individually small in size and the nodes are linked via memory addresses. Removing a node is as simple as redirecting the pointers around the removed node, notifying the memory book keeper that it is no longer needed, and then applying a re-balancing operation that adjusts those addresses to achieve a balanced tree.

This has its advantages:

The tree has exactly the capacity for what is held.
The tree can be allocated in highly fragmented memory spaces.
No elements are copied when modifying the tree (excluding creating the node itself).
Memory bookkeeping is paid as needed.

But has its disadvantages:

Each node must at least identify its two children, and other book keeping state. Usually 3*sizeof(pointer).
Tree traversal requires memory access to read the location, then another memory access to access the next node.
Tree nodes are allocated sparsely increasing the chance of a cache-miss, or a page-miss
Much more memory bookkeeping is required.

Simplifications

Note that I have simplified this significantly, and alternate implementation choices could be made:

I could have used block allocation for the tree, forcing the elements of many nodes other than the one being manipulated to be copied around, while simplifying the rebalancing of the tree, and omitting storage/modification of node addresses.
I could have used single element nodes for the heap, sacrificing memory density for minimal element copying.

These would have changed the trade-offs and the total cost of each. In a given context these changes would pay dividends, but outside of that context they hobble the use case with unnecessary work.

Specification

What is most efficient is situational. Thus it is usually best to specify the exact operations needed, and allow implementations to provide that operation in the most contextually efficient manner it can.

So as before if the operation is over expensive to copy objects, I probably would use a red-black tree to offer Heap operations, or some other similar low-copy data-structure.

Conversely if the data in the heap were single bytes, the block encoded binary heap is a clear winner: N * (1byte + 3*ptrsize bytes) vs. Nbytes.


A little confusion with the Knapsack problem (a worked example) I'm going through a worked example on the Knapsack problem:

My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a fraction of 1 (otherwise it breaks the inequality) but why specifically $4/5$? Any insight is highly appreciated.

The (non-negative) variables $x_1,x_2,x_3,x_4$ must satisfy the constraint
$$ 2x_1+2x_2+4x_3+5x_4 \leq 8. $$
If $x_1=x_2=1$ then this simplifies to
$$ 4x_3+5x_4 \leq 4, $$
which implies in particular that $x_3 \leq 1$ and $x_4 \leq 4/5$ (since $x_3,x_4 \geq 0$).


A faster, leaner JavaScript for scientific computing: what features should I keep? Here I'm really interested in lowering barriers to mathematical education.

Target:

I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-performance computing libraries (great lists of which are available through Sage and otherwise). And I want that, because I'd like to make it easy for people who learn JavaScript to get into scientific and numerical computing without having to learn Python (& company). (I know it's easy to learn Python, as I basically did it at some point, but this suggests that perhaps it'll be easy to compile some restricted subset of JavaScript to Python.)

Hypothesised method:

I'm primarily interested in a new language with minimal difference from JavaScript, because the market ("human compilers") I'm targeting are programmers who already know JavaScript. What I want to target those people for, is to give them a minimally different language in which to write code that compiles to faster C, in the manner that RPython and Cython do for Python. I'm willing to throw out a lot of JavaScript features, I just want to be careful to add a minimum number of features back in. I'll definitely be looking at Lua, Dart, ECMA Harmony (which has no formal date of release, or am I mistaken?), etc. as these are all close resemblances to contemporary (2012) implementations of JavaScript.

Questionable Motivations:

I'm personally willing to learn any language/toolset that gets things done faster (I'm learning Erlang myself, for this), but here, I am specifically interested in lowering the bar (sorry) for other people who may not have such willingness. This is just one of those "want to have my cake, and eat it too, so I am putting some time into researching the problem" situations. I have very limited prior experience in computer language design, but so far from a hacking-the-ecosystem point of view, the problem seems interesting enough to study, so, I hope to be doing more of that soon.

If you want to use JavaScript for scientific computing, why not try Node.js? Node is based on Google's V8 engine with some additional functionality for interacting with the file system, writing servers and linking to C and C++ libraries (this is definitely not an exhaustive list). It sports fast execution times and provides an interactive console as well as a way to execute your programs from the command line. I found @DaveClarke's comment about Python acting as "glue code" interesting because of the wording. Here is an excerpt from the Node documentation on addons:

  Addons are dynamically linked shared objects. They can provide glue to
  C and C++ libraries.

Node also has an excellent package manager called NPM, which would make it easy to share scientific modules which you have written. The NPM repository already contains some scientific modules, such as "natural" (for natural language processing) or "clusterfck" (a clustering library). There are most definitely many other libraries out there for a variety of applications.

The great thing about this solution is that you wouldn't have to modify JavaScript or create a new language. The syntax is essentially the same, but your code does not need a browser to execute. If you plan to follow up with node, a good first step might be to start creating addons for existing open-source scientific libraries written in C and C++, or you could port them to JavaScript. I was actually thinking about using node for scientific programming today which is what led me to this question. It would be great to see more robust tools like you find in Python.

I initially had links to natural and clusterfck, but I do not have enough rep to post them. Luckily, they come up as the first results if you google "clusterfck node" and "natural node".


kd-tree stores points in inner nodes? If yes, how to search for NN? The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept.

However, I was said to study Kd-trees from Computational Geometry Algorithms and Applications (De Berg, Cheong, Van Kreveld and Overmars), section 5.2, page 99. The main difference I can see is that Overmars places the splitting data in the inner nodes and the actual points of the dataset in the leaves. For example, in 2D, an inner node will hold the splitting line.

Wikipedia on the other hand, seems to store points in inner nodes and leaves (while Overmars only on leaves).

In this case, how do we perform nearest neighbour search? Moreover, why there is this difference?

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

Procedure NN(node), given query q
  if(node is leaf)
    Search all points, in node, update current best
  else {internal node}
    if( cut_coord(q) <= node's cut-value )
        NN(left-child)
        if( cut-coor(q) + current best distance > node's cut-value )
            NN(right-child)
        end if
    else {cut-coor(q) > node's cut value}
        NN(right-child)
        if(cut-coor(q) - current best distance <= node's cut-value)
            NN(left-child)
        end if
    end if(left/right)
  end if(node)

In order to perform ANN search, see the answer here.


distributed alpha beta pruning I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see below) are all quite old (1990 being the latest). I assume there have been many substantial advancements since then. What is the current standard in this field?

Also please point me to an idiot's explanation of DTS as I can't understand it from the research papers that I have read.

The algorithms mentioned above:

PVS: Principle Variation Splitting
YBWC: Young Brothers Wait Concept
DTS: Dynamic Tree Splitting

are all are discussed here.

yes the theory has advanced significantly and somewhat due to both the chess analysis literature and general parallel programming techniques. here are some newer refs on (chess) alpha beta pruning over distributed clusters/ parallelism. also some of the early distributed computing chess literature predates a lot of basic parallel design patterns and can be conceptualized within that framework.

Parallel Alpha-Beta Algorithm on the GPU / Strnad, Guid (2011)
Parallel Alpha-Beta Search on Shared Memory Multiprocessors / Manohararajah (2001) 98pp!
Parallelizing a Simple Chess Program / Greskamp, 2003
Parallel Alpha-Beta Pruning of Game Decision Trees: A Chess Implementation / Steele 1999
Is it possible to run a Minimax search with Alpha-Beta Pruning in parallel with OpenMP? (stackoverflow)
The DTS high-performance parallel tree search algorithm (Hyatt 1994)

the basic idea behind DTS is that search trees are distributed among computational nodes based on move/ layout complexity. unused processors that "finish early" can do additional work beyond an initial allocation which can be distributed as evenly as possible initially but will turn out to be uneven. hence its basically a kind of "load balancing" and "producer/ consumer" queue, or also similar to job scheduling.

  This idle processor broadcasts (using shared memory) that it is idle, and is available to "help" any other processor finish searching its tree. The busy processors collect the "state of the tree" data, and store it in shared memory for the idle processor to examine. This idle processor analyzes this data, and decides which (if any) of the busy processors seems to have a tree that is complicated enough that it would be efficient to help with the search. If such a position is found, the idle processor informs the processor which owns that node of this and they "join" forces.


Is it an open problem if generalized resolution is always possible? Let we have a 3CNF under following restriction: each variable occurs 3 times.

Then I apply generalized resolution (GR) (I don't know which name would fit more) technique (number of clauses can be arbitrary large, just an example):

$(x\lor A)\land(x\lor B)\land(\overline x\lor C)=(A\lor C)\land(B\lor C)$. Here $A,B,C$ are some clauses. Neither $A$ and $C$ nor $B$ and $C$ have opposing literals (like in original resolution, the reason is not to exponentially increase length of formula).

Is it an open problem if there is such a sequence of choices (which variable to choose for GR) that will return 'NO' if formula is unsatisfiable? Or there is a proof that some unsatisfiable formulas (with given restrictions) have no such sequences? Meaning that for every pair of literals $x,y$ on some step it will be possible to find a clause $(A\lor x\lor y)\land(B\lor\overline x\lor\overline y)$.

We assume that we can use any known polynomial technique such as unit propagation, absorption rules $(x\lor A)\land(\overline x\lor A)=A; A\land(x\lor A)=A$, pure literal rule (if variable always occur as positive or negative, remove all clauses where it is contained), changing equal literals, finding strongly connected components in a graph for 2-clauses, etc.

Resolution is refutation-complete. This means that if $S$ is a set of unsatisfiable clauses, then you can use resolution to derive the empty clause. Moreover, Resolution is sound, so you can only derive the empty clause if $S$ is unsatisfiable. Summarizing, given a set $S$ of clauses, you can use Resolution to derive the empty clause if and only if $S$ is unsatisfiable.

Unfortunately, sometimes generating the empty clause takes an exponential number of steps. Let $G$ be a random 4-regular graph on an odd number of vertices $n$, and let us associate with each of the $2n$ edges a variable. Consider the set of $\Theta(n)$ clauses stating that for every vertex, the XOR of the four variables corresponding to edges touching the vertex is 1. Since the number of vertices is odd, this set of clauses, known as a Tseitin contradiction, is unsatisfiable. Urquhart showed that with high probability, any Resolution refutation of this set of clauses has $2^{\Omega(n)}$ many lines (i.e., clauses); see Jakob Nordström's lecture notes.


Descriptive complexity of 3SAT lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity.
I found many formulas in $\exists$$SO$ that describe problems with graphs but none that describes the 3SAT language.

Thinking about it, I came to an "atomic" description like this:

$\exists$$v$$\forall$$C$ $(P(C))$

Where $v$ is a literal, $C$ is a clause (i.e. the $OR$ of 3 literals) and $P(C)$ means that $C$ is true.

However I'm not satisfied with this definition, I don't think it captures the complexity of the 3SAT language, especially the dependence of the variables on one another. Can you tell me a correct formula to describe this decision problem? Thank you.

The language consists of ternary relations $R_1, \dots, R_4$, which represent the clauses as follows:

$(x,y,z)\in R_1$ iff there is a clause $(x\lor y\lor z)$;
$(x,y,z)\in R_2$ iff there is a clause $(x\lor y\lor \neg z)$;
$(x,y,z)\in R_3$ iff there is a clause $(x\lor \neg y\lor \neg z)$;
$(x,y,z)\in R_4$ iff there is a clause $(\neg x\lor \neg y\lor \neg z)$.

($\lor$ commutes so you don't need to consider other patterns of negation.)

The formula then says "There exists a set $T$ of variables such that, if the variables in $T$ are set to true and the ones not in $T$ are set to false, the formula is satisfied."  That is,

$$\begin{align*}
\exists T\,\forall x\forall y\forall z\, \big[&\big(R_1(x,y,z)\rightarrow (T(x)\lor T(y)\lor T(z))\big)\\
&\quad \land \big(R_2(x,y,z)\rightarrow (T(x)\lor T(y)\lor \neg T(z))\big)\\
&\quad \land \dots\big]\,.
\end{align*}$$


Variant of interval scheduling with varying task durations I am probably just missing the correct term for my problem to find the solution but here it goes:

I have a set of tasks with a given duration and an interval for each task in which it has to be completed. I now need to find start times for the tasks, so that

each tasks is completed within its interval
no task overlaps with another task

Sketch:

The deterministic version of your problem (i.e. to determine whether there is a valid arrangement) is strongly NP-complete by a reduction from 3-Partition, as suggested in [1].

Given an instance $x_1,x_2,\ldots,x_{3m}$ of 3-Partition, let the duration in your problem be $[0, mB+m]$ where $B=\sum_{i=1}^{3m} x_i/m$. For each element $x_i$, there is a task with duration $x_i$. The intervals for these tasks are all $[0, mB+m]$. In addition, there are additionally $m$ tasks with duration $1$, and their intervals are respectively $[B, B+1], [2B+1, 2B+2],\ldots,[mB+m-1,mB+m]$. Note the positions of these additional tasks are fixed.

Since we can assume $B/4<x_i<B/2$ for all $i$ in 3-Partition, we can see there is a valid partition if and only if there is a valid arrangement in your problem.

[1] Garey, M. R., & Johnson, D. S. (1977). Two-processor scheduling with start-times and deadlines. SIAM Journal on Computing, 6(3), 416-426.


What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$ I can't find out how to find a context free grammar for bellow language, is there any specific way to solve that?

$L = \{w: n_c(w) \ne  n_a(w) + n_b(w)\}$

$\Sigma = \{a,b,c\}$. Consider the two cases:

$n_c(w) > n_a(w) + n_b(w)$: The idea is to create one more $c$ for each $a$ or $b$ produce in the word:
\begin{align}
             S_c \rightarrow aS_cS_c | bS_cS_c | c
    \end{align}
$n_c(w) < n_a(w) + n_b(w)$: In this case, we can produce as many $c$'s as $a$ and $b$ combined + 1.
\begin{align}
             S_{ab} \rightarrow aS_{ab} | bS_{ab} | cS_{ab}S_{ab}|a|b
    \end{align}

The grammar for the required language would be : $S \rightarrow S_c | S_{ab}$.


$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$? Now, I have the following conjecture.

  $\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$.

However, I am at a loss at how to realize/see this. Could anybody help me out?

Consider what happens when you feed into a majority gate the the inputs $x_1,\ldots,x_k$ and $k-1$ zeroes. You get an $\mathsf{AND}$ gate. If you feed into it $k-3$ zeroes, you get a gate corresponding to $x_1+\cdots+x_k \geq k-1$. Using similar ideas, you can construct a constant-depth circuit over the basis $\{\lnot,\mathsf{MAJ}\}$ that computes $x_1+\cdots+x_k = \ell$ and so $\mathsf{MOD}_{2017}$.

If you're not allowed to use constants but there is a tie-breaking rule for $\mathsf{MAJ}$, then you can implement constants using $\mathsf{MAJ}(x_1,\lnot x_1)$, whose constant value will depend on the tie-breaking rule.

If you're not allowed to use constants and every majority gate needs to have an odd number of inputs, then it is generally not possible to construct such a circuit. Indeed, suppose that you plug $x_i = x_1$ for all $i>1$, and that $k$ is chosen so that the output is constant whatever the value of $x_1$ is (this depends on your definition of $\mathsf{MOD}$, which you haven't supplied). On the other hand, you can prove by induction that every gate computes either $x_1$ or $\lnot x_1$, and in particular not a constant function