Stable marriage problem with only one side having preferences I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and through a series of proposals, we end up with a stable matching.

Thinking of it like medical schools and applicants, each medical school has a different number of slots available, so is there an intuitive or simple augmentation to the basic algorithm that solves this case?

The second question is, what if only one side has a preference ranking? For example, say medical students have preferences, but the schools do not, and simply have some number of spaces available (different between each school). All (or many of) the students (say 50 students) prefer school A, but it only has 5 slots or so. Is it possible to determine if there is a "matching" that allows everyone to get a choice in their top 3 or top 5 or something along those lines?

Clearly, if schools A, B, C have only 5 slots each, and 10 students rank the schools 1. A, 2. B, 3. C it is not possible for everyone to have their top 3. There are 30 "wants" and only 15 available slots. What I am interested in is determining if it possible and if possible, finding one of those matchings.

If this question makes no sense I can try to elaborate the specific use case it came up in.

The answer to your first question is: yes, there is a simple augmentation.  It is described in the standard literature on the stable marriage problem.  See the Wikipedia article for references in the literature where this is described.  It is also described here: The stable marriage algorithm with asymmetric arrays.  See also https://cs.stackexchange.com/a/28528/755.

Your second question is an instance of the assignment problem.  We form a bipartite graph, with an edge between a doctor $d$ and a school $s$ if the school $s$ is among $d$'s top 3 choices.  Then we want to know whether there is a perfect matching in this graph.  (If a school has multiple slots, then make multiple copies, one copy per slot.)  There are polynomial-time algorithms to determine whether a bipartite graph has a perfect matching.  See also Existence of bipartite perfect matching.

So, the answer to your second question is: yes, it is possible.


Find pair with maximum Appeal value Find pair with maximum Appeal value.

Input: Array
Output: index {i, j} ( i = j allowed) with maximum Appeal
Appeal = A[i] +A[j] + abs(i-j)

Example 1:

Input: [1, 3, -1]
Output: [1, 1]
Explanation: Appeal = A[1] + A[1] + abs(0) = 3 + 3 + 0 = 6

Example 2:

Input: [1, 6, 1, 1, 1, 1, 7]
Output: [1, 6]
Explanation 6 + 7 + abs(1 - 6) = 18

Example 3:

Input: [6, 2, 7, 4, 4, 1, 6]
Output: [0, 6]
Explanation: 6 + 6 + abs(0 - 6) = 18

I'm not sure how to approach this problem. I've tried the 2 pointer approach as below and it seems to work for some cases but I'm missing some fundamental intuition about it.

public static int[] maximumAppeal(int[] A) {
    int left = 0;
    int right = A.length - 1;
    int max = 0;
    int[] r = {-1,-1};
    while (left <= right) {
        int sum = A[left] + A[right] + Math.abs(left - right);
        if (A[left] <= A[right]) {
            if (sum > max) {
                max =sum;
                r[0] = left;
                r[1] = right;
            }
            left++;
        } else {
            if (sum > max) {
                max = sum;
                r[0] = left;
                r[1] = right;
            }
            right--;
        }
    }
    return r;
}

Edited:
Here's the link, its an Amazon question
https://leetcode.com/discuss/interview-question/355698

Let $B[i] = A[i] + i$ and let $C[j] = A[j] - j$. You are looking for
$$
\max_{i \geq j} B[i] + C[j] = \max_j (C[j] + \max_{i \geq j} B[i]).
$$

This gives a linear time in-place algorithm for your problem:

maxB = A[n] + n
maxSum = A[n] - n + maxB
for j=n-1 downto 1:

maxB = max(maxB, A[j] + j)
candidate = A[j] - j + maxB
maxSum = max(candidate, maxSum)

return maxSum


Why isn't P and P/poly trivially the same? The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?

The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, \dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_{i+1}$: they could be completely different. In particular, for any set $S\subseteq\mathbb{N}$, you could set declare $C_i=\mathrm{true}$ if $i\in S$ and $C_i=\mathrm{false}$ for $i\notin S$. Even if $S$ is undecidable!

In contrast, a language is in $\mathrm{P}$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.

You're correct that we can evaluate any fixed circuit in $\mathrm{P}$. But that's not necessarily enough to decide a language in $\mathrm{P/poly}$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.


Why is f(n) of class O(g(n)) in this graph? There is a lot of explanation about big O, but I'm really confused about this part.

Acoording to the definition of Big-O, in this function

$$f (n) \le c  g(n), \quad \text{for } n \ge n_0$$
$f (n)$ is   $O(g(n))$.

But a description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

So for example  34 is a upper bound for the set $\{ 5, 10, 34 \}$.

So in this graph, how is $f(n)$ in $O(g(n))$ because if I get the upper bound of $g(n)$ function its value would be different than what is mentioned here for $n\ge n_0$.

I think you're confused about the notion of upper bounds for a function. We're not trying to compute an upper bound for the function $f$ in the sense of saying that, e.g., $f(n) \leq 45$ for all $n$ (or all $n$ greater than some $n_0$). Rather, we're trying to say that, for all $n>n_0$, the value (number) $c\,g(n)$ is an upper bound for the value $f(n)$. The graph indicates this informally (since it only shows what happens for some unstated but limited range of values of $n$).


Finding unique cubiods with given volume I have an interval of intigers and I need to find all unique cuboids which have volume that falls within said interval.

I came up with a loop that goes over all uniqe combinations of 3 numbers (size of the cuboid) (1x1x1, 1x1x2, ...; also 2x1x1 is considered the same as 1x1x2) from 1 to the upper range of the interval. And then checks if the calculated volume falls within the interval. This solution works perfectly if the upper range isnt is too large. But if the interval ends in thousands the solution becomes very slow.

I am not really interested in code as I am in an algorithm on how to solve this differently. How would you go on about solving this?

Hint. Once you've chosen the first two dimensions, it's trivial to calculate what (if any) range of values for the third dimension give a volume within your interval.


Problem with understanding the Mathematical Equations related to Testing Tool I have downloaded the slides from the site:
[Compliance and Violation Patterns
It says No writes after calls. I can understand this concept. It’s a remedy for reentrancy problem. But it shows compliance and security patterns in some technical language related to Datalog or to some language related to software representation. Can some body please guide me what is the meaning of those equations?

Zulfi.

They are statements about patterns of correct and incorrect code:

For all call sites L1, there does not exist a store site L2 such that ... (and here I’m not clear—is that L2 may follow L1? Or that the truth of the statement may follow from the program, depending on L1 and L2?)
For all call sites L1, there exists a store site L2 such that ... (idem.)


Tightest upper bound on length of distinguishing string in Hopcroft's algorithm Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable.

What is the tightest possible upper bound (with proof) on the minimum length of a string that distinguishes two distinguishable states?

This question is taken directly from Hopcroft, Mowtani, & Ullman, Exercise 4.4.3.  I believe that the tightest upper bound is $\frac{(n-1)(n-2)}{2}-1$, but other sources I have found indicate that the tightest bound is $n-2$.

Let $Q$ be the set of states, $|Q|=n$. Consider the equivalence relation $E_i\subseteq Q\times Q$ of "indistinguishability by strings of length at most i".
Let $k$ be the tightest upper bound. We have a pair of distinguishable states $p,q$ for which the shortest distinguishing string $w$ has length $k$, i.e., $(p,q)\in E_{k-1}\setminus E_{k}$. By reading the first letter $w_1$ of $w$ we also get a pair of states $(\delta(p,w_1),\delta(q,w_1))\in E_{k-2}\setminus E_{k-1}$ for which the shortest distinguishing word has length $k-1$ (it is the word $w_2\dots w_k$). We can continue the same argument down to $0$.
Therefore, $E_0\supsetneq E_1\supsetneq\dots\supsetneq E_{k-1}\supsetneq E_k= E_{k+1}=E_{k+2}\dots$.
The equivalence $E_0$ has two equivalence classes (parts): the accepting and the nonaccepting states. (Assuming that there is at least one accepting and at least one non-accepting state; otherwise nothing is distinguishable and the tightest bound is $-\infty$.) And any equivalence relation can have at most $n$ parts.
By the chain of strict inclusions above, $E_1$ has at least 3 parts, $E_2$ has at least $4$ parts, etc., and $E_{n-2}$ has (at least) $n$ parts which means that $E_{n-2}$ is the identity relation. This implies that the worst-case bound is $k=n-2$.
This bound is tight: Consider a two-element automaton with one accepting and one non-accepting state. We have $n=2$ and $k=0=n-2$.


Why are Complexity Notations Called Asymptotic? Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?

I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes.

The word asymptotic stems from a Greek root meaning "not falling together". When ancient Greek mathematicians studied conic sections, they considered hyperbolas like the graph of $y = \sqrt{1 + x^2}$ which has the lines $y = x$ and $y = -x$  as "asymptotes". The curve approaches but never quite touches these asymptotes, when $x \to \infty$.
Nowadays we use "asymptotic" in a broader sense to mean any approximate value that gets closer and closer to the truth, when some parameter approaches a limiting value [emphasis added]. For us, asymptotics means "almost falling together".


Why is {w | no prefix of w starts with b} = {w | the first character of w is a} ∪ {e}? \begin{align} L &= \{ w \in \{a, b\}^* \mid \text{ no prefix of $w$
 starts with $b$}\} \\ &= \{w \in \{a, b\}^* \mid \text{ the first
 character of $w$ is  $a$} \} \cup \{e\} \end{align}

Why is it in union with an empty string? If an empty string from $b$ can also be a prefix.

The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.


Complexity of natural language processing problems Which natural language processing problems are NP-Complete or NP-Hard?

I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any results.

None of the NLP questions that are recommended are helpful, the closest are the following:

https://cs.stackexchange.com/questions/25925/why-is-natural-language-processing-such-a-difficult-problem
https://cs.stackexchange.com/questions/9920/how-is-natural-language-processing-related-to-artificial-intelligence
What aspects of linguistics are necessary or good for natural language processing?

The Wikipedia list of NP-complete problems does not list any complexity results for NLP.

The only lead I've found is the paper Theoretical and Effective Complexity in Natural Language Processing by J. Morin (1995).

Any help or pointers is appreciated!

Maybe one should first define what is a natural language processing (NLP)
problem.

For example, Context-Free (CF) grammars and languages were introduced
by linguists (Chomsky type 2 language, work of Bar-Hillel and others).
Ambiguity is a major problem in Linguistics for real sentence
analysis, and in the formal study of CF grammars (ambiguity) and
languages (inherent ambiguity). Ambiguity of a grammar is only semi-decidable.

So I guess the problem of ambiguity should be an answer to your
question. Does it classify as a NLP problem?

Now if you take some modern formalizations of syntax, such as a CF
backbone with feature structures (i.e. structured attributes), you
quickly get Turing power (cf LFG which have been proved NP hard, or
even Turing complete, depending on variants). So , if you are not careful, you
have all the complexity problems you might dream about.

For more, you can also look at this question from SE-Linguistics:
"Does the P versus NP conjecture in computer science have any direct
relevance to linguistics?"

In my own answer, I actually criticize the meaningfulness of the
question, or at least of some of its interpretations. Many of the
problems that are considered in linguistics, regarding analysis of
sentences, for translation or other purposes, are small problem, to be
solved in a very short time. Some linguists might even dispute that
there is real recursion in language structure, since whatever
recursion there is is rarely very deep. Hence one might wonder about
the linguistic relevance of complexity analysis which is defined
asymptotically. The first question should be whether we ever get close
enough to the asymptote for asymptotic analysis to be meaningful.

However, this remark does not apply to some aspect of NLP, when
massive amount of data have to be processed. I know of at least two
cases:

data mining in large corpora.
the inverse problem of linguistics: analysis of large corpora to
mechanically extract the data characterizing a language, both
structurally and to produce extensive lists of constituents, such
as phonemes, vocabulary for various parts of speech (aka
preterminals), prefixes and suffixes, or inflection mechanisms, to
give a few examples.

I am no expert in data mining, and thus do not know whether it
actually raises complexity problems related to the size of the corpora
being processed. In that case, asymptotic complexity would indeed be
an issue. But if it is mostly composed of a large number of small
additive tasks, then it is more doubtful that asymptotic complexity
matters much. However, I would imagine that some data mining
techniques will work with correlations between independent documents,
and that should raise corpus dependent complexity issues.

In the case of the inverse problem of linguistics, the identification
of a language (which, I guess, could be considered a data mining
problem), we are indeed trying to extract information by correlating
all parts of large corpora. Then asymptotic complexity becomes
extremely relevant. I have unfortunately no specific problem in mind,
probably because such systems have a pragmatic aim, and people
developing them will tend to simply avoid any form of higher
complexity, quadratic being probably already beyond the available
resources. But a search of the literature would probably raise some
complexity issues.

Another point is that linguistics does not have clearcut laws like
physics. It is more a matter of being close enough to what might be
considered current linguistic consensus, since no two people speak
exactly the same language. Hence, good approximations are usually
sufficient when the aim is so elusive. The techniques I have seen were
mainly fix-point techniques to identify parameters by iterative
recomputation of some function based on the corpus structure, until
it no longer makes much difference (plus user input to weed out
remaining pathological cases).

Analysing properties of grammars and other formalized linguistic
structures may also be a source of high complexity problems, as
mentioned above for ambiguity, since natural language descriptions are usually large enough for asymptotic analysis to be meaningful.


Multiplication of two or more algebraic quantities Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are

$$x^2-2x+3, \text{and } x-5$$

then the result of multiplication will be

$$x^3-7x^2+13x-15.$$

My question is that how to read the two algebraic quantities, find out the result of multiplication and print the result in c++.
I need hints and is there something to learn to multiply the two or more algebraic quantities by programming. If so,what is that?

Your algebraic quantities are polynomials in one variable. Multiplying two polynomials is an important computational problem with many applications. You can store a polynomial in two ways:

store the coefficients, that is for $p(x)=3x^2-x+3$ you store $(3,-1,3)$
store enough samples, that is for  $p(x)=3x^2-x+3$ you might store three values like $p(0)=3,p(1)=5,p(-1)=7$ (if your highest exponent is $k$ you need $k+1$ samples)

To multiply two polynomials you can do the following. Assume the coefficients of the first polynomial $A(x)$ are named $a_i$ and of the second $B(x)$ they are  named $b_i$, then the coefficients for $A(x)B(x)$ are the coefficients $c_i$ with
$$c_k= \sum_{(i,j)\colon i+j=k} a_ib_j$$

Without tricks this takes $O(n^2)$ time.

Another possibility is to multiply the samples (if they are taken at the same positions). The problem here is, that the product has a higher degree. That means that you need more samples than you needed for the original polynomials. So you had to record more samples in the beginning. What is even more severe is that it is not easy to evaluate the polynomials on arbitrary positions if you only have the samples. So the multiplacation goes fast in $O(n)$ time if you have enough samples, but the evaluation might need $O(n^2)$ time per se.

But here is the thing. You can change from one representation to the other in only $O(n \log n)$ by a famous algorithm called fast Fourier transform (FFT). In a nutshell you pick you sample points very clever and then you divide and conquer. Using FFT you can multiply and evaluate polynomials in time $O(n\log n)$. If you dont care so much about speed, just use the coefficient representation and the formula above.


Need clear explanation to Range updates and Range queries in Binary Indexed trees? I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm unable to understand the need of second tree. In the tutorial http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree :
It says as:

Consider a range update query – Add $\mathrm{val}$ to $[i,\dots,j]$. We will design a sum function, where we consider a summation function for all possible $x$ as following:
$0$  for  $0 \leq x < i$
$\mathrm{val} * (x - (i - 1))$ for  $i \leq x \leq j$
$\mathrm{val} * (j - (i - 1))$ for  $j < x < n$

I just want to know the following things:
If $i\leq x\leq j$, why is the sum $\mathrm{val}*(x-(i-1))$ ?
I'm not able to appreciate the entire algorithm.
Could someone explain me using examples?

Consider an array $A[0, \cdots, n-1]$ and its cumulative sum array $A'$.
Suppose we want to make a range update of $v$ to $A[i, \cdots, j]$. Then $A'$ is changed in the following way:

For $0 \le x < i$: $A'[x]$ does not change;
For $i \le x \le j$: $A'[x]$ is added by $v \ast \left( x-(i-1) \right)$;
For $j < x < n$: $A'[x]$ is added by $v \ast \left( j-(i-1) \right)$.

For your question, why is $v \ast \left( x-(i-1) \right)$?

First, the specification of range update of BIT Range-Update(v,i,j) means adding value $v$ to each element of $A[i, \cdots, j]$.

Secondly, $A'$ stores the cumulative sums of $A$. For $A'[x], i \le x \le j$, its increment consists of the cumulatively added values preceding it, which is, along with $v$ of itself, $v \ast \left( x-(i-1) \right)$. The increment of $A'[x], j < x < n$ is the same as that of $A'[j]$, which is $v \ast \left( j-(i-1) \right)$.

An example from the post you mentioned is as follows (thanks @JS1; the indices starts from 1 for consistency):

Suppose you had an empty array:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

And you wanted to make a range update of +5 to [4..8]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)


Can we detect perfect matchings in P? in NP? in coNP? This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question.
Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.

The class NP is a superset of class P . It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP . To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.

More precisely, if L is a set in P consisting of elements of the form (x, w), then the set
M={x:∃w,|w|≤|x|k and (x,w)∈L},

is in N P .
Let G = (V, E) be a graph. G is said to have perfect matching if there is a subset M of the edges of G so that

No two edges in M intersect (have a vertex in common); and
Every vertex of G has an edge in M.
Let MATCH be the set of all graphs that have a perfect matching. Let ~MATCH be the set of graphs that do not have a perfect matching. Let o(G) be the number of components of G that have an odd number of vertices.

Tutte’s Theorem: G∈MATCH if and only if for all subsets S of V, the number of components in G − S (the graph formed by deleting the vertices in S) with an odd number of vertices is at most |S|. That is,
G∈MATCH↔∀S⊆Vo(G−S)≤|S|.
Which of the following is true?

MATCH∈NP and ~MATCH ∉ NP
~MATCH ∈NP and MATCH ∉ NP
MATCH ∈ NP and ~MATCH ∈NP
MATCH ∉ P and ~MATCH ∉ P
None of the above

How to approach such type of questions ?

Edmonds' "blossom algorithm" determines membership in MATCH deterministically in time $O(|E|\,|V|^2)$.

You answer this kind of question by searching for algorithms that solve your problem as efficiently as possible and, if there don't seem to be any, searching for NP-completeness results. If you don't find either, then you need to come up with your own algorithm or your own hardness proof.


General name for linked lists based on hashes I am thinking of a particular datastructure, but don't know the name of it.

A sequence of elements may be modeled by a collection of some X, where each X consists of:

The element, serialized as a bunch of bytes.
[a] The hash of the previous X  in the sequence, based on the bytes of both parts of that X in a predictable way or [b] some mechanism to denote no such X exists, i.e. that this is the first element.

Given a database that contains (at least) all relevant Xs, and a lookup mechanism by hash, we can take a single X and reconstruct the sequence of elements from it.

What is the general name (if it exists) of this datastructure in the literature? I.e.

What is the general name of X?
What is the general name of a sequence of Xs.

Note that although this looks like (and is inspired by) a blockchain or git commit object, it is more general: any list sequence could be so rewritten.

In comparison with the blockchain / git, the above does not make any statement about distributed databases, timestamps or contents of each element. It also notably differs from git at least in the sense that it is single-parent.

This is known as hash chaining.  The blockchain uses this technique, as do some kinds of timestamping schemes (see, e.g., Haber & Stornetta) and in some cryptographic schemes for append-only audit logs.


Algorithm Selection for Classification problem I've been working on a developing a product selection network for my workplace. I work with lots of chemicals and the clients don't always know what they want/need so most of the time I have to ask a bunch of question, collect useful/ignore useless information, then make a selection from there. Discussions take place over the phone.

Ideal situation In terms of information collection/flow:
1. I ask a probing question which specifies which feature I am referring to
2. Client answering question and speech recogniser converts voice to text filling in feature input.
3. Text summariser searches the feature and reduces down to specific key words.
- For example: Me: "what kind of application are you looking to perform?"
               Client: "I'm wanting to adhere two pieces of wood together"
               Feature summarised to: adhere, wood
4. Once feature vector has enough information the network recommends the most suitable product.

Problems:
1. Clients tend to waffle and give useless information therefore network will need lots of training data.
2. Once a question is asked - client may not directly answer that question and may incidentally answer another feature question.

I would think the logical place to start would be a speech recognition RNN - I have written a weak tensorflow one however I think I'll just look to tap into Google's cloud speech recognition API here. This is where I get stuck - should I just use a simple forward/back propagation network from here and treat it as a classification problem or is there another way to do it?

Any direction pointers would be greatly appreciated.

Kind Regards, Andy

I don't think existing state-of-the-art technology will be adequate to solve this task effectively.  The current state of knowledge in NLP and AI probably isn't good enough to build something that will work well in practice.    Instead, I think you'll need to use humans.  Perhaps you can hire someone and train them -- that will probably be both cheaper and more effective than anything feasible with AI today.

(It seems impractical to obtain the large training sets typically needed for deep learning.  Also, your task requires deep understanding of spoken text at a semantic level, which is currently hard.  Finally, your task requires domain knowledge about the kinds of application tasks that clients are likely to ask about.)


Grammars: is there some connection between non-terminals $S$ and $S'$? Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.?

$$\begin{align*}
    S &\to aBS'\\
    B &\to b\\
    S'&\to bA
\end{align*}$$

$S'$ is just another nonterminal.

The reason $S'$ is used instead of, say, $T$, is that $S$ has been established as standard  for the start symbol of a grammar. Now, if you are talking about an algorithm that transforms a grammar (e.g. into a normal form), you will need to distinguish between the start symbol of the original grammar and that of the transformed grammar. In order to indicate that both are start symbols, it has become the norm to use $S'$ for one of them (usually the latter).


Single big BST vs multiple smaller BSTs? Which is faster for search? Lets say that I am storing 10^9 keys in a single BST.
Compared to having lets say having multiple BSTs of sizes 10^6 containing chunk of the bigger tree? Search through all of them executing in parallel.

I am talking about only search performance here, Given that processing power is not a bottle neck.

Searching among $N$ in a BST takes (roughly) $\log_2 N$ comparisons. So searching in $10^9 \approx 2^{30}$ takes around 30 comparisons. Searching in $10^6 \approx 2^{20}$ takes 20 comparisons. The cost of farming out the work to 1000 processors, collecting the results and figuring out the answer is surely costlier than 10 comparisons.


Is z-buffering the same as rasterization? I understand z-buffering as being "object-first" in contrast to "pixel-first" since the for loop starts with checking each triangle in the scene rather than each pixel. However, is this the same as rasterization,  or is rasterization just a general technique that encompasses z-buffering?

Z-buffering is easy to implement depth-buffering, where you check whether pixel is visible or not (in case of transparency, it is handled separately). This is optimisation to avoid calculating color at every pixel but instead check which are nearest to the screen, paying with memory.
Rasterization is general technique converting vector graphics into rasters, including filling triangle with pixels. Different technique is to use raytracing or photon mapping, in that case triangles are not rasterized (as in scanline rasterization) but rays (photons) are cast and traced.

So, yes, z-buffering is part of realisation of rasterization.


Real world applications of first order logic I study an AI course and we done some lectures about first order logic and the first thing that I was thinking is, what are the real world applications of first order logic and generally logical languages , especially in AI ?

If you want a specific example, IBM Watson should qualify. Check the links for details on how they use Prolog. I'd say that Prolog made a huge hype in its day, and most real today's system are based on different principles rather than "first-order logic programming" in narrow sense. However, there is definitely a niche for this approach. We live in the age of other hypes, that's it.


Serializability and the Lost Update Problem Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent states, and a concurrent execution of T1 and T2 is equivalent to a serial execution of T1 and T2, then that concurrent execution results in a consistent state, after committing both transactions.

For example, the following concurrent execution (time advances to the right)

T1: w(a=1)         w(c=4)
T2:     w(a=2)w(b=3)

where W(x=v) sets (i.e., writes) x to the value v, is equivalent to the serial execution T1;T2, thus it is serializable and both transactions are committed.

However, it is clear that T2's write of a causes T1's write of a to be lost, i.e., we have a lost update despite serializability.

That is, serializability ensures consistent states in face of concurrency, though it does not prevent lost updates, which may have serious consequences (for example, imagine that T1 writes the correct delivery address of a VIP customer, and T2 writes the wrong address, T1 and T2 are run concurrently by different operators, who do not notice the mistake).

Is my statement correct about serializability and lost updates?

If it is correct then the table in "Isolation levels, read phenomena, and locks" in this wiki page can only be wrong with regard to serializability and lost updates.

If so, what other stronger consistency level ensures that there are no lost updates?

Thanks

You say:

  serializability ensures consistent states in face of concurrency, though it does not prevent lost updates

This is not true, since by definition the lost update is the phenomenon arising in presence of Write-write conflict, that is when a transaction B overwrites a value written by a transaction A before the commit of A. This operation can lead to a state which cannot arise from any serial execution of A and B.

Consider for instance, in your example, the case in which the transaction T2 is executed one hour after the transaction T1: this could happen in real life, the execution of the two transactions is serial, that is there is no interference between the two transactions, however the update is wrong since someone wrote a bad address. But this means bad data, not data base inconsistency in itself (in other words, you have a database inconsistent with the reality, but this has nothing to do with concurrency and transaction management, that are properties related to the execution of concurrent operations over the database).


Dijkstra's algorithm - Finding additional paths with same weight but different edges given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a_1,a_2,...,a_k)$

assume that between the nodes s and t, there's an at least additional path with the same weight, but with different edges(meaning both paths have different edges, nothing in common). how can we find that additional path?

My attempt: let's create an array that holds the parent. that array will be separate, so the value of $parent[v_i]$ for some vertex $v_i \in V$ stores the parent of $v_i$ in the array, in the shortest path tree that is formed by the algorithm. now, we'll initiate the first element, meaning the parent of the root to be -1, and if we find shorter path through some vertex u, we can make u the parent of the current vertex. but i am not sure it solves the problem unfortunately.

would really appreciate if you could explain what you do so i can understand it.

tried to do a research on the site, but couldn't find a similar problem with no same edges and i don't know how to solve it, so i am asking for help here

thank you very much

One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$).

So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the queue you explored all the nodes $v_j$ reached from $v_i$, in the standard version of the algorithm, there was 2 cases:

a smallest path to $v_j$ has been found: $d[v_j]$ and $parents[v_j]$ are updated and $v_j$ is added to the queue.
the new path is not better, do nothing.

So now, if the path is smallest, $parents[v_j]$ is replaced by the list with one element $[v_i]$.

And there is an additional case: if path to $v_j$ is exactly the same in distance, append $v_i$ to $parents[v_j]$. Note that there is no need to put $v_j$ again in the queue.

Once you reach $t$ and you backtrack path using $parents[v_i]$, if there are several elements in the list, any may be picked and lead to a different shortest path.

Note that $parents[v_i]$ is $O(N^2)$ in space. The worst cases are very dense graphs,  and this would mean that there is a large number of shortest paths. In this case, other method to store $parents[v_i]$ may be more adapted.


Kraft's inequality and Shannon's noiseless coding theorem for an encoding A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley.

Does there exist a compact instantaneous binary encoding for this source with word lengths $2, 2, 4, 4, 5$ and $5$?

Shannon's Noiseless coding theroem that says a compact encoding has expected wordlength $n$ where $n\leq \frac{H(W)}{\log_2(D)}$.
I get $H(W)=2.328$ and $n=1.901$, but in this case the expected word length is $3.67$ so it cannont be a compact encoding.

I feel like I have gone wrong here, could somebody tell me how? Because I have gone on to the next question where I perform Huffman coding to achieve a compact instantaneous encoding however the word length for this encoding is still higher than $1.901$ so fee like I must have my value for $n$ wrong but can't see how?

I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a compact prefix code, since $1/4+1/4+1/16+1/16+1/32+1/32 < 1$.

Shannon's noiseless coding theorem states that when optimally encoding large blocks, in the limit the average encoding size per data item is the entropy. You can prove the upper bound part of the theorem using Huffman coding applied to large blocks. Huffman coding produces a code whose average bit length is at most $H(X)+1$, where $X$ is the source. If you use Huffman coding on blocks of size $n$, the average bit length per data item becomes $H(X)+1/n$ (why?), and by letting $n\to\infty$, you can get as close to the entropy as you want.


Representation of unsigned integer on a little endian, big endian computer This is a GATE 2021 exam question.

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?
A. 0x6665
B. 0×0001
C. 0×4243
D. 0×0100

According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.
My logic for answer being A,D :
The question is asking “which of the following choices represent(s) the unsigned integer on a little endian computer?”
Take Option “0x6665” :
The question is saying that 0x6665 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x6566.
So, for the original number 0x6566 :
On little endian(LE) : 0x6665
On Big endian(BE) : 0x6566
Clearly, LE = 255 + BE
Similarly, for 0x0100.
Take 0x0100 :
He is saying that 0x0100 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x0001.
So, for the number 0x0001 :
On little endian(LE) : 0x0100
On Big endian(BE) : 0x0001
Clearly, LE = 255 + BE
Similarly for 0x4243 and 0x0001, They do not satisfy “LE = 255 + BE” condition , So, answer should be option A,D.
For Reference, Refer Slide 26 in the below article :
https://www.cs.utexas.edu/~byoung/cs429/slides2-bits-bytes.pdf

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer

According to the dictionary, the definition of "numerical value" is "a real number regardless of its sign", in other words absolute value. Since the integer is unsigned, its numerical value is itself, and that will not change no matter how the integer is stored, little or big endian style, written on a napkin with lipstick in base seven, notches on a bedpost, or whatever. Therefore, the first line of the question is meaningless, which is always a nice start.
Additionally, the question confuses memory representation and integers. Two bytes in memory that look like (0x00,0x01) represent the integer 0x0100 in little-endian mode, but you can't say "let's add 255 to (0x00,0x01)" because (0x00,0x01) is not the number 0x0001 although it looks like it.
A correctly worded question would be:
"There are two bytes in memory. A big-endian cpu reads them with a uint16 load instruction and gets an uint16 value. A little-endian cpu reads the same two bytes and gets an uint16 value that is 255 higher than the big-endian cpu's value. What are the two bytes in memory?"
(One could also ask what uint16 one of the cpus gets)
Then it's pretty simple:
Memory    uint16     uint16
dump      read by LE read by BE
0x66 65   0x6566     0x6665
0x65 66   0x6665     0x6566    correct
0×00 01   0x0100     0x0001    correct
0×01 00   0x0001     0x0100
0×42 43   0x4342     0x4243    correct
0×43 42   0x4243     0x4342

According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.

Having nuked the question, let's play jeopardy and try to figure out what question you and your colleagues are answering.
Basically, to misquote a famous crook, you're having a disagreement over what the word "represents" represents. One thinks it is the memory representation in little-endian (although it is written wrong in the question, and honestly if the word "memory" was mentioned it wouldn't hurt for ease of comprehension) and the other thinks it's the integer itself (probably because the 0x values are written as integers not bytes). So you're both picking from a different column of my table above.
We will have to wait for the end of the war between little endians and big endians to know what the peace treaty says about who's right.
Another way to not fix the question would be: If the memory representation of a 2-byte unsigned integer on a little endian computer looks like it is 255 more than that on a big endian computer to a human reading the memory bytes in big endian order, which of the following choices represent(s) the unsigned integer?
However, this reveals to all the rampant systemic endianness supremacy asserting that humans of the wrong endianness are lower-class citizens. This implicit endianness bias and oppression must stop! As of today, the DIE commitee dictates that everyone will switch to the more inclusive and safe middle-endianness, and both-endians colonizers will be sentenced to pay reparations to native middle-endians.


Can not follow the example for max-flow-min-cut on Wikipedia This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut theorem.

Max flow isn't 9 it is 7. 4 from s to 1 and 3 from s to 2.It cannot have more than that.You can see that it is also equal to min-cut.


If-Then with disjunctions (OR) in Integer Linear Programming (ILP) I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.

Given the integer variables: x1, x2, x3, x4, y1, y2, y3, y4, I have the following constraints:

IF (y1 ≤ y3 ≤ y2  OR  y1 ≤ y4 ≤ y2)
THEN (x1 ≥ x4  OR  x2 ≥ x3)

Additionally for all of these variables I have upper and lower bounds.

I think I have to use the "big M" technique, but I'm not sure how to handle the logical OR in the IF condition and in the THEN condition and how to built up one complete model.

Does anyone of you know how to resolve this?
Many thanks in advance.

You have the following condition:

IF ((y1 <= y3) AND (y3 <= y2)) OR ((y1 <= y4) AND (y4 <= y2))
THEN (x1 >= x4) OR (x2 >= x3)

For each logical term, you'll need a new binary variable. At each "level" of the logical statements, you'll use the binary variables from the previous level. So:

z1 = 1 iff y1 <= y3
z2 = 1 iff y3 <= y2
z3 = 1 iff z1 = 1 AND z2 = 1
z4 = 1 iff y1 <= y4
z5 = 1 iff y4 <= y2
z6 = 1 iff z3 = 1 AND z4 = 1
z7 = 1 iff x1 >= x4
z8 = 1 iff x2 >= x3

Then you'll have a constraint that says:

if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1

Let's take one type of constraint at a time.

z1 = 1 iff y1 <= y3:

y3 - y1 + 1 <= Mz1
y1 - y3 <= M(1 - z1)

The logic is: If y3 > y1 - 1, i.e., y3 >= y1, then z1 must equal 1. If y1 > y3 + 1, i.e., y1 > y3, then z1 must equal 0.

Note that if the y variables are continuous, not integer, then replace the 1s with some small number. This isn't ideal from a numerical perspective though.

Constraints 2, 4, 5, 7, and 8 are similar.

z3 = 1 iff z1 = 1 AND z2 = 1:

z1 + z2 <= 2z3
z3 <= z1
z3 <= z2

The logic is: If z1 and z2 both equal 1, then z3 must equal 1. If either of them equals 0, then z3 must equal 0.

Constraint 6 is similar.

if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1:

z3 + z6 <= 2(z7 + z8)

The logic is: If z3 = 1 or z6 = 1, then z7 or z8 must equal 1.


Sizing a Cuckoo filter for a subset of elements Question

I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs:

There are over $n = 30 000$ first names that exists in the whole world
I have a Cuckoo filter storing the names of people who gave me a gift at least once
I am certain that the Cuckoo filter will not have to store more than 600 names
The names the Cuckoo filter will store are evenly distributed across the 30 000 names
Of course the final goal is to be able to know which names gave me a gift at least once, I might have to query for any of the 30 000 names.

I would like to design my filter for 600 elements; however the original paper about Cuckoo filters considers that the number of buckets $m$ is a multiple of $n$.

  Now consider a construction process that inserts $n$ random items to an empty table of $m=cn$ buckets for a constant $c$

Am I supposed to size the filter according to set of all names in the world ? Is there something I am missing ? This is not addressed in the original publication.

Constraints

Size : The Cuckoo filter will be transmitted over the network. But it will be done in an asynchronous way (let's say an update every 2 hours). So this will weigh in the size constraint.

Time : The real constraint is time. When I query the filter I would like my response in less than 5 seconds.

False positive : I also hope to have false positive rate of at most 20%.

Security : In my example I store names, but in reality I will store sensitive data that should be protected and anonymized under GDPR. After a statistical analysis I concluded that the data's entropy is too low to store as a list of hashes.

Other options : I'm open minded by nature. I always welcome other options.

Attempt at a self answer

Considering that the fingerprint is $f$ bits long, and I have $m$ buckets, the probability that the name Bob has the same features (index and fingerprint) as the name Alice is :

$$
\frac{1}{2^f} \cdot \frac{1}{m}
$$

Which means that the probability that there is another name colliding with the name  Anna is:

$$
(n - 1) \cdot \frac{1}{2^f} \cdot \frac{1}{m}
$$

With 30 000 names, a fingerprint of 8 bits and 600 buckets, the result is $0.39$ which means a false positive rate of 39 %.

To reduce the false positive rate I can either increase the fingerprint size or the number of buckets. Using 6000 buckets instead of 600 gives me a false positive rate of 3.9%. This hack might be working in my example case but in reality we are talking of $10^{19}$ names in the whole world and $10000$ names to store in the filter.

It seems to me that Cuckoo filter were not designed with this use case in mind, and when people are using Cuckoo filter, they hope to store almost every existing item in there at some point.

As discussed in the comments it turns out that, yes, I need to size my Cuckoo filter for the set of every existing name. That being said, it is not much of a problem in the end if I only send the buckets with fingerprints in it, which shouldn't be more than 600.

In addition to that, my attempt at a self answer was very wrong. The probability that there is another name colliding with the name Anna is actually:

$$P\left(\bigcup_{i = 1}^n A_i\right) =  \sum_{k = 1}^n (-1)^{k+1} \sum_{1 \le i \lt j ... \lt k \le n} P(A_i \cap A_j ... \cap A_k)$$

This is the inclusion-exclusion principle. Because of my hypotheses, the probability can be simplified as:

$$P\left(\bigcup_{i = 1}^n A_i\right) =  1 - (1 - p)^n$$

As highlighted in the original paper, we also have to take into account that $$2b/2^f \le \epsilon$$.


Evolving artificial neural networks for solving NP problems I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

  One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight Evolving artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).

No. This direction is unlikely to be useful, for two reasons:

Most computer scientists believe that P $\ne$ NP.  Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem.  If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm.  It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.
Neural networks aren't "magic".  They are a way of trying to find patterns.  For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective.  But they're not magic fairy dust.  Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem.  It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning.  We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning.  Neural networks aren't some kind of magical silver bullet that solve all machine learning problems.  They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something).  But don't be fooled.  Don't believe the hype.  Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers.  Not anytime soon, anyway.  That's just science fiction.


Finding the base case for T(n) = T(n - a) + T(a) + cn I was solving the recurrence using Recursion tree method:
$$ T(n) = T(n - a) + T(a) + cn$$
When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the form of:
$$h*ca$$
But I could not figure out on how to solve the base case.
I know that $T(n-a)$ would be at base case when $n=a$.
But how to compute the height $h$ of the recurrence.
I know the base case can be defined as:
$$n-ia=0$$
I have seen the previous examples in the book Introduction to Algorithms which quotes:

The subproblem size for a node at depth $i$ is $n/4^i$ . Thus, the
subproblem size hits $n=1$ when $n/4^i=1$ or, equivalently, when $i = \log_4 n$

For the recurrence: $T(n)= 3T(n/4)+ cn^2$
So, coming to the point what would be the base case such that the sub-problem size hits $n= ?$ like in the above example.
Would it be $n=a$?
Please correct me if I am wrong.
Thank you.

Every $0\le k\le a$ yields the base case $T(k)$.
If you are trying to solve the big-O of the recurrence, then you may as well assume that there is some $c$ where $T(k)\le c$ for every base case $k$. It will help making the computation a bit easier


Correctness of lower bound proof I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.

  Given a sorted array $A$ (of $n$ distinct elements) and three elements $x$, $y$, and $z$, where $x < y < z$. The problem is to determine whether $x$, $y$, and $z$ are in $A$ or not. Prove that any comparison-based algorithm for this problem needs at least $3\log n-c$ comparisons in the worst case, where $c > 0$ is some constant.

My current proof using a decision tree goes as follows:
A comparison based algorithm must have at least 2 outcomes per a single comparison. For example: >= or <. It can also have 3 outcomes: < or = or >. But it has to have at least two.

When trying to decide whether an element is in the array or not it could be equal to any of the $n$ elements or it might not be in the array. Thus we have $n+1$ leaves in the decision tree.

Because of this the height of the decision tree is at least $\log_2(n+1)$. This is a lower bound for deciding whether one element is in the array or not. If we want to decide if the 3 elements $x, y, z$ are in the array or not and we know that $x< y< z$ we can use this information to speed up the search by searching for $y$ first.

For example if the outcome of the first comparison is < then since we know that $x < y$ we can skip that comparison when searching for $x$ and save at least a step. Similarly, if the outcome of the first comparison is > then since we know $y < z$ we don’t have to redo that comparison when searching for $z$ and save at least one step.

So if the search for $y$ starts with some constant $c$ left-branches we save that many steps when searching for $x$ and if the search for $y$ starts with $c$ right-branches we save that many steps when searching for $z$.

Thus, if it takes $k$ steps in the worst case to search for the 3 elements a lower bound is:
$$ k \ge 3\log_2(n+1)-c \ge 3\log_2 n-c, $$
where $c$ is some positive constant.

Is this a correct proof? What I am unsure about is if the last statement is ok, where I just discard the "+1". And whether this holds true for "any comparison based algorithm". Any critique or suggestions are greatly appreciated.

The following answer works for a previous variant of the question, in which the goal is to determine which of $x,y,z$ are in $A$. It might be possible to adapt it to the current version, in which the goal is to determine whether or not all of $x,y,z$ are in $A$. One difficulty is that the number of trees of depth $h$ is now $\Theta(2^hh^3)$, so following the same steps would only give a lower bound of $3\log_2 n - \Theta(\log \log n)$.

Suppose that the array $A$ is $1,\ldots,n$. Let $x = i + 1/2$, $y = j + 1/2$, $z = k + 1/2$, where $1 \leq i < j < k < n$ are integers. Let us denote the resulting leaf of the algorithm by $\ell(i,j,k)$.

I claim that if $(i,j,k) \neq (i',j',k')$ then $\ell(i,j,k) \neq \ell(i',j',k')$. Indeed, suppose that $\ell(i,j,k) = \ell(i',j',k')$ although $(i,j,k) \neq (i',j',k')$. Suppose that $i < i'$ (the other cases are similar). Since $i + 1/2 < A_{i+1} < i' + 1/2$, we conclude that in this computation path, the algorithm never compares $x$ to $A_{i+1}$. Suppose that we change $A_{i+1}$ to $A'_{i+1} = i + 1/2$. The new array $A'$ is still sorted, and when running the algorithm on $A',i+1/2,j+1/2,k+1/2$, it still reaches the leaf $\ell(i,j,k)$ (since the only comparison whose answer is different is $A'_{i+1}$ and $x$). We have reached a contradiction, since $x \in A'$, and so we should have reached a different leaf.

Concluding, we have shown that the algorithm tree must have at least $\binom{n-1}{3}$ different leaves (this is the number of possible triples $(i,j,k)$). Since we are only considering runs of the algorithm in which the answers to all comparison queries are either $<$ or $>$, we can ignore all edges labeled $=$, and so we are left with a binary tree, whose depth must therefore be at least $\log_2 \binom{n-1}{3}$. This is a lower bound on the number of comparisons in the worst case.

When $n \geq 4$, we have
$$
\binom{n-1}{3} = \frac{(n-1)(n-2)(n-3)}{6} \geq \frac{(n-3)^6}{6} \geq \frac{(n/4)^3}{6} = \frac{n^3}{384},
$$
since $n-3 \geq n/4$. Therefore for $n \geq 4$ the number of comparisons must be at least
$$
\log_2 \frac{n^3}{384} = 3\log_2 n - \log_2 384.
$$
When $1 \leq n \leq 3$, we must still make (say) at least one comparison, and this allows us to obtain a lower bound of $3\log_2 n - c$ valid for all $n \geq 1$ (details left to the reader).


Graph theory : Trees I need to determine all the trees on 25 vertices for which there exists an integer m ≥ 2, such
that the degree of each vertex gives the same remainder when divided by m.

Can somebody help ?

Suppose $G = (V, E)$ is a tree with 25 vertices such that there exist some constants $c \geq 0$ and $m \geq 2$ such that $\operatorname{deg} v \equiv_m c$ for all $v$. Note that we can equivalently write $\operatorname{deg} v = a_v m + c$ for some $a_v \geq 0$.

Since $G$ is connected by definition, we get that it must have 24 edges in total, giving us
$$ \sum_{v \in V} \operatorname{deg} v = 2 \cdot |E| = 48.$$
We can express this sum using the aforementioned decomposition of the degrees in $G$ to get
$$
\begin{align*}
 \sum_{v \in V} \operatorname{deg} v
 &= \sum_{v \in V} a_v m + c \\
 &= c |V| + m \sum_{v \in V} a_v \\
 &= 48.
\end{align*}
$$
Due to the both terms in the rewritten sum being non-negative, we get that $c$ must be 1 if we are to find any solutions.
Hence we get that $m$ must divide $48 - c|V| = 23$, which implies $m = 23$ as we required $m \geq 2$.

At this point, we know that any such $G$ satisfying your conditions does so with $c = 1$ and $m = 23$.
By using our new formula again, we find that the sum of our $a_v$ must also equal 1 and therefore, $G$ must be isomorphic to a tree with 1 internal node and 24 leaves, which is also known as the star graph $S_{24}$.


Finding pairs of numbers in array whose reciprocals sum to 1 Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b < 1$.

For example:

Input: $2, 3, 1, 0.5, 3, 1.6$.
Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$.

We can compare each element with each other but it takes $O(n^2)$ complexity. How to  improve that algorithm? Maybe use special structure? Maybe use sorting?

Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) :

$$b > \frac{a}{a - 1}$$

Notice, if the array is sorted, then you can find the number of valid $b$ using binary search, which gives $O(n \log n)$ to compute the number of all pairs.

Also notice, that if $a$ gets bigger, then $b$ is allowed to be smaller. So if you you iterate over $a$ in sorted order, and keep a pointer (to indicate the allowed elements for $b$), you don't need to use binary search and can compute the result in $O(n)$.


Confused by Floating Point Spacing I'm currently taking a numerical analysis class in college and we're covering floating point systems. For the most part, I have a good grasp on it. However, something I can't seem to visualize, and haven't seen any totally lucid explanations about after searching extensively, is spacing between floating point numbers. Also of note is that I'm talking about IEEE-754 here, but it applies to general systems too.
The Things I Do Understand:

The area between $[-1,1]$ is a denormalized area.
The areas after $1$ and less than $-1$ are where the normalized floating point numbers reside.
The floating point numbers between perfect powers of the base are uniformly spaced, but the spacing varies from one perfect power of the base to another.
The spacing between values between two perfect powers is proportional to the power on the left for positive numbers and the power on the right for negative numbers. (i.e. on a number line, the uniformly-spaced values between two low powers are closer together than between a higher power.)

What I'm Struggling to Understand

From my understanding, the machine epsilon $\epsilon$ is a fundamental unit of spacing with respect to the floating point number line. That is, between $[1,B]$ where $B$ is the base, all values are $\epsilon$ apart. Then, you can scale any arbitrary floating point number by that fundamental machine epsilon and that product is the uniform spacing for that floating point number's associated power range. Is this even a correct interpretation?
I also read that $\epsilon$ is an upper bound for relative error, so I'm not really sure how that fits into my explanation of it being an indivisible spacing unit.

One of the questions I haven't been able to answer is what the minimum and maximum spacing between two positive floating point numbers is. I can trick myself into thinking I understand why multiplying the x's associated $B^e \cdot \epsilon$, where x is an arbitrary floating point number and $e$ is that number's corresponding exponent, yields the upper bound on error and therefore spacing, so $B^e \cdot \epsilon$ would be the maximum spacing.
Minimum spacing truly boggles my mind right now, though. If the machine epsilon is the indivisible unit of spacing, then for example, how could we have more minimal spacing than between $1$ and $1 + \epsilon$? Wouldn't that just be left to the rounding rule used (if round-to-nearest, it would depend whether the number is closer to $1$ or $1 + \epsilon$, since it'll be rounded to one of those two).

Basically, if you could explain this in plain-english it would really help me get a solid understanding of what's going on at the number line level.

This is best explained in the base 10 equivalent: scientific notation

In scientific notation you have a mantissa and a exponent such that the value is $\mathrm{mantissa} \cdot 10^{\mathrm{exponent}}$.

In a computer floating point the mantissa is always the same size of significant digits (a double precision has around 16 digits) and the exponent is bounded.

Let's take a arbitrary format for our examples: a 4 digit mantissa and a 1 digit exponent

1 is then represented by $1.000 \cdot 10 ^ 0$
the maximum value you can represent is $9.999 \cdot 10 ^ 9$
the minimum absolute value you can represent in a normalized fashion (first digit is not 0) is $1.000 \cdot 10 ^ {-9}$
$2\,147\,483\,648$ is most closely represented by $2.147 \cdot 10 ^ 9$ (note that this is actually $2\,147\,000\,000$)

Here you'll see that to represent that large number there is an absolute error of $483\,648$ or a relative error of $0.0002$.

A denormalized value would be when the first digit is 0 like with $0.001 \cdot 10 ^ {-9}$, here it isn't that significant but in binary the first digit of the mantissa is assumed to be $1$. So that first bullet point is false, denormalised is all values in $(0,B^{\mathrm{minExp}}) $and $(-B^{\mathrm{minExp}},0)$.

Our machine epsilon here is $0.001$ (going from 1 to the next representable value 1.001).

So for numbers with exponent $0$ there is an accuracy of $0.001$, while for numbers with exponent 5 there is a accuracy of $100$.


Sort array with minimum swaps Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized.

I was thinking of first determining whether it is increasing type or decreasing type i.e. the type in which least swaps would be required and then sort my array in increasing or decreasing order accordingly. I don't know how to implement in determining the type. Can someone help me in finding heuristic or algorithm to do so ?

Also if the array is 2-Dimensional, would the idea still work or will I use less swaps if I change elements between rows instead of within the row itself. And if it has to be inter-row, how would I go about for that such that all rows are sorted (a row can be either increasing or decreasing) ?

Let $A$ be the array; by hypothesis there exists a unique permutation $\pi : A \rightarrow A$ such that $\pi(A)$ is sorted. The minimum number of swaps required to sort $A$ is the minimum $h$ such that there exists a decomposition of $\pi$ in $h$ transpositions.

Certainly $\pi$ can be broken down in at most $n-k$ transpositions where $k$ is the number of cycles in the unique cycle decomposition of $\pi$: it is sufficient to observe that a cycle $(c_1, c_2, \dots, c_l)$ can be rewritten as $(c_1, c_l)(c_1, c_{l-1})\dots(c_1, c_2)$.

It can also be shown that $n-k$ is the minimum, the proof isn't straightforward but it's a known result that you can easily find in literature should you be interested.

As for your multi-dimensional case, the same idea should work, but you should be more specific about what you mean for a multi-dimensional array to be sorted.


Data structures for annotations in large-scale text editor I need to create a specialized text editor capable of handling text up to billions of characters long, with no line breaks.

I've read of multiple data structures to manage the text itself, including ropes, zippers, piece tables, gap buffers, and more.

However, I also need to support annotations on the text. Like comments in MS Word, each annotation lies over a range of positions. (Unlike MS Word comments, each annotation may lie over multiple non-intersecting ranges.)

Annotations can cover a single character or the whole text. Annotations may be created before, in between, or after text edits.

There can be tens to hundreds of thousands of annotations. Reacting to each edit by adjusting the coordinates of every single feature would incur a large, linear cost.

What are data structures that would support the following, even as coordinates change due to text editing, whose complexity does not include the number of annotations as a factor?

Finding the coordinates of features discovered by text search, in the current coordinate system resulting from text edits made after the annotations.
Finding annotations that intersect a range presented to the user, in the current coordinate system resulting from text edits made after the annotations.

For 1, one idea I've had is to store a history of coordinate-system changes, and apply all of those made after the feature's creation. However, the cost of this grows linearly with the number of edits.

For 2, one idea I've had is to create a custom R-tree of annotations which reacts to text edits by modifying its own coordinate system but not its clustering. But not sure how to handle new features, which don't necessarily lie anywhere in the original coordinate system. And again, the cost of this could grow linearly with the number of edits.

There are many possible data structures you could use.  I will list one.

Augmented balanced binary tree

Stores the string in a balanced binary tree.  Each leaf of the tree holds one character of the document, and you store them in a balanced binary tree data structure: e.g., a red-black tree or AVL tree.  In other words, you think of the tree as representing a map $i \mapsto S[i]$ that maps from an index $i$ to the $i$th character in the document.

This data structure will avoid the need to update the coordinate system by the simple expedient of not using any coordinate system at all.  No indices or offsets are used explicitly.  Instead, everything is represented implicitly in the shape of the tree.

Note that each internal node of the tree implicitly corresponds to a substring of the tree: namely, it is the substring obtained by concatenating all leaves that are descendants of that node.  Equivalently, it corresponds to an interval of indices: namely, the interval $[\ell,r]$ where $\ell$ is the index of the leftmost leaf under that internal node and $r$ is the index of the rightmost leaf under that node.

Also any substring of the document can be expressed into a disjoint union of $\le \lg n$ substrings obtained in this way.  Thus, if $T$ is a substring of the document, it can be viewed as corresponding to a set of $\le \lg n$ internal nodes of the tree (so that concatenating all of the leaves under those nodes yields exactly $T$).

Now you have a list of annotation objects, one per annotation.  The annotation object stores the set of internal nodes that correspond to the substring it is attached to.  Also, each internal node in the tree has a list of backpointers to annotation objects that it is associated with.

Now to attach an annotation to some substring $T$, you simply find the corresponding set of internal nodes, create an annotation object, and add backpointers to that object from each of those internal nodes.  This can be done in $O(\lg n)$ time.

Similarly, to delete or insert into the document, you insert or delete into the balanced binary tree data structure.  You can quickly identify which annotations this affects, by looking at the range of leaves affected, finding a list of $\le lg n$ internal nodes whose disjoint union is exactly that range, and following the backpointers in those nodes and all of their descendants.  Then you can update those annotation objects if needed.  Insertion and deletion doesn't disturb any of the annotations on the rest of the document, so there is no need to update any coordinate system.

What if you want to do random-access into the middle of document, i.e., given an index $i$, you want to quickly find the $i$th character in the document?  You can augment the data structure to make this efficient, by storing in each node the number of leaves it has under it.  If you insert or delete something somewhere in the document, then you update one or more leaves and all of the nodes on the path from those leaves to the root.

In this way, all operations can be performed in basically $O(\log n)$ time.


Are there sorting algorithms that take advantage of a metric space? We know comparison sorting algorithms use the ternary information (lt, eq, gt) garnered from a single comparison to make decisions about what to do next. Is there any research into using a metric? That is, if we compare $x$ and $y$ and we not only know that $y > x$ but we also know the value $y - x$. Presumably if $y - x$ were a very large number we could heuristically separate them from each other, or move $y$ closer to end of the array, or move $x$ closer to the beginning. Could you make fewer than $O(n \lg n)$ comparisons in this way?

This is not a very precise idea (and credit goes to my friend Ian who brought it up out of the blue one day), but I Googled around for a little bit and I was unable to find anything to help me narrow the question.

For the searching problem (rather than sorting), your idea sounds like interpolation search.  Binary search uses only the binary result of the comparison (less than or not), and runs in $O(\lg n)$ time.  Interpolation search also uses information about how close the values were, and heuristically runs in $O(\lg \lg n)$ time in the average case.  Thus, that's an example where using the extra information can speed up search (at least heuristically).


Showing that A' is a regular language Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language.
Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and removing its first 2 characters. Show that $A'$ is regular.

My solution so far is:

$ab \in \Sigma^*$ which is regular.
$A$ is a regular language
$abu ∈ A$, this means $u$ must be regular for all $abu \in A$ so $A'$ is regular.

Not sure if this makes sense, but please let me know if there's a better way, more formal.

Note: It's not an assignment, I'm just studying for my exam.

A word cannot be regular, only a language can be regular. So it's not clear what you mean by "$ab \in \Sigma^*$ which is regular", and even less what you mean by "$u$ must be regular for all $abu \in A$".

Given a DFA (or an NFA) $M$ for $A$, you can construct an NFA $M'$ for $A'$ as follows. Let $T$ be the set of states in which $M$ finds itself after reading some $ab \in \Sigma^*$ (so $1 \leq |T| \leq |\Sigma|^2$), in symbols $$T = \{ q(\sigma,ab) \mid a,b \in \Sigma \},$$ where $\sigma$ is the starting state of $M$ and $q$ is its transition function. Add to $M$ a new starting state $s$, and connect it to all sets in $T$ using $\epsilon$ productions. Hopefully you can see why the resulting automaton $M'$ accepts $A'$.

Here is a more difficult exercise for you to try. Show that if $A$ is regular then $\{u \mid abu \in A\text{ for a }\textit{unique}\text{ pair }a,b \in \Sigma\}$ is also regular.


Model for formula $\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)$ I am new to LTL and I am trying to understand how it works. My question is: is there such $\sigma$ that:

$ \sigma \models [\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)]$

I know that:

$\sigma \models \Box \psi: \forall k \, [(\sigma, k) \models \psi] \\
\sigma \models [\psi \Rightarrow \phi]: (\sigma \models \neg \psi) \vee (\sigma \models \phi) \\
\sigma \models \Box \psi \iff \sigma \models \neg\Diamond \neg \psi$

So

$\sigma \models [\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)] \iff \\(\sigma \models \Diamond (\neg\psi \land \neg\phi)) \vee [(\sigma \models (\Box \psi)) \vee (\sigma \models (\Box \phi))]$

I would say there is such $\sigma$ since I don't see any contrarguments but I'm not sure if I can say anything about $\psi$ or $\phi$ except that both are formulas (so I don't know how to show any specific example).

If you're just asking for any model satisfying the formula, you simply try to make one of these the case

The left hand side false
The right hand side true

Let's just pick number 2.  You have to make a model (with a state $\sigma$) where $\Box \psi \lor \Box \phi$ is the case.  Even easier is $\Box \phi$.

Create a (trivial) model where every state $\sigma$ has $\sigma \models p$ for all propositions $p$.

If you want to see if the formula is valid then the answer is no.  You should now be able to create a model that falsifies the formula.


Why aren't Grobner bases more common? I have only heard of / seen Grobner bases in passing, but my understanding is that they are much like vector bases but for polynomials instead of linear systems. I know polynomials are used in CAD and graphics at the very least. Is there any particular reason why I haven't seen Grobner bases in application? I'm trying to determine whether they are worth the time to learn for my own work.
Edit: I should probably have specified that my use for them would be in solving algebraic systems. I'm mainly wondering how they compare to numerical solution techniques such as Newton's method, and other more linearization/derivative based methods. I'm an interested in any use case, but especially in this one.

Well, I don't know what you expect to get as an answer, but in the comments you already got that if you haven't seen them used is due to two reasons.

The main one is probably that maybe you haven't had the need to solve problems in which they are needed, yet, and
that the problems, like finding a solution of a system of polynomial equations. are more efficiently done by algorithms that target exactly that problem, like Newton's method. Groebner bases can end up with large degrees for systems with relatively few variables and degrees larger than one.

The usefulness of Groebner bases becomes clear once you study what they are. They are  a form in which to put a system of equations. The form is canonical once you fix a way to order monomials in several variables. If you have seen some commutative algebra, Groebner bases are a canonical set of generators of ideals in a polynomial ring $I\subset R=K[x_1,x_2,\ldots,x_n]$.
When you choose a convenient monomial order it happens that the form has the same property as the row echelon form for linear system of equations, that the equations have less and less variables until eventually (for a system that has finitely many solutions) the last equation is a polynomial in one variables. So, incidentally you get out of it a method to find all solutions by backward substitution. You find all solutions of this polynomial in one variable, by either Newton's method, or perhaps some method that finds them all roots at once. This gives you the possible values of one of the variables. Then you substitute these values in the previous equations and repeat the process with them. See here for one way to do these steps.
Example: For the system $$\begin{align}x^2+y^2-1&=0\\xy-4&=0\end{align}$$
you get $$\begin{align}4x+y^3-y&=0\\y^4-y^2+16&=0\end{align}$$
Try it with Singular, by inputting
// Define the ring R[x,y] of polynomials in variables x,y;
// and lexicographical ordering to order monomials.;
ring r = 0,(x,y),lp;
// The ideal generated by those two polynomials. ;
ideal I =(x^2+y^2-1,x*y-4);
// The same ideal, but now generated by its Groebner basis.;
ideal GI=groebner(I);
// Print it.;
GI;

As you see, Groebner basis is not an algorithm, but a form for a system, and its goal is not to find one solution, but to put the system in a form that helps compute properties of the set of solutions as a whole. Modulo technicalities, the set of solutions is called an algebraic variety. Problems that you might need to solve could be, for example,

What is the intersection of algebraic varieties? More explicitly, suppose you have a mechanical arm with both ends attached to two fixed points and having two or three elbows (joints). What are the positions that these elbows can be? It is an algebraic variety that can be described first as the intersection of the equations that you get by imposing the length of each segment of the arm and the condition on the fixed points at each end.

Parametrization of algebraic varieties. If the mechanical arm above had only one elbow, its positions would be a circle. Perhaps you know that $t\mapsto (\cos(t),\sin(t))$ parametrizes a circle, when $t\in[0,2\pi)$, but it could be better to get a rational parametrization, like $t\mapsto(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2})$, for $t\in[-\infty,\infty]$. Such parametrizations always exist. You compute them by an algorithm that uses Groebner bases among other things.

Maybe you need the inverse problem of (2), implicitization. You want a robot arm that can cut this shape that the design team chose for the silhouette of a car. They sure like their Bezier curves. They happen to be algebraic.

You want your computer to discover the proofs of all synthetic geometry problems that you did in high school. After sufficient squaring, the hypotheses and the thesis are polynomial equations. So, you only need to check that the first can reduce the latter to $0=0$. This a particular case of problem (1).


Articulation points (or cut vertices), but only subset of vertices need to be connected I know we can find all articulation points efficiently in a graph using DFS.

But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is a path between them). How to efficiently find all nodes (vertices) which removal will cause at least one of the mentioned pairs to be disconnected (can't communicate with each other)?

For example, we can have different cases for image below (undirected graph):

If pairs are A-B and C-D, then 2 is not vertex cut, because pairs
remain connected.
If pairs are A-C and B-D, then 2 is vertex cut,
    because pairs can't communicate (there is no path between them).

If we know set of pairs that need to communicate, what is the most efficient way to find all "vertices cuts"?

Let $P$ be the set of pairs of vertices that need to communicate and let $n$ be the number of vertices of the graph.

Compute the block-cut tree $T$ of your graph and root it in an arbitrary vertex.
Remove from $P$ all pairs that belong in the same block.
For any vertex $v$ of the graph, let $b_v$ be the vertex of $T$ representing the block in which $v$ belongs.

For each of the surviving pairs $(u,v) \in P$, compute the lowest common ancestor $LCA(b_u, b_v)$ of $b_u$ and $b_v$ in $T$. This requires $O(n + |P|)$ time using, e.g., Tarjan's algorithm.

For every pair $(u,v) \in P$, the cut vertices that disconnect $u$ from $v$ are exactly those that appear in the (unique) path of $T$ from $b_u$ to $LCA(b_u, b_v)$ or in the (unique) path of $T$ from $b_v$ to $LCA(b_u, b_v)$.

These vertices can be found efficiently by visiting $T$ in postorder. While visiting a vertex $x$, keep track of a special vertex $s_x$. This vertex might not always exist, but if it does it will always be an ancestor of $x$. The meaning of $s_x$ is the following: all cut-vertices in the path from $x$ to $s_x$ disconnect at least one pair in $P$.

The visit of a generic vertex $x$ proceeds as follows:

Let $x_1, x_2, \dots$ be the children of $x$ in $T$, and set $s_x$ to the vertex of lowest depth in $T$ among $s_{x_1}, s_{x_2}, \dots$, if any.

If $x$ represents a block $B$:

2.1. For each pair $(u,v) \in P$ such that $\{u,v\} \cap B \neq \emptyset$, set $s_x$ to the lowest vertex among $s_x$ itself (if $s_x$ exists) and $LCA(u,v)$.

If $x$ is a cut-vertex, $s_x$ exists, and $x$ is a descendant of $s_x$ (a vertex is a descendant of itself):

3.1. Report $x$ as a cut-vertex disconnecting a pair of interest.

Step 1 requires time proportional to the number of children of $x$ in $T$, therefore the total time spent in this step will be $O(n)$.
The overall time required to perform step 2 is $O(n+|P|)$ after a $O(|P|)$ preprocessing that associates the pairs in $P$ to the corresponding blocks.
Finally, step 3. requires constant time per vertex (since the ancestor-descendant relation can be checked in constant time after a $O(n)$ preprocessing).


Prove language is not regular? I know how to use the pumping lemma to do so, but I don't think that can be used for this language:

$$L = \{x \in \{0,1\}^* : \text{no prefix of $x$ has more $1$'s than $0$'s}\}. $$

What other method can I use to prove this?

Hint: use $0^n1^n$ for large enough $n$.

Another approach is to use the Myhill-Nerode criterion, say with the words $0^n$.


Definitional equality of two propositions about propositional equality Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.3) that:

  It is important that definition equality is pervasive so if M and N are definitionally equal then P(M) is definitionally equal to P(N) whatever P is. In particular the proposition stating that M is propositionally equal to N is definitionally equal to the proposition that M is propositionally equal to itself.

What I don't get is how a proposition about equality of M and N propositionally can be definitionally equal to the proposition about propositional equality of M and M ?

Recall that (a few paragraphs above)

  two objects are definitionally equal if after certain computation steps they evaluate
  to identical results.

Assume throughout this post that $M$ and $N$ are definitionally equal. This means that there is a series of computation steps $M_0 \leftrightarrow M_1 \leftrightarrow \ldots \leftrightarrow M_n$ where I use $\leftrightarrow$ do denote a computation step, and $M_0$ is the term $M$ and $M_n$ is the term $N$.

Any computation step can be applied in any context. This is part of the definition of computation rules for calculi used in logic (as opposed to calculi used to model programming languages with side effects). So if you stick $M_0$ in some context $P$, there is a series of computation steps $P(M_0) \leftrightarrow P(M_1) \leftrightarrow \ldots \leftrightarrow P(M_n)$. This means that $P(M_0)$ and $P(M_n)$ are definitionally equal, i.e. $P(M)$ and $P(N)$ are definitionally equal.

Apply this to a property $P(X)$ that expresses “$M$ is propositionally equal to $X$”, no matter how this is expressed in a particular calculus. $P(M)$ is definitionally equal to $P(N)$, i.e. a property that expresses “$M$ is propositionally equal to $M$” is definitionally equal to “$M$ is propositionally equal to $N$”.

Strictly speaking, there isn't necessarily a single proposition stating that $M$ is propositionally equal to $N$ — there may be ways to state this that are not definitionally equal (it depends on the exact calculus. If a calculus has multiple ways to express this, there can be two (or more) non-definitionally-equal propositions stating that $M$ is equal to itself, and then there are also multiple non-definitionally-equal propositions stating that $M$ is equal to $N$. But for each proposition stating that $M$ is equal to itself, that proposition is definitionally equal to a proposition stating that $M$ is equal to $N$, by applying the computation steps that rewrite $M$ to $N$.

Reasoning about equality can be difficult to follow. We tend to have an intuition that equality is just equality, dammit. It's a bit difficult to internalize that there are different concepts of equality, and worse, they coexist in the same theory. I think it helps if you use words other than “equality”. If two terms are written exactly in the same way (as strings or at least as abstract syntax trees), they're identical. As long as you're not reasoning about variable binding, you can extend that to terms that are identical except for variable names, i.e. terms that are alpha-equivalent. Beyond that, don't use the word “equal”. If there's a series of computation steps that leads from $M$ to $N$, say that $M$ and $N$ are computationally equivalent or rewritable to each other. They're not necessarily “equal”, but they're equivalent for a certain equivalence relation. Then it's obvious and not particularly confusing that there can be coarser equivalences between terms. For example, there's an equivalence relation between terms defined by “if you replace $M$ by $N$ in a true proposition, you get a proposition that's still true”. This is a form of observational or extensional equivalence of propositions. It can be called “observational equality” or “propositional equality”, but to form an intuition, don't call it that. And then it's not so shocking that if $N$ can be rewritten to $M$, then any proposition stating that $M$ is whatever-equivalent to $N$ can be rewritten to a proposition that states that $M$ is equivalent to itself.


What restrictions apply to query and target vector encoding on fast-forward neural networks? I'm currently studying fast-forward multi-layer neural networks with back propagation, in the book I see that all query and target vectors are binary-encoded, this makes me believe that this is the only allowed encoding, yet all other neurons in the hidden layers and output layer can take on any real value between 0 and 1.

Now I am creating my own neural network and I want to classify an image by using the RGB values of every pixel as input neurons in some way.

So now my question is, as the title states, what restrictions apply to the encoding pattern used for query and target vectors?

The inputs are not restricted to be 0 or 1.  They can be arbitrary real numbers.  In practice we often normalize or standardize the inputs so that they are in the range $[-1,+1]$ (or most of the input values are in that range), but even that is not required, and even then, they can be any real number in that range.

The outputs are also real numbers, and they can be any real number: not limited to 0 or 1, and not limited to a particular range.  (In some applications we interpret the outputs using the softmax function -- i.e., we postprocess the outputs of the neural network using another function -- which rescales them to get one likelihood value per output that's in the range $[0,1]$, but this is not mandatory and will depend on the specific application setting.)


Complexity of Double Selection Sort I would like to find the best, average, worst-case complexities of below code.

Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position

def double_selection_sort(arr):
    n = len(arr)
    for i in range(int(n/2)):
        _min, _max = i, n-i-1
        for j in range(i+1, n-i-1):
            if arr[_min] > arr[j]:
                _min = j
            if arr[_max] < arr[j]:
                _max = j
        arr[i], arr[_min] = arr[_min], arr[i]
        arr[n-i-1], arr[_max] = arr[_max], arr[n-i-1]

I think its in the order of O(nlogn).

Thanks in Advance

This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload.
Since the change is minor, you can simply read complexity from basic selection sort.

The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. There is no mechanism to ignore swaps or detect sortedness, two loops are passing through every element, so we can simply infer that best case is equal worst case and equal average case.
Two nested loops with arithmetic progression (array elements to be viewed decrease by one each step) $\sum_{i=1}^{n-1}i = \frac{1}{2}(n^2-n)$ are now decreased, giving $\frac{1}{4}(n^2-n)$, so still $\mathcal O(n^2)$ for all cases.


Why NAT is a disadvantage when TCP source port field is 16 bits? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:

My question is on the second paragraph. From what I understand, basically this part talks disadvantage of using NAT(Network Address Translation). I don't understand what second paragraph is trying to say about disadvantage of using NAT because it seems to me that the second paragraph is saying about benefit of using NAT because by using NAT, we can solve the problem of depletion of IP address.
Can anyone explain to me what the second paragraph is trying to convey?

The practical limit to the number of hosts that can use a single NAT'd address is much less than 61,440.  This is because even a modest Internet-capable computer will use many simultaneous TCP connections to hosts beyond the firewall.  Each of these connections, while it is open or being negotiated open or closed, counts against that 61,440 figure.  If each local host needs to reliably be able to initiate 200 external TCP connections at once, then that 61,440 value is reduced to only 307 hosts.  This won't be a problem for a typical home network (yet), but a small business could easily reach this limit.
If the TCP source port size were larger, then that would offer a correspondingly larger number of address:port pairs for address translation to use, permitting many more hosts and connections from behind the firewall.


Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states? I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below:

Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states $q$ of $A$ we have $\delta(q,a)=q$.
Show that either $\left\{a\right\}^*\subseteq L(A)$ or $\left\{a\right\}^*\cap L(A)=\emptyset$.

As far as my understanding of the first part of the problem, the language accepted by $A$ is  $L(A)=\left\{a, aa, aaa, aaaa, aaaa...\right\}$.
Since, $\left\{a\right\}^*$ represents strings that belong to $L(A)$ including $\varepsilon$, therefore $\left\{a\right\}^*\subseteq L(A)$ is true.
How to show that $\left\{a\right\}^*\cap L(A)=\emptyset$?
Doesn't $L(A)$ represent strings generated by $\left\{a\right\}^*$? How can the intersection be $\emptyset$?

Hint: Suppose that $a^k \in L(A)$ for some integer $k$. Consider the initial state $s$ of $A$. From the premises it follows that $\delta(s,a^k) = s$, and since $a^k \in L(A)$, $s$ must be an accepting state. For every integer $\ell$ we have $\delta(s,a^\ell) = s$ and so $a^\ell \in L(A)$.


Min max solution to the random assignment problem Consider the standard assignment problem: $n$ people are assigned to $n$ jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$ .
An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest costs incurred by any individual, in the spirit of the John Rawls fairness criteria (see here). Is it known any algorithm that finds such maximin allocation, and is it known what is the random sum of costs in the random version of the problem?
Many thanks,

Yes, there is an efficient algorithm to find an assignment that minimizes the largest cost.  Suppose we want to check whether there is an assignment with largest cost $t$.  To do that, delete all edges with cost larger than $t$, ignore the costs, and check whether the graph has a bipartite matching using the Hopcroft-Karp algorithm; if it does, there is a valid assignment.  Now use binary search over $t$ until you find the minimum $t$ such that a valid assignment exists.  Thus, the problem can be solved $O(|E| \sqrt{|V|} \lg |E|)$ time.


"Equality" problem in distributed computation I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads).
I have seen as a side note in a few lower bound proofs, a reference that says the proof could be shorter using the "linear lower bound theorem for the Equality problem", but I couldn't find the statement or proof of this theorem.
I would like to know a few things:

What exactly is this "Equality" problem? (how is it formulated?)
Where can I find a proof for its lower bound? (or if the proof is short enough, I would be glad if you could add it here)

Thanks!

This is probably referring to the communication complexity of the function $f(x,y) = 1$ if $x=y$ and $f(x,y) = 0$ if $x \ne y$.  See https://en.wikipedia.org/wiki/Communication_complexity#Example:_%7F'%22%60UNIQ--postMath-00000031-QINU%60%22'%7F for the formulation and a proof of the lower bound.


VC dimension of linear separator in 3D I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions.

In three dimensions, a linear separator would be a plane, and the classification model would be "everything on one side of a plane."

It's apparently proved that the VC dimension of linear separators is d+1, so in 3D, its VC dimension is four. That means it should be able to put any set of 1, 2, 3, or 4 points on one side of a plane.

But, what about this case: four coplanar points on a square with opposite corners same adjacent corners different?

+1    -1

-1    +1

This is the case that a line (2-dimensional linear separator) cannot handle, but the 3-dimensional linear separator is supposed to be able to shatter this. But, I can't see how you could put two corners on "one side of a plane" because all four points are coplanar.

Could someone explain how a 3-d linear separator can shatter the four points I just described?

You have a small (but crucial) misunderstanding of what the VC dimension of a class is.

The VC dimension is the maximal number $d$ such that there exists a set of $d$ points that is shattered by the class.
It doesn't mean that every set is shattered.

In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then they can be.

This is similar to the case of 2D: 3 points that are co-linear cannot be shattered by a line, but there exists a set of 3 points that can be shattered.


Selecting random points at general position How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line?

The following algorithm eventually works, but seems highly inefficient:

Select $n$ points at random.
Check all $O(n^3)$ triples of points. If any of them are on the same line, then discard one of the points, select an alternative point at random, and go back to 2.

Is there a more efficient algorithm?

Here's an approach that I think achieves $O(n^2)$ running time, as long as the points are not too dense (as long as $n$ is not too large compared to the size of the region).

Store the set of all slopes of lines between any pair of points.  There are $O(n^2)$ pairs of points, and each pair of points determines line; add that line to the set.  I suggest you store this as a hash table that maps the slope $s$ to the set of pairs $(P,Q)$ of points which are at slope $s$ from each other.

Now to add a new point, pick a point $R$ uniformly at random.  Pair $R$ up with each other point, say $P$.  Compute the slope of the line from $P$ to $R$.  Look up that slope in the hash table, and see whether the corresponding set contains the point $P$.  The latter can be done in $O(1)$ expected time if you use suitable data structures for the hash table and for storing the set (in particular, the entry corresponding to slope $s$ can be a hash-set of all of the points that participate in a pair whose slope is $s$).  Since $R$ can be paired up with $n$ other points, this check will take $O(n)$ expected time.

Now as long as the number of points is not too dense (so that you don't reject a point more than a constant fraction of the time), the expected running time will be $O(n^2)$.