A comparison operation for lists, based on P(a > b)

Let $A \cup B$ denote the union of $A$ and $B$.  Sort $A \cup B$ into increasing order, keeping track for each element which list it came from.  Now for each element of this sorted list, annotate it with the number of elements of $A$ that are smaller than it and the number of elements of $B$ that are smaller than it.  Those annotations can be filled in with a single linear scan (starting from the start of the list, and scanning left-to-right, and keeping track of the number of elements of $A$ and $B$ seen so far).  Then you can compute the sum from those annotations: for each $i$, you can compute $\sum_j \text{sign}(a_i-b_j)$ directly from the annotation.

This algorithm takes $O(n \log n)$ time: $O(n \log n)$ time to sort, plus $O(n)$ for the scan, plus $O(n)$ time to add up the sums.


Use depth-first search, or breadth-first search, or any other graph search algorithm.  You don't need Tarjan's algorithm.


What is your intended application.  The article you cited does give a definition of size.  A production rule

T -> R

has size |R|+1, where |R| is the number of symbols in R.  A more precise definition can be found on page 9 of this document.

This notion of size is meant to compare different grammars that produce the same language.  In particular, in the article you cited, the notion of size is used to see that under grammar transformations, the size of the grammar can explode.


Minimum number that cannot be formed by any subset of an array

You can pre compute an array $B$ such that $B[0]=0$ and $B[i]=B[i-1]+A[i-1]$. That you can use $A[L,R]=B[R+1]-B[L]$ to speed up you computations.

Now you can enumerate all pairs $A[L,R]$ and insert them into some sorted data structure $T$, and then you will be able to enumerate all of them in a sorted fashion, and thus answer your question.

This will still be in complexity $O(n^2\log n)$ where $n$ is the size of $A$ but it will not change even if the numbers in $A$ are large. This is not fundamentally faster than proposed solution, I don't know if there is indeed a faster one.


Is there a tactic to help resolving existential quantifiers in Coq?

I was similarly stuck on this problem. I believe your Fixpoint for Star re should just be true. In regular expressions, the empty string is always accepted under star.


Destination-based vs source-based routing

Destination-based routing is the typical, most common type of routing. For this, each message that we send contains the address of the destination and the forwarding decision process makes its forwarding decision solemnly based on this address (and independent of the original sender). i.e. We don't care about who sent the message, only about where it is supposed to go.

So, when constructing a routes, one thing we can do is root a spanning tree at the destination. This creates a path from all possible sources to that destination. This is called a "sink tree".

Source-based routing is the reverse of destination-based routing. The decision process is based on the source address. So, when sending a message, we only include the address of the sender (and not of the destination). The decision on where to forward the message is based on this source address. This means that the source could be sending the message to any host (we don't know exactly who). Therefore we create a spanning tree routed at the source (this is known as a "delivery tree") and the message is thus sent to every child in this tree.

Source-based routing is only really useful for doing some kind of broadcast / multicast (e.g. consider a delivery tree when building a multicast group).


What's the maximum memory address space that the processor can access directly if it connected to a 16-bit memory?

I think there is a confusion here between the number of memory addresses and the total size of memory that can be addressed.

The microprocessor can access $2^{16} = 65536$ memory addresses, regardless of the size of data held at each memory address.

If each memory address holds one byte ($8$ bits) of data then the total memory size that can be addressed directly is $2^{16} \text{ bytes}$, which is $2^6 \text{ KiB} = 64 \text{ KiB}$.

On the other hand, if each memory address holds two bytes ($16$ bits) then the total memory size that can be addressed directly is $2 \times 2^6 \text{ KiB} = 128 \text{ KiB}$.

It also appears your text is using KB as an abbreviation for KiB, which is a common shorthand but not strictly correct.


Clarifying Practicality and Usage of a DFA's Accepted Language

Picture the DFA $M$ as a directed graph, as the usual graphical depiction. Then the final states of your $M'$ that accepts prefixes of the language accepted by $M$ will have all states from which a final state of $M$ can be reached as final states. It should be clear that not all states of $M$ qualify. In particular, any dead states of $M$ (non-final states that loop back on all symbols) won't be final in $M'$.


Is the language TMs that accept finite languages Turing-recognizable?

If that method worked, semi-decidability would always imply decidability for infinite languages (note how you don't need any property of $L$ to make the proof work), which we know is not true.

Since your reasoning is sound, one of your assumptions has to be faulty. What you assume is, paraphrased:

  Assuming semi-decider $H$ for $L$, I can enumerate $L$ in lexicological order by using $H$.

You don't say how you do this, though, and we have already determined that you can not.

What you probably had in mind that we always get a recursive enumerator, and even a repetition-free one for infinite languages. Thus, it's the order that has to be impossible to achieve.

Intuitively, you can not reject $i$ as next output of the enumerator after only finite time.

Proving that $L$ is not semi-decidable works by reduction as well. See here for inspiration.

Hint:

   Reduce from $\overline{K}$, the complement of the Halting language.

Details:

   Define a computable mapping $\langle M \rangle \mapsto \langle M' \rangle$ so that $\langle M \rangle \in \overline{K}$ if and only if $\langle M' \rangle \in L$. For instance, define $M'$ by

 M'(y) :
   Simulate M(⟨M⟩) for y steps.
   if M halts
     accept y
   else
     reject y
 Note how $L(M') = \emptyset$ if $\langle M \rangle \in \overline{K}$, and
 $L(M') = \mathbb{N}_{\geq N}$ if $M$ halts after $N$ steps on its own code.


When reading from a source, often a program wants to read data a few bytes at a time. For instance, the program can ask the OS for the next 4 bytes from a file, so to read the next 32-bit integer. Then, it can repeat the operation again and again, until all the integers have been read.

However, that is rather inefficient. First, disk (or even SSD) reads are done in hardware using large chunks, only, like 512 or more bytes. Reading that much only for 4 bytes is a waste of band. Second, switching between user mode and kernel mode has its cost, and it would be better if any such switch would transfer a non-trivial amount of data.

For that reason, reading is usually done in large chunks, using a "buffer". Basically, the OS reads a large-ish portion of the file (say, a few KBs), and keeps this in a kernel-space array (the "buffer"). This is done in one large chunk so to optimize disk/SSD access. After this, when the program asks for the next bytes, the OS does not need to involve the hardware, and can return data from the buffer.

Context switches are similarly optimized. The C library also commonly reads a large chunk form the OS, using a user-space buffer, using only one system call (= one switch). In this way, when the application program asks for the next (say) 4 bytes, the C library can copy from the buffer without making system calls.

When the buffer becomes empty, the C library starts asking again to the OS, and the OS starts asking again to the hardware.

Buffered writing is similar, but in the other direction, converting many small writes to fewer big ones, so to improve performance. This is done by the C library and the OS/kernel.


About having analytic control over any algorithm which finds perfect matchings.

Will it always return the same set of permutations in the same sequence?

No.  If you call the algorithm twice with the same input, it's not necessarily guaranteed to give the same output both times.  Many standard max-flow algorithms are non-deterministic, so there is no such guarantee.  For instance, consider any algorithm based on selecting augmenting paths.  If at any iteration there are multiple augmenting paths that would be acceptable, the max-flow algorithm will typically select one of them arbitrarily.  Consequently, it is not deterministic.

However, any such algorithm can easily be made to be deterministic by simply specifying a deterministic rule for resolving all non-deterministic choices.  For instance, whenever there are multiple acceptable choices, you can sort all of the acceptable options using some pre-specified order (say, lexicographic order) and always take the first.


Algorithm for splitting array into subarrays with sums close to the target value

You can solve it exactly using dynamic programming, though that might be too slow or might require too much memory. Calculate an array $B(\ell,k)$, which is the minimal error obtained by dividing $a_1,\ldots,a_k$ into $\ell$ parts. This can be implemented in time and space $O(mn)$ by calculating (in advance) the running sums $\sum_{i \leq t} a_i$.


summarizing the comments:
by the standard definition, a star is not a regular graph.

They might defined "regular" in a different way than common to apply to star topology.  Specifically, in the paper the OP point out "regular" is never defined (and sparsely used).


Finding a minimum weight path with certain restrictions

You can solve this in $O(|E| \log |V|)$ time, if all weights are non-negative.  Basically, you'll build a larger graph, of twice the size, then do a shortest-paths query in this graph.

I will call the edges of the original multigraph regular and added edges of the form $i\to j$ for $i\subset j$ as irregular.

For each set $i$, you have two vertices $i^-,i^+$ in the new graph, where $i^-$ represents a step along the path that visits set $i$ before visiting any regular edge; and $i^+$ represents a step along the path after visiting a regular edge. It is easy to work out the edges in this graph (if you have an irregular edge $i \to j$ in the original graph, you have $i^- \to j^-$ and $i^+ \to j^+$; if $i \to j$ is a regular in the original graph, you have $i^- \to j^+$ and $i^+ \to j^+$).

Add a source node $s$ to this large graph, with an edge $s \to i^-$ for each $i$ in your set of source vertices; and similarly add a sink node $t$ with an edge $i^+ \to t$ for each sink vertex $i$.

Finally, find the shortest path from $s$ to $t$ in this bigger graph using any standard algorithm  for shortest paths (e.g., Dijkstra's algorithm).

You can accommodate the restriction about adjacent edges by doubling the size of the graph again.  I'll let you work out the details.  Basically, each vertex in the bigger graph represents a vertex in the original graph, plus a little bit of state summarizing everything you need to know about what comes before this on the path.


I guess it depends on the particular algorithm you have in mind. However, the red/blue segment intersection algorithms that I'm aware of require that there are no monochromatic (red/red or blue/blue) intersections. For example, Chans red/blue intersection algorithm builds a trapezoidal decomposition on the blue segments. That does not really work if there are blue/blue intersections as well.

By the way, note that both red/blue segment intersection, as well as  general (monochromatic) segment intersection can be solved in optimal $O(n \log n + k)$ time.


Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal clique contains only two vertices.

So your algorithm finds a clique of size two instead of a clique of size $n/3$.


Dynamic array updated by adding arithmetic progressions

Hint: find a data structure that supports these three basic operations:

Given $l,r,b$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $b$.
Given $l,r,d$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $id$.
Given $l,r$, compute $\sum_{i=l}^r a_i$.

You can then use those basic operations to implement your operation 1.

Can you think of any way to support basic operations 1+3?  Can you think of any way to support basic operations 2+3?  If you can answer both of those questions with a "yes", you will probably then be able to solve your problem.


Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

You can take
$$
L = \{ a^n b^n : n \geq 1 \} \cup \{ a^k b^n a^n b^\ell : n,k,\ell \geq 1 \}.
$$
You can check that
$$
L \cap L^2 = \{ a^n b^n a^n b^n : n \geq 1 \}.
$$


What are some interesting applications of the skyline problem?

The "skyline problem" is an example of finding the Pareto front of a set of points in 2-D space. More generally it's an example of multi-objective optimization which has many applications.

You might find this thread relevant.


How to determine number of instances for resources in a resource allocation graph?

The number of instances should technically be specified to you. The best I can suggest is assume that each resource will only have one instance each. But I suggest getting more information on your scenario


Shortest paths from a source in weighted graph with only one negative weighted edge

No. The negative edge will not always be part of the shortest path. For example, in the digraph

A <==[+1]== B ==[+4]==> C ==[-1]==> D ==[+4]==> E

the shortest path departing from B is the path from B to A, and does not include the negative edge (C,D).

Even when the negative edge is part of the shortest path, it won't necessarily be the first edge of the path.


Helpful property of prime numbers: The gaps between consecutive prime numbers become arbitrarily large. That means for every r, there is a prime p such that none of the numbers p+1 to p+r are primes. That means $a^nd^mb^k$ is not in the language for p+1 ≤ m ≤ p+r.

That would generally work for "m is a member of an infinite set with arbitrarily large gaps between members of the set", like "m is a square, a cube, a factorial" and many others.


Example of an algorithm where a low-order term dominates the runtime for any practical input?

Cryptography is an example, if a degenerate one. For example, breaking AES encryption is $O(1)$ — all you have to do is find the right key among a finite number, $2^{128}$ or $2^{192}$ or $2^{256}$ depending on the key size (assume that enough of the plaintext is known to determine the key unambiguously). However even $2^{128}$ operations would take all of the computers today (a billion or thereabouts, each doing about a billion operations per sceond) more than the lifetime of the universe (about a billion billion seconds).

A slightly different way to illustrate why big-O isn't everything is to remark that we sometimes use a different algorithm for small input sizes. For example, take quicksort. With the right choice of pivot (which is a tricky business!), it's $O(n \lg n)$. Quicksort operates by divide-and-conquer: every instance involves doing a lot of sorting of small arrays. For small arrays, quadratic methods such as insertion sort perform better. So for best performance, a quicksort of a large array involves a lot of runs of insertion sort for small sizes.


Maximum Independent Subset of 2D Grid Subgraph

As JeffE mentions in a comment, a grid graph is an example of a bipartite graph. If you take a bipartite graph, and remove some of the vertices, it will still be a bipartite graph.

Königs Theorem states, that for bipartite graphs, the number of vertices in a minimum covering, equals the number of edges in a maximum matching.

As mentioned in the answer for Maximum Independent Set of a Bipartite Graph:

  The complement of a maximum independent set is a minimum vertex
  cover

What you are asking, is how to find a maximum independent set in a grid graph with some vertices removed, and the way to do that, is to use some of the algorithms for finding a maximum matching in a bipartite graph, from that construct a minimum vertex cover, and then invert it to get a maximum independent set.

The figure below shows a bipartite graph with a maximum matching (in blue), a minimum vertex cover (in red) and consequently also a maximum independent set (in white):


What is the relationship between NP/NP-Complete/NP-Hard to time complexity?

See the definition of NP completeness. For a problem to be NP-complete, it

needs to be in NP and
all NP problems need to be reducible to it in polynomial time.

Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems.

NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^{O(p(n))}$, for some polynomial $p(n)$. But it is well know that if P $=$ NP, then NP problems can be solved in polynomial time.

NP hard problems are at least as hard as NP problems – you cite a few examples.


Big theta of function with multiple types of n

You can calculate the limit of the function for $n\to\infty$:
\begin{align}
\lim_{n\to\infty}\frac{n\cdot7^n+\frac{8}{n!}}{(n+7)\cdot7^n}&=\lim_{n\to\infty}\frac{n\cdot7^n}{(n+7)\cdot7^n}+\lim_{n\to\infty}\frac{\frac{8}{n!}}{(n+7)\cdot7^n}\\
&=\lim_{n\to\infty}\frac{n}{n+7}+\lim_{n\to\infty}\frac{8}{(n+7)\cdot7^n\cdot n!}\\
&=1 + 0\\
&=\Theta(1)
\end{align}


What is and amplification factor in pseudo-random generators?

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed.
Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you have $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$.  You can use this to construct a language $L\in NP$, such that $L\in P$ allows you to break $G$ (construct a distinguisher with success probability $\ge\frac{1}{2})$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $l(n)>n$, you can construct a PRG with stretch $l'(n)=n+1$).


Flow in a network: Conservation of flow definition

The short answer is $f(u,v)=-f(v,u)$.  Note that the first sum includes both vertices $w$ such that $(u,w) \in E$, as well as vertices $w$ such that $(u,w) \notin E$ but $(w,u) \in E$.  Now unpack the implications of the first sum, separating by these two cases, and I think you'll see what happens.

For a more lengthy explanation, this is covered in standard textbooks.  Make a trip to a library to check out a few textbooks to find a detailed derivation; or, there are even online algorithm texts.


Application of cosine similarity to detect plagiarism

Usually this would be used in conjunction with a bag of words model. You need to convert each document to a vector where the length of the vector is the number of words in the vocabulary. The entries in the vector correspond to the number of occurrences of each vocabulary word in the document. You can apply cosine similarity to these document vectors.

You should consider using tf-idf weighting to make sure that a small set of very common words doesn't end up dominating the distance computation. https://en.wikipedia.org/wiki/Tf%E2%80%93idf


Both uli and Dave Clarke correctly observe that this is a linear programming problem, even in higher dimensions (Can these two point sets be separated by a hyperplane?) and so it can be solved in polynomial time.  But because your points lie in the plane, your problem can actually be solved in $O(n)$ time, where $n$ is the total number of points.

The simplest solution is probably Seidel's randomized algorithm.  Choose an input point $p$ uniformly at random, and recursively compute a separating line $\ell$ for all the points except $p$.

If no such line exists, then the original points are not separable.
If $p$ is on the correct side of $\ell$, then $\ell$ separates the original points.
If $p$ is on the wrong side of $\ell$, then either the original points can be separated by a line through $p$, or the original points are not separable at all.  This condition is easy to check in $O(n)$ time [exercise].

This algorithm runs in $O(n)$ time with high probability (with respect to the algorithm's random choices).  For more details, see the original paper or any number of online lecture notes.


What happens if you run Kosaraju’s algorithm on a DAG?

We should think about the property of SCC(strongly connected component)

A directed graph $G(V, E)$ is acyclic if and only if $G$ has no SCCs with more that one vertex. Because a directed cycle is SCC by definition of the cycle.

Hence, the result of the Kosaraju’s algorithm on a DAG will return $|V|$ trivial SCCs. In other words, it returns $\{\{v\}\mid v\in V\}$.


If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?

If $\overline{M}$ is r.e., then we do know something about $M$: namely, that it's co-r.e. And the intersection of any two co-r.e. sets is co-r.e., so $A\cap M$ is co-r.e. (every recursive set is a fortiori co-r.e.). Beyond that, of course, we can't say anything: every co-r.e. set is of the form $A\cap M$ for some recursive $A$ and some co-r.e. $M$ (take $A=\mathbb{N}$ and $M=$ the co-r.e. set in question).

This may seem a bit silly, but being the complement of an r.e. set is a very strong property, even though we think of it less than r.e.-ness. Also, lots of natural sets are co-r.e. but not r.e., like the set of (indices for) Turing machines which never halt on any input. So the conclusion "$A\cap M$ is co-r.e." is actually quite meaningful.

This answers your specific question, but let me say a bit more.

We didn't really use that $A$ was recursive, merely that $A$ was co-r.e. But what if $A$ is merely r.e.? Then in general $A\cap M$ is neither r.e. nor co-r.e. This is the first step into the difference hierarchy: $A\cap M$ can be rewritten as $A\setminus \overline{M}$, that is, as the difference of two r.e. sets, and we can continue further and talk about more complicated Boolean combinations of r.e. sets. It turns out that this gives a proper hierarchy, even in the coarse terms of Turing degree: for each $n$ there is an $(n+1)$-r.e. set which is not of the same Turing degree as any $n$-r.e. set (I believe this was proved by Cooper but I don't have a reference on hand; it certainly followed his proof of the case $n=1$).

We can try to continue the difference hierarchy into the transfinite but one runs into some difficulties in doing so (namely, the issue of finding appropriate "names" for complicated infinite ordinals - this is where Kleene's $\mathcal{O}$ becomes unavoidably relevant). What we get winds up not being a true hierarchy: even though the ordinals are linearly ordered, we can't avoid having different "difference levels" which are incomparable. The resulting "pseudo-hierarchy" is however a quite interesting object, and is called the Ershov hierarchy.

For more information on this, I strongly recommend the first couple sections of the paper The Ershov hierarchy by Stephan, Yang, and Yu.


Algorithm for listing all binary trees of a given height

As hinted at in comments, just follow the recursive structure of binary trees.

We create a function listbt(h) that lists all binary trees of exactly height h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

Correctness follows with an elementary inductive proof over h.

If you memoize the results of listbt this is going to be as efficient as it gets; the sheer number of trees and thereby the number of checks t != T dominate.

Note that if you employ term sharing (i.e. only link t and T in Node(t, T) but do not copy them) you can reduce the size of the output significantly. That only makes sense if your BTree implementation is immutable, though.


How can I improve my algorithmic ingenuity?

It seems that competitive programming might help you. Or just the "programming" part of it. If you want to hone your problem solving skills (and therefore your ability to come up with original ideas), it seems that solving competitive problems is the way to go, since they by design target this skill.

You would need two kinds of resources: problem archives and theory materials.

For problem archives I can suggest you to try out

timus.online (problems requiring some clever insights/observations start after ~270 difficulty)
codeforces.org (problemset tab, richer variety of problems, but the overall quality is somewhat lower than that on the timus)
onlinejudge.org (in uHunt there is a table with problems that cover a great variety of problems; a supplement for the book Competitive Programming 3)
urionlinejudge.com.br (has some great problems)

Also, there's atcoder.co.jp which is like codeforces but primarily targets math-related problems.

The key to finding original ideas is to know what people have come up with already. If you understand these ideas and can apply them relatively easily then you a) can come up with a clever idea by combining these older ideas in a clever way and b) you can search for fundamentally new ideas much more efficiently because you know what is not a new idea and what is not the new way of thinking to find new ideas.

If you agree with the previous paragraph, then you'll need resources where you'll be able to learn new concepts and ideas. The key with this is to not only understand the theorem or the algorithm but to understand the intuition and the proof(s) also. Proofs give explicit insight as to how to come up with and how to be sure that the idea works. Understanding the tricks and algorithms (of thinking) used in proofs is the key to come up with your own ideas.

Intuition, on the other hand, is an implicit insight, it's something that connects problems, its proofs (or a subset of proofs) and the topic of the problem in general. I say this so that you wouldn't think that intuition is something magical or that if you didn't get it when you read a proof then you wouldn't get it at all. To acquire it you have to perform these steps

Before seeing the solution, try to think on it for at least 30 minutes (for me, doodling helps a lot to come up with intuitive solutions)
Then, if you feel that some ideas that you think are going to work 100% are there but you can't quite reach them in your brain, don't give up on it and hold on to them until you go to sleep. If you won't be able to sleep thinking on the problem, then you're sure to get some insight when you wake up. (https://psychology.stackexchange.com/a/13366 + my experience).
Without any dependence on whether you have solved the problem or not after such a procedure, when you'll open the proof(s), you'll be able to absorb and analyze them much more efficiently, since you'll read not to know the ideas but to find out why your ideas weren't working, how close were you, where you have made a mistake in your thinking, what have you missed, why that thing you focused too much on wasn't that relevant, what have you had to know to solve it anyway, etc. etc.... (this is how SQ3R method works also, it makes you question the text first and only then lets you read it as a way to answer the questions; an active reading, instead of passive reading).
If you were able to extract some guideful intuition out of the proofs, congrats! Now, forget about this problem and come back after two or three days and solve another similar or a little harder problem on the same topic. This way you'll "imprint" this intuition in your brain, so to say, for a relatively long time (See, spaced repetition)
If you haven't then don't be sad. You understood more or less how the proofs work. This means that the only thing that's left is to unite them somehow with intuition. To do that just continue solving problems on the same general topic (strings, graphs, number theory, etc.). Intuition is not bound to some concrete problem (if that was, the intuition wouldn't be able to help solve other problems), if you'll understand intuitions behind other problems then naturally you'll understand the intuition behind the original problem as well!

Okay, so. With this, you'll be able to grasp the old ideas efficiently, understand the intuition and ingenuity behind them. These are plausible resources (although, I think you might already use them):

Introduction to Algorithms. Cormen
geekforgeeks.com
wikipedia.com (seriously, they have great articles on some algorithms)
visualgo.net (especially, if you're a visual learner ;)

From my experience at this point, you'll be able to come with original ideas by yourself and naturally. You'll be able to see the connections between the ideas clearly and they'll start to just pop into your head. Solving problems will sustain the neural paths in your brain and you won't forget the theoretical basis and intuition you've built. Solving problems will also build new neural connections and will bring joy when discovering new insights.

Lastly, I want to say that if your insight is nothing you've learned before, then it has value. If you combine two ideas together, even if it was simple, you'll get a new idea and it will have value. Every time you come up with such ideas, in any case, you create something valuable. If your goal would be to come up with something valuable, then you'll succeed every time. If your goal would be to come up with an "original insight", then you'll be quick to get severely demotivated, since no matter what you'll do, you'll most probably fail (at the beginning for sure). In the end, if you follow these steps or something similar, you cannot get not better! Surely, somewhen in the future, every tenth of your ideas will be a truly original one ;)


Sum weighted nodes between nodes in a DAG efficiently

A vertex $z$ is "between $v$ and $w$" in $G$ (that is there is a path in $G$ from $v$ to $w$ that traverses $z$) if and only if both the following conditions are true: 1) there is a path from $v$ to $z$ in $G$; and 2) there is a path from $w$ to $z$ in $\overline{G}$, where  $\overline{G}$ is the graph obtained from $G$ by reversing its edges.

Using any standard visit algorithm you can compute the set $A$ of vertices reachable from $v$ in $G$ and the set $B$ of vertices reachable from $w$ in $\overline{G}$.

Then you can compute $C = A \cap B$ and find the desired quantity as $\sum_{z \in C} \text{weight}(z)$. Each of the above steps can be performed in linear time.


Is polynomial time reducibility reversible?

This is provably not the case. Let $A$ be any non-trivial language in P (different from $\emptyset$ and $\Sigma^*$), and let $B$ be any EXPTIME-hard language. Clearly $A$ is polytime-reducible to $B$ (since $A$ is polytime and $B$ is non-trivial; or since P$\subseteq$EXPTIME and $B$ is EXPTIME-hard), but if $B$ were polytime-reducible to $A$ then it would follow that EXPTIME=P, contradicting the time hierarchy theorem.


residual graph and augmenting path in max flow

A full edge, e.g. $a \rightarrow c$, has a residual capacity of $0$ in the residual network. So you can't make an augmenting path over that directed edge.
However the reversed edge, $c \rightarrow a$ has a residual capacity of $5$ (since $c_{c \rightarrow a} = 0$ and $f_{c \rightarrow a} = -5$). Therefore you can create an augmenting path using the reversed edge.
The residual network would be:

E.g. a possible augmenting path would be $s \rightarrow c \rightarrow a \rightarrow d \rightarrow t$. You can increase the flow along that path by 5 and get the following flow network:

This is also the maximal flow, since $\{s, c\} - \{a, b, d, t\}$ forms a saturated s-t-cut.


Proving number of calls made in cut-rod algorithm

You can easily prove this by induction.

Base Case T(0) = 2^0 = 1.

Say T(k) = 2^k. is true for some k.

Hence T(k+1) = T(k) + sum(Ti) {i = 0 to k-1}
             = T(k) + T(k)
             = 2*2^k = 2^(k+1)

Note: By looking at the code, it seems that if you use dynamic programming and memo-ize the T(i)'s from bottom-up, you can make this algorithm into a O(n^2) algorithm.


Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)

Let me first give a concrete example of a formula $F(x,y)$ such that $\forall x \exists y. F(x,y)$ is true, but $\exists x \forall y. F(x,y)$ is false.
I'll then address the expansion of the universal quantifier in your question.

Take $F(x,y)$ to be a formula expressing the equality $x \oplus y = 1$, where $\oplus$ denotes exclusive-or.
We can explicitly write $F$ as $$F(x,y) = (x \land \neg y) \lor (\neg x \land y).$$

To see that $\forall x \exists y. F(x,y)$ is true, let $x$ be given and take $y = \neg x$.
Then $x \oplus y = x \oplus \neg x = 1$.

To see that $\exists x \forall y. F(x,y)$ is false, first take $x = 1$. Then for $y = 1$, we have that $F(x,y)$ is false, i.e., $F(1,1)$ is false.
By the same reasoning, $F(0,0)$ is false, so there is no $x$ such that $\forall y. F(x,y)$ is true.
Hence $\exists x \forall y. F(x,y)$ is false.

Your mistake is in the following argument.

  Suppose $\exists y\ (F[x \to T] \land F[x \to F])$ is unsatisfiable. Then at least one of $\exists y\ F[x \to T]$ or $\exists y\ F[x \to F]$ is also unsatisfiable.

The point is that $\exists y\ F[x \to T]$ and $\exists y\ F[x \to F]$ may both be satisfiable, but the choice of $y$ which satisfies them may be different.
In order to satisfy $\exists y\ (F[x \to T] \land F[x \to F])$, you must find a single value of $y$ that satisfies both $F[x \to T]$ and $F[x \to F]$ simultaneously.
This may not be possible, even if it is easy to satisfy one of $F[x \to T]$ and $F[x \to F]$ individually.

It may be helpful to expand your argument using the example I gave to see exactly where it breaks down.


Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$

Let us start by giving an alternative formula for $\sum_{u,d} |L(u,d)|$. For a node $x$, let $\pi^{(d)}(x)$ be its $d$'th parent, and let $h(x)$ be its height. Then
$$
 \sum_{u,d} |L(u,d)| = \sum_x |\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}|.
$$
It suffices to show that $|\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}| = O(\sqrt{n})$ for all nodes $x$.

Let $y = \pi^{(d-1)}(x)$ and $\pi(y)$ be $y$'s parent. If $L(\pi(y),d) \neq L(y,d-1)$ then $y$ must have a sibling $z$ with a leaf at depth $d$. We can associate the $d$ vertices on the path leading to the leaf (including $z$) to $\pi(y)$; note that vertices associated to different parents of $x$ are distinct.

For each element in $\{L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}$ choose a representative $\pi^{(d)}(x)$ with the maximal $d$, and let $I$ be the set of all such $d$'s. In particular, if $\pi^{(d)}(x)$ is a representative then $L(\pi^{(d)}(x),d) \neq L(\pi^{(d-1)}(x),d)$, and so $\pi^{(d)}(x)$ has $d$ vertices associated to it. We deduce that
$$
\sum_{d \in I} d \leq n.
$$
In particular, $I$ can contain at most $\sqrt{n}$ numbers larger than $\sqrt{n}$, and so $|I| = O(\sqrt{n})$.


RISC machines can have register renaming, just like CISC machines can have register renaming. Register renaming is an aspect of the processor implementation, whereas RISC is an aspect of the instruction set, so they are fairly orthogonal: there can be two processors implementing the same architecture (i.e. accepting the same code), but in different ways (and with different performance characteristics), one with register renaming and one without.

The Wikipedia article gives the example of the Alpha 21264. Alpha is pretty strongly on the RISC side.

The Alpha 21264 is considered superscalar, by the way. I don't know why a superscalar processor would have to be CISC or RISC: again, the ability to process multiple instructions in parallel is orthogonal to the complexity of the instruction set. In fact, RISC processors are more likely to be able to parallelize instruction execution successfully, because the instructions are easier to analyze. But CISC processors can and do do it too.


Are the definitions of loop in CS and in programming (standard/common) identical?

In Mathematics and computer science, looping is generally associated with either some repetitive work, or with accumulated summation (bitwise, or higher logic operations).
Looping is more of an abstract view of iteration, in, say, programming - where it is very specific and depends on the language and associated compiler with programming point of view.

Sidenote: it is also a convenient way of writing programs to have loops rather than call some functions multiple times which is not good practice.


Running time of algorithms that sometimes loop forever

The textbook Computational Complexity: A Modern Approach by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class cannot capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.


Can I remove left recursion on this grammar

Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$.

If you analyze carefully you will see that you are not applying Algorithm 4.19 at all. We are just removing left recursion where we have only immediate left recursion.

Cycles are of the form $A\rightarrow B, B\rightarrow C, C\rightarrow A$. When we remove left recursion in immediate left recursive grammars, we are ignoring $S\rightarrow S$.

Also presence of $\epsilon$ creates problem for the algorithm 4.19 given in the red dragon book (2007 edition), but the method of removing left recursion in immediate left recursive grammar works even in the presence of $\epsilon$.


Is s-grammar powerful enough to generate all possible DCFL?

Actually the example of a language not accepted can be quite simple, due to a technicality. The language $a^*$ is not generated by a s-grammar.

In fact, an s-grammar cannot generate $\varepsilon$. In order to remove $S$ from the stack we have to apply at least one production, and any production will produce a terminal symbol.

But even if we see this as a technicality, we cannot generate two strings, one of which is the prefix of another. If we can generate a string $\alpha$ which then is accepted because all veriables have been rewritten (the stack only contains the new $z'$), then how would we generate a longer string $\alpha\beta$? It must follow the same computation initially.

This is the case because the PDA you produce is actually a PDA with empty stack acceptance: when the stack is empty (or actually only has $z'$) we must accept. It is well known that deterministice PDA with empty stack acceptance can only generate prefix-free languages. Addingan end-of-string marker is usually the remedy.

The real-time property (reading a symbol every step) is a larger problem.
Consider the language $\{ a^i b^j c^i \mid i,j \ge 1\} \cup \{ a^i b^j d^j \mid i,j \ge 1\}$. It can be accepted by a DPDA. push $a$'s, push $b$'s. Then when reading a $c$ we pop the $b$'s and compare the $a$'s and $c$'s. Otherwise when reading a $d$ we compare the $d$'s with the $b$'s using the stack. Thus you need popping of stack symbols without reading input. A real-time PDA cannot do that (and neither the s-grammar). The source I know for this refers to Autebert, Berstel, Boasson: Context-Free Languages and Pushdown Automata in the Handbook of Formal Languages.

Of course the PDA has only a single state. I do have to check: it seems that also the single state restriction reduces the languages accepted.


An error on Introduction to Algorithms 3rd edition about closest pair of points

Just the two lines before, (or last two lines of page 1040 if you want) say the following:

Observe that if a pair of points has distance less than $\delta$, both
points of the pair must be within $\delta$ units of line $\lambda$. Thus,
as Figure 33.11(a) shows, they both must reside in the 2$\delta$-wide

Meaning that if you want to be able to combine them after divide and conquer phases, you specifically are going to look within the 2-$\delta$ range. And this is why the first step is to remove all the points that exceed that limitation, therefore that they do not satisfy such constraint.
You want to keep only the points within that window-range.


Is the Choice operator implementable on $\pi$-calculus?

The issue is that you are manipulating $\oplus$ but you don't have any rules (besides its definition) telling you what reductions you can do. The whole point of the paragraph that presents this definition is that there are multiple notions of choice and some but not all are encodable.

  Many process calculi have explicit choice or summation operators for
  nondeterminism, allowing for example $P+Q$ which can behave either as
  $P$ or as $Q$ (this is imprecise – in fact several different operators
  are possible).  [...] In some cases a form of choice is encodable
  in a choice-free calculus – for example a purely internal choice can
  be encoded in the π-calculus given in Section 1.1 above by [expression from question] but
  in  other  cases  non-encodability  results  can  be  proved [...].


Functional dependencies , minimizing SUU->V

Yes, each side of a Functional Dependency is a set of attributes, not a multiset, so SUU -> V can be simplified to SU -> V.

If you think about the definition of Functional Dependency you will understand why this is true.


ILP representation of the number of maximal 1 sequences in a row

I think this can be done with $9n$ variables, instead of $n^2$.  Define the following integer variables for use in your linear program:

$a_i = 1$ if index $i$ is within an event
$s_i = 1$ if an event starts at index $i$
$e_i = 1$ if an event ends at index $i$
$c_i = $ the number of positions until the end of this event (so that index $i+c_i-1$ is the end of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
$d_i = $ is how many positions since the start of the event (so that index $i-d_i+1$ is the start of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
$\ell^1_i = $ the length of the event containing $i$, if $i$ is the end of an event, or $0$ if $i$ is not the end of an event
$\ell^2_i = $ the length of the event containing $i$, if $i$ is the start of an event, or $0$ if $i$ is not the start of an event
$o^1_i = $ the amount index $i$ is shifted when copying to the new array, for the first copy of that element
$o^2_i = $ the amount index $i$ is shifted when copying to the new array, for the second copy of that element

These can be enforced with the following equations:

$s_i = a_i \land \neg a_{i-1}$ (see Express boolean logic operations in zero-one integer linear programming (ILP) for how to enforce this)
$e_i = a_i \land \neg a_{i+1}$
$c_i \ge c_{i+1} + 1 - n s_{i-1}$, $c_i \le c_{i+1} + 1$, $c_i \le n a_i$, $c_i \ge e_i$, $c_i \ge 0$
$d_i \ge d_{i-1} + 1 - n e_{i-1}$, $d_i \le d_{i-1} + 1$, $d_i \le n a_i$, $d_i \ge s_i$, $d_i \ge 0$
$\ell^1_i \le n e_i$, $\ell^1_i \ge d_i - n(1-e_i)$, $\ell^1_i \ge 0$
$\ell^2_i \le n s_i$, $\ell^2_i \ge c_i - n (1-s_i)$, $\ell^2_i \ge 0$
$o^1_i = o^1_{i-1} + \ell^1_{i-1}$, $o^1_0 = 0$
$o^2_i = o^2_{i-1} + \ell^2_i$, $o^2_0 = 0$

Then the total number of events is $s_1+\dots+s_n$, and you can model shifting as follows: index $i$ in the original array is shifted to indices $i+o^1_i$ and $i+o^2_i$ in the new array.

Do check my work carefully. There could easily be off-by-one errors or other mistakes in the above.


How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?

http://www.owenstephens.co.uk/blog/2014/09/28/NFA_DFA.html

https://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf

Evil's link and this other link seem to show how to apply the Pigeonhole Principle to show how to answer my problem. The second one explains it more visually and in a more noob friendly fashion.


What is the complexity class of finding vertex cover number of a simple graph?

It is actually finding the number that is NP-complete.  The (decision) problem is formally stated as follows:
Vertex cover.  Given a graph $G = (V, E)$ and an integer $k$, does there exist a set of at most $k$ vertices $C \subseteq V$ such that every edge has at least one endpoint in $C$?
As you can see, this is precisely your $\tau(G)$.
The other problem is often called the optimization problem, and is defined as following:
Vertex cover optimization.  Given a graph $G = (V, E)$, find a set $C \subseteq V$ of minimum size such that every edge has at least one endpoint in $C$.

The two problems are quite easy to jump between, at least if you are given polynomial time.  If you have an algorithm for the optimization problem, I'm sure you have already found out how to answer the decision version.
But given an algorithm for the decision version it is quite easy to create an optimization algorithm.  You can try to work it out yourself, but a hint is to see what happens with $\tau(G)$ if you remove a vertex from the graph.


A string that takes a DFA from any state to a given state?

It turns out that there exists a string that takes all states to the same state iff for each pair of states, there exists a string that takes both states to the same state.

Using this fact, I had success with the following algorithm:

Generate a new DFA from the Cartesian product of the old DFA with itself. (The new DFA contains $\left(a,b\right) \overset{x}{\rightarrow} \left(c,d\right)$ iff the old DFA contains $a \overset{x}{\rightarrow} c$ and $b \overset{x}{\rightarrow} d$, where $x$ is an input symbol and $a$, $b$, $c$, and $d$ are states.)
For each state $\left(a,b\right), a \neq b$ in the new DFA, search for a path from $\left(a,b\right)$ to a state of the form $\left(c,c\right)$. (If found, then that means there is a string that takes the old DFA from $a$ to $c$ and from $b$ to $c$.)
There is a reset sequence for the old DFA iff every search in the above step yields such a path.

More info:

https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-90.pdf


Finding all circuits that contain a given edge

It should be NP-complete to compute, given an arc $e = uv$ of a directed graph $D = (V,A)$ whether there is a cycle containing some vertex $w$ using the arc $e$.  The instance to this problem is $(D,e,w)$.

By reducing from back-and-forth (two-disjoint paths from $a$ to $b$ and from $b$ to $a$), given an instance $(D',a,b)$ of back-and-forth, construct the instance $D$ where you make two copies of $a$, $a_1$ and $a_2$ and an arc going from $a_1$ to $a_2$.  The constructed instance is $(D,(a_1a_2),b)$.

Now, suppose there are two-disjoint paths from $a$ to $b$ and back, then there is a cycle from $a_2$ to $b$ and from $b$ to $a_1$, hence $b$ is on a cycle containing the arc $a_1a_2$.  For the reverse direction suppose that $b$ is on a cycle traversing the arc $a_1a_2$.  Then, in the original graph, there is a path from $a$ to $b$ and one from $b$ to $a$.  qed


Articulation Vertex, significance and real world usage?

First, yes, probably.  One example is when we wish to split the graph into its sets of biconnected components.

Second, I think you misunderstand the purpose of the exercise.  The goal is to teach you to think in terms of graph algorithms, not necessarily give you the solution for existing real world problems.

Most real world problems differ slightly from textbook exercises and examples.  But the goal is to give you a toolbox so you can handle similar problems.

It is also important that you understand what an articulation point (or a cut vertex) is, as well as the similar concept for edges (bridge), so that you get a better understanding of graphs and graph connectivity.  It is crucial to understand the concept of cut vertices and bridges before lifting the definitions to their more general versions on vertex- and edge-connectivity (separators and cuts).


If P=NP, are there cryptosystems that would require n^2 time to break?

Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure Communications over Insecure Channels" by Ralph Merkle, where he proposed to use “puzzles”. This is a key agreement protocol.

Alice sends $n$ encrypted messages (called puzzles), each containing a unique identifier $I_i$ and a session key $K_i$, with the keys for each messages chosen among a set of $n$ keys. This takes $O(n)$ time ($O(1)$ per message).
Bob decrypts one of the messages by brute force and sends back $I_i$ encrypted with $K_i$. This takes $O(n)$ time ($O(1)$ per key, times $n$ possible keys).
Alice tries all the keys to decrypt the message. This takes again $O(n)$ time.

Each party requires only $O(n)$ computation, but an eavesdropper who wishes to find $K_i$ needs to try out half the puzzles on average to calculate the right key (the eavesdropper does not know which message Bob chose to decrypt), so the eavesdropper requires $\Theta(n^2)$ computation on average.

After Merkle invented his puzzles, Diffie and Hellman published a key agreement protocol based on the discrete logarithm problem. This protocol is still used today.

The problem with Merkle puzzles, or anything where the amount of work to be done by the attacker only increases as the square of the legitimate party, is that it takes huge key sizes and amounts of computation to achieve a decent security margin.

In any case, it is not clear that merely proving that P=NP will invalidate existing cryptographic algorithms. If the polynomial increase is a high enough power, it might not matter so much in practice. See How will security need to be changed if P=NP?, Can we say that if P=NPP=NP there is no CPA secure public key encryption?, P = NP and current cryptographic systems, …


Strongly NP-hard problems and Dynamic Programming

You're generalizing too much from a small sample size.  There is no guarantee that all weakly NP-complete problems can be solved using dynamic programming; I'd expect probably there are some that dynamic programming isn't much good for.

And, there is no guarantee that a strongly NP-hard problem will take exponential time to solve.  There are NP-complete problems that can be solved faster than exponential time.  (See also the exponential time hypothesis.)

Dynamic programming is just one algorithmic technique among many.  There's nothing magical about it, and it's not a be-all and end-all.  There are other algorithmic methods other than dynamic programming.


Maximum number of configurations of Turing machine after $n$ moves

Note that you are bounding the maximal number of configurations, that the machine can be in, from above. To see it more clearly, when a TM $M$ runs on a finite word $w$ it induces a configuration tree $G = \langle V, E\rangle$ where:

$V$ is the set of configurations that $M$ can be in when it runs on $w$,
$q_0w$ is the initial configuration of $M$ on $w$ and it is the root of the configuration tree,
and the edges in $E$ are defined such that $u$ is a child of $v$ whenever $u$ a consecutive configuration of $v$ (by consecutive we mean that it is possible to reach $u$ from $v$ without violating the transition function of $M$).

As you have mentioned, $k$ is a branching factor, and we usually mean by that the maximal branching degree in the configuration tree. In this aspect you're not correct, $k$ is at most $|{Q\times\Gamma\times \{L, R\}}| = {2|Q|\cdot |\Gamma|}$, and this follows from the definition of the transition function. Indeed, $k$ bounds from above the number of consecutive configurations (which is a subset of configurations) and not the number of all possible subsets of configurations of the TM.

Considering the configuration tree, it is a tree of height ($n = |w|$) with branching degree $k \leq {2|Q|\cdot |\Gamma|}$. Now its not hard to see that such a tree has at most $k^n$ leaves which bounds from above the number of configurations that $M$ can be in when it runs on a word $w$ of length $n$.

A thing worth mentioning is that, $k$ is a constant that does not depend on the input word $w$ (on $n = |w|$) or on a specific configuration tree, and we know that it exists. This sometimes makes life a bit easier as some algorithms/proofs rely on its existence to conclude some upper bounds.


Is the search for a k-Hamiltonian Path NP-hard?

Any problem in NP that contains an NP-complete problem as a special case is NP-complete.

Any algorithm that can solve the $k$-Hamiltonian path problem must, in particular, be able to solve the case $k=1$, which is just an ordinary Hamiltonian path.  We can obviously verify a claimed $k$-Hamiltonian path in polynomial time, so the problem remains in NP. Therefore, $k$-Hamiltonian path is NP-complete.


Is there a "flaw" in the backpropagation algorithm?

There's no paradox.  This is not a flaw.  Nothing is going wrong here.  In both examples, you're making steady progress: the output steadily gets (monotonically) closer and closer to the target.

Looking at individual weights (like w1 or w2), there's no reason to expect them to vary monotonically during the learning process.  If we perfect foresight and we know what the final optimal values of the weights are, we'd know whether each weight needs to increase or decrease -- but we don't.

Remember that backpropagation is just gradient descent, used to minimize some loss function.  Gradient descent is a local method for optimization: it makes a locally greedy step.  It has no global knowledge and as a result if you look at any single weight (any single coordinate), it won't necessarily vary monotonically: it might increase and then decrease, for instance.

Can you improve on backpropagation?  Yes, you can.  A large part of the success of deep learning is that researchers have found improvements to gradient descent for training neural networks (e.g., learning rate, momentum, and more).  Nonetheless, they're still optimization methods that work by taking a locally optimal step, and so they can be subject to overshoot and to phenomena such as you noticed.  Multidimensional optimization is hard.  You're going to see this kind of thing happen in pretty much any iterative method for optimization.

Bottom line: This isn't a flaw, this is only to be expected, given the difficulty of multidimensional optimization.  You still get to optimal values in the end, and that's almost-miraculous in its own right -- you should be glad for that and not worry too much about the fact that it takes longer to get there than if we already knew what the optimal solution was before we began.


Algorithm to generate integer sets fulfills restrictions

You want to enumerate all integer partitions of $v$ into exactly $\ell$ parts, where each part is $\le b$.  Let $F(v,\ell,b)$ denote the set of all such partitions.

One can construct a recursive algorithm for this.  For instance, any such partition must include the number $b$ one, two, three, ..., or $\lfloor v/b \rfloor$ times, so:

$$F(v,\ell,b) = \bigcup_{i=0}^{\lfloor v/b \rfloor} F(v-ib,\ell-1,b-1) + b+\cdots + b,$$

where $F(\star)+b+\cdots+b$ represents the set of partitions (multisets) obtained by starting with each partition in $F(\star)$ and adding $i$ copies of the number $b$ to it.  Moreover, this is a disjoint union, so there is no need to use hashtables to eliminate duplicates.

However, the number of such partitions can be exponentially large in $v$, so in general the algorithm might be infeasibly expensive, unless $v$, $\ell$, or $b$ are sufficiently small.


Genetic Algorithms - Why wouldn't we use the principle of Elitism?

It increases the convergence speed of the GA, which is a double-edged sword. You want the algorithm to find good solutions quickly, but not so quickly that is has not been able to sample sufficiently large areas of the space that it's not just doing a very local search around the initial population.

Another option that can work well is to be elitist, but try to intelligently figure out when you've converged and should introduce some diversity.


Pseudo-dimension of a subset of affine functions

I am using the definition of pseudo-dimension found here, page 10 of the pdf.
Denote $h_1(x) = 2x+1$, $h_2(x) = 4x$, $h_3(x) = x$ and $h_4(x) =3x+4$.
Let's consider $C = (-2, 2)$ a vector. Then $r = (-2.5, 6)$ is a witness that proves that $C$ is pseudo-shattered by $\mathcal{H}$:

$h_1(-2) = -3 <-2.5$, $h_1(2) = 5 <6$;
$h_2(-2) = -8 <-2.5$, $h_2(2) = 8 >6$;
$h_3(-2) =  -2>-2.5$, $h_3(2) = 2<6$;
$h_4(-2) = -2 >-2.5$, $h_4(2) = 10 >6$.

Clearly $\text{Pdim}(\mathcal{H})< 3$ since the pseudo-dimension cannot be greater than $\log_2 |\mathcal{H}|$.
That proves that $\text{Pdim}(\mathcal{H}) = 2$.


Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively

We are looking for a sum $z = x + y$, where $z$ has $k$ bits set, $x$ and $y$ have $g$ and $h$ bits set, and $z$ is as small as possible. We assume $g ≥ h$. A solution can be found directly, without any dynamic programming.

We add the numbers $x$ and $y$ from the lowest to the highest bit, taking carries into account. If we add two bits 0 + 0 without a carry, these bits can be removed without changing the number of bits set, but making the result smaller.

We can also take any pairs where we add 1 + 0 without carry, or 0 + 1 without carry, and move those pairs to the lowest bit positions. This doesn't change the number of bits set, but moving a 1 bit in the result to a lower bit position will not make the result larger, but may make it smaller.

Now if we add two bits 0 + 0 with carry, then we can remove these bits as well, but it is slightly more complicated. Obviously we can remove them if they are the highest bits. Otherwise, since adding 0 + 0 with or without carry does not produce a carry, and we removed all pairs 0 + 0 without carry, and moved all pairs 0 + 1 or 1 + 0 without carry to the lowest bit positions, the next higher bits must be 1 + 1. Adding 0 + 0 with carry gives a result of 1 and no carry, then adding 1 + 1 without carry gives a result of 0 with a carry. If we remove the two 0 bits, then we add 1 + 1 with carry, which gives a result of 1 with a carry. The number of bits set is unchanged, but a zero bit is removed in the result, making the result smaller.

So we are adding any number of pairs 0 + 1 or 1 + 0, then we may have a pair 1 + 1 producing a carry, followed by any number of pairs 1 + 1, 1 + 0 or 0 + 1. Starting with the addition 1+1 we will always have a carry, and adding 1 + 1 with carry produces a 1 with carry, while adding 1 + 0 or 0 + 1 with carry produces a 0 with carry. Reordering these pairs makes no difference to the number of bits set, but by moving all pairs 1 + 1 as far as possible to the lower positions we move 1-bits to lower positions in the result, making the result smaller.

Adding the initial 1+0 and 0+1 pairs produces exactly one bit set in the output for each bit set in the input. Adding 1+1 produces 0 output bits; each further pair produces one output bit set less than the input bits, and finally one bit will be set in the output from the final carry. If this optional range consists of j pairs, then we lose j output bits (for example, 111 + 111 = 1110, j = 3, six bits set in the input, 3 bits set in the output).

We see that we have no solution if $k > g + h$. If $k = g + h$ then one optimal solution is $x = (2^g - 1)·2^h$, y = (2^h - 1).

If $k < g + h$, then we let $j = (g + h) - k$. We need to lose exactly $j$ bits set, so the range of bit producing carries must be $j$ bits long. In this range, from j+1 to 2j bits are initially set; we get the smallest possible sum if we have as many pairs 1+1 as possible. If g + h ≤ j then there is no solution. We construct the numbers x, y as follows:

We have $a$ 1+1 pairs, where $a = min (k, j, h)$. Then we add $b = j-a$ pairs at higher and $c = k - a$ pairs at lower bit positions. Of these pairs, we have $g-a$ pairs 1+0, and $h-a$ pairs 0+1.

As an example: Let k = 10, g = 14, h = 3. j = 7, a = min (k, j, h) = min (10, 7, 3) = 3, b = j-a = 7-3 = 4, c = k - a = 10 - 3 = 7. We have

x =   1111 111 1111111
y =   0000 111 0000000
z = 1 0000 110 1111111


The clue that you got is a bit strange, since true clauses are not enough. Here is one possible solution. Given a CNF formula with $m$ clauses, let $a$ be a new variable, add the clause $a \lor \lnot a$, and add $m+1$ copies of the clause $a$. I claim that if this formula is half-satisfiable then the original formula is satisfiable.
An assignment in which $a$ is true satisfies at least $m+2$ out of the $2m+2$ clauses, which is more than half the clauses. Therefore any assignment half-satisfying the new formula must assign false to $a$, leading to the conclusion that the $m$ original clauses must all be satisfied.


Problems with decidability open (for a long time) proven decidable

I suspect there are many of them.  Pick almost any recent paper that shows decidability of some problem, and I suspect chances are good you'll  have an example.  So, I doubt your heuristic that if decidability remains open for a long time, chances are that the problem is undecidable.

For example: The matrix mortality problem for non-singular 2x2 matrices was recently shown to be decidable (Decidability of the Membership Problem for 2 × 2 integer matrices, Potapov, Semukhin).


A doubt on best media for a time capsule

This is an interesting question that has a multidisciplinary application. Not only does this apply to computer science, but given the nature of preservation of that data over time also applies to archival science!
While DVDs and CD-ROMs generally have a high information density, they were never designed with longevity in mind. The average life-expectancy for either of the two is about 100-200 years, according to Council on Library and Information Resources. [1]
This may sound like a long time, but your question regarding the ability to retrieve the information 120 years from now comes into play. A major factor in deciding if a media is archival or not is the ability for that information to be interpreted years later. Assuming there is still a method for retrieving data from CDs and DVDs 120 year from now depends on several factors:

How much information are you looking to store?
What are the storage conditions?
--You said "time capsule," but does this mean the capsule will be hermetically sealed? Will it be purged of all moisture, oxygen, and other environmental contaminants that are known to degrade material integrity over time? Will the environment be replaced with an inert gas like nitrogen to provide a stable environment?
What is the tolerance for data loss/corruption? Is this going to be something that needs to have archival quality, e.g. zero-tolerance for loss? CDs and DVDs can experience some loss given their storage and handling over time. [1]
You have already asked one of the most important questions regarding the ability to retrieve the information 120 years from now.

The last question is something that archivists have been asking for some time. In today's world where we are generating more data on a daily basis than we have since the beginning of time, we need to develop a solution that addresses the questions of how much information needs to be stored and for how long does it need to last?
A question still remains unanswered: does your time capsule have to have media that already exists, or is it a quandary into the realm of storage technologies that could be developed to store information for a long period of time?
If it has to be of media that already exists, there are a few options out there:

Microfilm: industry standard for data preservation. Film of particular types is guaranteed to last for ~500 years. [2] In the application of computer science, you could quite feasibly encode some arbitrary data in binary dots/dashes onto a piece of microfilm and interpret the data via computer. The advantage here is twofold: binary is a numbering system that isn't going anywhere and all you just need something to view the microfilm. Any intermediate technology can change between now and the next 120 years (think scanners, other ways of reading data into a computer), but all you need is a way to read visual data into a computer. This is unlike CDs or DVDs that can only be read by a very specific device.
You already mentioned one of them: an LP. Specifically an LP made from copper, aluminum and gold like the ones on Voyager I and II.
Least romantic? Straight up paper. As long as it is well-kept and information density is not a concern, acid-free paper will stick around for 120+ years (think The Declaration of Independence).

Things to stay away from:

SSDs or anything based on flash memory. These all need a minimum trickle charge of voltage to hold onto all of their data. Over time, the electrons leak from the storage cells and the data becomes corrupted. [3]

Some things have already been proposed for future storage:

Recording the information on a CD or DVD-like surface, or a small square, either of which would be made from glass. This would not involve the metallic substrate employed by laser-read media that is known to degrade over time. The method for recording the information would be etched in the media by laser in a similar bit pattern, while using etchings of varying depths could be used to increase the information density.
Using DNA to encode data. DNA is known to last for millennia as long as it is kept from UV light. It would also provide a method of storing information in base-4 -- given the fact that DNA uses the four base pairs G, C, T and A to store information -- versus base-2, which uses 0 and 1. This would effectively increase the information density in two domains: the space in which the data could be stored given the relatively small size of DNA and the numbering system used to store that data.


Kempe chains are explained in textbooks on graph theory. They appear in the five color theorem, an easy result which is proved using them.

The four color theorem is unfortunately rather complicated. You can try reading a summary of the Robertson et al. proof (including pointers to the computer code they use), Steinberger's simplified proof or Gonthier's account of his group's computer-checked proof.


Theta bound for runtime analysis of nested while loops

The innermost loop has running time $\Theta(n)$. The middle loop runs for $\Theta(\log i)$ iterations. If $2^m < n \leq 2^{m+1}$, this means that the total running time is proportional to
$$
n (\log 1 + \log 2 + \cdots + \log 2^m) = n \log 2(0 + 1 + \cdots + m) = \Theta(n m^2) = \Theta(n\log^2 n).
$$


There are two common ways that the implementation of any B-tree variant decides if you're at a leaf node or not.

Most B-tree implementations include a tiny header in each node (e.g. to store the number of elements/pointers in the node). It might only be a word in size, but even then, it's usually not hard to find one spare bit to mark leaf nodes vs internal nodes.
Unless you are in the middle of a difficult rebalance operation, all leaf nodes are at a fixed depth in any B-tree. So knowing this fixed depth means you can just keep track of how "deep" you are in the tree while searching and you will know when you reach a leaf.


There is a general method to convert any CFG into a PDA. That's what jmite meant. You can find more details on that in wikipedia, or by searching this site.

But once you realized the language is $L=\{w\#x \mid w^R \text{ is a substring of }x\}$, you can forget about the grammar and directly construct a PDA.

The PDA works like what you describe in your question - it begins by putting $w$ into the stack. Then it needs to pop it out and compare it to $x$. But it might be that the substring $w^R$ is not a prefix of $x$, which causes your confusion.

The idea you are missing is the power of non-determinism: allowing the PDA to "magically" select the right way out of many possible ways to proceed.

In more details, the PDA will do the following. It will read some letters from the $x$ part of the input and just ignore them. Then, at some point which will be chosen "non-deterministically" (or, "magically", if you prefer), it will start comparing the input to the stack (and accept if there is a match; reject otherwise).

If indeed $w^R$ is a substring of $x$, there is a way for the PDA to make the right choice and start comparing the input to the stack exactly at the right position. This is enough to show that the PDA accepts (at least) $L$.

The concept of non-determinism is very strange, but think about it that way: the construction above defines infinitely many possibly (deterministic) PDAs: each one starts to pop the stack at a different time. "Accepting" a word in a non-deterministic way is defined as the event that at least one of the above  machines accepts. The case of "Rejecting" a word is defined to be the event in which all the above machines reject.


Formally describing a new domain specific programming language

There are two parts of the semantics you will need to describe:

static semantics: structure of well formed programs
dynamic semantics: meaning of running programmings

Static semantics usually take the form of type systems. I'd recommend looking at the books by Benjamin C Pierce and Robert Harper. Alternatively, you could write the rules of well-formed programs as a collection of (formal or informal) statements describing the validity conditions of your program. The formal approach taken by type systems provides a well-known framework for such specifications.

There are many formalisms for expressing the dynamic semantics to consider as your basis:

denotational semantics --- gives meaning  in terms of semantic domains
operational semantics --- gives meaning in terms changes to an abstract machine states
axiomatic semantics --- gives meaning in terms of assertions about the state of the machine
algebraic semantics --- semantics is defined in terms of algebraic laws.

There should be plenty of books out there on these topics. A good broad introductory one is
Nielson and Nielson's Semantics with Applications. A downloadable version is available from the authors' site.
There is also a newer edition, but I haven't seen it.

Within each of these, there are choices to make. For example, if you decide to use operational semantics, there are large-step semantics, small step semantics, semantics based on labelled transition systems, semantics based on rewriting logic.

In Composing contracts: an adventure in financial engineering,
Simon Peyton Jones et al gives denotational semantics to a financial DSL.
The Denotational and Static Semantics of a Domain-Speciﬁc
Language for Flow-Network Design by
Assaf Kfoury presents a denotational semantics for a flow network DSL
Andrei Lapets' thesis Algebraic Semantics of Domain-Specific Languages
discusses algebraic semantics of DSLs.
There are many more: this, that, one in terms of abstract machines, another one.

What kind of approach you should take will depend on what kind of language your DSL is, what kind of experience you have with designing semantics, and your personal preference.

Without any concrete details, I can help no further.


Your solution is a good one, and that's how I'd prove it also. I don't believe a more straightforward or simpler version is possible.


Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where
$0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.
But I don't understand what should I do after above step.

The approach you would like to use here is "going backwards from the target".
Suppose we do have $c_1n^b \leq (n+a)^b$ for some constant $c_1\gt0$ when $n$ is large enough. What can we understand or deduce from it? What is needed to make it true?
Since the exponent is the same, we can use the law of same exponent, $(x/y)^m = x^m/y^m$ to simplify that inequality so that we will have the appearances of our variable $n$ closer to each other.
$$  c_1\leq \frac{(n+a)^b}{n^b}=\left(\frac{n+a}n\right)^b$$
Raising both sides to the power of $\frac1b$, we have
$$  (c_1)^{\frac1b}\leq \left(\frac{n+a}n\right)^{b\,\frac1b}=\frac{n+a}n = 1+\frac an$$
(Another way to obtain $(c_1)^{\frac1b}\leq\frac{n+a}n$ is to raise both sides of $c_1n^b \leq (n+a)^b$ to the power of $\frac 1b$.)
Since $c_1$ is a positive constant, $(c_1)^{\frac1b}$ is also a positive constant. To make the above inequality hold, we would like to make $\left|\frac an\right|$ small enough.  For example, we can require $\left|\frac an\right|\le \frac12$. That is why you see the following condition.
$$|a|\le\frac12 n$$
What is nice here is that we can reverse the above argument to obtain a wanted constant $c_1$. Note that it is just as fine if we choose a different condition such as $|a|\le\frac13 n$ or  $|a|\le\frac1{2019}n$ or infinitely many others.
If we start from $(n+a)^b \leq c_2n^b$, we could arrive at $|a|\le n$.

Are they derived from $0\le c_1n^b\le(n+a)^b\le c_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Yes, they are derived as you have just seen. You could say that they are general knowledge that helps solve this problem. You could also say that we just discovered some specific facts that help solve this problem.


Merge sort: sorting and merging complexity $\Theta(n)$

Each iteration of merge sort consist of 2 phases:

Merge Sorting the first and the second half separately.
Merging the two halves.

So in your equation phase 1 is represented by $2T(n/2)$. This means that merge sort is called on the two halves. This is a recursive call, which is why $T$ is used here.

Phase 2 is represented by $\Theta(n)$. Merging two lists of length $a$ and length $b$ takes $\Theta(a+b)$. In our case the two lists are both of size $\frac{1}{2}n$, so we get a total of $\Theta(n)$.

In the end we get that $T(n) = $ step 1 + step 2, resulting in
$T(n) = 2T(n/2) + \Theta(n)$


Try to undestand how the algorithm is supposed to work, and write your own, clean/consistent pseudocode (or directly Python) from it.

You already searched for implementations, look for comments on this paper. You might find corrections published elsewhere...

It is unlikely, but possible, that the given pseudocode or even the proposed algorithm itself is wrong. Mistakes happen.


I think you are confused about which algorithm he is describing. His description isn't for algorithm 2 but for algorithm 4, where an imaginary index i in reintroduced.

Let me write this algorithm with this index to make it clear to you:

maxSubSum(array a):
  maxSum = 0, thisSum = 0;
  i = 0;
  for j going from 0 to length(a)-1:
    thisSum += a[j];
    if thisSum > maxSum:
      maxSum = thisSum;
    else if thisSum < 0:
      i = j+1;
      thisSum = 0;
   return maxSum;

Now you can see that in this algorithm, whenever thisSum < 0, then j is indeed the "first index that causes the subsequence starting at index i to become negative", and the rest of the claim follows. Notice in particular that the example you gave cannot occur with this algorithm (you will never have i=0 and j=3 in that case).


Real-time systems and real-time operating systems

A system is several things working together. A real time system might include computer hardware and software. Depending on where you draw the line it might include sensors and actuators reaching into the "real" world (sorry for the pun ). The software might include an operating system, or not.

A realtime operating system is a set of software components with the purpose of making it easier for you as a programmer to write the application software of a real time system. Typically the OS helps in handling hardware and dividing the processor among several tasks. It could include tools used to create the system, to find bugs and to measure performance. This is a kind of software reuse, and I tend to think of it as "me beeing a midget, standing on the shoulders of the titans previous to me".

A real time system can loosely be defined by the statement "even if the response is correct, if it is too late it is as bad as if it was wrong". The concept of too late is the major concept in a real time system. This could be on a time scale of pico- or microseconds (sort of difficult with software), milliseconds or seconds (typical realtime areas) or even minutes, hours, days or years (probably not called realtime, but could be).

Often a real time system includes some mechanism to handle serious errors. The concept of fail-safe is often used. As example, even if the software stops totally, or part of the hardware becomes unserviceable, some hardware function in the system turns outputs to a safe state and maybe restarts the software. Another exemple might be that cars with computer controlled ignition and fuel injection has a special "limp-home" mode allowing you to do something useable even when some of the sensors are broken. Here the computer might be working, but not all parts of the system.

When human life is at risk, say in space exploration, the fail-safe solution might include running several computers in parallell and turning off suspicious ones using external hardware. The space shuttle is a famous example with several computers running in parallell and special hardware selecting to kick out erraneous ones. In addition there was a special fallback computer, using different hardware and software written by a different team to handle if the main computers would go totally off.


Finding maximal independent sets in an independence system

This looks equivalent to finding all maximal zeroes of a monotone function, given ability to make oracle queries to the function.  Let $f:\{0,1\}^n \to \{0,1\}$ be a monotone Boolean function, and call $x$ a maximal zero if $f(x)=0$ and $f(y)=1$ for all $y\ge x$ (i.e., $y_i \ge x_i$ for all $i$).

This problem has been studied extensively.  I believe there are no known polynomial time algorithms.  See https://cstheory.stackexchange.com/q/14772/5038, Maximal Elements in a Lower Set, https://cstheory.stackexchange.com/q/18047/5038,
How to enumerate minimal covers of a set, and https://cstheory.stackexchange.com/q/14772/5038.  I think the concepts of learning DNF representations for monotone boolean functions and monotone dualization will be relevant. I confess I don't fully understand the literature and don't know if there are any algorithms that are good-enough-in-practice.

The relationship: Suppose $\Omega=\{1,2,\dots,n\}$.  We can identify the set $A$ with its characteristic vector, which is an element of $\{0,1\}^n$.  Now an independence system $I$ determines a function $f$ given by $f(A)=0$ if $A \in I$, otherwise $f(A)=1$.  You have oracle access to $f$, and want to find all maximal sets $A$ such that $f(A)=0$.


Why does packet data don't need trailer/footer while frame needs it?

OSI Layer 2 is usually tasked with getting the information from the upper layers, provided in octets (bytes), into bits suitable for sending over the physical link (OSI Layer 1). On the receiving side, the bits need to be converted back into bytes.

Links do not usually have the nice property of sending an exact sequence of 0 and 1. There is timing to consider (e.g. on a TTL line, scan the voltage n times per second). shifting (especially in parallel lines), bit damage, etc. Also, on asynchronous lines (most ones, except ATM (asynchronous transfer mode), textbook example for a synchronous protocol, always makes me smile), there are periods of no data transfer. This means that the sender and recipient somehow have to signal beginning and end of “transfer blocks”.

This is all rather difficult, so the frame header and trailer do not necessarily have to be full numbers of 8-bit blocks. They often include some easily-recognised bit patterns, such as a large-ish number of either all-zeroes or all-ones, followed by a toggle sequence such as 010101, and only then followed by data; this allows the recipient to synchronise on the sender better. Even DCF77 works like that, so receivers can synchronise to the exact beginning of a minute.

Going further, Layer 2 switches often operate in “fast pass-through mode”, in which they only need to have received the header (containing the target (and often source) address) to decide where to send the frame, not needing to fully buffer the entire frame for this decision, leading to faster throughput (less latency). On the other hand, the sending side may, indeed, wish to calculate the checksum on the fly and append it, in the trailer, which is only needed on the recipient side, not on the switches in between. This all allows for cost reduction in hardware.


Your problem is NP-complete.

It is a multidimensional generalization of the subset sum problem.  The input to subset sum is a list of integers $a_1, \dots, a_n$ and a target $t$.  The question is whether there's some sublist of the integers whose total is $t$.  This corresponds to the case where your shopping list is just "$t$ apples" and each package on the shelf contains some number of apples.

Having multiple products for sale in the shop certainly can't make the problem any easier.  But it doesn't get any harder, either: it's still in NP because, as you've observed, if somebody tells you "buy this set of packages", you can easily check in polynomial time that this gives you exactly what you want.


algorithm that removes extraneous connections from a graph

You describe the graph as

$V$ - a set of vertices
$E$ - a set of edges, where each edge is (presumably) an unordered pair.

To determine where you can go from each vertex $v \in V$, you need to scan the whole of $E$, so you are already $\Theta (|V| + |E|)$.

If the graph is in the form ...
$$ V \rightarrow 2^V$$
... then you can find a spanning tree in $\Theta(|V|)$. To enumerate the edges left out, you are up to $\Theta (|V| + |E|)$ again. But if you don't need to enumerate them, you can determine whether any given edge is spare in constant time.

Correction

  If the graph is in the form $ V \rightarrow 2^V$, then you can find a
  spanning tree in $\Theta(|V|)$.

I think this is wrong. Whatever your search order, at each vertex you have to look through the neighbours to find an undiscovered one, which might be the last. Depending on the structure of the graph, this might happen at every vertex. So the worst case at least is $\Theta (|V| + |E|)$.


what does "vector" mean in computer science?

Vector here is essentially the same as string, sequence, or array, with the possible connotation of having fixed length.

Here is another way to express the same idea:

  Computer hardware operates on bits. Therefore we have to encode all data in bits before a computer can process it.


Advantages of Lambda calculus over Turing machine and vice versa

The lambda calculus and Turing machines are equivalent models of computation, each of which formally captures the informal notion of effective calculation (this is the Church-Turing thesis). The lambda calculus is a more abstract and algebraic approach, whereas Turing machines offer a more concrete, algorithmic approach.


Time Complexity of inserting a vector to a vector of vectors in C++

First tings first:
Line X does a copy subs[i] and creates a new vector.
In terms of vector length $n$ this step is $O(n)$.
Line Y is amortized O(1). (The vector might need to reallocate making it O(n) in the worst case; to avoid reallocation see @MSalters post.)
The runtime of the whole procedure is a bit more difficult.
At the $i$-th number subs contains every possible subset of all numbers so far.
Thus length of subs $=2^i$, but we are interested in how many numbers we need to copy. this can be calculate with the sum of all subset sizes which is $i2^{i-1}$ (meaning at step $i$ we have to copy $i2^{i-1}$ numbers and make $2^i$ push operations).
$$O\left(\sum_{i=0}^{n-1} i2^{i-1}+2^i\right) = O(n2^n)$$
The complexity on the right makes sense, all sizes of all vectors in subs will be $n2^{n-1}$ in the end.


Turing-unrecognizable language - what TM does?

You might be a little confused by a definition somewhere.  A TM $M$ is a recognizer for a language $L$ if it

Accepts every string in $L$
Either rejects or loops on every string not in $L$

Now let's think about the language ${\overline{A_{TM}}}$.  An input $\langle N,x\rangle$ is in ${\overline{A_{TM}}}$ if either:

$N$ rejects on $x$.
$N$ loops on $x$

So any recognizer will need to figure out (in finite time) that $N$ is going to loop on some input, which is just the halting problem.


What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an $O(n^2/(\log n/\log\log n)^{3/2})$ algorithm (there were improvements since).
The statement "problem X requires time $n^{2-o(1)}$" states that there exists a function $f(n) = o(1)$ such that any algorithm for X runs in time at least $n^{2-f(n)}$. In particular, there is no $O(n^{2-\epsilon})$ algorithm, for any $\epsilon > 0$. The converse should also hold, I believe – could be a  fun exercise to show.


Stronger versions of P != NP which better express actual convictions

Considering that the conviction "P != NP is incredibly hard to prove" is largely based on known barrier results, one promising approach (for answering this question) would be to look for a statement expressing a natural separation, and ask why it is hard to prove. Then one can check which of the known barrier results for P != NP can be extended to that statement.

The question "Why is it hard to prove ALogTime != PH?" should be most promising in this respect. This statement is weaker and more natural than "L-uniform NC1 != NP", because $\subset$ PH and

  ALogTime = DLogTime-uniform NC1 = $U_{E^*}$-uniform NC1 $\subset$ L-uniform NC1.

For the relativization barrier, it would be enough to show ALogTimeA = PHA for  A := TQBF, where TQBF is the PSPACE-complete problem to decide true quantified Boolean formulas. No idea whether the natural proofs and the algebrizing proofs barrier should be expected to carry over, but at least checking whether they do should not be terribly difficult.

I also wonder whether the statement "ALogTime != PH" points to the right place where the difficulties for proving separation results start. Below ALogTime, we have the logarithmic time hierarchy LH, which probably doesn't collapse either, but the question is whether this has been proved (or whether this is relatively easy to prove, just in case nobody cared yet).

Edit: It turns out somebody actually cared to prove that the logarithmic time hierarchy is strict, and how it is related to the AC0 hierarchy. See Searching Constant Width Mazes Captures the AC0 Hierarchy by Barrington et al. I didn't check which results were already proved in one of the references, and which results have been proved for the first time in that paper.

This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH". Observe that (it seems that) coNLogTime verification can be used instead of PTime verification when characterising NP, so this is actually really equivalent to a statement where "polynomial time" no longer occurs, only some version of "read only polynomial length witness string".


Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$

It means "open" the recursion.

For simplicity - denote $O(n)$ as $c\cdot n$:

$$ \begin{align}
T(n) &= 2T(n/2) + cn \\
&= 2(2T(n/4) + cn/2) + cn\\
&= 2  (2  (2T(n/8) + cn/4) + cn/2) + cn\\
& \vdots
\end{align}$$

It might give you intuition, but it is NOT a proof. To prove it, you will need mathematical induction or the master theorem.

Proving with induction (assuming O(n) component  is n for simplicity):

Claim: T(n) <= n*logn + n

Base:
T(1) = 1 (assumption)

Assumption: the claim is correct for all k < n.
Proof:

T(n) = 2T(n/2) + n = (assumption) <= 2* (n/2 * log(n/2) + n/2) + n
     = n*log(n/2) + 2n = n*(log(n)-log(2)) + 2n = (assuming base 2 for log)
     = n*(log(n) -1 ) + 2n = nlogn -n + 2n = n*logn +n

QED


Why does the following Backus-Naur form reflect the following syntax diagram?

< number>::=< digit > | < digit >< number > means that a number is either just a digit, or a digit followed by a number. So 1 is a number (just a single digit), and 12 is also a number (a single digit, followed by a number that consists of just the single digit '2'). Similarly 123 is a number that consists of a single digit '1' and a number (that itself consists of a single digit '2' followed by a number (that consists of the single digit '3')).


You can build a block cipher with any desired block size, using a method called "format preserving encryption".  The block size doesn't have to be limited to 64 bits or 128 bits.  This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.


How long does it take to crack a password by brute force

Perhaps your teacher was talking about some system where the format of passwords is restricted (e.g., where they can't be longer than whatever number of characters allows a typical computer to try all combinations in 21 days).  Or perhaps they were talking about some specific kind of password, such as words from the dictionary, maybe with c0mm0n m0d1f1c4t10n5.

In general, it's impossible to give a limit because passwords could be arbitrarily long. Indeed, even without needing crazy-long passwords, there are $62^{10}\approx 10^{18}$ possible ten-character passwords that can be made from numbers and upper-case and lower-case letters.  If you can try a billion passwords a second, it'll still take you a billion seconds to try all of these passwords, and that's about 32 years.

Note that the above discussion ignores the fact that, in reality, we don't guess passwords but, instead, guess strings that have the same hashes as passwords.  At the level we're talking about here, though, this doesn't make any real difference.


For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$

Assume that all languages are over the alphabet $\Sigma$. What you have here is a bit of ambiguity in the meaning of $\emptyset$ (recall that the emptyset is defined w.r.t a universal set, and here $\emptyset$ is used w.r.t different universal sets). Indeed, $S = \{ \emptyset\}$ refers the set of languages containing only the empty language, that is,  in this case, $\emptyset\subseteq \Sigma^*$. Also, $S = \emptyset$ refers to the empty set of languages, that is, in this case $\emptyset\subseteq 2^{\Sigma^*}$.
As you noted, if $S = \emptyset$, then $L_S = \{ \langle M\rangle: L(M)\in \emptyset\} = \emptyset \in \text{R}$. Now if $S = \{ \emptyset\}$, then $L_S = \{ \langle M\rangle: L(M)\in \{\emptyset\}\} = \{ \langle M\rangle: L(M) = \emptyset\} = E_{TM}$ which is known to be in $\text{coRE}\setminus \text{R}$.


Work backwards, from right to left.
Try to find which strings of the form $a^*$ belong to $L_1/L_2$. So find matches of strings $w_1\in L_1$ and $w_2\in L_2$ such that at the start only a string of the form $a^*$ sticks out: $w_1= a^k w_2$.


Design a Turing machine that accepts L={ww^r | w:(0,1)*}?

This can be done with a PDA or a TM. I'll assume you need a deterministic TM, for what I'm assuming is homework.

The strategy is to find the length of the string to determine where the middle is, then treat the tape as a stack to see if all of the characters match before and after that midpoint.

Here's an algorithm that can do it:

For every two input characters you read until you hit #, write a 0 after the last #. This will keep track of where the "middle" is. Mark the inputs as you read them.
If you hit # where you expected to find a number, the string length is odd, and so the machine can halt and reject.
Otherwise, write another # after your string of zeros.
Unmark all inputs and move the read head to the second #.
Using the number of zeros you have, mark the right half of the input.
Starting in the middle, working your way out, mark the left character and unmark the right if they match.
If you encounter a pair that doesn't match, halt and reject.
If you get all of the way to the #s, halt and accept.

For example, let's look at input #101100# (# here means the edges of the input). The read head is at the first #.

Input starts as # 1 0 1 1 0 0 # (leaving room for markers)
Mark the first two inputs, write a 0 at the end: # 1'0'1 1 0 0 # 0
Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0 0 # 0 0
Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0'0'# 0 0 0
You've found the second #, so the string is of even length. Write a # at the end: # 1'0'1'1'0'0'# 0 0 0 #
Unmark everything: # 1 0 1 1 0 0 # 0 0 0 #
Now, starting from the second #, mark the inputs from the right, and the 0s from the left until all of the 0s are marked:
First iteration: # 1 0 1 1 0 0'# 0'0 0 #
Second: # 1 0 1 1 0'0'# 0'0'0 #
Third: # 1 0 1 1'0'0'# 0'0'0'#
You now know the midpoint of the string (it's where an unmarked input is to the left of a marked input).
Starting from that midpoint, mark the left and unmark the right if they match:  # 1 0 1'1 0'0'# 0'0'0'#
Continue working outward, comparing in this way: # 1 0'1'1 0 0'# 0'0'0'#
On the third step, we find that 1 and 0 don't match. Halt and reject.

I'll leave it as an exercise to you to determine how to convert this algorithm into a TM.


Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

First, be careful what Vazirani actually says. On page 38, it is written that:

  "The minimum $k$-cut problem is polynomial time solvable for fixed $k$; however, it is NP-hard if $k$ is specified as part of the input."

(In particular, the claim you make about being NP-hard for any fixed $k \geq 3$ holds for a different problem, namely minimum weight multiway cut). Indeed, Wikipedia states this is the case as well: for any fixed $k$, you can solve the minimum $k$-cut problem in $O(n^{k^2})$ time. In other words, when $k$ is fixed, you have polynomially many ways of removing $k$ edges. So why does it matter if something is part of the input or fixed then?

When $k$ is fixed, it is not part of the input. The problem is this:

  (Minimum $k$-cut.) Input: A graph $G$. Question: Is there a $k$-cut?

So the problem is defined for every fixed value of $k$. We have minimum 2-cut, minimum 3-cut, minimum 4-cut, and so on. In contrast, the problem could be this:

  (Minimum cut.) Input: A graph $G$, an integer $k$. Question: Is there a $k$-cut?

Now, it is possible for $k$ to depend crucially on the size of the graph. This way a naive brute-force won't give you a polynomial time algorithm. Another example is given in this question of ours in the context of finding cliques.


How to avoid column wise access in matrix multiplication?

I'm assuming you don't want to store a copy of the second matrix in column-wise order and then multiply. In this case maybe the best way is to take the most advantage of cache hierarchy in modern CPUs. There are many complexity results for such setting.

For matrix multiplication there is a cache-oblivious algorithm based on Strassen's algorithm. Here you can find it in details. Notice that their aim is to optimize I/O access, so it may not fully match your requirement.


Your problem is known as hypergraph 2-colorability; the hypergraph has $U$ as vertices and the neighborhoods of vertices of $V$ as edges. Determining whether a hypergraph is 2-colorable is NP-complete.


Your first generalisation is wrong, it depends on what's the complexity of loop content. However if that 'some code' is of constant complexity [something like $O(1)$], the whole complexity will be $O(n)$.

Your second example is correct.