The constraint

  covariant type recursion (type constructor should not appear in negative position in a constructor argument)

excludes this

data Bad r = Bad (r -> r)
                  ^    ^--- positive position
                  ^-------- negative position

Indeed, all the occurrences of r must appear in positive position.

  Should all type variables also only appear covariantly?

Yes, precisely.

Essentially, your Fix Bad tries to generate a type $T$ isomorphic to $T \to T$. If we had that, we would have a model of the untyped $\lambda$ calculus, where terms are not normalizing ("terminating") in general.

Indeed, to apply any two terms $x, y : T$ we can exploit the isomorphism to treat $x$ as if $x : T\to T$, at which point the application $x y$ becomes feasible. As a special case, we also obtain $xx$, hence $\Omega = (\lambda x.xx)(\lambda x.xx)$ which is the archetypal non normalizing term.

To conclude let me point out that, in some advanced calculi with dependent types, covariant recursion is not enough, and you need an even stricter constraint called "strict positivity". Without that, contradictions arise. In Haskell-like languages, covariance (and the other constraints you mention) should suffice.


Why would you introduce the goto statement into a modern language?

There are two kinds of programmers: Those who for whatever reason never, ever use goto, and go to any lengths to avoid it, and those who use goto in one of the very rare situations where it is the best solution. (Someone said here in a comment that goto could be misused and programmers would find ways to misuse it - but those people are not programmers).

It makes sense to add "goto" to a language that doesn't have it if there is evidence that there are situations where it improves the code, and if it is not too difficult to implement. So I would assume that there was such evidence.


What is the difference between object detection, semantic segmentation and localization?

I read a lot of papers about, Object Detection, Object Recognition, Object Segmentation, Image Segmentation and Semantic Image Segmentation and here's my conclusions which could be not true:

Object Recognition: In a given image you have to detect all objects (a restricted class of objects depend on your dataset), Localized them with a bounding box and label that bounding box with a label. In below image you will see a simple output of a state of the art object recognition.

Object Detection: it's like Object recognition but in this task you have only two class of object classification which means object bounding boxes and non-object bounding boxes. For example Car detection: you have to Detect all cars in a given image with their bounding boxes.

Object Segmentation: Like object recognition you will recognize all objects in an image but your output should show this object classifying pixels of the image.

Image Segmentation: In image segmentation you will segment regions of the image. your output will not label segments and region of an image that consistent with each other should be in same segment. Extracting super pixels from an image is an example of this task or foreground-background segmentation.

Semantic Segmentation: In semantic segmentation you have to label each pixel with a class of objects (Car, Person, Dog, ...) and non-objects (Water, Sky, Road, ...). I other words in Semantic Segmentation you will label each region of image.


Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-context-free language.
To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the square-root operation to introduce another equality, as it seems predisposed to do so.


delete node from linked list (lang w/GC) -should deleted item 'next' be set to null

If you mean the next pointer of the node that was deleted, as far as I know it is normally not necessary to set the pointer to null.  Once the node is deleted, if the code is not buggy, then the code should not access the node after it is deleted, so the value of its next pointer should be irrelevant.  Sometimes some people do set the pointer to null, as a form of defensive programming (just in case the program is buggy and accesses that node after it was deleted).

I suggest that a useful exercise would be to ask your teachers why they teach yes or no.  Hearing their reasoning might be instructive and interesting!


What makes a nested function in gcc so complicated?

I don't see any obvious reason why the compiler could not inline the call to list_traverse, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily valid, but a reason can be just a suspicion.)

Without inlining, though, it's very difficult to see how the trampoline could be avoided. The frame containing the variables has to be passed through list_traverse so that it can be handed off to contains_aux. But presumably list_traverse is used elsewhere, and those other calls might not even involve a nested function, in which case there would be no stack frame to be passed through. There's nothing in list_traverse's prototype which specifies that it might be called with a nested function, so if it has external linkage, it needs to be usable with the standard calling convention, which has no room for hidden parameters. And if it is called with a nested function, there is no guarantee that the nested function it is called with was nested in the same way. (For example, there might be more than one stack frame which needs to accompany the closure, if the bound variables come from different places in the call stack.)

So aside from inlining, the only safe solution is to manufacture something which can be called like an ordinary function, thereby conforming with the type of list_traverse's first argument.

As evidence that inlining is possible, I offer the following C++ program, in which the same compiler happily inlines the lambda:

struct list_t {
    int value;
    list_t* next;
};

template<typename F>
void list_traverse(list_t* head, F check) {
    while (head && check(head))
        head = head->next;
}

bool list_contains(list_t *head, list_t* item) {
    bool found = false;
    list_traverse(head, [&](list_t *list)->auto {
        return list == item ? (found = true, false) : true;
        });
    return found;
}

(Alternatively, with a strangely bloated result: https://gcc.godbolt.org/z/s9XqW7).

I do understand that inlining might not be exactly what you're looking for, though.


Duplicating the quotation marks in in the quotation-mark enclosed strings

Just replace " in the list of possible characters with "".

That might have consequences for other grammar productions which use the same non-terminals, in which case you might need to separate special_character into special_character_not_quote and ".


How would i go about calculating the Big Theta of the following nested loop?

Each internal loop does $2^i$ iterations of $\Theta(1)$ so it takes $\Theta(2^i)$.
Therefore the time complexity of the code is the $\Theta(\Sigma_{i=0}^{log(n)} 2^i)=\Theta(n)$.

You could intuitively think of summation here as writing in binary base a number where all its digits are 1, and has the same number of digits as n, it is linear to the size of n.


What is the formal justification for the correctness of the second formulation of rod cutting DP solution

The proof of $r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$ is divided into two parts. In the first part, we prove that $r_n \geq \max_{1 \leq i \leq n} (p_i + r_{n-i})$. In the second part, we prove that $r_n \leq \max_{1 \leq i \leq n} (p_i + r_{n-i})$.

First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.

Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.


Is concurrent language CCS or CSP turing-equivalent in language power?

The answer to your (1) depends on what exactly you mean by "model" and by "interacting machines". The $\pi$-calculus in particular is usually deemed to be a good simplification of  the core aspects of message passing concurrency.

Regarding (2), you can simulate Turing machines in CSP, CCS, the $\pi$-calculus as well as in C. Hence they are all equivalent in terms of the functions they can compute on the natural numbers.


Algorithm to find smallest difference in array

This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for element distinctness, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.

(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x_i - x_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)

There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.


Hint. Reduce Hamiltonian path to this problem. Use the rewards $r_i$ to say that you have to visit each city, use the costs $f_{i,j}$ to say that you can't use more than one edge per city and set the target $k$ to an appropriate value.


This is a home work problem.
By the way the problem is ambiguous.
For concept see       3.6 pg259 of kurose 6th edition.

As for the solution normally what AIMD do is after the time out the it set window size to 1 in the next slow start phase
In sort the window increase in this manner 2,4,8,9,10,1,2,4,5,6
So after 10th transmission window size will be 6
But in question says the slow start phase start with 2 MSS So to consider that the window will Grow this way
2,4,8(threshold reached additive increase),9,10(time out& set threshold to 5),2,4,5(threshold reached additive increase),6,7


Hint : Try to understand more about context switching. Context switching takes place between 10 processes. (And you can forget about those 15 requests, instead consider each process needs 15 * 20 msec of CPU time)


We don't know. If any NP-complete problem were in co-NP, then we'd have NP$\,=\,$co-NP and we don't know whether that's true or not.


In the case $d=2$, it is possible in $O(n \log n)$ time. First, sort the input elements on their first component. Then, use a recursive divide&conquer strategy: if a pair of comparable elements exist, then either:

Both elements are contained in the first half of the list
Both elements are contained in the second half of the list
A pair can be formed by taking on element from the first half and one from the second half

Cases 1 and 2 can be solved by recursion. Case 3 can be solved by finding the element from the first half with the lowest second component and finding the element with the highest second component from the right list.

It is possible to implement the divide&conquer strategy in $O(n)$ time so the time complexity is dominated by presorting the list, taking $O(n \log n)$ time.

When going to $d=3$, a similar strategy might be possible, but the third case is harder: given two sets of 2-dimensional vectors $A,B$ it requires finding $a\in A,b\in B$ such that $a\leq b$.

Edit: the following paper may be relevant, it computes for each vector how many vectors are ranked lower in less than quadratic time. http://www.cs.uiuc.edu/class/fa05/cs473ug/hw/p214-bentley.pdf


Is there a logspace version of the reduction used in Cook-Levin?

To address your "follow-up", no.  The ability to use logspace reductions instead of polynomial time reductions to prove NP-completeness doesn't prove that P is contained in L.  It just proves that you don't need the full power of polynomial time reductions to define NP-completeness.  The situation is similar to saying, "Hey, there are lots of polynomial-time algorithms for graph reachability but I just found out that the problem is in logspace.  Does that mean that P$\,=\,$L?" except that now we're talking about a whole class of computations (the reductions) rather than just one problem.

In fact, if you check out books on descriptive complexity,1 you'll see that we can use even weaker notions of reduction (reductions definable by first-order formulas) and still define a meaningful and, as far as we know, equivalent notion of NP-completeness.  This is reassuring: it tells us that NP-completeness is a robust concept that doesn't seem to depend exactly on how you define it.

I say "doesn't seem to depend" because, as far as I'm aware, it is not known that defining NP-completeness in terms of polynomial time, logspace and first-order reductions makes exactly the same class of problems NP-complete.  But there are no problems known to be NP-complete under one of these kinds of reductions but not under one of the others.  (Stand by for this paragraph to be edited after people comment!)

1 E.g., Immerman, Descriptive Complexity (Springer, 1999) or Libkin Elements of Finite Model Theory (Springer, 2004).


I mean how the interpreter executes a code without translating it into machine code

TL;DR It's the interpreter's (machine) code that executes your program's code.
To explain it better, consider these lines taken from your example:
def sub(a,b)
    print(a-b)

I think you got this point wrong: when you write x-y in an interpreted programming language it's because you want to know the result (for example to save it into a variable) rather than to be printed. Also, the variables of the interpreter are not mixed with the ones of the interpreted programs: for example the variables x and y could have some meaning for the interpreter and another meaning for the final program. Usually the interpreter does not make any assumption on the program's variable, it just stores them into a "memory" which is just a set of pairs <variable_name, value>.
So, when there is an instruction like z = x-y in your program, the interpreter does the following:

look into the memory, retrieve the current value for x
look into the memory, retrieve the current value for y
compute x-y (call the result R).
set the value for z to be R in the memory.

Point 3. in the list above is crucial. If this was a real interpreter, it would not be a Python program but a compiled one, thus the implementation of point 3. would be a bunch of machine code that eventually contains a sub machine instruction, or some other sequence of machine instructions that together implement the subtraction.
So every instruction of every language is executed as machine code eventually:

in the compiled languages the higher level instructions are translated into machine code;
in the interpreted languages it's the interpreter's machine code to be executed.

Read the last paragraph again.
Actually you could write an interpreter using Python, but in this case it's the Python interpreter's machine code to be executed. Or it could have been any chain of pairs <interpreted language $L_i$, interpreter for $L_i$>, the point is that the last interpreter must be compiled, and thus at the very last it's just machine code to be executed because that is the only languages that the processor understands


Regular expression for the language where every a is surrounded by b's

Here is a regular expression for your language: $(b(ab)^*)^*$. It's not hard to check that every $a$ is bordered by $b$s in both directions. The other direction is more complicated and left to you.


You could use graphviz.  Its input format allows you to specify the color for each vertex.  You could write a simple script to take the specification of the graph and the clustering, and output a .dot file that lists the vertices and edges and specifies an appropriate color for each vertex (based upon your clustering).


Can a propositional threshold connective be expressed by standard connectives?

The idea is to use the following steps:

Construct an NC1 circuit computing the binary representation of $x_1+\cdots+x_n$, see for example these lecture notes (Theorem 7). This circuit implements carry-save addition.
Convert the NC1 circuit to a polynomial size formula, see for example these lecture notes (Proposition 1).
For each $k$, it is now easy to construct a polynomial size formula that tests whether $x_1+\cdots+x_n=k$.
Use up to $n$ of the formulas from the previous step to come up with your desired formula.

You can in fact implement the last two steps more efficiently, using $\log n$ rather $n$ copies of the preceding formula, by using a comparison gadget; details left to you.


Proving that a certain language is regular using pumping lemma

You cannot use the pumping lemma to show that a language is regular. The pumping lemma gives a property of regular languages: if $L$ is regular then $L$ can be "pumped". You can use this to show that $L$ is not regular: if $L$ cannot be pumped, then it is not regular. But you cannot use it to show that $L$ is regular: if $L$ can be pumped, it doesn't follow that $L$ is regular; moreover, there are examples of pumpable languages which are not regular. There are extensions of the pumping lemma which can be used to show that a language is regular, but they are not so useful in practice.
In your case, every word in $L$ contain $0$ or $4$ many $a$s, $0$ or $8$ many $b$s, and so on. In particular, it contains at most $4$ many $a$s, at most $8$ many $b$s, and so on. Therefore every word in $L$ has length at most $4+8+\cdots+2^{27}$. Consequently, $L$ is finite. Every finite language is regular.


This is certainly possible, and there are two possibilities:

There are two compilers for a language. For example, Haskell has GHC, and GHCJS, which is a JavaScript cross-compiler. GHC is written in Haskell, and GHCJS is written in Haskell (and normally compiled with GHC), so GHCJS is a self-hosted cross-compiler.
You run your self-hosted cross-compiler in a target language. So, if you had a Foo to Python cross-compiler, and it's the only compiler for Foo, and it's written in Foo, it can be self hosting, but you would have to cross-compile it, then run the result in a Python interpreter.

Basically, be careful that you don't confuse a language with a compiler. A language can have many compilers.


The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So by a brute force algorithm check every possible assignment to variables. Choose 10 variables from n, $(^{n}_{10})$ and set them to $True$ and set other variables to $False$ and check if this is a satisfying assignment. The run time of this algorithm is $(^{n}_{10})*n = O(n^{11})$.


How to find a subset of numbers such that its average is close to the average of the full set?

I am not sure if you are allowed to use a solver for this, but this problem can be easily formulated as a Mixed Integer Nonlinear Programming (MINLP) problem.

This can be solved with open source solvers like Couenne or Bonmin. Actually this model can be linearized so it can even be solved with linear Mixed Integer Programming (MIP) solvers.


The proof states that $(\underbrace{x+x+\dots+x}_{x~ times})' = (\underbrace{1+1+\dots+1}_{x~ times})$. Let's give it a try.

$$\lim _{\epsilon \to 0} \frac{\underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}_{x+\epsilon~ times} - \underbrace{x+x+\dots+x}_{x~ times}} {\epsilon} =\\ \lim _{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{x~ times} + \underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}_{\epsilon~ times}}{\epsilon} = \\ \lim _{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{x~ times} + \underbrace{x+x++\dots+x}_{\epsilon~ times} + \underbrace{\epsilon+\epsilon+\dots+\epsilon}_{\epsilon~ times}}{\epsilon} =\\
\lim _{\epsilon \to 0}\underbrace{1+1+\dots+1}_{x~ times} + \underbrace{x}_{1 ~time} + \epsilon = 2x$$


For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

Note that $b$ is upper bounded by $\log n$, so you can go over all possible integers $x\in\left[1,\lceil\log n\rceil\right]$, and for each $x$ check whether the equation $a^x=n$ has an integer solution, i.e. whether or not $n^{\frac{1}{x}}$ is an integer. You might be interested in root finding algorithms.


Elegant algorithm to semi-decide if two lambda calculus terms are equivalent

Let’s first suppose we can reduce both $t_1$ and $t_2$ to their $\beta \eta$-normal forms;
$$t_1 \twoheadrightarrow_{\beta \eta} M \qquad \text{and} \qquad t_2 \twoheadrightarrow_{\beta \eta} N$$
If $M$ and $N$ are identical, we are done. Otherwise, we check $\alpha$-equivalence by induction on term complexity:

if $M$ is a variable

if $N \equiv M$, output true

if $M$ is an abstraction $(\lambda x. M_1)$

if $N$ is an abstraction $(\lambda y. N_1)$

output whether $N_1[y:=x]$ and $M_1$ are $\alpha$-equivalent

if $M$ is an application $(M_1\ M_2)$

if $N$ is an application $(N_1\ N_2)$

output whether both $M_1$ is $\alpha$-equivalent to $N_1$ and $M_2$ is $\alpha$-equivalent to $N_2$

(You could also use de Bruijn notation and avoid the need for $\alpha$-conversions.)

For non-normalising terms, you can at best use the above procedure after each $\beta \eta$ reduction, but it shouldn't be possible (because of Halting problem) to have anything better than “iterative trying”.


Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

If $SAT \in PSIZE$ then the polynomial hierarchy collapses to the second level:
$\Sigma_2 = \Pi_2$ (see Karp-Lipton theorem ); but $NP=coNP$ (i.e. $\Sigma_1 = \Pi_1$) is stronger (the PH collapses to the first level).


This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an interval of the indices: a first and last element and everything between them.


Analyzing a randomized algorithm for finding an approximate median of an array

As suggested in the comments, the Chernoff bound is the best one because it gives better bounds as the input grows. We can again use this same Chernoff bound to determine a lower bound for the probability of success for the algorithm. This turns out to be $1 - 2 * \exp\left( -\frac13 ε^2 E(K) \right)$ as we have to subtract from $1$ the probabilities $P(G \geqslant (1 + ε) E(G))$ and $P(K \geqslant (1 + ε) E(K))$ because those are exactly the cases, where the algorithm fails to output the desired $ε$-approximate median.


In an FSA, can you have more than one transition for the same symbol from a single state?

The FA in the image is an NFA as clearly a DFA cannot have more than one move for a symbol from a particular state. Also, it doesn't have any moves for state $q_5$ nor for $q_{10}$.


Alternative algorithms for calculating x^2?

Base on the fact that:

If n is an even number $(n = 2m) \implies n^2 = 4m^2$

If n is an odd number $(n = 2m + 1) \implies n^2 = 4m^2 + 4m + 1$

And you can calculate $m$ by bitwise shifting right of $n$, calculate $4m$ (or $4m^2$) by bitwise shifting left.

So you can apply the recursion method to this process to establish the result with $O(\log n)$ time complexity.


Can we check in polynomial time if the language of a DFA is closed against Kleene star?

Assuming your DFA $A = (Q,q_0,F,\delta)$ is minimal, here is one approach:

$L(A) = L(A)^*$ iff $q_0$ is accepting, and adding $\epsilon$-transitions from each accepting state $q$ to $q_0$ does not change the language; the latter is true iff $L(A)\subseteq L(A_q)$ for each $q\in F$, where $A_q = (Q,q,F,\delta)$.

In order to check whether this holds, you can compute the product $A\times A$ and check whether the subset $F\times(Q\setminus F)$ is unreachable from $\{q_0\}\times F$, which you can do in polynomial time. In some more detail:

The product automaton has the form $A\times A = (Q\times Q, (q_0,q_0), F\times F, \delta')$, where

the set of states $Q\times Q$ consists of all pairs $(q_1,q_2)$ with $q_1,q_2\in Q$;
the initial state is the pair $(q_0,q_0)$ (though we won't be needing it for our purposes);
the accepting states are all pairs $(q_1,q_2)$ where both $q_1,q_2$ are accepting in $A$;
the transition function $\delta'$ applies the original transition function to both components of a pair, i.e. $\delta'((q_1,q_2),a) = (\delta(q_1,a),\delta(q_2,a))$.

In order to check whether $L(A)\subseteq L(A_q)$ for some $q\in F$, we start from the pair $(q_0,q)$; there should be no word $w$ such that $\delta(q_0,w)\in F$ and $\delta(q,w)\notin F$, which is equivalent to the set $F\times(Q\setminus F)$ being unreachable from $(q_0,q)$ in $A\times A$.

For example, consider the language given by the regular expression $(a + ab + ba)^*$ mentioned earlier by J-E. Pin. It is accepted by the automaton $A=(Q,q_0,F,\delta)$, where

$Q=\{q_0,q_1,q_2,q_3\}$,
$F=\{q_0,q_1\}$,
$\delta = \{(q_0,a,q_1),(q_1,a,q_1),(q_2,a,q_0),(q_3,a,q_3),(q_0,b,q_2),(q_1,b,q_0),(q_2,b,q_3),(q_3,b,q_3)\}$.

The only pair we have to check is $(q_0,q_1)$; exploring the states we can reach from it, we get:

$\delta'((q_0,q_1),a) = (q_1,q_1)$ - note that both components are the same; since $A$ is deterministic, this will be also be the case for all states reachable from here, in particular we will never reach any $(q,r)$ with $q\in F$ and $r\notin F$. We therefore don't need to explore this branch any further.
$\delta'((q_0,q_1),b) = (q_2,q_0)$. Fine because $q_2\notin F$.
$\delta'((q_2,q_0),a) = (q_0,q_1)$. Back to where we started.
$\delta'((q_2,q_0),b) = (q_3,q_2)$. Not only is $q_3\notin F$, but it is a trap state, i.e. all states we can reach from here are of the form $(q_3,q)$ and therefore not in $F\times(Q\setminus F)$.

Since we cannot reach $F\times (Q\setminus F)$ from $(q_0,q_1)$, we now know $L(A)\subseteq L(A_q)$ and therefore $L(A) = L(A)^*$.


$X = E$, so it remains to define the collection $A$. For each vertex $v_i$ in $V$ create $A_i$ as following: for each edge $x_t$ incident to the vertex $v_i$, add $x_t$ to $A_i$. Thus the edge $x_t=(v_i, v_j) \in E \Leftrightarrow A_i \cap A_j = \{x_t\}$, and every pair $A_i, A_j$ has at most one common element. So, if there are $k$ different elements in $A$ such that every two $A_i, A_j$ of them has non-empty intersection which is exactly the edge between vertices $v_i$ and $v_j$, then these $k$ vertices are pairwise connected meaning that they form a clique.


Select a set of elements from a 2D matrix, such that each element comes from distinct row and column

This is maximum matching in a weighted bipartite graph in disguise. (You can easily convert your objective of minimizing the sum of weights into one of maximizing it.)


Can quantum computers be modelled as a classical computer with access to an oracle?

Technically, the main differences between classical and quantum algorithms are super-position and entanglement that make the concept of oracle in quantum algorithms. As these two are only meaningful in quantum mechanics, you can't have that oracle with the same cost as the quantum algorithms, in classical algorithms.


What's really meant by context-free in the term context-free grammar?

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy.

If you consider context-free grammars, their production rules have the following form:

$$ A \rightarrow \alpha$$

So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the substitution of the non-terminal symbol takes place without considering its "context", that is the other symbols it is surrounded by.

On the other hand, if you consider production rules of context-sensitive grammars, they have the following form:

$$ \beta A \gamma \rightarrow \beta \alpha \gamma$$

where $A$ is a non-terminal and $\alpha$, $\beta$, $\gamma$ are sequences of non-terminals and terminals.

In this case the "context" (i.e., $\beta$ and $\gamma$) of the non-terminal symbol to be substituted influences the effect of the substitution and it is part of the rule itself.

You can find more details in this answer on mathematics and in this answer on software engineering.


Here is a list of algorithms might help you:

RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal unlike CSA.
Connection Scan Algorithm: This is a fast algorithm that doesn't need heavy preprocessing.
Trip-Based Public Transit Routing: requires more preprocessing compared to CSA and RAPTOR
Transfer Patterns

You might also wanna look at OpenTripPlanner algorithms bibliography


Can memoization be applied to any recursive algorithm?

Memoization can be applied to any function.  Whether it helps with a given program or not depends on how often the function is called with the same parameters.

You don't specify what your recursive solution is.  Typically for this problem is imagine something like

change(total, denominations) = sum of change(total - k m, denominations \ m) where m = max(denominations) over k m <= total

Can change be called with the same arguments more than once?  Yes.  For instance if you're trying to make change for $1 you might take two quarters and one dime or you might take no quarters and six dimes.  In either case you'll next be asking for the numbers of ways to make forty cents with a dime and a nickel.  So you can save something by calculating this once and storing the result.


Build a balanced binary tree from list in linear time

Answer #2.

An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows:

build-tree(list A of length n):
  if n == 1:
    return singleton tree of the 1 element in A.

  let m be the median element of A  # linear time select

  let L be all elements in A less than m
  let R be all elements in A greater than m

  construct a max-heap HL from L in linear time
  construct a min-heap HR from R in linear time

  let m be the root node of tree T
  let the structure of HL be the structure of all  left-children in T
  let the structure of HR be the structure of all right-children in T

  return T

Let's try an example on $[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6]$.

First we find the median $m = 8$.
We find $L = [5,1,3,2,4,7,6]$ and $R = [12,9,15,10,11,14,13]$.
Then we have max heap HL as shown below:

Then we have min heap HR as shown below:

Then we fill in the structure of T as follows:

The dotted lines represent the underlying structure of each original heap.

Analysis

The running time is as follows:

$O(n)$ for finding the median.
$O(n)$ for constructing the two heaps.
$O(n)$ for merging the two heaps.

Thus, the total time is still $O(n)$.


Is every program is equivalent to a Push Down Automata?

No. The class of languages recognised by pushdown automata is the class of context-free languages, whereas the class of languages recognised by Turing machines is the class of Turing-recognizable (aka recursively enumerable) languages. All context-free languages are recognisable but the converse does not hold.


Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive

This relation can be written as
$$n \leq \sqrt{2} \text{ and } n+1  > \sqrt{2}$$
or equivalently
$$ ((n^2 < 2) \text{ or } (n^2 = 2)) \text{ and } ((n+1)^2  > 2)$$
In terms of functions
$$h(n) = and[or[ls(sqr(n),2), eq(sqr(n),2)], gr(sqr(n+1),2)]$$
So, we have exponentiation (squaring), increment by $1$ (i.e. $n+1$), less than, equal to, greater than, conjunction, and disjunction. They are all primitive recursive whose composition result in the primitive recursive predicate $h(n)$ equal to $1$ if $n \leq \sqrt{2} \text{ and } n+1  > \sqrt{2}$, and $0$ otherwise.

On @chi's hint:

In fact this predicate is true for only $n=1$. So this predicate is drastically simplified and takes the following form $$h(n)=eq(1,n)$$


Let me spell out the solution.

We first show that Player 2 wins if there is a perfect matching $\pi$. Player 2's strategy is very simple: if the current path ends at a vertex $v$, she choose $\pi(v)$. Induction shows that $\pi(v)$ is never taken, since the edges chosen by Player 1 never belong to the perfect matching. Player 2 never gets stuck, and so wins.

The more complicated case is when there is no perfect matching. Let $\pi$ be a maximal matching, and let $x \in X$ be a vertex not in $\pi$. Since $x \notin \pi$, the edge $(x,y)$ chosen by Player 2 is not in $\pi$. If he can, Player 1 now choose $\pi(x)$, and induction again shows that Player 2 never chooses edges in $\pi$, and so Player 1 can choose an edge in $\pi$ as long as there is one adjacent to the vertex that Player 2 chose. If Player 1 gets stuck then the edges chosen by the players trace out an alternating path with Player 2 having one extra edge, showing that $\pi$ wasn't a maximal matching.


Method to change value in a key for a min heap

Find the key's node
Change the node's key to the new key
Heapify the node

This will work in $O(log(n))$ worst case.

If the old key is the new key the node wont move. You can also explicitly check it before searching for the node, if you prefer.


How is Pure Maths utilized in Computer Science research?

Let's do these in the order you listed. I will not be comprehensive, I will just try to impress you by pointing out cool applications of mathematics in CS. Others may know of even cooler applications.

Linear algebra is used to compute the Page rank of web pages, which is the basis of Google engine ordering pages from more relevant to less relevant.
Abstract algebra is used to model computational effects, such as exceptions, input/output, memory, parallel computation etc.
Functional analysis is used in the JPEG image format which uses Fourier analysis to achieve lossy compression.
Topology is used in domain theory to give mathematical models of programming languages. Algebraic topology is used in topological data analysis, and homotopy theory is used in homotopy type theory to study equivalence of datatypes (I am oversimplifying) and how to convert between them.
Number theory is used in cryptography to provide public key protocols, such as the RSA algorithm. These are used every time you buy anything on the Internet.

So, is that convincing enough?


Is complement of diagonal language countable?

A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$.  To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.


How many combination of “n” bits are there in terms of n?

Each bit can be either 0 or 1, so you have two choices per bit. That gives you 2^n combinations. E.g. n=1 implies 2^1=2 states, n=2 implies 2^2=4 states. You could arrive at this by 1) making a lexicographic list of all the combinations or 2) using a formula from combinatorics.

Your second question seems to address representing integers with binary numbers. You must first settle on an encoding scheme before that question can be answered. A popular encoding scheme is two's complement. The maximum positive integer represented in 4-bit two's complement is 0111, which is 7.


CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$

In this case you have the union of two trivially CGF languages and usually that is achived by the following trick. You write some $S_1$ grammar for the first one, $S_2$ grammar for the second one and just "or" them somewhere at the top level (here it's $S$). Your approach was just to use single recurrent literal, if I can say like that, and thus it was difficult to come up with CGF rules.

You would get something like this:

   $S \to S_1 | S_2 $

 $S_1 \to a^2 S_1 b | a^2 b$

 $S_2 \to a S_2 b^2 | a b^2$


You can add $n$ numbers of size $w$ without any overflow if you are using $\lceil \log n\rceil + w$ bits arithmetic.  My suggestion is to do just that and then check if the result is in the range.  Algorithms for multiprecision arithmetic are well-known (see TAOCP section 4.3 if you need a reference), there is often hardware support for addition (carry flag and add with carry instruction), even without such support you can implement it without data dependant jump (which is good for jump predictors) and you need just one pass on the data and you may visit the data in the most convenient order (which is good for cache).

If the data doesn't fit in memory, the limiting factor will be the IO and how well you succeed in overlapping the IO with the computation.

If the data fit in memory, you'll probably have $\lceil \log n\rceil \leq w$ (the only exception I can think of is 8-bits microprocessor which usually have 64K of memory) which means you are doing double precision arithmetic. The overhead over a loop doing $w$-bits arithmetic can be just two instructions (one to sign extend, the other to add with carry) and a slight increase of register pressure (but if I'm right, even the register starved x86 has enough registers that the only memory access in the inner loop can the data fetch). I think it is probable that an OO processor will be able to schedule the additional operations during the memory load latency so the inner loop will be executed at the memory speed and thus the exercise will be one of maximising the use of the available bandwidth (prefetch or interleaving techniques could help depending on the memory architecture).

Considering the latest point, it is difficult to think of other algorithms with better performance. Data dependant (and thus not predictable) jumps are out of question as are several passes on the data. Even trying to use the several cores of today's processor would be difficult as the memory bandwidth will probably be saturated, but it could be an easy way to implement interleaved access.


Feasible to apply image "interlacing" concept to video streaming for smoother buffering?

Such a concept exists, for example in MPEG-4 Scalable Video Coding. It's complicated, it comes at a cost in coding efficiency (quality/bitrate), and I don't know of anything that supports it. However it's an area of active research and it might be the way of the future. Given the current state of the art, it's a lot more practical just to do multiple transcodes, segment, and switch between them.


Proof of correctness of reversal algorithm for array rotation

Here is a proof by picture, which follows the steps of the algorithm:
$$
0,\ldots,d-1,d,\ldots,n-1 \\
d-1,\ldots,0,d,\ldots,n-1 \\
d-1,\ldots,0,n-1,\ldots,d \\
d,\ldots,n-1,0,\ldots,d-1
$$
You can easily turn this into a formal proof by giving a formula for the permutation after each step, which you can easily prove correct.


Minimum spanning tree with small set of possible edge weights

No, Kruskal's algorithm doesn't make any assumptions about how fast edges can be sorted.  I suspect you misinterpreted what you read.  Kruskal's algorithm doesn't make assumptions.

You linked to a Wikipedia article.  It states:

  Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in O(E α(V)) time

"Provided" means "If", not "We assume that".

If you use a standard sorting algorithm that takes $O(E \log E)$ time, then Kruskal's algorithm runs in $O(E \log E)$ time.  If you are in a special situation where there is a way to sort the edges in linear time (e.g., using counting sort), then Kruskal's algorithm can be implemented in a way that takes $O(E \alpha(V))$ time, which is faster.  But there is no assumption that you will always be in that special situation; usually, you won't.

The case where there are only two edge weights is indeed such a special situation, and thus Kruskal's algorithm can be implemented in a way that is asymptotically faster for such graphs than for general graphs.


About Control Unit in CPU and Clock Cycle

1.) (Almost) every component of the CPU needs to be synchronized by the clock, which means they all do their work only if the clock is high (1); never when it's low (0) (or alternatively only during rising edge). This could for example be implemented using an AND-gate, with the input to the component as first and the clock signal as second input. So the component will only get its new input if the clock is currently high, else it does nothing. And because the clock speed is set above the longest time any signal needs to propagate through any circuit in the CPU, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The control signals can be set at any time, but they will only be accepted during high clock.

2.) This is no loop, since the PC is actually a register which is egde triggered. This means, like mentioned above, that it is changing its state only one time per cycle for a short period of time. At an earlier time, the last output from ALU (PC + 1) is just waiting at the input of the PC. Then, at the next cycle, the PC takes its input. This is when PC = PC + 1 actually happens.


Bipartite graph matching with multiplicities

For k=2 it's Rainbow_matching, so it's NP-complete.

For all colors X make cliques of all people holding color X, and color it's edges with X.


Where should we place action symbols in a grammar?

Generally, there isn't an algorithm for placing the action symbols. You always need logic in there.

In your case, you want to take the action @add right after you read the second operand of +. The derivations are leftmost, which means that the leftmost rules are going to be expanded and evaluated before the right rules. That said if you have an input of id1 + id2 * id3, the @add action symbol will be useful after id2 because up to then you have the two operands that you want to add. Exactly the same with the @mul, which is useful after id3.

Another issue is the precedence rules of the operations. We want multiplications execute before additions. The above example should be executed as id1 + (id2 * id3). Your grammar takes that into account :) . Let's see the syntax tree and I'm sure that will explain everything to you:

Now you can see the actual sequence of the rules, the precedence of Multiplication and why the position of action symbols isn't something fixed.

In another grammar, somebody would first read the id and after that have an action symbol to take it into the symbol table (usually in programming languages like Fortran).

Don't hesitate to comment me if I did not cover you.


How to best calculate the best possible path with weights

Build the metagraph of strongly connected components.  Then execute your idea on the metagraph.  Note that once you enter a strongly connected component through any in-edge, you can collect all coins within it and leave through any out-edge out of that component.


Efficient compression of simple binary data

Sure, of course there are algorithms.  Here is my algorithm:

First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$.  If so, write out a 0 bit followed by $n$ one bits followed by a 0 bit.
If not, write out a 1 bit, then write out the 7z-compression of the file.

This is extremely efficient for files of that particular structure.

The point is: there is no free lunch in data compression.  You might be able to build a compression algorithm that compresses one type of file well, at the cost of compressing others worse.  But, if you know a priori something about the nature of the files you will be compressing, you can optimize your algorithm for that particular type of file.

The area is "data compression".  See our data-compression tag, and read textbooks on data compression.


Given a family of hash functions in table form, how can I know whether it's universal?

As you have stated, given a family $H$ of hash functions, the condition for universality is $\forall x,y, x \neq y: \text{P}_{h \in H}(h(x) \neq h(y)) \le \frac{1}{m}$. The probability is taken over $h \in H$, which is picked following a uniform distribution.

If you think for a while about what that means, you'll realize you need simply check whether there is at most one collision (i.e., equal entries) for any two distinct columns (i.e., every pair of $x$ and $y$) in the respective family's table. Hence, $G$ is universal, but $H$ is not; I'll let you figure out why.


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


Can the lambda string be generated in any grammar?

No.  $S \to \lambda$ is not implicit.  It is only present if it is explicitly listed in the grammar, otherwise there is no such production.  There are no implicit rules.  You've misinterpreted the definition.  The definition says what kinds of rules are allowed to be present in the grammar, not what will definitely be present.


What is an efficient data structure for prefix matching?

A trie is asymptotically optimal for this.  No data structure can achieve better asymptotic running time.

If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them.  Standard theoretical running time analysis is not reliable at predicting constant factors.

Another data structure to consider is to store every prefix of each word in a hashtable.  This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice.  The asymptotic running time will remain the same.  You'll have to decide whether you're willing to trade off space for time.

Suffix trees and suffix arrays don't seem relevant.  You're asking about prefix matching, not suffix matching or matching in the middle of the string.


What is the meaning of a prefix-free language?

You are correct: {a, b} is prefix-free, but {a, b, ac} is not.

The idea of a prefix-free code is that once you recognize a word you know for sure it's a word.  So for instance a code that includes both CONNECT and CONNECTICUT is not prefix-free, because if you start parsing a phrase like

ACONNECTICUTYANKEEINKINGARTHURSCOURT

taking every word as soon as you see it you're going to read this as

A, CONNECT, I, CUT, YANK, (error)

since you can't do anything with the string EEINKINGARTHURSCOURT.  (That's assuming you don't also consider CON a word also; if so, things would be even worse.)

Note that adding spaces between words is basically a way of making a code prefix-free: if "connect" by itself isn't considered a word, but "connect " is, then you'll have no trouble parsing

A CONNECTICUT YANKEE IN KING ARTHURS COURT


Intuitive way to understand the triangle spectrum?

Suppose there is a sound with frequency 440Hz. How large is each period of this periodic signal? It must be (1/440)s. The same applies in your case.


Why values can not be replaced with their extensionally equal values in an intensional system?

Supposing we have $a$ and $b$ of type $A$ and $p : \mathrm{Id}_A(a,b)$, there simply is not any rule of type theory that would allow you to replace $b$ with $a$ arbitrarily. So one answer is "because type theory does not let you do that", and if you think that it can be done, please show me how. But I suppose that is a non-answer, what you really are asking is why is type theory designed in such a strange way.

There are many ways to understand equality. Students of mathematics are typically taught only one, namely the equality arising from set theory and classical mathematics. This kind of equality is very intuitive and easily understood. But as you learn more mathematics, you begin to understand that sometimes two objects are not really equal, but are "kind of equal". For example, they could be isomorphic, or connected by a path. So it makes sense to look for other explanations of equality that capture the idea of a more "relaxed" equality.

In mathematics it makes a lot of sense to say that functions are equal if they produce the same outputs, but this is not so in computer science. For example, if functions $f$ and $g$ produce the same outputs, but one is much faster than the other, then it is useless for a computer scientist to consider them equal.

Type theory is a formal system which allows us to express these ideas. The identity type $\mathrm{Id}_A(a,b)$ is not necessarily the "true equality" (the only one that a student of classical mathematics knows about, and therefore calls it "true") of $a$ and $b$, it could be one of these other notions of equality that you learn about when you study homotopy theory and computer science.

For instance, one way to undertand $p : \mathrm{Id}_A(a,b)$ is to say that $p$ is some sort of a "path" from $a$ to $b$. That is, $a$ and $b$ are not "really equal", but there is a way to get from $a$ to $b$. And so, if $P :A \to \mathrm{Type}$, we certainly would not expect $P a$ and $P b$ to be "exactly the same", but rather that "there is a way to get from $P a$ to $P b$". Indeed, this goes under name transport and it follows from the rules for the identity type: given $p : \mathrm{Id}_A(a,b)$, there is a isomorphism of types $\mathrm{transport}_p : P a \to P b$.


How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Here is the skeleton of the proof. I leave it to you to fill in the
details.

Let $R$ be a FSA recognizing the set $A$ of ambiguous strings of $G$
(yes, I am generalizing a bit the problem to regular sets of ambiguous words, since it is no harder). Let
$\bar R$ be a DFA recognizing the complement $\bar A$ of $A$: $\bar
A=\Sigma^*-A$.

We can use the cross-product construction for intersection of the
languages of a CF-grammar and a FSA, applying it to $G$ and $\bar R$
to get a CF grammar $G'$ that recognnizes $L'=L-A$. This grammar $G'$ is
not ambiguous, since it has exactly the same parse trees as $G$, up to
renaming of non-terminals (and the ambiguous words have been removed).
The FSA $\bar R$ has been chosen deterministic to make sure it has at most one accepting computation on any input, and thus does not introduce new ambiguities.

Then, Since the language $A$ is regular, it is easy to produce a
non-ambiguous CF (or regular) grammar $F$ that recognizes $A$.

Then, given the two non-ambiguous grammars $G'$ and $F$, generating
respectively $L'=L-A$ and $A$ which have an empty intersection, it is
easy, with one extra production rule, to produce a non-ambiguous grammar $G''$ that
recognizes the union $L'\cup A=(L-A)\cup A=L$.

So the non-ambiguous grammar $G''$ generates the language $L$. QED

That is all very nice, but given some CF grammar G you may not be able
to do all this, even when it is actually possible.


In an Inverted Page Table, will following chains happen very often for small addresses?

According to my knowledge, inverted page table has an entry for each physical frame, not for each logical page.

It is usually designed as a Hash table, where the Hash function takes both the task id and the page number as parameters. Thus (task A, address X) and (task B, address X) will not be likely to produce the same Hash value.

Does that answer your question?


Why is Church-Rosser so important for basing programming languages on lamdba-calculus?

Think of it as a sanity check. CR cones from the days when we were just figuring out what programming languages were. The Lambda calculus was new, and its basic properties were unknown.

CR says that Lambda Calculus behaves like you would expect: every expression can be evaluated to a unique value, or runs forever. We didn't know if the calculus was well behaved. We had to prove it.

Imagine that CR didn't hold, and that the order you evaluated an expression mattered. We would throw Lambda calculus away. It would be like saying $2+2$ could have more than one value.

CR also justifies the existence of lazy languages, showing that they behave at least as well as eager languages, sometimes better. Haskell certainly owes its existence in part to CR.


Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book?

Those definitions are saying the same thing (at the level of precision of the English description).

An example from the book

Normal-order evaluation goes “fully expand and then reduce”, meaning that function calls are expanded before reducing the arguments, and the reduction only happens when the value is needed. Let's take one of the examples in the book: start from (sum-of-squares (+ 5 1) (* 5 2)). First, we fully expand the definition of sum-of-squares:

(sum-of-squares (+ 5 1) (* 5 2)) → (+ (square (+ 5 1)) (square (* 5 2)))

Since + is a primitive, we can't expand it. It requires integers as arguments, so here we have no choice: we must reduce the arguments. To reduce (square (+ 5 1)) in normal order, we start by expanding:

(square (+ 5 1)) → (* (+ 5 1) (+ 5 1))

Then we have the primitive *, also requiring integers as arguments, so we must reduce the arguments.

(+ 5 1) → 6
(+ 5 1) → 6

and so

(* (+ 5 1) (+ 5 1)) →→ (* 6 6) → 36

and likewise for (square (* 5 2)), so the original expression finally evaluates thus

(+ (square (+ 5 1)) (square (* 5 2))) →→ (+ 36 100) → 136

In contrast, applicative-order evaluates the arguments when the function is applied, before expanding the function call. So to evaluate (sum-of-squares (+ 5 1) (* 5 2)), we first need to evaluate the arguments:

(+ 5 1) → 6
(* 5 2) → 10

and then we can expand the function call:

(sum-of-squares (+ 5 1) (* 5 2)) →→ (sum-of-squares 6 10)
                                 → (+ (square 6 6) (square 10 10))

The next step is to evaluate the arguments of +; they're function calls, and in each case the arguments are already fully evaluated so we can perform the function call right away:

(square 6 6) → (* 6 6) → 36
(square 10 10) → (* 10 10) → 100

and finally

(+ (square 6 6) (square 10 10)) →→ (+ 36 100) → 136

An example with side effects

The order of evaluation doesn't make any difference when the expressions have no side effect. (Except with respect to termination, if you don't consider non-termination a side effect: an expression may terminate in some evaluation orders and loop forever in others.) Side effects change the deal. Let's define a function with a

(define (tracing x)
  (write x)
  x)

If we evaluate (square (tracing 2)) in applicative order then the argument is evaluated only once:

(tracing 2) → 2 [write 2]
(square (tracing 2)) → (square 2) [write 2]
                     → (* 2 2)
                     → 4

In normal order, the argument is evaluated twice, so the trace is shown twice.

(square (tracing 2)) → (* (tracing 2) (tracing 2))
(tracing 2) → 2 [write 2]
(tracing 2) → 2 [write 2]
(* (tracing 2) (tracing 2)) →→ (* 2 2) [write 2, write 2]

You can observe this in Scheme. Scheme applies applicative order to function evaluation, but also has a macro facility. Macro calls use normal order.

(define-syntax normal-order-square
  (syntax-rules () ((normal-order-square x) (* x x))))

At a Scheme prompt, you can see that (square (tracing 2)) prints 2 once whereas (normal-order-square (tracing 2)) prints 2 twice.

Towards theory

Let's present the rules of evaluation in a more formal way (with small-step semantics). I'm going to use a notation that's closer to what is commonly used in theory:

$(\lambda x y. A)$ is (lambda (x y) A), where $A$ is an expression.
$B[x\leftarrow A]$ means to take the expression $B$ and replace all occurrences of $x$ by $A$.
$[\![ \ldots ]\!]$ is an integer obtained by some mathematical computation, e.g. $[\![ 2+2 ]\!] = 4$.
$A \xrightarrow{\;t\;} B$ means that the expression $A$ evaluates to the expression $B$, and in doing so prints the trace $t$.

I'll simplify away everything that's related to variable binding: a variable is considered equivalent to its definition.

Evaluation rules come in two flavors. There are head rules, that explain how to make progress on the evaluation of an expression by looking at the topmost node in the syntax tree.

$$ \begin{align}
  ((\lambda x. B) \: A) &\longrightarrow B[x \leftarrow A] && (\beta) \\
  ((\lambda x_1 x_2. B) \: A_1 \: A_2) &\longrightarrow B[x_1 \leftarrow A_1, x_2 \leftarrow A_2] && (\beta_2) \\
  (* \: i \: j) &\longrightarrow [\![ i \times j ]\!] && (\delta_*) \\
  (\texttt{tracing} \: x) &\xrightarrow{\;x\;} x && (\delta_{\texttt{tracing}}) \\
\end{align} $$

$(\beta)$ is the rule the application of a user-defined function. I've defined a variant for two arguments (there are other, better ways to treat functions with multiple arguments but that's a topic for another day). The $(\delta)$ rules are for the evaluation of primitives (I'm treating tracing as a primitive because expressing it in terms of progn and write would unnecessarily complicate this presentation).

There are context rules, that explain how to look for things to evaluate deeper inside the evaluation syntax tree. The notation $\dfrac{P}{C}$ means “if there's a way to do the reduction $P$ according to the rules, then $C$ is also a valid reduction”. In other words, assuming that the premise above the line holds, the conclusion below the line holds.

$$
  \dfrac{A \xrightarrow{t} A'}{(F \, A \xrightarrow{t} F \, A')} (\texttt{App}^1_1)
  \qquad
  \dfrac{A_1 \xrightarrow{t} A_1'}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1' \, A_2)} (\texttt{App}^2_1)
  \qquad
  \dfrac{A_2 \xrightarrow{t} A'_2}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1 \, A_2')} (\texttt{App}^2_2)
$$

For example the rule $(\texttt{App}^1_1)$ means that to evaluate a function call, we can evaluate the argument. In a full treatment, there would be a similar rule for the function part, but we don't need it here.

The arrow $\longrightarrow$ means “evaluates in a single step to”. We can derive the notion of “evaluates to” (in any number of steps):
$$
  \dfrac{}{A \xrightarrow{} A}
  \qquad
  \dfrac{A \xrightarrow{\;t\;}^* B \text{ and } B \xrightarrow{\;t'\;} C}{A \xrightarrow{\;t,t'\;}^* C}
$$
The first rule means that an expression evaluates to itself (in zero steps). The second rule allows adding one more step to a sequence of evaluations.

These rules are non-deterministic: there can be more than one applicable rule for a given expression, and thus there are multiple possibilities to evaluate an expression. This is where evaluation strategies come into play. An evaluation strategy defines a priority on the rules.

In normal order, $(\beta)$ (the application rule) is applied before context rules that would affect the arguments. This is what the first quote means by “fully expand [apply head rules] and then reduce [in context]”, and what the second quote means by “delay the evaluation of procedure arguments until the actual argument values are needed” (don't apply context rules until forced by a $\delta$ rule). (In the first quote, the use of the word “expand” is somewhat jarring — applying $(\beta)$ is a reduction too!)
In applicative order, the context rules are applied first, and $(\beta)$ is only applied if the arguments can't be evaluated anymore. This is what the first quote means by “evaluate the arguments [in context] and then apply [head rules]”, and what the second quote means by “all the arguments (…) are evaluated when the procedure is applied [before performing the actual application]”.

Let's look at (square (tracing 2)) in this model. In the notation I've presented, that's $((\lambda x. (* \: x \: x)) (\texttt{tracing} \: 2))$. In normal order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))
  &\longrightarrow (* \: (\texttt{tracing} \: 2) \: (\texttt{tracing} \: 2)) && \text{by \((\beta)\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: (\texttt{tracing} \: 2)) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_1\)} \\
  &\xrightarrow{\;2\;} (* \: 2 \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_2\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
In applicative order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x))\:  (\texttt{tracing} \: 2))
  &\xrightarrow{\;2\;} ((\lambda x. (* \: x \: x)) \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^1_1\)} \\
  &\longrightarrow (* \: 2 \: 2) && \text{by \((\beta)\)} \\
  &\longrightarrow 4 && \text{by \((\delta_*)\)}
\end{align} $$
(I used left-to-right evaluation for function arguments; specifying this is necessary to get a fully deterministic evaluation order.)
This shows how $((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))$ evaluates to $4$ with the trace $2,2$ under normal order, but to $4$ with the trace $2$ under applicative order.


Expressing iterative version of fold in terms of recursive version

For easier typing let me rename $\mathsf{fold}_{recur}$ to $\mathsf{foldr}$ and $\mathsf{fold_{itr}}$ to $\mathsf{foldl}$ (an additional reason for the renaming will soon be apparent).

Then we have
$$\mathsf{foldr} \,(h,c) \,[x_1, x_2, \ldots, x_n] =
  h(x_1, h(x_2, \ldots, h(x_{n-1}, c) \ldots ))$$
and
$$\mathsf{foldl} \,(h,c) \,[x_1, x_2, \ldots, x_n] =
  h(\ldots h(h(c, x_1), x_2), \ldots, x_n).
$$
That is, your two different folds are also known as the right and left fold in functional programming languages. You are asking how to get the left fold in terms of the right fold. The short answer is "by reversing the list".

Suppose we had a list reversing function $\mathsf{rev}$. Then we could define
$$\mathsf{foldl} \, (h,c) \, \ell =
  \mathsf{foldr} \, ((\lambda (x,y) . h(y,x)),c) \, (\mathsf{rev} \, \ell).
$$
We just need $\mathsf{rev}$ expressed in terms of right fold:
$$\mathsf{rev} \, \ell =
  \mathsf{foldr} \, (\mathsf{append}, \mathsf{nil}) \, \ell
$$
and
$$\mathsf{append}(x, \ell) =
  \mathsf{foldr} \, (\mathsf{cons}, \mathsf{cons}(x,\mathsf{nil})) \, \ell.
$$
You can fold all these definitions into one fat definition of $\mathsf{rev}$, if you want to impress your teacher.


Do the polynomials in "polynomial time" have integer, real or complex coefficients?

When people say polynomial time, they mean that the time has polynomial growth, that is if we denote the time by $T(n)$, then $T(n) = O(n^c)$ for some real $c$. We get the same definition if we only allow integer $c$. Since $T(n)$ is real-valued, it wouldn't make sense to consider complex polynomials here.

The exact running time need not actually be a polynomial. For example, an algorithm running in time $n\log n$ (exactly) still runs in polynomial time, since (for example) $n\log n = O(n^2)$.


It is an illusion that the computation rules "define" or "construct" the objects they speak about. You correctly observed that the equation for $\mathrm{ind}_{=_A}$ does not "define" it, but failed to observe that the same is true in other cases as well. Let us consider the induction principle for the unit type $1$, which seems particularly obviously "determined". According to Section 1.5 of the HoTT book we have
$$\mathrm{ind}_1 : \prod_{C : 1 \to \mathtt{Type}} C(\star) \to \prod_{x : 1} P(x)$$
with the equation
$$\mathrm{ind}_1 (C, c, \star) = c.$$
Does this "define" or "construct" $\mathrm{ind}_1$ in the sense that it leaves no doubt as to what $\mathrm{ind}_1$ "does"? For instance, set $C(x) = \mathbb{N}$ and $a = 42$, and consider what we could say about
$$\mathrm{ind}_1(C, 42, e)$$
for a given expression $e$ of type $1$. Your first thought might be that we can reduce this to $42$ because "$\star$ is the only element of $1$". But to be quite precise, the equation for $\mathrm{ind}_1$ is applicable only if we show $e \equiv \star$, which is impossible when $e$ is a variable, for example. We can try to wiggle out of this and say that we are only interested in computation with closed terms, so $e$ should be closed.

Is it not the case that every closed term $e$ of type $1$ is judgmentally equal to $\star$? That depends on nasty details and complicated proofs of normalization, actually. In the case of HoTT the answer is "no" because $e$ could contain instances of the Univalence Axiom, and it is not clear what do to about that (this is the open problem in HoTT).

We can circumvent the trouble with univalance by considering a version of type theory which does have good properties so that every closed term of type $1$ is judgmentally equal to $\star$. In that case it is fair to say that we do know how to compute with $\mathrm{ind}_1$, but:

The same will hold for the identity type, because every closed term of an identity type will be judgmentally equal to some $\mathrm{refl}(a)$, and so then the equation for $\mathrm{ind}_{=_A}$ will tell us how to compute.
Just because we know how to compute with closed terms of a type, that does not mean we have actually defined anything because there is more to a type than its closed terms, as I tried to explain once.

For example, Martin-Löf type theory (without the identity types) can be interpreted domain-theoretically in such a way that $1$ contains two elements $\bot$ and $\top$, where $\top$ corresponds to $\star$ and $\bot$ to non-termination. Alas, since there is no way to write down a non-terminating expression in type theory, $\bot$ cannot be named. Consequently, the equation for $\mathrm{ind}_1$ does not tell us how to compute on $\bot$ (the two obvious choices being "eagerly" and "lazily").

In software engineering terms, I would say we have a confusion between specification and implementation. The HoTT axioms for the identity types are a specification. The equation $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ is not telling us how to compute with, or how to construct $\mathrm{ind}_{=_C}$, but rather that however $\mathrm{ind}_{=_C}$ is "implemented", we require that it satisfy the equation. It is a separate question whether such $\mathrm{ind}_{=_C}$ can be obtained in a constructive fashion.

Lastly, I am a bit weary of how you use the word "constructive". It looks as if you think that "constructive" is the same as "defined". Under that interpretation the Halting oracle is constructive, because its behavior is defined by the requirement we impose on it (namely that it output 1 or 0 according to whether the given machine halts). It is prefectly possible to describe objects which only exist in a non-constructive setting. Conversely, it is perfectly possible to speak constructively about properties and other things that cannot actually be computed. Here is one: the relation $H \subseteq \mathbb{N} \times \{0,1\}$ defined by
$$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$$
is constructive, i.e., there is nothing wrong with this definition from a constructive point of view. It just so happens that constructively one cannot show that $H$ is a total relation, and its characteristic map $\chi_H : \mathbb{N} \times \{0,1\} \to \mathsf{Prop}$  does not factor through $\mathtt{bool}$, so we cannot "compute" its values.

Addendum: The title of your question is "Is path induction constructive?" After having cleared up the difference between "constructive" and "defined", we can answer the question. Yes, path induction is known to be constructive in certain cases:

If we restrict to type theory without Univalence so that we can show strong normalization, then path induction and everything else is constructive because there are algorithms that perform the normalization procedure.
There are realizability models of type theory, which explain how every closed term in type theory corresponds to a Turing machine. However, these models satisfy Streicher's Axiom K, which rules out Univalence.
There is a translation of type theory (again without Univalence) into constructive set theory CZF. Once again, this validates Streicher's axiom K.
There is a groupoid model inside realizability models which allows us to interpret type theory without Streicher's K. This is preliminary work by Steve Awodey and myself.

We really need to sort out the constructive status of Univalence.


Longest double increasing subsequence (LIS variant)

A counter example where your algorithm fails:
S = 0 7 1 4 6 5 3 2.

Expected : 5, your algorithm would produce 3

There is an O(n^3) dynamic programming based algorithm for this if you are interested :)


Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

Range of any hash function is a sub-set of natural numbers (this is how we think of it, exactly for access to the arrays, that could lie behind). The actual output of common hash-functions (MD5, SHAX...) is $n$ bits, where $n$ is $128$ for MD5 and $512$ for SHA2 with 80 rounds.

These bits can then be interpreted as natural numbers from interval $[0, 2^n-1]$. They can also be interpreted as integer from $[-2^{n-1},2^{n-1}]$. They can also be interpreted as "strings", although in essence they are only bits. What @Arani is talking about (I think) is probably conversion of this binary number to the hexadecimal format, and viewing it as string.


Confusion in understanding a DFA question

Either you can make a 1 transition from every state to a non-final sink state. Or make a note that any character that doesn't match an available transition goes to a non-final sink state.
Depends on what format is usual for the course.
I assume the reason that 1 is also in the alphabet is to trip up people who forget about this sink state.


What does it mean for a problem to be solved in polynomial time "relative to" an oracle?

Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In the classical case, the algorithm can query the oracle on a specific input $x$, and it immediately gets the (Boolean) value of the oracle at that input: 1 if $x \in O$, and 0 if $x \notin O$. I'm not quite sure how this works in the quantum case, but perhaps the PDF explains that.

The theorem states that there is some oracle that allows quantum algorithms to solve some problems much faster than classical ones. That is, if a quantum algorithm is given access to this oracle, then it can solve some problem in time Q, but a classical algorithm which is given such access can only solve the problem in time C$\gg$Q.


For certain instructions in certain pipeline stages, we don't care about the results or operation of one or more of the hardware's many functional units.

Let's say the processor implementation has several functional units, e.g. in the ALU, for addition/subtraction, one for and/or, one for multiplication, one for division, one for shifting, and maybe even (separate from the ALU) one for computing addressing, e.g. combined shift & add for the various load & store instructions.  there may also be a completely separate adder next to the PC for doing pc-relative branches.

All that hardware is always there, but not all is always being used.

So, for example, when doing an unconditional branch instruction, the regular ALU is still there doing something, but we don't care about it.  All we have to do is ignore the unit's output, e.g. don't write it to a register.

So, at the times when we don't care about the regular ALU's output, we also don't care about the signals going into the ALU — the source operands, and the code that says whether to add vs. and vs. other.  We need to ignore not just the ALU's output, then but also any signals like overflow.  However, that is pretty easy to do, so sometimes this is done (ignoring output while giving "don't care" input), instead of instructing the ALU to do something specific during don't care, like adding 0 + 0.

However, when it comes to memory we never want to initiate a memory reference with a potentially garbage address, even a read, let alone a write, which could be destructive of program state.  Keep in mind that the memory reference goes thru the cache and then potentially off-chip, to the memory devices, and/or to I/O devices.  We don't even want to issue a read to a known or hard-coded address (like 0).  If the instruction isn't a memory reference, we should not touch memory at all!!  And we do that by forcing both the read and write signals to 0.


Determining a value in an algorithm on its first run

Posting Yuval Filmus's comment as an answer since they didn't:

  It’s a typo - should be $c’=$ instead of $c’-$ in line 5.


How to convert a context free grammar (could generate regular language) to a right-linear grammar

Assuming you want your general method to be computable, the answer is no. When you consider a CFG that generates a regular language and convert it into a right-linear grammar, the size-increase is not bounded by any computable (or "recursive") function (first shown by Meyer and Fischer in this paper; also, if you can access it, this paper by Kutrib is a nice survey on the general area of non-recursive tradeoffs).

If a (computable) general conversion method existed, you could use it to construct a computable bound on the blowup between CFGs and right-linear grammars, which would contradict the non-existence of such a bound. Thus, knowing that your grammar generates a regular language does not help you at all.


u can try: http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx

i hope this'll help.


Linear Path Optimization with Two Dependent Variables

You can consider the 1D-position of the 2 runners as one 2D-position.
X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).

Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the Tchebychev distance (infinite norm). I am pretty sure this is NP-complete.

A simple heuristic approach may be to always run to the next closest point (greedy nearest neighboor). Or you can either look for a more sophisticated one...


LL(1) grammars must be unambiguous, have no left recursion, and no conflicts.
The grammar you provide is unambiguous in terms of the syntax tree, however there are conflicts when parsing (which stops it from being an LL(1) grammar). The conflicts reside in the first set of S and C. That is to say, FIRST(S) = { b }, but its ambiguous in which production rule to apply: S -> bAb or S -> bBa. This can be eliminated by factoring out the b as such:
S  -> b S'
S' -> A b | B a

Similarly for C:
C  -> c C'
C' -> c C' | eps

The grammar also has left recursion in the rule B -> Bc; this is the definition of left recursion. This can be removed as such:
B   -> b B'
B'  -> c B' | B''
B'' -> c

Check the following for more information:

LL parser: https://en.wikipedia.org/wiki/LL_parser
Left recursion: https://en.wikipedia.org/wiki/Left_recursion
CFG checker (including LL(1)): http://smlweb.cpsc.ucalgary.ca/


how can i proof $3^n$ has a greater growth than $n2^n$?

One simple way would be divide both sides by $2^n$ to get $n$ and $(1.5)^n$. You can simply take a limit of $l  i  m_{n\to\infty} \frac{(1.5)^n}{n} = \infty$ To show that $(1.5)^n$ grows larger. This limit holds for any number larger than 1.


Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$?
There are two options:

Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.

(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!


Average-Case Analysis of a Simple Max-Finding Algorithm

Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested.

Another way to derive this result is to use indicator variables. Let $X_i$ be an indicator variable that is 1 if the value of max changes on the iteration of the loop corresponding to a length-$i$ subarray and 0 otherwise. Assuming the permutation given as input is uniformly random, this variable is 1 with probability $\frac{1}{i}$ because max only changes if the inspected element is the largest of its group. Using linearity of expectation, you can use this to show that the number of updates on expectation is $\Theta(\log n)$. Knuth's talk gives a different perspective using generating functions and derives a precise value as well as the variance.


Like Geier said, processors can't directly handle values smaller than a byte.  So a boolean type that was actually implemented as just a single bit would in most cases be inefficient.  The processor needs to do a bit of extra work to extract just that one bit.

The reason that the boolean type exists is more about semantics than anything else.  Logical true/false values is a very useful concept.  In many programming languages a conditional expression like "if x is 5" has a boolean value as the result.  And lets not forget that a boolean type corresponds nicely to a single bit, which is the building block of the binary numbers that computers work with.

There has been tri-state "booleans" in use, and there probably still is today.  But they are generally less useful and more complicated to deal with than the ordinary true/false ones.

What you are talking about would generally be implemented as bit flags (or bit fields), or simply by assigning different meanings to different numbers.


What complexity class would this version of generalized chess fall?

because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

It is possible that generalized chess is in $NP$. We do not have a proof that $NP \not = EXPTIME$ or a proof that a certificate for generalized chess would take an exponential amount of steps. It is highly likely, though.

  But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game).

This is unknown. It is known that if two players work together to reach a given position then this may take an exponential amount of moves but this doesn't apply to the specific case of whether white can win and doesn't allow us to conclude whether the problem is in $NP$ or not (because even if it takes an exponential amount of moves, maybe there is a "smarter" certificate that can prove this exponential sequence of moves exists in polynomial time).

  because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

No. Shortest path can be solved in exponential time (polynomial time even) and is in $NP$, but it's (likely) not $NP$-complete. Moreover, it is possible that there are problems that require exponential time to be solved and are in $NP$, but that are not $NP$-complete, see e.g. $NP$-intermediate.


It is not a rigorous answer, but if we are to posit in the way of Udi Manber using induction, we are tacitly positing a recursively enumerable algorithm that can terminate. Udi Manber's algorithmic approach though does not necessarily posit a primitive recursive algorithm. If the problem in our class is not recursively enumerable, then we cannot use Udi Manber's approach, and it may as well be uncomputable. A primitive recursive algorithm is likely to be more efficient than a recursively enumerable one.


Multi-prompt delimited continuations in terms of single-prompt delimited continuations

So, it turns out, the paper describing the construction I mentioned in the comments answers in the affirmative:

  Our technique of removing a dynamic prompt is rather general and thus can be used for the design of many other delimited control operators, which permit capturing the continuation up to an arbitrary (not necessarily the closest one) enclosing delimiter.  It becomes entirely up to the user which delimiters to skip and how the captured frames are to be composed or used separately.

If you look at their method, it seems like the idea would be to tag the H and HV values with tokens that specify the different prompts involved, and have the h and h' functions compare those tokens to decide what to do. This isn't terribly surprising, because the multi-prompt implementation I'm familiar with uses (representations of) stacks with frames tagged with the prompt, and their technique uses 'static' shift/reset (and macros) to hide explicit manipulation of the stack implementation of e.g. control/prompt, more or less.


I was first taken by your metaphore, but I do not think it works.
Actually he is saying that he is himself a decision procedure, though
he cannot describe his own internal program. Hence Justice Stewart
decisions are recursive, not recursively enumerable, at least where
pornography is concerned. I would indeed expect anyone capable of such
an arrogant statement to be computationally limited.

Now for other examples taken from the real world, the first that comes
to mind is actually co-RE, though that amounts to the complement being
RE.  It is the buggy program problem. If a program has a bug, it will
show some day, provided we use it long enough. But we cannot be sure
thre are no bugs, even when none has been found. Well, that was before
we could prove program correct (not that we are really there yet).

A close problem is falsifiability of scientific theories, as defined by
Karl Popper. The idea is that science is primarily co-RE:

A theory in the empirical sciences can never be proven, but it nust
be falsifiable, meaning that it can and should be scrutinised by
decisive experiments that could prove it wrong.

In other words, all we can know for certain, is that some empirical
science theories are false, because some consequences have been
experimentally proved false.
Whatever remain might be good theories, unless later proved false.

False theories form a RE set. Good theories are the co-RE complement.

But I am not sure this last example will make things clearer for your
students.

And the relations between scientific theories, or their correctness
status are a bit more subtle than that.

P.S. I think mortal people form an RE set.


Where are the address, control and data buses on a computer

The answer is "all of the above".

There are busses all over the system, some are going to be physically internal to a CPU, others might be be between CPU and memory, but not I/O, still others might connect I/O devices (EX: The PCI bus) and others may connect all 3.

Consider what a "bus" is.  I would define a bus as a group of related signals that are intended for a specific purpose.  Busses usually have additional qualifiers to help identify what their purpose is and define what they actually connect with.  IE: A Memory Data Bus would probably connect the data lines of a cache controller on a CPU with main memory.  A Memory Address bus would probably connect the address lines.  A Memory Control bus would carry control signals that signal the state of the other buses and/or provide clocks.  Often these 3 functions are grouped together to define a single "bus".  Sometimes the physical connections on busses are multipurpose where they are used alternately to carry memory or address information.

There are usually bus adapters that allow information to be passed between different busses in a system.  These will sometimes be named something like "bridge", "bus adapter", "gateway", "Hose interface", etc.   These bus adapters allow a system to pass data between busses with different data widths, clock speeds and signaling characteristics.  For example a PCI bridge would connect a PCI bus to a system bus that operates at a higher frequency and may transfer data in larger (or smaller) chunks.


Is it possible to construct 3-dimensional microchips?

Yes, it's possible to build 3-dimensional integrated circuits: we already know how to do that, and many chips already use 3D integration.

Building chips whose structure is similar to the brain structure is a different question.  Circuits on current chips (whether 2-dimensional or 3-dimensional) are very different from the structure of the brain.


What is the benefit of using one to one thread mapping model instead of Many to Many or two level?

I am gonna be very careful here and say it is due to complexity of managing threads at two different levels did not produce the expected results, the lack of a direct mapping caused issues meeting POSIX threads requirements. Notice that in the book it says that Solaris 8 and before have implemented many to many model. Here you can see the document they "explain" the retirement of this model.

  The Solaris 9 Operating Environment does not include an alternate threads implementation. The
  old MxN implementation has been gracefully retired and replaced with an enhanced version of
  the 1:1 implementation. The /usr/lib/lwp directories which held the alternate library in Solaris 8
  software have been preserved, but these now simply link back to /usr/lib.
  Extensive testing indicates that this decision should cause no issues for existing applications.
  Most applications are expected to benefit from this move and binary compatibility is preserved.

Again, sadly, there was nothing concrete stated as reason, but my guess will be complexity.


In the C language you cant insert space between '-' and '=', so you are better to implement '-=' as the single lexeme.


Doubt over the index value used in dynamic programming

The code there is not optimal in terms of space as you can reduce the space complexity to n.

In any case I would recommend thinking as follows when you are trying to convert a brute force recursive solution to dynamic programming.

First look at the recurrence.

f(i,j) = 1                                   if i==j
f(i,j) = f(i+1,j) + f(i,j-1) +1              if str[i] == str[j)
f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1)    otherwise

Here each i,j pair is a 'state' and each state depends on other states. Dynamic programming stores previously computed states into an array/hashmap/whatever hence allowing us to reuse previously computed states to make the program run faster.

If we are using a 2d array to store the states then state (i,j) is stored in dp[i][j]. State  (i-1,j) is stored in dp[i-1][j] and so on.

In any case look at the recurrence relation of the brute force solution. You can see that:

For any given state, i depends on the values of i+1 and i
For any given state, j depends on the values of j and j-1

Thus we can make the following inference:

Since i depends on i, i+1 values, i+1 must be filled before i. Hence i loops from n to 0.
Since j depends on j, j-1 values, j-1 must be filled before j. Hence j loops from 0 to n.

So we know the direction of our loops and we can just fill in values accordingly like so:

private int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}

And this is basically what is in the link that you posted. f(i, string.length-1)'s state contains the result which is why we return  dp[0][s.length()-1].

Time complexity: n^2; Space complexity: n^2

However this is not optimal. Optimal solution below:

Like I mentioned earlier we can make an optimization in terms of space to give us a better solution. This is not done in the link that you posted.

Notice that i depends on values of only i and i+1. This means states containing i+2, i+3, ... i+n is useless.
Similarly j depends on values of only j and j-1. This means states containing j-2, j-3, ... j-j is useless.

If something like this happens for any parameter of the recurrence, it means that we can reduce the dimension of the array by 1. We can either reduce the dimension i or we can reduce the dimension j (since either i or j can be reduced). Just make sure that the dimension you are reducing is the outer loop.

Here i represents the rows and j represents the columns of the array. Below I will show you how to reduce the i dimension. You can do the same with j but just make sure that if you reduce j, j is in the outer loop.

We are reducing dimension i, we need only 2 rows: row i and row 1+1. We dont need the other rows in the matrix. So let row 1 be row1, let row i+1 be row2.

private int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

The time/space analysis is:

Time complexity: n^2; Space complexity: n

So the general pattern to convert recursion to bottom up dp is:

Look at the recurrence relation
Figure out the order of the loops
Check to see if any variable x depends on x+-c where c is a constant. If that is the case, we can reduce the space complexity
Compute and store state i,j using previously computed states (unless it is the base case)
Return the result.

Hope this helps.


How can a CPU access more memory locations than 2^wordsize?

The 8080, as @TEMLIB pointed out, had 16 bit registers (the program counter, the stack pointer and BC, DE, and HL), and could access 216 bytes of memory.  The 8080 had an 8-bit bus, and for instructions that required 2 bytes of data or address the bus would be used for 2 cycles.

The 8086 is more interesting.  The 8086 had 16 bit registers, but could access 220 bytes of memory.  It did this by using segment registers.  There were four special 16-bit registers, CS, DS, ES and SS and every address was calculated by taking 16 times the appropriate segment register plus the 16-bit offset coming from a "normal" register.  So for example, instruction addresses were all calculated as an offset from CS * 16, and stack references were all calculated as an offset from SS * 16.

Modern 32-bit processors can also sometimes access more than 232 bytes of DRAM through the virtual memory system.  Each running program can access only 232 bytes of virtual memory but the page table entries map to (for example) 36 bit physical addresses, allowing the operating system to run multiple programs simultaneously that collectively can access up to 236 bytes of physical DRAM.


Powerset generation using recursion and time complexity

You should have converted you Java code into pseudo code.

In fact, if your code runs exactly as you describe, namely given a set $S$ as a string it generate all subsets of the symbols of the input string, then the running time is trivial. You just need to count the number of different subsets generated by your algorithm/code. Input size is the length of the input string, i.e., number of characters. So, if the number of characters is $n$ then there are total $2^n$ different subsets. So, the time complexity is $O(2^n)$.


The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

If you tried to get the longest stick out of 10, and they were shown to you in random order, how would you proceed?
Here’s a simple strategy, based on the simple idea that it’s daft to pick a stick that isn’t the longest so far: Don’t take any of the first four sticks, then pick the first stick that is longer than the longest so far. How will this work out?
If the first four contain the longest stick, you lose. If the first four contain the second longest stick, you win because you will pick the longest. If the first four contain the third longest stick, then you will pick the longest or second longest, 50% chance to win, and so on.
Chances are 65.61% that the first four don’t contain the longest, and 40.96% that they contain neither of the two longest; that alone gives you a 24.65% chance to win because you must pick the longest stick. You can calculate your chances to win quite easily: let p(k) be probability (“None of the p largest”) - probability (“None of the p+1 largest”), then your chance to win is p(1) + p(2)/2 + p(3)/3 ...
You would also check if skipping the first three or five or any other number might be better.
If you ignore about the first n/e sticks, this will give you a winning chance around 1/e even when n is very large.


NP Problem definition – verifiable on DFA vs. solvable on NFA

First, let me correct you: instead of a DFA there should be a deterministic Turing machine running in polynomial time, and instead of an NFA there should be a non-deterministic Turing machine running in polynomial time.

As you mention, both definitions are equivalent, and for this reason there is no single "go to" definition – you can use whatever definition is more appropriate in any single case.

Any formal development of complexity theory would necessitate picking one of these and then showing that the other is equivalent, but this is best left to the developers of these formal frameworks.

There are in fact many variants of Turing machines, so there are more than two definitions of NP. Even more equivalent definitions are provided by other models of computation such as RAM machines. Since all these definitions result in the same complexity class, they are all equally well definitions of NP.


Is this a known problem in graph theory?

If $G=(V,E)$, with $V=\{v_1,v_2,...,v_n\}$ and weights $\{c_{i,j}, i=1,2,...,n, j=1,2,...,p\}$ is the given graph, then we can construct the strong product (I finally found the name of the operation) $G\boxtimes K_p$ of $G$ and $K_p$, where $K_p$ is the complete graph with $p$ vertices. This is the graph with vertices $\{v_{i,j},i=1,2,...,n, j=1,2,...,p\}$ and edges $\{v_{a,b},v_{c,d}\}$ where either:

$a=c$,
$b=d$ or
$\{v_a,v_c\}\in E$. (The actual condition of the strong product reduces to this since in $K_p$ all vertices are adjacent).

We give the vertex $v_{i,j}$ the weight $c_{i,j}$, for $i=1,2,...,n$ and $j=1,2,...,p$.
The problem on $G$ is equivalent to the problem minimum (maximum) weighted independent set in the weighted $G\boxtimes K_p$. If a vertex $v_{i,j}$ of the new graph is chosen this corresponds to choosing vertex $v_i$  of the original graph and using the $j$-th weight $c_{i,j}$ corresponding to it.
The set of edges of $G\boxtimes K_p$ are exactly those that prevent the corresponding choices in $G$ to use adjacent vertices or reusing weights with the same index:

Condition $1$ defines edges in the strong product that prevent the equivalent of using two weights from the same original vertex.
Condition $2$ prevents using the weights with the same index from different vertices of the original graph.
Condition $3$ prevents that two vertices that were neighbors in the original graph are selected.

Example:
If $G$ is the graph

and $p=2$, then $G\boxtimes K_2$ would be the graph

Images created with this tool.


Arden's Rule, DFA & NFA to regular expressions

You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $[-]: Q\to RE$.

Let $(s, l, t)$ denote a transition from $s$ with label $l$ to target state $t$.

Also, let $\oplus_{i\leq n}r_i = r_1 + \ldots + r_n$.

1st case: By incoming edges.

Add a final state, $F$, and an $\varepsilon$-transition from each previous final state to $F$.
For every state $X$ with $n$ incoming edges $(s_i, l_i, X)_{i\leq n}$, make an equation $[X] = \oplus_{i\leq n}([s_i]l_i)$.
Use rule: $X = s + Xr \Longrightarrow X = sr^*$ on the equations
The final regular expression is $[F]$.

2nd case: By outgoing edges.

Add a new initial state, $S$, and an $\varepsilon$-transition from $S$ to the previous initial state.
For every state $X$ with $n$ outgoing edges $(X, l_i, t_i)_{i\leq n}$, make an equation $[X] = \oplus_{i\leq n}(l_i[t_i])$.
Use rule: $X = s + rX \Longrightarrow X = r^*s$ on the equations
The final regular expression is $[S]$.

Both methods work for NFAs as well. None of the above transformations depend on determinism.

Regarding your final thoughts, when you count the outgoing edges, if you add the $\varepsilon$-transition in the final states, then $[F] = \emptyset$, because $F$ (the new final state) has no outgoing edges, and this doesn't contribute to the equations. What you want to add is a new initial state, so that you can compute $[S]$. For your DFA example, $[S] = \varepsilon[A]$. Similarly, adding a new initial state is useless when transforming by incoming edges. In this case, $[S] = \emptyset$ and what you want is $[F]$, which for your example, would be $[F] = [A]\varepsilon + [D]\varepsilon$.