Is unary language with polynomial power context sensitive?

Not true for linear polynomials.  E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar  'S --> aaaS | aa'.  [unless you mean 'at most context-sensitive', not 'exactly context-sensitive']

The Pumping Lemmas for both regular and context-free grammars seem to imply that any language over a 1-letter alphabet can be decomposed into a (not necessarily disjoint) union of sub-languages corresponding to linear polynomials.  If the set of linear polynomials in question can be made finite (which I suspect must be true, but I can't prove or disprove off the top of my head [and I am not sure it even matters]), then any higher-degree polynomial must take on values not achieved by any polynomial in the linear set, in which case such languages must be at least context-sensitive.

Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b_km+c_k$ consecutive $a$s for some constants $b_k$, $c_k$ [think "Horner's Method"] and then 'cascades' to the next sub-grammar.

So if you mean 'at most context-sensitive', then yes.


Operator overloading is an example of syntactic sugar — a notation that doesn't give any extra power but makes programming easier. I don't know the rationale for the decisions in Java and in Python, but see below. See also this answer on stackoverflow.

First, I would like to critique the page you were linking. Let's consider the points raised there one by one.

Simplicity and cleanliness: It is claimed that operator overloading slows down the compiler and the JVM (!). This is non-sense. It's plain wrong for the JVM, since this is just syntactic sugar so it wouldn't affect the generated code at all. As for the compiler, the compiler is already equipped to parse infix operators and to resolve virtual methods, so supporting operator overloading won't make it more complex. On the flip side, operator overloading makes the Java code simpler and cleaner: compare a.add(b) to a+b.
Avoid programming errors: It is claimed that non-standard semantics for operators might confuse programmers. Compare this to C++'s use of >> and << in streams. I think this point is valid but overstated. The same point could be made with regard to other conventions. It's up to the programmers to not abuse the capabilities of the language.
JVM complexity: It is claimed that operator overloading complicates the JVM. As stated above, at the JVM level there would be absolutely no difference.
Easy development of tools: It is claimed that operator overloading complicated the design of IDEs. The answer here is very similar to the answer to the first point. The only complication with operator overloading is that you have to figure out the type of the operands, but presumably if it makes any difference you would need to do it anyway since there are also several different number types, say integer and floating point.

A point which is not raised is that operator overloading might complicate optimization since certain algebraic identities hold for numbers but not in general. This criticism is wrong for the following reason: algebraic identities cannot in general be used even for floating-point computations, since order of operations makes a difference. So the compiler needs to determine the type of the operands anyway, and could easily abstain from optimizing user defined operators.

The Python philosophy is to supply the coders with the rope to hang themselves. If you're a good coder, you will use the rope for good, say for tying your bicycle in the train, rather than to hang yourself or anybody else. Python trusts programmers more than Java, by design. See the second point above.

Let me end this answer by quoting an excellent answer to the stackoverflow question mentioned above:

  I left out operator overloading as a fairly personal choice because I had seen too many people abuse it in C++.

James Gosling. Source: http://www.gotw.ca/publications/c_family_interview.htm

  Many C++ design decisions have their roots in my dislike for forcing people to do things in some particular way [...] Often, I was tempted to outlaw a feature I personally disliked, I refrained from doing so because I did not think I had the right to force my views on others.

Bjarne Stroustrup. Source: The Desing and Evolution of C++ (1.3 General Background)


Is there such a thing as an "or" case in a dependency graph?

It's possible to represent a general boolean function as a directed acyclic graph. Wikipedia has examples of this on the binary decision diagram and propositional directed acyclic graph pages.

In the case of the PDAG, the up triangle represents AND, the down triangle OR, and the diamond represents NOT. The PDAG seems to be the closest to an AND/OR dependency graph, with the topmost element only having its requirements satisfied if the function would yield a 1.

To represent this mathematically, you could use Boolean algebra.


Given an array with N elements and an array of N indices find the lowest possible amounts of swaps

Hint: Assume you have four items that are in order a,b,c,d but you want them in order b, c, d, a. How many swaps do you need and why?

Then you generalise this to the whole array.


Calculate the number of elements after multiplying/adding two polynomials

If $F$ is the number of terms in $f(x)$ and $G$ is the number of terms in $g(x)$ then the number of terms in $f(x)\pm g(x)$ is between $|F-G|$ and $F+G$, and all cases can occur. If you want to calculate the number of terms, you can first run a loop that checks how many non-zero terms the result has, allocate the needed array, and then do the actual computation. The first pass could be faster, since you are only comparing coefficients, which might be faster than actually adding or subtracting them.

For $f(x) \cdot g(x)$, the number of terms is between $F+G-1$ and $FG$, and again these extreme cases can actually occur. Again you can run a first pass which calculates how many non-zero terms there are, though you'd have to be careful if you want to implement it using constant space and the same time (if it is at all possible). It might be better to calculate the product and then reallocate the result to its actual size.


How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1.

No, this is impossible. Consider $S=\{1,2,3\}$ and $W=3$. Our set $T$ should be $\{a,b,c\}$ such that $a+b=0, c=0$ and $a+b+c=1$.


Do the time and space complexities of a language depend on the Turing machine which is its recognizer?

Yes, you are correct. I applaud your careful reading.

This reading is most obvious if we view a TM as an algorithm (which they are). Clearly, for any computational problem, some algorithms are more efficient than others. Compare bubble sort to merge sort, for example.

But their definition is not wrong, just perhaps a little misleading. Any algorithm can provide a time-bound on a decision problem; but only one of them will be the lowest bound.


First of all LTL is defined over traces. In verification, we typically say that a state satisfies some LTL formula if all of the traces starting in the state satisfy the formula. I henceforth assume that this is what is meant in the question and this definition has been given in your course.

The Until operator is defined over a word as follows:

$$
w \models \psi \mathcal{U} \phi \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models \psi \wedge m^j \models \phi
$$

In this equation, $w^i$ represents the word starting at position $i$, where all letters before position $i$ have been removed. Applied to the concretization $\psi = b$ and $\phi = b$, we have:

$$
w \models b \mathcal{U} b \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models n \wedge m^j \models b
$$

Note that without loss of generality, we can assume that the $i$ searched for in the definition is always 0, because for $j=0$, we need to have $w^0 \models b$ for a word $w$ to be a model of $b \mathcal{U} b$. But then we can also choose $i=0$. Then the definition simplifies to:

$$
w \models b \mathcal{U} b \quad \text{ iff } \quad m^0 \models b
$$

Hence, you are searching for all states for which all outgoing paths start with a $b$ state, which is equivalent to saying that you search for all states in which $b$ hold.


Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children

If a node has $l$ children, with $l \geq 2$ during the inorder visit you have to treat the first $l-1$ children as left nodes, and you have to visit the parent multiple ($l-1$) times, writing multiple times the length of the prefix spelled inside the lcp array.
This, applied to the tree in the image, would yield the correct:
SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

keeping in mind that the edge labeled "$" with the leaf 7 should be the leftmost.


How can a 16-bit or more processor store a byte in a byte-addressed memory

For a one-byte read to address 0x01, the CPU can read a 16-bit value and discard half of it.

For a one-byte write to address 0x01, if the memory architecture doesn't support that directly, the CPU needs to read the 16-bit value at 0x00, then replace the second byte with 0xCD, then write a 16-bit value to 0x00.


How can a spinlock progress when it's busy-waiting?

There might be other CPUs in the system, if one is busy waiting, another can be doing something. Furthermore, if the OS uses preemptive scheduling, the thread doing the busy wait might be preempted and another thread will do something and release the lock for example. The signal might also come from an interrupt handler, for example if the thread is waiting for the completion of some I/O operation, and an interrupt will stop the execution of the thread temporarily, signal the lock, and resume the thread.


According to me answer should be :- AKBJCLIEDHFG

Your answer is ((A)  (K)  ((B) (J) (C)))   (L)   (I)   (((E) (D))  (H)  (F) (G))

Please take a close look at the part ((E) (D)). Here lies the ambiguity/confusion/uncertainty. The ambiguity is whether D is the left subtree or the middle subtree or the right subtree of E.

Because of the limited drawing spaces that shows the tree, it can be argued in a few ways. I could swear that D is meant to be the left subtree or E. On a different day, I might, agreeing with you, insist that D is so apparently the middle subtree of E. On another day, I could stretch myself a little bit, unabashedly claiming that D is in fact the right subtree of E. Unless there are some kind of instructions such as your textbook or whatever material you have been using has defined the rules how to tell the class of subtree from the way is drawn in case of ambiguity, it is impossible to conclude which subtree of E D is.

So your question is reduced to whether there are those kind of rules in your material. Or in your instructor's notes or oral guide. Or, what is general convention in your culture or your context to interpret "left", "middle" and "right". This question is not so much of computer science, but more about linguistics and drawings and culture.

If I had to pick one solution out of no context, I would be very frustrated on deciding whether D is a left subtree or right subtree of E. I would choose one of many possible actions below, without any particular preference.

try finding the context or the rules.
just choose left subtree.
just choose middle subtree.
wave my hands, declaring no value to solve a question that is not well-formed.
presenting two solutions or three solutions, each with its assumption stated clearly.
redraw the graph in the question.
raise a question about that question to seek other's judgements as you just did
had I been a student, my TA should have been my savior and my professor should have been the ultimate arbitrator.
the last option that stands for all the remaining possibilities.

(By the way, I just searched the lecture briefly. I have not found any definitive guide on how to tell left or middle or right subtree. Of course, I might have missed some hints or conspicuous rules.)


Set containment of MinimumBadPrefix and BadPrefix of a Safety Property

For (1), I will only give a sketch at first, in case you want to work it out yourself; I can add some details later if you want. Try proving the following:

$w\in BadPref$ if and only if $w$ has a prefix $u$ which is in $L$.

(2) is already covered quite well by David's comments.


Will this algorithm terminate on any input?

This is my idea for a proof although I am not quite sure whether it works:

Consider $r$, the number of symbols on all right-hand sides and $n$, the number of distinct nonterminals. Each grammar has a specific tuple $(r-n,n)$. Let's define an order on grammars. We first sort by $r-n$ and in case the values are equal by $n$.

Whenever step one fires, $r$ decreases as each rule has at least two symbols on its right hand side. Whenever step two fires, $n$ increases by one and $r$ stays the same (in case only two pairs are found) or decreases (if two or more pairs are found). If the third step fires, $r$ decreases by one and $n$ also decreases by one as one nonterminal is replaced by the whole right hand side of its definition which is removed. Let $G'$ be the tuple of the grammar (whose tuple is $G$) after the application of any of those steps, then:

step 1 always reduces $r-n$ by at least one, $G' < G$
step 2 always reduces $r-n$ by at least one, $G' < G$
step 3 does not change $r-n$ but reduces $n$ by one, $G' < G$

The application of each step reduces the tuple of $G$ to a lower tuple. What is left is to show, that both $r-n$ and $n$ have a lower bound. Per definition $n\ge1$. Since each nonterminal is defined in terms of exactly one rule, $n$ is also the number of rules. Since each rule has at least two symbols on it's right-hand side, $r\ge2n\to r>n\to r-n>0$. The tuples  have a lower bound that is eventually reached. Thus the algorithm must eventually terminate.


Cases where string concatenation is commutative

Simple solution: $a\cdot aa = aa \cdot a$?

In general there is a characterization due to Lyndon and Schützenberger.
For nonempty words $x,y\in \Sigma^+$ the following are equivalent:

$xy=yx$
there exists $z\in \Sigma^+$ such that $x=z^k$ and $y=z^\ell$ for some $k,\ell >0$.
there exist $i,j>0$ such that $x^i = y^j$.

This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.


Solving problems related to Marginal Contribution Nets

I got the following answer:

$v(\emptyset)=0$
$v(\{a\}) = 0$
$v(\{b\}) = 2-2 = 0$
$v(\{a,b\}) = 5+2-2 = 5$
$v(\{a,b,c\}) = 5+2+4 = 11$

Here's a general approach to doing this calculation.
Consider a set $A\subseteq \{a,b,c\}$. Define a map $I_A:\{a,b,c\}\to\{\text{True},\text{False}\}$  as follows:
$$I_A(x) = \left\{ \begin{array}{l@{~~}l} \text{True} & \mbox{if}~x\in A \\
\text{False} & \mbox{otherwise}
\end{array}\right.$$
This is the so-called indicator function of set $A$.

Now take each element of the marginal contribution net and evaluate whether it is true or false given $I_A$. If it is true, add the contribution. If not, add no contribution. More explicitly, given element $\psi\to c$, add $c$ only if $I_A\models\psi$ holds.

Here the notation $I_A\models\psi$ simply means evaluate the truth of the formula $\psi$ given the assignment of the variables $\{a,b,c\}$ to true or false.

Consider $v(\{a,b\})$. This corresponds to the map
$I_{\{a,b\}}=\{a \mapsto\text{True},b\mapsto\text{True},x\mapsto\text{False}\}$. Given this assignment of truth values, we can conclude that:

$a\wedge b$ is true, so $5$ is contributed.
$b$ is true, so $2$ is contributed.
$c$ is false, so nothing is contributed.
$b\wedge\neg c$ is true, so $-2$ is contributed.

Therefore the total contribution is $5+2-2=5$.


Let us first assume that you want to sample within

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

This doesn't make quite a difference, since the sample point will still lie in your requested area with high probability.

Now you are left with sampling a point from a simplex. In the 3d example you get a 2d simplex (triangle) realized in 3d.

How to pick a point uniformly at random was discussed in this blog post (see the comments).

For your problem it would mean that you take $n-1$ random numbers from the interval $(0,1)$, then you add a $0$ and $1$ to get a list of $n+1$ numbers. You sort the list and then you record the differences between two consecutive elements. This gives you a list of $n$ number that will sum up to $1$. Moreover this sampling is uniform. This idea can be found in Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134.

For example  ($n=4$)  you have the three random numbers 0.4  0.2 0.1 then you obtain the sorted sequence 0 0.1 0.2 0.4 1 and this gives the differences 0.1 0.1 0.2 0.6, and by construction these four numbers sum up to 1.

Another approach is the following: first sample from the hypercube (that is you forget about x+y+z=1) and then normalize the sample point. The normalization is a projection from the $d$-hypercube to the $d-1$-simplex. It should be intuitively clear that the points at the center of the simplex have more "pre-image-points" than at the outside. Hence, if you sample uniformly from the hypercube, this wont give you a uniform sampling in the simplex. However, if you sample from the hypercube with an appropriate Exponential Distribution, than this effect cancels out. The Figure gives you an idea how both methods will sample. However, I prefer the "sorting" method due to its simple form. It's also easier to implement.


There's a straightforward way to represent the logical AND of $n$ variables $x_1,\dots,x_n$: add the linear inequalities $y \ge x_1+ \dots + x_n-(n-1)$, $y \le x_i$ for each $i$, and $0 \le y \le 1$.


Find typing derivation of STLC term with reference types

The expression $t$ does not contain any free variables, so one can start typing it with an empty context: $\emptyset\,|\,\Sigma~\vdash~t : \mathrm{Int}$, and attempt to build the full derivation tree in a bottom-up way.

The tricky part of the typing derivation is where we try to type-check the subexpression $(!l_1\,!a)$. Because $(!l_1\,!a)$ lies in the body of a $\lambda$-expression which introduces the variable $a$ of type $\text{Ref Bool}$, at that point the context will be extended with an entry $(a : \mathrm{Ref~Bool})$, therefore $\Gamma=\emptyset,a : \mathrm{Ref~Bool}$.

$\dfrac{\dfrac{(a)}{\Gamma\,|\,\Sigma~\vdash~!l_1 : \mathrm{Bool \to Int}}{\text{T-Loc}}~~~~~~~~~~~~~\dfrac{\Gamma\,|\,\Sigma~\vdash~a : \mathrm{Ref~Bool}}{\Gamma\,|\,\Sigma~\vdash~!a : \mathrm{Bool}}{\text{T-Var}}}{\Gamma\,|\,\Sigma~\vdash~!l_1\,!a : \mathrm{Int}}{\text{T-App}}$

Completing the above sub-derivation by filling in the missing premise in $(a)$, shows what $\Sigma$ we must choose so that $t$ is typable. From the $\text{T-Loc}$ rule, clearly $\Sigma$ must contain the entry $(l_1:\mathrm{Bool \to Int})$.

This contradicts the expectation that $\Sigma(l_1) = \mathrm{Int \to Int}$. But this expectation is there only because we know that $\mu(l_1)$ is a term of type $\mathrm{Int \to Int}$. However, $\mu$ plays no role in the typing of an expression. It only plays a role in the evaluation process.

What is violated here is not the typing of $t$. Indeed, $t$ is straight-forwardly typable by following the typing rules and choosing appropriate $\Gamma$ and $\Sigma$. What is violated is the typing of $\mu$. Following the theory and notation of the book, the judgment $\Gamma\,|\,\Sigma\vdash\mu$ does not hold. Because of this, the preservation theorem does not apply and if you try to evaluate $t$, a run-time error will occur.


How are hash tables O(1) taking into account hashing speed?

The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification.

This is only true if:
- The amount of data to hash per item is trivial compared to the number of Keys and the speed of hashing a Key is fast - $k$.
- The number of Collisions is small - $c$.
- We do not take into account time needed to Resize the hash table - $r$.

Large strings to hash
If the first assumption is false the running time will go up to $\Theta(k)$.
This is definitely true for large strings, but for large strings a simple comparision would also have a running time of $\Theta(k)$. So a hash is not asymptotically slower, although hashing will always be slower than a simple comparision, because comparison has a early opt out ergo $O(1)$, $\Omega(k)$ and hashing always has to hash the full string $O(k)$, $\Omega(k)$.

Note that integers grow very slowly. 8 bytes can store values up to $10^{18}$; 8 bytes is a trivial amount to hash.
If you want to store bigints then just think of them as strings.

Slow hash algorithm
If the amount spend hashing is non-trivial compared to the storage of the data then obviously the $\Theta(1)$ assumption becomes untenable.
Unless a cryptographic hash is used this should not be an issue.

What matters is that $n$ $>>$ $k$. As long as that holds $\Theta(1)$ is a fair statement.

Many collisions
If the hashing function is poor, or the hash table is small, or the size of the hash table is awkward collisions will be frequent and the running time will  go to $O(log(n))$.
The hashing function should be chosen so that collisions are rare whilst still being as fast as possible, when in doubt opt for fewer collisions at the expense of slower hashing.
A rule of thumb is that the hashing table should always be less than 75% full.
And the size of the hashing table should not have any correlation with the hashing function.
Often the size of the hashing table is (relatively) prime.

Resizing the hash table
Because a nearly full hash table will give too many collisions and a big (empty) hash table is a waste of space, many implementations allow the hash table to grow (and shrink !) as needed.
The growing of a table can involve a full copy of all items (and possibly a reshuffle), because the storage needs to be continuous for performance reasons.
Only in pathological cases will the resizing of the hash table be an issue so the (costly but rare) resizes are amortized across many calls.

Running time
So the real running time of a hash table is $\Theta(kcr)$.
Each of $k$, $c$, $r$ on average is assumed to be a (small) constant in the amortized running time and thus we say that $\Theta(1)$ is a fair statement.

To get back to your questions
Please excuse me for paraphrasing, I've tried to extract different sets of meanings, feel free to comment if I've missed some

You seem to be concerned about the length of the output of the hash function. Let's call this $m$ ($n$ is generally taken to be the number of items to be hashed). $m$ will be $log(n)$ because m needs to uniquely identify an entry in the hash table.
This means that m grows very slowly. At 64 bits the number of hash table entries will take up a sizeable portion of worldwide available RAM. At 128 bits it will far exceed the available disk storage on planet earth.
Producing a 128 bit hash is not much harder than a 32 bit hash, so no, the time to create a hash is not $O(m)$ (or $O(log(n))$ if you will).

  The hash function going through $log(n)$ bits of element is going to take $Θ(log(n))$ time.

But the hash function does not go through $log(n)$ bits of elements.
Per one item (!!) it only goes though $O(k)$ data.
Also the length of the input (k) has no relation with the number of elements.
This matters, because some non hashing algorithms have to examine many elements in the collection to find a (non)matching element.
The hash table only does 1 or 2 comparisons per item under consideration on average before reaching a conclusion.

  Why are hash tables efficient for storing variable-length elements?

Because irrespective of the length of the input ($k$) the length of the output ($m$) is always the same, collisions are rare and lookup time is constant.
However when the key length $k$ grows large compared the to number of items in the hash table ($n$) the story changes...

  Why are hash tables efficient for storing large strings?

Hash tables are not very efficient for very large strings.

If $not$ $n >> k$ (i.e. the size of the input is rather large compared to the number of items in the hash table) then we can no longer say that the hash has a constant running time, but must switch to a running time of $\Theta(k)$ especially because there is no early out. You have to hash the full key. If you're only storing a limited number of items then you may be much better off using a sorted storage, because when comparing $k1$ $\ne$ $k2$ you can opt out as soon as a difference is seen.

However if you know your data, you can choose not to hash the full key, but only the (known or assumed) volatile part of it, restoring the $\Theta(1)$ property whilst keeping the collisions in check.

Hidden constants
As everyone ought to know $\Theta(1)$ simply means that the time per element processed is a constant. This constant is quite a bit larger for hashing than for simple comparison.
For small tables a binary search will be faster than a hash lookup, because e.g. 10 binary comparisons might very well be faster than a single hash.
For small datasets alternatives to hash tables should be considered.
It's on large datasets that hash tables truly shine.


Relationship between #of cores and Dynamic Power

The capacitive load of a dual-core system would be (roughly, ignoring, e.g., sharing parts of the memory hierarchy) twice that of a single core system (with the same core implementation), so the formula would be unchanged.

(Of course, the frequency and even the voltage for different cores might be independently adjustable.)


How to check if two sequences of setoid members are mutual rotations?

It might depend on $n$. If $n$ is prime then the following algorithm works in linear time. Compare $a_1$ to all elements in $a$ and to all elements in $b$. The resulting $a_1$ patterns must be congruent, and if they are, then they are congruent uniquely. Once you know the shift, it is easy to check whether the original sequences are congruent.

When $n$ is composite then you might run into trouble since there are several shifts possible. Still, it seems possible but messy to get a linear or quasilinear time algorithm.


Please explain "decidability" and "verifiability"

The key to understand here is that P and NP are classes of decision problems. That means that all of them have yes/no answers.

So when we say a problem like 3-SAT is NP-Complete, it means that given an instance of 3-SAT (aka a word potentially in the language), there is no known efficient way to test if the word is or is not in the language.

To say something is in NP means that there exists some sort of "proof" for each string in the language, which is polynomial in the length of the input.

For example, in 3-SAT, we're asking, does there exist an assignment of True/False to a set of variables in a boolean formula, such that the formula comes out to be true. The word we're testing is the boolean formula. There's no known way to find if there is a single solution that makes the whole formula true. But, if we have a set of true/false values for the variables, it's very easy to check (in polynomial time) if it causes the formula to evaluate to true.

The key point here is that the word we're testing is NOT the true/false values for each variable. The word we're testing is the formula containing the variables, and the language is the set of all boolean formulas which evaluate to true.

We don't know how to efficiently test if the word (formula) is in the language (can evaluate to true), but given a set of true/false assignments, we can verify if it evaluates to true i.e. it is a "proof" that the word (formula) is in the language.
Thus the problem is in NP, but not known to be in P.

NP is actually the class of non-deterministic polynomial solvable decision problems. This is because, in a non-deterministic turing machine, we have "decision" points where we can take one of multiple actions, and our polynomial certifier is basically just telling is which decision to take at each decision point.


De Casteljau's algorithm without temporaries / stack

The OP has indicated in the comments that they are only interested in a specific time $t$. De Casteljau's algorithm can be described as follows:

Input: order $N$, points $A_0,\ldots,A_N$, time $t \in (0,1)$.
Calculate $\overline{A_i A_{i+1}} = A_i(1-t) + A_{i+1}t$ for $0 \leq i \leq N-1$.
Calculate $\overline{A_i A_{i+1} A_{i+2}} = \overline{A_i A_{i+1}} (1-t) + \overline{A_{i+1} A_{i+2}} t$ for $0 \leq i \leq N-2$.
Continue similarly for $N-2$ more steps.
Output $\overline{A_0 A_1 \ldots A_n}$.

It is not completely clear what it does it meant to "implement" De Casteljau's algorithm. However, a reasonable informal interpretation of this statement is as follows:

  Schedule the computations in De Casteljau's algorithm in a way that uses the least amount of space and the least amount of computations.

Note that the two efficiency measures could potentially conflict.

There is an area of theoretical computer science covering exactly such questions, namely pebbling. See Jakob Nordström's survey-in-making. Your task exactly corresponds to pebbling a height $N$ pyramid. On the one hand, this is known to require $N+2$ pebbles (roughly temporary memory locations). On the other hand, there is a pebbling strategy using $N+2$ pebbles and a linear number of steps (a linear number of computations — we are allowing computing each node, i.e. $\overline{A_i \ldots A_j}$, more than once).

Here is how this pebbling strategy looks like in the case $N=2$:

$T_1 \gets A_0$.
$T_2 \gets A_1$.
$T_3 \gets T_1(1-t) + T_2t$.
$T_1 \gets A_2$.
$T_4 \gets T_2(1-t) + T_0t$.
$T_1 \gets T_3(1-t) + T_4t$.

The output is in $T_1$.


What is the initial state of DFA equivalent to an $\epsilon$-NFA?

There is no god-given algorithm for converting $\epsilon$-NFAs to DFAs. You can do it in several ways, and the results could well be different. It could be that your textbook's construction and the one in the software are simply different.


If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log  n).

In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n).

And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.


Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

A pragmatic solution might be to use methods from operations research, e.g., formulate this as an integer linear program or an instance of SAT, and use an off-the-shelf solver.  It's hard to say exactly what the best solution might be without knowing the specific constraints, but these approaches will be the most flexible in accommodating a wide range of possible constraints.


having issue with numbers in Polymorphic Lambda Calculus

The syntax you written is probably of the System F<:.

However, the typed Church numerals you written are introduced in the context of System F (a.k.a. λ2) at Fig. 11 of the source pdf.

The terms of System F are defined like below in Types and programming languages (Benjamin C. Pierce, MIT press, 2002):

t ::=           terms:
      x         variable
      λx:T.t    abstraction
      t t       application
      λX.t      type abstraction
      t [T]     type application

The typed Church numerals at Fig. 11 are terms in this definition.

Moreover, in System F<:, Church numerals are also well-typed and can be more generalized. Below examples are taken from Types and programming languages. Top is the maximum type.

szero = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. z;
sone  = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. s z;


Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope

Your objective function is indeed not convex, but you can make it convex with the appropriate transformation, which means it is solvable in polynomial time. But applying this reformulation is complex: you should try a non-convex solver first and stop there if it works in practice.

The easy way: Non-convex quadratic model

As pointed in the comments, it is a quadratic program, so you can solve it with a non-convex quadratic solver. Although not a polynomial-time algorithm theoretically, these solvers are really efficient in practice.

\begin{align*} {\rm minimize}&~ \sum_{i=1}^n r_i \\
\mbox{ subject to } & \\
& Ax + B y \leq c \\
& r_iy_i \geq x_i \\
& x>0, y>0
\end{align*}

The hard way: Convex fractional programming reformulation

Stated as follows, it is clear that it is a fractional programming problem:
\begin{align*} {\rm minimize}&~ \frac{\sum_{i=1}^n x_i \prod_{j\neq i} y_j}{\prod_{j=1}^n y_j} \\
\mbox{ subject to }& \\
& Ax + B y \leq c \\
& r_i \geq x_iy_i \\
& x>0, y>0
\end{align*}

Both the numerator and denominator are convex, so you can follow the transformation given in the above link to make it convex. This makes it solvable in polynomial time.

$$
\begin{align*}
z_i &= \frac{x_i}{\prod_{j=1}^n y_j} \\
w_i &= \frac{y_i}{\prod_{j=1}^n y_j} \\
t &= \frac{1}{\prod_{j=1}^n y_j} \\
\end{align*}
$$

And solve (yes, the convexity is far from obvious):

$$
\begin{align*} {\rm minimize}& ~ \frac{1}{t^{n-1}} \sum_{i=1}^n z_i \prod_{j\neq i} w_j \\
\mbox{ subject to } & \\
& \frac{\prod_{j\neq i} w_j}{t^{n-1}} \leq 1 \\
& Ax + By \leq ct \\
& z>0, w>0, t \geq 0
\end{align*}
$$


Where we Use Dynamic Programming and Greedy Algorithm?

Greedy Algorithm:

  An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems. [1].

Problems that can be solved by a Greedy Algorithm will have two properties:

Greedy Choice Property;
Optimal Substructure.

Essentially, Greedy Algorithms solve combinatorial problems having the properties of matroid.

For more detail you can consult Introduction to Algorithm.

Dynamic Programming:

  Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.  [2]

Dynamic Programming algorithms are often used for optimization because it will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.

Now, problems that can be solved by a Dynamic Programming Algorithm will have this necessary condition:

  Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. [3]


Cores, threads and sockets: what does it mean the calculation $T = tcs$ and the number on windows task manager performance?

There are two kind of threads, hardware and software threads. The threads number shown in red box is the number of software threads. The threads calculated above(16) is the number of hardware threads.
A processor consists of multiple functional blocks like, register sets, integer ALU, floating point ALU, instruction decoder, instruction fetch units... In a pipelined processor supporting superscalar architecture (also known as hyperthreading or HT on Intel processors), instructions from multiple software threads can be in different phase of execution at the same point of time. The number of software threads instruction sequence which can be concurrently executing in a single processor core is defined by the hardware and are known as logical threads. Look at SMT threads for more clarity.
The number of threads shown is red box or software threads are the total number spawn threads. At most, 16 of them can be executing at the same point of time on the specified hardware. Operating system schedule software threads (in 1000's) on the available processors using some scheduling policy.


Decidable languages kleene star closure - question on a proof

It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be decided or not, regardless of how much time it will take to figure out. Therefore, an NTM will sometimes be more convenient to reason about, as we can abstract the "try all possible ways to do this", into "guess the right way to do this". However, the abstraction is only valid if we have a finite number of possibilities to try, of course.

So, for the Kleene star closure:

Assume that we have a decidable language $A$. Given that $A$ is decidable, there exists a decider for $A$, let us call it $M_A$. From this $M_A$, we can now construct a decider of $A^\ast$, let us call that decider $M_{A^\ast}$.

This is a description of how $M_{A^\ast}$ works:

On input $w$:

If $w = \varepsilon$ (the empty string), accept

For all possible splits of $w$ into $w_1,w_2,...,w_k$: if $M_A$ accepts all the strings $w_1, w_2, ..., w_k$, then accept

If all splits have been tried without success, reject.

Lets look at an example where $A = \{w \in \{a,b,c\}^\ast \; | \; w \; \text{starts with} \; ab \; \text{or ends with} \; c\}$

For instance, we have that $\{c, ab, ac, bc, cc, aac\} \subset A$, but $\{a, b, aa, ba, bb, ca\} \cap A = \emptyset$.

Now, let us look at how $M_{A^\ast}$ will determine whether or not the string $ccab$ is in $A^\ast$:

First, $M_{A^\ast}$ checks the trivial case. Since $w \neq \varepsilon$, it cannot accept right away. It now has to try all the 8 possible splits of $ccab$ listed here:

$S_1 = \{ccab\}$

$S_2 = \{cca, b\}$

$S_3 = \{cc, ab\}$

$S_4 = \{c, cab\}$

$S_5 = \{cc, a, b\}$

$S_6 = \{c, c, ab\}$

$S_7 = \{c, cab\}$

$S_8 = \{c, c, a, b\}$

You could argue that split $1$ is not a real split, but since it complies with our definition of a split, $M_A'$ has to check whether $A$ accepts all $w' \in S_1$, which is only $ccab$. $M_A$ rejects $ccab$ because it does not start with $ab$ or end with $c$.
In $S_2$, $cca$ is rejected by $M_A$, and hence $M_A'$ does not have to check $b$ and proceeds to split $S_3$.
In $S_3$, both strings are accepted by $M_A$. $cc$ is accepted because it ends with $c$, and $ab$ is accepted because it starts with $ab$. The machine $M_A'$ now accepts, and hence $ccab \in A^\ast$, simply because $cc \in A$ and $ab \in A$.


Church-Turing Thesis and computational power of neural networks

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the power beyond that of a Turing Machine. In fact, the title of 1.2.2 is "The meaning of (non computable) real weight", where they discuss why their model is built to include non-computable components.

There are in fact many models of computation that exceed the power of Turing Machines (q.v. Hypercomputation). The catch is that none of these are apparently able to be constructed in the real world (but maybe in the $\mathbb{R}$ world - sorry, couldn't resist).


Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

I had the same thoughts when i did Complexity course myself.
Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine.
This is by definition of space complexity analysis.


If you allow arbitrary $e_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove.

Note that (for very good reasons) NP-hard and its ilk talk about the worst case complexity of the problem (that is well-defined, opposed to say avergage complexity; best-case essentially tells nothing in most interesting cases). That some proof gives just one particular hard case for particular sizes, while another gives a bevy of them, is irrelevant.


Grouping n points into groups of size m with objective to have least traveling distance in each group

It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. But that is an extreme case.

Even an approximation is difficult. I assume each worker goes from company office to location 1 to location 2 ... to location n to company office. I'd try to group far away locations into clusters so that a worker can do a complete cluster and not be left with a single job in a cluster; doing half a cluster one day and the other half the next day would be fine, or picking jobs up on the way. Problem changes if each worker starts at home and ends up at home, then you'd want each one to do jobs near his home.

In reality, you will have new jobs coming in every day, so you need a solution for one day, and then recalculate the next day. Plus take into account that customers waiting a long time will get angry.


How can follow this this guide to construct a graph with matrix/reachability

Okay let's say you got $n$ matrices $M_1,M_2,...,M_n$ with dimensions $a_1\times b_1,...,a_n\times b_n$.
Now we look at what happens to the dimension when we multiply two matrices $M_i, M_j, i\neq j$:
$$(a_i\times b_i)(a_j\times b_j) = a_i \times b_j$$
Notice that you can only multiply the two matrices iff $b_i = a_j = p$:
$$(a_i\times p)(p\times b_j) = a_i \times b_j$$
You might spot the pattern here: only the first dimension of the first matrix and the last dimension of the last matrix matter. Thus in order to get a matrix with dimensions $(x\ times y)$ you need a chain of matrices looking like that:
$$(x \times e_1)(e_1 \times e_2)(e_2 \times e_3)...(e_n\times y) = (x\times y)$$
where $e_i$ are just arbitrary numbers. This looks similar to a path in a graph, where you are walking from the node labeled with x to a node labeled with y.
Notice that for every node in the graph if it represents the first component of the dimension ($a_i$) of a matrix $M_i$ it's connected to the second component of the dimension ($b_i$).
Meaning $a_i$ and $b_i$ are connected. Secondly the second component of a dimension $b_i$ of a matrix $M_i$ is connected to all first components $a_j, i\neq j$ that have the same value ($b_i = a_j$). Now if  there is a path from $x$ to $y$ in a graph you can build an equation as shown above.
The graph in your particular example looks like this:
8(a1) -> 5(b1)
5(b1) -> 5(a2)
5(a2) -> 6(b2)
6(b2) -> 6(a3)
6(a3) -> 8(b3)

Now $8 = a_1 = x$ is your starting point and $8 = b_3 = y$ is your end point.
EDIT: Construction algorithm:
Input: arrays a,b with n elements
Output: adjacency list A of size 2*n
A = new array of 2*n lists
for i = 1 to n: A[i].add(i+n)
for i = 1 to n:
   for j = 1 to n:
      if b[i] == a[j]:
          A[i+n].add(j)

Notice that $A[i\leq n]$ corresponds to the node for $a_i$ and $A[n+i\leq 2n]$ corresponds to the node for $b_{i}$. Now if you want to check if you can build a matrix with a certain dimension $(x,y)$ you search through $a$ to find $i$ such that $a[i] = x$ and start a dfs or bfs from node $i$ which has the neighbors $A[i]$ and you stop your search when you arrive at node $n+j$ such that $b[j] == y$.


permutations sampling by probability matrix

The problem has recently been actively studied:
https://arxiv.org/abs/2007.15043
https://arxiv.org/abs/1904.03836
https://projecteuclid.org/euclid.ejs/1586419218
https://academic.oup.com/comnet/article-abstract/6/6/833/4772759
P.S. It is true, that problem is not fully or correctly defined, but Raphael's comments are at least a bit confusing.


It's easy to make other bases by switching out the combinators from one basis with ones that do something similar. For example, starting with BCKW, you can switch $C$ for $T = (\lambda x y. y x)$ (since both switch terms around) and $W$ for $\omega = (\lambda x. x x)$ (since both duplicate things). You know this is still a basis because you can recover $C$ and $W$ from it: $C = B(T(B B T))(B B T)$ and $W = C(B \omega(B B T))$.


Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b

The idea behind the construction is very simple: when the number of $a$'s and $b$'s read so far is equal, the stack will contain $\bot$. When $k$ more $a$'s were read, the stack will contain $\bot A^k$. When $\ell$ more $b$'s were read, it will contain $\bot B^\ell$.

Our automaton will accept by clearing the stack. We assume that the stack is initialized with $\bot$. The automaton has a single state and the following transitions:

When reading $a$ and the top of the stack is $\bot$, replace it with $\bot A$.
When reading $a$ and the top of the stack is $A$, replace it with $AA$.
When reading $a$ and the top of the stack is $B$, replace it with $\epsilon$.
When reading $b$ and the top of the stack is $\bot$, replace it with $\bot B$.
When reading $b$ and the top of the stack is $B$, replace it with $BB$.
When reading $b$ and the top of the stack is $A$, replace it with $\epsilon$.
There is an $\epsilon$ transition which, when the top of the stack is $\bot$, replaces it with $\epsilon$.

The final transition is used when the input is exhausted, to conform with the acceptance condition of emptying the stack. If we want to use acceptance by final state, we need to add a new state which will be the only final state, and modify the last transition by transitioning into this state.


Simulating multi-tape turing machines by single-tape TM

You can simulate a state machine with set of states $S$ and registers $R_1,\ldots,R_m$ varying over a finite alphabet $\Sigma$ using a vanilla state machine whose set of states is $S \times \Sigma^m$. You "store" a value $x$ in register $R_i$ by transitioning to a state whose $(i+1)$'th element is $x$. You "read" a value from $R_i$ by taking into account in your transition table the $(i+1)$'th element of the current state.

This is the sense in which $\hat{M}$ has registers – their contents are stored in the state of the machine. Here it is crucial that both $k$ and the tape alphabet are fixed and finite.


Doesn't post-order traversal require subtrees to be evaluated separately?

You are right. You finish each sub-tree before printing that sub-tree's root node. The correct order is B, D, E, C, A


algorithm analysis - complex dependant nested loop

The number of print statements executed is
$$
\sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i+1)} 1\right) + 1 \right],
$$
where the second sum is zero if $1 > i-(n-i+1)$.

The running time is proportional to the number of print statements, so it remains to compute the value of the expression above, or at least to give a good estimate. This I leave to you.


Can we use Operator precedence parsing with this grammar?

It's an operator grammar since no right-hand side has two consecutive non-terminals. So we then attempt to construct the precedence relations:

$$b \gtrdot b \\
b \doteq a \\
a \doteq b \\
a \doteq a
$$

There is no multiple entry, so an operator precedence parser is possible.


Algorithms with polynomial time complexity of higher order

The AKS primality test runs in time $\tilde{O}(n^6) \subseteq O(n^7)$, $n$ the length of the input number (in binary). This is the best known bound; as far as I know, there is no proven lower bound.


Given asymptotic bounds, what can we say about small n?

Nothing. If all you know about two functions is their $O$/$\Omega$ relations, you know nothing about how they relate to each other on any finite prefix.

Yes, this makes asymptotics of, say, runtime functions absolutely useless in terms of questions like, "which algorithm should I use in scenario X?" On first sight, that is.

Luckily, we usually do analyse with more detail but throw them away when formulating the theorem with coarse notation like Landau symbols. Many results about "practical" algorithms implicitly say, "and this behaviour can be observed for reasonable $n$".

Sometimes you get better theorems which use Landau notation for "error terms" only; authors like Knuth do not say "algorithm A runs in time $O(n \log n)$", but rather "algorithm A takes $2n\log n - 2n + O(1)$ comparisons". This does not completely do away with your issue, but mitigates it to some extent. If you know that that $O(1)$ stands for $\leq 1377$, you can make informed decisions based on that result.

Some of our reference material discusses facets of this issue.


If you have multiple initial states, then this automata is non-deterministic.


Suppose $A$ is undecidable and reducible to $B$. Given an algorithm for $B$, you can use the reduction from $A$ to $B$ to get an algorithm for $A$, which we assumed is impossible. Therefore $B$ must be undecidable.

If $A$ is undecidable and reducible to $B$ and $B$ is decidable then we obtain a contradiction and everything goes. Pigs can fly.


Show that UPrime = {1^n : n ∈ N is prime} is in P


turing machine for the language L ={w#w' where w<w'}

Here is a sketch of a construction method of the TM:

Compare bit by bit from the first bit to the last bit as normal. If equals, proceed to the next bit. Otherwise, it can decide the order.
If the head of TM reaches the word separator $\#$ or the blank symbol (say $\$$ or something), finish the comparison. If both words end simultaneously (i.e. when $\left| w \right| = \left| w' \right|$), then $w = w'$. If not, the shorter word is less than the other in the lexicographic order.

This idea is the same for both a deterministic TM and a non-deterministic TM. Only a non-deterministic TM can compare bits in a non-deterministic way.


Prove Queue Automaton is equivalent to Turing Machine

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)
queue:  0100101#  pop:1  buf:*
queue:  *0100101  pop:#  buf:1

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head,  and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself.
And if you want to be rigorous, you should also consider the special initial case in which the queue doesn't contain the head symbol #.


Determine whether a variable has positive influence in Boolean function

Given a CNF $\phi$ and a variable $x_i$, deciding whether $\phi$ depends on $x_i$ is NP-complete. It is clearly in NP: all we need to verify that $\phi$ depends on $x_i$ is two inputs different on $x_i$ on which $\phi$ evaluates to different values.

In the other direction, we reduce from SAT. Given a CNF $\psi = C_1 \land \cdots \land C_m$, let $x$ be a new variable and consider the CNF $\phi = \psi \land x$. If $\psi$ is satisfiable then $\phi$ depends on $x$, since substituting such a satisfying assignment reduces $\phi$ to $x$. If $\psi$ is not satisfiable then $\phi$ is always false, and in particular doesn't depend on $x$.


Collection of inference rules viewed itself as a judgment

The interpretation of such paragraph is that rules define judgements. It's more or less the same as saying
closure: the judgment satisfies this rules
strongest: ..and this is all there is

So, for example, if you have the following two rules to define the judgement "to be a nat":

$$\frac{}{\mbox{zero nat}} \quad \frac{x \mbox{ nat}}{\mbox{suc(} x\mbox{) nat}}$$

then you are stating that:

closed:

$\mbox{zero}$ is a $\mbox{nat}$ and
if $x$ is a $\mbox{nat}$, then $\mbox{suc}(x)$ is a $\mbox{nat}$

strongest: no other word is a $\mbox{nat}$


A question on the graph induced by the transition function of a deterministic Turing machine

Not likely: almost every property of a Turing Machine is undecidable, and almost every property of a graph is decidable.

If you ignore tape contents, you don't have Turing machines, you have finite automata. But graphs can't really represent tape content.

You can perform some trivial dead code analysis, but there may be unreachable states which are reachable in your graph.


What is the avantage of having memory mapped I/O?

There are many advantages to memory mapped I/O

Access: Memory mapped devices use the same instructions/addressing modes as regular memory. These map well into high level languages allowing device drivers to manipulate devices without the need to drop down into assembly language to use special I/O instructions.
Security: As memory addressed devices, memory management hardware can be used to control access to those devices. Generally, I/O instructions are "wide open" in privileged modes allowing a driver to access any I/O mapped device, even those that it should not.
Flexibility: Almost without exception, the processor instructions available for memory are more varied and versatile than those for I/O mapped. With memory, load/store instructions are supplemented with various monodic (inc/dec/etc) and dyadic (add/sub/etc) operators. Special I/O mode instructions are generally limited to load/store. This typically gives the compiler a better shot at creating better code (ignoring the whole RISC/CISC debate for now).

Support for special I/O mapping is generally a legacy issue. The x86 for example is (on some level) compatible all the way back to the 8008.

Very old processors often included I/O mapped device support because the memory address space was so small (often 65,536 bytes or less) that I/O addressing provided a way to preserve memory address space for actual memory.

Modern processors have larger (4G or larger) address spaces so that this is no longer an issue.


operate infinite times over a regular language

Colleague Apass Jack already warned about the dangers of infinity, and he also indicated a very simple example that shows that a very simple iteration leads to a non-regular language. Case closed, but I like to add an observation: iterating simple local substitutions lead to Turing power, not just non-regularity.

The single steps of a Turing machine van be encoded, and performed with a regular operation. The instruction "on reading $a$ in state $q$, write $b$, move left and change to state $p$" is coded as rule $aq \mapsto pb$ and is extended to longer strings containing a single state as $\alpha aq \beta \mapsto \alpha pb\beta $. This operation can be extended to sets of instructions, and will map a regular language into a regular language. However,iterating them will actually generated Turing machine computations!

(I have an answer somewhere with this observation, but cannot find it.)


How CPU know which process generated an interrupt?

First of all, different environments need different scheduling algorithms.

This is mainly because different operating systems have different objectives according the needs. Then, what the scheduler is going to optimize will not be the same for every case.

There are Real time systems, batch processing, interactive systems, etc. Let's consider interactive systems because these are the typical desktop computers and servers, offering services for various users. The main concerns for the scheduler is to "quickly" answer users querys.

In general, the scheduler tells the CPU wich process is next (the CPU is driven by the scheduler), and the details depends on the sheduler algorithm.

Consider the following simple and old scheduling algorithm, called Round-robin:

Each process is assigned with a pre-fixed quantum of time. There is a list of process. The CPU run process A, when the time is over (or A is blocked before time) it switch's to the next process B in the list. A is moved to the end of the list. The context of A is saved in the Process Control Block, so in the next turn for A the CPU knows where to continue because the IP register was saved in that context.
In this case, is like all processes have the same priority.
One key thing here is how much time is assigned to the quantum, it must be a reasonabe amount of time.

There are more complex algorithms, based in priority scheduling. In general, there are different classes of hierarchys, and each hierarchy may have his own queue of processes waiting to run. The CPU can start running process of the highest priority class, and when that class is empty it move downwards the hierarchy. The time of execution in this case can be a quantum, or the CPU can decrease priority of the current process in each clock interruption to avoid indefinite postponement of the other processes.


Proof Complexity of a Proof or Disproof of P = NP

Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+1] \to [n]$. This sequence of propositions is hard for certain propositional proof systems.

The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).


Is there a more efficient stability index algorithm?

Assume you have the sum $a[1] ... a[i - 1]$ and $a[i+1] ... a[n - 1]$. You can directly check the "stability" for index $i$. Think of how much additional computation you need to calculate the "stability" for index i + 1. In an $O(N^2)$ solution you would need $O(N)$ additional work by just recomputing the sum again. Is there something better you can do to reduce this to $O(1)$ so that the overall runtime reduces to $O(N)$.

Basically can you reuse some information that you already calculated before?


There are infinitely many strings over any alphabet, so if you pick any finite language, there are infinitely many strings not in it. In other words, there are infinitely many strings in the complement of any finite language.


What is the maximum number of classes resulting from partitioning by DFA as function of number of states?

I'm not sure what you mean by classes, but if you mean Myhill–Nerode equivalence classes, then the classical construction shows that the (unique) minimal DFA has as many states as equivalence classes.


All of the fields.  For instance, here is an example of a record:
{name: D.W., favoritecolor: blue}

You can think of a record as a function from field (key) to value.  For instance, the above would correspond to a function $f$ defined by $f(\text{name})=\text{D.W.}$, $f(\text{favoritecolor})=\text{blue}$.


What does it mean to "strengthen the precondition and weaken the postcondition" in Hoare logic?

Condition $A$ is stronger than condition $B$ if $A$ implies $B$.  That is, if $B$ holds in all situations in which $A$ holds.  Conversely, if $A$ is stronger than $B$, then $B$ is weaker than $A$. Note that, from the definition, $A$ is stronger and weaker than itself, since $A$ implies $A$.  (We might prefer to say "at least as strong as" instead of "stronger than" but I guess that gets convoluted and it's easier to just remember that "stronger than" really means "at least as strong as".)

So, to strengthen a condition is to replace it with a stronger one; to weaken a condition is to replace it with a weaker on. Because a condition is always stronger and weaker than itself, the phrase "strengthen the precondition and weaken the postcondition" does indeed mean that we can leave one (or even both!) of them unchanged.


Efficiently computing or approximating the VC-dimension of a neural network

If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.

It's not strictly an answer to your question, but it might help you on the way. The result is due to Baum and Haussler (1989).


Imagine you have an $\epsilon$-approximation algorithm $A$ which runs in $n^2+2^\frac1\epsilon$ on an instance of size $n$ and another one, $B$ which runs in $n^2+\frac1\epsilon$ (to give you an other example).

(I'm not using big-O notation to make it easier to talk about the polynomial bounds).

Now if you say $1/\epsilon$ is a constant, $2^\frac1\epsilon$ and $\frac1\epsilon$ both become constants, and you can say that the runtime of both $A$ and $B$ is bounded by a polynomial in $n$. Meaning that only $n$ is seen as a variable of that polynomial, as $\epsilon$ is a constant. So both $A$ and $B$ qualify as PTAS.

However, if this time you don't consider $1/\epsilon$ like a constant and want to include it as a variable in a polynomial upper bound, the situation changes.

For $B$, there exists some polynomial $p(x,y)$ of two variables $x$ and $y$, such that the runtime of $B$ is at most $p(n,1/\epsilon)$ for all $n,\epsilon > 0$. For example, $p(x,y) = x^2 + y$ works, because $n^2+\frac1\epsilon \leq p(n,1/\epsilon)$. Thus $B$ qualifies as a FPTAS.
For $A$ however, it is not possible to find such a polynomial. For every polynomial $p(x,y)$, you know that $n^2+2^\frac1\epsilon > p(n,1/\epsilon)$ once $1/\epsilon$ becomes big enough (or equivalently, once $\epsilon$ becomes small enough). Thus $A$ does not qualify as a FPTAS.


Dijkstra's algorithm will not allow you to obtain such minimum-weight shortest-path tree due to its greedy nature: once it obtains the shortest path to a vertex, the algorithm never reconsiders this vertex again.

One possible approach to obtain such a tree is to apply a small extension to Bellman–Ford's algorithm. Whenever there is a tie in step 2 of the algorithm $-$ that is, whenever there is a tie between (1) a newly computed distance between the starting vertex $s$ and a vertex $v$, and (2) the current best shortest path between $s$ and $v$ $-$ compute how much weight each of the two shortest path candidates adds to the current tree (and keep the path that minimizes this value). The current tree is available in the predecessor array, which stores the tree as an array of parent pointers.

Applying the above solution, you are, in effect, checking all possible shortest paths, so I presume that the answer to your last question is no.


Generate a unique number for a set of sequences of letters

Use a hash function. Since you have less than $2^{16}$ words, if you use a hash of 32 bits then you are likely to not have any collisions. If you do get collisions, you can try varying the key (hashes usually use some magic numbers, which in some cases are known as keys), or you can just use a longer hash.

Another possibility is to store the dictionary as a decision tree. The decision tree contains a node for each prefix of a word in your dictionary, and as you read a new word, you travel along the decision tree until you hit a leaf (the word is in the dictionary) or you get stuck (the word is not in the dictionary). But that amounts to storing the entire dictionary, which perhaps you are trying to avoid for some reason.

If for some reason you don't like these solutions, I have two other solutions to offer, though I don't recommend using them. The first one is to encode your words in base 26. This will be much more efficient than your prime-based code, though still somewhat unwieldy (the result could be up to 71 bits long). A more economic but more complicated solution is to use a Huffman code, either first order (the same code for each letter), second order (one code for the first letter, and henceforth the code depends on the previous letter), or even higher order.


Definition of the inverse of the Ackermann function

The Ackermann function $n \mapsto A(n,n)$ is definitely very far from being bijective, otherwise it could not grow so quickly. However, in the contexts it is usually employed (complexity theory, oh notations, ...) it is not really relevant which are the actual values of $\alpha$ point by point. You can add one or multiply by three and the results are the same, so nobody really cares about what is the actual definition. Any of your two will work.


if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC?

A polynomial from $3SAT$ to $A$ shows that $A$ is $NP$-hard.

A polynomial reduction from $A$ to $3SAT$ shows that $A$ is in $NP$.

So, the answer is yes.

You can construct a polynomial verification algorithm for $A$ by first reducing $A$ to $3SAT$, and then using the verification algorithm for $3SAT$.


Maximum weight tree with weights on vertices

It would seem that you need a Disjoint-set data structure.

When introducing each node $u$ with highest weight not in the tree, get all the nodes $u$ is connected to, call that neighbor set $C$. Iterate over all pairs $\{v, v'\}$ in $C$, $v \neq v'$, and check to see wether the disjoint-set trees of $v$ and $v'$ are same; if yes, adding $u$ will introduce a cycle. Finally, if adding that node $u$ restoring all the induced edges is possible without introducing a cycle, make sure that you add that $u$ to the same Disjoint-Set "tree" that contains all the prior nodes.


How is segmentation different from multiprogramming with fixed partition?

Segmentation partitions the address space into logically distinct parts
usually with the high-order bits representing the segment number, within which the low order bits are a normal linear address space.

A segment is the unit of access control to memory: one process may be able to read it while another is allowed to write it.

A process will generally have access to many segments.
Several processes may access the same segment. This is a possible way
for processes to communicate.

In Multiprogramming with fixed partitions, each process occupies a contiguous linear address space. It may or may not be aware of the position of the address space in the computer's memory. The process has complete access to its own address space and no access to any other process's. Any process, however, may make system calls.

You can put paging (virtual memory) underneath segmented or partitioned memory.


How does dynamic programming work in this example(generating the tables )

Here are all such sequences of length 1.

[1]

Here are all such sequences of length 2.

[1, 1]
[1, 2]

Here are all such sequences of length 3.

[1, 1, 1]
[1, 1, 2]

[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

Here are all such sequences of length 4.

[1, 1, 1, 1]
[1, 1, 1, 2]

[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]

[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]

[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]

[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

Please observe how the sequences grow longer and longer with the condition
$$a_{n+1} \leq \max_{1\le i \le n} (a_{i}+1) = 1+\max_{1\le i \le n} a_{i}$$
as well as the recurrence relation
$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$

  $a_{2} = a_{1+1} \leq \max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq  \max(2)$. and $a_{3}\leq \max(3)$.

Yes, $a_{2} \leq  \max(2)=2$. However, $a_{3}\leq \max(a_1+1, a_2+1)$. If $a_2=1$, then $a_3\le \max(1+1, 1+1)=2$. While $a_3\le \max(3)=3$ is true, it might be relaxed too much.

Let us see how we are going to fill the two dimensional array sequence($m$,$l$).

For example, how to use the following relation?
$$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\,.$$
We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $[1,2,3]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\,,$$
which corresponds to the unique sequence of length 4 and maximum number 4, $[1,2,3,4]$.

  What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a_4$ in the table of $l * m$?

It looks like you need to understand the recurrence relation.

$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$

where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a_1, a_2,a_3,a_4)$ is a sequence of length 4 and whose maximum number is $\max(a_1, a_2,a_3,a_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.

Let $a_1, a_2, \cdots, a_l$ be such a sequence. Let us consider its first $l-1$ items, $a_1, a_2,\cdots, a_{l-1}$.

The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is smaller than $m-1$. Then $$a_{l} = a_{(l-1)+1}\leq \max_{1\le i \le l-1} (a_{i}+1) = 1+\max_{1\le i \le l-1} a_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.

So this situation cannot happen.
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m-1$. Then $a_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.

So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m$. Then $a_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.

Combining all three cases above, we obtain that recurrence relation.


Equivalence of two definitions of mutual information

You can define the mutual information as $I(X;Y) = H(X) - H(X|Y)$. This definition is symmetric in $X,Y$ since
$$
H(X)-H(X|Y) = H(X) - \sum_y \Pr[Y=y] H(X|Y=y) = \\
\sum_x \Pr[X=x] \log \frac{1}{\Pr[X=x]} -
\sum_y \Pr[Y=y] \sum_x \Pr[X=x|Y=y] \log \frac{1}{\Pr[X=x|Y=y]} = \\
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{1}{\Pr[X=x]} -
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[Y=y]}{\Pr[X=x,Y=y]} = \\
\sum_{x,y} \Pr[X=x,Y=y] \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x]\Pr[Y=y]},
$$
and this expression is symmetric in $X,Y$.

This calculation also shows that if $X,Y$ are independent then $I(X;Y) = 0$, since then $\Pr[X=x,Y=y] = \Pr[X=x] \Pr[Y=y]$.

Moreover, if we write
$$
I(X;Y) = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} \log \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]},
$$
then the convexity of $z\log z$ implies that $I(X;Y) \geq z\log z$, where
$$
z = \sum_{x,y} \Pr[X=x] \Pr[Y=y] \frac{\Pr[X=x,Y=y]}{\Pr[X=x] \Pr[Y=y]} = \sum_{x,y} \Pr[X=x,Y=y] = 1.
$$
Thus $I(X;Y) \geq 0$.


Let's look at how many multiplications are necessary to perform $a^{16}$ by your recursive method:

$$a \xrightarrow{SQR} a^2 \xrightarrow{MUL} a^3  \xrightarrow{MUL} \ldots  \xrightarrow{MUL} a^{14}  \xrightarrow{MUL} a^{15}  \xrightarrow{MUL} a^{16}$$

Where:

$SQR$ = Squares a number

$MUL$ = Usual Multiplication

So as Yuval pointed out in the comments, even a small power of $2$ would require $\Theta(n)$ multiplications, which means this would be too slow for practical use.

However, you can the same thing using only $SQR$ with $\Theta(\log{n})$ operations. That is:

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{SQR} a^{16}$$

Of course, since $16$ is a power of $2$ we only need to use $SQR$. But you can alternate between $SQR$ and $MUL$. This is the principle behind Exponentiation by Squaring.

Example:Computing $a^{19}$.

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{MUL} a^{9} \xrightarrow{SQR} a^{18} \xrightarrow{MUL} a^{19} $$


Can we construct a Karp reduction from a Cook reduction between NP problems?

its a generally open TCS problem subject to ongoing research whether & the exact conditions Cook & Karp reductions are equivalent and is apparently closely related to the open NP=?coNP question & other complexity class separations eg E=?NE (wrt sparse languages).

here are two research papers on the subject & further leads on tcs.se via similar question:

Are Cook and Karp Ever the Same? Beigel, Fortnow
Cook vs. Karp-Levin: Seperating Completeness Notions If NP Is Not Small (1995) Lutz, Mayordomo
many one reductions vs Turing reductions to define NPC, tcs.se


What does "terms evaluated in related environments yield related values" means in the context of typing judgements?

The environments are related not identical. The context of this statement is logical relations, as described e.g. here. A logical relation is a type-indexed family of relations which follows the structure of the types (in a way I won't elaborate on). If for each type $\tau$, we assign a (binary) relation $R[\tau]$, then given $f:\tau_1\to\tau_2,x:\tau_1\vdash f\, x : \tau_2$ when $R[\tau_1\to\tau_2](f,f')$ and $R[\tau_1](x,x')$ we can ask if it is the case that $R[\tau_2](f\, x,f'\, x')$. This is what it is referring to in "terms evaluated in related environments yield related result".


Smoothing frequencies without count data

Yes. $\:$ Assume that the counts have the smallest sum that would produce your frequency data. $\:$ (How to do that depends on whether the frequencies were calculated and stored as doubles or something else.)


Automaton without variables and guards for queueing system

One deterministic automaton is enough to model this system.

Here are the list of states and their meanings. The alphabet is $$\{\text{a_customer_comes},\text{a_customer_leaves_server_1},\\ \text{a_customer_leaves_server_2},\text{a_customer_leaves_server_3}\}.$$ (We assume the input events happen one at a time. Otherwise, the problem might be too ill-defined enough to have a unique answer or too complex to be done as an exercise.)

$q_{0,0,0}$ : the initial state. No customer present.
$q_{1,0,0}$ : 1 customer at server 1 and 0 customer at server 2 and 0 customer at server 3.
$q_{0,1,0}$ : 0 customer at server 1 and 1 customer at server 2 and 0 customer at server 3.
$q_{0,0,1}$ : 0 customer at server 1 and 0 customer at server 2 and 1 customer at server 3.
$q_{1,1,0}$ : 1 customer at server 1 and 1 customer at server 2 and 0 customer at server 3.
$q_{1,0,1}$ : 1 customer at server 1 and 0 customer at server 2 and 1 customer at server 3.
$q_{0,1,1}$ : 0 customer at server 1 and 1 customer at server 2 and 1 customer at server 3.

I will let you figure out the transitions.


Are all decidable languages mapping reducible to its complement?

Let $L_1,L_2$ be two languages over $\{0,1\}$. A (computable) mapping reduction from $L_1$ to $L_2$ is a computable function $f\colon \{0,1\}^* \to \{0,1\}^*$ such that for all $x \in \{0,1\}^*$ it holds that $x \in L_1$ iff $f(x) \in L_2$.

In your example, $L_1 = \{0\}$ and $L_2 = \overline{\{0\}}$, there does exist a mapping reduction, given by
$$
f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases}
$$
Clearly $f$ is computable, and you can check that $x \in L_1$ iff $f(x) \in L_2$.

Hence your example doesn't work. You can check, however, that $\emptyset$ and $\{0,1\}^*$ are two examples of languages not reducible to their complement. Indeed, these are the only examples, which you can try to prove.


How to apply "verification" and "decision" for the SUBSET SUM problem?

If anybody could show you that verification is simpler than decision, then she would be famous, having solved the P vs. NP problem.

For SUBSET-SUM, verification means that given a set $S$ which has a subset summing to $t$, someone can convince you easily that this is the case. The way she would do it is by giving you a subset of $S$ summing to $t$.

In contrast, decision means given a set $S$ and a target $t$, decide whether there is a subset of $S$ that sums to $t$. Nobody knows how to do it efficiently, and we conjecture that there is in fact no way to do it efficiently.

A related problem is co-verification: given a set $S$ which has no subset summing to $t$, we want someone to convince us easily that this is the case. Nobody has any idea how such a convincing argument would look like, and we conjecture that there such convincing arguments don't in fact exist (in general). This is the NP vs. coNP problem.


Function problems and $FP \subseteq FNP$

I found the following in Papadimitriou's book Computational Complexity which I've found satisfying.

Let $R \subseteq \Sigma^* \times \Sigma^*$ be a binary relation on strings.
$R$ is called polynomially decidable if there is a deterministic Turing Machine deciding the language $\{x;y : (x,y) \in R\}$ in polynomial time.
We say that $R$ is polynomially balanced if $(x,y) \in R$ implies $|y| \leq |x|^k$ for some $k \geq 1$.

Then Papadimitriou notes the following, which basically is another definition for NP:

Let $L \subseteq \Sigma^*$ be a language. $L \in$ NP if and only if there is a polynomially decidable and polynomially balanced relation $R$, such that $L = \{x : (x,y) \in R$ for some $y \}$.

A few dozen pages later...

The function problem associated with $L$ [$\in$ NP], denoted $FL$ [here $L$ stands for said language, not logspace], is the following computational problem:
Given $x$, find a string $y$ such that $R_L(x,y)$ if such a string exists; if no such string exists, return "no".

Then

The class of all function problems associated as above with languages in NP is called FNP. FP is the subclass resulting if we only consider function problems in FNP that can be solved in polynomial time.


How to get expected running time of hash table?

Why not sort the array, then iterate over the sorted array, comparing the current number to the previous number.

n*log(n) for the sort, n for the iteration = 2n*log(n)


Are there decidable non-trivial properties of a LBA's accepted language?

Given a Turing machine $M$, you can construct an LBA $A$ that given as input a word of length $n$, it simulates $M$ on the empty tape as long as $M$ uses up to $n$ space, and the moment $M$ exceeds space $n$, it enters an infinite loop. In contrast, if $M$ ever halts, then $A$ also halts. Thus $A$ halts on some input iff $M$ halts on the empty input.
You can try to show that the second property is undecidable using a similar argument.


The only additional constraint which is required for $h_3$ and $h_4$ to be admissible is that both $h_1(n)$ and $h_2(n)$ return non-negative values for any state $n$, but this is always accomplished ---even if a heuristic function might return a negative value it just suffices to take the maximum between the value returned and 0, and this operation clearly preserves admissibility.

Thus, given that $h_1(n), h_2(n) \geq 0$ for every state $n$ and that both are admissible, it is easy to see that the values of $h_3(n)$ are upper bounded by those of $h_1(n)$ (the maximum value taking place when $h_2(n)=0$) Since $h_1$ is admissible so it is $h_3$; conversely, if $h_2(n)$ returns any strictly positive value then $h_3(n) < h_1(n)$. Now, if $h_1(n)$ is not overestimating the effort to reach the goal, then $h_3(n)$ is neither as well and thus, $h_3$ is admissible in this case also.

The proof of admissibility of $h_4$ follows the same lines.

Note that in these proofs it is never required for any heuristic function to strictly dominate another, i.e., the condition $h_1(n) < h_2(n)$ is useless and not necessary at all. The only important requirement is that none ever return negative values, but this is a trivial requirement.

To conclude, I think this is mostly a theoretical exercise. Note that as mentioned above $h_3$ and $h_4$ are upper bounded by $h_1$ and $h_2$ respectively so that, in other words, they are less informed than them. In other words, these transformations are of no interest.

Hope this helps,


What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

It's called "loop fusion".
It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.


You could organize type inference as follows.

Suppose your input syntax has type Input. Define output syntax Output to be like Input but with explicit type annotations on all variables. The type inference would have type

infer : Input -> List (Output * Type)

That is, given some input e, it returns a list of possible answers. Each answer is a pair (e', t) where e' is e with variables annotated by types, and t is the inferred type of e.

You can view this as all happenning in the nondeterminism monad. Whenever you need to infer the type of a variable x, you look up its possible types S | T | ... and branch on each one of them. This way you do not have to "pass back" any information to sub-expressions. Instead, each sub-expressions already comes annotated, in all possible ways.


How does this use of "apply" in Coq work?

You can ask Coq to show you its proof object. Before Qed, type Show Proof.

(fun (_ : forall n : nat, evenb n = true -> oddb (S n) = true)
   (H2 : oddb 3 = true) => H2)

As you can see, H1 is not used at all, and the goal is H2.

It comes from the definition of oddb and evenb, the definition of negb and the definition of the natural numbers and the booleans.

Definition oddb (n:nat) : bool := negb (evenb n).

oddb 3 is equal to negb (evenb 3) by the definition of oddb above.
evenb 3 is equal to evenb (S (S (S O))) by the definition of 3. This is equal to evenb (S O) which is equal to false by the definition of evenb.
Therefore oddb 3 = negb false which is in turn equal to true by the definition of negb.
evenb 4 is equal to evenb (S (S (S (S O)))) by the definition of 4. Applying the definition of evenb three shows that this is equal to evenb (S (S O)), to evenb O, and to true.

All of these equalities come from computation: if $x$ reduces to $y$ then $x$ is equal to $y$ — this is the most basic form of equality¹. The reductions above use the $\beta$ rule (applying a lambda term to an argument), the $\delta$ rule (replacing a name by its definition) and the $\iota$ rule (applying a recursive function fix … and simplifying pattern matching).

Coq has a large set of tactics to perform computations, though they're only needed in advanced cases. For example, after intros H1 H2, you can ask it to expand evenb and oddb, but do nothing else.

cbv delta.
cbv delta in H2.

Integers like 3 and 4 are syntactic sugar, not named constants. 3 is S (S (S O)), not just some term that reduces to it. If you want to see everything that's going on, turn off pretty-printing of notations.

Unset Printing Notations.

(Use Set Printing Notations. to turn them back on.)

You can watch the goal being reduced to its value.

cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota.

Of course you don't need to guide Coq so much, this is just if you want to see all the steps. You can simply ask Coq to compute as much as possible. Just after intros H1 H2, run

compute. compute in H2.

and you'll see that both H2 and the goal simplify to true = true.

In this particular case there's no simpler way to go from H2 to the goal than to fully calculate both. If you continue the tutorial a bit, you'll get to recursive proofs, where it's very common to have similar hypotheses and a similar goal, but with a variable instead of constants like 3. There you would typically combine H1 and H2 together (but here H1 is not particularly interesting — since you're proving something about evenb, you'd want the an implication of the form oddb … -> evenb … rather than evenb … -> oddb …).

¹  In a certain sense, it's the only form of equality.


Can type information be encoded in the untyped lambda calculus?

As mentioned in the comments, it is possible to reduce simply typed lambda calculus to untyped lambda calculus. This is the approach associated with Alonzo Church, called "Church Types" or "intrinsic types". Here, types are embedded in the language, and are intrinsic to the language. Still, the language can be stripped of it's types.

However, it is also possible to construct simply typed lambda calculus from untyped lambda calculus. This approach is associated with Haskell Curry, called "Curry Types" or "extrinsic types". Here, types can be derived from the AST of the language.

The latter type is what you are looking for. A thorough overview of the subject is here


Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Here is the basic idea. Suppose that $x0y \in L$. When would $x0y \notin \mathcal{B}(L)$? Exactly when $x1z \in L$ for some $|z| = |y|$. When does that happen? Fix some DFA for $L$, and suppose that after reading $x1$, it is at state $q$. Parikh's theorem shows that the set of lengths $\ell$ such that $x1z \in L$ for some $|z| = \ell$ is eventually periodic, that is, it is of the form $L_0(q) \cup \{k m(q) + a : a \in L_1(q) \text{ and } k \geq 0\}$ for some finite $L_0(q),L_1(q)$. We can further assume that $m(q) = m$ is the same for all states $q$, since there are only finitely many of them and we can take the LCM of the minimal periods.

As we read more and more zeroes, we obtain more and more constraints, which can be summarized in the form: the word cannot end in $\ell$ characters for $\ell \in L_0 + \{ km + a : a \in L_1 \}$. Note that there are only finitely many possibilities for $L_0$ and $L_1$, since $\max L_0 \leq \max_q \max L_0(q)$, and similarly for $L_1$. This means that we can store and maintain this information in a finite state automaton, and use it to decide $\mathcal{B}(L)$.


Designing algorithms that are fast enough is probably a function of experience. There are strategies (recursion, divide-and-conquer, dynamic programming...) that can be used. Often a problem can be approached with multiple strategies but one is more efficient than the other. The more of these strategies you know, the better you are equipped for using them in your algorithms. Experience will also give you a feel for what is an appropriate approach; you may intuitively notice which problems are recursive in nature, which can be expressed as operations on a graph etc. Then you can use what you know to knead the challenge into a familiar shape. Do a Google search for "algorithm strategies" to find useful resources which list generic strategies. Learn about these and then consider for algorithms you encounter how they are instances of these generic approaches (or combinations thereof).

Edge cases tend to occur where assumptions are made, and for some situations those assumptions are incorrect. An algorithm attempts to resolve something for some structure which seems consistent; it breaks down where the structure suddenly differs or becomes inconsistent. Edge cases are the sort of place in a program where you need to test assumptions and where decisions branch.

For example, suppose I have some algorithm that takes a list of elements as input and performs a computation over it. You begin your design by stating that for each element in the list, in order, some action is performed. That's an assumption right there. "Each element in the list" assumes there are some. How will it behave for an empty list?

An example of this I encountered in some programming contest a while ago. You were given a list of numbers and had to find out how many ways there were to divide this into three lists, maintaining the original order of the numbers, in some way that satisfied some condition (the sums for the three sub-lists had to be equal). I got started but soon noticed some test inputs failed. It turned out that empty sub-lists were also valid. I had assumed that each sub-list had to have at least one element. And then, of course, I'd need to consider whether my fixed program would handle inputs of 0, 1 or 2 numbers correctly as well.


while loop for bitwise conversion program

The & operator is a bitwise "AND". Since the binary representation of 1 consists only of a 1 on the least significant bit, the operation c & 1 checks if $c$ contains a 1 on the least significant bit. Another way to say it is that c & 1 is the remainder of $c$ modulo 2, that is 0 if $c$ is even and 1 if $c$ is odd.
The >> is a logical shift right, that is the deletion of the least significant bit.
For example, if $c = 26 = (11010)_2$, the steps are:

c & 1 = 0 so count is not modified. $c$ becomes $1101$;
c & 1 = 1 so count is incremented. $c$ becomes $110$;
c & 1 = 0 so count is not modified. $c$ becomes $11$;
c & 1 = 1 so count is incremented. $c$ becomes $1$;
c & 1 = 1 so count is incremented. $c$ becomes $0$.
c != 0 is not true so the algorithm stops. count was incremented thrice, and three is indeed the number of 1's in the binary representation of $c$.


As a rule of thumb, your red-black tree depth can't be less than log(n) and it shouldn't be more than 2*log(n+1). Your numbers look correct. (log(1000)=10 and your 1000 sample tests are between 10 and 20).

Ref: http://lcm.csa.iisc.ernet.in/dsa/node115.html


Finding the number of square prefixes of a string in linear time

Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will simply be the count of indices $i$ such that $Z[i] >= i$, assuming 0-indexing.

Fortunately, such an algorithm exists and is quite elegant! It's (as always) a good idea to try to devise it on your own. If you get stuck, here's a pretty good explanation: http://codeforces.com/blog/entry/3107.


Reservoir sampling algorithm probability

The whole reason for performing this sampling method is to get an uniform sample even if the population size is unknown at the start. So, if this method works, the probability cannot be skewed.

What happens, is that the samples chosen in the beginning have a chance to be overwritten by the samples chosen later. Intuitively, this balances it somewhat. But we must show that this 'balance' holds precisely:

The probability of $\frac{k}{i}$ refers to the  probability that sample $i$ is added to the reservoir, as it is added when a uniform random integer from $[1,i]$ is less than $k$, i.e. $k$ positions in the range $[1,i]$ lead to inclusion in the reservoir. (Total number of events is $i$, number of events that we 'want' is $k$, all events are equally likely, so final probability is $\frac{k}{i}$)

Now what is the probability that $i$, when chosen, remains in the reservoir until the end? It gets removed when a single integer in the range $[1,m]$ is picked, for all $i<m\leq N$. The probability that it doesn't get replaced at position $m$ is $1-\frac{1}{m}$. As these events are independent, the total probability that $i$ doesn't get replaced is $\prod_{m=i+1}^N (1-\frac{1}{m}) = \frac{i}{N}$ $^*$. As $i$ is in the reservoir at the end if it gets picked and not replaced, this probability is $\frac{k}{i}\cdot \frac{i}{N} = \frac{k}{N}$.

We're not done yet, as the calculation above only holds for the samples not originally in the reservoir. However, that case is similar: as they are always put in the reservoir, we only need the probability they stay, which is $\prod_{m=k+1}^N (1-\frac{1}{m}) = \frac{k}{N}$.

So the probability of being included in the final sample is the same for all positions, which means the final sample is uniform.

*: The expression $\prod_{m=i+1}^N (1-\frac{1}{m})$ can be simplified as follows:

\begin{align}\prod_{m=i+1}^N (1-\frac{1}{m}) &= \prod_{m=i+1}^N (\frac{m-1}{m})\\ &= \frac{i}{i+1}\cdot\frac{i+1}{i+2}\cdots \frac{N-2}{N-1}\cdot \frac{N-1}{N}\\ &= i\cdot\frac{i+1}{i+1}\cdot\frac{i+2}{i+2} \cdots \frac{N-1}{N-1}\cdot \frac{1}{N} =\frac{i}{N}.
\end{align}

It is also possible to show by induction on $N$, but I think the previous is more insightful.


Is there an efficient algorithm for expression equivalence?

Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms.

Your expressions are all multivariate polynomials.  Apparently, your expressions are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e_1,e_2$ are expressions, then $e_1+e_2$ and $e_1e_2$ are expressions.  If that's indeed what you intended, every expression is a multivariate polynomial over the variables.

Now, you want to know if two expressions are equivalent.  This amounts to testing whether two multivariate polynomials are equivalent: given $p_1(x_1,\dots,x_n)$ and $p_2(x_1,\dots,x_n)$, you want to know if these two polynomials are equivalent.  You can test this by subtracting them and checking whether the result is identically zero: define

$$q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) - p_2(x_1,\dots,x_n).$$

Now $p_1,p_2$ are equivalent if and only if $q$ is the zero polynomial.

Testing whether $q$ is identically zero is the zero testing problem for multivariate polynomials.  There are efficient algorithms for that.  For instance, one example algorithm is to evaluate $q(x_1,\dots,x_n)$ at many random values of $x_1,\dots,x_n$.  If you find a value of $x_1,\dots,x_n$ such that $q(x_1,\dots,x_n)$, then you know that $q$ is not identically zero, i.e., $p_1,p_2$ are not equivalent.  If after many trials they are all zero, then you can conclude that $q$ is identically zero (if $q$ is not identically zero, the probability that all of those trials yield zero can be made exponentially low).  The number of iterations you need to do is related to the degree of $q$; see the literature on polynomial identity testing for details.

For instance, see https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/

These algorithms apply if you are working over a finite field.  You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$.  If you are working over a finite field, the methods above apply immediately.

If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients.  You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$.  Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.


Proving the singleton language {x} is regular for all x ∈ Σ*

$\Sigma^*$ is a set of finite strings. There are infinitely many of them, but each one is finite – just like there are infinitely many natural numbers but each one of them is finite.

So, for any $x\in\Sigma^*$, $\{x\}$ is a finite language (it contains one string) of finite strings (because everything in $\Sigma^*$ is finite), so it's regular.


Do I understand pseudo polynomial time correctly?

The running time for binary search that you quote applies for the so-called RAM model. I think that it is usually assumed that the machine words have size $\Theta(\log n)$ bits, where $n$ is some natural parameter like the length of the input.

For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.