Find the length of the longest subarray having sum greater than k

We can improve your code and speed it up from $O(n^2)$ to $O(n \cdot \log n)$ with one change.
First precompute all prefix sum. Let $P_t$ = the sum of the first $t$ elements. Notice that $P_t$ is defined from $0 \leq t \leq n$ and in particular $P_0=0$. This step is $O(n)$ so it is ok.
Now you need to find two index $0 \leq j < i \leq n$ such that $P_i - P_j > k$ and $i - j$ is maximum.
The next step in your solution is fixing the right most index ($i$), so we need to figure out a way to find fast the leftmost $j$ such that $P_i - P_j > k$. For a fixed $i$ the condition can be converted to:
What is the smallest $j$ such that $P_i - k > P_j$?
We might be tempted to do binary search here, but it is not correct since $P_j$ is not sorted... but wait, we can just get rid of "not sorted elements" easily. Let's say that if there exist two index $a < b$ such that $P_a \leq P_b$, then we are not interested at all in the element at position $b$, since it will never be the leftmost index of an optimal interval, given that we can extend that interval up to position $a$.
With this in mind we can define an index $j$ important, if there is no index $k < j$ such that $P_k \leq P_j$, i.e. $j$ is the smallest element in the prefix ending at $j$. One nice property of important elements, is that they form a strictly decreasing subsequence of array $P$, and for any fixed $i$, the optimal election of $j$ is an important index.
Since the important index array forms a strictly decreasing subsequence we can perform binary search without any issue. To build such array, we inserts elements one by one, if the new element is less than the minimum element in the array then it is important and should be inserted, otherwise, we don't add this element. The minimum element of the important index array will always be the last one.
Pseudocode:
def largest_subarray(array, k):
    n := length of array
    P := prefix sum of array
    # Remember that P[0] = 0, P[1] = array[1], ...

    # List of important index in increasing order.
    # Notice the values such indexes are pointing too are decreasing.
    # That is P[J[0]], P[J[1]], ... is strictly decreasing
    # Initially there is only index 0
    J := [0]

    # Answer of this function.
    longest_length := -1

    for i in 1..n:
        # Check if there is at least one solution ending
        # at index i. i.e. If P[i] - min(P[j < i]) > k

        # Index of the smallest element
        last_j := J[-1]
        if P[i] - P[J[-1]] > k:
            # There is at least one solution, so we can run binary search
            # to find the optimal solution. i.e the smallest index j
            # such that P[i] - P[j] > k
            # Since j belongs to J, we are finding the smallest index
            # p such that P[i] - P[J[p]] > k
            p := bin_search()
            longest_length := max(longest_length, i - J[p])

        # Check if i is important
        if P[i] < P[last_j]:
            J.push(i)

    return longest_length


What kind of LTL formula can be represented by DBAs

You can define syntactic fragments of LTL that ensure that all properties expressible in these fragments are representable as DBAs. An example is given in the paper "A LTL Fragment for GR(1)-Synthesis". Also, the common fragment of ACTL and LTL only contains properties that are representable as DBAs.

But note that such a fragment will never be complete in the "if a formula is not in the fragment, then it is not representable as a DBA" sense. The reason is that if we have LTL formulas that are not representable as DBAs, then we may be able to combine them to a formula that is representable as DBA. For example, the properties "FG p | GF q" and "FG q | GF p" are both not expressible by DBA, but both their conjunction and their disjunction are.

Note that there are also DBAs that are not representable in LTL. So a fragment of LTL cannot be equiexpressive to DBAs.


Is there an online algorithm for radix conversion?

This answer is not complete, but it is the start of a complete answer, and nothing else has been offered.  I hope to finish it another time.

I have found that an online right-to-left algorithm exists in a more general case than I mentioned in my original question.

I suspect that no such algorithm exists in general, for reasons I outlined in my comment.  What would the online algorithm produce first?

Units digit first

Suppose the algorithm wants to produce the units digit of $Q$ without reading all of $P$.  Represent $n$ in base-$p$ as $n = \sum_i d_ip^i$ where each base-$p$ digit $d_i$ is between $0$ and $p-1$ inclusive. The units digit of $Q$ is equal to $n\bmod q$ which is $$\Bigl(\sum_i d_ip^i\Bigr)\bmod q.\tag{$\star$}$$  The result depends on every one of the $d_i$ unless the corresponding term $d_ip^i$ has the same value $\bmod q$ for each possible value of $d_i$.  In particular we must have $$0\cdot p^i \equiv 1\cdot p^i\pmod q$$ so $p^i$ must be a multiple of $q$ in order for us to ignore the $i$th term of the sum.  Say $p^{k_0}$ is a multiple of $q$ for some $k_0$.  Then in computing the units digit of $Q$ we can disregard all the terms of the sum with $i\ge k_0$, and we need only examine the first $k_0$ digits of $P$.

To compute the next digit of $Q$ we can disregard all the terms of the sum with $i\ge k_1$ where $k_1$ is the smallest number for which $p^{k_1}$ is a multiple of $q^2$, and so on.

For example, suppose $p=6$ and $q=8$ and $n=3021213_6$.  $6^3$ is a multiple of $8$ so we can generate the units digit of  $Q$ just by examining the last three digits of $P$.  $2\cdot6^2 + 1\cdot 6 +3 \equiv 1\pmod 8$ so the units digit of $Q$ is 1.   Reading the next three digits of $P$ will allow us to compute another digit of $Q$, and so on.

This situation includes the case of $p^i=q^j$ that I discussed in the original question, but it is more general.

Note that although the $k_i = O(i)$ it may not increase smoothly.  We actually have $k_i = \lfloor c(i+1)\rfloor$ for some rational constant $c$ that depends on $P$ and $Q$.  For example, $24$ is a multiple of $4$, and so $24^2$ must be a multiple of $4^2$, but it is also a multiple of $4^3$.  Next $24^3$ is a multiple of $4^4$ but not of $4^5$.  So when converting from base $24$ to base $4$, reading the first digit of $P$ gets you one digit of $Q$, but reading the next digit of $P$ gets you not one but two more digits of $Q$. Reading the third digit of $P$ gets you only one more digit of $Q$.  Here $c = \frac32$.

(To come: most significant digit first; intermediate digits first.)


Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements

There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to determine whether there is a choice of indices for which the sum equals $\binom{k}{2}$.


Algorithm to merge two incomplete lists of symbols (strings) into a complete one

The problem is called shortest common supersequence. For an arbitrary number of strings it is NP-hard, but for two strings it can be solved efficiently:

First find the longest common subsequence of the two strings with dynamic programming, then insert the remaining characters.


Difficulty understanding the faster multiplication hardware

You want to multiply x by y, where both are 32 bit numbers.

The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 bits. The second number is x if bit #30 of y is 1, and 0 if bit #30 of y is 0. This number is shifted by 30 bits. And so on. The last number is x if bit #0 of y is 1, and 0 if bit #0 of y is 0. This number is shifted by 0 bits.

So you have 32 numbers to add. You use 16 adders in parallel to add the first and second, the third and fourth, the fifth and sixth number and so on. You get sixteen 34 bit results. Next you use 8 adders in parallel to each add two of these sums. Then 4 adders in parallel, then 2 adders in parallel, then one adder to get the final result.

Obviously you figure out how big each result can be, and where you would be adding zeroes (which obviously don't need adding). In total you need 31 adders, five levels deep, so the delay for the multiplier is about five times that of a 32 bit adder.

(BTW. There are methods that can get the result faster and I think with less hardware).


Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?

Clearly, $\log(\frac{n}{\log(n)}) \le \log(n)$.
Substitute this into the equation to get that $T=O(n)+\frac{n}{\log(n)}\left(\log\left(\frac{n}{\log(n)}\right)\right)\le O(n)+\frac{n}{\log(n)} \log(n)=O(n)+n=O(n)$
So $T=O(n)$, and indeed it is not bigger than linear time.


Computer science problems related to music?

It is easy to think of many different problems:

Converting sound to scores.
Converting scores to sound.
Automatic music composition.
Music analysis, for example key recognition.
Music classification, such as style recognition and artist recognition.

All of these things are actually being done.


Why is the complexity of factorial a function of n?

Complexity can be expressed in terms of any reasonable measure. For example, when discussing graph algorithms, we usually state the complexity in terms of the number of vertices and/or edges, rather than the number of bits required to write the graph as input, e.g., as an adjacency matrix.

So I guess you've just come across resources that discuss the complexity in terms of the number being "factorialed" rather than the number of bits required to write down that number – I'm sure you'll agree that this is a reasonable measure, even if it's not your favourite one. Further, it's easy to convert between the two: a $k$-bit number can represent values up to $2^k$, so just take the expression you've been given and substitute $2^n$ for $n$.


Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack.

So let us consider the $n \times n$ chessboard now.
Warnsdorff's rule (nor any other method) won't find a solution for $n < 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, an efficient algorithm based on Warnsdorff's rule is described in [1, Proposition 2.2]. Other independently discovered algorithms that work in linear time are known as well (see e.g., [2]).

[1] Conrad, Axel, Tanja Hindrichs, Hussein Morsy, and Ingo Wegener. "Solution of the knight's Hamiltonian path problem on chessboards." Discrete Applied Mathematics 50, no. 2 (1994): 125-134.

[2] Parberry, Ian. "An efficient algorithm for the Knight's tour problem." Discrete Applied Mathematics 73, no. 3 (1997): 251-260.


Other reason for compilers to produce assembly rather than proper machine code are:

The symbolic addresses used by assemblers instead of hard-coding machine addresses
 make code relocation much easier.
Linking code may involve safety checks such as type-checking, and that's easier
 to do with symbolic names.
Small changes in machine code are easier to accomodate by changing the assembler
 rather than the code generator.


How come the branching factor of chess is 35?

Since the moves differ per turn it was calculated as the average. Yes you are right, there are exactly 20 moves in the first turn, but after advancing with knights, bishops, rooks and queen into the center of the board the number of legal moves is increasing and since it is average of the minimax tree also the situation after encrouning with several queens on the both sides is calculated (not very wise game, but still perfectly valid to have more than 100 available moves in one turn.

Please check for some more legal chess positions.


How to implement conditional probability distribution on set-valued Random Variables

Your understanding of the basic situation (without sets) has some caveats.  It seems that you are defining
$$f(x,y) =  \Pr[X=x \land Y=y] \times |\mathcal{X}| \times |\mathcal{Y}|.$$
You seems to be assuming that $X,Y$ are independently and uniformly distributed over the sample space $\mathcal{X} \times \mathcal{Y}$.  Note that this is a big assumption -- it typically won't hold, and if it doesn't hold, your formula is not correct.
You don't need a fancy accumulator function. There is a simpler expression for $f$, namely, $f(x,y) = 1$ if $x \in \mathcal{X},y \in \mathcal{Y}$ (and $f(x,y) = 0$ otherwise, if you allow that to happen).  Again, this is only valid if $X,Y$ are uniformly distributed on $\mathcal{X} \times \mathcal{Y}$.
When $X,Y$ are sets, the exact same formula holds... under the same assumptions.  No changes needed at all.
Your proposed formulas (1), (2) are not correct.
In practice, usually $X,Y$ are typically not independently and uniformly distributed.  Therefore, these formulas are usually not useful in practice.  Instead, you need to work directly with the probabilities; counts and $f$ probably won't be useful in that case.


The symbol $\space ≃ \space$ means "asymptotically equal to".

So when you read $ n ≃ i$, you can read it as $n$ asymptotically approaches $i$.

This means that the more $n$ increase in size, the more $i$ increase in size but $n$ never become equal to $i$.

  I mean suppose $n=1000$ and so $i=2,4,16,32,256,65536$ is in every steps.

This contains an error: when the program start $i=2$. At the first cicle, $i=2^2 = 4 $. $\space$ At the second cicle, $i=4^2=16$. $\space$ At the third cicle, $i = 16^2= 256$. $\space$ At the fourth cycle, $i=256^2 = 65536$. $\space$ At the fifth cycle the program stops since $i>n$.


The time complexity of finding the diameter of a graph

I assume you mean the diameter of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.


What is the use of First() and Follow() in compiler design?

$FIRST$ and $FOLLOW$ sets are used by the algorithm which produces an $LL(k)$ parser from a grammar. They're also used in a number of other algorithms which analyze grammars, but most students will run into them when learning about top-down parsers.

Parsing is a tiny part of the work of producing a compiler, and in practice you can generate a parser using code-generation tools which avoid you having to know much about implementation details. So I'd say that th4e direct answer to your question is that $FIRST$ and $FOLLOW$ sets have very little to do with compiler design, but they are useful in the understanding of how particular parsing algorithms work.


What was the first programming language with loop break?

I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote:

  "CPL did have a break command to cause an exit from a repetitive command such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967."

[...]

  "The introduction of break in CPL was almost certainly influenced by Dijkstra's paper..."

He also pointed me to the following document (see page 5):

http://www.cl.cam.ac.uk/~mr10/cpl2bcpl.pdf


Would using mouse position in the below scenario generate true random numbers?

Usually, mouse click position is highly correlated. Just as an example, take a look to a typical mouse interaction with a browser:

So, the use of raw mouse click positions without pre-whitening is discouraged.


Unconditional arithmetic circuit lower bounds for permanent/determinant

Kalorkoti gave an $\Omega(n^3)$ lower bound on arithmetic formulas for the determinant and permanent. As far as I know, nothing is known for unrestricted circuits.


What does the 2 in a 2-approximation algorithm mean?

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition is not available, assume this).


Answer 1

You can try to directly fit the function $\Pr[y | x]$. This is called a discriminative classification. This is typically solved via some regression mechanism such as ordinary least squares, or lasso, or ridge depending on certain assumptions of the model.

Answer 2

The reason we want to factor $\Pr[x, y] = \Pr[x | y] \Pr[y]$ is because we are interested in the class conditional density $\Pr[x | y]$. That is, what is the probability of observing data $x$ given the label $y$?

There are various pros and cons to both discriminative and generative classification. For example, generative models tend to be easier to fit [naive Bayes is maximized simply by counting, whereas discriminative requires solving some convex optimization problem]. However, discriminative models typically faire better under independence assumptions when fitting data.


A Turing machine diagram is a form of communication. Its goal is to describe a Turing machine — usually defined as a tuple with a specific format — in a form which is easier to grasp. As such, you can use whatever shortcut you want, as long as everybody understands what you mean. This might entail your explaining some non-standard notation which you invented as shorthand.

Your professor might have different ideas about this, but the answer I gave is valid for the working mathematician.


Does a regular expression model the empty language if it contains symbols not in the alphabet?

Regular expressions only use characters from the alphabet so, if you've fixed your alphabet to be $\{a,b\}$, then $(a^∗b+dc)^∗(b^∗d+ad)^∗$ isn't a regular expression. It doesn't describe any language, in just the same way that "seventy red" doesn't describe any number. In particular, it doesn't describe the empty language, in the same way that "seventy red" isn't equal to zero.

Now, if your alphabet includes all the symbols $a$, $b$, $c$ and $d$, you might want to ask what are the strings in $L((a^∗b+dc)^∗(b^∗d+ad)^∗)$ that contain only $a$'s and $b$'s. That is, what is $L((a^∗b+dc)^∗(b^∗d+ad)^∗)\cap \{a,b\}^*$? And the answer to that is that it's all strings matching $(a^*b)^*$, as you derive in the question.

Appendix. One could attempt to sidestep these issues by redefining regular expressions in a way that gives them well-defined semantics if they include symbols not in the alphabet. However, the standard definition does not do this.

Indeed, trying to do so would seem to open up a huge can of worms. For example, suppose your alphabet is $\{a,b\}$. We could agree that, since $c$ is not a symbol in the alphabet, the regular-expression-like-object $abc$ matches nothing. OK, but $+$ is also a symbol that's not in the alphabet. Maybe you're happy with $ab+$ matching nothing because it's syntactically invalid – note, $ab+$, not $ab^+$! But, now, what does $a+b$ match? Does it mean "$a$ or $b$" or "$a$ followed by some symbol that's not in the alphabet followed by $b$, which is impossible, so it matches nothing"?


How many layers should a neural network have?

One very good resource is the Neural Network FAQ. The question depends a lot on your problem. If the problem is linear in nature, there is no reason to have any hidden layers. If the problem is non-linear, often a single hidden layer with around 10 hidden neurons will do the trick.

There is a very similar question (with a very similar answer) at CrossValidated: How to choose the number of hidden layers and nodes in a feedforward neural network?)


you can go to Dynamic programming. To achieve benefits do this you need overlapping recursion.

Easiest way yo program it, using a Map library as Memoization. Store any value calculated. Check any value from the map before calculation. This will eliminate the recalculations.

The simple case is always the Fibonacci Sequence, in which given $n$ find the $F(n) = F(n-1) + F(n-2)$.

You could see the overlappings easily. Make an array to store $F_i$ once found to prevent refound, Top-Down.

Buttom up; Start from the lowest of the recursion to reach the target.

For your case you need a table of size $10^9 \times 1000$ to fill. If the size is big, you may reuse some rows.


The Go-Back-N protocol is often presented for didactic purposes as a first, maybe crude attempt at tackling loss of packets or of order in connection-oriented communications, without obeying the constrains of Stop-and-Wait protocols, also introduced for didactic purposes.  It is no wonder it appears inefficient -- it probably was never meant to be so.  Selective Repeat can be considered as a performance improvement in terms of retransmissions over Go-Back-N, and in practice TCP itself relies on a hybrid solution of the two.


Of monotone formulas and same ones satisfying certain properties

Spira's result uses the technique of formula balancing. For simplicity, I describe the non-monotone case, the monotone case being similar.

Let $\phi$ be a formula of size $n$. We can think of $\phi$ as a binary tree. In general, $\phi$ need not be balanced. It is not hard to show that $\phi$ always has a vertex $\psi$ corresponding to a subformula of size between $n/3$ and $2n/3$ (proof: descend from the root until you reach a subformula of size smaller than $2n/3$). Replace $\psi$ with a new formal variable $x$. The original formula is equivalent to the formula
$$
(\psi \land \phi|_{x=1}) \lor (\lnot \psi \land \phi|_{x=0}).
$$
(If $\phi$ is monotone, we don't need $\lnot \psi$.) What have we accomplished? At the cost of slightly increasing the size of the formula, we managed to get the two top levels of the formula balanced: the subformulas at depth 2 all have size between $n/3$ and $2n/3$.

We continue this process recursively with all the subformulas at depth 2. The process stops after $O(\log n)$ steps, since the subformulas at depth 2 decrease at a constant rate. Hence the final formula has depth $O(\log n)$, and so size $n^{O(1)}$. At the cost of polynomially increasing the size, we have ensured that it is balanced.


Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

There is a simple solution: use exactly the strings with sums of digits being divisible by $10$. There are $10^9$ such strings and it is easy to enumerate them, find $i$-th of them in the lexicographic order, generate random such string, et cetera.
Indeed, if two strings differ in exactly one position, then their sums of digits are also different modulo $10$. For example, the sums of digits for strings $0123456789$, $1123456789$, $\ldots$, $9123456789$ are $45$, $46$, $\ldots$, $54$ respectively.
Moreover, this solution is largest possible. Indeed, there are $10^9$ such strings: for every way to choose first $9$ digits, there is an exactly one way to choose the last digit to make the sum divisible by $10$. Hence, there are $10^9$ strings in our set.
On the other hand, any set of strings with minimal Hamming distance $2$ has at most $10^9$ elements. Indeed, consider $10$ strings with a given prefix of length $9$. They all are within Hamming distance $1$ of each other (because they differ only in the last position). Hence, at most one of them can belong to any "good" set. Therefore, any "good" set contains at most $10^9$ elements.


How to find the loop invariant in hoare triples

First understand the meaning of the loop invariant. It means a condition which is true in every iteration of the program/algorithm at the begining as well as at the termination of the loop. Your program is something like this.

$$ x > 1 \text{ and } y >1 $$

$$\text{ While } x >0  $$

$$\hspace{4cm}\text{ Do } x:= x - 1, y:=y+2$$

$$\text{ End }$$

$$x + y > 5$$

$2x+y >5$ is an invariant as you described. It is visible from the program that both $x$ and $y$ will be greater than $1$ during the first iterataion of the loop. So in the first iteration of while loop $2x+y > 5$(you can prove it). Notice in each iteration of the while loop the value of the $x$ gets decrease by value $1$ and value of y is getting increase by two so inequality $2x+ y  >5$ will be satisfied. You can prove it. Now come to the termination condition, at this point $x$ will be a negative number and my claim is value of $y$ is going to be at least $5$. Thus the invariant $2x+y > 5$ si true throught the iteration of the while loop.

Example :

Let $x=2$ and $y=2$, then $2 \times 2+2 = 6 > 5$ is satisfied. Now in the second iteration  $x = 1, y=4$ so $1 \times 2+4 > 5$ satisfied. Now $x = 0, y = 6$, loop terminated, $2 \times 0+6 > 5$.


Difference between cordic algorithm and table based methods for elementary functions computation

CORDIC uses small table to work, it calculates one bit at the time and being shift and add algorithm it is preferable when there are no multipliers available. Whenever multipliers are present, table based methods or power series are faster. Also one point worth notting - the scalling factor is also needed which sometimes is argument to use BKM, but this one is slower than CORDIC.

CORDIC is still used in x87 FPU, but nowadays Chebyshev polynomials are preferred way to compute special functions (or transcendental, but not elementary - this is rather bad name) (also do not consider Taylor here, it is very slow and works for small angles).

Drawbacks in both methods are increase in number of iterations and tables provided. Good to know how they work and grasp a piece of history, but not practical in software and not preferrable in hardware.


Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$

Not exactly, as your $1B$ and $0B$ productions might cause problems. You will accept 1101 for example. I believe just simplyfing it a bit, like this:

$A → 1B1\ |\ 1\ |\ \epsilon$

$B → 0B0\ |\ 1B1\ |\ 1\ |\ 0\ |\ \epsilon$

is enough (if we say that an empty string is a palindrome).


This is kind of a broad question, and there are a lot of well-written references. This answer is just a basic starting point.

Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we know that $A$ is unsolvable (according to some fitting notion of unsolvability), then $B$ is also unsolvable.

In undergrad computability course, we usually talk about mapping reductions. A mapping reduction from $A$ to $B$ is a computable function $f:\Sigma^*\to \Sigma^*$, such that for all $x\in \Sigma^*$ it holds that $x\in A$ iff $f(x)\in B$.

The intuition behind this definition is that, assuming we have an algorithm that solves $B$, then we can solve $A$. Indeed, given an input for $A$, we use the reduction $f$ to transform it to an input for $B$, and solve $B$ using our algorithm. The "iff" property of the reduction ensures that the answer we get on $B$ induces an answer for $A$.

As a concrete example, let's consider the halting problem: given a TM $M$ and input $w$, decide whether $M$ halts in its run on $w$.
We want to reduce $A_{TM}$ to the halting problem. That is, we want to show that if we could solve the halting problem, then $A_{TM}$ is also solvable. So what we need to show is a function that takes an input $M,w$ for $A_{TM}$, and transforms it into an input $M',w'$ for the halting problem, such that the $M$ accepts $w$ iff $M'$ halts on $w'$.

We do this as follows. Given input $M,w$, construct $M'$ to be the machine that behaves exactly like $M$, except that we replace the rejecting state of $M$ with a self-loop (that never halts). We then output $M',w$. Now, it is not hard to prove that $M$ accepts $w$ iff $M'$ halts on $w$, and thus we have a reduction. Also note that this reduction is computable, since computing $M'$ from $M$ is a simple matter of changing the behavior of a state.


Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

Hint, do you know the argument for the countability of the rational numbers?

Just enumerate every pair $a,b$ of natural numbers and output the $b$ if $P(a,b)$ is true.

Other way, can you construct a machine that given a $b$, answers YES if there is an $a$ such that $P(a,b)$ is true?


Subset sum-like problem over boolean vectors

Let us say that $x \leq y$ if $x_i \leq y_i$ for all $i$. Suppose that your starting vectors are $x_1,\ldots,x_n$ and your target is $y$. If $x_i \not\leq y$ then $x_i$ cannot belong to any solution, so you can throw away all these vectors. The remaining vectors OR together to a vector $x \leq y$. If $x \neq y$ then there is no solution. Otherwise, take all remaining vectors – this is clearly the maximal solution.


Linear Temporal Logic (LTL) Syntax Infinitely Often

Consider just $Fx$. It means that at some point in time, say $t_k$, from the perspective of current moment $t_0$, $x$ will be true. After this moment, $x$ may never again be true. Specificaly, at the moment $t_{k+1}$ the formula $Fx$ may not hold.

If we add $G$, we are saying that at every moment from current moment something most hold. $GFx$, that is $G(Fx)$, says that $Fx$ must hold in every moment, meaning that, in the above situation, even at $t_{k+1}$ $Fx$ holds, that is — there must be some future moment where $x$ holds.

We have that for any moment $t_i$ $Fx$ must hold. That means that for any $t_i$ $x$ must hold at some future $t_j$. Wherever we are in time, $x$ will hold eventually. And that is the same as saying that $x$ holds infinitely many times.


Does NFA to DFA conversion give the minimal DFA as result?

No, it is not in general minimal. The standard determinization procedure, the subset construction, always converts an NFA with $n$ states to a DFA with $2^n$ states and there is no reason that this should be minimal.

In practical terms, if you convert an NFA, you'll often find that there are unreachable states in the resulting DFA, which immediately shows that the result is not minimal. For a more extreme example, take any DFA with $n$ states, call it an NFA and determinize it. You now have a DFA with $2^n>n$ states that accepts the same language as it did before, so it's certainly not minimal. (This is a particularly strong example of the first case I mentioned. All states except subsets of size $1$ will be disconnected from the start state, and the states of size $1$ are a copy of the original DFA.)


Is infinitely fast computer fundamentally impossible even theoretically?

No, it doesn't mean that.

The problem with Thompson's lamp is that a particular state of an abstract machine is not well-defined. This is nothing unusual. E.g., dividing by 0 also yields an undefined value, because any value we could choose would lead to inconsistencies with other definitions that we would like to keep - at any rate, more than the isolated, unimportant definition of 1/0.

Abstract machines can be implemented in real machines, but there are limits; one if them is that you have only finite matter, space and time available. Therefore, infinitely fast machines, just as infinitely big machines, cannot be implemented. This merely means that we cannot check the question by physical experiment.

There are many other machines that are infinitely large that we also can't build, but which at least yield a well-defined prediction (for instance, the machine that never does anything would leave the state at the initial value). Those machines cannot be tested by experiment, but they can be predicted theoretically. This machine cannot even be predicted, because it has been carefully defined to fall into an undefined niche of logics.

But this has nothing to do with the question how fast an algorithm can be. There are many algorithms of which we do not know whether (given enough time) they eventually terminate. Some of these may be testable by running them and waiting long enough, but since we don't know how long "long enough" is, physical experiment can only ever give the answer "yes", but never "definitely no".

Therefore you shouldn't be too worried about the fact that a certain machine can't actually be built. Some problems are better handled via experiment, and some via theory. Those that cannot be handled either way are vexing, but almost always they are far removed from any practical problem that we really need to solve.

Example: if mathematics weren't incomplete, i.e. it it were possible to determine the truth of any propositional formula via a single algorithm, mathematicians would be glad, but everyday life would not be much affected. Even knowing P = NP would do little; it is one thing to know that a prime can be factored in polynomial time, quite another thing to be actually able to do it.


What's a side-effect free expression in Timed Automata?

Well, I typed side-effect in Google, then I chose anser number 4: Side effect (computer science)

The first sentence states:

  In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

From this definition, using elementary logic, I deduce that a "side-effect free expression" is an expression that modifies no state, and has no observable interaction with calling functions or the outside world.

In other words, its evaluation is not supposed to have any observable effect on the program. Then what the program does with the result of the evaluation is another matter and the rest of the program may have an observable behavior that depends on that result. But the effect is the same as if you had been given directly the result rather than evaluating the expression to get it.


Relation between covering radius and columns of parity check matrix

Here is the idea. Suppose that $C$ has covering radius $\rho$. Pick a vector $s \in \mathbb{F}^{n-k}$. Since $H$ is full rank, there is a vector $x$ such that $Hx = s$. There is a vector $y \in C$ with $|x-y| \leq \rho$ (here $|\cdot|$ is Hamming distance). Then $H(x-y) = s$, and so $s$ is a sum of at most $\rho$ columns of $H$. The opposite direction is very similar.


How do I use the Myhill-Nerode theorem to show that a language is not regular?

If you want to use Myhill-Nerode to show that a language is not regular, you need to prove that there are infinitely many equivalence classes.

Basically here, it suffices to prove that each $0^j$ is in a different class.

For instance $0^9$ and $0^{10}$ are not in the same class, because $0^90^7\in L$ while $0^{10}0^7\notin L$. Try to write the general proof for any $0^i$ and $0^j$ with $i\neq j$.


Why Iterative-Deepening-DFS requires O(b*d) memory?

You need $\Theta(d \lg b)$ memory in order to store where in the tree you are: a position at depth $d$ in the tree is given by $d$ integers in the range $1\ldots b$ indicating for each branch in the tree which particular child you're looking at.

You could think of it as a set of directions of how to get from the root node to the current child. For example: at the root, take the 2nd child, then take the 5th child of that node, and so on.

When you're doing DFS, you need this information: once you've considered all children of a node at depth $d$, you need to go back to the previous node at depth $d-1$ and consider its next child, but you can only get to its next child by knowing what child you're currently looking at.

It's not clear why Wikipedia says $O(bd)$.  Perhaps this is a mistake in the Wikipedia page.


Justification behind this heuristic in SMA*+

From what I can tell the function $c(n)$ was just chosen as a reasonably simple trade-off between f-cost and depth.

It appears that $e$ is added to simply have the denominator $\ln(d(n) + e)$ always be $\geq 1$ and prevent $\ln(0)$.


CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }

I believe the following CFG meets the requirements

$$
S \to aSB \mid \varepsilon\\
B \to b \mid c
$$


Question about handwritten numbers recognition with limited data set

I suggest you the following:

Adding a little bit of noise such as blurring
Transforming the images. You can rotate or stretch a bit, but make sure you don't change too much to change 6 to 9 or o to 0.

You can look at the following tutorials:

https://stackoverflow.com/questions/14177744/how-does-perspective-transformation-work-in-pil
http://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_imgproc/py_geometric_transformations/py_geometric_transformations.html
http://effbot.org/imagingbook/image.htm


How do I prove no algorithm exists for a given problem?

The term or tag you are looking for is "undecidability" or "computability". The basic version of the theory of undecidability is a part of the theory of computation, which is an ingredient of the curriculum of all students majoring in Compute Science, as far as I know.

You can search for "undecidability" or "halting problem", the most famous and the most canonical problem that cannot be solved by an algorithm, in your textbook or course material. Or right here. There are also much stuff around.


By definition, $ \mathsf{RL} $ is a subset of $ \mathsf{NL} $, and so $ \mathsf{coRL} $ is a subset of $ \mathsf{coNL} $.

Since $ \mathsf{NL} = \mathsf{coNL} $, $ \mathsf{coRL} $ is also subset of $ \mathsf{NL} $.

Moreover, $ \mathsf{NL} \subseteq \mathsf{P} $.

Please also note that although it is widely believed to be true, whether $ \mathsf{RL} \subseteq \mathsf{L} $ is still an open problem, and so is whether $ \mathsf{coRL} \subseteq \mathsf{L} $. (The obviuos relation is $ \mathsf{L} \subseteq \mathsf{RL} \cap \mathsf{coRL} $.)


How to Prove NP-Completeness of Minimum Crossing Problem?

Here is a short summary of the original paper. More modern treatments can be found in a paper of Cabello proving a hardness of approximation result. We are concerned with three different problems:

CROSSING NUMBER: Given a graph $G$ and a number $K$, can it be drawn with at most $K$ crossings?

BIPARTITE CROSSING NUMBER: Given a connected bipartite graph $G$ and a number $K$, can it be drawn in the unit square so that vertices of one part are on the top side, vertices of the other part are on the bottom side, all edges are within the square, and there are at most $K$ crossings?

OPTIMAL LINEAR ARRANGEMENT: Given a graph $G$ and a number $K$, can we arrange the vertices of $G$ in a line so that the total length of all edges is at most $K$.

The latter is known to be NP-complete. The reduction is from OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER, and then from BIPARTITE CROSSING NUMBER to CROSSING NUMBER.

There are several variants of the concept of crossing number, and the one meant here can be gleaned from the proof that crossing number is in NP: given a graph $G$ and a number $K$, to show that the crossing number is at most $K$, identify up to $K$ pairs of crossing edges, for each one introduce a new vertex, and add the appropriate edges so that the resulting graph becomes planar; planarity can be tested in polynomial (indeed, linear) time.

OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER: Given an instance $G=(V,E),K$ of OPTIMAL LINEAR ARRANGEMENT, we construct an instance of BIPARTITE CROSSING NUMBER as follows:

For each $v \in G$, we include two vertices $v_1,v_2$ on opposite bipartitions, and $|E|^2$ copies of the edge $(v_1,v_2)$.
Fix some ordering of $V$. For each $(x,y) \in E$ such that $x < y$, include the edge $(x_1,y_2)$.
Set the new $K$ to be $|E|^2(K-|E|) + |E|^2 - 1$.

Given a good arrangement $A$ of the vertices in $V$, the intended drawing of the new graph has both copies of $V$ equally spaced and ordered according to $A$, with edges $(v_1,v_2)$ being vertical (but slightly fanned so that they don't cross each other) and the "real" edges being straight. A "real" edge spanning a stretch of $\ell$ crosses $(\ell-1)|E|^2$ vertical edges, for a total of $(K-|E|)|E|^2$ crossings. There are also at most $\binom{|E|}{2} \leq < |E|^2$ crossings between "real" edges.

Conversely, any drawing of the new graph with fewer than $|E|^4$ crossings must be of the form above (due to the vertical edges), and so we can read off a good arrangement of the original graph.

BIPARTITE CROSSING NUMBER to CROSSING NUMBER: Given an instance $G=(V_1,V_2,E),K$ of BIPARTITE CROSSING NUMBER, we construct an instance of CROSSING NUMBER as follows:

We take all vertices in $V_1,V_2$ along with two special vertices $o_1,o_2$.
We include all original edges.
We connect $o_i$ to each vertex in $V_i$ using $3K+1$ edges (for $i=1,2$).
We connect $o_1$ and $o_2$ using $3K+1$ edges.
We use the same $K$.

Given a good drawing of the original graph, we draw the new graph by putting $o_1$ above $V_1$, $o_2$ below $V_2$, the edges from $o_i$ to $V_i$ are (almost) straight, and the edges connecting $o_1$ and $o_2$ go around the entire construction. This adds no new crossings.

In the other direction, we show that every good embedding of the new graph must be of this form, in a step by step fashion, completing the proof. I'm leaving this part to the reader.


This is completely implementation-dependent. As you say, if you need to copy the existing matrix, you have $n^2$ entries to copy, which takes $\Theta(n^2)$ steps; if you only need to add the new entries (for example, if you've pre-allocated a large matrix but you're adding the vertices one at a time), you only need to write $O(n)$ entries each time.

If you did have to copy the matrix every time you grow it, a more time-efficient option would be to start with a small matrix (say, $10\times 10$) and double it every time it fills up. Doing it that way means you need fewer expensive copies but the potential down-side is that you could waste a lot of space.  For example, if your graph ends up having 21 vertices, you'll have allocated a $40\times 40$ matrix, most of which is empty. You could mitigate that by not growing the array so aggressively (say, making it 25% bigger each time it grows, instead of 100%).


Efficient algorithm to generate undirected graph edges from 3D distribution of nodes based on distance

This is the intersection graph of a set of spheres.  The case of 2D disks, all of the same size, is well-studied; its intersection graph is known as a unit disk graph, and it has been studied in some depth in the literature.  I don't know if your case has been studied in the literature, but those are some search terms you could use to try to find related work.


What does normalizing with hidden bit really mean?

Generally speaking, normalized means "put in scientific notation."  That just means, the mantissa should never start with 0, and should be less than the base.  In binary that means the mantissa must be "1".  Since the mantissa of a normalized binary floating point number is always 1, we don't need to store the 1.  The first mantissa bit is hidden in the sense that it always exists, but we don't actually store the bit, because we know its value is 1.

So your normalized result ($1.1 \times 2^{-2}$) is correct, and it is correct because you've moved the first 1 to the left of the binary point.


How many sequences in a prefix code can be compressed by m bits?

There is no problem with the statement. An encoding $f$ of the set of strings of length $n$ is a map from $\{0,1\}^n$ to $\{0,1\}^*$ which is injective (one-to-one). Such a mapping compresses a string $x$ by more than $m$ if $|f(x)| < |x| - m$. In our case, all the strings have length $n$, so a string $x \in \{0,1\}^n$ is compressed by more than $m$ if $|f(x)| < n-m$. There are $\sum_{i=0}^{n-m-1} 2^i = 2^{n-m}-1 < 2^{n-m}$ such strings, and since $f$ is injective, the fraction of strings compressed by more than $m$ is less than $2^{n-m}/2^n = 2^{-m}$.


proving " if $k\log(k) = \theta (n)$ then $k = \theta (\frac{n}{\log(n)})$"

First, let me explain why your claim holds. Then we'll see how to prove it.

If $k \log k = \Theta(n)$ then $k$ has the same order of magnitude as $n$, and so we expect $\log k \approx \log n$ (or, more formally, $\log k = \Theta(\log n)$). Diving by $\log n$, we deduce $k = \Theta(n/\log n)$.

This was just intuition, so now let us see a rigorous proof. A rigorous proof rests on a rigorous definition of big $\Theta$, and this is a surprisingly delicate matter. In this case it suffices to assume that $n \geq 1$.

Upper bound

Suppose that $k \log k \leq Cn$ for $C>0$.

If $k \leq \sqrt{n}$ then
$$
\frac{k}{\frac{n}{\log n}} \leq \frac{\log n}{\sqrt{n}}.
$$
Now $\frac{\log n}{\sqrt{n}}$ is continuous and tends to zero at infinity, so it is upper-bounded by some constant $M$. Therefore in this case
$$
k \leq M \frac{n}{\log n}.
$$

If $k > \sqrt{n}$ then
$$
Cn \geq k \log k > k \log \sqrt{n} = \frac{1}{2} k \log n,
$$
and so
$$
k \leq 2C \frac{n}{\log n}.
$$

We conclude that for all $k$,
$$
k \leq \max(2C,M) \frac{n}{\log n}.
$$

Lower bound

Left to you as an exercise.


In your example the problem is in the so-called chain productions $M\to A$ and $N\to B$. Just look how these single nonterminals can finally be rewritten into terminals: $M \Rightarrow A \rightarrow a$. Remove the $M\to A$ chain production and replace it by $M\to a$.

In general, if we have any sequence of nonterminals $X_1 \Rightarrow X_2 \Rightarrow \dots X_n \Rightarrow c$ add the production $X_1\to c$. Then remove the chain productions of the grammar.

Recursion in general is not a problem. It is the essence of context-free grammars! The only requirement of Chomsky Normal Form is that productions are of the form $A \to BC$ and $A\to a$ with $A,B,C$ nonterminals (=variables) and $a$ terminal (letters).


Characterisation of graphs that are not 3-colorable

As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs.

However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem states every triangle-free planar graph is 3-colorable. Furthermore, such graphs can be 3-colored in linear time. In a random graph setting, almost all graphs with $2.522n$ edges are not 3-colorable [1].

You can find plenty of graph classes for which 3-coloring is easy on ISGCI.

[1] Achlioptas, D., & Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3-colorable. Electronic Journal of Combinatorics, 6(1), R29.


Finding an exactly weighted st-path in a digraph

This problem is NP-complete.

The "$\in$ NP"-part is trivial.

For the NP-hard part we reduce directed hamiltonian path:

  Given a directed graph $G=(V,E)$ and two vertices $v_1,v_2\in V$, is there a path from $v_1$ to $v_2$, that visits each vertex exactly once?

For the reduction we keep $G$, $v_1$, and $v_2$ and number the nodes from $1$ to $n$, so that $v_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.

It is easy to compute, that a hamiltonian path will have the correct weight.

For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.

Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0<i<n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.

The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.


Communication complexity of string matching

By simply exchanging random indices you cannot hope to do better than $\Omega(n)$ communication if you want constant error probability. If the strings differ in only a single bit, and you exchange $k$ indices, then the probability of finding the index in which they differ is $\frac{k}{n}$, so if you want this to be constant you must have $k=\Omega(n)$.

The randomized communication complexity can indeed be reduced to $O(\log n)$, but you're going to need stronger arguments. One way to do this is to encode both words with an error correcting code having a large distance, and then use your algorithm (naive sampling) on the codewords.

To elaborate on the above idea, the choice of code doesn't really matter, as the only property you need in order to make naive sampling work is large distance. One example is using Reed-Solomon, given $s\in\{0,1\}^n$, think of it as a string of length $k$ over $\mathbb{F_q}$, with $q=n$ and $k=\frac{n}{\log n}$. In that case you can think of $s=s_0,...,s_{k-1}$ as the polynomial $P_s=s_0+s_1x+...+s_k x^{k-1}$ over $\mathbb{F}_q$. If $s_1\neq s_2$ then their corresponding polynomials agree on at most $k-1$ points in $\mathbb{F}_q$, which means they will differ on at least $n-(k-1)=n\left(1-\frac{1}{\log n}\right)+1$ points in $\mathbb{F}_{q=n}$.
Thus, with high probability, $P_{s_1},P_{s_2}$ will disagree on a random point in $\mathbb{F}_q$. This protocol requires you to send three elements in $\mathbb{F}_q$ (a point and both polynomials evaluations on it), which results in $O(\log q)=O(\log n)$ communication.

This is only one option, there are many randomized protocols for equality. One example is using a simple public coins protocol, in which both parties share two random strings $r,r'\sim U_n$, and exchange the values of $\langle xr,r'\rangle, \langle yr,r'\rangle$. This succeeds with probability $\frac{1}{2}$, and you can turn it into a private coin protocol with logarithmic overhead in communication, see these notes for details. Another option is to choose a prime $p\le poly(n)$ at random, and exchange $x,y\bmod p$. If $x\neq y$ then with high probability $p$ will not divide $x-y$.


Reversible computation and no cloning theorem in quantum computing

No-cloning theorem refers to creation of independent copies of a qubit. With CNOT gates you’ll only create mirrors.

For instance, if you have $\alpha \left| 0 \right> + \beta \left| 1 \right>$ and measure it, you’ll get 0 with probability $p_a=|\alpha|^2$ and 1 with $p_b=|\beta|^2$. Now if you clone this qubit and measure both, you should get 00 with probability $p_a^2$, 01 with $p_a p_b$, 10 with $p_b p_a$ and 11 with $p_b^2$.

Mirroring with CNOT gives a different picture: 00 with $p_a$, 11 with $p_b$ and zero probability for 01 and 10.


Automata theory is a broad field and researchers keep inventing new types of automata. There is even a conference series on non-classical models of automata. So it is impossible to encompass all of automata theory. For classical models such as context-free grammars, recently formalized proofs of the most basic theorems have been carried out. These are derived from first principles (these are definitions in terms of set theory). See this example for an accessible account: https://www.react.uni-saarland.de/people/hofmann/jhofBA.pdf


Is well-founded recursion enough for practical total functional programming?

Let's restrict ourselves to the model of Turing machines (or, in general, of state machines). Consider complete states $s_1, s_2$ of the Turing machine (a complete state is a state specifying the full configuration of the Turing machine). We say that $s_1 \gets s_2$ if and only if we transition from $s_2$ directly to $s_1$.
It is easy to see that the Turing machine will terminate from any state if, and only if, $\gets$ is a well-founded relation.
A similar result holds for a strict language based on the $\lambda$-calculus. It's possible to determine whether a given term $T$ will reduce to a normal form by considering the $\beta$-reduction relation $\gets_\beta$ on all terms which $T$ can be reduced to. $T$ will reduce to a normal form under any reduction order if and only if $\gets_\beta$ is well-founded.
Thus, it's really not possible to get any more general than well-founded relations for proving termination.


What would be a decent threshold for classification problem?

There is no universal answer.  Instead, it depends on your application.  What counts as useful for your application?  That determines what should count as a useful or good-enough machine learning algorithm.  What counts as useful will vary widely from application to application; some applications require 99.99% accuracy, others might be happy with 52% accuracy.

In practice, there are also multiple ways to define accuracy.  If you expect that (in the ground truth) half of the objects should be classified 'good' and half as 'bad', then the obvious accuracy measure suffices, i.e., counting what fraction of instances your classifier outputs the correct answer.  However, if 'good' objects are a lot more common than 'bad' objects, or if the penalty for mis-classifying a 'good' object as 'bad' is very different from the penalty for mis-classifying a 'bad' object as 'good', then you might want to measure accuracy differently.  The best measure of accuracy is again application-dependent; there is no single universal answer.


Computational power difference between all interconnected qubit vs few interconnected qubit

A linear chain of qubits has two big disadvantages over a planar grid of qubits:

1) Resilience. If you arrange your qubits into a line, and any one of them doesn't work well, your quantum computer has been cut in half. In a grid you instead end up with a hole that, while inconvenient, can be routed around.

2) Closeness. In a linear chain, the qubits are on average farther apart. So if you want to interact two states, it may take longer to swap them towards each other so that they can interact. That being said, in highly parallel algorithms where you're already saturating all the connections with operations, you tend to be able to combine the swaps with the interactions you wanted to do anyways for no extra cost (e.g. see the paper "Quantum Simulation of Electronic Structure with Linear Depth and Connectivity").


Prove that this language is not context-free

A unary language (a language over a unary alphabet) is context-free if and only if it is regular. The easiest way to see this is to convert a context-free grammar to a regular grammar using the fact that $xy = yx$ over a unary alphabet.

There are many ways of showing that $L$ is not regular, and so not context-free. One way is using the Myhill–Nerode criterion. Since $0^{2^n} 0^{2^n} \in L$ while $0^{2^m} 0^{2^n} \notin L$ for $m \neq n$, we see that the words $\{ 0^{2^n} : n \geq 0 \}$ are pairwise inequivalent, and so $L$ is not regular.

A proof using the pumping lemma is also not too difficult. Given a pumping length $n$, choose $m$ so that $2^{m-1} > n$, and consider the word $0^{2^m} \in L$. According to the pumping lemma you can write $0^{2^m} = xyz$ with $|xy| \leq n < 2^{m-1}$ and $|y| \geq 1$ so that $xz \in L$. But $xz = 0^{2^m-|y|}$ cannot be in $L$ since $2^{m-1} < 2^m-|y| < 2^m$. This contradiction shows that $L$ is not regular.


Use the fact that $\mathsf{BPP}\subseteq\Sigma_2$. Also note that if $P=NP$ then the entire polynomial hierarchy collapses to $P$.


Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair

Look at it this way.

RMFF- Places Task one after the other until the processor goes beyond the bound

RMNF - Looks at all the processors and see where the task will fit

P-Fair - Uses max utilization of 1 for each processor.

RM can only use N(2^(1/N)-1), this means that both RM will have a different value than P-Fair when utilization is between that value and its upper bound.

As for the RMFF, RMNF just think about it and play with the numbers and you will find answer. Make up task and start placing them according to both methods.

P.S: 2 more hours? Hope it helped.


You are right. The complement consists of all strings not in the language. So basically if the language says "all strings such that X holds" the complement is "all strings such that not X holds", the logical negation of X.

In this case the logical negation of "$i=j$ and $i=k$" equals "not ($i=j$ and $i=k$)" or using the Morgan's rule, "$i\neq j$ or $i\neq k$".

But there is a slight catch. Actually the strings in $L$ have an additional explicit condition, they are of the form $a^i b^j c^k$ for some $i,j,k$. That means the actual complement is the union of (1) all strings not of the form $a^i b^j c^k$ (thus, not in $a^* b^* c^* $) and (2) all strings of the form $a^i b^j c^k$ such that "$i\neq j$ or $i\neq k$".

The strings in (1) form the regular language $\{a,b,c\}^* - a^* b^* c^* $ and should not bother you too much. The strings in (2) are treated elsewhere in this forum.


Code optimization - syntax tree vs. intermediate representation

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

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

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


This is architecture specific so the following might not be true for all architectures.

Normally there is a special hardware in the CPU called interrupt controller that will react to interrupts. You usually program this hardware on boot time by writing a handler for each interrupt (called interrupt service routine) and giving the interrupt controller a table with the location of these handlers (the interrupt vector table https://en.wikipedia.org/wiki/Interrupt_vector_table).

When a hardware interrupt happens, the interrupt controller will automatically lookup the location of the corresponding handler and immediately continue execution there (on the very next assembler instruction). Depending on the architecture, there might now be a second set of registers, another stackpointer etc. that the ISR uses or it has to save the status of the interrupted program to the memory (RAM) perform it's actions and restore the state once it finishes.

The ISR is automatically run in a higher privilege mode on the CPU (if not already in a high privillege mode) and can therefore invoke other OS functionality. How the ISR is now interacting with the OS can't be answered in general. It could for example set some flags which are then checked by the OS threads.

Maybe you will also find this answer interesting: https://cs.stackexchange.com/a/85156/108759


Class of languages that are equivalent to the lambda calculus

The lambda calculus is exactly equivalent in expressive power to Turing machines, so the languages that can be translated into it are exactly those that are no more powerful than Turing machines.

Models of computation that are more powerful than Turing machines are known as "hypercomputation". However, except for computability theorists, most people don't ever consider languages that can express hypercomputation, so most people don't need a word that "not capable of hypercomputation." It's a bit like there being no word for "food that isn't poisonous" because not being poisonous is the default state for food so people don't really need a word for that.

Your question title asks about languages that are equivalent to the lambda calculus, i.e., those where we can translate in both directions. Because the lambda calculus has the same power as Turing machines, these are exactly the Turing-complete languages.


What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?

P1 arrives at time 0 and needs 3 seconds to process.

P2 arrived at time 2 and needs 1 second to process.

Processing

P1 arrives first and will process 2 second because time quantum is 2s. 1s left.

After processing P1 (2 seconds later), P2 will arrive.

It will completely process it and then return back to P1.

1 second later both processes are processed.


Does every computational problem have a decision version?

Here is a "counterexample": sorting. The natural decision version of sorting is deciding whether a given array is sorted. Another natural decision version is given an array and a permutation, decide whether the permutation correctly records the sorted order of the array. In both cases, the "decision versions" can be solved in linear time, while sorting itself (in most models) requires loglinear time.

Here is another "counterexample": consensus. This is a classical problem in distributed computing. I'm not sure it has a "decision version".

The claim you are stating is not a mathematical claim; it's just a comment whose goal is to explain why in introductory classes we only consider decision problems. There are three reasons: First, decision problems can be used to analyze many other types of computational problems (though not all of them). Second, it has become conventional to consider only decision problems (for example P and NP are classes of decision problems). Third, introductory classes are introductory, and so their scope is limited.

In order to make the claim a mathematical claim (and so, potentially, right or wrong), you will need to define all the concepts involved; there might be several ways of doing it, resulting in different interpretations of the claim. Some interpretations will result in valid statements: for example, optimization problems have canonical decision problems, and to some extent the two kinds of problems are equivalent in complexity. Other interpretations might be more problematic, for example if they encompass my first counterexample. Another source of difficulty is computational problems like my second counterexample to which this entire paradigm seems inapplicable.

Lecturers often make such comments, and these are supposed to be helpful for you as a student. If you find one of these comments confusing, I think it's best to just ignore it. If you have access to the professor, you can discuss the matter with them, but otherwise just drop the matter.


Can we improve the precision of IEEE floats by dropping leading zeros in the mantissa?

If you drop the leading zeroes then $3,5,9,17$ and so on will all have the same representation. Don't forget that the number being represented need not be an integer.


Is there a formalization of the computational model for quantum computers?

Yes.  The quantum Turing machine is a mathematical formalization of a computation model for a quantum computer.

See also https://en.wikipedia.org/wiki/Quantum_computing#Developments and https://en.wikipedia.org/wiki/Quantum_complexity_theory and https://en.wikipedia.org/wiki/BQP.


What the Hoare invariant state is the following:

  If you run the code with $X$ equal to some value $x > 0$, then at the end, $F$ will have the value $x!$ ($x$ factorial).

You can check that this is indeed the case.


Proving Blank-halt to be recursively enumerable through reduction to Halting problem

If you reduce $X$ to $Y$, you're showing that $X$ is no harder than $Y$ and that $Y$ is at least as hard as $X$.

So, by showing that some problem $X$ reduces to the halting problem, you're showing that $X$ is no harder than the halting problem, i.e., that it's recursively enumerable. Remember that we normally define problem classes to include all lower classes, so showing that $X$ is RE doesn't necessarily imply that it's not recursive, for example. In this case, we can separately prove that the blank halting problem isn't recursive, by reducing the halting problem to it, which shows it's at least as hard as the halting problem, as above.


3✕n chessboard with holes - maximum number of knights not attacking each other

Use dynamic programming to calculate the maximum number of non-attacking knights on the left $3\times m$ part of your board with holes, given the placement of knights in the last two columns of this part of the board.


your problem looks inherently exponential to me to find all the solutions. a rough sketch to show that is to create a large # of similar-looking objects. the objects are the same under translation and rotation. they (apparently?) can also be scaled. so in a rough sense there is no way to "speed it up" if you already have an exponential time algorithm. you ask for a better algorithm but also ask for general ideas. here are some ideas/ suggestions.

youve abstracted the problem but it might help to step back and describe the background that inspired it. is it from some field in particular? chances are there are papers that study the general area.
it looks like its in NP because its easy to verify solutions. think of solving it in terms of NP. a canonical problem in this area is the satisfiability problem. many problems have been converted to it and SAT solvers are "state of the art" for solving NP problems. SAT solvers can discover and handle the intrinsic symmetries in the problem not technically "efficiently" (in the sense of guaranteed P time) but in the "most efficient way known" based on heuristics, "best practices", and decades of optimization research/ theory. so consider translating it to SAT and studying it that way.
if you want a general idea of the algorithm behavior you can run it at different scales and graph the # of solutions to find basic scaling properties.
if you just want any solution, you might try a probabilistic approach where you lay down a simple starting shape say square/ rectangle and then randomly alter it until it gets closer to your requirements. see eg heuristics. genetic algorithms are also good for this. you can encode the shape in terms of genetic coding.
imagine a triangular shape that has 2 straight sides at right angles and then a 3rd that is diagonal and has any # of corners required. its not an "efficient" use of space because it has a large open area but it satisfies your criteria and can be created at any scale with arbitrary # of corners. you didnt specify any criteria about minimizing or maximizing space inside or outside. so maybe this is a bit underconstrained as stated.
actually think this might need to be described better. are you touching squares only at the edges squares and the squares touching those edge squares? what do you mean by "corners"? corners on your object? corner squares on the rectangle? you give only one example so think your description is somewhat ambiguous or subject to misinterpretation on closer inspection.


Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product

I thought about this problem a lot and I think that I devised a suitable
solution. I focus here on asymptotic analysis with respect to $K$, and my aim
is to provide tighter upper bound than one that I suggested in the
question. Therefore, I now observe slightly different problem
where $k_i \geq 1$. In that case the number of steps $T(K,n)$
required to enumerate all n-tuples of naturals greater or equal one 1 with
product less than or equal to $K$ is:
\begin{equation}
T(K, n) = \sum_{k=1}^{K} T(\lfloor \frac{K}{k} \rfloor, n - 1)
\end{equation}
\begin{equation}
T(K, 0) = 1
\end{equation}
where $T(K, 0)$ is the number of elementary operations in the basic case.

For any bound $x$, we know that:
\begin{equation}
T(x, 1) = \sum_{k=1}^{x} T(x, 0) = x
\end{equation}

Moreover, for $T(x, 2)$ we have:
\begin{equation}
T(x, 2) = T(\frac{x}{1}, 1) + T(\frac{x}{2}, 1) + T(\frac{x}{3}, 1)... + T(\frac{x}{x}, 1) = \frac{x}{1} + \frac{x}{2} + \frac{x}{3} ... + \frac{x}{x}
\end{equation}
We can see that this is in fact finite partial sum of harmonic series:
\begin{equation}
T(x, 2) = x \sum_{k=1}^{x} \frac{1}{k} = x H_x
\end{equation}
where $H_x = \sum_{k=1}^{x} \frac{1}{k}$ is the x-th harmonic number.

Now with $T(x, 2) = x H_x$, $T(x, 3)$ can be expressed as:
\begin{equation}
T(x, 3) = T(\frac{x}{1}, 2) + T(\frac{x}{2}, 2) + ... + T(\frac{x}{x}, 2) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1
\end{equation}
Now we can bound $T(x, 3)$:
\begin{equation}
T(x, 3) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1 \leq x H_x (1 + \frac{1}{2} + ... + \frac{1}{x}) = x H_x^2
\end{equation}

By induction, we get that $T(K, n) = K H_K^{n-1}$. Harmonic number can be
approximated with integral:
\begin{equation}
H_K = \int_{1}^{K} \frac{1}{t} dt = \ln K
\end{equation}

Therefore, an upper bound on complexity is given with $O(K \log^{n-1} (K))$.


Natural deduction proof: distributivity of existential quantification

You didn't say exactly what you tried, but it looks like you're trying to get there by applying elimination rules. That's not the simplest approach, and it might not work directly without case analysis on $P$ and $Q$ (I haven't tried). There's a very powerful theorem about natural deduction and most other basic logical framework: if there's a way to derive a proposition, there's a way to derive it without using elimination rules. This is called normalization. In the Curry-Howard correspondence, normalization of derivations corresponds to evaluation of programs and an introduction-only proof is a value (program with only constructors).

To prove that $(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$, let's use $\rightarrow_I$: we need to prove that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x.Q)$.

If there's a derivation of $\exists x. P \lor Q$, then there is a normal derivation of it, and in particular there is a derivation ending in $\exists_I$. The premise of this derivation is $[t/x](P \lor Q) = ([t/x]P) \lor ([t/x]Q)$ for some term $t$. This proposition itself has a derivation ending in one of the introduction rules for disjunction: either $_I\lor$ with the premise $[t/x]P$ or $\lor_I$ with the premise $[t/x]Q$. In the first case, we have a derivation of $[t/x]P = P$. In the second case, we can apply $\exists_I$ to derive $\exists x. Q$. In the first case, we can then derive $P \lor (\exists x. Q)$ with $_I\lor$. In the second case, we can derive the same proposition $P \lor (\exists x. Q)$ with $\lor_I$. We've shown that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x. Q)$, QED.


Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Update: this doesn't answer the question that the original poster was looking for, and doesn't help with  the general case where $|\Sigma|>2$, so the question remains open.

Here is a simpler construction, showing that in the case where $\Sigma=\{0,1\}$, $O(k \cdot 2^{2k})$ states suffice, and in fact you can recognize the language with a DFA with that many states.

Let's start by looking at the complement language:

$$\overline{L_k} = \{u \cdot v \in \Sigma^* : |u| = |v| = k, \exists i . u_i = v_i\}.$$

Notice that this can be recognized by a NFA with $2k^2 |\Sigma|$ states.  The NFA first guesses $i$ and a symbol $x$, then accepts all strings $u \cdot v$ where $u_i = v_i = x$.

Convert this to a DFA using the standard subset construction.  We get a DFA with $\le 2^{|\Sigma| k + 1} k$ states.  Now we can compute its complement, which is another DFA with the same number of states that recognizes $L_k$.  Since it is a DFA, it is in turn automatically a NFA, too.

This beats your construction for the case where $|\Sigma|=2$, but otherwise leads a NFA that's larger than your scheme.  However, I thought it might be of interest, both because it is so simple, and because it in fact provides a DFA (not just a NFA) to recognize your language $L_k$.


Identity in the category of types and functions

It has to satisfy the properties of the identity arrow - i.e. its left and right composition with any other arrow is that arrow.

Of course, you can have multiple different categories where the objects are types (for some definition of "types" - it's actually really complicated, if not impossible, once you start looking at polymorphic or dependent types) and arrows are something somehow related to functions between them. What exactly you choose to call "arrow" is up to you, as long as it satisfies the required properties (composition and identity).

A trivial example, you can say that "let us define that the (sole) arrow between type $A$ and type $B$ represents the family of all functions between $A$ and $B$" - in this category the sole arrow $A \to A$ will happen to also be the identity arrow. I suppose this is what you mean under "looking at type level".

Or you can say: For a given family of equivalence relations $Eq_T$ on every type $T$, let us define that there is one arrow between type $A$ and type $B$ for every function $A \to B$, modulo the function equivalence relation "maps $Eq_A$ to $Eq_B$". Then if you take the usual equality relation on integers and consider the arrows $int \to int$, in this category you'll only have one identity arrow - the function that maps a number to itself. The function $x \to x+1$ will not work.


This is just a shorthand, leaving off some things that aren't really needed to understand the concepts. If you want your $7$ to be written as a function again, all you need are a couple more implicit lambdas. Here's how I'd write the Church addition with those lambdas in place:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

But we also know that:

$$\lambda k . f k = f$$

Therefore:

$$\lambda g . \lambda z . 7 g z = 7$$


Limit repetitions in randomized list with each unique element occurring n times

I will assume that by "random" you mean you want the output will be uniformly distributed on the set of all valid arrangements, or in other words, that all valid arrangements are equally likely to be output by the algorithm.

Simple method: rejection sampling

A simple approach is to use rejection sampling: generate a random arrangement, then check if it contains any element $m$ times in a row, and if so throw that away and repeat.

You can generate a random arrangement by starting with the list $[0,1,2,0,1,2,0,1,2,\dots]$ and then applying a random permutation to it, i.e., randomly shuffling it.

This will ensure the output is uniformly distributed.  It will be efficient if $m$ is large and inefficient if $m$ is too small.  In particular, if $m \ge \log_3 n$, then this should be pretty efficient; the expected number of times you repeat is $O(1)$.  On the other hand, if $m \ll \log_3 m$, then this becomes highly inefficient, because you have to repeat many times.

Sophisticated method: ranking/unranking

Here is a more sophisticated technique that will be more efficient if $m$ is small.  It works by counting the number of valid arrangements using dynamic programming, and using ranking/unranking techniques.

Let's start by looking at how to count the number of valid arrangements.  In particular, let $f(n)$ denote the number of valid arrangements of length $n$.  I'll show how to compute $f(n)$ using dynamic programming.

To aid with that, let $g(n,x,r,a_1,a_2,a_3)$ denote the number of valid arrangements of length $n$ that use exactly $a_1$ 1's, $a_2$ 2's, $a_3$ 3's, without repeating any number $m$ times in a row, and assuming that before these $n$ you have a sequence of $r$ $x$'s in a row (e.g., if $x=3$ and $r=2$, then a valid sequence is allowed to start with up to $m-r-1$ 3's, but no more than that).  Notice that

$$f(n) = g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3) + g(n-1,3,1,n/3,n/3,n/3-1),$$

so if we can compute the $g$'s, we can compute $f$.  Also there is a recursive relation among the $g$'s:

$$g(n,1,r,a_1,a_2,a_3) = g(n-1,1,r+1,a_1-1,a_2,a_3) + g(n-1,2,1,a_1,a_2-1,a_3) + g(n-1,3,1,a_1,a_2,a_3-1),$$

which is obtained by a case analysis on the first digit of the sequence, and symmetrically for other values of $x$.  (Here I assume we agree on boundary conditions like $g(\cdot,\cdot,m,\cdot,\cdot,\cdot)=0$.)

Now this gives a dynamic programming algorithm for computing $g$, by memoizing, and thus an algorithm for computing $f$.  What is the running time?  Well, there are at most $3m(n/3)^3 = O(n^3m)$ different subproblems, and solving each one can be done in $O(1)$ time using memoization, so the total running time is $O(n^3m)$.

Now that we know how to count, how do we use that to generate a random valid arrangement?  We'll use unranking.  Since there are $f(n)$ valid arrangements, we can think of each integer in the range $1..f(n)$ as corresponding to a valid arrangement.  We will construct an algorithm that can find the arrangement corresponding to a particular integer $i$; then all we need do is pick a random integer in that range, find the corresponding arrangement, and we have a random valid arrangement.

It's easy to use the recursive formula above to build an unranking procedure.  Given an integer $i$, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3)$; if yes, then the first number in the sequence is 1; if not, we test whether $i \le  g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3)$; if yes, then the first number in the sequence is 2, else it is 3.  We continue from there to iteratively fill in each element of the sequence.

This lets us pick a valid sequence uniformly at random.  The running time is $O(n^3 m)$, so it is efficient for all values of $m$.  You can even precompute all of the $g$ values in advance, in which case the running time becomes $O(n)$ per random sequence you want to generate.


How to decompose into BCNF while preserving all functional dependencies

this very example is discussed in the first place I looked.

The short answer is that you cannot always achieve all of

BCNF;
an information-equivalent schema;
using keys as the only declared constraint(s).

Pick any two.

In this case you must retain R = {A, B, C}, with key {A, B} -- then we can't losslessly decompose R. In order to represent the FD C -> B as a relation with a suitable key, you need R1 = {C, B} with key {C}. So far we've achieved BCNF. To retain information equivalence, you need an Inclusion Dependency (aka Foreign Key constraint) R[C] ⊆ R1[C].

Strictly speaking to retain info equivalence, that Inclusion Dependency should probably be an Equality Dependency. But this is a contrived example, so nobody in practice would do that.


Length of the solution calculation in Breadth-first

I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.

Length of the solution

Once you reach a fitting leaf you have found your solution and can
   abort. The length of the solution, i.e. the number of steps you have
   to perform to get everybody across, is the length of the path from the
   root to that leaf.
Cost of the algorithm

The number of steps the algorithm has to perform is different, of
  course; it may visit many nodes that are not part of the final
  solution. The details depend on the specific implementation at hand.

Specifically, you seem to be concerned about backtracking out of
  dead ends. The usual way to implement BFS is using a queue which
  makes backtracking free since you don't actually do it; the next
  node to visit is already at the front of the queue.

If you don't use a queue and backtrack explicitly, well, you get
  quadratic worst-case performance. Don't do it.


The idea of ECC memory is that sometimes memory bits spontaneously flip --- this is rare but happens with noticeable probability, especially if memory is large. Using ECC memory, you can recover from such errors, at a certain cost (overhead).


Which CNF boolean formulas blow up exponentially at conversion to DNF?

The classical example is
$$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$
which blows up to $2^n$ terms when converted to a DNF.

Most functions have CNF and DNF complexity very large – $\Theta(2^n/n)$ if I remember correctly – and so for random functions there is no blow-up for trivial reasons.

Miltersen, Radhakrishnan and Wegener construct a monotone function which has an exponential gap.


Take the language to be $L=\Sigma^*$. $L$ can be solved trivially, so there is a polytime NTM that doesn't use any nondeterminism and solves $L$, call it $M$. The counting function for $M$ is $\#M(x)=1$ which is trivial.

Take $N$ be the following polytime NTM:

$N :=$ on input $x$,
1. nondeterministicly guess $b\in\{0,1\}$,
2. nondeterministicly guess an assignment $\tau$ for $x$,
3. if $b=0$,accept,
4. if $b=1$ and $\tau$ satisfies $x$, accept.
5. otherwise reject.

It is easy to see that $L(N) = L = L(M)$. However $\#N(x)=2^{numvar(x)}+\#SAT(x)$ which is essentially $\#SAT$ and is complete for $\#P$.

$numvar(x)$ denotes the number of propositional variables in $x$.

Therefore the notation $\#L$ is not well-defined (even if we assume $L \in \mathsf{NP}$). You have to fix a NTM $M$ first for $L$ and then talk about $\#M$. Depending on the NTMs you choose for $L$ you will get different counting languages.

In some cases like $SAT$, the intended NTM for the language is clear from context. In such cases, we may use the notation $\#L$ to mean $\#M$ where $M$ is the intended NTM for $L$. Note that even in those cases we are still fixing an NTM for $L$, we just don't state that explicitly.


Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two of opposite types with probability $q$. For what values of $p, q$ can we recover the partition with high probability (with respect to $n$)? It turns out that if $p$ and $q$ are too close then it is statistically impossible, and otherwise a simple algorithm succeeds with high probability.

The question you are asking is very specific, and the answer likely depends on the exact model and its parameters. It seems likely that for a low mutation rate, some iterative algorithm should work, perhaps even provably (with high probability).

One way to formulate this question more concretely is to come up with constraints on the relations between the sequences, constraints that hold with high probability. It could be that for an appropriate choice of constraints, the problem becomes feasible.


Why is the tape not part of the definition of a Turing Machine?

To formally define an instance of a Turing machine (not the general concept) you don't need to explicitly mention the tape itself, or its contents. To denote a configuration of this particular machine, or a computation performed by it, that is when you need some form of notation to describe the contents of the tape.


Why can't un-journaled filesystems be resized?

The "file allocation table" (which gives the FAT filesystem its name) is a fixed-size array "statically allocated at the time of formatting." Its size is determined by the size of the partition, because "The table contains entries for each cluster, a contiguous area of disk storage." (quoted from Wikipedia).

So if the partition is made larger, the FAT has to be made larger. But in order to do that, whatever pieces of files which happen to occupy the sectors adjacent to the FAT need to be moved elsewhere. That's not a simple procedure, and while it is being performed, the whole filesystem is in an inconsistent state.

That might seem like a suboptimal design, but since FAT was designed for single partition removable media (i.e. floppy disks) whose size was determined at the time of manufacture, there was no need to plan for resizing. The fixed-size immovable allocation table makes for faster, simpler code.

The Wikipedia article provides a lot more details, if you're curious. It's actually not too difficult a project to write a FAT driver, which might provide additional insights.


Result of ANDing & ORing functions expressed as CDNF & CCNF

There is no need to guess. Try to prove your guesses. If $f$ is the disjunction of minterms $\{m_i : i \in I\}$ and $g$ is the disjunction of minterms $\{m_j : j \in J\}$ then it is definitely the case that $f + g$ is the disjunction of $\{m_k : k \in I \cup J\}$, but not all $m_k$ are necessarily minterms. For example, $x + xy = x$.

Regarding $F+G$, try to use de Morgan's rules twice to reduce it to the case of $fg$, which is identical other than the operators involved. In Boolean algebra addition and multiplication are dual (via de Morgan's rules), so anything you can with CNFs you can also do with DNFs.


How to get the best factor for abstract algorithm that has expected cost?!

I don't know what the author of the question means with "approximation guarantee" (is it defined earlier in the book?), so I am just going to tell you what you can derive from the information that's given.

If the expected value of the algorithm is $\mathbb{E}=v$, then the probability that the algorithm outputs a value larger than $kv$ is at most $\frac{1}{k}$, from Markov's bound, if the cost function never goes negative. So if you run the algorithm $t$ times, then the probability that the minimum value among all trials is greater than $kv$, is at most $k^{-t}$ (why? because the trials are independent).

There are no hard guarantees until there is more information.


decidability about NFA accepting an input

The textbook probably suggests you convert into a DFA because  it is easier to simulate a DFA than to simulate a NFA and determine whether the DFA accepts the word w.  This is trickier on a NFA (but still possible, if you know how).


What edge-set is required to make a non-cyclic directed disconnected graph initial?

Assuming that "initial" means connected and having a single source, you can do no better than adding an edge to each source.


Can a computer game can run on a boot mode without the aid of os?

Yes, it is possible to boot computer to the specially designed program, which will be some game. But this will be harder, because there will be no drivers for advanced hardware, only elementary BIOS functions, basic video memory access. For example, if author want to add sound to the game, he can used PC speaker, or write own driver for ... for which card? Sound blaster, or RTL? What if user has another card? Same problem for video: game may know about some Radeon and will not work on older or newer AMD card or on Nvidia or Intel.

So, writing a bootable computer game is the same as writing both the game and the Operating System with drivers (or stealing its codes like in PS4's Orbis OS with FreeBSD sources or SteamOS with linux sources).


Yes, the decision problem is NP-complete.  If $n=1$ it is exactly the knapsack problem, which is already known to be NP-complete.

Possibly related Given a set of 2D vectors, find the furthest reachable point.


Algorithm for building a suffix array in time $O(n \log^2 n)$

You can compute the suffix array in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. The source code is contained in the original paper. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can also get the suffix-tree in linear time when you have access to the suffix-array and the LCP-array. The LCP-array can be also constructed with the DC3-algorithm.


Can an (extended) regular grammar have multiple nonterminals in its RHS?

Right regular grammars are very similar to NFAs. In fact, if we modify them slightly by forbidding productions of the form $A \to a$ but allowing ones of the form $A \to \epsilon$, they are completely equivalent to NFAs. As such, it's natural to allow rules of the form $A \to r B$, where $r$ is an arbitrary regular expression.

If we want to stay within the realm of grammars, we can allow instead (or additionally) rules of the form $A \to S'B$, where $S'$ is the starting symbol of a (nonterminal-)disjoint regular grammar (more generally, the regular grammars involved must form a DAG).


There are a few things to realize:

First, top level declarations are implicitly let-bound, so your code is equivalent to the following:

let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

  id :: a -> a
  id x = x

Secondly, as was mentioned in the comments, Haskell will sort the let statements topologically, nesting them when it can, and any recursive uses are monotyped unless annotated.

Finally, the types of let-variables are generalized at their definition, but specialized at their use. So now we have (something close to):

let
  id :: a -> a
  id x = x
in let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

Finally, we need to see that while variable types are generalized at their definition, they are specialized at their use.

So, this is roughly what inference does:

The checker infers the type $id : \alpha \to \alpha$, then generalizes this to $\forall a \ldotp a \to a$.
The checker puts $id : \forall a \ldotp a \to a$ into the environment for checking $x$ and $y$
While checking the definitions of $x$, at the use of $id$,
the type $\forall a \ldotp a \to a$ is instantiated to $\beta \to \beta$, where $\beta$ is a fresh unification variable.
While checking the definitions of $y$, at the use of $id$,
the type $\forall a \ldotp a \to a$ is instantiated to $\gamma \to \gamma$, where $\gamma$ is a different fresh unification variable.

Because the polymorphic type scheme is instantiated with unique variables at each use, the inference is able proceed without error.


Can the set of all $2^{24}$ colors be expressed as a ternary linear code?

Hint: The number of codewords in a ternary linear code is a power of 3.

That's my best guess for the answer that the setter expects. However, the truth is you can certainly use a ternary linear code to represent all colors, you will just have a little redundancy.


Why do we should not to use simple count instead of cumulative count in Counting Sort?

It is related to the stability of output this algorithm:

Stable sort: For same number appearing more than once in the input array, ties are broken by the rule that whichever number appears first in the input array appears first in the output array.

•The property of stability is important only when satellite data are carried around with the element being sorted.

•Counting sort is often used as a subroutine in radix sort. Counting sort’s stability is crucial to radix sort’s correctness.

Having a cumulative sum helps it in making it a stable sort.


Splitting a node in B+ tree with odd number of keys

There is no advantage to choosing one over the other.

"Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (whether to the left or the right) which isn't yet full, it's often better to balance the entries evenly between this node and its sibling. This saves an allocation.


Minimum number of moves required to transfer items from source bins to target bins?

The problem is NP-hard, by reduction from the partition problem.

Here is the reduction.  Consider an instance of the partition problem, namely, integer $x_1,\dots,x_n$.  Create $n$ source bins and 2 target bins, with $x_i$ items in the $i$th source bin.  Set the capacity on the target bins to $(x_1+\dots+x_n)/2$.  Then there is a solution to your movement problem that uses exactly $n$ moves, if and only if there is a solution to the partition problem.

We can also show your problem is strongly NP-hard, by reduction from 3-partition.

As a result, you should not expect to find any efficient algorithm that always gives the optimal answer and scales to large problems.  You might try looking for heuristics, approximation algorithms, or algorithms that could be exponential time in the worst case but hopefully are often fast in practice.  For instance, you could look into simulated annealing, integer linear programming, and approximation algorithms for bin packing.


For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

For this example I would simply state that the problem is that the uniqueness of values of timestamps, if it happens to hold, is only accidental: there is generally no fundamental reason that the same timestamp (even with very high precision) could not be assigned to 2 separate records.

For a primary key uniqueness should not be accidental but fundamental.


Is it proven that quantum computation is no better at solving NP complete problems than classical computation?

It is suspected that NP-complete problems cannot be solved in quantum polynomial time (i.e., that they are not in BQP), but this hasn't been proved. We don't expect a proof in the near future, since this would imply that P is different from NP.


Paths between tuples, MSV, decision trees

Consider any path from $a \in T$ to $b \in T$ inside $Y$. Let $t$ be the first time in which the first $k$ coordinates are not distinct. Prior to time $t$, for each $1 \leq i \leq k$, all coordinates in $j \in \{k+1,\ldots,n\}$ such that $a_j = a_i$ must keep satisfying this relation along the path, since otherwise there will be more than $k$ distinct values. Therefore at the point $t$, there will be fewer than $k$ distinct values. We conclude that the first $k$ coordinates always remain distinct, and that they determine the rest of the vector. In particular, the values in the first $k$ coordinates can't cross each other: if $a_i < b_i$ and $a_j > b_j$ then the intermediate value theorem shows that at some point $x$ along the path, $x_i = x_j$. We conclude that $a_1,\ldots,a_k = b_1,\ldots,b_k$. Since the first $k$ coordinates determine the rest, in fact $a = b$.


Clever memory management with constant time operations?

With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

This works well as long as all allocated blocks have the same size, and that size is a multiple of the size of a pointer, so that alignment is preserved. Allocation and deallocation are constant-time (that is, as constant-time as memory accesses and elementary additions -- in a modern computer, a memory access can involve cache misses and even virtual memory, hence disk accesses, so the "constant time" can be quite big). There is no memory overhead (no extra per-block pointers or things like that; the allocated blocks are contiguous). Also, the allocation pointer reaches a given point only if, at one time, that many blocks had to be allocated: since the allocation prefers using the free list, the allocation pointer is increased only if the space below the current pointer is clock full. In that sense, this is an optimal technique.

Decreasing the allocation pointer after a release can be more complex, since free blocks can be reliably identified only by following the free list, which goes through them in unpredictable order. If decreasing the big segment size when possible is important to you, you could want to use an alternate technique, with more overhead: between any two allocated blocks, you put a "hole". The holes are linked together with a doubly-linked list, in memory order. You need a data format for a hole such that you can locate the hole start address by knowing where it ends, and also the hole size if you know where the hole begins in memory. Then, when you release a block, you create a hole which you merge with the next and the previous holes, rebuilding (still in constant time) the ordered list of all holes. The overhead is then about two pointer-sized words per allocated block; but, at that price, you can reliably detect the occurrence of a "final hole", i.e. an occasion to decrease the big segment size.

There are many possible variations. A good introductory paper is Dynamic Storage Allocation: A Survey and Critical Review by Wilson et al.