Non-deterministic Turing machine to solve graph colouring Consider the graph coloring problem: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise.

I am able to design a deterministic Turing machine that would solve it with a greedy approach trying the different combinations of coloring with the $n$ colors. I think this takes exponential time although I'm not sure how to proof it.

However, I am not able to conceive a nondeterministic Turing machine that would do so. Can someone guide me designing an algorithm for this machine?

The algorithm would be as follows:

Go through each vertex and "guess" a coloring using non-determinism. This takes time $O(V\log n)$, since this is the time it takes to write all the colors.
Check that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts.

By definition, a non-deterministic Turing machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.


Indistinguishability of exponentially close distributions Let $D_{1}$ and $D_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial number of samples from any one of the distributions, the task is to output $1$ if the samples come from the first distribution and $0$ if they come from the second one. I am trying to show that no polynomial-time algorithm (even with bounded error) can do this task.
Intuitively, it should be very clear that two distributions that are exponentially close are indistinguishable. But how do I formalize the intuition?

Here is the key. Let $A \otimes B$ be the distribution corresponding to a sample from $A$ and an independent sample from $B$, and denote total variation distance by $d_{TV}$. Then
$$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$
We can see this using the $L_1$ formula for $d_{TV}$:
\begin{align}
d_{TV}(A_1\otimes A_2,B_1\otimes B_2) &=
\frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &\leq
\frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[A_2=x_2]| \\ &+
\frac{1}{2} \sum_{x_1,x_2} |\Pr[B_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &=
\frac{1}{2} \sum_{x_2} \Pr[A_2=x_2] \sum_{x_1} |\Pr[A_1=x_1] - \Pr[B_1=x_1]| \\ &+
\frac{1}{2} \sum_{x_1} \Pr[B_1=x_1] \sum_{x_2} |\Pr[A_2=x_2] - \Pr[B_2=x_2]| \\ &=
\sum_{x_2} \Pr[A_2=x_2] d_{TV}(A_1,B_1) + \sum_{x_1} \Pr[B_1=x_1] d_{TV}(A_2,B_2) \\ &=
d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2).
\end{align}
Now let $D^{\otimes n}$ denote $n$ independent samples from $D$. The above inequality shows that
$$
d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).
$$
Let $E$ be the event that your algorithm outputs "$D_1$". The definition of $d_{TV}$ guarantees that
$$
|\Pr_{D_1^{\otimes m}}[E] - \Pr_{D_2^{\otimes m}}[E]| \leq d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).
$$
Here $\Pr_D$ denotes that the samples in the algorithm are generated from the distribution $D$.
We deduce that an algorithm with advantage $\delta$ must use at least $\delta/d_{TV}(D_1,D_2)$ samples.


Is the 2nd parity bit in RAID 6 a simple calculation? I'm trying to understand how the 2nd parity bit or byte is set in RAID 6. I'm reading a paper by H. Peter Anvin, and it goes into Galois field algebra, which is somewhat new to me. Anyway, a rep from HP was trying to explain RAID 6 to me and she thought it was merely two XOR operations, one for the 1st parity bit and one for the 2nd.  This doesn't make sense to me, but since I'm still working through the paper I don't know if it reduces to something simple for RAID 6 as opposed to RAID n. It looks to me like the 2nd parity bit is quite a bit more complicated than the XOR based 1st parity bit. Is that true?

The general case is indeed a bit complicated.

However, in the case of 4 disks you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store 4 bits redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store.

We can represent the scheme as 4 x 4 tables. The first 2 bits of our data determine the row and the last 2 bits of our data determine the column.

Disk 1: Just store the first 2 bits. That is:

00 00 00 00
01 01 01 01
10 10 10 10
11 11 11 11

Disk 2: Just store the last 2 bits. That is:

00 01 10 11
00 01 10 11
00 01 10 11
00 01 10 11

So far so good. Given disk 1 + disk 2, we can recover our original data: disk 1 tells us the row (the first 2 bits of the original data) and disk 2 tells us the column (the last 2 bits of the original data).

Disk 3: This is what we do on RAID5, just XOR the bits:

00 01 10 11
01 00 11 10
10 11 00 01
11 10 01 00

Again, everything is still fine. You can recover the original data using disk 1 + disk 3 or disk 2 + disk 3. A key observation is that the lookup table for disk 3 forms a Latin square: all elements of each row are distinct, and all elements of each column are distinct. For example, if you know the data on disk 1, you know the right row, and then you can use the data on disk 3 to recover the column. Conversely, if you know the data on disk 2, you know the right column, and then you can use the data on disk 3 to recover the row.

Disk 4: Here we can use the following lookup table:

00 01 10 11
10 11 00 01
11 10 01 00
01 00 11 10

Don't worry how it is constructed; we do not really care about that. The crucial properties are:

The lookup tables of both disk 3 and disk 4 are Latin squares. Therefore if you know 1 + 3 or 1 + 4 or 2 + 3 or 2 + 4, you can recover both row and column (i.e., the original data).
The lookup tables of disk 3 and disk 4 form orthogonal Latin squares, which makes it possible to recover the data if we only have disks 3 + 4.

Let's elaborate on the second point. By concatenating the lookup tables of disk 3 and disk 4, we get this matrix:

0000 0101 1010 1111
0110 0011 1100 1001
1011 1110 0001 0100
1101 1000 0111 0010

Now note that each 4-bit string occurs in this table exactly once. That is, if we know what is stored on disks 3 + 4, we know where we are on this table. We know both the row and the column, and hence we can recover the original data.

If you insist on seeing the connection to Galois fields, consider the field $F = GF(2^2)$. Label the elements of the field with $F = \{0,1,x,x+1\}$; these correspond to 2-bit strings ($0$ ≈ 00, $1$ ≈ 01, $x$ ≈ 10, $x+1$ ≈ 11). Now any 4-bit string can be encode as a pair $(a,b)$, where $a,b \in F$.

A pair $(a,b)$ is now stored as follows:

Disk 1 stores $a$.
Disk 2 stores $b$.
Disk 3 stores $a+b$.
Disk 4 stores $xa+b$.

Now given, for example, just $p = a+b$ and $q = xa+b$, you can solve $a$ and $b$. Using the rule $2 \equiv 0$, you can find

$p + q = (xa+b) + (a+b) = (x+1)a + 2b \equiv (x+1)a$,
$p + xq = (xa+b) + x(a+b) = 2xa + (x+1)b \equiv (x+1)b$.

Then divide by $x+1$ to get $a$ and $b$, etc. But in the end, this approach gives you precisely the same lookup tables as what was presented above.


Closest Pair Algorithm I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example:
Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B
Then when we have a look at B,
we will link B to C
Next when we consider X,
we will link X to Y
Next when we consider C,
we will link C to D   ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time.  Not to mention it doesn't work.  What might be a better algorithm?

Here is what the current algorithm is:

for(i in list)
  while (i and j) is not linked
     increment j
  if j is not the end
     while ++j is not the end
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..?  Can anyone point me in the right direction please?

An alternative approach could be

Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$
Then you have two choices

Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.


Is it necessary to learn how to prove Mathematical theorems as a CS Student? I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:

  Problem 4. If a set, $A$, is finite, then $|A| < 2^{|A|} = |\cal P(A)|$, and so there is no surjection from set $A$ to its powerset. Show that this is still true if $A$ is infinite. Hint: Remember Russell's paradox and consider $\{x \in A \mid x \notin f(x)\}$ where $f$ is such a surjection.

My question is: am I expected to prove these math theorems and should I focus on my proving skills (because they are proving to be quite difficult for me at the moment)? Do they make me a better problem solver in later courses such as Data Structures and Algorithms?

There are several different ways to answer your question.

First, in the particular course you are taking now, part of the material is mathematical proofs. In order to succeed in this course, you need to be able to prove mathematical theorems. There are several reasons for this requirement:

Some more advanced classes also involve proving theorems.
The concept of proof and mathematical validity is important even if you don't expect to actively prove theorems. You need to understand the difference between a heuristic algorithm and an algorithm which is guaranteed to always work efficiently.
Programming is an abstract pursue, and requires a certain way of thought. Mathematics is one way to develop this way of thought, since it forces you to think in abstract terms.

Second, while more advance proofs do involve a lot of problem solving, in this particular problem you are handed out the solution, and your task is to convert the hint into a formal proof (in the sense of your class). At this stage of your class, you are not required to be able to create completely new proofs. Rather, the emphasis is on you understanding what is a mathematical proof and how it is written. Later on you might be given more creative tasks.

Third, the course you're taking will also teach you basic mathematical concepts that might be useful for you in the future. For example, one of the topics you are taught is propositional logic. You could encounter propositional logic in database theory, verification, and elsewhere. The only way to understand such an abstract concept is to play with it, and the way we play with concepts in mathematics is by proving simple statements.

Fourth, you mention that proving theorems is hard for you at the moment. This is why you're taking this class. One goal of the course is to teach you how to prove theorems. You might find it hard, but if the course goes slowly enough, you will eventually find it easy, and will have gained an invaluable skill. In a similar vein, you might have encountered the jump in difficulty level from high school to undergraduate studies. It requires some adjustment, but eventually you will gain the relevant studying skills.


Removing left-recursion in grammar while maintaining left-association of operator I have a problem with this exercise:

  Let G be the following ambiguous grammar for the λ-calculus:

  E → v | λv.E | EE | (E)

  where E is the single non-terminal symbol, λv.E represents abstraction w.r.t. the variable v in E, and EE represents application.

  Define an LL(1) grammar G′ such that L(G′) = L(G) and the ambiguity of G is resolved by imposing the following usual conventions:

  abstraction is right associative;
  application is left associative;
  application has higher priority than abstraction.

  Show the LL(1) parsing table for G′ and the parse tree obtained when parsing the string λv1. λv2. v1v2v1.

I eliminated ambiguity setting precedence and association, obtaining this grammar:

E -> EF | F
F -> λv.G | G
G -> (E) | v

which is not LL(1), since the production E -> EF is left recursive.
However, eliminating left recursion from that production I obtain:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

that does not comply with requirement 1.2.

I looked for a solution on the Internet, but it seems like it is not possible to eliminate left-recursion preserving left associativity.

However, this exercise appeared on the compilers exam some years ago, so there must be a correct answer.

Thank you for your help.

Compatibility of left associativity and LL(1) parsing

You just hit one of the major inconsistencies in the use of
context-free (CF) syntax. People want to choose grammars so that the
parse-tree will reflect the intended structure of the sentence,  close to its semantics, especially in the case
of non associative operators, such as application. This was pretty much the original intent of CF grammars in linguistics. But at the same
time they are constraining themselves to parsing technology that will
tolerate only some types of grammars.

Indeed, if the parse-tree is to reflect the left associativity of an
operator, then the grammar is necessarily left-recursive, since the
top application node in the parse-tree is necessarily adding the
rightmost term of non-parethesized successive applications.. So LL
parsing is out of the question. You are right.

There are two ways out of this. One is not to rely on the parser to
give the rigth "parse-tree" to be used for later stages of processing
(such as reducing the lambda expression, here). This lead to the
concept of Abstract Syntax Trees (AST) that can be built from the
parse-tree, but with a different structure.

The other solution is to use more general parsing Techniques that will
accept any CF grammar, and parse in accordance with it. General CF
parsers is a well developed technology  (and I do not cease to wonder
why LL remains so popular).

I have no idea what could be considered a proper answer to these
contradicting requirements.

What I would do is show they are contradicting requirements. Give a
first grammar that meets the associativity and priority constraints,
then transform the grammar into and LL(1) grammar for the parsing.

The fact that something appeared in a journal or on an exam is not a
total garantee that it is correct.  And I might be wrong too ... but I
did some checking, in addition to my own knowledge of the issue.

About this specific example

This being said, the first grammar you are suggesting does not seem
quite correct. It does not have a way of producing λu.λv.v .

One trick to know is to start with operators (here abstraction or
application) with the lowest priority (abstraction). It is the same for arithmetic
expressions.


Worst-case time algorithm?...which one is faster? Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why?

Is A more faster than B, for all $n>n_0$ if $g(h)=Ω(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=O(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=Θ(f(n)\log n)$?

If $g(n) = \Omega(f(n)\log n)$ then for large $n$, $g(n) \geq Cf(n)\log n$ (for some $C > 0$, and so algorithm $B$ takes more time than algorithm $A$ (in the worst case). In other words, algorithm $A$ is faster.

If $g(n) = O(f(n)\log n)$ then all we know is that for large $n$, $g(n) \leq Cf(n)\log n$; it could be that also $g(n) = \Omega(f(n)\log n)$, in which case algorithm $A$ is faster; or it could be that $g(n)$ is constant while $f(n) = n$ (for example), in which case algorithm $B$ is faster; and there are other possibilities.

If $g(n) = \Theta(f(n)\log n)$ then in particular $g(n) = \Omega(f(n)\log n)$, and so we revert to the first case.


Performing Transitive Reduction via neighbourhood and strongly connected components I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to access online.

The section is actually talking about a way to perform transitive closure for a graph randomly choosing a node and determining it's strongly connected component(SCC). Though there are further steps on what to do next for using the above to calculate transitive closure, I want to focus on the SCC determination and its role in transitive reduction.

SCC is found for a node v with the following formula,
Given a

graph $G$ and it's reverse graph $G'$
$N_G(v,\infty)$ indicates the neighbourhood of a node $v$ with radius $\infty$ i.e. all the nodes in the graph which can be reached by $v$

then the SCC with $v$ in it is given by $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$

Once you find the SCC, collapse it to a single composite node( composite in the sense that information on which original node was collapsed is still retained) and then modify all the previous edges to point in or out to this single composite node. One repeats the above until the graph size is small and then we use that graph(and the SCC info to find transitive closure). That is the context of this question.

What I don't understand is below. It is mentioned that

  We can iterate the above steps a fixed number of times. We can
  alternatively iterate until the graph becomes sufficiently small, or
  we could examine all nodes v in turn and not stop until each node is
  in an SCC by itself; i.e., NG(v, ∞) ∩ NG′ (v, ∞) = {v} for all
  remaining nodes v. If we make the latter choice, the resulting graph
  is called the transitive reduction of the original graph G.

I don't understand, for transitive reduction, how one can reduce to {v} without losing valid paths which can't be reduced.

P.S - My way of reducing the graph , is for every node v, delete $edge(v,a)$ if there exists $edge(n,a)$ for n in $N_G(v,\infty)$. There is 'currently' no need for SCC.

P.P.S - I am trying to implement this in Apache Spark for parallel computing. If you know of a more suitable algorithm, I would be happy if you could leave some pointers

EDIT: EXAMPLE 1
Consider a cycle with 4 nodes a,b,c,d.
For $v=a$, $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is ${a,b,c,d}$
According to the text, for transitive reduction, I have to reduce $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ to ${a}$.
If I take out any of the edges,e.g. from $d$ to $a$ so that  $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is  ${a}$ , it won't be a transitive reduction any more as there is no path from $d$ to $a$ as in the original path. Is my interpretation correct?

The standard definition of the transitive reduction of a graph $G$ says that we delete as many edges as possible, to retain the same reachability relationships.  However, the vertex set is unchanged: no vertices may be deleted.

The procedure you describe appears to involve deleting vertices.  Therefore, it does not appear to match the standard definition of transitive reduction.  (Perhaps your book has a non-standard definition of transitive reduction; if so, you might need to edit your question to ask about it.)

That said, a related construction does appear to correctly provide the transitive reduction.  In the related construction, instead of collapsing all vertices in a SCC into a single vertex, we replace the SCC with a directed cycle; then we apply transitive reduction to the dag of SCCs.  It is possible that your textbook actually uses the following procedure: (1) shrink each SCC to a single vertex, (2) apply transitive reduction to the resulting graph (which is the dag of SCCs), (3) now take each shrunken vertex and restore all of the original vertices and turn it into a directed cycle.  That should provide a correct algorithm for transitive reduction.  If that is what the book had in mind, your mistake was that you failed to perform step (3): you performed steps (1) and (2) and stopped there.  Of course, you have to perform the full procedure to get the full transitive reduction.

You might also be interested in the notion of a minimum equivalent graph, which involves deleting both edges and vertices; however, finding it in general is NP-hard.


Distribute a number of tasks into multiple days (scheduling) This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense, that the sum of taks' length is exactly the same as the sum of day's capacity, e.g. tasks of total length 150 must be scheduled into days of total capacity 150.

Resource sharing is not involved, but the ordering of task is important. Idealy, for every j > i, task Tj must be processed in the same day or later than task Ti. But then, the solution does not exist for the most cases. Thus, as few as possible tasks are allowed to be processed at most one day before a task with smaller index. If there is still no solution, as few as possible tasks are allowed to be processed at most two days before a task with smaller index, and so on.

This seems to me as an NP-hard problem. I have created an algorithm based on Binary Decision Diagrams, which performs an exhaustive search over all schedules but, of course, is quite limited by the size of the problem. I need a comparison with other solutions. Can you, please, suggest me some state-of-the-art approach to solve the given problem.

EDIT: I want to minimize how much the solution violates the natural ordering over how many times it violates the natural ordering.

Suppose that you have 200 tasks to be scheduled in 100 days. The capacity of each day is 4. Task 1 has capacity 1, task 200 has capacity 3, and tasks 2 to 199 have capacity 2.

In any solution, task 1 and task 200 have to be assigned to the same day. That means that there is a big violation of the ordering of the tasks. So even if you could solve your problem effectively, the best solution (which is indeed hard to compute) might still be very bad.

Even worse, even if we totally disregard the ordering constraint, there could still be no solution. Consider two days of capacity 7 and four tasks of length 2, 3, 3, 6, respectively. The total length is 14 = 2 $\times$ 7, yet there is no way to separate the tasks into two days of capacity 7.
This problem (in which the precedences are not taken into account) is called the Partition problem, so that is one keyword you might want to search for. Unfortunately,  checking if a solution to the Partition problem exists is a strongly NP-complete problem whenever you have 3 days or more.


Finding "fingerprint" sets Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all of the books in X's special subset. I think of this special subset as a unique "fingerprint" for X.

I would appreciate suggestions on an approach for finding such sets. (While this reads like a homework problem, it is related to a problem in my biology research that I am trying to solve.)

I assume you want the fingerprint to be as small as possible. Then this is the Hitting Set problem: For each person, make a list of all books liked by X but not by this person. Then, the goal is to select at least one book from each list. The problem is NP-hard, so you can't expect to find an algorithm that always solves it optimally in polynomial time. The greedy algorithm has a bad theoretical worst-case bound, but often works quite decent in practice. If you want to solve it optimally, an Integer Linear Programming solver should be able to solve instances of up to 1000 or maybe 10000 books. If you give more details on the size and structure of your instances, we could suggest other approaches.


Effective Procedures and P vs NP Problem If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two explicit queries:

If an effective procedure cannot be given which yields a solution, in what sense is the S actually a solution? Does this defy the formal definition of solution? I am assuming that an effective procedure is equivalent to a proof.
If there is no effective procedure to arrive at an accepted solution, this implies that solution is not a syntactic consequence of problem. According to formal definition, syntactic consequence is equivalent to an effective procedure. If solution to a hard problem is not a syntactic consequence of problem, what is it?

No. $\mathrm{P}\neq\mathrm{NP}$ means that there is no efficient (i.e., deterministic polynomial time) solution to $\mathrm{NP}$-hard problems, not that there is no effective (i.e., computable) solution. The fact that the solution is hard to find doesn't mean that it's impossible to find. Indeed, essentially the whole reason that $\mathrm{NP}$ is an interesting class of problems is that we know how to check proposed solutions to $\mathrm{NP}$ efficiently. Regardless of how hard it is to find satisfying assignments to Boolean formulas, if I give you an assignment and tell you that it satisfies the formula, you can easily check that I'm telling the truth.


How to determine if a language is deterministic context-free language? I have the following question to solve : DCFL means Deterministic Context-Free Language.

Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $f(L)$ is a DCFL. Explain your answers.
(a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)
(b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

I tried to find a counterexample to the problem, however I didn't find anything. So I am thinking that it is deterministic.
I am wondering how I should approach these kind of questions? and how to determine a language is deterministic?

Here $L$ is DCFL.

  (a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)

Let's define homomorphism $h$ as follow:

$h(a) = a, \space a\in\Sigma$

$h(\epsilon)= c$

$L' = h^{-1}(L) \cap (\Sigma^*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.)

Now start with DPDA of $L'$ and whenever you find $c$ in input make transition to final state.

  (b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

Consider $L=\{a^nb^{2n}\} \cup \{ca^nb^n\}$ Now $f_2(L) = \{a^{n-1}b^{2n}\} \cup \{a^nb^n\}$ Which is not DCFL.


What is the difference between directed graph and bidirectional graph? Is the graph above bidirectional? The image in wikipedia confused me a lot, before I heard about something called as bidirectional graph, I would say the above one a directed graph, but I am not sure now.

As stated in the Wikipedia article, a bidirected graph is a graph where all edges have an orientation at both edges of the edge. The orientation is an arrow head. So in your example, it is not a bidirected graph because the edges only have orientation on one end.
The following would be an example of a bidirected graph. Notice there is an arrow head on both sides of each edge of the graph.

There are three types of edges of a bidirected graph.

Extroverted edge: arrow heads oriented outwards or towards vertices (e.g. $\{a,b\}$)
Introvert edge: arrow heads oriented inwards or away from vertices (e.g. $\{b,c\}$)
Directed edge: arrow heads oriented in one direction or away from one vertex and towards the other (e.g. $\{a,c\}$)

There are also loose edges (which have no orientation on either end) and half edges (which have orientation on one end).
Another use of bidirected graph is a directed graph where each edge has a matching edge going the opposite direction. Your example would not be a bidirected graph in this context either since there are edges that do not have the reverse direction (e.g. $(1,3)$ exists but $(3,1)$ does not). The following is an example of bidirected graph in this context.

Bidirected graphs are not common in my experience. This is just from a quick read of the Wiki article.

Bidirected graphs: https://en.wikipedia.org/wiki/Bidirected_graph
Directed graphs: https://en.wikipedia.org/wiki/Directed_graph


Casting to boolean in integer linear programming I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\}$, where

$$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

My problem is to maximize $y$. How can I use linear constraints for this?

I tried certain cases like Cast to boolean, for integer linear programming but that won't work if the problem is to maximize $y$.

Add the following two constraints:
$$
y \leq 5-x \\
y \geq 1-x/5
$$
If $x = 5$, then these constraints state that $y \leq 0$ and $y \geq 0$, hence $y = 0$. If $x \leq 4$, then $5-x \geq 1$, and so the first constraint doesn't impose any constraint on $y$. On the other hand, $1-x/5 > 0$, forcing $y = 1$; and this assignment satisfies the constraint since $x \geq 0$ implies $1-x/5 \leq 1$.


Efficiently enumerate all subsets of an ordered set What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\{2, 5, 6\}$ (using the normal ordering for integers), I need the following:
$$\{\}, \{2\}, \{5\}, \{6\}, \{2, 5\}, \{2, 6\}, \{5, 6\}, \{2, 5, 6\}.$$
Smaller subsets should come first, but the ordering of the subsets of equal size is not important.

I'm looking for an algorithm that is efficient both in theory and in implementation (in a general purpose programming language) for very large sets.

One possibility is to generate separately all subsets of size $k$ using the following recursive approach:

  A $k$-subset of $a_1,\ldots,a_n$ is either a $k$-subset of $a_2,\ldots,a_n$ or $a_1$ adjoined to a $(k-1)$-subset of $a_2,\ldots,a_n$.

Run this recursive algorithm for $k=0,\ldots,n$. If you're careful, you will get a lexicographically ordered output.


Is 2**x faster to compute than exp(x)? Forgive the naïveté that will be obvious in the way I ask this question as well as the fact that I'm asking it.

Mathematicians typically use $\exp$ as it's the simplest/nicest base in theory (due to calculus). But computers seem to do everything in binary, so is it faster on a machine to compute 2**x than Math::exp(x)?

Since this is CS and not Stackoverflow, I'm going to assume that you're asking a question about numeric analysis, and (to keep things simple) IEEE-754 floating point in particular. In that case, the answer to your question partly depends on what you mean by "easier", and partly on the details of the system.

No modern CPUs that I'm aware of have an instruction built in which does exactly what you'd expect either for either the $e^x$ operation (which henceforth we will call exp, its usual name in C) or $2^x$ (exp2). They are both implemented using library functions.

As is the case with all numeric methods for transcendental operations, there are a few special cases to consider:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

However, there is another thing that makes the problem slightly less complicated: the useful domain is quite small. For binary32, exp(x) underflows if $x < -104$ or so, and overflows if $x > 88.7$ or so. Unusually for transcendental operations, we can also ignore the subnormal case, since exp(x) is indistinguishable from 1.0 if x is subnormal. All of the above is also true for exp2, except that the domain is slightly different.

Your intuition is right in that most implementations compute $e^x = 2^{x/\ln 2}$. However, the cost of that multiplication by $\frac{1}{\ln 2}$ is trivial compared to the rest of computing exp2. A typical method uses a precomputed table with $K$ elements:

$$\hbox{exp2}(x) = 2^n \times T[j] \times P(y)$$

where $n$ is the integer part of $x$, the table $T$ contains values of $2^{j/K}$ for all $j$ in the range $[0,K)$, and $P$ is some polynomial approximation to $2^x$ (quartic is sufficient for binary32) in the range $[0,\frac{1}{K})$. The $2^n$ part is cheap, since it's just manipulating the exponent. $T$ is a lookup table. So $P$ is likely to be the expensive part of the operation.

I should point out for completeness that Intel x86 FPUs include an instruction called f2xm1, which computes $2^x-1$ for $x$ in the range $[-1,1]$. However, on a modern CPU, this is a fairly expensive and non-pipelined instruction, and you are highly discouraged from using it. As the Intel Optimization Reference Manual Section 3.8.5 rightly notes:

  Although x87 supports transcendental instructions, software library
  implementation of transcendental function can be faster in many cases.

Edit: It's been pointed out in the comments that I should explain some of the new terminology used in IEEE 754-2008. Some of the language has changed since 1985 and 1987, and most people are far more familiar with the old jargon.

The terms "binary32" and "binary64" are the new names for 32-bit and 64-bit binary floating-point numbers, which the old standard called "single" and "double" respectively.

The term "subnormal number" replaces the previous term "denormal number" or "denormalized number".


Is there an polynomial time algorithm to find that sum of square-roots is less than an integer? Given: A list of $n$ integers $x_1,x_2,\dots,x_n$ and an integer $k$.

Determine: Is $\sqrt x_1 + \sqrt x_2 \cdots \sqrt x_n \le k$?

Question: Is there any polynomial time algorithm for the above problem? If yes, give an algorithm; otherwise prove it.

The complexity of the square-root sum problem is a long-standing open question. The stumbling block is that, although we know how to compute square roots efficiently, we don't know if it's possible to determine whether $\sum_i \sqrt{x_i}\leq k$ by evaluating only a polynomial number of bits of each square root.

The specific problem with the algorithm you propose in the question is that the phrase "compute the square root of each value" is underspecified. Any irrational square root (e.g., $\sqrt{2}$) requires computing an infinite number of bits, so you need to state what precision you're using.


Big-Oh of recursive function Can someone please explain to me why this function runs in O($n^2$) rather than O($n^3$). I feel like since that for loop runs in O($n^2$) and f() is recursively called around n times, that it should end up being $n\cdot n^2$ for an overall O($n^3$).

f(n) {
    if (n == 0) {
        return 0
    }

    int result = 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            result += j

        }
    }
    return f(n/2) + result + f(n/2)
}

The reason is easier to see when you figure the big-$\mathrm O$ of the loop and the recursion (last line) separately and then add them. The loop takes $\mathrm O(n^2)$ time, and the recursive part takes twice the time of $f(n/2)$.

So we get
$$\mathrm{time} (f(n))=\mathrm O(n^2 + 2\mathrm{time}(f(n/2)))\tag a$$

and we can simplify this  by noticing that this will form a geometric sequence.

$$ = \mathrm O(n^2+2\left(n/2\right)^2 + 4\mathrm{time}(f(n/4)))\tag b$$
$$ = \mathrm O(n^2 + 2(n/2)^2 + 4(n/4)^2 + 8\mathrm{time}(f(n/8)))\tag c$$
$$= \mathrm O\left(\sum_{i=0}^{\inf} \frac{n^2}{2^{i}}\right)\tag d$$
$$= \mathrm O\left( n^2\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)\right)\tag e$$

$\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)$ on line $\mathrm (e)$ converges to a  nonzero value that is not dependant on $n$ (specifically, $2$), so it can be removed from the $\mathrm {O}()$, to give just $\mathrm O(n^2)$

Note that this way of solving (leaving constant factors and ignoring the base case of recursion) will not work for all problems.

For example what if the inner loop had time complexity $\mathrm O(n)$? $$\mathrm{time}(f(n)) = \mathrm O(n + 2\mathrm{time}f(n/2)) = \mathrm O(n + 2\frac{n}2+4\mathrm{time}f(n/4)) = ...$$ which would give $\mathrm O\left( n^2\sum_{i=0}^{\inf}1\right)$, which is obviously not correct because it diverges.
However, if we ingore the constant factor of 2, we get
$$\mathrm{time}(f(n)) = \mathrm O(n + \mathrm{time}f(n/2)) = \mathrm O(n + \frac{n}2+\mathrm{time}f(n/4)) = ...$$ which gives $\mathrm O\left( n^2\sum_{i=0}^{\inf}\frac1{2^n}\right)$, which converges to $2$

-- End note


Find non-overlapping scheduled jobs with maximum cost Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum.

Now I'm not sure if a greedy algorithm will do the trick. That is, sort by cost and always take the next job that doesn't intersect and with max cost between the two.

Is this equivalent to a knapsack problem? How could I approach it?

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.

There are a number of special cases of perfect graphs for which people have discovered simpler and more efficient algorithms for this task. I don't know whether interval graphs fall into one of these special cases.


How to handle horizontal lines in the Polyfill Algorithm? When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled?

For instance, consider the following image:

For intersection I wrote if the line on the scan line count it as 1 point, even I count as 2 point or no point, wont help. Any idea how should I handle the horizontal line?

Edit: here a complex example of horizontal line intersection, let's take a look at line 3:

Alright, if we take a look at next point and previous point of the intersection of both end of horizontal line, if those point are in same side, means I can count them in or out, doesn't effect the whole calculation.
But if they are are opposite side, I have to count them in and count one side extra.

What do I mean?
Take InterS1 and InterS2 as an example, so when I get this I have count that horizontal line as 3 points:

point1 = InterS1
point2 = InterS2
point3 = InterS2

Why I need to do that?

When next point and previous point are in different direction, is letting us know that our intersection line crossing outside and passing through inside of shape.
Also because line can be created when there is start point and end point, so I need to have even number to draw lines.

So now I have no idea base on what I need to add the extra point to one side.
Do I make sense?

See Polygon Filling. It gives one method to deal with edges parallel to scanline. It says that it is imperfect, but you can ignore the horizontal edges. Other solution is to take either left or right endpoint of horizontal edge (any one point only). Yet another solution is to take right or left endpoint depending on the situation, so that whole edge is filled.

If you ignore horizontal lines you should get something like the following:


Confusion converting BNF to regular expression I have a Computer Science A-Level exam tomorrow and I've been trying to get this question answered by my teacher but she's not been too helpful so asking here instead.

In an exam question, I have the following BNF grammar, where _ denotes a space.

<fullname> ::= <title>_<name>_<endtitle> |
               <name> |
               <title>_<name> |
               <name>_<endtitle>

<title> ::= MRS | MS | ... | SIR

<endtitle> ::= ESQUIRE | OBE | CBE

<name> ::= <word> |
           <name>_<word>

<word> ::= <char><word>

<char> ::= A | B | ... | Z

The mark scheme says that the first rule, fullname, can be represented with a regular expression. But I'm not really sure how you could represent it with a regular expression when it's made up of other rules that can't be represented by regular expressions themselves e.g. name which is recursive. Also I thought regular expressions were made up of just letters and symbols e.g. a*b? . Forgive me if I don't seem too knowledgable on this because the resources we have for the A-Level are pretty awful.

There are two ways of interpreting 'the first rule can be represented with a regular expression'; you should review this 'mark scheme' to determine which applies.  One possibility is that the first rule is being treated as defining a language over its own terminals and non-terminals, without ever expanding the non-terminals.  I.e, think of treating the tokens 'title', 'name', and 'endtitle' as single characters of the 'language' of 'fullname' (along with the space-char).  Then it is easy to see that that is a regular language - there are only four strings in it!

The other possibility is what you assumed, i.e that non-terminals are to be expanded.  In this case your observation that 'name' is recursive is misplaced.  The issue is not whether the set of productions for that non-terminal is regular, the issue is whether the set of strings generated from that non-terminal is regular.  For 'name' the answer is yes: The set of strings generated from 'name' is seen, with a little thought, to be simply a sequence of one or more 'word'-s separated by spaces, for which a regular expression is easy to construct [given a regular expression for 'word', of course].  So yes, in this case 'fullname' generates a regular language.

[P.S. Note: Your 'word' is missing a production for a single 'char']


Cyber Security - recommended reading I'm applying for a doctoral training in Cyber Security, although I come from a maths background. I've been told that my background meets the entry criteria, although for my application I would like to be able to say that I've looked into Cyber Security it at least some detail.

Given that I will have very little time to do any reading before applying (about 2 weeks), what would you recommend I read? A few chapters from an academic text, or a popular book on the topic?

Specific book/paper recommendations would be appreciated.

Take a peek at Anderson's classic "Security Engineering" (PDF legally available for free at the link). It won't help you with the details, but it gives an overview of the whole area, for (more or less) laypeople.


Distribution of Ones in a Psuedorandom Sequence Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?

Yup, it's possible.  This generator is easily broken, as each output bit has degree only two.  There's an efficient algorithm that, given the first $n$ bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.

Let $x_1,\dots,x_{128}$ denote the initial state of the first LFSR and $x_{129},\dots,x_{256}$ denote the initial state of the second LFSR.  Then every bit produced by your generator can be expressed as a multivariate polynomial over $x_1,\dots,x_{256}$.  The degree of this polynomial is two: each monomial is of the form $x_i x_j$ or $x_i$.  Here were are working in the finite field $GF(2)$, i.e., working modulo two.  In this field, the AND of $x_i$ and $x_j$ is the term $x_i x_j$ (the product).  It follows that the output of the generator is a polynomial of degree two.  (Why?  Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p_1(x_1,\dots,x_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p_2(x_{129},\dots,x_{256})$ of degree one.  Now the output of the generator is the AND of these two, i.e., it is the product $p_1(x_1,\dots,x_{128}) p_2(x_{129},\dots,x_{256})$, which is a polynomial of degree two.)

So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x_1,\dots,x_{256}$.  If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x_1,\dots,x_{256}$.  At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.

How do you solve the system of linear equations?  One simple approach is linearization: if $n > 256^2/2$, then you can replace each monomial $x_i x_j$ by a new unknown $y_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination.  If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough.  (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.)  For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.

To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher".  For instance, you could use AES in CTR mode (counter mode).  This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.

By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.


Can I have a "dependent coproduct type"? I'm reading through the HoTT book and I have a (probably very naive) question about the stuff in the chapter one.
The chapter introduces the function type
$$ f:A\to B $$
and then generalizes it by making $B$ dependent on $x:A$
$$B:A\to\mathcal{U},\qquad g:\prod_{x:A}B(x)$$
and that is called the dependent function type.
Moving on, the chapter then introduces the product type
$$ f:A\times B$$
and then generalizes it by making $B$ dependent on $x:A$
$$B:A\to\mathcal{U},\qquad g:\sum_{x:A}B(x)$$
and that is called the dependent pair type.
I can definitely see a pattern here.
Moving on, the chapter then introduces the coproduct type
$$ f:A+B$$
and ... combobreaker ... there is no discussion of dependent version of this type.
Is there some fundamental restriction on that or it is just irrelevant for the topic of the book? In any case can someone help me with intuition on why  function and product types?  What makes those two so special that they get to be generalized to dependent types and then used to build up everything else?

The dependent sum is a common generalization of both the cartesian product $A \times B$ and the coproduct $A + B$. It just so happens that the HoTT book introduces dependent sum by generalizing $A \times B$, because that does not require the boolean type to be defined first.

The coproduct is a special case of dependent sum. Given types $A$ and $B$, consider the type family $P : \mathtt{bool} \to \mathcal{U}$ defined by $P(\mathtt{false}) = A$ and $P(\mathtt{true}) = B$. The dependent sum $\sum_{b : \mathtt{bool}} P(b)$ is equivalent to $A + B$. By the way, you can also get $A \times B$ as a dependent product $\prod_{b : \mathtt{bool}} P(b)$.

You ask what is special about products and function types. There are many, many reasons why $\sum$ and $\prod$ are "necessary". In terms of logic, they are necessary because they correspond to $\exists$ and $\forall$ by the propositions-as-types correspondence (but that only shifts the question to "why are $\exists$ and $\forall$ necessary?"). In terms of category theory, $\sum$ and $\prod$ are necessary because they are the left and right adjoint to substitution. Ask a more secific question if you would like to know more.


Why all problems are not in P complexity? İf Somebody wants to play perfect chess.I consider for finding solution to this problem,possible minimum data compression method which describes with 10 bit maximum possible data is in the range of 2^10.Then with some formula which can take input as next move in the chess,There should be some formula that can change all equations which are in the chess solving algorithm.Therefore ,if we assume in the chess.There should be 10^120 possible games.With approximately 400 bit with if conditions we can calculate all possible game's best strategy and with same thinking way all math problems can be solved with P complexity.Why there are differences with complexity classes?Short answer:İn karnaugh map some variation cannot be described shortly.
I understood my mistake vote to delete.

Chess is a fixed, finite problem. Because there's no input, you can solve it in a constant amount of time.

Computational complexity considers problems with inputs and looks at how the cost of the computation increases as the input gets longer. For example, you could generalize chess from an $8\times 8$ board to an arbitrary $n\times n$ board and ask how the time taken to compute which side can force checkmate varies as a function of $n$.  Certain versions of this problem (it depends on exactly what rules you take) have been proven to require an amount of time that is exponential in $n$, which implies that they can't be solved in only a polynomial amount of time.


Merging and Unmerging Sets of Trees Efficiently Background

Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:

Tree 1:

{
  a: {
    b: 1
  },
  c: [{}],
  d: 3
}

Tree 2:

{
  a: {
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

merge(t1, t2) would yield:

{
  a: {
    b: 1
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

Note the overwrite of primitives (d).

Problem

I'd like to be able to merge some order set of trees like the above (the order is important because of the overwriting of primitives) AND be able to efficiently unmerge one of the trees.

Mathematically, I want two functions $merge$ and $unmerge$ such that the following holds true:

$$
unmerge(merge(t_1,...,t_n,...,t_p), t_n) = merge(t_1,...,t_{n-1},t_{n+1},...,t_p)
$$

where $p,n \in Z^+$ and $n \leq p$.

Simple solutions like "delete all of the nodes on $t_n$ from the merged tree" obviously doesn't work in many cases.

More robust solutions like creating immutable copies of the interim trees might would has you could take the cached tree $merge(t_1,...,t_{n-1})$ and then merge in the subsequent trees $t_{n+1},...,t_p$. However, in the worst-case ($n=1$) this is equivalent to just remerging the entire set; ideally, there would be some less computationally complex solution.

Would love any advice or pointers for further research. Thanks!

One solution

Make trees immutable, using path copying.  Give each tree a name.  Whenever you create a new tree T3 by merging two trees T1,T2, remember in T3 that it was created by merger of T1,T2 (i.e., include pointers to T1,T2 as part of the auxiliary information in the root node of T3).  Also keep track in the auxiliary information for each tree all of the original trees it was transitively created from.

Now, when you want to unmerge a tree, you can look at the auxiliary information to work out what you need to do.  When you call unmerge(T, U), look at the auxiliary information for T to find the two trees T1,T2 it was merged from; if U was used to create T1, then

unmerge(T, U) = merge(unmerge(T1, U), T2)

so you can proceed recursively.  Similarly, if U was used to create T2, then

unmerge(T, U) = merge(T1, unmerge(T2, U))

The running time of this will be proportional to the maximum "depth" of the merge operations, times the time to merge two trees.

A more efficient solution

With more sophisticated data structures, you can speed up the unmerge operation so it performs at most $O(\log n)$ merges.

Call a tree "atomic" if it wasn't created by a merge/unmerge.  The auxiliary information for each tree T will be an ordered list of the atomic trees T1,..,Tk it was created from, so that T = merge(T1,..,Tk).  This list will be stored as a persistent self-balancing binary tree with k leaves, one per atomic tree in the list, ordered in the same way they are in the list.  Each node in that self-balancing tree corresponds to an interval Ti,..,Tj of the list (namely, Ti,..,Tj are the set of leaves under that node); add metadata so that node points to the tree produced by merge(Ti,..,Tj).  Also, as auxiliary information for tree T, we'll have a map that given the name of a tree U lets you look up where in the list T1,..,Tk that U appears; this can be done with a second persistent self-balancing binary tree with k leaves, ordered by lexicographic order on the names of the atomic trees.

The merge(T1, T2) operation merges the two trees, and constructs its auxiliary information by concatenating the associated lists.  Those operations on the self-balancing binary trees can be done in $O(\log n)$ time, so this adds little overhead to the merge operation.

Finally, unmerge(T, U) can be implement as follows.  First, we look up where U appears in the associated list for T; suppose U is the ith item in the list T1,..,Tk, i.e., U = Ti.  Then we need to compute merge(T1,..,Ti-1,Ti+1,..,Tk).  It turns out that this can be done in $O(\log n)$ merges.  Why?  Well, we look at the path from Ti to the root in the self-balancing tree for T; if we take all of the siblings of the nodes on that path, and merge their associated trees in the correct order, we get merge(T1,..,Ti-1,Ti+1,..,Tk).  Since it is a self-balancing tree, its depth is at most $O(\log n)$, so there are at most $O(\log n)$ nodes along that path, so we need to do at most $O(\log n)$ merge operations.  Thus, unmerge(T, U) is about $O(\log n)$ times as slow as a merge operation.

A final note: there's nothing special here about the fact that the T1,..,Tk are trees.  They could have been any value, such as simple integers or anything else.  So, you might find it easier to think about this with simple values first.  On the other hand, this also means that my algorithm isn't taking into account the fact that the T1,..,Tk are trees; it's possible that data structures that take that into account might be able to be even more efficient.


How to find all shortest paths between two nodes in a weighted undirected graph? How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes.
I want to find all nodes that can be on a shortest path. For example:

10 11
1 2 1
1 3 1
3 4 2
4 5 1
5 6 1
5 10 2
1 7 1
7 8 3
7 9 2
9 10 2
8 10 1

The answer is

1
7
8
9
10

because there are two shortest ways

1 7 8 10

and

1 7 9 10

To tell whether a vertex $v$ is along some possible shortest path from $s$ to $t$, compute $d(s,v)$ (the length of the shortest path from $s$ to $v$) and $d(v,t)$, and then.....

You can compute $d(s,v)$ for all vertices $v$ efficiently using....

(It's your exercise, so I'll let you have the pleasure of working out how to fill in the blanks.)


Constant factor of an array In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:

  Insertion into a full array can be handled by resizing, i.e.,
  allocating a new array with additional memory and copying over the
  entries from the original array. This increases the worst-case time of
  insertion, but if the new array has, for example, a constant factor
  larger than the original array, the average time for insertion is
  constant since resizing is infrequent.

I grasp the concept of amortization that seems to be implied here, yet they seem to imply that in other cases, a newly allocated array could possess a constant factor smaller than the original array. Is that so? What does "constant factor" mean in this particular context? I'm having trouble understanding what's being said here.

That's probably a typo or poor wording -- in the quote, "has" should be "is".


Proving that collision is less likely if the table size is prime in case modulo arithmetic is used If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets,

  where m = table_length/GreatestCommonFactor(table_length, x)

Can someone help me to prove the above equation.

 Example for the above question would be:
 x = 3, table_length = 24
 m = 24/gcd(3,24) = 24/3 = 8

So 3%24 = 3  ->1
   6%24 = 6  ->2
   9%24 = 9   ->3
   12%24 = 12 ->4
   15%24 = 15 ->5
   18%24 = 18 ->6
   21%24 = 21 ->7
   24%24 = 0  ->8
   27 %24 = 3 ->1

From the above equation inference can be drawn that when

   table_length/GreatestCommonFactor(table_length, x) is 1,

i.e when x and table_length are co-prime, the distribution would be proper and will cover all the buckets.

Based on observation

exactly 8 distinct multiples of 3 modulo 8.
exactly 2 distinct multiples of 4 modulo 8
exactly 1 distinct multiple of 8 modulo 8
exactly 4 distinct multiples of 6 modulo 8
exactly 8 distinct multiples of 6 modulo 8

There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo n

Is a better way of proving possible?

It requires Theorem 31.20 on Page 927 from the CLRS (for which there is a proof of the theorem on the same page) that "if $d = gcd(a, n)$ then $\langle a\rangle = \langle d \rangle = \{0, d, 2d, \ldots, ((n/d) -1)d\}$ in $\mathbb{Z}_n$, and thus $|\langle a\rangle| = n/d$"

But it's Corollary will be more useful to the proof:
"The equation $ax \equiv b \mod n$ is solvable for the unknown $x$ if and only if $d|b$, where $d = gcd(a, n)$"

These conclusions will be the core of the proof.


Relation between type-checking decidability, typability decidability and strong normalization Yo! This is probably a stupid question, however I've never seen it written down explicitly if, for instance, decidability of type-checking is equivalent to the strong normalization property. Therefore I'm asking this question to clarify all possible relations between type-checking, typability and strong normalization.

Let me explain my motivation. For type theories (I'm being intentionally vague here, but I'm interested mainly in dependent type theories), strong normalization is used to prove the decidability of type-checking. On the other side, any typed systems that I know that have one of these properties also have the other one. However I've never seen explicitly stated that strong normalization is equivalent to decidability of type-checking.

Analogously, to prove typability, one usually (maybe always), reduces a term to a normal form. However it's know that typability is not true for dependent type theories, whereas strong normalization may hold.

By decidability of type-checking, I mean that for any given type $A$, context $\Gamma$ and untyped term $a$, it's possible to decide in a finite number of steps whether $\Gamma \vdash a: A$ is true or not.

By decidability of typability, I mean that for any given untyped term $a$, it's possible to decide in a finite number of steps whether there exist a context $\Gamma$ and a type $A$ such that $\Gamma \vdash a: A$ is true.

1)Is it true that decidability of type-checking is equivalent to every term being strongly normalizable?

2)More generally, what's the relation between decidability of type-checking, typability and strong normalization? Which one implies the other?

Thanks in advance.

EDIT

Given the unsatisfaction regarding the level of generality of my question (which I was unaware of), I would like to delimit it only to Pure Type Systems. Of course, additional comments or counterexamples regarding other type theories will be of great utility.

I'll give a more focused and technical answer to Martin's. If we're interested in dependent type theories, then neither direction is obvious, but both are generally assumed to hold. However the direction Decidable $\Rightarrow$ Normalizing is open, I believe, even for relatively well understood systems, though we do have partial results. This question explores some of the same issues.

More technically: a good technical framework for these questions is the setting of Pure Type Systems in which normalization does imply decidability of type checking. The result is folklore, but non-trivial, since a strategy for when to apply the conversion rule needs to be found. The obvious strategy is to normalize inferred types before all applications of the application rule. There are some subtleties even here, where the correctness of a natural (more efficient) strategy called expansion postponment was open for a while, but has been settled since.

There are type systems which are normalizing but undecidable, most notably the system with intersection types which types exactly the normalizing terms, and so must be undecidable (since otherwise it could be used to identify normalizing terms). It would be tempting to say here that the system is defective in the sense that it is not type directed, i.e. the terms do not contain enough information to figure out the type.

Now the converse, which would suggest non-normalizing systems are undecidable, is far from obvious: it was even open for a while for the famous $Type:Type$ system of Martin-Löf! This case was solved by giving an example of a looping combinator, which allows writing arbitrary computations.

However the general problem is still open for general pure type systems, though it is widely believed to be true, and some partial results have been shown in this direction, e.g. here.


Non-deterministic Turing machine and palindromes I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$.

I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(n)$ time – and then check both tapes (one from beginning and the second from the end) – $O(n)$ time again.

However, I can't picture how to do such procedure in a non-deterministic TM using only one tape. All the procedures I came up with take $O(n^2)$ steps. How can the non-determinism reduce the running time here?

Guess a position $\ell$ and add it to the left of the input. Copy it to the beginning of the tape, on top of the input string (use an expanded alphabet). Now go to position $\ell$, carrying your counter around with you. For each position you move, you need to spend $O(\log n)$ time to copy the counter, but that's fine. Decrementing the counter and comparing it to zero also take only $O(\log n)$. Once at position $\ell$, remember the symbol there, and go back to the beginning. Now move your counter all the way to the other end of the string, and count $\ell$ positions from there. Compare the symbol you find to the one you remember.


How to prove ln(n) = Θ(log2 n)? This is a homework problem and I'm not sure how to do it correctly. It says "Prove ln(n) = Θ(log2 n) with n = odd number".
Bu using Natural logarithm rules, we can somehow know this is partcially true

However, I'm stuck with this since I don't understand how to do the whole procedure.

You correctly pointed out that $\ln n = \frac{\log_2n}{\log_2 e}$. You can rewrite this as $\ln n = \frac{1}{\log_2e}\cdot\log_2n$. Since $\Theta(\cdot) $ allows you to drop constant factors (and as @Pseudonym pointed out, $\frac{1}{\log_2e}$ is constant), it follows that $\ln n = \Theta(\log_2n)$


Minimum number of moves required to transfer items from source bins to target bins? I have a set of source bins, each with some number of items, and a set of target bins.  I want to move all of the items from the source bins to the target bins, using the minimum number of moves.  Each move can move any number of items from one source bin to one target bin.

The bins do not have the same size, but the total capacity of source and target bins is the same.

I came up with a few possible formulations for this problem:

1) as a problem of finding the sparsest solution to an underdetermined system of linear equations with variables in $\mathbf N_0$. Lots of literature about this but very sparse (no pun intended) on $\mathbf N$.

2) I could also describe it as finding the min cost flow of a bi-partite network $G=\{U,V,E\}$, fully connected, with  $U$ supply nodes (source bins) and $V$ demand nodes (target bins) with $|U|$ not necessarily equal to $|V|$, edge cost given by

$$c_{uv} =
\begin{cases}
1 &\text{if link is used}\\
0 &\text{otherwise}
\end{cases}$$

and the total demand equal to the total supply.

However, the cost is non-linear so usual min cost flow algorithms do not work here.

3) and I also considered the Split Deliveries Vehicle Routing problem with vehicles (source bins), vehicle capacity (size of source bins) customer demand as the target bins, and a space where all inter customer location distances are 1.

All of these are NP-Hard problems.

My questions:

What is the complexity of this problem?  Can it be solved in polynomial time?  Is there any research literature covering this problem?

The problem is NP-hard, by reduction from the partition problem.

Here is the reduction.  Consider an instance of the partition problem, namely, integer $x_1,\dots,x_n$.  Create $n$ source bins and 2 target bins, with $x_i$ items in the $i$th source bin.  Set the capacity on the target bins to $(x_1+\dots+x_n)/2$.  Then there is a solution to your movement problem that uses exactly $n$ moves, if and only if there is a solution to the partition problem.

We can also show your problem is strongly NP-hard, by reduction from 3-partition.

As a result, you should not expect to find any efficient algorithm that always gives the optimal answer and scales to large problems.  You might try looking for heuristics, approximation algorithms, or algorithms that could be exponential time in the worst case but hopefully are often fast in practice.  For instance, you could look into simulated annealing, integer linear programming, and approximation algorithms for bin packing.


Why is Binary Heap never unbalanced? My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?

You must refer to the definition of a Binary Heap:

A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

It is by definition that it is never unbalanced. The maximum difference in balance of the two subtrees is 1, when the last level is partially filled with nodes only in the left subtree.


co-NP but not NP problems What are the problems that are in co-NP but not in NP?

i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.

co-NP is the set of complements of problems that are in NP. So co-NP contains problems such as non-3-colourability, Boolean unsatisfiability and so on.
Most complexity theorists believe that NP$\,\neq\,$co-NP and one consequence of this is that the complement of any NP-complete problem would be in co-NP but not in NP.

Wikipedia has more information on co-NP.


Prove Subset-Sum is NP-complete - Alternative reduction? It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the Subset-Sum problem?

In general, each $NP$-hard problem can be reduced to all other known $NP$-hard problems (there exist hundreds).

For the subset-sum there is for a example knapsack. Subsetsum is a specialisation of knapsack.

The other way, if you could solve subset-sum in poly-time, then you would also be able to solve PARTITION (and 3-PARTITION and 4-PARTITION)


Optimizing Fleury's algorithm to work in O(|V|+|E|) The time complexity of Fleury's algorithm is $O(|E|^2)$ because for each edge I have to check whether it is a bridge or not and that takes $O(|V|+|E|)$ time. But, instead of that if I store my bridges in a hash table by a traversal at the beginning and then print the Eulerian tour (checking for each bridge in $O(1)$ using the hash table), the overall time complexity would be $O(|V|+|E|)$. So, will this optimization be useful? If yes, why is it not included in Fleury's algorithm?

In addition, which algorithm is used in practice to print an Eulerian path (not Eulerian cycle, I know that can be done in $O(|V|+|E|)$ using Hierholzer's algorithm)?

I am more interested in theoretical analysis (whether this optimization would be useful) rather than actual implementation.

Because a bridge in current graph may not be a bridge in the primary graph. Note Fleury's Algorithm deletes an edge after you pass it.

Consider the following graph:

You start at $A$, then move to $B$ and delete the edge $AB$.

Now $BE$ becomes a bridge so the algorithm then chooses $BC$. However, $BE$ is not a bridge in the primary graph, so you cannot detect it in advance.

According to Wikipedia

  If there are no vertices of odd degree, all Eulerian trails are
  circuits. If there are exactly two vertices of odd degree, all
  Eulerian trails start at one of them and end at the other.

So finding an Eulerian trail is essentially the same as finding a cycle (if there are exactly two vertices of odd degree, add an edge connecting them and find an Eulerian cycle in the new graph).


Direct encoding of the solution into the chromosomes in a Random-Key Genetic Algorithm In a random key genetic algorithm1, the chromosomes consist in a sequence of real numbers (initially randomly generated) in the interval $[0,1]$.

I've been told by my teacher that in these kinds of genetic algorithms, one cannot encode the solution directly into the chromosomes, as that would generate "infinitely large" convergence times. Instead, the proposed solution from my teacher is to use the weights in the chromosomes to modullate the construction of a solution through a greedy algorithm. Let me clarify that further with the classical example of the Travelling Salesman Problem:

In a direct encoding (my proposal), with $N=4$ cities, a chromosome with values $[0.1, 0.7, 0.4, 0.9]$ could be decoded in order to determine the order in which to visit the cities, which would become $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$.

The other approach consists in constructing a solution by means of a regular greedy algorithm. For example, starting from the initial location, a simple greedy algorithm for the TSP would select, at each iteration, the closest city for its next step. In order to fit the chromosomes in this schema, when considering going to the next city, one would multiply the distance to the considered location by the value of the allele for that city, essentially changing the values of the greedy function with the chromosome's genes.

So my question would be:

Is this kind of "modullating a greedy" chromosome encoding widespread in the literature? I couldn't find any examples. I find it surprising that it works well, because when using a greedy there's no way to explore the whole solution space, and the variations in the chromosomes arising from crossover are probably going to end up generating the same greedy solutions all the time.
Is the first kind of encoding (the direct one) something unacceptable for a random-key genetic algorithm? Would something similar be unacceptable as well for a regular (as in, more generic) genetic algorithm?

As said elsewhere. Genetic algorithms are more art than science. The encoding and evaluating of chromosomes can be anything you like. The only "unacceptable" techniques are the ones that don't work.


Is it possible to create a "Time Capsule" using encryption? I want to create a digital time capsule which will remain unreadable for some period of time and then become readable. I do not want to rely on any outside service to, for instance, keep the key secret and then reveal it at the required time. Is this possible? If not, is some kind of proof possible that it is not?

One strategy would be based on projections of future computing capabilities, but that is unreliable and makes assumptions about how many resources would be applied to the task.

The problem is known as timed-release cryptography. For some references/introduction look at:

"Time-lock puzzles and timed-release Crypto" by R.R. Rivest, A. Shamir, and D. A. Wagner (1996)

Our motivation is the notion of "timed-release crypto", where the goal is to encrypt a message so it cannot be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to "send information into the future" ...

or "Provably Secure Timed-Release Public Key Encryption" J.H. Cheon et al. (2008)


Help understanding formal language notation I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the plain English sentences do not even make sense or have the letter s on the end of words where they should not be. please help me understand this:

Language generators. A language generator is a device that can be used to generate the sentences of a language. A generator seems to be a device of limited usefulness as a language descriptor. Generators can more easily read and understand them. A language generation method constructs a language generator G and capable of generating a string of language by a process called derivation. For example, consider a language L over alphabet

  ∑ = {a, b}

  L= {a^n, b^n|n ≥ 1}

  G = {  s -> asb   s -> ab   s -> 3(i need to turn this symbol the
  opposite direction)}

W = aaa bbb

Derivation:

S ⇒ asb  ⇒ aasbb  ⇒ aaabbb

i.e., S ⇒ aaabbb It means we have derived aaabbb starting from start symbol S using the rules of language generator G in finite number of steps.

The problem seems to be that they assume you have a background in formal language theory.
Here's the basics.

$\Sigma$ is the symbol which is traditionally used for an alphabet. When you're talking about strings, you always have a finite set of symbols that can be in those strings. Here we use $\Sigma=\{a,b\}$ to say that all our strings are binary, that is, they only contain the letters $a$ and $b$. We could have just as easily chosen $0,1$ or $\vee, \wedge$ or any other symbols we like. We just need a finite set of symbols.
$\epsilon$ is the empty string, the string of length 0. Sometimes you'll see this as $\lambda$, which is confusing, so be prepared for either. In a programming language like C, you'd see this written as "". It has the property that when you append it to the beginning or end of a word, it gives you that same word.
This is a description of context-free grammars. It's basically a concise way of defining a set of strings over some alphabet. We say that a string is in the set if there's some set of derivation rules we can apply to get that string.

The derivation rules basically are a way of generating strings. The idea is that, you start with a special start symbol, usually called $S$. We have upper and lowercase letters, called non-terminals and terminals. We keep applying rules until we only have lowercase letters left.

The X -> Y things you see are the derivation rules. This is saying, in any string, you can replace the symbol on the left with the symbol on the right. The idea is that you keep doing this until you get a word with only lowercase letters.


How can I model overlapping service times in queueing model? Say there are two queues (1 and 2) in series.

The latency will be $t_1 + t_2$ without overlapping of their service times ($t_1$ and $t_2$ respectively).

If there is a overlapping, the latency will be $t_1 + t_2 - T_o$ where $T_o$ is the overlapped time. (Specifically $T_o = \min(t_1,t_2)$ in my case)

To my best understanding, queueing model is not suitable for modeling the overlapped service times. However, there would be some works for extension cause this overlapping is very common behavior, I believe.

How can I model overlapping service times in queueing model?

That's not in series.  If their times are overlapping, they're not in series.

You mentioned that in your particular example, the latency is $t_1 + t_2 - \min(t_1,t_2)$.  This quantity can be more cleanly expressed as $\max(t_1,t_2)$.

As a result, your queries are certainly not in series -- on the contrary, they are in parallel.  And, there are clean and simple ways to model two queues in parallel.

In particular, assuming the queue times are independent and letting $t=\max(t_1,t_2)$, we have

$$\Pr[t \le x] = \Pr[t_1 \le x] \times \Pr[t_2 \le x].$$

Thus, the cumulative distribution function (CDF) for $t$ is the product of the CDF's for $t_1,t_2$.  The CDF for a single queue is easy to compute given standard properties of the queue (e.g., it's easy to compute the CDF from the PDF).


Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?
I should probably use Ogden's lemma, but I don't know how to do that in this case.

If $L$ is context-free, then according to Parikh's theorem, the set $\{(p,q) : p,q \geq 1, p \geq q^2 \text{ or } q \geq p^2\}$ is semilinear, say it is the union of the linear sets $L_i$. Each linear set is either a singleton or of the form $(a,b) + \mathbb{N}(x,y)$. In the latter case, I claim that either $x = 0$ or $y = 0$. Otherwise, for large $n$ we have $\frac{a+nx}{b+ny} \approx \frac{x}{y}$, and in particular it isn't the case that $a+nx \geq (b+ny)^2$ or $b+ny \geq (a+nx)^2$.

It follows that there exists a finite set $F$ such that
$$
\bigcup_i L_i = F \cup \bigcup_j (p_j+\mathbb{N}t_j,q_j) \cup \bigcup_k (p'_k,q'_k+\mathbb{N}t'_k).
$$
Let now $z \geq 2$ be some integer larger than all indices in $F$ and all $p_j,q_j,t_j,p'_k,q'_k,t'_k$, and consider the point $(z^2,z)$, which should be contained in this union. By construction, it is not contained in $F$ or in any $(p_j+\mathbb{N}t_j,q_j)$. If $(z^2,z) = (p'_k,q'_k+nt'_k)$ and $(p,q) = (p'_k,q'_k+(n+1)t'_k)$, then we must have $q \geq p^2$, which implies that $z+t'_k \geq z^2$. This again contradicts our choice of $z$.
It follows that $(z^2,z)$ is missing from the union, and we reach a contradiction.


Complexity of solving multiple problems of the same complexity? If I am given two languages $A$ and $B$ which are in NP, then we know that there exists a NDTM that can decide $A$ in polynomial time, and there exists another NDTM that can decide $B$ in polynomial time. Can I decide $A$ and $B$ in polynomial time using a NDTM by simply using a NDTM to check for belonging in $A$ then use another NDTM to check for belonging in $B$ and if both accept then it belongs to both $A$ and $B$?

Yes, you can test whether $A \cap B$ is in $\textsf{NP}$ by testing $A$ and $B$ separately. Actually, you have proven that the class $\textsf{NP}$ is closed under intersection. See this lecture note (Exercise 1) for details and other cases.


Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past their start and end points) to an arbitrary point.

The best I have done so far is to generate a set of sample points along each line and use a KD-tree to solve the nearest neighbor problem for the points - i.e. find the nearest line sample point to the query point. But this is inaccurate and needs a large number of samples for long lines.

I did see this:
Algorithm for nearest edge detection with respect to a point (in all directions)

but it relied on a sweep method and a small number of lines of finite length.

All your lines define a planar subdivision, where each polygonal region is bounded by a finite number of line segments or rays. So, at first you need to find a (probably infinite) region, containing a query point, and then you'll be able to select its boundary line with minimum distance from this point.

There are many ways to preprocess a planar subdivision in order to solve the Point location problem with logarithmic time complexity. Some hierarchical data structure is typically devised, which can be traversed for any query point, and it's proved, that the length of the traverse path is limited by $O(log(N))$, where $N$ is the number of regions. As @Pseudonym mentioned in comments, you can also use Binary space partitioning (BSP) to build a BSP tree - it's also a hierarchical data structure (binary tree), which will allow you to efficiently find a region, containing a query point. It looks like your problem suits well for this BSP approach.

Sorry to say, you can get regions with $O(n)$ boundary segments/rays, where $n$ is the number of lines. To overcome this difficulty you can further subdivide each region into Voronoi diagram, generalized for its boundary segments and rays. It's easy to see that the total number of such refined regions will be limited by $O(n^2)$, which still gives you logarithmic time complexity for the nearest line search. However in average case these regions with many boundary segments/rays will make up a small fraction of all regions - so in average you still will be able to quickly select the closest boundary segment/ray just by looping over the region boundary.

If you want to know more about general properties of the geometric structure you're working with - it makes sense to read this Wiki page.


Find expression with minimal distance to target I will start of with an informal example and give a more formal problem definition later.

Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and multiplication, we can construct expressions like $(\pi + 2.3) * 0.3 + 4.382$ and $(0.3 + \pi) * (2.3 + 4.382)$. We put the following constraints on the expressions:

Each value in the set must be used exactly once in the expression.
We can only use addition, multiplication and brackets in our expression.

The goal now is to get as close to a target value, say $9.5$. For example, the expression $2.3 * \pi * 4.382 * 0.3 = 9.49886...$ gets close. How can we find the expression whose evaluation is closest to $9.5$? Or more formally:

  Given a finite set $V$ of - not necessarily unique - elements, two
  binary operands $f(x, y)$ and $g(x, y)$ that operate on the elements
  in $V$ and a target value $t$, find the expression $E$ containing each
  element of $V$ exactly once, such that the evaluation of $E$ is as
  close to $t$ as possible. $E$ must consist only of the values in $V$,
  the given operands and brackets.

I understand that for small sets, an exhaustive check that checks all possible expressions is feasible. Using heuristics, quickly finding an approximate answer (with small distance to the target) is probably possible for larger sets too. My questions are; does a more efficient method exist to find exact answers for large sets? Do efficient methods exist specifically for certain operands? What fields of mathematics and computer science touch on this subject?

This is a very difficult problem. For an already hard special case, you can look at the subset sum problem. So in general, one direction to look at is NP-hard optimization problems (and ways of coping with hardness).


How to "logically" solve boolean logic I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.

Up to now I'm just solving these boolean implementations by guessing all required gates which is so much time consuming. I'm not able to find any logic in the implementation.

I'm wondering if you have any method, tipp how to solve this.

Here is an example of the Mux requirements presented in the book

Mux requirement image example
Mux requirement image example continue

The nand gate is defined as follows --when and, not gates are available--

a nand b  ≡  ¬(a ∧ b)

Hence, since conjunction is idempotent, $a ∧ a ≡ a$, we have the not gate:

a nand a  ≡  ¬ a

Since negation is its own inverse, $¬ ¬ x ≡ x$, we have the and gate:

  a ∧ b
≡ ¬ ¬ (a ∧ b)                   -- double negation
≡ (¬ (a ∧ b)) nand (¬ (a ∧ b))  -- not in terms of nand
≡ (a nand b) nand (a nand b)    -- using ‘definition’ of nand

Finally, the or gate:

   a ∨ b
≡  ¬¬ a ∨ ¬¬ b                 -- double negation
≡  ¬ (¬ a ∧ ¬ b)               -- De morgan's law
≡  (¬ a) nand (¬ b)            --  using ‘definition’ of nand
≡  (a nand a) nand (b nand b)  -- not in terms of nand

Neato!


How can I efficiently find the largest positive interval in an unsorted array? Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an interval of 4 because 8 - 4 = 4. But the largest positive interval is between index 2 and index 10, because 11 - 1 = 10.

I can see that there's a way to do this in linear time, but I can't figure out what it is. The n^2 brute force solution is straightforward, but I want to understand the better way.

To be clear, the largest positive interval in [20, 1, 4] would be 3, not 19, because 20 -> 1 is an interval of -19.

The solution I would put forward is to translate the array in linear time to an array of differences, e.g. [20, 1, 7, 4, 2] becomes [0, -19, 6, -3, -2], and then use Kadane's algorithm for finding the maximum contiguous subsequence. The largest subsequence would be 6 on its own, implying indices 1 and 2 provided the answer.

Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.


ANN with communication between nodes of same layer I starting to learn about artificial neural network.

I already did some simple things for classification, with different hidden layer.

I would like to know :

Is there a way to create "communication" (synapse) between neurons of the same layer ?
If yes how will work the back-propagation ?

Thanks a lot

Yes! That is definitely possible. You should know that not all network topologies are layered. You could also have a network which consists of loose neurons which are connected to one another in a more liquid way:

The reason we have 'layers' in networks is not because they add functionality, but because they make coding easier and more overseeable. When you have for example this network:

input: [neuron1, neuron2]
hiddenlayer: [neuron3, neuron4, neuron5]
output: [neuron6]

that is exactly the same as:

[neuron1, neuron2, neuron3, neuron4, neuron5, neuron6]

Because all neurons get activated sequentially.

So what kind of synapses do you want to create inside a layer? Recurrent or feedforward?


Learning a specific functional form with machine learning Suppose I have only three independent features (x, y, z) as the input to some machine learning routine (e.g. neural network). From some domain knowledge, I know that the output o(x, y, z) must have the specific functional form

o(x, y, z) = f(x)*g(y)*g(z)

where the g(.) are the same function. The details of f(.) and g(.) are not known beforehand (except that f(.) is a decaying function with respect to x). Given that there is no upper limit on the sample size, is it possible to incorporate such a functional form (or in general, any specific functional form) into the machine learning routine?

Yup.  You define two neural nets (or other models) $f,g$ with weights $\theta,\psi$, define

$$o_{\theta,\psi}(x,y,z) = f_\theta(x) g_\psi(y) g_\psi(z),$$

define a loss function (which compares the predicted output $o_{\theta,\psi}(x,y,z)$ to the desired output), and then use stochastic gradient descent to find weights $\theta,\psi$ that minimize the aggregate loss on the training set.


When do we need U(n+2) to solve a problem that can be formulated in U(n)? I understand the need for a universe hierarchy, and that each new level brings additionnal proof-theoretic strength.

In the HoTT book there are examples of proofs that need to use the next level in the Universe hierarchy.

Do we have examples of inhabited types A:U(n), where the construction of the inhabitants/proof a:A requires the use of U(n+2) ?

This question on the theoretical CS stack exchange asks if pentation is implementable on Church numerals in a predicative variant of System F. In the normal, impredicative system, this is quite easy, because we have:

ℕ : Type
ℕ = forall (R : Type). (R -> R) -> (R -> R)

1 : ℕ
1 R s z = s z

hyper : (ℕ -> ℕ -> ℕ) -> (ℕ -> ℕ -> ℕ)
hyper op m n = n ℕ (op m) 1

So, because a Church numeral can be instantiated to work on the type of Church numerals, we can easily iterate an operation to get to the next hyper operation.

However, in a predicative system, the quantification over types increases the size of the quantifying type to be larger than the size of the types quantified over. So, a Church numeral that can be instantiated to operate on Church numerals must be one that quantifies over a higher universe.

The person asking the question links to a paper on the functions representable in such a stratified system with $\omega$ universe levels (I.E. one for each natural number). The paper shows that the representable functions are the super-elementary functions, which includes tetration, particular finite compositions of tetration, and products and sums of those functions. However, the only reason that all these functions are even representable is that they make use of Church numerals for all universes. So, for instance, tetration has a type (something) like:

_^^_ : Church 0 -> Church 1 -> Church 0

That is, to compute tetration for 0-level numerals, you must make use of higher level numerals. And depending on the complexity of the function, you may have to use much higher levels to compute 0-level numerals (arbitrarily high levels).

I showed in the answer there how if you add even more universes, it is possible to give a uniform type for tetration, which then means pentation can be defined. But now the universes involved are indexed by transfinite ordinals (if at all), and you still (seem to) need to go up levels to define some functions on lower (but still very high) levels.


How did 'Isabelle' (the theorem prover) get its name? The title says it all, but I'm curious because it isn't obvious how a theorem prover came to be named 'Isabelle'. Was it named for a person? I couldn't find out by some Google searches.

A little google-fu (and my own memory) tells me it was apparently named by Larry Paulson after Gerard Huet's daughter.

Gerard Huet happens to be one of the people behind the less poetically named Coq theorem prover.

Small world!


Is the dynamic programming pairwise alignment algorithm considered greedy? I'm a freshman in Computer Science and I'm studying bioinformatics sequence alignment algorithms.
My understanding of a greedy algorithm is one that takes the best decision for a particular instance in order to find a general best decision. By that definition, would the basic dynamic programming pairwise alignment algorithm be considered greedy?

No. Rather, the DP algorithm for pairwise sequence alignment1 is an instance of backtracking. What makes it superior to naïve exhaustive search is that

it abandons potential solutions as soon as it can prove that it is going to be sub-optimal (each field in the DP matrix considers only the optimal previous sub-alignment), and
it computes partial results only once and reuses them — that’s the “dynamic programming” aspect of it.

There are other, greedy algorithms for pairwise sequence alignment. These will first find so-called perfect “seed matches” between a query and a database, and then extend those outwards using one of several strategies. They thus explore locally optimal solutions but aren’t (in general) guaranteed to find a global optimum. This is for instance what the BLAST algorithm is doing.

1 By which I’m assuming you mean the Needleman–Wunsch or Smith–Waterman algorithm or some minor variation.


Fibonacci Sequence recursion algorithm and the time complexity I am reading a free book on algorithms

http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf

and on page 13 it says

"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"

I do not understand how they know that T(n) ≥ Fn

if someone could explain it to me it would be much appreciated.
here is a picture of the information needed

You can prove that $T(n) \geq F_n$ by induction. For $n = 0$ and $n = 1$ we have $T(n) \geq 1$ and $F_n \leq 1$. Suppose that the claim holds for $n-1$ and $n-2$. Then
$$
T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n).
$$


Convolutional Neural Networks - Where should I start from? I will soon be starting a part-time job within a start-up and I've been assigned to a project where I'll have to build a CNN that recognizes and counts people in various kinds of videos.

My CEO knows I have no training or experience in Computer Vision and he suggested that I should spend all my working hours in the first month on understanding the necessary concepts behind CNNs and then proceed with the implementation for the next two months.

I know that mathematics are a huge part of understanding the necessary concepts. I'm a CS 3rd year undergrad and my relevant studies in math are comprised of the following:

Calculus $I - IV$
Linear algebra and differential equations (didn't study partial differential equations)
Complex analysis

I've managed to pass these courses with maximum scores. Since mathematics is a very dear interest of mine, I spent a lot of time on actually understanding each and every concept I've studied so far.

So, my questions is, are there any textbooks on CNN(preferably free) you could recommend, given my experience and goal?

Also, since my mathematical training may not be enough, I would also appreciate insights (or textbooks) on what should I learn, or improve while studying the concepts behind CNNs.

I know this is a link only answer, but the question is a reference request.

Neural Networks and Deep Learning is a free online book. The book will teach you about:

Neural networks, a beautiful biologically-inspired programming paradigm which enables a computer to learn from observational data
Deep learning, a powerful set of techniques for learning in neural networks


LL1 parsing algorithm for strings generated by a given grammar How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar?

I have to design a parser for a specific grammar.
Let $G$ be the grammar described as:

$$S \rightarrow aBC $$
$$B \rightarrow bB \mid cC $$
$$C \rightarrow c \mid S $$

My approach

1. Test if the grammar is $\operatorname{LL(1)}$

First I have to determine if the grammar is $\operatorname{LL(1)}$ or not. It seems that G is  $\operatorname{LL(1)}$ because:

$\operatorname{FIRST}(aBC) \cap \operatorname{FIRST}(bB \mid cC) \cap \operatorname{FIRST}(c \mid S) =
\{a\} \cap \{b,c\} \cap \{c,a\} = \emptyset
$

2. Write a string generated by G

$s = abccaccc$

3. Design the algorithm for parsing strings

I'm getting stuck here

4. Test the algorithm for a given string

Lets test the algorithm for a given string $s = abccaccc$

Here's a possibly useful quote from Aho, Lam et al ("the Dragon Book"). (Emphasis added.)

A grammar $G$ is $LL(1)$ if and only if whenever $a \to \alpha | \beta$ are two distinct productions of $G$, the following conditions hold:

For no terminal $a$ do both $\alpha$ and $\beta$ derive strings beginning with $a$.

…


A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP Wikipedia states on sparse languages that

  There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ P/poly.

Is that correct in that it is so far proven for an arbitrary Turing reduction and not a limited P-time reduction? (Could it be true for P-time reductions also, but maybe not proven so far?) It cites this without reference. What is a reference for this?

No, what you suggest would be meaningless. The Turing reduction is also polytime. For a proof, see Theorem 3.2 in Oded Goldreich's lecture notes.


Prove $EXP \subset E^E$ I'm trying to prove $EXP \subset E^E$ (strictly).

I believe I need to construct my own $A \in E^E$ and show that $A \notin EXP$, but I cannot think of a smart way of doing that.

Thanks.

The class $E^E$ contains 2E, which is the class of problems solvable in iterated exponential time. The reason is that the E oracle can be applied on a padded input of exponential size. The time hierarchy theorem separates 2E from EXP.