Why do mainstream speech models no longer require a personalized training step?

Have speech models advanced past the need for any personalization of the training data?

There were two aspects which improved accuracy significantly:

Deep learning and neural networks greatly improved the accuracy.
Amount of training data that major companies use has grown over years by order of magnitude. Companies collected so much data that effect of adaptation decreased.

  Or, do they just do the personalization under the covers now, without an explicit training wizard?

There is a small adaptation usually going on, but it is very marginal in effect. It is basically matching your voice with some baseline voices and produces a vector of similarities and then this vector is used in realtime and adjust neural network input (so called i-vector adaptation). This kind of adaptation is pretty fast, you can adapt from 2-3 seconds of speech. For technical details you can read

https://www.microsoft.com/en-us/research/uploads/prod/2018/04/ICASSP2018_CortanaAdapt.pdf

  Or, do they not do training, even though it would still be beneficial (e.g. because it's inconvenient)?

There are some cases where adaptation would be beneficial but again there are multiple aspects here:

It works good without adaptation.
Neural network recognition does not fit well with adaptation actually. You need many many GPU nodes to train a big neural network, it is very hard to adjust it afterwards. You can adjust a small layer with adaptation data but effect is usually small just because neural network is pretty tightly tied thing and you can't simply modify a bit without retraining.
Like I said above the amount of training data is so huge that your custom data is probably already in the training set and adaptation will not help much
Adaptation can also harm. Imagine your speech had an unusual crack or beep from background or something like music and system adapted to it. Then it will actually decode your normal clean speech with less accuracy than unadapted system.
Adaptation is not very convenient for users. Why do you need to adapt when you can simply start using the system.

So the system design moved to the "it just works" and it is a good direction.


Worst case scenario in binary search tree retrieval

Hint: If the tree has height $h$ then the worst number of comparisons is ...? If the tree is "equilibrated by height" (I guess balanced) and has $n$ nodes then its height is ...?


There is some great mysticism around Operating Systems. They are sometimes treated like this dark wizardry that only a handful of the initiated are allowed to understand. (Compilers are treated like that as well.)
Here's the truth, though: an Operating System processes inputs and does something in reaction to those inputs. You know what also does that? Every other program.
An OS is just a program. There is nothing special or magical about it.

But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right?

Why not?
Linux was literally written by accident.
Linus Torvalds saved up to buy his dream machine, the pinnacle of computing at the time: a 32 bit 80386 PC clone. And he wanted to learn how to program the 80386 to get the most performance out of it. He spent a lot of time using a terminal program to connect remotely to the university, but all terminal programs that existed where too slow or too clunky.
So, he decided to kill two birds with one stone and teach himself 80386 assembly by writing a better terminal program. After a while, he realized that if he wanted to really dive into how the 80386 works and wanted the most performance, he should get rid of the Operating System and just boot into his terminal program directly. So, he wrote a boot loader that booted directly into the terminal program. Now, without the OS, he also needed a keyboard driver, so he could type commands into the terminal program, he needed a console driver so that the terminal could print answers back, and he needed a driver for the serial port, so he could connect to the university. Unfortunately, when he wanted to transfer files, he still had to boot into the OS, so he added a hard disk driver and a file system driver to the terminal program. And in order to be able to use the terminal program while it was downloading files, he added multithreading and a scheduler.
It was at this point, that he realized, that he had accidentally written an almost complete Operating System. So, he decided to further play around with it, add some missing features, etc.
Then, one day, he mistyped a command, and accidentally overwrote the partition with his Minix installation, thus destroying the existing OS that was installed on the PC.
Now, he had a decision to make: reinstall Minix or finish his OS. And the rest, as they say, is history.
So, writing an OS is really not that different from writing any other kind of program. Linux is the existence proof of that, because it is just a normal program that accidentally became an OS.


how to identify patterns in program execution flows?

There's probably no existing turnkey solution that will do what you want, out of the box.  I suspect this would be a research-level task, so you might want to start by searching the research literature to see if anyone else has tried to do something like this.  (Google Scholar is useful.)

If you some advice on how to pursue this yourself, my advice would be:

Try to narrow the scope.  Rather than trying to detect all bugs, pick a single class of bugs (e.g., use-after-free would be a fine choice) and see if you can have any success detecting those, as a first step.  If you're successful then you could broaden the scope.
Think now about how you'll obtain enough data to work with.  I suspect one of the biggest challenges will be how to obtain a large training set with known labels, that have many instances of in-the-wild use-after-free bugs, as well as many other traces with no instances of those type of bugs, labelled with whether there was a bug or not and which function invocations were responsible.
Take a look at association rule learning, sequential pattern mining, grammar induction and automata learning (e.g., my links here; e.g., you might try to learn a small automaton that detects use-after-free bugs), and recurrent neural networks (especially LSTM).
Also, you might need to do some feature engineering.  For instance, when you have pointers or handles (like 0x100), you might want to canonicalize them, as the only useful information is whether two calls used the same pointer or a different pointer -- the actual value of the pointer is irrelevant.  Since you have domain knowledge of that fact, by transforming the data before you feed it to the data mining / machine learning framework, you can help it learn a lot faster and more effectively.


How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$

You can use the master theorem.
This theorem allows you to solve some recurrences of the form $T(n) = aT(n/b) + f(n)$.

You need to compare $n^{\log_b a}$ with $f(n)$.
In you case $n^{\log_b a} = n^{\log_2 5}$ and $f(n)=n^2 \log^2 n$.

There are different cases depending on how the above functions compare, but I am only going to discuss the one that is relevant to you (you can find more on Wikipedia).

In your case $f(n) = O(n^{\log_b a - c})$ for some constant $c>0$.
To see this pick, e.g., $c=0.1$ and substitute to obtain:
$n^2 \log^2 n = O(n^{\log_2 5 -0.1})$, which is true since $\log_2 5 - 0.1 > 2$.

The master theorem then tells you that $T(n) = \Theta(n^{\log_b a})$, which in your case is $T(n) = \Theta(n^{\log_2 5})$.


Solving recurrence relations using substitution followed by tree method/masters theorem

For your first method, it is dominated by the first term, not the last.  (The second term is $2^{k/2} * 4 = 2^{(k/2)+2} < 2^k$ for $k$ large.)

In your second method, when you divide each term by $2^k$, you didn't.  You divided the second term by $2^{(k/2)+1}$ instead.


Finding paths with minimum intersections

Let there be $n$ such pairs, and $k$ vertices. Then you can translate this problem into a minimum-cost integer multi-commodity flow problem.

The core trick is to encode the minimum intersections by turning each vertex of your original problem into a triplet of vertices in the minimum-cost flow problem, an input node, and output node, and $n$ edges connecting the input node to the output node. Each edge has capacity $1$, but the costs are respectively $1$, $k$, $k^2$, $k^3$, etc. This ensures that no vertex is visited twice unless there is no more efficient solution, and similarly thrice, etc.

Then connect the output nodes to the input nodes in the flow network as in the original graph. If the original graph was an undirected graph make sure to connect the input and outputs of the pair both ways for each edge.

Finally add a source node of commodity $i$ with demand $1$ and connect it to the input node of each $o_i$, and a sink node for that commodity connected to the output node of each $d_i$.

You can tweak the cost scaling for each shared vertex, that is up to you to decide. Is one triple shared vertex equally bad to two doubly shared vertices? Then use costs $0, 1, 1, \dots$.

Unfortunately minimum-cost integer multi-commodity flow is NP-complete in general, so this does not guarantee any polynomial runtime. But it's a well-studied problem so you might be able to find fast approximations and/or good libraries. Maybe someone else has a better solution, but this problem seems difficult to me to find globally optimal solutions.


Yes, it is possible.  Use

$$h_2(x) = \text{hash}(\text{signature}) - h_1(x) \bmod n.$$

The theory behind this: if $c$ is a constant, the function

$$f(t) = c - t \bmod n$$

is an involution for any $c$ and any $n$, since

$$f(f(t) = c - (c-t) = t \pmod n.$$

Therefore, we can use the hash of the signature as the constant $c$.  This gives you a scheme that works for any $n$, without requiring that $n$ be a power of two.


If you store all of the intervals in a segment tree, then the operation "find all intervals that contain the point $x$" is known as a stabbing query.  Building a segment tree from $n$ intervals takes $O(n \lg n)$ time, but once it is built, you can answer a stabbing query in $O(\lg n + k)$ time, where $k$ is the number of intervals that intersect the point $x$ (i.e., the length of the output of the operation).

In comparison, a linear scan (as described in G. Bach's answer) requires no preprocessing but takes $O(n)$ time to answer each stabbing query.  Thus, if you plan to make many stabbing queries on the same set of intervals, it may be faster to build a segment tree in advance, as each stabbing query can then be answered much faster.

See also interval trees, which have similar properties.


What is the need of re-sampling the image for HOG features?

You are indeed sliding window over the image which has fixed size, but the picture may have different resolution or simply the person in the photo is in some distance from the camera (so the face size in the picture will be related to distance) but your classifier should work anyway, so checking at different sizes is one of the ways to detect people at different depth.


Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

That definitely isn't enough. The set of Turing machines that always halt is countable (being a subset of the countable set of all Turing machines), but very not decidable.
Don't overcomplicate: If you are given a Turing machine, any property of the machine as such (number of states, number of transitions, is it deterministic, ...) that can be checked by a deterministic algorithm is obviously decidable.


Is it admited to give the complexity of a function regarding the resulting data structure?

The running time of a function is usually measured with respect to the length of the input, which is represented by the parameter $n$. In your case, if the input is the integer $m$ then the input length is $n = \log m$ and the running time is $O(m) = O(2^n)$.

For functions whose output is much larger than the input, it makes sense to measure the complexity with respect to the size of the output. In your case, the function runs in linear time with respect to the size of the output.

In other cases it might be meaningful to use other parameters to measure the running time of a function. For example, functions on graphs are sometimes measured with respect to the number of vertices and the number of edges. The end goal is usually to analyze the running time of some function in terms of its input length, but on the way it is OK to measure the running time of subroutines in terms of other parameters.


k-disjoint pair paths where any source can pair with any sink

Your link refers to edge-disjoint paths -- i.e., vertices can visited by multiple paths, but no edge can be visited by multiple paths.  It sounds like you want vertex-disjoint paths -- is that right?  Please edit to clarify.

Both problems can be solved in polynomial time with a Maximum Flow algorithm.

For edge-disjoint paths, put unit-capacity bidirectional edges (i.e., one edge in each direction) between every pair of adjacent vertices; make a super-source $s$, with unit-capacity out-edges to each of the $k$ sources, and a super-sink $t$, with unit-capacity in-edges from each of the $k$ sinks.  The capacity constraints ensure that no edge is used by more than one path.

For vertex-disjoint paths, do the same -- but then replace every vertex $v$ with two vertices, $v_-$ and $v_+$, with all of $v$'s in-edges incident on $v_-$ and all of $v$'s out-edges incident on $v_+$, and add a single directed edge of unit capacity from $v_-$ to $v_+$.


Why isn't deque implemented as a dynamic array?

The reason why std::deque is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to std::vector.

You already partially said it: changing the capacity of an std::vector requires reallocating the memory and copying the entire content to the new memory. While it is true that the std::vectorreallocation scheme achieves a O(1) amortised complexity, the implementation of std::deque guarantees a true O(1) complexity bound for appending.


Minimal requirements for Kleene's recursion theorem

I stumbled upon a (partial) answer myself, in David Madore's essay about quines. I quote,

  A different, perhaps more satisfactory, way of stating the fixed-point theorem would be to eliminate the universality theorem from it, and to say: for every computable function $k$ there exists a $n$ such that $\phi_n(\dots) = k(n\dots)$. This corresponds more precisely to the intuitive content we have described. It is proved without the use of the universality theorem, using only the s-m-n theorem (for the actual proof, take the proof we have just given, and replace $\phi_{h(x)}(\dots)$ by $k(x\dots)$ everywhere). The advantage of formulating things like this is we see that it also works for primitive recursive functions (which satisfy s-m-n but not universality), so in effect a primitive recursive function can also make use of its own number. By applying the universality theorem (the function $\phi_{h(x)}(\dots)$ is computable, so we can call it $k(x\dots)$) we recover the fixed-point theorem as we have stated it.

So Kleene's fixed point theorem goes through at least for primitive recursive functions. It might still be that there's an even simpler class of languages that it also applies to, and I won't accept my own answer in case someone else has more to say on that topic. But for now I'm happy knowing this.


solving Recurrence relation f T(n)=T(n/2)+log log(n)

Let's consider $n=2^k$:
$$\begin{array}{l}T(n)=T\left(\frac{n}{2}\right)+\log\log n = T\left(\frac{n}{2^2}\right)+\log\log \frac{n}{2}+\log\log n = \\
=T\left(\frac{n}{2^3}\right)+\log\log \frac{n}{2^2}+\log\log \frac{n}{2}+\log\log n=\\
=\cdots=\\
=T\left(\frac{n}{2^k}\right)+\log\log\frac{n}{2^{k-1}}+ \log\log\frac{n}{2^{k-2}}+\cdots+\log\log n=\quad(3)\\
=T(1)+\log\log 2 + \log\log 2^2 + \cdots + \log\log 2^k=\\
=T(1)+\log\left[ \log2\cdot \log2^2 \cdots  \log2^k \right] =\\
= T(1)+\log\left[ k!\log^k2 \right]=\\
=T(1) + \log k! +k \log\log 2 \in \Theta(k \log k)\end{array}$$
where $k=\log_2 n$.


How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

$\mu^2(i)$ is 1 if $i$ is square-free, or 0 otherwise.  Therefore, your question is equivalent to asking how to count the number of square-free numbers in the range $1..n$.  That has been studied before; see, e.g.,

Counting Square-Free Numbers, Jakub Pawlewicz, arxiv 1107.4890.

That paper claims it can be computed in $\tilde{O}(n^{0.4})$ time (ignoring polylogarithmic factors).


Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

I haven't read this anywhere, but this is how I believe $Y$ could have been derived:

Let's have a recursive function $f$, perhaps a factorial or anything else like that. Informally, we define $f$ as pseudo-lambda term where $f$ occurs in its own definition:

$$f = \ldots f \ldots f \ldots $$

First, we realize that the recursive call can be factored out as a parameter:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M} f$$

Now we could define $f$ if we only had a way how to pass it as an argument to itself. This is not possible, of course, because we don't have $f$ at hand. What we have at hand is $M$. Since $M$ contains everything we need to define $f$, we can try to pass $M$ as the argument instead of $f$ and try to reconstruct $f$ from it later inside. Our first attempt looks like this:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M} \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}$$

However, this is not completely correct. Before, $f$ got substituted for $r$ inside $M$. But now we pass $M$ instead. We have to somehow fix all places where we use $r$ so that they reconstruct $f$ from $M$. Actually, this not difficult at all: Now that we know that $f = M M$, everywhere we use $r$ we simply replace it by $(r r)$.

$$f = \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}_{M'} \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}_{M'}$$

This solution is good, but we had to alter $M$ inside. This is not very convenient. We can do this more elegantly without having to modify $M$ by introducing another $\lambda$ that sends to $M$ its argument applied to itself: By expressing $M'$ as $\lambda x.M(xx)$ we get

$$f = (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}(xx)) (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}(xx))$$

This way, when $M$ is substituted for $x$, $MM$ is substituted for $r$, which is by the definition equal to $f$. This gives us a non-recursive definition of $f$, expressed as a valid lambda term!

The transition to $Y$ is now easy. We can take an arbitrary lambda term instead of $M$ and perform this procedure on it. So we can factor $M$ out and define

$$Y = \lambda m . (\lambda x. m(xx)) (\lambda x.m(xx))$$

Indeed, $Y M$ reduces to $f$ as we defined it.

Note: I've derived $Y$ as it is defined in literature. The combinator you've described is a variant of $Y$ for call-by-value languages, sometimes also called $Z$. See this Wikipedia article.


Why double error correction and quadruple error detection cannot occur at the same time?

With a hamming distance of five, you can make one of two assumptions:

A. No word has more than four errors. Since you need five changes to get from one valid word to another valid word, and five errors don’t happen, every invalid word has 1 to 4 errors.

B. No word has more than two errors. If you find an invalid word, then it has at most two changes from a valid word. To reach any different valid word would take at least 3 more changes, so there is only one valid word within two changes, so you can fix the errors.

But you can’t assume both at the same time. If you find an invalid word, it could have two or four errors, and trying error correction would give you a totally wrong result.

If you have a hamming-distance of 7, you can indeed detect up to four errors and fix up to two errors at the same time. A word with four or three errors cannot be made valid with 1 or 2 changes, so you can detect 3 or 4 errors without being able to fix them, and you can fix 1 or 2 errors.


$a^{2n}$ where $n\geq1$ is not Regular using Pumping Lemma

You can't prove that a language is regular by applying the pumping lemma.

Regular Languages are a subset of Languages that satisfy the pumping lemma. So you can only proof irregularity with the lemma. (By assuming that the language is regular and coming to a contradiction)

One way to show that a language is regular, is e.g. constructing a Regular Expression, NFA or DFA (all of these being equivalent).


Canonical reference on agent-based computing

If you want to approach this field from a computer science perspective then the standard reference I would recommend is:

Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

Currently, it seems like the focus of theoretical work in this field (and this is obviously biased by my own interests) is to consider environments where agents are limited in their interactions. If you just have agents meet randomly, then ABMs are usually overkill and things can be done analytically. However, if there is some interesting network structure (fixed or dynamic) to the interactions (as there often is in real life) then ABMs become an essential tool. A good book discussing some of these ideas from a CS perspective is:

David Easley and Jon Kleinberg [2010], "Networks, crowds, and markets: Reasoning about a highly connected world," Cambridge University press. (draft available online)

Questions of interest:

Simulation modeling of diseases

Sources for Algorithmic Evolutionary Game Theory


Disproving well-quasi-order by providing an infinite anti-chain

Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size.

It is perfectly fine to specify an infinite chain by giving an algorithm that enumerates its members, and even more complicated constructions are possible (e.g. the priority method). However, the end result of the construction should be a single infinite chain rather than a sequence of antichains of unbounded size.

I suggest taking a look at Higman's lemma.


Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

These are known as ranking and unranking functions.  You are right about the correspondence between recurrence relations for counting and unranking algorithms.


Searching for an algorithm with $\Theta(n2^n)$ time complexity

If you just want any algorithm with running time $\Theta(n 2^n)$ you can trivially compute $\ell = n 2^n$ from the input size $n$ and then have a loop of no-ops (or any constant number of "useless" elementary operations) iterate $\ell$ times.
If you are looking for a "reasonable" algorithm for a "well-known" problem with that time complexity, you can look for example at the brute-force solution for the subset-sum problem.
Given an input collection of $n$ non-negative integers $X=\{x_1, x_2, \dots, x_n\}$ and $T \in \mathbb{N}$ the problem asks to decide whether there exists a subset $S$ of $X$ for which $\sum_{x_i \in S} x_i = T$.
A trivial brute-force algorithm for this problem looks at $2^n$ possible binary vectors $v_1, v_2, \dots \in \{0,1\}^n$ of length $n$, where each vector $v_i$ represents a subset of $X$. For each $v_i$ we explicitly check, in $\Theta(n)$ time, whether $(x_1, \dots, x_n) \cdot v_i = T$.
After all vectors have been examined, return "yes" if one such vector was found and "no" otherwise.


Do data structures help to reduce complexity of operations, at the cost of something else?

To represent a collection of integers, you can use an array with one word of memory per element. For instance, say $A = [0,1,7,10]$. Alternatively, you could use an array $B$ to represent the same collection in the obvious way: $B = [1,1,0,0,0,0,0,1,0,0,1]$. Searching for element $x$ in $A$ takes $\Theta(n)$ time (or perhaps just logarithmic time if $A$ is indeed sorted), but you can do the same in $B$ in $O(1)$ time by just looking at $B[x]$, i.e. just indexing $B$ at position $x$. This is a tradeoff: by using more memory for $B$, you get faster lookups. Time-memory tradeoffs like this are often encountered.

Sometimes, one can show that to solve a problem, you must always no matter what spend some time, memory, or other resource to solve it. In such results, one must always specify the model of computation used. For instance, there is a well-known decision tree lower bound of $\Omega(n \log n)$ for sorting. So in this model, you absolutely can't beat this bound no matter what you do.


There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger values of $k$, Viterbi's algorithm would be too slow. The exact threshold depends on your hardware (its capabilities, and how much "space" is available to implement the algorithm), and on the required speed. Viterbi's algorithm is optimal, and so it should probably be preferred over other algorithms when the constraints allow using it.


Finding a hamiltonianISH path in a graph

This is the longest path problem.  It's NP-hard to find the longest path in a general graph.  You can try applying any standard algorithm for finding longest paths.  Search on this site for "longest path" and "Hamiltonian path" to find many references.  Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).


Prolog compilers already do this. Imagine if you had the program:
p(t1) :- body_1.
p(t2) :- body_2.
% ...
p(tn) :- body_n.

and you issued the query p(t).
There is a lot of literature on this topic, and I don't know if there is a recent review which covers it all. You could start with:
Colomb, J. Enhancing Unification in Prolog through Clause Indexing, J. Logic Programming, 1991:10:23-44.


Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

What I wanted to know is if there is a polytime algorithm (on the order of k) for determining this curve. If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?

Yes, this is possible. The equation for the curve will be nonlinear. (It is not possible to have a linear equation which describes the curve, because there exists sets of $k$ points (as long as $k \ge 4$) where no linear separator exists.)

Let the $k$ points in $n \ge 3$ dimensions be $\vec{x}_1, \vec{x}_2, \ldots, \vec{x}_k \in \mathbb{R}^n$.
For each point $\vec{x}_i$, suppose the set it is in is given by a label $\ell_i$, which is either $+1$ or $-1$. So the points are divided into those labeled $+1$ and those labeled $-1$.

Then we define the following function:
\begin{align*}
f: \mathbb{R}^n &\to \mathbb{R} \\
f(\vec{x}) &:= \sum_{i=1}^k \ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right),
\end{align*}
where $d_{min}$ is the minimum distance between a pair of points, over all pairs of $2$ out of the $k$ points. That is, we take the minimum over $\|\vec{x}_1 - \vec{x}_2\|$, $\|\vec{x}_1 - \vec{x}_3\|$, etc. I am using $\| \cdot \|$ to denote the norm, that is, the length of vectors in $\mathbb{R}^n$.

Now I claim that your desired curve is given by the set
$$
\big\{ x \;\mid\; f(\vec{x}) = 0 \big\}.
$$

To justify this, we should show that $f$ separates the points labeled $+1$ from those labeled $-1$. So we first calculate $f(\vec{x}_i)$. We get
\begin{align*}
f(\vec{x}_i) =
\underbrace{\ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right)}_{= \ell_i \cdot e^0 = \ell_i}
+
\underbrace{\sum_{j \ne i} \ell_j \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_j\| \right)}_{\text{small}}
\end{align*}
Now the first term is just $\ell_i$, which is $1$ or $-1$, and the second term is small enough that it doesn't change the sign. Specifically,
we can bound the second term (in absolute value) by
$$
(k-1) \exp \left( -\frac{\log k}{d_{min}} \cdot d_{min}\right)
= (k-1) \cdot \frac{1}{k} < 1.
$$

So $f$ is positive on points labeled $+1$ and negative on points labeled $-1$. Also, $f$ is continuous on the entire $\mathbb{R}^n$. So, the points $\vec{x}$ where $f(\vec{x}) = 0$ must be a separating boundary curve between the positively and the negatively labeled points. $\square$

Finally, some notes:

Definition of a curve: In the question, it is not defined what a curve is, here; I took it to be the zero set of a continuous function, but you might want something more specific. This curve is actually a $(k-1)$-dimensional surface, but it might not be smooth at the points $\vec{x}_i$. A modification could be made that would smooth out these points by replacing $\|\vec{x} - \vec{x}_i\|$ with $\|\vec{x} - \vec{x}_i\|^2$ and $d_{min}$ with $d_{min}^2$.
Polynomial time: Returning the function $f$ is polynomial time: the only hard part is to compute the quantity $d_{min}$, which requires computing the distance between every pair of points in the set. So this is $O(k^2)$ time. The rest is just $O(k)$ time. Note that this requires that we have a model of computation in mind where arithmetic can be done on real-number values (it won't be a traditional Turing machine).


sort array with some of the elements in a known range

Using radix sort, the second subarray can be sorted in $\Theta(log_{b}(n\sqrt n)(n + b)$ where $b$ is the base with which the numbers are represented. If $n$ is chosen  as the base, radix sort sort the array in $\Theta(log_{n}(n\sqrt n)(n + n)) = \Theta(\frac{3}{2}(n + n)) = \Theta(n)$. Now all 3 subarrays can be sorted in $\Theta(n)$ thus the array is sorted in $\Theta(n)$


Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$

$\newcommand{\co}{\mathsf{co}\text{-}}\co A=\left\{L\subseteq \Sigma^* \mid \overline{L}\in A\right\}$

Saying that the class $A\subseteq P\left(\Sigma^*\right)$ is closed under complement is equivalent to saying $A=\co A$ (verify).

Note that $\overline{A}$ is not the same as $\co A$, here we're simply taking all the languages outside of $A$, and we require nothing about the complement of these languages.

$\newcommand{\BPP}{\mathsf{BPP}}\BPP$ is closed under complement, since we can simply flip the answer (verify yourself that this works), so $\co \BPP=\BPP$.

$\overline{\BPP}$ however is a whole new story, and even contains all undecidable languages, since $\BPP\subseteq \mathsf{PSPACE}$.


More efficient algorithm for determining if one list is a sublist of another list

Let's start with the case when the lists are sorted. In that case, you can apply a simple modification of the basic merge algorithm on sorted lists: discard the elements instead of constructing a merged list, and only keep track of whether an element from list 1 was missing from list 2.

In the pseudo-code below, head(list) is the first element of list, and advance(list) means to discard the head of list. In other words, head(cons(h,t)) = h and advance(list) when list = cons(h,t) means list := t.

while list1 is not empty:
    if list2 is empty or head(list1) < head(list2):
        return false
    else if head(list1) = head(list2):
        let x = head(list1)
        while list1 is not empty and head(list1) == x: advance(list1)
        while list2 is not empty and head(list2) == x: advance(list2)
    else: (head(list1) > head(list2))
        advance(list2)
return true

Exercise: prove that this algorithm returns true when all the elements of list1 occur in list2 and false otherwise.

Let $n_1 = \mathrm{length}(\mathtt{list1})$, $n_2 = \mathrm{length}(\mathtt{list2})$ and $n = \max(n_1, n_2)$. The algorithm above removes at least one element of list2 at each iteration, and in the worst case it removes all the elements of both list. Therefore it executes at most $n_2$ iterations of the loop and performs at most $n_1 + n_2$ removals of the head of the list: its complexity is $O(n)$.

Now suppose that the lists are not sorted. An obvious solution is to sort them, then apply the known algorithm. Since sorting is $O(n \log n)$, this algorithm is $O(n \log n)$.

Exercise: make sure you understand why my statements about complexity are true.

Exercise (difficult!): can you do better than $O(n \log n)$ in the general case?


What happened if we implement quicksort without tail recursion?

You're correct that your version with a loop doesn't guarantee O(log n) additional memory. The problem is that you have recursively sorted the partition "on the left". You ignored:

  the partition with the fewest elements is (recursively) sorted first

This is essential. It ensures that each time you make a recursive call (and lay down a new stack frame, requiring constant additional memory), the sub-array that you are sorting is at most half the size of sub-array being sorted at the previous stack level. Therefore the maximum depth of the recursion is the base-2 log n, which gives the desired bound on memory use.

In your code you permit a worst case in which you recursively sort the larger partition, having size only one smaller than the previous at each step. Then indeed the recursion depth can be n.

The way to make the code entirely iterative, with no call-recursion at all, is (as always) to use a stack data structure instead of the call stack. So instead of recursively calling to sort the small partition, you push the large partition on to the stack (by which I mean, push a pair of integers describing its location in the array) and loop around to continue sorting the small partition. When the size of the piece you're working on hits 1 you pop the stack and loop around to continue sorting that.


How to choose a word to apply the Pumping Lemma?

You are on the right track. You just need to continue observing and trying. The trials and errors you have done might have been done by many experienced users more or less in different ways.

As you have found $w=c^n$ does not work. That word is too simple to be pumped outside of $A$, whether we will pump it down or pump it up.

Let us continue your preference/acumen to ignore the $a^n$ part. Let us choose word $b^mc^k$, where $m<k$. If we can pump substring of $b^m$ enough time, the number of $b$'s in $w$ will become larger than $k$ eventually. To ensure what will be pumped is a substring of $b^m$, we can let $m\ge p$, where $p$ is the pumping length.

So let us try $b^{p}c^{p+1}$. I will let you check that this word, if pumped up, will be no longer in $A$.

However, the number of $b$'s in $w\in A$ must be even. If $p$ is odd, $b^pc^{p+1}$ is not in $A$ in the first place. Well, in that case, we can choose $b^{p+1}c^{p+2}$.

In general, how to choose the right word so that it could pump down or up out of the language might feel like a bit of black magic without much pattern initially. However, there is actually not much  choices involved. You may learn from this answer and this answer.

Exercise. Prove the following language is not regular.
$B=\{a^nb^mc^k\mid n,m,k \in N \wedge n\operatorname{mod}2=1=m\operatorname{mod 2}\ \wedge m<k\}$


DFA containing substring to not containing substring by flipping acceptability of all states?

Shortly, yes. Formally, for every DFA $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, F\rangle$, define the DFA $\overline{\mathcal{A}} = \langle \Sigma, Q, q_0, \delta, F' \rangle$, where $F' = Q\setminus F$. That is, $\overline{\mathcal{A}}$ is obtained by flipping the acceptance of the states in $\mathcal{A}$. We calim the following.
Claim: $\overline{L(\mathcal{A})} = L\left(\overline{\mathcal{A}}\right)$.
Proof:  for every word $w\in \Sigma^*$, we have $$ w\in L(\mathcal{A}) \leftrightarrow\\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\mathcal{A}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|}\in F$}\leftrightarrow \\  \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin Q\setminus F$} \leftrightarrow \\ \text{the run $r_0, r_1, \ldots, r_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r_{|w|} \notin F'$} \leftrightarrow \\ w\notin L\left( \overline{\mathcal{A}}\right)$$
Crucial points in the construction that you should ponder about:

Both automata have the same structure, in particular, they have the same run over the same word $w$: can you tell where we relied on this fact?

The automaton $\mathcal{A}$ is deterministic (in particular, there is a single run of $\mathcal{A}$ on $w$ that determines whether $w$ is accepted or rejected): if $\mathcal{A}$ is nondeterministic, then the construction does not work. Indeed, on input word $w$, there could be two runs of $\mathcal{A}$ on $w$: $r$ which is accepting, and $p$ which is rejecting. After flipping the acceptance of states, we get that $r$ is rejecting and $p$ is accepting, and so $w$ is still accepted.


Maximum number of states in minimized DFA from NFA with $n$ states

The maximum number of states is $2^n$. Conversion from NFA to DFA is done by subset construction and the number of states of the resulting DFA is in the worst case $2^n$. Minimization of the resulting DFA in the worst case might not reduce the number of states.

An example of this is automaton that accepts strings over $\Sigma = \{0, 1\}$ which have $1$ as the $n$th symbol from the end. Of course, $n$ is a concrete number. A NFA has states $q_0...q_n$ and the following transition function:

$$(q_0, 0) \rightarrow \{q_0\} \;\;\;\; (q_0, 1) \rightarrow \{q_0, q_1 \}$$
$$(q_i, 0) \rightarrow \{q_{i+1}\} \;\;\;\; (q_i, 1) \rightarrow \{q_{i+1}\} \;\;\;  1 \leq i \leq n-1$$

Intuitively, the corresponding DFA needs to remember last $n$ symbols since it does not know has it seen the end, which means there are $2^{n}$ states. For more details, I suggest looking into this book. It has a more detailed proof and generally covers these topics in thorough.


What is the most used way to write for-loop as pseudocode?

Just use whatever is clearest in your particular situation. Pseudocode is not a formal language with formal syntax.

Note that for $e\in [1,8]$ do doesn't necessarily imply that the values $1$, $2$, ..., $8$ are assigned in any particular order.  Note that $\{x\in \mathbb{N}\mid 1\leq x\leq 8\}$ is somewhat redundant: an algorithm can't possibly loop over all the reals or rationals between $1$ and $8$, so the set can only really be a set of natural numbers. Finally, note that the association $\mathrm{e}=2.71828\ldots$ is very strong, so $e$ is often a poor choice of variable name.


How is the literal meaning of "rendezvous" related to its usage in distributed computing?

In this context, the rendezvous would mean "a bunch of threads meeting together" instead of people. Rendezvous is a method of synchronisation in which at least two threads "meet". In other words, each thread that reaches the rendezvous point waits until all other threads have reached the same point before proceeding.

In the context of Distributed Algorithms the Rendezvous Problem is the task of devising an algorithm that will ensure that at least two entities (e.g., mobile agents) starting from different positions will meet after a finite amount of time in a specific environment (e.g., in a graph).


What the difference between the Fourier Transform of an image and an image histogram?

This post is a copy from the top voted answer to the question What does the Fourier Transform mean in the context of images?
The answer is math.sx user due to dls.

In sound processing, the Fourier Transform has a physically intuitive meaning. A sound or function $f : [0,b] \rightarrow [-1,1]$ can be represented as a trigonometric series. And each term of the series corresponds to a frequency which you perceive. Many effects (like filtering, reverb, etc.) have an interpretation in the frequency domain which is useful for analysis. Unfortunately, the physical interpretation isn't as simple when we start talking about images. But on the analytic usefulness transfers over.

If we're talking about grey-scale, then an image is simply a function $f : [0,1]^2 \rightarrow [0,1]$. It takes a point in the square $[0,1]\times[0,1]$ and produces a value between 0 and 1, the intensity. The Fourier Transform just says we can represent this function in the frequency domain using a countable basis of trigonometric functions. Say you want to blur an image; this corresponds to a low-pass filter in the frequency domain. The following link shows many examples of Fourier transforms of images, gives an explanation of the physical interpretation (which I don't claim to understand entirely) and shows examples of basic image processing. This website shows more illustrative examples.

Another very important use of (variants of) the 2d-Fourier transform is image compression. The Wikipedia page for the JPEG codec lists the basis functions used to represent images.

Finally, note that if you're talking about an RGB image you can represent the image using the Fourier transform on each color component.


Premise: The figures depict functional dependencies, not relation schemas. It is improper to say that a functional dependency is or not in any normal form. So, I suppose that you are asking if the functional dependencies violate or not a normal form.
You say:

Suppose that a dependency  X -> A causes a violation of 3NF. There are two cases:
• X is a proper subset of some key K. Such a dependency is called a partial dependency.
• X is not a proper subset of any key. Such a dependency is called a transitive dependency, because it means we have a chain of dependencies  K->X-> A.

You have given one correct definition of 3NF a few lines above, and according to this definition the two cases are true only if A is not a prime attribute (that is, is not part of a key), otherwise the dependency does not violate the 3NF.
So the answer to the question which is title of your post: “Are all relational schemas with partial dependencies not in 3NF?” is NO.

Am I correct that "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are not 3NF, while "Figure 19.8 Case 2" is 3NF?

Yes, if you mean that in these cases the dependencies do not violate the 3NF.

Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure 19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"? Does that case exist?

Yes, both cases could exists: in general in a relation scheme there can be multiple candidate keys (and possibly with empty intersection).

Am I correct that
If that case can exist, it will be 3NF.
If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Since both cases can exists, the relevant dependencies do not violate the 3NF, while it is incorrect the assertion that “all relational schemas with partial dependencies are not in 3NF” (if a partial dependency determines a prime attribute, than it does not violate the 3NF).


Converting a context free grammar to a PDA -- is my solution correct?

Doesn't that language simply recognize any string in $\{0,1\}^*$ that has at least three $1$s in it?

If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it.

This is because I'm not on the mood to do a direct translation of that grammar, if that is what you really wanted to check :P


Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard?

This problem is NP-complete, by reduction from 1-in-3 positive 3SAT.

1-in-3 positive 3SAT is a variant of 3SAT, where we require that exactly each clause consists of 3 positive literals (no negation), and to satisfy the formula, exactly one literal in each clause must be true (no more, no less).  Thus, each 1-in-3 positive 3SAT instance is a formula

$$\varphi(x_1,\dots,x_n) = \bigwedge_i (x_{c_{i,1}} \sqcup x_{c_{i,2}} \sqcup x_{c_{i,3}}),$$

where $x \sqcup y \sqcup z$ is true iff exactly one of $x,y,z$ is true.

You can immediately convert this to an instance of your problem.  In particular, the $i$th clause corresponds to an equation

$$x_{c_{i,1}} + x_{c_{i,2}} + x_{c_{i,3}} = 1.$$

For instance, the clause $(x_3 \sqcup x_5 \sqcup x_6)$ corresponds to the equation $x_3 + x_5 + x_6 = 1$.
We get one equation per clause.  The equations are simultaneously satisfiable iff the formula $\varphi$ is satisfiable.  This completes the reduction.


Reduction of the diagonalization language to the universal language

If you look closely at the proof to show that $L_u$ is not recursive, the autor is using a reduction to $\overline{L_u}$ (which is not RE), not to $L_u$, and explain that a reduction to $L_u$ cannot work since $L_u$ is RE.


Shortest unambiguous representation of a graph over an alphabet

Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.

A representation for the graph will be said to be Unambiguous if the graph can be reconstructed from that representation.

Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \{0,1\}$. If we had an additional symbol $|$ in our alphabet, then we can easily encode the graph matrix as $0011|0011|0101|0000$.

But, as we dealing with only boolean symbols, we have to come up with some encoding that doesn't need the separator $|$. An easy way for doing this could be making each 5th bit special. If it is $0$ then it will mark a separator, else the next four bits are also encoding a single row of the matrix, and it won't mark a separator. If the encoding of row doesn't need additional four bits, then make the extra bits $0$. (You need few more such rules to make this encoding "unambiguous").

For example, your matrix can simply be encoded 0011 0 0011 0 0101 0 0000.

Of course, there are much better possible encodings which might utilize the presence of patterns in the matrix (like sparse matrix).

But, your question asks: Given a matrix representation of a graph, what is its shortest possible unambiguous representation over the boolean alphabet? Well, we can easily come up with a trivial encoding: the empty string $\epsilon$ represents the given graph and all other strings represent the graph as per the encoding described above.

So, the smallest unambiguous representation of the given graph matrix would be of length $0$.

This will also hold for any other alphabet.


EPI question on multiplying two integers

Judging from your comment, it looks like you might see what the issue with your explanation was, but it might be fruitful for someone to see this example worked out, so I'll post this anyway.

We can see that this works by stepping through the execution of this function. Let's use your examples of values for a and b:

a = 0b1110;
b = 0b0001;

We can now step through the function. Here are the initial variable assignments:

sum     = 0;
carryin = 0;
k       = 1;
temp_a  = a; // = 0b1110
temp_b  = b; // = 0b0001

We can now look at the first while loop iteration:

// (temp_a || temp_b) == (0b1110 || 0b0001), so we loop
ak = a & k; // = (0b1110 & 0b0001) = 0
bk = b & k; // = (0b0001 & 0b0001) = 1
carryout =  (ak & bk);      // =      (0 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (1 & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0 | (0 ^ 1 ^ 0)) = (0 | 1) = 1
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 1      << 1 = 0b10
temp_a >>= 1; // = 0b1110 >> 1 = 0b111
temp_b >>= 1; // = 0b0001 >> 1 = 0b000

Thus, after this loop, we have the following variable assignments:

sum     = 1;
carryin = 0;
k       = 0b10;
temp_a  = 0b111;
temp_b  = 0b000;

We then check the condition ((temp_a || temp_b) == (0b111 || 0b000)), and see that it is true, so we loop again:

ak = a & k; // = (0b1110 & 0b010) = 0b10
bk = b & k; // = (0b0001 & 0b010) = 0
carryout =  (ak & bk);      // =      (0b10 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b10 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0    & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (1 | (0b10 ^ 0 ^ 0)) = (1 | 0b10) = 0b11
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b10  << 1 = 0b100
temp_a >>= 1; // = 0b111 >> 1 = 0b11
temp_b >>= 1; // = 0b000 >> 1 = 0b00

Thus, after this loop, we have the following variable assignments:

sum     = 0b11;
carryin = 0;
k       = 0b100;
temp_a  = 0b11;
temp_b  = 0b00;

Checking our condition again, we loop again (there are two loops left, so I will just go ahead and put both of them):

ak = a & k; // = (0b1110 & 0b100) = 0b100
bk = b & k; // = (0b0001 & 0b100) = 0
carryout =  (ak & bk);      // =      (0b100 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b100 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0     & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b11 | (0b100 ^ 0 ^ 0))
                            //   = (0b11 | 0b100) = 0b111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b100 << 1 = 0b1000
temp_a >>= 1; // = 0b11  >> 1 = 0b1
temp_b >>= 1; // = 0b00  >> 1 = 0b0
// Variable assignments:
/* sum     = 0b111;
   carryin = 0;
   k       = 0b1000;
   temp_a  = 0b1;
   temp_b  = 0b0; */
// Loop again ((1 || 0) is true)
ak = a & k; // = (0b1110 & 0b1000) = 0b1000
bk = b & k; // = (0b0001 & 0b1000) = 0
carryout =  (ak & bk);      // =      (0b1000 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b1000 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0      & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b111 | (0b1000 ^ 0 ^ 0))
                            //   = (0b111 | 0b1000) = 0b1111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b1000 << 1 = 0b10000
temp_a >>= 1; // = 0b1    >> 1 = 0b0
temp_b >>= 1; // = 0b0    >> 1 = 0b0
// (temp_a || temp_b) == false, so we are done.
// Final variable assignments:
/* sum     = 0b1111;
   carryin = 0;
   k       = 0b10000;
   temp_a  = 0b0;
   temp_b  = 0b0;*/

Lastly, we calculate sum | carryin and return:

return sum | carryin; // = 0b1111 | 0 = 0b1111

This returns the result 0b1110 + 0b0001 = 0b1111, which we expect.


Let $L$ be a non-regular language over $\Sigma$, and let $w_1,w_2,\ldots$ be an enumeration of $\Sigma^*\setminus L$. Define $L_i = L \cup \{ w_j : j \geq i \}$. Each $L_i$ is non-regular (why?), $L_i \subset L_{i+1}$, and $\bigcup_i L_i = \Sigma^*$.


How to get to the efficient solution of a problem on buying with exchange policy

It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1).

First, we can verify by brute force that the number of additional chocolates we can get by returning wrappers repeatedly is indeed (choc-1)/(wrap-1).

Second, here is how we can understand or prove that formula.

Suppose we have wrap-1 wrappers. Imagine we can borrow one wrapper from a benefactor. Then we can return the wrap wrappers for a chocolate, the wrapper for which will be returned to the benefactor. So we do not owe the benefactor anything any more.

Looking back, we had wrap-1 wrappers initially while we had enjoyed one chocolate without wrapper in the end. So, every wrap-1 wrappers will bring one chocolate without wrapper, as long as we had no less than wrap wrappers. If we have choc wrappers, we will have choc/(wrap-1) wrapper-less chocolates. However, there is a catch. There is, in fact, no benefactor. So the number should be (choc-1)/(wrap-1) instead.

In a more friendly world where there are benefactors or a more admissible policy where wrap-1 wrappers can be exchanged for one wrapper-less chocolate, the number of additional wrapper-less chocolates will be choc/(wrap-1).


Let's remove the $L$ superscripts. The derivative with respect to $z_L$ is
$$
\frac{\partial a_j}{\partial z_j} =
\frac{e^{z_j} \sum_k e^{z_k} - e^{z_j} e^{z_j}}{\left(\sum_k e^{z_k}\right)^2} =
\frac{e^{z_j} \sum_{k \neq j} e^{z_k}}{\left(\sum_k e^{z_k}\right)^2} > 0.
$$


Radix sort splits data into own digits of given size, you may choose the base in which data would be treated. If you have 64bit integer you may choose size of radix to be any number, say 2 bits, 4bits, 21bits, 32bits etc., but since computer stores digits as binary numbers it makes more sense to stick with power of two.
Also, you would like to omit modulo operator and use bit masks for efficiency purposes, which is not possible for other numbers.

You haven't described your code, but if it assumes 10 as default base, it is perfectly good, your code is in hexadecimal representation, which gets stored as binary and then treated as decimal based number for sorting. This doesn't change your code, just language feature to provide numbers like that (you can input octal number using 0 in front, say 056, but it will not change running time, but changing radix will).


How can a computer deal with real numbers

Sage is an open source computer algebra system. Let's see if it can handle your basic example:

sage: sqrt(3) * (4/sqrt(3) - sqrt(3))
1

What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules.
Here is another example:

sage: 1 + exp(pi*i)
0

So sage can also handle complex numbers.
Computers never handle real numbers, since real numbers cannot be represented exactly on a computer. Instead, they either handle approximate representations of real numbers (usually floating point numbers but sometimes fixed point numbers), or they represent real numbers symbolically, as in the example above. Sage can convert between the two representations (in one direction!), and it can handle floating point numbers of arbitrary accuracy. For example,

sage: RealField(100)(pi^2/6 - sum(1/n^2 for n in range(1,10001)))
0.000099995000166666666333333336072

This computes $\pi^2/6 - \sum_{n=1}^{10^4} 1/n^2$ to 100 bits of accuracy (in the mantissa).
Another approach worth mentioning is interval arithmetic, which is a way of computing expressions with a guaranteed level of accuracy, using provable error brackets. Interval arithmetic is used in computational geometry, together with exact representation of rational numbers.
In theoretical computer science there are several other notions of real computation, but they are mostly of theoretical interest. See the answers to this question.


Can generalized Turing machines compute all reals?

Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine models fail to compute almost all real numbers.

In fact, the alphabet need not be fixed. It is enough that the alphabet is taken from some countable set of finite alphabets, for example $\{1,\ldots,n\}$ for every $n$.


Deriving the Sobel equations from derivatives

The Sobel operator is an approximation of the derivative in the X dimension followed by a simple smoothing operator in the Y dimension.  (Or derivative in the Y dimension and then smoothed in X).

Consider a one-dimensional signal $f(t)$.  The derivative of $f(t)$, $d f(t) / dt$ can be written as:

$$
\lim_{\Delta \rightarrow 0} \frac{f(t+\Delta) - f(t-\Delta)}{2\Delta}
$$

This is called the centered difference formula.

But with a discrete signal the smallest $\Delta$ you have at your disposal is the distance between samples, so you use that as an approximation of the limit.

We can see just how bad (or good) an approximation it is by looking at what it does to a complex exponential signal $e^{\omega i t}$.  The true derivative would give $\omega i e^{\omega i t}$.  The approximation gives
$$
\frac{e^{\omega i (t+1)} - e^{\omega i (t-1)}}{2} =
\frac{e^{\omega i}e^{\omega i t}-e^{-\omega i}e^{\omega i t}}{2} =
\frac{e^{\omega i} - e^{-\omega i}}{2}e^{\omega i t} =
i \sin(\omega)e^{\omega i t}
$$
so extremely accurate with low frequencies ($\omega$ near 0), but increasingly inaccurate as $\omega$ approaches the Nyquist frequency ($\omega \rightarrow \pi$).  This is about the best you are going to do with three samples.  It also has the advantage of over-attenuating the high frequency response rather than over-amplifying.

Now let's do some smoothing in the Y dimension.  We want something that only uses 3 points, and about the best you are going to get is $\frac{1}{4}f(t-\Delta) + \frac{1}{2}f(t) + \frac{1}{4}f(t+\Delta)$.  This filter has frequency response:
$$
\frac{1}{4}e^{\omega i (t - \Delta)} + \frac{1}{2}e^{\omega i t} + \frac{1}{4}e^{\omega i (t + \Delta)} =
\frac{1}{2}(1 + \frac{e^{-\omega i \Delta}+e^{\omega i \Delta}}{2})e^{\omega i t} =
\frac{1}{2}(1 + \cos \omega)e^{\omega i t}
$$
which smoothly transitions from passing low frequencies to completely attenuating high frequencies.

So convolve the derivative approximation in the X dimension with the smoother in the Y dimension and you get the kernel:
$$
\frac{1}{8}
\left[
\begin{array}{ccc}
1 & 0 & -1 \\
2 & 0 & -2 \\
1 & 0 & -1
\end{array}
\right].
$$


A bit late to the party, but the second approach can be useful to simplify the merkle-path. When hashing a pair, it's required to know if the leaf is on the left or right side of the pair. This can become quite complex, for example, when implementing multi-leaf inclusion proofs. By sorting the pairs before hashing, it doesn't matter which side the leaf actually has in the pair, as you're applying the same rule every time. Pretty neat solution in my opinion.


Why don't these 2 algorithms take the same time to detect duplicate lines in a file?

When you delete line j, each line which was after that line will be moved by one line upwards. That means, that your line i, which is below, also will be moved. So, since it was moved, it has changed it's number. And it means that you need to decrease i : i = i - 1.

As an example see this:

Given file:    Lines 2 and 3 are equal    Remove line 2:
1 00                                      1 00
2 01
3 10                                      2 10
4 01                                      3 01

And your second algorithm didn't see that their positions have changed. However, if it wouldn't be file, but an array/list/etc, you'd got an error.


Calculating all products of $n-1$ factors when given $n$ factors

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below.

Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$.
Output: $p_1, \cdots, p_n$, where $p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$, the product of all input elements except $e_j$.
Procedure:

Allocate array $p_1, p_2,\cdots, p_n$ of $n$ element in $E$.
Let $s=e_1$, $p_1=1$
For $i$ from 2 to $n-1$ inclusive, let $p_i = s$ and $s= se_i$.
Let $p_n=s.$

Now
$$
\begin{pmatrix}
p_1\\p_2\\ p_3\\p_4\\\cdots\\ p_{n-1}\\ p_n
\end{pmatrix}
\text{is}
\begin{pmatrix}
 1\\e_1\\e_1e_2\\ e_1e_2e_3\\\cdots\\ e_1e_2\cdots e_{n-2}\\e_1e_2\cdots e_{n-2}e_{n-1}
\end{pmatrix}
$$.
Let $b=e_n$.
For $i$ from $n-1$ to 2 inclusive downwards, let $p_i=p_ib$ and $b = e_ib$.
Let $p_1=b$.

The number of multiplications performed by the algorithm above is $3(n-2)$.

I believe that is the tight lower bound. However, I have not been successful proving it even though I have tried a few times. I am still trying from time to time.


How multiprocessing is done in Single Core Systems?

The operating system (or the thread scheduler) switches from one thread to another at more or less regular intervals, making it look as if these threads were running simultaneously.


Verify correctness of quantifier elimination, using SAT

Here are two techniques I've been able to identify:

Identify an explicit Skolem function. Suppose Priscilla can identify an explicit function $f$ such that

$$\forall x . P(x) \Leftrightarrow Q(x,f(x))$$

holds.  Then it follows that Priscilla's claim is correct.

This means that Priscilla can help us verify her claim by providing a function $f$ so that the above proposition holds.  We can confirm that the above proposition holds by testing the following formula for satisfiability:

$$\neg (P(x) \Leftrightarrow Q(x,f(x))).$$

If this formula is not satisfiable, then Priscilla's claim has been verified.

One caveat is that Priscilla needs to be able to identify a suitable function $f$.  A further caveat is that we need $f$ to be concretely representable in some concise form, say, as a polynomial-sized boolean circuit.  However, if those conditions are met, then this technique should work.
A hybrid argument.  Consider the special case of this problem, where we are quantifying over a one-bit variable (rather than a $n$-bit variable); it turns out the problem is easy to solve in this case.  This suggests that we try to chain that technique $n$ times, each time removing one more bit of $y$.  It turns out that this idea will sometimes work, but not always.

Let me explain how to verify Priscilla's claim in the case where $y=(y_1)$ is a one-bit variable.  Then $\exists y . Q(x,y)$ is equivalent to $Q(x,\text{False}) \lor Q(x,\text{True})$.  The latter formula is at most twice as large as $Q$, so still polynomial sized.  Now we can use our SAT solver to test whether $Q(x,\text{False}) \lor Q(x,\text{True})$ is equivalent to $P(x)$; the equivalence holds exactly if the following formula is not satisfiable:

$$\neg (P(x) \Leftrightarrow (Q(x,\text{False}) \lor Q(x,\text{True}))).$$

So, if we're quantifying over a single bit, this gives a way to verify that the quantifier elimination was done correctly.

To solve the original problem, apply this multiple times.  Priscilla's job will be to give us $n+1$ boolean predicates $R_0,R_1,R_2,\dots,R_n$ such that

$$R_i(x,(y_{i+1},\dots,y_n)) \equiv \exists y_1,y_2,\dots,y_i . Q(x,y).$$

Our task will be to verify whether all of these boolean predicates were correctly generated.  We can do this by testing whether $Q(x,y) \equiv R_0(x,y)$, $P(x) \equiv R_n(x)$,

$$R_{i+1}(x,(y_{i+2},\dots,y_n)) \equiv \exists y_{i+1} . R_i(x,(y_{i+1},\dots,y_n)) \qquad \text{for $i=1,2,\dots,n-1$}.$$

Notice that the latter is an instance of quantifier elimination with a single bit, so we've already described how to test it was done correctly using a SAT solver.  We can also test whether $Q \equiv R_0$ and $P \equiv R$ using a SAT solver straightforwardly.  So, we can check whether Priscilla generated $R_0,\dots,R_n$ correctly.  If she did, then we've verified that $P$ was generated suitably.

One caveat is that Priscilla needs to be able to generate the $R_i$'s.  A bigger caveat is that the size of all the $R_i$'s needs to be reasonable (say, polynomial-sized).  If Priscilla generates the $R_i$'s naively, their size might grow exponentially with $i$, which is no good.  So, Priscilla will need a way to simplify at each stage; there needs to exist some sequence of $R_0,\dots,R_n$ that are all polynomial-sized, and Priscilla needs to be able to find such a sequence.  That is by no means guaranteed.  That said, if Priscilla can do this, then this technique should work.

I'm not fully satisfied with these techniques -- they are incomplete heuristics, and they might fail on some/many problem instances -- so I would still be interested to see other ways of approaching this problem.


Regular expression at least 2 out of 3 consecutive characters should be 1

Assume that string $s$ is in $L$. We will look at the last two characters of the string:

00, impossible, because this string could not be in $L$.
01, next character must be 1, new last two characters is 11.
10, next character must be 1, new last two characters is 01.
11, next character may be 1 or 0, new last two characters is 10 or 11.

Note that no matter your current state, you will always pass through the 11 state within two steps. Assuming that $s$ ended with 11, we get the following loop:

(1|(011))*

This will be the middle section of any string in $L$. All we need to do now is handle possible prefixes, making sure not to allow any with size < 3:

(111|011|1011|11011)

And finally, possible suffixes (note the empty union to express that the suffix is optional):

(|0|01)

Now all that's left is to concatenate them:

(111|011|1011|11011)(1|(011))*(|0|01)


How to check if a language is not regular?

Yes your answer is correct.
Language L generates strings that begin with 2as followed by any number of bs then followed by any number of cs
Your regular expression represents L correctly
It is also worth reminding how the pumping lemma works , if a string in a language L cannot be pumped , then L is non-regular , however some languages can still fool the pumping lemma
Consider the language F = {a^i b^j c^k| i,j,k ≥ 0 and if i = 1 then j = k}. Which appears as a regular language in pumping lemma but is actually non-regular
This is why there are other methods to prove that a language is non-regular
For example to prove F is non-regular you should remember that regular languages are closed under complement (if F is regular then F' is regular too ) , then by the pumping lemma you can show that F' is non-regular and thus F is non-regular , sometimes closure under intersection is useful too
Finally you should try to get an intuition on the language , clearly L needs only finite memory to check the number of as , there can be any number of bs and cs and the FA does not need to remember the number of bs and cs , an intuition is a good first step .


Prove Recursive formula (Dynamic programming) N(C,i)

I figured it out.

Overlapping-subproblems:

$P_i == P_{i_1}$: If two beers has the same price it will give overlapping subproblems. The assignment thinks this is okay.
$P_i == P_{i-1}+P_{i-2}$: If a collection of beer has the same price as another collection of beers they will end up with the same parameter $C$. Because every left call doesn't change the value of $C$ it will give overlapping subproblems.

Proof of Correctness

I thought I had to prove the algorithm through induction with a mathematical equation. This wasn't the case. I had to prove that simple base-cases would give the correct value, and that the recursive calls would get closer to the 1st and 2nd statement and prove that the algorithm would eventually terminate.

Case 1: If $C = 0$, then $N(C,i)=1$
Case 2: If $i = 0$ and $C!=0$, then $N(C,i)=0$ (Had to edit my formula. The assignment specified that you had to use all your money)
and more...


Is this probability distribution data structure already discovered?

This is a straightforward use of augmented data structures.  I wouldn't expect it to be publishable on its own; it's more of an undergraduate exercise.  So, I would expect that it's probably been thought of many times before by many people independently, but not necessarily written down in any particular research paper.

The idea of storing in the node of a tree the number of leaves under it is a completely standard idea in augmented data structures.  So too is the idea of storing each node the sum of the values in the leaves under it.  If you read some algorithms and data structures textbooks that describe augmented data structures, I'm sure you'll find examples of both of those motifs.


Are there any NP complete problems in SUB EXP TIME?

The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known


Here is a possible DFA:

Basically, just send any invalid string like baac, caa*, etc. to a junk state.

As suggested by Yuval Filmus, you can minimize the number of states further by merging $s$ and $a$ :


You subsequently clarified that you are looking for a way to do multi-label classification in general, and the example in the question about wanting a cake was just an example.

OK, here is one standard way to do multi-label classification.  For each candidate label, you build a boolean classifier that outputs true or false: true means that the label applies, false means it doesn't.

In your example, you'd have three classifiers: a "cake classifier" that outputs true if the sentence should be labelled "wants-cake" and false otherwise; a "drink classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise; and a "solution classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise.  You now train each one separately.  Given a sentence, you run all three classifiers on it and use that to select which labels should or should not be associated to the sentence.  For instance, if the "cake classifier" outputs true, the "drink classifier outputs false, and the "solution classifier" outputs true, then you label the sentence as "wants-cake + wants-solution".

This allows you to use any boolean classifier as your underlying building block.  For instance, you can use SVMs, decision trees, random forests, and many other schemes.


The meaning of 'Pool' in Computer Science

A pool is basically some grouping.  It's kinda vague.
In that figure, the "data pool" is just some set of data while the "instruction pool" is just some set of instructions.  The figure means to show that a single instruction and multiple data go into the vector unit at a time, and then that single instruction is applied to each of the multiple data independently.

On the "pooling" design strategy
I clicked the link to "Pool (computer science)", Wikipedia.  That article's worded a bit confusingly because it's talking about a design strategy called "pooling" rather than discussing the term "pool" itself.
Pooling is when a resource is collected up into a pool for some reason.  Because it's such a vague term, it can apply in a lot of different situations, so it's hard to give a more specific description without overstating it.
But to give a common example, there's thread pooling in which a bunch of threads are kept alive-and-waiting to do jobs.  This pattern's often useful when you might have a bunch of little jobs that you want to run on different CPU cores.  Then, whenever you want to run a job, you pick an available thread from the thread pool and have it run the job.
In principle, you don't actually need a thread pool; you could instead create a new thread each time you want to run a new job.  The problem's that threads can be expensive to create and dismiss, so if you're running a bunch of little jobs, it's often highly inefficient to keep creating/releasing threads.
That said, "pooling" is unrelated to what the SIMD diagram was referring to as a "data pool" and "instruction pool".  In that diagram, they just meant that they had a bunch of things data and instructions to use on them, which they vaguely referred to as existing in pools.


Like other have pointed out, it seems you are confused by the difference between a minimum spanning tree, and a shortest path tree.

A minimum spanning tree, is a tree such that it spans all vertices, and the sum of all edges is as minimum as possible.

A shortest path tree, is a rooted tree such that the distance between the root, and any other vertex is as minimum as possible. (That doesn't necessary mean that the sum of its edges has to be minimum as possible).


Connection between max independent set and graph coloring

Let $n$ be the number of vertices of a graph $G$, $\chi(G)$ be its chromatic number, and $\alpha(G)$ be the size of its maximum independent set. Then
$$
\alpha(G) \chi(G) \geq n.
$$
The reason is that every color class in a legal coloring is an independent set.

The bound can be tight – simple examples are complete graphs ($\alpha(G) = 1$ and $\chi(G) = n$) and empty graphs ($\alpha(G) = n$ and $\chi(G) = 1$). More generally, if $G$ is a union of $m$ many $n/m$-cliques, then $\alpha(G) = m$ while $\chi(G) = n/m$; and if $G$ is a complete $m$-partite graph in which all parts have size $n/m$, then $\alpha(G) = n/m$ and $\chi(G) = m$.

The bound can also be far from tight. A simple example is the union of an independent set of size $n/2$ and a clique of size $n/2$: $\alpha(G) = n/2+1$ and $\chi(G) = n/2$.


Ways to implement a decision making process involving complex rules

It sounds to me like the techniques here are not a matter of science (e.g., clever algorithms) so much as engineering (e.g., program structuring).

The approach I would suggest is to have a list of validators.  Each validator is a function or object that, when passed a shopping cart, checks whether the cart satisfies a particular criterion.  You have one validator per criterion in your business rules.  Then, to check whether a shopping cart is valid, you can simply iterate over all the registered validator.

This lets you structure the program logic in a cleaner way.  Each criterion is separated out into its own function or subclass.  Thus, while you still might have hundreds of lines of code in general, this way there is some structure, and if you're lucky, most or all validators can be written in a fairly concise way, as each one deals with only a single concern/criterion.


How to define an automata for zig zag concatenation?

let $Q=Q_A\times Q_B\times \{1,2\}$ (1 means A, 2 means B)

also define $F=F_A\times F_B\times \{2\}$  (we end with B)

and $q_0=(q_A,q_B,1)$ (we start with A)

with the delta function: $\delta ((q_1,q_2, i),\sigma)=
      \begin{cases}
      (\delta(q_1,\sigma),q_2,2) &i=1 \\
      (q_1, \delta(q_2,\sigma),1) &i=2
   \end{cases}$

The idea is to encode both A and B together, with some "index" telling us if we need to check A or B


Difference between sequential and parallel divide and conquer

Just like you wrote, you can solve independent subproblems in parallel. Here are two examples:

In merge sort, you can sort the two halves of the input in parallel, and then merge them together sequentially.
In quicksort, you split the input into two halves sequentially, and can then sort both of them in parallel.

In the first case there is no divide step, and in the second case there is no conquer step. In other cases probably all three steps will be present.

Some divide-and-conquer approaches have a single subproblem. This is the case in binary search. Such algorithms do not benefit from parallelization.


How logic programming (especially ASP) is related to the reasoning in (first-order) logic?

Logic programming is proof search for some logic. Traditionally, this is the Horn clause fragment of first-order logic. Languages like lambdaProlog extend this to (intuitionistic) hereditary Harrop formulas. There are also languages like Lolli, LolliMon, and Olli that work in fragments of linear logic (ordered linear logic in the last case). The concepts here are the notion of uniform proofs, focused proofs, and polarization, which lead to the concept of an abstract logic programming language.

The other way of thinking about logic programming that is more common via the Datalog path is as finite model theory. The idea there is simple: just calculate what the model would be, i.e. literally the sets of tuples for each relation. For Datalog (with or without stratified negation), this is relatively simple; there is a single minimal model.

When non-stratified negation is allowed, the situation gets quite a bit more complex. There is no longer a unique minimal model. There are two ways of dealing with this situation. One is to move to 3-valued models and for things like $q\leftarrow\neg q$ we can assign the truth-value $U$ to $q$ representing an "undefined" third truth-value. This leads to well-founded semantics. Given this 3-valued model, we can create a set of 2-valued models by considering all ways of assigning $T$ or $F$ to the "undefined" tuples excluding models with unfounded propositions which gives stable model semantics. The recent paper Founded Semantics and Constraint Semantics of Logic Rules gives a nice way of generalizing, organizing, and understanding these various semantics and the details of what "unfounded" means. Answer set programming is often conceptualized as stable model semantics. The XSB implementation of tabled logic programming is capable of handling non-stratified negation and producing a well-founded semantics which can then be fed into an answer set programming system leading to a significant performance gain over directly applying answer set programming.

Returning to proof search, what's happening in answer set programming can be partially thought of with respect to disjunctive logic programming. Typical logic programming languages do not allow disjunction in the head. That is, you can't prove $p\lor q$ except by proving $p$ or $q$. The issue is clear. Given the (disjunctive) logic program $p\lor q.$, should $?{-}\,p$ succeed or not? More pointedly, what should be produced by $?{-}\,t(X)$ where $t(1)\leftarrow p\land\neg q. t(2)\leftarrow q\land\neg p.$ is appended to the earlier program? Finally, append $r\leftarrow t(1)\land t(2).$ and ask if $?{-}\,r$ holds. These examples illustrate that while we can find a model where $t(1)$ holds and a model where $t(2)$ holds, there's no model where both $t(1)$ and $t(2)$ hold. This can be related to the previous paragraph by noting the classical equivalence $p\lor q \equiv p \leftarrow \neg q$. In particular, the program $p\leftarrow\neg q. q\leftarrow\neg p.$ leads to both $p$ and $q$ being "undefined" in well-founded semantics and has two stable models, though this omits the model where both $p$ and $q$ hold. (One way to see why this happens is that there are implicitly completion rules that make the program look like $(p\leftrightarrow\neg q)\land(q\leftrightarrow\neg p)$.) In terms of proof search, there's simply no proof of $p$ from $p\lor q$. Via the soundness and completeness theorems of (classical) first-order logic, having a proof of some formula is equivalent to having it hold in all models. Answer set programming just enumerates the (stable) models. To see if answer set programming has proven something, you need to check to see if it's true in all the models the answer set program produces. Normal logic programming implicitly constructs a proof, so it can only talk about what holds in all models.

Finally, pure logic programming meaning logic programming omitting extra-logical features like cut (!), assert, retract, and others, is, as I said at the beginning, purely a matter of proof search. It does not "assert new facts and knowledge". It is the process of "discover[ing] consquences that are implicit in the initial premises". Most logic programming languages are restricted to a fragment of logic where this process is particularly amenable to computation. Indeed, they are often restricted to satisfy a much more stringent notion of "monotonicity" as is especially evident in Datalog. Datalog is usually implemented via forward chaining, which means starting from what is known and producing all immediate consequences. This is iterated until a fixed point is found. Monotonicity in this context means that once something is derived, you can never learn something later that will change your mind. Non-stratified uses of negation lead to non-monotonicity. For example, for the program $p\leftarrow\neg q. q\leftarrow\neg p.$, initially neither $p$ nor $q$ is true thus we may feel justified in deriving either or both of $p$ and $q$. If we pick both, then we scuttle our justification for picking either. Whichever we pick, we end up with a statement that isn't true in all models. Of course, in general there can be an arbitrary long chain of logic before we realize we're in this situation at which point we'll have already derived a bunch of things we should not have.


Average case algorithm analysis using Kolmogorov Incompressibility Method

The idea of the incompressibility method is that an incompressible input satisfies certain properties that can be helpful in the analysis. In your case, the complexity of the algorithm depends on how many characters appear in the string. When processing the $k$th character, the "running time" (or rather its proxy, the number of comparisons when checking the list) is $\approx \alpha_k/2$ comparisons on average, where $\alpha_k$ is the number of different characters that have been seen so far. In order to estimate $\alpha_k$, note that we can encode the first $k$ characters using roughly $8\alpha_k + k\log \alpha_k$ bits, and we deduce that $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Hence unless $k$ is very small, $\alpha_k$ has to be very close to $256$, and we can deduce that there are on average $128$ comparisons per character. We can use the inequality to determine how large $k$ needs to be, and also what happens when $k$ is small.

The reason we are trying to count the exact complexity in the case of your algorithm is that its worst-case and best-case running times are both $\Theta(n)$. We used incompressibility to estimate $\alpha_k$, which can also be estimated directly using probabilistic methods, but the incompressibility calculation is probably simpler. Still, incompressibility doesn't obviate the need to analyze the algorithm probabilistically – it just makes the analysis more tractable in some cases.


CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n

I'll suggest two methods, but since this is your exercise, you'll have to work out some of the details.  Important: study them both.

Method 1 (the dumb method)

We're going to use guess-and-check.  In other words, we're going to guess a solution to the recurrence $T$, and then we'll check whether our guess is correct.

How do we come up with a reasonable guess?  Well, we could try stuff blindly, but I have a better suggestion.  The reason this recurrence is difficult is because of the nasty $+2$ in $T(n/2+2)$.  So if that's inconvenient, let's throw it away: let's look at what happens with the related recurrence where that isn't present.  In other words, define a new recurrence $U(\cdot)$ by

$$U(n) = 4 U(n/2) + n.$$

Now use your methods to find a solution to $U(n)$ (e.g., recursion tree, etc.).  Finally, use that formulate for $U(n)$ and let's use that as our guess for $T(n)$: let's check whether it also provides an asympotically valid solution to $T(n)$.  If it is, ta-da, you are done!

I call this a "dumb" method because, while it might happen to work on this example, there's no guarantee it will work in every situation.  So that's why it is helpful to know a more powerful method:

Method 2 (transform of variables)

My suggestion is to first apply a change of variables to make that nasty $+2$ go away, then solve the transformed recurrence using standard methods you already know.

Here's an example.  Suppose we define a new recurrence for $S(n)$ by making the definition $S(n) = T(n+3)$.  (This corresponds to the change of variables $n \mapsto n+3$.)  Can you derive a recurrence relation for $S(n)$?  Sure, with some simple manipulation of the definitions of $S$ and $T$, you ought to be able to derive a recurrence of the form

$$S(n) = 4 S(\text{something}) + \text{stuff}.$$

In particular, I think you'll find that the $\text{something}$ has the form $n/2+\text{blah}$.  So, go do it.  Sit down with a pencil and work out the exact recurrence for $S(n)$ (fill in the $\text{something}$ and $\text{stuff}$ parts with their exact expressions).

Now if we were lucky, we'd get a recurrence of the form $S(n) = 4 S(n/2) + \text{stuff}$.  That'd be lucky, because then you could use your standard methods to solve that kind of recurrence (now that the nasty $+2$ is gone).  Unfortunately, when you work this out, you will discover that you were not lucky.  The nasty $+2$ got replaced by some other $+\text{blah}$, which is still nasty (since $\text{blah}\ne 0$).

But don't give up.  It turns out that $S(n)=T(n+3)$ was not lucky.  So try a different definition.  Try replacing the $3$ with some other number.  If you play around with it a bit, I think you will discover that there is another number you can use instead of $3$ that will be lucky: it'll make the recurrence look like

$$S(n) = 4S(n/2) + \text{stuff},$$

and that's a recurrence you should know how to solve (e.g., recursion trees nad such).  Once you find a solution for $S(n)$, you can plug back into the definition $S(n)=T(n+3)$ to get a solution for $T(n)$, and you're good.

This will work.  It takes a little more work, but it is more general, so it is worth knowing.  I suspect it is the method that your instructor wanted you to learn.


Passing a non-mutable argument by value or by reference?

Be careful. If I define (C type syntax for familiarity):

int var;

void f(const int x)
{
      ...
      var = ...;
      ...
      /* use */ ... x ...
      ...
}

Now go f(var). If pass by value, f uses the original value (at the call); with pass by reference, the value asigned in f. The language should specify which one. Only if the compiler can prove it makes no difference can it decide (and for that, it has to know all programs calling f, or forbid changing global variables).

I'd give one option, just for clarity of specification.


How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

The loop iterates $k$ times, where $k$ is minimal such that $\sum_{i=1}^k i>n$.  We know that $\sum_{i=1}^k i = \tfrac12k(k+1)$, so you just need to solve for $k$.


What algorithm can I use for a rule based system?

You don't need an algorithm.  Since you already have a set of rules, all you need to do is implement the rules.

The simplest implementation strategy is to simply re-evaluate all the rules each time something changes.  However, in some cases this might repeat work unnecessarily and there might be more efficient implement the rules.

For instance, if one of your rules is "IF the user has bought more than 1000 items today THEN sound an alarm", then re-evaluating this each time an item is bought might be unnecessarily inefficient.  A more efficient approach would be to keep a counter for each user that keeps track of how many items the user has bought today; each time an item is bought, increment the counter and sound an alarm if it is over 1000; and each midnight, reset all counters to zero.

So in some cases optimizations might be possible.  However, that is entirely depend on the specific of the rule, and there's not much we can say in general.  If you have a question about how to implement a specific rule efficiently, you can ask a new question specifically about that particular rule.


How come finding an $n/2$ size clique in a directed/ non directed graph is not in $\sf NL$?

(Turning my comments into an answer.)

You have to deterministically verify that the $\mathcal{O}(n)$ vertices on your witness tape form a clique.  Since you can only move to the right, you can only do linear amount of work for this set, however there are $\mathcal{O}(n^2)$ pairs of vertices in the clique, and you have to check every pair.  Hence you cannot check every pair and thus not verify if it is a clique or not.

Note that this is not a proof that $\mathbf{Clique}$ is not in $\mathsf{NL}$, only that this algorithm (or idea) doesn't work.


Maybe you're confusing two different problems.
The algorithm you are describing shows that the problem of testing whether a CFG generates some string from $1^∗$ is decidable (e.g., see here at page 21). Anyway, the problem of testing whether a CFG generates all the strings of the language $1^∗$ is truly decidable. Consider all production rules to be simple (I mean, no "$|$" on the right), and eliminate all productions including a teminal character different from 1 on the right. Now you have a CFG over a terminal alphabet of a single letter, and then it generates a regular language (see here). All that remains is to test if two regular languages are equal. Moreover, there are effective procedures to convert a CFG over a one letter (terminal) alphabet into a regular grammar (e.g., see here).

I was forgetting the last part of your question: the fact that it is undecidable whether $R\subseteq G$, where $R$ is a regular language, and $G$ is a CFG, does not implies that for some specific regular languages you can not decide the inclusion. For example, if $R$ is finite (possibly empty), then testing for $R\subseteq G$ is decidable (see the first link above).


Prove/Disprove: NP is closed under "mixed" complexity

The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows:

Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $x_1x_3 \ldots x_{n-1} \in S_1$ and $x_2x_4 \ldots x_n \in S_2$.

In terms of witnesses, a witness for $x \in S$ has the following form:

An even number $n$ and $n$ strings $x_1,\ldots,x_n$.
A witness $w_1$ for $S_1$.
A witness $w_2$ for $S_2$.

To verify this witness, we check:

$x = x_1 \ldots x_n$.
$w_1$ is a witness for $x_1 x_3 \ldots x_{n-1} \in S_1$.
$w_2$ is a witness for $x_2 x_4 \ldots x_n \in S_2$.


Why S=1, R=1 Is forbidden in RS-Flip Flop

This question has an accepted answer on another site.

Digest: If you had both inputs set to $1$, both outputs would be $0$ but they are supposed to be complementary.


Solve the worst case of this recurrence equation

For starters, let's rewrite the recurrence as
$$ T(n) \leq \max \sum_{i>0} T(a_i) + O(n\log n). $$
Suppose now that we could show that $T(m+1) - T(m)$ is increasing in $m$. In this case, it follows that we can assume that $a_2 = \cdots = a_k = 1$, and so
$$ T(n) \leq \max T(a_1) + O(n\log n). $$
The largest that $a_1$ can get is $n/2$ (well, $(n-1)/2$), and so
$$ T(n) \leq T(n/2) + O(n\log n). $$
Expanding this, we get $T(n) = O(n\log n)$.

Showing that $T(m+1) - T(m)$ (if this is indeed true) looks a bit messy, but potentially could be done in the spirit of the following lemma.

Lemma For all $a,b \geq 1$, we have $T(a+b) > T(a) + T(b)$.

Proof. Choose the $a_i,b_j$ for which
$$
\begin{align*}
T(a) &= \sum_{i=1}^k T(a_i) + a + \log k \sum_{i=1}^k a_i, \\
T(b) &= \sum_{j=1}^\ell T(b_j) + b + \log l \sum_{j=1}^\ell b_j.
\end{align*}
$$
Consider the sequence $c_0 = a_0+b_0$, $c_1,\ldots,c_t = a_1,\ldots,a_k,b_1,\ldots,b_\ell,1$, where $t = k+\ell+1$. This sequence sums to $a+b-1$ and satisfies $c_0 \geq c_r \geq 1$ for all $r > 0$, and so
$$
\begin{align*}
T(a+b) &\geq \sum_{i=1}^k T(a_i) + \sum_{j=1}^\ell T(b_j) + T(1) + a+b + \log(k+\ell+1) \left(\sum_{i=1}^k a_i + \sum_{j=1}^\ell b_j + 1\right) \\
&> T(a) + T(b).
\end{align*}
$$


Prove complement a^nb^nc^n is contextfree

You're overcomplicating. There is no need for the grammar to be deterministic, so it's OK for cases to overlap.

Say $\omega \in \overline{L_1}$. At least one of the following statements must be true:

$\omega = a^ib^j\nu \text{ where } i \ge 1, j\ge 0 \text{ and } i \ne j, \text{ and } \nu \text{ does not start with } b$
$\omega = a^ib^jc^k \text{ where } i, j, k \ge 1, \text{ and }j \ne k$(I don't require $i = j$, although if $i \ne j$ then the first condition also applies.)
$\omega \text{ does not start with } a$

These all have reasonably simple grammars.

Just in case it's not obvious, there are a few ways to do $a^jb^k | j\ne k$. One simple one:

$$\begin{align}
S &\to A \mid B \\
A &\to aC \mid aA \\
B &\to Cb \mid Bb \\
C &\to \epsilon \mid aCb
\end{align} $$

$C$ is a balanced sequence of $a$ and $b$, $A$ has more $a$s, $B$ has more $b$s, and $S$ has either more $a$s or more $b$s.


The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a family of circuits does, which is an infinite sequence $(C_n)_{n \in \mathbb{N}_0}$, $C_n$ being the circuit for inputs of length $n$.

Moreover, Boolean circuits in general are intrinsically non-uniform models of computation anyway since the input gates count as part of the circuit. If you insist on an arbitrary number of input gates, then you necessarily end up with a circuit of infinite size (which is a no-no). (In fact, this is why we use the notion of constructability to obtain uniform circuits; any sort of uniformity must be extrinsic to the circuit.)


DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring

The condition that all words have length $\geqslant 3$ makes the computation of the minimal DFA much more difficult. Thus let us first consider the language
$$
K = \{ u \in A^* \mid \text{every substring of length 3 of $u$ contains at least two $0$} \}
$$
where $A = \{0,1\}$. The forbidden patterns of the words of $K$ are $11$ and $101$, so that $K$ is the complement of the language $A^*(11 + 101)A^*$. But there is a nicer way to write $K$, using the comment of Luke Mathieson. Indeed, apart from the last two letters, every $1$ has to be followed by two $0$. This leads to the regular expression
$K = (0 + 100)^*(\varepsilon + 1 + 10)$. I let you compute the minimal DFA of $K$ which has only three states (plus a sink state if you want a complete DFA).

Now $L = A^3A^* \cap K$ and you can use standard algorithms to get its minimal DFA
(9 states, 10 if you count the sink state).


IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory

This blog post by Scott Aaronson gives a overview of why this simulation does not change anything about our understanding of quantum computers.

Maybe the best way to understand why is to understand what computer scientist are trying to prove at the moment: "quantum supremacy". The idea is to show that quantum computers can solve some problems much faster than classical computer (I insist on some because we know quantum computer only provide a speedup for some classes of problems but not all.) Now in theory we already have strong evidence that this the case because of Shor's algorithm:

a quantum computer can factor a $b$-bit integer in time roughly $O(b^3)$
the best known classical algorithm to factor $b$-bit integer runs in time $e^{kb}$ for some constant $k$
one can verify if a factorization is correct with a classical computer in time $O(b^3)$

From this one can derive a "practical proof" that quantum computers provide a speedup of classical computers as follows:

generate a random integer with $b=10000$ bits
run Shor's algorithm to factor it: this takes maybe a few seconds (or minutes)
verify answer with a classical computer: takes a few seconds (or minutes)
factorize the number with a classical computer: takes a millions of years or more

The important fact in this example is that the incredible difference between the quantum and classical computers: a few seconds vs a few million years.

There is one major problem though: to factor an integer that size with a quantum computer, we need to build a quantum computer with many thousands of qubits. At the moment, the largest quantum computer ever built does not even have a hundred. Thus we cannot run the above experience (yet).

This is where Scott Aaronson and the IBM experiment enters the picture. Instead of trying to factor numbers, we want to find another problem as above but where the quantum computer is much smaller so that we can actually build it. One such problem is quantum simulations:

simulating a quantum system with a quantum computer is very easy (polynomial time)
simulating a quantum system with a classical computer is very hard (exponential)

So we go ahead and redo our experiment:

pick a quantum system at random of size $b=100$ qubits
simulate it with a quantum computer: takes a few seconds/minutes
simulate it with a classical computer: takes a few million year

Since we can build a quantum computer of that size (~100 qubits), we are done right? Well no because how do we know the simulation with the quantum computer was correct? Sure it's fast, but maybe it's wrong! In this case we have not proven anything. You see with factorization, verifying the result is easy, but for simulation it is as hard as the simulation itself... This is the crucial issue.

In order to fix this, we want to find a value of $b$ such that the classical computer can still find the answer so that we can verify it but it has to be long enough to demonstrate that the gap between quantum and classical is huge. Researcher are trying to find this sweet spot, and think it is around $b=50$ where a supercomputer will take may a few months or year. The IBM paper shows that $50$ is too small. But remember that the simulation for $b=100$ is trillions of times harder than for $b=50$ (exponential), thus may the sweet spot is at $b=60$, but it is unlikely that we can ever reach $b=100$.

NOTES: I simplified most of the actual complexity bounds. I ignored the fact that quantum computations only give the correct answer with high probability, one may have to re-run the algorithm several times.


Is connecting islands with pontoons NP-complete?

After looking at the new diagrams, I see that you may need multiple pontoons to cross between islands. Given that, you could get very close to a solution of the Steiner Tree problem by turning the nodes into islands and creating a sufficiently diverse collection of pontoons with small arcs. Wikipedia says that there is in fact a PTAS for the Steiner tree problem, so I can't say immediately that this renders it NP-complete. However looking at the details of the Steiner tree might either get you a good approximate solution or show that the problem is NP-Complete.