Can inputs in the decision tree model be computed?

A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia:

A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one child labeled $0$ (the left child in the diagram) and another child labeled $1$ (the right child in the diagram). The binary tree doesn't have to be complete as in the example above.
In order to evaluate the decision tree, you start from the root, evaluate the function written there, and descend to the left child or to the right child accordingly. You continue in this fashion until reaching a leaf, at which point you output the label written there.
The cost of a decision tree is its depth, or equivalently, the maximum number of edges in a root-to-leaf path.
The most common choice for the set $\mathcal{F}$ of allowed queries is $\{x_1,\ldots,x_n\}$. Linear decision trees are decision trees in which $\mathcal{F}$ consists of all linear threshold functions. Alegbraic decision trees of degree $d$ are decision trees in which $\mathcal{F}$ consists of all polynomial threshold functions of degree $d$.
Comparison-based algorithms can also be modeled by decision trees. Here the input is an array of length $n$, the output is a permutation of the positions of the array, and the allowed queries are comparisons.
Decision trees capture some properties of algorithms, and ignore other properties. They are most often used to prove lower bounds on algorithms solving a certain problem. For example, we can represent every comparison-based sorting algorithm as a decision tree. This representation completely ignores how difficult it is to decide what comparison to do next, and how difficult it is to generate the output given the results of past comparisons. Yet the model is useful, since it shows that every comparison-based sorting algorithm must make $\Omega(n\log n)$ comparisons in the worst case, and in particular, must have running time $\Omega(n\log n)$.
Kane, Lovett and Moran constructed linear decision trees of depth $\tilde{O}(n)$ solving the 3SUM problem. In contrast, the 3SUM conjecture states that no RAM-based algorithm for 3SUM runs in time substantially better than $O(n^2)$. This is one case in which the decision tree model isn't able to capture the hardness of a problem.
The main point here is that proving lower bounds on computation time is hard. The only lower bounds we know how to prove are in restricted models, or on a specific type of resource, such as queries in the decision tree model, or communication in the communication complexity model. These models abstract away computation but capture some pertinent properties which suffice for proving meaningful lower bounds in many cases.
We can now answer your questions one by one:

The decision tree model is really a family of models, parametrized by the set $\mathcal{F}$ of allowed queries. As a user of the decision tree model, you get to decide which queries you allow.

The decision tree model is a non-uniform model. You can use whatever functions from $\mathcal{F}$ that you wish. Unless stated specifically, there is no requirement that there be an efficient procedure that constructs the decision tree for inputs of given length.

The most common measure of complexity for decision trees is depth. Another measure of complexity sometimes used is size; in this case, we sometimes allow DAGs (known in this context as branching programs) rather than just (directed) trees. Enlarging the set $\mathcal{F}$ of allowed functions can reduce the complexity.

For the specific case of linear decision trees, it is known that arbitrary weights can be reduced to polynomial weights at the cost of increasing the depth by at most 1, see Goldmann and Karpinski, Simulating threshold circuits by majority circuits. (The models are not the same, but it seems likely that the conclusion still holds.)
Another example where comparing more complicated linear functions can make a large difference is 3SUM. The decision trees constructed by Kane, Lovett and Moran have sparsity 6, while an earlier lower bound of Ailon and Chazelle (cited in [KLM]) shows that sparsity 5 cannot achieve depth $\tilde{O}(n)$.


Is the balanced parentheses language inherently ambiguous?

$$S \rightarrow (S)S$$
$$S \rightarrow \epsilon$$

Generalising this to other Dyck languages is left as an exercise.


Using existential quantifier within implication

Your statement attempts to be express in formal logic the following sentence:

  There exist $\sigma_{opt}$ and $n$ in $R^+$ such that if $0 < n < 1$ then $\sigma_{opt} = n$.

The attempt at translation goes about by replacing English words by mathematical symbols, while keeping English syntax. Unfortunately, that is not how this sort of translation works. Just as when translating between human languages the syntax needs to be changed, here as well you have to conform to the syntax of statements in predicate logic. Your statement is, unfortunately, ungrammatical (more formally, it is not well-formed, that is, it is not a wff).

The syntax of sentences in predicate logic is described in many sources, so let me just mention that the following sentence is valid:
$$
\exists \sigma_{opt} \in R^+ \exists n \in R^+ \; (0 < n \land n < 1) \to \sigma_{opt} = n.
$$
We often allow shortcuts to be used, and so consider the following statement to be valid as well (standing for the former statement):
$$
\exists \sigma_{opt},n \in R^+ \; 0 < n < 1 \to \sigma_{opt} = n.
$$
You are using a different shortcut for folding the two existential quantifiers, but your convention is not standard; it's better to use standard conventions, unless there's a good reason to deviate from standard practice.

Finally, I'm not sure what your statement is supposed to express, but it probably doesn't express what you were hoping for: it doesn't depend on any parameter (this is why it's a statement rather than just a formula), which was probably not your original intention.


Space Complexity measures the amount of space it takes to carry out a specific task (as a function of the input size). It is very similar to time-complexity, that measures the amount of time it would take to complete the task. In both cases, the complexity highly depends on the specific model of machine (RAM machine is faster than a double-tape Turing Machine, which is in turn faster than a single-tape Turing Machine).

Let's now focus on a specific simple model: Single-tape TM.

Example: Sorting

Consider a simple task: say, sorting. The input is a list of numbers $x=\{a1, a2, ...\}$ and the machine should write them in order. The size of the input is $|x|=n$.

One way to perform this task on a single-tape Turing machine, is to perform a Merge Sort: we look at the first number $a1$, split the list into two list, one for numbers that are larger than $a1$ and the second list with the other numbers (and then we repeat it recursively).

But how do we implement "spitting the list into two" on a single-tape TM?
A possible solution will mark the end of the input, then go over the list $n$ times, and every time it finds a number that should be on the second list, it will move it to the end of tape.
So, if we started with $n$ numbers, now we have a list of $2n$ places (some of which will be empty, since we "moved" the numbers to somewhere else). If we continue with this naive approach, we will keep increasing the space in use more and more, and will get a very large space complexity (say $n^2$ if we stupidly double the space at each phase of the recursion).

But there is a more efficient way to do it: after creating two lists, we can "close the empty gaps" that occurred when we moved elements. Since we never add or remove elements, the same amount of space we started with is always big enough to keep the intermediate lists.
For this approach we might need to maintain some counters that will tell us where each list begins and ends. Using smart methods, this can be done very efficiently, so that we will never use more than $\approx 2n$ cells of the tape. That is, the space complexity is $O(n)$ in this case.
 (see also In-place merge sort, which is not exactly what I was talking about, but might give you more intuition)

Now you can also see that Space and Time are related. If we perform the space-efficient variant, the TM needs to do some extra-work of "closing gaps", marking start and end points, keep track of counters, etc. This extra work takes time.
It is very common that there is a tradeoff between space and time:
if the algorithm is very fast, it takes a lot of memory, and if it is very space-efficient then it takes more time. For the task of sorting, see a table comparing the time and space complexity of various sorting algorithms. (Note that in that table they count the space complexity excluding the input).

Space complexity and its relation to Time complexity

So now we can define the space complexity of "sorting" as the minimal space it takes to sort. That is, take the most-efficient (memory-wise) sorting algorithm. How much space does it take to sort $n$ elements? This is the space complexity of sorting.

More generally, we can define classes of tasks that take the same space complexity. For instance $DSPACE(n)$ contains all the tasks that can be solved using $O(n)$ memory. Said differently, it contains all the tasks whose space-complexity is at most $O(n)$

There is a strict hierarchy here: If we know that a task needs $O(n)$ space, it clearly cannot be in $DSPACE(1)$. More accurately, for any function $f(n)$,
$$ DSPACE( o(f(n)) \subsetneq DSPACE( f(n)).$$

Finally, we can relate time and space:
$$DTIME (f(n)) \subseteq DSPACE(f(n)),$$
since in $x$ time we can access at most $x$ cells of the tape. More interestingly, we know that
$$DSPACE(f(n)) \subseteq DTIME(2^{O(f(n))}).$$
That is, whatever task that we can solve using $x$ bits of memory, we can also solve using in at most $2^{O(x)}$ time-steps. This follows since a machine with $x$ memory has  maximal number of $2^{O(x)}$ different configurations, so if it doesn't go into an infinite loop it must end in less than $2^{O(x)}$ time.


qsort is not Quicksort. qsort is whatever the implementor of the standard library decided.
Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time.
Radix sort of 50 million numbers with six digits is obviously nonsense. Six digits means you expect only 64 different values and therefore would use counting sort. With less than 26 digits it doesn't make sense.
Your radix sort does an awful lot of copying, and worse, uncached copying.
Your radix sort doesn't produce a correctly sorted result if digits is an odd number.
Your qsort call doesn't produce a correctly sorted result if the array contains very large and very small numbers.


Match students and teachers based on ranking

Your problem differs from stable marriage problem in a minor way. A teacher can have 4 students maximum. You will have to fix the maximum students allotted to teacher (you may not have 3-4, if you also prescribe minimum number of students then you might have to dig deeper).

Now you can do two things, first, have four copies of each teacher and solve the stable marriage problem. Second solution is essentially like first but you keep a list of 4 "engagements"  for each teacher.


I think you can answer this in $O(n)$ time with a recursive algorithm, as follows.  It basically boils down to an ugly case analysis.

Over the real numbers

Let me start by assuming you are working over the real numbers, to make it easier to present the ideas.

Suppose the range is $(r_1,r_2,\dots,r_n) \ldots (s_1,s_2,\dots,s_n)$ and the bounding box has corners $(b_1,\dots,b_n)$ and $(c_1,\dots,c_n)$ with $b_i \le c_i$ for all $i$.  There are four cases:

If the intervals $[r_1,s_1]$ and $[b_1,c_1]$ don't overlap, then there is no overlap between your range and your bounding box.
If $r_1=s_1$ or $r_1=c_1$, then check whether $b_1 \le r_1 \le c_1$ and then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $r_1$ (i.e., the range is $(r_2,\dots,r_n) \ldots (\infty,\dots,\infty)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
If $r_1<s_1$ and $s_1=b_1$, then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $s_1$  (i.e., the range is $(-\infty,\dots,-\infty) \ldots (s_2,\dots,s_n)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
Otherwise, the intervals $[r_1,s_1]$ and $[b_1,c_1]$ overlap at more than two points.  In this case, there is guaranteed to be an overlap between your range and your bounding box.  In particular, pick a value $x_1$ that is in the overlap and such that $r_1<x_1<s_1$; then $(x_1,b_2,\dots,b_n)$ is in the range and in the bounding box.

It is easy to see that this runs in $O(n)$ time, because the running time satisfies the recurrence $T(n) = T(n-1) + O(1)$.

Over the integers

If you are dealing with integers, then it suffices to add the following cases just before the "Otherwise":

If $s_1=r_1+1$, recurse twice: recurse on the range $(r_1,r_n,\dots,r_n)\ldots (r_1,\infty,\dots,\infty)$ and recurse again on the range $(s,-\infty,\dots,-\infty) \ldots (s_1,s_2,\dots,s_n)$ (leaving the bounding box alone).  If either of them finds a point of overlap, then you have found an overlap between your range and your bounding box.  (*)
If $c_1=b_1+1$, then there is a point of overlap.  (If $r_1<b_1<c_1\le s_1$, use $(b_1,\dots,b_n)$); if $r_1 \le b_1<c_1 < s_1$, use $(c_1,\dots,c_n)$); those are the only two possibilities.)

The running time with this modification remains $O(n)$.  It takes a little more work to see why, though.  Naively, we obtain the recurrence $T(n)=2 T(n-1) + O(1)$, due to need to recurse twice in the case marked (*); and this recurrence satisfies $T(n)=O(2^n)$, which is very bad.  Fortunately, this is an overly loose upper bound.  Note that when $(r_1,\dots,r_n) = (-\infty,\dots,-\infty)$ or $(s_1,\dots,s_n)=(\infty,\dots,\infty)$, then we never invoke the case (*) in any subsequent recursion.  So, when running on one of those inputs, the running time is $O(n)$.  Moreover, the case (*) recurses on inputs of this form.  Thus, we will never invoke case (*) more than once in the entire recursion tree.  Thus, the entire recursion tree can involve at most $2n$ recursive calls.  Thus, the total running time remains $O(n)$.

This algorithm looks a pretty messy, with at least 6 different cases.  Perhaps there is a cleaner way to do it.


How is this expression a valid lambda expression?

When in doubt, write down a lot of parentheses:
$$\lambda x . ((x ((\lambda y . ((y y) x)) x)) x)$$
and
$$\lambda x . ((x (x x)) x)$$
In $\lambda$-calculus there is the convention that $A B C$ is understood to be $(A B) C$, that is, application associates to the left. So, if somebody wants to $A (B C)$ instead, they have to put in some parentheses.


ILP and number of variables in constraints

There are no hard rules for which formulation would be better especially for mixed-integer problems, however

The time to solve an lp relaxation usually increases with the number of nonzeros in the constraint matrix, but
Tighter lp relaxations usually reduce the number of lp relaxations that need to be solved.

To take your example, suppose you have a variable $y$ that is 1 only if all variables $x_0, x_2, \ldots, x_{n-1}$ have value 1, and all values are binary.  You could write a single constraint
$$ny \le \sum_{i=0}^n x_i$$

or $n$ constraints
$$y \le x_i, \forall i \in \{0, \ldots n-1\}$$

Both sets of constraints will have the same integer-feasible set, but the $n$ constraints have a much smaller continuous-feasible set, so it is probably be much faster to solve.


Is the BPP class closed for union and intersection?

Let $T_1$ (resp. $T_2$) a polynomial-time probabilistic Turing machine with error probability of at most $1/3$ for $L_1$ (resp. $L_2$).
Let $T'_1$ (resp. $T'_2$) be a Turing machine for $L_1$ (resp. $L_2$) obtained by running $T_1$ (resp. $T_2$) $9$ times and returning the majority result.
The error probability of $T'_1$ (resp. $T'_2$) is at most $p_F = \sum_{i=5}^9 \binom{9}{i} (1/3)^i (2/3)^{9-i} < \frac{1}{6}$.
A Turing machine for $L_1 \cup L_2$ (resp. $L_1 \cap L_2$) simulates $T'_1$ and $T'_2$ and accepts if and only if at least one of (resp. both of) $T'_1$ and $T'_2$ accept.
By the union bound, the probability of error of this Turing machine is at most $2 \cdot p_F < 2 \cdot \frac{1}{6} = \frac{1}{3}$.


Is it possible for a Turing machine to halt without reading the complete input string?

Nothing special happens if the Turing machine doesn't read the entire input. For example, the machine can halt immediately, without looking at the input at all. If the Turing machine halts at an accepting state, then the input is accepted. If it halts at a rejecting state, then the input is rejected. In this way you can construct a Turing machine that accepts all inputs or that rejects all inputs, in both cases without looking at the input string at all.

In your example, the machine accepts "adc" iff it accepts "a".


Basic question about backjumping in SAT solvers

The intervening assignments between the current assignment and the backjump point might have been arrived at via considerable backtracking and backjumping themselves and it would be wasteful to repeat all that work.  But in the context of a modern solver that work may not need to be repeated, because:

Any conflicts that occurred during the intervening assignments should have produced conflict clauses that rule out those time-wasting bad assignments in the immediate future.
Some solvers implement "phase saving" which remembers whether a variable was assigned true or false across backjumps (and restarts).  So when DPLL chooses that variable again as a decision variable it will use the same true/false value, essentially picking up where it left off before the backjump.
The intervening assignments may not be repeated in the same order after the backjump.  Solvers have heuristics that decide which variable becomes the next decision variable.  These heuristics usually give preference to variables recently involved in conflicts, which usually has the effect of shuffling the decision variable order after every conflict.

There is another reason to backjump past 7 and then assert -3 and that is because of the way two-watched-literals works.  Two-watched-literals is a clever algorithm for noticing when clauses are made unit by an assignment.  It uses a lazy data structure that does not need to be updated for every clause referenced by an assignment and more importantly does not need to be updated at all when backtracking or backjumping.  You can assume every SAT solver that implements DPLL also uses this algorithm to track unit clauses.

But in order for the lazy data structure to work there are procedural rules that must be followed.  One of them is that you must roll back decision variable assignments and their unit propagations as a group.  So to use your example, if -3 were asserted after the 7 assignment instead of before it and the 7 assignment were ever rolled back, then the -3 assignment would be undone separate from the |6 1 2 assignments that caused it.  This would leave clause C, [-1 -2 -3], as a unit clause but two-watched-literals would not detect it.  DPLL search is now broken and the solver may be confused enough to later claim that it has a satisfying assignment when it doesn't.  If -3 is asserted together with the other consequences of the 6 assignment, then all the implications of that assignment will be rolled back together as they must be.


In order to make sure $3)\implies1)\,$ is true, let us assume that all costs of edges are different. Otherwise, there is a counterexample at Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?.

Here is a hint to prove $3) \implies 1)\,$. Suppose you have some MST $T'$. Show that $T$ and $T'$ have the same number of edges.  Show that $T'$ must contain every minimal cut.


Algorithm to save state of array as it changes

In the following we assume that whenever we make a delete-operation, the value to delete is guaranteed to exist in the array, and if multiple copies of it exist, we should remove its leftmost appearance.

The problem can be solved in $\mathcal{O}(\log n)$ per update, and in linear time (with respect to the output size) per query with standard persistent trees (tree traversal is linear time). The only issue is that since our ordered set is ordered by index, not value, we need a map (that doesn't have to be persistent) that translates from index to value. To not degrade the complexity, add a two-way link between nodes representing the same value in the current persistent tree and the map. These links are easy to maintain with no overhead.

If the input values are bounded, since the only query we are interested in is outputting the entire list at a specific time, we can improve on this. If the values are at most $m$, and we can use $\mathcal{O}(n + m)$ memory, we can make $n$ operations in $\mathcal{O}(n)$ time, and answer queries in linear time (with respect to the output size). To do this, we store snapshots of the array and the incremental changes between them.

Let $k$ be the highest amount of elements that have been on the current list since we last took a snapshot. We will take a new snapshot when we have deleted at least $\lceil\frac{k+1}{2}\rceil$ elements. This way we only need to apply a linear number of operations (in output size) to produce any array: if the output size is $n$, we apply at most $n+1$ deletions (since $\frac{n + (n+1) + 1}{2} = n+1$), and thus at most $2n+1$ insertions.

How to then produce the array? Start from the latest snapshot before it, then apply all of the insert-operations. Then, for each delete-operation, increment the delete-count of its respective value (stored in an array of size $\mathcal{O}(m)$. Replacing this with a map would give a $\mathcal{O}(\log n)$ overhead to both operations and queries). Then loop through the array produced after all insertions, at each point checking if the delete count of the value there is nonzero. If it is, we delete that value and decrement the count. Otherwise we proceed as normal. This takes linear time in the size of the snapshot and the number of operations we apply, which is linear in the size of the output.

It remains to show that this method of storing snapshots only uses $\mathcal{O}(n)$ memory. We show this by induction: After $n$ operations, the total size of snapshots up to that point is at most $n$. This holds initially, since we have no operations and one snapshot of size $0$. Say the previous snapshot was at time $n_0$ and was of size $s_0$, and now after $a$ insertions and $b$ deletions, we are taking another snapshot. The size of this new snapshot is then $s_0 + (a - b)$, and by induction the total size of snapshots at most $n_0 + (s_0 + (a - b))$. Thus it suffices to prove that $n_0 + a + b \geq n_0 + s_0 + (a-b)$, but this is equivalent to $2b \geq s_0$, which trivially holds, since $2b \geq 2\lceil \frac{s_0 + 1}{2} \rceil \geq s_0 + 1$.


Show that language of distinct binary strings is irregular

Suppose that the pumping length is $n$. Consider the string
$$
w = [0^n,0^{n-1},\ldots,0].
$$
You take it from here.


Zero-based array implementation with logarithmic insertion time

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL.

In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a rope, which is a stronger kind of string (see Wikipedia). Ropes are designed for exactly this purpose.


Why add S0 -> S while converting CFG to Chomsky Normal Form

This has to do with the fact that grammars in Chomsky normal form cannot generate the empty word. Indeed, if we only allow rules of the form $A \to BC$ and $A \to a$, then it is impossible to generate the empty word.
In order to accommodate languages containing the empty word, we allow the transition $S \to \epsilon$, where $S$ is the starting symbol. For various reasons (for example, the proof of the pumping lemma), we still don't want any other symbol to generate the empty word, so we disallow $S$ on the right-hand side.
The transition $S_0 \to S$ allows us to treat $S$ as a normal symbol, that is, to allow it to appear on the right-hand side, even if the grammar generates the empty word.


As pointed out in the previous answer, you cannot do very well if you simply assume that your input is a connected graph. However, you can do better if you make certain assumptions on your graph's structure. That is, one can ask: given a class of graphs $\mathcal G$, will the clique problem be solvable in polynomial time, assuming that all inputs are contained in $\mathcal G$?

The answer turns out to be positive for a nice class (or should I say classes) of graphs: graphs whose treewidth is bounded by a constant.

Without getting into too much detail (see http://en.wikipedia.org/wiki/Tree_decomposition for more details), the tree-width of a graph is a measure of how much it "resembles" a tree. Trees have a treewidth of 1, whereas cliques have a treewidth of $n-1$ (where $n$ is the number of vertices).

The clique problem is $\mathcal O(t^t n)$ on graphs whose treewidth is at most $t$.

Treewidth is believed to be the "right" measure for graphs problems (although more complex measures do exist): Courcelle's Theorem (see http://en.wikipedia.org/wiki/Courcelle's_theorem) states that any graph property that can be succinctly expressed via some logical parameters can be solved in polynomial time on graphs with treewidth bounded by a constant. This includes vertex cover, clique, independent set, and many others.

This means that many NP-hard graph problems are fixed parameter tractable, with treewidth being the parameter.

Hope this helps.


Simplifying this expression with big O when several variables are involved

All is correct, but - it can be done in one step after you represent this expression as a sum of terms:
$$\mathcal{O}(3m+2m⋅n⋅p+p⋅n+p⋅m)=\mathcal{O}(m⋅n⋅p)$$
because:

The term $(m⋅n⋅p)$ dominates all the other terms - $(3m)$, $(p⋅n)$, and $(p⋅m)$ - in this sum.
Constants are eliminated according to the $\mathcal{O}$ definition.


The author suggests that you become aware of the kinds of problems that graph algorithms can solve, rather than on the details of these algorithms. To give an example from a different field, it is much more useful to know that linear programs can be solved than to understand how the simplex algorithm works. Another example closer to the subject matter is maximum flow – again, it is more important to be familiar with the problem than with any algorithm for solving it.

You can always look up the algorithm that solves a particular problem – and if you're lucky, perhaps somebody already implemented it in some library. But you have first to know which known problems to reduce your own problem to.


Why isn't it simple to count the number of words in a regular language?

Yep, this is wrong, because of ambiguity.

Consider the following language:
$(a + aa) + a(a + \epsilon)$.

With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.

A better method is to use dynamic programming on an minimal DFA for your language, with no "dead" states. If the minimal DFA is cyclic, the language is infinte, so we can assume there's no cycles. Using a DFA is key, because the determinism means there's exactly one path through the DFA for each word.

What you do is build up a recurrence for the number of words that end at a given state:

1 words ends at the start state: $\epsilon$
For each state $q$, the number of words ending there is the sum of the number of words ending at each state with a transition into $q$.

The total number of words is then the sum of the number of words ending at each final state.


"For small values of n, O(n) can be treated as if it's O(1)"

This is largely piggy-backing on the answers already posted, but may offer a different perspective.

It's revealing that the question discusses "sufficiently small values of n".  The whole point of Big-O is to describe how processing grows as a function of what's being processed.  If the data being processed stays small, it's irrelevant to discuss the Big-O, because you're not interested in the growth (which isn't happening).

Put another way, if you're going a very short distance down the street, it may be equally fast to walk, use a bicycle, or drive.  It may even be faster to walk if it would take a while to find your car keys, or if your car needs gas, etc.

For small n, use whatever's convenient.

If you're taking a cross-country trip, then you need to look at ways to optimize your driving, your gas mileage, etc.


What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

It is well-known that the number of non-negative integer solutions to $x_1+\dots+x_a = b$ is $\binom{a+b-1}{a-1}$, and the number of positive integer solutions is $\binom{b-1}{a-1}$. To see the latter, notice that a set $1 \leq i_1 < i_2 < \cdots < i_{a-1} \leq b-1$ corresponds to the solution $x_1 = i_1$, $x_2 = i_2 - 1$, ..., $x_{a-1} = i_{a-1} - i_{a-2}$, $x_a = b - i_{a-1}$.

Therefore the number of ways to fill your array is
$$
\binom{S-1}{N-1} \cdot S!, \text{ where } S = S_1 S_2 \cdots S_D.
$$
Indeed, if you sort each filling then you get $x_i$ many $i$'s for $0 \leq i \leq N-1$, where $x_i \geq 1$ and $\sum_i x_i = S$.

You can generate all the fillings by first generating all solutions to $x_0 + \cdots + x_{N-1} = S$ (which you can do recursively, for example, or using an algorithm for generating all subsets of $[S-1]$ of size $[N-1]$, and converting each subset to a solution in the obvious way), filling the array in nondecreasing order accordingly, and then generating all permutations (a well-known problem).


Getting a tighter upper bound on the following function

Let's count how many times we have to make a call into fib for each value of n. Let's call that number $f(n)$.

Then:

$$
\begin{align}
f(0) &= 1 \\
f(1) &= 1 \\
f(n) &= 1 + f(n-1) + f(n-2) \qquad \textrm{(for $n > 1$)}
\end{align}
$$

The first several values for $f$ are then 1, 1, 3, 5, 9, 15, 25, 41, 67, etc.

It turns out that if you add one to $f$ and half the result,(*) you get the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is, $f(n) = 2\cdot\textrm{fib}(n+1) - 1$

Since it is well known that the Fibonacci function is $O\left((\frac{1+\sqrt{5}}{2})^n\right)$, so is $f(n)$.

Note that since $\frac{1+\sqrt{5}}{2} \approx 1.618 > 1.6$, the book is actually technically incorrect when it says that $O(1.6^N)$ is an upper bound, and should be corrected to say $O(1.62^N)$ or something similar.

(*) Okay, I kind of pull that out of a hat. As for how to mentally jump from a recursion that's almost like one you know but off by a constant (as in this case, the recursion formula for $f$ looked like the recursion for fib but had that annoying $1+$ at the beginning) one technique is to say:

"What if $g$ were something that obeyed fib's  recursion rule, and $f(n) = g(n) + C$ for some constant $C$. What happens when I substitute that into my recursion equation?"

You then end up with:

$$ g(n) + C = 1 + g(n-1) + C + g(n-2) + C $$

Using $g(n) = g(n-1) + g(n-2)$, you find that $C$ is $-1$. From that you see "Oh, $1+f(n)$ should look kind of like the Fibonacci series, but it starts with "2, 2", so..." (and then it's straightforward to write a formula for $f(n)$).


This is an incomplete question because you have no base case; A[-3, -3] is not defined, for example. But let's assume we're looking at a window into a larger array, so those values have some consistent, distinct and independent value.

Denote those predetermined values with #, and look at the top-left corner. The values we can fill in are those three topmost rows and three leftmost columns, denoted by ·.

# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·

Doing those in parallel means that you need to take n / 3 sequential steps. Since the matrix is square, exclusively going down balances the costs better, but still gives you n / 3 sequential steps with parallelism of 3n.

This is remarkably excessive for a typical CPU for significantly sized n; rather you should be streaming memory into SIMD operations as fast as possible. You can do a straightforward N-wide SIMD loop over the x-axis.

A[i:i+N, j] = A[i-4:i-4+N, j-4] + A[i-3:i-3+N, j-3] + B[i:i+N, j]

This probably won't max out your bandwidth entirely, but it will get pretty darn close and it's unlikely you can get more from a multicore algorithm, though you are free to try partitioning the work along diagonals.


Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

Yes.  The following algorithm yields $O(n^2)$ answers (remember what $O(\cdot)$ means!) but it runs in time $O(n)$.

halt;

You probably meant to ask if an algorithm that yields $\Theta(n^2)$ answers can run in time $O(n)$. The answer to that is no. Whatever exact definition you choose for "yielding an answer", yielding one answer must take at least one computation step in any reasonable model of computation, so writing $\Theta(n^2)$ answers must take $\Omega(n^2)$ steps.


Is computer science really a branch or sub-branch of physics?

No it is not. Computer science has as much to do with computers as astronomy does with telescopes: they're a tool.

Even if computers didn't exist the science of computing things still would. IMO Computing Science would be a much better name, but we're stuck with what we have I guess.


Constructing a Pixel Image from Rectangles and Row or Column Rotations

Yes.  For every image, there exists some sequence of operations that generates that image.

I'll describe how to implement a set (x,y) operation, which sets the pixel in the xth row and yth column (and leaves all other pixels unchanged).  It should be clear that you can construct any image you want by repeatedly applying this primitive.

Here's how to implement the "set (x,y)" operation using the 3 operations you gave us:

Rotate column y upwards by x-1 positions, so that position (x,y) moves to position (x,1).
Rotate row 1 leftwards by y-1 positions, so that position (x,1) moves to position (1,1).
Set the pixel in the upper-left corner (the pixel at position (1,1)).
Rotate row 1 rightwards by y-1 positions, so that position (1,1) moves back to (x,1).
Rotate column y downwards by x-1 positions, so that position (x,1) moves to position (x,y).

It is easy to see that each of these 5 steps can be done using one of your three operations, and that afterwards, the pixel at (x,y) is set and all other pixels are left unchanged.

This shows that given a image with dimensions mxn, we can create it using at most 5mn operations.  Of course, this sequence of operations probably isn't the shortest possible.  I don't know whether there is an efficient algorithm to find the shortest sequence of operations to generate a target image.


Minimise simultaneous equation remainder

This problem is an instance of linear programming.

If you allow fractional multiples then it can be solved in polynomial time using standard techniques for linear programming.

If you require integer multiples the problem is (strongly) $NP$-complete. There is a very easy reduction from 1-in-3-SAT. Let the dimension of the vectors be equal to the number of clauses, let the target vector be $(1,\ldots,1)$ and for every variabele create a vector $a_i$ that for each clause it appears in has a $1$ in that position (and a $0$ otherwise). You can achieve distance $0$ if and only if the formula is satisfiable.


Changing a matrix to become an ancestry matrix

TL;DR: I prove the variant of this problem in which we can only change matrix entries from 1 to 0 is NP-complete. (I think the original version is NP-complete too, but haven't proved this.)
Rooted Transitive Tree Editing
Another way of stating this problem is to ask for the minimum number of edge changes (additions of new edges or deletions of existing edges) needed to change a given digraph into the transitive closure of a rooted tree -- that is, a rooted tree augmented with all edges $uv$ whenever there is a path from $u$ to $v$. Let's call this graph a rooted transitive tree, and the decision form of this problem "Rooted Transitive Tree Editing":
Given a digraph $G=(V',E')$ and an integer $q$, is it possible to turn $G$ into a rooted transitive tree with at most $q$ edge edits?
I'll call the variant of the problem in which we are only permitted to delete edges "Rooted Transitive Tree Deletion". In the language of the original problem, in this variant we are only allowed to flip matrix entries from 1 to 0. This deletion variant of the problem is NP-complete by reduction from a slightly restricted form of Partition Into Triangles (PIT), as I'll show below. I suspect the full editing version can be shown to be NP-complete using a similar reduction, probably involving making the "handle" gadgets longer paths -- suggestions/extensions welcome!
The basic idea is to create a "triangle handle" vertex for each of the $O(n^3)$ triangles in the input graph, make each input vertex a descendant of the handle of every triangle it belongs to, and then look for a way to keep only the edges from the input graph that are used in a partition into triangles, and only the edges to handle vertices of triangles in this partition, deleting all other edges.
Partition Into Triangles
In Partition Into Triangles, we are given an undirected graph with $3n$ vertices, and ask whether it is possible to partition the vertices into triangles. P. 192 of "Computers and Intractability: A Guide to the Theory of NP-Completeness" (Garey and Johnson, 1979) indicates this problem is NP-complete. Here we need a slightly restricted form of the problem in which every vertex is covered by some triangle. The following simple reduction from the general problem shows the restricted version is still NP-complete. Attach a separate "diamond" to each vertex -- that is, for each $v_i, 1 \le i \le |V|$, add the vertices $x_i$, $y_i$ and $z_i$, and the edges $v_ix_i$, $v_iy_i$, $x_iy_i$, $x_iz_i$ and $y_iz_i$. Every vertex in the modified graph is covered by a triangle, and since the only triangle covering $z_i$ is $x_iy_iz_i$, it must always be chosen, leaving $v_i$ available as before.
Construction
Let $G=(V,E)$ be the input PIT instance, with $|V|=3n$. Let $t$ be the number of triangles in $G$. Note that $t \le {|V| \choose 3}$ and can be computed in polynomial time. We construct an instance $R=(V', E', k)$ of RTTD as follows:

Create a "plain" vertex $v_i'$ for every vertex $v_i \in V$.
Create the directed "plain" edges $u_i'v_i'$ and $v_i'u_i'$ for every undirected edge $uv \in E$.
For the $j$-th triangle $v_av_bv_c$ in $G$:

Create a "handle" vertex $h_j$.
Create the directed "handle" edges $h_jv_a'$, $h_jv_b'$ and $h_jv_c'$.

Create a root vertex $r$, and directed edges from it to every other vertex.
Set the threshold parameter $q$ to $3t+2|E|-2|V|$.

$G$ is a YES-instance of PIT $\implies$ $R$ is a YES-instance of RTTD. First notice that between any two adjacent vertices $u'$ and $v'$, at least one of the two opposite-pointing directed edges must be deleted. Also, for any triangle $v_iv_jv_k$ in $G$, 3 of the 6 resulting directed edges in $R$ can be deleted so as to produce a transitive 3-path, e.g.:
vj
| \      Edges are directed from high to low
|  \
|   vi
|  /
| /
vk

A partition into triangles uses exactly $|V|$ edges in $G$. Given a partition of $G$ into triangles, we delete all $2(|E|-|V|)$ of the directed edges in $R$ corresponding to edges not used by the partition. For each triangle, we also delete 3 of the 6 directed edges so as to produce a transitive 3-path as shown in the above figure (the order of the vertices in the path is unimportant) -- this deletes a further $|V|$ edges. Finally, we delete directed edges from handle vertices to plain vertices for all unused triangles: There are $t-|V|/3$ unused triangles, each of which has 3 such edges. The final digraph is a rooted transitive tree, and we have deleted in total $2(|E|-|V|)+|V|+3(t-|V|/3)=3t+2|E|-2|V|=q$ directed edges, so $R$ is a YES-instance of RTTD.
$R$ is a YES-instance of RTTD $\implies$ $G$ is a YES-instance of PIT. We know there exists a subset of at most $q=3t+2|E|-2|V|$ directed edges, the deletion of which from $R$ yields a rooted transitive tree $R'$.
No directed edge from the root $r$ to any handle vertex can be deleted, since that handle vertex would then become a second vertex with indegree 0 (in addition to $r$), and a rooted transitive tree must have exactly one such vertex. Nor can a directed edge from $r$ to a plain vertex $v_i'$ be deleted, since by the assumption that every vertex is covered by a triangle, $v_i$ has some handle vertex $h_j$ for an ancestor, and the deletion of $rv_i'$ would imply the deletion of $rh_j'$, which fails as just described.
The budget of directed edge deletions must therefore be allocated between handle edges and plain edges. If a vertex in $G$ participates in multiple triangles, its corresponding plain vertex in $R$ will have multiple handle vertices as ancestors -- but since no handle vertex is the ancestor of any other handle vertex, each plain vertex can choose at most one handle vertex to be its parent in the edited digraph $R'$, and must delete directed edges from all other handle vertices. Thus at most $|V|$ handle edges can survive, meaning that at least $3t-|V|$ handle edges must be deleted in any solution.
We now wish to show that plain edges will be deleted so as to ensure that each handle vertex is either totally "full" or totally "empty" -- that is, that for any handle vertex, either all 3 of its out-edges are preserved, or all 3 are deleted. Say that a vertex in $G$ is assigned to triangle $j$ if $h_jv_i'$ is preserved in $R'$ (not deleted). Each triangle is assigned between 0 and 3 vertices, inclusive. We will show that any valid assignment -- that is, an assignment in which every triangle is assigned either exactly 0 or exactly 3 vertices -- preserves strictly more plain edges, and thus requires strictly fewer deletions of these edges, than any assignment in which some triangle is assigned 1 or 2 vertices.
A valid assignment preserves $|V|$ plain edges, meaning that $2|E|-|V|$ plain edges must be deleted, which together with the $3t-|V|$ handle edges that must be deleted requires a total of $3t+2|E|-2|V|$ edges.
Notice that for any pair of vertices assigned to distinct triangles, there must be no directed edges between their corresponding plain vertices in either direction in $R'$, so if these 2 directed edges exist (i.e., if the vertices are adjacent in $G$) they must both be deleted. IOW, triangle assignments group plain vertices into connected components in $R'$.
Take the assigned vertex counts of the $t$ triangles and sort them in decreasing order. Doing so with a valid assignment produces a list $L^*=333\cdots3000\cdots0$, with $|V|/3$ 3s followed by $t-|V|/3$ 0s. Suppose we have an invalid assignment, producing a list $L$ containing at least one 1 or 2. We will walk along these 2 lists 3 or 6 vertices at a time, comparing the number of preserved plain edges.

Each triangle assigned 3 vertices preserves 3 plain edges (see ASCII art diagram).
Each triangle assigned 2 vertices preserves 1 plain edge.
Each triangle assigned 1 or 0 vertices preserves 0 plain edges.

The longest common prefix of $L$ and $L^*$, consisting of 3s, preserves an equal number of plain edges. Following this, $L$ continues with one of the following cases (with cases having trailing 0s promoted to equivalent cases having trailing 1s):

111: Preserves 0+0+0=0 edges (vs. 3 edges for the corresponding 3 from $L^*$).
21: Preserves 1+0=1 edge (vs. 3 edges for the corresponding 3 from $L^*$).
2211: Preserves 1+1+0+0=2 edges (vs. 6 edges for the corresponding 33 from $L^*$).
222: Preserves 1+1+1=3 edges (vs. 6 edges for the corresponding 33 from $L^*$).

Each case preserves strictly fewer edges than does the valid assignment, and any subsequent cases are at least as bad due to the decreasing order. Thus any invalid assignment requires strictly more plain edge deletions and at least as many handle edge deletions, so a solution with $3t+2|E|-2|V|$ edge deletions implies a valid triangle assignment, from which a solution to the original PIT instance can be immediately read off.
The above establishes NP-hardness of the RTTD problem. Clearly the construction takes polynomial time, so the problem is furthermore NP-complete.


Is this a good approach for first attempt to create my own language and compiler?

That sounds like a fine way to start, and you'll become familiar with the issues involved.

How's it going?

At a certain point, consider learning more about programming language implementation techniques from

a book like Compilers: Principles, Techniques, and Tools (2nd Edition)
open courseware for MIT's Computer Language Engineering course
a MOOC like Udacity's Programming Languages: Building a Web Browser
Stanford's Programming Languages course

It's also worth investigating libraries to use such as parser generators, although some people swear by the recursive descent parsing approach as easier to build, also good at generating helpful error messages.

Another tip: It's easier to implement a programming language in a language like Clojure than Java. (Clojure is a modern Lisp dialect that's hosted on Java.) E.g. your intermediate representation could be a list of Clojure forms. They handle reading & writing as readable text, and you can construct & interpret (eval) them quicker and easier than text.


what is the general name of this problem?

The machine learning subfield you are asking about is called Data Stream Mining.

(However I'm not sure about its relationship to platform games)


This doesn't seem like a valid regular grammar; my instructor says it is

Your teacher is wrong, unless of course s/he does not adhere to the wikipedia definitions. It is "technically" equivalent to a regular grammar, but that is not a well defined concept. What can we allow as extensions that give us "technically" regular grammars.

There is a concept that is perhaps suited. That is self-embedding. A variable $A$ is self-embedding if $A\Rightarrow^*uAv$ for non-empty $u,v$. A grammar is non self-embedding if none of its variables is self-embedding. Every non self-embedding context-free grammar has an equivalent regular grammar, which was already observed by Chomsky. With this concept we extend the regular grammars, while we are certain to stay within the regular languages.

And, since you are asking more details, your instructor is wrong again on the single nonterminal remark. Such grammars also include $S\to aSb\mid \varepsilon$ for which every sentential form has (at most) one nonterminal, but for which the language is non-regular. In fact these languages are called linear, and form a family between regular and context-free.

Note that $S\to AB, A\to aA|\varepsilon, B\to Bb|\varepsilon$ defines a regular language (mixing leftmost and rightmost). On the other hand $A\to aB\mid\varepsilon, B\to Ab$ is nonregular. This exemplifies the non self-embedding distinction.


If a deterministic finite automaton recognizes a language, must that language contain every accepting input?

No.
The language (only one!) recognized by a DFA is the set of all inputs it accepts.
The definition of a DFA also includes its alphabet, so you have to consider that an intrinsic part of the DFA. If you change the alphabet at all, you now have a new and different DFA, which potentially recognizes a different language.


Description of resolution algorithm as it applies to SAT

What you are looking for is a proof of the completeness of resolution. Here is one example. The relation to DPLL is that a run of DPLL which terminates in failure can be converted to a resolution proof that the formula is unsatisfiable.


Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays

You can solve the issue by using some pointers. First, run counting sort algorithm on all arrays in $\Theta(n)$ (suppose all of them are in a set). In the meanwhile, when running the algorithm, set a pointer for each number of each array  to the sorted index of that number.

Using this data structure, you will have $k$ sorted arrays at the end.


What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

we can see how the computation tree grows with finite alphabet and rules even when using a DFA , consider the following :

We begin at 1 , then when reading a , we arrive at 1 and 2 , reading another a , 1 arrives at 1 and 2 , 2 arrives at 1 and 2 , so we are at 1,2,1,2 and so on , here is a part of the computation tree :

Hopefully you can see how the computation tree grows exponentially with every symbol , the arrows to the left represent the string read up to this level
Of course the same can be shown for a TM , you can imagine this DFA as a TM , which reads a symbol , writes nothing then goes to right , and you will yield same result
As for a relation , we know that every t(n) time nondeterministic single-tape Turing machine has an equivalent 2O(t(n)) time deterministic single-tape Turing machine.


Just concatenate all of the variables into a single, long vector.  In your case, you'll have a $2n$-dimensional vector:

$$v = (v_{1,x},v_{1,y},v_{2,x},v_{2,y},\dots,v_{n,x},v_{n,y})$$

where $v_{i,x}$ is the x-coordinate of $v_i$ and $v_{i,y}$ is the y-coordinate of $v_i$.  Now treat this as a function of $v$, i.e.,

$$f(v) = \sum_{i,j} (||v_i - v_j|| - d_{i,j})^2$$

This gives you an objective function $f: \mathbb{R}^{2n} \to \mathbb{R}$, which you can try to maximize.  For instance, you can apply the gradient descent method to $f$ (after computing the partial derivatives of $f$).

That said: for your particular problem, gradient descent might not work very well, unless you happen to have a starting point (initial value for $v_1,\dots,v_n$) that is close to the optimum value.  There might be many local optima that gradient descent could get stuck in.  The only way to know for sure is to experiment with a bit and see what happens.


How important is initial state for local search optimisation?

A good initial state can often be helpful.  I would guess that there is a significant chance that spending extra time to find a good initial state will be useful.
All we can say in general is that "it depends".  It depends on the specific problem and the shape of the fitness landscape.  If the problem has few or no local minima, the search might not be very sensitive to the initial state.  If it has many local minima, the search might be very sensitive to the start state, and a good start state might help again.  There are no universal answers that can be supplied.
Usually the only way to answer these questions is to try it and see.  With heuristics, there aren't any provable guarantees and it's often hard to make many predictions based on theory or analysis.


Is it possible to modify the linux assembler in order to modify what fuctions do?

While this is trivially possible, the fundamental flaw in your idea is that assemblers are not interpreters. Python programs are run by the Python interpreter, Swapping - and + in the Python interpreter would likely crash all Python programs. But normal programs are executed directly by the CPU. The assembler is not involved in their execution.


Hint: Such sets $A,B$ (sans the requirement of recursive enumerability) are called recursively inseparable. According to Wikipedia "it is possible for $A$ and $B$ to be recursively inseparable, disjoint, and recursively enumerable", and Wikipedia might have relevant examples.  (Even if not, now you know what term to look for in the vast sea of internet.)

Extra hint: Wikipedia does indeed provide two such examples:

$A$ is the set of encodings of TMs whose output is $0$, $B$ is the set of encodings of TMs whose output is $1$.
$A$ is the set of provable tautologies, $B$ is the set of refutable contradictions.


Optimal combination, given pairwise costs

This is a generalization of independent set.  In particular, if all edge weights are either 0 or 1, then there's a solution to your problem with total sum 0 iff there is an independent set of size k.  It follows that your problem is NP-hard.

More usefully, your problem is equivalent to the maximum edge-weighted clique problem, which asks to find the $k$-clique that maximizes the sum of edge weights between clique vertices.  (Your versions asks to minimize the sum rather than maximize the sum, but if we negate the edge weights it becomes equivalent.)  Here's one example of a paper that studies that problem, and describes some experiments with different approaches to that problem:

Solving the maximum edge weight clique problem via unconstrained quadratic programming.  Bahram Alidaee, Fred Glover, Gary Kochenberger, Haibo Wang.  European Journal of Operational Research, vol 181, 2007.

A literature search seems to turn up other papers on the subject as well.  (See also https://stackoverflow.com/q/16625964/781723.)


Does throughput includes CPU idle time also?

You are correct!

According to the defenition Throughput (in case of scheduling in OS) is :

  Number of processes that can be completed in a unit of time.

The process can use both the CPU or the I/O operations. So the I/O time and idle times and CPU time are calculated in throughput.

Note: CPU idle time is not calculated when you want to have the Utilization of the CPU. So in your case CPU Utilization is 42/47.


The meaning of "set" in NP-complete problem

It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are forbidden, then there is a simple polynomial time reduction from the former to the latter showing that if the first version is NP-complete, so is the second one.


pseudocode to split number value to array of numbers

num_to_arr(num):
   length_of_arr = log(num)+1 //log(num) base 10
   arr[length_of_arr]
   digit = 0

   while num > 0:
      digit = num % 10
      arr[length_of_arr - 1] = digit
      length_of_arr = length_of_arr - 1
      num = num / 10

return arr

This should do the job.


Can someone provide an introductory example of a certificate in complexity theory?

Suppose you are the verifier for SUBSET-SUM: "given a set $S$ of integers, is there a subset of $S$ whose elements sum up to exactly zero?" To show the problem is in NP, you must be able to efficiently verify that a solution I give you is correct. As the verifier, you only care about verifying solutions (not "finding solutions"!). You do not care where that solution might come from or who constructs it. Now, when you are given a subset, you can easily sum up the elements and announce whether or not those elements sum up to 0.

The example you mention is a problem that is also in P (clearly, we can solve it in polynomial time). Every problem in P is also in NP. We don't have to care about the certificate, but instead we can simply solve the problem in polynomial time. (Check the definition of NP if this feels confusing, but hopefully it doesn't).

You might also enjoy the question How can I verify a solution to Travelling Salesman Problem in polynomial time?


Why do we use dynamic memory allocation in general and why did we use it in this particular example?

If you declared array as int arr[n] then the memory might be allocated on the Stack and arr would exist as long as the function lis exists, i.e., it would be allocated locally in the lis. malloc on the other hand, would allocate the memory on the Heap and the array would exist until you explicitly free it using free. Nevertheless, as Yuval Filmus noted, memory allocation for the variable length arrays depends on compiler implementation and environment (for example underlying environment may have no distinction between heap and stack). In addition, the GNU C Compiler allocates memory for variable length arrays on the stack.

However, regarding the time or space complexity of the algorithm, it would not make any difference. In particular, the time complexity of an algorithm has nothing to do with its implementation in a particular language.


SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the number of balls landing into each bin isn't $n/k$ but rather has roughly Poisson distribution with mean $n/k$ (assuming $n/k$ is "small"). Thus you expect there to be a few bins which do get quite a few balls more than their share, and vice versa. A good hash table should be able to handle that – there are several approaches that you are probably aware of.

A similar situation happens when you throw $n$ balls into two bins. Rather than each bin getting exactly $n/2$ balls, the number of balls in each bin has roughly normal distribution with mean $n/2$ and standard deviation $\sqrt{n}/2$. Thus you expect one bin to contain roughly $\sqrt{n}$ more balls than the other.

Another similar situation concerns throwing $n$ balls into $n$ bins. Rather than an even allocation, you expect the maximum cell to contain roughly $\log n/\log\log n$ balls. However, if any given ball is given two options, and you put it in the lighter bin, then the maximum cell contains only roughly $\log\log n$ balls in expectation. This is one way of coping with your problem.


You are right that a 3CNF is, in particular, a CNF. The hint you give suggests that you find a reduction that, given a 3CNF $\psi$ on $n$ variables, constructs a CNF $\varphi$ such that $N(\psi) = 0$ iff $N(\varphi) = 1$, where $N(\chi)$ is the number of satisfying assignments of $\chi$. I can give a stronger hint: the reduction constructs a 4CNF $\varphi$ on $n+1$ variables such that $N(\varphi) = N(\psi) + 1$.


A programming language is a formal language, informally speaking a collection of words with a well-formed set of specific rules. As such, you can write down the definition of a formal language and thus a programming language on a piece of paper.

Also, if I've written down somehow digitally the definition of a programming language, surely you can represent and download that description. So then you might talk about an interpreter or a compiler for a language. That is not a programming language, that's an interpreter or a compiler. It's a program you might download.

If the question is "does a programming language exist outside of its description", the answer is no with the above definition: a programming language is defined by a formal language.


Best known (state of science) time complexity of an array access problem

Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions.

The underlying array is a dynamic array (let's call it $T$) : it has amortized O(1) complexity for insertion at the end. In the array, you store tuples of values and booleans : the boolean will be set to false when you delete, true when you insert. You also keep a stack / queue / some dynamic data structure with O(1) push and pop to keep the indexes of empty places in the array that were previously filled (i.e. they are not at the end of the array), let's call it $S$.

get(i) : if the boolean at i is true, return the elemet at position $i$ in $T$ : $O(1)$, otherwise return an error : no element at that position.
Insert(x) : if $S$ is empty, insert the element at the end (setting the associated boolean to 1) : $O(1)$ amortized with dynamic array. If $S$ is not empty : pop a position from $S$ and insert the element at that position : $O(1)$ as well.
Delete(i) : set the boolean at $i$ to false, and add $i$ to $S$. $O(1)$ as well.

The only downside of that method is that the array is never reduced, and therefore has size $O$(number of insertions) and not $O$(number of element).


When $f_i$ are given as black boxes, it takes $\Omega(n)$ in the worst case to compute their AND.

The constraints that the question puts on the functions $f_i$, don't really tell anything about $f_i$ and their behavior, maybe except for a very small subset of inputs. For instance, we can assume that over the inputs $x=0,...,n$ each $f_i$ is 1, except for the case where $x=i$. This satisfies all the constraints stated. But if $x>n$ we have no idea how $f_i$ behaves. As a trivial example, it can be that each $f_i$ has some infinite kernel (=values of $x$ that zeroize it), but the union of all the kernels doesn't cover the entire $\mathbb{Z}$. As a block box, it is not clear that you even have a compact way to describe each kernel, and you have no choice but querying the black box.

Even if the kernel of each function is known (and has a compact description), it can be that the most compact description of their union is "the union of the kernel of $f_1$ and $f_2$ and ...", which hints that one must compute each $f_i$ separately to know their AND value. For instance, if $f_1$ is the indicator function of all the prime numbers, and $f_2$ is the indicator of all odd numbers whose binary representation has an equal number of ones and zeros. Probably simpler examples can be found.


How to represent whitespace in a context-free grammar?

This is a classical confusion between language and metalanguage.

More generally, you have the same problem when you want to include in
your symbols, expecially terminal symbols, characters that have
syntactic meaning in the syntax of grammars, for example the symbol
"|" which is often used to give on the same line all possible
right-hand-sides for a given non-terminal.

In such a case, you do what I just did: use some mechanism for
quotation, such as "|", or " " in the case of a space. Some form of quoting is the usual technique to avoid confusion between language and metalanguage.
And as you remarked, the language of grammars already uses the space for its own (lack of) purposes.

So you write:

S -> xAx
A -> " "

Of course, the spaces outside the quotes still play the same role as before, wherever allowed. So the grammar could be written as well:

S ->  x A  x
A  ->   " "

Whatever is within quote must be written exactly as expected.

However, in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want one compulsory space where you have the terminal " ", or whether you forbid spaces, unless specified by the syntax as done here.

The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyser (whether LR(1) or any other) will ignore the quotes, as it ignores the arrow ->. It would work as well with a grammar written as [(S,xAx)(A," ")]. Some metalanguages for writing grammars, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions.

Another question you may want to look at is: What are the meanings of metalanguage and metasyntax and EBNF?


Let me start by answering a slightly different question:
Given a weighted graph $G=(V,E)$ on $n=|V|$ vertices, we want to find a maximum-weight matching of cardinality at most $k$.
Let $L$ be the largest edge weight in $G$, and define $L' = 2nL$. Transform the graph $G$ by adding $\ell =n-2k$ new vertices $v_1, \dots, v_\ell$, and all edges in $\{v_1, \dots, v_\ell\} \times V$. Each new edge has weight $2nL$. Let $G'$ be the new graph.
Compute a maximum matching $M$ of $G'$ and return the matching $M \cap E$.
If there is a matching $M$ of weight $\ell L' + x$ in $G'$ then there is a matching of weight $x$ and size at most $k$ in $G$.
There are exactly $\ell$ edges in $M' = M \cap (\{v_1, \dots, v_\ell\} \times V)$ since at most $\ell$ edges in $\{v_1, \dots, v_\ell\} \times V$ can belong to any single matching and, if $|M| < \ell$, the weight of $M$ would be at most $(\ell-1)L' + \frac{n+\ell}{2}L < (\ell-1)L' + nL < \ell L'$.
Then, there are at most $k$ edges in $M'' = M \setminus M' = M \cap E$ as otherwise we would have $|M| = |M'| + |M''|  > \ell + k = \frac{\ell}{2} + \frac{\ell}{2} + k = \frac{\ell}{2} + \frac{n}{2} - k + k =  \frac{\ell + n}{2}$, which is a contradiction.
Since the weight of $M'$ is exactly $\ell L'$, the weight of $M'' \subseteq E$ must be $x$.
If there is a matching $M''$ of weight $x$ and size at most $k$ in $G$ then there is a matching $M$ of weight $\ell L' + x$ in $G'$.
Since $|M''| \le k$, there are at least $n-2k= \ell$ distinct unmatched vertices $u_1, \dots, u_\ell$ in $V$ (w.r.t. $M''$).
Choose $M = M'' \cup \{ (v_i, u_i)  \mid i=1, \dots, \ell\}$. The weight of $M$ is $\ell L' + x$.

We can now look for a maximum-weight matching of cardinality exactly $k$ in $G$.
We can reduce this problem to the one of finding a maximum-weight matching of cardinality at most $k$.
Given $G=(V,E)$ let $L$ be its largest edge weight.
Modify $G$ by changing the weight $w(u,v)$ of each edge $(u,v)$ to $w'(u,v) = w(u,v) + kL$. Call $G'$ the resulting graph. Find a maximum-weight matching $M$ of cardinality at most $k$ in $G'$. If $|M| < k$, the instance has no feasible solution, otherwise return $M$.
Clearly a matching $M$ of size $k$ in $G'$ weighs $kL + x$ if and only if $M$ weighs $x$ in $G$. We only need to show that: 1) if a matching of size $k$ exists in $G$, $M$ contains exactly $k$ edges, and 2) if no feasible matching exists in $G$, $M$ contains less than $k$ edges.
The second claim is immediate since any matching in $G'$ is also a matching in $G$. We then focus on the first claim:
If $G$ admits a matching of size $k$, $M$ contains exactly $k$ edges
By construction $|M| \le k$. We now show  that $|M| \ge k$. Suppose towards a contradiction that $M < k$. Then the weight of $M$ is at most
$\sum_{(u,v) \in M} w'(u,v) \le  (k+1) |M| L \le (k+1)(k-1)L = (k^2 - 1)L < k^2 L$. Since a weight of at least $k^2 L$ is attainable by selecting the edges in any matching of size $k$ in $G'$ (such a matching exists in $G$ and hence in $G'$), this contradicts the fact that $M$ is a maximum-weight matching.
.


Must a min weight subset of edges connecting all vertices form a tree?

Claim : if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree

True. It is the definition of MST on weighted (positive) graphs. Subset $S$ can't form a cycle due to minimum total weight condition.

You can prove this by contradiction, assume $S$ is a MST and forms a cycle, as all weights are positive, you can still remove a one edge $e$ from a cycle. $S -e $ is still going to be connect all the vertices of graph, but subset $S - e$ has total weight strictly less than the total weight of $S$, this is a contradiction to our assumption.


Difference between cross edges and forward edges in a DFT

Wikipedia has the answer:

All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails.

This will explain the diagram:-

Forward edge: (u, v), where v is a descendant of u, but
not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Cross edge: any other edge. Can go between vertices in
same depth-first tree or in different depth-first trees. (layman) It is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.(formal)


Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < \cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + \cdots + n_{d-1} < k$ but $n_1 + \cdots + n_d \geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,\ldots,a_{d-1}$, and any $k-(n_1+\cdots+n_{d-1})$ elements of value $a_d$. You take it from here.


Why do some architectures use a CMP instruction before branching while others just branch?

Every architecture may offer different flags and condition registers. It also may implement operations (e.g. addition) affecting these flags one way or another. Say an architecture A you mention does not need CMP; this means all flags and registers are set predictably in an orthogonal fashion for each operation (or else that particular jump/branch instructions must be enforced). An architecture B could not have this guarantee and use different flags for each operation and/or offer more generic jump/branch - then B offers a CMP instruction that makes sure flags are set as expected by the programmer/compiler.

There are several differences between A and B. For example, an architecture may offer more registers (X, Y not just ACC) which you could directly run operations on (therefore appropriate CMP instructions makes sense to select register etc). Architecture A may have to implement additional logic or even offer more flag registers to accomplish its aforementioned guarantee. Some processors want an instruction to do minimal register transfers/operations to maintain a given command execution cycle/clock.

These are a few things there are of course much more that turn this and other design choices to a successful architecture for compilers and intended users. Each choice reflects on the instruction set. What is important is to take advantage of each instruction the way it is intended in the best way and produce correct and fast code easily even in an automated way (from compiler).

All of the above possible reasons aside, note that you do not always have to use CMP (or have two instructions to branch) if your flags, condition registers are treated as you need them from the previous operation - you use CMP only if previous operation set flags are not set as expected for a subsequent branch.

Indeed sometimes in assembly written by humans (not compiler) we often just add a CMP in there, even if unnecessary, just to make sure because we may not remember the flags each operation affects (so that is a waste and not the way CMP is intended at least not for performance programming)!


How hard can identifying non-membership in a semi-decidable language be?

A language $L$ is semidecidable if there exists a computable predicate $f$ such that
$$
x \in L \Leftrightarrow \exists y \, f(x,y).
$$
We can construct a machine $M$ which halts on $x$ iff $\exists y \, f(x,y)$: the machine just goes over all possible $y$, for each one checks whether $f(x,y)$, and if so, halts. This shows that we can decide $L$ using an oracle to the halting problem, i.e., using an $\emptyset'$-machine.


Why can't edit distance be solved as L1 distance?

Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.


By definition
$$O(g)=\{f\colon \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$
so $O(1)$ can be viewed as set of bounded functions. Outgoing from here $\log^{O(1)}(a+b)$ we can understand as set of functions $\log^{f(n)}(a+b)$ where $f(n) \in O(1)$.
Addition.
Understanding of $f \in \log^{O(1)}(a+b)$ not seems to be differ from understanding of $f \in O(1)$ and does not mean that "O(1) can be arbitrary large constant", as is in your comments. $O(1)$ is not constant, or set of constants, but set of functions. In same way $f \in O(1)$ does not mean that $f$ is bounded by any arbitrary large constant, but there $\exists C_f>0$ for which we have $f(n) \leqslant C_f$. So, $f \in \log^{O(1)}(a+b)$, mean, that $\exists g \in O(1)$, i.e. $\exists C_g>0$ $g(n) \leqslant C_g$, such that $f(n)=\log^{g(n)}(a+b)$. In words: function $f$ is bounded by $\log$ having bounded function in superscript. For example, $f$ cannot be $\log^n(a+b)$, but can be $\log^{\frac{1}{n}}(a+b)$ or $\log^{\frac{1}{n}+1}(a+b)$.


Hint: For each vertex $v$ and color $c$, have a variable $x_{v,c}$ which means "vertex $v$ gets color $c$". Now construct a 3SAT instance that states:

Each vertex gets some color.
Neighboring vertices get different colors.


What is meant by a language have a "finite specification"?

A specification in this sense is any description of the language that allows you to determine exactly what strings are in the language and what strings are not. We're usually quite vague about what exactly constitutes a specification since, ultimately, it doesn't matter. A specification must be describable by some finite string of characters, whether those characters represent English words ("The set of all strings consisting of some number of $a$s followed by the same number of $b$s"), mathematics ("$\{a^nb^n\mid n\geq 0\}$") or somethign else. As your notes go on to say, whatever reasonable meaning you give to "finite specification", there will only be countably many of them, whereas there are uncountably many languages.


Mean geodesic distance between two points in Delaunay Graph

As you have probably come to the right conclusion by now, for a Delaunay graph, the magnitude of the mean distance between two randomly chosen nodes depends on the particular configuration of the points.

Here is one extreme example. Let each one of the six sided of the triangulated honeycomb have $n$ edges. We will have $3n(n+1)+1$ points. The average distance between two nodes is $\Theta(n)$, which is $\Theta(\sqrt {3n(n+1)+1})$.

We can also consider the row of triangles just above the middle line in that honeycomb as a separate graph. It has $4n+1$ nodes. The average distance between two nodes is $\Theta(n)=\Theta(4n+1)$.

It is intuitive clear that for any given Delaunay graph of $N$ points, the mean distance between two nodes is between $\Theta(\sqrt{N})$ and $\Theta(N)$, which grows much faster than $O(\log(N))$, the mean distance between two nodes in a small-world network. That is one evidence why we call that kind of network small world!


Show that Vertex-Cover is NP-complete, using Stable-Set

You have it backwards- you have to reduce a known NP-complete problem to the thing that you want to show is NP-hard. If you were to reduce Vertex-Cover to Stable-Set, you would be saying that Stable-Set is at least as hard as Vertex-Cover... but Vertex-Cover could still theoretically be polynomial.

Since this seems like a homework problem, I don't want to actually give the solution here. What you need to do is find a way of transforming the Stable-Set problem into the Vertex-Cover problem. That way, any solution to Vertex-Cover would be a solution to Stable-Set, so VC is at least as hard as SS. After that, you need to show that VC (note that you need to work with the decision version of VC and SS, which asks does there exists a VC/SS of size k) is in NP by showing that given a witness, you can check if it's correct or not.

Solutions to both problems are sets of nodes in a graph. If there's a VC of size k, that means that all edges have at least one node touching them. If there's a SS of size k, that means no edge has two nodes touching them. I'd suggest drawing out some graphs, finding the VC and SS of both of them, and seeing if there's a relationship between the two sets, as well as the size of each set and the number of nodes in the graph. While I haven't worked out a proof, I don't think you need to do a transformation on the graph itself (like drawing in new nodes/edges) in this case. However, for some problems, you might need to.

Here is a handout on NP-completeness reductions, which might help you. I suggest reading some reductions to get a handle on it.


Superposition calculus: Elimination of redundant atoms

This one seems to be a case of a not very careful choice of notation in this paper.

So we have a clause $C = \Gamma, u\approx v, u\approx v \to \Delta$ in $\mathcal{N}$.

We could use the simplification rule as follows. Let $\Gamma_1 = \Gamma, u\approx v$. Then the following two conditions hold:

$C = \Gamma_1, u\approx v \to \Delta$ in $\mathcal{N}$
$\Gamma_1 \to u\approx v, \Delta$ is a tautology therefore it can be added to $\mathcal{N}$ without loss of soundness.

Now applying the simplification rule we can replace $C$ with $\Gamma_1\to \Delta$. From the definition of $\Gamma_1$ we have replaced $C$ with the clause $\Gamma, u\approx v\to\Delta$. Effectively the second occurrence of the atom $u\approx v$ has been removed.

They also claim that the same procedure works for removing of multiple occurrences in the succedent.

Also note that this is not specific to equational theorem proving and applies to any atoms.


Bin-packing satisfiability rather than minimization

Having a fixed number of bins makes little difference. If you use sorted-first-fit for example, the only difference is that the algorithm can fail. On the other hand, if you use a better algorithm for bin-packing (one that considers all bins before it is proven that they are all needed), you would find a trivial lower bound l for the number of bins, try to fit them all, and if it fails increase l by 1 and start all over again.

The different sizes make the problem likely harder to solve. For example, if you only wanted to decide which bin contains the largest item, that would in normal bin packing be no problem: Just put it into the first bin; it doesn't matter which one. With different bin sizes, pick all the bins that are big enough, remove duplicates with the same size, and try putting it into each of these bins. So you have more possible combinations. (If you had 100 bins of size 10 and 100 bins of size 5, then items of size 6 would be no problem, but a largest item of size 5 or smaller would be put into one of two bins).

I say "likely harder" because in the extreme you might have items that fit into one bin only.

Once you try to find an optimal solution using brute force, any additional restrictions make it easier because they remove possibilities from the search tree.


Pumping lemma problem - Choosing the right string to pump

If $k$ is the pump length from the regular pumping lemma choose $w=c^ke^k$. Clearly, $w\in L_1$, but if you pump you have to change the number of $c$'s while leaving the $e$'s unaltered. Hence after pumping the word is no longer a member of $L_1$.


Compact Shared Reduced Binary Decision Diagrams with negated identifiers

Found the answer in the paper Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean function Manipulation.

more accurate treatment can be found in section 2.3 in Proving circuit correctness using formal comparison between expected and extracted behaviour (pdf download available).

in short, canonicity is preserved if, quoting from tvandijk.nl/pdf/mscthesis.pdf page 15 "Complement edges" (The Parallelization of Binary Decision Diagram operations for model checking, thesis by Tom van Dijk):

"Minato [35] proposes the following constraints:

1) Only 0 is used as the value of a leaf.

Alternative rule 1 : only 1 is used as the value of a leaf.

Alternative rule 2 : do not allow complement edges on leaves.

2) No complement edges are allowed on 0-edges.

Alternative rule: no complement edges are allowed on 1-edges"

note that this is not a "true" restriction as if we decide that only hi edges are complemented, and we want to create a node with its lo edge being complemented, we just negate the whole node, like a?b:not(c) == not(a?not(b):c).


Higher order rewriting theory and critical pairs with the beta rule

The theory of higher-order critical pairs can indeed handle this example, as outlined in the following article:

Higher-Order Rewrite Systems and their Confluence, Richard Mayr & Tobias Nipkow

There are several different notions of higher-order rewrite systems, and several of them are able to handle your example, including those of the paper.

The critical pair lemma is still true: if every critical pair is development closed, and the system is terminating, then one can conclude that it is confluent. The second condition is necessary though, in particular, $\beta$-reduction on untyped terms can muck things up.

This means that completion is still a meaningful operation in this setting.

At any rate, your second rule seems a bit more natural in a termination context, where $F$ is "pushed towards the leaves", but obviously it depends on the meaning of the symbol.


Given the phrase "Where NONE of the following are TRUE" and two statements how should a boolean logic be composed?

The correct meaning is:

"Where (NOT (value > 10)) AND (NOT (value < 25))".

Applying one of the De Morgan's laws:

1) P AND Q <=> NOT( (NOT P) OR (NOT Q) )
2) P OR Q <=> NOT( (NOT P) AND (NOT Q) )

we get:

"Where NOT ( (NOT(NOT(value > 10))) OR (NOT(NOT(value < 25))) )"

and the equivalent final result is

"Where NOT ((value > 10) OR (value < 25))" :-)


What are functions called that yield the same result when applied to one of their result values

A function satisfying that property is called idempotent.


Subsampling of Frequent Words in Word2Vec

My guess is that we should regard $f(w_i)$ as a number between 0 and 1, i.e., the number of times word $w_i$ appears divided by the number of words.  This makes it an estimate of the probability of occurrence of word $w_i$.

Then the formula seems to lead to reasonable results.  If you have a very frequent word (appears as a $10^{-3}$ fraction of the words), we have $P(w_i) = 1 - \sqrt{10^{-2}} = 0.9$, so it's very likely to be discarded.  If you have a moderately infrequent word (probability of occurrence $10^{-5}$), then we have $P(w_i) = 1 - \sqrt{1} = 0$, so it won't be discarded.  If you have a word that is even rare than that, it won't be discarded either.  So this discards very frequent words with high probability and keeps almost all words that are rare or moderately rare.


Minimally satisfying multiple qualitative requirements at once

It depends what you mean by "minimal".  You might mean either of the following two:

you want to minimize the number of foods selected (variables set to true).
you want a set of foods that's a valid solution, but where any subset of that set is no longer a valid solution.

I'll discuss solution to both variants of the problem.

Minimizing the size of the set

If you want to minimize the number of foods selected (the number of variables set to true), the problem is NP-hard, so there is not likely to be any algorithm that is both efficient and always provides the optimum answer for all possible instances.

However, don't give up.  There are reasonable approaches.  Your problem can be formulated as an instance of integer linear programming (ILP), and then you can use an off-the-shelf ILP solver to solve it.  ILP solvers have gotten pretty good so they might be adequate.

You have $n$ zero-or-one integer variables $x_1,\dots,x_n$, corresponding to the $n$ foods.  Each requirement then translates to one (or more) linear inequalities.  For instance, the requirement that you must have food #1 and food #2 corresponds to $x_1=x_2=1$.  The requirement that you must have at least three foods corresponds to $x_1+x_2+x_3+x_4 \ge 3$.  Some kinds of requirements take a bit more work to formulate as linear inequalities; see Express boolean logic operations in zero-one integer linear programming (ILP) for some tools you can use.  Then, you want to minimize the objective function $x_1+x_2+\dots + x_n$ subject to those constraints.  An ILP solver will do that for you.

Alternatively, you could use an off-the-shelf pseudo-boolean satisfiability solver.

The ILP solver will generate one minimal solution.  To generate all of them, there are various ways to do that.  For instance, if you know there's a solution with 3 variables set to true and no solution with 2 variables set to true, then you can add the requirement $x_1+x_2+\dots + x_n=3$ and enumerate all solutions to the corresponding integer linear program.

Minimal sets of foods

Alternatively, suppose you want to enumerate all ways to choose a set of foods that is minimal (no proper subset is a valid solution).  This requires different methods.

One way is to find a valid solution, then start removing foods until you can no longer remove any more.  That will be one minimal solution.  To enumerate minimal valid solutions, you can now look for a new solution that is not a superset of any prior minimal solution.  This could be very slow.  One way to find a valid solution is by using an integer linear program (ILP), as above; you can formulate the constraint that the solution must not be a superset of any prior minimal solution as well.

An alternative approach might be to view this as the problem of converting a Boolean formula to DNF form.  I think that each DNF clause corresponds to one minimal subset of foods (of variables that can be set to true).  There are various methods for conversion to DNF form; e.g., Quine-McCluskey, the Espresso logic minimizer.  I haven't thought about this carefully and I don't know for sure whether this will find all minimal solutions.  It appears that in your specific situation, you have a monotone Boolean formula; I don't know whether there are better algorithms for converting monotone Boolean formulas to DNF form.


Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

One of the most basic assumptions in cryptography is the existence of hard problems, even on a very conceptual level. For example, to establish a secure communication channel, you want your cipher to impose problems on eavesdroppers which they cannot solve.

The problem is that the existence of hard problems generally has (severe) impact to questions in complexity theory. The most attractive problems for cryptography are those in $\mathsf{NP}$, in particular because, assuming $\mathsf{NP}$ has intractable problems, these have nice asymmetrical properties: Although you can verify a solution efficiently, it is infeasible to find one. However, establishing intractable problems in $\mathsf{NP}$ necessarily entails proving $\mathsf{P} \neq \mathsf{NP}$.

Furthermore, some cryptographic primitives imply the existence of hard problems even without basing on the hardness of a particular problem. For example, the existence of one-way functions, which are essentially the most basic cryptographic primitive, implies $\mathsf{P} \neq \mathsf{NP}$. We also know one-way functions exist if and only if PRNGs exist, so it is clear one-way functions are not an isolated case (whose existence is hard to establish). Also, asymmetric cryptography implies the existence of either of these primitives. (Read more on Impagliazzo's five worlds if you are interested in these issues.)

Modern cryptography is highly dependent on complexity theory for its assumptions. Since that is the case anyway, it only seems natural to embrace the conjectures of complexity theory too.


Unsupervised Learning: BCM or Oja's Rule

Oja's learning rule and the BCM share the underlying generative model, a linear perceptron: $$y = w^T x,$$ where $w$ and $x$ are vectors of the similar dimension.

But they differ in their goals:

Oja's rule (run with a sufficiently small learning rate) extracts the 1st principle component of the covariance matrix of the data: $$C = \langle xx^T \rangle_{p(x)}$$ s.t. $ \lambda_1 w_1 = C w_1$, where $\lambda_1$ is the largest eigenvalue.

The BCM rule maximizes the input selectivity with respect to a specific input pattern. The selectivity is defined as $$ s(w) = 1 - \frac{\langle w^T x^{(i)} \rangle}{ \max_i w^T x^{(i)} }. $$ The selectivity is maximized if the output neuron responds strongly to one of the input patterns (e.g. the kth stimulus $x^{(k)}$) but barely responds to all others.

The third rule doesn't make sense to me (I'll use explicit notation for vectors now). Assuming that $n$ is a scalar (e.g. learning rate), $\vec{x}$, $\vec{y}$ and $\vec{w}$ must have the same dimensions. Then, what's your generative model? Neither can it be $y = \vec{w}^T \vec{x}$ (because $\vec{y}$ is a vector) nor $\vec{y} = W \vec{x}$ because your weights are vector and not a matrix..


How to detect intersecting segments based on length of the segments

First assume that you know where $A,B,C,D$ are.  In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\alpha_A,\alpha_B,\alpha_C)$ are called the barycentric coordinates of $D$.  You can read off which of the segments $Dx$ ($x\in \{A,B,C\}$) cross a side of the triangle $ABC$ from the sign pattern of the barycentric coordinates.

It's not particularly difficult to find suitable coordinates either.  You can just assume that $A=(0,0)$, $B=(d(A,B),0)$, and $C$ is either intersection point of the appropriate circles around $A$ and $B$.  This will then uniquely determine $D$ by intersecting three circles.


How to convert an NFA with overlapping cycles into a regular expression?

Rather than "reading off" you should employ one of several canoncial methods to do this. By far the nicest I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma (a needed result) is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

In short: For every state $q_i$, create the equation

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q_i \overset{a}{\to} q_j$ means there is a transition from $q_i$ to $q_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

Solving it (using Arden's Lemma) yields one regular expression $Q_i$ for every state that describes exactly those words that can be accepted starting in $q_i$; therefore $Q_0$ (if $q_0$ is the initial state) is the desired expression.

Application to the given automaton is left as an exercise; a complete example is included in above linked document.

See also here where I posted a similar answer.


Choosing taps for Linear Feedback Shift Register

The taps are decided by the polynomial in a straightforward way:
for $X^n$, you connect the $n$th tap. Note that in your diagram the first tap is $R4$, the 2nd is $R3$ etc..

Since your polynomial is $X^5+X^2+1$ the feedback is an XOR of the output of the 2nd tap ($R3$) and the 5th tap ($R0$). The "$+1$" of the polynomial ($X^0$) is usually always there and corresponds to the "feedback" itself, i.e., the line connected into the first bit ($R4$).

The output should be the "feedback" line (rather than $R0$). This is important since the polynomial is identified with the generated sequence, and if you take the output of $R0$ you generate a different sequence, not the one identified with $X^5+X^2+1$ (although they are the same up to a prefix)

See more details in Wikipedia: Linear feedback shift register.


Does a given e-NFA accepts all the Strings?

A classical result, attributed to Meyer and Stockmeyer, is that checking whether an NFA accepts all strings is PSPACE-complete. Nevertheless, there are some non-trivial heuristic algorithms. See for example Antichains: A New Algorithm for Checking Universality of Finite Automata by De Wulf, Doyen, Henzinger and Raskin.


Time complexity of a classical version of Shor's algorithm

When we say that an algorithm runs in polynomial time, we mean that there is a constant $k$ such that the algorithm runs in time $O(n^k)$, where $n$ is the length of the input as a string. When the modulus $N$ is part of the input, it's specified in binary (or any number system other than unary) so the length of that part of the input is only about $\log N$. Thus, running in time $O(N^2)$ corresponds to running in time $(2^{\log N})^2$, which is not a polynomial in the length of the input.


How do I model this expression maximization problem as a Knapsack problem?

One approach (not based on the knapsack problem): suppose you are given a threshold $\tau$ and want to check whether you can find a subset such that

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}} \ge \tau.$$

Could you solve that problem?  If you could, you could use binary search on $\tau$.

Note that the above condition is equivalent to

$$a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k} \ge \tau \cdot (b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}),$$

or equivalently,

$$a_{i_1} - \tau b_{i_1} + a_{i_2} - \tau b_{i_2} + a_{i_3} - \tau b_{i_3} + \dots + a_{i_k} - \tau b_{i_k} \ge 0.$$

And that enables us to find a simple way to check for the existence of that subset.

See if that gives you any ideas.


Does this algorithm for permuting rows and columns of a matrix converge?

For an $n \times m$ matrix $M$, define the potential function
$$
\Phi(M) = \sum_{i=1}^n \sum_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j).
$$
If we write it as
$$
\Phi(M) = \sum_{i=1}^n 2^{n-1-i} \sum_{j=1}^m 2^{m-1-j} M(i,j)
$$
then it immediately follows that reordering rows either fixes $M$, or strictly increases $\Phi$. Similarly, reordering columns either fixes $M$ or strictly increases $\Phi$. Since there are only finitely many $n \times m$ matrices, it follows that your algorithm eventually converges.
It is definitely not the case that the process terminates after three steps. For example, here is a matrix which requires five steps:
$$
\begin{pmatrix}
0&0&1&0 \\
0&1&0&0 \\
1&0&0&1 \\
0&0&1&1
\end{pmatrix}
$$
This is a matrix in which the $(i,j)$'th entry depends only on $i+j$. Specifically, $M(i,j) = 1$ iff $i+j \in \{4,7,8\}$.
More generally, the $n \times n$ matrix $M$ in which $M(i,j)=1$ iff $i+j \in \{4,2n-1,2n\}$ requires $2n-3$ rounds, which is optimal for small values of $n$ (over all $n \times n$ matrices). Moreover, this is the unique choice over matrices of this form.
(To complete the picture, for $n = 3$ the unique optimal choice is $i + j \in \{4,6\}$ rather than $i+j \in \{4,5,6\}$, and for $n = 2$ the only choices are $i+j \in \{4\}$ and $i+j \in \{3,4\}$, which both correspond to two rounds.)


You case (i) analysis is wrong, consider the input $60 + 60 + 60 + 20 = 200$. The most even split you can do is $60 + 60$ and $60 + 20$ which has a makespan of $120$, thus there is at least one feasible input for which professor Smart's algorithm returns the optimal result.

For case (ii) we know each job size is at most 10. Professor Smart's algorithm returns a makespan of $120$, which means one machine has a sum of jobs of $120$ and thus the other $200 - 120 = 80$.

But since we know each job has at most a size of $10$ we could move jobs over from the bigger instance to the smaller instance at least until the bigger instance hits $110$ and the smaller $90$ while being guaranteed that each job moved reduces the makespan. But $110 \cdot 1.05 < 120$ thus the algorithm is not a $1.05$ approximation algorithm.


Are Context Sensitive Languages Turing Complete?

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct.

To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The proof is not difficult and comes from Alan Turing himself). That means that we can associate every positive integer with some Turing machine, in such a way that every machine has a unique index.

Now, take the language $L_1 = \{a^i \mid i > 0\}$ (where $a^i$ means a string consisting precisely of $i$ $a$s). Since any string of $a$s is in $L_1$, the language is equivalent to the regular expression $a^+$.

The semantics of a program in  $L_1$ is simple: it does whatever Turing machine number $i$ would do, where $i$ is the length of the program. That's clearly a Turing complete regular language.

Then we define $L_2 = \{a^ib^i\mid i>0\}$ and $L_3 = \{a^ib^ic^i\mid i>0\}$, with the same semantics: in each case, program $i$ executes Turing machine number $i$. So these languages are also Turing complete, but $L_2$ is context-free and $L_3$ is context-sensitive.

Now, let's redefine the semantics. We'll define three languages with exactly the same syntaxes, but instead of executing Turing machine $i$, they print out $i$ in binary and then halt. These three new languages are still regular, context-free and context-sensitive, respectively, since the syntaxes have not changes. But none of them is Turing complete.

Bottom line: What a language means and how it is expressed are completely different concepts.


If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.