Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular

$L_1 = \{a^ib^jc^k: i,j,k \ge0\} = a^*b^*c^*$ is regular.

Assume that $L = \{a^ib^jc^k: (i=1) \Rightarrow (j=k)\}$ is also regular.

Then $L_2 = \{ab^jc^k: j\neq k\} = L_1 - L$. By closure properties (difference of regular sets is regular) $L_2$ is regular. But using Pumping lemma it is not difficult to prove that $L_2$ is not regular. So we have a contradiction.

In fact we could prove that $L$ is not regular directly using Pumping lemma.


Peer grading design - choosing a graph, to get accurate rankings/ratings

There are two parts to this: (a) selecting a graph (experimental design) to determine which pairs of essays the students will evaluate in the peer grading process, and (b) ranking all the essays, based upon the student's peer grades, to determine which the teacher should rank.  I will suggest some methods for each.

Choosing a graph

Problem statement.  The first step is to generate a graph.  In other words, you need to select which pairs of essays to show to the students, during the peer grading exercise.

Suggested solution. For this task, I suggest that you generate a random graph $G$, selected uniformly at random from the set of all 3-regular (simple) graphs.

Justification and details.  It is known that that a random $d$-regular graph is a good expander.  In fact, the regular graphs have asymptotically optimal expansion factor.  Also, because the graph is random, this should eliminate the risk of skewing the grading.  By selecting a graph uniformly at random, you are ensuring that your approach is equally fair to all students.  I suspect that a uniformly random 3-regular graph will be optimal for your purposes.

This raises the question: how do we select a 3-regular (simple) graph on $n$ vertices, uniformly at random?

Fortunately, there are known algorithms for doing this.  Basically, you do the following:

Create $3n$ points.  You can think of this as 3 copies of each of the $n$ vertices.  Generate, uniformly at random, a random perfect matching on these $3n$ points.  (In other words, repeat the following procedure until all $3n$ points are paired off: select any unpaired point, and pair it with another point chosen uniformly at random from the set of unpaired points.)
For each two points that are matched by the matching, draw an edge between the corresponding vertices (that they are a copy of).  This gives you a graph on $n$ vertices.
Next, test if the resulting graph is simple (i.e., it has no self-loops and no repeated edges).  If it is not simple, discard the graph and go back to step 1.  If it is simple, you are done; output this graph.

It is known that this procedure generates a uniform distribution on the set of 3-regular (simple) graphs.  Also, it is known that at step 3 you have a constant probability of accepting the resulting graph, so on average the algorithm will do $O(1)$ trials -- so this is pretty efficient (e.g., polynomial running time).

I have seen this approach credited to Bollobas, Bender, and Canfield.  The approach is also summarized briefly on Wikipedia.  You can also find a discussion on this blog post.

Technically speaking, this requires that the number $n$ be even (otherwise there is no 3-regular graph on $n$ vertices).  However, this is easy to deal with.  For instance, if $n$ is odd, you can randomly choose one essay, set it aside, generate a random 3-regular graph on the remaining essays, then add 3 more edges from the set-aside essay to 3 randomly chosen other essays.  (This means that there will be 3 essays that are actually graded 4 times, but that shouldn't do any harm.)

Ranking all the essays

Problem statement.  OK, so now you have a graph, and you have presented these pairs of essays (as indicated by the edges in the graph) to the students for them to grade during the peer grading exercise.  You have the results of each comparison of essays.  Now your task is to infer a linear ranking on all of the essays, to help you determine which ones to have the teacher evaluate.

Solution. I suggested you use the Bradley-Terry model.  It is a  mathematical approach that solves exactly this problem.  It was designed for ranking players in some sport, based upon the results of matches between some pairs of the players.  It assumes that each player has an (unknown) strength, which can be quantified as a real number, and the probability that Alice beats Bob is determined by some smooth function of the difference of their strengths.  Then, given the pairwise win/loss records, it estimates the strength of each player.

This should be perfect for you.  You can treat each essay as a player.  Each comparison between two essays (during the peer grading process) is like the result of a match between them.  The Bradley-Terry model will allow you to take all of that data, and infer a strength for each essay, where higher strengths correspond to better essays.  Now you can use those strengths to rank-order all of the essays.

Details and discussion. In fact, the Bradley-Terry model is even better than what you asked for.  You asked for a linear ranking, but the Bradley-Terry model actually gives a (real-number) rating to each essay.  This means you know not only whether essay $i$ is stronger than essay $j$, but a rough estimate of how much stronger it is.  For instance, you could use this to inform your selection of which essays to rank.

There are alternative ways to infer ratings or rankings for all the essays, given the data you have.  For instance, the Elo method is another.  I summarize several of them in my answer to a different question; read that answer for more details.

One other comment: The Bradley-Terry model assumes that the result of each comparison between two players is a win or a loss (i.e., a binary result).  However, it sounds like you will actually have more detailed data: your slider will give a rough estimate of how much better the peer grader rated one essay than another.  The simplest approach would be to just map each slider to a binary result.  However, if you really want, you might be able to use all of the data, by using a more sophisticated analysis.  The Bradley-Terry model involves doing logistic regression.  If you generalize that to use ordered logit, I bet that you could take advantage of the extra information you have from each slider, given that the results from the sliders are not binary but are one of several possibilities.

Efficient use of the teacher

You suggest having the teacher manually grade the top X% and bottom X% of all of the essays (using the ranking inferred from the results of the peer-grading).  This could work, but I suspect it is not the most efficient use of the teacher's limited time.  Instead, I'd like to suggest an alternate approach.

I suggest that you have the teacher grade a subset of the essays, with the subset carefully selected to try to provide the best possible calibration for all of the essays that weren't graded by the teacher.  For this, I think it might help if you selected a sample of essays that cover the range of possible answers (so for every essay, there is some teacher-graded essay that is not too far away from it).  For this, I can think of two approaches you could consider trying:

Clustering. Take the ratings that are produced by the Terry-Bradley model.  This is a set of $n$ real numbers, one real number per essay.  Now cluster them.  Suppose you want to have the teacher grade $k$ essays.  One approach would be to use $k$-means clustering (on these one-dimensional data points) to cluster the essays into $k$ clusters, and then randomly select one essay from each cluster for the teacher to grade -- or have the teacher grade the "cluster head" of each cluster.
Furthest-point first. An alternative is to try to select a subset of $k$ essays that are as different from each other as possible.  The "furthest-point first" (FPF) algorithm is a clean approach for this.  Assume that you have some distance function $d(e_i,e_j)$ that lets you quantify the distance between two essays $e_i$ and $e_j$: a small distance means that the essays are similar, a larger distance means they are dissimilar.  Given a set $S$ of essays, let $d(e,S) = \min_{e' \in S} d(e,e')$ be the distance from $e$ to the nearest essay in $S$.  The furthest-point first algorithm computes a list of $k$ essays, $e_1,e_2,\dots,e_k$, as follows: $e_{i+1}$ is the essay that maximizes $d(e,\{e_1,e_2,\dots,e_i\})$ (out of all essays $e$ such that $e \notin \{e_1,e_2,\dots,e_i\}$).  This algorithms generates a set of $k$ essays that are as dissimilar from each other as possible -- which means that each of the remaining essays is pretty similar to at least one of those $k$.  Therefore, it would be reasonable to have the teacher grade the $k$ essays selected by the FPF algorithm.

I suspect either of these approaches might provide more accurate scores than having the teacher grade the top X% and bottom X% of essays -- since the very best and worst essays probably are not representative of the mass of essays in the middle.

In both approaches, you could use a more sophisticated distance function that takes into account not just the strength estimates based upon peer grading but also other factors derived from the essays.  The simplest possible distance function would take into account only the result of the Terry-Bradley model, i.e., $d(e_1,e_2) = (s(e_1)-s(e_2))^2$ where $s(e)$ is the strength of essay $e$ as estimated by the Terry-Bradley model based upon the results of the peer grading.  However, you can do something more sophisticated.  For instance, you could compute the normalized Levenshtein edit distance between essay $e_1$ and $e_2$ (treating them as text strings, computing the edit distance, and dividing by the length of the larger of the two) and use that as another factor in the distance function.  You could also compute feature vectors using a bag-of-words model on the words in the essays, and use the L2 distance between these feature vectors (with features normalized using tf-idf) as another factor in the distance function.  You might use a distance function that is a weighted average of the difference in strengths (based upon the Terry-Bradley estimates), the normalized edit distance, and anything else that seems helpful.  Such a more sophisticated distance function might help do a better job of helping the clustering algorithm select which are the best $k$ essays to have the teacher grade.


Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?

Let $G = (V,E)$ be the input graph. And, let $G_{M} = (V,E_{M})$ be an MST of this graph. First, note the following properties of the MST and BMST.

An MST is always a BMST

If all edges in the graph have distinct edge weights, there is always a unique MST.

Let $e$ be any edge in $E_{M}$. Let $(S_{e},V \setminus S_{e})$ be the cut obtained after removing $e$ from the graph $G_{M}$ and $C_{e}$ denote the edges of $G$ that goes across this cut. Then, $e$ is the minimum weight edge among the edges in $C_{e}$.

Following is the property that is required for a BMST to be an MST.

Property: Every BMST is an MST if and only if for every $e \in E_M{}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$, where $w$ denote the weight of the bottleneck edge in a BMST or MST.

Proof:  First, let us prove the 'only if' direction.
($\to$) Suppose every BMST is an MST. For the sake of contradiction assume that there is an edge $e \in E_{M}$ such that there exist an edge $e'$ in $C_{e} \setminus \{e\}$ that has weight smaller than $w$. Let us remove $e$ from $G_{M}$ and add $e'$ to $G_{M}$. Let this new graph is $G_{M}'$. It is easy to see that this graph is a BMST. However, it is not an MST since
$$\begin{align} Total\_Weight(G_{M'}) &= Total\_Weight(G_{M}) - w(e) + w(e')\\ &> Total\_Weight(G_{M}) \end{align}$$
Here, I have used the fact that $w(e) < w(e')$ by Property 3 of MST.
This contradicts the fact that every BMST is an
MST. This completes the proof of the 'only if' direction. Now, let us prove the 'if' direction.
($\gets$) Suppose for every $e \in E_{M}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. For the sake of contradiction, assume that there is a BMST $G_{B} = (V_{B},E_{B})$ that is not an MST. Therefore, we can say that there is an edge $e$ in $E_{M}$ that is not in $E_{B}$. Now, remove this edge form the graph $G_{M}$ and let $(S_{e}, V \setminus S_{e})$ be the corresponding cut. Let $u$ be a vertex in $S_{e}$, and $v$ be a vertex in $V \setminus S_{e}$. Let $p$ be a path from $u$ to $v$ in $G_{B}$. It means, there exist an edge $e' \in p$ that goes across the cut. In other words, $e'$ belongs to $C_{e}$. Now, note that since $e' \in G_{B}$, the weight of $e'$ is $\leq$ $w$. It contradicts the fact that all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. This prove the 'if' direction. Hence the proof is complete.


Is F(F(s,x), x) necessarily a PRF if F is?

Let $\mathrm{RF}_n$ be the set of random functions over $\{0,1\}^n$. Let  $F_{f,i}$ be an oracle that answers the first $i$ queries with $F_{f(\cdot)}(\cdot)$ and answers the remaining queries with $f(\cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $\{f\leftarrow \mathrm{RF}_n:F_{f(\cdot)}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$, it can also distinguish  $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$ for some $k$.

Now construct a new distinguisher $D'$. Given an oracle $\mathcal{O}(\cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns

$F_{f(x)}(x)$ if $i<k$, or
$\mathcal{O}(x)$ if $i=k$, or
$f(x)$ if $i>k$.

We can see if $\mathcal{O}$ is $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$. If $\mathcal{O}$ is $\{s\leftarrow\{0,1\}^n:F_s(\cdot)\}$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$. Since $D$ can distinguish $\{f\leftarrow \mathrm{RF}_n:F_{f,k-1}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:F_{f,k}(\cdot)\}$, our distinguisher $D'$ can distinguish $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$ and $\{s\leftarrow\{0,1\}^n:F_s\}$, which contradicts to the fact that $F$ is a PRF.

So $\{f\leftarrow \mathrm{RF}_n:F_{f(\cdot)}(\cdot)\}$ and $\{f\leftarrow \mathrm{RF}_n:f(\cdot)\}$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.


The reason why the SAT solver is slow is unlikely to be the size of the clauses, but rather the hardness of the problem itself.

In any case, any instance of CNF-SAT can notoriously be transformed into an equisatisfiable formula with at most three literals per clause by replacing each clause in the form:

$$
( x_1 \vee x_2 \vee \dots \vee x_n)
$$

with:

$$
 (x_1 \vee x_2 \vee y_1) \wedge (\neg y_1 \vee x_3 \vee y_2) \wedge \dots \wedge (\neg y_{n-4} \vee x_{n-2} \vee y_{n-3}) \wedge (\neg y_{n-3} \vee x_{n-1} \vee x_n)
$$

where $\{y_i\}_{i \in \mathbb{N}}$ are fresh variables.


We need to inspect the factors after that, since the factors of $n!$ grows linearly while the factors of $2^n$ stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that $2^4 = 16$ while $4! = 24$. However, by observing the factors, we notice $2^n$ has $16$ as a factor and $n!$ has $24$ as a factor for all $n \geq 4$ and we factor out the first four [the first $N$] to clearly highlight that the factorial grows faster.

The factors of $\frac{1}{16} 2^n$ factors out the first $2\cdot 2 \cdot 2 \cdot 2$. It is equal to $2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2$ with $(n-4)$ factors. The factors of $\frac{1}{24}n!$ factors out $1 \cdot 2 \cdot 3 \cdot 4$ and is equal to $5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, n$, again with $(n-4)$ factors. When $n = 4$ then these factored-out functions are equal to unity. In fact:

$2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2\cdot 2 = c_f2^n$ where $c_f = \frac{1}{16}$ whereas
$5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, (n-1) \cdot n = c_gn!$ where $c_g = \frac{1}{24}$.

The $(n-4)$ factors of $c_f2^n$ is clearly less than the $(n-4)$ factors of $c_gn!$. We arrive at $c_f2^n < c_gn!$. Move the constant factor on the LHS to obtain $2^n < \frac{c_g}{c_f}n! = \frac{24^{-1}}{16^{-1}}n! = \frac{16}{24}n! = \frac{2}{3}n!$.

By inspecting the factors of $2^n$ and $n!$ after the initial four, and knowing that for all $n > 4:\: 2^n < n!$, we factored out the first four terms of each function and inspected the rest to determine $2^n \leq \frac{2}{3}n!$.

The formal definition of big-O states that:

$$\exists c > 0\; \exists N > 0: \forall n\; (n>N) \Longrightarrow f(n) \leq cg(n)$$

In your case, $c = \frac{2}{3} = \frac{16}{24}$ and $N = 4$.


You can check that P halts iff $x = ty$ for some integer $t \geq 1$. Hence $g(x,y,z)$ is just the following function:
$$
g(x,y,z) = \begin{cases} 1 & \text{ if $x = ty$ for some integer $t \geq 1$}, \\ 0 & \text{ otherwise.} \end{cases}
$$
Given integers $x,y$, it is not hard to check whether $x = ty$ for some integer $t \geq 1$. Hence $g$ is computable (even in polynomial time!).


Does infinite length strings lead to uncountable languages?

A finite language is finite. Every finite set is countable, by definition.

A language of finite-length strings over a finite alphabet may be infinite but is always countable.

A language of infinite-length strings over a finite alphabet might be uncountable.


NSA Recommended Cryptography Algorithms changes from a single paper

There are many examples in cryptography.  Much of progress in cryptography is driven by academic research.
The Advanced Encryption Standard (AES) was a result of a request for research from the National Institute of Standards and Technology.  Two cryptographers proposed a new algorithm, which was eventually adopted as the standard.  A bit over a year ago NIST released a report estimating that there was $250 billion in economic benefit from the AES standard.  This can be directly traced back to academic research.  This doesn't involve prime numbers or number theory, though.
Key sizes and algorithm design typically comes out of academia.  The RSA algorithm was created by academics who published a research paper proposing the algorithm (which in turn built on prior research from others, such as Hellman and Diffie), and has been extremely widely used to protect digital infrastructure -- including secure browsing and other uses.
Research has played a major role in setting parameters and key sizes for cryptographic algorithm; see, e.g., https://en.wikipedia.org/wiki/Key_size for a number of examples.
Caveat: many of the researchers doing this work might self-identify as computer scientists more than mathematicians.  But the lines between theoretical computer science and applied mathematics in this area are blurry.


Algorithm to find the probability of a given text to be about a large topic

You can try simple probabilistic graphical models, the simplest one being Naive Bayes.

One way to do this would be to represent a portion of text as a word frequency vector, that will be associated with a topic (the "class variable"). Then you use many such texts that are associated with topics to train your model (i.e. you model the probability of a frequency vector given a certain topic). Finally, given a new text you can ask what is the most likely topic assignment.

Naive Bayes, the simplest graphical model, would miss dependencies between the frequencies of the various words, but it is worth a shot as it is easy to implement. More complicated models could be used to capture these dependencies.


What would show a human mind is/is not reducible to a Turing machine?

To answer your question:

  Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

The Turing test was conceived as a way to test a particular special case of this assumption: it gives us a way to test whether a particular AI system is successful at behaving indistinguishably from a human.  Thus, this would give a plausible way to prove the assumption -- if we could come up with an AI system that is good enough to pass the Turing test.  Unfortunately, that's something we haven't been able to do, yet.


List of all possible reasoning tasks - satisfiability and theorem proving only?

There is no exhaustive list of reasoning tasks, as the phrase "reasoning task" does not have a precise definition.

Don't put too much weight on categorizations.  They're a descriptive tool that might help you get a high-level overview of a field, but they're inherently subjective, incomplete, and imperfect.  There's tons of work on artificial reasoning, and there are many ways one could potentially put a mental framework around it -- there's no one right answer about how to do that.


If L is regular, show that even(L) is also regular

1) Since $L$ is regular we can build a DFA $M = (Q,\Sigma,\delta,q_0,F)$ accepting it.

2) Next we build a DFA $C = (\{c_0,c_1\},\Sigma,\delta_c,c_0,\{c_0\})$ that accepts all strings of even length -- it will help us "count". I'll let you figure out $\delta_c$.

3) Make a product $\epsilon$-DFA $P = (Q_p,\Sigma,\delta_p,(q_0,c_0),F_p)$ from $M$ and $C$, where

$$Q_p = Q \times \{c_0,c_1\}$$

Accepting states are just all state pairs, with an accepting state from the original DFA $M$:
$$
F_p = \{(q_i,c_j) \mid (q_i,c_j) \in Q_p \wedge ~q_i \in F \}
$$
And the transition function looks like this:

all transitions from the "even" state pairs $(q_i,c_0)$ are replaced by $\epsilon$-transitions:
$$
\begin{array}{ll}
\delta_p((q, c_0),~a) = \emptyset,~\forall a \in \Sigma,~\forall q \in Q\\
\delta_p((q, c_0),~\epsilon) = \{(\delta(q,a),~c_1) \mid a \in \Sigma\},~\forall q \in Q
\end{array}
$$
all transitions from the "odd" state pairs $(q_i,c_1)$ mimic the original DFA $M$ (or more precisely, unmodified product automaton):
\begin{array}{ll}
\delta_p((q, c_1),~a) = \{(\delta(q,a),~c_0)\},~\forall a \in \Sigma,~\forall q \in Q \\
\delta_p((q, c_1),~\epsilon) = \emptyset,~\forall q \in Q
\end{array}

Intuitively, the $\epsilon$-NFA $P$ works as follows: it guesses (or skips) all the odd-numbered symbols in the input string.

We have got an $\epsilon$-NFA accepting even(L), thus even(L) is regular.

Example. Let our original automaton be a DFA which accepts the same language L as the regular expression $(001)^*$ (dead states are not shown):

Here is our product $\epsilon$-NFA accepting even(L):


Explain Hashed page tables in operating system

Definitions (What's with the symbols?)

In the diagram, we have these guys:

Virtual Page Number (VPN): p, q
Page Frame Number (PFN): r
Offset: d
Hash Function: h(x)
Hashed Page Table with schema (key, VPN, PFN, Pointer to next entry with key) for each entry in the table

It so happens that h(p) = same_key and h(q) = same_key. There is hash collision. Both p and q are hashed to the same_key.

This is resolved by chaining the entry with VPN = q to the entry with VPN = p. Chaining means to use the Pointer field in the entry with VPN = q to point to the entry with VPN = p.

Workflow (How the system works)

Operating system (OS) grabs p from the CPU, and performs h(p) to get same_key.

OS looks up the first entry in the Hashed Page Table with key = same_key and checks p against the first entry's VPN field. It checks p against q. This is incorrect.

OS uses the Pointer in the first entry to find the second entry. It knows that the second entry has the same key = same_key, because the Page Table is constructed this way. OS checks p against the seond entry's VPN field. It checks p against p. This is correct. Bam. Kill confirmed.

OS knows that this is the correct entry it is looking for. It grabs PFN from the second entry. It grabs r. r is the correct physical frame number that corresponds to virtual page number p.

OS uses r to look for the physical frame it wants in physical memory, and looks for the exact word wanted which is offset by d within frame r in physical memory. OS grabs the contents of the word and we're done.

Source: Dave Johnson's COMP 421 (Rice University CS Dept)


Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular

First of all, your language definition seems vague. By "starting with a 0", it can mean two things. Either there is an extra 0 at the beginning of the string, followed by equal number of 0s and 1s, i.e number of 0's is greater than the number of 1's by 1, or it could also mean the string has an equal number of 0's and 1's, but starts with 0 instead of 1. Please define it clearly for the sake of clarity. I'm assuming your language definition to be the former, since you've mentioned in your attempt that you're taking the generic string to be $00^p1^{p+1}$, basically implying the string is of the form $0^n1^n$.

Secondly, the length of the string you've taken, $i.e$ - $|0 0^p 1^{p+1}| = 1+p+p+1 = 2p+2$, and not $p+1$.

Given that the string you have taken is of length 2p+2 which is definitely greater or equal to $p$ (the pumping length you have assumed in this case), your approach seems right. Although you can use the generic proof of proving that any language of the form $L = \{ a^nb^n : n ≥ 1 \}$ is not regular, in this case.

Regarding what other string you could take, You can basically take any string of the form $0^n 1^n$ (divide it however you want), i.e it should just satisfy the condition that there should be equal number of $0$'s and $1$'s, and start with zero.

The generic string $0^n 1^n$ works for the general proof. It is obviously longer than $n$. Considering $xyz = 0^n 1^n$, $|xy| ≤ n$, hence $y$ can only contain $0$'s, $y ≠ \epsilon$, $\implies$ y must contain at least one 0. Now $xy^0z \in L$ according to the pumping lemma, but this is a contradiction, as it would imply that it contains at least one $0$ less, but the same number of $1$s as in $0^n 1^n$. Hence, L is not regular.


What does does $O$ mean in this context?

It means exactly the same thing.  It means there is a constant $c$ such that the term is $\le c \cdot \epsilon^2$ (where $c$ does not depend on $\epsilon$).  Big-O notation is not unique to computer science; it is also widely used in mathematics.  See https://en.wikipedia.org/wiki/Big_O_notation, which explains some ways it is used in mathematics.


Data structure for getting the k'th largest element

Here is a solution that uses only comparisons. For simplicity, assume that $n$ is a power of 2.

Find the median of the original array in $O(n)$, and extract the largest $n/2$ elements. Then find the median of the new array in $O(n/2)$, and extract the largest $n/4$ elements. Continue in this way, extracting the $n/8,n/16,\ldots,1$ largest elements. In total, preprocessing takes time
$$ O(n+n/2+n/4+\cdots) = O(2n) = O(n). $$

Given $k$, find $\ell$ such that $n/2^{\ell+1} < k \leq n/2^{\ell}$. By construction, $n/2^\ell < 2k$. The $k$th largest element is thus one of the $n/2^{\ell}$ largest elements. Using the linear time selection algorithm, locate the $k$th element among them in $O(n/2^\ell) = O(k)$.

We can improve the running time for $k \leq Cn/\log n$ (for arbitrary $C$) to $O(1)$ as follows.

During preprocessing, use a linear time selection algorithm to locate the $Cn/\log n$-th largest element in $O(n)$, and extract all larger elements. Sort them in $O(n)$.

During query time, locate the $k$th largest element for $k \leq Cn/\log n$ in $O(1)$ using the new array.

Conversely, we can show that this $O(1)$ behavior cannot extend beyond $O(n/\log n)$ for comparison-based algorithms. Indeed, suppose that there is an algorithm which preprocesses an array in $O(n)$, and is able to locate the $k$th element in $O(1)$ for $k \leq f(n)$, where $f(n) = \omega(n/\log n)$. This allows us to sort an array of size $f(n)$ in time $O(n) + O(f(n)) = o(f(n) \log f(n))$ by adding $n - f(n)$ dummy elements, contradicting the well-known lower bound for sorting.


The terms you can use to search the literature are stable marriage and  the assignment problem.

As far as discouraging strategic voting, one relevant term might be strategy-proof.  This might also be relevant to the general area of mechanism design.  My vague recollection is that discouraging strategic voting in stable-marriage-like problems is a hard problem, but I don't know if I'm remembering that right.

For instance, consider stable marriage.  The traditional algorithm gives a matching that is male-optimal and female-pessimal (every male gets the best possible mate he possibly could have received in any stable matching; and every female gets the worst possible mate she could have received in any stable matching).  Now suppose the females all get together and collude.  In a world of perfect information, they can compute what the female-optimal matching would be, and then change their reported preferences to ensure that the female-optimal matching will be selected.

In fact, collusion is not necessary -- the same result happens if each female individually acts in their own self-interest, without any cooperation or conspiracy.  Assume again a world of perfect information, where everyone's true preferences are known (to the females, at least).  Then each female can compute the best possible mate she could hope for, i.e., the best mate out of all possible matches in all possible stable matchings; she can then change her reported preferences to list that male as her first preference.  If the men use their true preferences and each woman uses this procedure to select her preferences strategically, and then we run the traditional algorithm, we end up with the female-optimal (and male-pessimal) matching.  Each woman has an incentive to behave in this way, and no collusion is necessary (assuming perfect information).


Reducing Vertex Cover to Half Vertex Cover

Let special vertex cover be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover.

Now suppose we're given an instance $G = (V,E),k$ of special vertex cover. Construct an instance $G',k$ of half vertex cover by attaching $|E|$ new edges to each vertex in $V$.

The total number of edges in the new graph is $|E|(|V| + 1)$. A vertex cover of size $k$ in the original graph covers this many edges in the new graph:
$$
|E|(1+k) = |E|\left(1 + \frac{|V|-1}{2}\right) = |E| \frac{|V| + 1}{2},
$$
exactly half the edges. Conversely, consider any $k$ vertices of the new graph, which cover exactly half of the edges. If they cover $m$ of the original edges then they cover at most $m + k|E|$ edges of $G'$, where $m \leq |E|$. The calculation above shows that $m = |E|$, that is, all edges of $G$ are covered.

It remains to reduce vertex cover to its special case. If $|V| = 2k+1$ then there is nothing to do.

If $|V| < 2k+1$, then we add $\delta := 2k+1 - |V|$ many paths of length 2 edges. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + \delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+\delta) = |V| - 2k + \delta = 1.
$$

Similarly, if $|V| > 2k+1$ then we add $\delta := |V| - (2k+1)$ many triangles. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + 2\delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+2\delta) = |V| - 2k - \delta = 1.
$$


How many bytes of memory is used just to "acknowledge" that a certain file is a .jpg?

Depends on how accurately you want it to be.

If you trust the extension then all you need is the 4 last characters in the file name (32 bits)

If you trust the magic header number then you need to check the file starts with 3 bytes ff d8 ff (24 bits). Though other file types have different sizes of magic number. There is a (non-exhaustive) list of them on wikipedia.

If you want to make sure the file is an actual image then you need to actually decode it. Here the size depends on the file size.


Minimum number of strings to cover entire space within Hamming distance

The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for an exact formula for the minimal size of a covering code.


Computational complexity of maximizing sum of rational functions

Your problem can be solved in polynomial time.

Suppose $n-2$ variables (without loss of generality, say $z_3,\ldots,z_n$) are fixed, then the objective becomes maximizing $$\frac{W_1}{D_1-z_1}+\frac{W_2}{D_2-z_2}$$ where $z_1+z_2\le k-(z_3+\cdots+z_n):=K$. Let $$f(z)=\frac{W_1}{D_1-z}+\frac{W_2}{D_2-(K-z)}, 0\le z\le K,$$
then
$$f''(z)=\frac{2W_1}{(D_1-z)^3}+\frac{2W_2}{(D_2-K+z)^3}\ge0,$$
which means $f(z)$ is convex on $[0,K]$, thus the maximum value is achieved at either $z=0$ or $z=K$. This suggests that we can adjust an optimal solution such that either $z_1=0$ or $z_2=0$.

We can repeat this adjustment until there are only one non-zero variable among $z_1,\ldots,z_n$. So to solve your primary problem, just try the solutions $(k,0,\ldots,0),(0,k,\ldots,0),\ldots,(0,\ldots,0,k)$ and choose the optimal one among them.


This might not be the correct answer to your question(as I am not sure about jamming signal), but it might resolve the query.

As Ethernet uses CSMA/CD for error detection, the time taken to transmit the data must be greater than or equal to twice the time taken to propagate the data. Only then the station will come to know if there had been a collision.

Tt >= 2*Tp


When testing n items, how to cover all t-subsets by as few s-subsets as possible?

The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $\frac{1}{3} {n \choose 2}$ triples whenever $n \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working Sage code!). For other $n$, you could round up to the next $n' \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and use a modification of this triple system for $n'$ to cover all pairs for $n$.

If you want the best construction for other $n$, the number of triples required is the covering number $C(n,3,2)$, and is given by this entry in the on-line encyclopedia of integer sequences. This links to the La Jolla Covering Repository which has a repository of good coverings. The online encyclopedia of integer sequences gives a conjectured formula for $C(n,3,2)$; if this formula holds, intuitively that means there should probably be good algorithmic ways of constructing these coverings, but since the formula is conjectured, it is clear that nobody currently knows them.

For high covering numbers, good coverings are harder to find than for $C(n,3,2)$, and the repository will give better solutions than any known efficient algorithms.


When binary search algorithm will be $O(1)$

Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $(\log n)$.

This is a nice open-ended question to test how well students understand the referred concepts. Here is how I could show my understanding about the conventional binary search.

First, the algorithm time is always $O(\log n)$ in its usually implementation, i.e, an (indexed) sorted array (SA) or a binary search tree (BST) in the RAM model + comparison model (the computation model that is usually used when we talk about binary search). Even if the algorithm happens to find the wanted element in the very first iteration, i.e., comparing the wanted element against the element in the middle of the SA or the root of the BST, it takes $O(\log n)$ time still. Even in the worst time, it takes $O(\log n)$ time still.

Second, the algorithm time will be $O(1)$ when its runs on some particular subsets of the searching problems in some particular ways as illustrated below.

The number of elements, i.e., the length of the array or the number of elements in BST is bounded by a constant. In this case, even a linear search algorithm will run in $O(1)$ time. Note that the wanted element may or may not be in the given elements.

Note this situation is different from the situation when the number of different values of the element (as used in the comparison) is bounded. We may need $\Theta(\log n)$ steps to find the index of a $2$ in an sorted sequence of $n$ numbers all of which are 1, 2, or 3.
The wanted element is in the middle of the SA, or in the one-quarter or three-quarter position of the SA, and so on but within a bounded times of iterations. The exact indices of these positions depend on the exact implementation of the binary search. An implementation might check the element at index $(n-1)/2$ first in an array with indices $0,1,\cdots, n$ and odd $n$ or check the element at index $(n+1)/2$ first. The former implementation might need $\Theta(\log n)$ to find the element at index $(n+1)/2$.
The wanted element is within a bounded depth away from the root of the BST.
We could construct various special set of searching situations where the time for a particular implementation of the algorithm will be $O(1)$ by reverse engineering. Specifying a constant $c$. Searching an array by binary search algorithm. If it ends with $c$ steps, we include that problem instance. All together we will find a set of problem instances   where the binary search algorithm will run within $c=O(1)$ steps.

Here is a shorter version that could be used as a reference answer to the question for grading. Again, only the conventional binary search algorithms are considered.

  The binary search algorithm always runs in $O(\log n)$ time in the usual computation model.

  If the wanted element is among the elements that could be possibly compared within $c$ comparisons for some constant $c$, then the algorithm time is $O(1)$. It happens when the number of total elements is bounded by a constant, when the wanted element is the element in the middle of a sorted array of odd length and when the depth of the wanted element is less than a constant where a binary search tree is used.


You can't.  There is no such data structure.  Assuming you have a separate instance per set, and each instance is initialized separately (using only information about the set it represents and not any information about any of the other sets), these running times are not achievable.

In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time.  Indeed, testing disjointness requires $\Omega(n)$ time, as explained here.  Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$.  Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$.  Now $T_1,T_2$ are guaranteed to have a common element.  So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another.  Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible.  It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.

This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.


Finding the smallest number that scales a set of irrational numbers to integers

I'm assuming that $0 \not \in \mathbb{N}$, otherwise $s=0$ is a trivial solution.

If you input numbers contain at least one positive and one negative number there is no solution.
If your input numbers are all negative, either there is a solution but no smallest solution, or there is no solution at all. You can decide which of the two is the case by solving the same problem on with the numbers multiplied by $-1$.

Assume then that all input numbers are positive.

If $s a_1 = c$ and $s a_2 = c'$ for $c,c' \in \mathbb{N}$, then $c' = s a_2 = c \frac{a_2}{a_1}$, i.e., $\frac{a_2}{a_1}= \frac{c'}{c}$. This shows that you can only find a solution if all your irrational numbers can be obtained by multiplying $a_1$ by some rational factor.

In this case you can consider the set of numbers $\{1, \frac{a_2}{a_1}, \frac{a_3}{a_1}, \dots, \frac{a_n}{a_1}\}$ instead. Since they are all rationals you can write them as $\{1, \frac{b_2}{c_2}, \frac{b_3}{c_3}, \dots, \frac{b_n}{c_n}\}$, where $b_i,c_i \in \mathbb{N}$ and $gcd(b_i,c_i)=1$. You can then find the minimum common multiple of the denominators and multiply it by $a_1^{-1}$.


Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

Θ(n log n) means the algorithm is O(n log n) and Ω(n log n), and is slower than Θ(n) so your reasoning is correct.

But there's another layer: Landau notation denotes asymptotic bounds on functions. Saying "worst case" restricts it to those functions which result in the highest run time. For example take binary search: we get a best-case runtime asymptotic of Θ(1) and a worst-case asymptotic of Θ(log n).

To answer your question about the difference between "worst-case Θ(n log n)" and "run-time O(n log n)"*, the first one gives us more information: it tells us it runs about as fast as n log n, where the second tells us it runs at most n log n.

*Technically the second one doesn't tell us for what 'run-time' configuration it is asymptotically approaching, but in that case generally most people mean 'in the worst case this algorithm runs in O(n log n)' when they don't say anything.


Describe in English the pattern in the following regular expressions

The first one is very close, but not quite right. Your phrasing technically allows strings that start with $yyy$, but the language contains no such string. There are lots of ways to fix what you have to incorporate this. For instance, you might try "all strings in which $y$s appear only in blocks of length divisible by $3$ preceded by at least one $x$." You'll want to check that to make sure it's right, of course.

The second one isn't too bad. Notice that a description of the regular expression inside the outermost parentheses might be "an odd number of $c$s followed by an odd number of $d$s." By applying the Kleene star, we allow this to be repeated an arbitrary number of times. Something like "All strings which, if non-empty, start with a $c$, end with a $d$ and alternate blocks of $c$s and $d$s of odd lengths," should be close.

Some general pointers:

Work from the inside out. Describe the subexpressions first, and use those descriptions to describe expressions.
If you're not seeing a pattern, it never hurts to write out some representative strings.
Pay special attention to boundary cases, especially around the empty string. Natural language tends to be a little unclear when it comes to things existing, satisfying properties vacuously, etc.


Recursive, Recursively Enumerable and None of the Above

You can choose the language of the halting problem

$\qquad \displaystyle B_1 = \{\langle T \rangle \mid T \text{ halts on } \langle T \rangle\} \in B$

and its complement

$\qquad \displaystyle C_1 = \overline{B_1} \in C$.

This is fairly standard material. The proof for $B_1$ not being recursive is the well-known diagonalization. Proving $B_1$ to be RE (recursively enumerable) is a tad tricky, involving interleaved simulation of multiple TMs, but is widely documented. If $C_1$ were RE, then $B_1$ being RE would imply that both are recursive; hence $C_1$ is not RE. This illustrates some of the techniques for such proofs in general.


The end of a time slice is costly (need to interrupt the running program, switch over to the kernel, stash away the running process context, restarting another process means loading it's context, cache contents of the processor are now useless and have to be reloaded). You want to do this hopefully only when forced (the running program does a system call, which forces a context switch anyway; a high-priority interruption arrives), but on the other hand you don't want any process to just monopolize the system by never yielding. So sometimes (i.e., by time slice end) you will force it. The "80%" rule of thumb is just that, it works (most of the time, for most workloads, and probably makes very little practical difference if it is 60% or 90%).

Take a look at e.g. Pabla's discussion of the Completely fair scheduler in Linux to get a feel of the problems to be solved. The history of Linux' schedulers is quite enlightening (and people have been reported to be sucked into hacking it, never to be seen again...)


Seeding the Mersenne Twister Random Number Generator

A random number generator has the following simplified pseudocode:

state S;

int random() {
  S = advance_state(S);
  return extract_integer(S);
}

The random number generator maintains an internal state, which in the case of MT consists of an array of words and an index. Every time you want to generate a new number, two things happen: (1) the state is modified in some devious way; (2) the state is compressed to the output word. The entire random number generator is thus a finite state machine which proceeds deterministically from state to state (there is no "input"), while also producing output.

MT is implemented slightly differently by generating several output words at once, but this is just an optimization - you can also implement it in just the way I described.

Here is a simple naive example. The internal state S is a 32-bit word. It is updated by increasing it by 1. The output is the least significant bit. If S is seeded by 0, then the first few outputs are 0, 1, 1, 0, 1, 0, 0, 1, ... (the first $2^{32}$ bits in the Thue-Morse sequence).

How does the internal state get initialized? There are two ways. One way is to give the entire internal state. The other way is to give a smaller "seed", and from the seed generating an internal state in some devious way. If we do it deviously enough, then the function associating a seed with the resulting internal state will look like a random function (in other words, it will seem as we're selecting $2^{32}$ different random internal states, when the seed is a 32-bit integer).

The cryptographic strength of the second way is only 32 bits - you only need to try all $2^{32}$ different seeds in order to complete a given sequence. If you care about that and the seed is too short for your taste, you can use the first method and come up with an entire internal state, though that's usually not necessary, and certainly isn't necessary if all you want is random numbers for simulation purposes. (If you want cryptographically secure random numbers, please don't use MT.)

Other ways of seeding a random number generator, which sit on top of these methods, include using a password or passphrase (which is converted to a seed using a hash function) and using random data from your computer (which again passes through a hash function which functions as a randomness extractor).


You are asking (or at least typing) multiple questions that are unrelated.

Time Complexity of the Ackermann function

First, understand that this is not a meaningful query. The Ackermann function, let's call it $A$ (assume a one-parameter variant), is a function, not an algorithm. You can certainly talk about $\Theta(A)$.

What you likely mean is the time $T_A(n)$ required to compute $A(n)$. I do not know of any algorithm besides explicitly computing the recurrence; the runtime of this approach can be investigated using the standard approach. It's unlikely that the result will be a meaningful $\Theta$-asymptotic in terms of the "usual" basic functions; you'd get runtime bounds expressed in $A$ itself.

That does not mean that there is no faster algorithm; it would not contradict the growth of $A(n)$ per se. Depending on your computational and cost model, you can compute huge numbers with little cost.

Are all primitive-recursive functions in $O(A)$?

Yes. That is (a consequence of) how we show that $A$ is not primitive recursive.

Note that here we are back to comparing values of the functions again; no mention of "time complexity" is being made.

Can all primitive-recursive functions be computed in time $O(T_A(n))$?

Not knowing $\Theta(T_A)$, I do not have an answer to this question.


Source entropy and other questions related to information theory

If you look at wikipedia you see that topological entropy is modeled after Kolmogorov-Sinai (KS) entropy, but it is defined without reference to a probability measure $\mu$ on the space.

For KS entropy, you need to use Shannon entropy: $-\sum_i\mu(X_i) \log \mu(X_i)$ for some partition of the space $\{X_i\}$, which can only be defined if you have some probability measure $\mu$ on your space, while topological entropy is defined without reference to a probability measure.

Since putting different probability measures on the space will give different KS entropies, while not affecting the topological entropy, these entropies are different. However, they are related by the theorem that the topological entropy is the supremum of the Kolmogorov-Sinai entropy over all probability measures $\mu$.


How can I minimize floating point error when multiplying normal distribution PDFs?

While there is an entire subject that studies how to prevent or reduce floating point errors from piling up, it happens we have a shortcut here.

Let $\mathcal N(u, \sigma)=\frac{1}{\sqrt{2\pi\sigma^2} } e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$ , the normal distribution with mean $u$ and standard derivation $\sigma$.
Suppose we are given $n$ Gaussian normal distribution $\mathcal N_i(u_i, \sigma_i)$ . What is the product of $n$ of them? It turns out,

$$\prod_{i=1}^n \mathcal N(\mu_i,\sigma_i)= s\mathcal N (\mu,\sigma)$$
where
$$
\frac1{\sigma^{2}} = \sum_{i=1}^n \frac1{\sigma_i^{2}}\,, \quad
\frac\mu{\sigma^2} = \sum_{i=1}^n \frac{\mu_i}{\sigma_i^{2}}
$$
and
$$
s =  (2\pi)^{\frac{1-n}2} \frac{\sigma}{\prod_{i=1}^n \sigma_i}\exp\left(\frac12 \left(\frac{\mu^2}{\sigma^2} - \sum_{i=1}^n \frac{\mu_i^2}{\sigma_i^2}\right) \right)
$$

If you use the above formula to compute, floating point errors should not be a concern any more.

Please note the reference you used is misleading in the sense the product function is not a probability distribution function.

Exercise. Prove the above formula for the product of $n$ normal distribution.


The minimum pumping length $\ell$ of $(01)^*$ is $2$.
First of all notice that there are no words of length $1$ in the language.
Then, if you look at a formal definition of the pumping lemma for regular languages (what you wrote is still informal) you'll find that the length $|xy|$ of the prefix $xy$ of a word in the language that can be pumped must be $\le \ell$.
This allows you to prove that the minimum pumping length $\ell$ must be $2$ by showing:

That there is a DFA for $(01)^*$ that uses at most $2$ states, implying $\ell \le 2$. This DFA is trivial to obtain.
That $\ell=1$ is not a valid pumping length. This is true since $|y|$ must be positive and, together with $|xy| \le \ell$, this implies $|y|=1$. In other words $x = \epsilon$ and $y=0$. It is easy to obtain a word not in the language by repeating $y$ either $0$ or at least $2$ times.


Subset with modified condition, is it still NP-complete?

What precisely are the problems? I may be missing something (and cannot do comments yet). Are they

(1) Given a set $A \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \le M$.

(2) Given a set $ \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \ge M$.

If so these problems seem clearly in $\mathbf{P}$, basically by the reasoning you described -- we just want the minimum/maximum possible subset sum, and then we compare that with $M$. Assuming empty $S$ is allowed:

for (1), add up all the negative numbers in $A$ and see if it's $\le M$. If Yes, then return yes. If not, return No.
for (2), add up all the positive numbers in $A$ and see if it's $\ge M$.

Again I may be missing something, but it seems like the other answer's reduction might not be addressing the possibility that $SS_\le$ and $SS_\ge$ would return yes based on different sets? Like consider input $A = \{1, 3\}$ and $M=2$.


My best guess: a student process is a process run by a student.

All users have to log in. The OS may well know various types of users, and may be able to determine from some table that a given user is a student. This can be useful to lower their priority for computer time in a shared machine used mainly for research, or possibly do the opposite during exam period. So having a scheduling queue for student processes would make sense.

As far as I know ... there is no direct relation to learning machines who would run processes that are studying something. But who knows? It may be coming.


Most efficient way to check if key exist on a table

Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.


Finding the shortest path in a n-dimensional grid

It's easy: first get the 1st dimension right, then the 2nd dimension, then the 3rd dimension, etc.

For example, if you want to get from $(1,3,0)$ to $(3,4,1)$, you go via the following sequence of points: $(1,3,0), (2,3,0), (3,3,0), (3,4,0), (3,4,1)$.


Will random function ever hit a hard coded decimal number?

Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 <= rnd < 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0.123456 will never be hit.
But even if 0.123456 would be hit eventually, that random number generator would produce 2^53 possible values. On average it needs to produce 2^52 values before a match. That isn't going to happen within two hours. Assuming 10ns per number, 10ns * 2^52 is about 45 million seconds, or 521 days.


finding maximum virtual and physical memory

No, you can't get size of physical memory with the provided information.

Explanation:

Virtual memory that you mentioned is correct. But you can calculate
it just by seeing the number of bits virtual address has (What you
did is correct though).
To calculate the physical memory, we need to know that Physical memory is a collection of frames, which has same size as pages. Since
Page size is already given (4KB), next we need to know how many
frames does main memory(physical) has. For this we need to know the
size of page table entry, which contains frame address. If we know frame
address length, then we can calculate the total number of frames by
calculating  2^(length of frame address).
Then you can multiply the frame size (4KB) with the above value to get the size of Physical memory.


How to prove LTL-formulas true for all paths?

The statements you wrote are tautologies, i.e. they are always true. I will give you an example proof for the arguably easiest statement $FXp \leftrightarrow XFp$ so you see how you could do it yourself for the others. Also, it would be good to know if you are working on finite or infinite paths. I am going to use infinite paths here because that is more common as far as I know.

The statement says "There is a point in the future so that at the next position $p$ holds if and only if there is a point in the future other than the current point at which $p$ holds.

We can describe the path with the single predicate $p$ by a set $A \subseteq \mathbb{N}$ at which $p$ is true, and $\mathbb{N} \setminus A$ at which $p$ is false. Let $n \in \mathbb{N}$ be any position.

If $n \models FXp$, this is (by definition) equal to: there is a position $m \geq n$ such that $m \models Xp$, which is equal to $m+1 \models p$, which is equal to $m+1 \in A$. In other words: $n \models FXp$ if and only if there is an $m \geq n$ such that $m+1 \in A$.

If $n \models XFp$, this is equal to $n+1 \models Fp$, which means there is an $m \geq n+1$ such that $k \models p$, so $k \in A$. Again, this means $n \models XFp$ if and only if there is an $k > n$ such that $k \in A$.

You can see that these two statements are clearly equivalent if you choose $k = m+1$. Therefore, $n \models FXp$ iff $n \models XFp$.


How to find the big O notation of $\log^b x$

How would you determine big o notation for this? I don't think you can simply do O(log(x)^b) can you?

$\mathcal O\left(\log^b x\right)$ or $\mathcal O\left(\left(\log x\right)^b\right)$ is correct.

  x^3 + log(x)^b

Assuming $b$ is a constant. You always take the fastest growing term in a polynomial. $T(x)=\mathcal O\left(\log^b x\right)$ is called polylogarithmic time. In this case, $\mathcal O\left(x^3\right)$ grows faster than $\mathcal O\left(\log^b x\right)$.

You can see a list of different complexities (sorted from lowest to highest) here.


Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$

Your PDA accepts the language
$$ \{a^{i+j} b^{i+2j} : i,j \geq 0 \}, $$
which is different from the one you are interested in. In fact, you can show that it equals
$$ \{a^kb^\ell : k \leq \ell \leq 2k \}. $$


How can I prove this language is not CFL?

The easiest way goes as follows: if $L$ were context-free than so $L \cap a^*$ would be. Now $L' = L \cap a^* = \{ a^m : m \text{ is prime}\}$ is a unary language, so $L'$ is context-free iff it is regular iff it is eventually periodic. If it were eventually periodic then it would be either finite or have finite asymptotic density, but we know that primes are infinite and have zero asymptotic density.

You can also prove that $L'$ is not context-free using the pumping lemma. The pumping lemma shows that for some $p$, every prime $q > p$ satisfies the following: there is $1 \leq t \leq p$ such that $q + (\ell-1)t$ is prime for all $\ell$. Choosing $\ell = q+1$, we get that $q(t+1)$ has to be prime, which it isn't.


Characterization of computationally universal functions

Several authors have considered this question. If you look at some recent work, it will cite older work. The most recent I am aware of is Pieter Hofstra's and Robin Cockett's work on Turing categories, see Definition 3.1 in their Introduction to Turing categories.


First of all, don't have a head pointer in your structure that doesn't point to the head of the list: it will confuse everyone. Call the pointer in your structure next or something!

You are right that in a singly-linked list (one with a next pointer but no pre pointer) it is illogical and inefficient to add new items to the end of the list. Singly-linked lists work best when you add each new item to the beginning of the list. Then all you need to do is:

Create a new item and fill in its data.
Set its next pointer to the value stored in the global head variable.
Set the global head variable to point to the new item.

Thus, as you say, only the first item to be added to the list will have next=null.

Adding items to the end of the list involves walking through the whole of the list every time, which is not efficient or sensible.

If you wanted a singly linked list to which you could add items at the end, you would have a second global variable (call it tail) pointing to the last item in the list. This makes for inelegant code, since you now have different kinds of behaviour when tail is null (which it will be at the beginning) and when tail is not null. In fact, a good way of handling matters in this case is to create the list with one fictional item in it already, and tail pointing to that item. This saves a lot of tests, but you will of course have to remember, when walking through the list, not to pay attention to that fictional item.


How does this unsigned subtraction work?

In your example, what you are really doing is
$$
15 - 14 \equiv 15 + (16 - 14) \pmod{16}.
$$
To compute $16 - 14$, you first compute $15-14$ (flipping all bits), and then add $1$ to get $16 - 14$.


Your question is strange. If you do not know what kind of language you
have, the question may well be meaningless, as the concept of
ambiguity can only be defined with respect to a known system of
enumeration of the sentences of the language. There is none if the language is not Recursively Enumerable.

Thus it does not make sense to ask whether a language is ambiguous in
general.

I take this as an opportunity for a little survey of these types of definitions.

In your case, if you specified that your language is context-free (but
you did not), the question makes some more sense since CF languages
have at least one CF grammar, which can be used as reference rewriting
system to generate the sentences of the language (assuming you
restrict to leftmost derivations, as canonical representatives of
equivalence classes of derivations).

However, each CF language has actually an infinity of CF grammars
generating it, and ambiguity has to be defined with respect to a
single generation system. Hence the concept of ambiguity makes sense
for the language of a given CFG with respect to that CFG, but does not
make sense a priori for the langage alone.

However, computer science developed the concept of inherent
ambiguity.

  A CF language is inherently ambiguous iff all CF grammars generating that
  language are ambiguous.

It is however becoming common to say that a CF language is ambiguous
to mean that it is inherenlty ambiguous.

Notes:

Given any CF grammar G, it is trivial to give an ambiguous
CF grammar G' that generates the same language. So, what can be
interesting is not to know whether a CF language may have an ambiguous CF
grammar (that is always possible), but whether it has only ambiguous CF
grammars.
This refers only to CF grammars. It is possible that an inherently ambiguous CF language can be generated unambiguously by a grammar that is not CF. For example, I would conjecture that there is an inherenlty ambiguous CF language that can be generated by an unambiguous Tree Adjoining Grammar (TAG) (but I do not know whether it is true or easy to check).
This kind of knowledge organization framework can apply to other properties related to the generation or recognition process associated with a language. A good example is determinism of automata of a given family recognizing the language.
Precision is always important: a language may be inherently non-deterministic with respect to a left-to-right PDA recognizer, but not when the PDA recognizer is right-to-left.
This kind of framework, whether for ambiguity or other properties, can also be developed for other families of
languages and enumeration mechanisms (possibly up to some notion of
generative equivalence, such as the order of rule application in the
case of CF grammar derivations).

Hence your question should be better phrased as:

If I am given a language L that is Context-Free, is there any
technique to prove that it is not ambiguous.

It is even better if you say "... that it is not inherently
ambiguous".

Note that even there, there is the implicit assumption that you refer to the leftmost derivations of CF grammars.

In the case of CF languages and grammars, you have many answers that
you can find on the CS Theory site at the question Ambiguity in
regular and context-free languages.

In particular:

it is undecidable whether a given CF grammar is ambiguous (1962-63, Cantor - Floyd - Chomsky and Schutzenberger)
it is undecidable whether a given CF language is inherently ambiguous (Ginsburg and Ullian - 1966).


Hint: Let $A = \{ a_1,\ldots,a_n \}$. Choose a large number $M$ and consider the set $\{ M + a_1, \ldots, M + a_n, M, \ldots, M \}$ ($n$ times the number $M$) and the target $nM + C$. If you want an actual set, instead of taking $n$ times the number $M$, take $M,2M,4M,\ldots,2^{\lceil \log_2 n \rceil}M$ (we assume that $0 \notin A$; otherwise, remove $0$ from $A$).


How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?

The google indexing and search is run in parallel using a map-reduce algorithm.
As the number of pages to index expands, so does the number of computers that google uses for the task.

Currently Google handles about 3.5 billion searches per day.
A single search uses 1 000 computers in parallel (each computer holds $\frac{1}{1000}$ of the total Google index) and takes on average 0.2 seconds.

Servers available for search are always in read-only mode. When the search index gets updated those servers are temporary unavailable for search.

Given the current amount of floor-space in its data centres Google has a maximum of about 1.7 million servers.
Obviously most of these are devoted to something other than search.


Algorithm for finding best combination of elements

You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.


Is there an example of an AVL tree that is taller than a binary heap?

Consider the following AVL-tree with 7-nodes. It has 4 levels.
The form of a binary heap is determined by the number of its nodes. With seven nodes it would be the perfectly balanced binary tree with 3 levels.

An AVL-tree is height balanced, in the sense that the height of two sibling subtrees never differs by more than one. Leaves however may exist on several levels. Binary heaps are much more rigidly structured. Leaves exist only on two  levels, and nodes are added level by level, from left to right.

The example tree is of a special type: it has the minimal number of nodes to get a tree of this height.

OK for an exercise, but it is quite uncommon to compare AVL-trees and binary heaps. The value of the nodes are ordered in completely different ways. Also binary heaps are in fact implemented as arrays, not as pointer structures.


Where can a student learn image processing?

There are books on digital image processing which you can look into. Many common image manipulation techniques, such as smudging (usually known as blurring) are accomplished by image filtering, which is a process of applying a two-dimensional filter to an image: the value of each pixel in the new image is a linear combination of its original value and the original values of its neighbors. Sepia tone is an example of color manipulation: assuming the image is stored as RGB, this amounts to applying some carefully constructed mapping on the R,G,B values of each pixel. The mapping can be represented as a table $\{0,\ldots,255\}^3 \to \{0,\ldots,255\}^3$, or alternatively some formula can be applied instead.


Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law

You have the basic rule that (a or b) = not (not a and not b), so you use that repeatedly. The first application gave you B~CD + ACD = NAND(~(B~CD), ~(ACD)). You're almost there:

NAND(~(B~CD), ~(ACD)) = NAND (NAND (B, ~C, D), NAND (A, C, D))
 = NAND (NAND (B, NAND (C, C, C), D), NAND (A, C, D))


Thought process to solve tree based Dynamic Programming problems

I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type.  It also really helps to program them in (e.g.) Python so that you get some hands-on experience.

So, perhaps it is better to start with a simpler tree problem first, like (weighted) Vertex Cover or (weighted) Independent Set?

In both these cases (they are similar, but let us focus on Vertex Cover), the
entire solution of a subtree can be summarized in the root of the subtree with
two numbers: the optimal solution if the root of the subtree is in the vertex
cover, and the optimal solution if the root of the subtree is not in the
vertex cover (but covered from below).

So the plan is to store, for each node $u$, two numbers, $u_{\text{in}} = c_i$
and $u_{\text{in}} = c_o$, and in the end, we will look at what are the values
in the root node $r$, i.e. $r_{\text{in}}$ and $r_{\text{out}}$.

The Algorithm

The algorithm is then quite simple.  For the base case, starting at the leaves, in leaf node $v$, you store $v_{\text{in}} = w(v)$ and $v_{\text{out}} = 0$.  Clearly, in the subtree with only one node, there are no edges to cover, so this is quite easy.

Then the rest of the algorithm is given a node $v$ with children $u_1, \dots, u_d$, we need to compute two cases.

$v$ is in the vertex cover: then the optimal solution is $v_{\text{in}} = w(v) + \sum_{u \in u_1 \dots u_d} \min(u_{\text{in}}, u_{\text{out}})$
$v$ is not in the vertex cover, so all children must be, hence $v_{\text{out}} = \sum_{u \in u_1 \dots u_d} u_{\text{in}}$

Now, the only thing we need to do is return the result of the root node $r$, which can either be in or not in the vertex cover, so we return
$$ \min( r_{\text{in}}, r_{\text{out}}) $$

In other words, we found out what information we need in the "separator" of a
subtree, and how can combine the information from the subtree with the rest of
the tree.

Exercise: Solve Weighted Vertex Cover and Weighted Independent Set on trees.
Exercise 2: Solve Weighted Dominating Set, which needs one more state, namely in the dominating set, not in the dominating set but dominated, not yet dominated (dominated from above).


Need help regarding random password generator: Urgent

There's really no way to do this. First, the website generating the password would need to be open source, or at least publish what algorithm they use. Supposing they do that, then we would need to know the "inputs" to the algorithm. That would depend on their source of randomness: it might be the microsecond that your query was submitted, or it might be random mouse movements, or it might be random atmospheric data. It's also possible that the website uses some "secret salt" in addition to the randomness source, so that their results can't be replicated from the randomness alone.

Really, we have two situations. Either the password can't be recovered/explained, because the website is using proper security to make sure that your password is secret. Or, you can fully recreate the inputs to the algorithm, in which case someone else could, meaning that your password isn't very secure.

There is a third possibility, which is that this website isn't legitimate, and it's deliberately returning things with Malay profanity. I'd try generating another password to see. But in all likelihood you're just terribly unlucky.


I don't know anything about routing, so take this with a grain of salt.
What you have is a metric graph, in that your graph satisfies the triangle inequality.  If you start removing edges, then  heuristic algorithms might have less to work with, which isn't obviously better.
Take for example a look at these questions:

Bottleneck TSP with MST
For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

Taking removing edges to the extreme is actually how Christofides algorithm works for approximating Travelling Salesman; Namely by finding a Minimum Spanning Tree and deleting all the remaining edges.


How does Rogozhin's (2, 18) universal turing machine work?

I see (at least) two errors:

The head position should be at the beginning of $S$; and there is an extra 1 at each $P_i, i > 1$: $P_i = bb 1^{N_{i_{m_i}}}1b....b1^{N_{i_2}}1b1^{N_{i_1}}$

c⃖₁ c⃖₁ b  b  1  1  b  1  b b >1  c  1  c  1  c
                 ^            ^
                !!!          !!!

Don't forget that the rest of the tape should be fille with $1^{\leftarrow}$ (the balnk symbol).

A few years ago I also examined its behaviour; you can find the javascript version I made here: click "Small" to load it, then fill the tape (click on the second gray row to place the head), and click "Step". You can compare it with your implementation.


Can FPSPACE give exponentially long outputs?

Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only allowed to use a bounded amount of space.  This definition is necessary for something like LOGSPACE to make any sense: if you counted the output as part of the space used, then even an algorithm such as "just output the input" wouldn't run in LOGSPACE. That's important because we often want to use LOGSPACE reductions between problems.

A simple example of a (nontrivial) FPSPACE algorithm that produces exponentially much output is a SAT solver that just tries every possible combination of values for the variables and outputs the combinations that satisfy the formula.  This will produce exponentially long output for the class of inputs $X_1\lor\dots\lor X_n$.

Note that, for TIME-bounded complexity classes, we don't have this kind of problem since, on a Turing machine, writing $\ell$ symbols of output always takes at least $\ell$ time steps so, e.g., a polynomial time machine can only produce polynomially much output.


Is selection in genetic algorithm considered to be a genetic operator?

One of my first Google hits is a widely-cited article:

Eberhart, Russell C., and Yuhui Shi. "Comparison between genetic algorithms and particle swarm optimization." In International Conference on Evolutionary Programming, pp. 611-616. Springer, Berlin, Heidelberg, 1998.

The third paragraph of the article says:

  Regardless of the specific implementation, it is generally agreed that GAs utilize one form or another of three operators: selection, crossover, and mutation.


Compare regex in programming languages with regular expression from automata/formal language?

In programming, "regular expressions" are used for searching (if a match happens in the string), not for simple accepting. I.e., it is as if what is written is .*your-re-here.*.

It is often of interest to know not only if it matched, but exactly where. And so the above isn't all the story, most RE machines also look for the longest match. For simplicity, many RE libraries don't handle alternation (e.g. ed(1) in Unix of yore didn't), as characters, character classes, star applied to the last character, and anchors (beginning/end of line) were enough to handle 90% or more of the "text editing" requirements. And that can be written in simple, short code.

Furthermore, depending on the exact machinery used, it is more or less easy to extend the "regular expressions" with non-regular constructs, like "match what matched between parenteses before", like ([a-z]*) \1 to mean "the same word twice, separated by a space". Such constructs are handled e.g. in vi(1), as tasks like the mentioned are useful to catch typos (a common error is to to write the same word twice).


Can a petri net fire only one transition at a single moment?

Both.

Only one transition being able to fire at a time is known as interleaving semantics. Multiple transitions firing simultaneously is known as step semantics. Some people doing concurrency theory only call the latter real concurrency, and they care deeply about the difference; I'm sure the difference has consequences, but I've worked with Petri nets and I've never run into a situation where it mattered.

In a Petri net editor I used to work on, durations could be assigned to transitions - so these "transitions" represent tasks or processes that take a certain time. Once that is possible, clearly it makes a great difference whether two of them can be firing at the same time or not. But I would say such "timed transitions" really aren't transitions; rather, they are shorthands for a transition (start), a place (executing), and another transition (termination).


Adaptive Radix Tree - Question regarding child indexing

The red values in the image shows key values associated with a location.

Node4 works by performing a linear search for the key byte in the 4-element key array. If we were looking for key value 255 in the image you posted, we'd find at array index 3. We then find the corresponding child by looking at index 3 in the child pointer array.

Node256 is just an 256-element array of child pointers indexed by key byte, yes.

The problem with Node256 is that it wastes a lot of space if most of the array is empty. Node48 uses much less space by exploiting the fact that a pointer is much larger than a byte (typically 8 bytes). We have an 256-element array of bytes (the child index array), one for each key value. When we index into this array, we get a byte that is an index into the 48-element child pointer array. So the lookup is something like this (the actual implementation is slightly different):

Node *find(Node *node, byte key) {
    idx = node->child_indexes[key];
    // Index == 255 is element missing
    if idx == 255 { return null; }
    return node->children[idx];
}

Since the child index array has 256 elements we can just index it with the key byte, no need to search like in Node4 and Node16. But as you say, we only have 48 child pointers, so at most 48 positions in the child index array will be in use at any one time. The elements are small though, so it is not much of a waste.


An algorithm that find the max X/Y in a polygon in O(log n)

Assume the polygon is a convex polygon; otherwise there might not be an $O(\log n)$ algorithm to find the maximum of X-coordinates or Y-coordinates.

First, let us handle the case of X-coordinate.

Let $x_1, x_2, \cdots, x_n$ be the X-coordinate of the points. Since $x_1$ is the minimum X-coordinate, that sequence is a bitonic sequence. Here are two nice answers to how to sort a bitonic sequence.

Next, let us solve the case of Y-coordinate, which is mildly more complicated.

Let $y_1, y_2, \cdots, y_n, y_{n+1}=y_1$ be the Y-coordinate of the points. We can drill down into the following cases by comparing $y_1$ against $y_2$ and against $y_n$.

$C_{\lt, \lt}$ when $y_1\lt y_2$ and $y_1\lt y_n$. Here $y_1$ is the minimum.
$C_{\gt, \gt}$ when $y_1\gt y_2$ and $y_1\gt y_n$. Here $y_1$ is the maximum.
$C_{\lt, \gt}$ when $y_1\lt y_2$ and $y_1\gt y_n$. Here Y-coordinates goes up from $y_1$ to the maximum, then goes down to the minimum, then goes up to $y_1$.
$C_{\gt, \lt}$ when $y_1\gt y_2$ and $y_1\lt y_n$. Here Y-coordinates goes down from $y_1$ to the minimum, then goes up to the maximum, then goes down to $y_1$.

The first two cases are bitonic sequences, which can be treated as before.

Let us check the case of $C_{\lt, \gt}$; the case $C_{\gt, \lt}$ can be handled similarly.

Let $y_M$ is the maximum and $y_m$ is the minimum, where $M<m$. Given an index $1<i<n$, we can compare $i$ to $m$ and $M$ as follows:

If $y[i-1] < y[i] < y[i+1]$ and $y[i] > y_1$, then $i < M$.
If $y[i-1] < y[i] > y[i+1]$, then $i = M$.
If $y[i-1] > y[i] > y[i+1]$, then $M < i < m$.
If $y[i-1] > y[i] < y[i+1]$, then $i = m$.
If $y[i-1] < y[i] < y[i+1]$ and $y[i] < y_1$, then $i > m$.

The above result enables us to cut the search intervals in half each time with 2 or 3 comparisons, thus ensuring an algorithm with $O(\log n)$ time-complexity.

Exercise. What about the case when we have a sequence of $n$ distinct numbers, in which there are $t$ local maximums and $t+1$ local minimums?


A problem is NP-hard iff its complement is coNP-complete

This argument is given for any complexity class.

If $C$ is a complexity class (for your question NP) and $L$ is $C-Hard$ (an 'identical' argument can be for complete languages):

If $A \in coC$ so $\bar A \in C$  so $ \bar A \le L$: ($\phi$ is the Karp-reduction for that matter)

$ \exists \phi.x\in \bar A \iff \phi(x)\in L $

Since it's iff the negation is:

$ \exists \phi.x\notin \bar A \iff \phi(x) \notin L$

Hence, (by definition of complementary)

$ \exists \phi.x\in A \iff \phi(x) \in \bar L$

$A \le \bar L \implies \bar L \in coC-Hard$

Negating the answer of an NP Turing machine won't help you to decide a language in coNP (except for trivial cases like language in P), since by definition an NP Turing machine accepts iff there exist an accepting branch in its' computation.

For simplicity, assume your NP Turing machine always has a rejecting branch in every computation (we can assume it for every NP Turing machine, why?), negating the answer will result in the trivial language $\Sigma $* every-time.


Does a PDA immediately accept if at final state with empty stack?

There are two ways in which a PDA may accept:

Final state: The PDA has finished reading the input and it is in the final state
Empty stack: The PDA has finished reading the input and its stack is empty.

The PDA in the example you have provided is non-deterministic, and when non-deterministic systems read an input for which a transition is not defined, they get stuck. In this case, when the PDA reads the string aaabbba, it would get stuck after reading the last b.


What is usually meant by saying that a (not necessarily binary) function  is computable in $O(\log n)$ space, is that there exists a Turing machine computing it which uses only $O(\log n)$ space in its work tape. This limitation does not concern the output tape, which is write only. You can also think of this condition as being able to, given $i$, output the $i$'th bit of the circuits description using only $O(\log n)$ space.

A circuit family $\{c_n\}_{n\in\mathbb{N}}$ is logspace uniform $NC^k$ iff $c_n$ is a circuit with $n$ inputs of size $poly(n)$ and depth $O(\log ^k n)$, and additionally, there exists a logspace Turing machine such that given $1^n$ as input, outputs a description of $c_n$.


Finding infeasible sets of constraints (CSP)

If your system of constraints is expressed as a SAT instance, then this is known as the MAX-SAT problem.  MAX-SAT is harder than SAT, but there are standard algorithms.  The case of other discrete constraints can be reduced to Weighted MAX-SAT.


Average-case analysis of linear search given that the desired element appears $k$ times


Is time complexity more important than space complexity?

In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon which applies to the cryptography as well.

There are much more about time-complexity to talk about in computer science and software industry while space-complexity is more restricted to hardware. It occurs to me that there are over 10 times more tasks/techniques/concepts/results/articles about time-complexity than space-complexity. Overwhelmingly, programming contests are about time-complexity.
Space/memory can be reused easily. Available space can be expanded easily. On the other hand, time needed for computing cannot be shorten that easily. Parallelization helps, but it cannot speed up the serial part of the program. Practically and relatively speaking, we are enjoying the cheap memory now while we are still hungry for computing speed.

Now come to the cryptography side of the question.

As you have observed, most algorithms in cryptography have $O(1)$ space time-complexity. Although space might be critical such as in embedded devices, there is not much value of space-complexity in general.
On the other hand, the time-complexity is the critical factor of a cryptographic algorithm, especially in encryption/decryption. It should produce data fast enough. Authorized users should be able to retrieve the plaintext fast enough while adversaries do not have fast algorithms to decrypt the ciphertext.


The Hamming bound is an upper bound on the size of codes. It's not a tight bound in general, though in some specific cases it is achievable. Codes achieving the Hamming bound are called perfect codes.

When the alphabet size is a prime power, all perfect codes are known: apart from some trivial cases (repetition codes, codes with one codeword, and codes containing all possible codewords), they share the same parameters as a Hamming code or a Golay code.

What this means is that if your alphabet size is a prime power and you have parameters satisfying the Hamming bound, then a code with these parameters actually exists only in the cases listed above. In any other case, the bound isn't tight.


Weighted Set covering problem with a fixed number of colors

General advice

The question is confused about what you are looking for.

There is obviously no hope for a polynomial-time algorithm that finds the optimal solution to this optimization problem.  This problem is at least as hard as weighted set covering (without coloring restrictions).  Weighted set covering is NP-hard.  Therefore, your problem is NP-hard.  Therefore, any general polynomial-time algorithm that always outputs the optimal solution to your optimization problem would imply that $P=NP$ (which seems unlikely).

Obviously, if the question is confused about what you're looking for or if you are unable to communicate it in the language that computer scientists understand, then that reduces the likelihood that anyone will be able to answer your question in a way that helps you.  We're not mind-readers.

Based on your comments, I suspect that what you actually want is an approximation algorithm for your problem, or a heuristic algorithm.  So, here is my advice, based upon my inference of what I suspect you actually want (as opposed to what you said you want).

First, I suggest that you learn about approximation algorithms and heuristic algorithms.  Learn the terminology, learn some basic results, learn some of the standard examples of approximation algorithms.  This will help you communicate with others and be able to express your requirements clearly in a language that other computer scientists can understand.  Also learn about standard strategies for dealing with NP-completeness (e.g., Dealing with intractability: NP-complete problems).

Second, I suggest that you take a closer look at the sort of problem instances typically arise in your application.  If you want to maximize the chance you find an approximation algorithm or heuristic algorithm that is useful in your application scenario, you need to analyze the parameters and properties of the problem instances that arise in your application.  What are typical values of $k,m,n$?  That's the sort of question you should be asking (and communicating in the question).

Without that kind of information, I don't think anyone here can predict what the best approach to your particular problem might be.  However, I'll suggest some candidate approaches that you could try out.

SAT solvers

You can formulate (the decision problem version of) your problem as a SAT instance and then try solving it with an off-the-shelf SAT solver.

We'll solve the decision problem version: given $u$, we'll test whether there exists a solution of total cost at most $u$.  Introduce boolean variables $x_1,\dots,x_k$.  The intent is that $x_i=1$ means that the $i$th set $S_i$ is selected, and $x_i=0$ means that it is not.  Also introduce variables $c_1,\dots,x_k$, where $c_i\in \{1,\dots,m\}$ represents the color assigned to the $i$th set (if it is selected).  Note that each $c_i$ can be represented as a number of boolean variables using standard techniques.  Finally, introduce variables $y_0,y_1,\dots,y_k$, where $y_i$ is an integer that represents the total cost of all sets that were selected from out of the first $i$ sets.  Each $y_i$ can be represented as $\lceil \lg (u+1) \rceil + 1$ bits, using binary encoding.

Now we're going to add some constraints to capture the requirements for a solution to be valid.  For each element $u \in U$, we'll add a constraint to require that element $u$ is covered by at least one of the selected sets:

$$\bigvee_{u \in S_i} x_i.$$

(Here the logical OR is taken over all sets $S_i$ that contain $u$; at least one of them must be selected.)  Also, for each pair $i,j$ of sets that interfere, we'll add a constraint to require that they have been given different colors: namely, $c_i \ne c_j$.  Finally, we'll add constraints to define the $y_i$'s: $y_0=0$, and for each $i=1,\dots,k$:

$$y_i = y_{i-1} + \begin{cases}
\text{cost}(S_i) &\text{if $x_i=1$}\\
0 &\text{otherwise} \end{cases}.$$

Finally, we'll add the constraint that the total cost is at most $u$: namely, $y_k \le u$.  To deal with overflow, it helps to add constraints that $y_i \le u$ for all $i$ and to make sure you've allocated enough bits for each $y_i$ so that you can encode all integers in the range $0,1,\dots,2u$.

Notice that all of these constraints can be encoded in SAT (i.e., as CNF clauses) in a straightforward way.  Some SAT solver front-ends, such as STP, even provide support to make it easy to express these: they'll convert the integer constraints to CNF by bit-blasting.

Now that you've formed a CNF formula representing the assertion that there exists a solution of total cost $\le u$, you feed it to a SAT solver and see whether it can find a satisfying assignment.  If it can, then you know the optimal solution costs at most $u$; if it can't, you know the optimal solution costs at least $u+1$.  Now you can use binary search to find the optimal solution.

This is not an approximation algorithm: this algorithm finds the exact optimum.  Of course, it is a heuristic.  SAT is NP-complete, so there is no guarantee that this algorithm will run in polytime (and we can be pretty sure that on some problem instances, it won't).  However, SAT solvers are pretty good in practice, and so this might work pretty well on problem instances that arise from practice.

This formulation is a straightforward combination of the formulation of weighted set cover as a SAT problem, and the formulation of graph coloring as a SAT problem (see e.g. here).  If you are having trouble following this, study other reductions to SAT and other ways of encoding standard problems as SAT instances.

Integer linear programming

Another approach would be to formulate this as an integer linear program, then feed it to an off-the-shelf ILP solver.

The approach is very similar to the formulation in SAT.  You can use similar variables to that listed in my SAT formulation above.

Boolean variables can be encoded as integer variables that are restricted to be in the range $0 \le \cdot \le 1$.  Boolean operations on boolean variables can be expressed using the techniques shown here: Express boolean logic operations in zero-one integer linear programming (ILP)

I recommend encoding the $c_i$'s as a one-hot encoding, i.e., introduce boolean variables $c_{i,j}$ where $c_{i,j}=1$ means that the $i$th set (if selected) is assigned the color $j$.  Then you can add the constraints

$$\sum_j c_{i,j} = 1 \text{ for each $i$}$$

and

$c_{i,j}+c_{i',j} \le 1$ for each pair of sets $i,i'$ that interfere and each color $j$.

There's no need for the variables $y_0,\dots,y_k$ or to limit yourself to the decision version of the problem.  Instead, you can make the objective function be

$$\sum_i \text{cost}(S_i) x_i,$$

which is a linear function of the variables (as required).

Now feed it to an ILP solver, and see what the best solution it can find is.

Naive greedy algorithm

There's a straightforward extension of the greedy algorithm, that could be used for your problem.  It will only sometimes find a solution, so it is incomplete; other times, it will fail to find any valid solution.

In particular, at each point in time, we will have a partial solution (some sets that can be colored with $\le m$ colors).  We will incrementally select a set to add to the partial solution greedily.  We can prioritize the sets as follows, to help us select the next set.  The priority of $S_i$ is the number of additional elements of $U$ that would be covered if we selected $S_i$ (over and above the number of elements that have already been covered by our current partial solution), divided by the cost of $S_i$.  Given a partial solution, we find a coloring for the sets (using some heuristic for graph coloring that tries to color them with as few colors as possible), then for each $i$ we see whether adding $S_i$ would increase the number of colors above $m$.  If we can't find a way to color the current selection + $S_i$, then we throw away $S_i$.  Out of the remaining unselected sets, we choose the set with the highest priority.  We repeat until we can make no further progress.

If this process ends with a selection that covers all of $U$, then we have found a candidate solution.  It may not be optimal (it probably won't be), but it is a solution.  If it ends without covering all of $U$, then the algorithm failed.


A,B decidable: proof that A\B is decidable too

Let $M_A$ and $M_B$ be deciders for $A$ and $B$ respectively. You can construct a TM $M$,

$M$ = "On input x,

$\qquad$ 1. Simulate $M_A$ on x.

$\qquad$ 2. Reject if $M_A$ rejects. Else simulate $M_B$ on x.

$\qquad$ 3. Accept if $M_B$ rejects. Else reject."

$Correctness$:

$\qquad$ $M$ always halts as $M_A$ and $M_B$ always halts. $M$ accepts if $M_A$ accepts and $M_B$ rejects i.e, $x \in A$ and $x \notin B$. $M$ rejects otherwise.


If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then
$$
L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}).
$$
Standard closure properties of context-free languages imply that $L^{|2|}$ is context-free.


You don’t exit a deadlock cycle. Once you are in a deadlock situation, you lost. You do your best to avoid deadlocks.

With server software, you may be able to have a process that watches other processes and kills them if they are stuck due to a deadlock. Doing this correctly and make your software continue to run correctly is extremely difficult. It’s so difficult that i wouldn’t even try. In addition it is an absolute pain to test (and you don’t want software that isn’t tested). For normal software running in anything from workstation to mobile phone, it’s just not done. Remember that you have two tasks that are trying to do something and one or both of them have to be killed, that is hard to recover from.

What you do in practice: 1. Instead of locking a mutex you check if it is lockable which avoids deadlocks. 2. You add code that detects situations where a deadlock is possible. And if you find a possible deadlock you fix your code. 3. Write sensible code in the first place.


Why isnt node checked for nil value in start when transplanting binary tree

If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to update $v$'s parent pointer.

Could the code be structured differently? Probably. Why, then, did the authors choose this particular implementation? No deep reason. They programmed the algorithm, and that's the code they came up with. You might have come up with a different code. There's no one right answer in programming.


When are log complexities considered equivalent?

$O(\log(n))$ and $O(\log(n-1))$ contain the same set of functions.

The inclusion $O(\log(n-1)) \subseteq O(\log(n))$ is trivial.
As for $O(\log(n-1)) \supseteq O(\log(n))$, let $f(n) \in O(\log(n))$ and let $c \ge 1$ and $n_0 \ge 3$ be such that:
$$
f(n) \le c \log(n) \quad \forall n \ge n_0.
$$

We have:
$$
f(n) \le c \log(n) = c + c \log(n/2) \le c + c \log(n-1) \le 2c \log(n-1).
$$

Showing that $f(n) \in O(\log(n-1))$.


Based on the comments:

$$S \to 1S00 \mid 100$$


What goes into proving two complicated programs are equivalent?

Formal analysis today is usually done on module or unit level. Unfortunately I'm not aware of a common metric which allows to predict if a formal analysis will be possible. Only structurally very simple codes can be formally analysed even with LOC's or cyclomatic complexities of up to a million.

In your case here the code of any of the two programs is clearly too complex for a full formal analysis:

Model-checking will not work.
A complete (bi-) simulation will not work either.

So the best practical solution I know is model-based testing. While it is not a proof still formal methods can be used. It ultimately eliminates the disaster of writing and maintaining manually written test cases.

P.S.:

A short list of steps which can be done in this case:

An abstract model of the two programs is created. This is a third implementation which will omit all unimportant details. The abstraction has the advantage that this model is simple enough again to be formally analysed. The model can be implemented in any language you like if the model analyser will analyse the byte code.
The abstract model can be traversed and e.g. a condition coverage is reached in a test suite. This step is done using a model-based-testing tool.
Finally these test cases are tested on the two programs and it is checked if the abstract model can simulate the two program implementations.
This simulation relation is of course not a proof of the equivalence.
The abstraction is a very clean specification what was taken into account in our tests and what was omitted.
Two model-based testing tools which can be recommended: Microsoft Spec Explorer, Conformiq Designer


DFAs are regular languages, but regular languages are closed under concatenation

The third paragraph is the correct description how to interpret the statement from your notes. This is also easy to prove: Say $L$ and $L'$ are regular languages described by some regular expressions $r$ and $r'$ respectively. Then $rr'$ describes the concatenation $LL'$ of $L$ and $L'$.