Relevance of memory reads while calculating the time complexity of an algorithm

For a memory read to be relevant to the algorithm, the information read in must be processed in some way.
If the information is never compared or used as input to any operator, it will not affect the algorithm and thus was unnecessary to read in the first place.
If there were an operator that could accept a variable number of inputs, a number that could grow without bounds, then and only then could you have the number of memory reads far outnumber the number of operations in the way you describe.  For instance, if "sum" were a single atomic operation accepting any number of inputs, then you could have such an algorithm.
However, a model of computation where a single operation could utilize an unlimited number of inputs is not very interesting nor very useful for algorithmic analysis.  It would essentially just push all the hard work to a lower level of abstraction.  So you won't find such a model in any CS literature.

A paragraph from an MIT Open CourseWare PDF about communication networks as in Graph Theory makes a related point (related to what I said about just pushing the hard/interesting work to a different level of abstraction) in discussion of switch sizes:

One way to reduce the diameter of a network (and hence the latency needed to route packets) is to use larger switches. For example, in the complete binary tree, most of the switches have three incoming edges and three outgoing edges, which makes them $3 \times 3$ switches. If we had $4 \times 4$ switches, then we could construct a complete ternary tree with an even smaller diameter. In principle, we could even connect up all the inputs and outputs via a single monster $N \times N$ switch, as shown in Figure 6.9. In this case, the “network” would consist of a single switch and the latency would be $2$.
This isn’t very productive, however, since we’ve just concealed the original network design problem inside this abstract monster switch. Eventually, we’ll have to design the internals of the monster switch using simpler components, and then we’re right back where we started. So the challenge in designing a communication network is figuring out how to get the functionality of an $N \times N$ switch using fixed size, elementary devices, like $3 \times 3$ switches.


Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?

Multiplication can inherently be computed faster than division because it parallelizes better.

If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.

ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.

In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.

If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta_y}{\Delta_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$).
More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,

$$y=\left\lfloor\frac{\Delta_y}{\Delta_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta_yx+\Delta_x\epsilon}{\Delta_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.

The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta_y$ to the remainder, or increment the quotient and add $\Delta_y-\Delta_x$ to the remainder).

When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in fixed-point arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.

$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=[2^n\Delta_y/\Delta_x]$ and $e=[2^n\epsilon]$. The "division" is implemented with a fast shift.


Turing machine with "move to origin" instead of "move left"

When you want to move one position to the left, execute the following algorithm:

Mark the current position as special.
Move to the origin.
Translate the tape one cell to the right, while keeping the special marker in place.
Move to the origin.
Scan until reaching the special marker.
If you move to the right, don't forget to erase the special marker.

(This simulates a Turing machine with a single two-sided tape.)


will this be decidable or partially decidable?

The language is clearly not decidable; use Rice's theorem. See e.g. our reference question.

We can certainly simulate $M$ on every input by dovetailing and count accepted inputs; if $|L(M)| \geq 3$ our counter hits three after finite time and we accept, otherwise we loop. Therefore, $A$ is semi-decidable.


Can an FO formula with infinite length be expressed with an infinite set of finite formulas?

You are getting at infinitary (first-order) logic. While a well-defined (and natural, and extensively studied) concept, it is quite different from ordinary first-order logic. Before diving into more detail, let me point out the main issue with your suggestion:

  There are "infinitely long" expressions which aren't just infinite conjunctions of finite expressions.

That is to say, your idea

  Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

is incorrect. One way to see this is with the compactness theorem. For example, suppose I had a set $\Gamma$ of (finitary) first-order sentences which expressed connectedness. Then consider the expansion of $\Gamma$ to include sentences saying "$c$ is at distance at least $n$ from $d$," for each natural number $n$, where $c$ and $d$ are new constant symbols. By the usual compactness argument, this has a model, but (the reduct of) this model isn't a connected graph; contradiction.

The usual manipulations we perform with finitary formulas don't behave intuitively in general when we look at "infinitary" formulas, and in fact infinitary logic (see below) is a very different beast from its finite counterpart.

Having said what infinitary logic isn't, let me end by saying a couple sentences about what infinitary logic is.

For a start, let's look at the simplest nontrivial example: $\mathcal{L}_{\omega_1,\omega}$. This is smallest class containing all first-order formulas, closed under (a) quantifiers and (b) countably infinite conjunctions and disjunctions. This logic is much stronger than first-order logic - for example, connectedness (in the language of graphs) is definable by an $\mathcal{L}_{\omega_1,\omega}$-formula, namely

$$\forall x,y[\bigvee_{n\in\mathbb{N}}\exists z_1,...,z_n(z_1=x,z_n=y, z_1Ez_2E...Ez_n)].$$ This is a relatively simple infinitary formula, and there are much more complicated ones we can consider; there is a rich (and non-collapsing) hierarchy of infinitary formulas, and in fact many fragments of $\mathcal{L}_{\omega_1,\omega}$ of mathematical interest (see e.g. this paper for a good starting point).

We can go beyond $\mathcal{L}_{\omega_1,\omega}$ by either allowing longer Boolean combinations, or infinitely long blocks of quantifiers, but as we go further up the hierarchy of infinitary logics things get progressively much nastier. $\mathcal{L}_{\omega_1,\omega}$ is quite abstract, but still "concrete" enough to be relevant outside of infinitary logic - see e.g. the notion of a Scott sentence, which is useful in computability theory, classical model theory, and set theory.

There are several texts on infinitary logic; I recommend Marker's recent book as a good starting point, and Barwise's old book for a more in-depth treatment of the "local" flavor.


You can show that $L$ is regular by using an NFA. Briefly, the NFA is going to simulate DFAs for $A$ and for $B$, guessing the decomposition of the input into $x \oplus y$ as it goes. The same works for any other operation such as AND and OR.

In more detail, suppose that we are given DFAs for $A,B$:

Sets of states $Q^A,Q^B$.
Initial states $q_0^A,q_0^B$.
Final states $F^A,F^B$.
Transition functions $\delta^A,\delta^B$.

We construct an NFA for your language $L$ as follows:

Set of states is $Q^A \times Q^B$.
Initial state is $\langle q_0^A,q_0^B \rangle$.
Final states are $F^A \times F^B$.
Transition function is
$$
\begin{align}
&\delta(\langle q^A,q^B \rangle, 0) = \{\langle \delta^A(q^A,0), \delta^B(q^B,0) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,1) \rangle \}, \\
&\delta(\langle q^A,q^B \rangle, 1) = \{\langle \delta^A(q^A,0), \delta^B(q^B,1) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,0) \rangle \}.
\end{align}
$$
You can prove inductively that
$$
\delta(\langle q^A,q^B \rangle, w) = \{ \langle \delta^A(q^A,x), \delta^B(q^B,y) \rangle \mid x \oplus y = w \},
$$
from which the correctness of the construction easily follows.


Why does the neural network logistic regression cost function sum for all layers only for lambda?

The first term depends on the output of the entire network, i.e., on all the parameters for all layers, not just a single layer's parameters.

This is an application of the empirical risk minimization framework for training a classifier, with regularization.  The cost function $J(\Theta)$ has the form

$$J(\Theta) = \text{empirical risk} + \text{regularization penalty}.$$

Denote the empirical risk by $R(\Theta)$; it depends on the parameters $\Theta$ (for all layers).  Denote the regularization penalty by $P(\Theta)$; it depends on the parameters $\Theta$ (for all layers).

The empirical risk $R(\Theta)$ is the sum of the loss for each instance in the training set, i.e., it has the form

$$R(\Theta) = {1 \over m} \sum_{i=1}^m \ell(h_\Theta(x^{(i)}), y^{(i)}),$$

where $\ell$ is a loss function, $x^{(i)},y^{(i)}$ is the $i$th instance in the training set, and $h_\Theta(x)$ denotes the output of the classifier on input $x$ when the parameters are $\Theta$.  Note that the output of the classifier depends on all the parameters for all the layers, so $R(\Theta)$ depends on all the parameters for all layers (not just a single layer).

A comment on notation: We use $\Theta$ to denote all of the parameters, i.e., a single vector that concatenates the parameters for each layer.  Here it appears $\Theta^{(l)}$ has been used to denote the parameters for the $l$th layer, so $\Theta = (\Theta^{(1)}, \dots, \Theta^{(L)})$.

In your specific example, we use the cross-entropy loss for $\ell$ (this is also known as the logistic loss function, where there are only two classes).  That's how we get the first term.

Also the regularization penalty $P(\Theta)$ depends on all of the parameters, for all layers; it is a sum of penalties for each layer.

If you work through the math, you'll see how we get something of the form you've shown in the question.  As this answer hopefully makes clear, each term depends on the parameters for all the layers, not just a single layer.


Looking for an algorithm to solve a specific Vehicle Routing Problem

A metaheuristic would do. I would opt for a Large Neighbourhood Search (LNS), a Genetic Algorithm (GA), or Tabu Search (TS).


proving that $P\ne NP$ under an assumption

Here is a more direct proof. Suppose that $P=NP$. In particular, SAT can be solved in polynomial time. Therefore $P^{SAT} \subseteq P^P = P \subseteq coNP$.


Injectivity verification in o(n) space and O(n) time

You haven't specified your exact computation model, so let me assume that you measure space in words of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.

The oracle should provide you with the relative order of the elements, say as an array $B$ whose entries are the numbers $1,\ldots,n$ in the appropriate order. This advice takes $O(n)$ words, and can be verified in $O(n)$ time and $O(1)$ additional space.

In slightly more detail, here is the verification algorithm:

for i from 1 to n:
  verify that 1 ≤ B[i] ≤ n
for i from 2 to n:
  verify that A[B[i-1]] < A[B[i]]

Let us prove that  there exists an array $B$ for which the verification succeeds iff $A$ consists of distinct elements.

$\longleftarrow$ Suppose that $A$ consists of distinct elements. Order $A$ in increasing order: $A[j_1] < \cdots < A[j_n]$. If we take $B[i] = j_i$ then the verification will succeed.

$\longrightarrow$ Suppose that the verification succeeds for some array $B$. Then $A[B[1]] < \cdots < A[B[n]]$. This implies that $A$ contains at least (and so exactly) $n$ distinct elements.


What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) polynomial with the property that that a solution exists precisely when the polynomial is not identically zero.

[1] Björklund, Andreas. "Determinant sums for undirected hamiltonicity." SIAM Journal on Computing 43.1 (2014): 280-299.


Proving time-complexity analysis for merge-sort-like algorihtm

There is no reason to calculate a closed form solution to this recurrence. Indeed, this is not even possible, due to the following reason:

$O(n)$ is not a closed form function. It just signifies that the recurrence holds with $O(n)$ replaced by some function $f(n)$ which belongs to the class $O(n)$.
It is not clear what happens when you plug in $n$ which is not divisible by 4.
A related issue is that there are no initial conditions - the recurrence seemingly never bottoms out.

Any reasonable way to address the latter two concerns will lead to a recurrence which is amenable to the Akra–Bazzi method. According to this method, we first need to calculate the value of $p$ satisfying
$$ (1/4)^p + (3/4)^p = 1. $$
The solution to this equation is $p = 1$. The asymptotic solution is then
$$
T(n) = O\left(n\left(1 + \int_1^n \frac{O(u)}{u^2} \, du \right)\right) = O(n\log n).
$$


Method for finding correlation between data sets

Let's start with comparing two time series.  To compare them, you probably want to use cross-correlation.  The cross-correlation computes the correlation between signal $f$ and a delayed version of signal $g$, for all possible delays.  An efficient way to compute the cross-correlation is indeed by using a FFT, taking the product, and then applying an inverse FFT.

Now suppose you have $k$ time series.  I think the best you can do is to compute the cross-correlation between each pair of time series.  This requires ${k \choose 2}$ cross-correlation computations.


Wanted: Concrete Example of Busy Beaver Holdout

Skelet has 43 holdouts (those with type = ----).
At least No. 827123 (the very first in the lists) is still open, afaik.
My "feeling" is that all but 6 (no idea, which!) have been shown to be infinite.
Good luck!
http://skelet.ludost.net/bb/nreg.html
No info on actual holdouts, but state-of-the-art in several aspects:
https://www.scottaaronson.com/papers/bb.pdf
These are the 43 holdouts according to Skelet:
Nonregular machines:
    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |

    C1L E1L  H1L D1L  D1R D0L  A1L E1R  B0L C0R  |   827123 |
    C1L E0R  H1L C0R  D1R A0L  A1R D1R  A1L B0R  |  1668912 |
    C1L A0R  H1L E1L  D1R B0L  A1R C1R  C0L D1L  |  2523420 |
    C1L D0R  H1L E0L  D1R C1L  E1L A1R  B1L D0L  |  3911891 |
    C1L A1L  H1L D0L  D1R E0L  A1L C0R  C1R B0L  |  6311798 |
    C1L B0R  H1L D0R  D1L A0R  E1R C0L  C1R E1R  |  7224038 |
    C1L B0R  H1L E1R  D1L A1L  A1R D0L  A0R C1R  | 11799516 |
    C1L B0R  H1L C0R  D1L C0L  E0R C1L  A0R E1R  | 11997798 |
    C1L D1R  H1L C0L  A1R C1L  E1R A0R  B1L E0L  | 18119527 |
    C1L A0L  H1L C0L  D0R A1L  B1L E1R  D1R E0R  | 21181509 |
    C1L A0L  H1L A0R  D0R A1L  E0R D1R  A1L B0R  | 22109761 |
    C1L E0L  H1L E1L  D0R A1L  A0L C1R  C1R B0L  | 22600133 |
    C1L B0R  H1L A1R  D0L E1R  E0R C1L  C1R A0R  | 25621006 |
    B1L H1L  C1R E0R  D1L B0R  D0L A1L  C0R A0L  |  5359517 |
    B1L H1L  C1L B1R  D1R E1L  B1R D0R  A1L C0L  |  6594274 |
    B1L H1L  C0R D1L  D1R C1R  E1L E0L  A0L B0R  | 11530505 |
    B1L H1L  C0R E1L  D0R C1R  A1L B1R  B0L A0L  | 11679832 |
    B1L H1L  C0L D0R  D1L E0R  E1L A0L  C1R D0R  | 14576100 |
    B1L H1L  C0L B0L  C1R D0R  A1L E0R  A0R E0R  | 15076017 |
    B1L H1L  C0L D1L  D0R C1L  E1R A0L  A1L E0R  | 15764213 |

    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |

    C1L E1L  A1L H1L  D1R E0R  B1R E1R  C1R A0L  |   123831 |
    C1L E0L  A1R H1L  D1R A0L  D0R B1R  C0L B0R  |  3198755 |
    C1L C0R  D0L H1L  D1R E0L  C1L E0R  A1R B1L  |  5585454 |
    C1L A1L  E1R H1L  D1R D0R  B0R E0L  A0L C1R  |  6314131 |
    C1L A0R  A1L H1L  D1R E1L  A1R D0R  E0L B0R  |  6929003 |
    C1L E1R  D1R H1L  D1L C0L  A1R D1L  B1R A0R  | 12568936 |
    C1L E0L  D1R H1L  B1L E1L  A1R E1R  A1L D0R  | 17982461 |
    C1L D0R  A0L H1L  A1R D0L  E1R B1L  C1L C0R  | 23741566 |
    C1L E0L  C1R H1L  D0R A1L  A1R E0R  B1R E0L  | 30515821 |
    C1L B0R  E0R H1L  D0L C1L  E1L C0L  A1R C0R  | 33424333 |
    C1L E0R  C0L H1L  D0L B0L  D1R A0R  A1R D1L  | 33938206 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R E1L  | 34364505 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A1L  | 34429669 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A0R  | 34508331 |
    C1L E1R  D1R H1L  D0L C0L  B1R A1L  D1L A0R  | 34605254 |
    C1L B0R  C1R H1L  D0L D0R  A1R E0L  D1L E1L  | 36278670 |
    C1L C0L  D1L H1L  B0L D0R  E0R A1L  A1R E1R  | 40470734 |
    B1L D1L  C1R H1L  E1R D1R  E1L C0R  A1L D0L  | 43710027 |
    B1L A0L  C1R H1L  C0R D0R  E1L B0L  E0L A1L  | 45963385 |
    B1L A0R  C1L H1L  D0L E1R  E1L A0L  C1R A0R  | 50233205 |
    B1L E0R  C1L H1L  D0L C0L  D1R A0R  B0R E0R  | 50317033 |
    B1L A0R  C0L H1L  C1R D1L  E1L A1R  B0L D0R  | 54769539 |

This page was last modified at 16 May 2003.
(c) Skelet, May 2003 in terms of GNU GPL


Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?

why would one want to allow multiple occurrences of a same vertex in the stack

For general remarks, I can only guess here since I can't read the minds of others.

A recursive method incurs quite some cost for managing registers and the (call) stack; an explicit stack may be so much faster that, usually, the iterative method is faster even though it's worse on memory.

Saying "usually", keep in mind that your arguments are worst-case considerations. Depending on the graphs you're looking at, the actual behaviour may be very different. When you ask on Stack Overflow, you'll usually get practice-driven trade-offs: use what's faster in your setting.

  why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of O(|V|)

Because then you don't have DFS any more! We always want to follow the edge to a node that we discovered last. We have to keep track of the "older" edges with the explicit stack; the call stack remembers them for us by reference, thus saving the memory.

If you are very concerned about memory consumption -- which, depending on your inputs, you may have to be! -- there are ways around keeping duplicates in the stack. Here is one idea.

For each node, store in an array not only whether it was already visited/handled, but also its position in the stack (either by pointer or index). If you add a node to the stack and that position is set remove the old stack entry, then push the new one.

Clearly, this keeps the stack at $\leq |V|$ entries. Also, if removing items from the middle of the stack is fast, it does not make the algorithm (much) slower -- the node will have to be removed either way. If not, then a new trade-off appears.


How does hash table search scales with number of keys?

In principle, they're similar in running time and space complexity.

In practice, the first one might have some modest advantages: possibly half as many accesses, less space overhead if some of the "secondary hashtables" were small (e.g., for a particular value of the first key, there aren't many possible second keys).

I would not expect to see a tremendous difference between the two, nor a difference in asymptotic worst-case running time.  Both have $O(1)$ expected running time for all major hash table operations, under some reasonable assumptions.


"Low-High" sort divide and conquer with merge... how small to make the subproblems for good efficiency?

My plan of attack is to simply try many different final block sizes such as 1024, 512, 256.... and just time them all. I chose a power of 2 block sizes cuz they can be halved in size easily without any fractions.  For testing purposes, I would force the array sizes to be a perfect power of 2 so they divide perfectly.  My goal is not a generic sorting algorithm but rather more of a divide and conquer optimization speed question.

So in array B, there would be sorted subarrays which I can then merge back into A, so the storage for this algorithm is roughly 2N.

Also regarding the merge part of this (or any sort using merge), why not just start with sorted arrays of size 1 and work your way up?  For example, if we had an array of size 1024, start by merging adjacent pairs of numbers, then merge those pairs into quads...


How to find every negative cycle in a graph

First of all, there can be exponentially many negative cycles, as @Steven already mentioned.  Take $K_n$ with only negative edges.  Enumerating all of them will be bound to take exponentially long time.
You also say that you want to find the most negative cycle in the graph (which should be simple if you enumerate them all), however, in case you want a special algorithm for this problem, note that this problem is NP-complete; the reduction from Hamiltonian is straight forward.
Since you ask for any algorithm, just run, for every subset of vertices, a DP algorithm to find the Minimum Hamiltonian Cycle for that induced subgraph.  (Since you don't want to revisit an edge, you can probably find a way to add $\min_{e \in E(G)} w(e)$ to every edge, thereby avoiding all the negativity.)
(P.s., OP stated in a comment that cycles on the same vertex set are considered equivalent.)


What is 'K' in the Bounded Post Correspondence Problem?

Suppose your list is M=(bba,ab,bba,a) N=(bb,aa,bb,baa) Then its equivalent tile representation is as follows

Now your pcp problem is equivalent to finding a sequence of tiles(repetition allowed) such that concatenating all upper halves and concatenating all lower halves gives you same string.
K here is nothing but number of tiles that can be used

Edit : As Yuval Filmus subtly mentions in his comment, there are many other interpretations of K. In an another formulation K can also be the maximum length of concatenated string, in which case the bounded PCP problem is Pspace complete. But usually many books refer to K as being number of tiles that are allowed.Please refer to Sipser book for more.


You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.


Method for Creating Any Unambiguous Grammar?

No, and there is indeed a reduction to the undecidability of ambiguity.

First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say "ambiguous!" when you first find a word you've seen before.

Now, the method you are proposing allows to semi-decide unambiguity. You effectively look for a computable enumeration of all unambiguous grammars. You just generate grammars until you find your given grammar and answer "unambiguous!".

Since semi-decidability and co-semi-decidability imply decidability, this contradicts what you already know. Hence, there can be no "set of rules" as you propose.


Priority queue with both decrease-key and increase-key operations

Assume you have a priority queue that has $O(1)$ find-min, increase-key, and insert. Then the following is a sorting algorithm that takes $O(n)$ time:

vector<T>
fast_sort(const vector<T> & in) {
  vector<T> ans;
  pq<T> out;
  for (auto x : in) {
    out.insert(x);
  }
  for(auto x : in) {
    ans.push_back(*out.find_min());
    out.increase_key(out.find_min(), infinity);
  }
  return ans;
}


Complexity of bitwise AND operation on bit string regular expressions

Formalism

Let me formalize your problem as follow.  Define a gegular expression as an expression that follows the following grammar:

$$E ::= 0 | 1 | E_1 E_2 | E^k,$$

where $k$ ranges over positive integers and $E_1,E_2$ range over gegular expressions.  Note that these are not regular expressions, as Yuval Filmus explains, even though they are related.

Obviously, each gegular expression codes for a single binary string.  If $E$ is a gegular expression, let $[E]$ be the binary string is codes for.  Also let $\text{len}(E)=\text{len}([E])$ denote the length of the binary string $[E]$.  Of course, these can be easily computed recursively: e.g., $\text{len}(E_1 E_2) = \text{len}(E_1) + \text{len}(E_2)$ and $\text{len}(E^k) = k \times \text{len}(E)$.

Given two gegular expressions $E_1,E_2$, the ultimate goal is to find a third gegular expression $E_3$ such that

$$[E_3] = [E_1] \land [E_2],$$

i.e., that represents the bitwise-AND of the bit strings that $E_1,E_2$ code for.  If this holds, we will write $E_3 = E_1 \land E_2$.  ($E_3$ may not be unique -- there may be multiple acceptable $E_3$ -- but we won't let this bother us.)

Helpful tools

Here are some little lemmas that are helpful.

First, if $E$ is a gegular expression and $\ell$ is a positive integer, we can compute a new gegular expression that codes for the first $\ell$ bits of $[E]$.  Define $\text{prefix}_\ell(E)$ to be this gegular expression.  We can compute $\text{prefix}_\ell(E)$ recursively using the following relations:

$$\text{prefix}_\ell(E_1 E_2) =
\begin{cases}
\text{prefix}_\ell(E_1) &\text{if $\ell < \text{len}(E_1)$}\\
E_1 &\text{if $\ell = \text{len}(E_1)$}\\
E_1 \; \text{prefix}_{\ell-\text{len}(E_1)}(E_2) &\text{otherwise.}
\end{cases}$$

$$\text{prefix}_\ell(E^k) = E^{\lfloor \ell / \text{len}(E) \rfloor} \; \text{prefix}_{\ell \bmod \text{len}(E)}(E).$$

You might notice that this does not increase the size of the gegular expression too much (at most a quadratic blowup, and usually much less).

Also, there are some special cases where your problem is easy.  For instance.

$$E_1^k \land E_2^k = (E_1 \land E_2)^k$$

if $\text{len}(E_1)=\text{len}(E_2)$.

If the exponents are not identical, we can reduce to the above case.  Let $E_1,E_2$ be two gegular expressions of lengths $\ell_1,\ell_2$, respectively (i.e., $\ell_i = \text{len}(E_i)$).  Let $m = \text{lcm}(\ell_1,\ell_2)$ be the least common multiple of their lengths.  Then

$$E^k = (E E \cdots E)^{\lfloor k/m \rfloor} E E \cdots E$$

holds for all $E,k,m$, where the first $E E \cdots E$ represents $m$ concatenations of $E$ and the second $E E \cdots E$ represents $k \bmod m$ concatenations.  Thus we have

$$E_1^{k_1} \land E_2^{k_2} =
(E_1 E_1 \cdots E_1 \land E_2 E_2 \cdots E_2)^{k_3} \;
\big( \text{prefix}_{\ell'_1}(E_1^{k_1}) \land \text{prefix}_{\ell'_2}(E_2^{k_2}) \big),$$

Also, if $\text{len}(E_1) = \text{len}(E'_1)$, then

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land E'_1) (E_2 \land E'_2).$$

If they are not of the same length, say $E_1,E'_1$ have lengths $\ell_1,\ell_2$ where $\ell_1<\ell_2$, then we can express their bitwise-AND as

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land \text{prefix}_{\ell_1}(E'_1)) (\text{prefix}_{\ell_2-\ell_1}(E_2) \land \text{tail}_{\ell_2-\ell_1}(E'_1)) (\text{tail}_{\text{len}(E'_2)}(E_2) \land E'_2).$$

(Here $\text{tail}()$ is defined analogously to $\text{prefix}()$, except it relates to the end of a string rather than the beginning.)

I think from these special cases, you should be able to build a recursive algorithm that computes the bitwise-AND of any two gegular expressions.


What algorithm do SVMs use to minimize their objective function?

The SVM problem (and other related problems) can be described as a minimization \ maximization of a quadratic function.
This can be easily solved with the gradient descent algorithm, however I recommend using the SMO algorithm since it is a direct solution (to the dual of the SVM problem), and can be also used for kernelized SVMs


Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem

The problem is equivalent to the Maximum Independent Set problem on the "bipartite complement graph" (take the complement graph and delete edges with both endpoints on the same side of the bipartition). Such an MIS is the complement of a Minimum Vertex Cover, which can itself be deduced from a Maximum Matching.
You can probably take it from here (with maybe a bit of googling for how to find a Minimum Vertex Cover in a bipartite graph).


Minimum pumping length of finite language

Let $w \in L$ be the longest string of the finite language $L$. Assume a pumping length $p \leq |w|$. This would imply $w = xyz$ with $|y| \geq 1$ and $xy^2z \in L$. Can you see the contradiction?
Having ruled out pumping length $p \leq |w|$, the minimal possible value for $p$ is indeed $|w|+1$, for which as you noted the conditions of the pumping lemma are trivially true.


When is relation in 3NF but not in BCNF?

"I think we can correctly interpret this condition as β−α are key attributes."

No. β−α is a set of attributes. What that statement is saying is,

Every attribute in that set is part of some (at least one) candidate key for the relation.

Also, if by 'key' attribute, you mean an attribute that is a superkey, i.e., an attribute whose value uniquely determines the tuple, then NO, every element in β−α is NOT a key attribute. It is just a prime attribute (in other words, part of some candidate key).

For example, if we write your schema as:

  Dept_advisor : {A, B, C},

then the FD's can be written as:

B → C (α = {B}, β = {C}, β−α = {C} - {B} = {C})
AC → B (α = {A, C}, β = {B}, β−α = {B} - {A, C} = {B})

Here, [1] is neither a trivial dependency nor is α (here, B) a superkey of the relation. In other words, none of the two conditions for BCNF hold for this FD.
For BCNF, you need all the FD's to satisfy at least one of the two conditions, but here you have one FD which satisfies none. So this schema is not in BCNF. You got this right.

Now, testing it for 3NF, you can confirm that both [1] and [2] satisfy at least one of the 3 conditions for 3NF. [2] satisfies the 2nd condition (α = {A,C} is a superkey), so we are good so far. [1] does not satisfy any of the first two conditions, which are also the conditions for BCNF. But, it does satisfy the third condition, i.e., each attribute in β−α (here, only one attribute, namely B) is part of some candidate key.

What candidate key is that, you ask? You can easily find one.

Take {A, B}. It is a candidate key because you have the FD B → C, which means {A, B} → {A, B, C} gives all the attributes of the relation, which means it is a superkey. But no proper subset of {A, B}, i.e., neither A nor B alone, are superkeys themselves. In other words, neither {A} → {A, B, C}, nor {B} → {A, B, C}. So yes, you got this one right too, but for the wrong reasons.

As for the other statement, about 3NF tables being dependent only on the "primary key", you are better off just ignoring it and sticking to the definition and trying to understand and use it correctly.


Find rectangle of minimum area where dimensions are larger than minimum

One simple solution uses k-d trees. In preprocessing, prepare a sorted list $L$ of $x_i y_i$ as well as a three dimensional k-d tree $T$ storing the points $(x_i,y_i,x_iy_i)$; this can be done in time $O(n\log n)$ and takes up space $O(n)$. Given $a,b$, we do binary search on $L$ to find the least $c$ such that $T$ contains a point $(x_i,y_i,x_iy_i)$ with $x_i \geq a,y_i \geq b,x_iy_i \leq c$; each such query takes time $O(n^{2/3})$, for a total query time of $O(n^{2/3}\log n)$.

It's not clear whether we actually need a three dimensional k-d tree; if a two dimensional one suffices, then the running time could get down to $\tilde{O}(n^{1/2})$.


An algorithm for topological sorting based on depth-first search: why do we need two tags?

Consider the following graph $G = (V, E)$ where
$$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$
If your example started at $1$, it will add $3$ to the list and then it will add $1$. In the next step the algorithm will choose $2$ as an unvisited vertex, which has an edge to a visited vertex $3$. Hence, It will conclude that the graph is not a DAG. However, the graph is a DAG and your algorithm is not always correct.

The reason why we need two kinds of marking is to distinguish cycles from components we already done in previous iterations. Reaching back to an ancestor in the recursion tree means that there is a path going back to a vertex we came from and hence a cycle. Meanwhile an edge to a vertex that is permanently marked (and hence was visited in a previous iteration) can never introduce a cycle, since else we would have reached the current vertex in the same iteration as well.


Does a context-free grammar with multiple variables have a "starting" point?

What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where:

$N$ is a set of non-terminal symbols
$\Sigma$ is a set of terminal symbols
$P$ is a set of production rules
$S$ is a start symbol

You have only provided $P$, but to have a grammar, you also need $N$, $\Sigma$ and $S$.

$N$ and $\Sigma$ are often omitted when defining a grammar, because they are clear from $P$ (like in your example, where $N = \{ S, A \}$ and $\Sigma = \{ 0, 1 \}$).

Explicitly specifying the start symbol (referred to as $S$ in the formal definition above) can be omitted when there is a clear convention for the name of the start symbol; naming it $S$ as you do in your example is a common convention.

What this all means for your example is that if you assume that $S$ is the start symbol, then $1$ is not a member of the language. If you instead assumed that $A$ is the start symbol, then $1$ would be a member of the language. Such grammar would be formally valid, but defining it like this wouldn't make sense from a human's point of view.


Data structures and algorithms for bridge game play?

If the data is really a tree graph, then maybe a Prüfer code?


Chomsky NF or Greibach NF benefits for LR parser?

The point of generating a parser (usually) is to parse: "Analyse (a string or text) into logical syntactic components" (some online dictionary). That's different from simply recognizing that a text is a member of a language. A given language has a variety of grammars which will recognize its sentences, but typically there is a specific grammar which defines the "logical syntactic components" and their relationship to each other, as in the above definition. In real-world applications -- compilers, for example -- one expects an output which is more interesting than simply "the input is/is not a valid program".

In some cases, it is possible to recover the original parse tree from the parse tree generated by parsing a transformed grammar. (This is true for CNF, with the usual transformation strategy.) In other cases (such as GNF, as far as I know), it is annoyingly difficult, making such a transformation of limited use for parsing (as opposed to recognition).

Also, not all grammar transformations preserve LR(k)-ness. In particular, the usual CNF transformation involves refactoring of every production into a series of rules with precisely two non-terminals. This often has the effect of converting an LR(1) grammar into a grammar which is not LR(k) for any k. So that's not much help, either.


Why is {w | no prefix of w starts with b} = {w | the first character of w is a} ∪ {e}?

The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.


How to distinguish empty cells from cells outside of the input cells?

The common definition of the Turing machine is that when you go left when you're at the furthest left point on the tape, is to stay on that spot. So if you want to determine where it began, mark it off, as you said, with a diamond or similar.


Point in Polygon Problem: Has anybody invoked the line integral?

Summing the angles around a point is equivalent to calculating the winding number around that point. It will give you a correct answer in the general case.

Going more in depth, I'll try to show that your proposed algorithm has many drawbacks.

Algorithmic runtime

Algorithmically, your proposed algorithm must iterate over all $N$ points. Because of that, we can assume it runs in $\Theta(N)$ time.

In contrast, a ray casting algorithm checks against edges, of which there are $N$. The algorithm can be optimized using grids or quadtrees to reduce the amount of calculations needed. Since the ray might intersect all edges, that algorithm runs in $\mathcal{O}(N)$ time.

We can conclude that the ray casting algorithm will never perform worse than the angle sum.

Gotchas

You mentioned the ray casting algorithm as having gotchas. I'll assume you refer to the problems occurring when the ray crosses a vertex or an edge directly. First, your proposed algorithm has the same problem. What if the point you choose is on a vertex or an edge?

The solution to the problem for both algorithms is to define strict rules. That is, from the start, decide (or parametrize the algorithm) so that points on edges or vertices of the polygon are either all included or all excluded.

As an aside, the solution for ray casting's problem of intersecting vertices and edges can be solved using a similar rule. When a vertex is on the ray, it must be considered to belong to one side of the ray (more here).


Does XNOR of three variable equals XOR of same three variables

XOR is addition modulo 2, and XNOR computes the sum modulo 2 of its inputs and 1. Since
$$ (x+y+1)+z+1 \equiv x+y+z \pmod{2}, $$
We see that XORing three variables is the same as XNORing them. The same holds for any odd number of variables. When XNORing an even number of variables, you get the negation of their XOR.

Nothing of this sort happens for AND or OR. There isn't any particular reason. You should think of it the other way around: XOR satisfies this surprising property, but other gates do not. XOR is special. It has absolutely nothing to do with AND and OR being "basic gates", whatever that means (mathematically, probably not much).


Do multiple transitions over the input give finite state machines more power?

Multiple passes do not add any power.

It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector. A vector state is an accepting state iff there is a path of length $k$ starting at the original machine's starting state and linking the state at each position to that position.

Specifically, let the original machine be $(Σ, Q, q_1, δ, F)$, where $Q = \{q_1, \ldots, q_n\}$. Define the new machine $(Σ, Q^n, q'_s, δ', F')$ with

$$\begin{align}
q'_s &= \langle q_1, \ldots, q_n\rangle \\
\delta'(\langle q_{i_1},\ldots,q_{i_n}\rangle, s) &= \langle \delta(q_{i_1}, s),\ldots,\delta(q_{i_n}, s)\rangle \\
\langle q_{i_1},\ldots,q_{i_n}\rangle \in F' &\text{ iff } \exists t_1,\ldots,t_k \text{ with } t_1 = 1, q_{t_k} \in F \text{ and } t_j = i_{t_{j-1}} \text{ for } j \in \{2,\ldots,k\}
\end{align}$$
Although that's a lot of states, it's still a finite number, and the set of  accepting states is well-defined and can be enumerated. So the multiple-pass machine is still a finite-state machine.


How can a 64-bit processor address 2^64 different memory locations at a time?

It's not clear where you found this claim so it's hard to tell exactly what it's supposed to mean.

But, obviously, no, the CPU can't access every memory location simultaneously. Each CPU instruction can only access some fixed small number of memory locations at a time, and only a fixed small number of instructions can be executing simultaneously.


How does a Single Pass Compiler does parsing,analyzing and generating code all at once?

PROGRAM Demo
{
  INTEGER i;
  i= 4;
  WRITELN(i + 5);
}.

Line 1: enter the program name in the symbol table. Generate the program prologue.
Line 3: enter the declaration of variable i in the symbol table.
Line 4: evaluate the constant expression and generate code for the initialization of i.
Line 5: parse the function call and the argument expression. Generate code for the evaluation of the expression i + 5, the push on the stack and the call of the WRITELN predefined function.
Line 6: Generate the program epilogue.

Done.


Is Huffman encoding for the entire language or the body of text?

The statistics used to derive the Huffman codes from can come from any source that you want. For a practical example, the popular DEFLATE format allows both "dynamic Huffman codes" (in this usage it is not a form of adaptive Huffman coding, it means the codebook is specified in the data stream) and "fixed Huffman codes" (a codebook that is specified in the DEFLATE specification).
A codebook based on the statistics of the actual data being compressed generally results in a smaller compressed size. The trade-off is that a codebook that is not pre-defined must be supplied along with the data (the decoder still needs it), adding to the overall size. Canonical Huffman codes can mitigate the impact (requiring only the code lengths to be transmitted, the codes themselves can be inferred in a simple way), but transmitting the codebook is going to cost some extra data, and may not be worth the size overhead for short texts (especially when the statistics of the given text happen to approximately line up with the statistics on which the pre-defined codebook was based).
Other practical considerations may favour using slightly inaccurate statistics, for example statistics based on some prefix of the data to be able to start encoding without having to wait until the input is fully known. The more accurate you want the statistics to be, the longer the latency is between the "first input" and the "first output" of the encoder. Even if the input is entirely known at the start, depending on the application, gathering fully accurate statistics may not be worth the time investment.


Is it possible for the runtime and input size in an algorithm to be inversely related?

Try brute force searching of a key for a cryptographic algorithm.  The more of the key you give it to start with, the less you have to search for.  True that trend stops at the limit of keysize (but that's still monotonic), and there are probably other examples in the field of extensive search where the more input data, the easier it is to prune branches of the potential tree.


Matching Lemma with infinitely many symbols

Turing machines can simulate whatever algorithm you can actually program. So if you can solve your problem by writing a program in C or python (for example), then a Turing machine can also solve your problem.

The most general statement of this principle - everything that is computable can be computed using a Turing machine - is known as the Church-Turing hypothesis. For the specific case of languages like C or python, we know that this hypothesis is true - in principle you can convert every program in C or python to an equivalent Turing machine. The Turing machine would be a lot slower, though. (But only by a polynomial amount!)

For your specific problem, you can allocate a specific location in the tape for your the variables you need, and then update them as you go. The number of states in the Turing machine is proportional (more or less) to the number of instructions in assembly code for your algorithm. Actually programming Turing machines is hard and somewhat pointless. Memory handling is particularly awkward, but Turing machines can implement arrays, tables, and other data structures by allocating special areas on the tape and maintaining them. Perhaps you will hear more about that later in your class.

Finally, for the reason you mention, the tape alphabet is always finite. Without loss of generality, we can assume that it contains only zero and one, though that might make programming the Turing machine even harder. Data structures such as strings and numbers can be encoded in just the same way that they are encoded in your computer - as a string of zeroes and ones.


You need to design a NPDA that behaves as follows:

If it reads "a" and stack is empty push "a" onto stack
If it reads "b" and stack is empty push "b" onto stack
If it reads "a" and top entry on stack is "a" the push "a" onto stack
If it reads "b" and top entry on stack is "a" the pop "a" from the stack
If it reads "a" and top entry on stack is "b" the pop "b" from the stack
If it reads "b" and top entry on stack is "b" the push "b" onto stack

The top entry on the stack is therefore "a" if the NPDA has read more "a"s than "b"s, and is "b" if it has read more "b"s than "a"s. If the stack is empty then the NPDA has read equal numbers of "a"s and "b"s.

The accepting states are therefore if the top entry of the stack is "a" or the stack is empty.


Backus–Naur Form's syntax can be represented with a BNF itself. Here is an example taken from this Wikipedia article:

<syntax>         ::= <rule> | <rule> <syntax>
<rule>           ::= <opt-whitespace> "<" <rule-name> ">"
                     <opt-whitespace> "::=" <opt-whitespace>
                     <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression>     ::= <list> |
                     <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list>           ::= <term> | <term> <opt-whitespace> <list>
<term>           ::= <literal> | "<" <rule-name> ">"
<literal>        ::= '"' <text> '"' | "'" <text> "'"

"" denotes the empty string. The article provides some more details on undefined here rules for <rule-name>, etc.


How to solve linear equation with binary tree

For solving this question you should assume a tree with '=' root
And in the left side of root push factors of x and in the right side push your constant values, now variable x is equal to sum of right side division by left side.


Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$'s. The following is not the most efficient grammar, but it will do.

Context free grammar rules:

$S \rightarrow BAFUE\ |\ \epsilon$
$U \rightarrow UD \ | \ D$

Non-contracting grammar rules:

$FD \rightarrow DG$
$AD \rightarrow D1A$
$1D \rightarrow D1$
$A1 \rightarrow 1A$
$BD \rightarrow BH$
$H1 \rightarrow 1H$
$HA\rightarrow AI$
$IA\rightarrow AI$
$IG \rightarrow AAF$

Now some non non-contracting rules:

$FE \rightarrow E$
$B \rightarrow \epsilon$
$AE \rightarrow E$
$E \rightarrow \epsilon$

Though this grammar has four non non-contracting rules, I have left them as it is, to help understanding. With a little effort we can convert it into a non-contracting grammar and then to a context-sensitive-grammar.

$IG \rightarrow AAF$ is the important rule, every time it adds two extra $AA$'s to be later substituted by 1's.


Infer number of comets, based upon observations of their periodic visits to Earth

Based on the restriction you gave, that you cannot identify one comet from another, there is no difinative method of calculation. Here is a proposed situation, There are 2 comets following the same trajectory, they each orbit at exactly ten year orbit durations, so each one is seen every ten years, they are however exactly 5 years apart in their orbits. From the ground if we cannot differentiate between these two comets we only see a comet appear overhead regularly every 5 years, there is no way to tell if this is one comet appearing ever 5 years, or two comets appearing every ten years, but 5 years apart. From this it is impossible to deterministically say how many comets there are, so no algorithm can give you numComets with the assumptions that you have specified.


Substitution for Landau's O notation formula

First let us notice that $\log s = n^{o(1)} = o(n)$, and so $\mathit{poly}(\log s, n) = \mathit{poly}(n)$. This shows that the first summand is $2^n \mathit{poly}(n)$.

Next, since $\log s = n^{o(1)}$, also $O(\log s) = n^{o(1)}$ (since constants are $n^{o(1)}$) and $O(\log s)^c = n^{o(1)}$ (since a constant multiple of $o(1)$ is also $o(1)$), hence the second summand is $2^{n^{o(1)}} = o(2^n)$. So the first summand is more significant.


building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas

Here is something your oracle can do: if you are given two formulas $\alpha,\beta$, and are guaranteed that at least one of them is satisfiable, then you can find one of them which is satisfiable by calling $M(\alpha,\beta)$: if $M(\alpha,\beta) = 1$ then $\alpha$ is satisfiable, and if $M(\alpha,\beta) = 0$ then $\beta$ is satisfiable.

Given a satisfiable formula $\varphi$ over $x_1,\ldots,x_n$, you can use this to find a satisfying assignment, variable by variable: at each step, you consider assigning the variable the two possible truth values, and use the method described above to find an assignment under which the formula is still satisfiable. Finally, you can check whether the supposed satisfying assignment indeed satisfies $\varphi$. If so, $\varphi$ is satisfiable. Otherwise, it isn't.


Bounds for Akra-Bazzi versus Master theorem

Both methods give $\Theta$ type estimates. That is, the master theorem gives some estimate $T = \Theta(f)$, and the Akra–Bazzi theorem gives some estimate $T = \Theta(g)$. From the definition of $\Theta$ it immediately follows that $f = \Theta(g)$ and $g = \Theta(f)$, that is, the estimates are equivalent. I suspect either one of you was mistaken, or both bounds that you got, while seemingly different, are in fact equivalent.


How to design an algorithm to generate balanced teams?

There's probably a tradeoff between ease of implementation and the quality of the solution.  I'll list a few possible approaches.  The first step is to pick a way to measure the quality (imbalance/unfairness) of a proposed solution.  One possibility would be the variance of the team averages; another would be the gap between the largest team average and the smallest team average.  Then, pick one of the following methods to choose an assignment that is as good as possible, under this quality measure:

Random. The simplest to implement method is random assignment.  Randomly assign each kid to a team (subject to the requirement that each team has the same number of boys and same number of girls).  Measure the quality of each assignment.  Do this for 1000 random assignments.  Pick the best one.  That's very easy to implement.
Here is a simple way to do the random assignment: randomly re-order the list of kids, and put the first $k$ into the first team, the next $k$ into the second team, and so on, where $k$ is the desired team size.  To also ensure gender equality, do this separately for the boys and girls.

A greedy heuristic. A different approach is to assign the kids to teams in a heuristic way.  Sort the kids from slowest to fasteast.  Now iterate over the kids in this order and, for each kid, assign that kid to a team.  Assign the kid to the fastest team (measured by their average speed given the current assignment).  If some teams currently have fewer members than others, only choose among the teams with the fewest members.  To ensure gender equality, when a boy picks a team, have them only pick among the teams with the fewest number of boys; and symmetrically for girls.  There are other heuristics you could consider, but this seems like it might yield good results.

Random + heuristic. You can combine the first two ideas.  First, randomly pick a fraction of the kids, and then randomly assign them to teams.  Second, assign the rest of the kids via the above heuristic.  You can repeat 1000 times and take the best assignment seen so far.
It will probably help to ensure that the initial random assignment assigns the same number of boys and girls to each team.

Simulated annealing. A more sophisticated method is to start with a random assignment and use simulated annealing to improve it.  In each step, you randomly pick a pair of kids of the same gender but from different teams, and you consider what would happen if you swapped them.  Depending on how this affects the quality of the solution, you decide whether to make the swap or not, in a particular way.  Simulated annealing might improve on the other methods, but it is also a little fiddly, as there are parameters you have to tune to get it to work to best effect.

Integer linear programming. If you're willing to measure quality by the difference between the largest team average and the smallest team average, a more sophisticated method still is to use integer linear programming.  You have a zero-or-one integer variable $x_{i,j}$ indicating that the $i$th kid is assigned to the $j$th team, and then you can write down linear inequalities that capture the requirements on a solution to be valid.  This can potentially give you the optimal solution.

I suspect the latter two approaches are more complicated than is really necessary and just trying a bunch of random assignments might be good enough.
In general, your problem is NP-hard; it is as hard as bin-packing.  If you cared enough you could investigate the heuristics and approximations for bin-packing and try seeing if you can adapt them to your problem.  I don't know that that will be worth the effort.


Why is NFA minimization a hard problem when DFA minimization is not?

For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA.

For NFA the situation is complicated as there is no unique minimal NFA in general.

Here is an example for the finite language $\{ ab, ac, bc, ba, ca, cb\}$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat.

This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity.


Are there any problems that get easier as they increase in size?

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input.  Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer.  In other words, $T(n) \in \mathbb{N}$ for all $n$.  Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing.  (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.)  For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.

Note that this answer covers only deterministic algorithms (i.e., worst-case running time).  It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever.  I don't know whether it's possible for such an algorithm to exist.  I thank Beni Cherniavsky-Paskin for this observation.


Find cycles with specific weights in complete graph

Welcome to CS.SE.
I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.
A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?
This leads to the following python 2.7 code, that does not make the assumption that the graph is complete. Its core is the find function, everything else is for playing and testing.
import random
random.seed()

min_weight,max_weight=1,20
c_length=30

# build the graph (complete in this case)
V = ['A','B','C','D','E']
N = {u:[v for v in V if v!=u] for u in V}
weight = {}
for (u,v) in [(u,v) for u in V for v in N[u] if u<v]:
        weight[(u,v)] = weight[(v,u)] = random.randint(min_weight,max_weight)
for (u,v) in sorted(weight):
        print u+'--'+str(weight[(u,v)])+"--"+v

# build a correct sequence of weights
c = []
u = random.choice(V)
while len(c)<c_length:
        v = random.choice(N[u])
        c.append(weight[(u,v)])
        u = v
print c

# search all paths corresponding to the weight sequence in the graph
def find(c,S):
        if len(c)==0:
                return(S)
        return set([u+r for u in S for r in find(c[1:],[v for v in N[u] if weight[(u,v)]==c[0]])])

result = find(c,V)
print result

# check results
def check(x):
        if len(x) != len(c)+1:
                return(False)
        for i in xrange(len(x)-1):
                if weight[(x[i],x[i+1])] != c[i]:
                        return(False)
        return(True)
for x in result:
        assert(check(x))

Is it correct? It is far from optimal, of course.


Structural parametrization for weighted vertex cover

Find the set $L$ containing the $\ell$ extra edges (actually, find any set $L$ of $\ell$ edges such that $G-L$ is a tree).
Let $C$ be an optimal solution.
For each edge $(u,v)$ in $L$, guess whether $u \in C$. If you guess "yes", add $u$ to a set $X$, otherwise add $v$ to $X$.
(Notice that it is possible for both $u$ and $v$ to be in $C$, but we do not need to explicitly consider this case).
Overall, there are at most $2^\ell$ distinct choices for the $\ell$ guesses.
At least one set $X^*$ among the guessed sets $X$ is a subset of $C$.
Given $X^*$ you can find the minimum weighted vertex cover in poylnomial-time by considering $F=G-X^*$. Since all the edges in $L$ have an endpoint in $X^*$, $F$ is a forest. Then you can find a minimum weighted vertex cover $C_i$ for each tree $T_i$ in $F$. The set $\cup_i C_i$ is a minimum  weighted vertex cover for $F$, and $X^* \cup (\cup_i C_i)$ is the sought solution.
You could also directly find a minimum  weighted vertex cover for $G-L$ with the constraints that the vertices in $X^*$ are forced to be in the cover. This can be done, e.g., with a straightforward modification of the dynamic programming algorithm for trees.
Another option is setting the weights of the vertices in $X^*$ to $0$ (or to $\sum_{v \in V}$) making them essentially "free" to select.
Since you don't actually know $X^*$ you can run the above procedure on each guess $X$ and then select the cover of minimum  weight.


Whole books and fields of research are devoted to methods for computing eigenvalues and eigenvectors. Properties of the matrix matter, a lot. The ideal method will depend on whether

the matrices are symmetric or nonsymmetric,
positive definite or indefinite,
sparse or not sparse,
you need all the eigenvalues/vectors or just a few,
you have $O(1)$ access to the elements of the matrix or just the ability to apply it to vectors via a function call
etc...

That said, at the core of most modern methods for finding all the eigenvalues of a generic matrix is the The QR algorithm (the eigenvalue algorithm, not the related orthogonalization algorithm). The methods most used in practice such as the Arnoldi iteration (or Lanczos for symmetric problems) are basically a 2 step process in which the matrix is converted into a nicer form, and then the QR algorithm is used.

Understanding the power method is a good place to start from because it's intuition informs most of the other methods in some way or another.


Your problem is known as Maximum coverage. The greedy algorithm (repeatedly take a set which covers the maximum number of uncovered elements) is a $1-1/e$ approximation, and runs quite efficiently.


Can we use reductions to design approximation algorithms for NP-hard problems?

Yes, but you need an approximation-preserving reduction in the opposite direction.


Heap structure in array, computing parent and child

While it is possible to write a formal proof, I think the best proof is by picture:

If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) contains $2^d$ nodes, and so a simple induction shows that level $d$ occupies the indices $2^d, \ldots, 2^{d+1}-1$. Consider now the $i$th node on the $d$th level (again, counting from zero). Its children are nodes $2i,2i+1$ on level $d+1$, as the following table makes clear:
$$
\begin{array}{c|c}
\text{parent} & \text{children} \\\hline
0 & 0,1 \\
1 & 2,3 \\
2 & 4,5 \\
\cdots & \cdots
\end{array}
$$
The index of the $i$th node on the $d$th level is $2^d + i$. The indices of nodes $2i,2i+1$ on level $d+1$ are $2^{d+1}+2i,2^{d+1}+2i+1$. Notice that
$$
2^{d+1}+2i = 2 \times (2^d + i), \\
2^{d+1}+2i+1 = 2 \times (2^d + i) + 1.
$$
This explains the formulas for the left and right children. The formula for the parent follows similarly, since
$$
\lfloor (2^{d+1}+2i)/2 \rfloor = \lfloor 2^d + i \rfloor = 2^d + i, \\
\lfloor (2^{d+1}+2i+1)/2 \rfloor = \lfloor 2^d + i + 1/2 \rfloor = 2^d + i.
$$


Which complexity classes are $\mathsf{RE}$?

Time-bounded classes can be enumerated. Suppose we want to enumerate all languages in P. Every language in P is accepted by some Turing machine $T$ running in time $f(n)$ for some polynomial $f$. We can construct a Turing machine $T'$ that emulates $T$ but also keeps track of the time, and stops after $f(n)$ steps. Every Turing machine of the form $T'$ accepts a language in P, and vice versa, for every language in P, we can construct such a machine $T'$. The machines $T'$ themselves can be enumerated by enumerating the simulated machines $T$ and the "timers" $f(n)$.

For a space-bounded class, you do something similar, keeping track of the space usage of the Turing machine. You also need to prevent infinite loops somehow, either using a timer or by keeping track of all positions encountered so far during the simulation.

Non-deterministic and randomized versions can also be handled this way, so for example, PH can be enumerated.


Finding a source of a directed acyclic graph in linear time

As Yuval mentions, the datastructure is important here. I'll try to give a solution for some of the types of adjacency lists:

Incoming edge list: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is $0$  or not. A size $0$ list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of all sources (or you can stop after finding one) in $O(|V|)$ time - linear in the number of vertices.
Outgoing edge list: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the size of the graph - $O(|V| + |E|)$.
Both lists together: For each vertex, there is a mixed list of vertices which have an edge to or from this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the size of the graph - $O(|V| + |E|)$.
Both lists separately: Just pick the incoming edge list and follow 1.

As a side note, if choosing the datastructure is in your hands, you might want to analyze what all operations you intend to perform, and how frequently, and choose an appropriate datastructure.

Edit: For case 1, if you have a dag where the number of sources is very small as compared to $|V|$ (eg, in a tree with one source), and where the average distance from any vertex to a source is small as compared to $|V|$ and you only want any one source, you can use a faster on average algorithm (although worst case asymptotic complexity will be the same). Select any vertex at random, and go to any of its parent (from the incoming edge list), and on to its parent and so on, till you reach a node which has no parent - a source. This small gain of efficiency is for very limited types of graphs with a slightly more complex algorithm.


Let's analyze two consecutive steps of the GCD algorithm: given $a > b$, we compute $c = a \pmod{b}$ (replacing $a$) and $d = b \pmod{c}$ (replacing $b$). The two new numbers $c,d$ we are left with satisfy

$$ c+d \leq b \leq \frac{1}{2} (a+b). $$

So the sum of the two numbers decreases by a factor of at least a $1/2$ every two iterations. If $a,b$ are at most $n$-bit long, then at the start of the algorithm, $a+b \leq 2^{n+1}$. After $2(n+1)$ steps, the two remaining numbers have sum at most $1$, so by that time the algorithm must have terminated.


Decidable problems for which no concrete decision procedure is known

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n \in \mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:

Always return "true".
Always return "false".

But you need to solve $P=NP$ to know which one.


Not able to prove non regularity using pumping lemma

Don't forget that the pumping lemma guarantees that $|ux| \leq n$, where $n$ is the pumping length (which is also a lower bound on the length of $w$). You can use this condition to forbid the situation you describe.


String of minimum length in $\{a, b\}^*$ not in a regular expression

First, the string of minimum length might not be defined properly since it might not be unique.

Here is a way to find a string of minimum length:

Convert the regular expression to a nondeterministic finite automaton.
Convert the nondeterministic automaton into a deterministic one.
Use a breadth first search until you encounter the first nonfinal state (if there is one at all).


Why can you push multiple symbols on a PDA stack at once?

You always have to take out a symbol. So if we could only write a single symbol, we could never really build up stack content.

Writing more than two symbols is just syntactic sugar; we could easily simulate it with PDAs restricted to writing zero, one, or two symbols.


First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

The grammar you have presented is left linear grammar. The production $A \rightarrow Ad$ in when transformed into $FM$, $A$ becomes state & an edge with $c$ terminal from $A$ to $A$ (self loop). So its clear for this particular grammar $First(A)$ is $c$.

Moreover, your approach is also correct or primarily correct.


What kind of reductions are usually used in order to prove PP-completeness?

Here "PP-complete" means "complete for PP".  The definition of PP defines the complexity class PP; it does not define the type of reduction you can use, as that is an orthogonal concern.  So, "complete for PP" actually means "complete with respect to a particular class of reductions", and the meaning of that is implicitly parametrized by a class of reductions (usually the reader assumes you will be able to infer the class, from context).  For each class of reductions, you potentially get a different notion of completeness.

In this case, we're talking about polynomial-time many-one reductions, also known as Karp reductions -- the same class of reductions as is commonly used in the definition of NP-completeness.  This becomes immediately clear if you read the proof of completeness of MAJSAT (it's immediate to see that this is the type of reduction that gets constructed, in that proof).

In the future, please make sure to do research through standard sources before asking here, and to use some effort to formulate your question clearly and precisely -- that will increase the chances that you get a useful answer.


Scheduling / Queuing jobs with multiple different workers

The simplest option is a single queue that workers can scan for a good job for them. In other words job distribution is done when a worker just finished his previous job and needs a new one.

Using only this will create suboptimal distribution when the queue is nearly empty due to the first come first serve.

Swapping jobs between workers is very difficult to implement in a way where the overhead of the swap does not exceed the work of the actual job. One way could be to periodically in the job have it be queued back partially completed but only if the current worker is suboptimal for that task and a better job for it is available in the queue.


The nand gate is defined as follows --when and, not gates are available--

a nand b  ≡  ¬(a ∧ b)

Hence, since conjunction is idempotent, $a ∧ a ≡ a$, we have the not gate:

a nand a  ≡  ¬ a

Since negation is its own inverse, $¬ ¬ x ≡ x$, we have the and gate:

  a ∧ b
≡ ¬ ¬ (a ∧ b)                   -- double negation
≡ (¬ (a ∧ b)) nand (¬ (a ∧ b))  -- not in terms of nand
≡ (a nand b) nand (a nand b)    -- using ‘definition’ of nand

Finally, the or gate:

   a ∨ b
≡  ¬¬ a ∨ ¬¬ b                 -- double negation
≡  ¬ (¬ a ∧ ¬ b)               -- De morgan's law
≡  (¬ a) nand (¬ b)            --  using ‘definition’ of nand
≡  (a nand a) nand (b nand b)  -- not in terms of nand

Neato!


Suppose that we have a context-free grammar $G$ and a set of words $S$, and we would like to prove that the language $L(G)$ generated by $G$ is precisely the set $S$. The most direct way of doing this is to prove $L(G) \subseteq S$ and $S \subseteq L(G)$, which amounts to showing:

For every $x \in L(G)$ we have $x \in S$.
For every $y \in S$ we have $y \in L(G)$.

How this is done depends on how the set $S$ is given, so there is no further, more specific advice that I can offer, except that drawing trees is not really going to result in a proof.


What is the name of the following algorithm?

This is a form of local search.  It is similar to hill climbing.  It's also reminiscent of stochastic hill climbing, as @Juho suggests.


Optimal strategy in repeated cake-cutting

Let $v(x) = \frac{V(x) - V(0)}{V(1) - V(0)}$ so $v(x)$ nicely goes from $0$ to $1$. Maximizing $v$ also maximizes $V$. To cover my ass for future mistakes regarding $<$ vs $\leq$, I will assume that you will never exactly guess $x = h$.

Now, if $n = 1$, we can find the expected value from cutting at $x$ by integrating over all possible $h$:

$$e_1(x) = E[v(x)] = \int_0^x (1 - v(x))dh + \int_x^1 v(x)dh = (1 - 2x)v(x) + x$$

Which allows you to maximize $e_1$ with differentiation to find the optimal $x$. Note that in the above example "all possible $h$" meant $[0, 1]$. But what if we know that $h \in [a, b]$ due to previous information?

Then we get the following sum of integrals for when also $x \in [a, b]$:

$$\int_a^x (1 - v(x))dh + \int_x^b v(x)dh = (a + b - 2x)v(x) - a + x$$

Which makes the total expected valuation:

$$e_{1,a,b}(x) = E[v(x) | a \leq h \leq b] = \begin{cases}
v(x) & \text{if $x < a$}\\
(a + b - 2x)v(x) - a + x & \text{if $a \leq x \leq b$}\\
1 - v(x) &\text{if $x > b$}
\end{cases}$$

Now let's analyze $n = 2$. Suppose our first cut is at $x$, then there is a $x$ chance $h \leq x$ and $1 - x$ chance $h \geq x$. In both those scenarios we will then choose our best possible $y$. This gives equation:

$$e_2(x) = e_1(x) + x\left( \max_{0 \leq y \leq 1} e_{1,0,x}(y)\right) + (1-x)\left( \max_{0 \leq y \leq 1} e_{1,x,1}(y)\right)$$

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\max_{0 \leq y \leq x} ((x - 2y)v(y) + y), \max_{x \leq y \leq 1} (1 - v(y))\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(\max_{0 \leq y \leq x} v(y), \max_{x \leq y \leq 1} ((x + 1 - 2y)v(y) - x + y)\right)$$

Now let's say $v(x) = x$, a simple linear increase in desire for more cake. Now we can actually solve:

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\begin{cases}x(1-x)&0\leq x \leq \frac{1}{3}\\\frac{1}{8}(x+1)^2&\frac{1}{3} \leq x \leq 1\end{cases}, 1 - x\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(x, \begin{cases}\frac{1}{8}(x-2)^2&0\leq x \leq \frac{2}{3}\\x(1-x)&\frac{2}{3} \leq x \leq 1\end{cases}\right)$$

Now $e_2$ is complicated, but is essentially a piecewise function which can be solved.


Let's answer your questions one by one:

A deterministic reduction proves NP-hardness. A randomized reduction doesn't. If a problem is NP-hard with respect to randomized reductions, then it could (potentially) be solvable in polynomial time even if P$\neq$NP. The assumption BPP$\neq$NP does rule out polynomial time algorithms for any such problem, however – even randomized ones.
The consequence is that P$\neq$BPP, which is conjectured to be false.
NP-hardness is defined with respect to deterministic reductions.
We say that the problem is "NP-hard with respect to randomized reductions".


Implementing an interval tree using arrays?

To a mathematician "prove or disprove" is a very strict requirement. I do not know how serious I should take this.

Every tree that has been implemented using pointers also has a array implementation. The trick is to do the addresses yourself as indexes to an array. That is usually called a cursor implementation.

Binary trees can be implemented, as you say, storing children of node $i$ at indices $2i$ and $2i+1$. This is sometimes called an implicit representation as no explicit structure is stored. The method is  alwaus possible, but only advisable when the tree is perfect (all levels completely filled) or near perfect, like the complete trees used to store a binary heap. Otherwise it is a waste of space. When some node $i$ is missing in the tree then also nodes $2i$ and $2i+1$ are missing, and $4i,\dots, 4i+4$, etc.


What do the symbols M and N mean in this definition of lambda terms?

I suggest you read the page following the supposedly cryptic notation:

  The above Backus-Naur Form (BNF) is a convenient abbreviation of the following equivalent, more traditionally mathematical definition:

  Definition. [...]

In said definition, it is stated that $M$ and $N$ are simply arbitrary lambda terms. (In a nutshell, it is an inductive definition.)

As to why the author prefers this notation, it is stated right after the definition:

  Comparing the two equivalent definitions, we see that the Backus-Naur Form is
  a convenient notation because: [...] the use of distinct meta-symbols for different syntactic classes ($x$, $y$, $z$
  for variables and $M$, $N$ for terms) eliminates the need to explicitly quantify over
  the sets [of variables and lambda terms].


Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

In fact, a MST is a subset of the edges building a tree (thus without cycle) using the minimum edge weights. It has exactly N-1 edges for a N nodes graph.

It may exist several different MST for the same graph. For an unweighted graph, which is in other way a graph with weight 1 on every edges, the total weight of any spanning tree is N-1. Thus any spanning tree is a MST.

When you use BFS or DFS to explore a graph, you build an exploration tree, which is the shortest path tree for BFS. And if the graph is unweighted, you can say this tree is a MST, yes so 1. and 2. are true.

3. is true, MST and SPT are different. Just make BFS and DFS on a 3-clique (3 nodes connected to each other) to have an example.

4. is true but remember that "minimum" adds no information to any spanning tree of an unweighted graph. And also that a N nodes tree has exactly N-1 egdes.


Finding the rectangle with maximum perimeter weight in a 2D array

Let us denote the entries of the array by $A(i,j)$.
Fix the first and last rows of the rectangle $i_1,i_2$. For $j_1<j_2$, the perimeter of the corresponding rectangle is
$$
\sum_{i=i_1}^{i_2} [A(i,j_1) + A(i,j_2)] + \sum_{j=j_1}^{j_2} [A(i_1,j) + A(i_2,j)] = \\
\left[\sum_{i=i_1}^{i_2} A(i,j_1) - \sum_{j<j_1} [A(i_1,j) + A(i_2,j)]\right] +
\left[\sum_{i=i_1}^{i_2} A(i,j_2) + \sum_{j \leq j_2} [A(i_1,j) + A(i_2,j)]\right].
$$
Let us denote the first term by $x_{j_1}$ and the second by $y_{j_2}$. Using appropriate precomputation, it is possible to compute the arrays $x_j,y_j$ in $O(n)$. We can also compute $\max_{j_1<j_2} (x_{j_1}+y_{j_2})$ in $O(n)$. In total, for each $i_1<i_2$ we can compute the maximum perimeter in $O(n)$. Since there are $O(n^2)$ choices for $i_1,i_2$, the entire algorithm runs in $O(n^3)$.
This answers your first question. I'll let you check whether these methods can help with the second question.


What does a proof that Co-NP =P entail for the NP versus Co-NP question

$\text{P}=\text{co-NP}$ implies that $\text{co-P}=\text{co-(co-NP)}=\text{NP}$.  But
$\text{co-P}=\text{P}$: you can just swap the accept and reject states of a deterministic Turing machine to complement the language that it decides.


Time complexity of the fastest algorithm for this case

I think it's not optimal but here's a lower bound: you have to move at least $\lfloor\frac{n}{3}\rfloor$ elements.

Split $A$ into blocks of $3$: {$A[1],A[2],A[3]$}, {$A[4],A[5],A[6]$}, ...

The claim is you have to move at least one element from each block. Otherwise, assume the block {$A[k],A[k+1],A[k+2]$} is kept unchanged. Since $A$ is sorted, $\min(A[k],A[k+2])<A[k+1]<\max(A[k],A[k+2])$, which violates your constraint. So the problem takes $\Omega(n)$. Combine this with your $O(n)$ approach we get $\Theta(n)$.


Your approach looks good. Let's just write it clearly. Let's look at $E[X_1]$.

With probability $1/10$ the first coin was used to buy the coffee, thus the value is $X_1=0$.

With probability $9/10$ we are back in the situation of part II (we can add a new "Gold" coin - the party that gets this coin will not get his dollar back), so the expectation of this case is just like in Part II.

Adding both cases (with the appropriate weight) should solve your question, for $X_1$, and by the linearity of expectations, and since all parties are symmetric, the answer is $10 E[X_1]$.


maximum Hamilton cycle and NP-completeness

A decision problem is NP-complete iff it is in NP and it is NP-hard.
The decision version of Max-Hamiltonian cycle would be "given a weighted graph $G$ and a value k, decide whether there exists a Hamiltonian cycle of weight at least $k$ in $G$".
Your problem is clearly in NP (since a yes-certificate is the sought Hamiltonian cycle). Moreover it is also NP-hard since it is a generalization of the classical Hamiltonian cycle problem on unweighted graphs (simply set all edge weights to $1$ and $k=n$ to obtain an instance of your problem).
We can then conclude that this problem is NP-complete.


Find the maximizing row-column matches in a matrix

The problem can be solved with dynamic programming in $O(RC)$ time.

I'll start by showing how to solve it in $O(RC^2)$ time.  Let $M[\cdot,\cdot]$ denote the input matrix.  Let $A[i,j]$ denote the total value of the best matching using only rows $1..i$ and columns $1..j$.  We will compute the entries of $A[\cdot,\cdot]$.  There is a recursive relation for $A[\cdot,\cdot]$:

$$A[i,j] = \max(A[i-1,j],\max\{M[i,j'] + A[i-1,j'-1] : 1 \le j' \le j\}).$$

Here the $A[i-1,j]$ term corresponds to not including any match for row $i$, and the $\max\{M[i,j'] + A[i-1,j'-1] : 1 \le j' \le j\}$ corresponds to matching row $i$ to column $j'$.

You can fill in the entries of the $A$ array in a straightforward way in $O(RC^2)$ time, and the value of the best matching is given by $A[R,C]$.  So, this gives an $O(RC^2)$ time algorithm.

You can speed this up to $O(RC)$ time by simultaneously computing another array $B[\cdot,\cdot]$, with entries defined as

$$B[i,j] = \max(A[i,1],A[i,2],\dots,A[i,j]).$$

Then all of the entries of $A$ and $B$ can be filled in, if you do it in the right order, in a total of $O(RC)$ time.  This is linear in the size of the matrix, i.e., proportional to the number of entries in the input matrix. Since any algorithm will presumably have to examine all entries in the matrix, I think that means this algorithm is asymptotically optimal: no algorithm can run faster by more than a constant factor.


How do you define the semantics of RPN? Ignoring the print commands, I would imagine a recursive definition that, given a sequence of operations, tells you what the state of the stack is like. From this definition it is straightforward to prove the correctness of the algorithm. In order to add prints, the recursive definition should also include the sequence of numbers printed. To add errors, the recursive definition should give either a pair as above or the error symbol.

Edit: Here is how you would formally define the semantics, which in the simplified case are a partial mapping from a sequence of operations to a sequence of numbers (the stack). It is only partial since sometimes arguments might be missing.

The function $F$ is defined as follows. First, $F(\lambda)=\lambda$, where $\lambda$ is the empty sequence. $F(\sigma,n) = F(\sigma),n$, where $\sigma$ is a sequence. If $F(\sigma) = \tau,a,b$ then $F(\sigma,+) = \tau,a+b$. If $|F(\sigma)| \leq 1$, then $F(\sigma,+)$ is undefined. Other arithmetic operations are handled in a similar fashion, only you need to make sure not to divide by zero.

Given the semantics, the proof of correctness is rather boring, and I'd rather not spell it out. The loop invariant is essentially the function $F$.


Measuring Fitness in Genetic Programming Functionology

I don't know how to solve your original problem, but I can describe how to solve a simpler version of it.  Given numbers $a_1,\dots,a_n$ and a target $y$, if you only allow operations +,-, you can count how many operations it will take to reach $y$.

In particular, this amounts to asking for integers $x_1,\dots,x_n$ such that

$$a_1 x_1 + \dots + a_n x_n = y,$$

while minimizing $|x_1| + \dots + |x_n|$.

This can be solved using integer linear programming.  Introduce variables $w_1,\dots,w_n$ and the constraints $w_i \ge 0$ and $-w_i \le x_i \le w_i$ as well as

$$a_1 x_1 + \dots + a_n x_n = y,$$

and then minimize the objective function $w_1 + \dots + w_n$.

While integer linear programming is NP-hard in the worst case, when the numbers aren't too large, I expect that this will yield an efficient solution.

Introducing the *,/ operators makes your problem much harder.

To deal with your full problem, you might consider using the A* algorithm.  For instance, you might build a heuristic function that estimates the distance to the target by using integer linear programming to get an overestimate of the distance to the target (you know that the distance using +,-,*,/ operators will be at most the distance using +,- operators, and the latter you can compute efficiently using ILP).  I don't know for sure whether this will work well or not, but it's something you could try.


Using singly linked list instead of a doubly linked list?

Other than saving space, the first advantage I can see for singly
linked lists over doubly linked lists is to avoid having to update two
links instead of one when you modify the list, when adding an element
for example.

Of course, one might say that you can always ignore the second link,
but in that case, it is no longer doubly linked, but only an unused
field.

What might also be seen as an advantage is that singly linked list are
necessarily consistent, though possibly wrong when there are bugs in
the program.  Doubly linked lists can end-up having inconsistent links
forward and backward. But it is debatable which of the two cases, if
any, is an advantage.

update:

I had tried to see some impact on garbage collection, but found
none. Actually, there is one when storage reclamation is done by
reference counting, as reference counting is defeated by loops, and
doubly linked lists contain loops. Singly linked list escape the
problem. Of course, there are ways around it for doubly linked lists,
such as the use of weak pointers, or programmable reference counting
as part of data abstraction.


Showing two Turing machines decide different languages

Languages are just sets (of strings). As with any pair of sets, you show that they're different by showing that one set contains an element that's not in the other. Note that, in general, the problem of determining whether two Turing machines decide the same language is undecidable, so there's no algorithm you can use to generate such a string, in general. But, for any two given Turing machines, you can still try to figure it out.


How to estimate the complexity of sequential algorithm given that we know the complexity of each step?

In the first case, we have $O(n^9)+O(n^9)$ and according to it's summation properties we have $O(n^9)+O(n^9)=O(2n^9)=O(n^9)$.
For the second case, both $n^2$ and $n^3$ are smaller than $n^9$, so we have $O(n^2)+O(n^3)+O(n^9)=O(n^2+n^3+n^9)<O(n^9+n^9+n^9)=O(3n^9)=O(n^9)$
In the general case, if we have time complexities $t_1,t_2,...,t_k$, then $O(t_1)+...+O(t_k)=O(max\{t_1,...,t_k\})$


What are applications of the levels of the Chomsky hierarchy?

First, let's be clear, there are two separate types of languages, Turing Decidable (also called recursive), and Turing Recognizable (also called semi-decidable or recursively-enumerable).

The "application" of decidable languages is all of computer science. It's a huge class that includes exactly the problems that can be solved by algorithms. So you're not going to find specific applications like you would for compilers and CFGs, because the applications covered by decidable languages are "everything else." If you can write code for it, it's in this class.

Recursively-enumerable problems are ones where you know a solution when you see one, but might never know when you're out of potential solutions. You always halt on a "yes" answer, but might never halt for "no". This class is basically first-order theorem proving: we recognize proofs when we see them, but with quantifiers, there's no way to know if no proof exists.

It's also worth mentioning that parsers are CFG recognizers. Other parts of compilers, like translation and type-checking, are definitely not context-free.


Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one

Some case analysis shows that:

Without loss of generality, every subarray is monotone.
Without loss of generality, no monotone subarray is "broken", that is, joining two adjacent subarrays cannot result in a monotone subarray.

This reduces the number of options in dynamic programming to $O(1)$, and so should lead to an $O(n)$ algorithm.
(It seems that some case analysis is still needed. For example, if the array is $a,b,c$, where $a<b>c$, then the best solution depends on whether $a<c$ or $a>c$.)


Longest common sequence matrix giving wrong answer

Look at row=1 and column=8 (using 0 indexed numbers) in your matrix. That value says that the length of LCS between SHINCHAN and N is 2, which is impossible since N itself is of size 1.

When s1[i] and s2[j] are equal you need to look at the number in matrix[i-1][j-1] and add one and not matrix[i][j-1] (which I think you are doing). You can compare your method to the pseudocode written in the wikipedia article to arrive at the correct matrix (copied below for convenience)

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]


Context-free languages not closed under making them "extension-free"

Rather than the language $L\subseteq \Sigma^*$ consider the language $L' =L\$\$$, so concatenate every string by two copies of $\$$ where $\$$ is a new symbol not in $\Sigma$.

Let $x\in \Sigma^*$.
String $x\$$ is not a proper prefix of $L'$ iff $x\$\$ \notin L'$ iff $x\notin L$.

That should start you going.


Let $\sf{Bubble Sort}$ be defined as the following:

for (j = A.length; j > 1; j--)
    for (i = 0; i < j - 1; i++)
        if (A[i] > A[i + 1])
            swap(i, i + 1, A)

Given some permutation $x_1, \cdots, x_n$, an inversion is said to have occurred if $x_j < x_i$ for some $i < j.$ We see that $\sf{Bubble Sort}$ performs an inversion check for each pair, and if so, performs a swap. Let $X$ be the number of swaps. It is not hard to see in the worst case there are $X = \binom{n}{2}$ possible swaps made. But we are interested in the expected case, which we can compute by defining $X$ in terms of inversions in $\sf{Bubble Sort}$.

Now let $X = \sum_j \sum_{i<j} I_{ij}$ where $I_{ij}$ is the indicator variable that there exists an inversion for some pair $(i,j)$. The expectation is defined as $E[X] = E[\sum_j \sum_{i<j} I_{ij}] = \sum_j \sum_{i<j} E[I_{ij}]$. We now need to determine $P\{I_{ij}\}$.

When assuming any possible permutation as input, each with uniform probability, it can been shown that $P\{I_{ij}\} = \frac{1}{2}$. The reasoning behind this is that under any possible permutation, half of the time $x_j < x_i$ and half of the time $x_i < x_j$ for $i \neq j$.

Returning to our expectation calculation we see that $E[X] = \sum_j \sum_{i<j}E[I_{ij}] = \sum_j \sum_{i<j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$


Decision if there exists a path between $s$ and $t$ of length $k$

I think you (or whoever asked you this question) probably does mean "simple path" (that is, a path that does not contain any vertex more than once), since this problem is indeed NP-hard.

If paths that may repeat vertices (often called "walks") are permitted, the problem is not NP-hard any more: It can be solved in polynomial time using matrix multiplication.  Specifically, if $A$ is the adjacency matrix of the graph, then $A^k[i, j]$ (the element at row $i$, column $j$ in the matrix $A$ raised to the $k$-th power) is the number of walks of length exactly $k$ from $v_i$ to $v_j$.  You can compute $A^k$ in $O(n^3 \log k)$ time using exponentiation by squaring.


I think you're asking about universal Turing machines? The machine is universal, in the sense that it can compute anything that any other Turing machine can compute.  This is interesting is that Turing machines seem to be a very good model of what can be computed by physical devices, such as actual computers. In particular, we're not aware of any physical computation process (i.e., any mechanism we could use to build a computer) that can compute something that a Turing machine can't. So, in practice, the Turing machine is taken as the definition of what can be computed. (See also the Church–Turing thesis.)


Show that the halting problem is decidable for one-pass Turing machines

I assume $Q$ is state set of $M$. If so, this runtime bound does not make much sense; in particular, a Turing machine with three states can move to the end of the input and check whether $x$ is an even number; it is clearly not enough to wait three steps.

The next question is whether there is a computable bound on the runtime of halting one-pass machines. Unfortunately, there is not: $M$ might be nondeterministic and halt after an arbitrary amount of steps.

So we determinise $M$ while simulating (that is computable) and look for a bound for all paths. Now we are getting somewhere: after having consumed the input, there are two cases. Either $M$ halts or it enters a loop. As it only moves right (into empty tape), such loops can be detected.

   Putting things together, we simulate a determinisation of $M$. We run every branch until $x$ is consumed¹ and then for another $|Q|\cdot|\Sigma_T|$ steps, $Q$ the set of states and $\Sigma_T$ the tape alphabet of $M$. At this point $M$ has either stopped or loops (in this branch), which we detect by a pair of current state and tape symbol occuring for the second time. We only have to check finitely many branches up to a computable bound, therefore $L$ is recursive.

$M$ might loop here already if not moving the head is allowed, but that can be detected, too.


Algorithm To Compute The Gaps Between A Set of Intervals

The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction.

Let $I_1, I_2, \cdots, I_n$ denote the sorted intervals. When the algorithm has just finished processing $I_i$, we record the values of gaps and last_covered_point as $\text{gaps}_i$ and $\text{last_covered_point}_i$ respectively.
Let us prove the following proposition, $P(i)$, for $i=1, 2, \cdots, n$.

$\text{gaps}_i$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_i$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$.

When $i=1$, $\text{gaps}_1$ is the empty set and $\text{last_covered_point}_1$ is the right endpoint of $I_1$. So $P(1)$ is correct.
For the sake of mathematical induction, assume $P(i)$ is correct, where $1\le i\lt n$. Let $I_{i+1}=[s, e]$. There are two cases.

If $s\gt\text{last_covered_point}_i+1$, then $$\text{gaps}_i\cup[\text{last_covered_point}_i +1, s-1]=\text{gaps}_{i+1}.$$
Let $m$ be any point between the start point of $I_1$ and the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$. Suppose $m$ not covered by any of $I_1, I_2, \cdots, I_{i+1}$.

If $m\le\text{last_covered_point}_i$, the induction hypothesis says that $m$ is covered by some interval in $\text{gap}_i$.
Otherwise, $m\gt\text{last_covered_point}_i$. Since $m$ is not covered by $I_{i+1}$, we know $m<s$. So $m$ is covered by $[\text{last_covered_point}_i +1, s-1]$.

In both cases, $m$ is covered by some interval in $\text{gaps}_{i+1}$. Since $\text{last_covered_point}_i$ is the largest point covered by one of $I_1, I_2, \cdots, I_i$ and $s$ is the smallest point covered by $I_{i+1}$, $[\text{last_covered_point}_i +1, s-1]$ is a maximal gap.

Otherwise, we have $s\le\text{last_covered_point}_i$+1. We can also verify that $\text{gaps}_{i+1}=\text{gaps}_{i}$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_{i+1}$.

Finally, since step 4.2 says $\text{last_covered_point}_{i+1}=\max(\text{last_covered_point}_i, e)$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$, $\text{last_covered_point}_{i+1}$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$.
So, $P(i+1)$ is correct. $\quad\checkmark$.


Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests?

When talking about the complexity of SAT, we usually care only about the complexity in terms of input size. This is because the classes P and NP are defined this way: they are oblivious to what the input represents. Your formula, while depending on a small number of variables, will be very long.

3SAT is nicer in this regard, since assuming clauses don't repeat and every variable appears at least once, the number of variables, the number of clauses, and the bitlength of the input are all polynomially related, so from the point of view of complexity theory, any of them could serve as the parameter against which complexity is measured.

Moreover, I don't see why any particular choice of formula would "require a test for each subset of the group of variables". We don't know how to substantiate claims of this sort in the case of SAT.


Question related to Hilbert's 10th problem

As pointed by Yuval and cody there are easy solutions to get infinitely many Diophantine equations that are not provable nor refutable (let's say in PA).

However these syntactic solution result in provably equivalent sets, i.e. sets that the theory can prove they are equivalent. You can consider these as padding arguments. Another way is adding a variable which is not used at all.

You can also play with adding or removing some strings explicitly (finite variations of the set).

If you want to get Diophantine equations that are "essentially" different (e.g. the sets are not Turing equivalent) then that is more challenging and I think knowing that there is an independent Diophantine equation is not enough, you will need the fact that every r.e. set can be encoded as a Diophantine equation (or something similar).

ps: since you only care independence it is more natural to represent these formulas as Diophantine equations not their negations.