Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem.

Basically, order the positions from 1 to 9.  You're going to fill in a two-dimensional table $T$, where $T[i,s]$ denotes the score of the highest-scoring team that fills in just the first $i$ positions and has a salary cap of $s$.  The key observation is: given the row $T[i-1,\cdot]$ of the table, you can compute $T[i,s]$ via a simple recurrence relation.  In particular,

$$T[i,s] = \max \{ T[i-1,s-s_j] + p_j : j=1,2,3,\dots\},$$

where $j$ ranges over the candidates for the $i$th position, $s_j$ is the salary of the $j$th candidate, and $p_j$ is the projected points generated by the $j$th candidate.   This lets you fill in the table, row by row.

The running time is quadratic: proportional to the total salary for the team, times the number of positions.  There are two nested loops, rather than 9.


First the term MMU refers to many different thing (more on later below). For now let's defined MMU as "virtual to physical address translation".

The caches L1 and L2 are always managed in hardware, however note that for proper operation the OS still has to interact with the cache on some occasions (notably when using DMA). An important point to be aware of is that depending on whether the caches are virtually or physically indexed, they have a different relationship with the MMU. Indeed a virtually indexed cache (typically L1) will usually be accessed by the CPU without going through the MMU and it will not only contain the data but also the security bits associated with the MMU (privilege bit, read/write, cacheability, etc). On the other hand, a physically indexed cache must come after the address translation and does not care about the MMU at all. This also applies to higher levels (L3 and L4) which are always physically tagged (and sometimes outside the CPU die).

Thus a typical CPU will have the core with a memory bus connected to the L1 (which is typically split between data and instruction, but this is not important here). On cache miss, the L1 will issue read/write on a bus that goes through the MMU then L2, L3, L4 and finally DRAM.

The MMU itself may consist of different things. The simplest forms of MMU are just segmentation and PMU (protection memory unit). More advanced forms of MMU include a TLB so as to support paging. The TLB itself is always a hardware component (essentially just another cache). However there are two very different ways of managing the TLB:

in hardware: the MMU has a "page table walker" that can issue read to the memory to load TLB entries on a miss (this includes x86, ARM, etc)
in software: the MMU triggers a CPU exception on a TLB miss, and then the OS does the page table walk in software, fills the TLB with the entry and return from the exception (this includes MIPS)


The Alias Method provides a means of sampling from a discrete distribution in $O(1)$ time, with $O(n)$ space and $O(n)$ pre-processing time.


Is there a name for this priority queue data structure?

This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that:

You have fast set and get at any index
You have fast "aggregate" queries on ranges
You can support fast update queries on ranges, for some combinations of updates and queries

The $j$th node at height $k$ in the tree "summarizes" a subarray $[j*2^k, (j+1)*2^k)$ of the original array. Since each element of the array appears in only logarithmically many such subarrays, we can do updates in $O(\log n)$ time.

The range queries can use any associative operation. In your example the operation is $\max$, but other examples include sum, product, even standard deviation (via sum and sum of squares).

I originally called this a Fenwick Tree (aka Binary Indexed Tree), which is a similar structure but which compresses the tree into only exactly $n$ storage with no overhead(but loses access to the original array).


How does CPU actually retrieve data from memory when you call a variable in a programming language?

Your assumption that the variable is sent to the CPU is wrong. Every program must be compiled to some machine code (or it will be interpreted, but it roughly comes down to the same thing). The idea of compilation is to translate the human-readable code to a series of bits, which can then be read by the processor. In order to get an idea of what those series of bits do, you could also take a look at assembly which is actually not much more than an encoding of the instruction set of a CPU.

Now the trick is that the compiler builds a so-called symbol table where it keeps track of all variables that have been defined by the programmer(s). Once it knows about all of the variables, it also knows how much RAM it needs (not considering dynamic allocation of course) and thus can allocate a certain space in memory. All variables are then mapped to some piece of memory or if the compiler is smart enough, it might even map certain (temporary) variables only to registers on the CPU to save some memory (not completely sure about that last thing though). The compiler thus creates a series of bits where each variable is represented by the correct register- or memory-address and the cpu does not bother/know about any variables.

For dynamically allocated memory things get a bit trickier, but eventually it comes down to memory addresses being stored in variables which are handled by the compiler again.

I hope I understood your question correctly and did not spread too much nonsense (if I did, please correct me) as I am not an authority whatsoever in this region, but that is roughly my view on these things.


First of all note that a non-deterministic algorithm and a non-deterministic Turing machine are two different things.

A non-deterministic Turing machine is a computational model, while a non-deterministic algorithm "is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm" (Wikipedia). For example a QuickSort algorithm which partitions the array based on random choice of a pivot is a non-deterministic (probabilistic) algorithm.

So your definition 1 should be read as following

  A problem $L$ is in $NP$ when there exists a nondeterministic Turing machine which solves problem $L$ in polynomial time.

Similarly, the second definition should be read as following:

  NP includes decision problems. If there exists a solution for these problems, it should be possible to check on a deterministic Turing machine in polynomial time whether the solution is indeed a solution.

For the concept of $NP$ see this post.


Is that true that A is decidable if A$\le_m$A complement?

If co-$A$ is decidable then so is $A$, as you mention in your question.

However the mere fact that $A \le_m$ co-$A$ does not imply the dependability of $A$. See this answer.


These are both wrong, as they don't obey the syntactic rules of first-order logic. The rules are:

if $P$ is an $n$-ary predicate and $x_1, \dots, x_n$ are variables, then $P(x_1, \dots, x_n)$ is a formula;
if $\varphi$ and $\psi$ are formulas, then $\neg \varphi$, $\varphi\wedge\psi$ and $\varphi\vee\psi$ are formulas;
if $\varphi$ is a formula and $x$ is a variable, then $\exists x\,\varphi$ and $\forall x\,\varphi$ are formulas;
nothing else is a formula.

(If you like, you can say that $\varphi\rightarrow\psi$ and $\varphi \leftrightarrow \psi$ are formulas, or you can say that they're just abbreviations for $\neg\varphi\vee\psi$ and $(\neg\varphi\vee\psi)\wedge(\varphi\vee\neg\psi)$, respectively.)

There's often more than one way of translating any English-language statement into a first-order sentence.  Decide what your domain is going to be and the rest will follow.

Every student who likes chocolate is smart.
Here, you have several choices of domain, such as the following.

Domain is the set of all students: $\forall x\,\big(\mathrm{LikesChoc}(x)\rightarrow\mathrm{Smart}(x)\big)$. Since everything in the domain is a student, the variable $x$ can only be a student so you don't need a predicate to say that.
Domain is, say, the set of all people: $\forall x\,\big(\big(\mathrm{Student}(x) \wedge \mathrm{LikesChoc}(x)\big)\rightarrow \mathrm{Smart}(x)\big)$. The domain now includes things that aren't students, so we need to enforce that with a predicate. A professor who likes chocolate isn't necessarily smart.
Domain is, say, the set of all people and all foods. $$\forall x\,\big(\big(\mathrm{Student}(x) \wedge \exists y\,\big(\mathrm{Chocolate}(y) \wedge \mathrm{Likes}(x,y)\big)\big)\rightarrow \mathrm{Smart}(x)\big).$$ That is, for every entity $x$, if $x$ is a student and there is a thing $y$ that is chocolate and is liked by the student $x$, then $x$ is smart. I've assumed that "likes chocolate" means "likes at least one thing that is chocolate"; you could interpret it to mean "likes all things that are chocolate", and you can probably figure out how to change the formula to reflect that.

There exists a barber who shaves all men if, and only if, they do not shave themselves. I'll let you have another go at this. Try taking the domain to be the set of men, with a unary predicate that says who's a barber and a binary predicate (as you have), that says who shaves whom.


Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

here is a construction not exactly as requested but related/ somewhat similar. the contrapositive of the Chomsky-Schutzenberger theorem can be used to prove a language is not unambiguously CFL. it describes the close connection of the construction to generating functions that yields key insight into the problem.

see ORDINARY GENERATING FUNCTIONS OF CONTEXT-FREE
GRAMMARS / TANNER SWETT, EDWARD ABOUFADEL, sec 2.6 p 6


Counting subarrays that satisfy either of two conditions

I don't want to give away the solution -- I want you to have the chance to experience the pleasure of finding a nice solution on your own -- but I'll suggest a bunch of hints that might help:

To count the number of range-pairs that satisfy either 1) or 2), you could instead count the number of range-pairs that satisfy neither 1) nor 2) (and then adjust your answer appropriately).  What would it mean for a range-pair to violate 1) and violate 2)?  Try writing out the conditions.  I think you might find that those conditions are easier to think about.  When I suggest you write out the conditions, I really do mean it: write it down, in full, and then stare at the result for a while.  I think you'll be able to find how this is related to another problem that is easier to state.
You might look at the first derivative of the array $a[]$.  In other words, let the array $b[]$ be defined by $b[i] = a[i]-a[i-1]$ (so $size(b) = size(a)-1$).  Now translate the conditions so that they refer to $b$ instead of $a$.  Write down the result, simplify as much as possible, and stare at it.  I think you'll find that helps you write down a cleaner version of the problem statement, which makes this problem look even cleaner and helps you see how this might be related to some other problem that is easier to restate.  Hint: repeated substrings....
You might find it interesting and helpful to learn about algorithms for the longest common substring problem, the Rabin-Karp hash function, and rolling hash functions.  Suffix trees may be helpful, too.
If you're still stuck, try counting the number of such range-pairs where the ranges are of length 1 (i.e., $y_1-x_1=y_2-x_2=1$).  Can you do it?  Now try counting the number of such range-pairs of length 2.  How would you do that?  Can you do it?  Is there a simple way to think about what that's counting?  Now how about the number of range-pairs of length 3.  Once you've solved all three of those, does that give you any ideas for how to generalize?  I'm not trying to suggest that this is literally the algorithm you should use (it's one possible algorithm, but you can build better ones), but that this will help you conceptualize what this is asking you to solve and it might help you think about the problem more clearly so that you can identify even better solutions.

Finally: You'll need to spend some significant time struggling with this problem on your own.  Be prepared to have to try out many different ideas and have most of them go nowhere. Be persistent. Don't expect it's just going to magically come to you in 5 seconds.  Solving these kinds of algorithm problems takes hard work and a lot of effort, so don't just assume it's not going to work before you put in that kind of effort.

Bottom line.
I'm pretty sure this can be solved in $O(n\ell)$ time, where $n=size(a)$ and $\ell$ is the length of the longest repeated substring (and thus in $O(n \lg n)$ time on average, if the input string is random).  Also I believe it should be possible to solve this in $O(n)$ worst-case running time, using sufficiently advanced algorithmics machinery (augmented suffix trees).  Caveat: I haven't checked all the details carefully, so you should do that yourself.


Does the running-time of this push-relabel algorithm become zero if there are many edges?

First of all, we usually assume that there are no self-loops. As a consequence, $|E| \leq |V|(|V| - 1) < |V|^2$.

That aside, there is (probably) a misuse of Landau notation here.

The given bound is (probably) not correct for all (families of) graphs. For instance, if $|E| = 0$ the same arithmetic issue occurs but the algorithm will certainly have non-zero running time.

The authors probably simplified away terms of the order of, say, $\Theta(|V|)$ or $\Theta(|E|)$. They do this because they are asymptotically dominated by the given term -- if all quantities are non-zero. This is a fundamental problem with using Landau notation with more than one variable without being rigorous about it.

So, even if the leading term would become zero (which can certainly happen and be correct!) lower-order terms would be non-zero and lead to useful bounds.

Example

Consider this very simple algorithm:

1 def algo(n, m)
2   x = 0
3   for i = 1 .. n
4     for j = 1 .. m
5       x += 1
6   return x

A standard analysis tells you immediately that the running-time is in $\Theta(nm)$ as that is how often the line x += 1 will be executed. Now, if n or m is zero, does the algorithm have zero running time? No!

A more precise analysis leads to the running-time being

$\qquad c_1 + c_2 n + c_3 m + c_4 nm$

with suitable constants $c_1$ (cost of lines 2 and 6, setup of line 3), $c_2$ (management of line 3, setup of line 4), $c_3$ (management of line 4) and $c_4$ (line 5).

Background

Landau notation only makes sense if the parameters go to infinity in suitable ways. We can not just insert finite values for some parameters and expect it to behave well.

Refer to A general definition of the O-notation for algorithm analysis by Kalle Rutanen et al. for details.


How to build/recognise a deadlock-free order of resources

Preventing deadlocks can be achieve by removing one of the Coffman condition, one being the  circular wait condition.

For this we need to build a partial ordering of the resources.

From Wikipedia a partial ordered (poset) set is :

  A (non-strict) partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all a, b, and c in P:

  a ≤ a (reflexivity);
  if a ≤ b and b ≤ a then a = b (antisymmetry);
  if a ≤ b and b ≤ c then a ≤ c (transitivity).

For the processes, there is no interest in the first two clauses, resources are distinct and unique. All we care about is the transitivity. Assuming a given order of resources, we then must ensure that each process never claims a lower resource before a higher one.

Building a deadlock free order is as simple as ordering the resources. This choice is arbitrary.

To solve your examples, we need to find what order has been chosen, if one exists, and verify it is a poset.

is not a poset since $a > c$ (from X) and $c > a$ (from Z) contradicts the transitivity.
is a poset since $b > a > c > d$ in all groups.
is not a poset since $b > c$ (from X) and $c > b$ (from Y) contradicts the transitivity.
is not a poset since $a > c$ (from X) and $c > a$ (from Y) contradicts the transitivity.

Conclusion, only 2 is a deadlock free order as the circular wait condition is removed.


Given matrix, count paths visiting each number exactly once

If I understand well, you are looking for an Hamiltonian path which is basically NP-complete. With your DP idea, there is $2^{21} = 2M$ possible bitmasks and there is no way to order them. So I am not sure to understand how it works.

In fact you can start building a graph and get rid of any direction/"-1 cells" consideration. In your example you would get a simple chain from 1 to 21.

Then, in the very general case you may have to explore all possible paths (using DFS for instance). But in this kind of problem you can look for some tricks. The point is to select the 20 edges of the path:

Any vertex having only one edge is either start/end (NB a reversed valid path is valid like in your example) and its edge is selected
A vertex having 2 edges have these edges selected (unless it is start or end)
A vertex having 2 edges selected, have all the other edges removed.


Wikipedia does not list insertion complexity for arrays - why?

The array is a fixed-size data structure, and insertions would change its size. Thus they are impossible, which is why Wikipedia says "N/A" for the insertion complexity.

A dynamic array can have its size changed, which is why complexities are given in that column.


How can CFGs have epsilon rules if CSG may not have them?

The definition you state is for noncontracting grammars, which define the context-sensitive languages (modulo the issue of the empty word). In contrast, context-free grammars define the context-free languages, which are a strict subset of the context-sensitive languages.

So whoever told you that a Type 1 grammar is context-free iff it is noncontracting, used highly idiosyncratic terminology. Or perhaps they just made a mistake.

The Wikipedia article mentions a paper of Chomsky in which noncontracting grammars are called "Type 1". In an earlier paper of Chomsky, he used "Type 1" to mean context-free grammars. This might be the source of the confusion.

Finally, to answer the question in your title: noncontracting grammars only define the context-sensitive languages without $\epsilon$. Conversely, the context-free languages without $\epsilon$ are defined by context-free grammars without $\epsilon$ productions (this follows from Chomsky normal form, for example). In this sense a noncontracting grammar is a generalization of a context-free grammar, in both cases for languages without $\epsilon$. If you want to include also languages with $\epsilon$, you need to consider essentially noncontracting grammars instead; these are also allowed to contain the product $S\to\epsilon$, assuming $S$ doesn't appear in the right-hand side of a production.


How does node expansion work in a graph for AI search?

It seems to me that you are confusing the graph itself with the search tree produced by some search procedure.
As you state, you can't go from one node to the next unless that node knows its neighbors (and not only its own parent). But the search tree is (perhaps implicitly) generated from a search procedure you perform on the actual graph. Perhaps this is what the authors mean with the description you quote.
The actual graph on which you do a search in you can represent via an adjacency list. There, given a node, you can locate its neighbors and the search progresses using that information.


A faster, leaner JavaScript for scientific computing: what features should I keep?

If you want to use JavaScript for scientific computing, why not try Node.js? Node is based on Google's V8 engine with some additional functionality for interacting with the file system, writing servers and linking to C and C++ libraries (this is definitely not an exhaustive list). It sports fast execution times and provides an interactive console as well as a way to execute your programs from the command line. I found @DaveClarke's comment about Python acting as "glue code" interesting because of the wording. Here is an excerpt from the Node documentation on addons:

  Addons are dynamically linked shared objects. They can provide glue to
  C and C++ libraries.

Node also has an excellent package manager called NPM, which would make it easy to share scientific modules which you have written. The NPM repository already contains some scientific modules, such as "natural" (for natural language processing) or "clusterfck" (a clustering library). There are most definitely many other libraries out there for a variety of applications.

The great thing about this solution is that you wouldn't have to modify JavaScript or create a new language. The syntax is essentially the same, but your code does not need a browser to execute. If you plan to follow up with node, a good first step might be to start creating addons for existing open-source scientific libraries written in C and C++, or you could port them to JavaScript. I was actually thinking about using node for scientific programming today which is what led me to this question. It would be great to see more robust tools like you find in Python.

I initially had links to natural and clusterfck, but I do not have enough rep to post them. Luckily, they come up as the first results if you google "clusterfck node" and "natural node".


Why did Alan Turing have to define computation before demonstrating undecidability?

Without fixing a concrete model of computation, you can't show that you can actually do the "then construct" part of your argument, so it's not a proof.


High Level Programming Languages vs Block Programming Environments

A Block programming environment is higher in the abstraction levels as compare to high level programming languages which basically mean that Block programming environment is easy to work with and there is less conceptual burden to carry BUT you can do "less stuff" (as it is very abstracted) where as in high level programming languages you can do "more stuff" but the conceptual burden at this level is much high.

This is how abstraction principle works. More abstract = less things to worry about BUT less ability. Less abstract = More things to worry about BUT more ability.

It is usually advised that you start at the top abstraction layer so that you can start learning things without freaking out with way too much details and as you get more and more experience you start to look at bottom abstraction layers to gain more insights and get more done.


A "trivial" property is one that holds either for all languages or for none.


Is there a problem in this BN form language?

That grammar has two problems.

It's ambiguous. You say that you want to give AND precedence over OR and make both operators left-associative, but your grammar does not reflect that goal since it does not distinguish AND from OR and it explicitly accepts both left- and right-associative parses:

<WORD> <OPERATOR> <LOGICAL>    (* right associative *)
<LOGICAL> <OPERATOR> <WORD>    (* left associative *)

On a more minor level, probably a typo, your third and fourth productions are identical.

It's possible that you have tried to fix the issue by using precedence declarations in your parser generator tool. Precedence declarations are not part of BNF, and incorrect precedence declarations are really a programming error, rather than an issue in parser theory.

If you have such a problem, you should probably ask a question on a programming site, such as StackOverflow, and comply with the usual rules of including a complete reproducible example. However, in the usual approach to using precedence to resolve parser ambiguity, it is important that you don't have explicit parser ambiguity, as above. Thus, a "traditional" precedence-augmented BNF grammar (as per the Dragon book) would look like this:

%left <OR>
%left <AND>

<LOGICAL> ::= <WORD>
          |   <LOGICAL> <OR> <LOGICAL>
          |   <LOGICAL> <AND> <LOGICAL>


Space and time complexy of operations on 32-bit array vs. binary array

If you ignore the word size then both arrays use $\Theta(n)$ space. Remember that $32n = \Theta(n)$.

If your word has a (non-constant) length of $w$ bits and all the integers in a1 fit in a constant number of words (with no additional assumptions on their values), then a1 still uses $\Theta(n)$ words, while you can represent a2 using $\Theta(\lceil \frac{n}{w} \rceil)$ words (by packing groups of $w$ bits of a2 into a single word).

A common choice of $w$ in the word-RAM model is $w=\Theta(\log n)$.

In your Python example there is no difference between a1 and a2 since both lists are storing integers (using a fixed number of bytes that depends on the implementation and architecture, and assuming that the stored integers fit within the maximum integer representable using these bytes. Handling arbitrary precision integers is another story).
However there might be ad-hoc types specifically designed to handle indexed collection of bits (e.g., bitsets).

Also, the language/implementation might optimize the array representation when it knows that it will store bits. This is the case, for example, of std::vector<bool> in C++, which can possibly reduce the space usage by some constant factor by packing bits into integers (as described above). For a fixed words size (e.g., 32 or 64 bits), this does not change the asymptotic space complexity.


How to (Efficiently) Sort a List of Items with Parent/Child Relationship

I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological_sorting) to order the items.


Philosophical answer

The general philosophy in realizability theory (TTE is a special case of it) is that for a program $p$ realizes a map $f : A \to B$ then $p$, it should work correctly on realizers of arguments, i.e., if $r$ realizes $x \in A$ then $p\,r$ realizes $f(x) \in B$. It is quite unnatural to say anything about "non-realizers", for at least two reasons. First, it would break the categorical structure of the category of representations (exponentials break). Second, from the programming point of view you are asking that a program always produce garbage output when given garbage input. This is an unreasonable request: the behavior should be unspecified for garbage input, as a program may in fact be unable to tell that it was given garbage input.

Technical answer

We are in the realm of realizability theory, of which TTE is a special case. It is important to understand that, when working with representations, there are two notions of function:

The maps which take realizers to realizers, in the case of TTE these are the maps $\Sigma^\omega \to \Sigma^\omega$. Let us call these realizers.
The morphisms in the category of represented sets, which are maps between sets that are tracked by a realizers. In TTE these are also called $(\gamma_1, \gamma_2)$-computable maps, but we shall just call them morphisms.

Standard textbooks on computability theory almost alawys talk about the first notion. The question is asking about the relationship between the first and the second notion.

Typically realizers are not actually functions, but are elements of some model of computation, such as Turing machines (either type I or type II) or the closed terms of $\lambda$-calculus. In the case of Type Two Effectivity this becomes apparent once we try to compute the standard representation for the set of realized maps, because that is when we define what it means for an element of $\Sigma^\omega$ to implement a realizers $\Sigma^\omega \to \Sigma^\omega$.

Morphisms between represented sets are functions (which happen to be tracked by a realizer).

Let us consider the question "Is the restriction of a computable map also computable?" in both senses.

Is the restriction of a realizers (as a map) again a realizer? The answer is negative, for if $f {:}{\subseteq} \Sigma^\omega \to \Sigma^\omega$ is computed by a Turing machine, one can show that the domain of $f$ is a $G_\delta$-set. Therefore, if we restrict $f$ to a domain which is not a $G_\delta$-set there will be no Turing machine that computes the restriction.
Is the restriction of a morphism $f : D_1 \to D_2$ again a morpshism? Here we have to understand "restriction" in the sense of category theory, i.e., a precomposition with a (regular) mono. This amounts to restricting the representation $\gamma_1 : \Sigma^\omega \to D_1$ to a subset $D \subseteq D_1$.  We could define the realizability model so that restrictions need not be realized, but that would be silly and useless. It is much better to make sure that the resulting category has good properties, because then we can actually do something with it. And so we define the notion of "tracked by a computable map" in the way we do and enjoy the resulting ambient.


A language L is equal to its Kleene closure if and only if L contains ε and L = L^2. So in a sense, this problem boils down to testing whether those two conditions are true. The test for whether L contains ε is pretty easy to accomplish - just see if A's start state is accepting. The trickier part is seeing whether L = L^2.

If you already know that ε ∈ L, then L ⊆ L^2, so the only way that L isn't equal to L^2 is if there's a string in L^2 that isn't in L. This is something we can test in polynomial time, as follows:

Construct an NFA for L^2 by applying the concatenation construction to A and itself. Call the resulting automaton B.
Take the cross product of B and the automaton formed by flipping the accept and reject states of A. Running this automaton corresponds to simultaneously running A and B, with the accepting states corresponding to executions that lead to an accepting state in B and a rejecting state in A.
Run a DFS over this net automaton to find an accepting state. If one exists and is reachable, there's a string in L^2 that isn't in L, and otherwise every string in L^2 is in L.

Step (1) takes polynomial time and builds an automaton with 2n states, where n is the number of states in the original automaton A, since we're just duplicating the states in A and adding in some new transitions. Step (2) builds an automaton with 2n^2 states, and the DFS in step (3) runs in time polynomial in n.

Overall, this construction runs in polynomial time.


Divide and conquer algorithm to sort nk items in n lists that runs in O(nk*logn) time?

This is classic multi-way merge: Create a heap of pairs (element, which list did it come from). Initialize with first elements of each list. Repeatedly remove the minimum element and add the next element from its originating list.

Also discussed before at https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge .


Number of binary search trees with maximum possible height for n nodes

The number of trees with $n$ nodes of height $n-1$ is $2^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives $2^{n-1}$ options.


Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

Let us describe an NTM $N$ that computes $L_1$ in polynomial time. The machine "guesses" the first $n - |w|$ letters of a word $x'$ (it makes all possible guesses non-deterministicly) and append $w$ to $x'$ then it simulates $M$ on the resulting word. If $M$ accepts on any of the guesses the machine $N$ halts and accepts. If all reject, $N$ also rejects.

Since, we have $n$ zeroes as a part of the input, the guesses are done in linear time in the size of the input. The simulation also runs in polynomial time in an NTM by assumption, hence, we get a total polynomial running itme and hence, $L_1$ is in NP. The correctness of $N$ is straight forward.


Are there infinite possibilities to the outcome of the P vs. NP question?

This isn't really a question about P vs. NP - any other statement would do in its place. The point is that there are a couple different "philosophical contexts" being mixed up here, and depending on exactly how you ask the question each of $2$, $3$, or infinity are reasonable answers (I'm not claiming that these are exclusive, but I think they frame the question well):

The Platonic: If we adopt a certain measure of Platonism (for P vs. NP, something like "the natural numbers exist objectively even if our understanding of them is limited") then yes, every statement is either true or false. Provability from a given theory is a purely secondary matter, and the independence of a statement from (say) ZFC has no bearing on its truth.
The formalist: If we don't want to make any philosophical commitments, the most we can ask is whether the statement is provable in a given theory. Once we fix a single theory of interest - say, ZFC - the formalist version of the question does indeed boil down to three possibilities: our statement is either provable in that theory, or disprovable in that theory, or independent of that theory. (Or the theory is inconsistent, in which case the first two options hold simultaneously.)

Wildness of the type you're asking about emerges when we ask the "broader" formalist question: which theories is our statement provable in? When asked this way we do indeed get a wild situation, since for any interesting statement there will be some theories which prove it and some theories which disprove it. Note that this is really a more "stable" perspective than focusing on a single theory, but in practice mathematicians tend to prefer a single background theory so we can ignore foundational considerations which aren't really germane to the specific mathematics at hand.

Of course this conflicts with the language we often use in actual practice. The "true/false/independent" trichotomy blurs the Platonic and formalist contexts by conflating a fixed theory - usually ZFC - with "truth." This is a common practice, but is at best raising the question of why we assign privileged status to ZFC specifically (why not ZFC + an inaccessible? or ZF? or ZC? or ...). Ultimately it's just a linguistic convention: we recognize that in many situations, in order for our everyday mathematical language to be truly accurate we need to implicitly understand "true" as an abbreviation for "provable in ZFC."


Is there an equivalent of van Emde Boas trees for ropes?

Fredman and Saks show in "The cell probe complexity of dynamic data structures" that you cannot do better than $\Theta\left(\frac{\lg m}{\lg \lg m}\right)$ amortized time for the operations you are looking for. They call this problem "list representation".

Dietz presented a data structure in "Optimal Algorithms for List Indexing
and Subset Rank" that achieves this bound.


liskov substitution principle seems to have two conventional meanings

I don't think either of these is the Liskov substitution principle. My understanding of the principle is that for $S$ to be a subtype of $T$, it must be the case that we can substitute a value of type $S$ anywhere a value of type $T$ is required without compromising the correctness of our program.

Now, the subtyping rule for functions is probably a sufficient condition for the Liskov principle to be satisfied, as long as functions are sufficiently abstract. But this is not "the" principle, because it says nothing about anything that isn't functions.

Also, this page argues that subclassing in most OOP languages is insufficient to ensure the Liskov principle is satisfied. That is, it only ensures that the principle is satisfied with respect to other simple, declared subtyping relationships like you mentioned. It does not ensure that implicit invariants are respected, and indeed, it is possible to violate these invariants in a subclass. So the Liskov principle would say that sometimes sub-class does not imply sub-type.

It's probably also possible for this second argument to apply to "functions" in a language as well (although it would be pretty unsatisfactory), in which case the Liskov principle would not validate the induced subtyping rule.


What is the time complexity of checking if a number is prime?

When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have this amount of digits. It only matters a factor $\frac12$ at most, and that is absorbed in the $O$.

This gives a computational complexity of $O( \sqrt{n} \log \sqrt{n}\log(\log(\sqrt{n}) ) \log\log(\log(\sqrt{n}) )))$. We can simplify this to $O( \sqrt{n} \log(n) \log(\log(n) ) \log(\log(\log(n) )))$.

However, when notating it using the number of bits $b$ of a number, which is more standard usage, we get a computational complexity of $O(2^{b/2} b \log b \log\log b)$.

You also need to compute $\sqrt{n}$ but that has only complexity $O(b \log b \log\log b)$ when using Newton's method and the Schönhage-Strassen algorithm.

However, this is not optimal. The current best algorithm, the AKS algorithm, reaches a complexity of less than $O(b^{7})$ worst-case , which is much faster.
(To be precise, even $O(b^{6+\varepsilon})$ for any $\varepsilon>0$ has been shown, but that is more complicated than it needs to be for this answer.)


$\mu$ and $\sigma$ are simply mean and standard deviation. I assume there is also a normalizing coefficient out there. Or the normalization as you mentioned comes from $\alpha$, since it $\alpha$s are vectors composed of the standard deviation and mean.


A "triangular" data structure for commutative relationships

Some languages, such as C, support ragged arrays: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.


Does linear programming admit a strongly polynomial-time algorithm?

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.


Naive Bayes' Classification and Using the Entire Vocabulary in the Denominator

If you're using Laplace smoothing, you'll replace the count with a "pseudocount", and that won't be zero.  So, it does make a difference.


How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?

It can be computed in a completely analytical way. Take:

$$
F_n = F_{n-1} + F_{n-2} + F_{n-1}F_{n-2}
$$

Adding $1$ to both sides and factorizing we obtain:

$$
F_n + 1 = (F_{n-1} +1)(F_{n-2}+1)
$$

Now let $G_n = F_n + 1$ :

$$
G_n = G_{n-1} G_{n-2}$$

Taking the logarithm in some base $b$ :

$$
\log_b{G_n} = \log_b G_{n-1} + \log_b G_{n-2}$$

Which we rewrite, letting $H_n = \log_b{G_n}$ , as:

$$
H_n = H_{n-1} + H_{n-2}
$$

This suggests an effective way to compute $F_n$ . First of all we compute $H_0 = \log_b(1 + F_0)$ and similarly $H_1$. Then we determine $H_n$ in closed form. Since $H$ is a second-order recurrence with constant coefficients, $H_n$ is in the form:

$$
H_n = A\phi^n + B\psi^n
$$

where $\phi, \psi$ are the solutions to the associated polynomial equation $h^2 = h +1$, namely $\frac{1 \pm \sqrt{5}}{2}$. Knowing $H_0$, $H_1$, we can determine $A, B$ as the solutions to the following system:

$$
\left \{
\begin{array}{r c l}
H_1 & = & A\left( \frac{1 - \sqrt{5}}{2} \right) + B\left( \frac{1 - \sqrt{5}}{2} \right) \\
H_0 & = & A + B
\end{array}
\right .
$$

Now, remembering that $H_n = \log_b{G_n}$ and $G_n = F_n + 1$, we can finally compute:

$$
F_n = b^{H_n} -1
$$


How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?

Generally, the idea of a (normal) petri-net is to efficiently represent a system to model an arbitrary amount of 'agents' that change their state depending on certain transitions. (This would quite quickly get out of hand in a state machine)

So, the basic strategy is to first determine what your 'agents' are and model them as your tokens. The state of an individual agent corresponds to the places and the state transitions correspond to transitions in the petri-net.

Depending on what you want to model, you need to do a bit more and also consider different (in your modeling interpretation, not as far as the petri-net is concerned) tokens that are created by some action of other tokens, but the general idea of what tokens, places and transitions are remains the same.

Your answer follows the basic strategy, but it fails to meet the requirement that the tokens are distinguishable and that at least one of them must remain in front of the hall. In a normal petri-net, we cannot distinguish tokens from another, so if a token moves to $p_1$, we cannot know which.

A solution is to construct different transitions such that we know which assistant moves, based on the transition taken. The 'given solution' you provide does this and adds some restrictions to model the requirement that at least one of them must remain in front of the hall.


I guess that this question should not be left floating around unanswered.

The reasoning in (b) can't be used to prove that this problem is NP-complete because, at best, it implies the reduction from 3PARTITION to PARTITION which is of no use. Any problem in NP can be reduced to PARTITION.

The proper way of doing this (after showing that the problem is in NP) is to:
i) Start from an arbitrary instance of PARTITION

$A=w_1,...,w_n$ with $S(A)=\sum\limits^{n}_{i=1}w_{i}=2m$

ii) Append $m$ to $A$ and obtain $A'$, an instance of the 3PARTITION problem.
iii) Prove that $A\in PARTITION\Longleftrightarrow A'\in 3PARTITION$
iv) Conclude that $PARTITION \leq_{p}3PARTITION$


Minimal length of a string that contains two strings

Following the explanation on Wikipedia,

obtain the longest common subsequence of $a$ and $b$ with a (quite elementary) dynamic programming approach and
insert the characters which are not part of the LCS in-order and in appropriate positions.

Note that the result of neither step is necessarily unique.

Writing actual (pseudo)code, correctness proof and runtime analysis are easy exercises.


Optimal algorithm to distinguish given black box access

You need $\Omega(2^n)$ samples in order to accomplish your task.
Consider an algorithm that gets $m$ samples from $D$ and then another sample, either from $D$ or from $U$, and has to guess which it is. Its input thus consists of $m+1$ samples $X_1,\ldots,X_m,Y$.
We will generate the distribution $D$ at random by choosing a random set $V \subseteq \{0,1\}^n$ of size $2^{n-2}$ and letting $D$ be a uniform sample from $V$. Note that $d_{\mathrm{TV}}(D,U) = 3/4$.
Consider now the following two distributions:

Distribution $\mathcal{D}$: Choose $D$ at random as above. Generate $m+1$ samples from $D$.
Distribution $\mathcal{U}$: Choose $D$ at random as above. Generate $m$ samples from $D$ and one sample from $U$.

Let $S$ be the set of vectors appearing in the first $m$ samples. We can describe the distribution of the final sample as follows:

Distribution $\mathcal{D}$: With probability $|S|/2^{n-2}$, output a random element in $S$ (each one is output with probability $1/2^{n-2}$). Otherwise, output a random element not in $S$.
Distribution $\mathcal{U}$: Output a random element.

To see where the alternative description of $\mathcal{D}$ comes from, notice that given $S$, the conditional distribution of $V$ is a random set of size $2^{n-2}$ containing $S$. When sampling a random element from $V$, we have a probability of $|S|/2^{n-2}$ to choose one of the elements from $S$, with probability $1/2^{n-2}$ each. Otherwise, we choose an element from $V \setminus S$, which given the distribution of $V$, is just a random element not in $S$.
This shows that the TV distance between the two distributions is
$$
\mathbb{E}\left[|S|(1/2^{n-2} - 1/2^n)\right] < \frac{m}{2^{n-2}}.
$$
In particular, any algorithm whatsoever will behave almost the same in both cases unless $m = \Omega(2^n)$. Indeed, your algorithm $A$ satisfies
$$
\Pr_{\mathcal{D}}[A=1] - \Pr_{\mathcal{U}}[A=1] \geq \frac{3}{4} - \frac{1}{4} = \frac{1}{2},
$$
showing that the variation distance between $\mathcal{D}$ and $\mathcal{U}$ is at least $1/2$. This is only possible if $m/2^{n-2} \geq 1/2$, that is, if $m \geq 2^{n-3}$.


Remove duplicates of first elements of pairs

You can do this pretty easily in $O(n log(n))$ time by using a hash table (such as Python's dict) to map from the first value in a pair to the largest second value it's been seen with.

def myfunc(pairs):
   mapping = {}
   for key, value in pairs:
       if key not in mapping or value > mapping[key]:
           mapping[key] = value
   return sorted(mapping.items())

Hash table lookups take $O(1)$ time on average, so eliminating the duplicates in the loop will take $O(n)$ time. Sorting is (asymptotically) slower, taking $O(n log(n))$ time.


Since you find it interesting to solve, I do not want to completely
spoil it too much  for you. So here is a big hint to solve it in linear time.

You start with two indices $i$ and $j$ which are the first and last indices of
central segment.

Initially you set $i=0$ and $j=n$. And you compute the 3 sums in
$s_1$, $s_2$ and $s_3$. So initially $s_1=s_3=0$.

Then you progressively increase $i$ and decrease $j$, by variations of
1, keeping $s_1$ and $s_3$ about the same value (by doing the change on the
smallest sum $s_1$ or $s_3$), until one becomes bigger than $s_2$.
Each increment or decrement  takes constant time (adding or
substracting the value of an element to two of the sums, and doing a
few comparisons).

When one of $s_1$ and $s_3$ becomes larger than $s_2$, say for example
$s_1$. Then you have $s_1\geq s_2 > s_3$.

Then you know that the right value for $i$ is either the current value
or the previous value. Typically it is the previous value of i, if
$s_1$ has become greater that the previous value of $s_2$. But things
are a bit more subtle. So you note this value of $s_1$ as $m_1$, a
possibility for the maximum, and then try to see if you could have
achieved a lower value for the maximum with the previous value of $i$
and $s_1$,
just before the last increase. So you revert $i$ to that previous
value, and you start to decrease $j$ to get the lowest possible maximum for
$s_2$ and $s_3$ without touching $i$ (that is easy, and recall that $s_1$ remains lower
than both others sums). Let $m_{2,3}$ be the lowest maximum found. Now, if
$m_{2,3}$ is greater than $m_1$, then the answer is $m_1$, else the
answer is $m_{2,3}$.

And you must consider the symmetrical case when $s_3$ is the first to
exceed $s_2$.


Unix glob() function and formal language equivalence

Every glob expression can be recognized with a regular expression (the translation is straightforward).  Every regular language is also context-free, and there is a straightforward translation: convert the regular expression to a DFA, then turn that into a pushdown automaton that never uses or looks at its stack.  So, it follows that every glob expression can be recognized by some pushdown automaton, i.e., it recognizes a context-free language.


What is the name for the complexity class $O(n^{1+\epsilon})$

The term I've seen in use is superlinear, as in "Are there super-linear time complexity lower bounds for any natural problem in NP?"


Concatenating polyhedra at their region of contact

I was recently referred to an article 'Mesh arrangements for solid geometry' by Qingnan Zhou et. al. [pdf]
and the corresponding code by Dr. Campen which exactly solves this problem.

This algorithm inserts new vertices and edges in the region of intersection between $P1$ and $P2$ thereby a generating new polyhedron $P$ and evaluates boolean operators on $P$ by selecting/rejecting vertices and edges depending on the operator. For my problem, $P$ forms the solution.

However, out of curiosity I would like to know if anyone has an alternative to this approach.

Update: I have tested the tool referred above against my original problem, it successfully prevents self-intersection by inserting new vertices and edges at the region of contact between $P1$ and $P2$.


Choosing correct action in bottom up parsing

Because it will allow the string to be parsed. I know that is not a very satisfactory answer, but it really is the only answer. It is similar to asking why a particular step in a proof was chosen, and not some other step: because whoever wrote the proof (or, in this case, the derivation) somehow figured out how to do it.
That depends on the algorithm used by the parser. It might try one action, see if it works, and if not backtrack and try the next possibility. It might try both actions in parallel, reporting only the succesful one(s) at the end. It might have an analysis of the grammar that lets it know what to do in particular circumstances. You will probably see various different techniques as your course continues.


What is the complexity of this bubble sort algorithm?

The inner loop is executed $(n-1) + (n-2) + (n-3) + \dots + 0 = \tfrac{1}{2}n(n-1) = \Theta(n^2)$ times.


It doesn't work. I am paraphrasing Scott Aaronson in this answer, whose article on the subject gives more details.

They claim to have some way of solving the subsetsum problem efficiently. The basic gist being that they encode all of the numbers in the instance as electrical signals, and then throw all the electrical signals together in to a big melting pot. They then measure the output signal and try to find whether it contains a signal corresponding to a solution.

However, this requires an exponentially precise signal (to be able to figure out whether the particular frequency/signal you want is there) so it isn't really a viable approach to solving $NP$-complete problems. The article claims that this is likely to be resolved in the future and that the general principle of memcomputing might one day become viable but I think that claim should be taken with a grain of salt. It seems that whatever trade-off you make, be it time, energy, memory or precision, you always end up hitting some barrier that requires exponential resources.


In which pipeline stage are exceptions detected?

Both.

I'll assume you are talking about pipelined machine organizations with

out-of-order completion (different instructions take different amounts of time to produce their results)
precise interrupts (instructions appear to produce their effects in-order).

An exception might be detected in the instruction fetch stage (if, for example, there is a page fault when trying to access the instruction memory), in the execution stage (like in your example of an overflow) or, for memory instructions, for a page fault when trying to access the data memory.

One important question is what to do with the other instructions in the pipeline.  Instructions that were fetched before the excepting instruction should appear to commit their changes before the interrupt, and instructions that were fetched after the excepting instruction should get cancelled somehow before they commit any changes at all.

Typically you deal with this by having some form of commit stage (called the "write-back" stage in the 5-stage pipeline that is often used in computer organization courses.)  Instructions commit in order, even if they "complete" their execution out-of-order.  At the time the excepting instruction arrives at the commit stage all the previous in-order instructions will have committed, but their will be some number of instructions that were fetched after the excepting instruction still in the pipeline.  Those following instructions need to be cancelled, and this is often done by keeping a cancelled bit with each instruction as it flows down the pipeline.  The commit stage just doesn't write-back the results of any cancelled instructions.

The other question that needs to be answered is when do you redirect the fetch unit to the exception handler.  It would be simplest to signal the fetch unit only from the commit stage, but for longer pipelines that can cause an extremely long bubble between the exception being detected and the exception handler starting to fetch.  In that case you might redirect the fetch unit when you detect the exception.  The Pentium 4 did it this way, for example.


Is $O(\log_2 n)$ close to $O(n)$ or $O(1)$?

As far as I understand your question, you have to take a look at the differences: $O(\log n - 1) = O(\log n)$ versus $O(n - \log n)$. Since

\begin{eqnarray}
n - \log n & \stackrel!> & \log n\\
n & > & 2 \log n\\
\end{eqnarray}

you have $O(\log n) \subset{} O(n - \log n)$. The difference to $O(n)$ grows faster than the difference to $O(1)$.

Thus, $O(\log n)$ is closer to $O(1)$ than $O(n)$.


MSO (Monadic second-order logic) Logic On Words

Start with the following: There are three disjoint sets $X_1,X_2,X_0$ that together hold the $b$-positions of the string. The last $b$ is in set $X_1$,


You've stumbled on the fact that inference of static invariants for higher-order languages is quite difficult in practice, in addition to being undecidable in theory. I'm not sure what the definitive answer to your question is, but note several things:

Polymorphism and refinement types behave poorly together, as you have noted, in particular the notion of most general type is lost. A consequence of this is that analyses based on refinement types in the presence of polymorphism may need to chose between whole-program analysis (as opposed to compositional analysis) and the use of heuristics to decide which type you want to assign to your program.
There is a strong relationship between inferring refinement types and:

Computing the abstract interpretation of your program
Computing loop invariants in an imperative language.

With this in mind, here are a few disorganized references on the inference of refinement types. Note that there are many differing flavors of refinement types: I tend to be more interested in refinements of inductive datatypes, so this list may be skewed in that direction.

Start with the classics: Relational Abstract Interpretation of Higher-Order Functional Programs by Cousot & Cousot. This explains how to extend abstract interpretation to higher-order programs using relational semantics.
Liquid Types by Rhondon, Kawaguchi and Jhala. This is very evolved work, that combines HM and a type of predicate refinement to infer security annotations (array bound checks for instance) for ML style programs. The inference proceeds in 2 steps; the first is HM inference of type annotations, which guide the choice of refinements to perform.
I should probably also mention the work by Fournet, Swarmy, Chen, Strub... on $F^*$, an extension of $F^\#$ which seems similar to the liquid types approach, but with the goal of verifying cryptographic protocols and algorithms for distributed computing. I'm not sure how much published work there is on the inference of annotations in this case.
There is a nice paper by Chin and Khoo on inference of a specific kind of refinement types: types with size annotations.
The ATS programming language is a system which allows various refinements and provides facilities for writing programs with them. However the annotations may be arbitrarily complex (and thus undecidable) and therefore may require user interaction. I believe that there is a form of inference for these types, I'm not sure which article to recommend however.
Last, but not least The Cartesian Product Algorithm, by Ole Agesen. While not mentioning refinement types explicitly, this seems to be the work closest to solving the problem you seem to have. Don't be fooled by the mention of parametric polymorphism in the abstract: they look to infer concrete types, which are just tuples of possible atomic types. Emphasis is given on efficiency. I recommend reading this article first to see if it solves your problem.

Side note: type inference in the presence of intersection types can be very undecidable: in the simplest form, $\lambda$-terms with intersection type are exactly the strongly normalizing terms. Tread softly around them :)


How to prove a complete binary tree of depth N has $2^{N+1} - 1$ nodes?

Hint 1: Draw some binary trees of depth $0, 1, 2$ and $3$. Depth $0$ is only the the root.

Hint 2: Use Induction on the depth of the tree to derive a proof.

The base case is depth $n=0$. With depth $0$ we only have the root, that is, $2^{0 + 1} - 1 = 1$ nodes, so the formula is valid for $n=0$.

The next case is depth $n=0+1=1$, since the tree is full the root must have $2$ leafs. So we have $1 + 2 = 3$ nodes in total. The formula still holds since $2^{1+1} - 1 = 3$.

Can you generalize this procedure? Does this hold for all $n \geq 0$?


what are the weakest preconditions of these following statements

Let's do the first one. You want to find what condition on $b$ will imply $2(b-1)-1>0$. All you have to do is solve this inequality.
The other ones are similar.


Prune and search Algorithm for Generating a Bottleneck Spanning Tree

Let $b$ is the bottleneck edge of $MBST$, and let $b$ has weight $w(b)$.
Suppose $e_{m}$ is the median weighted edge of $G$, and let $e_{m}$ has weight $w(e_{m})$. Suppose $G$ gets partitioned into two subgraphs $G_{1}$ and $G_{2}$ such that edges in $G_{1}$ have weight $\leq w(e_{m})$ and edges in $G_{2}$ have weight $> w(e_{m})$.
If $w(b) \leq w(e_{m})$, then there must exist an $MBST$ within $G_{1}$ itself. Since the algorithm is recursing on $G_{1}$, it will output an $MBST$ if it exists. If the algorithm does not output a valid spanning tree, it means $b \notin G_{1}$. In other words, $b \in G_{2}$.
In that case, the algorithm will update $e_{m}$ to be the median weight edge of $G_{2}$. The graph $G$ will again get partitioned into two subgraphs $G_{1}$ and $G_{2}$. And, the algorithm can repeat this process.


Can Floyd-Warshall algorithm be used in an undirected graph with negative edges?

Floyd–Warshall can be used to detect the presence of negative cycles in directed graphs. This aspect has been widely used in the scheduling community in the form of detecting consistency of a simple temporal network. To answer your question, the values output by Floyd–Warshall will be correct even in the presence of negative edges as long as there are no negative cycles.


Is this padded version of the Halting Problem in NP?

Unless you're talking about promise problems, you are required to handle arbitrary inputs.

Given a string $x\in\left\{0,1\right\}^*$, we have $x\in L$ iff $x=\langle M\rangle \cdot BB\left(|M|\right)$ and $M$ halts for some fixed input ($\cdot$ denotes concatenation).

This means that even before talking about the witness (which is indeed linear), you must verify that $x$ has this specific form (unlike in promise problems, where you only care about specific inputs), and this is undecidable.

Note that this only shows why your justification to why this problem is in NP does not work. However, this language is obviously undecidable, since otherwise you could compute $BB(x)$, and thus lies outside of NP.


relation between $\forall$ and implication in intuitionistic logic using curry-howard and propositions as types

The difference between $s\to t$ and $\forall x : s. t$ is that in the second case, the return type of the function depends on the input.

For example, in most languages, you can make a function that takes a natural number and returns an array of that size and it will have type $\operatorname{nat} \to \operatorname{nat} \operatorname{array}$. But if you want to specify it further and say that it doesn't return any array but really an array of that size, then you would want to type it as $\forall n :\operatorname{nat}. \{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\}$. In both cases the output of the function (the array of size $n$) depends on the input $n$ of the function but in the second case, the return type $\{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\}$ also depends on the input while in the first case it does not.

Another example would be a function that takes a proof that $m=2$ and returns a proof that $m\le 2$. All it has to do it use the reflexivity of $\le$, which I'll call $\operatorname{le\_refl}$. You can define $(\lambda (m:\Bbb N).\lambda (p:m=2).\operatorname{le\_refl}(p)):\forall (m:\Bbb N).(m=2\to m\le 2)$. Note that you could also write the type as $\forall (m:\Bbb N).(\forall(p:m=2). m\le 2)$ but since the return type $m\le 2$ of the inner function doesn't depend on the proof $p$ (even though its output does), you can simplify it and use the arrow notation.

Yet another way to think of is that $\forall(x:A).B(x)$ (where I write $B(x)$ instead of $B$ to emphasize that it can depend on $x$) is often written $\Pi(x:A).B(x)$ in type theory. And it makes sense because in a way, this expressions gives you a way to define a type $B$ given $x:A$. And the you look at the set of all functions that take an input $x:A$ and return an element of $B(x)$. Now think of the cartesian $\prod_{x\in A}B(x)$ product of the elements of the set $\{B(x)|x\in A\}$. An element of that is a big tuple indexed by $A$ and if you ask the element in the spot $x\in A$, it gives back an element that's in $B(x)$. So it's the exact same thing. Also note that when you take $B$ to be constant, you get $\prod_{x\in A}B$ which is usually denoted $B^A$ or $A\to B$.


Two way deterministic pushdown automaton accepting word consisting of two equal words

Here are the two basic ideas.
(1) After checking that the input length is even, move to the middle position of the input.
The trick to find that position uses the stack in a similar way that we recognize the language $\{\;a^{2n}b^n \mid n \ge 0\;\}$.
(2) Then check that the two halves are equal.
Here the stack is used in a similar way that one recognizes the language $\{\; ww^R \mid w\in\{a,b\}^*\;\}$, except that the head does not move forward in both cases.


How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

Sure, $y^0$ is $\epsilon$, but that does not make $|y|=0$.
Consider $y=\mathit{foo}$. Here, $|y|=|\mathit{foo}|=3$, yet $(\mathit{foo})^0=\epsilon$.
No contradiction – $y$ is unchanged.


is the problem of parallelising any program, NP-complete?

It is not clear what exactly you want of that compiler, so let me explore several possibilities.

Optimize the parallelism

This is impossible. Optimizing even sequential runtime is not computable, and a similar proof shows the same for parallel runtime. The proof also extends to any notion of "almost optimal" like within a constant factor or something similar.

Thus, any notion of parallelization in this direction is not even in NP, and it's not even close.

Get some parallelism

Without defining exactly what "some" means we can not classify the problem in terms of complexity. There are certainly things that modern compilers can do, for instance vectorize suitable for-loops -- but all of these are certainly not NP-hard to detect (or they wouldn't do them).

I'm certain that you can carefully define some parallelization feature that is NP-complete to detect. I'd especially look towards coarse-grained parallelism, though exploiting that requires serious rewrites of code.

Do anything

That's trivial and hence boring. For instance, standard data-flow analyses will identify (sub)sequences of statements that are independent and can thus be reordered or, in principle, be executed in parallel. This will get you some very fine-grained parallelism that may not even gain you a speed-up, and will certainly not scale to many processors, but well.

Some language have features to tell the compiler that two things are independent, e.g. method calls, and that way lies potential gain. Then it's easy for the compiler again, though.


First, let me change your definition of PP a little bit:

On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$

On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$

Here, I replaced the error term with $\epsilon(n)$ and added $\geq$ and $\leq$. If we don't include $\leq$ and $\geq$, then problems in $BPP$ would not fall under our definition of $PP$.

You can replace the error with any small $\epsilon(n)>0$ you want, but you are not accomplishing anything by going past $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$.

Realistically, we do not need an error term smaller than $\epsilon(n)^{-1} = 2^n$ because you can amplify the error by a polynomial amount to get $2^{poly(n)}$ (since we are a polynomial time machine).

We unfortunately can't amplify beyond this, but that turns out not to matter. There does not exist a probabilistic polynomial time Turing machine that can accept or reject with error probability $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$. A probabilistic polynomial time Turing machine does not have a large enough number of configurations to accept or reject with such a fine grained/detailed error.

To see what I mean, think about how you would design a PPTM that outputs YES with probability just $1/2^{2^n}$. The best you could do is use almost all of your runtime to generate $poly(n)$ random bits and accept if they are all $0$'s. The probability of this happening is bounded by $1/O(2^{poly(n)})$.


Number of possible heaps on $\{1,...,2^h-1\}$

The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.

Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C_{h-1}$ appears). You just have to think of how to split $2^{h}-2$ keys between left and right (the key of the root is uniquely determined, since it is a heap).

I will edit this answer if it is not clear enough.


First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all independent sets of size $k$ contain $v$. Accordingly, remove $v$ and all its neighbors, and find an independent set of size $k-1$ in the remaining graph. In this way, you can recover an independent set of size $k$.

Second, how to check whether a graph contains at least two independent sets of size $k$, assuming $k \geq 2$. First, you determine whether in contains at least one. Suppose that it does, say $I$. If $J$ is any other independent set, then $I \setminus J$ and $J \setminus I$ are both nonempty (since $|I| = |J|$). In particular, if $x \in I \setminus J$ and $y$ is any other vertex in $I$, then even after adding the edge $(x,y)$, the set $J$ will constitute an independent set.

This leads to the following algorithm: for each pair of vertices $x,y \in I$, check whether $G + (x,y)$ contains an independent set of size $k$. If so, this independent set is necessarily different from $I$. Conversely, if an independent set of size $k$ different than $I$ exists, then necessarily it will be an independent set in $G + (x,y)$ for some $x,y \in I$.

Third, how to check whether a graph contains exactly two independent sets of size $k$. This is the same as checking whether a graph contains at least three independent sets. I think that at this point, it's better if you try to generalize the above argument from two to three independent sets. You might get stuck, but you won't know until you try.


Can we obtain a state diagram of a single Turing machine

There are two possible meanings of state here:

One of the finite states in the finite control mechanism of the Turing machine.
The entire state of the Turing machine, including its internal state (the one from the previous definition), the locations of the heads, and the contents of the tapes.

If you are looking for a state diagram of the second type, then it's infinite. If you're looking for a state diagram of the first type, then it's finite.

Different programs seem to have different number of states – every program is finite (has finitely many states, under the first interpretation above), but there is no bound on its length: it can be as long as you want, as long as it's finite. The same is true for Turing machines.


Techniques to prove a language is not DCFL

There is a direct type of argument, related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). Then if one input string is the prefix of another, the computation for the longer string must have the shorter computation as prefix. Thus, the computation accepts at (at least) two moments.

As an example, $\{ a^n b^m \mid n\ge1, m=n \mbox{ or } m=2n \}$ is not DCFL; which is seen as follows.

Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewire $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\{ a^nb^nc^n\mid n\ge 1\}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.


Algorithm for finding optimal branch points

If whatever happens after $B$ depends on that, you can't "reuse" any runs after a modified $B$. So the tree-like scheduling is really the best that can be done.

If the later steps are independent of (some) of the previous steps, things get more interesting... but that presumes you have a completely reliable way of determining that. The simplest way to get the most efficient runs without too much extra work in this case would be just to store away the results of all runs, and instead of running any of them first check if the result is already stored (memoisation). Might need to supplement with some logic to clean up (delete results that won't be used ever again, or use some heuristic to delete them).


Approximating unique string occurrences using a small, fixed amount of memory

Your problem is known as the count-distinct problem. The Wikipedia page describes some of the algorithms which have been designed for this problem.


MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP

Let's start by describing a polytime reduction $f$ that takes a 3CNF $\varphi$ to another $f(\varphi)$ such that:

$\varphi$ is satisfiable iff $f(\varphi)$ is satisfiable.
We can always satisfy all clauses of $f(\varphi)$ but one.

The idea is very simple: add a new variable $x$, replace each clause $\alpha \lor \beta \lor \gamma$ with 3CNF clauses equivalent to $x \lor \alpha \lor \beta \lor \gamma$ (i.e. with the clauses $x \lor \alpha \lor \lnot T$, $T \lor \beta \lor \gamma$ for a new variable $T$ appearing only in these clauses), and add the clause $\lnot x$. We can always satisfy all clauses but the last by having setting $x$ and all $T$ variables to true. On the other hand, the entire 3CNF is satisfiable if and only if the original one is.

We deduce that $\varphi$ is unsatisfiable iff $c(f(\varphi)) = |f(\varphi)|-1$, where $|f(\varphi)|$ is the number of clauses in $f(\varphi)$. This shows that MAX3SAT is coNP-hard. So if MAX3SAT is in NP then NP=coNP.

Conversely, as observed by David Richerby, MAX3SAT is in the polynomial hierarchy (indeed, in $\Delta_2^P$) since $c(\varphi) = k$ iff some assignment satisfies exactly $k$ clauses, and all assignments satisfy at most $k$ clauses. If NP=coNP then the polynomial hierarchy collapses to the first level (i.e. NP), and so MAX3SAT is in NP.


Computer Architecture-3 level RAM hierarchy

Cache memory levels are inherently a "subdivision" of main memory (RAM). To speed up the access of RAM, the cache was created using the notion of "The Principle of Locality". Frequently in programs, memory is accessed in locations that are close (local) to previously accessed locations, so it benefits to keep sections of data stored in nearby cache instead of going all the way to the hard drive. Also, cost has historically been a factor. Cache memory is more expensive than memory space on a hard drive, etc. Keep in mind, the landscape of computer memory models is always changing, and it is likely that other methods will be used in the future to speed up memory access. I think the current trend is to move away from mechanical storage devices with moving parts, hence the SSD's.


Is all data stored in computers stored as machine code?

I wouldn't put it that way.  What is stored in memory is bits.  It's just data in binary form.
Humans might then label some of those bits as "machine code" because we intend or expect it to be executed; or because it will be executed.  That's a matter of interpretation we apply.  The memory module just sees a bunch of bits.  It just sees some data and has no knowledge of what the meaning or intended purpose of that data will be.
Memory is not limited to storing executable code.  Computers also store other data in memory.  For instance, your computer might store a copy of an email, or a picture or photograph you took.  Those aren't code, but they can be stored in memory.
It may be helpful to think that the memory can be used to store data or can be used to store code -- but there is nothing in the computer architecture that enforces any distinction between the two.  From the perspective of the memory module, it is just bits.


What is the time complexity of this method?

The worst-case time complexity is $O(n^{2})$.

Consider the example string "aaaaaaaaaa" — that is, 10 'a's. This happens to be the worse case edge scenario, because j++ has to run for every remaining character in the string, at every position. When i=0, the while loop will run 9 times; when i=1, 8 times; so on until when i=N-1, the loop runs 0 times. Therefore, the total number of times the while loop has to run (over all i) is given by the sum from 0 to N-1, which, with arithmetic series, is $S = \frac{N}{2}(N-1)$. This simplifies to $\frac{N^{2}-N}{2}$; however, when writing time complexity with big-O notation, we ignore constant or slower-growing factors. Therefore, as $N$ grows asymptotically large, the total time complexity reduces to $O(N^{2})$, although in reality it is something closer to $O(\frac{N^{2}}{2})$.

Another way to look at it is that the outer for loop runs exactly $N$ times, and the number of times the inner while loop runs does depend on $N$ (and linearly at that), so the time complexity must be at least greater than $O(n)$.


What does a polynomial time reduction mean?

Be careful, you probably mean a reduction from a problem to another, and not a reduction from an algorithm to another.

When a problem $A$ is polynomial time reducible to a problem $B$, it means that given an instance of $A$, there is an algorithm for transforming instances of $A$ into instances of $B$. This is often done to derive hardness results: if there was a fast algorithm for some problem, there would also be a fast algorithm for some other problem. The Wikipedia article on reductions gives as an example problem pair multiplication and squaring. Both of these happen to be rather easy problems, of course.

It doesn't matter what your problems look like and how the transformation actually works, as long as it is both correct and polynomial time.


Is there a difference between top-down and bottom-up dynamic programming?

To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space.  If you know what the lowest level calculations are going to be and the dependency order going upward, it makes sense to iteratively do them in the proper order and store those results.  Factorials, naive Fibonacci and the Euler recurrence relation for partitions are all good examples of problems suited to this approach.

Some problems don't have an easily determined bottom or dependency order for the calculations.  Chess positions evaluations, for example, are usefully memoized by position, with the evaluation score stored so it need not be recalculated.  Positions can recur at multiple levels of the search tree due to move transposition and repetition so saving evaluation results is worthwhile.  But there's no way to know what the positions at the lowest levels of the tree are going to be without recursively descending (and taking into account intermediate pruning) so top down is really the only feasible approach.


Running time of an algorithm containing binary elements for cryptography

We take only one step for computing each $2^ix_i$ (By using left-shift operation we can compute $2^i$ in constant time). So the complexity of Algorithm $\mathcal{A}$ is $\mathcal{O}(n)$.

I suspect you used loop for computing $2^i$, and this incurred your bad result.

PS : sorry for my bad english


Is how much memory a program needs computable?

No, and there's a simple way to see it.

Suppose that there was a way to compute how much memory a program needs. What does it mean precisely? It would mean that there's a way to find, given an arbitrary program¹, a number $n$ such that the program can run on a machine with $n$ bits¹ of memory.

First snag: what about programs that require an infinite amount of memory? Our memory analyzer would have to return something like $\infty$ in that case. Ok, that's not too bad — we could have an analyzer that returns either a (finite) amount of memory or $\infty$. If the program needs an infinite amount of memory, it doesn't terminate (each step of computation can only access a finite amount of memory).

If the memory analyzer returns a finite amount $n$, then we can run the program in a machine with $n$ bits of memory. But a “machine with $n$ bits of memory” is a finite automaton! Deciding whether a finite automaton terminates is easy.

So our memory analyzer has let us decide whether the program terminates. Since this is impossible (it's the halting problem), the hypothesis that there's a way to compute how much memory a program needs is false. If you have a correct memory analyzer (i.e. one that returns $n$ or $\infty$ if a program can run in at most $n$ bits of memory) then there must be programs for which the analyzer returns $\infty$, yet the program could in fact run in a finite amount of memory.

¹  A program including all of its inputs! The amount of memory is a function of the inputs in general.
²  You can use any unit, bits are just an example. That only changes the amount of memory from a finite number to a different finite number.


How are alphabetic characters programmed into a computer?

It isn't stored anywhere. 01100001 could represent anything. It could be the ASCII character "a" or it could be the integer 97 or it could even be something different entirely. It's up to the programmer to tell the computer what to do with 01100001, for instance by supplying a font file that tells it how to map binary sequences to the instructions to draw a character on the screen. Often this is taken care of in libraries but the OS and motherboard have no idea that 01100001 represents "a".


How the Abstract DPLL Algorithm Works in SAT Solving

Describing DPLL as a series of state-transition rules is the worst way I've ever seen to aid understanding the algorithm.  The pseudocode provided in the WIkipedia article on DPLL is much easier to understand if you're approaching the algorithm for the first time.

;Algorithm DPLL
;Input: A set of clauses Φ.
;Output: A Truth Value.

function DPLL(Φ)

if Φ is a consistent set of literals
   then return true;
if Φ contains an empty clause
   then return false;
for every unit clause {l} in Φ
   Φ ← unit-propagate(l, Φ);
for every literal l that occurs pure in Φ
   Φ ← pure-literal-assign(l, Φ);
l ← choose-literal(Φ);
return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

Decision literals are the literals returned by the choose-literal function called above.  Annotated literals are just literals that are members of M that are marked in some way so the DPLL implementation can distinguish decision literals from literals added to M by unit propagation.  This marking is for the sake of the backjumping code which must unroll assignments until the one responsible for the current conflict is found and then replace it.

Note that the original DPLL algorithm did not have backjumping in it.  It simply backtracked, either reversing the current assignment or returning false if the algorithm had run out of assignments to try.  Backjumping was a later innovation.

Note also that pure literal assignment isn't usually done in modern SAT solvers that implement some form of DPLL.  It is a fairly expensive check to do in an algorithm expected to recurse and backtrack an exponential number of times and the benefits of doing the check don't outweigh the costs.


Importance of a person to another person in social network

yes, social networks have a simple (graph) connectivity property in many or most cases/ situations/ contexts (such as "friend" connections on a social network like Facebook etc), but also a weighted property of the graph in various other situations. a common aspect of this now measured is widely/ generally referred to as the influence of the "friendship". two users may be connected, but influence measures other aspects.

one aspect of high interest to marketers and driving a lot of research is how much "friends" influence each others purchasing decisions ie if person A buys x, does that influence friend B to buy x also, or a y similar to x. here are a few papers/ refs on this subject. there are different ways to attempt to measure influence and in some cases it may be derived/ estimated that some users have more friends and are more thus influential on those friends, in other ways it can be determined from additional data such as looking at buying patterns of A, B if A, B are connected etc.

buying influence is just one of the major/ dominating areas of weighting under study, but there are various others. another key aspect coming up in 2016 in the US is voting influence that is under some study also, ie tendency of connected users to vote in similar ways.

Determining Influential Users in Internet
Social Networks / Trusov, Bodapati, Bucklin
Do Friends Influence Purchases in a Social Network? / Iyengar, Han, Gupta
HOW FRIENDS INFLUENCE US ON SOCIAL MEDIA (AND WHAT THAT MEANS FOR MARKETERS) / fast company


Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm

The reason that 3SAT is hardest empirically when the clause-to-literal ratio is 4.2 is because this is the satisfiability threshold (the threshold at which a random 3SAT becomes unsatisfiable with high probability). However, this is a very different type of hardness than NP-hardness. First of all, the model is different: you are generating a random 3SAT instance with a given clause-to-literal ratio, and hardness applies only on average. Second, there is no formal connection between the satisfiability threshold and computational hardness. There are some properties of the solution space which we think make the problem hard near the satisfiability threshold, but this is just a heuristic.

Now for your actual questions:

While there are definitely no formal results, it might be the case that known practical approximation algorithms for MAX-3SAT perform poorly near the satisfiability threshold.
No idea.
You are asking two questions. Regarding your first question, if you had an algorithm which approximated MAX-3SAT only on satisfiable instances, say achieving 99% performance, you could run it on any given instance, and so determine whether it is satisfiable or less than 99% satisfiable. We know that this is unlikely as long as the performance is larger than 7/8. Regarding your second question, the instances coming out of the hardness proof are not arbitrary, so there is a class of formally "hard instances", but I don't think it has anything to do with the satisfiability threshold.


How to solve recursion T(n) = T(n/3) + T(2n/3) + n?

Look at the recursion from QuickSort for the average case:
$T(n) = T(n/2) + T(n/2) + n$
which ends up in $O (n \log n)$.
Note that $n/2 + n/2$ sums up exactly to $n$. Just like $n/3 + 2n/3$ sums up exactly to $n$. Substitute the formula for $T(n)$ in $T(n/3)$ and $T(2n/3)$ and you'll see it's the sum of $T(x)$ for four values $x$ which add up to $n$, plus $2n$. Substitute again, and you see it's the sum of $T(x)$ for eight smaller values $x$ which add up to $n$, plus $3n$. And so on. Since the $x$ shrink by at least a factor $2/3$, the number of rounds until you end up at $T(1)$ is $O(\log n)$.
So that's what you guess, and once you guessed it you can prove it: $T(n) = O (n\log n)$.


Solving recurrences (tree method) with square roots

$n^2 \cdot \sqrt{n} = n^{5/2}$, then you can proceed with the Master Theorem as normal.

If you specifically need to use the Recursion Tree Method for solving recurrences, then you can still proceed normally.

Root Level : $n^{5/2}$
Next Level : $4 \cdot (n\ /\ 2)^{5/2} = 2^{4/2} \cdot n^{5/2}\ /\  2^{5/2} = n^{5/2}\ /\ 2^{1/2}$
Next Level : $16 \cdot (n\ /\ 4)^{5/2} = 4^{4/2} \cdot n^{5/2}\ /\ 4^{5/2} = n^{5/2}\ /\ 4^{1/2}$
etc.


Average case analysis by key comparisons of Max Sort

The number of comparisons on an array of length $n$ is $\binom{n}{2}$, regardless of the contents of the array. Therefore all of the following are $\binom{n}{2}$: the worst-case number of comparisons, the best-case number of comparisons, and the average-case number of comparisons, with respect to any input distribution.


Ambiguous Grammar and SLR parsing table : No conflicts?

In state 9, you can reduce either $S$ or $S'$, as well as the possible shift action for $e$. So there are both reduce/reduce and shift/reduce conflicts.

The production $S' \rightarrow \epsilon$ cannot be correct; there is already a production $S \rightarrow iCtS$ for an if without an else, so if $S'$ can derive the empty string, $S \rightarrow iCtSS'$ is ambiguous. Once you remove that, you will still have the shift-reduce conflict with $e$. (Since an SLR parser doesn't use lookahead to restrict reduce actions, the entire row for a state with a reduce action must consist of precisely that reduce action. But this particular grammar is ambiguous, so using LALR(1), for example, won't help.)

Finally, $\epsilon$ is not a symbol; it is simply a way of making an empty symbol sequence visible. So it cannot be the head of a column the action table, and also it cannot be on the right hand side of the dot in an item.


Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

In your step 3b, you have to carry out at most $\deg(u)$ many decrease-key key operation. Thus in total you need $\sum \deg(u) = 2m$ many decrease-key operations. A single decrease key runs in $O(1)$ amortized time (Fibonacci Heaps). Thus the total running time is $O(m+n\log n)$. If you are not using Fibonacci heaps the running time is slower. Something like $O(m \log n )$.

I do not see how you got to $O(m+n\log n)$ by following your arguments. Also its unclear how you can do all the decrease-key key operation for one step in $O(n)$ time.


Find shortest prefix to generate original string by overlapping

What you are looking for is called the quasiperiod of a string. If such a string has a quasiperiod of $|S|$ it is called superprimitive, and can not be covered by a substring.

A method for computing it in $O(n)$ time is given in "An On-Line String Superprimitivity Test" by Dany Breslauer. You might also be interested in "Of Periods, Quasiperiods, Repetitions and Covers" by Alberto Apostolico and Dany Breslauer.


What does a faster algorithm mean in theoretical computer science?

No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.

In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.

If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $\Theta$ rather than just as a big $O$.


You are confusing two or three different concepts here:

Languages: these are collections of strings.
Context-free grammars: this is a specific way to describe languages.
Parsing: this is the process in which a computer "understands" input.

You haven't explained what you mean by "arithmetic"; some people think of arithmetic as the set of first-order statements about the natural numbers which are true, for example. However, it seems that by arithmetic you mean the set of well-formed arithmetic expressions (you leave out some important details, for example, what atoms are allowed, whether whitespace is allowed, and so on). Assuming this, arithmetic is most certainly not a context-free grammar, simply because arithmetic is a language, not a grammar. However, it can be described as a context-free grammar, as you demonstrate.
The next thing you are worried about is parsing ("order of operations"). Grammars describe languages, that is, sets of strings; parsing is a separate issue. It is true that context-free grammars are intimately related to parsing, via parse trees. It is possible to construct a context-free grammar for the language of arithmetic expressions that reflects "order of operations", in the sense that we can use the parse tree directly to evaluate the expressions in a recursive way (in the fashion of attribute grammars.
For example, suppose that the only atom is $n$, and that we are only interested in addition and multiplication, and allow parentheses; and furthermore, multiplication has higher priority than addition, and both associate to the left. This is reflected in the following grammar:
\begin{align}
&\mathit{EXPR} \to \mathit{EXPR} + \mathit{TERM} \mid \mathit{TERM} \\
&\mathit{TERM} \to \mathit{TERM} * \mathit{FACTOR} \mid \mathit{FACTOR} \\
&\mathit{FACTOR} \to (\mathit{EXPR}) \mid n
\end{align}
You can check that $n+n+n$ is "understood" as $[n+n]+n$, and $a+b*c$ is understood as $a+[b*c]$, for example. Moreover, this grammar is unambiguous (unless I made a mistake), that is, any word in the language has a unique parse tree.
In practice, starting with an ambiguous context-free grammar and precedence rules (including associativity), parser generators can create equivalent unambiguous context-free grammars (or more accurately, parsing algorithms).


Why are there no complete problems for NP ∩ coNP?

It is still open whether $\mathrm{NP\cap coNP=QP}$, where $\mathrm{QP=\cup_k2^{log^k(n)}}$.
And in this answer, we have shown that $\mathrm{QP}$ has no complete problem.
If now someone shows that $\mathrm{NP\cap coNP}$ has some complete problem, that would imply $\mathrm{NP\cap coNP\neq QP}$.


Viewing images that compressed using lossless algorithms

Image is decompressed before viewing for the most time.
It is not necessary to decompress it fully if this is very big image and you have preview of the top left cropped area - only needed rows could be decompressed up to visible part.
This is highly implementation dependent, some programs use system built-ins (Windows format BMP) some disregard this and use own (on other systems Windows BMP is not generally built-in).
It may be stored in RAM, on disk, translated to internal format. There is no reason to stick with one scheme.

There are no references as this is implementation specific.
But I can share with my own scheme: I always unpack compressed data, never depend on external libraries, store it on internal format and since I use it in image editor - I store in RAM last three operations used on images.
They can be huge (800k x 600k) so if that is the case I put only visible part to RAM.
Since BMP can come in up side down format and other compress techniques prevent me from mapping coordinates to file, I explicitly store them as small sized decompressed grid (something like Google Maps do).


Time Complexity of a Union Find algorithm

Figured this out. Since uf.Union is an inverse ackermann it grows so slowly that it could be considered constant. thus the second loop would run O(clgn) giving and expected output of O(n + clg n))


Represent the events as a bipartite graphs: the vertices are the users and subjects and the edges are events (so there's an edge from user $x$ to subject $y$ if there's an event involving that user and subject).  What you're looking for is essentially a minimal vertex cover. A vertex cover is a set $C$ of vertices such that every edge includes at least one vertex from $C$. A minimal vertex cover is one that includes the smallest possible number of vertices.

Example. If the events are "John likes pizza", "John likes candy" and "Jane likes candy", the graph has vertices John, Jane, pizza and candy and the edges are John–pizza, John–candy and Jane–candy. A minimal vertex cover would be John and candy (in this case, there are several other minimal vertex covers).

For general graphs, finding minimal vertex covers is NP-hard but, for bipartite graphs, there is a polynomial-time algorithm because of König's theorem, which says that finding minimal vertex covers of bipartite graphs is equivalent to finding maximum matchings (i.e., a biggest-possible set of edges such that no pair of edges in the set shares an endpoint), which can be done by the Hopcroft–Karp algorithm.  The algorithm for finding a minimum vertex cover from a maximum matching is described in the "Proof" section of the Wikipedia König's theorem page.

Let $C$ be the minimum vertex cover that you just computed, and let the vertices in it be $c_1, \dots, c_k$ (so each $c_i$ is either a user or a subject).  The groups are $g_1, \dots, g_k$, where $g_1$ is all the events that involve the user or subject $c_1$and, for $i>1$, $g_i$ is the set of all events that involve the user or subject $c_i$ that haven't already been included in one of $g_1, \dots, g_{i-1}$.


Why theta(n^2) if m=floor(n/2) for Naive String-matching

Here is the relevant excerpt from Introduction to Algorithm by CLRS, 3rd edition.

  Procedure NAIVE-STRING-MATCHER takes time $O(n - m +1)m$, and this bound is tight in the worst case. For example, consider the text string $a^n$ (a string of $n$ a’s) and the pattern $a^m$. For each of the $n-m+1$ possible values of the shift $s$, the implicit loop on line 4 to compare corresponding characters must execute $m$ times to validate the shift. The worst-case running time is thus $\Theta((n-m+1)m)$, which is $\Theta(n^2)$ if $m=\lfloor n/2\rfloor$.

Proposition: Let $f(n,m)=\Theta((n-m+1)m)$ be the worst-case running time where $1\le m\le n$. If $m=\lfloor\frac n2\rfloor$, then $f(n,m)=\Theta(n^2)$.

Proof. There are constants $c_1, c_2\gt0$ such that for all $1\le m\le n$,
$$c_1((n-m+1)m)\le f(n,m)\le c_2((n-m+1)m).$$

Now let $m=\lfloor \frac n2\rfloor$. Since $1\le n+1-2\lfloor\frac n2\rfloor\le2$, for $n\ge2$,
$$ \begin{align}
\frac{n^2}4&\lt\left(\frac{n+1}2\right)^2-1\\
&\le \left(\frac{n+1}2\right)^2-\left(\frac{n+1-2m}2\right)^2=(n-m+1)m\\
&\le\left(\frac{n+1}2\right)^2-\frac14\lt n^2
\end{align}$$
So $$\frac{c_1}4n^2\lt f(n,m)\lt c_2 n^2,
$$
which says $f(n,m)\in \Theta(n^2)$.


Any problem in P can be reduced to the language of odd integers

Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties:

$f$ can be computed in polynomial time.
If $x \in S$ then $f(x) \in A$.
If $x \notin S$ then $f(x) \notin A$.

Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows:

Determine whether $x \in S$.
If $x \in S$ then output something in $A$.
If $x \notin S$ then output something not in $A$.

You take it from here.


Is O(|A| + |B|) the size of the union of two synchronized DFAs A and B?

Your conjecture is wrong. Consider the following languages:

$L_1$ is the language of words over $\{a,b,c\}$ such that the number of $b$s after the last $a$ is a multiple of $x$.
$L_2$ is the language of words over $\{a,b,c\}$ such that the number of $c$s after the last $a$ is a multiple of $y$.

The minimal DFA of $L_1$ contains $x$ states, and that of $L_2$ contains $y$ states. Both DFAs have $a$ as a synchronizing word. The minimal DFA for $L_1\cup L_2$ contains $xy$ states (and also has $a$ as a synchronizing word).


I'm not sure inverting these equations will help you gain any understanding. Consider for example the simple case in which $a = b$. In that case,
$$
x'^2 + y'^2 = (x^2 + y^2) (1- a\|P\|)^2 = \|P\|^2(1-a\|P\|)^2,
$$
and taking square roots,
$$
\sqrt{x'^2+y'^2} = \|P\|\,\big|1-a\|P\|\big|.
$$
You know the left-hand side. The right-hand side is either $\|P\|(1-a\|P\|)$ or $\|P\|(a\|P\|-1)$ (though I'm not sure the latter is physically possible in your case), and in each case you get a quadratic for $\|P\|$. You get at most four solutions for $\|P\|$, and for each positive one you can substitute back, calculate $x,y$, and check that the equations are satisfied.

The case $a \neq b$ looks more complicated, but perhaps can be solved explicitly using a bit of creative algebra. Failing that, there are numerical method that can invert these equations.


Algorithm to return largest subset of non-intersecting intervals

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem).

We first sort the intervals by their right end point. Suppose the sorted order is
$I_1, I_2, \ldots, I_n$.

Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval being the rightmost interval in that set. We pick the interval which gives the maximum (as any non-intersecting set has a rightmost interval).

This we do using dynamic programming.

Suppose we have computed the sizes (say $S_1, \ldots, S_n$) for intervals up to $k-1$.
Now you want to compute for $I_k = [L_k, R_k]$.

Pick $L_k$, and do a binary search in $[R_1,R_2, \ldots, R_k]$. Say $R_j \lt L_k \lt R_{j+1}$.

Now all the intervals $1,2,\ldots,j$ do not intersect $I_k$ (and all others up to $I_{k-1} \cap I_k$). Thus we need to pick the max among $S_1, S_2, \ldots, S_j$ and add $1$ to it. This maximum can also be computed dynamically, in a separate array, along with the $S$.

This can be implemented so that the whole algorithm runs in $O(n \log n)$.

We can also modify this algorithm a little to give you the actual intervals which form the non-intersecting set.