Minimum distance in an undirected weighted graph to cover k nodes using teleportations

You can do this in polynomial time with a greedy algorithm by always
traveling to the nearest un-visited terminal, and dropping a portal in
every terminal.
The crucial observations are these:

Since it's free to drop a portal and use one, you always put a portal in each of the terminals.
There is no point traveling anywhere but to a terminal.
When you move to a terminal, you always travel from the closest portal.

Let $G = (V, E, w)$ be the input graph and $T \subseteq V$ be your $k$
terminals, with $v_0 \in T$.
Start with $T' = \{v_0\}$.  While $|T'|<k$, pick a terminal not in
$T'$ that is of shortest distance from $T'$ and add it to $T'$.  Sum up
the distances traveled in total.
Notice that you can preprocess your graph in $O(t^2 (n+m))$ time to get
a new (complete) graph $G' = (T, E', w')$ with only vertices from $T$ and
where the edge $t_1t_2$ has $w'(t_1, t_2) = \text{dist}_G(t_1, t_2)$.
Edit: This answer is updated.  The previous answer was based on Steiner Tree.


How does a TLB lookup compare all keys simultaneously?

Computer hardware is fundamentally parallel.  Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is writing back the results of a slightly earlier calculating instruction.

One of the reasons a layer 1 cache in a CPU is so small, and so much more expensive per bit of storage, is that the tag cache portion of the address is broadcast to multiple cache lines, and each of them has some independent hardware logic to compare this tag value against its own tag value in parallel, each independently calculating "that tag matches what I have" or "it doesn't match me".


challenge: Closing hash, linear probing, probe length 1

This problem was formulated and solved in 1962 by Donald Knuth; apparently, it was his first exercise in algorithmic analysis. It's often referred to as the "parking problem".

Knuth's analysis is beautifully simple. (Note: Knuth, and I think most computer scientists, used $n$ as the size of the hash table, and $k$ as the number of items inserted. So do I, even though the question is expressed differently.)

Let's start with the set $A$ of hash values of $k$ items, consisting of all sequences $\langle a_1, \ldots, a_k \rangle$, where $0 \le a_i < n$. Clearly there are $n^k$ possible sequences.

Now, suppose we have a bug-free hash table of size $n+1$, and look the set $B$ of all possible hash sequences for $k$ items,  $\langle b_1, \ldots, b_k \rangle$ with $0 \le b_i < n+1$. There are $(n+1)^k$ such sequences.

Of those sequences, we select the subset $B'$ for which the last table entry ($n$) is empty at the end of the insertion. Since once a slot is occupied, it remains occupied at the end, we know that for every sequence in $B'$, every $b_i < n$. Therefore, every sequence in $B'$ is also in $A$.

Moreover, we know that in the course of the insertion, no probe passes through position $n$. In other words, every sequence in this subset of $B$ is a sequence in $A$ in which there is no wrap-around, which are precisely the sequences in $A$ which do not trigger the bug.

So it will only remains to count these sequences. But that's trivial, because all of the slots in the (bug-free) hash table are identical. So the probability that a particular slot will be unoccupied after inserting $k$ items is $1 - {k \over {n+1}}$, with the result that there are $(n+1-k)(n+1)^{k-1}$ such sequences.

Thus, the probability that a random sequence of $k$ insertions into the buggy hash table will trigger the bug is $1 - {(n+1-k)(n+1)^{k-1}\over n^k}$.

By the way, the output of the program you paste-binned is not correct.  For example, it lists $4, 4, 4$ twice in the list for three insertions into a table of size 5.


Asymptotic complexity class preservation under logarithm?

This does not hold for all $f$, $g$. Consider $f(x) = x!$ and $g(x) = x^x$. It is the case that $x! \not\in \Omega(x^x)$ yet, using Stirling's approximation, we have that

$$\log (x!) \in \Theta(x \log x)$$

Since, $\log(x^x) = x \log x$, we have

$$\log f(x) \in \Theta(\log g(x))$$


With a list of opcodes for a virtual machine, is it possible to assign a number to every possible program of size n that can be run on that machine?

There is no need to assign a number. The program already is a number.
If you have $m$ opcodes and your program has $n$ instructions, then it can be interpreted as an $n$-"digit" number written in base $m$.


Proof emptiness for PDA is $\mathcal{O}(n^3)$

Start with an arbitrary PDA. Convert it to a PDA which pushes at most two symbols to the stack at each step — this only incurs a linear blow-up. Convert the PDA to a CFG using the standard construction, described in this answer. Since the PDA pushed at most two symbols at each step, the CFG has size $O(n^3)$ (for each transition $p \stackrel {a,\gamma} \to q$, where $a$ is a letter and $\gamma$ is a word in the stack alphabet, we have to enumerate over $|\gamma| \leq 2$ states, hence the number of transitions is at most the original number of transitions times $|Q|^2$). Convert the CFG to Chomsky normal form with linear blow-up. Then use the linear time algorithm described in this answer to check whether the CFG generates an empty language or not.

Summarizing:

Convert the PDA to one in which at most two symbols are pushed to the stack at each move (linear blow-up).
Convert the new PDA to a CFG (cubic blow-up).
Convert the CFG to Chomsky normal form (linear blow-up).
Check emptiness of the CFG in Chomsky normal form (linear time).

You can probably skip the step in  which you convert the CFG to Chomsky normal form by modifying slightly the algorithm described in the second answer.


Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

You've forgotten that $y$ can be pumped any number of times, including zero. The string $xy^0z = b^pc^p$ is not in the language.


Turing machines: can a machine write to a finite number of memory cells, but not halt?

Consider a Turing machine that repeatedly moves its head right, then left, then right, then left, and so on.


Algorithm for finding a mouse hole in a wall in O(n) time

This problem goes by various names, including the linear search problem and the cow path problem. The solution indicated in Denis's answer is optimal for deterministic algorithms (though the competitive ratio is 9 rather than 8), but randomized algorithms can do almost twice as better; see Kao, Rife and Tate.


How can I show mathematically the time complexity of this function is O(N)?

You can use induction on input.
For example, in your foo,
to show that foo(N) uses exactly N comparisons,
Base case: foo(1) uses 1 comparison
Induction hypothesis: foo(N) uses N comparisons
Step case: foo(N+1) does one comparison and then call foo(N), thus in total, does N+1 comparisons.
You can prove similar statement for addition or all operations, and then you can give a time complexity based on those number of operations.


Example using Penetrance & Branching Factor in State-space Heuristic Search

Consider the following search tree. Your heuristic search algorithm starts the search at the root node. Unexpanded nodes are marked gray.

For some reason, the heuristic is being guided towards the left-most subtree, when in fact the goal node is in the right-most subtree, marked with green.

Nodes that have been expanded are marked red. After the appealing left-most subtree turned out to be a dead-end, the heuristic is now luckily being guided directly towards the goal. From the situation of the previous figure, we'll expand a total of three new nodes before arriving at the goal.

From the figure above, the length of the path to the goal is $3$. There are $17$ expanded nodes. Therefore, the penetrance is $3/17 \approx 0.43$.

The branching factor is the maximum number of successors of any node. For example, the branching factor of a binary tree is $2$ since each node has at most two children. Likewise, in the above search tree the branching factor is $3$.

What you seem to be interested in is not the branching factor, but the effective branching factor $B^*$ which is a way to characterize the quality of a heuristic. If the total number of expanded nodes is $T$, and the length of the path to the goal is $L$ (this is more commonly known as depth), then $B^*$ is the branching factor that a uniform tree of depth $L$ would have in order to contain $T+1$ nodes. Therefore,

$$T+1 = 1 + B^* + (B^*)^2 + \cdots + (B^*)^L.$$

If you plug-in the values we obtained in search, that is, $T=17$ and $L=3$, you get $B^* \approx 2.165$. This is exactly the same value you get from using your equation; it's just merely a different representation for the same thing.

The effective branching factor can vary across instances, but is somewhat constant for hard enough problems. A well-designed heuristic would have a value of $B^*$ close to $1$, allowing fairly large problems to be solved reasonable cheaply.


Kraft's inequality and Shannon's noiseless coding theorem for an encoding

I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a compact prefix code, since $1/4+1/4+1/16+1/16+1/32+1/32 < 1$.

Shannon's noiseless coding theorem states that when optimally encoding large blocks, in the limit the average encoding size per data item is the entropy. You can prove the upper bound part of the theorem using Huffman coding applied to large blocks. Huffman coding produces a code whose average bit length is at most $H(X)+1$, where $X$ is the source. If you use Huffman coding on blocks of size $n$, the average bit length per data item becomes $H(X)+1/n$ (why?), and by letting $n\to\infty$, you can get as close to the entropy as you want.


How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is
$$
p(\alpha) = \frac{2^{-n}}{m} \sum_{j\colon \alpha \text{ satisfies } C_j} 2^{|C_j|}.
$$
Let $A$ be a random satisfying assignment chosen according to the algorithm, and let $X = 1/p(A)$. Then
$$
E[X] = \sum_{\alpha \text{ satisfying}} \frac{\Pr[A=\alpha]}{p(\alpha)} = \sum_{\alpha \text{ satisfying}} = \text{# satisfying assignments}.
$$


Decision Tree Learning Deviation - Russell and Norvig

TL;DR: They are basically doing a chi-squared test to compare the distributions.

In more detail: Let's break this down into two parts, $\Delta = \Delta_1 + \Delta_2$ where

$$\begin{align*}
\Delta_1 &= \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k}\\
\Delta_2 &= \sum_{k=1}^d \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}.
\end{align*}$$

Then $\Delta_1$ is the test statistic for a chi-squared test of the goodness of fit between the two distributions $p_k$ and $\hat{p}^k$.  Similarly, $\Delta_2$ is the test statistic for the goodness of fit between $n_k$ and $\hat{n}_k$.

If the distribution $p_k$ is similar to $\hat{p}_k$, and $n_k$ is similar to $\hat{n}_k$, then $\Delta$ will be small (the former means that $\Delta_1$ will be small, and the latter means that $\Delta_2$ will be small).  Conversely, if $p_k$ is not similar to $\hat{p}_k$, or $n_k$ is not similar to $\hat{n}_k$, then $\Delta$ will be large (in the former case, $\Delta_1$ will be large; in the latter case,  $\Delta_2$ will be large).

So this is a convenient measure of the total deviation between these distributions: a convenient way to get a single number to help us measure the extent to which both $p_k$ is similar to $\hat{p}_k$  and $n_k$ is similar to $\hat{n}_k$.

The chi-squared test is a standard test for goodness of fit, so its test statistic is a reasonable choice here.  As for why the chi-squared test  is a good test for measuring goodness of fit, you can read the standard literature on the chi-squared test.


Confusing notation in concatenation of error correcting codes

You get it right.

The notation $$(C_{out}\circ C_{in})(m)$$
means: "take m, encode it with $C_{out}$ and then encode each symbol with $C_{in}$."
From the point of view of the channel, $C_{in}$ is "closer", hence the inner one; see the figure in the wiki page you refer to.

This is indeed what the wiki page says.

The confusion is probably because you think of composition of functions, where the common notation $(g\circ f)(x)$ means $g(f(x))$. But here we don't have function composition but instead code concatenation, so the $\circ$ operation has a different meaning - it means
$$ C_{in}(c_1), \ldots, C_{in}(c_n)$$
with $(c_1, \ldots, c_n) =  C_{out}(m)$.

Just to complete the picture, concatenation codes where developed by David Forney in 1965, where he named the inner/outer codes that way (again, having the channel  as the center of this point-of-view). See his PHD work and in particular Figure 2 that illustrates this concept (same as in wikipedia).


Three of the options use the same trick: if $C1,C2$ are two classes of languages and $C1 \subseteq C2$; then $L1 \in C2$ doesn't imply that $L1 \notin C1$.

The only choice that cannot be made true is 3: if there is a polynomial time reduction from an undecidable language $L_1$ to a decidable language $L_2$ then $L_1$ becomes decidable, too  (just build a Turing Machine that computes the reduction and then solve the problem using the decider for $L_2$) and this is a contraddiction.


Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?

There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong.

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.


$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1

According to the description $w$ is a palindrome of length $n$, and not the complete string $x$. A palindrome is a string that will be the same when reversed. For each length $n$ there are of course finitely many palindromes (as there are only finitely many strings of that length).

The language consists of all palindromes with given length, with arbitrary strings before and after. The palindromes can be listed,  and "hard-wired" in the expression.

$L_1 = (0+1)^*(0+1)(0+1)^*$,
$L_2 = (0+1)^*(00+11)(0+1)^*$,
$L_3 = (0+1)^*(000+010+101+111)(0+1)^*$, ...

The complement is added to see how many strings are not of the given form. Any nonempty string will contain a palindrome of length 1 of course. Hence $L_1^c= \{\varepsilon\}$.

Strings that do not contain $00$ or $11$ must have alternating $0$ and $1$'s,hance the $(01)^*$ etc.


How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$.
Let's consider the set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. Then we can define an equivalence relation on the set $A$:
$$(a_1 \sim a_2) \equiv (P(a_1) = P(a_2))$$
A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.
The algorithm to split all the arcs into such equivalence classes is exact, but may be slow for large graphs. It consists of two steps:
Step 1. For each arc $a \in A$ compute the subset $P(a) \subset P$. This can be done by scanning all the paths in the set $P$, and updating all the subsets $P(a)$ along each such path.
Step 2. Let's assume that we store all the subsets $P(a)$ as binary numbers. Sort the set $A$ by these numbers - this will allow us to group together all the arcs with the same subset of paths. Scan this sorted set of arcs, assigning the same color to arcs in each group.


$\mathbf{NC_2}$ is closed under log-space reduction

We want to show that if $A\le_lB$ and $B\in NC_2$ then $A\in NC_2$.

Since $A\le_l B$ we have a Turing machine $M_{f,i}(x)$ calculating the i'th bit of the reduction output $f(x)_i$, using logarithmic space.

$M_{f,i}(x)=1 \iff \left( G_{M_{f,i}(x)},c_{start},c_{acc} \right)\in PATH$

Where $G_{M_{f,i}(x)}$ is the configuration graph of the computation of the logspace machine $M_{f,i}$ on $x$,and $c_{start},c_{acc}$ are the initial and accepting configurations, correspondingly.

Now your $NC_2$ circuit for $A$ will, "in parallel", compute all the bits of the reduction $f(x)$ (this can be done since you proved $PATH\in NC_2$) and send the result as input to the $NC_2$ circuit for $B$. This results in an $NC_2$ circuit for $A$.


Modeling a set of probabilistic concurrent processes

One approach is to model it as a composition of $N+1$ processes: a scheduler process, plus your $N$ basic processes.  At each time step, the scheduler process selects which basic process will execute next.  Your scheduler could be randomized: for instance, at each time step, it could choose which basic process to execute next uniformly at random, if you wanted.

Now the transitions of the entire system, and their probabilities, should be easy to derive.  A state of the system is of the form $\langle s_0,s_1,\dots,s_N \rangle$ where $s_0$ is the state of the scheduler and $s_i$ is the state of the $i$th basic process.  Each transition might have the form $\langle s_0,\dots,s_N \rangle \to \langle s'_0,s_1,\dots,s_{i-1},s'_i,s_{i+1},\dots,s_N \rangle$ (where $i$ is a deterministic function of $s_0$, and with probability given by the probability of $s_0 \to s'_0$ in the scheduler multiplied by the probability of $s_i \to s'_i$ in the $i$th basic process).

There are probably other ways to model it as well, maybe better ones for all I know.  This is just one possibility that occurs to me.


IS Array of Positive Integers Always 'Equalizable' With This Strategy?

If the GCD of the array D is larger than 1, then this cannot always be done. The simplest example is $A = \{1,2\},D=\{2\}$. In contrast, if the GCD of the array D is 1, then it is known that large enough integers can be represented as positive linear combinations of elements of D. In particular, there is an integer $N$ such that $N-a$ can be represented for all $a \in A$. Summing all these representations will equalize the array.

For example, when $A = \{2,3,7\}$ and $D = \{1,2,5\}$, we can add $\{1,0,0\}$ once and $\{1,1,0\}$ four times, reflecting the representations $7-2=5 \times 1$, $7-3=4 \times 1$, $7-7 = 0 \times 1$. Even when $D = \{2,5\}$ this has a solution: using $11 = 3 \times 2 + 1 \times 5$, $10 = 2 \times 5$, $6 = 3 \times 2$, we can add $\{2,0,2\}$ three times, $\{5,5,0\}$ once, and $\{0,5,0\}$ once to get $\{13,13,13\}$.


clustering with uncertain number of clusters

Several algorithms allow doing this.
First one is the hierarchical clustering. When creating your dendrogram, the key is to cut the "longest branches." DBSCAN is also a good alternative. Finally, you can use K-means or GMM and optimize your number of cluster against a metrics (see sklearn pages on the subject) (be aware of overfitting)


Proving that the language of TMs with finite left head moves is undecidable

Hint: Reduce from the halting problem. Given a Turing machine $M$ and an input $w$, you want to come up with a new pair $\langle M',w \rangle$ such that $M$ halts on $w$ iff $M'$ makes a finite number of left moves on $w'$. Now if $M$ halts on $w$ then in particular it makes a finite number of left moves, but the other direction is not true. Think of a way of ensuring that if $M$ makes an infinite number of moves in any direction, then $M'$ makes an infinite number of left moves. (You might want to add some spurious moves.)


Group values up to a threshold and minimize groups

I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.


Convert scientific notation decimal number to binary

There is more than one correct approach to convert the number.  The former is a correct algorithm for the problem.  This kind of base conversion would usually be implemented in a library for the programming language you are using.  There might be many such implementations out there, and I don't know what all of them are doing.

I would not recommend the latter approach, as I expect computing $2^\alpha$ where $\alpha=31 \log_2 10$ will be painful.

See also The math behind converting from any base to any base without going through base 10? and https://math.stackexchange.com/q/48968/14578 and https://en.wikipedia.org/wiki/Positional_notation#Base_conversion and https://en.wikipedia.org/wiki/Binary_number#Conversion_to_and_from_other_numeral_systems.


As pointed out by the other answer, producing a list of the intersections is not doable in subquadratic time.
However, counting all the intersections can be done in linear time.
The rough idea for that one is to sort all coordinates (starting points and end points of intervals) into one list using counting sort (as the range of the values we are sorting is fixed) and iterate over it, maintaining a counter for the number of intervals intersecting at the current point and another one for the total number of intersections.
If the current coordinate is an end point, reduce the first counter by 1.
Otherwise (i.e. the current coordinate is a starting point), increase the first counter by 1 and increase the total counter by the value of the first counter.


The role of asymptotic notation in $e^x=1++Θ(^2)$?

What the equation means is that there exist constant $A>0$ and $B,C$ such that
$$
|x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2.
$$
In particular, for small $x$, $e^x$ is very close to $1+x$, since the error is only $O(x^2)$ (when $x$ is small, $x^2$ is much smaller than $x$).

The same estimate doesn't hold for large $x$ — indeed, $e^x$ grows faster than $x^2$, indeed faster than any fixed power of $x$. So the quoted estimate only holds for small $x$.

Here is a graphic example. Below is the plot of $\frac{e^x-1-x}{x^2}$ for $|x| \leq 0.1$. You can see that it is very close to $0.5$. This is consistent with the Taylor expansion of $e^x$, which is $1 + x + x^2/2 + O(x^3)$.

In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.

Credit: plots executed using Desmos.


Rather than thinking about this in terms of substitutions, you might find it useful to think about this in terms of equalities that you can infer.

In the first step, you inferred that $w=Y$.

In the second step, you inferred that $X=p(Z)$.

In the third step, you inferred that $X=Z$.

It follows that you can infer $Z=p(Z)$.  So we know $X=Z=p(Z)$ and $w=Y$.

Of course, if you can infer that two things are equal, you can substitute one for the other.  But maybe it's easier to think about unification as being a way to keep track of which things are equal (which in turn helps you know which substitutions you can make).  Hope this helps make this kind of situation feel more intuitive.


Finding longest balanced parentheses using $n$ smaller strings

First, let's remark that the order in which you put the selected strings is not significant as long as it is valid.  That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence.  The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns.  An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$.  This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$.  You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the  exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound)  and thus you are sure that after the ninth or so column, you'll have duplicate entries.


Operating System: About user thread and kernel thread?

As the given text says, it is not necessary that for every new user thread a new kernel thread is also created. In fact different operating systems can implement this in a different way. Some OS will map every new user thread to a new kernel thread(one to one mapping), some can have a maximum limit on number of kernel threads beyond which a kernel thread will be mapped with more than one user thread(many to one). There can also be an OS which maps a single user thread to more than one kernel thread, and vice versa. This would be a many to many model.

All these models have their own pros and cons. Which model to choose would depend upon what functionality is required from OS, available hardware resources etc.


Separability of the nearest power of two function

No, $f(x+y)$ is not separable.

Consider: $f(3+5)=8$.  Also $f(3)=4$ and $f(5)=8$.

At the same time, $f(4+5)=16$.  Also $f(4)=4$ and $f(5)=8$.

It follows that $f(x+y)$ is not determined by $f(x)$ and $f(y)$ (consider $y=5$, $x_1=3$, $x_2=4$), so there is no function $h$ such that $f(x+y)=h(f(x),f(y))$.


Complexity of Merge Sort that splits in a random position

For definiteness, let us suppose that the $T(1) = 1$ and that if the split is $k+(n-k)$ then the running time is $T(k) + T(n-k) + n$.
The recursion for the worst-case running time is therefore
$$
T(n) = \begin{cases} \max_{1 \leq k \leq n-1} T(k) + T(n-k) + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}
$$

In order to calculate the worst-case complexity, we need both an upper bound and a lower bound. You already gave the lower bound:
$$
T(n) \geq T(1) + T(n-1) + n = T(n-1) + n+1.
$$
Iterating this easily yields $T(n) = \Omega(n^2)$.

In the other direction, let us prove that $T(n) \leq n^2$ for all $n$. The base case is clear. For the inductive case,
$$
T(k) + T(n-k) + n \leq k^2 + (n-k)^2 + n \leq 1 + (n-1)^2 + n = n^2 - n + 2 \leq n^2,
$$
since $n \geq 2$. It follows that $T(n) = \Theta(n^2)$.

(In fact, with some more work you should be able to show that $k=1$ is indeed (together with $k=n-1$) the worst choice.)

Let us now proceed to the average case running time (i.e., the expected running time), which satisfies the recurrence
$$
S(n) = \begin{cases} \frac{1}{n-1}\sum_{1 \leq k \leq n-1} [S(k) + S(n-k)] + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}
$$
We can simplify the inductive case to
$$
S(n) = \frac{2}{n-1} \sum_{1 \leq k \leq n-1} S(k) + n.
$$
This implies that for $n \geq 2$,
$$
n S(n+1) = 2(S(1) + \cdots + S(n)) + (n+1)n, \\
(n-1) S(n) = 2(S(1) + \cdots + S(n-1)) + n(n-1).
$$
Subtracting gives
$$
nS(n+1) - (n-1)S(n) = 2S(n) + 2n \Longrightarrow nS(n+1) = (n+1)S(n) + 2n \Longrightarrow \\ \frac{S(n+1)}{n+1} = \frac{S(n)}{n} + \frac{2}{n+1}.
$$
This shows that
$$
\frac{S(n)}{n} = \frac{2}{n} + \frac{2}{n-1} + \cdots + \frac{2}{2} + \frac{S(1)}{1} = 2H_n - 1 = \Theta(\log n),
$$
and so $S(n) = \Theta(n\log n)$.


Is there a name for the class of operations containing prefix, suffix, etc?

In natural languages, at least, the term is affix.


Is a relational database just a $ \geq 2$-dimensional array?

No, it isn't. A data structure can be described in two ways:

How does it store the data.
Which operations are supported, their performance (usually given as asymptotic time- and/or space-complexity), and what laws do they obey.

Obviously, a database doesn't store all its data as a single array.

Arrays support, as basic operations, retrieving an element by index and storing an element under an index. Operations required for databases are (to a first approximation) given by relational algebra: selection, projection, union, difference, and join (or product).


Spotting the difference between two arrays using divide-and-conquer

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.


Why is the complete state of a turing machine representable by a finite word?

I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

No, it can not.

When the Turing machine starts, the tape contains the input (a finite-length word) followed by an infinite amount of blank symbols (often written as #). It is common to simply omit the trailing infinitely many blanks, and just represent a finite prefix instead, adding blanks as needed when the head moves right past the end of the tape.

When the machine runs, in each step it can at most (over-)write over one tape symbol, and move right by at most one position. This is an essential feature of any Turing machine.

Hence, after finitely many steps, we still have a finite amount of non-blank symbols. The tape again contains infinitely many trailing blanks (usually not represented), so it can be represented by a suitable finite prefix.


What is the equivalent of the integers symbol Z for n bit only integers?

For bounded sets, the usual convention is to use interval notation.

Specifically, $[a,b]$ means "real numbers between $a$ and $b$, inclusive", while $[a\mathinner{\ldotp \ldotp}b]$ means "integers between $a$ and $b$, inclusive". Changing any of the square brackets to curved means that endpoint is not included: $a \not\in (a,b]$, for example.

In this case, you'd want the interval $[0\mathinner{\ldotp \ldotp}2^n)$. Or, if you think the delimiters look mismatched and weird, you can use $[0\mathinner{\ldotp \ldotp}2^n-1]$.

P.S. LaTeX doesn't have a builtin for "two dots", so I used \mathinner{\ldotp \ldotp} from this answer.


What is the decision version of independent set?

The definition of the decision version of independent set is the following:

Given as input a graph $G = (V,E)$ and an integer $k \in \mathbb{N}$, does there exist a set of pairwise non-adjacent vertices $I \subseteq V$ of size $|I| \geq k$?

The problem is polynomial time solvable if you consider $k$ to be constant, i.e., you can solve the problem in time $\mathcal{O}(n^k)$ but we usually take $k$ to be a part of the input.  If you reduce an NP-complete problem to this problem, you will see that the $k$ is indeed unbounded.


Fork() execution and number of processes

Each fork call duplicate process, so after first call there are two of them. You may call the one with pid = 0, the master process (parent, top, original).

After that two processes are in the second line (second fork), executing it, there are four processes now. I have not seen such distinction, but you may at that point say that two of them are child processes.

After the final fork, there are eight processes altogether, according to your materials, the original process is called parent and the rest are childs.

To draw it properly you should create a tree, with two children after each fork, where in fact one of them is the original caller.


What you are looking for are directed acyclic graphs (DAGs). If you want your DAG to have a unique "root", then you can ask for a DAG with a single source. DAGs are very useful in many branches of computer science.


To build a special unary regular expression

There is a "smart" way of following your approach:
$$
(a^p)^*a(\epsilon+a)^{p-1}
$$
Here $r^p$ is shortcut for $r$ concatenated $p$ times.

This regular expression has length $O(p)$. On the other hand, using the pumping lemma it is not hard to show that the minimal NFA for the language contains at least $p$ states, and this gives a lower bound of $\Omega(p)$ on the size of a regular expression for the language, since a regular expression can be translated to an NFA with only a constant multiplicative blow-up in size.


Primitive recursive functions and unbounded quantifiers

If $P(t,x_1,\dots,x_n) \in \zeta$, then clearly $(\forall t)_{\le 0}P(t,x_1,\dots,x_n) = P(0,x_1,\dots,x_n) \in \zeta$.

Moreover, if for some $y$, we have $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, then it can easily be shown that $(\forall t)_{\le y+1}P(t,x_1,\dots,x_n) = P(y+1,x_1,\dots,x_n) \land (\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, noting that taking the logical and is a primitive recursive operation.

By induction, we have that for any $y$,  $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$. Things work similarly for $(\exists t)_{\le y}$. However, this reasoning doesn't extend to unbounded quantifiers, and in the general case, $\forall t P(t,x_1,\dots,x_n) \notin \zeta$.

If you think of PRC predicates as things that can be checked by a computer in finite time, the underlying meaning is that

if it takes finite time to check whether a given proposition is true for any given value, then it also takes finite time to check whether it's true for any/all values in a finite set (at most the sum of the finite times taken to check for each element in the set)
on the other hand, it's not necessarily possible to check that it's true for any/all values in an infinite set. Naively checking for $0$, then $1$, then $2$, etc..., could take forever.

The answer to your second question is proposition 4. Indeed, in proposition 3, the universal quantifier over $x$ is bounded by the free variable $y$, which is a finite value. In other words, proposition 3 could be rewritten as $(\forall x)_{\le y}P(x)$.


What are the #P-hard version of Latin square and sudoku?

The counting problems corresponding to your two decision problems are:

Given a partially filled Latin square, in how many ways can it be completed to a Latin square?
Given a partially filled Sudoku puzzle, in how many ways can it be completed to a Sudoku solution?


Let $w(a,b)$ be the expected profit with $a$ positive cards and $b$ negative cards. Then $w(0,0) = 0$ and
$$
w(a,b) = \max\bigl(0, \tfrac{a}{a+b} (w(a-1,b) + 1) + \tfrac{b}{a+b} (w(a,b-1) - 1)\bigr).
$$
Indeed, if we stop the game immediately, the profit is zero. Otherwise, with probability $\tfrac{a}{a+b}$, we pull out a positive card, and with probability $\tfrac{b}{a+b}$, we pull out a negative card.

Using this recurrence, it is easy to compute $w(4999,4999)$. On my laptop it took less than a second.


Shortest path that passes through specific node(s)

Compute the shortest path between all pairs of the twelve special nodes (nodes 1, 100, and all ten of your particular nodes), and use these as edge lengths in a new graph consisting only of these twelve nodes. Now, you have a graph containing twelve nodes, and you want to find the shortest path from 1 to 100 that uses at least five other nodes. Now, you can use your algorithm (which I think is just dynamic programming) on this graph, which is much smaller. The solution on the new graph will give a solution for the original graph, which you can find by replacing the edges in the solution in the new graph with the shortest paths you computed in the first step.

For your example, we will have 4 nodes in the new graph. The edge lengths in the new graph are: 0-1:5, 0-4:6, 0-5:11, 1-4:5, 1-5:10, 4-5:5. These correspond to the shortest paths between nodes $i$ and $j$ in the original graph. The shortest path including one node from the list is 0-4-5, which has length 11. Now, replacing each edge in this path with the path computed in the first step gives the path 0-3-4-5 in the original graph.


How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

What you ask might not be possible in general. If $L(T)$ denotes the set of words $x$ for which $T(x)$ accepts, and you do not have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, then you could choose:

$M$ as a Turing machine that takes another Turing machine $T$ as input and accepts if and only if $T$ halts on empty input. (Notice that such a Turing Machine $M$ exists).
$M'$ as a Turing Machines that recognizes $\Sigma^*$.

Then, there is no Turing Machine $T$ that recognizes $L(M) \cap L(M') = L(M)$ since $T$ would solve the halting problem.
On the other hand, if you are fine with a Turing machine that accepts $L(M) \cap L(M')$ or if you have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, your problem is solved by a Turing machine that, on input $x$, operates as follows:

Simulate $M(x)$ until it halts (possibly never).
If $M(x)$ rejects, reject.
Simulate $M'(x)$ until it halts (possibly never).
If $M'(x)$ rejects, reject.
Accept.


Python: Clustering based on pairwise distance matrix

The constraints you have are not very clear (why should you start with "central items" ?). You should maybe try to come up with a well defined problem by precisely defining the clustering(s) you are looking for.

For example, if the clustering you want is such that the maximum number of clusters is $k_{max}$ and the maximum distance between two elements in a cluster is $d_{max}$, one possible approach is to perform a Complete-linkage Hierarchical clustering of your items. Possible clusterings then correspond to cuts in the resulting dendogram. Most library include the possibility of finding a cut that correspond to $k$ clusters or at a "height" $d$. A cut at height $d_{max}$ corresponds to the smallest clustering that respect the distance constraint. If the latter is not possible with the library you are using, you can explore every cut from size $1$ to size $k_{max}$ and select one that respects the distance constraint (Note it may not always be possible to found one e.g. with  $d_{max}$ close to $0$ and $k_{max}$ close to $1$.)


There are languages that are representable by an LTL formula but by no deterministic Büchi automaton (DBA).
Thus a translation from LTL to DBA cannot exist.
An example is the formula $\mathbf{F}\mathbf{G} a$, which states that from some moment on $a$ has to hold forever.
A nondeterministic Büchi automaton can guess when this moment occurs.

No deterministic Büchi automaton can accept the corresponding language. To see this, assume that there is a DBA for the language and note that when reading only $a$ an accepting state must be visited at some point.
After visiting the accepting state, let the next symbol of the input word be $b$, and then $a$ again until another accepting state is reached.
Such a state must be reached again eventually, as $a^* b a^{\omega}$ is part of the language.
By iterating this idea a word can be constructed that is not in the language but nevertheless is accepted by the automaton, which contradicts the assumption.


Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not

It's not regular. Hint: Let $p$ be the integer of the pumping lemma and pump the string $x^{6p}y^{3p}z^{2p}$.


Basic idea: In the exact cover problem, each element is reduced to a number. Then, each set is reduced to the sum of the numbers it covers. Finally, set $k$ to be the sum of all numbers.

This reduction always works one way: If a solution exists for the exact cover problem, a solution also exists for the subset sum problem.

The hard part is to prove the other way. Trivial numbers don't work. Suppose the elements are reduced to $1,2,3,4$, and the sets are

$S_1=\{3,4\}$
$S_2=\{3\}$

The reduction to subset sum is the numbers $7,3$ and $k=10$, which return YES but there's no solution to the exact cover problem!

We need to be smarter in choosing the numbers. Noticed the flaw in the previous numbers is that $3$ can replace $1,2$. We don't want any number to be replaced. Hence, we want the numbers to have sufficiently large gaps. Suppose in an exact cover problem of $n$ elements, the first element is reduced to $1$. How large should the second number be? There are $2^{n-1}$ sets that can include the first number. So, the second element should be reduced to a number larger than $2^{n-1}$ such that no matter how many times $1$ appears, it cannot replace the second number. Let's just reduce the second element to $2^n$. The same argument applies to the third argument, so we reduce it to $2^n\times 2^n=4^n$.

In conclusion, the $i$-th element in the exact cover problem has a value of $2^{in}$. Each set is reduced to the sum of numbers it covers.

Now we showed that exact cover is in NP-Hard. We need to prove that it is also in NP in order to show that it is NP-Complete. I think that's relatively simple. If you need help for that, I'll provide some hints for you.


How to cover given entries in a matrix with minimum number of rows and columns?

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns.

A vertex cover of $G$ corresponds to a set of selected rows and columns such that each matrix entry of 1 is in at least one of selected rows or columns. So, the problem to find minimum number of covering plates is the same as determining the minimum vertex cover for graph $G$.

Thanks to Kőnig's theorem, for bipartite graph $G$, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. So, the problem is shifted to find a a maximum-cardinality matching  of $G$.

There are many efficient algorithms that finds a maximum-cardinality matching in a bipartite graph, such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. There are many existing implementations of them in various programming languages that can be easily searched.


Examples of languages not decidable by a TM using certain upper bounds on space/time

Look up the time hierarchy and space hierarchy theorems. They give examples of languages which can be computed using $f(n)$ time (or space), and require more or less $f(n)$ time (or space). These languages are basically the following:

  Descriptions of Turing machines that halt after time $f(n)$ (after using space $f(n)$).

Perhaps you won't consider these languages natural. Unfortunately, the best lower bounds known for natural languages are currently only $\Omega(n)$ (for time) and probably even worse for space. However, it is conjectured that NP-hard problems require exponential time (this is known as the Exponential Time Hypothesis).


Is it possible that the diameter of a graph be shorter than the longest shortest path?

The diameter of a graph is, by definition, the length of the longest shortest path, i.e.,

$$\mathrm{diam}(G) = \max_{x,y\in V(G)} \min\, \{\mathrm{len}(P)\mid P\text{ is a path from }x\text{ to }y\}\,.$$

But remember that the length of a path is the number of edges it contains, not the number of vertices. (That is, a single edge is a path of length 1, not 2.)


what is the difference between memory access and data memory access?

A memory access happens when the CPU loads bits from main memory or stores bits to main memory. The CPU will first check to see if it can load the bits from a cache, in which case it will skip the (slow) memory access entirely.

One kind of memory access is a data memory address, when the CPU runs an instruction that explicitly loads or stores data from/to memory. In your examples, the arrows request data memory accesses (or cache accesses). "Data" is a very general term but here it means the bits that the program is operating on, as distinct from the bits that convey the program itself.

Another kind of memory access is an instruction fetch, which happens when the program counter gets a new value as part of running the instructions in the program. It usually just steps forward but a branch instruction can jump to a new location. Either way, no memory access is needed when the instructions are already cached.

In your example, the sequence of register/memory instructions have to load into the CPU before it can execute them. That requires instruction fetches.

(A Harvard architecture CPU has one bus to/from data memory and a second bus to/from instruction memory, so it can fetch from both in parallel. In that case the distinction between an instruction fetch and a data fetch is starker.)

The instructions themselves had to get into memory somehow. An interpreter or loader put them there, treating those instructions as data.

The distinction is whether the data is loading by the explicit request of the program instructions vs. the implicit need to load instructions themselves. The former are easier to cost out. The latter costs depend on the size of the instruction caches, on interruptions taken that might spill this program's instructions from the cache, etc.


How large is the seed in an encryption algorithm such as stream cipher?

The seed of a pseudorandom generator that is used as a stream cipher is called a key.
The most common key sizes are 128 bits and 256 bits. (That's symmetric keys, where there's no cheaper way to break than brute force. Asymmetric cryptography typically relies on keys having certain mathematical properties that make the algorithm work, but also enable better attacks than brute force.)
To understand how hard it is to break a 128-bit key, meaning that you have to try $p \cdot 2^{128}$ possibilities for a chance of success $p$, consider these orders of magnitude:

A fast processor might be able to try about one billion keys per second (1GHz).
A powerful attacker might be able to afford one billion processors.
The universe is about 1 billion billion seconds old (a little over 30 billion years).
1 billion is slightly less than $2^{30}$ ($2^{30} = (2^{10})^3 = 1024^3 \gtrsim (10^3)^3 = 10^9$).

So if you're extremely rich and willing to wait until the universe is twice as old, you can enumerate about $2^{120}$ keys. If you're only willing to wait 30 years, you can only enumerate about $2^{90}$ keys, giving you a chance of breaking any particular key of less than one in 250 billion. Conclusion: a 128-bit key is sufficient for security against brute force.
A 256-bit key provides a security margin that can cover:

Hypothetical advances in cryptanalysis that make the algorithm slightly easier to break.
Hypothetical advances in computation, such as quantum computers, which effectively halve the key size.
A very powerful adversary who tries to break basically every encrypted communication, and is interested in even succeeding for a tiny fraction.
A very powerful adversary who records basically every encrypted communication, and would detect if the same key is used twice, which could then let them discover the key by non-cryptographic means (exploiting a bug, demanding it at gunpoint, a subpoena, …). Due to the “birthday paradox”, there's a macroscopic chance that two instances will generate the same random key if the number of instances is at least about the square root of the number of possible keys, so 8 billion people using a billion different keys each (about $2^{63}$ keys in total) would be around the threshold for 128-bit keys.

In practice, key size just isn't an issue except in legacy software and protocols that are at least 2 decades out of date (keys shorter than 128 bits became obsolete when AES became the de facto standard in the early 2000s). Cryptography gets broken by non-cryptographic means or due to implementation weaknesses such as side channels, or gets circumvented altogether due to non-cryptography-related security vulnerabilities (binary exploits, escaping exploits, misconfigured controls, phishing, …). Cryptographic algorithms are usually the strongest part of information security.


Algorithm to find k elements following the median in sorted order

Answering your second question:

Find the median $m$, and partition the set into $L_1 = \{x | x \in S \wedge x < m\}$ and $L_2 = \{x | x \in S \wedge x > m\}$.
Find the $k$th largest element $x_k$ in $L_2$, and partition the set into $L_2' = \{x | x \in L_2  \wedge x \leq x_k\}$ and $L_3 = \{x | x \in L_2 \wedge x > x_k\}$.
Sort $L_2'$ and return.

Steps 1 and 2 take $O(n)$. Step 3 takes $O(k \log k)$. Total time $O(n + k \log k)$.

Note this assumes distinct values. Repeated values involves some edge case handling.


is it possible to know if a language is regular if its equivalence classes are finite?

One of the main results of Myhill–Nerode theory is that a language is regular iff its Myhill–Nerode relation has finitely many equivalence classes. You can find a proof in many online resources. In particular, if all equivalence classes of the Myhill–Nerdoe relation of a language are finite, then it must have infinitely many equivalence classes, and so be non-regular.

The language $L^*$ is finite in two cases: if $L = \emptyset$ or if $L = \{\epsilon\}$. In any other case it is infinite.


Sort an array of $n$ elements when only $\log n$ are not in place

Assuming that "$k$ elements out of place" means that there exist $k$ elements whose deletion leaves the rest of the array sorted, there's an $O(n+k\log k)$-time algorithm to sort the whole array.

In a nutshell, compute an increasing subsequence of length at least $n-2k$, sort the others, and merge. The former can be accomplished in time $O(n)$ by a simple stack algorithm that pushes elements one at a time and pops the top two whenever they're out of order. The optimal deletion strategy must delete at least one of these elements, so the total damage is upperbounded by $2k$  deletions.


Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

Pick any pair of vertices $u,v$ where it is possible to reach $v$ from $u$.  Add an edge $u \to v$ with a length that is really large.


You're using the terminology of recursion theory. Let me rephrase the argument in terms of computer programs.

$K$ is the set of all programs $x$ which halt when run on $x$ as input.
$K_1$ is the set of all programs $x$ which halt on some input.

Given a program $x$, consider the following program $f(x)$:

For $n=1,2,3,\ldots$: run program $x$ on inputs $1,\ldots,n$ for $n$ steps, and halt if $x$ halts of any of them halt.

The program $f(x)$ halts iff $x \in K_1$. In particular, $x \in K_1$ iff $f(x) \in K$. Since $f$ is computable, this gives a reduction from $K_1$ to $K$.


Generate all combinations of a set/array with specific conditions

Let $k = 11$ in your problem, so we want to generate all sets with values in the range $0$ to $k$ and with between $1$ and $12$ elements. Then you can do the following:

First generate all sets for $k-1$ (recursively)
Then, for each set, make two copies, one with a $k$ on the end and one without a $k$ on the end.

If you prefer doing it iteratively, here is this described in an iterative fashion (pseudocode):

generate_all_subsets(k):
    let sets = [[0]]
    for i from 1 to k:
        for each set in sets:
            add sets + [k] to sets
            # (now there are two copies: sets, and sets + [k],
            #  so the size of 'sets' has doubled)
    return sets


Find the best set of triples of objects, using each object at max one time

Your problem is NP-hard.  In particular, 3-dimensional matching is a special case of your problem, and 3-dimensional matching is NP-hard -- so your problem is, too.


How to solve this mapping reduction problem by proving the computability of this function?

The reduction function is simply

$$
f(x)=x0
$$

which is computable, since a TM can move to the end of $x$, append a $0$, and halt. It is also total, by definition.

Note that to prove that $f$ is computable we do NOT have to consider the decidability / enumerability of any sets. I think your confusion is caused by thinking about c.e. sets when crafting $f$, but defining a reduction function does not involve enumerability. You only have to ensure that $f$ is total computable, and that $x\in A \iff f(x)\in B$ for all $x$.


Bipartite maximum matching with added constraints

Let me start by modifying the problem statement to use standard graph theory terminology, according to my interpretation of the original post:

Let $G=(V, E)$ be a bipartite graph, with $V= A \cup B$, with $A=\{a_i\}_{1\leq i \leq m}$, with $B=\{b_j\}_{1 \leq j \leq n}$, and with $E \subseteq A \times B$. For an edge set $S \subseteq E$, let $f(A, S)$ denote the set of integers $i$ such that $(a_i, b_k) \in S$ for some $k$, and let $g(B, S)$ denote the set of integers $j$ such that $(a_k, b_j)\in S$ for some $k$. Find a maximal edge set $S^*\subseteq E$ with the property that $f(A, S^*)\subseteq g(A, S^*)$.

Assuming that this interpretation is correct, this algorithm should work:
Initialize $S = E$. Construct $m$ lists $A_1, A_2, \ldots A_m$, where $A_i = \{j \ |\ (a_i, b_j) \in S\}$, and construct $n$ lists $B_1, B_2, \ldots B_n$, where $B_j = \{i \ |\ (a_i, b_j) \in S\}$. Compute $f(A, S)$ and $g(B, S)$, and take some $c \in f(A, S) - g(B, S)$. Remove all edges of $S$ of the form $(a_c, b_k)$, and update $\{A_i\}, \{B_j\}, f(A,S)$, and $g(B, S)$ accordingly. Repeat until $f(A, S) - g(B, S)$ is empty.
It is easy to see that the resultant $S$ is maximal, as every edge removed was necessary. It is also easy to see that the running time is $O(\lvert V \rvert+\lvert E \rvert)$, as each edge is processed $O(1)$ times.


If the language is finite like you have given in the question then regular expression is simple just write all string separated by $+$(union).
So $$r = 100 + 10 + 011$$
further you have something common in first two string so
$$r= 10(0+\epsilon) + 011$$

  I feel like I'm overcomplicating it.

For that You need to learn three operators $*$ , $+$ and $.$ properly & understand the language given then It will be easy for you to make a regular expression without making a D.F.A..


Courses that give good insight on the nature of a Computer Science major?

Here are some thoughts about your suggestions for further study, plus one that you didn't mention.

Discrete Mathematics

This course should be part of the background for every computer scientist. The material is relevant for lots of areas we deal with and can be interesting and engaging whether or not one is going to concentrate on CS. That said, though, the subject matter won't necessarily give you an insight into what CS is really about unless it is specifically tailored to computer science applications (which it rarely is, in my experience).

Theory of Computation

A great choice, though it takes a bit of "mathematical maturity" to get through (meaning that you might find Discrete listed as a prerequisite). In one sense, this is the foundation for much of the rest of CS, since it asks "What things can and cannot be computed?" and often proceeds to answer this question by looking at increasingly more powerful models of computation, asking what kinds of problems these models can and cannot solve. Full disclosure: I'm a theorist and so find this area to be particularly beautiful.

AI

Well taught, this can turn out to be an eye-opening introduction to a lot of CS topics as well as being, in many people's opinion, just downright fascinating. Poorly taught, though, this can be little more than a specialized data structures course (still interesting, just not as much fun).

Data Structures

You didn't specify what your programming course covered, but this is a natural follow-on. Learning to program, you were exposed to what one might call the standard collections of algorithmic basics, like selection (if statements), loops, arrays, function calls, and (if you were lucky), recursion. A course in Data Structures goes on from there and usually is organized around the "canonical" structures used for organizing data, structures like lists, trees, stacks, hash tables, and the like. This is absolutely indispensable for any practicing computer scientist. At many schools, in fact, it's the next course to be taken after the first programming course.

So, what should you do next? All of your possibilities have their merits, but I'd advise a Data Structures course, for a couple of reasons. First, if you take it and hate it (assuming that your reaction isn't just due to a lousy teacher or a poorly-designed course), then CS is probably not the way you want to continue and it'll be good to find that out early. If, on the other hand, you take it and walk out with the reaction "that was fun", then you'll not only have shown you probably have an aptitude for all the rest that will follow, but at most schools, you'll have placed yourself at the right point in the CS curriculum to continue.

Best of luck.


How many languages exist over the following alphabets?

A language over an alphabet $\Sigma$ is any subset of the set of all finite strings with elements in $\Sigma$. If $\Sigma$ is finite or countably infinite, and not empty, then the set of all finite strings with elements in $\Sigma$ is countably infinite ($\aleph_0$) and the set of all languages over the alphabet $\Sigma$ has the same cardinality as the real numbers ($\aleph_1$). (Not calling it just "uncountable", because the set of languages is indeed uncountable, but there are uncountable sets with higher cardinality).


One-way function is not injective when it is in NP

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.

Since $L$ is always in $\mathsf{NP}$ (using the very same machine), the contrapositive is exactly the statement you're after.


Yes if $\Sigma \supseteq \{a, b\}$. To show the equality, let's show one is a subset of the other, and vice versa.

$\Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \subseteq \Sigma^\ast$ holds, because for any word $w \in \Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\}$, we know $w = u a^n b^n$ for $u \in \Sigma^\ast$, therefore $w \in \Sigma^\ast$ since $\Sigma \supseteq \{a, b\}$.
$\Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \supseteq \Sigma^\ast$ holds, because

$$
  \Sigma^\ast \cdot \left\{ a^n b^n \middle| n \geq 0 \right\} \supseteq \Sigma^\ast \cdot \{ a^0 b^0 \} = \Sigma^\ast \cdot \{ \varepsilon \} = \Sigma^\ast
$$

where $\varepsilon$ is the empty word.


Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

Suppose there is a cycle $v_1v_2\ldots v_kv_1$ such that every edge in this cycle belongs to some shortest path. Suppose $v_1v_2$ belongs to the shortest path $1\ldots u_1v_1v_2u_2\ldots N$ and $v_2v_3$ belongs to the shortest path $1\ldots u_3v_2v_3u_4\ldots N$, then the weight of the path $v_2v_3u_4\ldots N$ is no greater than that of the path $v_2u_2\ldots N$1. Hence, $1\ldots u_1v_1v_2v_3u_4\ldots N$ is another shortest path.

Repeating similar argument for the edges $v_3v_4,\ldots,v_kv_1$, we can get a shortest path $1\ldots u_1v_1v_2\ldots v_kv_1u_{2k}\ldots N$. This is impossible because $1\ldots u_1v_1u_{2k}\ldots N$ is obviously shorter.

1 Otherwise the weight of the path $1\ldots u_3v_2v_3u_4\ldots N$ is greater than that of the walk $1\ldots u_3v_2u_2\ldots N$, which contradicts to the assumption that $1\ldots u_3v_2v_3u_4\ldots N$ is a shortest path.


In computer science, "lazy" means "just in time": in other words, you defer doing a computation until the last possible moment (e.g., until when the output is needed).

In computer science, "online" means that you are processing a bunch of input in a streaming fashion.  For instance, you might be given a sequence of queries.  An online algorithm would immediately answer each query.  In contrast, an offline algorithm might wait until it has seen all the queries before answering any of them.


Can every CFG be converted into an equivalent CFG of this form?

Since you're allowing $x = \epsilon$ in a production of the form $A \rightarrow xBC$, it seems you can first convert the grammar to Chomsky Normal Form so that every production is of one of the forms $A \rightarrow \epsilon BC$, $A \rightarrow x$, and $A \rightarrow \epsilon$. The only problem is that the productions which produce only a single terminal are not of the form you want, but that isn't too difficult to remedy.


Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

The fact of the matter is, if a proof exists, then a Curry-Howard version of the program exists too. That doesn't mean that it's easy to find, though.

Undecidability still holds for Curry-Howard: if your types are advanced enough to capture logic, then there's no algorithm which takes in a type and outputs a program of that type, if it exists. Just like there's no algorithm that looks at a proposition and tells you if it's true or not.

  Billions of zeros on critical line have been calculated in many many ways.

Curry-Howard does not say that a program to compute zeroes can be turned into a proof of the Reimann hypothesis. It doesn't say that any program is a proof. What it says is, there is a dependently typed programming language where there's a type corresponding to the Reimann hypothesis, and a program with that type iff there's a proof of the Reimann hypothesis.

What this program would actually look like, if it's a proof, is a function that takes a number and a proof that that number is a zero of the Zeta function, and outputs a proof that that number is either a negative integer or has complex part 1/2. (Notice how the type of the input proof depends on the value of the given input, this is the "dependent" of dependent types).


What is the Best and easiest way to create a Classifer for Sentiment Analysis

This isn't the best way but it's simple and fast:

preprocess the input with the Porter Stemmming algorithm (it's a process for removing the commoner morphological and inflexional endings from words in English) or similar (take a look at Snowball)
preprocess the input flagging words before and after every negation ("never", "not", "no", "n't"):

the movie was not great => the movie ¬was not ¬great

Use Bernoulli Naïve Bayes (duplicate words are removed from the document and given a class, positive or negative, you assume that the words are conditionally independent of each other):
  $$P(C_j | D) = \frac{\prod_i P(x_i | C_j) P(C_j)}{P(D)}$$

$$P(x_i | C_j) = \frac{count\ of\ x_i\ in\ documents\ of\ class\ C_j}{total\ number\ of\ words\ in\ documents\ of\ class\ C_j}$$
($x_i$ are the individual words of the document $D$)

You can also use Laplacian smoothing to avoid problems if  the  classifier encounters a word that hasn't been seen in the training set:

$$P(x_i | C_j) = \frac{1 + count\ of\ x_i\ in\ documents\ of\ class\ C_j}{2 (total\ number\ of\ words\ in\ documents\ of\ class\ C_j)}$$

This works quite well.

Further steps are feature selection (removing redundant features, while retaining those features that have high disambiguation capabilities) and the use of ngrams (e.g. Fast and accurate sentiment classification using an enhanced Naive Bayes model by Vivek Narayanan, Ishan Arora, Arjun Bhatia).


How does equality works for qubit-vectors?

The state of an $n$-qubit system is defined by $2^n$ complex numbers. Basically the numbers are weightings for each of the classical $n$-bit states, similar to a probability... but square-rooted.

Technically, two quantum states are equal only if all of those weights are equal. But, when it comes to the practical aspects of quantum computing, it's better to focus on continuous concepts like distance rather than discrete concepts like equality because we only get very indirect access to the weights.

For example, quantum mechanics places pretty strict limits on how well you can compare two states. If the vectors defined by the amplitudes of state $a$ and state $b$ are an angle $\theta$ apart, then the chance of any QM process correctly distinguishing between them is upper-bounded by $\frac{1}{2} + \frac{1}{2}|\sin \theta|$ or equivalently $\frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle a | b\rangle|^2}$ (look up 'Trace Distance'). Distinguishing is strictly easier than equating, and we're already failing probabilistically at distinguishing! That's why people focus more on the distances.


Interval Scheduling problem with more than 1 machine

You may want to consider a solution with dp(i, j, k) where i represents the x that machine 1 is at, j represents the x that machine 2 is one, and k represents the index of the task you're considering
The state transition in this case would be O(1) because you either take the task or not, for which you can increment/decrement i/j accordingly.
I'm not sure what D and n are but if D refers to the amount of time allotted for machine 1 and 2 and n is the number of tasks, then I believe this could be the solution you're looking for
Note that "x" refers to time. Also, this solution would work if the tasks were assigned a value
Let me know if you want an implementation of this


Given a regular language, show another language is regular

Your idea is right.

However, in general the initial state $q_0$ of a finite state automaton may also be used in other ways than just as a starting position, so the automaton may return to the state. Those later visits do not want to loose the letter $1$.

Are you sure the order $δ(δ(q,a),1)$ is correct?


Why can't we flip the answer of a NDTM efficiently?

A nondeterministic Turing machine accepts if at least one path accepts; it only rejects if all paths reject. This asymmetry makes it hard to "flip answers".

For example, suppose you have a nondeterministic Turing machine $M$ that has two paths for input $w$: one accepts, the other rejects. $M$ has at least one accepting path for $w$, so it accepts. Suppose we want to produce a machine that accepts exactly the inputs that $M$ rejects.  The obvious first attempt is to take $M$ and make its accepting states reject, and its rejecting states accept. $M$ has one accepting path for $w$ and one rejecting path; this new machine $M'$ has one rejecting path and one accepting path. So it still accepts $w$, which it was supposed to reject!

A nondeterministic machine can't look at all its paths simultaneously and take action based on what all of those paths do. If you like, you can think of it as a form of parallelism where the threads are forbidden to communicate with each other. When all of the threads have finished the program must ask itself the following question: "Did at least one of my threads accept?" If the answer is yes, it is legally obliged to accept; if the answer is no, it is legally obliged to reject. It cannot do anything else.

When you simulate a nondeterministic machine $M$ using another one, $M'$, each path of $M'$ simulates one path of $M$ and sees only that path. It can't say, "If all those other paths rejected, I'll accept" because it can't see the other paths; it can only see itself. So all it could possibly say is things like, "If the path I simulated accepted, I'll reject" or "If the path I simulated accepted, I'll accept too". Then, at the end of the computation, the machine has to say, "If any of my paths accepted, I'll accept too", leading to the problem I described above. To invert the behaviour of $M$, each path of $M'$ needs to say, "If the path I simulated accepted, I reject; else, I accept" and, at the end of the computation, the machine needs to say, "If all of my paths accepted, I accept; else, I reject."  This is because, if all of the simulator's paths accepted, that means all of $M$'s paths rejected, so $M$ rejected, so the simulator needs to accept. But the simulator isn't a valid nondeterministic Turing machine because it isn't using the legally mandated acceptance criterion. It can't do that.

The only way we know to figure out if a nondeterministic machine rejects its input is to try every possible path and verify that they all reject.  After all, if even one of them accepted, the machine would accept the input.  But trying every possible path is exponentially slower than trying just one.


Dynamic Programming on bracketed sequences

Let $S(i,j)$ be the set of the shortest FBEs containing $x_i\ldots x_j$. We focus on non-trivial cases ($j-i\ge 2$).

If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k<j$ such that $x_i,\ldots, x_k$ belong to $A$ and $x_{k+1},\ldots,x_j$ belongs to $B$. Easy to see $T(i,j)=\min_k\{T(i,k)+T(k+1,j)\}$.

Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form [$A$]. Note $x_{i+1},\ldots,x_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x_i\neq$ [ or $x_j\neq$ ] (say $x_i\neq$ [ WLOG), then $A$[] (with the form $AB$) is also an FBE containing $x_i\ldots x_j$, which contradicts to the assumption. Hence $x_i$ and $x_j$ must match.

Combining the two paragraphs above, we have proved

if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

if $x_i$ and $x_j$ match,

$$T(i,j)\ge \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

Note concentrating a shortest FBE containing $x_i\ldots x_k$ and a shortest FBE containing $x_{k+1}\ldots x_j$ constitutes an FBE containing $x_i\ldots x_j$, so $T(i,j)\le \min_k\{T(i,k)+T(k+1,j)\}$. In addition, if $x_i$ and $x_j$ match, say $x_i=$ [ and $x_j=$ ], and let $s$ be a shortest FBE containing $x_{i+1}\ldots x_{j-1}$, then [$s$] is an FBE containing $x_i\ldots x_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x_i$ and $x_j$ match,

$$T(i,j)\le \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

So the recursion turns out to be

if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

if $x_i$ and $x_j$ match,

$$T(i,j)= \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$


Build a scheduler, to simulate parallel game flow

Your set of rules is self-conflicting. You require

  Same unit cannot perform two actions in parallel

but also

  When unit perform attack, the interacting unit must perform take damage [...] during the attack-action time of the performing unit.

and

  Multiple units can attack single unit at once

In other words, you require that multiple take damage actions be performed simultaneously while demanding that that may not happen.


What does it mean that a value can only be incremented after it's been loaded into a register?

Here are some more concepts to help with this.

CPUs use load and store instructions to execute the high level language concept of tally++;.  This is not atomic, unlike atomic CPU operations such as read-modify-write.

This question is alluding to the fact that there is no atomicity and that the common set of instructions can be executed in any interleaving by the $n$ processes.

The "lost update" concept is the enemy here. Wikipedia's "Concurrency control" article talks about this but mostly in a database transaction sense. Nevertheless it is absolutely the same high level concept of:

Thread1 reads tally into register (likely the ALU) (observes 6)
Thread2 reads tally (observes 6)
Thread1 increments ALU (now is 7)
Thread2 increments ALU (now is 7)
Thread1 writes ALU to tally memory (value stored is 7)
Thread2 writes ALU to tally memory (value stored is 7)

So BOTH threads/processes/whatever have "incremented" tally but the shared memory value of tally is ONLY 1 larger than when it started. Thread2's write to memory caused a lost update; Thread1's write was "lost".

By setting the question to say that there are at least three instructions required to increment (i.e. tally++;) the asker is saying that it is entirely possible that lost updates can occur due to interleaving of the instructions by multiple processes and causing lost updates.

I'd say the lower bound of tally is 50 (maximum destructive interleavings occur).
Upper bound is 50 * numProcesses (where no unscrupulous interleavings of the increment code occur).

Concepts to look up are:

Shared memory concurrency/parallel
Atomic and non-atomic instructions like load store and read modify write
Interleaving of instructions
Lost update


Correctness proof of the algoritm to generate permutations in lexicographic order

One can try to come up with the algorithm by oneself (thereby proving its correctness) after incremental understanding of: (a) how to define a permutation as "larger" (lexciographically) than another one, (b) what really the very next permutation of $P$ "looks like" compared to $P$ (how/where it differs from $P$). Once we find-out some properties, we may be able to write this algorithm ourselves.
Some outline:

define the "lexicographic order" of permutations $P_1$ and $P_2$. Say, $k$ is the very first index at which they differ. Then the "order" of their elements at index $k$ decides the "lexicographic order" of $P_1$ and $P_2$.

So what should be the smallest and largest permutation of array $a$ ?

Suppose array $a$ currently holds permutation $P$. Say $P'$ is the very next permutation of $P$ in the lexicographic-order, and they first differ at index $k$. Now, use the definition in (1) and the observation in (2) to find out what is the structure of elements in $P/P'$ at index $k$ and after it. You can argue that:

elements in $P$ after $k$ must form a decreasing-sequence (call it $S$).
element in $P$ at $k$ must be smaller than the largest element of $S$, which is $a[k+1]$.
due to above, we must have an element $a[l]$ in $S$ which is the smallest element in $S$ larger than $a[k]$. In $P'$, this element must appear at index $k$.
so the remaining (after $k$) elements of $P'$ are simply $S$ with $a[l]$ removed and $a[k]$ added.
these remaining (after $k$) elements of $P'$, must be in increasing order (for $P'$ to be the smallest possible, but larger than $P$). The 4th step in the posted algorithm is simply obtaining this increasing order by reversing the existing decreasing-sequence $S$ (now modified via swap, but continues to remain decreasing).

(For further details, refer to section "Lexicographical Order" in this).


Difference between the tilde and big-O notations

The $\sim$ notation is similar to the more conventional $\Theta$ notation. There are two main differences between $\sim$ and $O$:

$O$ only provides an upper bounds, while $\sim$ is simultaneously an upper bound and a lower bound. When we say that the running time of an algorithm is $O(n^2)$, this doesn't preclude the possibility that it is $O(n)$. In contrast, if the running time is $\sim n^2$ then it cannot be $\sim n$.
 Another notation with these properties is $\Theta$.
$O$ only holds up to a constant: $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C > 0$ (and large enough $n$). In contrast, for $\sim$ the implied constant is always $1$: if $f \sim g$ then $f/g \to 1$. This contrasts with $\Theta$ in which the implied constant is arbitrary, and indeed there could be different constants for the lower and upper bounds.

Exact constants are impractical in general, for many reasons: they are machine dependent, hard to compute, and could fluctuate depending on $n$. The first problem can be mitigating by measuring some proxy for the actual time complexity, such as the number of comparisons in a sorting algorithm.

Sampling the course, it seems they are using $\Theta$, but call it order of growth.


No, a compiler takes as string as input and checks if that string is syntactically correct. If it is, it outputs another string (code in a different language, e.g., machine code) that is equivalent to the input; if it is not, it outputs "syntax error".

A Turing machine is an abstract machine (i.e., a description of a machine, rather than an actual physical thing) that performs computations. According to the Church–Turing thesis, anything that can be computed by any physical system can be computed by a Turing machine.  Since compilers are implemented on physical systems, one could, in principle, design a Turing machine that computes the same mapping from strings to strings as any given compiler.  But it's not true that a compiler is a Turing machine; rather, a compiler does something that a Turing machine can also do.


Which all nodes will qualify as an ancestor?

The root-2 is an ancestor of 11 (it's the great-grandparent) but you're asking about the 2 on the left, which is not an ancestor. There is no directed path from that node to 11 since the left-2 has no outgoing edges. Paths must respect the direction of the edges.  Siblings are not ancestors for the same reason.

(Sometimes, we want to talk about a path that ignores the edge directions. These are usually referred to as something like "paths in the underlying undirected graph".)


Alternative formulation of complexity class $BPP$

The subscript to $\Pr$ denotes which random variable the probability is over. In this case the probability is over $r$, which is samples uniformly at random (this is what is conveyed by $\in_R$) from $\{0,1\}^{p(n)}$. You can think of $r$ as representing a sequence of $p(n)$ many random coin tosses.


Average length and entropy of a code from a probabilistic source

$\sum_{x\ne 000} p(x)$ is the probability of at least one 1 in the word. It's easy to break it according the number of ones ($\#1$) in $x$
$$=3 \Pr[\#1 =1] + 3\Pr[\#1=2] + 1\Pr[\#1=3]= 0.488$$

Which is indeed equal to $(1-(p_0)^3)$ as you wrote yourself.

The entropy is being computed similarly. Just plug in $\Pr(x)$ for any possible $x\in \{0,1\}^3$. BTW, your formula is written incorrectly (I assume it is a typo). Should be
$$ H(X) = -\sum_{a_i} p(a_i) \log_2(p(a_i)).$$


Why are blocking artifacts serious when there is fast motion in MPEG?

DCT is both discrete and finite, it has a limited range in both the space and frequency domains. If the change in a certain location is large or the location changes a lot, the results of the transform will be beyond the sampling range in the frequency domain.

Since as you mentioned MPEG is based on blocks, the result of a block with with missing high frequencies, after transform back to the spacial domain, will result in the loss of detail in that block - making the block look flat.

For a more accurate result try Signal Processing Stack Exchange.


mapping function to map the index of Lower triangular matrix

Index of $A_{i,j}$ in $1$-$D$ will be $\frac{i(i-1)}{2} + j$ assuming $1$ based indexing.


Time - Complexity Convex Optimization and Eigen Decomposition

Regarding the eigen-decomposition, often it is enough to just compute the first few eigenvalue/eigenvector pairs. In the case, Krylow-subspace methods can be blazingly fast.

For the convex minimization under linear constraints, the (preconditioned) Uzawa iteration is a typical Krylow-subspace method, which is often not bad. There exist probably more advanced algorithms for this problem now, but http://scicomp.stackexchange.com would be a better place to ask about these.  Also Schur-complement methods, or just parameterization of the linear sub-space might work fine too. And in case the linear constraints is actually a bunch of linear inequalities, a state of the art linear/convex programming solver might be the way to go.


Choose a modelling language, like JuMP, and solve it as a MILP.

An attempt I made with CPLEX solves a random instance ( $n=16$, $max(P)=60000$ ) to optimality almost instantly.

I've implemented the following

$$ max(z)$$
$$ z = \sum_{i=1}^n\sum_{k=1}^n A(i,k) $$

$$   \sum_{k=1}^n A(i,k) =\sum_{k=1}^n A(k,i)\quad \forall i \in [1,n]$$
$$ A(i,k) + B(i,k) = P(i,k)\quad \forall (i,k) \in [1,n] \times [1,n]$$

$$A\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$
$$B\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$


Is the languague L={, M accepts a finite amount of words} decdidable?

The function you defined is not a reduction at all - it may not even stop!
The problem is running $m$ on $w$: can you be sure $m$ wont be stuck in an infinite loop on $w$? you can't.
You can define a proper reduction as follows: (on input $<m,w>$)
Create the machine $M_{m,w}$that does the following algorithm, and return in: (on input $s$)

Emulate $m$ on $w$ for $|s|$ steps. If $m$ halted in that time, reject $s$. Otherwise, accept $s$.

I will leave it for you to prove this is a proper reduction from $H_{TM}$ to $L$ (its a good exercise!)


Formalizing basic category theory in Coq

A natural way to write down what you want is to restrict the type of composition to only the "composable" morphisms:

$$ \mathrm{compose}:\forall f\ g: \mathrm{mor}, t(f) = s(g)\rightarrow \mathrm{mor}$$

adding, of course, the conditions:
$$ s(\mathrm{compose}\ f\ g\ e)=s(f)$$
$$ t(\mathrm{compose}\ f\ g\ e)=t(g)$$

This works, as it now only allows composing functions that are provably composable. This roughly corresponds to the fibered product in category theory you were mentioning.

However is somewhat awkward as it adds proof obligations to every application of compose, which can quickly become unmanageable (even expressing associativity is hard!). Also it somewhat precludes adding the notation $\circ=\mathrm{compose}$, since compose takes 3 arguments.

This is a somewhat common problem in type theory, which results from the fundamental tension of having partial functions in a total language.

Another, less elegant solution, is to define composition to be everywhere defined:
$$ \mathrm{compose} :\mathrm{mor}\rightarrow\mathrm{mor}\rightarrow\mathrm{mor}$$
and guard every theorem involving composition with well-definedness conditions:

$$\mathrm{assoc}:\forall f g h:\mathrm{mor}, t(f)=s(g)\wedge t(g)=s(h)\Rightarrow\\ \mathrm{compose}\ f\ (\mathrm{compose}\ g\ h) = \mathrm{compose}\ (\mathrm{compose}\ f\ g)\ h $$
This essentially means:

  compose is defined everywhere, but the definition is only meaningful if applied to composable morphisms.

This approach also has drawbacks, mostly the gargantuan quantity of proof obligations that follow every application of the basic axioms.

I'm afraid you have to choose your poison in this case, or come up with a clever way to do better...


is conflict possible In accepting state of LR(0)?

I don't think there is a real conflict here.

It does look like a shift/reduce conflict but if you are at
the end of the input there is no ";" symbol that can be shifted so only reduction to S' applies.

There are ways you can deal with things that look like conflicts near the accepting state.

One is to have a pseudo token for end of input.
This distinguishes a parse where you consume all the input from one where you have
unconsumed tokens (garbage) remaining.

If you have a choice between which rules to apply you can have a preference for a reduction to the start symbol and thus to accepting rather than applying further rules.


Mixed Integer Linear Programming application problem

While I can't answer if your model is okay or if it has some subtle flaw, I think I can confirm that general approach works and the issue is with CBC solver.
I reimplemented the game on my own: https://gist.github.com/afish/56d710cf440bf652fa2ea51f356f7378
CPLEX finds solution for city center and 4 houses in 3 seconds. CBC can't do it (I killed it after couple minutes). I imagine the same situation might be with your code.
I don't know what solvers you can use but seems like CBC is not a good choice here. Just for the record, I also tried MIPCL, SCIP, and GLPK - none of them could solve the problem in a reasonable (~seconds) time.


Serializability and the Lost Update Problem

You say:

  serializability ensures consistent states in face of concurrency, though it does not prevent lost updates

This is not true, since by definition the lost update is the phenomenon arising in presence of Write-write conflict, that is when a transaction B overwrites a value written by a transaction A before the commit of A. This operation can lead to a state which cannot arise from any serial execution of A and B.

Consider for instance, in your example, the case in which the transaction T2 is executed one hour after the transaction T1: this could happen in real life, the execution of the two transactions is serial, that is there is no interference between the two transactions, however the update is wrong since someone wrote a bad address. But this means bad data, not data base inconsistency in itself (in other words, you have a database inconsistent with the reality, but this has nothing to do with concurrency and transaction management, that are properties related to the execution of concurrent operations over the database).


The predicate whose truth value you're trying to check states the following:

  For every even number $x$ in the list, $x/2$ is also in the list.

This holds in the first case: the even numbers are $-2,0,2$, and indeed $-1,0,1$ are in the list, but not in the second case, since $4$ is in the list but $2$ isn't.


Are number of states in a NFA same as Pumping length?

Here is a counterexample. Consider the language $L = 1^* + 0^*1^n$. The minimal NFA for $L$ has $n+C$ states for some constant $C$, but every word can be pumped, so the pumping length is 1.


Does an optimal path imply the heuristic is admissible?

No.

Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1.

We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)>1$.

However, using $A^*$ search algorithm, we will end up with the path $s, t$, the unique and, hence, optimal path.

Exercise. Construct a counterexample where there are more than one path.


Why is this function computable in polynomial time?

What $0^{|w|^2-|w|-1}$ is? It is "$0$" symbol repeated $|w|^2-|w|-1$ times. What is time complexity of simply outputting $0$ $|w|^2-|w|-1$ times? Clearly it is $|w|^2-|w|-1$, what is $O(|w|^2)$, i.e. polynomial of length of input.


Solving the Path Explosion Problem in Symbolic Execution

The heuristic approach to solving the path explosion problem picks the next branch to explore based on some function. A simple heuristic function, yet pretty effective, would be to assign the score of a branch based on how many times it has been seen before, and then pick the one with the lowest score. This ensures that branches which haven't been seen yet are explored first instead of getting stuck in a path explosion, whose branches would have been seen many times.


Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2)

An amortized cost is just the average cost of a sequence of $n$ operations (in the worst cases). If I remember correctly, its definition is defined as

$$
\hat c(n) \sim \frac{\sum\limits_kc(k)}{n}
$$

Now,
$$
\hat c(n) = \begin{cases}
2n - 1 & \text{if $n$ is a power of 2} \\
0 & \text{otherwise}
\end{cases}
$$
obviously fits that description. In the same vein, so does
$$
\hat c(n)_{\text{alt}} = \begin{cases}
n & \text{if $n$ is a power of 2} \\
1 & \text{otherwise}
\end{cases}
$$
which is just our original cost function ;)

In fact, many such cost functions exist. However, none of them clearly spells out a tight bound on the cost of any arbitrary instruction.

For example, to say that $\hat c(n) \sim 2n$ is to say that the total cost of $n$ operations is approximately $\sum_k^n 2k = 1 \times n^2$. On the other hand, the true total cost of $n$ operations is
\begin{align*}
\sum_k c(k) &= n + (2^0 - 1) + (2^1 - 1) + \dots + (2^{\lfloor\log_2(n)\rfloor} - 1) \\
&= n + 2^{\lfloor \log_2(n) \rfloor + 1} - 1 - (\lfloor\log_2(n)\rfloor + 1) \\
&\le n + 2n - \log_2(n) - 2 \\
&\le 3n
\end{align*}

This means that a good "amortization" technique here would give an amortized cost of $\hat c(n) = 3$ for any arbitrary $n$.

Now, why is $\hat c(n) = 3$ more "elucidating" than $\hat c(n) = \text{n is a power of 2} ~?~ 2n - 1 ~:~ 0$? Well, because it gives a uniform amortized value for every $n$. This then forms the (unspoken) cardinal rule of amortized runtime analysis:

  Good amortized cost functions are not piecewise.

Why? If $\hat c(n) = \square$ uniformly, then we can easily say that each and every operation is bounded by the same $\square$.

Now, I can definitely hear some readers protest: "but I see case analyses in CLRS itself!" Do you? Well, for algorithms with multiple operations (say PUSH, POP, and MULTIPOP), then we need to give a cost function for each individual operation. However, the amortized cost function given for each operation is "continuous"!

Fret not, this is a pretty common problem. I haven't gone through CLRS myself, but I've stumbled upon these confusions as well when I first went through this technique.

We've already seen that $\hat c(n) = 3$ provides a valid bound, but it doesn't really give us any intuition about the problem (beyond pushing around some inequalities). Why 3? How do we get to that answer without working with (or around) arithmetic and geometric series?

There are good news and bad news. Bad news first: the most general framework you have here is the vague phrase that you already know; just figure out how much you have to pay upfront so you can cover the up to the next "big shock." While this might not seem like very much to work with, it does give us some general intuitions: the important aspect of the problem is not only the magnitude of these shocks (heh), but also their location.

In our case, we know that the location of these shocks are logarithmically distributed, which means that most of the time, you just incur a cost of one. However, these shocks are also pretty big, so you'll need to pay enough up-front to cover for them. In particular, after $2^k$ operations, you'll have to pay at least $2^k - 1$ operations and a further $2^k$ operations. This immediately suggests that $2^{k} + 2^{k} - 1 \le \hat c(2^k)$. Following a similar argument, we also have $\hat c(2^k) \le 2^{k} - k + k \times 2^k$. This refines our bound to $2n -1 \le \hat c(n) \le \lfloor \log_2 n + 1\rfloor n - \lfloor \log_2 n\rfloor$. After this, you can keep refining this bound until you get something as tight as possible. Unfortunately, there's really no way to do this unless you stumble onto the geometric series and realize that $\sum_k^n 2^k = 2^{n+1} - 1$, but at least this should give you a way to make gradual progress in your analysis.

Good luck!


The problem is NP-complete. This rules out an exact algorithm that works in all circumstances, but does not rule out heuristic algorithms that work well in practice, or approximations algorithm with provable approximation guarantees.

The reduction is from 3SAT. Given a 3SAT instance $\phi$ with variables $x_1,\ldots,x_n$ and clauses $\phi_1,\ldots,\phi_m$, construct the following set system. For each variable $x_i$ there are two sets $A_{i,0}$ and $A_{i,1}$ and $N=n+1$ sets $B_{i,t} = \{\beta_{i,t,0},\beta_{i,t,1}\}$, and for each clause $\phi_j$ there is a set $C_j = \{\gamma_{j,1},\gamma_{j,2},\gamma_{j,3}\}$. The set $A_{i,b}$ consists of the following elements:

The $N+1$ elements $\alpha_i,\beta_{i,1,b},\ldots,\beta_{i,N,b}$.
For each clause $\phi_j$ that contains $x_i$ as the $k$th literal and is not satisfied by $x_i = b$, the element $\gamma_{j,k}$.

One can find $n(N+1)+m$ diverse sets if and only if $\phi$ is satisfiable. Indeed, given a satisfying assignment $\vec{x}$, the family $\{ A_i^{x_i} : i \in [n] \} \cup \{ B_{i,t} : i \in [n], t \in [N] \} \cup \{ C_j : j \in [m] \}$ is diverse: $\alpha_i$ belongs only to $A_i^{x_i}$, $\beta_{i,t,1-x_i}$ belongs only to $B_{i,t}$, and if the $k$th literal of $\phi_j$ is satisfied then $\gamma_{j,k}$ belongs only to $C_j$.

For the converse, suppose $\mathcal{S} = \mathcal{A} \cup \mathcal{B} \cup \mathcal{C}$ is a diverse family of size at least $n(N+1)+m$, partitioned according to the type of the set. If $\mathcal{A}$ contains both $A_{i,0}$ and $A_{i,1}$ for some $i$, then $B_{i,1},\ldots,B_{i,N} \notin \mathcal{B}$. Hence $|\mathcal{S}| \leq 2n + (n-1)N + m < n(N+1) + m$, which is impossible. Therefore $\mathcal{B}$ and $\mathcal{C}$ must contain all sets of the corresponding type, and $\mathcal{A}$ must contain $n$ sets, which together encode an assignment $\vec{x}$. Since $C_j \in \mathcal{S}$ is diverse, by construction the assignment $\vec{x}$ satisfies clause $\phi_j$, hence $\phi$ is satisfiable.


find the union of all min cuts of a flow network

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

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


How is a 2-bit predictor better than a 1-bit predictor at determining loop iterations

The assumption is that destructive aliasing (or really any aliasing) is rare. That is, the branch predictor entry is unique to that static branch or at least not shared with another branch that is generally not taken.

If there is no aliasing, a later encounter of the loop will still predict taken for the 2-bit predictor but will mispredict for the 1-bit predictor. (A 1-bit predictor will also lack constructive aliasing with other loops since the previous encounter with the other loop will set the predictor entry to not-taken.)

(The common technique of BTB filtering "never" taken branches (i.e., a BTB miss for a branch that is not taken does not update the predictor and behaves as if no branch was present) can reduce destructive aliasing for taken branches.)

For loop dominated workloads a loop branch is both less likely to alias (fewer static branch instructions, one static branch accounts for multiple dynamic branches) and less likely to have destructively aliasing (constructive aliasing with other loop branches is more likely).

If aliasing were common, branch prediction would not work well because the prediction would not apply to the branch being predicted. (A 1-bit predictor can reduce aliasing by providing twice the number of entries compared to a 2-bit predictor of the same storage capacity. For certain workloads with high static branch count, the tradeoff of number of entries/aliasing and hysteresis may be justified.)


Different feature sets for training and testing?

The answer to the question in the title is no. Most ML algorithms are built around the assumption that the training and test data are drawn from the same distribution. So you should do the same pre-processing and use the same features at train and test time.

That being said, the procedure you describe sounds more like using background knowledge to make the features in the test set more similar to what you saw during training. This certainly seems like a reasonable thing to do and might fall under the heading of Domain Adaptation, when the distribution of the training and test sets change. Unfortunately I'm not familiar enough with the area to say for sure or give you a reference.


CNNs: Why do the filters identify more complex features as the model goes on?

In a convolution neural network, every neuron in layer $i+1$ depends on few neurons in layer $i$. It thus aggregated local information for layer $i$. As you go through the layers, the subset of input that the neuron sees grows, and so the features depend on a larger part of the input. Eventually, neurons depend, in directly, on all inputs.


Why is the laplace transform not popular for image processing convolution?

The Laplacian is indeed used in image processing routinely but, possibly not as much as Fourier transforms. Reasons (other than just the difference in span of uses, narrow vs wider) may be: Fourier transforms have been highly optimized due to their wide application, and are possibly less complicated theoretically than the Laplacian. sometimes the Laplacian of the Gaussian is taken for "blob detection".[2][3]

From the book Digital signal processing fundamentals By Ashfaq A. Khan p105:

  Convolution is the primarily tool in image processing while Laplace Transform is used mainly in signal processing, such as speech and controls systems.

[1] Laplace filter in image processing (with edge detection and motion estimation applications)

[2] Laplacian in blob detection intuition (mathoverflow)

[3] blob detection


Efficient algorithm for detecting overlaps in time intervals

select * from table where end_time > 12.00PM order by end_time

fetch single row, and check if start_time < 12.00PM.


$(Q\to R)\wedge (R\to Q)$ converting to sentence

Your answer and the professor's answer are both correct.  Other ways to say $p$ implies $q$ are: "if $p$ then $q$" and "$p$ only if $q$".  You can replace "only if" by "implies".

Thus, "I have time ONLY IF I will go to town" and "IF I have time I will go to town" both say the same thing - "I have time implies I will go to town".