thread scheduling in multi core architecture

The load balancing or multiprocessor scheduling problem is one of the earliest NP-hard problems for which an approximation algorithm has been developed.  The classic paper is:

  R.L. Graham: "Bounds for certain multiprocessing anomalies," Bell System Technical Journal, 45(9):1563–158, 1966.

In the load balancing problem you are given $M$ identical cores, and $N$ threads.  All the threads are assumed to be available at the beginning, and all the thread run times are given before hand.  Graham proved that list scheduling, taking the threads one-by-one and assigning each one to the machine that currently has the least load is a 2-approximation.  He further proved that Longest processing time (or LPT) scheduling, where you sort the threads in decreasing order of running length before doing list scheduling is a 4/3-approximation algorithm.  See, for example: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/11ApproximationAlgorithms-2x2.pdf

Graham's original result has been extended over the years to cases where there are dependences between jobs (i.e., job $j$ needs to finish before job $k$ starts), and to where each job $i$ is not permitted to be scheduled before a given time $a_i$ (known as the arrival time), and to where the machines have different properties, and the jobs have requirements about what machine properties are required.

In the case where the job lengths and/or arrival times are not known before hand the problem becomes much harder.  This becomes an online algorithm.  The main research I am aware of in this area is for the case where the jobs do have dependences between them, but the dependences are restricted to fork-join patterns.  The work in this area started (afaik) with the paper

  Robert D. Blumofe; Charles E. Leiserson: Scheduling multithreaded computations by work stealing. J. ACM 46(5):720-748, 1999.

(Note that this is called "work stealing", but you should really view the work being stolen as a new, dependent, job, so it actually fits into the non-migratory requirement you specified.)

As to your other question: there has been some work in using type inference to infer program running times, but I don't know that anything practical ever came out of it.  The paper I'm aware of is:

  Brian Reistad; David K. Gifford: Static Dependent Costs for Estimating Program Execution Time, ACM Conf on Lisp and Functional Programming, 1994.


how does the shap algorithm work in polynomial time?

First, some notation.
A decision tree is a binary tree in which each internal node is labelled by one of $x_1,\ldots,x_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with real numbers. To evaluate the decision tree on an input $(x_1,\ldots,x_n) \in \{0,1\}^n$, we just follow the tree from the root to a leaf, and output the value on the leaf. From now on, we fix a decision tree $T$, as well as a reference output $y$.
A decision tree is irredundant if no root-to-leaf path contains the same variable twice. We can easily make a tree irredundant in linear time, and so we assume that $T$ is irredundant. (For some reason, the paper doesn't make this assumption.)
Given a subset $S \subseteq [n]$, let $f(S)$ denote the expect output of $T$ when run on a random input $x$ subject to $x_S = y_S$ (i.e., $x_i = y_i$ for all $i \in S$). Alternatively, it is the expected value of the following process. Start at the root and proceed to a leaf. At any given node, if the node queries a variable $i \in S$, go to the branch labelled $y_i$. Otherwise, take a random branch. Thus $f([n])$ is the value of $T$ on $y$, and $f(\emptyset)$ is the value of $T$ on a random input.
For $i \in [n]$, we define the Shapley value $\phi(i)$ to be
$$
\phi(i) = \sum_{i \notin S} \frac{|S|!(n-|S|-1)!}{n!} (f(S \cup \{i\}) - f(S)).
$$
For the actual algorithm, the coefficients won't matter much. Indeed, we will calculate directly
$$
\alpha_+(i,\ell) = \sum_{\substack{i \in S \\ |S|=\ell}} f(S), \\
\alpha_-(i,\ell) = \sum_{\substack{i \notin S \\ |S|=\ell}} f(S),
$$
from which we can determine $\phi(i)$ using the formula. In the same way, we can compute other power indices, such as the Banzhaf index.
Let $v$ be any node in $T$. Define $\alpha_{\pm}(i,\ell,v,s_0,s_1)$ as the same value as above, when run on the decision tree rooted at $v$, given that we have already put $s_1$ nodes inside $S$, and $s_0$ nodes outside $S$. Thus we are interested in $\alpha_-(i,\ell,r,1,0)$ and $\alpha_+(i,\ell,r,0,1)$, where $r$ is the root of $T$.
If $v$ is a leaf then $\alpha_{\pm}(i,\ell,v,s_0,s_1)$ is just the label of $v$ multiplied by the number of possible sets $S$, which is $\binom{n-s_0-s_1}{\ell-s_1}$. Now suppose that $v$ is an internal node labelled with $x_j$ and having children $v_0,v_1$. If $j = i$ then
$$
\alpha_+(i,\ell,v,s_0,s_1) = \alpha_+(i,\ell,v_{y_i},s_0,s_1), \\
\alpha_-(i,\ell,v,s_0,s_1) = \frac{\alpha_-(i,\ell,v_0,s_0,s_1) + \alpha_-(i,\ell,v_1,s_0,s_1)}{2}.
$$
(In fact, it doesn't matter whether we choose $\alpha_+$ or $\alpha_-$ on the right-hand side.) If $j \neq i$ then
$$
\alpha_{\pm}(i,\ell,v,s_0,s_1) = \alpha_{\pm}(i,\ell,v_{y_j},s_0,s_1+1) + \frac{\alpha_{\pm}(i,\ell,v_0,s_0+1,s_1) + \alpha_{\pm}(i,\ell,v_1,s_0+1,s_1)}{2}.
$$
The actual algorithm in the paper is some sort of mild optimization of this idea.


Doubt regarding binary trees and counting

I think your answer is correct. Without bothering with recursive relations, we can observe that the only semi-balanced binary trees are perfect trees.

In fact, the only semi-balanced binary trees of heights $1$ and $2$ respectively are perfect (obvious for height $1$, casework for height $2$). Now, assume by inductive hypothesis that all semi-balanced binary trees of height at most $n$ are perfect trees. By definition, the root of a semi-balanced binary tree of height $n+1$ must have two semi-balanced subtrees as children, one of which has height $n$. By inductive hypothesis, that subtree is exactly the perfect binary tree of height $n$. By inductive hypothesis and definition of semi-balanced binary tree, the other subtree must therefore be too the perfect binary tree of height $n$, which completes the proof.

We can see that for e.g. $N=7$ the presence of a factor $2$ yields a wrong answer.

Nitpicky thing: you should take the upper integer part of the lower limit of the sum, and the lower integer part of the upper limit.


Yes, consider the graph that consists of vertices $v_1,\ldots,v_{2n}$ and edges $(v_1,v_2),(v_3,v_4),\ldots,(v_{2n-1},v_{2n})$. This graph has exactly $2^n$ maximal independent sets, because for each $0\leq i\leq n-1$, we can either choose the vertex $v_{2i}$ or $v_{2i+1}$.


Here's how to count the models:

There are two options for $a$. Denote the option not chosen by $\bar{a}$ (so if $a = x$ then $\bar{a} = y$, and if $a = y$ then $\bar{a} = x$).
There is one option for $p(a),q(a)$: both have to hold.
There are three options for $p(\bar{a}),q(\bar{a})$.
There are two options each for $b,c$.

In total, we get $2 \cdot 1 \cdot 3 \cdot 2 \cdot 2 = 24$.


Fenwick Tree Traversal using Binary value of Index

Answering Question 2:

Simply count the number of 1's in the binary value.

This is part of the beauty of Fenwick trees, they're very simple to implement. The whole algorithm for finding the sum up to some index i is:

sum = 0
while i > 0:
    sum = sum + f_tree[i]
    i = i - (last set bit of i) // remove last set bit
return sum

At each step, we remove the last set bit from the index. Intuitively, the total amount of iterations is equal to however many set bits there are. You can find this in $O(\log i)$.

Answering Question 1:

Yes you do need to remove the last set bit. That is implicit on the structure of the tree.

Let's say the last set bit of some index $i$ is bit $r$ (e.g. if $r = 0$ it is the least significant bit). The value in the Fenwick Tree at index $i$ is "responsible" for the sum of all values $[(i - 2^r + 1) \dots i]$.

Now let's say index $i$ has set bits $\{r_0, r_1, \dots r_k\}$, that is, $i = \sum_{j = 0}^k 2^{r_j}$. We can then get the sum up to index $i$ in segments (iterations of the sum algorithm). Let $S_n$ denote the range that the accumulating some covers after the $n$th iteration.

$$\begin{align}
S_0 & = [(i - 2^{r_0} + 1) \dots i]\\
S_1 & = [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i]\\
& \vdots\\
S_k & = [1 \dots 2^k] + \dots + [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i] \\
S_k & = [1 \dots i]
\end{align}$$

Example

This may be easier to visualize with an example. Take your first one for instance:

  001100100100100011$_2$ = 51491$_{10}$

I'm not going to go through all the math, I encourage you to do that. This is, in short, how it would work out with a total of 7 iterations.

$$\begin{align}
S_0 & = [51491 \dots 51491]\\
S_1 & = [51489 \dots 51490] + [51491 \dots 51491]\\
& \vdots \\
S_6 & = [1 \dots 32768] + \dots + [51489 \dots 51490] + [51491 \dots 51491]\\
S_6 & = [1 \dots 51491]
\end{align}$$

A lot of this information came from this Topcoder Article on Binary Indexed Trees. I would highly recommend reading it if you have confusion with Fenwick Trees.


What strategy should I use to sovle this interview problem? May I apply DP on this?

This problem is NP-hard. The decision problem, whether a perfect allocation exists, it self is NP-hard. The decision variant is actually the same as the subset sums problem. Given a set of numbers $S$ and a target number $k$, is there a subset of $S$ that sum up to $k$. The problem itself is a variation of the Knapsack problem.

However, the subset sum problem and the knapsack problem are both weak NP-hard problem. Both admit pseudo polynomial dynamic programming solutions (polynomial in the values of the input). So here is a dynamic programming solution for your problem. For each $i \in \{0, \dots n\}$, let us define the function $dp_i : [M] \rightarrow {0, 1}$, where $M$ is the sum of all needs of drugs from all patients. Now set $dp_0(0) = 1$. And for each $i$, we compute $dp_i$ as $dp_i(k)$ equals to 1 if and only if there is a subset of the first $i$ patients that need exactly $k$ units. The transitions are as follows:
$$dp_i(s) = \max\{dp_{i-1}(s), dp_{i-1}(s) - \mathrm{need}(i)\}.$$

An efficient way to implement it is by using bitwise operations on bitsets (a standard trick), where $dp_i = dp_{i-1} | (dp_{i-1}<< \mathrm{need}(i))$, where $|$ is logical or-operator and the $<<$ is left-shifting.


Why is data stored on a flash disk irretrievable if the memory chip is cracked?

The data may well still be there, the problem is that there is no (reasonable) way to get an electrical signal into or out of the data cells.  When you crack a chip you are cracking wires.  The minimum feature size in many chips made these days is around 20nm=200 Angstroms.  I suppose that if you (a) had an electron microscope, (b) knew exactly how the manufacturer had laid out the chip (what every wire means, and what signals need to be sent where to get the data), and (c) had some kind of electron microscope based soldering iron or micro-manipulator with a tip just a few atoms wide, you could laboriously and painstakingly repair all those broken connections.

But, while data recovery companies (the super duper ones) might have electron microscopes, I doubt they have either (b) any access to the manufacturer's layout or (c) a micromanipulator that could actually be used to do the repair.  Also, we're talking about potentially needing to repair thousands of connections, so even if someone were able to do it, they'd probably charge tens or hundreds of thousands of dollars.


The single tape case is known as the Linear speedup theorem. It has a nice little trick by compressing the tape and using overlapping chunks of the tape. Try whether it also works in the two-tape case.


How can I show a linear languages are closed against concatenating with regular ones?

The piece of the puzzle is not to start $L_1$ and $L_2$ in parallel, but to first generate the regular suffix (strings in $L_2$), then (when the left-linear grammar finishes) continue with the linear prefix (strings in $L_1$).

(added, deadline closed) Thus we assume we have grammar $G_i = (\Sigma,V_i,P_i,S_i)$ for language $L_i$, where $G_1$ is linear, and $G_2$ is left-linear, following your own suggestion, and generates the regular language "in reverse".
Given two strings $w_1$ and $w_2$ in the respective languages, having derivations $S_1 \Rightarrow^*_{G_1} w_1$ and $S_2 \Rightarrow^*_{G_2} B w' \Rightarrow_{G_2} w_2$, we glue these together as
$S_2 \Rightarrow^*_{G_2} Bw'\Rightarrow S_1 w_2 \Rightarrow^*_{G_1} w_1 w_2 $. Thus, first generate $w_2$, in the last step switching to the axiom $S_1$ of $G_1$, then generate $w_1$.

Technically this is achieved by requiring $V_1 \cap V_2 = \varnothing$, choosing all productions in $P_1$ and $P_2$ except that "final" productions $A\to a$ with $a\in\Sigma$ in $P_2$ are changed into $A\to S_1a$.


Minimum cardinality graph partition that removes specific edges

Try to look at what happens when all the edges are bad edges.
What would the question be if I asked:

Can you partition the graph into three partitions, e.g. red, green, blue, such that for every edge, the "color" of the endpoints of each edge is "chromatic".

(Let's also make the graph into a complete graph by adding "good" edges between every non-adjacent vertices.)


Learning Specific Topics In Machine Learning

First I'll say, because you didn't mention it, that you also need a strong probability and statistics background.

A good place to start with CNNs is (in my opinion) the highly praised Stanford course:
https://www.youtube.com/playlist?list=PL3FW7Lu3i5JvHM8ljYj-zLfQRF3EO8sYv

If you are looking for more practical stuff (and on more than just CNNs), there are many guides for different machine learning models in Kaggle, where you can also join challenges which you can learn a lot from.
https://www.kaggle.com/

If you are interested in theory, this book might help - but might also be difficult without a strong statistical background:
http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/index.html
(the book is free to download from there)


https://en.wikipedia.org/wiki/Trap_(computing)

It is called a hardware trap because the mechanism of triggering it, and handling it, is embedded in the hardware itself and it cannot be [fully] controlled/disabled in software.


Why can System F1 a.k.a. λ → have kind `*`, but no quantification `∀`?

Why can System F1 have kind *, but no universal types, i.e. quantification ∀?

Because "System F1 has types of kind *" does not mean "any types which have kind * in some other system (e.g. universal types) are allowed in F1".


Gap between numbers in fixed-point vs. floating point arithmetic

Yes, the difference is constant.
It is not really constant, but approximately, yes.  With exceptions.

With binary floating point numbers, the expression $(f(r)−r)/r$ is constant within a factor of $2$.  It is between $1 \over 2^m$ and $1 \over 2^{m-1}$ where m is the number of bits in the mantissa.  For rounding error calculations, you can assume it is constant.

A note on 0:
Obviously, you cannot apply the formula when $r=0$.  But it is important to know that while $f(r)-r$ decreases when $r$ becomes small, $f(0)-0$ is much larger than, for instance, $f(f(r))-f(r)$.  There is a huge non-representable gap around $0$.


I'm unable to add comments but I think this problem can be simplified to:

B = []
for pair in A:
    B.append(pair[0] - pair[1])

min_sum(B, k)

min_sum returns k elements that add up to give the smallest number possible (absolute value). This (at least to me) feels easier to work with.


Approximate Bayesian Computation VS Monte Carlo Simulation

Yes, ABC is a specific application of Monte Carlo method. That application is approximating likelihood functions.

Anything that happens in a computer is actually deterministic. However, ABC, like any other MCM, must have a good pseudo-random generator. There is no difference in the amount of randomness required by the methods.

Examples of Monte Carlo methods which are not ABCs include genetic algorithms and Monte Carlo integration.


Decider for the family of Turing machines that move infinitly to the right on some input

Given a Turing machine $M$ for which such an input exists, what does $M$'s state graph look like?

   For some input $w$, there is a computation of the form $q_0 \leadsto q (\leadsto q)^\omega$ whose transitions all have movement $R$ (or $N$, depending on the meaning of "only"). Therefore, the state graph has to have an "$R$-path" from $q_0$ to some $q$ which lies on an "$R$-cycle".

Is this also a sufficient criterion? The answers to both questions lead you towards a decision procedure.


Would it ever be possible for computer viruses to evolve new "genes" to allow them to perform their job?

I suppose it would be possible in theory, but computer malware (viruses, worms, etc.) typically don't work this way today, and there are good reasons why they're written the way they are.

You might be interested in polymorphic code, which changes itself to evade detection.  It changes the sequence of instructions to some other sequence of instructions that will have the same effect, but will have a different binary.  This helps evade detection by anti-virus tools that are looking for a specific "signature" of bytes.  However, this is not the form of mutation you are asking about, because it will never cause the malware to "evolve" some new behavior it didn't already have.

Really, there is not much reason why malware authors would want or need their malware to evolve new functionality.  They can either build the desired behavior into the malware.  Or, they can have the malware contact a central "command & control" server to download new code ("software updates" for the malware) periodically, to let them control the behavior of the malware.  Usually the bad guys work out offline what attacks they want to mount, and then implement this in the malware or command the malware to perform those attacks.

By working out the attacks offline, in advance, the attackers can test those attacks on their own systems and make sure they'll work properly and won't be detected.  From the attacker's perspective, this is a lot better than writing malware that randomly tries stuff in hopes it'll evolve to a useful attack; malware that tries random stuff will be a lot more likely to set off alarms and be detected.

So, there's not really any need or motivation for using "natural selection" in malware, and it's not typically seen in practice.


Find median of unsorted array in $O(n)$ time

This is a special case of a selection algorithm that can find the $k$th smallest element of an array with $k$ is the half of the size of the array. There is an implementation that is linear in the worst case.

Generic selection algorithm

First let's see an algorithm find-kth that finds the $k$th smallest element of an array:

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

The function split(A, pivot) returns L,R such that all elements in R are greater than pivot and L all the others (minus one occurrence of pivot). Then all is done recursively.

This is $O(n)$ in average but $O(n^2)$ in the worst case.

Linear worst case: the median-of-medians algorithm

A better pivot is the median of all the medians of sub arrays of A of size 5, by using calling the procedure on the array of these medians.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

This guarantees $O(n)$ in all cases. It is not that obvious. These powerpoint slides are helpful both at explaining the algorithm and the complexity.

Note that most of the time using a random pivot is faster.


Checking if two statements can be reached in one control flow

This can be solved with a "context-free reachability" query in a graph.  Each function call corresponds to an open parenthesis, each return corresponds to a close parenthesis, and you want to know whether there is a path in the graph such that the sequence of parentheses formed is properly nested and that traverses those two nodes in order.  If you search on that term you should find papers with algorithms for that problem.

The exact nature of the context-free language depends on how you formulate the question.  Suppose we want to know whether there is a path in the program that respects function calls and returns and visits $u$ and $v$, in that order.  One way is to ask whether there exists a path through the graph that starts at $s$ (the start point of the program), then eventually visits $u$, then eventually visits $v$, and where the word formed by this path is in the Dyck language $L$ of properly nested parentheses, e.g., $S = L(S)$ where $S := \varepsilon | (S)$.  Equivalently, you can ask whether there exists a path in the graph that starts at $u$ and ends at $v$, and where the word formed by this paths in a different context-free language $L'$, namely, the set of all suffixes of words in $L$.  Here $L'$ is context-free, as it can be recognized by the grammar $S' := S | S)$.  This then becomes a context-free reachability query on the graph.  In practice we have multiple parentheses symbols, one per function.  You can find these kinds of details in papers on context-free reachability.


Probability of detecting errors in codewords

I think your approach is fine, but the question is not fully well-defined (unless I'm missing something).

The general error probability is
$$\sum_{i} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$
The questions explicitly says that the error probability of all codewords except $C1,C2,C3,C4$ is negligible, so the error becomes:

$$\sum_{i\in\{1,2,3,4\}} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$

Computing the error probability is easy: if the Hamming distance is $x$, it takes $\lfloor x/2\rfloor +1$ bit-flips (or more) to corrupt the codeword, and $x$ bit-flips (or more?) to be undetected by the receiver. You can easily compute that in a similar way to what you wrote, and get a reasonable bound.
However, the question explicitly says that the terms $\Pr(C_i\text{ is transmitted})$ are unknown, yet it requires you to give an exact numerical answer. contradiction.


why should I go for logistic regression?

If you want to know why your advisor advised you with that advise, you should ask your advisor why he advised you thus, as Yuval points out.

If you want to know what makes logistical regression a good method, it is because it takes as input a data set such as the one you have and it outputs a probability (distribution), which is precisely the input-output format you were looking forit; it is simple, widely available, easy to implement, and in practice, it turns out that they do a markedly good job at predicting real-world data. It is also the last step before curve-fitting turns into AI, because neural networks are really just logistic regression on steroids.

There are other methods because world of data analysis is big. You are looking for a classification model. For example, you can use a Bayesian learning algorithm, such as Naive Bayes or Pearl's algorithm. Weka is a freely available software toolkit with 100 (+/- 50) different classification algorithms. It is quite user-friendly. If your data set is large and complex enough, you can consider letting loose a true AI, such as a neural network, or a Deep Learning machine. All these things are freely available.


How many times can you pour milk among 3 buckets?

Since the total amount of water is C liters (C being the capacity of bucket C), the number of possible states is at most the number of non-negative integer solutions of $x+y+z = C$, which is $\binom{C+2}{2}$. Any sequence of moves longer than that must repeat a state. Therefore it is enough to recurse up to level $\binom{C+2}{2}$.


Basic question about 4-way set associative

Four way set associative does not mean 4 sets.

It means each set is of 4 blocks.

Individual block can be read or written.

Go through this document for understanding the concept of set associative cache.


Universality is a somewhat informal notion. What it roughly means is that for each computable function $f$ there is a "program" $P$ in the model so that "running" $P$ on any input $x$ always "halts", and "outputs" the correct answer. (Note that Turing machines don't make an appearance here: they are just one example of a universal computation model.)

The quoted words are those that need to be defined. For Turing machines:

A program is specified as a list of states, a tape alphabet, an initial state, final states, and transitions.
Running a Turing machine $T$ on an input $x$ means that we initialize the tape with an encoding of $x$ and run the machine $T$ on this tape according to the usual rules.
A Turing machine halts if it reaches a final state. (There are some variants here.)
What the Turing machine outputs (if it halts) is the contents of the tape.

Rule 110, as a computation model, needs to be defined formally in the same way. A definition is reasonable if one can computably simulate the computation model, in the following sense: there is a computable function $S$ such that for every program $P$ and input $x$ (both encoded as natural numbers), $S(P,x)$ halts iff $P$ halts on $x$, and if $S(p,x)$ halts then its output is identical to the output of $P$ on $x$.

If you're curious as to the particular setup of Rule 110 as a computing system, I suggest you take a look at Matthew Cook's paper which proves the universality of Rule 110 (or rather, of a computing system built around Rule 110).

As for other rules, such as Rule 30 and Rule 90, we don't know that they are not universal. There might be convincing computing systems built around them which is universal, but we are just not aware of any.


Is the set of codes of Deterministic Finite-State Automata a regular language?

This answer is, in a sense, a completely cheating approach, but it is indeed possible to encode all DFAs as strings.

We can write out a DFA by writing out its transition table.  We can write out the transition table using just 0s and 1s as follows: first, write out a number of 1s equal to the number of states, then a 0.  Then, write out a number of 1s equal to the number of symbols in the alphabet, then a zero.  Then, write out each row of the transition table by writing out each entry as a number of 1s indicating which state should be transitioned into, then a 1.

Now, this particular encoding of a DFA is not regular.  However, what we can do is the following.  Consider the set of all such encodings.  We can then order them in length-lex order, and then can number the DFAs produced this way 0, 1, 2, 3, 4, ..., etc. based on their ordering.  In this case, we now have a bijection between $\mathbb{N}$ and the set of all DFAs.  From there, we can then consider the regular language consisting of all natural numbers written out in binary.  This set is definitely regular; here's a regular expression for it:

  0 | 1(0|1)*

So we now have a regular language consisting of encodings of DFAs.  The encoding is not at all easy to work with - you'd have to start listing off all encodings of DFAs until you found the one you were looking for - but mathematically it is well-defined.


I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with.

Because bitwise operators treat bits independently, you can try to fix each bit in your answer, iteratively, from highest to lowest. The first question is "can I not have the highest bit set to 1 in my answer?". If after removing all edges with the highest bit set to 1 from the graph, the source and destination are still connected, the answer is yes, you throw away all those edges for good and proceed with the next bit. If the answer is no, you put the removed edges back, because they might come in handy, and again proceed with the next bit.

Running time is $O(Elog MaxCost)$.


For a more general reduction, László Lovász [1] proved that

COLORABILITY reduces to 3-COLORABILITY

The COLORABILITY problem is defined as follows:

Input: A graph $G$ and a positive integer $k$.
Problem: Is $G$ $k$-colorable?

That is, the reduction given by László Lovász is applicable to any $k$ ($k \ge 4$).
However, this reduction is quite intricate. You can find an excellent explanation by Vašek Chvátal here. Please free feel to ask if you have some difficulty in understanding this reduction.

[1] Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973.


What is meant by the term "prior" in machine learning

Put simply, and without any mathematical symbols, prior means initial beliefs about an event in terms of probability distribution. You then set up an experiment and get some data, and then "update" your belief (and hence the probability distribution) according to the outcome of the experiment, (the posteriori probability distribution).

Example:
Assume we are given two coins. But we don't know which coin is fake. Coin 1 is unbiased (HEADS and TAILS have 50% probability), and Coin 2 is biased, say, we know it gives HEADS with probability 60%. Mathematically:

Given we have HEADS, the probability that it is Coin 1 is 0.4 $$p(H | Coin_1) = 0.4$$ and probability it is Coin 2 is 0.6 $$p(H| Coin_2) = 0.6$$

So, that is all what we know before we set up an experiment.

Now we are going to pick a coin toss it, and based on the information what we have (H or T) we are going to guess what coin we have chosen (Coin 1 or Coin 2).

Initially we assume $p(Coin_1) = p(Coin_2) = 0.5$ both coins have equal chances, because we have no information yet. This is our prior. It is a uniform distribution.

Now we take randomly one coin, toss it, and have a HEADS. At this moment everything happens. We compute posterior probability/distribution using Bayesian formula:
$$p(Coin_1 | H) = \frac{p(H | Coin_1)p(Coin_1)}{p(H | Coin_1)p(Coin_1) + p(H | Coin_2)p(Coin_2)} = \frac{0.4\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.4$$

$$p(Coin_2 | H) = \frac{p(H | Coin_2)p(Coin_2)}{p(H | Coin_1)p(Coin_1) + p(H | Coin_2)p(Coin_2)} = \frac{0.6\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.6$$

So, initially we had $0.5$ probability for each coin, but now after the experiment our beliefs has changed, now we believe that the coin is Coin 1 with probability 0.4 and it is Coin 2 with the probability 0.6. This is our posterior distribution, Bernoulli distribution.

This is the basic principle of Bayesian inference and statistics used in Machine learning.


How is the complexity of algorithms to solve 3CNF (decision problem) specified?

An algorithm runs in polynomial time if its running time on an input $x$ is $O(|x|^k)$ for some $k$. Here $x$ is a (without loss of generality, binary) string, and $|x|$ is the length of $x$.

For 3CNF it also makes sense to consider the running time as the number of different variables. This is because if there are $n$ variables then there are $O(n^3)$ different clauses. The hardest 3CNF to solve are those in which no clause appears twice, and for such 3CNF, the size of the 3CNF (as a binary string) is polynomial in $n$. Therefore for such 3CNF, an algorithm is polynomial in the input size iff it is polynomial in the number of variables. An additional easy argument shows that 3CNF can be solved in polynomial time in the input size iff it can be solved in polynomial time in the number of variables.


Can we build computer without instruction pointer register (PC/IP)?

One possible thought could be a data-flow architecture.

Here the various processing elements are wired together to implement the desired algorithm and rather than an IP register, each processing element (add, subtract, multiply, and, or, compare etc) acts when data is presented.

This sort of things is mostly seen today in fast algorithms embedded in FPGAs. I understand, but have no direct info, that crypto-currency miners are designed along these lines.

So, is this still a computer? Well. oddly enough, a popular way to program these machines uses "C" source code to describe what needs to be done and a sophisticated compiler to design the data-flow machine needed to get the job done.

On a similar note, the LabView programming environment presents a similar model with interconnected elements driven by the data and not an instruction address concept.


$A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

Got it. The question makes it seem more complicated than it really is.

Let $M$ and $N$ be TMs that recognize $A$ and $B$, respectively.
Construct an enumerator $E$ that behaves as follows:

For each $s_i \in \Sigma^*$ (in lexicographic order):
Run $M$ and $N$ on $s_i$ simultaneously. It must be the case that $s_i$ is in at least one of $A$ or $B$. So, at least one machine is guaranteed to halt.
If $M$ halts, $s_i \in A$, which means certainly $s_i \not\in \overline{A} \cap B$, so print $s_i$.
If $N$ halts, $s_i \in B$, which means certainly $s_i \not\in A \cap \overline{B}$, so do not print $s_i$.

So $E$ prints at least all the strings in $A \cap \overline{B}$, and definitely does not print strings in $\overline{A} \cap B$.
$E$ enumerates a language in lexicographic order, so its language is decidable and satisfies the conditions.


The idea is to use a hybrid argument. Let us first write a formula for the new PRG:
$$
G(x) = G_1(G_{3,1}(x)) G_2(G_{3,2}(x)),
$$
where $G_3(x) = G_{3,1}(x) G_{3,2}(x)$.

Suppose that we could distinguish between $G(U_k)$ and $U_{4k}$, where $U_n$ denotes $n$ random bits. Consider the following sequence:
$$
G(U_k); G_1(U_k) G_2(U_k); U_{2k} G_2(U_k); U_{4k}.
$$
By assumption, we can distinguish between the first distribution and the last distribution. Hence we can distinguish an adjacent pair of distributions.

If we can distinguish $G(U_k)$ and $G_1(U_k) G_2(U_k)$, then this gives a distinguisher for $G_3$.
If we can distinguish $G_1(U_k) G_2(U_k)$ and $U_{2k} G_2(U_k)$, then this gives a distinguisher for $G_1$.
If we can distinguish $U_{2k} G_2(U_k)$ and $U_{4k}$, then this gives a distinguisher for $G_2$.

By assumption, $G_1,G_2,G_3$ are all secure, so we obtain a contradiction.


Does the callback concept of programming have any basis in computer science?

(I might be wrong, but this is my understanding.)

Callbacks, especially as seen in JS, are analogous to a semantic model known as Continuation-passing style (CPS). In CPS, a program’s flow is modeled as a series of functions, each of which takes in a continuation, and calls the continuation with the function’s result when finished.

As stated, this is also a form of higher-order programming, where functions are used as values.


Suppose that $L$ is regular. Then so is $L' = L \circ \{ccc\} = \{a^3 b^n c^n \mid n \ge 3\}$. This implies that $L'' = (aaa)^{-1}L' = \{b^n c^n \mid n \ge 3\}$ is also regular and, in turn, that $L''' = L'' \cup \{\varepsilon, bc, bbcc\} = \{b^n c^n \mid n \in \mathbb{N}\}$ is regular. This is a contradiction since $L'''$ is known not to be regular.


Is there a known method for constructing a grammar given a finite set of finite strings?

This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature.  See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, https://cstheory.stackexchange.com/q/27347/5038.

For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, Smallest DFA that accepts given strings and rejects other given strings, Are there improvements on Dana Angluin's algorithm for learning regular sets, and https://cstheory.stackexchange.com/q/1854/5038.


Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class

A rich man walks into a bar and says, "I can buy this beer because I am a millionaire." Eloo says, "The beer costs \$5. I don't understand why this millionaire can buy it, but this guy with five dollars can't."

Remember that $\mathrm{DTIME}[f(n)]$ is the class of languages that can be decided by a deterministic Turing machine that uses at most $f(n)$ steps on any input of length $n$. So, since $t_1\log t_1\leq t_2$, anything in $\mathrm{DTIME}[t_1\log t_1]$ is in $\mathrm{DTIME}[t_2]$.


Turing machines moving left at least once

Let's assume for simplicity that at each step, the head moves either left or right (but doesn't stay in place).

Suppose that $M$ never moves its head left when run on $w$.
After the machine traverses the length of $w$, it reaches a blank cell, and from this point on, will always fall on a blank cell. Therefore the only information that changes from step to step is the current state of the machine. After at most $|Q|$ steps (where $Q$ is the set of states), the machine will either halt or repeat a state, in which case it enters an infinite loop.

This gives a simple algorithm for deciding your language, that I'll let you spell out.

If the head is also allowed to stay put, the argument becomes a bit more complicated, but the conclusion is identical.


Briefly, the answer is no, we cannot construct minimum spanning tree for an un-directed graph with distinct weights using BFS or DFS algorithm. This post provides a counterexample.

Computing MST using DFS/BFS would mean it is solved in linear time, but (as Yuval Filmus commented) it is unknown if such algorithm exists. However, there is an expected-linear-time randomized algorithm computing the MST.


Does left factoring CFG make it unambiguous?

The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is

$$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$


Yes. Using L'Hospital:

$\lim_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^{k-1} (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdots  2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \frac{k!}{\sqrt n} = 0$

I hope I got it right, quite some time since I've used it. I^ve left out the $\frac{1}{2}$ from the $\sqrt n$


Looking for a contex-free grammar for the following language

Hint: you want to measure size of $x$ and $y$, and still have the sum of the two in the end. so when you read them, you will need twice their size: one for $x'$, and one for $z$.
Start with designing a PDA, it seems easier than a grammar.
Then you can use a PDA-to-grammar translation to get the wanted grammar.


Polynomial Identity Testing Evaluating a polynomial on a circuit

If you're working over $\mathbb{Z}/p\mathbb{Z}$, you don't have to do anything: the intermediate results can't get larger than $p$.

If you're working over $\mathbb{Z}$, the standard trick is to pick a random $k$-bit prime $p$ and then reduce everything modulo $p$, so you are effectively working over $\mathbb{Z}/p\mathbb{Z}$.  One can show that the probability of getting a wrong answer using this method is exponentially small in $k$ (using the prime number theorem).

If you're working over $\mathbb{Q}$, you can reduce this to working over $\mathbb{Z}$ by clearing all fractions.


On complexity of the sieve, start crossing at the square of p - Part II

The sum only goes up to $\sqrt{n}$. You can see that in the big display at the bottom of page 3, where only the first $\pi(\sqrt{n})$ primes are considered. Substituting $\sqrt{n}$ for $n$ in your formula, we get $n/\log n + O(n/\log^2 n)$.


Given a Turing machine $M$, we can construct an LBA $B$ which on input of length $n$ checks whether $M$ halts on the empty input within $n$ space. Therefore $L(B)$ is empty iff $M$ doesn't halt.


Enumerable disjoint subsets whose union is equal to the union of the sets

This answer assumes that enumerable means recursively enumerable.

Here is an enumerator for $C$:

Run enumerators for $A,B$ in parallel.
Whenever the enumerator for $A$ outputs a word, check whether the word has already been enumerated by the enumerator for $B$; if it hasn't, output it and continue.

The enumerator for $D$ is defined symmetrically.


What will a given CPU architecture do in the event that we were to invert all of the instruction bits to a given instruction?

If you are decoding instructions using logic based on individual bits in the opcode, this "inversion' scheme is probably counter productive.  If the opcodes are decoded using a simple table lookup of the "value" of the opcode, then the actual pattern of the opcode is just arbitrary and the inversion scheme is just as valid as one based on the alphabetic order of the mnemonics.
For stack based machine, variable length opcodes could be more valuable, shorter opcodes for push, pop, and any immediate value instructions to give more space for address or data bits.
Self-modifying code has been out of fashion for decades, so being able to flip the meaning by inverting the bits would seem to have no utility.


A subgraph of a graph $G$ is any graph that has a subset of $G$'s vertices and a subset of its edges.  In particular, for an graph $G=(V,E)$, the graph $(V,\emptyset)$ is a subgraph that's not connected.


Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method


Study the proof of the pumping lemma for context-free languages. The pumping property is obtained by finding a repeated non-terminal on a path in the derivation tree. By looking at the first repetition you can find a bound on the length of that path in the tree, and hence a bound on the length of the substring $uvyz$.

What is k?


Given a functor $F:Set\to Set$, an $F$-algebra is just a function $f:F(X)\to X$, where $X$ is some set known as the carrier set.

In your example, $X$ is the set of elements of some group.

The endo functor $F$ in this case is $$F(X)=X\times X+X+1.$$
Think of this as representing the three different operators.
The first component of the sum, $X\times X$, captures the arguments of $*:X\times X\to X$.
The second component, $X$, captures the arguments of $∼:X\to X$. The third component, $1$, captures the constant $e:1\to X$ – the $1$ represents a set with one element, thus the function $e$ picks out a single element of $X$.

To understand why these components are summed together, recall that there is an isomorphism $(A\to X) \times (B \to X) \equiv (A+B)\to X$ (where $+$ is disjoint union of sets).

The three functions above can be seen as an element of the set given by the product of their signatures: $$f=(*,∼,e):(X\times X \to X)\times (X\to X) \times (1\to X).$$ Using the isomorphism, we can find an equivalent function  $$f':(X\times X + X + 1)\to X,$$ which is $F(X)\to X$. Thus, an $F$-algebra.

To capture the notion of a group needs additional equations (the expected ones), which falls outside of the basic definition of an $F$-algebra, but are added in a trivial way.

Googling "Universal Algebra" will find you some online textbooks/notes. I'm not sure which ones are good.


Effect of value of k in K-Nearest Neighbor

There is no simple answer.  The standard approach to choose $k$ is to try different values of $k$ and see which provides the best accuracy on your particular data set (using cross-validation or hold-out sets, i.e., a training-validation-test set split).

Intuitively, $k$-nearest neighbors tries to approximate a locally smooth function; larger values of $k$ provide more "smoothing", which or might not be desirable.


What is the difference between "deadlock prevention" and "deadlock avoidance"

It seems that deadlock prevention and deadlock avoidance are two names for the same concept. Indeed, the Wikipedia section on deadlock avoidance has been marked as redundant. While the distinction might be taken from the literature, some people at least are arguing that this distinction is superfluous. See the paper The classification of deadlock prevention and avoidance is erroneous by Neumann Levine, which is mentioned in the Talk part of the Wikipedia article.


Radix sort sorts numbers by sorting on the least significant digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the most significant digit first.

The key point to radix sort is that the digit sorts used in each iteration of radix sort are stable: numbers (digit here) with the same value appear in the output array in the same order as they do in the input array. Given this, you can convince yourself of the correctness of radix sort by simply observing how a set of two-digit numbers are sorted. (Actually, we are using mathematical induction on the number of digits. However, a simple example with a set of two-digit numbers suffices here.)

In the first iteration, the numbers are sorted by their least significant digits. Now consider the second iteration which then sorts these numbers by the leftmost digits. Given two number $a = a_1 a_0$ and $b = b_1 b_0$, if $a_1 \neq b_1$, then after the second iteration, they are in the right order. If $a_1 = b_1$, then we know that the order between $a$ and $b$ should be consistent with $a_0$ and $b_0$. This is the case because the digit sort used by the second iteration is stable.


It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".

The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.


MinHash already is super-fast.  I suggest you check whether you understand correctly how MinHash works.

Take any standard hash function $H$; then all you have to do is compute $H$ once on each element of the set.  You can implement $H$ with as fast a hash algorithm as you want.  The update operation requires one call to $H$ (namely, if your set's hash is currently $y$, and you add element $x$, the new hash is $\min(y, H(x))$), and the union operation is super fast (namely, the union of two sets with hashes $y_1,y_2$ is $\min(y_1,y_2)$).  Notice that these operation have the property you want (adding an element already in the set does not change the hash).

I have a hard time imagining how you could get much faster than that.

If you want this to be faster, a reasonable way is to choose a $H$ that is faster.

I've described a variant where the hash of a set is the smallest of the element-hashes.  The only downside is that the number of hash collisions might higher than you like.  Measure and see if that is actually a problem in practice.  If it is, you can consider variants that keep the $k$ distinct smallest element hashes.  If $k$ is large, you can store those $k$ hashes in a heap of size $k$ to make the update and union operations faster.


Give an example of a non-regular language $L$ such that $L^*$ is regular

Define $L=\{a^nb^n|n\in \mathbb N\}\cup \{a,b\}$

It's not hard to see that while $L$ is not regular, $L^*=\Sigma^*$.


Here is the original statement in CLRS.

  Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$.

It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush or subconsciously. It is good enough in most situations. I would encourage you to keep this primitive understanding, as it may help forming the most compact and natural representation of knowledge in your mind.

Should we read aloud that notation, we can say "$w$ from $E$ to $\Bbb R$" or "$w$ from capital $E$ to bold $\Bbb R$" literally. Adding a bit of interpretation, we can also say, "function $w$ from edges to real numbers", "function $w$ that maps each edge to a real number", or, even more explicitly, "function $w$ whose domain is the set of edges and whose codomain is the set of real numbers".

While the simple and natural understanding, "an edge has a weight", is probably enough to understand the setup for that section of the book, that mathematical notation has some distinct advantages.

In general, although expressive and colorful, natural languages or thoughts, are more complex and abound with ambiguity and arbitrary vagueness. If "an edge $(u,v)$ has a weight $w$", is weight something like "2 miles", "5.0 dollars", or "approximate 7.7 pounds"? Could the edge $(u,v)$ also have an extra weight? Should I use the same symbol $w$ for the weight of edge $(u,v')$ that is not edge $(u,v)$? While these questions may or may not pose a problem for you, it might for other readers of the book.

On the other hand, the notation "$w: E\to\Bbb R$" defines exactly what is the domain, codomain and the kind of correspondence of a relation. To be pedantic, it means the symbol/entity $w$ associates to every element of $E$, i.e, an edge of $G$ exactly one element of $R$, i.e, a real number. There is no room to err.

Moving down the road, page 648 of the book presents the following formula.

  $\begin{aligned}
w(T') &= w(T)  - w(x,y)  + w(u,v)\\
      &\le w(T)
\end{aligned}$

If you try to express the facts embodied in the above formula in plain English, more than two or even five times longer statements may be needed to attain the same rigor and clarity. The result can hardly be more visually appealing. That is how the notation $w:E\to\Bbb R$ shines.

The power of mathematics notations, including notations in computer science, is what you would like to master if you want to dive further into the mathematics, computer science and many other subjects where symbolic computations are needed and useful. In a sense, notations like this are beautiful data types. You can get familiar with them. You can become comfortable with them.


Is radix sort really O(n) for sorting 32 bit integers?

You can choose $k = 1$ and then the time is $\Theta(32(n+2)) = \Theta(n)$ and the space is $\Theta(2n + 2) = \Theta(n)$. In general, if you replace 32 by any fixed number, the complexities will be $\Theta(n)$. If, however, you try to use radix sort with integers of non-constant width $m$, the complexities will be as stated (with $32$ replaced by $m$), or even worse, since you are assuming that operations on these integers take constant time, which might not be the case for integers of arbitrary size (depending on your computation model).


Dynamic programming, coming up with an algorithm

For each $m$, let $\sigma(m)$ be the maximum sum of non-adjacent values among the first $m$ values of the array $A$. Then:
$$
\begin{align*}
&\sigma(0) = 0, \\
&\sigma(1) = A(1), \\
&\sigma(m) = \max(A(m) + \sigma(m-2), \sigma(m-1))
\end{align*}
$$
As an exercise, now try to solve similar problems in which you slightly modify the constraints. For example, suppose that if you select an element then you are not allowed to use $a$ elements before or after it; or that among any $b$ adjacent elements, you are allowed to choose at most $c$.


DP - Removing contiguous subsequences from a sequence optimally

First collect the consecutive alphabets together. Say the input string is "1110000110100" then I mean form the array $A=\{(3,1),(4,0),(2,1),(1,0),(1,1),(2,0)\}$ where an element (  called chunk ) of $A$ $(a,b)$ means there are $a$ consecutive $b \in \{0,1\}$. Now the problem has been reduced to removal of chunks and we will concern ourselves with $A$ rather than the original string.
Now make a DP table $D$ where $D[i][j][k]$ means least number of steps used to removed all chunks till $A[i]$ such that last chunk removed was of $k \in \{0,1\}$ and the size of the last chunk removed was $j$. If it is not possible assign it $\infty$ ( take care of the boundary cases and initial condition for table $D$ ).
Now say you are at chunk $i$ and it is a chunk made of 0's and it's size is $t$. Now you have to fill the table $D[i][][]$ given that you have already filled the tables $D[1][][],D[2][][]......D[i-1][][]$. You have two options (a) If $t \ge K$ remove this chunk first and now you are left with subproblem with $A[1]...A[i-1]$; (b) or if its possible to remove the chunks of 1's before , and then if the chunk of 0's get's size greater than equal to $K$, you can remove it ( rwe will take minimum of all cases while filling the DP table ).  As you asked for only hint I leave it upto you for coming up with the recurrence relation.

As you said $N$ and $K$ are small, I think this method would suffice.


How do I go about constructing a game tree that does not duplicate any states?

Instead of a tree you use a game graph. You maintain a set of nodes (your game states) and, if you need them, a set of edges you already explored. Each time you want to explore a new edge you check whether it leads to a node in your set of nodes. If it doesn't you just found a new node and have to add it to the set.

Your programming language of choice probably provides an efficient data structure for sets already. If it doesn't, you can use a Hash Map or a Search Tree.

However, for non-toy games (a strange concept, games that are not toys...) I don't think that this will buy you anything. The state space is huge and you can't store any significant part. A small cache of some $k$ states might still work though.


Simple proof for NP-completeness of Edge Dominating Set

I assume that you only want to show the minimum edge dominating set problem is NP-complete for the general graph (i.e., you don't care about what properties the constructed graph has).

In case you missed it, there is an arguably simpler reduction from 3-SAT in the same paper (see Theorem 2). The reduction assumes no further "specialist" knowledge. You can make the presentation even slightly easier by skipping verification of bipartiteness and boundedness of the maximum degree of the resulting graph.


Asymptotic relation between n! and (n+1)!

I am afraid that you could have been more careful.

  I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$.

By L'Hospital's rule we have $$\lim_{n \to \infty} \frac{(n+1)!}{n!}=\lim_{n \to \infty} (n+1)=\infty\,,
$$ which means $(n+1)! = \omega(n!)$, or what is equivalent, $n! = o(n+1)!$. Note that both $(n+1)! = \Omega(n!)$ and, what is equivalent, $n! = O(n+1)!$ are correct, which are, however, less precise.


Transforming SAT to Quadratic Programming in polynomial time

The reduction of SAT to quadratic programming is pretty simple. The idea is that we can use the quadratic objective to "force" the variables to be Boolean, and so we can implement an integer linear program whose feasibility is equivalent to the SAT instance.

Given a SAT instance on a set of variables $x_1,\ldots,x_n$, we define the following quadratic program:
$$
\begin{align*}
& \min \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 \\
\text{s.t.} & \\
& 0 \leq x_i \leq 1 & 1 \leq i \leq n \\
& x_{i_1} + \cdots + x_{i_j} + (1 - x_{k_1}) + \cdots + (1 - x_{k_\ell}) \geq 1 & \forall \text{ cl. } x_{i_1} \lor \cdots \lor x_{i_j} \lor \bar{x}_{k_1} \lor \cdots \lor \bar{x}_{k_l}
\end{align*}
$$
The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x_i \leq 1$, a solution is $0,1$ if and only if $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 = 0$, and for any other solution $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 > 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).


Which number representation takes the largest amount of memory?

The question seems rather bizarre.

Using n bits, each representation can represent $2^n$ different values. Two of them have different representations for +0 and -0. I would assume that signed-magnitude and one's complement are used if someone values the ability to distinguish +0 and -0.

If the question was "which representation takes the largest amount of memory", then that question is already nonsense because no matter what you think about +/- 0, one's complement and signed magnitude are the same. If the question was "which representations take the largest amount of memory", then I'd still say that claiming one (or two) take more than the others is very misguided.

(And the number $-2^{n-1}$ that can be represented with n bits two's complement or signed magnitude has its own problems where both negation and division can lead to overflow).


Let us call your problem as $\mathsf{RESVC}$. $\mathsf{RESVC}$ is NP-Complete.

Given a subset $S \in L$ its easy to verify in poly. time whether it forms a
valid cover of size k. Hence, $\mathsf{RESVC} \in \mathsf{NP}$
$\mathsf{RESVC}$ is also NP-hard because the decision version of the Minimum Dominating set problem reduces to it. And, we know that the decision version of Minimum Dominating set is NP-complete. The reduction goes as follows:

$\qquad \displaystyle \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET} = \{ \langle G,k \rangle : G \text{ has a dominating set } S \text{ s.t. } |S| \leq k \}$

Reduce the instance $\langle G,k \rangle$ of above language to $\langle G',k \rangle$ as follows:

Lets say $G = (V,E)$ and $V = \{v_1,v_2,\dots,v_n\}$ and define $G' = (L \cup R, E')$ with

$L  = \{v_{11},v_{21},...,v_{n1}\}$
$R  = \{v_{12},v_{22},...,v_{n2}\}$
$E' = \{(v_{i1},v_{j2}) : (v_i,v_j) \in E \vee (v_j,v_i) \in E\} \cup \{(v_{i1},v_{i2})\}$

Now, it is easy to see that $\langle G',k \rangle \in \mathsf{RESVC}$ if and only if $\langle G,k \rangle \in \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET}$.


1) Usually any accessed data are saved into L1, independent whether they were previously available in L1, L2... or memory only.

For exclusive cache, data are stored ONLY in L1, for inclusive one, in the entire hierarchy. There are also mixed strategies. Also, some CPUs have "victim cache", which is extra cache level which gets ONLY data moved out of LLC (last level cache).

2) Yes, for write-back exclusive cache.

3) You misunderstood his explanation. He said that data are fetched and placed to both caches. Inclusion, btw, isn't the "bit set", but entire cache policy. The policy is built right into the hardware.

4) Exclusive cache better use precious space, but each time you have to bring new block into L1, you have to displace some block to L2, then some one to L3... and finally some one to memory. This means a lot of work. With inclusive cache, you just drop data from L1 cache, or replace older copy in L2 with newer copy displaced from L1.

As result, exclusive strategy is more optimal when adjacent cache levels has closer sizes (f.e. <=4x) and inclusive is better when sizes are very different.

More info at en.wikipedia.org/wiki/Cache_inclusion_policy


How to give a context free grammar for any given language ie: a^n (ba)^m a^n

The reference question "How to prove that a language is context-free?" has some examples to build a context-free grammar using a simple toolbox. As is mentioned there one needs a "nesting structure" to make this work.

You ask about the difference between language like $L_1 = \{ab^na^nc \mid \dots \}$ and $L_2 = \{a^n (ab)^m a^n \mid \dots \}$. In both cases the parts that are iterated the same $n$ number of times have to be generated in parallel. Productions like $Y\to b Y a$ are good for that.

In case of $L_1$ the $a\dots c$ pair is around the repeat $b^nc^n$ and can be generated before $S\to a X c$, but also independently as $S\to AXC, A\to a, C\to c$  .
In case of $L_2$ the $(ab)^m$ is inside the repeat $a^n\dots a^n$ and has to be generated after, like your own solution $S\to aSa, S\to X, X\to abX\mid \varepsilon$.


How is pre-computation handled by complexity notation?

I understand that you have some computational problem with input size $n$, and you use $f(n)$ time for preprocessing. Perhaps after that, you can answer some kind of queries in $g(n)$ time. Both $f$ and $g$ are functions of the input size, and you can now apply Big Oh and say, for instance, that $f(n) = O(n^2)$ and $g(n) = n$.

Now, nobody is forcing you to "consider the runtime to be $O(n)$" or anything like that. So why not just say it like it is, e.g., "after a $O(n^2)$-time preprocessing step, queries can be answered in $O(n)$ time", or "there is an $O(n^2)$-time algorithm for solving the problem", or whatever it is precisely that holds. It's up to you how you present it.

In particular, I want to clear the misconception that "big O would consider one 'run' of the algorithm". If you look at the definition of Big Oh, you'll see that it says nothing about algorithms or their "runs".


What's the true meaning of $(a + b)^\omega$ in regular expression

The notation is standard but it's an omega ($\omega$, the first infinite ordinal; basically, the infinity in "There are infinitely many natural numbers"), not a $w$ (the 23rd letter of the Latin alphabet).

Both as a closure operator applied to languages and as an operator in $\omega$-regular expressions, $^\omega$ is directly analogous to ${}^*$, except it denotes the concatenation of infinitely many things, rather than any finite number of them.


A Question about what it means to Compare two Vectors

Yes, element-wise comparison is the usual convention for these constraint problems.


Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

No, "it doesn't make sense". You are correct in the sense that that choice is not a logical consequence of any requirements and known truths. It could be considered as arbitrarily selected.

Well, we do not need to make any sense when we are forced to decide which one of two global timestamps, $(T_i,i)$ and $(T_j,j)$ where $T_i=T_j$, is earlier than the other one, as long as our choices are consistent, so that we will be able to arrive at a total ordering that respects the local ticks. There are indeed many different ways to decide that can lead to many different total orderings.

What does it mean by "choice being consistent"? Here is a simple example. Suppose we have three global timestamps, (1,5), (1,2), (1,4). It is consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,5) $\prec$ (1,4). However, it is not consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,4) $\prec$ (1,5). Intuitively, if (1,5) precedes (1,2) and (1,2) precedes (1,4), then (1,5) must precedes (1,4). That is, the transitivity of $\prec$ must be respected; otherwise, $\prec$ is not a partial ordering any more. The transitivity of temporal
ordering of events is the essence of time.

Among many schemes to decide which global timestamp is earlier in a pair of two global timestamps with the same local timestamp, the easiest and most natural one is the one specified in the paper. That is, $(T_i,i) \prec (T_j,j)$ where $T_i=T_j$ and $i<j$. Since we have assumed that the second coordinate, the process number is globally unique, this scheme is complete in the sense that all those kind of pairs are ordered and this scheme is apparently consistent. Moreover, whenever the process numbers do have any inkling to the actual order of physical time as what happens in many situations, smaller process number usually indicates earlier in physical time. So, after all, that decision in the paper makes a lot of sense.


Landau Notation: Why is O(f) (not) the set all g < c*f?

There are at least three fundamental misunderstandings, here.

$O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some $c$ such that $g\leq c\,f$ for all $n$, but just for all large enough $n$.
The argument of $O(\cdot)$ is a (mathematical) function. If $A$ is an algorithm, it makes no sense to write $O(A)$: it doesn't type-check. In particular, for an algorithm $A$, we don't talk about "the order of $A$". Rather, $O(\cdot)$ is a way of comparing mathematical functions: $O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $n$.
$O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $n$. So it's simply not true that, in your example, $g_1$ would be the only function you'd describe as being $O(n^2+10)$.

$O(\cdot)$ is defined that way because it's useful to do so: it's a way of comparing functions and it doesn't care what you use those functions for. ($O(\cdot)$ doesn't care about complexity theory, just as the meter doesn't care about Mount Everest.) So, when we say that the running time of an algorithm is, say, $O(n^2)$, we just mean that, for large enough inputs, it's no worse than some constant times $n^2$. Often, we say it that way because we don't know anything more precise.  In the same vein, I'm pretty sure that you have less than a million dollars in the bank but It would be hard for me to find out how much less.

In cases where we do know something more precise, we might use $\Theta(\cdot)$, or we might use separate $O(\cdot)$ and $\Omega(\cdot)$ bounds.  For example, we might say that the running time of some algorithm is $\Theta(n\log n)$, meaning that there are constants $c_1$ and $c_2$ such that, for all large enough $n$, the running time is between $c_1n\log n$ and $c_2n\log n$.  For some other algorithm, we might only be able to prove that its running time is $O(n^3)$ and $\Omega(n^2)$, meaning that there are constants $c_1$ and $c_2$ such that, for large enough $n$, the running time is between $c_2n^2$ and $c_1n^3$.


Let $G=(V,E)$. By symmetry it suffices to show that $u$ must be a cut-vertex.
Let $C$ be the set of vertices in the connected component of $G-(u,v)$ containing $u$. Clearly $v \not\in C$.
Let $x$ be a neighbor of $u$ distinct from $v$. Since $(x,u) \in E \setminus \{(u,v)\}$, we must have $x \in C$ and hence $x$ is disconnected from $v$ in $G-(u,v)$.
Since $G-u$ is a subgraph of $G-(u,v)$ containing both $u$ and $v$, $x$ must be disconnected from $v$ in $G-(u,v)$. The claim follows by noticing that $x$ was connected to $v$ in $G$.


The base of logarithms is irrelevant in big-O notation, since
$$\log_b x = \frac{\log_a x}{\log_a b} = O(\log_a x)\,,$$
so $O(\log_a x)$ and $O(\log_b x)$ denote exactly the same class of functions.

The assertions made by the paper about how long a certain computer would take to solve some problem don't appear to be well founded.  As a minor issue, doesn't "terahertz range computer" mean $10^{12}$ operations per second, not one million per second?  But the major point is that $O(n^2\log n\log\log n)$ is not the same thing as $n^2\log n\log\log n$: it's merely a statement that, there's some constant $c$ such that, for large enough $n$, the number of computation steps is at most $cn^2\log n\log\log n$.  In particular, it doesn't tell us what the value of $c$ is: it could be $10^{-100}$ or $10^{100}$ or anything else. Further, the analysis is never sufficiently precise to equate some number of "computation steps" with an actual number of machine instructions.

You simply cannot turn an asymptotic expression such as this into a running time in seconds without more information.  One possible way to obtain the value of $c$ would be to time the actual execution of the program, but this isn't possible as we don't have any quantum computers that can run Shor's algorithm on $1000$-digit numbers. I don't see anything that would enable the authors of the paper to give precise wall-clock running times for a program on a computer that doesn't exist.

It appears that the authors are using $\ln$ to denote base-$2$ logarithms, since they say that a $k$-digit number equates to $k\ln10$ bits.  A  1000-digit number is about 3300 bits and
$$3300^2\log_2 3300\log_2\log_2 3300\approx 451\times 10^6\,,$$
so that's certainly not where the $84$-second claim comes from.

It seems, in fact, to come from interpreting $\ln$ as meaning the natural logarithm. Based on the incorrect claim that a $1000$-digit number has $1000\log_e 10\approx 2300$ bits, we get
$$2300^2\log_e 2300\log_e\log_e2300\approx 84\times 10^6\,.$$
This calculation is not meaningful in any way.


modular arithmetic in rolling hash algorithm

What you are missing is the identity
$$
(a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}.
$$


Using a rotation matrix to transform/shift a pinhole camera

It looks like you got it, but what's actually going on here is that you are working in homogeneous coordinates.
In this system, a point in space is represented as a 4-tuple, $(x,y,z,1)$. You can multiply this 4-tuple by any non-zero constant and it represents the same point, so this is equivalent to $(wx,wy,wz,w)$ for any $w \ne 0$.
A vector is the difference between two points, and this is represented as a 4-tuple with a zero in the fourth component, $(x,y,z,0)$.
Right-multiplying that 4x4 matrix by a point has the effect of adding the translation component, and right-multiplying by a vector has the effect of not adding the translation component.


How can I make the variance of a multiple sum of set of fixed number of variables minimum?

If you're willing to replace 'variance' with 'max minus min' (spread), then you could formulate this as an instance of integer linear programming and apply an off-the-shelf ILP solver.  There is no guarantee that it finds an optimal solution in a reasonable amount of time, but if you're lucky, it might complete without taking too long; or if you stop it early, you might get a decent solution.
To formulate this as an instance of ILP, add zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means that person $i$ is assigned to team $j$.  Each requirement in the problem statement can be expressed as a linear inequality; for instance, the requirement that everyone in a team has a different can be expressed by inequalities of the form $x_{i,j} + x_{i',j} \le 1$ for each pair $i,i'$ of people from the same seed.
To minimize the spread, introduce variables $\ell,u$.  Let $v_i$ denote the value of person $i$ (this is a constant, not a variable).  Add linear inequalities $\ell \le \sum_i x_{i,j} v_i \le u$ for each team $j$.  Finally, minimize $u-\ell$, subject to the inequalities above.
If you want to use the variance, this becomes a mixed-integer quadratic program instead of a mixed-integer linear program, and I think quadratic programs are significantly harder.


How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

Em…… I seem to have figured out how to construct a probability distribution to achieve $\mathrm{MinACL}$ as close to $H(P)+1$ as possible. Suppose, for the information source $(S,P)$ with $|S| = 2^l + 1$, $p_0 = 1 - \epsilon$, $p_i = \epsilon/2^l,1\leq i\leq2^l$, a valid Huffman tree could be constructed as follows: First build a full binary tree with $s_i,1\leq i\leq2^l$, as leaves and then make $s_0$ sibling of the root of this binary tree, and child of the Huffman tree root node. This scheme can be justified easily given $\epsilon\in(0,0.5)$. Then, $H(P) = -(1-\epsilon)\log(1-\epsilon)-(\epsilon/2^l)\log(\epsilon/2^l)$ and $\mathrm{MinACL}(P) = (l+1)\cdot\epsilon+1\cdot(1-\epsilon)$.

$$
\lim_{\epsilon\to0}\mathrm{MinACL}(P)-H(P) = 1
$$

(I haven't calculated the limit, but the graph below if of much evidence:
)


Paging only for user code. What about kernel code?

Other than the fact that kernels tend to be small, as Yuval points out, you should also consider that they are often not relocatable code (in fact, address binding for kernels is done at compile-time) and so the memory they are allocated could not be moved or swapped-out in any case, not only for paging.  Obviously there are also performance-related concerns, and one should consider handling exceptional cases too, like the code responsible for paging being swapped out.
Usually, memory limitations in operating systems are handled in different ways other than paging. For monolithic kernels, this means offering a loadable module system, while for microkernels the problem might not even apply, since their footprint on main memory is usually much lower than monolithic kernels (system services in microkernels are implemented as user-level processes).

Last but not least, enabling paging on kernel memory would defy one of its main definitions, being "[that] part of the operating system that is always resident in memory"1 ;-).


What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity?

This algorithm requires at most $O(n \log n)$ string comparisons, assuming you use a suitable sorting algorithm.
If strings are at most $S$ characters long, each string comparison can take up to $S$ operations.  So, the worst-case running time could be as large as $O(S n \log n)$.
If the size of the character set is constant, then it is possible to solve your problem in $O(n(S+\log n))$ time with a slightly different algorithm: compute the length of each string ($O(nS)$ time), sort the strings by length ($O(n \log n)$ time), then for each length, use radix sort on the strings of that length ($O(nS)$ time).


How many ways to find a sum totalling n using only certain Integers?

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

Consider the decision problem version of your problem: given $S,n$, is there at least one way to reach a sum of $n$ using the integers from $S$ (possibly multiple times).

Suppose I have a partition instance, a set $T$ where I want to know whether it can be partitioned into $T_1,T_2$ such that the sum of $T_1$ equals the sum of $T_2$.  Let $c$ be a very large constant, and define $S=\{t+c : t \in T\}$ and $n=(m+|T|c)/2$ where $m$ is the sum of all of the numbers in $T$.

Then the answer to the decision problem is yes if and only if the answer to the original partition problem was yes.

You should be able to fill in the details from here (including, in particular, how to choose the constant $c$, based upon $T$).

See also https://cstheory.stackexchange.com/q/19758/5038.

Of course, the problem may still be easy for many $S$; there may even be infinite easy subclasses.  See also Dealing with intractability: NP-complete problems for more on strategies for what to do, when you have a problem that is NP-hard but you still have to solve it.


Question as regards a proof of the Time Hierarchy Theorem

Your arguments is as follows:

If $N$ rejects $[N]$ then $([N],[N]) \in H_f$.
Since $([N],[N]) \in H_f$, $N$ accepts $[N]$ in $f(m_n)$ steps.

This is indeed a contradiction, so we conclude that $N$ accepts $[N]$. Then we argue again:

Since $N$ accepts $[N]$ then $([N],[N]) \notin H_f$.
Since $([N],[N]) \notin H_f$, it is not true that $N$ accepts $[N]$ in $f(m_n)$ steps.

Since the running time of $N$ is $f(2m_n+1)^3$ in your case, there is no contradiction. After $f(m_n)$ steps the machine $N$ might still be running.


Articulation points (or cut vertices), but only subset of vertices need to be connected

Let $P$ be the set of pairs of vertices that need to communicate and let $n$ be the number of vertices of the graph.

Compute the block-cut tree $T$ of your graph and root it in an arbitrary vertex.
Remove from $P$ all pairs that belong in the same block.
For any vertex $v$ of the graph, let $b_v$ be the vertex of $T$ representing the block in which $v$ belongs.

For each of the surviving pairs $(u,v) \in P$, compute the lowest common ancestor $LCA(b_u, b_v)$ of $b_u$ and $b_v$ in $T$. This requires $O(n + |P|)$ time using, e.g., Tarjan's algorithm.

For every pair $(u,v) \in P$, the cut vertices that disconnect $u$ from $v$ are exactly those that appear in the (unique) path of $T$ from $b_u$ to $LCA(b_u, b_v)$ or in the (unique) path of $T$ from $b_v$ to $LCA(b_u, b_v)$.

These vertices can be found efficiently by visiting $T$ in postorder. While visiting a vertex $x$, keep track of a special vertex $s_x$. This vertex might not always exist, but if it does it will always be an ancestor of $x$. The meaning of $s_x$ is the following: all cut-vertices in the path from $x$ to $s_x$ disconnect at least one pair in $P$.

The visit of a generic vertex $x$ proceeds as follows:

Let $x_1, x_2, \dots$ be the children of $x$ in $T$, and set $s_x$ to the vertex of lowest depth in $T$ among $s_{x_1}, s_{x_2}, \dots$, if any.

If $x$ represents a block $B$:

2.1. For each pair $(u,v) \in P$ such that $\{u,v\} \cap B \neq \emptyset$, set $s_x$ to the lowest vertex among $s_x$ itself (if $s_x$ exists) and $LCA(u,v)$.

If $x$ is a cut-vertex, $s_x$ exists, and $x$ is a descendant of $s_x$ (a vertex is a descendant of itself):

3.1. Report $x$ as a cut-vertex disconnecting a pair of interest.

Step 1 requires time proportional to the number of children of $x$ in $T$, therefore the total time spent in this step will be $O(n)$.
The overall time required to perform step 2 is $O(n+|P|)$ after a $O(|P|)$ preprocessing that associates the pairs in $P$ to the corresponding blocks.
Finally, step 3. requires constant time per vertex (since the ancestor-descendant relation can be checked in constant time after a $O(n)$ preprocessing).


Here is my interpretation of your notation. The function $F = m(0,4,5,6)$ is in fact
$$ F = (x \land y \land z) \lor (\bar{x} \land y \land z) \lor (\bar{x} \land y \land \bar{z}) \lor (\bar{x} \land \bar{y} \land z). $$
(Perhaps positive and negative literals are switched, and possibly I am reading the bits in reverse order.)

The notation $F+G$ just means $F \lor G$. In that case, $m(S) + m(T) = m(S \cup T)$. Similarly, if $FG$ means $F \land G$, then $m(S)m(T) = m(S \cap T)$. Finally, the negation of $m(S)$ is $m(\bar{S})$. Basically, $m(S)$ is the function which is true on the truth assignments in $S$, so we can identify it with $S$. Boolean operations on functions correspond to boolean operations on sets.


variable exponent in expression of a formal language

Whenever $m,n$ are chosen, there is only a single interpretation for $(A^nB)^m$. The variables are "locked" in the set builder notation $\{ \dots \mid m,n>0\}$. I mean, the string $(A^2B)^3$ equals $AABAABAAB$, there are no schools here.

If you want to have repetitions of variable length sequences of the form $A\dots AB$ then the regular expression $(A^*B)^*$ is appropriate.

The point here is that for each $m,n$ the $(A^nB)^m$ here is only a single object, not a set of strings (a language).

Consider the domain of natural numbers, which probably is better known. Let us analogously define the set $S = \{ (n+1)^m \mid m\ge 2,n>0\}$. Here it is quite clear that every $m,n$ is a single number, the $m$th power of a specific $n+1$. We would not consider choosing another $n$ for each multiplication. So we have $(2+1)(2+1)(2+1)\in S$ and not $(2+1)(5+1)(10+1)$.

The confusion is perhaps that in formal languages we consider both powers of single words and powers of languages. The $(A^*B)^*$ is an abbreviation for $\bigcup_{m\ge 0}\{ A^nB\mid n\ge 0\}^m$. In this case for any $m$ we compute the $m$th power of the language $\{ B, AB, AAB, AAAB, \dots \}$ which is the concatenation of $m$ copies of the language. Then we can choose a different string (i.e., a different $n$) in each term.

Another example that shows the difference between these confusing notations is the following. For a language $L$ its square is $L^2 = L\cdot L = \{ uv\mid u,v\in L\}$. This is the concatenation of two copies of $L$, and we may choose two diferent strings: $\{aa,b\}^2= \{aaaa,aab,baa,bb\}$.
Squaring all words is different: $\mathrm{sq}(L) =\{ w^2 \mid w\in L \}$. Same example $\mathrm{sq}(\{aa,b\}) = \{aaaa,bb\}$.

But again, the formal reason is set builder notation, as in my first paragraph.


non-deterministic finite automaton state transition table language question

Starting from the $M$ you gave in a comment (which you should really include in the question), we have the transition table
$$\begin{array}{r|cc}
\delta & 0  & 1 \\ \hline
q_0    & q_1 & q_2\\
q_1    & q_0 & q_2\\
q_2    & q_2 & q_2
\end{array}$$
with $q_0$ the start state and $q_1$ the final state. Now we modify this to a new NFA $M'$ by adding another final state $q'_0$ and construct the transitions $\delta'$:

$\delta'(q'_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
$\delta'(q'_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
$\delta'(q_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
$\delta'(q_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
$\delta'(q_1, 0) = \{\delta(q_1, 0)\}=\{q_0\}$, since $\delta(q_1,0)=q_0\notin F$
$\delta'(q_1, 1) = \{\delta(q_1, 1)\}=\{q_2\}$, since $\delta(q_1,0)=q_2\notin F$
$\delta'(q_2, 0) = \{\delta(q_2, 0)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$
$\delta'(q_2, 1) = \{\delta(q_2, 1)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$

giving us this transition table for $M'$
$$\begin{array}{l|cc}
\delta'     & 0           & 1 \\ \hline
\{q'_0\}    & \{q_0,q_1\} & \{q_2\}\\
\{q_0\}     & \{q_0,q_1\} & \{q_2\}\\
\{q_1\}     & \{q_0\}     & \{q_2\}\\
\{q_2\}     & \{q_2\}     & \{q_2\}\\
\{q_0,q_1\} & \{q_0,q_1\} & \{q_2\}
\end{array}$$
with $\{q'_0\}$ the start state and $\{q'_0\}, \{q_1\}, \{q_0,q_1\}$ the final states. Notice that $\{q_0\}$ and $\{q_1\}$ are unreachable so can be eliminated from the NFA. Notice also that in both FAs, state $q_2$ is a "trap" state: once you enter it (on input $1$), you'll never leave. This means that neither FA will accept any string containing a $1$ and from there it's not too hard to see what $L(M)$ and $L(M')$ are.


Designing solution to critical section problem with two semaphores vs single semaphore

If only one semaphore is used to control the access to the critical section, it is not possible for deadlock to happen. That is why two semaphores are used in the problem statement since the problem is designed to, I assume, showcase deadlock.

A single-semaphore-based program can protect the critical section from concurrent access as well, as demonstrated by your program that uses a single semaphore.

However, some critical sections do require two or more semaphores to protect. Here is an example. There are only one fork and one knife. Each of the two diners must obtain both of them before entering the dining section. So there should one semaphore for the fork and another one for the knife. If the waiting operations of these two semaphores are not arranged in the same order for both diners, deadlock could happen. Note that one semaphore is not enough to deal with this situation correctly.


Finding a simple cycle that goes through two vertices

The decision version of your problem (deciding whether such a cycle exists) is NP-complete. See Proposition 9.2.1(P3) on page 477 (495) in Digraphs – Theory, Algorithms and Applications by Bang-Jensen and Gutin.


Note: For this answer I chose to assume that the question was somewhat
naive, since, as remarked by @D.W. in his comment, the OP should
otherwise search for himself in wikipedia and other places on the web,
and the spectrum of problems and techniques is far too wide for an
answer here. So I am focussing on the fundamental aspects, obvious to
a seasoned computer scientist, but somewhat magical for someone with
less technical experience, and seeming to border artificial
intelligence, when it is often just the application of appropriate
recipes (well, often complex ones). One meta-remark: users who ask
questions should give some information regarding their experience (or
their age, as a weak indicator). It is often difficult to assess the
level appropriate for an answer.

A fundamental question is whether there is any difference between
numerical computation and algebraic manipulation.

As a computer scientist (to be ?) you shold more than anyone else be
aware that all that is done by the computer, or by the mathematician,
is to manipulate representations of abstract entities.

You learn in "algorithmics and data structures" that to deal
efficiently with a problem, you have to find a proper representation
for the data (e.g. a graph, an array, a string, a hash-table, a binary-tree, etc.) and to
manipulate this representation appropriately (which impacts the choice of the proper representation) to get a representation
of the result.

Numerical calculation is no different. You represent numbers by
sequences of symbols (though some systems use two dimensional
representations). Then you define various manipulation schemes of
these sequences that corresponds to numerical operations you are
interested in.

The invention of the representation 0 for a number measuring the absence of any content, and of positional
numeration system (i.e. representation of numbers) was a major step in
mathematics, and allowed for more effective encoding techniques for
numerical data, and of simpler manipulation techniques for doing the
operations.

This oganization is universal: we always work on representations. The
computer does nothing else, even when doing simple arithmetics.

So the answer to your question is simply, as always: choose a
representation for whatever concepts you want to manipulate an design
the algorithms that manipulate these representations in a way that
corresponds to the abstract manipulations you are interested in.

Typically, if you want to manipulate algebraic expressions containing
constants, variables (identifiers) and operators, you can just
represent them as a rooted tree structures with constants and
variables on the leaves, and the operators on the nodes. That is easy, though more complex representations may sometimes be useful.

Now you may consider your expression as representing a function of a
variable x, that appears among the variables, and you want to
compute the derivative of that expression for x. You can probably imagine
the algorithm yourself, if you know the rules for computing a
derivative, when you do it by hand.  This is a fairly simple recursive
procedure, since the derivative of an expresson can be defined from
the subexpressions and their derivatives, in a way that depends on the
top operator.

You can do things similarly for some trigonometric computations, applying various rules and strategies for transforming trigonometric expressions (such as: $\cos(a+b)=\cos a\cos b-\sin a\sin b$ ), that were used by hand by people (including myself) before computers were available to do it.

Now, many of these manipulation problems are actually hard to
solve. But that comes from the diffculty of mathematics, not from the
fact that it is mechanized in a formal calculation system. There involve a wide variety of techniques and mathematical theories, that have to be adressed individually, and certainly not together in a single question.

As a final remark, we should remember that much of the theory of
computation originates with the search for answers to the
Entscheidungsproblem, a challenge posed by David Hilbert in 1928
about mechanisation of mathematics, and addressed by such people as
Gödel, Church, Turing, and several other pioneers of the field. The
fact that computing devices are now used to do just that, mechanize
mathematics, was only to be expected. It is always pleasing to see
some consistency between the various branches of computer science.


Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?

Consider your last inequality:

$\qquad \displaystyle n < \frac{c_2y}{c_1x}\log(n)$

Now, $C\log n$ with $C = \frac{c_2y}{c_1x}$ is a concave function. Therefore, there are at most two intersections, and only one of them is interesting for you; that is, solve

$\qquad \displaystyle n = C\log(n)$

and find out which algorithm is faster in which interval by simply calculating the respective function values at some point in the respective interval.

It is true that solving this equality explicitly is hard/impossible. For some fixed $C$, computer algebra gives you an expression in a well-known function; interesting (real) intersection turns out to be at

$\qquad \displaystyle n = e^{-W_{-1}(-\frac{\ln 2}{C})}$

if $C \geq e \ln 2$, with $W_k$ the analytic continuation of the product log function. This function does not have a nice closed form, but it can be evaluated numerically for given $C$; for instance, you get $\approx 116,74$ for $C=17$.


Decomposing the search problem into several small problems

The term you are looking for is "divide-and-conquer".  There are gazillions of divide-and-conquer algorithms; any algorithm textbook should show you quite a few examples.  Divide-and-conquer is more general, because it also allows you to do some merger operation to combine the solutions to each piece -- but many divide-and-conquer algorithms do follow the form you are looking for, so I think "divide-and-conquer" should be a helpful search term.

In graphs, one common use of divide-and-conquer is to decompose the graph into connected components or strongly connected components, and then work on each component separately.  In many cases, no pre-processing or post-processing to glue together the solutions is needed: you just take a union of the solution for each component.


The claim is not that every woman ends with the last man on her list. Rather, consider all stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)


Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not

The exercise above is right but is missing something. You need to do 1-0.11 since you need to find the <, not the >. When I wrote 0.11 I have found the > but I need the < so  1-.. .


Languages A, B ∈ NP-complete such that A⋃B = Σ*

Hint: let $A$ be a NP-complete language and $B=\Sigma^*$.  Then $A \cup B = \Sigma^*$.  Is $B$ the complement of $A$?  Does it belong to coNPC?


Can bottom-up architectures be effectively programmed in top-down paradigms?

I would like to generalize this into a more common scenario. This I believe makes sense since the particulars of subsumption architecture are perhaps not a primary aspect in the question (and the same problems occur in non-robotic fields as well).

In general software archtitecture there is a bi-directional approach, or multi-paradigm approach, as in the question. The bottom most layer of an operating environment is generally written bottom up. Very specific code bits are written to driver very specific hardware elements on the system. These are then combined to form higher level components. I suspect we could easily describe this as a subsumption approach if we simply describe our robot as the system itself, and the goals to control specific aspects of that system. Though I'm not sure it is improtant to do so.

From the top-down most applications are written in higher level languages, or described in terms of an abstract machine. This is quite far removed from the bottom most libraries which will actually be doing the work.

At some point these two layers have to meet -- actually they meet at many locations in a variety of scenarios. This where you have to "adapt" the layers to be suitable for the other layer. The term "adapter" here is 100% correct. There is indeed a software pattern called "adapter" which is used for this purpose.

Aside from specific adapters we can actually consider the entire toolchain of any modern programming. The compiler itself, along with the liner and an execution VM, are the primary interface between the two layers.  That is, a high level language is written in one domain, and the compiler is what allows it to work in the lower level domains.

If you are looking specifically for paradigm effectivness, consider that high-level languages exist for imperative programming (C++), functional programming (Haskell), and declarative programming (Prolog). These paradigms all ultimately work on the same underlying low-level libraries.

Is the question in robotics much different? No, I don't believe so. Indeed if the same ideas were formulated today I don't think they'd have a robotic specific term (subsumption architecture) as there is no strong difference from normal software architecture. You even indicate in your last paragraph both a functional and imperative paradigm for controlling a robot. I would however use a domain specific language to be used -- and again, the vast assortment of domain specific languages is further evidence that multiple paradigms can be efficiently adapted to each other.


Random algorithm with biggest sequence that never repeats

If you don't want to follow Yuval's advice :), Mersenne Twister algorithm is a good random number generator and has a quite simple implementation (period of $2^{19937}−1$). See Wikipedia page for quick highlights on advantages/disadvantages. There are also many open source implementations in many programming languages.

For technical details and in-deep analysis of the algorithm see M. Matsumoto's articles that are available on his page.


Meaning of "pushing x down" and "pulling x up" in database query handling

I would normally say "pushing inward"/"pulling outward", but "down"/"up" make sense if you are thinking in terms of syntax trees and, being a computer scientist, your trees grow downward.

In (classical) logic there are rules like De Morgan's rule which says $\neg(P\land Q)\equiv(\neg P)\lor(\neg Q)$ and many others that allow you to move negation either outward/upward toward the outermost connective (reading the equivalence from right to left), or inward/downward towards the leaves of the syntax tree (reading the equivalence left to right). If we actually draw out the syntax tree it will look like

    ¬             ∨
    |            / \
    ∧      ≡    ¬   ¬
   / \          |   |
  P   Q         P   Q

which illustrates the down/up movement. In general, we can use any available equivalences for any sort of expression to move operations around. In the case of negation, since we have $\neg\neg P\equiv P$ it is often desirable to try to move them toward each other. Systematically moving them towards the leaves, i.e. inward/downward, is one way to accomplish this. Often these types of cancellations are one of the goals of applying these equivalences. There are other concerns too. For example, if it is possible to remove duplicates before a join rather than after, that could be extremely advantageous.

  Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

This just states that sometimes the available equivalences are not so simple, and an equivalence might simplify a selection at the cost of making a join more complicated or vice versa and so the equivalences can't just be blindly applied in a fixed direction (at least not if you want a good result).


First class types enable something called dependent typing. These allow the programmer to use values of types at type level. For example, the type of all pairs of integers is a regular type, while the pair of all integers with the left number smaller than the right number is a dependent type. The standard introductory example of this is length encoded lists (typically called Vector in Haskell/Idris). The following pseudo-code is a mixture of Idris and Haskell.

-- a natural number
data Nat = Zero | Successor Nat

data Vector length typ where
  Empty : Vector Zero typ
  (::)   : typ -> Vector length typ -> Vector (Successor length) typ

This piece of code tells us two things:

The empty list has length zero.
consing an element onto a list creates a list of length n + 1

This looks very similar to another concept with 0 and n + 1, doesn't it? I'll come back to that.

What do we gain from this? We can now determine additional properties of the functions we use. For example: An important property of append is that the length of the resulting list is the sum of the lengths of the two argument lists:

plus : Nat -> Nat -> Nat
plus          Zero n = n
plus (Successor m) n = Successor (plus m n)

append : Vector n a -> Vector m a -> Vector (plus n m) a
append Empty  ys = ys
append (x::xs) ys = x :: append xs ys

But all in all this technique does not seem all to useful in everyday programming. How does this relate to sockets, POST/GET requests and so on?

Well it doesn't (at least not without considerable effort). But it can help us in other ways:

Dependent types allow us to formulate invariants in code - rules as how a function must behave. Using these we get additional safety about the code's behaviour, similar to Eiffel's pre- and postconditions. This is extremely useful for automated theorem proving, which is one of the possible uses for Idris.

Coming back to the example above, the definition of length-encoded lists resembles the mathematical concept of induction. In Idris, you can actually formulate the concept of induction on such a list as follows:

              -- If you can supply the following:
list_induction : (Property : Vector len typ -> Type) -> -- a property to show
                  (Property Empty) -> -- the base case
                  ((w : a) -> (v : Vector n a) ->
                      Property v -> Property (w :: v)) -> -- the inductive step
                  (u : Vector m b) -> -- an arbitrary vector
                  Property u -- the property holds for all vectors

This technique is limited to constructive proofs, but is nonetheless very powerful. You can try to write append inductively as an exercise.

Of course, dependent types are just one use of first class types, but it's arguably one of the most common ones. Additional uses include, for example, returning a specific type from a function based on its arguments.

type_func : Vector n a -> Type
type_func Empty = Nat
type_func v     = Vector (Successor Zero) Nat

f : (v : Vector n a) -> type_func v
f Empty = 0
f vs    = length vs :: Empty

This is a nonsensical example, but it demonstrates something you cannot emulate without first class types.


What is the difference between rateless and online encoding?

They are not the same thing. The difference is when you know the message to encode.

In fountain codes, you know the message at the onset. The code allows you to keep generating more and more redundancy. The message, however, is fixed.

In online codes you do not know the entire message at the beginning, but you learn it as time goes by. Each time you learn an additional part of the message you can encode this part in a coherent way to the encodings of the (prefix of the) message you have already obtained or sent.