Constrain certain variables in CNF to unique satisfying assignments

If you could add clauses to a CNF formula to cause it to be unsatisfiable iff certain sets of variables don't have non-unique assignments among the formula's satisfying assignments, you could use this same method to solve UNIQUE-SAT for any CNF formula.  Since UNIQUE-SAT is co-NP-complete, you'll have proven NP = co-NP.  So it is unlikely there is a solution to the problem that involves simply adding clauses.


Can someone provide a trivial example to the "reduction" procedure used to prove hardness?

First of all It may be a good idea to read about SAT and Clique problems. Quite a good point to start your research in NP problems. I'd suggest investigating SAT-3CNF, as it is a flagship example of an NP-Complete (both NP-Hard and in NP itself) problem.

Now, to show that an NP-Hard problem X can be reduced to Y would indeed prove that Y is NP-Hard too. To do that you need to provide a relation that maps X to Y (so for any example from X this function maps it to an example from Y.) What you basically want to show is that being able to solve Y efficiently, you'd be also able to solve X efficiently. Personally I believe you should start by reading about SAT-3CNF and Independent Set problems - there are some great examples explaining how they are equivalent, and the mapping is pretty intuitive. You may read about them, for example, here.

To answer your last question - I believe dealing with NP problems can be treated as non-trivial itself. Therefore I would recommend to spend just some time with them, get used to them and try to understand them, so that you are not just pointlessly trying to memorize problems and solutions.


If you don't constrain yourself to simple cycles, you can actually use the Bellman-Ford algorithm to find all the relevant vertices.

Start by running a DFS on the graph to find its strongly connected components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ iterations where $V_i$ is the vertices in $G_i$), add $V_i$ to your list of vertices that belong to a negative (not necessarily simple) cycle.

If one of the strongly connected components contain a negative cycle, then because $G_i$ is finite and so are the weights, you can loop through the negative cycle as much as you need, and then add go in a cycle through all the vertices in $G_i$. You only need to loop an amount that will guarantee a total negative cycle.

It is easy to show that there are no cycles between any $G_i,G_j$ and therefore there are no negative cycles other than inside the strongly connected components.

Since you run BF on each subgraph seperately, you keep the time complexity of BF which is $O(|V|\cdot|E|)$.


How is a program executed at the CPU level?

You can try taking a simple program and compiling it to native machine code.  (Java normally compiles to JVM code, but Andrew Tennenbaum has a book where he describes how to design a CPU that runs that natively, so it will do.)  On GCC, for example, you give the compiler the -S switch.

This will tell you that anything tricky, like I/O, is implemented by calling the operating system.  While you could download the source to the Linux kernel and do the same to it, what's going on under the hood is: everything is manipulating the state of the computer's memory, for example the list of running processes, or else talking to hardware by using special memory addresses that control it or using special CPU instructions like in and out on the x86.  Generally, though, only special programs called device drivers will talk to particular hardware, and the OS will send requests to use hardware to the right driver.

Specifically, if you print, "hello, world!" your compiler will turn that into a set of instructions that loads the string into a particular location (for example, loading the address of the string in memory to the %rdi register) and calling a library function with the call instruction.  This library function might find the length of the string with a loop, then call the system call write() to write that number of bytes from the string to file descriptor number 1, which is standard output.  At that point, the OS looks up what that process' file number 1 is and decide what writing to it means.  If writes to standard output get printed on your screen, there will be some process like copying the bytes to a buffer, which is then read by your terminal program, which tells the windowing system which letters to put where in what font.  The windowing system decides exactly what that should look like, and tells a device driver to put the pixels on the screen, which it does by changing video memory.


If A is mapping reducible to B and A is recognizable, then is B recognizable too?

Answer for Corrected Question

Short answer, no.

You can think of reductions as "making problems harder" (somewhat inline with using $\leq$ as the base symbol for reductions of).

In this case we only have two levels of "hardness", a problem/language is either recognizable ("easy") or unrecognizable ("hard") (but this obviously extends to other degrees of computability and complexity).

So if $A \leq B$, and $B$ is "easy", $A$ must be "easy" too (because it's "less than" $B$). Contrapositively, if $A \leq B$ and $A$ is "hard, then $B$ must also be "hard" (because it's "greater than" $A$).

Using this intuition, it may be a bit easier to see why the latter two are wrong:

If $A \leq B$ and $A$ is "easy", this doesn't tell us much about $B$ (it could be "easy" or "hard").
Similarly, if $B$ is "hard", it doesn't tell us much about $A$.

Note that as with the first pair, the second are really the same statement, just logically inverted.

Old Answer, Just Here for Posterity

I think you may have misread something. The second (provided) theorem is not correct, it should be if $A \leq_{m} B$ and $A$ is unrecognizable, then $B$ is unrecognizable.

This is just the contrapositive of the first statement.

Following from this, the final two are mistaken.


Showing that $n\log n - n$ is $\Omega(n)$

According to the definition of big Omega, in order to show that $n\log n - n = \Omega(n)$, we need to come up with $n_0$ and $c$ such that all $n \geq n_0$ satisfy $n\log n - n \ge cn$.

Let us assume that the logarithm is to base 2. When $n \geq 4$, we have $\log n \geq \log 4 = 2$, and so $n\log n - n \geq 2n - n = n$. Therefore we can take $n_0 = 4$ and $c = 1$ and satisfy the requirements for $n\log n - n = \Omega(n)$.

The choice of $4$ is arbitrary — any $n_0 > 2$ would work (for an appropriate value of $c$).


The first concept you mention is that of an algebraic data type (or ADT). These are (recursive) sum-of-product types, though in many languages the product types are not first-class in that you may not refer to them directly, but only as part of the sum.
The second concept is a true sum type. However, in both the examples mentioned, the sum type has a restriction that the summands must be unique, e.g. you cannot describe the type $A + A$, because summands are referenced nominally, rather than by their index.

Note that ADTs suffice to describe sum types (even with non-unique summands), by wrapping their summands in new constructors. However, they are more general, as they can describe fixed point types, like binary trees.


What's the difference between "polynomial time Turing-reducible" and "polynomial time many-to-one reducible"?

A polynomial-time many-one reduction is a polynomial Turing reduction that only calls the oracle once, and that returns the oracle's answer without any further computation.


Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?

In your suggestion you write the tapes next to one another. That has another disadvantage, if one of the tapes runs out of space one has to move the information to extend that space.

The solution is to write different tapes on "tracks", above each another, technically this is done by extending the alphabet to a cartesian product of alphabets. If the original tapes all have alphabet $\Sigma$ (for $i=1,\dots,k)$ and blank $B\in \Sigma$, the single tape simulator has alphabet $\Sigma^k\cup\{B\}$. Additionally one needs to mark the positions of the heads, leading to extra symbols on the tracks.

(edited to include answer to question in comment)


Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$?

It is known that some formulas require exponentially long Resolution proofs. Therefore Resolution cannot be used (directly) to prove that $\mathsf{NP}=\mathsf{coNP}$.

Note that the details of your procedure are completely irrelevant. The lower bounds show that whatever algorithm you use to create your Resolution refutations, there will be some formulas on which it will take exponential time, simply because every Resolution refutation of these formulas is exponentially long.


finding best n players in minimum number of comparisons

You can't.  There isn't enough information in a single elimination tournament to know who the $n$ best players are.  All you can infer is who the best player is.  You can't even tell who is second best; the second-best player could be any of the people who lost to the best player.

If you're not limited to a single-elimination tournament, I recommend you use a selection algorithm to find the top $n$ players, then use a sorting algorithm to rank-order those $n$ players.  Asymptotically, this needs only $O(N + n \log n)$ matches if you start out with $N$ players and want to rank-order the top $n$ of them.  If you only want to find the top $n$ players without rank-ordering them, a selection algorithm suffices, and then you'll only need $O(N)$ matches.  You can study the literature on selection algorithms and sorting algorithms to figure out how to reduce the constant factor hidden in the big-O notation.

In practice if you want to hold some matches simultaneously, you might want parallelizable selection algorithms and sorting algorithms.  Figuring out how to parallelize selection algorithms might be worth a question of its own.


How to prove that  $n(\log_3(n))^5 = O(n^{1.2})$?

Do what you did, but let $a = (3^{0.2})$... that should do it, right?

The reason that what you did didn't work is as follows. The big-oh bound is not tight; while the logarithm to the fifth is indeed big-oh of linear functions, it is also big oh of the fifth root function. You need this stronger result (which you can also get from the theorem) to do what you're doing.


Transitive closure of a directed graph (reachability) algorithm intuition/explanation

What the algorithm is doing is updating all $T[x][y]$.
Assume that $T$ is transitive and that a new edge $(u,v)$ is added. Which pairs $(x,y)$ would need updating? Well, those pairs for which adding $(u,v)$ creates a new path from $x$ to $y$.
Assume that we are in a case that doesn't enter the IF. If it is because $T[x][u]\neq 1$ then there was no path to go from $x$ to $u$. So adding $(u,v)$ will not help getting from $x$ to $y$.
If $T[x][u]=1$ and $T[x][v]=1$, then the new edge $(u,v)$ doesn't really change anything in terms of being able to get from $x$ to $y$.
So, the cases excluded by the IF are cases that don't need updating anyway.
Assume now that you are in a case that does enter the IF. So, $T[x][u]=1$ and $T[x][v]=0$.
If $T[x][y]=1$ we already were able to get from $x$ to $y$ before adding $(u,v)$. The maximum returns $1$. So, the value of $T[x][y]$ is not changed and still is $1$ after the loop exits.
Assume that $T[x][y]=0$. If we consider a $y$ such that $T[v][y]=1$, then that means that we can go from $x$ to $y$ by going from $x$ to $u$, from $u$ to $v$ using the newly added edge, and from $v$ to $y$. Precisely in this case the maximum will also result in $1$. To $T[x][y]$ gets updated to $1$.
Now, if the inned loop lands in a $y$ such that $T[x][y]=0$ and $T[v][y]=0$, that means that we originally were not able to get from $x$ to $y$ by paths not using the edge $(u,v)$. Any path that uses the newly added edge $(u,v)$ would have to go from $x$ to $u$, then $u$ to $v$ and finally some path from $v$ to $y$. This last part of the path can be assumed consisting entirely of edges different from $(u,v)$ by taking the portion starting from the last time that the supposed path leaves $v$. But the assumption $T[v][y]=0$ means that this path doesn't exist. So, there is no way to go from $x$ to $y$, and in fact the maximum in the code results in $0$ in this case.
So, that covers all the cases.


If $L$ were decidable, then you could make a decider for $A_{TM}=\{\langle M, w\rangle\mid M\text{ accepts }w\}$ by deciding $\langle M, M, w\rangle$. We know, however that that's impossible, since $A_{TM}$ is undecidable.


Selection algorithm variant for an array

Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be:
$$\frac{n(n-1)}{2} $$
For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.


what is the 'x :=' part mean in a hoare triple?

Short answer, it's an assignment, but it's not part of Hoare logic.

It means whatever it means in the programming language you're using.

A Hoare triple in general looks like $\{P\}\; C\; \{Q\}$ (stolen from the all-knowing wiki), where:

$P$ and $Q$ are assertions about the state of the system before and after $C$ is executed; and
$C$ is some piece of code.

So the meaning of $x :=$ depends entirely on the semantics of the code.

Assuming someone hasn't written this as a trick, $:=$ is usually used as an assignment operator (to avoid confusion with $=$ as equality), so in this case the line should be read as $x := x + 1$, i.e., the line of code is incrementing the variable $x$.

If the triple were written in a C-like language, you could write it as $\{x=2\}\; x=x+1;\; \{x=3\}$, or similarly in your favourite language.


augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?

By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the pointer.

An in-order traversal of BST outputs all values in order in linear time. So you can apply your linear-time algorithm similarly on BST, only the pointers advancing to the in-order next node.


Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF?

Well, that's not really what Herbrand's theorem says.  That's not a good way to think about Herbrand's theorem.  To understand the answer to your question, you first need to understand a little better what Herbrand's theorem does and doesn't imply.

I suspect I know what you are thinking.  You are thinking, given a statement $\varphi$ of first-order logic, you can find a disjunction $\psi_1 \lor \dots \lor \psi_k$ of quantifier-free formulas that is equivalent to $\varphi$.  However, that's not really what Herbrand's theorem says.  Herbrand's theorem doesn't necessarily give an effective or easy way to find the disjunction.  Herbrand's theorem says that if $\varphi$ is true, then there exists such a disjunction, but to actually find the disjunction, you have to know that $\varphi$ is true, and you have to know a proof that it is true (roughly speaking).

Let me give you an example and an analogy that may clear things up.  Here is D.W.'s theorem:

D.W.'s Theorem. Any formula of first-order logic can be expressed as either True or False.  In other words, for every sentence $\varphi$ of first-order logic, there is a formula $\psi \in \{\text{True}, \text{False}\}$ such that $\varphi$ is valid if and only if $\psi$ is valid.

D.W.'s theorem is trivially true; I can prove it in a single line.  Pretty cool, huh?

However, D.W.'s theorem is actually not very useful.  Given a formula $\varphi$ of first-order logic, D.W.'s theorem doesn't help you figure out whether $\varphi$ is valid or not.  Similarly, Herbrand's theorem doesn't really help you figure out whether $\varphi$ is valid or not.

Now, the formula $\text{True}$ is in Conjunctive Normal Form.  Also, the formula $\text{False}$ is in Conjunctive Normal Form.  Therefore, by D.W.'s theorem, every sentence $\varphi$ of first-order logic is equivalent to some quantifier-free formula $\psi$ in CNF form.  However, this probably not the kind of equivalence you were hoping for, because given $\varphi$, it's not necessarily easy to compute the $\psi$ that is equivalent to $\varphi$.


Here is the solution I found. I suppose here that the values entering the stack will be in $[\![0, n-1]\!]$. For that, I create an array $a$ of size $n$ that will implement a kind of doubly linked list: it is such that for $i \in [\![0, n-1]\!]$, $a[i] = (p_i, n_i)$ where:

if $i$ is not in the stack, $(p_i, n_i) = (-2, -2)$;
if $i$ is in the stack, $p_i$ (previous) is the value that is above $i$ in the stack ($-1$ if $i$ is the top of the stack) and $n_i$ (next) is the value that is below $i$ in the stack ($-1$ if $i$ is the bottom of the stack).

The stack is then a couple $(i_0, a)$, where $i_0$ is the top element of the stack ($-1$ if the stack is empty).
That way, the usual operations on stack can be done in $O(1)$ worst case:

testing emptyness: just check if $i_0 = 1$ or not;
pushing element $i$:

if $a[i] = (-2, -2)$, $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$
if $a[i] = (p_i, n_i)$ (duplicate case), then $a[p_i] \leftarrow (p_{p_i}, n_i)$, $a[n_i] \leftarrow (p_i, n_{n_i})$ (only if $p_i/n_i\neq -1$), $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$

popping element: $i\leftarrow i_0$, $i_0 \leftarrow n_{i_0}$ $a[i] \leftarrow (-2, -2)$, return $i$.

In the case of the DFS, one can also add the case $a[i] = (-3, -3)$ to differentiate vertices that already exited the stack from the $a[j] = (-2, -2)$, vertices that have not already entered the stack. The array a can then replace the boolean array usually used.


What is different between Set and Type in Coq?

Coq has 3 "big" types:

Prop is meant for propositions. It is impredicative, meaning that you can instantiate polymorphic functions with polymorphic types. It also has proof irrelevance, meaning that if $p_1, p_2 : P$ then $p_1 = p_2$. This allows terms that are only used for proof to be erased in any code generated by Coq.
Set is meant for computation. It's predicative, and doesn't have proof irrelevance, which lets you do nice things like not assuming $1 = 2$. The Set parts remain during code extraction.
Type is a supertype of both of these, allowing you to write code once that works with either

I'm pretty sure your error is because you're defining a Set whose parameters can be Type, which means they can be Prop, which isn't allowed. If you change to this:

Inductive prod (X Y: Set) : Set :=
| pair: X -> Y -> prod X Y.

your code should work.


Collection of real world non computable programming tasks

Are there some inputs that make my program crash?
Can this object be freed (from memory) or can it be needed later?
I'm building an editor and want to detect the programming language automatically. Given two languages described by CFGs, is there some input code for which I won't be able to guess the language (because it's valid in both languages)?
Do these two programs do the same thing?

Suppose that you have a property of programs so that:

It only depends on what the program does, not how it's written. So for example "It computes the factorial" or "It loops forever" work, but neither"It's written using a for loop" nor "It uses 5 variables" do.
There is some program that has the property
There is some program that doesn't have the property

Then Rice's theorem tells you that you can't have a (meta-)program that looks at source code and tells you if the program it describes has the property.

(My first and last examples are instances of that theorem)


The statement is obviously false: my computer can make sounds and it's hard to see that that as either storing or manipulating data.  I suggest you just ignore it and move on, since producing this kind of list does nothing to help your understanding of computers, programming or anything else.


Deteremine if Language is in $R$ or $RE$

The language is in RE: simply generate all inputs $x$  with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs in parallel. Whenever one simulation halts, accept.
The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem.
Indeed, to decide whether a Turing machine $T$ halts on empty input, we could create a new machine $M$ that simulates $T$ if $x=\varepsilon$ and does not halt otherwise. Then $M \in L$ if an only if $T(\varepsilon)$ halts.


Proof that locality is sufficient in showing two graphs are isomorphic

This method fails on regular graphs. For example, it fails on the following two graphs: the hexagon, and two disconnected triangles.

More generally, if you continue to explore neighbors' neighbors and so on, you get the 1-dimensional Weisfeiler–Lehman method. If you start with $k$-tuples of vertices, you get the $k$-dimensional Weisfeiler–Lehman method. Cai, Fürer and Immerman proved in An optimal lower bound on the number of variables for graph identification that there exist non-isomorphic graphs on $n$ vertices which fail to be distinguished by the $k$-dimensional Weisfeiler–Lehman method unless $k = \Omega(n)$. Since the running time of the method in the worst case is asymptotically $n^{k+1}$, this shows that the Weisfeiler–Lehman method doesn't yield a subexponential time algorithm for graph isomorphism.

For more on the Weisfeiler–Lehman method, check a paper of Douglas, or the recent work of Neuen and Schweitzer.


Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.

Why is dovetailing useful? Here is one example. Suppose that $L$ is recursively enumerable (there is a Turing machine enumerating all words in $L$) and also co-recursively enumerable (there is a Turing machine enumerating all words not in $L$). Then $L$ is recursive (there is a Turing machine that, given a word $x$, decides whether $x \in L$). For the proof, we simulate the first two machines in parallel, wait for $x$ to appear, and the answer accordingly.

How is dovetailing implemented? Typically, we alternately simulate one step of each machine.

In contrast to your operating system, in theoretical computer science we are sometimes interested in dovetailing infinitely many computations. This can be accomplished by running the first machine for one step, then the first two machines for one step, then the first three machines, and so on. Perhaps you will encounter examples illustrating why this is useful later in your academic life.


Min-hash are not just (standard) hash functions, but a family of functions $\cal H$, such that if you randomly pick one function $h\leftarrow \mathcal{H}$ out of the family, it will satisfy the requirement you have in your question.

Check
"Min-wise independent permutations"
by Broder, Charikar, Frieze and Mitzenmacher, 2000. They define this notion and analyze it in a very simple way to follow.

From a practical point of view, you usually have a bound on the size of the sets you use (say $2^{256}$, probably more than the number of atoms in the universe).
Then, a 256bits output is enough to have hash-functions that are permutations (and clearly, the set of all the permutations is a good family of min-hash functions..)
So the problem is not the output length, but how many functions are there in the min-hash family, so that if you pick one at random, you get the probability that any element is the minimum exactly $1/2^{256}$.

To overcome the huge set of hash-functions (there are $256! \gg 2^{256}$ permutations of 256 bits..),
they relax the requirements on the probability of the min-hash and get an approximated notion of $\epsilon$-min-hash, which guarantees that
$$\Pr_{h\leftarrow {\cal H}}[h(A)=h(B)] = \frac{|A\cap B|}{|A\cup B|}\pm \epsilon$$
which is more useful from efficiency perspective (the set $\mathcal{H}$ is smaller and easier to get).


Genetic Algorithms: Converge to best solution for one, few or many environments?

Unless you define "wide variety" very precisely and prove that your algorithm is able to abstract over all varieties in the way you want, then yes, you'll have to test it every time. I think for most interesting problems you won't be able to produce such a proof.

For a related entertaining read, check Neural Network Follies. The author describes a project where a neural network was trained to spot tanks in images. Instead the network learned how to tell whether it's sunny or not.


I agree with the commenters that your question is either ill-defined or nonsensical. It all hinges on what you mean by "tokens", and what it would mean to "not have tokens."

If you mean multi-character sequences that are "chunked" together into larger words, consider Brainfuck — or actually most esolangs, including my favorite, Befunge — where every "command" is a single character. However, on the other hand, many Brainfuck interpreters actually treat [-] as a single "chunk" meaning "set the current tape cell to zero", so in that sense maybe you'd call [-] a "token".

On the other hand, if you consider single characters to be "tokens", then maybe we need to go the other direction, and find programming languages in which everything kind of flows together without divisions. The first thing that pops to mind is Inform 7 (yes, that's Inform 7 source code!), where meaning is conveyed through English prose. Obviously Inform 7 has a parser that deals in words, but those words don't directly correspond to anything like LET in Basic; it's more complicated than that.

Or, consider Piet, an esolang in which programs are expressed as two-dimensional pixel paintings. Does a pixel count as a "token"? Does a rectangle of pixels count as a "token"?

In the same vein — of trying to break away from the strictures of linear words and into more free-flowing worlds — consider noit o' mnain worb, a nondeterministic cellular automaton. It uses ASCII characters to represent cells in the automaton; but do those characters each count as a "token", or are the relevant building blocks of worb programs more like "corridors" and "gates"?

For that matter, consider Wireworld, a better-known cellular automaton. Does Wireworld count as a "language"? and if so, does "it" "have" "tokens"?

For that matter, consider the "language" in which ENIAC was programmed. It certainly didn't have "tokens"! But if you were to write down the plugboard configuration for a given "program", I suppose that you'd pick some way of writing it down that involved ASCII and a grammar of tokens. I don't guess you'd communicate the plugboard configuration with a pen-and-ink drawing. (But maybe you would! Who knows!)

For that matter, what would you say about plain old x86 machine code? That's a "computer language" if ever there was one... but it doesn't have "tokens", does it? All it has is a stream of bytes, one after the other, which are chunked together to form instructions. Or does an instruction (such as B82A0000 or C3) count as a "token"? Does it matter if the same set of bytes (or some of them, at least) could be reinterpreted by another part of the program as a piece of data, a jump address, et cetera?

Basically, you need to define what you mean by "language" and "token"; and once you do that, I think you'll find that your question answers itself.


Avoiding "side effects" in recursive functions

If the helper function mutated the object c (which concat doesn't do in JS), then helper would have that side effect. But overall your intersection function wouldn't have any side effect that I can see, as the c array doesn't exist outside of it.

PS: concat returns a new array every time. The original c array is unchanged.


If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory?

The trick to making this work is "paging."  When bringing data from a hard disk into physical memory, you don't just bring a few bytes.  You bring an entire page.  4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper.  If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages).  That's much easier!  The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal.  In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.


Undergraduate Computer Science Textbooks

Since you like to work through books, meaning you will spend a lot of time with one book and dig into the details using the book, I would recommend that your next book be

Introduction to algorithms by Cormen

I don't have this book as it didn't exist when I went to school but learning algorithms and data structures is where you will start at the University level once you have one programming language learned.

This is the kind of book that once you put it on your bookshelf and you will keep grabbing again and again for the rest of your life if you continue to program.

I know you asked about math, but if you can do problem solving, and converting word problems to math, then learning the math you need for programming is not something to worry about. In math you take word problems and convert them into the language of math, with programming you take word problems and convert them into algorithms and data structures. The thinking is the basically the same, one produces an abstract result and the other a program that can be run on a computer.


Looking for a subjective ranking algorithm

Analytic hierarchy process (AHP) is a way to maximize or minimize or rank or prioritize things which are given in data formulated as qualitative comparisons, like a customer likes A more than B and so on. Given a set of customers and all their preferences, AHP can provide the max or a 'best' ranking or something like this.
See: https://en.wikipedia.org/wiki/Analytic_hierarchy_process


single tape NTM to single tape DTM equivalence

The claim is that for constant $b$, if $f = O(t(n) b^{t(n)})$ then $f = 2^{O(t(n))}$. Indeed, $xb^x \leq b(b+1)^x$, and so
$$
Ct(n) b^{t(n)} \leq Cb (1+b)^{t(n)} = 2^{\log_2(1+b) \cdot t(n) + \log_2 b + \log_2 C}.
$$
From here it's not hard to check that $f = O(t(n)b^{t(n)})$ implies $f = 2^{O(t(n))}$.


Things you are missing is

RAM performance: Intel CPUs has lower memory latency, and compilation speed significantly depends on memory latencies
Amount of cores/threads: each Ryzen core is slightly slower than Intel core, but it has 1.5x more cores, and each core can run 2 threads. This makes it 1.5x faster for ideal multi-threaded tasks (like benchmarks), but real programs may be not ideally scale from 4 to 12 threads
SSD speed, in particular 4K IOPS (i.e. speed of reading many small files)

F.e. first test on this page compares C++ compile times on various Intel/AMD CPUs:

8700K: Intel 6-core
7820X: Intel 8-core with slower memory controller
2700X: AMD 8-core
2600X: AMD 6-core

As you can see, Intel 6 cores outperformed AMD 8 cores and even Intel's own 8 cores coupled with slower memory controller.

And this page discusses a lot memory/cache latencies.


Turing machine - infinite tape in one or two directions

They are equivalent in computational power.  Anything computable by one of these two kinds of Turing machines, is computable by the other kind.  Let's look at how to simulate a Turing machine with a doubly infinite tape, on a Turing machine with a singly infinite tape.

The idea is to cut your doubly infinite tape in two, so that you have
two singly infinite tapes, a left one and a right one, which you will ultimately merge. You may mark
the ends with a tape location containing a special EOF symbol. You
also duplicate your finite control, so that you have two identical
finite state controls. You assume that you have a control passing
device (see below), so that, when the left machine tries to go beyond the right
end of its tape, it passes the control to the right machine, on its
leftmost tape position (just before the left end of the right
tape). And conversely, when attempting to pass the left end of the
right tape.

Now, in order to distinguish the left and the right machines, we
change the names of the states and the tape symbols, by indexing them
with $R$ and $L$ respectively for the left and the right machine. And
we change accordingly the transitions of the two machines so that they
work as before.

Now we are ready to merge the two half-tapes, for example by folding
the right one onto the left one. For that you flip over the right half
tape, and you are careful to modify accordingly the transitions,
exchanging right for left and left for right. Then you fuse the two
half tapes into a single tape containing pairs of symbols, a left one
and a right one, each component being possibly blank.

You modify again the transitions of both machines, so that the left
(resp. right) transitions use and modify only the left (resp. right)
parts of the pairs on the tape. Then you merge the control of the two machines by
simple set union respectively for states, and for transitions.

You add a set of transitions for each existing state, so that when the
tape symbol is EOF, it goes back to the previous tape location (the
first non-EOF location) and the state changes to its chiral
counterpart: if it is a left (resp. right) state, it changes to its
right (resp. left) counterpart.  That is the control passing device.

I may have forgotten a detail, but this is the general idea of the
construction. The proof is left as an execise.

Of course, the initial tape (input) must be modified accordingly.
But that can be made simple by placing the input (if finite) fully on
the left side (the one that is not flipped over) of the tape cut.

Then you put away the screw driver as it may be dangerous for the kids.

PS I only showed that the doubly infinite tape can be simulated with a singly infinite tape. The converse seems too obvious.


Complexity of an optimisation problem in 3D

Since TSP is NP-complete, most problems you'll encounter in practice can be.  (NP is a pretty general class.)  A classic paper of Karp gives a large number of other NP-complete problems that, by definition, can be reduced to TSP.


How to prove this language is context free?

I see that the language is equivalent to $L = \{aa^nbbb^mccccc^n\}$,

Indeed

  but I'm not sure if that helps at all.

Well, maybe not. How about if we write the equivalent language ever-so-slightly differently:

$$L = \{a^nabbb^mccccc^n\}$$

That's the same as

$$\begin{align}L &= \{a^nMc^n\}\\
M &= \{abbb^mcccc\}\\
\end{align}$$
And then
$$\begin{align}L &= \{a^nMc^n\}\\
M &= \{abbNcccc\}\\
N &= \{b^m\}\\
\end{align}$$
Which seems pretty straight-forward.

Or, to put it another way: Look for symmetries. Or try to create them.


Where should "imply" be placed in this formalisation?

Here is how to break your statement up:

If (any house is green) then (there exists a horse that is white).

An equivalent statement would be

If some house is green, then some horse is white.

The condition is "there exists a house which is green", and the consequence is "there exists a horse which is white".
If we wanted a different quantifier for the condition, we would change it to

If all houses are green, then some horse is white.

As you mention in the comments, this is more of a question in the semantics of the English language. This doesn't necessarily make it a bad question, since it highlights the need for a logical formalism which transcends such linguistic difficulties.
You can formalize the original statement as
$$
(\exists x \, \mathit{house}(x) \land \mathit{green}(x)) \to
(\exists y \, \mathit{horse}(y) \land \mathit{white}(y)).
$$
The prenex form is
$$
\forall x \exists y \, (\mathit{house}(x) \land \mathit{green}(x)) \to (\mathit{horse}(y) \land \mathit{white}(y)),
$$
or equivalently,
$$
\forall x \exists y \, \lnot \mathit{house}(x) \lor \lnot \mathit{green}(x) \lor (\mathit{horse}(y) \land \mathit{white}(y)).
$$


Acceptance problem for CFGs is not regular

Let's prove a more general result:

  Let $\phi\colon \{0,1\}^* \to 2^{\{0,1\}^*}$ be an arbitrary function mapping binary strings to languages over the binary alphabet. Suppose that the range of $\phi$ is infinite. Then the language $L_\phi = \{(x,y) : y \in \phi(x)\}$ is not regular.

(The language is over the alphabet consisting of $0,1$ as well as parentheses and comma.)

For the proof, we use Myhill—Nerode theory. Let $(x_n)_{n \in \mathbb{N}}$ be encodings of languages such that $\phi(x_i) \neq \phi(x_j)$ for $i \neq j$. Then the words $(x_i,$ and $(x_j,$ are inequivalent modulo $L_\phi$: taking any word $y \in \phi(x_i) \Delta \phi(x_j)$, the word $y)$ separates the words $(x_i,$ and $(x_j,$.

Interestingly, $L_\phi$ could be context-free. Let $\phi(0^n) = \{1^n\}$ and $\phi(w) = \emptyset$ if $w$ contains $1$. Then $L_\phi = \{(0^n,1^n) : n \in \mathbb{N}\}$, which is context-free.


Class of Algorithms where finding output of algorithm can be aided by output of same algorithm given a similar input

It can be algorithms which use initial guess, for example algorithms for finding roots and local minimums/maximum like Newton's method and gradient descend. Here g and x are functions, and g is close to x means that they have roots or local minimums/maximums in similar locations, so taking A(g) as initial guess, algorithm can converge faster to A(x).


Priority inversion in Hoare and Mesa monitors

Unless you are careful priority inversion is possible in either Hoare type or Mesa type monitors.  This is because monitors implement a form of mutual exclusion (only one process can be "in" the monitor at a time), and mutual exclusion and priorities don't mix well.  Boosting the priority of the thread in the monitor, mitigates (but does not completely solve) the problem.  Priority boosting is typically done either with a priority ceiling, or priority inheritance, or both.

Hoare type condition variables introduce an additional priority inversion problem, though.  In Hoare type condition variables a low-priority thread may WAIT on the condition variable (thus giving up the monitor lock), then a high-priority thread could run, make the condition true and SIGNAL the condition variable.  In a Hoare type condition variable, the high priority thread immediately loses the monitor lock and gives it to the lower-priority thread.

In a Mesa type condition variable this particular priority inversion won't happen.  The low-priority thread WAITs on the condition variable, giving up the monitor lock.  Then a high-priority thread runs, makes the condition true and NOTIFYs the condition variable.  The high-priority thread does not give up the monitor lock, and keeps running.


Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x_0$, the state after $t$ steps is $x_t \equiv x_0 x^t \pmod{c(x)}$. In particular, $x_t = x_0$ if $x_0 (x^t-1) \equiv 0 \pmod{c(x)}$.


Extracting Randomness from Mouse Acceleration

Start by reading How to extract randomness from a file?.

At a broad level, it seems like you understand pretty well the techniques.

To extract randomness in practice, I recommend you use a cryptographic hash, and use techniques from the cryptographic literature for cryptographic building pseudorandom generators.

You mention "extractors".  I know there's some cool theory surrounding them, but I don't recommend you use extractors.  They are beautiful but not practical.  Cryptographic hash functions are superior in practice.

You talked about estimating the amount of entropy in the data.  Unfortunately entropy estimation is an inexact science.  It's also easy to over-estimate the amount of entropy (e.g., if there are non-trivial correlations in the data that you didn't think to check for).  So, a typical procedure that cryptographers often use is to make some estimate of the entropy rate (typically through a priori calculations), then divide by a factor of 4 or so to provide a safety margin -- and gather random values from many sources, and feed them all into the pool.  The hope is that even if one source provides low-entropy data, or even if one of the entropy estimates is too optimistic, maybe some other source will have enough entropy in it to make up for the problem.

Overall, I recommend you spend some quality time in the cryptographic literature reading about the techniques that have been developed there.  Cryptographers have spent a lot of time worrying and thinking about this, because cryptography relies upon high-quality random numbers.  And, rather than re-inventing the wheel yourself, it's probably better to re-use some existing well-tested cryptographic method.

Here are a few pointers to get you started:

https://crypto.stackexchange.com/q/41967/351
https://crypto.stackexchange.com/q/27028/351
https://crypto.stackexchange.com/q/32984/351
https://crypto.stackexchange.com/q/10517/351
https://crypto.stackexchange.com/q/18355/351
https://crypto.stackexchange.com/q/39186/351

You can look around Crypto.SE and the resources mentioned there, and you'll probably be able to pick up a bunch about this topic.  Have fun!


Lower bound of complexity of simple problem

The informal argument is that you need at least $n$ steps to read all the input assuming you can only read at most one element of the input per "step". Of course, you might state that maybe there's an algorithm that doesn't need to read all the input. The argument against that is an adversarial argument which produces an input where such an algorithm will get the wrong answer.

Let $x$ be an input of length $n$ that doesn't contain $O$, and $A$ an algorithm that completes in less than $n$ steps correctly reporting that the input does not contain $O$. There is necessarily an element of the list that $A$ did not look at. Pick one and call that the $i$th element. Running $A$ on $x'$ which is identical to $x$ except that the $i$th element is $O$ then produces the incorrect result. Since $A$ is deterministic and all the inputs $A$ actually reads are the same, then $A$ must behave in the same manner and so it will incorrectly report that the list does not contain $O$.


Look at the binary representation of the sum. Each 1 in that representation represents a power of two that has to be included as a summand, either directly or indirectly.

If the number of 1s in that representation is greater than the number of summands, there is no solution, if it is equal, there is exactly one solution, and if it is smaller, things get interesting.

The basic property you'll want to exploit in the last case is that you can represent any power of two as once that power, or twice the next smaller power, or 4 times the one after that and so on.

I think this approach can lead to an efficient algorithm. (But I did not follow it through myself, so no guarantees.)


How is β-reduction a 2-morphism in Category theory?

Here is a new paper that covers a similar topic. The idea is that by doing algebra in enriched categories (2-categories are like categories enriched in categories), you can talk about more fine grained semantic structure on the algebra. (I haven't read through the whole paper myself, but I know enough to see some of the ideas behind it.)

The way it relates to your question is thus: ordinary categories are, "set enriched," meaning the homs are sets. When giving a categorical semantics of a type theory (say), the (open) terms are interpreted as arrows, the idea being that the domain of an arrow is the context, and the codomain is the type of the open term.

$$ Γ ⊢ e : T \ \ \ \ \ \Longleftrightarrow\ \ \ \ \  e \in Hom(Γ, T)$$

The important thing is that both the terms in the language and the semantics of those terms will form (enriched) categories, and the interpretation of those terms into the semantics will be functors that must preserve the structure of the hom collections. For sets, the structure is just equality of elements. So, equal terms must be assigned equal semantic values.

However, this means set enrichment isn't very good at letting us have structured semantic requirements. If we have β equivalent terms:

$$
(λ x → (x, x))\  e\\
(e,e)
$$

then with set enrichment, we have two choices:

They are not equal, so the semantic values assigned can be totally unrelated.
They are equal, so the semantic values must be the same.

However, option 2 basically means that our syntactic category has arrows that are β equivalence classes of terms (or whatever equivalence you wish to require of the semantics). We have pre-quotiented the syntax by all the reductions that hold.

Instead, think about poset enrichment (which is like a 2-category in which there is at most one 2-morphism between any two 1-morphisms). Now there is an additional partial order $\prec$ on elements of the sets, and the semantic assignment must respect that partial order. Now we have a third option, which is to say these two terms are not equal, but they are related:

$$(λ x → (x, x))\ e \prec (e, e)$$

And the semantics can no longer assign them completely unrelated values, they must assign them values that are 'connected' in the semantics.

With posets we are basically only able to represent whether or not a term is reducible to another. With enrichment in a category (like a 2-category), we are able (I think) to keep track of multiple potentially different ways in which reductions can occur, and how to compose them. Vertical composition is like:

$$ e_1 \rightsquigarrow e_2 ∧ e_2 \rightsquigarrow e_3 ⇒ e_1 \rightsquigarrow e_3$$

And horizontal composition is rather like:

$$f_1 \rightsquigarrow f_2 ∧ x_1 \rightsquigarrow x_2 ⇒ f_1 x_1 \rightsquigarrow f_2 x_2$$

Although you should take that with a grain of salt, because that gets into the part of the paper I haven't really read yet.

So, by using 2-categories or enriched categories, we can explicitly represent richer structure on our terms, and talk about semantics that preserves that structure.


I would treat each multiple choice answer as a "feature" of a given user. If we assume your 2500 multiple choice questions each had 4 possible answers, you would then have a sparse matrix that is 70,000x10,000. You could have a varying number of answers per question and still use this approach.

You could then cluster this via k-means or similar data clustering.

If you really want to do graph clustering, you could treat the sparse matrix as a bipartite graph, with 70,000+10,000 nodes, and edge exists where a user has given a certain answer. You could then apply graph clustering techniques like modularity maximization or graph partitioning.

Detecting these groups/clusters/communities falls under the category of unsupervised learning.


Given a set of string patterns, find which ones match a particular string

Rather than build 5 NFAs (one for each pattern), I suggest you build a single NFA or DFA that represents the parallel composition of all five patterns.  Then you can run the string through this automaton and check what state it ends at.  That state will tell you which of the 5 patterns it matches.

For best performance, build a NFA for each pattern, take the parallel composition using the product construction, and then convert to a DFA.  This should be quite fast.


I think it would be unusual to find an organisation advertising specifically for someone to design algorithms. Generally speaking a company will have a product or a number of products which go through an improvement and release cycle. Part of this will involve optimising algorithms/code. However to specialise so greatly I would have thought would mean such an employee would spend much of their time twiddling their thumbs! Any organisation nowadays generally wants someone to be multi-skilled (eg able to code as well)

Having said that, large organisations which engage in a lot of research (the likes of NASA, Google, Facebook, Bell Labs, Xerox of old) may have posts such as that. Bear in mind that those guys will be looking for real genius-level staff as well. (You may well be a genius.. :) )

I would try to broaden my horizons a little beyond just algos though, as after all, an algorithm is no good unless it can be implemented! And that will always bring its own set of challenges given available resources and the specific nature of the problem domain.

I know this isn't an "answer" just my thoughts. As a first port of call try typing "algorithm designer" into monster.com or similar job site! Good luck!


What is the SetHorspool string searching algorithm and how is it implemented?

Reading the source code we can see that it is an extension of Horspool to find a match from a set of needle strings $S$, rather than matching a single needle string.
How it works is by representing the set $S$ as a trie. This allows you to efficiently check character by character whether starting at position $i$ any of the strings on the trie can be found in the haystack. And like in Boyer–Moore–Horspool, if a position $i$ of the haystack fails to match any of the strings in $S$, instead of simply trying $i' = i+1$, a smarter skip lookup table is used: $i' = i + T[\text{haystack}[i + |\text{needle}| - 1]]$.
The second difference is how $T$ is computed. Normally the pseudocode is as follows (from the Wikipedia article):
function preprocess(pattern)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

But in SetHorspool, the minimum safe skip considering all patterns is computed instead:
function preprocess(S)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← min(length(pattern) : pattern ∈ S)
    for pattern in S
        for i from 0 to length(pattern) - 1 exclusive
            T[pattern[i]] ← min(T[pattern[i]], length(pattern) - 1 - i)
    return T


how to solve this lambda expression with free variable/s

The term $\lambda x . x y$ is in normal form. It does not reduce any further.

In general, to find out these things, you can just type them into a $\lambda$-calculus calculator. One is available in my PL zoo (hmm, it is momentarily under construction):

lambda @ programming languages zoo
Type Ctrl-D to exit or "#help;" for help.
# #constant y ;
y is a constant.
# ^ x . x y ;
    = λ x . x y

The language wants you to declare free variables as constants, which is why we first explain that y is a known constant.


Complexity of the language of all TMs $M$ such that $L(M)$ is decidable

This set is not r.e. nor co-r.e., in fact it's complete at the 3rd level of the arithmetic hierarchy ($\Sigma^0_3$-complete). This is shown in Soare's textbook.


There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.


Practical importance of interval / circular-arc graphs in resource allocation

Making Louis' comment into an answer:

Given a set of intervals (interval system) $\mathcal{I} = \{ [x_1, x_2] ,\dots, [x_{2n-1}, x_{2n}] \}$. Each of the $n$ intervals corresponds to the time period a certain job is being worked on. Now, we want to find all time periods in which the number of concurrently active jobs is maximal. These time periods happen to correspond to the maxcliques of maximal size of the intersection graph $G(\mathcal{I}) = (\mathcal{I} , E)$ with $E$ being defined as
$$ ([a,b] , [c,d]) \in E \iff [a,b] \cap [c,d] \neq \emptyset $$
The closed neighborhood of a vertice $v$ in a graph $G$ is defined as
$$ N[v] := \{ u \in V(G) : \{v,u\} \in E \} \cup \{v\}$$
It is known that for any interval graph every maxclique can be characterized as the intersection of two neighborhoods, i.e. for each maxclique $C$ of $G$ there exist some $u,v \in V(G)$ s.t. $C = N[u] \cap N[v]$.

With this we can easily devise an efficient algorithm to find the wanted time periods.

If you have any other answers along these lines I'd be happy to hear them.


Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

If you only wanted to parse regular expressions then you wouldn't have such problems (unless you were a really incompetent programmer, I guess). Caveats include the time needed to build an automaton; an asymptotically worse algorithm may outperform the automaton approach in many cases in practice.

The real issue is probably that they use library functions that deal with regexps which are way more powerful than plain regular expressions. Also, features like matching groups introduce further complexity.

In this case, trouble arose because these engines match substrings (with plain regular expressions, we typically only match whole inputs) and use backtracking; long partial matches that eventually mismatch cause long backtracks. In essence, this is the worst-case for naive, quadratic-time string matching.

Can this be improved? Maybe. Using the ideas from string matching automata we would backtrack not to the second symbol, but to the start of the longest suffix that matches a prefix of the pattern. But since the pattern is not fixed anymore, it's certainly not trivial to extend the ideas.


That list would be endless ... I will just try to provide a number of representative examples according to different criteria:

Best-first search (BFS): they are complete, i.e., they are guaranteed to find a solution provided that one exists and they are admissible, i.e., they are guaranteed to find the optimal solution provided, again, that one exists. However, they take memory exponentially in the depth of the search tree. Other than Greedy best-first search and A$^*$, pure heuristic search ($f(n)=h(n)$) is often quoted as another BFS algorithm

Depth-first search (DFS): they are not complete, and thus they are not admissible. However, running a sequence of depth-first searches with a threshold that increases monotonically is guaranteed both to be complete and admissible while it takes memory just linear in the depth of the search tree. The most prominent member in this class would be IDA$^*$. However, this is not the only way to guarantee both completeness and admissibility and Depth-First Bround-and-Bound (DFBnB) takes also memory which is linear in the depth of the search tree.

Bidirectional Search (BS): It has been observed that BS saves an exponential amount of time and memory in the case of blind (non-heuristic) search. Many efforts have been invested to reproduce the same result when using heuristic search but it is still an open question how to implement bidirectional search efficiently when using heuristics. James Kwa showed that BS* does not always expand less nodes than a single A$^*$ and Ariel Felner et al. have recently suggested Single-Frontier Bidirectional Search as a way to turn bidirectional search into a unidirectional search.

Perimeter Search (PS): while most people was considering that bidirectional search consists of two searches progressing simultaneously (either in front-to-front or front-to-end fashion), Giovanni Manzini and also Nelson and Dillemburg simultaneously and independently suggested to develop a perimeter around the target node $t$ and then to issue a unidirectional search from the start state $s$. The resulting algorithm is better known as Bidirectional Iterative-Deepening A* BIDA$^*$

Real-Time Search (RTS): in most cases the search is conducted off-line, i.e., the solution is seeked and as once it is found, it is executed. Korf (again) showed that this is not necessarily a limitation and was the first in introducing Real-Time Search for looking for the solution while the agent is moving. The same algorithm was improved and it is known as Learning Real-Time Search. This work started a branch of research which is continued even nowadays and you can find a myriad of algorithms to solve problems in Real-Time search. Very importantly also, this category of algorithms was devised taking minimax as a motif where decisions are taken without ever visiting a goal node. This is, these algorithms are also expected to solve problems which are unsolvable with the previous algorithms.

Moving-Target Search: somehow related to the previous case, but not exactly equal is the case of seeking a moving target while the agent is moving. Originally (as far as I know) Ishida and Korf (get in use to hear from Korf ;) ) suggested an algorithm called exactly like this Moving-Target Search. Ishida continued the work later and some work has been presented in recent years.

Sub-optimal search: most of the algorithms described above (all but RTS) are used to find optimal solutions. However, some algorithms are "extended" to find sub-optimal solutions with guarantees on the error margin. For example, Ira Pohl introduced weighted-A* WA$^*$ which is known to find solutions with a bounded error. There are also a lot of research in this category and one of my favourite algorithms  (among others) is $A_{\epsilon}$

But bear in mind that these are just only a number of prominent examles. The list of algorithms is huge and even the list of categories is quite large (though not impossible to get, of course).

Cheers,


Your image appears darker because standard RGB is used in transformation, with problem inherent to color - grayscale conversion as standard RGB transformation does not preserve luminance.

Simple modification is to switch RGB channels to color space using perceived luminance: $Y = 0.299*R + 0.587*G + 0.114*B$. That way, luminance and chrominance blurring will not result in darkening or artificial color bleeding.

Color spaces like Y'UV or RGB are non-linear, so make sure to use linear one, say sRGB or any perception-aware/ linear space.

If you can trade speed with accuracy, floating-point box filters are visually better. Given 5x5 blur is tempting, but does not approximate Gaussian Blur accurately enough.

Something is wrong with your code.
Images appears darker by bad color space, but not that much. I took python code found here as it is, and took your image, the result is darker in my opinion, but not visible to the point of shadow dark.

I haven't seen your picture while writing answer but, it seems to me that divisor used is bigger than the sum of cell values.


Prim's Algorithm - Building the Priority Queue

Assuming your PQ is backed by a heap (as you refer to it later). Since the only invariant in a heap is that the parent must be $<$ the children (heap property) you can see there can be no ordering between children of a single parent. A priority queue will always return you the minimal element regardless of order, just think about how $\min$ works: $\min\{1,2,3\}=\min\{2,3,1\}=\min\{3,2,1\}$.
Because a heap is represented in a continous array, you'll have $[b, c]$ after removing $a$ which means that $c$ will always be the left child. Look at the heap image on Wikipedia and notice it's leaning left.
Yes, that's the order they'll be in a usual heap, because all their weights are $\infty$. But any other structure (regardless of insertion order) would be acceptable as long as $a$ is the root, because it wouldn't hurt the heap property.

  parent-child relationships [in PQ's heap] do not correspond to the
  parent-child relationships in the original graph

That is absolutely correct. Just because your PQ is backed by a heap which encodes a tree you can't assume that the graph structure will have anything to do with the heap tree's structure. Just think about a non-tree graph with cycles and multiple edges between vertices: how would that be reflected in the heap's tree? There isn't even a correspondence with the partial MST.

Another argument: the whole structure correspondence breaks big time as soon as you modify just one key in the heap and sift it to it's place. For example:

     a(0)                            a(0)
   b(∞) c(∞)   --- d.key = 1 -->   d(1) c(∞)
 d(∞)                             b(∞)

even before modifying the key $d$ was the child of $b$ which wasn't true in the graph and is not even reachable. The same is true after modification for the reverse.

The best is to think of a PQ as:

interface PriorityQueue {
    add(node, cost)
    update(node, cost)
    (node, cost) popMin()
}

the fact that it's implemented as a heap shouldn't be of a concern, just assume that the PQ does add and update in $\mathcal{O}(n\log{n})$ and popMin in $\mathcal{O}(1)$ to get quasilinear runtime of Prim's algorithm. Even when you implement it you should separate the algorithm from the PQ implementation.


I believe that Håstad gave such an algorithm in 2000, see On bounded occurrence constraint satisfaction. His algorithm is stated for instances where each variable occurs at most $B$ times, and the advantage over 7/8 depends on $B$. The running time, however, seems not to depend on $B$.

In order to prove that P=NP, you need to find an algorithm which, given a satisfiable instance, satisfies at least $7/8+\epsilon$ clauses, for some constant $\epsilon>0$. This will enable you to distinguish between satisfiable instances and instances which are at most $7/8+\epsilon/2$ satisfiable, which is NP-hard as my answer to the question you mention shows.


The recurrence is supposed to express the worst-case runtime of binary search on an input of size $n$ (the letter $T$ might stand for time). The range you have to search search is halved in each step, so you get the $T(n/2)$ term on the right side.

Most of the time people only count the comparisons of the data, not the extra comparison for the loop condition, so it takes 1 comparison to halve the search space. For your analysis you might want to write a $+2$ instead of the $+1$, since you do count the loop condition.

As we want to express the worst case runtime, we assume that the element is not in the array, so the recursion terminates only when there is just one element left. This provides us with the base case of $T(1)=1$.


Knapsack with non-overlapping rectangles

This problem is known as maximum disjoint set.  In your case, assuming the rectangles are parallel to the axes, the problem is maximum disjoint set for axis-parallel rectangles.  The problem is indeed NP-hard, but Wikipedia has an approximation algorithm with an approximation ratio of $O(\log \log n)$ if all values $v_i$ are the same, or approximation ratio $O(\log n/\log \log n)$ for the general case where the values may differ for each rectangle.  You can check out the citations there to find an entry point to the research literature.

I have not been able to find any lower bounds on what approximation ratio is achievable, so as far as I can tell, it is an open problem whether you can achieve a constant-factor approximation ratio for this problem.

If you're willing to relax the running time requirement, there is a recent result achieving an approximation ratio $1+\epsilon$, at the cost that the running time becomes larger than polynomial, namely, $2^{\text{poly}(\log \log n/\epsilon)}$.  See arXiv:1307.1774 and arXiv:1608.0027.

In the case where none of the small rectangles are too small (i.e., each small rectangle has an edge whose length is at least a constant fraction of the length of corresponding edge of the large rectangle), this problem has a PTAS, i.e., $1+\epsilon$ approximation ratio is achievable.  See arXiv:1703.04758.


Algorithm to match numbers with minimum number of moves

The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).

This is the algorithm which solves the problem (originally written by dc2):

function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2


To add two $n$-bit numbers, you need a circuit of depth $\Omega(\lg n)$.  Depth $O(\lg n)$ is also achievable, so the lower bound is tight.

There are many examples of such circuits; for instance, a carry lookahead adder has depth $O(\lg n)$ (and size $O(n)$).  One can even achieve depth $\lg n + o(\lg n)$; for instance, a Krapchenko adder has depth $\lg n + O(\lg^{1/2} n)$ (and size $O(n)$).

This all assumes bounded fan-in gates, as usual.  If you allow AND and OR gates with arbitrary fan-in, then you can achieve constant depth (depth 3, I think).  See, e.g., https://en.wikipedia.org/wiki/AC0.


Reduction Vertex cover into Dominating Set

Remember that you also have to care for the reverse direction. In this case, you should see whether every dominating set is also a vertex cover (hint: no, but why?).


Exact meaning of $2^{\mathcal{O}(f(n))}$

The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c > 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$.

The class $2^{O(f(n))}$ is simply
$$
2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \},
$$
which is essentially what you wrote.

A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such that $\phi(n) \leq Cf(n)$ for all large enough $n$.

Given this point of view, $2^{O(f(n))}$ simply stands for some function of the form $2^{\phi(n)}$, where $\phi(n) = O(f(n))$.


To summarize the comments.

A. Sometimes $L^+$ is defined to be $L\circ L^*$, where '$\circ$' is the  concatenations operator.

B. Assume the following definitions,

  $L^* \equiv \{\varepsilon\} \cup L \cup L^2 \cup \cdots$

  $L^+\equiv L \cup L^2 \cup \cdots$

Then, by the properties of the concatenation operator, $L\circ L^i = L^{i+1}$. Explicitly for the case of $i=0$, it also holds that $L\circ\{\epsilon\} = L$.

Then,
$$\begin{align}
L\circ L^* &= L \circ \left(  \{\varepsilon\} \cup L \cup L^2 \cup \cdots \right )
\\ &= (L\circ \{\varepsilon\}) \cup (L\circ L) \cup (L \circ L^2) \cup \cdots \\ &= L \cup L^2 \cup \cdots \\ &\equiv L^+
\end{align}$$

The only missing part is to explain the second transition--The distributivity of the concatenation operator over unions.


Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}

First of all the answer you have provided is DPDA and not NPDA. "Z" denotes that your stack is empty, so you start by taking input i.e., "a" and keep storing them in your stack, as soon as "b" arrives you start removing one "a" for every "b" that arrives (b,a|Epsilon). Now their are two possibilities
(i) m>n :- if so number of "b" are less than "a", so after all the "b" are computed only "E" will be left in the string so we reach the final state i.e., (E,a|a)
(ii) n>m:- in this case all the "a"s will be removed so only "Z" will remain in the stack, so in this case this will be the final state i.e., (b,Z|Z)

Hope this will help.


Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM

Don't construct machines for $L(A)\cap L(B)$ and $L(A)\cup L(B)$. Use a variant of the product construction for those two automata to directly construct an automaton for symmetric difference. Because of the way the product construction works, you don't need to store much intermediate data at all: essentially the algorithm is just a couple of for loops and, with at most $n$ states to loop through, you only need $\log n$ bits to hold the value of the loop counter.


About the pseudo polynomial complexity of the KnapSack 0/1 problem

Whether $n$ is "included in the input" or not is irrelevant. No "tricks" are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list.
The input is at least $n$ bits long because it must include a list of all the values and weights of items. If we are not given the values and weights of the items as part of the input, then how are we supposed to solve the problem (if we do not know the weight/value of some items)?
Now, since we know that the input has length (in bits) at least $n$, any running time of the form $n, n^2, n^3,...$ is polynomial in the length of the input.
However, the length of a (reasonable representation of the input) is at most $O(n\log W)$ (assuming the values of the items are on the same order of magnitude as their weights). For every item we must give the weight and value, and this can be done with $\log W$ bits per item (by giving the binary representation of the weight/value).
As Yuval noted, $nW$ is not polynomial in $n\log W$.
It does not matter if we consider the input as the lists only or the lists "together with" $n$. If we also include $n$ explicitly, it just makes the input $\log n$ bits longer. But since the input is already at least $n$ bits long, having $\log n$ extra bits makes no difference.


Suppose that the root of the tree has subtrees $T_1,\ldots,T_m$, and that you found the optimal wake-up times $t_1,\ldots,t_m$ for each of the subtrees (that's the "dynamic programming" part, though I'd just call it recursion). In which order should you wake up the subtrees? If $t_i > t_j$, should you wake $T_i$ or $T_j$ first? Use this to come up with a recursive formula for the optimal wake-up time of the tree.


Suppose that you have an algorithm $f$ that decides $L=\{1^{BB(k)}\mid k \in \mathbb N\}\subseteq \{1^n\mid n\in \mathbb N\}$. Then you can build the following algorithm that computes $BB$:

// input k
n = 0
values_of_bb = []
while length(values_of_bb) < k
  if f(1^n) == 1
    values_of_bb.push(n)
    n = n + 1
return values_of_bb[k]

This will be true for all strictly increasing functions from $\mathbb N$ to $\mathbb N$: if the image is decidable, then the function is computable. You just have to enumerate potential values in increasing order and put them in a list (still in increasing order), and then the $k^\text{th}$ value is simply the $k^\text{th}$ element of this list.


runtime to a BFS flood-fill with multiple centres?

Suppose there are n pixels on the screen.

We add the neighbours onto the queue only if they haven't yet been processed.

This way a pixel is added onto the colouring queue only if it hasn't been coloured yet.

Thus a pixel can be added onto the queue for a maximum of 1 time.

So if there are n pixels, then at most n additions would be done to the queue and thus n operations would be needed to colour the entire display.

It doesn't matter if number of centres are increased or decreased since each pixel would need to be added onto the queue at most once.

Thus the complexity would remain O(n) in both the cases.

Sources that claim the complexity to be O(4^n) are considering a brute force approach where we don't remember the pixels we have already coloured and end up colouring it over and over again.


strange choice of constant when showing $an + b = O(n^2)$ ("Introduction to Algorithms" book)

Because of the requirement $an+b>0$. The definition requires $0 \leq f(n)$.


The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter.

While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is to the right of the circle.

If the splitting plane is to the left of your circle you must continue searching in the right child, and vice versa. However when the splitting plane intersects your circle you must search both children.


Is there a way to hash a turing machine?

Sure.  Any Turing machine can be represented as a bit string (print out the description of the Turing machine).  Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).


If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is  hanoi(n, 'A', 'B', 'C') :

hanoi(n, 'A', 'B', 'C')
hanoi(n-1, 'A', 'C', 'B')
hanoi(n-2, 'A', 'B', 'C')
...
hanoi(1, 'A', $ , €)
Moving disc from A to $

To see if $ is equal to B or C, you just have to remark that the value of to_peg and spare_peg alternate each time so the disk to move only depends on the parity of n. In our example :

If n is odd then \$ = B and otherwise, \$ = C


Does DFS have better constants/complexity than Backtracking on a Graph?

When you explore a graph of $N$ vertices and $E$ edges, you basically need to store the visited vertices in a $N$ boolean array. But eventually (when you are interested in retrieving path and not only connection), you will use instead a $N$ bactrack array, containing for each vertex, the one that let you reach it (the parent vertex in the exploration tree).
Exploration methods BFS and DFS needs an extra storage for a queue of vertices to visit which size is $O(N)$. One can consider that the difference between BFS and DFS is just that they respectively use a FIFO and LIFO queue. Note that DFS algorithms often use a recursion hiding the additional storage.
Now, what you call "backtrack" is just a simpler way to do the DFS as you don't have a "todo" queue. When a vertex is fully explore, you just go back in the exploration tree. Of course, it is less efficient than DFS as you will run the exploration loop several times on some vertex. One can argue that it is slightly more efficient in space as you save the queue storage, but practically, this is negligible.


Hardness of a problem which is the sum of two NP-Hard problems

Nothing.
Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be easy to compute.
Upper bound: Suppose $h(x) = f(x)$. Then $\sum_x g(x) = 2 \sum_x f(x)$, which is as hard as computing $\sum_x f(x)$, which is assumed to be NP-hard. Since NP-hard means (roughly speaking) NP-complete or harder, there is no upper bound on the complexity; it could be arbitrarily hard to compute $\sum_x g(x)$.


Why strokes are treated differently than fills in modern graphics pipelines

Modern graphics hardware draws triangles. 99% of the hardware is dedicated to drawing triangles. One percent is support for line drawing, and it's mostly for historical reasons. If at all possible, line drawing will be done using the triangle drawing hardware.


Can Stoer-Wagner find min s-t cut for given s and t?

Finding a minimum s-t cut is easier than finding a minimum cut, so there is no reason to use or adapt Stoer-Wagner; instead, using a standard algorithm for finding a minimum s-t cut, such as using a network flow algorithm.


Calculating the Time complexity using Radix sort

You are correct.  We have $(n/\log n)^{20} \le n^{10}$ for all $n\ge 1$, so each number can be expressed using at most $d=20$ "digits".  The running time of radix sort is $O(dn)$, and $O(20n)$ is $O(n)$, so the running time is linear in $n$.


Hausdorff distance between two binary images according to distance maps

So I finally managed to do it, here's the answer for future reference.

The idea is not to compute the distance map of the image, but of its complement.

Here's a example to better understand :

You have these binary images, where our objects are in black :

Object $X$

Object $Y$

To compute $h(Y, X)$, you need to compute the distance map $dX$ of the complement of $X$ (here using 4-adjacency, but work the same with any distance):

The distance is 0 on the object.

You now only need to find the $max(dX[i,j])$ such as $Y[i, j]$ is in the object.

Here's our example with $Y[i, j]$ in the object in orange, and the $max(dX[i,j])$ in red :

So $h(Y, X) = 3$.

$h(X, Y)$ is computed in a similar fashion, using $dY$ and $X$.

Now that you have $h(X,Y)$ and $h(Y,X)$, you can easily compute the Hausdorff distance $H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$.

If you already have your distance map, the complexity of the Hausdorf distance is obviously $O(X + Y)$ with this algorithm since you only need to iterate one time over each image.

Note that computing the distance matrix is also done in linear time, so its always better to go with this method instead of the naive one.

Here some sources:

A Linear Time Algorithm of Computing Hausdorff Distance for Content-based Image Analysis (M. Julius Hossain, M. Ali Akber Dewan, Kiok Ahn and Oksam Chae)
An image algorithm for computing the Hausdorff distance efficiently in linear time (R. Shonkwiler)


The three cases correspond exactly to the three cases in the statement of the theorem. Let's consider them one by one. Suppose for simplicity that $T(1) = 1$.

Case 1. Suppose that $f(n) = n^\delta$, where $\delta < \log_b a$. Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta.
$$
Since $\delta < \log_b a$, we have $b^\delta < a$ and so $a/b^\delta > 1$. Therefore
$$
\sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i =
\left(\frac{a}{b^\delta}\right)^{\log_b n} \sum_{j=1}^{\log_b n} \left(\frac{b^\delta}{a}\right)^j = \Theta(n^{\log_b a - \delta}),
$$
since the geometric series $\sum_j (b^\delta/a)^j$ converges, and $\log_b (a/b^\delta) = \log_b a - \delta$. We conclude that
$$
T(n) = n^{\log_b a} + \Theta(n^{\log_b a - \delta} n^\delta) = \Theta(n^{\log_b a}).
$$
(So it is not quite true that the first term is dominant.)

Case 2. Suppose that $f(n) = n^{\log_b a}$ (this is the case $k = 0$; the case $k > 0$ is similar though slightly more complicated). Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^{\log_b a}.
$$
This time $a = b^\delta$, and so each summand is equally dominant, leading to
$$
T(n) = n^{\log_b a} + (\log_b n) n^{\log_b a} = \Theta(n^{\log_b a} \log n).
$$

Case 3. Suppose that $f(n) = n^\delta$, where $\delta > \log_b a$. Then
$$
T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta.
$$
Since $\delta > \log_b a$, we have $b^\delta > a$, and so $a/b^\delta < 1$. Therefore the geometric series $\sum_i (a/b^\delta)^i$ converges, implying that
$$
T(n) = n^{\log_b a} + \Theta(n^\delta) = \Theta(n^\delta).
$$

These proof sketches serve to explain that proof hints. However, they're not a complete proof, for two reasons. First, I assumed that $f$ has a specified form rather than a specified order of magnitude. Second, there is a tacit assumption that $n$ is a power of $b$. With more work we can take these points into account and prove the complete theorem. (A third and more minor point is the base case – you have assumed a base case of $1$, whereas the theorem calls for an arbitrary base case.)


Number of different binary search trees storing n distinct keys?

The solution to your recurrence is
$$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$
also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.


simon funk is the apparent inventor of a simple & ingenious SVD (singular value decomposition) algorithm during the netflix contest although the algorithm may have predated his discovery (would like to know a ref if anyone knows). SGD = stochastic gradient descent (?) which can be applied to all kinds of optimization problems, incl SVD.

so it depends on your recommender system framework and if its trying to use SVD for recommendations, which is common, but not universal. if it is using SGD to compute the SVD, then that is very similar to the Funk algorithm except the Funk algorithm is probably more prone to get stuck in local minima.

in other words the SGD may find a superior solution but it may take longer. so basically both SGD/Funk are two approaches to computing the U,V matrices & you can do experimental testing to see which gives you the best results or desirable performance.

Funks algorithm is basically just straight gradient descent and SGD is stochastic gradient descent that adds a simulated annealing-like approach to the optimization where earlier in the convergence/search, weights are randomly perturbed to avoid local minima, and then as the search progresses & hopefully converges, the perturbation factor decreases.

fyi for SVD it can be possible to find the optimal solution using matrix based methods even for large matrices (esp if large distributed resources are available) and one could possibly compare either the Funk algorithm or SGD to the actual global optimum.


What is the time complexity of generating n-th prime number?

What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition).

It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is simple to formalize the concept that algorithms for a problem does performs some task like computing some other things during its computation but that is not simple at all!

Moreover why would we care? What we care about in practice is not that the algorithm computes all previous primes, but rather time and space efficiency. So I guess a better way of asking your question is asking if there is more efficient way of computing $n$th prime number than sieve-based methods.

If you are asking if there is a provably correct and efficient algorithm to find $n$th prime given $n$ in binary the answer is that is an open question. We don't know if there is any such algorithm, and we don't know if there isn't one. AFAIK, it is consistent with our current state of knowledge that there are algorithms for generating the $n$th prime that run in linear time in $n$. In fact, it can even be the case that we can generate the $n$th prime from bits of $n$ using a polynomial-size constant-depth circuit with threshold gates ($\mathsf{TC^0}$), in simplified non-technical terms: there can be a parallel algorithm with polynomial number of processors that generates the $n$th prime number in constant time and each processor computes very simple functions. So there is big gap between algorithms that we have (upper-bounds) and lower-bounds we can prove for the problem.

However we have algorithms that work efficiently and correctly assuming conjectures like conjectures about how primes are distributed.

See the Wikipedia article on generating prime numbers if you haven't. Also you may want to check this question: Which is the fastest algorithm to find prime numbers?


Please run your code with four more lines of printing statements, as shown below. Once you have seen the output, it will be immediate for you see what is happening. Basically, given the sequence 8 1 9 3 5 7 6, the partition routine rearranges it to 1 3 5 8 9 7 6 at first. Then it exchanges 6 with 8, the first element beyond the end of elements not larger than 6. So the sequence becomes 1 3 5 6 9 7 8.

System.out.print("Pivot with " + pivot + ": ");  // add this line
printArray(arr);  // add this line

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

System.out.print("Exchange   " + pivot + ": ");  // add this line
printArray(arr);  // add this line

Aside from the question proper, what you needed most is an Integrated Development Environment (IDE) where you can trace code execution and check the values of all relevant variables step by step easily. Using the command line can only serve as a temporary measure. I recommend Intellij Community Edition; others might have different recommendations. Once you are able to use that machinery, you will be able to answer others' questions such as this one just like I have answered your question. Well, as long as you will program in java, an IDE is a must unless you do not mind lagging behind other by a factor of 2 to 10. Just a bit of unsolicited advice that I offer to everyone of my local students. It is entirely up to you what to do, of course.


How to use different size features in SVM?

I think you have a misconception.  SVM does not necessarily give the latter 58 features a weight of 58/59.  Rather, SVM learns what weights to use for each feature, based upon what helps it build the best classifier.

So, just use those features and train with them.  Don't try to find a way to manually provide different weights for the features; SVM training automatically takes care of that for you.


A Haskell type class defines a set of functions (sometimes called methods) that belong to the type class. In most cases, specific instances must supply specific implementations of one or more of these.

An instance can implement all methods, or just enough to make the instance work. If an instance doesn't implement all methods, the default implementations are used.

Type classes are typically documented with the minimal implementation required. This is also true for Bifunctors:

Minimal complete definition

bimap | first, second

This means that an instance must implement either bimap, or both first and second. An instance can also implement all three, but that's not required.

The tuple instance, for example, is implemented using bimap:

instance Bifunctor (,) where
  bimap f g ~(a, b) = (f a, g b)

This means that the first and second implementations are the default implementations you quoted above. They call the instance's bimap implementation.


Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory

The original  statement in my question
sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))
is a valid statement in Homotopy Type Theory but because (homotopy-) isomorphisms are a special case of equivalences, the statement can be generalized to

sym (ua fEquiv) ≡ (ua (invEquiv fEquiv)) (*)

It is one of the properties of ua that are informally proven in the Univalent Foundations book in section 2.10.

Solution

The results from 1 have been implemented and proven in the lemmas in the Agda Cubical library. The function uaInvEquiv of those lemmas in particular solves my problem (*). For future applications it is better to use 4 because they are more general than my own approach below.

Historical solution

Using the hint to use EquivJ, I gave a proof for the theorem that may not be the most efficient one but it worked (typechecked) for my specific case:

baseIndLemma : (A : Type ℓ-zero) → (λ i → ua (idEquiv A) (~ i)) ≡ ua (invEquiv (idEquiv A))
baseIndLemma A =
  sym ( ua (idEquiv A) ) ≡⟨ uaIdEquiv ⟩
  sym refl ≡⟨ refl ⟩
  refl ≡⟨ sym uaIdEquiv ⟩
  ua (idEquiv A) ≡⟨ cong ua (equivEq (idEquiv A) (invEquiv (idEquiv A)) refl) ⟩
  ua (invEquiv (idEquiv A)) ∎

myUaInvEquiv : sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))
myUaInvEquiv = EquivJ
  (λ _ _ e → sym (ua e) ≡ ua (invEquiv e)) (λ A → baseIndLemma A) ℕ₀ ℕ fEquiv


Triangulate the polygon
Determine in which of the triangles the point should lie (weights triangle areas)
Sample the point in the triangle as explained in this post


Basic action for every data structure O(1)

What was meant is that every data structure is designed to do something really well, e.g:

For an array, lookup by index is O(1)
For a linked list, insertion at the head is O(1)
For a heap, finding the smallest element is O(1)

... and so on. This doesn't mean that the operation that is O(1) for one data structure wouldn't have much worse complexity for some other data structure.


When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

Beware the abuse of notation; I can not recommend using "$2^{O(n)}$".

That said, a common interpretation is using the placeholder semantic. That is, we read

$\qquad\displaystyle f \in 2^{O(n)} \quad"\iff"\quad \exists\, g \in O(n).\ f \in O(2^{g(n)})$

Compare that to the definition of $O(2^n)$ and you'll quickly see that the two are not the same.

   Because $2^{cn} = (2^c)^n$, the term "$2^{O(n)}$" covers all exponentially bounded functions, i.e. the union of all $O(a^n)$; use $c = \log_2 a$.

Your titular question should answer itself now.

   Since $3^n \not\in O(2^n)$, this Landau class does not cover all exponential function. This is easy to show independently of above discussion, by the way.

Note how the "definition" makes two $O$ out of one; that's why I think that notation is bad. See also this related question where is becomes clear that even experts don't agree on what the notation should mean here, exactly. Here's another related question.


Starting point:
$$
S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b
$$
Substitute values of $A,B,E$:
$$
S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b
$$
Substitute values of $D$:
$$
S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon
$$
You can generate $bb$ from $C$ even without the rule $C \to bb$:
$$
S \to aCC \mid aCb \\ C \to bC \mid \varepsilon
$$
You can generate $b$ from $C$:
$$
S \to aCC \\ C \to bC \mid \varepsilon
$$
The language of $C$ is $b^*$, so $CC$ generates exactly the same words as $C$:
$$
S \to aC \\ C \to bC \mid \varepsilon
$$

The grammar generates the regular language $ab^*$.


What are all the decidable languages that can be constructed using a turing machine with only the Reject and Accept states?

If there are only two states, the rejecting state and the accepting state, then the machine must start in one of those states. That means it must immediately halt, which should tell you what language it can accept.


Why 2 way DFA have the same power as one way DFA?

The intuitive explanation why two-way DFA and NFA are not more powerful than DFA is that all these variations have finite memory. A non-deterministic or two-way automaton has more memory per state than a basic DFA, but as long as there's only a finite amount of memory, a fancy automaton is no more powerful than a DFA with perhaps more states.

A two-way DFA can retrace its steps, but it has no memory of it. When the automaton is at a certain position in the input, the only thing that encodes how it got there is the state, and it's taken from a finite state. So there's no way for the automaton to behave differently based on the position or the movement history.

Let's look a bit more precisely at how a DFA can simulate a two-way DFA, i.e. how the memory of a two-way DFA can be represented in a DFA. The states of a DFA represent all that is known about the input after reading a prefix of the input. Reading a word $uv$ can be decomposed into 1. reading $u$ from the initial state and 2. reading $v$ from the state reached after reading $u$. The information about the partial input $u$ that the DFA remembers is simply the state reached after reading $u$.

Before studying this for a 2DFA, let's do it for an NFA. An NFA reads its input sequentially from left to right like a DFA, but at each stage, any set of states of the NFA may potentially be reached. Thus, the information about a partial input that the NFA remembers is the set of reached states. There are at most $2^n$ sets of states in a world with $n$ states, and therefore an NFA with $n$ states can be simulated by a DFA with at most $2^n$ states. This is in fact a tight bound.

In an NFA with $n$ states, the amount of information in the system is encoded in the set of reachable states. Each new input character triggers a transition from a set of states to a new set of states. Since there are $2^n$ sets of states, an NFA can be converted to a DFA that recognizes the same language and that has at most $2^n$ states.

Let's now turn to a two-way DFA with $n$ states. After reading some input $u$, the 2DFA remembers what state it has reached. In addition, after reading more input, the 2DFA may backtrack into $u$ and, perhaps, come back out. We want to abstract $u$ away completely, so we need to count all the ways to backtrack into $u$ and come back. If the 2DFA ever backtracks into $u$, it may do so from any state $q$ amongst its $n$ states. When it comes back out, it will have reached some other state $q'$ (perhaps the same, it doesn't matter). The state $q'$ depends on $q$ and $u$, but it doesn't depend on what comes after $u$, since by definition $q'$ is the state reached after working through $u$ in a deterministic automaton. Therefore each prefix $u$ defines a mapping from $q$ to $q'$. The information stored in the 2DFA after processing $u$ consists of the initial exit state (which state is reached immediately after reaching the end of $u$) and the mapping from reentry state to subsequent exit state. (I don't claim that all mappings are possible.) There are $n$ initial exit states, and $n^n$ mappings of state to state. Thus the information in a 2DFA after processing some prefix consists of at most $n \times n^n$ different possibilities. This means that a 2DFA can be simulated by a DFA with at most $n \times n^n = n^{n+1}$ states.

The tight bound is in fact $n \times (n^n - (n-1)^n)$. I don't have an intuition for the second term.


Are too many function calls bad(as in slows speed performance) for programs written using interpretor-based scripting language(JavaScript, Perl)?

Practically speaking, function calls have a cost.  They have a cost if your language is interpreted.  They have a cost of your language is compiled.  Some compilers can substitute the code for some functions (it's called inlining), but in the vast majority of cases, one does not do that.

However, the cost of a function call is low.  If you have a 50 line function with a reasonable amount of work done on each line, you'll find function calls account for less than 1% of your total runtime.  Their value in organization typically far exceeds their cost.

You don't want to be excessive with function calls unless you can inline them.  Some styles of code depend on inlining, such as some C++ code which may have 10+ function calls nested and do perhaps 3 lines worth of work.  That kind of a situation demands inlining.  However, for the vast majority of the cases, don't worry about it.

You will eventually learn how to profile your code, which is a way to find hotspots where you spend a lot of your time.  Always profile before you optimize.  You will find that most of your function calls don't have a significant effect on runtime at all, and if you're unlucky, 3-4 functions might have too much overhead.  Then you remove those functions, inlining the code manually, and you leave all of the other functions.

If you're interested in numbers, it is estimated that a function call in Python (an interpreted language) costs between 150ns and 350ns.  In C++, the cost is on the order of 15-30 instructions, which is on par with a L1 cache miss (if that term doesn't mean anything to you, it's a good indicator of just how fast these function calls are).  On a 4GHz processor, that's 4-8ns.


Do we know how to make a "voice print" and use it for computer generated voice?

See the Voice transformation project from the The Center for Speech Technology Research at the University of Edinburgh.
Thesis: Transforming Voice Quality and Intonation by Ben Gillet.
It doesn't do exactly what you are asking, but something similar; it tries to change the voice of a recording to another voice.
Abstract:

Voice transformation is the process of transforming the characteristics of speech uttered by a source speaker, such that a listener would believe the speech was uttered by a target speaker. In this thesis two aspects of the transformation problem are addressed: voice quality and intonation
The voice quality transformation component of our system has two main parts corresponding to the two components of the source-filter model. The first component transforms the spectral envelope as represented by a linear prediction model. The transformation is achieved using a Gaussian mixture model, which is trained on aligned speech from source and target speakers. The second part of the system predicts the spectral detail from the transformed LPC parameters. A novel approach is proposed, which is based on a classifier and residual codebooks. The system has some similarities with earlier work by Kain, however the work reported here is not restricted to speech spoken in a monotone and with mimicked prosody. Also, on the basis of a number of performance metrics it outperforms existing systems.
We also present a new method for the transformation of pitch contours from one speaker to another based on a small linguistically motivated parameter set. The system performs a piecewise-linear mapping using these parameters. A perceptual experiment, clearly demonstrates that the presented system is at least as good as the existing technique for all speaker pairs, and that in many cases it is much better and almost as good as using the target pitch contour.


Yes, exactly. Because you can instantiate the polymorphic type with an infinite amount of (mono)types.

For example, the type $a \to a$ (which is a polymrphic type) represents

Bool $\to$ Bool
Char $\to$ Char
(Char $\to$ Int) $\to$ (Char $\to$ Int)
etc...