How do neural networks create results like its inputs? I understand basic neural networks (input layer, hidden layers, output layer) and gradient descent learning. However I keep hearing about news talking about neural networks painting and making jazz music. That is puzzling me.

As I understand a neural network, you feed it the input data (i.e. a picture, music, ...) and it gives you some kind of classification on the result. But by reading those results it looks as if they were using the neural network to generate new results based on a training dataset. Because of that, I'm thinking the kind of neural networks they're referring to is essentially different from the ones I've studied, so I'd like to ask:

What are the differences between classic neural networks and the ones used to run these experiments? What makes them fundamentally different so that they are able to generate results similar to its input?
Do these results (generating results with a NN) have anything to do with deep learning? Or is deep learning just a better learning technique?

These are known as Autoencoders. As you said, these neural networks are trained to produce output that is similar to the input, rather than output a classification of some kind.

Internally, they do not differ much from other neural net designs. Simply, the expected output is the input (or a slight variant of the input), rather than a classification.

One difference however is often the level of depth. Networks designed to replicate sequences, like writing jazz music, need to remember a sequence throughout training and prediction. This is where deep learning succeeds better than other methods.

This paper briefly discusses one type of an auto-encoding network and how it's used to produce music. I think you will find the design is very similar to a traditional neural network.


Would memoization make any improvement to Strassen's algorithm? Could the run-time of the Strassen's algorithm be improved by adding Memoization to it?

I don't get why the other answerers don't even make an attempt to reason along the lines the question has been asked. If anything, they should explain why memoization can or cannot work.

In any case, let's think about how we can can approach memoization in the Strassen's algorithm. We know that it involves dividing our matrix into four equal quarters, calculating products of individual submatrices and combining them through addition with the following complexity:

$T(N) = 7T(N/2) +  O(N^2)$

The one place where we can apply memoization is in the product of the submatrices stage. Each time we encounter two submatrices that need to be multiplied, we can store the result hoping that we encounter the same submatrices again and don't have to recompute the product. This will take up a lot of memory of the order of $O(N^2)$ for each saved product.

That brings us to the next question - How many products are going to be there? We will be having one $N^2$ matrix in the outermost call, $7(\frac{N}{2})^2$ matrices in the next call, $49(\frac{N}{4})^2$ matrices in the subsequent call and so on until $7^{(log N)}$ individual products. You will notice that we're using more and more memory as the recursion depth increases. (The memory requirement will be greater than $O(N^2)$)

Although the memory size is large, what is really important for us is to locate a given matrix from the set of stored matrices. Naively, this would take $O(number\_of\_products \cdot N^2)$ time for iterating through all of the products computed so far. We can probably make it faster by passing the input matrices through a hash function and mapping the hash value to the matrix. This can be done in $O(N^2)$ for the right choice of hash function, and $O(1)$ for a map based lookup.

How will this affect our complexity? We now do an additional lookup before computing the product, and save the product right after as well. $T(N) = O(N^2) + 7T(N/2) + O(N^2) + O(N^2)$. This is equivalent to our original complexity.

This shows us that asymptotically, we don't do worse in terms of time complexity although the space complexity shoots up.

Will it actually speed things up? It really depends on how often we will have repeating submatrices that we need to recompute. I do not think that in any practical scenario (especially if we are dealing with floating point operands), we will see the same sets of submatrices too many times. But this is an intuition. If I were you, I'd try it out and empirically find out if it helps.


(a,b)-tree vs B-tree I would like to know what are the differences between (a,b)-tree and a B-tree. It has been a few days I am studying different papers and I am seeing different definitions that make me confused.

For example in External Memory geometric Data Structure by Lars Arge on Page 3 he says

  Normally, the N data elements are stored in the leaves (in sorted order) of an (a; b)-tree T , and elements in the internal nodes are only used to guide searches.

So the N data elements are stored in the leaves and internal nodes are only used to guide searching, they don't contain any data element other than the leaves. While in B-trees it is not so, In B-tree internal nodes contain their own different elements and every element of an internal node is used as a separator of its children. In fact it is a data element that is moved up.  Like this

But from (a,b) Trees, it says

  A B-Tree is a (a,b)-tree with a = ceil(b/2).

Which is in contradiction with the structure of internal nodes, Furthermore it shows that internal nodes have different elements than the leaves and all of the elements are not stored in the leaves. They may be stored in the internal nodes as well. In the insertion phase, some of the elements of the nodes are moving up to the parent as the separator.

I would like to know what are the elements in the internal nodes of B-trees and (a,b)-trees?

Thanks in advance.

It seems you are right. The author probably takes as a standard definition the B+-tree where internal nodes are used as separators.

You should always be prepared for authors that deviate from standard definitions and naming conventions!


Token Scanner for programming Language(Lexical Analysis) This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.

The Question is : Do i have to convert the entire given DFA to an ε-NFA(which will result in more states),add the keywords(with ε transitions too)and then convert back to a DFA or i just have to add the keywords so that the DFA becomes an NFA and then convert back to a DFA

There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's necessary to do so, and it's not because it's efficient to do so.

Thompson's construction has the following advantages:

It's recursive on the structure of the regular expression.
It's easy to convince yourself that the construction is correct.
It's straightforward to incorporate certain extensions (e.g. the LEX lookahead operator "/").

Real-world implementations of regular expressions, even if they are based on Thompson's construction, typically optimise a dozen or so common base cases (e.g. Kleene closure of a character set; [a-zA-Z0-9_]* expands to something much bigger than it needs to be), saving Thompson's rules for higher levels.


Is deciding if there's a solution to a single multivariate quadratic equation NP-hard? I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard.

Is deciding if there's a solution to a single multivariate quadratic equation NP-hard too?

I am intersted in the NP-hardness of deciding if there's a solution to a single quadratic equation over any field; not only over $\mathbb R$.

I am currently trying to reduce from the problem of deciding whether there's a solution to the equation $x^T Ax=\lambda$ subject to $x\in[0,1]^n$ (which is NP-complete) to our problem using Lagrange multipliers.

For $\mathbb{R}$ (the real numbers), you can decide whether a single multivariate quadratic equation has any real roots or not, in polynomial time.  See https://cstheory.stackexchange.com/a/19858/5038.  There are some other answers to that question that partly address the case of other fields.

For $\mathbb{F}_2$ (the integers modulo two), you can decide whether there is a root in polynomial time.  See https://cstheory.stackexchange.com/q/37687/5038.

I don't know what the situation is for $\mathbb{Q}$ or $\mathbb{F}_{p^n}$.


Find the point with minimum max distance to any point in a set Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?

This is the smallest enclosing circle problem, and can be solved in linear time. Also, these slides describe a randomized algorithm that runs in expected linear time.


What is token-type in Lexical analysis? I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 .

i cannot understand what is this kind of method ?

  E = m * 2;

  conversion to token types(this method) below

<id , E> <op=> <id , m> <op*> <number , 2> <op;>

it is token-type pairs ? or is there any technical term associated ?

I don't know what is the proper name for what you're seeing, but it is the standard way to lexically analyze text. You divide it into tokens of specific types. For the sake of context-free parsing (the next step in the parsing chain), you only need the type of each lexeme; but further steps down the road will need to know the semantic content (sometimes called annotation) of each lexeme. For example, the context-free parser doesn't care which number $2$ is; it only needs to know that it's a number. Further down the road, it will suffice to know that this number is an integer. Even further, you would need to know that this integer is specifically $2$.

Some lexemes are atomic, for example the various operators (though in principle we could group, say, + and - together). We need to separate them because syntactically = is different from +, and + is different from * (due to operator precedence). These don't need any annotation.


Algorithm for determining whether 2 entities of some feature are the same? I'm trying to think of a way to do approximate joins between 2 rows in a data table. Like for example lets say I have a row where the person name is "John Doe" but then another data table uses a different person format like "Doe, John." Now suppose I can put them both to a standard format say "John Doe." Sweet so I have a way to reference them and let's say there's other data correlated with "John Doe" is there any algorithms out there to infer whether these 2 John Does are the same given the other data columns? You can see the other data columns as features as well, because I know FB has an algorithm to stop duplicates for the same person and StackOverflow will merge accounts if it thinks they're being used by the same person. Any suggestions?

I am not able to clearly understand your use case, but from what I infer I believe if you are trying to de-dupe data on other features, the approach would be to use LSH(Locality Sensitive Hashing) you can see the following links to get an overview. hope this helps.

https://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing

https://www.cs.utah.edu/~jeffp/teaching/cs5955/L6-LSH.pdf

https://en.wikipedia.org/wiki/Locality-sensitive_hashing


Solve recurrence relations A) Solve this recurrence where $T(0)=0$ and write it in O-notation:
  $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$

So, I started to calculate:

  $T(1)=2(0)+c=c$

  $T(2)=1(0+c)+c=2c$

and so on, which gives me that $T(n)=nc$

This I can prove by induction: $(n-1) \rightarrow n$

  $T(n)= {2 \over n} (0+c+2c+...+(n-1)c)+c = {2 \over n} (c{(n-1)n \over
 2} )+c = nc$

Which gives me $O(n)$ (since $c$ is a constant). Am I right with this?

  B) For $T(n)=kT({n \over k})+ckn$
  find the closed form for the function $T(n)=f(c,k,n)$ (I don't know what does this mean) and write it in
  $\mathcal O$-notation.  If you had the algorithm working with $k=2$, $k=3$ or
  $k=4$ which one would you choose?

I'm stuck with this problem. With the help of the master theorem, I would get $log_k k = 1$ which would give $\mathcal O(n \log n)$ but how to find the closed form?

This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.

An easy road is to write:
\begin{align}
(n + 1) T(n + 1) &= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\
n T(n)           &= 2 \sum_{0 \le k \le n - 1} T(k) + n c
\end{align}
Subtract to get:
$$
(n + 1) T(n + 1) - (n + 2) T(n) = c
$$
This is a linear recurrence of the first order. Divide by $(n + 1) (n + 2)$ to get:
\begin{align}
\frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1}
  &= \frac{c}{(n + 1) (n + 2)} \\
\sum_{0 \le k \le n - 1}
    \left( \frac{T(k + 1)}{k + 2} - \frac{T(k)}{k + 1} \right)
  &= c \sum_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\
\frac{T(n)}{n + 1} - T(0)
  &= c \sum_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\
  &= c \left( 1 - \frac{1}{n + 1} \right) \\
  &= c \frac{n}{n + 1} \\
T(n)
  &= T(0) (n + 1) + c n
\end{align}


In Agda's GADT, are "parameterized" and "indexed" different semantically? I know they have different scoping:
data a (n : Set) : Set where
    introA : a n

data b : Set -> Set where
    introB : {n : Set} -> b n

That's not what I'm caring about. Are they different semantically?

The following explanation lacks mathematicial precision but should explain what is going on.

A GADT is a special case of a recursive type. A recursive type $T$ is a solution of a type equation of the form
$$T = \Phi(T).$$
(If this is not clear, please ask.)
Sometimes $\Phi$ depends on a parameter $p : P$ of some given type $P$, so we have a parameterized equation
$$T = \Phi(p, T).$$
Now the solution $T$ is not just a type, because it depends on $p$, so we get a dependent type $T : P \to \mathsf{Type}$ such that
$$T(p) = \Phi(p, T(p))$$
for all $p : P$.

We may also consider recursive equations in collections other than $\mathsf{Type}$. For example, an equation in $\mathsf{Type} \times \mathsf{Type}$ is a mutual recursive type
$$(T_1, T_2) = \Phi(T_1, T_2).$$
The types $T_1$ and $T_2$ can be arbitrarily entangled, i.e., there is no guarantee that we can separate the equation into two equations
$T_1 = \Phi_1(T_1)$ and $T_2 = \Phi_2(T_2)$. If we could separate like that, we would be back to the previous case of a parameterized fixed-point equation (the parameters ranging over $\{1, 2\}$).

We could similarly solve simultaneously for three, four, etc. types. In general, given any type $I$, we can solve an equation which is simultaneous in $I$-many types $T_i$, one for each index $i : I$, which gives us an indexed equation
$$(T_i)_{i : I} = \Phi((T_i)_{i : I}).$$
The above notation is a bit ugly and it would be better to write
$$T = \Phi(T)$$
where it is understood that the uknown $T$ is a dependent type $T : I \to \mathsf{Type}$ indexed by $I$. Again, there is no guarantee that we can disentangle the equation into $I$-many separate equations of the form $T_i = \Phi_i(T_i)$.

The two kinds of equations translate back to recursive and inductive type definitions. Let us write $\mathsf{rec}_U\,\Phi$ for the solution of a fixed-point equation $X = \Phi(X)$, where $X : U$ and $\Phi : U \to U$. We now have:

Given a map $\Phi : A \to \mathsf{Type} \to \mathsf{Type}$, the type family $R : A \to \mathsf{Type}$ given by
$$R = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}}\,(\lambda X : \mathsf{Type} \,.\, \Phi(a, X))$$
is a recursive type with a parameter $a : A$, as in the first case.
Given a map $\Psi : (A \to \mathsf{Type}) \to (A \to \mathsf{Type})$, the type family $Q : A \to \mathsf{Type}$ given by
$$Q = \mathsf{rec}_{A \to \mathsf{Type}}\,(\lambda F : A \to \mathsf{Type} \,.\, \Psi(F))$$
is a recursive type with index $a : A$, as in the second case.

It should be clear that $R$ and $Q$ are not the same thing. In $R$ we solve one fixed-point equation in $\mathsf{Type}$ for each parameter $a : A$, whereas in $Q$ we solve a single fixed-point equation in $A \to \mathsf{Type}$.
As a sanity check you should try to translate your examples to the above notation.

Lastly, the indexed recursive types are more general than the parametrized ones. Indeed,
$$R = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}}\,(\lambda X : \mathsf{Type} \,.\, \Phi(a, X))$$
can be written as
$$
R = \mathsf{rec}_{A \to \mathsf{Type}}\,(\lambda F : A \to \mathsf{Type} \,.\, \lambda a : A \,.\, \Phi(a, F(a))).
$$
In the other direction, an indexed recursive type $Q$ as above may be converted to a parameterized one precisely when $\Psi$ can be separated, which means that it has the form $\Psi(F) = \lambda a : A \,.\, \Psi'(a, F(a))$ for some $\Psi' : A \times \mathsf{Type} \to \mathsf{Type}$, in which case we have
$$Q = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}} (\lambda X \,.\ \Psi'(a, X )).$$


How can a device decipher spoken English words? I want to know how it can process spoken English words and Pull out a matching response? Is it a chip or a installed software? Does it take up a lot of space? Thanks.

You'll want to read about natural language processing.  It's an entire field of research and practice.  There are many textbooks and online resources that provide an introduction to that area.


Finding duplicates in a stream of numbers This is an interview question.
Say you have a function foo() which returns some integer.
You need to write an algorithm that does the following:

(1). Call foo() in a loop, till the returned value of foo() is -1.
(2). Returns true if during the loop there were two calls of foo() which returned the same value.

This is what I thought to do, please tell me if this is efficient enough:

(1). Initialize a hash map , which maps an integer to the number of times we got it in the loop
(2). Call foo() in a loop till the returned value of foo() is -1, while updating the hash map accordingly.
(3). Check if there is a key in the hash map which is mapped to a value greater than 1.

There might be other variations, but your answer should be pretty good.

There are two improvements to your algorithm, though.

Instead of a hashmap that counts the number of times each integer appears, you can just use a hashset to record the appearance of each integer.
While you are calling foo() in a loop, you will return immediately if you find the returned integer is in the hashset and if you are not required to finish the loop till the returned value of foo() is -1. Many built-in implementations return false when you insert an existing value into a hashset.


Existence of shortest path in a graph with no negative cycles? Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex.

How do I prove that for every vertex $v$ in $G$, there is a shortest $s-v$ path with $<= n - 1$ edges?

Where $n$ is the number of vertices in $G$.

If there is a path $P$ from $s$ to $v$, there is one where no vertex
occurs more than once, with a weight that is less or equal to $P$. Indeed, if a vertex $x$ occurs twice, there is necessarily a loop
from $x$ to itself. This loop cannot have a negative weight by
hypothesis. So by removing it, we get a path that is no heavier. This
can be repeated until we obtain a path where no vertex occurs more
than once. Hence there are at most $n$ vertices on such a path, which
means that the path has at most $n-1$ edges.

Thus we can consider only paths with at most $n-1$ edges, with each
edge occurring at most once, since any other path is no lighter than a
path in that set.

Since this set is finite, the number of edge conbinations to be used for a
path is necessarily finite too (further limited by the constraint or
forming a path from $s$ to $v$). Thus the set of weights has a minimum
corresponding to some path(s) wich is (are) the minimum /shortest path(s).


Prove that there exists a machine which decides an infinite subset of halting problem We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?

Let $M$ be a TM which accepts all inputs. Then $\{ \langle M, w \rangle \mid w \in \{ 0, 1 \}^\ast \}$ is an infinite subset of $H$ and (easily) decidable.

Going further, let $M_w$ be a TM which halts if and only if its input is not equal to $w \in \{ 0, 1 \}^\ast$ and let it be such that $\langle M_w \rangle$ is computable from any $w$ (e.g., $w$ is a substring of the description of $M_w$). Then the set $\{ \langle M_w, w' \rangle \mid w, w' \in \{ 0, 1 \}^\ast \}$ is another infinite subset of $H$ which is decidable. The description for a decider could be, for example: Given $\langle M_w, w' \rangle$, compute $\langle M_{w'} \rangle$ and accept if and only if it is equal to $\langle M_w \rangle$.

A warning: in the question text you referred to "a machine that decides any infinite subset of $H$". Indeed, no such machine exists (since $H$ is an infinite subset of itself); however, this is not what the question title (presumably the intended question) is implying.


Minimizing the maximum Manhattan distance Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself.

The points are inside a grid, –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000,  N<=100000.

In the example below the points are (1, 1), (6,1), (6,6), (3,4) and the smallest maximal Manhattan distance (equal to 5) is achieved from points (4,3), (5,2) (marked with E).

Is there an efficient algorithm to solve the problem?
The restrictions are quite large so the brute force approach wouldn't work.

Edit: problem: http://varena.ro/problema/examen (RO language)

Manhattan-distance balls are square and aligned with the diagonals, which makes this problem much simpler than the Euclidean equivalent.

Find an input point P with maximum x+y, an input point Q with minimum x+y, an input point R with maximum x-y, and an input point S with minimum x-y. The minimum maximum distance d is the maximum of ceiling(((P.x+P.y) - (Q.x+Q.y))/2) and ceiling(((R.x-R.y) - (S.x-S.y))/2) or sometimes that quantity plus one. Accordingly, for each center C, we can compute the bounds on C.x+C.y and C.x-C.y so that (P.x+P.y) - (C.x+C.y) <= d and similarly for Q, R, S. Then there's some simple formula to count the points in that rotated rectangle. If the count is zero, increase d and try again.

The overall running time is O(N).


Finite automata start state Can a finite automata not have a start state?
I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.

It depends on the definition. Some definitions of a deterministic finite automaton (DFA) are a quadruplet $(Q, \delta, q_0, F)$ where $Q$ is the set of states and $q_0 \in Q$ is the initial state. Therefore, it must be defined.
However, the definition of non-deterministic finite automaton (NFA) is sometimes seen as a quadruplet $(Q, \Delta, I, F)$ where $Q$ is the set of states and $I\subset Q$ is the set of initial states. Here, you can chose $I = \emptyset$ and get an automaton without initial state.
Since a DFA can be seen as a special case of a NFA, it is not necessary for an automaton to have an initial state. In both cases (DFA and NFA), the language recognized by an automaton without initial state is $\emptyset$.


Sorting networks hybrid sort I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 elements) fixed size array, would it make sense to use them in quicksort or mergesort when the recursive call is for an array with less than the given threshold?

The article Applying Sorting Networks to Synthesize Optimized Sorting Libraries by  Codish et al. experiments in this area, trying to take advantage of "instruction  level  parallelism  and  non-branching  conditional assignment instructions, both of which are common in modern CPU architectures", and create a quicksort implementation that falls back on sorting networks instead of falling back on insertion sort. In their tests, the result was faster than with the insertion sort fallback. That said, the paper only analyses how it performs with int, and has a dedicated "copy-and-swap" algorithm for int to order two integers without branches.

The hybrid sorting algorithm RADULS2 described in Even faster sorting of (not only) integers by Kokot et al. seems to use sorting networks too. The following note is rather interesting:

  Yet it is worth mentioning, that our implementation of sorting network for 16B records uses SSE to allow elements swapping by branchless code. Without such optimization [sorting networks] performed much worse as compilers tend to produce the code with branching instructions. The cost of swapping the elements is easy observable in case of 32B records—in such a situation [enumeration sort] clearly outperforms [sorting networks].

Access Aligned Sort uses bitonic sorting networks to improve a bottom-up mergesort and ends up with an algorithm that is faster that standard implementations of std::sort when sorting properly aligned float arrays. The algorithm uses [Boost.SIMD] to take advantage of SIMD instructions.

Finally, I've also experimented with sorting networks in a library of mine: I managed to obtain sorting algorithms which were faster than the usual insertion sort for small arrays of int, but I had to use the "copy-and-swap" trick described in Applying Sorting Networks to Synthesize Optimized Sorting Libraries to make them efficient, and I realized that it didn't really improve things for long or long long integers. The number of comparison tends to make the algorithm too slow compared to a simple insertion sort, which is adaptive. I tried to use them as a fallback algorithm for quicksort instead of insertion sort, but it didn't make an observable difference.

GPU sorting networks and hardware sorting networks would probably outperform most sorting algorithms, but I don't know much about those. Some guy implemented a few sorting networks with CUDA, you might want to take a look.

Conclusion: if you only need to sort small arrays, sorting networks are worth it, but they generally require implementers to carefully implement them if they want decent speed, and most of the time, unless you're sorting something else than raw collections of integers or floating point numbers, they aren't faster than usual sorting algorithms. When you use them as a fallback, it doesn't even always make a speed difference, so unless you really need that speed, they're not worth the implementation cost.


What important/crucial real-world applications use blockchain? As part of some blockchain-related research I am currently undertaking, the notion of using blockchains for a variety of real-world applications are thrown about loosely.

Therefore, I propose the following questions:

What important/crucial real-world applications use blockchain?
To add on to the first question, more specifically, what real-world applications actually need blockchain - who may or may not currently use it?

From a comment, I further note that this disregards the notion of cryptocurrencies. However, the use of smart contracts can have other potential applications aside from benefits they can pose to the area of cryptocurrencies

Apart from Bitcoin and Ethereum (if we are generous) there are no major and
important uses today.

It is important to notice that blockchains have some severe limitations.  A
couple of them being:

It only really works for purely digital assets
The digital asset under control needs to keep its value even if it's public
All transactions need to be public
A rather bad confirmation time
Smart contracts are scary

Purely digital assets

If an asset is actually a physical asset with just a digital "twin" that is
being traded, we will risk that local jurisdiction (i.e. your law enforcement)
can have a different opinion of ownership than what is on the blockchain.

To take an example; suppose that we are trading (real and physical) bikes on the
blockchain, and that on the blockchain, we put its serial number.  Suppose
further that I hack your computer and put the ownership of your bike to be me.
Now, if you go to the police, you might be able to convince them that the real
owner of the bike is you, and thus I have to give it back.  However, there is no
way of making me give you the digital twin back, thus there is a dissonance: the
bike is owned by you, but the blockchain claims it's owned by me.

There are many such proposed use cases (trading physical goods on a blockchain)
out in the open of trading bikes, diamonds, and even oil.

The digital assets keep value even if public

There are many examples where people want to put assets on the blockchain, but
are somehow under the impression that that gives some kind of control.  For
instance, musician Imogen Heap is creating a product in which all musicians
should put their music on the blockchain and automatically be paid when a radio
plays your hit song.  They are under the impression that this creates an
automatic link between playing the song and paying for the song.

The only thing it really does is to create a very large database for music which
is probably quite easy to download.

There is currently no way around having to put the full asset visible on the
chain.  Some people are talking about "encryptions", "storing only the hash",
etc., but in the end, it all comes down to: publish the asset, or don't
participate.

Public transactions

In business it is often important to keep your cards close to your chest.  You
don't want real time exposure of your daily operations.

Some people try to make solutions where we put all the dairy farmers' production
on the blockchain together with all the dairy stores' inventory.  In this way we
can easily send trucks to the correct places!  However, this makes both farmers
and traders liable for inflated prices if they are overproducing/under-stocked.

Other people want to put energy production (solar panels, wind farms) on the
blockchain.  However, no serious energy producer will have real time production
data out for the public.  This has major impact on the stock value and that kind
of information is the type you want to keep close to your chest.

This also holds for so-called green certificates, where you ensure you only
use "green energy".

Note:  There are theoretical solutions that build on zero-knowledge proofs
that would allow transactions to be secret.  However, these are nowhere near
practical yet, and time will show if this item can be fixed.

Confirmation time

You can, like Ethereum, make the block time as small as you would like.  In
Bitcoin, the block time is 10 minutes, and in Ethereum it is
less than a minute (I don't remember the specific figure).

However, the smaller block time, the higher the chance of long-lived forks.  To
ensure your transaction is confirmed you still have to wait quite long.

There are currently no good solutions here either.

Smart contracts are scary

Smart contract are difficult to write.  They are computer programs that move
assets from one account to another (or more complicated).  However, we want
traders and "normal" people to be able to write these contracts, and not rely on
computer science programming experts.  You can't undo a transaction.  This is a
tough nut to crack!

If you are doing high value trading, and end up writing a zero too much in the
transaction (say \$10M instead of \$1M), you call your bank immediately!  That
fixes it.  If not, let's hope you have insurance.  In a blockchain setting, you
have neither a bank, nor insurance.  Those \$9M are gone and it was due to a
typo in a smart contract or in a transaction.

Smart contracts is really playing with fire.  It's too easy to empty all your
assets in a single click.  And it has happened, several times. People have lost hundreds of millions of dollars due to smart contract errors.

Source: I am working for an energy company doing wind and solar energy
production as well as trading oil and gas.  Have been working on blockchain
solution projects.


If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$ The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp:

  Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is reducible to $\overline{L}$ in polynomial time.

I am not sure if my solution idea is correct. Anyone knows the correct solution of this exercise?

My idea is: I use the definition of NP-complete. Q is in NP class and L is NP-complete. The function f to reducible in polynomial time Q to L, is also the function f to reducible in polynomial time notQ to notL

By hypothesis $Q \le_p L$, i.e., there exists a poly-time computable function $f(x)$ such that $x \in L \iff f(x) \in Q$. Then:
$$
x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \in \overline{Q}.
$$

Therefore $\overline{L} \le_p \overline{Q}$.


Red-Black tree height from CLRS The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is

$$h(n) \leq 2\log_2(n+1)$$

There's a subtle step I don't understand. The property 4 reported at the beginning of the chapter states:

  If a node is red, then both its children are black.

And because of such property it is later stated

  According to property 4, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least $h/2$.

I can intuitively agree, but as exercises I'd like to prove it, but I can't manage how to actually do it. Why is that property true? I'm not actually neither able to set up the problem, the only think I could think of was that I if I have $r + b = h$ nodes, where $r$ is the number of red nodes and $b$ is the number of black nodes I can have a total of

$$
k = \frac{h!}{r!b!}
$$

And I'd like to prove from here that if $b < r$ than I have the contradiction, but I need something more that this probably. Any help?

step 1 : At first let me say that , property 4 which states that children of a red node , should be black , comes from the definition of red-black tree , because 2 (or more) red nodes can't come after each other .
step 2 : For the statement that is a result of property 4 :
let's consider a path from root to a leaf , which consists of 2K nodes, and the number of Red ones, is more than the number of black ones, so at least number of red nodes must be K+1 and therefore number of black nodes is K-1. From property 4 we shouldn't put 2 (or more ) red nodes consecutively , so between every 2 red nodes , we should put a black one and since we have (at least) K+1 red node and (at most) K-1 black nodes , after we put the Kth red node , we will run out of black nodes and we have to put the (K+1)th red node right after the Kth red node , so we get two red nodes placed consecutively (you can prove it by induction )and this is in contradiction with Red-Black tree definition. so "at least half the nodes on any simple path from the root to a leaf, not including the root, must be black"
step 3 : For the Height of the tree :
we know that the height of a tree ,  is the number of edges in the longest path from root to a leaf and from what we proved in step 2 , at least half of the nodes on this path can be black , so if we have the height of h , at least we have h/2 black nodes , which comes to say that the black-height is at least h/2 .
step 4 : And for your solution , I guess you are being too general , in my idea you'd better consider number of red and black nodes , in an arbitrary path from root to a leaf rather than in the whole tree .
Hope it works as an idea not the whole solution :)


Does it matter if I reverse the arguments order of a lambda calculus function? what is the difference between the below functions?
$$\lambda x.\lambda y.f(x, y)$$
$$\lambda y.\lambda x.f(x, y)$$

And it appears that there is a $\texttt{reverse operation}$ in lambda calculus which can reverse the order of the arguments. So does the order actually matter?

I am asking this question because I am reading this paper, in which the author reverse the argument order in the 5th page:
$$ [\![ R[b]]\!] = \lambda y.\lambda x.[\![b]\!](x, y)  $$
Here $R$ is the ${reverse}$ $operator$. I am not sure why the author did this. And why it matters to change the order in which the arguments are taken.

You can compute either of them from the other, by using the aforementioned "reverse arguments" function.

However, they are very different as functions. For instance, the usual encoding of true is $\lambda xy.\, x$ while false is encoded as $\lambda yx.\, x$ ($\alpha$-equivalent to $\lambda xy.\, y$), which is the flipped version of true. True and false are meant to be different.

Indeed, if we had true and false equal then, for any $M,N$
$$
M =_\beta^2 (\lambda xy.\, x) M N =_{Hp} (\lambda yx.\, x) M N =_\beta^2 N
$$
So, we would get that all $\lambda$-terms are equal, making the whole theory of lambda calculus trivial.


What happens with register usage in deeply nested functions calls (in theory)? I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, where each function had let's say a dozen temporary variables throughout. What happens to register usage? It seems like everything would have to be stored in memory and the register usage would almost be negligible. What is it like in reality? Where am I going wrong?

Ignore recursion for the moment, and pretend that a recursive call is just like any other call.

Then the solution is easy: all local variables are spilled to the stack across calls, including the recursive call. So yes, if there is deep recursion going on, most of the local variables will reside on the stack most of the time.

Every platform (operating system + CPU family) defines a protocol called the application binary interface, or ABI for short. This specifies how parameters are passed to a function, how values are returned, how the stack is to be managed, and so on. If you want to see what a real-world ABI looks like, see the SysV ABI for Intel x86-64/AMD64. Almost all operating systems follow this ABI on that family of CPUs, with Windows being the most notable exception.

The ABI will specify that some registers are not preserved across function calls (i.e. they are caller-save) and some are preserved (i.e. they are callee-save). A callee-save register must be preserved by a function if it wants to use that register, and a caller-save register must be explicitly spilled across a call if the caller needs the value.

It's also possible to optimise recursion, as long as the function ultimately presents itself to the rest of the system as if it obeys the ABI. This is where things get interesting.

Tail call optimisation is the most common scenario. If the last thing that a function does in some code path is to call another function, it's sometimes possible to transform the last call into a jump. And if it's a recursive call, then it can be transformed into a loop.

So this:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
}

can be transformed into this:

foo(args)
{
    while (the base case doesn't apply) {
        before_the_recursive_call();
        args = recursive_args;
    }
    return something();
}

But in that case, no local variables have to be saved across that final call. So nothing, in theory at least, needs to be spilled to the stack there.

As an aside, in C++, the semantics of RAII and exception handling often makes tail call optimisation impossible, so you won't often see this in compilers for the C family of languages.

There is a related optimisation called "middle recursion optimisation", which is used for the more familiar recursive scenario, where there is a single recursive call in the middle of a function:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
    return after_the_recursive_call();
}

This can be transformed into something like this:

foo(args)
{
    while (the base case does not apply) {
        before_the_recursive_call();
        push_anything_to_the_stack_that_the_last_part_needs();
        args = recursive_args;
    }

    return_value = something();  // base case

    while (pop_the_stack()) {
        return_value = after_the_recursive_call();
    }
    return return_value;
}

Again, this is rare in C-like languages. You would more typically find it in functional or logic languages which don't have loop constructs, and only have recursion. In a language like that, it's often worth going to a lot of trouble to optimise recursion into loops.


Merging of two increasing binary trees why do we exchange left and right subtree We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.
One way to merge these kind of trees is as follow (we denote by $E$ the empty binary tree) :

merge ($E$, $B(l, x, r)$) = $B(l,x,r)$

merge ($B(l, x, r)$, $E$) = $B(l,x,r)$

merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_1, B(l_2,x_2,r_2)$), $x_1, l_1$) when $x_1 \leq x_2$

merge ($B(l_1,x_1, r_1), B(l_2,x_2,r_2)$) = $B($merge($r_2, B(l_1,x_1,r_1)$), $x_2, l_2$) when $x_1 > x_2$

Thus when merging two binary trees we are exchanging the left and right subtrees. I am wondering why it's important to do so ?
I guess this is because we don't want our final binary tree to be pathological like for example a tree with only nodes on it's right (which will cause a big height). If this is the reason why we exchange the left and right subtrees when merging I am wondering what make us believe that with this merging function we will not encounter pathological trees ? I mean how can we be sure that this new merging function will not produce pathlogical binary trees ?
Also it's the first time I see a merging function that exchange the left and right subtree. So is this a common thing to do for some categories of binary trees like increasing trees ?
Thank you !
Some references : Skew heap and min-heap

Both leftist heaps and the skew heaps you consider here join two trees by "zipping" the trees along the rightmost path.  Then left and right children are swapped to keep the left leaning property. In leftist heaps this in done where necessary, where in skew heaps left and right are always swapped. Hence the code.

You ask whether the skew heaps will never deteriorate into trees that have linear behaviour, instead of logarithmic. Well, this can happen.

  One may ask whether amortization is really necessary in the analysis
  of skew heaps, or whether skew heaps are efficient in a worst-case
  sense. Indeed they are not: we can construct sequences of operations
  in which some operations take O(n) time. For example, suppose we
  insert $n, n + 1, n - 1, n + 2, n - 2, n + 3, \dots  , 1, 2n$ into an
  initially empty heap and then perform delete min. The tree resulting
  from the insertions has a right path of $n$ nodes, and the delete min
  takes $\Omega ( n)$ time. (See Fig. 3.)

Quoted from the original reference "self-adjusting heaps" by Sleator and Tarjan,  SIAM Journal on Computing, which is linked on the wiki-page for skew heaps.


NP-Hard problems which are not NP-Complete Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others.
Is it always true that a ${\sf NP}$-complete problem is always a decision problem such as vertex cover of size $k$, independent set of size $k$ and many others.

No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.
In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.


Is there any good way to judge whether the rectangle is inside the point cloud? How to judge whether a rectangle in the figure is inside the given point cloud? For example, in this figure, the red rectangle is outside the point cloud and the green rectangle is outside the point cloud.

The point cloud can define a polygon.
After you define a polygon you can use the point inside polygon test on the four corners of the rectangle and see if all the points are inside the polygon.

The point in polygon test.


Correctness proof for finding weighted maximum independent set for a tree The maximum weighted independent set for a tree can found out using the following dynamic programming approach.

Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } where v ∈ children(u)

where Min[u] and Mout[u] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.

I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.

Here is an easier-to-understand dynamic programming approach. I think if you can prove this, then you can prove yours.

Let $\textsf{I}(u)$ be the weight of the weighted largest independent set of subtree rooted at $u$.

The goal is to compute $\textsf{I}(r)$, where $r$ is the root of the tree.

The recurrence relation for dynamic programming is:

$$\textsf{I}(u) = \max \{ w(u) + \sum_{v: \text{ grandchild of } u} I(v), \sum_{v: \text{ child of } u} I(v) \}$$

Can you prove (or disprove) it?

Hint: Do a simple case-by-case analysis.


Is log(n) in complexity class P? $\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P?

$n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P?

If not, what complexity classes contain those problems?

The definitions I've found all refer to "polynomial time", not "at most polynomial time".  This may be at odds with $\mathcal{O}$ being defined in terms of bounds, but I haven't found a source which clarifies the discrepancy.

Wikipedia says:

  An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.

$\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.


Smoothing in Naive Bayes model A Naive Bayes predictor makes its predictions using this formula:

$$P(Y=y|X=x) = \alpha P(Y=y)\prod_i P(X_i=x_i|Y=y)$$

where $\alpha$ is a normalizing factor. This requires estimating the parameters $P(X_i=x_i|Y=y)$ from the data. If we do this with $k$-smoothing, then we get the estimate

$$\hat{P}(X_i=x_i|Y=y) = \frac{\#\{X_i=x_i,Y=y\} + k}{\#\{Y=y\}+n_ik}$$

where there are $n_i$ possible values for $X_i$. I'm fine with this. However, for the prior, we have

$$\hat{P}(Y=y) = \frac{\#\{Y=y\}}{N}$$

where there are $N$ examples in the data set. Why don't we also smooth the prior? Or rather, do we smooth the prior? If so, what smoothing parameter do we choose? It seems slightly silly to also choose $k$, since we're doing a different calculation. Is there a consensus? Or does it not matter too much?

The typical reason for smoothing in the first place is to handle cases where $\#\{X_i = x_i | Y = y\} = 0$. If this wasn't done, we would always get $P(Y=y|X=x) = 0$ whenever this was the case.

This happens when, for example, classifying text documents you encounter a word that wasn't in your training data, or just didn't appear in some particular class.

On the other hand, in the case of the class prior probability, $P(Y = y)$, this situation should not occur. If it did this would mean you are trying to assign objects to classes which didn't even appear in the training data.

Also, I've never encountered the term $k$-smoothing. Laplace or Additive smoothing is much more common.


Implementing the GSAT algorithm - How to select which literal to flip? The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or you reach the max_tries/max_flips limit and find no solution.

I'm implementing the following algorithm:

procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

I'm having trouble interpreting the following line:

V <- the variable whose flip yield the most important raise in the number of satisfied clauses;

Isn't the maximum number of satisfied clauses what we're looking for? It seems to me that we're trying to use the solution or approximations to it to find the solution.

I've thought of some ways to do this but It'd be good to hear other points of view (The assumption is that once the variable is flipped once it is selected.):

Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.
Randomly select the variable that I will flip starting with the literals that are more common.
Pick a random literal.

Isn't the maximum number of satisfied clauses what we're looking for?

Yes, we're looking for an assignment that satisfies the maximum number of clauses (that is all of them, preferably). And to that end we ask ourselves "Which single variable will bring us closest to this goal when flipping it?" and then flip it.

  It seems to me that we're trying to use the solution or approximations to it to find the solution.

Using the solution would be if we asked "Which combination of multiple flips would give the best result?" or simply "Which assignment would be the best?". However that's not what we're doing, we're only looking one step ahead. Using an approximation of the solution seems like an accurate description. However there's nothing wrong with that. That's how greedy strategies work.

  Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.

Right.


Show that for A and B, a language J exists such that A $\leq_T$ J, B $\leq_T$ J I am working on theory of computation problems, and I came across this one:

Show that for A and B, a language J exists such that $A \leq_T J$, $B \leq_T J$

The only $J$ I can think of for the moment is the language that uses a $TM$ $N$ which contains a recognizer $M1$ for $A$, and another recognizer $M2$ for $B$. $N$ uses oracle $J$ to check if input $x\in A U B$. If $J$ accepts, then it means that either $M1$ or $M2$ will halt, so $N$ can now simultate $M1$ and $M2$ simultaneously.

But I think there should be a simpler way to solve this..... any help?

Just define $J$ as $A\oplus B = \{m \mid m =2k \text{ if } k \in A, \text{ and }  m =2k+1 \text{ if } k \in B \}$. Then $k \in A$ is decided by querying $2k \in A\oplus B$, and $k \in B$ is decided by querying $2k+1 \in A\oplus B$. Thus $A \leq_T A\oplus B$, $B \leq_T A\oplus B$.

This result is well known in the theory of computability. It establishes the least upper bound on the lattice of the Turing degrees of $A$ and $B$.


Search Space for Population Metaheuristic Optimization Problem Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S| = |(y^x)^N|.

|y^x| comes from basic combinatorics: it is the number of ways to arrange |x| objects into |y| configurations.

As an example, suppose x = (1, 2, 3, 4) and y = (1, 2, ... 5) and N = 100. Clearly, |x| = 4 and |y| = 5. The xs are drawn from some probability distribution (e.g., uniform). A configuration might look like

1 1 3 2 4

Another might be

4 3 1 1 3

for some previously-specified probability distribution. The underlying metaheuristic algorithm generates N = 100 such configurations randomly.

I am just unsure on how to incorporate N.

There are $|x|^{|y|}$ configurations.  Then you want to generate $N$ configurations.  By the same reasoning, there are $(|x|^{|y|})^N$ ways to do that.


Finding the half with greatest elements in a set Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this in $O(n)$ time?

Proceed in two phases.

Determine the median of the input.
Partition the input with the median as the pivot (cf. Quicksort).

Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.


What is the adjunct of the evaluation morphism in a closed monodical category? According to the nlab article about evaluation map if $X, Y \in C$, a closed monodical category then the adjunct to evaluation morphism $[X, Y]\otimes X \rightarrow Y$ is the identity morphism $[X, Y] \rightarrow [X, Y]$.

Is that correct and if yes why?
Because it seems to me that the adjunct of such has to be $X \rightarrow [Y, (X \otimes Y)]$

Adjuncts are morphisms related by the natural isomorphism:

$$Hom(FA, B) \cong Hom(A, GB)$$

defining the adjunction. The adjuncts of (co)units are identities:

$$
(ε_A : FGA → A)  \longleftrightarrow (1_{GA} : GA → GA) \\
(η_A : A → GFA) \longleftrightarrow (1_{FA} : FA → FA)
$$

This correspondence is basically what connects the $Hom$ definition of adjunctions with the (co)unit definition.

In this case, $FA = A \otimes X$ and $GA = [X,A]$.


How to find a local minimum of a complete binary tree? How to find a local minimum of a complete binary tree?

Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$.  You may assume that the real numbers labeling the nodes are all distinct.  A node $v \in V(T)$ is a local minimum if the label $x_v$ is less than the label $x_w$ for all nodes $w$ that are joined to $v$ by an edge.
You are given each a complete binary tree $T$, but the labeling is only specified in the following implicitly way: for each node $v$, you can determine the value $x_v$ by probing the node $v$. Show how to find a local minimum of $T$ using only $O(\log n)$ probes to the nodes of $T$.

Attribution: this seems to be Problem 6 in Chapter 5 "Divide and Conquer" from the book "Algorithm Design" by Jon Kleinberg and Eva Tardos.

As the tree is finite and the labels are real numbers, we are assured that there is a least element in the set of labels (this question from math.SE has a proof of this simple property). In this case as all the labels are distinct, it is okay that we require the local minima to be strictly less than their neighbours. If they were, then we would have to relax this condition to "less or equal to", otherwise there may not be a solution. Nonetheless we know that there is at least one local minimum to find.

If the tree is rooted (i.e. we have a notion of a parent-child relation) we can solve the problem marginally cheaper. If the tree is unrooted, then asymptotically we can do as well, but we will likely perform more actual probes.

First we'll deal with the rooted case.

As the tree is a (complete) binary tree, each vertex has at most three neighbours, its parent and two siblings (with the root of course having no parent), so a vertex is a local minimum if its label is less than the labels of its two children and parent. Hence we can determine if a vertex is a local minimum or not with at most four probes (in fact as we will traverse the tree in an ordered fashion, we will need at most three in the rooted case).

To actually find a local minimum, we can traverse the tree, starting with the root as the current vertex, in the following fashion:

Probe the current vertex's label, and the labels of its two children.
If the current label is the smallest, halt and report that the current vertex is a local minimum.
Else set the current vertex to the child with the smallest label, and return to step 1.

As we start from the root, we never need to worry about the parent's label - the root has no parent, and if our current vertex has a parent, then we must have discounted it in the previous iteration. Note that in step 2 it's not strictly required that we choose the smallest label, any that is smaller than the current is sufficient1, picking the smallest just gives a definite choice (again because we have distinct labels).

As we select one vertex out of the two children, our traversal picks out a path from the root to (at furthest) a leaf, thus as we have a binary tree of depth $d < \log n + 1 $ (as it's a complete binary tree with $n = 2^{d}-1$ vertices), we perform at most $3d \in O(\log n)$ probes.

In the unrooted case, we don't have such a convenient starting point, however we still have the tree structure (even if the algorithm doesn't know it). We can use the following algorithm:

Pick any vertex to be the initial current vertex.
Probe the label of the current vertex and all of its neighbours.
If the current vertex has the lowest label, halt and report it as a local minimum.
Else, select the neighbour with the lowest label as the new current vertex and return to step 2.

At each iteration we only perform at most 4 probes, so the question is how many iterations can there be? The key is to observe that we can never backtrack (we know that were we came from had a bigger label), so we must follow a simple path in the graph, but as the graph is actually a complete binary tree, the longest simple path has length $2d$. Thus even in the unrooted case we perform at most $8d \in O(\log n)$ probes.

For correctness we look at the second algorithm (the rooted case is clearly just a special case of the unrooted).

The fact that the algorithm can never backtrack also guarantees termination, as the graph is finite. Now we need only demonstrate that the vertex $v$ we terminate at is in fact a local minimum. Assume for contradiction that it is not, then it has some neighbour $u$ that has a label with a lower value. We have three cases: (1) $u$ is the previous vertex in the path which the algorithm has followed, in which case when the algorithm was at $u$, it would not have selected $v$ as the next vertex; (2) $u$ is appears in the path, but more than one iteration earlier, in this case the graph is not a tree; and (3) $u$ is not in the path the algorithm followed, but then the algorithm would select $u$ as the next vertex in step 4, and the algorithm would not have terminated at $v$. Thus $v$ must be a local minimum.

Another way to see this is to simply observe that the sequence of labels of the vertices selected by the algorithm is monotonically decreasing. From this both the termination and correctness follows immediately.

Footnote:

The property that allows this is that every subtree has a local minimum - again, every finite set which has a total ordering has a least element. Thus by induction, when we extend the subtree with a new root and a sibling-subtree, we have three cases: (1) the new root is smaller than both its children, so the algorithm would terminate the new root; (2) the new root is smaller than one child but not the other, then the algorithm will not choose the larger root and must take the smallest by definition; or (3) both children are smaller, but in this case, as noted, each subtree has at least one local minimum, so we may select either.


Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$? In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u_i \rangle = \sum^n_{j=1} x[j] u_i[j]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?

I just noticed that if we have one disagreement then we change one single entry from +1 to -1. Thus, the summation decrease by 1 because we are missing one of the +1's in the summation but on top of that because they are Rademacher vectors instead of simple binary 0,1 then it means that the +1 actually changes to -1, meaning the inner product decreases by an additional 1.

So it decreases by 2 cuz:

we lose a +1 in the summation
but we also replace the +1 with a -1

so total decrease is by two leading to $ \leq n-2$


Reducing a system of two boolean algebra assertions to a single one Given a system of two Boolean Algebra equalities

a = b.
c = d.

one can exhibit a single equation

F(a,b,c,d) = 0.

which is equivalent to the former system. (Symmetric difference is pivotal for constructing such quaternary operation F(a,b,c,d)).

Questions:

Is there binary operation x ? y (infix notation) such that

a ? c = b ? d.

is equivalent to the original system?
Is there binary operation x ? y  such that

a ? b = c ? d.

is equivalent to the original system?

Edit (June 13): The question is more subtle than I managed to convey. Boolean algebra is a finitely definable variety. I was wondering if we can get a single axiom system by combining identities. Padmanabhan proved in 1968 that every definable class of lattices (such as BA) can be defined by a single identity within the class of lattices. The key observation in his method is equipping the identities

a = b.
c = d.

with disjoint sets of variables. Then, simple disjunction

a v c = b v d.

would do.

No.  There is no such binary operation.

This is easy to prove with a counting argument.  Given a candidate binary operation $?$, count the number $n$ of boolean values $x,y$ such that $x?y$ is true.   Out of the 16 possible values for $a,b,c,d$, exactly $m=n^2+(4-n)^2$ of them will satisfy $a?c = b?d$.  The possible values for $m$ are $m \in \{16,10,8\}$.  However, there are only 4 possible values of $a,b,c,d$ such that $a=b$ and $c=d$, which is not in the set of possible values for $m$.

Or, you could do as David Clarke suggests and write a tiny program to enumerate all possibilities.  Frankly, you probably should have done that before asking in any case; that would have helped you ask a more specific question, such as "I know no such binary operation exists; can you give me any insight why not?".


Assume that SAT ∈ PSIZE, does it imply that NP = coNP? Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ?

I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ and $\mathrm{coNP}$ are contained in $\mathrm{PSIZE}$, but I can't see how does help me. Any ideas ?

If $SAT \in PSIZE$ then the polynomial hierarchy collapses to the second level:
$\Sigma_2 = \Pi_2$ (see Karp-Lipton theorem ); but $NP=coNP$ (i.e. $\Sigma_1 = \Pi_1$) is stronger (the PH collapses to the first level).


Is there a difference between computational graphs and neural networks? According to this post, "neural networks are a special form [of a computational graph]". I think that one can infer from that that all neural networks are computational graphs.

My question then would be: are there computational graphs that aren't neural networks?

a computational graph is made of node where is done "operation" on incoming variables. (see first paragraph from the link done in OP)

A neural network use perceptron or "neuron" model for each node. a generic example of neuron model is : Each incoming value is multiply by a "synaptic" weight, then are sum and the result will be pass to an activation function. Which will give an output result that could be project to next nodes. Neural Network can "learn" by adapting synaptic weights thanks to methods such as backpropagation or direct feedback alignment.

Any computational graph where nodes are not a kind of neuron/perceptron model are not neural network.


$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$ I'm trying to prove that for arbitrary $c > 0$,

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

Intuitively, this seems to be true to me (little-o implies some gap "between" $f(n)$ and $n^c$ that we can formally express as $\epsilon$). However, I'm having some trouble formalising this argument.

What I've done so far:

$f(n) = o(n^c) \rightarrow \exists c_0, n_0 > 0 \ s.t. \forall n \geq n_0, 0 \leq f(n) < c_0 n^c$

Suppose (for a contradiction) that no such $\epsilon$ fulfilling the above condition exists.

Then we have

$\forall \epsilon > 0, \exists n \geq n_0 \ s.t. f(n) \geq c_0 n^{c-\epsilon}$

I'm not sure how to proceed from here.

This is false. Consider for example
$$ f(n) = \frac{n^c}{\log n}. $$


Finding optimal separating value Problem description
We are given two sorted arrays of even numbers: A and B.
Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd number to predict which set an element belongs to. If an element is smaller than X, it will be assigned to A,and if it is bigger - to B.  The value should be optimal, meaning the number of improperly matched values should be minimal.
For example, if A = [2,4,6] and B = [6, 10, 12]. Separating value 3 would cause 2 mismatched values 4 and 6. Optimal would be 5 or 7, both causing one improper matched element.
The algorithm is supposed to return an optimal separating value (only one of there are many) and the number of mismatched items.
My ideas
At first I thought about using Binary Search for each element of A to find a number of elements of B smaller than it. Then repeat for B.
A better idea would be to generate candidates for such separating numbers. For example, if we only  have values 10, 50, 100 we don't have to check all odd numbers, we can just check 9, 11, 51, 101. We could then calculate prefix sums, indicating how many numbers from A are bigger than the checked value and how many elements from B are smart than that value. The sum of the two sums for a number would be the total number of errors. The only thing left is to find the value with minimal errors.
Is this approach even near optimal, maybe we can find a better way. Also, calculating such prefix sums can be tricky because if we want not to care about the range of numbers we would have to find a way to skip some numbers and that makes our iteration harder, although possible.
What are your ideas? Some pseudocode or code in Python is very welcome.

Initialize an array of pairs $T[i] = (x, c)$ containing all elements of $A$ and $B$. Let $x$ be the elements themselves, and $c = 0$ if the element came from $A$ and $c = 1$ if the element came from $B$. Then sort $T$ based on the $x$ values in ascending order.
Then the number of mistakes you'd get if you choose a value between $T[i]\text{.}x$ and $T[i+1]\text{.}x$ is:
$$\sum_{j=0}^i T[j]\text{.}c + \sum_{j=i+1}^n\left(1 - T[j]\text{.}c\right) = $$
$$(n - i) +\sum_{j=0}^i T[j]\text{.}c - \sum_{j=i+1}^nT[j]\text{.}c = $$
$$(n - i) +2\sum_{j=0}^i T[j]\text{.}c - \sum_{j=0}^nT[j]\text{.}c = $$
$$- i +2\sum_{j=0}^i T[j]\text{.}c - C$$
where $C$ is just a constant, which doesn't matter if you wish to minimize the quantity. So to find the optimal value:
S = 0
best = inf
best_i = 1
for 1 <= i <= n:
    S += 2*T[i].c
    if S - i < best:
        best = S - i
        best_i = i


How to get the expected running time of an algorithm I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise.

It uses a direct access table (hashing function $h(x)=x$), which makes the running time linear. So it creates a new array, initializes all values to false, then iterates through the given array, and since each value is an index to the hash table, it accesses that array location and changes it to $1$. If it is already a $1$, then you know that it is a repeated number.

But when getting the expected running time, you need to first define a probability space. This is the part I am confused about. How can you define a probability of a number being repeated in A, if you are just given an array with arbitrary numbers?

Usually you assume uniform distribution on inputs which share a certain parameter.
You could assume uniform distribution on e.g.

All inputs of length $n$, e.g. if your input looks like $w_1\#\dots\#w_k$, where $w_i\in\{0,1\}^*$, $n=k-1+\sum_{i=1}^k|w_i|$.
All multisets (bags) of $n$ integers up to $k$
All $n$-tuples of integers integers up to $k$ (different,since e.g. $\{1,2\}_b$ corresponds to $(1,2)$ and $(2,1)$ and $\{1,1\}_b$ only to $(1,1)$)

You can combine this with an assumption about the distribution of the parameter, say the size $n\sim \mathrm{Geo}(0.5)$. However, this is unusual, most would consider the limit of probabilities as your parameter $n\rightarrow\infty$ instead.

If you choose 3, the probability of no repeated numbers can be calculated this way:
There are different $\binom{k}{n}$ sets of size $n$ and each set corresponds to $n!$ $n$-tuples. There is a total number of $k^n$ $n$-tuples, so
$$P(\text{no repeated number})=\frac{\binom{k}{n}\cdot n!}{k^n}$$


Weak Precedence Grammar and Parsing I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?

Any help will be appreciated. If it is possible, could you give an example. Thanks

Weak precedence is first an algorithm for parsing (see Parsing Techniques - A Practical Guide 1st edition p. 186). So a weak precedence grammar would be a grammar which can be parsed by this algorithm (see the reference for a description of the algorithm, you'll probably want to start at least a few pages earlier).

IIRC, the interest of weak precedence parsing dropped at lot when practical LR(1) variants (SLR(1) and LALR(1)) were discovered, but precedence algorithms are still sometimes used in hand written parser for parsing expressions while the rest of the grammar is parsed with a recursive descend variant.


Why is augmenting path calculation O(m) I'm trying to learn augmenting paths and I got confused. I've found some other source that has the same setup that my slides have, therefore I will refer to that.
It is said that

Each augmenting path computation can be easily done in O(m) time.

in these lecture notes within a graph of m edges. I could not understand how it is O(m). Isn't trying to find an augmenting path that has capacity from source to the target an exhaustive process? Maybe I misunderstand what they mean as augmenting path computation but even if that is the case, the clarification of that would be helpful

As given in your lecture notes, and an augmenting path is an s-t path in the residual graph such that all edges on the path have a positive residual capacity.
There could be many augmenting paths in the graph. But you just need to find one such path. Therefore, you can apply DFS or BFS which takes $O(m)$ time to find one such path from $s$ to $t$.


printf("%d",~5); prints out -6 why is that? I was reading the book "Computer systems: A programmer's perspective" and saw that the operator, "~", is a NOT operator. When I use it to NOT positive integers, it returns the negative of the original number plus one. Why does that happen?

That's because computers use $2$'s complement representation of negative numbers. $5$ in binary is $101$. Assume an $8$-bit architecture. Then $5$ would be represented as $00000101$. Hence ~$5$ will flip all the bits which gives $11111010$ which is the $1$'s complement of $5$. Adding $1$ to it gives you the $2$'s complement representation which the computer interprets as $-5$. Hence ~$5=11111010$ is $-5-1=-6$.


heap pop creates unbalanced tree? say you have a min-heap.  Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something you have to do to maintain the balance of the tree?

When popping the root, it is first replaced by the very last element, and then a heapify operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.

Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.

The three steps are illustrated in the Wikipedia article. We start with a max-heap:

We remove the root, and replace it with the very last element:

Finally, we perform a heapify operation on the root:


MULT in a RISC - should instructions take the same amount of time in a RISC system I am studying computing  as part of my A level course, and my understanding is that all instructions in a RISC architecture should execute in roughtly the same, small number of clock cycles (ideally one).

This leads me to ask how multiplying two (possible very large) numbers takes (roughly) the same time as all the other commands, such as LOAD, STORE, ADD, etc.
I believe the most common way a computer multiplies numbers is using a Binary Multiplier, which requires multiple addition executions, meaning that a multiplication, or PROD command (from an example from Stanford University) will execute with many cycles per second and not be consistent with the speed/cycles of other commands from a reduced instruction set.

RISC processors are pipelined, and have been since the beginning.  That is, at a single time there are several instructions which are in different phase of execution.  That mean that there is two different numbers that you can give for the execution time.  One, the latency, which measures the time between the start of an instruction and its end.  The other, the throughput, which measures how many instructions can be executed in a given time.

When someone says that RISC have single clock instructions, they are thinking about throughput, that is that RISC processors are able to execute one instruction per clock, and not latency, that is that it take one clock to execute any given instruction.

Early RISCs did not have multiplication instructions. That was more a consequence of manufacturing process limitation of the time, which would not have allowed to put a multiplier on the chip along with the rest of the processor, than a fundamental characteristic of RISC.  With increased integration density, RISC acquired such instructions.

Note that it is possible to achieve bigger throughput than one instruction per cycle.  For that, you need to be able to decode several instructions per cycle, and have several execution unit. That is something called super-scalar and high-end processors are super-scalar since the early 90's.

Note also that the possibility to achieve the theoretical throughput in practice depend on the program (you need to have instructions which are independent to be able to execute them in parallel, you need to have the data available, and thus have pattern of memory accesses and a memory sub-system which together allow to provide the data rapidly enough).


Are "pipes" puzzles NP-hard? Is the decision version (i.e. does a solution exist) of this puzzle NP-hard (for an nxn puzzle)? It feels like it has very local strategies which allow easily solving the instances, but it's not obvious to me that these generalize to larger puzzles. The rules are as follows:

Each tile has exits on some of its edges
Each tile may be rotated but not flipped
All tiles must form a single component in solution where two adjacent are connected if both of them have exits touching
All exits must be connected to an exit on the other tile they face

It's very easy to see that brute force requires exponential time, but constructing a gadget to show that this puzzle is NP-hard seems quite difficult.

In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles. Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.

It is tough to be a plumber.
Král, Daniel; Majerech, Vladan; Sgall, Jirí; Tichy, Tomass; Woeginger, Gerhard.
In: Theoretical computer science, Vol. 313, No. 3, 2004, p. 474-484.
https://doi.org/10.1016/j.tcs.2002.12.002


P vs NP and Angle Trisection (serious question) I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.

My understanding from many popular-level sources (like Scott Aaronson's P vs NP for dummies blog post, or this New Yorker article) is that the P vs NP question asks whether a problem that can be checked "quickly” can also be solved "quickly". But to my knowledge there are well-known problems that can be checked quickly but are impossible to solve regardless of time or number of operations.

Take, for example, the (in)famous angle trisection with straightedge and compass. If asked to check that a provided angle really does trisect 60 degrees, you can very quickly verify that fact using a straightedge and compass. But if someone asks you to solve the problem of trisecting that 60 degree angle using the same straightedge and compass, you can’t do it. So the solution here really only goes "one way" (i.e. using classical tools, the 20 degree angle can be checked really quickly, but no finite amount of operations/time will ever solve the problem of constructing it).

How does this relate to P vs NP? My thought is that this would show that NOT every problem that can be checked quickly can be solved quickly. The specific case of the 60 degree angle trisection appears to be checked in P time and not solved in P time (or any time for that matter, because by using classical tools the problem of the 60 degree trisection cannot be solved at all).

I know I’m missing something, and I tried looking up the formal definition of P vs NP on the Clay Math website, and that was way over my level of understanding (I’m betting that the categories of P and NP don’t apply to my example for reasons I am just not aware of). I just went through the exercise and tried to intuit the question using some well-known math, and I’m having a tough time figuring out where my mistake is.

Any thoughtful feedback is very much appreciated :)

PS: This was moved from CS Theory StackExchange b/c it is not a research q.

Here is a possible analog of the P vs NP question for straightedge-and-compass constructions.

Suppose that we are given a line with three points $a,b,c$ on it, and consider the following question:

  Given just the line and the points $a,b$, can we construct the point $c$ using a straightedge and compass?

If we are given a construction, then we can verify that it indeed constructs the point $c$. But without such a construction, it is not clear how to check whether the point $c$ can be constructed.

However, this connection is a bit misleading, for various reasons, among which is that it is not completely clear how to specify the input, and what operations are allowed on it; in contrast, the P vs NP question is completely formal.

The P vs NP question is a scaled-down version of other questions in computability theory, whose answer is known. For example:

  Given a C program $P$, does $P$ ever halt?

If $P$ halts, then we can verify it by running $P$ and checking that it eventually halts; you can think of this as a verification process in which the witness is the execution trace of $P$. But without an execution trace, it is not so clear how to determine whether $P$ ever halts. Indeed, Turing proved that no algorithm can determine whether a given C program ever halts.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question can be stated as follows:

  Is there a polynomial time algorithm to determine whether an input graph is 3-colorable?

(A graph is 3-colorable if we can color its vertices using 3 colors so that the endpoints of each edge get different colors.)

Given a 3-coloring, it is easy to check (in polynomial time) that it is a valid 3-coloring. But without such a 3-coloring, it is not clear how to check whether a given graph is 3-colorable. Indeed, people conjecture that this cannot be done in polynomial time (but it can obviously be done in exponential time, by trying all possible 3-colorings).


Adversarial Monte Carlo Tree Search Asymmetry Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth,
growing promising subtrees more than non-promising ones.

But in a 2-player adversarial game, when a win at one node is a loss at the node below it, wouldn't the tree growth be extremely favourable for the current player at each node, and result in a not so asymmetric tree growth?

The most explored path will be the Nash Equilibrium, because at each step we choose the best move for each player.
The asymmetry happens at each level towards the best move for the current player, thus overall the tree will not grow asymmetrically.


Basic question about 4-way set associative When the CPU writes or reads from the memory and stores the value that was read or written into L1 cache. Do the CPU store the whole block( 1 block , leaves the other three ways empty) or the whole set ( 4 blocks)?

Four way set associative does not mean 4 sets.

It means each set is of 4 blocks.

Individual block can be read or written.

Go through this document for understanding the concept of set associative cache.


What data structure might this game use? This question is not about game development or about actual implementation details.

I was playing Little Alchemy yesterday.  (Warning: Productivity hazard.)  You start with the four classical Elements of earth, air, fire, and water.  You can combine them to produce other "Elements" (wood, humanity, time, cities, etc.), combine those to produce even more, etc.  All of the relationships are predefined, so the game is less about crafting and more about lateral thinking.

I got curious about how exactly the game could store and query the various combinations optimally.  Whether the developer actually does so under the hood is a different story, and not what I'm asking about.

Consider the following game mechanics:

There is no limit to the number of Elements, but it's decided in advance by the game's designer and thus does not change at runtime.
All Elements are made by combining exactly two other Elements, possibly of the same kind (Fire + Water = Steam).
Even the four base Elements can be created (Fire + Ice = Water).
Some Elements can be created through more than one combination. (Fire + Water = Energy + Water = Steam)
Some combinations produce more than one Element (Human + Cow = Minotaur and Milk)
Some Elements are "final" and cannot be combined to produce any other, though they may in future updates.  (Jedi + Swamp = Yoda)
Order of combination does not matter (e.g. Water + Fire = Fire + Water).

The game presumably needs fast lookup and low memory usage.  More specifically:

Given exactly two elements, look up the result of their combination, if any.  This should be fast.
There is no insertion or removal except by the game's designer in advance.  This can safely be slow.

Given these, what data structure might Little Alchemy use to store the various combinations that can be used to produce elements?

Initial Thoughts

Back-of-the-envelope guess?  A big ass-hash-table that maps (Element, Element) pairs to Element lists. For $n$ Elements, this results in amortized $O(1)$ lookup and $O(n^2)$ memory, because theoretically any combination can produce every other Element at once.  Can we do better?

A hashtable is asymptotically optimal.  Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces).  Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space.  You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal.  Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors.  But speaking pragmatically: I expect a hashtable will be fine.  The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.


Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$,
find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in each of $S_i$, i.e., for

$S_1$ = $\{sub_11,sub_12,sub_13\}$, where $sub_11$, $sub_12$, $sub_13$ are disjoint,

$S_2$ = $\{sub_21,sub_22\}$, where $sub_21$, $sub_22$ are disjoint

Then find
$A$ = $\{asub1,asub2,asub3\}$, where $asub1$, $asub2$ are disjoint

and

$asub1$ can be a subset of only one of $sub_11$ or $sub_12$ or $sub_13$ but not more than one of them. Same goes for $asub2$ and $asub3$.

Similarly

$asub1$ can be a subset of only of either $sub_21$ or $sub_22$ or but not both of them. Same goes for $asub2$ and $asub3$.

More formally,

$\forall sub_i \in S_i,$
and given a subset $asub \in A,$

If $Asub=\{sub_i\mid asub\subseteq sub_i\}$

$then$
$|Asub|=1$

$Example 1:$

$X = \{e1,e2,e3,e4,e5\}$

$S_1 = \{\{e1,e2\},\{e3,e4\},\{e5\}\}$

$S_2 = \{\{e1\},\{e2,e3,e4\},\{e5\}\}$

$S_3 = \{\{e1,e2,e3,e4\},\{e5\}\}$

$A= \{\{e1\},\{e2\},\{e3,e4\},\{e5\}\}$

$Example 2:$

$X = \{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12\}$
$S_1 = \{\{e1,e2,e11,e12\},\{e3,e4,e5,e6\},\{e7,e8,e9,e10\}\}$
$S_2 = \{\{e1,e2,e3\},\{e4,e5,e6,e7,e8\},\{e9,e10,e11\},\{e12\}\}$

$A= \{\{e1,e2\},\{e3\},\{e4,e5,e6\},\{e7,e8\},\{e9,e10\},\{e11\},\{e12\}\}$

Preferably the algorithm for finding $A$ should take optimal time.

P.S. Forgive me if the mathematical description of the problem is not formal enough or if there are mistakes in it, I am not a mathematician.

Without loss of generality, each asub$i$ can be taken to have exactly one element (size 1).  (If there is any solution, then there is a solution where all asub$i$'s are of size 1.)

Now it's easy to iterate over all sets of size 1 and determine which are valid for asub$i$.  Let $A$ be the collection of all such sets.  There is your solution.  As a bonus, I even gave you a solution where $A$ is as large as possible.

The running time is polynomial (in fact, quadratic), so this should be an efficient algorithm.


Test a bit substring function How do we test the following function?

bits(bitstring, i, j)

which returns a copy of the substring from i to j of some bitstring.

Consider the fixed 32-bit value:

bitstring=0x12345678

We could manually pre-determine the correct return values for ~500 different combinations of i and j. But this only covers 0x12345678.

There are 232 ≈ 4 billion different strings like 0x12345678.

Even for a non-exhaustive test,  manually recording the constants we expect to get from any combination of (bitstring, i, j) does not seem like the best solution.

I imagine we can use the fact that bit strings map to unsigned integers and do some arithmetic to compare the return value of bits to bitstring.

Any help with vocabulary or classifying this validation problem would be appreciated, too.

Technical side note: My uncertainty lies in whether the bit manipulations are being performed correctly, since the bit substring does not necessarily begin or end on a byte boundary.

Another note: After a few edits I have realized the important question here is what are the different ways we can check that one bit string is a substring of another? But the original question has a broader scope so I will leave it as it is.

You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output.  You can still do that despite "not falling on a byte boundary".

In this case the function bits is a stateful interface, so you have to deal with that, but the same techniques for testing stateful interfaces should work fine here.  In particular, the "input" is a sequence of operations on the data structure / API, and the "output" is the sequence of results from those operations.  For instance, the first operation might be to set the contents of the underlying byte stream, and the second operation might be to invoke bits().

I'm not sure where you're getting $512 \times 2^{32}$ from (presumably you mean $32 \times 2^{32}$), and those aren't permutations; but in any case that doesn't change anything.  Testing almost never exhaustively tries all combinations.  I don't see why this would be any different.  Instead, the idea behind testing is that we try a small fraction of the possibilities, and if there is a bug, we hope that one of the test cases we try will expose it.  This doesn't provide any guarantees, since there could always be a bug that only triggers on one of the test cases we didn't try -- testing is not verification, and does not prove correctness -- but it is useful nonetheless.

So, nothing prevents you from testing this function.  Standard methods work fine.


Understanding the time-complexity of Insertion Sort From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below).

INSERTION-SORT(A)                         cost     times
1  for j <- 2 to length[A]                c1       n
2      DO key <- A[j]                     c2       n - 1
3         ▷ Insert A[j] into the sorted
          ▷          sequence A[i..j-1]   0        n - 1
4         i <- j-1                        c4       n - 1
5         while i > 0 and A[i] > key      c5       sum_{j=2}^2 t_j
6            do a[i+1]<-A[i]              c6       sum_{j=2}^2 (t_j-1)
7                i <- i-1                 c7       sum_{j=2}^2 (t_j-1)
8         A[i+1] <- key                   c8       n - 1

The algorithm above shows the times that each statement is executed. But wait, why is line 1 executed n times?

Shouldn't line 1 be executed n-1 times since insertion sort starts making comparisons at the second element at the list.

Thanks in advance.

As I see this, it is clear that the array is indexed from 1 to length[A] instead of the usual 0 to length[A}-1.

The first statement is executed n times. It is just that (n-1) times it enters the loop and the last time n'th time when j > length[A] it exits from the loop.

Hence it is correctly mentioned that the internal statements get executed n-1 times.


Where in the Chomsky Hierarchy are Regular Expressions as a language? I'm referring to regular expressions as language: \begin{equation*}
 \Sigma = \{ ``a", ``b", ``(", ``)", ``*", ... \}
\end{equation*} and \begin{equation*}
 L = \Sigma^* \text{, which form a legal regular expression}
\end{equation*} I am not referring to their computational power. I did some research, but wasn't able to find anything relevant. Intuitively, I would imagine they're context-free, but am not sure how to attempt a proof.

I am trying to use this as a lemma, so a reference, or recommendation for how to attempt a proof would be extremely helpful.

Are we talking regular expressions as in only union, concatenation and star?

Consider the following grammar:

$R -> a | b | c$

$R -> R+R$

$R -> RR$

$R -> R^*$

$R -> (R)$

This captures all regular expressions. So if we're only talking in the Chomsky hierarchy, then it's clearly context free.
If you allow parentheses, it's not regular, since well-nested parentheses are known to not be regular. If you want a proof, do a homomorphism from the language of REs to the language of well-nested parentheses.

I don't know where they fit in terms of more detailed classification (i.e. $LL(1)$, $LR(0)$ etc.).

You could probably find something about this if you searched for "parsing regular expressions."


Color coding to get an FPT algoirthm for $k$ disjoint triangles Consider the following problem:
Input: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?
Assume we want to use color coding to develop an FPT Algorithm for that, as done here (starting from slide 60).
The reference material proposes the following method:

Choose a random coloring $V \rightarrow [3k]$
Check if there is a colorful solution where the $3k$ vertices of the $k$ triangles use distinct colors.

For 2. it proposes this, amongst others, this method:
Try every permutation $\pi$ of $[3k]$ and check if there are triangles with colors $(\pi(1), \pi(2), \pi(3)), (\pi(4),\pi(5),\pi(6), \dots)$
I don't understand why we have to check every permutation $\pi$ of the colors. Wouldn't it be enough to just to check each triple of vertices, see if there are a triangle and if so, only count this triangle if it only uses colors we have not seen before? So like so:

For each triple $x,y,z \in V$:

If $x,y,z$ form a triangle and colors ${c(x),c(y),c(z)}$ not in colors_seen_so_far:
2.1 colors_seen_so_far += $\{c(x), c(y), c(z)\}$
2.2 num_triangles += 1

where we initialize colors_seen_so_far = $\emptyset$ and num_triangles = $0$

No, this is not correct.

As a counterexample, suppose we have a graph consisting of a central triangle, together with 3 outer triangles, such that each outer triangle is joined to the central triangle by one shared vertex (i.e., each vertex of the central triangle is identified with one vertex of one of the outer triangles).

Clearly, a solution for $k=3$ would take the three outer triangles and not take the inner triangle.

Assume the random coloring assigns a distinct color to every vertex (otherwise there is no colorful solution).

If your greedy algorithm considers the central triangle first it will always take it, but this is incorrect.


Graph Closeness - Different result with gephi and NodeXL I'm writing a JavaScript library for calculating graph measurements such as degree centrality, eccentrality, closeness and betweenness.

In order to validate my library I use two exist applications Gephi and NodeXL to run calculation with them.
The problem is I got what looks like different results.

I build simple graph:

  (A) ----- (B)
   |         |
   |         |
  (C) ----- (D)

Gephi gave those results:

A ecc=2 close=1.333 bet=0.5
B ecc=2 close=1.333 bet=0.5
C ecc=2 close=1.333 bet=0.5
D ecc=2 close=1.333 bet=0.5

NodeXL gave those results:

A close=0.25 bet=0.5
B close=0.25 bet=0.5
C close=0.25 bet=0.5
D close=0.25 bet=0.5

Note that NodeXL does not calculate eccentrality.

Which one is right?
Are the results really different?

I didn't normalize (or at least not intend to normalize) any results.

The closeness of a node in a graph is defined as the reciprocal of the sum of all distances to other nodes.

Since your example is completely symmetric, we only calculate the closeness centrality of $A$.

distance $A\to B$ is 1
distance $A\to C$ is 1
distance $A\to D$ is 2

Therefore the sum of the distances is 4, and the closeness of $A$ is $1/4$. This shows that the NodeXL results are correct. I would advise you to have a look at the manual of Gephi to check how the closeness is computed here. It should be definitely be smaller than 1.