Convert an IF statement in Mixed Integer Programming I want to convert an IF statement for my optimization problem. I want to minimize the total price. I want 800 tones of salt and 3 suppliers offer me their prices.
Supplier $1$ offers me $100$ tones at $\\\$150$ a tone.
Supplier $2$ offers me $400$ tones at $\\\$170$ a tone, if I take $300$ tones (or more)the price drops to $\\\$150$.
Supplier $3$ offers me $1600$ tones at $\\\$170$ a tone.
Here is my model without the if statement :
$x_i$ is an integer variable representing the quantity bought to the supplier $i$,
$p_i$ is the price of the supplier $i$, $c_i$ is the maximal capacity offered by the supplier $i$.
$Min( p_1\times x_1 + p_2\times x_2 + p_3\times x_3)$
$s.t.  x_1 + x_2 + x_3 = 800$
$ x_1 \leq 100$
$ x_2 \leq 400$
$ x_3 \leq 1600$
Now I want to use the Big M method the convert my if statement but I don't know how to do it.
I tried this method : Express a "complex" IF-Statement to Linear Programming to find the constraints but I don't know how to modify my prices. I tried this :
If $x_2 \geq 300$, Then $p_2 = 150$, Else $p_2 = 170$.
i.e.
If $x_2 \geq 300$, Then $b = 1$, Else $b = 0$ and $p_2 = 150b + 170(1-b)$
In addition to this I code in python the the mip library, do you know a better library to do this?
Thanks a lot !

Let $x_i$ represents the quantity bought from the $i$-th supplier, and
consider the following scenario: the price of the 2nd supplier is 170\$ per tonne but, if you buy at least 300 tonnes, then you get to choose a non-negative quantity $d \le x_2 - 300$ and you get a 20\$/tonne discount on $d$ tonnes, otherwise $d=0$ (i.e., you get no discount).
Clearly this is equivalent to your original problem since, given $x_1, \dots, x_3$, it is always convenient to maximize $d$.
You can model this as follows:
$$
\min 150x_1 + 170 x_2 + 170x_3 - 20d \quad \mbox{s.t.}\\[6pt]
\begin{align*}
x_1 &\le 100 \\
x_2 &\le 400 \\
x_3 &\le 1600 \\
x_1 + x_2 + x_3 &= 800 \\[6pt]
100 y &> x_2 - 300 & (1)\\
300 y &\le x_2 &(2)\\[6pt]
d &\le x_2 - 300y &(3)\\
d &\le 100y &(4)\\[6pt]
x_1, x_2, x_3,d &\ge 0 \\
y &\in \{0,1\}
\end{align*}
$$
Notice that $y$ is a binary variable that equals $1$ if and only if $x_2 \ge 300$. Indeed, if $x_2 \ge 300$ the constraint $(1)$ is satisfied only when $y=1$ (recall that $x_2 - 300$ is at most $100$), and the constraint $(2)$ simplifies to $300 \le x_2$, which is true. If $x < 300$ then the constraint $(2)$ forces $y=0$ and the constraint $(1)$ simplifies to $0 \ge x_2 - 300$, which is true.
If $y=0$, then $d$ must be $0$, and this is enforced by constraint $(4)$ which becomes $d \le 0$ (recall that $d$ is non-negative), while $(3)$ is always satisfied. If $y=1$, then constraint $(3)$ enforces $d \le x_2 - 300$, which also implies constraint $(4)$ since $d \le x_2 - 300 \le 100 = 100y$.


Is there a way to find a simple regular expression for this language? Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is divideable by 5. Obviously this is a regular language, and I can also find a simple linear grammer.

My idea for a regular expression was to check all the combinations where I can receive sum zero (in modulo 5) with the digits 1 and 2 and put 0* in between. But is there no better way? Something more elegant?

Edit:
My expression is $0^* 1 0^* 1 0^* 1 0^* 1 0^* 1 0^* \cup 0^* 1 0^* 1 0^* 1 0^* 2 0^* \cup 0^* 1 0^* 1 0^* 2 0^* 1 0^* \cup 0^* 1 0^* 2 0^* 1 0^* 1 0^* \cup \ldots $ and so it goes on for all the possible combination. My question is if there is a way to simplify this - Or maybe a different approach?

Forget about the $0$, they are boring. Like you said, you can add $0^*$ basically everywhere and you are done.

Now for the $1,2$. Just try to order them in batches that total 5. Then you realised that this might be problematic in case at the count of 4 we read $2$ and overshoot by one. No problem, we remember this, and continue until we reach a proper multiple of five. Note however, that the overshoot just might repeat when we have $212$, or similar.

So here is how the regular expression is constructed: any multiple of five, or when we reach an overshoot, wait until we are back. Repeat.

First some abbreviations:

$E_5= \{11111,1112,1121,1211,2111,221,212,122\}$.

$E_4 = \{1111,112,121,211,22 \}$.

$E_{\mathrm{shoot}}= \{1112,212,122\}$.

Finally here is your expression:

$\Big ( E_5 \cup E_4\cdot 2 \cdot (E_{\mathrm{shoot}})^*\cdot E_4\Big )^* $.

Ah. Add $0^*$, lots of them.


To remove all comments in a JavaScript file, do we need just a scanner or also a parser? I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string:

let hi = " // here ";
let foo = "   use this: /*   ";
let foo2 = "   \" and that */   ";

it also can get complicated with the cases with string being able to be quoted by ' and the backtick `:

let hi2 = 'here //';
let i = 123;
let hi3 = `here //  ${i  /* don't use j */}`;
let hi4 = `here //  ${i  // don't use j
                         // because j is not good
                     }`;
let hi5 = ` and use there ' " \' \" \`  /*  */`;
let hi6 = ` this is really closing, not quoted backtick \\`;
let hi7 = `here //  ${i  /* don't use j in `` */}`;

So I mentioned a scanner (lexical analyzer) and a parser (like yacc or bison) can be used. So we can build a tree of node representing the program, and then wherever it is a comment type of node, we can remove it. (comment nodes have no children, I think? If they do, then can just change the comment to nothing, the empty string).

But is it true that all we need is a scanner?  We can tokenize all the text, and then we get each element which is a string, an operator, the left and right operands, and also the comment elements.

And then we can just remove all the comment elements and then reconstruct the program using all the tokens.

So probably we don't even need the program code to be represented as a tree, but just as a series of tokens.  So if we already have a scanner and parser, all we need is a scanner, and when we supply it with the proper grammar rules, we can remove all the comments?

(is the following considered grammar or just finite state automata and do we just use it to form the tokens?)

Scanner (tokenizer) will be enough. Most programming languages do not allow comment nesting, so there is no need to use recursive parsers to strip all comments.


Algorithmic consequences of algebraic formula for partition function? Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic consequences for fast computation of the partition function?

It is my uninformed belief that Rademacher's formula is faster in practice (and perhaps in theory also) than the Bruinier and Ono formula. While Rademacher's asymptotic expansion is an infinite sum, we know that $p(n)$ is an integer, so if we have bounds on the tails of the expansion, we can use the formula to compute $p(n)$. According to Calkin et al., "the exact formula of Rademacher yields a very fast algorithm".

Bruinier and Ono describe what would take to implement their algorithm in Section 5 of their paper. The first step is to determine representatives for $\mathcal{Q}_n$, of which there are $h(-24n+1)$. According to Soundararajan, we should expect $h(-24n+1) = \Theta(n)$, so the formula would involve $\Theta(n)$ summands. That makes it worse than Euler's formula for $p(n)$ (computationally speaking), though the latter admittedly requires $\Omega(n)$ memory.


Understanding N process Peterson's algorithm The intuitive informal description of two process Peterson's algorithm for process 0 can be given  as follows:

flag[0]=true;                   //I am ready to enter my critical region
turn=1;                         //but you may take your turn to enter your critical section

while(flag[1]==true && turn==1) //if you are ready to enter your critical section
                                //and if its your turn,
{ }                             //I will wait

//Critical Section

flag[0]=false;                  //I am no more ready to enter my critical section

Peterson's algorithm for n processes is given as follows:

Each process runs the following pseudo code:

lock(pid);
<critical section>;
unlock(pid);

where lock() and unlock() functions are defined as below..

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;
    turn[count] = i;
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
}

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;

Now I want to understand the n process Peterson's algorithm in same intuitive way, but I am unable to bring such informal explanation for it. To be precise I want to know the following:

In 2 process Peterson's algorithm, flag[i]=true means "process i is ready to enter its critical section". What does it mean in n process algorithm when flag[i]=true
In 2 process Peterson's algorithm, turn=1 means "its process 1's turn to enter its critical section". What does it mean in n process algorithm when turn[i]=x
How can we intuitively /  informally describe the line:

 "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"

The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this:

When a process wants to start running (i.e.: executes lock()), it imagines that it's joining an imaginary queue of processes. It doesn't know exactly how many processes are in the queue nor exactly what position in the queue it is in (because of the vagaries of concurrency). It does know that the queue can only have N possible positions because there are N total processes. The goal is for to only allow a process to exit the lock() procedure once it is sure that it is at the head of the queue.

To keep the notation consistent with the pseudocode listed above, we'll say that position 0 is the tail (back) of the queue, position N-1 is the head (front) of the queue, position N-2 is second from the front, etc... , and position -1 means you're not in the queue at all (i.e.: has not executed lock()).

What each process does is it makes an estimate of what its potential position is in this queue and declares that it is the most recent process to estimate that it is in that position (if that position is not -1). Initially, when a process first starts the lock() procedure, it will of course estimate that it is at the back of the queue (i.e.: position 0). These estimates of where each process thinks it is in the queue and who is the most recent process to think they are in each position is shared information. In the pseudocode the position estimates per process are stored in the flags array and the list of most recent process per position is in the turn array.

Then, each process looks around at this shared information to see if it can update its estimate of where it is in the queue. These updates can only move a process's estimate one position forward in the queue (i.e.: closer to the head). You can update your position in two situations: 1) if another process comes later than you and thinks it is in the same position as you, 2) if everyone else thinks they're strictly behind you. Whenever you see one of these situations happen, you can update your estimate of your position to move one step toward the head.

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;                 // I think I'm in position "count" in the queue
    turn[count] = i;                  // and I'm the most recent process to think I'm in position "count"

    "wait until                       // wait until
     (for all k != i, flags[k]<count) // everyone thinks they're behind me
     or (turn[count] != i)"           // or someone later than me thinks they're in position "count"

                                      // now I can update my estimated position to "count"+1

 }                                    // now I'm at the head of the queue so I can start my critical section

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;                        // I'm not in the queue anymore

As noted before, this is slightly different than the presentation of the 2-process version as given above. However, we can reframe that presentation in this framework easily with only some slight modification. Note that in the 2-process case, the queue only has two potential positions, the head (position 1) and the tail (position 0) of which only position 0 is explicitly claimed.

flag[0]=0;                   // I am at the tail of the queue
turn=0;                      // and I am the most recent process to join the queue

while (flag[1]==0            // while you are in the queue
    && turn==0)              // and I joined the queue later than you did
  { }                        // I will wait

//Critical Section

flag[0]=-1;                  // I am no longer in the queue


(Generally) How to specify asynchronous action with side effects using logic equations Say you have this function call sequence:

function all() {
  fn1()
  fn2()
  fn3()
}

And say that fn2 was asynchronous and caused all kinds of side effects:

var globalPacketCounter = 0

function fn2() {
  var httpRequest = ...
  httpRequest.on('data', function(){
    globalPacketCounter++
  })
  drawGraphicsToDisplay()
  ...
}

Something complicated and with unknown implementation, though you can probe it to determine the types of behavior it has, and read docs, etc.

I'm wondering, generally speaking, what you can do to incorporate this into a model checking or symbolic evaluation system, or other verification system like Hoare logic or something. I would like to do this:

all() =
  /\ fn1() in state 1
  /\ fn2() in state 2
  /\ fn3() in state 3
  /\ complete = true in state 4

Some sort of logical statement. The question is (partially) if this is a valid approach; that is, treating the fn2() as a single step in a logic equation. The main part of the question though is how to generally do this. I would like to basically treat everything as logic functions but am not sure how to apply it to the "async with side effects" case.

One way to model your example is through program graphs. (See chapter 2 in Principles of Model Checking.) What you can do is model all() as one program, which synchronizes on action 'data' with another program that runs concurrently to all(), let's call it listen(). listen() will have an initial state where it waits until it can synchronize with the all() on action 'data'.

Once you have these two models (or more for bigger examples) you can interleave them, which is a construction that contains all the possible states. Program graph interleaving also preserves shared variables (so globalPacketCounter will be updated correctly) unlike interleaving on transition systems. Though I would be careful about them, since atomicity is not implicit in the models. You can read more about critical actions in section 2.2.2. of the book.

After interleaving of PGs you construct a transition system, which you can transform to a logical equation. And there you have it.


Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples? The way I think of reducing problem $A$ to problem $B$ in polynomial time, i.e. $A \leqslant_P B$,  is that you assume an efficient solution to $B$ which is enough to solve $A$. Now, this is suspiciously similar to $A \in \mathsf{P}^B$. I'm confident that $A \leqslant_P B \implies A \in \mathsf{P}^B$ but is the reverse implication true? If not, can you provide some counter examples?
Similarly can anything be said about the statement:
$$
A \leqslant_L B \iff A \in \mathsf{L}^B
$$
Edit: Clarified $\leqslant_P$ is polynomial reduction and fixed notation for PTIME, LOGSPACE.

Assuming $\le_P$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect.
For example, for any language $L$ we have $\overline{L} \in P^L$ (and in fact, in $O(1)$ time and space as well, so this is also an example for logspace many-one reductions)
But obviously if we take $L=\mathrm{Halt}$ to be the halting problem language, we wont have that $\overline{L} \le_P L$ since $\mathrm{Halt}\in \mathsf{RE}$ but $\overline{\mathrm{Halt}}\notin \mathsf{RE}$ and $\mathsf{RE}$ is closed under $\le_P$.


What does $k$ mean in regular expressions? From what I have learned in Introduction to Automata Theory, Languages, and Computation, regular expressions can be represented with $R^{(k)}_{ij}$.

I understand that $i$ and $j$ represent the starting state and the closing state respectively. However, I am still trying to understand the purpose of $k$.

To put it simply, what does $k$ stand for in $R^{(k)}_{ij}$?

Side note: Link to the book is here.

$k$ means that if $w \in R^{k}_{ij}$ then on reading $w$, FA starting from the state $i$ enters the state $j$ and never enters a state $t$ where $t > k$ while reading input $w$. In the book, you learn from, $R^{k}_{ij}$ is defined as the set of all strings that transition the automaton $M$ from $q_i$ to $q_j$ without passing through any state higher than $q_k$.


Deterministic Nonfinite Automaton - Longest Block of Ones How to Think About Algorithms - Jeff Edmonds

Exercise 2.2.2

The problem asks to find  $\sum$, Q, δ, s, and F of this program if we see it as an automaton. Edmonds characterized this as deterministic non-finite automaton since 'n' is not bounded.

$\sum$ is {0,1} but I'm not sure how to model Q and the transition functions.

One guess is just simply Q = { q[p_max, q_max, length_max, p_current, length_current] }, with each of the 5 variables taking a value in the set of size around n ( { 1, 2, 3, ... , n} ), which will have O(n^5) states

but even if I use this brute force approach I can't easily define transition functions that determine the next state based on current state and the input read each iteration (0 or 1).

The biggest difficulty is modeling conditionals. When you are at a state q_1, the next state seems to be defined not just by 0 or 1 input but also by the length variables.

He didn't provide any solutions and I did a lot of research but still lost.

Any suggestions?

Your guess is definitely on the right track, though you may need one more piece of information. As you have infinite states (of which each input will use some number of them according to a function of the length of the input), you can use (as you observe) the states to encode information that deals with the length of the input.

There are a number of ways to do this (you can use the same variables as the code essentially), but I think it's clearer to be more explicit. Each state can keep track of the following six things:

The starting position of the best run so far.
The ending position of the best run so far.
The length of the best run so far.
The starting position of the current run being counted.
The ending position of the current run being counted.
The length of the current run being counted.

So each state could be labeled something like:

$$q_{maxstart,maxend,maxlength,currentstart,currentend,currentlength}$$

This then solves the transition problem:

A zero in the input ends the current run, and resets to start counting again, but doesn't affect the best run so far
A one in the input increases the end point of the current run (and sets the starting point if the current run length is zero) AND if you happen to be in a state where the current run length is the same as the best run length, it also alters the best run length subscripts (that is, the transition takes you to a state where those change suitably).

There's no branching in either of those, so the process is completely deterministic.

A couple of examples to illustrate:

The start state is easy, it's just $q_{0,0,0,0,0,0}$ with the transitions $\delta(q_{0,0,0,0,0,0},0) = q_{0,0,0,1,1,0}$ and $\delta(q_{0,0,0,0,0,0},1) = q_{0,1,1,0,1,1}$. This uses the case where the current run length is the same as the best, and we see a one, so we update the best start and end to be the same as the current start and end etc.
Now let's try a state where the current run changes, but isn't better than the best. Imagine we're in state $q_{a,b,50,x,y,3}$, then the two transitions will be $\delta(q_{a,b,50,x,y,3},0) = q_{a,b,50,y+1,y+1,0}$ and $\delta(q_{a,b,50,x,y,3},1) = q_{a,b,50,x,y+1,4}$.

This actually pretty much covers all the cases (as there's really not much going on except the abuse of subscripts to count for us).

To boil that down to some rules for putting in the transitions:

$\delta(q_{a,b,n,x,y,m},0) = q_{a,b,n,y+1,y+1,0}$
If $m < n$, $\delta(q_{a,b,n,x,y,m},1) = q_{a,b,n,x,y+1,m+1}$
If $m = n$, $\delta(q_{a,b,n,x,y,n},1) = q_{x,y+1,n+1,x,y+1,n+1}$

You don't need any states where $m > n$, so you don't have to worry about that case (though you can include them and give them a rule like #3 if you want a complete infinite enumeration of all the subscripts.


Why is my regular grammar for palindromes wrong? I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with.

I've created grammar which can generate all palindromes and that is why I wonder why it's wrong.

A -> e
A -> a | b | ... | z
A -> aAa | bAb | ... | zAz

Your grammar is correct, in the sense that it does generate all palindromes over the alphabet $\{a, \dots, z\}$. But it's a context-free grammar and not a regular grammar. In a regular grammar, you're only allowed rules of the form $A\to\epsilon$, $A\to a$ and $A\to aB$, i.e., there is at most one non-terminal on the right and any terminals must come before it.

(Alternatively, you get the same class of languages by insisting that any terminals on the right must come after the nonterminal but you can't mix the two in a single grammar.)


Does FACTORING have optimal substructure or analog to it? Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily solvable instance is encountered, at which point the ancestry of subproblems can be successively reconstructed from the sequence of solved instances to arrive finally at the solution of the original problem.

In terms of original research toward this question I considered the following two possibilities. It is not thought that either of these are to be very workable, and are here to attempt to illustrate the intended meaning of the question, which then asks whether it is likely there are approaches that could be workable that display optimal substructure or analogous structure:

The hypothetical, magical FACTOR_SUCCESSOR function, which when given an integer factorization for X, returns the integer factorization for X+1 in polynomial time in log(X). [This can be used to construct a factoring algorithm to factor N using the binary (or any other) base representation of N.] This hypothetical function seems difficult to construct since, for example, see here.
An approximation approach. This would make use of the idea that if large (>500 decimal) N is hard to factor (say a semiprime), then perhaps if N-m is k-smooth, with factors in a multiset F, and then perhaps good approximations to base representation vectors of p and q could be obtained by forming p' and q' from disjoint covering subsets of F. The choice of k determines how expressive F is in being able construct varied factors of about equal size to p and q. It is unclear both if p' and q' would be good approximations to p and q even if they were of similar size and m were small, and even if they were good approximations, the algorithm appears more of a one-shot, and not amenable to iterative betterment of that guess. This is accounting for the idea of 'randomly modifying' parts of the guess p' and q' to then give an m' < m, with the same k-smooth property, and beginning the search for selections of disjoint covering subsets of F nearby to p' and q'. It is unclear whether m' could be easily found, also if the algorithm would get stuck in a local optima, removed from p and q. Which makes it seem quite unworkable.

Edit: it is incorrect to say optimal substructure is a meaningless term since it has both a generally accepted meaning (in computer science referring to problems by which larger instances are amenable to solution using the solution of smaller instances) and also a derivable meaning in that if one considers the possible meanings of "optimal" and "substructure" put together one arrives at a conclusion that such a concatenation is likely to refer to the state of having a substructure which is in some way optimal. In the context of the solution of problems, the intended meaning naturally follows. Maybe Raphael simply doesn't like the question or the answer or both, because they're so meaningful!

No.  There's no known optimal substructure like that.  Such a substructure would naturally lead to algorithms for factoring large composite numbers, which is a notoriously hard problem.  For numbers that are products of two primes, there is no known optimal substructure; these are the kinds of numbers that are used in the RSA cryptosystem, and factoring them has been studied in great depth in the literature.  However, the best factoring algorithms known don't use optimal substructure; instead, they use other number-theoretic ideas.

Another way to put it: recursion does not seem like a useful approach to factoring products of two primes efficiently.  The natural way to recurse is to find a divisor $d$ of $n$, then recurse on $d$ and $n/d$; but that's a chicken-and-egg problem, because finding a divisor of $n$ is exactly the problem that's hard.  For instance, when $n$ is a product of two primes, factoring is the problem of finding a (non-trivial) divisor of $n$.  So, the problem is that, to figure out what to recurse on, you first need to solve the problem itself.  My thanks to @Raphael for this helpful way of thinking about things.


proof that BFS remains total after adding edge to graph I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).

The inductive proof consists in 2 cases:

(i) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u,v \in G$

(ii) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u \in G, v \not\in G$

I'm stuck at (i).

If I add a new edge $(u,v)$ to $G$, the $BFS$ will remain the same until it reaches $u$ or $v$, then it will add $v$ or $u$ to the queue (where one of them wouldn't be there). I understand that every other member of the queue is there, but there will be one more, so ignoring the fact that there is a new vertex in the queue, the $BFS$ will run in every other vertex just like it should.

How can I show formally that this new vertex in the queue will not interfere in the fact that the $BFS$ is total?

Let us assume that $G$ is a connected undirected finite graph.

Instead of by induction, a direct proof by contradiction as the following is probably easier and clearer.

Suppose we have just finished a BFS starting at vertex $s$. For the sake of contradiction, let us assume that there is a vertex $u$ of $G$ that is unvisited. Because $G$ is connected, there is a path from $s$ to $u$. Select the first unvisited vertex on that path and name it $u'$ (which may or may not be $u$). Let $s'$ be the vertex right before $u'$ on that path (which may or may not be $s$). Then $s'$ must be visited.

Now take a moment to reflect on BFS. Whenever a vertex is visited, each of it adjacent vertices must have been visited earlier or later; I will let you prove this proposition rigorously. However, this contradicts that $s'$, a visited vertex is adjacent to $u'$, an unvisited vertex. Our proof is done.

Here is the summary of the proof strategy. A subset of vertices of a connected graph that is closed under adjacency must contain all vertices. This also holds for infinite graphs.


What is the state of the art in encapsulated search in functional logic programming? I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation.

According to [1], encapsulated search in PAKCS depends on the order of evaluation, while in MCC, it does not, but using it requires knowledge of the compiler implementation and it does not follow the Curry language specification. This was written in 2007, so it may of course be out of date now.

KiCS2 returns results from encapsulated search in the IO monad, but I do not understand why.

[1] Braßel and Huch, On a Tighter Integration of
Functional and Logic Programming, Proc. APLAS 2007

The reasons for using the IO monad appear to be described in Braßel and Huch and Hanus, 2004, but I cannot find a clear reason given for using a list instead of a set. I guess it is so the list can be elaborated lazily.

It seems that the approach described in the 2007 paper was unsatisfactory for some reason (I don't know why), because KiCS2 has gone back to the "API" described in the 2004 paper, i.e. using the IO monad. (There is an unsafe version which does not use the IO monad, but that is not referentially transparent!)


Minimum absolute value of subset sums of integer values $f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\mathbf{POLY}\overset{\Delta}{=}\{ f:\{0,1\}^*\rightarrow \{0,1, \}^* |$ exists polynomial TM which competes $f  \}$

We give a Turing reduction from the $\mathrm{SubsetSum}$ problem.
Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find a set $X \subseteq A$ such that $\sum_{x \in X} x = k$ and define the set $A' = A \cup \{- k\}$.
We want to show that $f(A') = 0$ if and only if $(A, k) \in \mathrm{SubsetSum}$:

Suppose that $(A, k) \in \mathrm{SubsetSum}$. Then there exists a set $X \subseteq A$ such that $\sum_{x \in X} x = k$, i.e. the sum over the elements of $X \cup \{-k\} \subseteq A'$ is $0$, implying $f(A') = 0$.
Otherwise, we have $(A, k) \notin \mathrm{SubsetSum}$. As $A$ only contains positive integers but no subset of $A$ sums to $k$ we infer that any subset of $A'$ sums to some nonzero value.

It follows that if $f$ is computable by some polynomial time DTM then $\mathrm{SubsetSum}$ can in turn be decided in polynomial time, showing that $\mathsf P = \mathsf{NP}$.


Is $(a+b)^*$ closed under reversal? If you have a language $L_1 = \{ w | w \in \{a,b\}^* \}$. Then does the language $L_1^R$ (the reversal of $L_1$) have the exact same elements as the language $L_1$?

My Logic: Since $L_1$ can contain a string as well as the reversal of the string (ex. $L_1 = \{ababba, abbaba\}$), then $L_1^R$, over the same alphabet, can contain the same strings as what $L_1$ has (ex. $L_1^R = \{abbaba, ababba\}$ which is equivalent to $L_1$)?

Am I looking at this correctly?

If an arbitrary language $L$ is closed under reversal ($L=L^R$), then $L^*$ is also closed under reversal, since

$$
\begin{array}{ll}
  L^R &= \{ w_1 \ldots w_n \ |\ \forall i.\ w_i \in L \}^R \\
      &= \{ (w_1 \ldots w_n)^R \ |\ \forall i.\ w_i \in L \} \\
      &= \{ w_n^R \ldots w_1^R \ |\ \forall i.\ w_i \in L \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i^R \in L \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i \in L^R \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i \in L \} \\
\end{array}
$$

So, being $\{a,b\}$ trivially closed under reversal (provided $a,b$ are letters, not words), $\{a,b\}^*$ is such.


Automatic speech correction When we are trying to learn a new language without any help from native speakers, the first thing we need is something/someone to correct our grammatical mistakes/improper word selection.

So is there any research done on building tools to help critique our spoken language? I often hear people saying that the more you try to speak, the better you get, so I'm wondering if automated tools could help provide feedback on our attempts at speaking in the new language.

This is part of the field called CALLS, or computer-assisted language learning.

It is an interesting subject, and the straight-forward approach would be to first do speech-recognition, then use NLP to find errors, and notify the user. Interestingly, I would think that any good speech recognition software would have to use NLP to disambiguate the speech (and possibly use NLP in additional ways).

So it is sort of a catch-22: in order to recognize the speech, some sort of assumption that the user is using (mostly) correct langauge is made, and therefore NLP can be used to assist the speech recognizer. But in this case, you have to be much much more sensitive to the user using incorrect language. So I think a different approach is necessary, where you integrate the "incorrectness detector" directly into the speech recognition somehow.

Or, perhaps use statistical/machine learning methods entirely (or a combination); ie. train the machine on data of non-native language speakers, and use a learning algorithm to teach the machine what mistakes commonly happen. I am unsure how feedback would work here though.

More info, on non-native pronunciation error detection and feedback:

Rosetta Stone can evaluate pronunciation
Byki (the paid version gives feedback on pronunciation, I don't know how it works though)
Automatic Pronunciation Evaluation And Mispronunciation Detection Using CMUSphinx

Basically, research into exactly what you are asking, via speech recognition software method, I wrote about above.
EduSpeak®: A speech recognition and pronunciation scoring toolkit for computer-aided language learning applications (paywalled)

Machine learning approaches:

A new method for mispronunciation detection using Support Vector Machine based on Pronunciation Space Models
Automatic Error Detection for Unit Selection Speech Synthesis
Using Log Likelihood Ratio based SVM Classiﬁer
Mispronunciation Detection via Dynamic Time Warping on Deep Belief Network-Based Posteriorgrams

This is all mostly about pronunciation. For grammar, you can tack on something to speech recognition, using NLP. The same caveats apply to grammatical error detection as to pronunciation; NLP would normally likely be used as part of speech recognition, so the error detector would likely have to be integrated directly into the speech recognition software.

More info on non-native grammatical error detection and feedback:

Presentation: The Computer and Natural Language. Special Topic: Grammatical Error Detection
An Analysis of Grammatical Errors in Non-native Speech in English


Pick parameter function that minimises whole function I have a recursive algorithm defined by the following recursion.

$$T(n) = T(n/f(n)) + O(\log f(n)).$$

I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = \Theta(\log n)$. If $f = O(n)$ then $T(n) = \Theta(\log n)$. Is this true for all functions $f$ that $T(n) = \Omega(\log n)$ or can I get asymptotically better behaviour for some $f$? The reason I think there might be is that you can look at an extended binary search where you split your domain into $f(n)$ sections and then examine each section to see if your value is in that section. This recursion can be presented as follows:

$$T(n) = T(n/f(n)) + O(f(n)).$$

Binary search clearly runs in logarithmic time or worse for all values of $f$. This is the same as my recursion except that it is linear in $f$ instead of logarithmic. So you might expect better behaviour.

This is probably not possible. Let $n_1,\ldots,n_k$ be the sequence of $n$s encountered in the recurrence, starting with $n_1 = n$. Using the concavity of $\log$ (and eliminating the big $O$), we get that
$$ T(n) \geq k \log \frac{f(n_1) + \cdots + f(n_k)}{k}. $$
Assuming $f$ is monotone, we have $k \geq \log n_1/\log (n_1/n_2) = \log n/\log f(n)$. This monotonicity also shows that $n_{(k+1)/2} \geq \sqrt{n}$. Therefore
$$ T(n) \geq \log n \frac{\log f(\sqrt{n}) - 1}{\log f(n)}. $$
For all $f(n)$ I can think of, $\log f(\sqrt{n})/\log f(n) = \Theta(1)$, so they can't give you anything better than $\log n$. This also says that if you're looking for a monotone $f$ which beats $\log n$, then it must satisfy $\log f(\sqrt{n}) = o(\log f(n))$.


Number of ways painting graph in two colors, such that two nodes of same color are linked by edge We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must be an edge between them.

I tried some examples on paper and I always got numbers of the form $2^x$, however I couldn't see a valid way to find such $x$ or I couldn't prove why this is the case.

Does this problem become easier if we are given directed acyclic graph instead of undirected one?

Call a coloring where two nodes of same color must be linked by an edge (a.k.a. adjacent) attractive-coloring. The more common node coloring, where no two adjacent nodes are of the same color will be called repulsive-coloring.

Let $G$ be a given graph and $G'$ be the complement graph of $G$, i.e., $G'$ and $G$ are on the same nodes such that two distinct nodes of $G'$ are adjacent if and only if they are not adjacent in $G$.

An attractive-coloring of $G$ is an repulsive-coloring of $G'$ and vise versa. So the number of attractive-2-colorings of $G$ is the number of repulsive-2-colorings of $G'$. Note that a 1-coloring is considered a 2-coloring.

A graph can have a repulsive-2-coloring if and only if it is a bipartite graph. A connected bipartite graph has exactly two repulsive-2-coloring, i.e., assuming the two colors are red and black, we can color all nodes in one group red and all nodes in the other group black or the other way around.

Suppose the connected components of $G'$ are $C_1, C_2, \cdots, C_k$. If one of them is not bipartite, then there is no repulsive-2-coloring for that component and hence no repulsive-2-coloring for $G'$. If all of them are bipartite, then there are two repulsive-2-colorings for each of them and hence $2^k$ repulsive-2-colorings of $G'$.

Exercise (the well-known theorem on 2-colorable graphs). The (repulsively-)2-colorable graphs are exactly the bipartite graphs.


After how many iterations will an integer circle back to 0 in Python? If this question is completely garbage I apologize because I am new to CS and haven't understood at how programming languages (Python specifically) work.

I was reading about how in a standard two-byte representation of a number, if one was to increment 65,536 times, the integer would wrap back to one. Would this case occur in Python, and if so at what number would this occur?

Edit: I read a little bit further into this and it seems that after an increment, programming languages seem to redefine the value. Would this prevent this from occur

Your question is about python, but let me make it more general. Integers are represented in three major ways in modern computers:

Unsigned integers of a fixed number of bits.
Signed integers of a fixed number of bits.
Bignums, also known by various other names such as multiple precision integers.

The first two exhibit the wrap-around behavior. The third doesn't.

Python uses three different representations for integers:

Small integers are stored as "constants".
Integers which fit into a signed machine word (plain integers) are stored as such.
Larger integers (long integers) are stored as bignums.

This is described in the python documentation.

Plain integers are automatically promoted to long integers if need be. Therefore the wrapping around behavior does not happen.

On a 64-bit system, $2^{63}-1$ is the largest plain integer:

>>> (2**62-1)*2+1
9223372036854775807
>>> 2**63
9223372036854775808L

Note the suffix L, which indicates a long integer.


Is it possible to ever define $L(M)$ of a given Turing Machine, $M$? In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in \{0,1\}^*\}$. However, we proceeded to discuss when a language is recursively enumerable vs machines that are deciders etc, and then started discussing the halting problem.

My question is : given a Turing Machine $M$, is it undecidable to construct its Language $L(M)$, since theoretically there could be an input that never reaches a reject or accept state? (My intuition tells me this reduces to the halting problem).

EDIT

If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts (see @d'alar'cop's comment)?

In answer to your edited question,

  If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts?

The answer is yes, we can. In technical terms, this asks whether the language accepted by a TM is recursively enumerable.

Here's how to produce the strings that $M$ accepts. Define an enumerator TM, $E$ that acts as follows:

Startup: decide on an enumeration of all possible input strings, $s_1, s_2, \dotsc$. For example, if the input alphabet was $\{0, 1\}$ the strings might be enumerated in order $\epsilon, 0, 1, 00, 01, 10, 11, \dotsc$. It's not hard to see how this could be accomplished. In particular, we could find, for every string $s_i$, the next string in order, $s_{i+1}$.
Then use what's known as a dovetail construction in your enumerator TM $E$:
$$\begin{align}
&\text{repeat for } i = 1, 2, \dotsc \\
&\quad\text{for } k = 1, 2, \dotsc , i\\
&\quad\quad\text{simulate }M\text{ on } s_k\text{ for } i\text{ moves}\\
&\quad\quad\quad\text{if } M(s_k)\text{ accepts}\\
&\quad\quad\quad\quad\text{output } s_k
\end{align}$$

It's not hard to see that every string $s_i$ accepted by $M$ will eventually be displayed (perhaps several times) by the enumerator TM $E$. In effect, we're running $M$ in (simulated) parallel on all possible strings $s_i$. Of course, the enumerator $E$ will run forever, but while it's running it will eventually produce any string in $L(M)$ in a finite time, which is just what you wanted.


2CNF with 3 variable occurences If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable?

Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one variable (2 per positive and negative occurences).

So, is it even possible?

The following is unsatisfiable:
$$
(x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor z) \land (\lnot z \lor w) \land (\lnot z \lor \lnot w) \land (y \lor w).
$$
This contains every variable exactly three times, not all of them of the same polarity. If you allow variables to appear less than three times, you can drop the last clause $y \lor w$.


find the union of all min cuts of a flow network I'm trying to solve the following question :

  Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and unions, i.e. for every $ S_1,S_2\in\mathcal F , S_1 \cup S_2 \in \mathcal F$  and $ S_1 \cap S_2 \in \mathcal F $.

that part I took care of just fine using the min-cut-max-flow theorem.

the other part is the one that I had trouble with :

  Given a max flow $ f $,find $S_{\min} = \bigcap_{S\in\mathcal F} S \text{ and } S_{\max} = \bigcup_{S\in\mathcal F } S $.

I realized that when considering a min cut $(S,T)$ , and given the residual graph (which can be built from the given maximum flow) , every vertex that's reachable from $s$ (source node) , must be in $S$ , so I was able to use that to come up with an algorithm to find $S_{\min}$.

But as for finding an algorithm for $S_{\max}$, I'm kinda having trouble putting my finger on a property of a min cut edge, i.e. what does it take to be a cut edge (or for a vertex to be in $S$) of some min cut?

I'm not looking for the full answer but rather a hint.. any help is appreciated.

Note $S_{\max}=V-\bigcap_{S\in\mathcal{F}}(V-S)$. And $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph.

The reason why $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph is the same as the reason why $S_{\min}$ is the set of all vertices that are reachable from $s$. You can prove this using the complementary slackness conditions.


Longest path in a graph with special property I have a special graph in which I have two types of edges only, say one with type 0 and one with type 1. Now I have to find a longest path in the graph such that it starts with a vertex then follows as many type 0 edges as it can and then again start with a vertex and follows as many type 1 edges it can. The length of the longest path will be number of distinct vertices in both the paths. (If some vertex coincide count it once.)

Note : The graph is undirected, heavily contains cycles and has upto 10^6 vertices. So I would need a O(n) algorithm.

P.S : Sorry forgot to give the more important information, for every vertex there are 0 or 2 edges of each type always.

As Raphael pointed out, this problem is also NP-complete. There is an easy reduction from longest path problem to this problem. Just take the graph of longest path problem and label all of the edges type-0. There won't be any type-1 edge. This labeled graph will have a longest path of length $k$ iff original graph has a longest path of length $k$.

This proves the NP-hardness of the problem.

It is easy to see that the problem is in NP, the NDTM machine for the problem will be similar to the longest path problem. Both this add to make the problem NP-complete.

But if you are happy with any kind of approximation, then you can refer Approximation to longest path and modify the algorithm to suit your purpose. However be prepared that the modification may not be trivial.


Guess the number from its different base representations Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or return no number exists.

Constraints given: $2\leq base \leq 36$, No. of numbers given in different representations is N $\le$ 100, Test Cases $\leq$200, time Limit 1sec

For example,

Here $T=1,N=3$,

$1001111$

$117$

$4F$

These all represent the same number, i.e $(79)_{10}$. $(1001111)_3$ = $(117)_8$=$(4F)_{16}$ Hence answer is $79$. Whereas if any of the above number is changed to any other except those (for eg. if (1001111) is changed to something else) then the answer would be "No such number exist".

Please suggest an Efficient way with a pseudo code/code.

Let's start with a simple algorithm. Go over all possible interpretations of the first string (using all possible bases). For each such interpretation, go over the remaining string, and check whether they equal the interpretation of the first string for one of the possible bases. If there are $m$ possible bases and $n$ digits in total, then the running time is $O(m^2 n)$, ignoring the cost of arithmetic.

We can improve this as follows. Suppose for simplicity that all strings are at least two digits long (if not, we know the value of the number, and can finish in $O(nm)$ time). Compute all possible interpretations for each string, put all of these $nm$ numbers together, and sort them. Check whether the sorted list contain $n$ identical elements. This algorithm takes $O(nm \log (nm))$ time.

Another improvement, with a slightly better running time, modifies the original approach using binary search. Go over all possible interpretations of the first string. For each such interpretation, go over the remaining string, and for each one, use binary search (on the base) to find whether they equal the interpretation of the first string for one of the possible bases. This algorithm runs in $O(nm \log m)$ time.


If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$ The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{coNP}$.

My main idea is to prove that $L$ is also $\mathrm{NP}$-complete (or rather $\mathrm{NP}$-hard, as it is in $\mathrm{NP}$), but I don't really see a possibility to prove this, as it is not sufficient that a subset of $\mathrm{NP}$ is reducible to $L$; thus I would be very thankful for some idea for a proof.

Addendum 1:

I am aware of if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$, but in this source only the obvious implication is proven.

Addendum 2 - My proof of the first subset-relation:

All languages $K\in\mathrm{coNP}$ are reducible to the $\mathrm{coNP}$-complete language $L$, thus if $L\in\mathrm{NP}$ every $K$ is reducible to a language in $\mathrm{NP}$ and the implication $K\in\mathrm{coNP}\Rightarrow K\in\mathrm{NP}$, and thus $\mathrm{coNP}\subset\mathrm{NP}$, holds.

$\newcommand{\co}{\mathsf{co}\text{-}}$

Let $A\subseteq \Sigma^*$ be some class of languages. Saying $\co{A}\subseteq A$ means that $A$ is closed under complement, and this is equivalent to $\co{A}=A$.

To show the other direction, $A\subseteq \co{A}$, let $L\in A$ be some language in the class $A$. $\overline{L}\in \co{A}$, and since we know $\co{A}\subseteq A$, we have $\overline{L}\in A$, which means $L\in \co{A}$.


How to create this pushdown transducer? (formal languages and automata) Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$.
How should I use the stack to remember or to compute how many characters of c to read? And how can I output $b^{n-m}$?

I have also tried to simplify the problem and firstly create a pushdown automata for $a^m b^{2m}c^m$, but I didn't succeed.

Thank you!

It is no surprise you could not create that PDA: the language $\{a^m b^{2m}c^m\mid m\geq 0\}$ is not CF. The same is true of $\{a^m b^{2m}c^{m+n}\mid n\geq m\geq 0\}$. You may try to prove it.

Hence, I suspect that the pushdown transducer is not supposed to recognize the input string but assumes it is well formed, and simply has to translate correctly when it is.

So I would simply use the pushdown stack of the transducer to collect the information to be found in the input (supposed to be well formed) to produce the correct output, without worrying about acceptance. You do not care what happens when the input string is not well formed.  It is actually quite simple to produce $b^{n-m}$


Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests? Since you are free to chose any formula for the SAT problem, doesn't the choice of a formula that requires a test for each subset of the group of variables force it to perform $2^N$, essentially making SAT unsolvable in polynomial time in respect to the number of variables on the input?

When talking about the complexity of SAT, we usually care only about the complexity in terms of input size. This is because the classes P and NP are defined this way: they are oblivious to what the input represents. Your formula, while depending on a small number of variables, will be very long.

3SAT is nicer in this regard, since assuming clauses don't repeat and every variable appears at least once, the number of variables, the number of clauses, and the bitlength of the input are all polynomially related, so from the point of view of complexity theory, any of them could serve as the parameter against which complexity is measured.

Moreover, I don't see why any particular choice of formula would "require a test for each subset of the group of variables". We don't know how to substantiate claims of this sort in the case of SAT.


Finding the equivalence classes of a language I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language
$$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$

The best way I've learned to find the equivalence classes from a formal language is to create an automation and minimize it. Is there a conventional way of finding the equivalence classes of a language more quickly and intuitively? Because I do not know the DFA for this problem. Thanks for the help!

Your language is $01^*0(0+1)^*$, i.e., all words starting with 0 and containing at least one more 0.

Indeed, a word of the form $0y0z$ is in $A$ since we can take $n=1$ and $x = y0z$. Conversely, if $w = 0^nx \in A$ then $w$ contains at least $2n \geq 2$ many 0's, and starts with a 0.

Therefore the Myhill–Nerode equivalence classes of your language are:
$$
\epsilon, 1(0+1)^*, 01^*, 01^*0(0+1)^*.
$$


How do I model line comments in a CFG? Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. How to express that in a context free grammar?

Without multi-line statements, it's rather simple; assuming line is the non-terminal for well-formed line, change its right-hand-side appearances to

line (# .*)?

(borrowing regular expression syntax for brevity).

Otherwise, if you explicitly handle line breaks, replace occurrences of the line-break token CRLF (or so) similarly by

(# .*)? CRLF

If line breaks remain implicit, one chance you have left is make it part of the lexer; don't only skip whitepace, but also (# .*)? [\r\n]. You can also create a token COMMENT for that and place it in all places of the grammar where it may appear. This strategy doesn't work for nested multiline comments, though, a common problem in older languages.


Do the "virtual memory"s mentioned in the 2 articles refer to different things? I've read the following 2 articles explaining the difference between virtual memory and physical memory. One thing that I found confusing is that the term virtual memory seems to mean different things in these 2 articles.

What Is the Difference Between Virtual Memory & Physical Memory? says Virtual memory is used when the RAM is filled.

While Wikipedia says virtual memory is used to tell programs where the physical memory is.

Is one of the articles wrong? Or does virtual memory have different meaning in different context?

That first link is bogus.   I can see where they're getting that misconception from, but it's not actually correct.


How does MIPS ( or any other multi-byte word arch ) fetch a word? I've recently been studying MIPS as part of a CS course, but something bugs me.
We've seen so far that MIPS increments the PC by 4 each cycle because each word is in fact comprised of 4 bytes (32 bits), each with their own address.
I've also seen that a theoretical RISC machine has instructions that should only take a single cycle to execute.

Ignoring memory latency, how does it manage to generate an address for each 4 bytes?
It can't have four adders for memory address calculation right? That'd be too expensive! Or am I incorrect in this assumption?
I've also seen other architectures that manage to pull multiple bytes from memory (even multiple words) in a single step/cycle/instruction, but how is this achieved if each byte needs an address?

MIPS can load a 32-bit (4-byte) word in a single instruction (load word, LW). The fact that each byte of the word is individually addressable doesn't affect this.  Effectively, the instruction says "Read the four bytes beginning at this address", not "Read the byte at this address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address."

By way of an analogy, you can photocopy any two facing pages of a book simultaneously, even though each has its own number.


DFA: Can the set of States Q be empty by definition? Can the set of states Q be empty by definition?

I was wondering about this question when doing exercises in the pumping lemma for finite automaton.

In a DFA - no, because the definition includes a single initial state $q_0$, which means that $q_0\in Q$, and therefore $Q\neq \emptyset$.

In an NFA, however, this is indeed possible.


Is there an O(n log n) algorithm for 4D line simplification? The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are other algorithms with worst case $O(n \log n)$ runtime complexity, which compute exactly the same result as the Ramer-Douglas-Peucker algorithm. Since these algorithms are based on a "path (convex) hull" datastructure, it is not obvious whether they can be generalized to 4D lines.

Is there a (randomized) algorithm which has (expected) $O(n \log n)$ runtime (independent of input) for the case of 4D lines? You may assume Euclidean distances and a global absolute tolerance.

The algorithm that works with 4D case is described in the article Near-Linear Time Approximation Algorithms for Curve Simplification by four authors: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang.

  Given a polygonal curve $P$ in $\mathcal R^d$
  and a parameter $\epsilon \ge 0$, an $\epsilon$-simplification of
  $P$ with size at most $\mathcal \kappa_F(\epsilon/2, P)$
  can be constructed in $\mathcal O(n\log n)$ time and $\mathcal O(n) $ space.

The algorithm does not depend on monotonicity properties. It covers the original line with disks and seeks the line traversal on the ordered set.

Sidenote:
There is a modification of Douglas-Peucker algorithm with the worst-case in $\mathcal O(n\log n)$ described in the paper An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification. by John Hershberger and Jack Snoeyink: improved DP line simplification. Indeed it uses path hull.


"Visited" vs "Seen" Positions in Breadth-First Search I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid.

In the Python program below, uncommenting the indicated lines switches between versions.

As well as help with understanding the difference, I would like to know if there is a "canonical" version which is considered best practice. Clearly here the second version performs best, but it is a also different to most of the statements of the algorithm I have found, which add the current node to a "visited" list straight after dequeuing.

BFS Algorithm

These versions store the whole path at each stage in the queue.

Version 1

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
    dequeue the next path
    name the last element frontier
    add the frontier to a set of visited positions
    check if the frontier is the goal position
        if so, return the path
    otherwise, check neighbouring cells:
        if the cell is legal and is not in the set of visited positions,
             enqueue a new path consisting of the current path + this new cell
if no successful path was found, return None

Version 2

Enqueue a list containing the start position, as the initial path.
while the queue has elements in it:
    dequeue the next path
    name the last element frontier
    check if the frontier is the goal position
        if so, return the path
    otherwise, check neighbouring cells:
        if the cell is legal and is not in the set of previously seen cells,
             enqueue a new path consisting of the current path + this new cell
             add the current cell to a set of previously seen cells.
if no successful path was found, return None

import collections

offsets = {
    "up": (-1, 0),
    "right": (0, 1),
    "down": (1, 0),
    "left": (0, -1)
}

def is_legal_position(maze, pos):
    i, j = pos
    num_rows = len(maze)
    num_cols = len(maze[0])
    return 0 <= i < num_rows and 0 <= j < num_cols

def bfs(grid, start, end):
    """
    Bread-First Search in a 2d list. Stores whole paths in queue.
    """
    queue = collections.deque([[start]])
    seen_or_visited = set()

    while queue:
        print("####### While queue is not empty #########")
        path = queue.popleft()
        print("Path", path)
        frontier = path[-1]
        print("Frontier:", frontier)
        seen_or_visited.add(frontier) # Uncomment for version (1)
        if frontier == end:
            return path
        enqueued_this_round = []
        for direction in ["up", "right", "down", "left"]:
            print("### Direction: ", direction)
            row_offset, col_offset = offsets[direction]
            next_pos = (frontier[0] + row_offset, frontier[1] + col_offset)
            if is_legal_position(grid, next_pos) and next_pos not in seen_or_visited:
                print("Enqueueing", next_pos)
                queue.append(path + [next_pos])
                # seen_or_visited.add(next_pos) # Uncomment for version (2)
                enqueued_this_round.append(next_pos)
        print("seen_or_visited:", seen_or_visited, "\n")
        print("Enqueued this round", enqueued_this_round, "\n")

maze = [[0] * 5 for row in range(5)]
start_pos = (4, 4)
end_pos = (0, 0)
print(bfs(maze, start_pos, end_pos))
```

I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks.

For that, do the following:

Comment out all print lines except print("Frontier:", frontier)
Then do python program.py > version1.txt, modify your program such that it represents verison 2, and then do python program.py > version2.txt.
Get pen & paper and draw a 4 × 4 table.

Here is a comparison of the first lines of both log files:

    Version 1           Version 2

Frontier: (4, 4)     Frontier: (4, 4)
Frontier: (3, 4)     Frontier: (3, 4)
Frontier: (4, 3)     Frontier: (3, 4)
Frontier: (2, 4)     Frontier: (4, 3)
Frontier: (3, 3)     Frontier: (2, 4)
Frontier: (3, 3)     Frontier: (4, 4)
Frontier: (4, 2)     Frontier: (3, 3)

I leave it as an exercise for you to draw this with pen & paper. Can you take it from here?

Note that the duplicate (3, 4) is version 2 is suspicious. Can you guess where it comes from?

  I would like to know if there is a "canonical" version which is considered best practice.

You typically want the invariant that everything in the queue is already put in the seen queue. As a formula, this amounts to saying $$\text{work queue}\ \subseteq\ \text{seen queue}.$$

Otherwise, you could pick the tip of the work queue, say item $i_1$, go through its neighbors to then add its neighbor $i_2$ to the work queue. However, $i_2$ was already part of the work queue before (perhaps just after $i_1$!), but you couldn't know since you didn't keep the seen queue synchronized.

Hence, implementing this invariant amounts in your code to

putting start onto the seen queue

queue = collections.deque([[start]])
seen_or_visited = set([start])

choosing version 2, i.e.

seen_or_visited.add(next_pos) # Uncomment for version (2)

You may also want to comment out version 1, i.e.

#seen_or_visited.add(frontier) # Uncomment for version (1)

since the invariant, fulfilled by the two points above, guarantees that whatever you pick from the queue (here, frontier) has already been added to the seen queue.

By the way, your function is missing a return None in case it doesn't find the target position.


Prime attribute dependant on another prime attribute allowed under BCNF? I have been studying DBMS ans I have a question that I got conflicting answers to:
Is prime attribute that is dependant on another prime attribute allowed under BCNF?

Meaning P->P.

I know that NP->P is not allowed.
and also NP->NP (as it is not 3NF - transitive relation)
Thanks.

By definition, a relation is in BCNF if and only if, for every non trivial functional dependency, the left hand part is a candidate key.

So, if you have a dependency A → B where both A and B are prime attributes, this dependency violates the Normal Form only if A is not a candidate key, but a part of some candidate key.

Note that in that case, the dependency does not violates the 3NF.


What is the largest possible minimal 3CNF formula as function of the number of variables? I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it $O(n)$? Is it $O(log(n))$? Is it $O(1)$, but just larger than 8?

Chungboom Lee, On the size of minimal unsatisfiable formulas shows that when $k=2$, the answer is $\Theta(n)$, and when $k \geq 3$, the answer is $\Theta(n^k)$. Here $k$ is width of the clauses.


How to detect "tree-able" set-families? A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family corresponds to a path from the root to a leaf. For example, the following family is treeable:
{ {1, 2, 6}, {1, 3, 4, 5, 6} }

A possible tree is:
1 -> 6 -> 2
     |
     + -> 3 -> 4 -> 5

However, the following family is not treeable:
{ {0, 1, 2}, {0, 2, 3}, {0, 3, 1} }

Is it possible to decide in polynomial time whether a given set-family is treeable (and construct a tree)?

An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process.
Let's consider the set of sets $A$ as a list $A[i]$.
The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s_0$. And you keep a set $D$ of all indexes you already encoutered.
Then, we loop on other sets to add their information to the set tree. We consider the vertices of the tree starting from the root and adding new vertices when necessary.
let s define a function compare($s$, $v$) with $s$ a set and $v$, the set associated to a vertex of $G$.

if $s == v$ then return true

$c = s \cap v$

if $c == v$ then

for $v_s$ in sons(v) if compare(s-c, $v_s$) then return true
if $s-c \cap D$ is not empty then return false
create a new son to $v$, $v_s$ associated to set $s-c$ and return True

in $G$, develop vertex $v$ to $v_1$ and $v_2$ associated respectively to sets $c$ and $v-c$, return compare($s$, $v_1$)

Thus, the main loop is:

$root = A[0]$
$D = A[0]$
for $s$ in $A[1:]$

if compare(s, root) then $D = D \cup s$
else return false

return true

When reaching the $i^{th}$ set, $G$ contains at most $i-1$ vertices, and you will recursively call the compare function up to $i-1$ times. Thus for $N$ sets covering $L$ different indexes (thus the set operations are $O(L)$), this algorithm solves the problem in $O(L N^2)$
An exemple:
$A = [\{1, 3, 5\}, \{1, 2, 3, 4\}, \{ 1, 2, 3, 6\}, \{1, 2, 3, 5, 7\}]$
the initial tree $T$ has one vertex associated to the set $A[0] = \{1, 3, 5\}$
{1, 3, 5}

then you treat $A[1] = \{1, 2, 3, 4\}$, the root vertex has to be developed in
{1, 3} - {5}

to finally add a $\{2, 4\}$ son vertex to the root:
{1, 3} - {5}
|
{2, 4}

then comes $A[2] = \{ 1, 2, 3, 6\}$, after root, it remains $s = \{2, 6\}$. On $\{5\}$ child, there is no possibility as 2 is already in $D$. But on $\{2, 4\}$ child, it works after developing it.
{1, 3} - {5}
|
{2} - {4}
|
{6}

Finally comes $A[3] = \{1, 2, 3, 5, 7\}$, that will not work as 2 and 5 are both in $D$ and in different branches of $T$.


What's the meaning of this service specification What's the meaning of the example statement here?

"A service specification S describes an interface: it specifies the behavior of certain program elements (functions or subprograms) through statements expressed in program logic. For instance, these might be such statements:

[...]
x, y : N[{x>0} y := x * x {y > x}]

"

The quote is from the article  "On The Hourglass Model"
By Micah Beck,
Communications of the ACM, July 2019, Vol. 62 No. 7, Pages 48-57

That means:

For all natural numbers x and y,

if the value of variable x is greater than zero
then after the assignment statement "y := x*x" is executed
the predicate "y > x" will be true.


What to do with empty set during NFA to DFA conversion? I am currently converting this NFA to a DFA

I have come up with the following DFA:

        0      1
->A    {A}    {B}
  B    {CA}
*CA    {A}    {AB}
 AB    {CA}   {B}

Although, I have no idea what to put for B. In the NFA, upon the B receiving 1 input, it goes nowhere - assumable unaccepted by the NFA. Do I send the DFA to a new, dead state upon receiving input 1 whilst in B?

I can try it:

        0      1
->A    {A}    {B}
  B    {CA}   {}
*CA    {A}    {AB}
 AB    {CA}   {B}
 {}    {}     {}

But is this correct by the rules of DFA?

Creating a new sink state is perfectly fine. The empty set is also a subset of all states.

In most DFA diagrams this state is omitted for simplicity.


Seems like NP cannot equal coNP by the definition of NP A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will generally be an intractable number of possibilities. How can it be possible to deterministically verify the no answer  for all possibilities in polynomial time?

As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?

This kind of argument presupposes that the only way to (for example) prove that a SUBSET-SUM instance is not solvable is by going over all subsets and checking that their sum doesn't match. This isn't true — a meet-in-the-middle algorithm works in time $O(\sqrt{2}^n)$ rather than $O(2^n)$, where $n$ is the number of sets.

Furthermore, consider the analog of this question for polynomial space rather than time. In this case it does hold that NPSPACE=coNPSPACE, for the simple reason that PSPACE=NPSPACE.


Partition array into K subsets, each with balanced sum Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that

$A'_{1} = \{a_{1}, ...,a_{x}\}$

$A'_{2} = \{a_{x+1},...,a_{y}\}$

$...$

$A'_{k} = \{a_{z+1},...,a_{n}\}$

where each subarray $A'_{1},A'_{2}, ...,A'_{k}$ has sum of its elements closest to $\sigma; \sigma = \frac{\sum_{i = 1}^{n} {a_{i}}}{k}$

Example:  $A = \{{5,6,1,3,4,10\}}, k = 3$

$\sigma = \frac{29}{3} = 9.\overline{66} \approx 10$

Best solution to split array is:

$A'_{1} = \{5,6\}$

$A'_{2} = \{1,3,4\}$

$A'_{3} = \{10\}$

with sums $11, 8, 10$

One way to measure "badness" of each solution, is to define function $h(A_{1},...,A_{k}) = \sum_{i = 1}^{k} {(s_{i} - \sigma)^2}$, where $s_{i}$ is sum of elements of subarray $A_{i}$

Can you point me towards the solution? I've been trying for a few days now, and I'm no closer to an algorithm than I was few days ago.

Use dynamic programming.  This is a straightforward application of dynamic programming.  This is a very nice exercise, so I'll let you do the exercise yourself and won't spoil it for you -- but since you only wanted a hint, my hint is "use dynamic programming" (that's a huge, enormous hint that should be enough for you to work out the rest of the details).

In particular, you should be able to solve this in $O(kn^2)$ time.


Amortized analysis of resizing array implementation of a stack Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne:

  Proposition E. In the resizing array implementation of Stack
  (Algorithm 1.1), the average number of array accesses for any sequence
  of operations starting from an empty data structure is constant in the
  worst case.

  Proof sketch: For each push() that causes the array to grow ( say from
  size N to size 2N), consider the N/2 - 1 push() operations that most
  recently caused the stack size to grow to k, for k from N/2 + 2 to N.
  Averaging the 4N array accesses to grow the array with N/2 array
  accesses (one for each push), we get an average cost of 9 array
  accesses per operation.

It is unclear to me why 4N array accesses are required to grow the array. From my understanding, in the proof they describe the case when the array grows from size N to 2N, and for that it should require only 2N array accesses (copy the first N elements, 2 array accesses per element).

They include the initialization of the new array.
From page 207 of the text:

Q. Does int[] a = new int[N] count as N array accesses (to initialize entries to 0)?
A. Most likely yes, so we make that assumption in this book, though a sophisticated compiler implementation might try to avoid this cost for huge sparse arrays.


Example of a simple recognizable language, whose complement is not recognizable Can any one provide me with a simple language that is recognizable, but that it's complement is not?

I have read that recognizable languages may have this property but I am yet to find an example to think about. If you could provide the recognizable proof for both language and complement I would be very thankful, but just the language itself would be a nice help.

Thank you

The set of recognizable languages whose complement is not recognizable is $RE\setminus R$. This holds since if $L,\overline{L}\in RE$, you can run the machines for $L,\overline{L}$ simultaneously and decide $L$. An example of a language in this set is the famous halting problem.


Quantum algorithms and quantum computation Is my (very high-level) understanding correct here regarding quantum algorithms —

Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ability to have states that are superpositions of $|0\rangle$ and $|1\rangle$.

Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

That is my very high level understanding of what is going on with quantum algorithms. Am I correct, 'sort-of' correct, or way-off? Can someone clarify my understanding?

This is more-or-less a reasonable description of quantum computation. A few remarks are in order:

Regarding "quantum parallelism":

  Quantum computers can process a massive amount of operations in parallel [...]
  Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

This description, as it stands, applies equally well to randomized computation. We don't assume that random bits have any special sort of state-space, of course — we can just flip coins rather than having to carefully manipulate ions, or photons, or what-have-you — but the mathematics behind probability distributions and quantum states are nearly identical. (Try out some computations involving probability vectors some time, replacing the unitary transformations with stochastic transformations.)
Regarding "quantum properties":

  However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too [...] e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

We do increase the probability that we observe a given result — but this is a consequence of the fact that we decrease the probability of seeing unhelpful outcomes. Classical probability distributions "interfere constructively" too, though we just call it cumulated probability — one thing which is special to quantum computation is the fact that destructive interference (partial or total cancelling of amplitudes) occurs.

This can be seen as one of the reasons why quantum computation is more powerful: the existence of amplitudes which would cancel if you simply added them, means that amplitudes sometimes do cancel when the computation calls for transitions involving both of those amplitudes.
This is something which simply doesn't happen with probability distributions — in fact, it doesn't even happen in nondeterministic Turing machines.

The trick, of course, is to find the particular ways in which you can conspire to have unhelpful outcomes partially cancel (or indeed, to determine which outcomes could be helpful to you, in order to arrange for the other outcomes to cancel). Simply recognising that amplitudes can possibly cancel is not in itself enough to figure out how to compute more quickly.
Regarding Shor's algorithm:

  I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

Shor's algorithm is an example of an algorithm which uses the quantum Fourier transform (or QFT), a unitary transformation which broadly speaking is helpful to find/expose periodic patterns. The fact that it can be performed unitarily means that certain simple periodic patterns which would otherwise be difficult to determine in a small number of trial calculations can be quickly discovered by looking at bulk properties.

Using QFTs to expose periodic properties is one particular trick in the bag of quantum algorithms; there are others as well.


Connection between non determinism and LL(1) conflicts I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.

As per my understanding non deterministic context free grammar is a context free grammar in which at some point in time during parsing, multiple actions are allowed. Also I believe non determinism occurs when we have multiple productions in grammar with same prefix of production (right hand side) bodies. Also I know we eliminate non determinism by left factoring grammar.

Wikipedia article says:

We do left factoring to eliminate FIRST-FIRST conflicts. ref
Left recursion is a special case of FIRST-FIRST conflict. ref
Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
Left recursion is eliminated using rule like below ref :
$A\rightarrow A\alpha | \beta $
ios converted to
$A\rightarrow \beta A'$
$A'\rightarrow \alpha A' | \epsilon$

I have following doubts:

Since both non determinism and FIRST-FIRST conflicts are removed with left factoring and since left recursion is special case of FIRST-FIRST conflict, is non determinism a reason behind FIRST-FIRST conflict and left recursion (and also for FIRST-FOLLOW conflict)? If yes, does non determinism cause anything else and there is nothing else apart from these three (FIRST-FIRST conflict, left recursion and FIRST-FOLLOW conflict) in which non determinism manifests?
Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?
I know LL grammar should be both non deterministic and unambiguous. Does ambiguity also manifests in some way in LL parsing table or grammar? I read ambiguity can be eliminated by enforcing association and precedence between grammar symbols and this resolves SHIFT-REDUCE conflicts in LR parsers. Is anything like this required for eliminating ambiguity to make grammar a valid LL grammar?

No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.
Some deterministic grammars -- and even some deterministic context-free languages -- have no $LL$ parser. Such grammars are not necessarily ambiguous. An accurate deterministic parser obviously cannot be generated for an ambiguous grammar, but failure to generate a parser doesn't say anything about ambiguity.
Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.


proof of the rice's theorem Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser's book).
Assume for the sake of contradiction that $P$ is a decidable language satisfying the properties and let $R_P$ be
the TM that decides $P$.
We show how to decide $A_{TM}$ using $R_P$ by constructing TM $S$.
First let $T_∅$ be a
TM that always rejects, so $L(T_∅)$ = ∅.
You may assume that $<T_∅> \notin P$ without loss of generality, because
you could proceed with $\bar{p}$ instead of $P$ if $<T_∅> \in P$.
Because $P$ is not trivial, there exists a TM $T$ with
$<T> \in P$.
Design $S$ to decide $A_{TM}$ using $R_P$ ’s ability to distinguish between $T_∅$ and $T$.
$S = $“On input $<M, w>:$

Use $M$ and $w$ to construct the following TM $M_w$.
$M_w$ = “On input $x:$

Simulate $M$ on $w$. If it halts and rejects, reject. If it accepts,
proceed to stage $2$.
Simulate $T$ on $x$. If it accepts, accept.”

Use TM $R_P$ to determine whether $<M_w> \in P$. If YES, accept. If NO, reject.”

TM $M_w$ simulates $T$ if $M$ accepts $w$. Hence $L(M_w)$ equals $L(T)$ if $M$ accepts $w$ and $∅$ otherwise.
Question:  I'm having trouble understanding the last few lines of this proof. $R_p$ is a decider that decides $p$. It tells us that a  machine has the property $p$ or not. When we run $R_p$ on the description of $M_w$ and suppose $M_w$ accepts $w$ then the language of $M_w$ equals the language $T$ otherwise $\phi$. Now i don't understand how this proves that acceptance problem is also solvable if we have a decide for $P$. I'm stucked at his point , any help would be great.

Let us verify that $S$ is a decider for $A_{\text{TM}} = \{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\}$.

Let $⟨M,w⟩\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

First, construc $M_w$. Since $M$ accepts $w$, $M_w$ simulate $T$.
Use TM $R_P$ to determine whether $⟨M_w⟩ \in P$. Since $M_w$ simulate $T$, $⟨M_w⟩\in P$. So, the answer is YES. So, accept.

Now let $⟨M,w⟩\not\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

First, construc $M_w$. Since $M$ do not accept $w$, $M_w$ simulate $T_\emptyset$.
Use TM $R_P$ to determine whether $⟨M_w⟩ \in P$. Since $M_w$ simulate $T_\emptyset$, $⟨M_w⟩\not\in P$. So, the answer is NO. So, reject.

The above analysis shows that $S$ is a decider for $A_{\text{TM}}$.

Hope this helps.

Exercise of a minute or less. Verify that if $M$ do not accept $w$, $M_w$ simulate $T_\emptyset$.


What is the exponent of 0.00000072 And how do I solve this?
I know this is a decimal and we have to convert it to an exponent. I want to know how I would solve this and the steps as well so I will be able to solve questions similar to this in the future. Thank you

The number 0.00000072 has no exponent.
My best guess is that this question is about scientific notation. Every non-zero real number can be written in the form $\pm d_0.d_1d_2d_3 \ldots \times 10^e$, where $d_0 \neq 0$. Here $e$ is the exponent. Some examples:

$32 = 3.2 \times 10^1$. The exponent is $1$.
$-0.0014 = -1.4 \times 10^{-3}$. The exponent is $-3$.
$3.14159 = 3.14159 \times 10^0$. The exponent is $0$.

Hopefully now you can solve the question on your own.


Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular? We have a language  $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$
if I say i = 0 everything is okay because $L =a^{n-t}b^m$ and 2(n-t) + 3m <= 1000
if I say i = 2  $L =a^{n+t}b^m$ and 2(n+t) + 3m <= 1000 because I'm not sure about t value.
I think it didn't work. Is this language regular? How can I prove that?

The language is finite and, as such, it is regular (all finite languages are regular).
To see that the language is finite, notice that the maximum length of each word in $L$ is upper bounded by $500$.
Indeed, if $w \in L$, and $n$ (resp. $m$) is the number of $a$s (resp. $b$s) in $w$:
$$
2|w| = 2(n + m) \le 2n+ 3m \le 1000.
$$


Time Complexity for Creating a Graph from a File Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example:

0 5
0 7
2 3
4 5
1 5
.
.
.

I want to create a graph (adjacency list) by reading this file line-by-line. For each line, I will create an edge between the two vertices. Of course, if the vertex doesn't exist yet, then I will add it before creating the edge.

I read here of an algorithm that builds a graph with a time complexity of $O(|V| + |E|)$ where $V$ = set of vertices and $E$ = set of edges. That makes sense to me. However my algorithm doesn't insert the vertices in a loop first and then insert all of the edges in another loop second. My algorithm just adds the vertices as it's looping through the edges.

My question is if my algorithm is $O(|E|)$? It seems like that can't be right, but I read here that when calculating the time complexity you don't take into account if statements. That's exactly what my vertex creation would be -- an if statement that checks if the node exists in the middle of my looping through all the edges.

You forget that $O(|E|) \subset O(|E|+|V|)$ and $O(|E|+|V|) \subset O(|E|)$. Though It's actually $O(|E|\ln|V|)$, because checking if a vertex has been inserted is hardly $O(1)$.


Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path theorem. Now the theorem which is the subject of this question depends on two other theorems so I present the dependence before presenting the actual theorem and the difficulty which I face in the said.

Dependencies:

Theorem 22.7 (Parenthesis theorem)
In any depth-first search of a (directed or undirected) graph $G = (V, E)$, for any two vertices $u$ and $v$;, exactly one of the following three conditions holds:

the intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ are entirely disjoint, and neither $u$ nor $v$ is a descendant of the other in the depth-first forest,

the interval $[d[u], f[u]]$ is contained entirely within the interval $[d[v], f[v]]$, and $u$ is a descendant of $v$; in a depth-first tree,

the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$, and $v$ is a descendant of $u$ in a depth-first tree.

Corollary 22.8 (Nesting of descendants' intervals)
Vertex $v$ is a proper descendant of vertex $u$ in the depth-first forest for a (directed or undirected) graph $G$ if and only if $d[u] < d[v] < f[v] < f[u]$.

Theorem 22.9 (White-path theorem)
In a depth-first forest of a (directed or undirected) graph $G = (V, E)$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $d[u]$ that the search discovers $u$, vertex $v$ can be reached from $u$ along a path consisting entirely of white vertices.
Proof
$\Rightarrow$ : Assume that $v$ is a descendant of $u$. Let $w$ be any vertex on the path between $u$ and $v$ in the depth-first tree, so that $w$ is a descendant of $u$. By Corollary 22.8, $d[u] < d[w]$, and so $w$ is white at time d[u].
$\Leftarrow$:

Suppose that vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$, but $v$ does not become a descendant of $u$ in the depth-first tree.
Without loss of generality, assume that every other vertex along the path becomes a descendant of $u$. (Otherwise, let $v$ be the closest vertex to $u$ along the path that doesn't become a descendant of $u$.)
Let $w$ be the predecessor of $v$ in the path, so that $w$ is a descendant of $u$ ($w$ and $u$ may in fact be the same vertex) and, by Corollary 22.8, $f[w] \leq f[u]$.
Note that $v$ must be discovered after $u$ is discovered, but before $w$ is finished.$^\dagger$ Therefore, $d[u] < d[v] < f[w] \leq f[u]$.
Theorem 22.7 then implies that the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$.$^{\dagger\dagger}$
By Corollary 22.8, $v$ must after all be a descendant of $u$. $^\ddagger$■

$\dagger$ : Now it is clear that since $u$ is the first vertex to be discovered so any other vertex (including $v$) is discovered after it. In point $1$  we assume that $v$ does not become the decendent of $u$, but by the statement that but before $w$ is finished I feel that this is as a result of exploring the edge $(w,v)$ (this exploration makes $v$ ultimately the descendant of $u$, so the proof should have ended here $^\star$)
$\dagger\dagger$ : Considering the exact statement of theorem 22.7 , I do not get which fact leads to the implication in $5$.
$\ddagger$ : The proof should have ended in the $\star$, but why the stretch to this line $6$.
Definitely I am unable to get the meaning the proof of the $\Leftarrow$. I hope the authors are using proof by contradiction.
(I thought of an alternate inductive prove. Let vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$. We apply induction on the vertices in the white path. As a base case $u$ is an improper descendant of itself. Inductive hypothesis, let all vertices from $u$ to $w$ be descendants of $u$ , where $w$ is the predecessor of $v$ in the white path. We prove the inductive hypothesis by the exploration of the edge $(w,v)$. But I want to understand the proof the text.)

$\dagger\dagger$ Theorem 22.7 concludes that exactly one of the three conditions listed is satisfied. The inequalities listed in (4) show that the intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ intersect. Therefore, the first condition of the theorem is not the one being satisfied. In the other two conditions one of these two intervals is inside the other. Now, because the inequality $d[u]<d[v]$ is strict, it can't be that $[d[u],f[u]]$ is inside $[d[v],f[v]]$. So, the third condition in the theorem is the only one that can be satisfied.
$\dagger$ This is also using theorem 22.7 or its corollary. The inequality $d[u]<d[v]$ is part of the assumption, that by time $d[u]$ the vertex $v$ is still white. The inequality $f[w]\leq f[u]$ comes from Corollary 22.8, since $w$ is a descendant of $u$. The inequality $d[v]<f[w]$ is due to $(w,v)$ being an edge. Because all neighbors of $w$ must be discovered before we consider it finished. Now, the claim that the proof should end here is jumping to the conclusion of the theorem without justification. It hasn't been justified that DFS will actually use $(w,v)$ to discover $v$.
Example 1: For example, consider the graph with vertices $1,2,3,4$ and (directed) edges $(1,2),(1,4),(2,3),(4,3)$ and we start at $1$ doing DFS. Assume that we already discovered $1$ and $2$.
At this point the vertex $v=3$ is is a white path from $u=w=2$. Just one edge $(2,3)$. DFS will discover $3$ and make it a descendant of $2$. There is no way to change that, since Theorem 22.9 proves it. But imagine that at this point we stop obeying DFS and go to discover $4$ and from $4$ go and discover $3$. Then $3$ wouldn't be a descendant of $2$. It would only be a descendant of $4$ and $1$. Theorem 22.9 proves that DFS wouldn't do that.
Example 2: This is to illustrate the question in the comments. Consider the graph with vertices $1,2,3,4$ and edges $(1,2),(1,4),(2,3),(2,4),(3,4)$. Assume that we have discovered already $1$ and $2$, in that order. The vertex $v=4$ is in a white path from $u=w=2$. However, the edge $(2,4)$ doesn't necessarily need to be used by DFS. If the neighbors of a vertex are considered in the order according to the labels that we gave them in this example, then from $2$ DFS will discover $3$ and from $3$ it will discover $4$. Then $3$ becomes finished, then $2$ becomes finished, and $1$ becomes finished, in that order.
While theorem 22.9 doesn't ensure that either $(2,4)$ or $(3,4)$ will be used, since that depends on the other in which neighbors are explored, note that it does ensure that the edge $(1,4)$ will not be used (under the assumptions of the example that $1$ was discovered and $2$ just got discovered). In fact, Theorem 22.9 implies that $4$ will be a descendant of $2$.


Run-time of a summation function and its complexity I am trying to analyze the running time of the following function:
def algo(array: List[int]):
    x = 1
    y = 0
    sigma = 0
    for ix in range(1, len(array)):  #len(array) always >= 1
        summation = 0
        for jx in range(ix, 0, -1):
            summation = summation + array[jx]
            if summation > sigma:
                x = jx
                y = ix
                sigma = summation
    return (x,y)

I have identified a basic unit of the algorithm to count as the number of iterations/total loops, $L$, it runs through. So for instance, if the length of array, $n$, is $1$, then $L = 1$. If, $n = 5$, then $L = 15$. The pattern follows that of the triangular numbers sequence. If you plot a set of points $(n, L)$ you will see that it kind of looks exponential. Is my line of thinking so far okay?

The body of the inner for loop is executed in constant time per iteration and it does not affect the number of iterations of the outer loops.
Let $n$ be the length of array. The outer for loop iterates $n$ times. During the $i$-th iteration of the outer loop, the inner for loop iterates $i$ times.
The overall time complexity is therefore:
$$
\Theta(1) \cdot \sum_{i=1}^{n} i = \Theta(1) \cdot \Theta(n^2) = \Theta(n^2).
$$


Time complexity of Tsp using DP this is the recursion formula for problem :
C(i,S) = min { d(i,j) + C(j,S-{j}) }

In fact, when I tried to implement it as a code, the following code came to my mind:
int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j++)
     {
      cost = dist(i,S[j])+TSP(j,S-{j});
      if(cost < min)
       min = cost;
      }
global_cost+=min;
return min;
}

Because this for compares n times to find the minimum, it means its recursion as:
T(n) = nT(n-1)+n ==> T(n) = O(n!)

Because each step we compare to find the minimum size of size S is, of course, the code is factorial. So what does it have to do with the subset and So why the complexity of time in the form of (n^2*2^n)? And what is the proof of its time complexity?

Your algorithm is known as the Held–Karp algorithm, and is described on Wikipedia, and also mentioned on the Wikipedia page on the traveling salesman problem.
Your implementation of the algorithm is wasteful. Using memoization, there are only at most $n2^n$ inputs. Since TSP runs in time $O(n)$ ignoring recursive calls, when using memoization, the total running time will be $O(n^22^n)$.


Code optimization - syntax tree vs. intermediate representation I'm working on a compiler for my own custom language.  As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been formed.  Though I haven't yet started writing the optimization section of my compiler, I've been going through it in my head and it seems preferable to have the optimizer operate on the syntax tree before converting to the intermediate representation.
Is there a reason to prefer one approach to the other or is mostly a matter of personal taste?
For example, suppose I have an if block like
if ( some_expression ) {
    do_stuff
}

If it could be recognized by the compiler that some_expression will always evaluate to true and have no side effects, then I could remove its computation simply by pruning the tree.
However, if I had already converted the tree to an intermediate representation, such as an assembly-ish list of simple instructions, the processes of recognizing and resolving the scenario would be (in my imagination since I haven't yet attempted to implemented this) far more complicated.

These days, the trend is to do optimization with the intermediate representation. Check out LLVM for example:

The LLVM Core libraries provide a modern source- and target-independent optimizer, along with code generation support for many popular CPUs (as well as some less common ones!) These libraries are built around a well specified code representation known as the LLVM intermediate representation ("LLVM IR"). The LLVM Core libraries are well documented, and it is particularly easy to invent your own language (or port an existing compiler) to use LLVM as an optimizer and code generator.

LLVM can provide a source-independent optimizer because it is performs its optimization passes over the code only after it is represented in LLVM IR.
Why might it be far more complicated to do this? It depends on your intermediate representation. One of the design goals for the intermediate representation would be to facilitate various optimizations rather than make them needlessly complicated. See all the optimizations that LLVM can achieve working on the LLVM IR, for example, in this list of analysis and transform passes.