Hamiltonian path greedy and anti-greedy algorithms

No.

In fact, we can prove the following stronger proposition.
Claim. Given a complete weighted undirected graph, a run of the greedy algorithm on it and a run of the anti-greedy algorithm on it, the $i$-th heaviest edge chosen by the greedy algorithm weighs no more than the $i$-th heaviest edge chose by the anti-greedy algorithm, for all valid $i$.
Proof. It is enough (and necessary) to show, given any weight $w$, the number of edges chosen by the greedy algorithm that weigh more than $w$ is no more than the number of edges chosen by the anti-greedy algorithm that weigh more than $w$.
Fix an arbitrary weight $w$. Let $\overrightarrow{u_1v_1}$, $\overrightarrow{u_2v_2}$, $\cdots$, $\overrightarrow{u_kv_k}$ be the edges chosen by the greedy algorithm that weigh more than $w$, in the same order as they were chosen by the greedy algorithm. Assume $k\ge1$; otherwise we are done.
Note that $u_1, u_2, \cdots, u_k$ and $v_k$ are distinct, since they are the starting vertex of distinct edges and the ending point of the last edge, respectively. Let $u_{k+1}=v_k$.
Consider any two vertex $u_p$ and $u_q$ such that the greedy algorithm visits $u_p$ earlier than $u_q$, i.e., $p<q$. We know $\overrightarrow{u_pv_p}$ weighs no more than $\overrightarrow{u_pu_q}$ since it weighs the least among all edges from $u_p$ to unvisited nodes. Since $\overrightarrow{u_pv_p}$ weighs more than $w$, so does $\overrightarrow{u_pu_q}$. We have just proved the simple and critical observation that all edges among $u_1, u_2,\cdots,u_{k+1}$ weigh more than $w$.
The anti-greedy algorithm will visit each vertex in $u_1, u_2, \cdots, u_{k+1}$  soon or later, since it will find a hamilton path. Consider the $m$-th time when the anti-greedy algorithm have just visited such a node. If $m\lt k+1$, then there is at least another such node that has not been visited, which means the next edge it will choose must weigh no less than the edge to that unvisited node, which weighs more than $w$ as we just proved above. That is, for each of the first $k$ times the anti-greedy algorithm must choose an edge that weigh more than $w$.  $\quad\checkmark$


Acceptance behavior of L and NL with and without cycling

Shaull's comment answers the question:

  Do you mean that the TM repeats a configuration? If so, it can always be avoided by keeping a (logspace) counter for the maximal number of configurations, and halting when the counter resets.

This technique can even be used, without knowing (beforehand) any bound for the amount of space used. The TM can just keep track of the amount of space used till the current step (excluding the additional counter), and halt when the counter exceeds the maximal possible number of different configurations given the space used.

The additional counter will take the same amount of space as the computation already used plus the logarithm of the length of the input already scanned. Tracking of the amount of space used adds the logarithm of that used space to the total used space. So this approach to detect (avoid) repeated configurations works for any non-sublogarithmic space complexity class.

When I asked that question, I had in mind a technique for finding cycles which only works for deterministic machines: I take two copies of the machine, and always perform one step for the first machine and two steps for the second machine, and then compare the configurations of the two machines. Those configurations can only be equal if the machines cycles, and any cycle will be found before the first machine repeats a configuration.

This technique only works for deterministic machines, and only when copying the machine doesn't violate any resource restrictions. For example, it doesn't work for stack machines (because having two stacks is fundamentally different from having only one stack), and it doesn't work for machines which may only read their input once.

For machines which can read their input only in forward direction and only once, the above two techniques can be slightly modified. Each time a new symbol from the input is read, the entire machinery for detection of repeated configurations is reset, and starts again from zero. So the input position must no longer be included in the number of possible states, and the copied machines (of the second technique) no longer need any access to the input. This allows to apply those techniques also to DFAs.

Similar modifications to also make those techniques applicable to stack machines would be nice, because we know that PDAs have no problems with repeated configurations either.


Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations.
Warning: a little dose of personal experience is included in this answer.
Reading suggestion: If this answer looks too long to you, just read the text in boldface.
Background and Definitions
Memoization means the optimization technique where you memorize previously computed results, which will be used whenever the same result will be needed.
Memoization comes from the word "memoize" or "memorize".
Dynamic programming (DP) means solving problems recursively by combining the solutions to similar smaller overlapping subproblems, usually using some kind of recurrence relations. (Some people may object to the usage of "overlapping" here. My definition is roughly taken from Wikipedia and Introduction to Algorithm by CLRS.) I will only talk about its usage in writing computer algorithms. Note that an actual implementation of DP might use iterative procedure.
Why is DP called DP? The word "dynamic" was chosen by its creator, Richard Bellman to capture the time-varying aspect of the problems, and because it sounded impressive. For the full story, check how Bellman named dynamic programming?.
Nowadays I would interpret "dynamic" as meaning "moving from smaller subproblems to bigger subproblems". (The word "programming" refers to the use of the method to find an optimal program, as in "linear programming". People like me treat it as in software programming sometimes.)
Explanations
Why do some people consider they are the same?
It is understandable that Dynamic Programming (DP) is seen as "just another name of memoization or any tricks utilizing memoization". When the examples and the problems presented initially have rather obvious subproblems and recurrence relations, the most advantage and important part of DP seems to be the impressive speedup by the memoization technique.
In fact, for some time, I had been inclined to equating DP to mostly memoization technique applied to recursive algorithms such as computation of Fibonacci sequence or the computation of how many ways one can go from the left bottom corner to the top right corner of a rectangle grid.
How are DP and memoization different?
The memoization technique is an auxiliary routine trick that improves the performance of DP (when it appears in DP). It appears so often and so effective that some people even claim
that DP is memoization
Let me use a classic simple example of DP, the maximum subarray problem solved by kadane's algorithm, to make the distinction between DP and memoization clear.
Since I was a kid, I had been wondering how I could find the maximum sum of a the contiguous subarray of a given array. First thought was grouping adjacent positive numbers together and adjacent negative numbers together, which could simplify the input. Then I tried combine neighbouring numbers together if their sum is positive or, hm, negative. Then the uncertainty seemed attacking my approach from everywhere. Many years later, when I stumbled upon the Kadane's algorithm, I was awe-struck. It is such a beautiful simple algorithm, thanks to the simple but critical observation made by Kadane: any solution (i.e., any member of the set of solutions) will always have a last element. Trust me, only if you can appreciate the power of such a simple observation in the construction of DP can you fully appreciate the crux of DP.
Please note there is not any (significant) usage of memoization in Kadane's algorithm.
Just in case you might brush off Kadane's algorithm as being trivial, let me present two similar problems.

Can you find efficiently the maximum sum of two disjoint contiguous subarray of a given array of numbers?
Can you find efficiently two disjoint increasing subsequence of a given sequence of numbers the sum of whose lengths is the maximum? (This problem is created by me.)

If you can find the solution to these two problems, you will, I believe, be able to appreciate the importance of recognizing the subproblems and recurrence relations more. That might just be the start of a long journey, if you are like me.
By Wikepedia entry on Dynamic programming, the two key attributes that a problem must have in order for DP to be applicable are the optimal substructure and overlapping sub-problems. In other words, the crux of dynamic programming is to find the optimal substructure in overlapping subproblems, where it is relatively easier to solve a larger subproblem given the solutions of smaller subproblem.
In summary, here are the difference between DP and memoization.

DP is a solution strategy which asks you to find similar smaller subproblems so as to solve big subproblems. It usually includes recurrence relations and memoization.
Memoization is a technique to avoid repeated computation on the same problems. It is special form of caching that caches the values of a function based on its parameters.

More advanced dynamic programming
Here I would like to single out "more advanced" dynamic programming. More advanced is a pure subjective term. What I would like to emphasize is that the harder the problems become, the more difference you will appreciate between dynamic programming and memoization.
Even as the problem becomes harder and varied to solve, there is not much variation to the memoization. The memoization technique are present and helpful most of the time. However, it becomes routine. After all, all you need to do is just to record all result of subproblems that will be used to reach the result of final problem.
However, as I have been solving more and harder problems using DP, the task of identifying the subproblems and construction of the recurrence relations becoming more and more challenging and interesting. There are many variations and techniques in how you can recognize or define the subproblems and how to deduce or apply the recurrence relations. Many of the harder problems look like having a distinct personality to me. Here are some classical ones that I have used.

Knuth's optimization that reduces the dimension of computation almost by one.
the Golden Rule of harder DP problems (named by me for the lack of a name): when you cannot move from smaller subproblems to a larger subproblem because of a missing condition, add another parameter to represent that condition.
Convex hull trick
Dynamic programming on graphs with bounded treewidth

The following is a nice article.

Dynamic programming from novice to advanced


Are time complexity of followng codes equivalent?

I'm not familiar with C++ but it looks like that both codes are equivalent, for loop and while loop has the same power.

In your examples, in both cases you first you initial the variable k, and  the loop doesn't stop as coud() condition holds, inside the loop there is a call to f(); method, and finally to next();.


What is the name of the optimization that removes self eliminating multiplication-division statements?

It's probably most easily described as a two-step process. First a step of Copy Propagation to get

x_2=x*c/c
print(x_2)

followed by a step of Constant folding to remove the unecessary operations.


Does loop invariant has nothing to do with termination?

The loop invariant is just a proposition which holds on each iteration of the loop (in your question, the relationship between $x$ and $y$ holds regardless, so no, it is not affected by loop nontermination). It doesn't inherently say anything about termination. It is potentially something that you can use to argue about termination.
The Wikipedia article on correctness additionally describes the difference between partial and total correctness. For partial correctness, we don't require a program terminates, only that the result is correct if it is returned.


We can eliminate all but one of the vertices by checking for the existence of $n-1$ edges because we can eliminate one possibility for each edge we check. In particular, if there is an edge going from $x$ to $y$, we eliminate $x$ and move on to $y$ (as another vertex can be reached from it); if not, we eliminate $y$ (as it cannot be reached from $x$). Once we reach the last vertex, whichever vertex is not eliminated should be compared with each other vertex (ensure the superstar condition is upheld: there is an edge incoming but not outgoing) until it is eliminated or confirmed as the superstar. Some pseudocode:

vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

Let's walk through an example to illustrate the method. Take this array, with the source vertex on the top and destination on the side. 1 indicates an edge:

$$
\begin{array}{r|c c c c|r}
  & 1 & 2 & 3 & 4 \\
\hline
1 & - & 1 & 0 & 1 \\
2 & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

I'll grey out the vertices we have ruled out as potential superstars.
I'll use green and red to indicate the edges we are looking at when they do and do not contain the edge we're looking for, and blue to indicate where we have already looked.

We start by looking at vertices 1 and 2.

$$
\begin{array}{r|c c c c}
  & 1 & 2 & 3 & 4 \\
\hline
1 & - & \color{green}{1}
          & 0 & 1 \\
2 & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$
The green number shows there is an
edge from 2 to 1, so we eliminate 2 and look for an edge from 3 to 1:

$$
\begin{array}{r|c c c c}
  & 1 & \color{grey}{2} & 3 & 4 \\
\hline
1 & - & \color{blue}{1}
          & \color{red}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & 1 \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

We see there is no such edge, so we eliminate 1 and take 3 as our current
vertex. Recall that we have eliminated 2 already, so see whether there is an edge from 4 to 3:

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & 4 \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & 1 & 1 & - & \color{green}{1} \\
4 & 1 & 1 & 0 & - \\
\end{array}
$$

There is an edge from 4 to 3, so we eliminate 4. At this point we have
eliminated all but one of the vertices (3), so check out its edges and see whether it qualifies:

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{red}{0}
              & 1 \\
\color{grey}{2} & 1 & - & 0 & 1 \\
3 & \color{green}{1} & 1 & - & \color{blue}{1} \\
\color{grey}{4} & 1 & 1 & 0 & - \\
\end{array}
$$

There is an edge from 1 to 3 but not the reverse, so 3 is still a candidate.

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & \color{red}{0}
              & 1 \\
3 & \color{blue}{1}
      & \color{green}{1}
          & - & \color{blue}{1} \\
\color{grey}{4} & 1 & 1 & 0 & - \\
\end{array}
$$

There is also an edge from 2 to 3 but not the reverse, so 3 is still a candidate.

$$
\begin{array}{r|c c c c}
  & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\
\hline
\color{grey}{1} & - & \color{blue}{1}
          & \color{blue}{0}
              & 1 \\
\color{grey}{2} & 1 & - & \color{blue}{0}
              & 1 \\
3 & \color{blue}{1}
      & \color{blue}{1}
          & - & \color{green}{1} \\
\color{grey}{4} & 1 & 1 & \color{red}{0}
              & - \\
\end{array}
$$

There is an edge from 4 to 3 but not 3 to 4; that completes our check of 3's edges and we have found that it is, in fact, a superstar.

Since we eliminate one vertex as a possible superstar on each of the first
$n-1$ edge checks, the best case is that the $n$th check eliminates the
final vertex for a complexity of $n$. In the worst case (the last or
second-to-last vertex is a superstar, or the final check disqualifies it), after the first $n-1$ comparisons we compare the candidate
with $2\times(n-1)$ more vertices, for a worst case complexity of $3n-3$ ($O(n)$). So, this algorithm is
$\Theta(n)$.


Given a list of students and their courses, place them in specific classes

At first glance, the stable matching problem's solution is discussed in the following pdf.
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

It would be hard to cast the course assignment problem as stable matching because he fact that the courses have a finite capacity

However, the following pdf states that, http://dss.in.tum.de/files/bichler-research/2014_diebold_matching_course_allocation.pdf

  The allocation of students to courses is a wide-spread and repeated
  task in higher education, often accomplished by a simple first-come
  first-served (FCFS) procedure. FCFS is neither stable nor
  strategy-proof, however. The Nobel Prize in Economic Sciences was
  awarded to Al Roth and Lloyd Shapley for their work on the theory of
  stable allocations. This theory was influential in many areas, but
  found surprisingly little application in course allocation as of yet.
  In this paper, we survey different approaches for course allocation
  with a focus on appropriate stable matching mechanisms. We will
  discuss two such mechanisms in more detail, the Gale-Shapley student
  optimal stable mechanism (SOSM) and the efficiency adjusted deferred
  acceptance mechanism (EADAM). EADAM can be seen as a fundamental
  recent contribution which recovers efficiency losses from SOSM at the
  expense of strategy-proofness. In addition to these two important
  mechanisms, we provide a survey of recent extensions with respect to
  the assignment of schedules of courses rather than individual courses.
  We complement the survey of the theoretical literature with results of
  a field experiment, which help understand the benefits of stable
  matching mechanisms in course allocation applications.


Complexity of simulating idle games (pt1)

As you have said in your question, non-cyclical resource production is easy to simulate, but let's describe the simple case before seeing how it impacts the answer. For our cookie-bakery scenario, this is the setup:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=0,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
The above describes the initial state of our game, we currently have 567 cookies and 10 bakeries. It also describes the production statistics, how much each resource produces per tick. For us, cookies produce nothing and bakeries produce 2 cookies per tick. How do we find how many cookies there are when the time is up?
$$
C(t_f)=\int_{t_i}^{t_f}\frac{dC}{dt}dt+C_i=2567
$$
This function will calculate how many cookies have been produced by time $t_f$. In our simple case, $\frac{dC}{dt}$ is easy to calculate:
$$
\frac{dC}{dt}=B_{cpt}B(t)=20
$$
Since there are no new bakeries being generated, the number of bakeries is constant $B(t)=B_i$.

Question 1
The trouble begins when the resource production contains cycles. That is to say, $\frac{dC}{dt}$ is dependent on $C(t)$ itself. We have entered the realm of differental equations. For an example, here is a tweaked setup where cookies can also asexually reproduce every tick:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=1,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
Now the rate of change for cookies looks like:
$$
\frac{dC}{dt}=B_{cpt}B(t)+C_{cpt}C(t)\text{ where }C(0)=C_i
$$
For our case, this is a linear first-order differential equation, our integrating factor is:
$$
\mu(t)=e^{-C_{cpt}t}
$$
Plug it into the differential equation form:
$$
C(t)=\frac{B_{cpt}B(t)}{-C_{cpt}}+ce^{C_{cpt}t}
$$
Find our constant $c$ by checking the initial condition:
$$
C(0)=\frac{B_{cpt}B(0)}{-C_{cpt}}+ce^0=C_i \\
c=C_i+\frac{B_{cpt}B_i}{C_{cpt}}
$$
Plug it back into our original equation:
$$
C(t_f)=\frac{B_{cpt}B(t_f)}{-C_{cpt}}+\bigg(C_i+\frac{B_{cpt}B_i}{C_{cpt}}\bigg)e^{C_{cpt}t_f} \approx 1.58\times 10^{46}
$$
The asexual reproduction of cookies produces substantially more cookies than just bakeries, but keep in mind the cookie population is essentially doubling every time plus new cookies are being produced by bakeries.
This method can be extended for larger cycles instead of just self cyclical, but it requires higher order differential equations.
Note: Since we are just evaluating an exponential function, it is extraordinarily efficient, $O(1)$. However, this solution adapts the mathematics of population growth estimates to fit this discrete system and will only produce an approximation. Depending on how many timesteps are required to simulate, it may be preferable to spend more time computing an exact result.

Question 2
Automatic buying is quite a bit more difficult to achieve because the functions showing resource counts are no longer smooth and continuous.

This graph shows the cookie production assuming starting with one bakery & zero cookies and buying another bakery every thousand cookies. The period of the function decreases with time because more and more bakeries are added to produce cookies. An estimation could be created by fitting a function to the period, but I do not know of a method to exactly count the number of bakeries and cookies without checking each timestep.


Pseudo code algorithm for beauty contestant question

You are asking for the Pareto-optimal front in 3D space.  This is a well-studied problem.

In 2D, there are $O(n \log n)$ time algorithms: see, e.g., What are some interesting applications of the skyline problem?, An online algorithm to find the Pareto frontier elements, minimum subset of dominating 2D points.

In 3D, life is more complicated, but apparently it is still possible to solve this in $O(n \log n)$ using fancy methods.  See the following paper:

On Finding the Maxima of a Set of Vectors.  H.T. Kung, F. Luccio, F.P.Preparata.  Journal of the ACM, vol 22 no 4, Oct 1975, pp.469--476.


Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

Without fully answering your question, I would like to answer it at
least partially by remarking that computation cost can be evaluated
only with respect to an abstract model of computation.

If you want to use two different models, for two different programs,
than you have to determine the complexity of reducing each model to
the other, in order to have a meaningful comparison.

Another point is that physics does not well qualify as a computation
model for several reasons:

it is not clear enough what physics allows and does not allow regarding of computation, computation speed, storage, etc.
computation models are defined with various assumptions about unit
operations and their costs, and about infinity and asymptotics,
which are not meant to be a reflection of reality, but only an
approximation of reality intended to facilitate the analysis of
some phenomena, whether abstract or physical.

This is why Turing machines are more appropriate than finite
automata theory to analyse the behavior of devices with very large,
though still finite memory. For example, the powerset construction
of DFA may exist in theory when the memory is finite, however big,
but may also quickly exceed the capacity of our limited universe,
thus hardly making any sense.

Considering your first example about the "physical" time cost of
executing a for loop on an array of size $n$. If we are to do
asymptotic physics, we have to do it right, or at least as right as
current knowledge in physics will allow. Due to universe expansion,
the part of the universe that we can ever hope to access is bounded by
a radius of some $z$ zillion light-years (corresponding to a distance
at which the expansion speed relative to us equals the speed of
light), so that nothing relevant to us can be further away.

You can see that as good news: distances being bounded, access is
asymptotically in constant time, so that the classically accepted cost
analysis does hold, despite your remarks.

Of course, since you still want to have arbitrarily large memory, you
have to assume that this finite sphere can hold infinitely many bits
of information ... which I fear physicists cannot really tell. But
let's be optimistic.

Another way to do away with your remark is to consider that the access
time is small enough that it will not really impact the computing
time, unless you have specific reasons to think otherwise.

Some high speed computer do have to be programmed taking into account
physical distances, in particular to memory. But why should functional
program be exempted from such physical limitations. How much
computational capacity do you store with each cell?  Instead of the
$+$ operator, can you pass any arbitrarily complex fuction as
parameter and still have it reduced locally in each memory cell.

Or to put it differently, what prevents an imperative program from
taking advantage of an architecture that has computing power in each
memory cell. This is remindful of various specialized architectures,
such as vector processors.


How to improve the CPI and Speed up factor in CPU-OS simulator?

To be able to improve CPI and the speed-up factor you need to enable the pipeline. The programmer can help improve CPI but it is best to leave that to an optimising compiler and clever CPU architecture. The simulator's built-in compiler offers some help in reducing the CPI, for example loop unrolling, constant folding, identifying code dependencies, etc. In pipelined architecture, the goal is to reduce/prevent hazards and the above optimisations help do that. In addition, the pipeline has a means of forwarding operands, i.e. prior to previous instructions updating registers in a later stage, that contributes to reducing the CPI. There is also the technique of jump predictions. All these are available in the simulator which you should explore.


recNat :: (Integer -> a -> a) -> a -> Integer -> a
recNat s z n | n <= 0    = z
             | otherwise = s (n-1) (recNat s z (n-1))
-- Exercise: Express this in terms of foldNat.

log2 :: Integer -> Integer
log2 = fst . recNat (\n (c, p) -> if 2*p > n+1 then (c, p) else (c+1, 2*p)) (0, 1)


Scheduling to minimize the truncated gaps

The problem is polynomial-time solvable.
To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$.

Let $OPT[t,p]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job must be scheduled at time $t$.

Let $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big\rfloor$ be the penalty incurred if the job is scheduled at times $t'$ and $t > t'$ and is not scheduled at any time in-between.

Then $OPT[0,p] = 0$ and, for $t>0$:
$$
OPT[t,p] = c(t) + \min_{\substack{t'=0,\dots,t-1 \\ P(t',t) \le p}} OPT\left[t', p - P(t',t) \right]
$$

The minimum attainable penalty up to time $t$, with the constraint that the job is scheduled at time $t$, is then:
$$
\mu(t) = \min \{p \in \{1,\dots,\lfloor t/2 \rfloor\} \mid  OPT[t,p] \le B \}
$$

And the minimum attainable penalty for your problem is:
$$
\min_{t=0,\dots,n}  \left\{ \mu(t) + P(t,n+1) \right\}.
$$

Notice that there are at most $n \cdot (P(0,n)+1) = O(n^2)$ values $OPT[p,t]$ to compute.


Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension

(This answer assumes my conjectural interpretation of the predicate $T$.)
The function $H(x)$ is given by
$$
H(x) = \begin{cases} t & \text{if program $x$ run on input $x$ halts after $t$ steps} \\ \bot & \text{if program $x$ never halts when run on input $x$} \end{cases}
$$

Hint: Given a total computable function extending $H$, show how to solve the halting problem. There is no need to use diagonalization – this is already taken care of in the proof that the halting problem is undecidable.


Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

Yes.  The phrase to search for in the literature is "dynamic shortest paths".  "Dynamic" refers to the path that the graph might change, and we want to efficiently update the shortest paths (more efficiently than recomputing them from scratch).

There are different ways one might change the graph.  Some papers consider the case where edges can be added.  Others consider where edges can be removed.  You can also find algorithms that can handle both kinds of changes; that might go under the name "fully dynamic shortest paths".

Search the literature.  You'll find many algorithms, with different tradeoffs between running time, simplicity of implementation, and types of graph updates supported.


We can calculate 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. You can store this in any way you want: as 100!, as the ASCII string 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000, as a Unicode string, or in binary in any number of formats. It all depends on what you want to do with the value. If you want to display the value on screen as a decimal, you might as well store the decimal string. If you want to do arithmetic, then you should be using a library for dealing with "big numbers" such as GMP, and in this case the library will provide its own means for storing numbers. If you're just interested in storing the expression 100!, and intend to use it in a computer algebra software (CAS), you might as well store it as just 100!.


Is there a set of NP-hard problems that are most commonly used for proving NP-hardness?

Most textbooks will have a set of 'core' NP-Complete problems from which all their examples and exercises would reduce from, which are probably the ones you list (3SAT, Vertex Cover, Independent Set, Clique, k-Coloring, Set Cover, Dominating Set, Hitting Set, Subset Sum, Knapsack.)

A bigger set of 'standard' problems would be Garey & Johnson's book. Beyond that, people look at hard restrictions of the standard problems (i.e. k-coloring for k=3, Exact Cover version of set cover, not-all-equal 3SAT, etc).

Beyond that, it gets fairly domain specific.


Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states:

  We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}[O(n^2)]$.

Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices.

Unfortunately this is not better than what you had hoped for.


How append, prepend, and generally insertAt work in RRB-tree

Currently there's no "magic trick" to do an insertAt for RRB-trees: It can be implemented by doing

concat(append(leftSlice(rrb, i), elt), rightSlice(rrb, i))

Append can (as I've shown in my thesis) be very efficient. If you don't want to focus on transients and tails, then chapter 5 explains how you modify the persistent vector append algorithm to work for RRB-trees. In short, you have to first find the path to walk, then walk and update it just as in the persistent vector, but in addition you have to update the slot sizes.

Prepend is simply a special case of concatenation.


Whatever that can be done using algorithm can be done using Turing machine

The hypotesis is the following:

"Since an algorithm is a well-defined sequence of steps we can always execute an algorithm in a piece of paper(sometimes we may need a really big paper) using a pencil."

Then he created the Turing Machine who can simulate a hand using a pencil with an infinite paper.


All strings in which every substring 000 appears after every 1

The formulation

every substring 000 appears after every 1

is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x_0 \ldots x_{m-1}$ be words. We say that $x$ occurs in $w$ at position $i$ if $$w_i w_{i+1} \ldots w_{i+m-1} = x_0 x_1 \ldots x_{m-1}.$$
The language in question consists of all words $w$ such that if $1$ occurs in $w$ at position $i$ and $000$ occurs in $w$ at position $j$, then $i < j$. This means that after the first time that $000$ occurs, the word consists only of $0$s. Therefore we can break words in the language into two parts: the first part doesn't contain $000$ at all, and the second part, which is optional, contains $000$ followed by any number of $0$s.


Closed form solution for optimization problem

There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. Namely,
$$\|C\|^2_F = \text{Tr}\left[CC'\right],$$
where $C'$ denotes the transpose of $C$. The second fact is the derivative of the Frobenius norm squared, which is given by $$\frac{\partial}{\partial C} \text{Tr}\left[(S - AC)(S - AC)'\right] = -2A' (S - AC).$$

Luckily for us the derivative of sums is equal to the sum of the derivatives (i.e., the derivative is a linear function). So we can take the derivative of the objective with respect to $C$ piecemeal. We end up with $$\frac{\partial}{\partial C} \|S - AC\|^2_F + \lambda\|C\|^2_F = -2A' (S - AC) + 2\lambda C.$$ Setting this equal to 0 and solving we have, $$\begin{align*} -2A' (S - AC) + 2\lambda C &= 0 \Leftrightarrow \\ -2A'S + 2A'AC + 2\lambda C &=0 \Leftrightarrow \\ -2A'S + 2(A'A + \lambda I)C & = 0 \Leftrightarrow \\ C &= (A'A + \lambda I)^{-1}A'S,
\end{align*}$$ where $I$ is the identity matrix.

An eigendecomposition of this result gives more insight into the behavior. Put simply, you add $\lambda$ to the eigenvalues of the $A'A$ matrix which should shrink your final estimates. This is a form of regularization known as ridge regression. Except here we are applying it for multivariate multi regression instead of linear regression.


Why are transcendental functions of large numbers inaccurate on computers?

There's nothing fundamentally hard about computing $\sin(10^{99})$.  You simply compute $x = 10^{99} \bmod 2\pi$, then compute $\sin(x)$.  (Why is this valid?  It's because $\sin(x)=\sin(y)$ if $x\equiv y \pmod{2\pi}$.)  It's not too hard to compute $x$ if you use a numerical representation that has enough digits of precision, and then to compute $\sin(x)$ using standard methods.

However, a standard double won't have enough precision to perform this computation.  It only has about 53 bits of precision; that's a lot less than the $99 \lg 10 \approx 329$ bits of precision you'd need to be able to distinguish $10^{99}$ from $10^{99}+1$. (A standard IEEE float cannot even represent values in excess of $3*10^{38}$). Of course, $\sin(10^{99})$ is very different from $\sin(10^{99}+1)$.  So, if you want to compute $\sin(10^{99})$, just stuffing $10^{99}$ into a float or double and then trying to invoke the $\sin(\cdot)$ function on that is not going to end well.

If you want to compute $x$ to at least $b$ bits of precision, you'll probably need a numerical representation that can represent $10^{99}$ to at least $329+b$ bits of precision (probably more than that, for intermediate values that arise during the modular reduction).  A float or double ain't gonna be enough for that.


Why we still need Short Term Memory if Long Term Memory can save temporary data?

There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer requirements - it only needs to store the data for a short while until it gets refreshed, so it's not a surprise that it often is faster.
But the fundamental reason is that memory gets slower to access the bigger it is. This is why modern architectures don't just have 'RAM' and 'disk', there's layers upon layers of increasing size memory, with only the topmost layer being non-volatile:

CPU registers
L1 cache
L2 cache
L3 cache
RAM itself
Cache on the disk micro-controller
The disk itself


Generate random numbers from an interval with holes

0 1 2 3 4 5 6 7 8 9

0 1 2 3 - 5 - 7 8 -

"-" are in $S = \{4,6,9\}$

You can create mass distribution with  $$\text{Prob}(x) = \begin{cases}\frac{1}{N - |S|} & \text{if } x \notin S\\
0 & \text{if} \ x \in S
\end{cases}
 $$

and then use this algorithm. Copied from here.

from collections import defaultdict
import random

def roll(massDist):
    randRoll = random.random() * sum(massDist) # in [0,1)
    s = 0
    result = 0
    for mass in massDist:
        s += mass
        if randRoll < s:
            return result
        result+=1

sampleMassDist = [1,1,1,1,0,1,0,1,1,0]

d = defaultdict(int)
for i in range(1000):
  d[roll(sampleMassDist)] += 1

print d


If you do not flip the kernel, you simply obtain a different operation that is called cross correlation. When the filter is symmetric, like a Gaussian, or a Laplacian, convolution and correlation coincides. But when the filter is not symmetric, like a derivative, you get different results.

The reason why convolution is preferred over correlation is that it has nicer mathematical properties. In particular, convolution is associative, while correlation in general is not.

For a more technical explanation we need to go into the frequency domain.
The main theorem of convolutions states that the Fourier tansform of the convolution $f*g$ of two functions $f$ and $g$ is equal (up to a constant depending on the transformation) to the product of the Fourier transforms of the two functions. In symbols

$$ {\mathcal {F}}\{f*g\}=k\cdot {\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$$

where $\mathcal {F}$ is the Fourier transform. In the case of correlation, you would get multiplication by the complex conjugate, that is less nice, and in particular not associative.

Another interesting property of convolution is that convolving a kernel with
a unit impulse (e.g. a matrix with a single 1 at its center and 0 otherwise),
you get the kernel itself as a result. Correlation would flip the kernel,
instead.


It depends on what you are trying to achieve, but generally i/o intensive jobs should receive a higher priority, and a small time quantum.

I assume you are asking about some variety of multilevel feedback queuing.  The idea behind multilevel feedback queue-based schedulers is to try to approximate shortest remaining time first scheduling, where you are trying to minimize the average time each process spends waiting while it is ready-to-run.

We assume each process goes through the following cycle:

ready-to-run: waiting for all higher-priority processes to finish using cpu.
running: for some amount of cpu time then perform a blocking i/o request.
sleeping: after making a blocking i/o request, the process sleeps, waiting for the response from the i/o system.

When the response comes back from the i/o system the process wakes up and is ready-to-run again.  We call the set of processes that are ready to run (the processes not blocked waiting for a response from the i/o system), the run queue.

If we were able to predict exactly how long each process needed the cpu before its next i/o request, then we wouldn't need to have quanta at all.  Every time a process made an i/o request (moving it from state running to state sleeping) or got a response from i/o (moving it from sleeping to ready-to-run) we would just find the process with the shortest remaining time to its next i/o request, and run it.

But we don't know exactly how long each process will use the cpu before its next i/o request.  So we have to guess (e.g., by keeping track of how long it took the last few times, and using the average of those as the guess), but we might be way off.  So we also start a timer with a length somewhat larger than our guess for the expected cpu usage.  If our guesses are very good, then the timer will never fire.  Instead, each process will either make an i/o request, causing itself to block and allowing some other process to run, or a response to an i/o request will return, preempting the currently running job and allowing us to perform a new scheduling decision.

Multilevel feedback queues approximate shortest remaining time first by having a few priority levels and moving jobs to lower priority when they use more than their allotted quantum.  The idea is over 50 years old:

Corbató, FJ; Daggett, MM; Daley, RC: An Experimental Time-Sharing System, AFIPS Conference Proceedings, Vol. 21, pp. 335-344, 1962.


Clarification of Definition for Functional version of TSP

In definitions of complexity classes, $n$ is always the input length in bits.

Often the definitions are invariant under polynomial blowup (for example, polytime and logspace), and in such cases you can also take $n$ to be other parameters of the input, the resulting class being the same. For example, if the input is an unweighted graph, you can take $n$ to be the number of vertices.


Conditionals with normal order evaluation

Here is the church notation:

TRUE: $\lambda ab.a$

FALSE: $\lambda ab.b$

IF: $\lambda pxy.pxy$

By passing a church boolean as a predicate to the IF function, we choose one of two alternatives. TRUE chooses the first argument passed to it, and FALSE chooses the second.

We can derive COND by folding IF across a list of (condition, result) pairs

You can find wikipedia's explanation here, as well as assorted lambda calculus derivations here.


Booth's algorithm Question : Binary Number Arithmetic (Multiplication)

When you use normal multiplication, multiplicand and multiplier are represented using (Sign + Magnitude) representation. So effectively 1101 is +(13) in Decimal and (1110) is +14 in decimal as they represent the magnitude. Sign bit would be separate. So the result is (+13)*(+14) = +182 which is 1011 0110 in binary.
When you use booth multiplication, operand are in 2's complement representation. So 1101 is -3 and 1110 is -2 in decimal. So the answer will be 0000 0110 that is +6 in decimal. The problem is with your representation of multiplicand and multiplier.


Yes. You can obtain a PDA with only one state by "encodng" the state of your PDA into the stack of the new PDA. See this document.


But the thing is - these sentences are not mathematical objects.

Yes, they are. A set of sentences can be a mathematical object. Just about anything can be a mathematical object.

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

[...] but I don't quite see the relationship with the first definition

Well, "an infinite collection of instances together with a solution for every instance" is a mathematical object (representing a collection of questions that computers might be able to solve).


Comparing floating-point numbers as integers

There are a few fine tricks in the IEEE P754 format, which allows the use of integer operations for comparisons, or for rounding... It is useful for hardware implementations, for CPUs without an FPU, for some optimized libraries that need fast comparisons...

Caveats:
- The sign bit (MSB) must be handled separately.
- NaNs must be checked.

When comparing 0, denormals, normals or infinites of the same sign, integer comparisons work for floating point numbers.


Does every procedure have a structural equivalent?

Every procedure has a functional equivalent, but not a structural equivalent, going by contextual definitions of functional and structural equivalent based on your question.

That every procedure has a functional equivalent is part of the general result that all “reasonable” methods of defining computation result in the same definition of what is computable. This is the Turing thesis.

A model that is close to your definition of procedures is the RAM machine. It's also possible to define a model based more closely on imperative programming with variable names. Two models based on function calls are µ-recursive functions and the lambda calculus. Both of these models require more than the ability to call a function.

With µ-recursive functions, there is a way to iterate calls to a function (the primitive recursion operator) and a way to call functions recursively until a condition is reached (the minimisation operator). Think of the primitive recursion operator as for loops and of the minimisation operator as while loops (building a general while loop requires more than the minimisation operator because that operator extracts only a specific part of the functionality).

With the lambda calculus, functions can be defined and applied to other functions. This unbridled functionality allows building recursive functions and thus arbitrary computations.

All of these models of computation can be proved to be equivalent. I'll refer you to a textbook for a formal proof; I'll just give the intuition here. Given an imperative program, put all of its variables in a single structure. Where functions use local variables, make a chained list of structures. This way you end up with a single variable in your program. In functional programming, this is known as the world state. Now you can pass this single variable as an argument to all function calls and have the functions returned the modified world state. Express all loops and conditional statements using while, and change while (condition) do_stuff() to a recursive call to do_stuff that minimizes the number of iterations (that's where the primitive recursion and minimisation operators get combined). You no longer need any assignment operator! You've converted your imperative program to a recursive functional program.

This transformation lets you convert an imperative program into a functional one. However, it doesn't really help if what you wanted was to know whether your programs are equivalent, because there are many different ways to implement a particular mathematical function in any framework. It's a general result that functional equivalence (determining whether two programs compute the same result) is undecidable: there is no algorithms that given two programs always says (correctly) “yes, they're equivalent” or “no, they aren't equivalent”. This is a special case of Rice's theorem, which informally speaking says that any decidable property of algorithms that depends only on what the algorithm computes (i.e. the mathematical function that it implements) and not on how it computes it is either the property “true for all algorithms” or “false for all algorithms”. This theorem holds for any Turing-equivalent model of computation (because if there was a way to decide a property for programs written in one model, it could be transposed to any model simply by translating the programs).


What defines the interaction between CPU, Memory and I/O parts?

A microarchitecture is a high-level description (in contrast to a hardware-description or circuit-level) of an implementation of an ISA. This includes how instruction bytes get fetched, how many decorders there are and what instructions each can decode, how many functional units there are and for which instructions, the cache hierarchy, how all of these units are connected to each other, and it may also include the number of cores or hardware threads and how they interact with each other and what resources are shared between them.

Main memory and I/O devices are not part of the microarchitecture, but the microarchitecture description includes how it interfaces with components of the system. The term architecture is used to either refer to only an ISA or to both an ISA and a microarchitecture that implements it, depending on the context. Therefore, it also specifies how to communicate with memory and I/O devices, but only in terms of instructions and addresses. You can use the term computer or computer system to refer to the image you've attached. The term CPU may refer to either a single core, a multi-core processor design, or a physical processor package (which may include the DMA and interrupt controllers shown in the image).


How can I prove that there is a decidable language which is not in P?

Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question is not well-formed.

"Polynomial time" is the class P of Turing machines $M$ that have the following property: there is are constants $c$ and $k$ such that, for every input of length $n$, $M$ halts in at most $cn^k$ steps. Notice that this property talks about all inputs, so you can't test it just by looking at one input.

Indeed, it doesn't make sense to ask if a particular input is "accepted in polynomial time." Let the input have length $n$ and suppose that the Turing machine takes $t$ steps to accept it.  We can always find constants such that $t\leq cn^k$. For example, we could take $c=t$ and $k=0$.

You need to look at the time hierarchy theorem which says, loosely, that Turing machines with longer running time can decide more languages than Turing machines with shorter running times. Its proof does indeed use diagonalization, so you started with the right idea.


Your Turing machine just needs to read the first four symbols one the input tape that will be sufficient to to solve the problem $L3$.


Resolution complexity versus a constrained SAT algorithm

While the deductions made by $M$ can have equivalent (possibly exponentially bigger) resolution proofs, I'm not sure what you mean by translating the rule system of $M$ into resolution form. If $M$ has a rule saying that if the problem is a PHP (pigeonhole principle) problem then output unsat if number of pigeons > number of holes, how would you translate that rule into resolution form?
Edit: To elaborate on the last point, we know that Extended Resolution (ER) which in a nutshell, allows one to add new variables, has polynomial-size PHP proofs. Now suppose, $M$ uses ER to prove PHP. Such reasoning cannot be "directly" translated into a resolution proof as that would require adding new variables to the formula which is not allowed in pure resolution proofs.
As I mentioned in point 1, you can translate the deductions by $M$ into resolution proofs of those deductions but the resolution proof might be exponentially larger.


Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing floating-point square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and moreover the range of floating-point numbers is limited. Use a bignum package instead.


In a $k$-way set associative cache,main memory block mapping in range?

Number of sets in cache = v. So, main memory block j will be mapped to
  set (j mod v), which will be any one of the cache lines from (j mod v)
  * k to (j mod v) * k + (k-1). (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence
  reduces the chances of replacement.)

This is a simple concept of k-way set associate mapping.

To understand it better I would like to take an example:

Example:

2-way set associative
4 blocks
Lines of a set are placed in sequence one after another (as in the
question)
The main memory blocks are numbered 0 onwards (as in the
question)

Empty 2-way set associative Cache Memory :

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   -   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Memory reference (data asked for processing) in the order:

4, 5, 9, 7

Reference 4:

4 % 4 = 0 (goes to Block 0 Set 1) Cache miss as it doesn't already present in the cache

As it had 4 blocks, we mod it the reference address to know which location of cache should I put it.

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 5:

4 % 5 = 1 (goes to Block 1 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 9:

4 % 9 = 1 (goes to Block 1 Set 2) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 4:

4 % 7 = 3 (goes to Block 3 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   7   │   -   ║
╚═══╧═══════╧═══════╝

Visualization of Cache memory for you undersatnding:

╔═════════════════════════════════════════════════════╗
║                    Cache Memory                     ║
╠════════════════╤════════════╤═══════════════════════╣
║ Memory address │ References │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       0        │     4      │                       ║
╟────────────────┼────────────┤ Cache line 0 elements ║
║       1        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       2        │     5      │                       ║
╟────────────────┼────────────┤ Cache line 1 elements ║
║       3        │     9      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       4        │     -      │                       ║
╟────────────────┼────────────┤ Cache line 2 elements ║
║       5        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       6        │     7      │                       ║
╟────────────────┼────────────┤ Cache line 3 elements ║
║       7        │     -      │                       ║
╚════════════════╧════════════╧═══════════════════════╝

Both of the two set of cache line 1 is full, therefore calculation the location of first and last element of line gives us the answer.

Lets now check if the answer is option (1) as you mentioned

  (j mod v) ∗ k  to  (j mod v) ∗ k + (k − 1)

Given:

v = 4 (four blocks)

k = 2 (two-way)

First element of cache line 1 = (j mod v) ∗ k = (5 mod 4) ∗ 2 = 2 yes, its located at memory location 2.

Last element of cache line 1 = (j mod v) ∗ k + (k − 1) = (9 mod 4) ∗ 2 + (2 - 1) = 3 yes, its located at memory location 3.

Done.

Answer: (j mod v) ∗ k to (j mod v) ∗ k + (k − 1)


Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.


DFA for binary language with constraints on triplets

Imagine writing a program on any high-level language for checking if string corresponds the given restriction. You would probably iterate symbols one by one and check if appending next symbol breaks the restriction.

Now note that you need only two last symbols to do it,  and there are finite number of two-symbols combinations (namely $--, -0,-1,00,01,10,11$, where "$-$" stands for absence of preceding symbol at the very beginning of the string).

Why wouldn't we use these combinations as automata states? You are left only to add transitions, which are pretty straightforward (e.g. appending $0$ to $11$ transits to $10$, appending $1$ to $00$ transits to the dead state, and so on). Can you finish it now?


What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve?

Your PatternSieve is what is called a wheel sieve, or the wheel optimization for the SoE and is mentioned at the SoE Wikipedia page.  It's well known and used in all fast SoE implementations.  See Wheel factorization at Wikipedia for example.  Pritchard wrote some articles about it in the early 1980s (e.g. A sublinear additive sieve for finding prime numbers and Explaining the wheel sieve).  Sorenson has also written a number of good summary papers over the last 30 years (a recent paper that includes a number of references: Two compact imcremental prime sieves).  I found Quesada and van Pelt's 1996 paper A Note on the Extensions of Erathosthenes' Sieve to be useful, though I believe Sorenson's are better as a whole.

The very basic skip-evens is the first form of this, and is almost always used.  Doing mod-6 (skipping 2 and 3) is oft-used because it's simple, as seen in Robert William Hank's Python examples.  Mod-30 (skipping 2, 3, and 5) is especially popular in high performance implementations because the 8 candidates fit perfectly in one byte.  Going further is less common because of decreasing gains for quite a bit more complexity but mod-210 isn't too bad and primesieve uses that in some cases.  The modulo is the small primorial (e.g. $5\# = 30 \rm{\ and\ } 7\# = 210$), while the number of remaining numbers is $\phi(n)$ (Euler's totient), e.g. $\phi(30) = 8 \rm{\ and\ } \phi(210) = 48$.

You are looking at empirical performance.  This is certainly interesting, but Java is definitely not the best language here, and you would be best served by using properly fast comparisons.  It's fairly well known that properly optimized segmented SoE implementations are faster than the segmented SoA.  E.g. GordonBGood's long analysis.  The SoA you're using is certainly simple and easy to follow, but it's straight from the Wikipedia pseudocode which indicates it skips lots of optimizations.  Even Bernstein's convoluted but fast C implementation is slower than the fastest SoE implementations (though it is optimized enough to beat the simple ones).


Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$

Hint: A string of the form $a^nb^m$ where $n \neq 2m$ can be either

A string with too many $a$'s, or
A string with too few $a$'s

Create production rules for each of these cases.


Proof of Program Correctness - Loop Invariants

Generalities

Regarding your first question, the correctness of every loop (without fancy control flow!) can always be proven using a loop invariant which states all the possible values of all variables. In your case (or rather in the modification below), this loop invariant would be
$$ (n,i,r) \in  \{(0,0,-1),(0,0,0),(1,0,-1),(1,1,-1),(1,1,1),(2,0,-1),(2,1,-1),(2,2,-1),(2,3,-1), \ldots \}. $$
Of course, this invariant isn't particularly helpful, though it can certainly be used to prove the correctness of the loop. A more delicate issue is whether we can actually express the invariant in any formal sense - when the loop always terminates as in this case, the set of possible values of the variables is certainly computable.

Regarding your second question, when you're using a loop invariant you always reason by induction - that's how you know that the loop invariant is actually maintained. Consider the following problem:

x, y = 0, 1
for i in range(n):
    x, y = y, x + y
return x

I claim that this program computes the $n$th Fibonacci number $F_n$. Here is a "loop invariant" that can be used to prove it: if $i = n$ then $x = F_n$. Of course, this is not really a loop invariant since you can't prove that it's maintained by the loop; an actual loop invariant is $(x,y) = (F_i,F_{i+1})$.

Your suggested loop invariant is like the first example above - it's simply not a loop invariant, and in particular it's not clear how you'd prove that if the loop terminates then it holds. It might seem "trivial", but this argument doesn't constitute a formal proof. In contrast, if you use an actual loop invariant, then you can use induction to prove that the loop invariant is maintained throughout the loop, and in particular is satisfied if the loop terminates. That's more formal, and can be turned into an actual formal proof (in the sense of program verification or axiomatic logic).

Whether your type of proof is acceptable or not depends on the venue. If this is a question in a course in which you're supposed to learn how to write this kind of formal proofs, then your answer isn't acceptable. In an algorithms class, it might be acceptable since the proof is "obvious". Ask your professor if in doubt.

Specifics

We now turn to the problem at hand.

The idea of a loop invariant is a condition which is true throughout the loop. As you mention, the condition that you describe is only true after the loop terminates (in the return statement). Ergo, it's not the correct condition. First, let's modify the program in the following way: instead of returning $i$, let's have a variable $r$ initialized with $-1$; when $i^3 = n$, assign $r = i$ and break out of the loop. Throughout the loop one of the following is always true, assuming $n > 1$ (for $n = 0,1$ the program fails; the condition in the main loop needs to be $i \leq n$ instead of $i < n$):

$i^3 < n$ and $r = -1$.
$i^3 = n$. In this case, $r = -1$ if the loop hasn't terminated, and $r = i$ otherwise.
$\sqrt[3]{n} \notin \mathbb{Z}$ and $i^3 > n$ and $r = -1$.

The second condition isn't quite of the usual form, and that is because usually break statements are not allowed. You can correct this by modifying the code as follows (this code also corrects the bug mentioned above):

r = -1
i = 0
while i <= n and r == -1:
    if i*i*i == n:
        r = i
        continue
    else:
        i = i + 1
return r

Now the loop invariant becomes:

$i^3 < n$ and $r = -1$.
$i^3 = n$ and $r \in \{-1,i\}$.
$\sqrt[3]{n} \notin \mathbb{Z}$ and $i^3>n$ and $r = -1$.

Now the loop termination condition makes it clear that if $i \leq n$ then necessarily $r \neq -1$, and so by the loop invariant, $r = i$.


Solve T(n) = T(n-1)*n with repeated substitution

This is the rucursive formula for $n$ factorial.

Define the formula $T(n)$ for $n \geq 0$ as $T(n) = nT(n-1)$. By repeated substitutions observe that
$$ T(0) = 1$$
$$ T(1) = 1\times T(0)=1 \times 1$$
$$ T(2) = 2 \times T(1)=2\times 1\times 1$$
$$ T(3) = 3\times T(2)=3\times 2\times 1\times 1$$
$$\dots$$
$$T(n) = nT(n-1)=n\times (n-1)(n-2)\dots 1\times 1 $$
Thus by simple observation you can easily guess the pattern of product of the first $n$ positive integers.

For a complete proof you need to prove that $T(n) = n!$. This is easily done by induction. For $n=0$, $T(n)=1 = 0!$. Assume that formula is true for $n-1$. Then $T(n)=nT(n-1)=n(n-1)!=n!$ which completes the proof. So $T(n)$ is $\Theta(n!)$.

There is no a standard method to solve such kind of recurrence relations, but you usually guess the explicit form of the formula and proof it, for example, using induction or other technique or method.

As an exercise try to guess and prove explicit formulas for

$T(0) = 1, T(n)=2T(n-1)$
$T(0) = 1, T(n) = nT(n-2)$, for only even $n$s.


Why is non-determinism a useful concept?

Yes, you are correct computers are deterministic automate. Non-deterministic models are more useful for theoretical purpose, sometime the deterministic solution is not as obvious to the definition(or say problem statement) and so little hard to find solution. Then one approach is that first design a non-deterministic model that may be comparatively easy to design and then try to convert it into a deterministic one. Below, I have tried to demonstrate what I mean with an example. Consider regular expression:

(01)*01(0 + 1)*

Now suppose, if you are asked to draw DFA for the language generated by above RE.

With my knowledge of designing FAs, I know that (1) when a * present in regular expression indicated I need corresponding  loop in  FA  (2) concatenate operations like a.b means something like: (q0)─a→(q1)─b→(q2).

So, at my fist attempt I would draw an NFA like:

Thought this is not a deterministic solution but looks very simple FA that can be easily designed using the given regular expression.  My kind-of-analogy to show similarity between the above regular expression and my NFA is as below:

The loop at state  q0 should be for (01)*
01 (after (01)*) gives (q0)─0→(q1)─1→(q2)
(0 + 1)*  gives a self loop at state q2 for label 0, 1

According to my analogy I think the FA I drawn above is comparatively simple to draw from given RE. And luckily in class of finite automata every Non-deterministic model can be converted into an equivalent deterministic one. We have algorithmic method to convert an NFA into DFA. So I can easily convert above NFA into a DFA:

Other part is unfortunately this is not always possible to convert a non-deterministic model into deterministic one, for example class for deterministic push down automate is subset of class of deterministic push-down automate "check venn diagram" and you can't always convert an NPDA into a PDA.

Usually when it is not possible to convert a non-deterministic solution into deterministic one then with the help of non-deterministic solution we define deterministic solution in sub-domain (or say partial domain) instead of complete domain. Or we define solution in some other ways (e.g. greedy approach) that of-course may not give you an optimal solution.

Sometimes non-determinism is an effective mechanism for describing some complicated problem/solution precisely and effectively, for an example non-deterministic machines can serve as model of search-and-backtrack algorithm (read: How string process in non-deterministic model using backtrack). Oppositely deterministic models better represents efficient, minimized and less-redundant solutions.

Here I would also like to quote from Wikipedia Use of Nondeterministic algorithm:

  In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.

  A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.

As @keshlam also mentioned in his comment: "Nondeterminism" is in practice used to refer to any unpredictability in the outcome of some process. For an example, Concurrent programs exhibit non-deterministic behaviour - two executions of the same program with the same input can produce different results (if concurrency control mechanism are not applied ). Read more about this in "Usefulness Of Non Determinism".

I would also suggest you to read following links:
1.  What is the difference between non-determinism and randomness?
2. 9.2.2 Nondeterministic vs. Probabilistic Models: (a). Nondeterministic: I have no idea what nature will do. (b). Probabilistic: I have been observing nature and gathering statistics.
3. Nondeterministic programming


shortest path from start to end in a grid but with a twist

Use any search algorithm, where your state space is the set of tuples $(x,y,d)$ where $(x,y)$ are your co-ordinates and $d$ is a Boolean flag that says whether or not you've already dug through a wall. If $d=\mathrm{true}$, then your available moves are just to move to a vacant adjacent square; if $d=\mathrm{false}$, then your available moves are to move to a vacant adjacent square, or to move into a wall and set $d\leftarrow\mathrm{true}$.


Is it decidable whether a Turing Machine will visit every non-end state from input x?

It's undecidable because you could use it to decide halting.

Because the number of states in a Turing machine is finite you can enumerate all $2^n$ combinations of possible non-end states. Run the algorithm against all of them.

If the algorithm returns yes for a group of states that includes an original end state then the machine halts.

Halting problem is undecidable so the algorithm cannot be executed by a Turing machine.


Can nested structures be encoded more "readably" with a single delimiter?

\n and \t would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot more. You then have an encoding scheme of \n then $x$ \t characters where $x$ is the nesting level. So this:

[a b [c d [e] f]]

in memory becomes:

a\nb\n\tc\n\td\n\t\te\n\tf

visually becomes:

a
b
    c
    d
        e
    f

As Evil mentions, you could similarly remove \n and \t between characters at the same level to achieve something like this:

ab
    cd
        e
    f


Prove a^4n b^m is irregular using puming lemma

Yes, you can use the pumping lemma. It looks like your line of thoughts just had a minor glitch.

Suppose your adversary claims the pumping lemma for $L$ works for some number $p\ge1$.
You can pick $z=a^{4(p+1)}b^p$, a word that "barely" satisfies the requirement.
Your adversary claims $z=uvw$ where $|v|\ge1$, $|uv|\le p$ and for all $n\geq 0$, $uv^{n}w\in L$.

Since $|uv|\le p<4(p+1)$ and $z$ starts with $4(p+1)$ consecutive $a$'s, there must be no $b$ in $uv$. That is, $v=a^i$ for some $i=|v|\ge1$.

Consider $uv^0w=uw$. Since $z$ "barely" satisfies the requirement, removing some $a$'s without removing any $b$ will make $z$ not satisfying the requirement. You have beaten your adversary, again.

The above proof works, in fact, for any language $M$ such that $L\subseteq M\subseteq \{w\mid \#_a(w)\ge4(\#_b(w)+1)\}$.

I have been saying "$z$ 'barely' satisfies the requirement", since it is easier to understand that way although it is not very rigorous. It should be quite easy for readers to make it rigorous.


It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$.

The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration.

The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{dividend}$ the highest multiple $x = k \cdot \text{divisor}$ such that $k=2^i - 1$ for some integer $i$ and $x \le \text{dividend}$.
This is true because initially $k \le \log ( 1+ \frac{\text{dividend}}{\text{divisor}})$ and the same value of $i$ cannot be selected more than two times in a row since $3 \cdot (2^i - 1) = 3 \cdot 2^i - 3 = 2^{i+1} + (2^i-3) \ge 2^{i+1} - 1$.

This analysis is tight in the following sense:
let $\text{divisor}=1$ and $S_j = \sum_{i=0}^j (2^i - 1)$. Let $\text{dividend}= S_\ell$ for some $\ell \ge 2$ of choice.

Clearly $S_j > 2^j - 1$. Moreover, we can show by induction on $j$ that $S_j < 2^{j+1}-1$.

The base case $j=0$ is trivial: $S_0 = 0 < 2^1 - 1 = 1$.
Suppose now that the claim is true for $j-1$:
We have $S_j = S_{j-1} + (2^j - 1) < 2^j - 1 + (2^j - 1) = 2^{j+1} - 2$.

This means that when divisor is $S_j$, the inner loop will subtract $2^{k}-1$ where $k=j$ (in $k-1$ iterations), and the divisor will become $S_{j-1}$. It follows that $\ell$ iterations of the outer loop are needed to reach $S_0 = 0$.

The overall number of iterations of the inner loop is then:
$$
\sum_{i=1}^\ell (i-1) = \sum_{i=0}^{\ell-1} i = \frac{\ell (\ell-1)}{2} = \Theta(\ell^2).
$$

But $\ell \ge \log S_\ell$, since $S_\ell$ has at least $\ell$ binary digits and hence the above quantity is $\Omega(\log^2 S_\ell) = \Omega(\log^2 \text{dividend}) = \Omega(\log^2 \frac{\text{dividend}}{\text{divisor}})$.


Clustering index is applied when records are physically ordered on a nonkey field(called clustering field). As clustering field is nonkey so there can be more than one distinct record for a single clustering field value.

The strategy of clustering index is: There is one entry in the clustering index for each distinct value in the clustering field, containing the value, and a pointer to the first block in the data file that has a record with that value for its clustering field.

So clearly it is a sparse index.


Continuation-passing style: what is meant by "CPS'ing"?

I had only a quick look at the paper, but I believe that they are referring to moving from
$$
    t_1 \to t_2 \cdots \to t_n
$$
to
$$
    t_1 \to t_2 \cdots \to \lnot \lnot t_n
$$
where $\lnot t = (t \to r)$ for some fixed return type $r$. In the paper, they choose $r = \sf Type$. So, we get
$$
    t_1 \to t_2 \cdots \to (t_n \to {\sf Type}) \to {\sf Type}
$$
In the case of the state monad we get
$$
    state \to ((a \times state) \to {\sf Type}) \to {\sf Type}
$$
which is isomorphic to (exchanging the order of the arguments)
$$
    ((a \times state) \to {\sf Type}) \to state \to {\sf Type}
$$

Anyway, Sect. 2.3 of the paper shows the actual transform.


Which implementation for the Maclaurin Series for the cosine function is better?

The main problem with the iterative approach is that the terms of the series get smaller and smaller with increasing index, so if you sum terms from 1 up, you eventually end up adding values of very small magnitude to accumulated sums of much larger magnitude.  When done using floating-point arithmetic, that's pretty much the same as simply discarding terms after some point.  The recursive approach sums the same terms, but in reverse order, so all the small terms get a chance to accumulate into larger sums before the larger terms get added; this lets the smaller terms actually contribute to the final sum.

I suspect that the way the recursive approach builds up the larger factorials in small steps also helps produce more accurate sums.


What is the best hash functions for millions of String keys?

hash = (hash + getChar(strlen, i)) * 123456791


What is the difference between consensus and mutual exclusion in Distributed Systems?

If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed database systems when they are doing leader election to decide which machine will accept writes (this has to be mutually exclusive).

However, different algorithms for mutual exclusion provide different guarantees of progress in the presence of failures; those that are fully fault-tolerant are essentially equivalent to consensus; those that aren't, are weaker.


Given a valid combination, how to get its index in the sequence of integer partition

This is called ranking combinatiorial objects, in this case combinations. Ranking and unranking algorithms exist for various simple combinatorial objects and even a general ranking algorithm exists for arbitrary combinatorial objects given that computing the number of objects matching certain criteria is feasible and there is a total ordering (eg lexicographic ordering).

For combinations, a reference is Algorithms for Unranking Combinations and Other Related Choice Functions, Zbigniew Kokosinski 1995

Assuming a lexicographic ordering among combinations of $K$ from $N$ the following algorithm can be used (which runs in $O(K)$ time assuming binomial computations are cheap):

Assuming the combination is given as an array (item) of length $K$ and where

$$item[0]<item[1]<\dots<item[K-1]$$

and each $0 \leq item[i] \leq N-1$

(If you want the combination in reverse order simply change the algorithm below to match in reverse order and skip last step. Also since your combinations take values between $1$ and $N$ you might want to subtract $1$ from below algorithms, where $item[i]$ is used)

$index = 0$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

Note: The algorithm above can be modified to rank combinations with repeated/duplicate elements. Ie

$$item[0] \leq item[1] \leq \dots \leq item[K-1]$$

One needs to replace the counts used to represent combinations with repeated elements instead of binomials which count combinations with unique elements.

$index = 0$

$N \leftarrow N+K-1$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]-i+1$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

In essense ranking combinations is a bijection from $N,K$ combinations to natural numbers $0 \dots \binom{N}{K}-1$. This defines a combinatorial number system.

Algorithms above are modified to match my use case (for my combinatorics library Abacus) where combinations take values $0 \dots N-1$ and are non-decreasing. For your use case you can modify them to match wikipedia article.


Set relationship between Big-Oh and Theta notations

In general, a proposition $P$ is said to be stronger than $Q$ if $P$ implies $Q$ ( symbolically, $P\Rightarrow Q$)  and $NOT$( $Q$ implies $P$).  In the example at hand, $f \in \Theta(g) \Rightarrow f \in \mathcal{O}(g)$ , so that $f \in \Theta(g)$ is a stronger assertion than $f \in \mathcal{O}(g)$.


What is a limitation of using an array concerning capacity?

Array is defined to have continous memory, so there is a need to extend it by finding continous block that fit it in.
Also the array size is given in advance.
The limit is the largest available continous block and possibility to index it.

For example C defines $malloc$ and $realloc$, which seeks such block (it may start in the same place as original array).
$realloc$ when finds larger region in different place rewrites the content of the array.

If there is no constraint about continous regions - there are lists of arrays used - smaller blocks connected in linked list, easier to grow, but a bit slower to operate on.

Some languages provides growing arrays, but internally it could be stack, list or anything else, so definition of "what is array" is crucial.


It is indeed the case that $FNP\subseteq FPSPACE$. Recall that a function in $FNP$ is of the form

  Given an input $x$ and a polynomial-time predicate $F(x,y)$, if there exists a $y$ satisfying $F(x,y)$ then output any such $y$, otherwise output 'no.'

source: Complexity Zoo

To see that every problem in $FNP$ is also in $FPSPACE$, note that we may enumerate over all possible $y$ (which can have at most polynomial length) and test whether the predicate holds for any of them. This all can be done in polynomial space, since $y$ is of polynomial size and computing the predicate is polynomial-time (and thus polynomial-space).

Whether the inclusion is strict depends on how you view an $FPSPACE$ machine. The most common definition is to have a polynomial "working" tape and an unbounded (write-only) output tape and in this case, $FNP\subsetneq FPSPACE$ because the output can be exponential. If you restrict the output to what is on the working tape (and thus the output is polynomially bounded), then the question is open (and depends on whether $NP=PSPACE$).


How do you create a sentential form in a given grammar?

If you know how to decide whether a word belongs to the language generated by a grammar, then you can extend this to sentential forms, in the following way. For each nonterminal $A$, add a new terminal $\mathbf{A}$. Add rules $A \to \mathbf{A}$. Given a sentential form, replace each nonterminal $A$ with the terminal $\mathbf{A}$. Now ask whether the resulting word belongs to the language generated by the augmented grammar.
As an example, your grammar turns to
\begin{align}
S &\to aBS \mid abT \mid a \mid \mathbf{S} \\
T &\to d \mid dT \mid \mathbf{T} \\
B &\to da \mid \epsilon \mid S \mid \mathbf{B}
\end{align}
The original grammar generates $aBaabda$ iff the augmented grammar generates $a\mathbf{B}aabda$.


If A is NL-complete then complement of A is also NL-complete?

Start with the definition of $coNL$.
$$coNL = \{A\mid \overline{A} \in NL\}$$
Since $NL=coNL$, every $coNL$-complete language is $NL$-complete as well.
Let $A$ be a $NL$-complete problem. Then
$$\forall B \in NL,B \leq_L A$$
or equivalently
$$x \in B \Longleftrightarrow f(x) \in A, \text{  where } f \text{is logspace computable}$$
$$x \notin B \Longleftrightarrow f(x) \notin A, \text{  where } f \text{is logspace computable}$$
$$x \in \overline{B} \Longleftrightarrow f(x) \in \overline{A}, \text{  where } f \text{is logspace computable}$$

and so $$\forall \overline{B} \in coNL,\overline{B} \leq_L \overline{A}$$
This shows that $\overline{A} $ is $coNL$-complete and hence $NL$-complete (since $coNL=NL)$.


I believe the reason for favoring regular expressions over LALR(1) grammars for accepting simple grammars stems from the time needed to build an LALR(1) automaton. Let $m$ denote the size of the grammar which is used to build the automata for accepting the language defined by said grammar. If you need to build up the accepting automaton during runtime you will probably want to use regular expressions because building up an LALR(1) automaton will take $O(m\cdot 2^m)$ which does not include the necessary testing if the input grammar even is LALR(1) ($O(m^3)$). Regular expressions instead can be build up quite easily, the check can occur during conversion (see [1] , re2post).

Adding to the speed gained when building up different regular expressions during different program runs modern regular expressions, mostly PCRE, are NP-Complete, thus very powerful (see for instance [2]). Additionally, with most languages supporting regular expressions there also is an interactive environment to check if the regular expression really expresses your intention, which is more efficient from a programmer's perspective than to write the grammar, generate the parser and do a test and then reiterate the process. I believe this to be the main reason for using regular expressions over LALR(1) grammars.

If you are interested in the implementation and runtime aspects of grammars [3] might also be of interest to you.

[1] http://swtch.com/~rsc/regexp/

[2] http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

[3] Gerhard Goos, William Waite, Compiler Construction, Springer, Jan 1984 ( symbolaris.com/course/Compilers/waitegoos.pdf)


State complexity of difference of two languages

This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ and any $m$.
It is an interesting question whether the bound is tight for all $n$. This is likely the case if we take for $L(A_1)$ the language $(\Sigma^n)^*$.


Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?

Sure you can use the pumping lemma,

String in $L$ consists of four consecutive segments: a $A$ segment followed by a $B$ segment followed by another $A$ segment followed by another $B$ segment.
Assume that $L$ is context free and let $p$ denote the pumping length of $L$. consider the string $A^pB^pA^pB^p\in L$.We can write this string as $uvxyz$ where $|uxy|\leq p$ and $|uv|>1$. We look at two cases:

case 1: Either $v$ or $y$ contains more than one type of character (i.e at least one of $v$ and $y$ contains both $A$'s $B$'s). In this case, pumping up once to $uv^2xy^2z $ inserts an extra $A^iB^j$ sequence into $s$ i.e the resulting string will contain at least $3\quad A$ segments and $3\quad B$ segments. For instance, if $v=AABB$, then pumping once would result in an additional $AA$ segment followed by an additional $BB$ segment. But string in $L$ contain only four segments
case 2: Both $v$ and $y$ contain only one type of character (i.e they are both all $A$'s or all $B$'s). Since $uxy\leq p$, $uxy$ contains letters from at most $2$ segments of $s$. Pumping once to $uv^2xy^2z$ increases the number of characters in one or two of the segments, but leaves the remainig segments untouched. Thus, the number of characters in each segment will be unbalanced.


Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

Citing CLRS 3ed pp. 94-95:

  In the first case, not only must $f(n)$ be smaller than $n^{\log_b a}$, it must be polynomially smaller. That is, $f(n)$ must be asymptotically smaller than $n^{\log_b a}$ by a factor of $n^\epsilon$ for some constant $\epsilon > 0$.

  Note that the three cases do not cover all the possibilities for $f(n)$. There is a gap between cases 1 and 2 when $f(n)$ is smaller than $n^{\log_b a}$ but not polynomially smaller.

For your case we have:
$$\begin{align}
f(n) & = n \log n\\
n^{\log_b a} & = n^2\\
\end{align}$$

We can then show:
$$\begin{align}
f(n) & = n \log n\\
& < n^{2-\epsilon} & ^{*}\text{for } \epsilon < 1\\
& < n^2 & \text{for } \epsilon > 0\\
\end{align}$$

Then you see we can pick a $\epsilon$ value in the range $(0, 1)$ to get a polynomial difference of at least $n^\epsilon$ because:
$$ f(n) < n^{2-\epsilon} < n^2$$

So yes, it is admissible, but your caution is noteworthy, because there are cases where the Master Theorem can not be applied in scenarios similar to this. One example would be the following:

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

You see $\frac{n}{\log n}$, while smaller than $n$, is not polynomially smaller, thus we cannot use the Master Theorem.

$^*$: A polylogarithmic function grows more slowly than any positive exponent


The same answer you'd get on The Great Outdoors Stack Exchange: it's one of these.

Photo: ridge from Mount OtenSho to Mount Tsubakuro, Japan. By Alpsdrake; public domain; from Wikipedia

On a plateau, your value doesn't change much if you move in any direction. On a ridge, your value doesn't change much if you move in one direction, but it falls a lot if you move in the other directions.


How can I explain to my parents that I study programming languages?

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge that they do this task methodically: if this number is greater than 9, then add a carry, and so forth. This description they just gave of what to do that is an example of an algorithm.

This is how I teach people the word algorithm, and in my experience this has been the best example. Then you can explain that one may imagine there are more complex tasks that computers must do, and that therefore there is a need for an unambiguous language to feed a computer these algorithms. So there has been a proliferation of programming languages because people express their thoughts differently, and you're researching ways to design these languages so that it is harder to make mistakes.

This is a very recognizable situation. Most people have no concept that the computers they use run programs, or that those programs are human-written source code, or that a computer could 'read' source code, or that computation, which they associate with arithmetic, is the only thing computers do (and data movement, and networking, maybe).

My research is in quantum computing, so when people ask me what I do, I don't attempt to explain that. Instead, I try to explain that quantum physics exists (they've usually heard of Schrödinger's cat, and things that are in two places at once), and that because of this strange physics, faster computation might be possible.

My goal is to leave the person feeling a little more knowledeable than they did going in, feeling excited about a world they didn't know existed, but with which you have now familiarized them. I find that that's much more valuable than explaining my particular research questions.


A possible solution would be generating (in Apriori terms) a "transaction" that contains indexed symbols and mine that for frequent itemsets.


Fixed point, what does it mean in the world of computer science

In computer science, the arguably most prominent use of fixed-points is in lattice theory¹. A lattice is a partially ordered set $(S, \leq)$ with the additional property that given any two elements $x,y \in S$, the set $\{x,y\}$ has both a supremum and infimum (in $S$).

Now you often consider monotone functions $f$ on this lattice which "converge", that is for some $x \in S$ you have $f(x)=x$. Important results in this area are Kleene's fixed-point theorem and the Knaster-Tarski theorem.

A prominent example is the lattice $(2^A,\subseteq)$ for $A$ some set, and $f$ induced by an inductive definition. For example, let $A = \{a,b\}^*$ and we define a language $L \in 2^{\{a,b\}^*}$ by

$\qquad \begin{align}
  \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\
  aw \in L &\implies baw \in L \\
  bw \in L &\implies abw, bbw \in L
\end{align}$

This inductive definition corresponds to the monotone function

$\qquad \displaystyle f(A) = \{\varepsilon, a\} \cup A \cup \{baw \mid aw \in L\} \cup \{abw, bbw \mid bw \in L\}$

By Knaster-Tarski theorem, we know $f$ has a smallest fixpoint which is a supremum of all smaller "intermediate results" (which correspond to finitely often applying the constructors of the inductive definition), and that smallest fixpoint is indeed $L$.

By the way, the largest fixpoint also has uses; see here for an example.

In recursion theory, there is another fixed-point theorem, also due to Kleene. It says²,

  Let $\varphi$ a Gödel numbering³ and $ r :\mathbb{N} \to \mathbb{N}$ a total, computable function (intuition: a compiler). Then there is $i \in \mathbb{N}$ such that $\varphi_{r(i)}=\varphi_i$.

In fact, there are even infinitely many such $i$; if there where only finitely many, we could patch $r$ (by table-lookup) to not have fixed-points, contradicting the theorem.

Everybody uses it every day, even if you don't realise it.
I don't like that Wikipedia article; you are probably better off checking a genre book.
A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.


You want to estimate
$$
S := \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} (n-i).
$$
You can start with the formula
$$
S(m) := \sum_{i=1}^m (n-i) = m \left(n - \frac{m+1}{2}\right).
$$
The formula for $S(m)$ is an increasing function for $m \leq n-1/2$ (as you can check by computing the derivative), and so $\sqrt{n} - 1 < \lfloor \sqrt{n} \rfloor \leq \sqrt{n}$ implies (for $n \geq 2$) that
$$
S(\sqrt{n}-1) < S \leq S(\sqrt{n}+1).
$$
Substituting, we get
$$
n^{3/2} - \frac{3}{2}n + \frac{\sqrt{n}}{2} < S \leq n^{3/2} - \frac{n}{2} - \frac{\sqrt{n}}{2}.
$$
Therefore $S = n^{3/2} - O(n)$. In particular, $S = \Theta(n^{3/2})$.

We can also get an exact formula:
$$
S := \lfloor \sqrt{n} \rfloor \left(n - \frac{\lfloor \sqrt{n} \rfloor + 1}{2}\right).
$$


Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking?

I'll put the two inequalities together, for readability: $i^2 \leq x < (i+1)^2$.

Taking the positive square of a positive number is a monotone function. Hence,
$$i^2 \leq x < (i+1)^2 \implies i \leq |\sqrt{x}| < i +1$$

Then, the interger part of $|\sqrt{x}|$ is obviously $i$.


Let the index of the central item be $c$, and the length of the list be $2r+1$. We assume that the indices of the list are $0,\ldots,n-1$.

There are four cases to consider:

If $n > 2r+1$, then the results are undefined (per your post).
If $0 \leq c-r$ and $c+r \leq n-1$, then you just take elements $c-r,\ldots,c+r$.
If $c-r < 0$, then you take elements $0,\ldots,2r$.
If $c+r \geq n$, then you take elements $n-2r-1,\ldots,n-1$.

In the latter two cases, we are guaranteed to be within bounds since $n > 2r+1$.


lower bound proof with adversary argument

Here comes $A$ (is it Apass?), the simple smart adversary Walkman.

For the first 18 pairs of batteries you put into $A$ to test, $A$ will just not operate. So you will need at least 18 tests before finding 2 full batteries. On the other hand, the accepted answer to another question by OP shows 18 tests is enough. So the desired lower bound is 18 tests.

The real question is, of course, does this behavior of $A$ come from an actual combination of batteries regardless of whichever 18 pairs of batteries are chosen to be tested?

The answer is yes.

Instead of proving for the case of 30 batteries and 18 tests, let us prove the general cases, which is actually easier since we can use mathematical induction.

(Consistency of $A$) Let $n\ge2$ be a positive integer. $S=\{\{i,j\}\mid 1\le i\lt j\le 2n\}$ with $\#|S|\le n+3$. Let $B=\{i\mid1\le i\le 2n\}$. Then there exists a function $f: B\to \{0,1\}$ such that $|f^{-1}(0)|=n$ (and hence $|f^{-1}(1)|=n$ as well) and for each $\{i,j\}\in S$, if $f(i)\ne 0$, then $f(j)=0$ (If we interpret 0 as an empty battery, this means no pair in $S$ will make $A$ operate).

Proof by induction on $n$

$n=2$. $|S|\le5$. Since there are 6 different pair of numbers can be drawn from $\{1,2,3,4\}$, there is one pair of numbers which is not in $S$. WLOG, let that pair of numbers be 1 and 2. Let $f(1)=f(2)=1$ and $f(3)=f(4)=0$. Case proved.
Suppose it is true for $n$. Let us consider the case of $n+1$, where
$S'=\{\{i,j\}\mid 1\le i\lt j\le 2(n +1)\}$ with $\#|S'|\le(n+1)+3$ and $B'=\{i\mid1\le i\le 2(n+1)\}$.
Since $\#|S'|=n+4$ and each element of $S'$ has two numbers, the total number of appearances of numbers in all elements of $S'$ is $2(n+4)$, which is smaller than the double of $2(n+1)$. So there must be one number that appears less than 2 times. WLOS, let that number be $2n+2$. There are two cases.

If $2n+2$ appears in $\{j, 2n+2\}\in S'$ for some $j$, WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.
If $2n+2$ does not appear in any element of $S'$, choose any element $j$ that appear at least once in some element of $S$. WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.

Consider $S=\{\{i,j\}\in S'\mid 1\le i\lt j\le 2n \}$. Since either $2n+2$ or $2n+1$ appears in one of elements of $S'$, $\#|S|\le\#|S'|-1\le n+3$. By induction hypothesis, we can define $f$ on $B$ such that $f^{-1}(0)=n$. Extend $f$ by letting $f(2n+2)=1$ and $f(2n+1)=0$. Now we can see that $f^{-1}(0)=n+1$ and for each $\{i,j\}\in S'$, if $f(i)\ne 0$, then $f(j)=0$, thus concluding our proof.

Apparently, Turán lemma is not needed if it can be useful here at all.

Here are several related exercises I designed for the interested readers.

Exercise 1. Check that the original question is the case when $n=15$.

Exercise 2. Verify the last statement of the above proof.

Exercise 3. (the case of 3 batteries) Another Walkman needs 3 full batteries to operate. Let's say we have a mixed set of 30 batteries, 20 of which are empty and the remaining 10 of which are full. The only way to test whether a battery is full or empty is to put 3 of them in the Walkman and try it out. However, we can not tell which one is empty or full when the Walkman does not operate. What is the minimum number of tests that guarantees to identify 3 full batteries? Prove your answer.

Exercise 4. What is the average number of steps for the testing strategy shown here? Can we do better (this last question is a research topic)?


An efficient algorithm to find a shortest cycle including a specific vertex

You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).

An important property of BFS is that if it runs from vertex $v$, then every vertex $s$, when it is first reached, then the path that was found from $v$ to $s$ is minimal. Thus, reaching $v$ from $v$ with BFS finds the shortest path from $v$ to itself, namely the shortest cycle that contains $v$.


Grammar of regular languages vs. context free languages

If the language is regular, then it can be defined using rules of the form $A \to \sigma B$ and $A\to \varepsilon$ by just simulating a finite state automaton. Here the nonterminals $A,B$ represent states of the automaton, and a production of the first type corresponds to a transition from $p$ to $q$ with label $\sigma$. The latter type of productions is for a final state $A$.  Thus, when we use this construction the number of variables equals the number of states. As we know this number cannot be bounded.

Grammars of this type are called right-linear. Nowadays they are sometimes called regular grammars (but I am not fond of this as I would prefer regular to distinguish the expressions of that name).

If you do not like $\varepsilon$-production then we can take productions $A\to \sigma$ for transitions leading into a final state. But in this way we cannot produce the empty string.

Every context-free language can be generated by rules of the form $A \to \sigma B_1\cdots B_m$.  This is called Greibach normal form. In general we can restrict to $m\le 2$ for this normal form. Restricting to $m\le 1$ will (of course) give only regular languages.

Greibach normal form is special as in each derivation step a letter is produced.


Can the zero-one principle be used to prove the stability of a sorting network

You can use a $0/1/2$ principle, in which the inputs are $\{0,1,2\}$, and $1$-inputs are also annotated by their indices. The network should sort the input successfully, maintaining the order of the $1$-entries. This is clearly a necessary condition, and it's not too hard to show that it is sufficient.

That doesn't quite answer your own question, though I conjecture that your criterion isn't sufficient. All one needs to do in order to prove my conjecture is to give a sorting network satisfying your condition but not mine. You can try looking for such a network using a computer. If you can find no such network, perhaps your criterion does work after all.