Solving a in/equality constraint problem with graph search

You're on the right track.  Construct an undirected graph with an edge for each equality constraint, as you suggested.  Next, look into the concept of connected components, and algorithms for finding them.  You should be able to take it from here.

This problem can be solved in linear time.


One definition of NP is "the set of languages accepted by non-deterministic Turing Machines in polynomial time."

There's a trivial transformation that lets us convert any deterministic Turing Machine into a non-deterministic one, which will have the exact same running time. Basically, you just take the same deterministic TM, rename it as non-deterministic, and don't use any non-determinism.

In short, any deterministic TM is also a non-deterministic TM (but the converse is not true).

So, suppose there's a language $L$. If we can accept $L$ in polynomial time with a deterministic TM, then we just make the trivial non-deterministic TM which runs identically, and we can now accept $L$ in polynomial time with a non-deterministic Turing Machine.

We know that $|P| = |NP|$ because both sets are infinite and countable. There are countably many Turing Machines, since each Turing Machine can be represented as an integer. There is at least one Turing Machine for each language in $NP$, and likewise, at least one Turing Machine for each language in $P$. Since both of these sets are infinite, they must be infinite countable.


Computer Architecture: How to determine the bits of the address used to access the cache?

A direct-mapped cache is another name for a one-way set associative cache.
Calculating number of bits in address space
 Number of bits in address space = log2(Memory size)
 Bits in (Tag + Index + offset) = Number of bits in address space
In order to know the number of bits in Tag field, we would need to figure out the number of bits in Index and Offset fields. Then the above equation can be used to get the number of bits in the Tag field.
The index bits are used to select the row in the cache. The offset would then be used to get the cache block. This means we definitely need those number of bits to access information from the cache and the remaining bits from the total address space can be used to store the tag information.
Calculating the number of bits for the offset
The offset fields can be calculated using the information about the block size. A cache block is the basic unit of storage for the cache. For these set of problems the offset should be able to index every byte from within the cache block.
offset bits = log2(block size)
Calculating the number of bits for the cache index
Calculation for the number of index bits is slightly more involved than the calculation for the offset field. The reason being that the calculation needs to take the number of sets, block size and the cache size into account. The index bits are needed to select the cache row but before that we need to figure out the number of rows for a given cache configuration.
The number of rows would be equal to the cache size divided by the block size for a direct mapped cache (there's just one way). For a n-way set associative cache, the number of rows would be cache size divided by the number of ways and the block size, i.e.
Number of rows = Cache Size / (Block Size x Number of Ways)
Once the number of rows are known, the number of index bits would simply be the log base 2 of the number of rows:
Index bits = log2(Number of rows)
That's it. We can now work the number of Tag bits using the following relationship:
Tag + Index + Offset = Address bits
Source: https://blog.quicksilicon.in/setassociativecache/


Maximum integer in a sorted list which also is in an unsorted list

Are you familiar with binary search? If not, look that up. It has complexity $O(\log n)$ and will find you the index $i$ where you would insert $x$ into $A$ to maintain sorted order. From this you can instantly see whether $x$ already exists in $A$ by checking whether $A[i] = x$.
Then, do this for $b_1, b_2, \dots$, checking for each whether it is in $A$ in $O(\log n)$ time, and if yes, whether it is bigger than the current best found.
You do this $k$ times to find the biggest element that is in both $A$ and $B$ in $O(k \log n)$ time.

You can even be a bit smarter, like such:
lo = 1
best = A[1] - 1
for b in B:
    if b > best:
        i = binary_search(A, lo, n, b)
        if A[i] == b:
            best = b
            lo = i + 1

This doesn't change the worst case complexity but will avoid needless binary searches, and make the bounds on the binary searches that you do tighter.


Solving T(n) = 2*T(n-1)+4 witht the Master Theorem


The problem you describe is exactly asymmetric TSP. As your reduction shows, asymmetric TSP generalizes the Hamiltonian circuit problem, which is known to be NP-hard.
Usually we consider metric versions of TSP, in which the triangle inequality $c(i,k) \leq c(i,j) + c(j,k)$ holds, and often the TSP instance is symmetric, $c(i,j) = c(j,i)$. Your reduction shows that (symmetric) metric TSP is also NP-complete, since the cost function you construct is symmetric and satisfies the triangle inequality.


Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s

Try to transform the graph as following. Assign weight 0 to each edge and then "split" each vertex into two vertices by connecting them by an edge with the weight equal to the vertex's weight.

  ====>(12)====>   turns into  =====>(v)--12-->(u)====>

The find the longest path in $O(|V| + |E|)$. Please look here.


How to find mean ,max ,min in constant time?

If you are just given an array and asked to find these statistic there there is no way to do that (unless the size of the array is upper bounded by a constant). An easy way to convince yourself that this is true is noticing that in $O(1)$ time you can only access $O(1)$ entries of the array. Then the maximum, minimum, or median could be in the unread entries (notice that you can safely assume that any $O(1)$-time algorithm always accesses the returned entry).
You talk about "insert operations" which makes me thing that you were actually asked to design a data structure that supports some set of operations, among which there are insertions and reporting the above statistics. If this is the case then the answer depends on how what the other operations are and how much time do you want to spend on those.
If the only updates to the array are insertion then it suffices to keep track of the number of elements, their sum, and the maximum and minimum element after each insertion. This will require $O(1)$ time per insertion and $O(1)$ time to report the statistics.


Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$

Frankly, I think your argument works. As there is always one of the letters missing, the second condition forces the substring to be "short", pumping will not get equal amounts of $a,b,c$.

For didactical purposes authors in books take extra precautions to make sure the student understands that all cases must be covered. Hence they tend to avoid shortcuts.


What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a

Your function produces the sequence A109128, that is
$$
\mathit{recurser}(i,j) = 2\binom{i+j}{i} - 1.
$$
You can prove this by induction.
How I found out: I computed the first few values, and searched the OEIS.


Deriving from a terminal word in a context free grammar

There is absolutely no problem writing $ab \Rightarrow^* ab$. It definitely happens in proofs.


Does input space size contribute at all to the runtime of an algorithm?

We measure the running time as a function of the length of the input, not as a function of $n$.  So, it doesn't matter whether the length of the input is $2^n$ or not.

When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $n$).

For your problem, the length of the input could be $2^n$, but it will typically be a lot less than $2^n$, because typically we'll have many fewer sets than that.  Either way, it doesn't matter, because we're measuring the running time as a function of the input length.

Typically, the format/representation of the input doesn't affect the running time much; the running time will be identical for any reasonable way to represent or encode the input.  So, typically that doesn't matter.  In the cases where it does matter, be careful to specify the input representation, or ask if it isn't specified.


Proving using Beta Reductions (Lambda Calculus)

First let:
$$ true = \lambda x ~ y . x $$
$$ false = \lambda x ~ y . y$$
$$ or = \lambda x ~ y .((x ~ true) y) $$
So this is what you wrote:
$$or ~ true ~ false \rhd_{\beta} true$$
$$  \Bigg ( \Big( \lambda x ~ y . (x ~ true) y \Big) true \Bigg) ~ false $$
$$ \Bigg ( \lambda y. \Big ((true ~ true) y \Big) \Bigg) false $$
$$ ((true ~ true) ~ false) $$
Unwrap $true$.
$$ \Big( (\lambda x ~ y . x) ~ true) \Big) ~ false $$
$$ \color{red}{(\lambda y . true) ~ false } \rhd true $$
In the red step, which is what's burdening you, you're just consuming the $false$, why? Because there are no free $y$ variables in $true \equiv (\lambda x~ y. x)$. This is rule-(e) for substitution.

Definition 1.12 (Substitution) For any $M, N, x$, define $[N/x]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows (after [CF58, p.94]).
(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

Note: $FV(P)$ stands for the set of free variables of $P$.


Detecting all cycles in un-directed graph

Following is an algorithm better than the brute force search.

Given graph $G$, find the DFS tree $T$ of $G$. We know from the structural property of $T$ that any for edge $(u,v)$ in $G$, we have that either $u$ is an ancestor of $v$ in $T$ or $v$ is an ancestor of $u$ in $T$. Therefore, brute force search for cycles in $G$ only along subsets of the branches in $T$. This is equal to the trivial brute force search if $G$ is a clique but better otherwise.

However, one can hope for better heuristics. For instance, see [1].

[1] Hongbo Liu, Jiaxin Wang: A new way to enumerate cycles in graph. AICT/ICIW 2006: 57.


Definition of the cyclic shift of a formal language?

The cyclic shift of a language $L$ consists of all cyclic shifts of the words in $L$. Instead of defining the cyclic shift formally, let me give an example. The following are all cyclic shifts of the word monkey:

monkey onkeym nkeymo keymon eymonk ymonke

To see the connection with the definition, consider nkeymo. If we write monkey as mo concatenated with nkey and then switch both parts, we get nkeymo. This corresponds to setting u=mo and v=nkey in the definition above.

To answer your concrete question, $u,v \in \Sigma^*$. (The alphabet is usually denoted by $\Sigma$.)


A similar question was answered here:

How can it be decidable whether $\pi$ has some sequence of digits?

We can ignore the question "if a given TM halts" as it is irrelevant what the question actually is, let's just name the condition C.

If C is true, then the correct algorithm is if n == 0 return true else return false. If C is false, the correct algorithm is return false. Whether C is true or false, one of these two algorithms is correct for every n, so such an algorithm exists.

Additionally, "does a given TM halt" is computable for the same reason - the correct algorithm is either return true or return false. What is not computable is a function that answers "does this TM halt" for any TM.


Recursive Algorithm Copying Array vs. Time Complexity

The first point is that as in the most binary search implementations we are passing an array with their sub-indices each time, and in the common programming languages, arrays are passed by reference this problem cannot happen.

However, if this copy happened each time this would be $n+\frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^{\log(n)}} = \Theta(n)$.
Hence, time complexity of this algorithm which copies half of the passed array would be $\Theta(n)$.

Moreover, if the implementation passed the whole of the array each time and control the search using sub-indices, the time complexity would be worse and it would be $\Theta(n\log(n))$, as each time ($\log(n)$) copy the whole of the array with size $n$.


Admissibility of heuristic in the $A^*$ algorithm

It's exactly as you suspected:

Sometimes, the algorithm will find an optimal solution even with an unadmissible heuristic... only an admissible heuristic guarantees the optimality of the solution returned.

If you use an unadmissible heuristic, there's no guarantee what will happen.  The solution you get back might be the best one; or it might not be.  And, you probably won't have any way of telling whether the solution you got back was optimal or not, so you won't even know for sure when this is a problem and when it isn't.

If you use an unadmissible heuristic, you'll often (but not always) get sub-optimal solutions.


A doubt on converting NOT gate to CNF formula

Your formula does actually look like $x_2 = F(x_1)$, it's just written with different symbols.

First, we can rewrite the two clauses using implication. Since $(a \to b) \iff (\neg a \lor b)$, we can rewrite the formula as

$$
(\neg x_1 \to x_2) \land (x_2 \to\neg x_1)
$$

Now, you can recognize that this is $(a \to b) \land (b \to a)$, which is to say $a \iff b$.

$\iff$ as a boolean operator behaves the same way as $=$; it evaluates to true when its left hand side and right hand side are the same. So your formula is equivalent to

$$ x_2 \iff \neg x_1 $$

Viewing this as a constraint (assuming $x_1$ can be treated as "fixed"), $x_2$ is fixed as $x_2 := \neg x_1 $


Examples for directed graphs with super polynomial cover time

Yes, it's not too hard to construct such a graph.  Consider a path $v_1 \to v_2 \to v_3 \to \dots \to v_n$ containing $n$ vertices.  Now add a new "dead-end vertex" $w$, and add edges $v_1 \to w$, $v_2 \to w$, $v_3 \to w$, etc.

If you do a random walk starting at $v_1$, the probability that you reach $v_n$ is $1/2^{n-1}$, as you have to get lucky and move in the right direction at each of the vertices $v_1,\dots,v_{n-1}$ to avoid getting stuck at the dead end.  Therefore, the cover time will be $\Omega(2^n)$.

Notice how things would change if we converted this into an undirected graph.  In an undirected graph $w$ would no longer be a dead end: if we hit $w$, we're not stuck (we still have a chance to get back to where we want to be, by backtracking our steps).  In the directed graph, $w$ is a dead end: once you hit $w$, you're done and you have no hope of making it to where you want to be.


Is this argument wrong "since DOM is special kind of RDOM, then RDOM is NP-hard"?

There are two statements here that rule the argument. The first statement:

  Statement 1.
  To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM
 \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance
  $\langle G',r,k'\rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only
  if $\langle G',r,K'\rangle \in RDOM$.

is a general framework for showing that RDOM is NP-hard. However, in this statement, you have not shown how to prove that this reduction works. You just said how to prove that this problem (or any problem) is NP-hard. In order to prove it, you need a proper reduction from all instances of DOM to instances of RDOM. The second argument however,

  Statement 2.
  By the way, my friend states that we know that a domination is a
  $1$-rainbow domination in the same graph, i.e. domination is a special
  kind of rainbow-domination, and since domination is
  $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to
  convince him that this is wrong? or Is this argument correct?

looks like a proper reduction. If "every domination is a $1$-rainbow domination in the same graph", then this proof is completely right. This is a proper reduction from every instance of DOM problem to instances of RDOM or 1DOM problem. However, if "every domination is NOT a $1$-rainbow domination in the same graph", then this proof is completely wrong.

My understanding is that a domination, can be any of 1-rainbow domination, ...,or |V|-rainbow domination. In this case, it is implied that by having a polynomial algorithm for RDOM problem, you can iterate $|V|$ times thorough $r$-dominations and determine if the graph is dominating. Thus, if you have a polynomial algorithm for RDOM problem, you can solve the DOM problem polynomially.


We can show that after every iteration of the for-loop in question, counted is FALSE. Therefore, inversions = inversions + n1 - i + 1 is executed if and only if j++ is executed in the same iteration (both are guarded by R[j] < L[i]). Since neither i nor j is changed between evaluation of the two if conditions, this implies that your version is equivalent.

   We perform an induction over k. Before the loop, counted is explicitly set to FALSE. In any given iteration, we start (by induction hypothesis) with counted == FALSE. If L[i] <= R[j], counted is not changed throughout the current iteration. If the opposite is the case, counted is first set to TRUE, but reset to FALSE in the else block. For this, we note that the truth value of R[j] < L[i] remains unchanged from the first to the second if.

I guess the extra block is there for didactic reasons.


Best way to merge different trees to single data structure?

I don't think post-processing the trees to try to exploit similarity is likely to lead to much success.  Instead, I would suggest trying the following approaches, which to my mind seem more likely to be effective.

Tune the hyperparameters. Try adjusting the number of trees (num_iterations).  If you can get close to the same accuracy with fewer trees, the classifier will be faster.

Try a different classifier. There are other classifiers that are faster for evaluating new samples, especially in the multi-class regime.  For instance, you could try logistic regression and random forests.

Hierarchical multi-class classification. XGBoost is fundamentally a boolean classifier (where there are only two classes).  It handles  multi-class classification (with more than two classes) using the strategy one-vs-rest (or one-vs-all) strategy: if there are $K$ classes, then we construct $K$ boolean classifiers, where the $i$th either outputs "class $i$" or "not class $i$".  This is what leads to the blowup in number of trees: the running time is proportional to $K$.

If your classes have any hierarchical structure, then an alternative is to use a hierarchical structure.  You build a binary tree, where each leaf corresponds to a single class and each internal node corresponds to a set of classes (hopefully, ones that are semantically related).  You construct a classifier for each internal node of the tree, which predicts whether to go left or right down the tree.  You classify each new instance by walking down the tree, as directed by the classifiers that you visit.  Thus, with $K$ classes, we end up with a binary tree with $K$ leaves and of depth (typically) about $\lg K$.  Thus, you can classify a new instance by evaluating $\lg K$ classifiers.  This offers a speedup over one-vs-rest, because the time to classify a new instance is proportional to $\lg K$ rather than $K$.

However, hierarchical classification has some caveats.  It can potentially lead to reduced accuracy.  The effect on accuracy depends on the structure of the class labels.  If there is some hierarchical structure, then it might work well, but if not, it might work poorly.  For instance, suppose you have classes "Poodle", "Chihuaha", "Siamese", and "American Shorthair", you might group the first two into the cluster "Dog" and the latter two into the cluster "Cat".  Thus, you would first apply a Dog vs Cat classifier; then, depending on the result, you would either apply a Poodle vs Chihuaha classifier or a Siamese vs American Shorthair classifier.  So, hierarchical classification might work quite well in this example.  However, if your four classes are unrelated, hierarchical classification might cause a loss in accuracy.

Try a cascaded classifier.  Rather than building a single classifier, try to build a cascade of classifiers.  A cascade is a sequence of multiple fast classifiers, which are applied sequentially.  A classifier can either output a confident answer or can output "not sure"; in the former case, we stop and use that as the answer, and in the latter case, we proceed to the next classifier in the cascade.  The goal is that many instances will get answered quickly (you only have to apply the first few classifiers), and only the difficult ones will have to be evaluated by classifier in the sequence.


As the authors state in the introduction to their paper, UCT is an application of UCB1 for a specific problem:

  The main idea in this paper it to apply a particular bandit algorithm, UCB1
  (UCB stands for Upper Confidence Bounds), for rollout-based Monte-Carlo planning. The new algorithm, called UCT (UCB applied to trees) described in Section
  2 is called UCT.

It's not the algorithm but the particular application which is new.


About the 'trick' for finding the diameter of an graph in $O(n^2)$

The diameter of the following graph is $2a+4$. If you start from $v$, you will need $i=2a+1$ iterations to have $s,t\in W_{i}$. It provides a family of counter-examples for an arbitrary large number of indirections (as $a \to \infty$).


CRF message passing as convolution operation

I read the article. The meaning of the equation:
$$[G\otimes Q](f_i)$$ stand for $G$ convolution with $Q$ in the feature point $f_i$ and not multiplied by $f_i$.

The $f_j$ is hidden inside the convolution operation.

The actual operation is done using cross bilateral filter.
You can see more information on the Project site of the article.
You can also find a source code in this site.


This task interested me, at least in non-degenerate case. I've tried to google it and suddenly found a beautiful approach described here (starts with "Next, the constraints are added to the Delaunay triangulation...", but we don't care about Delaunay here).

Name the set of segments $S$. First, forget about segments and build any triangulation $T$ of all endpoints of $S$. Then repeat the following process for all segments one-by-one:

If $e \in T$, we are done with this step. Otherwise, remove all edges of $T$ having an interior intersection point with $e$. One can see that it will unite some triangles of $T$ into one polygon. Add $e$ to $T$; it will break this polygon into two smaller polygons. Triangulate them both and add needed edges to $T$.

The key point is that if $e \in S$ was added to $T$, it will never be removed, because segments in $S$ don't have interior intersection points. So, after this process $S \subset T$.


Here are the values of $j$ at the end of each iteration:
$$
1,3,6,10,15,21,28,36,45,55,\ldots
$$
More generally, after $t$ iterations, $j = 1 + \cdots + t = \binom{t+1}{2} = \Theta(t^2)$. Therefore the loop halts after $\Theta(\sqrt{n})$ iterations.


Compute context free grammars for twice the amount

One general approach would be to try writing some initial strings and try to figure out a pattern. In my minimal experience, a lot of the times the strings I miss are of smaller lengths.

The initial strings for this would be:

$(\epsilon, aab, aaaabb, aaaaaabbb, ...)$ and so on.

Here we notice that: a) The string always has to start with an $a$ and b) Every time we generate an $b$, there should be two $a$'s corresponding to it.

So, we can write it as:

$$S \rightarrow \epsilon \  | \ aaSb$$


Robot follows a path near an obstacle without colliding

Robot Motion Planning is an important topic in Computational Geometry. There have been a lot of research in this field.

Here are some pointers that might help you:

Slide: http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/06_Bazhenova_RMP.pdf

Slide: http://www.cs.cmu.edu/afs/cs/academic/class/15381-s07/www/slides/020807motion.pdf

Book: http://books.google.com/books?hl=en&lr=&id=_VRM_sczrKgC&oi=fnd&pg=PR11&dq=robot+motion+planning&ots=zFkR07oxBJ&sig=efsVfaDPAlhKgxZwClKS136moCI#v=onepage&q=robot%20motion%20planning&f=false

Website: http://correll.cs.colorado.edu/?p=965


Gap problems are examples of promise problems, which are really the three-valued logic analogs of languages: some elements are in the language, some elements are not, and for the rest, we don't care.

A promise problem is in P if there is a polynomial time algorithm that answers Yes on all Yes instances and No on all No instances; we don't care what it answers on the don't care instances.

A promise problem $L$ is NP-hard if for every NP problem $L'$ there is a polytime reduction $f$ such that if $x \in L'$ then $f(x)$ is a Yes instance of $L$, and if $x \notin L'$ then $f(x)$ is a No instance of $L$.

We can similarly define the analogs of many other properties of languages. Usually this is done in an ad-hoc basis. We definitely think of promise problems as single languages rather than as a class of languages.


If you are handling only one truck/cargo in your problem, then this is a typical  Knapsack problem. If you are handling the bigger problem of distributing all items on how many trucks, then it is a variant of Bin Packing problem. Both problems are NP-Complete, however Knapsack has approximate algorithms with guaranteed bounds from optimality.

I suggest you use a somehow mangling compromise between A and B:

Solve using A, then solve using B and take the best answer.
Do both sortings, keep 2 arrays, then at each step compare A choice to B choice and select the better choice (greedy approach)
Assign a weight to each factor then sort an array C according to your weight function. If you don't know the weights then make it equal (half for each factor). If you value price more make its weight above 0.5 if you value volume more then give it a higher weight. This is called multiplicative weight


Isomorphism of a DFA and the minimal DFA

No. If the result of minimizing was always isomorphic to the thing you started with, minimization would do nothing!

For a concrete example, consider any automaton with more than one state, which has every state accepting. This automaton accepts $\Sigma^*$ and is not isomorphic to the minimal automaton for that language, which has just one state.


Your solution is valid and follows definition of d-ary heap. But as you pointed out your notation is a bit sophisticated.

You might use those two following functions to retrieve parent of i-th element and j-th child of i-th element.

$\text{d-ary-parent}({\it i}) \\
  \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\
  \ \ \ \ {\bf return}\ d(i-1)+j+1$

Obviously $1 \le j \le d$. You can verify those functions checking that $\text{d-ary-parent}(\text{d-ary-child}(i,j)) = i$

Also easy to see is that binary heap is special type of $d$-ary heap where $d=2$, if you substitute $d$ with $2$, then you will see that they match functions PARENT, LEFT and RIGHT mentioned in book.
If I understand your answer correctly you use a geometric progression. In your case you get go $h = log_d(n\,d-1+1) - 1$, which is obviously $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$, which in fact is a valid and correct solution. But just for sake of handling constant fluctuations you might wanna write $\Theta(\log_d(n))$.

The reason for this is that some heaps might not be balanced, so their longest path and shorthest path migt vary by some constant $c$, by using $\Theta$ notation you eliminate this problem.
You don't need to re-implement procedure given in textbook, but you must alter it a bit, eg assigning all children to $AUX$ table using given $\text{d-ary-parent}$ and $\text{d-ary-child}$ functions.

Because $\text{EXTRACT-MAX}$ was not altered, it depends on running time of $\text{MAX-HEAPIFY}$. In your analysis you now you must use worst-case time proportional to hight and number of children which each node must examine (which is at most d). Once again your analysis is very precise, in the end you got $O(d\ \log_d(n(d-1)))$, which can be transformed to:

$O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(d-1))$

For practical reasons we can always assume that $d \ll n$, so we can lose the $d \log_d(d-1)$ part of O notation, then we will get $O(d\log_d(n))$. Which is also valid solution. But not surprisingly you can also analyse function run time using Master theorem, which will show that $\text{MAX-HEAPIFY}$ is not only $O$ but even $\Theta$.
CLRS book already provides INSERT procedure.  Which looks like this:

$\text{INSERT}(A, key)\\
  \ \ \ \ A.heap\_size = A.heap\_size + 1 \\
  \ \ \ \ A[A.heap\_size] = -\infty\\
  \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

It can be easy proven but common sense dictates that it's time complexity is $O(\log_d(n))$. It's because heap might be traversed all the way to the root.
Just like INSERT, INCREASE-KEY is also defined in textbook as:

$\text{INCREASE-KEY}(A, i, key)\\
  \ \ \ \ {\bf if}\ key < A[i]\\
  \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\
  \ \ \ \ A[i] = key\\
  \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\
  \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\
  \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

Complexity is obviously $O(\log_d(n))$ (see previous point).


You've eliminated entropy encoders, which is the type of data you described.

A Memory-less Markov is a contradiction of terms.

The best Compression possible for the specifically generated list of characters, might just be the program that is used to generate the deterministic data in the first place.


If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).

What you are asking is impossible.

One thing which is possible is to compare keys with three rather than two possible outcomes:

If $K(r)$ is close to $K(s)$ then $|r - s| < 1$.
If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$.
Otherwise, we don't know.

Of course, the aim is that the third case happens as rarely as possible. One simple way to achieve this is to choose a random $x$ and some small (non-random) $\epsilon > 0$, and to use
$$
K(r) = \lfloor r/\epsilon + x \rfloor.
$$
Under this definition, the only uncertainty is for $r,s$ at distance $(1-\epsilon,1+\epsilon)$. The random component mitigates even this uncertainty, albeit only by a little.


The following diagram, from a blog post I wrote, is a visual proof that it's impossible:

Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). The first packet always reaches the server at 1.5s on the server's clock, the second always reaches the client at 2s on the client's clock, etc. The packet contents and local arrival times are the only things a protocol could be based on, but the contents and arrival times can be held constant as the asymmetry varies by also varying the initial clock skew.

Basically, asymmetry in the one-way latencies looks exactly like clock skew. Since the problem states we don't start off knowing the initial clock skew or the one-way latency asymmetry, and varying one looks like varying the other so their effects are indistinguishable, we can't separate their contributions in order to solve for the one-way latency asymmetry. It's impossible.

More formally, you can't solve for edge lengths when given only the lengths of the cycles. The cycle basis has $n-1$ degrees of freedom, corresponding to $n-1$ unknown clock skews relative to one of the participants. You can always hide the one-way latencies, even when there are many participants:

If you're not so visually inclined, I have another intuitive argument. Imagine a time portal to a hundred years in the future. As you chat across it to someone on the other side, you realize the conversation is totally normal despite the hundred year asymmetry in one-way delays. Any observable effect would have been obvious on that scale!


Algorithm: Dimension increase in 1D representation of Square Matrix

There is a simple solution, but it requires a different 1D
representation of your matrix $M$. You suppose it is stored in an
arbitrarily long 1D array $A$, so that new elements can be added.

Then the elements of the matrix $M$ are stored such that: $M[i,j]$ is
stored in $A[k]$ with $k=(j-1)^2+i$ if $i\leq j$ and $k=i^2-j+1$
otherwise.

Other similar formulae are also possible.

The idea is to stores in order the successives layers of increased
matrix size starting with the $1\times 1$ matrix.

Storing order of a $3\times3$ matrix is described here, each element of the matrix being its index in $A$. The first index $i$ is the line index of matrix $M$ representation:

  1  2  5
   4  3  6
   9  8  7

When you increase the size $m$ of the matrix, you only have to add the new
layer at the end, i.e. add the representation of the last row and last column
at the end of the used part of array $A$. The cost is linear in $m$.

Explanation

The initial version of the question asked for a linear data structure,
without explicitly allowing for linked-lists, which I do not consider
more linear than anything else, the memory having generally a linear
address space. Hence I assumed the idea was to use, as efficiently as
possible, a one dimensional array $A$, without trying to mimic pointers.

I started looking for an efficient way to store (and retrieve) the
elements $M(i,j)$ of the matrix $M$ in $A$, so that extending the
matrix with an extra dimensional layer for the highest values of the
indices, could be done cheaply ... the cheapest being to add the new
layer right at the end of the existing matrix, so that the cost would
be no more than the number of elements to be copied.

To do that, while keeping a uniform indexing scheme requires to have
done it uniformly, starting from the $1\times 1$ matrix. The question
being somewhat imprecise regarding constraints, I assumed that keeping
each line in one contiguous piece is not really required.

The placement of the elements of matrix $M$ in the linear array $A$ is
illustrated by the above $3\times 3$ matrix, where each element has
the value of its index in $A$.

This organization is such that the index in $A$ of an element $M(i,j)$
of the matrix $M$ does not depend on the size of $M$, but only on $i$
and $j$. Taking $p=max(i,j)$, the placement in $A$ of the
upper-lefmost submatrix of $M$ of size $p$ is independent of the rest
of the matrix $M$. The element $M(i,j)$ is either on the rightmost
column of that submatrix if $i\leq j$, or on its last line otherwise.
Furthermore, the first $(p-1)^2$ elements of array $A$ are already
used to store the upper-left submatrix of size $p-1$. One uses the
next $2p-1$ elements of the $p^{th}$ row and $p^{th}$ column, which
contain element $M(i,j)$. This can be done in different ways, and the
proposed formula stores these $2p-1$ elements in top-down and
right-to-left order.

Note: the first version of the formulae used $p=max(i,j)$ explicitly to
compute the squares, a remnant of my initial search for a
solution. But @WeaklyTyped remarked rightly that the test comparing
$i$ and $j$ does the job, allowing to replace $p$ by $i$ or $j$,
according to the test result.

Actual use of the representation

One characteristic of this representation is that it preserves random access (access time is constant and independent of indices and
matrix size), which is not usually the case with list
representations. However it does not require
multiplication for indexing the array $A$, since only addition and
integer squares are needed. Integer squares can be memorized in a
linear array, or can be computed with addition only if successive
square values are needed in a loop, for example to read a line or a
column of the matrix, using the formula $(p+1)^2=p^2+2p+1$.

But, as usual, the usefulness of such a representation is highly
dependant on the operations needed and their frequency.

Note: this representation was found independently, but it may have been used before. Pointers to the literature are welcome.

A better solution with pointers

(Added July 1st 2014, after the answer was accepted)

The layer approach described in the previous algorithm seems more
effective than most pointer based representations for two reasons:

given $i$ an $j$, it allows access of element $M[i,j]$ in constant
time;
it has no overhead in space for storing pointers (not to mention
possibly greater garbage collection costs).

However, the last statement is not completely true. We chose to use an
array $A$ of "sufficient" length because that initially (in the first
version of the question) seemed a given constraint. But, if we relax
that constraint, it is clear that it is a costly solution in space
since the array $A$ must have a size sufficient to store the largest
version of the matrix $M$ that may be used.

Actually, there is something absurd about the solution presented
above, if it is to be more than an intellectual exercise (but the context and
motivations of the question were not given). If the array
$A$ has the maximum size that will ever be needed, why not simply code
the maximum sized matrix in it, and use at any time only the indices
that are actually needed, given the current matrix size $m$?

Since pointers are (now) allowed, this is a good motivation for
attempting to get the benefits of the solution presented above, without its
absurd drawback.

The idea is quite simple: keep the layer structure presented above,
but store the layers separately, rather than contiguously in the same
array.

So a matrix $M$ of size $m$ is implemented as $m$ arrays $L_p$ with $1\leq
p\leq m$, each $L_p$ having $2p-1$ elements corresponding to the
elements $M[i,j]$ of $M$ such that $max(i,j)=p$.

In order to access $M[i,j]$, one only has to compute $p=max(i,j)$ to
locate $L_p$, and then index appropriately with $i$ or $j$ inside
$L_p$ to get the right element. Actually, as in the first algorithm
above, it may be faster just to have two cases based on a comparison
between $i$ and $j$.  I do not get into the detailed formulae, that
are somewhat obvious to work out.

However this require an extra structure to find a pointer to $L_p$
when $p$ is known.

Three obvious ideas come to mind:

The first idea is to use an array of links to the $L_p$ layers,
which is indexed by $p$. The drawback is that the size of the array must be
the maximum possible value for $m$, but that is not as bad as the
maximum values for $m^2$. The advantage is that accessing any
element $M[i,j]$ will still be in constant time.
The second idea is to use a linked list, which avoids the constant
size array. However, the list has to be followed sequentially to get
the right layer $L_p$. Hence accessing any element $M[i,j]$ will on
the average be in linear time with respect to the current size
$m$. Note that, with this solution, it is better to access the list
from the end corresponding to the largest value of $p$. Firstly, that
is where layers are added or removed. Secondly, assuming that all
elements of $M$ have equal chance of beeing accessed, the
probability of finding an element in layer $L_p$ is proportional to
$(2p-1)/m^2)$, hence a higher probability for higher values of $p$.
Indeed, accessing the list from the higher value of $p$ is on
average twice as fast as accessing from the lower values of $p$
(proof left as an exercise). But access is linear in $m$ in both
cases.
In order to reduce access time, the accessing structure can be a
balanced tree. The size of the tree is linear in $m$, as it is with
a simple list, but the time complexity of finding the right $L_p$ is
now logarithmic in $m$, hence also for accessing an element
$M[i,j]$. While building this balanced tree, it is better to give to
each $L_p$ a weight proportional to $2p-1$ to account for its
probability of being the right layer. However, I have not checked
how much of a difference it makes.

But actually, trying to build a sophisticated balanced tree is
probably self-defeating sophistication, because it may have to be
maintained, and it may require more computation to be explored.  A
better solution is probably a widely branching tree that is walked
very simply by indexation.

Using a tree of indexing arrays

(I have no idea whether this has an official name in textbooks)

The nodes of the tree are arrays of length $2^d$, so that we can build
a balanced tree with nodes of degree $2^d$. The leaf nodes are arrays
of pointers to matrix layers, and the other nodes are arrays of
pointers to other arrays (or nothing).  Without going into details,
given a layer number $p$, The binary representation of $p$ is cut into
chunks of size $d$ which are used as indices for the arrays while
walking down the tree to find the layer $L_p$. With a value for $d$ of
3 or 4, this should give simple and fast access for matrices of
significant size.


Can someone give me an explanation of how dcaches works?

what is considered a miss or hit and how this is calculated

A hit occurs if the request word is in the cache; if not, we have a cache miss.

It isn't clear how much you understand about hardware caches from the question, but I'll assume you at least know the definition of cache sets and lines.

In a direct-mapped cache, each cache set can hold only one line. Thus, the number of sets is equal to the number of cache lines. Usually, cache lines are many words long (e.g. 64-byte cache lines), but in your example a cache line consists of a single word. Since the cache can hold 16 words (lines), we can deduce that there are 16 cache sets.

Each memory address is mapped to a set. The set holding a memory address is determined by the address's set-index bits. If there are 16 sets, then each address must have $lg 16 = 4$ set-index bits. Let's assume these are the lower-order bits of the address. So, for example, address 7 will uses cache set 7 (because the binary representation of 7 is 00000111).

In this problem, the cache starts full (often referred to as a warm or hot cache). You are given a sequence of memory addresses. Each memory address will be either a hit or a miss, as defined earlier. If the address is a miss, the word at that address must be brought into the cache, and the old value is ejected from the cache.

  Also, what would be the difference if the dcache had a two-word blocks instead of 1?

If the size of a cache line is two words, then you have twice as many values in your cache. It is then possible that a requested word is already in the cache, even if you have never requested that address before. This will happen if you previously addressed a word in the same cache-line as that word.


It's just the ordinary English-language meaning of the word:

  peak, n.
  [...]
  4 a (1) : the top of a hill or mountain ending in a point
  Merriam-Webster

See, for example, Wikipedia:

  Fitness landscapes are often conceived of as ranges of mountains. There exist local peaks (points from which all paths are downhill, i.e. to lower fitness) and valleys (regions from which many paths lead uphill).


How do I know if my algorithm is right (without coding)?

You prove that the algorithm is correct.  This requires (1) writing out a precise specification of what you mean by correctness, (2) writing a mathematical proof that your algorithm meets this specification.  Algorithms courses and textbooks often include some material on how to prove algorithms correct, as well as many examples of this, so that would be a good starting point to study, if you want to learn more about proofs of correctness for algorithms.  See also formal methods / formal verification, and possibly the following question on this site: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect


Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n}

You can upper bound this probability as follows. The relative order within a consecutive subsequence of a random permutation is just another random permutation, so the probability that a specific consecutive subsequence of length $\log n$ is monotone is exactly $2/(\log n )!$. Since there are at most $n$ of this (actually, exactly $n-\log n+1$), the probability is at most
$$
\frac{2n}{(\log n)!} \sim \frac{2n}{\sqrt{2\pi\log n}(\log n/e)^{\log n}} = o\left(\frac{1}{n}\right).
$$


Are you using the Training set for testing ? What is your train test split ?

With Neural Nets, it's always the pyramid shape that works. This is because as you go deeper, data about the input is condensed and we get a proper representation of the input for outputting the required class or regression value.

The only reason reverse pyramid nets will work well is overfitting, which accommodates noise and does not generalize well.

http://www.deeplearningbook.org/contents/mlp.html

Try the Bible of Deep Learning for more details.


Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

If the language is infinite, the word $\# w_1 \# w_2 \ldots$ would be infinite, and so doesn't map to an integer in any meaningful way.
Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.


The derivation $T_1 \to U_1$ is not right-regular.  It does not fall into the three allowed categories of rules.  See Wikipedia on right-regular grammars.  If you have a non-terminal on the right-hand side, it needs to be preceded by a terminal.


What is the literature on a sparse matrix encoding of rose trees?

In view of rose tree being just a special case of a graph,
the matrix representation you mentioned is simply the adjacency matrix representation of directed graph. Your particular encoding takes the rose tree's edge to always be directed consistently either from parent to child or child to parent.

Questions about rose tree in this encoding thus can be researched easily by looking up results about adjacency matrix representation of directed tree graph.

Relevant notions are:

get all leaves of subtree -> reachability
graft tree -> wedge sum


Keep a hash table that stores a histogram of the items that have appeared in the past minute, as well as a counter for the number of unique items, initialized at zero. Also keep a circular queue with the actual timestamped list of items.

Every time you see a new item or query the number of unique items, go over the circular queue and delete all items which are older than one minute. For each one that you delete, update the histogram. If a cell in the histogram reaches zero, decrement the unique items counter, and delete the cell. If you are adding a new item, update the histogram, and if the item did not appear in the hash table, increase the unique items counter.


How does CFS prevent a long sleeping task from occupying the CPU?

Just found it out by myself:

each time CFS places a new/old task into the rbtree it does not reuse its old runtime but rather assigns a new one:
se->vruntime = max(se->vruntime, vruntime) where vruntime is the current minimum virtual runtime.

That is basically what is expressed through "sleeper fairness": each task gets a fair share of CPU time, no matter whether it is running or not.


Difference between row-polymorpism and bounded polymorpishm?

So, there are a few differences:

In row polymorphism, you've bound $\rho$ to a name, so you can use it elsewhere. For example, forall rho . rho -> {x : int | rho} is expressible with row polymorphism, but not purely using bounded polymorphism. Likewise, you can even express field deletion this way: forall rho .{x : int | rho} -> rho is a perfectly valid row-polymorphic type, but subtyping doesn't really have a way of expressing this.

Because row polymorphism lets you add and delete fields this way, usually it works with a "stack" semantics, so that old fields are shadowed when new fields of the same name are added.
Bounded subtyping uses, well, subtyping. So with row polymorphism, you can't give x : {x : int, y : int} as argument to a function of type {x : int} ->int. But most systems with bounded subtyping would have non-polymorphic subtyping too, that would allow this, since most systems have {x : int} <: {x : int, y : int}.

Bounded subtyping tends to be  bit more precise and flexible, and the "stack" semantics of row polymorphism don't arise that much. But inference is much easier for row polymorphism, and can work in the absence of any type annotations (for example, in Elm), which usually isn't the case in the presence of subtyping.


For any non-trivial $A,B$, finding a language which both are polynomially reducible to

Part (a) is correct since you can take the language
$$ C = \{ 0x : x \in A \} \cup \{ 1y : y \in B \}. $$
Here $0x$ is the concatenation of the strings 0 and $x$. This part works even when $A,B$ are trivial.

Part (c) is correct by taking $C = \emptyset$ and using $A,B \neq \Sigma^*$, for example.


Are regular grammar languages defined from "accepting" states?

There is a one-to-one correspondence between NFAs and right regular grammars without productions of the form $A \to a$.
Given a right regular grammar with productions of the form $A \to aB$ and $A \to \epsilon$ and starting symbol $S$, create an NFA in which:

The states are all nonterminals.
The initial state is $S$.
A state $A$ is final if there is a production $A \to \epsilon$.
There is an edge labeled $a$ from $A$ to $B$ if there is a production $A \to aB$.

This NFA accepts the same language as the grammar.
You can also easily carry out the transformation in the other direction.
This shows that in the absence of rule of the form $A \to a$, the analogs of accepting states are nonterminals with productions of the form $A \to \epsilon$.
We can replace a production $A \to a$ by a pair $A \to aX$, $X \to \epsilon$, where $X$ is a nonterminal which is common to all such productions, but doesn't appear anywhere else. We can think of $X$ as the accepting sink. A production $A \to a$ signifies a possible transition to the accepting sink.


Karatsuba Multiplication with n/3 division of large number

The algorithm you are looking for seems to be the Toom-3 algorithm.


On-line simulation of a two-head tape Turing machine using single-head tape(s)

Two heads on a single tape are more powerful (in real time) than two single heads on two distinct tapes.

See T. Jiang, J.I. Seiferas and P.M.B. Vitanyi, 1994, "Two Heads Are Better than Two Tapes"

EDIT: I just read the proof and it is not trivial (and I didn't read/understand the details :-):

The language $L = \{ x2x' | x \in \{ 0,1 \}^* $ and $x'$ is a prefix of $x$ $\}$ can be easily recognized by a two-head single tape TM in real time: one of the two heads stays on the beginning of the input, the second moves right and as soon as it reads the 2 both move right and check whether $x'$ is a prefix of $x$.

But $L$ cannot be recognized by a two single-head tapes TM in real time. In a TM with two single-head tapes one of the two tapes is empty and trivially if the first head scans the input while the other copies it, when the 2 is read, the prefix of $x$ is far from both heads.

Hence the prefix(es) of $x$ should be made "quickly" available at every time using a so called "holographic" representation (see fig. 1 of the paper). But if $x$ is incompressible this cannot be achieved and when it is time to check the prefix one of the two heads must move too far from its current position (the number of moves cannot be bound by a constant).


What are some concrete examples of what typed lambda constants are?

With the simply-typed lambda calculus, constants are typically basic datatypes. For example, here is a way to encode booleans in this presentation's notation:
$$
\Sigma_B = \{ \mathrm{false} : \mathsf{bool}, \mathrm{true} : \mathsf{bool} \} \cup
           \bigcup_{T:\mathit{Type}} \big\{ \mathrm{if}_T : \mathsf{bool} \rightarrow T \rightarrow T \rightarrow T \big\}
$$
Note that we can't have a single “if” function: there needs to be one per type. To have a single “if” function that works with multiple types, you'd need to switch from the simply-typed lambda calculus to a typed lambda calculus with polymorphism. In the simply-typed lambda calculus, you have separate functions $\mathrm{if}_{\mathsf{bool}}$, $\mathrm{if}_{\mathsf{bool}\rightarrow\mathsf{bool}}$, etc.

The intended execution rules for these constants are
$$
\begin{align}
\mathrm{if}_T \: \mathrm{true} \: M \: N &\longrightarrow M \\
\mathrm{if}_T \: \mathrm{false} \: M \: N &\longrightarrow N \\
\end{align}
$$
But the choice of reduction rules doesn't affect the type theory. (We normally do want them to preserve types, i.e. the subject reduction property.)

For the type $\mathsf{bool}$, the constants $\mathrm{true}$ and $\mathrm{false}$ are known as constructors: they're ways to build new values of this type. The constants $\mathrm{if}_T$ are destructors: they're ways to take a value of this type and analyze it. Intuitively speaking, whenever a type is a ”data type”, it's defined by its constructors and destructors. An example of a kind of type that isn't a data type is function types, but even there you can think of lambda abstraction as a constructor for function types and application as a destructor. Constructors and destructors are a computational notion, not directly related to typing. (They do get related once you start viewing computation as a way to simplify typing proofs.)

Here's a second example with an encoding of signed integers ($\mathbb{Z}$). Note that this is just one possible encoding, a simple one from the typing perspective.
$$
\Sigma_N = \{ \mathrm{0} : \mathsf{int}, \mathrm{S} : \mathsf{int} \rightarrow \mathsf{int}, \mathrm{P} : \mathsf{int} \rightarrow \mathsf{int} \}
$$
This particular signature defines three constructors: $\mathrm{0}$ (zero), $\mathrm{S}$ (successor) and  $\mathrm{P}$ (predecessor).
You may want to combine booleans and integers. For typing purposes you can just put them together, but for computational purposes it's useful to add a way to destruct an integer, e.g. by adding a comparison function. Here I've made the comparison function piggyback on booleans so that it doesn't need to be polymorphic.
$$
\Sigma_{BN} = \Sigma_B \cup \Sigma{N} \cup \{\mathrm{le} : \mathsf{int} \rightarrow \mathsf{int} \rightarrow \mathsf{bool} \}
$$


Note: I mixed up boolean functions and propositions in what follows for
brevity, and I hope it'll not cause any confusion.

I assume you have defined the function $\max?$ something like this:

max?(e, l) = ge_all?(e, l) && member(e, l),

where

ge_all?(e, []) = True
ge_all?(e, cons(x,xs)) = e >= x && ge_all? e xs.

You will need a bunch of lemmas [they can be proved using structural induction]:

Lemma 1: $\text{member}(e, l) \implies \text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ [this one is suggested by @Alexander]. Its proof is pretty boring because of lots of subcases.

Lemma 2: $\text{ge_all?}(e, l) \implies \text{ge_all?}(e, \text{unique}(l))$.

Lemma 3: $\text{ge_all?}(e, l) \implies \text{ge_all?}(e, \text{repeated}(l))$.

Theorem: $\max?(e,l) \implies \max?(e, \text{unique}(l)) \vee \max?(e, \text{repeated}(l))$.

Proof sketch:

$\max?(e, l)$ implies $\text{member}(e,l)$, which in its turn implies $\text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ [by lemma 1]. So we consider two cases:
(1) $\text{member}(e,\text{unique}(l))$ and (2) $\text{member}(e,\text{repeated}(l))$.

In the case (1) we can prove $\text{max?}(e,\text{unique}(l))$ like this: $\max?(e, l)$ implies by definition $\text{ge_all?}(e,l)$, which [by lemma 2] implies $\text{ge_all?}(e,\text{unique}(l))$. Since $\text{ge_all?}(e,\text{unique}(l))$ and $\text{member}(e,\text{unique}(l))$ we get $\text{max?}(e,\text{unique}(l))$.

The case (2) is similar. End of proof.


When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is called on a set of inputs which were already used, the results are just fetched from the table. This reduces recursive Fibonacci to iterative Fibonacci.

Dynamic programming can be even smarter, applying more specific optimizations. For example, sometimes there is no need to store the entire table in memory at any given time.


Is the halting problem solvable for NPDAs?

There is no "minimal normal form" or the like for PDAs. If there was, a first step would be to minimize the PDA. This minimal type of machine would certainly not allow pathological examples like the one in your other post. We can, however, do something similar.

You can convert any NPDA to an equivalent context-free grammar. For these there are ways to remove useless rules and simplify them, and there are normal forms (Greibach and Chomsky).  Definitely GNF allows answering the "halting problem", because a word of length n is generated in n steps. Going from GNF back to a PDA you get one with a similar property.

Maybe this method is not satisfactory for you, because you would like a more direct analysis of the given NPDA. But as you have observed, this can be very hard, because of possible very complex epsilon-loops.

To summarize: it is decidable whether for a given NPDA, there exists an equivalent one that always halts. But probably this is always true, because there is (e.g. Greibach NF for all context-free languages).

But you ask about a given PDA, not about whether a halting one exists for the same language. Thus for an answer to your question, one might have to analyze which kind of thing the mentioned grammar transformations eliminate and what that means in terms of PDAs.

Therefore, there is strong evidence that the question is decidable, but I have no definite method. In the transformations, one does not detect whether "useless" loops in the PDA/grammar would halt or not - they are simply eliminated, all of them.


Yes, the "line" $u \to v \to w$ is trivially confluent, and so are the empty graph, the graph with a single node, and the "line" $u \to w$. In the case of a graph with a single node $v$ there is only one case to consider, with $v_1 = v_2 = v$. The common ancestor is then $v$ itself, and the common successor is also $v$.


When is it useful to split critical edges?

An easy google search shows in Muchnick, Advanced Compiler Design & Implementation, Section 13.3 Partial-Redundancy Elimination, pp 407-408:

  A key point in the algorithm is that it can be much more effective if the critical edges in the flowgraph have been split before the flow analysis is performed.

So the notion is useful to increase the efficiency of certain flow analyses in redudancy elimination, which aims to find portions of code with common sub-expressions and hoist them out into a single computation, which is facilitated in the absence of critical edges.


Variant of interval scheduling (multiple machines with given availability)

Let us call $n$ the number of intervals and $m$ the number of available machines.

There is an algorithm by Brucker and Nordmann running in time essentially $O(n^{m-1})$. Thus for any constant $m$, the problem admits a polynomial time algorithm. The authors claim that the algorithm is practical up to $m=5$ machines.

When $m$ is not constant, the problem appears to be hard, however I do not know whether the version you stated is NP-hard. In this case, Faigle, Kern and Nawijn show that by a simple greedy algorithm you can schedule at least half of the intervals scheduled in an optimal solution. This is the overview of their algorithm, that they call $G$ (the jobs are denoted by $I_1,I_2,\ldots,I_n$,  and are considered ordered by their left endpoints):

  $G$ places $I_t$ on a free feasible machine if such a machine is
  available. Otherwise $G$ tries to replace a job $I_v$ by $I_t$ on a
  feasible machine with the goal to reduce the maximal remaining
  processing time. If neither action is possible, $G$ discards $I_t$.


Why Halting problem is Recursively Enumerable?

If you want to understand Halting Problem is r.e. by Davis Book notation and you are looking for g(x) you can think of universal program! universal program is the function $\phi (x,y)$ that is the program which run program number $y$ on input $x$.
This program is equal to partially computable function g(x) (see page 30 definition of partially computable). As Ran G mentioned, it is possible program y on input x never halt! That's the reason it is partial function not computable function(i.e. it is both partial and total)

+If function g(x) be computable then the set B will be computable or in the other words it is decidable.


English is neither a language with a given operational semantics nor a model of computation of any other kind. Your question does not make sense.


For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.


Is this algorithm for partial ordering of sets complete and sound?

It is pleasing to see such a nice algorithm.

Your algorithm is correct for all inputs except possibly for two corner cases.

For example, if we have
input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]], then your algorithm will not produce the expected A<=B.
For example, if we have input = [['A', 1], ['B', 1], ['A', 1], ['B',1] or input = [['A', 1], ['A', 1], ['B', 1], ['B',1], then your algorithm will not produce the expected A<=B and B<=A.

The issue is not in your algorithm proper but how you define your input and expected result and how you specify the way to sort all endpoints of the intervals. Here is a sample solution.

Require that all input intervals are non-degenerate and different.
When sorting, break ties with the other endpoint. That is, given A=[1,2] and B=[2,3], when ['A', 2] and ['B',2] are compared, we must put the former before the latter since 1 < 3.

By the way, you can just use const item of input instead of const item of input.reverse(). Also, you may use ${closed.slice(l[0][0],l[0][1])} <= ${l[1]} instead of ${closed.slice(l[0][0],l[0][1])}:${l[1]} since you use "<=" to define the relation. You should get a slightly prettier output.

Last but not least, Code View Stack Exchange should probably be a better place to post this kind of question.


In my opinion, such transducers does not exist.

It is not possible to convert from base 2 to base 1, since the regular language $\{10^n\ |\ n \in \mathbb{N}\}$ would become $\{1^{2^n}\ |\ n \in \mathbb{N}\}$, which is nonregular. However, regular languages are closed under the translation by the finite state transducer.

On the other hand, I was not able to find such a straightforward proof for the opposite case (that does not mean that such a proof does not exist). But I am inclined to believe that it is not possible as well. The reason is that the transducer would have some transitions writing $\varepsilon$ and some transitions writing non-$\varepsilon$ words. However, since the length of the image of $w, |w| = n$ is $O(\log n)$, the transitions writing non-$\varepsilon$ words are used significantly less (but nonconstant number of times) than the $\varepsilon$-transitions on all inputs. However, for a finite state transducer, a transition is either used a constant number of times, or there exists an input such that the number of uses of that transition is at least $\frac{1}{m} n$, where $m$ is number of transitions and $n$ is the length of the input (this is not so hard to prove). Moreover, clearly, such input exists for arbitrarily large $n$. Therefore, we get a contradiction.


Can an instruction with a dependency read the register in same cycle as it's being written?

With modern processors, arithmetic units tend to be able to deliver results simultaneously to a register, and to another arithmetic unit that requires that result.

There is a limit to this, so if you have three add instructions "x = a + b, y = x + x, z = x + x", then the a+b operation is unlikely to be able to send the result to a register, and to four inputs of two more additions. Even reading from a register is likely limited, so in this extreme example you could have (assuming an adder can forward to one input and a register, and registers can be read by two inputs):

Cycle 0: Adds a+b, sends result to x and first input of y = x + x.
Cycle 1: y = x + x reads second input from x; z = x + x reads first input from x
Cycle 2: Adds x + x, sends result to y. z = x + x reads second input
Cycle 3: Adds x + x, sends result to z.

On the other hand, take x = a + b, y = x + a, z = x + b:

Cycle 0: Adds a + b, sends result to x and first input of y = x + a
         y = x + a reads a, z = x + b reads b.
Cycle 1: Adds x + a, sends result to y. z = x + b reads x.
Cycle 2: Adds x + b, sends to z.

So an instruction cannot read a register at the time it is written to, but often results can be forwarded to an instruction at the same time they are written to a register.


Give a $3$-state DFA for $(01 \cup 1)^∗$

It is correct that your DFA accepts 001, which is wrong.

Here is a strong hint. The three sets of strings accepted by the states should be the set of accepted strings, the set of accepted strings with one "0" attached at the end, the set of the strings that contains two consecutive "0"s. (From that description, you can see how to construct simple DFA by the Myhill–Nerode relation.)

In case the above hint does not ring a bell, here is the full answer, which you can reveal by hovering your mouse over it.

   Let state $S_1$ be the set of all strings having no consecutive "0"s and ending in "1". Let state $S_0$ be the set of all strings having no consecutive "0"s and ending in "0". Let state $S_{00}$ be the set of all strings having two consecutive "0"s. $S_1$ is the start state and the accepted state. Here are the transitions.

 $\quad(S_1, 0)\mapsto S_0$
 $\quad(S_1, 1)\mapsto S_1$
 $\quad(S_0, 0)\mapsto S_{00}$
 $\quad(S_0, 1)\mapsto S_1$
 $\quad(S_{00}, 0)\mapsto S_{00}$
 $\quad(S_{00}, 1)\mapsto S_{00}$

 It should be easy to see that the above DFA accepts the given set of strings, $(01\cup 1)^*$.


Tarjan's Strongly Connected Component algorithm

1... On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, n.lowlink)?

The code works either way.  The two possibilities are:

I. n.index == node.index, which means the assignment will never change the value of node.lowlink, or

II. n.index < node.index, which means setting node.lowlink to either n.index or n.lowlink will cause node.index to be unequal to node.lowlink, guaranteeing that node will be part of the SCC containing everything on the stack back to the node with an index matching n.lowlink.

  2... Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?

No, that's not true.  The components of any particular SCC are not guaranteed to have the same .lowlink value, so you can't partition the vertices into SCCs that way.  The .lowlink values are used to determine when to pop the stack; the stack determines what is in an SCC.

  3... Is it ever true that after we recurse in line 30, n may not be in stack?

Yes, n may not be in the stack.  n could be a vertex belonging to a previously identified SCC.  There's a forward link to n obviously but there may be no back link from n or its SCC to the current SCC.


Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

$S\to\lambda$ is unnecessary because $S\to B$ and $B\to\lambda$.
The grammar recognizes the desired language.

You can prove the second assertion pretty easily using induction (for example on the length of the derivation, or the length of the sentence).

You'll probably find it easier to prove two assertions independently:

If a sentence is in $L$, then it is in $L(G)$.
If a sentence is in $L(G)$, then it is in $L$.

Together, these prove equivalence.


What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?

You just need to use $P_1$, $P_2$, $P_3$ and $\Leftrightarrow$ symbols, for example $P_2$ is a formula, $(P_1 \Leftrightarrow P_3) \Leftrightarrow P_2$ is a formula. As stated in the question, you must not use $\vee$, $\wedge$ or $\neg$.
You need to find the number of non-equivalent formulae. For example, $P_1 \Leftrightarrow P_2$ is equivalent to $P_2\Leftrightarrow P_1$, but $P_1\Leftrightarrow P_2$ is not equivalent to $P_1 \Leftrightarrow P_3$.


I think you are trying to build the 2-SAT implication graph for 3-SAT.
In 2-SAT, $(x_a \vee x_b)$ may indeed be considered as 2 implications, $\neg x_a \Rightarrow x_b$ and $\neg x_b \Rightarrow x_a$.
The problem is that $(x_a \vee x_b \vee x_c)$ is not equivalent to any of the 6 implications like $\neg x_b \Rightarrow x_a$, as $x_c$ is sufficient to satisfy the clause.
You may eventually have $(\neg x_a \wedge \neg x_b) \Rightarrow x_c$ or $\neg x_a \Rightarrow (x_b \vee x_c)$, but neither let you build such implication graph.


Assuming NP≠coNP, do we have a similar theorem to Ladner's?

Yes.

Before answering your question, let me make it clear that the reasoning provided in the link Filmus suggests above will not work for $\mathrm{NP\cap coNP}$, since this nasty class refuses to be efficiently enumerated. Also, it is very unclear to talk about $\mathrm{FP^{NP\cap coNP}}$-reductions, not to mention how to enumerate them. Very faint an idea to do complexity theory that way.

By Ladner's splitting theorem for $p$-degrees, every non-zero $p$-degrees splits into two lesser incomparable $p$-degrees.

Now, by the assumption that $NP\neq NP\cap coNP$, the $NP$-complete degree is separated from $P$ (zero $p$-degree). Applying the splitting theorem and downward closure for $p$-m-reduction of $NP$, we have that the complete degree $\mathcal{C}$ splits to two lesser degrees $\mathcal{A}$ and $\mathcal{B}$.

Whenever $\mathcal{C}$ splits into $\mathcal{A}$ and $\mathcal{B}$, we have that $\mathcal{C\subseteq P^{A, B}}$. And, we know that $\mathrm{P^{NP\cap coNP}=NP\cap coNP}$.

So, at least $\mathcal{A}$ or $\mathcal{B}$ must be outside of $NP\cap coNP$. That is the intermediate degree you are seeking.


An efficient data structure supporting Insert, Delete, and MostFrequent

In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$  amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, you may implement your priority queue in $o(\log n)$. Indeed, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $ and $\mathcal{O}(1) $ time for the findMin operation. Thorup proved that

If we can sort $n$ keys in time $S(n)$ per key, then we can implement a priority queue supporting find-min in constant time and updates (insert and delete) in $S(n)$ time.

See M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Since we can sort in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space, as shown by

Y. Han and M. Thorup. Integer sorting in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space. in Proc. FOCS 2002

the bound is proved.


Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?

For a particular $n$, there are at most $2^{O(n)}$ different TMs with $n$ states, and we can have a list for all of them: 1 is the TM halts, and 0 otherwise. A TM that has this "list" in its memory can decide the problem you give in your question. Not only this language is decidable - it is even regular!

The "halting problem" states though, that there is no TM that works for all possible $n$'s.


I'm a bit late, but the only answer does not address the question.

You state that the vocabulary $\sigma$ depends on the choice of turing machine $M$. If this were the case, then indeed the claim would only follow for arbitrary vocabularies.
But - as the index of $\Phi_M$ and the missing one of $\sigma$ hint at - only the formula depends on $M$, the vocabulary is fixed for all turing machines.

Now all this shows, is undecidability for this particular vocabulary $\sigma$. To get the desired undecidability for all vocabularies with at least one binary relation, we have to do the reduction using only a single binary relation. We do this by encoding all of $\sigma$ into a single binary relation. The specifics are a popular exercise (and indeed the first exercise in the chapter), and go back to techniques first used by Kálmar.


Use pumping lemma to show L is not context free

$\{ 0^{2^n} \mid n \ge 0 \}$ is not context-free.

To show this, you can use any of the usual techniques to show that a language is not context-free, such as the pumping lemma for context-free languages.

The pumping lemma states that if $L$ is context-free, then there exists a pumping length $p$ such that for all $n \ge p$, there exist $u,v,x,y,z$ such that $0^{2^n} = uvxyz$ and $|vy| \ge 1$ and for all $k \ge 0$, $uv^kxy^kz \in L$. Take $n = p$: for all $k \ge 0$, $|uv^kxy^kz| = |uxz| + k |vy|$ must be a power of $2$. This is not possible for large $k$ since it would imply that the distance between consecutive powers of $2$ is never more than $|vy|.

You can also use Parikh's theorem, which states that the set of possible numbers of occurrences of a letter in a context-free language is semi-linear (i.e. it's of the form $\{a p + b \mid a \in \mathbb{N}, b \in B\} \cup C$ for some integer $p$ and some finite sets $B$ and $C$). For a language with a singleton alphabet, this means that the set of lengths of words in the language is semi-linear, which $\{2^n \mid n\in\mathbb{N}\}$ isn't.


Can Hall's theorem be applied to scheduling problems?

A Characterization of Open Shop Scheduling Problems Using the Hall Theorem and Network Flow, a thesis by Arunasri Chitti may provide what you need.

The abstract reads:

  Open shop scheduling problems are combinatorial problems where jobs
  with certain processing requirements on a number of different machines
  must be arranged in such a way that objectives related to completion
  time are optimized. Such problems have applications over a wide
  spectrum including such as communications, routing and manufacturing.

  Many open shop problems are NP-hard but there are a number of special
  cases which possess polynomial solutions in the case of few machines
  or few jobs or when preemption of jobs is permitted. Many such
  solutions are based in the theory of matching or Hall’s theorem, or
  more generally network flow. The primary focus of this thesis is to
  describe a number of polynomial-time solutions which are constructed
  using these related concepts and methods.

The paper discusses the problem of scheduling resources to needs in a reasonably optimized fashion, Open Shop Scheduling, and how a particular subset of those scheduling problems "are a number of special cases that do have polynomial solutions and those solutions often come from the theory of matching, network flow and Hall’s theorem, which are related concepts and methods." See What is an NP-complete in computer science as well as What are the differences between NP, NP-Complete and NP-Hard?. Also see the Wikipedia topics NP-hardness and NP-completeness.

Scheduling in the context of the paper is defined as:

  Scheduling deals with the arrangement of a given set of jobs, on the
  given machine such that the provided resources are assigned to the
  jobs in an optimal way. Scheduling provides us the starting and the
  completion time for each operation or job.

A Scheduling problems in the context of the paper is defined as:

  According to Peter Brucker [1], a Scheduling problem is defined as
  following: Given m machines Mj (j= 1, 2...m) and n jobs Ji (i= 1,
  2…n), a schedule now is allocation of one or more time intervals for
  each job on one or more machines.

The thesis goes on to demonstrate the use of applying flow theory to a particular subset of matching resources to needs using graphs. The thesis concludes with:

  Open Shop Scheduling problem is different from other scheduling
  problems. This shop problem is very closely related to matching.
  Although, we have surveyed number of problems where Hall technique
  works, yet there are unexplored problems where matching is applied.
  The connection between algorithms of parallel machines and open shop
  are more close than other shop problems. In this thesis, we have
  learnt flow techinques are useful and seem to be one of the strongest
  tools available for non-NP Complete scheduling problem.


Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. Please check it.

Problem Definition:

The algorithm $\mathcal{A}$ of @norbertpy is for a variant of the original problem:

  To find the minimum positive number $2m$ such that for each item in the array, adding a number from $[0, 2m]$ can lead to a strictly ascending array?

The solutions to these two problems can be reduced to each other (by $\pm m$).
Note that I have ignored the "except the last" part.

A lemma for the property of the algorithm $\mathcal{A}$:

Let $L'[n]$ be the last element of the resulting strictly ascending list of any feasible solution to $L[1 \ldots n]$. We first claim that:

  Lemma: $\mathcal{A}$ gives the smallest value of $L'[n]$ among all the feasible solutions to $L[1 \ldots n]$.

This lemma can be proved by mathematical induction on the length $n$ of $L$.

Now we prove that $\mathcal{A}$ always gives the optimal solution.

Base case: $n = 1$ and $n = 2$ are trivial.

Inductive Hypothesis: Suppose that for any $L[1 \cdots n-1]$ of length $n-1$, the algorithm $\mathcal{A}$ gives us the optimal solution $m$.

Inductive Step: Consider the $n$-th iteration of the greedy algorithm $\mathcal{A}$: it compare a = head + 1 - L[n] with $m$, and take $M = \max(m,a)$ as the feasible solution to $L[1 \cdots n]$.

We aim to prove that

  $M$ is the optimal solution to $L[1 \cdots n]$.

Suppose, by contradiction, that there is another feasible solution to $L[1 \cdots n]$, denoted by $M' < M$.

First, $m < M'$: otherwise, $M'$ is a smaller feasible solution to $L[1 \cdots n-1]$, which contradicts the assumption.

Thus we have $m < M' < M$. Because $M = \max(m,a)$, we obtain $m < M' < M = a$.

By the lemma above, $L'[n-1]$ in the solution corresponding to $M'$ is not less than that in the solution corresponding to $m$. However, $L'[n]$ (for $M'$) is less than that for $M$ (because $M' < a$). According to the way how $a$ is chosen in $\mathcal{A}$, the resulting array (for $M'$) is not strictly ascending. Thus $M'$ cannot be a solution. Contradication.


Semi-decidability of the language $\overline{L_{\epsilon}}$

Assume for contradiction $\overline{L_{\epsilon}}$ is semi-decidable. It's easily proven that $L_{\epsilon}$ is semi-decidable by reduction to the HALTING problem, i.e. $L_{H}$ is semi-decidable. If $L_{\epsilon}$ and $\overline{L_{\epsilon}}$ are semi-decidable, hence $L_{\epsilon}$ is decidable. This is a contradiction, as $L_{\epsilon}$ as well as $L_{H}$ are semi-decidable.
In this prove the following claim was used:

$\textbf{Claim:} \text{ If $L$ and $\overline{L}$ are semi-decidable, then $L$ is decidable}$


Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$?

The two expressions are equal: $3^{\log_2 n} = n^{\log_2 3}$. To see this, you can use the following identities: $\log_a b = \log_c b/\log_c a$, $\log_a b = 1/\log_b a$, and $a^{\log_a b} = b$. Using these identities, we get
$$
3^{\log_2 n} = 3^{\log_3 n / \log_3 2} = 3^{\log_3 n \cdot \log_2 3} = (3^{\log_3 n})^{\log_2 3} = n^{\log_2 3}.
$$


Why do ¬, ∀ and ∃ have the same precedence?

Order of precedence is simply a notional convenience. There is no notion of strength here, just notation. All three operators are unary operators with notation "$\circ\  \cdot$", where $\circ$ denotes the operator symbol $\exists, \forall,\neg$ and $\cdot$ the operand. There can never be any ambiguity in which order to apply these operators: the operator to the right must always be applied to the operand first.

Hence, they have the same precedence among eachother if we consider only those three operators.  (Note that there can be ambiguity if the unary operators have different position, e.g. $-x^2$, this could mean either $(-x)^2$ or $-(x^2)$ if there was no precendence between $^2$ and $-$.)


Resource Allocation Graph: Two processes want the same resource

Where is the problem here?is there a missing edge from ur graph?....As I see it : R3 could be assigned to P1 till it finishes, then to P2 (or vice verca), finally when both P1 & P2 finishes P0 could get R1,R2 (freed by now)


What are the drawbacks of fully-convolutional neural networks?

All-convolutional network is a great idea exactly because it has much more advantages than disadvantages. Most of modern convolutional networks are designed to use CONV for everything. If you are focused specifically on disadvantages, here're a few:

An FC to CONV layer replacement means great reduction in the number of parameters. It's cool to save the memory, but it's loss of flexibility nevertheless. In my experiments, CIFAR-10 classification accuracy dropped slightly after this single change, though it was certainly within one standard deviation. But I'm sure there are cases when this loss of flexibility makes a bigger impact.
A convolution is a significantly slower operation than, say maxpool, both forward and backward. If the network is pretty deep, each training step is going to take much longer.
The network is a bit too slow and complicated if you just want a good pre-trained model. That's why the researches still use AlexNet and VGGNet for experiments. They are simple (in terms of architecture), well-known and provide good performance - that's exactly needed.


Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement)

This problem (at least assuming you wish to find some sort of maximal subset) is simply the multidimensional knapsack problem, see e.g. "The Multidimensional Knapsack Problem: Structure and Algorithms" by Jakob Puchinger, Günther Raidl, Ulrich Pferschy.
To read that paper in your terminology, a quick translation.
Your 'components' are known as resources, their multiplicities as capacities. The $i$th resource $S_i$ has capacity $c_i$. Each of your multisets $M_j$ is an item, and it consumes $w_{ij}$ of the $j$th resource. Thus $w_{ij}$ is the multiplicity of $S_i$ in $M_j$.
Finally in the optimization version that's studied in the linked paper we wish to know the most profitable solution. In this context each of your multisets $M_j$ (AKA items) has an associated profit $p_j$. The paper selects $x_j \in \{0, 1\}$ to determine whether item $j$ is part of the optimal solution, and thus solves the following problem:
\begin{align}
\text{max }\;\; & z = \sum_{j=1}^n p_jx_j\\
\text{s.t. }\;\; &\sum_{j=1}^nw_{ij}x_j \leq c_i, \quad i =1,\dots,m,\\
           &x_j\in\{0, 1\},\quad j = 1,\dots,n.
\end{align}
Note that the paper uses $m$ as the number of components/resources and $n$ as the number of multisets/items.


Minimum number of bits to represent negative number

The representations of the numbers as 6-bit two's complement binaries are
\begin{align}
+32_{10} &= 10\,0000_2\\
-32_{10} &= \overline{10\,0000}_2 + 1_2\\
         &= 01\,1111_2 + 1_2\\
         &= 10\,0000_2
\end{align}
which would give the same representation for both numbers. That means you cannot use 6-bits numbers to represent both values using two's complement.

For 7-bit binaries it works, however:
\begin{align}
+32_{10} &= 010\,0000_2\\
-32_{10} &= \overline{010\,0000}_2 + 1_2\\
         &= 101\,1111_2 + 1_2\\
         &= 110\,0000_2
\end{align}
As you can see, the most significant bit represents the sign of the number.

Another perspective on your question: What is the biggest positive/smallest negative number you can store in an $n$-bit two's complement binary? Then the answer is $2^{(n-1)}-1$ for the biggest positive and $-2^{(n-1)}$ for the smallest negative number.

That means that a 6-bit binary can hold values $-32, \ldots, 31$ and a 7-bit binary values $-64, \ldots, 63$. The number $-32$ then fits into the range of 6-bit binaries, while $+32$ doesn't. You'd need one more bit for the latter.


QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

In order to know that you may just decrement gt, you have to compare the element at position gt to the pivot.

For illustration, here is the relevant part of the code from the slides you took your illustration from:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) exch(a, i, gt--);
   else              i++;
}

Your modification would look like this:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (a[gt].compareTo(v) > 0) gt--;
      exch(a, i, gt--);
   }
   else              i++;
}

If the element is larger, we save a swap, as you illustrated. Furthermore we won't have to compare that element again. If, however, the element is not larger, we will compare it to the pivot twice, once before the swap and once after the swap.

So with your modification we save a swap for each element that is larger than the pivot and on a position that ends up to the right of the pivot, while we introduce an additional comparison for each element in such a position that is not larger than the pivot.

Averaging over all inputs we can expect the  number of elements smaller resp. larger than the pivot to be equal. So the performance will depend on the number of elements equal to the pivot (and the cost of a swap vs. a comparison). Your modification will have the better relative performance, the smaller that number is. But 3-way partitioning was developed with inputs with many equal keys in mind, so the original choice seems reasonable.

Taking a second look at the modified algorithm, we note that if we compare an element twice, there is no other comparison happening between these two. So it seems worthwhile to remember the result of the comparison. However, if we want to keep the structure of the code, this means a lot of control structure overhead:

Boolean doComp = true;
int cmp;
while (i <= gt)
{
   if (doComp) cmp = a[i].compareTo(v);
   doComp = true;
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (cmp = a[gt].compareTo(v) > 0)
      {
         gt--;
         doComp = false;
      }
      exch(a, i, gt--);
   }
   else              i++;
}

My gut feeling is that even though it combines the advantages of the previous two versions in terms of number of comparisons and swaps, it will perform worse due to the overhead of the additional control structures.

Not only have we introduced additional operations (checking conditions, maintaining the flag), we also introduced (compared to Dijkstra's version) two additional conditional jumps (for if and while), that will often but irregularly switch between taken and not taken. The latter is a problem on modern processors, since they rely on branch predictions for optimal performance and such branches will lead to a high number of mispredictions. (The branch corresponding to the outer loop is an opposite example: Always predicting that the loop will be entered is wrong only once.)

With these considerations in mind, we can try to optimize the code. The following should perform quite well:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if (cmp > 0)
   {
      while ((cmp = a[gt].compareTo(v)) > 0) gt--;
      exch(a, i, gt--);
   }
   if (cmp < 0) exch(a, lt++, i++);
   else         i++;
}

This version makes as many comparisons as Dijkstra's version and as many swaps as your suggested version without introducing too much overhead: For each comparison we have one branch based on cmp > 0 and possibly one based on cmp < 0. This is the same as for Dijkstra's version except that the role of the two comparisons is exchanged.

So, summing up / answering your final questions explicitly:

The additional swaps you point out can be avoided without introducing other costs. So, as you suspected, they degrade performance compared to the final version in this answer.
The version you suggest removes the unnecessary swaps, but introduces additional comparisons. So it will too perform worse than the final version in this answer.
As I pointed out, the realitve performance of the original and your version will depend on the input at hand and the relative costs of swaps and compares. (Since usually compares are faster than swaps, I'd expect your version to be faster on average.)


How to define enumeration of the set of finite state machines?

One simple encoding is to represent each of the $N$ states by a partial function $f_n:\{0,1\} \rightarrow \{1, \dots, N\}$. Input $x$ in state $n$ will cause a transisition to state $f_n(x)$ if $f_n(x)$ exists and an error condition if not. You can assume that the initial state is always state $1$.
For $N$ states there are $(N+1)^2$ such partial functions (because either $0$ or $1$ or both may fail to have an image), so there are $(N+1)^{2N}$ encodings. However, some of the encodings will represent FSMs that are isomorphic (because they represent the "same" FSM with a re-labelling of states).
For example, for $2$ states there are $9$ partial functions from $\{0,1\}$ to $\{1,2\}$ and each state can be represented by one of these partial functions, so there are $9^2=81$ representations of FSMs. The $2$ state FSM which stays in the same state on input $0$ and changes to the opposite state on input $1$ is represented by the two functions
$f_1(0)=1 \quad f_1(1)=2\\
f_2(0)=2 \quad f_2(1)=1$


Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n

Suppose that $L$ is an infinite language which satisfies the pumping lemma with constant $n$. Let $w \in L$ be a word of minimal length in $L \cap \Sigma^{\geq n}$ (i.e., among the words in $L$ of length at least $n$, choose a word of minimal length). Since $L$ satisfies the pumping lemma, we can write $w = xyz$ in such a way that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. In particular, $xz \in L$. Since $|xz| < |xyz|$, we must have $|xz| < n$, and so $|w| = |xz| + |y| < n + |xy| \leq 2n$.


Network Flow with multiple connected subsets

Hint: think about your source node and what it is connected to.


How can I make my algorithm more efficient?

If values in both arrays are positive integers, there is an algorithm in $O(n_1 + n_2 + \max(A))$. This algorithm is interesting if those three values are of the same order of magnitude.
The steps are as follow:

check last element of $A$ to know $\max(A)$;
create an array $B$ of size $\max(A)$;
browse $A$ and modify $B$ so that $B[i]$ represents the smallest index $j$ such that $A[j] \geq i$ (that means the number of elements of $A$ that are $<i$);
browse $M$; for $m \in M$, if $m > \max(A)$, return $n_1$, else return $B[m]$.


Find shortest path in undirected graph that goes through all vertices and returns to starting vertex

Travelling salesman problem looks almost the same but I can't repeat a visited vertex.

Going from vertex 3 to vertex 5 I can't do that
3 -> 2 -> 3 -> 1 -> 3-> 4 -> 3

A solution is: 3->1->2->4->3

That's my function:

private static List<HashMap<Integer,Integer>> graph = new ArrayList<>();

public static void dfs(int currentVertex,Stack<Integer> visited,long currentTime) {
    if(visited.size() == graph.size()-1) {
        if(!graph.get(currentVertex).containsKey(targetVertex)) {
            return;
        }

        currentTime += graph.get(currentVertex).get(targetVertex);
        if(currentTime < fastestTime) {
            fastestTime = currentTime;
        }
        return;
    }

    for (Map.Entry<Integer,Integer> vertex: graph.get(currentVertex).entrySet()) {
        if(!visited.contains(vertex.getKey())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}


How is the space complexity O(LogN) for rangeSumBST problem

The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $O(N)$ but the space complexity is $O(H)$ where H is the height of the tree.
Even following the link you provided, they state this:


Two recurrences for the change-making problem with repetition

First, the number of subproblems and dependencies among these subproblems for the first recurrence are $v$ and $nv$ respectively, while they are $nv$ and $2nv$ respectively for the second one.

Pictorially, the subproblem-dependency graph of the first recurrence is a 1D array and that of the second one is a 2D table.

Informally, the subproblem-dependency graph of the second recurrence can be regarded as a "compacted" version of that of the first one in the sense that the 2D table is compressed into a 1D array through the clause $\lor C[i−1,w]$ in the second recurrence.

Formally, inspired by the comment made by @Raphael, if we expand $C[i−1,w]$ recursively in the second recurrence, we get (ignoring the $w \ge x_i$ details)

$$
\begin{align*}
  C[i,w] &= C[i, w-x_i] \lor C[i-1, w] \\
         &= C[i, w-x_i] \lor (C[i-1, w-x_{i-1}] \lor C[i-2, w]) \\
         &= C[i, w-x_i] \lor C[i-1, w-x_{i-1}] \lor C[i-2, w-x_{i-2}] \lor C[i-3, w] \\
         &= \cdots  \\
         &= \bigvee_{j \leq i: x_j \le w} C[j, w-x_j]
\end{align*}
$$

Therefore, we can conclude that $C[n,w] = C[w]$.


The stopping criterion depends on the specific algorithm used; some common ones include after a fixed number of iterations, or after the total improvement over the past $t$ iterations is at most $u$ (for some parameters $t,u$).

No, it's not correct to stop after you make the first improvement.  Usually you will need many iterations of improvements.


Datastructure for lookup of single point in range (3d)?

I would not use a nearest neighbor query, they tend to be expensive compared to window query or range query. However, most indexes that support nearest neighbor also support window queries.

You can use any spacial index that supports shapes, quadtree, R-Tree (especially RStarTree), ...:

Insert your circles into the index. This is often only supported as inserting rectangles, so you may have to insert the MMB (minimum bounding box).
For querying, indexes commonly support window queries (rectangular, axis-aligned windows(boxes)). Just set the window size to 0 by defining the min/min/min corner and max/max/max corner of the query to be equal to your search point. This should return all MBBs that intersect with your search point.
Finally, for all returned circles, you have to manually calculate whether they really intersect with your search point (they may not intersect because the MBB is larger than the circle.

For example-implementations (Java) of various spatial indexes have a look here (shameless self advertisement).


How do I use induction to show that the language of a grammar is contained in a given set?

When proving something about a language generated by a grammar, your induction should be on the number of derivation steps.

Here, the induction hypothesis should be:
$S=>^i a^kAb^kc^jBd^j $ for $i,j < i, A \in \{ X, \epsilon\}, B \in \{ Y, \epsilon\}$ .

base: for $i=1$ we have that $S=>^1 XY = a^0Xb^0c^0Yd^0$. and the hypothesis holds.

step: Assume $S=>^i a^kXb^kc^jYd^j => a^{k'}Xb^{k'}c^{j'}Yd^{j'}$. We have 4 case for the last derivation step.

if it was $X \rightarrow aXb$, then $k' = k+1$ and $S=>^{i+1} a^{k+1}Xb^{k+1}c^jYd^j$
Similar case if it was $X \rightarrow ab$, and then $S=>^{i+1} a^{k+1}b^{k+1}c^jYd^j$
If last derivation was $Y \rightarrow cYd$, then  $j' = j+1$ and $S=>^{i+1} a^{k}Xb^{k}c^{j+1}Yd^{j+1}$
Similar case if it was $Y \rightarrow cd$, and then $S=>^{i+1} a^{k}Xb^{k}c^{j+1}d^{j+1}$

Since $L(G1)$ contains terminal words, the last derivations must be $X \rightarrow ab$ or $Y \rightarrow cd$.

By that we proved that $L(G1) \subseteq \{ a^nb^nc^md^m | n,m > 0\}$


Data General MV/8000 virtues of "No mode bit"

The answer is that Ed deCastro, President of Data General Management, had established a team of engineers in North Carolina specifically to design the next generation CPU. He assigned the task of support and incremental enhancements to us, the Massachusetts team. Three times we proposed a major new architecture, each time with a very sensible mode bit, and described it as a modest incremental enhancement. Each time, Ed saw through our disguise and rejected the proposal, expecting the North Carolina team to succeed. Ed believed that regardless of how we attempted to disguise our proposals, he would know it was a new generation architecture if it had a mode bit. So we had to propose a new generation architecture with no mode bit, even if that made it less efficient. That's how we got it past Ed deCastro. See The Soul of a New Machine, by Tracy Kidder.


Essentially, these Voronoi diagrams are problems about solving Voronoi problems for $L_1$ metric. Both $L_1$ and $L_\infty$ has efficient solutions for the case of points ($O(n \log n$) time complexity algorithms).

You might be interested in some of the Papadopoulou's papers.

For $L_\infty$ metric you can use the more general solution for polygon offset distance. (Gill Barequet, Matthew Dickerson, Michael T. Goodrich:
Voronoi Diagrams for Convex Polygon-Offset Distance Functions. Discrete & Computational Geometry 25(2): 271-291 (2001)).

Since your rectangles are axis-paralle, the offset distance function will be same as $L_\infty$ metric. However, you will have trouble at the corners. I think, you will not have much difficulty in using their results. The algorithm presented by them is quite efficient too.