Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon Let's say I give you the following array of points:

(1,1) (1,3), (2,2), (4,1), (4,3)

My (terrible) mspaint drawing of the shape that would be created by these looks like this:

How, given an arbitrary set of coordinates, can I define the edges which constitute a shape with no overlapping edges?

A copy from the highest voted answer from SO:

    Our strategy is to make a plan where we are sure that the polygon
    includes all points, and that we can find an order to connect them
    where none of the lines intersect.

    Algorithm:

    Find the leftmost points p
    Find the rightmost point q
    Partition the points into A, the set of points below pq, and B, the set of points above pq [you can use the left turn test on (p,q,?)
    to
    determine if a point is above the line].
    Sort A by x-coordinate (increasing)
    Sort B by x-coordinate (decreasing).
    Return the polygon defined by p, the points in A, in order, q, the points of B in order.

    Runtime:

    Steps 1,2,3 take O(n) time.
    Steps 4,5 take O(nlogn) time.
    Step 6 take O(n) time.
    Total runtime is O(nlogn).

    Correctness:

    By construction, all points besides p,q are in set A or
    set B. Our output polygon from line 6 therefore outputs a polygon with
    all the points. We now need to argue that none of the line segments in
    our output polygon intersect each other.

    Consider each segment in the
    output polygon. The first edge from p to the first point in A can't
    intersect any segment (because there is no segment yet). As we proceed
    in order by x-coordinate through the points in A, from each point, the
    next segment is going to the right, and all previous segments are to
    the left. Thus, as we go from p, through all the points of A, to point
    q, we will have no intersections.

    The same is true as we go from q back
    through the points of B. These segments cannot intersect each other
    because they proceed from right to left. These segments also cannot
    intersect anything in A because all points in A are below line pq, and
    all points in B are above this line.

    Thus, no segments intersect each
    other and we have a simple polygon.

  Source: Broken link

  I understand this is really late, but it might be useful for future
  viewers.


Paxos: Responding to Reordered Prepare Requests In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with:

  A promise never to again accept a proposal numbered less than n, and the proposal with the highest number less than n that it has accepted.

Therefore:

  [An acceptor] can receive two kinds of requests from proposers: prepare requests and accept requests. An acceptor can ignore any request without compromising safety. So, we need to say only when it is allowed to respond to a request. It can always respond to a prepare request. It can respond to an accept request, accepting the proposal, iff it has not promised not to.

Next, Lamport offers this optimization:

  Suppose an acceptor receives a prepare request numbered $n$, but it has already responded to a prepare request numbered greater than $n$, thereby promising not to accept any new proposal numbered $n$. There is then no reason for the acceptor to respond to the new prepare request, since it will not accept the proposal numbered n that the proposer wants to issue. So we have the acceptor ignore such a prepare request.

Suppose an acceptor receives a prepare request numbered $n$, but it has responded to a prepare request numbered $n + 1$ and accepted the proposed value (the prepare request for proposal $n$ was delayed arbitrarily by the network). The acceptor has thus promised never to accept a proposal numbered less than $n + 1$. However, we know that:

  an acceptor can always respond to a prepare request.

Therefore, the acceptor can respond with a promise never to accept a proposal numbered less than $n$ since it has already made a promise never to accept a proposal numbered less than $n + 1$, however it cannot respond to the prepare request for proposal number $n$ with the proposal $n + 1$ because it must respond with:

  The proposal with the highest number less than $n$ that it has accepted.

Since $n + 1 > n$ it can respond with no proposal. This would enable both the proposer of proposal number $n$ to choose a value, and the proposer of proposal number $n + 1$ to choose a value. However, even in the case where the proposer of $n$ sent their accept request before the proposer of $n + 1$, the accept request would be ignored because a majority has promised not to accept a proposal numbered less than $n + 1$. Thus, safety is still guaranteed. Is this correct?

Correct. Another way to think about Paxos is as a two step process:

Gaining permission to propose a value
Actually proposing a value

The act of successfully gaining permission from a majority of peers to propose a value explicitly precludes the possibility of any previous proposal from being accepted by a majority of peers.


Decidability of an regular expression I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing.

  Be A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

Answer: Create a turing machine P, this machine receives a pair where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to loop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?

When showing that something is decidable, we don't usually invoke the concept of Turing machines. Rather, we use the Church–Turing thesis that states that informally described algorithms are realizable by Turing machines. Even when describing Turing machines, there is no need to describe subroutines—that's a programming concept that you are misusing here. Finally, there is absolutely no need to add consistency checks to your code! This code isn't going to be compiled. You can assume that it is bug-free. That's why we only give an informal description, in which these messy details are missing.

Another mistake you make in describing your program is the input $W$. This input is constant, and so there is no need to include it. Also, you haven't explained how you represent $W$: the set of all strings containing $111$ is infinite.

Let me rephrase your algorithm informally. The algorithm gets as input a regular expression $r$, which it then converts to an equivalent DFA (there is no need to explicitly go through the intermediary NFA; we already know that regular expressions can be converted to equivalent DFAs). Then it goes over all strings containing $111$ in lexicographic order, and if the DFA accepts any of them, it outputs Yes.

Do you see the problem with your algorithm? It never outputs No. When the answer is No, it never halts. So you haven't shown that the problem is decidable, only that it is semidecidable (i.e. recursively enumerable).

Let me offer a different direction. Suppose I gave you a regular expression, and asked you whether the language it describes has a word containing $111$. How would you answer that? Can your answer be implemented mechanically? If so, you've found an algorithm and shown that the problem is decidable.


Do problems in P have a minimum number of YES and NO instances? If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an accept state and separate reject state are defined but I'm not sure if that applies to this case. Is it maybe possible to have only YES instances or only NO instances?

Thanks very much in advance.

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with $\Sigma$ being the underlying alphabet.

Both $\Sigma^*$ and $\emptyset$ are regular languages, and in particular, are both in $P$.

So yes - there are trivial languages are in $P$.

In fact, this argument also works when there are finitely many YES or NO instances, since finite languages are regular, and also their complements are.

So for a language not to be in $P$ it must first of all have both infinitely many YES and infinitely many NO instances.


Can Dijkstra's algorithm outperform A star, in terms of vertices checked? I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more vertices than Dijkstra's algorithm. What I'm asking however is the following. Given an A star algorithm with some heuristic which is not the heuristic returning 0, could it possibly check more vertices than Dijkstra's algorithm?

My intuition is yes, and I will show why. Consider the Figure underneath, in which we consider a large amount of discrete points in this plane, representing the vertices of the graph, and connecting arcs with cost 1 between all adjacent points, creating a grid graph. Suppose the heuristic used by A star is euclidean distance, and suppose many curved walls like the ones I drew in the middle exist in this fashion, not only the three I drew. A star in this situation would be "tricked" to go in between the walls, since the heuristic would guide it close to the point, only to find out it's a dead end (or a local optimum of some sorts if you will), and this would happen as many times as there are walls. Dijkstra would not be tricked this way. The only problem with my example here, is that Dijkstra will probably not outperform A star here. So, is my intuition wrong, or do more clever instances than this one exist in which Dijkstra can in fact outperform A star in terms of vertices checked?

No,

Dijkstra will explore all nodes with cost less than the cost of the completed path. While A* will explore all nodes with cost+heuristic less than the cost of the completed path.

Thus if the heuristic is always positive then A* will expand less or equal nodes.


how to check whether a flow network contains unique maximum flow? I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum flow or not. I have been search everything I could, and some people said run an algorithm that able to find a max flow first, then modified the edges capacity, and run the algorithm one more time to see if we get the same flow value. But this seems never works for me especially when we are given arbitrary flow network, like non-integer flow graph. How should I start a good approach? (Literally stuck for few hours)

Find a maximum flow.  Then create m new flow networks: one for each edge in the maximum flow.  In each new configuration, reduce the capacity of one of the edges to an amount just below its flow.  Find the maximum flow on each of the new flow networks.  If any of the new configurations generate the same maximum flow value as the original graph, then that new flow is also a maximum flow in the original graph.  Hence, the original maximum flow is not unique.


Understanding hashtable performance in the worst-case Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. java.util.HashMap) hashtable $O(\log n)$. Why? I cannot really understand this. If we have a uniformly-distributed hash values it should be the case that each hash bucket contains approximately the same number of elements.

Therefore, if we have load-factor (buckets_number/elements_number) say $0.5$, we guarantee the constant-time performance for search operations $O(2)$.

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations.

In the worst case however, all your elements hash to the same location and are part of one long chain of size n. Then, it depends on the data structure used to implement the chaining. If you choose a sorted array, you can do binary search and the worst case complexity for search is O(log n). If you choose an unsorted list, you have a worst case of O(n) for search. Depending on your choice of data structure, the performance (worst and average case) of insert, delete and search changes.

According to Coding-Geek.com, Java 7's HashMap implementation uses a linked list (unsorted), but Java 8 uses a balanced binary tree instead. Of course, insert/delete/search in a balanced tree of size n has complexity O(log n).


How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities I want to express the following in relational algebra:

Given a table of

PEOPLE: ID, SocietyName

Where the combination of ID and SocietyName form a key such that we could have the same ID in the table more than once but paired with a different society name.

I would like to be able to output all pairs of people, ID1 and ID2 such that they do not both attend any of the same societies. I am struggling to structure this in my head, I think I will need to rename PEOPLE to p1 and p2 say, then do some kind of join but I am not sure how to refine the output so it is only pairs where none share the same society.

Firstly $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\times \rho_{c_2(i_2, s)}People)})$ gives all possible permutations of ID pairs in the form $(a, b)$ with $a\leq b$.

By $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}$, we can gain all pairs of people who attend a same society.

So the answer is

$$\Pi_{i_1, i_2}\Big(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1,s)}People\times\rho_{c_2(i_2, s)}People)}-\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}\Big)$$


How approximate are "approximate" nearest neighbor (ANN) search algorithms? Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.

If I have a (more or less) randomly distributed point cloud what is the likelihood that I get the exact nearest neighbor given a target point within the clouds bounding box?  I know that it is dataset dependent... but does anyone have a good numerical study somewhere that shows trends?

nanoflann is a library for building KD-trees.  For the best bin first (BBF) approximate nearest neighbor algorithm (which is based on KD-trees), the authors report the following performance results:

  In 12 dimensions, for example, BBF recovers the closest neighbor 94%
  of the time (versus 59% for restricted search) while on average
  examining only 200 of the 100,000 leaf nodes. For this same case, the
  “exact” search has to examine over 2400 leaves. [Even] when the method
  does not discover the exact nearest neighbor, it does not fail by
  much.  Even up to dimension 20, the average distance of recovered
  neighbors is only 2% greater than the true NN distances.

However, that paper does not contain a formal analysis of the error bounds in this particular $\varepsilon$-approximation.


Is it feasible to generate every possible RGB image? This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent resolution then that of all the atoms we estimate are visible in our universe.

This makes sense because an image of a decent resolution (like the image displayed your computer monitor) should be able to contain every picture imaginable, every frame from every movie ever made and never made. It would contain every correct and incorrect mathematical equation. Or even every book/webpage that will exist or can exist. It's intriguing to think it would be possible to generate every possible image because it contains all knowledge but also all anti-knowledge which means there is a lot of stuff to sift through including lots of random noise.

The only other research into this topic that I could find is this art project, where they wrote some code to generate all 15x10 pixel black and white images which is estimated to take approximately 46 quinvigintillion or 4.6x1079 years to complete.

So is it feasible to generate every possible RGB image (of a decent resolution)?

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly.  For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system.  (There's something wrong with your reasoning if you've concluded it's reasonably possible to enumerate all such images.)


Error solving the next recurrence: $T(n)=7T(n/2)+n^2$ Hello I'm trying to solve this recurrence with the method that says the teacher that when you get to
\begin{align*}
T\bigg(\frac{n}{2^{k}} \bigg)
\end{align*} you do
\begin{align*}
\frac{n}{2^{k}} &= 1 \qquad (\text{by definition})\\
k &= \log_{2}(n)
\end{align*}

\begin{align*}
T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &=
7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &=
7^{k}T\bigg(\frac{n}{2^{k}}\bigg) + \sum_{j=1}^{k-1} 7\frac{n}{2^{j}}+n^{2}\\ &=
7^{\log_{2}(n)} + \sum_{j=1}^{\log_{2}(n)-1} 7\bigg(\frac{n}{2^{j}}\bigg)^{2}+n^{2}\\
\end{align*}

After developing, I have left
\begin{align*}
7^{\log_{2}(n)}+n^{2}
\end{align*}
But I know the solution is
\begin{align*}
n^{\log_{2}(7)}
\end{align*}

What am I doing wrong?

Some of your sums have typos, but you already have the right answer.

Here's a useful fact about logarithms:

$a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$

Apply it to your answer, keeping in mind that $\lg 7 \approx 2.8 > 2$:

$O(7^{\lg n} + n^2) = O(n^{\lg 7} + n^2) = O(n^{\lg 7})$


Turing Machine construction How should I go about building a Turing machine for the following language:

$$L = \{  a^ib^j \in (a,b)^* \mid i \le j \le 2i \} $$

I know how to construct a Turing machine for $\{  a^nb^nc^n \mid n \in \mathbb N \}$ but don't really where to start for the one above.

How would you construct a TM for $\{a^i b^j \mid i \le j\}$? Well, the easiest solution is to keep removing letters on both sides until you run out of $a$s or $b$s. At this point you can look at what you are left with and decide whether $i \le j$ was initially true.

Now, what if, instead of removing $a$s, you were moving them somewhere to keep for later use? This way you’d be able to test for $i \le j$ and still have all your $a$s available. By doing something similar with all those saved $a$s and the remaining $b$s you will be able to check the second condition, $j \le 2i$.


Is transitivity required for a sorting algorithm Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators?

Background:

A sorting algorithm generally sorts the elements of a
list according to a comparator function C(x,y), with

\begin{array}{ll} C(x,y) = \begin{cases}
-1  & {\text{if}}\ x\prec y   \\ 0 & {\text{if}}\ x\sim y \\
+1 & {\text{if}}\ x\succ y  \\ \end{cases} \end{array}

The requirements for this comparator are, as far as I
understand them:

reflexive: $\forall x: C(x,x)=0$
antisymmetric: $\forall x,y: C(x,y) = - C(y,x)$
transitive: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
C(x,y) is defined for all x and y, and the results depend only on x and y

(These requirements are always listed differently accross different
implementations, so I am not sure I got them all right)

Now I am wondering about a "tolerant" comparator function, that accepts numbers x,y as similar if$ |x - y| \le 1$:
\begin{array}{ll}
C(x,y) = \begin{cases}
-1  & {\text{if}}\ x\lt y-1   \\
0 & {\text{if}}\ |x - y| \le 1 \\
+1 & {\text{if}}\ x\gt y+1  \\
\end{cases}
\end{array}

Examples: both [ 1, 2, 3, 4, 5] and [1, 4, 3, 2, 5] are correctly sorted  in ascending order according to the tolerant comparator ($C(x,y) \le 0$ if x comes before y in the list)
but [1, 4, 2, 3, 5] is not, since C(4,2)=1

This tolerant comparator is reflexive and antisymmetric, but not transitive.

i.e. C(1,2) = 0 , c(2,3) = 0, but C(1,3) = -1, violating transitivity

Yet I cannot think of any sorting algorithm that would fail to produce a "correctly sorted" output when given this comparator and a random list.

Is transitivity therefore not required in this case? And is there a less strict version of transitivity that is required for the sorting to work?

Related questions:

Why is antisymmetry necessary for comparison sort? (about antisymmetry)
Sorting algorithms which accept a random comparator (about a random C(x,y))
OrderBy with a non-transitive IComparer (about the c# sort algorithm, by me)

You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator?

The answer: Of course.  You can run any algorithm with any input.

However, you know the rule: Garbage In, Garbage Out.  If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output.  In particular, there is no guarantee that the output will be "sorted" according to your comparator.  So, running a sorting algorithm with a non-transitive comparator is not likely to be useful in the way you were probably hoping for.

As a counterexample, running insertion sort on the input list $[3, 2, 1]$ using your comparator would leave the list unchanged -- yet the resulting output list is not in sorted order (according to your comparator).


Complexity of class finding selection of entries in matrix Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, for each column, also exactly one is circled, and such that all entries circled are only $x$ (if such a circling of entries exists), what complexity class does this belong to? Thanks!

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$.
There are various algorithms that compute the maximum cardinality matching. For example, The Hopcroft–Karp algorithm runs in $O(\max(|E|\sqrt {|V|}, |V|^2)$.
So, we can say that the complexity class of the problem in the question is in $O(n^{2.5})$ since $|E|\le n^2$ and $|V|= 2n$.


Finding maximum takes at least $\lceil n/2 \rceil$ comparisons We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.

I want to prove that finding the maximum in $A$ (that is, outputting the index at which the maximum is found in $A$) takes at least $\lceil n/2 \rceil$ comparison by assuming that there exists an algorithm that can find the maximum in at most $\lceil n/2 \rceil -1$ comparisons.

I tried assuming that there is such an algorithm, then took as an initial input some particular array $A$ (just a basic one, namely $1,2,3,\cdots,n$) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.

I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.

I thank you in advance!

In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A_1,A_2$ with no edges between them. It is consistent that all elements in $A_1$ are smaller than all elements in $A_2$, in which case the maximum is in $A_2$. Similarly, the maximum could be in $A_1$. The algorithm cannot tell which is which, hence will be wrong on at least one of these scenarios.

The exercise was probably aiming at the following simpler argument: if less than $\lceil n/2 \rceil$ comparisons are made, then there is at least one element which is not compared at all. Hence for all we know, it could be the maximum, or the minimum (if these are different!); indeed, it could be at any position at all. This argument works as long as $n > 1$.


Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3) Please bear with my unhelpful typesetting.

My question is regarding well known FLP paper
Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson

While discussing Lemma 3, in 4th paragraph, authors make an assumption I am unable to understand.

The assumptions are -

1) There exist two neighbour configurations $C_0$ and $C_1$ both from set $\mathscr{C}$ (which contains configurations on which event $e$ was never applied). So far so good. Till this part we never discuss about valency of $C_0$ and $C_1$.

2) Next assumption is - From $C_0$ taking $e$ causes to go to $D_0$ while from $C_1$ taking an $e$ causes to go to $D_1$.

3) $D_0$ and $D_1$ do not have same valency. (Both are not 0-valent/1-valent simultaneously)

The proof of lemma goes on and uses commutative property to prove that set $\mathscr{D}$ is bivalent.

While I have no problem with rest of proof, I am failing to understand why all three parts of the assumptions should be considered consistent to each other. It is these assumptions (especially 2 and 3) that lead to contradiction.

Here is clarification regarding points 2 and 3.

To me it seems that from the assumption, $e(C_i) = D_i$, we introduced the contradiction by saying that $D_0$ and $D_1$ are of different valencies. How can one justify that this choice is valid? Why should not I think that both $D_0$ and $D_1$ should be of same valency? How do I prove that set $\mathscr{D}$ will still remain bivalent even if $D_0$ and $D_1$ are of same valency?

In other way, question would be, how to prove that all three points mentioned above can actually arise in some consensus protocol with assumptions given in lemma.

The fact that $e(C)$ followed by $e'(e(C))$ or vice-versa; $e'(C)$ followed by $e(e'(C))$ should result in same configuration is achieved due to commutativity, and we knew this before hand. My point is, we specifically chose a scenario which was contradicting in itself and does not does anything more in the bigger picture to draw a contradiction of the statement, that $\mathscr{D}$ is univalent.

The paper says

  By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$

Here is a proof:

The set of configurations forms the nodes of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following any edges labelled $e$. $\mathscr{D}$ is the set of nodes reachable from $\mathscr{C}$ by paths labelled $e$.

Let $i$ be the valence of $e(C)$: $e$ applies to $C$ by assumption; it is in $\mathscr{D}$ by definition; it is univalent by the assumption from paragraph 2. Let $D$ be a $(1-i)$-valent node in $\mathscr{D}$, which exists because paragraph 3 shows that $\mathscr{D}$ has both 0-valent and 1-valent configurations. By the definition of $\mathscr{D}$, there must be some node $P \in \mathscr{C}$ such that $D = e(P)$. By the definition of $\mathscr{C}$, there is a path from $C$ to $P$ consisting of nodes in $\mathscr{C}$.

The valences of $e(C)$ and $e(P)$ are unequal. For every node $V$ along the path from $C$ to $P$, $e(V) \in \mathscr{D}$, so every one is univalent. Thus, there must be two adjacent nodes along the path with different valences under $e$. These constitute $\{C_0, C_1\}$.


Combinations and Permutations of M sets of distinct items? I'm wokring on this problem for a while. I want to know:

The correct name of this problem, so I can look it up in textbooks\online.

Here is the problem descirption:

The (un-ordered) combinations to be generated are:

of 1 item size:   {a1}, {a2} .... {c4}
of 2 items size:  {a1, b1}, {a1, b2} ... {b2, c4}
of 3 items size:  {a1, b1, c1}, ... {a3, b2, c4}

The question is: Given any number of sets M where each set has distinc number of items, How many (un-ordered) combinations are there of size 1, 2, ..., up to M? And how to generate those combinations?

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to

for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2.
for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of size 2.
for each element in $B$, pair it with each element in $C$. This gives us $|N_B||N_C|$ combinations of size 2.

In total, this gives us as $ |N_A||N_B|+|N_A||N_C|+|N_B||N_C| = 3\times2 + 3\times4 + 2\times4 = 26$

What we have done above is to take all possible combinations of the sets in $M$ (set combinations of size 2 are $AB, AC, BC$), taken the product of all their sizes, and finally added them up.

In general, given $n$ sets in $M$, and we want to know the number of $k$ sized combinations. The high-level algorithm would be as follows

for each k-sized set combination of sets in M
  multiply the sizes of all the sets in the k-size set combination
  add this product to the final result

This can be written briefly as
$$ \sum_{\substack{S \subseteq M\\|S|=k}}\prod_{X\in S}{|X|}$$

Now, to generate all unordered combinations of size $k$, we follow the same steps as the above algorithm, but instead of taking the product of set sizes, we perform a cross product on all the sets in each $k$-size set combination.

Combinations(M,k):
  if |M| == 1
    return { {e} | e in any set of M }

  M[1] = first set in M

  if |M| > k
    Result = Combinations(M\{M[1]} ,k)
  else
    Result = {}

  Temp = Combination(M\{M[1]},k-1)

  for each element e in M1:
    make a copy of Temp called Dummy
    to each set in Dummy, add e
    add all the elements in Dummy to Result

  return Result


NEXP = Σ$_2$ ⟹ NEXP = MA? Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?

(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \Leftrightarrow \mathsf{NEXP} = \mathsf{MA}$.)

This is not known.

$NEXP = \Sigma_{2}$ means that $NP$ and $NP^{NP}$ are different. But, $MA$ seems too weak to reach that high to catch $NP^{NP}$.


Avoiding "side effects" in recursive functions I am writing a function to find the intersection between two sets.

The non-functional requirements of the assignment include avoiding "side effects".

function intersection(a, b) {
  return helper(a, b, []);
}

function helper(a, b, c) {
  if (a.length == 0) {
    return c;
  }

  if (b.contains(a[0])) {
    return helper(a.slice(1, a.length), b, c.concat([a[0]]));
  }

  return helper(a.slice(1, a.length), b, c);
}

Would mutating the argument c in the above code be considered a side effect?

The specific assignment is written in OCaml, so, though the above example is in an imperative language, I want to stay true to the spirit of functional programming.

Please don't provide any alternate solutions to the problem.

If the helper function mutated the object c (which concat doesn't do in JS), then helper would have that side effect. But overall your intersection function wouldn't have any side effect that I can see, as the c array doesn't exist outside of it.

PS: concat returns a new array every time. The original c array is unchanged.


How does one program crashing not crash the entire system? In Windows, if you write a random assembly program that has a random jump to an address that doesn't exist, the program crashes and Windows says something went wrong with the program.

Since each computer system is essentially a constant execution of assembly, how does the one program crashing not cause the entire system to crash with it?

Probably you should read something about OS memory management.

If the program is running it has memory which is readable, memory which is writable and both. If it tries to go beyond its permissions, OS kills it and reports to you in a way you call "crash".

That's all was very roughly speaking.


Finding path that minimizes largest of the sum of weights of each group in a directed multigraph Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group?  All weights are non-negative integers in the range 0..30,000.

Let me put an example for $n=2$ groups to understand it better:

If we were to find the shortest path from s to t of this multigraph, that would be easy. Just run a Floyd-Warshall algorithm and in case there is more than 1 edge for a pair of vertices, get the one with lowest weight.
The shortest path in this case would be getting all the red edges (s-1-2-t)

This would give us 2 groups with following weights:

Blue: 0
Red: 5+5+5 = 15

So the largest of this groups is max(0,15) = 15

But in this problem, we want to minimize the largest of the sum of weights of the two groups, so the path that minimizes this in this example is s-1-2-t (red-red-blue).

This would give us 2 groups with following weights:

Blue: 10
Red: 5+5 = 10

So the largest of this groups is max(10,10) = 10

I guess this problem is NP-hard, because the partition problem can be reduced to this problem. Given an instance of partition, i.e., a multiset $S$ with $k$ elements, just build a graph with $k+1$ vertices and two edges between each pair of consecutive vertices (both edges having weight equal to the corresponding element of $S$; one red, and one blue).  Or, you can reduce $n$-way multi-way partition to this problem.  Again, build a graph with $k+1$ vertices, and between each pair of consecutive vertices add $n$ edges (one for each group in the partition problem) with weights equal to the numbers in the multiset. Here is a diagram that tries to explain this reduction:

But just like there is an easy greedy approximation for the partition problem, there might be something simple for this problem aswell.
To be honest, I don't even know how to approach this problem. Any ideas?

And even though it would be great to have a general case approximation, an approximation for the case where n=2 groups would be enough for me right now.

At least for the case $k=2$, there is an efficient algorithm to solve your problem.  Suppose all weights are integers in the range $0..\alpha$.  Then there is an algorithm whose running time is $O(\alpha VE \log^2(\alpha V))$.  In your case, $\alpha=30,000$.

How does this algorithm work?  I'll show that, when $k=2$ and when the solution is known to be at most $\beta$, there is an algorithm with running time $O(\beta E \log (\beta V) \log \beta)$.  It's easy to see that we must have $\beta \le \alpha V$, so this will imply the claimed result (using the fact that $\log(\alpha V^2) \le 2 \log(\alpha V) = O(\log (\alpha V))$.

The algorithm works by reducing to the decision version of the problem.  Given an instance of the problem and a proposed $\gamma$, we test whether there exists a solution that is at most $\gamma$ (i.e., a path from $s$ to $t$ using red edges that total at most $\gamma$ and blue edges that total at most $\gamma$).  Then we do binary search on $\gamma$.  This will require $O(\log \beta)$ solutions of the decision problem, so it suffices to solve the decision problem in $O(\beta E \log (\beta V))$ time.

How do we do that?  We make $\gamma+1$ copies of each vertex $v$; call these copies $(v,0)$, $(v,1)$, ..., $(v,\gamma)$.  Intuitively, the new vertex $(v,i)$ corresponds to a state that can be reached if you can reach vertex $v$ from the starting point along a path where the sum of the blue edges is at most $i$.  Now we'll construct a new graph on these $(\gamma+1)V$ vertices as follows.  For each blue edge $u \to v$ with weight $w$ in the original graph, we add edges $(u,i) \to (v,i+w)$ for each $i$.  For each red edge $u \to v$ in the original graph, we add edges $(u,i) \to (v,i)$ for each $i$.

Once this larger graph is constructed, we check whether there exists a path from $(s,0)$ to any $(t,i)$ with length at most $\gamma$.  This can be done using Dijkstra's algorithm.  Since the larger graph has $O(\gamma V)$ vertices and $O(\gamma E)$ edges, the running time of Dijkstra's algorithm in this graph will be $O(\gamma E \log (\gamma V))$.  Since $\gamma \le \beta$, the claimed result follows.

This doesn't contradict your NP-hardness result, as your NP-hardness result uses very large integer weights, while the running time of this algorithm is proportional to the weights themselves (rather than to the number of bits needed to represent the weights).  Or, to put it another way, this algorithm is a pseudopolynomial time algorithm, but not a fully polynomial time algorithm.


Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better  states  when  there  is  no  available  heuristic. It uses nested levels of random games in order to guide the search. It consists in two functions : nested(position, level) and sample(position)

The basic sample function just plays a random game from a  given  position,  we  use  the  function play(position,  move) which plays the move in the position and returns the resulting position.

int sample (position)
1  while not end of game # I don't understand why did he wrote a while
2    position = play (position,random move)
3  return score

If it just played a random game from a given position, shouldn't it have been without a while and only this : position = play (position,random move) ? And where does he get the score ?

The  Nested  Monte-Carlo  Search  function  plays  a  game, choosing  at  each  step  of  the  game  the  move  that  has  the highest score of the lower level Nested Monte-Carlo Search. At each step the algorithm

tries all possible moves
plays a nested search at the lower level after each move
memorizes the move associated to the best score of the lower level searches.

As the samples are randomized, it is not guaranteed that a nested search will always improve on previous searches or  even  lower  level  searches.   In  order  not  to  lose  the  best moves of the best sequence found by a previous search, the algorithm memorizes the best sequence. If none of the moves improve on the best sequence, the move of the best sequence is  played,  otherwise  the  best  sequence  is  updated  with  the newly found sequence and the best move is played:

int nested (position, level)
1  best score = -1
2  while not end of game
3    if level is 1
4      move = argmax_m (sample (play (position, m)))
5    else
6      move = argmax_m (nested (play (position, m), level - 1))
7    if score of move > best score
8      best score = score of move
9      best sequence = seq. after move
10   bestMove = move of best sequence
11   position = play (position,bestMove)
12 return score

In the following example he claims that if depth first search has one chance out of two of choosing the wrong move at the root, A level 1 Nested Monte-Carlo Search will always find the best score.

Yet I don't get why for the first step. I have some difficulties when starting playing move = argmax_m (sample ( play (position, m)))
$$move = \underbrace{argmax_m (\overbrace{sample ( \underbrace{play (position, m)}_{(1)})}^{(2)})}_{(3)}$$

so we move first for a given unkown position m. I believe it is
chosen by argmax_m. Yet, how can it chose between both nodes ? Where
do we test the score ?
Why randomness here ?
Where can we test the argmax_m ?

You've asked many questions.  The usual rule on this site is to ask one question per post.

The definition of sample is correct.  play evaluates where you end up after making a single move.  sample evaluates the result of a game where both players randomly choose a move.

In other words, imagine a particularly stupid strategy, where both players randomly pick a move (blindly, without taking into account the position or any other strategy; it's purely random) at each step.  Starting from position, you could simulate playing out a full game and see what happens.  The resulting score (which player won) gives you a very crude approximation of how you should evaluate position.  For instance, suppose in that random playout, the first player happens to win.  Then we might suspect that position is better for the first player than the second player.  Obviously, this is a crude approximation, but it's just a start.  And that's what sample computes.

So that approach computes the level-0 approximation of the evaluation of each position.

Of course, given a way to compute an evaluation score for any position, that gives you a way to play the game: whenever it is your turn, look at all possible moves you could make, evaluate the resulting position, and pick whichever move takes you to the position that looks most favorable for you.  That's what the logic is doing with the argmax.  So, this gives you a level-0 strategy.

Now we're ready to talk about how to compute a level-1 approximation of the evaluation of each position.  Basically, we simulate doing a playout -- we simulate playing the game -- but now rather than using a blind random strategy, we use a slightly smarter strategy.  In particular, each player uses the level-0 strategy described above to decide how to move.  So now simulate a game where both players are using the level-0 strategy, starting from position, and keep going until the end of the game.  See which player wins.  This is your level-1 evaluation of position.

You can use the level-1 evaluation to form a level-1 strategy: always make the move that leads to the position whose level-1 evaluation is as favorable as possible.

And now you can probably see how to use this idea to form a level-2 evaluation, and a level-2 strategy, and a level-3 evaluation, and so on.  That's the idea of nested Monte Carlo.


From FACTOR To KNAPSACK If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded knapsack problems since two factors can be viewed as one value, say within the set for the knapsack problem, and the other being the number of copies of the first factor?

FACTOR 15; 3, 5

Unbounded KNAPSACK with value of 15 and the set of all integers; {5,5,5} andor {3,3,3,3,3}
Would this mean FACTOR was NP-Complete?
Would solving unbounded knapsack problems in polynomial time in this way prove P=NP?

(1) NP-complete only contains problems that can be answered by Yes or No, which are called decision problems. So FACTOR is not an NP-complete problem even your reduction is correct. In fact, if your reduction were correct, it proves that FACTOR is NP-hard.

(2) If you want to prove the NP-hardness of FACTOR by reducing UKP (unbounded knapsack problem) to it, you should find an integer $M$ (in polynomial time) for each instance $I$ of UKP and show that the answer of $I$ can be gotten (in polynomial time) using the factorization of $M$.

In your proof, you can only solve a specific subset of UKP instances by FACTOR, so it is not a correct reduction.


What are the definitions of syntax and semantics? For a formal language $L \subseteq \Sigma^*$ over an alphabet
$\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax

  The syntax of a formal language is its structure, and is specified by
  a formal grammar of the formal language.

From http://en.wikipedia.org/wiki/Syntax_%28logic%29

  In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning

How do you define the "structure" of a formal language,
and therefore define the syntax of a formal language? Ideally define
them formally or mathematically?
The syntax of a formal language should be defined formally, because it pertains to the formal language which is defined formally as a subset of $\Sigma^*$, right?
Raphael once said that the syntax of a formal language is
the language itself. Is it true?
From http://en.wikipedia.org/wiki/Syntax_%28logic%29

  Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formulas of a formal system.

We shouldn't equate the two concepts: the syntax of a formal language, and a formal grammar of a formal language, should we?

Note that a formal language can have several formal grammars that all generate the language. When a formal language has multiple different formal grammars that generate it, is the syntax different for different grammar?

Also a formal language may not have a formal grammar that can generate it, and still syntax should make sense to such a formal language?

For a non-formal language $L'$  over an alphabet  $\Sigma$,

What are
the definitions of its syntax and its semantics, ideally
mathematically?
When defining its syntax, how do you distinguish what pertains to
the formal part of the language, and what is not?
Can its semantics be defined as a mapping $L' \to S$ where $S$ is some other
set?
Maybe, for example, when $L'$ is a programming language?
Maybe, for example, when $L'$ is a natural language, such as English?

Thanks and regards!

To beging with, the expression "formal language" may refer to formally
defined sets of string as considered in the theory of automata and
formal languages. I shall write that "Formal Language" with capital
first letters. But "formal language" may also refer to some kind of
language that is intended for expressing meaning, but is precisely
defined mathematically. I shall rather call it formally defined language.

A first remark is that formally defined languages are similar to natural
languages (vernacular), in the sense that both are used to convey
meaning through representations of that meaning.

This is the fundamental issue. We have to convey meaning, to others,
or to ourselves (when we take notes). Meaning can concern all sorts of
things, some finite, some infinite, possibly about strange domains of
human imaginations, such as real numbers, or the set of all sets.
But we can always do that only through representation. The
representation may be a linear sequence of symbols. It may also be a
spatially organized collection of symbols. It may be drawings, or data
structures in a computer, or sound stream, or gestures. It is
physical.

To answer the question in a nutshell, and in a very general way: the
organisation of the physical representation of discourse is syntax,
while semantics is the meaning conveyed, and the way it is derived
into, or from, the representation.

A major characteristic of syntax is that syntactic representations
are finite: they convey a finite amount of information. This is true
of pictures that can de digitized with finite precision to convey what
they are supposed to convey, But the best example is one of the most
common form of representation: the written text. If one takes all the
symbols used for writing as digits in a proper base, any written text
may be read an integer number, which is a finite object. This does not
prevent the discourse from being about infinite objects, or whatever
else, including ghosts, leprechauns, the Zeta function, the turtle
that carries the planet on its back and the last Sunday before the
Big-Bang. And, this does not forbid having an infinite number of
representations, of sentences of the language.

But how is syntax connected to semantics? How do we associate a
meaning with physical representation. The most basic way is to
associate a specific meaning to specific representations, and learn
these associations. This is basically how ideographic writing gets
started. But it has limitation: you can define only a finite number of
meanings in this way. An important aspect of language is to
be able to handle unbounded number of meaning by associating in an
organized way the representation of elementary meanings.

So syntax is not just a collection of elementary representations, but
also a collection of rules to associate them to make more complex
representations. Elementary representations correspond to elementary
meanings, and rules associating them indicate how the simpler meanings
can be composed to make more complex meanings.

A simple example is the way formally defined languages are
specified in mathematics (I am simplifying somewhat, skipping over
some technical issues, parsing technology for example). The syntax is
defined as a set of string over an alphabet. This set is often defined
by a context-free grammar. that provides rules to create strings on
the alphabet. The rules also associate strctures to strings: the
parse-trees. The definition of semantics associate a value (of
whatever domain) to the elements of the alphabet, and associate
operations on these values to the rules of the grammar. This define a
homomorphism from the set of string in the context-free syntax to the
set of values in the semantic domain. (Note that, sometimes, the syntax is directly defined as a set of trees.)

So we have an infinite set (the syntax Formal Language) of finite
representations (string or sentences of the formal language) which has
a finite definition/description (the Context-Free grammar). The
semantics is defined by specifying a domain of values, and both the
domain and the values in it may be finite or infinite entities. For example
a mathematical text, though finite, can talk about real numbers which
are a continuously infinite set of infinite entities (in the sens that
most reals do not have a finite description). Furthermore, the mapping
is finitely defined, by associating a function with each grammar rule.
A rule composes subpart of the text into a larger text, and the
associated function composes the meaning of these subparts into a
meaning for the larger text.

Not all kinds of Formal Languages may be appropriate for syntax
definition. They must provide some structure to the language strings
that can be used to define the semantics mapping. Besides context-free languages and grammars, there are
many other kinds of Formal Languages and Formal Language Definitions
that can provide structure for syntax strings (tree adjoining grammars
for example). They are mostly used in computational linguistics for
natural language. Other mechanisms, such as attributes or features on
grammar symbols, can be added both to specify the strings of the
languages or the semantics mapping (but it may be disputed whether
they should be considered syntax or semantics).

However, as written earlier, syntax need not be composed of strings of
symbols. Other structured representations can be considered, such as
graphs, or sound stream. An interesting example is abstract syntax
trees that can represent programs of a programming language as tree
structures. Some programming systems and development environments
actually consider the abstract syntax tree (AST) as the primary
representation of programs, and provide tools to create programs
represented directly as AST, possibly without ever producing a string
representation in some cases. The language Lisp was probably the first to do that.
This is also very frequent in proof systems and other symbolic
computation systems that manipulate mathematical formulae, which
remain represented by tree structures, or even other data types.

This shows that different representation systems, different syntaxes,
may be used to represent the same semantic structures. Actually, when
these representations can easily be translated into each other, while
preserving semantic meaning, they are often considered the same
language. In other words, the same language may have multiple
syntactic representations, including multiple string syntaxes.  But
the semantics preserving intertranslatability shows that these
different representations are structurally similar. Another obvious
example is natural language, that can exist as text or as speech.

Conversely, given a syntax, it is possible to combine it with
different semantic interpretations, i.e. different semantic mappings.


Closest point in embedded simplicial complex Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded in $\mathbb R^3$ ($n=3$) and one-dimensional chains of line segments ($k=1$) in $\mathbb R^n$.
Given many points $\{x_i\}_{i=1}^M\subset \mathbb R^n$, is there a data structure/algorithm for efficiently answering closest point queries of the form $\min_{y\in\mathcal S} \|x_i-y\|_2$?
I'm looking for a generalization of methods that handle, e.g., closest point on a triangle mesh.  Pointers to existing implementations are also much appreciated!

If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries.
For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-Tree work fine with millions of points.
C++ implementations are available from libSpatialIndex, Boost R-Tree, PH-Tree C++, and many others.
For Java implementations, have a look at my TinSpin Index Library or any other one.
Disclaimer: I am the developer of TinSpin and PH-Tree.
EDIT
I assumed by point you mean vertex, my mistake. I think you can adapt the approach if you are looking for nearest points on any simplex: Instead of storing vertices in the index, you can store the 2D/3D/$k$D bounding boxes of all geometries (vertices/lines/triangles/..) in the tree. Then there are two options:

Use a nearest neighbor search to go through all bounding boxes and their elements to calculate the actual distance. You will have to check and compare these distances until the distance of the bounding boxes becomes larger than the current closest simplex you could find.
Implement a custom distance function that returns nearest neighbors sorted by their closest point. This may require in depth knowledge of the index you are using.

This should still result in a $O(log(numberOfSimplexes))$ unless there are a lot of elongated geometries with overlapping bounding boxes. For example, a bad case would be a spherical data space with all geometries being lines that represent the diameter.
By intuition, I think R-Trees or the PH-tree are best suited for this kind of search.
I have little experience with this, but for larger dimensionality $k$, the bounding box approach may work less well because boxes in $k$-dim space tend to become very large, so they may be a lot of overlap (or maybe not, because the whole dataspace is also growing exponentially?).
In any case, it can make sense to break up 'flat' objects (such as line segments in 3D) in to multiple segments in order to represent them with a chain of smaller bounding boxes instead of one large bounding box. Having several small bounding boxes if more efficient than one large one.


Gate/transistor number and program length measures of computational complexity? Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity?

For example, problems are characterized by O(.) measures of time and space complexity. Space complexity tells me the amount of memory needed but not the number of computational components needed. We assume a Turing machine and count the number of steps performed. But in practice, the number of instructions available, and the level of parallelism have some non-linear relationship with the amount of time needed to solve a problem. Amdahl's law deals with speeding up one part of the problem. On a more general level, there could be at least an empirical or conjectural observation of how physical hardware like NAND gates or transistors scale with problem size or speed.

Thinking in terms of program size, there is Kolmogorov complexity defined as the shortest program that will generate a sequence or other data object. But what about the min. program that will solve a problem? Has anyone defined or used Kolmogorov-like complexity to characterize a problem rather than information content?

Two well-known books in this research area are:

  Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984

and

  F. Tom Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, 1991.

The connection between space and time complexity is due to the finite speed of communicating across distance.  Thus, a lot of the interesting results are about how various communication networks can (or cannot) be embedded in 3-dimensional space.


Why are PTAS-Reductions used to establish APX-Hardness? What's the intuition for PTAS reductions instead of approximation preserving reductions or something of that ilk? I'd expect APX-Hardness to mean something like "finding a constant factor approximation for this problem is as hard as finding a constant factor approximation to any problem in APX" but having just a PTAS reduction from A to B isn't strong enough to imply a constant factor approx to B can be converted into a constant factor approx of A.

Let me correct two misconceptions in your question:

$PTAS$-reductions are approximation-preserving
$APX$ is the class of problems that have constant-factor approximations

The big open question isn't whether $APX$ problems have constant-factor approximations (by definition, they do), but whether they have polynomial time approximation schemes. The meaning of $APX$-complete is "As hard as any problem in $APX$ to find a polynomial time approximation scheme for". A $PTAS$ from $A$ to $B$ reduction allows any polynomial time approximation scheme for $B$ to be used for $A$.


Generating all words of length n in a CFG Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$?

Preferably efficient in time, and with low memory usage.

I'm only interested in the words themselves - not their derivations. If the language is ambiguous and has multiple derivations for a word it would be nice if there is an efficient way to make sure each word is only output once.

The order of the words is irrelevant. If time can be saved by preprocessing the grammar $G$ (e.g. to CNF) then that's perfectly fine.

I can suggest one possible algorithm based on memoization of a rather naive recursive algorithm, with some corner cases cleaned up.  I don't know if there might be a better approach.

Convert the grammar to Chomsky normal form.  Let $L(A,\ell)$ denote the set of words of length $\ell$ in $L(A)$ (i.e., all words of length $\ell$ that can be derived from $A$).  We'll construct an algorithm to compute $L(S,n)$ recursively, where $S$ is the start symbol of the grammar.

The recursive algorithm for computing $L(A,\ell)$ works as follows. If we have a rule $A \to \varepsilon$ and $\ell=0$, add $\varepsilon$ to the output; for each rule $A \to a$, if $\ell=1$, add $a$ to the output; for each rule $A \to BC$ and each $0 \le i \le \ell$, add $uv$ to the output for each $u \in L(B,i)$ and $v \in L(C,\ell-i)$.

Memoize this algorithm.

As an optimization, when considering a rule $A \to BC$, only iterate over $i$ such that $0 \le i \le \ell$ and $L(B,i)$ is non-empty and $L(C,\ell-i)$ is non-empty.  This prevents generating a long list of candidate values for $u$ that you'll never use.  (You can precompute whether $L(A,i)$ is empty or not, for each symbol $A$ and each $0 \le i \le n$, in $O(n^2 |G|)$ time using dynamic programming, where $|G|$ is the number of rules in the grammar.)  Or equivalently, when you implement the recursive algorithm, implement it using lazy lists, so that the output of $L(A,\ell)$ is a lazy list with elements generated on demand.

With this optimization, I think the total running time of this algorithm should now become something like $O(m n^2 |G|)$, where $m$ is the total number of words of length $n$ in $L$ and $|G|$ is the number of rules in the grammar.  Maybe there is a tighter bound on the running time: this might be pessimistic.


How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function? Like in the title the following equation:

$F(n)=F(n-1)+F(n-2)+f(n)$, with $F(0)=0, F(1)=1$
$f(n)=f(n-1)+f(n-2)$, with $f(0)=0, f(1)=1$

I don't know how to solve this. The $f(n)$ is basically just $F(n)$, but
then I have
$$F(n)=F(n-1)+F(n-2)+F(n) \Rightarrow F(n-1)+F(n-2)=0$$
and I cannot go anywhere from this.

$f(n)$ is the well-known Fibonacci sequence.

Let $\alpha=\frac{1+\sqrt5}2$ be the golden ratio and $\phi=\frac{1-\sqrt5}2$. It is shown here that
$$f(n)=(\alpha^n-\phi^{n})/\sqrt5$$

Gnasher729 conjectured that $F(n) \approx 0.72 * n * f(n)$. Following that clue, we can find the following identity holds for all cases we tested by trial and error.
$$F(n)= nf(n) - (n-2)f(n-2) + (n-4)f(n-4) - (n-6)f(n-6) + \cdots$$
where the sequence of summands goes on as long as the summand makes sense.

How to prove that long formula? We can observe it implies for $n\ge2$,
$$ F(n) = nf(n) - F(n-2).$$

Let us prove that simple recurrence relation of $F(n)$ by induction on $n$.

The base cases when $n=2$ and when $n=3$ is easy since f(2)=1, f(3)=2, F(2)=1+0+1=2 and F(3)=2+1+2=5.

Suppose it is true for $n\le k$, where $k\ge3$.
$$\begin{aligned}
F(k+1) =& F(k) + F(k-1) + f(k+1)\\
=& (kf(k) - F(k-2)) + ((k-1)f(k-1) - F(k-3)) + f(k+1)\\
=& k(f(k)+f(k-1))-f(k-1) - (F(k-2)+F(k-3)) + f(k+1)\\
=& kf(k+1)-f(k-1) - (F(k-1)-f(k-1)) + f(k+1)\\
=& (k+1)f(k+1)- F(k-1)\\
\end{aligned}$$

Now that we have proved that simple recurrence relation of $F(n)$, it is immediate to prove that long formula, which can also be stated succinctly as

$$F(n)=\sum_{0\le i\lt n, i\text{ even}}(-1)^{i/2}f(n-i)$$

Interested readers may enjoy the following exercises, roughly in the order of increasing difficulty.

Exercise 1. Given the above formulas for $f(n)$ and $F(n)$, show that $F(n)=\Theta(n\alpha^n)$.

Exercise 2. Given the above formulas for $f(n)$ and $F(n)$, show that $$\lim_{n\to\infty}\frac{F(n)}{n\alpha^n}= \frac1{1+\alpha^{-2}}\approx 0.7236$$

Exercise 3. Find a close formula for $F(n)$.


Can counting problems have optimal substructure? I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties:

optimal substructure
overlapping subproblems

I stumbled upon an article which states that:

  Counting problems cannot exhibit optimal substructure, because they are not optimization problems. Instead, the kinds of counting problems that are amenable to DP solutions exhibit a different kind of substructure, which we shall term disjoint and exhaustive substructure.

Is this a valid claim? The Wikipedia article on Dynamic Programming states that:

  In addition to finding optimal solutions to some problems, dynamic programming can also be used for counting the number of solutions...

This implies that counting problems can have optimal substructure. I'm confused about what the PEG article is trying to say. I've also been unable to find information on this concept of disjoint and exhaustive substructure. My guess is that PEG is being a bit pedantic and the concept of optimal substructure only makes sense in the context of optimisation problems. You can't have an optimal count, there is just one correct answer. By disjoint we mean that we're interested in subproblems where solutions don't overlap (in order to avoid duplicates, we only want to count each unique combination once) and exhaustive means we want to count all possible unique combinations.

I thought I have a reasonable understanding of dynamic programming but reading this has confused me so essentially I'm looking for clarification.

Edit:
I've found another article on this which looks useful but I'm struggling to understand the proof provided for optimal substructure. I also can't find any information on what weak ordering has to do with dynamic programming and optimal substructure.

I think you understand what's going on well.  It's just two different ways of looking at things.  I agree with you that I think PEG is being a bit pedantic.  Personally, I never particularly liked "optimal substructure + overlapping subproblems" as the definition of dynamic programming; those are characteristics that dynamic programming algorithms tend to have, and tend to help us separate dynamic programming from (say) divide-and-conquer or greedy algorithms.  I like to think of dynamic programming as recursion plus memoization (and possibly, plus table-driven bottom-up memoization).  But to each their own.


Can there be an algorithm for a relation which is not a function? Functions are relations but all relations may not be functions.Can there be an algorithm for a relation which is not a function?What has theory of computation got to say about relations in general.

Your question is very general, especially it is not clear to me what you mean by "algorithm for a relation". I still have some answers.

The difference between (binary) relations and functions is that the former can have several different outputs for the same input. This is just what non-determinism offers us. Thus the theory of computation offers us many models of computation thatcan be seen as computing relations instead of functions.

Further, the input in the most common models of computations has the form of a string. Thus you could compute a relation in the way that string "(x,y)" is accepted iff (x,y) forms part of the relation. This, of course, generalizes to relations of higher order.


How can I do a subtraction on unary numbers terminated in X on turing machine? For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation.
This was my latest try:

First of all, notice that if you have to compute $N-M$ you can subtract one from each operand and the result will not change (i.e. $N-M = (N-1) - (M-1)$.
Keeping that in mind, I would remove a 1 from each operand replacing it with another symbol Y just to avoid spaces on the tape, and repeat until either operand "runs out" of ones --that means that either $N$ or $M$ is now zero. When it happens, clean out the tape a little bit: the left operand is the result of the computation.
So, executing this algorithm in your examples:
example 1
11X1111X input
Y1XY111X
YYXYY11X notice that the left operand is zero
  X      cleanup

example 2
1111XX input
Y111XX notice that the right operand is zero
1111X  cleanup

As you can see from the second example, if the first operand is bigger than the second you will have to revert the last substitution replacing a Y with a 1.
Another meaningful example:
1111111X1111X input
Y111111XY111X
YY11111XYY11X
YYY1111XYYY1X
YYYY111XYYYYX
YYYYY11XYYYYX notice that the right operand is zero
    111X      cleanup

As for the actual program, here is just a sketch, try to write it yourself:

in q0 search for a 1 to replace. That means, skip all the Ys and continue moving right until you find a 1, then don't move and go to q1.
in q1 replace the 1 with a Y, then move right and go in another state (q2) to reach the other operand.
in q2, go right until you find an X (that means you have reach the second operand), then move right and go to q0 to remove a 1 from the second operand too.

This part will replace a 1 from both operands (if there are enough ones), the states of the machines are q0 -> q1 -> q2 -> q0 -> q1 -> q2.
At this point the scanner is placed at the end of the input string, you realize it when you find an empty cell in q2, so;

in q2, if you find an empty cell, move left and go to q3 (which will move the scanner at the beginning of the input).
in q3 move left ignoring any character until you find an empty cell. That means you have reached the beginning of the string. Move right and go to q0.

This loop continues until either operand runs out of 1s. You realize it when you find an X in q0, so:

in q0 if you find an X, move right and go to q4 that is the state that initializes the cleanup part
in q4 move right ignoring any character until you find an empty cell, that means you have reached end of the input, move left and go to q5 to perform the cleanup phase.

Complete the program as an exercise: if you want you can edit this answer to add the sketch of the cleanup phase.


Data structure for a quantity to price multiplier table Yesterday at work I came across an interesting problem that I wasn't able to figure how to structure properly. I'm relatively new to the field and was wondering if I could get some help around here.
What i have here is a table like this:

          |1-2| 3-5 | 6+ | ($)
          ________________
          |              |
10 - 100  | x9   x6   x4 |
          |              |
100 - 2000| x5   x3   x2 |
          |______________|

Where the columns shows the base price and the row shows the quantity.
The idea here is that the bigger quantity you buy, the better the price. Not only that but we would also reduce the multiplier to items with bigger base price, because otherwise the price could become too high too quickly.

The outcome I want to achieve is when given two variables - base price and quantity to find where I'm standing in the table. This means for each table entry I need two ranges.

Let me give some examples:

Base price: 1.5$
Quantity: 200
Result: x5 (multiplier)

So the actual price will be 7.5$

Base price: 10$
Quantity: 15
Result: x4

So the actual price will be 40$

How would you remember the data and how would you write something flexible and scalable so one is able to add and remove table rows easily?

I would evaluate the answers based on how clean the solution is. And by clean I mean easy to use and easy to implement. Currently in our system this table is made from 20 if statements so anything would be better I think!

It's hard to see anything beating the obvious implementation with arrays. You have an array whose columns are indexed by price bands and whose rows are indexed by quantity bands. Store that as a 2D array. Use a pair of 1D arrays to store the minimum value in each price and quantity band. To look up a value, just use linear search through the bands.  Binary search would be faster if the array is huge but it's probably not necessary for small arrays (and your "20 if-statements" suggests the array is very small).

Load the data from a file so you can easily rebuild the data structure if you change your discounting schemes. I'm assuming this is a relatively rare event and, with a small table, it takes no time anyway.


Concatenation of the intersection of two languages I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings:
$$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$

I've tried a lot of sets for e.g.
$L1 = \{a,b,c,d\}$,
$L2 = \{a,f,g\}$,
$L3 = \{s,d,h\}$.
but always the LHS comes out equal to the RHS instead of unequal.
Any idea how to prove this?

First, you may notice that there is a one-sided containment here. It always holds that
$(L_1\cap L_2)L_3\subseteq L_1L_3\cap L_2L_3$ (prove it!)

From this, you see that in order for the equality to fail, you need to get a strict containment.
Intuitively, this means that you need the concatenation with $L_3$ to add words to both $L_1$ and $L_2$.

One way to achieve this is, for example, to first let $L_1\cap L_2=\emptyset$, and then "tailor" $L_3$ to fix this emptiness.

A concrete example is below (hidden as spoiler, hover mouse to see it):

  $L_1=\{a\}$, $L_2=\{aa\}$, $L_3=\{a,\epsilon\}$.


Generate numeric or string ID for a sequence of elements How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.

Example:
[41,1001,32] should generate the same ID as [32,1001,41]
[41,1001,32, 5] should be different.

Elements could be hundreds where each individual ID can be a 4/5-digit number.

I thought about sorting, concatenate and Hash/Compress the string, but are there gonna be a lot of collisions ?

Any ideas would be much appreciated.

If you don't care about the length of the id, sort the list and use that as the id.

If you do care about its length, sort the list and then use the SHA256 hash of the sorted list as the id.  It is believed to be infeasible to find collisions for SHA256, so you shouldn't have to worry about collisions.  If you find one, publish it and you'll be famous (briefly).


How to do binary search on a path in a binary heap I am trying to solve this question:
Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in time $O(\log(\log n))$.
My solution:
Before the loop, I will create a new linked list and initiate $heap[i]$ to be the first item in the list.
Then, I will run a loop on the heap that will start from index $i$, and in every iteration, it will extract the parent of the item in the index $i$ to a new array and will break after extracting the root of the heap.
Then, I will use binary search on the new array (I know that every parent in the heap is bigger than its children. So the new array is already sorted).
The problem is that the extraction of the parents cost me $O(\log i)$ which can be in the worst-case  $O(\log n)$, and for that reason, my solution can't work.
I will be grateful for any help.

Note that a path from the root to $heap[i]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming $1$ based indexing, the $1^{st}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{2} \rfloor$ location in the array. The $2^{nd}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{4} \rfloor$ location, and so on. Using it you can easily perform binary search on the path from root to $heap[i]$ in $O(\log \log n)$ time.
Pseudocode:
Assume that we have a min heap. Initialize, start = $1$ and end =  $h = \lfloor \log(i) \rfloor$
BinarySerach (start, end)

mid = (start + end)/2
index of mid = i/(2^(h- mid)) //(h-mid)^th ancestor of i

if (end-start = 1)
    if (heap[index of mid] == x) return "YES"; otherwise "NO".

if (heap[index of mid] >= x)
   return BinarySearch (start, mid)
else
   return BinarySearch (mid+1,end)


Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$ Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and assigning the $i$th string $x_i$ to number $i \in \mathbb{N}$.
But given strings $x_i,x_j \in \Sigma^*$, is there any special mapping such that the concatenation operation $f:\Sigma^* \rightarrow \Sigma^* | (x_i,x_j) \rightarrow x_ix_j$ is also related to the usual addition performed over the corresponding indices $i,j \in \mathbb{N}$ to which $x_i$ and $x_j$ are mapped ?
For instance, if I assign the character $\{1\}$ to the number $1$, and string $x$ is assigned the number $10$, is there a mapping such that the string $x1$ is assigned the number $11$ ? (i.e. $10 + 1$)

Yes, if you don't want an injective mapping: just assign to all strings value 0.
No, if you want an injective mapping:

Empty string must correspond to value $0$. Otherwise,
$$value(\epsilon) = value(\epsilon \cdot \epsilon) = 2 value(\epsilon),$$
- contradiction when $value(\epsilon)\ne 0$.

Let "0" correspond to value $a$ and "1" correspond to value $b$ ($a,b > 0$). Then
$$value(0^b) = b \cdot value(0) = ab = a \cdot value(1) = value(1^a)$$
- contradiction, since both $0^b$ and $1^a$ correspond to the same value.


Does $f(n) = O(g(n))$ imply $f(h(n)) = O(g(h(n)))$? Can we prove the following, or find a counterexample?

$$f(n) = O(g(n)) \Longrightarrow f(h(n)) = O(g(h(n)))$$

I should figure out whether $\log(n^{\log n}) = O(a^{\log n})$, and this will be facilitated if the above holds.

Let's assume for simplicity that $f(n),g(n)$ both take positive integer values. Then $f(n) = O(g(n))$ iff there exists $C>0$ such that $f(n) \leq Cg(n)$ for all $n$. This implies that for any $h\colon \mathbb{N} \to \mathbb{N}$, $f(h(n)) \leq Cg(h(n))$ holds for all $n$, and so $f(h(n)) = O(g(h(n)))$.
In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C>0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim_{n\to\infty} h(n) = \infty$. In particular, there exists $M>0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.


Bellman Ford Dynamic Programming I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so many unnecessary re-computations, it is not exactly efficient in the likes of other dynamic programming that computes the sub-problems bottom up to the final problem. For example, FloyWarshall has a well defined sub structure of considering all other vertices up to k.
But for Bellman Ford, the implementation is not really relying on any computed sub problems, it is just a brute force algorithm that correctly returns the shortest path but it is not correctly computing the sub-problems in some correct order needed by a dynamic programming algorithm?

Dynamic programming doesn't necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.
To understand what this function is, take a look at the proof. The invariant is "after $i$ iterations, we've found all shortest paths of length at most $i$". Therefore, we can define our function $f(v, \ell)$ - the length of the shortest path to vertex $v$ with length at most $\ell$ - in the following way:
$$f(v, \ell) = \min_{u \ \in\  in(v)} (f(u, \ell-1) + d(u,v))$$
What Bellman-Ford does is slightly different (e.g. it can compute all shortest paths in a single iteration, if our order is lucky), but it can only help us, so we don't mind.


Big-Oh vs Theta in recurrence tree method I am solving this problem from here.

The given relation is

$$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$

The solution via recurrence tree method is given as:

  The zeroth level has a single node with cost $n^2$. The first level has two nodes, each with cost $(n/2)^2 = n^2/4$. The third level has
  four nodes, with cost $(n/4)^2 = n^2/16$.

  In general, you can get the cost of a node by taking the subproblem size and squaring it. At the $i$th level, this cost is $n^2/4^i$. On the other hand, the $i$th level has $2^i$ nodes, so the total cost of each level is $n^2/2^i$.

  The height of the tree is $\log n$.

  Hence, summing the costs at each level we get

  $$\sum_{n=0}^{\log n} \frac{n^2}{2^i} = n^2\sum_{n=0}^{\log n} \frac{1}{2^i} \leq 2n^2$$ by the sum of an infinite geometric series. Therefore the total cost of the algorithm is $\Theta(n^2)$.

As far as I understand, we use Big-Oh to give an upper bound i.e it cannot get worse than this and we use Theta to prove a tight bound i.e when we have proved a lower and an upper bound.

However, here we have only proved an upper bound, so shouldn't the answer be $O(n^2)$?

Is this a specific case when it doesn't matter if we interchange Big-Oh and Theta?

In this particular case $T(n) = 2T(n/2) + n^2 \geq n^2$, so the lower bound is trivial.


Can adjacency lists be used in directed graphs? I've been reading: https://en.wikipedia.org/wiki/Adjacency_list

It says that that graph can be constructed with the list $\{b, c\}, \{a, c\}, \{a, b\}$.

However, what if I wanted to construct a directional list? Does $\{b, c\}$ point to $b$ or $c$?

How can you use a list to represent a directional graph?

Your graph is actually undirected. The notation is a list of edges in the graph. Since edges are undirected, each edge is a set of two vertices. Your lists contains three edges, since a triangle has three edges. It actually contains all possible edges involving the vertices $a,b,c$.

A directed graph is one in which edges consist of two ordered vertices. The edge points from the first vertex to the second. You can represent such a graph using a list of pairs.

Adjacency lists are a different data structure, which is described in the Wikipedia page you link to, so I skip its description here. It can be used for both undirected and directed graphs, in the natural way.


Why is the step property in a balancing network defined as it is? I was trying to understand why the equation $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ describes the step property in a balancing network?

First, recall $x_i$ to be the number of tokens a network gets as input and similarly $y_i$ to be the number of output tokens. Recall that a balancing network is just a network that distributes tokens to its output.

I was reading the art of multicore programming and in page 272 it says:

  If the number of tokens n is a multiple of four (the network width),
  then the same number of tokens emerges from each wire. If there is one
  excess token, it emerges on output wire 0, if there are two, they
  emerge on output wires 0 and 1, and so on. In general,

  $$ n = \sum x_i $$

  then

  $$y_i = \left( \frac{n}{w} \right) + (i \pmod w) $$

  we call this property the step property.

It also defines equivalent ways to see the step property as:

For any $i<j$, $0 \leq y_i - y_j \leq 1$

i.e. as we go up the output wires, the wire can only increase one step at a time or not increase (so top values are always larger or equal). An example:

However, the formula $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ doesn't make sense to me also, specifically the following doesn't make sense:

  if there are two, they emerge on output wires 0 and 1, and so on...

I tried plugging in the numbers too say, $ n = 6 $, but the results don't quite make sense.

For example according to the formula above we get:

$$ y_0 = \left( \frac{6}{4} \right) + (0 \pmod 4) = 1 + 0 = 1 $$
$$ y_1 = \left( \frac{6}{4} \right) + (1 \pmod 4) = 1 + 1 = 2 $$
$$ y_2 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 2 = 3 $$
$$ y_3 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 3 = 4 $$

which doesn't agree with what  the picture of the diagram would be because it seems to be backwards. Not sure if I made a mistake or misunderstood the formula, but it should be giving something as in the figure/diagram/picture from the book. Also, according to the formula, is it ever possible for it be equal? It seems to always increase in the wrong direction.

The formula is wrong. The correct formula is
$$
y_i = \lfloor \frac{n}{w} \rfloor + [i < (n \mod{w})],
$$
where $[C]$ equals 1 if $C$ holds, and 0 otherwise.

Sometimes books contain mistakes. When you see a mistake, correct it and proceed. No need to ask us for permission.


Compression with random dictionary Is the following scenario theoretically possible, or provably impossible?

Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice and Bob starts sending each other new files with arbitrary entropy, each of them < 1 MiB, but they compress them with a clever algorithm that exploits information in Q, typically breaking the Shannon limit.

This is provably impossible. The proof of Shannon's theorem goes through as usual.

As a simple example, suppose that are looking for an algorithm that compresses all $n$-bit strings to smaller strings. This is impossible since there are $2^n$ possible inputs, but only $2^n-1$ possible outputs. The proof of Shannon's theorem is very similar. Note how $Q$ makes absolutely no difference.

What happens if you choose a random 1 MiB window of $Q$ as your file? This can easily be compressed to 30 bits, by sending the location of the window. However, in this case the entropy of $Q$ is indeed at most 30 bits, since there are at most $2^{30}$ different windows.


What TSP variant doesn't return to start point? For my case I have starting point and several cities.

I want the shortest route to visit all cities without returning starting point.

I have read several TSP algorithm and all include the return a full cycle.

So what TSP variation should I look for to solve my problem?

You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.)

Edit: it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add two dummy cities $v$ and $w$ such that:

$v$ is only connected to the starting point and to $w$,
$w$ is connected to everything.


Turing decidable languages On an old worksheet I came across the question

If L1 and L2 are two Turing decidable languages, then show that 1∪2 and 12 are Turing decidable languages (high-level description with stages is enough).

How do I go about answering this without being given a language to work from?

Both $L_1$ and $L_2$ are decidable. Hence, they have algorithms $A_1$ and $A_2$ (respectively) that decide them.
Try to create a new turing machine (algorithm) using the two algorithms $A_1$ and $A_2$.
For example, for the union $L_1\cup L_2$, you can create the following algorithm:

run $A_1$ on the input. If it accepted, then also accept.
else, run $A_2$ on the input, and return what $A_2$ returned.


Turing decider Halting Problem Wiki and my classes Textbook defines a decider as:

  In computability theory, a machine that always halts—also called a
  decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a
  Turing machine that halts for every input.

So shouldn't this decider be able to decide the Halting Problem?
Because it halts always? I am a bit confused.

Here is an example of a decider:

  On input $w$, accept if $|w|$ is even, and reject if $|w|$ is odd.

Does it solve the halting problem?


Interpretation in scripting languages Why is pure interpretation more common for scripting languages compared to programming languages?

I mean, why are programs written in a scripting language not converted to machine language and then executed? From what I have read, one of the reasons is speed; for scripting purposes speed is not so important and since interpretation is slower it doesn't matter for scripting languages.

Are there more reasons for using interpretation in scripting?

Scripting languages are a class of programming languages. This class is rather fuzzily defined.

One possible definition is that they're languages that are designed to automate small tasks, rather than to write large, complex programs. Because they are small tasks, the author tends to spend some time tweaking them, so it makes sense to make the path from source code to executable as simple as possible, and it doesn't get simpler than making the source code itself executable. Because they are simple tasks, the end-user might want to tweak them, too, so it makes sense to distribute them as source code. Because the tasks are relatively small and simple, there's little to be gained by static checking and optimization, so there's little value in using a compiler.

Another possible definition is that a scripting language is one in which the source code is executable. In other words, a scripting language is pretty much defined as one that's intended to be interpreted.

Few scripting languages are purely interpreted though. Most at least parse the whole file before starting execution. Many even compile to some form of bytecode that can be saved to disk.


Decision problems in $\mathsf{P}$ without fast algorithms What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known algorithm is "slow".

Here are two examples:

Recognition of perfect graphs. In their FOCS'03 paper [1] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of [1], see here).
Recognition of map graphs. Thorup [2] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.

I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.

[1] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.

[2] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.

Perhaps the following problems fit into your examples:

(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms
for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
AKS-primality test in $O((\log n)^{12})$ time.
Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.


Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines" In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that

  The reader may find it helpful to visualize a two-dimensional spatial network of processes, which yields a three-dimensional space-time diagram. Processes and messages are still represented by lines, but tick lines become two-dimensional surfaces.

However I failed to visualize them in my head, especially the two-dimensional surfaces. Could anyone make more explanations? An illustrative picture would be excellent.

Here's my take:

...and here's a 3D version without the nice colors.

Vertical black lines are processes; magenta lines are messages (wavy lines); spheres are events, and time is on the vertical (blue) axis.  The planes are 'tick lines.'

In Dr. Lamport's original diagrams, messages are only passed between "adjacent" processes.  Presumably in a real distributed system any process can send a message to any other process, but this is hard to draw clearly in a 2D diagram.


Guaranteed existence of a blocking set in the accept definition of Stellar In the SCP, condition 2 of the accept definition allows a node to vote for one statement and later accept a contradictory one. Condition 2 assumes the existence of a v-blocking set which has not only voted for a but also accepted it. What is the argument to show that this is the case?

What is guaranteed is that if a quorum of an intact nodes accepts a statement s, then eventually every intact node v will find itself v-blocked by a set of nodes that has accepted s, i.e. "accept s" cascades throughout all intact nodes until all have accepted and then confirmed s. This is called the cascade theorem in the paper "Fast and secure global payments with Stellar". You can find a brief justification of this theorem at the end of section 3.1.2. There is also a formal proof in Isabelle/HOL here: https://github.com/stellar/scp-proofs. Finally it is also guaranteed that if an intact node is v-blocked by "accept s", then at least one intact node saw a quorum voting for s.


Is the language of all non-palindromes context-free? Is the language $L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}$, context-free? I think this grammar:

$
S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\
A \rightarrow aAa \mid bAb \mid aAb \mid bAa \mid a \mid b \mid aa \mid ab \mid ba \mid bb
$

generates it, but I'm unable to conclude anything using the pumping lemma for context free languages.

If $w$ is not a palindrome then there must be some $i$ such that the $i$th letter from the left is different from the $i$th letter form the right; and vice versa (prove!). This means that
$$
L = \{ \Sigma^{i-1} a \Sigma^* b \Sigma^{i-1} : i \geq 1 \} \cup \{ \Sigma^{i-1} b \Sigma^* a \Sigma^{i-1} : i \geq 1 \},
$$
which is easily seen to be context-free.

Your grammar almost manages to capture this characterization. Unfortunately, it doesn't generate the words $ab$ and $ba$. A simpler grammar is
$$
\begin{align*}
&S \to aSa|bSb|aTb|bTa \\
&T \to aT|bT|\epsilon
\end{align*}
$$


Simple question about grammar derivations I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.

Here is an example of a grammar derivation in a Youtube lecture I found. I get everything he covers here except that it isn't clear to me how a derivation is chosen when there are multiples available.

For example, in the video he constructs a grammar E that has productions E + E, E * E, and id. I'm assuming that the correct derivation is chosen by pattern matching the input string to the grammar but that isn't made clear, nor is it really made clear in other sources I've read and watched. The derivation used at a given step sometimes seems arbitrarily chosen.

My reason for asking is because if it isn't matched to the input pattern, what is to keep his grammar from expanding an E into the (arbitrarily chosen) non-terminal production E + E infinitely, and never reach a terminal condition?

Edit Related question:

On the bottom of this page there is a discussion of leftmost and rightmost derivation. In the leftmost derivation example, how does it know the correct derivation to use to move from the second to third derivation? In other words, how does it know to make this derivation: a+X → a+ X*X

Why couldn't it just derive a+X → a+a and terminate? I know it doesn't match the input string, but what actually prevents that incorrect derivation from being chosen?

Actually you have to study the working of a parser in detail to get the answer to your question.

Parsers can be top down or bottom up. In top down parsing, we try to derive the input string from the start symbol. In bottom up parsing, the reverse procedure is applied, i.e. we try to reduce the input string to the start symbol.

Let me try to answer your question by explaining the working of recursive descent parser, a general top down parser.

Recursive descent parser will choose the productions based on the order in which they are specified. I will explain with an example.

The grammar given is

    S-> aAB | bAB
    A-> d | a
    B-> b

Let the input be

    bab

The input pointer points to the first symbol 'b'. The recursive descent parser will start with start symbol S. The working is as follows

    S-> aAB

Whenever a terminal symbol is obtained, it is checked for match with the current input symbol. Input symbol 'b' doesn't match with the terminal 'a'. So the parser will backtrack and choose the next production

    S->bAB

The terminal symbol matches with the input. Hence input pointer is advanced and it points to 'a'. Next substitute for A.

    S-> bdB

Input symbol and the obtained terminal does not match. So backtrack and choose the next production for A.

    S-> baB

Now a match is obtained and B is replaced with its production

    S->bab

Thus input is successfully parsed.
The steps in derivation can be summarised as

    S-> aAB (backtrack)
     -> bAB
     -> bdB (backtrack)
     -> baB
     -> bab