Time Complexity: Why does $n^n$ grow faster than $n!$?

The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $\log$, which is false. There are countless examples, take:
$$f(n)=n^{100}, \quad g(n)=n$$
If you take their logarithm they become:
$$\log f(n) = 100 \log n,\quad \log g(n) = \log n $$
So their logarithms are both linear in $\log n$, while it's obvious they do not have a similar growth rate.  Another example can be:
$$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$
and their logarithms are:
$$\log f(n) = 2n, \log g(n) = n$$
You can see that $f(n) = g(n)^2$ and it has faster growth rate, but both their logarithms are linear in $n$.
The intuitive reason is that, when you compare $\log f(n)$ and $\log g(n)$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.

In case you are wondering, the reversed direction would actually hold most of the time: If $\log f(n)$ grows faster than $\log g(n)$, and $g(n)=\Omega(1)$, then $f(n)$ grows faster than $g(n)$, and the condition $g(n)=\Omega(1)$ prevents cases like $f(n) = \exp(1/n), g(n) = \exp(1/n^2)$.


Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'

We show a karp reduction from $L$ to any other language $L'$, as long as $L'\notin\{\Sigma^*,\emptyset\}$.

The reduction proceeds as follows. Since $L'$ is non-trivial, there exists $x,y$ such that $x\in L'$ and $y\notin L'$.
Given input $w$, the reduction runs $M$ on $w$ (which takes polynomial time). Then, if $w\in L$ the reduction outputs $x$, and if $w\notin L$ it outputs $y$.

Proving correctness is trivial.

As @dkuper states, this is simply not true if we allow $L'$ to be trivial. However, it is a common mistake to ignore these end-cases in exercises (which I assume this is).


DFA accepting strings with at least three occurrences of three consecutive 1's

No, you don't need NFA (although it is equivalent to DFA) or PDA or Turing machine to solve this problem. It can be easily done with a DFA.

Lets number the states in given DFA in clockwise fashion starting from start state as Q0 to final state as Q9. First of all, it being a DFA, Q9 should have a self loop with label 1 as all possible transitions should be shown from all the states in a DFA.

Now we need to add two states, lets name them Qa and Qb. The changes in the transitions to be made are as follows:-

Instead of having a 1 transition from Q2 to Q3, make a 1 transition from Q2 to Qa.
Instead of having a 1 transition from Q5 to Q6, make a 1 transition from Q5 to Qb.
Make a new 1 transition from Qa to Qb and a 0 transition from Qa to Q3.
Make a new 1 transition from Qb to Q9 and a 0 transition from Qb to Q6.

These changes in the provided DFA will allow it to satisfy given conditions. It simply counts input substring 1111 as two consecutive 111 and skips a step (of three intermediate states), increasing the count be 2.


How to access the bit at a particular index?

This can be done by running an AND between n and a number with it's ith bit set to 1, which can be obtained by 1 << i. The result of this operation will be zero if the ith bit in n is zero, or 1 << i otherwise.

Case of zero:

n     = 10111
m     = 01000 (1 << 3)
n & m = 00000

Case of one:

n     = 10111
m     = 00100 (1 << 2)
n & m = 00100 (1 << 2)

So:

$m = 1 << i$

$\text{if}\; (n \;\&\; m == 0)$

$\;\;\;\;\text{return} \;0$

$\text{else}$

$\;\;\;\;\text{return} \;1$


Intersection of two particular languages

$$L_1 = \{a^{n+1}b^{2n}a^{n+1} \mid n \ge 0\}$$

$$L_2 = \{w \mid (\#_a(w) + \#_b(w)) \bmod 2 = 1\}$$

I assume that $\#_a(w)$ means the number of $a$s in $w$.

First, I would write out some $w$ in $L_1$ and $L_2$:

$$L_1 = \{aa, aabbaa, aaabbbbaaa, \ldots\}$$

$$L_2 = \{a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, \ldots\}$$

From this, we see that words in $L_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L_2$ are always odd length ($(a+b)\bmod2 = 1$).

This means $L_1 \cap L_2 = \emptyset$.

Before OP's edit to post ($L_2 = \{w \mid (\#_a(w) + \#_b(w)) \bmod 2 = 0\}$):

First, I would write out some $w$ in $L_1$ and $L_2$:

$$L_1 = \{aa, aabbaa, aaabbbbaaa, \ldots\}$$

$$L_2 = \{aa, ab, ba, bb, aaaa, aaab, aaba, \ldots\}$$

From this, we see that words in $L_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L_2$ are always even length ($(a+b)\bmod2 = 0$).

This means $L_1 \cap L_2 = L_1$ (because $L_1 \subset L_2$).


A more tutorial-paced presentation of the same/related material is available in:
Roy L. Crole: Basic Category Theory for Models of Syntax. Generic Programming 2003: 133-177. This should help.


Which types of mathematical functions are the least complex for a computer to compute ?

To evaluate polynomial you use Horners scheme, or if you do not know how to compute it, still straightforward naive approach works. It depends on "how big" is this polynomial...

For logarithm and exponent you could use BKM and for trigonometric functions CORDIC.
So ranking by time polynomial is the fastest, and the rest is equally time consuming.
It is hard to tell apart, as basically the same algorithm can compute all these functions.

Using floating point numbers (so inexact results are obvious) the time complexity of special functions is $O(1)$, because underneath you have constant number of rounds no matter what the input was.
Number of iterations is fixed for given precision, so it does not depend on particular input (although angle reduction is time consuming for huge input value).
Polynomial evaluation is $O(n)$ in number of given coefficients using Horner, otherwise it is $O(n^2)$.


Blocking because of concurrency correctness condition

For your first question

  Q: However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

  A: Serializability is inherently a blocking property:
  under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

  Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.

For your second question

  Q: Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

A: An operation is blocked in a history if its invocation event has no matching response event.

I am not able to answer the question "Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?".
My opinion is that it may or may not cause effects in the history. It is non-deterministic.


A semantic network is a graphic notation for representing knowledge in patterns of
interconnected nodes and arcs. It is one way for knowledge visualization and presentation. It was used firstly for for artificial intelligence and machine translation in computer science. What is common to all semantic networks is a declarative graphic representation that can be used either to represent knowledge or to support automated systems for reasoning about knowledge.

Ontology is a representation vocabulary, specialized to some domain or subject. It is a representation of a set of concepts within a domain and the relationships between those concepts. It is used to reason about the properties of that domain, and may be used to define the domain.

You can find more in references as (specially 4):

1)  Sowa, John F., ed. “Principles of Semantic Networks: Explorations in the Representation
of Knowledge”, Morgan Kaufmann Publishers, San Mateo, CA, 1991.

2) Noy N.F., McGuinnes D. L. “Ontology Development 101: A Guide to Creating Your
First Ontology”. Stanford Knowledge Systems Laboratory Technical Report KSL−01−05 and
Stanford Medical Informatics Technical Report SMI−2001−0880, March 2001.

3)María Auxilio, “An Overview of Ontologies”, Center for Research in Information and Automation Technologies Technical Report, Interactive and Cooperative Technologies Lab, Universidad De Las Américas Puebla, México, March 2003.

4) ABDEL-BADEEH M. SALEM, MARCO ALFONSE "Ontology versus Semantic Networks for Medical Knowledge Representation", ICCOMP'08 Proceedings of the 12th WSEAS international conference on Computers, 2008.


Is this problem about picking optimal entries of a matrix NP-complete?

Reduce to maximum-weight bipartite matching.

If you just wanted  for each j, pick at most a($\hspace{.015 in}$j) entries from the j-th column ,

then the reduction would be

One of the parts is    one vertex for each row.

The other part is    for each j, a($\hspace{.015 in}$j) vertices for the j-th column .

The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The  one vertex per row  ensures that at most one element will be picked for each row.

The  a($\hspace{.015 in}$j) vertices for the j-th column  allows the j-th column to be

used a($\hspace{.015 in}$j) times but prevents it from being used more than that.

The weights of the edges make the total weights of the matchings

correspond to your objective function.

.

For  for each j, pick exactly a($\hspace{.015 in}$j) entries from the j-th column ,  you'd do:

Check whether-or-not    n  <  a(1) + a(2) + a(3) + ... + a(m-1) + a(m)  .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be

a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1  +  the corresponding matrix entry  .

This will make it so that all maximum-weight matchings use the whole column part,

thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.


How to show two models of computation are equivalent?

You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is).

Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions are outlined. If you did this formally, you would take a general Turing machine (a tuple) and explicitly construct what the corresponding 2-PDA would be, and vice versa.

Formally, such a simulation may look like this. Let

$\qquad \displaystyle M = (Q,\Sigma_I,\Sigma_O,\delta,q_0,Q_F)$

be a Turing machine (with one tape). Then,

$\qquad \displaystyle A_M = (Q \cup \{q^*_1,q^*_2\},\Sigma_I,\Sigma_O', \delta', q^*_1, Q_F)$

with $\Sigma_O' = \Sigma_O \overset{.}{\cup} \{\$\}$ and $\delta'$ given by

$\quad \displaystyle (q^*_1,a,h_l,h_r) \to_{\delta'} (q^*_1,ah_l,h_r)$ for all $a \in \Sigma_I$ and $h_r,h_l \in \Sigma_O$,
$\quad \displaystyle (q^*_1,\varepsilon,h_l,h_r) \to_{\delta'} (q^*_2,h_l,h_r)$ for all $h_r,h_l \in \Sigma_O$,
$\quad \displaystyle (q^*_2,\varepsilon,h_l,h_r) \to_{\delta'} (q^*_2,\varepsilon,h_lh_r)$ for all $h_r,h_l \in \Sigma_O$ with $h_l \neq \$$,
$\quad \displaystyle (q^*_2,\varepsilon,\$,h_r) \to_{\delta'} (q_0,\$,h_r)$ for all $h_r \in \Sigma_O$,
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',\varepsilon,h_la) \iff (q,h_r) \to_\delta (q',a,L)$ for all $q \in Q$ and $h_l \in \Sigma_O$,
$\quad \displaystyle (q,\varepsilon,\$,h_r) \to_{\delta'} (q',\$,\square a) \iff (q,h_r) \to_\delta (q',a,L)$ for all $q \in Q$,
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',ah_l,\varepsilon) \iff (q,h_r) \to_\delta (q',a,R)$ for all $q \in Q, h_l \in \Sigma_O'$,
$\quad \displaystyle (q,\varepsilon,h_l,\$) \to_{\delta'} (q,h_l,\square\$)$ for all $q \in Q$ and $h_l \in \Sigma_O'$, and
$\quad \displaystyle (q,\varepsilon,h_l,h_r) \to_{\delta'} (q',h_l,a) \iff (q,h_r) \to_\delta (q',a,N)$ for all $q \in Q,h_l\in\Sigma_O'$

is an equivalent 2-PDA. Here, we assume that the Turing machine uses $\square \in \Sigma_O$ as blank symbol, both stacks start with a marker $\$\notin \Sigma_O$ (which is never removed) and $(q,a,h_l,h_r) \to_{\delta'} (q',l_1\dots l_i,r_1\dots r_j)$ means that $A_M$ consumes input $a$, switches states from $q$ to $q'$ and updates the stacks like so:

[source]

It remains to show that $A_M$ enters a final state on $x \in \Sigma_I^*$ if and only if $M$ does so. This is quite clear by construction; formally, you have to translate accepting runs on $M$ into accepting runs on $A_M$ and vice versa.


The source distance does not need to be treated specially. It can change like any other vertex. In this scenario, it'll be updated to -1 by the end of the fourth round. The weights into and out of B will never become quiescent: either B's distance will be more than 2 greater than G's distance, or (say) A's distance will be more than 5 greater than B's distance. So the cycle will still be detected.
Now, if you ever find yourself reducing the source distance below zero, you immediately know that there's a negative cost cycle, and can terminate early. But there's no need to do so for the algorithm to work.


Efficient Median Algorithm With Very Constrained Operators

I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all that just to find the minimum; instead of making that large array (which sounds like it contains $\binom n 2$ elements, not $2n$, unless I misunderstood you), you can basically do the following:

Starting from the left, take every pair of consecutive elements, and put the minimum of the two on the right. Something like this in pseudocode:

temp1 = min(array[i], array[i+1])
temp2 = max(array[i], array[i+1])

array[i] = temp2
array[i+1] = temp1

What will happen is that the minimum element gets moved all the way to the far right using $2(n-1)$ mins and maxs. We can then do our recursive call on the first $n-1$ elements, and repeat until we finally pull out the median.1

1 Some of you reading this will note that basically what we end up with is a bubble sort (reverse in the example I gave) where we stop as soon as we figure out the median. If you decide to move the max to the right instead, then we pretty much are doing a normal bubble sort, but stopping once we get the median.


How do I find the number of inversions using a red black tree?

What you are trying to do is correct. However only number of rotations will not be able to tell you anything about the inversions. The whole procedure is as follows.

You start with an empty red-black tree. Then you insert the elements in the given sequence one by one, in the order that they occur in the sequence.

Whenever an element $x$ in the sequence is inserted, the elements larger than $x$ already existing in the red-black tree are inversions. You need to calculate this number.

You total up all the inversions for all elements and you get the total number of inversions.

You need to augment the red-black tree by keeping the size of sub-trees in the interior nodes. Then you can find the number of elements larger than $x$ either during insertion or after insertions by doing a search of element $x$.

Since you are confused about the strategy, I suggest you should use the second method. Don't count the larger elements during the insertion stage. Count them immediately after the insertion is done and before another insertion is to be done (in a separate function). This will take additional  $O(\log n)$ on the augmented tree.

If all your numbers are distinct then this algorithm suffices. However, if some numbers are same, then you have to modify your insertion to insert only at the rightmost possible position and/or counting only the strictly larger elements depending on your algorithm. You will need to further augment the data structure to hold the min-value and max-value of the sub-tree in the node.


Proving/Disproving that language L is non-regular/CFL

In fact it turns out that there is no simple method to prove things like this. Except when you want to disprove a statement, then a well-chosen counter example suffices. But also here there are no guidelines how to find them. Experience and trial and error, I would say. In your three questions I see three different approaches.

For (1) go look for a counter-example. Since the statement is true for most languages, you have to look for trivial special cases, but still contradicting the general claim.

For (2) you can try contra-positive. Instead of $A \Rightarrow B$ consider the equivalent $\lnot B \Rightarrow \lnot A$. This is then a (somewhat exotic) closure property. Can you recover $L$ from $L'$?

And I am afraid that (3) looks like simple Boolean set algebra. It is in fact the most straightforward of the three questions.


Can any recursion implementation be written as tail-recursion?

You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call is a tail call (just not necessarily a tail recursive call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point.  Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point.  Continuation-passing style essentially makes the stack explicit.  Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

Example

procedure depth_first(t):
  if not-null(t):
    l = depth_first(t->left)
    r = depth_first(t->right)
    return l + r + 1
  else:
    return 0

The first step is to make every procedure take an extra parameter, k which is a continuation procedure (a procedure which you return to by calling it with the return value as its parameter).  Then you turn the procedure "inside out":

procedure depth_first(t, k):
  if not-null(t):
    depth_first(t->left,
       lambda(l):
         depth_first(t->right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)

Should you do it?  Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes.  Otherwise probably not.  One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand.  Let the compiler do what it's best at and concentrate on writing maintainable code.


Algorithm for finding cycles in a hypergraph

Yes, there is a simple and efficient algorithm for this.

Given a hypergraph $H=(V,E)$, construct an undirected graph $G$ as follows: add the edge $(u,v)$ to $G$ if there is a hyperedge that contains both $u$ and $v$.  Find the connected components of $G$.

Your condition (ii) is now equivalent to: $v_0,v_1,\dots,v_n$ are all in the same connected component.  Thus, you want to find a subset of vertices that are all in the same connected component, but aren't contained in any hyperedge.

This leads to a simple algorithm.  Iterate over the connected components of $G$.  Let $S$ denote the set of vertices in one connected component of $G$.  Test whether $S$ is contained in any hyperedge of $H$.  If it isn't, then the hypergraph has a cycle (any cycle in $G$ that visits each vertex of $S$ at least once, and doesn't visit any vertex outside $S$, is a cycle in $H$).  If after testing all the connected components of $G$, none of them are a valid cycle, then the hypergraph doesn't have any cycles.

(You don't need to test any of the subsets of $S$.  If $S$ isn't a cycle, then none of the subsets will form a cycle, either.  Why?  If $S$ violates condition (i), then every subset of $S$ will violate condition (i), too.)


Yes, this can be done in linear time. The vertices whose removal causes the graph to split into multiple components are called articulation points. The number of such components for each vertex is the number of biconnected components that the vertex belongs to. For biconnected components and algorithms for computing them see the wikipedia page https://en.wikipedia.org/wiki/Biconnected_component.


Method for finding Hyperrectangle that a coordinate is within

The best algorithm will depend on the proportion of hyperrectangles to dimensions. If I understand correctly, what you want is to do a first-pass computation where you build a data structure in order to get a sublinear algorithm (in terms of the number of hyperrectangles) that will tell you which hyperrectangle a point is in.

I think a binary search tree would work well. At each branch of the tree you can split the set of hyperrectangles in half by performing a check to see if coordinate X_i is greater than or less than some value. You want to include in each set every rectangle that is at least partially inside the split region. For example, if you have a rectangle from (0,0) to (2,2) and you split on the first coordinate at 1, you would want to include this rectangle in both sets. Continue until you have only single hyperrectangles - these will be the leaves of the tree.

How and when you split is up to you. Each time the number of hyperrectangles on both sides should be roughly equal. An approach where you just cycle through the dimensions would probably work well. For example, first you split halfway along X_1, then halfway along X_2, ... eventually you split halfway along X_d, then you start over if necessary.

If n is the number of hyperrectangles, then the construction step should take about O(n*log(n)), and the lookup step should take about O(log(n)) each time.


Why analysis of Aloha protocol uses Poisson distribution?

IMO, the biggest reason is that Poisson distribution is more tractable mathematically. Some experimental studies claim that it does follow Poisson. However, there are also other experimental studies show that it does not.

Mathematically, Poisson distribution can be viewed as the approximation of binomial distribution under certain conditions. However, it is not the rationale behind the Aloha protocol.

As a mathematical model, you should consider your own scenario carefully and decide whether to use it or not.


Minimum distance between start and end by going through must visit points in a maze

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a tree where every leaf is grey or red (there may be grey and red vertices in the interior of the tree, too). Now perform a depth-first traversal of the tree, investigating the children of each node in arbitrary order, except that, if one of the children is on the path from the start to the red (end) node, that child is investigated last. If the red node was a leaf, you are done; if not, take the unique path from the leaf you finished at to the red node. The total distance is twice the number of edges in the reduced tree, minus the number of edges on the shortest path from the start to the red vertex.

For general graphs, the problem is NP-hard. Consider the special case where the "maze" actually has no black squares. What we have is, essentially, a so-called rectlinear TSP, where the start, end and grey squares are the "cities". Rectilinear TSP is metric TSP using the Manhattan distance as the metric. The input is a set of points with 2D integer co-ordinates. Observe that metric TSP doesn't care whether you revisit cities or not because it obeys the triangle inequality: if the shortest route from A to B is via C, and the salesman has already visited C, he'll just drive straight past; in the maze world, we don't care whether he stops or not, since he's allowed to stop in a city as many times as he wants. Rectilinear TSP is NP-hard: see Garey, Graham and Johnson, Some NP-Complete Problems (Proc. 8th STOC, pp. 10–22, 1976; ACM DL).

To prove NP-hardness of the maze problem, we need to demonstrate a reduction from rectilinear TSP. This isn't quite trivial because the maze problem has specified and distinct start and end squares but I'm reducing from rectilinear TSP, in which the salesman starts at any city he chooses and returns to that city at the end. But observe that it doesn't matter what the start city is, since the tours ABCDA and CDABC have exactly the same length: forcing the tour to start at a particular city doesn't actually change the answer. So, if I'm allowed to cheat once more and put the red and orange squares in the same place, I'll do that. But you probably mean that squares have a unique colour, so here's the full reduction:

  Take the northern-most of the cities and make it be the start square (if there are multiple cities equally far north, choose any one of them. Make every other city a grey square. Place the end square one square to the north of the start square and colour black the squares north, east and west of the end square. Make every other square white.

Because of the black walls, any route from the start square to the end square must revisit the start square immediately before going to the end. The end square and its black walls are outside the convex hull of the original cities, so no optimal tour of the original cities would have gone through those squares. Therefore, a shortest route from the start square to the end square consists of a solution to the rectilinear TSP problem (a shortest tour from the start city, through all the other cities and back to the start city), followed by the one-square move from the start square to the end square. This completes the reduction.


Skip List estimate number of elements less than (or greater than) a value

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach.  Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.).  Annotate each node with the size of the subtree under that node.  Then, make this data structure persistent.  This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely.  In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable.  Instead, updates essentially work by creating a new copy of the data structure.  Thus, each thread has its own copy of the tree.  The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree.  To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry).  Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.


Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no efficient algorithm for solving your problem. In particular, you won't find any closed form.

Roth showed that the number of satisfying assignments is even NP-hard to approximate within $2^{n^{1-\epsilon}}$ for any $\epsilon > 0$. This means that even finding a decent closed-form approximation can be ruled out.


Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

Let $L=\{a^p \mid p \in \text{Prime} \}$.

Let $m,n\in\Bbb N$, $m<n$. Let $s$ be the smallest prime number that is bigger than $(3n)! + 3n$.

$a^na^{s-n}=a^s\in L$.
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n < s - (n-m) < s $.

Any number between $(3n)! + 2n $ and $(3n)!+ 3n$ inclusive is not a prime number.
Any number between $(3n)!+3n$ and $s$ exclusive is not a prime number.

So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.

The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.


Can someone tell a formal definition for this problem: k-disjoint triangle?

Finding $k$ disjoint triangles in a graph means that you color $3k$ vertices with $k$ colors, $\chi_i, 1 \leq i \leq k$ such that for each color $\chi_i$, the graph $G[X_i] \simeq K_3$, where $X_i$ are the three vertices that received color $\chi_i$.
It simply means that you cannot use the same vertex in two different triangles.
This type of problem is often referred to as $K_3$-packing or triangle-packing: You want to "pack" as many triangles as possible in a graph $G$.
The problem is NP-complete even if you are given a tri-partition of the graph, and this problem is called 3-dimensional matching, one of Karp's 21 NP-complete problems.


Why is the VC dimension different on intervals and half intervals?

I assume a half interval $I_a$ is always of the form

$$ \{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\} $$

This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \{y,z\} \subset \mathbb{R}$ such that $y < z$. $S$ is not shattered, since it is impossible to find a half interval $I_a$ such that $S \cap I_a = \{z\}$ (if $z$ is included in the intersection, than $y$ has to be included as well).

When we consider intervals $I_{a,b} = \{(a \leq x \leq b \mid a,b \in \mathbb{R}\}$ in contrast to half intervals, we are able to find an interval $I_{a,b}$ such that $I_{a,b} \cap S = \{z\}$ (as well as for all other subsets of $S$). This makes the difference in the VC dimension.


Here are some checks you can perform for yourself:

Is there any recursion in the rules?
No: The language is finite, hence regular.
Can the recursions all be written in the form of $A \to \alpha B$, with $\alpha$ a terminal string and $A$, $B$ non-terminals?
Yes: The grammar is (or can be transformed into an equivalent) right-regular (one), hence the language is regular.

If there are constructs like $A \to \alpha B \beta$ or even $A \to \alpha A \beta B \gamma$, then you'll have to look more closely, and there's no easy way: deciding whether a context-free grammar generates a regular language is, in general, undecidable (cf. Greibach's theorem).
See our reference questions for techniques for showing either direction.


Probability of data loss for mirrored,3 disk system

Let us look at the probability of the "123" event happening. That is, Disk 1 fails, and then Disk 2, and then Disk 3, and all of these happen within a span on $H$ hours. Your claim is that the probability of this is $F ∗ (\frac{FH}{365∗24})^2$. But the $\frac{FH}{365∗24}$ term only denotes the probability of a disk failing in the $H$ hours after the first  disk fails. In particular, it does not consider the ordering constraint of "Disk 2 fails before Disk 3 fails".

Instead, what $F ∗ (\frac{FH}{365∗24})^2$ denotes is the probability that Disk 1 fails, and in the ensuing $H$ hours, both Disk 2 and Disk 3 fail. So this captures both the events "123" and "132".

Similarly, the probability of either the event "213" or "231" happening would be $F ∗ (\frac{FH}{365∗24})^2$. And similarly for the events "312" and "321" combined.

So the final answer should be $(F ∗ (\frac{FH}{365∗24})^2) * 3$, and not $(F ∗ (\frac{FH}{365∗24})^2) * 6$.


Property testing of a complete multipartite graph

The following answer construct a tester for a graph being complete $\ell$-partite for a fixed value of $\ell$.
Consider the following tester:

Choose $\ell+1$ vertices at random.
Verify that the edges between them are consistent with a complete $\ell$-partite graph, that is, there is a way to color the vertices using $\ell$ colors such that there is an edge between two vertices iff they have different colors.

We claim that for every $\epsilon>0$ there exists $\delta>0$ such that if the test succeeds with probability at least $1-\delta$, then the graph is $\epsilon$-close to complete $\ell$-partite. To show this, we assume that the test succeeds with probability at least $1-\delta$, and show that the graph is $\epsilon(\delta)$-close to complete $\ell$-partite, where $\epsilon(\delta) \to 0$ as $\delta \to 0$. Moreover, the proof is by induction on $\delta$, the case $\ell = 1$ being trivial.
Let $\gamma$ be the probability that $\ell-1$ randomly chosen points form a clique. If $\gamma \leq \sqrt{\delta}$ then the graph passes the test for being complete $(\ell-2)$-partite with probability at least $1-\sqrt{\delta}-\delta$, and we complete the proof by induction. Assume, therefore, that $\gamma \ge \sqrt{\delta}$.
The expected failure probability of the test given that the first $\ell-1$ points form a clique is at most $\delta/\gamma \leq \sqrt{\delta}$. In particular, we can find a clique $x_1,\ldots,x_{\ell-1}$ such that with probability $1-\sqrt{\delta}$ over the choice of $x_\ell,x_{\ell+1}$, the graph induced by $x_1,\ldots,x_{\ell+1}$ is consistent with a complete $\ell$-partite graph.
Define the color $c(x)$ of a point $x \neq x_1,\ldots,x_{\ell-1}$ as follows. If $x$ is connected to all but $x_i$, then $c(x) = i$. If $x$ is connected to all, then $c(x) = \ell$. Otherwise, $c(x) = \bot$. Then with probability $1-\sqrt{\delta}$, the following holds:

Either $c(x_\ell) = c(x_{\ell+1}) \neq \bot$ and $(x_\ell,x_{\ell+1})$ is not an edge,
Or $c(x_\ell) \neq c(x_{\ell+1})$, $c(x_\ell),c(x_{\ell+1}) \neq \bot$, and $(x_\ell,x_{\ell+1})$ is an edge.

This shows that we can partition all but $\sqrt{\delta} n$ of the vertices into $\ell$ sets, such that the induced graph differs from the corresponding complete $\ell$-partite one in an $O(\sqrt{\delta})$-fraction of edges.


Is a "protocol" a set of algorithms and data structures?

is a protocol a pack of algorithms and programming source codes? (in both the computer and network)

No. A protocol is an abstract description of how systems communicate. Source code could be an implementation of a protocol, but the protocol is not the same as its implementation. Basically, a protocol tells a programmer "the messages should be formatted like this and you should respond in this way to this message", but it is up to the programmer to decide how to implement this in an algorithm and/or source code.

  regarding the previous question, if so, that means the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follows the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)

Yes, operating systems and other hardware do contain code (or sometimes specialized hardware) that implements protocols. However, the way a protocol is implemented may (will) be different between different operating systems and pieces of hardware. The protocol sets standards for how the system should behave to the outside world, but not for how this is implemented internally.


Difference between auxiliary space v/s space complexity

First consider the definitions below:

$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.

$\mathbf{Space \space Complexity}$ is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity $\textit{includes}$ input size.

I can see where your confusion comes from; usually, when we say "Space complexity of Mergesort" we mean its Auxiliary Space, because we obviously cannot improve the space we use for the input itself. As such, some of the statements in your question are not correct.

$\bullet$ Mergesort has Auxiliary space of $O(n)$ (in its common use) since you allocate a new array, and Space complexity of $O(n)$

An example between the two would be:

If we compare Quicksort and Mergesort, they both have a space complexity of $O(n)$ and run at $O(n\log n)$ time, but Mergesort requires Auxiliary space of $O(n)$ while Quicksort requires Auxiliary space of $O(1)$

Finally, to answer your question: usually the intention while asking about "space complexity" is indeed Auxiliary space, although there is some ambiguity here in regard to the formal definitions above. To be pedantic, you can separate the two space complexity types in your answer.


Can a Post machine have more than one accepting state?

According to the description on Wikipedia, there could be more than one accepting state. The truth is, it doesn't matter. The model with a single accepting state and the model with many accepting states are equivalent. A machine of the former kind is also a machine of the latter kind. In the other direction, starting with a machine with many accepting states, single out one of them as the "real" accepting state, and add transitions from the other states to the chosen accepting state.


What is the maximum possible degrees of a vertex of an MST

Suppose that the graph is already a tree. Then the minimum spanning tree is the graph itself. In particular, if we take a star on $n$ vertices, we obtain a minimum spanning tree having a vertex of degree $n-1$. This is optimal, since in a graph containing $n$ vertices, all degrees are at most $n-1$.


Two-State Turing Machine for Parenthesis Matching

Just a "source code" compendium of Raphael's answer: this a working version that uses the same trick (on state q1) and has tape alphabet:
_  ( ) [ { / \   (where $\_$ is the initial blank symbol)

q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

You can see it at work using a Turing machine online simulator; the source code is:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

A final note: if you want to see how this technique can be pushed to the limit, read (and try to understand :-) the construction of the Universal Turing machine with 2 states and 18 symbols by Y. Rogozhin in "Small universal Turing machines"


Since the graph is complete, any set $S$ will induce a cut of weight

$$\sum_{i\in S, j\notin S} c_ic_j ~~=~~ \sum_{i\in S} c_i \cdot \sum_{j\notin S} c_j.$$

Denote the two sums in the latter formula by $A$ and $B$. The problem of finding a maximal cut then means maximizing $A\cdot B$, while $A+B$ is fixed. It is well-known that the maximum of this product is achieved for $A=B$. In this case the product becomes $\left(\frac 12 \sum_{i=1}^n c_i\right)\cdot \left(\frac 12 \sum_{i=1}^n c_i\right) =  \frac 14 \left(\sum_{i=1}^n c_i\right)^2$. So $W$ should not be a quarter of the sum of squares, but a quarter of the square of the sum.

So the reason you could not prove the correctness of the reduction is, that the reduction as given is not correct. (And I'm somewhat embarrassed that I only noticed this after your followup question in the comment.)


Solve SUBSET SUM for Reciprocals of Primes

The observation is that the denominator of the reduced fraction $1/p_{i_1} + \cdots + 1/p_{i_m}$ is $p_{i_1} \cdots p_{i_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't divisible by any $p_{i_j}$. Indeed, the numerator is simply
$$
\frac{p_{i_1} \cdots p_{i_m}}{p_{i_1}} + \cdots + \frac{p_{i_1} \cdots p_{i_m}}{p_{i_m}}.
$$
All terms but the $j$th are products of $p_{i_j}$, but the $j$th term isn't, so the numerator isn't divisible by $p_{i_j}$.

As a consequence, if $\alpha/P$ is a sum of reciprocals of distinct primes, then we can read off the primes from the prime factorization of the reduced form of $\alpha/P$. We can compute this reduced form efficiently using GCD. Since we know $p_1,\ldots,p_n$, we can figure out whether the denominator is a product of a subset of $\{p_1,\ldots,p_n\}$, and if so, it only remains to check whether $\alpha/P$ is equal to the sum of reciprocals of prime in this subset.


Each teacher has given a form to each student.

becomes

$$\forall x\forall y[\mathrm{Teacher}(x)\wedge\mathrm{Student}(y)\to\exists z(\mathrm{Form}(z)\wedge\mathrm{Give}(x,y,z))]$$
The main thing is to understand this table:

$\begin{eqnarray*}\text{every } A\quad & \forall x(A(x)\to\dots) \\ \text{some } A\quad & \exists x(A(x)\wedge\dots) \end{eqnarray*}$


Common Algorithms without Asymptotically Tight Bounds

This is somewhat of an anomaly, but yes - technically you could say that there are such algorithms. For example, consider an algorithm that checks whether a number in unary encoding is a prime - the first thing the algorithm can check is whether the number is even, this takes $O(n)$ time.

If it is, the algorithm rejects, otherwise it applies some primality test that takes $\omega(n)$ (at the very least by first converting it to binary, which takes $\theta(n\log n)$).

The point is that on every input of even length, the algorithm stops "quickly", so there is no asymptotically tight bound.

But this is clearly a stupid example.
One way to avoid this problem is to define the running time of an algorithm on inputs of length $n$ to be the worst case running time on inputs of length at most $n$. This way  you can get a tight bound.


What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies?

Closure and cover are two completely different things.

The closure of a set of attributes or a functional dependency $f$ is a set of relation schemes that can be implied by $f$. In order to find the closure, we can expand the FD or the set of attributes based on the given set of FDs by replacing each relation with the ones inferred by it. For example,

$$X = \{ f_1:A \rightarrow BC,~~~ f_2: C \rightarrow D,~~~ f_3: BD \rightarrow E, ~~~~f_4: F \rightarrow G , ~~~~f_5: F \rightarrow H \}$$

then the closure of $f_1: A \rightarrow BC$ or $\{A\}$ is $\{A,B,C,D,E\}$:

$$A \rightarrow_{f_1} ABC \rightarrow_{f_2} ABCD \rightarrow_{f_3} ABCDE$$

while the closure of $F\rightarrow G$ is $\{F, G, H\}$.

The cover of a set of functional dependencies $X$ is a set of functional dependencies $Y$ that is equivalent to $X$ and the left-side of each functional dependency in $Y$ is unique. Though, not every cover is minimal, and we are usually looking for minimal cover. For example a cover of $X$ is,

$$Y=\{f_1:A \rightarrow BC,~~~ f_2: C \rightarrow D,~~~ f_3: BD \rightarrow E, ~~~~f_4: F \rightarrow GH \}$$

Please do some search before posting your questions, there are plenty of resources on the web, including Wikipedia and Wikipedia.


The grammar is always LALR, if no merging is possible and in this case LALR = CLR, but when merging is possible, we have to see that if conflicts come up and if they do come up, grammar is not LALR and if they don't,the grammar is LALR.


In circuit complexity, a monotone operation is a function $f$ which is also monotone: if $x \leq y$ then $f(x) \leq f(y)$, where $x \leq y$ is a shorthand for $x_i \leq y_i$ for all $i$. There are many ways to define modulo $N$, but most of them are probably either uninteresting or not monotone. For example, consider the function which is true if the input is divisible by $N$. Then $f(0) = 1$ while $f(1) = 0$, and $0 \leq 1$ no matter what the actual length of the input is.


Decide if L is regular or not and argue it. Trying to use Pumping Lemma

(a): Recall that regular languages are closed under complement, i.e if $L$ is regular, so is $L'$. ($F_{L'} = Q_L- F_L$)

Assume that $L$ is regular.
This follows: if $L = \{x \in \{0,1\}^* \mid |x|_0 \neq 4.|x|_1 \}$ is regular, then so is $L' = \{x \in \{0,1\}^* \mid |x|_0 = 4.|x|_1\} $

Now you should show that $L'$ is not regular. And that gives you a contradiction.

(b) You can construct the following DFA for this.


algorithm for finding a straight line to separate class

First sort data base on their $y$ value. Then find the minimum and maximum value between members of the second class which is denoted by $y_{min_2}$ and $y_{max_2}$, respectively. Then, line with equation of $y = y_{min_2}$ and $y = y_{max_2}$ are candidate. We can count the number of first class member in sides of these two lines in $O(\log(n))$.

Therefore, we find an algorithm which works in $O(n\log(n))$.


Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).


Is finding if a graph has k isolated nodes a NP-Complete problem?

No, determining whether a graph has $k$ isolated vertices is not1 NP-complete. Just count the number of isolated vertices and compare against $k$. This can be done deterministically in linear time (linear in the size of the graph's description; possibly quadratic in the number of vertices).

1 Unless P=NP and, even then, it might not be NP-complete.


I agree in principle with the comment suggesting that a recursive implementation would be simpler to analyze, and the other comment mentioning that there is no "legal" definition of such an algorithm like merge sort.

However, I think you've done yourself a favor (in terms of your learning objectives) by attempting to implement this bottom-up (rather than top-down), iterative (rather than recursive) merge sort, which is essentially what you have above. I think this shows good understanding on your side. Perhaps you can attempt to implement an in-place version, rather than creating a newList (etc.).

Typically, you would divide the input into two equal parts, sort each, and then merge. Instead, you start "at the leaves" and progress up the chain -- merging singletons, then merging pairs, then merging pairs of four items, etc. Each iteration of your loop "looks like" a particular depth-level in the recursive tree of typical merge sort.

That said, your delete-based approach isn't the most suited for arrays (which, it seems, CPythons lists are under the hood -- a Google search found this) at all in terms of cost. You should be able to fix this, but when doing so, be careful to handle non-power-of-two input sizes.


How to know if a problem belongs to NP Class?

Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast.
From my experience, it's more about the type of problem than what specific constraints you give it.
For example Indipendent-Set: Including a vertex at one end of the graph may inpact if you can take a vertex at the other end of the graph. This kind of unforeseeable side-effects makes it impossible to really find an algorithm, because you can't decide anything about your solution because you don't know the implications.

On the contrary is sorting: If you use quicksort, you can pick a pivot and split the elements into 2 parts, the ones lower and the ones higher than the pivot.
This way you already made the problem easier: You only need to sort these 2 parts, and you know which of them belongs to which side of the pivot.

Getting such a handle on a NP-hard problem was not successful yet.

I know that this was pretty vague, in the end you can't generalize your question. Every change to a given problem may generally make it NP-hard, you need to look individually.

To prove that something is NP-hard, you can try to reduce an known NP-hard problem to it. This is how it's done with most of them.

An example for your question would also be:
The Maximum-Cut problem is NP-hard, but if you only ask if there exists a cut of size |E|, then it becomes easy, because it is equivalent to asking if the graph is bipartite


What does it mean to be Turing reducible?

From wikipedia article Turing Reduction, in computability theory, a Turing reduction from a problem $A$ to a problem $B$, is a reduction which solves $A$, assuming the solution to $B$ is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve $A$ if it had available to it a subroutine for solving $B$. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for $B$. Turing reductions can be applied to both decision problems and function problems.

This potentially allows us, along with a few other things, to solve problem $A$ using a deterministic Turing machine if $B$ is solvable using deterministic Turing machine.

I assume $SUPERHALT = \{ \langle M,x \rangle \ | \ M^{HALT}$ halts on input $x \}$. If so, then your reduction is incorrect.

First of all, a Turing machine $M$, that uses $HALT$ as an oracle, cannot be used as a non-oracle machine and given as an input of $HALT$. So using something like $HALT(\langle M, x \rangle)$ leads nowhere.

We can use relativizing proof to prove that $SUPERHALT$ is unsolvable even with availability of $HALT$ as an oracle.
We simply take Turing's original proof (with the machine given as self-input) that the halting problem is unsolvable, and give all the machines an oracle for the halting problem. Everything in the proof goes through as before.

From the fact that $SUPERHALT$ is unsolvable (even with the availability of $HALT$ as an oracle) we can prove $SUPERHALT \not\leq_T HALT$. Suppose there is a turing reduction $M'$ for $SUPERHALT$, which uses $HALT$ as a subroutine. Then this $M'$ which  uses $HALT$ as an oracle is able to decide  $\langle M^{HALT},x\rangle \in SUPERHALT$.   This is a contradiction. Hence $SUPERHALT \not\leq_T HALT$.


Finding a negative cycle in a bipartite graph

Given a directed graph, turn each edge $(u,v)$ into two edges $(u, x)$ and $(x,v)$ with the same weight where $x$ is a newly added vertex. Now the graph becomes a bipartite graph, and there is a negative cycle in the original graph if and only if there is a negative cycle in the new bipartite graph.

Suppose the two parts of the bipartite graph are $X$ and $Y$. We increase the weights of all edges from $X$ to $Y$ by $r$ and decrease the weights of all edges from $Y$ to $X$ by $r$, where $r$ is a large enough positive integer. Now we get a new bipartite graph where all edges from $X$ to $Y$ have positive weights and all edges from $Y$ to $X$ have negative weights. In addition, there is a negative cycle in the original bipartite graph if and only if there is a negative cycle in the new bipartite graph.

So if there is an $O(f(|V|,|E|))$ algorithm to solve your problem, we can solve the problem on general directed graphs in $O(|E|+f(|V|,|E|))=O(f(|V|,|E|))$ (since $f(|V|,|E|)\in \Omega(|E|)$) time by applying the algorithm on the bipartite graph obtained from the conversion above. This means your problem is asymptotically no easier than the problem on general directed graphs.


What is the runtime of the 'Risch Algorithm'?

The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log_2, \pi, e^x, \sin x$.
Akitoshi Kawamura in his dissertation Computational Complexity in Analysis and Geometry has proved that integration is $\#P{-}complete$ operation.

There are multiple modifications of the Risch algorithm, but still nobody have implemented the full algorithm (source: Wolfram, survey over CAS systems) in algebraic case.


Is the difference of two context-free languages still context-free?

The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.)

See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.


Implementing abduction over first order theories

You could use an SMT solver inside a counterexample-guided inductive synthesis loop to learn an expression that fits. The paper below does something similar. If you aren't interested in finding the weakest expression, you could save on computational costs by using templates.

Albarghouthi, Aws, Isil Dillig, and Arie Gurfinkel. "Maximal specification synthesis." ACM SIGPLAN Notices. Vol. 51. No. 1. ACM, 2016.


A Question about a Question related to Graph Theory and Maximum Flow

It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow.  Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird.  Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow).  Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.


Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

you're focused on images so will construct a scenario that fits your question in the affirmative. imagine certain images that are not compressed via lossy compression eg a non jpeg-like algorithm. imagine the images are not compressed and stored in a straight pixel format. next suppose there are images that are composed of sub images in a vertical fashion. eg imagine a stack of images composing a larger image:

A
B
C
D

in the above crude diagram A,B,C,D are stacked images that compose a larger image, say E. now suppose that one creates a file that is concatenating files/images A,B,C,D,E. on a standard "lossless" dictionary compression algorithm like lempel-ziv, the algorithm will be smart enough to use A,B,C,D as long dictionary strings, and compose E out of those strings. (this depends on specifics like maximal dictionary word size etc, but it could be made to work). so in this admittedly rather contrived scenario, the answer is YES.

however, you are missing something about JPEG, it is typically lossy compression, and also images are generally a 2d format, whereas a lot of compression algorithms take advantage of 1d patterns like long strings. so this lossiness combined with the 2d format will mean that general compression algorithms will not really save much over the cost to store the original images (which generally are already compressed anyway).

therefore this is generally a negative answer overall, the overall idea of "compressing" using a "dictionary of images" is not really valid/possible/plausible and you can get a better idea of why by studying the mechanics/dynamics of compression algorithms in a more detailed way. on the other hand there are a wide variety of image compression algorithms that do in fact take advantage of redundancies in images. in JPEG for example the image is broken into squares and it can reuse common squares!


Simple approach: for each $1 \le i \le N$ (I assume that the $<$ in the question are typos) run depth-first or breadth-first search ignoring nodes coloured $i$.

Slightly more advanced approach: use a matrix-based all-pairs reachability algorithm, but rather than record a Boolean isReachable or a numeric shortestDistance record a bitmap of which colours can be avoided.


Perceptron learning rule past exam question

Firstly let me say that I am not going to solve this for you. What I would do instead is help you figure out how to solve it all by yourself.

How many inputs will your perceptron have if your input vector is in n-D?
Conceptually, what does the output from a perceptron represent?
Following from the second point, what does updating the weights do to the output from your perceptron?
Ideally, what should the updating of the weights do to the output?
When do you need to update the weights?

Think about this by plotting the inputs and output from the perceptron on a graph.

These are some of the basic concepts you need to understand to get the basics of Artificial Neural Networks (ANNs).

Good Luck


proving {$a^ib^jc^k : j = i \lor j = k$} is not regular

If you intersect your language with $a^+ b^+$ then you get $\{ a^n b^n : n \ge 1 \}$, whose irregularity you probably know how to prove.


Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $\sum_{w\in N(v)} f'(v,w) \leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.


Upper bound derivation of expected time for finding a large cut

We can upper bound the first summand by
$$
\sum_{i \leq m/2-1} i \Pr(X=i) \leq
\sum_{i \leq m/2-1} (m/2-1) Pr(X=i) =
(m/2-1) \sum_{i \leq m/2-1} Pr(X=i) =
(m/2-1) Pr(X \leq m/2-1) = (1-Pr(X \geq m/2))(m/2-1) = (1-p)(m/2-1).
$$
Similarly, we can upper bound the second summand by
$$
\sum_{i \geq m/2} i \Pr(X=i) \leq
\sum_{i \geq m/2} m Pr(X=i) =
m \sum_{i \geq m/2} Pr(X=i) =
m Pr(X \geq m/2) = pm.
$$


A Problem on Time Complexity of Algorithms

For $k = \left\lceil \dfrac{r}{2} \right\rceil$, it is conjectured (and proven in some simpler models of computation by JeffE) that $r$-SUM problem has lower bounds $\Omega(n^k)$, the solution for which can be verified in $O(n)$ time.

Pick an $r$ such that $k \gt t$, implying $\omega(n^t)$ bounds.


Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$.

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\{0,1,2\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that
$N = 20\cdot 100^{28} + \sum\limits_{0\leq i< 28}30\cdot 100^i + 9
= 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem.
Here, we also use that $29$ does not divide $100-1$.

I hope from this you are able to solve the exercise.


An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

Your statement is meaningless, since $O(n^2)$ and $O(n\log n)$ are just upper bounds on the time complexity. If you know that $A \leq 100$ and $B \leq 10$, you have absolutely no idea which is larger, $A$ or $B$.
Let us correct your statement to

If $n<100$ then $\Theta(n^2)$ is more efficient, but if $n \geq 100$ then $\Theta(n\log n)$ is more efficient.

This statement still has no truth value, since we don't know which functions are represented by $\Theta(n^2)$ and by $\Theta(n\log n)$. What we do know is that for large enough $n$, the $\Theta(n\log n)$ algorithm would be more efficient.
Suppose you instantiate your statement with specific functions $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n\log n)$. There is no reason to expect that there is a single crossover point. For example, take the following functions:
$$
f(n) =
\begin{cases}
100 & \text{if } n < 20, \\
n^2 & \text{if } n \ge 20
\end{cases} \\
g(n) =
\begin{cases}
50 & \text{if } n < 10, \\
200 & \text{if } 10 \le n < 20, \\
10^{300} n\log n & \text{if } n \ge 20
\end{cases}
$$
As you can see, $g(n)$ is faster for $n < 10$, and then for (astronomically) large enough $n$.
While such definitions are artificial, in practice we could have (say) $f(n) = 3n^2 + n\log n + 9n + 17$ and $g(n) = 10n\log n + 4\sqrt{n} + 50$, which might have several crossover points (I haven't checked).
Finally, even if there is a single crossover point, there is no reason to expect it to be exactly $n = 100$. The exact crossover point(s) depend on the functions $f(n),g(n)$. The only way to determine it is by running the two algorithms and comparing the running times.


What problem is to the set packing problem, as the hitting set problem to the set cover problem?

Let $E$ be indicator matrix $e_{ij}=[u_j\in S_i]$ and $w\geq 0$ be boolean vector. What you have written is $Ew\leq 1$ where $(1,w)$ is being maximized. If we relax this to linear programming and get respective dual $E^tv\geq 1,\, v\geq 0$ where $(1,v)$ is minimized. Latter problem under constraints $u\in\{0,1\}^m$ would be Set Cover problem. To get respective Hitting Set consider new sets $S'_j=\{S_i:u_j\in S_i,\,i=1,\ldots,m\}$ and new ground set $U'=\{S_i:i=1,\ldots,m\}.$ The Set Cover reduces to Hitting Set for sets $\{S'_j\}$ over ground set $U'.$ So Set Packing and Set Cover are dual in some way. But  their optimal values do not coincide but they do coincide for their convex relaxations. More on this topic see e.g. in Wlliamson

You could also consider $H$ as being maximum independent families of sets $S_i.$ Let $F_h=\bigcup\limits_{h\in S_i}S_i,\,h\in H.$ These families are non-intersecting. Set Packing optimum is the lower bound for Set Cover.

As for $H$ interpretation. I suppose $S_i$ represents class of some useful things to take. Overall utility is maximized while the only one thing can be taken from each class.


What will be the Turing machine to show that the function $T(n) = n$ is time constructible?

You almost certainly have the right machine: just implement a binary counter and increment it once for each character of the input.

What you need is a more sophisticated analysis of the running time. You've presumably reasoned that the counter will end up with $\log n$ bits, you need to increment it $n$ times and each increment could change all the bits, so there are $O(n\log n)$ operations.  This is completely correct but you can do better.

Suppose the current value of the counter is even. How many bits do you have to change to increment the counter? How often do you need to change more than two bits? How often do you have to change all $\log n$ bits to increment the counter?


Binary, rooted trees

Let's focus first on the case of binary, rooted trees
(i.e., every vertex has either 0 or 2 children).
This case can be solved in polynomial time using
dynamic programming, with subproblems as defined below.

Let me first define some notation that will be helpful.
$\newcommand{\dist}{\text{dist}} \newcommand{\dom}{\text{dom}} \newcommand{\gap}{\text{gap}} \newcommand{Ni}{\mathbb{N}_{-\infty}}$
Let $T_v$ denote the set of descendants of $v$, including $v$ itself, i.e., the vertices in the subtree rooted at $v$.  If $S$ is a set of vertices, let $\dist(v,S)= \min \{\dist(v,s) : s \in S\}$.  Define $\dom(S) = \{v\in V : \exists s \in S . \dist(s,v) \le K\}$; this is the set of vertices dominated by $S$.
Finally, let $\gap_v(S) = \max \{\dist(v,w) : w \in T_v \setminus \dom(S)\}$, i.e., the gap of $S$
(with respect to $v$) is the depth of the deepest descendant of $v$ that is not
dominated by some node of $S$.
Also, define the depth of $S$ (with respect to $v$) to be $\dist(v,S)$.
Define $\Ni = \mathbb{N} \cup \{-\infty\} = \{-\infty,0,1,2,3,\dots\}$.

The intuition is that we can build up an optimal dominating set
recursively, bottom-up.
Let $v_0$ and $v_1$ be the two children of the root, and suppose we have
a set $S_0 \subseteq T_{v_0}$ for the left subtree and $S_1 \subseteq T_{v_1}$
for the right subtree.
Can we combine $S_0,S_1$ somehow to get a dominating set for the whole tree?
To determine the answer to this question, all we need to know about
$S_0,S_1$ are their depth and gap (with respect to the root).
Therefore, all that matters when searching for a minimum dominating set
is their depth, gap, and size.
We don't need to enumerate all possibilities for $S_0,S_1$; for each
possible combination of depth and gap, we just need to know the minimum
attainable size for a set with that depth and gap.
This enables us to use dynamic programming effectively.

In particular, we will use the following definition of a subproblem:

  INPUT: a vertex $v \in V$, a depth $d \in \Ni$, a gap $g \in \Ni$
  OUTPUT: $n(v,d,g)$, defined to be the size of the smallest set $S \subseteq T_v$ of depth $d$ and gap $g$, i.e., the size of the smallest set $S \subseteq T_v$ such that $\dist(v,S)=d$ and $\gap_v(S)=g$

You can use dynamic programming to solve these subproblems,
traversing the tree in a bottom-up fashion.
If $v$ is a leaf, $n(v,d,g)$ is easy to compute.
Next suppose that $v$ is an internal node, with children $w,x$.
Then we can compute $n(v,d,g)$ from $n(w,\cdot,\cdot)$ and $n(x,\cdot,\cdot)$
as follows.
If $d>0$ and $g\ge 0$, we use the recurrences:

$$n(v,0,-\infty) = \min \{1 + n(w,d',g') + n(x,d'',g'')\}$$

$$n(v,d,-\infty) = \min \{n(w,d-1,-\infty) + n(x,d'',g''), \\
n(w,d'',g'') + n(x,d-1,-\infty) : d'' \ge d-1, d+g''+1 \le K\}.$$

$$n(v,d,g) = \min \{n(w,d',g') + n(x,d'',g'') :
\min(d',d'')=d-1, \max(g',g'')=g+1\}.$$

We have some easy base cases when $d\le 0$ or $g=-\infty$:
$n(v,-\infty,g) = 0$ if $g = \max\{\dist(v,w) : w \in T_v\}$,
or $\infty$ otherwise;
$n(v,0,g) = \infty$ if $g \ge 0$.

In the exposition above, $d,g$ are implicitly subject to the constraints that
$d \in \{-\infty,0,1,\dots,2K\}$, $g \in \{-\infty,0,1,\dots,K-1\}$,
$d \ge 0 \land g \ge 0 \implies d+g > K$, $g \ge 0 \implies d \le g+K+1$,
$g=-\infty \implies d \le K$ (since other combinations aren't possible).
$d',g'$ and $d'',g''$ are implicitly constrained in the same way.

Finally, the size of the smallest distance-$K$ dominating set for the entire tree is given by
$\max \{n(r,d,-\infty)\}$ where $r$ is the root of the tree.

Running time analysis:
There are $O(|V| \cdot K^2)$ subproblems.
Each recurrence can be computed in $O(K^2)$ time, by organizing the
$\min$ computation suitably.
Therefore, the total running time is $O(|V| \cdot K^4)$.

Unrooted trees

It is easy to deal with unrooted trees:
simply pick an arbitrary vertex to be the root, and now a depth-first
search will turn it into a rooted tree.
Then you can apply the above algorithm.

Trees of arbitrary branching factor

The above algorithm can be easily generalized to trees whose
branching factor at each vertex is $\le 2$ (i.e., each vertex has
either 0, 1, or 2 children).

I haven't thought through what happens if the tree might have
arbitrary branching factor (i.e., not restricted to $\le 2$).
I expect that similar recurrences and subproblems will be applicable.
If you organize the $\min$ computations cleverly, you might be able
to achieve a low-order-polynomial running time,
e.g., $O(|V| \cdot K^c)$ for some small constant $c$ (e.g., $c=4$).
However, I haven't worked through the details; I'll leave that to you.


Minor Mistake in Computability, Complexity, and Languages?

There's no contradiction, here.  The first case defines the partial function $g\colon \mathbb{N}\to\mathbb{N}$ given by
$$g(n) = \begin{cases}
 x &\text{if $x\in\mathbb{N}$ and }x^2=n\\
 \text{undefined} &\text{if no such $x$ exists.}
\end{cases}$$
As the text says, "the domain of $g$ is the  set of perfect squares."

The second case defines the total function $h\colon\mathbb{N}\to\mathbb{R}$ given by
$$h(n) = x \quad \text{if }x\in\mathbb{R}_{\geq 0} \text{ and } x^2=n\,.$$
The domain of $h$ is the set of all the natural numbers.

You say that these are the same function, but they are not. $g(2)$ is undefined but $h(2)$ is defined (and equal to $\sqrt{2}$). $h$ associates a square root with every natural number but $g$ only associates square roots with natural numbers that are perfect squares.

$\mathbb{N}$ is closed under $g$ because, whenever $g$ is defined, $g(n)\in\mathbb{N}$. $\mathbb{N}$ is not closed under $h$ because, for example, $2\in\mathbb{N}$ but $h(2)\notin\mathbb{N}$.


Recursive definitions over an inductive type with nested components

What works

If you nest the definition of the fixpoint on lists inside the definition of the fixpoint on trees, the result is well-typed. This is a general principle when you have nested recursion in an inductive type, i.e. when the recursion goes through a constructor like list.

Fixpoint size (t : LTree) : nat :=
  let size_l := (fix size_l (l : list LTree) : nat :=
                  match l with
                    | nil => 0
                    | h::r => size h + size_l r
                  end) in
  match t with Node l =>
    1 + size_l l
  end.

Or if you prefer to write this more tersely:

Fixpoint size (t : LTree) : nat :=
  match t with Node l =>
    1 + (fix size_l (l : list LTree) : nat :=
          match l with
            | nil => 0
            | h::r => size h + size_l r
          end) l
  end.

(I have no idea who I heard it from first; this was certainly discovered independently many times.)

A general recursion predicate

More generally, you can define the “proper” induction principle on LTree manually. The automatically generated induction principle LTree_rect omits the hypothesis on the list, because the induction principle generator only understand non-nested strictly positive occurences of the inductive type.

LTree_rect =
fun (P : LTree -> Type) (f : forall l : list LTree, P (Node l)) (l : LTree) =>
match l as l0 return (P l0) with
| Node x => f x
end
     : forall P : LTree -> Type,
       (forall l : list LTree, P (Node l)) -> forall l : LTree, P l

Let's add the induction hypothesis on lists. To fulfill it in the recursive call, we call the list induction principle and pass it the tree induction principle on the smaller tree inside the list.

Fixpoint LTree_rect_nest (P : LTree -> Type) (Q : list LTree -> Type)
                         (f : forall l, Q l -> P (Node l))
                         (g : Q nil) (h : forall t l, P t -> Q l -> Q (cons t l))
                         (t : LTree) :=
  match t as t0 return (P t0) with
    | Node l => f l (list_rect Q g (fun u r => h u r (LTree_rect_nest P Q f g h u)) l)
  end.

Why

The answer to why lies in the precise rules for accepting recursive functions. These rules are perforce subtle, because there is a delicate balance between allowing complex cases (such as this one, with nested recursion in the datatype) and unsoundness. The Coq reference manual introduces the language (the calculus of inductive constructions, which is the proof language of Coq), mostly with formally precise definitions, but if you want the exact rules regarding induction and coinduction you'll need go to the research papers, on this topic Eduardo Giménez's [1].

Starting with the Coq manual, in the notation of the Fix rule, we have the fixpoint definition of $\mathsf{Fix} f_i \, \{ f_1 : A_1 := t_1 \; ; \;\; f_2 : A_2 := t_2 \}$ where:

$$\begin{align*}
  \Gamma_1 &= (x : \mathtt{LTree}) &
  A_1 &= \mathrm{nat} &
  t_1 &= \mathsf{case}(x, \mathtt{LTree}, \lambda y. g_1 (f_2 y)) \\
  \Gamma_2 &= (l : \mathtt{list}\;\mathtt{LTree}) &
  A_2 &= \mathrm{nat} &
  t_2 &= \mathsf{case}(l, \mathtt{list \: LTree}, \lambda h \: r. g_2 (f_1 h) (f_2 r)) \\
\end{align*}$$

In order for the fixpoint definition to be accepted, “if $f_j$ occurs [in $t_i$] then … the argument should be syntactically recognized as structurally smaller than [the argument passed to $f_i$]” (simplifying because the functions have a single argument). Here, we need to check that

$i=1$, $j=2$: l must be structurally smaller than t in size, ok.
$i=2$, $j=1$: h must be structurally smaller than l in size_l, looks ok but isn't!
$i=2$, $j=2$: r must be structurally smaller than l in size_l, ok.

The reason why h is not structurally smaller than l according to the Coq interpreter is not clear to me. As far as I understand from discussions on the Coq-club list [1] [2], this is a restriction in the interpreter, which could in principle be lifted, but very carefully to avoid introducing an inconsistency.

References

Cocorico, the nonterminating Coq wiki: Mutual Induction

Coq-Club mailing list:

[1] Thread “Meta theory: induction over terms with abstract variables”; first message by Robbert Krebbers on 2009-10-21; explanation by Adam Chlipala; counterexample by Bruno Barras; reply by Hugo Herbelin.
[2] Thread “Termination checking with nested recursion”; first message by Gert Smolka; reply by Hugo Herbelin.

The Coq Development Team. The Coq Proof Assistant: Reference Manual. Version 8.3 (2010). [web] ch. 4.

Eduardo Giménez. Codifying guarded definitions with recursive schemes. In Types'94: Types for Proofs and Programs, LNCS 996. Springer-Verlag, 1994. doi:10.1007/3-540-60579-7_3 [Springer]

Eduardo Giménez. Structural Recursive Definitions in Type Theory. In ICALP'98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 1998. [PDF]


prove correctness of in-order tree traversal subroutine

In your proof the largest element of binary search tree $T$ can in fact be the root of the tree. I did not check whether you took care of that.
If you want to use induction by a number of elements in the tree, I would advise you to take strong induction, that is the hypothesis assumes the algorithm works for any number less or equal to $n$. Then the hypothesis can be applied to both subtrees which must have less elements than the full tree.
Finaly you could use structural induction, that is induction using the inductive definition of the structures you consider. Here that is the notion of a binary tree: which is either empty, or a root and two subtrees. In practise this gives the same proof as strong induction, but you did not need to quantify the number of nodes.


Algorithm for checking unambiguity in the derivation of a string

gnasher's comment more or less answers this. A sketch of an algorithm would be:

enumerate all derivations of the grammar that do not generate strings longer than $s$. This can be done, because CFGs do not have deleting rules (or if yours do, they can be converted for example to Chomsky Normal Form)
check how many of the strings generated are equal to $s$.

This takes a long time, of course. But I doubt that there is a fundamentally better way.


Doubt regarding cache hit ratios and access time

I think, that the part with some other useless information... in your problem specification must contain some information on solving your problem. As I was trying to calculate the numbers that you got I found some errors, and I thought there must be some more input. Let me first explain:

Your formulas are incorrect for both Method 1 and Method 2. When accessing some memory level you ALWAYS access this level, not with probability! Explanation goes something like this: You ACCESS $L1$, if you MISS (some probability), you go to $L2$. On $L2$ you again make an ACCESS, and if you MISS (with some probability), you move to $L3)...

So Method 1 with your first problem would be:
$$[T1]+0.1([2*T1]+0.1*[3*T1])=1.23[T1]$$

And Method 2 for first problem: $$[T1]+0.1([T1+2*T1]+0.1[T1+2∗T1+3∗T1])=1.36[T1]$$

So now looking at your second problem, you can solve it by using Method 1:

New Method 1

Effective access time = 20 + 0.2*(120) = 44ns
Increase by 40ns, so new time = 84ns
84 = 20 + (1-h)*120
Hit ratio = 0.467

Note that here I assumed you made a mistake with answer $(C)$ in your problem description (it is not $0.4467$, but it is $0.467$).

Now if you would have miss penalties defined in your problem statement, then you would use Method 2. Miss penalty just says, that if you do not get a result in your current level, then you have to copy it from the upper level. Now let us assume, that miss penalty on second level is 300ns (that means copying the contents to level 1 and accessing it). Everything else stays the same. The calculations would go:

New Method 2

Effective access time = 20 + 0.2*(120+0.2*300) = 56ns
Increase by 40ns, so new time = 96ns
96 = 20 + (1-h)*(120+(1-h)*300)
Hit ratio = 0.65840

One other caution... You need to use the same formula for calculating the average access time if you chose one method. (In your Method 2 you calculated access time by Method 2 and then calculated the new hit ratio with Method 1)

So how do you know which method to choose? From the problem description! If you have miss penalty given, then you take the second approach. If you do not have miss penalty, then you use the first approach.


In general $U$ will only be unitary if your composed matrix is hermitian.
I will answer the more general problem that the matrix is partially diagonalizable:
$$U^{-1} \begin{pmatrix}A & B \\ C & D\end{pmatrix} U = \begin{pmatrix}A' & 0 \\ 0 & D'\end{pmatrix}.$$
The diagonal matrix $A'$ contains the eigenvalues on its diagonal. You must already know them and their corresponding left and right eigenvectors. Now let $U_\text{eig}$ consist of the right eigenvectors and $V_\text{eig}$ consist of the left eigenvectors as columns. Then choose
$$U=(U_\text{eig}|V_\text{eig}^\perp)$$
where $\perp$ denotes an orthogonal complement (a basis of the null space).

Proof: Say, you have a matrix $U$ represented by $(U_\text{eig}|U_\text{rem})$ that partially diagonalizes your matrix. Then split its inverse like so: $V = (V_\text{eig}|V_\text{rem})$ with $U^{-1} = V^T$. We know that $V_\text{eig}$ contains left eigenvectors as columns.
It holds
$$I = U^{-1}·U = V^T·U
     = (V_\text{eig}|V_\text{rem})^T · (U_\text{eig}|U_\text{rem}).$$
Separated:
$$
\begin{array}{cc}
I = V_\text{eig}^T · U_\text{eig} & 0 = V_\text{eig}^T · U_\text{rem} \\
0 = V_\text{rem}^T · U_\text{eig} & I = V_\text{rem}^T · U_\text{rem}
\end{array}
$$
The equation $0 = V_\text{eig}^T · U_\text{rem}$ means that $U_\text{rem}$ is an orthogonal complement to $V_\text{eig}^T$.
You may not know the precise content of $V_\text{eig}$,
but orthogonality to $U_\text{rem}$ is invariant under change of the basis or re-ordering of columns.
Thus for your computation you can choose any left eigenbasis for your selected eigenvalues.


Regularity of “middles” of words from regular language

Let $R$ be a regular language. Then there is a finite automaton $M$ for which the language, $L(M)$, of $M$ is $R$. Without loss of generality, we may assume that $M$ has no unreachable states. Construct a new FA, $M'$, as follows:

For each state $q$ of $M$ which has a sequence of transitions to a final state of $M$, make $q$ a final state. Call the set of such states $S$.
Add a new start state $q_0$ having $\epsilon$-transitions to each element of $S$.

It's not hard to see that $M'$ will accept any string which is a substring of some string in $R$.


You miss the meaning of the Time Hierarchy theorem, or perhaps of the classes TIME($n^k$) that you show.

It is indeed obvious that $O(n^k) \subsetneq O(n^{k+1})$, for instance. It is also clear that the set of Turing machines that run in time $O(n^k)$ is a strict subset of those that run in $O(n^{k+1})$.

However, it is not immediately obvious that the set of problems that can be solved by TMs in time $O(n^k)$ (i.e., the class TIME($n^k$)) is a strict subset of TIME($n^{k+1})$. For this much stronger statement, you need the Time Hierarchy Theorem. That is, you need to argue that there exists some problem that can be solved in time $n^{k+1}$ but not in time $n^k$. (Of course, this is just a special case of applying the theorem to polynomial running times.)


Algorithm SAGE- PARI? for splitting polynomials over field extension

I though the answer was easier than what I found, so no real chance to do this "by hand". The article from Factoring Polynomials  describes a process over $\mathbb{Q}$ called the Zassenhauss method:  first factor modulo $p$ (say Berlekamp algorithm, rather accessible), then Hensel lift back and check bounds on coefficients and other tests. The Klueners article describes the "van Hoeij" algorithm which I admit is above my math understanding capabilities.

It also describes the "Trager method" over a field extension. Find a primitive element, compute it's minimal polynomial over $\mathbb{Q}$, factor it with say the previous method, so the extension is the field modulo the maximal ideal generated by the minimal polynomial, and apply chinese remainder to decompose the given polynomial.


difference between deadlock avoidance and detection

Simply to put
Deadlock avoidance: you employ some methods to avoid the deadlock ,but prevention is more restrictive than avoidance.

Deadlock detection: Here only the detection only takes place whether the current state is in deadlock or not.


If you want to state that $O(f(n))$ is the best bound on the complexity that you can get, then you can use big Theta instead: $\Theta(f(n))$ stands for a function – in this case worst-case time complexity – that is asymptotically equal to $f(n)$ up to constants. That is, if the worst-case time complexity $T(n)$ satisfies $cf(n) \leq T(n) \leq Cf(n)$ for some $0<c\leq C$, then you can state that the (worst-case) time complexity of the algorithm is $\Theta(f(n))$. This implies both the upper bound $O(f(n))$ and the matching lower bound $\Omega(f(n))$, showing that the upper bound is best possible.


Does the transitivity of big-O notation hold for asymptotically nonnegative functions?

Suppose $f(n)$, $g(n)$ and $h(n)$ are asymptotically non-negative functions such that $f(n) = O(g(n))$ and $g(n) = O(h(n))$.

Then, by definition, there exist positive constants $c_1, c_2, m_1, m_2$ such that

$$
0 \le f(n) \le c_1 g(n)
$$

whenever $n \ge m_1$ and

$$
0 \le g(n) \le c_2 h(n)
$$

whenever $n \ge m_2$.

Choose $c = c_1 c_2$ and $n_0 = \max\{m_1, m_2\}$.
Note that both $c$ and $n_0$ are positive.
Then, whenever $n \ge n_0$, we have

$$
0 \le f(n) \le c_1 g(n) \le c_1 c_2 h(n) = c h(n)
$$

which implies that $f(n) = O(h(n))$.


I'm not sure I get all your questions. I'll try to answer according to my interpretation of what you are asking, and you can clarify if I got you wrong.

  Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

First, there is no second qubit, but a second system (of $n$ qubits). Next, consider $\psi_a$, and recall that for any $f(x_j)$ there are only two preimages $j$ and $j\oplus s$, then if you measure $f(x_j)$ at the second system, the first system must either be $j$ or $j\oplus s$.

  Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

Kind of. However, you don't measure $\vert\psi_a\rangle$ directly. There is another hadamard gate which is missing there. I.e., you measure
$$(H\otimes I) \left\vert\psi_a\right\rangle = \frac1{2^n}\sum_x\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle$$

Now if you re-arrange it properly, it should give
\begin{align*}
\frac1{2^n}\sum_{x\in\{0,1\}^n}\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle &=
\frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left\vert i\right\rangle\left\vert f(j)\right\rangle + (-1)^{i\cdot (j\oplus s)}\left\vert f(j\oplus s)\right\rangle \\
&=
 \frac1{2^n}\sum_{j\in XS}\sum_i \left ((-1)^{i\cdot j}+(-1)^{i\cdot j}(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \\
&=
 \frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left(1+(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle
\end{align*}
Where $XS\subseteq \{0,1\}^n$ is the largest subset such that if $j\in XS$ then $\forall j'\in XS, f(j)\ne f(j')$; so that the sum over $j$ is only over half the space and  we don't count twice $x=j$ and $x=j\oplus s$. But note that $f(j)=f(j\oplus s)$ which we use in the second transition.

The above shows that for any $i$ for which $s\cdot i=1 \mod 2$ there is a destructive interference that cancels these terms, and you are left with only $i$'s for which $s\cdot i=0 \mod 2$. Thus, any $i$ you will measure (at the first system) must satisfy $s\cdot i=0 \mod 2$.


I'd assume that a TM does not accept any input if for every input $w$ it either loops or halts and rejects.
The general approach to show some language is undecidable goes as follows:

Assume that there exists a machine $M$ that recognizes the language you are given
Take some language that you know is undecidable
Create a machine $N$ that using $M$ solves the undecidable language
Since the language is undecidable, you have reached a contradiction

Do you see how being able to answer the question "is it true that machine $T$ doesn't accept any input?" would help you answering the question "does machine $T'$ accept $\epsilon$?"?
Hint: Sometimes it is useful to create a machine that ignores its input!
About semi-decidability: There's a theorem that says that a language is decidable if and only if it is semi-decidable and its complement is semi-decidable. Once you prove that your language is undecidable you can easily check that its component is semi-decidable, which immediately gives you that the language itself cannot be semi-decidable.
Regarding Rice's Theorem: Generally I'd say it is a very useful theorem, but I would recommend to solve some undecidability exercises using just pure contradictory reasoning, since it allows you to understand the concept of reducing one problem to another better, in my opinion :)


The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as there are any chocolates left, fill a box with one of each of the chocolates. That solution is linear in the number of chocolate pieces but unfortunately not linear in the problem size. So instead of doing the greedy algorithm, we simulate how it would run and calculate how many boxes would be filled, in polynomial time.

Let $x_i$ be the number of pieces of type $a_i$. Sort in descending order, then remove the chocolates where $x_i$ = 0. If n ≤ k you need $x_1$ boxes.

As long as $x_k$ > $x_{k+1}$ you would put chocolates $a_1$ to $a_k$ into a box. This fills $x_k - x_{k+1}$ boxes, and you decrease $x_1$ to $x_k$ by $x_k - x_{k+1}$. You simulate this in constant time.

After that you have $x_1$ to $x_j$ greater than $x_k$, and $x_{j+1}$ to $x_m$ equal to $x_k$, for some j < k and m > k. So you have a larger number of j chocolates, and an equal number of m-j chocolates, m > k. You would fill m-j boxes by putting m-j of the chocolates $a_1$ to $a_j$ into each box, and filling with k-j of the chocolates $a_{j+1}$ to $a_m$.

You would do that t times. t is limited: With each round of m-j boxes, the number of the top j chocolates is reduced by m-j, the next chocolates are reduced by k-j. The difference is reduced by t (m-k), so t ≤ $(x_j - x_{j+1}) / (m-k)$. The next chocolates are reduced by t (k-j), so t ≤ $(x_m - x_{m+1}) / (k-j)$, letting $x_{m+1} = 0$ if m = n. You take the largest possible t and simulate t (m-j) steps in constant time.

When this is done (and t may be 0) we remove all chocolates with a zero count, and we may be done. If not, then we do one simulation step which will change the situation, and start all over.

That's the idea. You can probably clean this up a bit.


Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

The greedy algorithm is optimal.

The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.

Given an $n$-digit number $A=a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is a digit, let $a_t$ be the rightmost digit of $A$ such that $a_n, a_{n-1}, \cdots, a_t$ is non-decreasing. Let $r$ be the number of all digits that are equal to $a_t$ from $a_t$ to its left. In other words, the digits of $A$ are classified as displayed in the following illustration for some integer $t$ and $r$, where $ a_t>a_{t-1}$ and $a_{t+r}<a_{t+r-1}=\cdots=a_{t+1}=a_t$. Note that if there is only one digit in $A$, it is $a_t$ with $t=0$ and $n=r=1$.
$$\begin{aligned}
A&=\overbrace{a_{n-1}a_{n-2}\cdots a_{t+r}\ \underbrace{a_{t+r-1}\cdots a_{t+1}a_t}_{r\text{ copies of }a_t}}^{\text{longest non-decreasing}}\ a_{t-1}\cdots a_0\\
\mu(A)&=a_{n-1}a_{n-2}\cdots a_{t+r}\{r\text{$-$}1\text{ copies of }a_t\}a_{t-1}\cdots a_0\\
\end{aligned}$$

Define integer $\mu(A)$ as shown above, which is $A$ but with one of $a_{t+r-1},\cdots,a_{t+1}, a_t$ removed. For example, $\mu(1214532)=114532$, $\mu(112)=11$, $\mu(40012)=0012$ and $\mu(0012)=001$. Note that the value of $\mu(A)$ does not depend on the number of leading $0$'s in $A$. For example, $\mu(001332)=00132$${}=\mu(1332)=132$.

Lemma. $\mu(A)$ is the smallest number that is $A$ with one digit removed.
Proof. Easy.

Let $G$ be the greedy algorithm. The lemma above says $G(A,k)=\mu^k(A)$.

Claim. For all non-negative integer pairs $(A,k)$, $G$ is optimal, i.e., $G$ returns the smallest number.
Proof. Let $P(k)$ be the proposition that $G(I,k)$ will return the smallest number for all integer $I$ of more than $k$ digits. The claim is $P(0)$, $P(1)$, $P(2)$, $\cdots$ are true.

Use induction on $k$. The base case, when $k=0$, is trivially true.

Assume $P(k)$, the induction hypothesis, is true. Let $A$ be an integer and $S$ be some $k+1$ digits of $A$ such that $B$, which is $A$ with digits in $S$ removed, is as small as possible. We will prove $G(A,k+1)\le B$, i.e, $P(k+1)$ is true, thus completing the induction.

Let us reuse the classification above of the digits of $A$, i.e., they start with the non-decreasing sequence $a_{n-1}, a_{n-2}, \cdots, a_{t}$ with $a_{t}>a_{t-1}$ and $ a_{t+r}<a_{t+r-1}$.

$S$ does not contain any digit in that sequence.

This cannot happen, since we can get a number smaller than $B$ by removing $a_{t}$ and arbitrary $k-1$ digits to the right of $a_{t-1}$.
$S$ does contain one of the digits in that sequence, say, $a_\ell$.

$S$ does not contain any one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.

We can modify $S$ by substituting $a_t$ for $a_\ell$. The removal of the digits in the modified $S$ will return a number smaller than $B$. So this case cannot happen, either.
Otherwise, WLOG, let $a_\ell$ be one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.

The lemma above tells us that $A$ with $a_\ell$ removed is $\mu(A)$. Let $S_-$ be $S$ without $a_\ell$. So $S_-$ are some $k$ digits of $\mu(A)$. We have the following diagram, where the arrow reads "become". $\require{AMScd}$
\begin{CD}
    \mu(A),k@>\text{greedy algorithm}>> G(\mu(A), k)\\
    @| \\
    \mu(A),k@>{\text {remove elements in }S_-}>> B\\
  \end{CD}

The induction hypothesis ensures $G(\mu(A), k)\le B$. Since $G(A,k+1)=G(\mu(A), k)$, we are done.

Exercise. (A couple of minutes or more) Given two positive integers $k\lt n$ and an $n$-digit integer $A>0$, how can you remove $k$ digits from $A$ such that the resulting integer is the biggest one? Explain the greedy algorithm. Prove it is correct.

The exercise shows that the greedy algorithm is still optimal in the original problem when $A$ is negative.


Is there a shell between the kernel and hardware

Given the details you have given us, you are of course right.  There is no shell between the hardware and the kernel; that's just silly.  Asking "but what if there were?" would be like asking "but what if pigs could fly?".

It is likely that either there was some misunderstanding or that the examiner is confused.  The former is much, much more likely.

One thing I might critique is your characterization of a shell as an interpreter.  While a shell is an interpreter, not every interpreter is a shell.  I suppose it is possible that the examiner was asking a follow-up question to see if you understand that.

As far as how a kernel runs programs.... read a standard operating system textbook.  The details are adequately covered in any standard OS textbook.

The thing is... I'm not sure why you're asking us. Why not ask your professor or examiner?  We can't tell you what was in your examiner's head.


Given price and number of pages of each book, What is the maximum number of pages you can buy?

I am afraid that the following recurrence equation as in the question is incorrect.

f(x, 0) = max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) )

Let g(i,j) be the maximum number of pages possible when you have i units of money to spare and books 0..j available to select, where 0..j means 0, 1, ..., and j. (I use g instead of f since I am not absolutely sure of the definition of f in the question. It looks like g(i,j) should be the same as f(i,j) in the question. )

Here is the recurrence equation.

g(x, indx+1) = ( x >= price[indx+1] ) ?
              max( g(x - price[indx+1], indx) + pages[indx+1], g(x,indx) ) :
              g(x, indx)

In plain words, there are (at most) two possibilities when books 0..(indx+1) are available to select.

Book indx+1 is selected (when x >= price[indx+1]). You have pages[indx+1] more pages.

Then you are left with x - price[indx+1] units of money and books 0..indx to select.
Otherwise.

Then you are left with x units of money and books 0..indx to select.

Note that the available books on the right-hand side of the equation are always less than the available books on the left-hand side. That reduction of a larger problem to a smaller problem signifies the power of recursion.

The base case are when no books are available, i.e., g(i,0) = 0 for all i, and when there is no money to spare, i.e., g(0, j) = 0 for all j.


Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

This language is obviously decideable, just emulate $M$ on $w$ and see whether it halted within $n$ steps or not...

Now, to whether $nHALT\in P$ or $nHALT\notin P$. The length of $n$ here is logarithmic to its "value" (assuming that $\Sigma$ here is not unary). Thus, the number of steps we will need to emulate would be exponential in its size! I dont see a polynomial time algorithm for that, so I assume it's probably not in P. But I have not proven that (just gave intuition on why it could be the case), and there is also a chance that showing that is equivalent to some open problem (maybe somehow you could prove its $\mathcal {NP-Complete}$?)


If $F\in 3SAT$ it means that there is some assignment that satisfies $n$ clauses. It doesn't mean that every assignment satisfies all clauses. This makes the reduction wrong, since there might be an assignment for $F\in 3SAT$ that satisfies fewer than $n$ clauses. The reduction you've proposed would be valid if you started with $Tautology$, but then, that problem isn't known to be $NP$-complete.

Your problem is $coNP$-complete (as the reduction from $Tautology$ shows), so finding a reduction from $3SAT$ would prove $NP\subseteq coNP$.


Prove consistency of maximum of two consistent heuristic functions?


Irregularity of language of words whose length is of power of 2

The strategy for proving a language non-regular is a proof by contradiction:

We assume that $L$ is regular. This then means that there exists a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3. But now it is enough to find some $w$ where $|w| \geq p$ such that no partition can satisfy all three conditions simultaneously.

In the concrete case, you have not told us what alphabet $\Sigma$ we are considering. I assume that $\Sigma = \{ a,b\}$, but this is not important.

So we assume that $L$ is regular, and therefore there must exist a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3.

But now consider $w = a^{2^p}$. Clearly, $w \in L$. Moreover, we have that $|w| \geq p$, so there should be some partition of $w = xyz$ that satisfies conditions 1, 2 and 3.

If the partition must satisfy condition $3$ then the first two parts of the partition, that is, $xy$, must have total length less than $p$. Therefore, $|y| \leq p$. If the partition must also satisfy condition $2$, then $y$ cannot be the empty string, so $y = a^k$ for some $k$ where $0 < k < p$.

But can such a partition then also satisfy condition $1$? No. It is enough to find an $i \geq 0$ such that $xy^iz \notin L$ to see this. Take $xy^2z$. This string has length $2^p + k$, and since $k < p$, we know that $2^p + k$ cannot be a power of $2$. So $xy^2z \notin L$.

–

In other words: The appropriate strategy is to try to satisfy the conditions one by one. Usually, we first try to satisfy condition $3$. This will tell us where $y$ can appear (among the first $p$ symbols) and how long it can be. Given that, we then try to also satisfy condition $2$, and this usually just provides with the useful information that the string $y$ that can be repeated, is non-empty. Finally, we show that we can "pump our way out" of the language with this partition, thereby violating condition $1$.