Does weak consistency allow reordering of events? I am on studying a consistency model: weak consistency. weak consistency
This model was first defined by Dubois et al. (1986), by saying that it has three properties:

Accesses to synchronization variables are sequentially consistent.
No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
No data access (read or write) is allowed to be performed until all previous accesses to synchronization variables have been performed.

And there is an example saying that the following sequence is weak consistent :

Here, S represents accessing synchronization variables.

But how is this possible ? I don't understand how can the event R(x)2 happens before R(x)1 of processor P3 while W(x) 1 happens before W(x)2 on processor P1.

Weak consistency rather appears in distributed systems where changes to variables have to be transmitted via the network.
Before a synchronization there is no guarantee to the visibility of write operations.
On P2 the W(x)1 could arrive before W(x)2 and on P2 W(x)2 could arrive before W(x)1.


Why can't you write the 2-paths problem as a max-flow problem? This is a follow-up question to this. Consider the 2-paths problem:

  Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and $P_2=(s_2,\dots,t_2)$ such that $P_1$ and $P_2$ are vertex-disjoint?

This problem has been shown to be NP-complete (references here).
This struck me as unusual, because there seems to be a natural way to formulate this as a max flow problem:

Add new vertices $s$ and $t$ to $D$.
Add arcs $(s,s_1),(s,s_2),(t_1,t),(t_2,t)$.
Let all vertices have capacity one (besides $s$ and $t$).

It seems to me that the max $s-t$ flow of this new graph (call it $D'$) should be two iff $D$ has those desired paths $P_1$ and $P_2$. Surely there must be some mistake here, because this seems to imply that an NP-complete problem can be solved in polytime. Where is the mistake?

The proposed construction does find two vertex disjoint paths from s to t (if they exist). HOWEVER, the paths might be $P_1=(s_1,…,t_2)$ and $P_2=(s_2,…,t_1)$, which is not what we want.


Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous Prove that the following grammar is unambiguous:
$$X \to  aX | Y$$
$$Y \to Yab | b$$

I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?

First, figure out what the language is.
Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous?
Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect the resulting word?


Langton's Ant Periodic Behavior I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

The path of the ant is (ultimately) periodic if and only if it is bounded.  (Clearly, an unbounded path cannot be periodic.  Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)
Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical.  To return to a particular square after once leaving it, the ant must travel an even number of steps.  Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path.  (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can.  Since the ant's path is, by assumption, bounded, this process will always terminate.)  Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left.  But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.


Vertex Cover problem modification Modification of vertex cover problem.
Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP?
Given a graph G and integer k, does G have a vertex cover with k vertices?
Is there any important difference between this two problems?

For fixed $c$ (i.e., we consider $c$ as a constant) this is trivially solvable in time $n^cm$ which is polynomial in $n$, however, if $k$ is part of the input, then $n^k$ would be considered exponential in $k$.

Vertex cover is solvable in $2^k \cdot n^{O(1)}$.


How to solve this very complicated assignment problem A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack.  The width of an item depends only on the position within the stack but not on which stack it is placed in. The width of a stack is the maximum of the widths of z items placed in it.
The objective is to place the items in the stacks so that the sum of the widths of the stacks is minimum. No position in the stacks could be left unassigned. That means we have to choose z x n items out of m items to be placed in the stacks.

I tried to map this problem to different types of assignment problem but could not find one that exactly matches the constraints and objectives.
What would be a good approach to solve this problem?

Edited based on D.W. s comment:
I am looking for a practical solution. The number of stacks n is not large..it would be around 10. The number of positions within a stack, z is at most 36, but 9 is the most frequent number of positions. The number of items m on average is around 100-200. The widths are NOT integers, but floating point values (precision of 0.01 is good enough). I have not tried the integer linear programming approach...I need a very fast solution that can work for online calculation of some scheduling in an embedded system.

I don't see a way to solve this using standard algorithms for the assignment problem.

If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP).  You can introduce zero-or-one variables $x_{i,j,k}$, where $x_{i,j,k}=1$ means that item $i$ is placed in stack $j$ position $k$, and continuous variables $w_j$, where $w_j$ represents the width of stack $j$.

It's then not too hard to write down linear inequalities that capture all your requirements.  For instance, we have $\sum_{j,k} x_{i,j,k} = 1$ (each item is placed in one location) and $\sum_i x_{i,j,k} = 1$ (two items can't be placed in the same location; every position must be full) and $c_{i,k} - w_j \le M (1-x_{i,j,k})$ where $c_{i,k}$ is the width of item $i$ if placed in position $k$ and $M$ is a sufficiently large constant (this ensures that the $w$'s represent the stack widths correctly).  Then, you can minimize $\sum_j w_j$ with an off-the-shelf ILP solver.

I don't know how efficient it will be, or whether it will be adequate for online realtime calculation, but I suggest you give it a try and find out.

If it is too slow, there are some options.  One option is that some ILP solvers come with a way to impose a time limit; the solver tries to find the best solution it can within the time limit, with no guarantee that it will find the optimal solution.  Another option would be to try to craft some heuristic that doesn't necessarily yield the optimal solution, but is fast; maybe a greedy algorithm or something.  For instance, here is an off-the-cuff idea.  Associate with each item the smallest possible width it could have, among all the possible places it can be placed (out of the positions that remain open).  Pick the item with the largest associated value, and place it in the position that minimizes its width.  Update the associated values for all items, and repeat.  No guarantees about the quality of the solution, but this will be fast.  One could also use the smallest amount that it increases the total cost of the solution, out of all possible placements, rather than the smallest width, as the value associated with a particular item.


Maximize product of sum of two subset Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize
$$
\left(\sum_{i \in S} a_i\right)\left(\sum_{i \notin S} b_i\right)
$$

A naive solution is to iterate over the powerset of $\{1, 2, \dots ,n\}$ and find the maximum value, which is $O(n2^n)$. How to use dynamic programming to solve this?

Any comments would be appreciated.

If you could solve this problem, then you would be able to solve the NP-complete PARTITION problem. The partition problem asks whether a given set of positive integers $X$ can be partitioned into two equal parts. Given a set $X$ whose sum is $M$, choose an arbitrary ordering of its elements $X = \{x_1,\ldots,x_n\}$, and let $A=B=X$. Your problem asks to maximize
$$
f(S) = \left(\sum_{i \in S} x_i \right) \left(M - \sum_{i \in S} x_i\right).
$$
As a quadratic in $\sigma = \sum_{i \in S} x_i$, $f(S)$ is maximized at $\sigma = M/2$, at which we have $f = (M/2)^2$. This is achievable for some set $S$ iff $X$ can be partitioned into two equal halves.


Decide if this language is context free I got this question for homework:

Decide if this language is context free or not:
$\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$.

Intuitively I think it's not context-free because a $PDA$ can't remember the places of all the $1$'s in $x$.
I tried using the pumping lemma but couldn't find the right example to show the language is not context-free.
I'd be grateful for any lead.

Hint: Following up on Hendrik Jan's hint, here is another way to view this language:
$$
\{ x1y@1z : x,y \in \{0,1\}^*, z \in \{1\}^*, |x| = |z| \}.
$$


Implement K-means clustering with Map-Reduce Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around to do it using Map Reduce(I know what Map Reduce is). Can someone provide me an explanation/algorithm of how to do that? More specifically I am looking what Map and Reduce phases will look like for such an implementation? I was also asked how many Mappers and Reducers will I need?

You can run a loop over $j\in\{1..k\}$:

Create a map that maps each point $x_i$ to itself if $x_i$ is nearest to the mean $m_j$, and to the zero vector otherwise:
$$x_i \rightarrow \begin{cases}(x_i, 1)  & d(x_i, m_j) \le d(x_i, m_l),\ l\neq j \\ (0,0) & \text{otherwise} \end{cases}$$
In the reduce stage, you would find the sums and counts:
$$(x_{i1}, c_1), (x_{i2}, c_2)\rightarrow(x_{i1}+x_{i2}, c_1+c_2)$$
You then divide the resulting sum by the total count.

Thus, for each iteration in the k-means algorithm you will need $k$ maps and $k$ reduces.


Theoretical worst case running time of finding a path through a maze? Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the theoretical worst-case running time of finding a path through this maze?

The maze has a density of d (for example, if d = 0.5, then half of the maze is filled with obstacle/wall cells)
The path finding algorithm uses a stack to keep track of the path and for back tracking when necessary
The algorithm uses a search order of down, right, up, left

If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.


Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials.

In particular, $f(x),g(x) \in GF(2)[x]$ are primitive polynomials of order $n$, and the characteristic polynomial of the LFSR is given by:
$$c(x)=f(x)g(x).$$
What is the minimal period of any state of this LFSR, other than the all-zeros state?

I've tried to say that if $c(x)$ is a product of two primitives then it has a period of
$$\pi=2^{2n}-1 $$
but my math gets me to
$$\pi =2^{n+1}-2$$
What did I do wrong?

The states of a LFSR with characteristic polynomial $p(x)$ correspond to elements of the multiplicative group of $GF(2)[x]/(p(x))$.  The period of a LFSR state is the order of the corresponding group element.  So, we can rephrase this as a group theory question, and use facts we know from group theory to answer the question.

The LFSR state with minimal period is exactly the group element $g \in G$ with minimal order, where here $G_c$ is the multiplicative group of $GF(2)[x]/(c(x))$.

The LFSR state with minimal period (other than the all-zeros state) is the group element with minimal order (other than the identity element).

Thus, to find the minimal period you want, you need to find the order of the minimal-order group element of $G_c$ (other than the identity element $1$).

Assuming $f,g$ have no common factor (i.e., $f\ne g$), the structure of $G_c$ is $G_c \cong G_f \times G_f$, where $G_f$ is the multiplicative group of $GF(2)[x]/(f(x))$ and $G_g$ is the multiplicative group of $GF(2)[x]/(g(x))$.  This follows from an analog of the Chinese remainder theorem.

Let $g_1$ be the group element of minimal order in $G_f$, and $g_2$ the group element of minimal order in $G_g$.  From what we know about the structure of $G_c$, the group element of minimal order in $G_c$ is either $(g_1,1)$ or $(1,g_2)$.  So it suffices to find the group elements of minimal order in $G_f$ and $G_g$.

From the fact that $f$ and $g$ are primitive, we know that $G_f,G_g$ are cyclic groups of order $2^{n_f}-1$, $2^{n_g}-1$, respectively, where $n_f = \deg f$ and $n_g = \deg g$.  Per Lagrange's theorem, we know that the divisors of $2^n-1$ correspond to the orders of the group elements of $G_f,G_g$.

Let $d_f$ be the smallest divisor of $2^{n_f}-1$ (such that $d_f>1$), and similarly for $d_g$.  Then the group element of minimal order in $G_f$ will have order $d_f$, and the group element of minimal order in $G_g$ will have order $d_g$.  It follows that the group element of minimal order in $G_c$ will have order $d=\min(d_f,d_g)$, and the LFSR state of minimal period will have period $d$.

So, the answer to your question is: the minimal period (other than the all-zeros state) is exactly $\min(d_f,d_g)$ where $d_f$ is the smallest divisor of $2^{\deg f}-1$  (other than 1) and $d_g$ is the smallest divisor of $2^{\deg g}-1$ (other than 1).


The language of non-extendable strings of a regular language is regular I recently came across this question in my textbook.

  $ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $
  $ \text{Prove that the language is also accepted by some FSA.} $
  $ \operatorname{Max}(L) = \{x \in L : \forall y \in \Sigma^* - \{ \lambda \}.\ xy \notin L \}.$

Where $ \lambda $ is the empty string in this case.

It seems that any regular language that has any maximal length string must not contain any repetition operators $"{^*}"$. Hence the regular language only consists of characters, concatenation, and alternation. That means the FSA it generates cannot contain any cycles that contain a final state.

From the above, I decided to go with cases, where the language is generated by a regular expression that contains repetition or does not.

If the regular expression contains repetition, then the FSA that accepts the new language contains only one state, the starting state, and no final states.

If the regular expression does not contain repetition, then the FSA that accepts the new language is a copy of the original FSA with the final states restricted to the final states that were the largest number of edges away from the starting state of all the final states. That means only the longest strings that were accepted will be accepted.

This description intuitively makes sense, however, I cannot see how I might begin to prove any part of this, and I do not even know if this description is fully accurate. Is this description accurate and is there an easier way? If this description is accurate, how would I go about proving it?

The definition does not ask for a maximal length string in $L$ but it looks for the strings that cannot be extended into a longer string in the language: $x\in L$, but no $xy \in L$ for nonempty $y$.

This means that repetitions are no problem. For $L = a^*b$ in fact $\mathrm{Max}(L) = L$ as no string can be extended to a longer string in $L$. But for $L = ba^*$ we have $\mathrm{Max}(L) = \varnothing$,as every string can be extended.

If you start with a (deterministic!) FSA, you can easily see which strings can be extended, and which not. How?


Designing CFG that accepts # of 1's = # of 2's + # of 3's Designing following language $\{ w \mid w\in\{0, 1\}^* \mbox{ such that } |w|_0 = |w|_1\}$ is easy.

  Note $ |w|_0 $ means number of occurrences of 0.

$$
S \to 0S1 \mid 1S0 \mid SS \mid \lambda
$$

Then how about this? Language $\{ w \mid w\in\{1, 2, 3\}^* \mbox{ such that } |w|_1 = |w|_2 + |w|_3\}.$

It is somewhat difficult for me. Below is my solution. Is it correct?

$$
S \to XSX \mid \lambda
$$
$$
X \to 1123 \mid 1132 \mid 1213 \mid 1231 \mid 1312 \mid 1321 \mid 2113 \mid 2131 \mid 2311 \mid 3112 \mid 3121 \mid 3211 \mid \lambda
$$

Given a grammar for $\{ w \in \{0,1\}^* : |w|_0 = |w|_1 \}$, you can obtain a grammar for $\{ w \in \{1,2,3\}^* : |w|_2+|w|_3 = |w|_1 \}$ by replacing $0$ in the first grammar by a non-terminal $Z$, and adding the productions $Z\to 2 \mid 3$.


find the strong component containing the vertex v I'm trying to solve this question for practising purposes:

"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, describe a simple quadratic-time algorithm for computing the strong components of a digraph."

The question can be found here . It is question 31.
They give a couple of hints:

"Partial solution: To compute the strong component containing s

Find the set of vertices reachable from s
Find the set of vertices that can reach s
Take the intersection of the two sets

Using this as a subroutine, you can find all strong components in time proportional to t(E+V), where t is the number of strong components."

My thoughts so far:

In order to find the vertices reachable from s, I can to DFS (or BFS, but will stick with DFS) from s. If n is the number of vertices and m is the number of edges this takes O(n+m) time, which seem fine for the purpose. I need to safe every discovered vertex somewhere. Not sure which datastructure works best for this. I will come back to this problem later.
In order to find all vertices that can reach s, I could bild/compute the reverse of the graph and to another DFS from a again. Computing the reverse of the graph should be O(n+m) and the DFS is O(n+m). So in total I have 3*O(n+m) which is just O(n+m). Of course the discovered vertices also need to be safed.
I'm not sure about how to build the intersection. Of course this is going to depend on how I saved the nodes before. So here are my ideas:

Building the intersection:

If I saved the nodes in two separate arrays (one for the first DFS and one for the second) I possibly could use a Hash-Table. This should be O(|firstNodes| + |secondNodes|) time. Maybe this would be ok, since O(|firstNodes| + |secondNodes|) is smaller than O(n+m), but it doesn't seem optimal to me and it need extra space.
What if I mark the nodes I discoverd with the first DFS. Then I do the second DFS and check if nodes are already marked. If yes, I mark them "special" as belonging the the strong component? I wouldn't have a list afterward that gives me the vertices of the strong component s belongs to but the strong component is still computed? For this approach I would need extra space at every node (in order to mark it).
In order to find all strong compoonents in time proportional to t(E+V) I could then to the same procedure on a vertex that is not yet marked as belonging to a strong component -> as long as there are such vertices, therefore t times. I would need to make sure, that every strong component is marked differently (e.g. increaing integers) and that the "I fould you" marks from the DFS are gone after each iteration (but not the marks for the strong components).

What do you think? What have I missed?
Thank you and happy Easter!

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the multiplicative constant, but not the asymptotic space complexity.
All your ideas are sound. During a BFS, since you need to check if vertices are seen or not, the common way to do it is to use a boolean array. Now for a strongly connected component, you will run two BFS's, and use two boolean arrays. The intersection can be computed by a index-wise AND.


Proving whether $\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy) is satisfiable, valid or unsatisfiable I have a question that I am stuck on reasoning about knowledge. For the following statement, I need to show whether it is valid, satisfiable or unsatisfiable:

$\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy)

I have done the following:

Let e w be an interpretation where e is the set of possible worlds and w is the real world. Then we need to show that for any interpretation, e w satisfies  $\neg \bf{K}$(Happy $\lor$Sad) $\lor$ $\neg \bf{K}$(Happy).:

Now assume that such an interpretation e w satisfies  $\bf{K}$(Happy $\lor$Sad). This would mean for all w' $ \in$ e, e w' satisfies  $\bf{K}$(Happy $\lor$Sad). However in a world w'' = {$\neg Happy, \neg Sad$}, then the interpretation e w'' does not satisfy  $\bf{K}$(Happy $\lor$ Sad).

Therefore, we have a contradiction and for any interpretation e w, e w satisfies $\neg \bf{K}$(Happy $\lor$Sad).

Similarly, assume an interpretation e w satisfies $\bf{K}($Happy). However, if we have a world(s) where $\neg$Happy is true, then e w'' does not satisfy  $\bf{K}($Happy). Therefore for any e w, e w satisfies $\neg \bf{K}($Happy) and thus the statement is valid.

I'm not sure whether my proof is correct and if not, could give me a hint on how to go about with this question.

The formula is either satisfiable or unsatisfiable. Only when it is satisfiable, it may also be valid.

To rule out that the implication is valid, show that its negation is satisfiable, that is, construct a model that satisfies the LHS but not the RHS. (Hint: a model with just one possible world suffices.)

Next, rule out that the implication is unsatisfiable by providing a model that satisfies the RHS. (Hint: again, a model with just one possible world will do.)

After these two steps, you're left with the answer.


An algorithm to drop low-priority items from a heap-based priority queue I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value.  (Or, equivalently, to drop from a priority queue realised by such a heap all items whose priority is too low.)

It is easy to make an algorithm that walks the heap level by level from bottom up, comparing the item weights to the threshold value and doing dropping-and-swapping.  It will turn out to be extremely inefficient though if, for example, all items in the heap need to be dropped.

It looks better to start by finding an item at the bottom level that is heavier than the threshold value and walk upwards from it until finding the highest element that needs to be dropped.  Then the whole sub-heap under that element needs to be dropped.  The space taken up by this sub-heap can be filled with elements moved from one or two bottom levels that are not in this sub-heap, and the sub-heap can be rebuilt.  However, this method does not look perfect either, as most likely the dropped sub-heap will be filled with elements some of which need to be dropped too.

Are there any efficient or well-studied algorithms for this?

Let $n$ denote the size of the min-heap.  It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then call MakeHeap to turn it into a heap.

I would be surprised if you can do better than this, in asymptotic worst-case running time.  For instance, any approach that involves scanning all items at the bottom layer will necessarily take at least linear time, i.e., at least $\Omega(n)$ time.  And if there is any item in the bottom layer that you don't examine, then in at least some cases you won't be able to tell whether it needs to be included or not.  So I suspect it may be possible to construct an adversarial argument that shows that at least $\Omega(n)$ time is needed -- though I don't know for sure.

Alternatively, one could consider the running time as a function of the output size.  Let $m$ denote the size of the output, i.e., the number of elements that are above the threshold.  Then it is easy to achieve $O(m)$ running time, by doing a top-down recursive pre-order traversal of the min-heap (think of it as a binary tree), truncating the traversal at each internal node that is above the threshold.  The running time is $O(m)$ since you only visit a node if it is included in the output or if it is an immediate descendant of a node included in the output; since each node has at most 2 descendants, this means that the number of nodes visited is at most $3m$, i.e., $O(m)$.  This is clearly optimal, as a function of output size: any algorithm that produces $m$ outputs has to take at least $\Omega(m)$ time, just to write out the output.


How can I study the nature of the structure of evaluation of function in lambda calculus? I am specifically focusing on lambda calculus, following this paper: A Tutorial Introduction to the Lambda Calculus.

Suppose we have three functions that represent the natural numbers 0 and 1, and a successor function:

$\lambda sz.z = 0$

$\lambda sz.s(z) = 1$

$\lambda wyx.y(wyx) = succ$

Suppose I were to evaluate $succ\ succ\ 1$. As I evaluate this expression, it is becoming clear to me that it's not 3 as I might naively expect, but I do not truly grasp "why." Even as I go through the motions of evaluating the expression, I do not understand the nature of the turn of events and why certain expressions produce a certain result due to their structure and construction.

A question I might ask would be something like, why does $succ$ have that form, and is there an alternative form for $succ$ that produces the same result? If it is unique, what makes it special? I don't know how to answer these questions well yet, so I am seeking guidance.

Is there a method by which I can better visualize or understand the evaluation of expressions and how it affects the "class" of their output? I am very new to lambda calculus, so please excuse me.

Edit: I think I understand the rules for evaluation of lambda calculus (substitution, prevention of name collisions, etc.), but I have a hard time understanding the arbitrary rules by which one can construct lambda calculus' equivalent forms for the natural numbers, the successor functions, and the addition and multiplication functions. It's how these parallels to these concepts were mapped over to lambda calculus that I am interested in.

For example, why are the functions for "choose second," "false," and "discard next argument," and "0" have the same form and thus equivalent? There exists systems in which applying the zero function to a list of object does not result in returning a list with the front-most argument removed. Even if it is a convention, is there a reason why it is structured as such?

For example, why is does the successor function work? One can say that it was discovered through trial and error, but this makes for poor understanding of the nature of a concept besides "it is so" and "it works." I hope this makes sense.

I'll try addressing only some of the questions.

Church numerals are defined to be functions (abstractions in $\lambda$-calculus speech) that take two arguments: a base argument $z$ (stands for zero), and a "successor" function $s$ which will be repeatedly applied to the base $z$. The number of times $n$ we apply $s$ corresponds to some natural number $n$.

The successor function $\mathsf{succ}$ takes a Church numeral corresponding to some $n \in \mathbb{N}$ (the numeral's canonical form is $\lambda sz. s^nz$), and returns a Church numeral corresponding to $n+1$, i.e. some term that behaves like $\lambda sz. s^{n+1}z$.

Notes:

$s^n z$ means $s (s (s (... s z))...)$, where $s$ applied $n$ times to $z$;
two abstractions are behaviorally equivalent if applied to the same arguments they yield the same result.

Let's obtain a $\lambda$-term representing $\mathsf{succ}$. In what follows I'm using Church numerals and corresponding natural numbers interchangeably, I hope that it won't cause confusion, since the current domain can be derived from the context.

$\mathsf{succ}$ is an abstraction that takes a Church numeral $n$, so $\mathsf{succ} = \lambda n. \textsf{<...>}$
$\mathsf{succ}$ returns a Church numeral, which must take 2 arguments, that's why $\mathsf{succ} = \lambda n. (\lambda sz. \textsf{<...>})$
After supplying some $s$ and $z$ to $(\mathsf{succ}\ n)$ we must have $s$ applied $n+1$ times to $z$. Notice that the Church numeral $n$ allows us to easily get $s$ applied $n$ times: we just apply $n$ to $s$ and $z$: $(n\ s\ z) = s^n z$. Then, using the fact $s^{n+1} z = s (s^n z)$, we get $s^{n+1} z = s (n\ s\ z)$. Finally, $\mathsf{succ} = \lambda n. (\lambda sz. s (n\ s\ z))$ or, sweetening with some more syntactic sugar, $\mathsf{succ} = \lambda nsz. s (n\ s\ z)$.

The term we've got for the successor function is not unique, one can use any form of $\mathsf{succ}$ as long as it fulfills its role: make "the next" Church numeral out of the current one. For instance, the following is a valid term for $\mathsf{succ}$ too: $\lambda nsz. n s (s z)$, and it can be obtained using the fact $s^{n+1} z = s^n (s z)$.

In fact, there are infinitely many syntactically different $\lambda$-terms for the successor function. We can invent many different (and silly) ways of "implementing" $\mathsf{succ}$: make a Church pair $(\lambda nsz. s (n\ s\ z), \text{<any-term>})$ and take its first component, i.e.
$$
\mathsf{succ} =
\mathsf{fst}\ (\mathsf{pair}\ (\lambda nsz. s (n\ s\ z))\ \text{<any-term>}),
$$
or add $x+1$ to a number and subtract $x$, i.e.
$$
\mathsf{succ} = \lambda n. \mathsf{minus}\ ((\mathsf{plus}\ n\ \mathsf{(x+1)})\ \mathsf{x})
$$

Now, let's address the $\mathsf{succ}\ (\mathsf{succ}\ 1)$ issue (I'm using the unrestricted evaluation strategy here):
$$
\begin{array}
    \mathsf{succ}\ (\mathsf{succ}\ \mathsf{one}) &= \quad \text{(by definitions of succ and one)} \\
    \mathsf{succ}\ ((\lambda nsz. s (n s z))\ (\lambda sz.s z)) &\to_{\beta} \\
    \mathsf{succ}\ (\lambda sz. s ((\lambda sz.s z) s z)) &\to_{\beta}^{*} \\
    \mathsf{succ}\ (\lambda sz. s (s z)) &= \quad \text{(by definition of succ)} \\
    (\lambda nsz. s (n s z))\ (\lambda sz. s (s z)) &\to_{\beta} \\
    (\lambda sz. s ((\lambda sz. s (s z))\ s z)) &\to_{\beta}^{*} \\
    (\lambda sz. s (s (s z)))
\end{array}
$$
We've got a $\lambda$-term which clearly represents the number $3$ as was expected. If you try using $\lambda nsz. n s (s z)$ as the successor function you'll get the same result.

Under more restricted reduction strategy, viz. the call-by-value strategy, we sometimes get a term which doesn't look like a Church numeral at all, but behaves like one. A classical example is
$$
\begin{array}
\mathsf{succ}\ 1 &= \\
(\lambda nsz. s (n s z)) (\lambda sz. s z) &\to_{\beta} \\
\lambda sz. s ((\lambda sz. s z) s z)
\end{array}
$$

The result is behaviorally equivalent to $\lambda sz. s (s z)$.

Now I'm going to show that $(\mathsf{succ}\ \mathsf{succ})\ N$ is equivalent to Church numeral corresponding to $N(N+1)$. Then somewhat unintuitive term $(\mathsf{succ}\ \mathsf{succ})\ 1$ indeed evaluates to $2$.

$$\begin{array}
\mathsf{succ}\ \mathsf{succ}\ N &= &\text{unfold the 1st succ}\\
(\lambda nsz. s (n s z))\ \mathsf{succ}\ N &\to_{\beta} \\
(\lambda sz. s (\mathsf{succ}\ s\ z))\ N &\to_{\beta} \\
\lambda z. N\ (\mathsf{succ}\ N\ z) &\to_{\beta}^{*} &\text{(apply succ to N)}\\
\lambda z. N\ (\{N+1\}\ z) &=_{\alpha} &\text{(rename z → s)} \\
\lambda s. N\ (\{N+1\}\ s) &= &\text{unfold {N+1}} \\
\lambda s. N\ ((\lambda tz'. t^{N+1}\ z')\ s) &\to_{\beta} \\
\lambda s. N\ (\lambda z'. s^{N+1}\ z') &= &\text{(unfold N)} \\
\lambda s. (\lambda tz. t^{N}\ z)\ (\lambda z'. s^{N+1}\ z') &\to_{\beta} \\
\lambda s. (\lambda z. (\lambda z'. s^{N+1}\ z')^{N}\ z) &= &\text{(syntactic sugar)} \\
\lambda sz. (\lambda z'. s^{N+1}\ z')^{N}\ z &\to_{\eta} &\text{(η-reduction)} \\
\lambda sz. (s^{N+1})^{N}\ z &= \\
\lambda sz. s^{N(N+1)}\ z &= \\
N(N+1)
\end{array}$$


Does |xy| ≤ p in the pumping lemma count for all i? While learning about the pumping lemma, I came across the following question:

Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are 0, 1, a01, aa001, etc...

In regular english: a word with leading as, followed by any amount of either 0 or 1 characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of as.

My initial attempt was the following:

Pick w as $ a^p0^p1 $. This obviously holds since $ p \cdot 1 = p $.
Split w into xyz as $ x = \epsilon $, $ y = a^p $, $ z = 0^p1 $.
Show that $ xy^2z = a^{2p}0^p1 $ does not hold, since $ p \cdot 1 \ne 2p $.

However, the answer key instead opts to introduce two new variables $ m \geq 0 $, $ n \gt 0 $, then splits on $ x = a^m $, $ y = a^n $, $ z = a^{p-n-m}0^p1 $ (splitting the sequence of a into three parts). Then, they too use $ i = 2 $ to show that $ xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1 $, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $ |xy| \leq p $ condition of the pumping lemma: x is empty and $ |y| = p $. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually does violate the $ |xy| \leq p $ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?

Your mistake is in the following step:

  Split $w$ into $xyz$ as $x = \epsilon$, $y = a^p$, $z = 0^p 1$.

You're not allowed to choose how $w$ splits into $xyz$. You should show that for any way of splitting $w$ into $xyz$ such that $|xy| \leq p$ and $y \neq \epsilon$, there exists $i$ such that $xy^iz \notin L$.

Here is a similar "proof" that the language $01^*$ isn't regular:

Pick $w$ as $01^p$.
Split $w$ into $xyz$ as $x = \epsilon$, $y = 0$, $z = 1^p$.
Show that $xy^2z = 0^21^p$ is not in the language.

The proof of the pumping lemma will choose a different splitting, for example $x = 0$, $y = 1$, $z = 1^{p-1}$.


How to extract best illustrative sentences from documents for a given word? I want to extract "best" sentences from the given (html) documents. Let me illustrate this with an example. I have a word "determine". Now I have hundreds of html files having paragraphs and sentences that contain this word. Out of those sentences, I want to collect and score only those that are capable of describing or illustrating the meaning of "determine". Lets go further, following are the sentences I have collected from the web (from google search for the word, vocabulary.com, merriam-webster.com, yourdictionary.com) for the word "determine":

It will be her mental attitude that determines her future.
Officials are working with state police to determine the cause of a deadly bus crash.
They are unable to accurately determine the ship's position at this time.
The program officers were determined to do better on that front.
And how did you determine that?

In my case, I would like my algorithm to filter out (4) and (5) since they seem to be incomplete sentences in the sense they won't be able to better "illustrate" the word "determine". I won't entertain (1) as well since this sentence is not stronger enough to help the reader visualize the use of the word "determine", if we assume the reader is reading the word for the first time. Now for the remaining sentences (2) and (3), I would like to rate them to find their "usefulness".

For sure this is NLP problem and requires extensive research work to achieve. But still I am new to this domain, and it would be extremely helpful if anyone could point me towards the related works. I believe this forum is the good one to put such queries related to computer science.

Luhn, H.P. (1958, April). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159-165.

Describes the main elements of automatically creating literature abstracts. Significant sentences are candidates for inclusion into an abstract. The measure of sentence significance is based on significant words, and the proximity of significant words within sentences. Word significance is based on its frequency within the document; the word-frequency diagram depicts the set of words to consider as significant. Word significance also applies to the creation of indexes for search and retrieval.

Consider also the presentation I created when I took a graduate course: "Term Association and Thesaurus Construction"; you might find the references there useful too.


Why are there two different `until` ($\cup$) semantics in Timed Computation Tree Logic? Background:
In the book of Principles of Model Checking (Christel Baier and Joost-Peter Katoen, MIT Press, 2007), Section 9.2, page 701, the semantics of the until modality is defined over some time-divergent path $\pi \in s_0 \Rightarrow^{d_0} s_1 \Rightarrow^{d_1} \cdots \Rightarrow^{d_{i-1}} s_i \Rightarrow^{d_i} \cdots$ as follows:

(We can skip the formal definition at your first reading.)
$\pi \models \Phi \cup^{J} \Psi \iff$
$\exists i \ge 0. s_i + d \models \Psi \textrm{ for some } d \in [0,d_i] \textrm{ with } \sum_{k=0}^{i-1}d_k + d \in J \textrm{ and }$
$\forall j \le i. s_j + d' \models \Phi \lor \Psi \textrm{ for any } d' \in [0,d_j] \textrm{ with } \sum_{k=0}^{j-1} d_k + d' \le \sum_{k=0}^{i-1} d_k + d$.

  Intuitively, time-divergent path $\pi \in s_0 \Rightarrow^{d_0} s_1 \Rightarrow^{d_1} \cdots \Rightarrow^{d_{i-1}} s_i \Rightarrow^{d_i} \cdots$ satisfies $\Phi \cup^{J} \Psi$ whenever at some time point in $J$, a state is reached satisfying $\Psi$ and at all previous time instants $\Phi \lor \Psi$ holds.

However, in the book of Model Checking by E.M. Clarke (Section 16.3, Page 256), the semantics of the until modality is given as follows:

  $s \models E[\Phi \cup_{[a,b]} \Psi]$ if and only if there exists a path $\pi = s_0 s_1 s_2 \cdots$ starting at $s = s_0$ and some $i$ such that $a \le i \le b$ and $s_i \models \Psi$ and for all $j < i, s_j \models \Phi$.

As indicated, the second definition is stricter than the first one in that it does not allow the case of $\lnot \Phi \land \Psi$ before reaching a state satisfying $\Psi$.

Questions:

Why are there two different until ($\cup$) semantics in Timed Computation Tree Logic (TCTL)?
Which one is more official?

The two definitions are equivalent:

As you point out, the second one implies the first, as if $\phi$ holds, then clearly $\phi\vee \psi$ holds.

Conversely, consider a computation that satisfies the first definition, and assume by way of contradiction that it does not satisfy the second definition.
Thus, there exists some time in which $\psi$ holds, and in all previous times, $\psi\vee \phi$ holds. However, there also exists a previous time $d$ where $\psi\wedge \neg \phi$ holds, otherwise the second definition would hols.

Consider the minimal (or infimum) time $d$ for which this happens. Then in that time, $\psi$ holds, and in all previous times, $\psi\wedge \phi$ holds, so the second definition also holds for time $d$, which implies it for any later time.

Another way of looking on it: assume that the second definition doesn't hold, so either $\psi$ never holds, in which case clearly the first definition fails, or there is some minimal time $d$ where $\phi$ doesn't hold, and $\psi$ doesn't hold before $d$. In the latter case, $\phi\vee \psi$ also doesn't hold at time $d$, so the first definition doesn't hold.


In Probabilistic Graphical Models, are Cliques and Clusters the same? I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are the cliques and clusters the same?

A clique is a rigorously defined, exact part of a graph $G=(V,E)$;

$\qquad\displaystyle C \subseteq V \text{ is clique} \iff \{ \{u,v\} \mid u,v \in C, u \neq v \} \subseteq E$.

A cluster is more general, but also more nebulous. Here's what Wikipedia has to say:

  Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So, a cluster also is a set of nodes that is "dense" in some sense, depending on the metric used. However, while is it always clear whether adding a note increases the size of a clique, it's not always clear from looking only at one cluster whether adding a node to it is better; the quality of a clustering is defined on the whole graph.

As the Wikipedia article shows, there are many notions of clustering. Cliques can be seen as one of them.


Is object oriented programming considered to be a declarative programming approach? Is object oriented programming considered to be a declarative programming approach?
On Wikipedia, it is said that OOP tries to extend the imperative programming paradigm to a somewhat declarative programming approach, but what precisely makes OOP imperative or declarative?

When you write an OO code, you describe object features (attributes, properties, methods) and implement them. This may be seen as declarative: you do not have an imperative approach giving the sequence of operations to reach a given goal; you have a declarative approach describing features of objects, in a sense characterizing them.
To be more precise, let me take an example. When one says that an image has a filtered version, a blurred version, etc, this may be seen as declarative; these are features of any image. When one implements a procedure to filter or blur an image, then this is imperative: the code is thought of as a sequence of operations aiming at transforming an image, not a description of what the transformed image is.
I am not an expert, though, so I hope someone will correct this if needed.


Is final state mandatory in DFA(Deterministic Finite Automata) In state diagram of DFA is it mandatory to keep a final state. I mean whether DFA is possible without final state or not?

The definition of DFAs calls for a set of final (aka accepting) states. Nothing requires that set to be non-empty.  But note that a DFA without an accepting states can't accept any input, so all such DFAs are essentially equivalent to the one you drew.

Having said that, the class of languages accepted by DFAs wouldn't change if you insisted that every DFA must have at least one accepting state. You could still accept the empty language with an automaton whose state graph was disconnected, with all accepting states unreachable from the initial state. If you insisted on at least one accepting state and a connected state graph, the empty language wouldn't be accepted by any DFA.


Equivalence of Krom formulas tractable? Assume I have two Krom formulas $\psi_1, \psi_2$.  Krom formulas are propositional formulas in CNF that have 2 literals in every clause.  Each literal can be negated or unnegated.  In other words, $\psi_1,\psi_2$ are 2-CNF formulas.  For instance:
$(x_1 \vee \neg x_2) \land (\neg x_2 \vee x_3 ) \land (x_3 \vee x_4)$
I want to decide whether $\psi_1,\psi_2$ are logically equivalent, i.e., $\psi_1 \leftrightarrow \psi_2$.  Equivalently, I want to test whether  $F=(\psi_1 \vee \neg\psi_2)\wedge (\neg \psi_1 \vee \psi_2)$ is true for all assignments of $x_1,\dots,x_n$.
Is this problem tractable?

Recall 2-SAT solution which uses strongly connected components: we build a graph with vertices $x_1,\ldots,x_n, \lnot x_1, \ldots, \lnot x_n$, and we replace each clause $x_i \lor x_j$ with edges $\lnot x_i \to x_j$ and $\lnot x_j \to x_i$. An example from here:

To satisfy the formula, it's necessary and sufficient to assign vertices so that there are no contradictions in the graph (no edge $true \to false$). We'll use these graphs for equivalence checking.

We build these graphs $G_1$ and $G_2$ for both formulas $F_1$ and $F_2$.
If there is a cycle $x_i \leadsto \lnot x_i \leadsto x_i$ in a graph, then its formula has no solutions. We check that both formulas are solvable/unsolvable.
If there exists a path of form $x_i \leadsto \lnot x_i$ (similarly for the case $\lnot x_i \leadsto x_i$), we know that to satisfy the formula we must select $x_i$ to be false (otherwise we have a contradiction). We remember this choice. Using the graph, we can assign values to all vertices reachable from $\lnot x_i$ (they must be true). Again, check that both formulas made exactly the same decisions in the end.
Remove all edges to/from all known vertices from the graphs.
Now, $F_1$ and $F_2$ are equivalent $\iff$ the remaining graphs are equivalent in the following sense: for any $v_1,v_2$ path $v_1 \leadsto v_2$ exists in $G_1$ iff it exists in $G_2$. This can be checked in at most $O(|V|\cdot|E|)$ time (just run DFS from each vertex and check that it has visited the same vertices for both graphs). Maybe it can be done faster.

Proof:
$\Leftarrow$: evident, since after transitive closure of graphs we'll have the same implications in both formulas.
$\Rightarrow$: By contradiction. Wlog we assume that there exists a path $v_1 \leadsto v_2$ in $G_1$ which doesn't exist in $G_2$. It means that assignment $v_1 := true$, $v_2 := false$ is feasible in $F_2$ (since there is no path $v_1 \leadsto v_2$) but is infeasible in $F_1$.
Namely, the following assignment satisfies $F_2$:

$true$ for all vertices reachable from $v_1$.
$false$ from all vertices which can reach $v_2$.
Remove all known vertices (mentioned above and their complements) from the graph. All remaining vertices create connected components. We color connected components in $true$, and connected components corresponding to their complements - in $false$ (see note below).

This assignment has no contradiction, since there can be no edge $u \to v$ of form $true \to false$:

If $u$ belongs to a component which was full colored $true$, then such $v$ must also be true.
Otherwise, it means that $u$ is reachable from $v_1$, and therefore $v$ is also reachable from $v_1$ and must be true. $\blacksquare$

Technical note: for each variable $x_i$ there are two vertices: $v_i$ and $\lnot v_i$ - and one may wonder if it'll lead to some problems with assignments. The answer is that after step 4), $v_i$ and $\lnot v_i$ will lie in two different components (moreover, they are symmetric: $u \to v$ in one component means $\lnot u \to \lnot v$ in another one). Therefore, whatever decision we make for $u$ in one component, we can make the opposite decision for $\lnot u$ in another one.


Computing the minimum distance between each pain of points I am trying to read an algorithm for computing minimum distance between each pair of points  from the book: Algorithm Design

Algorithm Design

It considers the points in a line. If the points are in a line why we need to sort them? We can start from the beginning and compute the distances from starting pint to  all the points on the  right.

Some body please guide me why we need sorting?

Suppose the points are $[4,1,10,11]$.  The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points.

In this problem, the input is an array containing numbers, not in sorted order.


Is Post Correspondence Problem in NP? I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input configuration of pile
$$(t_1/b_1, t_2/b_2,...t_n/b_n)$$
concatenating $t_1, t_2,...,t_n$ as a string $t$ and concatenating $b_1, b_2, ..., b_n$ as a string $b$, then compare $t$ and $b$ to see if the two are equal and then conclude that the input is actually a solution to PCP.

The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the PCP instance). It turns out that in this case there isn't always a polynomial size solution even when the problem is solvable. In fact, there is no computable bound on the size of a potential solution, since otherwise the problem would be decidable!


Decide given complexity of given function I'm trying to determine correct notation for the given functions which are $f(n) = n$ and $g(n) = (log(n))^{100}$. Moreover, I don't understand while calculating its complexity using limit because calculator shows that it goes infinity, so  f(n) is growing faster than g(n). But, I found vice versa. Could you explain me where I'm doing wrong?

This answer assumes that $\log$ is to the base 2.

Consider $n = 2^{1000}$. Then
$$
f(n) = 2^{1000}, \quad g(n) = (\log_2 2^{1000})^{100} = (1000)^{100} < (1024)^{100} = (2^{10})^{100} = 2^{1000}.
$$
If you increase $n$ even more, you will see an even more dramatic difference between $f(n)$ and $g(n)$. You just have to consider large enough $n$, perhaps too large for your calculator.

What this example shows that even though $f(n)$ grows faster than $g(n)$, for values of $n$ encountered in practice the situation is very different, with $g(n)$ being much larger than $f(n)$. This shows the limits of asymptotic analysis – it is a natural and useful mathematical notion, but it isn't always a good model for reality.


What type of recursion is this? I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar:

$\qquad  A \to 0 A 1 \mid 0 1$

Which produces:

$\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \Rightarrow \dots$

But I am unsure what type of recursion this is called, since it sorta stays in the middle.

If this is not left-recursive, would you agree that this is not LL(1) because non-terminal A has 0 appear twice in FIRST(A)?

What is a name for ?

There may be a name for that recursion, but then I would have
forgotten it. It does not really matter. Call it central recursion or
middle recursion if you will. And you can even define it simply :

  A recursive rule (or non-terminal) is said to be middle recursive iff it is recursive, but neither left recursive nor right recursive.

If I have to write a paper, and cannot find the accepted name for
something, and there may be none, then I make one up and give a proper
definition for it so that people can read my paper.

The point is that not everything needs to have a specific name. You
give names only to entities and concepts that play a specific role in
the kind of work you are doing. You example seems to be just a general
case of recursion, which happens to be neither left nor right.

Left recursion is important as it plays a significant role when you
study left-to-right recursive descent parsers. Hence it was given a
name.

Regarding your second question, I would agree. This may even happen in
the absence of recursion, with a grammar generating a finite language.
$\qquad  A \to 0 0 \mid 0 1$
But there are other grammars for that language. This grammar is not LL(1), but the language is.


Approximation with imperfect dichotomy oracle Given an unknown $x$ and an oracle $O(r)$ such that:

If $O(r)$ is true then $x \geq r$.
If $O(r)$ is false then $x < 2r$.

Conversely, the oracle has a defined behaviour only outside the interval $(x/2, x]$, and may output anything between.

We want to find a factor 2 approximation of $x$.

What is the strategy with a minimal number of calls to $O$?

I found thanks to @YuvalFilmus 's advice! (if you want me to remove this answer and post it yourself, feel free to ask)
1. We find a factor 4 approximation
If we know a value r s.t. O(r/2) = True and O(r) = False, then we know that x is in [r/2, 2*r[.
And for any starting point y, while O(y) = True we multiply y by 2 until we have O(y) = False, and conversely for O(y) = False to find such a value.
By the properties of the oracle, this terminates. We have a logarithmic complexity. But when evaluating $O(y \times 2^k)$ for an integer k, we know that there is an index that separates the True values from the False. Thus we can apply binary search on this logarithmic scale to have a $\log(\log(x))$ number of evaluations of the oracle.
2. We transform a $2^{1+\frac{1}{k}}$ approximation in a $2^{1+\frac{1}{2k}}$ approximation
Suppose you know $x\in[a, b[$ with $\frac{b}{a} = 2^{1+\frac{1}{k}}$.
Take $c = a * 2^\frac{1}{2k}$.
We know that if $x \in [a, c[$, then $O(c)$ is false, and that if $x \in [2c, b[$, then $O(c)$ is true.
Thus we can eliminate one interval of ratio $2^\frac{1}{2k}$, and the remaining interval is of ratio $2^{1+\frac{1}{k}-\frac{1}{2k}}$ = $2^{1+\frac{1}{2k}}$.
3. Complexity
We make $\log(\log(x))$ calls to the oracle in the first stage, and then $i$ to get a $2^{1+\frac{1}{2^i}}$ approximation factor.
For example, if you work with integers, the stop condition is $ x * (2^{1 + \frac{1}{2^i}} - 2) < 1 $. A Taylor expansion gives us $i > \log(x) + 1$ with the first term, so $i > \log(x) + 2$ should be fine.
4. Other strategies
Like shown below, more evaluations per step could get us immediately better approximation factors than 2.
However, it requires too much evaluations, with no improvement in the worst case when the oracle is a threshold function.
Let $x_1, x_2 = \frac{r}{2}, x_3, x_4=b, x_5, x_6=2r$ be numbers in geometric progression of ratio $\sqrt2$ with $r$ found after the first stage.
We know $O(x_2) = T, O(x_4) = F, O(x_6) = F$, and we know $x \in [x_2, x_6[$. We split this interval in 4 and look at the values of $O(x_1), O(x_3), O(x_5)$. We note $?$ when a value can be True or False.
For $x\in[x_2,x_3[$, the possible values are $?, F, F$.
For $x\in[x_3,x_4[$, the possible values are $T, ?, F$.
For $x\in[x_4,x_5[$, the possible values are $T, ?, F$.
For $x\in[x_5,x_6[$, the possible values are $T, T, ?$.
If we get $O(x_1) = F$ or $O(x_5) = T$, we know a $\sqrt2$ factor approximation of x. Else, the value of $x_3 = c$ allows us to eliminate either the leftmost or the rightmost interval, which is exactly the first step of the second stage of our general strategy to transform a $4 = 2^{1 + \frac{1}{1}}$ approximation into a $2\sqrt2 = 2^{1 + \frac{1}{2}}$ approximation.


How to prove 3CLIQUE is decidable From our computational complexity, there's a question asking to prove 3CLIQUE is decidable.

The definition of 3CLIQUE is:
$$\{(V,E) : G = (V,E)\text{ is an undirected graph that contains a clique of size 3}\}.$$

I know this is an NP problem, and NP is a set of problems that easy to verify but hard to solve, but I don't know how to prove. Is there anyone who can help me on this?

In fact, NP is not the set of problems that are easy to verify but hard to solve. It is just the set of problems that are easy to verify. NPC, the set of NP-complete problems, is the set of problems that are easy to verify but seem hard to solve.

Your problem is in NP but it isn't NP-complete (unless P=NP), since it's also in P. That is, it can be solved in polynomial time. To prove this, you need to give a polynomial time algorithm that, given a graph $G=(V,E)$, determines whether it contains a clique of size 3. I trust that you are able to do it yourself.


clustering with uncertain number of clusters I detect a unmanned aerial vehicle(UAV) in a picture using template matching. The template library only contains targets with different scales, rotations and other differences.I want to simplify the template library using clustering. I learned the k-means and Gaussian mixture model（GMM）but they all need determine the value of k.Are there any approaches which can solve my problem?

Several algorithms allow doing this.
First one is the hierarchical clustering. When creating your dendrogram, the key is to cut the "longest branches." DBSCAN is also a good alternative. Finally, you can use K-means or GMM and optimize your number of cluster against a metrics (see sklearn pages on the subject) (be aware of overfitting)


Do any two spanning trees of a simple graph always have some common edges? I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far.  But I couldn't prove or disprove this either.  How to prove or disprove this conjecture?

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:


How to decompose a unit cube into tetrahedra? I was presented with the problem of breaking the unit cube $[0,1] \times [0,1] \times [0,1] $ into tetrahedron shapes.  The first two pieces are easy, but it's not so easy to visualize after that.  I found:

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

What remains is a triangular prism.  Then maybe I think it readily splits into 2 or 3 pieces.  In any case, they are difficult to draw and keep track of all the data.

Also I think I could have started differently with this other tetrahedron:

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

There should be lots of solutions, but I neither have the date to store into a computer nor do I have picture of even a single one.


How to prove the language of all Turing Machines that accept an undecidable language is undecidable? I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable
I am not sure about this. This is my try :
Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be a TM which is recognizing $A_{TM}$.
Let $S$ be a TM which works on input $\langle M,w \rangle$ in the following way(the goal is that $S$ will be a decider for $A_{TM}$):

Construct a TM $N$ which works on Input $x$ as follows: Run $M$ on $w$. If $M$ $accepts$ run $A$ on $x$ and accept $x$ if $A$ accepts.(In this case is $L(N)=A_{TM}$). If $M$ $rejects$ $w$, $accept$ $x$.(In this case is $L(N)=\Sigma^*$)
Run $E$ on $N$ and accept if N accepts. Otherwise reject

I am not sure if my reduction is the right way or not. Maybe someone can help to finish the reduction :)

I think you are on the right track but things need to be made more explicit. First, what machine exactly is $A$? Any machine? Where does your contradiction appear?
First, you need to explicitly say that $A$ is a machine for an undecidable language, for example, let $A$ be the universal machine, that on inputs $\langle M \rangle w$ simulates $M$ on $w$, and accepts if $M$ accepts $w$.
Then, say explicitly that $S$ is a decider (a machine that always halts), and include the simple extra steps that show that $S$ accepts $\langle M \rangle w$ if and only if $w \in L(M)$. Finally, recall that $S$ is then a decider for a problem we already know is undecidable; a contradiction.
Edit: Sorry, it seems that $A_{TM}$ is standard notation for the universal machine. Forget about that comment if that is the notation used in your context.


How do we define if a Turing machine goes to the right or left? In my college course notes, we are given two examples.

  Example 9.1.1:
  $$ M(K, \Sigma, \delta, s) $$
  where

  $ K = \{q_0, q_1\} $
  $\Sigma = \{a, \# \}$
  $s = q_0$
  $ \delta = \begin{array}{|c|c|c|c|}
\hline
q & \sigma & \delta(q, \sigma) \\ \hline
q_0 & a & (q_1, \#) \\
q_0 & \# & (h, \#) \\
q_1 & a & (q_0, a) \\
q_1 & \# & (q_0, R) \\ \hline
\end{array}$

  Note that state $(q_1, a)$ cannot happen if the start state is $q_0$. This is included only for completeness (to make $\delta$ a total function).

  This machine will scan right, changing any $a$ that sees to a $\#$. When it first hits a $\#$, it will halt.

  Example 9.1.2:
  $$ M(K, \Sigma, \delta, s) $$
  where

  $ K = \{q_0\} $
  $\Sigma = \{a, \# \}$
  $s = q_0$
  $ \delta = \begin{array}{|c|c|c|c|}
\hline
q & \sigma & \delta(q, \sigma) \\ \hline
q_0 & a & (q_0, L) \\
q_0 & \# & (h, \#) \\ \hline
\end{array}$

  This machine will scan left until it encounters $\#$, then halt.

One TM goes to the right while the other goes to the left. Obviously this is determined by the transition rules, but how do we explicitly know/define where to start (either on the left of the string or right?).

I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?

It's not specified in the description you gave, but absent directions to the contrary, a TM is generally understood to start at the leftmost non-blank cell.


Longest common substring in linear time We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity.
Can a solution be found in only linear time?

Let $m$ and $n$ be the lengths of two given strings,
Linear time assuming the size of the alphabet is constant.
Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, assuming the size of the alphabet is constant.
Here is an excerpt from Wikipedia article on longest common substring problem.

The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

Building a generalized suffix tree for two given strings takes $O(m+n)$ time using the famous ingenious Ukkonen's algorithm. Finding the deepest internal nodes that come from both strings takes $O(m+n)$ time. Hence we can find the longest common substring in $O(m+n)$ time.
For a working implementation, please take a look at Suffix Tree Application 5 – Longest Common Substring at GeeksforGeeks
(Improved!) Linear time
In fact, the longest common substring of two given strings can be found in $O(m+n)$ time regardless of the size of the alphabet.
Here is the abstract of Computing Longest Common Substrings Via Suffix Arrays by Babenko, Maxim & Starikovskaya, Tatiana. (2008).

Given a set of $N$ strings $A = \{\alpha_1,\cdots,\alpha_N\}$ of total length $n$ over alphabet $\Sigma$ one may ask to find, for each $2 \le k\le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in $O(n)$ time with the help of suffix trees. However, the resulting algorithm is rather complicated (in particular, it involves answering certain least common ancestor queries in $O(1)$ time). Also, its running time and memory consumption may depend on $|\Sigma|$.
This paper presents an alternative, remarkably simple approach to
the above problem, which relies on the notion of suffix arrays. Once
the suffix array of some auxiliary $O(n)$-length string is computed, one
needs a simple $O(n)$-time postprocessing to find the requested longest
substring. Since a number of efficient and simple linear-time algorithms
for constructing suffix arrays has been recently developed (with constant
not depending on $|\Sigma|$), our approach seems to be quite practical.

Here is the general idea of the algorithm in the paper above. Let string $\alpha$ be concatenation of all $\alpha_i$ with separating sentinels. Construct the suffix array for $α$ as well as its longest-common-prefix array. Apply a sliding window technique to these arrays to obtain the longest common substrings.


Turing machine different accepting states I want to design a Turing machine that accepts at most 3 0s. Now, I have designed one, which goes to accept state overtime it sees 1, 2 and 3 0s and rejects any further 0s. I wanted to know if it is okay for TM to go to accepting state from 3 different states?

Of course, a Turing machine can transition to a given state from as many other states as you like. Machines used in halting problem reductions usually have an "infinite loop" state that only transitions back to itself, and many other states that transition into that one.


What does "Outstanding" mean in the context of architecture? I'm taking an Advanced Computer Architecture course and I've come across the term "outstanding" a few times and I've searched online about what it means in the context of computer science/architecture but I can't find anything relevant. For example, on my notes there are some references such as:

"IBM Power5 allows 8 outstanding cache line misses"
"Each thread can perform 8 outstanding memory accesses"

Outstanding means, it hasn't been resolved. In the case of cache misses, that means the data request has not been serviced yet. When a cache miss happens, it has to fetch the data from the next level cache/memory, until this data arrives, you need to hold this request somewhere. You've got two options in this situation. Either block the entire cache, until data from the next level arrives. This is the easiest to implement, but quite bad in terms of performance. On the other hand, you could save the information about this data request somewhere, and carry on servicing others. This is is much better in terms of performance. Now, coming to this "place" where you are going to store information about the pending cache miss, this is a hardware structure. So you can only have finite number of "outstanding" misses. Number of entries in this buffer, is what is being provided as the number of outstanding cache misses.


What does a solution to the Rectangle-Fit problem look like? I've been learning about NP-Complete problems, and came across the rectangle fit problem. Basically, the rectangle-fit problem is the problem of whether or not a set of 2d rectangles can fit in a larger 2d rectangle. What I have not been able to find, or solve myself, is what a possible solution looks like.

Say there is a set of rectangles $R$ and a large rectangle $T$, how do I indicate a possible placement of all rectangles in $R$ into $T$? I was thinking coordinates, but there is no assumption $T$ is defined as a graph. At a high level, how would I denote where/how each rectangle should be placed?

I am not asking for how to solve this NP-Complete problem. I am asking how do I define the placement of rectangles in $R$ for a candidate solution. I saw an academic paper saying that it is obvious there is a polynomial time verifier for the problem, but there was no explanation of what the certificate the verifier is using looks like.

Particularly, I was looking at: http://ranger.uta.edu/~weems/NOTES5311/hw3ansold.pdf for the verifier.

You can simply list the coordinates of the upper-left corner of each rectangle (and its orientation, if you're allowed to rotate rectangles).  That completely determines its position, and thus listing that for all rectangles completely identifies the configuration of all rectangles.


why does $ A≤_p \#SAT$ if $A \in BPP$ hello and thank you for helping me understand the following:

I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?

language A is in BPP class, if for a probabilistic turing machine M, M outputs 1 for all $x \in A$ in a probability $\geq 2/3$, and for all $x \not \in A$ M outputs 1 in a probability of $\leq 1/3$ and of course M must run in a polynomial time on all inputs.

so if $A \in BPP$, why does it mean that $A≤_P\#SAT$? if M is reduced to boolean F, it means that we'll get output of 1 in a probability of $\geq 2/3$ for every $x \in A$? why?

can someone please show me algorithmically or mathmatically why if language $A \in BPP$ then $A≤_P\#SAT$? quite lost

thank you, would appreciate if you could explain along.

Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any accepting run of $M$, there is exactly one setting of $z$ which satisfies $\phi$.

By definition, if $x \in L$ then $\phi$ has at least $(2/3)2^m$ satisfying assignments, and if $x \notin L$ then $\phi$ has at most $(1/3)2^m$ satisfying assignments. You can distinguish between the two cases using a $\mathsf{\#SAT}$ oracle.


How to check if a list of XY coordinate meet the safety distance to each others? My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I draw a circle with radius R at every points, would any circle cross other circles on the plane.

I want to code this in Python, if that matters.

The problem you are solving has many well-known efficient algorithms.

The problem is to find closest pair of points in the plane.
If the closest pair have distance less than the safety distance, you already have a pair.
If not, no other pair can have a less distance, and hence all pairs are safe.

One efficient way to solve this problem is using divide and conquer. The algorithm is practical and easy to implement. It has run-time $O(n \log n)$ (check the notes at the end).

It might be an over-kill, but as efficient from the theoretical point of view, to build Delaunay-Triangulation over the set of points and compare each point to its neighbors in the triangulation, which is also achievable in $O(n \log n)$.

There are many libraries that offer a ready-to-use Delaunay-Triangulation (you can check CGAL-Boost library for C++), which makes it an easier way to implement that the previous method.

ps. Another very well-known approach, used in many different problems is line-sweep. There is also a line-sweep $O(n \log n)$ algorithm for Closest pair of points problem. (please check the link).


Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)? According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments.

There's no explanation given for this substantial difference between two similar algorithms, both variants of Bubble-sort. Can anyone help explain it?

Sorting is all about removing inversions.

Combsort is much faster than cock-tail sort because it does more "long range" comparisons and exchanges; exchanging two out-of-order elements that are far apart will (on average) remove (a lot more) more inversions than exchanging two that are close together.

As for the formula you quote... well, Wikipedia's wrong.  Combsort isn't that much faster.  The formula you quote is a (very) weak lower bound on the average number of comparisons (try substituting p=2.log2(n) into the formula. Combsort can't possibly require only O(1) comparisons to perform the whole sort because... it's obviously had to do about pn, before the insertion sort phase, at the end of the sort, even begins).

[I think that formula has been (mis)quoted on the Wikipedia Combsort page since something like 2008, and I don't think anyone bothered to point out, even on Wikipedia's Combsort talk page, that the paper being referenced gave it as a formula, only for a lower bound, before June 2013.]

In practice, unless you are sorting billions of records, if you use increments that are relatively prime and have a growth ratio of 1.25 or so, Combsort will require (on average) about 3*log2(n)*n comparisons (and will generally run somewhere between 2 and 3 times slower than a quicksort or a mergesort, if you are sorting, say, integers).

You are unlikely to run into Combsort's (quadratic) worst case unless you deliberately engineer an input that will cause it.


Comparing asymptotic complexity of functions $\log{n}$, $(\log{n})^c$ and $\sqrt{n}$ I usually follow approach of taking logs and putting arbitrary large powers of $2$ for $n$ and reducing the given function to some constant value for large value of $n$. So in this case I did it as follows:

$\log{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\log(2^{2^{2^{16}}})}={2^{16}}$

$(\log{n})^c$

Putting $n=2^{2^{2^{16}}}$, $c=2$ and taking $\log$

$\log({(\log{2^{2^{2^{16}}}})^2})=\log({2\times(\log{2^{2^{2^{16}}}})})=\log({2\times(2^{2^{16}})})=\log{2}\times\log{2^{2^{16}}}$

$=1+2^{16}$

$\sqrt{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\sqrt{2^{2^{2^{16}}}}}=\log{2^{2^{2^{{16}^{\frac{1}{2}}}}}}=\log{2^{2^{2^8}}}=2^{2^8}=2^{16}$

So it looks like:

$\log{n}=\sqrt{n}<(\log {n})^c$

However I checked that $\log{8}>\sqrt{8}$. But, $\log{(2^{2^{2^{16}}})}=64$, whereas $\sqrt{2^{2^{2^{16}}}}$ is much larger number making equality between the two unlikely.

So where I am making mistakes in above calculations?
How above three functions compare asymptotically?

for any $c>1,\epsilon>0$,
$$\lim_{n\to\infty} \frac{(\log n)^c}{n^\epsilon} = 0$$

This means that $\log n=o( (\log n)^c)$ and $(\log n)^c = o(n^\epsilon)$. In particular, for $\epsilon =0.5$, $(\log n)^c = o(\sqrt{n})$.

See Reference answers to frequently asked questions


Can a simulation be conducted in which the inhabitants would observe infinite time divisibility? In this video, a physics theorist talks with his collegues claiming to have found evidence for Simulation Theory. I'm not here to ask about the various proofs for and against ST - that's basically in the realm of philosophy at this point.

But one of the physicists claims that because of the nature of mathematics, it's impossible to simulate a particular aspect of our universe: infinite divisibility of time. The theorist responded that math can be used to describe infinite time division, which is all the simulation would need to do.

My question is this: In Computer Science, can we determine whether it is or is not possible through any currently known medium of computing to create a simulation in which the inhabitants would be able to observe infinite time divisibility?

Elaboration:

If you simulate things at a rate of infinite divisions per second of simulated time, you could never simulate the entire second right? The simulation would hang infinitely? The question is whether you could simulate based on something other than an interval, like in quantum physics, things (seem to) happen more or less precisely on a small level based on whether or not they're being observed (Disclaimer: that's a severe oversimplification).

Whether in CS this method of simulation (resulting in observed but perhaps not literal infinite time divisibility) is fundamentally possible via the computing formats we're aware of is my question. I think it's quite an interesting fundamental CS question.

Somehow the simulation would have to describe the occurrence of events via functions, not increments, which make it look like to an observer within the simulation that there is no smallest increment.

Yes, you can compute over continuous quantities. Calculus is an example.

If it was actually impossible to compute how a continuous system would behave, then how did this physicist end up believing reality is continuous? How did they make predictions that were confirmed by experiment, scientifically justifying their belief, if they weren't able to calculate any predictions?


Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS) I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function.
The versions are as follows:

Definition 1: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be universal if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

Now in the above definition the authors are using "for each pair of distinct keys $k,l\in U$" to mean that probably we do not leave out any possible key pair for which collision occurs.

Definition 2: With a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ which is the chance of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$.

Through-out the rest of the book the author uses the second definition.
I felt like finding the equivalence of the two definitions.

Definition 1 $\implies$ Definition 2

Definition $1$ says that for a pair of distinct keys says $k,l$ for the set $A=\{h \in \mathscr{H} : h(k)=h(l)\}$ ,
$$|A|\leqslant|\mathscr{H}|/m \tag 1$$
Now if we chose a hash function $h\in \mathscr{H}$ at random then for the said pair of distinct keys $k,l$ we have,
$$ Pr\{h(k)=h(l)\} = \frac{\text{no. of functions in A}}{\text{no. of functions in $\mathscr{H}$}}=\frac{|A|}{|\mathscr{H}|} \leqslant\frac{1}{m} \quad\text{using (1)}$$

I could not quite find a way to show that:
$$\text{Definition 2 $\implies$ Definition 1}$$
Or the way I proved the first implication actually proves the equivalent...
Previously I made an attempt but it was wrong as it was pointed out and so that wrong portion has been edited out.
I had found two similar questions 1 and 2 but it did not quite seem to answer my query.

Both definitions are equivalent, and I think you have almost specified the reason behind it.
The below equivalence work in both ways.
From Definition 2:
"the chance of a collision between distinct keys $k$ and $l$" $\le$ $1/m$
$\Leftrightarrow$
{note that the "chance" here is about the process of picking $h$ from the class $\mathscr{H}$}
(Number of functions in the class where $k$ and $l$ collide) $/$ (Total functions in the class) $\le$ $1/m$
$|A|/|\mathscr{H}| \le 1/m$
$\Leftrightarrow$
$|A| \le |\mathscr{H}|/m$
(which is the wording used in Definition 1)


Maximum number of distinct values for bitwise OR You are given an array with $N$ elements. The values of the elements may be any number in the interval $[0,10^9]$. Define $f(a,b)$ as the bitwise or of all the values in the subarray $[a,b]$. Find a bound on the number of distinct values of $f(a,b)$.

Attempts: I have tried to brute force cases to find a pattern but was unsuccessful.

Please explain the reasoning behind your answer. I am a complete beginner.

Notice that the max value here given is 1e9. Therefore at most log(1e9) bits can be there. Suppose we fix an 'a' and iterate over 'b' such that b>=a. Thus this will form a monotonic function as bitwise OR can only increase the value of the initial operands. Moreover the OR operation can only turn a bit ON from OFF and not the other way round. So whenever the values increases that means a new bit has to be set ON. However for a fixed value of 'a' we can only turn on at most log(1e9) bits. Hence when we iterate over 'a' we can have a maximum bound of O(n)O(log(1e9)) distinct values. Hence the bound is O(nlog(MAX_VALUE))


Is this problem that's similar to integer linear programming also an NP-complete problem? I've come across this problem while trying to work out a table-formatting algorithm.

It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely familiar with linear programming, but I believe this doesn't matter much).

Let $\vec v = (v_1, \dots, v_n)$ be a vector of positive-integer variables.

The problem is to find if there is an assignment to $\vec v$ such that

$$ v_1 + \dots + v_n = c $$

and

$$ A \vec v \geq \vec w $$

where $c$ is a known constant, $\vec w$ is a known constant, and $A$ is a matrix with the special property that each row of $A$ is of the form $(0, \dots, 0, 1, \dots, 1, 0, \dots, 0)$.

That is, each inequality constraint only uses coefficients 1 and 0, and only "consecutive" variables appear in each linear constraint.

I think that this problem is NP-complete, but I haven't been able to prove it.

I think a reduction to exactly-1-in-3-SAT or set-cover is most likely to succeed (variables would be literals/values respectively and rows in the matrix would correspond to clauses/sets), but the restriction that constraints only refer to consecutive variables doesn't seem strong enough to describe arbitrary clauses/sets.

Alternatively, I might be wrong, and this problem actually has an algorithm that I have been missing. (The problem I'm actually interested in solving is finding the smallest $c$ such that constraints remain satisfiable, but I've phrased the problem this way so that it remains a simple decision problem)

As an example, here's a small instance of this problem:

$$
\begin{array}{}
v_1 + v_2 + v_3 + v_4&=& 10 \\
v_1 &\geq& 1 \\
v_2 &\geq& 1 \\
v_2 + v_3 &\geq & 3 \\
v_3 + v_4 & \geq & 4 \\
v_3 &\geq& 1 \\
v_4 &\geq& 1
\end{array}
$$

which has a possible assignment $\vec v = (1, 1, 6, 2) $.

Your problem is solvable in polynomial time.

Your problem is equivalent to ILP with difference constraints, i.e., every linear inequality has the form $x_j - x_i \ge c_{i,j}$.  (Why?  Set $x_i = v_1 + \dots + v_i$; then $v_{i+1} + \dots + v_j = x_j - x_i$.)

Such a system of inequalities can be solved with shortest-path algorithms.  In particular, if we didn't have the restriction to integer values, this becomes the standard problem of solving a system of difference constraints.  You can solve this by creating a graph with one vertex per variable and one edge per constraints, and finding shortest paths using Bellman-Ford.  See, e.g., Algorithms: Difference Constraints, Decide whether a set of inequalities is solvable, http://videolectures.net/mit6046jf05_demaine_lec18/, or a good textbook (I think this is described in CLRS).

As stated, those algorithms don't take into account the restriction to integer solutions.  But if you examine how shortest path algorithms work, if all of the constants are integers, then the solution will be an integer solution as well.  So, that ensures you get an integer solution.

Lastly, the requirement that $v_1 + \dots + v_n = c$ is equivalent to $x_n = c$, which can be handled using the shortest paths algorithm.  In particular, find a solution; then if $x_n \ne c$, then set $c' = c - x_n$ and add the constant $c'$ to all variables; the result will be another solution that satisfies all the inequalities, and also satisfies the equality $x_n = c$.

Finally, once you've solved to find a solution for the $x$'s, you can recover a solution for the $v$'s by setting $v_i = x_i - x_{i-1}$.

One catch is that this solution might not be all positive.  To handle this, I suggest adding the inequalities $x_i - x_{i-1} \ge 0$ before solving.  That will then meet all of your needs.


Reduce Max-Cut to Max-2SAT I would like to find a reduction from Max-Cut to Max-2Sat.
Could someone shed light on this problem, preferably spiced with some intuition?

Thanks,
Matan.

Given an instance $G = (V,E)$ for Max-Cut, we create an instance of Max-2Sat with one variable $x_v$ per vertex $v \in V$, and two clauses per edge $(v,w) \in E$:
$$ x_v \lor x_w, \qquad\overline{x_v} \lor \overline{x_w}. $$
Every subset of $V$ corresponds to a truth assignment for the $x_v$ in a natural way. Furthermore, the number of clauses satisfied is exactly
$$ |E| + |E(V,\overline{V})|. $$
Intuitively, the edge $(v,w)$ is cut iff $(x_v \lor x_w) \land (\overline{x_v} \lor \overline{x_w})$, and this is why this reduction works.


Comparing different implementations of genetic algorithms I am looking up some material for my thesis in CS (development of a module to integrate a genetic algorithm in a system developed by other students).

My actual current task is to make a comparative analysis of several libraries for genetic algorithms.
After this comparison I will choose one of these libraries and an algorithm.

I want to know if you can give me any tips or best practice to perform such comparison. Which approach to the task would you recommend?

Your first step, when doing a comparative analysis, is to identify your requirements.  We can't tell you what the requirements should be; that's something you'll need to figure out on your own.

Then, you can try to evaluate the libraries to determine how well they meet your requirements.  The particular style of evaluation depends upon what kind of requirement you want to evaluate.  For instance, evaluating performance is very different from evaluating reliability.


rope data structure - undo operation I was reading (wikipedia) about how the rope data structure might be suitable for a text editor.  Within the article it mentions "If only nondestructive versions of operations are used, rope is a persistent data structure. For the text editing program example, this leads to an easy support for multiple undo levels."  I don't understand how the undo works in this.

For example, let's say i had an existing rope with the left leaf as "hello" and the right leaf as "world".  The parent (root) would have the value 5 (length of hello).  Then, if i were to delete "world" i am just left with the root and left (hello) node.  Now, if i wanted to "undo" the delete, haven't I already discarded the "world" node?  Traditionally "undo" is done by placing things on a stack, but in this case I don't understand if using a stack what to put on it or how to do the undo in general.

The approach is to build a fully persistent version of the rope data structure.  This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world") and version 2 ("hello").  To undo the last operation, you just start working from version 1 rather than version 2.  In particular, yes, you can store these pointers in a stack data structure. The point is that each modification creates what is effectively a new copy of the data structure, without modifying the old version.  Of course, actually making an entire copy would be inefficient, so what the data structure does is share the parts of the tree that are unchanged.

For details on how to make a persistent version of the data structure, see What classes of data structures can be made persistent?.  See also Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration.


How is the oracle function for Grover's Search algorithm obtained? I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ they want to use. In other words, they are explicitly putting in a set of gates of what they want to find before they look for it, then they get what they want -- a self-fulfilling prophecy.

How is the oracle function really implemented so that by simply looking at the choice of oracle function you don't immediately know the answer without evaluating it?

Here's the problem Grover's algorithm helps you solve:

Input: a function $f$
Output: a value $r$ such that $f(r)=0$

If you're paying attention, you should ask how $f$ is specified.  This is the oracle part: $f$ is provided as a black box.  That means, given any $x$, the algorithm can evaluate $f(x)$, but the algorithm can't "look inside the black box" and see how $x$ is represented.  So, the algorithm doesn't have a way to "look at the choice of oracle function"; all the algorithm can do is supply some value $x$ and ask for the value of $f(x)$, and do that over and over again.

Why is this useful?  There are some situations where we can easily specify a function $f$ but it seems to be very hard to find a value $r$ such that $f(r)=0$.  (In fact, in many of those situations, even knowing how $f$ is implemented doesn't seem to help.)  For instance, $f$ might be the SHA256 cryptographic hashing function: given any string $x$, we can efficiently compute its hash $f(x)$, but there seems to be no way to invert it short of trying lots and lots of candidate strings to see if any of them work.

Another example is $f(x,y)=x \times y - 179...23$, where $179..23$ is some specific large number that is known to be a product of two primes but whose factorization is unknown (we don't know what the primes are) -- we probably wouldn't actually use Grover's algorithm on that specific example, but it illustrates an example where we know how to specify a function where it's still hard to find an input that maps to zero.

Take a look at https://en.wikipedia.org/wiki/One-way_function and https://en.wikipedia.org/wiki/Grover%27s_algorithm.


Is there a connection between the halting problem and thermodynamic entropy? Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem.

A TM is an abstract concept of a machine (or engine if you like). The Halting Theorem is an impossibility result. A Carnot Engine (CE) is an abstract concept of a heat engine and Carnot proved the Carnot Theorem, another impossibility result related to thermodynamic entropy.

  Given that a TM is physically realizable (at least as much as a CE, or maybe not?) is there a mapping or representation or "isomorphism" of TM or CE which could allow to unify these results and in addition connect to entropy?

There are of course formulations of TM and the Halting Theorem in terms of algorithmic information theory (e.g. Chaitin, Kolmogorov etc.) and entropy (in that context). The question asks for the more physical concept of entropy (if in the process of a potential answer algorithmic entropy arises it is fine, but it is not what the question asks exactly).

One can also check another question in physics.se which relates quantum uncertainty with the 2nd law of thermodynamics. See also: an algebraic characterization of entropy, an algorithmic characterization of entropy, a review and connections between various formulations of entropy

I am not at all an expert in this area, but I believe you will be interested in reversible computing.  This involves, among other things, the study of the relationship between processes that are physically reversible and processes that are logically reversible.  I think it would be fair to say that the "founders" of the field were/are Ralph Landauer and Charles H Bennett (both of IBM research, I think.)

It touches on quantum computing and quantum information theory, but also examines questions like "what are the limits of computation in terms of time, space and energy?"  It is known, (if I remember correctly) that you can make the energy required to perform a reversible calculation arbitrarily small by making it take an arbitrarily long time.  That is, energy $\times$ time (=action) required to perform a reversible computation can be made a constant.  This is not the case for non-reversible computations.

Many of the people studying in this area are also working on quantum computing and digitial physics (the idea that the universe is a big quantum cellular automata).  The researchers names that come to mind are Ed Fredkin, Tommaso Toffoli and Norm Margolus.

These questions are absolutely on topic for computer science.  Not just for the theory (which includes cool math as well as cool physics) but for engineers who want to know the ultimate limits of computation.  Is there a minimum volume or energy required to store a bit of information?  The action required to perform a reversible computation may be constant, but are there limits on what that constant is?  These are critical knowledge for engineers trying to push the boundaries of what is possible.


Basic questions about network flow calculations Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to each edge $e$ of the graph a capacity $c_e$ is assigned (which can be defined as a function vertex properties of the endpoints of an edge), and in analogy to flow of water through pipes for example, a net flow is assumed to take place from the source towards the sink. That is the net flow out of the source, is equal to the net flow entering the sink:
$$
\sum_{u\in O(s)} f(s,u)-\sum_{u\in I(s)}f(u,s)=\sum_{u\in I(t)} f(u,t)-\sum_{u\in O(t)}f(t,u)
$$
where $O(s)$ denotes the set of vertices, that $s$ is incident on, and $I(s)$ denotes the set of vertices that are incident to $s.$
Now often, one is interested in computing the maximum possible flow in the graph, which leads to using Menger's theorem, which relates maximum number of distinct paths (between $s$ and $t$) to the minimal cut-set, or in a general setting, it relates the maximum flow to minimum cut capacity (summing the capacities of the minimum cut, that disconnects source from sink).

There are many algorithms that allow computing the maximum flow rather efficiently, for a given digraph. But my questions are (sadly) rather basic, but are solely related to computing maximum flow:

Assuming the capacities of all the edges are known, why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities? or am I wrong?
How are then the individual flows $f$, through each edge $e$ (where $f_e\le c_e $), calculated when we are estimating the maximum flow? Do we set all flows equal to respective capacities (i.e. $f_e=c_e$)?  Or is the individual flow, a function of the minimum capacity ($\text{min}(c_e)$ for all edges $e$) of the graph?
Of course it is possible that I'm completely wrong here, in which case, the question becomes: how is the flow decided for each edge (knowing at least that $0\le f_e \le c_e$ for all edges), when we are interested in estimating the maximum flow through the graph?

I think all your questions are answered by examining the actual algorithm to compute the max flow.

With regards to your Q1: in the max flow problem your input is a graph and capacities on edges, your output is the max flow. Thus, max flow is a function of the graph and capacities.

The basic algorithm for computing max flow is as follows. Your capacities are $c: E \rightarrow \mathbb{R}$. We shall incrementally compute the flow $f: E \rightarrow \mathbb{R}$. Let $f^i$ be the flow in iteration $i$. To begin with set $f^0 = 0$. In iteration $i$ construct the residual capacities $c^i(e) = c(e) - f^i(e)$ - this is how much capacity is left on edge $e$ given that we are already sending $f^i(e)$ flow through it. Find an augmenting path from $s$ to $t$, i.e., any path $p$ from $s$ to $t$ such that all edges on that path have positive residual capacity. How much flow can you push on this path? Clearly it's the minimum capacity along an edge of that path $f_{add} = \min_{e \in p} c^i(e)$. Update your flow by pushing $f_{add}$ flow along path $p$. This process naturally stops when your residual graph does not have an augmenting path from $s$ to $t$. It's a fact that at that point the flow you constructed is, indeed, the maximum flow. This fact requires a proof. This is a meta-algorithm (called Ford-Fulkerson), because I have not specified how to choose augmenting paths. Certain choices are better than others. Using BFS (in which case, this max flow algorithm has a name of Edmonds-Karp) to choose the augmenting path results in a polynomial time algorithm, but it again requires proof.