In algorithm analysis what does it mean for bounds to be "tight"

Generally speaking, a bound is tight if there is no "better" bound.

Take, for instance, $f(n) = \sin(n)$. Then, $-1.5 \leq f(n) \leq 2n$ are valid bounds on $f$ but they are not tight -- there are better bounds, e.g. $-1.2 \leq f(n) \leq 1.5n$.

Now, $-1 \leq f(n) \leq 1$ are tight bounds -- there are no tighter ones.

You will note that the range of $n$ is relevant here. I implicitly let $n \in \mathbb{N}$ (or $\mathbb{R}$ if you want) here; if we consider $n \in \{ \pi i \mid i \in \mathbb{N} \}$ there are better bounds.

Now, using Landau symbols the terminology is used similarly: $f \in \Omega(n)$ is a tight bound if there is no "better" $\Omega$-bound, i.e. one with a faster-growing parameter function. If we also know that $f \in O(n)$, then both bounds are tight and we have $f \in \Theta(n)$. It is, however, very possible that you have, say, $f \in \Omega(n)$ and $f \in O(n^2)$ and both bounds are tight.

Here, and in particular in the context of algorithm analysis, the range of (the implicit) parameters is relevant as well: are you talking about all inputs? Worst-case inputs? The average case? For instance, $\Omega(n)$ is a tight (lower) bound on the asymptotic running time of (improved) Bubblesort if you consider the best case, but not for average or worst case.

Note that "tight" can be relative to your goals. If you want to prove asymptotics of the form $f \sim g$, you wouldn't call a $\Theta$-bound "tight".


This problem seems to be NP-hard.  A reduction from 3-SAT is left as an exercise, but here is a hint.  The empty nodes are free, and then create a color for each literal and its negation.  The cost is 1 for each.  You can then visit a "clause" for free if and only if one of its literals is selected.  Now, the cheapest s-t-path costs $n$ if and only if the formula is satisfiable.


Probability of k-clique in a random graph

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$.

Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On the other hand, it is known that the expected number of cliques of size $k_0+1+C$ is $O((\log n/n)^C)$ for any constant $C$ (this is because the expected number of cliques drops by $\Theta(\log n/n)$ near $k_0$). This shows that $k \leq k_0+3$. We conclude that $k_0 \leq k \leq k_0+3$.

You can probably decrease the length of this interval by 1, following the proof of the classical result which shows concentration of the clique number of two values rather than three.


Prove that $L_1 = \{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\}$ is not regular using Pumping lemma

For your choice of $s=0^11^12^2$, the pumping lemma might not apply. Remember, assuming that the language is regular means that there is an (unknown) integer $p$ such that the pumping lemma applies to every string of length $p$ or more. You don't know what $p$ is: if it were, say, 6 then since $|s|=4$ the PL simply wouldn't apply to your string and you could draw no conclusion.

That's why the strings chosen for pumping almost invariably involve $p$: it's there to assure that no matter what $p$ was, the pumped string would be at least $p$ characters long. For your example, you could choose $0^p1^p2^{2p}$ or $0^p1\,2^{p+1}$ or $0^p2^p$ even something like $0^{p^2}1^{2p+1}2^{(p+1)^2}$.

Here's what a PL proof of this result looks like, with some bits for you to fill in: Assume the language $L$ is regular. Choose $s=0^p1^p2^{2p}\in L$, where $p$ is the integer of the pumping lemma (why can we say the PL applies to $s$?). Then if we write $s=xyz$ as in the PL, we'll have $y=0^t$ for some $0<t\le p$ (why?) and then $xy^2z\notin L$ (why?), a contradiction (why?).

The proof without the PL is an example of a more or less common idiom: using closure properties. If $L$ were regular, then $L\cap 0^*2^*$ would be also, since regular languages are closed under intersection. However
$$
L\cap 0^*2^*=\{0^n2^n\mid n\ge 0\}
$$
(since we set $k=0$ when doing the intersection) but we know that that language isn't regular, so we have a contradiction and hence $L$ must not be regular.


An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).


Is this FA really equivalent to the given regular expression?

They aren't equivalent. For example, the string "L__L" is described by the expression, but not accepted by the automaton (no way to have two '_' in a row).


In general, proof crafting is a dark art. There is no simple universal strategy which in all cases leads to a proof, in the shortest way, with the least effort. One usually relies on instinct and experience (doing several exercises helps greatly).

Trying to reconstruct the derivation bottom-up is often a good strategy. However, note that in natural deduction (unlike some other systems) going bottom-up one needs to cope with infinitely many possibilities.

For instance, if I have to prove $A$, I could try to deduce it through modus ponens / implication elimination:

$$
\dfrac{\dfrac{\vdots}{B\rightarrow A} \qquad \dfrac{\vdots}{B}}{A}
$$

However, formula $B$ above could be anything! I have to chose among infinitely many formulas, which is not easy.

Worse, in some cases it is needed to exploit some rule like double negation elimination

$$
\dfrac{\lnot\lnot A}{A}
$$

It is not obvious when this is needed. For instance, I know that using this rule (or something equivalent like the law of excluded middle) is needed to prove $((A \to B)\to A)\to A$, but I can see this only because this is a very famous logical formula (called Peirce's Law).

At the end of the day, one can try a few heuristics, but should expect to have to backtrack a few times. In general the problem is very hard, but fortunately the exercises which one finds in books / exams usually are solvable with some intuition and little backtracking.


Best practices for normalizing up training, validation, and test sets

Yes, that's what it means.  Basically, mean_T1 and var_T1 become part of the model that you're learning.  So, same as you'd apply machine learning to the training set to learn a model based on the training set, you'll compute the mean and variance based on the training set.


Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

A roung, informal sketch of how I would prove this:

We can simulate multiple threads running concurrently in a programming language like C. (Note that this is without hardware support! There are some cool ways to do this, my favorite is using continuations in Scheme, inserting a call to a thread scheduler whenever a function returns).
We can simulate a multi-tape TM with a single-tape TM.
We can simulate a single-tape TM in a programming language like C.

From this, we get that we can simulate a multi-tape TM in our programming language. Since we can simulate threads, we can now simulate multiple multi-tape TM's running concurrently.
And, since we can simulate C with a single-tape TM, we can simulate the whole thing with a single-tape TM.

The transitivity of turing-completeness is a useful tool. That is, if A simulates B, and B simulates C, then A simulates C.


You can unroll the procedure:

x = 4;
y = 2;
u = x;
v = y;
u = 2*u;
x = u+v;
u = u-1;
print x;

This is semantically equivalent to your program.

Once you copy the value of x to u, the link between the two disappears. This is in contrast to references in C++ or mutable objects in python, which are really pointers; if u were a reference (i.e., if parameters were passed by reference), then the assignment u = x would have identified the two variables as pointing at the same location in memory. As it is, u is just a value (since parameters are passed by value), and so this linkage is absent.


Drawing Annotated Parse Tree for Syntax Directed Definition

The Dragon book style starts with the parse tree of the expression, i.e., the root (I think the very top is a mistake, the expression is an error as written) is the step $E \Rightarrow E + T$. The tree is then decorated giving the attributes their value (like $E.val = 19$). In an attributed grammar you give the grammar and the attributes, so that the grammar looks in part as (subindices mark diferent uses of the same symbol, left to right):
\begin{eqnarray}
E \rightarrow T \quad E.val \leftarrow T.val \\
E \rightarrow E + T \quad E_0.val \leftarrow E_1.val + T.val
\end{eqnarray}
You see that the answer to your second question is that the value of the child $F$ is used to compute the value of $T$.


Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

$2$-connectedness is the same as bridgeless.

So $M$ must be the set of bridges in $G$ no matter how large or small their sum is.


How can Kolmogorov complexity help me practically with measuring entropy?

How can Kolmogorov complexity be useful to you in measuring the complexity of this data?  It can't.  The Kolmogorov complexity of a sequence of bytes is not computable.

Don't read too much into that comment.  I'd take it as hinting that the idea of Kolmogorov complexity might be a relevant or interesting concept to know about, not necessarily that you can directly compute that value in a particular real-life situation.  Anyway, just because someone wrote something doesn't mean it's true.  If you're not sure what they meant by it, or you are wondering what justification they had for saying that, you might need to ask them.

I notice that Yuval Filmus's answer to the question you linked to provided a similar summary of Kolmogorov complexity, so I'm a bit confused about what is unclear here.


Designing a DFA for binary strings having 1 as the fourth character from the end

You have not created a DFA.

What you have created is a second slightly less messy NFA. (Sort of; as mentioned in comments elsewhere you need the explosion of internal states out from (2) that you have out from (9) in the original NFA)

So let's pretend that we have an NFA that is made by chopping off state (2) in the second picture and adding state (9) from the first picture in its place.

Now, let's walk through the powerset construction on that new NFA:

Start in state {1}. So let's call the DFA state corresponding to the singleton set {1}, DFA_1.

From DFA_1 you can see either a 0 or a 1. On 0, DFA_1 goes to {1}, so DFA_1 again. On 1, it goes to {1,9}. Call that DFA_2.

From DFA_2, on 0 it goes to {1,10,13,16,19}. Call that DFA_3. On 1 it goes to {1,9,22,25,28,31}. Call that DFA_4.

For DFA_3, on 0 it goes to {1,11,14} (since the other nodes only have transitions out on 1). Call that DFA_5. On 1, from DFA_3 we go to {1,9,17,20}. Call that DFA_6.

For DFA_4, on 0 it goes to {1,10,13,16,19,23,26} - call that DFA_7. On 1, DFA_4 goes to {1,9,22,25,28,29,31,32}. Call that DFA_8.

For DFA_5, on 0 it goes to {1,12}. Call that DFA_9. Note that DFA_9 is an accepting state. On 1 it goes to {1,9,15}. Call this DFA_10, also an accepting state.

For DFA_6, on 0 it goes to {1,10,13,16,18,19}. Call this DFA_11. On 1, we get {1,9,21,22,25,28,31}. Call this DFA_12. Note that DFA_11 and DFA_12 are accepting states.

For DFA_7, on 0 it goes to {1,11,14,24}. Call that DFA_13. On 1, we get {1,9,17,20,27}. Call that DFA_14. (DFA states 13 and 14 are accepting states)

For DFA_8, on 0 it goes to {1,10,13,16,19,23,26,30}. Call that DFA_15. On 1, it goes to {1,9,22,25,28,29,31,32,33}. Call that DFA_16. (DFA states 15 and 16 are accepting states)

For DFA_9, on 0 it goes to {1}. We've seen this before! That's DFA_1. On 1 it goes to {1,9}, which is DFA_2.

For DFA_10, on 0 it goes to {1,10,13,16,19}, that is, DFA_3. On 1 it goes to {1,9,22,25,28,31}, that is DFA_4.

For DFA_11, on 0 it goes to {1,11,14}, which is DFA_5. On 1 it goes to {1,9,17,20}, that is, DFA_6.

For DFA_12, on 0 it goes to {1,10,13,16,19,23,26}, or DFA_7. On 1, it goes to {1,9,22,25,28,29,31,32}, or DFA_8.

For DFA_13, on 0 it goes to {1,12} (DFA_9). On 1 it goes to {1,9,15} (DFA_10).

For DFA_14, on 0 it goes to {1,10,13,16,18,19} (DFA_11). On 1, we get {1,9,21,22,25,28,31} (DFA_12)

For DFA_15, on 0 it goes to {1,11,14,24} (DFA_13) On 1, we get {1,9,17,20,27} (DFA_14).

For DFA_16, I hope you can see the pattern by now. On 0 it goes to DFA_15 and on 1 to DFA_16.

So, in summary:

DFA state #  |   Next for 0  |  Next for 1  |  Accepting?
---------------------------------------------------------
          1  |       1       |      2       |
          2  |       3       |      4       |
          3  |       5       |      6       |
          4  |       7       |      8       |
          5  |       9       |     10       |
          6  |      11       |     12       |
          7  |      13       |     14       |
          8  |      15       |     16       |
          9  |       1       |      2       |  yes
         10  |       3       |      4       |  yes
         11  |       5       |      6       |  yes
         12  |       7       |      8       |  yes
         13  |       9       |     10       |  yes
         14  |      11       |     12       |  yes
         15  |      13       |     14       |  yes
         16  |      15       |     16       |  yes

As a side note, I think this process might have been simpler had you started with an NFA of only 5 states corresponding to the regex (0|1)*1((0|1)(0|1)(0|1)).

(Though you'd still end up needing 16 DFA states - it can be proven that that's the minimal number of DFA states needed for this problem)


What you are missing is a definition of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first link) makes it clear that you can choose whether it is the inside or the outside of the circle which gets the value +1, and this shows that any two points whose distance from the origin is not the same can be shattered, and so the VC dimension is at least 2.


From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?

Trivially, yes: the grammar is extractible from the items.

Probably more in the spirit of the question. LALR(1) is easily extracted from LR(1): merge LR(1) items which correspond to the same LR(0) one and the grammar isn't LALR(1) if that process results in conflicts. (BTW this can be considered as a definition of LALR(1)).

SLR(1) is not so easy; you need to compute the follow sets to find out if there are conflicts. (SLR(1) is based on the LR(0) items like LALR(1), but it has "unneeded" conflicts due to the use of follow sets instead of the computation of look ahead one to choose which production to reduce.)


Shortest walk through a given subset of edges

This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ becomes a pair of vertices $v_+, v_-$ connected by an edge in $G'$.  All of these edges should also be added to $F$.  Then for each $(u, v) \in E$, add the corresponding 4 edges $(u_-, v_-), (u_-, v_+), (u_+, v_-), (u_+, v_+)$ to $E'$ (but not to $F$).  All edges in $E'$ get weight 1.

Now if and only if there is a Hamiltonian Path in $G$, there is a path (and thus also a walk) of length $2|V|-1$ in $G'$ that passes through all the edges in $F$.  (Exercise: Prove that if a walk having length $2|V|-1$ and passing through all edges in $F$ exists in $G'$, then $G$ has a Hamiltonian Path; the other direction is easy.)  IOW, if your problem could be solved efficiently by some algorithm, then that algorithm could be used as a subroutine to solve Hamiltonian Path efficiently too, and people don't think that's very likely.


An easier problem to use would be max clique. We do the transformation as follows. We take the graph that we wish to find the max clique in and give all edges in it weight 1, and for all non edges we give weight (-)infinity (or if you dont like infinity an arbitrarily large number based on the number of edges total, negative enough so that if one is picked the total will always be negative). This problems solution will give us a clique since the negative infinity weight will prevent selecting anything that does not have edges between them for the solution. This clique is also the largest, as a larger clique would have a larger edge sum and we assume this algorithm returned the largest edge sum. This is therefor at least as hard as solving max clique, which is NP complete.


turing machine logic instead of something

You could write $\neq 2 \to x,R$, but you might have to explain somewhere that by that you mean that the transition is taken as long as the symbol read is not $2$.

More generally, you can use whatever notation you want as long as you explain it and it's unambiguous.

This is the answer of a practical mathematician. Your professor could have different ideas.


Use of -1 to express edge cases in computer programs and data structures

Most PL folks would probably suggest that an option type is better suited.

For instance, in Haskell you'd use a Maybe T type: you use Nothing instead of -1, and Just x instead of x.  In SML, you'd use a T option type, and use None instead of -1 and SOME x instead of x.

The benefit of this is to better document the meaning of the sentinel value, and also to force the programmer to consider both cases everywhere it is relevant.  This helps avoid certain kinds of programming mistakes, where a -1 value is inadvertently used as if it were a real value.  It also ensures that the domain of the type T is separate from the sentinel value.

In a language without an option type, you can also use tagged unions or other methods of encoding this into the type system or class hierarchy.

That said, this is a pretty subjective question.  Opinions will vary.  You should not expect everyone in a field to share the same opinion about a subjective matter like this.


In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition?

The example is part of the construction to obtain a finite automaton for each regular expression. This construction is known as Thompson's construction and works recursively. Given automata $A(e_1)$ and $A(e_2)$ for expressions $e_1$ and $e_2$, instructions are given to build new automata for the expressions $e_1 + e_2$, $e_1\cdot e_2$ and $e_1^*$. These new automata contain a lot of $\varepsilon$-edges to connect the original parts.

Hence the purpose of the example is not to give an efficient automaton (that is a no-brainer for $ab$) but to illustrate these constructions.


Determine smallest possible parameter set for FPT

Recall that the runtime must be of the form $f(k) \cdot n^c$ for some constant $c$. So I believe that the exercise is asking, given that all three are at most $n$, which do you have to take as formal parameters in your analysis to achieve an FPT runtime.

So if only $p$ is a parameter, is that FPT? What if only $q$? Clearly, if both are fixed, you have FPT runtime.


Why does introsort use heapsort rather than mergesort?

The 2 downsides of quicksort is that it requires $O(\log n)$ extra space (to keep the unsorted intervals) and bad pivot selection (or contrived sequences designed to make you select a bad pivot) may cause it to be a $O(n^2)$ time and $O(n)$ extra space algorithm.

Switching to heapsort when the recursion depth becomes too large (at around $\log n$) means we have a guaranteed upperbound that is $O(n \log n )$ time and $O( \log n)$ extra space.

Heapsort's $O(1)$ extra space requirement makes it a better choice to mergsort's $O(n)$ where for a contrived array that $n$ could still be large.

The reason heapsort isn't used for the full sort is because it is slower than quicksort (due in part to the hidden constants in the big O expression and in part to the cache behavior)


Multiplication of two or more algebraic quantities

Your algebraic quantities are polynomials in one variable. Multiplying two polynomials is an important computational problem with many applications. You can store a polynomial in two ways:

store the coefficients, that is for $p(x)=3x^2-x+3$ you store $(3,-1,3)$
store enough samples, that is for  $p(x)=3x^2-x+3$ you might store three values like $p(0)=3,p(1)=5,p(-1)=7$ (if your highest exponent is $k$ you need $k+1$ samples)

To multiply two polynomials you can do the following. Assume the coefficients of the first polynomial $A(x)$ are named $a_i$ and of the second $B(x)$ they are  named $b_i$, then the coefficients for $A(x)B(x)$ are the coefficients $c_i$ with
$$c_k= \sum_{(i,j)\colon i+j=k} a_ib_j$$

Without tricks this takes $O(n^2)$ time.

Another possibility is to multiply the samples (if they are taken at the same positions). The problem here is, that the product has a higher degree. That means that you need more samples than you needed for the original polynomials. So you had to record more samples in the beginning. What is even more severe is that it is not easy to evaluate the polynomials on arbitrary positions if you only have the samples. So the multiplacation goes fast in $O(n)$ time if you have enough samples, but the evaluation might need $O(n^2)$ time per se.

But here is the thing. You can change from one representation to the other in only $O(n \log n)$ by a famous algorithm called fast Fourier transform (FFT). In a nutshell you pick you sample points very clever and then you divide and conquer. Using FFT you can multiply and evaluate polynomials in time $O(n\log n)$. If you dont care so much about speed, just use the coefficient representation and the formula above.


Estimate the running time of counting nodes in a binary tree

Hint 1. You say the running time is $O(2^N)$ but what is $N$?  $2^N$ would indeed be bad if $N$ were the number of nodes.

Hint 2. How many times does your code visit each node in the tree?  How much time does it spend on each node?


Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays

A HashSet can store $n$ elements in $\mathcal{O}(n)$ space and add/query elements in amortized $\mathcal{O}(1)$ time. Therefore we can use the following approaches:

1. Are A's values distinct?

HashSet setA;
for i in {1, ..., n}
    if setA.contains(A[i])
        return "No, A[i] is a duplicate.";
    endif
    setA.add(A[i])
endfor
return "Yes, values are distinct.";

2. Do A and B intersect?

HashSet setA, setB;
for i in {1, ..., n}
    if setB.contains(A[i]) or setA.contains(B[i])
        return "Yes, A and B intersect.";
    endif
    setA.add(A[i]);
    setB.add(B[i]);
endfor
return "No, A and B are disjoint.";

Edit: Thanks to D'Nabre for pointing out a problem. The assumed $\mathcal{O}(1)$ for querying the HashSets may not work out in this case. D'Nabre also pointed at the element distinctness problem, which is worth a look. From Wikipedia:

  it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.


Find vectors with elements of finite fields that sum up to given value

It looks like subset-sum problem. It should be possible to adapt the pseudopolynomial algorithm.


Vertex cover of a graph by removing leaf-vertices from a DFS tree

Look at the definition of vertex cover (as provided by the book). It is strictly defined on undirected graphs. Thus, the answer doesn't apply to directed graphs, nor to any other kinds of graphs you might think of. So your counterexample is invalid, as it makes invalid assumptions (graphs are always undirected here). These invalid assumptions are the source of your confusion.

To consider directed graphs, we first need to define what a vertex cover is on a directed graph. Well, we can say it is a subset of vertices such that every arc is incident to at least one vertex in the subset. Again, the book makes no claim about such directed vertex covers. If you are now asking "does $\{ a \}$ form a (directed) vertex cover as per our definition?", the answer is NO as you correctly observed.


Problem with Understanding a Recursion Tree

Think of it this way, you have a mathematically formal description of a recursive function. Which every function maps an element (or more than one element) To 1 element in the codomain.

What would T(0) be in terms of this functions as an input? It wouldn't change the time complexity.


Algorithms to prioritize equipment renewals

Given the clarification to the question, it is a 0-1 knapsack problem (your knapsack is the money available, the value is the objective function), and look for ways to solve that one, for example following the Wikipedia lead.

Edit: A simple approximate algorithm would be just sort equipment on increasing cost per unit (age * importance), and in that order include each if it fits (doesn't run over maximal cost). In the case of continuous knapsack (i.e., can include a fraction of a item) that strategy is optimal. Should work fine if there are many items, and the data isn't too spread out.


Understanding trap and dead state in automata

The concepts you mention are not formal concepts. You can define several notions of a dead state, for example (focusing on DFAs):

A dead state is a non-accepting state with self-loops for all symbols.
As in definition 1, but we also require the state to be reachable.
A dead state is a state from which no accepting state is reachable.
As in definition 3, but we also require the state to be reachable.

If we allow some transitions to be "missing" (i.e., our definition of DFA defines the transitions function as a partial function rather than as a function) then we have more possibilities, for example:

A dead state is a non-accepting state in which all outgoing transitions are self-loops.
As in definition 1, but we also require the state to be reachable.
A dead state is a non-accepting state without outgoing transitions.
As in definition 3, but we also require the state to be reachable.

If the exact definition used matters, the concept should be explicitly defined. It is usually used in a somewhat informal way, in which the intended meaning is usually obvious from context.


Is inserting into an ordered array by swapping has downsides compared to inserting into a position and offsetting elements

Both work.  Both approaches are approximately equivalent, in some sense.  However, your approach will do about twice as much work.

Think about an array that initially contains $[2,4,6,8,0]$ where the $0$ is the final empty element that can be filled in.  Imagine you want to insert the number $5$.

The standard method will read $8$ from index $3$, then write $8$ to index $4$, yielding $[2,4,6,8,8]$; then read $6$ from index $2$ and write $6$ to index $3$, yielding $[2,4,6,6,8]$; then write $5$ to index $2$, yielding $[2,4,5,6,8]$.  That's 2 reads and 3 writes -- 5 memory operations.
Your method will swap $8$ and $0$, yielding $[2,4,6,0,8]$ (this involves reading $8$ from index $3$, reading $0$ from index $4$, writing $8$ to index $4$, writing $0$ to index $3$); then swap $6$ and $0$, yielding $[2,4,0,6,8]$; then overwrite the $0$ with $5$.  Each swap requires 2 reads and 2 writes, so this does a total of 4 reads and 5 writes -- 9 memory operations. That's about twice as much.

Why is your method slower?  Because your method keeps reading the $0$ and writing it somewhere.  That is extra, unnecessary work.  If you care about optimization, that might matter.  If you just want a method that you can understand, either one should be fine.


Denote the closure of a class C of languages under log-space many-one reductions by Closure( under log-space many-one reduction of, C), and the closure of a class C of languages under e-free homomorphisms by
Closure( under e-free homomorphisms of, C). So for example

NP=Closure( under log-space many-one reduction of, NP)
NP=Closure( under e-free homomorphisms of, NP)

We want to show:

  If P=Closure( under e-free homomorphisms of, P) then P=NP.

For this, it is sufficient to show

P=Closure( under log-space many-one reduction of, P)
NP=Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))

because if P=Closure( under e-free homomorphisms of, P) then
NP=Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))
=Closure( under log-space many-one reduction of, P)=P

It is well known how to show (1). For showing (2), it is sufficient to show

NP=Closure( under log-space many-one reduction of, {SAT})
SAT $\in$ Closure( under e-free homomorphisms of, P)

because if X$\subset$Y then Closure( under ... of, X)$\subset$Closure( under ... of, Y).

It is well known how to show (3), which says that SAT is NP-complete under log-space many-one reductions. For showing (4), note that certificates of length O(n) are sufficient for SAT, where n is the length of the input. So we need to show that e-free homomorphisms can erase a certificate of length O(n) from the input, if the certificate is encoded suitably. This is straightforward in a certain sense, but we have to change the alphabet. The letters of the larger alphabet contain both an original input letter, and an additional certificate letter. To "erase the certificate", the homomorphism replaces this pair of "(original letter, certificate letter)" by the "original letter".

If you want to stay with the 0-1 alphabet, then homomorphisms from the free monoid over 0-1 can't erase information selectively enough, because such a homomorphism is already uniquely determined by the image of 0 and 1. But if you look instead at the submonoid of words whose length is a multiple of some number k, then you can easily find suitable homomorphisms.


Number of nodes of height $h$ in a heap or almost complete binary tree

Except for the next to last level all nodes are full, nothing to show. On the last level there are only leaves.

Only on the next to last level there can be non-full nodes, i.e. nodes with only one child. And there can be leaves. So your reformulation should be "X-1 nodes must be full or leaves."

Now it depends on the definition if the statement is true. If the last level must be filled from left to right, for example (this is the case if you implement the tree as an array), the next to last level looks like:

full full ... full (one possibly non-full) leaf leaf ...leaf

If another element is added, it must be a child of the non-full node and thus will make it full. If one element is removed, the non-full node will become a leaf.

As I said, the exact details depend on the exact definition of almost full binary tree. If the last level can be filled in an arbitrary manner, then the statement does not hold.


Is the term page replacement actually a misnomer?

No.

A page is the entity in virtual memory.
A page frame is the real memory into which it is mapped.

So it is the page, not the frame, that is replaced.

The metaphor is that the (virtual) page is the picture around which the frame is placed. You move the frame to picture different pages. See here.


Theory of computation introductory curriculum

Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book is such a joy to read. It's written at an introductory level, which means less notation, more exposition, and more intuition. The motivation behind every idea and theorem is crystal clear. He precedes every proof with a "proof idea" section that lays out the path the proof is going to take without getting into the gory details. The book covers Automata Theory, Computability Theory, and Complexity Theory to a satisfactory depth for an undergraduate level. I've read many textbooks in computer science and math, and this is probably my favorite.


You can solve the first part by providing a valid topological ordering of the vertices, which shows that the graph is a DAG. To show that the union is equal to $E$ show that each arc in $E$ belongs to one of the two sets
The second part needs more context, what is OPT here?


Number of contiguous subsequences summing to a given target

Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a_1,\ldots,a_n$. Form a new array $b_0,\ldots,b_n$ containing the running sums of the previous array:
$$
b_0 = 0, \qquad b_i = a_1 + \cdots + a_i.
$$
Notice that $a_i + \cdots + a_j = b_j - b_{i-1}$. Therefore we can rephrase the problem as follows:

  Given an array $b_0,\ldots,b_n$ and a target $t$, find the number of pairs $i<j$ such that $b_j = b_i + t$.

As an example, if $A = 2,5,6,-1$ then $B=0,2,7,13,12$, and for $t=5$ we get two solutions: $7 - 2 = 12 - 7 = 5$.

The idea now is very simple: we scan $B$ from left to right, and for each $b_j$, we count the number of values $b_j-t$ which have occurred previously, storing them using a hash table.

Initialize the count of solutions: $N \gets 0$.
Initialize a hash table $H$ containing a single entry: $B[b_0] \gets 1$.
For $j = 1,\ldots,n$:

If $b_j - t \in B$, let $N \gets N + H[b_j - t]$.
If $b_j \notin H$, let $H[b_j] \gets 1$, and otherwise let $H[b_j] \gets H[b_j] + 1$.

Return $N$.

The same algorithm can be implemented in deterministic $O(n\log n)$ time using a self-balancing binary search tree.


Prefix computation used for lexical analysis?

The important fact in this case is that the list append operation is associative.

Hadoop has "tokenize" as one of its built-in parallel operators.  The meaning of "tokenize" in this case is much less general than "lexical analysis".  They mean "splitting a string at a specific well-defined set of `delimeter' characters."  I doubt there is much you could do with a more general lexical analyzer (one where you are running an arbitrary finite-automata over a string.)

So suppose you need to split a string at all the space characters.  You are essentially creating a list of indices into the string.  The list append operation is associative.  So each processor generates the appropriate list of indices for the substring assigned to it, and then you append all the lists together.


Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$

Hint: Can you do $$L=\{a^nb^m\mid m=3n\}$$

Try it also for: $$L=\{a^nb^m\mid m=3n-1\}$$

Then you might want to be able not to always have that many $b$.

And there is a bit more to take care of.


Arithmetic expressions grammar transformation

The missing step:

E --> P T
T --> B E T |

rewrite E in T:

E --> P T
T --> B P T T |

Simplify T:

E --> P T
T --> B P T |

Equivalent to:

E --> P T
T --> {B P}

And there you are.


The decision version of MAX-CUT is as follows:

  Given a graph $G$ and an integer $k$, is there a cut in $G$ containing at least $k$ edges?

This version is clearly in NP.


Is an algorithm in pseudocode a reasonable way to establish complexity?

To state the obvious, you need to prove that the language is decided by some Turing machine that uses a logarithmic amount of space on its work tape.

Anything beyond that is a question of how rigorous the proof should be. A proof should be rigorous enough to convince an appropriately skeptical reader. How much skepticism is appropriate in a given situation?  Well, that's a largely social construct. If we were chatting during a coffee break at a complexity theory conference, I'd probably be convinced by "Oh, just use a couple of binary counters to remember how many $a$s and $b$s you've seen. The input has length $n$ so the counters only need $\log n$ bits each."  If I was marking your undergrad complexity theory exam, I'd expect rather more detail. For example, our conference chat didn't include the fact that the machine should reject if it finds an $a$ after the first $b$ and your pseudocode also misses this, so it accepts the string $aba\notin L$.

Expecting a full definition of the Turing machine is probably unreasonable. First, it would take a long time to produce. Second, and more importantly, it would be sufficiently complicated that it would be hard to verify that the Turing machine really does what you claim it does. A proof that is too complicated for anyone to understand isn't really a lot of use.  That being the case, you're pretty much going to have to use pseudocode. If I wanted to test that you could produce a formal description of a Turing machine, I'd use a simpler language, such as the strings with an even number of $a$s in them.

Is pseudocode on its own enough? Not quite. For example, you can't just invoke Church–Turing to convert your pseudocode into a Turing machine. Why not? Because Church–Turing preserves computability but not complexity. So, what does an answer need?  I would say the following.

Pseudocode for an algorithm.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode actually solves the required problem.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode can be converted into a Turing machine with the appropriate resource bounds.

Even if you think the two proofs are obvious, it's a good idea to write a sentence or two about them. Trying to explain as briefly as possibly why something is correct can often find bugs such as the $aba$ problem.


Dynamic Programming - How to get the solution from the predecessor matrix

That depends a lot on the question, really. But basically, since you have the values of the all your "sub-problems", and you know your formula for the problem (Meaning, how the current problem is solved using the optimized solutions for the smaller problem), you can just check which cells (That are possible optimized solutions) in the matrix satisfy this formula.

Then, you can know that this cell is part of the solution.

Continue this way from top to bottom - and you'll get your whole solution (And not just the value, which is I guess was your problem).


NP-completeness for integer linear program

This is a classic facility location problem. That Wikipedia article suggests that NP-hardness can be proven by reduction from set cover.

Since the asker has now stated to have found a solution by reducing from vertex cover, I will go ahead and reveal the reduction from set cover:

   For each value, create a store; for each set, create a warehouse. Assign the cost of each warehouse to be 1. Assign the cost of the route from a warehouse to a store to be an arbitrarily small value if that warehouse's set contains that store's value, or an arbitrarily large value otherwise. Then the minimum cost solution to the facility problem builds precisely the set of warehouses corresponding to the minimum set cover in the original problem.

 The $k$ value is used to turn the optimization problem (minimize sets/cost) into a decision problem (is there a solution with no more than $k$ sets/cost?). The $k$ from the set cover instance will be the same as the $k$ in the facility problem instance if you are allowed to set the "arbitrarily small" values to exactly 0 - otherwise you might have to fudge the value by some amount, but less than 1 as long as you pick the "arbitrarily small" weights to be small enough. You just need the total of every "arbitrarily small" cost to be less than 1, and every "arbitrarily large" cost to be greater than the sum of the costs of all the warehouses and all the "arbitrarily small" routes.

 Note that, if only integer costs are allowed in the facilities problem, you can still achieve the same result by scaling all the costs by their least common multiple.


Slowdown in making nondeterministic Turing machines deterministic

If this were the case, then we would have P${}={}$NP, since then any polynomial-time NTM could be made into a polynomial-time DTM.
Your question is whether NTIME$(f(n))\subseteq{}$DTIME$(2f(n))$ for any function $f\colon\mathbb N\to\mathbb N$.  For $f\in\omega(n)$, one has DTIME$(2f(n))={}$DTIME$(f(n))$. So in this case, the question boils down to whether NTIME$(f(n))={}$DTIME$(f(n))$ or not. This question seems open.
What is known is that DTIME$(n)\subsetneq{}$NTIME$(n)$, see https://people.math.gatech.edu/~trotter/papers/34.pdf
It is also known that NTIME$(f(n))\subseteq{}$DTIME$(2^{O(f(n))})$, so you can simulate any NTM by a DTM with exponential slowdown.


virtual machine based programming languages vs low level

It is impossible for one language to be faster than another language, period.
A programming language is a set of abstract mathematical rules and restrictions. It is an idea. A piece of paper. You cannot run a language, therefore, you cannot measure its performance.
What you can do is run a particular piece of code written in one language using a particular version of a particular implementation of that language with a particular set of command line flags in a particular environment and compare its performance to a different piece of code written in a different language run with a different version of a different implementation configured with a different set of flags in a different environment.
But with all those differences, it will then be impossible to tell which of all of those differences actually caused the difference in performance. Was it the different benchmark programs? The different configuration options? The different versions? The different implementations? The different environments? Was the difference in performance caused by the language or by the quality of the implementations? Was it maybe caused by the difference in how much money was invested in optimizations?
I am willing to bet that for every set of environments and implementations that you can present me where language A is faster than language B, I can find a different set of environments and implementations where for the same two pieces of code, language B outperforms language A.
For example, there are Java implementations that are really fast. There are C++ implementations that are really slow. All I need to do is run my benchmarks using those two implementations, and I will have "proven" that Java is much faster than C++.
In the YARV Ruby VM, the Hash class is implemented in C. In the Rubinius Ruby VM, the Hash class is implemented in Ruby. Benchmarks that make heavy use of Hashes run faster on Rubinius than on YARV. Does that prove that Ruby is faster than C?


If $n$ is odd, no comparison involving elements of $S$ is performed outside of the for loop.
Moreover, each loop iteration performs exactly $3$ comparisons involving some element in $S$. The number of iterations is the minimum integer value of $k$ such that $2+2k > n$, i.e., $k=\left\lceil \frac{n-2}{2} \right\rceil = \frac{n-1}{2}$.
Therefore, the total number of comparisons involving some element in $S$ is $3 \cdot \frac{n-1}{2} = \frac{3n}{2}-\frac{3}{2}$.


Proving NP Completeness of a subset-sum problem - how?

The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable.  Using the 3SAT -> SUBSET SUM reduction from your lecture notes:

The $y$ values encode statements about which variables have positive literals in which clauses.  The $z$ values encode statements about which variables have negative literals in which clauses.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else.  The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula.  Note that the required sum $k$ has a one in each digit position corresponding to the variables.  This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both.  Note also that sum $k$ has a three in the digit position corresponding to each clause.  The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values.  All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.


Machine learning algorithm to play Connect Four

Just to offer a simpler alternative to reinforcement learning, you can use the basic minimax algorithm to search for good moves, and use machine learning to evaluate board positions.

To clarify, minimax builds a game tree where each node is labeled with the outcome from the leaves up (1=player A wins, 0=player B wins), assuming that A chooses the moves that maximize this number, and B chooses the moves that minimize it.

Unless the game is very simple, you won't be able to construct the whole game tree down to the terminals. You'll instead need to stop at unfinished board positions and evaluate the leaves with some heuristic (essentially the probability that player A will win from the given position). You can let a machine learning algorithm like a neural network try to learn this probability from connect four positions with known outcomes.

To generate training examples you could build your minimax player with a simple heuristic, let it play itself a thousand times, use those games to train your first neural network, then let that pay itself a thousand games and so on. With a little luck, your system will improve with each generation.


Search for maximum subsequence sum problem, here you will find a linear time solution. Bentley's "Programming Pearls" gives several alternative algorithms and some history. The linear time solution is obvious in hindsight, but it took several tries by experts to come up with it...


First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to the goal.

Now, when considering the sliding-tile puzzle, the Manhattan distance can be shown to be an admissible heuristic function as it results from a constraint relaxation [1].

From here, consider your first question: if the Manhattan distance is an admissible heuristic function for the sliding-tile puzzle where the cost of each movement is 1, it is also an admissible heuristic function for the case where the cost of each movement is strictly greater or equal than 1 (because all tiles are numbered 1 onwards).

Regarding your second question, a heuristic function $h_1(n)$ is said to dominate another heuristic function $h_2(n)$ if and only if $h_1(n)\geq h_2(n)$ for all states $n$. For some restrictive models (a unique goal, constant branching factor, no duplicates, etc.) it can be shown that more informed heuristics (i.e., $h_1(n)$ in the previous definition) expand less nodes when using A$^*$. From here, if you enhance your heuristic function with the average of all tiles, then it is necessarily more informed than pure Manhattan but watch out, it should be easy for you to note that this second heuristic function is not necessarily admissible as it can very easily overestimate the effort to reach the goal. Thus, using this second heuristic it is very likely that you will expand less nodes but you cannot guarantee that the solution returned is optimal.

Hope this helps,

Bibliography

[1] Pearl, Judea. Heuristics - Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, 1984.


Polynomial space complexity with exponential size witnesses

Hint: Use Savitch's theorem to show that PSPACE=NPSPACE.


Applying Machine learning in biological data

A simple starting point would be to apply a bag-of-words feature vector and try using a naive Bayes or logistic regression classifier.  You'll probably want to apply stemming and lemmatization and remove stop words.

Going based on this one example, determining which gene is regulated looks like it might be plausibly feasible, but determining whether it is up- or down-regulated might be pretty tough, especially given the limited training set you have.  Of course, it's hard to know without seeing more examples and without some domain knowledge in biology.

There are lots of techniques in the NLP literature, and probably your best bet is to start by reading up on standard NLP methods and start trying some of them, and see if that raises a more narrowly targeted question.  Machine learning often requires significant experimentation (try a bunch of things).  It's also helpful to know standard techniques so you can use your domain knowledge of these documents to help you brainstorm possible features.


The reverse DFA is not working as expected

Answering my own question based on the comment by Hendrik Jan:

The reverse DFA is correct. It is just that it is not deterministic. It's an NFA, so we should follow all the paths possible. And if we do so, it will accept all the strings starting with "10".

Example: assume we want to test this string: "10001". and assume that states are named 1, 2, and 3 from the right. By following this path, the NFA accepts the input string: "1,2,2,2,3,3"


Sampling a uniform distribution of fixed size strings containing no forbidden substrings

Suppose the alphabet is $\{a,b\}$, and you have one forbidden word, $aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over $ab,ba,bb$. Hence the first letter has the following distribution: $a$ with probability $1/3$, $b$ with probability $2/3$. In contrast, the allowable words are
$$
aba,abb,bab,bba,bbb.
$$
So the first letter should have the distribution $a$ with probability $2/5$, $b$ with probability $3/5$.

Here is an algorithm that does work. Construct a DFA (or UFA) for your language. For each state $q$, using dynamic programming you can count how many words of length $m$ are accepted when the automaton is started at $q$. Let us denote this by $c(q,m)$.

The correct distribution of the first letter $\sigma_1$ of a word of length $n$ in the language is
$$
\Pr[\sigma_1 = \sigma] = \frac{c(\delta(q_0,\sigma),n-1)}{c(q_0,n)}.
$$
More generally, given the first $\ell$ letters $\sigma_1 \ldots \sigma_\ell$, the following letter has the distribution
$$
\Pr[\sigma_{\ell+1} = \sigma \mid \sigma_1 \ldots \sigma_\ell] = \frac{c(\delta(q_0,\sigma_1\ldots\sigma_\ell\sigma),n-\ell-1)}{c(\delta(q_0,\sigma_1\ldots\sigma_\ell),n-\ell)}.
$$
Ignoring the cost of arithmetic, you can implement this scheme in roughly $O(|Q|n)$, where $Q$ is the set of states, or in $O(|\Sigma|n^2)$. (The former, assuming that $|Q| = \Omega(|\Sigma|)$.)

As an example, let us consider the counterexample above. We construct a DFA containing two states (we can omit the sink state, obtaining a UFA) $q_0,q_1$. The transition function is $\delta(q_0,a) = q_1$, $\delta(q_0,b) = q_0$, $\delta(q_1,b) = q_0$. The relevant values of $c$ are
$$
\begin{array}{c|cc}
n & c(q_0,n) & c(q_1,n) \\\hline
0 & 1 & 1 \\
1 & 2 & 1 \\
2 & 3 & 2 \\
3 & 5 & 3
\end{array}
$$
These are computed by the recurrences $c(q_0,n) = c(q_0,n-1) + c(q_1,n-1)$ and $c(q_1,n) = c(q_0,n-1)$, with base case $c(q,0) = 1$.

Since $\delta(q_0,a) = q_1$ and $\delta(q_0,b) = q_0$, we see that (for $n = 3$) $\Pr[\sigma_1 = a] = c(q_1,2)/c(q_0,3) = 2/5$ and $\Pr[\sigma_1 = b] = c(q_0,2)/c(q_0,3) = 3/5$.


Can $\emptyset$ be reducible to any other language?

$\emptyset$ can be reduced to any other language $L$ except $\Sigma^*$.

Remember that a reduction from $L_1$ to $L_2$ has to map "yes" instances of $L_1$ to "yes" instances of $L_2$ and "no" instances of $L_1$ to "no" instances of $L_2$.  Every input is a "no" instance of the language $\emptyset$ so, to reduce $\emptyset$ to any $L\neq \Sigma^*$, you just need to choose some word $w\notin L$ and your reduction maps everything to $w$.  Obviously, for $L=\Sigma^*$, this doesn't work because there's no $w$ you could use.

Similarly, $\Sigma^*$ can be reduced to any other language except $\emptyset$.


For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$

Let $B=A'$, the Turing jump of $A$. This is a basic result in the theory of the Turing degrees.


The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

The language
$$L_1 = \{(x,u) ~|~ \exists v\in \{0,1\}^{d|x|^8}M(x,u,v) = 0\}$$ belongs to $NTIME(n)$ by design, since $|v| = O(|x| + |u|) = O(|x|^{8})$. By the assumption of the theorem, $L_1$ is decidable by some deterministic $D$ in $O((|x|+|u|)^{1.2}) = O(|x|^{9.6})$ steps. The recipee for $D$ isn't important, but the existence of such algorithm $D$ leads to the last step of the proof.


It is still $\sf{NP}$-complete, even for $k=2$. Given an instance of subset sum, we can transform it in to this variant by splitting up the numbers and adding some extra bits.

First, the sum of all numbers in the problem will be less than $2^m$ for some value of $m$.

Now, let's take a number $n$ from the original problem which has $k$ bits set. We will split this number in to $k$ numbers with exactly 2 bits set such that the sum of those numbers is $n+2^{k+m}$. We can do this recursively, by finding $\lceil{k}\rceil$ numbers that sum up to the first $\lceil{k}\rceil$ bits plus $2^{k+m-1}$ and $\lfloor{k}\rfloor$ numbers that sum up to the last $\lfloor{k}\rfloor$ bits plus $2^{k+m-1}$.

In addition to that number we will also add the number $2^{k+m}$ to the problem. A solution must either contain this number or all of the $k$ numbers constructed previously. If the original target value was $t$ the new target value will be $t+2^{k+m}$.

If the original problem had more than one number, we can repeat this process taking $k+m+1$ for the new value of $m$.

There are only two ways the bit at position $k+m$ can be set: the answer can contain the number $2^{k+m}$ or all of the $k$ numbers that sum up to $n+2^{k+m}$. So we have reduced subset sum to your subset sum variant.

As an example, let's take ${\{2,3,5\}}$ with target value $7$. This problem could be encoded as the subset sum variant presented here by taking the following binary numbers:

2 gets mapped to $0100\ 1$ and $0000\ 1$. (Using the extra bit is not strictly necessary here.)

3 gets mapped to $1000\ 00\ 1, 0100\ 00\ 1$ and $0000\ 00\ 01$

5 gets mapped to $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ and $0000\ 00\ 000\ 01$.

The new target value would become $1110\ 10\ 010\ 01$.

If the original problem is represented with $n$ bits, then the transformed problem has at most $O(n^4)$ bits. The original problem will have at most $O(n)$ numbers each with at most $O(n)$ bits, so the sum of all of them is also O(n). The transformed problem will have $O(n^2)$ numbers (since each $n$-bit number is split in to $n+1$ $2$-bit numbers, with their length being at most $O(n^2)$ since we use $n$ additional bits for each number. So the total size of the transformed problem is $O(n^4)$ bits.


Using a computer algebra system to optimize mathematical expressions

This doesn't completely answer your question, but you ask if research has been done on this.

This is an area called Symbolic Algebra. I'm sure there are many such research groups, but here is one:

https://www.scg.uwaterloo.ca/

They're the group at Waterloo which developed the Maple software (similar to Mathematica).


SICP: applicative or normal order evaluation

This is how I understand it:
; Normal
(test 0 (p))
(if (= 0 0) 0 (p)))

Normal order continues expanding because it hasn't yet reached an expression with only primitives, which recurses into an infinite loop replacing (p) by (p).
; Applicative
(test 0 (p))
(if (= x 0) 0 y))
(if (= 0 0) 0 y))

Applicative order applies the procedure (the if predicate) to the arguments that are the values of its sub-expressions. Because if short-circuits, the expression reduces to #t before before evaluating sub-expression y.


This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$.

This problem is a special case of $X+Y$ sorting. According to Wikipedia, no algorithm whose complexity is better than $O(n^2\log n)$ is known for this problem. The decision tree complexity, however, is only $O(n^2)$. (That is, there is an algorithm which asks at most $O(n^2)$ decisions and outputs the sorted $X+Y$; deciding which question to ask could be difficult.)

Your version (with $X=Y$) is no easier than the general case. Indeed, suppose that $X,Y$ are integer arrays. Let $Z = \{ 4x+1 : x \in X \} \cup \{ 4y+2 : y \in Y \}$. Given the sorted version of $Z+Z$, it is easy to extract $X+Y$ by taking all elements of the form $4m+3$ and extracting $m$.

The $X+Y$ problem is 3SUM-hard. However, this doesn't shed much light on the problem since 3SUM itself can be solved in $O(n^2)$ (and even faster), while the $X+Y$ problem plainly requires $\Omega(n^2)$.


SAT algorithm for determining if a graph is disjoint

Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected.

Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_v$ for $v \in V$:

$x_{v_0}$.
For every $(u,v) \in E$, $\lnot x_u \lor x_v$ and $\lnot x_v \lor x_u$.
$\bigvee_{v \neq v_0} \lnot x_v$.

Here is a SAT instance which is satisfiable iff the graph is connected.

Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_{v,i}$ for $v \in V$ and $i \in \{0,\ldots,n-1\}$:

$\lnot x_{v,0}$ for all $v \neq v_0$.
For every vertex $v \in V$ and $i \in \{0,\ldots,n-2\}$, $\lnot x_{v,i+1} \lor x_{v,i} \lor \bigvee_{u\colon (u,v) \in E} x_{u,i}$.
For every vertex $v \in V$, $x_{v,n-1}$.


Dynamic Programming for a variant of the coin exchange problem

Add a parity parameter to $C$ and check for it in the base case, making the wrong parity invalid:

$$
\newcommand{\for}{\text{for }}
C(S, m, n, p) =
    \begin{cases}
      0& \for n < 0\\
      0& \for n = 0 \wedge p = 1\\
      1& \for n = 0 \wedge p = 0\\
      0& \for m = 0\\
      C(S,m-1,n,p) + C(S, m,n-S_m, 1-p)& \text{otherwise}
    \end{cases}
$$

Note that I'm using mathematical notation above so $S$ and $m$ are using one-based indices.

Since we want only an even number of summands we want $p = 0$, thus $C(S, m, n, 0)$ gives the answer you want.


Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix

Yes.  You can.  You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$.

Small simplifications.
Note that $d$ is unnecessary.  $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$).  So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$.  Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$.  Finally, I will assume you are looking for integer values of $a,b,c,e$, with no limit on how large or small they are.

Finding a $f$.
Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$.  There are several cases, according to which relational operator $f$ uses:

Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns.  For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns.  You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations.  Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.

In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.
Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$.  Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$.  Form a system of inequalities obtained by all the points in $S$.  Solving this then gives us a valid combination of values for $a,b,c,e$.  There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.

You can improve this to check whether there exists a single linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution.  If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done.  If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:

Introduce unknowns $x_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x_{i,j,k} \le 1$.  Add constraints $ai+bj+ck+e \ge x_{i,j,k}$ for each $(i,j,k) \in S'$.  Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum_{(i,j,k) \in S'} x_{i,j,k}$.  This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.

If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.
Less than: For $f$ of the form $ai+bj+ck+e < 0$, we can adjust the above approach by using linear inequalities of the form $ai+bj+ck+e < 0$ (or $ai+bj+ck+e \le -1$ if we require $a,b,c,e$ to be integers) and carrying on as before.
Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.

Finding $F$.
So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$.  But how do we find a full $F$?

I don't know of any efficient way to find the optimal $F$.  However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.

In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$.  Define $T = \{(i,j,k) \notin S : F(i,j,k)=\text{True}\}$.  Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.

Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible?  Well, I've already described how.  For each relational operator $\bowtie \in \{=,\ne,<,>\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible.  This gives you four candidates for $f$.  For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.

In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.


Find k compatible objects with minimum total penalty

Well, the graph is obvious, isn't it? Independent set


Find set of non-overlapping rectangles in a 2D grid

The problem you state is shown to be NP-Hard [1, 2]. However, there is an $O(\log \log n)$ approximation algorithm for the problem [3].

[1] H. Imai, T. Asano. Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms 4(4): 310-323, 1983.

[2] R.J. Fowler, M.S. Paterson and S.L. Tanimoto, Optimal packing and covering in the plane are NPcomplete. Information Processing Letter. 12 3 (1981), pp. 133137.

[3] Parinya Chalermsook, Julia Chuzhoy: Maximum independent set of rectangles. SODA 2009: 892-901


Determine the number of reachable states in a subset construction?

Start with a 3SAT instance $\phi$ on $n$ variables with $m$ clauses $C_1,\ldots,C_m$. For each clause $C_j$, we construct an NFA $A_j$ which reads a binary input string, interpreting its first $n$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $C_j$ is satisfied, then on the $(n+1)$'th symbol it branches to $n$ new states.
Now consider an NFA consisting of the NFAs $A_1,\ldots,A_m$ together with an initial state with $\epsilon$-transitions to the starting states of $A_1,\ldots,A_m$ (alternatively, if you allow multiple initial states, you can just put all of them together). If $\phi$ is satisfiable then the number of reachable states in the corresponding DFA will be at least $n^m$, otherwise it will be at most $n^{m-1} + 2^m n + 1$.


Confusion related to time complexity of fast fourier transform

If you compute by recursion each unit root at a time, it will indeed be costly. However, observe that when you compute $A_{even}(\omega_{n/2}^i)$ and $A_{odd}(\omega_{n/2}^i)$, you actually gain two values for $A$. For $i< n/2$ we have that:

$A(\omega^i_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^i\cdot A_{odd}(\omega_{n/2}^i)$

$A(\omega^{i+n/2}_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^{i+n/2}\cdot A_{odd}(\omega_{n/2}^i)$

This ability to compute two values using a single computation of $A_{even}$ and $A_{odd}$ allows for the divide and conquer approach to reduce the time to $O(n\log n)$.


Can a CPU be replaced without interrupting the processes running on it?

On a multitasking operating system, any process can be paused while other processes are executing. When a process is paused, all of its data is in RAM, outside the CPU. The CPU itself only contains a small amount of data in registers.

On a multiprocessor system, this same mechanism also allows processes (or more precisely threads) to migrate from one processor to another. As long as the processors are connected to the same RAM, a processor switch is no more complicated than a context switch.

The operating system kernel can save the few pieces of data that it normally stores in registers to a fixed place in RAM, and can make its startup code read this data back. All major multiprocessing operating systems can in fact do that: it's called suspend to RAM.

What prevents replacing the CPU during a suspend-to-RAM is not a difficulty with software architecture, but with hardware architecture. It is possible on some expensive servers, but not on a consumer device.

You can actually replace your CPU and restart with your old processes, even on a computer where this requires turning off the power, by using suspend-to-disk. Take all the data in RAM and save it to disk. This is similar to swapping. The kernel needs to do more work, because it has to power down all peripherals and restore their state afterwards. But again there is no extra theoretical difficulty, just a lot of practical difficulties in writing drivers.


For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time?

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

If $f$ is a time-constructible function, then the Time Hierarchy Theorem says that there are problems that require $O(f(n))$ time, and cannot be solved with time $o\left (\frac{f(n)}{\log(f(n))}\right )$. Specifically,
$$ \text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$$

This consider only decision problems, and does not regard the time it takes to generate the output.


Building a huffman tree is bottom up.

You start with the all the leave nodes with their frequency.
Then you select and remove the 2 nodes with the smallest frequencies
create and insert a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes
if set has 2 or more nodes repeat from step 2

Selecting the 2 nodes with the least frequencies requires a min heap.


Number of edges required to guarantee $K_3$ as subgraph

Hint: Matrix multiplication runs in time $O(n^{2.71})$. A relevant matrix is the adjacency matrix of the graph.

Actually, this has been improved several times in the past very. Recently, Le Gall improved this to time $O(n^{2.3728639})$. It is conjectured that matrix multiplication runs in time $O(n^{2+\epsilon})$ for every $\epsilon > 0$.


$\newcommand{\maxsnp}{\mathsf{Max}\text{-}\mathsf{SNP}}$The definition of $\maxsnp$ gives us the ability to define:

Universal ($\forall$) and existential ($\exists$) quantifiers over variables
Existential quantifiers over relations

With this definition we can define $\mathsf{Max}$-$\mathsf{SAT}$:

$$\exists x, \forall y \text{ such that } |\psi(y)| \leq |\psi(x)|$$ where $|\psi(x)|$ is the number of clauses satisfied in formula $\psi$ under assignment $x$.

Given that $\mathsf{Max}$-$\mathsf{SAT}$ is $\mathsf{NP}$-$\mathsf{Hard}$, we see that $\mathsf{NP}$-$\mathsf{Hardness}$ is implied from $\maxsnp$.


Radon transform for advanced 3d graphics and games?

I've been studying the use of OpenGL and DirectX and even though I am at an intermediate level, I believe this is where the use of bump maps, light maps etc comes into play. These are encapsulated in the idea of a Shader. The hardest part about the shader and lighting to work correctly with the 3D object with respect to the angle of the camera view directly depends if your normals are defined correctly. As for what you are describing it does make sense using 3D approximation, however my linear algebra is a little rusty, I am not sure if the conventional 4x4 matrices will work, and when it comes to motion with rotations you might have to redefine your quaternions too.


What is the purpose of Bayesian networks?

I am trying to state a possible bayes net:
What the creature wants to know is what to do next. So the root node is 'ACTION'. Possible actions are (let's say field 1 = home): [move to field 1, move to field 2, ... move to field n, sleep, eat] or [go north, go south, go east, go west, eat, sleep]. 'ACTION' depends on the creature's 'STATE', that can be [afraid(by another creature), under attack, hungry, tired]. 'STATE' depends on 'ANOTHER CREATURE' and 'FOOD AVAILABLE'. The latter two nodes can be [yes,no] and both depend on the current 'FIELD', [field 1, ..., field n].

'FIELD' -> 'ANOTHER CREATURE'

'FIELD' -> 'FOOD AVAILABLE'

'ANOTHER CRATURE' -> 'STATE'

'FOOD AVAILABLE' -> 'STATE'

'FIELD' -> 'ACTION'

'STATE' -> 'ACTION'

Each node has a table containing the probabilities p(value|value of dependency1, value dependency2,...). For example the 'ACTION' table holds the probabilities for each combination of p(action to take | value of 'STATE', value of 'FIELD').

I think suitable methods to estimate the model's probabilities are Q-learning or SARSA-learning.


What are some applications of binary finite fields in CS?

Finite fields come up in many places. Here are just a few examples:

The Razborov-Smolensky polynomial method.
Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication.
List decoding - codes like Reed-Muller are algebraic codes.
Algebraization, the method used to prove IP=PSPACE.
Elliptic curves over finite fields are used in cryptography.


Question about H-gate on entangled qubits

Assuming that the initial quantum state is $\left| 00 \right\rangle$, the effect of the circuit is
$$
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix} \cdot
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} =
\begin{bmatrix} 1/2\\1/2\\1/2\\-1/2 \end{bmatrix},
$$
where the rows and columns are indexed by $\left|q_0q_1\right\rangle = \left|00\right\rangle,\left|01\right\rangle,\left|10\right\rangle,\left|11\right\rangle$. When you measure the two qubits at the end, you should get each of the four possibilities with probability $(\pm 1/2)^2 = 1/4$, which is exactly what you have observed.

If, however, you apply the CNOT gate with input roles reversed, you get
$$
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix} \cdot
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} =
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix},
$$
so in this case you will always measure $\left|00\right\rangle$.


Lets refactor and reword these statements for ease of thought.

Let $A(n)$ be $Θ(g(n))$.

Let $B(n)$ be $O(g(n))$.

  Note that $A$ implies $B$ because $A$ is stronger than $B$.

This means for $A$ to be fulfilled we have to fulfill the criteria of $B$ and more. Therefore $A$ being fulfilled implies $B$ must also be.

  Written set theoretically, we have the set of functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$.

Well this is not contradictory, but actually equivalent in a sense to the last statement which showed that $A$ has the criteria of $B$ and more.

From our understanding of this point we can determine that: All the functions that fulfill the criteria of $A$ fulfill $B$, but not all functions that fulfill the criteria of $B$ fulfill the criteria of $A$.

This is really an equivalent statement to: The functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$ because the second set contains the first.

And therefore $\Theta(g(n))\subseteq O (g(n))$ is true, and it is equally true that $f(n) = \Theta(g(n))$ implies $f(n) = O(g(n))$ without any contradiction.

Furthermore this makes sense with the definition for $\Theta(g(n))$ which states that:
$f(n)\in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Clearly by this definition, $f(n) \in Θ(g(n))$ does imply $f(n) \in O(g(n))$, and $\Theta(g(n))$ is clearly a subset of $O(g(n))$ as well.


How exactly the "load word" instruction loads from RAM?

Responding only to your UPDATE: MIPS always had load/store byte.  The original models may not have allowed unaligned word accesses.  Load byte is (relatively) easy on a 32-bit bus.  For example, you could fetch the entire word from memory (by setting the bottom 2 address bits to "0") and then add a little circuit so that when the word reaches the processor you use the bottom 2 address bits to shift and mask the correct byte into the destination register.

Store byte is somewhat more complicated.  At the beginning of the store-byte operation the processor shifts the byte into the desired position in the 32 bit word, and then sends the entire 32-bit word along with the entire address (including the 2 low-order bits) to the cache.  The cache uses the 2 low-order bits to control which bytes do and do-not get written.  (The cache has such control (at the word level) anyway, since typically the SRAM array is something like 256x256 bits (= 8Kbytes) or 512x512 bits (= 32Kbytes).)

The only recent architecture I can think of that didn't include load/store byte instructions was the DEC Alpha 21064 (released 1992).  Instead they added a lot of special bit shift-and-mask operations to extract bytes from words.  If you needed to store a byte on the 21064, I think you may have had to load the word that contained the byte, shifted and masked in the byte that you wanted to write, and then write back the entire word.

They added load/store byte instructions in the 21164A (released 1996) because the extra instructions to do all that extra work in software were making the instruction cache less effective than it should have been for programs with a lot of byte operations.


Why is software emulation of alternative architectures so hard/slow?

If the underlying machine is similar to the simulated one, you can run most code natively (no speed loss unless there are hard to handle instructions or other characteristics, this is the "virtualization" business). If it is very different, you have to really simulate each instruction (for a cost of half a dozen or so native instructions for a typical machine). If it is important enough, you can use tricks like JIT compilation to native code to speed it up.


Monte-Carlo Algorithm for counting 'on' bits in a binary array

This is a standard technique. Run the algorithm multiple times and take the median answer. The median will be a success unless there are many failures; use a Chernoff bound to show that this many failures has the low probability you require. Typically, a constant number of runs will give a constant (but better than $1/2$) failure probability, poly-log runs will give polynomially small failure probability and a polynomial number of runs will give exponentially small failure probability.


Are there any type constructors which are *not* functors?

One obvious counterexample is a binary search tree. You cannot freely substitute the values in a binary search tree because a substitution might change the ordering (relative to Ord), or even replace the values with a type which is not an instance of Ord at all.

A possibly less-obvious example is a contravariant endofunctor. Consider:

data Tricky a = Tricky (a -> String)

Try writing a Functor instance for this.

But that doesn't mean you can't construct a functor-like class which it the type does satisfy. This Tricky type, after all, is a contravariant functor:

-- Somebody has probably already implemented this in a library
-- somewhere, with a better name.
class ContraFunctor f :: * -> * where
    contramap :: (b -> a) -> (f a -> f b)

instance ContraFunctor Tricky where
    contramap f (Tricky t) = Tricky (t . f)

and like fmap, it must satisfy some axioms which are left as an exercise.

What's interesting, though, is that you can usually come up with a functor-like class (and its axioms, of course) which applies type substitutions in a principled way, from the types of the functions which comprise their API.

The full details are beyond the scope, but it's based on a remarkable property of a polymorphic function is known as the "free theorem". Any polymorphic function has a theorem that it satisfies simply by virtue of being polymorphic, and the theorem is mechanically derivable from its type.

What the theorem essentially states is that a polymorphic function commutes with a type substitution. This is what "polymorphic" really means.

Let's take reverse as an example:

reverse :: forall a. [a] -> [a]

There are no constraints whatsoever on the type of a, so it will commute with any type substition:

forall f :: A -> B. fmap f . reverse = reverse . fmap f

(Remember, . is function composition in Haskell.)

This is true for any types A and B. In a deep sense, this is what the "forall" actually means in the type of reverse.

Now consider sort:

sort :: forall a. Ord a => [a] -> [a]

The problem here is that Ord is a constraint on the type of a. What this means is that this is a constraint on any type substitution: it must be a homomorphism of Ord.

forall f :: A -> B.
    (forall x y : A, compare x y = compare (f x) (f y))
    => fmap f . sort = sort . fmap f

That extra precondition, that f is an Ord-homomorphism, intuitively means that f is a function which preserves the order. This should make sense: if a type substitution doesn't change the ordering of elements, then that type substitution commutes with sort.

But here's my favourite example of all. Suppose that F and G are functors. Now consider this function:

eta :: forall a. F a -> G a

The free theorem of this function is:

forall f : A -> B.  fmap f . eta = eta . fmap f

Note that the two fmaps are different instances; the first one is the instance for G and the second is the instance for F. What this is saying is that eta, by virtue of its type alone, is a natural transformation.


Is the empty problem (or its complement) Karp reducible to any problem in NP?

Of course there is.

Just take any non-trivial language $L$ (i.e., $L \neq \varnothing$ and $L \neq \Sigma^\ast$). Then there are concrete words $x \in L$ and $y \not\in L$.

To reduce $\varnothing$ to $L$, simply map everything to $y$. Then the input is in $\varnothing$ (which is false) if and only if $y \in L$ (which is also false). Hence, the reduction is correct.

For $\Sigma^\ast$, do the same but use $x$ instead.

As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $\textbf{P} = \textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $\varnothing$ or $\Sigma^\ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).


How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?

The $\log$ function is concave so, by Jensen's inequality,
$$\frac{1}{k}\sum_{i=1}^k\log m_i \leq \log\Big(\frac1k\sum_{i=1}^k m_i\Big)$$
i.e.,
$$\sum_{i=1}^k \log m_i \leq k\log\frac{m}{k} = k\,(\log m - \log k)\,,$$
which is basically what you got by bounding $\log m_i\leq \log m$.  We can't do any better than this because we could have $m_1 = \dots = k_m = \tfrac{m}{k}$, in which case $\sum_i\log m_i = k\log\tfrac{m}{k}$.

However, if $k$ is a fixed constant, then $k\log\tfrac{m}{k}=O(\log m)$.


A year after and I'm writing one myself.


Using decision oracle to solve optimization problem of maximum polyomino tiling

Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.

A gangly polyomino in a double-width problem instance

Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \times (b+1)$ in which each polyomino's width has been doubled, and a new polyomino has been added that consists of a row of $2a+1$ blocks with a column of $b$ blocks hanging below its leftmost block (thus giving it a total height of $b+1$) and a double-width copy of polyomino $p_1$ (the template polyomino) below the top row and to the right of the left column but pushed up and left as far as it will go, so that at least one block of column 2 below row 1 is occupied, and at least one block of row 2 to the right of column 1 is occupied. Intuitively, because all other polyominos have even width, the only way to fill up the odd-width rectangle we have is to use this gangly new polyomino, in which case its horizontal and vertical "arms" must form the topmost row and leftmost column, respectively.

Let the size of an optimal solution to the original problem be $k$ (this can be found in $O(\log {ab})$ time with binary search using only decision problem oracle calls). Iff there is a solution to the newly constructed decision problem instance with size $2k+(2a+1)+(b+1) = 2(k+a)+b+2$, then there is a solution to the original instance that has $p_1$ in its top-left corner.

If the answer is "no", try the same instance again but with a different template polyomino: form the gangly polyomino by pressing $p_2$ into the top-left corner instead of $p_1$. Repeat this until you find you hit a "yes" instance. If none of the polyominos results in a "yes" instance when pressed into the top-left corner, start again with $p_1$ but one block down from where it was in the first constructed problem, and with the blocks at positions $(2, 2)$ and $(2, 3)$ also filled in. Why? These represents a (double-width) block that we know must remain empty in every optimal solution (since if there was some optimal solution where it was covered by a polyomino, we would have found it by now). Add 2 to the target value for the decision problem to compensate for the added filler blocks.

If performing this down-one-row move would cause the polyomino to extend past the bottom of the range, add the 2 filler blocks as usual but instead move the template polyomino back up to the top (so that its topmost block occupies row 2) and as far left as possible so as to not overlap any existing block.

In general, a constructed instance with $f$ filler blocks gets $f$ added to its decision problem target.

Once you hit a "yes" instance, you know that this placement of the template polyomino is part of some optimal solution, so you keep that placement of the template in the gangly polyomino from that point on. Form the next problem with the next available polyomino as template immediately below the last one, or flush with the top and to the right as usual.

Time complexity

Each time we try all $n$ polyominos at some position, we add at least 2 blocks (either 2 filler blocks, or the double-width blocks corresponding to some input polyomino) to the gangly polyomino. We can only add at most $ab$ such pairs of blocks before it is no longer possible to obtain a "yes" answer, so at most $abn$ calls to the decision oracle suffice.


The function $\log(n^n) = n\log n$ grows much faster than $\log n$, so we can conclusively say that $\log(n^n) = \omega(\log n)$. It even grows much faster than $n$, so $\log(n^n) = \omega(n)$.

You say that whether $\log(n^n) = \Theta(\log n)$ (where perhaps you mean $\Theta(n)$ instead of $\Theta(\log n)$) is "inconclusive", since for small $n$ there is one behavior, and for large $n$ there is another. For asymptotic analysis we care only about the behavior for large $n$.


Relationship between Las Vegas algorithms and deterministic algorithms

There is no contradiction here. A Las Vegas algorithm terminates in expected polynomial time, say $Q(n)$. Markov's inequality shows that for any given polynomial $R(n)$, it terminates in polynomial time $Q(n)R(n)$ with probability $1-1/R(n)$. The number of graphs on $n$ vertices, $k(n)$, is exponential in $n$, so the failure probability $1/R(n)$ is much larger than $1/k(n)$.

Another subtle point is uniformity. A deterministic algorithm needs to handle any input size, while your $A^\rho$ can only handle inputs of certain size. In general, a randomized algorithm can use an unbounded number of random bits. However, your argument can still be formulated in terms of non-uniform models such as circuits, and it is still wrong for the reason described above.


Prove that the language is not regular without using Pumping Lemma

1) your proof is correct (and nice).

2)They could mean prove that the complement is not regular (this is a classic result, and the proof is simpler). More generally, if you saw in course some languages that are not regular, you can probably reduce one of them to this one by closure operations.

Another technique without pumping lemma is to show that the number of Myhill-Nerode equivalence classes is infinite.


Regular Expression for the language that requires one symbol to occur at least once

The simplest regular expression I can think of for this is $\left(a \mid b \mid c\right)^* a \left(a \mid b \mid c\right)^*$. This is simpler than yours by the following measures of complexity:

It contains less nesting (and fewer parentheses in general)
It contains fewer quantifiers


Min-cut in a network with zero flow from source to sink

No, your gut feeling is not correct.

Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\{s,A\}, \{B,t\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side.

$$ s \longrightarrow A \longleftarrow B \longrightarrow t$$

You could learn several lessons from this simple problem.  One is that source and sink are symmetric in some strong sense. It looks like your gut feeling does not respect this symmetry. Another lesson is that a few simple examples should be included in your repository. Always try constructing some simple or extreme examples when you want to check a proposition of unknown truth value.


Is there an analog of "regular" for infinite strings?

Probably the most specific term to describe your first string, $010101\dots$ is periodic. A string $x_1x_2\dots$ (finite or infinite) is periodic if there is some $t$ such that, for all $i$, $x_i=x_{i+t}$. In the case of this example, we can take $t=2$. A slightly weaker notion is that a string is eventually periodic if there are $n$ and $t$ such that $x_i=x_{i+t}$ for all $i\geq n$.

More generally, though, there is a direct analogue of the regular languages, which is the $\omega$-regular languages. These are recognized by natural generalizations of finite automata. The state set is still finite but the acceptance criterion must be modified to deal with infinite words – in particular, we can't just say "Accept if the automaton finishes in an accepting state" because the automaton never finishes processing its infinite input.

The simplest class of automata for infinite words are Büchi automata. They are defined exactly like the finite automata you're used to, and they accept their input if at least one accepting state is visited infinitely often during the automaton's run. One difference from ordinary finite automata is that it turns out that nondeterministic Büchi automata are more powerful than deterministic ones, and the $\omega$-regular languages are the ones accepted by nondeterministic Büchi automata.  Other sensible acceptance criteria lead to other automaton models which accept the same class of langauges.

Note that it doesn't quite make sense to write $xy^\omega z$, since you can't have anything after an infinite sequence of $y$s. At least, you can't if the positions in your string are indexed by the natural numbers. If they're indexed by larger ordinals this can make sense.

I can't actually remember if there's an analogue of the pumping lemma for $\omega$-regular languages. This is slightly embarrassing, though it is most of a decade since I taught a graduate class on this stuff.


What are the units for time complexity graphs?

We use Big-O notation to describe how "fast" an algorithm runs with respect to the size of the input in the worst case scenario. This input can be a number, a list of numbers, a matrix, etc. By fast, it essentially translates to number of steps the algorithm takes based on the size of the input in the worst case scenario.
I should start by describing the difference between an algorithm and an implementation of an algorithm. An algorithm is just a set of instructions that solves a problem. An implementation of an algorithm is code that is run on hardware that actually performs the set of instructions.
Suppose we have a simple problem, "given a list of numbers of arbitrary size and in no particular order, find the maximum value in the list". We solve this problem with an algorithm. Below is a solution to the problem.
FindMax(ls)
   m <- null
   for each x in ls
      if x > m
         m <- x

   return m

To analyze how good this solution is, we to find what the worst case is for this algorithm to handle. For this algorithm, the worst case would be a sorted list in ascending order. This is because the if statement will always be true (adding more steps).
Let $n$ be the size of the input list. Now let's count the number of steps our algorithm takes to complete (in the worst case). The initialization is 1 step (m <- null). The for loop will loop $n$ times. The amount it does inside the loop will be 2 steps (1for the if statement check and 1 for its body). Finally, 1 step for return m.
Let $T(n)$ be the worst case runtime for our algorithm. From above we have $T(n) = 1 + 2*n + 1 = 2*n + 2$.
This is where big-O notation will help us. We need to find a function $g(n)$ grows at a similar rate as $T(n)$; this function will be our upper bound. In other words, we need to find a function $g(n)$ where $T(n) \leq k*g(n)$ for all $n \geq n_0$.
Let's try $g(n) = 1$. Here we see that no matter what $k$ we try, $T(n)$ will always be greater at some point; more precisely, when $n>k$ then $T(n) > k*g(n)$. This means $g(n) 1$ is not big enough.
Let's try $g(n) = n$. Here we see that if we choose $k \geq 3$ and $n_0 = 1$, $k*g(n) \geq T(n)$ for $n \geq n_0.
What we proven is that $T(n)$ is bounded above by $g(n) = n$. This means that $T(n) \in O(g(n))$; in other words $T(n) \in O(n)$. Notice how I used $\in$ instead of $=$. This is because $O(g(n))$ is the set of all functions that are bounded above by $g(n)$. However, it is common practice to abuse the notation $T(n) = O(n)$.
The purpose of this example is to show you the context of big-O notation. Big-O notation is purely abstract in that we count the number of steps of the algorithm, not the amount of time (in seconds) it takes to complete. If we implement this algorithm in a program language (like C/C++ or Java) and run it on the computer, then we have many more factors to consider:

Number of cores of CPU
Clock speed of CPU
Amount of memory
I/O speed of the input
Language specific performance issues (e.g. C/C++ faster than Java)
etc.

None of these factors describes how well an algorithm performs; rather they show how well the implementation performs. See Big O Notation for an example and more information.


Determine the move in which a LOGO turtle crosses a point that it has already visited

Hint: Find some constant $C$ such that if the turtle ever crosses its own path, then it must hit one of the last $C$ segments in the path. (I think that $C=5$ should work.)


How can the union of two 'context-free but not regular' languages be regular?

Let $L$ be a context-free but not regular language over $\{0,1\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^*$ is regular.

In particular, let $L=\{a^nb^n\mid n\in\Bbb N\}$.

The previous example requires you to verify that both $L$ and $\overline L$ are context-free. Here is an example with less burden.

Let $\Sigma=\{a,b,c,d\}$. Let $F_1$ be a context-free but not regular language over $\{a,b\}$. Let $F_2$ be a context-free but not regular language over $\{c,d\}$.
Then both
$F_1\cup\{c,d\}^*$ and $\{a,b\}^*\cup F_2$ are context-free but not regular. The union of them,  $\{a,b\}^*\cup\{c,d\}^*$ is regular.

In particular, Let $F_1=\{a^nb^n\mid n\in\Bbb N\}$ and $F_2=\{c^nd^n\mid n\in\Bbb N\}$.

Exercise 1. If $R$ is a regular language and $F$ is context-free but not regular such that $R\setminus F$ is context-free, then $F\cup (R\setminus F)$ is a desired example. Show that we can take $R=a^*b^*$ and $F=\{a^nb^n\mid n\in\Bbb N\}$.

Exercise 2. If $L_1$ and $L_2$ are 'context-sensitive but not context-free' languages, defined over the same alphabet $Σ$ then, the union $L_1\cup L_2$ can be a context-free language. In fact, the union $L_1\cup L_2$ can be a regular language as well.


Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

First let's consider the case when numbers are unique. The idea is that for each element $w_t$ we count the number of elements in the sequence which are less than $w_t$. After each loop on all elements of the sequence we check if there are $i-1$ elements less than $w_t$ then $w_t$ must be $i$-th element in the sorted sequence, so we halt with the output equal to $w_t$.

proc(w, k, i)
 for t=0 to k
   counter = 0
   for j=0 to k
     if w[t] > w[j]
      counter = counter + 1
   if counter == i-1 then output w[t] and halt
end-proc

Now, if numbers are not unique then we have to count duplicates as well

proc(w, k, i)
 for t=0 to k
   counter = 0
   dups = 0
   for j=0 to k
    skip if j == t
    if w[t] == w[j]
      dups = dups + 1
   for j=0 to k
     if w[t] > w[j]
       counter = counter + 1
   if counter+1 <= i AND i <= counter + dups+1
     then output w[t] and halt
end-proc

  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
  \__________  __________/     \_____  ____/
             \/                      \/
 all elements less than w[t]   duplicates

Both procedures require only constant number of variables i, j, k, counter, and dups whose lengths are $O(\log(k))$. Your solution is similar to these algorithms so your approach is correct.


Coin Change Problem Recurrence Relation with one parameter

One possible definition is
$$
C(N) = \sum_{i \in S_m} C(N-i),
$$
with base cases $C(0) = 1$ and $C(x) = 0$ for negative $x$. This counts the number of ways to write $N$ as a sum of elements of $S_m$ where order matters, that is, if $a \neq b$ then $a + b$ is different from $b + a$. As an example, if $S_m = \{1,2\}$ then $C(3) = 3$ since $3 = 1 + 1 + 1 = 1 + 2 = 2 + 1$.

It is, however, possible to obtain a one-parameter recurrence relation, using inclusion exclusion:
$$
C(N) = \sum_{\emptyset \neq A \subseteq S_m} (-1)^{|A|+1} C(N-\Sigma A),
$$
where $\Sigma A$ is the sum of elements in $A$. For example, if $S_m = \{3,4,5\}$, then the recurrence is
$$
C(N) = C(N-3)+C(N-4)+C(N-5)-C(N-7)-C(N-8)-C(N-9)+C(N-12).
$$
The initial values are
$$
C(0) = 1, C(1) = C(2) = 0, C(3) = \cdots = C(7) = 1, C(8) = \cdots = C(11) = 2,
$$
or in table format:
$$
\begin{array}{c|ccccccccccc}
N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline
C(N) & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2
\end{array}
$$