P is in big-endian format.
  P0 —0111011011010011001011010010011001011001010010001011011010000001,

The first bit, 0, means 2*0 + 1 = 1 is not a prime.
The second bit, 1, means 2*1 + 1 = 3 is a prime.
The third bit, 1, means 2*2 + 1 = 5 is a prime.
The fourth bit, 1, means 2*3 + 1 = 7 is a prime.
The fifth bit, 0, means 2*4 + 1 = 9 is not a prime.
The sixth bit, 1, means 2*5 + 1 = 11 is a prime.
The seventh bit, 1, means 2*6 + 1 = 13 is a prime.
The eighth bit, 0, means 2*7 + 1 = 15 is not a prime.
The ninth bit, 1, means 2*8 + 1 = 17 is a prime.
And so on.

  P1 —0100110000110010010100100110000110110000010000010110100110000100,

The first bit, 0, means 2*64 + 1 = 129 is not a prime.
The second bit, 1, means 2*65 + 1 = 131 is a prime.
The third bit, 0, means 2*66 + 1 = 133 is not a prime.
The fourth bit, 0, means 2*67 + 1 = 135 is not a prime.
The fifth bit, 1, means 2*68 + 1 = 137 is a prime.
The sixth bit, 1, means 2*69 + 1 = 139 is a prime.
The seventh bit, 0, means 2*70 + 1 = 141 is not a prime.
The eighth bit, 0, means 2*71 + 1 = 143 is not a prime.
The ninth bit, 0, means 2*72 + 1 = 145 is not a prime.
And so on.

  P2 -1001001100101100001000000101101000000100100001101001000100100101,

The first bit, 1, means 2*128 + 1 = 257 is a prime.
And so on.

  P3 -0010001010001000011000011001010010001011010000010001010001010010,

The first bit, 0, means 2*192 + 1 = 385 is not a prime.
And so on.

And so on.

  P7 -0000010100010000100010100100100000010100100100010010000010100110.

The first bit, 0, means 2*448 + 1 = 897 is not a prime.
And so on.
The last bit, 0, means 2*511+1 = 1023 is not a prime.

  Could somebody please help me understand what is going on here (in plain English)? I think that (k&63) has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

If you have read the above explanation for many bits in P0, P1, ..., P7, the answer to your questions should be obvious now. For a number $2k+1$, $\lfloor k/64\rfloor$, the quotient of $k$ divided by 64, is which $P$ should be used. $k \mathbin{\&} 63$, the remainder of $k$ divided by 64 is how many bits you should move to the right to find its primeness-indicator bit.


CTL - model checking for formula $A [a \cup b]$ I'm trying to verify if the following model satisfy $A [a \cup b]$:

The algorithm I'm using is taken from "Concepts, Algorithms, and Tools for Model Checking", Joost-Pieter Katoen. In particular I applied the SatAU part (previous calculation of the states in which a and b are valid):

Intuitively the formula is verified in state $\{s_1, s_2, s_3, s_4\}$ (so the model does not satisfy the property because the set doesn't contain the other initial state $s_0$).
But if I apply the algorithm above the only state that I get are $\{s_2, s_3, s_4\}$, because the condition to generate the new $Q$ set (row 7) says to take a state s only if it has a connection with EACH element of the old $Q$ set.
Is it correct my interpretation of the algorithm? How can I get also $s_1$ from the algorithm?

Your answer $Sat(A(a \cup b)) = \{ s_1, s_2, s_3, s_4 \}$ is correct. And your conclusion that the model does not satisfy the property is also correct because the initial state $s_0 \notin Sat(A(a \cup b))$.

In my opinion, there is a typo in Line 7:
$$Q := Q \cup \left( \{ s \mid \forall s' \in Q. (s,s') \in R \} \cap Sat(\phi) \right).$$

According to the fixed point interpretation,
$Sat(A(\phi \cup \psi))$ is the smallest set $T \subseteq S$ satisfying
$$Sat(\psi) \cup \{ s \in Sat(\phi) | Post(s) \subseteq T \} \subseteq T.$$
Therefore, the iteration step for Line 7 should be:
$$Q := Q \cup \left( \{ s \mid \forall (s,s') \in R. s' \in Q \} \cap Sat(\phi) \right),$$ or concisely,
$$Q := Q \cup \{ s \in Sat(\phi) \mid \forall (s,s') \in R. s' \in Q \}.$$

By the way, this lecture note by Joost-Pieter Katoen is quite out-of-date (back to 1999). In 2007,  along with Christel Baier, he has published a wonderful book on model checking "Principles of Model Checking (The MIT Press)". You should read it now (online version avaiable).


return a key of a node with maximum value within a range of keys in B+ tree I've been asked a question about B+ Tree.

The question is: Suppose we have object of the following type:

class Obj {
private:
    int value;
    int key;
public:
    Obj(int uniq_key , int value)
}

and I am creating a Generic B+ tree which will sort objects in it leafs nodes by keys and not by values. (The keys are unique values aren't)
Now I want to return the key of a node containes Maximum value within a range of keys.
For Example:

If I have the following objects inserted in my B+ tree:

Obj a(1,10) , Obj(2,5) , Obj(3,0)

Then by calling this method I will get a return value : 1

I thought of having an extra rank tree with the same data stored in it and a pointer from a leaf node in the B+ tree to it's equivalent node in the rank tree but I think that there is a solution involves adding extra data in the nodes in the B+ tree which can solve this issue.

p.s.   I don't know if this post is duplicated - I couldn't find anything else answering this kind of question.

Thank you,
Michael

Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants).  You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't need to look at its grandchildren etc.).

Now any range can be expressed as the union of $O(\log n)$ subtrees.  In other words, you can find $O(\log n)$ nodes such that their descendants cover the range exactly.  So, the max value of any node within that range can be obtained by looking at the values in those nodes, and taking the max of them.  In this way each query can be answered in $O(\log n)$ time.


Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n) I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author claimed that this can be done in $O(n)$.

How should I understand this time complexity? Just because we traverse all nodes in $O(n)$? But in the iteration for some node $v$, one also needs to traverse all its incident edges. Does that mean the time complexity should be $O(m+n)$ or $O(m)$? Is it related to the data structure which one uses to represent the DAG?

It certainly depends on the data structure used to represent the DAG.

We will use a data structure that I am going to call the characteristic-hash-vector (CHV). Given a graph $G$ of size $n$, and a subgraph $S \subseteq G$, the characteristic vector $X_S$ is the vector of size $n$ that has a 1 for each node in $S$ and a 0 for all other elements. The CHV is a way of representing the characteristic vector using a hashmap. Given a subset $S$, each node $v$ in $G$ is mapped to $X_S(v)$.

Let's try representing the DAG as a set of nodes, and with each node $x$, maintain a CHV for incoming nodes $y$ (there exists a directed edge from $y$ to $x$) and a CHV for outgoing nodes $w$ (there exists a directed edge from $x$ to $w$). Then, it is easy to find a node with no incoming edges. Start with any arbitrary node, and then pick any arbitrary node from its incoming CHV, and so on, until we reach a node with an empty incoming CHV. By the proof the earlier in the section, we know that this search will terminate in $O(n)$ time.

Then, we go to each node in this final node's outgoing CHV, and remove the final node from its incoming CHV (this is where we use the constant-time properties of hashmaps/CHVs). This process also takes $O(n)$ time.

Thus, we have a runtime of $O(n)$ for each iteration of the loop in the algorithm to compute a topological order for a DAG.


How MO'S algorithm with update query works? MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing difficulty to understand MO'S algorithm with updates (https://www.youtube.com/watch?v=gUpfwVRXhNY)

Since articles related to MO'S algorithm with updates is rare can someone who knows this algorithm can explain it.

A short (or long?) recall:
Mo's algorithm is used for problems, when you want to answer a lot of range queries over an array, in which it is not possible to generate an efficient data structure like a Segment tree, because combining multiple nodes can be very inefficient. The famous problem is to count the number of distinct elements in ranges $(l, r)$. Precomputing some ranges, like in a Segment tree, would not help, because combining two ranges is not efficient, and in general is an $\Omega(n)$ operation.

To answer such queries efficient, we need two ideas:

Mo's algorithm uses the fact that we know all queries at the start, so we can answer them offline (in any order we like).
We order the range queries by the tuple $\left(\left\lfloor\frac{l}{B}\right\rfloor, r\right)$ with $B = \sqrt{n}$ and compute the answers for them in this order.
This means we split the array into $\sqrt{n}$ blocks of size $\sqrt{n}$. First answer all range queries that start in the first block (sorted by their range ends), then all range queries that start in the second block, an so further.
The second idea is to use a data structure that represents a specific range $[L, R]$, can give us the answer to its range quickly, and it's possible to add/remove single numbers quickly to modify it's range.
And we will maintain this data structure the entire time, starting with the empty range $[0, 0)$.

E.g. in the example we just use a set together with the information how often each number appears in the current range. Adding a number will increases the count of the number (or adds the number with count 1 if it doesn't exit), and removing a number just decreases the count (or removes the number from the set).
Assuming that the data structure currently maintains the range $[L, R]$, and the next query covers the range $[l, r]$. Then we just need to individually add the parts of the array, that were not covered by the old range but are covered in the new range, to the data structure: $[l, r] / [L, R]$, and remove the parts that were covered before and are now not covered $[L, R] / [l, r]$.
It can be easily be proven, that we only add/remove $\sqrt{n}$ numbers on average per query (if we assume that we have $Q \approx n$ queries).

To handle updates we have to handle a new dimension: time. Because an identically query $(l, r)$ asked multiple times, can give different answers depending on the updates in the time between them.
So we represent each query as a tuple $(l, r, t)$. The first query gets $t = 1$, the second $t = 2$, and so on.

Again as before, we just order the queries, this time by $\left(\left\lfloor\frac{l}{B}\right\rfloor, \left\lfloor\frac{r}{B}\right\rfloor, t\right)$ with $B = n^{\frac{2}{3}}$.
So here we have blocks of size $B$ for $l$ and $r$, and answer them accordingly. First all with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 0$ (sorted by $t$), then all queries with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 1$ (sorted by $t$), and so on.

But now, if the data structure currently represents the range $[L, R]$ at timepoint $T$, and we want to answer the query $[l, r]$ at timepoint $t$, then we additionally to adding the parts $[l, r] / [L, R]$ and removing the parts $[L, R] / [l, r]$, perform the updates in the time range $(T, t]$ if $T < t$, or undo the updates in reverse if $T > t$.
It can be proven, that we add/remove/update $n^{\frac{2}{3}}$ numbers on average during each query.


Predicate Logic - negating the conclusion to prove logical consequence? In Predicate Logic, if you want to prove the logical consequence using the method of resolution, do you ALWAYS start off by negating the conclusion?

The method works in the same way as proofs by contradiction. Suppose you have a set of assumptions $A$ and you want to prove that formula $\phi$ is a logical consequence of the formulas in $A$. One of the ways to do this is as follows.

Put the negation of $\phi$ in your assumptions. So, now $A' = A\cup\{\neg\phi\}$
Show that $A'$ is inconsistent. Here, this means to consecutively apply the resolution step on (appropriately chosen) formulas of $A'$, until a contradiction $(T\to F)$ is reached.

Classical logic tells you that, if (a) the initial set of assumptions $A$ is consistent and (b) $A\cup\{\neg\phi\}$ is inconsistent, then $A\cup\{\phi\}$ is consistent and you can say that $\phi$ is a logical consequence of $A$. So, if steps (1) and (2) succeed, then $\phi$ is a logical consequence of $A$.

If you don't negate the goal when you put it in the set of assumptions and  if you manage to show that $A\cup\{\phi\}$ is inconsistent, then $A\cup\{\neg\phi\}$ is consistent and therefore $\neg\phi$ is a logical consequence of $A$.


Minimum depth of addition and multiplication circuit using XOR and AND gates What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates?
I read somewhere that we can achieve constant depth for addition if we have an OR gate. Can I achieve that using XOR gates?

You can simulate an OR gate using a constant number of AND and XOR gates:

$$x \lor y = ((x \oplus 1) \land (y \oplus 1)) \oplus 1.$$

Consequently, anything you can do in depth $d$ using AND and OR gates, can be done in depth $\le 3d$ using AND and XOR gates.


How can computer memory remember after the computer runs out of battery? According to my fragile knowledge of computer hardware the way computers store information is by electric circuits. If there is current the bit is 1 if there isnt its 0. My question is after a computer runs out of battery the memory stil holds all of the information, how? Wont it be the case that all the bits are 0?

There’s permanent storage that doesn’t need any power and lasts forever.
Your computer likely has a tiny battery for important things like clock time which should last for a very long time.
Your computer probably has code that dumps all memory contents to permanent storage just before the battery runs out and reads it back when there is enough battery life.


Optimization problem over bidirectional connected graph A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators, trays and slots are identified by unique IDs and slot also have access to the ID of their own article. In the same tray there can be multiple slots with the same article.
Example:
tray A contains

slot SA1 with 5 items of article X;
slot SA2 with 10 items of article Y;
slot SA3 with 3 items of article Z

tray B contains

slot SB1 with 12 items of article Y

tray C contains

slot SC1 with 4 items of article X;
slot SC2 with 15 items of article Z;
slot SC3 with 8 items of article W

trays A, B and C belong to the same elevator.
——————————————————
I have to design an algorithm which, given an order list (we can model it as a dictionary with articles' IDs as key and quantity needed as values), returns the minimum list of trays needed to satisfy the order. That is, find the smallest (in terms of cardinality) set of tray whom slots contain a sufficient quantity of each articles listed in the order.
This is quite different from a standard warehouse optimization problem because we are not considering the physical distances between each tray, since the elevators are automatic and they give us the tray, while in the classical problem is the human who moves toward the tray to pick the item from it.
After reading through articles about warehouse optimization, I've decided to take an heuristic approach.
I've modeled a sort of euclidean space, with an axes for each article contained in the order. Then we can consider a tray as a point on that space, with coordinates for each axes equal to the quantity that tray has of the article corresponding to that axes. In the same way we can imagine our order as a point.
Then I've create a heuristic function, $f(order\ o, tray\ t)$, which returns the "euclidean distance" from point-tray $t$ to the point-order $o$. The idea is that the more a tray is "near" the order, the more article we can pick out of it.
So, to satisfy the order, I simply compute $f(order\ o, tray\ t)$ for each tray in every elevator. Then I order it by descending value and finally I greedily take a tray with the minimum distance from the order. This will be repeated until we collect enough articles to satisfy the order.
I've tried to build a graph in which each node is a tray and is connected to each of the others by a directed edge. The weights of the edge from node $i$ to node $j$ will be equal to the heuristic function computed on tray $j$.
→ $w[i, j] = f(order, j)$
This results in a fully-connected, bidirectional graph (each node linked with each other node by both an incoming and an outgoing edge).
I want to apply some algorithm of shortest path (or any other useful algorithm) taken from graph theory on this graph but I couldn't find anything really helpful.
Is there any algorithm I can apply on such a graph? Or maybe the graph is not the right structure to represent my problem. I'm open to new solutions.

This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you don't select).  It presumably remains NP-hard, but can be solved by a number of methods.  Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to it.


Find maximum element in sorted arrays in logarithmic time Been stuck on this for a while, would really appreciate some help:

  Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, [35,42,5,15,27,29] is a sorted array that has been circularly shifted k = 2 positions, while  [27,29,35,42,5,15] has been shifted k = 4 positions. Give an algorithm for finding the maximum element in A that runs in O(log n) time.

The elements in A are distinct.

I understand that to achieve O(log n) time I'll probably have to search through the list by starting at the middle, and then going left or right, then splitting the list in half over and over, but I'm not sure how to attack it beyond that.

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.

Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.

However, if you assume the elements are distinct, then you can indeed give an $O(\log n)$ time algorithm.

Assume the array was sorted ascending. Once it is cyclic shifted, we will have that, in the rotated array (say $a[1,2, \dots n]$), that $a[1] \gt a[n]$. (It might help to draw a figure here, plotting $i$ on x-axis and $a[i]$ on the y-axis).

Now if you pick a $j$, you compare $a[j]$ with $a[1]$ and move right or left, depending on whether it is greater or lesser, like binary search.


Algorithm to generate combinations of n elements from n sets of m elements Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:

[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F]

What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.

If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group).

This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d_i < k-1$ the next number is obtained by increasing $d_i$ by $1$. Otherwise set $d_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.

This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d_1$ every time you increment the number, $d_2$ changes only every $k$ increments, etc. In general $d_i$ changes every $k^{i-1}$ increments.

Since the total number of increments is $k^n$, the total number of operations is:
$$
O\left(\sum_{i=1}^n \frac{k^n}{k^{i-1}} \right) =
O\left(\sum_{i=1}^n k^{n-i+1} \right) =
O\left(k \cdot \sum_{i=0}^{n-1} k^i \right) =
O\left(k \cdot  \frac{k^n - 1}{k-1} \right) =
O(k^n).
$$

This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).

A pseudocode:

A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;

while true:
    //A contains a n digit number in base k. Do something with it

    i = 1;
    while i<=n and A[i]==k-1:
        A[i]=0;
        i=i+1;

    if i>n:
        return;  //We have already seen all n-digits numbers in base k
    else:
       A[i]=A[i]+1;


Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory" In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality.

In Fig. 1.3, the author says a black colored leaf is the minimal with respect to set inclusion and a hitting set consists of the vertices labeling the edges on the path from the root to the leaf. However, both grey and black colored hitting set consists of 3 vertices. Why grey colored leaf is not minimal in this case?

Related question: Given a set of sets, find the smallest set(s) containing at least one element from each set

It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of minimum cardinality, not a minimal set.

A set $S$ is called minimal with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.

On the other hand, a set $S$ is said to have minimum size or cardinality with respect to some property if there exists no set $T$ of strictly smaller size (i.e. $|T|< |S|$) that also satisfies this property.

A minimum size set must be minimal (why?), but a minimal set need not be of minimum size (why?).

In the example in the book, the set $\{b,c,d\}$ is not a minimal hitting set, because its strict subset $\{c,d\}$ is also a hitting set. The subset $\{b,d,f\}$ is a minimal hitting set, because it has no strict subset that is a hitting set. It is not a minimum hitting set, because there is a hitting set of size $2$ ($\{c,d\}$).


Efficient algorithm to find all distances to a specific node in a tree I wish to calculate the number of nodes within a certain distance of a particular node in a tree such as the one below:

Let's assume I'm looking for all the distances to node 2. What would be the most efficient (in terms of time complexity) method of computing the distances? Can it be done in linear time?

For this instance the output for the above tree would be:

within one edge length distance: 4
within two edge length distance: 2
over two edge lengths away: 0

What I've done so far:

A simple brute force-ish solution would be to traverse the tree all the way to node 2 starting from all other nodes and counting the edges. I can make it a bit more efficient by storing the distances for all the nodes that are visited during each traverse and using the value if the node is visited again in a traverse that has originated from another node (for example traverses originating from nodes 1 and 3 in this graph will both result in visiting node 5). Is this the most efficient it can get?

Assuming your edges are not directed (which seems to be the case in case you are dealing with trees), you can calculate the distance by starting a breadth-first search from node 2. Then, you get the number of steps necessary to go from node 2 to each node $n$, which, as the graph is undirected, is the same as the number of steps necessary to go from node $n$ to 2.

If your had a directed graph, you can basically do the same, but you have to traverse edges in the opposite direction. E.g. if you are at node $n_1$, and have the edges $n_1 \to n_2$ and $n_3 \to n_1$, you would then process $n_3$ as a successor, but not $n_2$.


Number of Matchings in a Bipartite Given two sets A and B of sizes |A| = n and |B| = m, where m >= n.
There are edges from set A to set B.
I need to find the number of matchings where all of vertices in set A have been matched with one vertex in set B.
Is it possible to caclulate this quantity ?

(I have very little knowledge of Graph Thory and Bipartite Matching or how it is computed)

A matching in which all the vertices in $A$ are matched is known as a perfect matching. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is zero-one. The permanent-vs.-determinant question is analogous to the more famous P-vs.-NP question.

When $m > n$, you can add $m-n$ dummy vertices to $A$ and connect them to all vertices in $B$. The number of perfect matchings in the new graph is exactly $(m-n)!$ times the number of perfect matchings in the old graph.


Prolog: Deletion of all appearances of an element in a list I am trying to create a predicate in Prolog which allows me to delete all occurrences of X in a list L. I have the following code:
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

And now, upon querying this following line, I receive no result, implying that no list R could be constructed so that it followed my requirements.
?:- my_delete(baz, [foo, bar, baz], X)

The construction works fine when the list I want to delete from didn't contain an occurrence of X in the first place, but not if it did.
Why is my set of predicates insufficient? What needs to be changed?

There are some rules of thumb I follow when writing prolog. Two of them are:

Use dif instead of \=. From the reference manual: "To make your programs work correctly also in situations where the arguments are not yet sufficiently instantiated, use dif/2 instead."

Avoid unnecessary variables and always get rid of the "Singleton variables: [X]" error. It makes the code much more readable.

When I rewrite your code accordingly, your
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

becomes
my_delete(A, [], []).
my_delete(X, [Y|K], [Y|M]):- my_delete(X, K, M), dif(X, Y).
my_delete(X, [X|K], R) :- my_delete(X, K, R).

which is not only concise and more readable, but it already seems to work.
As for your particular case, I think it has to do with the quote in the first rule of thumb above. Your X and Y are not sufficiently instantiated, so it is no surprise for me, that your program does not work correctly.
But the "dif vs. \=" issue is probably not a problem in this case. I replaced dif(X, Y) with X \= Y in the code I suggested above, and it still works. (It may be causing a problem in your code though. I don't know if this is the case.)
Just using dif instead of \= is not a solution either. After replacing the \=s with dif in your code, it still does not work correctly. If the element to be removed is at the last position, it does not work. my_delete(baz, [baz], X) fails, for example.
So what is the problem? It seems to me that you've made two mistakes in your last line. You've put an unnecessary (Y \= X). Line 3 was supposed to be the case in which L starts with X. So the inequality check there should probably be an equality check. And secondly, you probably shouldn't have splitted R into [Y|M].
You can try the code here: https://swish.swi-prolog.org/p/myClMmML.pl
Swish has a great debugger as well. Check out its help.


Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma:

$L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$

Now I realize that the condition $m \equiv 0 \space mod \space n$, is essentially saying that $m$ is some multiple of $n$. Is it possible that could you go about proving that $L$ is not regular in the way that you can prove that $L = \{0^n 1^n\}$ is not regular since $m$ is a multiple of $n$, since $m = kn$ (where $k$ is some integer)?

Updated:

-- My attempt at the proof:

If the language $L$ is regular, then by the pumping lemma $\exists \space p \space | \space \forall s \in L \cap \Sigma ^{\geq p}  $.

Next by the pumping lemma $\exists x, y, z : s = xyz$, where $s$ is a string such that:

(1) $|y|\geq1$

(2) $|xy|\leq p$

(3) $\forall i\geq0, xy^iz \in L$

Now suppose we let $m = kp$, where $k$ is some integer, let the string $s = 0^p 1^{kp}, s\in L$ and $|s|\geq p$. By the pumping lemma the decomposition of $s$ is defined by $s = xyz$. Now we show that $\forall x, y, z$ that (1)-(3) do not hold.

If (1) and (2) hold, then $s=0^p1^{kp} = xyz$, with $|xy|\leq p$ and $|y|\geq 1$.

So $x = 0^u, y=0^v, z=0^w1^{kp}$

$u+v \leq p$, $v \geq 1 $, $w \geq 0$

$u+v+w = kp$

But (3) fails for $i=2$ since $xy^2z = 0^u0^v0^v0^w1^{kp} = 0^{u+2v+w}1^{kp} \not\in L$ since $u+2v+w \neq kp $

Hence $L$ is not a regular language.

Is this the correct way to go about this proof?

Here is a nicer proof, (implicitly) using the Myhill-Nerode criterion. Let $p_1,p_2,p_3,\ldots$ be the list of all primes, and consider the words $x_i = 0^{p_i}$, $y_i = 1^{p_i}$. Then $x_i y_i \in L$ while $x_i y_j \notin L$ for $i \neq j$. So given a DFA for $L$, if $\sigma_i$ is the state that the DFA is at after reading $x_i$, we must have $\sigma_i \neq \sigma_j$ for $i \neq j$ (why?), so the DFA must have infinitely many states.


Theta Runtime of Nested for Loops I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much for(int i = 0; i < U -1; i++)), and the inner loop runs exactly n times in total for the duration of the entire execution. It can run n times once and never run again, or it can run once in each iteration of the outer loop n times, or anything in between.

It's obvious that this runs in O(nU) time. However, I think I can also state it runs in theta(U + n) time because the inner loop runs independently of the outer one. But still, they are nested, and not multiplying the runtimes of nested loops feels awkward.

Intuitively I know I am right, but I don't really know how to show it. I'm not looking for a formal proof, but any kind of insight is welcome.

Yes, the running time is $O(U+n)$, assuming that each iteration of the inner loop takes $O(1)$ time.  The way to prove it: try to write down an expression for the running time, as a function of $U$ and $n$.  What did you get?  Now, see you can show that this expression is at most $c \cdot (U+n)$, for some constant $c$ that you get to specify.


iterating over subsets by switching one element at a time How do I iterate over all the $k$-element subsets of $\{1,2,\dots, n\}$ by switching one element at a time?

123
134
234
124
145
245
345
135
235
125

This comes from Ch2 of  Combinatorial Algorithms by Nienhuis and Wilf.

Equivalently I am asking for a Hamiltonian circuit on the Johnson graph of $k$ element subsets of a set of $n$ elements connected if their intersection has $k-1$ elements.

I am trying to understand how the equation $$A(n,k) = A(n-1,k), \overline{ A(n-1,k-1)}\otimes \{n\}$$ from Nienhuis-Wilf leads to a type of "gray code" for subsets.  In fact, it is the gray code when you restruct to $k$-element sets.

Here, $A(n,k)$ is an ordering, looping over the $k$-element subsets of $\{1,2,\dots, n\}$.   The notation $\overline{ A(n-1,k-1)}\otimes \{n\}$ means we should list the $k-1$-element substs of $\{1,2,\dots, n-1\}$ and append the element $n$ to each element of that list.

This equation can also be thought of a set theoretic version of the binomial coefficient identity

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Using this formation I came up a means of listing all the subsets in order.

Here gc(n,k) is returning an array of $k$-element arrays, enumerating the $k$-element subsets of $\{1,2,\dots, n\}$.

def gc(n,k):
    if(k==1):
        return [[i+1] for i in range(n)]
    elif(n == 0):
        return []
    else:
        L = [ x+ [n] for x in gc(n-1,k-1)]
        return gc(n-1,k)+ L[::-1]

How do I find the predecessor or successor of a given subset without generating all the subsets?  I wrote some python code for this, which is different from what is in the textbook.  It still doesn't return the correct answer.

def S(n,k,a):
    if k == 1:
        return [(a[0] + 1)%n]
    elif(a[-1] == n-1):
        return P(n-1,k-1, a[:-1]) + [n-1]
    else:
        return S(n-1,k,a)

def P(n,k,a):
    if k == 1:
        return [(a[0] - 1)%n]
    elif(a[-1] == n-1):
        return S(n-1,k-1, a[:-1]) + [n-1]
    else:
        return P(n-1,k,a)

This looks pretty close to the recursion in Nienhuis-Wilf but I would like to understand where I am going wrong in my implementation.

Here is how to convert a number from $\binom{n}{k}$ to a subset of $\binom{[n]}{k}$, and vice versa. This is known as inductive counting. I'll use your formula
$$ \binom{[n]}{k} = \binom{[n-1]}{k} + \binom{[n-1]}{k-1} \times \{n\}. $$

Given a code $x \in [0,\binom{n}{k})$, the idea is that the first $\binom{n-1}{k}$ codes will be used to code the $\binom{[n-1]}{k}$ part, and the rest will be used to code a subset in $\binom{[n-1]}{k-1}$ which will be completed to the required subset by adding the element $n$. Here is the relevant quasi-python code:

decode(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode(n-1, k, code)
  elif:
    return decode(n-1, k-1, code - binom(n-1, k)) + [n-1]

Encoding is the reverse process, and mirrors it exactly:

  encode(n, k, S):
    if k == 0:
      return 0
    elif n-1 not in S:
      return encode(n-1, k, S)
    else:
      return encode(n-1, k-1, S[:-1]) + binom(n-1, k)

Using these subroutines, you can compute the successor and predecessor of a given subset. You could also do it directly, for example by "unrolling" the resulting code, but this is a programming question which you should be able to solve for yourself in a couple hours.

The preceding doesn't produce a Gray code at all. You can obtain a Gray code by reversing the second half in your fundamental formula (this is the meaning of the overline). The corresponding decoding function is

decode2(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode2(n-1, k, code)
  elif:
    return decode2(n-1, k-1, binom(n, k) - 1 - code) + [n-1]

I'll leave the encoding function as an exercise. The proof that this forms a Gray code is by induction. You prove a more general claim, stating what are the first and last sets in the ordering for any given $n,k$, and given that you prove by induction that the result is a Gray code. Details left to you.


Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same? I understand the difference in the parsing tables of the above 4 parsers.
I understand that CLR>LALR>SLR>LR(0) in terms of power.

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?. I think goto should vary as reduce moves vary?
Also, if a grammar is accepted by CLR(1) parser, for which parser it would have highest and lowest no. of reduce moves or would it be the same?
Please explain

Every reduce action corresponds to a production; the action "undoes" the production by replacing its right-hand side with the non-terminal which produced it.

That can only happen in one way; the parsing automaton does not invent or suppress non-terminals. So it doesn't matter which algorithm was used to create the automaton; the actions will be the same.

The automata may have different numbers of states, so the state sequence may differ. But not the actions performed on state transitions.

To put it another way:

If a grammar has an *LR automaton, the grammar is unambiguous, which by definition means that there is only one rightmost derivation. A rightmost derivation, written backwards from sentence to start symbol, can be represented as a series of shifts and reduces. Any LR grammar which recognises a sentence in this grammar must produce the same rightmost derivation, so it must perform the sane sequence of shifts and reduces.


Operator precedence in propositional logic there is some kind of priorities for the elements in propositional logic ?

for example : p ∧¬q → r , given this ,we there may be two options

(p ∧¬q) → r  OR p ∧ (¬q → r) , which one is the correct ?

If you look at formal definitions of the syntax of propositional logic, you will find that

$\qquad p \land \lnot q \to r$

is not a proper sentence; parentheses are needed to avoid exactly the ambiguity you mention.

Operator precedences can be used for implicit parenthesisation. You seem to be asking if there are agreed-upon operator precedences in logic.

I don't think formal logics contains this concept; formal grammars just do not lend themselves to model precedences (or any ambiguity) very well. In practice (by which I mean both blackboard writing and implemented logic parsers), we do use precedences; usual conventions include

$\lnot$,
$\land$,
$\lor$,
$\implies$,
$\iff$

in decreasing order of precedence. Using these, your example is equivalent to

$\qquad (p \land (\lnot q)) \to r$.

David's warning is apt, though: if you want to be clear, don't rely on implicit precedences. Typesetting can help -- you can e.g. group terms with spacings -- but in case of doubt, just put the parentheses. In a larger body of work, you can also state your convention once and safe symbols afterwards, provided you stick to your own rules.


DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$ I need some help with the following task:

I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$.

How can I recognize that the new substring $y$ begins? For example: $w=zy$, where
$z = 1111$ and $y = 1001$.

This is what I have so far:

In order to verify whether the string is of the form $1^ky$ with $y\in \{0,1\}^*$ and $|y|_1\le k$ you want to determine whether a symbol $1$ in the prefix belongs to the $1^k$ part, or starts $y$.

Now imagine $1^k \cdot 1y$ is of the correct form, i.e., $|1y|_1 \le k$, then certainly $1^{k+1}\cdot y$ is also correct, as $|y|_1< |1y|_1 \le k < (k+1)$.

So, keep reading $1$'s while possible.


Proof emptiness for PDA is $\mathcal{O}(n^3)$ It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is easier.

Do you maybe have a book or paper I should investigate?

EDIT: This looks interesting but a formal proof from a book or paper would be great!

Start with an arbitrary PDA. Convert it to a PDA which pushes at most two symbols to the stack at each step — this only incurs a linear blow-up. Convert the PDA to a CFG using the standard construction, described in this answer. Since the PDA pushed at most two symbols at each step, the CFG has size $O(n^3)$ (for each transition $p \stackrel {a,\gamma} \to q$, where $a$ is a letter and $\gamma$ is a word in the stack alphabet, we have to enumerate over $|\gamma| \leq 2$ states, hence the number of transitions is at most the original number of transitions times $|Q|^2$). Convert the CFG to Chomsky normal form with linear blow-up. Then use the linear time algorithm described in this answer to check whether the CFG generates an empty language or not.

Summarizing:

Convert the PDA to one in which at most two symbols are pushed to the stack at each move (linear blow-up).
Convert the new PDA to a CFG (cubic blow-up).
Convert the CFG to Chomsky normal form (linear blow-up).
Check emptiness of the CFG in Chomsky normal form (linear time).

You can probably skip the step in  which you convert the CFG to Chomsky normal form by modifying slightly the algorithm described in the second answer.


Existence of suitable pseudo-random number generators to derandomize BPP to P I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other.

My understanding is that if there is a suitably strong pseduo-random number generator that only uses $O(\log n)$ seed bits, then we can derandomize $BPP$ to $P$ by simulating $BPP$ machines in polynomial time using the random number generator and looping over every possible seed.  If I understand correctly, the "suitably strong" details were made explicit with Impagliazzo-Wigderson's conditional result that unless $E$ has sub-exponential circuits, $P=BPP$ by way of simulating $BPP$ machines with a pseudo-random number generator.

However, it is known that there is an oracle to which $P^A \ne BPP^A$.

While I understand that this does not imply $P \ne BPP$, cannot we at least say that this means that $P$ cannot simulate $BPP$ machines? Because if $P$ could just simulate $BPP$ machines directly, then it could also access the oracle $A$ in exactly the same way as $BPP$, and it would not be possible to get an oracle separation.

So putting this all together, why can't we say that Impagliazzo-Wigderson's result actually proves $E$ has sub-exponential circuits?

Or alternatively worded, doesn't the oracle separation prove no "suitably strong" pseduo-random number generator exists that would allow derandomizing $BPP$ by just simulating it in polynomial time?

It's possible I'm missing something subtle, but I have a feeling I'm actually just way off the mark. So please help me understand what is going on here.

$P^A\neq BPP^A$ implies the inexistence of strong enough PRG's in the relativized world, not necessarily in the usual (non black box) model.

Remember that when defining a PRG, you require it to fool some adversary with bounded resources, e.g. polynomial size circuits, or probabilistic poly time Turing machines. The NW generator fools circuits of bounded size $S$ (which depends on the hardness of the problem you started your construction with), but this does not mean it can fool circuits (or Turing machines) with access to the oracle $A$.

As an example, for any PRG $G$ which fools poly time probabilistic Turing machines, let $\mathcal{O}_G$ be the oracle which tells you whether some string $s$ is a possible outcome of $G$. $G$ can no longer fool poly size Turing machines with oracle $\mathcal{O}_G$.


Why can't we say that a Neural Network is a NP problem solver? From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The example he draws on is just seeking the next yes till you find some final output. For those reasons, I had assumed that even SGD is NP complex, and by extension Neural Networks. And my logic was that, through readings it seems like a Back Prop algorithm is always looking for a way to reach towards the global minima by taking the most negative step.
However, from my reading, it seems like Neural Networks have a computational Complexity of P. And as a result of the fact that most people believe $P\neq NP$ then a NN can only take a guess/approximation at a solution.
From what I follow, the belief is that since a Neural Network can't promise an ideal result, it isn't an NP solver. But that confuses me since from what I have seen, a Neural Network just never gives that ideal solution. Does that mean all these problems are just more complex than P and so they can only make a different guess every time? While an NP solution is supposed to consistently give back the correct answer.
From linear Algebra, we know that a solution needs to be a repeatable, deterministic mapping from $X\to Y$ Or else it is a mere approximation function and $X$ is not in the domain of the transformation.
To me that means either my understanding of what a Neural Network does in its backpropagation is wrong. Or that my understanding of NP complexity is wrong.

SGD is an algorithm, not a problem.  It is not NP-complete or NP-hard.  SGD is one approach to an optimization problem.  Some optimization problems are NP-hard; some are not.
All of your deductions start from that one incorrect assumption, so they don't actually follow.
"Neural Networks" don't have a computational complexity; they aren't a problem.


Palindromes and linear grammars Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?

Consider Post correspondence problem (PCP). If $\alpha_1 \dots \alpha_n$ and $\beta_1 \dots \beta_n$ are the words of PCP, then $S \to \alpha_iS\beta_i^r$ and $S \to \#$ where $\#$ is a symbol not in any of $\alpha_i, \beta_i$ and $s^r$ is the string $s$ reversed, gives a grammar $G$ such that if $G$ generates a palindrome, then the corresponding instance of PCP has a solution. PCP is RE though.


Is star closure of reverse of language equivalent to reverse of closure of that language is the following true
$ (L^R)^* = (L^*)^R $

I tried the following to prove it true.
let u,v belong to L then $ L^* = \{ u,v, uu, vv, uv, vu ... \} $
and $ (L^*)^R = \{ u^R, v^R, u^Ru^R, v^Rv^R, v^Ru^R, u^Rv^R ... \} $

now $ L^R = \{ u^R, v^R \} $ so
$(L^R)^* = \{ u^R, v^R, u^Ru^R, v^Rv^R, u^Rv^R, v^Ru^R ... \} $

Take any $w\in {(L^*)}^R$. Then $w$ can be writen as $w=(u_1\cdot u_2\cdots u_n)^R$, with $u_i\in L$. We have

$$
w =(u_1\cdot u_2\cdots u_n)^R =u_n^R \cdot u_{n-1}^R \cdots u_1^R,
$$

and therefore $w\in (L^R)^*$.

Assume now that  $w\in {(L^R)}^*$, then by the same argument
$$
w =u_1^R \cdot u_{2}^R \cdots u_n^R= (u_n\cdot u_{n-1}\cdots u_1)^R ,
$$
and hence $w\in {(L^*)}^R$.

As a consequence ${(L^*)}^R={(L^R)}^*$


Algorithm to compute maximum of blocks We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total).

One algorithm is to compute the maximum of every $n/2$ consecutive numbers separately. This leads to an $O(n^2)$ algorithm.

Can we do better? Perhaps using a heap or an appropriate data structure?

Here some ideas:

Put the numbers in an array and repeat it. This allows to view the problem in a different light. Now you just have to compute a bunch of range maximum queries. RMQ is a well studied topic, and there are countless efficient solutions:

Sqrt-Decomposition: $O(N)$ preprocessing, $O(\sqrt{N})$ per query.
Segment Tree: $O(N)$ preprocessing, $O(\log N)$ per query.
Sparse-Tables: $O(N \log N)$ preprocessing, $O(1)$ per query
Farach-Colton and Bender: $O(N)$ preprocessing, $O(1)$ per query
and many more

Most of them are of a more general nature, e.g. they allow modifying the array. And some (like Farach-Colton and Bender) are not very pleasant to implement. This is probably way too much for your application.

So here I want to present a very simple and short data structure, which is still capable to compute the maxima in optimal $O(n)$ time: the Max-Queue.

A Max-Queue is a queue, that functions like a normal queue (you can insert values at one end and remove values at the other), and also can compute the maximal value in $O(1)$ time. CP-algorithms.com describes a few possible implementations of min-queues, which are just the dual data structure. I'll
use method 2 here:

The queue internally keeps track of how many items we have pushed and popped already, and stores the elements as pairs (value, push_index). E.g. pushing the elements [1, 6, 2, 4, 3] leads to the queue: [(1,0), (6,1), (2,2), (4,3), (3,4)]. And one thing more. It will do this in such a way, so that we only store elements in a monotone decreasing way, so that it stores the maximum at the beginning, and so that after popping the maximum the next maximum is still at the beginning. This would give us the queue structure: [(6,1), (4,3), (3,4)]. This allows looking at the maximum in $O(1)$ time (just look at the first element), inserting in amortized $O(1)$ time (you need to delete all elements from the back that are smaller than the new value), and popping in $O(1)$.

A Min-Queue implementation can be found under the link above. Each method consists of only 1-4 lines of code.

With the Max-Queue we can find all desired maxima in $O(n)$ time.
We insert the first $n/2$ numbers in the queue, and print the maximum. The pop a value, insert the next one, and print the maximum. Repeat until you printed $n$ values.


If $f(n)=n^a$ for a given $a>0$, find $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$ If $f(n)=n^a$ for a given $a>0$, I need to find a function $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$.
I am not sure how to find such function, which satisfies both of the conditions.

For given $a>0$ and $f(n)=n^a$ we consider
$$g(n)= \begin{cases}{}
n^{a+1}, & n=2k\\
0, & n=2k-1
\end{cases}$$
for $k\in \mathbb{N}$


Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not This is what do I have to solve:
Byron Book: Exercise 8.3 chapter 8
Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population
mean is indeed 48.2333 and the population standard deviation is indeed 26.5170, then at
least 8/9 of all tasks require less than 127.78 seconds of CPU time.
This is how I did it :
So first I calculated: 127.78-48.23 = 79.5
Then I wrote P(X<127) < (26.5^2)/(79.5^2) = 0.11
I don't understand if I did it right because I did not use this part : at least 8/9 of... and I think it is important.
Can anyone help me with this ? Thank you in advance.

The exercise above is right but is missing something. You need to do 1-0.11 since you need to find the <, not the >. When I wrote 0.11 I have found the > but I need the < so  1-.. .


How do I calculate response time of a multiple core cpu when given certain information? On my homework the question asks:

  A program executes serially in 200 seconds. If it is parallelized, 7
  seconds of overhead are required for synchronization, locking, and
  communication. Compute the execution time, ideal speedup (if there
  were no overhead required), actual speedup, and the percentage of the
  ideal speedup that is obtained for 1, 2, 4, 8, 16, 32, 64, and 128
  processors.

How do I calculate the answer to this? It is not something that has been covered in class yet and the homework is due before the next time the class meets.

My guess is that I divide 200 seconds by the number of cores and then add 7 * # cores to get the total response time. I don't think it is that simple.

Edit:
Amdahl's law says: T(n) = T(1)[B + 1/n(1-B)] where B is the percentage of the algorithm that is not parallelized and n is the number of cores. If I assume that the 7 seconds mentioned is the part of the algorithm that is not parallelized, I can get the percentage by saying:

      7sec * n
B  =  --------
       200sec

Then I plug the value for B into Amdahl's equation. Coencidentally, this gives me  the same answers as I got before when I did my own formula:

 200
 ---  +  [7 * (n - 1)]
  n

After doing a little bit of algebra, I discovered that my formula is a simplified version of Amdahl's formula. Of course all of this assumes I am correct when I read the question as if the 7 seconds are the part of the algorithm that is not parallelized.

Thanks for looking,

Zach

I think you don't need to add (7*number of cores) to the total response time. The overall execution time requires just 7 more seconds, because each piece of code is running in parallel with others. So just divide 200 by the number of cores and add 7 to it. Obviously in the ideal case you don't need to add anything. Also look at the Amdahl's law in the Wikipedia... It also states a law about speedup with parallelism and these problems share the same concept.


When are binary trees better than hashtables in real world applications? I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree.
I do understand the algorithms, and how to implement a binary search tree and such. I do so how smart it is that we can do lookups in O(log n) time.

I am however having a hard time finding an example of when I would use a binary tree, where a hash tables would not do the same/better job.
I have been doing some searching around and found that it is used for 3D graphis, something about what items are to be displayed, i do however have a hard time relating to this.

Can any one give me an example where it would be better to user a binary tree over a hash table?

Hash tables can only tell you if an element is present or not.

Here are somethings you can do with a binary tree that you can't do wiht a hash table.

sorted traversal of the tree
find the next closest element
find all elements less than or greater than a certain value

See this wikipedia article on K-d trees for an example of a real world data structure that makes use of the special properties of binary trees.
http://en.wikipedia.org/wiki/K-d_tree


Why translating a program from one high-level programming language directly into another is difficult? I am looking for a better explanation (research level, papers) to answer:

Why translating a program from one high-level programming language directly into another is difficult?

Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply because I am unaware of such results, but you are very much welcome to correct my ignorance.

I understand that at the core of the argument can say something like one-to-one mapping for such translation simply does not exists.

In general, I am not comfortable with terminology used in my own question.

We know from text books: Low-level language - each command or object of the language has one-to-one mapping to CPU commands (e.g. Assembler). All other languages are High-level.

Is there a way to reformulate the question into FSA formalism like with  regular languges, or some other formalism. But I don't think Church–Turing thesis can help here - it is not about computability or existence of a proof.

PS

My motivation is very simple - I want to discuss/answer how difficult is such a problem for example in translating PHP to Java. Please note that direct translation is indeed a mapping of language commands or objects  (e.g. HipHop does not qualify).

Probably any pragmatic solution would be indirect translation, i.e. in order to (partially) convert a program P written in high-level language A into a high-level language B:

(complexity lowering) convert codebase of program P from A to low or inter-mediate level language C
(shared codebase) resue parts of converted codebase of program P by calling commands in low or inter-mediate level language C from high level language B

The task is simple. Here are two naive strategies.
Say we want to compile from A to B.

Pick a language C for which you have a compiler A $\to$ C and an interpreter for $C$ in $B$.
Create a new program in B that includes the compilate (in C) as string and the code of the interpreter.

Compile code in A to machine code or intermediate language. Translate line by line to B.

Both give horrible programs -- but you did not require anything fancy.
The more theoretical answer is: we know that effective (i.e. Turing-computable) compilers exist between any two Turing-complete languages, since such define nothing but an admissible numbering.


Polynomial time approximation of NPC problem I have found a polynomial time solution of an NPC problem. My algorithm give exact result in most cases. For example if I run my algorithm for 20000 problem instances, then it fails 10 times to give correct result. But, I am unable to prove the approximation ratio mathematically. Is it feasible to show it with the experimental results? I am waiting to hear the possible solutions for it.

Is it feasible to show it with the experimental results?

No, you can not. There is no shortcut around formal proofs here.


Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation I'm trying to proof/refute the following equation:

$$n^n = \Omega(n!)$$

Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem.

$$\lim_{n\to \inf}{{f(n)}\over{g(n)}} = K$$

However, in this case $n!$ is somewhat of a party-stopper. I found Stirling's approximation which states that:

$$n! \approx \left(\frac{n}{e}\right)^n\sqrt{2πn} $$

My idea was therefore:

$${n^n}\over{(\frac{n}{e})^n\sqrt{2πn}}$$
$${n^n}\over{\frac{n^n}{e^n}\sqrt{2πn}}$$
$${e^n}\over{\sqrt{2πn}}$$
$$\lim_{x\to \infty}{{e^2n}\over{2πn}} = \infty$$

$$ 0 < K \leq \infty $$

therefore the original equation is true.

Is that approach "ok", did I understand Stirling's approximation correctly?

Stirling's approximation states that
$$ n! \sim \sqrt{2\pi n} (n/e)^n. $$
This notation means that the ratio between the two sides tends to 1 as $n$ tends to infinity. For your purposes, we can simply write
$$ n! = \Theta(\sqrt{n} (n/e)^n). $$
Since $\sqrt{n} = o(e^n)$,
$$ n! = o(n^n). $$

If all you want to show $n! = O(n^n)$, then as Jukka mentions you can use the simple bound $n! \leq n^n$.


Difficulty understanding pre-emptive vs non-preemptive CPU scheduling I'm having difficulty understanding what my book is trying to say in regards to preemptive and non-preemptive CPU scheduling.

It says the following:

  CPU Scheduling decisions may take place under the following four
  circumstances:

  When a process switches from the running state to the waiting state (for example, I/O request..)
  When a process switches from the running state to the ready state (for example, when an interrupt occurs)
  When a process switches from the waiting state to the ready state (for example, completion of I/O)
  When a process terminates

  In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for
  execution. There is a choice, however, in circumstances 2 and 3.

  When scheduling takes place only under circumstances 1 and 4, we say
  that the scheduling scheme is non-preemtive; otherwise, the scheduling
  scheme is preemptive. Under nonpreemptive scheduling, once the CPU has
  been allocated to a process, the process keeps the CPU until it
  releases the CPU either by terminating or by switching to the waiting
  state.

It is mainly the bolded part that confuses me. What does it mean by there "being a choice"? The way it's worded almost sounds like it's saying that in circumstances 2 and 3, a new process DOESN'T have to be selected for execution. I'm not quite sure I follow at all what this section of my book is trying to tell me, especially the bolded part.

In circumstances 1 and 4, the current process can't continue running.  Therefore, there's no choice: the OS scheduler has to step in and select a different process.

In circumstances 2 and 3, the OS scheduler has a choice: it can either allow the current process to continue running, or it could step in and put the current process to sleep and select a different process to run.  The latter operation is called "preempting" the current process and scheduling a new one to run.

So, yes, your understanding sounds about right.


Approximate max weight path in directed graph Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights (e.g. $\tilde{w}_{ij} = - w_{ij}$) will result in cycles with negative sum, thus no minimum cost walk exists in $\tilde{G}$.
General question
How well can we approximate the maximum weight path between $i$ and $j$ in $G$, using the shortest path algorithm on a graph $\tilde{G}$ with transformed weights $\tilde{w}_{ij}$ ?
In my case, one has $w_{ij}\in\mathbb{N}\setminus\{0\}$. The transformed weights $\tilde{w}_{ij}$ can be obtained using any function, but I assume a decreasing function $f$ is well adapted so that $w < w' \iff f(w) > f(w')$.
My approach
I am currently trying to use $f(w) = \dfrac{1}{w}$, in this context we have two important paths given a fixed path length $L$.
Denote a path $p = (i_0i_1, i_1i_2, i_2i_3, \dots i_{L-1}i_L$) with weights $W = (w^{(1)}, w^{(2)}, w^{(3)}, \dots, w^{(L)})$,
denote the maximum weight path of length $L$ by $p^*$ with weights $W^*$ achieving
$$ W^* = \arg\max_W\{\mathtt{Cost}(W)\} = \arg\max_W \sum_{k=1}^L w^{(k)}$$
and the path $p_*$ achieving minimum transformed cost with weights $W_*$
$$ W_* = \arg\min_W \sum_{k=1}^L \tilde{w}^{(k)} = \arg\min_W \sum_{k=1}^L f(w^{(k)}) = \arg\min_W \sum_{k=1}^L \dfrac{1}{w^{(k)}}$$
Specific question
In this specific context, do we have the approximation $\mathtt{Cost}(W^*) \approx \mathtt{Cost}(W_*)$ ?
Or is it "very wrong" to replace $W^*$ by $W_*$ ? What would be the distribution of the relative error defined as
$$E_r = \dfrac{\lvert\mathtt{Cost}(W^*) - \mathtt{Cost}(W_*)\rvert}{\mathtt{Cost}(W^*)}$$
Statistical analysis
I have tried a quick statistical analysis as follows:

Letting $L\in\{3,4,5,6,7,8\}$
sampling $w \sim \mathrm{Uniform}(1,w_{\max})$
The value for $w_{\max}$ was also picked from the set $\{50, 100, 150, 200, 500\}$
for each combination of $L,w_{\max}$ I computed $10^5$ values of $W^*, W_*$ using $10^3$ candidate weights $W_i$

The results:

In $80.8\%$ of cases we have $\mathtt{Cost}(W^*) = \mathtt{Cost}(W_*)$ and even better $W^*=W_*$
When computing the relative error $E_r$ one finds that $82.6\%$ of error values are less than $0.001$, $89.7\%$ less than $0.01$ and $99.9\%$ less than $0.1$

The histogram for $E_r > 0$ is as follows

You can't.  That approach is a dead end.  Finding the maximum (simple) path is NP-hard, by reduction from Hamiltonian cycle.  See, e.g., How to prove NP-hardness of a longest-path problem?, How is the Longest Path Problem NP complete?, Longest cycle in a digraph, https://en.wikipedia.org/wiki/Longest_path_problem.  It is also known to be hard to approximate, so you shouldn't expect any such simple approach to give a good approximation for all graphs.


Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the proof using Myhill-Nerode and figuring out other methods to use generally.

Let $L=\{a^p \mid p \in \text{Prime} \}$.

Let $m,n\in\Bbb N$, $m<n$. Let $s$ be the smallest prime number that is bigger than $(3n)! + 3n$.

$a^na^{s-n}=a^s\in L$.
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n < s - (n-m) < s $.

Any number between $(3n)! + 2n $ and $(3n)!+ 3n$ inclusive is not a prime number.
Any number between $(3n)!+3n$ and $s$ exclusive is not a prime number.

So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.

The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.


In instruction pipelining, can we forward an operand more than one clock cycle? Most operand forwarding examples that use the standard 5-stage MIPS pipeline forward operands from EX or MEM by ONE clock cyle to a later instruction. Is it possible to do so for more than one (from the 5th to the 8th clock cycle, for example)?

Paul's Comment is correct:
"Yes. This is one way of avoiding a structural hazard on the write ports of the register file with operations of several different latencies (i.e., having a single writeback stage for all operations). However, adding forwarding paths increases wiring and operand selection complexity."

In general, the amount of hazards and amount of opportunities for forwarding increase with pipeline depth. So a 10-stage pipeline will yield more hazards and more theoretical opportunities for forwarding than a 5-stage pipeline. However, the control logic to detect and schedule all the forwarding increases significantly (likely with a polynomial factor).

The distance of stages you can forward an operand is justified by the minimum of the two following things:

The number of forward stages until the operand enters the register file.
The number of reverse stages where the operand could logically be used.

In other words, it makes no sense to attempt to perform 5 cycles of forwarding on a 5-stage pipeline since all operands would have been in the register file anyway.


Why comparison is dominant time consumption for comparison-based sorting algorithms? Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption?   While I understand the standard analyses of asymptotical behavior of number of comparison operations, I don't quite understand why other costs of other types of operations are negligible.

[Edit 2014-08-26]

If I run the same mergesort implementation on two different computers (with possibly different architecture etc.), how to argue that running time of mergesort divided by the number of compares will approach (possibly different) constants as the problem size increases?

Because the number of comparisons dominates the number of other operations. Since costs of all operations are usually pretty much the same (within a constant factor), costs of non-comparison operations get eaten by constants in the asymptotic measure.


Best way to merge different trees to single data structure? I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast because every tree is simply nested if-else statement. What I noticed is that many trees are similar and I was wondering if there is a way to merge all of those trees into one tree or maybe to reduce number of trees by merging some of them? Maybe even convert everything to some different data structure?

This is what dump looks like:

booster[0]:
0:['::'] yes=2,no=1
    1:['=>'] yes=4,no=3
        3:['es'] yes=8,no=7
            7:['ef'] yes=10,no=9
                9:leaf=-0.0339584
                10:leaf=0.0612883
            8:leaf=-0.0484913
        4:leaf=0.0358804
    2:[';\s'] yes=6,no=5
        5:leaf=0.373993
        6:leaf=-0.0376609
booster[1]:
0:['</'] yes=2,no=1
    1:['h\n'] yes=4,no=3
        3:[':v'] yes=8,no=7
            7:leaf=-0.0487989
            8:leaf=0.0200258
        4:['_t'] yes=10,no=9
            9:leaf=-0.03375
            10:leaf=0.172536
    2:['*\s'] yes=6,no=5
        5:leaf=0.354577
        6:leaf=0.0165644

// etc.. boosters go on and on...

Let me explain how it works by going through booster[0].
First we check if sample we're classyfing contains '::'; if yes we jump to branch 2. There we check if sample contains ';\s' and if yes, we jump to branch 6. Branch 6 is leaf so we just take value -0.0376609 and we add it to probability that sample is class '0'.

We do the same for booster[1] and it gives us probability that sample is of class '1'. It goes on and on for all 50 classes and then the process is repeated for many iterations that gives us 50 * num_iterations of trees. It comes up around 10k of trees.

Anyone has any idea if there is a better way of representing these trees so our classification works even faster?

I don't think post-processing the trees to try to exploit similarity is likely to lead to much success.  Instead, I would suggest trying the following approaches, which to my mind seem more likely to be effective.

Tune the hyperparameters. Try adjusting the number of trees (num_iterations).  If you can get close to the same accuracy with fewer trees, the classifier will be faster.

Try a different classifier. There are other classifiers that are faster for evaluating new samples, especially in the multi-class regime.  For instance, you could try logistic regression and random forests.

Hierarchical multi-class classification. XGBoost is fundamentally a boolean classifier (where there are only two classes).  It handles  multi-class classification (with more than two classes) using the strategy one-vs-rest (or one-vs-all) strategy: if there are $K$ classes, then we construct $K$ boolean classifiers, where the $i$th either outputs "class $i$" or "not class $i$".  This is what leads to the blowup in number of trees: the running time is proportional to $K$.

If your classes have any hierarchical structure, then an alternative is to use a hierarchical structure.  You build a binary tree, where each leaf corresponds to a single class and each internal node corresponds to a set of classes (hopefully, ones that are semantically related).  You construct a classifier for each internal node of the tree, which predicts whether to go left or right down the tree.  You classify each new instance by walking down the tree, as directed by the classifiers that you visit.  Thus, with $K$ classes, we end up with a binary tree with $K$ leaves and of depth (typically) about $\lg K$.  Thus, you can classify a new instance by evaluating $\lg K$ classifiers.  This offers a speedup over one-vs-rest, because the time to classify a new instance is proportional to $\lg K$ rather than $K$.

However, hierarchical classification has some caveats.  It can potentially lead to reduced accuracy.  The effect on accuracy depends on the structure of the class labels.  If there is some hierarchical structure, then it might work well, but if not, it might work poorly.  For instance, suppose you have classes "Poodle", "Chihuaha", "Siamese", and "American Shorthair", you might group the first two into the cluster "Dog" and the latter two into the cluster "Cat".  Thus, you would first apply a Dog vs Cat classifier; then, depending on the result, you would either apply a Poodle vs Chihuaha classifier or a Siamese vs American Shorthair classifier.  So, hierarchical classification might work quite well in this example.  However, if your four classes are unrelated, hierarchical classification might cause a loss in accuracy.

Try a cascaded classifier.  Rather than building a single classifier, try to build a cascade of classifiers.  A cascade is a sequence of multiple fast classifiers, which are applied sequentially.  A classifier can either output a confident answer or can output "not sure"; in the former case, we stop and use that as the answer, and in the latter case, we proceed to the next classifier in the cascade.  The goal is that many instances will get answered quickly (you only have to apply the first few classifiers), and only the difficult ones will have to be evaluated by classifier in the sequence.


Which are the most effective sorting algorithms for a large dataset? A bit of background, the work that I currently and will be doing involves sorting very large amounts of data (in this case, grayscale pixels in descending order), sometimes up to 4 million.

Which are the most effective and efficient sorting algorithms that could handle multiple large datasets (such as descried in the 1st paragraph)?  Is there an algorithm that could simultaneously sort through 2 or more sets of pixels?

quick sort. in C++, it's better to use std::sort rather than qsort(), since it allows compiler to perform much better optimization (both implements quick sort algorithm)
depending on your data, sometimes better: http://en.wikipedia.org/wiki/Counting_sort and http://en.wikipedia.org/wiki/Radix_sort

  simultaneously perform sorts on multiple large datasets?

i've not heard of such algorithms at all. but you can distribute tasks among CPU cores. moreover, you can split one dataset between two cores, and then merge results of sorting


Why does DFS only yield tree and back edges on undirected, connected graphs? Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.

Now, from intuition and in class lectures by Steven Skiena, I know that the above holds true, since it dives all the way down, and then throw a rope back to a previous vertex. I also know that DFS is great in finding cycles.

However, my problem here is that I don't know how to prove that the edge is either a tree edge or a back edge.

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges.

A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such that $u$ is neither an ancestor nor descendant of $v$. So what you need to argue is that in an undirected graph, there's no way you can get a cross edge. It might help to think of why the can occur in directed graphs, and why you can't have this case in undirected graphs.


Prove that the following language is regular Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,1,F1), A2=〈Σ,P,p0,2,F2) be their DFA.

Prove that the following language is regular, by making an appropriate NFA for it:

3={11′22′…′ |12…∈1,1′2′…′ ∈2} (Meaning, the language of all words in which the letters on the even positions (starting from 0) form a word from L2 and the letters on the odd positions form a word from L1.

Would appreciate help with that. Thank you.

The idea is like the production of two DFAs. Let two DFAs be $M_1 = (Q_1, \Sigma , \delta_1, q_{01}, F_1)$ and $M_2 = (Q_2, \Sigma , \delta_2, q_{02}, F_2)$. Define NFA $M = (Q, \Sigma , \delta, q_0, F)$ to have:

$ Q = Q_1 \times Q_2 \times \{0,1\}$

$ \delta((q_1,q_2,0), a) = (\delta(q_1,a),q_2,1) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ \delta((q_1,q_2,1), a) = (q_1,\delta(q_2,a),0) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ q_0 = (q_1,q_2,0)$

$ (q_1,q_2,0) \in F \ \text{iff} \ q_1 \in F_1 \ \text{and} \ q_2 \in F_2$

Note that the 0 or 1 is just indicating moving turn! In a final state, the turn has to be 0 meaning $M1$'s turn!


Best Approach To Parse Human Readable Text To Machine Readable (CSV) I am attempting to parse a large amount of text that cannot be readily used by other software due to the human readable design. However, each "section" of the text has the same format. By "section", I mean lines 1-10 (section 1) will have the same format as lines 11-20 (section 2). My plan is to loop through this text and gather all sections into a list. Then convert that list into a CSV.

Example:

####################################
123456789   first-name last-name   2/25/2018
------------------------------------
more-user-info1               12345
other-info1
123                   user-name1
------------------------------------
even-more-data1
####################################
112233445   first-name last-name   1/1/2018
------------------------------------
more-user-info2               78900
other-info2
555                   user-name2
------------------------------------
even-more-data2
####################################
<piece 3 here> ...

So to give you an idea ###... means new section.

My question is what is the best approach to parsing this data? This is just an example, a real section has a lot more data and a lot of edge cases/optional data. This is also coming from a super old program so I am not aware of any blueprint or business rules around the data.

I am currently using regex to find the data I need to store. Are there any options besides regex to parsing non-strictly structured text?

My approach is to check that my assumptions about the format of the data are correct while reading. Example, I ensure that as expected, I get the series of # characters, that the next line starts with a number and ends with a date as mm/dd/yyyy. Upon any failure, I would throw an exception with a message such as "expected so and so at line xxx but found yyy". In case things go south, I will not be left with some cryptic error message related to regex.


Efficient way to find key points on spline to approximate it with line strip Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the line strip and the spline at any given point is <= d.
Here is a visual example. I'm looking to find a computationally efficient way to find the points in the green circles that I use as beginnings and endings for the lines.

What I thought about is walking along the spline, summing up the traveled distance. As I walk the spline, I test the last position as a key-point candidate. Once the distance traveled on the spline and the length of the line through the key-point candidate deviate by a certain percentage, I use the last key point candidate that was still below that percentage. What I'm uncertain about is first, if there is a more efficient way, and second, deviation in length as a percentage is not really the same as distance (e.g. in cm). If there is a relatively long, relatively straight part of the spline, the length deviation that I might accept, could lead to quite a large distance between the spline and the line somewhere on the way, couldn't it?
[Discussion / Comments]
What's a "line strip"?
For the purpose of this question a line strip is a bunch of connected line segments, like the red strip in the image above.
Do you require that each endpoint of each line segment in the line strip must be on the spline?
No. I just require that the maximum distance between the line segment and the spline segment is <= d. And I want to end up with a small number of line segments. It doesn't need to be the smallest number possible, but it should be reasonably small. The smaller the better. If allowing for a few extra segments prevents me from having to iterate over my solutions for optimization, I'd take that.
Given the difference between the lengths of the curved and straight segments, you can give an upper bound for maximal distance between them
That is not a bad idea! As I stated above, I tried this by giving the deviation in percent of the line-segment's length. But using the absolute deviation in length instead (without converting to percent), does give me an upper bound for the maximum distance. So this would be better than what I used before.

A simple approach would be to take a dense sample of points on the spline (i.e., more than you need), and then apply the Ramer-Douglas-Peucker polyline simplification algorithm to get rid of as many of them as possible. Note: Unless you generate the point sample in some clever way (e.g., with density proportional to the local curvature), this isn't guaranteed to recover sharp bends perfectly.
According to that Wikipedia page, the straightforward implementation takes $O(n^2)$ time in the worst case for $n$ points, though there is also a more complicated version due to Hershberger and Snoeyink that takes just $O(n \log n)$ time in the worst case.


PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$ Can someone help with this
$L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Let me prove a more general theorem.

  For $A \subseteq \mathbb{N}^2$, the language $L(A) = \{a^i b^j : (i,j) \in A \}$ is context-free iff $A$ is semi-linear.

One direction is Parikh's theorem. In the other direction, it suffices to show that $L(A)$ is context-free if $A$ is linear (since every semi-linear set is a union of linear sets). Indeed, suppose that $A = (i_0,j_0) + \sum_{t=1}^m \mathbb{N} (i_t,j_t)$. Then $L(A)$ is generated by the grammar
$$
S \to a^{i_0} b^{j_0} \mid a^{i_1} S b^{j_1} \mid \cdots \mid a^{i_m} S b^{j_m}.
$$

A classical result shows that a set is semi-linear iff it is definable in Presburger arithmetic. In particular, if $A$ is the solution set of a system of linear inequalities with rational coefficients (as in your example) then $A$ is semi-linear and so so $L(A)$ is context-free.

In your particular case, ignoring for the moment the condition $i > 0$, we have
$$ A = \{ (i,j) : 2i \leq 2j \leq 3j \} = \mathbb{N}(1,1) + \mathbb{N}(2,3). $$
Indeed, clearly $(1,1),(2,3) \in A$ and $A$ is closed under addition, and so $\mathbb{N}(1,1) + \mathbb{N}(2,3) \subseteq A$. In the other direction, suppose that $2i \leq 2j \leq 3i$. Then
$$
(3i-2j)(1,1) + (j-i)(2,3) = (i,j).
$$
This shows that the following grammar generates your language without the condition $i > 0$:
$$ S \to \epsilon \mid aSb \mid a^2Sb^3. $$
If we bring back the condition $i > 0$, then we get the decomposition
$$
A = \{ (i,j) : 2i \leq 2j \leq 3j \text{ and } i > 0 \} = \{(1,1) + (2,3)\} + \mathbb{N}(1,1) + \mathbb{N}(2,3),
$$
leading to the grammar
$$
S \to ab \mid a^2b^3 \mid aSb \mid a^2Sb^3.
$$

In these examples all linear sets were generated by two vectors ("periods"). Indeed, a classical result (following from Caratheodory's theorem; see for example Slide 24 of these slides by Widjaja Lin) shows that every semi-linear set in dimension $k$ (in our case, $k=2$) is the union of linear sets with at most $k$ periods.

If you are interested in the algorithmic side of things, The taming of the semi-linear set is a good starting point.


Prove that $\texttt{prefix}(L)$ is regular Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular.

So far I have provided that the grammar to produce this language is:
$S \rightarrow 0S1 \thinspace | \thinspace \epsilon$

Would you go about proving $\texttt{prefix}(L)$ is regular just like you would any language, proving that $\Sigma^\star$ = $\texttt{prefix}(L)$, or by induction on the length of the words in $\texttt{prefix}(L)$.

It appears that $prefix(L)$ is non-regular.

Let $L = \{0^n 1^n: n \ge 0\}$.  Then, $prefix(L)$, defined to be the set of all prefixes of strings in $L$, is the set of all strings that consist of zero or more $0$'s followed by at most the same number of $1$'s, i.e. $prefix(L) = \{0^n 1^m: m \le n\}$. Intuitively, the reason $prefix(L)$ is nonregular is that a machine that can check whether the number of $1$'s does not exceed the number of $0$'s must store a count of the number of $0$'s in the input seen so far, and so this language cannot be recognized by a machine with a finite number of states.

A formal proof that $L' := prefix(L)$ is nonregular is as follows.  Consider the subset $S = \{0^1, 0^2, \ldots, 0^p\}$.  Any DFA $M$ that recognizes $L'$ must take the inputs $0^i$ and $0^j$ $(i < j)$ to different states because $0^i 1^j \notin L'$ but $0^j 1^j \in L'$.  Hence, the machine $M$ contains at least $p$ states.  But $p$ was arbitrary. This proves there does not exist a DFA (with a finite number of states) recognizing $L'$.

This proof method requires us to find an infinite subset $S$ of pairwise distinguishable prefixes; see online about the Myhill-Nerode theorem.


Problems unsolvable by an oracle machine? Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?

Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...

Every problem $P$ can be solved with an oracle machine with oracle access to $P$. In order to get a more meaningful answer, we consider the concept of Turing semi-degree, which is the set of all problems computable with an oracle to $P$, for some problem $P$. The same diagonalization argument used to prove that the halting problem isn't decidable shows that no Turing semi-degree encompasses all languages. (Alternatively, there are uncountably many languages but only countable many problems computable with any given oracle.)

A Turing degree consists of the "hardest" problems in a Turing semi-degree. More formally, it is the set of problems equivalent to some problem $P$: problems which are computable given an oracle to $P$, and conversely $P$ can be computed given an oracle to them. The study of Turing degrees consists a significant part of classical recursion theory.


Subset sum problem for permutations Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, alternatively, as a variant of this problem, in the same order) is equal to $g$, i.e. $g_{i_1} \circ g_{i_2} \circ \cdots \circ g_{i_k} = g$.

This is actually a subset sum problem, but for symmetric group $(S_n, \circ)$ instead of $(\mathbb{Z}, +)$.

The questions are:

Is there a known solution in polynomial time?
Otherwise, is this problem known as NP-complete?

I've found a paper on knapsack problems in groups, however, these results seems to be not applicable for symmetric group.

The subset sum problem is even harder(NP-hard) for special groups which you can embed into $S_n$. See the paper you have linked in the problem description.

$\textbf{Observation:}$ $g$ can be writtens as combination of elements $\{g_1,\ldots,g_k\}$ if and only if $g \in \langle g_1,\ldots,g_k\rangle$. Under the assumption that each of $g_i$ can appears any number of times.

The complexity of the problem depends upon the input representation. There are two two most commonly used ways, Cayley table and generating set. For Cayley table see this paper for results. Read the CGM(Cayley membership problem) Link

$\textbf{CGM} $

$\textbf{Input :}$ A group $G$ by its Cayley table, $X \subseteq G$ and $t \in G$.

$\textbf{Output :}$ Does $t$ belong to the subgroup $\langle X \rangle$ generated by $X$?

In general problem is in Symmetric log space.

$\langle A \rangle$ means subgroup generated by $A$


If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$? Suppose the following is true for some f(n) and g(n):
$f(n) = \Theta(g(n))$
Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?
I know that for the above to be true, there must exist positive constants $c_1$, $c_2$, $n_0$ such that for all $n \geq n_0, $ $c_1(g(n)) \leq f(n) \leq c_2(g(n))$. Thus if $f(n) = \Theta(g(n))$, then can I assume:
$\frac{1}{k}c_1(g(n)) \leq f(n/k) \leq \frac{1}{k}c_2(g(n))$ to satisfy big Theta?
My apologies if this is totally obvious or if I'm completely on the wrong track, my math background isn't the strongest. Are there any relevant properties that might describe this relationship?

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.


Ambiguous Grammar and SLR parsing table : No conflicts? We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-then-else grammar which is pretty much ambiguous.

So I started with the following rules ( as given in Principles of Compiler Design, Aho and Ullman, 2002 Reprint)

$$
S \rightarrow iCtSS' \\
S \rightarrow iCtS \\
S \rightarrow a \\
S' \rightarrow eS \\
S' \rightarrow \epsilon \\
C \rightarrow b \\
$$

S is the statement, and C is the condition. All apart from S', S and C are terminals, and epsilon refers to null.

The given grammar is written in a way that conforms to recursive descent parsing.

Augmented the grammar as

$$
S\prime\prime \rightarrow .S \\
S \rightarrow .iCtSS' \\
S \rightarrow .iCtS \\
S \rightarrow .a \\
S' \rightarrow .eS \\
S' \rightarrow .\epsilon \\
C \rightarrow .b \\
$$

And then generated the instances-set as

$$
I_{0} [ S\prime\prime \rightarrow .S, S \rightarrow .iCtSS', S \rightarrow .iCtS, S \rightarrow .a, S' \rightarrow .eS, S' \rightarrow .\epsilon, C \rightarrow .b]\\
I_{1} [S \rightarrow i.CtSS', S \rightarrow i.CtS, C\rightarrow.b]\\
I_{2} [S \rightarrow a.]\\
I_{3} [S'\rightarrow e.S, S \rightarrow .iCtSS\prime, S \rightarrow .iCtS]\\
I_{4} [S \rightarrow \epsilon.]\\
I_{5} [C \rightarrow b.]\\
I_{6} [S \rightarrow iC.tSS\prime, S\rightarrow iC.tS]\\
I_{7} [S\prime \rightarrow eS.]\\
I_{8} [S \rightarrow iCt.SS\prime, S \rightarrow iCt.S, S \rightarrow .iCtSS\prime, S\rightarrow.iCtS, S\rightarrow.a]\\
I_{9} [S \rightarrow iCtS.S', S \rightarrow ICtS., S' \rightarrow .eS, S' \rightarrow .\epsilon]\\
I_{10} [S \rightarrow iCtSS'.]\\
$$

Based on these sets that I made, I constructed a parsing table

However, as per my derivation of the instance-sets, there were no conflicts in the table (the grammar being ambiguous), I was not sure if I worked it out correctly. One thing that adds to the dilemma that there has been no instance where S was the first non terminal in grammar, and so there are no states that can accept the final variable S during parsing.

Can anyone please help me with this? I checked it further online and they mentioned that the ambiguous grammar tended to have conflicts, but there were none in this case. Where am I going wrong?

Thanks.

In state 9, you can reduce either $S$ or $S'$, as well as the possible shift action for $e$. So there are both reduce/reduce and shift/reduce conflicts.

The production $S' \rightarrow \epsilon$ cannot be correct; there is already a production $S \rightarrow iCtS$ for an if without an else, so if $S'$ can derive the empty string, $S \rightarrow iCtSS'$ is ambiguous. Once you remove that, you will still have the shift-reduce conflict with $e$. (Since an SLR parser doesn't use lookahead to restrict reduce actions, the entire row for a state with a reduce action must consist of precisely that reduce action. But this particular grammar is ambiguous, so using LALR(1), for example, won't help.)

Finally, $\epsilon$ is not a symbol; it is simply a way of making an empty symbol sequence visible. So it cannot be the head of a column the action table, and also it cannot be on the right hand side of the dot in an item.


Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below?

Fact 1: For monotone submodular functions, Nemhauser, Wolsey and Fisher proved [1]  that simple greedy algorithm gives $1-1/e$ approximation guarantee.

Fact 2: For non-monotone non-negative submodular functions, Buchbinder et. all proved [2] that randomized greedy algorithm gives $1/e$ approximation for cardinality constraint.

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use.

There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes into the sum of a monotone submodular and an arbitrary modular function. The optimization problem is
$$ \max_{S \in \mathcal{I}} g(S) - c(S) \enspace,$$
where $g:2^V \rightarrow \mathbb{R}_+$ is a non-negative and monotone submodular function, $c:2^V \rightarrow \mathbb{R}$ is a modular function, and $\mathcal{I} \subset 2^V$ is a matroid on the ground set $V$. Note that if $c$ takes positive values, then the entire submodular objective $f = g - c$ is non-monotone and may take negative values.  The first approximation result was given by Sviridenko, Vondrák, and Ward in 2014 who showed that one can use a continuous extension & rounding approach to obtain a set $S$ such that
$$ g(S) - c(S) \geq (1 - e^{-1}) g(OPT) - c(OPT) $$
They applied this result to obtain tight approximation guarantees for monotone submodular maximization and monotone supermodular minimization with bounded curvature. They also show that this approximation is tight in the sense that no algorithm making polynomially many queries to $g$ and $c$ can do better. Then in 2018, Feldman gave an algorithm that also goes through the continuous domain but is more efficient in that it by-passes a certain "guessing step" in the previous algorithm. Most recently, Harshaw, Feldman, Karbasi, and Ward in 2019 gave a series of much faster algorithms which do not go through the continuous extension, but are based on greedily optimizing a "distorted surrogate objective" which changes thoroughout the algorithm; however, their results apply only when the modular function is non-negative and the constraint is a cardinality constraint. They also extend the analysis to show that when $g$ is $\gamma$-weakly submodular, then one may obtain the analogous approximation
$$ g(S) - c(S) \geq (1 - e^{-\gamma}) g(OPT) - c(OPT)  $$
Moreover, this extended approximation guarantee is tight in the value oracle model.

There is the hardness result by Uriel Feige which shows that even verifying that $f(S) \geq 0$ for some $S$ is NP-Hard. So, the decomposition into a sum of submodular and monotone functions really is crucial in all these algorithms.
I don't know how much further one can push the decomposition approach.


Proving that non-regular languages are closed under concatenation How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?

You can't prove it because it isn't true: the class of non-regular languages isn't closed under concatenation.

Let $X\subseteq \mathbb{N}$ be any undecidable set containing $1$ and every even number.  For example, take your favourite undecidable set $S$ and let $$X = \{0, 2, 4, \dots\} \cup \{1\} \cup \{2i+1\mid i\in S\}\,.$$ The language $\mathcal{L} = \{a^i\mid i\in X\}$ is undecidable, so it certainly isn't regular.  But $$\mathcal{L}\cdot\mathcal{L} = \{a^{i+j}\mid i,j\in X\} = \{a^i\mid i\in\mathbb{N}\}\,,$$
is regular.


Algorithm for Even Fitting I'm trying to design an algorithm for evenly fitting decimal numbers into a decimal number.

Say I have a set $N$ of decimal numbers ($N_1$, $N_2$, ..., $N_n$) and a target value $Y$. I'd like to see what combination of values of $N$ (values may be used zero to many times) add up evenly to $Y$.

I've accomplished it by selecting random values of $N$ until I either add up to $Y$ or pass it - at which point I start over. This algorithm does not seem efficient, however. Sometimes it takes 50k passes before it lands on an answer.

The set I'm actually working with is 21 dollar values between \$0.89 and \$8.04 and the target is \$43.94.

Is there a simpler algorithm?

Provided the $N_i$ are all positive, this is pretty much exactly the problem of "how many ways can I make value $Y$ out of coins with values $N_i$ (assuming no restriction on the number of coins)?"

That problem has a very easy recursive solution that breaks into two cases at each step:

Include a "coin" of value $N_i$ and recurse.
Assume you have used $N_i$ as many times as you are willing and recurse using only values $N_j$ for $j > i$.