Given a set of points in the plane all laying on the axis, find the number of right angled triangles My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa) but it's taking too much time..can anybody suggest me a better approach?

Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane.

Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ axis and the right angle is at the $y$ axis. The third is analogous where two vertices lay on the $y$ axis and the right angle is at a point on the $x$ axis. Let us solve the first two cases the third one can directly be derived from the second one.

The first case. Note that by excluding the origin from the set any point on the $x$ axis with a point on the $y$ axis form such a triangle with the origin so the number of such triangles is number of points on the $x$ axis times the number of points on the $y$ axis (excluding the origin).

The second case. Lets $X$ be the list of all points on the $x$-axis sorted in ascending $x$ coordinate and analogously we define the list $Y$ for points on the $y$-axis. $X$ and $Y$ can be build in time $O(n \log n)$. Note that for a fixed point on the $x$ axis the other point must be on the other side of the $y$-axis and as further it is from the axis, as further the $y$-vertex must be from the origin. So we can again use a sliding window approach. For each point $x_1$ to the left of the $y$-axix (we do the same later with the opposite side), iterate over all points $x_2$ to the right of the $y$-axis one by one from the left to the right and for each find the coordinate $y$ such that the points $x_1, x_2  (0, y)$ are a right-triangle wirth right angle at $y$. This can be found easily, since $y$ must be the point of intersection of the circle having $\overline{x_1 x_2}$ as a diameter with the $y$-axis. Note that $x_1, x_2 (0,-y)$ is also such a triangle. So we will keep two iterators starting at $y$ and one going upwards the other downwards, for each $x_2$ move both iterators till they reach a point whose absolute $y$-coordinate is not less than $y$. If it is equal to $y$ increase the number of triangles by one and iterate.

Here is an $O(n^2\log n)$ solution. For each point $p$ we will find the number of triangles that have a right angle at $p$ in time $O(n\log n)$. By iterating over all $p$ we can find the total count in the given time bound.

To this end let us sort all the points in polar angle relative to $p$ (we exclude $p$ from the set. Note that for a chosen candidate $p'$ we get that all triangles having an edge $\overline{pp'}$ have the third vertex at a fixed angle and hence all possible candidates appear consequently in the sorted list. So let us union all points having the same polar angle with $p$ in groups and keep a count for the size of each group. Now we can use a sliding-window approach to find for each group $g$ the group of points $g'$ (if it exists) such that $p$ forms a right triangle with each point of $g$ and point of $g'$. Note that by iterating over all groups we would have counted each triangle twice so we have to divide by 2 (or stop when the second pointer reach the first group).


The complexity of $A^{k \cdot log_{x} (n)}$ is exponential? The complexity of $A^{k \cdot log_{x}(n)}$ is exponential? ($k$ and $x$ is constants, $A$ is defined constant base, $n$ is the size of the task).

It is in a class of polynomial complexity?

This is polynomial complexity, because

$$A^{k \log_x n} = A^{k \lg n / \lg x} = (2^{\lg A})^{k \lg n / \lg x} = (2^{\lg n})^{k \lg A / \lg x} = n^{k \lg A / \lg x}$$

and $k \lg A / \lg x$ is a fixed constant.


Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$ Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation
$$W \cdot W^{T} = M,$$
where $M$ can have negative entries.

You might be looking for the Cholesky decomposition. The referenced article also contains an example for  $M$ having negative entries. Note the constraints on $M$ for this decomposition to exist.


Introductory Book on Pseudo-Random Number Generation I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is.

My Request

I'm looking for an introductory book on pseudo-random number generation.  Does one exist?

My Requirements

The book must be understandable by someone with the following mathematics background:

calculus
discrete math (combinatorics, logic and proofs, set theory, mathematical induction, functions and relations, inclusion-exclusion, generating functions, recurrence relations, graphs/graph algorithms)
linear algebra (vectors,matrix algebra, eigenvalues, transformations, diagonalization)
introductory numerical analysis (computer arithmetic and errors, root-finding algorithms, computational techniques for matrices, numerical integration and differentiation)

I would prefer a book that does not require knowledge of any specific programming language:

Would like algorithms to be presented in a pseudocode style (e.g. Introduction to Algorithms by Cormen)
If the book isn't language neutral, I know the following languages: Python, Java, C++,C,Ruby.

I'm looking for a book that is accessible to a fairly inexperienced CS undergraduate:

I have a basic understanding of stacks, linked lists, trees, heaps, hash tables and graphs
I'm comfortable with basic programming concepts

The book should cover pseudorandom number generation at an introductory level:

I'm not looking for a complete encyclopedic treatment on every research paper ever published in the area, but enough content to gain an entry level understanding in the area that you'd expect someone to learn in a first undergraduate course on pseudo-random number generation. For example if someone asked you for a book on introductory calculus you'd probably recommend a book that covers limits, differentiation, related rates, approximation of derivatives, L'Hopital's Rule and some basic continuous optimization. I'm looking for something similar in the area of PRNG. It's hard for me to specify exactly what I'm looking for because I know next to nothing about the area, but try and think of what you'd expect a complete amateur in the area to be able to reasonably learn in a semester.

What I've Tried

I'm looking at Chapter 3 of Donald Knuth's art of computer programming volume 2. The book seems quite old and uses some kind of assembly that I don't understand. If this is the authoritative reference, I'll find my way around these issues, but other books would be nice.

The book Random numbers and computers by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python. It is aimed at "anyone who develops software, including software engineers, scientists, engineers, and students of those disciplines".


How to prove that DFAs from NFAs can have exponential number of states? All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. Therefore, its states should be members of the power set of states of the NFA. This seems to indicate that the number of states of the DFA could scale exponentially in terms of the number of states of the NFA. However, I was wondering how to actually prove this.

One operation that transforms an NFA into another NFA but does not do so for a DFA is reversal (point all the arrows the other way round, and swap initial states with accepting states). The language recognized by the transformed automaton is the reversed language $L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$.

Thus one idea is to look for a language that has an asymmetric construction. Going forward, this language should be recognized by inspecting the first $n$ symbols, requiring only $n + O(1)$ states. Going backwards, it should be necessary to keep a memory of the last $n$ states, which requires $A^n + O(1)$ states where $A$ is the alphabet size.

We're looking for a language of the form $M_n S M'$ where $M_n$ consists of words of length $n$, $S$ is a nontrivial subset of the alphabet, and $M'$ doesn't provide any further constraint. We might as well pick the simplest alphabet $\mathscr{A} = \{a,b\}$ (a singleton alphabet won't do, you don't get smaller NFAs there) and $M' = \mathscr{A}^*$. A nontrivial $S$ means $S = \{a\}$. As for $M_n$, we require that it does not correlate with $S$ (so that the DFA for the reversed language will need to keep the memory of $S$): take $M_n = \mathscr{A}^n$.

Thus let $L_n = (a|b)^n a (a|b)^*$. It is recognized by a simple DFA with $n+2$ states.

Reversing it yields an NFA that recognizes $L_n^R = (a|b)^* a(a|b)^n$.

The minimal DFA that recognizes
$L_n^R$ has at least $2^{n+1}$ states. This is because all the words of length $2^{n+1}$ must reach distinct states in the DFA. (In other words, they belong to distinct Myhill-Nerode equivalence classes.) To prove this, take two distinct words $u,v \in \mathscr{A}^{n+1}$ and let $k$ be a position where they differ ($u_k \ne v_k$). Without loss of generality, let's assume $u_k = a$ and $v_k = b$. Then $u b^k \in L_n^R$ and $v b^k \notin L_n^R$ ($b^k$ is a distinguishing extension for $u$ and $v$). If $u$ and $v$ led to the same state in a DFA recognizing $L_n^R$ then so would $u b^k$ and $v b^k$, which is impossible since one leads to an accepting state and the other one doesn't.

Acknowledgement: this example was cited in Wikipedia without explanations. The article gives a reference to an article that I haven't read which gives a tighter bound:
Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", Theoretical Computer Science 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9.


Subgraph Isomorphism checking in Multigraphs I am considering the following problem:

Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs
Question: Find a subgraph in G which is isomorphic to H

Is there any algorithm available for checking subgraph isomorphism in Multigraphs (specifically for multiple edge types) ?
If yes, what is the complexity?

Submultigraph isomorphism is clearly NP complete:

it's easily seen to be in NP (an isomorphism can be specified in space polynomial in the size of the graphs, and it's easy to check that a proposed isomorphism is valid);
it includes the NP-complete subgraph isomorphism problem as a special case.

The more interesting question is what the best known algorithms are; I'm afraid I can't help with that.


Time Complexity of the Kruskal Algorithm after sorting In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?

Almost linear in term of the number of edges of the graph.

More specifically, here is the quote from Wikipedia entry on Kruskal's algorithm.

  Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in $O(E \,\alpha(V))$ time, where α is the extremely slowly growing inverse of the single-valued Ackermann function.

Here $E$ stands for the number of edges in the graph and $V$ stands for the number of vertices in the graph. In fact, $\alpha(n)$ is less than 5 for any practical input size $n$, since  $\alpha$ is the inverse of the growing function $f$ and $f(1)=3$, $f(2)=7$,$f(3)=61$, $f(4)=2^{2^{2^{2^{16}}}}-3$, a number whose number of digits is a number whose number of digits is 19727 (all fractional parts ignored). In other words, even if $n$ has trillions of trillions of digits, $\alpha(n)$ is still 4.

Please note in computer science, this factor $a(V)$, however slowly grows, represents a real barrier to achieve a linear algorithm even after the edges have been sorted by weight.


Is this system Turing complete? I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.

I came up with the following idea:

The input is an array of $N$ integers. The genetic program consists of up to $N$ ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.

The ASTs can be arbitrary complex and consist only of four arithmetic operators ($+$, $-$, $\times$, $/$) and can operate on constants and fixed elements of the given array (no random access).

So for $N=3$, we have three ASTs, for example:

\begin{align*}
    a[0] &= a[0] + 1\\
    a[1] &= a[0] + a[1]\\
    a[2] &= a[0] \times 123 + a[1]\,.
\end{align*}

The $N$ ASTs are executed one after another and this is repeated infinitely.

Now my question, is this Turing complete or will it fail to solve some kinds of problems common for an game AI?

You can probably use this to simulate register machines and, if you can do that, the system is Turing complete.

The setup is as follows.

The machine has a sequence of names registers, each of which holds a non-negative integer.
Program instructions are labelled with non-negative integers and execution starts with, say, instruction $0$;
The three possible instructions are:

halt;
increment register $R$ and goto instruction $I$ (where $R$ and $I$ are integer constants);
if register $R$ is zero, goto instruction $I$; else, decrement $R$ and goto instruction $J$ ($R$, $I$ and $J$ are constants).

For example, the following program adds the contents of registers $0$ and $1$ and halts with the sum in register $0$:

0. if R1=0, goto 2 else decrement R1 and goto 1
1. increment R0 and goto 0
2. HALT

My recollection from computation theory classes 20+ years ago is that you can simulate a Turing machine using a register machine with two registers (and certainly with some fixed number of registers). Proving this is long and tedious because you have to code up the tape and all manipulations of it as arithmetic operations and, heck, you even have to code up arithmetic operations such as addition, multiplication and exponentiation. Oh, and you'll probably have to be more careful than I was with my addition routine, because you'll probably want to do arithmetic on two values without destroying them both, which requires copying them to extra registers and then copying back.

You can simulate a two-register machine (i.e., a register machine with two registers) with $n$ instructions with your system as follows.  Use two array cells to store the register values, and then probably one array value for each instruction, such that $A[i]=1$ if instruction $i-2$ is the next to be executed and $A[i]=0$, otherwise. Then executing the system with $A=[x,y,1,0,\dots,0]$ should simulate the register machine running with input $x$ in the first register and $y$ in the second.  If there are $n$ instructions in the program, ASTs will look like this:

$$A[i]=(A[2]*v_0) + (A[3]*v_1) + ... + (A[n+2]*v_n)\,,$$

where $v_j$ is the value that should be stored in $A[i]$ if instruction $j$ is executed.

Note that all of this assumes that the array elements can hold unboundedly large numbers. If not, your system only has a finite number of states so cannot be Turing-complete. The simulation I have in mind only uses non-negative integer values in the arrays.


Is the Berman-Hartmanis Conjecture Solved? The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on One-Way Functions and Polynomial-Time Isomorphism).

Since the Cook-Levin theorem states that $NP$ is polynomial-time reducible to $NP$-complete.

Does the Berman-Hartmanis conjecture state anything about the converse statement? I.e. if $NP$ is polynomial-time isomorphic to $NP$, then one-way functions do not exist?

It seems to me that proving the converse and proving the non-existence of one-way functions proves the $P=NP$ problem.

Furthemore, is the Berman-Hartmanis conjecture solved?

The conjecture remains open. Also there is a proof that shows that if the conjecture is true, then P=/=NP. To my knowledge no one has proven the opposite, that if the converse is true then P=NP, to be true.


Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s Design a Pushdown Automata, accepting either by final state or by
  empty stack to accept the set of all strings of 0’s and 1’s such that
  no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I'm not looking for the answer, right now I'm just trying to understand the question. I don't understand what sort of words would be accepted and what would be rejected. For example, I can't understand whether the following word would be accepted:

011011 ; where 01 is prefix and 1011 is suffix
011011 ; where 011
is prefix and 011 is suffix
011011 ; where 0110 is prefix and 11 is
suffix

My question is: Given a word, how do I know which part of it is the prefix?

Please try to give an explanation without the actual PDA answer, I'd like to try it myself first.

If we have a word, $w=a_1a_2\dots a_n$ where the $a_i$ are characters from the underlying alphabet, then the prefixes of $w$ are the empty word, $\epsilon$, and the words $a_1$, $a_1a_2$, $a_1a_2a_3$, ..., $a_1a_2\dots a_{n-1}a_n$. In informal terms, the prefixes of a word consist of all left-hand segments of the word.


Problem with proving the undecidability of REGULAR$_{TM}$ Sipser in his book provided the following proof for undecidability of  REGULAR$_{TM}$:

  S = “On input $<M,w>$, where $M$ is a TM and w is a string:

  Construct the following TM $M_2$.

  $M_2$= “On input $x$:

  If $x$ has the form $0^n1^n$, accept .
  If $x $ does not have this form, run $M$ on input $w$ and
  accept if $M$ accepts $w$.”

  Run $R$ on input $<M_2>$.
  If $R$ accepts, accept; if $R$ rejects, reject .”

and it also states:

  Note that the TM $M_2$ is not constructed for the purposes of actually running it on some input. We construct $M_2$ only for the purpose of
  feeding its description into the decider for REGULAR$_{TM}$ that we have assumed to exist.

So it means we don't run the $M$ on $w$ at all. I would like to know why when the $M_2$ accepts regular languages we conclude that the $M$ accepts $w$ while we never run $M$ on $w$? The reduction must have a meaningful relationship between the problems. I can't understand this relation in this problem.

thanks

Note $M_2$ is constructed based on $\langle M,w\rangle$. That is to say, different $\langle M,w\rangle$ may result in different $M_2$.

If $M$ accepts $w$, then $M_2$ will accept any string (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ accepts it at the second step), thus $M_2$ accepts a regular language.

If $M$ does not accept $w$, then $M_2$ will only accept string of the form $0^n1^n$ (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ skips the first step, and will not accept it at the second step), thus $M_2$ accepts a non-regular language.

So we can conclude $M$ accepts $w$ iff $M_2$ accepts a regular language.


Which in-memory data structure can accommodate billions of md5 value? For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it.
I tried using hash data structure, it worked well but no of lookups goes high with table entries.
I tried using trie, each node storing a byte, but the memory consumption is too high. As each node required 256 pointer for successor on next level.
Can anyone suggest better data structure which could use less space as well as no of lookups is The ?

Maybe you can use a binary trie (critbit tree?) that splits in two on each node instead of 256? Of course you get many more nodes, but they are a LOT smaller.
An example implementation in Java is here: critbit


Avarage height of Red-Black tree I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes).

On first test I filled array with 10-50-100-200...-1000 elements of random numbers from 0 to 32k~~ and checked their height and then second array with the same number of elements, however this time keys were picked randomly from 0-9, instead of 0-rand().

And I wonder if I have this right, is this possible height or im just getting some semi-random numbers. Would be grateful for checking that out. For now I don't know how to compare these scores and charts. The scores are very close, but the first array seems to have height slightly lower than second array.

As a rule of thumb, your red-black tree depth can't be less than log(n) and it shouldn't be more than 2*log(n+1). Your numbers look correct. (log(1000)=10 and your 1000 sample tests are between 10 and 20).

Ref: http://lcm.csa.iisc.ernet.in/dsa/node115.html


Is the language of words containing equal number of 001 and 100 regular? I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a language such as $L$, where $L$ = $\{ w \mid$ number of instances of the substring "001" equals the number of instances of the substring "100" $\}$ regular? Note that the string "00100" would be accepted.

My intuition tells me it isn't, but I am unable to prove that; I can't transform it into a form which could be pumped via the pumping lemma, so how can I prove that? On the other hand, I have tried building a DFA or an NFA or a regular expression and failed on those fronts also, so how should I proceed? I would like to understand this in general, not just for the proposed language.

An answer extracted from the question.

Yes, it is regular; below is an automaton that accepts it.

As pointed out by Hendrik Jan, there should be an additional 0 self-loop at q5.


Computing the complement of a set Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list.
I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in $\{1, \ldots, n\}$ but not in $A$.

One way to do this is to sort the entries of $A$ and then go through them and list all the entries I do not see. This takes $O(n \log n)$ in the unit cost RAM model. My question is whether there exists a linear time $O(n)$ algorithm in the same model.

Since you have both lists, even if not both at the same time, your
space cost is at least that of the longest, thus at least $n/2$.
This corresponds to a $O(n)$ space complexity.

So, unless you exclude it for some reason, it makes sense to use a bit
array $M[1:n]$ to represent the set A by its characteristic function,
i.e. $M[i]=0$ iff $i\notin A$, and $1$ otherwise. The space complexity
is unchanged, and the array $M$ is actually much smaller than one of
the two lists (initial or final).

Initializing the array $M$ from the initial list is linear.

Then you can take the logical complement of the array $M$ in linear
time.

Then you scan the array in linear time to get all the element of the
complement of your initial list in linear time $O(n)$

Of course, by now you have noticed your mistake: sorting is in time
$O(n \log n)$ (or better according to comment) when $n$ is the number
of element to be sorted.  But it is trivially linear if $n$ is the size of the
finite ordered set they come from.

Using an array, as I just did is one way of sorting in linear time with respect to the size of the referance set.

Your own answer was good because of that. Only your complexity assessment was wrong.


write adt for stack operations Ok, I dont understand whats the difference between:
write code for stack operations and write adt for stack operations?
lets say the operation is push() and pop(). So what different code is to be written for adt?

Code is literal programming code (be it C/C++, Java, Python, etc.). We can agree the code will be completely different between languages. In addition, if you are implementing a stack, then you have modify your code depending on what underlying data structure you're using to store the data (c style arrays in C, ArrayLists in Java,  etc.).
ADT is a way to express the basic operations of the data type independently from the code (from any programming language). This leads to pseudocode.
For instance, a queue ADT might have the following functions: enqueue, dequeue, front. The enqueue function takes data and adds it to the back of the queue; the dequeue function removes data from the front of the queue and returns it; finally the front function simply returns the first data in the queue but does not remove it.
The above is the most basic queue ADT, but you could have other functions like back, isEmpty, or even something weird like thirdPlaceInQueue. It all depends on what your needs are. Be careful though, giving too much functionality may lead to a different ADT. For instance, if you gave a queue ADT the ability to add to the front and remove from the back, you would then have a deque ADT.


Finding missing range in multidimensional domain Let's suppose that I have a monodimensional numeric domain and a list of ranges in this domain defined as

class Range {
    int lowerBound;
    int upperBound;
}

then it's trivial to check if the union of the List<Range> is covering the entire domain. However in case of a bidimensional domain I have a List<Pair<Range>> and I'm no longer able to figure out if my rectangles (bidimensional ranges) are covering the entire area.

For example suppose that I have these ranges:

pair{ range{0, 7}, range{0, 5} },
pair{ range{7, 10}, range{0, 7} },
pair{ range{0, 5}, range{5, 10} },
pair{ range{5, 10}, range{7, 10} }

covering the domain as shown below.

How can I know that part of the domain isn't covered? (gray area in the picture). In other words is there an algorithm or a data-structure allowing to find if there exists at least one point in that domain that is not included in any of the rectangles? Is this solution also extensible to the n-dimensional case?

This problem is known in computational geometry as Klee's measure problem.

The solution to this problem in 2D case is based on an approach known as Sweep Line Algorithm and is know as Bentley's algorithm.

Conceptually, it is as easy as sweeping the plane by a vertical line from left to right. An intersection of a vertical line with a set of rectangles is a set of one-dimensional ranges. That way, a two-dimensional problem is reduced to $O(N)$ one-dimensional problems.

Here is an overview:

Represent each rectangle as a pair of vertical ranges. One range on the left-hand side of it and one range on the right-hand side of it.
Sort vertical ranges by their $x$ coordinate. That should take $O(N \log N)$ time.
Scan the resulting $2N$ vertical ranges in increasing order of $x$ coordinate while maintaining a set of active ranges. When encountering a left-hand side of the rectangle the corresponding range is added to the set, crossing a right-hand side removes the corresponding range.
As you finish processing updates to the set at the given $x$ coordinate verify that the current set of active ranges covers your $y$ range completely.

An efficient implementation of this algorithm maintains a set of ranges in a data structure that supports $O(\log N)$ update and query operations. It can be implemented by building a Segment Tree for all different $y$ coordinates and maintaining a total covered range in that segment tree.

It gives an overall $O(N \log N)$ complexity for a 2D algorithm.

This algorithm can be generalized to higher dimensions with $O(N^{d - 1} \log N)$ complexity. However, there are better algorithms for $d > 3$. You can find references in the Wikipedia article for Klee's measure problem.


Prefix/suffix property of language containing only empty word Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?

The definition says that language has prefix/suffix property requires that there is no code word in the system that is a prefix (initial segment) of any other code word in the system.

So if we have this finite language with $\varepsilon$ this mean that, there arent any prefix/suffix of empty word so our language has or not prefix/suffix property?

You probably mean $L=\{\varepsilon\}$, i.e. the language which contains only the empty word, as opposed to the empty language. Both the empty language and the language which contains only the empty word have the prefix/suffix property, since they satisfy the definion.

However, the prefix property is a property of a code, not a property of a language. A language can describe a code, but neither the empty language nor the language which contains only the empty word describe a code. So in the end it is irrelevant whether those languages have the prefix/suffix property.

Edit rici is right that Hopcroft&Ullman say that the LR(0) grammars define exactly the DCFL's having the prefix property. (They hasten to add that the prefix property is not a severe restriction.) So in this case it is good that the empty language and the language which contains only the empty word have the prefix property. Additionally, Berstel&Perrin allow the empty set as a code, so you can also dispute my other claim. But they agree that $\{\varepsilon\}$ has the prefix property, and is not a code:

  Proposition 2.1.9 Any prefix (suffix, bifix) set of words $X\neq \{\varepsilon\}$ is a code.

Both Hopcroft&Ullman and Berstel&Perrin consider $\varepsilon$ to be a prefix/suffix of any word, but they require a proper prefix/suffix in the definition of the prefix/suffix property. (This is clearly the right thing to do, otherwise no set of words would have the prefix/suffix property.)


Representing a network with two types of connections: A fishing application I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together.

Here's the most basic setup. Say there are two people represented by nodes.

Person one owns a fishing right and also acts as an authority who can land fish.
Person two is a fisherman.

Person one sells the signle fishing right to person two. Person two catches the fish and sells the fish back to person one. Intuitively, I want to write a directed adjacency matrix, in which positive i,j values represent the fishing rights transaction and negative j,i values represent the physical fish transaction, which leads to the following adjacency matrix:

\begin{bmatrix}
     0 & 1 \\
     -1 & 0
   \end{bmatrix}

My question is: Can I use signs like this to represent related but distinct connections? The basic logis follows from the fact the total fish caught = the total fishing rights. By summing the elements, we get zero representing a closed system. Here is a more complicated example:

\begin{bmatrix}
      0 & 1  & 0  \\
      0 & 0  & 0  \\
      0 & -1 & 0 \\
   \end{bmatrix}

In this example person one sells the fishing right to person two as before. Now there is a person three, however, who lands the fish. Again the sum of all the elements is zero as total fishing rights = total fish caught. The network captures a different reality, however. In this second network, all the activities are separated as in an open market. In the original network, all the activities were through a relationship between person one and person two.

Sure, of course.  You can define a matrix to contain whatever numbers you want it to contain.  There's nothing that prevents you.  The real question is whether the result has the properties you want it to have, but since you haven't listed any properties, there's nothing to answer here.


Check two balanced binary search trees that sub set of each other Given two balanced binary search trees $T_1,T_2$. We want to check,
are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have
$n_2$ nodes.
Instructor say it can be done in $O(n_1+n_2)$ time complexity with
$O(\log n_1+\log n_2)$ space.

My idea:
I use in order traverse on two trees , and compare first node in order traverse  $T_1$ with first node in in order traverse $T_2$, and etc. if all nodes in $T_1$ present in $T_2$ then  we say $T_1\subseteq T_2$, but i can't prove my space complexity followed from mentioned complexity. Any one can help to guarantee my space complexity be $O(\log n_1+\log n_2)$.

When you try to traverse a tree, you start at the root, and you will have to remember all the nodes that you were visiting, to be able to find the next node. If your tree is balanced, then it contains only O (log n) nested notes, so your space requirement for two trees is only O(log n) + O(log m). Unbalanced trees could be nested up to n levels deep, so you could need up to O(n) + O(m) space to traverse both trees.


Is there an existing algorithm for this type of sorting? This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted books, and must quickly sort them into alphabetical order.

A number of commenters pointed out that a far more practical method for real-life sorting would be to take the first letter of each book and put it into 26 different piles (an A pile, a B pile, down to a Z pile.) Then use a conventional sorting method (insertion / quick sort etc.) for each of the 26 sub-piles (which would contain around 50 books each, assuming a roughly even distribution of letters. Or you could repeat the same process if the sub-pile is significantly large, sorting the As into ABs, ACs, ADs and so on.

Is there a name of this kind of sorting algorithm?

This is called bucket sort: split your data range into $k$ "buckets" ($O(k)$), put the data into the buckets ($O(n)$), sort each bucket (however you like), then concatenate all the buckets ($O(k)$). If the sorting is faster than $O(n \log n)$, then the whole algorithm runs faster than any comparison-based sort possibly could!

The problem is that it depends on the distribution of the data. If 99% of your book titles start with A, this gives no real benefit at all! And it doesn't work on data that can't be divided into buckets.

A variation of this, "radix sort", is basically the same except in binary (and with some extra recursion). It runs in $O(wn)$, where $w$ is the bit length of your data (the "word size").


How to make efficient path minimum queries in a tree? Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them?
My original idea was to solve Least Common Ancestor Queries on any two nodes (using an Eulerian Tour Tree or the Binary Lifting Method), then to split any path into one or two vertical paths that pass through the LCA. After this, we could process the path minimum query on the vertical paths.
However, processing the path minimum query on a vertical path proved to be pretty hard: in path sum queries (finding the sum of all node values on a path), if we know the sum of all nodes from an ancestor to the parent of node A, and also the sum of all nodes from that ancestor to node B, then the sum of all nodes from node A to node B is just equal to the second value minus the first one. In Range minimum Queries, however, this does not work.
Is there any efficient way to solve this problem? Am I missing something in my current approach?

You can preprocess your tree in time $O(n \log n)$ so to obtain a data that uses $O(n)$ space that can answer path-minimum queries in constant time. See "Bottleneck Edge Queries" in this paper which shows how to answer queries that ask for the edge of minimum weight in the unique path between two given vertices in a tree.
You can easily reduce your problem by splitting each edge into two edges and then setting the weight of each edge incident to a vertex $v$ of the original tree to the weight of $w$ itself.
If you are find with a solution that is easier to implement but requires $O(n \log n)$ space and preprocessing time (rather than the $O(n)$ space of the paper I liked above), and supports $O(\log n)$-time queries, then you can do  the following:
Start by constructing a LCA oracle for $T$. To do so consider an Euler tour $E = \langle u_1, u_2, \dots u_{m}\rangle$ of your tree and construct an array $A[1 \dots m]$ where $A[i]$ contains the depth of $u_i$. Here $m=2m-2$. Then construct a range minimum query (RMQ) oracle on $A$, so that the LCA $u_k$ between $u_i$ and $v_j$  with $i<j$ is such that $k$ is the index of the minimum $A[k]$ in $A[i], \dots, A[j]$.
A simple RMQ oracle is the following: for each index $i$ of $A$, and for each $j=0, 1, \dots, \lfloor \log m \rfloor$, store in $B[i, j]$ the index $k$ of the minimum $A[k]$ between $A[i], \dots, A[i+2^j-1]$. All the entries of $B$ can be found in $O(n \log n)$ time since, for $j>0$, $B[i,j]$ is either $B[i, j-1]$ or $B[i + 2^{j-1}, j-1]$.
The answer to a RMQ query $(i,j)$ is then the index of $A$ with the minimum value among the two indices $B[i, \Delta]$ and $B[j- \Delta, \Delta]$, where $\Delta=\lfloor j-i+1 \rfloor$.
We are now able to find the LCA $w$ of two vertices $u$ and $v$ in constant time. Then your problem reduces to the one of finding the vertex of minimum weight in two ancestor-descendant paths, namely those between (i) $w$ and $u$, and (ii) $w$ and $v$.
This can be done using a trick similar to the previous one: For each vertex $z$ at depth $d$ maintain $\delta = \lfloor \log d \rfloor$ values $M[z, 0], \dots, M[z, \delta]$, where $M[z, j]$ is the minimum among the weights of the vertices $z= z_1, z_2, \dots, z_{2^j}$ encountered by walking from $v$ towards the root for $2^j - 1$ steps. Moreover, for each vertex $v$, we explicitly store the $O(\log n)$ vertices $z_{2^j}$.
As before, all the values $M[z,j]$ can be found in $O(n \log n)$ time and a path query on an ancestor-descendant path of length $L \ge 2$ can be answered by letting $\ell = \lfloor \log L \lfloor$ and selecting the minimum among $M[z, \ell]$ and a recursive query for the path of length $L - 2^\ell$ that ends with $z_{2^\ell}$.
The query time can actually be improved to $O(1)$ if you additionally compute a long-path decomposition of your tree. The long path decomposition is defined recursively and is obtained by selecting the longest root-to-leaf path $P$, deleting (the edges and vertices of) $P$ from the tree and returning the union of $P$ with all the long-path decompositions of the trees in the resulting forest.
This decomposition can be found in $O(n)$ time and has the following property: given a vertex $v$, the (unique) path $P_v$ that contains $v$ has a lenght |P_v| not smaller than the height of the subtree rooted in $v$.
Let $P_1, P_2, \dots$ be the paths of the decomposition and for each $P_i$ construct an array $P'_i$ by extending $P_i$ by $|P_i|$ edges towards the root, and writing down the vertex weights along this extended path.
Build a RMQ oracle on each of the obtained arrays and, for each $v$, keep a reference to the position of $v$ in the (unique) array associated with the path $P'_v$ such that $v$ is contained in $P_v$.
The total size of the arrays is $O(n)$ and hence the total size of the  RMQ oracles is $O(n \log n)$.
A query on an ancestor-descendant path can now be answered in $O(1)$ time by first looking at $M[v, j]$ and a then querying the oracle associated with $P'_{z'}$, where $z'=z_{2^\ell}$.
This is because $L-2^\ell < 2^\ell$ (by the choice of $\ell$), showing that $P_{z'}$ has length at least $2^\ell-1$, and hence all the remaining $L-2^\ell$ proper ancestors of $z'$ (that were not already considered in $M[v, j]$) must be in $P'_{z'}$.
There is a great paper explaining this technique that combines the lookup table $M$ with this extended path-decomposition.
With some additional work you can even get rid of the $O(\log n)$ factor in the space complexity.


Nested for-loop math notation I'm new to writing math notation that describes algorithms and I need to translate some python code. Does the notation structure below correctly describe a nested for-loop that for-each value in p iterates over all other values in p?

Example code
function(p):
    for a in p:
       for b in p:
         // do something with a and b...

The $\sum$ notation is specifically summation. There is also product notation:
$$n! = \prod_{i=1}^{n} i $$
But I think what you want is some kind of Zermelo-Fraenkel notation?
$$\left\{ f(a,b)\,|\,a,b \in P \right\}$$


Comparison-based lower-bound for finding duplicates in an array of $n$ numbers Decision Problem: Given $n$ real numbers, give an algorithm that outputs "1" iff there are at least two numbers that are identical and outputs "0" otherwise.
  (Assume that comparison between any two numbers works in $O(1)$-time).

The problem is obviously solvable in $O(n\log n)$-time via augmenting mergesort, and when we limit the numbers to integers or bitstrings, we might be able to use hashing to improve the runtime.

However, an acquaintance told me that there is an $\Omega(n\log n)$ lower bound to this problem on the comparison model, meaning that this problem is as hard as sorting. Is he correct? If so, give a proof.

Your problem is known as element distinctness. You can find $\Omega(n \log n)$ lower bounds for several computation models in the answers to a question on cstheory. The lower bound for the comparison model is particularly simple.


Theoretical minimum number of registers for a modern computer? I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an interpreter). In the project we made some assumptions about the target machine closely related to "real" native executables, including:

a run-time stack, tracked by a dedicated stack pointer ("SP") register
a heap for dynamic object allocation, tracked by a dedicated heap pointer ("HP") register
a dedicated program counter register ("PC")
the target machine has 16 registers
operations on data (as opposed to, e.g., jumps) are register-to-register operations

When we got to the unit on using register allocation as an optimization, it made me wonder: What is the theoretical minimum number of registers for such a machine? You can see by our assumptions that we made use of five registers (SP, HP, PC, plus two for use as storage for binary operations) in our compiler. While optimizations like register allocation certainly can make use of more registers, is there a way to get by with fewer while still retaining structures like the stack and heap? I suppose with register addressing (register-to-register operations) we need at least two registers, but do we need more than two?

If you allow direct memory access by memory address, then you do not need any "registers" because you can use memory locations instead. For example, memory at location 0 can be the program counter, at location 1 we have the stack pointer, etc. But that is cheating.

So to prevent ourselves from cheating, let us assume there is no direct memory access, because we could use fixed memory locations as registers. Then we can get away with two registers, a program counter and a stack pointer, as explained in the Wikipedia article on stack machines. The stack is only accessible through the stack pointer, and the program is only accessible through the program counter.

Another possibility is to use counter machines. A two-counter machine is Turing complete, i.e., it can compute whatever Turing machine can. This again is nicely explained in the Wikipedia article on counter machines.


Is there any Boosting algorithm with closed-form solutions? My goal is to formulate the learning and generalization phases of any Boosting algorithm as a matrix-vector operation.

Through Google, I found a good pdf (*) describing several boosting algorithms but the author Marco Cusumano-Towner only hints and doesn't explain how to recast the boosting algorithms (GradientBoost, Adaboost, QuadBoost) using matrix operations.

My question is:

Can I formulate a boosting algorithm as a regression, a game or a linear programming and arrive at closed-form solution which uses only matrix operations?

(*) Boosting with log-loss

Basically: no.  Boosting is a "meta-method".  If you have a weak learner (an algorithm for learning), it is a way of taking advantage of that weak learner algorithm iteratively to do better at learning some concept than the weak learner would do on its own.

Many/most weak learners don't have a closed-form solution for the model they build; instead, their learning algorithm may fundamentally rely upon iterative methods, optimization algorithms, or other techniques.  As a result, boosting with such a weak learner won't have a closed-form solution, either.


Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$ I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
The site here https://courses.csail.mit.edu/6.046/fall01/handouts/ps2sol.pdf mentions :

The running time of HEAPSORT on an array A of length n that is sorted in decreasing order will
be  $\Theta(n\lg n)$.
This occurs because even though the heap will be built in linear time, every time the
max element is removed and the HEAPIFY is called it will cover the full height of the tree.

It's the last line which I can't understand. I tried the array A <7, 6, 5, 4, 3, 2, 1>. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get <6, 4, 5, 1, 3, 2> 7. However, the second time itself the full height of the tree is not covered and I get <5, 4, 2, 1, 3> 6, 7. How does that statement hold then?
Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs full $\lfloor \lg k \rfloor$  operations, where k (I'm assuming) is the number of nodes in the modified heap in each iteration, thereby obtaining the summation.
$$ \sum_{i=1}^{n-1}\lg{(n-i)}= \lg\Big((n-1)!\Big) = \Theta(n\lg{n}) $$
Can someone help me realize this. I just want to understand how MAX-HEAPIFY covers the full height of the tree each time it is called.
UPDATE: I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. During HEAPSORT, if each node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree, that would mean that each call to MAX-HEAPIFY won't perform full $\lfloor \lg k \rfloor$ operations but $ \Theta(\lg k) $ operations, right? (I know $\lfloor \lg k \rfloor $is also $\Theta(\lg k)$ but all I need is for MAX-HEAPIFY to perform $\Theta(\lg k) $ operations each time)  $$ \sum_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But that statement doesn't hold as pointed out in the comments. Now I don't have anything to work with. How can I guarentee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time?

Edit: This proof is insufficient as pointed out in comment.
I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.
Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.


Computability of function composition I have some problems to understand computability and hope you can help me.
In the lecture we had following problem:
Consider the three partial functions $f,g,h\colon N \to N$, where $f$ is computable and $g$ is not computable. The following two statements are correct:

If $h(x) = g(f(x))$, then $h$ could be computable.

If $g(x) = h(f(x))$, then $h$ is not computable.

Well, 2 is clear I think, because we know that $g$ is not computable and $f$ is computable, so $h$ has to be not computable, otherwise $g$ would be computable.
But 1 is a big problem for me. If $f$ is computable and $g$ is not computable, how can $h$ be computable?

Suppose that $f(x) = 0$. Then $g(f(x))$ is computable for any function $g$, computable or not. This explains 1.
As for 2, the composition of two computable functions is computable, so if both $f$ and $h$ are computable, so is $g$. Since $f$ is computable and $g$ isn't, the only conclusion is that $h$ is not computable.


NP-completeness: Reduce to or reduce from? Very simple question, but a mistake I make often enough that I'd love to have a standard reference.

I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $P$, then showing that this solves another NP-Hard problem $Q$ in polynomial time.

Have I reduced $P$ to $Q$ or have I reduced $Q$ to $P$?

Since $Q$ is the problem of known hardness I've chosen, have I reduced from $Q$ or reduced to $Q$?

To show a new problem $X$ is hard, you reduce from a problem of known hardness to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$.

The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-SAT instance to an instance of $X$. Given an instance of 3-SAT, you transform it into an instance of $X$, apply the efficient algorithm for $X$, and thus have solved the 3-SAT instance.


Is everything in CS either a numeric method or a symbolic method? Or maybe also a combination of the two, but not something else, whether numeric, nor symbolic. Do they cover the whole field?

No. You could make a decent argument that every algorithm is in some sense a symbolic manipulation, though not in the sense normally used for symbolic computation - they are not explicitly algebraic, and more naturally find expression as logic and set theory (unsurprisingly). Taking the wider view of symbolic manipulation though, even numerical analysis is just symbolic calculation, it's only at the external semantic level that we recognise it as an approximation of what we actually want to do. The computer is still just pushing bits around.

However Computer Science extends beyond algorithms, even though they are central to CS. It includes complexity, computability, plus practical subfields like networking, machine intelligence, compiler and language design &c. which involve more than just designing algorithms.

Just to pick a few illustrations of this: designing a programming language is not a computation of any sort (the compiler is of course), but it is certainly computer science; the construction of a complexity reduction is not a computation (but the reduction itself is; the choice of processor layout in parallel computing is a choice made by the designer.


Algorithm to compute $n^{\log k}$ in $O(\log\log k)$ I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\log k$ in steps. Any ideas?

The idea is to use repeated squaring. Compute $n,n^2,n^4,\ldots n^{\log k}$. To compute $n^{2^i}$ use the fact that $n^{2^i} = n^{2^{i-1}} n^{2^{i-1}}$. Note that the answer of $n^{2^{i-1}}$ will be known in the $i$th iteration.


Density of uniform distribution over two disjoint squares A probability distribution $P$ over $X \times \{0, 1\}$. $P$ can be defined in term of its marginal distribution over $X$ , which we will denote by $P_X$ and the conditional labeling distribution, which is defined by the regression function
$$
\mu(x) = P_{
(x,y) \sim P}
[y = 1 \mid x]
$$
Consider a 2-dimensional Euclidean domain, that is $X = \mathbb R^2$, and the
following process of data generation: The marginal distribution over $X$ is uniform over two square areas $[1, 2] \times [1, 2] \cup [3, 4] \times [1.5, 2.5]$. Points in the first
square $Q_1 = [1, 2] \times [1, 2]$ are labeled 0 (blue) and points in the second square
$Q_2 = [3, 4] \times [1.5, 2.5]$ are labeled 1 (red).

Describe the density function of $P_X$, and the regression function, Bayes predictor and Bayes risk of $P$.
In the image, I have defined the Probability density function. I am having trouble in figuring out the pdf of this function in 2 dimensional space.

The density $p_R$ of the uniform distribution over a rectangle $R$ is given by $p_R(x) = 0$ if $x \notin R$, and $p_R(x) = 1/\mathit{area}(R)$ otherwise. Indeed, up to scaling the distribution must have this form, and the choice $1/\mathit{area}(R)$ ensures that $p_R$ is a distribution.
In your case, you have a mixture of two such distributions: with probability $1/2$ you take a uniform point in $[1,2] \times [1,2]$, and with probability $1/2$ you take a uniform point in $[3,4] \times [1.5,2.5]$. The density function of the mixture is the average of the density functions of the individual distributions.


Are those definitions of universal hash family equivalent? I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.

Definition 1:

$H$ is a universal hash family if and only if $$\mathbb{Pr_{h \in H}}[h(k) = h(l)] = 1/m$$

where $k \neq l$ and $k,l\in Key$ and $m$ is the Size of the Hashtable

Definition 2:

The same as above just substitute the equals sign with a less or equal sign.

Well, i think those definitions are equivalent, because i think the probability for a collision can't possibly be strictly less than 1/m or am i missing something?

P.S.
I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

There are still families with collision probability less than $1/m$, e.g., with three keys and two buckets,

$$\{(2, 1, 1), (1, 2, 1), (1, 1, 2)\}$$

has collision probability $1/3 < 1/2$, and there are other counterexamples for all other parameter settings. The most plausible path to your intuition being true would be if $h(k)$ and $h(l)$ were necessarily independent, but they're not and can in fact be anti-correlated.


Are non-regular languages decidable? Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?

Context-free languages are not regular but decidable; on the other hand recursively enumerable languages are not regular and only semi-decidable. So sadly only knowing about the non-regularity of a language does not help with determining its decidability.


Is this formal grammar context-free (CFG) but not context-sensitive (CSG)? I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$

Now, we see, the production rules $A \rightarrow \varepsilon$ and  $B \rightarrow \varepsilon$ implies that this grammar is not context-sensitiv ($CSG$). But on the other hand, we see this grammar satisfies the conditions for a context-free ($CFG$) grammar, because every production rule has just one NON-terminal on the left side.

We know, according to the Chomsky hierarchy, a contest-free grammar imples a contest-sensitive grammar: $CFG \implies CSG$

Now i am confused, is my grammar context-free or it is not, even if it satisfies the conditions? Can it be $CFG$ without being $CSG$?

Context-free languages are context-sensitive languages; therefore, if there's a valid CFG for a language, then there is a valid CSG for the same language. Depending on how you define CFGs and CSGs, it's possible that a CFG may not count as a CSG. It's quite often the case that CSGs aren't CFGs, even if the CSG generates a context-free language. Basically, even if CFG does not imply CSG, it is still true that CFL implies CSL. That's the confusion: the Chomsky hierarchy implies things about languages.

If your definition of a CSG says "No ϵ  transitions", you're right. If it says "The only ϵ  transition can be S→ϵ , then you are right. If it doesn't say something specifically excluding α→ϵ , then you're wrong. It's a matter of how you define what consistutes a valid CSG, which sounds obvious, and in fact is.


Good way to describe co-RE (co-recursively enumerable)? I get that R is a set of languages that are decidable by a Turing Machines

And that RE is a set of languages that a each language can be recognized by a TM, that is the machine will halt when given a word from that language and loop otherwise.

But I can't wrap my head around co-RE.  Is there a good way to describe it? A good example to convey what it really means?

The class ${\sf coRE}$ contains all languages whose complement is in ${\sf RE}$. Put differently:

A language $L$ is in ${\sf RE}$ if there exists a Turing machine that can check if a requested word $w$ is contained in $L$  for every word $w\in L$. The machine always tells the truth but it may cycle on inputs $w\not\in L$.
A language $L$ is in ${\sf coRE}$ if there exists a Turing machine that can check if a requested word $w$ is not contained in $L$  for every word  $w\not\in L$. The machine always tells the truth but it may cycle on inputs $w\in L$.

An example:
The language $\{ \langle M,w \rangle \mid \text{$M$ cycles on input $w$}\}$ is in ${\sf coRE}$. Just take a Turing machine that simulates $M$ on $w$ and rejects, whenever the simulation stops.


How can memory size be 1M x 16? 1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16? Or can there? Wondering about this for a question we were given..

It seems that a bunch of different things are being conflated here:

Bits in an addressable memory location - 16 in this example.
Addressable memory locations - 1M = 2^20 in this example.
CPU word size

These can all be the same, or they can be entirely different. I will try to explain the differences:

1 - Bits in an addressable word. This can be ANYTHING. Typically this will be the same as the CPU word size - e.g., 32-bits for a 32-bit processor. However, it can be larger (e.g., direct access to a "double word") or smaller (e.g., individual byte access for a CPU that has a 16-bit or larger word size). On some CPUs there will be different instructions that use different size operands and addressing schemes - e.g., floating point instructions might work only on 32-bit ("single word") or 64-bit ("double word") memory locations but other instructions might work with individual bytes. In some designs, every byte can be addressed and accessed directly but 16-bit words only on even addresses (or 32-bit only on addresses divisible by 4).

2 - Addressable memory locations. Historically this was often double the addressable memory location size. For example, a typical 8-bit CPU such as the Z80 or 6502 could directly address 64k = 2^16 memory locations. However, there are quite a few variations. One significant one is a segmented memory addressing scheme such as that used by the 8086 family. This is one method of expanding the total addressable memory while keeping the addresses directly used by most instructions to a smaller size (16-bit in the case of the 8086). While there is some logic to keeping the address size (=# of addressable memory locations) the same as the CPU word size, in many (most?) CPU architectures that was simply not practical in many cases until we arrived at the era of affordable 64-bit CPUs.

3 - CPU word size. The CPU word size normally refers to the standard chunks of memory operated on and produced as results by individual CPU instructions. Another way of looking at it is the register size. However, there have been exceptions here as well. For example, the 8-bit 8080 has 7 8-bit registers and 2 16-bit registers (SP and PC - both needed to be 16-bit to match the memory address size) and some of the 8-bit registers could be used in pairs for operations that really operated on 16 bit values. Similarly, many 16-bit CPUs have some instructions that operate on 32-bit quantities either for floating point arithmetic or again for memory addressing.

Now that I've rambled on a bit (pun intended), back to the original question: 1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16?
A few possibilities come to mind:

16-bit CPU with memory locations 16-bits wide and a 20-bit segmented architecture like the 8086. (But not actually the 8086 as the 8086 address space was 1M x 8)
16-bit CPU with a 20-bit or larger (typically 31-bit or 32-bit) total word-addressable memory with the 1M being just a small portion of the potential addressable memory for that particular CPU.
16-bit CPU with 21-bit or larger (typically 31-bit or 32-bit) total byte-addressable memory with the 1M just being a small portion of the potential addressable memory for that particular CPU.
32-bit CPU with memory addressable in 16-bit words (i.e., 1/2 the native CPU word size) for better performance with instructions that don't need 32-bit words.

In case it isn't already clear, the CPU word size historically directly translated to the number of pins available for reading/writing memory. So an 8-bit CPU could interface with memory 8-bits at a time and a 16-bit CPU 16-bits at a time. That all changed famously with the 8088 which internally was a 16-bit CPU but externally only 8-bits. So while the 8086 could directly use 16-bit wide memory like the example 1M x 16, the 8088 could not. That difference gives the 8088 performance that is in some ways closer to an 8-bit CPU than a 16-bit CPU.


How many thresholds and distance matrix are in Eigenface? I edited my question trying to make it as short and precise.

I am developing a prototype of a facial recognition system for my Graduation Project. I use Eigenface and my main source is the document Turk and Pentland. It is available here: http://www.face-rec.org/algorithms/PCA/jcn.pdf.

My doubts focus on step 4 and 5.

I can not correctly interpret the number of thresholds: If two types of thresholds, or only one (Notice that the text speaks of two types but uses the same symbol). And again, my question is whether this (or these) threshold(s) is unique and global for all person or if each person has their own default.

I understand the steps to be calculated until an matrix O() of classes with weights or weighted. So this matrix O() is of dimension M'x P. Since M' equal to the amount of eigenfaces chosen and P the number of people.

What follows and confuses me. He speaks of two distances: the distance of a class against another, and also from a distance of one face to another. I call it D1 and D2 respectively. NOTE: In the training set there are M images in total, with F = M / P the number of images per person.

I understand that threshold(s) should be chosen empirically. But there must be a way to approximate. I was initially designing a matrix of distances D1() of dimension PxP. Where the row vector D(i) has the distances from the vector average class O(i) to each O(j), j = 1..P. Ie a "all vs all."

Until I came here, and what follows depends on whether I should actually choose a single global threshold for all. Or if I should be chosen for each individual value. Also not if they are 2 types: one for distance classes, and one for distance faces.

I have a theory as could proceed but not so supported by the concepts of Turk:

Stage Pre-Test:

Gender two matrices of distances D1 and D2: In D1 would be stored distances between classes, and in D2 distances between faces. This basis of the matrices W and A respectively.

Then, as indeed in the training set are P people, taking the F vectors columns D1 for each person and estimate a threshold T1 was in range [Min, Max]. Thus I will have a T1(i), i = 1..P

Separately have a T2 based on the range [Min, Max] out of all the matrix D2. This define is a face or not.

Step Test:

Buid a test set of image with a 1 image for each known person Itest = {Itest(1) ... Itest(P)}

For every image Itest(i) test:

Calculate the space face Atest = Itest - Imean

Calculate the weight vector Otest = UT * Atest

Calculating distances:

dist1(j) = distance(Otest, O (j)), j = 1..P

Af = project(Otest, U)

dist2 = distance(Atest, Af)

Evaluate recognition:

MinDist = Min(dist1)

For each j = 1..P

If dist2 > T2 then "not is face" else:

If MinDist <= T1(j) then "Subject identified as j" else "subject unidentified"

Then I take account of TFA and TFR and repeat the test process with different threshold values until I find the best approach gives to each person.

Already defined thresholds can put the system into operation unknown images. The algorithm is similar to the test.

I know I get out of "script" of the official documentation but at least this reasoning is the most logical place my head. I wondered if I could give guidance.

EDIT:

i No more to say that has not already been said and that may help clarify things.

Could anyone tell me if I'm okay tackled with my "theory"? I'm moving into my project, and if this is not the right way would appreciate some guidance and does not work and you wrong.

I'll begin with an apology since I will probably not answer your question as you expect (mostly because I don't understand exactly what you are asking).

Let's recap the process of face recognition using Eigenfaces.

take each image of $d_1$ by $d_2$ and treat it as a $d_1\cdot d_2$ vector (images should be in greyscale).
compute the mean of the vectors in hand, i.e. if you have m images, $X_{mean}=\frac{1}{m}\sum_{i=1}^mX_i$ and move your samples such that the a-prior mean is is zero, (this is an important step that is commonly forgotten).
compute the covariance matrix, $X^TX$. I assume in your scenario $d_1\cdot d_2>>m$, so you obtain the same information by finding $XX^T$ eigenvalues, this could improve your running time significantly.
project the $m$ images over the $p$ eigenvectors corresponding to the largest eigenvalues.
Given a new image, project it using the matrix $[u_1,...,u_p]$ and run K-Nearest-Neighbour (it should be more than sufficient for your purpose).

I think your original question is regarding the classification process after you have projected the images over the principal components.
I the algorithm above, I suggest using KNN.

A few notes:

Eigenfaces don't work so well in reality, you must use images with very similar orientation, otherwise you won't achieve good results.
How to choose the k in the nearest neighbour algorithm? it depends on the number of training examples you have, obviously, there is no point of choosing k to be larger then the number of examples per person.
regarding point 3 above, $X^TX\in M_{(d_1\cdot d_2)\ x\ (d_1\cdot d_2)}, XX^T\in M_{mxm}$, so if your images are over 100 by 100, it's practically a must.
a couple of useful links:

http://docs.opencv.org/modules/contrib/doc/facerec/facerec_tutorial.html
http://vision.ucsd.edu/content/yale-face-database

Good Luck!

Addition:

http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
After obtaining the first p Eigenfaces (which are the first p eigenvectors of $X^TX$), you have a matrix $O\in M_{(d_1\cdot d_2)\cdot p}$, given a new image $x\in \mathbb{R}^{d_1\cdot d_2}$, project $O^Tx$, this is a vector in $\mathbb{R}^p$.
Now you have your samples in $\mathbb{R}^p$, your original training samples, and a new image that was projected over $O$, you know want to ask yourself how to classify the new image, one way is to decide by finding the closest vector using $L_2$ or $L_1$ this is the same as using KNN with k=1.
I suggest you read about KNN from the link above.

to sum it up:

compute the projection matrix $O$
project your training data $z_i=O^Tx_i$.
given a new sample, $\overline{x}$, compute $\overline{z}=O^T\cdot\overline{x}$
now you have vectors in $\mathbb{R}^p$, you run the KNN which is an iterative way to find the k closest vectors, and classify your new vector as the majority of the k vectors.


Generalised 3SUM (k-SUM) problem? The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.

It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.

So I was wondering if this would apply to the generalised problem: Find integers $a_i$ for $i \in [1..k]$ in a set $S$ of size $n$ such that $\sum_{i \in [1..k]} a_i = 0$.

I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?

$k$-SUM can be solved more quickly as follows.

For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements.  Check whether $S$ contains both some number $x$ and its negation $-x$.  The algorithm runs in $O(n^{k/2}\log n)$ time.
For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements.  For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$.  (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.)  The algorithm runs in $O(n^{(k+1)/2})$ time.

Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation.  For more details, see:

Nir Ailon and Bernard Chazelle.  Lower bounds for linear degeneracy testing.  JACM 2005.
Jeff Erickson.  Lower bounds for linear satisfiability problems.  CJTCS 1999.


Fastest algorithm to find whether a list contains a word? Given an unordered list of words, what's quickest way to test whether a certain word is in that list?

I can't think of another way to do this other than just going through each element in the list and checking whether it's the word I want.

If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do.

If you want to carry out multiple tests (but you do not know all the test items in advance) then it is worth the initial overhead of sorting the list, creating a hash table, or creating a search tree.


For dynamic programming problems, how do we know the subproblems will share subproblems? So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:
Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.
So my question is that how do we know when in a problem if we apply the divide-and-conquer approach, we will get overlapping sub-problems?
Eg:
Let's take the famous problem from Cormen.

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting, and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Here, how do we know that subproblems will overlap?

The answer is - you don't.  Not in advance.  There are no guarantees and there is no silver bullet process.
Instead, dynamic programming is a way of thinking about a problem, a framework for approaching a problem.  You typically won't know whether that approach will be successful or not in advance.
Dynamic programming basically amounts to finding a recursive algorithm for the problem, and then speeding it up with memoization.  You'll have to try different recursive algorithms (different ways of decomposing into subproblems) and see, for each candidate, if it has the properties that are needed to apply these ideas successfully.  You usually won't know in advance whether any particular decomposition into subproblems will be successful.   You might be able to tell whether those subproblems will be "overlapping", but not whether it'll lead to a useful dynamic programming algorithm.  It's partly an art, where experience helps give you some intuitions for what kinds of subproblems might be useful in any particular situation.
I encourage reading What is dynamic programming about?, When can I use dynamic programming to reduce the time complexity of my recursive algorithm?, and Deciding on Sub-Problems for Dynamic Programming to get a sense of this perspective.
Personal opinion: I personally don't find "overlapping subproblems" as a very helpful way to think about dynamic programming.  I encourage you to use whatever works for you, but that one never worked very well for me.  If you want to understand it, think about algorithms that work on an array $A[1..n]$.  Divide-and-conquer will work on some subarrays, say $A[1..n/2],A[n/2+1..n],\ldots$, but no pair of those have a partial overlap.  Dynamic programming may work on all subarrays, say $A[i..j]$ for all $i<j$, and there are pairs of those that partly overlap (e.g., $A[3..5]$ overlaps with $A[4..9]$).  That's what is meant by "overlapping subproblems", and that is one distinction between dynamic programming vs divide-and-conquer.  That said, I don't find that a very helpful characterization, personally -- and especially, I don't find it helpful at designing an algorithm (it might be more helpful once I already have an algorithm and am wondering whether I should call it divide-and-conquer vs dynamic programming, but at that point I often don't care too much what we call it).


Why is the time complexity of insertion sort not brought down even if we use binary search for the comparisons? There are two factors that decide the running time of the insertion sort algorithm:
the number of comparisons, and the number of movements.
In the case of number of comparisons, the sorted part (left side of $j$) of the array is searched linearly for the right place of the $j^{th}$ element. If instead, we use a binary search, then the time complexity of finding a place for the $j^{th}$ element comes down from $\operatorname{O}(n)$ to $\operatorname{O}(\log n)$. So, for all the $n$ elements, the time complexity for comparisons becomes $\operatorname{O}(n \log n)$. Even so, the number of movements is still going to take $\operatorname{O}(n)$ time, and the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. Why is that?
Are any of my statements wrong assumptions?
Can a possible explanation be: the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. This is because to search an element (using binary search) it takes $\operatorname{O}(\log n)$ time, and to move the elements it takes $\operatorname{O}(n)$ time. Total cost is $\operatorname{O}(\log n)+\operatorname{O}(n)=\operatorname{O}(n)$ time. To do this for $n-1$ elements, it takes $n(n-1)=\operatorname{O}(n^2)$ time?

For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts.

Summing over $j$, you get

$$
\sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2)
$$

The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a linear amount of work per iteration. So the complexity does not change.


How to implement AO* algorithm? I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-heaps to implement the A* algorithm. In these cases, we do not need to construct the search tree explicitly.

But I can not find a simple data structure to simulate the searching process of the AO* algorithm. I would like to know if constructing the search tree explicitly is the only way to implement AO* algorithm? Can anybody provide me an efficient implementation?

Regarding this article every time you expand a node in the AO* algorithm you must go backwards to update all of its predecessors’ estimated cost.

When you use linear data structure to contain the nodes you must traverse the data elements sequentially and only one data element can be directly taken (stack, queue, priority queue …).

In AO* each time a node is taken for expansion based on its estimated cost the algorithm iterates over all of the nodes that are its predecessors(to update their estimated cost). That means that sometimes you should take element based on its estimated cost and sometimes based on its successor. There is no sequence order that can meet both of these conditions in the general case.
Probably there is a way to use "nested" linear data structures, but it should just imitate a tree structure, and it will be better to build the search tree instead.


What is the origin of the client server model? I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?

This is a good question.

It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then.

However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. The following paper seems to be the earliest hit:

Jay E. Israel et al. (1978): Separating Data From Function in a Distributed File System.

I did not find the full text of this paper. It seems that it was published in the Proceedings of the Second International Symposium on Operating Systems Theory and Practice, which was held in October 1978. A preview is available here; I am quoting the relevant part (emphasis mine):

  The distributed file system (DFS) is so named because it is implemented on a cooperating set of server computers which together create the illusion of a single, logical system. The other computers in the network that use the DFS for creating, destroying, and randomly accessing files are called its clients (we employ the term "user" to stand only for human users; programs that access the DFS are always called clients).

This looks like a good candidate of the first paper that uses the client-server terminology. Note the way it is written: the authors clearly assume that the reader is familiar with the term "server", but they are here introducing the unfamiliar term "client"—so strange that they have to justify its use.

I checked various resources, including the digital libraries of IEEE and ACM, and I was not able to find any hits that predate 1978. However, already in 1979 there was at least one paper that is boldly using the new term "client" in its title. Unsurprisingly, it is citing Israel et al. (1978).

OED knows the term, but again the earliest use is by Isreal et al.

Edit: Here are some further comments on the term "server". Looking at various papers written in 1960s, it seems that the term "server" was primarily used in the context of queueing theory; there a "server" can be any kind of entity that provides some service.

Whenever a "server computer" was mentioned in computer science papers written in 1960s, it was typically related to the applications of queueing theory in the context of computer systems. Perhaps this is the origin of the term in our field?

I am not sure what is the first instance of a "server" used in this sense without any direct connection to queueing theory.

However, RFC 5 from 1969 that I mentioned above seems to be already using the term "server" in the context of client-server systems and computer networks, without any explicit references to queueing theory. Of course the term "client" was not introduced yet, so they used the words "server-host" and "user-host".


Does a Haskell program count as an inductive proof? Is the following statement from [1] true?

"Since recursion is the main computational technique, a terminating pure Haskell program counts as an inductive proof of a theorem."

My intuition is that inductive proofs require a base case, assume the hypothesis case for k, prove induction step fork+1.
I am not clear on how these steps occur in the execution of a program (function?). Also, what logic is employed in such a proof?

Regards,
Patrick Browne

[1] http://ebooks.iospress.com/volumearticle/44257

Thanks for your very helpful answers.

Would it be fair to say that the answer may be morally yes [1], but technically perhaps no [2].

Below are two Haskell programs together with what I consider to be equational proofs (not inductive) that they evaluate to a desired ground term.
The first program is not recursive. So does the quote in my original posting include non-recursive programs?

    -- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
proveZ = z == 4
-- Equational Proof
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
proveSize =  size (Add (Add Empty 1) 2) == 2
-- Equational Proof
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)

The motivation for my original question is that I wish to understand the relationship between the evaluation of a Haskell program and the application of equational logic to the same Haskell program. While Haskell produces the correct answer, as would a non-functional language, is the computation a proof in equational logic?  I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a).
In summary is my yes/no opinion reasonable?

[1] Fast and Loose Reasoning is Morally Correct:
 http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf

[2] Formulating Haskell: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.1399

The statement is not true as stated. Even if we imagine a Haskell-like language where all functions terminate and values are non-bottom, only some programs would correspond to inductive proofs (as opposed to proofs not using induction), but it would be the ones that (directly or indirectly) use recursion. That said, what they are doing induction over may not at all be obvious. (For the OP: every inductive type gives rise to a notion of structural induction with "mathematical induction" just being structural induction over the naturals.) Many patterns of recursion in practical programs, e.g. quicksort, do not correspond to a direct structural induction over their inputs.

For real Haskell, for just about any program proving that it terminates for all inputs requires very strong restrictions on those inputs: all values must be fully defined and all passed in functions must terminate on at least the inputs exercised by the current program. The latter isn't checkable in general, but what we can do instead is reduce a value that stands for a putative proof to normal form, and if we succeed then we have a real proof. Unfortunately, Haskell doesn't evaluate things to normal form but only to weak head normal form. For some types we can force the weak head normal form of one expression to correspond to normal forms via rnf, but we can't do this for functions in general.

Even without restrictions, programs in Haskell correspond to proofs in some logic, albeit an inconsistent one. This leads to another aspect that they conveniently didn't elaborate on. They say that certain Haskell programs correspond to proofs of theorems, but they don't say what theorems you can state! Haskell (particularly with higher-rank polymorphism) is closely related to the polymorphic lambda calculus and that corresponds to intuitionistic, second-order propositional logic1 (SOPL) (not to be confused with second-order predicate logic which is usually what "second-order logic" refers to). While SOPL is uninteresting in the classical case, it turns out to be pretty powerful in the intuitionistic case, capable of embedding intuitionistic first-order predicate logic. The embedding is non-obvious and even with it you would not be able to prove something like the Fundamental Theorem of Arithmetic. In practice, most programs correspond to completely trivial theorems or (intutionistic) propositional tautologies.

From my (admittedly very brief) skimming of the paper, it seems that they are more interested in the Prolog-like reasoning the type class system enables than leveraging the propositions-as-types correspondence. So their comments seem to be a bit of a non sequitur anyway.

1 See Chapter 12.


Optimal flow in a network with non-constant edges' weights I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather different so i need an advice.

Suppose that we have a weighted directed graph with two (possibly the same) vertices designated as "source" (S) and "target" (T). We can imagine that vertices represent the currencies and edges are conversion options. There is some initial amount of money in vertex S and it has to be converted to vertex T in such way that the resulting sum is maximum possible.

Conversion can be done in parts so if there is some sum S at vertex V and there are several edges coming from V then we can send different amounts of money along these edges (i.e. we are not obliged to use only one edge or to divide the sum in equal parts or to use multiples of some fixed lot etc.). We are also not obliged to convert total sum. It can be the case that the best option is to convert some part of it.

Now comes the trickiest part. Each edge's weight depends on amount of money that must be transported through an edge. For each edge E there is some function F(E) that receives amount of money entering the edge and returns amount of money leaving the edge. We can assume that ratio of output/input gets smaller when input gets bigger.

Thank you very much for any ideas. Any help will be highly appreciated.

Your problem is a generalization of the Longest Path problem, which is NP-hard.  If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once.  At that point, you are just looking for the longest path.

Your generalization, allowing partial conversions, non-constant functions, etc. cannot be easier than that.


The trick used in the proof of the doubly exponential complexity of Presburger arithmetics I posted this on MathUnderflow but got no answers, so thought I'd try it here,

I am reading Rabin and Fischer's old paper [will post a link when possible] where among other things, the doubly exponential complexity of Presburger arithmetics is proven.

The proof relies on the existence of a formula $I_{n}(x)$ informally asserting "$x < 2^{2^{kx+1}}$" with $|I_{n}| \in O(n)$. Though the construction of this formula is not given in the paper, which was a surprise to me considering that it is presumably highly nontrivial, given that bound and the fact that we only have addition at our disposal!¹

I later learned that the construction of this formula relies on a "trick", previously discovered by Fischer, and independently by Volker Strassen, but I have not managed to track down a paper describing this trick in detail!

So if anyone knows about the paper I am talking about and can either point me in its direction or even describe the trick to me...

This post from Lipton's blog contains a link to the paper as well as mentions [and provides a rough, unfortunately insufficient for me, sketch of] said trick, BTW.

¹ I know that this is a vague description. Though, a sufficiently detailed description would be way too long for a SX post, so I just hope that someone that already knows about the paper in question - and thus can make do with that brief sketch - bumps into this and is able to help me.

Martin's comment (and Yuval's follow up) gives the reference which explains the construction in some detail.

I'll elaborate a bit because I think it's a gorgeous proof: basically it's performing the "usual" proof of undecidability of PA (arithmetic with addition and multiplication), but relativized to $2^{2^{c\cdot n}}$! That is, there is a (short) formula which expresses multiplication up to that number, i.e. a formula $M_n(x,y,z)$ such that
$$M_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x< 2^{2^n} $$

Now you build $M_n$ by induction on $n$, with a crucial trick that is reminiscent of the Karatsuba algorithm for multiplying binary numbers or certain tricks for matrix multiplication:

In the definition for $M_{n+1}(x,y,z)$ you end up with a conjunction of the form
$$M_{n}(x_1,y_1,z_1)\wedge M_{n}(x_2,y_2,z_2)\wedge M_{n}(x_3,y_3,z_3)$$

But you can replace this with
$$ \forall u v w,(u=x_1\wedge v=y_1\wedge w=z_1)\vee(u=x_2\wedge v=y_2\wedge w=z_2)\vee(u=x_3\wedge v=y_3\wedge w=z_3)\Rightarrow M_n(u,v,w)$$

This trick allows a linear increase in size instead of an exponential one (as a function of $n$).

There's a couple of other tricks involved, but this is the main one. The internals of the recursion are important, of course, but the similarity to the Karatsuba trick is really quite striking.


Sum of heights in a complete binary tree (induction) I need to prove the following statement using induction on the number of nodes in the tree:

The sum of heights of a complete binary tree is $\theta(n)$.

Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)≤c_1n$ for some $c_1$. But, I couldn't show the lower bound ($sum(n)≥c_2n$ for some $c_2$).

The base case is a complete binary tree, with 3 nodes in the height of 1.

The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$

I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree.

Can someone explain how to complete this step?

A complete binary tree of height $h$ has exactly $2^{h-k}$ nodes of height $k$ for $k=0,\ldots,h$, and $n=2^0+\cdots+2^h = 2^{h+1}-1$ nodes in total. The total sum of heights is thus
$$
\sum_{k=0}^h 2^{h-k}k = 2^h \sum_{k=0}^h \frac{k}{2^k} = 2^h \left(2 - \frac{h+2}{2^h}\right) = 2^{h+1} - (h+2) = n - \log_2 (n+1).
$$

The answer below refers to full binary trees.

I'm assuming the following definition of height. The height of a tree is the length of the longest root-to-leaf path. The height of a vertex in a tree is the height of the subtree rooted at this vertex. Denote the height of a tree $T$ by $h(T)$ and the sum of all heights by $S(T)$.

Here are two proofs for the lower bound. The first proof is by induction on $n$. We prove that for all $n \geq 3$, the sum of heights is at least $n/3$. The base case is clear since there is only one complete binary tree on $3$ vertices, and the sum of heights is $1$. Now take a tree $T$ with $n$ leaves, and consider the two subtrees $T_1,T_2$ rooted at the children of the root, containing $n_1,n_2$ vertices, respectively. Suppose first that $n_1,n_2 \geq 3$. Then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + n_1/3 + n_2/3 = n/3 + 2/3 > n/3.
$$
If (say) $n_2 = 1$ then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + (n-2)/3 = n/3 + 1/3 > n/3.
$$
This completes the proof.

The second proof proceeds by bounding the number of leaves in a complete binary tree. Order the children of every node so that it has a left child and a right child. Exactly half of the leaves are left children. Each left child has a different parent, and in particular each left leaf has a different parent. So a tree $T$ with $f$ leaves has at least $f/2$ non-leaves. In particular, the total number of vertices $n$ satisfies $n \geq f + f/2 = (3/2)f$, so that $(2/3)n \geq f$ and so $n-f \geq n/3$. We conclude that
$S(T) \geq n-f \geq n/3$.

The upper bound can be proved along the lines of the second proof. Suppose that there are $f$ leaves. Thus there are at most $f/2$ vertices at height $1$, at most $f/4$ vertices at height $2$, and generally speaking, at most $f/2^h$ vertices at height $h$. Therefore the total height of vertices is at most
$$
\sum_{h=0}^\infty h \frac{f}{2^h} = f \sum_{h=0}^\infty \frac{h}{2^h} = 2f \leq 2n.
$$


Intersection/Union of Language of PDA, CFG and NFA I stumbled across the following question.

Say I have given an arbitrary PDA $P$, NFA $N$, and CFG $G$. My question is then if the following language ($L(P) \cap L(N)) \cup L(G)$ is context-free.

How can this be determined?

$L(P)$ and $L(G)$ are context-free; $L(N)$ is regular.  By standard closure properties, the intersection of a context-free language with a regular language is context-free, and the union of two context-free languages is context-free. Therefore, $L(P)\cap L(N)$ is some context-free language $C$ and $C\cup L(G)$ is context free.

The closure properties can be proven without reference to the specific language by using the fact that every context-free language is accepted by a PDA or defined by a context-free grammar.  For example, to show that the union of two context-free languages is context free, let those languages be defined by grammars $G_1$ and $G_2$ with start symbols $S_1$ and $S_2$. We can rename the non-terminals in $G_1$ and $G_2$ so that no non-terminal appears in both grammars. Now form the a grammar $G$ with start symbol $S$ consisting of the rule $S\to S_1|S_2$, all the rules of $G_1$ and all the rules of&nbsp:$G_2$.  You should be able to convince yourself that $L(G) = L(G_1)\cup L(G_2)$. But proving this didn't require us to know anything about what rules are contained in the grammars.


Common name for a group of commands which break the linear structure of the program I'm looking for a name of a group of all commands which are break the linear structure of the program.

In C PL, they are: goto,return,break,continue. C++ also contains throw.

Perl has last,next,return.

Is there a common name for those groups of commands? Where can I read about those kind of commands?

These are control flow statements. There is a quite a large list of them on their Wikipedia page.


Minimally extend a tree such that there are no bridges in the new graph We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.

An edge $e$ is a bridge if the graph with that edge removed is no longer connected.

For example, here is a tree with 8 nodes

1 2
2 3
3 4
4 5
3 6
3 7
3 8
At least three edges should be added. For example: (1, 6), (5, 7), (8,4)

In very small graphs we can brute force all possible new edges. However, this is too slow for bigger trees. I tried making some observations but I couldn't find anything that could solve the problem.

This problem is the task "NET" from Baltic Olympiad in Informatics 2015.

Start by proving the following statement:

Let $G=(V,E)$ be an undirected graph. There are no $\mathrm{bridges}$ if and only if there are two edge disjoint spanning trees of $G$.

Proof:

Suppose there are two edge disjoint spanning trees, $T_1, T_2$ of $G$.
Now we remove an arbitrary edge. If it belongs to neither $T_1$, or $T_2$, we're done. If it belongs to $T_1$, it is therefore not in $T_2 $ (symmetrical for $T_2$)  $\Rightarrow$ $G$ is still connected $\Rightarrow$ there are no $\mathrm{bridges}$ in $G$.

Suppose there are no two edge disjoint spanning trees. Then there is at least one cut $C^*$ of $G$ s.t $C^*=\{A, \bar{A}\}$ and $\delta(C^*) \leq 1$. Otherwise it is easy to constructively show there are two spanning trees.
Let $e$ denote the edge between $A$ and $\bar{A}$. Since $e$ is the only edge connecting the two subsets, by removing it, $G$ is separated into two unconnected componenets, therefore $e$ is a $\mathrm{bridge}$

If you can add any edge you want, simply extend $G$ s.t there are two edge disjoint spanning trees. If you start from a tree, it means you have exactly $n-1$ edges, and to create another distinct spanning tree you would have at least $n-1$ additional edges.
If you can't add any edge you want, see http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf by Tarjan on disjoint spanning trees (with algorithm)